Understanding Token Ring

 
Byte Magazine Jan 1989 Vol 14 No 01 PC Computers IBM PS/2 Token Ring

https://ia902702.us.archive.org/29/items/byte-magazine-1989-01/1989_01_BYTE_14-01_PC_Communications_and_Annual_Awards_and_Digitizing_Tablets.pdf

Pages 363-368, 370, 372, 374, 376

Editor's note: In this issue, we inaugurate a new column by Brett Glass, a hardware designer, programmer, and author with some impressive credentials. Brett was one of the architects of Texas Instruments ' TMS380 chip set (which implements the IEEE 802.5 Token Ring local-area network) and coauthored Living Videotext 's ThinkTank 2. 0. He founded BADGE, the Bay Area Amiga Developers ' Groupe, and is an instigator of the Hackers ' Conference, an annual get-together for the pioneers of the microcomputer revolution. Brett holds a BSEE from the Case Institute of Technology and an MSEE from Stanford University. In Under the Hood, Brett will present in-depth analyses of significant new technology, as well as provide technical background for understanding the material that appears elsewhere in BYTE. We feel fortunate to have a writer of Brett's caliber on-board, and we welcome your response to this new column. If you 'd like to contact him personally, see the note at the end of the column. KS

Page 363

THE TOKEN RING
by Bret Glass

The IBM Token Ring has captured more than 50 percent of the microcomputer local-area network market and more than 20 percent of all LAN applications worldwide. This specification (also known as the ANSI/IEEE 802.5 standard) got a late start relative to other LAN standards. IBM released it in late 1985, years after Ethernet and ARCnet. Why has the Token Ring become so popular so quickly? And what's really going on under the hood? In this article, I'll tell the "inside story" of the Token Ring and show why it's likely to be the dominant LAN standard by the end of this decade.

Token Ring Fundamentals

Before I go any further, it's vital to understand where the term Token Ring comes from. The nodes in a Token Ring, which can be microcomputers, minicomputers, mainframes, or other types of computer equipment, are electrically connected to one another in a "ring" configuration, as shown in figure 1 .

Figure 1: A functional overview of the Token Ring. (a) The sending station waits for a token; (b) the sending station makes the token a frame by adding addresses and data; (c) the receiving station copies data and sets the "copied bit"; and (d) the sending station removes the data and generates a new token. (Figure courtesy of IBM Corp.)

Each node receives information from one of its neighbors (its nearest active upstream neighbor, or NAUN for short) and transmits it to the node immediately downstream. Unless a node is transmitting its own data, it passes on whatever information it receives from its NAUN verbatim. Thus, any node can transmit information to any other node by sending it through some or all of the others. The total effect resembles an endless, circular version of the party game Telephone, in which players occasionally add their own information to the circle. This is the ring part of the Token Ring.

But what is a token, and what role does it play in making the network function? Well, as mentioned above, each node on the ring can either transmit its own data or retransmit the data it receives from its NAUN. As you might expect, however, it can't do both at the same time. Thus, if two nodes on the ring try to transmit simultaneously, it's probable that one will "swallow" the other's data and keep it from propagating to the entire ring. To avoid this, the nodes take turns transmitting, keeping track of whose turn it is to talk by passing around an electronic "baton" called a token.

A token is a short (24-bit) message that says to the node that receives it, "It's your turn to send data if you want to." When a node that wants to transmit receives a token (see figure 1a), it changes the token into a frame, appending its address, the recipient's address, and the data (see figure 1 b). The transmitting node is said to be in possession of the token. No other node can talk; each must obediently retransmit the data as it sees it. When the frame reaches its destination node, it is passed on (see figure 1c), with status bits within the frame changed to indicate that it was received. The frame continues moving along the ring until it arrives back at the sender.

Now, it isn't very useful for the frame to go around the ring more than once: On its initial circuit, it has already visited every node on the ring. Therefore, the sending node doesn't retransmit its own data. Instead, on recognizing its own frame, it "strips" the frame from the ring and passes a token to its nearest downstream neighbor (see figure 1d). The cycle repeats, with each node getting a chance to speak in turn.

