GATE CS

Performance metrics

Delay, throughput and link utilisation

Performance metrics describe how long data takes to cross a network and how much of a link's capacity is actually used. For GATE you compute transmission, propagation and end-to-end delay, find throughput from the bottleneck link or the sender's window, and use the bandwidth-delay product to decide how large a sliding window must be to keep a link busy, with the sequence-number limits for Go-Back-N and Selective Repeat.

7 previous-year questions · 7 solved · 5 practice questions

Delays and the conventions used

A packet crossing one link meets four delays. Processing delay is the time a node takes to examine the header and choose the output link. Queuing delay is the wait in the output buffer. Transmission delay is the time to push all the bits of the packet onto the link. Propagation delay is the time one bit takes to travel along the wire. Unless a question gives them, processing and queuing delays are taken as zero.

Conventions to state before calculating

1 byte = 8 bits, so a packet of $L$ bytes has $8 L$ bits.
For data rates, kilo = $1 0^{3}$ and mega = $1 0^{6}$ (a 10 Mbps link sends $1 0^{7}$ bits per second).
For data sizes (packet, frame, file, window), use $2^{10}$ and $2^{20}$ only when the question defines them that way (for example 1 KB = 1024 bytes); rates stay in powers of 10 even then. When the question is silent, these notes use powers of 10 for sizes too.
Propagation speed is whatever the question gives (for example $2 \times 1 0^{8}$ m/s); do not assume the speed of light.
Time units: 1 ms = $1 0^{- 3}$ s, 1 $μ$ s = $1 0^{- 6}$ s. Convert everything to seconds or everything to ms before dividing.

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.

EXAM TIP

Transmission delay is paid once per link, per packet. Propagation delay is paid once per link regardless of packet size. A small packet over a long link is dominated by $T_{p}$ ; a large packet over a slow link is dominated by $T_{t}$ .

Throughput and the bottleneck link

Throughput is the rate at which useful bits are actually delivered end to end, in bits per second. On a path of several links in series, bits cannot arrive faster than the slowest link can carry them. That slowest link is the bottleneck.

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.

If a link of rate $R$ is shared equally among $n$ flows and every flow always has data to send, each flow gets $R / n$ of it. A flow's throughput is then the minimum of its share on every link it crosses.

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.

EXAM TIP

Throughput is limited by the bottleneck rate, but the number of bits in flight is limited by the sender's window. If the window is smaller than $R \times RTT$ , the sender stalls waiting for acknowledgements and the link is underused.

Stop-and-wait and link utilisation

In stop-and-wait the sender transmits one frame, then waits for its acknowledgement before sending the next. Define $a = T_{p} / T_{t}$ , the ratio of the one-way propagation delay to the transmission delay. The link is busy only for $T_{t}$ out of each cycle of $T_{t} + 2 T_{p}$ (frame out, acknowledgement back).

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.

Utilisation falls as $a$ grows, that is, for long links, fast links or short frames. Making the frame longer (larger $T_{t}$ ) raises utilisation, which is why stop-and-wait is acceptable on short slow links but poor on long fast ones.

EXAM TIP

Use RTT consistently: the cycle is $T_{t} + RTT$ with $RTT = 2 T_{p}$ . A frequent slip is using $T_{p}$ instead of $2 T_{p}$ , or computing $a$ with the round-trip time already included and then doubling again.

Sliding window: utilisation and window size

A sliding-window sender may have up to $N$ unacknowledged frames outstanding. After sending a window of $N$ frames, it waits for the first acknowledgement, which arrives $T_{t} + 2 T_{p}$ after the first frame began transmission. In that cycle the sender has used the link for $N T_{t}$ .

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}$ .

WORKED EXAMPLE

A link of 4 Mbps carries frames of 500 bytes. The one-way propagation delay is 7.5 ms. Find the utilisation of stop-and-wait, the utilisation with a window of 8 frames, and the smallest window that keeps the link fully busy. Ignore ACK transmission time and errors.

Solution

Frame size = 500 x 8 = 4000 bits, rate = $4 \times 1 0^{6}$ bit/s, so $T_{t} = 4000/ (4 \times 1 0^{6}) = 1$ ms.
$a = T_{p} / T_{t} = 7.5/1 = 7.5$ , so $1 + 2 a = 16$ .
Stop-and-wait: $U = 1/16 = 6.25%$ , throughput $= 0.0625 \times 4 = 0.25$ Mbps.
Window of 8: $U = min (1, 8/16) = 50%$ , throughput 2 Mbps.
Full utilisation needs $N \geq 16$ , so $N_{m i n} = 16$ frames.

