A compass time-space model-based virtual IP routing scheme for NTSN satellite constellations

Yifei JIANG, Shufan WU, Qiankun MO

School of Aeronautics and Astronautics, Shanghai Jiao Tong University, Shanghai 200240, China

KEYWORDS

Abstract Recently, Non-Terrestrial Satellite Networks (NTSTs) have gained more and more attentions due to global coverage, low latency, and high-speed communications.The routing scheme is one of the primary challenges for NTSNs, due to the mega scale of an NTSN constellation and the dynamic topology feature.To solve many pressing problems, a Compass time-space Model-based Virtual IP(CMVIP)routing scheme is proposed in this paper.In order to compensate for discontinuities in existing topology models,a compass-shaped time-space model is proposed.It can be adapted with Inter-Satellite-Link (ISL) and Ground-Satellite-Link (GSL) transmissions.A distributed algorithm with multiple optimization objectives and multiple constraints is applied for routing path discovery.To more realistically verify the specific scheme,a traffic model that supports two different services is proposed.Access and bearer services are the two main applications of an NTSN.Experimental results demonstrate that the proposed scheme achieves superior Qualityof-Service (QoS) performance.In addition, comparison results demonstrate that the CMVIP routing scheme is superior to the Virtual-Topology-based Shortest Path (VT-SP) routing algorithm.

1.Introduction

With rapid developments of personal mobile communication,Non-Terrestrial Network (NTN) technologies have attracted a lot of attention in academia and industry.Especially, with the gradual construction of many commercial satellite constellations, e.g., Starlink, OneWeb, and Telesat, many key technologies of satellite Internet become the core of 6G communication.Compared with a terrestrial network, an NTN has many advantages such as global access and network security.

International Network Generations Roadmap1has shown the complete NTN topology including Geosynchronous Earth Orbit (GEO), Medium Earth Orbit (MEO), Low Earth Orbit(LEO), and High Altitude Platform (HAP).GEO and MEO are set up as a network control plane,and they are responsible for the operation and maintenance of an NTN.HAP is used as auxiliary access for ground terminals.As the bearer network of an NTN2system, LEO can realize both terminal access and data relay functions.All data flows are delivered through the LEO constellation.A low-orbit Non-Terrestrial Satellite Network (NTSN) exhibits many special features: frequent topology variation; harsh space environment; limited power and frequency resources.Unfortunately, those features will greatly degrade network performance.After a lot of research,many scholars believe that an excellent routing strategy can make up for these shortcomings.Moreover, some novel routing strategies have special advantages, e.g., Quality-of-Service(QoS) guarantee, load balance, and high reliability.From a system perspective,the routing scheme may determine the network performance of an NTSN.

In most research, NTSN routing strategies3can be mainly divided into static and dynamic routing schemes.The basic concept of a static routing scheme is to calculate the routing path in a centralized node, and the routing path cannot be adaptively adjusted with changes of satellite topology.Liu et al.4proposed a satellite network task deployment method based on Software-Defined Network (SDN) and Information-Centric Network (ICN).Kumar et al.5proposed a centralized QoS-aware routing algorithm for a beyond 5G NTN.A modified Bresenham algorithm and Dijkstra algorithm were implemented to find the optimal path in a significantly reduced computation time.However, all static routing schemes suffer from sudden link failure or congestion because centralized routing calculation cannot be changed once completed.Dynamic routing strategies are implemented and distributed in each NTSN node.By these strategies, the selection of next node is according to the latest network state.The routing path can also be adaptively adjusted according to the dynamic link state.Shiyue Dai et al.6proposed a Distributed Congestion Control Routing (DCCR) protocol based on traffic classification in LEO satellite networks.A lowoverhead distributed scheme was used to compute the routing.A Longer Side Priority(LSP)strategy was proposed,aiming at maximizing the path searching space.However, this kind of dynamic routing strategy still depends on the Link State Information (LSI) which relies on periodic information updates.Therefore, a network space–time model is crucial for all kinds of routing strategies.

