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

Time deterministic network routing algorithm based on stochastic temporal graph

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