Load Balancing Routing Algorithm Based on Extended Link States in LEO Constellation Network

Chaoying Dong,Xin Xu,Aijun Liu,Xiaohu Liang

College of Communications Engineering,Army Engineering University of PLA,Nanjing 210007,China.

Abstract: As an important part of satellite communication network,LEO satellite constellation network is one of the hot research directions.Since the nonuniform distribution of terrestrial services may cause inter-satellite link congestion,improving network load balancing performance has become one of the key issues that need to be solved for routing algorithms in LEO network.Therefore, by expanding the range of available paths and combining the congestion avoidance mechanism, a load balancing routing algorithm based on extended link states in LEO constellation network is proposed.Simulation results show that the algorithm achieves a balanced distribution of traffic load,reduces link congestion and packet loss rate,and improves throughput of LEO satellite network.

Keywords:LEO satellite; routing algorithm; congestion avoidance;load balancing

I.INTRODUCTION

In recent years, satellite communication networks have developed rapidly.As an important part of the“air −spaceintegration” information network [1],satellite networks can not only supplement the ground network of 5G systems, but also provide services for oceans, remote and polar regions.It can also provide users with a better service combining with technologies such as artificial intelligence,big data,and the Internet of Things.LEO satellite constellation has been one of the hotspot research field of satellite communication due to its low transmission delay,low propagation loss and global coverage.Due to non-uniform distribution of ground users and the need for high-quality transmission with larger data volume and more user services in the future, the load balancing problem of LEO constellation network has become one of the key issues.

In this paper, we consider a network composed of LEO satellites with Inter Satellite Links(ISLs).To transmit data in such a network,routing has to adapt to link dynamics.For example, GSLs will vary notably as satellites move along their orbits,accompanied with link handovers.The paths need timely adjustment to such link changes.Meanwhile, a LEO satellite is a source node as well as a relay node.Routing algorithm ignoring traffic load will lead to network congestion and poor network performance.

Therefore, it is essential for routing algorithms to be responsive to both load variation and link state changes.In light of this, we take the DSP algorithm as a start, which is known to deliver packets via the shortest path which leads to low latency.However,practical issues, such as node congestion, could impede its application.Thus we investigate the congestion avoidance mechanism for satellite networks and design a routing algorithm that not only exhibits high throughput, but also delivers packets with reasonable end-to-end delay.Our contributions are summarized as following.

• We propose a load balancing routing algorithm based on extended link states(LRES).This algorithm not only maintains the optimality of path set, but also reduces congestion probability of links;

• We design an adaptive congestion threshold setting mechanism.This mechanism can better adapt to the change of traffic load;

• We come up with a link congestion status notification mechanism and a rerouting mechanism,which integrate active discovery and automatic detection.The timeliness of link state acquisition is guaranteed with a small overhead.

The rest of the paper is organized as follows:In Section II,we discuss some related work.Section III describes our system model and problem formulation.In Section IV, we define the node congestion threshold,propose a node state notification and rerouting mechanism,then introduce the load balancing routing algorithm based on extended link states(LRES)method.In Section V,we discuss parameters selection,and analyse the simulation results.Finally, paper is summarized in Section VI.

II.RELATED WORK

From the perspective of system design, the length of the inter-satellite links of low-orbit satellites varies with the latitude.The traditional shortest path algorithm only relies on the path length to determine the forwarding path, which may cause business aggregation in high latitude areas [2][3].The uneven distribution of ground gateway stations around the world is also an important reason for the unbalanced load of the satellite network.At the same time, from the application point of view, the satellite constellation network can achieve global coverage, and due to the global population distribution and user mobility,it can also cause the uneven distribution of traffic around the world[4].

To solve this problem, the low-orbit satellite constellation routing must be able to select different paths,which are light−loaded.Roy[4][5]proposed a pathbased minimizing maximum flow routing method to achieve flow balance.The algorithm assumes that all inter-satellite links have the same length and give all paths the same priority for selection, thus avoiding the concentration of traffic in high latitude areas.According to the relative relationship between the gateway and the reverse slot, Wei [6] dynamically divided the satellite network into light-loaded and heavy-loaded areas, meanwhile, defined different congestion indexes for the heavy-load areas,and used the smallest weight path to solve the problem of uneven global traffic distribution.However, the routing decision relies on the link information of the entire network,which could not adapt to traffic changes well.

