Zengyin Yang, Hewu Li, Qian Wu,＊, Jianping Wu1,

1 Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

2 Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing 100084, China

3 Beijing National Research Center for Information Science and Technology (BNRist), Tsinghua University, Beijing 100084, China

I. INTRODUCTION

Background.With the booming development of terrestrial network and the increasing network demands of rural, remote and other areas, building an Integrated Terrestrial-Satellite Network (ITSN) to provide global Internet access, has become ever more attractive.Several practical ITSNs have been proposed,e.g., Transformational Satellite Communications System (TSAT) program sponsored by the U.S. Air Force [1] and Future Integrated Terrestrial-Satellite Network (Future ITSN)proposed in [2]. Generally, ITSN is an integrated network consisting of terrestrial and satellite networks. The satellite network consists of many heterogeneous space nodes including Geostationary Orbit (GEO), Medium Earth Orbit (MEO), Low Earth Orbit (LEO)satellites and ground Gateways. The satellite network is a unified network similar to the terrestrial network, in which all space nodes are interconnected via satellite-satellite links and satellite-gateway links. As satellite continually flies, the topology of satellite network changes frequently. The terrestrial network mainly refers to terrestrial Internet and mobile communication networks like 2G/3G/4G/5G,whose network topology is almost static. Both satellite and terrestrial networks are integrated with each other.

To meet the demands of interconnecting heterogeneous space routers, while at the same time achieving the integration between terrestrial and satellite networks, many researchers are moving to the widely and successfully used terrestrial routing protocols [3-7]. Naturally, such routing protocols provide the IP connectivity in satellite network, which is preferable to the traditional dedicated circuits for different satellite services such as voice,video, and data. Besides, using terrestrial routing protocols can achieve the integration of satellite and terrestrial networks more efficiently.

However, terrestrial routing protocols are intentionally designed for the almost static networks, and rely on propagating the routing message to discover New Network Topology(NNT) after the topology change occurs. That means if we implement them into the satellite network of ITSN, frequent topology changes of satellite network will incur overly numerous routing messages [3-5]. The whole ITSN will fail to provide efficient service for most system time. This issue even becomes more severe as the network scale increases.

Contributions.In this paper, we firstly propose a Topology Discovery Sub-layer for ISTN Routing Scheme (TDS-IRS), which adds a Topology Discovery Sub-layer (TDS) between routing protocol and physical topology in every space node, to avoid routing protocol propagating numerous routing messages for discovering NNT. The TDS is responsible for discovering the NNT in advance of topology change by taking advantage of the movement predictability of satellite and the requirements of routing schemes. Routing protocols will not aware the topology changes, and thus avoid propagating the numerous routing messages.

The core module of TDS-IRS is TDS. It is used to discover when the topology change will occur and what the kind of NNT will be. Its first goal of figuring out the timing of topology change can be easily achieved by making use of the movement predictability of satellite and the time synchronization of all satellites. However, the second goal of TDS is a challenging issue as there exist two conflicts that can make the NNT discovery fail.The first conflict is criteria conflict when a single node decides to generate NNT according to various criteria of candidate links and nodes. The second conflict is decision conflict between multiple nodes. If decisions of two nodes are conflicted with each other, one of both nodes may be removed from ITSN. The NNT may be invalid if the NNT discovery scheme does not ware that conflict.

Secondly, we formulate the discovery process of NNT as a generic optimization problem. Both criteria and decision conflicts are formulated as the goal function and the constraints of that problem, respectively. Furthermore, we design a Weighted Perfect Matching based Topology Discovery (WPM-TD) model to solve that generic problem. In that model,the perfect matching is used to eliminate the decision conflict, and the maximum weighted matching is used to eliminate the criteria conflict. The result of maximum weighted perfect matching thus is the NNT.

Thirdly, we build a testbed with real network devices and meanwhile interconnect that testbed with the real Internet to validate TDSIRS. Results show TDS-IRS can assist routing protocol discovering NNT immediately with the less on-board overhead compared with some optimized routing schemes.

Finally, we verify the core module of TDSIRS, i.e., WPM-TD, in different network scenarios. Extensive experiments show WPM-TD can work efficiently, avoiding invalid NNT and decreasing 20% ～ 57% of potential topology changes. Also, the deployment of WPMTD in TDS-IRS can improve up to 47% ～105% of network throughput.

Organization.The rest of this paper is organized as follows. Section II presents background and motivation. In section III, we present the architecture of TDS-IRS and the challenges of TDS. Solution related to TDS is presented in section IV. In section V, we conduct extensive emulations to evaluate TDS-IRS and WPM-TD. Finally, we survey some related works in section VI and draw a conclusion in section VII.

II. BACKGROUND AND MOTIVATION

2.1 Integrated terrestrial-satellite network

Overview.Integrated Terrestrial-Satellite Network (ITSN) is an integrated network of terrestrial and satellite networks. The terrestrial network consists of Internet and mobile communication networks like 2G/3G/4G/5G. Satellite network comprises Geostationary Orbit (GEO),Medium Earth Orbit (MEO), Low Earth Orbit(LEO) satellite and ground gateways. The satellite network is a unified network in which satellites are interconnected via satellite-satellite links and satellite-gateway links. Meanwhile,the satellite network interconnects with the terrestrial network via one or more gateways. The global users can flexibly access both terrestrial and satellite networks. Communications among these users can be routed between both networks efficiently.

