Table of Contents

Introduction to Token Rings

A token ring network is a type of local area network, configured in either a ring or star topology, where a bit sequence or special waveform called a token is used to grant write access to the network. Only the host(s) with a token is/are permitted to transmit data on the network. Control in a token ring network can either be centralized, where a central controller distributes the token(s) to hosts, or it can be decentralized, where hosts pass the token(s) between themselves. In both cases, tokens are typically distributed and passed in a circular and cyclic fashion.

In this module, we will only consider ring topology token ring networks.

Characteristics of Token Ring Networks

The following are characteristics of token rings:

• service in cyclic order
• implementations
  • IEEE 802.4, token bus
  • IEEE 802.5, IBM token ring
  • Fiber Distributed Data Interface (FDDI) token ring
  • polling system for use in token distribution

In ring topology token ring networks, point-to-point links connect stations in a closed loop, where frames are transmitted and travel only a single direction around the ring. Each intermediate station between the transmitting host and the destination host receives and regenerates the frame (but does not store/copy it locally). The delay incurred for a host to receive a frame, inspect the header, and determine whether or not to forward the packet adds a delay of a few bits at each intermediate host. After the correct course of action is determined from the header, the intermediate host will forward the frame as the remainder of the frame is being received – this is an example of cut-through switching.

Removing a Frame from the Network

A problem with token ring networks, as we've discussed them so far, is that they pose the opportunity for the infinite forwarding of packets around the ring. How can we design a token ring network such that a transmitted frame is "removed" from the network? There are two options:

1. the destination host removes the frame when it receives the frame and determines it is in face the destination
2. the source/transmitting host removes the frame when it receives it back (i.e. when the frame traverses the entire ring topology and arrives back at the source)

Let's discuss what we mean by "remove" a frame from the network. In a token ring network, each host must receive the frame, check the headers, and retransmit the frame. If a host chooses to not retransmit a frame, it will effectively be removed from the network, since all hosts after the receiving host will never receive the frame.

Of the two options above, option 1 would allow the frame to only traverse the links required to make it to the destination, while option 2 utilizes all links between hosts. This means that in option 1, only the hosts between the source and the destination will know about the frame, while in option 2, all hosts will see the frame. It turns out that option 2 is a better choice in practice. Although it might seem less efficient, forcing a frame to traverse each host in the ring natively supports broadcast packets and aids in the implementation of some token ring protocol features.

Pros and Cons of Token Rings

Like many things in life, as well as in networking, there are both benefits and drawbacks to token ring networks. Advantages include:

• simple implementation due to fixed path
• routing is unnecessary
• frame incurs small delay at each host
• can span wide geographic areas
• very efficient for heavy traffic

while disadvantages include:

• single point of failure
• inability to add/remove hosts w/o disrupting others
• delay increases as number of hosts in ring increases

Operation of a Token Ring

Recall that a NIC is a network interface card, which implements the protocols of the underlying network and simply exposes an abstract network interface to the host for frame reception and transmission.

Like NICs for other types of networks, such as Ethernet, a token ring NIC supports two main operating modes – transmit mode and receive/listen mode.

Transmit Mode

In transmit mode, a token ring NIC will write a frame to the network. This frame will propagate to the next host in the ring, ..., which will eventually propagate back around to the source NIC. At this time, the source NIC will elect to not transmit the frame, thus removing the frame from the network.

Receive Mode

In receive mode, a token ring NIC will wait for a frame. When a frame arrives, it will read the destination address of the frame from the header. If the destination is the address of the host where the NIC is installed, the NIC will copy the frame to the host as well as retransmit the frame towards the next host in the network. If the destination address of the frame is not for the host where the NIC is installed, the NIC will simply retransmit the frame towards the next host in the network. The delay to check the destination address of the arriving frame is the retransmission delay, which is typically a small number of bits relative to the size of the frame.

Tokens

As discussed briefly, a token is what provides access control in a token ring network. Tokens are a special sequence of bits or a special waveform – the exact representation of a token depends on the token ring implementation. Only devices with a valid token may transmit at a given time. There are two types of tokens – idle tokens and busy tokens. If a host is given an idle token, that host may initiate a transmission onto the (idle) network. On the other hand, if the host is passed a busy token, the host may not use the network, since it is being used (i.e. is busy) by another ongoing transmission.

