Because of its wide area coverage and high reliability, satellite communication system is playing a more and more important role in all aspects of social development and national life. Major countries in the world are also competing to deploy space infrastructure and build space-based communication networks. With the deep integration of satellite communication system and Internet, Satellite Internet has become an important part of space-based information transmission system. Large scale satellite constellation systems such as Starlink and oneweb, which have been rapidly promoted in recent years, are typical representatives of Satellite Internet. As the structure of Satellite Internet becomes more and more complex, the scale and investment become larger and larger. How to give full play to its potential and carry out its application efficiently is an important topic in the field of Satellite Internet. Routing technology is not only the basic technology to ensure the interconnection between nodes of Satellite Internet, but also an important research direction of Satellite Internet.

The space nodes of Satellite Internet often contain multiple LEO satellites. There is high-speed relative motion between these LEO satellites and between satellites and the ground, which makes the whole network topology have time-varying characteristics. Therefore, the routing strategy based on static topology commonly used in ground network can not be directly used in Satellite Internet. Early satellite networks mainly adopted "snapshot technology"

[1-2] to realize on-board routing and forwarding, that is, the centralized routing mechanism based on virtual topology, calculates and generates the forwarding table of each time slice on the ground, stores the forwarding tables in all time slices on the satellite, and updates them regularly. With the increase of the number of satellites, it brings great challenges to the static discrete-time slice technology based on virtual topology. Therefore, frequent link switching will lead to a sharp increase in the scale of routing tables stored and maintained on the satellite. In order to solve the problem that the on-board routing table is too large, the satellite relative position information can be used, so the satellite relative position in the same orbital altitude can be used for routing addressing [3].

Similarly, using the idea of location and adopting the IP addressing strategy based on geographical location information addressing, the location information of the destination address can be obtained by using the IP address, and its relative orientation can be calculated. Its optimal forwarding interface can be obtained at the spatial node for data packet forwarding, which does not need the exchange of status information between neighbors [4], which can reduce the signaling overhead in the satellite network. The above only briefly describes the current satellite network routing research. The subsequent part of this paper will summarize the satellite internet routing technology, systematically summarize various routing strategies based on satellite network, and take this as the main line to introduce the research status and future development direction of Satellite Internet routing.

As an information transmission system derived from satellite communication network, Satellite Internet is similar to conventional satellite communication network in system composition, including space segment, ground segment and user segment. The system structure of satellite communication network is shown in Figure 1.

Fig. 1 system structure of satellite communication network

The space segment is composed of communication satellites. The satellite's orbit can be divided into Leo (low earth orbit), MEO (medium earth orbit), geo (geostationary orbit) or IGSO (inclined geosynchronous orbit). According to the different types of on-board loads, the communication satellite can adopt the working mode of transparent relay or on-board processing.

The ground section includes gateway station, network management center, Internet access and other functional entities. The user segment includes various user terminal equipment and support facilities for application scenarios.

With the deep integration of satellite communication network and ground network, especially 5g mobile communication system, as a system, the overall consideration of satellite communication network and 5g mobile communication network is an important direction of information network in the future. In addition, the construction of China's heaven earth integrated network is also advancing steadily. The system structure of heaven earth integrated network is shown in Figure 2 [5-6].

Figure 2 system structure of heaven earth integrated network

The network structure of Satellite Internet is complex and involves many network entities. The primary solution is the interconnection between nodes in the network. Therefore, routing technology is an essential technology to ensure reliable and efficient transmission of information in Satellite Internet, and it is also the main content of this paper. In terms of space segment architecture, the network can be divided into single-layer and multi-layer constellation structures, which will be discussed separately in this section.

The space segment satellites of the single-layer constellation system are deployed at the same orbital altitude and are composed of one or more orbital planes. Each satellite is generally equipped with inter satellite link, which can communicate with adjacent satellites on the same orbit plane and different orbit plane. At the same time, the satellite can interact with the ground gateway station and the user station respectively through the feed link and the user link, so as to form a complex heaven earth communication system with multiple links. Its structure is shown in Figure 3.

Fig. 3 single layer constellation satellite internet structure

