This chapter was the other half of the network layer: not what a router does to a packet, but how every router came to know what to do.
What this page is
-
The chapter in one picture — every idea, linked to the section that taught it.
-
The argument in five steps, which is how the chapter hangs together.
-
Every number worth remembering, sortable.
-
The book’s slips in this chapter, collected, several of them proved by tooling.
-
A closing quiz on the chapter as a whole.
Where you are
Chapter 4 ended with every router consuming a forwarding table and never saying where the table came from. This chapter is where it comes from.
The book calls the control plane control plane Simple How the routers work out where everything should go. Precise The network-wide logic that controls how a datagram is routed among routers along an end-to-end path from source host to destination host. introduced in ch. 4 — open in glossary the network-wide logic that controls how a datagram is forwarded along an end-to-end path. It also controls how network-layer components and services are configured and managed. Both halves of that definition got their own sections.
The journey down the stack now has one step left. Chapter 6 is the link layer, whose job is much more local: moving packets between nodes on the same link or LAN (Local Area Network) Local Area Network A network covering one building, campus or home. introduced in ch. 1 .
The chapter in one picture
Hover an idea to see what it connects to. Click one to go back to the section that taught it.
Hover a node to dim everything it does not touch. Click one to go back to the section that taught it. The two dashed links across the middle are the chapter’s two best jokes: BGP is a distance-vector algorithm that learned from count-to-infinity, and SDN runs the same Dijkstra as OSPF, somewhere else.
Read this map as a list
- control plane (5.1) — connects to per-router control, logically centralized
- per-router control (5.1) — connects to control plane, link-state (LS), distance-vector (DV)
- control agent (5.1) — connects to logically centralized
- logically centralized (5.1) — connects to control plane, control agent, SDN controller
- G = (N, E) (5.2) — connects to least-cost path
- least-cost path (5.2) — connects to G = (N, E), link-state (LS), distance-vector (DV)
- link-state (LS) (5.2.1) — connects to per-router control, least-cost path, Dijkstra · O(n²), route oscillation, OSPF · protocol 89
- distance-vector (DV) (5.2.2) — connects to per-router control, least-cost path, Bellman-Ford, count-to-infinity, BGP · port 179
- Dijkstra · O(n²) (5.2.1) — connects to link-state (LS), OSPF · protocol 89, network-control app
- Bellman-Ford (5.2.2) — connects to distance-vector (DV)
- route oscillation (5.2.1) — connects to link-state (LS)
- count-to-infinity (5.2.2 · 44) — connects to distance-vector (DV), poisoned reverse, AS-PATH
- poisoned reverse (5.2.2) — connects to count-to-infinity
- autonomous system (5.3) — connects to ASN, intra-AS routing, BGP · port 179
- ASN (5.3) — connects to autonomous system
- intra-AS routing (5.3) — connects to autonomous system, OSPF · protocol 89
- OSPF · protocol 89 (5.3) — connects to link-state (LS), intra-AS routing, areas + backbone, traffic engineering, Dijkstra · O(n²)
- areas + backbone (5.3) — connects to OSPF · protocol 89
- traffic engineering (5.3) — connects to OSPF · protocol 89
- BGP · port 179 (5.4) — connects to autonomous system, gateway router, BGP route, IP-anycast, distance-vector (DV)
- gateway router (5.4.2) — connects to BGP · port 179, eBGP / iBGP
- eBGP / iBGP (5.4.2) — connects to gateway router
- BGP route (5.4.3) — connects to BGP · port 179, AS-PATH, NEXT-HOP
- AS-PATH (5.4.3) — connects to BGP route, count-to-infinity
- NEXT-HOP (5.4.3) — connects to BGP route, hot potato
- hot potato (5.4.3 · rule 3) — connects to NEXT-HOP, local preference
- local preference (5.4.3 · rule 1) — connects to hot potato, routing policy
- routing policy (5.4.5) — connects to local preference, selective advertisement
- IP-anycast (5.4.4) — connects to BGP · port 179
- transit traffic (5.4.5) — connects to selective advertisement
- selective advertisement (5.4.5) — connects to routing policy, transit traffic
- SDN controller (5.5.1) — connects to logically centralized, northbound API, southbound API, OpenDaylight · ONOS
- network-control app (5.5.1) — connects to northbound API, Dijkstra · O(n²)
- northbound API (5.5.1) — connects to SDN controller, network-control app
- southbound API (5.5.1) — connects to SDN controller, OpenFlow · 6653
- OpenFlow · 6653 (5.5.2) — connects to southbound API, flow table
- flow table (5.5.2) — connects to OpenFlow · 6653
- OpenDaylight · ONOS (5.5.4) — connects to SDN controller, NETCONF · YANG
- ICMP · protocol 1 (5.6) — connects to ping · 8/0 → 0/0, traceroute · 11/0
- ping · 8/0 → 0/0 (5.6) — connects to ICMP · protocol 1
- traceroute · 11/0 (5.6) — connects to ICMP · protocol 1, port unreachable 3/3
- port unreachable 3/3 (5.6) — connects to traceroute · 11/0
- network management (5.7.1) — connects to SNMP · 7 PDUs, NETCONF · YANG
- SNMP · 7 PDUs (5.7.2) — connects to network management, MIB · SMI, trap
- MIB · SMI (5.7.2) — connects to SNMP · 7 PDUs
- trap (5.7.2) — connects to SNMP · 7 PDUs
- NETCONF · YANG (5.7.3) — connects to network management, OpenDaylight · ONOS
The argument, in five steps
1 — There are two ways to build a control plane
Section 5.1 drew both before any mechanism. Per-router control runs a routing algorithm in every router, and the routers talk to one another. Logically centralized control puts a remote controller in charge, and each router keeps only a control agent that obeys.
The data plane underneath is identical either way — the two figures share one base drawing on that page, deliberately.
| Per-router control5.2, 5.3, 5.4 | Logically centralized control5.5 | |
|---|---|---|
| Where the algorithm runs | ||
| Who talks to whom | ||
| Where the network’s state lives | ||
| To change the behaviour, you change | ||
| The chapter’s examples | ||
| How it goes wrong |
Cells marked ⓘ have a reason behind them — click to read it.
Section 5.1 named these two designs and then spent six sections on them. Every row is a place where the chapter made the same choice twice.
2 — Routing is a graph problem, and there are two algorithms
Turn the network into a graph G = (N, E) and “a good path” becomes “the
least-cost path”. Then choose what each node is allowed to know.
Link-state link-state algorithm Simple Every node knows the whole map and works the answer out itself. Precise A routing algorithm in which the network topology and all link costs are known to every node, typically by link-state broadcast. Each node then computes least-cost paths locally with Dijkstra’s algorithm. introduced in ch. 5 — open in glossary gives every node the whole map, and each runs Dijkstra locally. Little information sent to everybody.
Distance-vector distance-vector algorithm Simple Nobody knows the map; neighbours tell each other how far things are. Precise An iterative, asynchronous and distributed routing algorithm. Each node receives distance vectors from its directly attached neighbours, applies the Bellman-Ford equation, and distributes the result back. introduced in ch. 5 — open in glossary gives no node a map. Each knows its neighbours’ vectors and iterates Bellman-Ford. A lot of information sent to a few.
Each has its own failure. Link-state costs that follow traffic make routes oscillate. Distance-vector estimates can climb together in the count-to-infinity problem, which poisoned reverse partly fixes and does not solve.
3 — The real Internet cannot be one graph
Two reasons, and they are different in kind. Scale: hundreds of millions of routers is beyond what any router can store or converge over. Administrative autonomy: an ISP (Internet Service Provider) Internet Service Provider Connects hosts, and other ISPs, to the rest of the Internet. introduced in ch. 1 wants to run its own algorithm and hide its own topology.
So the Internet divides into autonomous systems. Inside one, OSPF (Open Shortest Path First) Open Shortest Path First The Internet’s intra-AS link-state routing protocol. Each router builds a complete map of its autonomous system and runs Dijkstra locally. introduced in ch. 5 — link-state, flooded to every router in the system, with its own hierarchy of areas. Between them, BGP bgp Simple The protocol that tells every network how to reach every other network. Precise Border Gateway Protocol: the Internet's inter-autonomous system routing protocol, defined in RFC 4271. Every AS runs it. It advertises prefix reachability between autonomous systems and is decentralized and asynchronous, in the manner of distance-vector routing. introduced in ch. 5 — open in glossary — distance-vector at heart, but advertising prefixes with attributes rather than costs.
And with BGP the chapter changes subject. Cost stops deciding, and policy starts: a route’s local preference is a number an operator sets by hand, and it is consulted before any measure of distance.
4 — Or the algorithm can leave the routers entirely
Section 5.5 takes the other branch from step 1. The switches keep only flow tables; a remote controller holds the network’s state, and applications above it decide what the network should do.
Section 5.5.3 then runs one link failure through the whole stack in six steps — and the algorithm at step 4 is Dijkstra, unchanged from section 5.2.1. Only its location changed.
What that buys is in the last row of the matrix above: to change how this network routes, you change one program.
5 — And somebody has to run all of it
The last two sections are about the network reporting on itself and being managed.
ICMP (Internet Control Message Protocol) Internet Control Message Protocol Carries error and diagnostic messages between hosts and routers. A ping is an ICMP message. Covered in §5.6.
introduced in ch. 2 is how the network layer reports errors, and it is what ping
and traceroute are built from. traceroute in particular never asks any router
anything: it sends datagrams designed to fail, one hop further each time, and
lets each failure identify its own router.
Network management is a managing server, agents inside devices, and a protocol between. SNMP (Simple Network Management Protocol) Simple Network Management Protocol The Internet’s network-management protocol, typically run over UDP so that it still works when the network is under stress (§3.3, built in §5.7). introduced in ch. 3 reads counters and receives alarms. NETCONF (Network Configuration Protocol) Network Configuration Protocol A protocol for communicating configuration and query data between a managing server and managed network devices. The modern alternative to polling with SNMP. introduced in ch. 5 and YANG (Yet Another Next Generation) Yet Another Next Generation The data modelling language used to describe configuration and operational data, from which NETCONF messages are generated. introduced in ch. 5 exist because in 2002 a workshop wrote down what SNMP could not do: configuration, and management at scale.
Every number worth remembering
| Number | What it is | |
|---|---|---|
Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.
Sort by section. The highlighted rows are the ones that explain a design rather than describe one.
What this chapter changed about earlier chapters
Chapter 3’s distance-vector blind spot got a name. In section 3.4 a receiver could not tell a retransmission from a new packet without a sequence number. Here the same shape of problem is larger. A distance vector carries a cost and no record of where it has been. That is why two nodes can raise each other’s estimate forever. BGP’s AS-PATH is the missing record, and it is why BGP does not have the problem.
Chapter 4’s flow tables got an author. Section 4.4 built generalised forwarding, match plus action, and the OpenFlow abstraction, and never said who fills the tables in. Section 5.5 is the answer.
Chapter 2’s content networks got a mechanism. Section 2.6 said a CDN (Content Distribution Network) Content Distribution Network Geographically distributed servers holding copies of content close to users. introduced in ch. 2 directs each user to a good server. Section 5.4.4 shows one way — IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 -anycast, which is nothing but ordinary BGP advertisements of one address from many places.
Chapter 1’s ISP hierarchy became a rule. Section 1.3.3 drew customers, providers and peering. Section 5.4.5 turns those relationships into behaviour. An access ISP tells its providers it has a path to nothing but itself. A backbone declines to advertise a route that would make it carry someone else’s transit for free.
The book’s slips in this chapter, collected
Each is recorded on the page where it appears. None changes an argument, and several are only visible to a reader who checks the arithmetic — which is the reader this site is for.
- §5.2.1, the oscillation example. Describing Figure 5.5(a)→(b), the text says y’s counterclockwise path to w costs 1 + e. The figure’s own labels give
c(y,x) = eandc(x,w) = 1 + e, so it costs 1 + 2e. Every other number in all four panels is exact. The conclusion is untouched: e is positive, so 1 is smaller either way. - §5.2.1, Figure 5.5. Panels (b) and (d) are the same state, despite different captions. The loads and costs are identical, because z never moved. The oscillation cycles between two states, not four.
- §5.2.2, page 394. “the particular looping problem we encountered before in Figure 5.5(b)” — it is Figure 5.7(b). Figure 5.5 is the oscillation figure, a different problem with a different cause.
- §5.4.2, page 403. The AS-PATH of the route that bypasses AS2 is printed “A3”. It is “AS3”.
- §5.4.3, page 404. “the least cost from router 1b to router 2d is 3” — the two NEXT-HOP routers under discussion are 2a and 3d.
tools/check-bgp-ch05.mjsshows why the slip survived: the distance to 2d also happens to be 3, and 2d is an internal router of AS2 that begins no route. - §5.5.3, pages 418 and 419. The introduction says flow rules at s1, s3 and s4 are affected and s2 is unchanged. Step 6 says entries are updated at s1, s2 and s4. The introduction fits the picture: after s1–s2 fails, s1’s only remaining neighbour is s3.
Check yourself
Check yourself — the whole chapter
0 of 7 answered1.A router's data plane is handed a forwarding table. Can it tell whether a per-router control plane or a remote SDN controller produced it?
2.What information does a distance vector carry that lets two routers count to infinity — and what does BGP add to stop it?
3.The book gives two reasons the Internet cannot be routed as one flat graph. Suppose routers had unlimited memory and processing power. Would one reason survive?
4.predictHot potato routing alone would send router 1b's traffic through AS2. The full BGP algorithm sends it the other way. Why?
5.In the SDN example of section 5.5.3, a link fails and Dijkstra's algorithm computes new paths. What is different from OSPF doing the same job?
6.An ICMP error message quotes the header and first 8 bytes of the datagram that caused it. Why 8?
7.Section 5.7 covers both SNMP and NETCONF. What single finding explains why the second exists?
The chapter in three lines
- Two control planes, one data plane. Per-router control runs a routing algorithm in every router; logically centralized control writes the tables from outside. The data plane cannot tell which one built its tables.
- Link-state sends a little to everyone and runs Dijkstra; distance-vector sends a lot to a few and iterates Bellman-Ford. Inside an autonomous system that becomes OSPF; between them it becomes BGP, where policy is consulted before distance.
- ICMP is the network layer reporting on itself, and
tracerouteis a clever misuse of one header field. Management is the same shape one level up: a managing server, agents, and a protocol — SNMP to watch, NETCONF and YANG to configure.