The widely and successfully used terrestrial routing protocols [3-7] are considered as promising protocols to interconnect heterogeneous space routers and meanwhile to integrate satellite network with terrestrial network.In satellite network, the terrestrial routing protocols can provide IP connectivity, which is preferable to the traditional dedicated circuits for satellite services such as voice, video, and data. Besides, using terrestrial routing protocols can achieve the integrated routing of satellite and terrestrial networks easily because these protocols have been widely used in the terrestrial network. As the satellite network is a large-scale backbone similar to the terrestrial network instead of an access network, the integrated routing is a critical factor for ITSN.One prominent characteristic of integrated routing is that the router of satellite network can learn the routing information of terrestrial users from the router of terrestrial network,vice versa.

Unicast vs Multicast.The terrestrial routing protocols can be classified into two types:unicast routing and multicast routing. In the terrestrial wired network, the unicast routing is preferable to multicast routing due to the large cost of building and maintaining multicast tree. In the satellite network, the wireless communication may provide the inherent multicast capacity, in which multiple users can share the same antenna of a satellite [8]. The multicast routing between satellite and users will be very efficient as multiple users can get a common share of the message from a satellite.

However, the wireless communication between satellites works like the wired communication. Since large scale of space area requires the antenna alignment and tracking,a satellite needs to adopt a single antenna for every peering node. In this case, the deployment of multicast routing between satellites will cost high, which is similar to what it does in terrestrial wired network, that is, to build and maintain many multicast trees. In the future, when the technology of phased-array satellite antenna becomes very mature, multiple satellites may can share the same antenna of a peering node. Multicast routing between satellites may become effective.

Besides, the unicast routing protocol can be easily extended to support multicast routing,such as MOSPF [9]. Hence, we mainly focus on the unicast routing between satellites in this paper.

Topology Change.Composed of many heterogeneous router-nodes, the whole ITSN is a very complex system. To describe the system clearly, we classify all nodes of ITSN from the view of topology dynamic, which is the critical factor in influencing routing protocols. These nodes can be classified into two types, i.e.,mobile nodes (MNs) and static nodes (SNs).In a narrow sense, SNs only refer to the nodes with static positions related to the ground,such as GEO satellites, gateways, and ground routers, while MNs only refer to the nodes with moving positions such as MEO and LEO satellites. In a broad sense, both MNs and SNs can be any nodes. When two nodes remain relatively static, they are both static nodes. While when two nodes move relative to each other,one node is as SN and other is the MN.

As for the practical satellite systems, the topology change occurring among satellites in the same system is very simple, in which link connection between any two satellites mainly remains unchanged or just closes for a while when that link disconnects. For instance, the satellite in Iridium system closes its link when it moves into the polar region [10], and reconnects that link when it leaves the polar region;and the link connection between adjacent satellites in Tsinghua Space Network almost keeps unchanged. On the contrary, the topology change occurring among different systems is very complicated. Hence, we mainly focus on the topology changes among different systems.

Then we summarize the scenarios where topology changes are triggered as follows.

1) Link disconnection: When one or more MNs fly out of the coverage of their peering SNs, a topology change (called mobility-related topology change, MRTC) will occur, i.e.,disconnecting the old connections to the old SNs and peering with the new SNs.

2) Appearance of special SNs: When one or more MNs fly into the coverage of some special SNs, which have more superiorities to attract the MNs to connect with compared to the current SNs, an MRTC may be triggered.For instance, an MRTC will be triggered when some MNs fly into the coverage of gateway, as gateways have unlimited resources and shorter delays than GEO satellites.3) Access of new MNs. If an old MN has been removed from ITSN due to some failures or a new MN needs ITSN to help itself convey data, it will keep trying to join the ITSN.When the access of an MN is allowed, an MRTC will be triggered. The routing protocol needs to propagate the access information of that MN through the whole network.

Fig. 1. Number of topology changes.

As all MNs in satellite network constantly move, the above scenarios will frequently arise, and thus the MRTCs occur frequently.We conduct an experimental analysis for it with the network parameters from the real world (see Table II). And the policy of an MS selecting the closest SN as its following SN when an MRTC occurs is applied. We observe the topology changes of ITSN during a day.

Figure 1 shows that the number of topology changes during a day increases linearly with network scale increasing. When network scale rises from 52 to 232, number of topology changes increases from 1359 times to 9765 times, and mean value of time intervals between any two neighboring changes is decreased from 1min to 10s.

2.2 Motivation

As we all know, the network topology discovery of terrestrial routing protocols relies on exchanging New Network Topology (NNT)among all routers. When a topology change occurs, a routing update will be triggered to propagate NNT. In that case, if we apply these protocols into ITSN directly, the overly frequent MRTCs will push routing protocol to trigger many routing updates. The whole net-work thus will be unstable for the most system time [4]. During that period, a lot of update messages will propagate throughout the whole network, which will severely waste the limited satellite resources, such as computing capacity, storage, and power of space router [3]. Especailly, these issues become more severe as the network scale increases.

Hence, before we implement terrestrial routing protocol into ITSN, some schemes are required to eliminate the severe effects of MRTCs.

III. ROUTING SCHEME USING TOPOLOGY DISCOVERY SUB-LAYER

To eliminate the effect of frequent MRTCs on terrestrial routing protocols, we design a novel routing scheme that uses a topology discovery sub-layer to conduct the network topology discovery for MRTCs.

3.1 Architecture

