Routing protocols
A router forwards packets using its forwarding table. Routing protocols are the control plane that builds that table. They run in software, react to topology changes in milliseconds to seconds, and hand the result to the hardware. See Forwarding and routing for the split between the two planes.
The internet is divided into autonomous systems (AS). An AS is a set of routers under one administrative control, identified by an AS number (ASN). Two families of protocols cover the two scopes:
| Inside an AS (IGP) | Between ASes (EGP) | |
|---|---|---|
| Examples | OSPF, IS-IS, RIP, EIGRP | BGP |
| Main goal | Best performance and resource use | Enforce business policy |
| Control | One administrator | Many independent operators |
| Metric | Link costs set by the administrator | Policy attributes and AS path length |
| Scale | One network. Split into areas if needed | The whole internet, about a million IPv4 prefixes |
Link state
Section titled “Link state”In a link-state protocol every router learns the whole topology and computes its own paths.
- Each router measures the cost of its directly attached links.
- It floods those costs to every other router in the AS, not just its neighbors.
- Every router now holds the same map of the network.
- Each router runs Dijkstra’s shortest-path algorithm on that map, with itself as the root. The result is a shortest-path tree.
- For each destination, the first hop on the tree goes into the forwarding table.
Dijkstra is cheap at this scale. A basic implementation is quadratic in the number of nodes, and a heap-based one is faster. The real cost is the flooding, which grows with network size.
Because every router computes from the same map, convergence is fast and routes are loop-free once the map is consistent. A faulty router can only advertise wrong costs for its own links, so errors stay local.
Going deeper: Shortest-path algorithms has a hand-worked Dijkstra example, the complexity argument, and the route oscillation problem.
Link costs are set by the administrator and do not follow current load. Load-sensitive costs make traffic oscillate between paths: a link looks cheap, everything moves to it, it looks expensive, everything moves back.
Distance vector
Section titled “Distance vector”In a distance-vector protocol a router knows only its neighbors and what they tell it.
The rule behind it is the Bellman-Ford equation. The cost from x to y is the cheapest of all neighbors v:
D_x(y) = min over v of { c(x,v) + D_v(y) }Each router sends its table (its “vector” of costs to every destination) to its neighbors only. When a neighbor’s vector or a local link changes, the router recomputes and, if anything changed, sends its vector again. Updates stop when nothing changes. The neighbor that gives the minimum becomes the next hop.
Bad news travels slowly
Section titled “Bad news travels slowly”When a link gets cheaper, the news spreads in a few rounds. When a link gets worse or fails, routers can feed each other stale information. Take three routers, with R1 attached to network N.
| Link | Cost |
|---|---|
R1 to R2 | 4 |
R2 to R3 | 1 |
R1 to R3 | 50 |
R2 reaches N directly at cost 4. R3 goes through R2 at cost 5. Now the R1 to R2 link rises to 60.
R2recalculates: direct costs 60, butR3claims to reachNfor 5, soR2picks1 + 5 = 6viaR3.R3’s path actually goes throughR2. The two routers now bounce packets forNbetween them.R2tellsR3its cost is 6, soR3updates to 7.R3tellsR2, which updates to 8, and so on.- The counting continues for roughly 45 rounds, until
R3’s cost passes 50 and it switches to the directR1link.
This is count to infinity. With a link cost of 10,000 it would take thousands of rounds, and packets loop the whole time. The Shortest-path algorithms deep dive shows the arithmetic round by round.
Practical protections:
- Poisoned reverse. If
R3routes toNthroughR2, it tellsR2that its own cost toNis infinity.R2then never triesR3as a way out. This only stops loops between two adjacent routers. A loop of three or more routers still counts to infinity. - A small “infinity”. RIP treats 16 hops as unreachable, so counting ends quickly. The cost is a network diameter limit of 15 hops.
- Triggered updates and hold-down timers shorten the time a bad route lingers.
RIP is the classic example: it counts hops, sends its table every 30 seconds over UDP port 520, and suits only small networks. EIGRP is an advanced distance-vector protocol that avoids loops with its DUAL algorithm. BGP is a distance-vector variant that carries the whole path, which makes loops easy to detect (see below).
Link state vs distance vector
Section titled “Link state vs distance vector”| Link state | Distance vector | |
|---|---|---|
| Tells whom | Every router | Direct neighbors only |
| Tells what | Its own link costs | Its cost to every destination |
| Router knows | Full topology | Only costs and next hops |
| Convergence | Fast, loop-free | Slower, can loop and count to infinity |
| Fault isolation | Good. A bad router misreports its own links | Poor. A wrong vector spreads onward |
| Cost | Flooding load and memory for the map | Light on messages |
| Examples | OSPF, IS-IS | RIP, EIGRP, BGP (path vector) |
OSPF (Open Shortest Path First, version 2 is RFC 2328) is the most common link-state IGP in enterprise and data center networks. “Open” means its specification is public. OSPFv3 extends it to IPv6.
How it operates
Section titled “How it operates”- OSPF runs directly over IP as protocol 89, not over TCP or UDP. It has its own reliable flooding. Hello and update packets use multicast addresses
224.0.0.5(all OSPF routers) and224.0.0.6(designated routers). - Routers send Hello packets to find neighbors and check that links are alive. Two routers that agree on timers, area, and subnet form an adjacency, swap their link-state databases, and reach the
Fullstate. - Routers flood a link-state advertisement (LSA) whenever a link changes, and refresh each one at least every 30 minutes.
- Equal-cost paths are all used, so traffic is split across them (ECMP).
- Link cost defaults to a reference bandwidth divided by the interface speed. Administrators can set any cost, for example to steer traffic away from an expensive link.
On a shared Ethernet segment, OSPF elects a designated router (DR) and a backup (BDR) so that each router forms adjacencies with those two and not with every neighbor. On point-to-point links, such as router-to-router links in a data center, set the network type to point-to-point to skip the election.
A large AS is divided into areas. Each area floods and computes only its own topology, which keeps databases and recalculation small.
| Element | Role |
|---|---|
| Backbone (area 0) | Exactly one. Every other area must connect to it |
| Area border router (ABR) | Sits on the edge of an area. Summarizes that area’s routes to the backbone and the reverse |
| Internal router | All interfaces in one area |
| ASBR | Injects routes from outside OSPF (static routes, BGP) |
Traffic between two areas goes from the source area to its ABR, across the backbone, and through the destination’s ABR. The common LSA types: type 1 (router links, within an area), type 2 (network, from the DR), type 3 (summary routes between areas), and type 5 (external routes).
Authentication
Section titled “Authentication”Any device that speaks OSPF on a segment can inject routes. Use cryptographic authentication (HMAC-based keys) on every interface. OSPF’s old plain-text “simple” password sends the secret in each packet and protects nothing. The older MD5 mode is better than none but weak. Do not run OSPF on interfaces facing users or servers: mark them passive.
Checking OSPF with FRR
Section titled “Checking OSPF with FRR”FRR is the common open-source routing suite on Linux. The commands below use its vtysh shell. Other vendors use almost the same words.
sudo vtysh -c 'show ip ospf neighbor'# Neighbor ID Pri State Up Time Dead Time Address Interface# 10.255.0.2 1 Full/DR 2h14m 33.4s 10.0.12.2 eth1:10.0.12.1
sudo vtysh -c 'show ip route ospf'# O>* 10.0.20.0/24 [110/20] via 10.0.12.2, eth1, weight 1, 02:13:55
sudo vtysh -c 'show ip ospf database'| Symptom | Likely cause | Fix |
|---|---|---|
Neighbor stuck in Init | Hellos go one way only (ACL or multicast filtered) | Allow IP protocol 89 and 224.0.0.5 in both directions |
| Neighbor never forms | Mismatched area ID, hello and dead timers, subnet, or authentication key | Compare the interface config on both sides |
Neighbor stuck in ExStart or Exchange | MTU mismatch between the two interfaces | Match the MTU on both ends |
| Traffic prefers a slow link | Reference bandwidth too low, so costs tie | Raise the reference bandwidth everywhere |
| Route missing between two areas | An area is not connected to area 0 | Connect it, or add a virtual link as a stopgap |
BGP (Border Gateway Protocol) connects autonomous systems. Every ISP, cloud, and large company uses it. Routers do not exchange routes to single addresses. They exchange prefixes in CIDR form, and each prefix says “this block is reachable through this path”.
BGP sessions are ordinary TCP connections on port 179 between two configured peers. A session stays up for a long time and carries only changes, in contrast to OSPF’s flooding.
eBGP and iBGP
Section titled “eBGP and iBGP”| Session | Between | Purpose |
|---|---|---|
| eBGP | Routers in different ASes, usually directly connected | Learn and announce prefixes across the border |
| iBGP | Routers in the same AS | Spread eBGP-learned routes to every router in the AS |
A router does not pass a route it learned from one iBGP peer on to another iBGP peer. To stay consistent, iBGP needs a full mesh of sessions between all routers, or route reflectors that relay routes for a group of clients. iBGP sessions are logical TCP connections and do not follow physical links.
flowchart LR
subgraph AS64496["AS64496 (origin)"]
A["Edge router<br/>owns 198.51.100.0/24"]
end
subgraph AS64497["AS64497 (transit)"]
B1["Edge router 1"] -->|"iBGP"| B2["Edge router 2"]
end
subgraph AS64498["AS64498"]
C["Edge router"]
end
A -->|"eBGP: AS path 64496"| B1
B2 -->|"eBGP: AS path 64497 64496"| C
Each AS adds its own number to the front of the path before it passes a route to the next AS. When the route reaches AS64498, the router knows the prefix exists and the AS path to reach it.
Route attributes
Section titled “Route attributes”A prefix plus its attributes is a route. The attributes carry the information BGP uses to choose.
| Attribute | Meaning | Scope |
|---|---|---|
| AS_PATH | The ASNs the advertisement has passed through. Doubles as a distance metric and loop check | Passed along |
| NEXT_HOP | The IP address of the router to forward to | Per hop. Resolved by the IGP |
| LOCAL_PREF | How much this AS prefers a route. Higher wins | Inside one AS only |
| MED | A hint from a neighboring AS about which entry point it prefers. Lower wins | Between neighboring ASes |
| ORIGIN | How the route entered BGP | Passed along |
| Communities | Tags that tell other routers how to treat a route | Passed along, by agreement |
A router that sees its own ASN in the AS_PATH of an incoming route rejects it. That check is why BGP does not count to infinity.
NEXT_HOP is where BGP and the IGP meet. The next hop is an address outside the AS, so a router inside the AS uses OSPF or IS-IS to find the cheapest internal path to it. Without a working IGP route to the next hop, a BGP route is unusable.
How BGP picks a route
Section titled “How BGP picks a route”When several routes exist for a prefix, the router eliminates candidates in order until one is left. The usual order:
- Highest
LOCAL_PREF(policy) - Shortest
AS_PATH - Lowest
ORIGINtype - Lowest
MED, when the routes come from the same neighboring AS - eBGP over iBGP
- Lowest IGP cost to the
NEXT_HOP(hot potato) - Lowest router ID, as the final tie-break
Vendors add rules. Cisco and FRR check a local weight before everything else.
Hot potato routing is step 6. The router hands the packet to the AS exit that is cheapest to reach through the IGP, and ignores how far the packet then travels. It saves capacity inside your AS. The side effect is that two routers in the same AS can pick different exits for the same prefix, and the forward and return paths often differ. The opposite, cold potato, carries traffic across your own network to the best exit, and a neighbor can request it with MED.
Policy and business relationships
Section titled “Policy and business relationships”Neighboring ASes are customers, providers, or peers. BGP policy mirrors those contracts:
| Relationship | Who pays | Typical LOCAL_PREF | What you announce to them |
|---|---|---|---|
| Customer | They pay you | Highest | All routes you know |
| Peer | Nobody. Settlement-free | Middle | Only your own and your customers’ routes |
| Provider | You pay them | Lowest | Only your own and your customers’ routes |
The rule underneath is “no free rides”. Traffic crossing your network should have a customer at one end. If you announced a route learned from one provider to another provider, you would carry their traffic for nothing. A multi-homed stub network applies the same rule: it announces only its own prefixes to both of its providers, so neither can use it as a shortcut to the other. See ISP tiers, peering, and IXPs for the commercial picture.
Operators steer traffic with a few controls:
- Inbound traffic (how others reach you): prepend your ASN several times in
AS_PATHon one link to make it look longer and less attractive, or use communities that your provider documents. - Outbound traffic (how you reach others): set
LOCAL_PREFhigher on the preferred provider.
Hijacks and leaks
Section titled “Hijacks and leaks”BGP assumes that peers announce only what they own. When that fails, traffic goes to the wrong place. A leak is a route announced to a neighbor that should not have received it. A hijack announces someone else’s prefix, often a longer one that wins by longest-prefix match. Defences:
- Prefix filters on every customer session, built from registry data (for example with
bgpq4). - Maximum-prefix limits that drop a session that suddenly sends far too many routes.
- RPKI route origin validation. The prefix owner signs a Route Origin Authorization (ROA) naming the ASN allowed to originate it and the longest permitted prefix. Routers reject announcements that do not match.
IP anycast
Section titled “IP anycast”Anycast gives the same prefix to several servers in different places. Each site announces the prefix with BGP. Every router on the internet picks the best path by the normal rules, which usually means the nearest site by AS path, so users reach a nearby instance with no special client logic.
The DNS root system works this way: 13 root server addresses are served by well over a thousand instances worldwide, and a query lands on a nearby one. Anycast also protects against DDoS, since attack traffic is split among sites.
Anycast has one weak point for long-lived TCP. If routes change during a session, packets can start arriving at a different site, which has no state for the connection and resets it. For that reason many content networks use anycast for DNS and the first request, and then direct clients to a specific site (see CDNs and video streaming).
Checking BGP with FRR
Section titled “Checking BGP with FRR”sudo vtysh -c 'show bgp summary'# Neighbor V AS MsgRcvd MsgSent Up/Down State/PfxRcd# 203.0.113.2 4 64497 1520 1498 2d03h12m 3
sudo vtysh -c 'show bgp ipv4 unicast 198.51.100.0/24'# Paths: (1 available, best #1)# 64497 64496# 203.0.113.2 from 203.0.113.2 (10.255.1.1)# Origin IGP, localpref 100, valid, external, best| Symptom | Likely cause | Fix |
|---|---|---|
Session stays in Idle or Active | TCP 179 blocked, wrong peer address or ASN, or a key mismatch | Test with nc -vz peer 179, then compare both configs |
| eBGP peer is not directly connected | Default TTL of 1 drops the session packets | Enable eBGP multihop, or use a directly connected address |
| Session up, 0 prefixes received | The neighbor is not announcing, or an inbound filter drops everything | Check the neighbor’s outbound policy and your inbound policy |
| Route present but unusable | No IGP route to the next hop | Fix the IGP, or set next-hop-self on iBGP sessions |
| Traffic uses the more expensive provider | LOCAL_PREF equal or reversed | Raise LOCAL_PREF on the preferred link |
| Traffic arrives from an unexpected network | Leak, hijack, or a neighbor changed its policy | Check a public looking glass, then your prefix filters and ROAs |
BGP in the cloud and in Kubernetes
Section titled “BGP in the cloud and in Kubernetes”BGP is also the tool for private connections to cloud providers and for exposing cluster networks.
- Dedicated cloud links. AWS Direct Connect, Azure ExpressRoute, and Google Cloud Interconnect all run BGP between your router and the provider. You announce your on-premises prefixes and receive the cloud network’s. A private ASN (64512 to 65534) is normal. Prepending and
MEDsteer which link carries traffic when you have two. - Site-to-site VPNs to cloud gateways can use BGP too, so the route tables update when a tunnel fails.
- Kubernetes. Calico and Cilium can peer with the top-of-rack switches to advertise pod and Service ranges, and MetalLB can announce
LoadBalanceraddresses with BGP, so external routers learn where each address lives. See Kubernetes Services.
Making a new service reachable
Section titled “Making a new service reachable”A public service needs three layers to line up: addresses, names, and routes.
- Addresses. Take them from a cloud provider or ISP, or request your own block and ASN from a regional registry.
- Names. Register the domain, set the authoritative name servers, and add the
A,AAAA,MX, and other records. See Networking services. - Routes. If the provider owns the addresses, its aggregate announcement already covers you. If you own the block, you originate it over BGP and publish a ROA so others accept it.
- Verify.
digfor the records,mtrto see the path, and a public looking glass to confirm the prefix is visible from several networks.