Delay in Packet-Switched Networks · Queuing Delay and Packet Loss

A packet waits four times at every router, and only one of those four waits changes from packet to packet.

Words you will meet

Processing delay — the time to read the header and pick the outgoing link.
Queuing delay — the time spent waiting behind other packets.
Transmission delay — the time to push all the bits into the link: L/R.
Propagation delay — the time for a bit to travel along the link: d/s.
Nodal delay — all four added together, at one router.
Traffic intensity — La/R: bits arriving each second, over bits leaving each second.
Packet loss — a packet dropped because the queue was full.

Why this matters

We would like the Internet to move as much data as we want, instantly, without losing any. It cannot. This section is where the book stops describing and starts measuring.

The four delays and the ratio La/R come back constantly:

chapter 3 estimates round-trip time and controls congestion;
chapter 4 studies queuing inside a router;
chapter 6 measures how long nodes wait to share a link.

All of it starts here.

The four delays

A packet starts in a host, passes through a series of routers, and ends in another host. At each node along the way it suffers four kinds of delay, which add up to the nodal delay for that node.

Figure 1.16 — the four delays a packet meets at router A

1 · processingstep 1 of 5

Router A reads the packet’s header, decides which outbound link it needs, and may check the bits for errors that happened on the way in. In a high-speed router this takes microseconds or less.

Each step highlights one component. Only the second of them changes from packet to packet.

Read all steps as text

1 · processing — Router A reads the packet’s header, decides which outbound link it needs, and may check the bits for errors that happened on the way in. In a high-speed router this takes microseconds or less.
2 · queuing — The packet joins the queue in front of the link to router B. It waits for every packet that arrived before it. If the queue is empty it waits not at all; under heavy traffic it waits a long time. This is the only one of the four that varies from packet to packet.
3 · transmission — Its turn comes. The router pushes all L bits of the packet into the link at rate R, which takes L/R seconds. This depends on the packet’s length and the link’s rate — and not at all on how far away router B is.
4 · propagation — The bits travel down the link to router B at the propagation speed of the medium, between 2×10⁸ and 3×10⁸ metres per second. This takes d/s seconds. It depends on the distance — and not at all on the packet’s length or the link’s rate.
total — Add the four together and you have the nodal delay: d_nodal = d_proc + d_queue + d_trans + d_prop. The whole process then repeats at router B.

Processing delay

Processing delay is the time required to examine the packet’s header and determine where to direct the packet. It can include other work too, such as checking for bit-level errors that happened while the packet’s bits travelled from the upstream node.

In high-speed routers this is typically microseconds or less. Small as it is, it matters for one reason: it strongly influences a router’s maximum throughput, the greatest rate at which it can forward packets at all.

Queuing delay

Queuing delay is the time the packet waits at the queue to be transmitted onto the link. Its length depends on how many earlier-arriving packets are already queued and waiting.

If the queue is empty and no other packet is being transmitted, the queuing delay is zero. If traffic is heavy, it can be long. In practice it ranges from microseconds to milliseconds. Section 1.4.2, below, is entirely about this one.

Transmission delay

Transmission delay is what it costs to push a packet out. Packets are transmitted first-come-first-served, so a packet can be transmitted only after every packet that arrived before it. When its turn comes, the router pushes all of its bits into the link.

d_{\text{trans}} = \frac{L}{R}

$L$ — the packet’s length, in bits.
$R$ — the rate of the link, in bits per second.

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

Live calculator — transmission delay depends on L and R only

What each symbol means

L — the packet’s length (bits)
R — the link’s rate (bits per second)

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

Packet length LbitsLink rate RMbps

Transmission delay1.20 ms

d_trans = L / R
        = 12,000 bits / 10.0 Mbps
        = 1.200e-3 s
        = 1.20 ms

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

Propagation delay

Propagation delay is what it costs to cross the distance. Once a bit is pushed into the link, it has to travel to the router at the far end.

d_{\text{prop}} = \frac{d}{s}

$d$ — the distance between the two routers, in metres.
$s$ — the propagation speed of the link, in metres per second. It depends on the physical medium and lies between $2 \times 10^8$ and $3 \times 10^8$ — equal to, or a little less than, the speed of light.

Read aloud: the time is the distance, divided by how fast a bit travels through this medium.

In wide-area networks propagation delays are on the order of milliseconds.

Live calculator — propagation delay depends on d and s only

What each symbol means

d — the distance between the two nodes (metres)
s — the propagation speed of the medium, 2×10⁸ to 3×10⁸ (metres per second)

Read aloud: the distance, divided by how fast a bit travels through this medium.

Distance dkmPropagation speed s×10⁸ m/s

Propagation delay45.0 ms

d_prop = d / s
       = 9,000,000 m / 2.0e+8 m/s
       = 45.0 ms
(the packet's length and the link's rate do not appear)

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