A host with a buffer of data to transmit will operate in receive mode until it receives an idle token from the network. Once an idle token has been received, the host will transition to transmit mode, where it converts the idle token to a busy token and may transmit its accumulated buffer of data onto the network in the form of a frame. Until an idle token is received, the host must operate in receive mode, forwarding any received frames to the next host in the network (and copying frames to itself if it's the destination).

Single Token Operation

When operating with a single token, the transmitting host will initiate its data transmission with a busy token at the head of the data frame. When the frame traverses the ring, all intermediate hosts will see the busy token and will continue to operate in receive mode, forwarding the frame along to the next host. When the frame arrives back at the transmitting host, the host will convert the busy token to an idle token and transmit the idle token to the next host as it's continuing to remove its data frame from the network. This next host will see the new idle token and may initiate a transmission if it has data to transmit; otherwise, it may pass the idle token on to its next host.

Multiple Token Operation

Multiple tokens can be used simultaneously in a token ring network. When multiple tokens are used, the transmitting host places the next token on the ring immediately after the end of the data frame, while the current token is placed at the beginning of the data frame. This means that for rings that have large propagation delays or that have typically small frames transmitted, several frames may exist on the ring simultaneously.

As an example, if a transmitting host has data to transmit, it will precede its frame with a busy token, transmit its frame, and then transmit an idle token. When the next host receives the busy token, it will continue to operate in receive mode; however, after the data frame it receives is retransmitted, it will see the idle token and may convert it to a busy token if it has data to transmit. Otherwise, the next host will simply pass on the idle token.

Single Frame Operation

There is a third mode of operation, which is effectively a subcategory of single token. This third mode of operation is called single frame. Token rings operating in single frame mode will only have a single frame (or partial single frame) on the entire network at any given time. What sets this apart from single token operation is that the entire frame must be removed from the network by the transmitting host before the transmitting host is permitted to transmit the idle token. Contrast this to single token mode, where the source host generates and sends the idle token before it has remove its entire data frame from the network.

Performance Analysis of Token Ring Networks

Assumptions and Notation

For the following analysis of token ring networks, we will assume:

• Poisson arrivals at each host
• equally likely destinations from each source (i.e. the average distance between the source and destination is 1/2 the ring length)
• equally spaced host around the ring (i.e. propagation delay between consecutive hosts is the the propagation delay around the ring / the number of hosts)
• same distribution of frame lengths at each host
• exhaustive cyclic service

The notation we will use is summarized in the following table:

Latencies in Token Rings

There are a couple different latencies or delays that must be considered when analyzing a token ring network.

Host Latency

On the hosts themselves, delay B is incurred when the frame is received and (briefly) buffered while the host NIC analyzes the destination address of the frame. This allows us to compute the walk time between any two consecutive hosts k and k+1 in the ring as:

Compare this to a centralized controller that polls hosts/handles tokens, where the walk time is equal to the propagation delay plus the token transmission time.

Ring Latency

The ring latency is the time requires for a token to circulate around the ring if all stations are operating in receive mode. The ring latency, τ' = Mw, which we can relate to the propagation delay and the host latencies as:

Delay Analysis

Finding Average Transfer Delay

The average transfer delay, T, is the sum of the average access delay, plus the average transmission time, plus the average latency, or T = W + E[X]/R + average latency.

The maximum latency is the host latency of B/R plus the ring latency of τ' = τ + MB/R. Thus, the average latency is half this, or τ'/2 = τ/2 + (MB)/(2R).

The average access delay, W, can be expanded on and expressed in the form:

where τ' = Mw.

This is the M/G/1 delay expression modified to account for token management delay.

Example

In this example, the single transmission keeps the network busy for time τ', rather than X/R. This is confirmed in our expression for W above.

Average Transfer Delay

The effective service time, E, of a frame is the time that the frame transmission keeps the network busy before a new transmission can begin. The effective throughput, S', of the network is the actual throughput that would give equivalent performance using the original M/G/1 expression for W. In other words, S' is a replacement for S in the M/G/1 average transfer delay expression. S' is defined as:

Note that the actual throughput is still S.

The average transfer delay can be expressed in the form:

Single Token Operation

In single token operation, there are a couple cases to consider – when the time to transmit a frame is greater than or equal to the ring latency and when the time to transmit a frame is less than the ring latency.

Frame Transmission Time, X/R >= Ring Latency, τ'

In this case, the busy token arrives at the transmitter before the transmission has completed. When this occurs, the idle token or next busy token is generated immediately after the data frame leaves the source host. The same behavior occurs in multiple token operation.

Frame Transmission Time, X/R < Ring Latency, τ'

In this case, the link is unavailable while the transmitter waits for the busy token to return. A gap in time occurs between the end of the data frame and the start of the subsequent idle token or busy token. During this time, the transmitter waits.

The normalized ring latency, a', is similar to the normalized propagation delay, a = τ/(E[X]/R), in random access LANs. The normalized ring latency can be expressed as:

The average transfer delay is expressed differently for different frame distributions. Let's consider fixed length frames and exponentially distributed frame lengths.

Average Transfer Delay for Fixed Length Frames

If a' <= 1, T is given by the expression for multiple token operation with fixed length frames. If a' > 1, E = τ' for each frame, which implies for fixed length frames:

and:

So:

Note that for a' > 1, stability is achieved only if Sa' > 1, i.e. if S < 1/a'. Also note that for a' > 1, W does not depend on E[X]; however, T does depend on E[X].

Average Transfer Delay for Exponentially Distributed Frame Lengths

For some frames, X/R <= τ' and E = τ'. For other frames, X/R > τ' and E = τ'(X/R). X/R is an exponentially distributed RV with mean E[X]/R, so:

We can express the average effective service time E[E] as:

And, the average transfer delay can be expressed as:

Note that the following must hold true for stability:

Multiple Token Operation

In multiple token operation, an idle token or the next busy token is generated immediately after the data frame leaves the source host. The effective service time is X/R, show below:

Average Transfer Delay in General

In general, the average transfer delay for multiple token operation is:

Average Transfer Delay for Fixed Frame Lengths

Average Transfer Delay for Exponentially Distributed Frame Lengths

Single Frame Operation

In single frame operation, the idle or next busy token is generated immediately after the end of the data frame returns to the source host.

Average Transfer Delay in General

In general, the average transfer delay for single frame operation is:

Note that the following must hold true for the system to be in a stable state:

Average Transfer Delay for Fixed Length Frames

The expression for T above can be simplified for single frame operation with fixed length frames:

Average Transfer Delay for Exponentially Distributed Frame Lengths

The expression for T above can be simplified for single frame operation with exponentially distributed frame lengths:

Examples

Example 1

Assume:

• ring length of 1 km
• link rate of 4 Mbps
• average frame length of 1000 bits
• 40 hosts in ring
• Poisson arrivals at rate 10 frames/second per station
• host latency of 1 bit
• propagation velocity of 5 us/km
• single token operation

So:

• R = 4 Mbps
• E[X] = 1000 bits
• M = 40
• λ = 10 frames/second
• B =  1 bit

Thus we can find the ring latency:

the normalized ring latency:

and the normalized throughput:

We don't know the frame distribution, but we do know how to solve for fixed length and exponentially distributed. If frames are fixed length, then since a' < 1:

If frame lengths are exponentially distributed, then:

Example 2

Assume the same as Example 1, except the station latency, B = 10 bits. Then the ring latency, normalized ring latency, and normalized throughput can be computed as:

If frames are fixed length, then since a' < 1:

If frame lengths are exponentially distributed, then:

Performance of Token Rings

Special Case: Light Traffic Load

Under light traffic load, meaning S is approximately 0, the average time waiting for service of previous arrivals into the network is negligible. Thus the average transfer delay can be approximated by:

Special Case: Small Normalized Ring Latency

With a small normalized ring latency, meaning a' is approximately 0, the average transfer delay for fixed length frame is approximately:

and for exponentially distributed frame lengths, the average transfer delay is approximately:

These results are independent of the token management technique.

Comparing Token Management Techniques with Exponentially Distributed Frame Lengths

For exponentially distributed frame lengths and a fixed normalized ring latency of a', we can compare the performance of single token, multiple token, and single frame token ring operations.

The graph above indicates that multiple token operation yields the best performance, followed by single token, and single frame operation with the worst performance. The best performance was achieved by minimizing the normalized ring latency, a', where performance is approximately the same for all three operating modes. It can also be observed that for a fixed normalized throughput, S, the number of hosts, M, impacts performance primarily through its effect on a'. Instability occurs for some values of S less than 1 if operating in single token or single frame mode.

Comparing Token Management Techniques with Fixed Frame Lengths

For fixed frame lengths and a fixed normalized ring latency a', it can be observed that the best performance is achieved with multiple token operation. On the other hand, the poorest performance is achieved with single frame operation. The performance for single token and multiple token are the same for a' <= 1, and the performance of single frame and single token are approximately the same for very large a' (which was previously shown for exponentially distributed frame lengths). There is however a lower delay for fixed length frames than exponentially distributed frame lengths.

Single Token Operation with Different Network Loads and Exponentially Distributed Frame Lengths

When single token operation is used with exponentially distributed frame lengths, it can be observed that the transfer delay is approximately independent of a' for small values of a'. Higher throughput, S, places more sever constraints on ring latency, and high ring latency severely restricts the allowable throughput.