# Multi-Protocol Location Forwarding (MPLF) for Space Routing

Xiangtong Wang, Zhiyun Jiang, Menglong Yang, Songchen Han, and Wei Li  Wei Li
was with the School of Aeronautics and Astronautics, Sichuan University,
Chengdu, China, e-mail: (see li.wei@scu.edu.cn).

###### Abstract

The structure and routing architecture design is critical for achieving low
latency and high capacity in future LEO space networks (SNs). Existing studies
mainly focus on topologies of space networks, but there is a lack of analysis
on constellation structures, which can greatly affect network performance. In
addition, some routing architectures are designed for networks with a small
number of network nodes such as Iridium while they introduce significant
network overhead for high-density networks (i.e., mega-constellation networks
containing thousands of satellites). In this paper, we conduct the
quantitatively study on the design of network structure and routing
architecture in space. The high density, high dynamics, and large scale nature
of emerging Space Networks (SNs) pose significant challenges, such as unstable
routing paths, low network reachability, high latency, and large jitter. To
alleviate the above challenges, we design the structure of space network to
maximum the connectivity through wisely adjusting the inter-plane inter
satellite link. we further propose Multi-Protocol Location Forwarding (MPLF),
a distributed routing architecture, targeting at minimizing the propagation
latency with a distributed, convergence-free routing paradigm, while keeping
routing stable and maximum the path diversity.

Comprehensive experiments are conducted on a customized platform Space
Networking Kits (SNK) which demonstrate that our solution can outperform
existing related schemes by about 14% reduction of propagation latency and 66%
reduction of hops-count on average, while sustaining a high path diversity
with only $O(1)$ time complexity.

###### Index Terms:

Space networks, Networking structure design, Multi-Protocol Location
Forwarding, Routing Scheme.

##  I Introduction

Low Earth orbit (LEO) mega-constellations, comprising thousands of satellites,
have been proposed to offer global broadband service and have attracted much
attention in recent years. “NewSpace” companies plan to launch mega-
constellations of hundreds to thousands of communication satellites into LEO
in the coming years. Their proposals have already received the first stage of
regulatory approval: SpaceX[1, 2], OneWeb[3], and Telesat[4] have obtained RF
spectrum from the FCC for their constellations.

Fig.1 shows the quintessential scenarios and use cases of future Space Network
(SN). Such system could have a deep and lasting impact on the current Internet
by extending its coverage to under-served communities, and providing lower
latency over longer distances than present-day fiber. The SN could potentially
serve as a core network and integrate into current terrestrial networks (TNs),
and supporting the data transmission from functional satellite such as remote
sensing satellite, weather observation satellites, etc.

Figure 1: Space Network Architecture.

However, realizing the full potential of these systems requires addressing new
challenges posed by high-density large-scale and highly dynamics in the
network, which bring a significant obstacle for datagram forwarding at the
network layer. Network layer protocols in TNs such as IP and ATM have a basic
premise: datagrams can be forwarded according to statically addressed nodes
for end-to-end reachability. Even in wireless sensor networks (WSNs) such as
Ad Hoc, nodes move around each other but still maintain a static topology,
generating significant overhead to update the network information in each
node[5, 6], which is difficult to apply in SNs due to their density and scale.
More importantly, there are significant obstacles for addressing these
challenges: the lack of network analysis tools that incorporate the dynamic
behavior of LEO SNs[7]. This creates a substantial risk that research in this
area may not keep peace with the rapid advances being made in the industry.

To address the above challenges, we explore how different configurations can
affect the structure of the SN. Based on the analysis, we propose the Multi-
Protocol Location Forwarding (MPLF) architecture which employs a geographic
based forwarding policy to enable end-to-end transmission between arbitrary
terminals worldwide in a distributed and convergence-free manner over a dense
constellation network. Considering the unique dynamics of LEO SN, we developed
a flexible and scalable simulator SNK with the goal of quickly designing
constellations and its network structure, obtaining reliable node information
in dynamic networks, and visualizing routing paths.

Comprehensive experiments under Ground-Stations and Mobile Stations (MS) in
various constellations conducted on SNK to verify the effectiveness of MPLF.
The results of experiments shows that compared with the other related
algorithms, MPLF can significantly improve the overall network performance, by
reducing about 14% average propagation latency, 60% jitter in maximum and 66%
average hops.

This paper is organized as follows. Section II first provides a short overview
about LEO/MEO satellite systems and ISL topology characteristics. We formulate
the SN model for simple description in SectionIII. In Section IV, the detailed
analysis is given to explore how different configurations affect the structure
of the SN. The heart of the paper is then formed by Section V providing a
detailed presentation of a new dynamic routing architecture MPLF for
overcoming end-to-end problem in a density and dynamic SN. In Section
refsec:exp, we present the performance analysis of MPLF and in Section VII we
conclude the paper.

##  II Background and Related Works

###  II-A Constellation and Networking Structure Design

With the advent of multi-satellite systems, i.e., constellations, the
traditional orbit design principles focused on a single satellite need to be
extended to consider the performance of the entire constellation. Some
constellations [8, 2, 9, 4] have implemented inter-satellite link (ISL) for
inter-satellite information transfer, at which point the system can be
abstracted as a network system, in which the design of space network structure
must take into account the motion and traffic characteristics between
satellite nodes in the system.

Satellite link establishment does not necessarily follow the principle of
closest proximity, and some researchers have studied the constellation
topology design, also called Link Assignment, which abstracts the FSA with a
finite state machine and uses an optimization method to dynamically adjust the
link establishment between satellites according to the load situation [10,
11], and the link can be established by satellites within any satellite visual
range (LoS). Bhattacherjee [12] ignored the nearest neighbor principle and
proposed a topology design method for the giant constellation network and
abstracted it as an integer linear programming problem, using moduli units to
reduce the problem complexity for optimization. They also introduce several
connectivity metrics for network evaluation. Although not using the nearest
neighbor principle can effectively increase the network throughput and reduce
the average hop count of flows, etc., it is more like an extension of the
study that mimics the network topology design in highly controllable DCNs [13,
14] and lacks practicality, especially in highly uncontrollable environments
in space where it is difficult to apply practically. because it would present
additional technical hurdles that are difficult to overcome. For example, the
network overhead of link dynamic adjustment, which can be extremely burdensome
when the constellation size rises, and is therefore only suitable for use in
constellations with a small number of satellites and interstellar information
transmission such as GNSS systems [15].

Although some constellations have planned to implement satellite Internet
without using ISL [3], to achieve relay transmission in the form of Bent-pipe
and ground stations, but it is difficult to achieve the performance of ISL
system in terms of time delay, throughput, and robustness [16]. Therefore,
establishing persistent links between neighboring satellites within and
between orbits, respectively, is a more practical approach. The persistent
links need to consider the link construction pattern, which generally allows
each satellite to establish persistent links with four or six adjacent
satellites in a nearest neighbor manner, forming a local topology of Manhattan
(+Grid) or triangular Manhattan pattern (*Gird)[17]. However, few works focus
on the network structure affected by the configuration of constellation,
specifically each satellite is connected to the neighboring satellites, but
without considering which phase is connected. The topology of space networks
built on the Manhattan or triangular Manhattan pattern is relatively simple,
but in the Walker configuration constellation there is a ’seam’ phenomenon,
which leads the ’last hop’ ambiguity of some geographic information routing
algorithms appear dead-end problem [18, 19].

The structure of space network constructed based on the Manhattan or
triangular Manhattan pattern is relatively simple, but there are ”seams” in
the Walker constellation, leading to dead-end problems in the ”last-hop”
ambiguity of some geographical routing algorithms [18, 19], which we will
discuss in Section V-E.

###  II-B Routing in Space Networks

Routing schemes have various criteria [20] and can be categorized by:
Centralized and decentralized according to the computational entity;
connection-oriented type and connectionless according to whether or not to
establish a state before data routing; Topology-based or position-based
routing according to whether or not to apply a location service; Load-
sensitive and load-sluggish according to load feedback; static or dynamic
according to the route change cycle.

