MPATH: a loop-free multipath routing algorithm ?
We present a distributed routing algorithm for computing multiple paths between each sourcedestination pair in a computer network, such that the paths are loop-free at all times and are not necessarily of equal length. In this algorithm, routers exchange second-to-last hop on the shortest path to destinations in addition to shortest distances, which are used to prevent the well-know count-to-infinity problem. The safety and liveness properties of the algorithm are proved and its performance is analyzed.
distributed routing algorithm multiple paths count-to-infinity problem