Biphase routing scheme for optimal throughput in large-scale optical satellite networks

Yunxiao Ning; Yongli Zhao; Avishek Nag; Hua Wang; Jie Zhang

doi:10.1364/JOCN.514819

Journal of Optical Communications and Networking
Vol. 16,
Issue 5,
pp. 553-564
(2024)
•https://doi.org/10.1364/JOCN.514819

Biphase routing scheme for optimal throughput in large-scale optical satellite networks

Yunxiao Ning, Yongli Zhao, Avishek Nag, Hua Wang, 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, Yongli Zhao, Avishek Nag, Hua Wang, and Jie Zhang, "Biphase routing scheme for optimal throughput in large-scale optical satellite networks," J. Opt. Commun. Netw. 16, 553-564 (2024)

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

Abstract

In the large-scale optical satellite network (LS-OSN), hundreds to thousands of low Earth orbit (LEO) satellites will be interconnected via laser links, offering global coverage characterized by high throughput and low latency. LS-OSNs present an attractive strategy to cultivate a comprehensively connected, intelligent world. However, the dynamic nature of the satellites, as they orbit the Earth, results in frequent changes in the LS-OSN topology. Thus, there is a pressing need for efficient routing algorithms that not only cater to massive traffic demands but also swiftly adapt to these constant topological changes. Traditional routing algorithms for services with specific bandwidth requirements often compromise on either computational speed or throughput efficiency. In response, this study introduces a routing scheme based on flow optimization and decomposition (FOND). This seeks to shorten the computation time while preserving optimal network throughput. Expanding upon the FOND scheme, we further devised two heuristic algorithms: the flow-based greedy path (FGP) and the flow-based greedy width (FGW). Simulation results from a 288-satellite constellation network indicate that both the FGP and FGW outpace contemporary methods in terms of the routing computation time while maintaining a consistent throughput equal to 100% of the network capacity. Notably, the FGP has exhibited an impressive capability, reducing the routing computation time to 0.23% compared to the baseline incremental-widest-path (IWP) algorithm, which operates on Dijkstra’s algorithm principles.

Full Article | PDF Article

More Like This

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
J. Opt. Commun. Netw. 15(12) 1038-1049 (2023)

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)

Optimizing satellite and core networks for a global quantum network

Vasileios Karavias, Catherine White, Andrew Lord, and Michael C. Payne
J. Opt. Commun. Netw. 16(4) 504-515 (2024)

Previous Article Next Article

Supplementary Material (4)

