GATE CSE Computer Networks Formula Sheet: Subnetting, Windows, TCP

Q: How many sequence number bits do Go-Back-N and Selective Repeat need?

Go-Back-N needs a sender window of at most 2ᵐ - 1, so m = ⌈ log₂(W + 1) ⌉. Selective Repeat needs a window of at most 2ᵐ⁻¹, so m = ⌈ log₂ W ⌉ + 1. For a window of 21 frames, Go-Back-N needs 5 bits and Selective Repeat needs 6. Mixing up the two limits is a common trap.

Q: How many usable hosts are in a /27 subnet?

A /27 block has 2³²⁻²⁷ = 32 addresses. The network address and the broadcast address cannot be given to hosts, so 30 are usable. Blocks are aligned to their size, so a /27 always starts at a multiple of 32 in the last octet. Read whether a question asks for addresses or usable hosts.

Q: What is the formula for stop-and-wait efficiency?

Efficiency = 1/(1 + 2a), where a is the propagation delay divided by the transmission delay of one frame. A sliding window of W frames raises it to W divided by (1 + 2a), capped at 1. If the acknowledgement takes noticeable time to transmit, add its transmission time to the cycle as well.

By MD ANISH AHAMADUpdated 4 Oct 20268 min read

GATE CSE Computer Networks Formula Sheet: Subnetting, Windows, TCP

Most Computer Networks questions in GATE CSE are numerical, and they come from a short set of templates: delays, sliding windows, subnetting, fragmentation, error detection and the TCP congestion window. This sheet goes deeper than the general GATE CSE formula sheet. Every formula has a one-line worked example and the trap that costs marks.

In this guide

Key takeaways
The terms this sheet uses
Delays and the bandwidth-delay product
Stop-and-wait and sliding windows
Medium access: CSMA/CD and ALOHA
Error detection: CRC, checksum and Hamming
IPv4 subnetting and CIDR
IPv4 fragmentation
TCP: congestion window, throughput and numbering
Quick revision

Key takeaways

Transmission delay is frame size over link rate; propagation delay is distance over signal speed. Every efficiency formula is built from these two.
Go-Back-N allows a window of $2^m - 1$ ; Selective Repeat allows only $2^{m-1}$ .
A $/p$ block has $2^{32-p}$ addresses and $2^{32-p} - 2$ usable hosts.
Fragment offsets count 8-byte units, so data per fragment is rounded down to a multiple of 8.
CRC is division with XOR; the remainder has as many bits as the generator's degree.
On a timeout TCP halves the current congestion window into ssthresh and restarts from 1 MSS.

The terms this sheet uses

Transmission delay is the time to push all bits of a frame onto the link. Propagation delay is the time one bit takes to travel the length of the link.
RTT (round-trip time) is the time for a frame to go out and an acknowledgement to come back. The bandwidth-delay product (BDP) is how many bits fit "in flight" in that time.
A window is the number of frames a sender may have unacknowledged. The window is limited by the number of sequence-number bits $m$ .
A prefix length $/p$ says how many leading bits of an IPv4 address form the network part. The MTU is the largest IP packet a link can carry.
cwnd (congestion window) and ssthresh (slow-start threshold) are the two numbers TCP keeps to decide how fast to send. MSS is the largest segment of data.

Mbps means $10^{6}$ bits per second unless a question says otherwise, and sizes in bytes must be multiplied by 8.

Delays and the bandwidth-delay product

Each delay answers a different question: how long to put the frame on the wire, and how long for it to cross.

Formula	One-line example	Watch out for
$t_{\text{trans}} = L / R$	1000 B at 10 Mbps: $8000 / 10^{7} = 0.8$ ms	Bytes to bits
$t_{\text{prop}} = d / v$	2000 km at $2 \times 10^{8}$ m/s: 10 ms	km to m
$\text{BDP} = R \times \text{RTT}$	$10^{7} \times 0.02 = 2 \times 10^{5}$ bits	RTT, not one-way delay
Store-and-forward: $\displaystyle (n + k - 1)\,\dfrac{L}{R} + \sum t_{\text{prop}}$	5 packets, 3 links, $L/R = 1$ ms, no propagation: 7 ms	Propagation is added once per link, not per packet

Stop-and-wait and sliding windows

Let $a = t_{\text{prop}} / t_{\text{trans}}$ . A sender that waits for each acknowledgement uses the link for one frame time out of every $1 + 2a$ frame times. A window of $W$ frames fills more of that cycle:

\eta_{\text{SW}} = \frac{1}{1 + 2a}, \qquad \eta_{W} = \min\!\left(1, \frac{W}{1 + 2a}\right)

Worked example. With $t_{\text{trans}} = 1$ ms and $t_{\text{prop}} = 10$ ms, $a = 10$ and $1 + 2a = 21$ . Stop-and-wait reaches only $1/21 \approx 4.76\%$ . A window of 21 frames keeps the link fully busy.

