The Network Core: Packet Switching · Computer Networking Interactive

The network core sends data by cutting it into packets, and every switch on the way must receive a whole packet before it can pass it on.

Words you will meet

Network core — the mesh of packet switches and links between the hosts.
Store-and-forward — a switch waits for the whole packet before sending any of it onward.
Output queue — the line where packets wait for a busy link. Also called the output buffer.
Queuing delay — how long a packet waits in that line.
Packet loss — a packet is dropped because the queue is already full.
Forwarding table — the table a router looks in to choose the outgoing link.
Routing protocol — what fills that table in automatically.
IP (Internet Protocol) address — the hierarchical address that identifies a host.

Why this matters

Two of the three things that make networks hard are introduced here: delay and loss. Store-and-forward is where delay begins, and a full queue is where loss begins.

Almost everything in chapter 3 exists because packets can be lost, and almost everything in chapter 5 exists because forwarding tables have to be filled in. Both problems start on this page.

What the core is

The network core is the mesh of packet switches and links that interconnects the Internet’s hosts. The way it moves data is called packet switching .

Figure 1.10 — the network core

The ringed devices are the network core: the mesh of packet switches and links that connects the hosts. Everything faded is edge or access. This section is about what happens inside the ringed part.

Drag any device to rearrange the picture. Hover a link to see its rate, delay and length.

The same map once more, now with the core picked out. Notice there are no hosts in it at all.

Read this diagram as text

Phone — wireless link — Cell tower (60 Mbps)
Tablet — wireless link — Cell tower (60 Mbps)
Cell tower — wired link — R-mob (1 Gbps)
Lin’s laptop — wireless link — Home AP (54 Mbps · 0.01 km)
Phone — wireless link — Home AP (54 Mbps)
Home AP — wired link — Home router (1 Gbps)
Home router — wired link — R1 (100 Mbps · 2 ms · 8 km)
PC — wired link — Switch (1 Gbps)
PC — wired link — Switch (1 Gbps)
AP — wired link — Switch (1 Gbps)
Server — wired link — Switch (10 Gbps)
Switch — wired link — R1 (1 Gbps)
R-mob — wired link — R1 (1 Gbps)
R1 — wired link — R2 (10 Gbps · 1 ms)
R2 — wired link — R3 (100 Gbps · 34 ms · 6,800 km)
R3 — wired link — R4 (100 Gbps · 4 ms)
R3 — wired link — R5 (100 Gbps · 3 ms)
R4 — wired link — R6 (100 Gbps · 5 ms)
R5 — wired link — R6 (100 Gbps · 4 ms)
R5 — wired link — Switch (100 Gbps)
Switch — wired link — Servers (100 Gbps)
R6 — wired link — R-cp (100 Gbps · 2 ms)
R-cp — wired link — Switch (10 Gbps)
Switch — wired link — www.example.edu (1 Gbps)

Notice what is not in the ringed part: any host at all. The core carries other people’s data and runs no applications of its own.

Messages become packets

In a network application, hosts exchange messages. A message can contain whatever the application designer wants. It might perform a control function — like the “Hi” messages in §1.1 — or it might carry data, such as an e-mail, an image or an audio file.

To send a message, the source breaks it into smaller chunks called packets . Each packet travels through communication links and packet switches on its own.

Packets are transmitted over each link at the full rate of that link. So if a host or a switch sends a packet of $L$ bits over a link of rate $R$ bits per second, the time to transmit it is $L/R$ seconds.

Live calculator — transmission delay of one packet on one link

What each symbol means

L — the length of the packet (bits)
R — the rate of the link (bits per second)
d_trans — the time to push every bit of the packet into the link (seconds)

Read aloud: the time is the number of bits in the packet, divided by how many bits the link sends each second.

Packet length L8,000 bits = 1,000 bytesbitsLink rate RMbps

Transmission delay80.0 µs

d_trans = L / R
        = 8,000 bits / 100 Mbps
        = 8.000e-5 s
        = 80.0 µs

Change any number above and the arithmetic re-runs, carrying the units through.

Store-and-forward

