Computer Networks

Layering: OSI and TCP/IP

Why networks are built in layers, the vocabulary of service, interface and protocol, the seven OSI layers and the four or five TCP/IP layers with the unit of data (PDU) and the typical protocols and devices of each, encapsulation and de-encapsulation, and how header overhead adds up; the layer tables are quoted from the textbooks, the header arithmetic is computed.

Circuit, packet and virtual-circuit switching

How data is moved through a network of links and nodes: circuit switching (reserved path, set-up time, no store and forward), packet switching (datagrams routed one by one, store and forward, statistical multiplexing) and virtual circuits (a path set up once, short labels per link); the total delay of a message split into packets over several links, the saving from splitting, and the probability that statistical multiplexing overloads a link, all computed exactly and cross-checked by an event simulation.

Delay, throughput and bandwidth-delay product

The four sources of delay (processing, queueing, transmission, propagation) and their formulas, bandwidth against throughput and the bottleneck link, the bandwidth-delay product as the amount of data in flight, round-trip time, and the utilisation of a stop-and-wait protocol and how many frames must be in flight to fill a pipe; numbers are exact fractions cross-checked by a simulation.

Error detection: parity, checksum and CRC

How a receiver notices that bits were flipped in transit: single parity, two-dimensional parity, the Internet (ones' complement) checksum and the cyclic redundancy check; CRC by modulo-2 long division with every step, the generator polynomial, what a CRC provably detects (all single-bit errors, bursts up to the CRC length, odd numbers of errors when x + 1 divides the generator) and how many error patterns escape; the divisions were checked against zlib's CRC-32 and the detection claims by trying every error pattern.

Hamming code (error correction)

Correcting errors without retransmission: Hamming distance and what the minimum distance of a code detects and corrects, the Hamming code with its check bits at the powers of two and the syndrome that names the wrong position, how many check bits m data bits need, the extended code that also detects double errors, and the odd-parity variant and the numbering conventions that questions use.

Medium access: ALOHA, CSMA and CSMA/CD

How stations that share one channel decide who may transmit: random access with ALOHA (pure and slotted, throughput G e^(-2G) and G e^(-G) with maxima 1/(2e) and 1/e), carrier sensing (the persistence variants of CSMA), collision detection and binary exponential backoff, the minimum frame length 2 d R / v that makes collision detection work, and the efficiency of CSMA/CD; formulas are checked by simulation and exact enumeration.

Ethernet, frames and minimum frame size

The Ethernet (IEEE 802.3) frame and its fields, 48-bit MAC addresses (unicast, multicast, broadcast), the 64-byte minimum and 1518-byte maximum frame and the reason for the minimum (collision detection), padding, the efficiency of Ethernet for different payload sizes with preamble and interframe gap, the longest network for a given minimum frame, and the difference between shared (CSMA/CD) and switched Ethernet; sizes and efficiencies are computed exactly, the standard's field list is quoted.

IPv4 addressing and classful addressing

The 32-bit IPv4 address, dotted decimal notation and conversion to binary, the network part and the host part, the five address classes with their leading bits, first-octet ranges, numbers of networks and hosts (126 / 16 384 / 2 097 152 networks and 16 777 214 / 65 534 / 254 hosts), default masks, the special addresses (this network, limited and directed broadcast, loopback, private ranges, multicast), and why an address belongs to an interface and not to a host; counts are verified by enumeration and the address arithmetic against Python's ipaddress module.

CIDR and subnetting

Classless addressing with the a.b.c.d/n notation: the mask from the prefix length, the network and broadcast address, usable hosts 2^(32-n) - 2, splitting a block into equal subnets by borrowing host bits, variable-length subnet masks (VLSM) allocation largest first, route aggregation (supernetting) and when blocks can be merged, and forwarding by longest prefix match; every calculation was cross-checked with Python's ipaddress module on thousands of random cases.

IPv4 header and fragmentation

The IPv4 header fields (version, header length, total length, identification, flags DF and MF, fragment offset, TTL, protocol, header checksum, addresses), why a datagram larger than the MTU of a link is fragmented, how the offset (in 8-byte units) and the MF flag are set, fragmentation of fragments on smaller MTUs, reassembly only at the destination, the cost of fragmentation, the number of fragments formula and the effect of the DF flag; fragmentation was checked at byte level with random packets and MTU paths.

Network address translation

Why NAT exists (a shortage of public IPv4 addresses and private address blocks), how a NAT router with one public address translates both the address and the port number of outgoing packets, keeps a translation table and maps replies back, what happens to packets that arrive for an unknown port, how many simultaneous connections one public address can support, and the objections to NAT (breaking end-to-end addressing, servers behind NAT, protocols that carry addresses); the translation logic is simulated with a real table and checked for invertibility and exhaustion.

Distance vector routing

Routing as the problem of choosing next hops, the distance vector (Bellman-Ford) algorithm run by neighbouring routers exchanging vectors, the update rule D(x,y) = min over neighbours of c(x,v) + D(v,y), round-by-round convergence (after k rounds paths of at most k+1 links are known), the count-to-infinity problem when a link fails, and the partial cures split horizon and poison reverse (which fix two-router loops but not loops of three); RIP as the protocol example; every table is the output of a synchronous simulation checked against Floyd-Warshall.

Link state routing

Link state routing: every router measures the cost to its neighbours, floods a link state packet through the network, so that every router holds the same map (the link state database), and runs Dijkstra's algorithm on it to build a shortest path tree and a forwarding table; the number of copies transmitted when a packet is flooded (2E - (N - 1)), sequence numbers, comparison with distance vector routing (information, convergence, loops, message cost) and OSPF as the example; Dijkstra, forwarding tables and flooding counts were checked against Floyd-Warshall and Bellman-Ford on random networks.

TCP: segments, handshake and teardown

What TCP provides (a reliable, ordered byte stream between two processes over unreliable IP), the segment header fields and flags, sequence numbers that count bytes and acknowledgement numbers that name the next byte expected, the maximum segment size, the three-way handshake (SYN and FIN each use one sequence number), data transfer, the four-segment connection close and the main states of the TCP state machine, and the wrap-around time of the 32-bit sequence numbers; the segment exchange is generated by a model of the protocol with 32-bit arithmetic and checked on random transfers.

Sliding window: stop-and-wait, Go-Back-N, Selective Repeat

Reliable delivery over a lossy link with acknowledgements, timeouts and sequence numbers: stop-and-wait, the sliding window idea that keeps the pipe full, Go-Back-N (cumulative acknowledgements, receiver window 1, resend everything from the lost frame) and Selective Repeat (individual acknowledgements, receiver buffers, resend only the lost frame), the utilisation min(1, N / (1 + 2a)), the window needed to fill the pipe, and the limits on the window for k-bit sequence numbers (2^k - 1 and 2^(k-1)); animations come from a slotted simulation of the protocols.

TCP flow control

How TCP stops a fast sender from overflowing a slow receiver: the receive buffer and the advertised receive window rwnd = RcvBuffer - (LastByteRcvd - LastByteRead), the rule LastByteSent - LastByteAcked <= rwnd, the window field in every acknowledgement, the zero-window probe, the silly window syndrome, the throughput limit rwnd / RTT of a 16-bit window and the window scale option, and the difference from congestion control; a round-based simulation checks that the buffer never overflows and that the long-run rate is the slower of the application and the buffer per round.

TCP congestion control

How TCP avoids overloading the network: the congestion window cwnd, slow start (doubling per round trip up to ssthresh), congestion avoidance (additive increase of one segment per round trip), the reaction to loss - timeout (ssthresh = cwnd/2, cwnd = 1) and three duplicate acknowledgements (Tahoe restarts in slow start, Reno uses fast retransmit and fast recovery) - the AIMD sawtooth with average window 3W/4 and the throughput 1.22 MSS / (RTT sqrt(p)); the per-round tables come from a round-based model checked against a per-ACK model and the rules checked on random event sequences.

Switches, learning bridges and VLANs

Connecting LAN segments at the data link layer: hubs, bridges, switches and routers compared, collision domains and broadcast domains, how a learning bridge builds its address table by flooding, forwarding and filtering, the spanning tree protocol that removes loops (root bridge, root ports, designated ports, blocked ports) and VLANs with the 802.1Q tag.

ICMP, ARP and DHCP (supporting)

The three helper protocols around IP: ICMP (error reports and ping and traceroute), ARP (finding the MAC address of the next hop and why the MAC addresses change at every router while the IP addresses do not) and DHCP (getting an address, mask, gateway and DNS server automatically: the four messages and the lease timers).

RIP, OSPF and BGP overview

The three routing protocols of the Internet and where each fits: autonomous systems and the split between intra-domain and inter-domain routing, RIP (distance vector, hop count, UDP), OSPF (link state, cost, areas, designated router, carried directly in IP) and BGP (path vector, TCP, policy), with the facts GATE asks and the differences that the metrics make.

Socket API

How a program uses the network: the socket as a file-descriptor-like handle, the TCP server sequence socket - bind - listen - accept - recv/send - close and the client sequence socket - connect - send/recv - close, what bind, listen and accept really do (the handshake is completed by the kernel before accept, accept returns a new socket), why a TCP recv is not matched to a send (a byte stream has no message boundaries) while a UDP datagram is delivered as a unit, ports and the address-in-use error, and the TCP states seen from outside; the C programs on the page were compiled and run, and the TCP states come from a real conversation observed with netstat.

DNS

The Domain Name System: a distributed, hierarchical database that maps host names to IP addresses; the name hierarchy (root, top-level, second-level domains) and zones, name servers (root, TLD, authoritative, local), resource records (A, NS, CNAME, MX and others), the message format byte by byte (header, question, answer with name compression), recursive and iterative resolution, caching with time-to-live and its effect on the number of messages and the delay, and DNS over UDP port 53; the messages were encoded by code and decoded by the real dig program, and the resolution counts were recomputed independently.

HTTP

The Hypertext Transfer Protocol of the web: clients and servers, URLs, the request and response messages (request line, header lines, blank line, body; status line and status codes), methods, the stateless protocol and cookies, conditional GET and caching, non-persistent and persistent connections with and without pipelining, and the response-time arithmetic for a page with embedded objects (2 RTT per object without persistence); the messages come from a real server, the connection counts from real clients, and the times from a closed formula checked against an event timeline.

UDP and ports

The User Datagram Protocol: the 8-byte header, ports and how a host uses them to deliver a datagram to the right process, the checksum with its pseudo header, what UDP does not do (no connection, no retransmission, no ordering, no flow or congestion control), the size limits and fragmentation, and when to choose UDP instead of TCP.