Early satellite network services, such as Iridium [8], started with
connection-oriented services, where packets between arbitrary source and
destination nodes were forwarded along the same path, while connectionless
forwarding was forwarded along different paths over time. [21, 22] proposes
QoS-guaranteed routing methods for ATM networks, and provides shortest paths
for ISL topologies abstracted as mesh networks. A similar connection-oriented
routing technique is MPLS, a widely used in ISP networks. [23] proposes MPLS
for satellite networks using the architecture of Celestri[24] as the network
topology, and explores the possibility of its use in satellite networks. The
connection-oriented routing approach is only suitable for networks with few
nodes, and providing centralized computation for networks with many nodes will
have a significant routing overhead and therefore is not ideal for large-scale
constellations.

To cope with the non-adaptability of centralized computational routing in
satellite networks, some efforts[25, 26] have designed a distributed,
connectionless routing algorithm with an Iridium-like constellation as the
topology that can provide a path with a minimum propagation delay. Its
algorithm abstracts the constellation topology as a two-dimensional mesh
network, discretizes geographic addresses into logical addresses assigned to
each satellite, and generates optimal forwarding paths hop-by-hop based on the
relative distance from each node to its destination.

To overcome the dynamic nature of the network, some have proposed to achieve
logical network statics through virtual nodes or virtual topologies[11, 27,
28]. This approach exploits the constellation topology’s predictability,
discretizes the dynamic topology according to the time slice, and assumes that
the topology is constant within a specific time slice, thus generating routes
using methods such as Dijkstra. Such methods shorten the adequate time of the
static topology when the constellation size is large, thus requiring frequent
updates of the topology, resulting in high overhead and not being suitable for
large-scale constellations.

The virtual node approach[21, 25, 29, 30] divides the geographical location
into several cells, called virtual nodes, and assigns a fixed logical address
to establish a mapping with the overhead coverage satellites. When the
satellites cover the cell change, the following satellite inherits the logical
address and network states, such as the routing table and other information of
the previous satellite, maintaining the logical invariance although the
physical entity has already changed. However, a large amount of bandwidth is
required to exchange this information. The overhead is extremely high if each
satellite caches a large routing table for the rest of the satellites in a
large-scale network.

Geographic routing (also called georouting or position-based routing) is a
routing principle that relies on geographic position information [31, 32, 33]
and have been widely used in WSNs. Greedy forwarding and face routing are two
of the earliest geographic routing strategies and have together formed the
basis of numerous subsequent approaches. In greedy forwarding, there are
different strategies a node can use to decide to which neighbor a given packet
should forwarded such as MFR (most forward within r) [34], NFP (nearest with
forward progress) [35], compass routing [36], RN (random nearest) [37]. Face
routing is derived from Compass Routing II where faces on a planar graph are
traversed using a technique known as the ’right hand rule’ (sometimes left
hand rule instead) in which the algorithm keeps track of all the times it
crosses the line connecting the source to destination[38, 39]. The main
advantage of face routing is that compared with greedy forwarding, it
guarantees delivery but with inefficiency caused by detours, which is not
negligible in SNs due to its large scale. The first geographical routing
scheme that applied into LEO SNs is introduced by [18], which pose a last-hop
ambiguity. Thus, a mobility management scheme[40, 19] that focuses on solving
the last-hop ambiguity of geographical routing schemes has been proposed.

###  II-C Sim/Emulation Platforms

Due to the characteristics of large scale, high dynamics, and a large number
of nodes of space networks, the existing simulation platform cannot meet our
current simulation demands on space networking. The ideal space network
simulation platform needs to integrate three core functions: 1)space dynamics
simulation and visualization, 2) network simulation 3) The high-performance
connection scheme between them.

Many network simulators, including OPNET, NS2/NS3, Mininet, etc., and space
simulators, including STK, MATLAB, SaVi, GMAT, etc., are considered for the
development of space network simulation platforms, and the key technology is
the organic combination of the two, i.e., to enable efficient interaction
between the two platforms with scalability and flexibility.

[41] developed a satellite networking visualization platform through Unity 3D,
which provides impressive visualization effects and can visualize the path
evolution and end-to-end routing delay. However, the packet-level network
simulation is still unachievable due to the lacking of support in network
simulation. [7] build a simulation platform Hypatia by combing NS3 and Cesium.
It is the first to use Cesium to achieve visualization on the Web side with
high flexibility. NS3 also supports virtual networks built by users to perform
packet-level simulations. Although the webside in Hypatia is underdeveloped
and the component interaction is weak, it still provides a good idea. On the
other hand, [42] combines the powerful network simulator mininet with STK,
which has obvious superiority in satellite simulation, and proposes the
StarPerf simulation platform and uses STK/Connect as a middleware to connect
them. However, the limited expandability in STK leads to the visualization
side lacking flexibility in showing customized entities such as ISLs.

Although some space network simulators have been proposed, there is still a
lack of unified platforms that can fully implement packet-level measurements
and powerful visualization of space networks. The visualization platforms that
present packet processes like ONOS[43] are of great value for future network
development to understand existing phenomena.

##  III Space Network Model

Definition 1: To tackle the temporal variations in the SN, we denote an
ordered time set as $\mathcal{T}=\\{t_{1},t_{2},\cdots\\}$ The elements of the
set $\mathcal{T}$ are called time stamps, where $t_{i}\leq t_{i+1}$. The
network topology that without tISLs can be considered unchanged between
adjacent time stamps. $t_{i+1}-t_{i}$ represents the minimum time granularity
of scenario change, and the time granularity with each element represent one
second of time can be simply described as a time set
$\mathcal{T}=\\{1,2,T\\}$.

Definition 2: The network topology at each time stamp $t\in\mathcal{T}$ can be
formulated as an undirected graph
$\mathcal{G}^{t}=(\mathcal{V},\mathcal{E}^{t})$, where $\mathcal{V}$ is the
set of network nodes and $\mathcal{E}^{t}$ is the set of active communication
links.

Specifically, assume $\mathcal{V}$ is the set of all network nodes such that
$\mathcal{V}=\mathcal{V}_{S}\cup\mathcal{V}_{G}\cup\mathcal{V}_{M}$ where
$\mathcal{V}_{S}=\\{s_{1},\cdots,s_{i},\cdots,s_{\mathcal{N}_{S}}\\}$ ,
$\mathcal{V}_{G}=\\{g_{1},\cdots,g_{i},\cdots,g_{\mathcal{N}_{G}}\\}$ and
$\mathcal{V}_{M}=\\{m_{1},\cdots,m_{i},\cdots,m_{\mathcal{N}_{M}}\\}$
represent the node sets of satellites, Ground stations (GSes) and Mobile
Terminals (MTs) respectively. Similarly, $\mathcal{E}^{t}$ is the set of all
types of links in the network and composed by Inter-Satellite Links (ISL),
Groundstation Satellite Links (GSL) and Mobile terminal Satellite Links (MSL)
which denoted as $\mathcal{E}^{t}=\mathcal{E}^{t}_{S\leftrightarrow
S}\cup\mathcal{E}^{t}_{S\leftrightarrow
G}\cup\mathcal{E}^{t}_{S\leftrightarrow M}$. We also describe all vertexes and
edges that adjacent to $v$ at time $t$ as $\mathcal{V}_{adj}^{t}(v)$ and
$\mathcal{E}_{adj}^{t}(v)$ respectively.

Definition 3: If the costs of GSLs $\mathcal{E}^{t}_{S\leftrightarrow G}$ are
not considered, Paths between vertexes
$\\{g_{s},g_{d}\\}\subset\mathcal{V}_{G}$ at each time stamp $t\in\mathcal{T}$
can be formulated as a set $\mathcal{P}^{t}_{g_{s}\rightarrow
g_{d}}=\\{p_{1},\cdots,p_{i},\cdots,p_{\mathcal{N}_{P}}\\}$, where the each
elements represents a oriented link set
$p=\\{\mathbf{e}_{1},\cdots,\mathbf{e}_{i},\cdots,\mathbf{e}_{\mathcal{N}_{p}}\\}$.

Definition 4: As described in Walker[44], the constellation is generally
described as $T/P/F$ where $T$ is the total number of satellites; $P$ is the
number of equally spaced planes, and $F$ is the relative spacing between
satellites in adjacent planes. The change for satellites in neighboring planes
equals $F\times 360/T$. The value range of the phase factor is $F\in[0,P-1]$.
At $F=F_{m}$, the phase difference between satellites in two adjacent orbits
achieves maximum where:

