MIT/LCS/TM-202
This research was supported in part by the Defense Advanced Research Projects Agency of the Department of Defense and monitored by the Office of Naval Research under contract number N00014-75-C-0661.
| CAMBRIDGE | MASSACHUSETTS 02139 |
J. H. Saltzer
This short memorandum describes a novel combination of three well-known techniques; the combination provides a systematic way of initializing a local-area ring network without previous, static designation of a distinguished station. The result is a distributed algorithm that dynamically designates a distinguished station from among a group of stations whose ability to communicate is hampered by the fact that the ring is not yet initialized. An appendix describes how this approach could be implemented as part of the 10 Megabit/second (version 2) ring network currently being installed at the M.I.T. Laboratory for Computer Science.
One of the more subtle problems of design in a digital communication ring is how to do initialization of the access protocol without designating a distinguished station to do housekeeping. In a ring, a signal once launched can circulate whether the signal is legitimate or spurious. Since a spurious signal may resemble anything, including legitimate traffic or protocol signals, the normal access protocols for any ring depend for their correctness on the ring starting off with a predictable signal pattern or format. (Even a contention ring depends on the predictable initial state of no signal at all.) Initialization of the signal format that drives the access protocols is required at startup and also following any failure that causes the expected signal format to be damaged. It is easy enough to insist that every station be prepared to reinitialize the signal format (and to detect the need for reinitialization) but this insistence introduces the danger that two or more stations will independently attempt reinitialization. These contending reinitializers can interfere with one another in such a way that none is successful. In a ring of 100 stations, one can imagine (in nightmares) an avalanche of contending attempts to reinitialize, none successful, going on indefinitely.
Earlier solutions to this problem have not been systematic or even very satisfactory. Prime Computer, Inc., in its Ringnet, for example, uses station-address-dependent timeouts (similar in function to the virtual token technique described here) to reduce the chance of contention, but relies primarily on small numbers of stations to avoid problems[1]. The L.C.S. version one ring network relies on the software at each node testing for ring format correctness either periodically or before each message origination[2]. The only protection against the reinitialization avalanche effect is that its probability is low with the small number of stations (fewer than ten) in the net. This approach ignores the coordination problem rather than solving it. The original design of the L.C.S. version two ring network envisioned an automatic scheme based on placing reinitialization responsibility only on stations that discover the need for reinitialization while attempting to originate a message. This scheme does not solve the contention problem, it instead attempts to reduce the typical number of contending stations to a level where a contention-backoff-retry algorithm has a greater chance of working.
Some more recent approaches have attacked the problem more systematically. Although there currently appears to be no published documentation on the subject, the Data Point ARC network (a star-organized bus rather than a ring) is reported to use a token-initialization technique closely similar to the one proposed here. The IBM Zurich Laboratory in its Z-ring has developed a quite different (and complex) ring format initialization algorithm using the distributed minimization technique of repeating only messages containing station numbers smaller than one's own[3].
To do protocol reinitialization systematically yet without central control, we here propose a novel, straightforward approach for rings that use a token or fixed frame format. The approach has three coordinated elements, jamming, a virtual token, and a try-at-most-once rule.
1) Jamming is a technique borrowed from the Ethernet, where it is used to insure that all contending stations agree that there was a collision[4]. In the Ethernet, whenever an originating station detects a collision by analysis of the signal levels, that station impresses an easily recognizable jamming signal on the net for a time long enough to propagate to every other network station. This jamming guarantees that all contenders agree on the need to backoff and retry. It also guarantees that all agree (to within a couple of propagation times) on when to begin the backoff timeout. It is this last property that is of interest in the ring. Therefore, the first step in systematic signal format initialization is that whenever any station detects a need for signal format reinitialization (generally by noticing that no format flags have passed by for one ring transit time) that station jams the ring by transmitting a characteristic pattern of data that does not resemble a normal frame or token (for example, a string of zeros) for T seconds, where T is chosen to be a little longer than one ring transit time. Since the jamming signal contains no format information, every other station will, within one ring transit time, similarly detect that the ring needs signal format reinitialization and emit T seconds worth of jamming signal. Thus a little more than 2*T seconds later all stations will have completed jamming and be in agreement, within about 2*T seconds, on when the entire procedure started. Note that this approach assumes that the lower-level, analog communication system is correctly operating (it must have its own initialization strategy).
2) Orderly, contention-free initialization can now be accomplished simply by having exactly one station place a correct signal format on the ring. The trick is to find a distributed algorithm that chooses exactly one station from a collection of stations that cannot currently communicate anything more sophisticated than a jamming signal and that are not even certain which other stations are participating in the exercise. A token-access ring normally avoids contention for message origination by circulating a token, and requiring that a station not originate a message unless it possesses the token. A similar technique can be used for ring initialization, with the exception that since the ring is not operating yet, the circulation of the initialization token must be simulated. This simulated initialization token is called a virtual token. The virtual token technique is borrowed from the Chaosnet, which uses it to reduce contention at every message origination[5].
In the ring, the virtual token works as follows: each station sets a timer to a value consisting of its station number times 2*T. When this timer finally expires, it is this station's turn to initialize the signal format. If some other station initializes the signal format first, a format correctness detector in each station will terminate that station's interest in protocol reinitialization, and operation will return to normal.
Thus the virtual token in effect visits each station in the ring in the order of its station number. The lowest-numbered active station will first decide that it has possession of the virtual token, and will reinitialize the signal format. The rest, waiting for their turn, will notice that the signal format has been restored and will return to their usual activities.
One interesting difference between this technique and that of the Chaosnet is the time scale involved. In the Chaosnet, multiples of the network propagation time are measured in microseconds. In the ring, because of per-station repeater delays and longer allowable cable runs, the transit time is more likely to be measured in milliseconds. If, for example, a value of T = 0.5 ms. is chosen, and there are 200 stations on a network, one might wonder if it will often require the better part of a second for the initialization to complete. This concern is not really important, however, for two reasons. First, since reinitialization should occur relatively rarely, promptness is not so important a design criterion as is inevitability and accuracy of the automatic procedure. Second, it is very likely that some low-numbered station will be active (one might intentionally assign bridges, gateways, and other high-availability servers low network numbers) so that reinitialization normally will occur very rapidly.
3) Some final, minor problems must be accounted for. Unless high-precision components are used the timers in different stations may be different enough to cause trouble. For example, if station 100 has a timer that is 1% slow, it may attempt reinitialization at just the same time as station 101. This problem can arise if there are no low-numbered stations, and the high-numbered stations have closely-spaced numbers. Similarly, a station may happen to join the ring in the middle of an ongoing reinitialization sequence, notice the lack of signal format, and try to initiate yet another reinitialization sequence. Both these problems are eliminated by providing one more degree of backoff. A node should try exactly once to do reinitialization with the virtual token. If that attempt fails, it should get out of the way to let some other node try. If, after a few seconds, no station has successfully reinitialized the signal format, automatic reinitialization is probably a hopeless activity anyway, and manual intervention should be called for. Assuming the ring is not actually damaged and thus the only problems are new participants and off-beat clocks, this try-at-most-once rule provides a very high probability of eventual success. Every active station will get to try, while collision-type interference becomes less and less likely as more stations exhaust their try and back off. (This observation suggests that one could even replace the systematic timeouts of the virtual token with random timeouts, and still expect a high probability of eventual reinitialization success. That approach would probably work, though with 250 stations it might be the usual case that many collisions occur at every reinitialization attempt.) Finally, a station that has tried, failed, and backed off should not inhibit itself forever from trying again. A period of correct ring operation can release the inhibition, or else an explicit reset request could be issued by the software of the computer at the station.
One of the attractions of this method of automatic protocol reinitialization is that it can be implemented entirely in hardware as part of the ring controller, without involving host-specific hardware or software. This isolation of implementation between the ring controller and the station allows the interface between the ring controller and the station to be more technology-independent than it would otherwise be.
The technique used here has the effect of rapidly distinguishing one ring station from the others; in effect one station dynamically assumes a role reminiscent of the role of the permanently-assigned monitor station of the Cambridge ring[6]. In contrast with the Cambridge ring, though, any station can take on this distinguished role and the role can be shifted from one station to another rapidly and automatically. Thus the advantage of having a distinguished station is obtained, without the usual disadvantage that failure of the distinguished station takes the ring out of service until either the distinguished station is repaired or another station is (manually) designated to be distinguished.
This observation can be turned to further advantage by allowing whichever station it is that succeeds in initialization to perform other distinguished services for the ring. Examples of such services that could simplify a ring design are: insertion of the extra delay necessary to pad out short rings; error reports or statistics; and marking packets to insure they do not pass by more than once. There is one objection, however, to adding such additional services in a dynamically-designated master station. Many stations (for example, those with high station numbers) will rarely, if ever, be called upon the exercise these services, and failures in the associated circuitry may accumulate, undetected. When a low-numbered station that has always assumed the designated role for a ring is one day removed from the ring, the higher-numbered stations may suddenly manifest many accumulated failures, making the ring quite unreliable for the while.
David Clark, David Reed, J. Noel Chiappa, and Kenneth Pogran participated in several rounds of intense discussions that laid the groundwork for the ideas suggested here.
Implementation of jamming, the virtual token, and the try-at-most-once rule for automatic ring reinitialization would involve several changes and some substantial simplification to the previous version 2 local network interface design[7]. The simplifications arise because in the previous design, ring reinitialization involved the ring controller, the host-specific hardware, software in the host and four different timers. With this new approach automatic ring reinitialization can be carried out entirely by the ring controller, and only two timers are required. Following is a list of mechanisms and procedures that would be implemented in each station interface.
Note that trying to initialize the ring inhibits any future attempts to reinitialize until such time as a token is detected. Thus for a single ring failure each station makes no more than one attempt to reinitialize.
If at any stage the station decides to abort the startup sequence, disabling the modem will reload the virtual token counter, thereby allowing the sequence to be tried again without need to power down.