Geographic Based Dynamic Routing in LEO Satellite Networks

1.1. Background

Low Earth Orbit (LEO) satellite constellations, exemplified by Starlink [LEO] and OneWeb, are rapidly transforming global Internet access. Compared to traditional Geostationary Earth Orbit (GEO) satellites, LEO satellites offer significantly lower transmission delay (20-50 ms), higher bandwidth efficiency, and lower launch costs.¶

However, LEO satellite networks present unique technical challenges, most notably the highly dynamic nature of network topology. Satellites in LEO constellations travel at orbital velocities of approximately 7.5-7.8 km/s, completing an orbit in roughly 90 minutes. Each satellite typically maintains four inter-satellite links (ISLs): two intra-plane links (forward and backward along the same orbital plane) and two inter-plane links (left and right to adjacent orbital planes). Intra-plane ISLs remain relatively stable due to minimal relative motion between co-orbital satellites. In contrast, inter-plane ISLs face continuous topology changes because adjacent orbital planes are non-parallel, and satellites can only maintain stable inter-plane connections with co-directional neighboring satellites for limited time periods.¶

1.2. Problem Statement

The extreme dynamicity of LEO satellite networks renders traditional routing protocols fundamentally unsuitable:¶

1. Topology Dynamicity Breaks Traditional Routing¶

   Traditional routing protocols such as OSPF [RFC2328], IS-IS [RFC1195], and BGP [RFC4271] were designed for static or low-dynamicity terrestrial networks. Their operational model relies on periodic or event-triggered synchronization of routing information across the entire network. In LEO satellite networks, this approach fails catastrophically:¶

   • Massive state synchronization overhead: Frequent topology changes trigger continuous link-state flooding, consuming enormous bandwidth and processing resources.¶

   • Convergence failure: With handovers occurring every 11-15 seconds and network scales reaching tens of thousands of satellites, traditional protocols cannot converge within the interval between topology changes. The network remains in a perpetual state of re-convergence.¶

   • Routing loops and black holes: Rapid topology changes cause routing inconsistencies, leading to transient loops and packet loss.¶

   • Resource exhaustion: Satellites have limited computational power, memory, and bandwidth. Processing hundreds of thousands of terrestrial routes while simultaneously managing constant topology updates exhausts these scarce resources.¶

2. Fixed IP Addressing Conflicts with Dynamic Topology¶

   Traditional IP addressing binds prefixes to geographic regions. In LEO networks, the same geographic area is served by different satellites at different times. Using fixed IP prefixes would require updating prefix bindings across the entire network every 15 seconds, which is operationally infeasible.¶

3. Predictable Motion Is Underutilized¶

   Although satellite topology is highly dynamic, satellite motion follows entirely predictable orbital mechanics. Existing routing approaches fail to exploit this determinism, instead using stochastic methods designed for uncertain environments.¶

4. Terrestrial Route Injection Overwhelms Satellites¶

   The terrestrial Internet contains hundreds of thousands of BGP prefixes. Injecting these into the satellite network would cause each satellite to maintain massive routing tables, consume bandwidth for route synchronization, and exhaust onboard resources. Satellites would spend more resources learning routes than forwarding traffic.¶

1.3. Objectives

The proposed mechanism aims to:¶

1. Decouple addressing from physical location to hide satellite mobility from the routing system.¶

2. Eliminate the need for network-wide routing state synchronization.¶

3. Reduce onboard computational and memory requirements.¶

4. Leverage predictable satellite ephemeris for pre-computed, time-sliced routing tables.¶

5. Enable seamless integration between the dynamic satellite segment and the static terrestrial Internet.¶

1.4. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

3.1. Network Segmentation

The overall architecture includes UT, user WR, UT, inter-satellite links, GS and PoP that connect satellite networks to the terrestrial Internet. Due to the high relative velocity between satellites and ground infrastructure, frequent handovers are required. For example, Starlink performs beam switching approximately every 15 seconds.¶

