# An Improved DTN Scheme for Large-Scale LEO Satellite Networks

Authors: Gaosai Liu; Xinglong Jiang; Huawang Li; Siyue Sun; Zhenhua Zhang; Guang Liang
Journal: Wireless Communications and Mobile Computing
 (2023)

---

## Abstract

A large-scale low Earth orbit (LEO) satellite network has the characteristics of a complex link environment, a large number of satellites, and the limited resources of a single satellite. Applying traditional routing algorithms has disadvantages such as high overhead, high end-to-end latency, and low message delivery rate. This paper proposes an improved delay tolerant (DTN) scheme for large-scale LEO satellite networks (LIDTN) to improve transmission efficiency and reduce the resource overhead and end-to-end latency of large-scale satellite networks. This scheme improves the network performance in three aspects: next hop selection, congestion control mechanism, and acknowledgment mechanism. For the next hop selection, we propose an equivalent distance and priori knowledge-based forwarding strategy (EPFS), which has the advantages of low overhead, loop avoidance, and fast convergence. For congestion control, we put forward an emergency function-based bundle drop algorithm (EBDA). For acknowledging, we propose the virtual acknowledgment algorithm (VAA) by combining the characteristics of many path hops and high link disruption rates in large-scale constellations. Finally, we simulate and verify the LIDTN scheme on the OneWeb constellation. The results show that the LIDTN scheme is suitable for large-scale constellations, the EPFS algorithm can reduce the network overhead during data transmission, EBDA can reduce the bundle drop rate, and VAA can reduce the end-to-end latency. LIDTN provides a new solution for large-scale constellation communication.


---

## Body

## 1. Introduction

Large-scale low Earth orbit (LEO) satellite constellations have uneven service distribution, frequent link switching, and a high probability of laser link interruption [1, 2], which brings more significant challenges to the design of routing algorithms. In recent years, routing algorithms for large-scale LEO constellations have gradually become an important issue in China and abroad [3–7]. Based on link characteristics, existing constellation routing algorithms are divided into delay tolerant (DTN) and nondelay tolerant (non-DTN) routing [8]. In particular, non-DTN routing protocols for single-layer satellite networks can be subdivided into virtual topology-based and node-based routing algorithms [9–12]. Virtual topology-based routing algorithms suffer from multiple time slice divisions in large-scale constellation scenarios, leading to high routing overhead and increased packet loss rates [13]. The virtual node-based routing algorithm will also result in high switching and computational resource overhead due to many periodic routing table updates. Non-DTN protocols oriented to multilayer satellite networks use high-orbiting satellites to manage low-orbiting, increasing construction costs and complexity [14–17]. Compared with non-DTN traditional constellations routing algorithms, DTN algorithms have significant advantages in resource consumption and have long been used in deep space-oriented uncertain networks [18–21], which have more significant potential for large-scale constellations network routing. In this paper, we will fully use the regularity and orbit predictability of large-scale constellation networks, combined with the resource consumption advantage of DTN, to conduct algorithm research for large-scale single-layer LEO satellite networks.In recent years, the application of DTN in the LEO satellite network has attracted significant attention. The predictable trajectory of nodes in the network is a characteristic of satellite networks, and nodes in traditional DTN application scenarios do not have this characteristic. Existing DTN routing techniques are classified as flooding-based, quota-based, and predictive forwarding-based [22–26]. Based on the above three DTN routing algorithms, the researchers took the reduction of packet copy number and end-to-end latency as the research objective. Literature [27, 28] are early studies on the application of DTN in satellite networks. They discussed the advantages and disadvantages of DTN applications in satellite networks and concluded that DTN has higher robustness than Performance Enhancing Proxies (PEPs). Literature [29] proposes the based on throughput constrained minimum delay backup path of contact graph routing (CGR) algorithm (TCMDB_CGR) for LEO constellations characteristics by optimizing the traditional CGR algorithm, which reduces the packet loss rate and average end-to-end latency when the link bandwidth is specific. Literature [30] investigates the congestion problem in DTN for satellite networks and proposes a fragmented congestion control algorithm (FCC) that reduces the packet loss rate. However, the number of iterations is related to the number of satellite cache bundles, and the increase in the number of bundles increases the computational overhead of the satellite. In literature [31], to reduce the replication overhead and forward packets efficiently, a quasideterministic network (DQN) is proposed. However, the application scenario of this algorithm is the network without intersatellite links (ISLs), and the Earth station is required to relay the transmission of data packets. In literature [32], in order to solve the problem of high latency and low network efficiency of DTN for satellite networks, a finite replication algorithm modified prophet with limited copies (MPWLC) based on service probability is proposed to reduce network overhead and average hop count.In the above literature, the researchers consider the characteristics of satellite resource-constrained and unstable ISLs. The traditional DTN routing algorithm is optimized to make DTN more suitable for satellite networks by reducing packet replication, packet loss, and end-to-end latency. However, the application scenarios of DTN technology are mostly small-scale single-layer or multilayer constellations. There is no research on the application of large-scale single-layer LEO satellite networks. In addition, to maximize the amount of data received by the data processing center (DPC), the literature [33] designed the space-air-ground integrated network (SAGIN) model that combines LEO satellites, spacecraft, ground stations, and DPC devices, significantly increasing the amount of data received by the DPC. The storage, carrying, and forwarding mechanism in this reference is similar to DTN. In this paper, DTN technology is applied to large-scale LEO constellations for the first time, and a LIDTN scheme is proposed. The scheme reduces resource consumption and improves adaptability in large-scale LEO networks by optimizing the design of next hop selection, congestion control mechanisms, and acknowledgment mechanisms. The simulation results show that LIDTN performs better in reducing storage space and computation overhead, end-to-end latency, and bundle loss rate than traditional DTN technology. The main contributions of this article are as follows:
(1)
We are combining the characteristics of storage, carrying, and forwarding of DTN and the predictable characteristics of satellite trajectory. An end-to-end intersatellite forwarding algorithm based on equivalent distance and priori knowledge is proposed for the first time. The algorithm can effectively reduce the routing overhead of large-scale constellations, and the storage and computing overhead of the next hop calculated by a single satellite is less affected by the constellation size. The satellite using this algorithm can select the next hop according to the equivalent distance and priori knowledge without storing the topology of the entire network. When the ISL of reaching the next hop fails, this algorithm can quickly select the new next hop according to the equivalent distance and priori knowledge without flooding(2)
In order to solve the congestion problem in the DTN carrying stage, a bundle dropping algorithm based on the emergency function was proposed according to the priority and time to live (TTL) value of the bundle. This algorithm can not only minimize the dropping rate of the bundle but also provide a priori knowledge for the subsequent bundle forwarding through the acknowledgment(3)
The virtual acknowledgment algorithm for large-scale constellations is proposed for the problem of the low efficiency of existing acknowledgment algorithms. This algorithm reduces the retransmission delay of the bundle and reduces the resource overhead of retransmission due to bundles and acknowledgment packets transmission incorrect or dropped. The simulation proves that the algorithm is better in the satellite network with more hops. Therefore, this algorithm is more suitable for a large-scale constellation. This algorithm is unnecessary for small-scale satellite networks, such as constellations with average hops of less than fiveThe rest of this paper is organized as below. Section II describes the system model and completes the construction of the constellation model, the ISL model, and the Earth station model. Section III completes the problem definition of bundle forwarding, congestion control mechanism, and acknowledgment mechanism. Section IV describes the specific implementation of the LIDTN scheme. The performance of the LIDTN scheme is simulated and analyzed in section V. Finally, the paper is summarized in section VI.


## 2. System Model

This section is aimed at establishing a large-scale satellite topology and ISL model. Furthermore, three pairs of Earth stations are selected for modeling based on the geographical distribution of actual Earth stations.


### 2.1. Constellation Model

OneWeb constellation has been one of the hotspots of large-scale constellation research in recent years. The OneWeb constellation is planned to carry ISLs in the future. Therefore, the first-generation OneWeb constellation is used as the modeling object in this paper, and the parameters related to the OneWeb constellation are shown in Table1 [34, 35]. The topology of the constructed OneWeb constellation is shown in Figure 1. This paper defines the OneWeb constellation as an undirected graph G=V,E. V represents the satellite nodes and defines V=v1,1,v1,2,⋯,vn,m,⋯,vN,M. n represents the orbit number, m represents the satellite number in orbit, and there are a total of N orbits in the constellation, each with M satellites. The set of satellites located in the crossing seam is defined as v¯, v1,m∈v¯, and vN,m∈v¯. E represents the ISLs in the constellation. The Earth station is defined as ESi, and i is the Earth station label. As shown in Figure 1, the Earth station is connected to the constellation through an Earth-satellite link (ESL). Earth stations connected to different satellites are connected by ISL relay [36].Table 1
Constellation parameters.
ParametersValueType of satellitesLEOAltitude1200 kmNumber of satellites per plane36Number of planes18Eccentricity0Inclination87.9 degreesPhase5 degreesFigure 1
OneWeb constellation topology.


### 2.2. ISL Establishment Rules

As shown in Figure2, the satellites in the constellation can establish ISLs with the four surrounding satellites, which are the top and bottom satellites in the same orbit and the left and right satellites in adjacent orbits. In Figure 2, there are three types of intersatellite links: intraplane ISLs, fixed interplane ISLs, and variable interplane ISLs. During constellation operation, the satellites connected by the intraplane ISLs and the fixed interplane ISLs are fixed. The variable interplane ISLs connect the satellites on both sides of the crossing seam. The satellites connected by each variable interplane ISLs change dynamically with time. For the OneWeb constellation shown in Figure 1, the crossing seam does not affect the satellites in orbit 2 to 17. Any satellite in orbit 2 to orbit 17 can establish ISLs with the four satellites surrounding it. The orbit 1 and 18 satellites can only establish fixed ISLs with the three surrounding satellites due to the effect of the crossing seam. The satellites in orbit 1 and the satellites in orbit 18 have an unfixed ISL with each other. The ISLs of vn,m are represented as en,mx, and x represents the direction of vn,m ISLs. x=U,D,L,R,FL represents the ISLs in the up, down, left, and right directions and feeder links, respectively. The feeder link connects to the feeder satellite and the Earth station. The feeder satellite represents the satellite that directly downloads data to the Earth station.Figure 2
ISL schematic.The satellites on both sides of the crossing seam establish ISLs, which can effectively reduce the transmission delay of the bundle [37]. This paper analyzes the time to establish ISLs between the satellites on both sides of the crossing seam in one period. Due to the symmetry of satellite orbit distribution, the time of establishing ISLs between satellites on both sides of the crossing seam is analyzed by taking the example of establishing ISLs between v1,1 and each satellite in orbit 18. The orbital period of the OneWeb is 2πR+H3/GM≈6555s, where R is the Earth’s radius, H is the altitude of OneWeb from the ground, and GM is the gravitational coefficient of the Earth. The shortest distance is used as the basis for establishing the ISLs between the satellites on both sides of the crossing seam. Since the satellites are in orbit 1 and 18 in opposite directions, v1,1 has at least two opportunities to establish a link with each satellite in orbit 18 in one period. As shown in Figure 3, the start to established ISL time between v1,1 and each of the satellites in orbit 18 is shown in one run cycle. On the connection line (t1,t2,t3,⋯,tn) in Figure 3, they represent the time to establish the ISLs for the nth time. For example, the red fonts (1, 3269, and 6555) in the figure represent v1,1 establishing an ISL with v18,14 at 1 s, 3269 s, and 6555 s, respectively. v1,1 disconnects the ISL with v18,14 at 73 s and establishes a new ISL with v18,13.Figure 3
The time forv1,1 to establish an ISL with the satellites in the 18th orbit.


