The idea: two routing protocols in one network

An ISP runs two kinds of routing at once. Inside its own network, an IGP such as OSPF finds the cheapest path between its routers. At its edges, BGP swaps routes with other networks and picks among them by policy: who pays whom. The page shows one ISP, AS64500, with four routers in two OSPF areas and four neighbours: a provider (AS64501), two peers (AS64502, AS64503) and a customer (AS64510).

AS64500 with routers R1, R2 and R3 in OSPF area 0 and R3 and R4 in area 1. R1 connects to provider AS64501 and peer AS64502, R2 to peer AS64502 and peer AS64503, R4 to customer AS64510. Dashed lines show the iBGP full mesh between the four routers.
OSPF works out costs inside the network; eBGP talks to neighbours; iBGP carries their routes across.

On the canvas the neighbours sit on top, each with the routes it has received from us. Below is AS64500: area 0 with R1 and R2, the area border router R3, and area 1 with R4 and a host. The tables show each router's best BGP route, the OSPF costs, the export rules, and the decision process at one router. Coloured boxes are routes from a customer (green), a peer (blue) or a provider (orange).

How a link-state protocol floods and runs Dijkstra is on Distance Vector vs Link State; how AS_PATH spreads across the internet, and hijacks, are on Anycast and BGP. This page is about what happens inside one AS and the policy at its edges.

OSPF areas and the area border router

A big OSPF network is split into areas. Every router describes its links in a router LSA, and that LSA is flooded only inside its own area. Area 0, the backbone, connects all other areas. A router in two areas is an area border router (ABR); it keeps one link-state database per area and passes summary LSAs between them: "I can reach 10.1.0.0/16 at cost 1" or "R1 is at cost 10 from me".

So R4 never sees the links of area 0. It only knows R1 is 10 away from R3 and R3 is 1 away from itself: cost 11. Areas keep the databases small and keep a flapping link in one area from making every router recompute (Demo 1: area 0 holds 3 router LSAs + 1 summary, area 1 holds 2 router LSAs + 2 summaries; R4 → R1 costs 11, R4 → R2 costs 5).

eBGP and iBGP

eBGP runs between routers of different ASes. A router puts its own AS number in front of the AS_PATH before sending, and sets LOCAL_PREF on what it receives. iBGP runs between routers of the same AS. It carries the route across unchanged: same AS_PATH, same LOCAL_PREF. With next-hop-self, the NEXT_HOP is the border router's own address, which OSPF knows how to reach.

One rule shapes iBGP: a route learned over iBGP is never passed to another iBGP peer. There is no AS_PATH change inside one AS to catch a loop, so this rule prevents it. As a result every border router must talk to every other router directly: a full mesh, 4 routers × 3 / 2 = 6 sessions here. Big networks use route reflectors instead.

In Demo 2 customer AS64510 announces 192.0.2.0/24 to R4: 1 eBGP UPDATE in, 3 iBGP UPDATEs across, then R1 and R2 send 4 eBGP UPDATEs out with AS_PATH 64500 64510. It takes 3 rounds.

The decision process

When a router has several routes to one prefix, it walks down a fixed list and stops at the first step that tells them apart:

StepPreferSet by
1highest LOCAL_PREFour own policy (here by relationship: customer 200, peer 150, provider 100)
2shortest AS_PATHhow far the route has travelled
3lowest ORIGIN (IGP < EGP < incomplete)the origin AS
4lowest MEDthe neighbour, compared only between routes from the same AS
5eBGP over iBGPwhere the route was learned
6lowest IGP cost to the NEXT_HOPOSPF
7lowest router IDa last tie-break

LOCAL_PREF comes first, so policy beats distance. In Demo 3 R1 hears 198.51.100.0/24 from its provider with a 2-AS path (64501 64511) and from the customer, through R4, with a 3-AS path (64510 64512 64511). R1 uses the customer route: 200 beats 100 at step 1. It then withdraws the provider route it had told its iBGP peers about (3 WITHDRAWs). Every router on the page uses ORIGIN IGP and MED 0, so steps 3 and 4 always tie.

Hot potato routing

Peer AS64502 meets us at two places: R1 in the west and R2 in the east. It announces 203.0.113.0/24 at both, with the same LOCAL_PREF (150) and the same AS_PATH (64502). At R4 both routes are iBGP, so the tie goes down to step 6: the IGP cost to the exit. R2 is 5 away, R1 is 11, so R4 sends the traffic to R2 (Demo 4). This is hot potato routing: get rid of traffic for another network at the nearest exit, because carrying it across your own network costs you. R1 and R2 themselves use their own eBGP route (step 5).

Two panels. Left: R3–R2 cost 4, so R4 reaches exit R2 at cost 5 and exit R1 at cost 11 and uses R2. Right: R3–R2 cost 12, so R2 costs 13 and R4 switches to R1 at cost 11.
Same BGP routes, different OSPF cost: the exit moves without a single BGP message.

The other side of hot potato: an OSPF change can move BGP traffic. In Demo 6 the operator raises the R3–R2 cost from 4 to 12. Now R2 is 13 away and R1 still 11, so R4 and R3 switch to R1. No BGP message is sent at all. When the R2–AS64502 link fails (Demo 7), R2 sends 3 iBGP WITHDRAWs and every router falls back to R1.