$F_{m}=\left\\{\begin{aligned} P/2-1&,&\text{P~{}is~{}even.}\\\
(P-1)/2&,&\text{P~{}is~{}odd.}\end{aligned}\right.$ (1)

Note that the constellation formulates the same architecture as $F=0$ and
$F=P$. In this paper we use $N/P/F$ to illustrate a constellation where the
$N$ is the number of satellites per orbit.

We also introduce the bias set $\mathcal{B}$ of inter-orbit link to describe
the structure of constellation, and it will be detailed discuss in IV-A.

##  IV Structure Design and analysis in space Network

TABLE I: Types of Link in space network.

Types of Link | Connected Entities | Dynamic | At Edge
---|---|---|---
Inter Satellite Link (ISL) |  Persistent ISL |  | intra-orbit ISL
---
(iISL)
adjacent satellites in same orbit |  |
| Inter-orbit ISL
---
(sISL)
satellites in adjacent orbits |  |
Temporary ISL |  | Encounter ISL
---
(eISL)
satellites in crossed orbits |  |
| Inter-shell ISL
---
(oISL)
satellites in adjacent shells |  |
Ground station satellite link (GSL) | NGEO satellite and ground station |  |
GEO satellite and ground station |  |
Mobile station satellite link (MSL) | satellite and mobile station |  |

The structure of satellite networks are more like a hybrid structure of the
mesh, ring and tree topology, which is significantly different from
terrestrial networks and inseparable from routing scheme design. In this
section, we introduce all the types of links that make up a satellite network,
which shown in Tab.I.

###  IV-A Inter Satellite Links (ISLs)

Intra-orbit Links (iISL). Without taking orbital perturbations into account,
each satellite follows the same direction and velocity in the same orbit
(plane). If a satellite establishes a link only with a neighbor satellite in
the same orbit the topology can be considered invariant, as this is the only
case of intra-orbit link in this paper.

Inter-orbit links (side links, sISL). Inter orbit links, i.e., the side links,
refer to links that are established between two satellites in the same
direction of movement but in adjacent orbits. Due to the relative homogeneity
of iISL, sISLs are the main reason affecting the overall topology of the
network. The main factors affecting the construction of sISL include:

  * •

The constellation phase factor $F$.

  * •

Number of sISL per satellite.

  * •

Which satellites in adjacent orbits establish sISL with.

Figure 2: The patterns of iISL (blue) and sISL (green) in +Grid (left two) and
*Grid (right two).

Fig.2 shows four typical patterns of sISL building. A satellite can build sISL
with another in adjacent orbit with 0 bias($\mathcal{B}=\\{0\\}$), -1 bias
($\mathcal{B}=\\{-1\\}$) or both ($\mathcal{B}=\\{-1,0\\}$). Generally, we
denote the pattern of 4 ISLs per satellites as +Grid [12] and 6 ISLs per
satellite as *Grid. The inter-orbit satellite link is generally a link
established between the current satellite and a neighboring satellite in
adjacent orbit. Note that there is another case where the link is a radom
encounter between two satellites, which we call a encounter ISL (eISL).

Figure 3: Inter Satellite Links

For most LEO SNs, iISLs already provide sufficient SW-NE connectivity, while
East-West connectivity and North-South connectivity require careful
construction of sISLs. Fig.3 shows a constellation with the size $N=40,P=40$
and various configuration where all iISLs (left cyan line) are identical, but
sISLs (right green line) vary dramatically. It can be seen that the more
uniform the connectivity of the constellation in all directions, the better
performance of networking overall if the user demand is evenly distributed
globally.

Encounter ISL (eISL). The networks generated from the above ISLs provide a
mesh topology, but they are two different meshes in any one region. - One
usually moves to the northeast (NE) and the other southeast (SE), also known
as the ’seam’[18], making it possible to establish a persistent ISL. There is
no doubt that the link between them can provide the network great connectivity
boost which we called as Encounter ISL (eISL).

Figure 4: Encounter ISL (Black and white) between NE direction and SE
direction satellites.

The relative speed between the two satellites in eISL is high, about 5 to 12
km/s. It is unclear for a satellite when, with which satellite, and for how
long the link will be established. Fig.5 (a) plots the number of eISLs and
Fig.5 (b) shows the duration of tISLs between two encountering satellites in
orthogonal orbits under the constellation of 20/20/0, where $L_{h}$ is the
distance threshold at which encountering satellites start to building eISL. We
observed that over 80% eISLs lasted less than 200s and the number of eISL
increases significantly with increasing $L_{h}$.

(a) Duration of eISLs.

(b) Num. of eISLs

Figure 5: eISL between two orthogonal satellites.

Inter-shell links (oISLs) Satellite networks can achieve full-time global
coverage by building multi-layer (shell) constellations. Different orbital
height lead to different rotational velocities of satellites relative to the
Earth between different shells, which makes it difficult to establish a
persistent ISL between different shells. However, the closer the height of
orbit and the closer the velocities, the longer it takes to establish
temporary links between satellites in adjacent shells. Thus, although
increasing the cost, stability can be effectively improved by increasing the
number of shells, such as the strategy of using GEO as a controller in some
SDN-based satellite networks [45].

Due to the complexity of the problem, eISL and oISL are not introduced in the
latter part.

###  IV-B Edge Links

Edge links, including Ground station Satellite Links (GSLs) and Mobile Station
Satellite Links (MSLs), are generally the links that connects forwarding
satellites and earth or mobile stations, which are difficult to establish
persistent links due to the high dynamics between satellites and station
nodes. The construction of the edge link is generally determined by the
handover policy, in which the Ground Station (GS) dynamically selects the
appropriate adjacent satellite among the coverage satellites, including
maximum elevation angle (MEA), maximum service time (MST) or one-way
latency[46]. However, it is simpler and more efficient to link all satellites
together, which is the approach we take in this paper. Since the coverage
satellites can be considered as two mesh networks with overlapping but large
topological distances, with a so-called ’seam’ between them (V-E), the GS
should be connected to at least one of each SE and NE satellite for better
connectivity in the absence of eISL.

###  IV-C Connectivity Analysis

The phase factor $F$ and the bias set $\mathcal{B}$ have an important impact
on the construction of the sISLs, They affect the pattern of each satellite
ISL and thus determine the global structure of the network, which can lead to
ISLs with different directional distributions.

From Fig.2 we already know that, the sISLs in $F=0,\mathcal{B}=\\{0\\}$
pattern are parallel to the equator, which is called Horizontal Ring[25], and
it effectively increases the connectivity of the network in the East-West
direction[41]. In fact, directional connectivity reflects the distribution of
ISLs over different directions, i.e., the better the connectivity in a certain
direction, the higher the proportion of ISLs in that angle, which will reduce
the path zigzag in that direction and thus reduce the propagation latency.

In order to describe the directional connectivity of the constellation under
different configurations, we define the $\alpha$ as the angle between the ISL
and Equator plane as:

$\displaystyle\alpha=\frac{\pi}{2}-\arccos{(\frac{\mathbf{e}\cdot\mathbf{e}_{z}}{\|\mathbf{e}\|\cdot\|\mathbf{e}_{z}\|})}$
(2)

where the $e_{z}$ is the normal vector of Equator plane, i.e., the rotation
axis of Earth. We count the probability density function $h(\alpha)$ during
time $\mathcal{T}$ as follows, which is shown in Fig.6 at a polar
coordination.

$\displaystyle
h^{\mathcal{T}}(\alpha)=\frac{\sum\limits_{\mathcal{T}}h^{t}(\alpha)}{\|\mathcal{T}\|}$
(3)

Figure 6: $h(\alpha)$ in constellations with +Grid (a) and *Grid (b).

We observe that iISL consists of orbits with $53^{\circ}$ inclination,
providing sufficient SW-NE and NW-SE connectivity in all patterns. However,
only the sISL in $F=0,\mathcal{B}=\\{-1,0\\}$ (solid blue line) provides
additional ISL at an inclination of about $63^{\circ}$, which improves the
North-South connectivity and thus reduces the zigzag connectivity, compared to
the other patterns.

##  V Routing architecture in space

In this section, we bring the concepts of the Multi-protocol Label Switching
(MPLS) [47] based network routing scheme and its expansion on the satellite
network.

In addition, we often refer to some interrelated concepts in routing[48, 20,
49] such as Switching and Forwarding, indicating the action to take when a
packet arrives. The former represents querying the packet egress port by
standard matching and sending the data, while the latter means getting the
packet egress port by fuzzy matching, i.e., there is a calculation step before
sending the data. Therefore, we use forwarding instead of switching in this
paper.

###  V-A MPLS Concepts for NGSO Constellation Networking

The basic idea of MPLS is very simple: at the ingress point of an MPLS
network, the ingress label edge router (LER), packets are classified according
to the information carried in the packet (e.g., source/destination address,
class of service, etc. ) or network-related information (e.g., ingress port),
or a combination of them. A group of packets processed in the same way is
called a Forwarding Equivalence Class (FEC). It is also possible to bundle a
group of FECs and use a label for that union. This process is called
aggregation. Then, a unique locally valid fixed-length label is selected for
packets belonging to a particular FEC and attached to each packet. A
subsequent Label Switching Router (LSR) examines the packet’s label, replaces
it with the new label already specified, and forwards the packet to the next
LSR based on the information stored in the table until it reaches the egress
point of the network (egress LER) . The unidirectional path of packets through
the MPLS domain is called the Label Switched Path (LSP).

MPLS has been proposed for geostationary orbit (GEO) systems with multiple
point beams, primarily as a way to simplify the complexity of on-board
switching [50]. However in LEO satellite network systems, functional elements
of MPLS, such as ingress LERs, egress LERs, or LSRs, must be mapped to
physical entities of the space network, such as satellites or GSes[23].
Routing and rerouting of paths is of key interest because it affects the
routing computation workload and routing performance. Therefore, the
connection-oriented routing approach also faces many challenges in the highly
dynamic topology between labeled edge routers (GSes) and labeled switching
routers (Satellites), where the label distribution protocol (LPD) is affected.
This is the motivation for us to proposed connectionless Multi-Protocol
Location Forwarding method.

###  V-B Multi-Protocol Location Forwarding (MPLF) Architecture

(a) MPLF between the data link layer and network layer.

(b) Illustration of MPLF.

Figure 7: MPLF architecture.

When two hosts communicate through the space network via LERs, datagrams pass
through different satellite groups due to the changing location of the
forwarding satellites, which poses a challenge to static network addresses.
Based on the concept of MPLS, we propose a connectionless routing architecture
called Multiprotocol Location Forwarding (MPLF), which lies between the
network and link layers (see Fig.7 (a)) and uses a distributed datagram
forwarding method to compute the next hop using satellite location and port
direction information. Some of the definitions in MPLF are as follows.

  * •

Location Forwarding Router (LFR). The satellite in the network could be
considered as LFR and it forward the packets according to information in
packet’s header and self-location to the next LFR, until the egress point
(egress LER) is reached.

  * •

Location Edge Router (LER). The ground station (GS) and mobile station (MS)
both could be considered as LER, which to encapsulate high-level packets with
constructed header and send them to associated satellites. Besides, the LER
needs to convert the address of the data, which we will describe in
SectionV-D.

  * •

Edge Location Server (ELS). LER can not store too large location tables in
local due to the limited storage resources, so an ELS similar to Domain Name
Server (DNS) can be built and connected with a terrestrial network, making it
possible to query ELS through the terrestrial network to get the location of
the destination LER when the local location table cannot be queried.

  * •

Equipment Identifier (EI). An identifier that uniquely represents the device.

We equivalently use LFR and switch satellite to describe the same entities,
and similarly for LER and MT or LER and GS. To achieve MPLF, we assume that
each satellite that we consider a Location Forwarding Router (LFR) must know
and can update the position of itself and the adjacent satellite that exists
in ISL in real-time, which is easy to achieve relying on existing GNSS or LEO
GNSS [51]. The MPLF procedure that transmit IP packet from T1 to T2 is
depicted in Fig.7(b), which as follows.

  * 1)