Formula	One-line example	Watch out for
Go-Back-N: $W \le 2^{m} - 1$ , so $m = \lceil \log_2(W + 1) \rceil$	$W = 21$ : $\lceil \log_2 22 \rceil = 5$ bits	Receiver window is 1
Selective Repeat: $W \le 2^{m-1}$ , so $m = \lceil \log_2 W \rceil + 1$	$W = 21$ : $5 + 1 = 6$ bits	Needs $W_s + W_r \le 2^{m}$
Throughput $\displaystyle = \dfrac{L}{t_{\text{trans}} + 2t_{\text{prop}}}$	1000 B every 21 ms: about 381 kbps	Add $t_{\text{ack}}$ if the ACK has a size

Trap: Writing $2^{m}$ for the Go-Back-N window, or $2^{m} - 1$ for Selective Repeat, is one of the most repeated slips in this subject. Say the two limits aloud until they stick.

Medium access: CSMA/CD and ALOHA

A sender must still be transmitting when news of a collision returns, so the frame must last at least one round trip:

L_{\min} = 2\,t_{\text{prop}}\,R = \frac{2dR}{v}

Worked example. For $d = 2$ km, $v = 2 \times 10^{8}$ m/s and $R = 100$ Mbps, $t_{\text{prop}} = 10\ \mu$ s, so $L_{\min} = 2 \times 10^{-5} \times 10^{8} = 2000$ bits, which is 250 bytes.

For ALOHA, pure throughput is $S = G e^{-2G}$ with a maximum of 0.184 at $G = 0.5$ . Slotted ALOHA gives $S = G e^{-G}$ with a maximum of 0.368 at $G = 1$ . Here $G$ is attempts per frame time, not per second.

Error detection: CRC, checksum and Hamming

