基于时变图的天地一体化网络时间确定性路由算法与协议

李红艳; 张焘; 张靖乾; 史可懿; 曾鹏程

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

您当前的位置：

首页 >

文章列表页 >

基于时变图的天地一体化网络时间确定性路由算法与协议

学术论文 | 更新时间：2024-06-05

- 基于时变图的天地一体化网络时间确定性路由算法与协议
- Time deterministic routing algorithm and protocol based on time-varying graph over the space-ground integrated network
- 通信学报 2020年41卷第10期页码：116-129
- 作者机构：
  
  1. 西安电子科技大学通信工程学院，陕西西安 710071
  2. 中国电信福建分公司网络运营支撑中心，福建福州 350001
- 作者简介：
  
  [ "李红艳（1966- ），女，陕西西安人，博士，西安电子科技大学教授，主要研究方向为时间确定性网络、天地一体化网络、新一代无线局域网、时变图技术等" ]
  [ "张焘（1992- ），男，福建三明人，博士，中国电信福建分公司网络运营支撑中心员工，主要研究方向为天地一体化网络、时变图理论、卫星网络路由、时间确定性网络协议" ]
  [ "张靖乾（1997- ），男，陕西西安人，西安电子科技大学硕士生，主要研究方向为卫星网络路由、网络协议仿真" ]
  [ "史可懿（1995- ），男，陕西汉中人，西安电子科技大学博士生，主要研究方向为时变图理论、天地一体化网络路由算法" ]
  [ "曾鹏程（1994- ），男，湖南邵阳人，西安电子科技大学硕士生，主要研究方向为卫星网络路由、时间确定性网络协议" ]
- 基金信息：
  
  国家自然科学基金资助项目(61931017);国家自然科学基金资助项目(61871456);国家自然科学基金资助项目(91638202);国家科技重大专项基金资助项目(2015ZX03002006);高等学校引智计划基金资助项目(B08038);陕西省自然科学基础研究计划基金资助项目(2016JQ6054)
- DOI：10.11959/j.issn.1000-436x.2020188
  中图分类号： TN915.03
- 网络出版日期：2020-10，
  
  纸质出版日期：2020-10-25
- 稿件说明：
移动端阅览
李红艳, 张焘, 张靖乾, 等. 基于时变图的天地一体化网络时间确定性路由算法与协议[J]. 通信学报, 2020,41(10):116-129.

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.
李红艳, 张焘, 张靖乾, 等. 基于时变图的天地一体化网络时间确定性路由算法与协议[J]. 通信学报, 2020,41(10):116-129. DOI： 10.11959/j.issn.1000-436x.2020188.

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 .

浏览量

1418

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

基于异常检测和AUV辅助的水下传感器网络可靠节能路由协议

无人机集群联合拓扑控制的智能路由规划方法

复杂网络环境下跨网访问控制机制

深空通信网络协议的发展与展望

基于蚁群优化的无线多媒体传感器网络区分服务路由