Propagation, queuing and processing delay; multi-hop pipelining

1. T_t of a 500-byte packet at 2 Mbps?
   Stuck? Peek at 1.3.1 Bandwidth, data rate, throughput and transmission delay

   • Bandwidth / data rate B = link capacity in bps (decimal prefixes).
   • T_t = L / B (L in bits) — independent of distance.
   • Throughput = bits delivered / time ≤ min link rate on the path (bottleneck).

   Read lesson 1.3.1

2. What does store-and-forward force a router to do?
   Stuck? Peek at 1.2.2 Packet switching: store-and-forward, datagrams, statistical multiplexing

   • Packet switching: packets with headers; no reservation; full link rate while sending.
   • Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
   • Datagram: each packet routed independently; may reorder; robust to failures.
   • Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.

   Read lesson 1.2.2

3. 1 µs is how many seconds?
   Stuck? Peek at 0.2.1 Bits, bytes and prefixes: powers of 10 for rates, powers of 2 for sizes

   • 1 B = 8 b. Lower-case b = bit, upper-case B = byte.
   • Rates: k = 10³, M = 10⁶, G = 10⁹ (bps).
   • Sizes: K = 2¹⁰, M = 2²⁰, G = 2³⁰ (bytes) — unless the question says 1000.
   • Time to push out = (size in bits) ÷ (rate in bit/s).
   • ms = 10⁻³ s, µs = 10⁻⁶ s, ns = 10⁻⁹ s.

   Read lesson 0.2.1

Back to the convoy: after the toll booth (transmission), each car still has to drive to the next city (propagation). At the next booth there may be a queue (queuing), and the officer takes a moment to check papers (processing). A message crossing several routers pays all four delays, hop after hop. GATE's favourite numerical asks exactly when the last bit of the last packet arrives.

Five packets, each 8 ms to transmit, cross 3 links (2 routers) by store-and-forward; each link adds 1 ms of travel. Guess the arrival time of the last packet: 5 × 3 × 8 + 3 = 123 ms, or much less?

Much less: 59 ms. Packets pipeline: while packet 2 is on link 1, packet 1 is already on link 2. The first packet needs 3 × 8 + 3 × 1 = 27 ms; each further packet arrives just 8 ms later: 27 + 4 × 8 = 59 ms.

Propagation delay

Default signal speed in copper and fibre: v = 2 × 10⁸ m/s (two-thirds of the speed of light) unless the question gives another value. T_p depends on distance, not on the packet size or the bit rate.

T_t vs T_p — the classic confusion

Transmission = getting all bits onto the link (depends on L and B). Propagation = one bit travelling the link (depends on d and v). The last bit of a packet reaches the far end at T_t + T_p after the first bit left.

Queuing and processing delay

• Processing delay: time a router spends examining the header and deciding where to send (usually µs; given in questions when it matters).
• Queuing delay: time waiting in the output buffer behind other packets. It depends on load: with packets of L bits arriving at a average rate a packets/s on a link of rate R, the traffic intensity L·a/R near 1 makes queues grow large; above 1 they grow without bound.

One packet over h links

Store-and-forward, equal links, no queuing: each link costs a full T_t plus its T_p. One packet arrives after h·T_t + h·T_p (+ processing at each of the h − 1 routers, if given).

N packets pipelined

With N packets on equal-rate links, packets overlap across hops. After the first packet arrives, each further one arrives one T_t later:

If link rates differ, the slowest link sets the spacing: first packet = Σ T_t,i + Σ T_p,i, then one bottleneck T_t per extra packet (when no buffer limits apply).

Putting it together

• A hop costs processing + queuing + transmission (L/B) + propagation (d/v).
• Store-and-forward pipelining: (N + h − 1)·T_t + h·T_p for equal links.
• Unequal links: the slowest link sets the spacing between arrivals.

• Propagation vs transmission: T_p uses distance and signal speed; T_t uses size and bit rate. Mixing them is the most common delay mistake.
• h counts links, not routers: 2 routers between two hosts means h = 3 links.
• Textbooks differ on whether processing delay is charged at the source and destination too. GATE-style questions specify it; when they say "processing delay at each router", charge it once per router on the first packet's path only.

"Booth, road, queue, clerk": transmission, propagation, queuing, processing — and for a convoy over h roads: (N + h − 1) booths plus h roads.

We can now time any multi-hop trip. Next (1.3.3): how many bits are "in the pipe" at once, how long until an answer can come back, and what fraction of the time is a sender that waits for replies actually busy?

1. NAT

   Propagation delay (ms) over 3000 km at 2 × 10⁸ m/s?

   Write your answer before opening the key.

2. NAT

   10 packets of 1000 bits cross 4 links of 1 Mbps, T_p = 0, store-and-forward, nothing else. Total time in ms?

   Write your answer before opening the key.

3. MCQ

   Which delay depends on the distance between the two ends of a link?

   1. Transmission
   2. Propagation
   3. Processing
   4. None
4. NAT

   3 packets of 1000 bits go over links of 10 Mbps, 1 Mbps, 10 Mbps in that order (T_p = 0, store-and-forward). Arrival time of the last packet in ms?

   Write your answer before opening the key.

5. MSQ

   Splitting a long message into smaller packets over several store-and-forward hops (header overhead ignored):

   1. reduces total delay because hops work in parallel
   2. increases total delay because there are more units
   3. gives (N + h − 1)·T_t + h·T_p for equal links
   4. has no effect when there is only one link

• T_p = d / v, v = 2 × 10⁸ m/s default; independent of size and rate.
• Nodal delay = d_proc + d_queue + T_t + T_p.
• One packet, h equal links: h·T_t + h·T_p.
• N packets, h equal links: (N + h − 1)·T_t + h·T_p (+ (h − 1)·d_proc).
• Unequal links: first packet ΣT_t + ΣT_p, then + (N − 1) × max T_t.
• Traffic intensity L·a/R → 1: queues explode.

• propagation delay T_p = d/v
• signal speed 2 × 10⁸ m/s
• queuing delay, traffic intensity
• processing delay
• total (nodal) delay
• multi-hop store-and-forward
• pipelining of packets: (N + h − 1)·T_t + h·T_p

1. T_p formula and default speed?
   Reveal answer

   d / v, v = 2 × 10⁸ m/s.
2. N packets over h equal links?
   Reveal answer

   (N + h − 1)·T_t + h·T_p.
3. Two routers between hosts: h = ?
   Reveal answer

   3 links.
4. Which delay depends on distance?
   Reveal answer

   Propagation only.

• Pipelined store-and-forward: (N + h − 1)·T_t + h·T_p. — N equal packets, h links of the same rate, no queuing; add (h − 1)·processing if routers add a fixed processing delay.
• Unequal link rates: first packet = ΣT_t + ΣT_p; then + (N − 1) × (largest T_t). — enough buffering at the slow link; packets all ready at the start.