MEAN DELAY ANALYSIS FOR UNIDIRECTIONAL BROADCAST STRUCTURES by JOSEPH WAI MING PANG B.A.Sc, The University of B r i t i s h Columbia, ]983 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE i n THE FACULTY OF GRADUATE STUDIES Department of E l e c t r i c a l Engineering We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA © Joseph Wai Ming Pang, 1985 In presenting t h i s thesis i n p a r t i a l f u l f i l m e n t of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t f r e e l y available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of E l b f T r l l C A l „ H ^ l ^ ^ l A ^ The University of B r i t i s h Columbia 1956 Main Mall Vancouver, Canada V6T 1Y3 Date Abstract U n i d i r e c t i o n a l broadcast structures constitute a c l a s s of high performance l o c a l network a r c h i t e c t u r e s . They are very f l e x i b l e and well suited f o r f i b e r optic implementation. The access methods used i n these networks are often based on c e r t a i n i m p l i c i t token-passing mechanisms to provide superior delay-vs-throughput c h a r a c t e r i s t i c s . The performance of these u n i d i r e c t i o n a l broadcast protocols i s evaluated i n t h i s thesis v i a a study on the c l a s s i c a l token-ring system. Emphasis i s placed on the analysis of mean delay-vs-throughput performance for the gated exhaustive service d i s c i p l i n e under asymmetric t r a f f i c . The analysis involves examination of the s t a t i s t i c a l behaviour of i n t e r a c t i n g queues. A number of exact r e s u l t s are derived and based on these r e s u l t s , a very good approximation for the average delays i s developed. The approximation agrees c l o s e l y with exact numerical solutions over a wide range of system parameters. The implications of the approximation are also discussed. i i TABLE OF CONTENTS Page 1. INTRODUCTION 1 1.1 High-performance Local Area Networks 1 1.2 Objectives 2 1.3 Previous Work 3 1.4 Outline 4 2. DEVELOPMENT OF THE LAN SYSTEM MODEL • ... 6 2.1 Description of D-net and Its Communication Protocol 6 2.2 Comparison of D-net with Token-Ring Systems 10 2.3 System Model and Parameters 11 2.4 D e f i n i t i o n s of System Random Variables 15 2.5 Comments on the Relations between System Random Variables.... 17 3. FORMULATION OF THE SYSTEM EQUATIONS 19 3.1 Imbedded Markov Chain Formulation 19 3.2 Moment Calculations 22 3.3 Approaches to the Solutions of the Basic Equations 23 3.4 Existence and Uniqueness of Solutions to the Basic Equations 24 3.5 Comments Regarding Solutions of the Basic Equations 26 i i i TABLE OF CONTENTS (cont'd) Page 4. SOME EXACT ANALYTIC RESULTS 28 4.1 Overview of Results 28 4.2 Expected Cycle Time , 28 4.3 S i m p l i f i c a t i o n of the Forcing Matrix B 31 4.4 The Jacobian Matrix A 33 4.5 An A u x i l l i a r y Result 35 4.6 A Difference Equation for the Second Joint Moments of Terminal Service Times 37 4.7 Solution for the Symmetric Case 45 5. MEAN DELAY ANALYSIS 47 5.1 Relationship between Mean Message Delays and Service Time Moments 47 5.2 A Fundamental Relation for {v^ } 50 5.3 An Approximation for ( v i i } 52 5.4 Comments on the Approximation for {v^ } 54 5.5 Comparison of Approximation and Exact Numerical Results for {v^ } 56 5.6 Delay-vs-Throughput Results 65 5.7 F i n i t e Buffering and Non-exhaustive Services 7 9 iv TABLE OF CONTENTS (cont 'd ) Page 6. CONCLUDING REMARKS 8 2 6.1 Summary of the Results 8 2 6.2 Suggestions for Further Work .' 8 3 REFERENCES 86 APPENDIX: Eigenvalues of the Jacobian Matrix A 89 v LIST OF FIGURES Page 2.1 Architecture of D-net 7 2.2 Trains of Packets on D-net 7 2.3 The Star-coupled Version of D-net 9 2.4 The Open-ring Version of D-net 9 2.5 Schematics for the Single-server Multi-queue Model 12 5.1a E versus p for N=8 and 1 sing l e large user 5 9 max 5.1b E versus p for N=8 and 1 sing l e large user 5 9 avg 5.2a E versus p for N=8 and 1 sing l e small user 60 max K 5.2b E versus p for N=8 and 1 sing l e small user 60 avg 5.3a E versus p for N=8 and 2 c l u s t e r s of i d e n t i c a l users 61 max 5.3b E versus p for N=8 and 2 c l u s t e r s of i d e n t i c a l users 61 avg 5.4a E versus p for N=16 and 1 s i n g l e large user 62 max 5.4b E versus p for N=16 and 1 sing l e large user 62 avg 5.5a E versus p for N=16 and 1 s i n g l e small user 63 max r ° 5.5b E versus p for N=16 and 1 single small user 63 avg 5.6a E versus p for N=16 and 2 c l u s t e r s of i d e n t i c a l users 64 max 5.6b E versus p for N=16 and 2 c l u s t e r s of i d e n t i c a l users 64 avg 5.7a v ^ versus p for N=8, 1 sing l e large user and t ^ P j 2 7 0 5.7 b v a r ( v i ; l ) versus p for N=8, 1 single large user and ti=P^2' • • • 7 0 5.8a V J J versus p for N=8, 1 single large user and t ^ P ^ 7 1 5.8b var(v ) versus p for N=8, 1 single large user and ^i=Pi 7 1 5.9a v ± versus p for N=8, 1 sing l e large user and t ^ l 7 2 5.9b var(v ) versus p for N=8, 1 sing l e large user and t ^ l 7 2 v i LIST OF FIGURES (cont'd) Page 5. 10a versus p for N=8, 1 si n g l e small user and t^ = p. 2 7 3 5. 10b v a r ( v ^ ) versus p for N=8, 1 si n g l e small user and C i = P i 2 7 3 5. 11a v.. versus p for N=8, 1 single small user and t^=p^ 74 5. l i b v a r ( v ^ ) versus p for N=8, 1 si n g l e small user and 74 5. 12a v.. versus p for i i N=8, 1 si n g l e small user and t^ = l . 75 5. 12b var(v..) versus n p for N=8, 1 si n g l e small user and t . - l . l 75 5. 13a v.. versus p for l i N=8, 2 c l u s t e r s of i d e n t i c a l users and 76 5. 13b >-s/ var(v..) versus i i p for N=8, 2 c l u s t e r s of I d e n t i c a l users and t - o 2 76 zi p i 5. 14a. v.. versus p for i i N=8, 2 c l u s t e r s of i d e n t i c a l users and 77 5. 14b varfv..) versus i i p for N=8, 2 c l u s t e r s of i d e n t i c a l users and 77 1 P l 5. 15a v.. versus p for N=8, 2 c l u s t e r s of i d e n t i c a l users and t . - l . 78 i i l 5. 15b va r f V j . ) versus i i p for N=8, 2 c l u s t e r s of i d e n t i c a l users and 78 A . l Right-half plane semicircle 93 v i i ACKNOWLEDGEMENTS I would l i k e to acknowledge my appreciation to Dr. R.W. Donaldson for his encouragement and supervision throughout the course of t h i s research.. I would also l i k e to thank Dr. H.W. Lee for his many valuable suggestions. Thanks are due to Ms. Charlotte Stevenson for typing the manuscript. F i n a l l y , f i n a n c i a l support from an NSERC postgraduate scholarship i s g r a t e f u l l y acknowledged. v i i i 1 1. INTRODUCTION. 1.1 High-performance Local Area Networks. The demand for l o c a l communication resources continues to grow very r a p i d l y . Today, l o c a l area networks (LANs) operating at a few Mbit/s can s t i l l s a t i s f y most current needs but the s i t u a t i o n i s l i k e l y to change i n the near future. The advent of superfast microcomputers, the evolution of new system architectures (e.g. d i s t r i b u t e d processing) and the Integration of data intensive services (e.g. i n t e r a c t i v e graphics, tele-conferencing) a l l lead to ever higher bandwidth requirements. Even with sophisticated bandwidth compression techniques, the bandwidth of the conventional co-axial cable w i l l not be adequate for many ap p l i c a t i o n s i n the future. Optical f i b e r emerges as the most promising candidate for implementing ft the high-performance LANs needed i n the future. The most impressive feature of o p t i c a l f i b e r i s i t s enormous information-carrying capacity; the t h e o r e t i c a l l i m i t i s well above 100 Gbps-km. Several Gbps-km can be achieved using current technology. As the technique of wavelength-division multiplexing matures, the bandwidth of an o p t i c a l f i b e r w i l l increase many-fold. Thus, not only can o p t i c a l f i b e r s a t i s f y the bandwidth requirements of LANs i n the foreseeable future, i t w i l l also provide great f l e x i b i l i t y for growth i n the long term. Other desirable features such as immunity to electromagnetic interference, high channel s e c u r i t y , low signal, l o s s , small s i z e , l i g h t weight, e t c a l l make o p t i c a l f i b e r very a t t r a c t i v e for LAN a p p l i c a t i o n s . Nevertheless, l i m i t a t i o n s on current f i b e r optics technology do impose constraints on LAN system designs ([5-7]). For example, 2 the very high i n s e r t i o n loss of current o p t i c a l taps has led designers to consider point-to-point configurations such as rings or stars instead of l i n e a r bus structures. Furthermore, b i d i r e c t i o n a l transmission on a single o p t i c a l f i b e r also faces considerable d i f f i c u l t y due to the minute f i b e r core size and crosstalk between source and detector. To overcome the technological d i f f i c u l t i e s with f i b e r o p t i c s , a number of new network schemes have been developed ([8-13]). Among these, the u n i d i r e c t i o n a l broadcast structures (UBSs) with c o n f l i c t - f r e e schedulings appear to be most s u i t a b l e f or very high data rate a p p l i c a t i o n s . The access protocols used i n these UBSs resemble the conventional token-passing on a r i n g which provides superior delay-throughput c h a r a c t e r i s t i c s . However, these networks avoid the major p i t f a l l s associated with the token-ring. As a r e s u l t , UBSs have received much attention l a t e l y . A t y p i c a l UBS c a l l e d D-net w i l l be described i n Chapter 2, together with i t s i n t e r e s t i n g properties. 1.2 Objectives. The primary goal of t h i s thesis i s to investigate the performances of UBSs by studying the c l a s s i c a l token-passing protocol. The performance index w i l l be the average message delay at each node. Unfortunately, a rigorous delay analysis under the most general conditions i s very d i f f i c u l t . To provide mathematical t r a c t a b i l i t y , a number of reasonable assumptions are made to simplify the problem. Attention i s focused on the gated exhaustive service d i s c i p l i n e because i t can be analyzed mathematically and also provides insight to the performance analysis of the more p r a c t i c a l non-exhaustive service schemes. 3 1.3 Previous Work. The problem of e s t a b l i s h i n g the queueing c h a r a c t e r i s t i c s of a token-ring system has been studied by many authors i n the l a s t two decades under various t i t l e s (e.g. p o l l i n g , t r a f f i c c o n t r o l , c y c l i c queues). The long h i s t o r y of this problem indicates both i t s importance and i t s i n t r a c t a b i l i t y . So f a r , no solutions are a v a i l a b l e to the general problem, whether exact or approximate, an a l y t i c or algorithmic. Thus, we have to use l e s s r e l i a b l e and hard-to-interpret r e s u l t s obtained from simulations or actual network measurements to study the queueing behaviour of many p r a c t i c a l token-ring systems. Nevertheless, rigorous analyses have been ca r r i e d out for some special although u n r e a l i s t i c cases. It i s the hope of many researchers that these analyses can shed some l i g h t on the behaviour of more p r a c t i c a l systems. A good summary of the more recent work on token-ring analysis can be found i n [29]. With few exceptions, most of the previous work dealt with the gated and the non-gated exhaustive service d i s c i p l i n e s with i n f i n i t e buffering and Poisson a r r i v a l s . The s p e c i a l case with only two nodes in the system was studied i n [19-21] and exact e x p l i c i t delay r e s u l t s were obtained. Generalizations to an a r b i t r a r y number of nodes were investigated i n [22-29J. Moment generating functions of cycle time, queue length and delay d i s t r i b u t i o n s have been obtained i n [22-26]. Unfortunately, these are not closed-form solutions that f a c i l i t a t e easy evaluation of delay moments. Attempts have been made to derive e x p l i c i t a n a l y t i c expressions for the average delays but they were successful for the symmetric case only ([25-27]). For the general asymmetric case, only numerical algorithms 4 ([27-29]) and approximate solutions ([30-33]) are a v a i l a b l e . Most of the approximations given i n the l i t e r a t u r e are based on rather h e u r i s t i c arguments and hence t h e i r regions of v a l i d i t y are unclear. In general, these approximations break down at very heavy network loadings or under highly asymmetric terminal t r a f f i c . Numerical algorithms have the advantage of generating exact r e s u l t s but they cannot r e a d i l y show the e f f e c t s of simultaneous changes i n the system parameters. An asymmetric token-ring has an enormous parameter space (the set of a l l possible combinations of parameters) and hence r e s i s t s analysis by numerical methods. Nevertheless, exact numerical r e s u l t s can serve as absolute references for v a l i d a t i n g approximations and simulations. The more general cases of non-exhaustive service d i s c i p l i n e s and f i n i t e buffering are much more d i f f i c u l t to deal with, as evidenced by the lack of previous work i n t h i s area. An approximate treatment of non-exhaustive service d i s c i p l i n e s can be found i n [34]. Non-exhaustive service d i s c i p l i n e s on a two-node system were analyzed i n [35]. The system with single-buffer nodes (inte r a c t i v e - u s e r model) was investigated i n [38] based on the work from [36-37 ]. 1.4 Outline. In Chapter 2, a t y p i c a l UBS c a l l e d D-net i s described to show the resemblance of the UBSs and token-ring systems. Then the queueing model and relevant system parameters are formulated- A number of important random var i a b l e s are defined and t h e i r r e l a t i o n s h i p s are discussed. 5 In Chapter 3, the queueing problem i s solved by the "method of Imbedded Markov Chain. The imbedded chain being considered i s the j o i n t terminal service times i n a service c y c l e . A recursive functional equation i s derived for the moment generating function of the imbedded chain at steady state. D i f f e r e n t i a t i o n s of t h i s basic functional equation y i e l d recursive l i n e a r equations for the f i r s t and second order moments. The existence and uniqueness of solutions to these l i n e a r equations are also established. In Chapter 4, a number of r e s u l t s are derived concerning the solutions of j o i n t moments of the terminal service times. A simple difference equation which has not been reported before i s presented. This equation provides the basis for a very good approximation. In Chapter 5, the r e l a t i o n s h i p s between average message delays and the normalized cycle time variances are given. A fundamental r e l a t i o n among the delays, dictated by Kleinrock's conservation law, i s also derived. An approximate sol u t i o n i s then developed, followed by a comparison with exact numerical r e s u l t s . In the conclusion, a summary of r e s u l t s i s given with suggestions for future research. 6 2. DEVELOPMENT OF THE LAN SYSTEM MODEL. 2.1 Description of D-net and i t s Communication Protocol. U n i d i r e c t i o n a l broadcast structures may be d i f f e r e n t i n topology and in many other aspects but their basic operations are very s i m i l a r . A t y p i c a l UBS c a l l e d D-net i s described to i l l u s t r a t e the basic communication protocol commonly used for UBSs. F i g . 2.1 shows the architecture of D-net. The network consists of an inbound and an outbound channel. A l l t r a f f i c flows u n i d i r e c t i o n a l l y from the outbound channel to the inbound channel. There are N stations i n the network, numbered i n the order shown i n the f i g u r e . Each st a t i o n has three taps: the receiver (R-)tap, the sensor (S-)tap and the transmitter (T-)tap. The R-taps are connected to the inbound channel to receive any broadcast messages. The S-taps and the T-taps are connected to the outbound channel as shown i n F i g . 2 . 1 ; they are used to sense upstream t r a f f i c and to transmit broadcast messages, r e s p e c t i v e l y . The black b a l l i s c a l l e d the locomotive generator and i t has only the R-tap and the T-tap. To transmit, a station f i r s t waits u n t i l i t senses upstream t r a f f i c at i t s S-tap. The s t a t i o n then looks for the end-of-carrier (EOC). The EOC event i s defined as the cessation of signal at the S-tap. It i s assumed that i t takes t, seconds to detect t h i s event. After detection of EOC, the d s t a t i o n s t a r t s transmitting i t s own packets. While transmitting, a s t a t i o n may sense more incoming upstream t r a f f i c through i t s S-tap. In this case, the s t a t i o n aborts i t s transmission and waits for the next EOC. Otherwise, the s t a t i o n f i n i s h e s i t s transmission. This basic operation w i l l be repeated. B a s i c a l l y , a s t a t i o n sees a ' t r a i n ' of packets separated by t . INBDUMD LDCDMDTIVE GENERATOR 7^ R T R R T S © © T S T T R • • • ® i T •*• OUTBOUND F i g . 2.1 Architecture of D-net. LDCDMDTIVE HX+t, F i g . 2.2 Trains of packets on D-net. 8 seconds on the channel and each s t a t i o n attaches i t s packets to the end of th i s t r a i n . The t r a i n thus grows i n size as i t passes through a station with ready packets. The locomotive generator i s used to transmit a short burst c a l l e d the locomotive to head the t r a i n of packets. Without the locomotive generator, the network w i l l s t a l l because no stations w i l l contend for the channel unless there i s some t r a f f i c . To keep the network ' a l i v e ' a l l the time, the locomotive generator generates a locomotive each time i t sees the end-of-train (EOT) at i t s R-tap. The EOT event s i g n i f i e s the end of a c y c l e . It i s detected when a silence period of 2t^ seconds a f t e r cessation of signal i s noted at the R-tap of the locomotive generator. If normal operation p r e v a i l s , the t r a f f i c on the u n i d i r e c t i o n a l channel w i l l consist of tr a i n s of packets separated by 2(T + t^) seconds shown i n F i g . 2.2 where i i s the propagation delay on ei t h e r the inbound or the outbound channel and 2t^ i s the time needed to detect EOT. It i s noted that the D-net u n i d i r e c t i o n a l bus described here i s not suitable for f i b e r optic implementation because of the d i f f i c u l t i e s with current o p t i c a l tap technology (e.g. high signal l o s s ) . Two modifications of the basic D-net structure are given i n [12] to overcome these technological d i f f i c u l t i e s . The star coupled version of D-net shown i n F i g . 2.3 i s suggested to enable the i n s e r t i o n loss of R-taps to be lumped i n the coupler so that each s t a t i o n receives approximately the same signal power. The open-ring version shown i n F i g . 2.A can be used to avoid the d i s t r i b u t e d i n s e r t i o n loss at the T-taps. Since each node i s ac t i v e i n the open-ring D-net, bypass c i r c u i t s must be Incorporated i n case of a node f a i l u r e . 9 STAR CDUPLER LOCOMDTIVE GENERATOR F i g . 2.3 The Star-coupled Version of D-net. T T R LOCOMOTIVE GENERATOR T R T R T S © © T S R © T v.. s T F i g . 2.A The Open-ring Version of D-net. 10 2.2 Comparison of D-net with Token-Ring Systems. By taking advantage of the inherent ordering of the network nodes, the D-net protocol provides orderly network access s i m i l a r to that of token-passing on a r i n g . As long as the EOC detection time in D-net is comparable to the token detection time i n a token-ring, the two networks w i l l have e s s e n t i a l l y the same delay performance. From the t r a i n i n g sequence of D-net, we may regard the switching overheads as being lumped in the inter-round s i l e n c e period of 2(x + t_) seconds. One advantage of D-net over d the conventional d i s t r i b u t e d token-ring i s that the impact of the inter-round overhead can be reduced by i n t e r l e a v i n g the locomotives. To do t h i s , the locomotive generator must ant i c i p a t e the length of each t r a i n and generate the locomotive not by detecting EOT but by precise timing. However, i n t e r l e a v i n g locomotives i s advantageous only when the inter-round overhead i s a s i g n i f i c a n t portion of the cycle time ( t r a i n + overhead). Calculations based on t y p i c a l parameters suggest that the i n t e r l e a v i n g of locomotives i s perhaps o v e r s k i l l e d for many LAN a p p l i c a t i o n s . A more a t t r a c t i v e way to reduce the r a t i o of overhead to cycle time i s to allow s t a t i s t i c a l v a r i a t i o n s of the s t a t i o n access times according to the network loading, for example by not r e s t r i c t i n g service to a single packet per node per c y c l e . The gated exhaustive service d i s c i p l i n e under i n v e s t i g a t i o n i n this thesis i s one example of this approach. The r e l i a b i l i t y issues surrounding the D-net protocol and token-ring are also d i f f e r e n t . One observes that the D-net protocol i s not completely d i s t r i b u t e d . The locomotive generator can be regarded as a central 11 c o n t r o l l e r whose f a i l u r e w i l l s t a l l the network. Fortunately, the locomotive generator i s a simple device so i t can be made redundant with l i t t l e a d d i t i o n a l cost. Nevertheless, the D-net protocol avoids the major p i t f a l l s i n token-passing such as l o s t tokens or duplicate tokens. If a locomotive i s l o s t because of channel e r r o r s , the locomotive generator w i l l simply time out and generate another locomotive. Considering the complexity of error detection and recovery mechanisms of conventional token-passing, the D-net protocol represents a major improvement over token-passing. Another r e l i a b i l i t y issue i s re l a t e d to the control passing mechanism i n the D-net protocol. Recall that each s t a t i o n attempts to transmit immediately a f t e r detecting EOC and aborts i t s transmission as soon as i t detects any incoming t r a f f i c at i t s S-tap. Since i t takes a f i n i t e amount of time to detect incoming t r a f f i c , there w i l l be c o l l i s i o n s of a very short duration (time needed to detect incoming t r a f f i c ) at the beginning of each packet. It i s assumed that each packet i s headed by a preamble portion for b i t synchronization and the c o l l i s i o n s mentioned above w i l l not a f f e c t the s y n c h r o n i z a b i l i t y of the preamble portion. 2.3 System Model and Parameters. As we have seen, the basic operation of D-net i s i d e n t i c a l to the token-ring except for the switching overheads from one s t a t i o n to another. For t h i s reason, the performances of D-net and a l l other s i m i l a r UBSs w i l l be studied i n t h i s thesis as i f they were token-ring systems. F i g . 2.5 shows the schematics of the single-server multi-queue model suitable for the analysis of the token-ring system. N queues, numbered from 1 to N, are 12 Q U E U E 2 • N • S E R V E R C Y C L I C S C H E D U L E R F i g . 2.5 Schematics for the Single-server Multi-queue Model. 13 attended by a single server i n a c y c l i c order. Further, time i s divided into contiguous s l o t s of fixed duration. A l l time quantities are measured in terms of t h i s fundamental un i t . A number of parameters are needed to specify the queueing system, i n order to pose a well-defined problem involving dependent queues. These parameters w i l l be discussed i n the following paragraphs. Message a r r i v a l s . Poisson message a r r i v a l i s perhaps the most popular assumption i n queueing a n a l y s i s . A s l i g h t l y more general type of a r r i v a l w i l l be considered here. Messages a r r i v i n g at a queue within a time s l o t w i l l be registered at the end of that s l o t . The number of message a r r i v a l s at queue i i n one s l o t i s random and i t s d i s t r i b u t i o n i s characterized by the moment generating function (MGF) 1 c t ^ s ) . A r r i v a l s within d i f f e r e n t time slots are assumed to be independent and the same assumption i s made for a r r i v a l s at d i f f e r e n t queues. By l e t t i n g the s l o t i n t e r v a l become vanishingly small while keeping the message a r r i v a l rate constant, one obtains Poisson message a r r i v a l s as a s p e c i a l case of the general independent slot a r r i v a l s considered here. Other a r r i v a l s t a t i s t i c s can also be reasonably approximated by choosing the appropriate s l o t size and the MGFs Message lengths. Message lengths are assumed random with general d i s t r i b u t i o n s described by MGFs (p\(s)}. Although generally d i s t r i b u t e d , the 1 The MGF of a random va r i a b l e X i s defined as F(s) = E[exp(sX)]. length of a message must be an i n t e g r a l multiple of the s l o t i n t e r v a l . Moreover, message lengths are assumed to be independent of the message a r r i v a l s and also independent among d i f f e r e n t queues. Service d i s c i p l i n e . The service d i s c i p l i n e i n a multi-queue system includes s p e c i f i c a t i o n s of the service schedule, order-of-service at each queue and the number of messages to be served from each queue in a service c y c l e . In a token-ring system, queues are inherently served i n a c y c l i c order (service schedule). Further, a f i r s t - c o m e - f i r s t - s e r v e d i s c i p l i n e w i l l be assumed at each queue (or d e r - o f - s e r v i c e ) . Thus, the service d i s c i p l i n e s i n t h i s thesis w i l l usually refer to the number of messages served from each queue i n a c y c l e . Various service d i s c i p l i n e s are possible; they can be gated or non-gated, exhaustive or non-exhaustive. For gated service d i s c i -p l i n e s , a l l messages a r r i v i n g at a queue a f t e r commencement of service at that queue w i l l not be served i n that service c y c l e . Services not gated are c a l l e d non-gated. The terms 'exhaustive' and 'non-exhaustive' are self-explanatory. In pr a c t i c e , almost a l l service d i s c i p l i n e s are non-exhaustive i n nature to avoid the p o s s i b i l i t y of very long cycles. Unfortunately, the rigorous analysis of non-exhaustive service d i s c i p l i n e s appear to be insurmountably d i f f i c u l t . As a r e s u l t , attention w i l l be focused on the gated exhaustive d i s c i p l i n e for mathematical t r a c t a b i l i t y . As wel l , most non-exhaustive schemes can be approximated by the gated exhaustive scheme for' low t r a f f i c l e v e l s . For the gated exhaustive d i s c i p l i n e , a l l messages buffered at a queue when service s t a r t s at that queue w i l l be served i n that p a r t i c u l a r cycle while messages arrived during service w i l l be l e f t i n the queue u n t i l the next c y c l e . This i s d i f f e r e n t from the truly exhaus-15 t i v e (non-gated exhaustive) d i s c i p l i n e where queues are served t i l l empty i n each c y c l e . The non-gated exhaustive scheme w i l l not be considered here. Interested readers can r e f e r to [22-29] for more d e t a i l . Switching overheads. There i s a generally d i s t r i b u t e d switching overhead from queue i to the next queue characterized by the MGF co^(s). Similar to the message length, the switching overhead must be an in t e g r a l multiple of the s l o t i n t e r v a l . Also, a l l switching overheads* are assumed to be independent of each other. The D-net, with constant switching overheads, i s an example. Buf f e r i n g . I n f i n i t e buffering w i l l be assumed throughout t h i s t h e s i s . This i s a reasonable assumption as long as the blocking p r o b a b i l i t y i s small. In summary, the system under consideration i s a single-server N-queue system. Time i s divided into fixed contiguous s l o t s . Queues are served c y c l i c a l l y under a gated exhaustive d i s c i p l i n e and a f i r s t - c o r a e - f i r s t - s e r v e order-of-service. I n f i n i t e buffering i s assumed at each queue. General independent time s l o t message a r r i v a l s are assumed with s l o t a r r i v a l s characterized by the MGF a^(s) at queue i . Messages a r r i v i n g at queue i have generally d i s t r i b u t e d lengths decribed by the MGF 8 i ( s ) . The switching overhead from queue i to the next queue Is also generally d i s t r i b u t e d with MGF (^(s). 2.4 D e f i n i t i o n s of System Random Variables. To formulate the mathematial queueing problem, a number of random var i a b l e s need to be defined. Let 16 (k) = kth cycle time of queue i , i . e . the time between successive scan instants (instant when service s t a r t s ) of queue i . (k) = the number of messages buffered at queue i at i t s scan instant i n the kth c y c l i c service of that queue. (k) = the number of messages arrived at queue i during the kth cycle of queue i . (k) = the number of messages served from queue i i n the kth cycle of queue i . (k) = the switching overhead from queue i to the next queue i n the kth cycle of queue i . (k) T\ = the terminal service time of queue i i n the kth cycle of queue i , i . e . time for the server to serve queue i and to switch to the next queue. A l l the above random variables assume non-negative integer values. According to the d e f i n i t i o n s , a number of rel a t i o n s h i p s can be written as follows: (k) (k) Z. = X. for gated exhaustive service (2.1) 7 (k) • K, = I L . }*> + W.^; (2.3) i fa 1.3 C.<k> = I T . ( k ) +rT.(k+1) (2.4) c ( k ) \ W = 1 M. < k ) (2.5) 1 j=l 1 , J where (k) L . = length of the j t h message buffered at queue i at i t s scan i»J instant i n the kth c y c l i c service of queue i . (k) M i j = number of messages arrived at queue i in the j t h s l o t of the kth cycle of queue i . (k) (k) The variables M, . and L. . are two sets of independent and i d e n t i c a l l y i , J i . J d i s t r i b u t e d ( i . i . d . ) random variables whose s t a t i s t i c s are described by the MGFs a^(s) and B^(s) r e s p e c t i v e l y . When the lower index exceeds the upper index i n any summation, the summation i s defined as zero. This convention w i l l be adopted throughout this t h e s i s . 2.5 Comments on the Relations between System Random Variables. Equations (2.1)-(2.5) represent the most basic r e l a t i o n s between the system random variables for the gated exhaustive service d i s c i p l i n e . For other service d i s c i p l i n e s , equations (2.2)-(2.5) s t i l l hold but (2.1) has to be modified. For example, i f queues are served according to the gated non-exhaustive scheme with queue i allowed to be served up to p^ messages in each c y c l i c s ervice, then (2.1) w i l l become Pi Z.^J = I I ( X , V * ' > j ) (2.6) 1 j-1 1 where I( •) i s the indicato r f u n c t i o n 2 . By d e f i n i t i o n , Z ^ < X ^ for a l l gated d i s c i p l i n e s . Moreover, there i s often a deterministic r e l a t i o n betwen (k) (k) Zj and Xj l i k e (2.1) and (2.6) but there are prominent exceptions such as the non-gated exhaustive case. One notices that equations (2.1)-(2.5) are recursive i n nature. Given „ (k) w (k) „ (k) v . „ (k) „ (k) „ (k) ,„ (k) , » •••» XJJ » w e can obtain , Z2 , •••> Z^ j and , T 2 ( k ) , .... T N ( k ) using (2.1) and (2.3). Then we can obtain C and X 2 ( k + 1 ) from (2.4), (2.5) and (2.2). C l e a r l y , X 2 ( k + 1 \ X 3 ( k + 1 ) , ... can be derived successively i n t h i s manner. Thus, (2.1)-(2.5) completely characterize the evolution of the system. We s h a l l use these equations to solve our queueing problem by the method of imbedded Markov chain i n the next chapter. 2 The in d i c a t o r function I(•) i s defined to be 1 i f the statement within brackets i s true and 0 otherwise. 19 3. FORMULATION OF THE SYSTEM EQUATIONS. 3.1 Imbedded Markov Chain Formulation. The imbedded Markov chain we consider here i s the j o i n t random variable of a l l the terminal service times i n a cy c l e . If we define T^ k^ = ( T ^ k \ . .., T K ^ ) , then T ^ w i l l be the imbedded chain. The steady state s t a t i s t i c s of T*^k^ can be obtained using moment generating functions. Let P(s) where s = (S}» s 2> s^) be the MGF of the random vector T^ k^ as k approaches i n f i n i t y . Then we can write P(s) = I exp(s • t) I p(t|u) p(u) (3.1) t u where t = ( t l s t 2 , t N ) , u = ( u l s u 2, U J ^ J ) N s • t = ) s t = dot (scalar) product, , n n n=l p(u) = lim P r o b ( ? ( k ) = u) , p(t*|u) = P r o b ( ? < k + 1 ) - t V ( k ) = u). Interchanging the order of summation y i e l d s P(s) = I p(u) I exp(s* • t) p(t|u) (3.2) u t The t r a n s i t i o n p r o b a b i l i t i e s can be expressed by N 'p(tlu) « n q(t |c ) (3-3) , n 1 n n=l 20 where q(t |c ) = Prob(T ( k + 1 ) = t |C ( k ) = c ) , n ' n n n' n N n-1 c n . L 3 . L , j Thus, the summation over t i n (3.2) can be w r i t t e n as N I exp(s • t ) p(t|u) = n e x p ( s n t n ) q ( t n | c n ) ) -> n=l t t n N-1 = n {I e x P ( s n t n ) q ( t n | c n ) ) I e x p ( s N t N ) q ( t J c N ) (3.A) n = 1 C n S Let L and 11^ be random variables having d i s t r i b u t i o n s of message lengths and a r r i v a l s i n a s l o t r e s p e c t i v e l y at queue N. Then the summation over t i n (3.4) can be evaluated as I e x P ( s N t N ) q ( t N l C N ) fcN - E t e x p ^ T ^ ) ^ - c K ] z ( k + 1 ) = E [ e x p ( s N L N ) N | C N ( k ) = c N ] E [ e x P ( s N W N ( k + 1 ) ) ] by (2.3) = E [ e x P ( Y K ( k ) X n 8 N ( s N ) ) | C N ( k ) = c N ] o ^ ) by (2.1) and (2.2) = E[(exp(M K J ! n B N ( s N ) ) ) C N ] ^ . ( s N ) by (2.5) = exp(c N too^CtoSjjCSy))) o^,(sN) = e x P ( c N W ) ^ ( B n ) (3-5) where ^ ( s ) = i!na N(toB N(s)). 21 Substitution of (3.5) into (3.4) gives N-l I exp(s-t)p(t|u) = n [I e x p ( s n t n ) q ( t n | c n ) ] exp(c'N % ( s N ) ) «^(s N) •+• n=l t n t N-2 = n [I e x P ( s n t n ) q ( t n | c n ) ] I e x P ( s N _ 1 t N _ 1 ) q ( t N _ 1 | c N _ 1 ) e x p ( c N S ^ ) ) ^ ( s ^ n = 1 'n V l N-2 = n [I e x p ( s n t n ) q ( t n | c n ) ] I e x p ( ( s N . 1 + y s N ) ) W ^ N - l lcN-l> n = 1 C n CN-1 . e x p ( ( c N - t N _ 1 ) SN(8N)) u i N ( s N ) N-2 = n [I e x p ( s n t n ) q ( t n | c n ) ] e x p [ c N _ 1 V l ( W W > ^ V l ( S N - l + n=l t n . e x p ( ( c N - t N _ 1 ) ysN)) (^(SJP (3.6) The l a s t step i s done by noti c i n g (c - t N _ ) i s independent of t^_1 and by using the same summing technique used to derive ( 3 . 5 ) . Continuing i n t h i s fashion, we can write N N N _> I e x p ( s - t ) P ( t | u ) = n exp((I u ) G n ( s ) ) n u>n( s n+H n(s)) ->• n=l i=n J n=l t J N N ^ = n exp(u F (s) ) n u (s +H (s)) r n n , n n n n=l n=l N = exp(u'F >(s)) n W n ( s n + H n ( s ) ) (3.7) n=l where Gn(h = S n ( s n + H n ( l ) ) (3. 7a) N H (s) = I G.(s'), !L.(s) = 0 (3.7b). k=rrrl Fn(J) = I G k ( l ) = FN(J) - Hn(J) (3.7c) k-1 F(s) = (F,(s), F 2 ( s ) , .... F N(s >)) 22 Substitution of (3.7) into (3.2) gives N P(s) = [ II co n(s n + H n ( s ) ) ] P(?(s)) (3.8) n=l Eqn. (3.8) i s a recursive functional equation that allows us to solve for P(s) . We s h a l l attempt to c a l c u l a t e the f i r s t and the second order moments •*( k) of T with k-*00 i n the next section. Before leaving t h i s section, we notice that exactly the same procedure can be used to derive the MGF of the jo i n t terminal service times for the time continuous system with Poisson message a r r i v a l s . The r e s u l t s w i l l be exactly the same except that a l l time quantities are expressed i n seconds and the a r r i v a l MGFs (ct\(s)} are replaced by {exp( X^ (exp( s ) - l ) ) } where X^ i s the message a r r i v a l rate at queue i . 3.2 Moment c a l c u l a t i o n s . To c a l c u l a t e the moments of the j o i n t terminal service times, i t i s convenient to take natural logarithm of both sides of (3.8) and write N P(s) = I 2 n ( s n + H n(s)) + P(F(s)) (3.9) n=l where P(s) = AnP(s) , to (s) = Jlno) (s) n n By d i f f e r e n t i a t i n g (3.9), we can get the ce n t r a l moment (and hence the moments) of the j o i n t terminal service times. D i f f e r e n t i a t i o n of (3.9) once and evaluation at s = 0 gives & N - oF. N o(s.+H.) » - J * L J + I ft ^ J (3.10) 23 A l l d e r i v a t i v e s w i l l be evaluated at the o r i g i n unless stated otherwise. A second d i f f e r e n t i a t i o n y i e l d s o~ N N ,* 5F 5F N ~ d 2F 52P = y y S2P k ™ I y &P k ^ L Ao Ao Ao Ao A d S i 5 s j k-1 *=1 5 s k d S A & S i & S j k-1 d S k & S i a S j + y 5(s k +H k) 5 ( s k ^ H k ) k-1 i j i j Eqns . (3.10) and (3.11) can be re a d i l y expressed i n matrix form as follows: v = Av + b (3.12) V = AVA T + B (3.13) where -+ T -> T v = ( v l f v 2 , v N ) , b = ( b l t b 2, b N) , V i = 5s" • b i ~ . \ U J 5s . • V = [v. .] , v. . = ° , i j J i j a s 1 a s j aF. A = t a i j J • a i j = ^ • ^k 5s., as . i J 3.3 Approaches to the Solutions of the Basic Equations. There are two approaches to obtaining solutions of (3.12) and (3 .13) . The f i r s t approach i s to recognize that (3.12) i s a set of N li n e a r equations 24 5P of N unknowns-g-^— with the forcing terms . Then we notice that (3.13) represents another set of l i n e a r equations of N(N+l)/2 unknowns {v. ,} (v..=v..) with forcing terms {b, .}; these {b..} are obtained from the s o l u t i o n of (3.12). Hence, we can solve (3.12) and (3.13) by standard techniques for solving systems of l i n e a r equations. Naturally, the questions regarding existence and uniqueness of the solutions to both set of equations a r i s e . These questions can be answered by e x p l i c i t series solutions using the second approach discussed l a t e r . The ultimate goal i s to solve (3.12) and (3.13) e x p l i c i t l y i n closed form. Unfortunately, no such solutions are available for (3.13) except for the symmetric case or for N=2. The second approach i s somewhat numerical i n nature. We notice that both (3.12) and (3.13) represent recursive r e l a t i o n s that allow i t e r a t i v e numerical s o l u t i o n s . A new estimate can be calculated from the immediately previous estimate using the right hand side of (3.12) and s i m i l a r l y for (3.13). If the i t e r a t i v e procedure converges, then we can obtain a s o l u t i o n . The main r e s u l t s obtained following t h i s l i n e of thought can be summarized i n Theorem 3.1 i n the next section. 3.4 Existence and Uniqueness of Solutions to the Basic Equations. Theorem 3.1; If the u t i l i z a t i o n of the system s a t i s f i e s p < 1, then unique CO solutions exist for both (3.12) and (3.13) and they are given by v = £ A b k=0 00 T k k and V = ^ A B(A ) r e s p e c t i v e l y . k=0 25 Indeed, the theorem can be extended to a l l higher order derivatives of P(s) but we w i l l r e s t r i c t our attention to the f i r s t two orders of moments. The proof of Theorem 3.1 r e l i e s heavily on a result proved i n the Appendix st a t i n g that i f p < 1, then a l l the eigenvalues of A have magnitudes less than unity. We prove Theorem 3.1 using t h i s r e s u l t . Proof of Theorem 3.1: We diagonalize A by A = TAT"1 (3.14) where A i s a diagonal matrix with elements equal to the eigenvalues Xp X 2» X^ of A, and T contains the corresponding column eigenvectors. Using t h i s d i a g o n a l i z a t i o n , we can write I A b = I r A k r _ 1 b = i x I A V " ^ k=0 k=0 k=0 and lAkB(Ak)T=I r A k r _ 1 B ( r " 1 k=0 k=0 = rd A k c A k ) r T k=0 where c = p - V " 1 ) 1 - l C l J j . (3.15) (3-16) Now \\ A = k=0 I K Ki=j) k=0 1 and £ A K C A K k=0 I c,.X kX k k=0 l j 1 J Both series exist i f |X.| < 1 for a l l i and t h i s Is guaranteed i f p < 1 OO oo X Therefore I A b and I A*B (A* ) both e x i s t i f p < 1 and s u b s t i t u t i o n of k=0 k=0 these seri e s into (3.12) and (3.13) w i l l v e r i f y that they are indeed solutions to the equations. Hence the existence of the solutions to (3.12) and to (3.13) has been established. To e s t a b l i s h the uniqueness of those solutions , we l e t v and u be solutions to (3.12) and write v = Av + D (3.17 ) u = Au + b (3.18) Subtraction gives (v - u) = A(v - u) (3.19) which implies (v - u) = A k ( v - u) for a l l k (3.20) but A k ( v - u) = TA^r *(v - u) •+ 0 as k •*• » so v = u. Similar arguments es t a b l i s h the uniqueness of the sol u t i o n to (3.13). 3.5 Comments Regarding Solutions of the Basic Equations. The series solutions given i n Theorem 3.1 are useful i n es t a b l i s h i n g existence and uniqueness, but they do not shed l i g h t on the e x p l i c i t closed-form s o l u t i o n s . Even for numerical solutions', one w i l l follow the i t e r a t i v e procedures given by (3.12) and (3.13) instead of c a l c u l a t i n g the series i n Theorem 3.1 term by term. In f a c t , a very nice numerical procedure was developed i n [28-29]. However, i t i s desirable to have ana l y t i c r e s u l t s that 27 display the e f f e c t s of changes i n system parameters. In the next chapter, we s h a l l derive a number of exact a n a l y t i c r e s u l t s . 28 4. SOME EXACT ANALYTIC RESULTS. 4.1 Overview of Results. A number of exact a n a l y t i c r e s u l t s are ava i l a b l e regarding the solutions to ( 3 . 1 2 ) and ( 3 . 1 3 ) . F i r s t of a l l , ( 3 . 1 2 ) can be solved e x p l i c i t l y i n closed form by considering the average cycle time. The sol u t i o n to (3.12) allows us to simplify the forcing matrix B i n ( 3 . 1 3 ) . Next, we explore the structures of the matrices A and B i n ( 3 . 1 3 ) . A simple difference equation r e l a t i n g the unknowns { v^j) i s derived by ex p l o i t i n g the structures of A and B. This difference equation has not been reported before and It w i l l form the basis of the mean delay approximation to be presented i n the next chapter. 4.2 Expected Cycle Time. From equation ( 2 . 4 ) , we observe that the expected cycle time at steady state i s equal to the sum of a l l expected terminal service times. This means the average cycle time i s independent of the queue. Using t h i s f a c t , we can compute the average cycle time and obtain other r e s u l t s as w e l l . We state these r e s u l t s p r e c i s e l y by the following Lemma. Lemma 4.1: The expected cycle time of queue i at steady state i s independent of i and i t i s given by (4.1) 29 ~ p. EW 5P _ ^ , _ i 5s. 1 Moreover, = P l EC + EW1 = - i — + EW1 (A.2) l where EC = average cycle time, EW^ = Uj' (o) = expected overhead from queue i to the next queue, N EW = \\ EW. = t o t a l expected overhead, j-1 2 p^ = S^'(o) = u t i l i z a t i o n of queue i , N p = 1 p . - system u t i l i z a t i o n , j - l J Proof of Lemma A . l : From (2.A), we can write N „ x i-1 lim E C . ^ = lim E[ I T\*> + £ T^'] k-**> 1 k-Kt. j=i J j = l J N / V. X - i m ^ - s i r «- 3 ) 1=1 J Equation (A.3) states that the average cycle time of queue i at steady state i s independent of i and we denote t h i s quantity by EC. From (3.10), we have 30 Next, we notice from (3.7a) and (3.7b) that Gj,' G 3, and Hj, H 2, are a l l independent of s ^ and from (3.7 c) that F^ = G^ + G2+ • • • + G ^ , therefore oF. oG1 S(s . + H.) ^ = IT, - a n d 'as, 3 = I ( ^ = 1 ) N 1 3-1 3 From the d e f i n i t i o n s of 3. and S., we have i l a.' = a.' 8 . ' = (average a r r i v a l s i n a s l o t x average message length i n s l o t s ) at q ue ue i Thus, S.' - <*>.' = EW. i i ] /s N " ° P V 0 P J . 1711 " P l A TT. + EWl 5s i -. . uo . 1 3=1 3 = p ]EC + Ew~i ( 4 . 5 ) Similar r e s u l t s can be obtained f or a l l other queues so (4.5) can be rewritten as -g-= p. EC + EW, ( 4 . 6 ) 0Sj i I Summation of (4.6) over a l l i gives EC = pEC + EW *=> EC =1^- ( 4 . 7 ) L - p Combination of (4.3), (4.6) and (4.7) gives (4.1)-(4.2) 31 We remark here that (4.1)-(4.2) are very general r e s u l t s that can be obtained by considering equations (2.2)-(2.5) only without assuming any p a r t i c u l a r service d i s c i p l i n e . One also notices that we did not solve (3.12) d i r e c t l y to obtain (4.2). Instead, we exploited the c y c l i c symmetry of the system to get (4.6) and (4.7), which are much simpler than (3.12). This r e a d i l y demonstrates the importance of c y c l i c symmetry In our problem. 4.3 S i m p l i f i c a t i o n of the Forcing Matrix B. The s o l u t i o n to (3.12) given by (4.2) can be used to simplify the elements i n matrix B to a considerable extent. This i s stated i n Lemma 4.2. Lemma 4 .2 The elements {b^ .. } of the matrix B i n (3.12) can be s i m p l i f i e d as N o(s + H ) o ( 6 . + H ) b i J " [ K 5s, 5s. ] E C <*'8> J k=l i j where 0 ) . C i = V + EC 2 varMj varL^ varW^ P i (TH^J2 + P i E L ^ ~ + "EC ( 4 ' 8 a ) EMj = average message a r r i v a l s at queue i i n a s l o t , varMj = variance of message a r r i v a l s at queue i i n a s l o t , EL^ = average message length at queue i , varLj = variance of message length at queue i , varW i = variance of switching overhead from queue i to the next queue; for the time continuous system with Poisson a r r i v a l s , 32 * .. . i r i = a i + -EC varWj = EMj E L j 2 + - g g — (A.8b) E L j 2 = second moment of the message length at queue i . Proof of Lemma A.2: From the d e f i n i t i o n of {b^^ } given i n (3.13), we have Y R a? * \ . . a 2 ( s k + V . . .. a ( s k + Hk> 5< sk + V i j , ^ , ^ 5s, Bs, 3s . ^ 5s, 5s , 5s, 5s. J k=l "k i j i j i j and s u b s t i t u t i o n of (A.2) gives N 5 2F 5 2(s, + H ) b i 3 " H ( V E C + V ) - 5 T B ¥ T + V 5s as J k=l l j I j + V L 5s. ] <*-9> i J From (3.7 a)-(3.7c), we have F. + H, = F. = G, + G~ + ... + G., a i N L 2 N and therefore a 2 F k a 2 ( s k + \ ) = \ E C "aiT^T + "k SiT^T ! i J i J a 2 F k a 2 F N a 2 s k i J i J i J a 2F a2H i J i 3 (A.10) 33 Summation of (4.10) over a l l k and s u b s t i t u t i o n into (4.9) give 3 2F N o2H, b i i = ( p E C + EW> lis-oin - A V E C i i y os,5s . , S Tc 5s.5s . i J k=l I j N 5 ( s k + Hfc) 5 ( s k + H k) +, ^, ^ k 6s. 5s. k=l l j p r » r a \ . , a \ , N v - . . &< 8k 4 f lk> r A 1 M = E C J t - a s - s s - " \ a r s r ^ r ^ — a r a T " <A-n> k=l i j l j k=l i j From (3.7 a), we have a \ . .. 9 ( s k + V 5 ( s k + V . , & 2 ( s k + V as. as. K. as. as. \ as, as. i 1 i J i J and s u b s t i t u t i o n into (4.11) gives p r » ,. ^ V 5< sk + V a< sk + V i j = k=l ^ ^ ^ = E C ? a ( s k + V a ( s k + V . , ^, k 5s., as. k=l i j 4.4 The Jacobian Matrix A. To study the Jacobian matrix A, we have to look i n t o the properties of the functions {F^, {G^ and {H^. The functions {G±} and {li\ } are defined i t e r a t i v e l y by (3.7a) and (3.7 b). We start with and calculate G N from H then we obtain H N_ 1 from G^, then G from then from G ^ and G^ ., and the i t e r a t i o n goes on. After we have obained Gp G 2, G^ and Hj, H 2, . . . i 1^ we compute F^ by summing {Gi> over a l l i and then F i by (F^ - 1L). These are the basic steps we follow to calculate the elements i n A. 34 Lemma 4.3: The Jacobian matrix A i n (3.13) can be expressed as A = [ u 0 - u 1 | u 0 - u 2 | u 0 - u 3 | ... | u 0 - U J J ] where u 0 = Pi (l+Pl)P2 ( l + p 1 ) ( l + p 2 ) p 3 ( V ( l + P k ) ) P N ->• » u l = N-l 0 0 0 P2 (1+P2)P3 ( l + p 2 ) ( l + p 3 ) P 4 N-l ( n d+P k))P N k=2 k W o" 0 , u 2 (4.12) 0 0 P3 ( 1 + P 3 ) P 4 N-l ( n (i+Pk))P N k=3 Proof of Lemma 4.3: From (3.7a)-(3.7c) , we have dG . S(s . + H .) oH 3 _ £ » J 3 _ osj ai ~ 9 S i J i dF . 6T dH. 1 m N 1 (4.15) dSj QSj oSj Eqns. (4.13) and (4.14) imply 35 SB. , 5H. i J 1 J 5 F N a n d _ = ( i + dH + P 1 I ( i = D j > 1 (4.16a) (4.16b) It can be seen that u. . = (1 + p.)u. + p.e. (4.17) ->• where e. i s the i t h unit column vector. 3 The i t e r a t i v e r e l a t i o n s given by (4.16a) - (4.16b) and (4.17) are i d e n t i c a l and since u^ , = 0 = [ -g^- ], we conclude that i " i = t - s r ^ a n d uo= t - s r 1 ( 4- 1 8 ) J i i C l e a r l y , (4.18) and (4.15) imply the res u l t given i n Lemma 4.3 4.5 An A u x i l l i a r y Result. We derive an a u x i l l i a r y r e s u l t before the de r i v a t i o n of the difference equation r e l a t i n g the unknowns ^ v ^ j } * n t n e n e * t section. Lemma 4.4: Let = -z— and I(«) be the ind i c a t o r function defined e a r l i e r i n i 5s i ' Chapter 2. Then ( b i + l i + l 2 " [~^T 1 1 +1 ~ T ~ 7^ 1 1 J a 2 1 a 1 36 Ji+l )t.) + 2t P ) I ( i - l ) ] KN 2 i i al (A.19) Proof of Lemma A.4: oH. From the structure of given by (A. 18), we have i a s 1 + 1 = P l a s i a i ± i ^ ! l j < i < N (^-20) a i a s i From (A.8), N a(s k-r H k) 2 b « • E C j i t k [ — ^ T " ] i-1 oH. 2 oli = *C [ I t k(-g?) + t j (v * - 0 f o r k >1) (A.21) k=l i 1 Thus, a 2 ( V i m — r b i i } a i i oH, 2 i-1 a oH 2 a 2 ° H- a i + l 2 - E C ^ i -ar— + V i — r ' i ] i+1 a t a. 2 = - [ t 1 + 1 + ( P l + 1 - - ^ ) t l ] a i Using the same r e s u l t s from (A.18) and (A.8), we have 37 d(s + H ) b i i = E C t i — a l " < 4- 2 3> Thus, fa i + l a i + l 2 3 i . ^ ^~a~r b n + i — r ^7 11 J 1 a^ 1 _ a i + l , _ a i + l ^ i b l i + l ~ b l i j - l i l i E C t r _ l l ± i i ! l + - a j + i a H i i ~ a i 1 a s i + i a i ^ i + i a i 9 81 2 a ? = -EC t. (—) I( i = l ) i < N (A.24) 1 a l Combination of (A.2A) and (A.22) give (A.19) A.6 A Difference Equation for the Second Joint Moments of Terminal Service Times. It i s d i f f i c u l t , i f not impossible, to solve (3.13) i n closed form. An a l y t i c solutions are a v a i l a b l e for the symmetric case and for N=2 only. For the symmetric case, (3.13) can be solved quite e a s i l y by arguments based on symmetry i . e . v. . = v . . and v . . = v. ,, .... In f a c t , v . . i s i ndependent i i 33 i J i + k J + k i J of i and j so long as i t j for the symmetric case. The algebra involved for the very simple case of N=2 i s already very tedious and the solu t i o n i n this case suggests that there i s l i t t l e hope i n the search for a simple formula for the general asymmetric case. Numerical techniques and h e u r i s t i c approximations were developed but t h e i r d i f f i c u l t i e s have already been discussed i n Chapter 1. Here, we derive a simple difference equation 38 r e l a t i n g the unknowns ^ v j j ) * Although t h i s equation does not allow us to solve (3.13) a n a l y t i c a l l y , i t represents a big improvement over e x i s t i n g a n a l y t i c r e s u l t s . Lemma A .5 : The unknowns {v. .}, modified from {vJ . }, s a t i s f y the following i j i j r e l a t i o n : < D H D V + P i D V + PjDH><V ' i ti+l = -2 — I ( j - i ) + -=-=• I ( j = i < j < N (A.25) p i p i + l where v i j p.p .EC 1 J i * j v = { (A.25a) 1 , V i i . ^ C i P , 2 var Cj = variance of cycle time of queue i at steady state, D = the forward difference operator i n the f i r s t index, H = the forward difference operator i n the second index; that i s W • v i j - V i y Vv<V = D vD H(v 1 : J) = v. . - v l j + 1 - v i + 1 . + v 1 + 1 J + 1 . Proof of Lemma A.5: We define r. to be the i t h row vector of the matrix [ u 1 1 u 2 | u 3 1 . . . | i ^ J , 39 ^IN • - T = as i n Lemma 4.4 and 1 = (1, 1, 1) . Using these d e f i n i t i o n s , i we can write the i t h row vector of A as ~ Th 6 1 1 from (3.13), we have v.. = (a. f T - r . T ) V ( a . f - r,) + b.. i i l i i i i i = a . 2 f T vf - 2a.f TVr. + r . T V r . + b.. (4.26) l l l l l i i and v u = ( a ^ 1 - r 1 T ) V ( a 1 f - r^) + = f Tvf - a 1 ? T V r + b u (v = 0) (4.27) Elimination of l ^ V r ^ using (4.26) and (4.27) gives a. T a. (v - 2 — v,.) = -a. 2 f vf + r7Vr. + (b. . - 2 — b..) ( 4 . 2 8 ) v i i a li.' l i i i i a^ l i ' Replacement of i by i+1 i n (4.28) gives < ' i + l i + l " 2 i f 1 V l i + 1 > " - a i + l 2 f T v f + r 1 + l V * i + l + < b l + l i + l " 2 a f \ i + l > i < N (4.29) Elimination of ? TV? using (4.28) and (4.29) gives 3 3 ^ 3 ( v i + l i + l - 2 I — v l i + l > T < V ^ " 7^ 1 a. * 1 l 3 ^ 3 3 ^ 3 •*• T + i+1 -• „ i+1 . , i+1 , u 9 1 K i = r i + l V r i + 1 T V r i + ( b i + l i - r l " 2 T. b l i + l } ^ i * aT a. 1 a. * 1 l i a 2 = r . ^ V r V , --i±^Lr. TVr. + b. . i < N (4.30) 1+1 1+1 o i l 11 a. * l where AO 2 \ i = < V i i + i " 2 TT b W - ~ r ( b i i " 2 b i i } 1 ^ 1 a 2 a 2 = EC [ t ^ + ( p 1 + 1 t±) + 2 ^ ^ ) I ( i = l ) ] i < N (A.30a) V 1 Eqn. (A.30a) i s obtained by Lemma A.A. Now, T a 2 r i+l V r i+l T r i a. z l N N OR. dH 0 a. . 2 dH, dH . Y Y r 1+1 k A -I =,^ . // as,,, as... 2 ^ os- J V k* k=l A=l i+1 l+l a^ i l i i dH. dH 0 a. . , 2 dH. dH 0 dH . = y * i ± l _ k * ] v ( v ^ - O f o r j ) ! ) k=l W d S i + l 3 s i + l a ^ 2 i i i i-1 dH i-1 dH dH^ dH, dH, _ y K I + y i * + i i \ i i d s i + i d s i + i V k l xii ^ i + i a s i + i V i i L ^ i + i ^ i + i V i l by (A.20) 5H. i-1 SH k dH. 2 = 2 *^Ti J i ^ I + T V k l + ( " ^ + T ) V l i i-1 a b\ = 2 p i + i ^ i r ^ r v ^ i + i S i by (4-2o) k=l i i g = 2 7 I L ± I Pi+1 ' i ^ i + P i + 1 2 V i i (A.31) Su b s t i t u t i o n of (A.31) into (A.30) gives a i + l . a i + l 2 ( v i + n + i - 2 7 — vn + i > r ( v i i " T: V I I } 1 a / 1 i a. = 2 I T 1 p i + i r l v*i + p i + i S i + bii 1 < N (A'32) Al The next step i s c r u c i a l i n t h i s proof. We notice that a l l the variables i n (A.32) are functions of {p^} and {t^}. By c y c l i c symmetry, eqn. (A.32) should hold i f we perform a c y c l i c s h i f t of indices i . e . replace p by p^+2.» p^ by p^ and s i m i l a r l y for {t^}. We denote t h i s c y c l i c s h i f t of indices by the operator CS(»). We further notice that C S ( V • v i + i j + i 1 » J < N ( 4 - 3 3 ) CS(p.) = p i + 1 i < N and C S ^ ) = P]_ (A.34) CS(t.) = t. ^ . i < N and CS(t. ) = t. (4.35) cL c l Csf - i i i ) = - i i 2 - i < N-l (4.36) a i a i + l With these i n mind, we perform the c y c l i c s h i f t of indices on (A. 32) and £,et 2 (v, + 9 , + 9 " 2 CS v ) - !i+L^ ( v - 2 C S 1 a i + l - 2 — P i + 2 C S < V V e V + P " i + 2 v l + l i + l + C S ( b i i ) 1 < h ~ l ( 4 < 3 7 ) a i + l i+2 •*• T..+ , . 2 Replacement of i by i+1 i n (A.32) gives ai+2 \ a i + 2 2 , „ a i + l ( vi+2i+2 " 2 a — V l i + 2 ) : ( v i + l i + l ~ 2 — V l i + 1 } 1 a. *• i+1 - 2 — P,„ r ^ / v e * + R , „ V 1 U 1 + b~ + 1 i < N-l (4.38) a i + l i+2 i+1 i+1 Ki+2 i+li+1 i+li+1 Noticing that CS(b' i i) = ^ for KKN-1, we can subtract (A. 37) from (A.38) and get 1 1 a 2 ! 1 42 " 2 Pi +2 ( rVlT v eVl " 1< i < N-l ( 4 . 3 9 ) Now, -> T + T •* r i + l V e i + 1 - c s ( r i V e i > i d l ^ 1-1 oH^ . = E l i — Vki+1 ~ C S ( I IT v k i ) k-1 1+1 k-1 1 Y V a H k + i " k - i ^ i + i V k i + 1 " k i i a s i + i V k + 1 1 + 1 i 5H, i 5H^ v. = y v - y k= OH k-1 ^1+1 k l + 1 k=2 5 S 1 + 1 k l + 1 1 v. & s i + l 1 1 + 1 1 + 1 v, . i < N (4.40) 1+ P l li+1 Moreover, a, a CS f—) = - i i i 1 < N (4.41) V V a2 Substitution of (4.40) and (4.41) into (4.39) gives , V l i + 2 V 2 i + 2 ^ ^ , a i + 2 r V l i + l V 2 i + 1 , - ^ 2 ^ a 7 ) + 2 a i + 2 7 ^ ^ = 2a „ ~ v 1 J M 1 < i < N-l (4.42) i+2 1+p li+1 S i m p l i f i c a t i o n of (4.42) gives 43 ( l + P l + P 1 + 1 ) v 1 1 + 1 - d + P 1 + 1 ) v 2 l + 1 - d + P ! ) v 1 1 + 2 + v 2 1 + 2 = 0 1 < i < N-l (4.43) (l - r p 1 - r p.)v l i - d + P l ) v 2 1 - < 1 + P l ) v 1 1 + 1 4 v 2 1 + 1 = 0 2 < 1 < N (4.44) Similar c a l c u l a t i o n s can be done for i = 1 and i = 2 and the r e s u l t s are very s i m i l a r except f or the residual terms on the right hand side of the equation. The r e s u l t s are c2 (1 + P l + P 2 ) v 1 2 - ( l + p2) v 2 2 - (1+Pj)v 1 3 + v 2 3 = — (4.45) t. ( l + 2 P l ) v n - ( H - P l ) v 2 1 - ( 1 + P l ) v 1 2 + v 2 2 = -2 — (4.46) Combination of (4.44), (4.45) and (4.46) gives < DH DV + P l D V + P j D H ^ l j £1 C2 = _ 2 _ i i ( j = l ) + _ £ I(j=2) j < N (4.47) p l p2 Cy c l i c s h i f t of indices on (4.47) y i e l d s (4.25). var Cj We would also l i k e to show v.. =—57— given i n eqn. (4.25a). From i i fcL (4.26), we have v n = a ^ f v t + b n = P. 2 ? T V l " + t, EC. Thus v EC = tTvt 44 ' A A a s i d s j N N o = I I [ a^--&-P-^-] i = l j=l & S i d S j & S i d 3 j = lim I f { E I T . ^ T . ^ ] - E [ T < k ) ] E [ T <k>]} k*» i - i j=l 1 J 2 N 2 ( k) = l i m { E[( f T < k )) ] - ( E [ £ ' T ^ ] ) } k+» i - l i - i = lim var var C n => v 11 EC var C. = > v i i = - T c - < 4 ' 4 8 > Lemma 4.5 i s a major contribution of this t h e s i s . No such simple r e s u l t r e l a t i n g the jo i n t moments of terminal service times has been reported before. Eqn. (4.25) i s a two dimensional l i n e a r but s p a t i a l l y variant difference equation. It can be solved up to N a r b i t r a r y constants. To see t h i s , we rewrite (4.25) as - H ^ i j ^ V i j ^ i + i j + i ^ p — ^ = i + 1 > < 4' 4 9 a> * i j + l = ( l+2p, . _ i fci It H ^ v i l + ! ¥ - v 1 + u + 1 ] + ~ i - J (4.49b) Using (4.49b), we can express v i i + ^ including CS(v N_^ N) i n terms of the diagonal elements. Then we can use (4.49a) to express other off-diagonal elements and th e i r c y c l i c - s h i f t e d counterparts i n terms of the diagonal elements i n a successive manner. Thus, we can assign N a r b i t r a r y values to 45 the diagonal elements and generate a so l u t i o n to (4.25). In other words, (4.25) i s not a complete set of equations that characterize a unique s o l u t i o n . However, we can use (4.48) to generate N equations r e l a t i n g v to other off-diagonal elements. This suggests a new numerical algorithm for solving (3.13). We start with a guess of the diagonal elements, compute a l l other off-diagonal elements by (4.49a) and (4.49b), update the diagonal elements by (4.48) and repeat the same procedure. The c r i t e r i a for convergence of th i s numerical procedure has not been established but experiments have shown that not only does the procedure converge f o r p < 1, i t also converges much faster than the algorithm given i n [29]. Eqn. (4.25) i s not only useful for numerical solutions, i t can also be used to solve (3.13) e x p l i c i t l y for special cases and to obtain approximate s o l u t i o n for the general case. In the next section, we use (4.25) to solve (3.13) for the symmtric case. An approximation based on (4.25) w i l l be presented i n the next chapter. 4.7 Solution for the Symmetric Case. As remarked e a r l i e r , (3.13) can be solved e a s i l y for the symmetric case. We do t h i s i n the following Lemma. Lemma 4 .6 If p and t j are independent of i , then the s o l u t i o n of (3.13) i s given by ( i n terms of v. .) 46 where r. . - . w -i T + T - I - K i * j ) (4.50) i j ( l + P i ) ( l - p ) 1 + Pi Pi p = Np ±, t = Nt i. = v. Proof of Lemma 4.6: By symmetry, v n = v 2 2 ... . N N -From (4.49b), we have 1 li V i o = v O Q = • . . = v.. 1 X = v. . + - r — (4. 51) 12 23 N-1N i i 1 + P i Pi From (4.49a), we have , t. ^ ""^ 1 1 IJ 24 N-2N i i 1+p Successive c a l c u l a t i o n s using (4.49a) show that v. . = v.. + ~ ' i * j (4.53) i j n 1+p. p. Furthermore, v = ±- f Tvf 11 EC N N N t. l = y y p. p. v.. + y t. i i i j i i P I P J ^ i ^ 1 = N ( p 1 2 y n + t 1 ) + N ( N - l ) P l 2 ( v 1 1 + I ^ - - ^ ) - P ^ l l - ^ A V l l d + P l ) ( l - p ) Combination of (4.53) and (4.54) gives (4.50). (4.54) 47 5. MEAN DELAY ANALYSIS. 5.1 Relationship between Mean Message Delays and Service Time Moments. As remarked i n Chapter 1, our goal i s to analyze the mean message delays on a token-ring. In the l a s t chapter, we concentrated on the solution for the second j o i n t moments of the terminal service times, because there i s an intimate r e l a t i o n s h i p between the mean message delays and these moments. This r e l a t i o n s h i p i s stated i n Lemma 5.1. Lemma 5.1: The mean queueing delay (excluding service) of a message' at queue i i s given by E D _ ( s l o t ; = j ( 1 + p i ) ( ~ i . + E c ) + ^ { i EL 1 - 1) (5.1) i for the discre t e time slot system and ED.(Poisson) " I d + P i X v ^ + EC) (5.2) for the continuous time system with Poisson a r r i v a l s . A l l quantities i n (5.1) and (5.2) are defined e a r l i e r i n Chapter 4, EC i n Lemma 4.1, var M , EM^ and EL^ i n Lemma 4.2 and v ^ i n Lemma 4.5. Recall that the delay i n a di s c r e t e time s l o t system i s measured i n sl o t s whereas the delay i n a time continuous system i s measured i n seconds. Thus, the quan t i t i e s i n (5.1) and (5.2) may have d i f f e r e n t numerical values even i f they represent the same thing. This i s important for system conversions such as t r e a t i n g the time continuous system as a l i m i t i n g case of the d i s c r e t e time slot system. 48 Proof of Lemma 5.1; The d e r i v a t i o n of eqn. (5.1) can be found i n [27] but we s h a l l include i t here to make th i s thesis self-contained. P h y s i c a l l y , the average mesage delay at a queue on a token r i n g i s the r a t i o of the sum of a l l message delays over many cycles to the number of messages served i n the same period of time. Let N be the number of cycles T we measure the message delays, ED^ be the expected t o t a l message delays i n a cycle and EZ^ be the expected number of messages served i n a cy c l e . Then the average message delay ED^ i s given by T T N ED ED E D i = IT EZ" - = E Z ~ <5-3> c i i T Quantities ED^ and EZj are independent of the cycle because we are only interested i n the steady state. For t h i s reason, a l l superscripts k denoting the kth cycle w i l l be dropped. From (2.1), (2.2) and (2.5), we have EZ = EYj = EC± EMj (5.4) T The quantity ED., i s more d i f f i c u l t to c a l c u l a t e . We sum a l l the message i n a t y p i c a l cycle and l e t p Cj = previous c y c l e , P Mj ^ = number of messages arri v e d i n the j t h s l o t of the previous c y c l e , Zj = number of messages served i n the current c y c l e , r L. . = the length of the j t h message being served i n the current cycle. 1 > 3 49 The delay of a message consists of two parts: waiting time f o r the beginning of current service cycle and the sum of service times of messages buffered up front of the queue. By separating these components, we can see that the t o t a l delay i s given by Z - C - 1 T r P P r r C D. = I (C - j) M + I L (5.5) 1 j-1 1 1 , 2 j-1 k-1 1 } Taking expectation of (5.5) gives ED = Z [ \ cJ(cJ-l)EM1 +4 Z ^ z J - U E L j (5.6) Since Z therefore = E[cJ EM2 + C j ( C j - l ) ( E M 1 ) 2 - C^EMj = E[Cj(var K± + CjCEM^) 2- EM^ ] (5.7) Substitution of (5.7) into (5.6) yi e l d s the following a f t e r some s i m p l i f i c a t i o n : EC. EM i (5.8) Substitution of (5.8) and (5.4) into (5.3) gives (5.1). 50 Eqn. (5.2) can be derived from (5.1) as a special l i m i t i n g case. To do t h i s , we f i r s t l e t the number of message a r r i v a l s i n a slot be Poisson. Then the term (var - EM^) becomes zero. Next, we l e t the time s l o t go to zero while keeping the absolute value ( i n seconds) of the cycle time f i x e d . Thus, the constant (- -ijj) e f f e c t i v e l y disappears from (5.1) and (5.1) Is converted to (5.2) with the units changed from time s l o t s to seconds. 5.2 A Fundamental Relation for {v^}-Eqns. (5.1) and (5.2) show that v ^ i s an important element of the mean message delays. In f a c t , i t i s the only unknown appearing i n the mean delay expressions. Therefore, i t i s hel p f u l to have as much information on {v„ } as p o s s i b l e . Based on Kleinrock's conservation law [15], a simple r e l a t i o n for ( V J J } can be derived. This i s stated i n Lemma 5.2. Lemma 5.2: The unknowns ^ v ^ j ^ s a t i s f y the following equation: j / i ^ i ^ i i " T^p ( 5' 9> where N p = 1 p = t o t a l system u t i l i z a t i o n , 1 = 1 1 N t = I * i • i=l Proof of Lemma 5.2: Let us c a l l the general time s l o t system we are considering System A and denote i t s parameters with superscript A. We now a r t i f i c i a l l y construct System B with parameters superscripted by B from the following s p e c i f i c a t i o n s : ( i ) System B i s time continuous with Poisson a r r i v a l s , It i s important to r e a l i z e that System B i s r e a l i z a b l e i . e . no ove r s p e c i f i c a t i o n s or inconsistencies i n the parameters. Since the numerical values of {v^} depend only on {p^} and {t^}, we ~ A ~ 3 ' - 3 conclude that v^^ i s equal to v^^ for a l l i numerically. Furthermore, v i s independent of the fixed overhead W^ , which i s the only overhead i n System B. Thus, i f we l e t EW^ go to zero, the mean delay at each queue i n System B w i l l 1 B ~ B B be given by (I4p^) v ^ . With EW^=0, System B i s now a work conserving system i . e . the server w i l l not be Idle so long as there i s a customer i n the system. We are now ready to apply the conservation law. Kleinrock's conservation law states that i n a work conserving multi-queue system, the i n t e n s i t y weighted mean of the average delays of a l l the queues i s independent of the way the queues are served. The law also states that for any M/G/l system with no preemption, the i n t e n s i t y weighted mean of the average delays i s given by ( i i ) P ( i i i ) var j=l where N . EL. 2 We notice from (A.8b) that 2 B Zi = P i B E ^ ! ) EL' B S u b s t i t u t i o n of (5.11) into (5.10a) shows o A 2 C i 2 1 1=1 and therefore N p I 1=1 p Therefore, N p 1»; B i 1 1 B ~2 Z 1-P B r 1 1 , B. ~B i-1 p N 1 B B 1-p r B / I _ L B ~ B p t -» 2, P 1 ( 1 + P 1 ) V = J I — i i B. B B 1=1 * * 1-p Replacing the superscripts B by A gives the desired r e s u l t . (5.10a) (5.11) (5.12) (5.13) (5.14) 5.3 An Approximation for { v^j}. To obtain exact solutions for { V J J }> ( 3 . 1 3 ) or equivalent equations must be solved. We cannot provide a closed-form a n a l y t i c s o l u t i o n . However, a very good approximation based on Lemma 4.5 can be derived. We start by considering the di f f e r e n c e ( v 2 2 - v ^ ) . From (4.26) or (4.27), we have 1 *T (5.15) and 53 v 2 2 = — CS(?TV1) ' (5.16) where CS(») Is the cyclic shift operator defined in Sec. 4.6. Subtraction gives ( v 2 2 - v n ) = ^ (CS(f TV?) - 1TV1) N-l N = E c t . ^ C S ( V - . = ^ l j ] - 2 [jIiCS(p.pNv.N) -l^ P lp. v x.] = 2 [ ^ P x P ^ S ^ . ^ - ^ p . p . v , . ] = 2 P1 ^ P j + J C S ^ N > - ^ l j + J <5'l7> Now, assuming that the total u t i l i z a t i o n i s low, a l l the coefficients appearing in (4.49a)-(4.49b) can be essentially replaced by unity and thus 'i+l V i j * V i + l j + V i + l j + l " p ^ ; I ( j = i + 1 ) 1 < J v.. + 1 - { (5.18) 1 ~ Zi i ( v i i + v i + n + i ) + T : 1 = J Successive calculations of the off-diagonal elements using (5-18) gives v ~ i j 4<*ii + v + -pf 4 < J ( 5 - 1 9 ) Substitution of (5.19) Into (5.17) gives ( v 2 2 - v n ) - 2 P l Y P J + 1[CS£ ( V j ^ ) + 1*) ( v n + v . + 1 . + 1 ) - Ii ] N _ 1 C4+1 t7 54 N-l tl N-l = 2 p i [ ^ V i ^ P J + I ] = 2 P l [ ( t - t ^ - l l ( p - P l ) ] P i t = 2pt (— - —) (5.20) •P By c y c l i c symmetry •P Using (5.21), the l e f t hand side of (5.9) can be computed as follows: ^ i + i i + i " v ~ i i * 2 p t £ " 7 ^ ( 5 > 2 1 ) N N i-1 p. t . I P i d + P i ^ j i - I PjCl+Pj) [ v n + 2pt I ) ] i = l 1=1 j=l N N i-1 p. t . = i p (i+p ) v + 2 Pt i j Pi(i+Pi) ( - ^ - r 1 ) < 5 ' 2 2 > i-1 i-1 j=l p Thus, (5.9) can be used to ca l c u l a t e as * u te t T V 2PT I ^ p i ( 1 + p i ) ("S1--^ )] / I p i < 1 + p i > ( 5- 2 3> p i-1 j-1 H i-1 By c y c l i c s h i f t i n g of i n d i c e s , we can compute ^22' v33' '*'» VNN* Unfortunately, the double sum In (5.23) cannot be s i m p l i f i e d for general cases so we have to leave i t as i t i s . 5.4 Comments on the Approximation for { v^}* It i s important to e s t a b l i s h or have some i n d i c a t i o n on the region of v a l i d i t y of our approximation given by (5.21) and (5.23). Clearly, our approximation i s exact for the symmetric case. From the l o w - t r a f f i c assumption we made to e s t a b l i s h (5.18), our approximation should also be very 5 5 good at low t r a f f i c l e v e l s . Although (5.21) i s not exact, i t suggests that the di f f e r e n c e s among ( v ^ } are small compared with the actual values of {v^ } at very high t r a f f i c l e v e l s (p •*• 1). With t h i s assumption and using Lemma 5.2, we can write N ' i i K ~l-p ' J 1 P i ( 1 + P i > ( 3 ' 2 4 ) for p close to unity. This matches the dominant term i n (5.23). Thus, we expect (5.23) to work well at high t r a f f i c l e v e l s as w e l l . As a matter of f a c t , comparisons with exact numerical r e s u l t s have shown that the approximation given by (5.21) and (5.23) i s very good over a very wide range of the parameters ( P j ) a " d {t^}•. These comparisons w i l l be discussed in the next section. A nimber of i n t e r e s t i n g properties of {v^^} can be deduced from (5.21) and (5.23). Eqn. (5.23) shows that v ^ consists of two parts. The f i r s t part i s a hyperbolic function independent of i that grows unbounded as p •+ 1. The other part i s the p o s i t i o n dependent part given by a double sum. Eqn. (5.23) i s also l i n e a r i n t ^ , which conforms with the l i n e a r i t y of the exact equation (3.13) with respect to t ^ . Eqn. (5.21) gives a somewhat d i f f e r e n t flavour about }; i t shows the r e l a t i o n of v^^' s between adjacent queues. For example, (5.21) suggests that a queue 'suffers' i f the preceding queue has a large f r a c t i o n of the t o t a l u t i l i z a t i o n but 'benefits' i f that preceding queue has a large t ^ . If t^ i s d i r e c t l y proportional to P i, (5.21) predicts that v ^ i s approximately independent of i . This special case corresponds to the time continuous system with Poisson message a r r i v a l s , fixed overheads and a constant message length for the whole system. 5.5 Comparison of Approximation and Exact Numerical Results for {v^}* In t h i s section, we compare the approximations given by (5.21) and (5.23) with exact numerical r e s u l t s . The biggest problem i n the comparison i s the search for representative cases, because we cannot possibly do the comparison for a l l conceivable combinations of parameters. Besides the number of queues N i n the system, the parameters needed to solve (3.13) are (Pj) and { t j } . These parameters cannot take on a r b i t r a r y values. F i r s t of a l l , they are a l l p o s i t i v e . Secondly, the t o t a l u t i l i z a t i o n p of the system should be less than unity. Even with these r e s t r i c t i o n s , the parameter space i s s t i l l unmanageably large. Since the approximation i s exact for the symmetric case, we c e r t a i n l y should look into highly asymmetric cases. Furthermore, we notice from (4.8a) that var Mj var L. var W^ This suggests that t^ can be very roughly regarded as a li n e a r combination of var M. - var L. var W. o i i i p . , P j , 1 i f the normalized variances j , —gj- and — — do not vary 1 (EM.) i l appreciably among the queues. For this reason, we s h a l l look into cases for t j a P j 2 , t ^ <* p ^ and t ^ « 1. With these considerations i n mind, we do the comparisons for a l l possible combinations of the following parameters: ( i ) N = 8, 16. ( i i ) t ± cc ? 2 t p ^ i , ! / p ^ l / p ^ . 57 ( i i i ) 0.01 < p < 0.99 with steps of 0.01. ( i v ) 1 large user with u t i l i z a t i o n 100 times that of other i d e n t i c a l users, 1 small user with u t i l i z a t i o n 0.01 times that of other i d e n t i c a l users, 2 c l u s t e r s of i d e n t i c a l users with u t i l i z a t i o n r a t i o of 1:5. In each case, the r e l a t i v e errors (absolute value) between the approximation and the exact numerical s o l u t i o n are computed for a l l queues; then the maximum and the average of these r e l a t i v e errors among the queues are plotted against the t o t a l u t i l i z a t i o n . There are f i v e curves, l a b e l l e d from 1 to 5, i n each graph. Curve 1 corresponds to the case of t^ « P±^' 2 to t^ « p^, 3 to t^ « 1, 4 to t j <* 1/Pj, 5 to t j « 1/p j 2 . The plots are shown at the end of t h i s section. Some of the curves i n these plots are too close to be l a b e l l e d separately so they w i l l be l a b e l l e d as a group. As expected, our approximation works well under very l i g h t and very heavy t r a f f i c , as shown In the p l o t s . The p l o t s also show that the approximation i s very good for t <= p 2, t <* p , t « 1 as well as for a l l i i i i i cases of a single large user. When t^ , <* 1/p^ or t^ <* 1/p^ 2 , the maximum r e l a t i v e errors at medium system u t i l i z a t i o n s of 0.7-0.8 can be as high as 12%. Fortunately, these are rather u n r e a l i s t i c cases. For example, i n the D-net protocol, var W^ = 0 and so from )(4.8a) var M var ti = p i 2 TEMTT2 + p i ~EL7~ • Therefore, t tends to be small i f p^ i s small and t h i s contradicts the inverse r e l a t i o n s given by t. « 1/p, and t. * 1/p, 2. Even with these 58 u n r e a l i s t i c system parameters, our approximation can s t i l l give reasonably accurate r e s u l t s (errors of about 10%). For more r e a l i s t i c parameters, our approximation i s excellent (errors of 1 to 2%). Thus, i t i s not unreasonable to treat our approximation as though i t were exact for many ap p l i c a t i o n s . .5.1b E versus p for N=8 and 1 single large user, avg 60 61 F i g . 5.3a E versus p for N=8 and 2 c l u s t e r s of Identical users. & max 6 . 0 - = j . 5.3b E versus p for N=8 and 2 c l u s t e r s of I d e n t i c a l users, avg F i g . 5.4a E versus p for N=16 and 1 single large user, avg 63 64 F i g . 5.6b E versus p for N=16 and 2 c l u s t e r s of i d e n t i c a l users. 65 5.6 Delay-vs-Throughput Results. Eqns. (5.1) and (5.2) show the r e l a t i o n between average message delays and the unknowns {v ^ } while eqns. (5.21) and (5.23) give approximate expressions f o r ^ V J J}* By combining a l l these equations, we can obtain an approximate sol u t i o n for the average message delays. We copy (5.1), (5.2), (5.21) and (5.23) here for easy reference: . . . . var M. - EM. E D ( s l o t ) = 1 ( l - ^ K v ^ 4 EC) + j ( i E ^ - l ) (5.1) i ^ ( P o i s s o n ) . 1 ^ ) ^ + E C ) ( 5 . 2 ) W I - V ^ T ) ( 5 ' 2 1 ) - i i • [ £ - P - X X p i ( i + p ^ {^-^)] ' U ( i + P i > 1=1 J=l i=l There are a nunber of special cases worth atten t i o n . (5.23) We f i r s t consider the case where v ^ i s independent or approximately independent of i . With this assumption and using Lemma 5.2, we get (5.24). We can rewrite (5.24) as N v. . - - r ^ - / (1 + I p , 2 / p ) (5.25) 1 1 1 _P i = i 1 Substitution of (5.25) into (5.1) and (5.2) gives / -, i T].t i var M. - EM E D ( s l o t ) m l ^ ^ + l ( EL^-1 ) (5.26) i and TI t (Poisson) B j i new ( 5 > 2 7 ) i 2 1-p where 66 N ? n. = (1+P.) / (1 + I P./p), 1 i=l tnew = t + EWd+j^ p 2 / p ) . The f i r s t term on the righ t hand side of eqn. (5.26) i s the queueing delay of an»M/G/l single-queue system with appropriate parameters. The second term i s due to the non-Poisson nature of the a r r i v a l s , which can be p o s i t i v e or negative. The t h i r d term arises because a l l message a r r i v a l s are registered at the end of a time s l o t . For the time continuous system with Poisson a r r i v a l s , the l a s t two terms vanish, as noted e a r l i e r . For very heavy system t r a f f i c (p+1), v i s approximately independent of i , as remarked e a r l i e r . Thus, (5.26) and (5.27) are v a l i d for this case. Moreover, the hyperbolic term dominates the right hand side of (5.26). Therefore ( s l o t ) _ 1 T 1i tnew , E D i ( 5 , 2 8 ) and •n t (Poisson) „ 1 'i new (5.29) i 2 1-p Eqns. (5.28) and (5.29) show that the average delays for both s l o t and Poisson a r r i v a l s are approximately proportional to (1+p^) as p •*• 1. This i n turn implies that i f a system has a user with u t i l i z a t i o n close to unity, the delay suffered by t h i s user i s roughly twice the delay suffered by other users. For very low system t r a f f i c (p •*• 0), (5.21) implies i s 67 approximately independent of i . Thus, (5.26) and (5.27) are again v a l i d in this case. Furthermore, 1 T 1i tnew 1 j \"p - j (t + EW) (5.30) By making the reasonable assumptions that var •* 0 as EM^ •*• 0 and var Lj > 0 as EL^ •*• 0, we can further approximate t for p •* 0 by i N 1 V TT V a r W / C O I N E C lml v a r w i w - s r ( 5- 3 1 ) where N EW = I EW i-1 N varW = 1 varW.. i-1 1 Therefore, varM — EM E D i ( s l o t ) . 1 (varW + ^ + 1 ( i _ _ i ^ and £ (Poisson) 1 (varW + £ W ) ( 5 l 2 v EW ' If var W = 0, then (Poisson) m 1 E W ( 5 > 3 4 ) Eqn. (5.34) i s i n t u i t i v e l y c l e a r but (5.33) shows a more subtle result i f var W * 0. For the time s l o t system, more information i s needed on the a r r i v a l s t a t i s t i c s i n order to si m p l i f y (5.32) any further. For the system with a single dominant user, that i s , p^ and t^ for the dominant user are much greater than p^'s and t ^ s for the other users, eqn. 68 (5.21) again implies that are approximately Independent of I. Thus, (5.26) and (5.27) are v a l i d in th i s case. Furthermore, 1 ^ i t new 1 t + EW(l + p) 2 iTp~ 2 1=^ for the dominant user and 1 Vnew 1 1 + Pi t + EW(l + p) , _ (5.36) for a l l other users. For the system with N-l i d e n t i c a l users and a single small user, that Is, p, and t. for the small user are much less than p.'s and t.'s for the i l r i i other users, eqn. (5.21) implies once more that v ^ i s approximately independent of i . As a r e s u l t , (5.26) and (5.27) are v a l i d . Furthermore 1 Vnew _1 1 t+EW(l+p/(N-l)) 5 . 2 1-p " 2 1+p/(N-l) 1-p 1 ; for the small user and 1 Vnew 1 t+EW(l+P/(N-l)) ,. 2 i-p 2 — — r ^ p ( 5 , 3 8 ) for the other i d e n t i c a l users. For t j * p^, eqn. (5.21) again implies that v.... i s approximately independent of i so eqn. (5.26) and (5.27) are again v a l i d . For the system with c l u s t e r s of i d e n t i c a l users, eqn. (5.21) shows that v ^ i ' s obey a l i n e a r r e l a t i o n s h i p within each c l u s t e r . This l i n e a r r e l a t i o n s h i p i n turn shows that the delays given by (5.1) and (5.2) are l i n e a r within each c l u s t e r of i d e n t i c a l users. 69 In most of the s p e c i a l cases considered so f a r , v^^ i s approximately independent of i . This i s v e r i f i e d for the following combinations of parameters: ( i ) N-8. ( i i ) t 4 = pj, P i , 1. ( i i i ) 0.01 < p < 0.99 with steps of 0.01. ( i v ) 1 large user with u t i l i z a t i o n 100 times that of other i d e n t i c a l users, 1 small user with u t i l i z a t i o n 0.01 times that of other i d e n t i c a l users. 2 c l u s t e r s of i d e n t i c a l users with u t i l i z a t i o n r a t i o of 1:5. There are two plots for a l l combinations of ( i i i ) and ( i v ) . The f i r s t plot consists of the exact numerical s o l u t i o n for {v^ } versus p (8 curves) and the second plot consists of the normalized variance of i V j . j } versus p. The normalized variance of ) i s defined as v a r < * i i > = ^ 2 \ <'ii-»> 2 ( 5 ' 3 9 ) Nm 1=1 where 1 N ~ 70 71 F i g . 5.3a v.. versus p for N=8, 1 single large user and t j - P ^ , r t V ) 110' 32. C -H 24. C -H 1 6 . G e. o —j 0 0 ~ | l l . l | r i i T T 7 M M l M , . I M I | i m M N . | I U l l l m | l I l ' l " 1 1 1 " " ! " M | I M I I M I I | M l l l l i n | l , l l i n 0.0 0.1 0 .2 0.3 0.4 0.5 0.6 0.7 0.8 0.S 1.0 F i g . 5.8b v a r ( v l j L ) versus p for N=8, 1 single large user and t^p^ 72 73 7 4 0 . F i g . 75 F i g . 5.12a v.. versus p for N=8, 1 single small user and t =1. 76 F i g . 5.13a v.. versus p for N=8, 2 c l u s t e r s of i d e n t i c a l users and t j - p . 2 . v o r t V ) 110"') 6.0-3 F i g . 5.15a v.. versus p for N=8, 2 c l u s t e r s of i d e n t i c a l users and t i = l . 79 5.7 F i n i t e Buffering and Non-exhaustive Services. We have assumed i n f i n i t e buffering and gated exhaustive service throughout t h i s t h e s i s . Nevertheless, we can use our re s u l t s to approximate the more r e a l i s t i c cases of f i n i t e buffering and non-exhaustive services. We start by considering the f i n i t e buffering case. Two kinds of buffer designs are possible, message buffering and s l o t buffering. As the i r names imply, a message i s the fundamental unit i n message buffering and a slot of a message i s the basic unit i n s l o t b u f f e r i n g . While s l o t buffering appears to be more e f f i c i e n t i n terms of memory requirements, message buffering allows for h i e r a r c h i c a l buffer management. We s h a l l consider message buffering here. Let us modify the i n f i n i t e buffering system we have considered to a f i n i t e buffering system with n^ message buffers at queue i . As long as the blocking p r o b a b i l i t y i s small, we can approximate the f i n i t e buffering system by the i n f i n i t e buffering system. We further approximate the blocking p r o b a b i l i t y at queue i by (block) „ 1 1 b p r o b ( x 0 0 > ) ( 5 . A 0 ) This approximation i s based on the assumption that the queue length i s a l o c a l maximum at the scan ins t a n t s . From (2.1) - (2.5) and previous a n a l y s i s , we have EX, = EM. EC (5.41) i l and var = var Y^ = var M± EC + (EM^) E C ^ = var H± EC + var C± (Eti±)2 + ( E M 1 ) 2 ( E C ) 2 = [var H + ( E M 1 ) 2 ( v i i + EC)] EC (5.42) where a l l variables are defined e a r l i e r . The blocking p r o b a b i l i t y given by (5.40) can be bounded using (5.41), (5.42) and Chebyshev's in e q u a l i t y which states that °x 2 Prob(|X-m | > 6) < (5.43) X 6 Z where X i s any random variable, i s the mean of X and a Y 2 i s the variance of X. By choosing n^ large enough, we can l i m i t ^(b-*- o c k) t o a n acceptable l e v e l . No t i c e that {n^} depends on (p^) and { t^} . Thus, we cannot choose a fixed set {n^} to keep {u^k^ o c , c)} small for a l l loading conditions. In f a c t , n^ grows unbounded as p + 1. The problem of approximating non-exhaustive services by the gated exhaustive service scheme i s s i m i l a r to the approximation for f i n i t e b u f f e r i n g . Let us consider the general gated non-exhaustive service where up to p^ messages are served i n each c y c l i c service of queue I. Let v^ be the p r o b a b i l i t y that the scan queue length (number of messages buffered at the scan instant) at queue I i s greater than p^. As long as v^ i s small for a l l i , we can approximate the gated non-exhaustive service reasonably well by the gated exhaustive service. We further assume that can be approximated by 81 v± » 11m Prob (X v J> p ) (5.44) k-*= Again, can be bounded using (5.41), (5.42) and (5.43). By choosing the appropriate i p ^ } and {t^ }, we can l i m i t within the desired l e v e l . Thus, we can obtain a region of loading conditions under which the gated non-exhaustive service can be approximated by the gated exhaustive service. In general, for a s u f f i c i e n t l y small p, the gated non-exhaustive service can always be approximated by the gated exhaustive service. For heavy t r a f f i c , one can use various heavy t r a f f i c approximations; see for example [15]. For intermediate t r a f f i c , i n t e r p o l a t i o n techniques could be used. 82 6. CONCLUDING REMARKS. 6.1 Summary of the Results. Recently, applications of f i b e r optics to LANs and the development of UBSs have i n t e n s i f i e d i n t e r e s t i n the performance analysis of token-ring systems. As a f i r s t step, the average message delays in a general asymmetric token-ring under gated exhaustive service d i s c i p l i n e have been investigated i n t h i s t h e s i s . Although the gated exhaustive service d i s c i p l i n e i s a s p e c i a l case, i t provides insights and l o w - t r a f f i c approximations for most non-exhaustive service schemes. The approach used i n t h i s thesis i s to formulate and solve the imbedded Markov chain of the j o i n t terminal service times. Recursive l i n e a r equations are derived for the f i r s t and second joi n t moments of the imbedded chain. The existence and uniqueness of solutions to these equations are also established. A number of re s u l t s concerning the solutions are also derived. Among these, the simple difference equation r e l a t i n g the second j o i n t moments of the terminal service times i s a s i g n i f i c a n t contribution of this t h e s i s . Such simple r e s u l t s have never been reported before. Based on equation (4.25), a very good approximation given by (5.21) and (5.23) i s derived. This approximation i s exact for the symmetric case and i t works very well over a wide range of system parameters for the asymmetric case. Even under very unusual circumstances, the r e l a t i v e errors i n the approximation are s t i l l acceptable (~10%). Some delay-vs-throughput r e s u l t s based on the approximation are also discussed. 83 6.2 Suggestions for Further Work. The performance analysis of a general token-ring i s a very d i f f i c u l t problem. In t h i s t h e s i s , a s p e c i a l case has been investigated but the ultimate goal i s to solve the general problem. Thus, future work i n t h i s area should concentrate on the generalizations of the work i n t h i s t h e s i s . Emphasis has been placed on the average message delay as a performance measure. This can be generalized to include the delay variance. The delay variance i s of considerable i n t e r e s t i n many applications such as packetized voice and i n t e r a c t i v e terminal conversations. In our model, the delay variances depend on the t h i r d j o i n t moments of the terminal service times. The analysis w i l l involve a t h i r d d i f f e r e n t i a t i o n of the basic functional equation (3.9) and the solutions of (3.12) and (3.13) to set up the necessary equations for the t h i r d j o i n t moments. The problem i s to examine the s o l u t i o n of those moments. Generalizations to even higher moments are possible but they tend to be d i f f i c u l t and less useful for p r a c t i c a l purposes. Although the a r r i v a l model used i n t h i s thesis appears to be very general, i t i s s t i l l inadequate for many p r a c t i c a l s i t u a t i o n s . For example, our a r r i v a l model does not accommodate deterministic a r r i v a l s i n voice applications and dependent a r r i v a l s i n functional d i s t r i b u t e d computing. Thus, generalizations on the a r r i v a l model i s d e s i r a b l e . Perhaps the most i n t e r e s t i n g generalizations are associated with the service d i s c i p l i n e . F i r s t of a l l , we have assumed the c y c l i c service schedule i n t h i s t h e s i s . In other words, each queue has a c y c l i c p r i o r i t y which cannot be interrupted by other queues. In a general p o l l i n g system, 84 many possible p r i o r i t y assignments are possible. Even in- a token-ring, the basic protocol can be modified to accommodate various p r i o r i t y schedulings. The assignment of p r i o r i t i e s , s t a t i c or dynamic, i s a design parameter which deserves further attention. Secondly, generalization of the gated exhaustive service d i s c i p l i n e to the more general non-exhaustive schemes would be very u s e f u l . This i s because non-exhaustive service schemes can be implemented very e a s i l y on a token-ring. Unfortunately, the rigorous analysis of non-exhaustive service schemes appears to be very d i f f i c u l t . Very often, one should contend with approximate approaches. One approximate approach i s to note that most non-exhaustive schemes can be approximated by the gated exhaustive service d i s c i p l i n e at low t r a f f i c l e v e l s ; for heavy t r a f f i c , one can use various h e a v y - t r a f f i c approximations, see for example [15]. Thus, the d i f f i c u l t case occurs when t r a f f i c i s between the two extremes. One further generalization can be made on the service d i s c i p l i n e . We (k) notice that i n a l l ' s t a t i c ' service d i s c i p l i n e s , can be derived (k) d i r e c t l y from (e.g. the r e l a t i o n given by eqn. (2.1)). One can generalize t h i s dependence. For example, In the D-net protocol, each station can detect the length of a t r a i n f a i r l y e a s i l y and estimate the current (k) (k) network loading, and then the s t a t i o n can determine not only from X^ but also from previous network loading estimates. Such elaborate service d i s c i p l i n e s may not be j u s t i f i e d for many LAN applications but we cannot be sure u n t i l we have done the a n a l y s i s . 85 There are some r e l a t i v e l y l e s s urgent matters, for example, f i n i t e b u ffering, dependent switching overheads, and time-variant system parameters whose e f f e c t s could also be examined-86 References [I] A.S. Tanenbaum, Computer Networks, Pr e n t i c e - H a l l , Inc., 1981. [2] W. S t a l l i n g s , Local Networks: An Introduction, New York: MacMillan, 1984. [3] D.D. Clark, K.T. Pogran, and D.P. Reed, "An Introduction to Local Area Networks," P r o c IEEE, v o l . 66, no. 11, pp. 1497-1517 , Nov. 1978. [4] R.M. Metcalfe and D.R. Boggs, "Ethernet: Distributed Packet Switching for Local Computer Networks," Commun. Ass. Comput. Mach., v o l . 19, pp. 395-404, 1976. [5] S.D. Personick, "Review of Fundamentals of Optical Fiber Systems," I E E E J . S e l e c Areas Commun., SAC-1, no. 3, pp. 37 3-380, Apr. 1983. [6] N.L. Rhodes, "Interaction of Network Design and Fiber Optic Component Design i n Local Area Networks," IEEE J . Select. Areas Commun., SAC-1, no. 3, pp. 489-492, Apr. 1983. [7] M.R. Fin l e y , J r . , "Optical Fibers i n Local Area Networks," IEEE Communications Magazine, v o l . 22, no. 8, pp. 22-35, Aug. 1984. [8] E.G. Rawson and R.M. Metcalfe, "Fibernet: Multimode Optical Fibers for Local Computer Networks," IEEE Trans. Commun., COM. 26, no. 7, pp. 983-990, July 1978. [9] R.V. Schmidt, E.G. Rawson, R.E. Norton, J r . , S.B. Jackson, and M.D. Bailey, "Fibernet II: A Fiber Optic Ethernet," IEEE J . Select. Areas Commun., SAC-1, no. 5, pp. 702-710, Nov. 1983. [10] E.S. Lee and P.I.P. Boulton, "The P r i n c i p l e s and Performance of Hubnet: A 50Mbit/s Glass Fiber Local Area Network," IEEE J . Select. Areas Commun. SAC-1, no. 5, pp. 711-720, Nov. 1983. [II] F.A. Tobagi, F. Borgonovo, and L. F r a t t a , "Expressnet: A High-Performance Integrated-Services Local Area Network," IEEE J . Select. Areas Commun., SAC-1, no. 5, pp. 898-912, Nov. 1983. [12] C.-W. Tseng and B.-U. Chen, "D-Net, A New Scheme for High Data Rate Optical Local Area Networks," IEEE J . Select. Areas Commun., SAC-1, no. 53, pp. 493-499, Apr. 1983. [13] J.0. Limb and C. Flores, "Description of Fasnet: A Uni d i r e c t i o n a l Local Area Communications Network," B e l l Syst. Tech. J. v o l . 61, no. 7, Part I, pp. 1413-1440, Sep. 1982. [14] L. Kleinrock, Queueing Systems, Vol. 1: Theory, New York: Wiley, 197 5. L. Kleinrock, Queueing Systems, Vol. 2: Computer Applications, New York: Wiley, 197 6. H. Kobayashi and A.G. Konheim, "Queueing Models for Computer Communications System Analysis," IEEE Trans. Commun., COM-25, no. 1, pp. 2-28, Jan. 1977. W. Bux, "Local-Area Subnetworks: A Performance Comparison," IEEE Trans. Commun., COM-29, no. 10, pp. 1465-1473, Oct. 1981. W. S t a l l i n g s , "Local Network Performance," IEEE Communications Magazine, v o l . 22, no. 2, pp. 27-36, Feb. 1984. L. Takacs, "Two Queues Attended by a Single Server," Oper. Res., v o l . 16, no. 3, pp. 639-650, 1968. B. Avi-Itzhak, W.L. Maxwell, and L.W. M i l l e r , "Queueing with A l t e r n a t i n g P r i o r i t i e s , " Oper. Res., v o l . 13, no. 2, pp. 306-318, 1965. M. Eisenberg, "Two Queues with Changeover Times," Oper. Res., v o l . 19, pp. 386-401, 197 1. R.B. Cooper and G. Murray, "Queues Served i n Cyclic Order," B e l l Syst. Tech. J . , v o l . 48, no. 3, pp v675-689, Mar. 1969. R.B. Cooper, "Queues Served i n Cy c l i c Order: Waiting Times," B e l l Syst. Tech. J . , v o l . 49, no. 3, pp. 399-413, Mar. 1970. M. Eisenberg, "Queues with Periodic Service and Changeover Time," Oper Res., v o l . 20, pp. 440-451, 1972. A.G. Konheim and B. Meister, "Waiting Lines and Times i n a System with P o l l i n g , " J . Ass. Comput. Mach., v o l . 21, pp. 470-490, 1974. G.B. Swartz, " P o l l i n g i n a Loop System," J . Ass. Comput. Mach., v o l . 27, pp. 42-59, 1980. I. Rubin and L.F.M. DeMoraes, "Message Delay Analysis for P o l l i n g and Token Multiple-Access Schemes for Local Communication Networks," IEEE J . Selec. Areas Commun., SAC-1, no. 5, pp. 935-946, Nov. 1983. Y. Aminetzah, "An Exact Approach to the P o l l i n g System," Ph.D. d i s s e r t a t i o n , McGill Univ., Montreal, P.Q., Canada, Mar. 1975. M.J. Ferguson and Y.J. Aminetzah, "Exact Results for Nonsymmetric Toke Ring Systems," IEEE Trans. Commun., COM-33, no. 3, pp. 223-231, Mar. 1985. 88 [30] R.T. Carsten, E.E. Newhall, and M.J.M. Posner, "A Si m p l i f i e d Analysis of Scan Times i n an Asymmetric Newhall Loop with Exhaustive Service," IEEE Trans. Commun., COM-25, no. 9, pp. 951-957, Sep. 1977. [31] W. Bux and H.L. Truong, "Token-ring Performance: Mean Delay Approximation," i n Proc. 10th Int. T e l e t r a f f i c Cong., June 1983, pp. 3.3.3.1-3.3.3-7. [32] M. Leibowitz, "An Approximate Method for Treating a Class of Multiqueue Problems," IBM J. Res. Develop., v o l . 5, pp. 204-209, 1961. [33] S. H a l f i n , "An Approximate Method for Calculating Delays for a Family of C y c l i c Type Queues," B e l l Syst. Tech. J . , v o l . 54, no. 10, pp. 17 33-17 54, Dec. 197 5. [34] P.J. Kuehn, "Multiqueue Systems with Nonexhaustive Cyclic Service," B e l l Syst. Tech. J . , v o l . 58, no. 3, pp. 671-698, Mar. 1979. [35] S.S. Nair, "Alternating P r i o r i t y Queues with Non-Zero Switch Rule," Comp. and Opns. Res., v o l . 3, pp. 337-346, 197 6. [36] C. Mack, T. Murphy, and N.L. Webb, "The E f f i c i e n c y of N Machines U n i d i r e c t i o n a l l y Patrolled by One Operative when Walking Time and Repair Times are Constants," J . Royal Stat. S o c , ser. B, no. 19, pp. 166-172, 1957 . [37] A.R. Kaye, "Analysis, of a d i s t r i b u t e d control loop for data transmission," i n P r o c Symp. Comput. Commun. Networks T e l e t r a f f i c , Polytech. Inst., Brooklyn, NY, Apr. 197 2. [38] F.A. Tobagi and M. Fine, "Performance of Uni d i r e c t i o n a l Broadcast Local Area Networks: Expressnet and Fasnet," IEEE J . Select. Areas Commun., SAC-1, no. 5, pp. 913-925, Nov. 1983. 89 APPENDIX: Eigenvalues of the Jacobian Matrix A. A number of re s u l t s regarding the eigenvalues of the Jacobian Matrix A are proved i n t h i s Appendix. Lemma A . l : The c h a r a c t e r s t i c equation |A—rI[ = 0 of the matrix A i s given by Q(r) = { n [(l+p.)r - p.] - r N + 1 } / (1-r) = 0 1=1 (A.l) Proof of Lemma A . l : From the structure of A given by Lemma 4.3, we claim that A can be written as follows: (A.2) A " TN TN-1' .T^ DR where T i • h-l 0 0 p i p i ' " p i 1 0 0 0 h 1^ = k x k i d e n t i t y matrix, D = J2 . R = 1 1 . . . . 1 1 o • • . i To see t h i s , we successively compute T^D, T^TjD, .... T N ^ - ] / - - 1 ! 0 A N D 8 e t T N T N - r * ' T l D = [pA+^\P2^2+e2^--'^^+t^] (A'3) 90 where and e^ are defined i n Lemma 4 . 3 . Then we notice that 2 N T N T N - 1 ' " T 1 D R = l P l<V * l>l J,^\+\^''-l\^\+\^ <A'4> k=l k=l N and u j [_ 1 = I \(\ + e^ .) (A.5) k=i Thus, T N V r " T i D R = I V " I I V " 2 I ' - - I V " N ] • A* The determinant |A— r11 can now be computed as follows: |A - r l | = | TDR - r l | - |T| |D - r T " 1 ^ 1 | |R| (A.6) where T = T T _.. .T.. N N-l 1 We notice that |T| = |R| = 1 so |A - r l | = |D - r T - 1 R - 1 | = |D - r T j " 1 ^ " 1 . . . ^ " ^ " 1 ! (A.7) The inverses of T^' s and R can be expressed by 1 - 1 1 - 1 - 1 0 Using these to calculate T ^ R - 1 , T ^ j T ^ 1 * " 1 » * * *' ^ ^ i ^ '' ^ N1**"1 x k - l 0 0 -Pk-V-'-Pk I 0 0 0 IN-k successively, we have 91 .'. D - rT~ 1R~ 1 p i r + p r ( 1 + p i ) r P 2r p 3 r -1 -1 -p 2 l+p 2 -1 0 3 "P-1+P3 . N * . -1 1+p. N P 2 " ( l + P 2 ) r P 3-(1+P 3)r P N r (A.8) —I (A.9) The determinant of the above matrix can be s p l i t into a sum of determinants of two matrices and U 2 where U l = p l r p 2 r P 2 ~ ( 1 + P 2 ) r P 3-(1+P 3)r P N r p N " ( 1 + p N ) r and U2 " p 1 - ( l + p 1 ) r p 2 - ( l + p 2 ) r P N - ( 1 + p N ) r C l e a r l y , 92 |u 2 | = n J P l - d + P l ) r ] (A.10) F a c t o r i z i n g P j from each row of 1^ and then from the f i r s t column, we have N (A.11) | u j = ( n P ) |u | 1 i - i 1 -where U 3 = 1-r 1-r r 77 l - ( l + i )r r l - ( l+-7 - ) r r PN-1 1-r 1-(1+ - i - ) r pN - I Replacement of the f i r s t column by subtracting from It the sum of a l l other columns y i e l d U4 " r 1-(1+ ~)r p3 r p N - l 1 1-(1+ - ) r J- pN JN — I (A.12) where |U,| = |U | 9 3 C l e a r l y , N . N |U | = n [1 - (1 + — ) r ] + (-if n (-^-) (A.13) i-1 M i 1=1 P i Using (A.10)-(A.13) and af t e r some algebra, we have | A - r l | = l u j + |U2| = T ^ <-D N 1 " [ d+P^r-p.] - r ^ 1 } (A.13) 1=1 1 1 N Since the factor (-1) i s unimportant i n the c h a r a c t e r i s t i c equation, we a r r i v e at (A.l) Notice that the c h a r a c t e r i s t i c polynomial Q(r) i s indeed of degree N N N+l because IT [ (1+p. )r-p. ]-r i s d i v i s i b l e by (1 - r ) . Also, Q(r) does not 1=1 i i depend on the s p e c i f i c order of the queues, that i s , s h u f f l e of the queue pos i t i o n s w i l l not aff e c t Q(r). Lemma A.2: N Let p = 1 p, be the system u t i l i z a t i o n and p < 1. Then there e x i s t s < 1 = 1 p o s i t i v e r e a l root of the c h a r a c t e r i s t i c equation Q(r) = 0 and i t i s bounded by p. Proof of Lemma A.2: N N+l Let f ( r ) = II [(1+P.)r - p ] and g(r) = r 1=1 C l e a r l y , f ( l ) = 1 = g ( l ) 94 N • and f (1) = I p + N < N+l = g'(1). 1=1 Therefore, there e x i s t e > 0, which can be a r b i t r a r i l y small, such that f ( l - e ) > g ( l - e ) . Pi Next, we notice that f ( r ) = 0 has exactly N r e a l roots at r = ^ , a l l Pi l y i n g between zero and one. Let t be the maximum of - r - — , then J 6 max 1+pj f ( t ) = 0 < g(t ). max max Since t < 1, we can choose e such that t < (l-e)» From the max max i n e q u a l i t i e s shown above, there must exist a r e a l root of Q(r) = f ( r ) - g(r) = 0 between t and (1-e). In f a c t , there i s only one r e a l root of Q(r) = 0 between t and (1-e) because f ( r ) and g(r) are both max monotonic i n that region. We s h a l l c a l l t h i s root r ° max To show r < p, we look at (Jin f ( r ) - An g(r)) on the i n t e r v a l max [ t ,1). 1 max N Jui f ( r ) - Jui g(r) = I An[ (1+p )r-p ] - (N+l) An r 1=1 N = I An[l - (1+p ) ( l - r ) ] - ( N + l ) A n ( l - ( l - r ) ) . 1=1 Let 6 = 1-r and expand the logarithmic function i n Taylor's series at r=l to obtain An f ( r ) - An g(r) N - (1+p ) 6 - 6k = -I I 1 + (N+D I — i = l k - l k k-1 95 N . .k = I [(N+l) - I (1 + P l ) k ] f k-1 i-1 = I [(N+i) -1 ( i +1 P j ) ] ^ k-1 1=1 j-1 J N k . *k = I [1 - I I {)) P ? ] £ k-1 1=1 j-1 3 1 k , N . -k k=l j-1 J i=l 1 K k . N . ,k k-1 j-1 J 1=1 1 * N . ck = I [I - (1 + I P l ) k + l ] f k-1 1=1 1 - I 2 -r - X k-1 k-1 = -2An(l-6) + An(l-(l+p)6). Setting r = 1 - 6 = p, we have An f(p) - i n g(p) > -2An p + An p 2 = 0. Therefore, f ( P ) > g(p). Since p > t , we can deduce that t < r < p. max max max Lemma A.3 A l l the eigenvalues of A, r e a l or complex, have magnitudes les s than o r equal to r i f p < 1. ^ max 96 Proof of Lemma A.3: We prove Lemma A.3 using the famous Rouche's Theorem i n complex analysis which states the following: If f ( z ) and g(z) are a n a l y t i c i n a closed region on the complex plane with a simply connected boundary C and i f | f ( z ) | > |g(z)| on C, then f ( z ) , f ( z ) + g ( z ) , f ( z ) - g(z) a l l have the same number of zeros inside C Let us consider a semicircle on the right h a l f complex plane with centre at the o r i g i n and radius R = r + E < 1 with E > 0 shown i n ° max Fi g . A . l . F i g . A . l Right-half plane s e m i c i r c l e . 97 N N+1 We l e t f ( z ) = II [ (1+p, )z - p ] and g(z) = z . On C. , 1=1 1 1 N | f ( z ) | = n |(i+p.)z - P,| i=i 1 N = n |(l+p )R(cos9 + jsinB) - p | ( j 2 = " l ) 1=1 1 N 1/2 = II [ (1+p )R 2 + p 2 - 2(l+p ) p Rcose] 1=1 N 1/2 = n [ ( ( 1+p )R - p ) 2 + 2(l+p ) p R(l-cos9)] 1=1 1 N > n |(i+ P.)R - p I 1=1 = f(R) > g(R) - feU) I-On C^, z = jy and | f ( z ) | = n [ ( i + P l ) 2 y 2 + P l 2 ] 1 / 2 > y N > y N + 1 = |g(z)| 1=1 1 1 By Rouche's Theorem, f ( z ) and f ( z ) - g(z) have the same number of zeros inside C. C l e a r l y , f ( z ) has exactly N r e a l zeros inside C so f ( z ) - g(z) should also have N zeros in s i d e C. We already know that the (N+l)th zero of f( z ) - g(z) i s at z = 1. Thus Q(z) = ( f ( z ) - g ( z ) ) / ( l - z ) = 0 has a l l N zeros i n s i d e C. Therefore, a l l eigenvalues of A have magnitudes l e s s than R = r + £• Since e can be a r b i t r a r i l y small, we can deduce that a l l eigenvalues of A have magnitudes l e s s than or equal to r . Moreover, r < p < 1 shows c ^ max max that A has eigenvalues of magnitudes less than unity.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Mean delay analysis for unidirectional broadcast structures
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Mean delay analysis for unidirectional broadcast structures Pang, Joseph Wai Ming 1985
pdf
Page Metadata
Item Metadata
Title | Mean delay analysis for unidirectional broadcast structures |
Creator |
Pang, Joseph Wai Ming |
Publisher | University of British Columbia |
Date Issued | 1985 |
Description | Unidirectional broadcast structures constitute a class of high performance local network architectures. They are very flexible and well suited for fiber optic implementation. The access methods used in these networks are often based on certain implicit token-passing mechanisms to provide superior delay-vs-throughput characteristics. The performance of these unidirectional broadcast protocols is evaluated in this thesis via a study on the classical token-ring system. Emphasis is placed on the analysis of mean delay-vs-throughput performance for the gated exhaustive service discipline under asymmetric traffic. The analysis involves examination of the statistical behaviour of interacting queues. A number of exact results are derived and based on these results, a very good approximation for the average delays is developed. The approximation agrees closely with exact numerical solutions over a wide range of system parameters. The implications of the approximation are also discussed. |
Subject |
Local area networks (Computer networks) |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2010-05-28 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0096210 |
URI | http://hdl.handle.net/2429/25104 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1985_A7 P35.pdf [ 3.88MB ]
- Metadata
- JSON: 831-1.0096210.json
- JSON-LD: 831-1.0096210-ld.json
- RDF/XML (Pretty): 831-1.0096210-rdf.xml
- RDF/JSON: 831-1.0096210-rdf.json
- Turtle: 831-1.0096210-turtle.txt
- N-Triples: 831-1.0096210-rdf-ntriples.txt
- Original Record: 831-1.0096210-source.json
- Full Text
- 831-1.0096210-fulltext.txt
- Citation
- 831-1.0096210.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.831.1-0096210/manifest