Time deterministic network routing algorithm based on stochastic temporal graph - Peng WANG; Xiushe ZHANG; Long SUO; Keyi SHI (Tongxin xuebao, 2021)
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.