T1 first sends an IP packet with destination T2 to source LER (i.e.,the
ingress LER) $g_{s}$.

  * 2)

Source LER $g_{s}$ queries the Equipment Identifier (EI) and space address
(sAddr, Cartesian coordination format) of destination LER (i.e., the egress
LER) $g_{d}$ by location table, packet the MPLF header with IP datagram, and
send it to associated LFR $s_{i}$.

  * 3)

The LFR $s_{i}$ receives the packet, takes out the EI from the MPLF header,
queries the association table.

  * 4)

If the EI does not exist in the association table, LFR calculates the port of
next hop based on forwarding strategies .

  * 5)

If EI exist in the association table, sends the datagram to the destination
LER via corresponding channel.

  * 6)

If the calculated next hop is the last hop, then drop the datagram for
achieving loop-free.

After the destination LER $g_{d}$ receives the datagram, it save the source
coordination $\mathbf{x}(g_{s})$ with the UTC time stamp to the local Location
Table for updating. MPLF does not require the implementation of complex label
distribution protocols like RSVP-TE[52] or CR-LDP [53] at LERs, its only
package the source and destination address to the datagram with coordination
conversion. It is a connectionless routing method, and there is another
calculation step before the general ’match-action’ paradigm. In summary, the
MPLF architecture has the following features and advantages:

  * •

Convergence-free. Only the current FLR location and destination location are
considered for each forwarding, and no forwarding table exists or needs to be
updated.

  * •

Mobility management is not required. Since there is no forwarding table, there
is also no need for mobility management for networks with topology changes.

  * •

Support for multiple protocols Similar to MPLS, MPLF is between the network
layer and the link layer and can support multiple protocols.

  * •

Loop-free. When packets have the same incoming and outgoing ports, they will
be dropped by the node.

  * •

Support for multi-layer SNs. The addressing system uses three-dimensional
coordinates (See V-D) and therefore supports the transfer of packets between
different orbital layers.

However, in order to implement such an architecture, there are some details
that we will discuss later, including location forwarding strategies (Section
V-C), address translation between ground and space (Section V-D), and dealing
with ’cross-seam’ in the Walker constellation Section V-E.

###  V-C Forwarding strategies

Input: last FLR $s_{in},~{}s_{in}\in\mathcal{V}_{adj}(s_{i})$

ECI Coordinations of

destination LER $\mathbf{x}(s_{d})$

current FLR $\mathbf{x}(s_{i})$

adjacent FLRs $\mathbf{x}(s_{j}),~{}s_{j}\in\mathcal{V}_{adj}(s_{i})$

Output: outport $\mathbf{e}_{next}$

1

2$\textit{cos}_{min}\leftarrow 0$;

3 $\mathbf{e}_{d}\left\langle
s_{i},s_{d}\right\rangle=\mathbf{x}(s_{d})-\mathbf{x}(s_{i})$ ;

4 for  _ $s_{j}\in\mathcal{V}_{adj}(s_{i})$ _ do

5

6 $\mathbf{e}(s_{j})\leftarrow\mathbf{x}(s_{j})-\mathbf{x}(s_{i})$ ;

7

8
$\textit{cos}=\mathbf{e}(s_{j})\cdot\mathbf{e}_{d}\backslash(\|\mathbf{e}(s_{j})\|\|\mathbf{e}_{d}\|)$;

9 if  _$\textit{cos}_{min}\geq\textit{cos}$_ then

10 $\textit{cos}_{min}\leftarrow\textit{cos}$;

11 $\mathbf{e}_{next}=\mathbf{e}(s_{j})$

12 end if

13

14 end for

Algorithm 1 MPLF-I with CPI strategy

Input: last FLR $s_{in},~{}s_{in}\in\mathcal{V}_{adj}(s_{i})$

ECI Coordinations of

destination LER $\mathbf{x}(s_{d})$

current FLR $\mathbf{x}(s_{i})$

adjacent FLRs $\mathbf{x}(s_{j}),~{}s_{j}\in\mathcal{V}_{adj}(s_{i})$

Output: outport $\mathbf{e}_{next}$

1

2$d_{min}\leftarrow 0$ ;

3 for  _ $s_{j}\in\mathcal{V}_{adj}(s_{i})$ _ do

4

5 $d_{j}\leftarrow\|\mathbf{x}(s_{j})-\mathbf{x}(s_{i})\|$ ;

6

7 if  _$d_{min}\geq d_{j}$_ then

8 $d_{min}\leftarrow d_{j}$;

9 $\mathbf{e}_{next}=\mathbf{e}(s_{j})$

10 end if

11

12 end for

Algorithm 2 MPLF-II with NFP strategy