Answer: 6.25% for stop-and-wait, 50% with a window of 8, and a minimum window of 16 frames.

EXAM TIP

If $N \geq 1 + 2 a$ , utilisation is capped at 1 (100%). Never report a value above 1; the answer is simply 1.

Go-Back-N and Selective Repeat

With $k$ bits in the sequence-number field there are $2^{k}$ distinct numbers. The window must be small enough that, after a loss, an old retransmitted frame can never be mistaken for a new one.

Property	Go-Back-N	Selective Repeat
Receiver window	1 frame (accepts only the next in-order frame)	Same size as the sender window (buffers out-of-order frames)
Maximum sender window	$2^{k} - 1$	$2^{k - 1}$
Sequence bits needed for window $N$	smallest $k$ with $2^{k} \geq N + 1$	smallest $k$ with $2^{k - 1} \geq N$ , i.e. $2^{k} \geq 2 N$
Acknowledgement	Cumulative: ACK $n$ confirms everything up to $n$	Individual: each frame is acknowledged on its own
After frame $i$ is lost or times out	Retransmit frame $i$ and every frame sent after it	Retransmit only frame $i$
Out-of-order frame at receiver	Discarded	Buffered, delivered in order once the gap is filled

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.

WORKED EXAMPLE

A sender with window size 6 uses Go-Back-N and then Selective Repeat to send 6 frames numbered 1 to 6. All six are transmitted before any timer expires. Frame 3 is lost on its first transmission only; every other transmission and every acknowledgement arrives. Count the total number of frame transmissions in each protocol.

Solution

First pass: frames 1, 2, 3, 4, 5, 6 are sent, giving 6 transmissions in both protocols (frame 3 is lost).
Go-Back-N: the receiver delivers 1 and 2, discards 4, 5, 6 as out of order, and the timer for frame 3 expires. The sender goes back and retransmits 3, 4, 5, 6, which is 4 more transmissions.
Go-Back-N total = 6 + 4 = 10.
Selective Repeat: frames 4, 5, 6 are buffered and acknowledged individually. Only frame 3 is retransmitted, 1 more transmission.
Selective Repeat total = 6 + 1 = 7.

Answer: Go-Back-N sends 10 frames in total, Selective Repeat sends 7.

EXAM TIP

The GBN limit is $2^{k} - 1$ and the SR limit is $2^{k - 1}$ . For $k = 3$ : GBN window up to 7, SR window up to 4. Stop-and-wait ( $W_{s} = W_{r} = 1$ ) needs only 2 sequence numbers, that is 1 bit. Check which protocol a question names before applying the limit.

Putting it together: a checklist

Procedure for a utilisation or window question

Convert the frame size to bits and the rate to bits per second, then compute $T_{t} = L / R$ .
Compute $T_{p} = d / v$ if distance and speed are given, or read it directly.
Form $a = T_{p} / T_{t}$ and $1 + 2 a$ .
Stop-and-wait: $U = 1/ (1 + 2 a)$ . Window $N$ : $U = min (1, N / (1 + 2 a))$ .
If frame loss or header overhead is given, apply $U = (1 - p) / (1 + 2 a)$ or the factor $(L - H) / L$ .
For the window that keeps the link busy, take the ceiling of $1 + 2 a$ .
For sequence-number bits, apply the GBN rule ( $2^{k} \geq N + 1$ ) or the SR rule ( $2^{k} \geq 2 N$ ) to that window.
Throughput = $U \times R$ ; bits in flight = $R \times T_{p}$ one way.

Quantity	Expression	Unit check
Transmission delay	$L / R$	bits / (bits per second) = s
Propagation delay	$d / v$	m / (m per second) = s
$a$	$T_{p} / T_{t}$	dimensionless
Bandwidth-delay product	$R \times T_{p}$	bits
Utilisation	$min (1, N / (1 + 2 a))$	dimensionless, at most 1

EXAM TIP

Check units at the end. A utilisation above 1 means a unit conversion (bytes versus bits, ms versus s) went wrong. A value of $1 + 2 a$ that is not a whole number is normal: a window is a whole number of frames, so round it up.

