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

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

Abstract

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

CLC Number:

TN915.03

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.

Figures/Tables 14

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 14

References 30

Related Articles 15

Metrics

Recommended 0

[1]	Fenghua LI,Tianzhu CHEN,Zhen WANG,Linjie ZHANG,Guozhen SHI,Yunchuan GUO. Cross-network access control mechanism for complex network environment [J]. Journal on Communications, 2018, 39(2): 1-10.
[2]	Jihong WANG,Wenxiao SHI. Survey on cluster-based routing protocols for cognitive radio sensor networks [J]. Journal on Communications, 2018, 39(11): 156-169.
[3]	Li-xiao HUANG,Hui WANG,Li-yong YUAN,Ling-guo ZENG. Improved LEACH protocol algorithm for WSN based on energy balance and high efficiency [J]. Journal on Communications, 2017, 38(Z2): 164-169.
[4]	Jian-ping AN,Song JIN,Jun XU,Yu ZHANG,Li-wei SHAO. Development and outlook of deep space communication network protocol [J]. Journal on Communications, 2016, 37(7): 50-61.
[5]	Bo ZHENG,Heng-yang ZHANG,Bao-liang WANG,Wei ZHAO. Load balancing geographic routing strategy for aeronautical ad hoc networks [J]. Journal on Communications, 2016, 37(12): 67-76.
[6]	Xu DING,Jiang-hong HAN,Lei SHI,Wei XIA,Zhen-chun WEI. Problem of the dynamic topology architecture of rechargeable wireless sensor networks [J]. Journal on Communications, 2015, 36(1): 129-141.
[7]	Ze-xin LU,Xiao-zhe ZHANG,Shi-cong MA,Bao-sheng WANG. Design and implementation: an open and reconfigurable router architecture with different network system supported [J]. Journal on Communications, 2013, 34(3): 126-133.
[8]	Yan-jing SUN,Wei FANG,Wei-dong LIU,Chong MENG. Differentiated service and ant colony optimization based routing protocol for wireless multimedia sensor networks [J]. Journal on Communications, 2012, 33(Z2): 9-14.
[9]	Bo YOU,Yue-peng YAN. Analysis and improvement of route switch in IEEE 802.11s [J]. Journal on Communications, 2012, 33(9): 23-30.
[10]	Zhi LI,Yi JIANG,Qian-mu LI,Feng-yu LIU. Stable enclosure based hybrid routing schema in heterogeneous wireless networks [J]. Journal on Communications, 2012, 33(9): 95-104.
[11]	Wen-jiang JI,Jian-feng MA,You-liang TIAN,Zhuo MA. Game theoretical routing protocol with fairness problem in wireless mesh networks [J]. Journal on Communications, 2012, 33(11): 17-23.
[12]	Wei-qiang WU,Shi ZHENG,Qin-yu ZHANG. Research on high dynamic high altitude platforms network oriented routing protocol [J]. Journal on Communications, 2012, 33(1): 153-159.
[13]	Xing-cheng LIU,Dong-sheng YUAN,Ping-yuan LIANG,Xiao-yu ZHANG. Performance analysis of cost function based energy-efficient routing protocol in WSN [J]. Journal on Communications, 2011, 32(6): 132-140.
[14]	Ying-fang FU,Xing ZHANG,Ting ZHANG,Liang-yu LUAN. Research on wormhole attacks in wireless mesh networks [J]. Journal on Communications, 2011, 32(1): 59-65.
[15]	Jing-jing GUI,Yu-sen ZHANG. New approach to security analysis of ad hoc routing protocols based on strand space model [J]. Journal on Communications, 2010, 31(9A): 217-222.