Anycast

Deep dive

How it works

In: one prefix announced from N sites; client source networks · Out: the site each client's packets reach · State: BGP routes in every router (RIB); per site, an up/withdrawn flag · Cost: O(1) per packet; O(sites) per router per prefix on change

1. Every site originates the same prefix (a /24 or shorter for IPv4, /48 or shorter for IPv6).
2. Each BGP router collects the announcements it hears and picks one best path per prefix: highest LOCAL_PREF, then shortest AS_PATH, then lowest origin and MED, eBGP over iBGP, lowest IGP cost, then lowest router id (RFC 4271 §9.1.2).
3. Packets to any address in the prefix follow that router's single best path, so each source network lands on one site. The set of sources per site is its catchment (RFC 4786).
4. Inside a site, an ECMP router spreads flows over servers; an L4 balancer keeps a flow on one server.
5. A local health check gates the announcement: service down, route withdrawn (RFC 4786 §4.4.1). Routers drop that path and fall back to their next-best site; only the withdrawn site's clients move.
6. Operators move load by changing what a site announces: AS-path prepends, communities, or announcing from fewer neighbours.

Catchments are policy, not geography: a higher LOCAL_PREF beats a shorter path to a closer site. Li et al. measured a root server with 100+ sites and 400M+ queries a day: site loads were often unbalanced and most queries travelled further than necessary, many by over 5000 km.

Stateful transports. RFC 7094 says UDP is the "lingua franca" for anycast and that TCP fails "probabilistically, but possibly catastrophically" when a route changes mid-connection. Measured (Wei and Heidemann, 9000+ vantage points, 11 root-DNS services): about 1% of vantage points were anycast-unstable; TCP flipping occurred in about 0.15% of (vantage point, service) pairs. Short connections mostly survive; no guarantee.

Prefix size. Prefixes longer than /24 (IPv4) or /48 (IPv6) are generally neither announced nor accepted (RFC 7454 §6.1.3), so announce a covering /24 or /48, not a host route.

Code

Toy BGP decision model: each client has a LOCAL_PREF and AS-path length per site; compute catchments, then test prepending and withdrawal.

use std::time::Instant;

/// One site's announcement of the shared prefix.
#[derive(Clone)]
struct Site {
    router_id: u32, // final tie-break (RFC 4271 9.1.2.2 f: lowest BGP Identifier)
    prepend: u32,   // extra copies of our own AS in the announced AS_PATH
    up: bool,       // false = route withdrawn (health check failed)
}

/// What a client network would learn from one site if it were announced.
#[derive(Clone, Copy)]
struct Path {
    local_pref: u32, // set by the client's own policy (customer > peer > transit)
    as_path_len: u32,
}

struct World {
    sites: Vec<Site>,
    paths: Vec<Path>, // flat: client c, site s at c * sites.len() + s
}

impl World {
    /// Best site for one client, as the BGP decision process orders routes:
    /// highest LOCAL_PREF, then shortest AS_PATH (incl. prepends), then lowest router id.
    fn best(&self, client: usize) -> Option<usize> {
        let n = self.sites.len();
        (0..n)
            .filter(|&s| self.sites[s].up)
            .min_by_key(|&s| {
                let p = self.paths[client * n + s];
                (std::cmp::Reverse(p.local_pref), p.as_path_len + self.sites[s].prepend, self.sites[s].router_id)
            })
    }

    /// Catchment map: client -> serving site (None if every site withdrew).
    fn catchments(&self) -> Vec<Option<usize>> {
        (0..self.paths.len() / self.sites.len()).map(|c| self.best(c)).collect()
    }
}

fn load(c: &[Option<usize>], site: usize) -> usize {
    c.iter().filter(|&&x| x == Some(site)).count()
}

fn xorshift(s: &mut u64) -> u64 {
    *s ^= *s << 13; *s ^= *s >> 7; *s ^= *s << 17; *s
}

fn world(clients: usize, sites: usize) -> World {
    let mut rng = 0x9e37_79b9_7f4a_7c15u64;
    let paths = (0..clients * sites)
        .map(|_| Path { local_pref: 100 + 100 * (xorshift(&mut rng) % 2) as u32, as_path_len: 2 + (xorshift(&mut rng) % 5) as u32 })
        .collect();
    World { sites: (0..sites as u32).map(|i| Site { router_id: i + 1, prepend: 0, up: true }).collect(), paths }
}

