CN · whole subject on one page

Short notes: Computer Networks

Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.

1. 🧱 Layering, Delays & Switching

Medium ●●7 PYQs →

Easy marks: which layer does what, how headers stack up, and end-to-end delay with transmission plus propagation over several hops.

  • Layers and encapsulation. The OSI model has 7 layers (physical, data link, network, transport, session, presentation, application); the TCP/IP stack has 4 or 5 (link, internet, transport, application). Each layer adds its own header on the way down. The PDU names are: message (application), segment (TCP) or datagram (UDP), packet or datagram (network), frame (data link), bits (physical). Devices: hub and repeater at layer 1, switch and bridge at layer 2, router at layer 3. A router rebuilds the data link header on every hop but never touches the transport layer.
    → Hosts use all layers, routers layers 1 to 3, switches layers 1 to 2, hubs layer 1. Frame, packet, segment, message.
  • Transmission, propagation and queueing delay. Transmission delay Tt = L / B (packet size over bandwidth): the time to push all bits onto the wire. Propagation delay Tp = d / v (distance over signal speed, about 2×10⁸ m/s in cable and 3×10⁸ m/s in air or vacuum). Queueing and processing delay are zero unless the question says otherwise. Careful with units: 1 Kbps = 1000 bps in networking, but 1 KB = 1024 bytes in many GATE questions.
    → Tt = L/B, Tp = d/v, one packet takes Tt + Tp per link. Mind the unit prefixes.
  • Bandwidth-delay product and channel capacity. The bandwidth-delay product B × RTT (or B × Tp for one way) is the number of bits "in flight" on a full pipe: it is the window size you need to keep the link busy. Capacity limits: Nyquist (noiseless) C = 2 · H · log₂ V bits/s for bandwidth H Hz and V signal levels; Shannon (noisy) C = H · log₂(1 + S/N), with S/N as a ratio (convert from dB: ratio = 10^(dB/10)). The smaller of the two bounds applies.
    → BDP = B × RTT. Shannon needs the S/N ratio, not dB. Capacity is the smaller of Nyquist and Shannon.
  • Circuit, packet and virtual-circuit switching. Circuit switching reserves a path first (setup time), then sends with no per-hop wait. Packet switching (datagram) sends each packet independently with store-and-forward: a router receives the whole packet before forwarding. For one packet over k links: k · (L/B) + total Tp. For n packets pipelined over k links: (k + n − 1) · (L/B) + total Tp. Virtual circuits set up a fixed path once and then use short circuit IDs. Packet switching wins for bursty traffic because links are shared.
    → Pipelined: (k + n − 1) Tt + sum of Tp. Packet switching shares links; circuits waste idle capacity.

Formulas

Transmission delay
Tt = L / B
Propagation delay
Tp = d / v
One packet over k store-and-forward links
k · (L/B) + sum of Tp
n packets over k links (equal sizes)
(k + n − 1) · (L/B) + sum of Tp
Bandwidth-delay product
B × RTT (bits in the pipe)
Nyquist capacity
C = 2 H log2 V
Shannon capacity
C = H log2 (1 + S/N), S/N = 10^(dB/10)

What GATE asks

  • ★★★Total delay of a file over several store-and-forward links. Count the packets and hops, use (k + n − 1) Tt plus the propagation delays. Check the unit prefixes.
  • ★★★Layer matching, PDU names, header field sizes. Which layer routes, frames, or does host-to-host delivery; sizes of port, MAC, sequence number fields.
  • ★★★How many times does a packet visit each layer. Hosts use all layers; each router uses layers 1 to 3 only. Count the link ends for layer 2.

Traps

"Bandwidth 1 Mbps" is 10⁶ bits/s, not 2²⁰.
In pipelined store-and-forward the propagation delays add up, but the transmission time is (k + n − 1) packets, not k × n.
A router changes the data link header at every hop; the IP addresses stay the same (without NAT).
Shannon uses the S/N ratio, not the dB value.

2. 🧮 Framing & Error Control

Medium ●●2 PYQs →

