Twenty-one question patterns that recur in GATE CN papers, each with the fastest reliable method. Every number in the mini examples is computed by the course code.
1 Unit traps
Recognise it: a size in KB/MB and a rate in kbps/Mbps in the same question.
Convert size to bits (×8, K = 1024 unless told 1000), rate to bit/s (k = 1000), then divide.
Valid when: the conditions in the lesson rule card hold.
Mini example
1 MB at 8 Mbps = 2²⁰ × 8 / 8 × 10⁶ = 1.048576 s.
2 Store-and-forward pipeline
Recognise it: "N packets", "h hops / k routers", "last bit arrives".
(N + h − 1)·T
t + h·T
p; h = routers + 1. Unequal links: first packet ΣT
t + ΣT
p, then (N − 1)·max T
t.
Valid when: the conditions in the lesson rule card hold.
Mini example
5 packets, 3 links, Tt 8 ms, Tp 1 ms → 59 ms.
3 a, utilisation, minimum frame
Recognise it: "efficiency", "utilisation", "minimum frame size", "maximum distance".
a = T
p/T
t. Send-and-wait U = 1/(1 + 2a). CSMA/CD L
min = 2·T
p·B. Ethernet η = 1/(1 + 5a).
Valid when: the conditions in the lesson rule card hold.
Mini example
Tt = 2 ms, Tp = 4 ms → U = 1/(1 + 4) = 0.2.
4 CRC remainder
Recognise it: a data bit string and a generator (bits or polynomial).
r = degree; append r zeros; XOR-divide; remainder has exactly r bits; send data + remainder.
Valid when: the conditions in the lesson rule card hold.
Mini example
Data 100100, G = 1101 → remainder 001, send 100100001.
5 Internet checksum
Recognise it: 16-bit words in hex or binary, "checksum".
Add in hex; whenever > 0xFFFF drop the 1 and add 1; answer = 0xFFFF − sum.
Valid when: the conditions in the lesson rule card hold.
Mini example
0x1234 + 0xF0F0 + 0xABCD → sum 0xAEF2 → checksum 0x510D.
6 Detect / correct with Hamming distance
Recognise it: "minimum distance", "detect up to", "correct up to".
Detect d − 1; correct ⌊(d − 1)/2⌋; Hamming r: 2ʳ ≥ m + r + 1.
Valid when: the conditions in the lesson rule card hold.
Mini example
d_min = 5 → detect 4, correct 2.
7 ALOHA throughput
Recognise it: "pure/slotted ALOHA", "frames per second", G.
G = attempts/s × T; frames/s delivered = attempts/s × e⁻²ᴳ (pure) or × e⁻ᴳ (slotted) = S/T.
Valid when: the conditions in the lesson rule card hold.
Mini example
T = 1 ms, 1000 attempts/s, pure → 135 frames/s.
8 Backoff winning probability
Recognise it: "collision", "backoff", "probability that A transmits first".
Ranges 2ⁿ for each station; count pairs K
A < K
B; divide by the product of range sizes.
Valid when: the conditions in the lesson rule card hold.
Mini example
A at range 2, B at range 4 → 0.625.
9 Token ring efficiency
Recognise it: "early/delayed token release", N stations, a.
ETR 1/(1 + a/N); DTR 1/(1 + a(N + 1)/N).
Valid when: the conditions in the lesson rule card hold.
Mini example
N = 10, a = 0.5 → ETR 0.9524.
10 Ethernet sizes and address types
Recognise it: "minimum frame", "padding", "multicast address".
Frame = 18 + max(data, 46) bytes; first-byte odd → multicast; all F → broadcast.
Valid when: the conditions in the lesson rule card hold.
Mini example
20 data bytes → padding 26, frame 64 bytes.
11 Subnet network / broadcast / hosts
Recognise it: an address with /n or a mask, "network address", "broadcast", "usable hosts".
Interesting octet block size = 256 − mask octet; network = largest multiple of the block ≤ the octet; broadcast = network + block − 1; hosts = 2ʰ − 2.
Valid when: the conditions in the lesson rule card hold.
Mini example
192.168.5.77/27: block 32 → network 192.168.5.64, broadcast 192.168.5.95, hosts 30.
12 Longest prefix match
Recognise it: a forwarding table with overlapping prefixes.
Keep every matching row; choose the longest prefix; default 0.0.0.0/0 only if nothing else matches.
Valid when: the conditions in the lesson rule card hold.
Mini example
Table /12, /18, /20, default; 172.16.70.9 → 172.16.64.0/20.
13 Aggregation
Recognise it: "summarise", "supernet", several contiguous blocks.
Write in binary; keep the common prefix bits; check the blocks are contiguous and aligned.
Valid when: the conditions in the lesson rule card hold.
Mini example
Four /24 from 192.168.0.0 → 192.168.0.0/22.
14 Fragmentation
Recognise it: "MTU", "offset", "MF", "number of fragments".
Data per fragment = ⌊(MTU − 20)/8⌋·8; offset = byte position / 8 relative to the original; MF = 1 except the last; later hops re-fragment using original offsets.
Valid when: the conditions in the lesson rule card hold.
Mini example
3980 data bytes, MTU 1500 → offsets 0, 185, 370.
15 Distance vector round
Recognise it: neighbour vectors and link costs, "after one exchange".
D_x(y) = min over neighbours v of c(x,v) + D_v(y); use only neighbours' vectors from the previous round.
Valid when: the conditions in the lesson rule card hold.
Mini example
See lesson 3.4.2 for full traces.
16 Dijkstra
Recognise it: a weighted graph, "shortest path", "order nodes are added".
Pick the smallest tentative distance, make it permanent, relax its edges; repeat.
Valid when: the conditions in the lesson rule card hold.
Mini example
Graph in final-test Q22: A → F = 8.
17 Window size and sequence bits
Recognise it: "100 % utilisation", "minimum bits", GBN/SR.
N = ⌈1 + 2a⌉; GBN bits ⌈log₂(N + 1)⌉; SR bits ⌈log₂ 2N⌉.
Valid when: the conditions in the lesson rule card hold.
Mini example
a = 12.5 → N = 26, GBN 5 bits, SR 6 bits.
18 Retransmission counting
Recognise it: "every k-th packet is lost", GBN/SR, total transmissions.
Simulate: in GBN a loss also wastes the rest of the window; in SR only the lost frame is resent.
Valid when: the conditions in the lesson rule card hold.
Mini example
10 frames, window 3, every 4th transmission lost, GBN → 27 transmissions.
19 cwnd trace
Recognise it: ssthresh, timeout or 3 duplicate ACKs, "cwnd at RTT n".
Table row per RTT: SS doubles up to ssthresh, CA +1; timeout → ssthresh = ⌊cwnd/2⌋, cwnd = 1; Reno 3-dup → cwnd = ssthresh.
Valid when: the conditions in the lesson rule card hold.
Mini example
ssthresh 16, timeout during RTT 8 → cwnd at RTT 12 = 8.
20 RTO (Jacobson)
Recognise it: EstimatedRTT, DevRTT, α, β, "new timeout".
RTTVAR ← (1 − β)RTTVAR + β|S − SRTT| (old SRTT); SRTT ← (1 − α)SRTT + αS; RTO = SRTT + 4·RTTVAR. Follow the question's order if stated.
Valid when: the conditions in the lesson rule card hold.
Mini example
SRTT 100, RTTVAR 10, S = 120 → RTO 152.5 ms.
21 HTTP / DNS round trips
Recognise it: objects on a page, persistent or not, parallel connections, DNS RTTs.
DNS Σ RTTs once; then non-persistent 2(N + 1), k-parallel 2 + 2⌈N/k⌉, persistent 2 + N, pipelined 3 RTTs.
Valid when: the conditions in the lesson rule card hold.
Mini example
Base + 10, 4 parallel, RTT 20, DNS 30 → 190 ms.