WEBVTT 00:00:00.000 --> 00:00:03.690 Welcome back to CSE 316 — Data Communication and Networking. 00:00:03.740 --> 00:00:12.690 This is the detailed video version of Session twenty-three, and I want to say it plainly before anything else: this is the last lecture of the course. 00:00:15.120 --> 00:00:22.190 It has two jobs. The first is TCP — the protocol carrying this sentence to your device right now. 00:00:22.240 --> 00:00:31.190 Its reliability, which resolves last session's fork, because TCP refuses to choose between the two ARQs. And then congestion control: two brakes, two phases, two loss signals, and the most famous picture in networking. 00:00:37.880 --> 00:00:46.830 And the second job is to land the course. In the last few slides we go back to the very first question of Week one — you send "hi" to the person beside you; how many machines touch it? — and this time you answer it properly. 00:00:51.330 --> 00:00:59.035 So: TCP, and then the whole stack. Let us finish this. 00:00:59.085 --> 00:01:03.935 The question this session answers, and it comes in two halves. 00:01:03.985 --> 00:01:12.935 The protocol carrying this sentence to your device has a strange habit. It sends faster, and faster, and faster — until the network drops a packet. 00:01:13.975 --> 00:01:21.125 Then it slows down. And immediately starts speeding up again. Toward the next drop. Forever. On purpose. 00:01:21.175 --> 00:01:28.385 Why that is rational rather than wasteful is what sections two and three derive, rule by rule. 00:01:28.435 --> 00:01:37.385 Half one: loss is the only word a best-effort network speaks. No router ever reports its capacity, so the ceiling can only be found by touching it. 00:01:38.825 --> 00:01:47.775 Half two: every flow halves on a shared loss, and halving takes more from whoever has more — so the flows converge on equal shares, with no referee anywhere in the system. 00:01:51.265 --> 00:01:56.895 And a promise for the end. In the last few slides we go back to the first question of Week one. 00:01:56.945 --> 00:02:05.895 You send "hi" to the person beside you. How many machines touch it? You guessed then. This time you will answer. 00:02:06.790 --> 00:02:10.080 Section one. TCP's reliability. 00:02:10.130 --> 00:02:19.080 Last session ended on a sentence: TCP refuses to choose. Here is the refusal, itemised — and the ACK trace that makes both parents visible. 00:02:24.079 --> 00:02:30.879 TCP in one slide, and every phrase in the first row is examinable. 00:02:30.929 --> 00:02:39.879 Transmission Control Protocol: connection-oriented, reliable, byte-stream transport. The machine carrying most of the Internet. 00:02:40.559 --> 00:02:44.859 Byte-stream is the word to respect. TCP numbers BYTES, not segments. 00:02:44.909 --> 00:02:53.789 A segment's sequence number is the number of its first byte, and an acknowledgment names the next byte expected. 00:02:53.839 --> 00:03:02.209 Connection-oriented — but look at where the state lives. Session eighteen's virtual circuits kept state in every switch on the path. 00:03:02.259 --> 00:03:11.019 TCP's connection lives in exactly two places: the two endpoints. The network between them keeps none of it. 00:03:11.069 --> 00:03:20.019 Three jobs. Reliability, which is last session's ARQ hybridised. Flow control — do not drown the RECEIVER. And congestion control — do not drown the NETWORK. 00:03:22.159 --> 00:03:31.109 Hold that third row. The network between the endpoints is still the best-effort datagram network of Week four, promises not included. It is exactly why the second half of this session has to exist. 00:03:37.712 --> 00:03:42.802 This is the cheapest trap in the topic, so let us disarm it now. 00:03:42.852 --> 00:03:51.802 The sequence number is the number of the segment's first byte. A segment carrying bytes four-thousand-and-one to five-thousand has sequence number four-thousand-and-one. 00:03:53.032 --> 00:04:00.802 Segments are just the envelopes; the contract is about bytes — and that is why the numbers look so large. 00:04:00.852 --> 00:04:07.432 And an acknowledgment names the next byte expected. So that segment is acknowledged by five-thousand-and-one. 00:04:07.482 --> 00:04:16.432 Not by "segment five", and not by five thousand. The acknowledgment is a statement about what the receiver still wants, not about what it got. 00:04:17.562 --> 00:04:26.132 Which makes "ACK three means segment three" the cheapest trap in the topic. It is the first line of the mistakes slide for a reason. 00:04:26.182 --> 00:04:33.929 Disarm it now, and every acknowledgment number in this session reads correctly. 00:04:33.979 --> 00:04:39.749 Last session ended on "TCP refuses to choose". Here is the refusal, itemised. 00:04:39.799 --> 00:04:48.749 Acknowledgments: cumulative, like Go-Back-N. ackNo names the next byte expected — everything before this is safe. 00:04:50.239 --> 00:04:56.789 One acknowledgment retires a batch, and a lost acknowledgment is healed by the next one. 00:04:56.839 --> 00:05:05.359 Buffers: like Selective-Repeat. Out-of-order segments are NOT discarded — they wait in the receiver's buffer while the hole fills. 00:05:05.409 --> 00:05:11.809 The SACK extensions even name them explicitly, so the sender knows which ones arrived. 00:05:11.859 --> 00:05:20.809 One retransmission timer, on the oldest unacknowledged byte. Restarted as acknowledgments arrive, and sized from a live estimate of the round-trip time rather than from a constant. 00:05:24.989 --> 00:05:33.869 And the shortcut: fast retransmit. Three duplicate acknowledgments for the same byte mean one segment is missing and the rest arrived. 00:05:33.919 --> 00:05:37.599 Resend it now; do not wait for the timer. 00:05:37.649 --> 00:05:46.599 So the answer to last session's fork is: both. Go-Back-N's acknowledgments, Selective-Repeat's buffers, and two different ways to notice a loss. 00:05:47.379 --> 00:05:56.329 Because real channels vary — sometimes clean, sometimes lossy — and a protocol that bets on either extreme is wrong half the time. 00:05:59.396 --> 00:06:07.886 Fast retransmit deserves a slide of its own, because the asymmetry it introduces runs the rest of this session. 00:06:07.936 --> 00:06:14.636 A duplicate acknowledgment means something arrived — and it was not the thing that was missing. 00:06:14.686 --> 00:06:23.636 The receiver got a segment, could not deliver it, and repeated its old acknowledgment. That is data, not an error. 00:06:23.896 --> 00:06:32.846 Three of them mean the pipe still works. Later segments are getting through, so the path is alive — and exactly one thing is missing. 00:06:35.056 --> 00:06:36.666 That is enough to act on. 00:06:36.716 --> 00:06:43.186 So resend that one segment now, without waiting for the timer — which can be a whole round trip earlier. 00:06:43.236 --> 00:06:49.836 That is fast retransmit, and it is the reason a single loss barely dents a healthy TCP connection. 00:06:49.886 --> 00:06:55.046 And here is the asymmetry being born. Duplicate acknowledgments are the network being TALKATIVE. 00:06:55.096 --> 00:07:04.046 A timeout is SILENCE — and silence is much worse news. Everything in TCP's congestion response is downstream of that one distinction. 00:07:05.977 --> 00:07:11.677 Now the trace. Get a pen — this one you should do rather than watch. 00:07:11.727 --> 00:07:20.677 The sender ships segments of a thousand bytes: bytes one to a thousand, then 1001 to 2000, 2001 to 3000, 3001 to 4000, and 4001 to 5000. 00:07:23.297 --> 00:07:25.567 Five envelopes, five thousand bytes. 00:07:25.617 --> 00:07:33.907 Segment two — bytes 1001 to 2000 — is lost. Destroyed on the wire, and nobody says so. 00:07:33.957 --> 00:07:41.127 There is no "I got a broken one" message in TCP, or in any of last session's protocols. 00:07:41.177 --> 00:07:50.127 Everything else arrives, intact and on time. Which is exactly the situation last session's two protocols disagreed about — and TCP is about to show you its answer. 00:07:53.027 --> 00:07:59.687 So: what acknowledgment numbers come back, and what does the sender do? 00:07:59.737 --> 00:08:08.687 Pause here and write the whole ACK column yourself. There are five arrivals and one retransmission, and every number is forced. 00:08:17.093 --> 00:08:26.043 Forty-two seconds on the whole of TCP's reliability, ending on the two brakes — which is the second section of this session. 00:08:28.253 --> 00:08:36.313 The five segments by byte range, and then the line underneath: bytes 4001 to 5000 becomes ACK 5001. 00:08:36.363 --> 00:08:44.543 The four rows of the refusal: cumulative ACKs in blue, buffering in green, one timer, and fast retransmit in orange. 00:08:44.593 --> 00:08:52.033 Blue from Go-Back-N, green from Selective-Repeat. The colours are the argument. 00:08:52.083 --> 00:09:01.033 The trace begins. Watch segment two go red, then three, four and five turn amber as they are buffered — and the ACK column filling with 1001. 00:09:03.983 --> 00:09:12.933 Dup three fires, and segment two goes back on the wire alone. And read the last row of the caption: a timeout is silence, and silence is much worse news. 00:09:16.813 --> 00:09:25.763 There is the jump. One acknowledgment retiring four segments, and the two cards underneath naming which parent each half came from. 00:09:26.293 --> 00:09:35.243 Now the second section, previewed. rwnd in green — advertised in every ACK. cwnd in red — advertised by nobody at all. 00:09:36.263 --> 00:09:45.213 And the formula, with the line that sets up everything after the section break: all the drama is inside cwnd. 00:09:46.820 --> 00:09:53.230 Now line by line, and check each one against what you wrote. 00:09:53.280 --> 00:10:01.100 Segment one lands. The receiver holds bytes one to a thousand, so the next byte it expects is 1001. ACK 1001. 00:10:01.150 --> 00:10:06.320 A cumulative acknowledgment, and so far entirely ordinary. 00:10:06.370 --> 00:10:15.320 Segment three lands — but the receiver is still missing byte 1001, so it says so again. ACK 1001, duplicate number one. 00:10:15.410 --> 00:10:24.360 And notice the second thing that just happened: segment three was BUFFERED, not binned. That is Selective-Repeat's behaviour, in the same breath as Go-Back-N's acknowledgment. 00:10:28.530 --> 00:10:34.750 Segment four lands. Buffered as well, and the acknowledgment repeats: duplicate number two. 00:10:34.800 --> 00:10:40.460 The receiver's buffer now holds two segments it is not allowed to deliver. 00:10:40.510 --> 00:10:45.810 Segment five lands. Duplicate number three — and three is the trigger. 00:10:45.860 --> 00:10:53.630 Fast retransmit: segment two crosses the wire again, alone, without waiting for the timer. 00:10:53.680 --> 00:10:58.980 And when it lands, the receiver's buffer already holds three, four and five. 00:10:59.030 --> 00:11:07.980 The hole fills, the buffer drains, and the next acknowledgment jumps straight to 5001. One acknowledgment retiring four segments, and the sender's window sliding four forward at once. 00:11:12.210 --> 00:11:21.160 That one jump is both parents visible at once: a cumulative acknowledgment retiring a Selective-Repeat buffer. 00:11:22.886 --> 00:11:25.766 Checkpoint one. 00:11:25.816 --> 00:11:34.766 One: a segment carries bytes 7001 to 8000 and arrives intact. What acknowledgment number comes back? 00:11:34.826 --> 00:11:41.446 Two: why does the receiver send ACK 1001 four times rather than reporting the loss? 00:11:41.496 --> 00:11:48.016 Three: what exactly triggers fast retransmit, and what does it save? 00:11:48.066 --> 00:11:57.016 One: 8001. The acknowledgment names the next byte expected — not the last byte received, and not the segment number. That single habit disarms the cheapest trap in this topic. 00:12:00.526 --> 00:12:09.476 Two: because there is no "this one was broken" message in TCP. A cumulative acknowledgment can only ever name the hole, so while byte 1001 is missing every ACK says 1001 — and the repetition itself becomes the report. 00:12:13.606 --> 00:12:22.556 Three: three duplicate acknowledgments for the same byte. It saves up to a whole retransmission timeout — the sender resends immediately instead of waiting for a timer sized from the round-trip estimate. 00:12:31.950 --> 00:12:35.110 Section two. Two brakes on one sender. 00:12:35.160 --> 00:12:44.110 The receiver can simply say how much room it has. The network says nothing at all — and that silence is the whole problem of the second half of this session. 00:12:48.168 --> 00:12:55.318 A TCP sender wears two brakes, and the second row is the hinge of the whole session. 00:12:55.368 --> 00:13:04.318 The first brake is honest: rwnd, the receiver's advertised window. Every acknowledgment says "my buffer has room for this many more bytes." 00:13:05.918 --> 00:13:14.328 Flow control: do not drown the endpoint. Simple, because the receiver can just tell you — and the number is exact. 00:13:14.378 --> 00:13:23.328 The second brake has nobody to tell you. The network's capacity — the routers, the queues, other people's traffic — is advertised by no one, because the datagram network does not talk. 00:13:26.568 --> 00:13:35.518 Session eight: best effort, no promises, no reports. So the sender must maintain its own guess, and that guess has a name: cwnd, the congestion window. 00:13:38.918 --> 00:13:44.788 The real sending window is the minimum of the two: min of rwnd and cwnd. 00:13:44.838 --> 00:13:53.788 Two brakes, and the softer one rules. If the receiver is slow, rwnd governs; if the network is congested, cwnd governs. 00:13:55.058 --> 00:14:01.468 And all the drama is inside cwnd. Flow control is easy because somebody tells you the answer. 00:14:01.518 --> 00:14:10.468 Congestion control is hard because nobody will — and the rest of this session is nothing but the rules for guessing. 00:14:11.202 --> 00:14:17.902 Why is guessing dangerous? Week four drew this curve; here is what it means for a sender. 00:14:17.952 --> 00:14:22.802 Below the knee, more load means more throughput. The network absorbs it. 00:14:22.852 --> 00:14:29.362 This is the region every sender wants to live in — and none of them can see where it ends. 00:14:29.412 --> 00:14:38.362 Past the knee, every extra packet buys delay, not throughput. It stands in a queue — Week four's queuing thief, collecting again. 00:14:38.632 --> 00:14:43.002 The line looks busier, and nothing arrives sooner. 00:14:43.052 --> 00:14:50.502 And past the cliff, queues overflow. Routers drop; senders retransmit; and retransmissions ARE load. 00:14:50.552 --> 00:14:55.912 The feedback loop points the wrong way, and the harder everyone tries the less gets through. 00:14:55.962 --> 00:15:04.912 Every TCP sender must find the knee — of a path it cannot see, sharing with senders it cannot count, on a network that reports nothing at all. That is the problem statement. 00:15:10.653 --> 00:15:13.683 And this is not a thought experiment. 00:15:13.733 --> 00:15:22.683 In 1986 throughput on the Internet's backbone fell from thirty-two kilobits per second to forty bits per second — a factor of about a thousand. Everyone resending everything, and almost nothing arriving. 00:15:27.253 --> 00:15:32.263 That is congestion collapse — observed, not theorised. 00:15:32.313 --> 00:15:41.263 The mechanism was exactly the feedback loop on the last slide. Queues overflowed, routers dropped, senders timed out and resent. 00:15:41.363 --> 00:15:45.743 The response to congestion made the congestion worse. 00:15:45.793 --> 00:15:49.873 Congestion control was written from that autopsy, not from theory. 00:15:49.923 --> 00:15:55.203 Every rule in the rest of this session is a lesson somebody paid for. 00:15:55.253 --> 00:16:01.463 And what was not available as a fix: the network could not simply be made to report its capacity. 00:16:01.513 --> 00:16:10.463 That refusal is the datagram design, and it WON — Week four, on robustness and simplicity. So the fix had to live in the endpoints, which is where we are about to put it. 00:16:16.756 --> 00:16:25.686 The same trace, one arrival at a time — with the receiver's buffer state written underneath at every step. 00:16:25.736 --> 00:16:31.866 State one: the five byte ranges, segment two marked as the casualty, and the buffer empty. 00:16:31.916 --> 00:16:40.096 Pause here and write the ACK column if you have not already. 00:16:40.146 --> 00:16:48.636 State two: segment one arrives, and the buffer line says the receiver holds bytes 1 to 1000. ACK 1001. 00:16:48.686 --> 00:16:55.756 State three is the important one. Segment three is amber — buffered — and the acknowledgment repeats. 00:16:55.806 --> 00:17:04.756 Read the buffer line: 2001 to 3000, undelivered. Arrived, and not delivered. That distinction is worth two marks. 00:17:05.986 --> 00:17:12.216 State four: four and five arrive and are buffered too, and the third duplicate turns red. 00:17:12.266 --> 00:17:21.216 That red row is the fast-retransmit trigger, and the verdict underneath is the reasoning that justifies it. 00:17:21.276 --> 00:17:30.226 State five: segment two comes back, the hole fills, everything turns green, and the acknowledgment jumps to 5001 in one move. 00:17:31.326 --> 00:17:40.276 State six pulls the two halves apart into cards: cumulative ACKs from Go-Back-N, buffering from Selective-Repeat. 00:17:41.236 --> 00:17:48.636 And the line between them: ACK 5001 is a cumulative acknowledgment retiring a Selective-Repeat buffer. 00:17:48.686 --> 00:17:56.926 State seven is the asymmetry, side by side — the polite signal and the silence, with both responses written out. 00:17:56.976 --> 00:18:05.926 Those two cards are the whole of the next section. Open the demo yourself and read them twice. 00:18:06.214 --> 00:18:12.474 Phase one, and the name is misleading: this phase is exponential. 00:18:12.524 --> 00:18:19.624 Begin with a congestion window of ONE segment, and no assumptions about the path. 00:18:19.674 --> 00:18:26.994 A new connection knows nothing — and starting big on an unknown road is exactly how 1986 happened. 00:18:27.044 --> 00:18:35.994 Every acknowledgment that returns grows the window by one segment. Not every round trip — every acknowledgment. 00:18:36.124 --> 00:18:45.074 So watch the arithmetic: send one, one ACK returns, window two. Send two, two ACKs, window four. Then eight, sixteen, thirty-two. 00:18:46.814 --> 00:18:54.284 The window DOUBLES every round trip — which makes "slow start" the worst-named exponential in engineering. 00:18:54.334 --> 00:19:02.614 Slow compared to what, then? To dumping a full window onto a road nobody has measured. Probe, do not assume. 00:19:02.664 --> 00:19:11.614 And it stops being reckless at a remembered boundary: ssthresh, the slow-start threshold — the height where trouble last began. 00:19:11.954 --> 00:19:20.904 Reach it, and TCP changes gear from doubling to adding one. That gear change is visible as a bend in every sawtooth graph you will ever see. 00:19:22.094 --> 00:19:28.424 So the phase is about ignorance, not speed. It is what a sender does when it has no information at all. 00:19:28.474 --> 00:19:35.926 Once it has some, it slows down on purpose — which is the next slide. 00:19:35.976 --> 00:19:38.036 Phase two. 00:19:38.086 --> 00:19:46.216 Past ssthresh, the knee is close, so growth goes linear: plus one segment per ROUND TRIP — not per acknowledgment. 00:19:46.266 --> 00:19:53.406 Sixteen, seventeen, eighteen. Creeping up on the ceiling instead of vaulting past it. 00:19:53.456 --> 00:20:01.946 Because ssthresh is a memory of where trouble last began, and the whole point of remembering it is not to arrive there again at full speed. 00:20:01.996 --> 00:20:07.546 Below it, ignorance and speed. Above it, knowledge and caution. 00:20:07.596 --> 00:20:12.176 And loss will come. It must — finding the ceiling is the whole method. 00:20:12.226 --> 00:20:21.176 That is not a failure of the protocol; it is the protocol working. The only way to learn where the limit is, is to touch it. 00:20:22.643 --> 00:20:24.843 Checkpoint two. 00:20:24.893 --> 00:20:33.383 One: a sender has rwnd of twelve and cwnd of five. How much may it have outstanding, and why? 00:20:33.433 --> 00:20:41.913 Two: cwnd is four, ssthresh is sixteen. What is cwnd after one clean round trip, and after two? 00:20:41.963 --> 00:20:48.773 Three: why can the network not simply tell TCP how much capacity is available? 00:20:48.823 --> 00:20:57.773 One: five segments' worth. The sending window is the minimum of rwnd and cwnd, and the softer brake rules. Here the network is the binding constraint, not the receiver. 00:21:01.573 --> 00:21:10.523 Two: cwnd is below ssthresh, so this is slow start and the window doubles: eight after one round trip, sixteen after two. At sixteen it reaches ssthresh and switches to congestion avoidance. 00:21:15.303 --> 00:21:24.253 Three: because the datagram network makes no promises and keeps no per-flow state — no reservations and no reports, by design, from Week four. That design won on robustness and simplicity, and the bill is that every sender must infer capacity for itself. 00:21:36.330 --> 00:21:39.270 Section three. The two loss signals. 00:21:39.320 --> 00:21:48.270 The asymmetry born at fast retransmit now governs everything: what TCP does about a loss depends entirely on how it found out. 00:21:51.555 --> 00:21:54.915 Four rows, in two pairs. 00:21:54.965 --> 00:22:03.505 Three duplicate acknowledgments: the polite signal. Later segments got through, so the pipe still works and exactly one segment died. 00:22:03.555 --> 00:22:07.035 Mild news — and detailed news. 00:22:07.085 --> 00:22:13.755 Response: remember half the current window as the new ssthresh, and cut cwnd to that same half. 00:22:13.805 --> 00:22:21.515 Then carry on avoiding — the phase does not change. That is the multiplicative decrease in AIMD. 00:22:21.565 --> 00:22:28.495 A timeout: silence. No duplicates came back at all, which means later segments are not getting through either. 00:22:28.545 --> 00:22:34.015 The path itself may be gone. Severe news, and no detail at all. 00:22:34.065 --> 00:22:42.875 Response: the same ssthresh bookkeeping — and then cwnd collapses all the way to one, and slow start begins again from the bottom. 00:22:42.925 --> 00:22:51.875 Mild signal, mild cut. Severe signal, total humility. Both share the ssthresh rule, and they differ entirely in what happens to cwnd — and that is the pair the exam most wants you to separate. 00:22:59.055 --> 00:23:05.625 Four rules. Write them at the top of the page before you attempt any trace. 00:23:05.675 --> 00:23:12.005 Rule one, slow start: while cwnd is below ssthresh, the window doubles every round trip. 00:23:12.055 --> 00:23:20.465 Because the path is unknown — and geometric probing finds an unknown ceiling faster than linear probing does. 00:23:20.515 --> 00:23:26.735 Rule two, congestion avoidance: at or past ssthresh, add one segment per round trip. 00:23:26.785 --> 00:23:35.195 Because the knee is near, and the cost of overshooting is a whole halving. So approach it slowly. 00:23:35.245 --> 00:23:44.195 Rule three, three duplicate acknowledgments: ssthresh becomes cwnd over two, cwnd becomes that same half, and the sender stays in avoidance. 00:23:44.675 --> 00:23:53.345 Mild signal, mild cut — the pipe still works, so do not throw away everything you learned about it. 00:23:53.395 --> 00:24:00.385 Rule four, timeout: ssthresh becomes cwnd over two, cwnd becomes one, and slow start begins again. 00:24:00.435 --> 00:24:09.195 Severe signal, total humility — you know nothing about this path any more, so behave like a new connection. 00:24:09.245 --> 00:24:14.605 And that is the whole mechanism. Four rules, one variable, and no help from anybody. 00:24:14.655 --> 00:24:23.605 Every number in a trace is one of these four firing. If you can name which, you can do any trace on any paper. 00:24:24.419 --> 00:24:30.369 Put the phases on one time axis and you get the most famous picture in networking. 00:24:30.419 --> 00:24:36.159 Exponential climb, linear creep, halve, creep, crash, climb again. 00:24:36.209 --> 00:24:44.879 Additive increase, multiplicative decrease — AIMD. Climb by one, fall by half. And the shape IS the mechanism, drawn. 00:24:44.929 --> 00:24:53.879 And you have all seen this graph already. Every download-speed monitor you have ever watched wobble was showing you exactly this. 00:24:54.319 --> 00:24:59.469 You were watching cwnd hunt for the knee, and you did not know its name. 00:24:59.519 --> 00:25:03.539 One more thing: the shape is not a flaw. It is the search. 00:25:03.589 --> 00:25:12.539 A flat line would mean the sender had stopped looking for the ceiling. The wobble is the protocol continuing to ask a question whose answer keeps changing. 00:25:16.459 --> 00:25:23.839 Forty-two seconds on the whole congestion story, ending on the half of the hook answer we have not delivered yet. 00:25:23.889 --> 00:25:30.989 The curve drawing itself, with the knee and then the cliff marked. Watch the right-hand side fall. 00:25:31.039 --> 00:25:39.989 The number in red, and the four rows of the autopsy. The third row is the one to read twice: the feedback loop pointed the wrong way. 00:25:40.869 --> 00:25:49.669 The chart begins: one, two, four, eight, in green, with ssthresh dashed across at eight. 00:25:49.719 --> 00:25:58.669 The line changes colour and slope at the dashed line — that bend is the gear change, and it is the thing to point at in an exam answer. 00:25:58.949 --> 00:26:07.899 The two signal cards side by side. Read the last three bullets of each: the ssthresh rule is shared, and the cwnd rule is not. 00:26:08.979 --> 00:26:17.929 And the full sawtooth, drawn: climb, halve, climb, crash, climb. Note the dashed ssthresh line moving down with each loss. 00:26:20.459 --> 00:26:29.409 Two flows, one link, no referee — the blue one starting big, the green one starting small, and the gap closing every time they both halve. 00:26:33.782 --> 00:26:39.552 Checkpoint three, and these three are the ones that turn into exam marks. 00:26:39.602 --> 00:26:48.122 One: cwnd is twelve when three duplicate acknowledgments arrive. Give the new ssthresh and the new cwnd. 00:26:48.172 --> 00:26:54.842 Two: same connection, but a TIMEOUT at cwnd twelve instead. Now give both. 00:26:54.892 --> 00:27:03.402 Three: in one sentence, why does a timeout deserve a harsher response than three duplicate acknowledgments? 00:27:03.452 --> 00:27:12.402 One: ssthresh six, and cwnd six. The sender stays in congestion avoidance and carries on adding one per round trip. Mild signal, mild cut. 00:27:12.992 --> 00:27:21.942 Two: ssthresh six again — the bookkeeping is identical — but cwnd collapses to one, and slow start begins from the bottom. Severe signal, total humility. 00:27:24.332 --> 00:27:33.282 Three: because duplicate acknowledgments prove that later segments are still arriving, so the path works and only one segment died; silence proves nothing is getting through, so the sender must assume it knows nothing about the path any more. 00:27:42.062 --> 00:27:45.482 Section four. The answer, and the course. 00:27:45.532 --> 00:27:54.482 One trace to make the rules automatic, then the answer to the hook — and then twelve weeks of this course, assembled on the question that opened it. 00:27:57.928 --> 00:28:05.008 This is the one to do on paper. Pause after the fourth click and take three minutes. 00:28:05.058 --> 00:28:14.008 The events, per round trip: five clean round trips, then three duplicate acknowledgments, then two clean round trips, then a TIMEOUT, then one clean round trip. 00:28:20.088 --> 00:28:22.588 Start: cwnd of one, ssthresh of eight. 00:28:22.638 --> 00:28:29.348 And no calculator is needed for any of this. Nothing here is harder than doubling or halving. 00:28:29.398 --> 00:28:35.898 Write cwnd after every step. And beside each number, write which of the four rules produced it. 00:28:35.948 --> 00:28:41.288 That second column is what turns a lucky answer into a reliable one. 00:28:41.338 --> 00:28:50.288 The common slip is forgetting the ssthresh update. Both loss signals change it, and a forgotten update sends every later step in the wrong direction. 00:28:50.478 --> 00:28:59.428 Update ssthresh first, then the window. Pause here — three minutes. 00:29:01.321 --> 00:29:04.741 Debrief, one event at a time. 00:29:04.791 --> 00:29:10.391 Five clean round trips. Slow start doubles: one, two, four, eight. 00:29:10.441 --> 00:29:18.581 And eight is ssthresh — so the gear changes, and the next two are nine and ten. Additive increase. 00:29:18.631 --> 00:29:22.971 Three duplicate acknowledgments at cwnd ten: the polite signal. 00:29:23.021 --> 00:29:29.671 ssthresh becomes five, cwnd becomes five. Halve the window, keep the phase. 00:29:29.721 --> 00:29:36.821 Two clean round trips. Still in congestion avoidance, because five is not below the new ssthresh of five. 00:29:36.871 --> 00:29:44.681 Six, then seven — one segment per round trip, climbing back toward a ceiling it still cannot see. 00:29:44.731 --> 00:29:53.681 A timeout at cwnd seven: silence. ssthresh becomes three — the same bookkeeping — and then total collapse. 00:29:54.281 --> 00:29:58.691 cwnd goes to one, and slow start begins again. 00:29:58.741 --> 00:30:07.691 One clean round trip. cwnd one is below ssthresh three, so this is slow start, and it doubles to two. 00:30:07.851 --> 00:30:16.801 One, two, four, eight, nine, ten, five, six, seven, one, two. Every number is a rule firing, and no step is arithmetic harder than halving. 00:30:17.351 --> 00:30:26.301 Every final exam in this course's history has one of these traces on it. You have just done the hard one. 00:30:26.388 --> 00:30:30.188 So. Why deliberately cause loss? 00:30:30.238 --> 00:30:33.448 Because loss is the only word the network speaks. 00:30:33.498 --> 00:30:42.448 The datagram network refuses to say "I'm full" — no reservations, no reports. And that refusal WON the design war, back in Week four, on robustness and simplicity. 00:30:45.968 --> 00:30:49.928 So the only way to learn the ceiling is to touch it. 00:30:49.978 --> 00:30:54.668 Grow until a drop says "that was too much", back off, grow again. 00:30:54.718 --> 00:31:03.668 The sawtooth is a conversation with a partner whose entire vocabulary is one word. Every climb is a question and every drop is the answer — and the question has to be asked again, because the answer keeps changing. 00:31:09.398 --> 00:31:13.458 And here is the second half. AIMD makes the Internet FAIR. 00:31:13.508 --> 00:31:22.458 Two flows share a link. Both climb by one. Both halve on the shared loss — and halving takes MORE from whoever has more. Run that long enough and the flows converge toward equal shares. 00:31:26.998 --> 00:31:34.718 No referee, no reservation, no negotiation. Billions of selfish senders, disciplined into fairness by arithmetic. 00:31:34.768 --> 00:31:43.718 That is why your download and someone else's video call split the Wi-Fi without either of you configuring anything. 00:31:44.621 --> 00:31:50.871 TCP is done, and the course has one question left — its first one. 00:31:50.921 --> 00:31:59.871 In Week one, minute one, I asked: you send "hi" to the person beside you. How many machines touch it? You guessed. Then you counted: fifteen to twenty-five. 00:32:01.281 --> 00:32:06.881 Today, the message falls through everything you now own. 00:32:06.931 --> 00:32:15.881 Application. The app formats "hi", and a name becomes an address. Sessions one to three — the layered model, and why a name is not a location. 00:32:18.421 --> 00:32:23.791 Transport. A socket pair: your ephemeral port to their well-known one. 00:32:23.841 --> 00:32:32.791 Sequence numbers, acknowledgments and windows standing guard — and cwnd pacing every byte, exactly as fast as the network can bear and no faster. 00:32:35.141 --> 00:32:39.171 Network. IP addresses, masks, longest-prefix forwarding. 00:32:39.221 --> 00:32:48.171 Fifteen to twenty-five routers each choose one best road — and in the core, labels remember the choice. 00:32:48.661 --> 00:32:54.871 Data link. Frames and MAC addresses, and ARP introducing neighbours on every LAN along the path. 00:32:54.921 --> 00:33:02.521 And one of those MAC addresses, in Session twenty, became half of an IPv6 address. 00:33:02.571 --> 00:33:10.551 Physical. Bits become signals on copper, glass and air — and Shannon sets the speed limit on every metre of it. 00:33:10.601 --> 00:33:15.501 Week one you counted the machines. Week twelve you can name every rule they obey. 00:33:15.551 --> 00:33:20.802 That is the entire distance you travelled. 00:33:21.822 --> 00:33:30.772 The same trace, drawn. Watch the shape appear as the rules fire — this is where the sawtooth stops being a picture and becomes a consequence. 00:33:32.262 --> 00:33:39.472 State one: the empty chart, the dashed ssthresh line at eight, and the four rules written out in the verdict. 00:33:39.522 --> 00:33:48.242 Pause and trace the whole thing yourself before going further. 00:33:48.292 --> 00:33:57.242 State two: one, two, four, eight — in green, and steepening. The doubling is visible as a curve rather than a claim. 00:33:58.772 --> 00:34:04.822 State three: the line changes colour to blue at the dashed line, and the slope flattens to nine and ten. 00:34:04.872 --> 00:34:12.312 That bend is the gear change. Point at it in an exam answer and you have earned the mark. 00:34:12.362 --> 00:34:18.722 State four: the red drop from ten to five, and the dashed ssthresh line moving down with it. 00:34:18.772 --> 00:34:26.282 Read the counters: cwnd was ten, ssthresh becomes five, cwnd becomes five, severity mild. 00:34:26.332 --> 00:34:33.472 State five: six and seven, back in blue. Climbing toward a ceiling it still cannot see. 00:34:33.522 --> 00:34:37.912 State six: the long red fall from seven all the way to one, and ssthresh down to three. 00:34:37.962 --> 00:34:46.912 Compare the two red segments on the chart — the halving and the collapse. That difference is the whole of section three, in one picture. 00:34:46.982 --> 00:34:53.962 And state seven: the finished shape, with the final answer written above it. 00:34:54.012 --> 00:35:02.962 Open it yourself and run your own event sequences until predicting the next number is boring. Boring is the target. 00:35:04.428 --> 00:35:08.598 Four lines on what actually happened over twelve weeks. 00:35:08.648 --> 00:35:14.088 In Week one the question was "how many machines touch it?" — and the honest answer was a guess. 00:35:14.138 --> 00:35:20.818 Somewhere between fifteen and twenty-five, and nobody in the room could say what any of them did. 00:35:20.868 --> 00:35:26.718 Now every one of those machines has a name and a rule. A router doing longest-prefix match. 00:35:26.768 --> 00:35:35.718 A switch doing label swap. A network card doing ARP. A transport layer pacing bytes against a window it inferred from nothing but silence. 00:35:37.968 --> 00:35:43.968 And every layer has a price you can state. Best effort bought robustness and cost promises. 00:35:44.018 --> 00:35:52.968 Windows bought throughput and cost state. Labels bought speed and cost locality. Nothing was free, and you can say what each thing cost. 00:35:53.848 --> 00:35:58.458 That is what an engineering education is. Not the facts — the trades. 00:35:58.508 --> 00:36:07.458 You came in able to send a message. You leave able to name every rule that delivers it, and to say what each one cost. 00:36:08.761 --> 00:36:12.321 Practical things, and then we finish. 00:36:12.371 --> 00:36:19.461 The rituals that never fail. N, mask, AND, first, last — the Session eleven ritual, unchanged. 00:36:19.511 --> 00:36:28.461 a equals T-p over T-f before any utilisation. Split, stuff, flip before any interface ID. And write the method before the answer, always. 00:36:28.581 --> 00:36:36.711 The mistakes slides are the marking scheme. Every session from Session nine onward ends with one. 00:36:36.761 --> 00:36:45.041 Read them as a checklist rather than as a warning — they were assembled from the marks that actually get lost, year after year. 00:36:45.091 --> 00:36:49.731 And bring a calculator, a pen, and enough sleep. 00:36:49.781 --> 00:36:58.731 The arithmetic in this course is deliberately small. The marks are in the reasoning — and reasoning is the first thing tiredness takes. 00:37:02.128 --> 00:37:11.078 Checkpoint four — the last one of the course. 00:37:15.978 --> 00:37:24.928 One: cwnd one, ssthresh four. Three clean round trips, then a timeout, then two clean round trips. Trace cwnd. 00:37:29.828 --> 00:37:34.938 Two: in one sentence, why does AIMD converge on equal shares? 00:37:34.988 --> 00:37:43.938 Three: name the five layers, and one thing each does to the message "hi". 00:37:46.688 --> 00:37:55.638 One: one, two, four — slow start, and four reaches ssthresh — then five, in avoidance. Timeout at five: ssthresh becomes two, cwnd becomes one. Then slow start: two, and at two it reaches ssthresh, so the next is three. The sequence is one, two, four, five, then one, then two, three. 00:38:00.648 --> 00:38:09.598 Two: because additive increase adds the same amount to every flow while multiplicative decrease removes a proportion — so each shared loss takes more from whoever has more, and the gap closes a little every time. 00:38:17.158 --> 00:38:26.108 Three: application formats the message and turns a name into an address. Transport builds a socket pair and paces the bytes with sequence numbers, acknowledgments and a congestion window. Network does IP addressing and longest-prefix forwarding across fifteen to twenty-five routers. Data link does frames, MAC addresses and ARP on every LAN. Physical turns bits into signals, under Shannon's ceiling. 00:38:38.908 --> 00:38:43.478 The last mistakes slide of the course. Five rows. 00:38:43.528 --> 00:38:50.918 "TCP numbers segments, so ACK three means segment three." The cheapest trap in the topic. 00:38:50.968 --> 00:38:59.088 TCP numbers BYTES. A thousand-byte segment starting at byte 4001 is acknowledged by 5001 — the next byte expected. 00:38:59.138 --> 00:39:07.018 rwnd and cwnd used interchangeably. They are both windows, and that is where the resemblance ends. 00:39:07.068 --> 00:39:14.988 rwnd is ADVERTISED by the receiver; cwnd is GUESSED by the sender. And the sending window is the minimum of the two. 00:39:15.038 --> 00:39:22.928 "Slow start is slow — it grows by one per round trip." The name invites it. 00:39:22.978 --> 00:39:31.928 Slow start DOUBLES per round trip. Congestion avoidance is the plus-one phase. The names lie; the exam does not. 00:39:33.238 --> 00:39:35.918 The same reaction to both loss signals. 00:39:35.968 --> 00:39:44.918 Three duplicate acknowledgments: halve and continue. Timeout: cwnd to one, and slow start again. Both set ssthresh to cwnd over two. 00:39:47.048 --> 00:39:52.638 And "the network tells TCP its fair share." It would be so much simpler if it did. 00:39:52.688 --> 00:40:01.638 Nobody tells anybody anything. AIMD converges to fairness by arithmetic, because halving takes more from whoever has more. 00:40:03.906 --> 00:40:09.326 Three tasks for the week, and the second one matters more than it looks. 00:40:09.376 --> 00:40:17.686 Trace cwnd until it is boring. Three fresh event sequences, written out with the rule named beside every number. 00:40:17.736 --> 00:40:22.976 Boring is the target — boring is what survives an exam room. 00:40:23.026 --> 00:40:28.916 One page, handwritten, from memory: the five layers, one sentence each. 00:40:28.966 --> 00:40:37.466 Do not copy it from anywhere. The value is entirely in the recall, and that page is your final-exam skeleton. 00:40:37.516 --> 00:40:43.856 And work the mistakes slides as a checklist. From Session nine onward, every session has one. 00:40:43.906 --> 00:40:52.856 They are the marking scheme in disguise, and reading them is the highest-yield hour of revision available to you. 00:40:53.430 --> 00:40:56.220 Four skills from this session. 00:40:56.270 --> 00:41:05.170 Read an ACK stream and say what the sender does: duplicate counts, the fast-retransmit trigger, and the jump when the hole fills. 00:41:05.220 --> 00:41:09.070 Bytes, not segments, at every step. 00:41:09.120 --> 00:41:14.150 Trace cwnd through any event sequence. Four rules, one variable. 00:41:14.200 --> 00:41:20.900 Update ssthresh first, then the window — and name the rule beside every number. 00:41:20.950 --> 00:41:25.890 Separate rwnd from cwnd, and both loss signals from each other. 00:41:25.940 --> 00:41:34.890 One window is told to you and one is inferred; one signal is detailed and mild, the other is silent and severe. 00:41:35.550 --> 00:41:39.760 And explain why deliberate loss is rational, and why it is fair. 00:41:39.810 --> 00:41:48.760 Loss is the only word the network speaks, and halving takes more from whoever has more. Two sentences, and they are worth more than any definition. 00:41:52.410 --> 00:41:55.840 Three phrasings, one last time. 00:41:55.890 --> 00:42:02.690 "What ACK comes back?" wants a byte number, not a segment number — and it wants the NEXT byte expected. 00:42:02.740 --> 00:42:11.440 Write the byte arithmetic in the margin: first byte, plus a thousand, plus one. Then the answer cannot go wrong. 00:42:11.490 --> 00:42:19.940 "Trace cwnd" wants the ssthresh column too. Both loss signals change it, and a trace that shows only cwnd has hidden the working. 00:42:19.990 --> 00:42:25.030 Method marks are real, and the ssthresh column is where they live. 00:42:25.080 --> 00:42:30.040 And "why does TCP cause loss?" is not "what is congestion control?" 00:42:30.090 --> 00:42:39.040 It wants the argument: the network reports nothing, so the ceiling can only be found by touching it — and the halving rule turns that into fairness with no referee. 00:42:43.367 --> 00:42:47.827 Three wordings, one session — and then we finish. 00:42:47.877 --> 00:42:51.767 "What ACKs come back?" is byte arithmetic and a trigger. 00:42:51.817 --> 00:42:59.147 ACK equals the next byte expected; three duplicates fire fast retransmit; and when the hole fills, one jump. 00:42:59.197 --> 00:43:04.207 "Trace cwnd for these events" is four rules and one variable. 00:43:04.257 --> 00:43:13.207 Double below ssthresh, plus one above it, three duplicate ACKs halve, timeout goes to one — and ssthresh is cwnd over two either way. 00:43:16.177 --> 00:43:21.247 And "why cause loss on purpose?" wants the argument, not the definition. 00:43:21.297 --> 00:43:30.247 Loss is the only word the network speaks, and halving takes more from whoever has more. That third question is the one this whole course has been walking toward since Week four chose the datagram. 00:43:36.567 --> 00:43:41.507 That is Session twenty-three, and that is CSE 316. 00:43:41.557 --> 00:43:50.507 TCP: bytes, not segments. Cumulative acknowledgments and buffers, because real channels vary and the real protocol refuses to choose. The sending window is the minimum of rwnd and cwnd. Four rules, one variable. 00:43:56.747 --> 00:44:05.127 Loss is the only word the network speaks — and AIMD turns that one word into fairness, with no referee anywhere in it. 00:44:05.177 --> 00:44:12.967 Twelve weeks ago I asked you how many machines touch a one-metre message, and you guessed. You could not name one thing any of them did. 00:44:13.017 --> 00:44:21.967 Now you can name all of it. The router doing longest-prefix match. The switch swapping a label. The card answering an ARP. The transport layer pacing bytes against a window it inferred from silence. And the physics underneath, with Shannon setting the ceiling. 00:44:30.417 --> 00:44:37.637 You came in able to send a message. You leave knowing everything that promised to deliver it. 00:44:37.687 --> 00:44:43.527 For the exam, bring a calculator, a pen, and the boring, reliable rituals. 00:44:43.577 --> 00:44:49.473 It was a privilege teaching you. Go be excellent.