|
|
|
{Page 67}
Department of Computer Science, Oklahoma City University, Oklahoma City, OK 73106
The IEEE 802.5 is the standard protocol for token ring local area networks (LANs) currently in use in many areas. It is popular because of its many advantages, such as reliability, simplicity of hardware, ease of use with various transmission media, efficiency at heavy load, and flexibility in link length and number of stations attached to the network. One of its drawbacks, however, is its inefficiency at moderate and light loads. At light loads, a station with a packet to send must wait on average half a round trip propagation delay time to receive the free token. This paper used the star topology implementation of the token ring network to develop a new protocol with improved performance characteristics at moderate and light loads. This is accomplished by first determining which stations have data to send, then sending the token only to these stations. For the new protocol, all performance characteristics had a significant improvement. © 2001 Oklahoma Academy of Science
| Introduction | Protocol | Conclusions | References | Top of Page | Table of Contents | Home |
The Institute of Electrical and Electronic Engineers 802.5 (1) standard has become a widely accepted protocol for token ring local area networks (LANs). A major part of its success is the advantages it offers over other network architectures. These advantages include its reliability and simplicity of hardware interfacing the transmission medium to the stations' electronics. Because each station provides an active tap to the transmission medium, there is great flexibility in length of link between stations. Many stations can be attached to the transmission medium without deterioration of the signal. The token ring has been remarkably adaptable to the available transmission medium. It has been implemented by using shielded twisted wire pair, coaxial cable, and fiber optic cable, all with great success.
A token ring is a ring whose media access control protocol is based on a short control frame, called a token, which circulates around the ring. A station that wants to transmit data on the medium must wait for a free token. When a free token arrives at the station, the token is changed to a busy token and the station transmits the busy token followed by its data packet. When the station has transmitted its packet and receives the first part of its data packet back on the network, it releases a new free token. The free token circulates around the ring until it reaches another station that has data to send.
One of the drawbacks of the token ring is its inefficiency at moderate and light loads. At light loading conditions only a few stations on the ring have data to send. By the token ring protocol, however, the token circulates from station to station regardless of whether or not a station has data to transmit. A station having data to transmit must wait for the free token to pass through all the stations that do not. The delay associated with the token passing through idle stations to get to an active station is the cause of the inefficiency.
Many token ring networks are actually implemented using a star topology (2). This paper proposes a new protocol for the star topology token ring LAN. The new protocol is not subject to the same delays as the topological ring operating under moderate and light loads.
| Introduction | Protocol | Conclusions | References | Top of Page | Table of Contents | Home |
2 The Star Protocol: The star LAN looks topologically like a wheel without a rim. It consists of a central controller and any num-
{Page 68}
ber of other stations, each connected directly to the central controller. The central controller has separate hardware to interface with each other node. This means it is capable of communication with any or all stations at any time simultaneously.
2.1 The Basic Star Protocol: Under moderate and lightly loaded conditions, the protocol works as follows. The central controller sends a request token to all stations simultaneously. This action initiates a transmission cycle (Fig. 1). Each station responds with a response token, either yes or no, depending on whether or not it has data to transmit.
The central station sends the transmit token to each station in turn that sent a yes response token. Stations that sent a no response token are not included in the token passing procedure. Thus, stations do not have to wait for the transmit token to pass through stations with no data to transmit. This clearly overcomes the stated drawback of the standard token passing protocol.
A complete transmission cycle (Fig. 2) consists of a request/response cycle followed by N token transmission cycles, for N active stations. A token transmission cycle consists of sending the transmit token to a data station followed by the data transmission.
Ti Datai
Figure 1. Token Transmission Cycle
Req Resp T1 Data1 T2 Data2 . . . Tn Datan
Figure 2. Complete Transmission Cycle
Depending on the level of loading, the central controller can revert to standard token ring operation. If the load exceeds a certain level, it sends the transmit token to each station in turn without going through the request/response cycle.
2.2 Priority Star Protocol: The above protocol can be used, with minor modification, in a network with multiple priority levels. In a multiple priority environment, the yes response token contains a priority field with enough bits to cover the number of priority levels. When a station responds with a yes response token, it also sets the priority bits to indicate the priority of its data. The central controller sends the transmit token first to stations with the highest priority, then to stations with the second highest priority, and so on until all stations that sent a yes response have sent their data.
A complete transmission cycle (Fig. 3) consists of a request/response cycle followed by N priority token transmission cycles, for N active stations. A token transmission cycle consists of sending the transmit token to a data station followed by the data transmision. In the priority protocol, the transmit token is sent to station in order of priority (Fig. 1).
Req Resp Tp1 Datap1 Tp2 Datap2 Tpn Datapn
Figure 3. Complete Transmission Cycle
2.4 Tokens: Having proposed different tokens for different purposes, the discussion in this section is devoted to describing new tokens for the star protocol. The transmit token is the eight bit pattern shown in Figure 4.
0 1 1 1 1 1 1 0
Figure 4. The Transmit Token
For the request token, bits are changed in the middle of the pattern to obtain the token as shown in Figure 5.
0 1 1 0 0 1 1 0
Figure 5. Request Token
The response token is as shown in Figure 6, where Y = 1 and N = 0.
{Page 69}
0 Y/N 1 1 1 1 1 0
Figure 6. Response Token
To accommodate multiple priority levels, three bits are dedicated to allow eight levels of priority. The priority token is shown in Figure 7.
0 Y/N P2 P1 P0 1 1 0
Figure 7. Priority Data Response Token
These tokens account for all services offered by the protocols proposed above. Each station with packets to send gets to do so before any station gets to send a second packet.
In addition, Kamal (3) suggested that multiple free tokens circulate on the ring. The intent is to have several tokens fairly evenly spaced around the ring to allow multiple transmissions simultaneously. This idea translates directly to the star topology. In fact, it works better in the star because the central controller knows precisely where each transmit token is located and is better able to control the equal spacing between tokens.
3 Performance Analysis: This section compares the waiting time delay of an equivalent topological ring to the topological star and then compares the propagation and transmission time performance of the two protocols. The results show the proposed star protocol has significantly better performance characteristics in both cases.
The following notations are used in the ensuing discussion:
| r | time to pass transmit token from one station to the next |
| x | message transmission time |
| M | total number of stations on the network |
| N | number of active stations on the network |
| T´ | mean token rotation time |
 |
