Computer Networks

Why this unit matters

Computer Networks contributes 7-10 marks in GATE CS and is notable for the variety of question types: layer identification, subnet calculations, routing protocol comparisons, TCP window-size problems, and application-layer protocol details. The numerical questions (subnet size, number of hosts, sliding window throughput) are especially mark-friendly once you know the formulas. This unit has grown in weight in recent papers and deserves serious preparation time.

Syllabus map

OSI model (7 layers) and TCP/IP model (4 layers); comparison, Switching: packet switching, circuit switching, virtual circuit switching, Data link layer: framing, error detection (parity, CRC), MAC protocols, CSMA/CD, Ethernet, bridges, spanning tree, Routing: shortest path (Dijkstra), flooding, distance vector (Bellman-Ford, count-to-infinity), link-state (OSPF), Fragmentation, IPv4 addressing, CIDR, subnetting, ARP, DHCP, ICMP, NAT, Transport: flow control (sliding window), congestion control (slow start, AIMD), UDP, TCP, sockets, Application: DNS, SMTP, HTTP, FTP, Email

OSI vs TCP/IP

OSI layer	Name	TCP/IP equivalent	Key protocols
7	Application	Application	HTTP, FTP, SMTP, DNS
6	Presentation	Application	SSL/TLS, MIME
5	Session	Application	RPC
4	Transport	Transport	TCP, UDP
3	Network	Internet	IP, ICMP, ARP
2	Data Link	Network Access	Ethernet, PPP
1	Physical	Network Access	IEEE 802

GATE trap: ARP and ICMP are often classified as Network layer in TCP/IP, but ARP operates between layer 2 and 3. Know the TCP/IP placement for GATE purposes: IP, ICMP, ARP -> Internet layer.

Switching

Circuit switching: A dedicated path is established before data transfer. Resources (bandwidth, buffers) are reserved for the entire call duration. Inefficient when traffic is bursty; no queuing delays once connected. Used in traditional telephony.

Packet switching: Data is divided into packets; each packet is independently routed. More efficient; can cause variable delays and out-of-order delivery. Used in the Internet.

Virtual circuit switching: Packets follow a predefined path (virtual circuit) but resources are not reserved. Best of both: packet format with predictable routing. Used in ATM, frame relay.

Data link layer

Framing and error detection

Framing methods: character count, flag bytes with byte stuffing, flag bits with bit stuffing (HDLC), physical layer coding violations.

Bit stuffing: In HDLC, the flag is 01111110. After five consecutive 1s in the data, a 0 is stuffed. The receiver removes a 0 following five 1s.

CRC (Cyclic Redundancy Check): Treat the bit string as a polynomial; divide by a generator polynomial G(x); the remainder is the CRC. Detects all burst errors of length <= degree of G(x), all single-bit errors, and all double-bit errors.

MAC protocols

CSMA/CD (Carrier Sense Multiple Access / Collision Detection): used in Ethernet. Station senses the medium; if idle, transmits. If collision detected, sends a jam signal and waits a random backoff time (binary exponential backoff)., CSMA/CA: used in WiFi (802.11). Cannot detect collision on wireless; avoids collision instead., TDMA, FDMA, CDMA: divide time, frequency, or code respectively.

Minimum frame size in CSMA/CD: the frame must be long enough so that the sender is still transmitting when the collision signal arrives back. If propagation delay = tau, RTT = 2tau. Minimum frame transmission time >= 2tau. For 10 Mbps Ethernet with 2500 m maximum distance: 2*tau ~ 51.2 microseconds -> minimum frame = 64 bytes.

Ethernet and bridges

Ethernet: CSMA/CD, 10/100/1000 Mbps, uses MAC addresses (48-bit).

Bridge: connects two LAN segments; operates at layer 2. Learns MAC addresses by observing source addresses. Builds a forwarding table (MAC address -> port). Unknown destinations are flooded; known ones are forwarded on the correct port only.

