Stable Internet routing without global coordination

By Lixin Gao, Jennifer Rexford. Measurement and Modeling of Computer Systems, 2000

780 citations recorded by the source corpus.

The Border Gateway Protocol (BGP) allows an autonomous system (AS) to apply diverse local policies for selecting routes and propagating reachability information to other domains. However, BGP permits ASes to have conflicting policies that can lead to routing instability. This paper proposes a set of guidelines for an AS to follow in setting its routing policies, without requiring coordination with other ASes. Our approach exploits the Internet's hierarchical structure and the commercial relationships between ASes to impose a partial order on the set of routes to each destination. The guidelines conform to conventional traffic-engineering practices of ISPs, and provide each AS with significant flexibility in selecting its local policies. Furthermore, the guidelines ensure route convergence even under changes in the topology and routing policies. Drawing on a formal model of BGP, we prove that following our proposed policy guidelines guarantees route convergence. We also describe how our methodology can be applied to new types of relationships between ASes, how to verify the hierarchical AS relationships, and how to realize our policy guidelines. Our approach has significant practical value since it preserves the ability of each AS to apply complex local policies without divulging its BGP configurations to others.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/388b2ae49a80071672e4fdbfb0d7d6053953fd81

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Electrical and Electronic Engineering

Citations in the corpus

AS relationships, customer cones, and validation (2013, positive): “Second, we use policy information encoded in the RIPE WHOIS database to extract more than 6,500 unique relationships; we extract only relationships between ASes where both ASes have policies recorded in the database and both policies are expressed consistently.”
Route flap damping exacerbates internet routing convergence (2002, background): “Later, Grif.n and Wilfong [6] showed the intractability of determining a safe policy con.guration for BGP. Finally, Rexford and Gao [20] proved that if BGP s policy expressiveness is con.ned to a simple set of policies, persistent route oscillations cannot occur.”
The stable paths problem and interdomain routing (2002, background): “A more elaborate set of guidelines, together with correctness proofs, can be found in [4].”
A new approach to interdomain routing based on secure multi-party computation (2012, background): “With nexthop policies and Gao-Rexford constraints, it is known that such a round-based computational process will converge after 2D+1 rounds [11], where D is the height of the Gao-Rexford hierarchy [4].”
Characterizing the Internet hierarchy from multiple vantage points (2002, background): “…directly into policies for exporting route advertisements via BGP sessions with neighboring ASes: • Exporting to a provider: In exchanging routing information with a provider, an AS can export its routes and routes of its customers, but cannot export routes learned from other providers or peers.”
Delayed Internet routing convergence (2000, background): “Griffin et al. in [11] and Rexford et al. in [8] also describe modifications to BGP policies which guarantee that the protocol will not diverge.”
Locating internet routing instabilities (2004, background): “The policies outlined above capture only a small subset of all possible relationships between two ASes, but they seem to apply to a substantial part of the relationships [31], [32], [33].”
A Survey of BGP Security Issues and Solutions (2010, background): “Policies configured in a BGP router allow it to filter the routes received from each of its neighbors (import policy), filter the routes advertised to its neighbors (export policy), select routes based on desired criteria, and forward traffic based on those routes [19], [20].”