A Dirty-Slate Approach to Routing Scalability

This paper presents Virtual Aggregation, an architecture that attempts to tackle the Internet routing scalability problem. Our approach does not require any changes to router software and routing protocols and can be deployed by any ISP without the cooperation of other ISPs. Hence, Virtual Aggregation is a configuration-only solution. The key insight here is to use divide-and-conquer so that default-free zone routers don?t need to maintain the entire routing table. Instead, an ISP can modify its internal routing such that individual routers in its network only maintain a part of the routing table. We evaluate the application of Virtual Aggregation to a few tier-1 and tier-2 ISPs and show that it can reduce routing table size on individual routers by an order of magnitude while imposing almost no traffic stretch and very little increase in router load. We also deploy Virtual Aggregation across two different testbeds comprising of Cisco and Linux routers. Finally, we detail some shortcomings of the proposed design and discuss alternative designs that alleviate some of these. However, in spite of the limitations, we believe that the simplicity of the proposal and its possible short-term impact on routing scalability suggest that it is an alternative worth considering