Based on the position information, the greedy forwarding strategies such as
NFP (nearest forward progress), i.e., forward to the neighbor is closer to the
destination[35, 18] or CPI (compass routing I)[36], i.e., forward to the
neighbor with the closest slope to that of the line segment connecting the
destination can be applied to MPLF. We refer to the MPLFs that implement the
above two forwarding policies as MPLF-I and MPLF-II, respectively. The
corresponding forwarding algorithm is shown in Algorithm.1 and Algorithm.2.

The LFR needs to query the local coordination as well as the address of
neighboring LFR at each forwarding to determine the next hop LFR. Thus, a LRF
needs to interact with its neighboring LFR at regular intervals to pass
coordination information to each other. In addition, although the LFR are fast
and relatively far away from each other, they do not need extremely accurate
coordination information, which means that the mutual coordination interaction
does not actually need high frequency, and we set 1Hz in the simulation to
transfer coordination information to each other.

###  V-D Coordination Conversion

Since the Geographic coordinate system is not continuous in the
$180^{\circ}W/0^{\circ}E$, which can be ambiguous at NFP or CPI forwarding, we
use Earth Centered Inertial (ECI) coordinate system and Earth-centered, Earth-
fixed (ECEF) coordinate system for datagram addressing. ECEF is generally used
for ground stationary or low-speed motion nodes such as Ground-stations (GSes)
or Mobile Stations (MSes). For satellites, it is more appropriate to use the
ECI coordinate system that takes into account the rotation of the Earth. The
conversion between the two coordinates systems need to be linked to
Coordinated Universal Time (UTC) [54], i.e., the ECI coordinates of an object
are time-varying, regardless of whether the object is moving or not. It is
necessary to consider when and where to convert the coordination.

Figure 8: Coordination Conversion in MPLF.

Fig.8 shows the two coordinate conversion strategies. The first method is very
simple, converting the ECEF coordinates of each LFR to ECI coordinates based
on UTC time and updating them at each hop to obtain accurate coordinates.
However this method is less efficient and can severely reduce the throughput
of the LFR when the traffic becomes heavy. Another method is to convert ECEF
to ECI coordinates in LER only and always use the initial ECI coordinates in
LFR. Although the coordinates will gradually increase the error with time, in
the worst case, i.e., LER is located at the equator, if the Earth orbit speed
is 27000km/s, the error is only 0.46m/ms, which is much lower than the
coverage radius of the satellite. Therefore, the error performance is
completely acceptable which is also the reason that we adopt this method.

###  V-E The Last Gap in MPLF

Compared with StarLink-like constellations, Iridium-like constellations have
more prominent inclinations. They have two orbits with opposite rotations and
large relative velocities, making it impossible to establish persistent ISL
between the satellites across these orbits. This situation creates the ’seam’
between orbits and leads to some routing schemes to have the so-called ’dead-
end’ or ’last hop’[18, 25, 55, 19]. There is no guarantee that CPI and NFR can
be delivered with certainty to the destination in networks with the ’seam’.
Fig.9 shows the dead end which source node send packets through SE satellites
(grey points) to the destination node that in the coverage of NE satellites
(shadow points).

Figure 9: Dead-end in CPI Forwarding.

However, it is foreseeable that as the number of satellites increases, the
source node is able to deliver the packets to the destination node even the
seam exists in the SN. To explore the impact of constellation density (i.e.
the number of satellite in the SN) and latitude on packet delivery, we define
reachability here for pairs $v_{s},v_{d}$ in paths
$\mathcal{P}^{t}_{v_{s}\rightarrow v_{d}}$ at time $t$ as follows:

$\psi^{t}(v_{s},v_{d})=\left\\{\begin{aligned}
1,&~{}\text{if}~{}v_{d}\in\mathcal{V}(e_{\mathcal{N}_{p}}),\exists
e_{\mathcal{N}_{p}}\in\mathcal{P}^{t}_{v_{s}\rightarrow v_{d}}\\\
0,&~{}\textit{other wise}.\end{aligned}\right.$ (4)

where $\mathcal{V}(e_{\mathcal{N}_{p}})$ describe all vertex (i.e., two end of
the link) linked by $\mathcal{N}_{p}$ and $\mathcal{P}^{t}_{v_{s}\rightarrow
v_{d}}$ is paths set at time $t$.

We further define the reachable probability $p_{r}(\mathcal{G})$ to describe
weather MPLF can find a path between two alternative vertexes $v_{s},v_{d}$
included by the satellite network $\mathcal{G}$ during $\mathcal{T}$, which
is:

$p_{r}(\mathcal{G})=\frac{\sum\limits_{\\{v_{s},v_{d}\\}}\sum\limits_{t=1}^{\mathcal{T}}\psi^{t}(v_{s},v_{d})}{|\mathcal{T}|},~{}\forall\\{v_{s},v_{d}\\}\subset\mathcal{V}$
(5)

Fig.10 shows the $p_{r}$ between GSes in SN with different latitudes. We
observe that with the increase of GS latitudes, the higher reachable
probability it achieved due to the denser satellites. The constellation with
$40^{2}$ size ($N=40,P=40$) maintains full reachable probability even at the
lowest latitudes region. The results show that with a dense LEO SN, $100\%$
reachable probability can still be achieved even the GSes located at the
Equator that with the sparsest density of satellites. Thus the effect of seams
can be neglected in such constellations.

Figure 10: Reachable probability among satellites and GSes in 40/40/0(f+0)
constellation.

###  V-F Multipathing in MPLF

LEO Constellation can provide multiple paths between a certain end-to-end
pairs and achieve load balancing through multi-pathing mechanisms such as
Equal-Cost Multipathing (ECMP) [56]. A GS $g$ may associate multiple
satellites $\mathcal{V}_{adj}(g)$ at time $t$ by GSLs
$\mathcal{E}_{S\leftrightarrow G}^{t}(g)$. we focus on paths from
$\mathcal{V}_{adj}(g_{s})$ to $\mathcal{V}_{adj}(g_{d})$ given by the routing
algorithm as the set of equal-cost paths $\mathcal{P}$. Thus, the number of
paths from $g_{s}$ to $g_{d}$ obeys $|\mathcal{P}_{g_{s}\rightarrow
g_{d}}|\leq|\mathcal{V}_{adj}(g_{s})|\ast|\mathcal{V}_{adj}(g_{d})|$ where
$|\mathcal{V}_{adj}(g)|$ is the number of satellites that GS $g$ associated.

However, when only few different links between multiple paths exist, the paths
are too correlated and less independent, which making it difficult to share
the load equally. In graph theory, the average degree is defined as
$d_{avg}=2n_{e}/n_{v}$, where $n_{v},n_{e}$ are the number of vertexes and
edges in a direction graph, and $1\leq d_{avg}\leq n_{v}$ [57]. To better
characterize the potential performance of multipathing over different paths
generated by routing algorithm, we take the $\gamma$ as the metrics to
describe the independency of paths as follows:

$\displaystyle\gamma(\mathcal{P})=\frac{2}{d_{avg}}=\frac{n_{v}}{n_{e}}=\frac{|\mathcal{E}_{S\leftrightarrow
S}(\mathcal{P})|}{|\mathcal{V}_{S}(\mathcal{P})|}$ (6)

where $|\mathcal{E}^{t}_{S\leftrightarrow S}(\mathcal{P})|$ is the number of
ISLs in $\mathcal{P}$ and $|\mathcal{V}^{t}_{S}(\mathcal{P})|$ is the number
of satellites (LFR) in $\mathcal{P}$.

###  V-G Complexity of MPLF

Traditional graphical algorithms such as the Dijkstra and Bellman-Fold
algorithms used in routing algorithms such as Distance Vector (DV) or Link
State (LS) usually have a high complexity, i.e. $O(n^{2})$ of Dijkstra and
$O(n^{3})$ of Bellman-Fold in worst case, where $n$ stands for the number of
nodes in the network. In addition, when small changes in the network occur,
such as the attendance of eISL or changes in link values caused by satellite
moving, creating significant overhead. Therefore, the conventional shortest
path algorithm have scalability problem, which is not suitable for the
networks with large number of nodes. In contrast, proposed MPLF provides
minimum propagation latency paths with the complexity $O(1)$, and it takes a
very short time to process the packets and the time is independent of the
network size. Besides, it does not need to consider the effect of topology and
link length changes to determine the next hop.

Another important point is the storage complexity of the MPLF. On one hand,
given a specific satellite network, the forwarding port for next hop of each
satellite is computed in real-time and can be embedded into the routing code
before deploying the satellites. Hence, no additional space for routing tables
is needed. On the other hand, all the other shortest path algorithms need at
least a connectivity matrix, which is of size $P^{2}\times N^{2}$ where $P$ is
the number of planes and $N$ is the number of satellites in a plane.
Furthermore, in order LER to process the incoming packets faster, a routing
table of size may be necessary. Therefore, our algorithm has much less space
complexity than the other schemes.

##  VI Simulation Study

In oder to show the effectiveness of our proposed MPLF, we compare the paths
generated by MPLF that combined with two forwarding strategies and denoted as
MPLF-I (NFP) and MPLF-II (CRI), with the Shortest Paths (SP) and Least Hop
(LH) paths generated by Bellman-Ford[58]. Large scale characteristics in space
networks lead to dynamic changes between links and high propagation latency,
which is the major part of link cost calculation. Therefore, in experiments we
only take propagation latency into consideration. For performance evaluation
of the MPLF we conducted three main experiments.

  * •

Experiment I: We compare the one-way propagation latency of paths generated by
MPLF with the paths generated by SP and LH among three cities pair.

  * •

Experiment II: We discuss the diversity and evolution of paths generated by
MPLF, SP and LH.

  * •

Experiment III: We applied the MPLF to the terminals that moved over 20000km
and compare the one-way latency of paths generated by MPLF with the paths
generated by SP and LH.

To achieve high-fidelity experiments, we develope a simulation framework SNK
[59] for satellite networking, and all the experiments are conducted on it.
One of the component in this framework is visualizer, a Cesium-based
visualizer that displays entities (e.g., satellites, GSes and aerocrafts) and
interacts (e.g., ISLs,GSLs) in real time in the browser. For downloading and
analysis the data from satellite networks, we also develope the visualizer-
backend to interact with visualizer. All the entities in network such as
satellites, ground station, mobile station, ISLs, etc. are built by the third
component scenario in SNK. In the experiments, we set orbit height to $550km$,
inclination to $53^{\circ}$ and minimum satellite elevation to $40^{\circ}$.

(a) Harbin to London.

(b) London to San Francisco

(c) San Francisco to Shanghai

Figure 11: One way propagation latency between city pairs under 20/20/0(+Grid)
constellation.

(a) Harbin to London.

(b) London to San Francisco

(c) San Francisco to Shanghai

Figure 12: One-way propagation latency between city pairs under 40/40/0(*Grid)
constellation.

(a) Harbin to London.

(b) London to San Francisco

(c) San Francisco to Shanghai

Figure 13: Path diversity between city pairs under 40/40/0(*Grid)
constellation.

(a) Harbin to London.

(b) London to San Francisco

(c) San Francisco to Shanghai

Figure 14: Path evolution between city pairs under 40/40/0(*Grid)
constellation.

###  VI-A End to End latency in GSes

We build constellations with the configuration $N/P/F=20/20/0$ (i.e., with the
size of $20^{2}$) and $N/P/F=40/40/0$ (i.e., with the size of $40^{2}$) and
both of them are patterned as +Grid pattern (See IV-A). We choose 3 typical
cities pairs: Harbin-London, London-San Francisco and San Francisco - Shanghai
at 4 different latitudes, as test connections for routing algorithms.
Simulation duration is set as $2000$ seconds and the time step is 10 seconds.
The one-way latency of Internet is drawn in red dash line which is given by
WonderNetwork111https://wondernetwork.com/ and the geodesic latency (i.e. the
time of geodesic length divided by $2c/3$ where c is light speed [41, 7]) is
drawn in blue dash line.

