，*，，，，，，

1.State Key Lab of Information Photonics and Optical Communication，School of Electronic Engineering，Beijing University of Posts and Telecommunications，Beijing 100876，P.R.China；

2.China Academy of Space Technology，Beijing 100094，P.R.China

Abstract: Frequent inter-satellite link （ISL） handovers will induce service interruption in large-scale space information networks，since traditional distributed/centralized routing strategy-based route convergence/update will consume considerable time（compared with ground networks）derived from long ISL delay and flooding between hundreds or even thousands of satellites.During the network convergence/update stage，the lack of up-to-date forwarding information may cause severe packet loss.Considering the fact that ISL handovers for close-to-earth constellation are predictable and all the ISL handover information could be stored in each satellite during the network initialization，we propose a self-update routing scheme based on open shortest path first（OSPF-SUR）to address the slow route convergence problem caused by frequent ISL handovers.First，for predictable ISL handovers，forwarding tables are updated according to locally stored ISL handover information without link state advertisement（LSA）flooding.Second，for unexpected ISL failures，flooding could be triggered to complete route convergence.In this manner，network convergence time is radically descended by avoiding unnecessary LSA flooding for predictable ISL handovers.Simulation results show that the average packet loss rate caused by ISL handovers is reduced by 90.5%and 61.3%compared with standard OSPF（with three Hello packets confirmation）and OSPF based on interface state（without three Hello packets confirmation），respectively，during a period of topology handover.And the average endto-end delay is also decreased by 47.6%，9.6%，respectively.The packet loss rate of the proposed OSPF-SUR does not change along with the increase of the frequency of topology handovers.

Key words：space information network；inter-satellite link；route convergence；self-update routing scheme

0 Introduction

A growing interest has been imposed on space information networks as the satellite internet is one of the“new infrastructure”and lots of countries want to accelerate its commercialization.Several mega-constellations have been planned，such as Starlink，OneWeb，Telesat，“National Network”project，etc［1］.These constellations composed of hundreds（or even thousands）of satellites can overcome distance and terrain restrictions to realize global coveragence and provide multiple services to individual users.Nevertheless，frequent inter-satellite link （ISL）［2］handovers caused by the periodic movement of satellites will induce service interruption in a large-scale satellite network.In order to route data correctly after topology changing，the routing protocol need to flood the connectivity variation and converge again.But route convergence in satellite networks takes a long time because of long ISL delay and forwarding the changed information between hundreds/thousands of satellites.Thus，until route convergence is done，for some satellitenodes，the lack of up-to-date forwarding information may cause severe packet loss，even service interruption.

The satellite routing scheme can be divided into two types：Centralized and distributed routing.Centralized routing solutions are represented by snapshot routing and software-defined network（SDN）enabled routing architecture.For snapshot routing，the system period of a satellite network is divided into several time intervals，and the network topology within each time interval is regarded as a constant［3］.Each satellite node only has the forwarding function based on routing tables that are pre-calculated and uploaded from the ground station.This scheme shows a strong requirement on storage and computing capability with the increase of the network scale.An adaptive snapshot routing strategy［4］was raised to reduce the occupation of previous onboard storage resources，and the results showed that the proposed scheme decreases on-board storage resource occupation and improves quality of service.But this scheme has a fatal shortcoming：Poor adaptability for unpredictable ISL failures［5］.As for SDN enabled routing architecture，its topology discovery （with link layer discovery protocol （LLDP））and routing computation relies on the SDN controller.And the route update delay includes time consumed by topology changing event awareness（from switch to controller），forwarding policy calculation and flow table updating（from controller to switch）［6-7］.But if the SDN controller continuously works in this way，it will suffer from tremendous delay for routing update and significant communication overhead［8-10］.And a reliable SDN control link also needs to be guaranteed until it is not affected by frequent ISL handover.Cho et al.［11］developed a power-efficient control link algorithm，and numerical results demonstrated that this algorithm can establish low latency and high reliability of control link with reduced power consumption.