Fig. 2. Architecture of TDS-IRS.

The architecture of TDS-IRS (Topology Discovery Sub-layer for ITSN Routing Schemes)is shown in figure 2, which consists of Routing Protocol (RP), Topology Discovery Sub-layer(TDS), Physical Topology (PT), and Ground Control Center (GCC).

The TDS is implemented between RP and PT, which is controlled by GCC. Primary functions of TDS are to receive the NNT from GCC, and then to submit that information to both RP and PT modules. Also, functions of TDS can be enhanced according to requirements of GCC, such as collecting network parameters, getting requirements of routing protocol, and verifying the implementation of NNT.

PT module, which is an essential part of the satellite, directly monitors and manages the flight status of satellite. It receives NNT from the TDS, and implement NNT by guiding satellite to adjust satellite antenna for building the link connection.

In RP module, some terrestrial routing protocols are implemented, which seem like working on the terrestrial network. Before an MRTC is triggered, RP will receive the NNT from TDS. And then RP will just update its routing table once PT implements NNT. The detection and propagation process of MRTC will be avoided. In some cases that PT may fail to apply the NNT, TDS will notify RP and GCC that failure. RP then discovers the network topology like what it does on the terrestrial network.

Terrestrial routing protocols can be the unicast routing protocols such as BGP, OSPF,or the multicast routing protocols such as MOSPF. When an MRTC occur, these routing protocols can get NNT from TDS. But, for multicast routing, there also exists an unpredictable connection changes between satellite and ground users due to the movement of both nodes. For these unpredictable changes,multicast routing protocol may need itself to discover the NNT unless we can design an advanced topology discovery method for the unpredictable changes.

GCC is the controller of TDS, which is responsible for figuring out when MRTC will occur and what kind of NNT will be. GCC conducts its functions with the help of information provided by TDS and predictability of satellite movement. Once GCC figures out that an MRTC will occur, it will generate an NNT and then send the NNT with PT and RP in advance. GCC even can be implemented into the terrestrial network, and communicates with the TDS of every space node by the integrated routing of ISTN.

3.2 Topology discovery sub-layer

Topology Discovery Sub-layer (TDS), which is core module of TDS-IRS, assists all space nodes discovering NNT before the MRTC occurs. It has two principal jobs, i.e., figuring out when the MRTC will be triggered and generating the NNT. The first job can be easily achieved by taking advantages of the predictable relative position of all space nodes to figure out when an MRTC will be triggered.On the contrary, the second job of discovering NNT is an important and challenging issue. In the rest paper, we will deep analyze the challenges of topology discovery and formulate the NNT generation as a generic optimization problem.

3.2.1 Challenges of topology discovery

Specifically, the challenges of the NNT discovery behave in the two conflicts. The first conflict is criteria conflict when a single space node makes a decision to generate its own best NNT according to multiple criteria of candidate links and nodes. The second conflict is decision conflict between different nodes.1. Criteria Conflict

As the coverage areas of candidate SNs overlap with each other, there exist many SNs for a single MN to select and to build the link connection when an MRTC occurs. Once the MN selects an SN, the corresponding NNT will be generated. That is, the decision of MN to choose SN irreversibly determines the feature of NNT. As network topology is the basis of routing selection, a reasonable NNT is essential for routing protocol. Hence, every MN wants to make the wisest decision to select its own best SN.

However, there exist many criteria involved in the decision process, such as bandwidth requirement of MN; spare access capacities,potential load, energy, processing capacity of SN; and duration, propagation delay, Signal to Noise Ratio (SNR) of the link between MN and SN. These criteria may even Conflict with each other. The decision process for a single MN is to make a tough trade off between these criteria.

We pick out some criteria that are directly related to route selection of routing protocol and analyze their impacts on decisions of MNs.

Spare Access capacity.Access capacity of an SN represents the maximum number of MNs to access that SN, which is limited by the number of tracking antennas equipped by SN and the channel interference of multiple antennas [11,12]. For instance, the number of antennas per gateway in Oneweb is about 10[11]. More antennas equipped by satellite will incur more cost or lower lifetime of satellite.As we all know, the build and launching of antennas cost very high. The operation of additional antenna also will consume more energy of satellite, which will decrease the lifetime of satellite. Besides, multiple antennas also incur the channel interference, which is similar to the MIMO interference in terrestrial wireless network [13-15].

If an SN has no spare access capacity, it will reject the accesses of other MNs. The access failure of an MN will severely damage the network performance. Firstly, the corresponding MN will lose the connection to ITSN, failing to provide its service. Secondly,an extra topology change will be incurred when that MN rejoins ITSN.

Link Propagation Delay.Since space nodes of satellite network are extremely far away from each other, the link propagation delay is very large so that in most cases it is taken as the metric for routing selection. And the delay difference from an MN to different SNs can be more than 100 ms. Many MNs will want to choose the closest SN, as selecting an SN with the smallest propagation delay can decrease the communication latency.

Link Duration.Link duration refers to the time from the link connection to the link disconnection. Ideally, if all MNs select the SN with largest link duration, the total topology changes of ITSN is minimal. However, if all MNs choose the SN independently with the largest link duration from their own views,some MNs will try to peer with the same MN simultaneously. Since the access capacity of that MN is limited, one or more MNs will fail to access and thus be removed from ITSN.