+---+   +---+   +--+   +---+     +---+   +--+   +---+   +----+
|DEV|<->|WR |<->|UT|<->|LEO|<--->|LEO|<->|GS|<->|PoP|<->|INET|
|   |   |   |   |  |   |Sat|     |Sat|   |  |   |   |   |    |
+---+   +---+   +--+   +---+     +---+   +--+   +---+   +----+
  ^               ^                        ^               ^
  |<-Terrestrial->|<----- Satellite -----> |<-Terrestrial->|
  |    Segment    |        Segment         |    Segment    |

- INET: Internet

The end-to-end network is logically divided into two segments:¶

Terrestrial Segment: From the DEV to the UT, and from the GS to the PoP and beyond. This segment uses traditional IP prefix-based routing (IPv4 [RFC791] or IPv6 [RFC8200]).¶

Satellite Segment: From the UT through the inter-satellite network to the GS. This segment uses geographic region coding for IP address, decoupling the destination address from the current physical location of the serving satellite. It is supposed the user traffic will be encapsulated in tunnel in this proposal.¶

3.2. Key Design Principles

1. Address-Satellite Decoupling: the address of satellite is not fixed, but periodically changed per geographic region coding.¶

2. Predictive Routing: Routing tables are pre-computed using satellite ephemeris data for each time slice, eliminating runtime route computation and flooding.¶

3. Localized State: Each satellite only needs to know connectivity information for its own and adjacent orbital planes, not the entire network topology.¶

4. Directional Forwarding: Routing decisions resolve to one of six directions: North, South, East, West, Down (to ground), or Up (to upper level shell).¶

5. Centralized Route Computation: A ground control unit centrally computes time-sliced routing tables using global constellation ephemeris and distributes validated routing tables to satellites, reducing onboard computation and ensuring routing consistency.¶

4.1. Hierarchical Grid Partitioning

The Earth's surface is partitioned into a hierarchical grid system. This document uses the H3 spatial index [H3] as a reference model, but other hierarchical geospatial indexing systems MAY be used.¶

The H3 system partitions the globe into 122 base (Level-0) hexagonal cells. Each Level-0 cell is subdivided into 7 Level-1 cells, each Level-1 cell into 7 Level-2 cells, and so on. This yields:¶

• Level 0: 122 regions¶

• Level 1: 122 x 7 = 854 regions¶

• Level 2: 122 x 7^2 = 5,978 regions¶

• Level 3: 122 x 7^3 = 41,846 regions¶

• Level 4: 122 x 7^4 = 292,922 regions¶

• Level 5: 122 x 7^5 = 2,050,454 regions¶

• Level 6: 122 x 7^6 = 14,353,178 regions¶

At Level 6, the smallest region has an area of 36 square kilometer, providing sufficient granularity for LEO satellite routing. In reality, make sure each cell has one satellite is the finest granularity. According to this address allocation schema, the satellite will have dynamic address and UT/GS will have fixed address.¶

4.2. Geographic Region Code (GRC) Format

The GRC is encoded as a 32-bit value compatible with IPv4 addressing, enabling reuse of existing IPv4 forwarding hardware and software with minimal modifications. In case of IPv6, it can also be easily fit into 128 bits address.¶

 0               1               2               3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Shell |   Level 0   |  L1 |  L2 |  L3 |  L4 |  L5 |  L6 |  IF |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The 32-bit structure is organized as follows:
- Bits 0-3 (4 bits): Satellite shell index (0-15).
- Bits 4-10 (7 bits): Level-0 region index (0-121).
- Bits 11-13 (3 bits): Level-1 region index (0-6).
- Bits 14-16 (3 bits): Level-2 region index (0-6).
- Bits 17-19 (3 bits): Level-3 region index (0-6).
- Bits 20-22 (3 bits): Level-4 region index (0-6).
- Bits 23-25 (3 bits): Level-5 region index (0-6).
- Bits 26-28 (3 bits): Level-6 region index (0-6).
- Bits 29-31 (3 bits): Interface index (0-5) supports 6 directions.

**Note**: The encoding above is illustrative. Implementations MAY
          use alternative bit allocations that preserve the
          hierarchical property while fitting within 32 bits.

