UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Modelling and performance comparisons of some ring networks Nadkarni, Ashok Vasant 1983-04-21

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata

Download

Media
831-UBC_1983_A6_7 N34.pdf [ 2.59MB ]
Metadata
JSON: 831-1.0051841.json
JSON-LD: 831-1.0051841-ld.json
RDF/XML (Pretty): 831-1.0051841-rdf.xml
RDF/JSON: 831-1.0051841-rdf.json
Turtle: 831-1.0051841-turtle.txt
N-Triples: 831-1.0051841-rdf-ntriples.txt
Original Record: 831-1.0051841-source.json
Full Text
831-1.0051841-fulltext.txt
Citation
831-1.0051841.ris

Full Text

MODELLING AND PERFORMANCE COMPARISONS OF SOME RING NETWORKS by ASHOK VASANT NADKARNI B.Sc, Bangalore University, India, 1972 B.E., I.I.Sc, India, 1975. M.A.Sc, University of Waterloo, 1977. A THESIS SUBMITTED IN PARTIAL FULFILMENT THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of Computer Science) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA May 1983 el Ashok Vasant Nadkarni, 1983 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of CoMpVTE& SCIENCE The University of British Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 DE-6 (3/81) Abstract This thesis is mainly concerned with the mathematical modelling of some common types of ring networks, i.e., token rings (both the exhaustive and the non-exhaustive service disciplines) and slotted rings. The models described make extensive use of the standard results of queuing theory. The two service disciplines for the token ring display tradeoffs between fairness and system performance. In the case of the slotted rings, an optimum value for the number of stations on the ring is determined which gives minimum or near-minimum delays for all load levels. The correctness of the models is verified by comparing the analytic results with those from simulation. Finally, we summarize interesting results of our models and offer suggestions for further research. The literature contains very little work in this area. Hopefully this thesis has provided new insights into the behaviour of certain ring type local area networks. iii CONTENTS 1 . INTRODUCTION 1 1.1 An Overview of Ring Networks 2 1.1.1 Token Ring 2 1.1.2 Slotted Ring 3 1.1.3 Characterization of Ring Networks 4 1.2 Thesis Outline 6 2. REVIEW OF SOME EXISTING MODELS 7 2.1 Models of the Token Ring2.1.1 Tanenbaum's Model2.1.2 Model by Cherukuri et al. 10 2.1.3 Bux's Model 12 2.2 Models of the Slotted Ring 14 2.2.1 Bux's Model  4 2.2.2 Model by King and Mitrani 16 3. MODELLING OF SOME RING NETWORKS 17 3.1 Introduction 13.2 The Token Ring - Exhaustive Service Discipline 17 3.3 The Token Ring - Non-exhaustive Service Discipline 21 3.4 The Slotted Ring 24 4. PERFORMANCE COMPARISONS 27 4.1 Introduction4.2 Token Ring - Exhaustive Service Discipline 28 4.3 Token Ring - Non-exhaustive Service Discipline 31 i v 4.4 Single-Token versus Multiple-Token Modes 35 4.5 Comparison with Simulation Results 38 4.6 The Slotted Ring 42 4.7 Optimization of the Number of Stations on a Slotted Ring 49 4.8 Comparison with Simulation Results 51 5. CONCLUSIONS 53 REFERENCES 6 APPENDIX I 59 APPENDIX II 64 V LIST OF FIGURES Fig. 1 Token Ring Model 13 Fig. 2 Slotted Ring Model 4 Fig. 3 Absolute Mean Delay vs. Normalized Load for a Token Ring (Exhaustive) 29 Fig. 4 Absolute Mean Delay vs. Normalized Load for a Token Ring (Non-exhaustive) 32 Fig. 5 Single-Token vs. Multiple-Token Modes for a Token Ring (Exhaustive) 36 Fig. 6 Single-Token vs. Multiple-Token Modes for a Token Ring (Non-exhaustive) 37 Fig. 7 Comparison of Analytic and Simulation Results for a Token Ring (Exhaustive) 40 Fig. 8 Comparison of Analytic and Simulation Results for a Token Ring (Non-exhaustive) 41 Fig. 9 Absolute Mean Delay vs. Normalized Load for a Slotted Ring 43 Fig. 10 Normalized Delay vs. Normalized Load for a Slotted Ring 44 Fig. 11 Absolute Mean Delay vs. Length of Ring (Slotted) 46 Fig. 12 Absolute Mean Delay vs. Normalized Load for a Slotted Ring 48 Fig. 13 Comparison of Simulation and Analytic Results 52 vi Acknowledgement I would like to thank Dr.S.T.Chanson for supervising my research and for his comments on this document. Thanks also to Dr.S.T.Vuong for reading and commenting on the final draft. I would also like to thank the Department of Computer Science for all the help provided while preparing this thesis. 1 CHAPTER 1 INTRODUCTION Local Area Networks (LANs) have been the subject of considerable research and development efforts in recent years [4,5,7,9,12,13]. A LAN is generally considered to be one which covers a "limited" geographical area such as a building or a group of buildings within a few kilometers of one another. There are many advantages of interconnecting computing facilities. Some of them are listed below: 1) allows devices (line printers, disk units, etc.) as well as software resources such as files and databases to be shared, 2) provides easier access to facilities in different physical locations, 3) facilitates the co-operation and co-ordination of projects (mainly due to points 1 and 2 above), 4) performance can be improved as parallel computation of logically independent tasks at different nodes becomes feasible. Furthermore, heavily loaded stations can be downloaded by distributing the load to other stations, 5) facilitates the implementation of electronic mail systems, 6) allows incremental growth of computing power (through the addition of nodes (or stations) in the network). Local area networks also exhibit certain characteristics such as high data rates, a high degree of interconnection between devices on the network (each station being able to 2 communicate with every other station). 1.1 An Overview of Ring Networks Ring networks ' form an important class of local area networks. Unlike the carrier sense bus networks, rings are made up of a series of point-to-point cables between consecutive repeaters or stations and signals travel in a closed loop. There are different types of ring networks like the token ring, the slotted ring, the contention ring and the register insertion ring. Two of the most common types are the token ring and the slotted ring. We shall consider some aspects of these two nets in the following sections. A description of the contention rings and the register insertion rings can be found in [18]. 1.1.1 Token Ring This type of ring net is characterized by a special bit pattern called the token which circulates around the ring. Typically, it is a series of eight I's. Obviously, this pattern must be avoided in the data that is transmitted by the various stations on the ring by employing techniques such as bit stuffing. A station may transmit a packet only if it is in possession of the token. Thus it examines each passing bit for the special pattern, thereby introducing a minimum of 1-bit delay on the line. On getting the token, the station replaces the token by a 3 different bit pattern, such as changing the last bit from a 1 to a 0 and then it starts transmitting its data. This bit pattern of 11111110 is called the connector. After a station has finished transmitting its data, it regenerates the token so that the next station on the ring can transmit its data. Thus the token goes from station to station in a round robin fashion giving each station on the ring a fair chance to transmit. There are two different types of service disciplines at the stations : the exhaustive discipline and the non-exhaustive discipline. Under the exhaustive discipline, a station is permitted to transmit all of its waiting packets upon receiving the token. A freshly arrived packet which joins the queue that is being serviced is also transmitted. There are advantages and disadvantages with this scheme as we will see later. The second type of service discipline is called non-exhaustive under which, a station is permitted to transmit only a fixed number of waiting packets (usually one) upon receiving the token. It is worthwhile to note that there can be at most one station on the ring which is transmitting at any given time. 1.1.2 Slotted Rings A slotted ring consists of a number of fixed-size slots which continuously move around the ring. This method requires one of the stations on the ring to be designated the monitor  station which initiates and regulates these slots. Any station wishing to transmit a packet must simply wait for an empty slot to pass by. On getting an empty slot, a station puts its packet 4 into the slot, marks the slot as full and the destination station removes this packet and sends an acknowledgement in the same slot. After getting the acknowledgement, the sending station marks the slot as empty and passes it down the ring without using it (to prevent hogging of the ring). Thus, each slot must have at least one bit to mark its status (full/empty), and one bit for acknowledgement in addition to other address bits, checksum, etc. As the slots are of fixed size, if the packet is too large to fit into a slot, more than one slot will be required to transmit such a packet. Also, in a slotted ring with multiple slots, there can be more than one station transmitting at any given time. 1.1.3 Characterization of Ring Networks Before we attempt to develop analytic models for the ring nets, it is important to know the various ring parameters which influence their performance. The "physical length" of a bit is an important parameter to be considered. It is the ratio of the propagation speed of signal to the bandwidth of the ring. If the physical length of the ring is not large enough to fit in a certain minimum number of packets, artificial delays will have to be introduced by putting shift registers on the ring. The time that it takes one bit to go once around an idle ring is called the walk time. The walk time is also a function of the number of stations on the ring since each station adds some delay. In the case of slotted rings, there are two additional parameters - the number of slots and the slot size. The slots are generally of the same size. In the case of the token rings, 5 the service discipline (exhaustive or non-exhaustive) must be spec i f ied. Apart from these physical parameters of the ring nets, the workload has a significant influence on their performance. In order to characterize the workload for a given ring net, one needs to know the distribution of arrival times of packets for each station and the distribution of packet sizes for each station. We shall make some simplifying assumptions to make the analysis mathematically tractable. All stations are assumed to have identical arrival distributions. The arrival pattern is assumed to be Poisson (i.e., exponential inter-arrival times) and all packets are assumed to be of equal length. Furthermore, in the case of slotted rings, if the packets are too large to fit into a slot, they must be broken into several minipackets before transmission and at the destination, these minipackets will have to be reassembled. If the packets are too small, a lot of ring bandwidth may be wasted due to the partially filled slots. In our models, the packet size is assumed equal to the slot size. With these assumptions, the workload can be specified simply by the mean network packet arrival rate, which is represented by X. The exact distribution of the location of stations on the ring does not have as much influence on performance as in the case of broadcast networks such as the Ethernet. The mean distance between two communicating stations can be assumed to be half the ring length. 6 1.2 Thesis Outline There are very few models in existence which describe ring networks. The models known to the author make use of processor sharing concepts. Our models described here use queuing theoretic concepts. The influence of the various parameters on the performance is tested exhaustively and performance comparisons are made for the various ring configurations and the operating modes. Before we describe our mathematical models (Chapter 3), we shall study some of the existing models in Chapter 2. In Chapter 4, we shall study the performance of the two types of ring networks. 7 CHAPTER 2 Review of some existing models Modelling of ring networks does not have a very long history and there are only a few existing models. We shall start our review of the various models by first considering the token ring and then the slotted ring. 2.1 Models of the Token Ring 2.1.1 Tanenbaum's Model [18] This model forms the basis for our model described in the next chapter. The service discipline at each station is assumed to be exhaustive, i.e., each station is permitted to transmit its entire queue of waiting packets after getting the token. The packet arrival at each station is assumed to have Poisson distribution and that all stations have the same mean arrival rate. The following notations are used in the model. N - Total number of stations on the ring X - Total arrival rate for all N stations (packets/sec) q - Mean number of packets accumulated at each station during the scan time, ix - Service rate (packets/sec) of each station w - Walk time (time taken by the token to go once around the idle ring) s - Scan time (time taken by the token to go once around the 8 ring - a function of the workload). The scan time consists of two components - the walk time w and the time taken to service the N.q packets. Therefore, s = w + N^CJ (1 ) M It is easy to derive an expression for q, the mean number of packets that accumulate at a station during a scan time. q = X .s (2) N Substituting in (1) we get s = w + X . s (3) M Hence, s = w (41- X/M If we represent X/M by p, we get s = _w_ (5) 1-P p may be interpreted as the utilization of the entire ring (not just one station). Notice that the scan time tends to infinity when the total arrival rate of the ring approaches the transmission rate of a single station and not the total transmission rates of all stations. This is quite obvious since only one station is allowed to transmit at any one time though packets are continuously arriving at all the stations. 9 Tanenbaum [18] does not derive an expression for the mean delay suffered by a packet, which can be defined as the delay from the time of arrival of a packet at the network to the time it is delivered at the destination station. These details, however, will be discussed in our model. 10 2.1.2 Model by Cherukuri et al. Cherukuri, Li and Louis [3] have derived a model for general token passing protocols that is extended to include the ring topology. Their model is based on the analysis of a polling system with multiple queues, due to Konheim and Meister [11], In their paper, Konheim and Meister have analyzed a communication system consisting of a number of buffered terminals connected to a computer by a single channel. The arrival distribution at every terminal is assumed identical. The terminals are polled in sequence. This general model has been adapted by Cherukuri, et al. to a token ring where the passing of a token from station to station is similar to cyclic polling discussed in [11]. In this model, the packet arrival process at each station is assumed to be Poisson and all stations are assumed to have identical mean packet arrival rate. The packets are assumed to be of constant size. Depending on the location of stations on the ring, the token-passing time between a pair of adjacent stations varies along the ring. Considering these parameters, the mean delay time is shown to be given by delay = 1 + b2 .a1 + S + a^O - S) (1 + N.r) 2r 2(1-S) 2 N 1-S where a^ = time unit by which token-passing time is expressed r = mean token-passing time between two stations 11 = I { (N-1)(1+d_) + w+d } N a, a, w = walk time d = mean signal propagation delay between any two stations 52 = variance of token-passing time between two stations = _1 { (N-1)(1+d_-r)2 + (w+d - r)2} N a, a, S = normalized total network packet arrival rate N = number of stations on the ring Based on this model, Cherukuri, et al. have analyzed the behaviour of token rings. Further discussion about the comparison of the results of this model with our models will be taken up in Chapter 4. 12 2.1.3 Bux's Model Werner Bux has modelled both the token ring as well as the slotted ring [2], The only performance measure considered is the delay-throughput characteristic. As in our models, delay is defined as the time interval between the generation of a packet at a station and its delivery at the destination station. This delay is made up of the queuing and access delay at the transmitting station, the transmission time of the packet and the propagation delay. To simplify the mathematical analysis, Bux made some assumptions. The arrival process at each station is assumed to be Poisson with the same mean value. The service discipline is assumed to be exhaustive. The distance between sender and receiver is assumed to be half the ring length. The symbolic notations used are : X - Aggregate arrival rate of all stations (packets/sec), Ld - Mean length of data in a packet (bits), Lh - Length of header (addressing and control information) C - Transmission rate (bits/sec) s - Scan time (sec) Tp - Service time of a packet (sec) = Lh+Ld C si - Time needed for passing the free.token from station i to station i+1 (assumed constant) N - Number of queues (stations) I Figure 1 Token ring model Figure 1 gives the model of the token ring. It is a single server queuing model with as many queues as there are stations on the ring. The rotating switch represents the cyclic servicing of the queues. The solution for such a queuing system has been derived by Konheim and Meister [11]. This solution has been adapted by Bux to obtain the following equation. delay = p.E[Tp*Tp] + E[Tp] + s(1-p/N) + s 2(l-p)E[Tp] 2(l-p) 2 where p = X.E[Tp], 1 4 2.2 Models of the Slotted Ring 2.2.1 Bux's Model This model for a slotted ring is also contained in [2]. The protocol for this ring requires the receiving station to return the slot with an acknowledgement to the sending station, which then marks the slot as empty and passes it to the next station downstream. A/H VN >yN - . ; V V V \ -Tp.( PROCESSOR SHARING) . I l v ^-CLOSEp LOOP nOpEL OF EP1PTX SLOT Figure 2 Slotted Ring Model Figure 2 shows the model of a slotted ring with only one slot. Each station on the ring has an associated queue. There is an extra queue in the model for the following reason. As we have seen, upon delivering its packet to the destination station, a slot travels around the ring to be marked empty by the sender before it can be used by the next station. This latency is represented by an extra fictitious customer who simply loops around for ever. The slot length dt is assumed to shrink to zero in order to simplify the mathematics. This idea is actually derived from the context of time-sharing systems where the equivalent of the slot length is the service time quantum. The 1 5 resulting model is termed "processor-shared" and is known to yield good approximations to the finite quantum model if the quantum is sufficiently small compared to the service time (i.e., in this case, if the slot size is much smaller than the packet size). Hence the packet size is assumed to be at least ten times the slot size. With these assumptions and using the standard results of queuing theory, the mean transfer time is shown to be (using the same notation as was used for the token ring model of the last section) delay = 2 E[Tpj + s 1-p 2 One more assumption is made at this stage that the slots will completely fill the ring length without leaving any gap between slots. Under this condition, the scan time s, the transmission rate C, the slot length Lh+Ld and the -number of slots n satisfy the relationship s.C = n(Lh+Ld) 16 2.2.2 Model by King and Mitrani King and Mitrani [9] have developed a model for the Cambridge Ring. The Cambridge Ring is a slotted ring in which the slot size is 38 bits. Only 16 out of the 38 bits are used to carry data and the remaining 22 bits are used to carry the source and destination addresses and other control information. This model is based on the processor-sharing concepts, as was discussed under Bux's model for the slotted ring. However, they have not discussed the mean delay suffered by a packet and hence there are no expressions for the mean delay. The throughput of the Cambridge Ring has been analyzed at the hardware level and also with respect to the Basic Block Protocol (see [9] for further details). 1 7 CHAPTER 3 Modelling of some Ring Networks 3.1 Introduction This chapter is concerned with deriving mathematical models for two of the most popular types of ring nets - the token ring and the slotted ring. In the case of the token ring, both the exhaustive and the non-exhaustive service disciplines are considered. The delay characteristics derived here reflect the behaviour of the networks at the hardware level. The higher level protocols generally modify these characteristics and these modifications depend upon the specifications of the protocols. These aspects fall beyond the scope of our models. 3.2 The Token Ring - Exhaustive Service Discipline Under the exhaustive service discipline, a station upon receiving a token is permitted to transmit all the packets waiting at that station. Here again, there are two modes of operation - multiple-token and single-token. In the multiple-token operation, a station generates a new token immediately after it has transmitted its last packet and passes this token to the next station downstream. In the single-token operation, the sending station waits for its packet(s) to return and a new token is generated only after the packets have been removed from the ring. From the reliability and recovery points of view, a single-token operation is better than the multiple-token one. 18 However, there are some tradeoffs since the single-token mode gives much higher delays, particularly when the number of stations on the ring is large. The following model is for multiple-token mode and can be easily extended to the single-token mode. We shall assume that the packet arrival has a Poisson distribution (i.e., exponential inter-arrival times), that the mean arrival rate is identical for every station on the ring and the mean service rate (bits/sec) at each station equals the channel transmission rate. The following notations are used: w = walk time (i.e., the mean time for the token to go once round an idle ring)(sec), s = scan time (i.e., the mean interval between' successive arrivals of the token at a station)(sec), N = number of active stations, X = packet arrival rate at each station (packets/sec), q = mean number of packets waiting at a station, PS = mean packet size (bits), C = mean service rate at each station (bits/sec) (=transmission rate of the channel). Since the scan time is the sum of the walk time and the mean time to service all the waiting packets in the net once, w + N.q.PS C (1) 1 9 The mean number of packets waiting at a station is simply the number of packets that has arrived at the station in between successive token arrival (i.e.,the scan time). Hence, q = s.X (2) Substituting (2) in (1), we get s = w (3) 1 - N.X.PS/C In the case of single-token operation, the scan time is increased by an extra delay equal to the walk time for each non empty station. This is because a non-empty station waits for its packets to return before it regenerates the token. The number of non-empty stations in the steady state can be represented by N.q. Therefore, s = w + N.q.PS + N.q.w (4) C q = s.X (5) Substituting (5) into (4), we get s = w 1 - N.X.PS/C - N.X.w (6) 20 Now mean delay time = mean time to wait for the token + mean time a packet has to wait after the token has arrived before it is placed onto the ring + mean propagation delay time. = s + q.PS + w 2 2.C 2 2 + s.X.PS + w 2.C 2 (7) 21 3.3 The Token Ring - Non-Exhaustive Discipline Under this service discipline, a station can send a maximum of n packets each time the token comes by. The value of n is usually 1. We shall derive an expression for the delay using the same notations adopted in the last section and with n=1. The scan time depends on the number of stations N1 with non-empty queues. If the stations are modelled as M/G/1 queueing systems then the probability of non-empty queue has been shown to be the product of the arrival rate (X) and the mean service time (s)(see [10]). Therefore, N1 = N.X.s (8) Now the expression for s can be written as follows: s = w + N1(PS/C) = w + N.X.s(PS/C) (9) Hence, s = w (10) 1 - N.X.PS/C For an M/G/1 queueing system, the mean queue length is given by 22 q = p + p2( 1 + c2) 2( 1-p) where c is the coefficient of variation of the service rate (ratio of standard deviation to the mean) and p is the ratio of the mean arrival rate to the mean service rate. We now make the additional assumption that the service time distribution at the station is exponential (i.e., the system is M/M/1). The coefficient of variation c for such a system is 1. Then the mean queue length at a station is given by 1 - p. = X/ (1/s) 1 - X/(1/s) = X. s (11) 1-X.s A packet arriving at a station will find q packets ahead of it. Now mean delay time = mean time to wait for the token + q scan times to service the packets ahead + packet transmission time + mean propagation delay. 23 Delay = s + q.s + PS + w (12) 2 C 2 If the scan time is assumed to be a constant., then the service time becomes deterministic. Such a system is called M/D/1 and its coefficient of variation of the service rate c is 0. This approximation will be compared to the M/M/1 approximation in Chapter 4. Both the M/M/1 and the M/D/1 systems are particular cases of the M/G/1 system. Now, if single-token operation is assumed then, as in the case of exhaustive discipline, the scan time is lengthened by an amount equal to the walk time for each non-empty station. i.e., s = w + N.X.s(PS/C + w) (13) Therefore, s = w (14) (1 - N.X.PS/C - N.X.w) The expression for delay is still (12) with the value of s given by (14). 24 3.4 The Slotted Ring We shall start by stating our assumptions. First, a message is assumed to be always correctly received at its destination station so that there is no need for the sending station to retransmit the same packet. The slots are assumed to be uniformly distributed over the ring (i.e., the gaps between slots, if any, are assumed to be equal in size). The packet size is assumed to be equal to the slot size. We also assume that the protocol requires a message slot to be emptied by its sender (i.e., a slot needs to go round the ring once before it may be used again). The following notations are used: N = number of active stations, n = number of slots on the ring, X = packet arrival rate at each station (packets/sec), w = walk time (i.e., time required by a packet to traverse the ring once)(sec), p = probability a slot is non-empty. If the system is not saturated, then p = N. X.w (15) n since w is the mean length of time a slot remains non-empty after it is filled with a packet. 25 Now the mean number of slots that will pass by the station before it gets an empty slot is given by bo ^ pK(1-p).k K'-O = p (16) (1-p) Hence the mean time the station waits (from the beginning of a slot) to find the beginning of an empty slot w n (1-p) Mean time for a station to put a packet onto the ring w n (1-p) w n w n( 1-p) (17) This is the mean service time for the station and the mean service rate u is given by its reciprocal. If the station is modelled as an M/M/1 queuing system then the mean time spent by a packet at a station is simply l/(mean service rate - mean arrival rate) where the mean service rate is given by the reciprocal of Equation (17) and the mean arrival 26 rate is X/N. Therefore, delay = __w + 1 + w (18) 2n M " X/N 2 where n = n(1-p) w The first term in the delay expression is the mean time to get to the beginning of a slot. The second term gives the mean queue wait time a packet spends in the station before being put onto the ring. The last term is the mean propagation delay of the packet. 27 CHAPTER 4 Performance Comparisons 4.1 Introduction The mathematical models derived in the last chapter can be used to study the behaviour of the three types of ring networks. We have chosen the mean delay time as our performance index (mean delay is the time interval between the generation of a packet at any station and its arrival at the destination station). We shall study the effect of the various ring parameters on mean delay time. These parameters include the network load, the number of active stations on the ring and in the case of the slotted ring, the number of slots and the slot size. In the case of the token ring, we shall also analyze the effect on performance due to the service discipline (exhaustive or non-exhaustive) and also the mode (single or multiple-token). One of the advantages of having a local area network is to provide easy access to the various hardware and software resources to users spread over various physical locations. Accessibility may be enhanced by adding more stations onto the ring. Hence the effect of increasing the number of stations on performance for a given network load is of interest and shall be studied. In the rest of the thesis, the ring bandwidth is assumed to be 3 MHz, unless otherwise specified. 28 In all the graphs in this chapter, mean delay time is plotted against the normalized load. The normalized load can be defined as the ratio of the total arrival rate for the network (in bits/sec.) to the channel transmission rate (also in bits/sec). There are two reasons for such a choice. Firstly, we eliminate channel transmission rate as an explicit parameter and secondly, normalized load has more intuitive meaning than absolute load. The normalized load varies between 0 and 1. When it is 0, there is no network traffic or load at all and when it is 1, the channel is fully utilized. The delay time is also normalized in order to meaningfully compare delays when different packet sizes are involved. This is generally done with a reference packet of size B. The normalized delay for a packet of size X is its absolute delay multiplied by B and divided by X. Therefore the normalized delay is the delay to transmit B bits of information. 4.2 The Token Ring ^ Exhaustive Service Discipline We shall study the effect of increasing the load and also increasing the number of stations on the ring for a given load. The results are shown in Figure 3. For any given N (number of stations) the delay increases with increasing load. This is due to the increased queue wait time at a station at higher loads. Under light load, most of the delay can be attributed to the time spent waiting for the token to arrive and the propagation time (i.e., the walk time is the single most important factor in determining the delay time). Increasing the Figure 3 : Absolute Mean Delay vs. Normalized Load for a Token Ring (Exhaustive) 30 number of stations for a given load has the effect of increasing the walk time since each extra station introduces an extra delay in the ring. This explains the increased delay as N increases when the load is light. Under heavier loads, a greater proportion of the total delay is due to the queue wait time. Increasing the number of stations for a given load reduces the mean queue length at each station. Due to these two opposing effects of increased scan time and reduced queue length, the curves cross each other as shown in Figure 3. One other important point to note is that for any given load level (<1), increasing the number of stations to a large value (such as 512) will increase the delay time significantly. Nonetheless, the system remains stable (i.e., finite delay and finite queue length). This results from the fact that both the queue length and the mean delay tend to infinity only when the scan time tends to infinity, which happens only if the number of stations N tends to infinity. 31 4.3 The Token Ring ^ Non-exhaustive Service Discipline Figure 4 plots the absolute delay versus normalized load for a token ring with non-exhaustive service discipline where each station can send at most one packet upon receiving the token. All the ring parameters and the workload parameters are identical to those in Figure 3. Comparing Figures 3 and 4, we can see that with the non-exhaustive service discipline the network saturates at a lighter load than with the exhaustive discipline. Similar results are reported by Cherukuri, et al. [3]. Moreover, the smaller N is, the more rapidly the system saturates. Thus the cross-over points for different N's have shifted significantly to the left compared to the case of the exhaustive service discipline. This phenomenon may be explained by the fact that for a given workload, the smaller the number of stations N on the network, the larger is the queue of waiting packets at each station. In the non-exhaustive discipline, each packet will have a mean wait time in the queue which exceeds that in the exhaustive discipline by the product of the mean number of packets in the queue ahead of it and the scan time. Thus the smaller N is, the more rapidly the system approaches saturation. Note also that increasing the number of stations on the ring makes the behaviour under this scheme more and more like that of the exhaustive scheme (compare Figures 3 and 4 for N=512). A qualitative explanation of this behaviour is that with the increase in the number of stations for a given load, the mean queue length at a station will drop below 1 in which case there is no difference between the two service disciplines. A quantitative analysis of this scenario is given below. Figure 4 : Absolute Mean Delay vs. Normalized Load  for a Token Ring (Non-exhaustive) 33 From the delay expression for the token ring (exhaustive) (Equation (7) of Chapter 3), we see that the delay tends to infinity (network saturation) when the scan time tends to infinity. From Equation (3) we have s = w 1 - N.X.PS/C Hence the scan time tends to infinity when N.X.PS = C. i.e., X(limiting) = C (19) N.PS In the case of non-exhaustive discipline, the scan time cannot exceed a certain maximum value, which is the sum of the walk time and the time to transmit N packets (i.e., when every station on the ring has at least one packet to transmit). However, the delay tends to infinity when the queue length becomes infinite. From (11), the limiting case is reached when X.s = 1. Substituting for s and simplifying the expression, we get X(limiting) = C (20) w.C + N.PS Comparing (19) and (20), it is clear that the saturation load for the non-exhaustive case is less than that for the exhaustive case, due to the extra term in the denominator of (20). However, 34 with the increase in the number of stations (N), the two limiting loads approach one another. From the above discussions, one can see the tradeoffs between the two disciplines. With the exhaustive discipline, a single station may hog the network, especially under heavy loads. Such a situation can be avoided by limiting the number of packets a station can send during each scan of the token. This however adds extra overhead and gives longer delay times. Under very light loads, the difference between the two disciplines is not very significant. Cherukuri, et al. [3] have discussed qualitatively the differences between the exhaustive and non-exhaustive service disciplines. Though they have not presented any expression for the two limiting load levels, their conclusions are similar to ours. They have also plotted delay versus normalized loads for N = 10, 500 and 1000 and the graphs show increasing delay with increasing number of stations. 35 4.4 Single-Token versus Multiple-Token In Chapter 3, we derived expressions for the mean delay for the multiple-token operation and the models were extended to include the single-token mode. Figures 5 and 6 show the differences in performance between the two modes of operation. The single-token mode is exhibiting longer delays under the same load than the multiple-token mode both for the exhaustive and the non-exhaustive service disciplines. This is due to the extra overhead involved. From Figure 5, we can see that with the increase in the number of stations on the ring, the single-token mode performs even worse. However, the single-token mode provides a more reliable operation of the ring and may be desirable if the network load is known to be very light or if the delays are not critical for the intended applications. 36 Figure 5 : Single-Token vs. Multiple-Token Modes  for a Token Ring (Exhaustive) = Multiple-token = Single-token 37 Figure 6 : Single-Token vs. Multiple-Token Modes  for a Token Ring (Non-exhaustive) = Multiple-token = Single-token 38 4.5 Comparison with Simulation Results In order to check the correctness of the results of the analytic models, simulation models are designed (see appendix). The simulation models also make use of some assumptions which are listed below: 1) the packet arrival process at any station is Markovian, 2) the mean packet arrival rate at every station is identical, 3) all packets are of equal size. The programming language used for all the simulation work is Pascal. These are discrete-event simulators with two types of events - the arrival of a packet (at any station) and the arrival of the token (at any station). A queue of packets is represented by a linked-list of records (a packet is represented by a record structure). For ease of implementation, all the N queues are combined into a single queue and each packet carries with it the station number where it belongs. Thus only those packets which have their station number X are transmitted (deleted from the linked list) when station X receives the token. In order to find the delay suffered by each packet, its time of arrival at the network is stored in the record structure. The mean delay is computed over a large number of packets. A good simulation model should also take into consideration the start up effects (which must be compensated for), as otherwise the delays are likely to be underestimated. This is due to the fact that queue lengths are zero when simulation is started and the first few packets to arrive will suffer delays 39 less than those suffered by packets that arrive in the steady state. Our simulation models eliminate such transient effects by collecting statistics for delay only after steady state is reached. Figure 7 compares the results of our analytic model with those of our simulation model for the token ring under exhaustive service discipline (multiple-token mode). Very close agreement is noticed at all load levels for different number of stat ions. Figure 8 compares similar results in the case of non-exhaustive service discipline (multiple-token mode). In Chapter 3, we modelled a station at first as an M/M/1 system and then we proposed an alternative model (M/D/1). The former model assumes exponential service time distribution and the latter assumes constant service time. From Figure 8, we see that the M/D/1  model agrees better with the simulation results. This is due to the fact that the variation in scan time is not significant once steady state is reached and hence it is more accurate to assume it to be a constant in our analytic model. Figure 7 % Comparison of Analytic and Simulation Results  for a Token Ring (Exhaustive) = Analytic + + + = Simulation Figure 8 : Comparison of Analytic and Simulation Results for a Token Ring (Non-exhaustive) = Analytic (M/D/1) = Analytic (M/M/1) + + + = Simulation M=128 ~1 '1.0 0.0 ~r 1 1 i 0.2 0.4 0.6* 0.8 NORMALIZED LOAD . 42 4.6 The Slotted Ring In the case of the slotted ring, there are several parameters which influence the delay characteristics of the ring. In addition to the network load, we shall study the effect on performance due to the number of slots, the slot sizes and the number of stations on the ring. In Figure 9, the absolute delay is plotted against the normalized load for a fixed number of stations (i.e., 128). The slot size is also kept constant at 64 bits. The number of slots on the ring (denoted by n) is varied from 1 to 8. Artificial delays are added to the ring (usually implemented by having shift registers on the ring) in order to accommodate the extra slots whenever the natural delay of the ring is found insufficient for that purpose. Under very light load, most of the delay can be attributed to the time spent waiting for the slot to arrive and the propagation time. This explains the longer delays with increasing number of slots under light loads (since the walk time increases with the number of slots). However, the probability of finding an empty slot also increases as the total number of slots increases. This reduces the mean queue wait time. Under heavier loads, this effect has a greater influence on the total delay and hence the mean delay time is reduced with the increase in the number of slots. Figure 10 shows the effect of varying the number of slots on the ring when the walk time is fixed. The number of stations on the ring is kept constant at 128. As the number of slots is increased, the slot size is correspondingly reduced in order to Figure 9 : Absolute Mean Delay vs. Normalized Load  for a Slotted.Ring N = 128, PS = 64 bits Figure 10 : Normalized Delay vs• Normalized Load  for a Slotted Ring N= 128, Reference Packet Size = 256 bits 45 maintain the walk time a constant. As different packet sizes are involved, it is more meaningful to consider the normalized delay instead of the absolute delay. The reference packet size for normalizing the delay is 256 bits. From Figure 10 it is clear that larger packet sizes give lower delay. The reason for the increased delay with smaller packet sizes is the extra transmission overhead involved when a larger number of packets need to be transmitted to carry the same amount of data. Next, we consider physically lengthening the ring while keeping the network load, the number of stations and the slot size constant. Obviously the gaps between the slots grow in size. Whenever the total size of the gaps becomes large enough to accommodate an extra slot, we shall do so. The initial length of the ring is just enough to accommodate one slot. Figure 11 shows the effect of lengthening a slotted ring with 10 stations and with a slot size of 64 bits. Initially as the ring grows, the walk time increases and the mean delay also increases. When the gap becomes large enough to accommodate a second slot, there is a sudden decrease in the delay time as the number of slots is now increased to 2. If the lengthening of the ring is continued, one can observe a marked sawtooth effect as shown in Figure 11. Similar sawtooth effect is also reported by King and Mitrani [9] in the case of the Cambridge Ring, which is also a slotted ring. It is therefore clear that other things being equal, performance  is maximized when there is no gap between slots. 46 Figure 11 : Absolute Delay vs. Length of Ring (Slotted) PS = 64 bits, Total Network Load .= -100 packets/s-a a. a to. CO o i—.a >-CC _J UJ a r> _i o CO oa 3 o 0,0 T T 40.0 . BO.O 120.0 160.0 RING LENGTH (MTRS) (X101 ) 200. D 47 Next we consider the effect of increasing the number of stations on the ring for a given load. Figure 12 shows the absolute delay plotted against the normalized load for various number of stations. As we increase the number of stations from 2, the walk time increases linearly as each extra station adds extra delay. This explains the increase in delay as N increases under light loads. Under heavier loads, the scenario is a little different since most of the delay comes from queue wait. When the number of stations is increased from 2 for a given moderate load, the delay decreases initially. This is because the decrease in the arrival rate at a station exceeds the decrease in the service rate M. A further increase in the number of stations results in less rapid reduction of the arrival rate and a more rapid reduction in the service rate at a station. At some point the mean delay begins to increase. This suggests the possible existence of an optimum value for N. For the parameter values selected here, the optimum N is 17. This number is not the optimum at all load levels but is so only near saturation. However, for lighter loads, this number still gives near-minimum delays. It is possible to find the optimum N analytically, as will be seen in the next section. This knowledge of optimum N can be useful in designing a slotted ring. No such optimum number of stations is found to exist for the two types of token rings where both the arrival rate at a station (X/N) and the mean service rate (1/s) of a station decrease rapidly when N is initially increased from 2 and both of them taper off to a more gradual decrease for larger N. Figure 12 : Absolute Mean Delay vs. Normalized Load  for a Slotted Ring n = 4, PS = 64 bits. 49 4.7 Optimization of the Number of Stations on a Slotted Ring At any load level, the optimum N can be deduced by taking the partial derivative of the mean delay with respect to N (Equation (18) of Chapter 3) and equating it to zero. The walk time w and the mean service rate of a station n are functions of N but the number of slots n and the load X are independent of N. We shall denote the mean delay by t. t = __w + 1 + w 2n M ~ X/N 2 (21 ) The walk time w consists of two parts - the delay due to the physical length of the ring (plus artificial delays) and the delay introduced by the stations. Let k be the delay introduced by each station. Then, w = w (length) + k.N Therefore, w = k SN Similarly, du/c)N can be computed from Equation (17) of Chapter 3, by substituting for p and taking the partial derivative with respect to N.. 50 -kn Equating (21) to zero, we get (M - X/N)"2 ( UN + X_[ = k + k (22) N2, 2 2n Substituting for y and BM/AN and assuming k to be 1-bit delayd.e., 0.33 microsec. for a 3 MHz ring), the above equation can be solved for given values of X and n. It reduces to a quadratic equation in N. When solved, it gives one negative root and one positive root, the latter one being considered the optimum value of N. For n=4 and near-saturation X, the positive root of Equation 22 is close to J_7. This agrees very well with the optimum N observed in Figure 12. As the load is reduced from the saturation value, the optimum value of N also reduces gradually as one would expect. Equation (22) is a general one that can be applied to any ring configuration. The value of optimum N can be computed for some other combination of ring parameters as well. We can vary the ring length and the number of slots by the same proportion. The above configuration had 4 slots and the walk time due to the natural length of the ring was 100 usee. With. 2 slots and a 50 Msec, walk time (i.e.,half the current ring size), the optimum N (for near-saturation loads) reduces to J_2. For 8 slots and a 200 jusec. walk time (twice the present ring size), it increases to 24. 51 4.8 Comparison with Simulation Results As with the case of the token rings, we verify the correctness of the analytic model by comparing its results with those from a simulation model (see appendix). This model simulates a station under the assumption of Markovian arrival of packets of equal size. No assumption is made about the service time distribution. This is a discrete-event simulator where the two events are the arrival of a packet and the arrival of a slot. However, every arriving slot is not necessarily empty but may be full with a certain probability which depends on the total arrival rate at all the stations. The delay statistics are collected over a large number of packets. The transient effects are eliminated by collecting statistics only after the steady-state has been reached. Figure 13 compares the results of the analytic model with those of the simulation model. A close agreement between the results were observed for various load levels and different number of stations. 52 Figure 13 : Comparison of Simulation and Analytic Results  for a Slotted Ring = Analytic + + + + = Simulation 53 CHAPTER 5 Conclusion In the last four chapters, we have analyzed the two common types of ring networks - the token ring and the slotted ring. Analytic models have been developed based on well known results of queueing theory. Simulation models were also developed which confirmed the correctness of the analytic models. In the case of the token rings, two different service disciplines were considered at the stations - the exhaustive and the non-exhaustive (sometimes also referred to as the round robin scheme). Each scheme has its advantages and disadvantages. The exhaustive discipline gives lower delays than the non-exhaustive one. However, under heavier loads, there is the possibility of one station hogging the entire network. The non-exhaustive scheme provides a higher degree of fairness to the stations on the ring, i.e., it gives each station a fair chance to transmit at the expense of longer delay time. There are two modes of operation of the token rings - the single-token and the multiple-token. Our models were extended to include these two modes as well. The single-token mode is characterized by having either packets from only one station or just the token with no data packet cycling in the ring at any time. It is known to provide higher reliability. However, as was discussed in Chapter 4, it also gives higher delays than the multiple-token mode. Hence the choice of the mode is dictated by the environment and the applications for which the ring is used. 54 In the case of the slotted rings, the effects of the various ring parameters on the delay characteristics were discussed. For a given ring configuration, an optimum number of stations was found to exist which gives minimum or near-minimum delays under all load levels. The value of this optimum number was also confirmed analytically. No such optimum was found to exist for the two types of token rings for reasons discussed in Chapter 4. A knowledge of the optimum number of stations can be useful both in the ring design and for tuning an existing network for better performance. Usually, several terminal devices are hooked onto a single station on the ring. A knowledge of an optimum number of stations can be used to redistribute the terminal devices between the number of stations that would maximize the performance of the ring. Even when ring expansions are contemplated, the number of stations for the expanded network can be planned in advance. All the models described in this thesis are at the hardware level with very few higher level protocols being considered. However, these low level models provide us with an understanding of the behaviour of these ring networks under various conditions. Such an understanding is essential before a more elaborate model can be designed which takes the higher level protocols into consideration. It is hoped that the ideas presented in this thesis will be of help to ring network designers as well as to researchers in the area of local area networks. 55 Future Research Directions More work can be done to improve the accuracy of the analytic models and make them more realistic. For example, the packet size distribution can be considered in the models instead of assuming all packets to be of the same size. The mean arrival rate at every station need not be identical and the distribution of arrival rates at the various stations can be considered in the models. The mean separation between the sending and the receiving stations depends on the distribution of stations on the ring. This separation is equal to half the ring length only if the stations are uniformly distributed along the ring and if every station is equally likely to send packets to any other station. These details can also be considered in the models. Finally, the higher level protocols have a significant effect on the delay characteristics and hence should be considered in future models. It must however be noted that it is inevitable that some simplifying assumptions be made in order to make the analysis mathematically tractable. The simulation models presented in this thesis are fairly general and can be used to study the effect of the parameter variations mentioned above. The models presented in this thesis (both analytic and simulation) provide a good groundwork for further research in the directions cited. More quantitative measurements are needed to enhance our understanding of the performance of ring nets. 56 REFERENCES [I] Blair, G.S., "A Performance Study of the Cambridge Ring", Computer Networks, Vol. 6, No. 1, Feb. 1982, pp. 13-20. [2] Bux, W., "Local Area Subnetworks : A Performance Comparison", IEEE Trans, on Communications, Vol. COM-29, No. 10,Oct. 1981, pp. 1465-1473. [3] Cherukuri, R., Li, L. and Louis, L., "Evaluation of Token Passing Schemes in Local Area Networks", IEEE Proc. Computer Networking Symposium, Dec. 1982, pp. 57-68. [4] Clark, D.D., Pogran, K.T. and Reed, D.P., "An Introduction to Local Area Networks", Proc. IEEE, Vol. 66, No. 11, Nov.1978, pp. 1497-1517. [5] Cotton, I.W.,"Technologies for Local Area Computer Networks", Computer Networks, Vol. 4, No. 3, July 1980, pp. 197-208. [6] Graube, M., "Local Area Nets : A Pair of Standards", IEEE Spectrum, Vol. 19, No. 6, June 1982, pp. 60-64. [7] Hamacher, V.C., "Local Area Networks", Proc. of CIPS, May 1982, pp. 243-254. [8] Kennington, C.J., "Problems inherent in the current ring protocols", INDRA Note 1040, Dept. of Computer Science, University College, London, Jan. 1981. [9] King, P.J. and Mitrani, I., "Modelling the Cambridge Ring", Performance Evaluation Review, Vol.11, No.4,1982, pp.250-258. [10] Kleinrock, L., Queueing Systems Volume I, Wiley, 1975. [II] Konheim, A.G. and Meister, B., "Waiting lines and times in a system with polling", JACM, Vol. 21, No. 3, July 1974, pp. 470-490. [12] Kryskow, J.M. and Miller, C, "Local Area Networks Overview -Part 1 : Definitions and Attributes", Computer Design, Vol. 20, No. 2, Feb. 1981, pp. 22-35. [13] McQuillan, J.M., "Local Networks Architectures", Computer Design, Vol. 18, No. 5, May 1979, pp. 18-26. [14] Nadkarni, A.V., Chanson, S.T. and Kumar, A., "Performance of Some Local Area Network Technologies", IEEE Digest of Spring Compcon Conf., March 1983, pp. 137-141. [15] Needham, R.M., "System Aspects of the Cambridge Ring", Proc. 7th Symposium on Operating Systems Principles, Dec. 1979, pp. 82-85. 57 [16] Saltzer, J.H., Clark, D.D. and Pogran, K.T., "Why A Ring?", SIGCOMM Computer Comm. Review, Vol. 11, No. 4, October 1981, pp. 211-217. [17] Saltzer, J.H. and Pogran, K.T., "Star-Shaped Ring Network with High Maintainability", Computer Networks, Vol.4, No.4, July 1980, pp. 239-244. [18] Tanenbaum, A., "Computer Networks", Ch.7, Prentice Hall,1981. [19] Wilkes, M.V. and Wheeler, D.J., " The Cambridge Digital Communication Ring", Proc. Local Area Commun. Network Symposium, Mitre Corp., May 1979, pp. 47-61. 58 APPENDICES APPENDIX I Program Listing for the Simulation of a Token Ring Program tokenring; Const N=32; ps=64; c=3000000; Type packet = RECORD arrtime:real; station:integer; next:packet; end; Var na, naa, pois, i, stn:integer; delay, totdelay:real; t, tpa, tta:real; head, tail, p1, p2:@packet; nq: integer; w: array (1..N) of real; x, t1, s, walk:real; lambda:real; mean,dseed,temp:real; nr,ier:integer; found:boolean; (used for non-exhaustive discipline] exhaustive:boolean; {decides the service discipline] FUNCTION random(x:real):real; Fortran 'RAND'; 60 PROCEDURE intpacktime; {inter-arrival times for packets} begin x:=random(0.0); t1: = (- l)*0.0/lambda) *LN (x) ; end; PROCEDURE initialize; begin exhaustive:=FALSE; {i.e.,non-exhaustive} delay:=0.0; totdelay:=0.0; found:=FALSE; na:=0; naa:=0; walk:=0.0001+(N*0.33)*0.000001; for i:= 1 to N do {for uniform distribution of stations} w(i):=(0.0001+(N*0.33)*0.000001)/N; stn: = 1; head:=nil; tail:=nil; nq:=0; t:=0.0; x:=random(0.7978); intpacktime; tpa:=t1; tta:=walk/2.0; end; {initialize} 61 PROCEDURE packetarr; {process arriving packet} begin t:=tpa; {advance time} intpacktime; tpa:=tpa+t1; {schedule next arrival} new(p1); p1@.arrtime:=t; p 1 @.stat i on: = 1+TRUNC(random(0.0)*N); p1@.next:=nil; if nq=0 then {start a queue} begin head:=p1; tai1:=p1; end; else begin tail@.next:=p1; tail:=p1; end; nq:=nq+1; end; {packetarr} PROCEDURE tokenarr; {process arriving token} begin t:=tta; {advance time} if nq >= 1 then {if a queue exists} begin 62 p2:=head; while (p2 -•= NIL AND -'found) do begin if p2@.station = stn then begin delay:=t-p2@.arrtime+(walk/2.0) + (ps/c) ; if na >500 then totdelay:=totdelay+delay; na:=na+1; if na > 500 then naa:=naa+1; if -"exhaustive then found:=TRUE; nq:=nq-1; {advance time by packet transmission time} t:=t+(ps/c); if t >= tpa then begin temp:=t-tpa; t:=t-temp; packetarr; t: =t+temp; end; end; p2:=p2@.next; end; end; tta:=t+w(stn); {schedule next arrival} stn := (stn mod N) + 1; {update station number} found:=FALSE; end; {tokenarr} BEGIN lambda:=8000; initialize; while naa < 1000 do begin if tpa <= tta then packetarr; else tokenarr; end; writelnC '); writelnC NORMALIZED LOAD IS ',lambda*ps/c); writelnC MEAN DELAY IS ', totdelay/naa); END. APPENDIX II Program Listing for the Simulation of a Slotted Ring Program slotring; Const N=32; ps=64; c=3000000; no=4; Type packet = RECORD arrtime:real; next:packet; end; Var na, naa, pois, nq, i:integer; delay, totdelay:real; t, tpa, tta:real; head, tail, p1, p2:@packet; w,s:real; x,t1,tempor:real; lambda:real; mean,dseed,temp:real; nr , ier:integer; FUNCTION random(x:real):real; Fortran 'RAND'; PROCEDURE intpacktime; begin x:=random(0.0); t1: = (- l)*0. O/lambda) *LN (x); end; PROCEDURE initialize; begin delay:= 0.0; totdelay:=0.0; na:=0; naa:=0; w: =0.0001 + (N*0.33)*0.000001 ; head:=nil; tail:=nil; nq:=0; t:=0.0; x:=random(0.7978) ; intpacktime; tpa:=t1; tta:=w/no; end; {initialize} PROCEDURE packetarr; {process packet arriva begin t:=tpa; {advance time} intpacktime; tpa:=tpa+t1; {schedule next arrival} new(p1); p1@.arrtime:=t; p1@.next:=nil; if nq=0 then {start a queue} begin head:=p1; tai1:=p1; end; else begin taiId.next:=p1; tai1:=p1; end; nq:=nq+1; end; {packetarr} PROCEDURE slotarr; {process slot arrival} begin t:=tta; {advance time} tta:=t+(w/no); {schedule next arrival} if N*lambda*w/no > N/(N+1) then tempor:=N/N+1; else tempor:=N*lambda*w/no; if random(O.O) > N*lambda*w/no then {slot empty} begin if nq >= 1 then {if a queue exists} begin p2:=head; head:=head@.next; if head=nil then tail:=nil; delay:=t-p2@.arrtime+(w/2.0)+(ps/c); if na > 500 then totdelay:=totdelay+delay; na:=na+1; if na > 500 then naa:=naa+1; nq:=nq-1; {advance time by packet transmission time} t:=t+(ps/c); if t >= tpa then begin temp:=t-tpa; t:=t-temp; packetarr; t:=t+temp; end; end; end; end; {slotarr} BEGIN lambda:=1000; initialize; while naa < 1000 do begin if tpa <= tta then packetarr; else slotarr; end; writelnC NORMALIZED LOAD IS ',N*lambda*ps/c); writelnC MEAN DELAY IS totdelay/naa); END. .63, $1.63T 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0051841/manifest

Comment

Related Items