Internet compact routing and content locality

The Border Gateway Protocol (BGP) is the de-facto routing protocol for the Internet, responsible for maintaining the routing paths along which packets are forwarded. As reliance on the Internet has become more important in daily life, the BGP routing table has increased at a near-exponential rate. This table size growth has created a far higher demand on router hardware, motivating the research and standards community to develop solutions for reducing routing table size whilst maintaining reachability.

Compact routing schemes can achieve a sub-linear table growth by trading shortest-path routing for a routing table size reduction. Cowen Landmark Routing is a compact routing scheme that has been described in a distributed manner and is suitable for Internet deployment. However, this scheme has not been entirely formalised or evaluated on representative network graphs.

There are other areas that have been affected by Internet growth. In regions with well-developed infrastructure, thoughts are turning to the environmental impact of technology. In developing regions, research focus is put on the locations that are traversed when accessing content. There is an active debate about how statistics like carbon intensity should be gathered and disseminated, but far less work has been done to reliably measure content locality.

This thesis provides algorithms for a compact routing protocol which are evaluated on Internet AS graphs. Results show that the protocol can achieve a substantial table size reduction, with a mean reduction of 98% and a low path stretch of 1.11x. Considerations for protocol deployment, including required changes to addressing and forwarding schemes, protocol security risks, and policy implementation, are also presented.

In addition, this thesis describes a methodology for measuring Internet content locality, providing results from an ongoing measurement campaign. These results are used to show that compact routing could support additional routing goals, such as increasing content locality or carbon-aware networking capabilities.