Inside a Router: Input Ports, Switching Fabrics, Output Ports and Queues

The picture: an airport baggage system#

Think about your suitcase at an airport. You hand it in at a check-in desk. The agent reads where you are flying and tags it. The bag drops onto conveyor belts under the floor, which carry it to the loading area for your gate. There it waits with other bags until it is loaded onto the plane.

Upstairs, a control room decides which gate each flight uses and prints the charts the desk agents read.

A router is built the same way. The desks are input ports. The belts are the switching fabric. The loading areas are output ports. The control room is the routing processor. And if three desks send bags to one gate faster than it can load them, the pile grows. When the loading area is full, new bags are left behind. On a network, that is a lost packet.

Vocabulary, before anything uses it#

The four parts and the two planes#

Every router has the same four parts. Three of them handle every packet. The fourth does not forward packets at all.

Why hardware? A full-size 1,500-byte packet is 12,000 bits. On a 10 Gbps link it arrives in 12,000 ÷ 10,000,000,000 = 1.2 microseconds. So each lookup must finish in about a microsecond, on every port at once. For minimum-size 64-byte packets it is 512 ÷ 10,000,000,000 = 51.2 nanoseconds, which is why forwarding is described as taking nanoseconds. Software cannot keep that pace. To help, the processor copies the forwarding table to every input port, and each port looks up from its own copy.

Input ports and the forwarding table#

An input port does four jobs, in order:

1. Line termination: turn the signal on the wire or fiber back into bits (the physical layer).
2. Link-layer processing: check the frame and unwrap the datagram inside.
3. Lookup: read the destination IP address and find the output port.
4. Queuing: if the fabric is busy, hold the datagram until it can cross.

In destination-based forwarding, the destination address is the only field that matters. One row per address would mean about 4 billion rows, so the table lists ranges instead.

Each range is a block that shares a prefix. Write the last byte in binary and it shows. In the first range, the last byte always starts with 0: that is 24 bits of 198.51.100 plus one more bit, written 198.51.100.0/25 (128 addresses). The second range starts 10: 198.51.100.128/26 (64 addresses). The third starts 11: 198.51.100.192/26 (64 addresses). Three prefixes replace 256 rows.

Now add a row 198.51.100.160/27 → link 4. It covers 198.51.100.160 to 198.51.100.191, inside the link 1 range, so 198.51.100.170 matches two rows. The rule is longest prefix matching: use the longest, most specific prefix. The /27 beats the /26, so it goes to link 4. The longest prefix matching guide covers this rule in full. Routers do the lookup in special memory called TCAM (ternary content-addressable memory), which checks every row at once.

Three ways to build the switching fabric#

Once the port knows the output, the datagram must cross the router. There are three classic designs.

Switching via memory

The router is really a computer. The datagram is copied into memory, the processor finds the output, and the datagram is copied out again. So it crosses the memory bus twice. If the memory bus moves 20 Gbps, the router forwards at most 20 ÷ 2 = 10 Gbps.

Switching via a bus

The input port puts the datagram straight onto a shared bus (wires every port can see), labeled with its output. Every output sees it; only the labeled one keeps it. There is no second copy, but only one datagram fits on the bus at a time. So the router can never forward faster than the bus.

Switching via an interconnection network (crossbar)

A crossbar has a horizontal bus from each of the N inputs and a vertical bus to each of the N outputs: 2N buses. Where two buses cross, a switch can close. An 8-port crossbar has 16 buses and 8 × 8 = 64 crossing points. Datagrams cross at the same time if they go to different outputs. Two for the same output must take turns.

If the fabric runs N times the line rate (N × R), inputs never wait for it. For 8 ports at 10 Gbps, that is 80 Gbps.

Where packets wait, and where they are lost#

Packets wait in two places: at the input port, before the fabric, and at the output port, after it. If either buffer fills, packets are lost.

Input queuing and head-of-line blocking

Input queues grow when the fabric cannot carry everything at once, for example when two inputs want the same output. One wins and one waits. The queue is first in, first out, so everything behind the loser waits too.