For a CRC, append $r$ zeros (where $r$ is the generator's degree), divide with XOR, and send the message with the $r$ -bit remainder in place of the zeros.

Worked example. Message 1101, generator $x^{3} + x + 1$ (1011). Divide 1101000 by 1011 with XOR: the remainder is 001, so the frame sent is 1101001. Dividing 1101001 by 1011 leaves zero, so the receiver accepts it.

Formula	One-line example	Watch out for
CRC detects all single-bit errors, all odd-count errors if $(x + 1)$ divides $G$ , and all bursts of length $\le r$	$x^{3} + x + 1$ catches every burst of length 3 or less	It does not detect every error
Internet checksum: one's-complement sum of 16-bit words, then complement	`F0F0 + 1234 = 10324`; wrap the carry to get `0325`; checksum `FCDA`	Add the carry back in; do not drop it
Hamming single-error correction: $2^{r} \ge m + r + 1$	$m = 4$ : $r = 3$ , since $8 \ge 8$	Minimum distance $d$ detects $d - 1$ errors and corrects $\lfloor (d - 1)/2 \rfloor$

The 2027 syllabus keeps error detection but drops several older items, as the Computer Networks syllabus changes guide explains.

The book's last-minute revision sheet covers every networks formula in one table, including message switching, ALOHA, RTO estimation, distance-vector updates and HTTP round-trip counts, each with its trap. It is part of the GATE CSE 2027 book.

IPv4 subnetting and CIDR

The host part of a $/p$ address has $32 - p$ bits. Every count follows from that.

Formula	One-line example	Watch out for
Addresses $= 2^{32-p}$	$/27$ : 32 addresses	Hosts versus addresses
Usable hosts $= 2^{32-p} - 2$	$/27$ : 30 hosts	Network and broadcast are excluded
Subnets from $/p$ to $/q = 2^{q-p}$	$/24$ into $/27$ : 8 subnets	Blocks are aligned to their size
Smallest block for $h$ hosts: least $s$ with $2^{s} - 2 \ge h$ , prefix $32 - s$	50 hosts: $s = 6$ , so $/26$	$2^{5} - 2 = 30$ is too small
Same subnet iff (IP AND mask) are equal; broadcast has all host bits 1	192.168.10.77/27: network .64, broadcast .95	Non-octet masks need binary on one octet

When several forwarding-table entries match, the router uses the longest prefix match, not the first match.

IPv4 fragmentation

Fragment offsets are stored in 8-byte units, so every fragment except the last must carry a multiple of 8 data bytes:

\text{data per fragment} = 8 \left\lfloor \frac{\text{MTU} - 20}{8} \right\rfloor, \qquad \text{fragments} = \left\lceil \frac{D}{\text{data per fragment}} \right\rceil

Worked example. A datagram carries $D = 3000$ data bytes over a link with MTU 1000. Data per fragment is $8 \lfloor 980 / 8 \rfloor = 976$ bytes, so there are 4 fragments of 976, 976, 976 and 72 bytes. Their offsets are 0, 122, 244 and 366, and MF is 1 on all but the last.

Remember: The offset is the number of data bytes before the fragment divided by 8. Each fragment's total length is its data plus the 20-byte header.

TCP: congestion window, throughput and numbering

TCP grows cwnd in two phases. Below ssthresh it doubles every RTT (slow start) but never jumps past ssthresh. At or above ssthresh it adds 1 MSS per RTT (congestion avoidance).

Worked example. With ssthresh 16 MSS and cwnd starting at 1, the window at the start of each RTT runs 1, 2, 4, 8, 16, 17, 18. A timeout at 18 sets ssthresh to 9 and cwnd to 1. Three duplicate ACKs at 18 under Reno would set both to 9 instead.

Formula	One-line example	Watch out for
Throughput $\displaystyle \le \dfrac{\min(\text{cwnd}, \text{rwnd})}{\text{RTT}}$	64 KB window, 100 ms: $65536 \times 8 / 0.1 \approx 5.24$ Mbps	Window in bytes, rate in bits
Wraparound time $\displaystyle = \dfrac{2^{32} \times 8}{R}$	At 1 Gbps: about 34.4 s	Sequence numbers count bytes
$\text{RTO} = \text{SRTT} + 4 \times \text{RTTVAR}$	SRTT 100 ms, RTTVAR 10 ms: 140 ms	Update RTTVAR with the old SRTT first
SYN and FIN use one sequence number each; a pure ACK uses none	ISN 1000: first data byte is 1001	ACK number is the next byte expected

The Computer Networks important topics guide shows which templates past papers have used most, and the common mistakes guide lists the unit slips that cost marks.

More formula sheets: all of GATE CSE · COA · Engineering Mathematics · Operating Systems

Quick revision

$t_{\text{trans}} = L/R$ , $t_{\text{prop}} = d/v$ ; store-and-forward takes $(n + k - 1)L/R$ plus one propagation per link.
$\eta = W / (1 + 2a)$ , capped at 1, with $a = t_{\text{prop}} / t_{\text{trans}}$ .
Go-Back-N $W \le 2^m - 1$ ; Selective Repeat $W \le 2^{m-1}$ .
CSMA/CD $L_{\min} = 2\,t_{\text{prop}}\,R$ .
$/p$ : $2^{32-p}$ addresses, $2^{32-p} - 2$ hosts; longest prefix match wins.
Fragment data $= 8\lfloor (\text{MTU} - 20)/8 \rfloor$ ; offsets in 8-byte units.
CRC: append $r$ zeros, XOR-divide, send the $r$ -bit remainder.
Timeout: $\text{ssthresh} = \text{cwnd}/2$ and $\text{cwnd} = 1$ MSS; Reno on three duplicate ACKs sets both to $\text{cwnd}/2$ .

Frequently asked questions

How many sequence number bits do Go-Back-N and Selective Repeat need?

Go-Back-N needs a sender window of at most $2^m - 1$ , so $m = \lceil \log_2(W + 1) \rceil$ . Selective Repeat needs a window of at most $2^{m-1}$ , so $m = \lceil \log_2 W \rceil + 1$ . For a window of 21 frames, Go-Back-N needs 5 bits and Selective Repeat needs 6. Mixing up the two limits is a common trap.

How many usable hosts are in a /27 subnet?

A /27 block has $2^{32-27} = 32$ addresses. The network address and the broadcast address cannot be given to hosts, so 30 are usable. Blocks are aligned to their size, so a /27 always starts at a multiple of 32 in the last octet. Read whether a question asks for addresses or usable hosts.

What is the formula for stop-and-wait efficiency?

Efficiency $\displaystyle = \frac{1}{1 + 2a}$ , where a is the propagation delay divided by the transmission delay of one frame. A sliding window of W frames raises it to W divided by (1 + 2a), capped at 1. If the acknowledgement takes noticeable time to transmit, add its transmission time to the cycle as well.

What happens to the TCP congestion window after a timeout?

On a timeout, ssthresh becomes half the current congestion window and the congestion window drops to 1 MSS, so slow start begins again. On three duplicate ACKs, Tahoe reacts the same way, while Reno sets both the congestion window and ssthresh to half the current window and then grows linearly. Halve the current window, not the old ssthresh.

How is the CRC remainder calculated?

If the generator has degree r, append r zeros to the message and divide by the generator using modulo-2 arithmetic, which is XOR with no borrows. The r-bit remainder replaces the appended zeros to form the transmitted frame. The receiver divides the received frame by the same generator and accepts it only if the remainder is zero.

Sources

Dates, fees and the syllabus are set by the GATE 2027 organising institute and can change. Always confirm at gate2027.iitm.ac.in.