4.3. Segmented Longest Match

Traditional IP routing uses longest prefix match with arbitrary prefix lengths (0-32 bits for IPv4). For GRC-based routing, a segmented longest match algorithm is used:¶

• Match boundaries are fixed at specific bit positions corresponding to hierarchy levels: 11, 14, 17, 20, 23, 26, 29, and 32 bits.¶

• A routing table lookup attempts to match the destination GRC at each of these fixed lengths, starting from the longest (most specific) and falling back to shorter (less specific) matches.¶

• This approach is compatible with existing trie-based or TCAM-based forwarding hardware without modifications.¶

5.1. Dynamic Address Assignment

Satellites dynamically bind GRCs to their interfaces based on their current orbital position:¶

1. A satellite continuously determines its coordinates using onboard GNSS or ephemeris-based position calculation.¶

2. The geographic coding module converts the satellite's coordinates into the corresponding GRC at the appropriate hierarchy level.¶

3. When a satellite enters a new geographic region, it updates its interface addresses to reflect the new GRC.¶

4. A satellite MAY bind multiple GRCs simultaneously (analogous to multiple IP addresses on a single interface), representing the multiple geographic regions it currently covers.¶

5.2. Interface Direction Mapping

Each satellite maintains 6 logical interfaces corresponding to directional ISLs:¶

• North: Intra-plane link to the satellite ahead in the orbital direction.¶

• South: Intra-plane link to the satellite behind in the orbital direction.¶

• East: Inter-plane link to the satellite in the adjacent orbital plane to the east.¶

• West: Inter-plane link to the satellite in the adjacent orbital plane to the west.¶

• Down: Link to ground (UT or GS) or lower level shell.¶

• Up: Link from ground to satellite or upper level shell.¶

All interfaces are bound with a GRC-based address, and routing table determine the egress direction based on the destination GRC.¶

6.1. Ephemeris-Based Pre-computation

Satellite ephemeris data provides precise orbital parameters, enabling the prediction of each satellite's position at any future time. The routing system leverages this predictability as follows:¶

1. The orbital period is divided into discrete time slices. The duration of each time slice is a configuration parameter, typically set to be shorter than the minimum handover interval (range from seconds to minutes).¶

2. A ground control unit computes the predicted positions and connectivity of all satellites for each time slice using constellation ephemeris.¶

3. Based on these positions, the coverage area of each satellite is determined, and the set of GRCs served by each satellite is identified.¶

4. For each satellite and each time slice, a routing table is centrally computed that maps destination GRCs to egress directions (North, South, East, West, Down, Up).¶

5. The computed routing tables are validated and distributed to satellites prior to the corresponding time slice.¶

6. Satellites locally store and activate the downloaded routing tables at time-slice boundaries.¶

6.2. Routing Table Structure

The routing table for each time slice MUST support multi-path and multi-source reachability, containing entries of the form:¶

The egress direction is one of: North, South, East, West, Down, or Up. The next-hop field is optional and MAY be used for explicit next-hop specification in complex topologies.¶

To preserve the multi-source characteristics inherited from terrestrial protocols (e.g., BGP multi-homing), a single destination GRC prefix MAY resolve to multiple egress directions. The forwarding engine can execute Equal-Cost Multi-Path (ECMP), Unequal-Cost Multi-Path (UCMP), or Active-Standby switches based on the path attributes.¶

6.3. Routing Table Refresh

At each time slice boundary:¶

1. The time-varying routing module retrieves the pre-computed routing table for the new time slice from the routing database.¶

2. The module updates the forwarding information base (FIB) with the new routing table.¶

3. The old routing table is retained briefly (e.g., for one additional time slice) to handle packets in flight that were forwarded based on the previous table.¶

4. The local GRC bindings are updated to reflect the satellite's new position.¶

This periodic refresh replaces the event-driven link-state updates of traditional routing protocols, providing deterministic and bounded routing updates.¶

7.1. Encapsulation and Tunneling

User traffic enters the satellite network at the UT and exits at a GS. The end-to-end flow is:¶