In the research of routing strategy based on single-layer constellation system, spaceThe constellation of the segment is often LEO constellation, including celestri like constellation [7-8], Globalstar like constellation [9], iridium constellation [10], etc. these constellations are composed of multiple orbital planes and dozens of satellites. For satellite nodes in the constellation, their connectivity will be fully considered. Each node often has four inter satellite links interconnected with the nearest four neighbor nodes, including two neighbor nodes in the same orbit plane and two neighbor nodes in different orbit planes [7-8, 11-12]. In addition, some studies only consider the single-layer constellation composed of multiple geo satellites [13].

Due to the high-speed relative motion between LEO satellites, the spatial topology composed of satellite nodes will change with time. The time-varying characteristic of this topology is an important factor to be considered in the design of routing algorithm. In order to shield the dynamics of spatial topology and make it transparent to the upper layer, the concept of virtual node can be adopted [9,14], so that the routing algorithm on satellite network can be carried on a virtual network with fixed topology, which is convenient for the algorithm design of routing layer. In addition to the idea of dynamic shielding, there are also studies to make use of the characteristics of the constellation, such as the quasi invariant characteristics of the tilted delta LEO constellation, adopt the location-based routing strategy, and solve the dead angle problem [11]. The dead angle is due to considering the inter satellite switching overhead in order to get the service of the same satellite for the longest time, The access of the ground station is not necessarily the destination unreachable problem caused by the nearest satellite. Although the spatial node topology is time-varying, considering the end-to-end delay in the system whose change interval is much greater than hundreds of milliseconds, some studies still adopt the flooding strategy in the route discovery stage, and use the cooperation of ground stations to reduce the requirements for on-board storage [9].

Unlike many traditional routing studies that use the predictability of satellite operation and adopt the time discrete graph model, Li et al. [15] proposed a temporal grid model (TNM) to describe the time-varying topology of large-scale small satellite system. The idea is to divide the whole space into small space, i.e. grid, and the satellite can be located in the grid, Instead of using the coordinates of each satellite, a network topology is constructed to adapt to the routing of random services. Similar to the idea of grid partition, Na et al. [10] used the geographical coverage characteristics of LEO satellite to partition the region, quantitatively analyze the ground traffic, and use the machine learning method to predict the satellite traffic, so as to provide reference for the design of routing algorithm.

The space segment of multi-layer constellation system is composed of satellites with different orbital heights. Different systems may have different combinations, such as multi-layer Leo, LEO / GEO, GEO / MEO / LEO hybrid constellation, etc. the satellite internet system structure based on multi-layer constellation is shown in Figure 4.

Fig. 4 Satellite Internet system structure based on multi-layer constellation

Because the multi-layer constellation system has a more complex space segment structure, the routing design in the network will have different considerations. Multilayer space segment structures include LEO / MEO double-layer structure [16-17], LEO / geo double-layer structure [18], MEO / IGSO double-layer structure [19], LEO / MEO / geo three-layer hybrid structure [20], etc. The multi-layer spatial structure brings more freedom to the design of routing strategy, and the strategies of routing design are more diverse. For example, the division of labor is based on distance. For short distance, only Leo layer is used for routing, while for long distance, MEO layer is used for routing [16]. The cooperation between multi-layer satellites can also be based on the delay or link congestion. The routing strategy adopted by Jiang et al. [18] is that the inter satellite link between geo and Leo will be activated only when the hops of Leo routing exceed the threshold (the threshold is determined according to the end-to-end delay) or blocking occurs, and then the geo layer will join the routing.

In the multi-layer space segment structure, there are a large number of satellites. When studying the routing strategy, grouping can be used for management. Yi et al. [19] took the MEO / IGSO hybrid constellation as the space segment and divided the satellite nodes into three groups. All MEO satellites on the same orbital plane belong to one group, and each IGSO satellite belongs to one group according to the spatial relationship, The three groups form a super group, all under the management of the ground control center. Each group will select a cluster head according to its distance from the ground control center, and the others will be members of the group. The interaction between the group and the ground control center shall be through the cluster head. In terms of management, all nodes in the space act as a member node of the ground control center. In fact, the system adopts a centralized routing strategy based on dynamic grouping.

