Early Token Ring Work at MIT

Noel Chiappa

Token Ring Local Area Networks (LANs) are now obsolete technologies,
but early work on them at MIT produced networks which have left
their mark on today's LANs. I start by telling the story of early
work at the Laboratory for Computer Science (LCS) at MIT on Token
Ring LANs (which we usually simply called 'rings', not 'token
rings', as was later usual industry practise). Some of the more
technical content below may bring back memories for people who lived
through the era of this technology.

Background and Beginnings

LCS got involved in rings almost by accident -- and I too wound up
involved in the ring work (and much else besides!) similarly
almost by accident.

In the mid-1970s, high-speed LANs were an obvious area of work, to
connect up the various mainframes and mid-size machines found in a
typical computing site of the day. Such LANs were designed to
provide relatively high throughputs (for those days, when 1
MBit/second was very fast) to modest numbers of computers over a
geographically fairly restricted scope (one building, or a small
group of them).

A particular LAN concept can be characterized along two main axes:
i) the method used to pass data to the interface stations
connecting user computers to the LAN, and ii) the access control
method used to mediate access to the LAN's resources. (The former
was often indicated by what people called the 'topology' of the
network, such as 'bus' or 'ring', which usually implied a
particular data distribution technique.)

In the case of token-ring LANs, they had i) point-point links
between pairs of stations that joined them all in a ring, with
each station repeating the data to its 'downstream' neighbour; ii)
a 'token' (a special bit pattern) circulated around the ring, and
a station which wanted to send a packet waited to see the token,
removed it from the ring, then sent its packet, finally emitting a
replacement token to indicate that the ring was 'free'. [Note 1]

Ethernet was a rival LAN technology being developed at the same
time. Ethernet -- both the 3MBit/second prototype done by PARC,
and the follow-on Dec-Intel-Xerox (DIX) 10 MBit/second commercial
version -- used i) a single wire 'bus' to which all the stations
were attached, and ii) used CSMA-CD ('Carrier Sense Multiple
Access with Collision Detection) as the control method. Very
briefly this meant that, like a conversation at a crowded dinner
table, a station listened for quiet before sending (Carrier
Sense), and stopped if its transmission collided with another
('Collision Detection'), to re-try after a short (random) backoff.