DEV->WR->UT->[Satellite Network]->GS->PoP->Internet

Step 1: The DEV sends an IPv4/IPv6 packet destined for a remote content server. The packet traverses the user's local network to the UT.¶

Step 2: The UT queries the Routing Database with the destination terrestrial IP. To preserve multi-source characteristics, the database MAY return a list of multiple candidate PoPs and their corresponding GS GRCs. The UT applies a multi-source selection policy (e.g., spatial proximity, load balancing, or primary/backup policy) to select one or more target GS GRCs, and encapsulates the user traffic into a tunnel.¶

Step 3: The encapsulated packet traverses the inter-satellite network. At each satellite hop, the forwarding engine extracts the destination GRC from the outer header, performs a segmented longest match lookup in the current time-slice routing table, and forwards the packet in the appropriate direction (North, South, East, West, Down or Up).¶

Step 4: The GS receives the encapsulated packet, terminates the tunnel, and forwards the inner packet to the PoP using standard IP routing.¶

Step 5: The PoP performs NAT (if required) and injects the packet into the terrestrial Internet.¶

Step 6: Return traffic follows the reverse path through the same GS, satellite network, and UT.¶

7.2. Forwarding Algorithm

The forwarding algorithm at each satellite is:¶

1. Receive packet from ingress interface.
2. Extract destination GRC from packet header.
3. Perform segmented longest match on destination GRC using
   current time-slice routing table.
4. If match found:
     a. If egress direction is "Down":
        - Forward packet to ground link (GS or UT).
     b. Otherwise:
        - Forward packet to the corresponding ISL interface.
5. If no match found:
     - Drop packet and optionally generate an ICMP unreachable
       message.
6. Update packet TTL/hop limit.

7.3. Handling Local Traffic

If the destination GRC matches one of the GRCs currently bound to the local satellite, the packet is delivered to upper layer protocol.¶

8.1. Geographic Coding Module

The geographic coding module is responsible for:¶

• Converting satellite coordinates (latitude, longitude, altitude) into the corresponding GRC.¶

• Determining the set of GRCs covered by the satellite's footprint at the current position.¶

• Updating interface address bindings when the satellite enters new geographic regions.¶

The module MUST support real-time coordinate updates at a rate sufficient to track satellite motion (e.g., at least 1 Hz).¶

8.2. Time-Varying Routing Module

The time-varying routing module is responsible for:¶

• Loading the pre-computed routing table for the current time slice from the routing database.¶

• Managing the transition between time slices, including FIB updates and table retention policies.¶

• Synchronizing with the satellite's onboard clock to ensure accurate time slice alignment.¶

The module SHOULD support graceful transitions that do not disrupt packets in flight.¶

8.3. Data Forwarding Module

The data forwarding module is responsible for:¶

• Receiving packets from ingress interfaces.¶

• Extracting destination GRCs and performing routing table lookups.¶

• Forwarding packets to the appropriate egress interfaces.¶

• Maintaining packet ordering within flows.¶

The module MUST support the segmented longest match algorithm and SHOULD leverage existing hardware forwarding engines (e.g., TCAMs) where available.¶

8.4. Routing Database

The routing database stores:¶

• Pre-computed routing tables for all time slices in the satellite's orbital period.¶

• Ephemeris data for all satellites in the constellation.¶

• Mapping between GRCs and geographic coordinates.¶

• Terrestrial-to-GRC Multi-Source Mapping Table: Maps a standard terrestrial IP prefix (IPv4/IPv6) to a set of candidate GRCs representing multiple terrestrial injection/egress points (PoPs/GSs).¶

The database is populated prior to satellite launch and MAY be updated via ground control uploads when constellation parameters change.¶

9.1. Border Gateway Function

The GS and PoP serve as the border between the satellite segment (GRC-based routing) and the terrestrial segment (IP prefix-based routing). The border gateway performs the following functions:¶