Virtual Topology(VT)and Virtual Node(VN)are the most widely used models.For the former model, the entire running cycle is divided into a large number of time slots.In each slot,the network topology and link status are considered constant.Yang et al.7proposed VT-based Networking (VTN) for promoting global interconnection.However, to guarantee performance, the time slot must gradually decrease with the dynamics increasing.For a complex NTSN with a high traffic density,too small time slots will seriously increase the computation burden.For the later model, the surface of the Earth is divided into a large number of small areas that are assigned a virtual center.The NTSN node that is geographically closest to the virtual center is assumed to be the virtual node.Ekici et al.8proposed a VN-based distributed routing algorithm for datagram traffic in satellite networks.However, the VN model cannot guarantee continuity when the constellation topology changes.For complex satellite constellations, frequent nodes switching will greatly increases overhand.This can degrade network performance.VT and VN are timeand space-based models, respectively.

Some novel network topology models improve system performance by fusing time- and space-based models.Li et al.9proposed a novel Temporal Netgrid Model(TNM) to portray the time-varying topology of large-scale satellite networks.This design makes up for many link status update interruption problems caused by time discontinuity.However, the main solution is still to divide the space into small cubes.Li et al.10proposed a global space grid to calculate spatial interconnection between satellite constellations.The GeoSOT-3D global grid model was introduced into aerospace topology for high performance by this model, and other similar models11–13were given to improve the network performance.Unfortunately, these models not only failed to fully solve the temporal and spatial continuity problems, but also failed to take into account the access problems of ground terminals.Moreover, some 3D space models are too complicated compared to 2D plane models.

In addition to topology models, routing algorithms are another research hotspot for improving NTSN performance.Many multi-objective optimization algorithms for QoS optimization have greatly improved network performance.Dai et al.14proposed a Quality of Experience (QoE)-aware algorithm to enhance user satisfaction by constructing QoE factors.This algorithm is based on analyzing dynamic network topology and multilayer tabu search.Liu et al.15proposed a bee colony algorithm optimization based on link cost.A model of inter-satellite links was established based on metrics of network transmission performance16namely delay and wavelengths utilization, with constraints of Doppler wavelength drift,transmission delay,wavelength consistency and continuity.This multi-objective17and multi-restriction routing algorithm can improve various QoS performances.However, a mismatch between the routing algorithm and the topology model will greatly degrade system performance.

Finally,a realistic and valid traffic model is the key to verify NTSN performance.Song et al.18proposed a multiple source–destination pairs traffic model as simulation conditions.This model can effectively verify the point-to-point communication performance, but it is not suitable for the traffic congestion problem.Manuel Roth proposed a geographical locationsbased traffic distribution.It is randomized and follows the distribution of a population density map of the Earth.However,this model ignores the case of device-to -device applications.

Based on the above analysis,a Compass time-space Modelbased Virtual IP (CMVIP) routing scheme is proposed for NTSN application.The specific topology model is suitable for Inter-Satellite-Link (ISL) and Ground-Satellite-Link(GSL).Both temporal and spatial continuities are considered.A proposed QoS-optimized routing algorithm takes into account network congestion and delay simultaneously.Especially,many communication physical layer conditions are also added into the algorithm, e.g., antenna beam hopping delay and antenna pointing delay.A traffic model including access services and bearer services is proposed.It’s applied to effectively verify the CMVIP routing scheme by a large number of simulations.

2.Topology model

2.1.Constellation topology

Walker constellation is the preferred topology for an NTSN due to its symmetry and stability.According to the different orbit elements, walker constellation can be subdivided into walker delta and walker polar.The former distributes multiple inclined orbits evenly over the entire equator.It can cover low and middle latitudes efficiently,but misses the poles.The most typical application is Starlink.The later distributes multiple vertical orbits over the half equator.It can achieve global coverage,but cannot meet traffic hotspot requirements.The most typical application is OneWeb and Iridium.

To study mega NTSN and global traffic problems, a walker-delta constellation is applied as the research object.The specific walker-delta constellation consists of 48 orbits and 1152 satellites.As shown in Fig.1, any ground terminal can be served by at least four satellites simultaneously.Two of them move upward (follow the orbit from South Pole to North Pole), and the other two move downward (follow the orbit from North Pole to South Pole).