This explanation is a bit simplistic (it doesn't include the notion of priority, for instance), but it covers the basics of the Token Ring architecture. The true brilliance of the Token Ring design lies in the subtleties added by IBM's scientists in Zurich and engineers from both IBM and Texas Instruments.

The Token Ring has the ability to prioritize access to the ring, "heal" after a cable breaks, disconnect malfunctioning nodes, and identify the locations of noisy connections within the network-capabilities absent from most other popular network standards. In the sections that follow, I'll explore some of these features in greater depth.

The Physical Layer: Logical Ring, Physical Star
I'll start my tour of the Token Ring with the lowest layer of the Open Systems Interconnection reference model: the physical layer. The first thing you'll notice if you look at the hardware of a typical Token Ring is that it doesn't look like a ring at all; rather, it resembles a star (see figure 2).

Figure 2 : At the lowest level, the physical layer, a Token Ring looks like a star (hence the term "star-wired ring topology ") in which each node is connected to a wiring concentrator, the medium access unit.

 Each network node uses a single two-pair cable to connect to a device called a wiring concentrator, or, in Token Ring parlance, a medium access unit (MAU). One pair is for receiving data, the other for sending data.

The star-shaped wiring topology has two advantages. First, only one cable is needed from each station on the network to a single, centralized location. (Telephone systems are wired the same way. In fact, IBM suggests that the same conduits and wiring closets be used for both.) This design requires more cable than if you were to simply connect successive nodes, but it makes it much easier to add new nodes and remove old ones.

The second advantage is that it's easy to bypass an inactive or malfunctioning node at the MAU by connecting its upstream node directly to its downstream neighbor (see figure 3).

Figure 3: Signal flow in the medium access unit. Note that any or all nodes in the star-wired ring can be bypassed if necessary.

When you turn a workstation off or when a node leaves the ring because of a malfunction, current ceases to flow in the "phantom circuit" (see figure 4) associated with that node. A relay opens in the MAU, and the ring reconfigures itself without the inactive machine.

Figure 4: The "phantom circuit " is essential to ring maintenance. If a node is on a damaged section of the ring or if requested by the local-area-network management program, a node removes itself from the ring by removing its voltage from the circuit (deactivating the phantom circuit). The presence of too much or too little current in the phantom circuit indicates a wiring problem. (Figure courtesy of Texas Instruments.)

If only one MAU is in the network, the MAU configures all the stations attached to it into a ring. If there is more than one MAU, each links its stations into a single ring that runs through all the MAUs.

Each node attaches to the MAU via a special four-conductor connector. The connector is hermaphroditic; that is, it can mate with identical connectors. When a connector is unplugged, shorting bars inside join the send circuit to the receive circuit, allowing the attached device to perform loopback tests on itself and the cable.

The connections between a node and the remainder of the Token Ring are transformer-coupled. This limits common-mode voltages and breaks ground loops that could cause harmful interference on the ring.

Longer Distances
In a bus-based network, like ARCnet and Ethernet, each network node must be able to be heard by all the others, thereby limiting the total size of the network to the distance that a single adapter' s signal can reach. But since each node on the Token Ring needs to send a signal only as far as the next node, a Token Ring can be much larger. A Token Ring node can be up to 300 meters away from its MAU, while an Ethernet (without repeaters) can span 500 meters maximum.

Encoding (Spreads across 366 and 367)

The Token Ring uses differential Manchester encoding to transmit bits on the ring. Manchester encoding schemes are "self-clocking"-they attempt to guarantee enough up-and down transitions in the incoming signal so that it's easy to predict when the next transition is going to occur.

Manchester and differential Manchester encoding require that there be a transition in the middle of each bit. In Manchester encoding (see figure A), the direction of the midbit transition determines whether the bit was a 0 (high-to-low transition) or a 1 (low-to-high transition).


Figure A: Manchester encoding.

In differential Manchester encoding (see figure B), the bit is a 0 if a transition occurs at the beginning of the bit time and a 1 if there is no transition at the beginning. Differential Manchester encoding was chosen for the Token Ring because it is polarity-independent, making the Token Ring easier to wire. The transmit and receive pairs and the transformers that drive them can be connected without keeping track of "positive" and "negative" leads.


Figure B: Differential Manchester encoding.

The Token Ring also uses Manchester code violations - occasional bits without transitions in the middle- to make delimiters completely unambiguous (see figure C). Besides 0 and 1, the Token Ring standard defines two "nondata" bits: J, a 1 bit without the middle transition, and K, a 0 bit without the middle transition.


Figure C: Manchester code violations.

When it's not sending data, a node "idles"-usually by transmitting 0 bits continuously. This provides the downstream node with a large number of transitions with which it can synchronize its clocking circuits. In no case should a station ever transmit more than 5 consecutive half-bits without a transition. If a node does not see a transition on its input after 5 half-bit times, a "BURSTS Error" has taken place. The node assumes that a serious ring problem has occurred and attempts to reestablish contact with its neighbors.

When the ring is idle, the stations on the ring continuously relay a token. A token consists of 3 bytes: a start delimiter, an access control field, and an end delimiter (see figure D). The most-significant bit of each byte is transmitted first; this is the reverse of Ethernet, RS-232C, and most other serial communications standards. The start delimiter and end delimiter contain Manchester code violations (Js and Ks); this guarantees that they will not be mistaken for ordinary data bytes.


Figure D: The abort delimiter consists of a start delimiter and an end delimiter together.

When a node that wants to transmit receives a token, it changes the token into a frame, appending its address, the recipient's address, and the data (see figure E). The frame also contains a redundancy code, and a status byte.


Figure E: Token format.

In the event that a node needs to abort a transmission in the middle, it sends an abort delimiter sequence, which consists of the start delimiter and the end delimiter together (see figure F).


Figure F: Frame format.

The MAC Sublayer
Let ' s examine the signals the Token Ring's physical medium carries and the techniques used to arbitrate access to the ring: the media access (MAC) sublayer. Data is transmitted on the ring using differential Manchester encoding (see the text box "Encoding" above) , typically at 4 megabits per second (IEEE will release a 16-Mbps Token Ring standard soon). When the ring is idle, the stations on the ring continuously relay a token (sometimes called a "free token") to one another.

When a node that wishes to transmit receives a token, it examines the priority bits to make sure its message has a priority at least as large as that of the token. If it does, it converts the token into a frame. Occasionally, a node will "decide" to abort a transmission in the middle. To do so, it sends an abort delimiter sequence, which consists of the start delimiter and the end delimiter together.

Addressing on the Token Ring
The IEEE 802.5 specification allows address sizes on the Token Ring. Besides a 6-byte address (the same length as in other IEEE standards), "short" 2-byte addresses are available for small networks.

The source address and destination address fields of a frame can do more than identify a single sender and recipient for the frame. The most significant bit of a source address is the routing information indicator, used when two or more rings are interconnected by nodes called bridges. When this bit is a 1, it indicates that the frame will specify not only the address of the destination node, but also a route to it-possibly spanning several rings. This technique is called source routing. Because the route is already worked out, the job of a bridge is simple. All it needs to do is follow the sender's routing instructions, which are tacked onto the beginning of the INFO field.

Destination addresses also have bits and bit patterns with special significance. It's possible to earmark frames for a server, a group of nodes, or all nodes (a broadcast address).

Functional addressing is a powerful feature built into every Token Ring adapter. By sending a frame to a functional address, a node can use network services-like a parameter server, an error monitor, or a network manager without knowing the address of the nodes that provide those services to the ring.

The Active Monitor
So far, most of the features I've looked at assume that the ring is up and running properly. But what if something goes wrong? When you first bring the ring up, or when any malfunction requires reconfiguration, the nodes on the ring test their equipment and send signals to one another to identify their NAUNs.

The nodes select one node (normally the active node with the numerically largest address) as the active monitor. This node is designated to perform special "watchdog" functions. The process by which neighbors are identified and the active monitor is chosen is called "beaconing." Once the active monitor has been chosen, it clears the ring and issues a token to restart normal ring operation.

The most basic function of the active monitor is to provide a clocking signal for the Token Ring. All other stations on the ring "listen" to this signal and synchronize with it. (The active monitor uses its own crystal to clock the data it transmits.)

The active monitor's next responsibility is to ensure that a token is circulating on the ring. First, the active monitor has to make sure that the token "fits" on the ring by introducing a 24-bit shift register into the ring. (Each node is designed to incur a minimal delay, typically 1 to 2 bit times. The wiring of the ring may not have 24 bits of delay all by itself. If the signal travels on the ring at two-thirds the speed of light, the ring needs to be 2/3 X 3 X 10(8) meters/second X 24 bits / [ 4 X 10(6) bits/ second] long, or at least 1200 meters long, for the wiring to delay the signal 24 bit times.)

The active monitor also watches for "lost tokens. " If it does not see a frame or a token go by within any 10-millisecond period, it clears the ring and starts a new token circulating. These actions keep the token from being irretrievably lost if a station fails to retransmit it.

The active monitor checks for frames and priority tokens (tokens with a priority greater than 0) that circulate around the ring more than once. It does this by checking the setting of the monitor bit in the access control (AC) field of each token or frame it sees. If the active monitor receives a priority token or frame with the monitor bit cleared, it sets the bit as it passes on the information. If the token or frame returns when it should not, the active monitor will discover that the monitor bit is already set to 1, and it will immediately purge the ring of data and restart the token-passing process.

Finally, the active monitor must "re-assure" the other stations on the ring that it is present and working. To do this, it broadcasts an active-monitor-present frame to the rest of the ring. If an AMP frame fails to circulate every so often, another station (the standby monitor) takes over the active monitor's job.

A Matter of Priority
On most other LANs, all nodes compete on an equal basis for use of the physical medium. For instance, there 's no way for an Ethernet station to say, "I have a very important message to send; please let me go next! " As an Ethernet gets crowded with traffic , it becomes likely that collisions, or just bad luck, will cause a delay of high-priority messages. We say that networks like the Ethernet are not "deterministic" -there 's no upper bound on the amount of time it will take a node to gain access. In some situations, like sensitive control application s, the delays can be disastrous.

Some networks are deterministic but lack priority structures. ARCnet, which is a token-passing bus network, guarantees that each node can talk in turn, but the turns are always distributed evenly. There 's no provision for getting an urgent message to its destination faster.

The Token Ring, however, has a unique scheme that provides for multiple priority levels and egalitarian, round-robin access on each level. The key to this scheme is the AC field present in each token or frame, which carries priority information and accepts "reservations" for the next use of the token.

After a station transmits a frame, it examines the AC field when the frame returns. If the reservation bits of the AC field contain a number greater than the priority level on which the station is currently transmitting, it means that one or more nodes wish to transmit at the higher priority as soon as possible. The sender emits a token with the higher priority. Since a station can use only a token that has a priority less than or equal to the priority of the frame that it wants to transmit, the token travels the ring until it reaches the station that urgently needs it.



Figure 5: Placing a reservation. (a) Station 5 is transmitting a frame to station 7 on the ring. Normally, station 7 would be the next node to get the token, even though station 12 had a higher-priority frame to transmit. (b) Station 12 sees that the reservation field of the frame is less than 3 and places a 3 there. The frame continues back to station 5, which absorbs the frame and emits a token. (c) The token emitted by station 5 had priority 3, so station 7 does not use it. The token continues on to station 12, which uses the token to transmit a frame. (d) When station 12 has finished transmitting, it releases a token, still at priority level 3. (e) Station 5 receives a token at priority level 3 and "remembers " that it was the one to raise the priority of the token. It therefore restores the priority to 0 so that station 7 will have a chance to transmit.

Figure 5 shows an example of the Token Ring's reservation system at work. In the simple three-node ring shown, with nodes at 5, 7, and 12 o'clock, station 5 is transmitting. Station 7 would normally use the token next, followed by station 12. But since station 12 has an urgent message to transmit, it changes the reservation field at the beginning of station 5's frame. Station 5 honors the reservation, emitting a priority token that station 7 cannot use.

Once station 12 is through transmitting and the frame has completed its circle, station 12 strips its frame from the ring and passes the priority token onward. The priority token completes its loop (being used in turn by any other nodes having urgent messages) until it returns back to station 5 (which originated the priority token) . Station 5 then demotes the token to a lower priority and gives station 7 its turn.

The Token Ring priority system has some especially nice properties. First, the priority of the token is always restored by the same node that raised it. Thus, a request for a high-priority token does not destroy the round-robin scheme on a lower level.

Second, it can recursively nest on all eight possible priority levels. Suppose, for instance, that station 5, from the previous example, had placed a reservation for priority level 6 while station 12 was transmitting (see figure 6) . Station 12 would elevate the priority of the token exactly as station 5 did and allow it to circulate. Station 12 would then restore the priority to 3. Station 5, in turn, would restore the priority of the token to 0 again.



Figure 6: If, in figure 5, station 5 had placed a reservation for priority level 6 while station 12 was transmitting, station 12 would elevate the priority of the token, allow it to circulate, then restore the priority to 3. Station 5, in turn, would restore the priority of the token to 0 again.

You can now see why the active monitor watches for recirculating priority tokens. Since each station that raises the priority of a token is responsible for lowering it again, a recirculating priority token indicates that a node has malfunctioned.

This scenario demonstrates only two levels of nested priority, not the most complicated (seven-level) case. But no matter how deeply priorities are nested, the result is the same: Round-robin order is maintained on each level, and the next node to transmit is always the one with the highest priority. These orderly and evenhanded procedures for selecting the next node to transmit pay off especially well under heavy loads. When many nodes contend for use of the network, a 4-Mbps Token Ring can perform nearly as well as a 10-Mbps Ethernet, while a 16-Mbps Token Ring can provide more than double the throughput.

I've already discussed one way in which faulty equipment can be removed from the Token Ring: the phantom circuit. Nodes that don't pass a thorough self test verifying that they can communicate properly with the rest of the ring remove themselves from the network. A more subtle feature, however, is the Token Ring's ability to localize intermittent faults and noisy links.

As you may recall, each node examines every token or frame it sees and sets the error-detected indicator if it detects any errors. The error-tracking process does not stop there. Each node maintains an internal count of how many times it set the EDI. Network management software can access this counter. If there is an intermittent or noisy path in a Token Ring network, the system can always track it down to a specific stretch of cable (a "failure domain") by determining which node is just downstream.

In certain cases, it's also possible to bypass a run of cable that has been completely destroyed. Look at figure 7 and notice the backup path. When two or more MAUs are connected in a ring, this path goes unused, because the ring goes in one end of each MAU and out the other.


Figure 7: The Token Ring can reconfigure itself to bypass shorts or breaks in a cable. In this diagram, the ring continues to function despite a cable break between MAU 3 and MAU 4.


Figure 8: A Token Ring bridge, a node that is on two rings at the same time and can pass frames from one ring to the other. (Figure courtesy of IBM Corp.)

But suppose that, for some reason, one of the cables connecting the MAUs into a ring fails. To get the ring up and running again, all you need to do is to remove the failed cable from both MAUs, allowing the backup path, which runs through all the MAUs, to complete the loop. Voila! The ring is up and running again. If the MAU is an "intelligent wiring center" (IBM doesn't make one, but Proteon and other vendors do), you may not even need to remove the cable. The network management software is able to reroute the ring without any human intervention whatsoever.

Bridges and Backbones

A bridge is a node that is on two rings at the same time and is able to pass frames from one ring to the other. Figure 8 shows a simple bridge. Figure 9 shows multiple rings bridged to a backbone ring. In large installations, a backbone ring connects many rings to each other. It consists of a series of bridges, each connecting a local ring to the backbone.

NetBIOS and the Token Ring
Originally, the IBM NetBIOS (see my article "Understanding NetBIOS " on page 301) had to handle many of the same functions that the Token Ring provides. The firmware present on most Token Ring adapters (the LLC sublayer) orders packets and ensures their delivery. Therefore, the NetBIOS API (Application Program Interface) is provided by a NetBIOS emulator.

Despite the extra layer of interface, the Token Ring card usually performs better than the original IBM PC Network.

Token Ring Chip Sets
As of this writing, three chip sets implement the Token Ring architecture. The two produced by IBM and UngermannBass are proprietary and not available to the general public. The third, the Texas Instruments TMS380, is available to all who wish to build an interface to the Token Ring.

The TMS380 chip set consists of five parts. The two Ring Interface chips (TMS38051/52) contain the analog components to interface to the ring. The Protocol Handler (TMS38020/21) manages the bit-level ring protocols.

The Communications Processor (TMS38010) contains a 16-bit microprocessor and 2.75 K bytes of RAM; it executes firmware (co-developed by Texas Instruments and IBM) from a ROM in the Protocol Handler. The System Interface (TMS38030) connects the whole package to a Motorola or an Intel microprocessor bus.

We can expect the chip set to shrink to two chips soon, and to a single chip eventually. IBM uses its proprietary chip set on the PC and PS/2 Token Ring cards, but it uses the Texas Instruments chip set on the Token Ring adapter for the RT. This is a good indication that the two implementations are compatible.

As this article went to press, the IEEE 802.5 committee was finalizing the text of the standard for the 16-Mbps Token Ring, and IBM released new dual-speed (4/16-Mbps) Token Ring adapters. Incorporated in the new boards is Early Token Release, which lets more than one frame (but only one free token) occupy the ring at one time. A proposal that may be adopted soon describes dual rings that rotate in opposite directions and merge to form a single ring if a cable fails. This feature is supported by Proteon but not by IBM.


Figure 9: A backbone ring consists of a series of bridges in a ring, each connecting a peripheral ring to the backbone.

An Animated Demonstration

This article has covered much of what there is to know about the Token Ring. For those readers who want to learn more or who want a graphical explanation, I've saved a fun and interesting surprise for last. The marketing folk at IBM's Research Triangle Park facility have developed a freely redistributable animated presentation on the Token Ring that will run on any IBM PC with a CGA.

First, download the file TOKNDEMO.ARC from the BIX listings file area "FROMBYTE88." (Warning: It's almost 180K bytes long.) Use PKXARC to unpack it onto a formatted floppy disk. Make the floppy disk the logged drive and type AUTOEXEC. You'll see a wonderful interactive demonstration of tokens running around rings, changing into frames with messages, shifting priorities, and vaporizing mysteriously. (Watch out for the mischievous starship Enterprise!) The demonstration software uses a special technique to produce up to 20 simultaneous colors on an IBM CGA and isn't guaranteed to work with all EGA or VGA implementations. However, you should still be able to follow the demonstration (perhaps sans some of the brilliant colors) on almost any compatible system. Have fun!

Many thanks to Leon Adams and Leslie Price of Texas Instruments for providing vital materials for this article. Thanks also to IBM for use of diagrams and the Token Ring interactive demonstration.

BIBLIOGRAPHY

LAN Primer (RTC Support Tool). Dallas: Texas Instruments, 1987.
The IBM Token-Ring Network Decision, 2nd ed. Armonk, NY: IBM, 1986.
TMS380 Adapter Chipset User 's Guide. Dallas: Texas Instruments, 1986.
TMS380 Adapter Chipset User 's Guide Supplement. Dallas: Texas Instruments, 1987.

9595 Main Page