Potential Load.Potential load refers to some SNs will potentially service for more MNs. For instance, many ground-based SNs(gateways) mainly locate within the territory and have smaller coverage area, while few space-based MNs (GEO satellites) locate at overseas and have a wider coverage area. And MNs seem to be evenly distributed in global because they continuously fly in their orbits.Potentially, the GEO satellite will service more MNs than gateway does, and have more potential load. Thus, the decision of an MN to select the SN with a large potential load is not the wise idea from a long-term perspective.

2. Decision Conflict

The decision Conflict of all nodes refers to the Conflict between multiple MNs’ decisions.As all MNs want to select their own best SN from their own views, the conflicts between their decisions will be incurred. That makes it difficult to generate a reasonable NNT that each MN pairs with an ideal SN. In some cases, it even brings some dangerous to the NNT discovery. For instance, if two MNs simultaneously select the same SN which only can provide access for one MN, the access of one SN will be rejected. The NNT will be invalid if the topology discovery of TDS-IRS does not ware this Conflict.

3.2.2 Formulation

In this part, we formulate the NNT discovery as a generic optimization problem. First of all,we use the candidate decision graph G= (S,M, C, E) to describe all candidate decision relationships of all MNs. Where M is the set of MNs that will trigger an MRTC, and S is the set of all MNs whose spare access capacity is denoted as the set C. All candidate link connections between MNs and SNs are denoted as set E.

As the candidate link connections in graph G represent all potential decisions of MNs,the decision of a single MN maps to the link selection in graph. That is, if an MN selects a link with the maximum gain in graph G, its own wisest decision is achieved.

We formulate the gain of an MN’s selection as a generic functionwherePSi,PMj,PEi,jare the network parameter sets of the ithSN, the jthMN, the potential linkEi,jbetween the ithSN and the jthMN, respectively. The detailed definition offi,jis the process of eliminating the criteria Conflict.

For the NNT generation of the whole network that all MNs select their own best links,its gain is the gain sum of all MNs’ decisions.However, there exists a decision conflict between multiple MNs. That means some constraints are needed to limit the decision of every MN. Considering these constraints, we formulate the NNT generation of the whole network as follows:

Subject to

WhereNS,NMare the number of SNs and the number of MNs, respectively.Siis theithSN whose network parameter set denotesPSi;Mjis thejthMN whose the network parameter set denotesPMj; andPEi,jis the parameter set of the potential link between theithSN and thejthMN.

The goal function F(λi,j, (Si,Mj,Ei,j)) is the gain of NNT generation. When it achieves the optimal value, all MNs will make the wisest decision under some constraints.

IV. SOLUTIONS

In the previous part, we formulate the topology discovery into a generic optimization problem. However, that problem cannot be solved easily. Firstly, according to its constraints, the whole problem is similar to the 0-1 programming problem. Secondly, the goal function is just an abstract function. In this part, we present a Weighted Perfect Matching based Topology Discovery (WPM-TD) model for that optimization problem and define a reasonable goal function.

In that model, the perfect matching is used to eliminate the decision conflict (to meet the constraints of optimization problem), and the maximum weighted matching is used to eliminate the criteria conflict (to achieve the maximum goal of optimization problem). The maximum weighted perfect matching thus is the discovered NNT.

Firstly, we model the constraints of that problem into the bipartite matching problem.Once we find a matching from the bipartite matching graph, all MNs make a reasonable trade off to eliminate the decision Conflict between multiple MNs.

Furthermore, we scale that bipartite matching into theweighted perfect matching [16].The result of weighted perfect matching is the optimal solution of the above optimization problem. In this step, the goal function needs to be defined to eliminate the criteria Conflict.

4.1 Designs

Candidate decision graph.Candidate decision graph refers to all candidate link connections between MNs and all SNs. As shown in figure 3(a), there exist three SNs and two MNs that will simultaneously trigger an MRTC. M1 can build the link connection with S1 or S2, while M2 can build the link connection with S2 or S3. The spare access capacity of these SNs is 2, 1, and 1, respectively.

Bipartite Matching Graph.The constraint of optimization problem is modeled to select all useful edges from candidate decision graph to form a new graph, in which every MN at most has one link and the spare access capacity of every SN is greater or equal to zero.

The above process is similar to the bipartite matching, but the bipartite matching does not meet the constraint of the spare access capacity directly. We add some “virtual nodes”to represent the constraint of spare access capacity of SN, the process of MN selection becomes the bipartite matching naturally. As shown in figure 3(b), we add a “virtual node”(S11) for S1. In this case, the matching of bipartite matching graph is the result that meets that the constraints of the optimization problem.

Fig. 3. Example of WPM-TD.

Once we find a matching from the bipartite matching graph, all MNs make a reasonable trade off to eliminate the decision Conflict between multiple MNs.

Weighted Perfect Matching Graph.In order to achieve the objective of optimization problem, we further scale the bipartite graph into a weighted perfect matching graph (That is also the weighted complete matching graph)[16], as shown in figure 3(c). Firstly, some“virtual links” are added to make link connection of such graph full-mesh. Then we calculate the quality of all links according to the criteria of candidate MNs and links, to eliminate the criteria conflict. The larger quality represents that the corresponding link is more likely to be chosen. And the quality of “virtual link” equals to zero.

We denote the weighted perfect matching graph as WG = (M, SC, EC, Q), where M is the set of MNs that simultaneously trigger an MRTC, and SC is the set of all original SNs and their virtual SNs. The size of SC is equal to the sum of all elements of set C in Graph G. EC is the set of all links, the size of which is equal to the value of |M|*|SC|. And set Q is the set of link quality, elements of which are calculated with some critical network parameters in the next part. The result of optimization problem is the matching of deleting all “virtual links” from the maximum weighted perfect matching of graph WG.

