Michael D. Schroeder, et al. Autonet: A high-speed, self-configuring local area network using point-to-point links. IEEE Journal on Selected Areas in Communications 9, 8, (October 1991) pages 1318-1335.
by J. H. Saltzer, March 6, 1996
A prerequisite to discussion of the Autonet paper is a clear understanding of the role of the link layer. One approach is to draw a picture of a workstation that has several physical links (a leased telephone line, a dialup line, an Ethernet, and two wires to an Autonet) coming out the back and ask the class to help develop the interface between the network layer and the link layer. This interface specification helps to clarify the need to distinguish between point-to-point links and multi-drop links, the need for the network layer to tell the link layer which link on which to send the message, and the distinction between the addresses used in the network layer (e.g., IP addresses) and the addresses used in the link layer (e.g., telephone numbers or Autonet port addresses.) Is the autonet point-to-point or multi-drop? (It looks to the attached system as a multi-drop link, even though it is internally constructed of point-to-point links, a link layer, and its own network layer. We have here a recursive use of the 6.033 reference model.) A good way to wrap up that preliminary discussion is to ask whether or not the two links from my workstation into the Autonet should be seen as two distinct physical links from the network level. (No. The Autonet design is that switchover from one link to the other should be done inside the link layer; in the SRC design the Autonet hardware controller does this job.) ---------- Autonet doesn't try to share a broadcast medium, and thus it avoids the grounding and signal-to-noise ratio problems of the Ethernet. 1. I want to install an Autonet to link 100 workstations and servers. I'm about to write the purchase order. How many Autonet switches should I order? This question will throw the class into utter, enlightening confusion. The answer depends on the topology you choose, and one can get into a lot of interesting tradeoff discussions. Suppose you want to take advantage of the twin-tail redundancy feature, having two connections from each workstation or server to the net. In that case you need 200 ports. With 12 ports per switch, it looks like you need at least 17 switches. But you have to use some ports to connect those 17 switches to each other. If you put the switches in a ring you use up 2 ports/switch for switch-to-switch links, leaving 10 workstation ports per switch, so you had better order 20 switches. In a ring configuration, any one switch can fail without denying service to anyone (assuming you were clever enough to not have both ports of some workstation go the the same switch!) Another possibility is the "double torus" connection . Arrange the switches in a square grid, connect each to its four nearest neighbors. At the edges, there isn't a neighbor on one side, so run a wire to the corresponding unconnected port at the other end of the same row (column) of switches. Now we are using 4 of the 12 ports on each switch for internal connections, and will need 25 switches, so a 5 x 5 array seems about right. 2. How robust is this configuration against failures? How much capacity does it provide? How many total megabits per second can we get between the set of workstations attached to switch 2 and the set of workstations attached to switch 7? 3. What is cut-through? (Most students will have only a vague idea of what it means.) When a packet is coming in wire 1, how soon can you start sending it out on wire 2? Do you have to wait for the whole packet to arrive? If the data rates on wire 1 and wire 2 are radically different, does the answer change? 4. What is a spanning tree? How do you build one? (Start with the network linked as you find it, and cross off links one at a time until you can't cross off any more without partitioning the network.) 5. Why do routes follow the up*-down* rule? What could go wrong if they didn't? 6. How does broadcast work? (1. Go up to the root of the spanning tree. 2. Go down just the spanning tree. This gets exactly one copy to everyone.) War story: there was a wonderful bug in the initial implementation of Autonet. An unterminated link wire would perfectly echo any data that was sent down it. This property was noticed immediately, but noone thought it mattered much. The first time someone disconnected a workstation from the net, the net locked up. Why? (Answer: Shortly after the disconnection, someone on the net initiated a broadcast. The broadcast went up to the root, then down along the spanning tree. When it hit the the unterminated link, the reflection came back looking like a new broadcast, which dutifully was passed up to the root, and then down along the spanning tree, forever looping. This bug falls in the category of surprises caused by interaction of seemingly unrelated features in a complex system.) 7. Are there layers inside the Autonet? (Yes, a link layer consisting of 100 Mb/sec coax cables running from one switch to the next, and a network layer that does routing and pushback.) 8. But Autonet is used as the link layer in bigger networks, isn't it? What is going on? (We are recursively applying the 6.033 reference model. Autonet is a link layer, but it is internally constructed as a two-layer network.) 9. The Autonet paper says that it is NOT an example of an ATM (Asynchronous Transfer Mode) network, yet the 6.033 reading assignment says that it is. What gives? (It isn't strictly ATM. It allows long, variable-length packets where ATM restricts use to short, fixed-length (53-byte) packets. And ATM provides for virtual channels, a kind of dynamically-assigned short address. But if you stand back a little way and compare various technologies, Autonet resembles ATM very closely; from a sufficient distance you really can't tell the difference. Autonet II, a 1 Gbit/second successor to Autonet, does provide all of the features of ATM.) In Spring, 1995, Bill Dally offered the following comment on this paper: To: 6.033-staff@MIT.EDU Subject: Autonet paper Folks, Coming from the world of multicomputer interconnection networks I found the Autonet paper a case study of overspecialization in Computer Science -- and associated lack of scholarship. The Autonet folks, coming from a distributed systems background, didn't bother to look at research from other fields. In particular: 1. Their routers don't use virtual cut-through (Kermani & Kleinrock) but rather wormhole routing (Dally & Seitz). In VCT one must have sufficient buffering for every packet accepted by the link-level flow control (or drop it) while in WH one may block a packet across several nodes. (See Ni's survey article in IEEE Computer, Feb 93 if you want more info). 2. Their up*/down* routing algorithm was published by David Gelernter in '81 IEEE TC C-30(10). 3. The distributed spanning tree algorithm they reference in a network publication in the mid 80s is identical to one I recall seeing published in the mid 70s. I can't dig up a reference to this right now, but I believe it was by Chandy and Misra. I'm not sure of the best approach, but we should try to use this as an example to motivate our students to be broad. Study the past or be damned to repeat it. ----Bill