CRC, Hamming and checksum calculations are mechanical and appear regularly. Know the procedures cold.

  • Framing and stuffing. The link layer must mark where a frame starts and ends. Bit stuffing (HDLC, flag 01111110): after five consecutive 1s in the data the sender inserts a 0, and the receiver removes a 0 that follows five 1s. Byte stuffing: an escape byte is placed before every data byte that looks like the flag or the escape. The overhead depends on the data: all-ones data stuffs the most (one extra bit per five).
    → Bit stuffing: 0 after five 1s. Byte stuffing: ESC before FLAG and ESC.
  • Parity and Internet checksum. Single parity bit detects every odd number of bit errors and misses even numbers; it detects, never corrects. 2-D parity can correct a single-bit error. The Internet checksum (IP, TCP, UDP) adds 16-bit words with end-around carry and sends the 1s complement; the receiver adds everything including the checksum and expects all ones. It misses errors that cancel out, such as swapped words.
    → Parity: odd errors only. Checksum: end-around carry, 1s complement, receiver expects all ones.
  • CRC (cyclic redundancy check). Treat the message as a polynomial over GF(2). For a generator of degree r (r + 1 bits), append r zeros, divide by the generator using XOR, and the remainder is the CRC appended to the message. The receiver divides the whole frame; remainder zero means accepted. A CRC with generator degree r detects all burst errors of length ≤ r and every odd number of errors if (x + 1) divides the generator. Ethernet uses CRC-32.
    → Append r zeros, XOR divide, send the remainder. Receiver remainder 0 means accepted. Degree r gives r check bits.
  • Hamming code and distance. The Hamming distance d between two codewords is the number of differing bits; a code detects up to d − 1 errors and corrects up to ⌊(d − 1)/2⌋. For single-error correction with m data bits you need r check bits with 2ʳ ≥ m + r + 1. Check bits sit at positions 1, 2, 4, 8, ...; check bit p covers every position whose binary form has bit p set. The syndrome (the failed checks read as a binary number) is the position of the flipped bit.
    → Check bits at powers of two. 2^r ≥ m + r + 1. Syndrome = position of the error. Detect d − 1, correct (d − 1)/2.

Formulas

Bit stuffing
insert a 0 after every 5 consecutive 1s in the data
CRC frame length
message + r bits, r = degree of the generator
Hamming distance d
detect d − 1, correct ⌊(d − 1)/2⌋ errors
Hamming check bits
2^r ≥ m + r + 1
12-bit Hamming (8 data bits)
r = 4, check bits at positions 1, 2, 4, 8
Internet checksum
~(sum of 16-bit words with end-around carry)

What GATE asks

  • ★★★Compute the CRC for a message and generator. Long XOR division; match the polynomial (x³ + x + 1 = 1011) before dividing.
  • ★★★Hamming codeword: find a missing data or check bit. Use even or odd parity over the covered positions.
  • ★★★Error detection capability / distance. d − 1 detected, (d − 1)/2 corrected; checksum and parity limits.

Traps

The generator x³ + x + 1 has 4 bits (1011) but only 3 check bits.
Do not append the generator; append zeros, divide, then append the remainder.
In Hamming codes the parity bits are interleaved at powers of two, not at the end.
Stuffed bits count towards the frame length.

3. 🪟 Flow Control & Sliding Window

High yield ●●●6 PYQs →

Efficiency and window-size numericals (stop-and-wait, GBN, selective repeat) are among the most predictable CN questions.

  • Stop-and-wait. Send one frame, wait for the acknowledgement. The cycle time is Tt + 2Tp (add the ack transmission time Tack if the question gives it). Efficiency = useful time / cycle = Tt / (Tt + 2Tp) = 1 / (1 + 2a) with a = Tp/Tt. Throughput = efficiency × bandwidth, or frame size / cycle time. It is bad on long fat links: utilisation falls as the bandwidth or distance grows.
    → η = Tt / (Tt + 2Tp). Higher bandwidth or distance lowers it. Count the ack time if given.
  • Go-Back-N. The sender may have N unacknowledged frames in flight. The receiver accepts only the next in-order frame (receiver window 1) and sends cumulative acks. On a timeout the sender goes back and resends the lost frame and everything after it. Sequence numbers needed: N + 1 (so ⌈log₂(N + 1)⌉ bits). Efficiency with window N: min(1, N · Tt / (Tt + 2Tp)).
    → GBN: receiver window 1, cumulative ack, resend from the lost frame, N + 1 sequence numbers.
  • Selective Repeat. Both sender and receiver have a window of size N. The receiver buffers out-of-order frames and acknowledges each one; the sender retransmits only the lost frame. To avoid confusing old and new frames the sequence space must be at least 2N, so ⌈log₂(2N)⌉ bits and N ≤ 2k − 1. It uses the same utilisation formula as GBN but wastes less on errors.
    → SR: both windows N, ack each frame, resend only the lost one, needs 2N sequence numbers.
  • Window size, utilisation and sequence-number bits. To reach 100% utilisation the window must cover the pipe: W ≥ 1 + 2a = (Tt + 2Tp) / Tt. For a target utilisation U: W = U · (Tt + 2Tp) / Tt, rounded up. Then pick the sequence-number bits from the protocol: stop-and-wait 1 bit, GBN ⌈log₂(W + 1)⌉, SR ⌈log₂(2W)⌉. Piggybacking puts the ack inside a data frame going the other way.
    → W = U (Tt + 2Tp)/Tt rounded up. GBN bits log(W + 1), SR bits log(2W).