In addition to grouping, due to the hierarchical structure between spatial nodes, the way of division of labor and cooperation at each layer can also be used to realize the spatial routing strategy. For the multi-layer space segment satellite system composed of Leo, MEO and geo satellites, considering the large number of LEO satellites, Akyildiz et al. [20] grouped LEO satellites, regarded each group as a node, and adopted the concept of logical location to isolate the mobility of LEO satellites from the upper layer protocol, so that the upper layer protocol design does not consider the mobility of Leo, The decoupling between the upper and lower layers of the protocol is realized. The geo layer hides the specific topology of Leo, which can reduce the computational complexity and make the calculation of routing table easier. GEO Satellite adopts the shortest path algorithm to calculate the routing table in the network and distribute it to MEO satellite. MEO satellite creates a routing table for LEO satellite and distributes it to LEO satellite, so as to establish the routing information of the whole space network.

Some new network structure technologies in recent research can also be appliedFor multi-layer satellite networks, such as SDN (Software Defined Network) technology. Wang et al. [21] proposed an SDN architecture based on GEO / MEO / LEO three-layer space segment, in which GEO, as the top-level control node, is responsible for calculating the optimized communication link and resource scheduling. As an auxiliary path, MEO satellite helps GEO Satellite collect information about targets on the ground and near LEO satellite. LEO satellite is responsible for receiving commands from GEO satellite and performing information forwarding function.

In addition, in recent years, as a hot research field, the heaven earth integrated network often has a multi-layer spatial structure, so its routing problem is also discussed in this section. The system architecture proposed by pace et al. [22] is a heaven earth integrated network including ground layer, middle layer and satellite layer. The proposed routing algorithm is to find a group of candidate paths with minimum hops and select the path with minimum congestion as the final routing path. Therefore, the routing problem is transformed into an optimization problem, that is, to minimize the use of the busiest link and achieve network load balance. Yang et al. [23] Aiming at the problem that the routing protocol successfully applied on the ground can not operate effectively in the integrated network of heaven and earth, using the predictability of satellite motion, proposed the concept of topology discovery sublayer to avoid the transmission of a large number of routing messages.

Compared with the terrestrial communication network, the network topology of Satellite Internet is time-varying, and the on-board storage, computing and power are limited. Therefore, the existing terrestrial communication network routing strategies can not be directly applied to the satellite communication network. Many studies have carried out corresponding routing strategy exploration according to the characteristics of the satellite network [24]. Satellite routing algorithms generally take some key performances as considerations, such as delay, bandwidth, data packet loss rate, robustness and resource utilization. These key performances will be classified and discussed in this section.

The research of Satellite Internet routing strategy often takes single or multiple performance as optimization objectives, which are related to the QoS (quality of service) often required by specific services, such as delay, bandwidth, data packet loss rate and so on.

Delay often refers to end-to-end delay in routing research. Delay minimization is the optimization goal of many routing strategies. In addition, if service QoS requires delay, the total end-to-end delay needs to meet this requirement, which can be expressed as

Where p (SRC, DES) represents a planned route from source to destination, which can be composed of multiple single hop links; (U, V) represents a single hop link, and the start and end nodes of the single hop are represented by u and V respectively; D (U, V) represents the end-to-end delay of the link (U, V); D represents the required end-to-end delay constraint of the whole route.

If the service QoS puts forward bandwidth requirements, the link available bandwidth between each hop in the route cannot be less than the bandwidth requirements, which can be expressed as

Where band (U, V) represents the available bandwidth of the link (U, V); Bmin represents the minimum bandwidth constraint required for the entire route.

In the process of data packets from the source node to the destination node, data packets may be lost due to channel interference, queuing timeout and other reasons. The ratio of the number of data packets lost to the total number of transmitted data packets is the data packet loss rate. QoS of different services generally have different requirements for data packet loss rate. For example, the data packet loss rate of data transmission service is usually lower than that of voice transmission service.

An obvious difference between Satellite Internet and terrestrial network is that the transmission distance between nodes is long. For example, GEO satellite is about 36000 km away from the ground, and the round-trip propagation time of signal between satellite and earth is about 240 Ms. Although LEO satellites are relatively close to the earth, the earth area covered by a single LEO satellite is relatively small, and the service time at the selected location is only about 10 minutes. Therefore, it is necessary to constantly switch between LEO satellites. In addition, with the increasing scale of Satellite Internet, the on-board processing time will also increase. Therefore, in order to reduce the transmission delay of information in satellite networks, there have been many satellite network routing studies aiming at low delay.