The rule that shapes everything else is called store-and-forward transmission .

The rule

Store-and-forward transmission means that the packet switch must receive the entire packet before it can begin to transmit the first bit of the packet onto the outbound link.

In plain words

A router is not a pipe. It is more like a person copying out a letter: they cannot start writing the copy until they have read the whole thing.

The consequence is that every link on the path costs a full $L/R$ , one after another. If switches instead forwarded each bit the moment it arrived, the total would be just $L/R$ however many links there were.

Follow it through with three packets crossing two links.

Figure 1.11 — store-and-forward, three packets over two links

t = 0step 1 of 5

The source starts pushing packet 1 into the first link. Nothing has arrived anywhere yet. The router can do nothing at all until the last bit of packet 1 reaches it.

Each block is one packet occupying one link for L/R seconds. Watch the second row start one slot later than the first — that overlap is the whole reason three packets do not cost three times as much.

Read all steps as text

t = 0 — The source starts pushing packet 1 into the first link. Nothing has arrived anywhere yet. The router can do nothing at all until the last bit of packet 1 reaches it.
t = L/R — Packet 1 is now completely inside the router, so the router may begin forwarding it. At the same instant the source is free, so it starts sending packet 2. Two links are now busy at once.
t = 2L/R — Packet 1 has arrived at the destination — one packet over two links costs 2L/R. Meanwhile the router has just received packet 2, and the source starts packet 3.
t = 3L/R — The destination now has packets 1 and 2. The router has packet 3 and begins forwarding it. The source has finished — it did its last work at 3L/R.
t = 4L/R — The destination has all three packets. Three packets over two links cost 4L/R, not 6L/R — because after the first packet, each one follows just one L/R behind the packet in front of it.

The general case

Now take a path of $N$ links, each of rate $R$ . That means $N-1$ routers sit between source and destination. The same logic gives the book’s equation 1.1:

d_{\text{end-to-end}} = N\,\frac{L}{R}

The book then poses a question and leaves it to the reader: what if we send $P$ packets over those $N$ links? The step-through above already answered it for $N = 2$ , $P = 3$ . The first packet pays the full $N$ hops; each packet after it arrives one $L/R$ behind the one in front. So:

d = (N + P - 1)\,\frac{L}{R}

Live calculator — equation 1.1, and the exercise the book leaves you

What each symbol means

N — the number of links on the path, so N − 1 routers (a count)
L — the length of each packet (bits)
R — the rate of every link (all the same here) (bits per second)
P — how many packets are sent back to back (a count)

Read aloud: one packet pays one transmission time per link; every packet after the first adds just one more.

Packet length LbitsLink rate RMbpsNumber of links NlinksNumber of packets Ppackets

One packet (equation 1.1)160 µs

d_end-to-end = N × L / R
             = 2 × 8,000 bits / 100 Mbps
             = 2 × 80.0 µs   (one hop)
             = 160 µs

P packets back to back320 µs

d = (N + P − 1) × L / R
  = (2 + 3 − 1) × 80.0 µs
  = 4 × 80.0 µs
  = 320 µs

Change any number above and the arithmetic re-runs, carrying the units through.

Set N = 2 and P = 3 and the second answer is 4L/R — the number the step-through above just walked you to. That second formula is the exercise the book poses and does not solve.

Everyday picture

A queue of people photocopying documents at a row of machines. Each person must finish copying the whole document at machine 1 before carrying it to machine 2. The second person can start at machine 1 as soon as the first person leaves it.

So the first document takes as long as there are machines. After that, one more document comes off the end every time one copying job finishes.

Where the picture breaks: people can see the queue and decide to come back later. Packets cannot. They arrive whether or not there is room, which is what makes loss — the next section — possible at all.

Queuing delays and packet loss

Each packet switch has several links attached. For each attached link it has an output queue , also called an output buffer, which stores the packets it is about to send into that link.

If a packet arrives and needs a link that is busy sending another packet, the arriving packet must wait in the output queue. So on top of the store-and-forward delay, packets also suffer queuing delay. Unlike $L/R$ , this one is variable: it depends on how congested the network is at that moment.