Formulas

a
a = Tp / Tt
Stop-and-wait efficiency
η = Tt / (Tt + 2Tp) = 1 / (1 + 2a)
With ack transmission
cycle = Tt + 2Tp + Tack
Sliding window efficiency
η = min(1, N · Tt / (Tt + 2Tp))
Window for full utilisation
N = 1 + 2a
Sequence numbers
GBN: N + 1 ; SR: 2N ; stop-and-wait: 2
Throughput
η × bandwidth

What GATE asks

  • ★★★Stop-and-wait utilisation or throughput. Compute Tt and Tp, include the ack transmission time if given, then Tt / cycle.
  • ★★★Minimum window size for a target utilisation. W = U (Tt + 2Tp) / Tt, round up; the answer may be a range.
  • ★★★Sequence-number bits for GBN or SR. GBN needs W + 1 numbers, SR needs 2W.
  • ★★★Which link or setting gives the lowest utilisation. Utilisation falls with larger Tp and larger bandwidth (smaller Tt).

Traps

One-way propagation delay Tp appears twice in the cycle (data out, ack back).
Higher bandwidth lowers stop-and-wait utilisation because Tt shrinks.
GBN window N needs N + 1 sequence numbers, SR needs 2N; mixing them up is the classic error.
"1 KB" frame is 1024 × 8 bits unless stated otherwise, while "1 Mbps" is 10⁶ bits/s.

4. 🔌 Medium Access & LANs

Medium ●●5 PYQs →

ALOHA throughput, the Ethernet minimum frame size and switch behaviour give steady marks.

  • ALOHA and slotted ALOHA. Pure ALOHA: send whenever you like; a frame collides if anyone else transmits within one frame time before or after it (vulnerable period 2T). Throughput S = G e−2G, maximum 1/(2e) ≈ 18.4% at G = 0.5. Slotted ALOHA: transmissions start only at slot boundaries, so the vulnerable period is T: S = G e−G, maximum 1/e ≈ 36.8% at G = 1. G is the average number of attempts per frame time.
    → Pure 1/(2e) = 18.4%, slotted 1/e = 36.8%. Vulnerable period 2T versus T.
  • CSMA/CD and the Ethernet frame size. CSMA listens before sending; CD (collision detection) keeps listening while sending and aborts on a collision, then waits a random binary exponential backoff. A sender must still be transmitting when the collision signal returns, so Tt ≥ 2Tp, i.e. minimum frame size = 2 · Tp · B. Classic Ethernet: 10 Mbps, 512-bit (64-byte) minimum frame, slot time 51.2 µs. Maximum cable length = (L/B)/2 × signal speed.
    → Tt ≥ 2Tp. Min frame = 2 Tp B. Classic Ethernet: 512 bits.
  • Hubs, bridges, switches and VLANs. A hub repeats bits to all ports: one collision domain and one broadcast domain. A bridge or switch is a learning device: it notes the source MAC and port of each frame, forwards to the known port, floods if the destination is unknown or broadcast, and filters if it lies on the same port. Each switch port is its own collision domain; the broadcast domain still spans the whole switch. A VLAN splits one switch into several broadcast domains; routers (layer 3) separate broadcast domains. Connecting n machines with k-port switches in a tree needs ⌈(n − 2)/(k − 2)⌉ switches.
    → Switch learns from source, forwards by destination, floods unknown. Router splits broadcast domains.
  • Token ring and wireless access. In token ring only the holder of the token may transmit; there are no collisions. The token must be able to travel the ring, so the time for a token to be considered lost is about ring propagation time + all stations' holding times. Efficiency improves when the frame is long compared with the ring latency. Wireless LANs use CSMA/CA (avoid, with RTS/CTS) since a sender cannot hear a collision while transmitting.
    → Token ring: Tp(ring) + n × hold. Tree of k-port switches: ⌈(n − 2)/(k − 2)⌉.