Name	Description
Data File 1	RCT (Routing Computation Time) of the ISP, IWP, GGP, GGW, FGP, and FGW algorithms.
Data File 2	Optimal TP (Throughput Performance) of time snapshots, and TP of the ISP, IWP, GGP, GGW, FGP, and FGW algorithms.
Data File 3	Maximum Path Length of the ISP, IWP, GGP, GGW, FGP, and FGW algorithms.
Data File 4	Mean Path Latency of the ISP, IWP, GGP, GGW, FGP, and FGW algorithms.

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 (9)

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	Explanations
$t$	$t \in T$ represents a snapshot and $T$ represents a series of snapshots.
$G^{t}$	$G^{t} = (V^{t}, E^{t})$ is a directed graph that represents the topology in snapshot $t$ .
$V^{t}$	$V^{t} = {v_{1}, v_{2}, \dots, v_{n}} = {V_{s a t} \cup V_{g a t e}}$ represents the set of network nodes in snapshot $t$ .
$V_{s a t}$	$V_{s a t}$ represents the set of satellite nodes in the space segment.
$V_{a c c}$	$V_{a c c} \subseteq V_{s a t}$ represents the set of access satellite nodes in the space segment.
$V_{g a t e}$	$V_{g a t e}$ represents the set of ground gateway nodes in the terrestrial segment.
$E^{t}$	$E^{t} = {e_{jk} \| \forall v_{j}, v_{k} \in V^{t}}$ represents the set of $m$ edges, where $e_{jk}$ represents a directional link from node $v_{j}$ to node $v_{k}$ .
$B_{a c c}, B_{i s l}, B_{f e e d}$	$B_{a c c}, B_{i s l}, B_{f e e d}$ are the bandwidth of the access link, the ISL, and the feed link, respectively.
${P a t h}^{t}$	${P a t h}^{t} = {p_{1}, p_{2}, \dots, p_{\| P a t h \|}}$ represents the set of end-to-end service paths in snapshot $t$ , where $p_{i} \in {P a t h}^{t}$ is an end-to-end path.
${PB}^{t}$	${PB}^{t} = {b_{1}, b_{2}, \dots, b_{\| P a t h \|}}$ represents the bandwidth of each path, where the bandwidth of $p_{i}$ is $b_{i}$ .
$F^{t}$	$F^{t} = {f_{jk} \| \forall e_{jk} \in E^{t}}$ represents the network traffic flow in snapshot $t$ , where $f_{jk}$ denotes the link traffic flow of $e_{jk}$ .
$C^{t}$	$C^{t} = {c_{jk} \| \forall e_{jk} \in E^{t}}$ represents the link capacity in snapshot $t$ , where $c_{jk}$ represents the link capacity of $e_{jk}$ .
${TH}^{t}$	${TH}^{t} = \sum b_{i}, \forall b_{i} \in {PB}^{t}$ represents the network throughput in snapshot $t$ .
$x_{jk}^{i}$	$x_{jk}^{i} \in {0, 1}$ represents whether path $p_{i}$ occupies link $e_{jk}$ .
$y_{j}^{i}$	$y_{j}^{i} \in {0, 1}$ represents whether path $p_{i}$ occupies node $v_{j}$ .
$v_{s}$	$v_{s}$ represents the virtual ingress node of the network traffic flow.
$v_{d}$	$v_{d}$ represents the virtual egress node of the network traffic flow.
${F l o w}^{t}$	${F l o w}^{t}$ represents the link traffic flow for the network to achieve its maximal throughput in snapshot $t$ .

Parameters	Values
Constellation type	Walker-Star
Operating height of the constellation	1050 km
Number of satellites	288
Number of orbits	12
Number of satellites per orbit	24
Inclination of orbits	89 deg
Right ascension of the ascending node (RAAN)	180 deg
Phase factor	3
Bandwidth of an access link	2 Gbps
Bandwidth of an inter-satellite link	10 Gbps
Bandwidth of a feedback link	16 Gbps
Number of gateways	16
Simulated duration	120 min
Simulation step	1 s
Number of time snapshots	498
Source node of service demands	288 access satellites
Destination node of service demands	Core network
Granularity of service demands	10 Mbps

