Notes
Every lesson's rule card, grouped by layer, plus the one-page formula index below. Use it for last-week revision; each card links back to its lesson.
| Topic | Formula / rule | Lesson |
|---|---|---|
| Units | rates 10³ (kbps), sizes 2¹⁰ (KB); bits = bytes × 8 | 0.2.1 |
| Transmission / propagation | Tt = L/B · Tp = d/v (v = 2×10⁸ m/s) | 1.3.2 |
| Store-and-forward | (N + h − 1)·Tt + h·Tp (equal links) | 1.3.2 |
| RTT, a, send-and-wait | RTT = 2Tp · a = Tp/Tt · U = 1/(1 + 2a) | 1.3.3 |
| Circuit vs packet | setup + M/R + hTp vs (⌈M/p⌉ + h − 1)(p + H)/B + hTp | 1.3.4 |
| Hamming distance | detect d − 1 · correct ⌊(d − 1)/2⌋ · 2ʳ ≥ m + r + 1 | 2.2.2 |
| Checksum / CRC | 1's-complement sum, send complement · append r zeros, send remainder | 2.2.4 |
| ALOHA | pure G·e⁻²ᴳ (max 0.184) · slotted G·e⁻ᴳ (max 0.368) | 2.3.2 |
| CSMA/CD | Lmin = 2·Tp·B · backoff K ∈ {0..2^min(n,10) − 1} | 2.3.3 |
| Token ring | ETR 1/(1 + a/N) · DTR 1/(1 + a(N + 1)/N) | 2.3.5 |
| Ethernet | frame 64–1518 B, MTU 1500 · η = 1/(1 + 5a) | 2.4.2 |
| Subnetting / CIDR | block 2³²⁻ⁿ · hosts 2ʰ − 2 · subnets 2ˢ · longest prefix wins | 3.1.4 |
| Fragmentation | data per fragment ⌊(MTU − H)/8⌋·8 · offset in 8-byte units · MF = 1 except last | 3.2.2 |
| Routing | D_x(y) = min_v {c(x,v) + D_v(y)} · Dijkstra picks the closest tentative node | 3.4.2 |
| Sliding windows | η = min(1, N/(1 + 2a)) · GBN W ≤ 2ᵏ − 1 · SR W ≤ 2ᵏ⁻¹ | 4.2.4 |
| TCP numbers | SYN/FIN use 1 seq · wrap = 2³²·8/B · RTO = SRTT + 4·RTTVAR | 4.3.4 |
| TCP congestion | SS: cwnd = min(2cwnd, ssthresh) · CA +1/RTT · timeout: ssthresh = ⌊cwnd/2⌋, cwnd = 1 | 4.3.5 |
| HTTP RTTs | non-persistent 2(N+1) · persistent 2 + N · pipelined 3 (+ DNS) | 5.3 |
Toolkit (units, binary, bit operations, probability)
- Network = devices + links that exchange data.
- Host = where a message starts or ends (laptop, phone, server).
- Link = physical path: copper (voltage), fibre (light), wireless (radio).
- All content → bits → signals → bits → content; meaning comes from an agreed encoding.
- One link per pair of n hosts: n(n − 1)/2 links — too many, so links are shared.
- Node = any device; host = node where messages start/end.
- Point-to-point (2 nodes) vs broadcast (all hear all).
- Simplex (one way) · half-duplex (two ways, one at a time) · full-duplex (both at once).
- Links: mesh n(n−1)/2, star n, ring n, tree n−1, bus 1 backbone.
- LAN (building) ⊂ WAN (cities) ⊂ the Internet (network of networks).
- Hub repeats to all · switch delivers within a LAN · router picks the next network.
- 1 B = 8 b. Lower-case b = bit, upper-case B = byte.
- Rates: k = 10³, M = 10⁶, G = 10⁹ (bps).
- Sizes: K = 2¹⁰, M = 2²⁰, G = 2³⁰ (bytes) — unless the question says 1000.
- Time to push out = (size in bits) ÷ (rate in bit/s).
- ms = 10⁻³ s, µs = 10⁻⁶ s, ns = 10⁻⁹ s.
- Binary places: 1, 2, 4, 8, 16, 32, 64, 128, …; MSB left, LSB right.
- Hex: one digit = 4 bits; A–F = 10–15; group from the right.
- k bits → 2ᵏ values, 0 … 2ᵏ − 1.
- Bits needed for N values = smallest k with 2ᵏ ≥ N.
- 2¹⁰ = 1024 · 2¹⁶ = 65,536 · 2²⁰ ≈ 1.05 M · 2³² ≈ 4.29 × 10⁹.
- AND (mask), OR, NOT (flip), XOR (1 where bits differ).
- a ⊕ a = 0, a ⊕ 0 = a, (a ⊕ k) ⊕ k = a.
- 1's complement = flip all bits; 1's-complement addition wraps the end carry back in.
- Modulo-2: + = − = XOR, no carries; bits ↔ polynomial.
- Mod-2 division: leading 1 → XOR divisor; leading 0 → XOR zeros; remainder = (divisor length − 1) bits.
- 2ᵃ·2ᵇ = 2ᵃ⁺ᵇ; 2¹⁰ ≈ 10³ (estimates only).
- log₂ x = power of 2 giving x; bits for N values = ⌈log₂ N⌉.
- P(none) = (1−p)ⁿ · P(≥ 1) = 1 − (1−p)ⁿ · P(exactly 1) = n·p·(1−p)ⁿ⁻¹.
- (1 − 1/n)ⁿ → 1/e ≈ 0.368; 1/(2e) ≈ 0.184.
- 1 + 2 + … + 2ᵏ⁻¹ = 2ᵏ − 1; expected tries = 1/p.
Layering, switching and delay — the physical path
- Layer: one job in the stack; serves the layer above, uses the layer below.
- Protocol: rules between peers (same layer, different machines): format, meaning, behaviour.
- Service: what a layer does for the layer above. Interface: how the layer above asks for it.
- Peer talk is logical; the real path is down → link → up.
- Layering = modularity + reuse − some overhead.
- OSI bottom-up: Physical, Data link, Network, Transport, Session, Presentation, Application.
- Scope: link → hop → host-to-host → process-to-process.
- Routers: layers 1–3; hosts: 1–7.
- TCP/IP (5): application (= OSI 5–7), transport, network, data link, physical.
- Encryption/compression = presentation; dialogue control = session.
- Encapsulation: payload + header (+ trailer at data link); decapsulation in reverse.
- PDUs: message (app) → segment (transport) → packet/datagram (network) → frame (data link) → bits.
- Addresses: link (per hop, changes) · network (end to end, fixed) · which-program id · names.
- Devices: hub/repeater 1 · bridge/switch 2 · router 3 · gateway/host up to 7.
- Efficiency = data / (data + all headers + trailer).
- Circuit switching: setup → data transfer → teardown.
- Dedicated path; each link's share (time slot or frequency band) is reserved: circuit rate = R/n.
- Total time = setup + bits/circuit rate (+ travel time if given).
- + guaranteed rate, in order, no queues; − setup delay, idle capacity wasted, fragile.
- Packet switching: packets with headers; no reservation; full link rate while sending.
- Store-and-forward: receive whole packet → buffer/queue → forward; full buffer → loss.
- Datagram: each packet routed independently; may reorder; robust to failures.
- Statistical multiplexing: share capacity on demand; P(exactly k of n) = C(n,k)pᵏ(1−p)ⁿ⁻ᵏ.
- Virtual circuit: setup chooses a path, switches store (in-link, in-VCI → out-link, out-VCI); packets carry short VCIs; no link capacity reserved.
- Connection-oriented: circuit, VC. Connectionless: datagram.
- Setup? reserved? per-packet routing? → circuit Y/Y/N · VC Y/N/N · datagram N/N/Y.
- Order kept by circuit and VC; datagrams may reorder.
- Bandwidth / data rate B = link capacity in bps (decimal prefixes).
- Tt = L / B (L in bits) — independent of distance.
- Throughput = bits delivered / time ≤ min link rate on the path (bottleneck).
- Tp = d / v, v = 2 × 10⁸ m/s default; independent of size and rate.
- Nodal delay = d_proc + d_queue + Tt + Tp.
- One packet, h equal links: h·Tt + h·Tp.
- N packets, h equal links: (N + h − 1)·Tt + h·Tp (+ (h − 1)·d_proc).
- Unequal links: first packet ΣTt + ΣTp, then + (N − 1) × max Tt.
- Traffic intensity L·a/R → 1: queues explode.
- RTT = 2·Tp for tiny signals (add Tt / queuing if stated).
- BDP = B × Tp bits in flight; B × RTT before any reply.
- a = Tp / Tt.
- Send-and-wait: U = Tt/(Tt + 2Tp) = 1/(1 + 2a); throughput = U·B.
- To keep the link busy: about 1 + 2a units in flight.
- Circuit: setup + M/R + h·Tp.
- Message switching: h·(M + H)/B + h·Tp.
- Packet switching: (⌈M/p⌉ + h − 1)·(p + H)/B + h·Tp.
- Optimal p ≈ √(M·H/(h − 1)); in MCQs evaluate each option.
Data link layer — error detection, MAC, Ethernet
- Data link layer = hop-to-hop delivery of frames to the next directly connected node.
- Jobs: framing, link addressing, error detection, medium access (+ error/flow control).
- MAC address: 48 bits, 6 bytes, 12 hex digits; 24-bit vendor prefix; flat.
- A new frame (new MAC addresses) is built on every link; the packet inside is unchanged.
- Foundation: bit stuffing inserts a 0 after five consecutive 1s.
- Single-bit vs burst; burst length = first to last damaged bit inclusive.
- Codeword = dataword (k) + r check bits.
- 1-D parity: detects odd numbers of flips only.
- 2-D parity: R + C + 1 check bits; detects all 1–3-bit errors, corrects 1, misses some 4-bit rectangles.
- d(x, y) = number of 1s in x ⊕ y; d_min = smallest over codeword pairs.
- Detect d_min − 1; correct ⌊(d_min − 1)/2⌋.
- Detect s needs d ≥ s + 1; correct t needs d ≥ 2t + 1.
- Hamming code: smallest r with 2ʳ ≥ m + r + 1.
- 16-bit words; checksum field = 0 while summing.
- Sum with 1's-complement addition (wrap carries); checksum = complement of the sum.
- Receiver: sum of all words + checksum = 0xFFFF → accept.
- Misses word reordering and compensating errors.
- G of degree r (r + 1 bits); append r zeros, divide modulo 2, send data + r-bit remainder.
- Receiver divides the whole frame: remainder 0 → accept.
- Undetected ⇔ error pattern E is a multiple of G.
- Catches: all single-bit errors (≥ 2 terms), all odd counts (x + 1 | G), all bursts ≤ r; (r+1)-bursts missed w.p. 2⁻⁽ʳ⁻¹⁾, longer 2⁻ʳ.
- Collision: overlapping transmissions on a shared link; all involved frames lost.
- MAC families: partitioning (TDMA/FDMA), random access (send freely, recover from collisions), taking turns (an orderly schedule).
- TDMA/FDMA: R/N per station, no collisions, idle shares wasted, wait up to (N − 1) slots.
- T = frame time; G = attempts per T.
- Pure: vulnerable 2T, S = G·e⁻²ᴳ, max 1/(2e) ≈ 0.184 at G = 0.5.
- Slotted: vulnerable T, S = G·e⁻ᴳ, max 1/e ≈ 0.368 at G = 1.
- Finite N: P(success) = N·p·(1 − p)ᴺ⁻¹.
- CSMA: sense before sending; collisions still possible within T_p.
- 1-persistent / non-persistent / p-persistent: what to do when busy.
- CSMA/CD: listen while sending; on collision jam, stop, back off.
- L_min = 2·T_p·B; d_max = L_min·v/(2B); i.e. T_t ≥ 2T_p.
- CSMA/CA (Foundation): wireless avoids collisions instead of detecting them.
- After the n-th collision: K uniform in {0, …, 2^min(n,10) − 1}; wait K × slot; abort after 16.
- Slot = 512 bit times (51.2 µs at 10 Mbps).
- P(A wins) = #{K_A < K_B} / (a·b); both at range 2: win 1/4, tie 1/2.
- Capture: A at range 2 vs B at range 4 → A wins 5/8.
- Polling: primary asks each station; η = T_t/(T_t + T_poll); single point of failure.
- Token passing: only the token holder sends (token holding time).
- Ring latency = d/v + N·b/R.
- ETR η = 1/(1 + a/N); DTR η = 1/(1 + a(N+1)/N).
- Frame: preamble 7 + SFD 1 | dest 6 | src 6 | type/len 2 | data 46–1500 | CRC 4.
- Frame 64–1518 bytes (preamble excluded); pad data to 46.
- MTU = 1500 bytes.
- First-byte LSB 1 → multicast; FF:…:FF → broadcast; else unicast.
- 64 bytes = 512 bits = CSMA/CD slot time at 10 Mbps.
- Shared Ethernet efficiency η = 1/(1 + 5a) (course default); variants 1/(1 + 5.44a), 1/(1 + 6.44a).
- Switched full-duplex: no collisions, no CSMA/CD, full rate per link.
- Collision domains: hub = 1; switch/router = 1 per interface.
- Broadcast domains: only routers split them.
Network layer — IPv4, CIDR, fragmentation, NAT, routing
- IPv4 address = 32 bits = 4 octets (0–255 each), total space = 2³².
- Split: Net-ID (left n bits) + Host-ID (right h = 32 − n bits).
- Identifies a network interface (routers have one IP per link).
- Classes by 1st octet: A = 0–127 (
0, 8 net bits), B = 128–191 (10, 16 net bits), C = 192–223 (110, 24 net bits), D = 224–239 (1110, multicast), E = 240–255 (1111, reserved). - Usable hosts = 2ʰ − 2 (exclude host all-0s = network address, host all-1s = directed broadcast).
- Specials:
0.0.0.0= this host (src only);255.255.255.255= limited broadcast (local LAN only);127.x.y.z= loopback.
- Borrow s bits from host field, leaving h bits → 2ˢ subnets, each with 2ʰ − 2 usable hosts.
- Subnet address =
IP AND Mask; Broadcast = host bits all1s. - Stride Δ = 256 − Mask octet: blocks start at
0, Δ, 2Δ, …and end atΔ−1, 2Δ−1, …. - Valid mask octets: 128, 192, 224, 240, 248, 252, 254, 255.
- CIDR
a.b.c.d/n: n prefix bits, h = 32 − n host bits, block size N = 2ʰ. - Alignment rule: first address must be divisible by 2ʰ (for
/(24−k), 3rd octet must be divisible by 2ᵏ). - Supernetting: 2ᵏ contiguous, aligned
/nblocks merge into one/(n − k)block.
- Match condition: Row
N/n(maskM) matches destinationDiff(D AND M) == N(i.e.Dfalls in[N .. N + 2³²⁻ⁿ − 1]). - Longest Prefix Match (LPM): Among all matching rows, pick the one with the largest prefix length n.
- Default route
0.0.0.0/0: matches every address with n = 0 (used only if nothing else matches).
- Block size for H usable hosts: smallest 2ʰ with 2ʰ − 2 ≥ H; prefix =
/(32 − h). - Largest-first rule: sort subnets by decreasing 2ʰ and allocate sequentially so every block is naturally aligned.
- Non-overlap: sum of block sizes ∑ 2ʰᵢ ≤ 2³²⁻ⁿ_parent, and every block starts on a multiple of its own 2ʰᵢ.
- Base header = 20 B (`HLEN = 5`); Max header = 60 B (`HLEN = 15`, max 40 B options).
- Multipliers: `Header = 4 × HLEN`, `Total Length = Header + Payload` (max 65,535 B), `Offset × 8 = start byte`.
- Per-hop changes: Every router decrements TTL by 1 (drops if 0) and recomputes Header Checksum (which covers IP header only).
- Max data per fragment:
d_max = ⌊(MTU − H)/8⌋ × 8(must be a multiple of 8 B). - Offset =
start_byte / 8(relative to original datagram); MF = 1 on all fragments except the very last of the original datagram (MF = 0). - Original payload from last fragment (MF=0):
8 × Offset + (TotalLength − 4×HLEN). - Reassembly: ONLY at final destination host.
- Private IPv4 ranges:
10.0.0.0/8,172.16.0.0/12(172.16..31.x.y),192.168.0.0/16. - NAPT table: maps
(Private IP, Private Port) ↔ (Public IP, NAT Port). - Rewrites: Outgoing → Source IP + Source Port; Incoming → Destination IP + Destination Port (+ checksums).
- Forwarding = local per-packet lookup (data plane); Routing = network-wide shortest-path computation (control plane).
- Graph model: routers = vertices V, links = edges E with positive cost c(u, v).
- Routing table entry at u for d: stores
(Destination d, Cost D_u(d), Next Hop = first neighbour along shortest path).
- Bellman-Ford:
Dₓ(y) = min_{v ∈ N(x)} { c(x, v) + D_v(y) }. - DV message: contains
[(y, Dₓ(y))]for all destinations y; sent only to immediate neighbours. - If the current next-hop's distance increases, recompute that branch before taking the minimum.
- Count-to-infinity: Bad news (link failure) causes neighbours to bounce increasing costs back and forth; RIP caps this with infinity = 16 (max valid hops = 15).
- Split Horizon: Do not advertise a route back to the next-hop neighbour v*.
- Poison Reverse: Advertise
Dₓ(y) = ∞to the next-hop neighbour v* (fixes 2-node loops, not 3+ node loops).
- LSP contents:
(Router ID, Direct Neighbours & Costs, Sequence #, Age)— distributed to all routers via controlled flooding. - Dijkstra: Greedily add min-D(u) node to permanent set N', then relax neighbours:
D(v) = min(D(v), D(u) + c(u, v)); time O(V²) or O((V+E) log V). - Next hop from source s to d = first node after s on the path traced backwards via
prev[].
- DV (Bellman-Ford, RIP): sends all |V| distances to neighbours only; partial topology; vulnerable to count-to-infinity (∞ = 16).
- LS (Dijkstra, OSPF): floods direct neighbour costs only (LSP) to all routers; full topology; O(V²) local compute; no count-to-infinity.
- Both can oscillate if link cost = traffic load.
Transport layer — sliding windows and TCP
- Delivery: Network Layer = host-to-host; Transport Layer = process-to-process.
- Port number = 16 bits (0–65,535): Well-known
0–1023, Registered1024–49151, Ephemeral49152–65535. - Demultiplexing: UDP uses 2-tuple
(DstIP, DstPort); TCP uses 4-tuple(SrcIP, SrcPort, DstIP, DstPort). - UDP (Foundation) = 8-byte header, connectionless, best-effort; TCP = connection-oriented, reliable, flow + congestion controlled.
- Stop-and-Wait ARQ: 1 packet in flight; uses 1-bit sequence numbers (0, 1) to discard duplicates when ACKs are lost.
- Utilisation:
η = Tt / (Tt + 2·Tp) = 1 / (1 + 2a), wherea = Tp / Tt(with losses of prob p:(1 − p)/(1 + 2a)). - Throughput:
η × B = L / (Tt + 2·Tp).
- Sliding-window utilisation:
η = min(1, N / (1 + 2a)); full utilisation atN = ⌈1 + 2a⌉. - k-bit sequence space:
0 .. 2ᵏ − 1(2ᵏ numbers); universal bound:Ws + Wr ≤ 2ᵏ.
- Go-Back-N bounds:
Wr = 1,Ws ≤ 2ᵏ − 1⇒ minimum bits for window N isk = ⌈log₂(N + 1)⌉. - Cumulative ACK: confirms all frames up to that number (survives lost earlier ACKs).
- On loss of frame f: receiver discards
f+1 .. min(M, f+N−1); sender times out and retransmits from f.
- Selective Repeat bounds:
Ws = Wr ≤ 2ᵏ⁻¹⇒ minimum bits for window N isk = ⌈log₂(2N)⌉. - Receiver: buffers out-of-order frames within Wr; sends selective ACKs / NAKs; delivers in order to upper layer.
- Every K-th tx lost (M frames): Total transmissions in SR =
M + ⌊(M − 1) / (K − 1)⌋.
- TCP Header: 20–60 B (`HLEN × 4`); 16b Src/Dst Ports, 32b Seq #, 32b Ack #, 6 Flags (`URG, ACK, PSH, RST, SYN, FIN`), 16b Window, 16b Checksum.
- Byte numbering: segment at `Seq = S` with L bytes covers `S .. S + L − 1`; receiver sends cumulative `ACK = S + L` (next expected byte).
- `MSS` = max TCP data payload per segment (`MTU − IP_hdr − TCP_hdr`).
- 3-way handshake:
SYN(seq=x) → SYN+ACK(seq=y, ack=x+1) → ACK(seq=x+1, ack=y+1). - Seq consumption:
SYN = +1,FIN = +1,Pure ACK = 0,Data(L) = +L(full connection advances byD + 2). - Teardown states: Active closer goes
FIN-WAIT-1 → FIN-WAIT-2 → TIME-WAIT (2·MSL) → CLOSED; Passive closer goesCLOSE-WAIT (half-close) → LAST-ACK → CLOSED.
- Flow control:
rwnd = RcvBuffer − (LastByteRcvd − LastByteRead); sender keepsBytesInFlight ≤ rwnd. - Zero window (`rwnd = 0`): sender runs Persist Timer and sends 1-byte Zero-Window Probes.
- Wrap-around time:
T_wrap = (2³² × 8) / Bseconds (34.36 s at 1 Gbps). - Window scaling:
True rwnd = HeaderWindow × 2ˢ(S ≤ 14, negotiated inSYN).
- EWMA:
Est_new = (1 − α)·Est_old + α·Sample = Est_old + (Sample − Est_old)·α(defaultα = 1/8). - Deviation & RTO:
Dev_new = (1 − β)·Dev_old + β·|Sample − Est|(defaultβ = 1/4);RTO = Est + 4·Dev. - Karn's rule: ignore RTT samples from retransmitted segments; double
RTOon each timeout.
- Effective window:
W = min(cwnd, rwnd). Always trace in units of MSS! - Slow Start (
cwnd < ssthresh):+1 MSSper ACK →cwnd ← min(2·cwnd, ssthresh)per RTT. - Congestion Avoidance (
cwnd ≥ ssthresh):+1 MSSper RTT (AIMD linear growth). - On Loss:
ssthresh ← ⌊cwnd / 2⌋; Timeout →cwnd = 1 MSS; 3 Dup ACKs →cwnd = 1 MSS(Tahoe) orcwnd = ssthresh(Reno).
- TCP Server order:
socket() → bind() → listen() → accept() → recv()/send() → close(). - TCP Client order:
socket() → connect() → send()/recv() → close()(OS auto-binds ephemeral port). - UDP Server / Client: no
listen()oraccept(); usesrecvfrom() / sendto()on a single bound socket. - Blocking calls:
connect(),accept(), andrecv()block by default;listen()does NOT block.
Application layer — DNS and HTTP
- Client initiates; server listens at a well-known port and answers.
- Application protocol = message types + syntax + semantics + rules + transport/port choice.
- Server sockets = 1 listening + 1 per connection.
- P2P: peers serve each other; client-server distribution ≥ N·F/u_s.
- Hierarchy: root → TLD → authoritative; local resolver works for hosts and caches.
- Recursive (server chases) vs iterative (referrals); full lookup = 8 messages.
- Lookup time = Σ RTT of servers actually contacted.
- Records: A, AAAA, NS, CNAME, MX; TTL for caching.
- Transport: UDP 53 (normal), TCP 53 (zone transfer / large).
- HTTP: request (method, path, version, headers, body) / response (status, headers, body); TCP 80; URL = protocol + host + path.
- Methods GET, POST, HEAD, PUT, DELETE; codes 2xx ok, 3xx redirect (301, 304), 4xx client (404), 5xx server.
- Stateless; cookies via Set-Cookie / Cookie.
- RTTs (base + N small): non-persistent 2(N+1); k-parallel 2 + 2⌈N/k⌉; persistent 2 + N; pipelined 3. Add DNS first.
- Order: DHCP (address, gateway, DNS server) → ARP (gateway MAC) → DNS (UDP 53) → TCP handshake (port 80) → HTTP GET/200 OK.
- Minimum to first byte (cached DNS/ARP): 2 RTT + transmission.
- IP fixed end to end (NAT rewrites at the edge); MAC changes per hop; CRC per hop; fragments reassembled at the destination.