Regarding the distributed routing scheme，open shortest path first（OSPF）-based dynamic routing and delay tolerant network（DTN）are two typical solutions.In the OSPF architecture，each satellite node（i.e.router）independently maintains a link state database（LSDB）that describes the structure of the network based on link state information.The routing table is calculated based on LSDB.OSPF enabled route convergence consumes too much time because of long ISL delay and flooding between hundreds（or even thousands）of satellites［12］.Within the period of network convergence，the routing table of some satellite nodes is not updated immediately and this may cause severe packet loss because of incorrect routing information.In Ref.［5］，a distributed dynamic routing based on ISL state information was proposed.But numerous ISL state flooding needs to be flooded in topology establishment phase and link failure response phase，and it will induce service interruption because of slow route convergence.At the same time，although DTN is an alternative for satellite networks，it is more suitable for deep space networks （disjointed networks） or sparse satellite constellation［13］.Madni et al.［14］found that quota-based DTN routing scheme in which the number of replicas was limited and fixed for each generated bundle could balance between delivery delay and overheads costs，but the delivery ratio was still much lower than that of the connected network.

Therefore，regardless of centralized and distributed routing scheme in satellite networks，route convergence caused by frequent ISL handovers is still a problem that has not been properly resolved.Plus，due to periodic motion of satellite，ISL handovers are common and inevitable.For sparsely connected constellation（i.e.Iridium，Iridium NEXT），this phenomenon is even more severe.Even in dense LEO constellation，e.g.Starlink，ISL handovers are also needed［15］，but the number of them is less.For frequent ISL handovers in sparsely connected constellation，since satellite constellation is decentralized generally（multi-layer satellite network combined with GEO/MEO/LEO may be an exception），OSPF-based distributed routing is a promising solution if slow convergence could be alleviated.

Since ISL handovers are predictable and all the ISL handover information（refereed as contact plan afterwards）could be uploaded to satellites in the network initialization period，we propose a self-up-date routing scheme base on OSPF（OSPF-SUR）to solve the slow route convergence problem especially under the frequent ISL handovers scenario.In the proposed routing scheme，for predictable ISL handovers，the routing table in each satellite node is directly updated according to locally stored ISL handover information and without the link state advertising（LSA）flooding for route convergence.For unpredictable link failures，LSA flooding could be activated to complete route convergence.By this way，the network convergence time can be descended by avoiding LSA flooding for predictable ISL handovers，and the packet loss rate caused by services interruption is also decreased.Finally，we conduct simulations to verify the OSPF-SUR.

The rest of this paper is organized as follows.In Section 1，we introduce the structure and function of contact plan tables（CPTs）that are stored in each satellite during the network initialization，and the self-update routing mechanism based on CPT is also elaborated.Then，the OSPF-SUR scheme is detailed in Section 2.In Section 3，a hardware platform is constructed to verify the effectiveness of the OSPF-SUR scheme，and simulation results are also analyzed and discussed.Finally，conclusions are drawn in Section 4.

1 Contact Plan Table

1.1 Definition of CPT

CPTs are employed to define the pre-calculated topology that is composed of ISL handover information for each satellite node.It includes multiple entries，and its structure of entry is illustrated in Fig.1.Each entry is composed of five parts：Node id，interface id，peer node id，effective time start and effective time end.Each entry of a CPT is directly related with specific ISL establishing and disconnecting.

Fig.1 Structure and function of CPT

1.2 Self-update routing mechanism using CPTs

Firstly，satellite nodes run the OSPF protocol and store CPT information when the network is initialized.During ISL establishing，the countdown timer is triggered according to the survival time of each entry in the CPT and the corresponding entry will be activated to update the routing table of each satellite nodes.The detailed update procedure is shown in Fig.2.Corresponding to each entry of the CPT in each satellite，the self-update procedure includes two procedures.

