MDVA: A Distance-Vector Multipath Routing Protocol

Routing protocols using the Distributed Bellman-Ford DBF algorithm converge very slowly to the correct routes when link costs increase, and in the case where a set of link failures results in a network partition, DBF simply fails to converge, a problem that is commonly referred to as the count-to-infinity problem. In this paper, the authors present the first distance vector routing algorithm, the Multipath Distance-Vector Algorithm MDVA, that uses a set of loop-free invariants to prevent the count-to-infinity problem. In addition, MDVA computes multipaths that are loop-free at every instant. In their earlier work, the authors showed how such loop-free multipaths can be used in traffic load-balancing and delay minimization, which otherwise are impossible to perform in current single-path routing algorithms.