Formulas

Pure ALOHA
S = G e^(−2G), max 1/(2e) ≈ 0.184 at G = 0.5
Slotted ALOHA
S = G e^(−G), max 1/e ≈ 0.368 at G = 1
CSMA/CD condition
Tt ≥ 2 Tp, so min frame = 2 Tp × B
Max cable length
d = (L/B)/2 × v
Switches to join n hosts (k ports each)
tree of switches: ⌈(n − 2)/(k − 2)⌉
Token ring: wait before assuming token lost
ring Tp + (stations × token holding time)

What GATE asks

  • ★★★Minimum frame size or maximum cable length in Ethernet. Apply Tt = 2Tp. Watch for a round trip versus one way.
  • ★★★ALOHA / slotted ALOHA throughput. Plug into S = G e^(−2G) or G e^(−G); maximum values to remember.
  • ★★★Switch / hub / VLAN: domains and learning. Count collision or broadcast domains; follow a frame through a learning switch.
  • ★★★Number of switches needed or token ring timing. Tree of k-port switches loses 2 ports per extra switch.

Traps

Min frame size uses the round trip (2Tp), not one way.
A switch does not shrink the broadcast domain; only a router or VLAN does.
Pure ALOHA max is 0.184, slotted is 0.368: do not swap them.
A learning switch learns from the source address and forwards using the destination.

5. 🌐 IP Addressing & Network Layer

High yield ●●●26 PYQs →

The biggest CN topic: subnet and CIDR calculations, longest-prefix forwarding and IP fragmentation arrive nearly every year.

  • IPv4 addresses and classes. An IPv4 address is 32 bits. Classful ranges by the first octet: A 0 to 127 (/8, 2²⁴ − 2 hosts), B 128 to 191 (/16), C 192 to 223 (/24, 254 hosts), D 224 to 239 (multicast), E 240 to 255. Number of networks: A 2⁷ (126 usable), B 2¹⁴, C 2²¹. Special: 127.x.x.x loopback, all-ones = limited broadcast, 0.0.0.0 "this host", and private ranges 10/8, 172.16/12, 192.168/16. Each block loses 2 addresses (network and broadcast) for hosts.
    → Class by first octet. Hosts 2^h − 2. Networks A 2^7, B 2^14, C 2^21.
  • Subnetting and CIDR. A prefix /n keeps n network bits and 32 − n host bits; the block has 2^(32 − n) addresses and 2^(32 − n) − 2 usable hosts. Network address = IP AND mask; broadcast = network with all host bits set. Two hosts are in the same subnet if they have the same network address under the mask. Masks: /24 = 255.255.255.0, /26 = 255.255.255.192, /30 = 255.255.255.252. A block must start at a multiple of its size (84.0/21 is not a valid block; 80.0/21 is).
    → Network = IP AND mask. Usable = 2^(32 − n) − 2. Compare network addresses for "same subnet".
  • VLSM, aggregation and longest-prefix match. VLSM gives each LAN a block just big enough: round (hosts + 2) up to a power of two, allocate the biggest first from a block so alignment holds. Route aggregation merges adjacent equal-size blocks into one shorter prefix (4 contiguous /24s become one /22) and shrinks routing tables. A router forwards by longest-prefix match: among all matching entries the one with the longest mask wins; the default route 0.0.0.0/0 matches everything but loses to any longer match.
    → Longest prefix wins. Blocks start at multiples of their size. Merge adjacent equal blocks.
  • IP header and fragmentation. If a datagram is bigger than the link MTU, a router splits it. Each fragment has its own header (20 bytes with no options). Payload per fragment is a multiple of 8 bytes because the fragment offset field counts in 8-byte units: per = ⌊(MTU − header)/8⌋ × 8. Offset = (bytes before this fragment)/8; MF = 1 on all fragments except the last. Only the destination reassembles; routers may fragment again. Fields changed by a router: TTL and header checksum (and fragmentation fields). Header length (HLEN) is counted in 4-byte words; total length in bytes.
    → Payload multiple of 8. Offset = start/8. Fragment count = ⌈data/payload⌉. Only the destination reassembles.
  • ARP, DHCP, ICMP and NAT. ARP maps an IP address to a MAC address: the request is a broadcast (destination FF:FF:FF:FF:FF:FF), the reply is unicast. Hosts use ARP for the next hop: a packet to another network is addressed (at layer 2) to the router's MAC while keeping the final destination IP. DHCP hands out IP, mask, gateway and DNS (over UDP 67/68). ICMP carries errors and diagnostics (ping, traceroute, time exceeded). NAT rewrites the source IP (and port) of outgoing packets and recomputes the IP and TCP/UDP checksums; it breaks end-to-end addressing.
    → ARP request broadcast, reply unicast. Off-subnet: MAC of the gateway, IP of the destination. Router changes TTL and checksum.