Notes	Explanations
$t$	$t \in T$ represents a snapshot and $T$ represents a series of snapshots.
$G^{t}$	$G^{t} = (V^{t}, E^{t})$ is a directed graph that represents the topology in snapshot $t$ .
$V^{t}$	$V^{t} = {v_{1}, v_{2}, \dots, v_{n}} = {V_{s a t} \cup V_{g a t e}}$ represents the set of network nodes in snapshot $t$ .
$V_{s a t}$	$V_{s a t}$ represents the set of satellite nodes in the space segment.
$V_{a c c}$	$V_{a c c} \subseteq V_{s a t}$ represents the set of access satellite nodes in the space segment.
$V_{g a t e}$	$V_{g a t e}$ represents the set of ground gateway nodes in the terrestrial segment.
$E^{t}$	$E^{t} = {e_{jk} \| \forall v_{j}, v_{k} \in V^{t}}$ represents the set of $m$ edges, where $e_{jk}$ represents a directional link from node $v_{j}$ to node $v_{k}$ .
$B_{a c c}, B_{i s l}, B_{f e e d}$	$B_{a c c}, B_{i s l}, B_{f e e d}$ are the bandwidth of the access link, the ISL, and the feed link, respectively.
${P a t h}^{t}$	${P a t h}^{t} = {p_{1}, p_{2}, \dots, p_{\| P a t h \|}}$ represents the set of end-to-end service paths in snapshot $t$ , where $p_{i} \in {P a t h}^{t}$ is an end-to-end path.
${PB}^{t}$	${PB}^{t} = {b_{1}, b_{2}, \dots, b_{\| P a t h \|}}$ represents the bandwidth of each path, where the bandwidth of $p_{i}$ is $b_{i}$ .
$F^{t}$	$F^{t} = {f_{jk} \| \forall e_{jk} \in E^{t}}$ represents the network traffic flow in snapshot $t$ , where $f_{jk}$ denotes the link traffic flow of $e_{jk}$ .
$C^{t}$	$C^{t} = {c_{jk} \| \forall e_{jk} \in E^{t}}$ represents the link capacity in snapshot $t$ , where $c_{jk}$ represents the link capacity of $e_{jk}$ .
${TH}^{t}$	${TH}^{t} = \sum b_{i}, \forall b_{i} \in {PB}^{t}$ represents the network throughput in snapshot $t$ .
$x_{jk}^{i}$	$x_{jk}^{i} \in {0, 1}$ represents whether path $p_{i}$ occupies link $e_{jk}$ .
$y_{j}^{i}$	$y_{j}^{i} \in {0, 1}$ represents whether path $p_{i}$ occupies node $v_{j}$ .
$v_{s}$	$v_{s}$ represents the virtual ingress node of the network traffic flow.
$v_{d}$	$v_{d}$ represents the virtual egress node of the network traffic flow.
${F l o w}^{t}$	${F l o w}^{t}$ represents the link traffic flow for the network to achieve its maximal throughput in snapshot $t$ .

Parameters	Values
Constellation type	Walker-Star
Operating height of the constellation	1050 km
Number of satellites	288
Number of orbits	12
Number of satellites per orbit	24
Inclination of orbits	89 deg
Right ascension of the ascending node (RAAN)	180 deg
Phase factor	3
Bandwidth of an access link	2 Gbps
Bandwidth of an inter-satellite link	10 Gbps
Bandwidth of a feedback link	16 Gbps
Number of gateways	16
Simulated duration	120 min
Simulation step	1 s
Number of time snapshots	498
Source node of service demands	288 access satellites
Destination node of service demands	Core network
Granularity of service demands	10 Mbps