The more direct way is to select the end-to-end path with the least delay to calculate the routing table, such as MLSR (multi-layered satellite routing algorithm) algorithm for multi-layer satellites [20].

For LEO satellite constellation, due to the relative motion between satellites, the inter satellite link has a life cycle. DLRA (double layered satellite network routing algorithm) [16] takes the remaining life cycle of inter satellite link into the weight function of path based on MLSR algorithm and LEO / MEO double-layer satellite network, To calculate the optimal path considering both delay and stability. Bdsr (bandwidth delay satellite routing) algorithm [25] takes into account both delay and bandwidth. When the link bandwidth is overloaded and the change of average end-to-end delay is constrained, it will select another link with more remaining bandwidth. With the increase of running time, the end-to-end delay gradually decreases and the average minimum bandwidth slowly increases.

The link state is the basic information required by the routing strategy. In order to reduce the overhead and convergence time of the link state based routing algorithm, SLSR (satellite network link state routing) satellite network link state routing algorithm [26] uses the characteristics that the spatial propagation delay is predictable and can be calculated in advance. Therefore, only the uncertain on-board queuing delay Real time status acquisition for link and node faults. For the routing strategy focusing on finding the path with the minimum end-to-end propagation delay, with the increase of satellite network traffic, there may be high data packet loss rate and long queuing delay, The queue state based dynamic routing mechanism QSDR (queue state based dynamic routing) of NGEO (non geosynchronous earth orbit) satellite network based on queue state [27] uses the routing model of satellite real-time queue state to adjust the pre calculated route, so as to send data packets as soon as possible and avoid congestion at the current node, All satellites in the network leave more space for receiving data packets from adjacent satellites, which reduces the queuing delay to a certain extent.

Delay is often an index requirement in QoS. In addition, it also includes bandwidth, delay jitter, data packet loss rate, etc. Taking time delay jitter as an example, one of its causes is that in LEO satellite networks, satellite motion frequently changes the relative positions of satellites belonging to different orbits, resulting in time delay jitter in inter satellite links. Different application scenarios have different QoS requirements. According to the quality of service requirements of multimedia applications, Rao et al. [8] used genetic algorithm to realize the QoS routing of inter satellite links, and proposed a multi-path inter satellite link routing (mpir) strategy suitable for LEO satellite networks, The strategy has good QoS guarantee in terms of delay jitter and call blocking probability constrained by bandwidth and delay.

However, the challenge is the complexity of the algorithm, especially when LEO satellite resources are limited. Liu et al. [17] introduced a heuristic routing algorithm and proposed a new predictable satellite network routing protocol (psnrp) to meet the quality of service requirements of network users and obtain better routing performance. In terms of adaptive QoS routing, Yan et al. [28] proposed an adaptive based dynamic routing (sradr, status and reputation adaptive routing) algorithm for satellite network status and reputation, introduced the security attribute represented by node reputation, and carried out route discovery and dynamic update maintenance according to the network status and node reputation value, Make the selected path a safe path with good comprehensive performance and state.

As an information transmission network, the data packet loss rate of Satellite Internet is often an important indicator in QoS. Zhang et al. [29] aimed at the sharp increase of data packet loss rate caused by satellite ground link switching, based on static routing and dynamic routing respectively, Two optimization strategies, source preplanning calculation (SPPC) and destination readdressing calculation (DRAC), are proposed to alleviate the problem of data packet loss. However, SPPC can not solve the handover interruption caused by random delay, and has high requirements for anti congestion of network transmission. Although DRAC can solve unknown network congestion, the cost is additional routing overhead.

Due to the circular visibility and orbit fixity of satellite orbit, Satellite Internet is vulnerable to attack and interference [30]. In addition, affected by the space environment, the aging of devices or the need for frequent updates of satellite technology, the satellite will fail, and its related inter satellite links will be broken, resulting in changes in satellite network topology. Therefore, improving the anti-interference ability and robustness of the network is also the focus of Satellite Internet Routing Research in recent years.

Table 1 key performance considered by some routing strategies

