WEBVTT 00:00:00.000 --> 00:00:03.690 Welcome back to CSE 316 — Data Communication and Networking. 00:00:03.740 --> 00:00:12.270 This is the detailed video version of Session eighteen, and it goes somewhere the addressing arc did not. 00:00:12.320 --> 00:00:18.270 Last session you watched a router referee the longest-prefix contest against a million rows — for one packet. 00:00:18.320 --> 00:00:27.270 In the core of the Internet, the big routers that carry your traffic between cities mostly do not do that. They stopped reading addresses entirely. 00:00:28.300 --> 00:00:37.250 Today: the virtual-circuit approach, taught in full — the road the Internet did not take in nineteen seventy — and then its modern comeback, running underneath the datagram Internet. 00:00:39.880 --> 00:00:45.650 The fork was never resolved. It was layered. 00:00:45.700 --> 00:00:52.270 The question this session answers, and it leans on both of the last two sessions by name. 00:00:52.320 --> 00:00:57.680 AND the destination against every row; longest match wins. Honest work. 00:00:57.730 --> 00:01:05.310 And it runs for EVERY packet, at line rate, against a table pushing a million rows. 00:01:05.360 --> 00:01:08.720 The big routers between cities mostly do not do that. 00:01:08.770 --> 00:01:13.240 Something else decides where your packet goes across the core. 00:01:13.290 --> 00:01:20.360 So what replaced them? A label: a twenty-bit number with meaning on one link only, swapped at every hop. 00:01:20.410 --> 00:01:29.030 It is not a cache and it is not a shortcut. It is a row index, and the address is still read exactly once, at the ingress. 00:01:29.080 --> 00:01:38.030 Section three derives the label and its header; section four walks a six-hop core crossing that costs one address lookup in total. 00:01:40.919 --> 00:01:43.439 Section one. The fork we skipped. 00:01:43.489 --> 00:01:52.439 Week four, one slide chose the Internet's philosophy: the datagram. Today, the road not taken — and it is not a museum piece. 00:01:55.543 --> 00:02:01.013 Two ways to move a packet across a network. There have only ever been two. 00:02:01.063 --> 00:02:08.773 The datagram approach: every packet independent, the full address inside, and a fresh decision at every router. 00:02:08.823 --> 00:02:12.163 Everything you have done since Session nine. 00:02:12.213 --> 00:02:19.803 The virtual-circuit approach: set up a relationship first, and then every packet of the flow follows the same path, 00:02:19.853 --> 00:02:24.853 wearing a small label instead of being routed again and again. 00:02:24.903 --> 00:02:28.093 And here is the word that does the work: VIRTUAL. 00:02:28.143 --> 00:02:33.863 Nothing is reserved. No copper, no bandwidth, no capacity. 00:02:33.913 --> 00:02:39.233 The circuit is rows in switch tables — written at setup, deleted at teardown. 00:02:39.283 --> 00:02:46.023 Week one's circuit switching reserved physics. This reserves only memory. Different animals entirely. 00:02:46.073 --> 00:02:55.023 If an exam answer says a virtual circuit "reserves bandwidth", it has confused the two. That is the single most common error on this topic. 00:02:57.841 --> 00:03:02.961 The choice the Internet actually made deserves a fair hearing first. 00:03:03.011 --> 00:03:06.631 A router can die and the next packet simply detours. 00:03:06.681 --> 00:03:13.701 There is nothing in the middle of the network that belongs to your conversation, so there is nothing to lose when a box fails. 00:03:13.751 --> 00:03:20.041 That is robustness, and it was bought by carrying the full address in every packet. 00:03:20.091 --> 00:03:27.391 And that robustness is why the military money paid for it. A network that survives losing pieces was the requirement. 00:03:27.441 --> 00:03:34.711 A network of circuits does not survive losing pieces: the circuits break, and have to be rebuilt. 00:03:34.761 --> 00:03:40.501 The price is a full table search per packet — which is exactly what you did by hand last session, 00:03:40.551 --> 00:03:44.201 and exactly the cost the core eventually got tired of paying. 00:03:44.251 --> 00:03:53.201 Both choices were right for their traffic. The interesting fact is that the modern core runs both at once. 00:03:53.674 --> 00:03:58.084 Connection-oriented transfer has three phases. 00:03:58.134 --> 00:04:05.094 Setup: a request walks from source to destination, and every switch on the path writes itself a table row. 00:04:05.144 --> 00:04:09.914 Then the acknowledgment walks back and completes those rows. 00:04:09.964 --> 00:04:15.864 Data transfer: packets flow, each carrying its label, all on the same road. 00:04:15.914 --> 00:04:24.864 And they arrive in order — because they all took one path. That is not a promise the protocol makes; it is a consequence of the geometry. 00:04:26.244 --> 00:04:30.964 Teardown: the flow ends, the rows are deleted, and the path stops existing. 00:04:31.014 --> 00:04:34.024 Because it was only ever bookkeeping. 00:04:34.074 --> 00:04:39.564 The datagram approach has no phases at all. Nothing to set up, nothing to tear down — 00:04:39.614 --> 00:04:44.394 and a full table search per packet as the price of that freedom. 00:04:44.444 --> 00:04:50.114 So the first byte costs a round trip on a circuit, and nothing at all on a datagram network. 00:04:50.164 --> 00:04:59.114 Which matters enormously for short flows, and not at all for long ones. Remember that when we price the fork. 00:05:00.141 --> 00:05:03.151 Here is the entire mechanism. 00:05:03.201 --> 00:05:06.141 A, R1, R2, R3, B. Four links. 00:05:06.191 --> 00:05:15.141 The packet crosses the first link wearing fourteen. R1 swaps it for sixty-six. R2 swaps that for twenty-two. R3 for nine. 00:05:15.741 --> 00:05:19.941 Four links, four labels, one flow. 00:05:19.991 --> 00:05:27.961 The number on the packet changes at every single hop, and none of them travels further than one link. 00:05:28.011 --> 00:05:34.841 A label means something only on its own link. Like a relay race where every runner carries a different baton, 00:05:34.891 --> 00:05:39.701 and only the two ends of each link ever agreed on anything. 00:05:39.751 --> 00:05:45.091 And what R2 did NOT do: it did not read an address, and it did not search a table. 00:05:45.141 --> 00:05:48.761 The label can BE the row number — one memory access. 00:05:48.811 --> 00:05:57.224 That last line is the second half of today, and Forouzan uses it almost verbatim. 00:05:57.274 --> 00:06:04.614 Take one switch at a time. A packet arrives at R2, on port one, wearing sixty-six. 00:06:04.664 --> 00:06:09.344 One: look up the key — port one, and label sixty-six. 00:06:09.394 --> 00:06:18.084 Not "sixty-six" on its own. The incoming port is half of the key, and that is precisely what makes labels local. 00:06:18.134 --> 00:06:23.524 Two: swap. Replace sixty-six with the row's outgoing label, twenty-two. 00:06:23.574 --> 00:06:30.284 One write. The IP header underneath is not touched, and is not even read. 00:06:30.334 --> 00:06:39.284 Three: send it out the row's port — port two. And R2's entire contribution to this packet's journey is over. 00:06:39.414 --> 00:06:42.534 One row, one answer, no ranking and no ties. 00:06:42.584 --> 00:06:51.534 Compare that with four ANDs and a contest. This is why the core wanted labels back — and the table has a row per circuit through this switch, not a row per destination on Earth. 00:06:57.381 --> 00:07:03.341 Forty-two seconds on the fork itself — both approaches, both prices. 00:07:03.391 --> 00:07:11.531 There they are side by side. Datagram: no setup, a full lookup at every hop, a table keyed on the destination. 00:07:11.581 --> 00:07:18.861 Virtual circuit: a setup phase, one small lookup, and a table keyed on a circuit number. 00:07:18.911 --> 00:07:26.371 Five packets from one conversation, each routed independently. No setup, so the first one leaves immediately. 00:07:26.421 --> 00:07:33.571 And nothing requires them to take the same road — they merely happen to. 00:07:33.621 --> 00:07:42.571 And there is the consequence. Two of them take the lower path, which is one hop shorter today, and they overtake. 00:07:42.771 --> 00:07:51.721 The receiver gets one, three, two, five, four — and reordering is TCP's problem, not the network's. It is not a bug; it is the bargain. 00:07:53.591 --> 00:08:01.881 Now the circuit. A, R1, R2, R3, B — and four links wearing fourteen, sixty-six, twenty-two and nine. 00:08:01.931 --> 00:08:10.461 Setup, data transfer, teardown. The setup packet walks the path and installs one row in every switch it passes. 00:08:10.511 --> 00:08:17.921 And there is R2's completed row. In port one, label sixty-six; out port two, label twenty-two. 00:08:17.971 --> 00:08:26.921 Box the rule: my out-label equals the next switch's in-label. A chain of purely local agreements, and out of it falls an end-to-end path. 00:08:28.461 --> 00:08:36.911 Then the price, row by row. Setup cost, state per switch, table key, ordering, and what happens when a link fails. 00:08:36.961 --> 00:08:41.871 Every row is a trade, and no column wins all five. 00:08:41.921 --> 00:08:48.591 And the synthesis: label swapping from the circuit world, IP addressing and routing from the datagram world. 00:08:48.641 --> 00:08:57.591 A circuit-switched forwarding plane, driven by a packet-switched control plane. That is the thesis of the hour. 00:08:58.250 --> 00:09:05.750 Where do the tables come from? Setup, in two passes — and the second pass is the interesting one. 00:09:05.800 --> 00:09:13.980 The request travels A to B. Each switch notes which port the request came in on, and assigns a label for that incoming link. 00:09:14.030 --> 00:09:19.950 R1 says fourteen, R2 says sixty-six, R3 says twenty-two, B says nine. 00:09:20.000 --> 00:09:28.770 But nobody knows their OUT label yet, because that belongs to the NEXT link — and the next switch has not spoken. 00:09:28.820 --> 00:09:34.010 So at the end of the forward pass, half of every row is blank. 00:09:34.060 --> 00:09:43.010 So the acknowledgment travels B back to A, carrying each link's label backwards. And now every switch can complete its row. 00:09:44.450 --> 00:09:50.810 R1: in port one, label fourteen; out port two, label sixty-six. 00:09:50.860 --> 00:09:59.810 R3: in port one, label twenty-two; out port four, label nine. And R2 in the middle: in one, sixty-six; out two, twenty-two. 00:10:00.170 --> 00:10:07.940 R2's out-label is R3's in-label. They are the same number because they are the same link. 00:10:07.990 --> 00:10:12.280 Box the rule: my out label equals the next switch's in label. 00:10:12.330 --> 00:10:19.820 A chain of purely local agreements — and out of it falls an end-to-end path. Nothing global was ever negotiated. 00:10:19.870 --> 00:10:28.820 Two passes, one forwards and one back, and the path exists. Nobody in the chain ever knew more than their own two neighbours. 00:10:31.529 --> 00:10:33.689 Checkpoint one. 00:10:33.739 --> 00:10:40.309 One. Name the three phases of a virtual circuit, and say which one carries data. 00:10:40.359 --> 00:10:46.999 Two. What exactly is reserved when a virtual circuit is set up? Be precise. 00:10:47.049 --> 00:10:55.999 Three. A packet arrives at R2 on port one wearing sixty-six. Talk through R2's three moves. 00:10:58.609 --> 00:11:07.559 One. Setup, data transfer, teardown. Only the middle one carries data; the other two are the price of admission. 00:11:07.799 --> 00:11:16.749 Two. Rows in switch tables. Nothing else. No copper, no bandwidth, no capacity — which is exactly why the word is "virtual". Week one's circuit switching reserved physics; this reserves memory. 00:11:19.829 --> 00:11:28.779 Three. Look up the key — port one, label sixty-six. Swap sixty-six for the row's out-label, twenty-two. Send it out the row's port, port two. No address is read, and no table is searched. 00:11:34.976 --> 00:11:38.196 Section two. Trace it, and mind the trap. 00:11:38.246 --> 00:11:47.196 The tables ahead deliberately reuse one number on three different links. If you follow it from table to table, you have treated a label like an address — and that is the whole misconception in one move. 00:11:53.963 --> 00:12:02.913 Three switches, three tables. A packet enters R1 on port one, wearing label five. Pause here for two minutes if you want to do it alone. 00:12:08.153 --> 00:12:13.423 R1: the key is port one, label five. Swap to thirty-one, out port two. 00:12:13.473 --> 00:12:19.413 One exact match. The packet crosses the first link wearing thirty-one. 00:12:19.463 --> 00:12:24.343 R2: the key is port two, label thirty-one. Swap to twelve, out port three. 00:12:24.393 --> 00:12:28.293 Note the key carefully — it is not just "thirty-one". 00:12:28.343 --> 00:12:35.813 R3: the key is port three, label twelve. Swap to seventy-seven, out port four. 00:12:35.863 --> 00:12:40.473 And the chain is five, thirty-one, twelve, seventy-seven. 00:12:40.523 --> 00:12:49.303 Four links, four labels, one flow — and not one of those numbers travelled further than a single hop. 00:12:49.353 --> 00:12:58.303 Now look at all three tables again, and find every row that mentions thirty-one. There are three of them. 00:12:59.252 --> 00:13:03.202 Here is the trap, and it was set on purpose. 00:13:03.252 --> 00:13:10.772 In R1, thirty-one is an out-label. In R2 it is our in-label — and also an out-label on a different row. 00:13:10.822 --> 00:13:16.772 In R3 it is the in-label of a completely unrelated flow arriving on a different port. 00:13:16.822 --> 00:13:25.772 Three rows, three tables, one number — and three unrelated meanings. The label space belongs to a link, not to the network. 00:13:26.572 --> 00:13:34.852 If you had followed thirty-one from table to table, you would have produced five, thirty-one, forty-four, thirty-one, fifty-two. 00:13:34.902 --> 00:13:43.362 That path is nonsense. It crosses links this flow never touches and arrives at ports the packet was never sent to. 00:13:43.412 --> 00:13:49.332 And the mistake is always the same one: treating a label as if it named a destination. 00:13:49.382 --> 00:13:58.122 It is not a short address. It is a baton, and every link runs its own race. The incoming PORT is what stops the numbers from colliding. 00:13:58.172 --> 00:14:04.835 This is worth failing once in private rather than once in an exam. 00:14:04.885 --> 00:14:10.705 Now price the fork honestly, because both columns have something the other wants. 00:14:10.755 --> 00:14:16.245 Datagram: a routing decision per packet, and reordering as a normal outcome. 00:14:16.295 --> 00:14:22.925 But NO state in the network. A router can die and the next packet simply detours. 00:14:22.975 --> 00:14:28.725 Virtual circuit: route ONCE at setup, and then every packet is an index lookup. 00:14:28.775 --> 00:14:34.935 Fast, ordered, predictable — and there is now state in every switch. 00:14:34.985 --> 00:14:41.715 A crash breaks the circuit until it is rebuilt. The flow stops, and somebody has to walk the setup again. 00:14:41.765 --> 00:14:47.755 Nothing detours by itself, because nothing else knows the path existed. 00:14:47.805 --> 00:14:56.335 Telephone-heritage networks went the circuit way: X twenty-five, Frame Relay, ATM. The Internet went datagram. 00:14:56.385 --> 00:14:58.235 Both were right for their traffic. 00:14:58.285 --> 00:15:07.235 So which does the MODERN Internet core run? Both at once. That hybrid has a name, and it is the rest of today. 00:15:09.302 --> 00:15:16.482 The same three tables, and the machine will let you make the mistake before it corrects you. 00:15:16.532 --> 00:15:22.352 State one: the chain is blank, and the packet is about to enter R1 on port one wearing label five. 00:15:22.402 --> 00:15:28.532 Work it out on paper before the next state. Two minutes if you need them. 00:15:28.582 --> 00:15:36.502 State two: the key is port one, label five. The winning row lights up, and the chain gains its first link. 00:15:36.552 --> 00:15:40.112 Swap to thirty-one, out port two. 00:15:40.162 --> 00:15:44.772 State three: port two, label thirty-one. Swap to twelve, out port three. 00:15:44.822 --> 00:15:51.622 Watch which row lights up — and notice that it is chosen by the pair, not by the number alone. 00:15:51.672 --> 00:15:59.012 State four completes the chain: five, thirty-one, twelve, seventy-seven, out of port four. 00:15:59.062 --> 00:16:04.522 Four links, four labels, and no number surviving more than one hop. 00:16:04.572 --> 00:16:11.492 State five highlights every row that mentions thirty-one. There are three, in three different tables. 00:16:11.542 --> 00:16:17.962 An out-label here, an in-label there, and somebody else's flow entirely in the third. 00:16:18.012 --> 00:16:26.792 State six produces the path you would have got by following thirty-one: five, thirty-one, forty-four, thirty-one, fifty-two. 00:16:26.842 --> 00:16:34.252 Nonsense at every step — and it is exactly the answer you get if you think a label is a short address. 00:16:34.302 --> 00:16:43.252 And the rule: a label is a baton, not an address. Open it, and try tracing with the port covered up — you will see immediately why the port is half the key. 00:16:47.699 --> 00:16:52.989 Five rows. You should be able to reproduce this table from memory. 00:16:53.039 --> 00:16:58.619 Setup before the first byte. Datagram: none. Circuit: one round trip. 00:16:58.669 --> 00:17:04.459 Which matters enormously for short flows, and not at all for long ones. 00:17:04.509 --> 00:17:11.909 State in each switch. Datagram: none per conversation. Circuit: one row per active circuit. 00:17:11.959 --> 00:17:15.809 And state is what breaks when a box reboots. 00:17:15.859 --> 00:17:24.059 Table key. Datagram: the destination address, longest match. Circuit: a small number, exact match. 00:17:24.109 --> 00:17:28.909 One of those is a search; the other is an array index. 00:17:28.959 --> 00:17:37.909 Order of arrival. Datagram: not guaranteed. Circuit: guaranteed on one circuit — because every packet took the same road. 00:17:39.209 --> 00:17:48.089 And when a link fails. Datagram: reroute silently, packet by packet. Circuit: the circuit breaks and must be rebuilt. 00:17:48.139 --> 00:17:57.089 Every row is a trade, and no column wins all five. The Internet chose the left column — and then borrowed the right one back. 00:17:59.558 --> 00:18:05.268 A minute of history, because it explains why both designs are still alive. 00:18:05.318 --> 00:18:12.158 The telephone tradition: X twenty-five, Frame Relay, ATM. Circuits all the way down — 00:18:12.208 --> 00:18:21.158 because the traffic was calls: long, steady, and ruined by reordering. Setting up once and following the path was obviously right. 00:18:22.488 --> 00:18:31.438 The Internet tradition: datagrams. Because the traffic was bursty, the network had to survive damage, and nobody wanted state in the middle. 00:18:31.718 --> 00:18:35.348 Also obviously right, for that traffic. 00:18:35.398 --> 00:18:40.718 And the modern core: a virtual-circuit engine bolted under the datagram Internet. 00:18:40.768 --> 00:18:46.078 IP addressing and IP routing protocols on top; label swapping underneath. 00:18:46.128 --> 00:18:55.078 That is MPLS, and it is the thesis of the hour. The fork was never resolved — it was layered. 00:18:55.482 --> 00:18:57.682 Checkpoint two. 00:18:57.732 --> 00:19:06.212 One. A packet enters R1 on port one wearing five. Give the label on every link, and the exit port. 00:19:06.262 --> 00:19:14.172 Two. The value thirty-one appears in all three tables. What does that tell you about labels? 00:19:14.222 --> 00:19:20.172 Three. Give two things the datagram approach buys, and two it costs. 00:19:20.222 --> 00:19:29.172 One. Five, thirty-one, twelve, seventy-seven — leaving on port four. Each lookup uses the key of incoming port and incoming label, and each label lives on exactly one link. 00:19:32.892 --> 00:19:41.842 Two. Nothing at all about the flow. The label space belongs to a link, so the same number on three links is a coincidence, not a message. Following it from table to table treats a label as an address. 00:19:47.132 --> 00:19:56.082 Three. Buys: no state in the middle, so a router can die and the next packet detours; and no setup, so the first byte leaves immediately. Costs: a full table search per packet, and no guarantee about order or path. 00:20:04.598 --> 00:20:05.938 Section three. MPLS. 00:20:05.988 --> 00:20:14.938 A virtual-circuit engine bolted under the datagram Internet — the same label swapping, built by routing protocols instead of by a user's request. 00:20:19.365 --> 00:20:24.955 Two reasons labels came back, and the second is the one that kept them. 00:20:25.005 --> 00:20:31.225 Remember the hook's arithmetic. Longest prefix match is per-packet work against a giant table. 00:20:31.275 --> 00:20:38.055 Every row a candidate, for every packet, at line rate. Honest — and expensive. 00:20:38.105 --> 00:20:41.545 And here is Forouzan's sentence, almost verbatim: 00:20:41.595 --> 00:20:48.215 in a connection-oriented network, the table is accessed by the label. The label IS the row number. 00:20:48.265 --> 00:20:54.105 No search. No contest. One array index, at wire speed. 00:20:54.155 --> 00:21:02.705 And now the quieter reason, which is why MPLS is still everywhere even though hardware does longest-prefix match fast anyway. 00:21:02.755 --> 00:21:06.705 An address only says WHERE a packet is going. 00:21:06.755 --> 00:21:13.545 A label can say which customer it belongs to, which path it must take, which class of service it paid for. 00:21:13.595 --> 00:21:22.057 Addresses find; labels steer — and that is the argument on the "what it buys" slide. 00:21:22.107 --> 00:21:27.347 Where does the label actually live? In a header that has no proper home. 00:21:27.397 --> 00:21:31.147 It squeezes between the data-link header and the IP header. 00:21:31.197 --> 00:21:37.817 So it is neither layer two nor layer three — and engineers call it layer two-point-five. 00:21:37.867 --> 00:21:44.707 Label: twenty bits. A million circuits per link, and values zero to fifteen are reserved. 00:21:44.757 --> 00:21:53.637 Label three means implicit null — "send me plain IP, I am the egress" — and it comes back in section four. 00:21:53.687 --> 00:22:00.747 EXP: three bits. Experimental, and in practice the class of service this packet paid for. 00:22:00.797 --> 00:22:05.247 So a label can carry priority as well as a path. 00:22:05.297 --> 00:22:11.767 TTL: eight bits, counting down exactly like IP's — because loops must still die. 00:22:11.817 --> 00:22:20.237 Nothing about MPLS makes a loop impossible, and in the core the IP header is never read, so it needs its own. 00:22:20.287 --> 00:22:25.327 And S: one bit. Bottom of stack. One means this is the last label. 00:22:25.377 --> 00:22:34.327 Which implies there can be more than one — and there usually is. That bit is the whole of the next slide. 00:22:34.645 --> 00:22:39.405 Bottom of stack, because MPLS headers can pile up. 00:22:39.455 --> 00:22:44.855 An outer label for the tunnel through the core, and an inner label for whose traffic this is. 00:22:44.905 --> 00:22:51.615 Encapsulation — Session three's oldest trick — doing circuits hierarchically. 00:22:51.665 --> 00:22:56.755 And that stack is how two companies can both use ten-dot-anything and never collide. 00:22:56.805 --> 00:23:05.695 The inner label says which customer. Their private addresses are never compared with each other, because the core never looks at them at all. 00:23:05.745 --> 00:23:11.145 And the first word of the name is MULTI-protocol. The shim does not care what it carries. 00:23:11.195 --> 00:23:18.725 IP today, Ethernet tomorrow, anything at all. It is a general-purpose circuit engine that happens to be full of IP. 00:23:18.775 --> 00:23:27.725 Two labels, two jobs, one mechanism — and this is what a carrier is actually selling when it sells you a VPN. 00:23:30.061 --> 00:23:37.201 Forty-two seconds on the mechanism, the header, and what the core actually bought. 00:23:37.251 --> 00:23:43.571 There is the complaint. A thirty-two-bit key, a million rows, ranked by length, searched for every packet. 00:23:43.621 --> 00:23:51.061 And it says nothing at all about which path the packet takes. That last point is the one that matters most now. 00:23:51.111 --> 00:23:58.661 The two ways side by side. The IP way: look at the address, search a million prefixes, rank the matches. 00:23:58.711 --> 00:24:07.661 The label way: look at a twenty-bit label — and it IS the row number. No search, no ranking, no ties. 00:24:08.591 --> 00:24:14.361 Now the drill. Enter LSR-one wearing seventeen: swap to forty-five, out port two. 00:24:14.411 --> 00:24:23.361 LSR-two: forty-five becomes forty-five. LSR-three: POP — and a plain IP packet leaves port four. 00:24:23.731 --> 00:24:30.561 And why the repeat is legal. Forty-five is not a place; it is a row number in the next switch's table. 00:24:30.611 --> 00:24:39.561 A relay race where every runner carries a different baton. The same number on two links is a coincidence, not a message. 00:24:41.241 --> 00:24:47.301 There is the LFIB: incoming port and incoming label in, operation and outgoing label and port out. 00:24:47.351 --> 00:24:56.301 One row, one answer. And the row counts: about a thousand label-switched paths, against about a million IP prefixes. 00:24:56.491 --> 00:25:04.041 The header itself. Twenty bits of label, three of traffic class, one bottom-of-stack bit, eight of TTL. 00:25:04.091 --> 00:25:11.141 Between the frame header and the IP header — layer two and a half, and labels can be stacked. 00:25:11.191 --> 00:25:18.101 And the honest ending: traffic engineering, multi-protocol, VPNs via the stack — but NOT speed, any more. 00:25:18.151 --> 00:25:27.101 Hardware caught up. What survived is that you get to choose the path and carry anything inside it, without touching IP. 00:25:29.611 --> 00:25:31.891 Checkpoint three. 00:25:31.941 --> 00:25:38.631 One. Name the four fields of the MPLS shim header and give the size of each. 00:25:38.681 --> 00:25:45.041 Two. Where does the shim sit, and why is it called layer two-point-five? 00:25:45.091 --> 00:25:53.821 Three. Why does MPLS need a TTL of its own when IP already has one? 00:25:53.871 --> 00:26:02.821 One. Label, twenty bits; EXP or traffic class, three bits; S, one bit — bottom of stack; and TTL, eight bits. Thirty-two bits in total. 00:26:03.461 --> 00:26:12.411 Two. Between the data-link header and the IP header. It belongs to neither layer two nor layer three, so it gets a number in between — which is a joke, and also the most accurate description anyone has given it. 00:26:17.121 --> 00:26:26.071 Three. Because in the core the IP header is never read. If the labelled path looped, nothing would decrement the IP TTL and the packet would circulate forever. The shim carries its own so that loops still die. 00:26:34.211 --> 00:26:37.111 Section four. Push, swap, pop. 00:26:37.161 --> 00:26:46.111 The packet arrives at the edge as an ordinary datagram, and leaves the far edge as an ordinary datagram. In between, it is a number. 00:26:49.245 --> 00:26:53.355 The life of a labelled packet, in four moves. 00:26:53.405 --> 00:27:02.355 It arrives at the edge of the core as an ordinary datagram. The ingress Label Edge Router does the LAST address lookup of the packet's core journey — 00:27:02.805 --> 00:27:11.235 one longest-prefix match, one routing verdict — and it hangs that verdict on the packet as a label. PUSH. 00:27:11.285 --> 00:27:18.555 Every Label Switch Router after that swaps: in-label, out-label, out-port. An index lookup each. 00:27:18.605 --> 00:27:25.445 Not one of them reads an address, and not one of them knows where the packet is going. 00:27:25.495 --> 00:27:32.915 At the far edge, POP. The label comes off, and an ordinary datagram steps back into the ordinary Internet. 00:27:32.965 --> 00:27:36.975 So a six-hop core path costs exactly one address lookup — at the ingress. 00:27:37.025 --> 00:27:42.235 That is what the core bought, and it is the answer to today's hook. 00:27:42.285 --> 00:27:51.235 The path it pinned has a name: the Label Switched Path — a virtual circuit in everything but its birth certificate. 00:27:52.545 --> 00:27:56.215 The drill. Call each hop before I do. 00:27:56.265 --> 00:28:01.485 Enter LSR-one wearing seventeen. The table says swap to forty-five, out port two. 00:28:01.535 --> 00:28:04.075 One exact match, and no address is read. 00:28:04.125 --> 00:28:09.385 LSR-two receives forty-five — and swaps it to … forty-five. 00:28:09.435 --> 00:28:13.215 Legal. Different link, different namespace. 00:28:13.265 --> 00:28:22.215 The same number is a coincidence, not a message. And if that made you hesitate, the trap from Section Two just worked on you twice. 00:28:23.855 --> 00:28:26.095 Out on port three. 00:28:26.145 --> 00:28:30.565 LSR-three receives forty-five, and its row says POP. 00:28:30.615 --> 00:28:36.175 So a plain IP packet leaves port four, back in datagram land. 00:28:36.225 --> 00:28:40.515 Three hops. Three array lookups. Zero address reads. 00:28:40.565 --> 00:28:46.235 That is the sentence to carry out of this session, and it is the hook, answered. 00:28:46.285 --> 00:28:55.235 One footnote: penultimate hop popping. The egress asked for "implicit null", so the last transit router removes the label and saves the egress a second lookup. 00:28:59.075 --> 00:29:04.235 What has just been built has a name, and the name is doing real work. 00:29:04.285 --> 00:29:13.235 The path is pinned, exactly as a virtual circuit is. Rows in tables, written in advance, followed by every packet of the flow. 00:29:13.475 --> 00:29:17.755 Everything from Section One applies, unchanged. 00:29:17.805 --> 00:29:21.535 But nobody dialled it. A user did not request this circuit. 00:29:21.585 --> 00:29:30.105 A label-distribution protocol between the routers built it, driven by the same IP routing that builds the ordinary table. 00:29:30.155 --> 00:29:33.565 So it is circuit forwarding, with packet-switched control. 00:29:33.615 --> 00:29:40.585 That is the whole hybrid in one line — and it is why the nineteen-seventy fork was never resolved. It was layered. 00:29:40.635 --> 00:29:49.585 One sentence of detail on the distribution protocol is enough. What matters is who built the path, not the acronym. 00:29:51.237 --> 00:29:59.077 So what does a carrier actually pay for? Four things, and the first is the weakest. 00:29:59.127 --> 00:30:08.077 Speed, historically. The index beat the search: one exact match against about a thousand label-switched paths, instead of a longest-prefix search over about a million IP prefixes. 00:30:10.907 --> 00:30:18.337 But be honest: modern hardware does longest-prefix match fast too. Speed alone would have let MPLS die. 00:30:18.387 --> 00:30:27.337 It did not die. Traffic engineering: a destination address picks the one best road, full stop. That is what forwarding MEANS. 00:30:27.387 --> 00:30:35.697 A label can be told to take the second-best road, on purpose — to balance load, or to honour a contract. 00:30:35.747 --> 00:30:41.607 VPNs, via the stack. An outer label for the path, an inner one for the customer. 00:30:41.657 --> 00:30:48.727 So two companies both using ten-dot-anything never collide, and neither of them has to renumber. 00:30:48.777 --> 00:30:57.727 Multi-protocol: the payload can be IP, Ethernet, or anything else. Hence the first word of the name — and it was not marketing. 00:31:00.237 --> 00:31:06.627 And IP is untouched. The addresses, the masks, the AND — all exactly as in Sessions ten to seventeen. 00:31:06.677 --> 00:31:12.711 Nothing above or below the shim had to change. 00:31:13.731 --> 00:31:21.321 The same four routers, twice: once as plain IP, and once inside a label-switched path. 00:31:21.371 --> 00:31:29.191 State one is the baseline. Four routers, and every one of them running a longest-prefix search of a million-row table. 00:31:29.241 --> 00:31:37.471 It works — Session seventeen is exactly this — but the interior routers are each solving the whole problem again. 00:31:37.521 --> 00:31:46.471 State two is label distribution, downstream to upstream. The egress asks for implicit null — label three, "send me plain IP". 00:31:47.051 --> 00:31:56.001 Then LSR-three advertises forty-five, and LSR-two advertises forty-five on a different link. The repeat is legal, and it is deliberate. 00:31:58.211 --> 00:32:06.791 State three: the packet enters wearing seventeen. The key is port one and label seventeen — one row, one answer. 00:32:06.841 --> 00:32:15.561 Swap to forty-five, out port two. And look at the packet on the left: a shim in front of an untouched IP header. 00:32:15.611 --> 00:32:21.161 State four: the key is port two, label forty-five. Swap to forty-five, out port three. 00:32:21.211 --> 00:32:28.381 No address anywhere in that decision. LSR-two has no idea what the destination is, and does not need one. 00:32:28.431 --> 00:32:37.381 State five is the plant, made explicit. Different link, different namespace — so the same number is a coincidence. 00:32:38.551 --> 00:32:45.971 If you followed forty-five from table to table, you treated a label like an address. Again. 00:32:46.021 --> 00:32:54.971 State six: the row says POP, because the egress asked for implicit null. The label comes off and a plain IP packet leaves port four. 00:32:55.311 --> 00:33:00.401 Penultimate hop popping, and it saves the egress a second lookup. 00:33:00.451 --> 00:33:09.401 And state seven counts. Four IP lookups on the left; one plus three exact matches on the right — against a table of a thousand rows rather than a million. 00:33:10.741 --> 00:33:19.691 Plus the stack: an outer label for the path, an inner one for the customer. One mechanism, two jobs. Open it and step through both columns yourself. 00:33:23.787 --> 00:33:28.717 Back to the question on slide two. What replaced the address? 00:33:28.767 --> 00:33:35.727 A number: a twenty-bit label, meaningful on one link only, swapped at every hop. 00:33:35.777 --> 00:33:40.237 It is not a shortcut, and it is not a cache. It is a row index. 00:33:40.287 --> 00:33:46.197 There is nothing to miss, nothing to expire, and nothing to fall back to. 00:33:46.247 --> 00:33:54.417 And the address is still read — exactly once, at the ingress. One longest-prefix match for the whole core crossing, 00:33:54.467 --> 00:33:59.777 and the verdict is written on the packet so nobody has to derive it again. 00:33:59.827 --> 00:34:07.107 So the core did not abandon IP. It stopped RE-DERIVING the same answer six times over, for every packet, forever. 00:34:07.157 --> 00:34:16.107 Which is the same instinct as aggregation two sessions ago: do the expensive thinking once, and let everyone downstream read the result. 00:34:19.553 --> 00:34:23.093 Now the thesis, in three lines. 00:34:23.143 --> 00:34:31.223 The Internet chose datagrams, and was right. No state in the middle, survives damage, no setup before the first byte. 00:34:31.273 --> 00:34:35.553 Fifty years of evidence say the choice was correct. 00:34:35.603 --> 00:34:43.383 The telephone world chose circuits, and was also right — for their traffic. Long, steady flows that hate reordering, 00:34:43.433 --> 00:34:47.283 on a network nobody expected to be bombed. 00:34:47.333 --> 00:34:55.443 And the modern core runs both, one under the other. Circuit forwarding underneath, datagram addressing and routing on top. 00:34:55.493 --> 00:35:01.403 Not a compromise — a stack. And the packet you sent this morning probably travelled inside one. 00:35:01.453 --> 00:35:10.403 When two good designs disagree and neither dies, look for the layer boundary. It is almost always where the argument went. 00:35:12.160 --> 00:35:16.550 Checkpoint four, and it is the last one. 00:35:16.600 --> 00:35:24.260 One. A packet crosses a six-hop MPLS core. How many address lookups happen, and where? 00:35:24.310 --> 00:35:32.720 Two. LSR-two swaps label forty-five for label forty-five. Is that legal? Explain in one sentence. 00:35:32.770 --> 00:35:40.740 Three. Give the two reasons MPLS survived after hardware made longest-prefix match fast. 00:35:40.790 --> 00:35:49.740 One. One, at the ingress label edge router. Every hop after that is an exact-match lookup on the label — and with penultimate hop popping, the egress receives a plain IP packet. 00:35:53.560 --> 00:36:02.510 Two. Yes. The label space belongs to a link, so the incoming forty-five and the outgoing forty-five are on different links and are unrelated numbers. The key is incoming port and incoming label. 00:36:06.900 --> 00:36:15.850 Three. Traffic engineering: a label can be sent down a path the routing protocol would not have chosen. And VPNs via the label stack: an outer label for the path, an inner one for the customer — so two customers using the same private addresses never collide. 00:36:27.040 --> 00:36:30.090 Five ways to lose these marks. 00:36:30.140 --> 00:36:34.870 Wrong: a virtual circuit reserves bandwidth along the path. 00:36:34.920 --> 00:36:43.870 Right: it reserves rows in switch tables. VIRTUAL. Week one's circuit switching reserved physics; this reserves memory. 00:36:44.750 --> 00:36:51.310 Wrong: follow label thirty-one through the tables to trace the path. 00:36:51.360 --> 00:37:00.310 Right: a label is local to one link. The key is incoming port and incoming label, and the same number elsewhere is a coincidence. 00:37:01.590 --> 00:37:03.740 Wrong: MPLS replaces IP. 00:37:03.790 --> 00:37:12.740 Right: IP is untouched. MPLS sits between layers two and three and carries IP unchanged — the ingress even uses an ordinary longest-prefix match. 00:37:14.550 --> 00:37:18.450 Wrong: the label is a shortened IP address. 00:37:18.500 --> 00:37:26.800 Right: it is a row number. It names no place, and it is thrown away and rewritten at every hop. 00:37:26.850 --> 00:37:31.390 Wrong: MPLS is faster, and that is why carriers use it. 00:37:31.440 --> 00:37:40.390 Right: it was, historically. Today it is traffic engineering and VPNs, and "faster" on its own is not the answer. 00:37:42.194 --> 00:37:47.134 This session had no arithmetic in it. Here is what it did have. 00:37:47.184 --> 00:37:56.134 The mechanism is one table lookup. Key: incoming port and incoming label. Value: operation, outgoing label, outgoing port. 00:37:57.414 --> 00:38:01.484 There is no arithmetic in it — not even an AND. 00:38:01.534 --> 00:38:09.454 The setup is two passes. A request forwards to assign in-labels, an acknowledgment back to fill in out-labels, 00:38:09.504 --> 00:38:14.544 and one rule: my out-label is the next switch's in-label. 00:38:14.594 --> 00:38:23.034 And everything else today was consequence. Locality, the stack, VPNs, traffic engineering, penultimate hop popping — 00:38:23.084 --> 00:38:27.564 all of it follows from a number that means something on exactly one link. 00:38:27.614 --> 00:38:35.116 Which is why the mechanism is trivial and the consequences are the content. 00:38:35.166 --> 00:38:39.046 Four things you should be able to do now. 00:38:39.096 --> 00:38:48.046 One: name the three phases of a virtual circuit, and say what is actually reserved — rows in tables, and never bandwidth. 00:38:48.576 --> 00:38:55.816 Two: trace a labelled packet through three switches from their tables, using the key of incoming port and incoming label — 00:38:55.866 --> 00:38:59.676 and without following a number across tables. 00:38:59.726 --> 00:39:08.676 Three: name the four shim fields with their sizes — twenty, three, one, eight — and explain layer two-point-five, including why the TTL has to be there. 00:39:12.216 --> 00:39:20.516 Four: say what MPLS buys, honestly. Traffic engineering and VPNs, with speed as a historical footnote. 00:39:20.566 --> 00:39:29.516 Homework: the trace drill from cold tables, the shim header from memory, and one paragraph on why the fork was layered rather than resolved. 00:39:32.475 --> 00:39:35.655 Three things before the next session. 00:39:35.705 --> 00:39:43.445 One: the trace drill, from tables you have not seen. Invent three switch tables with a deliberately repeated label, 00:39:43.495 --> 00:39:51.805 hand them to somebody else, and trace each other's. The trap only teaches once if you spring it on yourself. 00:39:51.855 --> 00:40:00.395 Two: the shim header from memory, with sizes. Four fields, thirty-two bits, and one sentence each on why the field exists. 00:40:00.445 --> 00:40:05.875 If you can say why the S bit is there, you understand the stack. 00:40:05.925 --> 00:40:10.915 Three: one paragraph — why was the fork layered rather than resolved? 00:40:10.965 --> 00:40:17.865 Not a summary. An argument. Which properties of each approach survive being put underneath or on top of the other? 00:40:17.915 --> 00:40:26.865 Reading: twenty-two point one onwards. Next, the arc's irony — an address space so large that scarcity is impossible, and the strange fact that NAT survived it anyway. 00:40:32.239 --> 00:40:35.289 Three wordings, one idea. 00:40:35.339 --> 00:40:40.669 Disguise one: "trace this labelled packet". Three tables and a start label. 00:40:40.719 --> 00:40:48.479 Key on incoming port and incoming label — never on the label alone. That is the whole marking scheme. 00:40:48.529 --> 00:40:54.579 Disguise two: "compare datagram and virtual circuit". That is the five-row trade: 00:40:54.629 --> 00:41:03.579 setup, state, table key, ordering, and what a failure does. Five rows, and neither column wins them all. 00:41:03.699 --> 00:41:10.439 Disguise three: "why does the core use MPLS?" And the answer is not "because it is faster". 00:41:10.489 --> 00:41:14.949 Traffic engineering, VPNs — with speed as a footnote. 00:41:14.999 --> 00:41:23.949 One idea underneath all three: a number that means something on exactly one link, and everything that follows from that. 00:41:25.655 --> 00:41:27.345 That is Session eighteen. 00:41:27.395 --> 00:41:32.835 A label is a baton, not a short address — and every link runs its own race. 00:41:32.885 --> 00:41:40.505 A virtual circuit reserves rows in tables. Never bandwidth: that is Week one, and a different animal entirely. 00:41:40.555 --> 00:41:47.655 Key on incoming port and incoming label. The same number on another link is a coincidence, not a message. 00:41:47.705 --> 00:41:56.045 Push at the ingress, swap through the core, pop at the far edge — three hops, three array lookups, zero address reads. 00:41:56.095 --> 00:42:05.045 And the thesis: the nineteen-seventy fork was never resolved. It was layered — circuit forwarding underneath, packet-switched control on top. The packet you sent this morning probably travelled inside one. 00:42:09.705 --> 00:42:18.505 Next session, the arc's last irony: an address space so large that scarcity becomes impossible, and the strange fact that NAT survived it anyway. 00:42:18.555 --> 00:42:23.201 I will see you there.