ELB[7][8] implements load balancing by actively exchanging congestion status information between nodes to prevent congestion.Each node marks satellite nodes as busy or idle state according to the occupancy of the queue.When a node enters busy state,it sends a corresponding signal to the neighbor node to reduce its sending rate.When TLR[9]sends packets,it not only considers the congestion state of the current output link, but also considers the possible congestion state of the next-hop satellite node.According to DTD [10] [11], satellites make independent decisions to detour part of the traffic from the default route to an alternative route.The DTD method allows satellites to provide real-time responses to congestion only by considering the link status of local and nearby satellites.However,for a group of satellites carrying a large amount of traffic,DTD may lead to local optimization and cascade congestion.

Although the above algorithms can balance the network load to a certain extent,there are still local optimization problems.Packets cannot completely detour around congested nodes during transmission.In order to solve this problem, this paper proposes the LRES algorithm,which try to avoid congestion on the entire data transmission path,thus achieving near global optimization and network load balancing.

III.SYSTEM MODEL AND PROBLEM FORMULATION

3.1 Constellation Model

The constellation network topology is based on the Iridium-like system[12]as the prototype,and uses the polar orbit constellation model [13].The constellation consists of N=(Np·No)satellites,whereNois the number of orbits, andNpis the number of satellites in each orbit.Each satellite has a maximum of 4 inter-satellite links,including 2 inter-orbit links and 2 intra-orbit links.There is a gap between the two adjacent orbital planes where satellites move in opposite direction.So the ISL between adjacent orbits 0 andNo −1 will be disabled to avoid continuous tracking.In the polar regions,the inter-orbit links will be closed, therefor there are only 2 intra-orbit links.Satellites connect to the earth stations via satellite-toground link GSL in its coverage area, as in Figure 1.

Figure 1. Communication between satellite and earth station in the constellation.

In this constellation network, virtual topology [14]model is used.Within a snapshot, the network topology is considered static.

The indexiof the satelliteViis determined as the following formula:

DenoteOi ∈{0,...,No −1}as the orbital index of satellite nodeVi.Si ∈{0,...,Np −1}is the order number of the satellite nodeViin its orbit.

It is assumed that the entire earth surface can be covered by a LEO constellation, and the network topology at any time can be determined by graph G = (V,E).Among them, V ={Vi|0≤i ≤N −1}is the satellite node set, E ={Ei,j|0≤i ≤N −1,0≤j ≤N −1,ij}represents the set of inter-satellite links in the constellation network.

3.2 Node Model

There are three kinds of nodes in the constellation network,that is earth station nodeG,satellite access nodeWand other satellite nodesS.The definition is as follows:

• Earth station nodeG: All earth stations can send and receive data at any time.

• Access satellite nodeW: Earth station enters the constellation network via an access satellite node,which will be determined according to some criterias.

• Forwarding Satellite NodeS: Other satellite nodes except access satellites node in the constellation network.They can forward data.

The three kinds of nodes play different roles in the network,as shown in Figure 2.

Figure 2. Nodes in constellation network.

3.3 Link Model

Links in constellation network include the satelliteground links(GSL)and the inter-satellite links(ISL).Here, we only consider ISL link.Ei,jrepresents the inter-satellite link between adjacent nodeViandVj.Then the relationship of all satellites in the network can be expressed as:

wherei,j ∈[0,N −1].

We define the path fromVstoVdasP(Vs →Vd).Then,

SupposePK(Vs →Vd) is the set of routing paths,which included the k shortest paths betweenVsandVd.That is:

among the k paths we define the distance ofm −thpathPm(Vs →Vd)isDm(Vs →Vd),m=1,2,...,k.

Suppose the path distance is just the hop count,then

and suppose

