An efficient algorithm to enable path diversity in link state routing networks
An efficient algorithm to enable path diversity in link state routing networks
复制标题
DOI：
10.1016/j.comnet.2010.11.005
复制
发表时间：
2011-04
期刊：
影响因子：
--
通讯作者：
Pascal Mérindol;Pierre François;O. Bonaventure;Stéphane Cateloin;Jean-Jacques Pansiot
中科院分区：
文献类型：
--
作者：
Pascal Mérindol;Pierre François;O. Bonaventure;Stéphane Cateloin;Jean-Jacques Pansiot
多路径路由允许负载均衡和快速重路由，以提高网络的可靠性和效率。目前的IP路由器只支持等成本多路径(ECMP)，它保证转发路径不包含环路。但是，ECMP提供的路径多样性有限。本文提出了一种允许路由器实现更多路径分集的高效算法：该算法允许所有路由器计算至少两条到达每个目的地的最佳第一跳不同路径，并在路径分集和开销之间取得良好的折衷。此外，我们还提出了一种多径路由方案，其目标是将快速重路由和负载均衡的无环路由结合起来。我们方案的低开销(不需要额外的信令消息和低复杂性)和其无环规则的性质允许在当前的IP路由器上增量地部署它。使用实际的、推断的和生成的拓扑，我们将我们的算法与现有的解决方案进行比较。
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.