Disjoint Path Optimization And Shortest Path Repair Algorithm Research In Time-varying Networks

In transportation and communication networks,due to frequent occurrence of failures such as natural disasters,service attacks,etc.,all these major problems will lead to network service failures and interruptions.Therefore making reasonable fault tolerance and recovery mechanisms are important for the normal transmission of the network.These mechanisms can still maintain service continuity when the network fails or is attacked.Usually,to ensure high fault tolerance and high transmission continuity of the network system,node or link disjoint paths is usually designed to improve fault tolerance performance and a global or local fault recovery scheme is usually designed to improve path transmission continuity.In addition,due to the time-varying and large-scale nature of real networks,in many industrial applications,it is an urgent need to real-time response to faults and establish fault emergency plans that satisfy the required real-time constraints.Therefore,this paper considers the fault emergency plans of the network in terms of fault tolerance and path transmission continuity in the time-varying network.In terms of path fault tolerance,in order to avoid network paralysis caused by failure,multi-path routing scheme is usually designed to improve the fault tolerance and reliability of the system.Because node-disjoint multi-path routing can well cope with frequent network changes and repeated link failures.So a special scheme is to use the node-disjoint multi-path method to optimize network performance.Therefore,this paper first proposes a minsum time-varying two node-disjoint paths problem from the source to the destination in first-in and first-out(FIFO)time-varying network,i.e.find two node-disjoint paths at any time and satisfy minimizing total time-varying delay of these two paths.In the process of designing the algorithm scheme,this paper adopts the method of dividing the time interval and design the time difference function to construct a time-varying interlacing path,and finally the algorithm scheme obtains the optimal solution in O(n~2α(T)~3)time.In terms of path transmission continuity,when a fault occurs,the general solution is to reroute a feasible path from the source to the destination.However,rerouting usually leads to high time and space complexity.Therefore,adopt local repair to design a resonable path scheme is very necessary to alleviate link or node failure.Based on this,this paper studies the problem of path fault repair in time-varying networks,and proposes an effective algorithm to solve the shortest path repair problem in time-varying networks.The algorithm scheme designs a time-varying adaptive parameter |δ|t to measure the variation of the time-varying network scale and repair the faults of the time-varying path in a local range.It not only ensures the time continuity of nodes in time-varying networks,but also makes full use of the time-varying shortest path subgraph to reduce the computational complexity and ensure the transmission continuity.Finally,for a time-varying network with n nodes and m edges,the time complexity of the algorithm is O(α(T)·[‖δ‖_t+|δ|_t·log|δ_|t]),where |δ|_t represents the maximum number of affected interval nodes in all departure time intervals,‖δ‖_t represents the total maximum number of affected interval nodes and interval edges in all departure time intervals.From the perspective of fault tolerance and path transmission continuity,this paper respectively designs multi-path routing scheme and local repair scheme in a time-varying network.This paper provides theoretical basis and technical support for reliable communication of time-varying networks.