IV.LOAD BALANCING ROUTING ALGORITHM BASED ON EXTENDED LINK STATES

4.1 Delay Definition

Let the delay of the ISLEi,jbeDelayi,j,then:

whererepresents the expected queuing delay of the linkEi,j, andrepresents the propagation delay of linkEi,j, that is, the delay includes queuing delay and link propagation delay.And

herecis the speed of light,Di,jrepresents the physical distance ofEi,j,andDi,jremains constant within a topology snapshot,hence it can be calculated in advance.qEi,j(x) is the queue length ofEi,jat timex,Pavgis the average packet size, andBEi,jis the ISL link bandwidth.

In order to meet the minimum latency requirements of services, it must satisfy the following condition when selecting paths:

That is, the sum of the delay of ISL pathP(Vs →Vd) and the uplink/downlink must less than the minimum delay requirements of services.

4.2 Link Congestion Threshold

In order to avoid congestion, we defineQthas the node queue length threshold.Once the queue length of the node reaches or exceedsQth, we consider that the node is in a congested state.

According to[2],the queue length of satellite nodeViat timetisQi(t), the maximum queue length isQR, andQi(t)≤QR.Then after timetd, the queue may be full, the satellite node will drop packets.The residual time of losing packettdis:

whereIiis the traffic rate when packets flowing intoViandOiis the traffic rate when flowing out ofVi.

By using K Shortest Paths( KSP )[15] algorithm,there arekpaths from source nodeVsto destination nodeVd.The path set isPK(Vs →Vd), and the corresponding distance set isDK(Vs →Vd).If data fromVscan successfully arrived atVd, that is,packets can successfully arrived at any node on the pathPm(Vs →Vd)which selected as the transmission path, there is no packets losing occurred.It means that the data transmission time fromVsto any node on the pathPm(Vs →Vd) is less than the residual timetdof losing packet for the corresponding node.Suppose all ISL links have the same propagation delay,and we defineas the reference value, of whichnis the hop count fromVsto a node on the pathPm(Vs →Vd),1≤n ≤Dm(Vs →Vd).

According to the definition ofγ, the bigger valueγis, the higher the probability of packet losing is.We take the maximum value ofγfor all nodes on the pathPm(Vs →Vd)as reference,thus that we can compare the losing probability of each path in the setPK(Vs →Vd).In detail,

Then,the packet losing probability for a path can be defined as the following,

And the congestion thresholdQthfor a link can be defined:

In other words,when the packet loss rate of a satellite node is large, the congestion threshold will be small;and when the packet loss rate is small,and when the congestion threshold will become large.According to this mechanism,Qthwill be changed alone with the packet loss probabilityp,hence packet can detour around a heavy-load satellite node in advance especially in heavy-load situation.

In order to make the traffic more balanced,we suppose that whenQi(t)≥α ∗QR, the satellite nodeVienters into the congested state, and whenQi(t)≤β ∗QR,the satellite nodeViexits the congested state.And, usuallyα > β.Refer to[16]and takeα= 0.8 andβ=0.75.

4.3 Link Congestion Status Notification Mechanism

According to the design principle of the LRES algorithm,packets are routed on the path without congestion nodes.Therefore, it is necessary to collect node information on the corresponding path.For this reason,a link congestion state(LCN)notification mechanism is proposed.It combines active state discovery with an automatic congestion state release mechanism to realize the link state interaction with lower overhead.

In the LCN mechanism,in order to reduce signaling overhead, only node congestion state information on limited paths are collected.And there is a link states table in every nodes to record the link congestion state.Once a node receive the link congestion notification,it will update the table.The node state information collection process is divided into the following two parts.

• Active state discovery mechanism: (1) The source node calculates several paths from source node to destination node.A actively sends state request messages on the first 2 shortest paths to collect link congestion state information to limit the overhead.Whenever these paths occur congestion, then switch to the following shortest paths to collect state.(2)Congestion status information feedback:The nodes on the corresponding path determine the link congestion status based on the comparison result of the link queue length.If it is in a non-congested state,busy= 0 is set, as shown in Figure.3(a); if the link is congested,busy= 1 is set,as shown in Figure.3(b).Once the congested link end node or its neighbor nodes ( which have received messages from the congested link end nodes through the automatic state congestion publishing mechanism ) receive the state request message from the source node,the request message is converted into feedback which carry the congestion state information and returns to the source node immediately.

