Load-balancing routing algorithms for service congestion avoidance in LEO optical satellite networks

Yunxiao Ning; Longteng Yi; Yongli Zhao; Kaiqiang Qi; Hua Wang; Sabidur Rahman; Jie Zhang

doi:10.1364/JOCN.489919

Journal of Optical Communications and Networking
Vol. 15,
Issue 12,
pp. 1038-1049
(2023)
•https://doi.org/10.1364/JOCN.489919

Load-balancing routing algorithms for service congestion avoidance in LEO optical satellite networks

Yunxiao Ning, Longteng Yi, Yongli Zhao, Kaiqiang Qi, Hua Wang, Sabidur Rahman, and Jie Zhang

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Yunxiao Ning, Longteng Yi, Yongli Zhao, Kaiqiang Qi, Hua Wang, Sabidur Rahman, and Jie Zhang, "Load-balancing routing algorithms for service congestion avoidance in LEO optical satellite networks," J. Opt. Commun. Netw. 15, 1038-1049 (2023)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Abstract

The low-Earth-orbit optical satellite network (LOSN) is an attractive solution to realize the end-to-end service quality of large-scale services, and it is the basis of establishing the 6G mobile network with high throughput and high reliability. However, the current LOSN is practically unable to achieve such high throughput for global service access. First, the centralized deployment of ground gateways will cause a heavy traffic load in the space segment of the LOSN, which becomes the bottleneck constraining the further growth of network throughput. Second, the high-speed movement of LEO satellites will cause continuous movement of traffic load, which will affect the scalability of routing computing. In this paper, two routing algorithms are proposed to increase the throughput in the dynamic LOSN topology. The congestion-aware load balancing (CALB) algorithm is proposed to address the inter-satellite link congestion in the dynamic LOSN topology. Then, a load-balancing routing algorithm based on satellite–ground cooperation (SGC-LB) is proposed to further reduce the impact of the network bottleneck. To evaluate the performance of the proposed routing algorithm, extensive simulations were performed on a 288-satellite Walker-Star constellation with inter-satellite links. The service blockage rate and network bandwidth utilization rate are evaluated showing the effectiveness of the proposed routing algorithm. The network using the SGC-LB algorithm can accommodate 60.00%, 56.00%, 42.22%, and 33.33% more services than using the Shortest Path algorithm, Sway algorithm, CALB algorithm, and Anycast algorithm, respectively, with zero service congestion during the simulation. The SGC-LB also gains a 6.04%, 5.00%, 5.04%, and 0.77% higher network utilization rate than the Shortest Path, Sway, CALB, and Anycast algorithms, respectively.

Full Article | PDF Article

More Like This

Deep-learning-based path computation without routing convergence in optical satellite networks

Yinji Jing, Longteng Yi, Yongli Zhao, Hua Wang, Wei Wang, and Jie Zhang
J. Opt. Commun. Netw. 15(5) 294-303 (2023)

Gravity-based network traffic abstraction and laser ON/OFF control in optical satellite networks

Wei Wang, Yuanjian Zhang, Yongli Zhao, Kexin Gao, Liyazhou Hu, and Jie Zhang
J. Opt. Commun. Netw. 15(12) 958-968 (2023)

Joint RMSSA scheme and link load balancing for static SD-SCNs from model building to algorithm design

Xin Yang and Qiang Sun
J. Opt. Commun. Netw. 15(8) 527-540 (2023)

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (8)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (4)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Equations (11)