PREVIOUS-YEAR QUESTIONS

7 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2023 · GATE CSE 2022

GATE 2026 CS1 Q.45

GATE 2026 · CS1Q.45 · 2 marks · MCQ

Consider the implementation of sliding window protocol over a lossless link, with a window size of $W$ frames, where each frame is of size 1000 bits (including header). The bandwidth of the link is 100 kbps (1k = $1 0^{3}$ ) and the one-way propagation delay is 100 milliseconds. Assume that processing times at the sender and receiver are zero and the transmission time of acknowledgements is also zero. Which one of the following options gives the minimum size of $W$ (in number of frames) required to achieve 100% link utilization?

(A)
10
(B)
21
(C)
20
(D)
11

Answer and solution

GATE 2026 CS1 Q.45: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.45: answer and solution

GATE 2026 CS2 Q.21

GATE 2026 · CS2Q.21 · 1 mark · MCQ

Consider a file of size 4 million bytes being transferred between two hosts connected via a path consisting of three consecutive links of bandwidth 2 Mbps, 500 kbps, and 1 Mbps, respectively. All processing delays and propagation delays are negligible. Assume that there is no other background traffic over the path and no other additional overhead to transfer the file.

Which one of the following is the total time (in seconds) to transfer the file?

Note: 1M=10^6, 1k=10^3

(A)
731
(B)
64
(C)
8
(D)
16

Answer and solution

GATE 2026 CS2 Q.21: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.21: answer and solution

GATE 2026 CS2 Q.65

GATE 2026 · CS2Q.65 · 2 marks · NAT

It is necessary to design a link-layer protocol between two hosts that are directly connected over a lossless link of length 3000 kilometers. Assume that the link bandwidth is $1 0^{8}$ bits per second and that the propagation delay in the link is 5 nanoseconds per meter. Every transmitted data byte is assigned a unique sequence number.

Let $N$ be the minimum number of bits needed for the sequence number field in the protocol header such that

i. the sequence numbers do not wrap around before 60 seconds, and
ii. the maximum utilization of the link is achieved.

The value of $N$ is ______. (answer in integer)

Answer and solution

GATE 2026 CS2 Q.65: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.65: answer and solution

GATE 2025 CS2 Q.36

GATE 2025 · CS2Q.36 · 2 marks · MCQ

Suppose we are transmitting frames between two nodes using Stop-and-Wait protocol. The frame size is 3000 bits. The transmission rate of the channel is 2000 bps (bits/second) and the propagation delay between the two nodes is 100 milliseconds. Assume that the processing times at the source and destination are negligible. Also, assume that the size of the acknowledgement packet is negligible. Which ONE of the following most accurately gives the channel utilization for the above scenario in percentage?

(A)
88.23
(B)
93.75
(C)
85.44
(D)
66.67

Answer and solution

GATE 2025 CS2 Q.36: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.36: answer and solution

GATE 2024 CS1 Q.36

GATE 2024 · CS1Q.36 · 2 marks · MCQ

Consider a network path P—Q—R between nodes P and R via router Q. Node P sends a file of size $1 0^{6}$ bytes to R via this path by splitting the file into chunks of $1 0^{3}$ bytes each. Node P sends these chunks one after the other without any wait time between the successive chunk transmissions. Assume that the size of extra headers added to these chunks is negligible, and that the chunk size is less than the MTU.

Each of the links P—Q and Q—R has a bandwidth of $1 0^{6}$ bits/sec, and negligible propagation latency. Router Q immediately transmits every packet it receives from P to R, with negligible processing and queueing delays. Router Q can simultaneously receive on link P—Q and transmit on link Q—R.

Assume P starts transmitting the chunks at time $t = 0$ .
Which one of the following options gives the time (in seconds, rounded off to 3 decimal places) at which R receives all the chunks of the file?

(A)
8.000
(B)
8.008
(C)
15.992
(D)
16.000

Answer and solution

GATE 2024 CS1 Q.36: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.36: answer and solution

GATE 2023 CS Q.17

GATE 2023 · CSQ.17 · 1 mark · MCQ

Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.

(A)
Longer link length and lower transmission rate
(B)
Longer link length and higher transmission rate
(C)
Shorter link length and lower transmission rate
(D)
Shorter link length and higher transmission rate

Answer and solution

GATE 2023 CS Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.17: answer and solution

GATE 2022 CS Q.59

