Handout 21 1Massachusetts Institute of TechnologyDepartment of Electrical Engineering and Computer Science6.826 — Principles of Computer SystemsHandout 21 April 7, 1997____________________________________________________________________________Autonet: A High-Speed, Self-ConfiguringLocal Area Network Using Point-to-Point LinksThe attached paper on Autonet by Michael Schroeder et al. appeared as report 59, SystemsResearch Center, Digital Equipment Corp., April 1990. Essentially the same version waspublished in IEEE Journal on Selected Areas in Communications 9, 8, (October 1991), pp1318-1335.Read it as an adjunct to the lectures on distributed systems, links, and switching. It gives a fairlycomplete description of a working highly-available switched network providing daily service toabout 100 hosts. The techniques used to obtain high reliability and fault-tolerance arecharacteristic of many distributed systems, not just of networks. The paper also makes clear theessential role of software in modern networks. Digital Equipment Corporation 1990.This work may not be copied or reproduced in whole or in part for any commercialpurpose. Permission to copy in whole or in part without any payment of fee is grantedfor nonprofit, educational, and research purposes provided that all such whole or partialcopies include the following: a notice that such copying is by permission of the SystemsResearch Center of Digital Equipment Corporation in Palo Alto, California; anacknowledgement of the authors and individual contributors to the work; and allapplicable portions of the copyright notice. Copying, reproducing, or republishing forany other purpose shall require a license with payment of fee to the Systems ResearchCenter. All rights reserved.Autonet:a High-speed,Self-configuringLocal Area NetworkUsing Point-to-point LinksMICHAEL D. SCHROEDERANDREW D. BIRRELLMICHAEL BURROWSHAL MURRAYROGER M. NEEDHAMTHOMAS L. RODEHEFFEREDWIN H. SATTERTHWAITECHARLES P. THACKERAPRIL 21, 1990SRC RESEARCH REPORT 59ABSTRACTAutonet is a self-configuring local area network composed of switches interconnectedby 100 Mbit/second, full-duplex, point-to-point links. The switches contain 12 ports thatare internally connected by a full crossbar. Switches use cut-through to achieve a packetforwarding latency as low as 2 microseconds per switch. Any switch port can be cabled toany other switch port or to a host network controller.A processor in each switch monitors the network’s physical configuration. Adistributed algorithm running on the switch processors computes the routes packets are tofollow and fills in the packet forwarding table in each switch. This algorithmautomatically recalculates the forwarding tables to incorporate repaired or new links andswitches, and to bypass links and switches that have failed or been removed. Hostnetwork controllers have alternate ports to the network and fail over if the active portstops working.With Autonet, distinct paths through the set of network links can carry packets inparallel. Thus, in a suitable physical configuration, many pairs of hosts can communicatesimultaneously at full link bandwidth. The aggregate bandwidth of an Autonet can beincreased by adding more links and switches. Each switch can handle up to 2 millionpackets/second. Coaxial links can span 100 meters and fiber links can span twokilometers.A 30-switch network with more than 100 hosts is the service network for Digital’sSystems Research Center.CONTENTS1. Introduction ................................................................................................ 12. Overview.................................................................................................... 23. Design Decisions......................................................................................... 33.1 Point-to-Point Links at 100 Mbit/s......................................................... 33.2 Unconstrained Topology with Pre-calculated Packet Routes.......................... 33.3 Automatic Operation ............................................................................ 43.4 Crossbar Switches................................................................................ 43.5 Limited Buffering with Flow Control ...................................................... 43.6 Deadlock-Free, Multipath Routing .......................................................... 53.7 Short Addresses ................................................................................... 53.8 Hardware-Supported Broadcast................................................................. 63.9 Alternate Host Ports............................................................................. 63.10 Integrated Encryption............................................................................ 73.11 Generic LAN Abstraction ...................................................................... 74. Innovations................................................................................................. 74.1 Distributed Spanning Tree Algorithm with Termination Detection ................ 74.2 Up*/Down* Routing............................................................................ 84.3 Dynamic Learning of Short Addresses...................................................... 84.4 Automatic Reconfiguration.................................................................... 84.5 First-Come, First-Considered Port Scheduler............................................. 95. Components ............................................................................................... 95.1 Switch Hardware.................................................................................. 95.2 Controller Hardware............................................................................ 115.3 Link Hardware................................................................................... 135.4 Switch Control Program ..................................................................... 135.5 The SRC Service LAN ....................................................................... 135.6 Host Software ................................................................................... 146. Functions and Algorithms ........................................................................... 156.1 Link Syntax...................................................................................... 156.2 Flow