Time deterministic network routing algorithm based on stochastic temporal graph

Peng WANG; Xiushe ZHANG; Long SUO; Keyi SHI

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

您当前的位置：

首页 >

文章列表页 >

Time deterministic network routing algorithm based on stochastic temporal graph

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

- Time deterministic network routing algorithm based on stochastic temporal graph
- Journal on Communications Vol. 42, Issue 9, Pages: 21-30(2021)
- 作者机构：
  
  1. 西安电子科技大学综合业务网理论及关键技术国家重点实验室，陕西西安 710071
  2. 中国电子科技集团公司第二十研究所，陕西西安 710071
- 作者简介：
- 基金信息：
  
  Key Project in Fundamental Research(2020JCJQXXX)
- DOI：10.11959/j.issn.1000-436x.2021138
  CLC： TN915.03
- Online First：2021-09，
  
  Published：25 September 2021
- 稿件说明：
移动端阅览
Peng WANG, Xiushe ZHANG, Long SUO, et al. Time deterministic network routing algorithm based on stochastic temporal graph[J]. Journal on Communications, 2021, 42(9): 21-30.
DOI：

Peng WANG, Xiushe ZHANG, Long SUO, et al. Time deterministic network routing algorithm based on stochastic temporal graph[J]. Journal on Communications, 2021, 42(9): 21-30. DOI： 10.11959/j.issn.1000-436x.2021138.

摘要

针对天地一体化网络环境中网络时变性和业务时延确定性保障之间的矛盾，构建了随机时变图模型，并基于该模型提出了时间确定性网络路由算法。首先，将空间信息网络最大概率时延保障路由计算问题建模为非线性规划问题。为解决该问题，提出了随机时变图模型，联合表征了由业务随机性导致的链路、存储与时间资源的随机特征，并且表征了存储与链路资源

的关联关系，为链路资源利用率的提升与业务的时间确定性保障提供了模型基础；在此基础上，提出了时间复杂度为O(n

)的最大概率时延保障的路由算法，并证明了该算法的最优性。

Abstract

With respect to the contradiction between the randomness of space-terrestrial integrated network resources and the deterministic requirements of service delay in the network

a stochastic temporal graph model was proposed

based on which a routing algorithm that could guarantee the service delay was constructed.Firstly

how to compute the time-deterministic route over the space information network was modeled as a non-linear programming.To mitigate the problem

a stochastic temporal graph model was proposed

which characterized the stochastic features

caused by the stochastic services of communication links

storage and temporal resources.In addition

the coupling relationship between storage and communication links was also modeled by the graph.Thus

a model was provided by the graph for enhancing the communication link utilization and supporting the time-deterministic routing.Based on this

a routing algorithm fulfilling service delay requirements with the highest probability was proposed with O(n

) polynomial time.The optimality of the algorithm was proved.

关键词

Keywords

references

DU J , JIANG C X , GUO Q , et al . Cooperative earth observation through complex space information networks [J ] . IEEE Wireless Communications , 2016 , 23 ( 2 ): 136 - 144 .

VLK M , HANZÁLEK Z , BREJCHOVÁ K , , et al . 1Qbv time-sensitive networks [J ] . IEEE Transactions on Communications , 2020 , 68 ( 11 ): 7023 - 7038 .

GROSSMAN E . Deterministic networking use cases [R ] . RFC Editor , 2019 .

YOSHIZAWA T , BASKARAN S B M , KUNZ A . Overview of 5G URLLC system and security aspects in 3GPP [C ] // 2019 IEEE Conference on Standards for Communications and Networking . Piscataway:IEEE Press , 2019 : 1 - 5 .

PECORELLA T , RONGA L S , CHITI F , et al . Emergency satellite communications:research and standardization activities [J ] . IEEE Communications Magazine , 2015 , 53 ( 5 ): 170 - 177 .

MOY J . OSPF protocol analysis [R ] . RFC Editor , 1991 .

BOOK B . Schedule-aware bundle routing [J ] . Consultative Committee for Space Data Systems , 2019 .

KYI M T , NAING L L . Application of ford-fulkerson algorithm to maximum flow in water distribution pipeline network [J ] . International Journal of Scientific and Research Publications (IJSRP) , 2018 , 8 ( 12 ): 306 - 310 .

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

RIBEIRO A , SIDIROPOULOS N D , GIANNAKIS G B . Optimal distributed stochastic routing algorithms for wireless multihop networks [J ] . IEEE Transactions on Wireless Communications , 2008 , 7 ( 11 ): 4261 - 4272 .

FU L Y , WANG X B , KUMAR P R . Are we connected? optimal determination of source–destination connectivity in random networks [J ] . IEEE/ACM Transactions on Networking , 2017 , 25 ( 2 ): 751 - 764 .

GENDREAU M , LAPORTE G , SÉGUIN R , . Stochastic vehicle routing [J ] . European Journal of Operational Research , 1996 , 88 ( 1 ): 3 - 12 .

RUSEK K , SUÁREZ-VARELA J ,, ALMASAN P , et al . RouteNet:leveraging graph neural networks for network modeling and optimization in SDN [J ] . IEEE Journal on Selected Areas in Communications , 2020 , 38 ( 10 ): 2260 - 2270 .

WANG J , TANG J , XU Z Y , et al . Spatiotemporal modeling and prediction in cellular networks:a big data enabled deep learning approach [C ] // IEEE INFOCOM 2017 - IEEE Conference on Computer Communications . Piscataway:IEEE Press , 2017 : 1 - 9 .

Views

548

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

AI问答

⁰