WEBVTT 00:00:00.000 --> 00:00:03.690 Welcome back to CSE 316 — Data Communication and Networking. 00:00:03.740 --> 00:00:09.880 This is the detailed video version of Session seventeen, and it is the finale of the addressing arc. 00:00:09.930 --> 00:00:18.880 Everything you have built since Session nine — every block, every mask, every AND — becomes a row in a table today, and you find out what a router actually does with it. 00:00:23.260 --> 00:00:32.210 One algorithm: AND every row, collect the matches, and take the longest prefix. Taught by hand, by video, and by simulator until it is reflex. 00:00:33.990 --> 00:00:42.390 Then the two loose ends close: where addresses come from, and how tens of billions of devices share four billion addresses. 00:00:42.440 --> 00:00:49.004 Two hooks fall today. One of them was asked eight lectures ago. 00:00:49.054 --> 00:00:52.344 Last session ended on a cliff. 00:00:52.394 --> 00:01:01.344 One address — one forty dot twenty-four dot seven dot two hundred — sitting inside TWO advertised blocks: the old aggregate, and the moved customer's new route. 00:01:03.164 --> 00:01:05.954 Today the cliff gets a floor. 00:01:06.004 --> 00:01:10.564 A router holds four rules. A packet arrives, and all four match it. 00:01:10.614 --> 00:01:19.564 It does not panic, it does not vote, and it does not ask a supervisor. One tie-breaker, run once per packet in every router on the path. 00:01:20.914 --> 00:01:28.604 Which rule wins? The longest prefix — the matching row with the most one-bits in its mask — and always that one. 00:01:28.654 --> 00:01:37.604 Section one runs the algorithm by hand. Section two derives the why: a longer prefix names a smaller block, so it is the most specific true statement about this destination. 00:01:40.794 --> 00:01:49.744 And a second question, eight lectures old — where your watch's address comes from — is answered in section four. 00:01:50.621 --> 00:01:52.951 Section one. The tie-breaker. 00:01:53.001 --> 00:02:01.951 A forwarding table is rows of facts, and forwarding is one AND per row followed by one comparison. The only interesting part is what happens when more than one row says yes. 00:02:07.309 --> 00:02:10.999 Start with what a row actually contains. 00:02:11.049 --> 00:02:16.059 A prefix. Every block you have built since Session nine becomes one of these. 00:02:16.109 --> 00:02:20.739 The block is the question; the row is the answer to it. 00:02:20.789 --> 00:02:27.209 A next hop, and an interface. And notice how humble forwarding is: it never plans the journey. 00:02:27.259 --> 00:02:33.419 It hands the packet one hop closer, and trusts the next router to do the same. 00:02:33.469 --> 00:02:42.209 Once the next hop is chosen, the network layer's work is finished. ARP finds that neighbour's MAC address, and framing carries it. 00:02:42.259 --> 00:02:45.789 Weeks four and nine shake hands right there. 00:02:45.839 --> 00:02:52.989 And the last row is the strangest and the simplest: zero dot zero dot zero dot zero, slash ZERO. 00:02:53.039 --> 00:03:01.989 Prefix length zero means zero bits have to agree — and an AND with no ones always succeeds. It matches every address ever sent. 00:03:02.939 --> 00:03:11.889 So: a rule that always fits, and that must never win unless nothing else does. Slide seventeen resolves it. 00:03:13.209 --> 00:03:19.989 Here is the table we will use all hour. Copy it down; it is worth having in front of you. 00:03:20.039 --> 00:03:28.989 A slash twenty-six — one lab. A slash twenty-three — Org4, last session's biggest customer. The slash twenty-two — the ISP's whole aggregate. And the default. 00:03:31.309 --> 00:03:36.639 That is the entire arc, sitting there as furniture. 00:03:36.689 --> 00:03:45.029 And now notice the scandal. The slash twenty-six lives inside the slash twenty-three, which lives inside the slash twenty-two. 00:03:45.079 --> 00:03:49.339 Three of the four rows overlap — deliberately. 00:03:49.389 --> 00:03:56.529 That is not sloppy configuration. It is aggregation plus detail — which is exactly what last session bought. 00:03:56.579 --> 00:04:02.619 Nesting is normal. And it is precisely why the table needs a tie-breaker in order to exist at all. 00:04:02.669 --> 00:04:11.619 A table with no overlapping rows would need no tie-breaker — and would also need one row per destination on Earth. 00:04:12.869 --> 00:04:21.819 Now do it by hand. Destination eleven dot ten dot two dot seventy-five. Four rows, four ANDs. Do them with me. 00:04:22.179 --> 00:04:27.069 Row one, the slash twenty-six. Its mask ends in one ninety-two. 00:04:27.119 --> 00:04:35.039 Seventy-five in binary is zero-one-zero-zero-one-zero-one-one, so the top two bits are zero-one — sixty-four. 00:04:35.089 --> 00:04:38.939 The network says eleven dot ten dot two dot sixty-four. Match. 00:04:38.989 --> 00:04:46.609 Row two, the slash twenty-three. Third octet: two AND two five four is two. 00:04:46.659 --> 00:04:51.979 The network says eleven dot ten dot two dot zero. Match. 00:04:52.029 --> 00:04:57.379 Row three, the slash twenty-two. Two AND two five two is zero. 00:04:57.429 --> 00:05:00.159 Eleven dot ten dot zero dot zero. Match. 00:05:00.209 --> 00:05:08.679 Row four, the default. An AND with no ones always succeeds. Always a match. 00:05:08.729 --> 00:05:14.829 Four matches — and the ranking is twenty-six beats twenty-three beats twenty-two beats zero. 00:05:14.879 --> 00:05:22.989 Out through m3, next hop ten dot nine dot nine dot two. Box that ranking; it stays on your page all session. 00:05:23.039 --> 00:05:31.989 Notice that only the interesting octet ever got written in binary. Everything else was a lookup you already know by heart. 00:05:33.649 --> 00:05:38.099 First, the obvious wrong answer, killed properly. 00:05:38.149 --> 00:05:46.709 A lazy algorithm takes the first hit and runs. And it would behave differently depending on the order the rows happen to sit in. 00:05:46.759 --> 00:05:53.809 Which is another way of saying it would be wrong. The same packet, the same table, a different answer after a reboot. 00:05:53.859 --> 00:05:57.759 That is not forwarding. That is a coin toss. 00:05:57.809 --> 00:06:05.649 The real rule: every row that fits gets a voice. Collect all the matches first — and only then rank them. 00:06:05.699 --> 00:06:14.649 And the ranking is by prefix length. Most one-bits in the mask wins. Twenty-six beats twenty-three beats twenty-two beats zero. 00:06:15.069 --> 00:06:24.019 One caution for the exam: a sorted table searched top-down is an IMPLEMENTATION of that rule, and a very common one. State the rule, not the implementation. 00:06:28.453 --> 00:06:33.723 The whole of forwarding, in three sentences and a footnote. 00:06:33.773 --> 00:06:38.893 One: AND the destination with every row's mask, and compare with the prefix. 00:06:38.943 --> 00:06:46.373 One AND and one comparison per row. No exceptions, no shortcuts, no special cases. 00:06:46.423 --> 00:06:50.763 Two: among the rows that matched, take the longest prefix. 00:06:50.813 --> 00:06:55.613 Not the first, not the newest, not the most familiar. 00:06:55.663 --> 00:07:00.463 Three: send the packet out that row's interface, to that row's next hop. 00:07:00.513 --> 00:07:07.643 And if the next hop column says "direct", deliver it on the spot — ARP, and a frame. 00:07:07.693 --> 00:07:16.643 And the footnote: if nothing matched at all, discard and report. The packet is dropped and ICMP destination-unreachable goes back to the source. 00:07:17.763 --> 00:07:26.713 Three sentences and one AND. That is the whole of forwarding — everything else in this session is consequence. 00:07:28.787 --> 00:07:34.517 Forty-two seconds, and it is the gauntlet you just ran, executed. 00:07:34.567 --> 00:07:42.387 There is the table, and there is the nesting: the slash twenty-six inside the slash twenty-three inside the slash twenty-two. 00:07:42.437 --> 00:07:50.537 Not sloppy configuration — aggregation plus detail, which is exactly why a tie-breaker has to exist. 00:07:50.587 --> 00:07:56.217 The per-row test, written out. Destination AND mask, compared with the prefix. 00:07:56.267 --> 00:08:05.217 Seventy-five AND one ninety-two is sixty-four; the row wanted sixty-four. Match. That is the same AND you have run since Session ten. 00:08:06.877 --> 00:08:13.717 Now every row. All four say yes — and there is the point: matching is not the question a router is asking. 00:08:13.767 --> 00:08:19.967 A lazy algorithm that stopped at the first hit would depend on the order the rows sit in. 00:08:20.017 --> 00:08:26.187 Longest prefix wins. Twenty-six beats twenty-three beats twenty-two beats zero. 00:08:26.237 --> 00:08:34.907 Out through m3, next hop ten dot nine dot nine dot two — and the three losing rows are still perfectly true. 00:08:34.957 --> 00:08:43.817 And the why. The four rows nest inside each other: four billion addresses, a thousand, five hundred and twelve, sixty-four. 00:08:43.867 --> 00:08:50.897 Longest prefix means smallest set means the most specific true statement about this address. 00:08:50.947 --> 00:08:56.807 Then the default: mask of no bits, so it matches everything and loses to everything. 00:08:56.857 --> 00:09:02.757 No special code anywhere — it is simply the shortest prefix in the table. 00:09:02.807 --> 00:09:09.797 And the last case: no match, no default, so the packet is discarded and ICMP goes back. 00:09:09.847 --> 00:09:18.797 Match, take the longest, and if nothing matches report it. Three sentences, and that is forwarding. 00:09:19.312 --> 00:09:28.262 Your turn. Same table, different destination: eleven dot ten dot zero dot nine. Pause if you want ninety seconds; otherwise come with me. 00:09:34.742 --> 00:09:43.692 The slash twenty-six. Eleven dot ten dot zero dot nine masked gives eleven dot ten dot zero dot zero — and the row wanted eleven dot ten dot two dot sixty-four. 00:09:44.332 --> 00:09:48.802 No. And notice you did not guess: you divided. 00:09:48.852 --> 00:09:55.872 The slash twenty-three. Third octet: zero AND two five four is zero, and the row wanted two. 00:09:55.922 --> 00:09:59.232 No. One octet decides it. 00:09:59.282 --> 00:10:07.262 The slash twenty-two. Zero AND two five two is zero, and the row wants eleven dot ten dot zero dot zero. 00:10:07.312 --> 00:10:10.422 Yes. Twenty-two bits. 00:10:10.472 --> 00:10:14.602 The default. Always. Zero bits. 00:10:14.652 --> 00:10:19.502 Two voices this time, and twenty-two beats zero. Interface m1. 00:10:19.552 --> 00:10:28.502 Different destination, different number of matches, identical method. Four ANDs, four verdicts, arithmetic all the way down. 00:10:30.978 --> 00:10:33.138 Checkpoint one. 00:10:33.188 --> 00:10:40.078 One. For eleven dot ten dot two dot seventy-five, run all four rows and say which wins, and why. 00:10:40.128 --> 00:10:49.078 Two. Why is "take the first matching row" wrong, even though it often gives the right answer? 00:10:49.248 --> 00:10:58.198 Three. Zero dot zero dot zero dot zero slash zero matches every address ever sent. Why does it almost never win? 00:11:00.618 --> 00:11:09.568 One. All four match: seventy-five AND one ninety-two is sixty-four, tick; two AND two five four is two, tick; two AND two five two is zero, tick; and the default always. The slash twenty-six is longest, so it wins — out on m3 to ten dot nine dot nine dot two. 00:11:14.738 --> 00:11:23.688 Two. Because the answer would then depend on the order the rows are stored in, which is an accident of configuration. The rule is longest-wins over all matches; a sorted table is one way to implement it. 00:11:32.538 --> 00:11:41.488 Three. Because zero bits is the shortest possible prefix. Any other matching row is longer, so the default only wins when nothing else matched at all. 00:11:45.478 --> 00:11:48.508 Section two. Why longest means correct. 00:11:48.558 --> 00:11:57.508 All four rows told the truth. The question is not which one is right — it is which one knows most. And that is worth owning rather than memorising. 00:12:00.745 --> 00:12:07.165 Take the four matching rows and read them as sentences about where the packet is going. 00:12:07.215 --> 00:12:14.315 The default says: it is somewhere on the Internet. True — and four billion addresses of vague. 00:12:14.365 --> 00:12:23.315 The slash twenty-two says: it is in the ISP's block. True, and closer. Still a thousand addresses of vague. 00:12:23.465 --> 00:12:32.415 The slash twenty-three says: it is in Org4's block. True, and closer again — five hundred and twelve addresses. 00:12:32.565 --> 00:12:39.155 And the slash twenty-six says: it is in this lab. True, and sharp — sixty-four addresses. 00:12:39.205 --> 00:12:48.155 Longer prefix means smaller block means a more specific claim. Longest prefix equals smallest set equals the most specific true statement about this address. 00:12:50.065 --> 00:12:56.906 Every enclosing row is still true. It just knows less. 00:12:56.956 --> 00:13:02.456 This is the part worth owning, because it turns a rule into a reason. 00:13:02.506 --> 00:13:11.456 Nobody advertises a slash twenty-six by accident. A long prefix got into that table because a router with better knowledge went to the trouble of saying it. 00:13:11.856 --> 00:13:16.556 Length is a proxy for how close the speaker was to the truth. 00:13:16.606 --> 00:13:21.136 So trusting the most specific voice is not a convention somebody chose. 00:13:21.186 --> 00:13:30.136 It is the only rule under which an aggregate, a hole and a default can all live in one table without contradiction — each of them true at its own scale. 00:13:32.286 --> 00:13:40.056 And that is last session's invoice, paid in full. Aggregation buys silence; longest-prefix match pays for it. 00:13:40.106 --> 00:13:43.906 I said that sentence on credit on Tuesday. It is settled now. 00:13:43.956 --> 00:13:52.360 The tie-breaker is not arbitrary. It is knowledge, measured in bits of prefix. 00:13:52.410 --> 00:13:57.510 Now go back to the cliff we ended on, and watch it get its floor. 00:13:57.560 --> 00:14:06.510 The old aggregate still says one forty dot twenty-four dot seven dot zero slash twenty-four, via R1 — and for organisations one to three that is still exactly right. 00:14:09.960 --> 00:14:18.910 The new voice says one forty dot twenty-four dot seven dot one ninety-two slash twenty-six, via R3 — and for organisation four that is the only correct answer. 00:14:22.450 --> 00:14:31.400 A packet for dot two hundred matches both. Two hundred AND two five five two five five two five five zero gives dot seven dot zero — tick. 00:14:32.320 --> 00:14:41.270 Two hundred AND two five five two five five two five five one ninety-two gives dot seven dot one ninety-two — also tick. 00:14:42.280 --> 00:14:51.230 Twenty-six beats twenty-four, so organisation four's traffic turns toward R3 — and organisations one to three keep riding the slash twenty-four, entirely unaffected. 00:14:53.760 --> 00:15:02.710 One extra row, worldwide, instead of three. That is what longest-prefix match buys, and why the aggregate never had to be torn up. 00:15:06.702 --> 00:15:12.332 The same table, and the machine doing the ANDs so you can watch the ranking instead. 00:15:12.382 --> 00:15:21.062 State one is the gauntlet you ran by hand. Four green rows, four ANDs written out, and the bits column on the right. 00:15:21.112 --> 00:15:26.882 Twenty-six beats twenty-three beats twenty-two beats zero — out on m3. 00:15:26.932 --> 00:15:32.022 State two changes one digit: seventy-five becomes one twenty-nine. 00:15:32.072 --> 00:15:41.022 The slash twenty-six goes red, the slash twenty-three wins, and the interface changes. One digit, one interface. This is why routers do not vote — the arithmetic IS the vote. 00:15:46.272 --> 00:15:55.222 State three is the drill. Only the slash twenty-two and the default match, and twenty-two beats zero. Interface m1. 00:15:55.352 --> 00:16:03.132 State four adds last session's hole: eleven dot ten dot one dot zero slash twenty-four, punched through the aggregate. 00:16:03.182 --> 00:16:10.032 The slash twenty-four out-shouts the slash twenty-two, and the packet goes to the customer who moved. 00:16:10.082 --> 00:16:18.222 State five is an address the hole does NOT cover, and Org4's own slash twenty-three catches it, exactly as it should. 00:16:18.272 --> 00:16:26.292 The hole covers two hundred and fifty-six addresses — one slash twenty-four. Everyone else is untouched. 00:16:26.342 --> 00:16:35.282 State six: an address the router knows nothing about. One green row, and it is the default — which is exactly its job. 00:16:35.332 --> 00:16:40.412 And state seven deletes the default and forwards again. DROPPED, in red. 00:16:40.462 --> 00:16:48.012 That red is life without a default route: any destination you have no specific knowledge of simply dies at your door. 00:16:48.062 --> 00:16:57.012 The slash zero row is the router's humility — "I don't know, but I know who might". Never build a table without it. 00:16:58.394 --> 00:17:05.574 Be precise about the default route, because it is the row people call a special case and it is not. 00:17:05.624 --> 00:17:12.334 Zero dot zero dot zero dot zero slash zero. Mask zero dot zero dot zero dot zero — no bits at all. 00:17:12.384 --> 00:17:18.064 So AND anything gives zero dot zero dot zero dot zero, which equals the prefix. 00:17:18.114 --> 00:17:27.064 It matches every address there is, including ones the router has never heard of — which is the whole point of it. 00:17:28.654 --> 00:17:35.044 And zero bits is the weakest possible claim, so any other matching row is longer and beats it. 00:17:35.094 --> 00:17:38.914 Therefore it wins only when nothing else matched. 00:17:38.964 --> 00:17:45.214 No special code anywhere. It is just a row, handled by the same one rule. 00:17:45.264 --> 00:17:48.814 Say it as: "I don't know, but I know who might." 00:17:48.864 --> 00:17:57.054 And your home router's whole table is often two rows: your own LAN, and zero dot zero dot zero dot zero slash zero. 00:17:57.104 --> 00:18:03.044 That is a complete, correct forwarding table. 00:18:03.094 --> 00:18:07.554 The last case, and it is why the default route matters. 00:18:07.604 --> 00:18:12.264 No row matches, and there is no default. The packet is discarded. 00:18:12.314 --> 00:18:19.154 A router does not guess, does not flood, and does not hold it hopefully in case something turns up. 00:18:19.204 --> 00:18:23.334 An ICMP destination-unreachable goes back to the source. 00:18:23.384 --> 00:18:28.664 The sender finds out; the packet does not silently evaporate. 00:18:28.714 --> 00:18:35.734 Which is why almost every real table carries a default: so that "no match" is a case that never arises. 00:18:35.784 --> 00:18:44.734 Delete the default row and watch a perfectly healthy router start dropping perfectly healthy packets. 00:18:45.027 --> 00:18:47.227 Checkpoint two. 00:18:47.277 --> 00:18:56.227 One. A packet for eleven dot ten dot one dot two hundred arrives, and the table has both eleven dot ten dot zero dot zero slash twenty-two and eleven dot ten dot one dot zero slash twenty-four. Which wins? 00:19:02.377 --> 00:19:09.077 Two. State, in one sentence, why longer means more specific means more trustworthy. 00:19:09.127 --> 00:19:18.077 Three. The default row is deleted and eight dot eight dot eight dot eight arrives. What happens, and what does the sender learn? 00:19:20.127 --> 00:19:29.077 One. Both match: one AND two five two is zero, tick; and one AND two five five is one, tick. The slash twenty-four is longer, so it wins. Same shape as last session's moved customer. 00:19:32.447 --> 00:19:41.397 Two. A longer prefix names a smaller set, so it is a narrower claim — and a narrow claim only got into the table because a router with better knowledge advertised it. 00:19:42.867 --> 00:19:51.817 Three. No row matches, so the packet is discarded and an ICMP destination-unreachable is returned to the source. Nothing is guessed and nothing is flooded. 00:19:56.625 --> 00:19:59.585 Section three. Where addresses come from. 00:19:59.635 --> 00:20:08.585 Every table, every mask and every AND assumed the host HAS an address. Who gave it one? And how do tens of billions of devices share four billion addresses? 00:20:13.492 --> 00:20:20.962 A machine wakes up owning nothing but a random transaction number, so consider what it can possibly say. 00:20:21.012 --> 00:20:28.342 It shouts DHCPDISCOVER. Source zero dot zero dot zero dot zero, because "this host" is the only name it has. 00:20:28.392 --> 00:20:34.352 Destination all ones, because it does not know who it is calling. 00:20:34.402 --> 00:20:41.472 Last session's special addresses were not trivia. They are exactly the vocabulary of being newborn. 00:20:41.522 --> 00:20:48.732 Any server that hears it answers DHCPOFFER: here is an address for you, and here is the lease. 00:20:48.782 --> 00:20:55.342 And the offer is broadcast too — so rival servers can see the bid and outbid it. 00:20:55.392 --> 00:21:00.252 The host picks the best one and broadcasts DHCPREQUEST — "I choose you". 00:21:00.302 --> 00:21:08.332 Which doubles as the rejection letter that every other server reads. One message, two jobs. 00:21:08.382 --> 00:21:14.732 And the chosen server closes with DHCPACK: it is yours, and the clock is running. 00:21:14.782 --> 00:21:18.102 Or NACK — somebody took it — start over. 00:21:18.152 --> 00:21:27.102 Four messages: DISCOVER, OFFER, REQUEST, ACK. D-O-R-A, if you want it to stick. 00:21:28.068 --> 00:21:33.528 Now the exam favourite. The reason matters more than the two numbers. 00:21:33.578 --> 00:21:42.528 Server port sixty-seven, client port sixty-eight. And the client's is the odd one — clients normally use ephemeral ports. 00:21:42.868 --> 00:21:49.468 Because the replies are broadcast. Every host on the network receives them, not just the one that asked. 00:21:49.518 --> 00:21:54.168 So the port has to be one that nobody else is listening on. 00:21:54.218 --> 00:22:00.918 Forouzan's example is the one to remember. If the DHCP reply landed on ephemeral port fifty-six thousand and seventeen, 00:22:00.968 --> 00:22:07.798 some unlucky DAYTIME client waiting on the same number would receive it, and be thoroughly confused. 00:22:07.848 --> 00:22:16.798 Port sixty-eight means only DHCP clients even look. And two clients racing are separated by the transaction ID — not by the port, which they share. 00:22:19.408 --> 00:22:27.618 And the OFFER carries more than an address: the mask, the default router, and the DNS server. 00:22:27.668 --> 00:22:36.618 The default router being, of course, the first next-hop of everything we did before the break. One message bootstraps the whole of Section One. 00:22:41.364 --> 00:22:47.604 One more thing about DHCP, and it is economics rather than protocol. 00:22:47.654 --> 00:22:54.394 Addresses are lent, not given. A lease has a duration, and at fifty per cent of it the host renews — 00:22:54.444 --> 00:22:59.694 unicast this time, because by then it knows exactly who to ask. 00:22:59.744 --> 00:23:08.694 So a pool serves more machines than it has addresses. A thousand addresses can serve four thousand households, because at any moment most of them are asleep. 00:23:10.584 --> 00:23:19.214 And that is the same bargain as statistical multiplexing: sell the average, not the peak, and accept a small probability of refusal. 00:23:19.264 --> 00:23:22.944 You have met this argument before. It was about bandwidth then. 00:23:22.994 --> 00:23:31.944 Which is also why one sixty-nine dot two five four exists: the address a host gives itself when the pool had nothing left, or nobody answered at all. 00:23:36.457 --> 00:23:42.637 Forty-two seconds for both loose ends — DHCP first, then NAT, then the hook from week five. 00:23:42.687 --> 00:23:51.637 There they are, named. Who gave the host an address? And why does your watch claim one when there are not enough to go round? 00:23:53.427 --> 00:24:00.187 Two answers: one leases, the other rewrites. Different boxes, different jobs. 00:24:00.237 --> 00:24:06.167 DISCOVER. Source zero dot zero dot zero dot zero — "this host", the only name it has. 00:24:06.217 --> 00:24:15.167 Destination all ones, because it does not know who it is calling. Last session's reserved corners, doing real work. 00:24:15.977 --> 00:24:23.417 The full ladder. The offer is broadcast so rivals can outbid; the request is broadcast so it doubles as the rejection letter. 00:24:23.467 --> 00:24:25.277 D-O-R-A. 00:24:25.327 --> 00:24:34.277 Then the ports. Sixty-seven and sixty-eight, and the reason: the replies are broadcast, so every host receives them. 00:24:35.047 --> 00:24:40.977 On an ephemeral port, some unlucky DAYTIME client would receive your DHCP reply. 00:24:41.027 --> 00:24:48.657 Now NAT. Private addresses inside, one real address at the door, and a rewrite in both directions. 00:24:48.707 --> 00:24:54.587 The Internet never sees a private address — and could not route to one if it did. 00:24:54.637 --> 00:25:03.587 And the five-column table, with the failure it exists to fix: two replies at one public address, identical in every field but the port. 00:25:03.827 --> 00:25:12.777 Laptop fourteen hundred, phone fourteen-oh-one. Ports, moonlighting as return addresses two weeks before we meet them properly. 00:25:13.337 --> 00:25:18.447 And the payoff: your watch does not have an address. It owns a row in a table. 00:25:18.497 --> 00:25:27.447 Four billion addresses serve tens of billions of devices, because almost everything is borrowing its name. 00:25:28.644 --> 00:25:31.674 Checkpoint three. 00:25:31.724 --> 00:25:39.384 One. Name the four DHCP messages in order, and give the source and destination of the first one. 00:25:39.434 --> 00:25:47.264 Two. Why does the DHCP client use well-known port sixty-eight instead of an ephemeral port? 00:25:47.314 --> 00:25:56.264 Three. A host has address one sixty-nine dot two five four dot seven dot nine. What has happened, and what has NOT happened? 00:25:58.584 --> 00:26:07.534 One. DISCOVER, OFFER, REQUEST, ACK. The DISCOVER goes from zero dot zero dot zero dot zero to two fifty-five dot two fifty-five dot two fifty-five dot two fifty-five — "this host", and limited broadcast. 00:26:13.174 --> 00:26:22.124 Two. Because the replies are broadcast, so every host receives them. On an ephemeral port some unrelated client waiting on the same number would receive the DHCP reply. Port sixty-eight means only DHCP clients look. 00:26:28.514 --> 00:26:37.464 Three. The host asked for an address and nobody answered, so it gave itself a link-local one. It has NOT been configured, it cannot reach the Internet, and the fault is DHCP — diagnosable from across the room. 00:26:45.911 --> 00:26:49.291 Section four. One building, one voice. 00:26:49.341 --> 00:26:58.291 Your laptop said one ninety-two dot one sixty-eight-something. Here is the machinery that makes that legal — and the answer to a question asked eight lectures ago. 00:27:02.277 --> 00:27:07.517 The mechanism first, and it is two rewrites and a notebook. 00:27:07.567 --> 00:27:16.517 Inside the site: private addresses. Free, unroutable, invisible — last session's reserved corners, doing real work. 00:27:17.687 --> 00:27:24.177 At the door: one router holding one real address — two hundred dot twenty-four dot five dot eight. 00:27:24.227 --> 00:27:29.777 Every outgoing packet has its source REWRITTEN to that public address. 00:27:29.827 --> 00:27:38.777 And the router jots down who was talking to whom — so that when the reply arrives it can rewrite the destination back to the private original. 00:27:39.067 --> 00:27:45.627 The Internet never sees a private address. Ever. It sees one building speaking with one voice. 00:27:45.677 --> 00:27:49.407 And it could not route to a private address even if it wanted to. 00:27:49.457 --> 00:27:58.407 One catch worth marks: with the simple table, conversations must START inside. NAT is a one-way door that remembers who went out. 00:28:01.075 --> 00:28:04.915 Now the failure that forces the real design. 00:28:04.965 --> 00:28:12.625 Laptop and phone both browse twenty-five dot eight dot three dot two. Two replies arrive at one public address. 00:28:12.675 --> 00:28:19.905 And the address alone cannot say which is which — everything about the two packets is identical. 00:28:19.955 --> 00:28:26.625 So the table has five columns: private address, private PORT, external address, external port, and protocol. 00:28:26.675 --> 00:28:30.445 The port is what does the work. 00:28:30.495 --> 00:28:35.245 The laptop asked from port fourteen hundred, the phone from fourteen-oh-one. 00:28:35.295 --> 00:28:41.785 The replies carry those numbers home. One row each, and no ambiguity anywhere. 00:28:41.835 --> 00:28:49.825 And notice who is moonlighting. Ports are transport-layer creatures — chapter twenty-three, two weeks from now. 00:28:49.875 --> 00:28:56.195 When we meet them properly, remember they were here first, doing a job nobody designed them for. 00:28:56.245 --> 00:29:01.925 That is how most of networking actually happened. 00:29:01.975 --> 00:29:06.905 And the catch, which is worth marks and worth understanding. 00:29:06.955 --> 00:29:15.875 An unsolicited packet arrives at two hundred dot twenty-four dot five dot eight. The router looks for a row to translate it with — and there is none. 00:29:15.925 --> 00:29:23.355 Nobody inside started this conversation, so there is nothing to look up. The packet is discarded. 00:29:23.405 --> 00:29:30.065 Which people mistake for a firewall. It is not one. It is a side effect of having a translation table at all — 00:29:30.115 --> 00:29:35.295 but it is a genuinely useful side effect, and it is a mark worth having. 00:29:35.345 --> 00:29:43.205 And it is why running a server behind NAT needs extra work. A permanent row has to be configured by hand — port forwarding — 00:29:43.255 --> 00:29:46.605 because no outgoing packet will ever create it for you. 00:29:46.655 --> 00:29:55.605 NAT is a one-way door that remembers who went out. Everything awkward about it follows from that single sentence. 00:29:56.097 --> 00:29:59.547 Both hooks. Today's first. 00:29:59.597 --> 00:30:04.227 Today's hook: which rule wins? The longest prefix, always. 00:30:04.277 --> 00:30:10.807 And you now own the why: longest means smallest block means most specific claim. 00:30:10.857 --> 00:30:17.667 First-in-the-table was wrong. Newest was wrong. The tie-breaker is knowledge, measured in bits of prefix — 00:30:17.717 --> 00:30:23.337 and specific routes exist because someone with better knowledge advertised them. 00:30:23.387 --> 00:30:28.657 And now week five's hook. More people than addresses, yet your watch "has" one. 00:30:28.707 --> 00:30:31.747 It does not. It never did. 00:30:31.797 --> 00:30:40.747 DHCP leased it a private address out of last session's reserved corners. NAT rewrites its packets into one shared public voice, and tells the replies apart by port. 00:30:41.237 --> 00:30:43.657 Your watch owns a row in a table. 00:30:43.707 --> 00:30:51.597 Four billion addresses serve tens of billions of devices, because almost everything is borrowing. 00:30:51.647 --> 00:30:56.037 That is the answer, eight weeks in the making. 00:30:56.087 --> 00:31:03.581 And the motto: most specific wins; everything else is borrowed. 00:31:04.591 --> 00:31:10.731 Two devices, one public address, and the table filling itself in front of you. 00:31:10.781 --> 00:31:18.661 State one: the laptop asks for a page. Watch the two lines — as it leaves the laptop, and as it leaves the router. 00:31:18.711 --> 00:31:27.661 The source is rewritten, and a row appears. The server will answer the public address, because it is the only address it was ever shown. 00:31:28.231 --> 00:31:35.291 State two is the reverse rewrite. The reply arrives addressed to the public address on port fourteen hundred. 00:31:35.341 --> 00:31:44.001 Port fourteen hundred finds the row; the row supplies the private address. The laptop never learns any of this happened. 00:31:44.051 --> 00:31:49.851 State three: the phone, same server. A second row, and a different private port. 00:31:49.901 --> 00:31:57.861 Both devices now appear to the Internet as one address. What distinguishes them is not the address at all. 00:31:57.911 --> 00:32:05.261 State four is the problem, laid out. Two replies, same source, same destination address, same port eighty. 00:32:05.311 --> 00:32:07.101 Identical in every field but one. 00:32:07.151 --> 00:32:15.981 State five tries to route them home by address alone — and cannot. Two rows, one external address. 00:32:16.031 --> 00:32:24.981 With a three-column table the router would have to guess, and guessing is not a thing routers do. That failure is why the fifth column exists. 00:32:25.471 --> 00:32:32.251 State six is the one-way door. A packet from outside that nobody asked for, on a port with no row. 00:32:32.301 --> 00:32:40.691 Refused. Conversations must start inside — and that is the mark, not "NAT is a firewall". 00:32:40.741 --> 00:32:49.691 And state seven is the whole mechanism in five lines. Open it, serve a few customers yourself, and watch the table do the work the address cannot. 00:32:53.420 --> 00:32:58.660 Read this at speed. Every line is a callback, not a lesson. 00:32:58.710 --> 00:33:07.660 DHCP names your laptop, and the datagram launches — best effort, no promises. ARP and framing carry it to the router. 00:33:08.190 --> 00:33:12.680 Weeks four, five and nine, in one sentence. 00:33:12.730 --> 00:33:21.680 NAT swaps its passport at the door. One public address, one row in a table, and the reply will find its way home by port. 00:33:22.180 --> 00:33:31.130 Every router on the path runs today's four ANDs and trusts the longest voice — against tables that stay small only because of last session's aggregation. 00:33:33.500 --> 00:33:40.750 Over blocks that exist because of the allocation fortnight, while queues add delay and physics sets the bit rate. 00:33:40.800 --> 00:33:49.750 Nothing in that sentence is new to you any more. That is what CLO4 means by "analyse addressing and forwarding" — you have just done the Internet, end to end. 00:33:54.255 --> 00:34:00.455 One separation before the checkpoint, because these two get conflated constantly. 00:34:00.505 --> 00:34:09.455 DHCP hands out addresses, with a time limit. It is a server on your network, answering broadcasts from machines that do not yet have a name. 00:34:09.935 --> 00:34:12.825 It never rewrites anything. 00:34:12.875 --> 00:34:20.575 NAT rewrites addresses and ports, in both directions. It is a function in your router, and it never hands out anything. 00:34:20.625 --> 00:34:25.615 It edits packets in flight and keeps a table of what it edited. 00:34:25.665 --> 00:34:30.285 And they live in the same box at home, which is exactly why they get confused. 00:34:30.335 --> 00:34:39.285 Your home router does both, plus forwarding, plus switching, plus wireless. Five jobs, one plastic case — and five different answers in an exam. 00:34:40.695 --> 00:34:49.645 Conflating the two is the most common error on this pair. Separate them by what they do: DHCP leases, NAT rewrites. 00:34:52.739 --> 00:34:57.859 Checkpoint four, and it is the last drill of the addressing arc. 00:34:57.909 --> 00:35:06.519 One. Who gave the phone one ninety-two dot one sixty-eight dot zero dot twenty-three, and by which four messages? 00:35:06.569 --> 00:35:14.319 Two. What does the web server see as the source address, and why can it never see the private one? 00:35:14.369 --> 00:35:23.199 Three. Phone and laptop stream from the same server. How do the two replies find their way home? 00:35:23.249 --> 00:35:32.199 One. DHCP, by DISCOVER, OFFER, REQUEST and ACK — with the DISCOVER sent from zero dot zero dot zero dot zero to all ones. 00:35:32.389 --> 00:35:41.339 Two. The NAT's public address. Private addresses are unroutable on the Internet, so no reply addressed to one could ever come back — which is exactly why the rewrite exists. 00:35:44.109 --> 00:35:53.059 Three. By port, through the five-column table. The laptop's conversation was recorded with one port and the phone's with another, so the two replies differ in one field, and the router reads that field. 00:35:59.882 --> 00:36:05.612 Five ways to lose these marks, and two of them are the pair I have just separated. 00:36:05.662 --> 00:36:09.492 Wrong: the router takes the first matching row. 00:36:09.542 --> 00:36:18.492 Right: longest-wins over ALL matches. A sorted table searched top-down is one implementation of that rule — state the rule. 00:36:19.032 --> 00:36:23.372 Wrong: slash zero is a special case the router checks last. 00:36:23.422 --> 00:36:32.372 Right: it is an ordinary row with zero bits. It matches everything and loses to everything, with no special code anywhere. 00:36:33.322 --> 00:36:36.152 Wrong: DHCP translates addresses. 00:36:36.202 --> 00:36:45.152 Right: DHCP leases; NAT translates. Different boxes, different jobs — and they only share a plastic case at home. 00:36:46.692 --> 00:36:52.812 Wrong: the web server replied to one ninety-two dot one sixty-eight dot zero dot ten. 00:36:52.862 --> 00:37:01.812 Right: no server ever replies to a private address. A private source address is unroutable, so no reply could ever be addressed back to it. 00:37:03.452 --> 00:37:07.652 Wrong: longest prefix wins because longer rows are newer. 00:37:07.702 --> 00:37:16.652 Right: because longer means a smaller block, a more specific claim, and a speaker who knew more. Length is a proxy for knowledge. 00:37:19.289 --> 00:37:24.599 I said at the start that the algorithm would be small. Here is the proof. 00:37:24.649 --> 00:37:29.119 The per-row test is Session ten's: destination AND mask, compared with the prefix. 00:37:29.169 --> 00:37:35.579 You have run that AND since the week you learned what a mask was. 00:37:35.629 --> 00:37:42.839 The ranking is one comparison of integers: count the one-bits in each matching mask and take the biggest. 00:37:42.889 --> 00:37:47.429 There is no cleverness in it, and no room for judgement. 00:37:47.479 --> 00:37:54.649 So the whole of forwarding is arithmetic you already had. What was new today is the REASON the ranking must exist — 00:37:54.699 --> 00:37:57.079 and that reason was last session's bill. 00:37:57.129 --> 00:38:05.158 Which is why the algorithm fits on a sticky note, and the justification took an hour. 00:38:05.208 --> 00:38:09.198 Four things you should be able to do now. 00:38:09.248 --> 00:38:18.198 One: forward a packet by hand against a five-row table, showing every AND — and say which row wins, and by how many bits. 00:38:19.218 --> 00:38:28.168 Two: explain why longest means most specific means most trustworthy, in one sentence, without using the word "convention". 00:38:28.748 --> 00:38:37.698 Three: draw the DHCP ladder from memory, with both port numbers — and give the reason port sixty-eight is well-known. 00:38:38.618 --> 00:38:45.648 Four: walk a packet through NAT in both directions, naming the field that tells two replies apart. 00:38:45.698 --> 00:38:54.648 Homework: your own five-row table with four hand-forwarded destinations; the DHCP ladder from memory; and read twenty-two point one. 00:38:58.375 --> 00:39:02.275 Three things before the next session. 00:39:02.325 --> 00:39:06.605 One: build your own five-row table and forward four destinations through it. 00:39:06.655 --> 00:39:15.605 Invent the rows — include one nested pair and a default. And write the AND for every row, not just the winner. The rows that lose are where the method shows. 00:39:18.545 --> 00:39:25.845 Two: the DHCP ladder from memory, with the two ports and the sentence about why the client's port is well-known. 00:39:25.895 --> 00:39:30.115 If you can teach it to somebody, you know it. 00:39:30.165 --> 00:39:35.435 Three: read twenty-two point one — IPv6 address space and notation. 00:39:35.485 --> 00:39:44.435 With the arc's irony in mind. This fortnight you mastered scarcity; next week, an address space so large that scarcity is impossible — and the strange fact that NAT survived it anyway. 00:39:48.115 --> 00:39:57.065 Also worth doing: find your own laptop's address. If it starts one ninety-two dot one sixty-eight, or ten, you now know both halves of why. 00:40:00.621 --> 00:40:05.811 Three wordings, and in every case the first move is the same. 00:40:05.861 --> 00:40:10.261 Disguise one: "which interface?" A table and a destination. 00:40:10.311 --> 00:40:17.081 AND every row, then take the longest match. Do not reason about it — write the ANDs. 00:40:17.131 --> 00:40:22.601 Disguise two: "why is this address one ninety-two dot one sixty-eight-something?" 00:40:22.651 --> 00:40:28.051 That is a DHCP and NAT question: leased from a private block, and rewritten at the door. 00:40:28.101 --> 00:40:34.061 Disguise three: "why does this packet get dropped?" Usually the default route. 00:40:34.111 --> 00:40:38.381 No match and no slash zero — discard, and ICMP back to the source. 00:40:38.431 --> 00:40:47.381 In every case, write the arithmetic out rather than reasoning about it. The arithmetic is shorter than the reasoning. 00:40:51.554 --> 00:40:53.484 That is Session seventeen. 00:40:53.534 --> 00:41:01.474 Every rule that fits speaks; the most specific one decides — and most of your devices are borrowing their names anyway. 00:41:01.524 --> 00:41:09.414 Match every row, take the longest, and if nothing matches, discard and report. Three sentences and one AND. 00:41:09.464 --> 00:41:18.414 The default route matches everything and loses to everything. It is not a special case; it is the row with zero bits, and it is the router's humility. 00:41:19.154 --> 00:41:28.104 And your watch does not have an address. DHCP leased it one, NAT rewrites it, and a table tells the replies apart by port. 00:41:28.494 --> 00:41:37.444 That is the addressing arc, complete. Next session we go somewhere the arc did not: the road the Internet did not take in nineteen seventy, and how it came back and took over the core. 00:41:40.074 --> 00:41:44.163 I will see you there.