20 Years of Inferring Interdomain Routing Policies

The Internet consists of numerous networks, known as Autonomous Systems (ASes), each owned by different organisations, including Internet Service Providers (ISPs), universities, and corporations. These ASes use the Border Gateway Protocol (BGP) to exchange routing information, enabling them to reach remote IP addresses through a series of AS hops, forming what is known as inter-domain routing.

BGP does not always follow the shortest path principle; instead, routing decisions are influenced by economic, performance, and security considerations. ASes independently set their routing policies to select the best routes and determine which routes to advertise to their neighbours. These decisions are often opaque, as ASes protect their proprietary business data and routing policies through non-disclosure agreements. This lack of transparency can make it challenging to understand, debug, and predict routing behaviour.

Characterising and inferring routing policies

In 2003, Wang and Gao revolutionised our understanding of Internet routing policies with an algorithm designed to infer and characterise these policies. Their work was essential for predicting and debugging routing paths, particularly when considering the phenomenon of selectively announced prefixes.

Over the past two decades, the Internet has transformed from a hierarchical structure to a more flattened and densely interconnected network. In our study, we replicated Wang and Gao's research to understand how selective announcements and routing policies have evolved over the past 20 years. Our findings highlight the persistent nature of selective announcements and the need for high-frequency BGP policy inference due to the dynamic nature of AS connectivity.

In this article, we give an overview of key concepts and findings from our recent paper. We delve into our replication of Wang and Gao's study, examining the persistence and evolution of selective announcements and their implications on current Internet routing policies.

Internet routing policies and the evolution of Internet structure

Routing policy inference

Routing policy inference involves understanding how ASes select and propagate routes. Import policies determine which route an AS chooses when multiple options are available, while export policies dictate which routes are advertised to neighbouring ASes. Wang and Gao's work was pivotal in showing that routing policies are more complex than previously understood and require continuous study to model accurately.

Business relationships among ASes

ASes establish interconnections based on various business agreements, which can be categorised into three primary types: customer-to-provider (c2p), peer-to-peer (p2p), and sibling-to-sibling (s2s). These relationships influence both the import and export routing policies of ASes. For instance, routes learned from customers are usually preferred over those from providers because customer traffic generates revenue. This route ordering based on the business relationships among ASes is known as the Gao-Rexford model.

Import routing policies

BGP routers follow a complex decision process to select the best route to a destination. This process prioritises routes based on several criteria, including local preference (locpref, hereon), AS path length, and origin type. The highest priority is given to routes with the highest locpref value. Typically, ASes assign higher locpref values to routes from customers and lower values to routes from providers, following the Gao-Rexford model to ensure global routing convergence.

Export routing policies

Export policies determine which routes an AS advertises to its neighbours. These policies are often guided by the valley-free rule, which prevents ASes from providing free transit to providers or peers. This rule ensures that customer routes can be advertised to any neighbour, but routes from peers or providers are only advertised to customers.

In addition to the valley-free rule, an AS may select to further restrict the propagation of certain routes for traffic engineering purposes. For example, in Fig. 1, below, AS13335 is multihomed to two providers but propagates an announcement for prefix p only to its direct provider AS3549 and not to AS9498. This selective announcement strategy can be observed through the routing tables of AS3257. By selectively advertising routes to different neighbours an AS may be able to control the links which will carry traffic for a specific route.

Changes in Internet topology

The Internet has undergone significant structural changes over the past two decades. In the early 2000s, the Internet was viewed as a multi-tiered hierarchy with a small number of Tier-1 ISPs providing global connectivity through peering links. Over time, this hierarchy has flattened, largely due to the rise of Content Providers (CPs) and Content Delivery Networks (CDNs), which have built extensive private networks to improve end-to-end performance and control.

IXPs have played a crucial role in the flattening of the Internet topology. They enable direct peering between large CDNs and other networks, bypassing Tier-1 ISPs and reducing transit costs. This shift has significantly changed the dynamics of inter-domain routing, as evidenced by the increased percentage of peer links over the past 25 years:

This table illustrates the growth in the percentage of peer links over the last 25 years, indicating the flattening of the AS-topology. In 1998, peer links accounted for 13% of all AS links, while by 2023, this figure had risen to 69%.

One metric that reflects the position of an AS in the IP transit market is the customer cone (CC) size, which expresses the number of ASes that a provider AS can access through routes learned from its customers. In Fig. 2, below, we plot the CC distributions in 2003 and 2023 respectively. Both distributions look similar, nonetheless, we observe that the maximum CC size has increased one order of magnitude (rightmost x-axis value).

This increase can be possibly explained by two factors. First, the number of ASes advertised in the BGP Default-Free Zone (DFZ) in 2023 has quadrupled since 2003, while the IPv4 address space is in the exhaustion phase. Additionally, over the past two decades there has been a trend of consolidation in the IP transit market, which led to fewer but larger transit providers.

Key findings from our study

• Prevalence of selective announcements: Selective announcements, where ASes announce prefixes to specific providers to manipulate traffic, remain a common practice even 20 years after they were first introduced. In our study, we observe that the use of selective announcements has increased by up to 30% over the past two decades, though there is significant variability among ASes (as shown in Fig. 3). This trend indicates that selective announcements are a highly dynamic aspect of Internet routing and should be computed on a regular basis.

• Variability in Local Preference: The assignment of Local Preference (locpref) values, which influence route selection, shows greater variability today compared to 2003. Specifically, for all studied routes, locpref allocations are consistent with AS relationships only in 83% of the cases, varying between 39-99% across the tested ASes. In contrast, in the original 2003 study the average consistency was above 99%. Therefore, we observe that locpref allocations have become significantly less conventional. This change suggests that ASes are using more diverse strategies to manage their routing policies and do not rely on AS relationships as heavily as they used to.

• Implications for Routing Path Inference: The differences in routing policies between 2003 and today highlight the challenges in accurately inferring AS paths. Our findings suggest that current models need to account for the increased variability and dynamic nature of AS relationships.

Conclusion

Our study replicates and extends the seminal work of Wang and Gao, providing a comprehensive analysis of the evolution of Internet routing policies over the past two decades. The persistence and increased variability of selective announcements highlight the need for continuous and high-frequency BGP policy inference. As the Internet continues to evolve, understanding and accurately modelling inter-domain routing policies will be crucial for improving network operations and ensuring reliable connectivity.

The insights gained from our replication study can inform various applications, including routing security, network optimisation, and the development of new inter-domain routing models. By making our data and source code publicly available, we aim to facilitate further research and foster a deeper understanding of Internet routing dynamics.

For more detailed information and access to our datasets, please refer to our paper.

The research paper this article was based on is published in the Proceedings of the 2023 ACM Internet Measurement Conference (IMC ’23), October 24–26, 2023, Montreal, QC, Canada by authors: Savvas Kastanakis (Lancaster University), Vasileios Giotsas (Cloudflare), Ioana Livadariu (Simula Metropolitan Center), Neeraj Suri (Lancaster University).

For inquiries or further discussion, please contact Savvas Kastanakis or Vasileios Giotsas.