A router is four pieces of hardware. The one that decides where a packet goes does it by finding the longest matching prefix in a table, in about five nanoseconds.
Words you will meet
- Input port — where a link arrives. It terminates the line, processes the link layer, and performs the lookup.
- Switching fabric switching fabric Simple The part of a router that carries packets from input to output. Precise The component connecting a router's input ports to its output ports, implemented via memory, via a bus, or via an interconnection network such as a crossbar. introduced in ch. 4 — open in glossary — the hardware carrying packets from input ports to output ports. A network inside a router.
- Output port — where a link leaves. It stores packets from the fabric and transmits them.
- Routing processor — the control-plane processor. It runs the routing protocols, or talks to the remote controller.
- Longest prefix matching longest prefix matching Simple When several rules fit, the most specific one wins. Precise The forwarding rule by which a router, finding several forwarding-table prefixes that match a destination address, uses the entry with the longest matching prefix. introduced in ch. 4 — open in glossary — when several table entries match an address, the most specific one wins.
- Line card — one physical card holding an input port and, usually, the output port for the same link.
- Match plus action — look at a header, decide something, do something. The abstraction this whole chapter generalises.
Why this matters
Section 4.1 said forwarding is a lookup in a table and takes nanoseconds. This section says what the hardware actually is, and the numbers are what make it interesting.
A 100 Gbps input link carrying 64-byte datagrams leaves the input port 5.12 nanoseconds per packet. Put several ports on one line card, as is normal, and the pipeline must run several times faster still. That is far too fast for software. It is why input ports, output ports and the switching fabric are almost always hardware. And it is why the routing processor, running at millisecond timescales, is a conventional CPU (Central Processing Unit) Central Processing Unit The general-purpose processor. In a router it runs the control plane at millisecond timescales, never the per-packet data path. introduced in ch. 4 sitting above the dashed line doing something else entirely.
The second reason to read carefully: the lookup here is a match plus action, and the book says so explicitly. Match on a header field, take an action. Every device in the rest of this book is a variation on it — link-layer switches, firewalls, NAT (Network Address Translation) Network Address Translation Letting a whole private network share one public IP address by rewriting addresses and ports. introduced in ch. 4 boxes — and section 4.4 makes the pattern general.
Four components
Line termination — The physical-layer job: an incoming physical link ends here, and the bits are recovered from the signal on the wire.
All seven stages, as text
- Line termination (input port) — The physical-layer job: an incoming physical link ends here, and the bits are recovered from the signal on the wire.
- Data link processing (input port) — The link-layer job: decapsulate the frame, check it, and hand the datagram inside it upward. This must interoperate with whatever link layer is on the far side of the incoming link, which may differ from the one on the way out.
- Lookup, forwarding, queuing (input port) — The one that matters. The forwarding table is consulted to find which output port this packet leaves by. The table is a shadow copy held at this line card, so no packet has to visit the routing processor. A packet may be queued here if the fabric is busy.
- Switching fabric (switching fabric) — Carries the packet from its input port to its output port. It is entirely inside the router — a network within a network router.
- Queuing (buffer management) (output port) — Packets arriving from the fabric are stored here until the outgoing link is free. If several inputs send to this output at once, they queue — and if the buffer fills, packets are dropped.
- Data link processing (output port) — Encapsulate the datagram in a new frame for the outgoing link. The link header is built fresh at every hop; it is never the one that arrived.
- Line termination (output port) — Put the bits on the outgoing wire.
Seven stages, three of them in the input port. Click any box, or step through. Notice where the dashed line falls: the routing processor is above it, and no packet ever crosses that line.
The four pieces, and which plane each belongs to:
- Input ports. Terminate the incoming physical link, do the link-layer work needed to interoperate with the other end, and — most crucially — perform the lookup that determines the output port. Control packets, such as those carrying routing-protocol information, are sent up to the routing processor instead.
- Switching fabric. Connects input ports to output ports. Completely contained within the router.
- Output ports. Store packets received from the fabric and transmit them on the outgoing link. When a link is bidirectional, its output port is normally paired with its input port on the same line card.
- Routing processor. Control plane. In a traditional router it runs the routing protocols, maintains routing tables and link state, and computes the forwarding table. In an SDN (Software-Defined Networking) Software-Defined Networking Separating the control plane from the data plane by computing forwarding tables in a remote controller. introduced in ch. 4 router it receives forwarding-table entries from the remote controller and installs them in the input ports.
”Port” here does not mean what it meant in chapters 2 and 3
The book flags this itself, and it is worth stopping on.
A port in chapters 2 and 3 was a 16-bit number in a transport-layer header, identifying a socket. Port 80, port 53, an ephemeral port above 1023.
A port in this chapter is a physical interface — a socket you can put a cable into. They have nothing to do with each other beyond the word.
How many of them: from a handful in an enterprise router up to hundreds of 10 Gbps ports at an ISP (Internet Service Provider) Internet Service Provider Connects hosts, and other ISPs, to the rest of the Internet. introduced in ch. 1 ‘s edge, where the incoming lines are most numerous. The book’s example is the Juniper MX2020 edge router, which supports up to 800 ports of 100 Gbps each, an overall system capacity of 800 Tbps.
Why it has to be hardware
Take a 100 Gbps input link and a 64-byte 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 datagram — the smallest interesting size.
64 bytes × 8 = 512 bits 512 bits ÷ 100 × 10⁹ bits per second = 5.12 nanoseconds
So a new datagram may arrive every 5.12 ns, and everything the input port does must fit in that. If N ports share a line card, the pipeline must run N times faster again.
Compare that with what the routing processor does — running routing protocols, reacting to a link going up or down, talking to a remote controller, answering management queries. Those happen on millisecond or second timescales.
Six orders of magnitude separate the two, and that gap is why the data plane is hardware and the control plane is software. It is the same gap section 4.1 drew as nanoseconds against seconds, now with a reason attached.
Everyday picture — the roundabout
Section 4.1 compared forwarding to getting through one interchange. The book now makes the interchange a roundabout.
A car stops at an entry station and states its final destination — not somewhere on the roundabout, but the end of its journey. An attendant looks it up, works out which exit leads there, and tells the driver. The car goes round and leaves by that exit, where it may meet other cars leaving at the same one.
- the entry road and entry station are the input port, attendant included;
- the roundabout is the switching fabric;
- the exit road is the output port.
The book then asks the questions that shape the rest of section 4.2, and they are worth holding on to because each one has a section attached:
- What if cars arrive fast but the attendant is slow? → input queuing (§4.2.4)
- What if the attendant is fast but cars cross the roundabout slowly? → fabric speed (§4.2.2)
- What if most cars want the same exit? → output queuing and head-of-line blocking (§4.2.4)
- What if we want to prioritise some cars, or block others? → packet scheduling (§4.2.5) and generalized forwarding (§4.4)
Where the picture stops. A driver states a destination and the attendant works out the exit. A real router is told nothing — it reads an address the sender wrote and never speaks to it. And the attendant knows the whole road network; the router knows one table, computed elsewhere.
The lookup, and why the table is small
A brute-force forwarding table forwarding table Simple A table in a router that says which outgoing link to use for each destination address. Precise A table in a router that maps destination addresses, or portions of destination addresses, to that router's outbound links. On arrival, the router examines the packet's destination address and searches this table to find the appropriate outbound link. introduced in ch. 1 — open in glossary would need one entry for every possible destination address. With 32-bit addresses that is more than 4 billion entries, and the book dismisses it in a sentence: totally out of the question.
So the table stores prefixes instead. The book’s example router has four links, numbered 0 to 3, and this table:
| Prefix | bits | |
|---|---|---|
| This 24-bit entry and the 21-bit entry below it overlap. That overlap is not a mistake; it is what longest prefix matching exists to resolve. | ||
Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.
Four entries in place of four billion. Sort by prefix length — the order of the rows never matters, only their length does.
Four entries in place of four billion, because a prefix stands for a whole range of addresses at once.
When two entries both match
Prefix 11001000 00010111 00011000 is 24 bits long. The first 24 bits of the address are 11001000 00010111 00011000. They match.
The address 11001000 00010111 00011000 10101010 matches two entries. Step through to see which one wins, and why the answer is not "the first one".
Read all steps as text
- 1 — Compare with the second entry: a 24-bit prefix — Prefix 11001000 00010111 00011000 is 24 bits long. The first 24 bits of the address are 11001000 00010111 00011000. They match.
- 2 — Compare with the third entry: a 21-bit prefix — Prefix 11001000 00010111 00011 is 21 bits long. The first 21 bits of the address are 11001000 00010111 00011. They also match.
- 3 — Two entries match. Which wins? — Not the first one found, and not the one that appears earlier in the table. The rule is the longest prefix match: the router takes the entry with the most matching bits.
- 4 — The packet goes out on interface 1 — The 24-bit entry wins because it is more specific. It names a smaller set of addresses, and the more specific rule is the one that was written for this address. Section 4.3.2 shows why the Internet is built to depend on this — it is what lets one organisation move to a new provider without renumbering.
In plain words
The rule is not “first match wins” and not “the entry listed first wins”. It is longest prefix match: the entry with the most matching bits.
The reason is that a longer prefix names a smaller, more specific set of addresses. If somebody wrote a rule covering exactly this address’s neighbourhood, that rule was written with more knowledge than the broad one, and it should win.
Section 4.3.2 gives the payoff. Longest prefix matching is what lets an organisation keep its addresses when it changes provider. The new provider advertises a longer, more specific prefix, and the world starts sending that organisation’s traffic to it. Nobody renumbers anything.
Doing a longest-prefix lookup in nanoseconds
Conceptually the lookup is simple: search the table for the longest matching prefix. At gigabit rates it must finish in nanoseconds, and a large table cannot be searched linearly in that time. So real routers use:
- specialised memory hierarchies — embedded on-chip DRAM (Dynamic Random Access Memory) Dynamic Random Access Memory Dense, comparatively slow memory. Routers embed it on-chip for forwarding tables and cache it with SRAM. introduced in ch. 4 with faster SRAM (Static Random Access Memory) Static Random Access Memory Faster and less dense than DRAM. Used as a DRAM cache in router lookup hardware, because memory access time is the binding constraint. introduced in ch. 4 used as a cache, because memory access time is the binding constraint;
- TCAM (Ternary Content Addressable Memory) Ternary Content Addressable Memory Memory whose stored bits can be 0, 1 or don’t-care. Present an address and it returns the matching forwarding-table entry in essentially constant time, whatever the table size. introduced in ch. 4 s — ternary content addressable memories. Present a 32-bit address and the memory returns the matching forwarding-table entry in essentially constant time, regardless of table size. The Cisco Catalyst 6500 and 7600 series can hold upwards of a million TCAM entries.
The “ternary” part is what makes a TCAM fit this problem: each stored bit can be 0, 1, or don’t care. A prefix is exactly a pattern of fixed bits followed by don’t-cares, so a TCAM matches all entries at once and returns the longest.
What else the input port does
Lookup is the important action, but not the only one. The book lists three more:
- Physical- and link-layer processing, as above.
- Header checks and rewrites — the packet’s version number and checksum are checked, and the checksum and time-to-live field are rewritten. Section 4.3.1 covers both fields; the point here is that a router genuinely modifies every datagram it forwards.
- Counters updated for network management — for example, the number of IP datagrams received.
And if the fabric is busy, the packet is queued at the input port and scheduled to cross later. That queue is section 4.2.4’s subject.
Match plus action, before it has a name
The book closes input-port processing by pointing at the shape of what just happened:
match — look up the destination address; action — send the packet into the fabric towards that output port.
That pair turns up everywhere:
| Device | Match on | Action |
|---|---|---|
| router (§4.2) | destination IP address | send to an output port |
| link-layer switch (ch. 6) | destination link-layer address | send to a port, plus others |
| firewall (ch. 8) | source/destination addresses and port numbers | drop the packet |
| NAT box (§4.3.3) | transport-layer port number | rewrite it, then forward |
Section 4.4 takes this pattern and makes it the general case, with matches over eleven header fields from three layers. Everything in this chapter after §4.3 is that idea being taken seriously.
Three ways to build the fabric
The fabric is at the heart of the router. The book gives three designs, and the difference between them is exactly one thing: how many packets may cross at once.
several packets per step. A crossbar is 2N buses joining N inputs to N outputs. Each vertical bus crosses each horizontal one at a crosspoint that the fabric controller can open or close. Close the crosspoint where input A meets output Y and the packet crosses. Several packets move in parallel, provided they want different output ports. A crossbar is non-blocking: a packet is never kept from an output port unless another packet is already going there.
These 3 packets need 1 time step to cross this fabric. All three want different output ports, so all three cross together. Real hardware: Cisco 12000 series; the CRS uses three non-blocking stages.
Three packets arrive at once, each wanting a different output port. Step the clock and count. Then press “all to the same output port” and watch the crossbar’s advantage vanish.
| Memorythe earliest routers | Busshared backplane | Crossbarinterconnection network | |
|---|---|---|---|
| Packets crossing at oncethe whole difference between the three | |||
| What caps the speed | |||
| How a packet is steered | |||
| Can a packet be blocked? | |||
| Real hardware |
Cells marked ⓘ have a reason behind them — click to read it.
One row is the one that matters: how many packets may cross at once. Click any cell for the reasoning.
The B/2 result, worked
Switching via memory is the oldest design, and it has a bound worth deriving.
The earliest routers were ordinary computers. An arriving packet raised an interrupt. The routing processor copied the packet from the input port into memory, read the destination, looked up the output port, and copied the packet out to that port’s buffers.
Every packet therefore crosses memory twice — one write and one read. If memory supports at most B packets per second written or read, then the total rate at which packets can be transferred from inputs to outputs is under
B / 2
Modern shared-memory routers keep the memory but move the work. The lookup and the store into memory are done by processing on the input line cards, not by a central processor. The book compares the result to a shared-memory multiprocessor. The factor of two remains.
A crossbar is non-blocking, and that is a narrower claim than it sounds
The book states it carefully. A crossbar is non-blocking: a packet will not be blocked from reaching its output port — as long as no other packet is currently being forwarded to that same port.
Read the second half again. Two packets from different input ports that both want the same output port cannot both cross. One waits at its input, because only one packet can be sent over any given bus at a time.
Press “all to the same output port” in the widget above and watch three time steps go by. The crossbar has not stopped being non-blocking; it is just that non-blocking was never a promise about output contention.
That surviving case is not a footnote. It is the thing section 4.2.4 is about, and it produces head-of-line blocking, which caps a whole input-queued switch at 58 % of its capacity.
Going faster than one fabric
Two ways the book mentions, both in production:
More stages. A multi-stage fabric uses several layers of switching elements so that packets from different input ports can head for the same output port at the same time. The Cisco CRS uses a three-stage non-blocking strategy.
More fabrics. Connect the input and output ports to N fabrics running in parallel. An input port breaks a packet into K smaller chunks and sprays the chunks through K of the N fabrics; the output port reassembles them. The switching capacity scales with the number of fabrics rather than the speed of any one of them.
Check yourself
Check yourself
0 of 6 answered1.Why are a router's input ports, output ports and switching fabric almost always built in hardware?
2.The word "port" in this section means something different from chapters 2 and 3. What?
3.predictThe address 11001000 00010111 00011000 10101010 matches a 24-bit prefix pointing at interface 1 and a 21-bit prefix pointing at interface 2. Which interface does the packet leave by?
Not the first match found.
4.Why does switching via memory cap forwarding throughput below B/2, where B is the number of packets per second memory can handle?
5.predictIn the fabric widget, set all three packets to the same output port and step the crossbar. How many time steps do they need?
6.The book calls the input port's job a "match plus action". Which of these is NOT an instance of the same pattern?
What to remember
- A router is four components: input ports, switching fabric, output ports, routing processor. The first three are hardware and are the data plane. The fourth is software and is the control plane.
- The forwarding table stores prefixes, not addresses — four entries instead of four billion. When several prefixes match, the longest one wins: not the first, not the earliest listed. The most specific rule was written with the most knowledge.
- Memory and bus fabrics move one packet at a time; a crossbar moves several — but only when they want different output ports. Everything else about the three fabrics follows from that one row.