MPATH: A Loop-free Multipath Routing Algorithm

摘要

We present a distributed routing algorithm for computing multiple paths between each source-destination 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.