（1）Update LSA and neighboring status information.For each satellite node，there have several LSAs in LSDB，and the contents of a LSA are replaced based on the corresponding entry.Specially，the LSA contents，including advertising node，link id，link data，are replaced by node id，peer node id，interface id of entry，respectively.And the survival time which is an extend field in the LSA is confirmed by effective time start and effective time end of entry in the CPT.As shown in Fig.2（a），each LSA in LSDB is updated by replacing the old contents based on the corresponding entry in the CPT.Then，the entry of the CPT is also used for updating neighbor status information in the neighbor interface table（NIT），but this updated procedure is only for the satellite nodes whose direct ISLs have changed.In Fig.2（b），for each entry in the CPT，interface id enables the corresponding interface tostart working and makes its status change to UP.Peer node id and interface id can determine the interface id of another satellite node for this link，and its neighbor status jumps straightway from down to FULL state.

Fig.2 Self-updating routing mechanism using CPTs

（2）Rebuild routing table.In Fig.2（c），the function of rebuilding routing table which combined with the information in NIT and LSDB will be triggered after the above procedures are implemented.Then，the obsoleted routing table will be replaced by a new one.In addition，next self-update timer determined by effective time end part of the entry is also configured and stored.

2 OSPF-SUR Scheme

Routing problem is an essential problem in satellite networks.Compared with traditional terrestrial networks，the main problem of satellite routing is frequent ISL handover.And ISL handover can be divided into two types.（1）Predictable ISL handovers（i.e.，normal ISL interruption）.The cause for this type is the periodic movement of satellites.（2）Unexpected ISL failures.The possibility of accidental ISL failures is relatively low.Nevertheless，regardless of the type of ISL handovers，the whole network needs to perform route convergence in order to recalculate the routing table whenever ISL handover changes.But route convergence takes too long time derived from the long ISL delay，flooding caused by frequent ISL handovers in large-scale networks composed of hundreds of satellite nodes.Until completing router convergence，it will cause the entire network to remain in an unstable state，especially severe packet loss rate.Moreover，even if the routing schemes in DTNs are adapted in this largescale network，it wastes valuable bandwidth，and can hardly guarantee the timeliness of services.The route convergence caused by frequent ISL handovers cannot be resolved through an efficient routing scheme.

Considering the fact that ISL handovers are predictable and all the ISL handovers information could be saved in each satellite node during the network initialization，we propose the OSPF-SUR scheme to address the slow route convergence caused by frequent ISL handovers.The OSPF-SUR scheme combines the dynamic routing protocol with the predictable characteristics of ISL handovers to solve the above problem.The routing table in each satellite node is updated according to the stored ISL handover information（i.e.CPT）in advance and the LSA flooding is also avoided，thus the network convergence time is radically decreased by avoiding flooding and the packet loss rate caused by incorrect routing is optimized.For unexpected ISL failures，flooding could be activated to complete route convergence.

When the ISL handover changes，a satellite node needs to confirm this type of ISL handovers，predictable or unexpected.If the current time for this ISL handover is one of the stored self-update timers and the changed ISL is consistent with the next changed ISL in CPT，this is a predictable one，otherwise is an unexpected ISL failure.And then the corresponding routing update process is triggered，as shown in Fig.3.For a predictable ISL handover in Fig.3（a），the procedures of self-update routing mechanism is performed as mentioned in the previous section.The saved CPT will be used to update the contents of the LSA in LSDB，and the interface and neighbor status in the NIT are also renewed for the satellite nodes where the direct ISL has changed.The function of rebuilding routing table is activated after the former two procedures are implemented.Then the newly generated routing table will take place of the old one.For each satellite node，LSA flooding generated by ISL handovers but not been sent out is avoided，otherwise the new LSA will induce ineffective update for the routing table and waste valuable bandwidth and this function is implemented by modifying the old flooding mechanism，as shown in Fig.4.The newly generated LSA is compared with all the LSAs in LSDB.If the new LSA is identical with the one in LSDB，this LSA is discarded，otherwise LSA flooding will be triggered.In this manner，the modified floodingmechanism successfully avoid the LSA flooding for predictable ISL handover，and it also can trigger LSA flooding to complete route convergence for unexpected ISL failures.

