Although watching TV shows from the 1970s suggests otherwise, the era wasn't completely devoid of all things resembling modern communication systems. Sure, the 50Kbps modems that the ARPANET ran on were the size of refrigerators, and the widely used Bell 103 modems only transferred 300 bits per second. But long-distance digital communication was common enough, relative to the number of computers deployed. Terminals could also be hooked up to mainframe and minicomputers over relatively short distances with simple serial lines or with more complex multidrop systems. This was all well known; what was new in the '70s was the local area network (LAN). But how to connect all these machines?

The point of a LAN is to connect many more than just two systems, so a simple cable back and forth doesn't get the job done. Connecting several thousands of computers to a LAN can in theory be done using a star, a ring, or a bus topology. A star is obvious enough: every computer is connected to some central point. A bus consists of a single, long cable that computers connect to along its run. With a ring, a cable runs from the first computer to the second, from there to the third and so on until all participating systems are connected, and then the last is connected to the first, completing the ring.

In practice, things aren't so simple. Token Ring is a LAN technology that uses a ring topology, but you wouldn't know it by looking at the network cabling, because computers are hooked up to concentrators (similar to today's Ethernet switches). However, the cable does in fact form a ring, and Token Ring uses a somewhat complex token-passing system to determine which computer gets to send a packet at which time. A token circles the ring, and the system in possession of the token gets to transmit. Token Bus uses a physical bus topology, but also uses a token-passing scheme to arbitrate access to the bus. A token network's complexity makes it vulnerable to a number of failure modes, but such networks do have the advantage that performance is deterministic; it can be calculated precisely in advance, which is important in certain applications.

Advertisement

But in the end it was Ethernet that won the battle for LAN standardization through a combination of standards body politics and a clever, minimalist—and thus cheap to implement—design. It went on to obliterate the competition by seeking out and assimilating higher bitrate protocols and adding their technological distinctiveness to its own. Decades later, it had become ubiquitous.

If you've ever looked at the network cable protruding from your computer and wondered how Ethernet got started, how it has lasted so long, and how it works, wonder no more: here's the story.

Brought to you by Xerox PARC

Ethernet was invented by Bob Metcalfe and others at Xerox's Palo Alto Research Center in the mid-1970s. PARC's experimental Ethernet ran at 3Mbps, a "convenient data transfer rate [...] well below that of the computer's path to main memory," so packets wouldn't have to be buffered in Ethernet interfaces. The name comes from the luminiferous ether that was at one point thought to be the medium through which electromagnetic waves propagate, like sound waves propagate through air.

Ethernet used its cabling as radio "ether" by simply broadcasting packets over a thick coaxial line. Computers were connected to the Ethernet cable through "taps," where a hole is punched through the coax cladding and the outer conductor so a connection can be made to the inner conductor. The two ends of the coax cable—branching is not allowed—are fitted with terminating resistors that regulate the electrical properties of the cable so signals propagate throughout the length of the cable but don't reflect back. All computers see all packets pass by, but the Ethernet interface ignores packets that aren't addressed to the local computer or the broadcast address, so the software only has to process packets targeted at the receiving computer.

Other LAN technologies use extensive mechanisms to arbitrate access to the shared communication medium. Not Ethernet. I'm tempted to use the expression "the lunatics run the asylum," but that would be unfair to the clever distributed control mechanism developed at PARC. I'm sure that the mainframe and minicomputer makers of the era thought the asylum analogy wasn't far off, though.

Ethernet's media access control (MAC) procedures, known as "Carrier Sense Multiple Access with Collision Detect" (CSMA/CD), are based on ALOHAnet. This was a radio network between several Hawaiian islands set up in the early 1970s, where all the remote transmitters used the same frequency. Stations transmitted whenever they liked. Obviously, two of them might transmit at the same time, interfering with each other so both transmissions were lost.

Advertisement

To fix the problem, the central location acknowledges a packet if it was received correctly. If the sender doesn't see an acknowledgment, it tries to send the same packet again a little later. When a collision occurs because two stations transmit at the same time, the retransmissions make sure that the data gets across eventually.

Ethernet improves on ALOHAnet in several ways. First of all, Ethernet stations check to see if the ether is idle (carrier sense) and wait if they sense a signal. Second, once transmitting over the shared medium (multiple access), Ethernet stations check for interference by comparing the signal on the wire to the signal they're trying to send. If the two don't match, there must be a collision (collision detect). In that case, the transmission is broken off. Just to make sure that the source of the interfering transmission also detects a collision, upon detecting a collision, a station sends a "jam" signal for 32 bit times.

Both sides now know their transmission failed, so they start retransmission attempts using an exponential backoff procedure. On the one hand, it would be nice to retransmit as soon as possible to avoid wasting valuable bandwidth, but on the other hand, immediately having another collision defeats the purpose. So each Ethernet station maintains a maximum backoff time, counted as an integer value that is multiplied by the time it takes to transmit 512 bits. When a packet is successfully transmitted, the maximum backoff time is set to one. When a collision occurs, the maximum backoff time is doubled until it reaches 1024. The Ethernet system then selects an actual backoff time that's a random number below the maximum backoff time.

For instance, after the first collision, the maximum backoff time is 2, making the choices for the actual backoff time 0 and 1. Obviously, if two systems both select 0 or both select 1, which will happen 50 percent of the time, there is another collision. The maximum backoff then becomes 4, and the chances of another collision go down to 25 percent for two stations wanting to transmit. After 16 successive collisions, an Ethernet system gives up and throws away the packet.

There used to be a lot of fear, uncertainty, and doubt surrounding the performance impact of collisions. But in practice they're detected very quickly and the colliding transmissions are broken off. So collisions don't waste much time, and CSMA/CD Ethernet performance under load is actually quite good: in their paper from 1976 describing the experimental 3Mbps Ethernet, Bob Metcalfe and David Boggs showed that for packets of 500 bytes and larger, more than 95 percent of the network's capacity is used for successful transmissions, even if 256 computers all continuously have data to transmit. Pretty clever.