### 2.3. Earth Stations’ Selection

In order to verify the effectiveness of the LIDTN scheme, three pairs are selected as modeling objects among the existing ground stations in this paper. Six Earth stations are distributed on six continents, for example, choose an Earth station in Asia, Africa, Europe, Oceania, South America, and North America, respectively. The Earth stations’ names, labels, and locations are shown in Figure4. We use ES3 in Europe and ES1 in Asia, which are in the northern hemisphere, as a pair of mutual transceiver Earth stations. ES2 in South America and ES6 in Oceania in the southern hemisphere serve as a pair of mutual transceiver Earth stations. ES4 in North America, located in the northern hemisphere, and ES5 in Africa, located in the southern hemisphere, act as a pair of mutual transceiver Earth stations. The selection of access satellites for Earth stations is based on the closest distance principle. According to the satellite run cycle, the number of satellites connected to the Earth stations at a given moment is fixed. The Earth stations automatically calculate the access satellites when sending data.Figure 4
Earth station distribution.


## 2.1. Constellation Model

OneWeb constellation has been one of the hotspots of large-scale constellation research in recent years. The OneWeb constellation is planned to carry ISLs in the future. Therefore, the first-generation OneWeb constellation is used as the modeling object in this paper, and the parameters related to the OneWeb constellation are shown in Table1 [34, 35]. The topology of the constructed OneWeb constellation is shown in Figure 1. This paper defines the OneWeb constellation as an undirected graph G=V,E. V represents the satellite nodes and defines V=v1,1,v1,2,⋯,vn,m,⋯,vN,M. n represents the orbit number, m represents the satellite number in orbit, and there are a total of N orbits in the constellation, each with M satellites. The set of satellites located in the crossing seam is defined as v¯, v1,m∈v¯, and vN,m∈v¯. E represents the ISLs in the constellation. The Earth station is defined as ESi, and i is the Earth station label. As shown in Figure 1, the Earth station is connected to the constellation through an Earth-satellite link (ESL). Earth stations connected to different satellites are connected by ISL relay [36].Table 1
Constellation parameters.
ParametersValueType of satellitesLEOAltitude1200 kmNumber of satellites per plane36Number of planes18Eccentricity0Inclination87.9 degreesPhase5 degreesFigure 1
OneWeb constellation topology.


## 2.2. ISL Establishment Rules

As shown in Figure2, the satellites in the constellation can establish ISLs with the four surrounding satellites, which are the top and bottom satellites in the same orbit and the left and right satellites in adjacent orbits. In Figure 2, there are three types of intersatellite links: intraplane ISLs, fixed interplane ISLs, and variable interplane ISLs. During constellation operation, the satellites connected by the intraplane ISLs and the fixed interplane ISLs are fixed. The variable interplane ISLs connect the satellites on both sides of the crossing seam. The satellites connected by each variable interplane ISLs change dynamically with time. For the OneWeb constellation shown in Figure 1, the crossing seam does not affect the satellites in orbit 2 to 17. Any satellite in orbit 2 to orbit 17 can establish ISLs with the four satellites surrounding it. The orbit 1 and 18 satellites can only establish fixed ISLs with the three surrounding satellites due to the effect of the crossing seam. The satellites in orbit 1 and the satellites in orbit 18 have an unfixed ISL with each other. The ISLs of vn,m are represented as en,mx, and x represents the direction of vn,m ISLs. x=U,D,L,R,FL represents the ISLs in the up, down, left, and right directions and feeder links, respectively. The feeder link connects to the feeder satellite and the Earth station. The feeder satellite represents the satellite that directly downloads data to the Earth station.Figure 2
ISL schematic.The satellites on both sides of the crossing seam establish ISLs, which can effectively reduce the transmission delay of the bundle [37]. This paper analyzes the time to establish ISLs between the satellites on both sides of the crossing seam in one period. Due to the symmetry of satellite orbit distribution, the time of establishing ISLs between satellites on both sides of the crossing seam is analyzed by taking the example of establishing ISLs between v1,1 and each satellite in orbit 18. The orbital period of the OneWeb is 2πR+H3/GM≈6555s, where R is the Earth’s radius, H is the altitude of OneWeb from the ground, and GM is the gravitational coefficient of the Earth. The shortest distance is used as the basis for establishing the ISLs between the satellites on both sides of the crossing seam. Since the satellites are in orbit 1 and 18 in opposite directions, v1,1 has at least two opportunities to establish a link with each satellite in orbit 18 in one period. As shown in Figure 3, the start to established ISL time between v1,1 and each of the satellites in orbit 18 is shown in one run cycle. On the connection line (t1,t2,t3,⋯,tn) in Figure 3, they represent the time to establish the ISLs for the nth time. For example, the red fonts (1, 3269, and 6555) in the figure represent v1,1 establishing an ISL with v18,14 at 1 s, 3269 s, and 6555 s, respectively. v1,1 disconnects the ISL with v18,14 at 73 s and establishes a new ISL with v18,13.Figure 3
The time forv1,1 to establish an ISL with the satellites in the 18th orbit.


## 2.3. Earth Stations’ Selection

In order to verify the effectiveness of the LIDTN scheme, three pairs are selected as modeling objects among the existing ground stations in this paper. Six Earth stations are distributed on six continents, for example, choose an Earth station in Asia, Africa, Europe, Oceania, South America, and North America, respectively. The Earth stations’ names, labels, and locations are shown in Figure4. We use ES3 in Europe and ES1 in Asia, which are in the northern hemisphere, as a pair of mutual transceiver Earth stations. ES2 in South America and ES6 in Oceania in the southern hemisphere serve as a pair of mutual transceiver Earth stations. ES4 in North America, located in the northern hemisphere, and ES5 in Africa, located in the southern hemisphere, act as a pair of mutual transceiver Earth stations. The selection of access satellites for Earth stations is based on the closest distance principle. According to the satellite run cycle, the number of satellites connected to the Earth stations at a given moment is fixed. The Earth stations automatically calculate the access satellites when sending data.Figure 4
Earth station distribution.


## 3. Problem Definition

The LIDTN scheme proposed in this paper has three problems to be solved.(1)
vn,m selects which of the surrounding satellites as the next hop. That is the next hop selection problem(2)
How to deal with congestion during forwarding(3)
How to improve the efficiency of the acknowledgmentThe selection of the next hop directly affects link congestion and the transmission path of acknowledgments. Acknowledgments and congestion control provide a priori knowledge for subsequent next hop selection.


### 3.1. Next Hop Selection Problem

During its operation, the satellites obtain their positions in real-time through the global positioning system (GPS) and send position information to the surrounding four satellites through ISLs. The surrounding satellites (SS) are defined as those capable of establishing a direct ISL with the satellite. SSn,m represents the surrounding satellite set of vn,m. SSn,m⊆vn,mU,vn,mD,vn,mL,vn,mR, vn,mU, vn,mD, vn,mL, and vn,mR, respectively, represent the up, down, left, and right four adjacent satellites of vn,m. The position information of vn,m at moment t is defined as Ln,mt=lonn,mt,latn,mt,hn,m, in which lonn,mt and latn,mt are the longitude and latitude corresponding to the subsatellite point of vn,m at time t, and hn,m is the altitude of vn,m. The location of the ESi is defined as Li=loni,lati. The distance Dn,mi between ESi and vn,m is shown in Equation (1) [38]. The distance Dn,mn′,m′ between vn,m and vn′,m′ is shown in Equation (2), where vn′,m′∈SSn,m.
(1)Dn,mi=fv↔ESlonn,mt,latn,mt,hn,m,loni,lati,(2)Dn,mn′,m′=fv↔vlonn,mt,latn,mt,hn,m,lonn′,m′t,latn′,m′t,hn′,m′.The next hop selection is determined by the state ofvn,m. Defining the state of vn,m at moment t as Sn,mt. Sn,mt is determined by the following inputs. vn,m obtains real-time location information of SSn,m, congestion status (a priori knowledge) of SSn,m by acknowledgment factor, and queuing status of each port sent by vn,m to SSn,m. The objective of vn,m at moment t is to find the optimal strategy πn,mt,∗ to forward the bundle to one of the satellites in SSn,m. πn,mt,∗ is defined as shown in Equation (3). When the state is Sn,mt, the set of actions that vn,m can execute is An,mt. We aim to find the optimal action an,mt,∗ to achieve strategy optimality.
(3)πn,mt,∗⟵an,mt,∗Sn,mtan,mt,∗∈An,mt,An,mt=en,mt,U,en,mt,D,en,mt,L,en,mt,R,en,mt,FL.Feeder satellites have up to five selections for the next hop, and other satellites have up to four selections for the next hop. The next hop selected byvn,m at moment t is defined as Nn,mt. Nn,mt is the satellite corresponding to action an,mt,∗. For example, if an,mt,∗=en,mt,D, then Nn,mt=vn,mD. The calculation of an,mt,∗ is shown in
(4)an,mt,∗=argminan,mtdn′,m′t,j,dn′,m′t,j=Dn′,m′j+Qn,mn′m′+IB0vc+Fack,vn′,m′∈SSn,m,where dn′,m′t,j is the equivalent distance between vn′,m′ and ESj at moment t, after the unification of the dimension of quantity. Dn′,m′j is the distance between vn′,m′ and ESj. v is the data transmission rate, and c is the data propagation rate. Qn,mn′,m′ is the length of the port queue sent from vn,m to vn′,m′. B0 represents the bundle currently being processed by the satellite. IB0 represents the size of the memory space occupied by B0. Fack represents the acknowledgment factor.


### 3.2. Congestion Problem Definition

