Skip to content

CONCEPT Cited by 1 source

Valley-free routing

Valley-free routing is the property — formalised in Gao–Rexford (IEEE/ACM Trans. Networking 2001) — that a well-formed BGP AS path, viewed against the customer-provider and peer-to-peer relationships of the ASes on the path, contains no "valley."

What a valley is

Imagine each AS on the path at a height determined by its relationship to its neighbors:

  • Up-step: customer → provider (moving up to buy transit).
  • Flat step: peer ↔ peer (same level).
  • Down-step: provider → customer (moving down to deliver transit).

A valid path has the shape: zero-or-more up-steps, at most one flat step, zero-or-more down-steps. That is, the path monotonically ascends, optionally crosses one peer boundary, and then monotonically descends. It never goes up → down → up — that is the "valley."

Why the rule emerges from pairwise policy

The rule is not a protocol primitive; it's an emergent property of consistent export policies:

  • Customer→provider: customer advertises only its own + its customers' routes upstream.
  • Peer↔peer: each peer advertises only its own + its customers' routes.
  • Provider→customer: provider advertises everything downstream.

If every AS follows these rules, valleys cannot form. Violations are route leaks and are most cleanly classified against valley-free as the reference invariant.

Hairpin leaks violate it most visibly

The Type 1 hairpin leak Cloudflare analyzes in the Venezuela post — AS52320 (provider) ← AS8048 (customer) ← AS6762 (provider) — is a canonical valley: AS8048 goes up to AS6762 to learn routes, then up again to AS52320 to re-advertise them. The leaked traffic's effective path becomes 52320 → 8048 → 6762 → 21980 with AS8048 forming the valley floor.

Seen in

Last updated · 200 distilled / 1,178 read