基于随机时变图的时间确定性网络路由算法  

Time deterministic network routing algorithm based on stochastic temporal graph

作　　者：王鹏[1] 张修社 索龙[1] 史可懿 WANG Peng;ZHANG Xiushe;SUO Long;SHI Keyi(Xidian University State Key Laboratory of Integrated Service Networks,Xi’an 710071,China;Twentieth Research Institute of China Electronics Technology Group Corporation,Xi’an 710071,China)

机构地区：[1]西安电子科技大学综合业务网理论及关键技术国家重点实验室,陕西西安710071 [2]中国电子科技集团公司第二十研究所,陕西西安710071

出　　处：《通信学报》2021年第9期21-30,共10页Journal on Communications

基　　金：基础加强重点基金资助项目(No.2020JCJQXXX)。

摘　　要：针对天地一体化网络环境中网络时变性和业务时延确定性保障之间的矛盾,构建了随机时变图模型,并基于该模型提出了时间确定性网络路由算法。首先,将空间信息网络最大概率时延保障路由计算问题建模为非线性规划问题。为解决该问题,提出了随机时变图模型,联合表征了由业务随机性导致的链路、存储与时间资源的随机特征,并且表征了存储与链路资源的关联关系,为链路资源利用率的提升与业务的时间确定性保障提供了模型基础;在此基础上,提出了时间复杂度为O(n2)的最大概率时延保障的路由算法,并证明了该算法的最优性。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(n2)polynomial time.The optimality of the algorithm was proved.

关 键 词：随机时变图 时间确定性路由 最大概率时延保障 时间确定性网络 天地一体化网络 

分 类 号：TN915.03[电子电信—通信与信息系统]