Numerical Problems in Computer Networks
Delay Analysis
Read aloud is unavailable in this browser.
Understanding Why Packets Take Time
Every packet traversing a network experiences delay. From the moment an application generates data to when it arrives at its destination, time passes—sometimes microseconds, sometimes seconds. Understanding the sources and magnitudes of these delays is essential for network engineers, system designers, and anyone preparing for technical interviews.
Why delay analysis matters: Delay directly impacts user experience, application performance, and system design decisions. A video call tolerates up to 150ms one-way delay before quality suffers. Financial trading systems measure competitiveness in microseconds. Content delivery networks are architected entirely around minimizing latency. Knowing how to calculate, predict, and optimize delay is a core networking skill.
By the end of this page, you will: (1) Decompose end-to-end delay into its four fundamental components, (2) Calculate each delay type for various network scenarios, (3) Apply queuing theory to estimate waiting times under load, (4) Analyze delay for multi-hop paths, and (5) Solve complex interview problems combining multiple delay factors.
The Four Components of Network Delay
End-to-end delay in a network is the sum of four distinct components. Each has different characteristics, different causes, and different optimization strategies.
$$D_{total} = D_{processing} + D_{queuing} + D_{transmission} + D_{propagation}$$
Understanding what each component represents and when each dominates is crucial for both problem-solving and network design.
| Delay Type | Definition | Formula | Depends On | Typical Range |
|---|---|---|---|---|
| Processing Delay (d_proc) | Time to examine packet header, determine output link, check errors | Fixed per device | Processor speed, lookup complexity, error checking | μs to ms |
| Queuing Delay (d_queue) | Time waiting in buffer for transmission | Varies with load | Traffic intensity, queue length, arrival pattern | 0 to seconds |
| Transmission Delay (d_trans) | Time to push all bits onto the link | L / R | Packet length (L), Link bandwidth (R) | μs to ms |
| Propagation Delay (d_prop) | Time for bit to travel from sender to receiver | d / s | Distance (d), Propagation speed (s) | μs to ms |
The most common mistake in delay problems is confusing transmission and propagation delay. Transmission delay is about pushing bits onto the wire (depends on bandwidth). Propagation delay is about bits traveling through the wire (depends on distance). A thick straw (high bandwidth) reduces transmission delay but doesn't make the liquid flow faster (propagation).
Transmission Delay In Depth
Transmission delay is the time required to push (transmit) all bits of a packet onto the outgoing link. Think of it as emptying a bucket through a pipe—the time depends on the bucket size (packet length) and pipe diameter (bandwidth).
$$D_{transmission} = \frac{L}{R}$$
Where:
- L = Packet length in bits
- R = Link bandwidth (transmission rate) in bits per second
Key Properties of Transmission Delay:
- Directly proportional to packet size: Double the packet, double the transmission delay
- Inversely proportional to bandwidth: Double the bandwidth, halve the transmission delay
- Independent of distance: A 1500-byte packet takes the same transmission time on a 1-meter or 1000-km link (same bandwidth assumed)
- Occurs at every hop: Each router must transmit the packet anew onto the outgoing link
Example 1: Transmission Delay Comparison
Compare transmission delays across different link speeds for a 1500-byte packet.
Packet size: 1500 bytes = 12,000 bits
Link speeds: 10 Mbps, 100 Mbps, 1 Gbps, 10 Gbps, 100 Gbps10 Mbps: 12000 / 10^7 = 1.2 ms
100 Mbps: 12000 / 10^8 = 0.12 ms = 120 μs
1 Gbps: 12000 / 10^9 = 12 μs
10 Gbps: 12000 / 10^10 = 1.2 μs
100 Gbps: 12000 / 10^11 = 0.12 μs = 120 nsExplanation
Each 10x increase in bandwidth produces a 10x reduction in transmission delay. At modern datacenter speeds (100 Gbps), transmission delay becomes negligible compared to propagation delay and processing overhead. This is why high-bandwidth links feel 'instantaneous' for single packets.
Example 2: File Transfer Time
How long to transfer a 1 GB file over different connections?
File size: 1 GB = 8 × 10^9 bits
Connections: 100 Mbps, 1 Gbps, 10 Gbps
Assume: Pure transmission time, ignore other delays100 Mbps: 8×10^9 / 10^8 = 80 seconds
1 Gbps: 8×10^9 / 10^9 = 8 seconds
10 Gbps: 8×10^9 / 10^10 = 0.8 secondsExplanation
For bulk transfers, transmission delay dominates. A home internet upgrade from 100 Mbps to 1 Gbps makes a 10x difference in download times. However, these calculations assume sustained throughput—real transfers are often limited by TCP dynamics, server capacity, or bottleneck links.
Propagation Delay In Depth
Propagation delay is the time for a single bit to travel from source to destination through the physical medium. It's determined by physics—the speed of signal propagation in the medium—and is independent of packet size or bandwidth.
$$D_{propagation} = \frac{d}{s}$$
Where:
- d = Distance between sender and receiver
- s = Propagation speed in the medium
Propagation Speeds in Different Media:
The speed of light in vacuum is c = 3 × 10⁸ m/s. In physical media, signals travel slower:
| Medium | Propagation Speed | As Fraction of c | Notes |
|---|---|---|---|
| Vacuum / Air (RF) | 3 × 10⁸ m/s | 1.0c | Satellite, microwave links |
| Fiber Optic | 2 × 10⁸ m/s | 0.67c | Refractive index ~1.5 |
| Copper (Cat 6) | 2.3 × 10⁸ m/s | 0.77c | Twisted pair cabling |
| Coaxial Cable | 2.3 × 10⁸ m/s | 0.77c | Cable TV, older networks |
The Tyranny of Distance
Propagation delay sets a fundamental lower bound on latency that no amount of bandwidth can overcome. This has profound implications:
| Distance | Medium | One-way Delay | Round-trip Time |
|---|---|---|---|
| 1 km (building) | Fiber | 5 μs | 10 μs |
| 100 km (city) | Fiber | 0.5 ms | 1 ms |
| 1000 km (country) | Fiber | 5 ms | 10 ms |
| 15,000 km (intercontinental) | Fiber | 75 ms | 150 ms |
| 36,000 km (geostationary satellite) | Vacuum | 120 ms | 240 ms |
| 385,000 km (Earth-Moon) | Vacuum | 1.28 s | 2.56 s |
This is why:
- Financial traders co-locate servers in exchange datacenters (every microsecond matters)
- CDNs place content at the edge (reduce distance to users)
- Geostationary satellites have inherent latency limitations
- Real-time gaming over satellite connections is problematic
For fiber optic: 1 km ≈ 5 μs. For quick estimates, divide distance in km by 200 to get one-way delay in milliseconds. New York to London (~5,500 km undersea fiber) ≈ 27.5 ms one-way, 55 ms RTT. Real-world measurements show ~65-75 ms RTT due to non-straight paths and switching delays.
Processing Delay In Depth
Processing delay is the time a router or switch needs to:
- Receive the entire packet
- Check the header for errors (CRC verification)
- Examine the destination address
- Perform table lookup to determine the output interface
- Update any fields (TTL decrement, checksum recalculation)
- Forward to the appropriate output queue
Factors Affecting Processing Delay:
| Factor | Impact | Typical Delay |
|---|---|---|
| Routing table size | Larger tables = longer lookups | ns to μs |
| Lookup algorithm | Hash vs tree vs linear | ns to μs |
| Hardware vs software | ASIC vs CPU-based | 100 ns vs 10 μs |
| Additional features | ACLs, NAT, deep packet inspection | μs to ms |
| Error checking | CRC verification | Adds ~1 μs per KB |
| Encryption/decryption | If terminating VPN/TLS | 10-1000 μs |
Store-and-Forward vs Cut-Through Switching
Store-and-Forward: The switch receives the entire frame, checks the CRC, then forwards. Processing delay includes the entire frame reception time plus lookup time.
Total delay = Reception time + Processing + Transmission time = L/R (incoming) + d_proc + L/R (outgoing)
Cut-Through: The switch begins forwarding as soon as the destination address is read (first 14 bytes of Ethernet). No CRC check.
Total delay ≈ Header reception + Processing + Transmission time ≈ 14×8/R + d_proc + L/R (outgoing)
For a 1500-byte frame on Gigabit Ethernet:
- Store-and-Forward: 12 μs + 1 μs + 12 μs = 25 μs
- Cut-Through: 0.1 μs + 1 μs + 12 μs ≈ 13 μs
In most interview problems, processing delay is either given as a constant (e.g., '1 ms per hop') or stated to be negligible. When not specified, you can mention it exists but focus on the dominant delays (usually transmission and propagation for simple problems, queuing for loaded systems).
Queuing Delay and Traffic Intensity
Queuing delay is the most complex delay component because it varies with time and network load. A packet may experience zero queuing delay if it arrives at an empty queue, or substantial delay if many packets are waiting.
Traffic Intensity (ρ)
The behavior of queuing delay is governed by traffic intensity:
$$\rho = \frac{La}{R}$$
Where:
- L = Average packet length (bits)
- a = Average packet arrival rate (packets/second)
- R = Link bandwidth (bits/second)
- La = Arrival rate in bits/second
Traffic intensity represents the ratio of arrival rate to service rate. Its value determines queue behavior:
| Traffic Intensity (ρ) | Queue Behavior | Average Delay | Practical Interpretation |
|---|---|---|---|
| ρ ≈ 0 | Queue almost always empty | ≈ 0 | Very light load, wasteful underutilization |
| ρ < 0.5 | Short queues, quick service | Low, stable | Light load, good performance margin |
| 0.5 < ρ < 0.8 | Moderate queuing | Manageable | Normal operating range |
| 0.8 < ρ < 1.0 | Queue builds rapidly | High and variable | Approaching saturation, risky |
| ρ ≥ 1.0 | Queue grows without bound | → ∞ | Unstable, packets will be dropped |
M/M/1 Queue Model
For mathematical analysis, we often use the M/M/1 queue model:
- First M: Arrivals follow a Poisson process (Markovian)
- Second M: Service times are exponentially distributed (Markovian)
- 1: Single server (one output link)
For M/M/1 queues, the average queuing delay is:
$$D_{queue} = \frac{\rho}{\mu(1-\rho)} = \frac{L}{R-La}$$
Where μ = R/L is the service rate.
Average number of packets in queue: $$N_{queue} = \frac{\rho^2}{1-\rho}$$
Average time in system (queue + service): $$D_{system} = \frac{1}{\mu(1-\rho)} = \frac{L}{R-La}$$
Example 3: Queuing Delay Calculation
Calculate average queuing delay for a router interface.
Link bandwidth: 100 Mbps
Average packet size: 1000 bytes = 8000 bits
Packet arrival rate: 10,000 packets/secondTraffic intensity:
ρ = La/R = (8000 × 10000) / 100,000,000
= 80,000,000 / 100,000,000 = 0.8
Service rate:
μ = R/L = 100,000,000 / 8000 = 12,500 packets/s
Average queuing delay:
D_queue = ρ / (μ(1-ρ))
= 0.8 / (12500 × 0.2)
= 0.8 / 2500 = 0.32 msExplanation
At 80% utilization, packets wait an average of 0.32 ms in the queue. If arrival rate increased to 11,000 packets/s (ρ = 0.88), delay would jump to 0.8/(12500×0.12) = 0.533 ms—a 67% increase for just 10% more traffic. This nonlinear behavior near saturation is why network engineers maintain utilization below 80%.
Queuing delay grows exponentially as ρ approaches 1. At ρ=0.9, delay is 9x higher than at ρ=0.5. At ρ=0.99, it's 99x higher. This 'cliff effect' is why seemingly small increases in traffic can cause dramatic performance degradation. Network capacity planning must account for this nonlinearity.
Multi-Hop Path Delay Analysis
Real network paths traverse multiple hops. Each hop contributes its own components to end-to-end delay.
Total End-to-End Delay
For a path with N links (N+1 nodes including source and destination):
$$D_{end-to-end} = \sum_{i=1}^{N}(d_{proc_i} + d_{queue_i} + d_{trans_i} + d_{prop_i})$$
Simplifications for Interview Problems
When all links have the same bandwidth R and all packets have size L:
$$D_{end-to-end} = N \times d_{proc} + \sum_{i=1}^{N}d_{queue_i} + N \times \frac{L}{R} + \sum_{i=1}^{N}d_{prop_i}$$
If processing and queuing are negligible:
$$D_{end-to-end} = N \times \frac{L}{R} + \frac{d_{total}}{s}$$
Where d_total is the total distance and s is propagation speed.
Example 4: Cross-Country Packet Delay
Calculate end-to-end delay for a packet traversing the United States.
Path: 15 router hops
Total fiber distance: 4000 km
All links: 10 Gbps
Packet size: 1500 bytes
Propagation speed: 2 × 10^8 m/s
Processing delay: 10 μs per hop
Queuing delay: Negligible (light load)Transmission delay per hop:
d_trans = (1500 × 8) / 10^10 = 1.2 μs
Total transmission = 15 × 1.2 = 18 μs
Propagation delay:
d_prop = 4,000,000 / (2 × 10^8) = 20 ms
Processing delay:
d_proc = 15 × 10 μs = 150 μs
Total end-to-end delay:
D = 18 μs + 20,000 μs + 150 μs ≈ **20.17 ms**Explanation
Propagation delay (20 ms) completely dominates. Even with 15 hops of processing and transmission, they add only 168 μs—less than 1% of total delay. For long-distance paths, propagation is king. This is why coast-to-coast RTT in the US is typically 60-80 ms (including ACK processing and real-world routing).
Example 5: LAN Packet Delay
Calculate delay for a packet within a datacenter.
Path: 3 switch hops (ToR → Aggregation → Core → Aggregation → ToR)
Total distance: 300 meters
All links: 100 Gbps
Packet size: 1500 bytes
Processing: 1 μs per switch
Queuing: 2 μs average per switchTransmission delay per hop (5 links):
d_trans = 12000 / 10^11 = 0.12 μs
Total transmission = 5 × 0.12 = 0.6 μs
Propagation delay:
d_prop = 300 / (2 × 10^8) = 1.5 μs
Processing and queuing:
d_proc + d_queue = 4 × (1 + 2) = 12 μs
Total delay:
D = 0.6 + 1.5 + 12 = **14.1 μs**Explanation
In datacenter networks, processing and queuing dominate because distances are short and bandwidths are high. This is why datacenter switching focuses on low-latency ASIC designs and minimal buffering. A 14 μs hop adds up quickly when distributed systems make hundreds of internal calls per user request.
First Bit vs Last Bit Delay
Interview problems sometimes ask for the time until the first bit arrives versus when the last bit arrives. This distinction is important for understanding pipelining in networks.
Single Link Analysis
Time for first bit to arrive at destination: $$T_{first} = D_{propagation} = \frac{d}{s}$$
Time for last bit to arrive at destination: $$T_{last} = D_{transmission} + D_{propagation} = \frac{L}{R} + \frac{d}{s}$$
The last bit needs the full transmission time plus propagation.
Multi-Hop Pipelining Effect
With store-and-forward switching, each router waits for the entire packet before forwarding. For N links:
$$T_{last} = N \times \frac{L}{R} + \frac{d_{total}}{s}$$
With cut-through switching (forward after receiving header), the packet 'pipelines' through the network:
$$T_{last} \approx \frac{L}{R} + N \times \frac{Header}{R} + \frac{d_{total}}{s}$$
The distinction grows significant with many hops and large packets.
Example 6: Store-and-Forward vs Cut-Through
Compare latencies for a 1500-byte packet over 10 switches.
Packet size: 1500 bytes
Header size: 14 bytes (Ethernet)
Link speed: 10 Gbps
Number of switches: 10
Total distance: 1 km (short for clarity)
Propagation speed: 2 × 10^8 m/sStore-and-Forward:
T = 10 × (12000/10^10) + (1000/2×10^8)
= 10 × 1.2 μs + 5 μs
= 12 + 5 = **17 μs**
Cut-Through:
T ≈ (12000/10^10) + 10×(112/10^10) + 5 μs
= 1.2 μs + 0.11 μs + 5 μs
≈ **6.3 μs**Explanation
Cut-through saves ~11 μs (63% reduction) by forwarding before the full packet arrives. This advantage is why high-frequency trading networks and latency-sensitive datacenters prefer cut-through switching. However, cut-through cannot detect CRC errors, so corrupted packets propagate further before being discarded.
KEEP LEARNING
There’s more to understand.
You’re reading the introduction. Create a free account to read the complete lesson, save notes and keep track of your progress.