Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network

Hongyan LI; Tao ZHANG; Jingqian ZHANG; Keyi SHI; Pengcheng ZENG

doi:10.11959/j.issn.1000-436x.2020188

您当前的位置：

首页 >

文章列表页 >

Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network

Papers | 更新时间：2024-06-05

- Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network
- Journal on Communications Vol. 41, Issue 10, Pages: 116-129(2020)
- 作者机构：
  
  1. 西安电子科技大学通信工程学院，陕西西安 710071
  2. 中国电信福建分公司网络运营支撑中心，福建福州 350001
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61931017);The National Natural Science Foundation of China(61871456);The National Natural Science Foundation of China(91638202);National S＆T Major Project(2015ZX03002006);The 111 Project(B08038);Natural Science Basic Research Plan in Shaanxi Province(2016JQ6054)
- DOI：10.11959/j.issn.1000-436x.2020188
  CLC： TN915.03
- Online First：2020-10，
  
  Published：25 October 2020
- 稿件说明：
移动端阅览
Hongyan LI, Tao ZHANG, Jingqian ZHANG, et al. Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network[J]. Journal on Communications, 2020, 41(10): 116-129.
DOI：

Hongyan LI, Tao ZHANG, Jingqian ZHANG, et al. Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network[J]. Journal on Communications, 2020, 41(10): 116-129. DOI： 10.11959/j.issn.1000-436x.2020188.

摘要

针对天地一体化网络时变多维资源与差异多样化业务导致网络端到端时延难保障、网络资源利用率难提升等问题，提出基于时变图的天地一体化网络时间确定性路由算法及协议。构建时变连续图模型，用于表征天地一体化网络时变拓扑、链路连通时段、节点缓存等多维资源的时空属性；提出面向业务的时间确定性路由算法，依据链路累积流量计算规则、节点流守恒约束与节点缓存约束，构建具有时间属性的最短时延路径；将所提路由算法与分段路由（SR）技术以及时间敏感网络（TSN）技术相结合，设计具有时延保障的时间确定路由协议，支持时变网络环境中拓扑发现、确定性路由的高效计算以及分组的定时转发。仿真结果表明，通过关联利用链路资源与节点存储资源，与基于快照图和接触图的路由算法相比，所提路由算法的链路资源利用率高、分组成功投递率高，保障了业务的端到端传输时延。

Abstract

In terms of the difficulties to construct the end-to-end path and improve the utilization of network resources

caused by the time-varying multi-dimensional resources and diverse services over the space-ground integrated networks

the time-varying graph-based time deterministic routing algorithm and protocol for the space-ground integrated network was proposed.Firstly

a time-varying continuous graph model was constructed to describe the spatial and temporal attributes of multi-dimensional resources

such as the topology

link connectivity opportunities

node caching and so on.Then

a service-oriented time deterministic routing algorithm was proposed.According to the calculation rules of link cumulative traffic

and the constraints of node flow conservation and cache

the time-varying path with the shortest transmission delay was constructed.After that

a delay-guaranteed time deterministic routing protocol was designed by combining the proposed routing algorithm with both the segment routing technology and the time sensitive network technology

which supported the dynamic topology discovery

the efficient calculation of deterministic routing and the timing forwarding of data packets on the time-varying network.The simulation results show that

compared with the routing algorithm based on snapshot graph and contact graph

the proposed routing algorithm has higher link resource utilization rate and the packet successful delivery rate by jointly using link and node storage resources by association

and ensures the end-to-end transmission delay of services.

关键词

Keywords

references

HOU S , LIU H . Handbook of space security:policies,applications and programs [M ] . New York : SpringerPress , 2015 .

YU Q , WANG J , BAI L . Architecture and critical technologies of space information networks [J ] . Journal of Communications and Information Networks , 2017 , 1 : 1 - 9 .

ZHANG T , LI J , LI H , et al . Application of time-varying graph theory over the space information networks [J ] . IEEE Network , 2020 , 34 ( 2 ): 179 - 185 .

STEINHAMMER K , GRILLINGER P , ADEMAJ A , et al . A time-triggered ethernet (TTE) switch [C ] // Proceedings of the Design Automation ＆ Test in Europe Conference . Piscataway:IEEE Press , 2006 : 794 - 799 .

ADEMAJ A , KOPETZ H . Time-triggered Ethernet and IEEE 1588 clock synchronization [C ] // 2007 IEEE International Symposium on Precision Clock Synchronization for Measurement,Control and Communication.Piscataway:IEEE Press . 2007 : 41 - 43 .

PLANKENSTEINER M . TT Ethernet:a powerful network solution for all purposes [J ] . Delft University of Technology , 2010 , 13 ( 3 ): 1 - 4 .

MEYER P , STEINBACH T , KORF F , et al . Extending IEEE 802.1 AVB with time-triggered scheduling:a simulation study of the coexistence of synchronous and asynchronous traffic [C ] // 2013 IEEE Vehicular Networking Conference.Piscataway:IEEE Press . 2013 : 47 - 54 .

ALDERISI G , PATTI G , BELLO L . Introducing support for scheduled traffic over IEEE audio video bridging networks [C ] // 2013 IEEE 18th Conference on Emerging Technologies ＆ Factory Automation (ETFA).Piscataway:IEEE Press . 2013 : 1 - 9 .

