Pipelined Reliable Data Transfer Protocols · Computer Networking Interactive

rdt3.0 works and is unusable: it leaves a gigabit link idle 99.97 % of the time, and the fix is to stop waiting.

Words you will meet

Sender utilization — the fraction of the time the sender is actually putting bits on the link.
Pipelining — allowing several unacknowledged packets to be in flight at once.
Bandwidth-delay product — link rate × round-trip time: how many bits fit in the pipe.
Go-Back-N and selective repeat — the two ways of recovering from loss once you pipeline.

Why this matters

Section 3.4.1 finished a protocol that is correct. This section shows it is also unusable, and the gap between those two words is where a great deal of networking lives.

The number below is the one to remember from this whole section. It explains something you have already met — why section 2.2.2’s round-trip counting was optimistic — and it is why TCP (Transmission Control Protocol) has a window at all.

The performance of stop-and-wait

Take two hosts, one on each coast of the United States. The speed-of-light round-trip propagation delay between them is about 30 milliseconds. Connect them with a 1 Gbps link and send 1,000-byte packets — 8,000 bits, headers included.

The time to put one packet on the link is

$d_{trans} = \frac{L}{R} = \frac{8000\ \text{bits}}{10^9\ \text{bits/s}} = 8\ \mu s$

Now follow the clock. The sender starts at t = 0. At t = 8 µs the last bit enters the channel. The packet crosses the country, and its last bit reaches the receiver at t = RTT/2 + L/R = 15.008 ms. Assume acknowledgements are small enough that their own transmission time can be ignored, and that the receiver replies as soon as the last bit lands. The ACK gets back to the sender at t = RTT + L/R = 30.008 ms.

Only then can the next packet go.

Figure 3.18 — the same link, two protocols

One packet, then a full round trip of nothing. In 30.008 ms the sender transmits for 0.008 ms — 2.7 hundredths of one percent of the time.

message 3 of 3

Click any arrow to see what that message says and why it is sent.

Both runs use the book’s numbers: 1 Gbps, 30 ms round trip, 8 µs to put one packet on the link. Switch between them and watch how much of the timeline is empty.

Read this diagram as text

Sender sends packet 1 to Receiver (15 ms). The first bit goes out at t = 0. The last bit enters the channel at t = L/R = 8 µs — too small to see on this scale. The packet then makes its 15 ms cross-country journey.
Receiver sends ACK to Sender (15 ms). The last bit arrives at t = RTT/2 + L/R = 15.008 ms and the receiver acknowledges at once. The ACK is assumed small enough that its own transmission time can be ignored. It reaches the sender at t = RTT + L/R = 30.008 ms.
Sender sends packet 2 to Receiver (15 ms). Only now may the sender transmit again. Everything between 8 µs and 30 ms was idle link.

Lifelines, left to right: Sender (host), Receiver (host).

In 30.008 milliseconds, the sender was sending for 0.008

Define the sender utilization as the fraction of time the sender is actually busy putting bits on the link. Then

$U_{sender} = \frac{L/R}{RTT + L/R} = \frac{0.008}{30.008} = 0.00027$

The sender is busy 2.7 hundredths of one percent of the time.

Put it another way: 1,000 bytes in 30.008 ms is an effective throughput of about 267 kbps — on a link that can carry a gigabit. Imagine the network manager who has just paid a fortune for gigabit capacity and is getting 267 kilobits out of it.

And this is the optimistic version. We ignored protocol-processing time at both ends, and every queuing and processing delay at every router in between. Including them would only make it worse.

Sender utilization

What each symbol means

L — packet length, header and data together (bits)
R — link rate (bits/s)
RTT — round-trip time (s)
N — packets the sender may have in flight at once (packets)

Read aloud: Out of one send-and-wait cycle, what fraction of the time is the sender actually putting bits on the link?

Packet lengthbitsLink ratebits/sRound-trip timesPackets in flightN = 1 is stop-and-waitpackets

Sender utilization0.000267

one packet takes L/R = 8,000 bits / 1.00 Gbps = 8.00 µs to send
after sending, the sender waits a full round trip: RTT + L/R = 30.0 ms
with 1 packet in flight it is busy 1 × 8.00 µs = 8.00 µs of that
U_sender = 8.00 µs / 30.0 ms = 0.000267
effective throughput = U × R = 267 kbps on a 1.00 Gbps link
to reach U = 1 the sender would need 3,751 packets in flight

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

The defaults are the book’s cross-country example exactly. Then try Lin’s path: L = 11680, R = 100000000, RTT = 0.18 — a slower link, and a worse result.

Lin’s path is worse, on a link a hundred times slower

Set the calculator to the canonical example used throughout this site: a 1,460-byte segment (11,680 bits), Lin’s 100 Mbps access link, and the 180 ms round trip to Frankfurt.

one segment takes 116.8 µs to transmit
the cycle is 180.1168 ms
U = 0.000648, an effective throughput of 64.8 kbps

A hundred-megabit link delivering 65 kilobits. It is worse than the gigabit example, and the reason is worth stating plainly: utilization depends on the ratio of transmission time to round-trip time, not on either one alone. Lin’s link is slower, which helps the ratio, but her path is six times longer, which hurts it more.

This is also the answer to a question chapter 2 left open. Section 2.2.2 priced a page load in round trips and assumed the link filled instantly once a connection was open. A stop-and-wait protocol would never fill it at all.

The fix: stop waiting

The solution is as simple as the problem. Rather than operating in a stop-and-wait manner, the sender is allowed to send several packets without waiting for acknowledgements.

Because the in-transit packets can be pictured as filling a pipe, this is called pipelining, and a protocol that does it is a pipelined protocol . It is the same word, and the same idea, as section 2.2.2’s HTTP (HyperText Transfer Protocol) pipelining, one layer up. There a browser sent requests without waiting for responses; here a transport sender sends packets without waiting for acknowledgements.

Switch the diagram above to the pipelined run. Three packets in flight instead of one, and the utilization is essentially tripled.

Utilization against how many packets are in flight

Packet length11680 bitsLink rate100 MbpsRound-trip time180 ms

At 2400 (move the pointer over the plot to read it anywhere):

U_sender:1.0

Drag the sliders to Lin’s path — 11,680 bits, 100 Mbps, 180 ms — and find the knee. Everything to the right of it is window you are paying for and not using.

In plain words

The curve rises in a straight line and then stops dead at 1.

The straight part is easy: two packets in flight is twice as good as one, three is three times as good. The knee is the interesting part. It sits at the point where the sender is transmitting continuously — where the first acknowledgement comes back exactly as the last packet of the window goes out.

That number has a name: the bandwidth-delay product, link rate multiplied by round-trip time. On Lin’s path it is 100 Mbps × 180 ms = 18,000,000 bits, or 2.25 megabytes, or about 1,541 segments of 1,460 bytes.

So a window of roughly 1,540 fills her pipe, and a window of 15,000 fills it no better. Everything past the knee is memory you are paying for and not using.

Hold on to that number — it comes back twice

1,540 segments in flight is what it takes to keep Lin’s link busy.

Section 3.5.5 will show that TCP’s receive-window field is 16 bits, so it can advertise at most 65,535 bytes — about 45 segments. That is thirty times too small, and it is why the window scale option exists.

Section 3.7.1 will show that TCP does not start with a large window anyway. It starts with one segment and works upward, which is a different way of arriving at the same problem.

What pipelining costs

Nothing is free. Allowing many packets in flight has three consequences.

What pipelining costs

	Why

Cells marked ⓘ have an explanation — click to read it. Sortable columns have a ↕ in the heading.

Three consequences, and the third one is why this section has two sequels rather than none.

The third is the one that shapes the next two sections. There are two basic approaches to pipelined error recovery, and they differ in what the sender retransmits after a loss:

Go-Back-N, in section 3.4.3 — resend the lost packet and everything after it. The receiver keeps nothing out of order, so it is simple; and when the window is large, it retransmits a great deal that did not need retransmitting.
Selective repeat, in section 3.4.4 — resend only what was actually lost. The receiver must buffer out-of-order packets, and the sender needs a timer per packet.

Check yourself

0 of 5 answered

1.On the book's cross-country link — 1 Gbps, 30 ms round trip, 1,000-byte packets — a stop-and-wait sender achieves about 267 kbps. Why so little?
2.predictSet the calculator to Lin's path — 100 Mbps, 180 ms, 1,460-byte segments — with one packet in flight. Roughly what throughput does stop-and-wait manage?
The link is a hundred times slower than the book's, but the round trip is six times longer.
3.What does pipelining actually change?
4.predictOn the utilization curve, what happens once the window passes about 1,540 packets on Lin's path?
5.Which of these is NOT a consequence of pipelining?

What to remember

Stop-and-wait wastes the link. On the book’s 1 Gbps, 30 ms path a sender is busy 0.027 % of the time and gets 267 kbps. Utilization depends on the ratio of transmission time to round-trip time.
Pipelining lets the sender have several unacknowledged packets in flight. Three in flight roughly triples utilization.
The curve flattens at the bandwidth-delay product — link rate × round-trip time. On Lin’s path that is 2.25 MB, about 1,540 segments. Beyond it, a bigger window buys nothing.