3 · Delay, loss, traceroute ★

HW1 P2–P5 · Sample midterm P5 · slides 1-43 → 1-51

The 4 sources of delay at each router

$$d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop}$$

Delay	What it is	Depends on
Processing $d_{proc}$	Check for bit errors, decide which output link	The router. Tiny, typically < 1 ms
Queuing $d_{queue}$	Waiting in the buffer for the output link to be free	Congestion. Changes from packet to packet
Transmission $d_{trans} = \dfrac{L}{R}$	Time to push all the bits of the packet onto the link	Packet size $L$ (bits) and link rate $R$ (bps). Not distance
Propagation $d_{prop} = \dfrac{d}{s}$	Time for one bit to travel the length of the wire	Distance $d$ and speed $s \approx 2\text{–}3 \times 10^8$ m/s. Not link rate

The #1 confusion: transmission vs propagation.
Transmission = how long to get the packet out the door (L/R). A faster link shrinks it.
Propagation = how long one bit takes to travel the road (d/s). Only a shorter wire shrinks it.
A 10 Gbps link across the ocean still has a big propagation delay.

Caravan analogy (slides)

10 cars (bits) = 1 caravan (packet). Each toll booth (router) takes 12 s per car. The next booth is 100 km away and cars drive 100 km/h. How long until the whole caravan is lined up at booth 2?

$$\underbrace{10 \times 12 \text{ s} = 120 \text{ s} = 2 \text{ min}}_{\text{transmission}} \;+\; \underbrace{\frac{100 \text{ km}}{100 \text{ km/h}} = 60 \text{ min}}_{\text{propagation}} \;=\; \mathbf{62 \text{ min}}$$

Change it: cars go 1000 km/h and the booth takes 1 min per car. The first car reaches booth 2 after 1 + 6 = 7 min, while 3 cars are still at booth 1. So when propagation is shorter than transmission, the first bit arrives before the last bit has left.

Where is the bit? (HW1 P2)

One link of rate $R$, length $m$, speed $s$. A starts sending at $t = 0$.

End-to-end delay (no queuing or processing): $$d_{end\text{-}end} = \frac{m}{s} + \frac{L}{R}$$
At $t = d_{trans}$, the last bit is just leaving A.
If $d_{prop} > d_{trans}$: at $t = d_{trans}$ the first bit is still in the link, not at B yet.
If $d_{prop} < d_{trans}$: at $t = d_{trans}$ the first bit has already reached B.

Worked example: when are they equal? (P2 g)

$s = 2.5 \times 10^8$ m/s, $L = 120$ bits, $R = 56$ kbps. Find $m$ so $d_{prop} = d_{trans}$.

$$\frac{m}{s} = \frac{L}{R} \;\Rightarrow\; m = \frac{L \cdot s}{R} = \frac{120 \times 2.5 \times 10^8}{56{,}000} \approx 535{,}714 \text{ m} \approx \mathbf{536 \text{ km}}$$

Multi-hop end-to-end delay (HW1 P4)

3 links, 2 routers in between. Each link adds its own transmission + propagation. Each router adds processing. (Store-and-forward: every router must receive the full packet before resending it, so you pay $L/R$ on every link.)

$$d_{end\text{-}end} = \frac{L}{R_1} + \frac{L}{R_2} + \frac{L}{R_3} + \frac{d_1}{s_1} + \frac{d_2}{s_2} + \frac{d_3}{s_3} + 2\,d_{proc}$$

Worked example

$L = 1500$ bytes, all links 2 Mbps, $s = 2.5 \times 10^8$ m/s, $d_{proc} = 3$ ms, link lengths 5000 km, 4000 km, 1000 km.

Bytes → bits first. $L = 1500 \times 8 = 12{,}000$ bits
Transmission per link: $$\frac{12{,}000}{2 \times 10^6} = 0.006 \text{ s} = 6 \text{ ms} \quad (\times 3 \text{ links} = 18 \text{ ms})$$
Propagation per link: $$\frac{5 \times 10^6}{2.5 \times 10^8} = 20 \text{ ms}, \quad \frac{4 \times 10^6}{2.5 \times 10^8} = 16 \text{ ms}, \quad \frac{1 \times 10^6}{2.5 \times 10^8} = 4 \text{ ms}$$
Processing: 2 routers × 3 ms = 6 ms
Add: $$6+6+6 \;+\; 20+16+4 \;+\; 3+3 = \mathbf{64 \text{ ms}}$$

Traps: bytes vs bits (×8), km vs m (×1000), and counting routers. N links have N − 1 routers between them.

Worked example: VoIP (HW1 P3)

A turns voice into a 64 kbps stream and groups bits into 56-byte packets. One link: 2 Mbps, 10 ms propagation. How long from when a bit is created until it's decoded at B?

The trick: there's a 4th delay hiding here. The first bit has to wait for the whole packet to be filled before anything is sent.

Packetization (filling the packet): $$\frac{56 \times 8}{64{,}000} = \frac{448}{64{,}000} = 7 \text{ ms}$$
Transmission: $$\frac{448}{2 \times 10^6} = 224\ \mu\text{s} = 0.224 \text{ ms}$$
Propagation: 10 ms
Total: $$7 + 0.224 + 10 = \mathbf{17.224 \text{ ms}}$$

Queuing delay

Traffic intensity

$a$ = average packet arrival rate (packets/s), $L$ = bits per packet, $R$ = link rate.

$$\text{traffic intensity} = \frac{L \cdot a}{R} = \frac{\text{bits arriving per second}}{\text{bits the link can send per second}}$$

$La/R \approx 0$: queuing delay is small.
$La/R \to 1$: queuing delay gets large (blows up near 1).
$La/R > 1$: more work arrives than can be served, so delay is infinite. Never design a system like this.

Example: 100 packets/s of 1500 bytes on a 1.5 Mbps link: $$\frac{12{,}000 \times 100}{1.5 \times 10^6} = 0.8$$ That's close to 1, so expect a large queuing delay.

N packets arrive at once (HW1 P5)

N packets of length L arrive together at an empty link of rate R. Packet 1 waits 0, packet 2 waits L/R, packet 3 waits 2L/R, …, packet N waits (N−1)L/R.

$$\text{avg} = \frac{1}{N}\left(0 + \frac{L}{R} + \frac{2L}{R} + \cdots + \frac{(N-1)L}{R}\right) = \frac{L}{RN}\cdot\frac{N(N-1)}{2} = \mathbf{\frac{(N-1)\,L}{2R}}$$

Example: N = 4, L = 1000 bits, R = 1 Mbps. Each packet takes 1 ms, so the waits are 0, 1, 2, 3 ms → average 1.5 ms. Check: $\frac{3 \times 1000}{2 \times 10^6} = 1.5$ ms ✓

(b) Batches of N arrive every LN/R seconds: it takes exactly LN/R to send a batch, so the buffer is empty when the next batch shows up. Every batch looks like the first one, so the answer is the same: $\frac{(N-1)L}{2R}$.

Packet loss

The buffer before a link has finite size. A packet arriving at a full buffer is dropped (lost).
A lost packet may be retransmitted by the previous node, by the source, or not at all.

Traceroute (Sample P5)

How it works: for each router $i$ on the path, the sender sends 3 probe packets with TTL = $i$. Router $i$ sends a message back, and the sender measures the round-trip time. So each line = 3 RTT measurements to that router. * = no reply (probe lost or router doesn't answer).

 1  cs-gw              1 ms   1 ms   2 ms
 ...
 7  nycm-wash...      22 ms  22 ms  22 ms
 8  62.40.103.253    104 ms 109 ms 106 ms   ← big jump

Q: The 3 delays to router 1 are 1, 1, 2 ms. Why are they different?

Queuing delay changes from moment to moment as the routers' congestion changes. The distance (propagation) and packet size (transmission) are the same for all 3 probes, so the variation comes from queuing.

Q: Router 7 → 8 jumps from ~22 ms to ~104 ms. Why?

That hop is the trans-oceanic link (New York → Europe). The jump is propagation delay over the long physical distance.

Q: Some later routers show a smaller delay than earlier ones. How?

Each line is a separate measurement taken at a different moment, so queuing delay differs between them. A later router can catch a less congested moment and come back faster.

Quick check

1. Which delay does a faster link rate reduce? Which one doesn't it affect?

It reduces transmission delay (L/R). It doesn't change propagation delay (d/s), which depends only on distance and signal speed.

2. Which of the 4 delays is the one that varies a lot from packet to packet?

Queuing. It depends on how congested the router is at that moment.

3. Traffic intensity is 1.2. What happens?

More bits arrive per second than the link can send, so the queue grows without limit. Average delay → infinite (and in practice, packets get dropped).

4. Practice: 2 links, 1 router. L = 8000 bits, both links 1 Mbps, lengths 2000 km and 1000 km, s = 2×10⁸ m/s, d_proc = 1 ms. End-to-end delay?

Transmission: 8000 / 10⁶ = 8 ms per link → 16 ms
Propagation: 2×10⁶ / 2×10⁸ = 10 ms, and 1×10⁶ / 2×10⁸ = 5 ms → 15 ms
Processing: 1 router × 1 ms = 1 ms
Total: 16 + 15 + 1 = 32 ms

5. Practice: 6 packets of 1500 bytes arrive at once at an empty 10 Mbps link. Average queuing delay?

$$\frac{(N-1)L}{2R} = \frac{5 \times 12{,}000}{2 \times 10^7} = 0.003 \text{ s} = \mathbf{3 \text{ ms}}$$

← 2 · Packet vs circuit switching · all topics

Delay	What it is	Depends on
Processing \(d_{proc}\)	Check for bit errors, decide which output link	The router. Tiny, typically < 1 ms
Queuing \(d_{queue}\)	Waiting in the buffer for the output link to be free	Congestion. Changes from packet to packet
Transmission \(d_{trans} = \dfrac{L}{R}\)	Time to push all the bits of the packet onto the link	Packet size \(L\) (bits) and link rate \(R\) (bps). Not distance
Propagation \(d_{prop} = \dfrac{d}{s}\)	Time for one bit to travel the length of the wire	Distance \(d\) and speed \(s \approx 2\text{–}3 \times 10^8\) m/s. Not link rate