WEBVTT 00:00:00.000 --> 00:00:03.700 Welcome back to CSE 316 — Data Communication and Networking. 00:00:03.750 --> 00:00:12.700 This is the detailed video version of Session twenty-two, and I want to say plainly before anything else: this is the final week of the course. Today the machinery. Next session, the finale. 00:00:17.310 --> 00:00:26.260 Last session gave you three tools — sequence numbers, acknowledgments and a timer. Today they assemble into real protocols, and then the protocols get priced against each other. 00:00:29.800 --> 00:00:38.750 Two movements. First, Stop-and-Wait: the simplest thing you can build from those three tools, and the discovery that it wastes ninety-five percent of a line somebody is paying for. Then the formula that turns that number into arithmetic. 00:00:44.530 --> 00:00:53.480 Second, the fork. Seven frames in flight, frame three dies, and there are exactly two things you can do about frames four, five and six. 00:00:54.230 --> 00:01:03.180 One of those two answers throws perfectly good data in the bin. Deliberately — and it is the right choice whenever the receiver's simplicity is worth more than the bandwidth it costs, which section four prices with numbers. 00:01:10.700 --> 00:01:14.940 The question this session answers, stated plainly. 00:01:14.990 --> 00:01:22.430 Seven frames in flight. Frame three arrives corrupted — noise, Session five, an old enemy. 00:01:22.480 --> 00:01:31.430 Frames four, five and six arrive perfect. And one of today's two protocols looks at those three perfect frames and throws them in the bin. Deliberately. By design. 00:01:33.350 --> 00:01:40.780 That protocol is Go-Back-N, and the discard is what buys it a receiver that is one integer wide. 00:01:40.830 --> 00:01:49.780 Binning perfect data is the right choice when the receiver's simplicity is worth more than the bandwidth it costs — a clean link with cheap hardware, where the discard clause almost never fires. 00:01:52.750 --> 00:02:01.700 On a lossy link it is the wrong choice, and Selective-Repeat's buffers repay their cost every time. Section four prices both. 00:02:02.400 --> 00:02:10.220 And the flag: this is the final week. Today the machinery — sliding windows, and the arithmetic that justifies them. 00:02:10.270 --> 00:02:19.220 Next session the finale: TCP, and the proper answer to the very first question of Week one. 00:02:20.025 --> 00:02:23.225 Section one. Stop-and-Wait, and its bill. 00:02:23.275 --> 00:02:32.225 Last session gave you three tools. Assemble them into the simplest possible protocol — and then price what it costs to run. 00:02:33.918 --> 00:02:42.228 Before Stop-and-Wait, the protocol Stop-and-Wait is fixing. Four cards, and the fourth names its descendant. 00:02:42.278 --> 00:02:51.228 Forouzan's first protocol is a simple connectionless protocol with neither flow control nor error control. Look at Figure twenty-three point seventeen: the packet drawn there carries no sequence number and no checksum. Nothing in it is numbered, so nothing can be missed; nothing is checked, so nothing can be found wrong. 00:02:59.678 --> 00:03:08.628 It rests on a single assumption, stated plainly in the book: the receiver can immediately handle any packet it receives, and can never be overwhelmed with incoming packets. Grant that assumption and there is nothing left for a protocol to do — the two transport layers are simply providing transmission services for their application layers. 00:03:23.768 --> 00:03:32.718 So each finite state machine has exactly one state, the ready state. The sending machine stays in ready until a request comes from the process in the application layer; then it encapsulates the message in a packet and sends it. The receiving machine stays in ready until a packet arrives; then it decapsulates the message and delivers it to the process. Figure twenty-three point eighteen. 00:03:48.708 --> 00:03:57.658 And the sender never thinks about the receiver. Example twenty-three point three: packets go out one after another and nothing comes back — no acknowledgment, no window, no timer. You have met this shape already under another name: UDP is a slight modification of this protocol. 00:04:06.868 --> 00:04:15.818 Withdraw the assumption and the receiver can drown, which needs flow control. Admit that packets get corrupted or lost, and you need error control. Stop-and-Wait, next, uses both. 00:04:25.744 --> 00:04:33.864 Four rows. The first is the assembly; the middle two are the whole protocol, told as two stories. 00:04:33.914 --> 00:04:40.094 Automatic Repeat reQuest — ARQ. Last session's three tools, made into a machine. 00:04:40.144 --> 00:04:47.894 Stop-and-Wait is the simplest version: send one packet, keep a copy, arm the timer, and wait. 00:04:47.944 --> 00:04:53.794 Story one: the frame dies. The timer rings, and the copy the sender kept goes again. 00:04:53.844 --> 00:04:59.784 Nothing had to be reported by anybody. The silence was enough. 00:04:59.834 --> 00:05:05.934 Story two: the acknowledgment dies. The timer rings, and the copy goes again anyway. 00:05:05.984 --> 00:05:14.934 And the receiver, seeing sequence number zero for the second time, bins the duplicate and politely re-acknowledges. Both failures have the same cure, which is what makes the protocol so small. 00:05:20.244 --> 00:05:29.194 So loss, in either direction, becomes mere lateness. And sequence numbers zero and one suffice — m equals one — because there is only ever one packet outstanding to be confused about. 00:05:31.614 --> 00:05:40.564 Reliable, correct and complete. And it uses five percent of the line, which the next slide computes. 00:05:41.611 --> 00:05:48.951 Let us price it. And do the arithmetic with me — it is two multiplications and a division. 00:05:49.001 --> 00:05:57.951 One megabit per second, twenty milliseconds round trip. Bandwidth times delay — Week three's bandwidth-delay product — is twenty thousand bits. 00:05:58.541 --> 00:06:04.831 That is the volume of the pipe. What COULD be airborne between the two ends at any instant. 00:06:04.881 --> 00:06:11.651 And we keep exactly one thousand-bit packet in it. One thousand over twenty thousand: five percent. 00:06:11.701 --> 00:06:20.501 Ninety-five percent of a line somebody is paying for, carrying silence — and the protocol is behaving exactly as designed. 00:06:20.551 --> 00:06:27.021 Notice what is not to blame. Not the cable. Not the distance. Not physics, and not the encoding. 00:06:27.071 --> 00:06:36.021 The pipe was never the problem. The PROTOCOL was — and that is a much better problem to have, because it can be fixed without buying anything. 00:06:38.144 --> 00:06:43.794 Forouzan's Example twenty-three point six, and the fix is simple. 00:06:43.844 --> 00:06:49.034 Allow fifteen packets in flight instead of one, on exactly the same link. 00:06:49.084 --> 00:06:58.034 Fifteen thousand over twenty thousand: seventy-five percent. Fifteen times the useful work, and nothing physical changed at all. 00:06:58.464 --> 00:07:04.624 The mechanism is a window: the sender may have up to W packets unacknowledged at any moment. 00:07:04.674 --> 00:07:10.584 Size W to the pipe, and the pipe stays full. That is the whole fix. 00:07:10.634 --> 00:07:15.844 The idea is pipelining — start the next task before the last one finishes. 00:07:15.894 --> 00:07:23.174 The sender stops waiting, except when the window is full, which on a well-sized window is rarely. 00:07:23.224 --> 00:07:29.044 No faster cable, no shorter distance, no better encoding, and no new physics. 00:07:29.094 --> 00:07:34.804 Only a changed rule about how many packets may be in the air at once. 00:07:34.854 --> 00:07:40.264 But we have just bought a new problem. With one packet out, loss was simple. 00:07:40.314 --> 00:07:47.634 With seven out and number three dead on the road — what exactly do you do with four, five and six, which arrived in perfect health? 00:07:47.684 --> 00:07:56.634 That question has exactly two answers — bin them, or buffer them — and sections three and four take one each. First the arithmetic, because the exam wants it in closed form. 00:08:02.411 --> 00:08:08.281 Draw this one on paper as I talk. It is the picture the whole formula comes out of. 00:08:08.331 --> 00:08:15.371 One Stop-and-Wait cycle, as a bar. A box of width T-f, where the sender is pushing bits onto the wire. 00:08:15.421 --> 00:08:21.051 Then a gap of two T-p, where it is doing nothing at all but waiting. 00:08:21.101 --> 00:08:30.051 So the whole cycle costs T-f plus two T-p. Transmission time once, propagation time twice — out with the frame, and back with the acknowledgment. 00:08:32.401 --> 00:08:37.621 And the useful part is the T-f alone. So utilisation is T-f over T-f plus two T-p. 00:08:37.671 --> 00:08:45.771 Everything else in the cycle is the road — and the road does not care how fast your line is. 00:08:45.821 --> 00:08:54.771 Now divide top and bottom by T-f, and the picture turns into something you can carry into an exam: a ratio, and then a formula built on it. 00:08:55.171 --> 00:09:04.121 Reproduce this bar once on paper. Every efficiency question you will ever be set is this one picture with different proportions. 00:09:06.302 --> 00:09:13.452 And here is the law. Two lines, and they are worth more marks than anything else in this session. 00:09:13.502 --> 00:09:20.632 a is the ratio of propagation time to transmission time — how many frames long the road is compared with the pushing. 00:09:20.682 --> 00:09:27.512 Compute it FIRST, always. Every other number in the answer depends on it. 00:09:27.562 --> 00:09:31.102 Stop-and-Wait: utilisation is one over one plus two a. 00:09:31.152 --> 00:09:40.102 With a of ten, that is one twenty-first — about four point eight percent. The five percent you already met, now derived rather than measured. 00:09:41.262 --> 00:09:49.832 With a window of W frames per cycle: W over one plus two a. Capped at one hundred percent, because a full pipe cannot be fuller. 00:09:49.882 --> 00:09:54.482 A window of fifteen gives fifteen twenty-firsts — about seventy-one percent. 00:09:54.532 --> 00:10:03.052 And the pipe fills at W equals one plus two a. Twenty-one frames airborne, and the line never sleeps. 00:10:03.102 --> 00:10:07.802 Beyond that number you are not sending faster; you are only queueing. 00:10:07.852 --> 00:10:16.802 Write both lines at the top of the page before you touch the numbers, and the question becomes arithmetic instead of reasoning. 00:10:20.362 --> 00:10:27.592 Forty-two seconds on the whole of the first movement — and it ends on the question the second movement answers. 00:10:27.642 --> 00:10:36.592 The three tools as rows, and then the green row: the frame dies or the ACK dies, and the cure is the same either way. 00:10:37.112 --> 00:10:46.062 The pipe bar, five percent full and red. Then the two lines of arithmetic: twenty thousand bits of volume, one thousand bits in it. 00:10:47.312 --> 00:10:56.262 Here is the picture you just drew. A thin green Tf, and then two grey Tp blocks — and the green sliver is the only part that is work. 00:10:57.422 --> 00:11:06.372 The two formulas, and then the four-step check underneath. Follow the numbers down: a is ten, Stop-and-Wait gets 4.8%, fifteen gets 71%, and the pipe fills at 21. 00:11:08.582 --> 00:11:17.532 The pipe filling as the bar grows — and the fourth row, W of thirty, still at a hundred percent. You cannot fill a pipe twice. 00:11:21.142 --> 00:11:30.092 The window drawn around the first five frames, and the line that closes the movement: Stop-and-Wait is just this picture with a window of one. 00:11:31.202 --> 00:11:40.152 And there is the fork. Seven frames, number three in red, and the two answers underneath. That is the rest of this session. 00:11:42.393 --> 00:11:51.343 Five steps. Pause and do each one before I say it — this is the exam question, in miniature. 00:11:54.413 --> 00:12:00.923 Step one. a equals T-p over T-f: ten over one. a is ten — the road is ten frames long. 00:12:00.973 --> 00:12:04.683 And every line below is now determined. 00:12:04.733 --> 00:12:11.073 Step two. Stop-and-Wait, window of one: U equals one over one plus twenty. 00:12:11.123 --> 00:12:20.073 One twenty-first, about four point eight percent — which is Example twenty-three point five's five percent, arrived at from the other direction entirely. 00:12:21.683 --> 00:12:27.823 Step three. A window of fifteen: fifteen over twenty-one, about seventy-one percent. 00:12:27.873 --> 00:12:36.823 And Example twenty-three point six said seventy-five. Near enough — the small gap is the acknowledgment's own transmission time, which the simple formula ignores. 00:12:39.753 --> 00:12:43.463 Step four. The pipe fills at one plus two a: twenty-one frames. 00:12:43.513 --> 00:12:52.463 That is the smallest window that keeps the line permanently busy. A window of thirty would still be a hundred percent, because you cannot fill a pipe twice. 00:12:52.763 --> 00:13:01.713 And step five, the sanity check: U can never exceed one, whatever W you are given. Cap it at a hundred percent. 00:13:03.053 --> 00:13:11.708 An answer above one hundred percent means the cap was forgotten — not that the wire is magic. 00:13:11.758 --> 00:13:17.838 Checkpoint one. These are small enough to do without a calculator. 00:13:17.888 --> 00:13:25.858 One: T-f is two milliseconds, T-p is eight. Find a, then the utilisation of Stop-and-Wait. 00:13:25.908 --> 00:13:33.348 Two: same link. What window exactly fills the pipe, and what does a window of six achieve? 00:13:33.398 --> 00:13:42.348 Three: why is the utilisation of a one-megabit link with a twenty-millisecond round trip only five percent under Stop-and-Wait? 00:13:42.898 --> 00:13:51.848 One: a equals eight over two, which is four. Stop-and-Wait: one over one plus eight, which is one ninth — about eleven percent. Compute a first; everything else depends on it. 00:13:54.738 --> 00:14:03.688 Two: the pipe fills at one plus two a, which is nine frames. A window of six gives six ninths — about sixty-seven percent. Better than eleven, and still not the whole line. 00:14:07.268 --> 00:14:16.218 Three: because bandwidth times delay is twenty thousand bits — the volume of the pipe — and Stop-and-Wait keeps exactly one thousand-bit packet in it. The cable is not the problem; the protocol is. 00:14:22.885 --> 00:14:26.565 Section two. What the formula is, and is not. 00:14:26.615 --> 00:14:35.565 The law tells you what a sliding-window protocol achieves when nothing goes wrong. Adversity is what separates the two protocols — and adversity is next. 00:14:39.518 --> 00:14:45.798 A new set of numbers, the same law. Three minutes on paper if you want them. 00:14:45.848 --> 00:14:53.318 First, a equals four. The road is four frames long. Write it down before anything else, and circle it. 00:14:53.368 --> 00:14:59.208 Stop-and-Wait: one over one plus eight, which is one ninth — about eleven percent. 00:14:59.258 --> 00:15:07.298 Better than the five percent of the last example, because this road is shorter. And still eight ninths of the line idle. 00:15:07.348 --> 00:15:11.898 A window of five: five ninths, about fifty-six percent. 00:15:11.948 --> 00:15:20.898 Five times the packets in flight, five times the utilisation — the relationship is exactly linear, right up until the cap. 00:15:21.288 --> 00:15:26.468 And the pipe fills at nine. Nine frames airborne, and the line never sleeps. 00:15:26.518 --> 00:15:35.468 Whichever sliding protocol you run, THIS is the ceiling — and the only step with any judgement in it was the first one. 00:15:36.818 --> 00:15:43.048 And now the honest reading of that formula, which matters more than the arithmetic. 00:15:43.098 --> 00:15:50.968 It is a ceiling. It assumes every frame arrives, every acknowledgment comes back, and no timer ever fires. 00:15:51.018 --> 00:15:58.698 By that measure Go-Back-N and Selective-Repeat are exactly identical: same window, same ceiling. 00:15:58.748 --> 00:16:07.698 So on a clean wire the two protocols tie. Which is worth saying out loud, because it means the entire comparison you are about to do is a comparison of failure behaviour. 00:16:09.298 --> 00:16:12.378 Success looks the same in both. 00:16:12.428 --> 00:16:21.168 And a loss taxes them differently. Go-Back-N pays a whole window of retransmissions per loss; Selective-Repeat pays one frame. 00:16:21.218 --> 00:16:25.648 The gap between them widens with the loss rate, and vanishes without it. 00:16:25.698 --> 00:16:34.648 Comparing the two ARQs on the exam means saying exactly that: the ceilings are the same, and the bills are not. 00:16:36.318 --> 00:16:40.478 Before we split, one more piece of tidying up. 00:16:40.528 --> 00:16:46.168 Stop-and-Wait is Go-Back-N with a window of one. Not an analogy — a special case. 00:16:46.218 --> 00:16:53.408 Set W to one in the formula and in the protocol, and one becomes the other exactly. 00:16:53.458 --> 00:17:02.408 Go-Back-N is the middle price: a window on the wire, and a receiver that stays as simple as Stop-and-Wait's. One integer of state. 00:17:03.228 --> 00:17:12.178 Selective-Repeat is the expensive one: buffers at the receiver, a timer per outstanding packet, and bookkeeping at both ends — bought in exchange for a lean wire. 00:17:14.948 --> 00:17:18.208 And the channel should pick, not the designer's taste. 00:17:18.258 --> 00:17:27.208 Which is the sentence this whole session is walking towards, and it is the answer to the question from minute one. 00:17:28.739 --> 00:17:37.499 The whole efficiency argument, one state at a time — with the pipe drawn to scale so you can see the waste rather than compute it. 00:17:37.549 --> 00:17:46.429 State one: the wire, the round trip, the packet, and one frame in flight in red. Nothing has been computed yet. 00:17:46.479 --> 00:17:53.499 State two: the two lines of arithmetic, and the pipe five percent full. Watch how little of the bar is green. 00:17:53.549 --> 00:17:57.059 This is the picture that makes the number stick. 00:17:57.109 --> 00:18:04.789 State three: the same bar, three-quarters green, and the counters underneath saying same wire, times fifteen. 00:18:04.839 --> 00:18:11.079 Nothing about the link changed. Only the rule about how many packets may be in the air. 00:18:11.129 --> 00:18:17.679 State four is the cycle bar — the green Tf and the two grey Tp blocks, drawn to scale at a of ten. 00:18:17.729 --> 00:18:23.189 If your paper drawing does not look like this, redraw it. 00:18:23.239 --> 00:18:32.189 State five: a equals T-p over T-f, then U equals W over one plus two a — and the four-step check with the answers on the right. 00:18:32.579 --> 00:18:37.839 Cover the right-hand column and do the four steps yourself before you look. 00:18:37.889 --> 00:18:45.909 State six is the second set of numbers. a of four, eleven percent, fifty-six percent, and the pipe full at nine. 00:18:45.959 --> 00:18:51.279 Same shape, new numbers, which is exactly what the final will do. 00:18:51.329 --> 00:19:00.169 And state seven: both protocols reach the same ceiling, and a loss costs Go-Back-N a whole window and Selective-Repeat one frame. 00:19:00.219 --> 00:19:07.535 That last pair of cards is the bridge into the second half of this session. 00:19:07.585 --> 00:19:10.955 Now the fork, properly stated. 00:19:11.005 --> 00:19:17.465 Seven frames in flight, and number three is destroyed by noise. Session five's old enemy. 00:19:17.515 --> 00:19:25.495 Four, five and six arrive perfect — flawless, on time, and out of order through no fault of their own. 00:19:25.545 --> 00:19:32.515 The receiver is waiting for three, and holds, at this instant, three frames it did not ask for yet. 00:19:32.565 --> 00:19:38.355 So what does it do? This is a design decision, not a fact about networks. 00:19:38.405 --> 00:19:43.815 Answer one: bin them. Accept the next expected number and nothing else, ever. 00:19:43.865 --> 00:19:50.635 That is Go-Back-N, and it protects the receiver's simplicity at absolutely any cost. 00:19:50.685 --> 00:19:56.955 Answer two: buffer them. Store them, mark them, and hold them until the hole in front fills. 00:19:57.005 --> 00:20:03.515 That is Selective-Repeat, and it wastes nothing on the wire, whatever the bookkeeping costs. 00:20:03.565 --> 00:20:08.175 And there is no third answer. You either keep the arrivals or you do not. 00:20:08.225 --> 00:20:17.175 Both are defensible — which is why both are in the textbook, and why the exam asks you to choose between them and justify it. 00:20:18.719 --> 00:20:25.619 Two sentences to write down, because almost every comparison question is answered by them. 00:20:25.669 --> 00:20:31.869 Go-Back-N protects the receiver's simplicity. Its receiver is one integer: "I want three." 00:20:31.919 --> 00:20:40.639 No buffers, no reassembly, nothing to get wrong — and nothing that can be implemented incorrectly on cheap silicon. 00:20:40.689 --> 00:20:46.099 Selective-Repeat protects the wire. It never asks for a frame that already arrived. 00:20:46.149 --> 00:20:54.899 Every retransmission it makes is a frame that genuinely died — and it pays for that precision in memory and timers. 00:20:54.949 --> 00:21:00.499 Neither is trying to be clever. Each is protecting the resource its designer thought scarce. 00:21:00.549 --> 00:21:09.499 And which resource actually IS scarce depends entirely on the channel and the hardware — which is what slide thirty-three prices, with numbers. 00:21:12.553 --> 00:21:17.343 Checkpoint two, and the first one is a trap. 00:21:17.393 --> 00:21:23.813 One: on a link with no losses at all, which of the two ARQs is more efficient? 00:21:23.863 --> 00:21:32.093 Two: frame three is lost; four, five and six arrive intact. What does each receiver do with them? 00:21:32.143 --> 00:21:38.673 Three: why is Stop-and-Wait a special case of Go-Back-N rather than a different idea? 00:21:38.723 --> 00:21:47.673 One: neither. With no losses the ceiling W over one plus two a is reached by both, and their behaviour is identical. Adversity is the only thing that separates them. 00:21:50.313 --> 00:21:59.263 Two: Go-Back-N discards all three, because its receiver window is one — it accepts only the next expected number. Selective-Repeat buffers all three and holds them, undelivered, until frame three arrives. 00:22:05.113 --> 00:22:14.063 Three: because setting W to one turns one into the other exactly. One packet outstanding, one timer, and a receiver that accepts only the next expected number. Same protocol, smallest window. 00:22:22.053 --> 00:22:24.513 Section three. Go-Back-N. 00:22:24.563 --> 00:22:33.513 Three design choices and one philosophy — and a discard clause that looks indefensible until you price what it buys. 00:22:35.084 --> 00:22:40.314 Three choices. Every property of the protocol follows from them. 00:22:40.364 --> 00:22:47.624 Cumulative acknowledgments. An ackNo of seven means "everything through six is safe, and I expect seven." 00:22:47.674 --> 00:22:56.624 One acknowledgment retires a whole batch — and if an acknowledgment dies, the next one heals it. That is extra value out of the same mechanism. 00:22:57.634 --> 00:23:05.054 One timer, on the oldest outstanding packet. When it expires, the sender resends EVERYTHING outstanding. 00:23:05.104 --> 00:23:08.804 That is the name of the protocol: go back N. 00:23:08.854 --> 00:23:14.634 And the receiver window is one. It accepts the next expected number and nothing else. 00:23:14.684 --> 00:23:22.224 A frame that arrives early and flawless is binned, and the old acknowledgment is simply repeated. 00:23:22.274 --> 00:23:26.684 Now look at what that receiver IS: one integer. "I want three." 00:23:26.734 --> 00:23:35.684 No buffers, no reassembly, no out-of-order logic, and nothing that can be implemented wrongly. The network pays for that austerity in repeats — and whether that is a good deal depends on how often the wire loses a frame. 00:23:44.095 --> 00:23:49.195 Forouzan's Example twenty-three point eight, step for step. 00:23:49.245 --> 00:23:54.245 Packet zero arrives and is acknowledged. The receiver now expects one. 00:23:54.295 --> 00:24:00.415 Normal service, and so far nothing distinguishes this protocol from any other. 00:24:00.465 --> 00:24:05.235 Packet one is lost on the wire. Destroyed, and nobody says so. 00:24:05.285 --> 00:24:13.005 There is no "I got a broken one" packet in this protocol, or in any of them. Silence is the message. 00:24:13.055 --> 00:24:19.715 Packets two and three arrive in perfect health — on time, intact, entirely usable. 00:24:19.765 --> 00:24:28.715 And are discarded. The receiver wanted one. Its window is one wide. It repeats the old acknowledgment and bins both. 00:24:28.985 --> 00:24:36.285 The timer on packet one expires — it was the oldest outstanding, and it never got its acknowledgment. 00:24:36.335 --> 00:24:45.285 And one, two and three all cross the wire again. Three transmissions to recover one loss, two of them carrying data that had already arrived intact. 00:24:46.805 --> 00:24:52.795 That discard clause is not an oversight. It is the price of a receiver with no memory at all. 00:24:52.845 --> 00:25:01.795 Whether it is a good deal depends on how often the wire loses a frame, which slide thirty-three prices. 00:25:02.119 --> 00:25:06.579 Go-Back-N's case, stated before it is judged. 00:25:06.629 --> 00:25:15.579 No buffers means no buffer management. No allocation, no overflow, no bookkeeping about which slots are occupied, and no code path that can be got wrong. 00:25:17.239 --> 00:25:21.599 On a cheap embedded controller that is not a small saving. 00:25:21.649 --> 00:25:30.599 No out-of-order logic means no reassembly. The receiver hands the application exactly what it accepts, in the order it accepts it, and it accepts exactly one thing at a time. 00:25:32.979 --> 00:25:39.789 Correctness becomes almost trivial to argue — and on real hardware, that matters. 00:25:39.839 --> 00:25:46.819 So the bill is paid entirely on the wire. And a wire that rarely loses anything sends that bill rarely. 00:25:46.869 --> 00:25:55.535 That is the whole argument for Go-Back-N, and it is a much better argument than it first sounds. 00:25:56.635 --> 00:26:05.585 Forty-two seconds covering both protocols end to end, and finishing on the answer to the hook. Watch it once; we do Selective-Repeat properly afterwards. 00:26:07.955 --> 00:26:16.675 The three design choices as rows — cumulative ACKs in blue, one timer in orange, and the receiver window of one in red. 00:26:16.725 --> 00:26:21.845 And the green row underneath: the receiver is one integer. 00:26:21.895 --> 00:26:30.845 The frame strip. Watch it change: first packet one goes red, then two and three go dashed-red and struck through, then all three turn brown as resends. 00:26:31.295 --> 00:26:40.245 Now the other lane. Frame three red, and four, five and six in amber — buffered, not binned. Same arrivals, opposite decision. 00:26:42.755 --> 00:26:51.705 The slide that costs marks. Four, five and six are held while the left edge is still the hole — and then three arrives and all four go green together. 00:26:55.575 --> 00:27:03.595 ackNo three, and the two interpretation cards. A receipt for a batch on the left; a receipt for one parcel on the right. 00:27:03.645 --> 00:27:07.245 Identical bits, opposite meanings. 00:27:07.295 --> 00:27:16.245 The two window limits, and the m-value table underneath. Note m of one gives a window of one for both — which is Stop-and-Wait. 00:27:16.605 --> 00:27:25.555 And the answer, which we will deliver properly in a few slides: protocols are bets about the channel. 00:27:25.834 --> 00:27:29.704 Checkpoint three, all on Go-Back-N. 00:27:29.754 --> 00:27:37.734 One: what does ackNo equals five mean in Go-Back-N? Be precise about what it does and does not confirm. 00:27:37.784 --> 00:27:44.264 Two: how many timers does a Go-Back-N sender run, and on which packet? 00:27:44.314 --> 00:27:51.324 Three: a Go-Back-N acknowledgment is lost. Is anything retransmitted because of it? 00:27:51.374 --> 00:28:00.324 One: everything through packet four arrived safely, and the receiver now expects packet five. It confirms a batch, not one packet — and it says nothing at all about anything numbered five or above. 00:28:04.874 --> 00:28:13.824 Two: one timer, on the oldest outstanding packet. When it expires, the sender resends every outstanding packet, not just that one. 00:28:14.594 --> 00:28:23.544 Three: not necessarily. Acknowledgments are cumulative, so the next one to arrive covers everything the lost one covered. Only if the timer expires before any later acknowledgment arrives does anything go again. 00:28:31.267 --> 00:28:34.777 Section four. Selective-Repeat, and the bet. 00:28:34.827 --> 00:28:43.777 The other answer to the fork: keep every arrival, resend only what actually died — and pay for it in memory, timers and bookkeeping. 00:28:46.767 --> 00:28:52.807 Four rows, and every one of them is the mirror image of a Go-Back-N choice. 00:28:52.857 --> 00:29:01.807 The receiver keeps a window of buffers. Four, five and six arrive while three is missing? Stored, marked, safe — and not delivered. 00:29:02.317 --> 00:29:09.707 Stored. That distinction matters, and it is examined; the next slide is about nothing else. 00:29:09.757 --> 00:29:15.247 Acknowledgments are individual. "Got four" means four, and only four. 00:29:15.297 --> 00:29:23.367 About anything else it says nothing at all — which is the exact opposite of Go-Back-N's cumulative promise. 00:29:23.417 --> 00:29:27.897 On timeout the sender resends exactly one packet: the dead one. 00:29:27.947 --> 00:29:36.097 Which requires a timer per outstanding packet, because the sender must know which individual frame is overdue. 00:29:36.147 --> 00:29:44.147 And when three finally arrives, three, four, five and six are delivered to the application in one ordered burst. 00:29:44.197 --> 00:29:53.147 One transmission to recover one loss. The wire is as lean as it can possibly be — and all of that leanness was bought with memory at both ends. 00:29:56.823 --> 00:30:04.153 Answer that before I do. Packet four is sitting in the buffer, intact. Can the application read it? 00:30:04.203 --> 00:30:10.363 No. And the reason is the whole point: the left edge of the receiver window is still the hole. 00:30:10.413 --> 00:30:16.653 Arrival and delivery are different events, and the question turns on the difference. 00:30:16.703 --> 00:30:21.883 Forouzan's condition one: a set of CONSECUTIVE packets. No gaps. 00:30:21.933 --> 00:30:28.323 The application is owed a stream, and a stream with a hole in it is not a stream. 00:30:28.373 --> 00:30:34.003 Condition two: starting at the LEFT EDGE of the window. Both conditions, every time. 00:30:34.053 --> 00:30:40.633 Consecutive somewhere in the middle is not enough; the run must start where the window starts. 00:30:40.683 --> 00:30:47.733 So the buffer holds until the hole fills — however long that takes, and however many arrivals pile up behind it. 00:30:47.783 --> 00:30:56.733 Which is why Selective-Repeat needs memory, and why the size of that memory is a real engineering cost rather than an accounting one. 00:30:56.943 --> 00:31:03.663 And then everything moves at once: three, four, five and six delivered together, in order. 00:31:03.713 --> 00:31:12.663 The window slides past all four, and its left edge lands on the next thing that is genuinely missing. 00:31:12.957 --> 00:31:16.987 Forouzan's Example twenty-three point nine. 00:31:17.037 --> 00:31:20.617 Same wire, same bits: ackNo equals three. 00:31:20.667 --> 00:31:29.567 Nothing about the packet itself tells you which protocol produced it. The meaning lives entirely in the agreement between the two ends. 00:31:29.617 --> 00:31:35.627 Under Go-Back-N it is a receipt for a BATCH: zero, one and two are all safe, and three is expected next. 00:31:35.677 --> 00:31:41.237 One acknowledgment retiring three packets at once, with a lost one healed by the next. 00:31:41.287 --> 00:31:47.237 Under Selective-Repeat it is a receipt for ONE parcel: packet three arrived. 00:31:47.287 --> 00:31:56.237 And about zero, one and two it says absolutely nothing. Any of them may still be missing, and the sender must not assume otherwise. 00:31:58.677 --> 00:32:07.627 Identical message, opposite meanings. If you carry one protocol's acknowledgment semantics into the other's question, the whole sub-answer collapses. 00:32:11.090 --> 00:32:16.410 Five rows, and read it as a purchase decision rather than a scorecard. 00:32:16.460 --> 00:32:24.780 Acknowledgments. Go-Back-N: cumulative — one ACK retires a batch, and a lost one is healed by the next. 00:32:24.830 --> 00:32:32.820 Selective-Repeat: individual — one ACK per packet, and a lost one costs a retransmission. 00:32:32.870 --> 00:32:38.020 Timers. Go-Back-N: one, on the oldest outstanding packet. 00:32:38.070 --> 00:32:46.980 Selective-Repeat: one per outstanding packet — which is where a large part of the bookkeeping cost lives. 00:32:47.030 --> 00:32:52.770 The receiver. Go-Back-N: one integer. No buffers, nothing to get wrong. 00:32:52.820 --> 00:33:01.470 Selective-Repeat: a window of buffers, plus the logic to know which slots are filled and which are holes. 00:33:01.520 --> 00:33:05.430 On a loss. Go-Back-N: resend the whole outstanding window. 00:33:05.480 --> 00:33:11.560 Selective-Repeat: resend one frame — the dead one, and nothing else. 00:33:11.610 --> 00:33:15.870 And the ceiling. Both reach W over one plus two a when nothing goes wrong. 00:33:15.920 --> 00:33:24.870 The bills differ, not the ceiling. A loss taxes Go-Back-N a window and Selective-Repeat a frame — so on a clean wire they tie, and on a dirty one they do not. 00:33:26.480 --> 00:33:34.940 Nobody wins this table. One protocol pays in bandwidth, the other in state. 00:33:35.960 --> 00:33:44.910 Both protocols in two lanes, running the same story — and the counters underneath tell you what the difference actually costs. 00:33:45.660 --> 00:33:50.860 State one: eight frames, a window of four, and frame three marked as the casualty. 00:33:50.910 --> 00:33:59.860 Pause and predict both pairs of counters — total transmissions and perfect frames binned — for each lane, before you go on. 00:34:03.250 --> 00:34:10.020 State two: both lanes send zero to three. The first three arrive, and frame three goes red. 00:34:10.070 --> 00:34:16.840 Note that so far the two lanes are identical. Adversity has not separated them yet. 00:34:16.890 --> 00:34:23.350 State three is the fork, made visible. Same arrivals in both lanes, and opposite decisions: 00:34:23.400 --> 00:34:32.350 Go-Back-N's four, five and six are dashed red and struck through — BINNED. Selective-Repeat's are amber — buffered. 00:34:33.170 --> 00:34:40.750 State four: the timeout. Go-Back-N resends three, four, five and six. Selective-Repeat resends three. 00:34:40.800 --> 00:34:45.430 Four transmissions to recover one loss, against one. 00:34:45.480 --> 00:34:53.520 State five: both lanes deliver the same eight frames in the same order. Nothing was lost to the application either way. 00:34:53.570 --> 00:34:57.400 Only the cost differed, which is the whole point. 00:34:57.450 --> 00:35:04.050 State six is the bill. Twelve sent and three binned, against nine sent and nothing wasted. 00:35:04.100 --> 00:35:13.050 And read the second half of the paragraph too — Selective-Repeat paid in memory, and that column of the bill does not appear in the counters. 00:35:14.670 --> 00:35:19.560 And state seven: Go-Back-N resends the past, Selective-Repeat resends the loss. 00:35:19.610 --> 00:35:28.560 Open it yourself and design the counter-scenario — a window of four, and TWO frames lost. Predict both counters before you run it. 00:35:31.157 --> 00:35:40.107 Every diagram in this session has had a sender on the left and a receiver on the right. Five rows to fix that. 00:35:43.187 --> 00:35:52.137 The four protocols of this chapter — Simple, Stop-and-Wait, Go-Back-N and Selective-Repeat — are all unidirectional. Data packets flow in only one direction and acknowledgments travel in the other. That is simplex, and it is a teaching convenience rather than a description of anything real. 00:36:03.977 --> 00:36:12.927 In real life, data packets normally flow in both directions: from client to server and from server to client. Which means acknowledgments also need to flow in both directions. Each machine is a sender and a receiver at the same time, and each one owes the other feedback about what has arrived. 00:36:28.537 --> 00:36:37.487 Piggybacking is the technique used to improve the efficiency of the bidirectional protocols. When a packet is carrying data from A to B, it can also carry acknowledgment feedback about packets arrived from B. One packet, two jobs: a sequence number for its own data, and an acknowledgment number for the traffic coming the other way. 00:36:47.467 --> 00:36:56.417 So the client and the server each use two independent windows, send and receive. Figure twenty-three point thirty-seven draws Go-Back-N implemented this way. The client's send window holds S-f, the first outstanding, and S-n, the next to send; its receive window holds R-n, the next expected. Four windows on one page, and the server's are the mirror image. 00:37:02.937 --> 00:37:11.887 And piggybacking is not a fifth protocol. It is a way of building the ones you already have: all of these protocols can be implemented bidirectionally using piggybacking. The window rules do not change — there are simply two sets of them at each end, one per direction. 00:37:27.816 --> 00:37:34.346 Two formulas the final wants verbatim, and one sentence of intuition behind them. 00:37:34.396 --> 00:37:40.076 Sequence numbers live in m bits: zero to two-to-the-m minus one, and then round again. 00:37:40.126 --> 00:37:49.076 Which means a number the sender uses today will be reused before long — and the windows must respect that. 00:37:49.216 --> 00:37:55.456 Go-Back-N: the window is at most two-to-the-m minus one. One less than the whole space. 00:37:55.506 --> 00:38:00.466 m of three gives seven; m of four gives fifteen. 00:38:00.516 --> 00:38:05.186 Selective-Repeat: at most two-to-the-m-minus-one. Half the space. 00:38:05.236 --> 00:38:14.106 m of three gives four; m of four gives eight. Selective-Repeat pays for its buffering cleverness with a smaller window. 00:38:14.156 --> 00:38:23.106 And here is why. With wrapping numbers, too wide a window would let a resent OLD packet land inside the receiver's window and be mistaken for a fresh one. 00:38:24.306 --> 00:38:33.256 Halving keeps old and new from ever overlapping. That is the intuition; Figure twenty-three point thirty-six is the picture; the final wants the two formulas. 00:38:38.666 --> 00:38:47.616 Rapid fire: m of three — seven and four. m of four — fifteen and eight. m of two — three and two. m of one — one and one, and a window of one is Stop-and-Wait. The circle closes exactly where this session started. 00:38:54.512 --> 00:38:58.542 So. When is binning perfect data smart? 00:38:58.592 --> 00:39:06.622 When what you get in exchange is worth more. Go-Back-N's discard clause buys a receiver with no memory — one integer of state. 00:39:06.672 --> 00:39:12.832 That is the trade, stated plainly. And it is a real trade rather than an excuse. 00:39:12.882 --> 00:39:19.262 On a clean link, that clause almost never fires. You keep the simplicity and you pay nothing at all. 00:39:19.312 --> 00:39:27.672 Cheap embedded silicon on a reliable wire is exactly this situation, and there are a great many of them in the world. 00:39:27.722 --> 00:39:35.332 On a lossy link it fires constantly — a whole window resent per loss — and Selective-Repeat's buffers repay their cost every single time. 00:39:35.382 --> 00:39:38.852 So the answer is not a preference. It is a measurement. 00:39:38.902 --> 00:39:45.192 Protocols are bets about the channel: pick the protocol after you have met the wire. 00:39:45.242 --> 00:39:53.742 And if your instinct at minute one was "never — that is wasteful", that instinct priced bandwidth correctly and forgot to price memory. 00:39:53.792 --> 00:40:02.742 TCP itself hedges. Cumulative acknowledgments like Go-Back-N, selective extensions like Selective-Repeat. Real channels vary, so the real protocol refuses to choose — and next session you watch it do so. 00:40:11.145 --> 00:40:15.695 Checkpoint four, the last one of the session. 00:40:15.745 --> 00:40:23.565 One: m equals four. Give the largest legal window for Go-Back-N and for Selective-Repeat. 00:40:23.615 --> 00:40:32.435 Two: window four, eight frames, frame three lost. How many transmissions does each protocol use? 00:40:32.485 --> 00:40:39.515 Three: name one situation where Go-Back-N is the better engineering choice, and say why. 00:40:39.565 --> 00:40:48.515 One: Go-Back-N, two-to-the-m minus one, which is fifteen. Selective-Repeat, two-to-the-m-minus-one, which is eight. Selective-Repeat gets half the space so that a resent old packet can never be mistaken for a new one after the numbers wrap. 00:40:56.295 --> 00:41:05.245 Two: Go-Back-N takes twelve transmissions and bins three perfectly good frames. Selective-Repeat takes nine and wastes nothing. The difference is four extra transmissions to recover one loss. 00:41:09.375 --> 00:41:18.325 Three: a reliable link with cheap receiving hardware — embedded silicon on a short, clean wire. The discard clause almost never fires, so the bandwidth cost is near zero, and the saving in receiver memory and complexity is real and permanent. 00:41:29.945 --> 00:41:36.255 Five mistakes, ten seconds each — and you have met every one of them in this session. 00:41:36.305 --> 00:41:42.525 Mixing up cumulative and individual acknowledgments. This is the most common error in this topic. 00:41:42.575 --> 00:41:51.525 Go-Back-N: ackNo n means "all through n minus one". Selective-Repeat: "packet n arrived, and nothing more is implied." 00:41:52.995 --> 00:41:58.345 Giving both protocols the same window limit. They look symmetrical and they are not. 00:41:58.395 --> 00:42:07.345 Go-Back-N at most two-to-the-m minus one; Selective-Repeat at most two-to-the-m-minus-one. Selective-Repeat gets HALF the space — m of three means seven and four. 00:42:11.185 --> 00:42:17.055 Saying Go-Back-N buffers out-of-order frames. It is the one thing it categorically does not do. 00:42:17.105 --> 00:42:25.065 Go-Back-N never buffers; Selective-Repeat always does. One integer against a window of slots. 00:42:25.115 --> 00:42:30.075 Computing utilisation without finding a first — or inverting the ratio. 00:42:30.125 --> 00:42:36.365 a equals T-p over T-f, always. Then U equals W over one plus two a, capped at a hundred percent. 00:42:36.415 --> 00:42:44.235 And comparing the two ARQs by quoting the formula — which makes them identical, and therefore answers nothing. 00:42:44.285 --> 00:42:53.235 The formula is the ceiling. A loss bills Go-Back-N a window and Selective-Repeat a frame. Say exactly that, and the comparison is done. 00:42:58.087 --> 00:43:01.947 Three things that carry into the last session. 00:43:01.997 --> 00:43:07.977 TCP takes all of it: sequence numbers, cumulative acknowledgments, windows, timers. 00:43:08.027 --> 00:43:16.977 Everything assembled in this session and the last one goes into the protocol carrying this sentence to your device right now. Nothing is thrown away. 00:43:18.957 --> 00:43:25.787 And then it does something no protocol today dared. It deliberately accelerates until the network drops a packet. 00:43:25.837 --> 00:43:32.297 On purpose. Forever. And that turns out to be the smartest thing the Internet does. 00:43:32.347 --> 00:43:41.297 Then we reassemble every layer of this course, and answer Session one's very first question properly — the one you were asked before you knew any of this. 00:43:41.867 --> 00:43:50.817 Read Forouzan section twenty-four point three before next session. And run the simulator until your predictions are boring — that is the point at which the material is actually yours. 00:43:56.254 --> 00:44:03.294 Four skills, and between them they are almost every mark this session is worth. 00:44:03.344 --> 00:44:12.294 Compute a, and then U, for any T-f and T-p. a equals T-p over T-f; U equals W over one plus two a, capped at a hundred percent. 00:44:13.664 --> 00:44:18.724 And know that the pipe fills at W equals one plus two a. 00:44:18.774 --> 00:44:27.694 State both window limits from memory: Go-Back-N at most two-to-the-m minus one, Selective-Repeat at most two-to-the-m-minus-one. 00:44:27.744 --> 00:44:33.074 And be able to say in one sentence why Selective-Repeat gets half. 00:44:33.124 --> 00:44:42.064 Walk a loss through both protocols and count: what is binned, what is buffered, what is resent, and how many transmissions each takes. 00:44:42.114 --> 00:44:48.294 Example twenty-three point eight is the model, and the demo is the practice. 00:44:48.344 --> 00:44:57.294 And say what each protocol protects and what it pays with. Go-Back-N protects the receiver and pays in bandwidth; Selective-Repeat protects the wire and pays in memory. 00:44:59.134 --> 00:45:05.424 That single sentence is most of a comparison question. 00:45:05.654 --> 00:45:10.584 Three phrasings that lose marks while you know the material perfectly. 00:45:10.634 --> 00:45:17.224 "Compare Go-Back-N and Selective-Repeat" is not "define Go-Back-N and Selective-Repeat". 00:45:17.274 --> 00:45:26.224 Two definitions side by side is not a comparison. Name what each protects, what it pays with, and when each bet wins — and the mark is yours. 00:45:27.944 --> 00:45:36.344 "Find the utilisation" wants a computed and shown. Write a equals T-p over T-f explicitly, before the substitution. 00:45:36.394 --> 00:45:42.864 Method marks are real, and a bare final percentage with no a in sight is fragile. 00:45:42.914 --> 00:45:48.584 And "why does Selective-Repeat need a smaller window?" wants the wrap, not the buffers. 00:45:48.634 --> 00:45:57.584 The answer is about sequence numbers wrapping and an old packet impersonating a new one — not about memory, which is a different cost entirely. 00:46:00.607 --> 00:46:03.957 Three wordings, one session. 00:46:04.007 --> 00:46:09.487 "Find the utilisation", or "find the window". Pure arithmetic, one formula. 00:46:09.537 --> 00:46:18.487 a equals T-p over T-f; U equals W over one plus two a, capped; and the pipe fills at one plus two a. 00:46:19.187 --> 00:46:25.917 "Trace this loss through the protocol" wants you to count what is binned and what is resent. 00:46:25.967 --> 00:46:34.917 Go-Back-N: receiver window one, one timer, resend everything outstanding. Selective-Repeat: buffer, individual acknowledgment, resend one. 00:46:37.217 --> 00:46:42.827 And "compare Go-Back-N and Selective-Repeat" is not two definitions side by side. 00:46:42.877 --> 00:46:51.827 What each protects, what each pays with, the same ceiling and different bills — and the two window limits. 00:46:52.674 --> 00:46:54.474 That is Session twenty-two. 00:46:54.524 --> 00:47:03.474 Stop-and-Wait wastes the pipe; windows fill it. U equals W over one plus two a, and the pipe fills at W equals one plus two a. 00:47:04.414 --> 00:47:13.364 Go-Back-N: cumulative acknowledgments, one timer, a receiver window of one, and a window at most two-to-the-m minus one. 00:47:13.804 --> 00:47:22.624 Selective-Repeat: individual acknowledgments, a timer each, buffers at the receiver, and a window at most half the space. 00:47:22.674 --> 00:47:31.624 And when frames die, Go-Back-N resends the past while Selective-Repeat resends the loss. That one sentence answers most comparison questions on its own. 00:47:33.424 --> 00:47:38.984 So: protocols are bets about the channel. Pick the protocol after you have met the wire. 00:47:39.034 --> 00:47:47.984 Next session is the last one. TCP — the protocol carrying this sentence to your device right now. It inherits everything from today, and then it does something no protocol here dared: it deliberately accelerates until the network drops a packet, on purpose, forever. 00:47:56.424 --> 00:48:05.314 Why that is the smartest thing the Internet does — and the proper answer to the very first question of Week one — next session. 00:48:05.364 --> 00:48:09.577 Come to the finale.