A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation

WANG Ning-yuan; LIU Liang; CHEN Dong; LIU Huan; HAO Shi-guang

doi:10.12263/DZXB.20201335

您当前的位置：

首页 >

文章列表页 >

A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation

PAPERS | 更新时间：2025-12-08

- A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation
- ACTA ELECTRONICA SINICA Vol. 49, Issue 11, Pages: 2124-2132(2021)
- 作者机构：
  
  1.中国空间技术研究院通信与导航卫星总体部，北京 100094
  2.鹏城实验室，广东深圳518052
  3.北京空间机电研究所，北京 100094
- 作者简介：
- 基金信息：
- DOI：10.12263/DZXB.20201335
  CLC： TN915.41;TP393.4
- Received：26 November 2020，
  
  Revised：2021-08-24，
  
  Published：25 November 2021
- 稿件说明：
移动端阅览
王宁远,刘亮,陈东等.低轨巨星座多品类业务流低复杂度分段路由方法[J].电子学报,2021,49(11):2124-2132.

WANG Ning-yuan,LIU Liang,CHEN Dong,et al.A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation[J].ACTA ELECTRONICA SINICA,2021,49(11):2124-2132.
王宁远,刘亮,陈东等.低轨巨星座多品类业务流低复杂度分段路由方法[J].电子学报,2021,49(11):2124-2132. DOI： 10.12263/DZXB.20201335.

WANG Ning-yuan,LIU Liang,CHEN Dong,et al.A Low Time Complexity Segment Routing Approach for Multi-Commodity Traffic Flow in Mega LEO Constellation[J].ACTA ELECTRONICA SINICA,2021,49(11):2124-2132. DOI： 10.12263/DZXB.20201335.

摘要

含有星间链路的低轨巨星座网络在全球多种业务回传至有限地理区域场景下会产生严重的网络拥塞问题，集中式的流量规划可以在一定程度上实现负载均衡.然而大规模网络规划的计算时间开销无法满足低轨星座的动态性要求.为此，本文提出了低复杂度的多品类流分段路由（MCFSR）算法，将星座-地面网络依据负载情况划分为两个分区，并在分区内对规划算法的精度与复杂度之间进行权衡，以达到降低算法整体复杂度的目的.同时，对于规划算法，本文提出了复杂度可调的改进的完全多项式时间近似（IFPTA）算法，用于分区内的路由规划，在计算复杂度不变的情况下使算法吞吐量更接近最优值.仿真结果证明了本文提出的MCFSR算法在巨星座场景下可以使多业务回传的总吞吐量接近最优，且时间复杂度开销远低于其他同类算法.

Abstract

The LEO mega-constellation network with inter-satellite links faces serious network congestion when multi-commodity traffics return to a limited geographical area from all over the world

which can be alleviated by centralized traffic planning. However

the computing time cost of large-scale network planning cannot meet the dynamic requirements of LEO constellation. Therefore

this paper proposes a low complexity Multi-Commodity Flow Segment Routing (MCFSR) algorithm

which divides the constellation-ground network into two zones according to different link payload

and balances between accuracy and complexity of the planning algorithm in each zone

so as to reduce the overall time complexity. Meanwhile

for the planning algorithm

this paper proposes an Improved Fully Polynomial Time Approximation (IFPTA) algorithm with adjustable precision and complexity for routing programming in each zone

which improves the planning accuracy without changing the computational complexity. Simulation results show that the total throughput of multi traffic backhaul programmed by proposed MCFSR algorithm approaches the optimal

with the time complexity far less than other similar algorithms.

关键词

Keywords

references

Di B , Song L , Li Y , et al . Ultra-dense LEO: Integration of satellite access networks into 5G and beyond [J]. IEEE Wireless Communications , 2019 , 26 ( 2 ): 62 - 69 .

宋海丰 . 国外新兴低轨通信星座发展态势分析 [J]. 国际太空 , 2018 ,( 5 ): 17 - 22 .

Song Hai-feng . Analysis on situation of foreign emerging LEO communication satellite constellations [J]. Space International , 2018 ,( 5 ): 17 - 22 . (in Chinese)

Liu J , Shi Y , Fadlullah Z M , et al . Space-air-ground integrated network: A survey [J]. IEEE Communications Surveys & Tutorials , 2018 , 20 ( 4 ): 2714 - 2741 .

Zhang N , Zhang S , Yang P , et al . Software defined space-air-ground integrated vehicular networks: Challenges and solutions [J]. IEEE Communications Magazine , 2017 , 55 ( 7 ): 101 - 109 .

