How Digital Equipment Corp. engineers saved Ethernet

Metcalfe received the IEEE Honorary Medal in 1996 and the Turing Award from the Association for Computing Machinery in 2022 for his work. But these are well-known facts. There is another story about Ethernet that few people know.

In the 1980s and early 1990s, I led a group of advanced network technology developments at Digital Equipment Corp. (DEC) in Massachusetts. I had the opportunity to witness the development of local network technologies during a period of great opportunities and fierce competition between different standards.

All companies, including DEC, Intel, and Xerox, tried in one way or another to adapt Ethernet, which appeared back in the 70s, to extract maximum profit. But in the 1980s, competitors to Ethernet emerged 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. First, it is a 48-bit MAC address — a unique number assigned at the stage of manufacturing the device's network port. MAC addresses are used only within the local network, but they are extremely important for its operation. Usually, along with general-purpose computers, there is at least one special-purpose device in the network — a router, whose main task 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 referred to as L2 — the data link layer. Routers mostly deal with network addresses that are used both within the local network and beyond. With some exceptions, the IP address (network address) in the data packet is sufficient for this packet to be delivered to any point on the Internet via a chain of other routers managed by service providers and communication operators. Routers and the operations they perform belong to L3 — the network layer.

In a local network with Token Ring, a shielded copper twisted pair connects each computer with its neighbors in an infinite ring structure. Each computer forwards data from the upstream neighbor to the downstream neighbor, 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 local network with Token Bus, all computers in the network are connected by a coaxial cable, but the wiring does not determine the order in which they transmit tokens. The devices agree on the sequence of token transmission, forming an infinite virtual ring through which both data and tokens circulate.

Ethernet, meanwhile, has become the standard for connecting devices via coaxial cable. To manage data transmission, it used the Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) method. Computers planning to transmit a data packet first check if their neighbors are transmitting anything. If no transmission is occurring, the computer sends its packet while simultaneously monitoring for a collision with a packet from another computer. Why can collisions occur? For example, because the signal between devices is not transmitted instantaneously. In the event of a collision, the sending computer retransmits its packet with a delay that has both a random and an exponentially increasing component, depending on the number of collisions.

The need for collision detection implies a compromise between data transfer speed, physical cable length, and minimum packet size. Increasing the data transfer speed 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 tracks.

Optical Threat

Meanwhile, a whole coalition of companies, including my employer, DEC, was developing a new ANSI LAN standard: Fiber Distributed Data Interface. The FDDI technology provided for the use of a variation of Token Bus for data transmission over optical fiber at speeds up to 100 Mbps, which was an order of magnitude faster than the 10 Mbps available with Ethernet.

A number of technical publications published the results of an analysis of the bandwidth and delays of competing local network technologies under various workloads. Given the results obtained and the increased network performance requirements due to the growth in processor speed, memory volumes, and non-volatile storage, the limited performance of Ethernet became a serious problem.

To create high-speed local networks, FDDI seemed a more advanced option than Ethernet, despite the fact that it used expensive components and complex technologies, especially in terms of fault recovery. However, all protocols for accessing shared resources 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 the accelerated version of Ethernet, would be to develop a new technology for local networks that provides store-and-forward transmission.

One fine evening in 1983, before leaving work to go home, I went to the office of Mark Kempf, the lead engineer and a member of my team. Mark was one of the best engineers I have ever worked with. He created the popular and highly demanded terminal server DECServer 100, which used the Local Area Transport (LAT) protocol developed by Bruce Mann from DEC's corporate architecture department.

I told Mark about my idea to use store-and-forward switching to improve local network performance.

And the very next morning, Mark presented me with the idea of a learning bridge (also known as a layer 2 switch or simply a switch):

• The bridge connects to two Ethernet local networks.

• By listening to all the traffic on each local network, it learns the MAC addresses of computers in both networks (remembering which computer is in which Ethernet network), and then selectively forwards the appropriate packets between the local networks based on the MAC address of the target device.