Satellite nodes cache bundles that have not received an acknowledgment. When the satellite cache space is insufficient, the bundles need to be dropped, definingCn,m and Cn,mR as the total cache capacity and the remaining cache capacity of vn,m, respectively. When Cn,mR satisfies in Equation (5), it is necessary to drop some of the bundles in the cache. ξ is the number of bundles in the cache.
(5)Cn,mR<IB0Cn,mR=Cn,m−∑i=1ξIBi.Which bundles are dropped when congestion occurs? How to mark the dropped bundles is the problem to be solved in this paper.(1)
Which bundles are dropped fromvn,m? Define the emergency function of Bi as [30]:(6)ABi=PRIiPRIi≠PRIj,1/TTLiPRIi=PRIj,i.e.ABi=PRIi,1/TTLi,where TTLi and PRIi represent the time to live and the priority of Bi, respectively. TTLj and PRIj represent the time to live and the priority of Bj, respectively. If two bundles have the same priority, that is, PRIi=PRIj, then ABi=1/TTLi. If the priorities of the two bundles are not equal, that is, PRIi≠PRIj, then ABi=PRIi. If ABi>ABj, the bundle Bj is discarded first. The initial values of priority are equal. Definitions are as follows:
(7)Bk∈B~Bks.t.ABk<AB0,k=1,2⋯ξ,where B0 represents the bundle currently being processed by the satellite. Bk represents a bundle with an emergency function value less than AB0. B~ represents the bundle set whose emergency function value of the cached bundles in the satellite is less than AB0. The relationship between Cn,mR, B0, and B~ is shown in Equation (8), where ITagB~ is the cache capacity occupied by the B~ tag after dropping the set B~. When Cn,mR+IB~=IB0+ITagB~ is satisfied, retain B0 and drop all bundles in set B~. When Cn,mR+IB~<IB0+ITagB~ is satisfied, drop B0. When Cn,mR+IB~>IB0+ITagB~ is satisfied, B0 is retained, and all or part of the bundles in set B~ is dropped.
(8)Cn,mR+IB~>IB0+ITagB~,Cn,mR+IB~<IB0+ITagB~,Cn,mR+IB~=IB0+ITagB~.How to mark the dropped bundles? This paper uses labels instead of each dropped bundle; the label composition is shown in Equation (9), where SkID represents the source node ID for sending Bk. SNk represents the sequence number of Bk. IBk represents the size of the cache capacity occupied by Bk. Tagkn denotes the nth term of Tagk.
(9)Tagk=SkID,SNk,IBkBk∈B~,SNk∈N∗,Tagk1=SkIDTagk2=SNkTagk3=IBk.To reduce the drop rate of the same bundle in the path,Tagk is sent to the next hop after dropping Bk. The next hop receives the label and updates ABk as shown in
(10)ABk=PRIk+1,1/TTLk.


### 3.3. Acknowledgment Problem Definition

In large-scale LEO networks, acknowledgment is necessary to ensure correct data transmission [39]. The destination node acknowledges the received bundle and replies with an acknowledgment packet (ACK) after decoding that the received bundle is correct. The bundle received is an incorrect reply to a negative acknowledgment packet (NACK). The theoretical time of the satellite from sending the bundle to receiving the ACK is tn,mack. tn,mack is defined as
(11)tn,mack=∑n,mR∗2Dn,mn′,m′c+Qn,mn′,m′+IB0+Packv+tn,mρ,where R∗ is the transmission path of the bundle. Pack is the ACK packet size, and tn,mρ is the vn,m processing time. n,m represents the label of the satellite, and n′,m′ is the satellite label of the next hop of vn,m. The value of n,m starts from vn,m and then takes the satellite label in the path R∗ until n,m is the last hop satellite label of the destination node. For example, the first time n,m is the label of vn,m. The second time the label of the next hop of vn,m is set to n,m and iterates until n′,m′ is the label of the last node in the path R∗.There are two main reasons why the source node does not receive anACK/NACK at the expected time. (1) The bundle is lost during transmission from the source node to the destination node. This situation is defined as E⟶. The set of satellites in the path that correctly receive the bundle is denoted as v⟶. (2) The ACK/NACK is lost during transmission from the destination node to the source node. This situation is defined as E⟵. The set of satellites in the path that correctly receive the ACK/NACK is denoted as v⟵.As shown in Equation (12), v⟶∗ represents the satellite in the path that receives the bundle closest to the destination node in case E⟶. Dn,mj denotes the distance between vn,m and the destination node ESj. vn,m is any satellite in set v⟶. v⟶∗ is the satellite corresponding to the minimum value of Dn,mj. v⟵∗ represents the satellite in the path that is closest to source node to receive the ACK/NACK in case E⟵. Dn,mi denotes the distance between vn,m and the source node ESi. vn,m is any satellite in set v⟵. v⟵∗ is the satellite corresponding to the minimum value of Dn,mi.
(12)E⟶:v⟶∗=argminvDn,mjvn,m∈v⟶,E⟵:v⟵∗=argminvDn,mivn,m∈v⟵.


## 3.1. Next Hop Selection Problem

During its operation, the satellites obtain their positions in real-time through the global positioning system (GPS) and send position information to the surrounding four satellites through ISLs. The surrounding satellites (SS) are defined as those capable of establishing a direct ISL with the satellite. SSn,m represents the surrounding satellite set of vn,m. SSn,m⊆vn,mU,vn,mD,vn,mL,vn,mR, vn,mU, vn,mD, vn,mL, and vn,mR, respectively, represent the up, down, left, and right four adjacent satellites of vn,m. The position information of vn,m at moment t is defined as Ln,mt=lonn,mt,latn,mt,hn,m, in which lonn,mt and latn,mt are the longitude and latitude corresponding to the subsatellite point of vn,m at time t, and hn,m is the altitude of vn,m. The location of the ESi is defined as Li=loni,lati. The distance Dn,mi between ESi and vn,m is shown in Equation (1) [38]. The distance Dn,mn′,m′ between vn,m and vn′,m′ is shown in Equation (2), where vn′,m′∈SSn,m.
(1)Dn,mi=fv↔ESlonn,mt,latn,mt,hn,m,loni,lati,(2)Dn,mn′,m′=fv↔vlonn,mt,latn,mt,hn,m,lonn′,m′t,latn′,m′t,hn′,m′.The next hop selection is determined by the state ofvn,m. Defining the state of vn,m at moment t as Sn,mt. Sn,mt is determined by the following inputs. vn,m obtains real-time location information of SSn,m, congestion status (a priori knowledge) of SSn,m by acknowledgment factor, and queuing status of each port sent by vn,m to SSn,m. The objective of vn,m at moment t is to find the optimal strategy πn,mt,∗ to forward the bundle to one of the satellites in SSn,m. πn,mt,∗ is defined as shown in Equation (3). When the state is Sn,mt, the set of actions that vn,m can execute is An,mt. We aim to find the optimal action an,mt,∗ to achieve strategy optimality.
(3)πn,mt,∗⟵an,mt,∗Sn,mtan,mt,∗∈An,mt,An,mt=en,mt,U,en,mt,D,en,mt,L,en,mt,R,en,mt,FL.Feeder satellites have up to five selections for the next hop, and other satellites have up to four selections for the next hop. The next hop selected byvn,m at moment t is defined as Nn,mt. Nn,mt is the satellite corresponding to action an,mt,∗. For example, if an,mt,∗=en,mt,D, then Nn,mt=vn,mD. The calculation of an,mt,∗ is shown in
(4)an,mt,∗=argminan,mtdn′,m′t,j,dn′,m′t,j=Dn′,m′j+Qn,mn′m′+IB0vc+Fack,vn′,m′∈SSn,m,where dn′,m′t,j is the equivalent distance between vn′,m′ and ESj at moment t, after the unification of the dimension of quantity. Dn′,m′j is the distance between vn′,m′ and ESj. v is the data transmission rate, and c is the data propagation rate. Qn,mn′,m′ is the length of the port queue sent from vn,m to vn′,m′. B0 represents the bundle currently being processed by the satellite. IB0 represents the size of the memory space occupied by B0. Fack represents the acknowledgment factor.


## 3.2. Congestion Problem Definition

Satellite nodes cache bundles that have not received an acknowledgment. When the satellite cache space is insufficient, the bundles need to be dropped, definingCn,m and Cn,mR as the total cache capacity and the remaining cache capacity of vn,m, respectively. When Cn,mR satisfies in Equation (5), it is necessary to drop some of the bundles in the cache. ξ is the number of bundles in the cache.
(5)Cn,mR<IB0Cn,mR=Cn,m−∑i=1ξIBi.Which bundles are dropped when congestion occurs? How to mark the dropped bundles is the problem to be solved in this paper.(1)
Which bundles are dropped fromvn,m? Define the emergency function of Bi as [30]:(6)ABi=PRIiPRIi≠PRIj,1/TTLiPRIi=PRIj,i.e.ABi=PRIi,1/TTLi,where TTLi and PRIi represent the time to live and the priority of Bi, respectively. TTLj and PRIj represent the time to live and the priority of Bj, respectively. If two bundles have the same priority, that is, PRIi=PRIj, then ABi=1/TTLi. If the priorities of the two bundles are not equal, that is, PRIi≠PRIj, then ABi=PRIi. If ABi>ABj, the bundle Bj is discarded first. The initial values of priority are equal. Definitions are as follows:
(7)Bk∈B~Bks.t.ABk<AB0,k=1,2⋯ξ,where B0 represents the bundle currently being processed by the satellite. Bk represents a bundle with an emergency function value less than AB0. B~ represents the bundle set whose emergency function value of the cached bundles in the satellite is less than AB0. The relationship between Cn,mR, B0, and B~ is shown in Equation (8), where ITagB~ is the cache capacity occupied by the B~ tag after dropping the set B~. When Cn,mR+IB~=IB0+ITagB~ is satisfied, retain B0 and drop all bundles in set B~. When Cn,mR+IB~<IB0+ITagB~ is satisfied, drop B0. When Cn,mR+IB~>IB0+ITagB~ is satisfied, B0 is retained, and all or part of the bundles in set B~ is dropped.
(8)Cn,mR+IB~>IB0+ITagB~,Cn,mR+IB~<IB0+ITagB~,Cn,mR+IB~=IB0+ITagB~.How to mark the dropped bundles? This paper uses labels instead of each dropped bundle; the label composition is shown in Equation (9), where SkID represents the source node ID for sending Bk. SNk represents the sequence number of Bk. IBk represents the size of the cache capacity occupied by Bk. Tagkn denotes the nth term of Tagk.
(9)Tagk=SkID,SNk,IBkBk∈B~,SNk∈N∗,Tagk1=SkIDTagk2=SNkTagk3=IBk.To reduce the drop rate of the same bundle in the path,Tagk is sent to the next hop after dropping Bk. The next hop receives the label and updates ABk as shown in
(10)ABk=PRIk+1,1/TTLk.


## 3.3. Acknowledgment Problem Definition

In large-scale LEO networks, acknowledgment is necessary to ensure correct data transmission [39]. The destination node acknowledges the received bundle and replies with an acknowledgment packet (ACK) after decoding that the received bundle is correct. The bundle received is an incorrect reply to a negative acknowledgment packet (NACK). The theoretical time of the satellite from sending the bundle to receiving the ACK is tn,mack. tn,mack is defined as
(11)tn,mack=∑n,mR∗2Dn,mn′,m′c+Qn,mn′,m′+IB0+Packv+tn,mρ,where R∗ is the transmission path of the bundle. Pack is the ACK packet size, and tn,mρ is the vn,m processing time. n,m represents the label of the satellite, and n′,m′ is the satellite label of the next hop of vn,m. The value of n,m starts from vn,m and then takes the satellite label in the path R∗ until n,m is the last hop satellite label of the destination node. For example, the first time n,m is the label of vn,m. The second time the label of the next hop of vn,m is set to n,m and iterates until n′,m′ is the label of the last node in the path R∗.There are two main reasons why the source node does not receive anACK/NACK at the expected time. (1) The bundle is lost during transmission from the source node to the destination node. This situation is defined as E⟶. The set of satellites in the path that correctly receive the bundle is denoted as v⟶. (2) The ACK/NACK is lost during transmission from the destination node to the source node. This situation is defined as E⟵. The set of satellites in the path that correctly receive the ACK/NACK is denoted as v⟵.As shown in Equation (12), v⟶∗ represents the satellite in the path that receives the bundle closest to the destination node in case E⟶. Dn,mj denotes the distance between vn,m and the destination node ESj. vn,m is any satellite in set v⟶. v⟶∗ is the satellite corresponding to the minimum value of Dn,mj. v⟵∗ represents the satellite in the path that is closest to source node to receive the ACK/NACK in case E⟵. Dn,mi denotes the distance between vn,m and the source node ESi. vn,m is any satellite in set v⟵. v⟵∗ is the satellite corresponding to the minimum value of Dn,mi.
(12)E⟶:v⟶∗=argminvDn,mjvn,m∈v⟶,E⟵:v⟵∗=argminvDn,mivn,m∈v⟵.


