Show simple item record

dc.contributor.authorLe, F.
dc.contributor.authorZhang, H.
dc.contributor.authorXie, Geoffrey
dc.dateDecember 2011
dc.date.accessioned2013-08-01T21:11:12Z
dc.date.available2013-08-01T21:11:12Z
dc.date.issued2011-12
dc.identifier.urihttp://hdl.handle.net/10945/34804
dc.descriptionProc. ACM CONEXT Conference, Tokyo, Japan, December 2011.en_US
dc.descriptionThe article of record as published may be found at http://dx.doi.org/10.1145/2079296.2079302en_US
dc.description.abstractRoute 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 cleanslate designs for RA.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 cleanslate designs for RA.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 cleanslate designs for RA.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 cleanslate designs for RA.en_US
dc.rightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.en_US
dc.titleOn Route Aggregationen_US
dc.contributor.departmentComputer Science (CS)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record