MLSA: A link-state multipath routing algorithm

High reliability is always pursued by network and protocol designers. Multipath routing can provide multiple paths for transmission and failover, and is considered to be effective in the improvement of network reliability. To compute multiple paths efficiently, we present MLSA, a tree based link-state multipath algorithm, to help a node to find multiple next hops for each destination. On each node, only a single tree needs to be maintained, locally and independently, while no other information than the basic link states need to be exchanged. We also prove the loop-freeness of MLSA, guaranteed by a underlying partial order established over the nodes. We evaluate MLSA with both real and synthetic topologies. The simulation results show that, MLSA can achieve comparable reliability as the naive algorithms based on shortest path trees, with much less computation overhead.