fn main() {
    // Ties: identical paths everywhere -> lowest router id wins, whatever the site order.
    let w = World { sites: vec![Site { router_id: 9, prepend: 0, up: true }, Site { router_id: 3, prepend: 0, up: true }],
                        paths: vec![Path { local_pref: 100, as_path_len: 3 }; 2] };
    assert_eq!(w.best(0), Some(1));

    let mut w = world(10_000, 5);
    let base = w.catchments();
    for (c, s) in base.iter().enumerate() { // each client reaches a site no other site beats
        let s = s.unwrap();
        let key = |t: usize| (std::cmp::Reverse(w.paths[c * 5 + t].local_pref), w.paths[c * 5 + t].as_path_len, w.sites[t].router_id);
        assert!((0..5).all(|t| key(s) <= key(t)));
    }
    // Prepending 3x at site 0 can only move clients away from it.
    w.sites[0].prepend = 3;
    let pre = w.catchments();
    assert!(load(&pre, 0) < load(&base, 0));
    assert!(base.iter().zip(&pre).all(|(a, b)| a == b || *a == Some(0)));
    w.sites[0].prepend = 0;
    // Withdrawal of site 2: only its clients move; nobody else changes.
    w.sites[2].up = false;
    let after = w.catchments();
    for (a, b) in base.iter().zip(&after) {
        assert!(a == b || *a == Some(2));
        assert_ne!(*b, Some(2));
    }
    println!("loads before {:?}", (0..5).map(|s| load(&base, s)).collect::<Vec<_>>());
    println!("loads after  {:?}", (0..5).map(|s| load(&after, s)).collect::<Vec<_>>());

    // Timing: recompute all catchments, 100k clients x 20 sites (release build).
    let mut big = world(100_000, 20);
    big.sites[7].up = false;
    let t = Instant::now();
    let c = big.catchments();
    println!("recompute 100k x 20: {:?} ({} assigned)", t.elapsed(), c.iter().flatten().count());
}

Complexity and constants

• Data plane: nothing extra; site selection is already in the RIB.
• Control plane: one route change per withdrawal, propagated hop by hop; until it finishes, some clients still hit the old site.
• Model above: recompute of 100,000 clients x 20 sites took 11-14 ms (about 6 ns per client-site pair), measured on Apple M4 Pro, single thread, release build, 5 runs. Real routers do not recompute globally; this is an offline what-if.

Efficiency

• Cost: per packet, zero extra work and zero extra bytes (no redirect, no proxy hop). Per failover: one BGP withdrawal; packets to the dead site are lost until it propagates. Bound: BGP convergence and path quality, not compute.
• Levers:
  • AS-path prepending — shifted B-Root load from MIA to LAX, up to 3 prepends, a small share stayed (Verfploeter, IMC 2017) — to drain a site gently.
  • Predict before you change — map catchments from about 3.8M vantage points, 430x RIPE Atlas's 9k (Verfploeter) — before any prepend or new site.
  • Geographic hint in BGP — removes much path inflation in simulation (Li et al., SIGCOMM 2018; a proposal) — shows what extra route information could do.
  • Restricted propagation (NO_EXPORT, NOPEER, peering-only announcements) — a local node serves only nearby networks (RFC 4786 §4.4.6) — to confine a site to a region.
• Naive → standard → state of the art:
  • One site, one unicast IP · every client pays the distance; one failure is an outage.
  • GeoDNS or DNS round robin · location is the resolver's, failover waits for TTLs.
  • Anycast with health-gated withdrawal · routing-time selection, failover at BGP speed.
  • Anycast plus measured catchments and traffic engineering · map, then change.

Implementation notes

• Announce from the host: BIRD, FRRouting, GoBGP or ExaBGP run beside the service and announce the service /32 or /24 only while the health check passes.
• BFD detects a dead link to the router fast; add a minimum hold-down before re-announcing.
• Long UDP sessions (voice, QUIC): after the first packet, move the client to a site-unique address so later route changes cannot split the session.
• Give each site a unicast address as well; from one vantage point the anycast address shows only one site.

Pitfalls

• Withdrawing under a sustained DDoS attack just moves the attack to the next site and can cascade (RFC 7094 §4.4). Contain the attack at one instance instead.
• Per-packet ECMP across neighbours that picked different sites splits one transaction over two sites (RFC 4786 §4.4.3). Use per-flow hashing.
• Flapping health checks flap the route; rapid announce/withdraw can cause route dampening upstream (RFC 4786 §4.4.4).
• Catchments shift when peering changes anywhere upstream: re-measure after any neighbour, provider or site change.

Variants and alternatives

In production

Root DNS servers, public open resolvers (Li et al.), time.cloudflare.com (anycast network of 335 locations per its time page), Google Maglev VIPs (each machine announces over BGP, router ECMP, controller withdraws when unhealthy), CDN and scrubbing edges.

Implementations

Sources

• Abley, Lindqvist, Operation of Anycast Services, RFC 4786 (BCP 126), 2006. RFC
• McPherson, Oran, Thaler, Osterweil, Architectural Considerations of IP Anycast, RFC 7094, 2014. RFC
• Partridge, Mendez, Milliken, Host Anycasting Service, RFC 1546, 1993. RFC
• Rekhter, Li, Hares, A Border Gateway Protocol 4 (BGP-4), RFC 4271, 2006. RFC
• Durand, Pepelnjak, Doering, BGP Operations and Security, RFC 7454, 2015. RFC
• de Vries et al., Broad and Load-Aware Anycast Mapping with Verfploeter, ACM IMC 2017. paper
• Li, Levin, Spring, Bhattacharjee, Internet Anycast: Performance, Problems, & Potential, ACM SIGCOMM 2018. paper
• Wei, Heidemann, Does Anycast Hang Up on You (UDP and TCP)?, IEEE TNSM 2018. paper
• Eisenbud et al., Maglev: A Fast and Reliable Software Network Load Balancer, USENIX NSDI 2016. paper
• Root Server Technical Operations Association, root-servers.org. site