Algorithm 1: Flow-Based Greedy Path Algorithm
Input: Topology of the current time snapshot $G^{t} = (V^{t}, E^{t})$ and the set of access satellites $V_{acc}$ .
Output: The path set ${Path}^{t}$ , bandwidth $P B^{t}$ , and traffic ${Flow}^{t}$ .
Phase I: Flow Optimization
1. Add virtual nodes $v_{s}$ and $v_{d}$ ;
2. Connect $v_{s}$ and $V_{acc}$ ;
3. Connect $V_{gate}$ and $v_{d}$ ;
4. Get graph $G^{'} = (V^{'}, E^{'})$ ;
5. Calculate ${Flow}^{t} = maxflow (G^{'}, v_{s}, v_{d});$
Phase II: Path Decomposition in the FGP algorithm
6. Initialize ${Path}^{t}$ , $P B^{t}$ , and $i$ ;
7. Remove the zero traffic flow link in $G^{'}$ according to ${Flow}^{t}$ ;
8. While ${Flow}^{t}$ is not empty, do:
9. Calculate $p_{i} = d i j k s t r a (G^{'}, v_{s}, v_{d})$ ;
10. If $p_{i}$ is nonempty, do:
11. Calculate $p_{i}$ ;
12. Remove bandwidth resources in ${Flow}^{t}$ ;
13. Record $p_{i}$ and $p b_{i}$ ;
14. $i + +$ ;
15. Else break.
16. Loop
17. End

Algorithm 2: Flow-Based Greedy Width Algorithm
Input: Topology of the current time snapshot $G^{t} = (V^{t}, E^{t})$ and the set of access satellites $V_{acc}$ .
Output: The path set ${Path}^{t}$ , bandwidth $P B^{t}$ , and traffic ${Flow}^{t}$ .
Phase I: Flow Optimization
1–5. Use the same flow optimization procedure with the FGP.
Phase II: Path Decomposition in the FGW algorithm
6. Initialize ${Path}^{t}$ , $P B^{t}$ , and $i$ ;
7. Create link weight set $W^{t}$ ;
8. While ${Flow}^{t}$ is not empty, do:
9. Calculate $p_{i} = d i j k s t r a^{'} (W^{t}, v_{s}, v_{d})$ ;
10. If $p_{i}$ is nonempty, do:
11. Calculate $p b_{i}$ ;
12. Remove bandwidth resources in ${Flow}^{t}$ ;
13. Record $p_{i}$ and $p b_{i}$ ;
14. Update link weight set $W^{t}$ ;
15. $i + +$ ;
16. Else break.
17. Loop
18. End

Algorithm 1: Flow-Based Greedy Path Algorithm
Input: Topology of the current time snapshot $G^{t} = (V^{t}, E^{t})$ and the set of access satellites $V_{acc}$ .
Output: The path set ${Path}^{t}$ , bandwidth $P B^{t}$ , and traffic ${Flow}^{t}$ .
Phase I: Flow Optimization
1. Add virtual nodes $v_{s}$ and $v_{d}$ ;
2. Connect $v_{s}$ and $V_{acc}$ ;
3. Connect $V_{gate}$ and $v_{d}$ ;
4. Get graph $G^{'} = (V^{'}, E^{'})$ ;
5. Calculate ${Flow}^{t} = maxflow (G^{'}, v_{s}, v_{d});$
Phase II: Path Decomposition in the FGP algorithm
6. Initialize ${Path}^{t}$ , $P B^{t}$ , and $i$ ;
7. Remove the zero traffic flow link in $G^{'}$ according to ${Flow}^{t}$ ;
8. While ${Flow}^{t}$ is not empty, do:
9. Calculate $p_{i} = d i j k s t r a (G^{'}, v_{s}, v_{d})$ ;
10. If $p_{i}$ is nonempty, do:
11. Calculate $p_{i}$ ;
12. Remove bandwidth resources in ${Flow}^{t}$ ;
13. Record $p_{i}$ and $p b_{i}$ ;
14. $i + +$ ;
15. Else break.
16. Loop
17. End

Algorithm 2: Flow-Based Greedy Width Algorithm
Input: Topology of the current time snapshot $G^{t} = (V^{t}, E^{t})$ and the set of access satellites $V_{acc}$ .
Output: The path set ${Path}^{t}$ , bandwidth $P B^{t}$ , and traffic ${Flow}^{t}$ .
Phase I: Flow Optimization
1–5. Use the same flow optimization procedure with the FGP.
Phase II: Path Decomposition in the FGW algorithm
6. Initialize ${Path}^{t}$ , $P B^{t}$ , and $i$ ;
7. Create link weight set $W^{t}$ ;
8. While ${Flow}^{t}$ is not empty, do:
9. Calculate $p_{i} = d i j k s t r a^{'} (W^{t}, v_{s}, v_{d})$ ;
10. If $p_{i}$ is nonempty, do:
11. Calculate $p b_{i}$ ;
12. Remove bandwidth resources in ${Flow}^{t}$ ;
13. Record $p_{i}$ and $p b_{i}$ ;
14. Update link weight set $W^{t}$ ;
15. $i + +$ ;
16. Else break.
17. Loop
18. End

Abstract

Supplementary Material (4)

Cited By

Figures (8)

Tables (4)

Equations (9)

Journal of Optical Communications and Networking