4.2 Nodes selection function

The generic quality function is defined as the sum of the gain of MN multiplied by an impact factor of SN, and a large enough constantCont.

Wherefi,jrepresents the quality of link (i,j).GMi,jrepresents the gain ofjthMN from link (i, j). AndISirepresents the impact factor ofithSN. The constantContrepresents the weight of achieving bipartite matching. If we ignore the value ofGMi,j?ISi, the weighted perfect matching will become the bipartite matching.

Gain of a single MN.The gain of MN is defined as 3-composite indicator, which refers to the throughput per distance ofjthMN via the link (i, j).

WhereBjrepresents the bandwidth ofjthMN,Duri,jrepresents link duration of link (i, j),andDisti,jrepresents the distance fromjthMN toithSN.

Impact factor of SN.The impact factor of SN is calculated by the network parameters,which represents the willingness of SN to accept MN. Two network parameters which are the spare access capacity (SAC) and the potential load (PL), are used to calculate the willingness. The larger value of willingness means that the SN is more likely to provide services for MNs. Since two network parameters have two different units, a normalization procedure is used. The normalized quality factor for all SNs is calculated as.

WhereSACiandPLiare the spare access capacity and the potential load of theithSN,respectively.

V. RESULTS

We now evaluate the performance of TDS-IRS in various scenarios. Firstly, we build a testbed with the real network devices and meanwhile interconnect that testbed with the real Internet to validate TDS-IRS. Then we conduct numerical simulations to verify the core module of TDS-IRS, i.e., WPM-TD. Finally, we scale that testbed into a large-scale emulator to analyze the network performance when WPM-TD is deployed in TDS-IRS.

5.1 Verification of TDS-IRS

In this part, we build the ITSN testbed with real network devices, and evaluate the performance of TDS-IRS compared with the modified OSPF (Open Shortest Path First protocol)/BGP (Border Gateway Protocol) [6,7] and snapshot-based routing [18,19]. The modified OSPF/BGP are the optimized terrestrial routing protocols for satellite network of ITSN,and snapshot-based routing is a classical routing scheme for traditional satellite network.

Testbed.The topology of the testbed is shown in figure 4, in which every node is a PC-based router implemented with router software Quagga [17]. Nodes S1, S2, S3 are GEO satellites, nodes G1, G2, G3 are the gateways,and nodes L1, L2 are MEO/LEO satellites.The modified OSPF is implemented in all routers, and the modified BGP is implemented between MEO/LEO satellites and GEO satellites/gateways. The testbed integrates with the real terrestrial network (CERNET2) [20] via Internet eXchange point (X1). And the whole testbed system is a pure IPv6 network.

To explore the performance of routing protocol, we set the communication between the user (User1) in such testbed and the user(User2) in the campus network of Tsinghua University, as shown in figure 4.

The implementation of TDS-IRS is based on the C/S model, as shown in figure 5. Every router has a client thread, which is a daemon thread, to act as the topology discovery sub-layer (TDS). Its functions are to receive the new network topology (NNT) sent from GCC, and to submit these messages to routing protocol and network card via the shell command. A server thread runs on the GCC, which is used to send the NNT message. Communications between clients and server are TCP sessions. The utilization of TCP can guarantee the reliability of sending NNT messages. Also,all messages are IPv6 messages.

Communication Recovery Time.We change the link connections between L1/L2 and S1…S3/G1...G3, find that modified OSPF/BGP will take about 20s to recovery the selected communication once the network topology changes. However, if we implement the snapshot-based routing scheme or our TDS-IRS, that communication will recover immediately. Note that the deployment of snapshot-based routing scheme requires us to configure the routing information of campus network user into every space node manually.

Bandwidth Overhead.During the process of recovering the communication, modified OSPF/BGP waste 128.1KB of bandwidth to discover the NNT. As the snapshot-based routing scheme needs to send the new routing table into every space node, it will waste about 159KB of bandwidth. In TDS-IRS, only 23.2KB of bandwidth will be consumed to update the NNT.

Fig. 4. Network topology of testbed.

Fig. 5. Implementation of TDS-IRS.

Storage Overhead.Snapshot-based routing scheme and our TDS-IRS will waste some memory for storing the route tables or the network topology. The snapshot-based scheme will consume about 116KB of storage for a single change, while the TDS-IRS only needs about 2.6KB of storage. According to the analysis in Section II, the number of topology changes during a day could be 9765 times during a day, the advantage of TDS-IRS as to storage and bandwidth becomes more apparent.

The summary statistics are shown in table I,we can get that TDS-IRS takes the less overhead to recover the communication immediately once the change is triggered.

5.2 Verification of WPM-TD

Simulation tools and scenarios.In this part,we will carry out the verifications of WPM-TD in the large-scale network scenario. These verifications are conducted on MATLAB software that runs on a LENOVO laptop. The experiment time is set for 24h.

Table I. Comparison of different routing schemes.

Table II. Parameters of the Selected Satellite Systems.

Table III. Network Scale of Different Network Scenarios.

