An efficient algorithm to enable path diversity in link state routing networks
Mon, 12/13/2010 - 00:27 by Olivier Bonaventure
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 additional 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.
- Authors
- Pascal Mérindol, Pierre Francois, Olivier Bonaventure, Stéphane Cateloin and Jean-Jacques Pansiot
- Source
Computer Networks , 55(1):1132-1149, April 2011.- Notes
- See http://dx.doi.org/10.1016/j.comnet.2010.11.005 or technical report at http://clarinet.u-strasbg.fr/~merindol/uploads/Research/TBFH_TR2010-01.p...
- Cite it
- BibTex
- Copyright
- See here
IEEE Copyright Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
ACM Copyright Notice: Copyright 1999 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page or intial screen of the document. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept., ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.
Springer-Verlag LNCS Copyright Notice: The copyright of these contributions has been transferred to Springer-Verlag Berlin Heidelberg New York. The copyright transfer covers the exclusive right to reproduce and distribute the contribution, including reprints, translations, photographic reproductions, microform, electronic form (offline, online), or any other reproductions of similar nature. Online available from Springer-Verlag LNCS series.