Numerical Problems in Computer Networks

Network efficiency is the cornerstone of all quantitative network analysis. Whether you're designing a new network infrastructure, optimizing an existing system, or answering interview questions, the ability to calculate and reason about efficiency determines your effectiveness as a network engineer.

Why efficiency matters: Every network resource—bandwidth, processing power, time—is finite and expensive. Understanding how efficiently a protocol or system uses these resources allows you to make informed decisions about network design, identify bottlenecks, and predict performance under varying conditions. In interviews at top technology companies, efficiency calculations are fundamental because they reveal whether a candidate truly understands network behavior at a quantitative level.

Before diving into calculations, we must establish precise definitions. In networking, "efficiency" can refer to several distinct but related concepts:

Transmission Efficiency measures how much of the transmitted data is actual payload versus overhead. When you send a frame, packet, or segment, only a portion carries user data—the rest consists of headers, trailers, checksums, and other protocol overhead.

Channel Utilization measures what fraction of the available channel capacity is actually being used for productive transmission. A channel might be idle due to propagation delay, acknowledgment wait times, or protocol constraints.

Protocol Efficiency combines both concepts—how well a protocol converts raw channel capacity into delivered user data.

Transmission efficiency quantifies the overhead cost of sending data through a network. Every protocol layer adds headers (and sometimes trailers), which consume bandwidth but carry no user payload.

The Basic Formula

$$\eta_{transmission} = \frac{D}{D + H}$$

Where:

• D = Data payload size (the actual user data)
• H = Total header/overhead size (all protocol headers combined)

This formula applies at any layer. You can calculate the efficiency of Ethernet framing, IP encapsulation, TCP segmentation, or the entire protocol stack.

Header Sizes Across the Protocol Stack

To calculate transmission efficiency, you must know the fixed and variable overhead at each layer. Here are the standard header sizes you should memorize:

Let's work through progressively complex examples to build your calculation skills.

Channel utilization measures how effectively we use the available transmission capacity over time. Unlike transmission efficiency (which is about overhead), channel utilization is about timing—how much of the time is the channel actively carrying useful data?

The Stop-and-Wait Problem

Consider the simplest reliable transmission protocol: stop-and-wait. The sender transmits one frame, then waits for an acknowledgment before sending the next frame. During the wait, the channel sits idle.

For stop-and-wait, utilization is:

$$U = \frac{T_{trans}}{T_{trans} + 2 \times T_{prop} + T_{proc}}$$

Where:

• T_trans = Transmission time = Frame size / Bandwidth
• T_prop = Propagation delay = Distance / Signal speed
• T_proc = Processing time (often negligible)

The factor of 2 accounts for the round trip: data travels to receiver, ACK travels back.

The 'a' Parameter

Network theorists define a dimensionless parameter a that captures the relationship between propagation delay and transmission time:

$$a = \frac{T_{prop}}{T_{trans}}$$

This parameter is crucial because:

• When a < 1: Transmission time dominates. The frame is still being transmitted when the first bit arrives at the receiver.
• When a > 1: Propagation delay dominates. The entire frame leaves the sender before the first bit reaches the receiver—the 'pipe' is longer than one frame.
• When a >> 1: Stop-and-wait becomes extremely inefficient because most time is spent waiting.

Using 'a', stop-and-wait utilization simplifies to:

$$U_{stop-and-wait} = \frac{1}{1 + 2a}$$

Sliding window protocols (Go-Back-N and Selective Repeat) overcome stop-and-wait's limitations by allowing multiple frames in flight simultaneously.

Go-Back-N Utilization

With window size W, the sender can transmit up to W frames before waiting for an ACK.

If W ≥ 1 + 2a: The sender never has to wait; utilization = 100%

If W < 1 + 2a: The sender exhausts the window before receiving ACKs.

$$U_{GBN} = \begin{cases} 1 & \text{if } W \geq 1 + 2a \ \frac{W}{1 + 2a} & \text{if } W < 1 + 2a \end{cases}$$