The default is the canonical running example: Bangkok to Frankfurt, about 9,000 km. Change the packet length — you cannot. It is not an input here, because it does not belong in this formula.

The comparison people get wrong

Transmission delay is not propagation delay

Transmission delay is the time for the router to push the packet out. It is a function of the packet’s length and the link’s rate. It has nothing to do with the distance between the two routers.
Propagation delay is the time for one bit to travel from one router to the next. It is a function of the distance. It has nothing to do with the packet’s length or the link’s rate.

The difference is subtle and important. If you remember one thing from §1.4, make it this.

Everyday picture — the book’s caravan

A highway with a tollbooth every 100 km. The highway segments are links and the tollbooths are routers. Cars travel at 100 km/h. Ten cars travelling together are a packet, and each car is a bit.

Where the picture breaks: cars can overtake, break down, and choose to leave the road. Bits within one packet do none of these — they arrive in the order they were sent or the packet is discarded whole. The analogy is about timing, not about freedom of movement.

The caravan analogy — Figure 1.17, in motion

t = 0step 1 of 4

The ten-car caravan arrives at the first tollbooth. The first car must wait at the entrance until all nine others have lined up behind it: the whole caravan is stored before any of it is forwarded. This is store-and-forward.

The tollbooth serves one car every 12 seconds, so 5 cars a minute. Ten cars therefore take 2 minutes to push onto the road — that is transmission delay. Driving the 100 km takes 1 hour — that is propagation delay.

Read all steps as text

t = 0 — The ten-car caravan arrives at the first tollbooth. The first car must wait at the entrance until all nine others have lined up behind it: the whole caravan is stored before any of it is forwarded. This is store-and-forward.
t = 2 min — The tollbooth has served all ten cars — 10 cars ÷ 5 cars per minute = 2 minutes. This is exactly the transmission delay: the time to push the whole packet onto the link.
t = 62 min — One hour later the caravan has driven the 100 km and is stored in front of the second tollbooth. Total: 2 minutes of transmission plus 60 minutes of propagation = 62 minutes. Notice that making the cars longer would change the first number and not the second.
faster cars — Now let the cars travel at 1,000 km/h and let the tollbooth serve one car per minute. Driving between booths takes 6 minutes, but serving the caravan takes 10. The first cars reach the second tollbooth before the last cars have left the first — exactly as the first bits of a packet can reach a router while the rest are still being transmitted.

Adding the four together

d_{\text{nodal}} = d_{\text{proc}} + d_{\text{queue}} + d_{\text{trans}} + d_{\text{prop}}

The contribution of each component varies enormously with the situation.

$d_{\text{prop}}$ can be a couple of microseconds for two routers on the same university campus. For two routers joined by a geostationary satellite link it is hundreds of milliseconds, and dominates everything else.
$d_{\text{trans}}$ is typically negligible at 10 Mbps and above, as on a LAN (Local Area Network) . For large packets over a low-speed dial-up modem link it can be hundreds of milliseconds.
$d_{\text{proc}}$ is often negligible.

Live calculator — all four together, and which one dominates

What each symbol means

d_proc — processing: reading the header (microseconds)
d_queue — queuing: waiting behind other packets (milliseconds)
d_trans — transmission: L/R (seconds)
d_prop — propagation: d/s (seconds)

Read aloud: the total wait at one router is the four components added together — and the percentages show which one actually matters.

Packet length LbitsLink rate RMbpsDistance dkmPropagation speed s×10⁸ m/sProcessing delayµsQueuing delayms

Nodal delay47.2 ms

d_nodal = d_proc + d_queue + d_trans + d_prop
d_proc  =   2.00 µs     0.0 %
d_queue =   1.00 ms     2.1 %
d_trans =   1.20 ms     2.5 %   (L/R)
d_prop  =   45.0 ms    95.3 %   (d/s)
d_nodal = 47.2 ms

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

Try three settings. A campus link (d = 1 km) — transmission dominates. An intercontinental link (d = 9,000 km) — propagation dominates. A dial-up modem (R = 0.056 Mbps) — transmission dominates again, by a lot.

Queuing delay, properly

Queuing delay is the most complicated and the most interesting of the four. Thousands of papers and several books have been written about it.

It is also the only one that varies from packet to packet. Suppose ten packets arrive at an empty queue at the same instant. The first suffers no queuing delay at all, while the last waits for the other nine to be transmitted. So queuing delay is described statistically: the average, the variance, and the probability that it exceeds some particular value.

Traffic intensity

When is queuing delay large, and when is it insignificant? Three things decide it: the rate at which traffic arrives, the rate of the link, and whether the traffic arrives smoothly or in bursts.

Let $a$ be the average rate at which packets arrive, in packets per second. Let $R$ be the link rate in bits per second, and suppose all packets are $L$ bits. Then bits arrive at an average rate of $La$ bits per second, and the ratio

\text{traffic intensity} = \frac{La}{R}

is what governs the queue. It is called the traffic intensity .

