YAMR: Yet Another Multipath Routing Protocol

Igor Ganichev, Bin Dai, P. Brighten Godfrey, and Scott Shenker
Appears in: 
CCR October 2010

Multipath routing is a promising technique to increase the Internet’s reliability and to give users greater control over the service they receive. However, past proposals choose paths which are not guaranteed to have high diversity. In this paper, we propose yet another multipath routing scheme (YAMR) for the interdomain case. YAMR provably constructs a set of paths that is resilient to any one inter-domain link failure, thus achieving high reliability in a systematic way. Further, even though YAMR maintains more paths than BGP, it actually requires significantly less control traffic, thus alleviating instead of worsening one of the Internet’s scalability problems. This reduction in churn is achieved by a novel hiding technique that automatically localizes failures leaving the greater part of the Internet completely oblivious.

Public Review By: 
J. Wang

This paper presents an Interdomain multipath routing protocol. Multipath routing has been shown to be a promising technique to increase reliability of Internet routing and provide greater flexibility for users to choose paths that best suit their needs. In recent years, many schemes have been proposed to support multipath interdomain routing. These existing works demonstrated the feasibility of providing alternative paths in a scalable and policy-compliant manner. In this work, authors propose “Yet Another Multipath Routing Protocol” (YAMR). The contributions of this paper are two-fold. The paper first presents a path calculation mechanism called YPC. YPC constructs a set of policy-complaint interdomain routing paths which tolerant any single interdomain link failure. However, the increase in path resiliency comes at a price: a considerable increase in the control message overhead imposed by alternative path advertisement. The paper then presents a mechanism which reduce control message overhead by localizing routing updates. The idea is that a router does not notify its neighbors failure event if it still has an available path to reach the same destination. This method can effectively reduce the control message overhead. To avoid forwarding loops and disconnectivity due to information hiding, a token is used as a signal to determine if information hiding is needed or not. All reviewers found that this failure hiding mechanism is quite interesting.
The paper uses simulations to evaluate the benefit of YAMR and compares it with BGP. The results show that YAMR not only outperforms BGP in terms of reliability, but also bests BGP in terms of control message overhead (a benefit from failure hiding). These results clearly demonstrate that YAMR is a promising technique for multipath interdomain routing. The current evaluation is based on synthetic topology. It would be interesting to see how YAMR performs on the real Internet topology. In addition, there are many interesting performance tradeoffs that clearly need careful exploration. For example, YPC requires each router to keep a set of alternative forwarding paths. This would incease router FIB size consumption. This can be a concern that impacts the routing scalability. What would be the ideal tradeoff between the increase in path diversity and the increase in router FIB size? The failure hiding mechanism can lead to inconsistency between the control plane and the data plane. To what extend would this inconsistency impact the failure resilience and existing routing dependent systems on the Internet? All of these tradeoffs warrant further exploration.