You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Notes	Explanation
$S$	$s \in S$ represents a topology state during a time period.
$G^{s}$	$G^{s} = (V, E^{s})$ is a graph that represents the topology of slice $s$ .
$V$	$V = {v_{1}, v_{2}, \dots, v_{m}} = {V_{n} \cup V_{m - n}}, (V_{n} \cap V_{m - n} = \emptyset)$ is the set of $m$ LOSN nodes.
$V_{n}$	$V_{n}$ represents $n$ satellites in the space part.
$V_{m - n}$	$V_{m - n}$ represents $(m - n)$ ground gateways.
$E^{s}$	$E^{s}$ represents the set of directional links of the current slice.
$C^{s}$	$C^{s}$ represents the capacity of directional links of the current slice .
$B_{a c c}, B_{i s l}, B_{f e e d}$	$B_{a c c}$ , $B_{i s l}$ , and $B_{f e e d}$ are the bandwidth of the access link, the ISL, and the feed link, respectively.
$c_{e}$	$c_{e} \in C^{s}$ represents the available bandwidth of the link $e \in E^{s}$ .
$D^{a l l}$	$D^{a l l}$ denotes all service demands of the simulation.
$D^{s}$	$D^{s}$ denotes the set of service demands of slice $s$ .
${s_{d}, t_{d}}$	${s_{d}, t_{d}}$ denotes the source-destination pair of service demand $d \in D^{s}$ .
$b_{d}$	$b_{d}$ denotes the bandwidth requirement of service demand $d \in D^{s}$ .
$P_{d}^{s}$	$P_{d}^{s}$ denotes the set of candidate paths from $s_{d}$ to $t_{d}$ in slice $s$ .
$S_{d}$	$S_{d} \subseteq S$ represents the slices in which demand $d$ will be transmitted.
$x_{d}^{s}$	$x_{d p}^{s} \in {0, 1}$ denotes whether path $p \in P_{d}^{s}$ is selected for service demand $d \in D^{s}$ .
$y_{d e}^{s}$	$y_{d e}^{s} \in {0, 1}$ denotes whether link $e \in E^{s}$ is used by service demand $d \in D^{s}$ .
$f_{d e}^{s}$	$f_{d e}^{s}$ denotes the bandwidth used by service demand $d \in D^{s}$ on link $e \in E^{s}$ .

Parameters	Values
Constellation type	Walker-Star
The number of satellites	288
Orbital planes	12
Satellites per orbit	24
Altitude	1050 km
Inclination	89°
RAAN	180°
Phase factor	3
Number of ground gateways	16
Number of user terminals	100
The bandwidth of ISL	10 Gbit/s
The bandwidth of feedback link	16 Gbit/s
Simulation duration	120 min
Simulation step	1 s
Number of service requests	Static model: [3,6,600,700]; Hybrid model: 13,000
Source of a service request	Random user terminals
Destination of a service request	Random ground gateways
Last time of a service	120 min
Service request bandwidth	50 Mbit/s

Notes	Explanation
$S$	$s \in S$ represents a topology state during a time period.
$G^{s}$	$G^{s} = (V, E^{s})$ is a graph that represents the topology of slice $s$ .
$V$	$V = {v_{1}, v_{2}, \dots, v_{m}} = {V_{n} \cup V_{m - n}}, (V_{n} \cap V_{m - n} = \emptyset)$ is the set of $m$ LOSN nodes.
$V_{n}$	$V_{n}$ represents $n$ satellites in the space part.
$V_{m - n}$	$V_{m - n}$ represents $(m - n)$ ground gateways.
$E^{s}$	$E^{s}$ represents the set of directional links of the current slice.
$C^{s}$	$C^{s}$ represents the capacity of directional links of the current slice .
$B_{a c c}, B_{i s l}, B_{f e e d}$	$B_{a c c}$ , $B_{i s l}$ , and $B_{f e e d}$ are the bandwidth of the access link, the ISL, and the feed link, respectively.
$c_{e}$	$c_{e} \in C^{s}$ represents the available bandwidth of the link $e \in E^{s}$ .
$D^{a l l}$	$D^{a l l}$ denotes all service demands of the simulation.
$D^{s}$	$D^{s}$ denotes the set of service demands of slice $s$ .
${s_{d}, t_{d}}$	${s_{d}, t_{d}}$ denotes the source-destination pair of service demand $d \in D^{s}$ .
$b_{d}$	$b_{d}$ denotes the bandwidth requirement of service demand $d \in D^{s}$ .
$P_{d}^{s}$	$P_{d}^{s}$ denotes the set of candidate paths from $s_{d}$ to $t_{d}$ in slice $s$ .
$S_{d}$	$S_{d} \subseteq S$ represents the slices in which demand $d$ will be transmitted.
$x_{d}^{s}$	$x_{d p}^{s} \in {0, 1}$ denotes whether path $p \in P_{d}^{s}$ is selected for service demand $d \in D^{s}$ .
$y_{d e}^{s}$	$y_{d e}^{s} \in {0, 1}$ denotes whether link $e \in E^{s}$ is used by service demand $d \in D^{s}$ .
$f_{d e}^{s}$	$f_{d e}^{s}$ denotes the bandwidth used by service demand $d \in D^{s}$ on link $e \in E^{s}$ .

