Evaluation Framework for Adaptive Multi-Path Inter-Domain Routing Protocols

Introduction

The availability time of a communication network and the services that it provides is an important performance and quality ratio. Full availability is not possible in practice, nodes and links fail at a certain frequency, so that the routing system must re-compute alternative paths. Adaptive routing protocols are aimed to update reachability information in the network as fast as possible, which should reduce the disruption time of the traffic after node or link failures.

Multi-path routing techniques allow routers to use different alternative paths to reach a network destination. This is possible since several next-hops are installed in the forwarding table of the router and they can be used concurrently. Multi-path routing has the potential to bring in notorious advantages to communication networks (Bagnulo, Burness, Eardley, García-Martínez, Valera, & Winter, 2009; Valera, Beijnum, Garcia-Martinez, & Bagnulo, 2010). For instance, effective increase in network capacity, scalable traffic engineering and regarding adaptive routing, faster response to network changes.

Intra-domain routing systems already benefit from multi-path routing features (Psenak, Mirtorabi, Roy, Nguyen, & Pillay-Esnault, 2007; Albrightson, Garcia-Luna-Aceves, & Boyle, 1994). As for inter-domain routing, there are proposals (Xu & Rexford, 2006; Beijnum, Crowcoft, Valera, & Bagnulo, 2009; Godfrey, Ganichev, Shenker, & Stoica, 2008; Motiwala, Feamster, & Vempala, 2007) to add multi-path capabilities, nevertheless the deployment of solutions is limited (Valera, Beijnum, Garcia-Martinez, & Bagnulo, 2010; CISCO Systems, 2010). Therefore, it is expected that additional multi-path inter-domain proposals appear and specialized evaluation tools, like the framework presented in this work, are likely to be needed in order to compare their adaptive properties.

BGP is the de-facto inter-domain routing standard nowadays. Routing based on the BGP protocol (and inter-domain routing in general) belongs to the category of policy-based routing systems. Policy-based routing systems, in contrast to cost-based routing, do not try to minimize a cost or weight function in a distributed manner. Instead, they try to align the steady-state path assignment of the network such that each node fulfils its preferences (i.e. the paths used to send the traffic in the steady-state match the specifics of the routing policy). Whereas cost-based routing can be guaranteed to converge analytically by means of theoretical frameworks such as routing and path algebras (Chau, Gibbens, & Griffin, 2006), policy-based routing is not guaranteed to converge for some (valid) configurations, since the relation among AS policies may be conflicting (Chau, 2006; Griffin, Shepherd, & Wilfong, 2002; Walton, 2001).

Typically, those unstable situations do not happen in practice thanks to the hierarchy imposed by the business relationships between providers. On the other hand, even under stable configurations, the same business relationships oblige ASes to hide connectivity details and the network visibility of peers is constrained to paths economically appealing to the announcing AS.