## 4. LIDTN Scheme Implementation

The LIDTN scheme proposed in this paper for large-scale LEO constellations mainly includes three algorithms. The first algorithm is equivalent distance and priori knowledge-based forwarding strategy (EPFS). This algorithm is primarily to reduce the routing overhead. The second algorithm is an emergency function-based bundle drop algorithm (EBDA). This algorithm is mainly to solve the congestion problem during bundle transmission. The third algorithm is the virtual acknowledgment algorithm (VAA). This algorithm mainly reduces the delay and overhead of the retransmission bundles.


### 4.1. Equivalent Distance and Priori Knowledge-Based Intersatellite Forwarding Strategies

As shown in Equation (4), vn,m calculates the optimal action an,mt,∗ at time t and then transmits the bundle to Nn,mt. The forwarding of vn,m to the bundle is influenced by the information flow shown in Figure 5. In the figure, Qn,mU, Qn,mD, Qn,mL, and Qn,mR are the queue lengths of the up, down, left, and right four sending ports, respectively.Figure 5
Schematic diagram of intersatellite information flow.When the bundle reachesvn,m, the following steps are performed to forward the bundle to the next hop.
(1)
Based on the receivedSSn,m position information, the distance between vn′,m′ and ESj is calculated by Equation (1), vn′,m′∈SSn,m. If vn,m∉v¯, vn,m is not in the crossing seam, SSn,m of vn,m is fixed. If vn,m∈v¯, vn,m is in the crossing seam, three satellites in set SSn,m are fixed, and the other satellite changes in a pattern similar to Figure 3(2)
The length of the port queue sent to the satellites surrounding ofvn,m is calculated and unifies the dimension of quantity of the queue length through Qn,mn′,m′+IB0/vc in Equation (4)(3)
The acknowledgment factorFack is not calculated if vn,m has not received an acknowledgment packet from vn′,m′ before. Otherwise, Fack is calculated. The value of Fack is calculated through a distance between vn,m and vn′,m′, and Tagk3 in the acknowledgment packet sent back to vn,m by vn′,m′. vn′,m′ is the next hop of vn,m.The expression of Fack is(13)Fack=1−λFack+λ∑i=1ξTagi3vc+Dn,mn′,m′0≤λ≤1,where λ denotes the smoothing factor.
(4)
The actionan,mt,∗ of vn,m is calculated by Equation (4), and an,mt,∗ is performed to forward the bundle to the next hop satellite(5)
vn,m forwards the bundle to vn′,m′. vn′,m′ performs the above four steps. The above steps are repeated until the bundle is at the destination nodeThe bundle queuing method follows the traditional first-in-first-out (FIFO) strategy, but the priority of the retransmitted bundle is higher than that of the first transmitted bundle.The bundle is forwarded according to the above process, and there is a probability of loops occurring. The two cases where loops occur are shown in Figure6. Since we use the equivalent distance forwarding bundle, Figure 6(b) has a lower probability of loop occurrence than Figure 6(a). To solve the loop problem shown in Figure 6, we propose the concept of a lock flag in the EPFS algorithm. The lock flags are set on the bundle sending ports of the satellite. When the satellite receives the bundle, the satellite will lock the port corresponding to the received bundle, and the satellite will not send the received bundle at this port. For example, in Figure 6(a), after vy receives Bi sent by vx on the left, it locks the port on the left of vy to this bundle. That is, vy cannot send the bundle through this port. This method can only avoid (Figure 6(a)) loops. For loop in Figure 6(b), the EPFS algorithm upgrades the lock flags. If the satellite receives the same bundle from a different port, the bundle is transmitted back, and the satellite that receives the returned bundle locks the port that receives the returned bundle. As shown in Figure 6(b), the up port of vb receives Bi transmitted by ve. Since there is already Bi in vb, Bi is transmitted back to ve through the up port. ve detects that the sent Bi, by computation, returns from the same port, and then, ve locks the down port for Bi. The flow of the EPFS is shown in Algorithm 1.Figure 6
Schematic diagram of the forwarding loop. (a) The first type of loop. (b) The second type of loop.
(a)(b)Algorithm 1: Equivalent distance and priori knowledge-based intersatellite forwarding strategies (EPFS).
Received bundleInput: Bundle B0, Port to receive B0: POutput: Lock flag: LF1:ifB0 received for the first time then2: LF=TURE;P is locked, and B0 cannot be forwarded through P3:else4:ifB0 is received again from the port that forwarded the B0then5:  Locks the port that receivesB0 again;6:else7:  ForwardB0 from the port where the B0 was received;8:end if9:end ifForward bundleInput: Time t, vn,m port queue Qn,mUQn,mDQn,mLQn,mR, The position of SSn,m, The position of the ESjOutput: Action an,mt,∗1:ifvn,m∈v¯then2: The ISLs betweenvn,m and the satellites moving in the opposite direction are not fixed.Calculate the satellite that is closest tovn,m in the opposite direction by equation (2)3:else4: The ISLs ofvn,m can only be established with four satellites: up, down, left, and right;5:end if6:forvn′,m′=vn,mU,vn,mD,vn,mL,vn,mRdo7:if The port forwarded by vn,m to vn′,m′ is not locked then8:  Calculate the distance betweenvn′,m′ and ESj by equation (1);9:  The normalized distance resulting from queuing is calculated by equation (4);10:ifvn,m has received the ACK from vn′,m′then11:   CalculateFack by equation (13);12:else13:Fack=0;14:end if15:  Calculatedn′,m′t,j by equation (4);16:end if17:end for18: Calculatean,mt,∗ by equation (4);vn,m forwards the bundle to vn′,m′ for the first time. vn,m cannot obtain the congestion status of vn′,m′ by the acknowledgment factor. The bundle has the probability of being dropped by vn′,m′. For this case, we will solve it in EBDA.


### 4.2. Emergency Function-Based Bundle Drop Algorithm

EBDA primarily solves the problem of congestion invn′,m′ after vn,m executes action an,mt,∗. The EBDA proposed in this paper has the following advantages. The first is the use of the emergency function ABi, which reduces the successive drops of Bi in the path and reduces the drops of Bi with small TTLi values. The second is the use of label Tagk, which replaces the larger memory space of Bk with a smaller memory capacity. Tagk3 in vn′,m′ provides a priori knowledge for an,mt,∗ of vn,m.According to the emergency function of Equation (6), all the bundles cached in the satellite have the probability of being dropped. There are two types of dropped bundles in this paper. The first type is to drop the current bundle B0 (not yet forwarded). The second type is to drop part or all of the B1,B2,⋯,Bξ. B1,B2,⋯,Bξ is stored in the cache before B0. (B1,B2,⋯,Bξ is the bundles that have been forwarded and have not yet received the acknowledgment).Those satisfyingAB0<minAB1,AB2,⋯,ABξ are the first type of bundle dropping. After dropping B0, Tag0 is used instead of B0 and updates AB0. AB0 is updated according to Equation (14). Since B0 has not been forwarded yet, dropping B0 directly will cause B0 transmission to be interrupted. Therefore, execute action an,mt,∗ and then drop B0.
(14)Tag0⟵replacedB0,Tag0=S0ID,SN0,sizeB0,AB0=PRI0,TTL0,PRI0=PRI0+1.The second bundle drop type needs to drop part or all ofB1,B2,⋯,Bξ. In the traditional method [40, 41], the bundles are dropped in first-in-first-out (FIFO) order until satisfied:
(15)Cn,mR+IB~≥IB0+ITagB~,where B~ represents the set of dropped bundles. In the literature [30], an iterative approach is used to reduce the bundle drop. The EBDA proposed in this paper can further reduce bundle dropout. In addition, using tags increases the bundle’s traceability and can provide priori knowledge for the subsequent bundle forwarding.The bundles cached in thevn,m at a certain moment are shown in Figure 7. B0 is the bundle newly received by vn,m. vn,m remaining cache space Cn,mR<IB0. Assume that AB0>AB1>⋯>ABζ−1>ABζ in Figure 7. If the bundles are dropped according to the emergency function in Equation (6), B1, B2, and B3 are dropped. Because Cn,mR+IB3>IB0+ITag3, dropping B3 alone can satisfy the cache requirements of B0. To further reduce the bundle drop, the bundles are grouped according to the value of A. The bundles cached in the vn,m are grouped as follows:
(1)
Arrange the values of the emergency function in the order from smallest to largest. Select the firstκ bundles that satisfy Equation (16).(16)Cn,mR+∑i=1κIBi−ITagi≥IB0,Cn,mR+∑i=1κ−1IBi−ITagi≤IB0,(2)
The firstκ bundles are grouped. Every ω bundles are defined as a group according to the size of the value of the emergency function. The κth bundle is in the last group. If the last group has less than ω bundles, the last group will be supplemented to ω bundles according to the value of the emergency functionFigure 7
The bundles stored in thevn,m at a certain moment.The setB~ of dropped bundles is calculated according to the flowchart of the algorithm shown in Figure 8. In the figure, B′ represents the set of bundles B1,B2,⋯,Bκ+Δω, where the emergency function value of B1,B2,⋯,Bκ is less than AB0, and the emergency function value of Bκ+1,Bκ+2,⋯,Bκ+Δω is greater than AB0. B~′ represents the temporary set variable. B~′=B~′,Bi denotes the storage of the bundle Bi into the set B~′. Bn is the set of bundles of the nth group. Each group included ω bundles. Set B′ contains κ+Δω/ω groups. floori/ω represents the integer part of i/ω. IBn represents the total cache capacity occupied by all bundles in collection Bn. argmaxBBn represents the bundle with the largest cache capacity in set Bn. B~=B~,argmaxBBn denotes storing the bundle argmaxBBn into the set B~. Figure 8 contains both internal and external iteration calculations. The internal iteration calculates the temporary set variable B~′, and the external iteration calculates the set variable B~. The condition for each end of the internal iteration is that there is sufficient capacity to store B0 after the satellite drops the bundles in set B~′. However, some bundles in set B~′ may not need to be dropped and still can meet the storage requirements of the bundle B0. Therefore, the set B~ is calculated by external iteration to reduce the number of dropped bundles on the premise of meeting the storage requirements of B0.Figure 8
Calculate setB~.The pseudocode of the EBDA algorithm is shown in Algorithm2. The labels in this algorithm will be used again in the VAA.Algorithm 2: Emergency function-based bundle drop algorithm (EBDA).
Input: Bundle: B0Output: Dropped bundles set: B~1:whileCn,mR+I (B~) < I (B0) + I (TagB~) do2:A=AB1,AB2,⋯,ABζ; The emergency function of the bundles in vn,m is deposited into A;3:B~=B~,argminBA; Store the bundle corresponding to the smallest value in A into set B~;4:  Deletes the smallest item inA;5:end while6: Follow Figure8 to find set B~ that needs to be finally dropped.7: Replace the dropped bundles with tags;