Spanning tree protocol (STP): Bridges run STP to eliminate loops in bridged LANs by disabling redundant links. Elects a root bridge; all other bridges find the shortest path to the root.

Network layer, routing

Dijkstra's algorithm (link-state)

Used by OSPF. Each router knows the complete topology (via link-state advertisements). Dijkstra computes shortest paths from the source. Time complexity: O(N^2) with adjacency matrix; O((N+E) log N) with a priority queue.

Distance vector routing (Bellman-Ford)

Used by RIP. Each router maintains a distance vector, its estimate of the cost to every other router. Periodically exchanges distance vectors with neighbours. Updates: d(x, y) = min over neighbours v of (c(x, v) + d(v, y)).

Count-to-infinity problem: When a link fails, routers may keep incrementing their distance estimates (counting up to infinity) before declaring the route invalid. Solutions: split horizon (don't advertise a route back to the node you learned it from), split horizon with poison reverse (advertise the route with cost infinity), triggered updates.

Flooding

Every incoming packet is sent out on every outgoing link except the one it arrived on. Guaranteed delivery; highly redundant; used in link-state advertisement dissemination.

Fragmentation, IPv4, CIDR, subnetting

IPv4 header

Key fields: Version (4 bits), IHL (4 bits, in 32-bit words), TOS/DSCP, Total Length (16 bits, in bytes), Identification (16 bits, for reassembly), Flags (3 bits: DF=don't fragment, MF=more fragments), Fragment Offset (13 bits, in 8-byte units), TTL (8 bits), Protocol (8 bits: 6=TCP, 17=UDP, 1=ICMP), Header Checksum (16 bits), Source IP (32 bits), Destination IP (32 bits).

Fragmentation

If a datagram is larger than the MTU of the next link, it is fragmented. Each fragment has the same Identification; MF=1 for all but the last; Fragment Offset = (byte offset of fragment data) / 8.

Example: A 4000-byte IP datagram (including 20-byte header) with MTU=1500.

Data portion = 3980 bytes.

Fragment 1: 1480 data bytes (offset=0, MF=1). Total = 1500 bytes. Fragment 2: 1480 data bytes (offset=1480/8=185, MF=1). Total = 1500 bytes. Fragment 3: 1020 data bytes (offset=2960/8=370, MF=0). Total = 1040 bytes.

CIDR and subnetting

IPv4 address: 32 bits, written in dotted-quad (e.g., 192.168.10.0).

CIDR notation: 192.168.10.0/24 means the first 24 bits are the network prefix; the last 8 bits are the host part. Total addresses = 2^(32-24) = 256. Usable hosts = 256, 2 = 254 (subtract network address and broadcast address).

Subnet mask: /24 = 255.255.255.0. Bitwise AND of IP and mask gives network address.

Example: divide 192.168.1.0/24 into 4 equal subnets.

Need 2 more bits for subnets -> /26. Each subnet has 2^6 = 64 addresses (62 usable hosts).

Subnets:

192.168.1.0/26 (hosts .1 to .62, broadcast .63), 192.168.1.64/26 (hosts .65 to .126, broadcast .127), 192.168.1.128/26 (hosts .129 to .190, broadcast .191), 192.168.1.192/26 (hosts .193 to .254, broadcast .255)

GATE trap: The question may ask for the number of valid hosts (subtract 2), number of subnets (2^borrowed bits), or the subnet to which a specific IP belongs (AND with mask).

ARP, DHCP, ICMP, NAT

ARP (Address Resolution Protocol): Maps IP address to MAC address within the same subnet. Sends a broadcast; the target replies with its MAC. ARP table cached for a short time (TTL ~20 minutes). For hosts on other subnets, ARP resolves the gateway (router) MAC, not the target host.

DHCP (Dynamic Host Configuration Protocol): Provides IP address, subnet mask, default gateway, DNS server to a host automatically. Uses UDP (client port 68, server port 67). Process: Discover -> Offer -> Request -> Acknowledge (DORA).

ICMP (Internet Control Message Protocol): Carries error messages (host unreachable, TTL exceeded, port unreachable) and informational messages (echo request/reply used by ping, traceroute). ICMP runs over IP (Protocol = 1).

NAT (Network Address Translation): Allows multiple devices with private IP addresses to share one public IP. The NAT router translates private (IP, port) pairs to (public IP, unique port) pairs and maintains a translation table. NAT breaks end-to-end connectivity and makes it difficult for external hosts to initiate connections.

Transport layer

UDP

Connectionless, unreliable, no flow control, no congestion control. Header: source port, destination port, length, checksum (8 bytes total). Used for DNS, streaming, gaming (latency-sensitive applications).

TCP

Connection-oriented (three-way handshake: SYN, SYN-ACK, ACK). Reliable, ordered, full-duplex. Provides flow control (receive window) and congestion control.

Three-way handshake: Client sends SYN (seq=x). Server responds SYN-ACK (seq=y, ack=x+1). Client sends ACK (ack=y+1). Connection established.

Connection teardown: FIN, FIN-ACK, FIN, FIN-ACK (four-way). TIME_WAIT state lasts 2*MSL (Maximum Segment Lifetime) to ensure the final ACK reaches the server.

Flow control, sliding window

The receiver advertises a window size (rwnd). The sender can have at most rwnd bytes unacknowledged in flight.

Effective throughput = Window size / RTT (assuming no losses and the window keeps the pipe full).

Example: Window = 64 KB = 65536 bytes, RTT = 100 ms, link speed = 10 Mbps.

Throughput = 65536 * 8 bits / 0.1 s = 5,242,880 bps = ~5.24 Mbps. The link is only 52% utilised.

To fully utilise a 10 Mbps link with 100 ms RTT: window >= 10 Mbps * 0.1 s = 1,000,000 bits = 125 KB.

Congestion control

Slow start: cwnd starts at 1 MSS (Maximum Segment Size). Doubles each RTT until it reaches ssthresh. At ssthresh, switches to congestion avoidance.

Congestion avoidance (AIMD): Increase cwnd by 1 MSS per RTT (additive increase). On packet loss (timeout or 3 duplicate ACKs): multiplicative decrease. On timeout: ssthresh = cwnd/2, cwnd = 1. On 3 duplicate ACKs (fast retransmit): ssthresh = cwnd/2, cwnd = ssthresh (fast recovery in TCP Reno).

GATE trap: In slow start, cwnd grows exponentially (doubles per RTT), not linearly. The name "slow" refers to starting with 1 MSS, not to the growth rate.

Application layer

DNS: Hierarchical, distributed database mapping domain names to IP addresses. Uses UDP port 53 (TCP for zone transfers > 512 bytes). Resolver sends a query; root servers refer to TLD servers; TLD servers refer to authoritative servers. Caching reduces load; TTL controls cache duration.

HTTP: Request-response protocol over TCP port 80 (HTTPS: 443). HTTP/1.0 is non-persistent (new TCP connection per object). HTTP/1.1 introduced persistent connections with pipelining. HTTP/2 uses binary framing and multiplexing.

Response codes: 200 OK, 301 Moved Permanently, 304 Not Modified, 400 Bad Request, 404 Not Found, 500 Internal Server Error.

SMTP (Simple Mail Transfer Protocol): Pushes email from sender's mail server to receiver's mail server, TCP port 25. SMTP is a push protocol. To retrieve email, the receiver uses POP3 (port 110) or IMAP (port 143).

FTP (File Transfer Protocol): Uses two TCP connections, control (port 21) and data (port 20 in active mode; ephemeral port in passive mode). FTP sends credentials in plain text.

GATE trap: SMTP is push (sending); POP3/IMAP is pull (receiving). HTTP and DNS use UDP (DNS) and TCP (HTTP), know which protocols use UDP vs TCP.

Worked examples

Example 1. Subnetting calculation.

An organisation gets 10.0.0.0/8 and needs to create subnets of 500 hosts each. How many host bits are needed and what prefix length?

2^h, 2 >= 500 -> 2^9 = 512, 512, 2 = 510 >= 500. So h = 9 host bits. Prefix length = 32, 9 = /23. Each subnet: 10.0.0.0/23, 10.0.2.0/23, 10.0.4.0/23, ... Total subnets from /8 = 2^(23-8) = 2^15 = 32768 subnets.

Example 2. IP fragmentation.

A 5000-byte datagram (20-byte IP header) with MTU = 1500 bytes. Data = 4980 bytes.

Fragment 1: 1480 bytes data, offset=0, MF=1. Total = 1500 bytes. Fragment 2: 1480 bytes data, offset=185, MF=1. Total = 1500 bytes. Fragment 3: 1480 bytes data, offset=370, MF=1. Total = 1500 bytes. Fragment 4: 540 bytes data, offset=555, MF=0. Total = 560 bytes.

Check: 1480+1480+1480+540 = 4980. Correct. (Offsets in 8-byte units: 0, 185, 370, 555.)

Example 3. Sliding window throughput.

Sender window = 8 segments, each 1000 bytes. RTT = 40 ms. Link speed = 2 Mbps.

Data in flight = 8 * 1000 * 8 = 64,000 bits. Time to transmit one window = 64,000 / 2,000,000 = 32 ms. Since 32 ms < RTT 40 ms, the sender runs out of window before the ACK returns. Throughput = window / RTT = 64,000 bits / 0.04 s = 1.6 Mbps. Utilisation = 1.6/2 = 80%.

Example 4. Distance vector routing.

Three routers A, B, C. Costs: A-B = 1, B-C = 2, A-C = 7.

Initial: A's vector [A:0, B:1, C:7]. B's vector [A:1, B:0, C:2]. C's vector [A:7, B:2, C:0].

After one exchange: A learns C via B: 1+2=3 < 7. A updates C cost to 3.

Updated A vector: [A:0, B:1, C:3]. Converges in one round for this simple topology.

Example 5. TCP slow start.

Initial ssthresh = 8 MSS. cwnd starts at 1.

RTT 1: cwnd=1, send 1 MSS. RTT 2: cwnd=2, send 2 MSS. RTT 3: cwnd=4, send 4 MSS. RTT 4: cwnd=8, reaches ssthresh. Switch to congestion avoidance. RTT 5: cwnd=9 (increase by 1 per RTT). RTT 6: cwnd=10.

If a timeout occurs at RTT 6: ssthresh = 10/2 = 5, cwnd = 1. Slow start restarts from 1.

Quick-revision summary

OSI has 7 layers; TCP/IP has 4 layers. ARP, ICMP -> Internet layer in TCP/IP., Minimum Ethernet frame = 64 bytes (to detect collision during transmission on worst-case network)., CIDR /n: 2^(32-n) addresses, 2^(32-n), 2 usable hosts., Fragmentation: offset in units of 8 bytes; MF=1 for all but last fragment., TCP flow control: rwnd limits sender. Throughput = window / RTT., Slow start: exponential growth to ssthresh; congestion avoidance: linear (AIMD)., SMTP port 25 (push); POP3 port 110, IMAP port 143 (pull). DNS port 53 UDP. HTTP port 80 TCP., Distance vector: count-to-infinity. Fix: split horizon, poison reverse, triggered updates.

How to study this unit

Memorise all key port numbers and protocols. A single table covers all application-layer marks.
Practice subnetting until you can compute the network address, broadcast, first/last host, and number of hosts for any /n within 30 seconds.
Work through 5 IP fragmentation examples, computing offsets and MF bits manually.
Simulate slow start and AIMD on a graph: draw cwnd vs RTT. This makes congestion control questions visual and fast.
Solve Dijkstra's algorithm on 5 different graphs. Practice until it is mechanically fast.
For TCP flow control throughput, always check whether the window or the link speed is the bottleneck, whichever gives the lower rate is the answer.