And because the buffer is finite, something worse can happen.

Where loss comes from

An arriving packet may find the buffer completely full. Then packet loss occurs: either the arriving packet or one of the already-queued packets is dropped.

Note what did not happen. The packet was not corrupted, and no link failed. The network simply had nowhere to put it. This is the ordinary way packets are lost on the Internet.

Figure 1.12 — where the queue forms

4 hops: A → router → router → router → E

Drag any device to rearrange the picture. Hover a link to see its rate, delay and length.

Two 100 Mbps links feed one 15 Mbps link. Send both journeys and the arithmetic is obvious: up to 200 Mbps can arrive at a router that can only send 15 Mbps onward. The surplus waits in the output queue, and when that fills, packets are dropped.

Read this diagram as text

A — wired link — router (100 Mbps)
B — wired link — router (100 Mbps)
router — wired link — router (15 Mbps)
router — wired link — C (100 Mbps)
router — wired link — router (100 Mbps)
router — wired link — D (100 Mbps)
router — wired link — E (100 Mbps)

The book’s example is worth doing in numbers. Hosts A and B both send to host E. Each reaches the first router over a 100 Mbps Ethernet link. The router must send everything onward over a 15 Mbps link.

Suppose A and B each send a burst of five packets back to back at the same moment. Data then arrives far faster than 15 Mbps can carry it away. Most of those packets will spend time waiting in the queue. If the burst is big enough to fill the buffer, packets are dropped.

§1.4.2 makes this quantitative, with the ratio that predicts when queues explode.

Forwarding tables and routing protocols

A router takes a packet in on one link and forwards it on another. But how does it choose which one?

In the Internet, every host has an IP (Internet Protocol) address . When a source sends a packet, it puts the destination’s IP address in the packet’s header. Like a postal address, this address has a hierarchical structure.

When a packet arrives, the router examines a portion of the destination address and forwards the packet to an adjacent router. Each router has a forwarding table that maps destination addresses — or portions of them — to that router’s outbound links.

Everyday picture — the book’s own analogy

Joe is driving from Philadelphia to 156 Lakeside Drive, Orlando, and refuses to use a map. He asks at a petrol station. The attendant reads only the Florida part of the address and says: take Interstate 95 south, then ask again.

In Jacksonville, another attendant reads the Orlando part: continue to Daytona Beach, then ask again. In Daytona Beach: take I-4 to Orlando. In Orlando, an attendant reads Lakeside Drive and names the road. On Lakeside Drive, a child on a bicycle reads 156 and points at the house.

Each person read only as much of the address as they needed, and each knew only the next step. The attendants and the child are routers.

Where the picture breaks: Joe carries himself, so he can ask questions on the way. A packet cannot ask anything — it is inspected by each router and passed on, with no say in the matter and no memory of where it has been.

Who fills in the table?

That leaves an obvious question: are forwarding tables configured by hand in every router?

No. The Internet has routing protocols that set the forwarding tables automatically. A routing protocol might, for example, work out the shortest path from each router to each destination, then use those results to configure the tables. Chapter 5 is devoted to how this is done.

Check yourself

Check yourself — §1.3.1

0 of 6 answered

1.What does store-and-forward mean?
2.predictIn the calculator, one packet crosses 3 links instead of 2. What happens to the end-to-end delay?
Change N from 2 to 3 and read the arithmetic.
3.Sending 3 packets over 2 links takes 4L/R, not 6L/R. Why?
4.Hosts A and B each send a burst of packets to host E across a 15 Mbps link. What causes packet loss?
5.How does a router decide which outgoing link to use for an arriving packet?
6.Who fills in the forwarding tables?

What to remember

Store-and-forward: a switch receives the whole packet before sending any of it on. So one packet over $N$ links costs $N \times L/R$ — that is equation 1.1.
Every link has an output queue. Waiting there is queuing delay, it varies with congestion, and a packet arriving at a full queue is simply lost.
A router forwards using a portion of the destination IP address and its forwarding table. Routing protocols fill that table in automatically.