Aiming at the problem that the offline routing algorithm of MEO / LEO satellite network can not adapt to unpredictable topology changes, Li et al. [31] proposed an anti destruction dynamic routing algorithm, which divides the satellite network into multiple clusters, optimizes the switching effect by adopting the boundary satellite source routing scheme, and enhances the system survivability in case of inter satellite link failure. Because the invulnerable dynamic routing algorithm needs to update the link state, it will produce additional transmission overhead. On this basis, the author further proposes an invulnerable routing algorithm for LEO satellite networks [32], in order to automatically avoid invalid inter satellite links and reroute at the least cost.

In order to cope with the variability of the network, Fang et al. [33] proposed a multi orbit hybrid satellite network routing algorithm based on detection and self-learning to solve the uncertain factors caused by the change of satellite network topology. Due to its distributed operation characteristics, it has good anti attack ability. To combat the variability of topology, it is often necessary to increase the system overhead to update the routing information. Pan et al. [34] proposed a new routing protocol opspf (orbit prediction short path first routing) for LEO satellite networks and an on-demand dynamic routing mechanism, which can reduce the communication overhead and routing convergence time in case of irregular topology changes. In the face of many factors affecting system robustness, such as unknown interruption, sudden congestion and intelligent interference, a more intelligent routing scheme is needed. Han et al. [30] proposed an anti-interference routing scheme for heterogeneous Satellite Internet based on game theory and deep learning, and modeled the routing anti-interference problem as a layered anti-interference Stackelberg game, The routing strategy has low overhead and good anti-interference performance.

Due to the high-speed mobile characteristics of satellite nodes, when satellite Internet operates over densely populated areas and sparsely populated areas, the network resource traffic distribution is extremely uneven. Instantaneous excessive traffic will cause satellite network node congestion, increase the network queuing delay, and then lead to the decline of the routing performance of the whole satellite network. In addition, due to the scarcity of orbit resources and the high cost of satellite launch and deployment, system resources including satellites should be used efficiently, which is also the focus of routing technology research.

Network congestion will lead to data packet loss and reduce the system throughput, which is not conducive to the efficient use of network resources. Ma et al. [11] proposed a distributed datagram routing algorithm suitable for LEO satellite networks. When selecting the next hop satellite node, its congestion state is considered. Therefore, the routing strategy is conducive to congestion processing and reducing delay, and can improve the success rate of data transmission in case of node failure. Yi et al. [19] proposed a centralized routing strategy of on-demand computing and caching for MEO / IGSO satellite network, designed a routing algorithm for dynamic grouping of satellite network topology, and divided data transmission routing calculation into three stages: direction estimation, direction enhancement and congestion avoidance, so as to make satellite network configuration more flexible, transmission more efficient and easy to manage.

Load balancing can balance the information transmission in the intra network link, which is conducive to improve the throughput of the whole system and avoid congestion. Li et al. [27] proposed a dynamic routing update algorithm based on real-time queue state and routing state model to balance the traffic load, ensure that each satellite sends data packets as soon as possible and avoid the congestion of the current node. Wang et al. [21] proposed two routing algorithms to optimize the number of inter satellite links. By scheduling low priority traffic to the links used by high priority services, the number of links used by low priority traffic is reduced. At the same time, the load balancing strategy is introduced to control the aggregation of network flows to reduce the total number of links used, so as to improve the resource utilization of satellite networks, energy conservation. However, in the case of dense orbits, the topology strategy of the reverse link can increase the number of inter satellite links and reduce the traffic on each link, which can contribute to higher and more stable network capacity performance [35]. Therefore, the strategy of reducing the number of links should be determined according to the specific situation.

Computing power is a valuable resource of Satellite Internet, especially for satellites as space nodes. The size, weight and power consumption of satellites limit their computing power, so it also poses higher challenges to routing algorithms. In order to meet the requirements of satellite storage and processing capacity, Zhang et al. [36] proposed a routing table generation and update algorithm, which assigns the routing calculation of satellite network to on-board router and ground router to complete, and generates LAN routing table and whole network routing table respectively. The algorithm can reduce the requirements for satellite computing power and reduce the burden of inter satellite links, and the ground router can also be upgraded with the expansion of satellite network. In addition, based on the combination of pre calculation and distributed on-board real-time calculation, and considering the real-time inter satellite link state, the routing and forward table of the next hop of the target on each satellite can also improve the real-time performance and reduce the on-board computing load [37-38].