Formulas

Hosts in a /n block
2^(32 − n) − 2 usable
Network address
IP AND mask
Broadcast address
network OR (NOT mask)
Prefix for h hosts
smallest 32 − b with 2^b − 2 ≥ h
Fragment payload
floor((MTU − hdr) / 8) × 8
Fragment offset
bytes before this fragment / 8
Classful network counts
A: 2^7, B: 2^14, C: 2^21
ARP request
dest MAC = FF:FF:FF:FF:FF:FF (broadcast)

What GATE asks

  • ★★★Subnet membership / network address / usable hosts. AND the addresses with the mask; compare network addresses.
  • ★★★Number of fragments, last-fragment size, offset value. Round the payload down to a multiple of 8; repeat across two links.
  • ★★★Forwarding table: longest-prefix match and aggregation. Find all matching prefixes and pick the longest; merge blocks for aggregation.
  • ★★★Valid CIDR block / allocation. Check alignment, size = power of two, no overlap.
  • ★★★ARP, NAT, header fields modified by routers. Which MAC is the destination; which fields change (TTL, checksum, source IP/port with NAT).

Traps

Payload per fragment must be a multiple of 8; the last fragment may be any size.
The offset is in 8-byte units, so offset 300 means byte 2400.
A router does not reassemble fragments; only the destination does.
A /30 block has 4 addresses but only 2 usable hosts.
ARP request is broadcast; the reply is not.

6. 🧭 Routing & Congestion Control

Medium ●●3 PYQs →

Distance vector versus link state comparisons, RIP/OSPF/BGP facts and token bucket numericals.

  • Distance vector routing. Each router keeps a table of (destination, cost, next hop) and periodically sends its whole table to its neighbours. On receiving a neighbour's vector it applies Bellman-Ford: cost(via k) = cost(to k) + k's cost to destination. It needs only local knowledge but converges slowly ("bad news travels slowly"): after a link failure two routers can keep increasing a cost until infinity (count to infinity). Fixes: split horizon (do not advertise a route back to where you learned it), poison reverse, and a small infinity (RIP uses 16).
    → DV: Bellman-Ford, neighbours only, slow convergence, count to infinity, split horizon helps.
  • Link state routing. Each router floods link-state packets describing its direct links; everyone builds the same map and runs Dijkstra. It converges faster, is loop-free in steady state and supports per-link metrics, but costs more CPU and memory (O(E log V) per run) and more flooding traffic. A distance vector protocol with split horizon still does not avoid all loops, whereas link-state converges after a topology change in one flooding round plus a computation.
    → Link state: flood, full map, Dijkstra. Faster convergence, more overhead.
  • RIP, OSPF, BGP and the Internet hierarchy. An autonomous system (AS) is a network under one administration. Intra-domain (interior) protocols: RIP (distance vector, hop count, max 15, runs over UDP) and OSPF (link state, Dijkstra, areas for hierarchy, runs directly over IP with protocol number 89). Inter-domain: BGP (path vector, over TCP port 179) exchanges reachability and policy between ASes, not shortest paths. OSPF is not an inter-domain protocol and does not use Bellman-Ford.
    → RIP: DV, UDP. OSPF: link state, IP, Dijkstra, areas. BGP: path vector, TCP, between ASes.
  • Congestion and traffic shaping: leaky and token bucket. The leaky bucket smooths traffic to a constant output rate: bursts queue in the bucket and leave at a fixed rate. The token bucket allows bursts: tokens arrive at rate r into a bucket of capacity C; sending needs tokens, so a full bucket lets you burst at the maximum rate M until the tokens run out, then continue at r. Burst duration = C / (M − r). To send D units from a full bucket: burst for C/(M − r) (sending M · C/(M − r)), then send the rest at rate r.
    → Token bucket: burst C/(M − r), then token rate r. Leaky bucket: constant output.