### 4.3. Virtual Acknowledgement Algorithm

The VAA proposed in this paper is applied to the following scenarios:(i)
The bundle is lost or occurs erroneously during transmission(ii)
The ACK/NACK is lost or occurs erroneously during transmissionVAA has the following advantages.(i)
Reduce the cache capacity occupied by the bundle in the satellite(ii)
Reduce end-to-end retransmission latency and acknowledgment delay(iii)
Directly provide priori knowledge for calculating the next hopVAA has different processing methods at destination nodes, relay satellites, and source nodes. The data flow of VAA in the constellation is shown schematically in Figure9. In the figure, ESi represents the source node, vn,m represents the relay satellite, and ESj represents the destination node. S1 represents the state of sending B0, and S2 represents the state of waiting for an acknowledgment after sending B0.Figure 9
Schematic diagram of the data flow of VAA.The mechanism of operation of VAA inESi is as follows. After ESi forwards B0 in state S1, it opens the timer, waits for the ACK of B0, and stores B0 in the cache. Then, ESi from S1 switches to state S2. The timer waiting for ACK in the node is defined as TIDn. n represents the sequence number of the bundle, and ID represents the node’s ID. For example, the timer waiting for the bundle B0 in vn,m is represented as Tn,m0. The timer waiting for the bundle Bn in ESi is represented as Tin.Therefore, the timer waiting for B0 in ESi is represented as Ti0. When Ti0>0 receives the ACK of B0, ESi deletes B0 in the cache. When Ti0>0 receives a NACK or Ti0≤0, ESi switchs to state S1, retransmits B0, and resets Ti0.The mechanism of operation of VAA invn,m is as follows. vn,m switches to state S2 after state S1 finishes forwarding, caching, and turning on timer Tn,m0 for B0. When Tn,m0>0 receives the ACK of B0, vn,m deletes B0 or Tag0 from the cache. The sum of the third term of all tags of vn,m is calculated by Equation (17), and ITagn,m3 is included in the ACK for forwarding. vn,m decodes B0 in the cache when NACK is received at Tn,m0>0 or Tn,m0≤0. If B0 is correct, vn,m switches to state S1, retransmits B0, resets Tn,m0, and forwards the ACK to the source node. If B0 is incorrect, remove B0 from the cache and forward the NACK to the source node.
(17)ITagn,m3=∑i=1ζTagi3.The above process deletesBi from the cache when vn,m receives the ACK of Bi. However, when ACK is lost during transmission, it triggers timeout retransmission of Bi for satellites on the path that did not receive ACK. It will cause the satellites that have received the ACK to cache and forward Bi again, resulting in resource waste. In order to solve this problem, after the relay satellite deletes the bundle corresponding to the ACK, the deleted bundle is temporarily replaced by the first two items in the bundle tag. The first two terms of the bundle tag are defined as Tagi′=SiID,SNi. Through the mapping relationship between Tagi′ and the bundle, when vn,m receives a bundle that has already replied to the ACK, it will send the ACK again but will no longer forward the bundle. Tagi′ can be deleted in two ways. The first is that vn,m again receives a bundle sent by the source node of the bundle corresponding to Tagi′. The second is that vn,m waits for time T¯n,mi after forwarding the ACK and then deletes Tagi′. The calculation formula of T¯n,mi is
(18)T¯n,mi=Tsrci−Tn,mi,where Tsrci represents the timer waiting for the ACK of Bi in the source node.In the VAA algorithm, the processing time ofACK is ignored. When the satellite receives the ACK, it is forwarded directly without considering the cache of ACK and queuing modeling of ACK.The mechanism of operation of VAA inESj is as follows. ESj receives Bi and decodes Bi. If Bi is decoded correctly, reply with an ACK. If Bi is decoded incorrectly, reply with a NACK. The pseudocode of VAA in ESi and vn,m is shown in Algorithm 3.Algorithm 3: Virtual acknowledgement algorithm (VAA).
VAA in source nodesESiInput: State S1,S2; ACK; NACK; time t1: Send bundleB0; Set the retransmission timer Ti0 according to equation (22);2:if Receive ACK of B0then3:  DeleteB0 from the cache;4:  Delete the retransmission timerTi0;5:end if6:if Receive NACK of B0 OR Ti0=0then7:  RetransmissionB0;8:  Reset the retransmission timerTi0;9:end ifVAA in relay nodesvn,mInput: State S1,S2; ACK; NACK; time t1: Forward the bundleB0; Set the retransmission timer Tn,m0 according to equation (22);2:if Received ACK of B0then3:  ReplaceB0 with Tag0′; Start timer T¯n,m0;4:  Delete the retransmission timerTn,m0;5:  CalculateITagn,m3 by (17); ACK⟵ITagn,m3;6:  Forward ACK;7:end if8:ifT¯n,m0≤0 or Received B1 //note: B1 and B0 were sent from the same source node. then9:  DeleteTag0′;10:end if11:if Received NACK of B0 OR Tn,m0=0 then12:  CalculateITagn,m3 by equation (17);13:  Check whetherB0 decoded in the cache is correct;14:ifB0 decoded correctly then15:   ACK⟵ITagn,m3; //note: Put ITagn,m3 into the ACK package.16:   RetransmissionB0; Forward ACK; Reset the retransmission timer Tn,m0;17:else18:   NACK⟵ITagn,m3; //note: Put ITagn,m3 into the NACK package.19:   DeleteB0; Forward NACK to source node ESi;20:end if21:end if


### 4.4. Scheme Analysis

In the EPFS algorithm, the satellite selects the next hop by calculating the equivalent distance and a priori knowledge. The proposed concept of a port lock flag can avoid loops in the path. EPFS algorithm does not need a routing table when forwarding bundles. After the satellite receives the bundle,an,mt,∗ is calculated, and the bundle is forwarded to the next hop. The satellite that receives the bundle later uses the same calculation method until the bundle is transmitted to the destination node. Because the equivalent distance between the satellite and the destination node is greater than that of the next hop of the satellite, theoretically, the bundles can be transmitted to the destination node 100%.Using the emergency function in the EBDA algorithm can reduce the successive drops of the same bundle in the path. Thus, the VAA based on EBDA can reduce the retransmission time due to bundle decoding errors or timeouts. As shown in Figure10, if B0 is only wrong when v1,5 is transmitted to ESj, only B0 received by ESj is incorrect. The first case in Figure 10 does not use EBDA; the satellites after v1,1 have a high probability of dropping B0 because of the lack of cache capacity. When B0 is continuously dropped, and the retransmission delay is t0r(19)t0r=t1,5j+∑i=14t1,i1,i+1,where t1,i1,i+1 is the NACK transmission delay between v1,i and v1,i+1. t1,5j is the NACK transmission delay between ESj and v1,5. The second case in Figure 10 uses EBDA. Because using the emergency function in the EBDA algorithm can increase the priority of the dropped bundle, reducing the probability of the same bundle being continuously dropped. For example, after B0 is dropped in v1,2, the priority of B0 increases, and B0 is no longer dropped in subsequent satellites. Therefore, v1,5 can retransmit B0 after receiving NACK. The B0 retransmission time delay is t0re=t1,5j. Denote B0, B1, B2, and B3 as B0:3. If B0:3 makes mistakes in the transmission process from v1,5 to ESj, B0:3 received by ESj are all incorrect. And B0 is dropped in all satellites after v1,1 because of insufficient cache capacity. The time of retransmission B0:3 without EBDA is t0:3r:
(20)t0:3r=4t1,5j+∑i=14t1,i1,i+1.Figure 10
Acknowledgement and retransmission schematics.Because the EBDA algorithm is used, the priority corresponding to the bundle will increase after the bundle is dropped, and the emergency function value will be increased. So the probability of the same bundle being continuously dropped by the satellite in the path is reduced. As shown in Figure10, suppose the bundles dropped by v1,2, v1,3, v1,4, and v1,5 are B0, B1, B2, and B3, respectively. The time to retransmit B0:B3 using EBDA is t0:3re:
(21)t0:3re=4t1,5j+t1,41,5.Becauset0:3re<t0:3r and t0re<t0r, using the EBDA + VAA algorithm can theoretically reduce the retransmission delay of destination node decoding errors.EBDA + VAA also can reduce timeout retransmission time. A timeout timerTn,m0 is set to wait for the ACK after vn,m forwards B0. The calculation of Tn,m0 is shown in Equation (22) [42]. RTT denotes round trip time, SRTT denotes the RTT after smoothing, and RTTV denotes the absolute value of SRTT−RTT after smoothing. The relay satellite transmits B0 to destination node ESj. The distance from the relay satellite to ESj is decreasing, and the RTT value is decreasing. Therefore, in Equation (12), v⟶n,m∗ retransmits the bundle in case E⟶, and v⟵n,m∗ retransmits the acknowledgment packet in case of E⟵, theoretically realizing optimality in reducing the retransmission delay.
(22)Tn,m0=SRTT+4RTTV,SRTT=1−αSRTT+αRTT,RTTV=1‐βRTTV+βRTT‐SRTT.The source node starts the retransmission timerTi0 after sending B0. After receiving B0, the relay satellite vn,m caches, forwards, and starts the retransmission timer Tn,m0. From Equation (22), Tn,m0<Ti0 can be derived. As shown in Figure 10, the retransmission B0 with No EBDA needs to wait for time T1,10. The retransmission B0 with EBDA needs to wait for time T1,50. Since T1,50<T1,10, EBDA can reduce the retransmission time of B0. If there are timeouts for retransmission of both B0:3, the time required to complete the retransmission of B0:3 in the No EBDA case is T0:3r:
(23)T0:3r=maxT1,10,T1,51,T1,52,T1,53.The time required to retransmitB0:3 using EBDA is T0:3re:
(24)T0:3re=maxT1,50,T1,51,T1,52,T1,43.From Equation (22), we can derive T0:3re<T0:3r. Thus, EBDA + VAA can reduce the timeout retransmission time.


## 4.1. Equivalent Distance and Priori Knowledge-Based Intersatellite Forwarding Strategies

