An efficient algorithm to enable path diversity in link state routing networks
(2011) Computer Networks — Vol. 2011, n° 55, p. 1132–1149 (5) (2011)
Files
merindol.pdf
Restricted Access - Adobe PDF
- 673.9 KB
Details
- Authors
- Abstract
- Multipath routing allows for load balancing and fast re-routing in order to improve the reliability and the efficiency of the network. Current IP routers only support Equal Cost MultiPath (ECMP) which guarantees that the forwarding paths do not contain loops. However,ECMP provides limited path diversity. In this paper, we present an efficient algorithm that allows routers to enable more path diversity: our algorithm let all routers compute at least the two best first hop distinct paths towards each destination and achieves a good tradeoff between path diversity and overhead. In addition, we propose a multipath routing scheme whose goal is to combine fast re- routing and load balancing loop-free routes. The low overhead of our scheme (no addi- tional signaling messages and low complexity) and the nature of its loop-free rules allow to incrementally deploy it on current IP routers. Using actual, inferred, and generated topologies, we compare our algorithm to existing solutions.
- Affiliations
Université de Strasbourg Laboratoire des sciences de l'image, de l'informatique et de la télédétection Université de Strasbourg Département informatique
Citations
Mérindol, P., François, P., Bonaventure, O., Cateloin, S., & Pansiot, J.-J. (2011). An efficient algorithm to enable path diversity in link state routing networks. Computer Networks, 2011(55), 1132–1149 (5). https://doi.org/10.1016/j.comnet.2010.11.005 (Original work published 2011)