Albulet M . Spacex non-geostationary satellite system: Technical information to supplement schedules-Attachment to fcc application sat-loa-20161115-00118 [R]. Federal Commun Commission, Washington DC, USA, Tech Rep SAT-LOA-20161115-00118 , 2016 .

Del Portillo I , Cameron B G , Crawley E F . A technical comparison of three low earth orbit satellite constellation systems to provide global broadband [J]. Acta Astronautica , 2019 , 159 : 123 - 135 .

Jun X , Lu W , Zhang G . Traffic modeling and simulation of broadband LEO satellite communication system [A]. IOP Conference Series: Materials Science and Engineering [C]. IOP Publishing , 2018 , 452 ( 4 ): 042082 .

Jia Z , Sheng M , Li J , et al . Joint HAP access and LEO satellite backhaul in 6G: Matching game-based approaches [J]. IEEE Journal on Selected Areas in Communications , 2020 , 39 ( 4 ): 1147 - 1159 .

Shmoys D B . Cut problems and their application to divide-and-conquer [J]. Approximation Algorithms for NP-Hard Problems , 1997 : 192 - 235 .

Shahrokhi F , Matula D W . The maximum concurrent flow problem [J]. Journal of the ACM (JACM) , 1990 , 37 ( 2 ): 318 - 334 .

Leighton T , Makedon F , Plotkin S , et al . Fast approximation algorithms for multicommodity flow problems [J]. Journal of Computer and System Sciences , 1995 , 50 ( 2 ): 228 - 243 .

Garg N , Koenemann J . Faster and simpler algorithms for multicommodity flow and other fractional packing problems [J]. SIAM Journal on Computing , 2007 , 37 ( 2 ): 630 - 652 .

Karakostas G . Faster approximation schemes for fractional multicommodity flow problems [J]. ACM Transactions on Algorithms (TALG) , 2008 , 4 ( 1 ): 1 - 17 .

Filsfils C , Nainar N K , Pignataro C , et al . The segment routing architecture [A]. 2015 IEEE Global Communications Conference (GLOBECOM) [C]. USA : IEEE , 2015 . 1 - 6 .

Davoli L , Veltri L , Ventre P L , et al . Traffic engineering with segment routing: SDN-based architectural design and open source implementation [A]. 2015 Fourth European Workshop on Software Defined Networks [C]. USA : IEEE , 2015 . 111 - 112 .

Bhatia R , Hao F , Kodialam M , et al . Optimized network traffic engineering using segment routing [A]. 2015 IEEE Conference on Computer Communications (INFOCOM) [C]. USA : IEEE , 2015 . 657 - 665 .

黄建洋 , 兰巨龙 , 胡宇翔 , 等 . 一种基于分段路由的多路径流传输机制 [J]. 电子学报 , 2018 , 46 ( 6 ): 1488 - 1495 .

Huang Jian-yang , Lan Ju-long , Hu Yu-xiang , et al . A segment routing based multipath flow transmission mechanism [J]. Acta Electronica Sinica , 2018 , 46 ( 6 ): 1488 - 1495 . (in Chinese)

Liu W , Tao Y , Liu L . Load-balancing routing algorithm based on segment routing for traffic return in LEO satellite networks [J]. IEEE Access , 2019 , 7 : 112044 - 112053 .

Boyd Stephen , Vandenberghe Lieven . Convex optimization [J]. IEEE Transactions on Automatic Control , 2006 , 51 ( 11 ): 1859 - 1859 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Optimization Study of the Load Balancing Algorithm in the Multi-Layer Lattice Boltzmann Method

Diverse User Service Requirement-Oriented Dynamic Resource Allocation Algorithm for Multi-Beam Satellite Systems

Via-Aware Parallel Layer Assignment Algorithm for VLSI Physical Design

Research on PPI Network Construction and Complex Mining Algorithm Based on Dynamic Graph

Research on Load Balancing of Distributed Control Plane in Polymorphic Network

Related Author

HE Peng

WANG Liang-jun

ZHANG Wu

ZHU Wen-hao

CHAI Rong

LIU Lei

LIANG Cheng-chao

CHEN Qian-bin

Related Institution

School of Mechanics and Engineering Science, Shanghai University

School of Computer Engineering and Science, Shanghai University

School of Communications and Information Engineering, Chongqing University of Posts and Telecommunications

College of Computer and Data Science, Fuzhou University

School of Information Engineering, Wuhan University of Technology

⁰