• Computers in both networks do not need to know the path their data will take in the extended local network — for them, this bridge is invisible.

At the same time, the bridge must be able to handle about 30,000 packets per second and decide whether to forward them further. Although the requirement of 30,000 packets per second was practically the limit for the Motorola 68000, Mark was confident that he could build a bridge supporting two Ethernet networks using only standard components, including a specialized device for searching 48-bit MAC addresses, which could be assembled using programmable logic arrays (PAL) and dedicated static RAM.

Mark's contribution did not receive wide recognition. The only exception is the textbook "Network Algorithmics" by George Varghese.

In a misconfigured network — for example, with bridges looping Ethernet networks — packets can circulate forever. We were confident that we could avoid such a problem. In the worst case, the product could be delivered without this protective feature. It was also obvious that a two-port device was only a starting point. In the future, multi-port solutions could be created, but they would require special components.

To coordinate the creation of the prototype of the learning bridge conceived by Mark, I submitted a proposal outlining the idea to management at three levels. 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 immediate supervisor at DEC, Tony Lauk, assigned several engineers and architects to solve the problem of packet looping in misconfigured networks. Within a couple of days, we had several potential solutions. Radia Perlman, an architect from Tony's group, proposed the perfect solution that we all unanimously supported: Spanning Tree Protocol (Translator's note: in Russian it is also called the "linking", "spanning" or "covering" tree protocol)

In Perlman's concept, bridges exchange information about themselves, select a "root" bridge based on specified criteria, and compute the minimum spanning tree (MST). MST is a mathematical structure that in this case describes how to efficiently connect local networks and bridges without loops. Thanks to MST, any bridge whose presence would create a loop was put into standby mode. A side benefit of this approach is the ability to quickly recover in case of bridge failure.

Mark developed the hardware and low-level code, taking into account synchronization features, and software engineer Bob Shelley prepared additional software. In 1986, DEC introduced a technology called LANBridge 100 (DEBET-AA).

And a little later, DEC released the DEBET-RC version, which supported 3-kilometer cables between bridges. Manuals for some DEBET-RC can be found on the Bitsavers website.

Mark's idea did not "reinvent" or displace Ethernet — that is its genius. By providing store-and-forward switching between existing Ethernet networks, bridges made it easy to upgrade networks as a whole. Since collisions did not spread 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 a single Ethernet cable isolated traffic on that segment, while the bridge still allowed data exchange with computers on other Ethernet cables.

This reduced traffic on both cables, increasing bandwidth 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 individual devices into a network.

This led to the gradual transition from CSMA/CD over coaxial cable to the copper and fiber optic lines commonly used today between devices and switches.

Speed is no longer dependent on collision detection limitations. Mark's solution completely changed people's perception of Ethernet.

The bridge could even have ports for different types of local area networks if the headers of the respective packets were similar enough.

Later, our team developed GIGAswitch, a multiport device supporting both Ethernet and FDDI.

The increased performance of bridges tempered the enthusiasm of developers of new network protocols. Subsequently, even FDDI disappeared from the market, unable to compete with faster versions of Ethernet.

Mark received a US patent for his device in 1986. DEC offered to license it for free, allowing any company to use this technology.

This led to the development of the IEEE standard. Well-known companies and startups began working on improving switching technology. Other improvements, including ASICs for switches, virtual local area networks, the development of faster and cheaper physical media and related electronics, all contributed to the longevity and popularity of Ethernet.

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 of these innovations are switches. The 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 dollars annually.

My boss Tony Lauk once said that the value of an architecture can be measured by the number of technological generations over which it will be in demand. It turns out that Ethernet has achieved tremendous success.

No one 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 maybe not—and without this solution, Ethernet would have been doomed to a slow but sure death.

I personally think that Mark not only saved Ethernet that day but also ensured its great future.