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

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

通信学报 ›› 2020, Vol. 41 ›› Issue (10): 116-129.doi: 10.11959/j.issn.1000-436x.2020188

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

李红艳¹,张焘²,张靖乾¹,史可懿¹,曾鹏程¹

¹ 西安电子科技大学通信工程学院，陕西西安 710071
² 中国电信福建分公司网络运营支撑中心，福建福州 350001

修回日期:2020-08-06 出版日期:2020-10-25 发布日期:2020-11-05
作者简介:李红艳（1966- ），女，陕西西安人，博士，西安电子科技大学教授，主要研究方向为时间确定性网络、天地一体化网络、新一代无线局域网、时变图技术等|张焘（1992- ），男，福建三明人，博士，中国电信福建分公司网络运营支撑中心员工，主要研究方向为天地一体化网络、时变图理论、卫星网络路由、时间确定性网络协议|张靖乾（1997- ），男，陕西西安人，西安电子科技大学硕士生，主要研究方向为卫星网络路由、网络协议仿真|史可懿（1995- ），男，陕西汉中人，西安电子科技大学博士生，主要研究方向为时变图理论、天地一体化网络路由算法|曾鹏程（1994- ），男，湖南邵阳人，西安电子科技大学硕士生，主要研究方向为卫星网络路由、时间确定性网络协议
基金资助:
国家自然科学基金资助项目(61931017);国家自然科学基金资助项目(61871456);国家自然科学基金资助项目(91638202);国家科技重大专项基金资助项目(2015ZX03002006);“111”计划基金资助项目(B08038);陕西省自然科学基础研究计划基金资助项目(2016JQ6054)

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¹

¹ School of Telecommunications Engineering,Xidian University,Xi’an 710071,China
² Network Operation Center of China Telecom Fujian Branch,Fuzhou 350001,China

Revised:2020-08-06 Online:2020-10-25 Published:2020-11-05
Supported by:
The National Natural Science Foundation of China(61931017);The National Natural Science Foundation of China(61871456);The National Natural Science Foundation of China(91638202);The National Science and Technology Major Project of China(2015ZX03002006);The 111 Project(B08038);The Natural Science Basic Research Plan in Shaanxi Province(2016JQ6054)

摘要/Abstract

摘要：

针对天地一体化网络时变多维资源与差异多样化业务导致网络端到端时延难保障、网络资源利用率难提升等问题，提出基于时变图的天地一体化网络时间确定性路由算法及协议。构建时变连续图模型，用于表征天地一体化网络时变拓扑、链路连通时段、节点缓存等多维资源的时空属性；提出面向业务的时间确定性路由算法，依据链路累积流量计算规则、节点流守恒约束与节点缓存约束，构建具有时间属性的最短时延路径；将所提路由算法与分段路由（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.

Key words: space-ground integrated network, time-varying graph, time deterministic routing algorithm, routing protocol, resource allocation on demand

中图分类号:

TN915.03

李红艳,张焘,张靖乾,史可懿,曾鹏程. 基于时变图的天地一体化网络时间确定性路由算法与协议[J]. 通信学报, 2020, 41(10): 116-129.

Hongyan LI,Tao ZHANG,Jingqian ZHANG,Keyi SHI,Pengcheng ZENG. 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.

图/表 14

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

参考文献 30

[1]	HOU S , LIU H . Handbook of space security:policies,applications and programs[M]. New York: SpringerPress, 2015.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	PLANKENSTEINER M . TT Ethernet:a powerful network solution for all purposes[J]. Delft University of Technology, 2010,13(3): 1-4.
[7]	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.
[8]	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.
[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.
[10]	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].
[11]	FINN N , THUBERT P , VARGAA B ,et al. Deterministic networking architecture[R]. Internet Draft:Internet Engineering Task Force, 2019.
[12]	WEST D . An introduction to graph theory[M]. New Jersey: Prentice-HallPress, 1996.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	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.
[18]	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.
[19]	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.
[20]	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.
[21]	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.
[22]	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.
[23]	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.
[24]	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.
[25]	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.
[26]	MOY J . Open shortest path first specification:RFC 1131[S]. Fremont,CA:IETF, 1989.
[27]	MOY J . OSPF version 2:RFC 1247[S]. Fremont,CA:IETF, 1998.
[28]	FALL K , SCOTT K . Delay-tolerant networking architecture:RFC 4838[S]. Fremont,CA:IETF, 2007.
[29]	SCOTTK , BURLEIGH S . Bundle protocol specification:RFC 5050[S]. Fremont,CA:IETF, 2007.
[30]	LEBRUN D , BONAVENTURE O . Implementing IPv6 segment routing in the Linux kernel[C]// Applied Networking Research Workshop. New York:ACM Press, 2017: 35-41.

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 30

相关文章 15

Metrics

推荐阅读 0

[1]	王鹏, 张修社, 索龙, 史可懿. 基于随机时变图的时间确定性网络路由算法[J]. 通信学报, 2021, 42(9): 21-30.
[2]	李贺武,刘李鑫,刘君,吴茜. 基于位置的天地一体化网络路由寻址机制研究[J]. 通信学报, 2020, 41(8): 120-129.
[3]	薛开平,周焕城,孟薇,李少华. 天地一体化网络无缝切换和跨域漫游场景下的安全认证增强方案[J]. 通信学报, 2019, 40(6): 138-147.
[4]	李凤华,陈天柱,王震,张林杰,史国振,郭云川. 复杂网络环境下跨网访问控制机制[J]. 通信学报, 2018, 39(2): 1-10.
[5]	王继红,石文孝. 认知无线传感器网络分簇路由协议综述[J]. 通信学报, 2018, 39(11): 156-169.
[6]	黄利晓,王晖,袁利永,曾令国. 基于能量均衡高效WSN的LEACH协议改进算法[J]. 通信学报, 2017, 38(Z2): 164-169.
[7]	安建平,靳松,许军,张宇,邵立伟. 深空通信网络协议的发展与展望[J]. 通信学报, 2016, 37(7): 50-61.
[8]	郑博,张衡阳,王宝良,赵玮. 航空自组网负载均衡地理路由策略[J]. 通信学报, 2016, 37(12): 67-76.
[9]	孙彦景,方卫,刘卫东,孟冲. 基于蚁群优化的无线多媒体传感器网络区分服务路由[J]. 通信学报, 2012, 33(Z2): 9-14.
[10]	游波,阎跃鹏. IEEE 802.11s路由切换分析与改进[J]. 通信学报, 2012, 33(9): 23-30.
[11]	李陟,姜怡,李千目,刘凤玉. 基于稳定闭域的异构无线网络混合路由策略[J]. 通信学报, 2012, 33(9): 95-104.
[12]	郭显,冯涛,袁占亭. 编码感知多跳无线网络安全路由协议[J]. 通信学报, 2012, 33(6): 133-142.
[13]	姬文江,马建峰,田有亮,马卓. 无线mesh网中一种基于博弈论的公平性路由协议[J]. 通信学报, 2012, 33(11): 17-23.
[14]	吴伟强,郑石,张钦宇. 面向高动态高空平台网络的路由协议研究[J]. 通信学报, 2012, 33(1): 153-159.
[15]	刘星成,袁东升,梁平元,张晓瑜. 基于代价函数的WSN能效路由协议性能分析[J]. 通信学报, 2011, 32(6): 132-140.