In order to improve the resource utilization efficiency of the system, the routing overhead in the system should be as small as possible. The geographic location-based method [39-42] can be used to divide the satellite network and the earth into multiple domains, which can effectively reduce the size and generation time of the routing table in the large-scale satellite Internet, maintain the stability of the routing table when the user conditions change, and greatly reduce the routing overhead.

The routing strategy of Satellite Internet can generally be modeled as an optimization model, but it is often a multi-objective optimization problem. With the increase of the scale of satellite network, its computational complexity also increases, and the search difficulty of routing space further increases. When more factors are considered, such as the optimization objectives include not only QoS requirements, but also time-varying satellite network link states, interference and other factors, it will further increase the difficulty of routing. Traditional routing design schemes are usually based on artificial modeling of network traffic characteristics, and on this basis, targeted routing strategies are designed. However, the current network traffic has complex temporal and spatial distribution volatility, and it is very difficult to model manually.

For example, many model-based network routing optimization studies are aimed at specific network scenarios or specific hypothetical traffic models. Due to the error caused by the assumptions and the difference between the model and the real network, the proposed scheme is difficult to achieve good routing effect in the real network scenario. However, artificial intelligence technologies such as machine learning (ML) can usually automatically extract the characteristics of network traffic and generate corresponding network strategies without relying on human expert experience, which opens up a new path compared with traditional schemes in solving the NP hard problem of network routing [43], Therefore, routing generation based on artificial intelligence is a promising research direction of Satellite Internet routing technology.

Since the third generation, the terrestrial mobile communication standard has tried to consider the satellite network as a whole in the process of standard formulation, but it is far from the integration of heaven and earth, and the heaven and earth network is still developing relatively independently. In recent years, with the rapid development of Satellite Internet, the trend of integration of heaven and earth has become more and more obvious. As a new generation of mobile communication, 5g network has higher openness in architecture. It is also known as the network composed of networks [44], which provides a technical basis for the integration of satellite network and ground network. As the next generation network system, the main institutions of 6G network are carrying out system definition and key technology verification. As an important feature of the future 6G network, the integrated development of heaven and earth has been widely recognized. Therefore, the interconnection between satellite network and ground 5g / 6G network is an inevitable requirement.

The routing mechanism based on virtual topology of conventional LEO satellite network is difficult to integrate with the ground routing mechanism, because the former uses satellite identification and inter satellite connection to generate routing information. When integrating with the ground network based on IP routing, two routing mechanisms are required, And the former is required to timely update the stored information of on-board routing according to the current ground user connection, which will produce considerable on-board maintenance overhead and aggravate the on-board resource pressure. Due to the high-speed movement of the satellite, the connection relationship between the satellite network and the ground network is constantly changing. Changing the access satellite in the traditional IP logical addressing mechanism will lead to the change of the terminal IP address and trigger the binding update. Frequent binding updates will consume a lot of on-board communication resources [4]. All these put forward very high requirements for the routing design of heaven earth integrated network, and make the world wide routing become a new research direction.

In recent years, the scale of space nodes of Satellite Internet shows the characteristics of multi-level and large-scale deployment. The scale of satellites of various constellations ranges from dozens to tens of thousands. The emergence of giant constellation system has greatly improved the ability of space network and can provide users with services compared with terrestrial network. The huge node size of the giant constellation brings great challenges to the routing mechanisms based on virtual topology such as "snapshot technology" commonly used in constellation routing. Since the number of time slices obtained by topology segmentation is directly proportional to the number of link switching, the expansion of the constellation size will lead to a sharp increase in the number of routing tables to be stored and maintained on the satellite, It not only challenges the satellite network with limited on-board resources, but also opens up a new research direction for space routing technology.

As an information infrastructure, Satellite Internet has strong penetration and driving. It will greatly change the way of information acquisition in the global society and become the driving force of social transformation and innovative development. As one of the basic technologies of Satellite Internet, routing technology is the key technology to realize efficient utilization of space resources, integration and interworking of heaven and earth, and service carrying support. Focusing on the interconnection requirements between satellite network nodes, this paper summarizes the research status of routing in satellite information transmission network, and discusses the challenges and further research direction of Satellite Internet routing technology.

This content comes from the network / satellite and network exhibition. This website only provides reprint. The views, positions and technologies of this article have nothing to do with this website. If there is infringement, please contact us to delete it!