Formulas

Bellman-Ford update
D_x(y) = min over neighbours k of [ c(x,k) + D_k(y) ]
Convergence
at most n − 1 rounds of exchanges
Dijkstra with a heap
O((V + E) log V)
RIP
hop count, infinity = 16, UDP port 520
Token bucket burst length
t = C / (M − r)
Token bucket total time
t + (D − M·t) / r

What GATE asks

  • ★★★Compare link state and distance vector. Overhead, loop behaviour with split horizon, convergence speed.
  • ★★★Which protocol is intra- or inter-domain, algorithm used. OSPF = Dijkstra, link state, hierarchical; RIP = distance vector; BGP = inter-domain.
  • ★★★Token bucket: minimum time to send D data. Burst until the bucket empties, then token-rate limited.

Traps

Link-state does not use Bellman-Ford; distance vector does.
BGP exchanges path/policy information and runs over TCP; it is not a shortest-path protocol.
Split horizon reduces, but does not fully remove, counting to infinity (loops of three or more routers).
In the token bucket the burst and the token arrival happen at the same time, so the burst lasts C/(M − r), not C/M.

7. 🚚 Transport Layer: UDP & TCP

High yield ●●●11 PYQs →

TCP handshake and congestion control, sequence-number wrap time, and UDP versus TCP facts are asked almost every year.

  • UDP and ports. UDP is connectionless and unreliable: an 8-byte header (source port, destination port, length, checksum) and no ordering, retransmission or flow control. Good for DNS, streaming, DHCP, RIP, SNMP, where speed or multicast matters. A socket is (IP address, port); a TCP connection is identified by the 4-tuple (source IP, source port, destination IP, destination port). Ports are 16 bits: well-known 0 to 1023 (HTTP 80, HTTPS 443, DNS 53, SMTP 25, FTP 21 and 20, POP3 110, IMAP 143).
    → UDP: no connection, no reliability, 8-byte header. TCP: reliable stream. 16-bit ports.
  • TCP segment, handshake and teardown. TCP is reliable, connection-oriented and byte-stream based. Header 20 to 60 bytes: ports, 32-bit sequence number (index of the first data byte), 32-bit acknowledgement number (next byte expected), flags (SYN, ACK, FIN, RST), receiver window (flow control), checksum. 3-way handshake: SYN (seq = x) → SYN+ACK (seq = y, ack = x + 1) → ACK (ack = y + 1). Initial sequence numbers are chosen randomly. SYN and FIN each consume one sequence number. Teardown: FIN, ACK, FIN, ACK, with the active closer going through FIN-WAIT-1, FIN-WAIT-2 and then TIME-WAIT (2 × MSL). A segment can carry data and an ack together (piggybacking).
    → SYN, SYN+ACK, ACK. ack = seq + 1. ISNs random. FIN-WAIT-2 waits for the other FIN.
  • TCP congestion control. The sender keeps cwnd and sends min(cwnd, rwnd). Slow start: cwnd starts at 1 MSS and doubles every RTT (+1 MSS per ack) until it reaches ssthresh. Congestion avoidance: +1 MSS per RTT (AIMD, additive increase). On a timeout: ssthresh = cwnd/2, cwnd = 1 MSS, back to slow start. On 3 duplicate ACKs: Tahoe acts as for a timeout; Reno halves (ssthresh = cwnd = cwnd/2) and uses fast recovery. Time to climb back: count RTTs, one per doubling or +1 step.
    → Slow start doubles per RTT; avoidance +1 per RTT; timeout ssthresh = cwnd/2 and cwnd = 1.
  • Throughput, sequence-number wrap and timers. Throughput ≤ min(cwnd, rwnd) / RTT. To keep a pipe full, rwnd ≥ bandwidth × RTT. The sequence-number field must not wrap within the maximum segment lifetime (MSL): 2ᵇⁱᵗˢ bytes ≥ bandwidth (bytes/s) × MSL. Wrap-around time for 32 bits at 1 Gbps: 2³² × 8 / 10⁹ ≈ 34 s. RTT estimation uses an exponential average and the retransmission timeout is set from the estimate plus a safety margin (Karn's algorithm ignores retransmitted segments).
    → Throughput = window / RTT. Seq bits ≥ log2(B(bytes/s) × MSL). 32 bits at 1 Gbps wrap in 34 s.

Formulas

TCP/UDP port
16 bits (0 to 65535)
Handshake
SYN(x) → SYN+ACK(y, x+1) → ACK(y+1)
cwnd in slow start
doubles each RTT until ssthresh
After timeout
ssthresh = cwnd/2, cwnd = 1 MSS
Throughput
min(cwnd, rwnd) / RTT
Sequence bits for no wrap in MSL
2^b ≥ B(bytes/s) × MSL
Wrap time of 32-bit seq at rate B
2^32 × 8 / B seconds

What GATE asks

  • ★★★Congestion window after k RTTs with a timeout. Apply slow start up to ssthresh, then +1 per RTT; reset on timeout.
  • ★★★Sequence-number bits or wrap-around time. bytes sent in MSL = B × MSL, then log2.
  • ★★★Handshake / teardown: flags, seq and ack numbers, states. Which flags are set in P1, P2, P3; ack = seq + 1.
  • ★★★TCP vs UDP facts, crashes and resets. Server crash gives RST; ISNs are random; FIN-WAIT-2 state.

Traps

Slow start doubles per RTT, even though cwnd grows by 1 per ACK.
After a timeout ssthresh is half of the cwnd at the time of loss, not half of the old ssthresh.
The ack number is the next byte expected: ISN + 1 for the SYN.
The sequence number counts bytes, not segments.
SYN+ACK: both SYN and ACK flags are set; the first SYN has ACK = 0.

8. 📬 Application Layer: DNS, HTTP, Email

Medium ●●9 PYQs →

Typical questions: how many RTTs does a page load take, how many DNS queries, which protocol uses TCP or UDP.

  • DNS. The Domain Name System maps names to IP addresses through a hierarchy: root servers, top-level-domain (.in, .com), authoritative servers. A name like www.gate.org.in is resolved iteratively by the local resolver: root → .in → org.in → gate.org.in, which is 4 query-response pairs when nothing is cached. In recursive mode each server asks the next on your behalf. Resolvers cache answers (TTL). DNS uses UDP port 53 for ordinary queries and TCP for zone transfers or large replies. Records: A (IPv4), AAAA, MX (mail), NS, CNAME.
    → DNS first. Iterative: one pair per level. UDP 53. A, MX, NS, CNAME records.
  • HTTP timing: persistent and non-persistent. An RTT is the round trip time. A TCP handshake costs 1 RTT, and a request-response costs 1 RTT (ignoring transmission time). Non-persistent HTTP opens a new connection per object: 2 RTT per object (1 handshake + 1 request). Persistent HTTP keeps the connection: after one handshake each object costs 1 RTT, and with pipelining all requests go out together, so n objects cost about 1 RTT. With p parallel connections, objects are fetched in ⌈n/p⌉ rounds. Total time = DNS lookup + 2 RTT for the base page + time for the embedded objects. HTTP is stateless; cookies add state.
    → DNS + 2 RTT base. Non-persistent 2 RTT per object. Persistent 1 RTT, pipelined 1 RTT for all.
  • Email and FTP. SMTP (TCP 25) pushes mail from a client to a server and between servers. To retrieve mail use POP3 (TCP 110, downloads and usually deletes) or IMAP (TCP 143, keeps mail on the server, folders). MIME adds attachments and non-ASCII content to the mail format. FTP uses two TCP connections: control (port 21, persistent, stateful) and data (port 20, new for each file transfer). POP3 and FTP are stateful; HTTP is stateless.
    → SMTP sends, POP3 or IMAP retrieve. FTP: 2 connections, stateful. HTTP stateless.

Formulas

Iterative DNS lookup
root, TLD, ... , authoritative: 1 query-response per level
Non-persistent HTTP, n objects
2 RTT × (1 + n) (sequential)
Persistent without pipelining
2 RTT (first) + 1 RTT × n
Persistent with pipelining
2 RTT + 1 RTT for all objects
Parallel connections
rounds = ceil(objects / connections)
Ports
HTTP 80, HTTPS 443, DNS 53, SMTP 25, POP3 110, IMAP 143, FTP 21/20

What GATE asks

  • ★★★Time to load a web page (DNS + HTTP + objects). Add DNS RTTs, TCP handshake, request, then objects for the HTTP variant.
  • ★★★Number of DNS query-response pairs. One per level of the name hierarchy when iterative and uncached.
  • ★★★Which transport protocol or port an application uses; protocol pairs for email. SMTP to send, POP3/IMAP to retrieve; DNS over UDP; email over TCP.
  • ★★★Order of actions in a web request. DNS first, then TCP handshake, then HTTP.

Traps

The DNS query always comes before the TCP SYN (you do not know the IP yet).
Non-persistent HTTP pays 2 RTT per object, not 1.
IMAP and POP3 retrieve mail; SMTP only sends.
FTP is stateful and uses two connections; HTTP is stateless.

9. 🔐 Network Security

Medium ●●6 PYQs →

RSA arithmetic, who signs with which key, and which algorithm is a hash or a cipher are quick marks.

  • Symmetric and public-key cryptography, RSA. Symmetric ciphers (DES, 3DES, AES) use one shared secret key: fast, but the key must be distributed. Public-key ciphers use a pair: encrypt with the receiver's public key, decrypt with the receiver's private key. RSA: choose primes p, q; n = p·q; φ(n) = (p − 1)(q − 1); pick e with gcd(e, φ) = 1; compute d = e⁻¹ mod φ (e · d ≡ 1 mod φ). Public key (e, n), private key (d, n). Ciphertext c = mᵉ mod n; plaintext m = cᵈ mod n. If you know n and φ(n), then p + q = n − φ(n) + 1 and you can factor n.
    → d = e⁻¹ mod φ. c = m^e mod n. p + q = n − φ + 1.
  • Hash functions and digital signatures. A hash (message digest) such as MD5 or SHA-1 maps a message to a fixed-size digest; it is one-way and collision resistant. RSA and DES are not hash functions. A digital signature proves origin and integrity: the sender computes H(m) and encrypts it with the sender's private key; sends (m, signature); the receiver decrypts the signature with the sender's public key and compares with H(m). To also keep the message secret, additionally encrypt with the receiver's public key. A birthday attack finds two messages with the same digest; the signer can use it to repudiate a signature.
    → Sign with your private key. Encrypt with the receiver's public key. MD5 and SHA-1 are hashes, RSA and DES are not.
  • Firewalls, IPsec, SSL/TLS and common attacks. A packet-filtering firewall allows or blocks packets by header fields (addresses, ports, protocol); a stateful firewall tracks connections; an application gateway (proxy) inspects the payload. IPsec secures the network layer (AH for integrity, ESP for confidentiality); SSL/TLS secures the transport layer (HTTPS on 443). Attacks: SYN flood (half-open connections), DoS/DDoS, man-in-the-middle, replay, spoofing. Certificates bind a public key to an identity through a trusted CA.
    → Firewalls filter, IPsec = network layer, TLS = above TCP, SYN flood = half-open connections.

Formulas

RSA keys
n = pq, φ = (p−1)(q−1), e·d ≡ 1 (mod φ)
RSA encrypt / decrypt
c = m^e mod n ; m = c^d mod n
Factor n from φ
p + q = n − φ + 1, then solve the quadratic
Signature
sign = D_senderPrivate(H(m)), verify with the sender public key

What GATE asks

  • ★★★RSA: find the private key or a prime factor. φ = (p−1)(q−1); d = e⁻¹ mod φ; or solve p + q = n − φ + 1.
  • ★★★Digital signature: which keys are used and in which order. Sign with your private key, encrypt with the receiver's public key; decrypt in reverse.
  • ★★★Hash vs cipher; birthday attack. MD5 and SHA-1 are hashes; RSA and DES are ciphers.

Traps

You sign with your private key but encrypt with the receiver's public key.
d is the inverse of e modulo φ(n), not modulo n.
RSA and DES do not generate message digests.
A birthday attack on a signed message is possible by the signer, not only by a third party.