How engineers at Digital Equipment Corp. saved Ethernet
The technology of “learning” bridges they created made it possible to significantly increase the speed of local networks.
Ethernet protocol developed by computer scientists Robert Metcalfe And David Boggsundoubtedly, had a huge impact on the development of networks. Metcalf in 1996 received medal of honor IEEE, and in 2022 – Turing Award from Association for Computing Machinery for your work. But these are well-known facts. There is another story about Ethernet that few people know anymore.
In the 1980s and early 1990s, I led the advanced networking technology group at Digital Equipment Corp. (DEC) in Massachusetts. I had the opportunity to observe first-hand the development of local network technologies during a period of great opportunity and intense competition between different standards.
All companies, including DEC, Intel and Xerox, in one way or another tried to adapt Ethernet, which appeared back in the 70s, to maximize profits. But in the 1980s, competitors to Ethernet appeared on the market in the form of new local network technologies. Among the most notable were Token Ring, promoted by IBM, and Token Bus (today Ethernet and both token-based technologies are part of the IEEE 802 family of standards).
All these network technologies have a number of common fundamental properties. Firstly, it is a 48-bit MAC address – a unique number assigned at the manufacturing stage of the device’s network port. MAC addresses are used only within a local network, but they are extremely important for its operation. Usually, along with general-purpose computers, the network has at least one special-purpose device – a router, the main task of which is to send data to the Internet and receive it from there on behalf of all other computers on the local network.
In the concept of network technologies, which has existed for several decades, the local network itself (roughly speaking, cables and low-level equipment) is usually classified as L2 – the link level. Routers, for the most part, deal with network addresses that are used both within the local network and outside of it. With some exceptions, the IP address (network address) in a data packet is sufficient so that the packet can be delivered anywhere on the Internet through a chain of other routers operated by service providers and carriers. Routers and the operations they perform belong to L3 – the network layer.
In a Token Ring LAN, shielded twisted-pair copper wire connects each computer to its neighbors in an endless ring structure. Each computer sends data from an upstream neighbor to a downstream one, and can send its own data to the network only after receiving a short data packet – a token – from the upstream node. If it has no data to transmit, it simply passes the token to its downstream neighbor, and so on.
In a Token Bus LAN, all computers on the network are connected by coaxial cable, but the wiring does not determine the order in which they transfer tokens. The devices agree on the sequence of token transfers, forming an endless virtual ring through which both data and tokens circulate.
Ethernet, meanwhile, has become the standard for connecting devices via coaxial cable. It used Carrier Sense Multiple Access with Collision Avoidance (abbreviated as CSMA/CA) to control data transmission. Computers planning to transmit a packet of data first checked to see if their neighbors were transmitting anything. If no transmission occurs, the computer sends its own packet while monitoring to see if that packet collides with a packet from another computer. What can cause collisions? For example, due to the fact that the signal between devices is not transmitted instantly. If a collision is detected, the sending computer resends its packet with a delay that has both a random and an exponentially increasing component, which depends on the number of collisions.
The need for collision detection involves a trade-off between data rate, physical cable length, and minimum packet size. Increasing the data transfer rate by an order of magnitude means either reducing the physical length of the line or increasing the minimum packet size by approximately the same factor. Ethernet developers wisely chose the optimal option: 10 megabits per second and 1500-meter routes.
Optical threat
Meanwhile, a coalition of companies, including my employer, DEC, was developing a new ANSI LAN standard: Fiber Distributed Data Interface. FDDI technology used a variation of Token Bus to transmit data over optical fiber at speeds of up to 100 Mbps, which was an order of magnitude faster than the 10 Mbps available using Ethernet.
A number of technical publications have published analyzes of the throughput and latency of competing LAN technologies under various workloads. Given these results and the increased demands on network performance driven by faster processors, more memory, and more volatile storage, limited Ethernet performance has become a major concern.
For high-speed local area networks, FDDI seemed to be a more advanced option than Ethernet, despite the fact that it used expensive components and complex technologies, especially in terms of disaster recovery. However, all shared resource access protocols had a number of unpleasant features or performance limitations.
There is a solution!
It occurred to me that the best approach, compared to FDDI or Fast Ethernet, would be to develop a new technology for local area networks that provides a store-and-forward type of transmission.
One fine evening in 1983, before leaving work, I walked into my office. Mark Kempflead engineer and member of my team. Mark was one of the best engineers I have ever worked with. He created the popular and highly sought-after DECServer 100 terminal server, which used the Local Area Transport (LAT) protocol developed by Bruce Mann of DEC's Enterprise Architecture Department.
I told Mark about my idea of using store-and-forward switching to improve LAN performance.
And the very next morning Mark presented me with the idea of a trainee bridge (also known as a layer 2 switch or simply a switch):
The bridge connects to two Ethernet local networks.
By listening to all traffic on each LAN, it learns the MAC addresses of computers on both networks (by remembering which computer is on which Ethernet network), and then selectively forwards appropriate packets between LANs based on the target device's MAC address.
Computers on both networks do not need to know which path their data will take in the extended local network – this bridge is invisible to them.
In this case, the bridge should be able to receive about 30,000 packets per second and decide whether to forward them further. Although the 30,000 pps requirement was near the limit of the Motorola 68000's capabilities, Mark was confident that he could build a dual-Ethernet bridge using only off-the-shelf components, including a dedicated 48-bit MAC address lookup device. , which can be assembled on the basis of programmable logic arrays (PAL) and dedicated static random access memory.
Mark's contributions are not widely recognized. The only exception is the textbook “Network algorithms» George Varghese.
On a poorly configured network—for example, with bridges that loop Ethernet networks—packets can circulate forever. We were confident that we could avoid such a problem. As a last resort, the product could be supplied without this protective feature. It was also clear that the two-port device was just a starting point. In the future, it will be possible to create multiport solutions, but they will require special components.
To get approval for Mark's learning bridge prototype, I submitted a proposal outlining the idea to management at three levels at once. By the end of the day, we received the green light and realized that if the prototype was successful, the company would have a new product.
Development
My supervisor at DEC, Tony Lauck, assigned several engineers and architects to solve the problem of packet loops on misconfigured networks. Within a couple of days, we had several potential solutions at once. Radhya Perlmanan architect in Tony's group, came up with an ideal option that we all wholeheartedly supported: Spanning Tree Protocol (Translator's note: in Russian it is also called the “spanning”, “spanning” or “spanning” tree protocol.”)
In Perlman's concept, bridges exchange information about themselves, select a “root” bridge based on given criteria, and calculate a minimum spanning tree (MST). MST is a mathematical framework that, in this case, describes how to efficiently connect local area networks and bridges without loops. Thanks to MST, any bridge whose presence would create a loop was placed in redundant mode. A side benefit of this approach is the ability to quickly recover in the event of a bridge failure.
Mark developed the hardware and low-level timing code, and software engineer Bob Shelley contributed additional software. In 1986, DEC introduced a technology called LANBridge 100 (DEBET-AA).
A little later, DEC released a version of DEBET-RC, which already supported 3-kilometer cables between bridges. Manuals for some DEBET-RC can be found at Bitsavers website.
Mark's idea didn't “reinvent” or replace Ethernet—that's the genius of it. By providing store-and-forward switching between existing Ethernet networks, bridges made it easy to upgrade entire networks. Since collisions did not propagate beyond the bridge, connecting two Ethernet networks immediately doubled the maximum length of a single Ethernet cable. Moreover, placing computers that communicate intensively with each other on one Ethernet cable isolated the traffic on that section, while the bridge still allowed communication with computers on other Ethernet cables.
This reduced traffic on both cables, increasing throughput and reducing the frequency of collisions. Ultimately, this meant that each computer could be equipped with its own Ethernet cable, and a multiport bridge would connect the individual devices into a network.
This is what led to the gradual transition from CSMA/CD over coaxial cable to the ubiquitous copper and fiber optic links between devices and switches today.
Speed is no longer affected by collision detection limitations. Mark's solution completely changed the way people thought about Ethernet.
The bridge could even have ports for different types of local networks if the headers of the corresponding packets were similar enough.
Our team later developed GIGAswitch, a multi-port device that supports both Ethernet and FDDI.
The increase in bridge productivity has dampened the ardor of developers of new network protocols. Subsequently, even FDDI disappeared from the market, unable to withstand competition with faster versions of Ethernet.
Mark received US patent to your device in 1986. DEC offered to license it royalty-free, allowing any company to use the technology.
This led to the development of the IEEE standard. Well-known companies and startups have begun to work on improving switching technology. Other improvements, including switch ASICs, VLANs, and the development of faster and less expensive physical media and associated electronics, have all contributed to Ethernet's longevity and popularity.
The enduring value of Ethernet lies not in CSMA/CD or its original coaxial nature, but in the easily understandable and functional approach it provided to protocol developers.
Today, the direct heirs to these innovations are switches. Ports of modern switches used in data centers can operate at speeds from 40 to 800 gigabits per second. The market for these devices generates more than $10 billion annually.
My boss Tony Lauck once said that the value of architecture can be measured by the number of technological generations over which it will be in use. It turns out that Ethernet has been a huge success.
Nobody knows what would have happened to Ethernet if Mark had not invented his “learning” bridge. Perhaps someone else would have come up with a similar idea. Or perhaps not – and without this solution, Ethernet would have been doomed to a slow but certain death.
I personally think that Mark not only saved Ethernet that day, but also ensured a great future for it.
