Performance formulas

Performance metrics: delay, throughput and link utilisation. 19 formulas for GATE CS Computer Networks, each with when to use it. Each is explained in the topic notes.

All 19 Performance formulas

TRANSMISSION DELAY

T_{t} = \frac{L}{R}

L = packet size in bits, R = link rate in bits per second. Depends on the packet and the rate, not on the length of the wire.

PROPAGATION DELAY

T_{p} = \frac{d}{v}

d = length of the link, v = propagation speed in the medium. Independent of the packet size and the link rate.

ROUND-TRIP TIME (NEGLIGIBLE ACK SIZE)

RTT = 2 T_{p}

For a short probe or acknowledgement whose transmission delay is negligible. If transmission delays matter, add them explicitly.

ONE PACKET OVER N LINKS, STORE-AND-FORWARD

T_{end-to-end} = i = 1 \sum N (\frac{L}{R _{i}} + T_{p, i})

Each router receives the whole packet before forwarding it. Queuing and processing delays are zero unless given. With equal links this is $N (L / R + T_{p})$ .

P PACKETS BACK TO BACK OVER N EQUAL LINKS

T = (N + P - 1) \frac{L}{R} + N T_{p}

All packets have the same size L, are sent without gaps, and no queuing occurs other than waiting behind earlier packets. The first packet needs N transmission times; each later packet finishes one transmission time after the one before.

THROUGHPUT OF A PATH

Throughput = min (R_{1}, R_{2}, \dots, R_{N})

Steady transfer of a long stream over links in series with no other traffic, and a sender window large enough not to be the limit. Delays do not change this rate; they only shift when the stream starts and ends.

FILE OF F BITS IN PACKETS OF L BITS, LINKS IN SERIES

T = \frac{F}{R _{b}} + i \neq = b \sum \frac{L}{R _{i}} + i = 1 \sum N T_{p, i}

Store-and-forward; $R_{b} = min R_{i}$ is the bottleneck rate (link $b$ ); F is a whole number of packets of L bits sent back to back; no other traffic, no processing delay. Every link other than the bottleneck adds one packet transmission time. With equal links and $F = P L$ this is $(N + P - 1) L / R + N T_{p}$ . For a very large F the first term dominates.

BANDWIDTH-DELAY PRODUCT

BDP = R \times T_{p}

Number of bits that fill the link from one end to the other (bits in flight in one direction). Using $R \times RTT$ gives the bits that can be in flight during one round trip.

WINDOW-LIMITED THROUGHPUT

Throughput = min (R, \frac{W}{T _{cycle}})

W = sender window in bits (a TCP window is given in bytes, so multiply by 8). $T_{cycle}$ = time from sending the first bit of a window to receiving its acknowledgement: $T_{t} + 2 T_{p}$ for frames of transmission time $T_{t}$ , or simply RTT when transmission time is negligible. With $W = N L$ this gives $U = N / (1 + 2 a)$ , as below.

STOP-AND-WAIT UTILISATION

U = \frac{T _{t}}{T _{t} + 2 T _{p}} = \frac{1}{1 + 2 a}

No errors, acknowledgement transmission time and processing time negligible. If the ACK has a non-negligible transmission time $T_{a c k}$ , the cycle is $T_{t} + 2 T_{p} + T_{a c k}$ .

EFFECTIVE THROUGHPUT

Throughput = U \times R

R = link rate. Equivalently, one frame of $L$ bits is delivered per cycle: $L / (T_{t} + 2 T_{p})$ .

STOP-AND-WAIT WITH FRAME LOSS

U = \frac{1 - p}{1 + 2 a}

Each frame is lost independently with probability p, acknowledgements are never lost, and every failed attempt costs one full cycle $T_{t} + 2 T_{p}$ (timeout equal to the cycle). The expected number of transmissions per frame is $1/ (1 - p)$ .

USEFUL THROUGHPUT WITH HEADER OVERHEAD

Useful throughput = U \times R \times \frac{L - H}{L}

L = whole frame in bits including the header, H = header bits. Use this only when the question asks for data (payload) throughput; otherwise headers count as transmitted bits.

SLIDING-WINDOW UTILISATION

U = min (1, \frac{N}{1 + 2 a})

N = sender window in frames, $a = T_{p} / T_{t}$ , no errors, ACK transmission negligible. Applies to Go-Back-N and Selective Repeat alike when there are no losses. $N = 1$ gives stop-and-wait.

WINDOW NEEDED TO KEEP THE LINK BUSY

N_{m i n} = ⌈ 1 + 2 a ⌉

Smallest window giving $U = 1$ . Equivalently, the window must cover one full cycle: $N T_{t} \geq T_{t} + 2 T_{p}$ .

GENERAL RULE FOR SEQUENCE NUMBERS

W_{s} + W_{r} \leq 2^{k}

$W_{s}$ = sender window, $W_{r}$ = receiver window, both in frames; k = bits in the sequence number. Go-Back-N has $W_{r} = 1$ , giving $W_{s} \leq 2^{k} - 1$ ; Selective Repeat with $W_{s} = W_{r}$ gives $W_{s} \leq 2^{k - 1}$ .

MAXIMUM WINDOW, GO-BACK-N

N_{m a x}^{GB N} = 2^{k} - 1

k = bits in the sequence number. A window of $2^{k}$ would make a whole new window look like a retransmission of the old one.

MAXIMUM WINDOW, SELECTIVE REPEAT

N_{m a x}^{S R} = 2^{k - 1}

Sender and receiver windows are equal; the two windows together must not exceed the $2^{k}$ numbers.

SEQUENCE BITS FOR A GIVEN WINDOW

k_{GB N} = ⌈ lo g_{2} (N + 1)⌉, k_{S R} = ⌈ lo g_{2} (2 N)⌉

N = sender window size in frames. Use $N_{m i n}$ from the utilisation formula when the question asks for the field that keeps the link fully busy.

Where this was asked: 2022 (1), 2023 (1), 2024 (1), 2025 (1), 2026 (3). See the 7 previous-year questions on Performance. This shows what was asked, not what will be asked.

KEEP GOING

Performance: the notes and 7 solved previous-year questions