As shown in Equation (4), vn,m calculates the optimal action an,mt,∗ at time t and then transmits the bundle to Nn,mt. The forwarding of vn,m to the bundle is influenced by the information flow shown in Figure 5. In the figure, Qn,mU, Qn,mD, Qn,mL, and Qn,mR are the queue lengths of the up, down, left, and right four sending ports, respectively.Figure 5
Schematic diagram of intersatellite information flow.When the bundle reachesvn,m, the following steps are performed to forward the bundle to the next hop.
(1)
Based on the receivedSSn,m position information, the distance between vn′,m′ and ESj is calculated by Equation (1), vn′,m′∈SSn,m. If vn,m∉v¯, vn,m is not in the crossing seam, SSn,m of vn,m is fixed. If vn,m∈v¯, vn,m is in the crossing seam, three satellites in set SSn,m are fixed, and the other satellite changes in a pattern similar to Figure 3(2)
The length of the port queue sent to the satellites surrounding ofvn,m is calculated and unifies the dimension of quantity of the queue length through Qn,mn′,m′+IB0/vc in Equation (4)(3)
The acknowledgment factorFack is not calculated if vn,m has not received an acknowledgment packet from vn′,m′ before. Otherwise, Fack is calculated. The value of Fack is calculated through a distance between vn,m and vn′,m′, and Tagk3 in the acknowledgment packet sent back to vn,m by vn′,m′. vn′,m′ is the next hop of vn,m.The expression of Fack is(13)Fack=1−λFack+λ∑i=1ξTagi3vc+Dn,mn′,m′0≤λ≤1,where λ denotes the smoothing factor.
(4)
The actionan,mt,∗ of vn,m is calculated by Equation (4), and an,mt,∗ is performed to forward the bundle to the next hop satellite(5)
vn,m forwards the bundle to vn′,m′. vn′,m′ performs the above four steps. The above steps are repeated until the bundle is at the destination nodeThe bundle queuing method follows the traditional first-in-first-out (FIFO) strategy, but the priority of the retransmitted bundle is higher than that of the first transmitted bundle.The bundle is forwarded according to the above process, and there is a probability of loops occurring. The two cases where loops occur are shown in Figure6. Since we use the equivalent distance forwarding bundle, Figure 6(b) has a lower probability of loop occurrence than Figure 6(a). To solve the loop problem shown in Figure 6, we propose the concept of a lock flag in the EPFS algorithm. The lock flags are set on the bundle sending ports of the satellite. When the satellite receives the bundle, the satellite will lock the port corresponding to the received bundle, and the satellite will not send the received bundle at this port. For example, in Figure 6(a), after vy receives Bi sent by vx on the left, it locks the port on the left of vy to this bundle. That is, vy cannot send the bundle through this port. This method can only avoid (Figure 6(a)) loops. For loop in Figure 6(b), the EPFS algorithm upgrades the lock flags. If the satellite receives the same bundle from a different port, the bundle is transmitted back, and the satellite that receives the returned bundle locks the port that receives the returned bundle. As shown in Figure 6(b), the up port of vb receives Bi transmitted by ve. Since there is already Bi in vb, Bi is transmitted back to ve through the up port. ve detects that the sent Bi, by computation, returns from the same port, and then, ve locks the down port for Bi. The flow of the EPFS is shown in Algorithm 1.Figure 6
Schematic diagram of the forwarding loop. (a) The first type of loop. (b) The second type of loop.
(a)(b)Algorithm 1: Equivalent distance and priori knowledge-based intersatellite forwarding strategies (EPFS).
Received bundleInput: Bundle B0, Port to receive B0: POutput: Lock flag: LF1:ifB0 received for the first time then2: LF=TURE;P is locked, and B0 cannot be forwarded through P3:else4:ifB0 is received again from the port that forwarded the B0then5:  Locks the port that receivesB0 again;6:else7:  ForwardB0 from the port where the B0 was received;8:end if9:end ifForward bundleInput: Time t, vn,m port queue Qn,mUQn,mDQn,mLQn,mR, The position of SSn,m, The position of the ESjOutput: Action an,mt,∗1:ifvn,m∈v¯then2: The ISLs betweenvn,m and the satellites moving in the opposite direction are not fixed.Calculate the satellite that is closest tovn,m in the opposite direction by equation (2)3:else4: The ISLs ofvn,m can only be established with four satellites: up, down, left, and right;5:end if6:forvn′,m′=vn,mU,vn,mD,vn,mL,vn,mRdo7:if The port forwarded by vn,m to vn′,m′ is not locked then8:  Calculate the distance betweenvn′,m′ and ESj by equation (1);9:  The normalized distance resulting from queuing is calculated by equation (4);10:ifvn,m has received the ACK from vn′,m′then11:   CalculateFack by equation (13);12:else13:Fack=0;14:end if15:  Calculatedn′,m′t,j by equation (4);16:end if17:end for18: Calculatean,mt,∗ by equation (4);vn,m forwards the bundle to vn′,m′ for the first time. vn,m cannot obtain the congestion status of vn′,m′ by the acknowledgment factor. The bundle has the probability of being dropped by vn′,m′. For this case, we will solve it in EBDA.


## 4.2. Emergency Function-Based Bundle Drop Algorithm

EBDA primarily solves the problem of congestion invn′,m′ after vn,m executes action an,mt,∗. The EBDA proposed in this paper has the following advantages. The first is the use of the emergency function ABi, which reduces the successive drops of Bi in the path and reduces the drops of Bi with small TTLi values. The second is the use of label Tagk, which replaces the larger memory space of Bk with a smaller memory capacity. Tagk3 in vn′,m′ provides a priori knowledge for an,mt,∗ of vn,m.According to the emergency function of Equation (6), all the bundles cached in the satellite have the probability of being dropped. There are two types of dropped bundles in this paper. The first type is to drop the current bundle B0 (not yet forwarded). The second type is to drop part or all of the B1,B2,⋯,Bξ. B1,B2,⋯,Bξ is stored in the cache before B0. (B1,B2,⋯,Bξ is the bundles that have been forwarded and have not yet received the acknowledgment).Those satisfyingAB0<minAB1,AB2,⋯,ABξ are the first type of bundle dropping. After dropping B0, Tag0 is used instead of B0 and updates AB0. AB0 is updated according to Equation (14). Since B0 has not been forwarded yet, dropping B0 directly will cause B0 transmission to be interrupted. Therefore, execute action an,mt,∗ and then drop B0.
(14)Tag0⟵replacedB0,Tag0=S0ID,SN0,sizeB0,AB0=PRI0,TTL0,PRI0=PRI0+1.The second bundle drop type needs to drop part or all ofB1,B2,⋯,Bξ. In the traditional method [40, 41], the bundles are dropped in first-in-first-out (FIFO) order until satisfied:
(15)Cn,mR+IB~≥IB0+ITagB~,where B~ represents the set of dropped bundles. In the literature [30], an iterative approach is used to reduce the bundle drop. The EBDA proposed in this paper can further reduce bundle dropout. In addition, using tags increases the bundle’s traceability and can provide priori knowledge for the subsequent bundle forwarding.The bundles cached in thevn,m at a certain moment are shown in Figure 7. B0 is the bundle newly received by vn,m. vn,m remaining cache space Cn,mR<IB0. Assume that AB0>AB1>⋯>ABζ−1>ABζ in Figure 7. If the bundles are dropped according to the emergency function in Equation (6), B1, B2, and B3 are dropped. Because Cn,mR+IB3>IB0+ITag3, dropping B3 alone can satisfy the cache requirements of B0. To further reduce the bundle drop, the bundles are grouped according to the value of A. The bundles cached in the vn,m are grouped as follows:
(1)
Arrange the values of the emergency function in the order from smallest to largest. Select the firstκ bundles that satisfy Equation (16).(16)Cn,mR+∑i=1κIBi−ITagi≥IB0,Cn,mR+∑i=1κ−1IBi−ITagi≤IB0,(2)
The firstκ bundles are grouped. Every ω bundles are defined as a group according to the size of the value of the emergency function. The κth bundle is in the last group. If the last group has less than ω bundles, the last group will be supplemented to ω bundles according to the value of the emergency functionFigure 7
The bundles stored in thevn,m at a certain moment.The setB~ of dropped bundles is calculated according to the flowchart of the algorithm shown in Figure 8. In the figure, B′ represents the set of bundles B1,B2,⋯,Bκ+Δω, where the emergency function value of B1,B2,⋯,Bκ is less than AB0, and the emergency function value of Bκ+1,Bκ+2,⋯,Bκ+Δω is greater than AB0. B~′ represents the temporary set variable. B~′=B~′,Bi denotes the storage of the bundle Bi into the set B~′. Bn is the set of bundles of the nth group. Each group included ω bundles. Set B′ contains κ+Δω/ω groups. floori/ω represents the integer part of i/ω. IBn represents the total cache capacity occupied by all bundles in collection Bn. argmaxBBn represents the bundle with the largest cache capacity in set Bn. B~=B~,argmaxBBn denotes storing the bundle argmaxBBn into the set B~. Figure 8 contains both internal and external iteration calculations. The internal iteration calculates the temporary set variable B~′, and the external iteration calculates the set variable B~. The condition for each end of the internal iteration is that there is sufficient capacity to store B0 after the satellite drops the bundles in set B~′. However, some bundles in set B~′ may not need to be dropped and still can meet the storage requirements of the bundle B0. Therefore, the set B~ is calculated by external iteration to reduce the number of dropped bundles on the premise of meeting the storage requirements of B0.Figure 8
Calculate setB~.The pseudocode of the EBDA algorithm is shown in Algorithm2. The labels in this algorithm will be used again in the VAA.Algorithm 2: Emergency function-based bundle drop algorithm (EBDA).
Input: Bundle: B0Output: Dropped bundles set: B~1:whileCn,mR+I (B~) < I (B0) + I (TagB~) do2:A=AB1,AB2,⋯,ABζ; The emergency function of the bundles in vn,m is deposited into A;3:B~=B~,argminBA; Store the bundle corresponding to the smallest value in A into set B~;4:  Deletes the smallest item inA;5:end while6: Follow Figure8 to find set B~ that needs to be finally dropped.7: Replace the dropped bundles with tags;


## 4.3. Virtual Acknowledgement Algorithm

The VAA proposed in this paper is applied to the following scenarios:(i)
The bundle is lost or occurs erroneously during transmission(ii)
The ACK/NACK is lost or occurs erroneously during transmissionVAA has the following advantages.(i)
Reduce the cache capacity occupied by the bundle in the satellite(ii)
Reduce end-to-end retransmission latency and acknowledgment delay(iii)
Directly provide priori knowledge for calculating the next hopVAA has different processing methods at destination nodes, relay satellites, and source nodes. The data flow of VAA in the constellation is shown schematically in Figure9. In the figure, ESi represents the source node, vn,m represents the relay satellite, and ESj represents the destination node. S1 represents the state of sending B0, and S2 represents the state of waiting for an acknowledgment after sending B0.Figure 9
Schematic diagram of the data flow of VAA.The mechanism of operation of VAA inESi is as follows. After ESi forwards B0 in state S1, it opens the timer, waits for the ACK of B0, and stores B0 in the cache. Then, ESi from S1 switches to state S2. The timer waiting for ACK in the node is defined as TIDn. n represents the sequence number of the bundle, and ID represents the node’s ID. For example, the timer waiting for the bundle B0 in vn,m is represented as Tn,m0. The timer waiting for the bundle Bn in ESi is represented as Tin.Therefore, the timer waiting for B0 in ESi is represented as Ti0. When Ti0>0 receives the ACK of B0, ESi deletes B0 in the cache. When Ti0>0 receives a NACK or Ti0≤0, ESi switchs to state S1, retransmits B0, and resets Ti0.The mechanism of operation of VAA invn,m is as follows. vn,m switches to state S2 after state S1 finishes forwarding, caching, and turning on timer Tn,m0 for B0. When Tn,m0>0 receives the ACK of B0, vn,m deletes B0 or Tag0 from the cache. The sum of the third term of all tags of vn,m is calculated by Equation (17), and ITagn,m3 is included in the ACK for forwarding. vn,m decodes B0 in the cache when NACK is received at Tn,m0>0 or Tn,m0≤0. If B0 is correct, vn,m switches to state S1, retransmits B0, resets Tn,m0, and forwards the ACK to the source node. If B0 is incorrect, remove B0 from the cache and forward the NACK to the source node.
(17)ITagn,m3=∑i=1ζTagi3.The above process deletesBi from the cache when vn,m receives the ACK of Bi. However, when ACK is lost during transmission, it triggers timeout retransmission of Bi for satellites on the path that did not receive ACK. It will cause the satellites that have received the ACK to cache and forward Bi again, resulting in resource waste. In order to solve this problem, after the relay satellite deletes the bundle corresponding to the ACK, the deleted bundle is temporarily replaced by the first two items in the bundle tag. The first two terms of the bundle tag are defined as Tagi′=SiID,SNi. Through the mapping relationship between Tagi′ and the bundle, when vn,m receives a bundle that has already replied to the ACK, it will send the ACK again but will no longer forward the bundle. Tagi′ can be deleted in two ways. The first is that vn,m again receives a bundle sent by the source node of the bundle corresponding to Tagi′. The second is that vn,m waits for time T¯n,mi after forwarding the ACK and then deletes Tagi′. The calculation formula of T¯n,mi is
(18)T¯n,mi=Tsrci−Tn,mi,where Tsrci represents the timer waiting for the ACK of Bi in the source node.In the VAA algorithm, the processing time ofACK is ignored. When the satellite receives the ACK, it is forwarded directly without considering the cache of ACK and queuing modeling of ACK.The mechanism of operation of VAA inESj is as follows. ESj receives Bi and decodes Bi. If Bi is decoded correctly, reply with an ACK. If Bi is decoded incorrectly, reply with a NACK. The pseudocode of VAA in ESi and vn,m is shown in Algorithm 3.Algorithm 3: Virtual acknowledgement algorithm (VAA).
VAA in source nodesESiInput: State S1,S2; ACK; NACK; time t1: Send bundleB0; Set the retransmission timer Ti0 according to equation (22);2:if Receive ACK of B0then3:  DeleteB0 from the cache;4:  Delete the retransmission timerTi0;5:end if6:if Receive NACK of B0 OR Ti0=0then7:  RetransmissionB0;8:  Reset the retransmission timerTi0;9:end ifVAA in relay nodesvn,mInput: State S1,S2; ACK; NACK; time t1: Forward the bundleB0; Set the retransmission timer Tn,m0 according to equation (22);2:if Received ACK of B0then3:  ReplaceB0 with Tag0′; Start timer T¯n,m0;4:  Delete the retransmission timerTn,m0;5:  CalculateITagn,m3 by (17); ACK⟵ITagn,m3;6:  Forward ACK;7:end if8:ifT¯n,m0≤0 or Received B1 //note: B1 and B0 were sent from the same source node. then9:  DeleteTag0′;10:end if11:if Received NACK of B0 OR Tn,m0=0 then12:  CalculateITagn,m3 by equation (17);13:  Check whetherB0 decoded in the cache is correct;14:ifB0 decoded correctly then15:   ACK⟵ITagn,m3; //note: Put ITagn,m3 into the ACK package.16:   RetransmissionB0; Forward ACK; Reset the retransmission timer Tn,m0;17:else18:   NACK⟵ITagn,m3; //note: Put ITagn,m3 into the NACK package.19:   DeleteB0; Forward NACK to source node ESi;20:end if21:end if


## 4.4. Scheme Analysis

In the EPFS algorithm, the satellite selects the next hop by calculating the equivalent distance and a priori knowledge. The proposed concept of a port lock flag can avoid loops in the path. EPFS algorithm does not need a routing table when forwarding bundles. After the satellite receives the bundle,an,mt,∗ is calculated, and the bundle is forwarded to the next hop. The satellite that receives the bundle later uses the same calculation method until the bundle is transmitted to the destination node. Because the equivalent distance between the satellite and the destination node is greater than that of the next hop of the satellite, theoretically, the bundles can be transmitted to the destination node 100%.Using the emergency function in the EBDA algorithm can reduce the successive drops of the same bundle in the path. Thus, the VAA based on EBDA can reduce the retransmission time due to bundle decoding errors or timeouts. As shown in Figure10, if B0 is only wrong when v1,5 is transmitted to ESj, only B0 received by ESj is incorrect. The first case in Figure 10 does not use EBDA; the satellites after v1,1 have a high probability of dropping B0 because of the lack of cache capacity. When B0 is continuously dropped, and the retransmission delay is t0r(19)t0r=t1,5j+∑i=14t1,i1,i+1,where t1,i1,i+1 is the NACK transmission delay between v1,i and v1,i+1. t1,5j is the NACK transmission delay between ESj and v1,5. The second case in Figure 10 uses EBDA. Because using the emergency function in the EBDA algorithm can increase the priority of the dropped bundle, reducing the probability of the same bundle being continuously dropped. For example, after B0 is dropped in v1,2, the priority of B0 increases, and B0 is no longer dropped in subsequent satellites. Therefore, v1,5 can retransmit B0 after receiving NACK. The B0 retransmission time delay is t0re=t1,5j. Denote B0, B1, B2, and B3 as B0:3. If B0:3 makes mistakes in the transmission process from v1,5 to ESj, B0:3 received by ESj are all incorrect. And B0 is dropped in all satellites after v1,1 because of insufficient cache capacity. The time of retransmission B0:3 without EBDA is t0:3r:
(20)t0:3r=4t1,5j+∑i=14t1,i1,i+1.Figure 10
Acknowledgement and retransmission schematics.Because the EBDA algorithm is used, the priority corresponding to the bundle will increase after the bundle is dropped, and the emergency function value will be increased. So the probability of the same bundle being continuously dropped by the satellite in the path is reduced. As shown in Figure10, suppose the bundles dropped by v1,2, v1,3, v1,4, and v1,5 are B0, B1, B2, and B3, respectively. The time to retransmit B0:B3 using EBDA is t0:3re:
(21)t0:3re=4t1,5j+t1,41,5.Becauset0:3re<t0:3r and t0re<t0r, using the EBDA + VAA algorithm can theoretically reduce the retransmission delay of destination node decoding errors.EBDA + VAA also can reduce timeout retransmission time. A timeout timerTn,m0 is set to wait for the ACK after vn,m forwards B0. The calculation of Tn,m0 is shown in Equation (22) [42]. RTT denotes round trip time, SRTT denotes the RTT after smoothing, and RTTV denotes the absolute value of SRTT−RTT after smoothing. The relay satellite transmits B0 to destination node ESj. The distance from the relay satellite to ESj is decreasing, and the RTT value is decreasing. Therefore, in Equation (12), v⟶n,m∗ retransmits the bundle in case E⟶, and v⟵n,m∗ retransmits the acknowledgment packet in case of E⟵, theoretically realizing optimality in reducing the retransmission delay.
(22)Tn,m0=SRTT+4RTTV,SRTT=1−αSRTT+αRTT,RTTV=1‐βRTTV+βRTT‐SRTT.The source node starts the retransmission timerTi0 after sending B0. After receiving B0, the relay satellite vn,m caches, forwards, and starts the retransmission timer Tn,m0. From Equation (22), Tn,m0<Ti0 can be derived. As shown in Figure 10, the retransmission B0 with No EBDA needs to wait for time T1,10. The retransmission B0 with EBDA needs to wait for time T1,50. Since T1,50<T1,10, EBDA can reduce the retransmission time of B0. If there are timeouts for retransmission of both B0:3, the time required to complete the retransmission of B0:3 in the No EBDA case is T0:3r:
(23)T0:3r=maxT1,10,T1,51,T1,52,T1,53.The time required to retransmitB0:3 using EBDA is T0:3re:
(24)T0:3re=maxT1,50,T1,51,T1,52,T1,43.From Equation (22), we can derive T0:3re<T0:3r. Thus, EBDA + VAA can reduce the timeout retransmission time.


## 5. LIDTN Scheme Simulation Results

In this section, we perform simulation experiments on the LIDTN scheme. The OneWeb constellation topology used in the simulation is shown in Figure1. The location and numbering of the Earth stations are shown in Figure 4. The paths ES1↔ES3, ES2↔ES6, and ES4↔ES5 in Figure 4 are defined as R1, R2, and R3, respectively.


### 5.1. Performance of the EPFS Algorithm

This paper analyzes the EPFS algorithm by taking the 3000th second of the constellation run period. As shown in Figures11–13, the path between the source and destination is calculated using the EPFS algorithm, Dijkstra shortest path algorithm, and Epidemic algorithm. In Figure 11, the route calculated by the EPFS algorithm and the path computed by the Dijkstra shortest path algorithm overlap entirely. That is, the path calculated by the EPFS algorithm is the shortest. The paths using the EPFS algorithm in Figures 12 and 13 partially overlap with the paths calculated by the Dijkstra algorithm, indicating that the paths calculated by the EPFS algorithm are not optimal every time. Simulations are performed for the whole constellation cycle, and the results show that the bundle can be sent from the source node to the destination node using EPFS.Figure 11
R1 schematic.Figure 12
R2 schematic.Figure 13
R3 schematic.Figure14 shows the number of satellites that need to be involved for one routing based on the Dijkstra algorithm, Epidemic algorithm, and EPFS algorithm. This figure shows that the Dijkstra routing algorithm requires each satellite to be informed of the status of 648 satellites in the constellation. The EPFS algorithm, on the other hand, enables the transmission of the bundle with the least amount of knowledge of the constellation satellite state. As the distance between the source and destination nodes increases, the number of participating satellites required by the EPFS algorithm varies less. The Epidemic algorithm has a large variation in the number of satellites needed to participate as the distance increases.Figure 14
The number of satellites to be involved using different algorithms on different paths.To verify the delay of the EPFS algorithm, the transmission rate is set to 0.8 Mpbs-1.2 Mpbs, the size of each bundle is set to 1 KByte-2 Kbyte, and the link failure rate is set to 1%-5%. The Contact Graph Routing (CGR) [19] algorithm is forwarded only as a single copy. Figure 15 shows the experimental results of CGR, Enhanced Contact Graph Routing (ECGR) [43], Adaptive Message Replication Technique (AMRT) [44], and EPFS algorithms. The experimental results show that the EPFS algorithm is more advanced than other algorithms. The experimental results of the ECGR algorithm and CGR algorithm are not much different. The AMRT algorithm is superior to ECGR and CGR, because the AMRT algorithm considers historical congestion when selecting the next hop. The EPFS algorithm proposed by this paper is superior to the other three algorithms in terms of delay. This is because the EPFS algorithm equivalents the queue length to distance and obtains the link state to the next hop in real-time according to priori knowledge. When the link fails, the EPFS algorithm can avoid it in time.Figure 15
Average time delay of different algorithms.