Poisson arrival rate of messages to each station |
| R | traffic intensity at each station =
T´ |
| x´ | mean message transmission time |
| VT2 | variance of the token rotation time |
| Cb2 | square of coefficient of variation of token rotation time |
| D´ | mean message delay |
| W´ | mean time spent waiting in queue |
| Q´ | mean queue length |
Sethi and Saydem (4) provided a performance analysis of token rings that gives analytical results for two message length distributions, constant and exponential. They provided results for both token rotation time and delay for a limited-to-one service discipline. Both performance issues are addressed in subsequent sections.
3.1 Token Rotation Time: Sethi and Saydem (4) analyzed a token ring with M total stations. The number of active stations, N, during a given token rotation was assumed to have a binomial distribution. The authors derived their results by assuming both constant and exponential message lengths.
3.1.1 Constant Message Length: For a constant message length assumption, the following results are presented.
For the token rotation time
T´R = (M r)/(1 - M x) (1)
for traffic intensity
{Page 70}
R R = (M r)/(1 - M
x) (2)
for the square of the variance of token rotation time
VTR2 = M R (1 - R) x2 (3)
and for the square of coefficient of token rotation time
CbR2 = [R (1 - R) x2 ]/ [M (r + R x)2] (4)
In equations 1-4, the number of stations plays a significant role because the token must pass through all M stations even if only a few are active.
For a star that is operating as a token ring under moderate or light loading conditions, only N stations in the network will be active, where N < M. By the new star protocol, the token will pass only to the N active stations. Thus, the following equations apply.
For token rotation time
T´S = (N r)/(1 -
N x) (5)
for the traffic intensity
R S = (N r)/(1 - N
x) (6)
for the square of the variance of token rotation time
VTS2 = N R (1 - R) x2 (7)
and for the square of the coefficient of token rotation time
CbR2 = [R (1 - R) x2 ]/ [M(r + R x)2] (8)
To ease the mathematical
manipulation, the simplifying assumption that (1 - N
x) = (1 - M x) -> 1 is made.
The ratio of mean token rotation time of the ring to the star is
T´R/T´S = M/N (9)
the ratio of traffic intensities is
R R/R S = M/N (10)
the ratio of square of variance of token rotation time is
VTR2/VTS2 = M/N (11)
and for the square of the coefficient of token rotation time is
CbR2/CbS2 = N/M (12)
As the number of active stations decreases, the new star protocol shows increasing performance characteristics for parameters related to token rotation time. This performance gain carries over to exponentially distributed message lengths, discussed in the next subsection.
3.1.2 Exponentially Distributed Message Lengths: The following analytical results were found for the token rotation time for a token ring with exponentially distributed message lengths.
For mean token rotation time
TR´ = (M R)/(1 -
M x´) (13)
for traffic intensity
R R = (M r)/(1 - M
x´) (14)
for the square of the variance of mean token rotation time
VTR2 = M R (2 - R) (x´)2 (15)
and for the square of the coefficient of the mean token rotation time
CbR2 = [R (2 - R) (x´)2 ]/[M (r + R x´)2 ] (16)
Once again, the total number of stations, M, has a significant impact on performance. For the new star protocol, only N stations are active so only N stations need to see the token. The following results hold for the new star protocol.
{Page 71}
For the mean token rotation time
TS´ = (N r)/(1 - N
x´) (17)
for traffic intensity
R S = (N r)/(1 - N
x´) (18)
for the square of the variance of mean token rotation time
VTS2 = N R (2 - R) (x´)2 (19)
and for the square of the coefficient of mean token rotation time
CbS2 = [R (2 - R) (x´)2]/[N (r + R x´)2] (20)
Forming the ratios of ring values to
star values and making the simplifying assumption (1 -
M x´) = (1 - N x´) -> 1, the following results are obtained
TR´/TS´ = M/N (21)
R R/R S = M/N (22)
VTR2/VTS2 = M/N (23)
and
CbR2/CbS2 = N/M (24)
3.2 Delay Analysis: Analytical results were also derived for mean waiting time, mean message delay, average number of messages in the individual queue, mean number of messages in all queues, and ring utilization.
The results of time spent in queue are
W´ = [(1 + Cb2) T')/(2 (1 - R)] (25)
for mean message delay
D´ = W´ + x´ (26)
for mean queue length
Q´ = ((1 + Cb2) R)/(1 - R) (27)
for mean number of messages in queues in the system
QS´ = [((1 +
Cb2) R)/(2 (1 - R))] + x´ (28)
and for ring utilization
UR = 1 - [1 - M l r/(1 - M
x) ]M (29)
All these equations except Equ. 29 hide their dependence on the number of stations in the network. To compare the performance of the ring to the star, equations were substituted for ring and star respectively, from the last section, and the ratio formed. The results are as follows.
For mean queue length
QR´/QS´ = M/N (30)
for mean waiting time
WR´/WS´ = M/N (31)
for the mean message delay
DR´/DS´ = M/N (32)
and for ring utilization
UR/US = [1 - (1 -
R)M]/[1 - (1 -
RS)N] (33)
Since RR < RS, (1 - RR)M < (1 - RS)N, the result is
UR < US (34)
For all parameters related to delay or queue length, the new star protocol is superior to the traditional token ring protocol.
Only a limited-to-one service discipline was analyzed in this work. The entire preceeding analysis intentionally overlooked another factor contributing to delay, the packet transmission time. On a topologi-
{Page 72}
cal ring, the packet transmission time is the time to traverse, on average, half the links on the ring. On a topological star, packet transmission time is the time to traverse just two links. Including this factor would enhance the superiority of the new star protocol over the ring protocol.
| Introduction | Protocol | Conclusions | References | Top of Page | Table of Contents | Home |
This article presents several new star protocols designed for a token rings operating under moderate to light loading conditions on a topological star. The new protocols include a basic star protocol. An enhanced star protocol implemented a multiple priority scheme for data transmission.
The performance of the traditional token ring protocol was then compared to the new star protocol for both token rotation time and message delay. For all parameters, the star protocol showed superior performance.
Future research will take several directions. First, there needs to be an analysis of the star protocol for both gated and exhaustive service disciplines. The performance gains of the new protocol make it highly desirable to see whether this protocol can be adapted to work with voice stations also on the network, thus creating an effective integrated services network protocol.
| Introduction | Protocol | Conclusions | References | Top of Page | Table of Contents | Home |
1. ANSI/IEEE Standards 802.5-1989. Token Ring Access Method and Physical Layer Specification: 1989.
2. Stallings W. Local and metropolitan area networks. 4thed. New York: Macmillan; 1993.
3. Kamal AE. On the use of multiple tokens on ring networks. Proc INFOCOM 1990; 15-22.
4. Sethi AS, Saydam T. Performance analysis of token ring local area networks. Computer Networks and ISDN Systems 1985; 9:191-200.
Received: September 28, 2000; Accepted: April 6, 2001
