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

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

Jose M. Camacho (Universidad Carlos III de Madrid, Spain), Lisardo Prieto (Universidad Carlos III de Madrid, Spain) and Francisco Valera (Universidad Carlos III de Madrid, Spain)
DOI: 10.4018/jaras.2011070103
OnDemand PDF Download:
List Price: $37.50


The simultaneous usage of multiple paths in communication networks has the potential to generate important benefits like better utilization of available resources and higher resiliency. Routing solutions with poor adaptive performance can benefit from multi-path techniques, since information about alternative paths is gathered beforehand. In particular, this study explores the embracement of multi-path routing by inter-domain routing protocols, which have been proven to have large convergence delay after network changes. Unfortunately, there are not many tools available to evaluate and compare the adaptive properties of different multi-path inter-domain routing proposals. An evaluation framework for those proposals is presented in this paper. The framework is aimed to provide a common ground for their evaluation and comparison. It is conceived based on a Swiss-army-knife approach and has a modular and extensible architecture. For completeness, a case of use is depicted to show the functionality and analyses that can be carried out using this framework.
Article Preview


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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 8: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 7: 1 Issue (2016)
Volume 6: 2 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing