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.480 This is the detailed video version of Session sixteen, and for three weeks you have done nothing but cut. 00:00:12.530 --> 00:00:21.090 A slash twenty-two into six tenants. A slash twenty-four into labs. Borrow bits, longer names, smaller rooms. 00:00:21.140 --> 00:00:30.090 Today the knife runs backwards. Four slash twenty-fours become one slash twenty-two, and the ISP says exactly one thing to the entire rest of the Internet. 00:00:32.230 --> 00:00:41.180 There is no new arithmetic in this session. There is one new question — what does saying one line actually cost — and the answer changes how you read a routing table. 00:00:45.553 --> 00:00:51.013 The question the whole session hangs on, and both halves of its answer. 00:00:51.063 --> 00:01:00.013 Your ISP owns four neighbouring slash twenty-fours. To the entire rest of the Internet it says exactly ONE thing about them. 00:01:00.463 --> 00:01:05.123 What does it say — and what does it COST to say it? 00:01:05.173 --> 00:01:08.843 What it says is one line: eleven dot ten dot zero dot zero slash twenty-two. 00:01:08.893 --> 00:01:16.913 Sections one and two derive that, and give the three checks that decide when four blocks may be merged at all. 00:01:16.963 --> 00:01:24.123 What it costs is precision. The aggregate speaks for every address inside it, including a customer who has left. 00:01:24.173 --> 00:01:33.123 Section four derives that cost and its fix: a longer prefix punched through the aggregate, which works only because every router lets the most specific row win. 00:01:37.586 --> 00:01:40.296 Section one. The reverse operation. 00:01:40.346 --> 00:01:49.296 Borrowing bits made smaller rooms with longer names. Handing them back makes one bigger name for many rooms — and there is no new arithmetic in that sentence. 00:01:53.412 --> 00:01:56.862 The two directions, side by side. 00:01:56.912 --> 00:02:05.862 Subnetting grows the prefix. Borrow bits from the host side, and you get smaller rooms and more detail. That is Sessions twelve to fifteen in one line. 00:02:08.192 --> 00:02:17.142 Aggregation shrinks it. Hand the bits back, and one bigger name covers many rooms. Same tree, opposite direction. 00:02:17.242 --> 00:02:26.192 Three names for the same thing. Forouzan says address aggregation, or summarization. The older word is supernetting — a super-net, above the nets. 00:02:27.222 --> 00:02:32.762 Any of them is acceptable in an exam. Use the one the question uses. 00:02:32.812 --> 00:02:41.762 And notice who does it: whoever speaks for others. The ISP knows all six customers of that block, row by row. The rest of the Internet needs one line. 00:02:43.202 --> 00:02:52.152 Detail inside, silence outside — the campus trick from Session twelve, now load-bearing for the whole planet. 00:02:53.612 --> 00:02:59.392 Aggregation is easy to describe as compression, and it is not. 00:02:59.442 --> 00:03:08.392 The ISP holds six rows, one per customer. That is its private knowledge, and it needs every row of it — because once a packet has arrived at its door, it has to know which customer to hand it to. 00:03:14.292 --> 00:03:22.472 The rest of the world holds one. Not because it is being kept in the dark, but because the detail would tell it nothing it can act on. 00:03:22.522 --> 00:03:31.472 Every one of those six rows points at the same door. Knowing which customer changes nothing about where an outside router sends the packet. 00:03:32.562 --> 00:03:40.132 So aggregation is not compression. It is delegation. "Send it all to me, and I will sort out which customer." 00:03:40.182 --> 00:03:44.872 The ISP takes on the detail so that nobody else has to carry it. 00:03:44.922 --> 00:03:53.872 And the same move happens at every level: the regional provider does it to the ISPs, and the national does it to the regionals. 00:03:56.876 --> 00:04:00.636 Now the merge, with the audit written out. 00:04:00.686 --> 00:04:09.636 The four blocks: eleven dot ten dot zero dot zero slash twenty-four, dot one dot zero, dot two dot zero, dot three dot zero. 00:04:10.236 --> 00:04:14.646 These are last fortnight's blocks, read backwards. 00:04:14.696 --> 00:04:23.426 Check one: a power of two. Four of them, so the prefix can drop by exactly two — twenty-four down to twenty-two. 00:04:23.476 --> 00:04:29.516 Two, four, eight, sixteen. Never three, never five. 00:04:29.566 --> 00:04:36.786 Check two: contiguous. Zero, one, two, three. No gaps — and nothing inside that is not ours. 00:04:36.836 --> 00:04:43.246 Both halves of that sentence matter, and slide fourteen is the second one. 00:04:43.296 --> 00:04:52.246 Check three: aligned. The candidate is eleven dot ten dot zero dot zero slash twenty-two, and it must start on a multiple of its own size — a multiple of one thousand and twenty-four. It does. 00:04:55.916 --> 00:05:01.106 Same law as the allocation week, entirely unchanged. 00:05:01.156 --> 00:05:09.956 Three ticks. The four slash twenty-fours ARE one slash twenty-two — and it is the same block the ISP was granted in the first place. 00:05:10.006 --> 00:05:18.956 We have just run Session twelve's split in reverse. Those three checks take ten seconds once they are drilled. 00:05:19.340 --> 00:05:23.030 Now the reason underneath the arithmetic. 00:05:23.080 --> 00:05:32.030 Write the four third octets in binary: zero, one, two, three become eight zeros, then seven zeros and a one, then zero-one-zero, then zero-one-one. 00:05:33.680 --> 00:05:36.950 Twenty-two bits identical. Two bits varying. 00:05:37.000 --> 00:05:45.950 And those two bits take every value they can take: zero-zero, zero-one, one-zero, one-one. All four, with none missing. 00:05:47.540 --> 00:05:54.850 A bit that takes every value carries no information about which block, because it is every block. 00:05:54.900 --> 00:06:02.550 So stop paying for it. Stop carrying it. It cannot answer any question you would ask. 00:06:02.600 --> 00:06:09.860 Hand the two bits back to the host side, and one name — slash twenty-two — covers all four rooms. 00:06:09.910 --> 00:06:14.710 Aggregation is not a new mechanism. It is the borrowed bits going home. 00:06:14.760 --> 00:06:23.710 And that is your shortcut: count the identical leading bits, and you have the prefix without dividing anything. 00:06:24.407 --> 00:06:29.177 The three laws, stated cleanly. Write these down. 00:06:29.227 --> 00:06:35.837 One: a power-of-two count, of equal size. Two, four, eight, sixteen. 00:06:35.887 --> 00:06:41.517 Three blocks can never become one, whatever their addresses are. 00:06:41.567 --> 00:06:50.037 Two: contiguous, and all of it yours. No gaps — and nothing inside the merged range that belongs to somebody else. 00:06:50.087 --> 00:06:59.037 Three: aligned on the merged block's own size. The parent must start on a multiple of its own size, or it lies about its own front door. 00:06:59.837 --> 00:07:08.787 Pass all three and the blocks are siblings. Fail any one and they are merely neighbours — and "neighbour" is not a relationship a prefix can name. 00:07:09.567 --> 00:07:18.517 The next three slides break all three laws in turn, and the third is broken by a pair that looks innocent. 00:07:20.493 --> 00:07:26.273 Forty-two seconds, and the whole session — including the bill at the end. 00:07:26.323 --> 00:07:35.193 There is last session's map: six customers, one unsold hole, all inside eleven dot ten dot zero dot zero slash twenty-two. 00:07:35.243 --> 00:07:42.263 Subnetting asked how to cut it up. Aggregation asks what the world outside needs to know about it. 00:07:42.313 --> 00:07:51.263 The naive answer is six lines, in every router on Earth. Six prefixes, six next hops — and all six point at exactly the same place. 00:07:51.993 --> 00:07:58.253 That is the definition of redundant, and it is the shape of a problem that does not scale. 00:07:58.303 --> 00:08:05.903 Now the four slash twenty-fours in binary. Twenty-two bits identical, and two bits taking every value they can take. 00:08:05.953 --> 00:08:14.443 Bits that take every value distinguish nothing — so hand them back, and one name covers all four. 00:08:14.493 --> 00:08:23.443 One line. Eleven dot ten dot zero dot zero slash twenty-two, to this ISP. Outside the ISP: one entry. Inside: six. 00:08:24.083 --> 00:08:29.083 Detail does not travel. That is the whole idea. 00:08:29.133 --> 00:08:38.083 And here is the two directions side by side. Subnetting walks down the tree and lengthens the prefix; aggregation walks up it and shortens the prefix. 00:08:39.993 --> 00:08:45.783 Same tree, same arithmetic, and only a new reason to walk it. 00:08:45.833 --> 00:08:54.593 Then it compounds. Sixty-four customer slash twenty-twos become one slash sixteen; the ISP's provider does the same to the ISP. 00:08:54.643 --> 00:09:03.593 One entry, in every router in the world, for all of a local ISP's customers — and a global table of about a million rows instead of one row per customer network on the planet. 00:09:07.323 --> 00:09:14.803 And there is the bill. The aggregate speaks for every address inside it, including the customer who left last month. 00:09:14.853 --> 00:09:23.803 It becomes a white lie, and the cure is not to withdraw it. Section four is nothing but that sentence. 00:09:24.487 --> 00:09:27.347 Now the numbers on that saving. 00:09:27.397 --> 00:09:36.347 Without aggregation: one row per customer block, in every router on Earth. And all six point at exactly the same next hop. 00:09:36.777 --> 00:09:43.677 With aggregation: eleven dot ten dot zero dot zero slash twenty-two, to this ISP. One line. 00:09:43.727 --> 00:09:51.247 And the six stay inside the ISP's own router, where they are the only place they are useful. 00:09:51.297 --> 00:10:00.247 The saving is not a one-off. Every ISP does it, so the table shrinks by the same factor everywhere — and then it compounds: local into regional, regional into national. 00:10:04.167 --> 00:10:13.117 Forouzan's own sentence, and it is worth quoting exactly: there is only ONE entry, in every router in the world, for all of a local ISP's customers. 00:10:14.977 --> 00:10:19.907 That is the reason the global table stays small enough to search. 00:10:19.957 --> 00:10:25.657 So the global table is roughly a million rows, and not one row per network on the planet. 00:10:25.707 --> 00:10:34.657 The Internet survives on aggregated silence. One prefix, one next hop, and the detail never travels — which is what a hierarchy IS, not a routing trick. 00:10:39.520 --> 00:10:44.040 Checkpoint one. Paper before answers. 00:10:44.090 --> 00:10:53.040 One. Run the three checks on eleven dot ten dot zero dot zero slash twenty-four through eleven dot ten dot three dot zero slash twenty-four, and name the merged block. 00:10:56.840 --> 00:11:04.060 Two. Write the four third octets in binary and say how many leading bits are identical. 00:11:04.110 --> 00:11:11.570 Three. In one sentence: why does the rest of the Internet not want the ISP's six rows? 00:11:11.620 --> 00:11:20.570 One. Four of them, which is a power of two. Contiguous, dot zero to dot three with no gaps. And zero over four is zero, so the start is aligned on one thousand and twenty-four. The merged block is eleven dot ten dot zero dot zero slash twenty-two. 00:11:29.430 --> 00:11:38.220 Two. Twenty-two identical leading bits — so the prefix is slash twenty-two, and you got there without dividing anything. 00:11:38.270 --> 00:11:47.220 Three. Because all six rows point at the same next hop. The detail cannot change what an outside router would do, so carrying it is pure cost. 00:11:49.954 --> 00:11:52.694 Section two. When the glue fails. 00:11:52.744 --> 00:12:01.694 Any two neighbouring blocks do not become one. Break a law and the answer is not "aggregate anyway" — it is "advertise two lines instead of one". 00:12:05.676 --> 00:12:10.686 The first refusal you can make without looking at a single address. 00:12:10.736 --> 00:12:19.686 Three slash twenty-fours: ten dot five dot four, dot five, dot six. All ours, all adjacent, all the same size. 00:12:19.866 --> 00:12:22.836 And they cannot become one line. 00:12:22.886 --> 00:12:30.526 Three times two fifty-six is seven hundred and sixty-eight, and that is not a power of two. No prefix has that size. 00:12:30.576 --> 00:12:34.176 There is no slash twenty-three-and-a-half. 00:12:34.226 --> 00:12:43.176 So aggregate what you can. Ten dot five dot four dot zero slash twenty-three covers dot four and dot five — four over two is two, whole. 00:12:44.466 --> 00:12:50.656 And ten dot five dot six dot zero slash twenty-four keeps its own line. 00:12:50.706 --> 00:12:59.536 Two entries. Not three, and not one. Partial aggregation is still aggregation, and it is the right answer rather than a failure. 00:12:59.586 --> 00:13:08.536 And do not force it: a slash twenty-two over dot four to dot seven would also claim dot seven, which this ISP does not own. That is refusal two. 00:13:12.728 --> 00:13:18.298 Refusal two, and it has a consequence most people do not expect. 00:13:18.348 --> 00:13:26.508 Your blocks are dot zero, dot one and dot three of some slash twenty-two — and dot two was sold to another ISP. 00:13:26.558 --> 00:13:35.508 A slash twenty-two over zero to three also claims two. There is no way to name dot zero, dot one and dot three and skip dot two: a prefix is an unbroken range or it is nothing. 00:13:40.178 --> 00:13:44.408 And claiming dot two is not untidy. It is theft of traffic. 00:13:44.458 --> 00:13:53.408 You would be advertising another ISP's customer, and packets for them would arrive at your door — which is an outage for somebody else, caused by you. 00:13:54.448 --> 00:14:03.398 The honest advertisement is two lines: eleven dot ten dot zero dot zero slash twenty-three for dot zero and dot one, and eleven dot ten dot three dot zero slash twenty-four on its own — because dot three is odd and can pair with nothing. 00:14:09.908 --> 00:14:18.858 "Advertise only what you own, all of it" is one sentence and two separate rules. Both of them are marked. 00:14:20.459 --> 00:14:27.539 And now the one that catches everyone. If you learn one aggregation fact this term, learn this. 00:14:27.589 --> 00:14:35.839 Ten dot five dot five dot zero and ten dot five dot six dot zero. Adjacent. Two of them. The same size. 00:14:35.889 --> 00:14:43.249 Every instinct says these merge. They do not — and they never will, at any prefix length. 00:14:43.299 --> 00:14:48.369 A slash twenty-three must start on an even third octet, and five is odd. 00:14:48.419 --> 00:14:55.089 Run the block's own mask over its own first address: five AND two-five-four is four. 00:14:55.139 --> 00:15:02.479 So "ten dot five dot five dot zero slash twenty-three" claims to start at ten dot five dot four dot zero. 00:15:02.529 --> 00:15:11.479 A block that lies about its own front door is not a block. That is the same sentence as the allocation fortnight, word for word. 00:15:11.629 --> 00:15:20.579 This is the most common error on this topic. Learn to spot it from the odd octet alone — you should not need to do any arithmetic to feel suspicious. 00:15:20.969 --> 00:15:29.919 What you actually hold is two slash twenty-fours, and two lines, permanently. The tree on the next slide shows exactly why. 00:15:33.055 --> 00:15:40.065 Forty-two seconds. The three laws, all three broken, and then the reverse read. 00:15:40.115 --> 00:15:47.805 The three tests: a power-of-two count, contiguous and all yours, and aligned on the merged block's own size. 00:15:47.855 --> 00:15:55.525 Pass all three and the blocks are siblings. Fail one and they are merely neighbours. 00:15:55.575 --> 00:16:02.425 Three blocks. Three is not a power of two, so no prefix has that size — refused without looking at a single address. 00:16:02.475 --> 00:16:11.285 Aggregate the aligned pair as a slash twenty-three, and let the third keep its own line. Two entries, not three. 00:16:11.335 --> 00:16:20.285 Now the gap. A slash twenty-two over dot zero, dot one and dot three also claims dot two — and dot two belongs to another ISP. 00:16:21.045 --> 00:16:28.965 Advertise only what you own, all of it. The honest answer is two lines, and never a slash twenty-two. 00:16:29.015 --> 00:16:35.365 And the famous one. Adjacent, two of them, the same size — and unmergeable forever. 00:16:35.415 --> 00:16:43.595 Five AND two-five-four is four, so the name lies about its own front door. What you hold is two slash twenty-fours. 00:16:43.645 --> 00:16:50.525 Draw the tree and it stops being a trick. Four and five hang off one parent; six and seven off another. 00:16:50.575 --> 00:16:59.525 Five and six hang off two different parents — so there is no node in the tree that covers exactly those two. Only parents are advertisable. 00:17:00.555 --> 00:17:09.505 Then the reverse read. Two hundred dot sixteen dot eight dot zero slash twenty-one is two thousand and forty-eight addresses — eight slash twenty-fours. 00:17:10.645 --> 00:17:18.155 Start at the advertised first address and count: third octet eight through fifteen, and stop. 00:17:18.205 --> 00:17:26.895 And could the same eight be called two hundred dot sixteen dot nine dot zero slash twenty-one? Nine AND two-four-eight is eight. No. 00:17:26.945 --> 00:17:35.895 A block's name is never a choice. The arithmetic chooses it, and there is exactly one legal answer. 00:17:36.677 --> 00:17:42.747 Now the tree, because it settles these cases faster than the arithmetic does. 00:17:42.797 --> 00:17:51.557 Draw two parents: ten dot five dot four dot zero slash twenty-three, and ten dot five dot six dot zero slash twenty-three. 00:17:51.607 --> 00:17:58.737 Under the first hang dot four and dot five. Under the second hang dot six and dot seven. 00:17:58.787 --> 00:18:07.737 Dot four and dot five: same parent. Siblings. Mergeable into ten dot five dot four dot zero slash twenty-three. 00:18:08.127 --> 00:18:17.077 Legal — and notice that the merge has a name that already existed in the tree. You are not inventing a block; you are naming a node. 00:18:17.367 --> 00:18:22.597 Dot five and dot six: different parents. Neighbours, and nothing more. 00:18:22.647 --> 00:18:30.137 Never mergeable — because there is no node in the tree that covers exactly those two and nothing else. 00:18:30.187 --> 00:18:35.517 Dot six and dot seven: same parent again. Siblings, and mergeable. 00:18:35.567 --> 00:18:40.547 Notice how quickly the tree answers what the arithmetic laboured over. 00:18:40.597 --> 00:18:46.627 And there is the rule: only parents are advertisable, because only a parent has a prefix. 00:18:46.677 --> 00:18:55.627 So draw the tree whenever the arithmetic feels slippery. Every aggregation question is really a question about the tree — do these blocks hang off one node, or two? 00:19:00.239 --> 00:19:06.099 Four cases. Run all of them in your head before each answer appears. 00:19:06.149 --> 00:19:15.099 A: ten dot five dot four dot zero slash twenty-four and ten dot five dot five dot zero slash twenty-four. Siblings, and four over two is two — legal. Ten dot five dot four dot zero slash twenty-three. 00:19:21.149 --> 00:19:30.099 B: ten dot five dot five and ten dot five dot six. The trap you just met. Five is odd. Refused, forever. 00:19:31.079 --> 00:19:40.029 C: three slash twenty-fours — dot four, dot five, dot six. Refused before you even look at the addresses, because three is not a power of two. 00:19:41.909 --> 00:19:47.099 Aggregate dot four and dot five, and leave dot six alone. 00:19:47.149 --> 00:19:56.099 D: eleven dot ten dot zero dot zero slash twenty-three and eleven dot ten dot two dot zero slash twenty-three. The two halves from the subnetting week. 00:19:57.339 --> 00:20:05.789 Glue them and you are holding eleven dot ten dot zero dot zero slash twenty-two again — zero over four is zero, legal. 00:20:05.839 --> 00:20:14.789 D is last fortnight's split, run backwards. B is the case that costs marks in an exam. 00:20:15.006 --> 00:20:17.206 Checkpoint two. 00:20:17.256 --> 00:20:26.206 One. Why can ten dot five dot five dot zero slash twenty-four and ten dot five dot six dot zero slash twenty-four never be merged? Show the arithmetic in one line. 00:20:29.986 --> 00:20:38.936 Two. Three consecutive slash twenty-fours are all yours. What is the best advertisement, and how many lines is it? 00:20:39.396 --> 00:20:48.346 Three. Your blocks are dot zero, dot one and dot three of some slash twenty-two, and dot two belongs to another ISP. What may you advertise? 00:20:50.776 --> 00:20:59.726 One. A slash twenty-three must start on an even third octet. Five AND two-five-four is four, so "ten dot five dot five dot zero slash twenty-three" claims to start at ten dot five dot four dot zero — it lies about its own front door. Refused at any prefix length. 00:21:09.306 --> 00:21:18.256 Two. Two lines: the aligned pair as a slash twenty-three, and the odd one out as a slash twenty-four. Three is not a power of two, so one line is impossible. 00:21:20.656 --> 00:21:29.606 Three. Eleven dot ten dot zero dot zero slash twenty-three and eleven dot ten dot three dot zero slash twenty-four — two lines. Never a slash twenty-two, because that would also claim dot two, which is not yours to claim. 00:21:38.406 --> 00:21:41.106 Section three. Read it backwards. 00:21:41.156 --> 00:21:50.106 An operator reads advertisements all day and asks one question of each: exactly which blocks does this line claim to own? The answer is arithmetic, not judgement. 00:21:55.225 --> 00:22:03.305 One line on the wire: two hundred dot sixteen dot eight dot zero slash twenty-one. What is it claiming? 00:22:03.355 --> 00:22:11.045 A slash twenty-one is two to the eleven — two thousand and forty-eight addresses. Which is eight slash twenty-fours. 00:22:11.095 --> 00:22:16.265 So the line claims eight blocks. No more, and no fewer. 00:22:16.315 --> 00:22:25.265 Start at the advertised first address and count: third octet eight, nine, ten, eleven, twelve, thirteen, fourteen, fifteen. And stop. 00:22:26.455 --> 00:22:33.745 That is the whole method, and it takes about four seconds once you trust it. 00:22:33.795 --> 00:22:38.135 And notice what the advertisement IS: a claim to own all eight. 00:22:38.185 --> 00:22:45.735 If you own only seven of them, this line is a lie — and it will attract traffic you cannot deliver. 00:22:45.785 --> 00:22:51.125 It is also a promise to accept all eight, including the block you have not sold yet. 00:22:51.175 --> 00:23:00.125 Silence about the empty half is part of the deal. Exams ask what a line claims; operations cares about what it promises. 00:23:02.121 --> 00:23:07.411 And now the second half of the drill, which is the half that carries the law. 00:23:07.461 --> 00:23:13.601 Could the same eight blocks be called two hundred dot sixteen dot nine dot zero slash twenty-one? 00:23:13.651 --> 00:23:22.601 Run the mask over the proposed name. A slash twenty-one mask keeps the top five bits of the third octet: nine AND two-four-eight. Which is eight, not nine. 00:23:25.551 --> 00:23:32.121 So the name claims to start at two hundred dot sixteen dot eight dot zero — which is not where it says it starts. 00:23:32.171 --> 00:23:37.311 Same disease as the five-and-six trap, seen from the other side. 00:23:37.361 --> 00:23:44.141 A block's name is never a choice. The arithmetic chooses it, and there is exactly one legal answer. 00:23:44.191 --> 00:23:49.021 "Which name is nicer" is not a question anyone gets to ask. 00:23:49.071 --> 00:23:58.021 And notice that the same test works in both directions. Forwards it decides whether a merge is legal; backwards it decides whether a name is honest. 00:23:58.511 --> 00:24:04.631 One division, and one AND — exactly as it has been since Session ten. 00:24:04.681 --> 00:24:10.731 So check every block against its own mask — including the one you have just invented by merging. 00:24:10.781 --> 00:24:19.731 That single habit catches every aggregation error there is. If a name survives its own mask, it is a block. If it does not, it is a claim about somewhere else entirely. 00:24:24.811 --> 00:24:31.191 Forouzan's own figure, walked slowly, because the next section is built on it. 00:24:31.241 --> 00:24:37.561 R1 serves four organisations, each a slash twenty-six of one forty dot twenty-four dot seven dot zero. 00:24:37.611 --> 00:24:46.561 Four rows: dot zero, dot sixty-four, dot one twenty-eight and dot one ninety-two. That is R1's private knowledge, and it needs all of it. 00:24:49.581 --> 00:24:57.331 To R2 it says one sentence: one forty dot twenty-four dot seven dot zero slash twenty-four, send it all to me. 00:24:57.381 --> 00:25:05.791 And R2's complete table for four whole organisations is one row plus a default. Not four rows. One. 00:25:05.841 --> 00:25:12.441 Now multiply by every ISP on Earth. Local into regional, regional into national. 00:25:12.491 --> 00:25:21.171 One entry in every router in the world, for all of a local ISP's customers — and a global table of about a million rows. 00:25:21.221 --> 00:25:30.171 Table search is per-packet work, at line rate. A table of millions does not merely cost memory; it costs time on every single packet, forever. 00:25:35.491 --> 00:25:43.231 One cell per slash twenty-four. Click the ones the ISP owns, and the three laws are checked live. 00:25:43.281 --> 00:25:51.781 State one: dot four and dot five. All three tiles green — contiguous, two of them, and four over two is two. 00:25:51.831 --> 00:25:58.331 Two lines become one: ten dot five dot four dot zero slash twenty-three. 00:25:58.381 --> 00:26:06.841 State two is the trap. Shift the window by one and everything about it still looks right: adjacent, two, same size. 00:26:06.891 --> 00:26:15.121 And the third tile goes red. Five over two is two point five. Two entries, and no aggregation at all. 00:26:15.171 --> 00:26:23.531 State three: three blocks. The second tile goes red before the addresses matter at all — three is not a power of two. 00:26:23.581 --> 00:26:32.531 And notice the verdict: partial aggregation, two entries. The machine calls that the right answer, not a failure. 00:26:33.281 --> 00:26:42.231 State four: dot zero, dot one and dot three, with dot two missing. Contiguity fails, and the machine lists exactly which cell is missing. 00:26:42.701 --> 00:26:49.431 The honest advertisement is two lines, and the machine builds them for you. 00:26:49.481 --> 00:26:57.861 State five: eight in a row from dot eight. Eight over eight is one — whole. One line, a slash twenty-one. 00:26:57.911 --> 00:27:05.781 And there is the binary panel: count the identical leading bits and you get the same prefix without dividing. 00:27:05.831 --> 00:27:13.201 State six is last fortnight's four slash twenty-fours, glued back into the slash twenty-two the ISP started with. 00:27:13.251 --> 00:27:19.891 Three green tiles, one line, and the binary panel showing twenty-two identical bits. 00:27:19.941 --> 00:27:28.891 Open it yourself and try to break it. Click any set of cells you like — the three laws are checked live, and whatever cannot become one line is decomposed into the smallest honest set of lines instead. 00:27:34.445 --> 00:27:36.725 Checkpoint three. 00:27:36.775 --> 00:27:45.725 One. Two hundred dot sixteen dot eight dot zero slash twenty-one is advertised. List the slash twenty-fours it claims, and say how many. 00:27:48.485 --> 00:27:56.995 Two. Show in one line why two hundred dot sixteen dot nine dot zero slash twenty-one cannot name that same set. 00:27:57.045 --> 00:28:05.995 Three. R1 has four slash twenty-six customers inside one forty dot twenty-four dot seven dot zero slash twenty-four. How many rows does R2 hold, and why? 00:28:07.535 --> 00:28:16.485 One. Eight slash twenty-fours: third octet eight through fifteen. A slash twenty-one is two thousand and forty-eight addresses, which is eight blocks of two fifty-six. 00:28:21.275 --> 00:28:30.225 Two. Nine AND two-four-eight is eight. The name claims to start at two hundred dot sixteen dot eight dot zero, so it lies about its own front door — and a block that does that is not a block. 00:28:34.475 --> 00:28:43.425 Three. One, plus a default. R1 advertises the slash twenty-four and keeps the four slash twenty-sixes to itself, because as far as R2 is concerned all four point at the same door. 00:28:49.073 --> 00:28:51.243 Section four. The bill. 00:28:51.293 --> 00:29:00.243 So far aggregation has sounded free: say less, know everything. Time to meet the customer who moved. 00:29:01.164 --> 00:29:07.744 Before the bill, one slide on why the saving mattered enough to build a hierarchy around. 00:29:07.794 --> 00:29:13.074 Remember processing delay from the performance lecture? Table search is per-packet work. 00:29:13.124 --> 00:29:19.014 Every row is a candidate to check, for every packet, at line rate. 00:29:19.064 --> 00:29:24.984 So a big table costs time, not just memory — and it costs it on every single packet, forever. 00:29:25.034 --> 00:29:30.914 That is a very different kind of expensive from "we need more RAM". 00:29:30.964 --> 00:29:38.694 Geographical routing pushes the same idea all the way to continents. Outside Europe, one row says "Europe". 00:29:38.744 --> 00:29:41.684 The address plan is the map. 00:29:41.734 --> 00:29:50.684 And aggregation is what keeps the map foldable. A million rows fits in fast memory and is searchable in time. Sixteen million would be neither. 00:29:51.244 --> 00:30:00.194 Which is why address planning is not bureaucracy. A tidy plan is a small table, and a small table is a fast Internet. 00:30:02.391 --> 00:30:06.761 Now the bill. It arrives as a cancelled contract. 00:30:06.811 --> 00:30:15.761 Organisation four cancels the contract and moves to an ISP across town — and one forty dot twenty-four dot seven dot one ninety-two slash twenty-six goes with them. 00:30:17.121 --> 00:30:25.801 Nobody renumbers. Renumbering a live network means touching every machine on it, so it is simply not on the table. 00:30:25.851 --> 00:30:33.861 R1 still advertises one forty dot twenty-four dot seven dot zero slash twenty-four — and for organisations one to three that is still perfectly true. 00:30:33.911 --> 00:30:35.891 But it is now false about the fourth. 00:30:35.941 --> 00:30:44.891 So a second voice appears: one forty dot twenty-four dot seven dot one ninety-two slash twenty-six, via R3 — organisation four's new home. 00:30:45.801 --> 00:30:49.751 And both are telling the truth as they know it. 00:30:49.801 --> 00:30:58.751 Now a packet for one forty dot twenty-four dot seven dot two hundred. AND with the slash twenty-four mask gives dot seven dot zero — a match. 00:31:01.721 --> 00:31:08.461 AND with the slash twenty-six mask: two hundred AND one ninety-two is one ninety-two — also a match. 00:31:08.511 --> 00:31:15.521 Two matches. And no contradiction, provided there is a tie-breaker. 00:31:15.571 --> 00:31:24.521 The table is searched longest mask first. The slash twenty-six is longer — more specific — so it speaks first, and organisation four's traffic turns toward R3. 00:31:26.331 --> 00:31:33.851 Organisations one to three still ride the slash twenty-four. The aggregate did not have to be torn up. 00:31:33.901 --> 00:31:42.851 The hole is a longer prefix punched through it, and longest-first does the rest. HOW a router runs that contest is next session's entire lecture. 00:31:46.433 --> 00:31:50.653 Name what has just happened, because it is deliberate. 00:31:50.703 --> 00:31:56.813 The slash twenty-four says "every address in here is mine". And it is wrong about sixty-four of them. 00:31:56.863 --> 00:32:03.523 Not maliciously. The world simply moved on, and nobody withdrew the sentence. 00:32:03.573 --> 00:32:11.963 And the cure is not to withdraw the aggregate. That would put three innocent organisations back into the global table as separate rows. 00:32:12.013 --> 00:32:16.663 The lie is cheaper than the truth, if you can correct it locally. 00:32:16.713 --> 00:32:22.233 So you punch a longer prefix through it. One extra row, worldwide, instead of three. 00:32:22.283 --> 00:32:27.903 And it only works because every router on Earth agrees to let the most specific voice win. 00:32:27.953 --> 00:32:36.903 Write the trade in one line: aggregation buys silence, and longest-prefix match pays for it. That is why the rule must exist. 00:32:39.666 --> 00:32:48.616 One more piece of content before the hook, and it is content rather than trivia: next session's DHCP ladder cites the top two rows by name. 00:32:50.756 --> 00:32:58.386 Zero dot zero dot zero dot zero: this host. The source address of a machine that does not yet know its own name. 00:32:58.436 --> 00:33:04.916 You will watch DHCP use it next session, and it will make complete sense when you do. 00:33:04.966 --> 00:33:11.866 All ones: limited broadcast. Everyone on THIS network — and routers refuse to carry it further. 00:33:11.916 --> 00:33:16.986 It is not a way to reach the Internet. It is a way to shout in one room. 00:33:17.036 --> 00:33:23.766 One twenty-seven dot anything: loopback. A letter you post to yourself; it never touches the wire. 00:33:23.816 --> 00:33:30.006 And it is the classic error — arithmetic landing here and being written down anyway. 00:33:30.056 --> 00:33:39.006 The three private blocks: ten slash eight, one seventy-two dot sixteen slash twelve, and one ninety-two dot one sixty-eight slash sixteen. 00:33:40.156 --> 00:33:49.106 Free inside any site, invisible to the Internet — and the raw material NAT works with next session. Your own laptop is almost certainly using one right now. 00:33:51.906 --> 00:34:00.856 One sixty-nine dot two five four: the address a host gives itself when DHCP never answered. Recognise it and you have diagnosed the fault from across the room. 00:34:03.376 --> 00:34:09.166 And two twenty-four slash four: multicast — one sender to a subscribed group. 00:34:09.216 --> 00:34:18.166 The exam rule: if your block arithmetic ever lands an answer inside one of these corners, the arithmetic may be perfect and the answer is still wrong. Re-read the question. 00:34:24.235 --> 00:34:32.105 Forouzan's figure, walked end to end — with the two tables side by side and a counter on each. 00:34:32.155 --> 00:34:38.435 State one: R1's four slash twenty-six customers, and the count says four on both sides. 00:34:38.485 --> 00:34:46.295 If R1 advertised what it knows, every router on Earth would carry four rows that all point at the same door. 00:34:46.345 --> 00:34:55.295 State two: R1 advertises the parent. Left-hand count still four — the detail lives inside R1. Right-hand count: one, plus a default. 00:34:57.415 --> 00:35:05.395 Detail inside, silence outside, and nothing about the four slash twenty-sixes ever leaves R1. 00:35:05.445 --> 00:35:10.385 State three is Forouzan's sentence made into a claim about the whole planet. 00:35:10.435 --> 00:35:19.075 Local into regional into national — and a global table of about a million rows instead of one per network on Earth. 00:35:19.125 --> 00:35:26.335 State four: organisation four moves out, and its row goes amber. Left-hand count drops to three. 00:35:26.385 --> 00:35:33.695 And R1's aggregate is still advertised — now true for three customers and false for the fourth. 00:35:33.745 --> 00:35:42.665 State five: R2's new reality. The old aggregate, still true for orgs one to three, and a second voice for the block that left. 00:35:42.715 --> 00:35:50.745 Right-hand count: two. One aggregate, plus one more-specific punched through it. 00:35:50.795 --> 00:35:56.985 State six is the packet. Destination one forty dot twenty-four dot seven dot two hundred, and both ANDs written out. 00:35:57.035 --> 00:36:04.045 Twenty-four bits matches. Twenty-six bits matches, and is longer. Via R3. 00:36:04.095 --> 00:36:10.985 And the last state is the sentence: aggregation buys silence, and longest-prefix match pays for it. 00:36:11.035 --> 00:36:19.985 Open it and step through the two counters yourself — watch them separate, and then watch one of them climb back by one. 00:36:20.993 --> 00:36:28.813 Back to the question from slide two. Both halves now have their derivations behind them. 00:36:28.863 --> 00:36:33.643 What does the ISP say? One line: eleven dot ten dot zero dot zero slash twenty-two. 00:36:33.693 --> 00:36:41.213 Four slash twenty-fours, six customers, three weeks of carpentry — compressed to five syllables. 00:36:41.263 --> 00:36:49.773 And everyone at every level does the same, so the planet's core routers hold about a million rows instead of one row per customer network. 00:36:49.823 --> 00:36:52.313 That is the first half. 00:36:52.363 --> 00:36:54.433 And the cost? Precision. 00:36:54.483 --> 00:37:03.253 The aggregate speaks for every address inside it — including the customer who left last month. It becomes a white lie. 00:37:03.303 --> 00:37:12.253 And the cure is not to withdraw it. The cure is a longer prefix punched through it — which only works because every router in the world agrees to let the most specific voice win. 00:37:13.933 --> 00:37:22.883 So: aggregation buys silence, and longest-prefix match pays for it. Next session you watch a router execute that rule, four ANDs at a time. 00:37:26.327 --> 00:37:30.887 The trade once more, in the form to write in an exam. 00:37:30.937 --> 00:37:39.887 What silence buys: a global table of about a million rows instead of one row per customer network on Earth — and therefore a table that fits in fast memory and can be searched at line rate, per packet, forever. 00:37:45.757 --> 00:37:54.707 What silence costs: precision. Every aggregate is slightly out of date, and some are wrong about a customer who left. The world does not stop to correct them. 00:37:57.827 --> 00:38:06.777 And who pays: longest-prefix match. It is the mechanism that lets a wrong-but-useful aggregate and a right-but-narrow exception live in the same table without contradiction. 00:38:08.237 --> 00:38:17.187 That is why the rule must exist — not as a convention somebody chose, but as the only way the two halves of this trade can coexist. 00:38:20.027 --> 00:38:24.517 Checkpoint four, and this is the last one. 00:38:24.567 --> 00:38:33.517 One. Organisation four moved. Why does R1 not simply withdraw its slash twenty-four and advertise three slash twenty-sixes instead? 00:38:35.077 --> 00:38:44.027 Two. A packet arrives for one forty dot twenty-four dot seven dot two hundred. Show both ANDs, and say which row wins. 00:38:44.597 --> 00:38:53.547 Three. Your subnetting arithmetic produces the block one twenty-seven dot four dot zero dot zero slash sixteen. What has gone wrong? 00:38:54.397 --> 00:39:03.347 One. Because that would put three separate rows into every router in the world instead of one. The aggregate plus one exception is two rows; withdrawing it is three. Silence is worth keeping. 00:39:07.427 --> 00:39:16.377 Two. Two hundred AND two five five two five five two five five zero is one forty dot twenty-four dot seven dot zero — a match. Two hundred AND two five five two five five two five five one ninety-two is one forty dot twenty-four dot seven dot one ninety-two — also a match. The slash twenty-six is longer, so it wins, and the packet goes via R3. 00:39:29.757 --> 00:39:38.707 Three. One twenty-seven dot anything is loopback. The arithmetic may be flawless, but the answer lands in a reserved corner, so the question has been misread. Go back and check the parent block. 00:39:49.333 --> 00:39:52.383 Five ways to lose these marks. 00:39:52.433 --> 00:39:57.353 Wrong: they are adjacent and the same size, so they merge. 00:39:57.403 --> 00:40:05.323 Right: only siblings merge. Check the merged block against its OWN mask — five AND two-five-four is four. 00:40:05.373 --> 00:40:10.363 Wrong: three blocks, so advertise a slash twenty-two and cover them. 00:40:10.413 --> 00:40:19.363 Right: advertise only what you own, all of it. A slash twenty-two over three blocks claims a fourth that is not yours. 00:40:20.213 --> 00:40:24.733 Wrong: aggregating hides the detail, so the detail is lost. 00:40:24.783 --> 00:40:32.753 Right: hidden is not lost. The detail lives inside the ISP, which is the only place it is useful. 00:40:32.803 --> 00:40:37.053 Wrong: the aggregate is wrong now, so withdraw it. 00:40:37.103 --> 00:40:43.173 Right: punch a longer prefix through it. One extra row worldwide beats three. 00:40:43.223 --> 00:40:52.053 Wrong: my arithmetic gives one sixty-nine dot two five four dot three dot zero slash twenty-four, so that is the answer. 00:40:52.103 --> 00:41:01.053 Right: reserved corners never appear in a legal answer. The arithmetic is fine and the reading was not. 00:41:02.213 --> 00:41:07.293 I said at the start there was no new arithmetic. Here is the proof. 00:41:07.343 --> 00:41:15.003 The arithmetic is Session ten's: one AND, one division, one comparison against the block's own mask. 00:41:15.053 --> 00:41:18.923 You have run it for three weeks in the other direction. 00:41:18.973 --> 00:41:24.983 The law is Session fourteen's alignment rule: a block must start on a multiple of its own size. 00:41:25.033 --> 00:41:31.563 Applied to a merge, that single rule produces all three conditions — count, contiguity and alignment fall out of it. 00:41:31.613 --> 00:41:38.183 The only new thing is the reason. You are no longer cutting a block to fit customers. 00:41:38.233 --> 00:41:45.263 You are choosing what the rest of the world is allowed to know — and that is a different kind of decision. 00:41:45.313 --> 00:41:54.263 Which is why this session is short on technique and long on consequences. The consequence IS the content. 00:41:55.013 --> 00:41:58.913 Four things you should be able to do now. 00:41:58.963 --> 00:42:07.913 One: run the three checks on any set of blocks in about ten seconds — power-of-two count, contiguous and all yours, aligned on the merged size. 00:42:09.973 --> 00:42:18.923 Two: spot the five-and-six trap from the odd octet alone, and say why it fails in one line of arithmetic, without drawing anything. 00:42:20.193 --> 00:42:29.143 Three: read an advertisement backwards and list exactly what it claims. A slash twenty-one is eight slash twenty-fours; count from the advertised first address and stop. 00:42:33.673 --> 00:42:40.793 Four: state the trade in one sentence — aggregation buys silence, and longest-prefix match pays for it. 00:42:40.843 --> 00:42:49.793 Homework is the four glue cases with proofs, plus the reverse drill. Reading: eighteen point five, up to label switching. 00:42:52.191 --> 00:42:56.041 Three things before the next session. 00:42:56.091 --> 00:43:03.581 One: the four glue cases, with proofs. Not "legal" or "illegal" — the line of arithmetic that settles it. 00:43:03.631 --> 00:43:11.061 A proof here is one division and one AND, so there is no excuse for a bare verdict. 00:43:11.111 --> 00:43:19.131 Two: the reverse drill. One seventy-two dot twenty dot sixteen dot zero slash twenty-two into its four slash twenty-fours. 00:43:19.181 --> 00:43:28.131 And then the harder half: could that same set be named one seventy-two dot twenty dot seventeen dot zero slash twenty-two? Run the mask over the name and see. 00:43:31.151 --> 00:43:37.981 Three: learn the reserved corners. Next session's DHCP ladder cites the top two rows by name. 00:43:38.031 --> 00:43:45.011 If zero dot zero dot zero dot zero and all-ones are not automatic by then, the ladder will not land. 00:43:45.061 --> 00:43:54.011 And next session's question: four rules all match one packet, and the router does not vote. The tie-breaker, plus DHCP and NAT. 00:43:58.120 --> 00:44:05.700 One last thing, because this question does not always arrive dressed as "aggregate these blocks". 00:44:05.750 --> 00:44:11.280 Disguise one: "summarise these routes". That is a merge question, forwards. 00:44:11.330 --> 00:44:14.950 Run the three checks and name the parent. 00:44:15.000 --> 00:44:21.020 Disguise two: "which blocks does this advertisement claim?" The same question, backwards. 00:44:21.070 --> 00:44:28.630 Size over two fifty-six gives the count; then count up from the advertised first address, and stop. 00:44:28.680 --> 00:44:34.650 Disguise three: "is this a valid CIDR block?" That is the alignment law, alone. 00:44:34.700 --> 00:44:41.840 Run the block's own mask over its own first address and see whether the answer is where it says it is. 00:44:41.890 --> 00:44:50.840 Three wordings, one law: a block must start on a multiple of its own size, and it must contain exactly what it claims. 00:44:53.051 --> 00:44:54.851 That is Session sixteen. 00:44:54.901 --> 00:45:01.991 Detail inside, one line outside. Only siblings merge — and the longest prefix cleans up the lies. 00:45:02.041 --> 00:45:09.221 Three checks: a power-of-two count, contiguous and all yours, aligned on the merged size. Ten seconds, every time. 00:45:09.271 --> 00:45:18.021 The refusal exams love: adjacent is not the same as sibling. Five AND two-five-four is four, and no amount of adjacency fixes that. 00:45:18.071 --> 00:45:26.241 And the trade, which is the sentence to carry out of here: aggregation buys silence, and longest-prefix match pays for it. 00:45:26.291 --> 00:45:35.241 Next session the longest prefix does the paying, in front of you, four ANDs at a time — and we finally find out where addresses come from, and why your watch has been lying to you about having one. 00:45:40.001 --> 00:45:44.798 I will see you there.