Final review sheet
Every question type with an example + answer · short-answer bank · traps · links go to the full topic
1. Formula sheet (memorize, no cheat sheet allowed)
| What | Formula | Topic |
|---|---|---|
| Circuit-switching users | C / r (link rate ÷ rate per user) | 2 |
| P(exactly k of N active) | C(N,k) · pk · (1−p)N−k | 2 |
| P(≥ m active) | Σk=mN C(N,k) pk(1−p)N−k = 1 − Σk=0m−1 … | 2 |
| Nodal delay | dproc + dqueue + dtrans + dprop | 3 |
| Transmission / propagation | dtrans = L/R · dprop = m/s | 3 |
| Traffic intensity | La/R (→ 1: delay blows up; > 1: infinite) | 3 |
| Avg queuing, N arrive at once | (N−1)L / 2R | 3 |
| No segmentation, N links | N · M/R | 4 |
| Segmentation, P packets | (N + P − 1) · L/R (L includes header) | 4 |
| Throughput | min(Rs, Rc, R/n) · time = F / throughput | 5 |
| Bandwidth-delay product | R · dprop · width of a bit = s/R | 5 |
| HTTP non-persistent, 1 object | 2 RTT + L/R | 8 |
| Page with k objects | DNS (RTT1+…+RTTn) + 2RTT0 + [k·2RTT0 | ⌈k/p⌉·2RTT0 | k·RTT0 | RTT0] | 8 |
| Access delay (caching) | Δ / (1 − Δβ), Δ = object size / Raccess, β = requests/s | 9 |
| Client-server distribution | Dcs = max{ NF/us, F/dmin } | 11 |
| P2P distribution | DP2P = max{ F/us, F/dmin, NF/(us + Σui) } | 11 |
| Checksum | add → wrap carry → flip bits | 14 |
| Sender utilization | U = (N · L/R) / (RTT + L/R), N = 1 for stop-and-wait | 16 |
| Max window, k-bit seq # | GBN: 2k − 1 · SR: 2k−1 | 15 |
Units: k = 10³, M = 10⁶, G = 10⁹ · bytes × 8 = bits · km × 1000 = m · ms = 10⁻³ s, µs = 10⁻⁶ s · RTT = 2 × one-way propagation.
2. Calculation question types
Type A · Circuit vs packet switching users (topic 2 · sample P3, HW1 P8)
Q: 3 Mbps link, each user needs 150 kbps when active, active 10% of the time. (a) Circuit-switched users? (b) 100 users: P(20 or more active)?
A: (a) 3000/150 = 20 users. (b) Σk=20100 C(100,k)(0.1)k(0.9)100−k. A formula is enough. Watch "20 or more" (start at 20) vs "more than 20" (start at 21).
Type B · End-to-end delay over several links (topic 3 · HW1 P4)
Q: 1500-byte packet, 3 links of 2 Mbps, s = 2.5×10⁸ m/s, lengths 5000/4000/1000 km, 2 routers each with dproc = 3 ms. Delay?
A: L = 12,000 bits → 6 ms per link (×3 = 18). Propagation 20 + 16 + 4 = 40. Processing 2 × 3 = 6. 64 ms.
Type C · Where's the bit / when do delays match (topic 3 · HW1 P2)
Q: L = 120 bits, R = 56 kbps, s = 2.5×10⁸. Distance where dprop = dtrans?
A: m = L·s/R = 120 × 2.5×10⁸ / 56,000 ≈ 536 km. At t = dtrans the last bit is just leaving A. If dprop > dtrans the first bit is still in the link; if smaller, it's already at B.
Type D · Packetization delay (VoIP) (topic 3 · HW1 P3)
Q: 64 kbps voice, 56-byte packets, 2 Mbps link, 10 ms propagation. Bit creation → decoding?
A: Fill the packet 448/64,000 = 7 ms + transmit 448/2×10⁶ = 0.224 ms + propagate 10 ms = 17.224 ms.
Type E · Queuing (topic 3 · HW1 P5)
Q: 6 packets of 1500 bytes arrive at once at an empty 10 Mbps link. Average queuing delay?
A: (N−1)L/2R = 5 × 12,000 / (2 × 10⁷) = 3 ms. (Same answer if a batch arrives every LN/R.)
Type F · Message segmentation (topic 4 · sample P2, HW1 P7)
Q: 8×10⁶-bit message, 4 routers, 1.6 Mbps links. (a) No segmentation? (b) 5000 packets of 1600 bits + 160-bit header?
A: 5 links. (a) 5 s/hop × 5 = 25 s. (b) L = 1760 → 1.1 ms; (5 + 5000 − 1) × 1.1 ms = 5.5044 s.
Type G · Throughput / BDP (topic 5 · HW1 P6)
Q: 20,000 km link, R = 2 Mbps, s = 2.5×10⁸. BDP? Max bits in the link for an 800,000-bit file? Width of a bit?
A: dprop = 0.08 s → BDP = 160,000 bits = max bits in link (min of file and BDP). Width = s/R = 125 m (longer than a football field).
Type H · HTTP response time (topic 8 · HW2 P0, P2)
Q: DNS visits n servers. Base HTML + 8 small objects on the same server. (a) Non-persistent serial? (b) 6 parallel? (c) Persistent?
A: (a) 18 RTT0 + ΣRTTi. (b) 2 + ⌈8/6⌉×2 = 6 RTT0 + ΣRTTi. (c) pipelined 2 + 1 = 3 RTT0 + ΣRTTi (no pipelining: 10 RTT0). Base HTML always costs 2 RTT0.
Type I · Web caching (topic 9 · HW2 P3)
Q: 900,000-bit objects, 15 Mbps access link, 16 req/s, Internet delay 3 s. (a) No cache? (b) Cache, miss rate 0.4?
A: Δ = 0.06 s, Δβ = 0.96 → access 0.06/0.04 = 1.5 s → 4.5 s. (b) 0.06/(1 − 0.4×0.96) ≈ 0.097 s; avg = 0.6×0 + 0.4×(3.097) ≈ 1.24 s.
Type J · P2P vs client-server (topic 11 · HW2 P5)
Q: F = 20 Gbits, us = 30 Mbps, d = 2 Mbps, N = 100, u = 300 kbps. Dcs? DP2P?
A: F = 20,000 Mbits. Dcs = max{100×20,000/30, 10,000} = 66,667 s. DP2P = max{667, 10,000, 2,000,000/(30 + 30)} = 33,333 s.
Type K · Internet checksum (topic 14 · HW3 P2)
Q: 01010011, 01100110, 01110100. 1s complement of the sum?
A: 01010011 + 01100110 = 10111001 → + 01110100 = 100101101 → wrap: 00101110 → flip: 11010001. Receiver adds all + checksum → 11111111 if OK. 1-bit errors always caught; 2-bit errors can cancel.
Type L · Utilization / window size (topic 16 · HW3 P4)
Q: 1 Gbps, 15 ms one-way, 1500-byte packets. Window for U > 98%?
A: L/R = 0.012 ms, RTT = 30 ms. N × 0.012 / 30.012 > 0.98 → N > 2450.98 → N = 2451.
Type M · GBN max window with example (topic 15 · sample P4, HW3 P7)
Q: k-bit seq #s. Max GBN window? Explain with k = 2. (No example = no points.)
A: 2k − 1 = 3. W = 4 fails: send 0,1,2,3 → receiver gets all, ACKs, expects new 0 → all ACKs lost → sender resends old 0 → receiver accepts it as new. ✗ W = 3: send 0,1,2 → receiver expects 3 → ACKs lost, old 0 resent → receiver expects 3, so it discards 0. ✓
Type N · GBN window positions (topic 15 · HW3 P5)
Q: GBN, window 4, receiver expects k. Possible sender windows? ACKs in flight?
A: Base from k−4 to k: [k−4,k−1] … [k,k+3]. ACKs in flight: k−5 to k−1.
3. "Explain / design" question types
| Question | Answer |
|---|---|
| Scheme for D = NF/us when us/N ≤ dmin (sample P6) | Server sends to all N clients in parallel at us/N each (total = us). Clients can take that rate since us/N ≤ dmin. Each finishes in F/(us/N) = NF/us, all at once. |
| Scheme for D = F/dmin when us/N ≥ dmin (HW2 P6b) | Send to all N in parallel at dmin each. Total N·dmin ≤ us, so it's allowed. Each finishes in F/dmin. |
| Traceroute: why do the 3 delays to one router differ? (sample P5a) | Queuing delay varies with congestion at each moment. |
| Traceroute: why the big jump 22 → 104 ms? (sample P5b) | Trans-oceanic link (NYC → Europe): large propagation delay. |
| Traceroute: why can a later router show less delay? | Separate measurements at different moments, so different queuing delays. |
| Steady-rate, long-running app: circuit or packet? (HW1 P1) | Circuit: predictable rate, reserve exactly what's needed, setup cost spread over the long session. If total rate < every link's capacity, no congestion control needed. |
| Other reasons to segment / drawbacks (HW1 P7) | + a bit error resends one packet, not the whole message; small packets don't wait behind huge ones. − must reorder at destination; more header overhead. |
| SMTP vs HTTP end of message (HW2 P4) | SMTP: line with only "." (CRLF.CRLF). HTTP: Content-Length header. HTTP can't use SMTP's way: binary body could contain CRLF.CRLF; SMTP is 7-bit ASCII only. |
| Protocols needed when the server IP is unknown (HW2 P1) | App: DNS + HTTP. Transport: UDP for DNS, TCP for HTTP. |
| Free-rider in BitTorrent (HW2 P7) | Can get the file via others' optimistic unchoking (if peers stay). With many machines: run a client on each, combine the chunks, have each ask for different chunks (Sybil attack). |
| NAK-only protocol (HW3 P3) | Infrequent data: worse (loss only noticed when the next packet shows a gap). Lots of data, few losses: better (gaps noticed fast, far fewer feedback messages). |
| Server → client ports and IPs (HW3 P1) | Swap the request: src port 80, dst port = client's port; src IP = server, dst IP = client. |
| ACK outside the window: possible? (HW3 P6) | True for both SR and GBN: premature timeout → duplicate packets → duplicate ACKs arrive after the window moved. Alternating-bit = SR with window 1 = GBN with window 1 (both true). |
4. Short-answer bank (1–2 sentences each)
Chapter 1
| Question | Answer |
|---|---|
| What does a protocol define? | The format and order of messages exchanged, and the actions taken on sending/receiving. |
| Cable vs DSL? | Cable: neighborhood shares one coax. DSL: each home has its own phone line to the central office. |
| Why is the Internet a hierarchy of ISPs? | Connecting every ISP to every other is O(N²); instead access → regional → tier-1, plus IXPs and peering. |
| Packet sniffing vs IP spoofing vs DDoS? | Sniffing: reading packets on a shared medium. Spoofing: fake source address. DDoS: flooding a target from many (botnet) hosts. |
| Circuit vs packet switching: one pro and con each | Circuit: + guaranteed rate; − idle reserved bandwidth is wasted. Packet: + efficient for bursty traffic, more users; − congestion (delay, loss). |
| FDM vs TDM? | FDM: own frequency band all the time. TDM: whole band, only in your time slot. |
| Store-and-forward? | A router must receive the whole packet before forwarding it. |
| Transmission vs propagation delay? | Transmission L/R: pushing bits onto the link (depends on size, rate). Propagation d/s: one bit traveling the wire (depends on distance). |
| Which delay varies the most? | Queuing (depends on congestion). |
| Traffic intensity > 1? | Queue grows without bound → infinite delay / loss. |
| Why is packet loss possible? | Router buffers are finite; packets arriving at a full buffer are dropped. |
| What is the bottleneck link? | The slowest link on the path; it sets end-to-end throughput. |
| Meaning of the bandwidth-delay product? | The max number of bits that can be in the link at once. |
| Which layer does routing? (sample 1b) | Network layer. |
| 5 layers + data units | Application (message), Transport (segment), Network (datagram), Link (frame), Physical. |
| Layers in a router? Switch? Host? | Router 3 (network, link, physical). Switch 2 (link, physical). Host all 5. |
| OSI layers missing from the Internet stack? | Presentation (interpret data: encryption, compression) and Session (sync, checkpointing, recovery). Apps implement them if needed. |
| Pro and con of layering? | + modular, change one layer without affecting others. − duplicated functionality; a layer may need info hidden in another. |
| Encapsulation? | Each layer adds its header going down (M → HtM → HnHtM → HlHnHtM); the receiver strips them going up. |
Chapter 2
| Question | Answer |
|---|---|
| How to uniquely identify a process? (sample 1a) | IP address + port number (IP → host, port → process on it). |
| Client-server vs P2P? | C-S: always-on server with permanent IP, clients don't talk to each other. P2P: no always-on server, peers talk directly, self-scalable but hard to manage. |
| Client process vs server process? | Client initiates contact; server waits to be contacted. |
| What is a socket? | The door between the app process and the transport layer. |
| What does an app-layer protocol define? | Message types, syntax, semantics, and rules for when/how to send and respond. |
| What do TCP and UDP not provide? | Timing, throughput guarantees, security. |
| Why do we need UDP? (sample 1c) | No connection setup (no RTT delay), no connection state, small 8-byte header, no congestion control (send as fast as wanted). |
| What is TLS / where does it live? | Encrypted TCP connections, integrity, authentication. Implemented in the application layer (libraries over TCP). |
| HTTP is "stateless" means? | The server keeps no info about past client requests. |
| How do sites keep state anyway? | Cookies: Set-cookie in the response, Cookie in later requests, cookie file in the browser, back-end database at the site. |
| Persistent vs non-persistent HTTP? | Non-persistent: one object per TCP connection (2 RTT each). Persistent: connection stays open for many objects (as little as 1 RTT for all). |
| What is pipelining (HTTP)? | Sending all requests back-to-back without waiting for each response. |
| GET vs POST vs HEAD vs PUT? | GET: request object (data in URL after ?). POST: data in the body. HEAD: headers only. PUT: upload/replace a file. |
| 301 vs 404 vs 304? | 301 moved permanently (Location: header). 404 not found. 304 not modified (conditional GET). |
| HOL blocking and HTTP/2's fix? | Small objects wait behind a big one (FCFS). HTTP/2 splits objects into frames and interleaves them, plus priorities and server push. |
| HTTP/3 transport? | QUIC over UDP (per-object error and congestion control, security). |
| Why use a Web cache? | Lower response time (closer), less traffic on the access link; cheaper than upgrading the link. |
| Why is a cache both client and server? | Server to the browser, client to the origin server. |
| Conditional GET? | Cache sends If-modified-since: date; server replies 304 Not Modified (no object) or 200 OK with the new object. |
| 3 email components; SMTP port? | User agents, mail servers, SMTP. SMTP: TCP port 25. |
| SMTP push or pull? HTTP? | SMTP push, HTTP pull. |
| Why does Bob need IMAP? | SMTP only delivers to a server (push); IMAP (or HTTP webmail) retrieves from it. |
| Why not centralize DNS? | Single point of failure, traffic volume, distant database, maintenance. Doesn't scale. |
| DNS hierarchy? | Root → TLD → authoritative. Local DNS server isn't strictly in it; it's the ISP's default server and acts as a proxy with a cache. |
| Iterated vs recursive query? | Iterated: each server says "ask this one next". Recursive: each server resolves on your behalf, heavy load on upper levels. |
| A / NS / CNAME / MX? | A: hostname → IP. NS: domain → authoritative name server. CNAME: alias → canonical name. MX: name → mail server. |
| Why are root servers rarely contacted? | Local servers cache TLD server addresses (entries expire after TTL). |
| DNS runs on which transport? | UDP. |
| How does a new BitTorrent peer get its first chunk? (sample 1e) | Optimistic unchoking: every 30 s each peer sends to one extra random peer. |
| Tit-for-tat? | Send to the 4 peers sending to you fastest (re-evaluated every 10 s); choke the rest. |
| Rarest first? | Request the chunks fewest neighbors have, so rare chunks spread before they disappear. |
| Tracker / torrent / churn? | Tracker: tracks peers in the torrent. Torrent: peers exchanging one file's chunks. Churn: peers come and go. |
| DASH? | Server: chunks at multiple rates + manifest. Client decides when, what rate, where to request each chunk. |
| Why buffer streaming video? | Network delay varies (jitter); a playout delay + buffer gives continuous playback. |
| Enter deep vs bring home CDN? | Enter deep: many servers inside access networks (Akamai). Bring home: fewer big clusters near them (Limelight). |
| Why not one mega video server? | Single point of failure, congestion point, long paths, same video sent many times over one link. |
| UDP vs TCP sockets? | UDP (SOCK_DGRAM): no connection, address attached to each packet (sendto/recvfrom). TCP (SOCK_STREAM): connect first; accept() creates a new socket per client. |
Chapter 3
| Question | Answer |
|---|---|
| Transport vs network layer? | Transport: process ↔ process. Network: host ↔ host. |
| Multiplexing / demultiplexing? | Mux (sender): gather data from many sockets, add headers. Demux (receiver): use header info to deliver to the right socket. |
| UDP demux vs TCP demux? | UDP: dest IP + dest port only (many senders share one socket). TCP: 4-tuple (src IP, src port, dst IP, dst port), one socket per connection. |
| UDP header fields? | Source port, dest port, length, checksum (16 bits each, 8 bytes). |
| Why the 1s complement of the sum? | Receiver adds everything + checksum; all 1s = no error detected. Simple check. |
| Can the checksum miss errors? | 1-bit: no, always caught. 2-bit: yes, if the same bit flips 0→1 in one word and 1→0 in another. |
| What fixes what in rdt? | Checksum: detect errors. ACK/NAK: feedback. Seq #: detect duplicates. Timer: recover from loss. |
| Why do seq #s 0 and 1 suffice for stop-and-wait? | Only one packet outstanding; receiver only needs "same packet or next one?" |
| Why is stop-and-wait slow? | One packet per RTT: U = (L/R)/(RTT + L/R), tiny on fast long links. |
| Pipelining needs? | A larger seq # range and buffering at sender and/or receiver. |
| GBN vs SR? | GBN: cumulative ACKs, one timer, resend all from the lost one, discards out-of-order. SR: individual ACKs, timer per packet, resend only the lost one, buffers out-of-order. |
| When is SR the same as stop-and-wait? (sample 1d) | When the window size is 1. |
| Why must the SR window be ≤ 2k−1? | Otherwise the receiver's new window overlaps seq #s the sender might retransmit, so an old packet is accepted as new. |
| Why does SR re-ACK packets below its window? | The original ACK may have been lost; otherwise the sender's window would never advance. |
5. Traps checklist (read right before the exam)
• Links = routers + 1. 4 routers → 5 links.
• RTT = 2 × one-way propagation.
• Add the header to every packet's size.
• "10 users" doesn't divide the link rate in packet switching.
• "20 or more" → k from 20. "More than 20" → k from 21.
• HTTP: the base HTML always costs 2 RTT; parallel rounds use the ceiling.
• Caching: hit vs miss rate; only misses use the access link; hits ≈ 0 s.
• P2P: include us in the sum; take the max, not the sum; convert G/M/k first.
• Checksum: wrap the carry, then flip.
• Utilization: round the window up; U ≤ 1.
• GBN max window question: write the concrete example (send all → all ACKs lost → old packet accepted).