The selection of network scenarios is based on the frontier research of Future ITSN proposed in [2]. The Future ITSN aims to interconnect with different satellite systems such as communications satellite systems, remote sensing satellite systems. The structure of Future ITSN consists of a backbone and many access networks. The backbone, which consists of GEO satellite and Gateway, is used to provide the global Internet access for access networks. While the access networks, which consist of Inclined Geosynchronous Orbits(ISGO), MEO and LEO satellites, are used to provide the services for users.

Some practical or proposed network systems are used to constitute the Future ITSN including Inmarsat [21], BeiDou [22], Tsinghua Space Network (rosette constellation), and Iridium [10]. Besides, we add some random IGSO/MEO/LEO satellites to represent other satellite systems. The ground gateways are set according to the core router positions of the practical network CERENT2. The detailed network parameters are shown in Table II.

As the network scale of Future ITSN system is very large, the system must be implemented step by step. We conduct the simulations with different network scales. Table III shows the different network scenarios scaling from 52 to 232.

As far as we know, there is no specialized solution for the NNT discovery. In similar scenarios, some methods have been proposed to build a new link connection when a link hand off between SN and MN occurs. Some authors [23] proposed that when a link hand off occurs, MN independently selects the SN with the shortest link distance from multiple candidate MNs. Chen [24] considered that MN independently selects the SN with largest link duration in order to decrease the number of potential topology changes. However,they all neglected the spare access capacity of candidate SNs. For analyzing the effect of the spare access capacity, we introduce another method that every MN independently selects the SN with the largest spare access capacity. For simplicity, these methods are called Distance-based, Duration-based, and Capacity-based, respectively.

Fig. 6. Comparison of WPM-TD and original existing methods.

Fig. 7. Comparison of WPM-TD and optimized existing methods.

From the comparison between WPM-TD with the existing methods shown in figure 6,we can easily get that the results of existing methods are very poor. In these methods, topology changes are triggered frequently and the number of invalid network topologies is extremely large. There are two main reasons for that.

1) The first one is the decision oscillation of MNs, which is incurred by the criteria difference between Gateways and GEO satellites. When an MN flies into the coverage of a gateway from that of GEO satellite, it wants to conduct an MRTC to select the gateway as its following SN. In the set of that MN’s candidate SNs, there may exist a GEO satellite whose criteria are better than that of all candidate gateways. As the decision of MN in the existing methods only relies on a specified criterion, the MN naturally selects the GEO satellite as its following SN. After the MN builds a link connection with the new GEO satellite,it will find that there are some gateways that it can connect with. Then the next decision process will be triggered.

2) The second reason is that neither Distance-based nor Duration-based method considers the spare access capacity of SNs into their decisions. When an MRTC occurs,the MN may select the SN without any spare access capacity as the following SN. Thus an invalid topology and additional topology changes are incurred.

There are two obvious optimizations for these issues, i.e., to let MN select the best SN only from gateways when an MN makes a decision from gateways and GEO satellites, and to notify every MN of the spare access capacity of all SNs before an MN makes a decision.

Figure 7 shows that the WPM-TD can work very well compared with the optimized existing methods. Figure 7(a) shows that, the topology changes incurred by WPM-TD are decreased about 20% ～ 57% compared with other methods. Moreover, WPM-TD always works better no matter how large the network scale is. There are two factors for that. 1) Link duration: The consideration of link duration can decrease the topology changes directly; 2)Elimination of decision Conflict: If a decision conflict occurs, there will exist one or more MNs to be removed from the ITSN. Then an extra topology change will be incurred when that MN rejoins the ITSN.

The second best method of decreasing topology changes is the Duration-based, in which MN selects the SN with the largest link duration. The selection of the largest link duration means the newly built link can maintain a long time, and thus the number of network changes is reduced.

In figure 7(b), WPM-TD decreases the invalid network topology from thousands to zero. That is because WPM-TD can avoid the decision Conflict between MNs. In other methods, the decision conflict of different MNs incurs the invalid topology changes.

Fig. 8. Throughput of the whole system.

5.3 Network performance

Emulator. To explore the network performance of TDS-IRS under different topology discovery methods, we enlarge the above small-scale testbed into a large-scale emulator by creating many virtual-routers in a PC.The Mininet software [25] is used to scale a PC-based router into many virtual PC-based routers. Every virtual router, which is a process in Linux Kernel, independently works as the real router does. It has independent system resources, such as the namespace, network card, and so on. Link connections between virtual routers are implemented by the virtual network card.

Although the emulator is based on the virtual technology, the emulation scenarios are constructed with the real world components rather than doing a simple assumption. The network parameters of emulations are shown in Table II. And the link delay is calculated according to these real network parameters, and the link bandwidth and the loss packet rate are configured as 800Mb/s and 0.012%, respectively. The MRTCs generated by topology discovery methods and these link parameters are configured into that emulator in almost real-time.

In the emulator, every node adopts the IPERF software to send the real traffic. MN runs an IPERF client, and the SN runs an IPERF server. Every MN continuously sends the 1Mb/s UDP data to the ground gateways for 1hour.All emulations are conducted on the Lenovo laptop T450 with 8G memory and 1Gb/s network card.

Performance.Figure 8 shows that WPMTD can achieve the maximum throughput of the whole network compared with the optimized existing methods. The maximum increase ratios in comparison to Duration-based,Distance-based, and Capacity-based methods are about 105%, 52%, 47%, respectively. Especially, with the network scale increasing, the increase of MPM-TC becomes better.

VI. RELATED WORKS