Fig.11 shows the One-way latency between city pairs in the constellation with
$20^{2}$ size. Due to the absence of the accessing satellite for a GS,
sometimes there is no valid path between cities. The red shadow is the invalid
time of LH, the green shadow is SP’s, the blue one is MPLF-I’s and the cyan
one is MPLF-II’s. In Fig.11 (a) and (b), MPLF-II has achieve a competitive
result with distributed method comparing with LH and SP. In Fig.11(c) the
latency of MPLF-II is lower, however, the valid time of MPLF-II is also
dramatically lower than LH and SP, the reason behind is that the reachable
probability of MPLF-II is decreasing with the density of accessible
satellites. However, After improve the size of constellation from $20^{2}$ to
$40^{2}$ (Fig.12), the MPLF-II has achieved the best performance path in one
way latency among cities which is almost indistinguishable from the path
generated by SP. Also, if the number of satellites is large enough, the ’dead-
end’ problem in MPLF-II will not exist as there is no shadow in the figure.
This clearly shows that our new proposed MPLF provides minimum one way
propagation latency with the complexity $O(1)$.

###  VI-B Diversity and Structure Evolution of Paths

To avoid congestion or failures caused by a particular satellite, the SN can
use path diversity in the routing scheme to provide multiple paths between the
same GS pair. With a routing algorithm, a satellite that associated by the
source $g_{s}$ can at least find a path to the satellite associated with a
destination $g_{d}$. The total number of paths between them is
$|\mathcal{V}^{t}_{adj}(g)|\ast|\mathcal{V}^{t}_{adj}(g_{d})|$ where
$|\mathcal{V}_{adj}(g_{s})|$ is the satellites that $g$ associated at time
$t$. We only take available paths in MPLF-II or MPLF-I into account and we
observe that due to the ’dead-end’ cases in MPLF-II and MPLF-I, the number of
available paths of them is less than LH or SP.

Fig.13 shows the CDF of $\gamma$ in city pairs. We notice that MPLF-II and
MPLF-I are get larger $\gamma$ comparing with LH/SP, which means it generates
more dispersed paths and can achieve higher utilization in practice. Over
$60\%$ paths generated by SP get $\gamma=0.85$, and paths generated by LH get
$\gamma=0.88$ while the paths generated by MPLF-I and MPLF-II gets 0.93 and
0.95 respectively. The higher value of $\gamma$ represents higher utilization.
The main reason behind this behavior is that the node of paths generated by
MPLF are more regularly distributed around a geodesic arc of SRC and DST
nodes, and the utilized links are therefore more concentrated, which brings
the concentrated $\gamma$.

In addition, as the latitudes of communicate GS is getting lower, the $\gamma$
is higher. we identify that such variations is caused by the gradually sparse
satellites that GS associated which reduce the probability of detours. Fig.15
shows the paths $\mathcal{P}^{t}$ in SN. The left one is generated by LH and
SP while the right one is generated by MPLF.

Figure 15: All paths from Harbin to London that provided by LH/SP (upper) and
MPLF (bottom) at an identical time.

Besides the path diversity, we also examine the structure evolution of
generated paths. For each connection, we measure the number of different
vertexes (satellite) between the paths $\mathcal{P}^{t}$ and
$\mathcal{P}^{t+1}$ over the adjacent time in simulation. If the forwarding
paths computed in two successive time-steps shows any different satellites, we
count the number of different satellites as the vertex change, i.e.,
$\|\mathcal{P}^{t}\cup\mathcal{P}^{t+1}-\mathcal{P}^{t}\cap\mathcal{P}^{t+1}\|$.
Across connections, we compute the CDF of these vertexes changes. Fig.14 (a)
and (b) show that in the median, over the 98% paths generated by MPLF change
less than 20 nodes in the connection of ’Harbin-London’ and ’London-San
Francisco’ while LH and SP are 40. In Fig.14 (c), more than 88% of the paths
generated in all algorithms have a number of node changes below 20, but the
rest of the paths generated by LH and SP are between 60 and 80, while MPLF is
only between 20 and 40.

Unlike the current Internet, LEO network paths evolve rapidly, especially for
the denser networks, with paths changing multiple times per minute. Changes in
path forwarding nodes during routing can lead to high fluctuation in data
transmission under network, so fewer changes in the number of nodes can allow
for more robust end-to-end data transmission.

TABLE II: Detailed information of moving LERs.