Accounting for Frame Errors

When the channel has bit error rate P (probability a frame is corrupted), efficiency decreases because corrupted frames must be retransmitted.

For Go-Back-N with frame error probability P:

$$U_{GBN} = \frac{(1 - P)}{(1 + 2a)} \times \frac{1}{1 + P(W-1)} \text{ (simplified)}$$

Or more precisely: $$U_{GBN} = \frac{W(1-P)}{(1 + 2a)(1 - P + WP)}$$

For Selective Repeat (SR), which only retransmits bad frames: $$U_{SR} = \frac{W(1-P)}{1 + 2a}$$

Selective Repeat is more efficient under error conditions because it doesn't retransmit correctly received frames.

Classic Ethernet using CSMA/CD (Carrier Sense Multiple Access with Collision Detection) has a theoretical efficiency limit based on the collision domain parameters.

The CSMA/CD Efficiency Formula

The maximum efficiency of CSMA/CD under ideal conditions is:

$$\eta_{CSMA/CD} = \frac{1}{1 + \frac{6.44 \times a}{N}}$$

Where:

• a = T_prop / T_trans (same 'a' parameter as before)
• N = Number of stations with data to send

As N → ∞ (heavy load), this simplifies to: $$\eta_{max} = \frac{1}{1 + 6.44a}$$

Why 6.44?

The constant 6.44 emerges from the analysis of backoff behavior. After a collision, stations use exponential backoff to reduce collision probability. The constant accounts for the expected number of slot times wasted in contention before a successful transmission.

Practical Implications

For CSMA/CD to work correctly:

• Minimum frame size = 2 × Bandwidth × Propagation delay
• For 10 Mbps Ethernet over 2500m: 2 × 10⁷ × (2500/2×10⁸) = 250 bits → rounded to 512 bits (64 bytes)

This is why Ethernet has a 64-byte minimum frame size—to ensure collisions are detected before transmission completes.

Token-based access methods and polling systems have different efficiency characteristics than contention-based protocols.

Token Ring Efficiency

In a token ring network, stations can only transmit when holding the token. The maximum efficiency depends on whether we use single token or multiple token operation.

Single Token Operation (immediate release after frame transmission): $$\eta = \frac{1}{1 + \frac{a}{N}}$$

Multiple Token Operation (token released after receiving ACK): $$\eta = \frac{1}{1 + \frac{a + T_{token}/T_{trans}}{N}}$$

Where T_token is the token transmission time (typically 3 bytes = 24 bits).

Polling Efficiency

In a polling system, a central controller queries each station in turn. The efficiency loss comes from:

1. Poll message overhead: Each poll consumes bandwidth
2. Walk time: Time to cycle through all stations
3. Propagation delays: Multiple round trips

$$\eta_{polling} = \frac{NT_{data}}{NT_{data} + N(T_{poll} + 2T_{prop})}$$

Where:

• N = Number of stations
• T_data = Data transmission time per station (average)
• T_poll = Poll message transmission time
• T_prop = Propagation delay (controller to station)

When facing efficiency problems in interviews or exams, use this systematic approach:

Step 1: Identify the efficiency type

• Headers and overhead → Transmission efficiency
• Waiting for ACKs → Channel utilization with stop-and-wait or sliding window
• Contention and collisions → CSMA/CD efficiency
• Token passing → Token ring efficiency

Step 2: Extract parameters

• Bandwidth (B or R) - usually in bps or Mbps
• Frame/packet size (L) - in bytes or bits (be careful with units!)
• Distance or propagation delay
• Window size (W) if sliding window
• Number of stations (N) if multiple access

Step 3: Calculate intermediate values

• T_trans = L / B
• T_prop = Distance / Speed (or given directly)
• a = T_prop / T_trans
• BDP = B × RTT

Efficiency calculations are fundamental to network analysis. Let's consolidate what we've covered: