Table of Contents
| Table of Contents | ||
|---|---|---|
|
...
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.
...
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
...
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:
| Variable | Description |
|---|---|
| X | RV denoting length of an arbitrary frame |
| R | link speed in bits/second |
| B | bits of latency per host |
| τ | propagation delay around entire ring |
| τ' | ring latency |
| a' | normalized ring latency |
| w | walk time |
| T | average transfer delay |
| W | average access delay |
| S | normalized throughput |
| S' | effective throughput |
| E | effective service time of a frame |
| M | number of hosts in the ring |
Latencies in Token Rings
There are a couple different latencies or delays that must be considered when analyzing a token ring network.
...
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.
...
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 essentially the walk time of each link in the topology plus the host latencies discussed above. 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.