An inclination of 55° and an altitude of 550 km are the basic parameters of the constellation.Each satellite can be represented by (O, S), where O is the orbit factor and S is the satellite phase factor.

2.2.CTSM design

For a walker-delta constellation, there are two moving factors namely Earth rotation and satellite orbit dynamics.Once the Center of the Earth(CE)is assumed to be a point of reference,any surface location moves periodically around a ring of equal latitude.This ring is stationary relative to the CE.Any satellite moves periodically around the CE in orbit.The orbit plane is also stationary relative to the CE.

In order to clearly describe the research question, a meshlike Virtual IP network Topology (VIPT) is introduced as a time-space network topology model.This model is used for route computation and mobility management.The number of IP nodes in the VIPT is equal to the total number of satellites in the constellation.The VIPT is a sphere-like shaped topology and relatively stationary with the CE.

As shown in Fig.2, the layer of the VIPT is between the satellite layer and the ground surface.From the perspective of the VIPT, all satellites move periodically along the orbit,and all ground locations move periodically along the isolatitude line.The VIPT can be divided into 48 subnet segments.Each subnet consists of 24 IP nodes.The IP address of the VIPT can be described as [X.Y.N.M], where X and Y mean a non-terrestrial or terrestrial network, respectively, N indicates the subnet Factor (NF), and M indicates the Address Factor(AF).In our design, the main purpose is to determine the parameters of N and M through the core algorithm.

Fig.1 Walker-delta constellation schematic.

Fig.2 Virtual IP network topology model.

With the relative motion between a satellite and the Earth,satellites will be dynamically assigned different IP addresses,and the ground area will be served by different IP nodes.Each IP node uniquely corresponds to an IP address.In order to efficiently allocate IP addresses and IP nodes, we propose a compass structure model.IP address and IP node allocation functions will be discussed in detail below.

For the IP address allocation function, 24 satellites in the same orbit are periodically assigned IP addresses which belong to the same network segment.To describe the problem more clearly, an IP Address Compass (IPACO) is introduced.As shown in Fig.3, there are two rings in the IPACO.The inner ring indicates the IP address in the same subnet,and the outer ring indicates the satellites in the same orbit.The inner ring is stationary relative to the CE.The outer ring rotates with the orbit motion.

In the initial state, the Address Factor (AF) is equal to the phase factor of the nearest satellite (AF = S), as shown in Fig.3 (Time Step 1).IPaddresscan be calculated by

Fig.3 Compass model for IP addresses (IPACO).

where Trunis the running time, Torbitis the orbit period, λ1is used to adjust the fluctuations caused by orbit perturbations,and numsis the number of satellites in an orbit.()integermeans extraction of the integer, while ()remaindermeans extraction of the remainder.

After Tslot-OPfrom beginning, the IP address is cyclically delayed by one bit.The updated state is shown in Fig.3(Time Step 2).

The entire constellation requires a 48-IP Address COmpass(IPACO) for the IP address allocation function.They operate independently, and each is responsible for an independent subnet.

For the IP node allocation function, the isolatitude regions are equally divided into 48 equal parts.They are periodically served by different IP nodes.To describe the problem more clearly, an IP Node COmpass (IPNCO) is introduced.As shown in Fig.4, there are two rings in the IPNCO.The inner ring indicates the equal-latitude regions, and the outer ring indicates the IP nodes in different subnets.The outer ring is stationary relative to the CE.The inner ring rotates with earth rotation.

In the initial state,the IP node for a specific area is equal to the subnet factor (NF) of the nearest satellite as shown in Fig.4 (Time Step 1).Different IP nodes will serve the same ground area periodically.IPnodeat any time can be calculated by

where Trunis the running time,Tearthis the Earth rotation period,λ2is used to adjust fluctuations caused by Earth rotation,and numOis the number of orbits.()integermeans extraction of the integer, ()remaindermeans extraction of the remainder.

After Tslot-EPfrom beginning, the IP node is cyclically delayed by one bit.As shown in Fig.4 (Time Step 2).

