Abstract
Route Aggregation (RA), the method to supersede a set of routes by a single, more general route, is a fundamental mechanism to the Internet scalability. Yet, despite its importance, it is poorly understood. We present the first systematic analysis of RA via both bottom-up experimental and top-down analytical approaches. We first conduct a set of experiments on RA behaviors of all major routing protocols as implemented by the two leading router vendors. Our experiments show that the RA behaviors vary significantly across routing protocols and vendors. We propose two router level primitives and incorporate them into a canonical router model. The new model captures the diversity of the observed behaviors. With aid of the model, we have advanced the fundamental understanding of RA on three fronts. First, we expose four new types of routing anomaly that can derive from RA. Configuring RA on one router interface can influence how routes are advertised on other interfaces of the same router, impacting network reachability in surprising ways. Second, we demonstrate that determining whether a RA configuration can result in persistent forwarding loops is NP-complete. Finally, we present sufficient conditions for RA primitives to guarantee routing safety, and explore clean-slate designs for RA. © 2011 ACM.