• Automatic congestion state release mechanism:In addition to the data source actively collecting link state, whenever the queue length on a link exceeds the congestion threshold, the state is notified to the neighbor nodes of the two nodes at both ends of the congestion link,without any further state flooding,as shown in Figure 4.

Figure 3. Active state discovery mechanism.

Figure 4. Automatic congestion state release mechanism.

Consequently, Link congestion state notification mechanism is based on extended link states, and it combines on-demand and passively triggered notification mechanism.Hence it can greatly reduce the signal overhead.

On the other hand, no matter whether the items in link states table reflect the current state of links along the path,the source node will still make the routing decision according to these items.That is to say, it will choose the path along which there are no congested links and update the route table.

4.4 Delay Analysis of Link State Feedback

Due to the relatively long delay of the ISL, the network node usually has a lag in obtaining the link state,which may affect the routing performance of the LRES algorithm.As shown in Figure.3(b), without considering the queuing delay,for a path of length H,the source node will obtain the link state after the average timetdelay.

Assuming that the link congestion or failure probability ispand the average transmission delay of ISL isτ,then in the case of Figure.3(b):

For mechanisms that need to obtain the link state of a complete path, the average time to obtain the link state will be:

For the orbit speaker link state update strategy in[17],then:

where, the symbol⎿」is the rounding symbol, andSiis the number of satellites in one orbit.

Based on the analysis, the impact of delayed link state on routing performance can be evaluated.First,we count the path hop distribution of DSP and LRES algorithms.In the Iridium constellation system, the maximum path hops of the two algorithms are 10 hops and 13 hops, and the average hops are 4.1 and 4.3.Therefore, we can take the average number of hops with H=5 in the formula (14)−(16).For the Iridium constellation, at different latitudes, the distance between satellites on adjacent orbits is usually not equal.However,because the inter-orbit ISL between adjacent orbits is usually only maintained below 60 degrees latitude,the distance between the orbits is about 3270 to 4480km;in addition,the distance of inter-orbit ISL in the track is about 4030km.Based on this, we can assume that the average distance of the ISL is 4000km,and the average ISL delay is about 13.33ms.Use these parameters in formula (14)−(16) to obtain the relationship between link congestion probabilitypand average link state feedback delay,as shown in Figure 5.

In Figure 5,LCN means using the link congestion state notification, Full Path means the mechanism to obtain the full path link state,Orbit Speaker means the link state update strategy of the track speaker in[17].

Obviously, the average link state feedback delay of the full-path scheme and the orbital speaker scheme independent with link congestion, the constant value of is 79.98ms and 133.3ms.For the LCN mechanism,as the link congestion probability increases, the feedback delay will first increase and then gradually decrease.Especially whenpis greater than 0.5,since the state request packet will return soon after being sent from the source, the feedback delay will be less than 10ms.(14)−(16)only includes transmission delay,but no queuing delay.During the feedback delay time,the packet will still be forwarded along the original path and may increase link congestion.From this point of view, the LCN solution can better deal with the impact of link state feedback delay.Of course, the link congestion probability is usually related to the traffic distribution in the network.

Figure 5. The relationship between tdelay and p.

On the other hand, the cost of link state exchange can also be inferred from the feedback delay.Overhead can be defined as network traffic except data flow.If the length of the state request packet isl, the overhead is (tdelay · l)/d.Therefore, the cost results of several link state exchange schemes will the same as in Figure 5, and the cost of the LCN scheme is the smallest among all.

In summary,LCN mechanism combines active state discovery with an automatic congestion state release mechanism, and only collects the link congestion states.Therefore,it can greatly reduce signaling overhead and speed up the response to link.

4.5 Rerouting Mechanism

Whenever a path encounters congestion, a new path should be chosen to detour packets.Thus,the rerouting mechanism is needed.