The global coverage requires a 24-IP node compass(IPNCO)for the IP node allocation function.Half is responsible for the ascending orbits, and the other half is responsible for the descending orbits.

During the operation, two compass models maintain in a cross shape as shown in Fig.5.The VIPT remains stationary relatively to the CE, and two different types of compasses rotate at their respective directions.

Fig.4 Compass model for IP nodes (IPNCO).

Fig.5 Two-dimensional compass model.

A walker-delta constellation has a crossed structure.The ascending and descending orbits are intertwined to form an overlapping mesh.Any ground terminal can be served by two ascending and two descending satellites at the same time.This feature is also feasible for multi-path transmission.To increase coverage efficiency, the IP addresses assigned to ascending and descending satellites cross each other as shown in Fig.6.In the process of the network operation, there are two key technologies,namely,access point switching and routing path finding which depend on the topological state.The relationship between users, satellites, and IP addresses can be dynamically characterized independently by two compasses.

In the VIPT, IP nodes can be described as (N.M).Yellow circles are for ascending satellites, and green circles are for descending satellites.This interwoven structure can not only increase coverage,but also improve compass time-space model efficiency.

3.CMVIP algorithm

A compass model virtual IP routing algorithm is proposed for QoS optimization in this section.Some Key Performance Indicators (KPIs) such as latency, congestion, and bandwidth are considered in the algorithm as optimization goals.Parameters such as antenna pointing and visibility angle are also considered as constraints.

The latency can be divided into access latency and bearer latency.The former is caused by Ground-Satellite-Link(GSL) delay, and the latter is caused by Inter-Satellite-Link(ISL) delay.The latency19of access can be described as

Fig.6 Global virtual IP topology schematic.

where delaypro-accis the propagation delay,delaybeam-hopis the antenna beam hopping delay, delayprocessis the digital processor delay, delayqueue-accis the queue delay, c is the speed of light, θ is the ground elevation angle, h is the orbit altitude,PacketGSLis the number of packets waiting in the cache for GSL transmission, D is the size of the packets, and BW is the bandwidth of the GSL channel.Delayaccessis responsible for the access services, which means the satellite relay data from a ground terminal to a ground gateway like a bend pipe.The latency of bearer services can be described as

where delaypro-beris the propagation20delay, delaypointis the antenna point delay, delayprocessis the digital processor delay,delayqueue-beris the queue delay,lvis the distance between adjacent satellites in the same orbit, lhis the distance between neighboring satellites in adjacent orbits, PacketISLis the number of packets waiting in the cache for ISL transmission, and BW is the bandwidth of the ISL channel.Delaybeareris responsible for the bearer services,which means that data is transmitted between satellites.

To normalize the latency, expired time is defined as TAccExpiredand TBerExpired.Therefore, the normalized delay can be expressed as

In addition to latency, congestion is also a parameter that must be considered.In order to increase the system isolation,there are two memory spaces for access services and bearer services respectively.Storage Rate (SR) is defined as the ratio of the number of stored packets to the Memory Space (MS).They can be described as

where SRacc,SRber,MSacc,and MSberare the storage rate and memory space of access services and bearer services,respectively.

Based on the above discussion, a QoS-oriented objective function for links is described as

where α,β1,β2,and χ are adjustment parameters used to balance the weights of different KPIs.

The objective function for a path can be described as

where path(k) is one of the multiple candidate paths.

The boundary conditions of optimization are described as

where BWrestrictionand Delayrestrictionare restrictions of the specific business.State() is the link state evaluation function.This state evaluation function can be achieved through the SPI signaling mechanism.

According to different business types,the operation process of the algorithm can be divided into an access routing algorithm and a bearer routing algorithm.

The access routing algorithm in the CMVIP(see Algorithm 1)calculates the optimal access satellite node according to Eqs.(11), (12), (19), (20), (21), and (22).

Algorithm 1 ?Access routing in CMVIP

Input:Linkstatesofconstellation Input:Sourceanddestination Input:RestrictionofBWanddelay 1?For: Fourusablesatellitesforaccess 2? While:Restrictionjudgment 3? Goalfunctionconstruction 4? End 5? Weightcalculationandsort 6? Accessnodeselection 7? Availabledurationestimation 8?End

The bearer routing algorithm in the CMVIP(see Algorithm 2)calculates multiple optimal bearer paths according Eqs.(15)～(21).The specific multiple routing algorithm can support multipath routing and failure recovery.

Algorithm 2?Bearer routing in CMVIP

Input:Linkstatesofconstellation Input:Sourceanddestination Input:RestrictionofBWanddelay 1?For:Fourusablesatellitesforsource 2? ForFourusablesatellites 3? Calculatetheshortesthops 4? While:Failedlinkelimination 5? Traversepossiblepath 6? Restrictionjudgment 7? Goalfunctionconstruction 8? Hopsrestriction 9? Durationestimations 10? End 11? Weightcalculation 12? Weightcompareandsort 13? End 14 ReserveNavailablepaths 15? End

The link state is mainly determined by a node’s transceiver channel.By default,when the node’s buffer space is free,packets can be sent according to the bandwidth capacity.In a congested and failure state, handshake signaling will keep the system up and running.In addition, the state between neighboring nodes can also be kept known by adding a control symbol in the frame header21.

There is no need to recompute a complete routing path at each node.Once the source node has calculated a complete path, it will be stored in the packet header.The intermediate node will determine whether to restart the routing calculation or to use the original routing path according to the congestion status and link status of the node.The main judgment is based on the queue delay of the forwarding channel and the status of next node.This design can greatly reduce the computational complexity.Each node periodically updates the routing table of the entire network in space and time, which ensures that new data packets do not need to wait for routing calculations.Moreover, in the process of outgoing, while optimizing the routing path, since the link state and node state are updated periodically, route discovery implementation can be guaranteed to be in the order of 10 ms.

The above routing algorithms are used not only to establish a routing path in the route discovery,but also for rerouting in route maintenance and failure recovery.By integrating with the CMVIP,the efficiency of the routing scheme can be greatly improved.

4.Traffic model

For more realistic verification of routing performance,a traffic model that matchs a real application is essential.As a supplement to terrestrial mobile communications, NTSNs mainly provide two services.The first service provides Internet access in remote areas, oceans, and mountains.Thanks to the large coverage of one satellite,this service can be realized by a single satellite which connects user and terrestrial gateway together.The second service provides Device-to-Device (D2D) dedicated connection for financial, medical, and military applications.This service requires Inter-Satellite-Link (ISL) and multi-hop relay.

Traffics of both services are related to population distribution and time, and the traffics of the two services are independent.To make a traffic model general, the traffic model is related to the size of the constellation.It is determined by three key parameters, namely the Number of Data Flows (NDF),the allocation of Data Flows(ADF),and the Number of Traffic (NT).The NDF determines the number of flows generated per cycle, the ADT determines the positions of flows, and the NT determines the number of packets generated in a flow(see Algorithm 3).They can be described as

where Poson()is a poisson distribution function,RS()is a random selection function, and Nor() is a normal distribution function.Pn(t)and Pd(lat)are the time and latitude correction functions, respectively, which can refer to the mobile communication traffic curve.NumSat is the total number of satellites in the constellation.l is the destiny factor of the traffic namely lemda, and A is the selection factor for access business and bearer business.

Algorithm 3?Traffic generation

Input:Timeandlatitude Input: l 1? NDTcalculation 2? While:NDTdo 3? ADTcalculation 4? While:ADTdo 5? NTcalculation 6? End 7? Trafficgeneration 8?End

From initialization, the number of flows, the number of tarffics,and the selection of the source and destination are calculated separately.

5.Performance evaluation

To verify the CMVIP, a series of simulations is implemented.The simulation scenario is constructed by using the System Tool Kit (STK) and the Network X tool package.

5.1.Simulation scenario settings

A walker-delta constellation can be described as T/P/F,where T is the total satellite number, P is the orbital plane number,and F is the phase factor.In this paper, a constellation with 1152/48/24 is the basic simulation scenario.

A set of CMVIP parameters is shown in Table 1.Some parameters are adjustable to optimize the routing scheme,e.g., λ1, λ2, TAccExpired, TBerExpired, α, and χ.Other parameters are determined by system design.

