Networking for beginners. Part 21: OSPF
All parts of the series “Networking for beginners”In part six a router's routing table was filled in three ways: connected networks appeared by themselves, static routes were written by the administrator, and dynamic ones "came from routing protocols through which routers tell each other about their networks". It's time to look at how exactly they tell each other. Within one organization — an office, a campus, a data center, a provider's network — it is almost always OSPF, Open Shortest Path First, RFC 2328. Between organizations it is BGP, and that is the next part.
Why dynamic routing
Three routers, five networks — static routes are written in ten minutes. Thirty routers, two hundred networks and backup links — no longer: every new network has to be added on every router, and when a cable is cut someone has to switch routes to the detour by hand. A dynamic protocol solves both problems: routers learn about all networks by themselves and rebuild paths by themselves on failures.
There are two families of protocols, and the difference between them is the main thing to understand.
Distance-vector: each router periodically gives its neighbors its whole table — "network X is 3 hops from me" — and the neighbor writes down "X is 4 hops via it". Nobody knows the network map; everyone knows only distances by hearsay. This is how RIP works, a protocol from 1988: the metric is the hop count, no more than 15, tables are sent every 30 seconds, convergence after a failure takes minutes, and loops between neighbors that trust each other are a classic problem. RIP lives on in textbooks and in small networks where it is enough.
Link-state: each router describes only its own links — "I have interfaces in these networks with this cost, and behind them are these neighbors" — and floods that description to all routers in the network. Everyone assembles the same map, and each computes the shortest paths from itself over it. The map is exact, there are no loops by construction, and convergence takes seconds. This is OSPF and its twin IS-IS (the same idea, a different format, running directly over the data link layer without IP; large providers like it).
Protocols within one organization are called IGP (interior gateway protocol), and between organizations EGP. OSPF is an IGP; the boundary of its responsibility is your network.
Where OSPF lives
OSPF runs not over UDP or TCP but directly in IP, as protocol number 89. It ensures reliable delivery itself, with acknowledgments. Packets go to the multicast addresses 224.0.0.5 (all OSPF routers) and 224.0.0.6 (only DR and BDR, more on that below) with TTL 1: nothing leaves the segment, the conversation is always between neighbors on the same cable.
Five packet types, with a common header:
bytes: 1 1 2 4 4 2 2 8
┌───────┬───────┬────────┬────────────┬────────────┬────────┬────────┬──────────┐
│ Ver=2 │ Type │ Length │ Router ID │ Area ID │ Chksum │ AuType │ Auth │
└───────┴───────┴────────┴────────────┴────────────┴────────┴────────┴──────────┘
| Type | Packet | Purpose |
|---|---|---|
| 1 | Hello | find neighbors and maintain adjacency |
| 2 | Database Description (DBD) | a list of the LSA headers I have |
| 3 | Link State Request (LSR) | "send me these LSAs in full" |
| 4 | Link State Update (LSU) | the LSAs themselves, one or more |
| 5 | Link State Ack | acknowledgment of an LSU |
The Router ID is a 32-bit router identifier, written like an IP address but not an address: it is set by hand (10.0.0.1), and if it isn't, the router takes the highest address of a loopback interface. All LSAs are signed with it, and two routers with the same Router ID break the network silently: their LSAs overwrite each other.
Hello: finding neighbors
A router with OSPF enabled on an interface sends a Hello every 10 seconds (30 on slow links) to 224.0.0.5:
$ sudo tcpdump -i eth1 -n -v proto ospf
IP (tos 0xc0, ttl 1, id 0, offset 0, flags [none], proto OSPF (89), length 68)
10.1.12.1 > 224.0.0.5: OSPFv2, Hello, length 48
Router-ID 10.0.0.1, Backbone Area, Authentication Type: none (0)
Options [External]
Hello Timer 10s, Dead Timer 40s, Mask 255.255.255.252, Priority 1
Designated Router 10.1.12.1
Neighbor List:
10.0.0.2
The Hello contains parameters that must match between neighbors: Area ID, Hello and Dead timers, subnet mask (on Ethernet segments), authentication type. If they don't match, there will be no adjacency, and the log will show a message like "Hello timer mismatch". That is the first thing to check when "OSPF won't come up". The Hello also lists the neighbors I have heard Hellos from: seeing itself in someone else's list, a router knows the link is two-way.
The Dead Timer is 40 seconds, four missed Hellos: the neighbor is declared dead, its LSAs are marked unreachable, and paths are recomputed. If the link physically goes down, the interface reports it immediately, without waiting 40 seconds; the wait happens when the link "seems to be up" but the neighbor doesn't answer — behind a switch, for example. For fast detection there is BFD: a separate protocol in which neighbors exchange tiny packets every 50–300 ms and notify OSPF of a failure within a fraction of a second.
Adjacency: from Hello to Full
Two routers that have heard each other go through these states:
Down ──► Init ──► 2-Way ──► ExStart ──► Exchange ──► Loading ──► Full
Hello I see who is DBD LSR/LSU: databases
received myself in master, exchange: request identical
its Hello numbering LSA headers missing ones
- Init — received a Hello from the neighbor. 2-Way — the neighbor has included me in its list: the link works both ways.
- ExStart — agree on who is the master (by Router ID) and which number to start DBD numbering from.
- Exchange — exchange database descriptions: not the LSAs themselves but their headers with version numbers. Each side compares them with its own database.
- Loading — request (LSR) the LSAs that are missing or newer at the neighbor, receive them (LSU), acknowledge (LSAck).
- Full — the databases are identical. From now on, new LSAs are simply forwarded as they appear.
$ vtysh -c 'show ip ospf neighbor'
Neighbor ID Pri State Dead Time Address Interface RXmtL RqstL DBsmL
10.0.0.2 1 Full/- 38.123s 10.1.12.2 eth1:10.1.12.1 0 0 0
10.0.0.3 1 Full/- 35.456s 10.1.13.3 eth2:10.1.13.1 0 0 0
Full is normal. An adjacency stuck in ExStart or Exchange is almost always an MTU mismatch: the MTU is carried in the DBD, and a router with MTU 1500 refuses to talk to a neighbor that announced 9000. Stuck in 2-Way is normal for a DROther on a segment with a DR (see below), and an error in all other cases.
DR and BDR
On an Ethernet segment with five routers, full adjacency between every pair means ten adjacencies and tenfold duplication of LSAs. So on multi-access segments a Designated Router and a backup BDR are elected: all the others (DROther) keep Full only with them and stay in 2-Way with each other. LSAs are sent to the DR at 224.0.0.6, and the DR floods them to everyone at 224.0.0.5. The election goes by the priority from the Hello (0 means don't participate), with ties broken by the highest Router ID, and the DR is not re-elected while it is alive: the first one up stays, even if a router with a higher priority appears later.
On a point-to-point link (two routers on one cable or a /30) no DR is needed, and it is turned off: ip ospf network point-to-point. That is exactly why the example above shows Full/-: on a /30, a DR election is pointless and only slows convergence.
LSA: describing links
An LSA (link-state advertisement) is a record in the shared database. Each one describes one object of the network and lives in the LSDB of every router in the area. The LSA header:
┌──────────┬──────┬──────────────┬────────────────────┬────────────┬──────────┬────────┐
│ LS Age │ Type │ Link State ID│ Advertising Router │ Seq Number │ Checksum │ Length │
│ seconds │ │ the object │ originator (RID) │ version │ │ │
└──────────┴──────┴──────────────┴────────────────────┴────────────┴──────────┴────────┘
The main types:
| Type | Name | Who creates it | What it describes |
|---|---|---|---|
| 1 | Router LSA | every router | all its links in the area: the neighbor or network behind each, the cost |
| 2 | Network LSA | the segment's DR | the segment and the list of routers on it |
| 3 | Summary LSA | ABR | a network from another area: the prefix and the cost to it |
| 4 | ASBR Summary | ABR | how to reach the router that injected external routes |
| 5 | External LSA | ASBR | a route from outside OSPF: static, from BGP, from another process |
| 7 | NSSA External | ASBR in an NSSA | the same, but inside a special area, see below |
The life rules of an LSA: the originator re-issues its LSA every 30 minutes with an incremented Seq Number; on receiving an LSA with a higher number, a router replaces the old one and forwards it on to all neighbors except the one it came from (this is flooding); an LSA nobody has refreshed for 60 minutes (LS Age = 3600) is removed. On a change — a link went down, a network appeared — the originator immediately issues a new version, and within seconds everyone has it.
You can see the whole database:
$ vtysh -c 'show ip ospf database'
OSPF Router with ID (10.0.0.1)
Router Link States (Area 0.0.0.0)
Link ID ADV Router Age Seq# CkSum Link count
10.0.0.1 10.0.0.1 312 0x8000000a 0x1a2b 3
10.0.0.2 10.0.0.2 298 0x80000009 0x3c4d 3
10.0.0.3 10.0.0.3 301 0x8000000b 0x5e6f 3
Three Router LSAs — three routers in the area, each with three links. The databases on all three routers are byte-for-byte identical; if on one router the Seq# of someone's LSA lags behind, flooding is broken, and that is where to start looking.
SPF: computing paths
Every router has the same map; from there each one computes from itself with Dijkstra's algorithm — shortest paths in a weighted graph whose vertices are routers and segments and whose weights are interface costs.
Interface cost = reference bandwidth / interface bandwidth. The default reference is 100 Mbit/s, chosen in the 1990s, and with it every link of 100 Mbit/s and above gets a cost of 1: gigabit and 10 gigabit are indistinguishable. The first thing done in any modern network is auto-cost reference-bandwidth 100000 (100 Gbit/s) identically on all routers: then 10G = 10, 1G = 100, 100M = 1000. The cost of a path is the sum of the costs of the outgoing interfaces along the way, including the last router's interface into the destination network.
The example we will work with:
R2 10.0.0.2
╱ ╲
1G, 100 ╱ ╲ 1G, 100
╱ ╲
R1 10.0.0.1 ────────────── R3 10.0.0.3 ──── 192.168.10.0/24 (1G, 100)
100M, 1000
The shortest path from R1 to 192.168.10.0/24: directly via R3 — 1000 + 100 = 1100; via R2 — 100 + 100 + 100 = 300. The path via R2 wins, even though it has more hops: OSPF counts bandwidth, not hops. In R1's table:
$ vtysh -c 'show ip route ospf'
O>* 192.168.10.0/24 [110/300] via 10.1.12.2, eth1, weight 1, 00:10:12
O>* 10.0.0.2/32 [110/100] via 10.1.12.2, eth1, weight 1, 00:10:12
O>* 10.0.0.3/32 [110/200] via 10.1.12.2, eth1, weight 1, 00:10:12
O 10.1.23.0/30 [110/200] via 10.1.12.2, eth1, weight 1, 00:10:12
[110/300] is administrative distance 110 (the priority of the route source: connected 0, static 1, OSPF 110, iBGP 200; for the same prefix from different sources, the lower one wins) and cost 300. If two paths get the same cost, both go into the table — ECMP, and traffic is spread across them by flow hash.
The R1–R2 link breaks: interface eth1 goes down, R1 immediately issues a new Router LSA without that link, and R2 issues its own; the LSAs spread within a second; all routers run SPF (milliseconds for hundreds of nodes); R1's path to 192.168.10.0/24 becomes 1100 via R3. Nobody configured anything.
Areas
The LSDB of the whole network on every router and SPF over the whole graph scale to a few hundred routers; beyond that the databases and recomputations get heavy, and any flapping line at the edge of the network makes everyone recompute everything. So OSPF divides the network into areas:
R10 ── R11 ── R12 ── ABR-A ── R1 ── R2 ── R3 ── ABR-B ── R20 ── R21
└──────── area 1 ────────┘ └──── area 2 ─────┘
└────── area 0, backbone ──────┘
ABR-A and ABR-B sit in two areas at once; area 1 ↔ area 2 traffic goes through area 0
- Within an area there is a full map and SPF, as described above. Router and Network LSAs (types 1, 2) do not leave the area.
- Area 0, the backbone, is a mandatory area to which all others are connected; traffic between two non-backbone areas goes through it.
- An ABR (area border router) sits in two areas, keeps two LSDBs and passes from one to the other not the map but summaries: Summary LSAs (type 3) — "network
192.168.10.0/24, cost from me to it 300". Between areas OSPF behaves like distance-vector: nobody sees the other area's topology, only distances to prefixes via the ABR. - To spare small areas entirely, they are made stub: the ABR does not pass external routes (type 5) into them, only a default route; totally stubby — it does not pass Summary either, only the default; NSSA is a stub that can itself inject external routes as type 7, and the ABR converts them to type 5 for everyone else.
A network of ten routers does not need areas: a single area 0. The limit of a few hundred routers per area is passed easily today with fast CPUs, and networks are split more often for administrative reasons than technical ones.
External routes
A route that OSPF does not know by itself — a static route to the internet, a route from BGP, from another OSPF process — is injected into OSPF by a router called an ASBR (autonomous system boundary router), using the redistribute command. It issues External LSAs (type 5), and they spread to all areas except stubs. There are two kinds of metric: E2 (the default) — the cost set at injection, which does not grow along the way: "the internet costs 20 from everywhere"; E1 — the internal cost to the ASBR is added to it, and the nearest ASBR wins. The most common external route is 0.0.0.0/0, the default route that the border router announces to the others: default-information originate.
So that other routers know how to reach the ASBR from another area, the ABR issues type 4 — the path to it.
Security and small things
- Authentication. Without it, any host on a segment that runs OSPF becomes a router of the network and gets the whole map, and, if it wishes, the traffic too. OSPFv2 supports MD5 and SHA with a shared key per interface (
ip ospf authentication message-digest); OSPFv3 delegates this to IPsec AH/ESP (part nineteen). - Passive-interface. On interfaces facing hosts (LAN, server segments) OSPF must not look for neighbors: the network needs to be announced, but Hellos need not be sent.
passive-interface defaultplus explicit enabling on links to routers is the standard. - OSPFv3 (RFC 5340) is the version for IPv6: it works over link-local addresses (part thirteen), adjacency is tied to the link rather than the subnet, the Router ID is still 32 bits, address information is moved into separate LSAs (types 8 and 9), and with address families one process can carry both IPv6 and IPv4.
- Stub networks and loopback: a
/32on a loopback interface is the best Router ID and the best address for managing the router; it is reachable as long as at least one link is alive.
Two routers on FRR
FRR is a suite of routing daemons for Linux, with configuration in a Cisco-like syntax. On R1 from the example:
$ sudo vtysh
R1# configure terminal
R1(config)# router ospf
R1(config-router)# ospf router-id 10.0.0.1
R1(config-router)# auto-cost reference-bandwidth 100000
R1(config-router)# passive-interface default
R1(config-router)# no passive-interface eth1
R1(config-router)# no passive-interface eth2
R1(config-router)# network 10.1.12.0/30 area 0
R1(config-router)# network 10.1.13.0/30 area 0
R1(config-router)# network 10.0.0.1/32 area 0
R1(config-router)# exit
R1(config)# interface eth1
R1(config-if)# ip ospf network point-to-point
R1(config-if)# ip ospf authentication message-digest
R1(config-if)# ip ospf message-digest-key 1 md5 s3cret
network … area 0 means "interfaces with addresses from this prefix take part in OSPF in area 0". On R2 and R3 it is symmetric, plus on R3 network 192.168.10.0/24 area 0 for the LAN, which stays passive. After 40 seconds show ip ospf neighbor shows Full, show ip ospf database shows identical databases, and show ip route ospf shows routes with the costs from the SPF section. All that's needed in the kernel is forwarding: net.ipv4.ip_forward = 1.
Troubleshooting in order: are there neighbors? (show ip ospf neighbor; if not, check the Hello parameters, authentication, passive); are the neighbors Full? (if not — MTU, DR); are the databases identical? (show ip ospf database, compare Seq#); is the route in the table? (show ip ospf route shows what SPF computed, show ip route what made it into the kernel; a difference means administrative distance or a filter).
Key takeaways
- Dynamic routing is needed when there are more networks and links than you can manage by hand, and when failures must heal themselves. Link-state (OSPF, IS-IS): everyone knows the map and computes paths themselves; distance-vector (RIP): everyone knows only distances by hearsay.
- OSPF is protocol 89 over IP, multicast
224.0.0.5, five packet types. Hello every 10 s finds neighbors; the Hello parameters must match. Adjacency goes up to Full through exchanging database descriptions and fetching LSAs. - LSAs describe links (1), segments (2), summaries of other areas (3, 4), external routes (5, 7); flooding with version numbers gives everyone an identical LSDB.
- Cost = reference / bandwidth, a path is the sum of outgoing costs, SPF by Dijkstra from yourself; equal paths mean ECMP. Raise the reference bandwidth identically on all routers.
- Area 0 is the backbone, the ABR passes summaries between areas, the ASBR injects external routes; stub areas get only a default.
- Authentication on links, passive on LANs, DR only on multi-access segments, point-to-point on
/30s.
Next — Part 22: BGP: the protocol by which the internet's seventy thousand networks agree on routes. Why it runs over TCP and without automatic neighbor discovery, what an autonomous system is, the OPEN and UPDATE messages, path attributes, how eBGP differs from iBGP and why iBGP needs OSPF, how the best path is chosen and how it is controlled, and how prefix hijacking is defended against today.
Only registered users can leave a comment.
Sign in or register to leave a comment.