Source Based Time Variant Routing

Abstract

This document describes a source-based time variant routing methodology that can be used in a network with predicted variations. By using source-based time variant routing, the source node uses stable information (e.g. orbit of satellite) to calculate the forwarding path between source and destination nodes. The intermediate node does not need to maintain routing information, such that in case of neighbor variations (restoration, activation, change of quality, or loss), there are no routing information changes. The routing decision is done by the source node. This makes building a highly scalable network with predicted variations possible (e.g. tens of thousands of satellites).¶

1. Introduction

[draft-ietf-tvr-use-cases] describes the use cases of time variant routing. This document describes a source-based time variant routing methodology that can be used in a network with predicted variations. By using source-based time variant routing, the source node uses stable information (e.g. orbit of satellite) to calculate the forwarding path between source and destination nodes. The intermediate node does not need to maintain routing information, such that in case of neighbor variations (restoration, activation, change of quality, or loss), there are no routing information changes. The routing decision is done by the source node. This makes building a highly scalable network with predicted variations possible (e.g. tens of thousands of satellites).¶

2. Specification of Requirements

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT","SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119].¶

3. Terminology

LEO: Low Earth Orbit with the altitude from 180 km to 2000 km.¶

VLEO: Very Low Earth Orbit with the altitude below 450 km.¶

GEO: Geosynchronous orbit with the altitude 35786 km.¶

ISL: Inter Satellite Link.¶

TN: Terrestrial Network; refers to networks providing connectivity through communication lines that travel on, near, and/or below ground.¶

UT: User Terminal. Usually known as a dish. Using cellphone as a user terminal will be described in a separate document.¶

UTID: A permanent ID uniquely identifies a UT. UTID is globally unique over the world.¶

UTTID: User Terminal Temporary ID.¶

GS: Ground Station, a device on the ground connecting the satellite and also connecting to TN.¶

GSID: A permanent ID uniquely identifies a GS. GSID is globally unique over the world.¶

SL: Satellite Link. Link between UT and satellite or link between GS and satellite.¶

FP: Forwarding path built via source based routing between UT, satellites and GS. A FP is calculated by UT via source-based routing algorithm. GS maintains a reversed FP used for reversed traffic from GS to UT.¶

SGDB: Satellite and GS database. Each satellite has a unique identifier (ID). SGDB maintains a database containing information of each satellite, including but not limited:¶

• Inclination (i)¶

• Longitude of the ascending node (Omega)¶

• Eccentricity (e)¶

• Semimajor axis (a)¶

• Argument of periapsis (omega)¶

• True anomaly (nu)¶

• Number and direction of the lasers (for ISL communication)¶

SGDB also maintains the information of each GS:¶

• The position (longitude, latitude) of ground station (the site connecting to PoP providing internet access).¶

SGDB does not maintain the position of UT(s).¶

To be clear, these information looks a lot, but these information is quite stable, and does not change due to the movement of the satellites.¶

For a given time T, the position (longitude, latitude, height) of any satellite is known based on the SGDB. Also the number of ISLs of a satellite is known, the adjacency(adjacencies) of a satellite can be determined and the bandwidth of the ISL(s) can be calculated.¶

4. Basic Logic of Source Based Time Variant Routing

One important character of source based time variant routing described in this document is that the routing decision is determined by the source node on the ground (user terminal or ground station), instead of on the satellite. The SGDB does not maintain any MAC and routing tables from users. The decision is made based on SGDB which is a stable database.¶

There are pre-conditions below to allow source based time variant routing algorithm work:¶

• It is required that UT and GS have SGDB. The method of synchronizing SGDB is described in section TBD.¶

• It is required that UT and GS are time synchronized. Detailed considerations on time synchronization is described in section TBD.¶

• It is required that UT, GS know their location(longitude, latitude).¶

                T=T0

                    +-+-+-+     +-+-+-+   +-+-+-+
                    |  C  |~~~~~|  D  |~~~|  F  |
                    +-+-+-+     +-+-+-+   +-+-+-+
                      ~     ~
                     ~      ~
+-+-+-+       +-+-+-+      +-+-+-+
|  E  |~~~~~~~|  A  |~~~~~~|  B  |
+-+-+-+       +-+-+-+      +-+-+-+
               *            *
               *             *
               *              *
            +-+-+-+          +-+-+-+   +-+-+-+
            | UT  |          | GS  |===| PoP |
            +-+-+-+          +-+-+-+   +-+-+-+

*** Satellite link
~~~ ISL (Inter Satellite Link)
=== Link on the ground (e.g. fiber)

Figure 1: Topology at time T0

              T=T0+T'

            +-+-+-+   +-+-+-+     +-+-+-+
            |  C  |~~~|  D  |~~~~~|  F  |
            +-+-+-+   +-+-+-+     +-+-+-+
                      ~     ~
                     ~      ~
+-+-+-+       +-+-+-+      +-+-+-+     +-+-+-+
|  G  |~~~~~~~|  E  |      |  A  |~~~~~|  B  |
+-+-+-+       +-+-+-+      +-+-+-+     +-+-+-+
                 *            *
                 *             *
                 *              *
             +-+-+-+          +-+-+-+   +-+-+-+
             | UT  |          | GS  |===| PoP |
             +-+-+-+          +-+-+-+   +-+-+-+