As shown in Figure 6, the packet is sent from the source nodeVsto the destination nodeVd,and the path isVs →Vi1→Vi2→Vi5→Vi6→Vi7···→Vin→Vd.When a link congest or fails suddenly.According to the LCN mechanism, the nodes at the end of the congestion link notify the link state information for neighbor nodes, and at the same time, the node starts the rerouting mechanism to find a new path.The process include following 3 steps:

Figure 6. Rerouting mechanism.

• Determine the position of Satellite 1 and Satellite 2.The satellite adjacent to the upstream end of the congest link along the path from the source node to the destination node is defined as satellite 1, as shown in Figure 6.Satellite 1 is the nodeVi5, and the adjacent satellite of the congestion link downstream end point is defined as satellite 2,as shown in the Figure 6,satellite 2 isVi7.

• First layer rerouting.Re-determine the next hop at satellite 1 according to the principle of the LRES algorithm.It is worth noting that in order to avoid path loops, the next node cannot be the next hop on the original transmission path,or the node that has been searched.The next node can only beVi4andVi3.

• If the satellite 1 does not find a available next hop, the 2nd layer search is carried out, that is,the rerouting node is extended to the upstream node of the satellite 1 to further expand the search range.As shown in Figure 6,ifVi2fails to search for the next hop, it will return toVi1to search,and so on.If there is no available paths could be used until message returning to the source path,the source node will still choose the first shortest path to forwarding packets.

V.SIMULATION AND ANALYSIS

5.1 Parameter Selection

The choice ofkvalue determines the number of alternative paths for the data during transmission.To a certain extent,it reflects the”flexibility”of data routing.The larger the value ofk,the more optional paths for packet transmission.However, excessivekvalue will lead to too higher complexity.In general,we take k=10.

The path selected by the algorithm needs to meettwo basic conditions: 1.The minimum delay conditionDealyth; 2.The complexity requirements.Excessivekvalue will lead to too high algorithm complexity and pressure on the computing power of satellite nodes; too smallkvalue will possibly make links entering the congestion state soon.

The Complexity of BCA-KSP isO(N2)+O(N(n·N))+O(k·pathsizemax·N).Among them,Nis the number of satellite nodes in the satellite network, andnis the number of network nodes, including satellite nodes and earth station nodes.Obviously,in order to reduce the computational complexity, the value ofkshould not be too large.The simulation is based on the Iridium system in Ns2.The specific parameters of the system and the algorithm are shown in Table 1.

Table 1. Parameters of Iridium constellation.

In order to analyze the performance of LRES in terms of congestion avoidance,simulations are mainly carried out in two scenarios.one is less-congested link scenario, and the other is multi-congested link scenario.DSP, ELB and TLR algorithm are compared in two scenarios.

Performance parameters include: average end-toend delay,network throughput and packet loss rate.

5.2 Simulation and Analysis

5.2.1 Less-congested link scenario

Choose 2 pairs of earth stations in North America and Africa, as shown in Table 2.Where packets are sent from two earth stations in the Washington DC to the earth stations in Goiania and Bahia Blanca.The parameters of the algorithm include shown in Table 3.Let the transmission rate of the earth station is 10Kb/s,20Kb/s,30Kb/s,40Kb/s,50Kb/s,60Kb/s,and simulation time is 100s.

Table 2. Source/Destination node.

Table 3. Parameters of the proposed method.

Figure 7. Total packet loss rate in less-congested link scenario.

Figure 8. End-to-end delay in less-congested link scenario.

Figure 9. Total throughput in less-congested link scenario.

The network packet loss rate are shown in Figure 7.When the transmission rate of the earth station is 0∼30Kb/s, the packet loss rate of all algorithms is 0, indicating that the network is in a light load at this time,and no packet loss has occurred in ISL and GSL.After 30Kb/s,DSP begins to lose packets and the ISL was congested.ELB, TLR and LRES just lose packets above transmission rate of 50Kb/s.It is because the path taken by DSP is always the shortest path, as shown in Figure 11.After 30Kb/s,links of 37-38,38-39, 39-50 reach the congested state.The ELB, TLR and LRES have a congestion avoidance mechanism based on queue threshold,which can detour congested satellites, as shown in Figure 11−13.When sending rate is less than 50Kb/s,there is no packet lost.When the rate beyond 50Kb/s,packets begin to loss.In this scenario,LRES,TLR and ELB remain same in terms of packet loss rate.