Fig.3 OSPF-SUR scheme for predictable and unexpected ISL handovers

Fig.4 Mechanism of avoiding LSA flooding for predictable ISL handovers

Further，as shown in Fig.3，the OSPF protocol that runs in satellite nodes will come into play at that time when the unexpected ISL failure changes.For unexpected ISL failures，satellite nodes will perceive this change，and then flood the newly generated LSA to surrounding nodes.After receiving the link state update packet（LSU），the satellite node reconstructs the routing table and continues to flood to all the neighbors until route converges.In addition，when these two types of ISL handovers occur at the same time，the procedures of self-update routing mechanism are performed，and LSA flooding for unexpected ISL failures is activated simultaneously to route convergence.

The flow of the OSPF-SUR scheme is exhibited in Fig.5.Topology planning results is firstly obtained from the prestored CPT，then the self-updating timestamps are set for predictable ISL handovers.When the topology change occurs， the changed satellite node will get the current system time，and compare it with the preset timestamps.If and only if the current time is one of the preset timestamps and the changed ISL is consistent with the next changed ISL in the CPT，this topology change is a predictable ISL handover.Otherwise，it is an unpredictable ISL failure.The following mechanisms are activated for predictable ISL handovers，including update LSA contents，neighbor status information and routing table（i.e.the mechanism is shown in Fig.2）.Meanwhile，the LSA flooding avoidance mechanism in Fig.4 also comes into play.As for unexpected ISL failures，it can be triggered in to flooding LSA in order to update the routing table.

Fig.5 Step diagram for OSPF-SUR scheme

3 Performance Evaluation

In this section，a hardware platform is constructed to verify the effectiveness of the OSPFSUR scheme.And we perform a series of simulations to evaluate the performance of the OSPFSUR scheme.

3.1 Functional verification of OSPF-SUR scheme

The hardware platform of a satellite network is built［16］.We only use three physical satellite nodes to verify its function.The structure of the hardware platform is shown in Fig.6.A CPU board and a FPGA board are connected to each other to form a satellite node，and the host connected with the CPU board can query and display the status and data information of the protocol operation run by the CPU board.Three physical satellite nodes are connected to each other to form a ring.The CPU board runs the OSPF-SUR scheme，and it can exchange information with the FPGA board that has multiple ISLs and controls the connection and disconnection of ISL.ISL status information can be forwarded to the CPU board from the FPGA board and then the routing protocol will be changed on the basis of receiv-ing information.In addition，the ISL handover information（i.e.CPT）is stored in the CPU board in advance，and ISL can be interrupted according to the instructions send by the CPU board.

Fig.6 Hardware platform structure

The setup of the hardware is shown in Fig.7.Suppose that traffic is transmitted firsthand from node 2 to node 3，and the predicable ISL handovers are the interruption of the ISL between node 2 and 3.When the predictable ISL handovers are coming，the procedures of self-update routing mechanism are performed based on the stored CPT，replacing the old contents of LSA in LSDB and updating the interface and neighbor status in the NIT.And the LSA flooding is also avoided for the predictable ISL handover.Afterwards，the routing table is updated when the above procedures are implemented，and the LSDB，routing table and transmission path on the CPU board will be updated.Meanwhile，the ISL on the FPGA board will be interrupted according to the presupposed timestamp.The updated results are acquired from the CPU board by the connected host.

Fig.7 Setup of simulation

