Computer Science Department
School of Computer Science, Carnegie Mellon University
Understanding Route Aggregation
Franck Le*, Geoffrey G. Xie**, Hui Zhang
March 2010
Route aggregation, the method to supersede a set of routes by a single, more general route, is a universal mechanism that is either explicitly included in a routing protocol specification or added by router vendors as a configuration option. Widely deployed for both intra-domain and interdomain routing purposes, route aggregation (RA) can be vulnerable to routing anomalies, and is fingered to be the cause of many reported loops and blackholes. In this paper, we posit that the problem arises from a lack of fundamental understanding of the RA mechanism. Moreover, we present the first rigorous and comprehensive analysis of route aggregation based on an absract model. We show that the range of potential anomalies from RA configurations is much wider than previously documented. We demonstrate that existing RA configuration guidelines are inadequate. We further prove that determining whether the collection of RA configurations in a network can result in a persistent forwarding loop is NP-hard. Given this complexity, we identify a sufficient condition for ensuring convergence and loop-free forwarding paths. Finally, from the condition, we derive a migration strategy to harden existing and future network designs against RA-induced route oscillations and forwarding loops.
32 pages
*Department of Electrical and Computer Engineering, Carnegie Mellon University
**Department of Computer Science, Naval Postgraduate School, Monterey, CA
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu
School of Computer Science