Live calculator — traffic intensity La/R

What each symbol means

L — the length of each packet (bits)
a — the average rate at which packets arrive (packets per second)
R — the rate at which bits leave the queue (bits per second)

Read aloud: the bits arriving each second, divided by the bits that can leave each second.

Packet length LbitsArrival rate apackets/sLink rate RMbps

Traffic intensity0.800

La/R = (L × a) / R
     = (8,000 bits × 1000 packets/s) / 10.0 Mbps
     = 8.00 Mbps arriving / 10.0 Mbps leaving
     = 0.800

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

The golden rule

If $La/R > 1$ , bits arrive faster than they can be transmitted. The queue grows without bound, and the queuing delay approaches infinity.

One of the golden rules in traffic engineering is: design your system so that the traffic intensity is no greater than 1.

Even below 1, the shape of the traffic matters

Suppose $La/R \le 1$ . The nature of the arriving traffic now decides everything.

If packets arrive perfectly periodically — one packet every $L/R$ seconds — then every packet finds an empty queue and there is no queuing delay at all.

Now let packets arrive in bursts but periodically: $N$ packets arriving together every $(L/R)N$ seconds. The first packet transmitted has no queuing delay, the second waits $L/R$ , and the $n$ th waits $(n-1)L/R$ .

Real arrivals are neither. They are random: packets are spaced apart by random amounts of time and follow no pattern. In that realistic case $La/R$ is not enough to fully characterise the queuing delay, but it still gives the right intuition:

Intensity close to 0 — arrivals are few and far between, and an arriving packet is unlikely to find another one waiting. Average queuing delay is close to zero.
Intensity close to 1 — there are intervals when the arrival rate exceeds the link’s capacity and a queue forms; when it drops below, the queue shrinks again. As intensity approaches 1, the average queue length gets larger and larger.

Figure 1.18 — average queuing delay against traffic intensity

One packet’s transmission time L/R1.0 ms

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

Average queuing delay:—

The shape is the lesson. Below about 0.7 the curve is almost flat; past 0.9 it climbs steeply; at 1 it has no finite value at all. Drag the slider to change L/R and watch the whole curve scale, but never change shape.

In plain words

As traffic intensity approaches 1, average queuing delay does not rise steadily — it increases rapidly. A small percentage increase in intensity produces a much larger percentage increase in delay.

You have felt this on a road. If a route is usually congested, its traffic intensity is already close to 1. Any small extra load — one event, one closed lane — and the delay you experience is enormous.

Watch it happen

One output queue, running

Arrival rate a800 packets/sBuffer size20 packets

Traffic intensity La/R = (8,000 bits × 800/s) ÷ 10 Mbps = 0.64 — comfortably below 1

Arrived: 0
Sent on: 0
Dropped ✕: 0 (0.0 %)

Start at 800 packets/s (La/R = 0.64) and watch the trace stay low. Move to 1,200 (0.96) and watch the swings grow. Move past 1,250 (La/R > 1) and watch the buffer stay full while the drop counter climbs.

Packet loss

Everything above assumed the queue could hold an unlimited number of packets. It cannot. A real queue in front of a link has finite capacity, though how much depends on the router’s design and cost.

So delays do not really approach infinity as the traffic intensity approaches 1. Instead a packet arrives to find a full queue. With nowhere to store it, the router drops it, and the packet is lost.

What loss looks like from the outside

From an end system’s point of view, a lost packet was transmitted into the network core and never emerged at the destination. Nothing announces it. No error message comes back.

The fraction of lost packets rises as traffic intensity rises. So performance at a node is measured not only by delay but also by the probability of packet loss.

A lost packet may be retransmitted, end to end, so that all the data eventually arrives. But that requires the sender to notice the loss in the first place, and noticing is the subject of chapter 3.

Check yourself

Check yourself — §1.4.1–1.4.2

0 of 7 answered

1.You double the length of a packet. Which delay component changes?
2.You move the two routers twice as far apart, keeping the same link rate. Which delay changes?
3.Which of the four delay components varies from one packet to the next?
4.predictIn the queue simulator, set the arrival rate so that La/R is about 0.95, then run it. What do you see?
Watch the queue-length trace, not just the current number.
5.predictNow push the arrival rate until La/R is above 1 and keep running. What happens to the dropped counter?
Watch the buffer fill first, then watch the loss percentage.
6.In the caravan analogy, what plays the part of one bit?
7.A packet is lost. From the sending host's point of view, what does that look like?

What to remember

Four delays at every node: processing, queuing, transmission, propagation. They add up to $d_{\text{nodal}}$ .
$d_{\text{trans}} = L/R$ depends on packet length and link rate, never on distance. $d_{\text{prop}} = d/s$ depends on distance, never on packet length or link rate.
Traffic intensity is La/R. Above 1 the queue grows without bound, and because real buffers are finite the excess becomes packet loss rather than infinite delay.