A New Fault-Tolerance Mechanism in Communications Based on KShortest Path Algorithm
Mao Shaow · Journal of Wuhan University · 2013
Classic Kshortest path algorithm is an important branch of the shortest path algorithm,which plays a very important role in path choosing of the real-time traffic network.In order to apply classic Kshortest path algorithm to communication networks,we improved the classic Kshortest path algorithm.When finding the K maximum capacity paths,transform network at first,then use MPS algorithm;to find K maximum capacity path,choose the maximum capacity correspond to source,destination,and arcs for labels;to find K maximum expected capacity path,we create a series of sub-networks for each sub-network to find the most dependable path at first,to sort their capacity to get the smallest,then all arcs whose capacity is greater than the smallest is defined as a sub-network of this subnetwork,until there is no paths from the source point to the target point.Then order them entirely for K maximum expected capacity path of each sub-network to get the K maximum expected path,and then through a network communication example to verify the correctness and feasibility of the algorithms.