Currently, many routing schemes have been proposed for ITSN. According to the role of satellite network in ITSN, they can be classified into three classes.

1) Routing scheme introduced in the late 1990’s and early 2000’s considered the satellite network as a single independent network[18,19,23,24]. They abandoned the terrestrial routing protocol and designed a new routing scheme for the satellite network. For instance,the snapshot-based routing schemes [18,19], “virtual node” routing schemes [26], the multi-layer constellation routing schemes[23,24], and so on. One prominent shortcoming of such schemes is that the routing information of terrestrial network does not exist in that satellite network. Besides, the concept of our TDS-IRS is different from that of these schemes such as snapshot-based routing schemes. Although the snapshot-based routing schemes also considered thatthe routing information should be generated in advance of topology changes, they mainly considered to calculate the routing table. TDS-IRS is to generate the network topology for routing protocols, and the routing protocols are responsible for calculating routing table. In some cases that the ground control center cannot communicate with the satellite, in TDS-IRS the whole satellite network still can work as TDS-IRS can trigger routing protocols to discover network topology. Compared with the snapshot-based routing schemes, TDS-IRS can achieve the integration between satellite and terrestrial networks more easily, while at the same time decrease the overhead of on-board storage with network scale increasing.

2) In the last years, the proposed routing schemes [8, 28-30] tried to take the satellite network as the access network of terrestrial network, in which the satellites are interconnected through ground gateways. Satellites in their ISTNs are used to provide Internet access for ground users, such as the Broadband Satellite Multimedia (BSM) system [28]. The gateway acts as an essential role to interconnect satellites with terrestrial network. Users in different satellites communicate with each other via gateways. The deployment of terrestrial routing protocols is used to provide IP access for different user networks.

In that network, ETSI (European Telecommunications Standards Institute) proposed a Satellite Independent Service Access Point(SI-SAP) interface for BSM communication,which provides a hardware abstraction layer to interconnect different network devices (e.g.satellite terminals and gateways) [28]. Based on that, some terrestrial routing protocols can be employed into the satellite to provide the access of different user networks [29]. For example, applying the technology of BGP/MLPS VPN to provide the IP access for user network such as the AAL5/ATM-based network [30].

However, the hard requirement of that ITSN in the gateway implementation severely limits its ability for providing global coverage. Besides, that concept of deploying routing protocols mainly aims to interconnect satellites and user networks, in which satellite almost acts as the transparent channel. If that concept is implemented into the interconnected satellite network like the Future ITSN, the topology change between satellites may still severely damage its performance.

3) Recently, the proposed routing schemes took the satellite network as a large-scale backbone similar to the terrestrial network[2,4,6,7]. This ISTN is also the basis of this paper. In this ISTN, the satellite network is a unified network that satellites are interconnected via satellite-satellite links and satellite-gateway links. Meanwhile, the satellite network integrates with terrestrial network via one or more gateways that are within the territory. The practical systems also are the Transformational Satellite Communications System (TSAT) [1] and Future Integrated Terrestrial-Satellite Network (ITSN) [2].

For this kind of ITSN, researchers mainly focused on scaling the terrestrial routing protocols into satellite network. Their core concept is to limit the area and amount of flooding routing messages by using the precomputed network topology, such as modified OSPF [6] and modified BGP [7]. However, the current ideas mainly focused on how to modify the specified terrestrial routing protocol for specified scenarios, which severely limits the scalability of these protocols. Our TDSIRS is a generic scheme with the considerable scalability. TDS-IRS not only can be suitable for OSPF and BGP, but also it can support the implementation of other terrestrial routing protocols in various scenarios. Besides, the above schemes did not consider how to generate the reasonable network topology before the network topology changes. Our WPM-TD that is designed to generate the new network topology reasonable can cooperatively make up the neglect of these schemes.

VII. CONCLUSION

Currently, building Integrated Terrestrial-Satellite Networks (ITSN) has become ever more attractive. And the widely and successfully used terrestrial routing protocol is considered as promising protocol to achieve integration between terrestrial and satellite networks.However, the implementation of terrestrial routing protocol into ITSN is limited by the severe mobility-related topology changes(MRTCs). Once an MRTC occurs, terrestrial routing protocol needs to send many routing messages to assist all router discovering the network topology. The whole network system becomes unstable for the most system time,and many limited satellite resources, such as computing capacity, storage, and power of space router will be severely wasted.

In this paper, we firstly propose a Topology Discovery Sub-layer for ISTN Routing Scheme (TDS-IRS) to free the terrestrial routing protocol from the trouble of MRTCs by assisting routing protocol discovering NNT in advance of the occurrence of MRTC. Secondly, we formulate the NNT discovery into a generic optimization problem, and we design a Weighted Perfect Matching based Topology Discovery (WPM-TD) model to solve that optimization problem.

Finally, we build a small-scale testbed and large-scale emulator to verify TDS-IRS and its core module (WPM-TD) in different network scenarios. Results show TDS-IRS can assist routing protocol discovering the NNT immediately with the less on-board overhead, and WPM-TD can work efficiently.

ACKNOWLEDGEMENTS

This work is supported by State Key Program of National Natural Science of China(91738202), and Science &Technology Program of Beijing (Z171100005217001).

[1] Vanderpoorten J, Cohen J, Moody J et al.,“Transformational satellite communications system (TSAT) lessons learned: Perspectives from TSAT program leaders,”Proc. Military Communications, 2012, pp. 1-6