*** Satellite link
~~~ ISL (Inter Satellite Link)
=== Link on the ground (e.g. fiber)

Figure 2: Topology at time T=T0+T'

Figure 1 shows a basic topology diagram of satellite constellations used to explain the terminology of source-based time variant routing.¶

Let's assume that UT knows its location (Xu, Yu) and the location of the nearest GS (Xg, Yg). UT and GS also know the orbit of the satellites from SGDB. The detailed method of getting this information is described in section 4.¶

With this information, given a time T=T0, it is not difficult for UT to calculate the shortest path towards GS using the Dijkstra algorithm (or similar ones). Considering a GS can have many UT connected, to minimize the load of GS, GS will maintain a reversed And vice versa from GS to UT, But this is not necessary considering this will bring a significant load on the GS, as a GS can have many UT connected. This is described below.¶

For the topology in Figure 1, at time T0, the best path to the nearest GS is UT->A->B->GS.¶

The source node UT encapsulates the entire path containing the source, destination, and a list of IDs of the satellites and the nearest GS, with a pointer toward the ID of the satellite which should process the packet (in the left diagram of Figure 1, UT encapsulates path list {[UTID,(A, B), GSID], current=A}, and points towards A), in front of the original packet.¶

When A receives the packet, it first checks if the satellite ID (the pointer points to) is equal to the ID itself. If yes, A checks if the next ID is in the adjacency table. If yes, move the pointer to the next ID and forward the packet to the corresponding ISL. So A forwards the packet towards B and moves the pointer pointing to B, the packet becomes {[UTID,(A, B), GSID], current=B}.¶

After B receives the packet, if the validations pass (same as the process of A described above), it forwards the packet towards GS via SL (air interface) and moves the pointer to the next, without removing the header. So the packet becomes {[UTID,(A,B),GSID], current=GSID}.¶

After GS receives the packet, it values GSID equal to the ID of itself. If yes, it records a reversed path, which sends traffic back to UT. The reversed path from GS back to UT is {[GSID,(B, A), UTID], current=GSID}. GS can either reply to UT using this path for protocol packets (e.g. UT authentication, IP allocation, etc.) or send the data packet to PoP. For the data packet back from PoP, GS can use the binding relationship between the IP address of the UT allocated by GS and FP, and send traffic to UT based on the destination IP of the packet. GS located the IP address to UT and built a binding relationship between the IP and the FP.¶

After the process above, the UT and GS build a bi-directional path over the SL and ISL. The path is stateless, which means the satellites do not need to maintain the status of the path.¶

As the satellites keep moving, after time T', the satellites covering the UT and GS change to E, D, and A as shown in the right diagram in Figure 1. The UT recalculates the path towards the closest GS, based on the SGDB and time T=T0+T', and the new path is UT->E->D->A->GS. The UT sends a path with a notification message to GS with the new path information, GS updates the binding relation between the IP of UT and FP, sends an acknowledge message back to UT, and switches the FP towards UT to the new path. After UT receives the acknowledge message, it switches the FP to the new path.¶

5. Maintaining and Synchronizing SGDB

6. User Terminal Registration

7. Network Topology Changes Considerations

                #             ^
                   #       ^
                     #  ^
      +-+-+-+  +-+-+^  #           +-+-+-+
      |  A  |**| UT|     #         |  B  |
      +-+-+-+  +-+-+^   #          +-+-+-+
                      #
                     # ^
                   #     ^
                #           ^


   #### coverage of satellite A
   ^^^^ coverage of satellite B
   **** satellite link between satellite and UT

Figure 3: UT Considerations on Satellite Coverage

8. Load Balancing Considerations

Due to ISLs are established in nearly vacuo space, the bandwidth of ISLs can reach much much higher bandwidth than SLs. So in most of the cases, ISL won't get full.¶

But still in some cases, one of the ISL MAY be used together by couple of other satellites as an intermediate node. Let's assume A,B,C and D have ISLs based in Figure 5. Traffic from UT connecting to A can have two paths towards the GS connecting to D, which are A-C-D and A-B-D. But UT connecting to B MAY also uses ISL B-D. This may lead to ISL B-D becomes overloaded.¶

This can be addressed in several ways:¶

• When a source UT have multiple ECMP towards (the number of paths=M) a destination GS, it sorts the path in ascending order based on satellite ID of each hop, then generates a random number N with a seed (the seed CAN use the permanent UTID). Then UT choose the Ith path (I=N%M).¶

• Quality of service mechanism SHOULD be introduced to ensure critical control packets are not lost and important service is not impacted.¶

• When an ISL utilization reaches a threshold, a satellite MAY randomly pick part of the best effort packets and generate FP switch notifications towards UT. UT recalculates the path without the corresponding link. The FP switch process is the same with the process described in section 7.1.¶

            +-+-+      +-+-+
            | A |~~~~~~| B |
            +-+-+      +-+-+
              ~          ~
              ~          ~
              ~          ~
            +-+-+      +-+-+
            | C |~~~~~~| D |
            +-+-+      +-+-+

      ~~~ ISL (Inter Satellite Link)

      Figure 5: Load Balancing between ISLs

9. Service Scenarios

10. Comparison with Existing Researches and Solutions

11. Security Considerations

TBD¶

12. IANA Considerations

This document does not make any requests from IANA.¶

13. References