Figure 10. Paths of DSP in less-congested link scenario.1

Figure 11. Paths of ELB in less-congested link scenario.1

Figure 12. Paths of TLR in less-congested link scenario.1

The average end-to-end delay of the network are shown in Figure 8.When the transmission rate is less than or equal to 30Kb/s, there is no difference between the four algorithms, and they all use shortest path.After transmission rate reaches 30Kb/s,since the shortest path links are saturated,the paths selected by ELB, TLR and LRES are longer than the shortest path, hence the delay of both are lager than DSP.In the transmission rate is between 30Kb/s and 50kb/s,the end-to-end delay of ELB is much longer than that of LRES algorithm.This is because ELB implements congestion avoidance within one hop.As shown in Figure 11, when the ISL saturates, the routing path selected by the ELB is 67-37-38-49-50-69.Thus the path length is the same as the shortest path,it does not consider the state of node 50, and it is also detoured,thus the queuing delay is still long.The path selected by the LRES algorithm is 67-37-26-27-28-39-50-51-69,as shown in Figure.13,due to the longer detour,it brings a longer transmission time.Since all nodes on the path are free of congestion, the queuing delay is short.Due to the difference in queuing delay between the two algorithms, the end-to-end delay of LRES is less than ELB in the range of 30Kb/s∼50Kb/s.TLR judges the congestion of the next 2-hop node,as shown in Figure 9.Its congestion mechanism has a significant effect in 30Kb/s∼50Kb/s, and its paths distance are shorter than LRES, thus its delay is less than LRES.Above 50Kb/s,ELB and LRES detour to the new path,as shown in Figure 11 and Figure 13.Obviously, the LRES third routing path is much larger,thus its propagation delay is higher than the ELB,but detouring to the nodes 38,39,50 keeps the data away from the congestion area, which leading the network traffic to the idle area, and has a better effect of avoiding congestion, so its queuing delay is much smaller than ELB.Similarly, when rate reaches 60Kb/s, the queuing delay of TLR increases rapidly,hence,its delay is longer than LRES.As a result,LRES has improved the delay compared to ELB, and the higher the rate, the more obvious performance of LRES advantage over TLR.

Finally, the network throughput are shown in Figure 9.When the transmission rate is less than 30Kb/s,there is no significant difference.Above 30Kb/s, the throughput of DSP keeps increasing,and after 40Kb/s,it keeps around 74Kb/s.The throughput of LRES,TLR and ELB is always greater than DSP.After the transmission rate is 50Kb/s, the throughput of LRES reached the best of the three, and remains the same with TLR.

Figure 13. Paths of LRES in less-congested link scenario.1

The above results prove that the proposed LRES scheme can effectively bypass the congested satellite nodes,and improve the performance of the network by avoiding congestion based on the entire path state.

5.2.2 Multiple congestion link scenario

In this scenario, 158 pairs of nodes in six continents on the earth were selected.The number of nodes is proportional to the area of each continent.The data flow distribution ratio between the continents is set as shown in Table 4.

Table 4. Traffic distribution based on geographic location.

According to[18],specific parameters are shown in Table 5.The transmission rate range is 300Kbps∼1Mbps,and the simulation time is 50s.

Table 5. Parameters of the proposed method.

