”5. Lin?“ bulh'nfh' 4,15. Harm 1: . \- ”} ‘..). mm' .. .1 11.12;”. 11$ .1". 7.; 1 11:.."1. '11‘1‘I"J':"_'.|." warn. 1 . ...‘f ‘ ”11".: THE 81‘ (1618193 31293 01555 2445 This is to certify that the dissertation entitled MODELLING AND ANALYSIS OF TOKEN PASSING COMPUTER NETWORKS presented by Vernon Joseph Rego has been accepted towards fulfillment of the requirements for Ph.D. Computer degree in . Sc1ence £11:an H. M1 Major professor Lionel M. Ni Date June 12. 1985 MS U is an Affirmative Action/Equal Opportunity Institution 0- 12771 LIBRARY Michigan State University PLACE It RETURN BOX to remove thie checkout from your record. TO AVOID FINEB retum on or betore date due. DATE DUE DATE DUE DATE DUE MSLLIe An Affirmative ActhNEquel Opportunity lnetltuion was.” MODELLING AND ANALYSIS OF TOKEN-PASSING COMPUTER NETWORKS BY Vernon J. Rego A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Computer Science 1985 Copyright by VERNON JOSEPH REGO 1985 ii v ABSTRACT MODELLING AND ANALYSIS OF TOKEN-PASSING COMPUTER NETWORKS BY VBI'DOD J. R890 This thesis is concerned with the performance modelling of token-passing protocols on local area computer networks. A token-passing system operating on a baseband cable may be viewed in a queueing-theoretic framework. The computer stations on the system represent queueing stations at which randomly arriving packets queue for service. A free token behaves as a single server who travels around the network, allowing each station that is visited a chance to make a transmission on the channel. The random time taken by a free token to cycle around an operational network, called the token's cycle-time, is an analytically useful measure. The derivation of cycle-time distributions for general asymmetric N-station systems is a primary contribution of this research. Both exact and approximate forms of this distribution are derived. The exact approach is based on general distributions for packet arrival. service, and token-passing times, while the approximate approach uses a Poisson arrival assumption. In modelling performance, the exact and approximate cycle-time distributions lead to exact and approximate queueing measures, respectively. Exact measures are obtained by using Poisson packet arrivals and semi-Markovian transmission times. Some results on the invariance and insensitivity of cycle-times are obtained, along with distributions for busy and vacation periods of the channel, with respect to each station. Approximate measures are obtained via an independence assumption that leads to single server queues with dependent service. This is due to serial cycle-time dependencies which arise at all but extreme loads. Methods of analyzing such queues, including schemes for estimating service-time variance, covariance matrices, marginal and joint cycle-time distributions, and correlation effects are discussed. Under certain conditions, it is shown that limiting and asymptotically stationary cycle-time distributions exist. Conditions for stationarity and system stability are derived, and simple stability measures are introduced. Methods for obtaining the distribution of system throughput and a new fairness measure are described. The link between multiqueueing systems with different service and queue emptying disciplines is demonstrated with the aid of a complex service discipline for which approximate cycle-time distributions are derived. Dedicated to Stanislaus & Pelicita & the rest of the clan iii ACKNOWLEDGEMENTS I would like to express my deepest appreciation to my advisor Lionel Ni for his friendship, patience and guidance during my graduate education. Also, my thanks go to Herman Hughes for his support of my endeavours. I would like to thank Raoul Le Page, Lewis Greenberg, and Richard Houang for agreeing to serve on my Ph.D. guidance committee. I am indebted to Richard Dubes and George Stockman for their objective views and good advice, to Richard Hoffman for being a keen test of new ideas, and to Steven Gadbois for being a good mathematician. For the many people who have contributed in various ways to make this task lighter, I would like to greet each with a humble 'thank you'. I gratefully acknowledge help from my co-employees at the M.S.U Computer Lab., with special thanks to Helen Ramsey, Deloris Morgan, Andrew Pittsley, Chuck Severance, Richard Wiggins, Mike Giddings, Bob Matson and Bruce Johnston. Last of all, I wish to express my sincere thanks to my three special families for the many months of help and tolerance. This is a special thank you, for Sophia, Graham, and Tricia Dorn, Richard and Pat Adadow, and the Rego family. iv TABLE OF CONTENTS LIST OF FIGURES .0.0..O0.0.0.0000000000000000000000000.00.00.00.00. Viii LIST OF SWLS 0......O....0....0.0....0......OOOOOOOOOOOOOOOOOOOOOO ix mpter 1: INTRODUGION OOOOOOOOOOOOOOOOOOOOOO0.0000000000000000000000 l 1.1 1.2 1.3 1.4 1.5 1.6 Chapter 2 .1 2.2 Chapter 3.1 3.2 3.3 3.4 3.5 Chapter ‘.1 Simple Problem Statement l Token-Passing Protocols 4 Classification Of Multiqueueing Systems '7 Review Of Previous Work l2 Sumary Of Contributions 18 organization or The TheSis OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 23 A QUEUEING mDEL FOR Tom-PASSING scams 00.00.000.00... 26 The Multiqueue And Cyclic Server Model 26 mkw Renewal Processes O00.0.00...OOOOOOOCOOOOOOOOOOOOOO 32 CYCLE-TIME DISTRIBUTIONS VIA SERVICE VECTORS ............. 36 The Markov Chain Of Vector Transfers 38 Asymetric Systems With General Distributions 39 Application Of The SV Method 48 Invariance Of Cycle-Times 55 SW .0.0..0.00000000000DOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO S7 PERFORMANCE MEASUREMENTS USING SERVICE VECTORS ........... 60 Busy Periods, Vacation Periods, And Service Times . . . . . . . . 62 Distributions Of Busy And Vacation Periods Of The Token . . 64 The Countable State Markov Renewal Matrix 71 Distribution Of Packet Queue Length ...................... 72 V Chapter 5.1 5.2 5.3 5.4 5.5 5.6 5.7 Chapter 6.2 6.3 6.4 6.5 6.6 6.8 6.9 6.10 Distribution Of Packet Queueing Delay .................... 74 An Application Of The SV Method ...... ........ ............ 75 Distribution Of Channel Throughput ....................... 77 SW ........... ... ........ .0... OOOOOOOOOOOO O. ........ O 80 CYCLE-TIME DISTRIBUTIONS VIA SERVICE PROBABILITIES ....... 82 The Markov Chain Of Server Transitions ................... 83 Service Probabilities For Poisson Arrivals ............... 86 Asymmetric Systems With Exponential Distributions ........ 88 Symmetric Systems With Exponential Distributions ......... 91 Stationary Cycle-Time Distributions ....... ..... . ..... .... 95 serial Demence Of CYCIe-Times O O O O O O O ..... O O O O O O O O O O O O 100 sumry 00.......OOOOOOOOOOOOOOOOOOOOOO0.0000000000000000 110 PERFORMANCE MEASUREMENTS USING SERVICE PROBABILIES ...... 113 The M/G/l Approximating Model ........................... 115 Covariance Matrix Obtaining Methods ..................... 116 Marginal Distributions Of Dependent Cycle-Times ......... 120 Principle Component Ananlysis For Quasi-Service Times ... 122 Distribution Of Packet Queue Length ..................... 124 Distribution Of Packet Queueing Delay ................... 127 Channel Utilization ..................................... 128 The M/G(r+l)/l Approach ................................. 130 Queue Length Distribution Via M/G(r+l)/Systems .......... 132 SM ............OOOOOOOOO0.000............OOOOOOOOOOO 13‘ vi Chapter 7: STABILITY AND FAIRNESS IN TOKEN-PASSING SCHEMES . ........ 135 7.1 7.2 7.3 7.4 7.5 7.6 Chapter 8.1 8.2 8.3 8.4 8.5 8.6 8.7 stailitYOf ms SCth 0000...... ..... 000000.000.0.00. Stability Index: A Measure Of System Stability .......... Issues Of fairness ........... amasure Of Fairness O..........O....0.000‘000.0.....OO0O Approximate Distributions For Token-Intervisit Times .... Summary ...................... MHIVE mm PASSING ms 00....... ........ 0....0... Description Of Model Distributions .. ............ . ...... . Cycle-Times For NATP And ATP ..... .............0.0....... Service, Switch, And Scheduled-Walk Distributions ...... . The Markov Chain Of Server Transitions .. ........ . ....... Cycle-Time Distributions For Asymmetric Systems ......... Computation Of Probabilities For The First Cycle ........ stationary Distributions ..0000000000.00.000.00.00000..00 5m .....O...0000.00.0.........0...0.0.0.000000000... Chapter 9: CONCLUSIONS AND FUTURE RESEARCH .... ”Pmlx: Prwts ....00.........O...0.0.0...0....00.00.00.000000000. LIST OF mas ......O...O0.000..000 vii 136 139 142 144 148 153 156 159 159 162 163 168 172 177 178 180 189 199 4a 4b 5a 5b 5c 7a 7b 8a 8b LIST OF FIGURES Conceptual view of Simple service schemes ...................... 3 Formal view of token-passing queues ........................... 27 Markov model for two station example ................... ..... .. 47 sv cycle-time density for two station example ................. 52 Enlarged view of peak in SV density ........................... 53 SP density for two, five, and eight station systems ........... 97 SP density for three, six, and ten station systems ............ 98 SP density degradation for moderate loads ......... ......... ... 99 Variance estimate ........ . .............. . .................... 108 Transmit phases and Switch phases ........ ..... . .............. 147 Cycle-times and Passage times .... ..... ........ ............... 147 MQCS abstraction for NATP ....... ........ .................... . 158 MQAS abstraction for ATP ............ ................... ...... 158 Markov model for three station example ....... ................ 165 viii i P LIST OF SYMBOLS set of N stations set of N walks station indices customer interarrival distribution, mean l/k customer service distribution, means a. 5 server‘s walk distribution, mean a server's switching distribution, mean 7 Markov kernel of transition functions Markov probability transition matrix reordered form of P station j's scan/dep cycle view of P sub-matrix of P, i = 0,1 limiting Markov state probability, element of n limiting semi-Markov state probability, element of O set of N-bit binary vectors probability constants random variable, representing state of Markov process at n transition tn transition time instant corresponding to n fixed states in 8 probability of corresponding transition probability of corresponding transition shift operators, for vector rotation ix 5j(k) ”k(Z) 7j(m.j) C(z) V(z) Ti(°") £1("') p('l°l°) FX(.) d(z) I, I kth entry of vector j kth entry of vector 2 (j+m-l) mod N cycle-time random variable random cycle-time generated by service vector 2 service time contributions generated by vector 2 to cycle-time during cycle cycle-time w.r.t i for corresponding transition time spent by server at station 1 probability that station 1 makes corresponding transition probability of specified number of arrivals distribution function of X decimal representation of binary number 2 transition matrices, from 60, 81 infinitesimal generator of Markov process nonsingular square matrix m-vector with only unit entries 2N-bit initial vector vector of initial probabilities, m elements state of chain I at time t phase of chain T at time t S(t) infinitesimal generator of process {S(t),r(t)} ZmN square block-partioned matrix 2mN square block-diagonal matrix matrix of service-times matrix describing reference station customer transitions x(t) !(t) "(5) H(t) limiting vector of s. vector of mean service-times vector of second moments of service-times traffic intensity matrix of transition functions for reference station customers Laplace-Stieltjes transform of A(t) probability of k arrivals in time x probability of k arrivals in vacation period plus exponential time queue length distributions at scan instants and arbitrary time, respectively sequence of increasing matrices, converging to G stochastic matrix, solution to nonlinear matrix equation invariant vector of G probability generating function for x probability generating function for y Laplace Stieltjes transform for delay distribution distribution of delay time mean queue length matrix having all rows as 5 throughput random variable conditional transition time distribution function sojourn time in state i cycle-time density cycle-time distribution geometric transform of queue length density xi fi/j 1.1 pm P1! 91 (i) {Xn } pk(1) Laplace-Stieltjes transform of f probability that reference station is empty token's (mixture) holding time at station 1 sum of all token (mixture) holding times at stations sum of all token passing (walk) times Pjo”o qjul symmetric form of a. 30 symmetric form of ajl inversion coefficients, chapter v sequence of random cycle-times time for the it” cycle probability queue j nonempty during cycle 1 holding time distribution of token in state j, during cycle 1 conditional density, cycles 1 and j joint density, cycles 1 and j N-vector, with entries pj(M) probability constants (p1,.....,pN) (git-000°IqN) quasi-service time random variable moving average of level i iterations lag k correlations for level i iterations xii correlation between cycles 1 and j geometric transform for queue length distribution at station j queue length distribution at station j mean queueing time token-intervisit time mean cycle-time mean cycle-time conditioned on station j's service critical arrival rate for station j customers variable vector of arrival rates critical vector of arrival rates general index of stability index for stable system cycle-time conditioned on station j's service maximum of conditional cycle-times minimum of conditional cycle-times ratio of it“ moments of conditional cycle-times a w., for weights a i l 1 random times between transmit events, switch events, respectively distribution functions for J, K, respectively rarefied point process i-fold convolution of F cycle-times for first and second cycles of ATP process set of recently determined active stations scheduled walk-time in ATP expected value of Y1 xiii set of scheduled walk-times union of sets 5 and w union of sets 5, M, and 5', chapter VIII distribution of (Y1. + Xi) trip-time random variable distribution of trip-time probability queue j is empty during first cycle probability queue j has exactly one customer queued during first cycle (1 - PO - plj). chapter VIII j dirac delta function xiv CRAPTBR I INTRODUCTION In a local area network, channel usage is regulated by a protocol operating at the data-link layer, one of the seven layers of the ISO reference model [Zimm80]. A channel access protocol is an algorithm specifying how a distributed set of stations must share a common communication medium. Broadly speaking, these protocols are of two types: contention-based and conflict-free. Examples of the first type are the ALOHA [Abra70], CSMA [Toba74, KlTo'IS], and CSMA/CD [ToHuBO]. Among these, the CSMA/CD is the most commonly used medium access control method for a local area network using a contention bus topology. The well known Ethernet local network [MeBo76, MeBTC77] is a CSMA/CD protocol that was developed and patented by Xerox. Performance models for the CSMA/CD protocols can be found in [Toflu80, LamsBO]. The contention-free protocols based on token-passing methods or various reservation methods try to avoid the contention drawback. An excellent survey of these, including descriptions of several access, initialization, and synchronization methods, can be found in Penney and Baghdadi [Pe8a79]. 1.1 Simple Problem Statement The operation of a token-passing protocol can be described independently of the local network topology in an abstract fashion. Consider a system of N independent queueing stations that are separated from one another by unequal distances. Customers arrive in a random fashion and queue at any one of the N stations for service. Arrivals between queues, as well as within queues are independent. In general, any two customers queued at a given station will possess the same arrival and service characteristics. This is not necessarily true of two customers queued at two different stations. We will always assume that there is no restriction on the length of a queue. A single server is required to visit the N queueing stations in a certain sequence, serving customers at each station. Within each station, customers are always served in a first-in first-out mode. Upon completing a station's service, the server takes a finite time to walk from one station to the next station in the sequence. We assume that the system is perfectly reliable at all times and that the server is in perpetual motion, either serving a customer at a queue, bypassing an empty queue, or walking between queues. Sometimes it is necessary to account for the time it takes the server to detect an empty queue and consequently bypass that queue. This time, called the station's switching time, does not include the time it takes the server to walk to the next queue. The system is said to operate under a simple serv1ce scheme if the sequence of queueing stations visited by the server is strictly cyclic, i.e. l, 2, ..., N, 1. Simple service schemes may be either nonexhaustive or exhaustive. The simple nonexhaustive scheme called a fair serv1ce discipline is one in which service can be provided to at most one customer per station queue on each server visit to that 1 5 "I/_\ \\ travel direction ( ( 3 (— walk token 2 4“ {’/ I'\ wa1t1ng packet ’ 3 Fig.1 Conceptual view of Simple service schemes station. Thus, a system may be completely described by specifying N, the service scheme, the arrival rates and service rates of customers at each queue, and the mean time it takes the server to walk from one queue to the next in the cyclic sequence. Given such information, it is instructive to obtain answers to both qualitative and quantitative questions regarding the behaviour of such a system under general conditions. The conceptual queueing model can be seen in Fig. 1. Given a system of N independent queues with a single server obeying the fair service discipline, and also given probability distributions describing customer interarrival and service times at the various queues and the random walk times between queues, the problem is to find methods of analysis that will enable us to obtain measures of queue lengths, response times, server utilization, effectiveness of the service discipline, improvements in service patterns, conditions under which queues remain stable etc. A formal definition of the problem is deferred to the material in chapter II. 1.2 Token-Passing Protocols The token-passing (contention-free) protocols on ring and bus networks are two of the three access mechanisms presently being standardized by the IEEE Standards Committee [IEEEB4a, IEBE84b]. In principle, the token—passing protocols, like the Mewhall networks [PaNe69], use a token to regulate channel access. The station that has received the token is allowed to access the channel. If the station is ready to transmit and has a packet stored in its buffer, it immediately puts the packet onto the channel. Upon completing its transmission, a station passes the token in an orderly fashion to the next station on the channel. If a station has no packet to send when it acquires the token, it simply passes the token along to the next station. In either event, a cyclic token-passing sequence of stations is defined. A token ring [IEEE84a, ECMA83a] is typically configured as a series of point-to—point cables between consecutive stations, with stations tapping onto the ring using active interfaces. The token is a unique signalling sequence of bits that circulates on the communication medium in one of two states. A station that wants to transmit listens to the network, and attempts to identify from each sequence of bits it receives the special bit pattern corresponding to the token. The last bit of the token's bit pattern may be either a 0 or a 1, corresponding to busy and free token states, respectively. Any station that detects the token in the free state may capture the token, change it to a busy token (by inverting the last bit), and append a number of informative bits that go to make up a variable length packet. These bits include appropriate control and address fields, the data field set up by the logical link control sublayer, the frame check sequence, and the frame-ending delimiter. The busy-token and packet combination is read and forwarded one bit at a time (since the topology is point-to-point) by consecutive stations on the ring, and only the destination station copies each bit of the packet as it passes. In an attempt to detect a free token, each station must pass a sequence of hits, including its most recently acquired bit, through a pattern matching circuit. Only in the instance of a free token will the last bit he inverted. In any event, this token-detection mechanism causes a l-bit delay within each station. When a station’s transmission is complete, the sending station performs certain tasks to ensure proper operation and then creates a new free token, which it passes on to the next station in the cyclic token—passing sequence. The sending station removes the packet from the ring when the cycle is complete. The token-passing bus is conceptually very similar to the token-passing ring [Buxw84]. A token bus [IEEEB4b, ECMABSb] is configured as a passive medium, generally a long unbranched trunk, with stations tapping onto it via stubs in a multidrop fashion. The bus topology does not impose a sequential ordering of stations, as in the case of the ring. Thus, the token is made to circulate on a logical ring instead of a physical one, with a sequence of station addresses defining the token's path. A bus operates in broadcast mode, in which a station's transmission can be heard by all stations on the bus. Token bus protocols take advantage of broadcast mechanisms in executing the difficult tasks of establishing and maintaining the logical ring. Each station on the ring is required to know its predecessor and successor. In steady-state, the protocol is seen to alternate between packet broadcasts to destination stations, and token-passing broadcasts. Within the framework of token-passing just described, there is room for flexibility in protocol design. For example, in the token ring protocol, two modes of token operation are possible. The description above specifies that a new token is generated by the transmitting station only after the busy—token header of the packet is removed from the ring. This is called the single token rule [Buxw81]. In a multiple token strategy, the transmitting station may issue a token before it receives the previous busy-token, thus allowing for more than one token on the ring at the same time [BCJKBZ]. This reduces the idle time on the ring that occurs in the single token method. For rings with small delay (i.e., the time taken for a single bit to make a complete cycle on the ring), the performance of both methods is approximately the same [AnSc82]. However, since efficiency of the single token mode is generally close to that of the multiple token mode and its complexity is far less, especially when considering fault tolerance, the single token mode is more popular. In token-passing protocols, a more important design issue is the maximum length of time that a station is allowed to retain control of the transmission medium, i.e., a station's channel-retention time. In the following section, the channel-retention time of a token-owning station is identified with a finite number of consecutive packet transmissions that this station is allowed to make before relinquishing the token. Hence, this time will depend on both the time to transmit a packet, and the number of consecutive packet transmissions permitted for that station. In general, the channel-retention times of the different stations may be allowed to vary. 1.3 Classification 0f Multiqueueing Systems In queueing terminology, token-passing systems behave like multiqueues with a single shared server. The token represents the server and the station buffers with packets represent queues of customers. The set of stations forms a logical ring of independent queues. The terms service scheme or service discipline are used to describe the sequence in which the server attempts to serve stations. Recall that this idea was already introduced in section 1.1, where stations were serviced in the order 1, 2, ... N, 1, ... etc.. Models of token-passing systems generally assume service schemes that belong to one of three categories. The first category consists of the early models that place no limit on any station's channel-retention time (simple exhaustive service). These models were given considerable attention in the literature. The second class consists of models dealing with systems exhibiting simple nonexhaustive service. One such scheme is the fair service discipline described in section 1.1. Another example is the gated service discipline, where the server only serves those customers that are found present in the queue when the server arrives at the queue. That is, new arrivals are required to wait for the next round of service. This service discipline has also attracted special attention in the literature, and probably so due to analytic difficulties that crop up with other nonexhaustive service patterns [Buxw84]. Ferguson and Aminetzah [PeAm85] suggest that the reason for the relatively large amount of research effort directed at performance modelling of exhaustive service systems is due to the inferiority of gated system waiting times in contrast to waiting times in exhaustive service systems. Yet another scheme is one in which the server is allowed to serve a different number of customers at each queue. Though this may lead to unfair service, distributing the shared server among queues with different demands in a manner that is sensitive to changes in station loads often improves server utilization. The third class of models are those involving complex serVice disciplines. With such disciplines, it is no longer necessary for service to be strictly cyclic, nor is it necessary for the sequence of stations visited by the server to be static. A complex adaptive nonexhaustive service discipline is introduced in chapter VIII. The server attempts to adjust the path of the service cycle in order to account for imbalances in station loads. Complex disciplines generally involve service schemes that are not fixed, but change according to a criterion, such as the minimization of station response times. These disciplines are usually hard to analyze and have not received much attention in the literature. Additionally, conditions under which one kind of server behaviour can be shown to perform better (i.e., attain nearer optimality of the criterion) than another kind of server behaviour are difficult to obtain. In order to further classify different service schemes, we define a station's channel-retention time in terms of an upper bound on the number of consecutive packet transmissions that the station is allowed at any one instance of token acquisition. This instant is defined to be the instant at which a station obtains and recognizes a free token. The bound is determined by the station's queue emptying discipline, or QED. The QED determines the maximum number of packets that can be transmitted by a station whenever the station acquires the token. The time taken by the token to make successive reappearances at a station is defined to be the cycle-time of the token with respect to the station. The token's arrival instant at a station during a cycle is called the scan instant 10 of the station for that cycle. The instant that the token leaves a station during a cycle is called the departure instant of the station for that cycle. Observe that the token's cycle-time can be defined either with respect to scan instants or departure instants, and both definitions are consistent. A QED associated with a scan instant is called an s-QED. With the discipline s-QED = n, the number of transmissions made by a station is min(n,x), where x is the number of waiting packets recorded by the token at the station's scan instant. A QED not associated with a scan instant is called an r-QED, where r is used to denote relaxation of the scan condition. With the discipline r-QED = n, at most n transmissions are allowed. In this discipline, packets arriving after the scan instant but while previous arrivals are being served may still be transmitted within the batch of n. When n is finite, both QED's require that transmissions from the stations be nonexhaustive. The scheme s-Qau c a is really a nonexhaustive transmission mode since x is always finite and packets arriving after this scan instant have to wait for the next cycle. With r-Qim = o, exhaustive transmissions are allowed. The above classification holds for the cases of both finite and infinite queues. If the queue capacity (buffer size) is finite, say some positive integer b, then the disciplines are specialized to s-Qal(b) and r-Qae(b). With s-Qim(b) - n, the number of allowable transmissions is min(b,n,x). Note that since x S b, this number will always be the minimum of x and n. If the flow control process of a network node is clever enough to make use of finite (data-link level) buffer space even while packets are being transmitted from this node, then the scheme r-QED(b) is equivalent to 11 r-QED - a. This is to say that a finite queue capacity does not preclude the possibility of new packet arrivals at a station while old packets are being transmitted, with arrivals and transmissions overlapping in a continuous stream. Given that the service discipline and QED of a multiqueueing system remain fixed while the system is in operation for a period of interest, and also assuming that each station utilizes the same QED, these systems can be further classified in terms of station parameters. In describing multiqueues we use random times to model arrival times, service times, and walk times. In general, station 1 can be described in terms of hi parameters, with ni not necessarily equal to nj, for i f j. In the present situation, n1 = n = 3. i If the customer arrival processes at all queues are identical, the system arrival process is called symmetric; otherwise, the arrival process is called asymmetric. This notion of symmetry applies also to the service distributions and walk distributions. The concept associates more readily to a model of a queueing system than the real process itself. Nevertheless, if a token-passing configuration possesses uniform traffic arrival characteristics we apply a symmetric arrival model, and otherwise, an asymmetric arrival model. Similarly, if all service requirements are identical, a symmetric service model is applied, and otherwise, an asymmetric service model. This holds also for the walk processes. A symmetric system is one in which each of the arrival, service, and walk distributions is the same for all stations on the network, thus requiring a model that is characterized by only three distributions. On the other hand, an asymmetric system is characterized 12 by 3N distributions. Partially symmetric systems are ones which lie somewhere in between the two extremes, with some stations characterized by common distributions while others differ. 1.4 Review Of Previous Work A considerable amount of work on performance comparisons via modelling of the various channel access schemes including the token-passing schemes has been done in the past [ArSt82, Buxwel, LiHGBZ, Stuc83]. Most of the literature on protocol performance modelling assumes some combination of the characteristics of symmetry, s-QPD 8 n, or r-QED c n, with either n = a, or 1 < n < a . The more realistic asymmetric configurations with QED = 1 appears to have been largely neglected. One possible reason for this is the inherent difficulty associated with processes not exhibiting independence, and the computational intractability of asymmetric multiqueue systems possessing queues with customer interference. One of the earliest formal versions of the multiqueueing problem was presented by Liebowitz [LiebGl]. The arrival distributions are assumed to be Poisson, walk times are finite, and service distributions are arbitrary. The system developed was symmetric in all distributions, and switching times were not considered. Liebowitz was interested in the stationary probability distribution of the the random number of customers found waiting (by the server) at any station at its scan instants. Utilizing the s—Qns - a discipline (gated service), an approximate solution was obtained. The result is an approximation 13 because of an assumption of independence, namely that "stochastic processes within a particular queue are considered independent of the processes within the other queues". Liebowitz [Lieb68] cited his problem as an important queueing problem for which no exact solution had been obtained. Eisenberg [Eise72] discovered that the different queue states at scan times could be modelled as a Markov process and consequently proposed the first general solution to the problem. Transform solutions were obtained for customer waiting times and server intervisit-times at each queue. Unfortunately, Eisenberg's transform solutions turned out to be difficult to work with. More recently, Ferguson and Aminetzah [PeAm85] developed an exact solution to this problem, obtaining the mean customer waiting times (for each station) on a general asymmetric system. A closely related model in which the server uses the visit sequence l,2,....,N,N-l,....2,l has been developed by Swartz [Swaral] with an application to disk service policy. Swartz obtains average queue contents and average station intervisit time. Another general model involving the scheme s-QED - l, for both symmetric and asymmetric arrivals has been examined by Kuehn [Kueh79] in an approximate fashion, improving on a result of Hashida and Ohara [HaOh72]. Kuehn uses an independence assumption that leads to an approximate solution for mean queue lengths and waiting times. The solution does well in the low and high traffic regions but weakens in between, especially with an increasing number of queues or increasing variance in service times. However, Kuehn's presentation was a first view of the problem as a multiqueue problem subject to different queue emptying disciplines. 14 Many models have been proposed in the literature for variations on the multiqueue problem. The chief difference between the Hashida-Ohara/Kuehn model and these is that the variations often involve a simplifying assumption of dependence between the customer arrival and service processes. The most common assumption is one which restricts the station buffers to hold at most one packet at a time (b = l), additionally requiring that a new packet may be generated only an independently random time after the present packet is transmitted. This reduces to a state dependent arrival process, or s-QED(1) - l (the machine interference problem). While this approach is a workable one, it follows that the generation of a new packet at a station depends on the availability of buffer space. In practice, a packet sent to a filled buffer signals the flow control process of the network layer to stop sending packets to the data-link layer. This packet is then lost to the data-link layer and must be regenerated. The time until a regenerated packet finds itself in the buffer is thus a random time that depends on the time some packet left the buffer via the transmission medium. If viewed in this fashion, the customer arrival times do not correspond to the points of a renewal process [Coxd62], since the interarrival times are not identically distributed and certainly not independent. The point to be noted is that the assumption described above will work under conditions of light load, but gradually tend to fail as the load is increased to the point where packet arrivals at the buffers are not independent. One of the earliest applicable models of the s-QED(l) - l discipline in the machine interference context is given by Mack, Murphy, 15 and Webb [MaMW57]. The model assumes a symmetric system, with constant walk and service times but zero switching times. The customer interarrival times (or machine running times) are exponentially distributed random variables. Expressions for the distribution of the number of failed machines per server cycle and server utilization were obtained. Mack also extends the results to the case of variable walk times [Mack57]. Using the same queueing configuration, Kaye [Kaye72] uses the Mack, Murphy, and Webb results to obtain an algorithm for the waiting time distribution of an arbitrary packet. An important point to be noted here is that Kaye was trying to model loop systems which typically allowed more than one packet to queue in a station's buffer. Thus, Kaye's approach was an approximation. However, Kaye conducted simulation experiments to argue that the number of packets lost in assuming that buffers could hold only one packet at a time was generally small. Bux [Buxwel] takes the same approximate approach in modelling the s-QED - l token-passing system and justifies using the approximation with Kaye's simulation result on symmetric systems. Another nonexhaustive service model, but in the setting of an M/H/l system with two queues was supplied by Eisenberg [Bise79]. The solutions given require detailed calculations for the restricted two station model. Other variations on models for nonexhaustive 'transmissions have been proposed by Konheim [Konh76], Hamacher and Shedler [HaShBl], Wu and Chen [WuCh75], and Heyman [Heym83]. Heyman develops an approximation (independently of Kuehn's model) for mean packet delay in the multiqueue problem using simple nonexhaustive service, constant walk and service times, and zero switching times, with 16 the intention of analyzing the performance of Fasnet [LiPlBZ]. In the case of exhaustive transmissions and symmetric arrivals, nearly all of the literature on protocol comparisons relies somewhat heavily on the results of Konheim and Meister [KoMe74]. These results are based on a discrete time approach using scan times and yield expressions for mean queue length and virtual waiting time for a stationary system. A review of the literature indicates that performance models for s-QED = 1 based token-passing protocols and ordered access protocols sometimes make questionable use [Buxw81, ChLLBZ, LiHGBZ] of the Konheim and Meister result. This result is meant for roll-call polling type systems or exhaustive service systems, where stations transmit until their buffers are emptied. Bux [Buxwel] argues that the exhaustive model and Kaye's model [Kaye72] (where arrivals and service are dependent) are equivalent since stations on large systems (more that 50 nodes) rarely see more than a single packet queued at any given time. The exhaustive model is then used to analyze the performance of token-passing ring and bus protocols. It must be noted that these two protocols are generally implemented with an s-QED - l, which differs considerably from the service schemes in [KoMe76] (r-an - a) and [Kaye72] (s-QED(1) - l, or state dependent arrivals). The above reasoning thus equates one model to a second model with the intention of analyzing a third. Though the three models resemble one another, they also have differences that can lead to strong arguments as to the justifiability of equating them. The load that a station places on the system, i.e., the ratio of the station's mean arrival rate to the mean rate of service it receives from the system, plays a part in making 17 one model appear to behave as well as another. The system load is defined to be the sum of the individual station loads. The key to the dilemma lies in the viability of the statement ”exhaustive service is equivalent to s-QED(l) = l”. The models are equivalent if and only if the statement (call it x) is true. Define a heavily loaded station to be one whose average buffer content exceeds one (e.g., 1.01). Let the number of such heavily loaded stations (on the average) be H, and let 7 and x be the mean queue lengths for the heavily loaded stations, and the whole system, respectively. Define L to be the load ratio L a (7*H)/(x*N). Viewing 8(L) as a Bernoulli random variable whose parameter L is a function of the parameters of the network, it would be appropriate to say that x has a higher probability of being true for smaller values of L. As L approaches 1, it is more and more likely that X(L) will be false due to packet loss. It is possible to envisage situations where N is large but only a small fraction of these stations is responsible for most of the network traffic. Thus a low average system load on a large network, and a high average system load on a small network are both situations that must be suspect. x is certainly not true (with high probability) for heavily biased and highly loaded asymmetric systems. An analysis of such asymmetric polling systems is provided by Swartz [Swar80] as a generalization of the Konheim and Meister result. In fact, Swartz's approach uses the same embedded Markov chain as Eisenberg [Eise72] and yields an exact expression for mean waiting time at each station. ' At this stage, it is worthwhile to point out that except for [LiebGl], [Kaye72], and [MaMWS7], the solutions reviewed above are 18 restricted to either mean waiting times, mean queue lengths, or both. It is uncommon to find results in the literature that present explicit forms for queueing and waiting time distributions, whether exact or approximate. 1.5 Su-ery Of Contributions The research effort involved in writing this dissertation was motivated by a need for performance models of token-passing systems. In particular, we are interested in asymmetric token-passing systems where a station is allowed to transmit at most one packet at each time that it acquires a free token and is ready to transmit (i.e., fair service systems). In section 1.1 we described how such N station token-passing systems can be viewed as multiqueues sharing a single server, where the service discipline used is s-QED - 1. We attempt to analyze a more general model, where the time taken by a free token to bypass each station that is not ready to transmit (e.g., with an empty queue) is not negligible. This time, called a station's switching time, is typically a small fraction of a station's service time. Thus, each station is characterized by four probability distributions describing its arrival, service and switching times, as well as the random time its takes the server to walk to the following station. For the most part, we focus our attention on purely asymmetric systems, thus requiring an analysis with 4N distributions. This work was initially undertaken as an exploratory project, with the objective of understanding token-passing system behaviour subject to 19 simple service schemes and various QEDs. When it was discovered that symmetric and asymmetric s-QED = l systems (a proposed standard token-passing QED, important for its fairness) presented an enigma to performance modellers, the focus of the problem shifted to an analysis of precisely this service scheme and QED. Consider a strictly asymmetric N-station token-passing system operating under this QED. Assuming that steady state operation of such a system will exist under certain conditions, at any random instant in time the system will be in one of 2" states. Each state can be thought of as a binary vector whose entries differentiate between empty and nonempty stations. Additionally, the server's position in the logical ring at this instant is important. Exponential complexity is one problem that shows itself immediately. This means that as N increases, simulations of such systems can be expected to be very expensive and time consuming. Additionally, the large number of states makes analysis more difficult. Another problem is one involving dependence. Since a queue can hold a number of customers at the same time, it becomes necessary to account for the effect that a certain queue length observed at a certain time may have on the succeeding server cycles. Still another problem is that of dependence between queues. A customer requiring a large service time at one queue will effect the following queues visited by the server, including the customer's own queue during the next cycle. The literature reviewed in the last section does provide a few applicable models, but these are either approximate in themselves (e.g., due to assumptions of independence), or models of other queueing systems ‘(borrowed-models) applied to token-passing queues. As pointed out in 20 section 1.4, the latter approach leads to an entirely different kind of approximation which we label as borrowed-model approximations. Frequently, assumptions of independence are known to fail. But the conditions under which models assuming independence fail to perform well can be established far more readily than conditions under which borrowed-model approximations fail. For example, a model assuming independence is almost sure to fail in situations where strong dependence is an intrinsic part of the system being modelled. To detect conditions under which independence fails will usually require an identification of parameters causing dependence. On the other hand, to detect conditions under which a borrowed-model approximation fails will require an examination of the effects of the various hypotheses under which the borrowed model was analyzed. Since an approximation is good only as far as the conditions of its reliability are known, approximate models assuming independence are generally safer to use than borroweddmodels. The approach taken in modelling the s-an - l token-passing protocol is to both make assumptions of independence, as well as to account for dependence by resorting to Markov formalism. In approximating, an independence assumption was chosen over the alternate approach of applying borrowed-models such as the machine interference model, or the exhaustive service model. The approximation arises due to an assumption that at steady state, the status (i.e., nonempty or empty) of every pair of queues in the system is independent. The entire research contribution can be divided into two parts. One part is the approximate method based on M/G/l queues, introduced for multiqueues by 21 Paul Kuehn [Kueh79]. This is called the service probability, or SP approach. The other part is an exact analysis, called the service vector, or sv approach. The latter view is of token-passing multiqueues in the framework of Markov queues with semi-Markovian service times. The latter problem was originally studied by Neuts [Neut66] and Cinlar [Cin167] in the context of single server queues. The service probability methods that we introduce chronologically precede the exact methods. A first step in solving the problem was obtaining the distribution of server cycle-time for symmetric and asymmetric systems. This was motivated by Kuehn's [Kueh79] reference to this as an open problem. Due to the independence assumption, the cycle-time distribution by itself is of limited use in solving for queueing distributions. The problem is not directly amenable to an M/G/l type analysis since the cycle-time random variable does not really correspond to the general service time random variable of an M/G/l queueing system. However, given the form of the cycle time distribution, it is possible to approximate the effects of correlation between consecutive cycles. Kuehn recognized that an i.i.d (independent and identically distributed) service time random variable model would underestimate measures of customer waiting-times. Consequently, Kuehn introduced two kinds of cycle-times with the intention of increasing cycle-time variance and thereby obtained better waiting time measures. For the most part, the approximate methods that we suggest are variations on Kuehn's method. An attempt is made to account for correlation effects between neighbouring cycles. We include criteria under which station queues are stable, indices of stability, the 22 existence of stationarity, applications of rarefactions, and a new definition of fairness. The same ideas are applied in determining the cycle-time distributions of the server in a complex nonexhaustive service discipline. In the latter analysis the idea of maximization of the entropy functional is used as a method of obtaining steady-state distributions. The service vector methods are a recent development and consequently, there is scope for improvement. For the first time, this problem has been placed in a queueing framework that is both appropriate (unlike M/G/l queues) as well as familiar to readers of the more advanced queueing literature. The key to this solution lies in a Markov renewal matrix and the corresponding embedded Markov matrix. Unfortunately, for an N station system, the required square matrix is of size 2". This matrix enables us to study transitions between cycles of various types and the effects of varying station parameters on the system. Again, the cycle-time distribution is obtained as a first step. In this case the cycle time random variable is station dependent, and the distribution obtained is functionally exact. Additionally, it is shown that the cycle-time distribution is unique. Otherwise stated, this is really an invariance result. In the interests of brevity we restrict our discussion only to an analysis, for the most part. We reserve much of the application for later work. Given the transition matrix, it becomes possible to embed our problem into single server queueing systems with semi-Markovian service and thereby solve for restricted mean waiting time and mean queue length for a given station. The chief assumptions made in the various sections of the analyses 23 may be summarized as follows. In the approximate methods the assumption is one of independence between different queues, as explained above. In obtaining cycle-time distributions under independence, exponential random variables are used. Actually, the exponential restriction is required only for customer interarrival times. Similarly, in the service vector methods, only the customer arrivals are required to be Poisson. All other distributions may be arbitrary. In all cases we conveniently assume existence of the first two moments of every distribution involved. Besides these, the only other assumptions are that the system is perfectly reliable, transmission or server behaviour is flawless, and queues whose steady-state distributions we seek satisfy a given stability criterion. The stability criterion as stated holds for GI/G/l queues. 1.6 Organization Of The Thesis The use of queueing theory in the study of communication models or related applications is so widespread that any survey of the literature for applicable models must almost surely be incomplete. The review presented in this chapter demonstrates a collection of useful problems in the realm of multiqueues that has not been given due attention. We focus our interest on a special member of this class and in the course of the dissertation, indicate the many difficulties that arise in the analysis. The token-passing protocol is formally described as a multiqueuing problem in a probabilistic context in chapter II. The parameters of the queueing system are introduced and interpreted in 24 terms of token-passing systems. We take the opportunity to briefly review the definition of a Markov renewal process in terms of required notation. The two approaches used in studying the multiqueueing problem form the two major portions of the dissertation. In chapter III, we introduce the exact SV methods for cycle-time distributions and obtain invariance and insensitivity results. In chapter IV, these results are put to use in determining useful queuing measures. Additionally, we define a random variable to represent the system's channel utilization. The results in chapter III are basically applications of Markov processes and numerical analysis, and the results of Chapter IV rely on PH-distributions [Neutel]. The results are merely stated in the text, and all proofs are given in the appendix. In chapter V we introduce the approximate SP approach, or the model based on an independence assumption. The cycle-time distribution is derived for asymmetric and symmetric systems. Interestingly enough, both the SV as well as the SP approach yield cycle-times whose distributions are (finite) mixtures. In chapter VI the approximate cycle-time time random variable is further analyzed for an application in the study of the queueing process at a fixed station. For the most part, this analysis focuses the effects of cycle-time dependency on the queueing process a station. In chapter VII some conditions (necessary and sufficient) are presented under which the token (on systems whose packet arrival rates are constant for the different stations) sees stable queues of packets. A new definition of fairness is given. This definition relies on 25 information that is in distributional form. With such information, we will be able to vary parameters to obtain fair protocols, or even compare two (or more) systems, to decide which is more fair. Additionally, we present an application of rarefactions to a point process obtained via the token's departure instants at a station. Under heavy or light traffic, the point process is approximately alternating renewal and yields the (approximate) distributions of token busy and idle periods with respect to a fixed station. Chapter VIII deals with a (non-existent) token-passing scheme based on a complex service discipline. The motivating idea is that under certain conditions, an adaptive token (made to adapt in a simple fashion to states of the network) will perform better than a non-adaptive one. Using an approximate approach, we obtain distributions for cycle-times associated with this system. In chapter Ix we summarize and conclude our study and also outline some interesting problems in the shape of future work. CHAPTER II A QUEUEING MODEL FOR TOKEN-PASSING SCHEMES In developing a stochastic model for token-passing on buses and rings we resort to the theory of Markov processes. In particular, we use a class of random processes called Markov renewal processes. This class is useful for modelling complex systems and has the advantage of including many of the standard processes that are popular for modelling. The theory of Markov renewal processes has been known since the pioneering work by Levy [Levy54] and Smith [SmitSS]. Its popularity is chiefly attributed to the two papers by Pyke [Pyke61a, PykeGlb] though the theory was already being applied in inventory models and queueing models even before this time [Pabe61, Finc59]. In the following two sections, we present a formal definition of the token-passing model and a brief review of Markov renewal processes. In addition, we relate the parameters of the model to the parameters of token-passing systems. 2.1 The Multiqueue And Cyclic Server Model The token-passing protocol can be viewed in terms of the multiqueue and cyclic server model [ReNiad]. The MQCS model is a system of N independent buffers, chained together to form a ring by sections of varying cable lengths, as depicted in Fig. 2. Packet arrivals at station j are generated by some process with interarrival distribution 26 X KNJ—‘v llllll N-I 27 €—_Z >< Z Y1 1 Y YN—l . 2 llllllllll V2 ll" Fig.2 Formal view of token-passing queues X ’ 1 ”N V mm 6— x1 28 given by Aj(t) = Pr(IjSt), where Ij is the interarrival time random variable at station j, jes = {l,2,....,N}. Let us label the walk between station (j-l) and station j as wj, jeS. In our notation (j-l) indicates the station just prior to station j, and (j+l) indicates the station immediately after j on the path of the token. The station index immediately after j is obtained by computing j mod N + 1. If the circulating token finds a waiting packet at the buffer of station j, a transmission of random length Xj ensues, with probability distribution function Bj(t) Pr(XjSt). If not, it SWitCheS from walk wj to walk wj+l' taking a random time Vj, with distribution function Sj(t) = Pr(VjSt). In any event, after leaving station j, the token spends a random time Yjfl in walk wjflew a {wl,w2,.....,wN}. Y). has distribution function given by Uj(t) = Pr(YjSt), jes. We use the term distribution to denote the cumulative probability distribution, while the term density is reserved for the probability density function. For analytic convenience, we assume that all distributions have finite first and second moments. Observe the following points regarding standard queueing notation. For a fixed index j, the queue at station 1 is a single server queue. The fact that the server is unable to give uninterrupted service to queue j does not change a j-customer's view of this queue as a single server queue. Thus, queue j is really a GI/G/l queue, where the customer interarrival distribution is given by Aj(t). Though customers at station j spend only a random time Xj in service, the GI/G/l approach requires the service time random variable to be the length of time that the server spends away from station j from the time the last customer's service 29 began. The time that the server spends away from queue j may be treated as a server vacation. Several traditional models usually take this vacation time to be a random variable which is independent of the general service time distribution. Clearly, the presence of dependency between queues makes this approach an approximation in our case. If we combine the vacation time with the random time that the server spends at. station j, we obtain a single random variable that may be viewed as station j's service-time random variable. This random time is the cycle-time of the server as seen from station j. It is convenient to introduce a random variable that describes the amount of time that elapses starting from the instant that the server finds station j empty to the instant that the server finds a customer queued at this station. This time is called a vacation period of the server, since a station j customer arriving in this period will find the server unavailable. Though queue j remains a single server queue in the cycle-time context, it can no longer be treated as a GI/G/l queue. This is because the consecutive customer service-times (i.e., cycle-times) will no longer be i.i.d. To be precise, the queue must be labelled as a GI/GD/l queue, where the ”GD” denotes a dependent service-time random variable. If this dependence can be placed in a semi-Markovian setting, we will have a GI/SM/l queue with vacationing server at station j. If we visualize the entire system of N queues as a single queue, the notation GI[Mo]/GD/l or GI[MD]/SM/l can be used for the appropriate situations. In order to avoid any confusion when referring to any particular view, we will always describe the queueing configuration. 30 The notation MQCS/s-QED a l is used to described the entire N-station system with respect to the queue emptying discipline that is of major interest to us. Due to conceptual similarities, a token ring and a token bus can both be analyzed with the same performance model. However, due to their structural differences, the choice of certain system parameters will differ. On a ring, the walk time between two consecutive stations is comprised of the signal propagation delay between the two stations and the token-delay inherent to the two stations in creating and receiving the token [Buxw84]. The first kind of delay is in the order of 5 u-sec per Km of cable, and the second kind of delay (station latency) is in the order of 1 bit tbme. In comparison, the walk time on a token bus is made up of three kinds of delays. The first kind is caused by the transmission of the token, the second due to the signal propagation delay between the stations, and the third due to the delay caused by the token-receiving station before it transmits either a token or a packet. Here, the first delay requires a time equivalent to the transmission time for l52 bits [Buxw84], the second is precisely the maximum end-to-end propagation delay of the cable, and the third is typically in the order of 1 bit. Thus, in terms of throughput and delay, a ring scheme performs better than a corresponding token-passing bus [Stuc83]. As token-passing service disciplines become more complex, it will be more convenient (or perhaps necessary) to view token related delays as being of two kinds. One kind will involve station delays, i.e., pattern matching circuit delays, delays between token receiving and reaction times, delays in scheduling near optimal paths etc. The other 31 class of delays will be due to signal propagation, token-transmission time, or even delays caused by an unreliable server (such as a lost token). With a view towards this type of generality, it was decided to incorporate the notion of switching times in the MQCS model. These random times are intended to serve as station related delays. The second class of delays are represented by the random walk times between stations. Performing the analysis is a first step toward acquiring tools for understanding system behaviour as a function of system parameters. In an average sense, only two basic characteristics of a local network, i.e., propagation delay and data rate, set an upper bound on performance, independent of the channel access protocol [Sta184]. This is especially true if performance is defined in terms of system averages. In our model, since we are interested in a more detailed view of individual stations' characteristics, we choose to model systems with variable propagation delay between pairs of stations, as well as variable switching times. Introducing such randomness is one way to obtain somewhat more realistic and detailed measurements about queueing processes, such as distributions of packet delay, minimum and maximum packet queue-sizes, etc. Such information is useful for large systems with asymmetric traffic characteristics and constraints on packet-queueing time or buffer sizes. Once again, we will only be interested in the steady-state behaviour of token-passing systems with a simple service scheme, s-Qlfl = l and FIFO within queues, flawless message transfer, and a perfectly reliable physical configuration. 32 2.2 Markov Renewal Processes In this section we present a brief review of Markov renewal processes and then interpret our problem in terms of notation that we develop as we proceed. In order to properly define a Markov renewal process we need a sequence of pairs of random variables from our system. Let Zn be a random variable taking values in a finite set 5* for n in the set of non-negative integers 1+. Let Tn be another random variable such that for each Zn€S*, Tn takes values in the non-negative real numbers 6+. The complete probability space (O,F,Pr) is defined with n : 0 ----- > R+ * 2:0 ----- >5. Tn such that O = To(u) S Tl(w) S .... S Tn(u) S ...., for 069. The sequence of pairs {(Zn,Tn)} is called a Markov renewal process if Pr( Zn+l = j I T - Tn S tl zopeeeeep Zn I ToleeeeeITn) n+1 Z ). (1) We take To = 0 for the rest of the discussion and suppose that fl Pr( 20 = k ) is given, for some res . The sequence {T —Tn} forms a n+1 sequence of dependent random varables, because (T ) depends on n+l'Tn zn+l and Zn for every n€I+. We will assume that {Tn’ n2 0} is persistent, i.e. Pr( Tn” - Tn < .. ) = l, for all nef. Additionally, to exclude the possibility of the process passing through infinitely 33 many states in zero time, we assume that Pr( Tn+ — Th 5‘ O ) = l for all 1 neI+. It can be shown [Pykefila] that given {Zn}, the {T -Tn} are n+l mutually conditionally independent and satisfy the properties, (Pl) the process {Zn , neI+} forms a Markov chain satisfying Pr( zn= j | 20,...,zn_l ) = Pr( 2n = j | zn_ = i ) 1 (P2) {Tn I Zn = z} forms a renewal process for every fixed zes . Let Q be a square matrix with entry Qij(t) S 1 being a * nondecreasing right continuous point function for i, j€S . Q is called a t * semi-Markov kernel over S if, for each 395 , the following properties are satisfied. Qij(t) = O for t s O, and (2) z . Qi.(+o) = 1 for 195*. jes 3 Observe that the Qij's define the joint conditional probability Qij(t)=PF(Zn+1=j , Tn+1'Tns t | zn=i) (3) Equation (3) says given that the present state is i, Qij (t) describes the probability of making a transition to state j after spending at most time t in state i. The kernel Q serves (for a Markov renewal process) a purpose analagous to the function of the transition matrix P in a Markov Process. Thus Q is really a matrix of transition functions for the process. In simulating the process, the states of the Markov chain must 34 first be genetrated with the aid of P. Given that a transition has been made from state i to state j, Qij(t) defines the distribution of the random time that elapses before the next jump is triggered. The probability transition kernel of the embedded Markov chain is defined as P = 9(9). In our application, we are mainly interested in the limiting probability distribution for the semi-Markov process {Z(t)}. This describes the limiting probability ej of finding the server in any particular state -j,j€S. , provided the process is stationary. The service probability approach (see chapters V and VIII) used in the derivation of cycle-time distributions requires an invariance result for semi-Markov processes in order for the distribution {¢j,jeS*} to exist. Such a result is already known, first provided by Arjas, Nummelin, and Tweedie [ArNT78], and later McDonald [McDoBS], for different conditions. A similar result, much simpler and restricted to our special case, is obtained in Theorems 5.1 and 8.4. The essence of the result is an invariant probability measure for the sequence of probability transition (k) kernels P . In our service probability and service vector applications, a t particle makes a sequence of transitions in a finite space S according (n) to a sequence of probability transition kernels {P ;n=l,..o}. If the particle is in state 1 after (k—l) transitions, it goes to state j with (k) on the kth transition. If the distribution of the a probability pij random time spent by the particle between transitions depends, in general, on the transition number, the current state, and the next 'state, then the process can be seen to behave as a semi-Markov process 35 with a varying probability transition kernel. If the kernel Q of the renewal process is known, for each probability matrix P, and if an invariant probability measure A can be shown to exist for P, then the classical limit theorems for semi-Markov and semi-regenerative processes are shown to be robust enough to accomodate our case [McDoBS]. Let "x be the mean time spent by the process in state x, xes*. McDonald showed that under certain mixing conditions, . A(z)uz llm P{Z(t)=z} = ——-———— (4) tea 2 . A(x)ux X95 CHAPTER III CYCLE-TIME DISTRIBUTIORS VIA SERVICE VECTORS In the following analysis, a method for deriving the server's cycle-time distribution for a general, asymmetric MQCS/s-QED = 1 system is presented. The assumption that arrivals are Poisson is not crucial to the cycle-time analysis, and all input distributions may be general. We only require that a certain chain of events satisfy the Markov property, and this follows by construction. The cycle-time distribution is defined with respect to a given station which we call a reference station. Without loss of generality we take station j to be the reference station. There are two ways in which we can measure the cycle-time of the server at the reference station. If an observer is positioned at the departure point of station j (i.e., the point at which the server exits from this station), and the observer is required to report to us the random times between server reappearances at this point, then we obtain cycle-times of departure type, or dep-cycles. If the observer is positioned at the reference station's scan point (i.e., the point at which the server enters this station, to check for possible customers), then we obtain cycle-times of scan type, or scan-cycles. The length of a dep-cycle is the random time between two successive appearances of the server at the departure point of the reference station. Correspondingly, a scan-cycle length is defined as the random time 36 37 between two successive appearances of the server at the reference station's scan point. In the analysis that follows, we derive the distributions of the cycle-times of scan type. This is based on simple probabilistic arguments and Markov renewal theory. In addition, we obtain a result of some interest. It is shown that the cycle-times of dep type measured at station j possess the same distribution as the cycle-times of scan type measured at station (3') modN + 1. Also, it is shown that the cycle-times of scan type (or dep type) have a unique distributional form, independent of the reference station j. Putting these two results together, we obtain the interesting observation that all N dep-cycles and all N scan-cycles have the same distributional form, i.e., the system's cycle-time distribution is unique, and independent of the point at which the measurement is made. Section 3.1 introduces an external view of the system, in which an observer positioned at the reference station's scan point behaves as a particle in a Markov renewal process. In section 3.2, the structure of the Markov renewal process is exploited in order obtain the Markov matrix describing the observer's steady-state transitions. Once this is known, solving for the invariant vector inevitably leads to a steady-state form of the cycle-time distribution. This distribution is obtained in the form of a finite mixture and is functionally exact. Section 3.3 contains some results on the invariance of cycle-times and the insensitivity of the cycle-time distribution. The last result is somewhat surprising in that the exact cycle-time distribution of the server can be reduced to a function of only the mean conditional and 38 unconditional cycle-times. 3.1 The Markov Chain Of Vector Transfers Assume that the queueing process at station j is stationary and that the system is operating at steady-state. Let C be the random time that elapses between two consecutive vector transfers from the server to the observer. The limiting distribution of this random time is our focus of interest. The mechanics of the approach that we use to arrive at this can briefly be explained as follows. In Fig. 2 we see that the server makes service cycles in order of increasing station indices, moving over to station 1 after station N has been visited. On each cycle made with respect to station j, the server constructs a (binary) vector, called a serVice vector, that records individual station events. On completing the cycle, the server instantaneously (i.e., in zero time) transfers the vector over to the observer and begins another cycle. We make the assumption that this transfer may take place at any time prior to or precisely the scan instant at the reference station, but only after the server has left the preceding station's departure point. Additionally, we require that the transfer be made at the same physical point for every cycle. Let 6 be the set of all N-bit binary vectors. The observer can be viewed as a randomly moving particle, with each vector transfer corresponding to a transition by the particle between states of a Markov renewal process. In this case, the state space 5* will be the 2N states of the set 6. Let T1' T2,..., Tn,... be the instants in time at which the 39 observer acquires the service vector from the server. Assume that + + , To - 0, and (Tn+l - Tn) > O, for all n, n91 , Tnea . Define the serVice vector Z = as 1 if a station i customer is served in the current cycle 0 otherwise, for all 185. If j = l, we take (j-l) to denote station N. At time T“, (n) (n) (n), the observer receives a service vector Zn = associated with the nth transition of the process. The sequence of states 20, Zl,..., Zn,.... forms a Markov chain. When time spent by the observer in any state (i.e., a cycle-time) is taken into consideration, then since this random time is generally not exponentially distributed, {zn'Tn} will be a Markov renewal process. Due to the nature of the transitions, i.e., different service vectors define different service patterns, the time spent by the server in a state before a transition is made will be a function of the current state and the next state. 3.2 Asy-etric Systems With General Distributions In making a transition from a state Zn = z to a state zn+l = z , the random time that elapses is precisely defined by the vectors I I I z = and z = ’ If the limiting distribution of the related semi-Markov process can be determined, the cycle-time distribution for station j easily follows. In order to deal with the Markov renewal process, we need its kernel of transitions Q. 40 In order to obtain the kernel, our approach requires the probability transition matrix P corresponding to the Markov chain {Zn} embedded at the instants of vector transfer from server to observer. For each possible transition 2 e z', with z,z'ea, we require the steady-state probability p(z,z') of making the transition. In the situation where the buffer capacity at each station is exactly one, the stochastic process governing packet queue lengths can be placed in a simple framework. If the server can encounter at most one customer waiting for service at any queue, the queueing process (seen by the server) at any station takes on a regenerative form, with future events that are probabilistic replicas and independent of past events at this station. In essence, this becomes a slightly modified version of the M/G/l/K queueing problem whose solution and transition matrix for the embedded chain are well known. In our case, the assumption of unrestricted buffer capacities makes events associated with the server's current scan instant at a station depend on past events at the station. The lack of a regenerative or easily identified semi-regenerative structure for this process requires another approach in obtaining P. In order to obtain a particular transition probability, it is necessary to examine the time involved in making the transition from the starting state into the target state. Define a shift operator M that maps a vector two-tuple from the set 6x9 into the same set such that M{(x1,...xN).(xl ....xN )} = {(xz....xN,xl ).(x2 ...,XN .x1} (1) 41 The mapping views a vector two-tuple as a 2N-bit computer word and does an end-around left shift on the word in such a way that all bits move to the left by one position, while the leftmost bit falls off the left edge and is placed in the rightmost (vacated) bit position. Applying M recursively for a total of 2N times will yield the original two-tuple. If we define the starting state 2 and final state 2' of a particular transition as a two-tuple in 6x6, then with the starting vector two-tuple and (N-l) repeated applications of M, we can obtain N vector two-tuples corresponding to the given transition. Let the N components of a transition 2 e z, (for scan-cycles at station j) be given by the vector pairs ,.., , ,.. ' Observe that the vectors and are, respectively, the first and second N bits of the 2N bit computer word representing [2,2,]. We fix our attention on each vector of the form , ies, and let 61(k) represent the kth entry (i.e., either 0 or l) of this vector. Physically, the entries of indicate exactly which stations required service (and which stations did not) on station i's scan-cycle during the transition 2 e 2', 19s. Given such information, it is a simple matter to compute the length of this particular cycle as a sum of independent random variables. The probability of a transition from z to z, is obtained as a product of N probabilities, one from each station. For each m, l S m S N, the nth station on the path of the server after a vector transfer to the observer is denoted by 7(m,j) = (j+m-l) mod N. For each I transition 2 e 2 recorded by our observer at station j, and each m, 1‘s m S N, the time taken by the server to make a complete cycle with 42 respect to station 7(m.j) is given by , N T7(m'j)(z.z ) = kil { J“m j)(k) + Y7(k'j) } (2) where J7(m.j)(k) = 57(m,j)‘k’ X7(m.j) ' ‘1 ‘ 57(m,j)‘k” ”7(m.j) ‘3’ Since the random variables Xk, Vk and Yk are independent for all k, Eq.(2) essentially describes the random cycle-time associated with station 1(m,j) (for transition 2 4 2' at the observer's point) as a linear combination of independent random variables. The distributions of arbitrary linear combinations of independent random variables can be obtained by the usual techniques [Spri79]. In the case of exponential random variables, and also gamma random variables with a restricted class of parameter types, exact results and computational forms are well known [AlOb82, Math83]. Given arbitrary distributions for each Xk , Vk, and Yk’ the distributions of the random times described by Eq.(2). can, in principle, always be obtained. In practice, unless the distributions 8 , S k and Uk are extremely complicated, the distribution of k, T1(m j)(z,z ) can be determined either in exact form or a form suitable I o for computation. For the remainder of this chapter, let the distribution of the random variable 1 )(z,z') in Eq.(2) be denoted 701113. I I by F (.,z,z ), for m = l,2,...,N, transition 2 e z , and each 7(mrj) (fixed) reference station j. Observe that a strictly asymmetric system will possess 2" possible distributions of this type. I In order to make the vector transition 2 a z , the server must 43 encounter individual station transitions of the form 4 " — . 27(m,j) z 7(m,j) during station J 5 scan cycle For each m, I S S , . e . l m N denote the probability of transition 27(m’3) z V(m’J) by £7(m j)(z,z ). This is the probability that the server encounters 27(m j) customer(s) (i.e., either 0 customers or 1 customer) on the I first visit and z j) customer(s) on the second visit to station I 7(m 7(m,j). Let pk(n,z,z') denote the probability that n customers arrive at station k during arandom time Tk(z,z'), where k takes on integer values between (and including) 1(l,j) and 7(N,j). Note that this corresponds to the probability of n arrivals at station k during the time the server was away from this station, i.e., during a reference station's scan-cycle transition. If the arrival process at station k is Poisson, with positive, constant intensity 1k, res, this probability can be obtained as I - - n I pk(n,z,z ) - 3 exp( xkt)(kkt) dFk(t,z,z ). (4) n .' In the case of a general customer inter-arrival distribution for a given station, the probability defined in Eq.(e) can always be obtained by substituting the appropriate distribution in the integral to describe the probability of n customer arrivals. Each scan-cycle transition probability p(z,z') can be obtained as p(ZrZ ) = n £7(m,j) (2,2 ) (5) 44 where the approch taken in obtaining each component of the product in Eq.(S) is explained as follows. For transition 2 4 z', and k = 7(l,j),...,7(N,j), let events Ak and Bk denote the outcomes of the binary random variables ”x and z'k , respectively, for given j. We use the basic probabilistic idea that P( B /\ A ) = P( B | A ) P( A ) (6) to obtain each probability zk(z,z'). The event Ak tells us if a customer was served at station k on the server's last visit to this station, during transition 2 4 z, . If a customer was not served at this station (i.e., Ak = O), the cycle-time takes on a value that is smaller than c, cee*, with a probability that is strictly less than the corresponding probability for a cycle-time incorporating a customer service at this station. In other words, for a given vector transition, cycle-times obtained by excluding a service-time contribution from a particular station are stochastically less than cycle-times that include such a contribution. We are interested in computing the conditional probability p( Bk | AK ) for each station hes. Observe that knowing AR by itself is not sufficient to compute this probability. If Ak = 0, then Bk is strictly a function of the arrival process at station k and the random time rk(z,z'). This can be computed with the aid of Eq.(S). It A = l, k then the situation becomes complicated, since we have no way of knowing exactly how many customers are queued for service at station k. In fact, this distribution of customer queue length is one of the many distributions we seek. If we strictly seek the conditional probability 45 that B = 1 given that A = 1, then indeed we are in trouble, since we k k must require the queue length distribution for this. Alternately, if we seek the conditional probability that Bk = 0 given that A = 1, then we k can utilize the additional knowledge that this conditional probability makes sense only if the number of customers queued for service at station k when the server arrived there was precisely one. Additionally, no customers must have arrived in the random time Tk(z,z'). The latter probability is obtained from Eq.(S), but the probability qk that station k's queue length is exactly one (given that Ax = l or that it was found nonempty) still remains to be computed. An example is presented in the following section to demonstrate a method for computing each qk. Other methods are also described. For now, assume that we know how qk may be computed for each has. Then with the aid of Eq.(S), we can write down an expression for computing I £k(z,z ), for each res, as Pk (OIZIZ ) zk=0, Zk =0 [l - pk(0.z,z )] zk=0, zk =1 £k(zpz ) = (7) PK (01212 )qk 21:31, Zk =0 [l - pk(0.z.z )qk] zk=l, zk =1 At this stage, we have the necessary material to enable us to use results from Markov renewal theory, if we interested in renewal analysis. We are interested in the distribution of time that the token 46 spends in scan-cycles, as seen by the observer at the reference station. So, we first focus our attention on P. In particular, we are interested in the limiting distribution of the Markov chain whose transitions are governed by P. An application of standard techniques [Klei75] will yield the limiting distribution {wz,zee}, where ”z is the steady-state probability that the vector transferred to the observer by the server is 269. Note that this distribution ignores the time spent by the particle in the various states of the related semi-Markov process. The length of time spent by the observer in any state 2 = of 9 is given by the random variable C(z) = 2 [z + 1.95 7(i.j) Xi (1 ' 270,37) Vi + Y'] (8’ .1 with law FC )(.), easily obtained as the distribution of a linear (z combination of independent random variables. In order to obtain the limiting density of the semi-Markov process {z(t)}, we compute the probability of each state 2 as the product of 'z and E(C(z)) normalized by the sum of all such product probabilities. Let {‘2' zee} be the probability density obtained in this manner. Each random service vector 2 describes a service cycle (made with respect to the observer's position at the reference station) of length C(z), and occuring with steady-state probability ‘2 . The cycle-time random variable as seen by the observer will have a distribution given by F (t) = Z t F (t) (9) C 269 2 0(2) A = 0.0032 1 30:1) = 198 £01) = 1 V1 Mean Cycle-time = 174.4186 Probability station 1 is empty = 0.44186 Probability station 2 is empty 8 0.39093 (00) (01) (10) (11) = 0 Probability transition matrix (00) P 0.9801 0.0491 0.0478 0.0024 V 47 i2 = 0.003492 30:2) = 100 £012) = 2 2 (01) 0.0103 0.7012 0.0005 0.0342 (10) 0.0056 0.0097 0.5568 0.0373 (11) 0.0040 0.2400 0.3949 0.9261 é'\ "" 0' Ga 0. K 0 Limiting service vector is (0.3604,0.07l7,0.0497,0.5181) Fig.3 Markov model for two station example 48 The time-considered distribution of cycle-time may be obtained by replacing ”i by oi for each state i in Eq.(9). 3.3 Application Of The SV Method In this section we apply the methods just presented to demonstrate how the cycle-time distribution may be obtained. For convenience, we assume negligible switching times on a strictly asymmetric, two station system. Let the arrival rates for stations l and 2 be denoted by Al and 12, respectively. Let the mean service times and mean walk times be given by l/ak and l/ak, respectively, for k = 1,2. A graphic description of this scenario is given in Fig. 3, with the system observer positioned at a point on the path of the server from station 2 to 1. Thus, station 1 is taken to be our reference station. Assume that the system is operating at steady-state. There are four possible service vectors (corresponding to service cycles) on our two station system, and these are (00), (01), (lo) and (ll). The ith entry of each vector tells if station 1 did or did not require a customer's service on the cycle represented by the vector, for i = l,2. For example, if the observer obtains a vector 10 from the server, this is taken to mean that station 1 had one customer served, but station 2 had no customer served in the most recent cycle. For a given vector (ij), let xij be the probability that no customers arrive at station 1 during a service cycle represented by vector (ij). The corresponding probability for station 2 is denoted by Yij' We are interested in constructing a 4 x 4 transition matrix P 49 representing transition probabilities for the four different kinds of cycles seen by the observer. Assume that two vectors consecutively transferred to the observer are (00) and (01). This means that station l had no arrivals during its server cycle (00). One application of the shift operator in Eq.(l) will allow us to determine events at station 2. Thus, the transition is possible only if station 2 had one or more customer arrivals during its own server cycle (00). We are interested in computing the probabilities that the server encounters no customers at each station given that each station saw the cycles (00), (01), (10), and (11), respectively. Note that computing the complementary probabilities directly would be extremely difficult (if not impossible), since we have no information on queue lengths. Let these probabilities be denoted by Pk[ o | ij 1, for i,je{o,l}, and k = 1,2. Recalling that qk is the probability that exactly one customer is queued for service at station k, given that it is not empty, the conditional probabilities for k = 1,2 are easily determined as an=Pl[0|00] = 300 bll=P2[0|00] = YOO a21 = P1[ 0 I 01 1 ' xOi ”21 = P2[ 0 I 01 1 : yOl (10) a31 = P1[ 0 I 10 1 ’ x10 91 ”31 = P2[ 0 I 10 1 g le qz a41 = plt o | 11'] = x11 91 ”41 = P2[ 0 I ll 1 ‘ yll 92 Let the complementary probabilities for stations 1 and 2 be denoted by an 2 and DH 2, respectively, for n = l.2,3,4. It now remains I I to apply Eq.(S) in order to obtain P. Once this is done, the transition matrix corresponding to the embedded Markov chain of server cycles may 50 be written as oo 01 10 ll 00 all‘bll all‘blz a12"”21 a12*b22 01 a21*”31 a21"”32 a22"”41 a22*b42 (ll) 10 a31*”11 a31"”12 asz'bzl a32*”22 11 a41*”31 a41"”32 a42"”41 a42"”42 At this stage the matrix in P described by Eq.(ll) is easily . computed if the two conditional probabilities ql and q2 are known. We now describe a method that allows us to compute them explicitly. Since P describes a Markov chain for which each state is aperiodic, recurrent, and nonnull, the Markov chain of vector transitions must be ergodic. Treating the four limiting state probabilities w 0’ and x 00' ”01' ”1 ll ‘5 well as the conditional probabilities ql and q2 as our six unknowns, we proceed to determine the matrix in Eq.(ll). With Foster's criteria [Fe1166] it can be shown that the Markov chain's ergodicity implies that the four limiting state probabilities satisfy a system of four linearly independent equations (one of them being the conservation equation, in which all four probabilities add to one). These four equations still involve the unknowns ql and q2 . To determine these, we make use of the mean cycle-time (see Eq.(S) of chapter V) and mean conditional cycle-times (see Eq.(l) of chapter VII). With these additional equations, ql and q2 are easily computed. Thus, the matrix and the invariant vector of limiting probabilities are both determined. By multiplying the qi's by their respective conditions (i.e., by the probability that station 1 is not empty at its scan instants, obtained 51 from Eq.(4) of chapter V), the unconditional probability that station i has exactly one customer queued at its scan instants can also be determined. Consider the following numerical example. Let A = 0.0032 and 1 k2 = 0.003492 be the mean arrival rates for stations 1 and 2, respectively, assuming Poisson arrivals. Also, assume that the service times and walk times for both stations are exponentially distributed random variables. Let the mean service times for stations 1 and 2 be E(X1) = 1/61 = 198 and E(X2) = 1/52 = 100, respectively. Let the server's mean walking time from station l to station 2 and vice—versa be given by l/al = l and l/az = 2, respectively. It is now a simple matter to compute xi and yij for i,j€{0,l}. Once this is done, a system of 1 six independent equations involving "ij and qi , for i,j€{0,l}, can be set up to enable us to solve. In this particular example, we chose to obtain ql and q2 from the mean cycle-time equation in an iterative fashion. Note that an iteration is not really necessary since these probabilities may be determined explicitly. Using an iterative criterion that selected both 5 qi subject to a permissible difference of 10-1 between the iterated mean cycle-time and the exact mean cycle-time, we obtained ql 8 0.0870366 and 92 8 0.0805674. Consequently, the limiting state probabilities of the embedded Markov chain are obtained as r - 0.3604, 00 3 0.0717, 0.0497, and I = 0.5181. '10' 11 Let the random cycle-lengths corresponding to the four service '01 vectors be F00, F01, F10, and F11, respectively. Note that each Fij' for i,je{0,l}, is a generalized Erlangian distribution composed of at f0) 52 1 Asymmetric two stotnon system Expected value ( stotnon 1 , station 2 ) 0.08% - wolkmg time ( 1 ,2) - service time ( 198 , l00 ) _ — orrnvol rote ( 0.00.52 , 0.00.3492 ) 0.06- 0.04~ 0.02~ 0430 ‘7'TuwT— 1' ' ' l ’ 1 1 O 20 4O 60 80 Cycle—Time, t Fig.4a SV cycle-time density for two station example 53 Asymmetric two station system Expected value ( station 1 , station 2 ) 0.08fi - walking time ( 1 , 2 ) - service time ( 198 , 100 ) . — arrival rate ( 0.0032 . 0.003492 ) 0.06- A ‘l .4.) V H... 0.041 0.02-1 0.00 0 Cycle—Time, t Fig.4!) Enlarged View of peak in SV density 54 most four distributions of independent, exponentially distributed random variables. Thus, the (embedded) cycle-time distribution witnessed by the observer at the instants of vector transfers is given by .FC(C) = (c) (c) + n' (C) + n (c) (12) ”00 P00 + ”01 F01 10 P10 11 F11 The method for computing qi described above is one in which a system of equations must be solved. In general for an N station system possessing ergodicity, the transition matrix (and the conservation equation) will yield 2" equations for the 2" limiting state probabilities associated with the service vectors of the system. In order for the invariant vector to be determined, it is essential that the N probabilities ql, ...., qN first be determined. Thus, an N station system will have 2" + N unknowns. Having already accounted for the 2” equations obtained from the transition matrix, the N mean conditional cycle-times (Eq.(l). chapter VII) fully determine the system. Figure 4a depicts the analytic versus simulated cycle-time densities tor this moderately loaded system. Figure 4b is an enlarged view of the extremely peaked behaviour or the density for small cycle-times. An alternate method is one in which all the limiting state probabilities are expressed in terms of the unknowns qi, i = 1,...,N. An expression can now be set up involving the limiting state probabilites and the mean unconditional cycle-time. Equation (9) tells us what S(C) should be in teams or the limiting state probabilities, while on the other hand Eq.(S) of chapter V tells us what the exact 55 value of E(C) is. Denote the estimate of mean cycle-time obtained from EQ.(9) as Cq' The problem then reduces to choosing a point (ql,q2,..,qN) in the N—dimensional unit cube such that the (nonlinear) constraint |E(C) - qu is minimized. Still another method, involving entropy maximization, can also be used. This method is used in chapter VIII to solve a similar problem. 3.4 Invariance Of Cycle-Times We obtain the result that for a general asymmetric system, the distribution of the observer's scan cycle-time is independent of the index of the station from which the observer makes the measurement. At first glance, this result appears surprising since two different stations must possess different transition probabilities corresponding to the same vector transition. But, note that the cycle-time random variable can be defined as the time taken by the token to make one complete traversal of the (logical) ring. This random time must possess the same distribution regardless of the reference point where the measurement is made. This is an interesting property, in that the cycle-time distribution really is unique. Let A1, A2, ..., AN be the N binary valued random variables associated with service events at the respective stations during any steady-state cycle. Define p1 = P(A1 = l) to be the unconditional probability that a customer is queued at station 1, waiting for the server during an arbitrary steady-state cycle, and let P(Ai 8 O) to be the probability that station 1 is empty. Observe that these N random 56 variables are not independent. However, given the limiting probabilities for the 2N vectors, we can proceed to solve for the probabilities pi as follows. We make use of the identity N N P(A \/A \/...A ) = z P(A.) - 2 P(A./\A.) 1 2 N i=1 i' where (j-l) is meant to indicate a station 1 such that j = 1 mod N + 1. Define vk(z) to be the kth entry of such a service vector, and let 61 = {z€9|v1(z)=l} be the set of all service vectors whose corresponding cycles include service of a reference station customer. Define its complement in 6 to be 90 = 9\91. For each (binary) service vector 2 recorded by the observer, 269, let d(z) be its decimal representation. Observe that 0 S d(z) S ZN-l. Let To be the instant at which the server completes some cycle and hands over a service vector 2 to the observer. The observer instantaneously identifies the most recent cycle-time as either the service time of a customer of type d(z) if zeal, or a vacation-time from station j if zeeo. Since it is possible for one or more such vacation times to occur consecutively, a vaction period is the sum of consecutively occuring vacation-times. Consider a sequence of random pairs {Zk'Tk}' where Tk is the instant at which the observer hands over vector 2x to the observer. This corresponds to the completion of the kth cycle defined with respect to scan-cycles at station j. Without loss of generality we take T = 0, O 63 and Zk to be defined only for k 2 1. We define a busy period of the server to be the random time b defined by b = Te-l ' Tn-l (la) where (l) e > n, for e.nei+, (2) zeeeo, zneel, zn_leeo, and (3) zmee n S m < e. 1! A vacation period of the server is the random time V defined by (1b) where (l) n > e, for e,n€I+, (3) ZmGGO, zneel, ze_leel, and eSm O, the intervals of time between events is conditionally independent, given the path function of the Markov chain M. Under this assumption {S(t), n(t)} is a continuous-time Markov process. Given the generator of the process {S(t), n(t)}, it is now possible to describe the distribution FV(.) as a PH-distribution. Let e. be a 2N-bit column vector with each entry equal to 1. Define an order m*2N square block-partitioned matrix A*with block-entry (i,k) as A*(i,k) = pik e'ak, where the vector product denotes the product of a column vector by a row vector. Define also an order m32N square . block-diagonal matrix T with diagonal block-entry i as T The i' infinitesimal generator of the Markov process {S(t), s(t)} is given by T. a T.(I - A*), where I is the order m*2N identity matrix. Thus, the token's vacation-period distribution is a PH-distribution, with the representation (v, T'). A similar procedure using the transition matrix a will yield the token's busy-period distribution as a PH-distribution. 71 4.3 The Countable State Markov Renewal Matrix Let D be a square matrix of order m with entry (i,k) as the service-time distribution of customer type i (or cycle-time distribution for vector of type i, i691), for each k, l S k S m. Thus each row of the matrix is the same. Given the current customer's service-time, the type of the next customer and service time of the current customer are both defined through D. Given the m customer types, with corresponding service vectors coming from 61, we require a probability transition matrix describing the probability transitions between the various customer types. Consider the matrix P1 defined in section 4.2. Define the row sum of the 1th row of this matrix to be 51, for l s i s m. Define a new matrix a. as I s (1.x) = Pl(i,k)/si (10) for l S i,k S m. Let A be a square matrix of order m with entry (i,k) given by A(i,k) = D(i,k) !.(i,k). It can be shown that A is aperiodic and irreducible and satisfies the property that A(+°) = 8.. Denote the row sum distributions of A(.) by "i(')' i = 1,2, ..., m. Let n1 be the mean service time of customer type i, and let n = (nl,...,nm). Observe that n1 is the (finite) mean of the distribution Mi(.). If 5 = ($1,...,5m) is the limiting invariant vector . of B , the traffic intensity at station j is given by p = pj = XSn (ll) 72 where we must assume that p < l for well defined steady state distributions to exist (see [Neut77]). The triple defining queue lengths, customer types at departure times, and various customer service times or cycle-times, leads to the classical definition [Neut66] for an embedded Markov renewal sequence. The matrix of transition functions for this sequence is given by 80(x) Bl(x) 82(x) B3(x) ... Ao(x) Al(x) A2(x) A3(x) ... o A (x) A (x) A (x) ... 90:) = O 1 2 (12) o o Aolx) Al(x) ... 0 o 0 A0(x) ... x where Ak(x) = l P(k,t) dA(t), for k 2 o, (13) O and P(k,t) is the generating function of the Poisson arrival process at station j, describing the probability that k customers arrive during (O,t]. Using "*" to denote convolution, define Bk(x) = F§(x) * Ak(x), for k 2 0. (14) 4.4 Distribution of Packet Queue Length Define x 8 {x(i,k),izo,lSkSm} to be the invariant probability vector of the matrix 0(a). This vector defines the stationary joint probability for packet queue length and packet type. at the scan , instants of reference station j. The stationary infinite vector x 73 consists of m-vectors x0,x1,... etc. Similarly, define y = {y(i,k),iZO,lSkSm} to be the joint probability for packet queue length and packet type at an arbitrary instant in time for a stationary queue. This infinite vector consists of m-vectors yoiyl,... etc. The th k entries in x and yo describe the embedded and arbitrary-time O probabilities that station j has no packets queued, and that the next type of packet to enter service is associated with cycle vector type R. It remains to solve the equation x9 = x. The solution may be written as 1+1 x. = x B.(u) + Z l O l k=l A for 120 (15) “k i-k+l(“)' The unique solution to the nonlinear matrix equation comprised of substochastic matrices c = z A Gk (16) k=0 is given by (see [Neut77]) a matrix G which is both positive and stochastic. Let g be the invariant probability vector of G. Let S(t) be the probability generating function of the distribution xo,x in 1,000 terms of complex variable 2, for |z|SI. Denote the Laplace-Stieltjes transform of the Markov renewal matrix A defined in section 4.3 as A(s). By using the system in Eq.(lS), we obtain xiz) = u - p)(z-l)sA(A - kz)[21 - an - izn'l (17> If 1(2) is the probability generating function for the components 74 of y, for |z| and corresponding service-cycle C(z), define the random time V(z) to be the time that the channel is actually being used for station transmissions (and not for overhead). That is, V(z) = lel + 22x2 +....... + ZNXN (25) For each 269, define the ratio random variable U(z) = V(z)/C(z). A method of obtaining an approximate distribution for server utilization is given as follows. The randem utilization of the server corresponding to a service vector 2 is simply U(z), and the overall server utilization is the random variable U' given by q ll 2 nz U(z) (26) 296 The expression in Eq.(26) describes the channel utilization of the system at the time instants of vector transfer from server to observer. Replacing ”2 by ‘2 in Eq.(26), the corresponding result is obtained for arbitrary time instants. For a data rate of R Mbps, the channel throughput of a token-passing system is obtained as 3* = RU'. Observe that the random variable 0" is defined in the range [0.1). For each 2, the distribution functions of V(z) and 6(2) can be obtained by the methods indicated in section 3.2. Given these distributions, the next step is to obtain the distribution of the 78 quotient random variable U(z). This is where a problem arises, forcing us to make an assumption in order to obtain an approximate distribution. Note that U(z) is a ratio of dependent random variables. If we make an assumption of independence, we can proceed as follows. One method is to resort to the Mellin transform which, for a given function f(x), is defined as _ a 5-1 Mf(s) - I f(x) x dx (27) O Treating l/C(z) as a random variable, we apply transform techniques to obtain the Mellin transform of the product (V(z))(l/C(z)) (for distribution functions denoted by their respective random variables) as MU(s) = NV NC(2-s) (28) and the inverse transform, or the distribution of each U(z) as l c+ib _S FU(t) = — lim 1 t NU(s) ds (29) 21:1 b-n- c-ib The complex inversion integral shown above falls in one of four classes [Spri79] each of which determines the transformed function uniquely. In this case, if at least one pole exists, the integrand of the inversion integral can be expressed as a Laurent series, with a unique expansion. The inversion integral may then be evaluated by the method of residues. Since poles can be shown to exist in our case, the next step is to evaluate the integral over the Bromwich path 79 (c-iu,c+im). In any event, we assume that the distribution for U may be obtained by resorting to Bromwich contours and consequently the residue theorem [Spri79]. At this time, we are not interested in the an explicit form for the distribution, but only a method to show that it can be obtained. The approach will necessarily depend on the form of the Mellin transform convolution and any convenient algebraic manipulation suggested by the function in determing its series representation. An approximate expression for mean system throughput can be obtained by computing E(C(z)) and E(V(z)), for each vector 2, 269. The latter expectation may be obtained by computing the mean service-time associated with service vector 2, and the former expectation is obtained from E(V(z)) simply by adding mean switching times for stations not served during this cycle, as well as the sum of all the mean walk times. Thus, both E(C(2)) and E(V(2)) are known constants, for a given vector 2. The mean utilization of the taken on a cycle generating service vector 2 is then obtained as E(H(z)) = E(V(z))/E(C(z)). If we take utilization and throughput to mean the same, then approximate mean system throughput is simply given as 2 ”z E(U(2)), where the summation is over all vectors 2, 269. It is also possible to obtain an exact distribution for server utilization. We briefly explain how this can be done in terms of our two station example. Since there are four possible service vectors, there are four random cycle-times generated by these vectors. Define the random variable Y = (Y1 + Y2) to represent total (walking-time) overhead. Then, the four cycle-times are Y, U = (Y + X1), V = (Y + X2): 80 and W = (Y + X1 + X2). During three of the four random cycle-times, the server spends some portion of the cycle doing useful work, i.e., serving customers. The three ratio random variables corresponding to useful server utilization times can be defined as 2 3 = (N1 + X2)/(Y + x1 + X2) The server utilization during the zero vector generated cycle-time Y is nil. The vectors (Yl/U' YZ/U, R1). (Yl/V' Y2/V, R2), and (Yl/W, YZ/W. Xl/W, XZ/W) can each be shown to have a generalized Dirichlet distribution [Spri79]. In oder to use the form in Eq.(26) to define utilization, we must obtain the marginal distributions for the random variables R1' R2, and R3. In the case of R3 it will be necessary to compute the sum of two dependent random variables once the joint distribution is obtained. Since this is a fairly straightforward matter, the exact distribution of server utilization or system throughput follows. 4.8 Summary In this chapter, applications of the SV method in obtaining performance measures of the MOCS/s-Qin s l queueing system are presented. An observer positioned at an arbitrary reference station pictures the queueing system at that station (in isolation) as an M/SM/l queue with a vacationing server. Unlike the usual server—vacation queueing models, the vacation-periods in this model are random sums of random variables that are conditionally independent but not i.i.d. For 81 an appropriate treatment of vacation times, the methods of Neuts [Neut81] can be applied. This involves an application of PH-distributions and some detailed, interesting results obtained by Neuts on the Perron-Frobenius eigenvalue of a Laplace-Stieltjes transform matrix. The latter matrix is obtained from a consideration of dependent cycle-times (chapter III). The main results of this chapter include generating functions for packet queue length densities and delay times, and first moments of these distributions. Using [Neut77], additional moments may also be obtained. The only necessary assumption is that of Poisson arrivals. Arbitrary distributions may be used for service, walk, and switching on an asymmetric system (as in chapter III). We take a novel approach in viewing the system's channel utilization as a random variable defined on [0,1). An expression is obtained for this random variable, and it is shown how its distribution may be computed. The use of such a random variable is clear. A distributional form for utilization will yield considerably more information on channel behaviour than the usual mean value approach. It is especially simple to compute the mean system throughput using this method. Additional results in this chapter are (exact) mean queue lengths and waiting times for each station, and distributions for token-busy and token-vacation periods with respect to a given station. In 4.6 the two station example presented in Chapter III is further used in order to demonstrate how the sv method may be applied. CRAPTER V CYCLE-TIME DISTRIBUTIONS VIA SERVICE PROBABILITIES In the following analysis, another method of obtaining cycle-time distributions is presented. This is based on a vector of probabilities (pl,p2,...,pN), where pi is the probability that at steady-state, the server encounters at least one customer queued at station 1 at its scan instants. The essence of the approach is to decompose C into a sum of independent random variables. The idea was originally used by Hashida and Ohara [HaOh72], and later by Kuehn [Rueh79]. Using negligible switching times, Hashida and Ohara expressed the Laplace-Stieltjes transform for Fb(.) as a product of walk time distribution and service time distribution transforms. This requires a major assumption, i.e., at steady state the probabilities of service events at stations 1 and j are independent, for ifj, i,jes. This assumption is difficult to justify, especially since dependence between the various stations' queueing patterns can be shown to exist for certain choices of parameters. Intuitively, the longer the period of time spent by the server at any one queue, the higher the probability that the server finds a customer at the next queue. We use the same approach as in [HaOh72] and [Kueh79] to define C, except that we have included 'the additional switching time random variables. We assume exponential distributions for service, switching, and walk distributions, in order to obtain an explicit form for the 82 83 distribution FC(.). In general, it is possible to work with any distributions, and this can be done for symmetric as well as asymmetric systems. Interestingly enough, dependence between queues does not affect the limiting distribution of a stationary random cycle-time when system load is either very high, or very law. But the effects of dependence can be observed for loads that are not extreme. From the results of chapter III we know that a sequence of random cycle-times can be shown to possess an mth order Markov dependence, where m varies with the parameters of the system. To determine m as a function of system parameters is not easy. We content ourselves with approximating m by studying sequences of cycle-times, with distributions that are obtained under the independence assumption. In section 5.1, the server's behaviour at the instants of transition between stations and walks is modelled as a Markov chain. In section 5.2, the transition matrix for this chain is acquired via the probabilities pi, i = 1,...,N. The distribution of cycle-time is obtained for asymmetric and symmetric systems in sections 5.3 and 5.4, respectively. A simple result on the existence of limiting distributions is presented in section 5.5, and the property of cycle-time dependence is discussed in section 5.6. 5.1 The Markov Chain Of Server Transitions Consider the behaviour of the process as the server moves from a walk to a station and from a station to a walk. Due to the nature of server transitions, the sequence of states visited clearly' forms a Markov chain. If each station, walk, and switching-action is considered 84 a state, the system will consist of 3N states in total. By the process of lumping [KeSn60], states of switching can be combined with corresponding stations to reduce the state space to 2N states. We are interested in a Markov renewal process {Zn,Tn}, where Zn is defined over the finite set S. = S U W. For each n61+, Tn is the (positive) random time spent by the process in the specific state of 5* defined by Z“. The kernel of the process is a 2N x 2N matrix 0 (identified with the distributions characterizing the sojourn times of the token in the Q various states of S ) defined as follows : piUi(t) i=wk 6 W, j=k 6 S Qij(t) = qui(t) i=wk 6 W, j=wk+l 6 W (l) piBi(t) + qisi(t) i= k 6 S, j=wk+l 6 W where pi + qi = l for all 165*. For the interpretation of Q, the ordering of states (aligned with rows and columns) is taken to be {w1,l,w2,2,....,wN,N}. The functions associated with the Markov renewal process (see section 2.2) can now be interpreted in terms of our model. The basic dynamic particle of our system is the token. Its behaviour in moving among the various states of 5., as given by Z", is governed by a monodesmic semi-Markov process which has a kernel 9. The matrix P is the matrix of transition probabilities of the underlying Markov chain, which is aperiodic, recurrent, and nonnull. P describes the transition probabilities of the taken from state i to state j. On leaving state wi, p1 is the probability that the next state visited is i, and qi is 85 the probability that the next state visited is wi+ It is shown in 1' section 5.2 that under the independence assumption, the chain is homogeneous in time. It follows that pi is the probability that the token encounters at least one waiting packet at station 1, and qi is the probability that the token finds queue 1 empty and switches to the walk before station (1) mod N + 1. From each state j, j65, the token moves to state wj+1 with probability 1. The function Hij(t) is the conditional transition time distribution for the time to make a state * transition from i to j. For each 165 , the distribution of the sojourn time of the taken in state i can be defined by hi(t) z . Q..(t) j6S ‘3 Pr( Tn+l - Tn s t | 20,.....,zn ) Pr( Tn+l - TD 5 t 1 2n = i ). (2) We are interested in determining the limiting density of fc(.), if it exists. Since stationarity can be shown to hold (see section 5.6), the cycle-time C can be expressed as a finite sum of independent random variables with distributions Bi(t)’ Ui(t), and Si(t), i65. With the aid of the independence assumption, C reduces to a sum of independent random variables. If the other stations are not in line of sight, the observer at station j sees a single server queueing system. Each customer from this queue keeps the server occupied for a random time C. Thus, to the observer, this system resembles a GI/G/l queue [Klei75]. In reality, there are two important differences. In a GI/G/l queueing system, 86 customer service times are i.i.d. In our system, the observer clearly sees the dependence between consecutive server cycles, i.e., customer service times will be positively correlated. The second difference arises with respect to the waiting time of a customer who arrives when the queue is empty. In a GI/G/l queue, this customer finds the server either serving the previous customer, or idle. In the queue at station j, the server may either be serving the previous customer at station j, or be in some other state of S*, but never idle. Hence, while a customer at station j records a service time of Xj, the observer records a service time of C for that customer. The key to determining fc(.) lies in determining the probability pi that at least one customer is found waiting for service at the scan instant at station 1, for all 165. 5.2. Service Probabilities For Poisson Arrivals We assume that the arrival processes are all Poisson with positive and constant rates, and the queue length distribution at the reference station is stationary. Using standard M/G/l methods [Klei75], the geometric transform of the packet queue length distribution at this station is given by r (z-l) LD. .(l-z)] 6(2) = Oj 3 (3) 2 - L[Aj(l-z)] where A1 is the rate of the Poisson arrival process at the reference station j, L[s] is the Laplace-Stieltjes transform of the service time density expressed in terms of the complex variable 5, and r j is the O 87 probability that the token finds no packet queued at the reference station at its scan instants. The initial condition rOj is evaluated from the geometric transform property G(2=l) = 1. This yields 1 = rojL[O]/(l + AjL'[O]). Since the transform of the service time density evaluated at s = O is unity and its derivative is the mean value, it follows that . = - C 4 r03 1 AjE( ) ( ) If the expected length of a cycle in the stationary state and the Poisson arrival parameter Aj of station j are known, Eq.(4) can be applied to any station. The probability r01 that the token encounters no packet at a station 1 during any visit to the station can be computed. Thus, r01 defines the parameter qi specified in Eq.(l). In this way the token's holding time at station 1 is obtained as a mixture of the station's service and switching distributions, the mixing density being Bernoulli with parameter p1, 165. The expectation E(C) in Eq.(4) can be obtained by investigating the flow balance of the system in steady-state. When the system is in the steady state, the mean number or customers arriving at any station is equal to the mean number of customers served at that station. In fact, the mean number of customers served at station j during a cycle is identical to the probability that the server encounters at least one customer at queue j at this station's scan instants [Rueh79]. For each station j, this probability is simply AjE(C). From this we obtain s(c) -- jg‘{E(Yj) + 015(0))“le + (l-ljs(c))s(vj)} 88 and consequently the mean cycle time as 2 [ E(Yj) + E(Vj) J jes Em = ( () ()i' (5) l - 2 A.E X. + 2 A.E V. 195 1 1 ies 1 1 5.3 Asymmetric Systems With Exponential Distributions In this section, fc(.) is derived for an asymmetric model, i.e., one with all distributions having different parameters. The arrival processes are assumed to be Poisson(kj), and the Bj's, Sj's, and Uj's are assumed to be exponential, with means l/ujo, l/u and l/aj, jl’ respectively. Since a cycle is defined in terms of contributions from all stations, the random length of a cycle will remain the same regardless of the index of the station from which the observer measures it. An observer positioned at any station will record the random variable C decomposed in terms of its various sojourn times as R 8 c = z x.' + 2 Y. = x + Y (6) jes 3 j6S 3 where the starred terms denote the respective sums. The random variable yj has density aj exp(-ajt), and the random variable x ' has a density j that is a mixture of the densities of xi and Vj , given by pjujo exp(-ujot) + qjujl exp(-ujlt). C can be viewed as the sum of N hyperexponential random variables and a generalized Erlangian random variable. Let the Laplace-Stieltjes transforms of the densities of the 89 random variables x' and Y” be given by L[fxs] and L[st], respectively. For all j65 we have a. a. with ajO = pjujo , ajl = qjujl , and a. L[fY.] = ————l——— . (a) 3 (s + a .) J The transform of fc is obtained as L[fc] = L[fX*] . L[fY*] = n L[ij'] . L[ij] (9) jGS Let 9 be the set of all N digit binary numbers representing the non-negative integers in the range [0,2N-l]. An element k69 is an N-bit binary vector of the form [k(l),k(2),....,k(N)]. In terms of our new notation, we have a . L[fx*] = z n 1 1(1) (10) k69 ies ( s + ui k(1) ) 5 and L[fYt] = r -—-——1——- (ll) j6S (s + aj) _ “i where 5.— (II ———)a.. 3 ies (ai - aj) 1 ifj 90 L[fc] can now be obtained from Eqs.(9). (10) and (11). Note that L[fC] contains ZNN terms, where each term has the form D .‘(s) = n a1 k(i) “j 11 195 (s + Hi k(i))(s + aj) for j65 and k69. (12) Using partial fraction expansion, the resulting expression consists of terms (5 + u) and (s + a), that are convergent for Re(s) > -u and Re(s) > -a, respectively. Upon inverting the transform in Eq.(IZ), we obtain ( ) { exp(-ajt) D . t = n a. . 6. k3 . l k(l) 3 165 U (u - a.) mes m k(m) J exp(-u t) + z ” 1(“) }. <13) nesmgs (um k(m)‘un k(n))(aj-un kn”) mfn The cycle time density thus can be obtained as fc(c) = Z Z ij(C) . (l4) jES REG The computational complexity of the asymmetric density can be obtained as follows. Let the time taken for each addition be ts, and the time taken for each multiplication be t Consider the expression p. for ij(c) given in Eq.(l3). The second (summation) term in the sum requires a time of Nztp + (N-l)ts, and the first term in the sum 91 requires a time of Nt The sum itself requires a time of ts, and the p. product term involving the ai k(“'5 and the Uj's requires an effort of (N+l)tp. The time required for any D is N2[tp + 2N + l] + Nts. For a kj given value of c69+, the effort required to compute fc(c) is 2NN{N2[tp + 2N + l] + Nts} + 2N(N-l)ts. This requires an algorithm of exponential complexity and is inefficient for large N. In fact, due to the presence of the summation over the set 9 in Eq.(l4), any algorithm for fC(.) will always be an exponential algorithm. 5.4 Symmetric Systems With Exponential Distributions In the event that aj = a, ujO = “0' “jl j j6S, the computation can be shown to be tractable. In this case we have = “l' and A = A, for all do = puo and a1 = qul. The transforms for {X8 and fyt become N N a a L[fx*] = z < > [ ——°— 11"1 [ ——i 11 (15) j=0 j s + “O S + “l Llfyrl = [ s + a (16) The transform L[fC] can be obtained from Eqs.(15) and (16). A direct inversion by partial fraction expansion will involve repeated differentiation in the computation of the coefficients of the fractions. To be precise, each term in the inverse will require the computation of h h 2N coefficients, where the Nt coefficient involves the N1 derivative of an expression of the form (5 + s)-m.(s + x)-n, where m S N, and 92 n S N. This requires an overall effort of 0(2N) and is clearly an undesirable scheme. As an alternative, we represent the transform of the density of X‘ as d. e. L[fX*] = 2 —-———l——. + z ————2———. (l7) jes (s + no)3 jes (s + ul)1 where l N-j N N-j-l _ dj = -——————§:s z ( ) ( ) {-1)” (ao)" “ (al)“ (18) (u -u ) 3 n=1 n n-l O l l N-j N N-j-l _ ej = ____——_N:3 Z ( ) ( ) {-1)n (al)N n (ao)n (19) (u -u ) n=l n n-l l 0 for j = l 2 3 N-l with d = a N and e = a N I I '0......’ I N 0 N l . The transform of the density of C can then be expressed as d.aN ejaN L[fc] s z 3 + z (20) ms e+uphs+m1 imis+mfle+afl where the computation of the coefficients of the partial fraction expansion becomes considerably simpler. Each of the 2N terms in the above transform is expressed as a fraction x(s) 1 ye) e+ufle+afl 93 m-l l = z z. -————————_. + 9(5) jm 3 e+uW3 for some mes. The coefficient 1k is given by l dk (s + u)mx(s) Ek = — .— k! ds y(s) s=-a l dk l = — — [ N] k! ds (5 + a) s=-a where since m S N we get (~l)k F(N+k) ‘k N+k k! P(N) (a-u) for k = 031’2peeepm-le The COGSfiCientS Sky k = O,l,2,...,N-l, for the (s + a)'s are computed in an identical fashion. An arbitrary term from the first summation in Eq.(ZO), say d a" j . (21) e+uphs+m1 nfe) can be seen to invert to j-k-l j-l s t exp(-u t) Dj(t)= djaN { 2 k 0 r=o P(j-k) N-l 5: tN’1'1 exp(-et) + Z 1 (22) k=0 P(N-k) 94 and E). (t) can be obtained in the same manner, with coefficients :1" and (R', from the term in the second summation. Hence, we obtain the density for C in the symmetric case as fc(c) = .2 Dj(c) + .2 Ej(c) . (23) 365 36S The complexity of an algorithm using Eq.(23) can be determined by investigation of the function Dj. Consider the quotient immediately after the first summation in Dj. The partial fraction coefficient 1k requires an effort of tp(N+3k-l), the power of t requires tp(j-k-2), the gamma function requires tp(j-k-l). and obtaining the quotient with the final products requires 3t . For a fixed value of k, the quotient P term requires a time of tp(N+2j+k-l). Varying k from O to (j-l) to obtain the first summation requires an overall effort of tp[5j2/2 + j(N - 3/2)], for each j65. In like fashion, the second summation can be seen to require an overall effort of tp[7N2/2 - 3N/2], for each j65. All products involved in the computation of a single Dj require a total effort of tp[5j2 + j(N - 3/2) + 7N2/2 - N/2 + 1]. All sums involved in the same computation require a total effort of ts(N+j-l). The total time required to compute the first summation in Eq.(23) is tP[5(N+l)2N2/4 + N(N+1)(N-3/2)/2 + 7N3/2 - N2/2 + N] + ts[N(N-l)/2]. By symmetry, 31 can be shown to require the same effort. Thus, we find that Eq.(23) yields an algorithm of (fourth-order) polynomial complexity. 95 5.5 Stationary Cycle-Time Distributions Assume that the observer at station j witnesses the operation of the entire system starting from time t = 0. At first, the observer will notice that the probabilities pi, 165, follow a transient path, fluctuating with changes in the system. After a time equal to the relaxation time [Giff78] of the system, these probabilities will attain constant values. For the queueing process at any station 1 to be stable, it is necessary (but not sufficient) that the limiting value of pi be strictly less than one. The stability of the queueing processes is not a necessary condition for the stability of the cycle-time random variable C. That is, if the arrival rate at some station k is so large that AkE(C) is greater than one, we take the convention that pk = 1. This will ensure that in steady state, the server stops at station k with probability one during each cycle, in order to serve a customer. Viewed in this fashion, it is easy to see that C will always be stable, i.e., its expectation will be finite since it is the sum of independent random variables, each of which has finite expectation. Let us suppose that the observer positioned at the reference station begins to record the successive cycle times starting from time t = 0, where without loss of generality we will assume that the token arrives at the reference station at time t = O. The observer sees a sequence C1,C2,..,Cn,.. of transient cycle times, where C1 is the random time taken by the token to complete the it“ cycle, 16I+. If pj(i) is the probability that queue j is not empty at station j's scan instant during the 1th cycle, then clearly the length of cycle 96 Ci depends on the probabilities pj(l), jes. The distribution of Cl is obtained as _ (i), (i), , (i) , FCi - [F1 F2 ....... FN ] G where ”a" is used to denote the convolution operation. F.(l) is the holding time distribution of the taken in state j, j65, during the ith cycle. G is a generalized Erlangian distribution constructed from the walk distributions. We now state a theorem regarding the distribution of cycle times as seen by the observer in steady state. The proof can be found in the appendix. Theorem 5.1: If the distribution of queue length at each station j, :95 is stationary, then the random cycle time C posseses a stationary distribution given by . (i) (i) (i) F = 11111 [F a? . .......*F 126. (24) c l. l 2 N The effects of varying system parameters on the cycle-time distributions obtained via the independence assumption are easily demonstrated. It is intuitively true that at very high loads, cycle-times are asymptotically independent. In Fig. 5a is shown a comparison of simulation versus analytic results for the cycle-time densities for asymmetric sets of two, five, and eight station systems, respectively. In Fig. 5b, similar results are shown for asymmetric systems with three, six, and ten station systems, respectively. Observe, that the independence assumption performs well at high loads. F(t) 0.0251 0.020“ 0.015“ 0.010; —; 0.005- n-B 97 Poleeon arrivals asymmetrlo Senvlce - Exponential neymmetnlc Swltchlng - Exponential (hlgh truffle. p-D.99l 120 Cycle Tlme. t 240 Fig.5a SP density for two, five, and eight station systems F(t) .020“ .016‘1 .012“ .008'1 .omJ n-S 98 (high traffic. p-0.993 n-io . :.’.-..-‘ . Poieeon arrivals neymmetric Service - Exponential Heymmetric Switching - Exponential 60 120 l " I _ 180 240 500 Cycle Time. t Fig.5b SP density for three, six, and ten station systems f(t) f(t) ) 99 0138a .l 0.06— Enlarged view C104— 0132— 0‘0011‘1‘11117'l‘l‘l'l—fi1 0 2 4 6 8 10 12 14 16 18 20 Cycle—Time, t Asymmetric two station system ‘i Expei ted value ( station 1 . station 2 ) O 08“ — walking time ( 1 ,2) i — service time ( 198 . 100 ) g - arrival rate ( 0.0052 , 0.00.5492 ) 0.06“ density via independence. assumption / C104— exact density via service vectors / 0132- 0.00 1 l l l I 0 20 40 60 80 100 Cycle—Time, t Fig.5c SP density degradation for moderate loads 100 Similarly, it can be shown that independence also does well at low loads. Unfortunately, for system loads that are neither extremely high, nor extremely low, the independence assumption appears to perform rather poorly, as can be seen in Fig. 5c. 5.6 Serial Dependence Of Cycle-Times If we recall the distribution of cycle-time obtained in chapter III, we see that Eq.(3.9) defines a strictly stationary distribution. Since the system regenerates itself whenever all the queues become empty, the time points corresponding to empty-queues also correspond to regeneration epochs in a regenerative process. By hypothesis, the first two moments of all system distributions are finite, and consequently E(C) is finite. It is easy to prove that under this condition, the mean time between epochs of regeneration is finite. From Theorems lO-4 and 10-5 of [HeSoBZ] it is clear that the stationary version of this regenerative process is stationary, and the regenerative process itself is asymptotically stationary. Consequently, the cycle-time process must be asymptotically stationary. Thus, Bq.(3.9) defines the strictly stationary distribution that the cycle-time process converges to asymptotically. Equation (3.9) is strictly stationary simply because we chose as the initial distribution of the semi-Markov process what would have been the limiting distribution from an arbitrary initial state. The fact that we have identified a regenerative process is important in that a study of the sample paths of the process in any one interval of the regenerative process will help us completely understand 101 the system's behaviour. A method of pursuing this will be via the busy period distribution of chapter III. In this section, we are interested in studying the effects of the independence assumption, and consequently leave the idea just mentioned aside. If we work with the cycle-time distributions defined in sections 5.3 and 5.4, and assuming an arbitrary starting random variable C, it is difficult to prove (without using asymptotic stationarity) the stationarity of the cycle-time process. Indeed, starting with a regeneration epoch, it can be argued that the ensuing sequence of cycle-times (which in general will be dependent) is weakly stationary. It would be interesting to investigate the effects of the first cycle-time random variable (obtained under independence) on the following random variables to determine the behaviour of deteriorating dependence. An arbitrary cycle seen by the observer at the reference station is found to have a random length with density fc(.). If the arrival rates at all stations are sufficiently low, then successive cycle lengths are approximately independent. The queueing situation at each station will closely approximate a GI/G/l queue with uncorrelated service times. For example, when arrivals at each queue occur sparingly enough so that an average of at most one customer per queue is awaiting service at a scan instant, and the time between this customer's beginning of service and the next customer's arrival is an independently random time. Again, approximate independence holds also for sufficiently high arrival rates. In this case, a customer is always found waiting for service at each queue at its scan instants, ensuring that the cycle time random variable (which now will be the sum of N 102 random walk times and N service times) takes the same form for each cycle, and is independent of the previous cycle. But in general, even in steady state, successive cycle time lengths are not independent. Consequently, any study of the system utilizing fc(.) must take into account this dependence. Consider an infinite sequence of consecutive cycle lengths "C-n""C-I'CO'CI""Cn’"’ denoted by {Ch}, that are observed at the reference station when the system is in the steady state. If cycles C1 and Cj of the sequence are independent, the autocorrelation function for terms at lag m = Ij-il in the sequence will be zero. A nonzero autocorrelation for a given lag m implies a degree of dependence between cycles that are m positions apart. Given the parameters of the system, it is not a simple task to establish the value of m for which the autocorrelation goes to zero. Conversely, if this value of m is determined in an empirical fashion, it is not correct to assume that cycles of lag m are independent. Thus, we need to develop an analytic approach towards identifying independent cycles, making appropriate assumptions along the way, if necessary. The discrete parameter stochastic process {Ca} possesses the property that the joint distribution function for (C1,C1+1) is different from the joint distribution function for (C. i that the service, walk and switching distributions possess finite first +1&1”). By our assumption and second moments, {Cn} is a second order process. Further, if it can I 7 be shown that the process {Cn } defined by OH = Cn+k has the same mean and covariance functions as the {CH} process, for every fixed number k61+, then {CD} is second order stationary or weakly stationary. For 103 i,j,n€1+, let Men) and rij = Cov(Ci.Cj) be the mean and autocovariance function of the {CH} process, respectively. We resort to an equivalent but more functional definition of weak stationarity, i.e., E(Cn) is independent of n and r1 depends only on the difference between i and j, j to prove weak stationarity. In order to emphasize the importance of lags, and not the index of the process, we define rj = raj autocovariance function of the process with some cycle Co chosen as the arbitrarily from {Cn} to be the reference cycle. From the symmetry property of autocovariance functions, it can be shown [HoPS72] that r_j a rj, jeI+, provided that there are a large number of cycles that occur prior to C0 in {CH}. Since V(Cn) = Cov(Cn,Cn), the common variance of the random variables in {CD} is given by r0. Using Schwarz's inequality, it can be shown [HoPS72] that since r0 > 0, the correlation between an and Cn+ can be given independently of n by k rk/ro. Prom Theorem 5.1 it follows that E(Cn) = E(C) is independent of n, with E(C) being given by Eq.(S). To prove weak stationarity of {CH}, it is left to show that rij depends only on Ij-il and not the particular values of i and j. We now present an argument to demonstrate the dependence between consecutive cycles of the sequence beginning at C0 (measured with respect to the reference station). This approach treats the symmetric and asymmetric situations simultaneously, with the appropriate density used for {C throughout the rest of this discussion. Since the arrival process at station j is Poisson, kjco is the probability that an arrival event at queue j occurs during the token's Co cycle. This corresponds to the probability that at the start of the 104 C1 cycle, at least one customer is seen awaiting service at station j given that a cycle of length Co has just occurred and no further information is available about the queue status at its CO scan instant. Since all stations on the network see the same cycle time random variable, corresponding probabilities can be generated for each station by utilizing its arrival parameter. Thus, a larger value of C0 ensures a higher probability that customers will be awaiting service at each station during the C1 cycle than a probability generated by a smaller value of C0. Since the probability that at least one customer awaits service at a station is equal to the mean number of customers served at the station, we can conclude that if CO is large, then Cl will also have a tendency to be large rather than small. Large cycles will tend to follow large cycles with a high probability. By the same vein, small cycles will tend to follow small cycles with a high probability. The notion of 'high probability' simply describes a probability strictly greater than one-half. By exactly how much this probability exceeds one-half is a function of the parameters of the system. If E(C) is used as a means for discriminating between large and small cycles, then since consecutive cycles tend to group on the same side of the mean, the covariances between neighbouring terms in {CH} will have a strong tendency to be positive. Let fi correspond to the probability density function of the random variable Cie{cn}‘ By fi/j is meant the conditional density, and by fi,j is meant the joint density of the random variables C1 and Cj. The same notation is generalized to three or more random variables. We take the convention that f0 = fC. Define p. = (pl(m),...,pw(m)) to be 105 the vector of probabilities associated with the N—station configuration during cycle Ci“ Here, pj(m) = kj .gock/m is the probability that at least one customer awaits service a: station j during at the server's Cm scan instant, Cme{Cn}, and jes. By using the mean of the random sample 00,...., m-l' we obtain queue state probabilities that use some history of the cycle time process. The density fc(c) can be also be expressed as a function of probabilities, i.e., as fc[c,p], where p is the vector (p1,...,pN), with q = 1 - p. The conditional density of C1 given Co, may be obtained (1) simply by replacing the term pj by pj in fc, for all jes. That is - 1 fl/O - fc[c.p 1 . (25) and with the aid of Eq.(25), the joint density of (C0,Cl) is obtained f0,l = fl/O . f0 (26) The general form of the conditional density function for Cm given Co"'°’Cm-l can be obtained by extending the idea outlined above, i.e., _ m fm/oll'ooo’m-l - fc[C'p ] (27) and the joint density of (C0,...,Cm) as Oll'oeo'm = fm/Opl,...,m-l 0,1,...,m-1 If we compute the marginal distribution of Co by treating this cycle as the first cycle after the system is found empty (i.e., after a 106 regeneration epoch, when it will be easy to compute the probabilities Pi) we will have described a way to express the conditional density and joint density functions of random variables from {Cn}° By the manner in which the joint densities are defined, it is clear that the covariances between pairs of terms in {CH} depend only on their distances from each other. Thus, weak stationarity follows. Given any pair of random variables in the sequence CO'C1""'Cm""’ their joint and marginal distribution functions may be obtained by repeated integration. These distributions incorporate the local dependence properties of the second order process. The intention of the discussion was to demonstrate how the process may be viewed as weakly stationary, since strict stationarity is not easily proved without looking for the asymptotic distribution. Let the maximal dependent set of random variables in the sequence CO'C1""Cn"' be defined as {cklxzo,cov(co,ck)za}, where 5 is some specified tolerance level. Terms in the sequence whose dependence on Co is too small (smaller than 6) are excluded from the set. Let m be the largest positive integer satisfying Cov(Co,Cm) z 5. Then, m5 is called the memory of the sequence with respect to 5. Henceforth, we suppress the subscript and understand the memory to be defined in terms of 5. The number m will vary systematically with the parameters of the process. Generally, higher arrival rates generate sequences with longer memories, and lower arrival rates give rise to shorter memory sequences. Also, choice of 6 will affect the memory length considerably. The relationship between the memory of the process and the parameters of the process is a subject for further research, as also the covariance 107 structure of {Cn}° Observe that if 5 is made arbitrarily small, the size of the maximal set grows large. By passing to the limit, it is trivial that the marginal density for each Cm sufficiently far (in the limit) from C0 enjoys independence of Co. This is a consequence of the fact that the sample mean is a consistent estimate of the true mean of the cycle times. By assuming that terms in {CD} are independent, the variance of the cycle time process obtained from the density fc underestimates the ”true” (unknown) cycle time variance. The independence assumption made by Hashida and Ohara [Ha0h72] disregards the positive correlation between successive random variables in the sequence. Kuehn [Kueh79] uses a form of conditioning that accounts for two kinds of cycles. One kind involves a server cycle where a reference station customer is served, and the other kind involves a server cycle where the reference station queue is empty. The net effect is to increase the cycle time variance of the process. This form of conditioning uses information pertaining only to the current cycle and not previous cycles. To incorporate such effects, one needs to consider sequences of dependent cycles and find methods to describe such dependence. The joint density functions obtained above were developed with the intention of demonstrating one such method. Given the (n+1) dependent random variables CO'c1"""'Cm' the marginal density function for each random variable and joint density functions corresponding to every pair of random variables in the maximal dependent set are obtained. Prom Eq.(26) it can be seen that the procedure is computationally simple estimate of "service" tune vanonce V(C) 108 "true" variance '- .....-...."u memory. m " 1 l I 1 0 20 30 size of dependent set Fig.6 Variance Estimate 109 since the form of the joint densities is merely the product of the individual marginals with the appropriate probabilities substituted. The variance-covariance matrix is obtained with the aid of the joint and marginal densities. Let amz represent the maximum ”true” variance of the cycle time process. Then an estimate of variance may be obtained as o) N "NE V(Ci)/(m+l) + 2 Z Z Cov(Ci,C.)/m(m+l) (29) o i 1 so that it can no longer be interpreted as a probability. If the other queues are stable, then the system is only partially stable since queue j is unstable. In such cases it is necessary to set (1 - raj) to 1. This means that a customer is present with probability 1 at each scan instant of this unstable queue.' Since we know that f3 is a mixture density, we can determine takes the form of Bq.(5.l¢), with D unique Ekm such that f km replaced S by Ekm' Let Lj(z) be the geometric transform for the number of arrivals at reference station j (as seen by the observer) during a random time S. Let r”j be the distribution of queue length at station j, n€I+. In order to derive the distribution of queue length it is necessary to exploit the geometric transform of the queue length distribution at station j (see Bq.(5.3)). If we can represent part of this transform as a ratio of two power series, the result is a single power series. By evaluating the low order coefficients of the new series, the terms rnj may be recovered [AbSt64], for n€I+. We may write Lj(z) as (H) } Zn Lj(z) = z z z { s (7) has tee n=0 km 125 E (n) ° n where é (kjt) exp( hjt) Ekm dt (8) D! with Ekm defined earlier. Observe that Lj(z) is of the form Lj(z) = o z” where on describes the probability of n packet arrivals H OMB at station j during a random "service time" S. Using the above equation, we can write the geometric transform for the length of station j's packet queue as r .(2-1) 2 o z OJ ”:0 n G(z) = (9) I2 from which, after some algebraic manipulation we obtain 9 0“.) r0.[ 1 + Z (—£———£—l)zn ] J _ n-l “0 6(2) = (10) w - 1 O m 1 + ( 1 )z B (-£)zn 00 n=2 mo The expression for 6(2) shown above is clearly of the form a a (l + z aizi)/(1 + r bizi) which simply reduces to z dizi. Thus d1 can 1 l o be determined recursively as i a - z b d._. i = 1,2,3... 1 jgl j 1 3 d1 = (11) 126 With the aid of di it is an easy matter to compute the distribution of queue length upto any desired value of n , n€I+. For example, to obtain r1j we compute d1 = 1/00 - l, and then rlj = rojdl. In order to compute r2j we first compute _ _ _ 2 . = d2 - (1 do ol)/o0 , and then obtain rzj rojdz. The higher order probabilities are computed in a similar fashion. For a stable system, the distribution of queue length will be unimodal and will possess the property that rnj = O, n 2 k, for some fixed kel+. Thus, the compuation will necessarily involve only a finite number of terms. There are other methods available for determining the distribution of queue length using Lj(z). For example, if this transform is extremely complicated, then an approximation may be desirable. Often, Lj(z) can be viewed as a rational function of the form Q(z)/R(z), with these functions being polynomials without common factors. The algebra of partial fractions will yield [Fell68] a simpler (exact) decomposition for Lj(z). If R(z) has distinct roots, the decomposition is exact. Methods for determining the zeros [RuTa77, CoBo72, Henr64] via algorithmic techniques are known. When the roots can only be found appriximately due to limitations of solving polynomials for zeros [CoBo72, Henr64], such as when the degree of the polynomial is large, the transform of the queue length distribution may be approximated [Henr64, Fell68, Doug63, CrCG79]. Once a simpler form for the transform is obtained, it may be inverted by one of several methods [Jage78, JageB‘]. 127 6.6 Distribution Of Packet Delay Let F*(s) be the Laplace-Stieltjes transform for PS, where s is a complex argument. We formulate the delay characteristics of an arbitrary packet at station j as that of a customer in an M/G/l system, with service time distribution FS(.). We define the delay of a packet as the time it spends in its queue before its transmission begins. Let f;(.) be the residual service time density for a transmission from station j (i.e., a packet in service). The Laplace-Stieltjes transform of this density is given by 1 - F'(s) 9"(5) = (12) s 13(5) Using this, we can express the transform of the packet delay distribution as l - A (s) W'(S) = ’15 j l - kjE(S)F (s) Inverting this last transform to obtain the delay density function, we obtain wj(t) = }_: k H) (1 - 113(3))[xjusn ?(k)(t) (14) where €(k)(t) is the k-fold convolution of the residual service time density. For a stable queueing system at station j, [1.113(8)]k will approach zero as k increases. This will enable us to approximate Wj(t) 128 by a finite number of terms, with accuracy increasing as the number of terms increases. Since E(Sr) is seen to exist for r = 1,2...., an application of Takacs recurrence theorem [Taka62] will allow us to evaluate the moments of packet delay distribution. Let Lj be the random variable representing mean queueing time for packets queued at station j. Then, i. r r E(Ci+l)E(Lr-i) 5(L.’) = -————l—T- z ( ) r = l,2..... (15) 3 (1 — pj ) i=1 i ( i + l ) with S(LO) = 1, and pj' = kjE(S) as the mean contribution of station j to the token's cycle time. Let Mj represent the random time that station j must wait from the instant that it begins a transmission to the instant that it next gains access to the channel (assuming that it does require a free token on the next pass). By hypothesis, since at least (r+l) moments of the quasi-service time distribution, and at least r moments of the packet delay distribution exist, the moments of station j's response time can be obtained as I“ 1' ref) = z, ( )E(s’) r(rjk") r = 1,2..... (16) 6.7 Channel Utilisation The fraction of time that each station keeps the token occupied (detains the token during packet transmission) is the station's channel 129 utilization. The total utilization (summed over all stations) yields the channel utilization of the system. This quantity can also be interpreted as the throughput of the system. In order to obtain an expression for utilization, it is necessary to obtain the stationary distributions associated with the semi-Markov process. Let {Z(t)} be the continuous time semi-Markov process associated with {Zn,Tn}. The embedded chain {Zn} observed at the instants of state transitions behaves like a Markov chain. {Zn} is aperiodic, positive recurrent and irreducible and can be shown [HoPS72] to possess a stationary distribution fl = (wwl,w1,...,sz,nN). The probability of finding the token in state 1 after the process has been operating for an arbitrarily long time is xi, ies'. The process {Z(t)} can be shown to exhibit a unique limiting behaviour within the chain {Zn}° The equilibrium distribution of {Z(t)} is given by Q = (¢w1"1""'¢wN’¢N)’ where ej is the limiting interval transition probability of observing the token in state 195*. This probability is different from that obtained from the chain due to the consideration of the holding time distributions in the various states of Q S . With qk = fox and pk = (1 - qk) we obtain 'j E(Yj) { ( ) r(v )} r r(r ) jg" Z x p E X + q + s res x k k k k xew x x ej = (17) t {P (X.) + q E(V )} 1 JE : 1 :1 jes r {p E(X ) + 3(v )} + z r(r ) res,“ x x qfew x ”r x 130 Let uj be the mean channel utilization by station j alone. Then 113. can be given by . E Y. 'ew e3 ( J) J uj = (18) ¢j {(l-roj)E(Xj) + rOjE(Vj) 395 and the approximate mean system throughput is obtained as U = 2 u. (19) jes 3 6.8 The M/G(r+1)/l Approach Another interesting queueing model applicable to the MQCS/s-QBDcl problem can be obtained from analyzing systems in which service times of adjacent or near adjacent customers (in a single server queue) are correlated. If we can determine the stationary distributions for such a queue, then we essentially have a closed-form solution to the problem. Unfortunately, our solution must depend on the correlation of the service times. In all the analysis we have carried out from section 5.5 through the present, we have only been able to propose models for describing the correlation function for a given process. In the following discussion, we do not require the i.i.d service time assumption that is often made. Observe that while our closed—form solution skips the i.i.d assumption, the one remaining difference between the queueing system at station j and an M/G(r+l)/1 queueing system still remains to be addressed (see section 5.1). The letter r in .the queueing notation above is used in conjunction with G to denote the 131 distribution of a moving average random variable of order r. As in the past, the queue at station j is viewed as a single server queueing system. The service time of the nth customer is given by S = gO(C n ) + 91(C H'HC’l n+r ) + ..... + gr(Cn), n z o, r with Z inf gi z 0, i=1 where {cm} is a sequence of i.i.d random variables with density function given by Eq.(5.14) or Bq.(5.23). The constraint on the 91's is to ensure nonnegative service times. We are particularly interested in the situation where the 91's are positive constants. Thus, Sn becomes a linear combination of independent random variables, Sn = bocn+r + blcn+r-l +.....+ brCn , n z 0. An analysis of such queueing systems was pioneered by Loynes [Loyn62a, Loyn62b], and Pearce [Pear66, Fear67]. Pearce was interested in queues with moving average service times of order r (i.e., M/G(r+l)/l systems) where the moving averages guaranteed service times that were correlated. However, in choosing the particular values of b no I 10 guidelines are available. Since we are interested in modelling positive correlation, we require that the bi's be positive. Consider the (n+1) dependent random variables $0,...,Sm. Application of the PCA method described in section 6.4 will yield coefficients a i - O,..,m, such 1' 'that the corresponding linear combination of the Sn's possesses maximum 132 variability. In theory, given the a1, it is possible that each hi can be determined from a system of linear equations that involve bi's and 61's. Thus, each bi will be defined in terms of the 31's. In practice, since principle component analysis is difficult for sequences of random variables with incompletely specified distributions, this approach is difficult. Instead, an iterative method can be used to determine a set of positive constants bi that maximizes the variability of a set of 81's via principle component analysis. 6.9 Queue Length Distributions Via M/G(r+l)/1 Systems In this section, we focus on the packet-queue length distribution at station j assuming that this station's packet transmission lengths (as seen by the observer) can be represented by moving averages of order two. For convenience, we take the sum of the bi's to be unity. Using lower case letters to denote actual realizations of random variables, the (n+r) tuples (co,..,c n+r-l)’ (C0,..,C ) are compactly (n+r-1))' (C(n+r-1))' n+r-l represented as (c with the cycle time distribution fc(.) taken as the common distribution of the C 's. i Let Pk(c("*"l)), r z o, be the probability that (C(“*r‘l) is equal to (C(n+r-1)) and the server finds k customers queued at station j (the reference station) after serving customer n. This corresponds to the instant that the token returns to station j for the (n+l)th time. The generating function of this distribution is given by n+r-1) P(c( ;z) = r P (c(”+"l))zi. IzISl (20) 133 (r) and its integral transform P*(s ;z;n) is given by (n+r-l) P'(s(r);z;n) = E[P(U ;z)exp(-srC n+r-1 - '5r-1Cn+r-2 "" slcn]' with |z|51, Re 5120, lSiSr. For the limiting distribution, we obtain the form P(wl,...,wr;z) = lim E P(C0""'Cn-1'Cn"°"cn+r-1;z)’ where wl,...,w is a realization of u ,..,u r n and its integral n+r-l' transform * (r). _ (r), _ _ _ P (s ,z) - E P(w ,z)exp( srwr ... slwl), |z|Sl, Re 5120, where fc is used as the density of the i.i.d random variables W1. Define w = B[exp(-kj5C)], for Re 520. When r = l, forlzISl, Re 5 20, we I obtain zP*(sl;z)=-z(1 - z)w{(l - z)bo + sl/kj}P*o{(l - z)kjb1}[z - W(l - 2)]-1- After some algebraic manipulation of the integral transform of the limiting distribution, dividing by z and taking the limit of the resulting expression as z e O, we arrive at x . _ _ _ _ -1 P (51,2) - (l z)w{(1 z)b0 + sl/AJ}W(1 biz)[W(bO)] . (l - i). go drc(c))w(l - z)].’1. |z|s 1, Re 5120. Finally, the generating function of packet-queue length distribution can be found by letting 51 = O, or 134 mn=(l-mnu-zmgwl-mnwwpr% (1 — k. I c d? (c))[w(l - z) - z]'1, |z| s 1. 30 C In the case of r = 2, the limiting packet queue length distribution's generating function is obtained by similar methods to be P(z) = - z'l(l - z)w{(l — z)bo}[1 + w'mmwbon'l I -1 l -1 x [{1 + bow (1)}{w (1)} W(b0 + b1) - how (no + ”1’1 x [{1+bow (1)}{w(1)}'1w(bo+bl+(1-z)b2} - how (no + b1 + (1 - z)b2}] x [{z - w(l - z)}'lw{(l - z)(bo + bl)}W{bo + (l - z)(b1 + b2)} + w{b0 + (l - z)b1}]. |z|sl. 6.10 Summary This chapter uses the cycle-time distributions developed in chapter v to develop two kinds of queueing models. One kind assumes i.i.d service times for queues, and the other kind attempts to incorporate the dependence between service times. The i.i.d assumption leads to an M/G/l type approximation that typically yields underestimates for steady-state queueing and delay distributions. The other models proposed attempt to take into account the correlations between pairs of dependent cycles. The intention here was to show that once an explicit form for the cycle-time distribution is obtained, several approaches (all giving special attention to dependence) in modelling these queues are possible. CHAPTER VII STABILITY AND EAIRNESS IN TOKEN-PASSING SCHEMES If the mean queue length at station j, jeS is finite, for finite Aj and positive service, walk, and switching times, then the queueing process at station j is called a stable process. Assuming that the queueing process at station j has a stationary distribution, it can be shown that the queueing process is stable. Observe that while stability is a consequence of stationarity, the converse need not hold. A stable queue is not necessarily stationary since a mean queue length may be finite even though its distribution may vary with time. Let pj - kjE(Xj) be the mean channel utilization by customers at station j. To the observer at station j, pj takes the form of a traffic intensity at queue j. Unlike standard GI/G/l queueing situations, no simple condition exists involving pj alone that can ensure stable queueing conditions at station j [Kueh79]. In Bq.(4.ll) it is shown that the traffic intensity at a single station can be computed via the SV method provided the limiting distribution for the vectors is known. Additionally, it is known [Weut77] that steady-state queueing distributions at a given station will be stationary only if the traffic intensity at the station is less that 1. In fact, only under this condition will the matrix G defined in Bq.(4.l6) be positive and stochastic. In section 7.1, a stability condition is given in a form that is related to the SP method. In 135 136 section 7.2 we describe how a system's degree of stability is related to the distance between the vector of mean arrival rates and a critical point in an N-dimensional space. Simple descriptive measures of system stability are presented. In section 7.3 we introduce the issue of fairness to describe how fair the operating protocol is to the N stations. The intention is to describe fairness within an operating protocol, and not between protocols. With some additional effort, the ideas presented here can be extended to compare fairness between different protocols. For a given set of system parameters, a flexible measure that describes how fairly service is distributed across the system is presented in section 7.4. The token-intervisit time for a station during its active cycles (i.e., those cycles in which this station makes a transmision) is the key statistic used in the fairness measure. The flexibility arises in our ability to choose an arbitrary linear combination of the moments of this random variable to define fairness in our own context. In section 7.5, we present an application of rarefactions to show how an approximate first passage time distribution may be computed. Since the approximation is based on a renewal assumption for the cycle-time process, the approximation will work well only for high and low loads. 7.1 Stability Of IQCS Sch-es Assume that the arrival, walk, service, and switching distributions at all queues are stationary. Treating each queue j, jGS, 137 as a GI/G/l queueing scheme, stability criteria for individual queues and for the whole system can be developed. Given that all queues in the set S\{j} are stable (which means that they have sufficiently small arrival rates), queue j arrives at its maximum contribution to the cycle time as pj approaches 1. If the arrival rates of the other (stable) queues remain unchanged, the longest cycles seen from station j correspond to ones in which a customer from queue j is served with probability 1. These cycles give rise to a mean cycle time of 2 E(Yk) + Z E(Vk) + E(Xj) res hes kfj E.(C) = I (1) 3 l - 2: pk + z: kkEfl'k) res res kfj Kfj where Ej(C) is the mean cycle time conditioned on the event that a customer from queue j is served during each cycle with probability 1. Observe that for Poisson arrivals, the successive (random) queue lengths seen by the server at station j form an embedded Markov chain. This fact was already made use of in Bq.(5.3) to obtain the probability that the server finds station j empty at any of its scan instants (i.e., Bq.(5.4)). Since the queue at the reference station has the same embedded Markov chain as an M/G/l queue, a limiting queue length probability vector with positive entries will exist if, and only if, this probability vector is the invariant vector of the transition matrix describing the chain. It is easy to prove ergodicity for the chain, and consequently, the existence of the invariant vector. But such a vector (with positive entries) can exist only if Bq.(5.4) holds. Using station 138 j's conditional cycle-time as a service time random variable, and noting that the first two moments of this random variable are finite, by hypothesis, we arrive at the following. The reciprocal of Ej(C) behaves as an upper bound for values of kj that generate stable queueing conditions at station j. In other words, queue j is stable provided that = l- r (2) where kj' is the critical arrival rate for queue j customers. If the arrival rate at queue j equals or exceeds this value, then queue j grows in unbounded fashion, or is said to saturate. This critical value for queue j defines its stability boundary. In the case of QEDs other than s-Qifl = 1, corresponding stability criteria may be constructed. In particular, consider the service scheme r-OBD - n In this discipline, the server attends to the queue at j' station j upto nj times in succession before moving on to station (j+l). The conditional cycle-time mean at station j can be obtained from Eq.(l) provided that the term E(Xj) is replaced by njE(Xj). In order to obtain the critical arrival rate for this discipline, the quantity 1 given in the fraction in Bq.(2) must be replaced by hi. It can be shown [Kueh79] that conditions of stability at queue j are sensitive to the arrival rates, service times, and switching times of all the other queues, as well as the sum of all the walk times. Regardless of the various customer arrival rates in the system, the server's mean cycle time is always stable since it remains bounded above 139 by the sum of all the mean walk times and mean service times. This characteristic of token-passing guarantees that all stations receive server attention within a random time that has a stable mean. 7.2 Stability Index: A Measure of System Stability If the condition in inequality (2) is satisfied by all N queueing processes then the entire system is stable. When modelling symmetric systems, the stability boundary is the same for all queues. Investigation of the condition in inequality (2) will show that kj is forced towards zero as N is increased asymptotically. Keeping all other parameters fixed, increasing the number of stations in a symmetric model requires that the arrival rates be decreased in order that condition (2) is satisfied and stability maintained. It would appear that asymmetric models are more realistic since it will often be the case that some queues fail to satisfy the stability condition. A typical situation is one where some station is doing large file transfers (generating large volumes of traffic). Such heavily loaded stations will contribute one packet to every token cycle until their packet traffic decreases. Thus it is necessary to investigate conditions of partial stability, where some queueing processes are stable.' In such an asymmetric system, the lightly loaded stations witness increased token-passing overhead for the duration of time that some other stations are heavily loaded. If the arrival parameters do not vary with time, we can define a simple stability index to capture the relationship between loading (offered 'system traffic) and throughput (channel utilization). Let the vector of 140 critical arrival rates for a stable system be denoted by A' = (ll',...,>.N'). A simple index of stability may be defined as I ' l. 2 l. |{ J l 3 3 }| M") = (3) N which really is the fraction of unstable queues in the system. Different configurations of unstable queues can give rise to the same value for the stability index. In order to understand the relation between the stability index, throughput, and the notion of partial stability, one must study the effects of varying arrival rates on the N-station system. Consider. the following argument presented in terms of an asymmetric system. From inequality (2) it can be seen that the boundary of total system stability is defined by the sides of an N-dimensional cube in an, whose corners are vectors with entries all zero, all nonzero, or have all but one entry zero. These respectively correspond to the zero vector, the vector A”, and vectors of the form Ax“ = (0,..,k *,...O) that describe the stability boundary for station k k alone. When the vector of arrival rates lies in the interior of the cube, the system is totally stable. Replacing the inequality in (2) by an equality, we obtain a system of N equations in the variables A , RES. The critical arrival rate vector A, can then be determined as the solution to this linear system. Let "k = (XI: - Vt) and = [ 1: Earl.) + 23(5)] + S(Xk). The individual station 1 S k if): (stability boundaries are obtained as 141 n ( 5r - ”r ) res , m l. = , 395. (4) 3 { n sk + n uk } - { z n skui } res res res ies ifk Let the (variable) vector of arrival rates be given by A = (kl,12,...,kN). The regions of stability as given by inequality (2) are bounded by planes in an N-dimensional space, with A. as a point common to all planes. Thus A, defines 2N different regions, only one of which is bounded on all sides. When A lies inside this region (which is the cube just described), we have total stability. Here I(A‘) is zero and does not say much about system throughput. If A z A“, then A lies in an infinite region where all queues are unstable causing total instability, with 1(A') = 1. In this case, the throughput attains its maximum possible value. But for these two regions, all other regions describe situations of partial system stability. This happens when some but not all coordinates of A are strictly less than corresponding coordinates in A', causing 1(A') to take on values between 0 and I. In this region, the system throughput will be a nondecreasing function of the stability index. When A lies within the cube that ensures 'total stability, 1(A') does not yield any information regarding system throughput. Here, a stability index that is more sensitive to changes in A can be defined. This is given by 15(A') = II A - A* ll , (5) 142 where || . || is used to denote the Euclidean norm in N dimensions. The system throughput in the absolutely stable region can be seen to be a nondecreasing function of the inverse of 15(A*). A phenomena involving stability occurs here that appears to characterize the multiqueueing situation and is unlike conditions in typical queueing systems. If A lies in the absolutely stable region and all coordinates are simultaneously increased, the queues that are first to become unstable are precisely those with the highest arrival rates, and they attain saturation in the order of decreasing arrival rates, independently of all other parameters [Kueh79]. 7.3 Issues of Fairness The fairness of a distributed protocol is an important measure of network performance since systems operating under global optimality are not necessarily fair [GeStBO] in terms of individual usage of the resource(s). In local-area networks, since protocols are generally designed to function far from saturation, individual station delay is an important parameter in the determination of protocol fairness. Unlike long-haul and contention based networks, individual station channel utilizations no longer maintain great importance in fairness determination, especially for the one-packet at a time QED. This is due to the fact that active stations are periodically visited by the server (token), independent of their buffer status or desire to transmit. This is not to imply that utilization cannot be taken as a factor in the resolution of fairness; only that a station's channel utilization by 143 itself does not reflect this station's ease of channel accessibility. For example, if the station under consideration transmitted packets with a mean length much smaller than the mean packet lengths of all the other stations, and if its mean packet arrival rate is not greater than that of any other station, then this station will have a smaller channel utilization value than any other station. But this only means that this station is less demanding of the channel than the other stations, and does not imply that the protocol is necessarily unfair. The issue of fairness in the context of local area networks was first introduced by Marsan and Gerla [MaGe82]. These authors define a fairness measure in terms of mean delay and mean throughput for individual stations. It is a well known fact that ordered access schemes are generally superior to contention-based or random schemes at conditions of high load. But under light load, the contention schemes perform better. The performance keywords here are mean throughput (at high loads) and mean delay (at low load) for individual stations. Define a particular station's accessibility to the channel (in the mean) as a ratio of its throughput at high load to its delay at low load. For convenience, we call this the mean throughput-delay ratio, or TDR. Fairness in [MaGe82] is defined as the smallest ratio of TDR statistics generated by pairs of stations, for every pair of stations on the network. Additionally, a protocol is defined to operate in an optimally fair fashion if the fairness statistic is unity, i.e., every TDR is equal to every other TDR. In the next subsection, we present an alternate approach to determine fairness. This method is based on the random time between a 144 station's access of the transmission medium and its next chance to access the medium. A definition of fairness is obtained in terms of distributions. Our approach is motivated by the fact that mean values are limited in their scope and do not yield any information about variations in resource usage. That is, the variation in the utilization of the channel (by a station) has important consequences on how the channel usage varies between the other stations. Since the total capacity of the channel is bounded, a highly variable or highly skewed transmission time by a single station can have strange affects on delays experienced by other stations. It is fairly easy to build examples where the fairness measure proposed in [MaGe82] cannot capture such information. 7.4 A Measure of Fairness In token-passing schemes, the cycles that are important to a particular active station are those cycles in which the station makes a transmission. Let Dj be the random length of a stationary cycle conditioned on the event that a transmission from station j is made. The notion of stationary here is taken to mean a random cycle-tbme with law defining the density in Bq.(5.l4) for the case of asymmetric systems, and Bq.(5.23) for symmetric systems. Define the order statistics R1 = max {D1,...,DN} and R2 = min {Dl""’DN}' corresponding to the largest and smallest such cycles, respectively. Let vi = stnzil/Emli] and 01. = aid. for a en+ and i=o,l,2.... . For 1' i .convenience, we limit ourselves to a (generally small) finite number of 145 weights, with a sum normalized to unity. For each integer k, k 2 O, we or) = (00,01,...,0k) and .(k) = (aO'al'...'ak)' and a define vectors 0 . . - (r) _ (r) corresponding fairness measure as A(k) - ||o a 'Ik , where Il’llk is used to represent the euclidean norm in k dimensions. t The protocol is said to exhibit perfect fairness in the r “ degree if X(k) = 0, for arbitrary choice of the weights a Note that fairness in i‘ the first degree is equivalent to the condition that r(nj) = d, dea*, for all jes. The measure introduced above can be motivated by the following argument. Focusing our attention on the conditional cycle times, we see that if every station's conditional cycle time converges to the same random variable in distribution, then every station must have the same fair chance of accessing the transmission medium. In other words, not only is their ”waiting time” fair in the mean, but it is also fair in terms of moments upto order It. For a given value of k, we can choose a weight vector a that appropriately describes our level of interest in each of the k moments. Thus if we are equally interested in the mean and variance, we set a1 = a2 = 0.5, and a1 8 O for all i, 2 S i S k. The further away the value of (01 + 02) from unity (i.e., the sum of the weights), the less fair will be the protocol. (k) as the centre of a unit ball in a We can view the vector a k-dimensional space. The measure X(k) lies within the ball or on the boundary (for a totally unfair protocol). The distance of X(k) from a(k) determines exactly how far the protocol operates from perfect fairness in the context of the first x moments of conditional cycle ‘times. 146 There is an interesting problem that presents itself at this time. Note that a fairness measure is really a random function of the parameters of the system. That is, it changes according to variations in pj, “jo’ “jl’ aj, jES, and N. Keeping some parameters fixed while varying others will allow us to study the distribution of a general fairness statistic X, as a function of the changing parameters. Consequently, this will allow us to determine those parameters that have the maximum effect (where we must define the kind of effect we are interested in) on the fairness of the protocol. Consider a measure X(k) for a given system to be defined in terms of the cycle-time density given in Bq.(5.l4). To obtain the density of the conditional cycle-time random variable Dj, simply replace the probability pj wherever it appears in Bq.(5.l3) by 1. This can be done for each station on the system. By definition, the random variables D3, jeS, are conditionally independent. The distributions of the order statistics R1 and R2 can be determined in a fairly straightforward fashion using the N distributions of conditional cycle-times 01,...,DN. Let the distribution of Dj be denoted by FDj' jeS. In order to obtain the distribution F of the random variable R R1 we proceed as follows. 1 By definition, FRl(r) = P(Rl S r) =P(Dlsr;eeeee' DNsr) (6) The largest of all the D 's is less than or equal to r if and only if 1 all the Dj's are less than or equal to r. By the assumption of ‘independence of conditional cycle—times, this gives us 147 STATION (3-1) sunos 5 5c»: msrm —| | I l ' : a, ' l l I ' | )tranrunr INSTANT ‘—----——-— -J 93*! IATIOW (3+1) (a) A cycle involves either a transmit phase or a switch phase. Fig.7a Transmit phases and Switch phases F— , ...].— .. ...| a ——1. ‘ c l c ‘ c ‘ C 1 1:31 SWITCH mssnn IRASSHII sullen IFANSHI‘I INSIANI INS] A81 INSIAN'I INS} ANT INSIAN'I (b) Iclationship between cycle and first passage times. Fig.7b Circle-times and Passage Times 148 FRl(r) = FDl(r) . FD2(r) ..... FDN(r) (7) and by using a similar reasoning, we obtain FR2(r) = l - (l - FD1(r)).(l - FD2(r)).....(l - FDN(r)). (8) Given the distributions of RI and R2, the next step is to obtain the distribution of the quotient random variable R = RZ/Rl' Since we are dealing with a quotient random variable, .and not with ratios of moments as before, the fairness statistic x' is a tunction of random variables. In general, determining the distribution of R is not a straightforward matter since we are now dealing with dependent random variables (i.e., order statistics are dependent). In order to find the distribution of the product of dependent random variables the two-dimensional Mellin transform [Spri79] can be used. 7.5 Approximate Distributions For Token-Intervisit Tiles Consider the scene involving reterence station j in Fig. 7a. On arrival at this station, the token may go into either a transmit phase or a switch phase depending on whether a customer is present or not. We are interested in successive token departure instants trom station j. The token's departure instant from the reference station after a transmit phase is called a T-instant, and the departure instant after a switch phase is called an S-instant. I: each type or instant is considered to be an event, the random times or the process {Z (t)} from -any T-instant to the next T-instant, and from any S-instant to the next 149 S-instant are the first passage times of the process between the respective events. Let the random variables J and K represent the first passage times for the transmit events and switch events (Fig. 7b). with distribution functions FJ and PK, respectively. Let J1,J2,....,Jn,... and K1,K2,....,Km,... be i.i.d (independent and identically distributed) sequences of random variables from the distributions FJ and Fk, respectively. Given the parameters of the system the joint densities of successive cycle time random variables can be developed and examined for serial dependence, as has already been outlined in the previous chapter. This dependence is small when the various traffic intensities are either very small or very large [Kueh79]. If the dependence is known to be small, then the cycle times (intervals between successive departure instants) seen at station j can be approximated by a renewal process {Sn,nZl;FC(.)}. Suppose that we delete each point SD of the renewal process with probability qj. Next, expand the time scale by the factor l/pj. The deletion of each point is done independently of the other points, and independent of the process {Sn}. By this rarefaction procedure [RenySG] we obtain a new point process Rpj = {Sn'}. The notation Rpj is used to denote a rarefaction procedure with respect to scale l/pj. Each term in the rarefied sequence {Sn'} is a scaled random sum of intervals of the process {Sn}, where each interval has distribution Fc(.). Clearly, the random number of intervals used in the sum is geometrically distributed with parameter pj. Thus 31* = ijx, where x is the first index that is hnot deleted. 3x is actually the first passage time of the process 150 {Z(t)} from a transmit event to a transmit event at station j. Alternately, 5x is precisely the random variable J, and S , is a scaled 1 version of this passage time. Consequently, FJ is the distribution of a geometric sum of random variables c with density fc. Let F3” be the interval distribution of the rarefied process {Sn'}. Then, except for the change in scale, PJ* and F: are the same distribution. We new state a theorem [nenysel that enables us to determine the interval distribution Ffi'. Theorem 7.1: Given a renewal process {Sn,n21;FC(c)}, the rarefied process Rpj{sn} - {8”,} is also a renewal process. The interval distribution F t of the new process is given by J n _ a (*1) 1'1 FJ (c) pj 1:1 FC (c/pj)qj (9) where 0 < qj < 1, pj = 1 - qj, and FC(*i) is the i-fold convolution of the interval distribution FC. Corollary 7.2: For renewal processes {Sn} and {Sn*}, where the latter process is a rarefaction of the former, if E(Sk) < +0, then E(Sk) = E(SK') for x z 1. If 3(sk) - +~, then r(sk') - +o for x z 1. Note that except for a scale change, Theorem 7.1 gives us the distribution of the random variable J. Replacing pj by qj and 151 vice-verse in the above argument yields a rarefied process whose interval distribution PK” is a scaled version of. the distribution of PK. Thus, we obtain the distributions of the first passage time random variables J and K. Using the fact that J and K are sums of random variables obtained by geometric compounding, we can apply Wald's theorem [Taka62] to obtain the means as E(J) = E(C)/pj and E(K) = E(C)/qj. and their variances as V(J) ( l/pj ) v(c) + ( qj/pjz ) (E(c))2 (10) v(K) ( l/qj ) v(c) + ( pj/qu ) (3(0))2 The mean passage times obtained in this manner are exact, independent of the renewal assumption. This means that the expressions for mean passage times are valid under all traffic conditions in a stationary system. If the traffic conditions are very low or very high, V(C) is a good approximation to the ”true" cycle time variance, and the expressions for passage time variances can be expected to perform well as approximations. If the arrival rates at all queues are zero or all queues are unstable, the renewal assumption is asymptotically exact. Since successive cycle times are now independent, V(C) obtained from fc is exact, and so the variances for the first passage times are also exact. For other traffic conditions, the serial dependency of cycle times must be taken into consideration. The approximation improves with the accuracy in the estimate of cycle-time memory. When pj = q., we find that J and K reduce to random variables 3 with the same distribution. When pj f qj, J and K will have different 152 distributions. Using this line of thought, we try to explain the behaviour of Kuehn's model. Let random variables S and T represent the lengths of cycles involving switch phases and transmit phases at the reference station, respectively. In the stationary state, the instants at which packets from station j are transmitted can be viewed as renewal points. At these instants, the queueing process at this station can be treated as an embedded Markov chain. Using renewal theory arguments, Kuehn obtains approximate expressions for the mean number of customers waiting at station j at the server's scan and departure instant, and the mean customer waiting time (service time excluded). We observe that independence between queueing processes at the various stations follows indirectly from the assumption that S and T are each i.i.d. random variables. Intuitively, we would suspect that the switch random variables (i.e., like S) and the transmit random variables (i.e., like T) are dependent, both within types, as well as between types. Given the occurrence of a T-cycle, it is more likely that the following cycle is a T-cycle rather than an S—cycle. That is, the longer it takes the server to return to the reference queue, the greater is the probability of finding a packet awaiting service at this queue. Thus, assuming that S and T are independent, or assuming that sequences of switching cycles and sequences of transmit cycles are i.i.d in themeslves gives sufficient cause for concern regarding the validity of the independence assumption. Note that the manner in which S and T are defined ensures that SC?) > 8(8). If the packet traffic offered by station j is very small, then 153 pj is close to O. In this case E(S) is very close to E(T), since packet contributions from station j are scarce. So the approximation can be expected to work well for station j. If the offered packet traffic at station j is very high, then pj is close to l, and station j makes frequent packet contributions to the cycle time. Now we have scarce S-cycles and conditioning on the distribution of these cycles does not offer much to the end result. So the approximation can be expected to work well again. When the offered traffic is moderate, then pj is closer to qj than before. Our ability to discriminate between the two types of cycles begins to get weaker as pj approaches qj. Consequently, the variance of the cycle time begins to depend more heavily on the actual arrivals at station j. At this stage, the approximation begins to degrade. Indeed, this was demonstrated both experimentally and analytically in Fig. 5c. 1.3 Summary In this chapter, we proposed a new and very general definition of fairness for token-passing protocols utilizing an s-QHI = 1 scheme. It is possible to obtain corresponding measures of fairness for other Ohms by generalizing this approach. The intention of resorting to distributions in our definition is motivated by the fact that mean values tend to neglect valuable information in a statistical sense. Consequently, it follows that the approach to determining the distributional measures is computationally more complicated than the {approach suggested by Marsan and Gerla [MaGe82]. 154 The fairness measure defined in section 7.4 is a function of several parameters, and in this sense is really a statistic. An interesting problem that immediately presents itself is the distribution of this statistic. In section 7.4 we presented a method to determine its distribution, and reserve the resolution of an explicit form for future work. Once the distribution is obtained, other insightful questions may be asked. In particular, we may be interested in the effect of the parameter N on the distribution of the fairness statistic, or the limiting and asymptotic forms of this distribution. The discussion on stability is a generalized form of Kuehn's [Kueh79] work on multiqueues. The proof for stability is obtained via the embedded Markov chain of queue length states. We presented two simple measures of stability, one in which the system's arrival rate vector fell outside an N-dimensional cube defining a stable region, and one in which the vector fell within the cube. Additionally, we discussed a possible interpretation of stability in relation to system throughput. There is considerable scope for future work in the realm of system stability, especially for more general arrival processes and time-varying rates. The last section of this chapter makes use of the fact that the cycle-time process closely approximates a renewal process for very high and very low loads. Clearly, the approximation improves as the load is further increased, or decreased. By treating consecutive service events and switching events as renewal points in their respective renewal processes, an application of rarefactions easily yields the interval distributions for these processes from the original (approximate) 155 renewal cycle-time process. The two intervals can be treated as first-passage times between service events and switching events, respectively. CHAPTER VIII ADAPTIVE TOKEN-PASSING SCHEMES Token-passing on large asymmetrically loaded systems can cause unnecessary delay for some stations (i.e., those that are more active) when the system load averaged over all stations is low. If a station's delay periods coincide with fruitless token-solicitations at inactive stations, a reduction in delay will follow a reduction in the number of such solicitations. This can be done by scheduling alternate token-paths at frequent intervals, in a way that the scheduled paths bypass any inactive station visits. Scheduling is done during a combined transmission and information gathering cycle (complete network traversal) of the token, with dynamically assessed priorities assigned to the active stations. An adaptive token-passing protocol (ATP) that achieves this has been presented in [ReHu85]. The ATP method is introduced as an upward compatible enhancement to the non-adaptive token-passing (NATP) bus protocol proposed by the Standards Committee [IEEEB4b]. Since ATP requires that the token-path be modified to accomodate the heavily loaded stations more frequently than in WATP, an adaptive system behaviour is required in ATP. Hence, the corresponding queueing model is called the multi-queue and adaptive server (MDAS) model. Following in the spirit of chapter five, the method of analysis used is based on service probabilities. Thus, since the underlying 156 157 assumption is one of independence, the results of this chapter are approximations. A key part of the analysis used in determining cycle-time distributions involves the queue length density function values for one-customer queues, for each queue on the system. In this chapter, these probabilities are determined by M/G/l approximation methods (i.e., service time represented by cycle-times, quasi-service times, moving averages etc.). This introduces a second approximation into the analysis. If such an approximation is not good enough, then the exact probabilities can be used. Recall that a method for computing these probabilities exactly was introduced in chapter III. The main results in this section are the distributions of cycle-times in the MQAS model or equivalently, in the ATP protocol. These distributions are important in performance considerations. With the aid of such distributions, other important distributions (i.e., station intervisit-time distributions, packet queue length distributions etc.) can be obtained. The derivation of these distributions, various important performance measures, and criteria to aid in comparing WATP and ATP protocols are a part of an ongoing research programme. A brief description of the organization of this chapter is as follows. In sections 8.1 through 8.3 we describe the operation of the ATP scheme in terms of the MQAS model. Since the system uses two kinds of service cycles, the distributions involving both cycle-types are introduced in section 8.1, the scheduling method and the two cycle-types are introduced in section 8.2, and the distributions involving the second cycle-type are given in section 8.3. The semi-Markov model for server behaviour is described in section 8.4 and the distributions for 158 observer l O N-l 1 Cycle C .LL.\ . /— Non-adaptive Token-passing Fig.8a HQCS abstraction for WATP N observer 2 C‘- cycle C2- cycle Adaptive Token-passing Fig.8b HQAS abstraction for ATP 159 both cycle-times are derived in section 8.5. The maximum entropy approach used in computing steady-state probabilities for nonempty and one-customer queues (i.e., probabilities that are require to determine the cycle-time distributions) is outlined in section 8.6 and the existence of stationary limiting distributions (under independence) is shown in section 8.7. 8.1 Description Of Model Distributions The ATP bus is modelled by a system of N independent and infinite buffers chained together to form a logical ring by sections of varying cable lengths. Figures 8a and 8b depict similar abstractions of the MDCS and MQAS models. It must be noted that the server's behaviour as described by this model is only one of a host of possible adaptive schemes. Packet arrivals at station j are generated by some process with interarrival distribution given by Aj(t) = Pr(IjSt), where I is j the interarrival time random variable at station j, 195 = {l,2,....,N}. Let us label the walk between station (j-l) and station j as w jeS. 1, In our notation (j-l) indicates station j's predecessor and (j+l) indicates station j's successor on the path of the token. The station index imediately after j is obtained by computing (1) mod N + 1. The time spent by the server in w is given by Yj, where Y has distribution 1 J P(YjSt) = Uj(t), for all w 6'. J 8.2 Cycle-Times l'or WATP And ATP For as long as it remains part of a logical ring on a 160 token-passing bus, the station that initiates a logical ring formation is defined to be a reference station, and similarly, the station that precedes this station on the logical ring is called the predecessor station [Refluas]. If these stations desire to retire, they must first transfer their respective identities to qualified stations on the ring. For the rest of our discussion, we take jes to be an index in which we have a special interest. In the case of MATP, j is arbitrary; since certain quantities are defined with respect to station j, it is called a reference station. In ATP, our definitions require that j be the single predecessor station on the bus. Note that this restriction is merely due to the fact that ATP cycles are defined with respect to the predecessor station. The analysis applies regardless of the particular station defined to be the predecessor. In this analysis we consider unrestricted queues, with at most one customer served per station at each of its scan instants. Let the MATP cycles (defined with respect to station j) be called C-cycles, with C denoting the random length of a stationary cycle. Let the density and distribution functions of this random variable be given by fc(.) and FC(.) respectively. The behaviour of the token in the ATP scheme involves the repetition of a pair of cycles. During the first cycle (which is similar in appearance to a C-cycle and defined with respect to the predecessor station). the server walks, switches, or services stations just as in RATP. The only difference is that all stations in S whose customer queue sizes exceed one at their respective scan instants, are labelled by the server as active stations. Thus, when the server 161 returns to the predecessor station (and the first cycle is complete), a set A of momentarily active stations on the bus will have been determined. The status of the active stations is made known to the other stations on the bus during the first cycle via broadcasting. The second cycle begins at the predecessor Station and in this cycle only stations in A are served, in the same order that they were visited in the first cycle. In this way, stations that are known to have a backlog of packets are given priority, with information that is accurate upto a cycle-time. As soon as the last active station (if the first cycle does find any active) has completed its transmission, the predecessor station immediately transmits a token control_frame to the reference station, from where the first cycle begins all over again. If the predecessor station detects the condition A = o, by performing a counter scan [ReHuBS], it immediately transmits a token control_frame to the reference station in order to initiate a Cl-cycle. Thus, steady-state operation of the ATP bus involves the repetition of the first and second cycles, in alternating fashion. Let the first cycle be called a C -cycle and the seCond cycle be 1 called a Cz-cycle.. Correspondingly, let C1 and C be the random lengths 2 of these cycles. Note that if A I S, then the Cz-cycle is the same as the Cl-cycle, since every station is labelled active. If A 8 a, then no station is found active, and the CZ-cycle is of length 0. The situations A - S and A - ¢ occur under heavy traffic and light traffic conditions, respectively. We follow a convention that assumes the Cz-cycle always occurs after a Cl-cycle, even if the latter cycle determines no momentarily active stations and consequently generates a 162 null C2-cycle. In this event, its length is taken to be zero. 8.3 Service, Switch, And Scheduled-Walk Distributions If station i is found empty during the C -cyc1e, the server takes 1 a random time Vi to switch past station 1 to walk wi+l' 195, where Vi has distribution P(ViSt) = 81(t). If a customer is served at station i during the Cl-cycle, then the customer's service time is a random variable Xi with distribution P(XiSt) = Bi(t). During the CZ-cycle, since only the active stations are visited, there are no switching distributions involved. Define a scheduled-walk to be the server's walk between stations in the Cz-cycle. In order to be able to visit only the active stations, the server's path in the Cz-cycle is scheduled in advance with the aid of station counters [Reau85]. Thus a scheduled-walk is a walk between active stations, or between an active station and the predecessor station, but not necessarily between adjacent stations. For each station iGA that is visited during a CZ-cycle, the server spends a random time y ' in the scheduled-walk to reach this station, 1 and a random time Xi to serve a customer at this station. The random I I I variable Y1 has distribution P(Yi St) = Ui (t). Each set A that is generated by a Cl-cycle (and consequently defines a subsequent C2-cycle) is defined to be a subset of the set 5' - {1',...,N'} of stations that potentially require transmission of a packet in each Cz-cycle. The time spent by the server in any state 16A is given by the random sum (r ' 1 + X1). In other words, this is precisely the time taken by the 163 server to walk from the previous active station (or predecessor station) to station i, plus the time taken to serve a station 1 customer. For each 165', we take the random sum (11' + x1.) to have the distribution Bi'(t). For analytic convenience, we assume that all distributions described in sections 8.1 through 8.3 possess finite first and second moments. 8.4 The Markov Chain Of Server Transitions The analysis of the ATP bus is similar to that of the NATP bus, where the MQCS model is used. Throughout the analysis, we use the MQCS model as a background model in order to obtain the distributions of interest in the MOAS model. To be precise, we seek representations for the distributions of the random times spent by the token in the first and second cycles, respectively. In order to arrive at these, we require certain probability vectors, and in order to obtain the vectors, we must examine how MQAS can be obtained as a modification of MQCS. In this section, we are only concerned with asymmetric systems. Consider the scene depicted in Figs. 8a and 8b, where observer 1 is stationed at the reference queue of the NATP bus, and observer 2 is stationed at the reference queue of the ATP bus. Assume that both systems are operating under identical conditions (i.e., the respective arrival, service, switching, walk, and scheduled-walk distributions are the same, for corresponding stations and walks). Also, assume that the systems are operating under steady-state conditions, and all queue length distributions are stationary. 164 Observer l sees a single server queueing system at station j. Recall that the difference between this system and a GI/G/l system was discussed in section 5.1. In the ATP system, observer 2 also sees an approximate GI/G/l queueing system. But in this case, the ”service distribution” is more complicated. For each station ies, let Ti' be the random time between two successive (server) scan instants at station i. We call this the trip-time of the server with respect to station i. Note that an instance of Ti, could either be C or C . If F 1 2 Tj" c1' and F 2, respectively, then C2 are the distributions of Tj*, C and C 1' observer 2 sees the trip-time as a compound distribution involving both C1 and C2. The distribution FTi' , 195, is useful in the investigation of system performance measures such as queue length distributions, packet delay distributions etc. Let Zn be a random variable taking values in the finite set S., where 5* is a union of sets S, S', and W, with R an index from the set of non-negative integers 1+. Let Tn be another random variable such that for each Zn€S*, Tn takes values in the non-negative real numbers R+. The sequence of pairs {(Zn,Tn)} is a Markov renewal process whose limiting behaviour is our main interest. Note that the assumptions made in chapter II carry over to the present analysis as well. The transition functions of the ATP server are considerably different from those of the NATP model's server. In this case, Qij(t) is an element of a 3N x 3N matrix Q, i.e., the semi-Markov kernel of the process. The server's behaviour over states of S. can be viewed as a .semi-Markov process. Let pOj’ plj' and qj be the probabilities that the server encounters zero, one, and more than one customer at station j's 166 scan instants of the Cl-cycle, respectively, for all jes. These probabilities are the mixing densities used to obtain the holding time distributions of the process in terms of the distributions specified earlier. The scene depicted in Pig. 9 describes the transitions of the token over the state space S. = {1,2,3}U{wl,w2,w3}u{l',2',3'}. In general, the kernel 9 is defined as (1 - pai)Ui(t) wkew, j=kes pOiUi(t) i=wkeW\{wl}, j=wk+l€W (1 - pOi)Bi(t) + P0151“) i=kes\{N}. j=wk+1ew N . . qkmgl (1 " gm)Bi (t) 1=Nesr j=k es I Jfll N mill (1 - 9m)Bi (t) i=Nes, j=wlew Qij(t) = k-l ' . ' . ' ' (1) N I I I I n (1 - qmnai (t) i=1: as \{N }, jwlew m=i+l 31' i=N', j=wl N . . N Paimlll (1 - qmwi (t) i=vN. j=vl o ' otherwise a for all i,jeS . For the interpretation of g, the ordering of states (aligned with rows and columns) is taken to be 167 {wl,1,w2,2,...,wN,N,1',2',...,N'}. Define p to be the matrix with entries pij = Qij(~), for all i,jes.. The model can be interpreted as follows. The basic dynamic particle of our system is the server, or token. Its behaviour in moving among the various states of 5., as given by Zn, is governed by a monodesmic semi-Markov process which is homogeneous in time and has a kernel 9. The matrix P is the matrix of transition probabilities of the underlying Markov chain. P describes the transition probabilities of the token from state i to state j. On leaving state wieW\{wN}, is p01 the probability that the token encounters no customer at station 1. It follows that for each Cl-cycle, p01 is the probability that the token encounters an empty buffer at station i, and (1 - p01) is the probability that the token finds at least one waiting packet at station i's buffer, for all ies. Note that p11 is the probability that exactly one customer is seen waiting at station 1, for all 165. From state w", the token visits state N with probability (1 - pON)' and with probability p0N it either moves to some state in the set S', or to state "1‘ From states "N or N, the states visited in S. depend entirely on the probabilities qi, for all 165, where qi is the probability that the token encounters more that one waiting customer at the buffer of station 1 during each Cl-cycle. From states ke{N'}US\{N}, the token moves to state wk+l with probability 1. The trip-time at station j, Tj*, can also be defined as the first passage time of the process from a state in the set {j,j'} to a state in the same set. This corresponds to the random time between token ‘ reappearances at the predecessor station. The random time Cl is the 168 time between the instant at which state w is entered and either (i) the 1 instant at which state ”N is left (if no customer is found waiting for service at station N), or (ii) the instant at which state N is left (if a customer at station N is served). This corresponds to the random time spent by the server in visiting (and possibly serving customers in) the various states of S. The random variable C2 is the time spent by the server in the states of different subsets A of S', for each such subset of active states generated by the preceding Cl-cycle. Under the independence assumption, Cl can be expressed as a finite sum of random variables with distributions Bi(')’ Ui(’)' Si(')' and C2 can be expressed as a finite sum of random variables with distributions Bi'(t), 195. C1 and C2 will possess limiting densities fCl(.) and fc2(.) that we would like to determine. Note that since the CZ-cycle depends on probabilities associated with the Cl-cycle, the random variable C depends on C 2 l' 8.5 Cycle-Time Distributions for Asymmetric Systems In the following discussion, we demonstrate how FCl(.) and FC2(.) may be determined with the aid of the distribution Ft(.). The arrival process at each station 19S is assumed to be Poisson(li), and 31' Si' ”1' and U1, are assumed to be exponential, with means 1/“10’ l/“il' 1/oi, and 1/ai', respectively. Since a cycle is defined in terms of contributions from all stations, the random length of a cycle will remain the same regardless of the index of the station from which the observer measures it. In this paper, we restrict our attention to 169 asymmetric cycle-time distributions for the ATP system. By using the symmetric form of the cycle-time distribution for C, it is simple to apply our results to the symmetric ATP distributions. Exponential distributions are used mainly for convenience and required only for interarrival times. The Distribution Of AM MATP C-cycle Let pol.” be the probability that in the NAT? process the server encounters no customer at queue i, for all 165, in a stationary system (and recall that p01. is the corresponding probability in the ATP process). Also, let aio = (1 - pOi‘)“io and ail = 901'“11' for all ieS. Let 9 be the set of all N digit binary numbers representing the non-negative integers in the range [0,2N-1]. An element see is an N-bit binary vector of the form [k(l),k(2),....,k(N)]. The asymmetric and symmetric cycle time densities are given by Eqs.(5.l4) and (5.23), respectively, with p01“ used in place of p01. The latter term is now used to denote a measure with respect to the Cl-cycle. The Distribution Of An ATP Cl-cycle The expectation E(Tj*) is a maximum when all stations in the set S\{j} take part in a CZ-cycle while station j sees only Cl-cycles. That is, observer 2 never gets to see the server in the Cz-cycle due to very low traffic at station j. In this case, E(Tj') takes on the value [E(Cl) + E(C2)]. But in general, 170 E(Tj ) S [E(C1) + E(Cz)l or 5(Tj') s [r(c) + r(c)] s 25(c) (2) The inequality in Eq.(Z) merely says that E(C) takes the shape of an upper bound for E(C1) and E(C2). The inequality E(Cl) S E(C) leads us to conclude that (1 - Paj) s (l - poj') (3) A. A. J 3 By our assumption that both systems (MATP and ATP) are operating under identical conditions, inequality (3) yields 3 (l - pOj) s (1 - Paj’ I or pOj S pOj (4) From inequality (4), the effect of the Cz-cycle in ATP can be interpreted as follows. The server has a greater probability of encountering an empty station buffer (at each station) in the Cl-cycle of the ATP bus than in the C-cycle of the MATP bus, simply due to the server's adaptive behaviour. The important point here is that FC1(’) may be obtained in asymmetric and symmetric forms from qu.(5.l4) and (5.23), respectively, provided that 'is replaced by p01 for all ies. p01 Thus, the probabilities p01 for all 195 must first be obtained in order to obtain FC1(’) . The Distribution Of An ATP Cz-cycle Given that the server visits state i, 165 , the random time 171 I I (Xi + Y1 ) spent by the server in this state has distribution 81 (t). Since this is the sum of independent random variables, Bi may be obtained as 81 * Ui' for all 165, where ”*” is used to denote the convolution operation. Note that in general, it is not necessary to differentiate between index sets S and S. since a specific index in each set really refers to the same station. However, we do differentiate between these sets in instances where the kind of cycle being considered (i.e., first or second) is important. The distribution 8 '(t) is a i generalized Erlangian distribution with a density given by I , , exp(-uol.t) eXp(-oi t) b. (t) = u .a. [ , + . ] (5) 1 0“ (a -u) (u -e) i Oi 0i i for all 165. Note that Eq. (5) is given in asymmetric form, but will work for the symmetric case if the subscript i is suppressed. If the system is in steady-state operation, qi is the probability that the server visits state i, 195', during the Cz-cycle. The distribution of time spent by the server in state 195. under conditions of stationarity is given by I F21(t) = q181(t) + (l-qi)60(t) (6) where 60(t) is the dirac delta function, defined with o t ,1 a, ten“ 50“" = c- t = O and I +60(t) = 1. Note that this agrees with the transition matrix P R obtained from Q in Eq. (3). That is, 172 1im F21(t) = qi V165 . (7) t-ea The distribution of a Cz-cycle is thus a sum of independent random variables with the distributions F21,F22,...,F2N. Let aio = qiai “10 II and ail = (l - qi) for ieS . The Laplace-Stieltjes transform for the density of the random variable C2 is given by n 1 C2]=Z[na.k(i)][n ,][n 1] (a) . .1 nee ies neG1(s + “n k(n))(s + an ) mer L[f with 61 a {x|k(x)=0}, “2 . {X|k(x)=l}, and the set a defined earlier. I The plane of convergence for terms l/(s + “i k(i))(5 + a1 ) is the region defined by Re(s) > -min (oi'mi k(i))' VieS. Inverting the expression in Eq.(B) we obtain fc2(.) as I exp(-unc) exp(-on c) r {.n ai k(i)” [ Z . + . 1} (9) k% 195 11661 (on ' “n RU”) (“n KL”) ' an) Thus, Fcz(.) is completely determined provided that p01 and pli are given, for all ieS. From this and the previous subsection, we see that obtaining the probabilities p01 and p11, Pies, is crucial in determining the distributions FCl and FCZ' In the next subsection we examine how these probabilities may be obtained. 8.6 Computation Of Probabilities for The First Cycle A sufficient condition for the existence of a stationary cycle-time distribution FC(.) in the NATP process is the stationarity 173 of each station's queue length distribution. This is also the case with the existence of stationary distributions FCl(.) and FC2(.) of the ATP process. A necessary condition for FC(.) to be stationary is the existence of a time-invariant value for p0i*' $165. For FC1(') and FC2(.) the necessary condition is the existence of time—invariant values for p01 and pli' VieS. This is summarized in the following lemma. Lemma 8.1: If the queue length distribution at each queue j, j€S , is stationary, then the NATP system possesses a stationary cycle-time distribution PC and the ATP system possesses stationary cycle-time distributions Ft and FC The expectations E(C), E(Cl), and E(C2) are l 2' stable even in the absence of stationarity for the respective distributions. Also, there exist unique probabilities pojx (for the NATP system), , and plj (for the ATP system) such that j - 1 - le(cl) Aj{E(C1) - E(Cz)} pOj ‘O O I R po. 2 p01 and plj = p0j(l - ”Oj)/v0j for v = r z I (l.t) exp(-A.t) D (t) dt 0’ mes tee a 3 3 k“ with ka(t) given by , exp(-amt) Dxm(t) ’ 125 ai k(i) “m { rg‘ (“1" K0“)- am) 174 ex (-u t) + 2 p n k(n) n65 n (u r65 r¢n }. r k(r)-"n k(n))(am-“n k(n)) with aiO' = (l - pain“) and an = paiuil, vies. Let {Z(t)} be the continuous time semi-Markov process associated with {Zn,Tn}. The embedded chain {Zn} observed at the instants of state transitions behaves like a Markov chain. {Zn} is aperiodic, positive recurrent and irreducible and can be shown [Klei75] to possess a stationary distribution fl = ("wl’"1'°°’”wN’”N’”1"'°'”N')‘ The probability of finding the token in state 1 after the process has been operating for an arbitrarily long time is ”i’ 165*. The process {Z(t)} can be shown to exhibit a unique limdting behaviour within the chain {Zn}’ The equilibrium distribution of {Z(t)} is given by e = (¢w1’¢1'"’¢wN'¢N’¢1""'¢N')' where oj is the limiting interval transition probability of observing the token in state jeS*. This probability is different from that obtained from the chain due to the Consideration of the holding time distributions in the various states of S“. The equilibrium distribution of the server over states of s' is obtained as .lm -p(u)s(xj) + pojEUjU 395 A ej - zj E(Yj)/A . . jaw (10) ”j {qu(Xj) + qu(Yj )1 jes' A 175 with A = kgsuk{E(Yk) + [p0kE(Xk) + (l - POk)E(Vk)] + qk[E(Xk) + E(Yk )1}. Let {¢j(t) = P[Z(t) = j]} be the server's time-considered state distribution over 5., and suppose that the initial distribution {oj(0)} may not be the equilibrium distribution. By obtaining the equilibrium distribution n of the chain {Zn}, the limiting probabilities ‘j = lim ¢j(t), for jeS., may be obtained. In order to identify conditions under which this equilibrium distribution is obtained, we proceed as follows. Define the function 4 (t) H(t) = r , oj h[-1——-] (ll) :95 ej where n(y) is a strictly concave function of y, yefl+. Clearly, H(t) is a function of the server's position (over states in S.) at time t, i.e., ¢j(t), jeS.. If the initial distribution is the equilibrium distribution, then H(t) takes on a constant value. Otherwise, H(t) increases monotonically to this constant value, as shown in the next lemma [Kell79]. Lemma 8.2: If the initial distribution {¢j(o)} is not the equilibrium distribution of the process {z(t)}, then the function H(t), t > o. is strictly increasing. 176 Theorem 8.3: The equilibrium distribution {oj} of the semi-Markov process {Z(t)} is the distribution obtained by maximizing the function ¢j(t) H'(t) = Z . ¢j(t) lnl ] . 'e . j s ¢J where H*(t) corresponds to the entropy of the distribution {¢j(t)}, with respect to the equilibrium distribution. In Theorem 8.3 we see that the monotonic increase of H'(t) is a consequence of the convergence of transient distribution {¢j(t)} to the equilibrium distribution {oj}. Additionally, this theorem gives conditions under which the equilibrium probabilities pOj and plj of Lemma 8.1 can be determined, VjeS. The method involves systematic increments to probability poj*, VjQS, until probability sets 91 = {poj, jes} and a2 = {plj, jes} that maximize the entropy H*(t) are obtained. Algorithm to obtain the sets H1 and W2 step 1: Compute the mean MATP cycle time i.e., 3(0) = [ 2 E(Y ) + E(V ) 1/(1 - p + 7 ), where p = Z l E(X ) Res k k 0 0 0 RES k k and 70 Z AKE(Vk). RES step 2: Set 6 10-" where (n-l) is the number of digits of accuracy required, and set Hold = - a. step 3: Set pOj = pOj + 6, and compute plj' VjGS. step 4: Compute n and then O. Using e, compute the entropy H”. step 5: If H' < H then Hold is maximimum; stop. Otherwise, set old' 177 1' Hold - H and go to step 3. The algorithm uses pojx, jeS, as prior probabilities in order to obtain the sets H1 and B By theorem 8.3, since the probabilities in 20 these sets maximize the entropy H”, these can be used as equilibrium probabilities for empty and one-customer buffers. The convergence of the solution is dependedent on the value of n chosen in step 2; in general, it is rapid. Once these probability sets are obtained, FC (.) and FC2(.) are completely determined for the ATP process. 8.7 Stationary Distributions As in the case of FC(.), the distributions FCl(.) and FCZ(.) can be obtained as stationary distributions, given that each queue length distribution is stationary. Let us suppose that observer 2 begins to record consecutive cycle-time lengths starting at time t = 0, where without loss of generality we will assume that the token arrives at the reference station at time t = 0. Thus, observer 2 sees a sequence of cycle-time pairs (Cll’c21)’°"(Cln'C2n)"" where cin is the random time taken by the server to complete the Ci nth pair of cycles. Let poj(n) and plj(n) be the probabilities -cycle (i=1,2), in the corresponding to the empty buffer and one-customer buffer, respectively, at station j's scan instants during the Cln-cycle, for all jes. Clearly, the length of cycle Cln depends on probabilities poj(n) and plj(n). The distribution of cycle Cln can be represented as (n) - (n) , (n) , (n) , Fc1 ’ [F11 F12 ”'FlN ] G 178 where Fli(n) is used to denote the holding-time distribution of the token in state ies during cycle Cln' If F21(n) is the holding-time distribution of the token in state iGS during cycle C2”, then the distribution of C2n can be represented as (n) - (n) x (n) t (n) Fc2. “ [F21 F22 "' FZN 1' The stationary distributions observed for C1 and C2, when the ATP system is operating at steady-state, can be obtained from the limiting values of the above time-dependent distributions. Theorem 8.4: If the distribution of queue length at each queue in S is stationary, the random cycle times C1 and C2 each possess stationary distributions, given by . (n) F = llm F C1 B9. C1 (n) and F = lim F C2 n+9 C2 8.8 Summary A well known disadvantage of token-passing on a bus is the delay suffered by a heavily loaded station on a lightly loaded network. If the network is large, and the fraction of stations contributing to most of the network traffic is small, then these stations will experience a considerable amount of delay in waiting for channel access. In this 179 study, we reviewed a scheme presented earlier [ReHuBS], where such stations are given priority over the inactive (or relatively inactive) stations, with the intention of reducing their delays. The protocol that achieves this is called the adaptive token-passing (ATP) protocol. The cycle-time distributions of the the token in the two ATP cycles are derived in this section order to (i) be utilized in subsequent work for deriving performance measures of the ATP scheme, and to (ii) compare it to the standard nonadaptive token-passing (MATP) scheme. For this presentation, we restricted our attention to the situation where at most one customer is served per station at its scan instants. The cycle-time distributions are obtained for an asymmetric system under exponential assumptions. It is possible to obtain these results for symmetric systems by either using the asymmetric results themselves, or by resorting to simpler expressions that are characteristic of symmetry. The analysis shows how adaptive token-passing can be formulated as a semi-Markov process, with cycle-time distributions obtained as stationary distributions (under certain conditions) when the system is operating at steady-state. ' Certain resulting approximate distributions are currently being studied as candidates for approximate models of performance. Note that it is possible to apply the results of chapters III and Iv to obtain exact results for the ATP system. This is reserved for future work. CHAPTER IX CONCLUSIONS AND FUTURE RESEARCH In concluding the thesis, we briefly summarize the contents of each chapter and discuss the consequences of the main results. The goal of the project was a detailed study of token-passing systems with a view towards results that would be of interest to researchers in the area of performance modelling. We were specifically interested in modelling asymmetric token-passing systems in which at most one packet is transmitted by a station that is both ready to transmit and is in possession of the free token. This service discipline has been analyzed only in an approximate fashion in the past. The usual approximations involve independence assumptions [Heym83, Kueh79], borrowed-models such applications of exhaustive service models or Brlang-loss models [Buxw8l, Heym83, Kaye72] and applications of gated service models [PeAm85], or light and heavy traffic approximations [Stuc83]. In our analysis, we are require to make no assumptions other than Poisson arrivals, general distributions with finite first and second moments for service, switching, and token-passing times, and the existence of a limiting or asymptotically stationary behaviour of the system at steady state. The last assumption can be derived for arbitrary distributions possessing finite first and second moments. Consequently, for a system with given parameters, the existence (or non-existence) of well defined steady state distributions can be established as a very first step. 180 181 Ideally, a performance model should yield results that are directly amenable to practical use, either for a quantitative or a qualitative measurement of the real world system being modelled. Unfortunately, and as is often the case, the results in this dissertation do not lend themselves to algorithmic coding and testing with any ease. Most, if not all of the results, involve a number of nontrivial steps before the final measure is established. The overall process is usually a trifle tedious and time-consuming, and with increasing time also increases the possibility of human error. In this regard, much of the work is largely analytic. It is open to application in a variety of queueing phenomena that utilize service disciplines resembling the round-robin service scheme. Due to limitations in resources and time some of the experimental work was left aside in favour of the analysis. The experimental and exploratory work in the neighbourhood of this dissertation area is part of an ongoing research programme. In chapter I we introduced the basic research problem in a simple form. In the interest of clarity, we also introduced the notions of service-disciplines (or schemes) and ones (queue emptying disciplines) to describe the server's motion through the queueing network, and the number of customer's served at each queue, respectively. Note that the term service-discipline is not to be confused with the meaning of the term (i.e., FIFO, LIFO, random order) in usual queueing terminology. In the ”standard" queueing literature, servers are stationary and customer's arrive, receive service, and depart. In our systems of multi-queues, it is the server who moves, from one queue to another. 182 Hence, the term service-discipline is meant to capture server behaviour. Within queues, we always take service to be FIFO, though this can be changed. The term QED is introduced as an aid to classification of multiqueueing systems. Apparently, prior to this, such queues were treated on an individual basis. QEDs and service-disciplines link multiqueueing systems together in a manner that facilitates analysis. The literature review of closely related models (in terms of our notation) is intended to demonstrate the similarities between members of the class of multiqueueing problems, only a few of which have ever been addressed. A brief review of Markov renewal processes is presented in chapter II, mainly to introduce notation. We also take the opportunity to present a formal definition of the problem. In chapter III we introduce a key random variable, i.e., the cycle-time random variable, and proceed to outline an exact method to determine its stationary distribution. The uses of the cycle-time random variable should be clear. It is important in that it describes the length of time between server reappearances at any station. Thus, we can compute the probability that any station has to wait for upto t units of time for service. In the past, this was known only approximately, and the approximation was known to be poor for systems with many stations. Note that our Markov methods of analysis allow for a transient analysis even though we choose to stay with steady-state results. The bad side of this approach is that the size of the required Markov matrix grows exponentially with the number of station's on the 183 system being modelled. A method for avoiding this drawback is currently under investigation. On a brighter note, it is shown that one Markov matrix is all that is required to describe cycle-transitions for all stations on the system. Given one station's transition matrix, applying a simple procedure will yield another station's matrix. Consequently, we also prove some invariance properties and demonstrate insensitivity of cycle-times. In chapter Iv we take a novel approach to modelling N-station multiqueues. The method of analysis is based on work by Neuts [Meut66, Neut77] and Cinlar [Cin167] on semi-Markovian, single server queues. The semi-Markovian approach yields the following elegant solution. We focus our attention on station j and pretend this is a single-server queueing system. The cycle that begins with service of a particular station j customer is taken to be the ”service time” of this customer. There are m = 2N-1 different types of customers (differentiated through their service vectors), and these arrive at station j according to a Poisson process. A transition matrix obtained via the Markov transition matrix of chapter III describes transition probabilities between successive customer types. Viewed in this fashion, we have a modified M/SM/l queue. The modification is due to customers who arrive to find an empty queue. The notion of server vacation periods is introduced to reduce this queueing scheme into an M/SM/l queue, using PH-distributions (i.e., phase-type distributions) [Neut8l]. We use PH-distributions to model busy periods and vacation periods of the token. The final stage involves M/SM/l queueing theory to obtain an algorithmic solution for 184 steady-state distributions of packet queueing characteristics at the reference station. Thus, performance measures can be obtained for each station on the network. The measures obtained in chapter IV are restricted to the queue at station j due to conditioning. With some effort, the actual queue-length measures (i.e., moments of the distribution) may be obtained. An interesting application of this approach is the determination of the distribution of throughput, with throughput considered as a random variable defined on [O,l). Just as in chapter III, a major problem here is exponential growth of the transition matrix with increasing N. The approximate methods discussed in chapters V through VIII chronologically precede the material in chapters III and IV. Still, these methods have certain advantages over the exact methods. For example, their ease of use and the computational convenience in dealing with square matrices of size N instead of size 2". Loosely speaking, the ideas are generalizations of previous work in the area of multiqueueing, notably work by Kuehn [Kueh79], and Hashida and Ohara [HaOh72]. In chapter V, we use exponential distributions to compute asymmetric and symmetric cycle-time distributions. We introduce switching time random variables to avoid working with impulse functions. In our experimental work we found that empirical distributions computed with simulated output did not differ from a uniformly random sample subset of the simulation output. Additionally, we found that for high and low loads, the cycle-time distribution obtained via independence assumptions performs remarkably well. For moderate loads, the independence assumption performs poorly. We can only conclude that this 185 is due to serial cycle-time depencencies that arise in a wide range of moderate loads. Again the problem of computational complexity arises. With regard to cycle-time densities, asymmetric systems require computational algorithms of exponential complexity, while symmetric systems require computational algorithms of polynomial complexity. In chapter VI, we introduce approximate methods to address the problem of serial dependence. Just as in chapter IV, this chapter deals with methods of obtaining queueing distributions. Since the i.i.d cycle-time assumption of Hashida and Ohara neglected covariance information, and the methods of Kuehn (mixing two kinds of cycle-times) which took into account two non i.d cycle-times proved to be superior to the Hashida/Ohara results, we decided to attack the covariance problem. Two methods for covariance function approximation, and a method for determining marginal cycle-time distributions (based on the original cycle-time distributions) are outlined. In choosing a linear combination of dependent cycle-times to construct a quasi-service time random variable, we demonstrate an application of principle component analysis. The quasi-service time random variable so constructed is guaranteed to possess maximum variability. Thus, the quasi-service time random variable may either be used in the Hashida/Ohara sense, or in the Kuehn sense. In either case, due to consideration of covariance, we are certain to obtain better results. In chapter VII, we discuss the stability of token-passing systems. Two notions of stability are presented. In the SV queueing sense, the stability criterion (as stated in Chapter IV) is a function of customer transition probabilities, mean arrival rates, and mean service times. 186 In the SP queueing sense, the stability criterion is a function of mean arrival rates and mean conditional cycle-times. Interestingly enough, both criteria are based on embedded Markov chains, where the SV chain is obtained via conditioning and the SP chain is obtained via the independence hypothesis. A study of the stability criterion in N dimensions allows us to define simple measures of system stability. The use of conditional cycle-times is carried one step further in defining a flexible fairness measure. The flexibility arises in our ability to change the weights involved in the measure, thereby giving the particular aspect of the measure that we are more interested in a correspondingly heavier weight. In this sense, we can change the measure to suit our purpose. Another result of this section is one that is very useful for conditions of extreme load. This is based on work by Renyi [Reny56] on rarefactions and determines the random time between two consecutive transmissions by a given station. In chapter VIII, we introduce a complex service discipline with the intention of deriving cycle-time distributions. This discipline is applicable to token-passing bus networks. Consider an asymmetric system with N stations, N very large (i.e., of the order 102). Examine the effects obtained if a few stations are continuously active and generate a large proportion of the total load on the network. For example, 5% of the stations on the system generate 90% of the total (transmission) load, while the remaining 95% are relatively inactive. This example illustrates the well-known disadvantage of token-passing for either high asymmetric station loads or low average loads, with the token spending a good deal of time in fruitless token-passes [Stalad]. 187 In order to analyze the complex service scheme, we require the distributions of the two cycle-time random variables involved. With the aid of these, the server's interarrival time distribution may be derived. As an approximate solution, we use the entropy approach [Kell79] in obtaining the limiting probabilities of certain queue states. This finally allows for the determination of the distribution of the server's interarrival time, Tj, at station j. The conditions under which this simple adaptive token-passing scheme performs better than a corresponding standard token-passing scheme are simple to derive. If we keep a given system fixed and change only the OED we obtain a new queueing problem. Similarly, if we change only the service discipline, we obtain yet another queueing problem. Thus, there is a rich class of strongly linked queueing problems that has not surfaced in the literature in any structured form. In this regard, there is more than ample scope for future research in this area. It may well turn out that a single method of analysis is applicable to a host of QEDs simultaneously. Such a result is not known at the present time. Some of the problems open for future research can be described as: (l) Generalizing solutions to accomodate related ones such as s-Qin a n, n > 1, finite queue capacity, relaxed disciplines, more complex disciplines etc. (2) Multiqueueing configurations with more than one server and a variety of QEDs. (3) Multiqueueing systems with time-varying arrival rates or randomly varying arrival parameters. 188 (4) Multiqueueing systems with arbitrary distributions for arrival, service, walk, and switching. (5) Asymptotic analysis of multiqueueing problems. (6) Distribution of the Fairness statistic. (7) Computational algorithms. The researCh areas outlined by no means exhaust the variety of interesting multiqueueing problems available. The topic in (7) is important for practical applications but is probably also extremely difficult. In fact, all of the topics mentioned above are challenging research problems. From our work, it is clear that one inherent problem of asymmetric multiqueues is the high degree of computational complexity. In this regard, the topic in (5) will provide valuable insight into the effects of increasing N. With an understanding of asymptotic behaviour, we can attempt to work around the problem of computation. , APPENDIX APPENDIX Proof for Lemma 3.1: Without loss of generality, we first work with stations 1 and 2. I Consider any transition of the form 2 * z in P1, where z = <21, .., ZN) l t and z = <21 , .., ZN >. By Eq.(S) of chapter III, the probability of this transition, i.e., p(z,z ), can be written as a product of conditional probabilities, one from each station. Denote these 0 I I probabilities as ‘1‘21 |zi, .. , zi ) where i = l,..,N and 20 = N. -1 For ease of notation we write station 1 s conditional probability simply as £1, unless specific mention of the condition is required. At steady state, given that an observer at station l's scan point sees a transition 9 <2 , .. , ZN > occur, another observer at 1’ " N 1 station 2's scan point must see a transition of the form <22, .. , z , 21 > * <22 , .. , ZN , x>. The x is meant to indicate that the original transition does not yield sufficient information to determine this entry. Recalling Eq.(S), we see that (N-l) out of the N conditional probabilities that go to make the probability p(z,z') in ’1 will also be present in the partial (due to absence of a specific x) transition probability seen from station 2. Since 21 is merely a descriptor for events at station 1, substitute 21 in place of x for station 2's transition. Then, station 2's transition tuple is obtained as the first and second set of N bits in , where w is defined in Eq.(l) of chapter III. 0 Let H(z,z ) denote a transition from a starting state (first N 189 190 bits) to a target state (second N bits), seen from station 2's scan point. Let p(H(z,z )) denote the probability of this transition in 92 as seen by the observer at station 2. Then this probability can be obtained as p(h(z,z')) = [ s2£3....sN ]*[£l(z')/£l(z)] where all the probabilities on the right hand side are defined. In particular, £l(z) describes the conditional probability £l(zl|z) and I I I £l(z ) describes the conditional probability ‘1‘21 |z ). Repeating this I procedure for every transition pair (z,z ) in P will yield the entire 1 transition probability matrix P2. Observe that the rows (and columns) of P2 will not be in the same order as the rows (and columns) of P1. In general, to obtain P from Pj, k = j mod N + 1, assuming that k I p(z,z ) describes a transition probability in Pj, the transformation r3 applied to each entry of pj is formally described as j I = I I I l r (2,2 ) [p(u(z.z )>] [£j(zj|zj .....zj_l)/£j(zj lzj....,z )1. j-l Extending the above idea, it is easy to show that the probability matrix viewed with respect to station k's scan-cycle can be obtained for any station k. Observe that N repetitions of the transformation on ’1 will yield Pl with rows and columns transposed, and 2N repitions will yield the original Pl. 191 Proof for Lane 3.2: If the observer is positioned to witness scan-cycles at station j, then the service vector obtained from the server is of the form ' Similarly, for scan-cycles seen at station k, the service vector obtained is . If the observer is positioned to witness dep-cycles at station j, then the first and last entries of the service vector must correspond to service events at stations k and j, respectively. Hence, this service vector must be of the form , and this is precisely the vector seen at or before station k's scan point. Furthermore, since the probability transitions for service vectors are not dependent on scan instants (as in [Kueh79]), we have that for all jeS, Pk(s) = Pj(d). Proof for theore-3.3: Let {“1} be the invariant vector obtained from the Markov transition matrix Pj. The elements of this vector are 2" probabilities corresponding to limiting state probabilities for the 2" different service vectors. Thus, the invariant vector is a vector of probabilities corresponding to states that are vectors (i.e., service vectors) in themselves. For each 269, let tjz be the steady-state probability that the observer at station j receives vector 2 from the SONG! e 192 Let z = , and define an operator R on elements of 6 such that R(zj,..,zN,..,zj_l) = (zj+l,..,zN,..,zj). In other words, R treats each element of 9 as an N-bit computer word and performs an end-around left shift. The bit that falls off the left edge is made to occupy the (vacated) righhmost bit position. From Lemma 3.1, we see that the transition matrix for any station will yield an invariant probability vector which, when suitably transformed, becomes the invariant vector for a neighbouring station. For each service vector 2 seen on a scan-cycle at station j, yes, it is easy to see that ”32 = ”Ram where k = j mod N + 1. Thus, given the invariant service vector distribution with respect to scan-cycles for any one station, it is possible to obtain the invariant service vector distribution with respect to scan-cycles for any other station. If station j sees a scan-cycle vector 2 (in the steady-state of the system) with probability :rjz, 299, then station 1: sees a different vector 8(2) with precisely the same probability. Since the vectors 2 and R(z) both generate the same cycle-time random variable (see Eq.(8) in chapter III), the mixture distribution obtained in Eq.(9) will be the same for both stations. That is, station j and station k see the same cycle-time random variable. By replacing indices, this can be shown to hold for every pair of stations j and k, for j,k€S. 193 Proof for Theorem 5.1: Consider a sequence of transient cycles witnessed by our observer at station j from the instant the system begins to operate. Without loss of generality we assume that the system begins at T = O, with O 20 = j, and that cycles are measured with respect to scan instants at station j. Let Ci be the it” cycle from the start of the process, 161+. Let pj(i) be the probability that the server finds at least one customer awaiting service at station j at its Ci scan instant, and qj(l) = 1 _ pj(l)' Let em be the mean of the first m terms in the cycle sequence. Since cm is a consistent estimate of the true cycle mean 3(0), we have lim P[|e - E(C)| s e] = 1, for all e > 0. ma m Next, consider the observer's view of the system after it has been operating for an arbitrarily long time. By hypothesis, all queueing distributions are stationary and consequently stable. Since the observer sees an H/G/l queueing system at station 1, it follows that what cm converges to is precisely the mean E(C) of the 6 distribution. Prom MIG/l theory we have that Iii qj(1) = qj always exists and is independent of a customer's virtual waiting time at the instant t = O [Taka62]. That is, 1: lim (l/k) z 9-”) =q k». i=0 3 j 194 and pj = l - qj. Consequently, for each jes we obtain weak convergence (k) of the distributions Fj , i.e., lim F.(k) = p.B. + q.S. ., jes. kg, 3 J 3 J J 3 II ~13 Given the weak convergence, we can interchange the operations of convolution and limit to obtain the theorem. Proof for Corollary 7.1: If E(Sl) < a , then D t 2 5(31 I s k=1 k 1 8(51 ) I 'U (I) N \r 'U A U) H I 'U (I) N \v ' k-l 2 E(S ) q. p. k=1 k 3 3 I ['1 A (I) H \v "U which is equal to 3(31). On the other hand, since 3(51') 2 ij(Sl), we have that 2(51‘) = a if 3(51) = a. That the result holds for all integers k > 1 follows from the fact that both processes are renewal processes. Proof for Lemma 8.1: By assumption of Poisson arrivals, the queueing process at station j is an M/G/l queue. The queue length states of queue j viewed at its 195 discrete set J of scan instants in the Cl-cycle forms an embedded Markov chain {L(t), tGJ}. Define pnj = P[L(t) = n], for all tGJ, ne1+, jes. By hypothesis, {L(t)} is stationary. Prom M/G/l theory [K1ei75], it follows that poj = 1 - le(cl), for all 365. Similarly, the M/G/l queue formed by customers at station j with service distribution FCZ yields poj + plj = 1 - le(c2). for all jes. Consequently, plj The inequality poj't 2 p0 is obtained in the analysis [Eq.(lc), Chapter = xj{E(cl) - E(C2)} for all jes. III]. The fact that expectations E(Cl) and E(C2) are finite follows from our assumption that all distributions in section II possess finite first moments. Hence C1 and C2 are random variables with stable means. The corresponding proof for the NATP case can be found in [ReN184]. Finally, the proof that plj can be obtained as a function of pOj and v may be found in section 6.5. This is acquired as a consequence of Oj obtaining the queue length distribution (as a performance measure). Proof for Lemma 3.2: Consider the semi-Markov process {Z(t)}. For some fixed 6 2 0, define pjk' = P(Z(t + a) = x | Z(t) = j) = p(zn+l = k, Tn+l - Tn < 5 | zn = j) = p(zn+l = x | zn = i)P(Tn+l - Tn < a | zn+l = t, 2n = 1) Q 196 where H1j(t) is the conditional transition time distribution function defined in Eq.(4), and {Zn} is the Markov chain of queue length states at station j obtained via embedding. Let oj(t) = P(Z(t)=j). It follows that ¢k(t + a) = z . ¢j(t)pjk jes z ¢.(t)p H. (5) jes' J jk 3k and ‘k = lim ¢k(t) = 11m 2 , ¢j(t)pjk' t*0 t*0 jes 2 e p. H (5). jes' 1 JR 1k Let bkj = ejpjk/ek. Consequently, bk' 3 > O, and 2 b J kj = 1' ¢k(t + a)/¢k z . ¢j(t)pjk /¢k jGS jgs. ¢j(t)ij(5)/¢j z z b .o.(t)/¢. jes' k: 3 3 We thus obtain, H(t + a) z . okn[¢j(t + 5)/¢k] jes a z o h[ z b .¢.(t)/¢.]. jes' k kes' k3 3 3 Since h(y) is a strictly increasing, concave function of y, H(t + a) > z z e b .h[¢.(t)/¢.J jes' kes' k *3 3 3 197 jés' kgs. ¢jpjkht¢j(t)/¢j] H(t). Thus, H(t) is a strictly increasing function of t, achieving a maximum H = lim H(t) lim 2 z ¢.p. h[ ¢.(t)/¢.] t+e t+¢ j€S* kGS. 3 3k 3 3 2 Z I-P h(l). jes* xes' 3 3* Proof for Theorem 8.3: Let the concave function h(y) [see Lemma 8.2] be defined as h(y) = (-y) ln(Y). By Lemma 8.2, H(t) = - jgs. ¢j(t) ln[¢j(t)/¢j] is a strictly increasing function, and takes on its maximum at H'(t) = lim - z , ejln(l) t+e jes = o. The monotonic increase of H'(t) is a consequence of the convergence of the transient distribution {¢j(t)}. tea*, to the equilibrium distribution ¢ of the process {Z(t)}. 198 Proof for Theorem 8.4: Let poj(i), plj(i), and qj(i) be the probabilities that the server encounters zero, one, or more than one waiting customer at station j, respectively, at the scan instant of this station during the C11 cycle, Vjes, VieI+. The token's holding-time distribution at station j has the representation F (i) (i) (i) J' 3' I and at station j has the representation (1) (i) ' F . = . B. 23 q: 3 By hypothesis, the queue length distribution at each queue in S is , Vjes, 161+. stationary. It follows that after an infinite number of cycles, the ATP system must reach a steady state, in which (1) lim p = p , 1' 0k 0k . (i) llm p - p , 1| 1k lk and lim qk(i) = qk, vxes, i-Oa where pOK’ plk’ and q1: are the stationary probabilities for queue res. We thus obtain (1) lim F = F tF I...*F *6, and il Cl 11 12 IN lim F (i) = F tr a 2F Vjes 1' C2 21 22 '°° ZN' ' Hence, C11 and C21 converge to Cl and C2 in distribution. LIST 01' REFERENCES ”J! .in u...-..-n-- ‘5 [Abra70] [Abst64] [AlOb82] [AndeSB] [AnSc82] [ArNT78] [ArSt82] [BCJKBZ] [Buowl] [Buxw84] [ChLL82] REFERENCES N. Abramson, " The ALOHA System-Another Alternative for Computer Communications,” Proceedings, Fall Joint Computer Conference, l970. M. Abramowitz and I. Stegun, eds., Handbook Of Mathematical Functions, u.s. Department of Commerce, National Bureau of Standards, Washington, D.C., 1964. M. Ali and M. Obaidullah, ”Distribution of linear combination of exponential variates," Commun. Statist.-Tneor. Nethods, 11(13), pp. 1453-1463, 1982. T. Anderson, An Introduction To Multivariate Statistical Analysis, John Wiley 8 Sons, Inc., N.Y., 1958. D. Andrews and G. Schulz, ”A Token-Ring Architecture for Local Area Networks: An Update, " CONPCON Fall 1982, 1388, 1982. B. Arjas, B. Nummelin, and R. Tweedie, ”Uniform Limit theorems for nonsingular renewal and Markov renewal processes,” J. Appl. Prob., Vol. 15, pp. 112-125, 1978. B. Arthurs and B. W. Stuck, ”A Theoretical Performance Analysis of Polling and Carrier Sense Collision Detection Communication Systems,” Proceedings of the IFIP TC 6 International ln-Deptn Symposium on Local Computer Networks, Florence, Italy, pp. 415-437, l9-21 April, 1982. W. Bux, P. Closs, P. Janson, K. Kummerle, H. Miller, and a. Rothauser, "A Local-Area Communication network Based on a Reliable Token Ring System, ' Proceedings, Intl. symp. on Local Computer Networks, 1982. W. Bux, ”Local-area subnetworks: a performance comparison,” IEEE Trans. Commun., pp. 1465-1473, Oct. 1981. W. Bux, ”Performance issues in local-area networks," IBM Journal, Vol. 23, We. 4, l984. R. Cherukuri, L. Li, and L. Louis, ”Evaluation of Token Passing Schemes in Local Area Networks,” Computer Networking SYmposium, IEEE Computer Society and N.B.S, Gaithersburg, MD, December 10, 1982. 199 [Cin167] [Cin169] [CoBo72] [COBOBB] [CoLe66] [ConoBl] [Coxd62] [CrCG79] [Doug63] [ECMA83a] [smash] [Eise72] [Eise79] [Fabe6l] [PaNe69] 200 E. Cinlar,”Time dependence of queues with semi-Markovian services,” J. Appl. Prob., Vol. 4, pp. 356-364, 1967. —————————, "Markov renewal theorY." Advances in Applied Prone, Vel' ppe 123-187' 19690 S. Conte and C. de Boer, Elementary Numerical Analysis, McGraw Hill, N.Y., 1972. J. Cohen and O. Boxma, Boundary Value Problems in Queueing System Analysis, Amsterdam, The Netherlands: North Holland, 1983. D. R. Cox and P. Lewis, The Statistical Analysis Of Series Of Events, Methuen, London, 1966. B. Conolly, Techniques In Operational Research, Volumez: Models, Search and Randomization, Ellis Horwood Limited, Chichester, WS, England, 1981. D. R. Cox, RENEWAL THEORY, Methuen, London, 1962. M. Cromie, M. Chaudhry, and W. Grassmann, ”Further results for the queueing system Mx/M/c,” J. Oper. Res. SOCe I V01. 3' We 755-763, 1979e J. Douglas, ”Asymptotic expansion for some contagious distributions,” Proceedings of the International Symposium on Discrete Distributions, Montreal, pp. 291-302, 1963. Standard ECMA-BQ: Local Area Networks Token Ring, September 1983. Standard BCMA-QO: Local Area Networks Token Bus (Broadband), September 1983. M. Eisenberg, ”Queues With Periodic Service and Changeover Times," Oper. Res., 20, No.2, pp. 440-451, March-April 1972. M. Eisenberg, ”Two Queues with Alternating Service,” SIAM J. Appl. Math., 36, No.2, pp. 287-303, April 1979. A. J. Pabens, ”The solution of Queueing _and Inventory Models by Semi-Markov Processes,” J. Royal. Stat. Soc., Ser. B., Vol. 23, pp. 113-127, pp. 455-456, 1961. W: Farmer and E. Newhall, ”An Experimental Distributed Switching System to Handle Bursty Computer Traffic,” Proceedings, ACM Symposium on Problems in the Optimization of Data Communications, 1969. [FeAmBS] [Fe1166] [Fe1168] [FinCSQ] [GeSt80] [Giff78] [Ha0h72] [HaShBl] [ReffBO] [Henr64] [BeSoBZ] [Heym83] [MoPS72] [IEEE84a] 201 M. Ferguson and Y. Aminetzah, "Exact. Results for Nonsymmetric Token Ring Systems,” IEEE Trans. Commun., March 1985. w. Feller, An Introduction to Probability Theory and Its Applications, Vol. II, Wiley (New York), 1966. , An Introduction to Probability Theory and Its Applications, Vol. I, third edition, Wiley, N.Y., 1968. P. Finch, ”The Output Process of the Queueing System M/G/l,” J. Royal. Stat. Soc., Ser. B, Vol. 21, pp. 375-380, 1959. M. Gerla and M. Staskaukas, ”Fairness in flow controlled networks,” ICC, Denver, B.S.A, June 1980. W. Giffin, Queueing: Basic Theory And Applications, Grid Inc., Columbus, Ohio, 1978. O. Mashida and K. Ohara, ”Line Accomodation Capacity of a Communication Control Unit,” ReView of the Electr. Comm. Laboratories, Nippon Telegraph and Telephone Public Corporation, 20, pp. 231-239, 1972. V. Carl Hamacher and G. Shedler, ”Collision-Free Local Area Bus Network Performance Analysis,” IBM J. Res. Develop., v.25, No.6, pp. 904-914, November 1981. N. Neffes, ”A Class of Data Traffic Processes- Covariance Function Characterization and Related Queueing Results,” B.S.T.J., 59, No.6, pp. 897-929, July 1978. P. Henrici, Elements Of Numerical Analysis, Wiley, N.Y., 1964. D. P. Neyman and M. Sobel, Stochastic Models In Operations Research, Volume I: Stochastic Processes and Operating Characteristics, McGraw Hill, N.Y., 1982. D. P. Beyman, ”Data-Transport Performance Analysis of Fasnet,” B.S.T.J., 62, No.8, pp. 2547-2560, October 1983. P. G. Noel, s. C. Port, and C. J. Stone, INTRODUCTION TO STOCHASTIC PROCESSES, Houghton Mifflin Co., Boston, 1972. IEEE Project 802 Local Area Network Standards, Draft IEEE 802.5, Token Ring Access Method and Physical Layer Specifications, 1984. [IEEEB4b] [Jage78] [Jage84] [JoKo77] [Kaye72] [Kell79] [KeSn60] [K1ei75] [R1To75] [KoMe74] [Konh76] [Kueh79] ,[Lams80] [Levy54] [Lieb61] 202 1888 Standard 802.4, Token Passing Bus Access Method and Physical Layer Specifications, 1984. D. Jagerman, ”An Inversion Technique for the Laplace Transform with Application to Approximation,” B.S.T.J., 57, No.3, pp. 669-710, March, 1978. , Calculation of Laplace transforms, in preparation, 1984. N. L. Johnson and S. Kotz, Urn Models and Their Application: An Approach to Modern Discrete Probability Theory, John Wiley & Sons, 1977. A. R. Kaye, ”Analysis of a Distributed Control Loop for Data Transmdssions,” P.I.B International Symposium XXII on Computer Communications and Teletraffic, April 4-6, 1972. F. Kelly, Reversibility and Stochastic NGtWOI'kS, John ‘ Wiley ‘ sons Ltde' NeYe' 1979e J. Kememy and J. Snell, Finite Markov Chains, D. Van Nostrand Company, Inc., Princeton, N.J., 1960. L. Kleinrock, QUEUEING SYSTEMS, Volume 1: Theory, Wiley-Interscience, N.Y. 1975. L. Kleinrock and F. Tobagi, ”Packet Switching in Radio Channels: Part I: Carrier-Sense Multiple-Access Modes and Their Throughput-Delay Characteristics,” IEEE Trans. Commun., Dec 1975. A. G. Konheim and B. Meister, ”Waiting Lines and Times in a System with Polling," J.A.C.M., 21, No.3, pp. 470-490, July 1974. A. G. Konheim, "Chaining in a Loop System,” 1888 Trans. Commun., Vol. 24, No.2, pp. 203-210, February 1976. P. J. Nuehn, ”Multiqueue Systems with Nonexhaustive Cyclic Service,” B.S.T.J., 58, No.3, pp. 671-698, March 1979. S. Lam, ”A carrier sense multiple access protocol for local networks,” Computer Networks, Vol. 4, 21-32, 1980. P. Levy, ”Processes semi-Markoviens,” Proceedings of the Int. Congr. Math., (Amsterdam), 3, pp. 416-426, 1954. M. A. Liebowitz, ”An Approximate Method for Treating a Class of Multiqueue Problems,” IBM Journal, 5, pp. [Lieb68] [LiF182] [LiHGBZ] [Loyn62a] [Loyn62b] [MaGe82] [Mack57] [MaMW57] [Math83] [wcnoas] [MeBo76] [MeBTC77] 203 204-209, July 1961. , ”Queues," Scientific American, 219, pp. 96-103, 1968. J. O. Limb and C. Flores, ”Description of Fasnet-A Unidirectional Local-Area Communications Network,” B.S.T.J., 61, No. 7, pp. 1413-1440, September 1982. M. T. Liu, W. Hilal, and B. H. Groomes, ”Performance Evaluation of Channel Access Protocols for Local Computer Networks,” Proceedings, COMPCON 82 Fall, pp. 417-426, 1982. R. Loynes, ”Stationary waiting time distribution for single-server queues,” Ann. Math. Statist., Vol. 33, pp. 1323-1339, 1962. ———————-—, ”The stability of a queue with non-independent arrival and service times, Proc. Camb. Phil. Soc., Vol. 58' We ‘97-520' 1962e M. A. Marsan and M. Gerla, ”Fairness in Computer Networks," NATO Research Report, Instituto di Elettronica, Politecnico di Torino, Torino, Italy, February 1982. C. Mack, ”The Efficiency of N Machines Uni-Directionally Patrolled By One Operative When Walking Time Is Constant And Repair Times Are Variable,” J. Royal Stat. Soc., Ser. B, Vol. 19, pp. 173-178, 1957. C. Mack, T. Murphy, and N. Webb, "The Efficiency of N Machines Uni-Directionally Patrolled By One Operative When Walking Time And Repair Times Are Constants,” J. Royal Stat. Soc., Ser. B, Vol. 19, pp. 166-172, 1957. A. M. Mathai, ”On Linear Combinations of Independent Exponential Variables,” Commun. Statist.-Theor. Methods, 12(6). PP- 625-632, 1983. D. McDonald, ”An Invariance Principle For Semi-Markov Processes," Adv. Appl. Prob., Vol. 17, pp. 100-126, 1985. R. Metcalfe and D. Boggs, ”Ethernet: Distributed Packet Switching for Local Computer Networks,” CACM, July, 1976. R. Metcalfe, D. Boggs, C. Thacker and B. Lampson, "Multipoint Data Communication System with Collision Detection,” U.S. Patent, 4,063,220, 1977. [Neut66] [Neut74] [Neut77] [Neut79] [Neut81] [Neut85] [Pear66] [Pear67] [PeBa79] [PYke61a] [PYke61b] [ReHu85] [ReN184] 204 M. F. Neuts, ”The single server queue with Poisson input and semi-Markov service times,” J. Appl. Prob., Vol. 3, pp. 202-230, 1966. ,"The Markov renewal branching process,” Mathematical Methods in Queueing Theory: Lecture Notes In Economics and Mathematical Systems, eds., M. Beckman et. al., Operations Research, Vol. 98, pp. 1-21, Springer-Verlag, N.Y., 1974. , "Some explicit formulas for the steady-state behaviour of the queue with semi-Markovian service times,” Adv. Appl. Prob., Vol. 9, pp. 141-157, 1977. , "A versatile Markovian point process," J. Appl. Prob., Vol. 16, pp.764-769, 1979. , Matrix-Geometric Solutions in Stochastic Models, The Johns Hopkins University Press, Baltimore, 1981. , Structured Stochastic Matrices of M/G/l Type and their Applications, in preparation. C. Pearce, ”A queueing system with general moving average input and negative exponential service time,” J. Aust. Math. Soc., Vol. 6, pp. 223-236, 1966. --—————, ”Queues with moving average service times,” J. Appl. Prob., Vol. 4, pp. 553-570, 1967. B. Penney and A. Baghdadi, ”Survey of computer communication loop networks: Parts 1 and 2,” Computer Communications 2, 165-180 and 224 -241, 1979. R. Pyke, ”Markov Renewal Processes: Definitions and preliminary properties,” Ann. Math. Statist., Vol. 32, we 1231-12‘2' 1961e R. Pyke, ”Markov Renewal Processes with Finitely Many States," Ann. Math. Statist., V01. 32, pp. 1243-1259, 1961. V. Rego and N. Hughes, ”Modelling An Adaptive Token-Passing Protocol," Technical Report, Dept. of Computer Science, Michigan State University, 1985. V. J. Rego and L. M. Ni, "Performance Modelling of Token-Passing Protocols,” Technical Report, Dept. of Computer Science, Michigan State University, 1984. [Reny56] [RuTa77] [SmitSS] [Spri79] [Sta184] [Stuc83] [Swar77] [Swar80] [Swar81] [TakaGZ] [Toba74] [ToHuBO] [WUCh75] 205 A. Renyi, ”A Characterization of the Poisson process," Magyar Tud. Akad. Mat. Kutato Int. Kozl., v.1, pp. 519-527 (in Hungarian). (Translated into English in Selected Papers of Alfred Renyi, Vol. 1, Akademiaj Riado, Budapest, 1976). A. Russell and R. Taylor, ”Numerical sanalygis and relationships for the queueing models M/Es k/l, E /M/1," Unpublished thesis, Royal Military College of Eanada, Kingston, Ontario, 1977. W. L. Smith, ”Regenerative Stochastic Processes,” Proceedings of the Roy. Soc. London, Ser. A, 232, pp. 6-31, 1965. M. D. Springer, The Algebra of Random Variables, John Wiley s Sons, New York, 1979. W. Stallings, "Local Network Performance,” 1888 Communications Magazine, pp. 27-36, February 1984. B. Stuck, ”Calculating the maximum mean data rate in local area networks," Computer, pp. 72-76, May 1983. G. Boyd Swartz, ”Polling With Unequal Arrival Rates," Doctoral Disseration at New York U., 1977. , ”Polling in a Loop System,” J.A.C.M , 27, No.1, pp. 42-59, January 1980. , "Analysis Of A Scan Service Policy In A Gated Loop System,” Applied Probability -Computer Science: The Interface, Volume II, eds., R. L. Disney, T. J. Ott, Institute Of Management Sciences, Florida Atlantic Univ., Boca Raton, Florida, pp. 241-252, January 1981. Lajos Takacs, Introduction to the Theory of Queues, Oxford University Press, Inc., 1962. F. A. Tobagi, ”Random Access Techniques for Data Transmission over Packet Switched Radio Networks," Ph.D. thesis, Computer Science Dept., UCLA, 1974. F. Tobagi and V. Hunt, ”Performance Analysis of Carrier Sense Multiple Access with Collision Detection,” Computer Networks, Oct/Nov 1980. R. M. Wu and Y. B. Chen, "Analysis of a Loop Transmission System with Round-Robin Scheduling of Services,” IBM J. Res. Develop., pp. 486-493, September 1975. 206 [Zimm80] H. Zimmerman, "051 Reference Model-The ISO Model of Architecture for Open Systems Interconnection," IEEE Trans. Commun., Vol. COM-28, pp. 425-432, April 1980.