BGP Path Selection

Every time you load a web page, your packets cross a dozen or more separate networks. The protocol that decides which networks to cross — and in what order — is BGP, the Border Gateway Protocol.

BGP divides the internet into Autonomous Systems (ASes): numbered networks controlled by a single organisation — a university, a cloud provider, an ISP. Right now roughly 75,000 ASes are reachable on the public internet. Each one runs BGP to advertise the IP prefixes it owns and to learn the prefixes owned by everyone else.

When two ASes exchange BGP routes, they describe a path through a sequence of AS numbers. A router that hears several paths to the same destination applies a strict priority waterfall — a list of nine tie-breaking rules — to pick exactly one winner. The first rule that distinguishes two paths settles the contest; the rest are never consulted.

That design is elegant and deliberately policy-neutral: each AS decides locally what it prefers, and no global coordinator is needed. It is also the reason a single misconfigured router in a small ISP can redirect traffic meant for a bank, a DNS root server, or an entire country.

The demo below shows a small internet of five Autonomous Systems. Each AS announces one or more prefixes and maintains BGP sessions with its neighbors. Click Trigger route leak to make AS3 (a customer) accidentally re-advertise a prefix it learned from its provider (AS1) to a different provider (AS2). Watch how BGP's path-selection waterfall propagates the leak and redirects traffic.

<!-- {{c_html_intro}} -->
<div id="app">
  <div class="legend">
    <span class="leg-item"><span class="dot normal"></span> {{leg_normal}}</span>
    <span class="leg-item"><span class="dot leaked"></span> {{leg_leaked}}</span>
    <span class="leg-item"><span class="dot affected"></span> {{leg_affected}}</span>
  </div>
  <canvas id="canvas" width="560" height="300"></canvas>
  <div id="info-box" class="info-box" aria-live="polite">{{info_default}}</div>
  <div class="btns">
    <button id="btn-leak" type="button">{{btn_leak}}</button>
    <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; color: #1a2233; }
#app { display: flex; flex-direction: column; align-items: center; gap: .6rem; padding: .5rem; }
.legend { display: flex; gap: 1rem; font-size: .82rem; flex-wrap: wrap; justify-content: center; }
.leg-item { display: flex; align-items: center; gap: .35rem; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 50%; }
.dot.normal   { background: #3b7dd8; }
.dot.leaked   { background: #e05c2a; }
.dot.affected { background: #d4a017; }
canvas { border: 1px solid #d0d8e4; border-radius: 8px; background: #f6f8fb; max-width: 100%; }
.info-box { font-size: .88rem; background: #eef1f7; border: 1px solid #c8d0dd; border-radius: 6px;
            padding: .5rem .9rem; max-width: 520px; width: 100%; min-height: 2.6em; text-align: center; }
.btns { display: flex; gap: .6rem; flex-wrap: wrap; justify-content: center; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .95rem;
         border: 1px solid #2a5ca8; background: #2a5ca8; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #2a5ca8; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice what happens: AS2 and AS5 now see AS3 as a shorter path to the leaked prefix, even though AS3 is not authorised to carry that traffic. BGP has no built-in authenticity check — it trusts every announcement at face value. Click Reset to restore the correct routing state.

BGP looks simple: pick the path with the highest local preference, then the shortest AS path, then the lowest MED, and so on. But beneath the waterfall lies a genuinely hard problem.

• Convergence is not guaranteed. In 1999 Timothy Griffin and Gordon Wilfong proved that when ASes have conflicting routing policies — each preferring a path that another AS refuses to export — BGP can oscillate indefinitely without ever settling. They called this the Stable Path Problem.
• Finding a stable state is NP-hard. In general, deciding whether a set of AS policies even admits a stable routing is as hard as satisfying a Boolean formula. The internet works in practice mainly because real policies tend to follow the Gao–Rexford conditions (valley-free routing), which do guarantee convergence.
• Route leaks are a trust problem. BGP was designed in 1989 for a small, cooperative internet. Every AS is trusted to announce only what it owns and to forward only what it should. When a customer leaks a provider's prefix to another provider, the protocol has no way to detect or reject it without external mechanisms like RPKI (Resource Public Key Infrastructure).
• The 2010 China Telecom incident re-routed roughly 15% of the internet's prefixes through AS4134 for 18 minutes. The 2008 Pakistan Telecom incident took YouTube offline worldwide. Both were route leaks, not attacks — yet the effect was indistinguishable from sabotage.

The deeper lesson is the same as in P vs NP: checking that a single routing table is consistent with a policy is easy; finding or guaranteeing a globally stable state is hard. BGP's design side-steps the hardness by trusting operators to cooperate — an assumption that graph coloring-style constraint solvers cannot make.

BGP path selection is not an academic curiosity — it shapes what you can reach, how fast, and whether anyone can intercept it:

• Internet outages: Facebook's 2021 six-hour outage was triggered by a BGP configuration change that withdrew its own prefixes, making it unreachable from the outside and locking out its own engineers.
• Cloud latency: hyperscalers spend enormous effort on BGP policy tuning to ensure traffic enters their networks at the nearest point of presence, shaving milliseconds off global latency.
• Censorship and surveillance: governments can instruct state-controlled ASes to announce more-specific prefixes for targeted destinations, attracting traffic for inspection or blocking.
• Security with RPKI: Route Origin Authorization (ROA) records let a prefix owner cryptographically sign which AS may originate it. Validating routers reject announcements that contradict the ROA — closing the most common leak vector.
• BGP security research: the stable path problem continues to motivate work on formally verifiable routing policies, drawing on constraint-satisfaction ideas from SAT solving.

Every outage, every millisecond of latency, every successful or failed censorship attempt is ultimately a BGP path-selection decision playing out across tens of thousands of routers simultaneously.

BGP is a marvel of pragmatic engineering: nine tie-breaking rules, applied locally by each AS, coordinate the routes of the entire global internet with no central authority. For decades it has held the internet together on little more than operator cooperation.

But the Stable Path Problem shows that this cooperative assumption is load-bearing. When it breaks — whether by misconfiguration, accident, or malice — the same algorithm that connects 75,000 networks can redirect continents. RPKI and route filtering are the patches; formal policy verification is the long-term research frontier.

The next time a website is unreachable, there is a real chance that somewhere in the world a router applied BGP's nine rules faithfully, picked the wrong winner, and sent your packets on a detour nobody intended. That is not a bug in the algorithm — it is a feature of any P vs NP-hard problem running on a network built for trust.