Table 1 CMVIP parameters.

A set of simlulation parameters is shown in Table 2.

Multiple D2D flows are implmented to verify the bearer services.Eleven cities distributed around the world are selected as sources and destinations, and six bidirectional flows are established22as shown in Table 3.

5.2.Simulation result analysis

In order to evaluate the traffic overhead optimization effect of the CMVIP,five different traffic density models are introduced under a 1152-satellite constellation.Meanwhile, comparisons are performed with the Virtual-Topology-based Dijkstra Shortest Path (VT-SP) algorithm23.

To more realistically verify the routing scheme, two different traffic services are simulated separately.The delivery loss ratio for access services is shown in Fig.7.The maximum delivery loss ratio of the CMVIP is below 0.1 % in the 1152-satellite constellation.The results indicate that the routing strategy maintains effective data transmission and keeps a high delivery success ratio as the traffic density increases.

The delivery loss ratio for bearer services is shown in Fig.8.Except for l = 29, the maximum delivery loss ratio of the CMVIP is below 0.1 % in the 1152-satellite constellation.In reality, the density of bearer services is much lower than that of access services.That means l smaller than 29.The results indicate that the routing strategy maintains effective bearer services and keeps a high delivery success ratio as the traffic density increases.

Average Relay Throughput(ADT) is an important parameter reflecting the communication ability.The ADT for access services is shown in Fig.9.The ADT of the CMVIP increases linearly with an increase of the traffic density,and it is greater than 500 Mbps.That indicates that the communication ability of the CMVIP is excellent.Although the ADT of the VT-SP also increases, compression occurs in a high traffic density.

The ADT for bearer services is shown in Fig.10.The ADT of the CMVIP increases linearly with an increase of the traffic density, and it is greater than 50 Mbps.Similier compression occurs in a high traffic density for the VT-SP.Because bearer services transmit packets through multi-hop relays, under the same bandwidth,the ADT of bearer services is lower than that of access services.

Table 2 Simulation network parameters.

Table 3 D2D bidirectional flows.

Fig.9 Average relay throughput for access services.

Fig.10 Average relay throughput for bearer services.

Latency is another important parameter for validating the routing scheme.In this paper, a lot of access services and bearer services with different traffic densities are introducesd as the simualtion background.The flows in Table 3 are introduced as simulation objects.In Fig.11, the maximun average delay of the CMVIP is below 250 ms.The results indicate that the latency of the CMVIP is very low, and the global D2D achieves low latency performance.The latency performance of the CMVIP is far better than that of the VT-SP.

Average Delay Jitter (ADJ) is an important indicator to measure the transmission stability.Under the same settings,the simulation of the average delay jitter is shown in Fig.12.The maximun ADJ of the CMVIP is below 50 ms.The results indicate that the CMVIP achieves a very stable communication capability.

Fig.11 Average delay for D2D services.

Fig.12 Average delay jitter for D2D services.

This paper compares and analyzes two routing schemes in different traffic densities.The overall performance of the CMVIP is better than that of the VT-SP.

6.Conclusions

The dynamic topology feature of an NTSN leads to new challenges for an efficient routing scheme.Existing topology models lack the synchronous continuity of time and space, and many routing algorithms are not fully compatible with the models.Some traffic models used for simulation lack realism.To solve these issues, firstly, a compass time-space model is proposed.By this model, Inter-Satellite-Link (ISL) transmission and Ground-Satellite-Link(GSL)access can be effectively expressed.Secondly,a routing algorithm optimized for QoS is proposed.Based on this algorithm, a set of multipath routes can be obtained.Finally, a traffic model that takes into account both access and bearer services is proposed.

Simulation results validate the effectiveness of the proposed CMVIP scheme under different traffic densities.Many simulations also demonstrate superior QoS performance in comparison with the VT-SP routing algorithm.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

This research was funded by the China State Key Laboratory of Robotics(No.19Z1240010018)and the office of the Military and Civilian Integration Development Committee of Shanghai, China (No.2019-jmrh1-kj3).