ZHOU Z , YAN Y , RUEPP S , et al . Analysis and implementation of packet preemption for time sensitive networks [C ] // 2017 IEEE 18th International Conference on High Performance Switching and Routing (HPSR).Piscataway:IEEE Press . 2017 : 1 - 6 .

QIANG L , LIU B , ECKERT T , et al . Large-scale deterministic network [R ] . Internet-Draft draft:Internet Engineering Task Force ,(2018-07-13)[2020-08-06 ] .

FINN N , THUBERT P , VARGAA B , et al . Deterministic networking architecture [R ] . Internet Draft:Internet Engineering Task Force , 2019 .

WEST D . An introduction to graph theory [M ] . New Jersey : Prentice-HallPress , 1996 .

WERNER M . A dynamic routing concept for ATM-based satellite personal communication networks [J ] . IEEE Journal on Selected Areas in Communications , 1997 , 15 ( 8 ): 1636 - 1648 .

WANG P , ZHANG X , ZHANG S , et al . Time-expanded graph-based resource allocation over the satellite networks [J ] . IEEE Wireless Communications Letters , 2019 , 8 ( 2 ): 360 - 363 .

GEORGE B , SHEKHAR S . Time-aggregated graphs for modeling spatio-temporal networks [C ] // International Conference on Advances in Conceptual Modeling . Berlin:Springer , 2006 : 85 - 99 .

LI H , ZHANG T , ZHANG Y , et al . A maximum flow algorithm based on storage time aggregated graph for delay-tolerant networks [J ] . Ad Hoc Networks , 2017 , 59 : 63 - 70 .

ZHANG T , LI H , ZHANG S , et al . STAG-based QoS support routing strategy for multiple missions over the satellite networks [J ] . IEEE Transactions on Communications , 2019 , 69 ( 10 ): 6912 - 6924 .

SHI K , ZHANG X , ZHANG S , et al . Time-expanded graph based energy-efficient delay-bounded multicast over satellite networks [J ] . IEEE Transactions on Vehicular Technology , 2020 ,DOI:10.1109/TVT.2020.2988023.

DU J , JIANG C , YU S , et al . Time cumulative complexity modeling and analysis for space-based networks [C ] // 2016 IEEE International Conference on Communications.Piscataway:IEEE Press . 2016 : 1 - 6 .

TANG Z , FENG Z , HAN W , et al . Improving the snapshot routing performance through reassigning the inter-satellite links [C ] // 2015 IEEE Conference on Computer Communications Workshops.Piscataway:IEEE Press . 2015 : 97 - 98 .

YUAN P , YANG Z , LI Y , et al . An event-driven graph-based min-cost delivery algorithm in earth observation DTN networks [C ] // 2015 International Conference on Wireless Communications ＆ Signal Processing.Piscataway:IEEE Press . 2015 : 1 - 6 .

GLACET C , FIORE M , GRAMAGLIA M . Temporal connectivity of vehicular networks:The power of store-carry-and-forward [C ] // 2015 IEEE Vehicular Networking Conference.Piscataway:IEEE Press . 2015 : 52 - 59 .

CAINI C , CRUICKSHANK H , FARRELL S , et al . Delay-and disruption-tolerant networking (DTN):an alternative solution for future satellite networking applications [J ] . Proceedings of the IEEE , 2011 , 99 ( 11 ): 1980 - 1997 .

ARANITI G , BEZIRGIANNIDIS N , BIRRANE E , et al . Contact graph routing in DTN space networks:overview,enhancements and performance [J ] . IEEE Communications Magazine , 2015 , 53 ( 3 ): 38 - 46 .

FRAIRE J A , MADOERY P , BURLEIGH S , et al . Assessing contact graph routing performance and reliability in distributed satellite constellations [J ] . Journal of Computer Networks and Communications , 2017 , 6 : 1 - 18 .

MOY J . Open shortest path first specification:RFC 1131 [S ] . Fremont,CA:IETF , 1989 .

MOY J . OSPF version 2:RFC 1247 [S ] . Fremont,CA:IETF , 1998 .

FALL K , SCOTT K . Delay-tolerant networking architecture:RFC 4838 [S ] . Fremont,CA:IETF , 2007 .

SCOTTK , BURLEIGH S . Bundle protocol specification:RFC 5050 [S ] . Fremont,CA:IETF , 2007 .

LEBRUN D , BONAVENTURE O . Implementing IPv6 segment routing in the Linux kernel [C ] // Applied Networking Research Workshop . New York:ACM Press , 2017 : 35 - 41 .

Views

3637

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Multicast time-expanded graph-based collective communication scheduling algorithm

Reliable energy-efficient routing protocol based on anomalous detection and AUV-aid for underwater sensor networks

Intelligent route planning method with jointing topology control of UAV swarm

Cross-network access control mechanism for complex network environment

Development and outlook of deep space communication network protocol

Related Author

Li Hongyan

Li Ye

Ma Han

Wang Peng

Liu Fei

WANG Zhigang

TIAN Xiaojing

WANG Lijuan

Related Institution

State Key Laboratory of Integrated Services Networks, Xidian University

Singapore University of Technology and Design

College of Computer, Qinghai Provincial Key Laboratory of IoT, Qinghai Normal University

The State Key Laboratory of Tibetan Intelligent Information Processing and Application

School of Computer Science, North China Institute of Science and Technology

AI问答

⁰