Transcript
Perlman: I'm Radia Perlman. Welcome to the talk, Myths, Missteps, and Mysteries of Computer Networks. How do you understand network protocols? The way that it's usually taught is as if just memorize the details of the current standards as if nothing else ever existed, no critical thinking about what's good, or what's bad, or alternate ways things could have been done. It's important to understand that nobody would have designed what we have today. It's just so grotesquely complicated. The only way to really understand it is to know how we got here. First, I'm going to talk about some layers 2 and 3 stuff. What is Ethernet exactly? It's not what you think it is. How does it compare and work with IP? If I ask a network person, why do we have both Ethernet and IP? They'll say Ethernet's layer 2, and IP is layer 3. I'll say, no, that's not really true. What is all this layer stuff? First, we need to review network layers. ISO is credited with naming the layers, but it's just a way of thinking about networks. Layer 1 is the physical layer, which is, what's the shape of the connector? How do you signal a bit to a neighbor who's on the same wire as you? Layer 2 is that you use the stream of bits that layer 1 gives you and somehow mark the beginning and end of a packet, maybe put in a checksum. It's a way of sending a whole packet to a neighbor. Layer 3 has switches that connect to multiple links and forward packets from one link to another in order to deliver a packet across a network from a source to a destination.
What layer is Ethernet? Ethernet was intended to be layer 2, which should mean that it's just between neighbors, which means it shouldn't be forwarded, but we are forwarding Ethernet packets. How did that happen? Way back when I was the designer of layer 3 of DECnet, and the routing protocol I designed for DECnet was adopted by ISO and renamed IS-IS. It can route anything. It wasn't really DECnet specific. Today, it's widely deployed for routing IP. What's a routing algorithm? Routers exchange information with their neighbors in order to compute a forwarding table. What's a forwarding table? The forwarding table is a list of destinations and output ports. When the switch or router bridge, I use these terms interchangeably, it's something that receives a packet. The packet contains a destination address. The switch looks in its forwarding table to decide which port to forward the thing on. Link state routing is what I did. Here's a picture of a network. There are seven nodes. Again, I'm using nodes and switches and routers interchangeably. You'll notice in this picture, like E has a neighbor B and the number here is the cost of the link. E has a neighbor F at a cost of 4. Each node is responsible for creating what I call a link state packet, saying who it is and who its neighbors are. C's link state packet says I am C, I have a neighbor B at a cost of 2, and it does, F at a cost of 2, and it does, and G at a cost of 5. These link state packets get propagated to all the other switches, and so all the switches have the same database, which is the most recently generated link state packet from all the other switches. That gives you enough information to draw the picture of the network or compute paths. Each one uses this database to compute its own forwarding table.
The Invention of Ethernet
Back to history, I was designing layer 3, then along came the Ethernet with great fanfare. Originally, Ethernet, the invention of Ethernet was a way for a bunch of nodes to share the same wire. There was no leader to call on them. They were all peers. If two of them talk at the same time, the receivers just get garbage, so they have to somehow work it out by themselves so that they're not always tripping over each other's transmissions. The invention of Ethernet was known as CSMA/CD. CS stands for Carrier Sense, which is just polite, listen before you start speaking. If someone else is talking, you don't start talking. MA is just lots of nodes share the same wire. MA is Multiple Access. CD is Collision Detect, which says that even while you're talking, you listen in case somebody else started talking at about the same time, in which case, you should both stop, wait a random amount of time and try later. If you try to load the link with more than about 60% of the traffic, there's too many collisions. This technology is fine, but it only works for a limited number of nodes, maybe hundreds, and a limited amount of distance. It's ok for within a building, but it wouldn't be ok for using for the entire internet. Ethernet addresses. Ethernet has a 6-byte address, but it only needs to identify nodes on a single link. I said there could only be a few hundred nodes on a link. Whereas IP has a 4-byte address, and it was intended to identify all the nodes in the internet. Why would the Ethernet designers use a 6-byte address when an Ethernet was only supposed to support a few hundred nodes. The reason is that it eliminated the need for users to configure addresses. When a manufacturer wants to manufacture a device that will plug onto an Ethernet, they purchase a block of addresses and configure a unique address into each device. A mild rant, for bizarre reasons, this built-in address is known as the MAC address. First of all, it's not an address, because to me, my address should change if I move. Here, it's something that's built into the device and always stays the same. MAC is some weird jargon that nobody remembers what it is or cares. At any rate, they're called MAC addresses.
Ethernet as a New Type of Link
I saw Ethernet as a new type of link. When I saw it, I said, I have to change the routing protocol in little ways to accommodate this new type of link. For instance, with the link state protocol, if you had a link with 500 nodes, all of whom are neighbors, and every one of them reported 499 neighbors, the link state database would get very large. I said, ok, instead of considering a 500-node Ethernet as fully connected, instead, think of it as having the Ethernet itself be a special node, called a pseudonode, and just have everybody report connectivity to it. Now it's n links with n+1 nodes instead of n squared links. Instead of fully connected here, it's one extra node and much fewer links. That was not a big deal. It was just, ok, Ethernet is a new kind of link. I wish they'd called it Etherlink, but because they called it Ethernet, a bunch of people said, this is the new way of doing networking. It's easy to get confused. An Ethernet packet has data and a header with a destination and source. A layer 3 packet looks the same, it has this extra field of a hop count. The reason for the extra field is that when the topology changes, it takes a while for information about that to propagate. The switches will have inconsistent forwarding tables, and packets might go around in loops. If you have a hop count to count how many times a packet has gone round in a loop, if it's looping, then the switches know to just throw it away. That enables the routing protocol to settle down more quickly rather than competing for bandwidth with all of these packets that are circulating.
It's easy to confuse Ethernet with a layer 3 protocol because it looks the same. Ethernet has different type of addresses. Ethernet addresses are flat. Meaning there's no way to summarize a bunch of addresses in a forwarding table because any particular address can be anywhere because it's really not an address it's an ID. Whereas a layer 3 protocol hands out addresses in such a way that you can draw a circle around a portion of the net, and anyone outside of the circle can just have a single forwarding entry that says, go to that circle. Ethernet doesn't have a hop count field. It wasn't because the Ethernet designers didn't know about hop counts, it just never occurred to them that anyone would be forwarding Ethernet packets. Because, really, we shouldn't be, it's not a layer 3 protocol.
How Ethernet Evolved from CSMA/CD to Spanning Tree
How did it evolve from CSMA/CD to spanning tree? People when they heard about, Ethernet is the new way of doing networking, they built their applications on Ethernet without having layer 3 in their network stacks. A level 3 router can't forward without the right envelope, the right header on there. I tried to argue with them and said, no, don't take out layer 3, you still need it. They said, you're just upset because no one needs your stuff anymore. I said, but you may want to talk from one Ethernet to another. They said, our customers would never want to do that. They were real heroes in the company because their applications were good, and so they made lots of money for the company. Their application would have been just as good if they'd done it correctly, which was including layer 3 in the step. I was in a bad mood about the whole thing. Around 1983, my manager called me in and said, "Radia, we need to design a magic box that will sit between two Ethernets and let someone on one Ethernet talk to someone on the other Ethernet," which is what my step was all about. The constraint was without changing the endnodes to have layer 3. There were no spare fields in the Ethernet header, and there was a hard size limit.
The basic concept was the bridge just listens promiscuously, meaning it just listens to every single packet, stores it up. When some other port is free, because the ether is free, or it gets the token depending on what kind of comported as, the bridge forwards onto that port. This requires a topology without loops, because otherwise there's no hop count, the packet will go around forever. Worse than that, if you have a bridge with five ports, it not only forwards it, but it forwards four copies because it forwards one on each one of its ports. What to do about loops? One possibility was just tell customers, "This is a kludge that's only going to last for a few months. Don't worry, we're going to fix the endnode software so that it has layer 3, and then you can use a real router." In the meantime, what if the customer just miscables something because that would be a total disaster, it brings down the entire bridge to Ethernet. The other thing is that a loop isn't a bad thing. A loop says that there's an alternate path in case something breaks. There was a desire for a loop pruning algorithm. As my manager explained the problem, allow any physical topology, no rules, just plug it together however you want. The bridges with zero configuration should prune to a loop-free topology for sending data. The other links that are not chosen to be in the loop-free topology are still there and you still run the spanning tree algorithm in case the topology changes. While the topology is settled down, you forward to and from all the links that are in the subset that's the loop-free topology and you don't forward data to or from links that are not chosen. This is the spanning tree algorithm. When he proposed this, I realized that night, it's really easy, just create a tree.
The physical topology looks something like this. These round things are bridges and the blue things are Ethernets. After running the spanning tree algorithm, the bridges decide which ports are excess and don't forward packets to or from those links. This is the loop-free topology. If you'll notice, the path from A to B would go like this, A to X. You might think, that's a silly spanning tree algorithm, if there had been a smarter spanning tree algorithm, you would have a better path from A to X. It really just has to go that way. The problem is, if you have a single subsetted, shared, loop-free topology, then you can't get optimal paths. If you imagine that the topology is a big circle, the spanning tree algorithm has to break at some place, break the circle at some place, and people on either side of the break have to go around the long way.
About a year after spanning tree bridges, CSMA/CD died a long time ago. When people think, Ethernet is wildly successful. No, it isn't. The main invention of Ethernet doesn't exist anymore. It's just point to point links, no shared links with running the spanning tree algorithm. My manager asked me to do this on a Friday. This was before people had cell phones or read email. He also said, and furthermore, just to make it more challenging, make it scale as a constant. No matter how many links and bridges there are in the world, the amount of memory necessary to run this in any bridge should be a constant, which is crazy. It'll probably be n squared, but the best you can hope for is linear. That night, which was a Friday, and he was going to be on vacation the following week, I realized, "It's trivial, I could prove that it works." It was such a simple algorithm, that on Monday and Tuesday, I wrote the spec. It was about 25 pages long. It was in enough detail that the implementers got it working in just a few weeks without asking me a single question. This brings us to the end of Tuesday. The remainder of the week, I couldn't concentrate on anything else, because I had to show off to my boss and he wasn't reachable. I spent the remainder of the week working on the poem that goes along with the algorithm, and is the abstract of the paper in which I published the algorithm. The poem is called the Algorhyme, because every algorithm should have an Algorhyme. "I think that I shall never see a graph more lovely than a tree. A tree whose crucial property is loop-free connectivity. A tree which must be sure to span so packets can reach every LAN. First, the root must be selected, by ID it is elected. Least cost paths from root are traced, in the tree these paths are placed. A mesh is made by folks like me. Then bridges find a spanning tree."
Then the interesting thing was, at first the implementers didn't want to bother with the spanning tree, because they said, this is just a quick hack until people fix the endnode, so it'll only last for a few months. Just tell the customers, don't put loops in. I sympathized with that somewhat. Because even though the spanning tree is incredibly trivial, if you add that to the basic concept, it makes it more complicated. If really, we were going to fix all the endnodes to put in layer 3, it really didn't have to be a fancy device. I didn't want to argue because they would not listen to me anyway, because they'd assume I was biased. I let management argue about it. Management said, yes, we should put the spanning tree algorithm into the bridge. Then I knew, yes, we'd done the right thing when I heard about the very first bridge that we sold, which I only found out about after the patch. It was sold to the most sophisticated networking customer there was, and they had two Ethernets and one bridge. At the time, they were arguing with the sales guy saying, "But we're doing all this fancy stuff with all these protocols." He said, "It doesn't matter. It's just going to work." They said, "We really need to talk to the engineers." He said, "No, you don't. It'll just work." They plugged it together and it didn't work and they were really angry. When field service went to figure out what the problem was, they realized that the world's most sophisticated customer had done this with the world's simplest topology, which is that they plugged both ends of the bridge into the same Ethernet. Indeed, everything was working perfectly, the bridge said, I don't need to forward packets, so I won't. If the topology ever changes, and I need to forward packets, I'll be happy to do that. I was glad that I had actually thought of this case. At any rate, everything was working fine. If that customer could get this topology wrong, it was right to make the product include the spanning tree algorithm.
Spanning tree Ethernet is a kludge, you don't get optimal paths. The traffic gets concentrated on the links that are selected to be in the tree, and the other ones are unused. Temporary loops are incredibly dangerous, because the header has no hop count. Why was bridging so popular? Originally, there were lots of layer 3 protocols: IPX, AppleTalk, IP, DECnet. You would need a lot of different routers in order to let everybody on one Ethernet talk to the other. Or people did make multiprotocol routers, but they were very expensive and slow, whereas bridges just worked and they were cheap. Zero configuration was required. You just plugged it together and it worked. Bridges wound up helping IP be much more tolerable, as we'll talk about later.
Why Do We Need Both Ethernet and IP?
Why do we need both Ethernet and IP, given that Ethernet is just point to point links today? Why not just interconnect everything with IP? The world has converged to IP as layer 3. You don't have to worry about AppleTalk or IPX anymore. It's in all of the network stacks. The original reasons for needing bridged Ethernet is gone. On a link with just two nodes, why do you need this extra header with the 6-byte source and a 6-byte destination when there's no need for any source or destination? If you hear something, it's for you. If you send something, it's for whoever's on the other side. Why can't we just plug everything together with layer 3? There were other layer 3 protocols that would have worked, and we wouldn't have needed the Ethernet header anymore. IP doesn't work that way. If IP were designed differently, we could get rid of this, the world would be much simpler. What's wrong with IP? IP is configuration intensive. Moving like a VM around from one side of a router to another, you'd have to change its address. Every link must have a unique block of addresses. If you have a block of addresses, you have to carve up the address space to have a different block on each link. Each router needs to be configured with which block of addresses are on which ports. If something moves, its address changes. You can't have a cloud with a flat address space where people would like to have a cloud, like a data center where you can move things around without changing their address.
With IP, each link has a different address block. If you move from one side of this router to the other, you have to change your address. Layer 3 doesn't have to work that way. For instance, a CLNP was a competing layer 3 protocol. When I was doing DECnet, when I started out, it had a 2-byte address, and we all realized, it needs a bigger address. Rather than trying to invent a new format, I looked at CLNP and said, this looks fine. It was a 20-byte address. With a 20-byte address, the way CLNP worked, the top 14 bytes was a prefix shared by all the nodes in a large cloud, and the clouds could support hundreds and thousands of endnodes and lots of links. The bottom 6 bytes were your specific node ID inside the cloud. For instance, your Ethernet address, you could use that and put that into the bottom 6 bytes. Inside the cloud, routers ignored this part. They just make sure, yes, it's inside my cloud, and then they route to the specific endnode here. If it's outside your cloud, then you route just like IP does but with a 14-byte address that can have as many levels of hierarchy as you want. In order to find the endnodes within the cloud, there was an extra protocol known as ES-IS where the endnodes periodically tell the router, I'm here in case anybody wants me.
With CLNP, the 14-byte prefix allows you to find the right cloud. Once you're at that cloud, you route based on the bottom 6 bytes. If you're using IP Plus Ethernet, in order to have a cloud that you can move around in, so Ethernet disguises a multi-link network to IP so that IP thinks it's a single link, so you don't have any IP routers inside of here. IP will get you to the destination link. Then, IP has to do ARP. It has to shout, who has this IP address inside of here? Whoever does will answer, it's me, and my Ethernet address is alpha. Then this router can forward into the cloud by adding the extra Ethernet header. Inside the cloud, IP just depends on some other technology like CSMA/CD, or spanning tree, or TRILL, or VXLAN, in order to glue a bunch of links together so that it looks to IP like a single link. In contrast, with CLNP, the top 14 bytes get you to the cloud. Then you don't need to do ARP or anything, or add an extra header, you just forward into the cloud, and routers inside the cloud know to route based on the bottom 6 bytes.
With hierarchy, if you have a block of addresses, you have to carve it up and configure everything with IP. With CLNP inside the cloud, zero configuration, you just plug it all together and it self-organizes. You don't have to tell the routers anything except one router has to be told what the 14-byte prefix for the cloud is. Then it will tell everybody else. The worst decision ever was that in 1992, people said, IPv4 addresses, 4 bytes are really too small, why don't we adopt CLNP with their 20-byte address. Somebody modified TCP to work on top of CLNP, and it was very easy for them to do it. It didn't take them like a month or something at most. That meant that all of the internet applications automatically worked on top of CLNP. It was much easier to change the internet back then, to a new layer 3 protocol because the internet was much smaller, it wasn't so mission critical, and IP hadn't yet invented things like DHCP and NAT. CLNP gave understandable advantages. You don't have to configure all the endnodes anymore, for instance. CNLP was much cleaner than IP. This level 1 of CLNP, level 1 routing was where you're routing based on the bottom 6 bytes. It's a cloud with flat addresses, and true layer 3 routing with a hop count and best paths.
The reasons given at the time not to adopt CLNP was it would be ripping out the heart of the internet and putting in a foreign thing. Or, we don't like ISO layer 6, or we're not immediately out of IPv4 addresses, and I'm sure we could invent something way more brilliant. The decision was, let's do something new, and whatever it is, we're going to call it IPv6. IPv6 is just a 16-byte version of IP with 8 bytes for the prefix and 8 bytes for the node ID on the last link. Eight bytes on top is inconveniently small for administering addresses, and 8 bytes on the bottom is way too much. For instance, once they did DHCP, where you have a node that's handing out addresses, 3 or 4 bytes would be more than sufficient. Why didn't they just do 6 bytes because Ethernet addresses were 6 bytes? At the time people were thinking, people might run out of the 6-byte addresses, so maybe they'll convert to an 8-byte address, the unique ID. The 8-byte unique IDs I don't think really caught on. IPv6 is technically inferior to CLNP, which is very frustrating even if we do wind up converting to it. Because IPv6 like IPv4 needs a different prefix on each link.
Some Other Protocol Observations, and Parameters
Some other protocol observations, parameters. I hate computers. I design things for people like me, which is just plug them together, and they work. Someone complained to me when I was at Digital that some customers found the bridge is boring, because they can't do anything with it, you just plug it together and it works. Some customers like to fiddle with things. I said, fine, if they want knobs, I'll give them knobs. They don't have to touch the knobs. Even if they do, they can't hurt themselves, because all settings will work. With parameters, if you do have parameters that people can set, of course, you need to do a sanity check to make sure they're setting it to a reasonable value. For instance, if the only legal values are between 30 and 50, don't let them set it to 70. That's easy enough to do. Sometimes, A and B have reasonable settings, but they won't interwork. An example of that is a protocol I was never able to explain to my otherwise bright college age son, which is that there's no such thing as a reliable I am dead now message. You have to periodically call your mother. Here's an opportunity for a parameter mismatch, which is how often you call your mother versus how long she waits before getting panicky and calling the police. What I did about that, was that in IS-IS, in the hello message where you say, "I'm still alive, link is still working." I put in the Hello Timer. In the IS-IS, the hello message says, "I'm Radia. I'm your neighbor on this link. Expect to hear hellos from me every 30 seconds." The neighbor says, "I'll multiply that by three or so. If I haven't heard from you for that amount of time, I'll declare the link down." OSPF pretty much copied IS-IS. They noticed the Hello Timer, and they put that in. What they did with it was that, when in OSPF if you receive a Hello Timer from your neighbor that says, "I'm Radia, expect to hear from me every 30 seconds." OSPF looks at it and compares it with its own configured Hello Timer, and if it's not identical, you refuse to talk. They haven't fixed it as far as I know. When I complained, I said, why not just adjust your Listen Timer? They said, it's just simpler, or something.
Latency, Fads, and Hype
Another short thing is latency. Suppose you care how long it takes to get a packet across the network? There's two ways of forwarding a packet. One is known as store-and-forward where each switch receives the entire packet, and then forwards it to the next one, versus cut-through, which says that as it's receiving the packet, once it can make a decision about what port to forward it on, assuming the port is free at the moment, it can immediately start forwarding. It's forwarding while it's receiving the packets. That will lower the latency across the network. What field do you need to see in order to make this forwarding decision? The destination address. Let's look at the IP header. The IPv4 header has the destination address as the last thing. The IPv6 header also has the destination as the last thing. Another thing to rant about are Fads. Every once in a while, somebody invents some doodad. People then take it and run and they come up with doodad specific jargon, and they design packet formats without asking, how would this compare with how it's done today? Is this useful in any sense? They convince someone in some funding agency that it's the next big thing so it gets funding. There's entire conferences about it. To get funding, people have to spin what they're actually working on as some aspect of doodad-ism. An example of things like these are active networks, name-based networks, otherwise known as content-centric networks. These things usually die out.
Another thing to rant about is hype. Blockchain is a great example of something that just got so much hype. It started as the technology behind Bitcoin. People made money on Bitcoin. The more they hyped it, the more money got poured in, and the more money they made. Startups leveraged the hype to claim their product has something to do with blockchain, and the money rolled in. After hearing so much hype, it's natural to assume blockchain must be important. There's lots of talk about how it's being considered for this and that, which is very different than it's actually being used for this or that, and also very different from it was the best solution for this or that. Companies were convinced to throw money at consortiums because people show slides with the logos of all the other companies that have already thrown the money at the consortium, and they don't want to miss out. People ask, how can I use blockchain in this application? Or, what can I build with blockchain? Instead, I say, no, start with, what problem are you solving? Look at various approaches and choose the best one. An engineer said to me, that sounds good, but what do I do? My manager really wants us to use blockchain. I said, fine, do what I said, which is start with what problem you're solving, compare solutions, and choose the best one. Build that and then tell your manager, I used blockchain. They'll never know the difference.
Theory vs. Practice
Theory versus practice. Secure communication on the internet. It's so straightforward in theory. We do this every day. It obviously works. A client wants to talk to a website, let's say, x.com. The client says, I want to talk to you. Prove that you're x.com. The website sends a certificate with cool crypto and great protocols. It proves that it owns the name, x.com. Then you can have a cryptographically protected conversation. What could go wrong? Let's look at reality. Usually, the user doesn't start with the DNS name, and instead does a search and gets some sort of obscure URL string. That's what a URL looks like. This is not something that humans really can deal with, even if the user finds the DNS name in the URL. I fell for a scam recently, so I understand the theory of all of this. I wanted to renew my Washington State driver's license. I knew it could be done online, so I did an internet search for, "Renew Washington State driver's license." I got search results. I clicked on the top listed site. It didn't occur to me that the top search wouldn't be correct. This is the first one that I got, and I clicked on it. As it turns out, it did say, Ad. Even when you're searching for things, often the one you want still gets promoted to the top because they paid money to the internet search people. I didn't notice anyway. I clicked on it, and everything was as I expected. It was this very nice site. Look how happy all these people are. It couldn't possibly be a scam. I clicked on renew driver's license, and it asked me everything that I expected, like, what's your address? What's your license number? What's your credit card number? I told it all of that, and success. I would have thought nothing of it, except probably in a month or two I would have started wondering why I wasn't getting my new license. These guys were overly greedy and they kept charging more money, so eventually the bank fraud department called me up and said, "Are these legitimate charges?" At that point I realized, probably this was not a real site. I told them, no, it wasn't legitimate. They disallowed the charges and gave me new credit card numbers. I wasn't harmed in any way, and it gives me a great example.
This is quite shocking because, given that users don't automatically know the right DNS name, and why should they? There is absolutely no security on the internet, even though we have all of this fancy crypto and wonderful protocols. Don't blame the user. Scam sites can appear first after the search, either because they pay the search engine company, or because they understand the ranking algorithm and they can game the system. The particular scam I did now seems to have been shut down, but it had different names for all 50 states, washingtonlicensing.org, idaholicensing.org, or dmv.washington.org, dmv.ohio.org. They were all probably the same site, and just sitting there collecting credit numbers. At the time, once I realized it was a scam, I didn't know what to do. How do you manage to alert the search engine, this thing is a scam. Somebody probably eventually figured out how to do it. I happened to know Vin Cerf, so I sent him an email saying, "Do you know how to report anything like this?" The site I should have gone to was dol.wa.gov. I claim I did nothing wrong. There's no reason why I should be expected to have known that.
This is something I want everyone to take to heart. It's something I wrote in our book, and once I wrote this paragraph I said, yes, this is absolutely true. Everyone should memorize it and take it to heart. I've seen it on quote words. "Humans are incapable of securely storing high-quality cryptographic keys, and they have unacceptable speed and accuracy when performing cryptographic operations. They are also large, expensive to maintain, difficult to manage, and they pollute the environment. It is astonishing that these devices continue to be manufactured and deployed, but they are sufficiently pervasive that we must design our systems around their limitations." That's a challenge for people. Don't blame the users, figure out how to make things work.
See more presentations with transcripts