### 5.2. Performance of the EBDA

In this experiment, we set the size of each bundle to be 1-20 M. Five bundles with similar emergency functions are used as a group. The probability of link congestion ranges from 2% to 30%. As shown in Figure16, the relationship between the average congestion probability and the bundle drop rate for the three algorithms, FIFO, FCC, and EBDA, in the R1, R2, and R3 paths is shown. The red curve shows the variation of the bundle drop rate with congestion probability for the EBDA algorithm in the three paths. The blue curve represents the traditional FIFO bundle dropping algorithm. The black curve represents the FCC algorithm. From Figure 16, the EBDA algorithm has the lowest drop rate of the bundle for the same congestion probability. As the congestion probability increases, the pronounced advantage of the EBDA algorithm (Table 2) shows the 15% probability of congestion, R1, R2, and R3 paths, with the occurrence of congested satellites.Figure 16
The average drop rate ofR1, R2, and R3 paths in different congestion probability.Table 2
Satellites with congestion occurring in one of the simulations at 15% probability of congestion.
RouteCongestion satellitesR1v04,32v01,32v16,22R2v11,09v11,08R3v18,26v18,23v18,21v18,18


### 5.3. Performance of the VAA

In this simulation, the VAA algorithm is compared with the traditional acknowledgment algorithm and the No-Stop-Wait ACK proposed in literature [39]. The traditional acknowledgment algorithm uses the acknowledgment method in TCP/IP. As shown in Figure 17, the VAA algorithm is compared with the end-to-end latency of the traditional acknowledgment method with the maximum bundle loss rate of 6% (Figure 17(a)), 10% (Figure 17(b)), 20% (Figure 17(c)), and 30% (Figure 17(d)) of the ISLs, respectively. The retransmission timing is calculated iteratively according to Equation (22), with α and β set to 0.5. The red curve in the figure represents the VAA algorithm. The blue curve represents the traditional acknowledgment algorithm. The black curve represents the end-to-end latency multiplier reduction of the VAA algorithm over the traditional acknowledgment algorithm. From Figure 17, the VAA algorithm has more significant advantages with increased link bundle loss rate and path hop count. When the maximum bundle loss rate of the ISLs is 10%, the VAA algorithm reduces the end-to-end latency by about 1.4 times compared to the traditional acknowledgment algorithm. When the maximum ISL bundle loss rate is 30%, the VAA algorithm reduces the end-to-end latency by about 2.4 times compared to the traditional acknowledgment algorithm.Figure 17
End-to-end delay variation with hop count under different ISL loss rates. (a) The maximum packet loss rate of 6% of the ISLs. (b) The maximum bundle loss rate of 10% of the ISLs. (c) The maximum bundle loss rate of 20% of the ISLs. (d) The maximum bundle loss rate of 30% of the ISLs.
(a)(b)(c)(d)In the No-Stop-Wait ACK strategy in literature [39], packets are sent without waiting for an acknowledgment to continue sending packets. After a certain number of packages are sent, the destination satellite acknowledges them uniformly. This strategy reduces the time consumption caused by each acknowledgment and reduces the end-to-end latency. Figure 18 compares the No-Stop-Wait ACK strategy and VAA + No-Stop-Wait ACK optimized with the VAA algorithm. Figure 18(a) shows a group of three bundles, and the destination node replies after sending three consecutive bundles. Figure 18(b) shows a group of five bundles. The destination node responds with an acknowledgment after receiving five consecutive bundles. From Figure 18, as the number of hops on the paths increases, the use of VAA optimization can reduce the end-to-end latency when transmission errors occur in each group of bundles. The more the number of hops, the better the effect of the VAA algorithm.Figure 18
Comparison of end-to-end latency of VAA + No-Stop-Wait ACK and No-Stop-Wait ACK. (a) A group contains three bundles. (b) A group contains five bundles.
(a)(b)


## 5.1. Performance of the EPFS Algorithm

This paper analyzes the EPFS algorithm by taking the 3000th second of the constellation run period. As shown in Figures11–13, the path between the source and destination is calculated using the EPFS algorithm, Dijkstra shortest path algorithm, and Epidemic algorithm. In Figure 11, the route calculated by the EPFS algorithm and the path computed by the Dijkstra shortest path algorithm overlap entirely. That is, the path calculated by the EPFS algorithm is the shortest. The paths using the EPFS algorithm in Figures 12 and 13 partially overlap with the paths calculated by the Dijkstra algorithm, indicating that the paths calculated by the EPFS algorithm are not optimal every time. Simulations are performed for the whole constellation cycle, and the results show that the bundle can be sent from the source node to the destination node using EPFS.Figure 11
R1 schematic.Figure 12
R2 schematic.Figure 13
R3 schematic.Figure14 shows the number of satellites that need to be involved for one routing based on the Dijkstra algorithm, Epidemic algorithm, and EPFS algorithm. This figure shows that the Dijkstra routing algorithm requires each satellite to be informed of the status of 648 satellites in the constellation. The EPFS algorithm, on the other hand, enables the transmission of the bundle with the least amount of knowledge of the constellation satellite state. As the distance between the source and destination nodes increases, the number of participating satellites required by the EPFS algorithm varies less. The Epidemic algorithm has a large variation in the number of satellites needed to participate as the distance increases.Figure 14
The number of satellites to be involved using different algorithms on different paths.To verify the delay of the EPFS algorithm, the transmission rate is set to 0.8 Mpbs-1.2 Mpbs, the size of each bundle is set to 1 KByte-2 Kbyte, and the link failure rate is set to 1%-5%. The Contact Graph Routing (CGR) [19] algorithm is forwarded only as a single copy. Figure 15 shows the experimental results of CGR, Enhanced Contact Graph Routing (ECGR) [43], Adaptive Message Replication Technique (AMRT) [44], and EPFS algorithms. The experimental results show that the EPFS algorithm is more advanced than other algorithms. The experimental results of the ECGR algorithm and CGR algorithm are not much different. The AMRT algorithm is superior to ECGR and CGR, because the AMRT algorithm considers historical congestion when selecting the next hop. The EPFS algorithm proposed by this paper is superior to the other three algorithms in terms of delay. This is because the EPFS algorithm equivalents the queue length to distance and obtains the link state to the next hop in real-time according to priori knowledge. When the link fails, the EPFS algorithm can avoid it in time.Figure 15
Average time delay of different algorithms.


## 5.2. Performance of the EBDA

In this experiment, we set the size of each bundle to be 1-20 M. Five bundles with similar emergency functions are used as a group. The probability of link congestion ranges from 2% to 30%. As shown in Figure16, the relationship between the average congestion probability and the bundle drop rate for the three algorithms, FIFO, FCC, and EBDA, in the R1, R2, and R3 paths is shown. The red curve shows the variation of the bundle drop rate with congestion probability for the EBDA algorithm in the three paths. The blue curve represents the traditional FIFO bundle dropping algorithm. The black curve represents the FCC algorithm. From Figure 16, the EBDA algorithm has the lowest drop rate of the bundle for the same congestion probability. As the congestion probability increases, the pronounced advantage of the EBDA algorithm (Table 2) shows the 15% probability of congestion, R1, R2, and R3 paths, with the occurrence of congested satellites.Figure 16
The average drop rate ofR1, R2, and R3 paths in different congestion probability.Table 2
Satellites with congestion occurring in one of the simulations at 15% probability of congestion.
RouteCongestion satellitesR1v04,32v01,32v16,22R2v11,09v11,08R3v18,26v18,23v18,21v18,18


## 5.3. Performance of the VAA

In this simulation, the VAA algorithm is compared with the traditional acknowledgment algorithm and the No-Stop-Wait ACK proposed in literature [39]. The traditional acknowledgment algorithm uses the acknowledgment method in TCP/IP. As shown in Figure 17, the VAA algorithm is compared with the end-to-end latency of the traditional acknowledgment method with the maximum bundle loss rate of 6% (Figure 17(a)), 10% (Figure 17(b)), 20% (Figure 17(c)), and 30% (Figure 17(d)) of the ISLs, respectively. The retransmission timing is calculated iteratively according to Equation (22), with α and β set to 0.5. The red curve in the figure represents the VAA algorithm. The blue curve represents the traditional acknowledgment algorithm. The black curve represents the end-to-end latency multiplier reduction of the VAA algorithm over the traditional acknowledgment algorithm. From Figure 17, the VAA algorithm has more significant advantages with increased link bundle loss rate and path hop count. When the maximum bundle loss rate of the ISLs is 10%, the VAA algorithm reduces the end-to-end latency by about 1.4 times compared to the traditional acknowledgment algorithm. When the maximum ISL bundle loss rate is 30%, the VAA algorithm reduces the end-to-end latency by about 2.4 times compared to the traditional acknowledgment algorithm.Figure 17
End-to-end delay variation with hop count under different ISL loss rates. (a) The maximum packet loss rate of 6% of the ISLs. (b) The maximum bundle loss rate of 10% of the ISLs. (c) The maximum bundle loss rate of 20% of the ISLs. (d) The maximum bundle loss rate of 30% of the ISLs.
(a)(b)(c)(d)In the No-Stop-Wait ACK strategy in literature [39], packets are sent without waiting for an acknowledgment to continue sending packets. After a certain number of packages are sent, the destination satellite acknowledges them uniformly. This strategy reduces the time consumption caused by each acknowledgment and reduces the end-to-end latency. Figure 18 compares the No-Stop-Wait ACK strategy and VAA + No-Stop-Wait ACK optimized with the VAA algorithm. Figure 18(a) shows a group of three bundles, and the destination node replies after sending three consecutive bundles. Figure 18(b) shows a group of five bundles. The destination node responds with an acknowledgment after receiving five consecutive bundles. From Figure 18, as the number of hops on the paths increases, the use of VAA optimization can reduce the end-to-end latency when transmission errors occur in each group of bundles. The more the number of hops, the better the effect of the VAA algorithm.Figure 18
Comparison of end-to-end latency of VAA + No-Stop-Wait ACK and No-Stop-Wait ACK. (a) A group contains three bundles. (b) A group contains five bundles.
(a)(b)


## 6. Conclusion

This paper proposes a new LIDTN scheme suitable for large-scale constellation data transmission. First, the next hop to which the bundles will be forwarded is determined based on the equivalent distance and priori knowledge. Second, a bundle drop algorithm based on the emergency function is proposed to solve the congestion problem in the bundle forwarding process. Finally, a virtual acknowledgment algorithm is proposed to reduce the retransmission time and retransmission overhead. The EPFS algorithm provides data input for the EBDA and VAA algorithms, and the EBDA and VAA algorithms provide a priori knowledge for the EPFS algorithm. The three algorithms of the LIDTN scheme complement each other and adaptively solve the problems of bundles forwarding, congestion, and acknowledgment. Simulation results show that the LIDTN scheme is effective. In space-based networks with high link failure rates, the EPFS, EBDA, and VAA algorithms offer better performance than existing methods.In future research, we will further optimize the LIDTN scheme so that the LIDTN scheme can be applied to large-scale multilayer polar/inclined orbit constellations.



---

*Source: 4899124-2023-02-21.xml*