GATE 2022 · CSQ.59 · 2 marks · NAT

Consider a 100 Mbps link between an earth station (sender) and a satellite (receiver) at an altitude of 2100 km. The signal propagates at a speed of $3 \times 1 0^{8}$ m/s. The time taken (in milliseconds, rounded off to two decimal places) for the receiver to completely receive a packet of 1000 bytes transmitted by the sender is ______.

Answer and solution

GATE 2022 CS Q.59: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.59: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

A packet of 1500 bytes is sent over a path of 3 links in series, each of rate 10 Mbps (kilo = $1 0^{3}$ , mega = $1 0^{6}$ , 1 byte = 8 bits) and each with a one-way propagation delay of 2 ms. Routers use store-and-forward. Ignore queuing and processing delays. What is the end-to-end delay of the packet, in ms?

Answer and solution

Answer: $9.6$ (accepted range $\pm 0.01$ )

L = 1500 x 8 = 12000 bits; R = $1 0^{7}$ bit/s, so $T_{t} = 12000/1 0^{7} = 1.2$ ms per link.
Three links: transmission total = 3 x 1.2 = 3.6 ms.
Propagation total = 3 x 2 = 6 ms.
End-to-end delay = 3.6 + 6 = 9.6 ms.

PRACTICE 22 marks · NAT

A stop-and-wait protocol runs over a 1 Mbps link (mega = $1 0^{6}$ ). Each frame is 1000 bytes and the one-way propagation delay is 20 ms. Acknowledgement transmission time and processing time are negligible and there are no errors. What is the throughput in kbps (kilo = $1 0^{3}$ , 1 byte = 8 bits)? Give your answer to two decimal places.

Answer and solution

Answer: $166.67$ (accepted range $\pm 0.1$ )

L = 8000 bits, so $T_{t} = 8000/1 0^{6} = 8$ ms.
Cycle = $T_{t} + 2 T_{p} = 8 + 40 = 48$ ms.
$U = 8/48 = 1/6$ .
Throughput = $U \times R = (1/6) \times 1000$ kbps = 166.67 kbps.

PRACTICE 32 marks · MCQ

A Go-Back-N sender uses a 2 Mbps link and frames of 1000 bits (mega = $1 0^{6}$ ). The one-way propagation delay is 12 ms. ACK transmission time is negligible. What is the minimum number of bits in the sequence-number field so that the sender can keep the link fully utilised?

(A)
5
(B)
6
(C)
7
(D)
8

Answer and solution

Answer: (B)

$T_{t} = 1000/ (2 \times 1 0^{6}) = 0.5$ ms; $T_{p} = 12$ ms.
$a = 12/0.5 = 24$ , so $1 + 2 a = 49$ and the window needed is $N = 49$ .
Go-Back-N needs $2^{k} \geq N + 1 = 50$ .
$2^{5} = 32 < 50$ and $2^{6} = 64 \geq 50$ , so $k = 6$ .

PRACTICE 42 marks · MSQ

Which of the following statements are correct?

(A)
With 4-bit sequence numbers, the largest sender window in Selective Repeat is 8.
(B)
With 4-bit sequence numbers, the largest sender window in Go-Back-N is 16.
(C)
In Go-Back-N, the receiver discards a frame that arrives out of order.
(D)
In Selective Repeat, the receiver window has size 1.

Answer and solution

Answer: (A), (C)

SR maximum window is $2^{k - 1} = 2^{3} = 8$ , so A is correct.
GBN maximum window is $2^{k} - 1 = 15$ , not 16, so B is incorrect.
A Go-Back-N receiver accepts only the next expected frame and discards any other, so C is correct.
A Selective Repeat receiver has a window equal to the sender's, to buffer out-of-order frames, so D is incorrect.

PRACTICE 51 mark · NAT

A link has a rate of 100 Mbps (mega = $1 0^{6}$ ) and a one-way propagation delay of 5 ms. How many kilobits (kilo = $1 0^{3}$ ) can be in flight on the link in one direction at one instant when it is completely full?

Answer and solution

Answer: $500$ (accepted range $\pm 0.01$ )

Bandwidth-delay product = $R \times T_{p} = 1 0^{8} \times 0.005$ bits.
= 500000 bits.
In kilobits: 500000 / 1000 = 500.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

performance metrics

Preparing in Kolkata? IAE Academy's course for GATE CSE.