LER Name | AC00 | AC01 | AC02 | AC03 | AC04 | AC05 | AC06 | AC07 | AC08 | AC09 | AC10
---|---|---|---|---|---|---|---|---|---|---|---
Start Point | 0E,50N | 18E,50N | 36E,50N | 54E,50N | 72E,50N | 90E,50N | 0E,40N | 0E,30N | 0E,20N | 0E,10N | 0E,0N
End Point | 180W,50S | 162W,50S | 144W,50S | 126W,50S | 108W,50S | 90E,50S | 180W,40S | 180W,30S | 180W,20S | 180W,10S | 180W,0S
Distance (km) | 19998.15 | 17461.25 | 15062.56 | 13020.83 | 11599.87 | 11081.69 | 19970.32 | 19972.31 | 19977.69 | 19984.97 | 19992.30
Velocity (km/s) | 10.1 | 8.81 | 7.60 | 6.57 | 5.85 | 5.59 | 10.08 | 10.08 | 10.08 | 10.08 | 10.08
$\bullet$ denotes the Distance is LER moving distance instead of end-to-end distance. |  |  |  |

Figure 16: The trajectory of moving nodes.

###  VI-C Latencies between Fixed GS and Moving LER

(a) Distribution of Avg. hop-counts of paths.

(b) Distribution of paths stretches.

Figure 17: One way propagation latency among cities in 40/40/0(+Grid)
constellation.

The space network can also provide communication to mobile objects such as
aircraft, ship or remote sensing satellite, therefore we wonder how the
propagation latency of the moving target behaves. In order to demonstrate the
propagation latencies and their distribution due to the terminals mobility, we
consider a scenario with multiple aircraft (moving LER) at different starting
points and end points from West to East. We use the constellation
$N/P/F=40/40/0$ with +Grid pattern as the network. The simulation duration is
set as 1980 seconds and the time step is 10 seconds. All the moving details of
LERs are shown in Tab.II.

Latency and jitter. We randomly select the paths between Harbin and Moving LER
generated by SP, LH, MPLF-I and MPLF-II, and plot their one-way propagation
latency on average, minimum, and maximum under the same constellation, as
shown in Fig.16. We observe that MPLF performs better results among all the
LER pairs, reducing the average latency by about 5ms to 10ms compared with LH
and SP, outperforming the other algorithms with about 14%. Besides, the path
fluctuations generated by MPLF are narrower than those generated by LH and SP
in most connections. For example, the fluctuations of ’Harbin-AC03’ and
’Harbin-AC04’ under LH and SP are more than 20 ms, while it is only 8 ms under
MPLF, about 60% reduction, which can significantly reduce network jitter.

Hops-count. Fig.17(a) shows the distribution of hop-count in paths to reflect
the one-way process latency and transmission latency in networking. We observe
that the MPLF outperforms the LH and SP with about 66% reduction in maximum
hops and 50% in hops jitter.

Stretches. Since the distances between pairs varying, we refer [12, 7] to
quantify latency in terms of stretch, i.e., the ratio of the path distance
across the designed network and the geodesic distance. The lower stretch
represents the less detours of the path. Fig.17(b) shows the distribution of
path stretch changes between 11 moving LER pairs. We observe that all the
stretch are under 1.6 in the paths generated by MPLF while all the stretches
are under 2.1 in the paths generated by SP and LH. Fig.18 shows the paths
generated by LH,SP,MPLF-I and MPLF-II between Harbin and moving LER at the end
point. The blue lines are the trajectories of moving LER.

From experiments results above, MPLF achieves better performance in terms of
latency compared with LH and SP. The path diversity and structure evolution
also illustrate that the MPLF can provides higher utilization. The advantage
of MPLF is not obvious when the range is extended to more GSes, but when
applied to mobile terminals, MPLF gets the best results compared to other
algorithms. It is worth noting that MPLF is a distributed algorithm, and
satellites also do not need to save global topological adjacencies. The
efficiency of its algorithm, which has only $O(1)$ complexity compared to
$O(n^{2})$ or $O(n^{3})$ of Dijkstra or Bellman-Ford, achieves better results
than other methods, which is highly feasible in space.

Figure 18: The trajectory of moving nodes.

##  VII Conclusion

This paper studied the design of architecture to enable low-latency
transmission in emerging LEO SNs. We investigate the structure design of space
networks and propose a distributed routing architecture MPLF, which
incorporates the location and orientation of mobile satellites into next-hop
decisions, but with dramatically lower complexity. Comprehensive experiment
results demonstrate that our algorithm outperforms related algorithms.

## References

  * [1] L. Space Exploration Holdings, “Spacex ka-band ngso constellation fcc filing sat-loa-20161115-00118,” http://licensing.fcc.gov.
  * [2] ——, “Spacex ka-band ngso constellation fcc filing sat-loa-20200526-00055-2378671,” http://licensing.fcc.gov.
  * [3] F. C. Commision, _FCC Grants OneWeb US Access for Broadband Satellite Constellation._ , https://docs.fcc.gov/public/attachments/DOC-345467A1.pdf, 2017.
  * [4] T. Canada, _SAT-MPL-20200526-00053_ , http://licensing.fcc.gov/myibfs/forwardtopublictabaction.do?filenumber=SATMPL2020052600053.
  * [5] T. Clausen and P. Jacquet, “Rfc3626: Optimized link state routing protocol (olsr),” 2003.
  * [6] C. Perkins, E. Belding-Royer, and S. Das, “Rfc3561: Ad hoc on-demand distance vector (aodv) routing,” 2003.
  * [7] S. Kassing, D. Bhattacherjee, A. B. Águas, J. E. Saethre, and A. Singla, “Exploring the” internet from space” with hypatia,” in _Proceedings of the ACM Internet Measurement Conference_ , 2020, pp. 214–229.
  * [8] I. C. Inc, “Iridium next,” https://www.iridiumnext.com/, 2020.
  * [9] L. Application of Kuiper Systems, _Kuiper NGSO constellation FCC filing SAT-LOA-20190704-00057_ , http://licensing.fcc.gov/myibfs/forwardtopublictabaction.do?filenumber=SATLOA2019070400057.
  * [10] H. S. Chang, B. W. Kim, C. G. Lee, Y. Choi, S. L. Min, H. S. Yang, and C. S. Kim, “Topological design and routing for low-earth orbit satellite networks,” in _Proceedings of GLOBECOM’95_ , vol. 1. IEEE, 1995, pp. 529–535.
  * [11] H. S. Chang, B. W. Kim, C. G. Lee, S. L. Min, Y. Choi, H. S. Yang, D. N. Kim, and C. S. Kim, “Fsa-based link assignment and routing in low-earth orbit satellite networks,” _IEEE transactions on vehicular technology_ , vol. 47, no. 3, pp. 1037–1048, 1998.
  * [12] D. Bhattacherjee and A. Singla, “Network topology design at 27,000 km/hour,” in _Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies_ , 2019, pp. 341–354.
  * [13] M. Al-Fares, A. Loukissas, and A. Vahdat, “A scalable, commodity data center network architecture,” _ACM SIGCOMM computer communication review_ , vol. 38, no. 4, pp. 63–74, 2008.
  * [14] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: Networking data centers randomly,” in _9th USENIX Symposium on Networked Systems Design and Implementation (NSDI 12)_ , 2012, pp. 225–238.
  * [15] Z. Yan, G. Gu, K. Zhao, Q. Wang, G. Li, X. Nie, H. Yang, and S. Du, “Integer linear programming based topology design for gnsss with inter-satellite links,” _IEEE Wireless Communications Letters_ , vol. 10, no. 2, pp. 286–290, 2020.
  * [16] D. Bhattacherjee, “Towards performant networking from low-earth orbit,” Ph.D. dissertation, ETH Zurich, 2021.
  * [17] L. Wood, _Internetworking with satellite constellations_. University of Surrey (United Kingdom), 2001.
  * [18] T. R. Henderson and R. H. Katz, “On distributed, geographic-based packet routing for leo satellite networks,” in _Globecom’00-IEEE. Global Telecommunications Conference. Conference Record (Cat. No. 00CH37137)_ , vol. 2. IEEE, 2000, pp. 1119–1123.
  * [19] H. Tsunoda, K. Ohta, N. Kato, and Y. Nemoto, “Geographical and orbital information based mobility management to overcome last-hop ambiguity over ip/leo satellite networks,” in _2006 IEEE International Conference on Communications_ , vol. 4. IEEE, 2006, pp. 1849–1854.
  * [20] M. Besta, J. Domke, M. Schneider, M. Konieczny, S. Di Girolamo, T. Schneider, A. Singla, and T. Hoefler, “High-performance routing with multipathing and path diversity in ethernet and hpc networks,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 4, pp. 943–959, 2020.
  * [21] R. Mauger and C. Rosenberg, “Qos guarantees for multimedia services on a tdma-based satellite network,” _IEEE Communications Magazine_ , vol. 35, no. 7, pp. 56–65, 1997.
  * [22] M. Werner, “A dynamic routing concept for atm-based satellite personal communication networks,” _IEEE journal on selected areas in communications_ , vol. 15, no. 8, pp. 1636–1648, 1997.
  * [23] A. Donner, M. Berioli, and M. Werner, “Mpls-based satellite constellation networks,” _IEEE Journal on Selected areas in Communications_ , vol. 22, no. 3, pp. 438–448, 2004.
  * [24] M. C. Inc, “Celestri,” http://www.celestri.com/, 1998.
  * [25] E. Ekici, I. F. Akyildiz, and M. D. Bender, “Datagram routing algorithm for leo satellite networks,” in _Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No. 00CH37064)_ , vol. 2. IEEE, 2000, pp. 500–508.
  * [26] ——, “A distributed routing algorithm for datagram traffic in leo satellite networks,” _IEEE/ACM Transactions on networking_ , vol. 9, no. 2, pp. 137–147, 2001.
  * [27] M. Jia, S. Zhu, L. Wang, Q. Guo, H. Wang, and Z. Liu, “Routing algorithm with virtual topology toward to huge numbers of leo mobile satellite network based on sdn,” _Mobile Networks and Applications_ , vol. 23, no. 2, pp. 285–300, 2018.
  * [28] T. Zhang, J. Li, H. Li, S. Zhang, P. Wang, and H. Shen, “Application of time-varying graph theory over the space information networks,” _IEEE Network_ , vol. 34, no. 2, pp. 179–185, 2020.
  * [29] Q. Chen, J. Guo, L. Yang, X. Liu, and X. Chen, “Topology virtualization and dynamics shielding method for leo satellite networks,” _IEEE Communications Letters_ , vol. 24, no. 2, pp. 433–437, 2019.
  * [30] Ö. Korçak and F. Alagöz, “Virtual topology dynamics and handover mechanisms in earth-fixed leo satellite systems,” _Computer networks_ , vol. 53, no. 9, pp. 1497–1511, 2009.
  * [31] F. Cadger, K. Curran, J. Santos, and S. Moffett, “A survey of geographical routing in wireless ad-hoc networks,” _IEEE Communications Surveys & Tutorials_, vol. 15, no. 2, pp. 621–653, 2012.
  * [32] M. Mauve, J. Widmer, and H. Hartenstein, “A survey on position-based routing in mobile ad hoc networks,” _IEEE network_ , vol. 15, no. 6, pp. 30–39, 2001\.
  * [33] J. C. Navas and T. Imielinski, “Geocast—geographic addressing and routing,” in _Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking_ , 1997, pp. 66–76.
  * [34] H. Takagi and L. Kleinrock, “Optimal transmission ranges for randomly distributed packet radio terminals,” _IEEE Transactions on communications_ , vol. 32, no. 3, pp. 246–257, 1984.
  * [35] T.-C. Hou and V. Li, “Transmission range control in multihop packet radio networks,” _IEEE Transactions on Communications_ , vol. 34, no. 1, pp. 38–44, 1986.
  * [36] E. Kranakis, H. Singh, and J. Urrutia, “Compass routing on geometric networks,” in _in Proc. 11 th Canadian Conference on Computational Geometry_. Citeseer, 1999.
  * [37] R. Nelson and L. Kleinrock, “The spatial capacity of a slotted aloha multihop packet radio network with capture,” _IEEE Transactions on Communications_ , vol. 32, no. 6, pp. 684–694, 1984.
  * [38] F. Kuhn, R. Wattenhofer, and A. Zollinger, “An algorithmic approach to geographic routing in ad hoc and sensor networks,” _IEEE/ACM Transactions On Networking_ , vol. 16, no. 1, pp. 51–62, 2008.
  * [39] B. Karp and H. T. Kung, “Gpsr: Greedy perimeter stateless routing for wireless networks,” in _Proceedings of the 6th annual international conference on Mobile computing and networking_ , 2000, pp. 243–254.
  * [40] H. Tsunoda, K. Ohta, N. Kato, and Y. Nemoto, “Supporting ip/leo satellite networks by handover-independent ip mobility management,” _IEEE Journal on selected areas in communications_ , vol. 22, no. 2, pp. 300–307, 2004.
  * [41] M. Handley, “Delay is not an option: Low latency routing in space,” in _Proceedings of the 17th ACM Workshop on Hot Topics in Networks_ , 2018, pp. 85–91.
  * [42] Z. Lai, H. Li, and J. Li, “Starperf: Characterizing network performance for emerging mega-constellations,” in _2020 IEEE 28th International Conference on Network Protocols (ICNP)_. IEEE, 2020, pp. 1–11.
  * [43] P. Berde, M. Gerola, J. Hart, Y. Higuchi, M. Kobayashi, T. Koide, B. Lantz, B. O’Connor, P. Radoslavov, W. Snow _et al._ , “Onos: towards an open, distributed sdn os,” in _Proceedings of the third workshop on Hot topics in software defined networking_ , 2014, pp. 1–6.
  * [44] J. G. Walker, “Satellite constellations,” _Journal of the British Interplanetary Society_ , vol. 37, p. 559, 1984.
  * [45] J. Bao, B. Zhao, W. Yu, Z. Feng, C. Wu, and Z. Gong, “Opensan: a software-defined satellite network architecture,” _ACM SIGCOMM Computer Communication Review_ , vol. 44, no. 4, pp. 347–348, 2014.
  * [46] Y. Zhang, Q. Wu, Z. Lai, and H. Li, “Enabling low-latency-capable satellite-ground topology for emerging leo satellite networks,” in _IEEE INFOCOM 2022-IEEE Conference on Computer Communications_. IEEE, 2022, pp. 1329–1338.
  * [47] E. Rosen, A. Viswanathan, and R. Callon, “Rfc3031: Multiprotocol label switching architecture,” 2001.
  * [48] A. S. Tanenbaum, _Computer networks_. Pearson Education India, 2003.
  * [49] L. L. Peterson and B. S. Davie, _Computer networks: a systems approach_. Elsevier, 2007.
  * [50] T. Ors and C. Rosenberg, “Providing ip qos over geo satellite systems using mpls,” _International journal of satellite communications_ , vol. 19, no. 5, pp. 443–461, 2001.
  * [51] T. G. Reid, A. M. Neish, T. Walter, and P. K. Enge, “Broadband leo constellations for navigation,” _Navigation: Journal of The Institute of Navigation_ , vol. 65, no. 2, pp. 205–220, 2018.
  * [52] D. Awduche, L. Berger, D. Gan, T. Li, V. Srinivasan, and G. Swallow, “Rsvp-te: extensions to rsvp for lsp tunnels,” Tech. Rep., 2001.
  * [53] B. Jamoussi, L. Andersson, R. Callon, R. Dantu, L. Wu, P. Doolan, T. Worster, N. Feldman, A. Fredette, M. Girish _et al._ , “Constraint-based lsp setup using ldp,” Tech. Rep., 2002.
  * [54] J. Zhu, “Conversion of earth-centered earth-fixed coordinates to geodetic coordinates,” _IEEE Transactions on Aerospace and Electronic Systems_ , vol. 30, no. 3, pp. 957–961, 1994.
  * [55] M. Roth, H. Brandt, and H. Bischl, “Implementation of a geographical routing scheme for low earth orbiting satellite constellations using intersatellite links,” _International Journal of Satellite Communications and Networking_ , vol. 39, no. 1, pp. 92–107, 2021.
  * [56] C. Hopps, “Analysis of an equal-cost multi-path algorithm,” Tech. Rep., 2000.
  * [57] D. B. West _et al._ , _Introduction to graph theory_. Prentice hall Upper Saddle River, 2001, vol. 2.
  * [58] A. Kershenbaum, _Telecommunications network design algorithms_. McGraw-Hill, Inc., 1993.
  * [59] W. Xiangtong, “Space networking kit,” https://github.com/xdr940/snk, 2022\.