[2] Hewu Li et al., “Progress and tendency of space and earth integrated network,”Science and Technology Review,vol. 34, no. 14, 2016, pp. 95-106

[3] Etefia B et al., “Emulating a satellite router,”Proc. Aerospace, 2010, pp. 1-14

[4] Zengyin Yang et al., “Analyzing and Optimizing BGP Stability in Future Satellite Interne,”Proc.IPCCC,2017, pp. 1-8

[5] Berson S, Jin Y., “Effect of mobility on Future Satellite Packet Networks routing protocols,”Proc. Aerospace, 2009, pp. 1-6

[6] Mingwei Xu et al., “Intra-domain routing protocol OSPF+ for integrated terrestrial and space networks,”Journal of Tsinghua University (Science and Technology), vol. 57, no. 1, 2017, pp.12-17

[7] Mingwei Xu, et al., “A routing update method of border gateway protocol based on routing check,”China pattern, in http.//epub.sipo.gov.cn/patentoutline.action

[8] Train J, Etefia B, Green H., “Hub and Spoke BGP:Leveraging multicast to improve wireless inter-domain routing,”Conf. Aerospace, 2010, pp. 1-7

[9] Moy J., “Multicast extensions to OSPF,”RFC 1584, vol. 11, no. 3, 1994, pp. 82-89

[10] I. Iridium, “Iridium Satellite Communications,” inhttps.//www.iridium.com/

[11] Oneweb Company, “Oneweb Non-Geostationary Satellite System,” inhttp.//licensing.fcc.gov/myibfs/download.do?attachment_key=1134939

[12] Li B et al., “Robust Chance-Constrained Secure Transmission for Cognitive Satellite-Terrestrial Networks,”IEEE Transactions on Vehicular Tech-nology, vol. PP, vol. 99, 2018, pp. 1-1.

[13] Zhu Z et al., “Secure Beamforming Designs for Secrecy MIMO SWIPT Systems,”IEEE Wireless Communications Letters, vol. PP, no. 99, 2017,pp. 1-1

[14] Zhu Z et al., “Beamforming and Power Splitting Designs for AN-Aided Secure Multi-User MIMO SWIPT Systems,” IEEE Transactions on Information Forensics & Security, vol. 12, no. 12, 2017,pp. 2861-2874

[15] Zhu Z et al., “Outage Constrained Robust Beamforming for Secure Broadcasting Systems With Energy Harvesting,”IEEE Transactions on Wireless Communications, vol. 15, no.11, 2016,pp. 7610-7620

[16] Cook, William, and Andre Rohe. “Computing minimum-weight perfect matchings.”INFORMS journal on computing,vol. 11, no.2, 1999, pp.138-148

[17] P. Jakma and D. Lamparter, “Introduction to the quagga routing suite,”IEEE Network, vol. 28,no.2, 2014, pp. 42-48

[18] Werner, Markus. “A dynamic routing concept for ATM-based satellite personal communication networks.”IEEE Journal on Selected Areas in Communications, vol. 15, no. 8, 1997, pp. 1636-1648

[19] Werner, M, et al. “ATM-based routing in LEO/MEO satellite networks with intersatellite links,”IEEE Journal on Selected Areas in Communications, vol. 15, no. 1, 1997, pp. 69-82

[20] Tsinghua University, “CNGI-CERNET2/6IX,” inhttp.//www.tsinghua.edu.cn/publish/net/6094/index.html

[21] I. Inmarsat, “Inmarsat,” inhttps.//www.inmarsat.com/

[22] Cao Chong. “Status of COMPASS /BeiDou Development,”Stanford’s 2009 PNT Challenges and Opportunities Symposium, 2009

[23] Akyildiz, Ian F., E. Ekici, and M. D. Bender. “MLSR.a novel routing algorithm for multilayered satellite IP networks,”IEEE/ACM Transactions on Networking, vol. 10, no. 3, 2002, pp. 411-424

[24] Chen Chao, and E. Ekici. “A Routing Protocol for Hierarchical LEO/MEO Satellite IP Networks,”Wireless Networks, vol. 11, no. 4, 2005, pp. 507-521

[25] B. Lantz, B. Heller, and N. Mckeown, “A network in a laptop: rapid prototyping for software-defined networks,”Proc. Hotnets, 2010, pp. 1-6.

[26] Buehren, M., “Functions for the rectangular assignment problem,” inhttp://www.mathworks.com/matlabcentral/fileexchange/6543-functionsfor-the-rectangular-assignment-problem

[27] E. Ekici, I. F. Akyildiz, and M. D. Bender, “A distributed routing algorithm for datagram traffic in leo satellite networks,”IEEE/ACM Transactions on Networking, vol. 9, no. 2, 2001, pp. 137-147.

[28] ETSI TR 102 353. “Satellite Earth Stations and Systems (SES); Broadband Satellite Multimedia(BSM); Guidelines for the Satellite Independent Service Access Point (SI-SAP) ”, 2015, inhttp://www.etsi.org

[29] ETSI TR 102 155: “Satellite Earth Stations and Systems (SES); Broadband Satellite Multimedia;IP inter working over satellite; Addressing and routing”, 2003, inhttp://www.etsi.org

[30] ETSI TS 102 292: “Satellite Earth Stations and Systems (SES); Broadband Satellite Multimedia(BSM) services and architectures; Functional architecture for IP inter working with BSM networks”, 2015, inhttp://www.etsi.org