The worked answers to the seven worksheets and quizzes from Weeks 1–4, in the order they were set. They cover Chapter 1 (circuit and packet switching, delay and throughput), Chapter 2 (HTTP, reading a new protocol, and DNS) and Chapter 3 up to reliable data transfer (sockets and demultiplexing, UDP against TCP, and rdt2.0 to rdt2.2).
Figures after the authors’ Chapter 1–3 slides, copyright © 1996–2025 J.F. Kurose and K.W. Ross.
The four questions on this worksheet cover circuit switching against packet switching §1.3, transmission delay against propagation delay §1.4, store-and-forward transmission across several links §1.3, and end-to-end throughput §1.4.
Four bursty users — A, B, C, D — share a link that supports 2 circuits. Each is active only 20% of the time. Under circuit switching, A and B each get assigned a circuit for the full 30 seconds.
The grid shows when each user has data (an X), one column per second.
Each row is one of the four users and each column is one of the 30 seconds. A black cell means that user has data to send in that second. The link can carry two users at a time — that is what "2 circuits" means.
Circuit switching §1.3: before any data is sent, two of the four users are each given one of the two slots and keep it for the whole 30 seconds. Here A and B get them, which is the shaded band. A white cell inside the band is a second where the slot is reserved but unused, and no other user may take it. C and D are given nothing, so none of their black cells ever reach the link.
Packet switching §1.3: nothing is reserved and any user sends whenever it has data. In a second where more than two users have data, the excess waits in a queue at the link.
A holds a circuit for all 30 seconds. In how many of those seconds does A actually send, and what percentage of the circuit sits idle?
A sends in: seconds
Idle: %
In second 5, D has data and A is silent. Can D use A's idle circuit? Over these 30 seconds, what happens to C and D's traffic?
If the same link is packet-switched instead, nobody reserves anything and all four users transmit whenever they have data.
In which seconds does demand exceed the link's capacity of 2? What fraction of the 30 seconds is that, and what must the link do with the traffic it cannot send immediately? What happens if too much traffic backs up?
Seconds: Fraction: %
Count the seconds' worth of user data the link actually carries over the 30 seconds under each scheme. (Under packet switching, traffic that has to wait still gets through a second or two later.)
Circuit-switched: Packet-switched:
X in each column and compare that count
with the capacity of 2. For part 4, count all the Xs belonging
to the users who hold a circuit, then count all the Xs belonging
to all four users.16 seconds · 80% idle
A has data in seconds 1, 3, 8, 14, 17 and 27; the circuit is reserved for all 30, so 24 carry nothing. B is the same — that is what "active 20% of the time" costs once you reserve capacity for 100% of it.
2No — and C and D are shut out entirely
A's circuit stays A's whether A uses it or not. Both circuits are assigned, so C and D never transmit: their 12 seconds of data never go out.
3Seconds 8 and 17 · about 7%
Second 8 has three users active, second 17 has four — 2 of 30 seconds. The excess is queued, and dropped once the buffer fills. That wait is queueing delay, one of the two this worksheet sets to zero. §1.4
If you also listed 3, 12, 21 or 27, you counted seconds where demand equalled capacity. Two users on a 2-circuit link both get through.
4Circuit-switched 12 · packet-switched 24
Circuit switching carries only A and B, 6 seconds each; packet switching carries all four, some of it delayed. Twice the data over the same link — bought by accepting a queue 7% of the time.
§1.3 The Network Core · video · knowledge checks · practice problems
A packet crossing one hop meets four delays, and they happen one after another along the time arrow, not at the same time. The router first processes the packet, then the packet waits its turn, then it is pushed onto the link bit by bit, and only then does the last bit travel down the fiber. The four add up. §1.4
This worksheet sets processing and queueing to zero and asks only about the
two shaded boxes. Note what separates them: d_trans is time spent at
the sender, pushing bits out at rate R, while
d_prop is time spent on the fiber, carrying a bit 50 km at
speed s. R appears in the first formula and nowhere in the
second, which is why changing the equipment at the two ends moves one of them and
leaves the other where it was.
For these questions, every message is L = 1,500 bytes = 12,000 bits and:
Scenarios A and B send the message over the same 50 km fiber between Foggy Bottom and the Ashburn campus (VSTC). Only the equipment at the two ends differs. Fill in the table in microseconds.
| Scenario | Link rate | Transmission delay (µs) | Propagation delay (µs) | Which dominates? |
|---|---|---|---|---|
| A | 1 Gbps | |||
| B | 10 Mbps |
The link rate is the only thing that changed between A and B. Why did that change one delay term but leave the other exactly where it was?
A geostationary satellite link runs at 100 Mbps and is 36,000 km from the user. Nearly the whole path is through space. Compute both delays in milliseconds, then find the total one-way delay.
Propagation: ms Transmission: ms Total: ms
Your provider offers to double the satellite link to 200 Mbps. What is the new total one-way delay, and what percentage improvement is that over your answer to Q3?
New total: ms Improvement: %
R appears in one of the two formulas and
not the other. Keep units consistent — 12,000 bits over 10⁹ bits/s lands in
seconds, so convert once at the end rather than part-way through. In part 4,
compute the new total first, then take the improvement as a fraction
of the old total.1propagation, then transmission
| Link rate | d_trans | d_prop | Dominates | |
|---|---|---|---|---|
| A | 1 Gbps | 12 µs | 250 µs | propagation |
| B | 10 Mbps | 1,200 µs | 250 µs | transmission |
12,000 / 10⁹ = 12 µs and 12,000 / 10⁷ = 1,200 µs. Propagation is 250 µs in both rows, because the fiber did not move.
2Only one formula contains R
Propagation depends on distance and medium only; transmission depends on how
fast bits are pushed onto the wire. The endpoint equipment sets R
and never touches distance or s. Processing and queueing delay, the two
this question leaves out, would not move either. §1.4
3120 ms + 0.12 ms = 120.12 ms
36,000 / (3×10⁵) = 120 ms of propagation; 12,000 / 10⁸ = 0.12 ms of transmission. The distance term is a thousand times the other.
4120.06 ms · about 0.05%
Doubling the rate halves transmission delay to 0.06 ms and leaves the 120 ms of propagation untouched. 0.06 / 120.12 ≈ 0.05%.
If part 4 came out near 50%, you halved the total rather
than the one term the upgrade reaches. Doubling R can only halve
the part R appears in, and here that part is a rounding error.
§1.4 Delay, Loss and Throughput · video · knowledge checks · practice problems
Each row is one of the three links and each column is one time slot, where a slot is the time to push one packet onto one link. A shaded cell means that packet is being transmitted on that link during that slot.
A router must receive a packet in full before forwarding it §1.3, so each packet moves down one row per slot and the shaded cells run diagonally. From slot 3 onward all three links are transmitting at the same time. Sent as one large packet instead, only one row would ever be shaded and the other two links would sit idle. (Drawn with four packets; the worksheet uses three.)
A 12,000-bit message travels from source to destination across three links:
Each link runs at R = 10 Mbps. Propagation, processing, and queuing delays are all zero — transmission delay is the only thing that matters here. Under store-and-forward, a router must receive a packet in full before it can start sending it onward.
Sent as one 12,000-bit packet, the message takes 3 × (12,000 bits / 10 Mbps) = 3.6 ms, because each link sits idle until the one before it has finished.
Now split the message into 3 packets of 4,000 bits, and assume for the moment that the receiver can reassemble them with no extra bits. Each hop now takes ms, which we will call a time slot. Mark which packet (P1, P2, P3) occupies each link during each time slot:
| Slot 1 | Slot 2 | Slot 3 | Slot 4 | Slot 5 | Slot 6 | |
|---|---|---|---|---|---|---|
| Link 1 | ||||||
| Link 2 | ||||||
| Link 3 |
Total time until the last bit arrives: ms
The same 12,000 bits crossed every link in both cases, so why is this faster?
Formulate an equation to generalize from your timeline: sending N packets across M links, where each hop takes t, finishes in × t.
In reality, packets need headers. Suppose each packet now has a 320-bit header carrying addressing and ordering information, on top of its payload. Recompute:
| Split into | Payload per packet | Total time (ms) | Header overhead (%) |
|---|---|---|---|
| 3 packets | 4,000 bits | ||
| 100 packets | 120 bits |
10.4 ms per hop · 2.0 ms total
| Slot 1 | Slot 2 | Slot 3 | Slot 4 | Slot 5 | |
|---|---|---|---|---|---|
| Link 1 | P1 | P2 | P3 | ||
| Link 2 | P1 | P2 | P3 | ||
| Link 3 | P1 | P2 | P3 |
4,000 / 10⁷ = 0.4 ms per hop; the last packet clears link 3 at the end of slot 5, so 5 × 0.4 = 2.0 ms against 3.6 ms as one packet.
2Three links transmit at once
From slot 3 onward every link is busy; with one packet only one link is ever active. This overlap is pipelining §1.3. The bits per link are identical — what the split recovers is idle time.
3(N + M − 1) × t
The first packet needs M slots to cross M links; the remaining N − 1 follow one slot behind.
If you wrote N × M, you costed every packet the full journey as though they went one at a time — the un-pipelined answer.
42.16 ms / 7.4% · 4.488 ms / 72.7%
| Split into | Bits per packet | Per hop | Slots | Total | Overhead |
|---|---|---|---|---|---|
| 3 packets | 4,000 + 320 | 0.432 ms | 5 | 2.16 ms | 7.4% |
| 100 packets | 120 + 320 | 0.044 ms | 102 | 4.488 ms | 72.7% |
Overheads are 960/12,960 and 32,000/44,000. Note the second row: 100 packets is slower than sending one — 4.488 ms against 3.6 ms. Splitting buys overlap; every split adds another header.
§1.3 The Network Core · §1.4 Delay, Loss and Throughput · video 1.3 · video 1.4 · knowledge checks · practice problems
A student in a residence hall downloads a large file from a course server.
The three boxes are the segments a download crosses, each labelled
with its rate. The server uplink and the dorm WiFi carry this student's traffic
alone. The campus backbone is divided evenly among everyone downloading at that
moment, which is what ÷ N means.
End-to-end throughput §1.4 is the smallest of the three rates after that division. Because N changes through the day, which segment is smallest can change too.
Suppose only the Campus Backbone network is busy, with 20 users evenly sharing the bandwidth, while the first and third links are idle. Where is the bottleneck and what is the end-to-end throughput?
At 3 a.m. only 2 students are downloading instead of 20. Everything else is unchanged. Recompute the throughput and note which segment limits it now.
Throughput: Mbps Bottleneck link:
150 Mbps · campus backbone
The share is 1,000 / 20 = 50 Mbps, so the throughput is min(200, 50, 100) = 50 Mbps and the backbone is the bottleneck link §1.4.
If you answered 100, you took the smallest of 200, 1,000 and 100. The 1 Gbps headline is the backbone's total, not this student's share — the division by 20 is the step that gets skipped.
2100 Mbps · dorm WiFi
The share is now 1,000 / 2 = 500 Mbps, so min(200, 500, 100) = 100 Mbps. Nothing was rewired; the backbone simply stopped being the smallest term.
If you answered 500, you computed the new share and
stopped. The share is an input to the min(), not the answer.
§1.4 Delay, Loss and Throughput · video · knowledge checks · practice problems
GW CSCI 4431/6431 Computer Networks · Chapter 1 Worksheet
The two questions on this worksheet cover how long a web page takes to load under different versions of HTTP §2.2, and how to read an unfamiliar application-layer protocol §2.1 from a transcript of one session with a mail server §2.3.
Time runs downward, the two vertical lines are the client and the server, and each arrow is one message crossing the network. A round trip is one message out and one message back, so every pair of arrows here is 1 RTT.
Nothing can be requested until a TCP connection exists, and setting one up
costs a message each way — that is the first round trip. The GET and
the first bytes of the reply cost a message each way too — that is the second. So
one object fetched over a fresh connection costs 2 RTT, which is where the
worksheet's "2 RTT per object" comes from.
Non-persistent HTTP 1.0 closes the connection once the object has been sent, so the next object opens a new one and pays both round trips over again. Persistent HTTP 1.1 leaves the connection open, so the handshake is paid once and every later object costs only its own request-and-reply round trip. Pipelining goes further: the client sends all its remaining requests back to back without waiting for each reply, so the whole batch comes back in one round trip. §2.2
Time runs left to right, measured in round trips §2.2: one RTT is how long a small message takes to reach the server and come back. The grey block is the base HTML file, costing two round trips — one to open the TCP connection, one to request the file and receive it. The dashed line is the moment the browser has that file and can read it.
Only past that line does the browser know which objects the page references, because the list of them is written inside the file it was waiting for. So the two round trips to the left are fixed, and every strategy on the worksheet — sequential, parallel, persistent, pipelined — differs only in what happens to the right.
A browser loads a page made of a base HTML file plus 6 embedded objects referenced within its code (images, scripts, stylesheets). The round-trip time between browser and server is RTT = 0.1 s. Every object here is very small, so ignore transmission time entirely — the only cost that matters is round trips.
Under non-persistent HTTP 1.0, fetching one object costs two round trips: one to open the TCP connection, one to send the request and receive the first bytes back. In persistent HTTP 1.1, a single connection can be reused to send multiple requests and responses, with only one RTT for the initial connection setup.
A sequential browser fetches all objects one at a time, opening and closing a connection for each. How many round trips is that, and how long does the page take to fully load?
Round trips: Total time: s
Generalize your count. Fetched this same way, how long would a page with a base file and 30 embedded objects take?
Round trips: Total time: s
Now the browser opens up to 4 parallel connections at a time, but still uses non-persistent HTTP. How long will it take to load the full page and 6 embedded objects? Hint: the answer is not 0.4 s — why not?
Round trips: Total time: s
Finally, the browser opens one persistent connection and pipelines: after receiving the HTML it sends all followup requests back-to-back without waiting for each response. How long will it take to fully load the page in the best case?
Round trips: Total time: s
Nothing physical changed across the three scenarios--same link, same distance, same server--yet we got different performance for each. Parts 1-3 ran the same protocol and differed only in how the client chose to use it, while part 4 needed a new capability the protocol itself had to provide. System design always has trade-offs; what is the cost to make part 4 faster and who pays it?
114 RTT · 1.4 s
Seven objects in total — the base file plus six — at 2 RTT each.
262 RTT · 6.2 s
2(N + 1) × RTT: N objects plus the base file, two round trips each.
36 RTT · 0.6 s
The base fetch is serial at 2 RTT §2.2, because the references to the six objects are inside the file the browser is still waiting for. Then 6 objects over 4 connections is 2 batches × 2 RTT — four objects in the first batch, two in the second.
If you answered 0.4 s, you either left the base file out or pooled all seven objects into the parallel connections — both give 4 RTT, and both treat the base file as just another object.
43 RTT · 0.3 s
One RTT to open, one for the HTML, one for the whole batch §2.2. The six responses still arrive one after another; they cost only one round trip between them because the six requests went out together.
The three strategies laid side by side, one row per round trip:
| RTT | done at | 1 — serial, non-persistent | 3 — 4 parallel, non-persistent | 4 — persistent, pipelined |
|---|---|---|---|---|
| 1 | 0.1 s | handshake for the base file | handshake for the base file | handshake — once, for the whole page |
| 2 | 0.2 s | GET base → HTML back | GET base → HTML back | GET base → HTML back, connection stays open |
| the browser parses the HTML and only now discovers the 6 references | ||||
| 3 | 0.3 s | handshake, object 1 | 4 handshakes at once | 6 GETs back to back → 6 responses return · 3 RTT |
| 4 | 0.4 s | GET → object 1 | 4 GETs → objects 1–4 | |
| 5–6 | 0.6 s | object 2, two RTT | 2 handshakes, then 2 GETs → objects 5–6 · 6 RTT | |
| 7–14 | 1.4 s | objects 3–6, two RTT each · 14 RTT | ||
5The server pays, and everyone pays to deploy
Parts 1–3 are all HTTP 1.0, changed only by a client-side decision no server had to agree to — which is why browsers did it. Part 4 needs persistence, and the server pays at run time, holding a socket open for a client that may never speak again. Both ends must implement it first, which takes years.
§2.2 The Web and HTTP · video · knowledge checks · practice problems
Each row names one of the four things the textbook §2.1 says an application-layer protocol must define, next to an example of it taken from the mail transcript on the worksheet.
Q2 walks that transcript once for each row: part 1 is semantics, parts 3 and 4 are syntax, and part 2 is the fourth row — the one that turns a list of messages into a state machine.
Each box is a state the server is in, and each solid arrow is the client command that moves it on. The server can only reach the last box by passing through all of them in order.
The dashed arrow is RCPT TO §2.3 arriving before
MAIL FROM: there is no transaction yet for a recipient to attach to,
so the server rejects it. That is what "stateful" means here — the same command
means different things depending on where in the chain it arrives. In HTTP,
GET /b.jpg means the same thing first, third, or on a brand-new
connection.
§2.1 Principles of Network Applications · §2.3 Email · video 2.1 · video 2.3 · knowledge checks · practice problems
We have not covered this protocol, but everything you need is below. The transcript shows a complete session with a mail server. C: = client → server message, S: = server → client message. Try to interpret the exchange below.
S: 220 hamburger.edu C: HELO crepes.fr S: 250 Hello crepes.fr, pleased to meet you C: MAIL FROM: <alice@crepes.fr> S: 250 alice@crepes.fr... Sender ok C: RCPT TO: <bob@hamburger.edu> S: 250 bob@hamburger.edu ... Recipient ok C: DATA S: 354 Enter mail, end with "." on a line by itself C: Do you like ketchup? C: How about pickles? C: . S: 250 Message accepted for delivery C: QUIT S: 221 hamburger.edu closing connection
The server answers 250 three times, each time followed by a different sentence. Which part of a reply is a program meant to act on, and which part is there for a human debugging? What could go wrong in a client that decided what to do by matching the words?
HTTP was described as a stateless protocol, because subsequent requests (even when pipelining) do not depend on prior ones. This protocol is stateful: what information must the server remember as the session goes on, and why does it need it? Does the order of the client's messages matter — what should happen if RCPT TO arrives before any MAIL FROM?
Alice writes a long email in which one of the lines consists of exactly one period, with nothing else on that line. Trace what a server receives and what happens to her message. If you email your partner a line that is just a "." — will it work? What might be happening differently?
Propose a protocol change that avoids the problem of Alice's message being mistaken for a control signal. Hint: look at how HTTP produces a response to a client. How does this change impact the client?
1The three-digit code is the contract
All three mean the same thing to a program: the last command was accepted §2.3. Only the code is specified, so a client that branched on the wording breaks against another server, an upgrade, or another language.
2The sender and a recipient — and order matters
The body after DATA carries no addressing, so a server that had
forgotten would hold a message with nobody to deliver it to.
RCPT TO before MAIL FROM is rejected
(503 Bad sequence of commands): there is no transaction yet to
attach a recipient to. Meaning depends on history — that is "stateful".
3Predicted: truncated. Actually: it works
From the transcript you would predict the server reads that line as the end of the message and runs the rest as commands. In practice the mail arrives whole, because of dot-stuffing: the sender adds a second period to any body line starting with one, and the receiver strips it off.
It works only because both ends follow the convention — and either program looks correct when tested against itself.
4Declare the length up front
An HTTP response sends Content-Length: 2651 then exactly that many
bytes. Do the same — DATA 2651 — and the server counts instead of
watching for a magic line. The client pays: it must know the size before the
first byte, and a wrong count desynchronizes the connection.
§2.3 Email · video · knowledge checks · practice problems
GW CSCI 4431/6431 Computer Networks · Chapter 2 Worksheet
Both quiz questions repeat a worksheet question with different numbers: end-to-end throughput from the Chapter 1 worksheet §1.4, and HTTP page-load time from the Chapter 2 worksheet §2.2.
A student in the library downloads a large file from a course server:
The three boxes are the segments this download crosses, each
labelled with its rate. The server uplink and the library WiFi carry this
student's traffic alone; the campus backbone is divided evenly among everyone
downloading at that moment, which is what ÷ N means.
End-to-end throughput §1.4 is the smallest of the three rates after that division. The share is an input to the minimum, never the answer on its own — and since N differs between 2 p.m. and 3 a.m., so can the smallest term.
The server uplink and the library WiFi are this student's alone. The campus backbone is shared evenly among everyone downloading at that moment.
At 2 p.m., 10 students are downloading. What is this student's end-to-end throughput, in Mbps?
At 3 a.m., only 3 students are downloading, everything else unchanged. What is the throughput now, in Mbps?
1.190
The share is 900 / 10 = 90 Mbps, so the throughput is min(600, 90, 150) = 90 Mbps, bottlenecked at the campus backbone.
1.2150
The share is now 900 / 3 = 300 Mbps, so min(600, 300, 150) = 150 Mbps. You are never asked to name the bottleneck, but 1.2 cannot be answered without finding it — the backbone stopped binding and the WiFi took over.
If you answered 300 on 1.2, you computed the new share and stopped. The share is an input to the minimum, not the result.
If you answered 150 on 1.1, you took the smallest of 600, 900 and 150 without dividing the backbone. The headline rate of a shared link is never one user's share of it.
§1.4 Delay, Loss and Throughput · video · knowledge checks · practice problems · same as Chapter 1 worksheet Q4
Time runs left to right in round trips §2.2. The grey block is the base HTML file, which costs two round trips and cannot overlap with anything, because it is what names the objects. The black blocks are those objects, two at a time because there are two connections.
Three objects over two connections take two batches, not one and a half. The second batch carries one object and leaves a connection idle, and still costs a full two round trips — so the batch count is always rounded up.
A browser loads a page made of a base HTML file plus 5 embedded objects referenced inside it. RTT = 10 ms. Every object is small, so ignore transmission time — only round trips count.
Under non-persistent HTTP, fetching one object costs 2 RTT: one round trip to open the TCP connection, one to send the request and get the first bytes back.
The browser fetches everything sequentially, opening and closing a connection for each object. How long does the page take to load, in ms?
The browser now opens up to 2 parallel connections, still non-persistent. How long does the page take to load, in ms?
2.1120
Six objects — the base file plus five — at 2 RTT each is 12 RTT.
2.280
The base file is serial: 2 RTT. Then 5 objects over 2 connections is ⌈5/2⌉ = 3 batches × 2 RTT = 6 RTT. Total 8 RTT = 80 ms.
The two strategies laid side by side, one row per round trip:
| RTT | done at | 2.1 — one at a time | 2.2 — 2 parallel connections |
|---|---|---|---|
| 1 | 10 ms | handshake for the base file | handshake for the base file |
| 2 | 20 ms | GET base → HTML back | GET base → HTML back |
| the browser parses the HTML and only now discovers the 5 references | |||
| 3 | 30 ms | handshake, object 1 | 2 handshakes at once |
| 4 | 40 ms | GET → object 1 | 2 GETs → objects 1–2 |
| 5 | 50 ms | handshake, object 2 | 2 handshakes |
| 6 | 60 ms | GET → object 2 | 2 GETs → objects 3–4 |
| 7 | 70 ms | handshake, object 3 | 1 handshake — the other connection has nothing left to fetch |
| 8 | 80 ms | GET → object 3 | 1 GET → object 5 · 8 RTT |
| 9–12 | 120 ms | objects 4 and 5, two RTT each · 12 RTT | |
Rows 7 and 8 are the ones the question is built on: the third batch carries a single object and leaves the second connection idle, and it still costs a full two round trips.
If you answered 60, every wrong route lands there: leaving the base file out, pooling all 6 objects into the parallel connections, or simply halving 2.1. All three assume the browser could have started on the 5 objects at time zero. It could not — the references to them are inside the HTML file it is still waiting for.
If you answered 70, you had the base file right but divided 5 by 2 without rounding up. The third batch carries one object and still costs a full 2 RTT.
§2.2 The Web and HTTP · video · knowledge checks · practice problems · same as Chapter 2 worksheet Q1
GW CSCI 4431/6431 Computer Networks · Week 2 Quiz
The six DNS questions cover how a name is resolved by iterated and
recursive queries, and what a lookup costs in round trips §2.4;
how caching and the TTL trade query load against how quickly changes spread; why DNS
runs over UDP and what that leaves the client to do §3.3;
forged replies and cache poisoning; and reading real dig output for
aliases and for answers that depend on who asks.
Each box is a DNS server; in reality each is many machines sharing one
name. The rows are the levels of the hierarchy §2.4: root,
one top-level-domain (TLD) server per ending such as .edu, and the
authoritative server an organization runs for its own names. A line means the upper
server knows the lower one's address. The bold path is the one a lookup for
gaia.cs.umass.edu follows.
The dashed box, the local DNS server, is run by your ISP or campus and is not part of the hierarchy. It is the only server your host asks, and it works down the bold path one level at a time, because each level only knows who to ask next.
Following the example presented by Kurose (slides 76-78), a host at engineering.nyu.edu wants the IP address for gaia.cs.umass.edu. Its local DNS server is dns.nyu.edu. No server anywhere has anything cached. Resolution involves the local server, a root server, a TLD server, and the authoritative server for cs.umass.edu.
Count every DNS message that crosses the network, including the host's question to its local server and the final answer back to the host.
How many DNS messages are sent in total if the query is iterated?
How many DNS messages are sent in total if the query is recursive?
In the iterated case, how many of those messages are sent by the local DNS server?
In the recursive case, how many of those messages are sent by the local DNS server?
Real Root and TLD operators answer iterated queries and refuse recursive ones. Why is this? What must the root server remember for recursive queries, and why isn't this needed for the iterated case?
1a8 1b8 1c4 1d2
The five vertical lines are the machines, time runs downward, and each arrow is one DNS message. Bold arrows are the ones the local server sends. A grey bar on a line means that machine has asked something and is waiting for the reply, so it has to remember the query until the reply comes back.
In the iterated case every server answers straight back to the local server, with either the answer or a referral ("I don't know, but ask this server") §2.4. In the recursive case each server passes the question down to the next and waits for the answer to come back up the same chain. Either way the question goes down three levels and the answer comes back up, so both total 8 messages. What changes is who sends them: the local server sends 4 when iterated and only 2 when recursive.
If you answered fewer than 8 for 1b, you expected recursion to save messages. It is a natural guess, because the local server does less. But the work has not gone away: the root and TLD servers now send the messages the local server used to.
1eThe root would have to hold state for every query
In the recursive case the root receives message 2 and cannot reply until message 7 arrives. For that whole time it must remember the question, who asked it, and a timer in case the answer never comes; that is the grey bar on its line. In the iterated case it replies at once with a referral and forgets the query, so nothing is outstanding. The root and TLD servers answer for the whole Internet. Holding a pending query for every lookup, and doing all the chasing that 1c and 1d show the local server handing off, would be an enormous load. Answering iteratively keeps their job to one cheap step: reply and forget.
§2.4 The Domain Name System · video · knowledge checks · practice problems
This figure uses iterated queries, as Q2 does: the local server asks each server itself, and each reply tells it who to ask next. Each box is one round trip between the two machines named in it, and its width is that round trip in ms; the numbers are made up, not the quiz's. Boxes run left to right because the local server cannot send the next question until the previous answer is back.
With recursive queries the picture would be different: the local server would make a single round trip to the root and wait while the root, TLD and authoritative servers passed the question down and the answer back up §2.4. Q1 compares the two.
The rows are three states of the local server's cache §2.4. If it has already cached the TLD server's address, the round trip to the root is gone, because learning that address was the only reason to ask the root. If it has the whole name cached, it answers the host at once. How long an entry may be kept is its TTL, which is what Q3 is about.
Use these round-trip times (note these are round trip -- NOT one way delays!). Assume every server responds instantly and ignore transmission time; only round trips matter.
| Link | RTT |
|---|---|
| host ↔ local DNS server | 4 ms |
| local DNS server ↔ root server | 35 ms |
| local DNS server ↔ TLD server | 40 ms |
| local DNS server ↔ authoritative server | 20 ms |
| host ↔ web server | 30 ms |
The queries are iterated, so every message in the chain passes through the local DNS server and each RTT above is paid in full, one after another.
Nothing is cached anywhere. How many ms pass between the host asking its local DNS server and the host receiving the IP address?
The local DNS server already has the TLD server's address cached, but nothing else. How many ms now?
The local DNS server has the full name-to-address mapping cached. How many ms now?
Assuming a cold cache case like in Q2a, the host performs a DNS lookup and then immediately opens a TCP connection to the web server and sends an HTTP request for a tiny file. How long would it take in ms from the start of the name lookup to the arrival of the page?
If the local DNS server can only cache one entry (TLD IP provided by root server, authoritative IP provided by TLD server, or destination IP provided by authoritative server), which do you think would be most valuable, and why?
2a99 2b64 2c4 2d159
| round trip, in order | 2a | 2b | 2c | 2d |
|---|---|---|---|---|
| host ↔ local | 4 | 4 | 4 | 4 |
| local ↔ root | 35 | — | — | 35 |
| local ↔ TLD | 40 | 40 | — | 40 |
| local ↔ authoritative | 20 | 20 | — | 20 |
| the host now has the web server's address | ||||
| host ↔ web: open the TCP connection | 30 | |||
| host ↔ web: request and receive the file | 30 | |||
| total, ms | 99 | 64 | 4 | 159 |
Each round trip must finish before the local server knows who to ask next, so they add up. In 2b the only reason to ask the root was to learn the TLD server's address, so with that cached the root round trip disappears. In 2c the local server answers from its cache. In 2d the lookup only produces an address: the host then pays one round trip to open a TCP connection and one to request and receive the file, the same 2 RTT per object as HTTP §2.2. Server processing and transmission time were set to zero.
If you answered 129 on 2d, you left out the TCP handshake: nothing can be requested until the connection exists. If you answered 189, you also charged a handshake to the DNS lookup, but DNS runs over UDP, which has no connection to open. Q4a asks what it would cost if it did.
2eThe TLD server's address, because of reuse
| cached entry | lookup | saves | also helps | typically kept |
|---|---|---|---|---|
| TLD server's address | 64 | 35 | every .edu name |
about 2 days |
| authoritative server's address | 24 | 75 | every name under umass.edu |
about 2 days |
| final name → address | 4 | 95 | that one name | minutes (Q6) |
Per lookup, the TLD entry saves the least. What makes an entry valuable is how much it
saves each time multiplied by how often it is used while it is kept. One
.edu referral is on the path of almost every lookup the local server makes
and is kept for days. The final mapping saves the most, but only helps someone who asks
for that exact name again within a few minutes. This is why local servers usually have
the TLD servers cached, and why most queries never reach a root server
§2.4. Another entry can be argued for, if the argument weighs
both the saving and the reuse. Real resolvers cache all three at once; the one-entry
limit only isolates the reuse question.
If you picked the TLD entry because it saves the most time, the choice is right but the reason is not: with these numbers it saves the least. And the authoritative entry skips the root as well as the TLD, which is why it saves 75 ms, not 40.
§2.4 The Domain Name System · video · knowledge checks · practice problems · §2.2 The Web and HTTP · video
You run the authoritative DNS server for example.com. The A record for www.example.com has a TTL of 300 seconds (5 minutes). One large ISP's local DNS server receives 50 queries per second for that name, continuously.
Roughly how many queries does that ISP's local DNS server forward to your authoritative server per hour?
You raise the TTL to 86400 seconds (24 hours) and, a week later, move the site to a new IP address, causing old cached entries to give an invalid result. In the worst case, how many seconds might a client keep contacting the old, dead address after you publish the change?
TTL is a single knob that provides a trade-off in two costs that pull in opposite directions — name both. Then: you knew about the move in Q3b a week in advance, so what should you have done, when, and which machines pay for it? Finally, name one other situation in which you would deliberately accept that same cost.
3a12
The line is one hour at the ISP's local DNS server. Each bar is one cached copy of the record, living for its 300 s TTL. When a copy expires, the next query that arrives (a fiftieth of a second later) cannot be answered from the cache, so the server asks you once and caches the new copy. That is 3600 / 300 = 12 queries an hour. The arrival rate hardly matters, as long as at least one query arrives per TTL.
If you answered 180000, that is 50 × 3600: the number of queries arriving at the ISP's server, not the number it passes on to you.
3b86400
A resolver that fetched the old record one second before you changed it keeps serving it for the full TTL: 86400 s, a whole day. Nothing can shorten that. DNS has no way to recall a record, because your server has no idea which resolvers hold a copy §2.4. You can limit the damage in advance, but you cannot undo it afterward.
3cTwo costs, a plan, and one more case
The two costs. A long TTL means fewer queries reach your server and users get faster lookups, but changes spread slowly and you cannot hurry them. A short TTL means changes take effect quickly, but your servers answer far more queries and more users wait for a full lookup.
Before the move. Lower the TTL, to 60 s say, at least one old TTL (a day) before the move, so every copy carrying the 24-hour TTL has expired by then. Move, check it works, then raise the TTL again. Your own authoritative servers pay: run 3a in reverse, and a 60 s TTL means 60 queries an hour from this one ISP instead of 12.
Another case. Any time being able to change the answer quickly is worth the extra load: failing over to a backup when a server dies, spreading load over a pool of servers that keeps changing, or a CDN sending each user to a nearby server. Q6b shows the last of these.
§2.4 The Domain Name System · video · knowledge checks · practice problems
Using Q2's RTTs and the cold-cache scenario from Q2a: if DNS ran over TCP, each of the three servers contacted would need a connection setup costing one extra RTT before the query could be sent. How many ms would the cold lookup take?
Every DNS message carries a 16-bit identification field, and a reply repeats the identification number of the query it answers. Explain why DNS needs this field and HTTP does not. Hint: Your answer should refer to the transport protocol each one runs over.
Q4b is an instance of a general pattern: choose a weaker transport and you take on work the stronger one was doing for you. Name one other job TCP performs that a DNS client must therefore handle itself, and say what a DNS client actually does about it.
4a194
| round trip | over UDP | over TCP |
|---|---|---|
| host ↔ local | 4 | 4 |
| local ↔ root | 35 | 35 + 35 |
| local ↔ TLD | 40 | 40 + 40 |
| local ↔ authoritative | 20 | 20 + 20 |
| total, ms | 99 | 194 |
Each of the three servers now needs a handshake round trip before the query round trip, so each of those costs is paid twice. The question adds nothing for the host's own step to the local server. The result is almost double, for a lookup that sits in front of nearly everything a user does.
4bUDP has no connection to tie a reply to its query
DNS runs over UDP, which has no connections §3.3. A resolver can have many queries outstanding on one socket, and replies may arrive late, out of order, twice, or forged. The identification number is how the client matches a reply to the question it answers. HTTP runs over TCP, where the connection does that job: whatever arrives on a connection belongs to the exchange on that connection, in order. DNS rebuilds, at the application layer, a service TCP would have given it for free.
4cReliability, most directly
UDP never resends a lost message, so a DNS client sets its own timer, sends the query again if no reply comes, and after repeated failures tries a different server. Other correct answers: congestion control (the client has to limit its own sending), and replies too large for one datagram (the server truncates the reply and the client repeats the query over TCP). Retries can produce duplicate replies, and the identification field from 4b is what lets the client spot them.
§2.4 The Domain Name System · video · knowledge checks · §3.3 Connectionless Transport: UDP · video · knowledge checks
In class we saw an SMTP session in which the client announced who it was and which address it was sending from, and the server believed both without checking.
The original DNS protocol also lacks any kind of authentication. Suppose a malicious observer is sitting between your local DNS server and a server you are trying to query. What could this attacker do if it can see your request and can fabricate a reply?
Why does that attack do more damage per successful attempt than forging a single email does?
Vertical lines are machines, time runs downward, and arrows are DNS messages. The names and addresses are invented for the example; ID 4711 is the query's identification number from Q4b. The bold arrows carry the forged answer: first from the attacker to the local server, then from the local server to every host that asks for the name.
5aForge the reply, and have it cached
The attacker sees the query, so it knows the identification number, port and question. It sends a reply that matches them, giving the address of a server it controls, and gets it to your local server before the real one. The local server accepts the first matching reply and throws away the real one when it arrives. Then it caches the forged answer and gives it to every host that asks for that name, for as long as the TTL the attacker wrote into the reply. Users who type the right name into the right browser reach the attacker's server, and nothing on their side looks wrong. This is DNS cache poisoning §2.4.
5bOne forgery reaches everyone, for the whole TTL
A forged email deceives one recipient, once, and only if they believe it. A poisoned cache redirects every user of that resolver for the whole TTL, and nobody has to do anything wrong: it happens before anything the user can check, so being careful about links does not help. The damage is multiplied by how many users share the resolver and by how long the attacker chose to have the answer kept. The fix added later, DNSSEC, lets a resolver check that an answer was signed by the owner of the name §2.4.
§2.4 The Domain Name System · video · knowledge checks
Here you will use https://digwebinterface.com. It runs the dig command-line tool for you and shows you the raw output, so you do not have to install anything.
Q6 has you run two queries. Each one tells you exactly what to type and which options to set — use those settings, because the two runs need different Nameservers settings.
Enter www.gwu.edu in Hostnames, set Type to A, and under Nameservers choose the Resolver: radio button with Comodo (US) selected in the dropdown. Submit.
You will see something close to this:
www.gwu.edu. 60 IN CNAME www.gwu.edu.cdn.cloudflare.net. www.gwu.edu.cdn.cloudflare.net. 300 IN A 104.18.9.37 www.gwu.edu.cdn.cloudflare.net. 300 IN A 104.18.8.37
Each line is one resource record: the name, then the TTL in seconds, then the class, then the record type, then the value. Your TTL numbers will not match the ones above.
Notice that no record in this output maps www.gwu.edu directly to an IP address. Explain what the CNAME line does instead, what the A lines are addresses of, and what this tells you about where GW's website is actually served from. Then explain why the CNAME and the A records carry different TTLs — who publishes each one, and why would they choose differently?
Now change Hostnames to www.amazon.com, leave Type on A, and under Nameservers select the All radio button. This asks the same question of every resolver in the list and shows you each reply, labeled with the resolver that sent it — Google, Cloudflare, Quad9, AT&T, and several outside the US, including HiNet in Taiwan and Yandex in Russia. Submit.
Read down the replies and compare the final A record from each one. (Do not worry if one or two resolvers time out — that is normal.)
Different resolvers report different IP addresses for the same name. Explain why: what is the authoritative server doing differently depending on who asks, which of the DNS services listed in §2.4 this is, and what Amazon gains from it. Then say what this means for the idea of "the IP address of www.amazon.com," and connect the very short TTLs on those A records back to the trade-off you described in Q3c.
www.gwu.edu
ever the name on an A line? For 6b: do the resolvers make up their answers,
or do they all ask the same server?www.gwu.edu, and which runs the one holding
…cdn.cloudflare.net? For 6b, find the resolvers whose address nobody else got
and note where they are; then compare how many seconds Amazon lets anyone keep its answer
with the trade-off you described in Q3c.
Boxes are names or addresses from the output above, and each arrow is one record, labelled with its type and TTL in seconds. The dashed outlines are zones: the part of the name space one organization publishes records for.
6aAn alias to a CDN name, published by two organizations
The CNAME line says www.gwu.edu is an alias, and its canonical
(real) name is www.gwu.edu.cdn.cloudflare.net
§2.4. The resolver followed the alias and looked that name up,
so both A lines are addresses of the canonical name, not of
www.gwu.edu. Because that name ends in cdn.cloudflare.net,
GW's website is served by Cloudflare's content distribution network, and the two
addresses are Cloudflare's machines §2.5. The TTLs differ
because two organizations publish these records. GW publishes the CNAME in
its own zone and chose 60 s, so it can switch CDN quickly; Cloudflare publishes the
A records in its zone and chose 300 s. Each made Q3's trade-off
separately.
6bThe answer depends on who asks
final A record |
resolvers that returned it |
|---|---|
3.167.164.20 |
Default, Comodo (US), Quad9, Verisign (US) |
3.171.29.237 |
Cloudflare, Google, OpenDNS |
3.166.104.154 |
AdGuard (CY) |
3.161.248.70 |
AT&T (US) |
54.192.251.125 |
HiNet (TW) |
13.249.10.125 |
Yandex (RU) |
| Securolytics (CA) timed out · captured 3 September; your addresses will differ | |
Eleven resolvers answered with six different addresses. None of them is wrong or out of
date: each is reporting what Amazon's authoritative server told it, and that server
chooses its answer based on who is asking, roughly where the querying
resolver is. This is load distribution, one of the four DNS services in
§2.4, used here to send each user to a nearby CDN server
§2.5. Amazon gets lower latency for its users, traffic spread
over many machines, and the ability to move users away from a failed or overloaded site
without anything changing on their side. So there is no single IP address of
www.amazon.com: the answer depends on who asks, and when. The TTLs of under
a minute are Q3's knob turned hard toward agility: a live routing decision is useless if
kept for a day, so Amazon accepts far more queries to be able to move a user quickly.
If you wrote that the resolvers disagree, or that some are out of date, look at where the difference starts. The variation comes from the authoritative server, and it is deliberate.
§2.4 The Domain Name System · video · knowledge checks · §2.5 Video Streaming and Content Distribution Networks · video · knowledge checks
GW CSCI 4431/6431 Computer Networks · Quiz 3 (DNS) · Study Guide
The four questions cover what the transport layer adds on top of IP, how UDP and TCP decide which socket an arriving segment belongs to, and which port numbers a reply carries.
IP already delivers datagrams from one host to another. What does the transport layer add on top of that?
A
The network layer carries a datagram from one host to another. The transport layer then hands it to the correct process running on that host.
B describes routing, which is the network layer's job.
C describes DHCP, which is also network-layer work, but it runs once when your machine joins a network rather than on every packet.
D describes the link and physical layers.
K&R §3.1 · DHCP is §4.3
Read: Kurose & Ross 9e, §3.1–3.2. Class slides 20–24.
You are running Wireshark on a server at 10.0.0.7. The server runs a single UDP application, and the capture below is filtered to show only the traffic arriving for it. As a reminder, the Info column shows the source -> destination ports and packet length
| No. | Source | Destination | Protocol | Length | Info |
|---|---|---|---|---|---|
| 1 | 192.168.10.14 | 10.0.0.7 | UDP | 73 | 54321 → 5000 Len=31 |
| 2 | 192.168.10.22 | 10.0.0.7 | UDP | 73 | 54321 → 5000 Len=31 |
| 3 | 172.16.4.9 | 10.0.0.7 | UDP | 80 | 61002 → 5000 Len=38 |
| 4 | 192.168.10.14 | 10.0.0.7 | UDP | 66 | 54321 → 5000 Len=24 |
| 5 | 172.16.4.9 | 10.0.0.7 | UDP | 80 | 61002 → 5000 Len=38 |
| 6 | 192.168.10.22 | 10.0.0.7 | UDP | 73 | 54321 → 5000 Len=31 |
How many sockets does that UDP application need in order to receive all of this traffic?
1
UDP demultiplexes on the destination port alone. Every datagram in this capture is going to port 5000, so all six of them arrive at the same socket, no matter which of the three clients sent them.
If you answered 3, you counted the three clients. Wireshark's Statistics → Conversations view also reports 3 here, so it is an easy answer to land on. But a conversation is not a socket — counting the far end is TCP's rule, and that is Q3.
If you answered 6, you counted the packets in the capture rather than the sockets receiving them.
K&R §3.2, connectionless demultiplexing · slide 21
Same server, same Wireshark session, a different application — this time a web server on port 80. Again the capture is filtered to show only the traffic arriving for it.
| No. | Source | Destination | Protocol | Length | Info |
|---|---|---|---|---|---|
| 1 | 192.168.10.14 | 10.0.0.7 | TCP | 74 | 9157 → 80 [SYN] Seq=0 Win=64240 Len=0 |
| 2 | 172.16.4.9 | 10.0.0.7 | TCP | 74 | 5775 → 80 [SYN] Seq=0 Win=64240 Len=0 |
| 3 | 172.16.4.9 | 10.0.0.7 | TCP | 74 | 9157 → 80 [SYN] Seq=0 Win=64240 Len=0 |
| 4 | 192.168.10.14 | 10.0.0.7 | TCP | 466 | 9157 → 80 [PSH, ACK] Seq=1 Ack=1 Win=64240 Len=412 |
| 5 | 172.16.4.9 | 10.0.0.7 | TCP | 471 | 5775 → 80 [PSH, ACK] Seq=1 Ack=1 Win=64240 Len=417 |
| 6 | 172.16.4.9 | 10.0.0.7 | TCP | 463 | 9157 → 80 [PSH, ACK] Seq=1 Ack=1 Win=64240 Len=409 |
How many sockets does the web server have for these connections?
172.16.4.9 in the Source column.
It appears twice, with two different source ports. Is that one connection
or two?3
A TCP socket is identified by the full 4-tuple. All six packets
are going to 10.0.0.7:80, but they come from three distinct
sources — 192.168.10.14:9157, 172.16.4.9:5775
and 172.16.4.9:9157 — so the server ends up with three
separate sockets. Notice that the last two come from the same host and
still count separately, because their source ports differ.
If you answered 1, you carried Q2's UDP rule forward. The picture is nearly the same, but the protocol changed, and so did the rule.
Worth knowing: the server also keeps a listening socket on port 80, shown in figure 3 above. It carries no data of its own — it exists to accept new connections — so the three sockets above are the ones serving these connections.
K&R §3.2, connection-oriented demultiplexing · slide 24
Host A sends a UDP datagram to host B. The datagram's header carries source port 6428 and destination port 9157. The application on B reads it and sends a reply straight back to the process on A that sent it.
What destination port number does B's reply carry?
6428
| Datagram | Source port | Dest port |
|---|---|---|
| A → B request | 6428 | 9157 |
| B → A reply | 9157 | 6428 |
B addresses its reply to the socket the request came from, so the two port numbers trade places on the way back.
If you answered 9157, you copied the original destination port instead of swapping the two. Port 9157 belongs to B, so a reply sent there would arrive back at B rather than at A.
This one bites in Project 1: a client that sends its reply to the wrong port is talking to itself, and it will then sit waiting for an answer that never comes.
K&R §3.2 · slide 22
GW CSCI 4431/6431 Computer Networks · Week 4 Quiz
This worksheet compares one DNS lookup carried over UDP §3.3 with the same lookup carried over TCP — in round trips, in bytes sent, and in the number of sockets §3.2 the server has to keep open.
Each line inside a box is one arriving message, written as source address : source port → destination port, and the circles are the sockets those messages are delivered to. In both boxes the same laptop, 10.2.0.9, sends three messages from three different source ports: 5775, 6428 and 9157.
On the left the messages are UDP datagrams to port 53. UDP consults only the destination port §3.2, which is 53 for all three, so all three reach one socket. On the right they are TCP segments to port 80. TCP consults all four values — source address, source port, destination address and destination port — and here only the source port differs, which is enough: each segment reaches a socket of its own, with its own buffers and timers. All three sockets are on port 80; each is labelled with its two ends, the server’s port 80 and the laptop’s port. A different source address would separate them just as well.
The TCP sockets do not exist in advance. The server creates each one when that connection’s handshake completes — the SYN, SYN-ACK and ACK at the top of the worksheet’s TCP timeline — and removes it when the connection closes. The UDP socket is created once, before any message arrives. Part 4 turns that difference into a number.
Time runs left to right. Each black bar is one connection, drawn from when it opens to when it closes; they all last the same length because the worksheet gives a fixed holding time. The dashed line picks out one instant, and the connections open at that instant are the ones it crosses — three of the five here.
So the number open at any moment is the rate at which they arrive multiplied by how long each one lasts. This is the same counting that tells you how many people are in a shop.
Each bar is one segment on the wire §3.3: the grey part is the transport header the protocol adds, the outlined part is the application's own data. The two bars carry the same payload, so the only difference is the header — 8 bytes for UDP against 20 for TCP.
That extra twelve bytes is nothing on a file transfer and everything on a name lookup, because a resolver's whole workload is small messages — and TCP also sends three header-only segments before any data moves at all.
A campus DNS resolver answers name lookups for the whole university. A laptop sends a 32-byte query and the resolver returns a 64-byte response. The round-trip time between them is RTT = 20 ms. Both messages are small, so ignore transmission time — only round trips matter.
Here is the same lookup over TCP. Each arrow is one segment, labelled with what it carries.
Draw the same lookup over UDP on the timeline below. Label every arrow with what it carries and how many bytes of application data are in it.
Using both diagrams, fill in the table. "Bytes on the wire" counts every arrow shown, in both directions, including transport headers. Each UDP header is 8 bytes; a TCP header is 20 bytes.
| Time | Bytes on the wire | |
|---|---|---|
| UDP | ms | bytes |
| TCP | ms | bytes |
The resolver answers 50,000 lookups per second. If every one of them ran over TCP instead of UDP, how much extra traffic would its link carry, in Mbps?
Extra bytes per lookup: Extra load: Mbps
Over TCP each connection stays open about 40 ms. At 50,000 lookups per second, how many TCP connections is the resolver holding open at any one instant, and how many sockets does that take? Serving the same load over UDP takes how many sockets — and what fact about UDP makes the two answers different?
TCP sockets: UDP sockets:
On your UDP diagram, draw a query that gets dropped before arrival at the server. The laptop has to choose how long to wait before deciding the query was lost. What goes wrong if it waits too little? What goes wrong if it waits too long?
1Two arrows
Query (32 B) out, response (64 B) back — no setup, no teardown. Five arrows against two settles the sheet before any arithmetic.
2UDP 20 ms / 112 B · TCP 40 ms / 196 B
UDP is one round trip: (32+8) + (64+8) = 112. TCP is two, at 3 × 20 for the header-only segments plus (32+20) + (64+20) = 196. 2× the latency and 1.75× the bytes for one question and one reply.
If you read 20 ms for TCP, you counted only the bottom two arrows — the handshake is a round trip too, spent before the question is asked.
384 extra bytes · 33.6 Mbps
196 − 112 = 84, and 84 × 50,000 = 4.2 MB/s. 84 bytes is nothing; 84 bytes fifty thousand times a second is a third of a 100 Mbps link.
42,000 TCP sockets · 1 UDP socket
50,000/s × 0.040 s = 2,000 open at once, and a TCP socket is keyed on the 4-tuple, so every client needs its own. UDP keys on the destination port alone, so one socket serves all of them.
2,000 against 1 is why DNS runs over UDP. State is what falls over first.
5Nobody announces the loss
Best-effort delivery §3.3 means there is no error, there is silence: the laptop finds out only because its timer expired. Too little: it abandons a query that was merely slow, and the retries add traffic when the network can least carry it. Too long: every lost query costs the user that whole wait.
§3.2 Multiplexing and Demultiplexing · §3.3 Connectionless Transport: UDP · video 3.2 · video 3.3 · knowledge checks · practice problems
GW CSCI 4431/6431 Computer Networks · UDP Worksheet
This worksheet builds three versions of a reliable data transfer protocol §3.4 — rdt2.0, rdt2.1 and rdt2.2 — over a channel that can corrupt bits but never loses or reorders a packet.
A reliable data transfer protocol lets an application send data as if the channel underneath were perfect, when it is not. The protocol has two halves, a sender and a receiver, and each half is written as a finite state machine §3.4: a few states, and arrows saying which event moves the machine from one state to another and what it does on the way. Each version below is built from the one before it, starting from a channel that never fails, and a table at the end compares all four.
The lower two boxes are the two halves of the protocol and the upper two are the applications that use it. Data travels left to right. The receiver’s answers travel back right to left, so packets cross the channel in both directions even though the application’s data goes only one way.
The code names are the four calls every state machine in this guide is written in. rdt_send() is the sending application handing data down, and deliver_data() is the protocol handing data up at the far end. udt_send() puts a packet on the channel, and rdt_rcv() fires when a packet comes off it — at either end, since both ends send and both receive. The dashed line is the unreliable channel; on this worksheet it can flip bits but never loses or reorders a packet.
Neither side can see across the channel. Each knows only what it has sent and what has reached it, so the sender learns what became of a packet only when an answer arrives that it can read.
rdt1.0A channel that never fails
Start with a channel that never corrupts, loses or reorders anything. The protocol then has nothing to repair: the sender turns each piece of data it is handed into a packet and puts it on the channel, and the receiver takes each packet off the channel and hands its data up. Neither side ever waits for the other, so each machine has a single state.
The sender is drawn above the dashed line and the receiver below it. An oval is a state: where the machine sits until something happens. The dashed arrow marks the state it starts in. A solid arrow is a transition. Above its short rule is the one event that makes it fire, and below the rule is every action the machine takes when it does, in order.
Here each machine’s only arrow leaves its one state and comes straight back: the event happens, the actions run, and the machine is ready for the next event. The sender’s event is the application calling rdt_send(); the receiver’s is a packet arriving, rdt_rcv().
The two vertical lines are the sender and the receiver, with time running down the page. Each sloping arrow is one packet crossing the channel; it slopes because crossing takes time. The text beside a line says what that side does when the event reaches it, and the grey text under each name is the state it starts in.
The application hands over d1 and then d2, and each is delivered the moment it arrives. Two pieces of data take two packets and no replies.
The channel under the transport layer can now flip bits, but it never loses or reorders a packet. A checksum lets whichever side receives a packet tell whether it arrived corrupted. rdt2.0's rules: the receiver answers every data packet with an ACK if it arrived intact or a NAK if it did not, and the sender retransmits whenever it gets a NAK. The sender is stop-and-wait: it sends one packet, then waits for the answer.
Each arrow in a state machine is labelled with the event that makes it fire (above the line) and every action the protocol takes when it does (below the line). rdt_send() is called by the application above; rdt_rcv() fires when a packet arrives from the channel below; udt_send() hands a packet to the unreliable channel; deliver_data() passes data up to the receiving application after a call to extract().
| Events — each labels exactly one arrow | Actions — use as many as an arrow needs | ||
|---|---|---|---|
| A | rdt_rcv(rcvpkt) && corrupt(rcvpkt) | 1 | udt_send(sndpkt) |
| B | rdt_send(data) | 2 | deliver_data(data) |
| C | rdt_rcv(rcvpkt) && isNAK(rcvpkt) | 3 | udt_send(NAK) |
| D | rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) | 4 | sndpkt = make_pkt(data, checksum) |
| E | rdt_rcv(rcvpkt) && isACK(rcvpkt) | 5 | Λ // do nothing |
| 6 | udt_send(ACK) | ||
| 7 | extract(rcvpkt, data) |
Complete both machines: On each arrow write the event's letter above the line and its action numbers below, in the order they happen. Give the sender's second state a name that says what it is waiting for.
The sender needs two states; the receiver gets by with one. What is the sender remembering while it sits in its second state that the receiver never has to remember from one packet to the next?
1five events, five arrows
| Machine | Arrow | Event | Actions |
|---|---|---|---|
| Sender | call from above → wait for ACK/NAK | B | 4, 1 |
| Sender | wait for ACK/NAK ↺ | C | 1 |
| Sender | wait for ACK/NAK → call from above | E | 5 |
| Receiver | wait for call from below ↺ | A | 3 |
| Receiver | wait for call from below ↺ | D | 7, 2, 6 |
Any name saying what the sender awaits is right. The ACK arrow does nothing
(Λ) — its whole job is the change of state. 4 before 1:
nothing to send until the packet is made.
If you wanted a corrupt(rcvpkt) arrow on the
sender, you found Q2 early. The rdt2.0 sender never checks whether the
reply arrived intact.
2That a packet is outstanding, and the packet itself
It must not accept new data while one is unacknowledged, and
sndpkt must survive until the ACK arrives or there is nothing to
retransmit. The receiver judges every packet on its own and carries nothing
from one to the next.
§3.4 Principles of Reliable Data Transfer · video · knowledge checks · practice problems
rdt2.0A channel with bit errors
Now the channel can flip bits inside a packet, though it still never loses or reorders one. rdt2.0 adds three things. A checksum §3.3 travels in every packet, so the side that receives it can tell whether it arrived intact. The receiver answers every data packet: an ACK (acknowledgment) if it arrived intact, a NAK (negative acknowledgment) if it did not. And the sender sends the packet again whenever a NAK comes back. The sender is stop-and-wait: after sending a packet it waits for the answer before it takes more data from the application, which is why it now has a second state.
The sender’s two states are Wait for call from above, where it waits for data, and Wait for ACK or NAK, where it waits for the receiver’s answer. The receiver still has one state, with one arrow for a packet that fails its checksum and one for a packet that passes. Λ under a rule means the transition takes no action; the ACK’s only effect is to move the sender back to its first state.
An intact packet is delivered and acknowledged. A corrupted one is answered with a NAK, and the NAK makes the sender send the same packet again. Until an ACK arrives, the sender stays in Wait for ACK or NAK and takes no new data.
Same layout as the rdt1.0 run. The zigzag marks a packet whose bits the channel flipped: it still arrives, but it fails its checksum. Grey text after an arrow is the state that side moves to.
d1 goes straight through: delivered, acknowledged, and the ACK returns the sender to Wait for call from above. The first copy of d2 fails its checksum, so the receiver answers with a NAK and delivers nothing. The NAK makes the sender send d2 again, and the second copy is delivered and acknowledged. The receiving application gets d1 and d2, once each, after six packets.
rdt2.0 has no arrow for an ACK or NAK that itself arrives corrupted. Q2 works out what that costs.
Use your rdt2.0 machines from Q1. The application calls rdt_send() twice — first with data d1, then with d2 — and both machines start in their Wait for call states. Each row of a trace is one packet crossing the channel, in the order it is sent. Row 1 is filled in as an example.
The channel corrupts the first copy of d1 and nothing else. Trace the exchange until d2 has been acknowledged. What does the receiving application end up with?
| # | Direction | Packet | Arrives intact? | Actions at the side it reaches | Sender's state afterward |
|---|---|---|---|---|---|
| 1 | S → R | data d1 | no | udt_send(NAK) | Wait for ACK or NAK |
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| 6 | |||||
| 7 |
The receiving application gets:
Start over. This time the first copy of d1 arrives intact, but the receiver's response is corrupted on its way back. Which arrow in your sender machine does that garbled packet take? What does the receiver believe has happened to d1?
The sender cannot read the garbled response, so it has to guess what it was. For each case, what does the receiving application end up with once d2 has gone through?
| It really was an ACK | It really was a NAK | |
|---|---|---|
Sender guesses ACK and moves on to d2 | ||
Sender guesses NAK and resends d1 |
1d1, d2 — once each
| # | Dir | Packet | Intact | Action where it lands | Sender after |
|---|---|---|---|---|---|
| 1 | S→R | data d1 | no | send NAK | wait ACK/NAK |
| 2 | R→S | NAK | yes | resend d1 | wait ACK/NAK |
| 3 | S→R | data d1 | yes | deliver d1, send ACK | wait ACK/NAK |
| 4 | R→S | ACK | yes | Λ | call from above |
| 5 | S→R | data d2 | yes | deliver d2, send ACK | wait ACK/NAK |
| 6 | R→S | ACK | yes | Λ | call from above |
Six packets to move two pieces of data; row 7 stays empty. Row 3 is the one to check: the sender is still waiting after the receiver has delivered and answered.
2None of them
The sender's only events there are isACK and isNAK,
and a garbled packet cannot be trusted to be either — so the specification has
no transition at all. The receiver meanwhile believes d1 is
done, and neither side can see the other.
3Neither guess is safe
| It really was an ACK | It really was a NAK | |
|---|---|---|
| Guesses ACK | d1, d2 — fine | d2 only — d1 lost, silently |
| Guesses NAK | d1, d1, d2 — a duplicate | d1, d2 — fine |
Guess ACK when it was a NAK and the sender throws away the only copy of
d1. Guess NAK when it was an ACK and the receiver — remembering
nothing — delivers d1 twice.
The fix is to always resend, because a duplicate can be repaired and a loss cannot. Telling copies apart needs a label on each packet — a sequence number, which is Q3.
§3.4 Principles of Reliable Data Transfer · video · knowledge checks · practice problems
rdt2.1Handling corrupted ACKs and NAKs
The channel is the same, but rdt2.1 allows for what rdt2.0 ignored: an ACK or a NAK can be corrupted just as easily as a data packet. A sender that cannot read the answer sends the packet again, to be safe. If the answer had been an ACK, the receiver now gets a second copy of a packet it has already delivered, so it needs a way to recognize a copy. rdt2.1 gives every data packet a one-bit sequence number, 0 or 1, alternating from one packet to the next, and the receiver remembers which number it expects next. A packet with the expected number is new. A packet with the other number is a copy: the receiver acknowledges it again but does not deliver it.
The sender now has four states, because it has to remember which sequence number it is using. The top row sends packet 0 and waits for its answer, the bottom row does the same for packet 1, and an intact ACK moves the sender from one row to the other. The worksheet calls these states call 0, wait 0, call 1 and wait 1.
To fit, each receive event is written without the rdt_rcv(rcvpkt) && that begins all of them and without the (rcvpkt) argument, so corrupt || isNAK stands for rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || isNAK(rcvpkt)).
The loop on each waiting state carries the new rule: a corrupted answer makes the sender send the packet again, exactly as a NAK does.
The receiver has two states, one for each number it can be expecting: Wait for 0 from below and Wait for 1 from below, which the worksheet calls expect 0 and expect 1. The abbreviations are the same as in the sender, and answers are written udt_send(ACK) and udt_send(NAK) as on the worksheet.
Each state has two loops. A corrupted packet gets a NAK. An intact packet with the other number is a copy of one already delivered, so it gets an ACK and nothing is delivered. Only an intact packet with the expected number is delivered, and it moves the receiver on to expecting the other number.
Same layout as the earlier runs, with the worksheet’s short state names: the sender’s on the left, the receiver’s on the right.
d1 travels as pkt0 and d2 as pkt1, and both are delivered. The ACK for pkt1 comes back corrupted, so the sender, still in wait 1, sends pkt1 again. The receiver is expecting 0 by now, sees a 1, and knows the packet is a copy: it sends another ACK and delivers nothing. That ACK arrives intact and the sender moves on to call 0. The application gets d1 and d2, once each.
rdt2.1 fixes the flaw from Q2. Every data packet now carries a sequence number, 0 or 1, alternating: d1 goes out as pkt0, d2 as pkt1, d3 as pkt0 again. ACKs and NAKs carry no number.
pktN it retransmits pktN whenever the response is corrupted or a NAK, and moves on only when an intact ACK arrives. Its states: call 0 → wait 0 → call 1 → wait 1 → back to call 0.Replay Q2 part 2 under rdt2.1: pkt0 carrying d1 arrives intact, the ACK is corrupted on its way back, and nothing else goes wrong. Trace until d2 has been acknowledged. What does the receiving application end up with?
| # | Direction | Packet | Arrives intact? | Actions at the side it reaches | Sender state after | Receiver state after |
|---|---|---|---|---|---|---|
| 1 | S → R | pkt0 (d1) | yes | deliver d1, send ACK | wait 0 | expect 1 |
| 2 | ||||||
| 3 | ||||||
| 4 | ||||||
| 5 | ||||||
| 6 | ||||||
| 7 |
The receiving application gets:
In row 3 the receiver sends an ACK for a packet it is about to throw away. What would happen if it sent a NAK instead? What if it sent nothing?
Why are two sequence numbers enough? Describe what would have to happen for a single bit to become ambiguous, and say why that cannot happen on this channel.
1d1, d2 — once each
| # | Dir | Packet | Intact | Action where it lands | Sender | Receiver |
|---|---|---|---|---|---|---|
| 1 | S→R | pkt0 (d1) | yes | deliver d1, send ACK | wait 0 | expect 1 |
| 2 | R→S | ACK | no | resend pkt0 | wait 0 | expect 1 |
| 3 | S→R | pkt0 (d1) | yes | duplicate: ACK, do not deliver | wait 0 | expect 1 |
| 4 | R→S | ACK | yes | Λ | call 1 | expect 1 |
| 5 | S→R | pkt1 (d2) | yes | deliver d2, send ACK | wait 1 | expect 0 |
| 6 | R→S | ACK | yes | Λ | call 0 | expect 0 |
Same channel and failure as Q2 part 2, but the bottom-left box of that table is
gone: the sender still resent, and the receiver saw 0 while
expecting 1 and knew it was a copy.
2NAK loops forever · nothing hangs forever
The sender is still in wait 0, and the receiver's ACK is the only way it
will learn d1 arrived. A NAK makes it resend
pkt0, the receiver NAKs the duplicate again, and nothing moves.
Nothing leaves it waiting forever — rdt2.1 has no timer. Timers are
rdt3.0's addition §3.4.
3Only one packet is ever outstanding
Stop-and-wait means the receiver answers one question: is this the packet I just delivered, or the next one? Two possibilities, one bit. Ambiguity would need a copy two steps old, and on this channel packets are never reordered or delayed past a later one.
§3.4 Principles of Reliable Data Transfer · video · knowledge checks · practice problems
rdt2.1 recovers from every corruption this channel can cause, using two kinds of answer. rdt2.2 does the same with one.
rdt2.2A NAK-free protocol
rdt2.2 does the same job as rdt2.1 without the NAK. Every ACK now
carries a sequence number, ACK0 or ACK1, naming the last
packet the receiver accepted intact. When a packet arrives corrupted, or arrives as
a copy, the receiver sends the ACK for the last packet it did accept, again. So a
sender waiting for ACK0 that receives ACK1 learns that
packet 0 has not been accepted, and sends it again — the same thing a NAK would have
made it do. TCP also has no NAK, and uses this same approach §3.5.
Drawn in the same layout as rdt2.1’s sender and with the same abbreviations, so the two figures can be compared label by label. The waiting states now wait for a numbered ACK, Wait for ACK 0 and Wait for ACK 1, and isACK(0) means an intact ACK carrying the number 0.
Only the events have changed. Each waiting state’s loop now fires on a corrupted answer or on the ACK with the other number, and each ACK arrow fires only on the ACK with the right number.
Same layout as rdt2.1’s receiver. Each state now has a single loop, because a corrupted packet and a copy get the same answer: the ACK for the last packet the receiver accepted, sent again.
In Wait for 0 from below the last packet accepted was packet 1, so the loop sends ACK1; in Wait for 1 from below it sends ACK0.
Same layout as the earlier runs, with a third piece of data, d3, so that packet 0 is used a second time.
d1 and d2 are delivered and acknowledged with ACK0 and ACK1. d3 goes out as pkt0 and arrives corrupted. The receiver, still expecting 0, does not say the packet was bad: it sends ACK1 again, the ACK for the last packet it accepted. The sender is waiting for ACK0, so ACK1 tells it that pkt0 was not accepted, and it sends pkt0 again. The second copy is delivered and acknowledged with ACK0.
rdt2.2 does the same job as rdt2.1 with one fewer message type: the receiver never sends a NAK. Instead every ACK carries a sequence number — ACK0 or ACK1 — naming the last packet the receiver accepted intact. Data packets are numbered as in Q3, and the state names are the same.
ACKN, an intact ACKN lets it move on. A corrupted response, or an ACK with the other number, makes it retransmit.The application sends d1 as pkt0, then d2 as pkt1. The channel corrupts the first copy of pkt1 and nothing else. Trace until d2 has been acknowledged.
| # | Direction | Packet | Arrives intact? | Actions at the side it reaches | Sender state after | Receiver state after |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 2 | ||||||
| 3 | ||||||
| 4 | ||||||
| 5 | ||||||
| 6 | ||||||
| 7 |
In row 4 the sender is waiting for ACK1 and receives a second ACK0. Which rdt2.1 message is that ACK0 doing the job of? Why does the ACK have to carry a number for this to work?
1six rows
| # | Dir | Packet | Intact | Action where it lands | Sender | Receiver |
|---|---|---|---|---|---|---|
| 1 | S→R | pkt0 (d1) | yes | deliver d1, send ACK0 | wait 0 | expect 1 |
| 2 | R→S | ACK0 | yes | Λ | call 1 | expect 1 |
| 3 | S→R | pkt1 (d2) | no | resend ACK0 | wait 1 | expect 1 |
| 4 | R→S | ACK0 | yes | resend pkt1 | wait 1 | expect 1 |
| 5 | S→R | pkt1 (d2) | yes | deliver d2, send ACK1 | wait 1 | expect 0 |
| 6 | R→S | ACK1 | yes | Λ | call 0 | expect 0 |
Row 2 → 3: the sender moves to call 1, and
rdt_send(d2) takes it to wait 1 before pkt1
goes out. Row 3 is the new idea: the receiver never says "that was bad",
only "the last thing I got intact was pkt0".
2It is doing the NAK's job
A repeated ACK0 while the sender waits for ACK1 means
the receiver has nothing newer than pkt0: resend. Without the
number the sender would read a plain ACK as confirming pkt1 and
lose d2 — the top-right box of Q2 part 3 again.
If you read ACK0 as "resend pkt0",
you have the direction backwards. An ACK names what the receiver
received, never what the sender should send.
The stronger reason to drop the NAK is loss: a vanished packet produces no NAK and no ACK at all, so the sender needs a timer anyway — and once the timer exists it covers corruption too. TCP does exactly this §3.5.
§3.4 Principles of Reliable Data Transfer · video · knowledge checks · practice problems
Each column is one version of the protocol, and each row asks the same question of all four.
| rdt1.0 | rdt2.0 | rdt2.1 | rdt2.2 | |
|---|---|---|---|---|
| What the channel does | nothing goes wrong | flips bits | flips bits | flips bits |
| New in this version | — | checksum, ACK and NAK, sending again | a sequence number, 0 or 1, on each data packet | a number on each ACK; no NAK |
| The receiver answers with | nothing | ACK or NAK | ACK or NAK | ACK0 or ACK1 |
| The sender sends again when | never | a NAK arrives | a NAK or a corrupted answer arrives | a corrupted answer, or the ACK for the other number, arrives |
| A copy of a packet already delivered | never happens | cannot be recognized | recognized by its number: ACKed, not delivered | recognized by its number: last ACK sent again, not delivered |
| States: sender / receiver | 1 / 1 | 2 / 1 | 4 / 2 | 4 / 2 |
| Still fails when | any bit flips | an ACK or NAK is corrupted | a packet is lost | a packet is lost |
The worksheet’s channel never loses a packet. When packets can be lost, the sender also needs a timer, so that it sends again when no answer arrives at all. That is rdt3.0 §3.4, in video 3.4b.
§3.4 Principles of Reliable Data Transfer · video 3.4a · video 3.4b · knowledge checks · practice problems
GW CSCI 4431/6431 Computer Networks · RDT Worksheet