APT: A Practical Tunneling Architecture for Routing Scalability∗

The routing table has seen a rapid increase in size and dy-namics in recent years, mostly driven by the growth of edge networks. This growth reflects two major limitations in the current architecture: (a) the conflict between provider-based addressing and edge networks ’ need for multihoming, and (b) flat routing’s inability to provide isolation from edge dy-namics. To address these limitations, we propose A Prac-tical Tunneling Architecture (APT), a new routing architec-ture that enables the Internet routing system to scale inde-pendently from edge growth. APT partitions the Internet ad-dress space in two, one for the transit core and one for edge networks, allowing edge addresses to be removed from the routing table in the transit core. In order to tunnel packets between edge networks, APT provides an efficient mapping service between edge addresses and the addresses of their transit-core attachment points. We conducted an extensive performance evaluation of APT using trace data collected from routers at two major service providers. Our results show that APT can tunnel packets through the transit core by imposing a minimal delay on no more than 0.8 % of all packets at the cost of introducing only one or a few new or repurposed devices per AS