However, in the late 1970's, LANs weren't available 'off the
shelf'; anyone who wanted one had to build their own. So the
Computer System Research (CSR) group in LCS applied to DARPA (then
LCS's main funding source) for money to build and deploy a LAN.

It turned out that DARPA was already funding a group at UC Irvine
(UCI), under Professor Dave Farber, to build a 1 Mbit/second ring,
a development of a previous generation ring called the
Distributed Computing System. So DARPA, naturally enough, said
'why don't you go in with their project'. So MIT, un-wisely
perhaps, agreed.

I came on board the project around then, in the fall of 1977, via a
fortuitous (for me!) set of circumstances; as a computer science student at
MIT, I had some ideas for an operating system I wanted to work on,
and I thought Professor Jerry Saltzer (who I'd gotten to know
fairly well via taking a course where he was a recitation
instructor) might be able to help me find a way to try out my
(crazy!) ideas.

Jerry, it turned out, was off on sabbatical at IBM, so I was shown
in to the acting group leader, a person I'd never heard of before,
Dr. David Clark. Dave listened with some interest as I sketched
out my operating system ideas, as it turned out they were very similar
to some work he'd done.

After hearing me out, he had a proposal: they were about to take
delivery of the prototype ring interface (called the Local Network
Interface, or LNI), and DARPA had provided them with a PDP-11/40
with which to test the LNI.

(The LNI was designed to plug into a UNIBUS, initially the
standard I/O bus for the PDP-11 family of computers. The PDP-11/40
was a medium-power minicomputer. It was at that time the smallest
PDP-11 available that had the capability of running timesharing.)

Now, CSR was the group that had done Multics [Corbato], and they
had a whole flock of people who knew how to program Multics -- but
none of them knew anything about PDP-11's. As luck (for me) had
it, at that point in time, the MIT CS Department's introductory
course, 6.031, taught people to code in PDP-11 assembler in the
first part of the course. So although I didn't know _that_ much
about PDP-11's, I knew more than anyone else in CSR.

So Dave's proposed deal was that if I helped with the LNI by
writing diagnostics for it, they'd let me use the 11/40 to work on
my operating system ideas.

We were both pretty enthusiastic about the latter, but it turned
out that they never went anywhere. Instead, I got completely
involved with all the networking stuff, which, even then, was
obviously going to be a Really Big Deal.

Anyway, I signed on for this deal, and started to learn more about
our PDP-11, which was running Unix. I'd never worked with Unix,
although I friend of mine in a group which was running one had
briefly showed me a bit about it, and it had favourably impressed
me (as it did so many others). So my first step was to read all
the available Unix documentation from cover to cover. That, plus a
bit of experimental detective work, left me in good enough shape
to work out how to write simple stand-alone diagnostic programs,
and load them from disk.

Making the LNI Work

About that time the first prototype ring interface arrived. It had
never even been plugged in: the group at UCI has designed it, and
some combination of MIT and UCI had had the prototype produced by
a commercial shop (I don't know the details), and then it was
shipped to us.

The V1 (Version 1) LNI (there was a V2 design later one -- more on
that below) was a a 5-1/4" high unit for the standard 19" wide rack
used to hold larger PDP-11 systems. It consisted of what was
effectively a single large circuit board, using wire-wrap (a now
obsolete technology in which each chip socket had tall pins for
each contact, and clever devices took a wire, stripped an inch or
so of the insulation, and wrapped the resulting bare end around
the pin). UNIBUS cables connected it to the rest of the computer
(originally PDP-11s, later on a VAX-11/780, too).

The LNI had been designed at UC Irvine by a combination of Mike
Lyle and Paul Mockapetris (of later DNS fame), who were graduate
students at UCI at the time: Paul did the hardware which stored a
table of 8 dynamically loaded names (the 'name-table', his thesis
project -- more on this below), and Mike did the rest (the ring
and bus interfaces).

The digital hardware design that UCI produced was not what it
could have been -- to our cost. One example: the V1 LNI used
binary counters for state machines; it took the encoded output
from the counter chip, and ran it into an n-bit binary decoder
chip so that, as the state counted up, one output after another
became 'live', in a sequence that was, in theory, always ordered.

However, the changes in the outputs of the counter sometimes had
some timing variation between them as it counted up, and as a
result, as it counted from 'N' to 'N+1', the outputs could briefly
show some value other than 'N' or 'N + 1'. The decoder dutifully
processed the (very brief) alternative value, and so every so
often one got 'glitches' on the output lines -- glitches that
drove us half crazy, trying to find and fix.

Also, the LNI was a pretty complicated beast. The people at UCI
had decided that for their application (a distributed computing
system that supported mobile processes, etc.) they needed complex
naming capabilities, with the ability to have 'mask' bits (in both
the names -- AKA addresses -- stored in the LNI, and in the
message header) -- think of them as multicast [Multicast] on steroids.
A sub-system of the LNI called the name-table held 8 dynamically
loaded 32-bit names (including masks) which applied to that
interface.

The LNI had three major sub-systems: the UNIBUS interface, the
name-table, and the ring interface. Although each of them had only
limited connection with the other two, unfortunately there was no
way to fully debug one independently of the others. So working out
where exactly the latest bug was was always an 'exciting'
challenge. A lot of the LNI's hardware footprint was devoted to
the name-table, although it turned out that that part of the LNI
actually worked fairly well; the problems we had to find and fix
turned out to be mostly in the interface to the UNIBUS, and in the
hardware to drive the ring.

The person tasked with debugging the LNI was Ken Pogran, a staff
member in CSR. An MIT graduate, while at school he could not
decide between hardware and software, so although he was doing
programming just before the LNI work, he was ideal for the LNI,
and enthusiastic at the chance of doing some hardware work. Soon
after the start, we hired a technician to help him, Joe Ricchio.
Ken set to debugging the LNI, and it quickly became clear that we
were in for a long slog.

I don't recall exactly what the first problem we found was; my
vague memory is that the first diagnostic I wrote simply tried to
read a register in the LNI, and if the attempt to read it failed,
to re-try it.

That kind of short, closed, loop you could watch on an
oscilloscope, but within a few days it became clear to Ken that an
oscilloscope was not going to cut it as we got further into
debugging more complex functions, so they hired in one of the
first logic analyzers to help, which was a wise move -- I don't
think we'd have ever gotten the LNI fully working without it. (We
first rented it, but eventually wound up buying it -- we used it
for so long it was cheaper that way!)

The UNIBUS had several operating modes. In the simplest, the CPU
could read or write from something attached to the bus (which
could be either memory, or a device). A more complex operation was
Direct Memory Access (DMA), in which a device asked the CPU to let
the device use the bus, and the device then did a read or write
cycle to computer memory itself. Finally, devices could use the
bus to request an interrupt on the CPU.

The LNI had to do all three of these, and we spent some time
getting that all to work. The DMA had to work well because the LNI
didn't have packet buffers; the packet had to be stored in
computer memory as it arrived.

We then would have moved on to trying to get the ring interface
part to work -- and that turned out to be fairly complicated, and
bug-ridden, too.

In addition to the normal processing of tokens, an LNI had to be
capable of 'initializing' the ring, i.e., introducing a token into
a quiescent ring. When sending a packet, the sending station
'drained' the packet off the ring; all the other stations
(including any destinations) merely watched the packet as it went
by. To prevent spurious tokens seeming to appear in data inside
packets, the LNI had to look at the data in the packet it was
sending, and 'bit-stuff' to convert any output data bit patterns
which looked like a token into an alternative form (a process which
the receiving station would of course have to undo).

The V1 LNI made heavy use of then-new programmable logic arrays
PLAs, which we wound up re-programming a lot as we got the LNI
working. The logistics of that were challenging, as we didn't have
a PLA programmer for quite a while, and we had to depend on the
kindness of the salesmen to use theirs!

But getting all that to work turned out not to be the only
problems. Others involved more purely electrical issues. The link
from one LNI to the next was a single twisted pair, with the data
and clock combined into a single self-timing signal. A big problem
(one we didn't really understand at the time) turned out to be
that the coding scheme used to combine the data and clock wasn't
guaranteed to have a "0" average voltage, so that produced a
varying DC offset (via the capacitance of the cable) which made
the signal harder to discern.

However, the biggest problem I remember had to do with clocking.
There was no master clock for the whole ring; each LNI had its
own. (In fact, there was no master station, which would have been
a single-point-of-failure -- all the LNIs were identical.)

To deal with the slight variation between the clocks on different
interfaces, the LNI used a system where each bit-time was divided
up into 6 slices (the LNI had a 6MHz master clock which was
divided down to 1MHz to provide a clock for the ring), and an LNI
which discovered that it was skewing from its neighbour could add
or subtract a slice to a particular bit on the input side (the
output side always sent at that particular LNI's 'native' clock
speed). I seem to recall we had some grief getting that all
working properly, since the rest of the circuitry had to stall or
skip one high-speed clock cycle, while the ring interface portion
kept running.

Eventually we did get the V1 LNI operating properly -- although it
took a lot of work. (The prototype unit had been wired with wire
which used blue insulation. When Ken made fixes, he used red wire.
By the time he was done, the first prototype had an incredible
amount of red wire in those parts of the board that interfaced to
the bus and the network. Only the part where the name-table was
stored was mostly still blue.)

Just about when were finally getting it running, we had a visit
from Someone Important (someone from DARPA, I assume), and I was
tasked to write a demo. All we had at that point in the way of
software was very small diagnostic programs, to do things like
send a packet, etc. So I quickly whipped up a simple demo that
involved the user typing on the keyboard of a terminal, and
sending the character around the ring in a packet, and then
displaying it. (I don't remember now whether this demo used two
computers, or one. It may have been two terminals attached to a
single computer.) Obviously, this would have been easy to fake,
but as I recall, it seemed to suffice.

The V2 LNI

We produced eight V1 LNIs, and put them into service to provide
data transmission to a number of the time-sharing machines at LCS
which were not fortunate enough to be on the ARPANET [Heart].

However, it was clear that mass production of network interfaces
was not really an appropriate use of LCS's resources. So we then
teamed up with a company called Proteon (whose boss, Howard
Salwen, had shared an office in graduate school with LCS'
Director, Michael Dertouzos) to design and produce the V2 LNI, a
follow-on 10 MBit/second commercial product.

Proteon at that point was mostly a specialty analog communication
shop, building things describable as 'N giga-hertz uplinks
for NASA' in small quantities. Involvement with the V2 LNI changed
their future completely.

The V2 LNI was not an evolution of the V1, but a wholly new
design. It came as a set of two smaller boards; we split it into
two boards because it would be necessary to plug into other kinds
of machines than just machines with a UNIBUS, and so there was a
Host Specific Board (HSB) and the ring interface card (CTL).

The V2 LNI used a totally different system for the clock. It used
a sophisticated purely analog system where the clocks in all the
machines in the rings independently adjusted their clock speeds
until there were an integral number of bit-times around the ring.

This too took forever to make work properly (as we deployed larger
number of stations on a single ring, the whole system went
un-stable, and would not lock up, and had to be modified). In a
later follow-on 100 MBit/second product from Proteon (the basis
for the open Fiber Distributed Data Interface ring standard [FDDI]),
they went back to the original V1 LNI approach of using digital
means to adjust bit-times, with independent, free-running clocks
in each interface.

In addition to the different ring clocking mechanism, and a higher
speed (10 MBits/second), we deleted the entire complex name-table
system. (We felt that that function, if needed, would be more
economically implemented in a software layer.) The programming
spec for the interface was considerably re-done, based on
experience with the V1 - an exercise which ended up in a memorable
blow-up between Jerry and me when I refused to follow his
instructions on one particular detail!

The detailed design of the interface to the host computer was also
entirely different;
the problems involved in interfacing between an asynchronous bus
(the UNIBUS) and a system with a fixed clock (the ring) led me to
indicate to the the engineer at Proteon who was designing the host
interface card, Henry Arbour, that we should use a design
technique that MIT was then pushing in its introductory digital
design course, 6.032, which used entirely un-clocked logic.

So we did all that, and the V2 LNI UNIBUS host interface card
worked very well from the start (the prototype had only about two
dozen fix wires on it, unlike the V1 LNI),
and with small changes was modified to produce
host interface cards for the Q-Bus (a lower-cost bus from DEC for
the LSI-11 family) and the Multibus.

The V2 LNI, and its successor, the 100 Mbit Proteon ring, went on
to become very successful products for Proteon -- although the
full story of Proteon is for another day.

Legacy of the V1 LNI

The V1 LNI did contribute one thing that remains with us today --
its network wiring pattern, originally called the 'star-shaped
ring'.

The big downside of the ring seemed to be the repeater aspect
(since a failing node could take down the whole ring), but MIT did
a lot to address that aspect.

Obviously, with a hard-wired ring, where each machine is an active
repeater, if one machine is powered off, the ring ceases to work.
Putting a relay at each machine, to pass the signals through if
the machine is powered down, is
one approach to deal with this, but it has potential issues.

First, if several machines in a row are powered off, due to the increased
wire length, it's not
clear if the signal will make it all the way from the last one
prior to the powered off group, all the way through to the next
functioning machine. Second, if an interface suffers a hardware
failure in the repeating circuitry, that also can take the entire
ring out.

So, with input from Jerry Saltzer [Saltzer80], MIT developed the
concept of the 'star-shaped ring': there's a central wiring point,
and a wire runs out to each interface, and then back to the wiring
point.

For the V1 LNI, the device at the center was a passive box, and if
one wanted to power down a machine, one had to trundle over to the
wiring point, and un-plug the line to that machine, and plug in a
jumper instead.

For the V2LNI (and other later rings), there was a relay on each
port at the central box which normally bypassed the cable run out
to each node, and the interface included a line from that computer
to energize the relay and cut that node into the ring.

IBM turned out a ring design (done by IBM Zurich, completely
independent of the MIT work, which reached many of the same
design conclusions) which was eventually standardized
as IEEE standard 802.5. It originally operated at 4
MBits/second, and was later upgraded to 16 MBits/second. It too
used the 'star-shaped ring' wiring scheme, which had proved to
work quite well.

There weren't really any effforts in the standards world to pick
one standard (be it bus or ring); everyone did their own thing,
letting the market decide
which technology would win out. The whole process extended out
over a very long time.

The initial Xerox Experimental Ethernet preceded the MIT work; the MIT V1 LNI
preceded the DIX Ethernet; that was roughly
contemporaneous with the V2LNI (I remember Jerry getting info
through the grapevine, before the DIX specification became public,
that the DIX Ethernet was going to operate at 10 MBits/second, so
he insisted we boost the speed of the V2 LNI to match). The IBM
ring LAN came along some time later, shortly before Proteon did the 100
Mbit/second ring.

Rings and Busses

Rings eventually faded away, which could lead one to think that
bus systems 'won' -- but in fact, the typical 'Ethernet' of today
is fundamentally different from the original Ethernet. Ironically,
the evolution of Ethernet has led to networking systems which in
many ways very closely resemble the star-shaped ring networks of
the past; the 'hub and spoke' wiring scheme for LANs which rings
pioneered has proven its utility, and is now ubiquitous

Ethernet had originally used the Xerox PARC technique of deploying
a single wire (the 'bus') running the length of the network, and
having individual stations tap into that wire (originally, via
actually drilling a hole in the co-axial cable used back then).

That large bus has been replaced by a system of point-point links
which run from host interfaces to active repeaters/hubs/switches,
which are similarly inter-connected among themselves by
point-point links. This produces a star-shaped wiring scheme
(without the relays), which consist (at the electrical level)
exclusively of point to point links.

Why did this happen? There are a number of factors which led to
the systems we see today.

The ring people had initially seen two advantages to token rings
over CSMA-CD busses. First, the analog electrical environment of
rings was _much_ simpler -- one transmitter, a wire, one receiver.
Second, theoretical studies indicated the token access control
would behave better than CSMA-CD at very high loadings (although
this latter turned out to be a non-issue, as LANs were never
loaded that highly for long periods of time).

Although the latter point was not significant, the former was:
point-point links are both easier to work with from an analog
point of view, and also are more welcoming to new transmission
techniques, e.g., optical. (In fact, an early MIT ring deployment
was an optical link from the LCS building, the famed 545
Technology Square, to the main campus. Getting there involved
going under some train tracks, and that was difficult. Proteon
produced an optical link using a laser, and we set one up in a
window on each side.)

For Ethernet, doing point-point cable runs to a multi-port 'hub'
which placed all the transceivers on a short 'bus' inside the box,
solved the analog issues with connecting lots of stations to a
large bus (noise, reflections, etc).

Second, even with only point-point cable runs, the CSMA-CD access
control method did not scale very well (in either speed or
distance). It turned out that that was the real, unavoidable,
problem with CSMA-CD (one not clearly seen in the early days); as
the speed and/or physical size of the network went up, it needed
longer packets to make sure it didn't have an 'unseen' collision.
In other words, with CSMA-CD, there was a fundamental relationship
between speed, network physical size, and minimum packet size:
increasing either of the first two required increasing the last.
The CSMA-CD access control method could not scale up.

Early Ethernets often used analog or digital repeaters (to reduce
analog noise, reflection, etc issues), but the 'contention zone'
over which the CSMA-CD mechanism functioned extended out to all
the interfaces connected to such repeaters. Use of analog or
digital repeaters (any of which could clean up the signal) could
reduce the analog issues, but they couldn't get around the
fundamental problem of the speed/size limitations of CSMA-CD.

When 100 Mbit/second Ethernet appeared, to accomodate stations
operating at different speeds, the connecting nodes became bridges
(packet switches), and not simply bit-by-bit repeaters -- in other
words, the contention zones (which were a problem for the reason
above) disappeared, as the network became a collection of packet
switches.

With all the wires (both switch-switch, and switch-interface)
being point-point links, and with the links being connected via
active circuitry, today's 'Ethernet' is, in electrical terms, far
more similar to the early rings than it is to the early Ethernets.
The major difference with rings is that there is no circulation
(i.e., repetition of data from station to station).

Thus, ironically, one of the major claimed 'advantages' of
Ethernet over rings -- that its coaxial cable transmission medium
was totally passive, with no dependence on the correct operation
of active circuitry -- disappeared. Not that anyone really cares --
in practise, everything works fine.

With today's 'Ethernet' network not really using contention any
more as a channel access method, but instead being an interface
specification used to connect stations to a packet-switching node,
neither the original CSMA-CD busses, nor token rings, truly live on.

Like the screw base for light bulbs (and many other examples), the
equipment on either side of the interface has changed out of all
recognition, and only the Cheshire Cat's smile of the interface
lives on.

Acknowledgements

A heart-felt 'Thank You' to Jerry Saltzer and Ken Pogran for
taking the time to review an early draft, and both catch a number
of errors of fact, as well as also producing helpful editorial
comments.

References and Notes:

[Corbato]	F. J. Corbato, V. A. Vyssotsky, "Introduction and Overview of the
			Multics	System", AFIPS FJCC (1965)

[Heart]		Frank Heart, Robert Kahn, Severo Ornstein, William Crowther,
			David Walden, "The Interface Message Processor for
			the ARPA Computer Network", AFIPS SJCC, AFIPS Proc.
			36: 551-567 (1970).

[Saltzer80]	Jerome H. Saltzer, Kenneth T. Pogran, "A Star-Shaped Ring
			Network with High Maintainability",
			Computer Networks 4: 239-244 (1980)

[Saltzer83]	Jerome H. Saltzer, Kenneth T. Pogran, David D. Clark,
			"Why a Ring?", Computer Networks 7: 223-231 (1983)

[FDDI]		[To be added]

[Multicast]	[To be added]

Note 1: A proposal by a particularly clever MIT undergraduate for
something called a 'contention ring', which still circulated bits
around a ring, but did not use a circulating token, instead
contending for access to the channel a la Ethernet, showed that the
circulation is truly the most fundamental thing about ring
networks, not the token, which is purely a channel access control
mechanism.