Parameters	Values
Constellation type	Walker-Star
The number of satellites	288
Orbital planes	12
Satellites per orbit	24
Altitude	1050 km
Inclination	89°
RAAN	180°
Phase factor	3
Number of ground gateways	16
Number of user terminals	100
The bandwidth of ISL	10 Gbit/s
The bandwidth of feedback link	16 Gbit/s
Simulation duration	120 min
Simulation step	1 s
Number of service requests	Static model: [3,6,600,700]; Hybrid model: 13,000
Source of a service request	Random user terminals
Destination of a service request	Random ground gateways
Last time of a service	120 min
Service request bandwidth	50 Mbit/s

Algorithm: Congestion Aware Load Balancing Algorithm
Input: Topology of the current time slice $G^{s} = (V, E^{s})$ , capacity $C$ , the set of service demand $D^{s}$ , and available bandwidth $C^{s}$ .
Output: Service path set $P (D^{s})$ and available bandwidth $C^{s}$ .
1: set $P (D^{s}) = {empty}$ ;
2: forall $d \in D^{s}$ in order do:
3: set $p = {empty}$ ;
4: if $(s_{d} \in V & t_{d} \in V) == TRUE$ then
5: forall $e \in E_{s}$ in order do
6: if $c_{e} \leq b_{d}$ then
7: remove $e$ from $C^{s}$ and $C$ ;
8: End
9: End
10: set weight matrix $W$ according to $C - C^{s}$ ;
11: $p = Dijkstra (W, s_{d}, t_{d})$ ;
12: if $is empty (p) == TRUE$ then
13: service demand $d$ is blocked;
14: else # assign link bandwidth for $d$ .
15: forall $e \in p$ then
16: $c_{e} = c_{e} - b_{d}$ ;
17: End
18: End
19: Else
20: service demand $d$ is blocked in slice $s$ ;
21: End
22: $P (D^{s}) = P (D^{s}) \cup p$ ; # record the route;
23: End