Output queuing and packet loss

Even with a fast fabric, packets pile up at an output when several inputs send to it at once. They arrive faster than one link can send.

With drop-tail, a full buffer drops each new arrival. Some routers use active queue management instead: they drop packets, or set a congestion flag in them, a little before the buffer fills, to warn senders early. RFC 7567 recommends it, but assume drop-tail unless a question says otherwise.

How big should a buffer be?

Too small, and short bursts cause loss. Too big, and packets wait so long that delay becomes the problem (bufferbloat). The classic rule of thumb uses the average round-trip time (RTT) and the link capacity C to set the buffer size B:

B = RTT × C

Research in 2004 (Appenzeller, Keslassy and McKeown) showed that with N independent TCP flows (separate connections sharing the link), much less is enough:

B = RTT × C ÷ √N

Real vendors size buffers in many ways. Both formulas are guides, not laws.

Packet scheduling: who goes next#

When packets wait at an output, the scheduler picks the next one to send.

Practice#

Draw the router first and mark where the packet is. Show units in every calculation.

1. Name the four parts of a router and the plane each belongs to.
2. Using the forwarding table above plus the row 198.51.100.160/27 → link 4, which link does each destination use? (a) 198.51.100.100 (b) 198.51.100.175 (c) 198.51.100.230 (d) 192.0.2.1
3. A router switches via memory, and its memory bus moves 40 Gbps. What is its highest forwarding rate?
4. A crossbar has outputs P, Q and R. Input 1’s front packet is for P. Input 2’s front packet is for P, with one for Q behind it. Input 3’s front packet is for R. Input 1 wins. What crosses this round, and which output is idle that need not be?
5. Four inputs and one output, all 10 Gbps. All four send to that output at full rate. The output buffer holds 6 megabytes. How long until drops begin?
6. A 40 Gbps link has an RTT of 100 milliseconds and carries 40,000 TCP flows. Size the buffer by the rule of thumb and by the √N rule, in megabytes.
7. A 100 Mbps link uses WFQ with weights 5, 3 and 2. What is each class guaranteed?

Solutions#

1. Input ports, fabric and output ports: data plane. Routing processor: control plane. The first three handle every packet in hardware; the processor builds the forwarding table.
2. (a) Link 0. (b) Link 4. (c) Link 2. (d) Link 3. 100 is 01100100, so the /25. 175 is 10101111: it matches the /26 and the /27 (160 to 191), and the longer /27 wins. 230 is 11100110, so 198.51.100.192/26. 192.0.2.1 matches nothing, so the default row.
3. 20 Gbps. Each datagram crosses the memory bus twice, so 40 ÷ 2 = 20.
4. Input 1 to P and input 3 to R cross. Q is idle. Input 2’s front packet waits for P, and the packet for Q is stuck behind it: HOL blocking.
5. 1.6 milliseconds. Arrivals 4 × 10 = 40 Gbps, departures 10 Gbps, so growth is 30 Gbps. 6,000,000 × 8 = 48,000,000 bits. 48,000,000 ÷ 30,000,000,000 = 0.0016 s.
6. 500 MB and 2.5 MB. 0.1 × 40,000,000,000 = 4,000,000,000 bits = 500 MB. √40,000 = 200, and 4,000,000,000 ÷ 200 = 20,000,000 bits = 2.5 MB.
7. 50, 30 and 20 Mbps. Weights sum to 10: 5/10, 3/10 and 2/10 of 100.

Test-readiness checklist#

• ☐  I can draw a router’s four parts and say which plane each belongs to.
• ☐  I can list an input port’s four jobs and look up a destination, including overlapping prefixes.
• ☐  I can give the speed limit of switching via memory, a bus and a crossbar.
• ☐  I can explain head-of-line blocking with a small example.
• ☐  I can compute how fast an output queue fills, and size a buffer with RTT × C and RTT × C ÷ √N.
• ☐  I can describe FIFO, priority, round robin and WFQ, and compute WFQ shares.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written.