Introduction

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.

Try It: Route Leak

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.

<!-- BGP Path Selection demo — five Autonomous Systems, one route leak -->
<div id="app">
  <div class="legend">
    <span class="leg-item"><span class="dot normal"></span> Normal path</span>
    <span class="leg-item"><span class="dot leaked"></span> Route-leak source (AS3)</span>
    <span class="leg-item"><span class="dot affected"></span> Affected ASes</span>
  </div>
  <canvas id="canvas" width="560" height="300"></canvas>
  <div id="info-box" class="info-box" aria-live="polite">Click "Trigger route leak" to see how a leak propagates through the topology.</div>
  <div class="btns">
    <button id="btn-leak" type="button">Trigger route leak</button>
    <button id="btn-reset" type="button" class="ghost">Reset</button>
  </div>
</div>

/* Styling for the BGP demo canvas and controls */
* { 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; }

/* BGP Path-Selection demo — route-leak propagation across 5 ASes */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* AS topology: id, display label, canvas position */
const ASes = [
  { id: 'AS1', label: 'Transit', x: 100, y: 60,  r: 30 },
  { id: 'AS2', label: 'Peer ISP', x: 280, y: 60,  r: 30 },
  { id: 'AS3', label: 'Customer', x: 100, y: 200, r: 30 },
  { id: 'AS4', label: 'Enterprise', x: 280, y: 200, r: 30 },
  { id: 'AS5', label: 'CDN', x: 420, y: 130, r: 30 }
];

/* BGP sessions (undirected); rel is informational only */
const EDGES = [
  { a: 0, b: 1, rel: 'peer' },
  { a: 0, b: 2, rel: 'provider' },
  { a: 1, b: 3, rel: 'provider' },
  { a: 1, b: 4, rel: 'peer' },
  { a: 2, b: 3, rel: 'peer' },
  { a: 2, b: 1, rel: 'peer' }
];

/* The IP prefix that AS1 originates */
const PREFIX = '10.1.0.0/16';

/* Demo state: normal routing or after the route leak */
let state = 'normal'; // normal | leaked

/* Routing paths per state: each value is an ordered list of AS indices from receiver to origin */
const PATHS = {
  normal: {
    AS1: [0],
    AS2: [1, 0],
    AS3: [2, 0],
    AS4: [3, 1, 0],
    AS5: [4, 1, 0]
  },
  leaked: {
    AS1: [0],
    AS2: [1, 2, 0],
    AS3: [2, 0],
    AS4: [3, 2, 0],
    AS5: [4, 1, 2, 0]
  }
};

/* ASes whose routing changes due to the leak */
const LEAKED_ASes = new Set(['AS2', 'AS4', 'AS5']);

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const infoBox = document.getElementById('info-box');
const btnLeak = document.getElementById('btn-leak');
const btnReset = document.getElementById('btn-reset');

/* Pick node fill colour based on role in the current state */
function asColor(id) {
  if (state === 'leaked' && id === 'AS3') return '#e05c2a';
  if (state === 'leaked' && LEAKED_ASes.has(id)) return '#d4a017';
  return '#3b7dd8';
}

/* Main draw function — redraws the entire canvas */
function draw() {
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  /* Draw BGP session lines (dashed) */
  ctx.lineWidth = 1.5;
  EDGES.forEach(({ a, b }) => {
    ctx.beginPath();
    ctx.strokeStyle = '#a0b0cc';
    ctx.setLineDash([4, 3]);
    ctx.moveTo(ASes[a].x, ASes[a].y);
    ctx.lineTo(ASes[b].x, ASes[b].y);
    ctx.stroke();
    ctx.setLineDash([]);
  });

  /* Draw active routing paths with their colour */
  const paths = PATHS[state];
  Object.entries(paths).forEach(([id, path]) => {
    if (path.length < 2) return;
    const color = (state === 'leaked' && LEAKED_ASes.has(id)) ? '#d4a017'
                : (state === 'leaked' && id === 'AS3') ? '#e05c2a'
                : '#3b7dd8';
    ctx.beginPath();
    ctx.strokeStyle = color;
    ctx.lineWidth = 2.5;
    for (let i = 0; i < path.length - 1; i++) {
      ctx.moveTo(ASes[path[i]].x, ASes[path[i]].y);
      ctx.lineTo(ASes[path[i + 1]].x, ASes[path[i + 1]].y);
    }
    ctx.stroke();
  });

  /* Draw AS nodes as filled circles with labels */
  ASes.forEach(({ id, label, x, y, r }) => {
    const col = asColor(id);
    ctx.beginPath();
    ctx.arc(x, y, r, 0, 2 * Math.PI);
    ctx.fillStyle = col;
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 11px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.fillText(id, x, y - 5);
    ctx.font = '9.5px system-ui, sans-serif';
    ctx.fillText(label, x, y + 9);
  });

  /* Show the originated prefix in the corner */
  ctx.fillStyle = '#1a2233';
  ctx.font = '11px ui-monospace, monospace';
  ctx.textAlign = 'left';
  ctx.fillText('Origin: ' + PREFIX, 8, canvas.height - 8);
}

/* Update the info box text to reflect the current state */
function updateInfo() {
  if (state === 'normal') {
    infoBox.textContent = i18nFmt('Normal routing — AS2, AS4 and AS5 reach %prefix% through AS1 (correct provider path).', { prefix: PREFIX });
  } else {
    infoBox.textContent = i18nFmt('Route leak! AS3 re-advertised %prefix% to AS2. AS2, AS4 and AS5 now route through AS3 instead of AS1.', { prefix: PREFIX });
  }
}

btnLeak.addEventListener('click', () => {
  state = 'leaked';
  btnLeak.disabled = true;
  draw();
  updateInfo();
});

btnReset.addEventListener('click', () => {
  state = 'normal';
  btnLeak.disabled = false;
  draw();
  updateInfo();
});

draw();
updateInfo();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bgp-path-selection/Content licensed under CC BY-NC 4.0.