Algorithm: Load-Balancing Routing Algorithm Based on Satellite–Ground Cooperation
Input: Topology of the current time slice $G^{s} = (V, E^{s})$ , capacity $C$ , a set of service demand $D^{s}$ , available bandwidth $C^{s}$ , and reachability matrix $A$ .
Output: Service path set $P (D^{s})$ and available bandwidth $C^{s}$ .
1: set $P (D^{s}) = {empty}$ ;
2: forall $d \in D^{s}$ in order do:
3: set $p = {empty}$ ;
4: if $(s_{d} \in V & t_{d} \in V) == TRUE$ then
5: if $A (s_{d}, t_{d}) \neq 1$ and $altered (d) 2$ then
6: do Step 20–28 of this program;
7: Else
8: forall $e \in E_{s}$ in order do
9: if $c_{e} \leq b_{d}$ then
10: remove $e$ from $C^{s}$ and $C$ ;
11: End
12: End
13: set weight $W$ according to $C - C^{s}$ ;
14: $p = Dijkstra (W, s_{d}, t_{d})$ ;
15: if $is empty (p) == FALSE$ then
# assign link bandwidth for $b$
16: forall $e \in p$ then
17: $c_{e} = c_{e} - b_{d}$ ;
18: end
19: elseif $altered (d) 2$
20: set $A (s_{d}, t_{d}) = 0$ ;
21: find $t^{'} \in V_{m - n}$ , such that
$L (t^{'}) \leq L (v), \forall v \in V_{m - n}$ ;
22: $p = Dijkstra (W, s_{d}, t^{'})$ ;
23: if $is empty (p) == TRUE$ then
24: $d$ is blocked in slice $s$ ;
25: Else
26: set $altered (d) + = 1$ ;
27: do Step 16–18;
28: End
29: Else
30: $d$ is blocked in slice $s$ ;
31: End
32: End
33: Else
34: service demand $d$ is blocked;
35: End

Algorithm: Congestion Aware Load Balancing Algorithm
Input: Topology of the current time slice $G^{s} = (V, E^{s})$ , capacity $C$ , the set of service demand $D^{s}$ , and available bandwidth $C^{s}$ .
Output: Service path set $P (D^{s})$ and available bandwidth $C^{s}$ .
1: set $P (D^{s}) = {empty}$ ;
2: forall $d \in D^{s}$ in order do:
3: set $p = {empty}$ ;
4: if $(s_{d} \in V & t_{d} \in V) == TRUE$ then
5: forall $e \in E_{s}$ in order do
6: if $c_{e} \leq b_{d}$ then
7: remove $e$ from $C^{s}$ and $C$ ;
8: End
9: End
10: set weight matrix $W$ according to $C - C^{s}$ ;
11: $p = Dijkstra (W, s_{d}, t_{d})$ ;
12: if $is empty (p) == TRUE$ then
13: service demand $d$ is blocked;
14: else # assign link bandwidth for $d$ .
15: forall $e \in p$ then
16: $c_{e} = c_{e} - b_{d}$ ;
17: End
18: End
19: Else
20: service demand $d$ is blocked in slice $s$ ;
21: End
22: $P (D^{s}) = P (D^{s}) \cup p$ ; # record the route;
23: End

Algorithm: Load-Balancing Routing Algorithm Based on Satellite–Ground Cooperation
Input: Topology of the current time slice $G^{s} = (V, E^{s})$ , capacity $C$ , a set of service demand $D^{s}$ , available bandwidth $C^{s}$ , and reachability matrix $A$ .
Output: Service path set $P (D^{s})$ and available bandwidth $C^{s}$ .
1: set $P (D^{s}) = {empty}$ ;
2: forall $d \in D^{s}$ in order do:
3: set $p = {empty}$ ;
4: if $(s_{d} \in V & t_{d} \in V) == TRUE$ then
5: if $A (s_{d}, t_{d}) \neq 1$ and $altered (d) 2$ then
6: do Step 20–28 of this program;
7: Else
8: forall $e \in E_{s}$ in order do
9: if $c_{e} \leq b_{d}$ then
10: remove $e$ from $C^{s}$ and $C$ ;
11: End
12: End
13: set weight $W$ according to $C - C^{s}$ ;
14: $p = Dijkstra (W, s_{d}, t_{d})$ ;
15: if $is empty (p) == FALSE$ then
# assign link bandwidth for $b$
16: forall $e \in p$ then
17: $c_{e} = c_{e} - b_{d}$ ;
18: end
19: elseif $altered (d) 2$
20: set $A (s_{d}, t_{d}) = 0$ ;
21: find $t^{'} \in V_{m - n}$ , such that
$L (t^{'}) \leq L (v), \forall v \in V_{m - n}$ ;
22: $p = Dijkstra (W, s_{d}, t^{'})$ ;
23: if $is empty (p) == TRUE$ then
24: $d$ is blocked in slice $s$ ;
25: Else
26: set $altered (d) + = 1$ ;
27: do Step 16–18;
28: End
29: Else
30: $d$ is blocked in slice $s$ ;
31: End
32: End
33: Else
34: service demand $d$ is blocked;
35: End

Abstract

Cited By

Figures (8)

Tables (4)

Equations (11)

Journal of Optical Communications and Networking