The comparison of the packet loss rate of each algorithm is shown in Figure 14.It can be seen that as the data transmission rate increases,the packet loss rate of each algorithm gradually increases.The DSP algorithm has the highest packet loss rate because there is no congestion avoidance mechanism.Whenthe transmission rate is less than 500Kb/s, the packet loss rate of ELB and LRES algorithms is 0, and the packet loss rate of TLR and DSP are greater than 0.Above 500Kb/s,all three algorithms except LRES occur packet lost.In other words, when the network is in low or medium load, the LRES algorithm can more effectively reduce the packet loss rate by detouring around congested areas.When the rate increases to 800Kb/s, the LRES algorithm begins to lose packets,but the packet loss rate is still lower than the other three algorithms.It can be seen that the LRES algorithm has better performance in avoiding congestion.Through its larger range of link congestion judgment and path selection,it can effectively avoid packet loss.

Figure 14. Total packet loss rate in multiple congestion link scenario.

Figure 15. End-to-end delay in multiple congestion link scenario.

The end-to-end delay performance is shown in Figure 15.The delay of ELB is the largest among the four algorithms.It is because the congestion avoidance mechanism of it only judges the link state within one hop,and packets may still enter the congested area after being detoured.The delay of TLR algorithm is lower than ELB and is greater than DSP.It is because the TLR algorithm will also choose the longer paths which increases the propagation delay.However,compared with ELB, the TLR algorithm is based on the two-hop link congestion state, thus the effect of congestion avoidance is better than ELB.Since the queuing delay is much lower than ELB,the average end-toend delay is less than ELB.For the LRES algorithm,in the low-to-medium load scenario, the delay is less than ELB and TLR, but greater than DSP algorithm.This is because the congestion avoidance based on extend links,and the queuing delay will be reduced,and less than ELB and TLR.However, under high load,such as the rate greater than 900Kb/s,the delay of the LRES algorithm will increase significantly.It is because most nodes in the network are in congested state at this time.LRES will choose longer paths.In addition, the state notification mechanism of LRES has feedback delays, thus the path selection may not be optimal.

Figure 16.Total throughput in multiple congestion link scenario.

In summary, in the low-to-medium load scenario,LRES algorithm can rely on its more global congestion avoidance mechanism to obtain better delay performance than ELB and TLR algorithms.Under high load conditions, the algorithm is designed to avoid congested links to reduce the occurrence of packet loss,while sacrificing part of the delay performance.

The total throughput performance is shown in Figure 16.The throughput of all four algorithms is proportional to the sending rate.At the same time, the LRES algorithm selects a detour path based on more global link state,effectively avoiding congested links,and making throughput performance better.

In addition, the throughput of each satellite node in all algorithms are shown in Figure 17-20.Comparing the above four figures, it can be seen that the throughput of the satellite nodes of the DSP algorithm are quite different.The satellite node 22 carries the highest traffic load and is much higher than other satellite nodes.That is,the network traffic is concentrated at certain nodes, the network traffic is unevenly distributed.Figures 18-20 show the throughput distribution of ELB, TLR, and LRES algorithms.It can be seen that compared with ELB and TLR algorithms,the throughput distribution of LRES algorithm is relatively more balanced.To sum up,the LRES algorithm has more advantages in the load balancing effect of network traffic, and the performance of the constellation network can be effectively improved by extending the link state.

Figure 17. The throughput of each satellite node in DSP.

Figure 18. The throughput of each satellite node in ELB.

Figure 19. The throughput of each satellite node in TLR.

Figure 20. The throughput of each satellite node in LRES.

VI.CONCLUSION

This paper introduces LRES, a load balancing routing algorithm for constellation networks based on extended path congestion avoidance.The algorithm provides better network load balancing performance by using more global link congestion information,effective congestion avoidance mechanism,and a state notification mechanism combining active discovery and automatic detection.The basic design principles and specific steps of the algorithm is discussed in detail,and the performance of the algorithm.

The simulation results show that LRES not only achieves the balanced distribution of traffic load,but also avoids network congestion more effectively.Compared with typical constellation routing algorithms, LRES reduces the packet loss rate and improves throughput,especially in the case of heavy network load.

ACKNOWLEDGEMENT

This work was supported by the National Natural Science Foundation of China (No.6217011238 and No.61931011).

NOTES

137 is the access satellite of ground station G66 and G67,50 is the access satellite of ground station G68,51 is the access satellite of ground station G69.