These changed information before and after the OSPF-SUR update in the CPU board are shown in Fig.8.It can be observed that the LSDB，the routing table and the transmission path are changed compared with the former ones.And the new transmission path is where traffic has to be forwarded by node 1 to reach the destination node.It means that the OSPF-SUR scheme in the CPU board accomplishes self-update routing procedures based on the stored CPT.At the same time，the LSA flooding information has not been sent out and other CPU boards have not received any flooding information.The above results successfully verify the effectiveness of the OSPF-SUR scheme.

Fig.8 Changes before and after OSPF-SUR scheme update

3.2 Simulation environment

In the simulation process，we take a LEO constellation as a constellation model to complete routing performance simulation.This LEO constellation is a walker-delta orbit model［17］，and has five orbital planes with 21 satellites on each orbit.Each satellite node has three laser communication terminals（LCTs）.It means that a satellite node maintains three ISLs with its adjacent nodes.And the processing latency of the intermediate satellite node examining packets by hardware/software and forwarding it consumes 100 ms.The specific parameters of this constellation are listed in Table 1.The optical ISL from LEO （i.e.，LCT accommodated on TerraSAR-X from Germany）to LEO（i.e.，LCT accommodated on NFIRE from America）is established，and full communication enters within typically from 41 s to 52 s including spatial acquisition and laser phase locking［18-20］.For the sake of conservatism，ISL reconstruction time is assumed to be 60 s in this paper.Meanwhile，under the restriction of topology handover times，we also compare the OSPFSUR scheme with the OSPF with three Hello packets confirmation，and the OSPF based on the interface state（OSPF-IS，without three Hello packets confirmation）.Besides，the simulation is executed by OMNET++［19］，which can simulate the corresponding network performance according to the input satellite parameters and routing strategy，such as delay，packet loss rate and throughput，etc.

Table 1 Constellation parameters

3.3 Simulation results

The performance comparison results versus different routing strategies during a period of topology handover are shown in Fig.9.For the OSPF-SUR scheme，the routing table can be directly updated according to the pre-stored CPT information and LSA flooding is avoided when a predictable ISL handover occurs，which substantially decreases the route convergence time，and packet loss caused by incorrect routing within route convergence time is also declined.Thus，the OSPF-SUR scheme always has the optimal performance in terms of the average packet loss rate and delay.It also can be seen from the Fig.9 that the OSPF scheme has the worst performance regardless of average packet loss rate and delay.It is because the OSPF scheme requires three Hello packets to determine ISL interruption，and then floods the changed information to complete route convergence.These processes take a long time to achieve route convergence，so a mass of packets are dropped and needed to retransmit，which contributes to the severe packet loss and tre-mendous delay.Meanwhile，compared with the OSPF routing strategy，the OSPF-IS scheme has the perception ability of link interruption，which means that this scheme does not require three Hello packets confirmation，and it only needs to flood changed information to the whole network to route convergence and then update the routing table.Thus，the packet loss rate and delay of the OSPF-IS scheme are better than these of the OSPF scheme and inferior to those of the OSPF-SUR scheme.

Fig.9 Performance comparison of routing schemes during a period of topology handover

The above explanations also can be verified in Fig.9（b）.Fig.9（b）shows the number of received packets with time within a period of topology change.The decline of received packets represents that route convergence is in progress.The duration that the curve of received packets drops and returns to normal means the route convergence time.The curve of the OSPF-SUR scheme declines to the lowest and returns to the normal most quickly compared with other routing schemes.And the curve of the OSPF scheme has the most severe downward trend and fluctuation，and the slowest recovery speed.As for the OSPF-IS scheme，the curve is higher than that of the OSPF scheme，and lower than that of the OSPF-SUR strategy.The reason for the aforementioned results is stated in the previous paragraph.

In addition，the curves for the packet loss rate under different routing schemes remain basically constant.The reason is that packet loss mainly occurs during the network convergence time，and the number of lost packets rises with the increase of the sending interval，but the total number of sent packets is also increasing，thus the packet loss rate is relatively constant.It also means that the packet loss rate depends on the route convergence time.