Who gets which routes: the export rules

Networks have business relationships. A customer pays its provider to carry its traffic to and from everyone. Two peers swap traffic between their own customers for free. These rules, written up by Gao and Rexford, follow from that:

Route learned fromTell customers?Tell peers?Tell providers?
a customeryesyesyes
a peeryesnono
a provideryesnono

Why is a peer route not passed to another peer? If AS64500 told AS64503 about 203.0.113.0/24 from AS64502, traffic from AS64503 to AS64502 would flow through AS64500. Neither of them pays AS64500, so it would be carrying their traffic for free. The same goes for telling a provider: we would end up paying it to carry traffic that is not ours. In Demo 5 the customer route 192.0.2.0/24 goes out on all 4 eBGP sessions, while the peer route 203.0.113.0/24 goes only to the customer (1 UPDATE); R1 and R2 keep it from AS64501 and AS64503.

AS64500 in the middle with its provider above, two peers on the sides and a customer below. A route from the customer goes to the provider and both peers (green ticks). A route from peer AS64502 goes down to the customer (tick) but not to the other peer or the provider (red crosses).
Customer routes go everywhere; peer and provider routes go only down to customers.

Together with "prefer customer over peer over provider", these rules keep paths valley-free: a path goes up through providers, crosses at most one peering link, then goes down to customers. Networks that follow them always reach a stable set of routes. A route leak is what happens when someone breaks them.

See also How a Router Forwards a Packet for what each router does with the route it picked, and Dijkstra's algorithm for the SPF step inside OSPF.

See also VLSM Address Planning for how one block is carved into subnets of different sizes and summarised into one prefix.

What the page leaves out

  • OSPF details: Hello packets, DR/BDR on shared links, LSA ages and sequence numbers, stub and NSSA areas, and type 5 external LSAs.
  • Route reflectors and confederations, which replace the iBGP full mesh in large networks.
  • MED, ORIGIN, communities and AS_PATH prepending as tools; real ISPs tag a route's relationship with a community, which the page does with a hidden tag.
  • Timers: real BGP batches UPDATEs (MRAI) and waits for the hold timer (90 s by default) unless BFD is used.
  • ECMP (sharing traffic over equal exits) and cold-potato routing with MED.

On the mind map

Open the Networking mind mapNetworkingLayers & links: frames on one local networkLayers & linksIP & routing: packets hop between networksIP & routingCore services: address, name and timeCore servicesTCP, UDP & sockets: end to end between two portsTCP, UDP & socketsHTTP & TLS: what a browser does per requestHTTP & TLSAPIs & push: how apps talk to serversAPIs & pushProxies & edge: boxes in the middle of the pathProxies & edgeContainers: virtual networks from Linux partsContainersReal-time media: voice and video over UDPReal-time mediaSecurity at the edge: filter traffic at the borderSecurity at the edgeRouter forwardingRouter forwardinglongest prefix match picks the next hopVRRP / HSRP failoverVRRP / HSRP failoverBackup takes over the gateway in 3.6 sSDN and OpenFlowSDN and OpenFlowcontroller writes rules, switch looks upTracerouteTracerouteTTL 1, 2, 3: each hop sends Time ExceededNATNATmaps private IP:port to one public IPIPv4 vs IPv6IPv4 vs IPv632 vs 128 bits; SLAAC, no NAT neededAnycast and BGPAnycast and BGPsame prefix announced from many sitesOSPF and BGP policyPolicy first, then path, then IGP costDistance vector vs link stateDistance vector vs link stateRIP shares distances; OSPF floods the mapSubnets and CIDRSubnets and CIDR/24 = mask: same subnet? ARP, else routerVLSM PlanningVLSM PlanningLargest first: no gaps, one summary routeRouter queues and AQMRouter queues and AQMFull buffers add delay; drop earlyDelay, loss, throughputDelay, loss, throughputSlowest link sets pace; full buffer dropsOpen the Networking mind mapNetworkingpackets hop between networksIP & routingRouter forwardingRouter forwardinglongest prefix match picks the next hopVRRP / HSRP failoverVRRP / HSRP failoverBackup takes over the gateway in 3.6 sSDN and OpenFlowSDN and OpenFlowcontroller writes rules, switch looks upTracerouteTracerouteTTL 1, 2, 3: each hop sends Time ExceededNATNATmaps private IP:port to one public IPIPv4 vs IPv6IPv4 vs IPv632 vs 128 bits; SLAAC, no NAT neededAnycast and BGPAnycast and BGPsame prefix announced from many sitesOSPF and BGP policyPolicy first, then path, then IGP costDistance vector vs link stateDistance vector vs link stateRIP shares distances; OSPF floods the mapSubnets and CIDRSubnets and CIDR/24 = mask: same subnet? ARP, else routerVLSM PlanningVLSM PlanningLargest first: no gaps, one summary routeRouter queues and AQMRouter queues and AQMFull buffers add delay; drop earlyDelay, loss, throughputDelay, loss, throughputSlowest link sets pace; full buffer drops
This page on the Networking mind map · 62 pages in 10 branches · open it to see the whole map and test yourself in recall mode.