Post a Comment On: Ken Shirriff's blog

code {background-color:#eee;font-size: 80%;} .gist table.lines { font-size: 12px; line-height: 10px; } .gist-meta { font-size: 80% !important; } .gist .blob-num { line-height: 10px !important;} .gist .blob-code { line-height: 10px !important;} The Alto was a revolutionary computer designed at Xerox PARC in 1973. It introduced the GUI, high-resolution bitmapped displays, the optical mouse and laser printers to the world. But one of its most important contributions was Ethernet, the local area network that is still heavily used today. While modern Ethernets handle up to 100 gigabits per second, the Alto's Ethernet was much slower, just 3 megabits per second over coaxial cable. Even so, the Alto used the Ethernet for file servers, email, distributed games, network boot, and even voice over Ethernet. The Alto's 3 Mb/s Ethernet isn't compatible with modern Ethernet, making it difficult to transfer data between an Alto and the outside world. To solve this, I built a gateway using the BeagleBone single-board computer to communicate with the Alto's Ethernet. In this article I discuss how the Alto's Ethernet works and how I implemented the gateway. The Alto's Ethernet hardware The Alto's Ethernet used a coaxial cable, rather than modern twisted-pair cable. A transceiver box was the interface between the Alto and the cable, converting the Alto's logic signals to the signals on the cable. In the photo below, you can see a transceiver clamped onto the coaxial cable; a "vampire tap" punctures the cable making contact with the central conductor. [Image]Inside a transceiver box. The "vampire tap" on the right connects the transceiver to the Ethernet cable. The connector on the left goes to the Alto. The Alto's Ethernet uses Manchester encoding of the bits. That is, a "1" is sent as "10" and a "0" is sent as "01". The reason to do this instead of just sending the raw bits is the Manchester encoding is self-clocking—there's a transition for every bit. If instead you just sent a raw stream of bits, e.g. "00000000000", the receiver would have a hard time knowing where the bits start and end. The figure below shows how 0110 is transmitted with Manchester encoding. [Image]An example of Manchester encoding, for the bits 0110. The Alto's network protocols The Alto predates TCP/IP, instead using a protocol called Pup (the PARC Universal Packet).1 The protocol has many similarities with TCP/IP, since the Pup designers influenced the TCP design based on their experience. The basic Pup Internet Datagram is analogous to an IP packet. A packet contains a destination address for the packet consisting of a network id (1 byte), a host id on the network (1 byte), and a 4-byte socket. A machine's host id is specified by jumper wires on the backplane (below). Thus, packets can be routed through a large network to the right machine. [Image]Long blue jumper wires on the Alto's backplane specify the system's Ethernet address. Some simple network operations just exchanged Pup packets, for example requesting the time from a network server. But for more complex operations, Xerox built layers on top of Pup. For a long-lived connection between two machines, Xerox built RTP (Rendezvous/Termination Protocol), a protocol to establish connections between two ports. This is analogous to a TCP socket connection. Once the connection is established, the computers can communicate using Byte Steam Protocol (BSP). This protocol handles error correction and flow control, very similar to TCP. On top of these protocols, Xerox implemented email, FTP (File Transfer Protocol), network boot, networked games such as Maze War, network error reporting, network disk backups and the first computer worm. [Image]Map of the Xerox PARC network, showing important servers. May 1978. From Alto User's Primer. Designing an Ethernet gateway I decided to build a gateway that would allow the Alto to communicate with a modern system. The gateway would communicate with the Alto using its obsolete 3Mb/s Ethernet, but could also communicate with the outside world. This would let us network boot the Alto, transfer files to and from the Alto and backup disks. I expected this project to take a few weeks, but it ended up taking a year. The first decision was what hardware platform to use. My plan was to use a microcontroller to generate the 3Mb/s signals by "bit banging", i.e. directly generating the 1's and 0's on the wire. (A regular processor couldn't handle this in real time, due to interrupts and task switching.) But a microcontroller wouldn't be suitable for running the network stack and communicating with the outside world; I'd need a "real computer" for that. Someone suggested the BeagleBone: a credit-card sized Linux computer with an ARM processor that also incorporated two microcontrollers. This would provide a compact, low-cost implementation, so I started investigating the BeagleBone. [Image]The BeagleBone single-board Linux computer is small enough to fit in an Altoids tin. It has many general/purpose I/O pins, accessible through the connectors along the top and bottom of the board. The BeagleBone's microcontrollers, called PRUs,2 are designed to run each instruction in a single 5ns cycle. Since the Ethernet pulses are 170ns wide, I figured I had plenty of time to send and receive signals. (It turned out that getting everything done in 170ns was challenging, but it worked out in the end.) In my gateway, the PRU reads the Ethernet signal coming from the Alto, and generate the Ethernet signal going to the Alto, as well as sending a network collision signal to the Alto. In case you're wondering what PRU code looks like, the C code fragment below shows how a byte is encoded and sent. The PRU code outputs the right sequence of HIGH/LOW or LOW/HIGH pulses (the Manchester encoding), making sure each part is 170ns wide. Each bit of register R30 controls an output pin, so the bit for the Ethernet write pin is set and cleared as needed. wait_for_pwm_timer() provides the 170ns timing for each pulse. The full code is here. To receive data from Ethernet, my PRU code doesn't do any decoding; it just measures the time between input transitions and sends these timings to the BeagleBone's ARM processor. Originally my code decoded the Manchester encoding into bits and assembled the bits into words, but 170ns wasn't enough time to do this reliably. Instead, since this decoding doesn't need to be done in real time, I moved the decoding to the more powerful ARM processor. The ARM processor also does the higher-level Ethernet protocol handling, such as generating and checking packet checksums. Rather than deal with transceivers and coaxial cable, I connected the BeagleBone to the Alto's Ethernet port directly, omitting the transceiver that normally connects to this port. This port provides standard 5V TTL signals to the transceiver, but the BeagleBone inconveniently uses 3.3V signals. I needed a circuit to translate the voltage levels between the BeagleBone and the Alto. This should have been easy, but I ran into various problems along the way. [Image]On the back of the Alto, Ethernet is accessed via a DB-25 connector that connects to a transceiver box. I built a prototype voltage translation circuit on a breadboard, using a 74AHCT125 level shifter chip (schematic). However, I was getting no Ethernet signal at all from the Alto, so I started probing the Alto's board for a malfunction. I discovered that although the Alto's schematic showed pull-up resistors, these resistors didn't exist on the Alto's Ethernet board (see photo below). Without a resistor, the open-collector signal stayed at ground. Adding the resistors to my circuit fixed that problem. [Image]One problem I encountered was termination resistors R8 and R9 appeared on the schematic but were missing from the board (above the word "ETHERNET"). The next step was to write the PRU microcontroller code to send and receive Ethernet packets. After a lot of testing with the Alto's Ethernet Diagnostic Program (EDP), I was able to echo packets back and forth between the BeagleBone gateway and the Alto. [Image]The Ethernet Diagnostic Program can be used to test the Ethernet. It has a simple GUI. To be useful, the gateway must support the network stack: Pup packets, network booting, Alto-style FTP and so forth. I started by rewriting the Alto's network code, making a direct port of the BCPL implementation3 to Python. This turned out to be a mess, because the original implementation depended heavily on the Alto's operating system, which provided multiple threads, so the application could run in one thread and the network code in other threads. I managed to get the stateless low-level Pup packets to work okay, but the higher-level Byte Stream Protocol was a tangle of busy-waiting loops and timeouts. Fortunately the Living Computers Museum+Lab (LCM+L) came to rescue. Josh Dersch at the museum had written a C# implementation of the Alto's network stack, so I decided to discard my implementation of the network stack. This implementation, called IFS,4 supported the low-level protocols, as well as servers for network operations, FTP, and Copydisk. IFS was a new implementation rather than a direct port like my attempt, and that approach worked much better. [Image]The Living Computers Museum built a 3 Mb/s Ethernet interface using an FPGA chip. The LCM+L also built an Ethernet interface to the Alto. Theirs was much more complex than mine, consisting of an FPGA chip on a custom PCI card plugged into a PC. Unlike my interface, theirs communicated with a transceiver box, rather than connecting to the Alto directly. Even though the LCM+L's FPGA interface worked for us, I decided to complete my interface board since I liked the idea of a low-cost, compact Ethernet gateway. Their interface is more "realistic", since it connects to a real transceiver and network cable and can work with multiple Altos on a network. (The photo below shows the mini-network connecting the LCM+L interface and an Alto.) On the other hand not everyone has Ethernet transceivers lying around, so mine is more widely usable. [Image]A very short 3 Mb/s Ethernet network, showing two transceivers attached to the coaxial cable. One transceiver is connected to the Alto and the other is connected to the LCM+L gateway card. I made a simple printed circuit board to replace my breadboarded prototype. This was the first circuit board I had designed in about 35 years and technology has certainly changed. Back in the 1980s, I drew circuit board traces with a resist pen on a copper-clad board, and then etched the board in ferric chloride solution from Radio Shack. Now, I designed my board using Eagle, uploaded the file to OSH Park, and received a beautiful circuit board a few days later. [Image]My 3 Mb/s Ethernet interface is a level-shifter card on a BeagleBone. Note the capacitor soldered directly to the driver IC to fix a ringing signal problem. Running the LCM+L's IFS software on the BeagleBone took some work since the BeagleBone runs Linux and IFS was written in C# for Windows. By using the Mono platform, I could run most of the C# code on the BeagleBone. However, the LCM+L software stack communicated with the gateway by encapsulating Alto Ethernet packets in a modern Ethernet packet, using a .Net Pcap library to access the raw Ethernet. Unfortunately, this library didn't work with Mono, so I rewrote the IFS encapsulation to use UDP. At this point the Alto and my BeagleBone implementation communicated most of the time, but there were a few tricky bugs to track down. The first problem was FTP would get sometimes bad packets. Eventually I discovered that I had mixed up byte and word counts in one place, and the large packets from FTP were overflowing the PRU's buffer. The next problem was that when I used Copydisk to copy a disk pack from the Alto to the BeagleBone, a dropped packet caused the network to lock up after a couple minutes. This was puzzling since the sender should retransmit the lost packet after a timeout and everything should recover (like TCP). After tedious debugging, I found that if the Alto and the BeagleBone transmitted packets close together, a race condition in my code caused a dropped packet.56 Then IFS neglected to send a necessary ack when it received an unexpected packet, so the Alto kept resending the wrong packet. After fixing both my gateway code and the IFS ack, the network ran without problems. [Image]Second version of the interface. Note the blue jumper wire to replace the missing trace. My first version of the PCB had a few issues8 so I made a second version (above). I found that the driver chip didn't sink enough current for a long cable, so I replaced it with the chip used by the transceivers (a 7438 open collector NAND gate). I also decided to try KiCad instead of Eagle for the second board. Unfortunately, I made a mistake in KiCad7 and the new board was missing a trace, so I had to solder in a jumper (which you can seen in the photo above). [Image]I probed the Alto's Ethernet card with an oscilloscope to check the signals it was receiving. An extender card from the LCM+L allowed us to access the card. I tested the new board but it didn't work at all: the Alto wasn't receiving data or sending data. I realized that the new driver chip was a NAND gate so the signals were now inverted. I updated the PRU code to flip LOW and HIGH on the data out signal. The board still didn't work, so I probed the Alto's Ethernet board with an oscilloscope, comparing the signals from the old working board to the new failing board. Strangely, both signals were identical in the Alto and looked fine. Eventually Marc asked me if there could be something wrong with the collision detection. I realized that the the new NAND driver was also inverting the collision detection signal. Thus, the Alto was seeing constant network collisions and refused to send or receive anything. After fixing this in my PRU software, the new board worked fine. I'm making a third revision of the board to fix the missing trace; hopefully this won't break something else. [Image]An assortment of vintage Ethernet transceivers, along with the tap tools used to drill holes in the Ethernet cable for the vampire tap connection. Conclusion The Ethernet gateway project took much more time and encountered more problems than I expected. But it worked in the end, and several Alto owners are now using my gateway. I've open-sourced this interface (the board layout and the gateway software); it's available on github. The Alto I've been restoring came from YCombinator; the restoration team includes Marc Verdiell, Carl Claunch and Luca Severini. My full set of Alto posts is here and Marc's extensive videos of the restoration are here. Thanks to the Living Computers Museum+Labs for the IFS software. Follow me on Twitter or RSS to find out about my latest blog posts. Notes and references For more information on the Pup protocol, see Pup: An Internetwork Architecture and the Pup Specifications memo.  ↩ Programming the PRU microcontrollers has a difficult learning curve, and it's not nearly as well documented as, say, the Arduino. Based on my experience with the PRU, I wrote some programming tips here and here. ↩ The Alto's network code is online; you can look at one of the Pup files here. The code is written in BCPL, which was a predecssor to C. It is very similar to C, but with different syntactic choices. For instance, >> is not a shift but accesses a field in a structure. ↩ At PARC, IFS was an acronym for Interim File System, an Alto-based distributed file server. It was called interim because an improved system was being developed, but somehow a new system never replaced IFS. ↩ Most of the time, the BeagleBone and the Alto alternated sending packets. But every second, IFS sent a "breath of life" packet, the packet executed by the Alto to start a network boot. The breath of life packet was part of the original Alto—it simplified the network boot code since the Alto didn't need to request a network boot, but just listen for a second or two. Since the breath of life packet was asynchronous with respect to the other network traffic, eventually it would happen at a bad time for my code, triggering the dropped packet problem. ↩ The problem with the PRU and the "breath of life" packet was due to how I was sending signals between the PRU and the main BeagleBone processor. When sending a packet, the main processor would signal the PRU, and then wait for a signal back when the packet was sent. When a packet was received, the PRU would send a signal to the main processor. The problem was that the PRU sent the same signal in both cases. So a "packet received" signal at the wrong time could wake up the packet sending code, losing the received packet. Fundamentally, I was treating the signals between the main processor and the PRU as synchronous, when everything was really asynchronous. I rewrote the gateway code so ownership of the send and receive buffers was explicitly transferred between the main processor and the PRU. A signal just indicated that ownership had changed somehow; checking the buffer status showed what exactly had changed. See this discussion for details. ↩ My error in KiCad was I placed a net label just a bit too far from the wire on the schematic, so the wire wasn't connected to the net. ↩ My first PCB had a couple issues that I had to hack around. Ringing in the signal to the Alto corrupted it, so I added a damping capacitor. The driver didn't have enough current for an Ethernet cable longer than 10 feet, so I added a pull-down resistor. There were also a couple mechanical issues. The location of the Ethernet jack made it hard to remove the cable, and the board blocked one of the BeagleBone buttons. I also discovered that using a 74HC125 driver chip didn't work at all; just the 74AHCT125 worked. ↩