1. Ingress (Satellite to Terrestrial):¶

   • Terminates satellite tunnel encapsulation.¶

   • Extracts the inner IP packet.¶

   • Performs standard IP routing lookup using the destination IP address.¶

   • Applies NAT if the satellite segment uses private addressing.¶

2. Egress (Terrestrial to Satellite):¶

   • Receives IP packets destined for satellite network users.¶

   • Determines the target UT GRC. If the user network is multi-homed (connected via multiple UTs for multi-source reliability), the gateway selects the optimal UT GRC list based on BGP metrics or geographic policies.¶

   • Selects the ingress GS and encapsulates the packet into a satellite tunnel with GRC-based outer addressing.¶

9.2. DNS and Address Resolution

The DNS resolution process is unchanged from standard IP networks:¶

1. The DEV queries a DNS resolver for the content server's domain name.¶

2. The resolver returns the server's IP address.¶

3. The DEV sends packets to this IP address.¶

4. The UT intercepts the packet and initiates the satellite routing process based on the destination's geographic region.¶

The GRC-based addressing is transparent to end hosts and applications.¶

10.1. Spoofing and Injection

Because GRCs are derived from geographic coordinates rather than administratively assigned prefixes, an attacker could potentially inject false routing information if they gain control of a satellite or GS. Mitigations include:¶

• Cryptographic authentication: Routing table updates and ephemeris data SHOULD be cryptographically signed by the constellation operator.¶

• Access control: Only authorized ground control stations SHOULD be able to modify routing databases.¶

• Anomaly detection: Satellites SHOULD monitor for anomalous routing behavior (e.g., sudden changes in forwarding patterns) and report to ground control.¶

10.2. Routing Database Integrity

The pre-computed routing tables are critical to correct network operation. Compromise of the routing database could cause widespread black holes or loops. Protections include:¶

• Secure storage: Routing databases SHOULD be stored in tamper-resistant hardware on satellites.¶

• Integrity verification: Checksums or digital signatures SHOULD be used to verify routing table integrity at load time.¶

10.3. Privacy Considerations

GRC-based routing encodes geographic information in packet headers. While this does not expose precise user locations (GRCs represent regions, not individual devices), traffic analysis could infer user coarse location. Operators SHOULD consider:¶

• Encryption: IPsec or TLS SHOULD be used to protect user traffic content, though GRC headers remain visible for routing.¶

• Logging minimization: Forwarding devices SHOULD minimize logging of GRC-based forwarding decisions to reduce metadata exposure.¶

12.1. Normative References

[RFC791]

Postel, J., "Internet Protocol", STD 5, RFC 791, DOI 10.17487/RFC0791, September 1981, <https://www.rfc-editor.org/rfc/rfc791>.

[RFC8200]

Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", STD 86, RFC 8200, DOI 10.17487/RFC8200, July 2017, <https://www.rfc-editor.org/rfc/rfc8200>.

[RFC2328]

Moy, J., "OSPF Version 2", STD 54, RFC 2328, DOI 10.17487/RFC2328, April 1998, <https://www.rfc-editor.org/rfc/rfc2328>.

[RFC4271]

Rekhter, Y., Ed., Li, T., Ed., and S. Hares, Ed., "A Border Gateway Protocol 4 (BGP-4)", RFC 4271, DOI 10.17487/RFC4271, January 2006, <https://www.rfc-editor.org/rfc/rfc4271>.

[RFC1195]

Callon, R., "Use of OSI IS-IS for routing in TCP/IP and dual environments", RFC 1195, DOI 10.17487/RFC1195, December 1990, <https://www.rfc-editor.org/rfc/rfc1195>.

[RFC2119]

Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, <https://www.rfc-editor.org/rfc/rfc2119>.

[RFC8174]

Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, May 2017, <https://www.rfc-editor.org/rfc/rfc8174>.

12.2. Informative References

[LEO]

Pan, J Zhao and L Cai, J., "Measuring a Low-Earth-Orbit Satellite Network", 2023, <https://ieeexplore.ieee.org/document/10294034>.

[H3]

Uber Technologies, "H3: Uber's Hexagonal Hierarchical Spatial Index", 2023, <https://h3geo.org/>.