The probability that the traffic needs to be retransmitted also depends on the network convergence time，thus the corresponding delay of the OSPF-SUR scheme is the lowest compared with other routing schemes in this simulation.And the delay of OSPF is the worst，it is because slow route convergence results in extended delay.For the OSPF-IS scheme，the delay is higher than that of the OSPFSUR，but lower than that of OSPF，and the reason is that the convergence time is centered between other routing schemes.Specifically，the OSPF-SUR scheme can optimize the packet loss rate performance by about 90.5%，61.3% compared with those of OSPF and OSPF-IS routing schemes.And delay is optimized about 47.6%，9.6%，respectively.In addition，the above-mentioned results demonstrate that the standard OSPF cannot be directly applied into space information network because of severe packet loss and tremendous delay.

Further，the routing performance under different topology handover times is also analyzed.In Fig.9，the comparison results of routing performance are similar to those in Fig.10：The OSPFSUR scheme always has the best performance in terms of packet loss rate and delay，the OSPF-IS scheme is the second and the OSPF scheme is the worst.The reason is stated in the previous paragraph，that is，the network route convergence time is the lowest for the OSPF-SUR scheme，and then that of the OSPF-IS is lower than that of the OSPF scheme.Another interesting point in Fig.10 is that with the increase of topology handover times，thepacket loss rate of the OSPF-SUR scheme remains almost unchanged，but other routing schemes are increasing.As we noted in previous paragraph，for the OSPF-SUR scheme，the routing table is updated according to the saved CPT in each satellite node without flooding LSA to the whole network，so the route convergence time is the smallest，and the packet loss rate has nothing to do with the increase of topology handover times.Nevertheless，for other routing schemes，the route convergence time is increasing with the number of topology handover times.The growth trend of the curve for the OSPF scheme is much higher than that of OSPF-IS because of three consecutive Hello packets confirmations for each ISL interruption.Further，as the number of topology handover times increases，delay curves are basically consistent with packet loss rate trends except for the OSPF-SUR scheme.For the proposed OSPF-SUR scheme，delay is slightly increased，not constant.This phenomenon is from the fact that the retransmitted packet caused by ISL interruption rises with the increase of frequency of topology handovers，and it contributes to tremendous delay.But for other routing schemes，delay is gradually deteriorated as the increase of topology handover times.It is because the route convergence time is aggrandized，thus the retransmitted packets within the network convergence time is added and then the delay is enlarged.In other words，the above results indicate that the OSPF-SUR scheme maintains the best performance as the number of topology handover times increase.

Fig.10 Performance comparison versus number of topology handovers

4 Conclusions

In satellite networks，ISL handovers caused by periodic mobility of satellites is a common and inevitable phenomenon.Specially，for a sparsely connected constellation，ISL handovers are even more severe than those of a dense constellation.Frequent ISL handovers will induce severe service interruption，because of slow route convergence in the existing centralized and distributed routing solutions.

In this paper，considering the fact that ISL handovers are predictable and all the ISL handover information could be stored in each satellite node，we propose an OSPF-SUR scheme to address the slow route convergence problem in distributed space information network routing.Based on the local CPT information stored in each satellite node，the self-update routing mechanism is implemented by directly updating the routing table without LSA flooding caused by predictable ISL handovers.LSA flooding is suspended by adding a special judgement condition before flooding.In this manner，for predictable ISL handovers，the routing table can be updated according to locally stored ISL handover information without LSA flooding.For unexpected ISL failures，the LSA flooding also can be triggered to complete route convergence.The function of the proposed scheme is verified with our hardware platform including CPU （running the proposed protocols）and FPGA boards（data forwarding）.And the simulation results show that under the same topology handover times，the OSPF-SUR scheme has the lowest packet loss rate and delay performance，compared with those of the standard OSPF with three Hello packets confirmation and the OSPF based on interface sate without three Hello packets confirmation.In addition，the packet loss rate of proposed OSPF-SUR scheme does not change along with the increase of frequency of ISL handovers.