Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

A queueing analysis of a multichannel, integrated voice and data communications system 1982

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

Item Metadata

Download

Media
UBC_1982_A7 H34.pdf
UBC_1982_A7 H34.pdf [ 4.19MB ]
Metadata
JSON: 1.0065616.json
JSON-LD: 1.0065616+ld.json
RDF/XML (Pretty): 1.0065616.xml
RDF/JSON: 1.0065616+rdf.json
Turtle: 1.0065616+rdf-turtle.txt
N-Triples: 1.0065616+rdf-ntriples.txt
Citation
1.0065616.ris

Full Text

A QUEUEING ANALYSIS OF A MULTICHANNEL, INTEGRATED COMMUNICATIONS SYSTEM VOICE AND DATA by DENNIS RAYMOND HALLER B.E., U n i v e r s i t y of Saskatchewan, 1980 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 E n g i n e e r i n g We accept t h i s t h e s i s as conforming to the r e q u i r e d s t a n d a r d THE UNIVERSITY OF BRITISH COLUMBIA June 1982 © Dennis Raymond H a l l e r , 1982 In presenting this thesis in p a r t i a l fulfilment 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 freely 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. It i s understood that copying or publication of this 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 e c t r i c a l Engineering The University of B r i t i s h Columbia 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date: 28 June 1982 i i A b s t r a c t A m u l t i c h a n n e l r a d i o communications system i s modeled as a m u l t i s e r v e r queue, with two d i s t i n c t customer c l a s s e s r e p r e s e n t i n g v o i c e and data messages. Data, the c l a s s with the s h o r t e r average l e n g t h , i s given non-preemptive p r i o r i t y over v o i c e . The queueing model i s analyzed as a continuous-time Markov c h a i n with an i n f i n i t e s t a t e space. The i n f i n i t e set of steady s t a t e balance equations i s t r u n c a t e d , then s o l v e d n u m e r i c a l l y u s i n g the l i n e a r programming (LP) technique of K o t i a h . Upper and lower bounds are thereby o b t a i n e d f o r the mean w a i t i n g times of each customer c l a s s , and the p r o b a b i l i t y d i s t r i b u t i o n f o r the number of messages i n the system. E x p l o i t a t i o n of the Markov ch a i n ' s p r o p e r t y of i r r e d u c i b i l i t y improves the o r i g i n a l a l g o r i t h m by c o n s i d e r a b l y reducing the computational c o s t . S i m u l a t i o n i s used to h e l p analyze the system and to v a l i d a t e the numerical r e s u l t s . The p a r t i c u l a r four-channel case of the queueing model i s t r e a t e d i n d e t a i l ; both s i m u l a t i o n and numerical r e s u l t s are presented. The LP method produces e x c e l l e n t r e s u l t s when the data t r a f f i c i n t e n s i t y i s l e s s than about 0.1 . T h i s corresponds t y p i c a l l y to the p r o p o r t i o n of data messages being l e s s than 90%. For other t r a f f i c mixtures, the upper bounds, e s p e c i a l l y f o r w a i t i n g times, are o f t e n too high to be of p r a c t i c a l use. However, the lower bounds of the mean w a i t i n g times are of g r e a t e r use; the s i m u l a t i o n r e s u l t s show them to be reasonably good approximations to the t r u e steady s t a t e v a l u e s . . . . X 111 Table of Contents A b s t r a c t i i L i s t of F i g u r e s v Acknowledgement v i I. INTRODUCTION 1 I I . SYSTEM ANALYSIS 3 A . THE APPROACH 3 B. MARKOV MODELING 3 C. NUMERICAL TECHNIQUES OF MARKOV MODELING 6 1. The Markov Chain Equations 6 2. F i n i t e S tate Space 7 3. I n f i n i t e S t a t e Space 8 I I I . MODEL SELECTION 11 A. BASIC ASSUMPTIONS 11 B. SERVICE DISCIPLINES . . 12 C. ALTERNATING PRIORITY MODELS 14 1. Previous I n v e s t i g a t i o n s 14 2. Markov Chain Model — Non-exhaustive S e r v i c e ..15 3. Markov Chain Model - Exhaustive S e r v i c e 16 D. NON-PREEMPTIVE PRIORITY MODELS 17 1. Previous I n v e s t i g a t i o n s 17 2. Markov Chain Model 18 IV. NUMERICAL SOLUTION TECHNIQUE 20 A. THE STATE SPACE 20 B. THE BALANCE EQUATIONS 21 C. THE LINEAR PROGRAMMING SOLUTION TECHNIQUE 24 D. NORMALIZATION CONSTRAINTS 26 E. IRREDUCIBILITY OF THE MARKOV CHAIN 28 1. The S i g n i f i c a n c e of I r r e d u c i b i 1 i t y 29 2. Improvements to the LP A l g o r i t h m 30 F. IMPLEMENTATION OF THE MODIFIED LP ALGORITHM 31 V. RESULTS 35 A. SYSTEM PARAMETERS 35 B. THE STEADY STATE PROBABILITY DISTRIBUTION p(n) ..38 C. MEAN WAITING TIMES 43 1 . D e f i n i t i o n 43 2. The L i m i t i n g Cases: a,-M 44 3. Waiting Time R e s u l t s 46 D. WAITING TIME SIMULATIONS 51 E. COMMENTS ON THE WAITING TIME RESULTS 53 1. E m p i r i c a l Observations 53 2. Waiting Times i n a Non-preemptive P r i o r i t y System 54 F. CONVERGENCE OF UPPER AND LOWER BOUNDS 56 G. COMPUTATIONAL COSTS 63 1. LP S o l u t i o n Cost 63 2. A Comparison with S i m u l a t i o n Costs 65 VI. CONCLUDING REMARKS 67 A. LIMITATIONS OF THE MODEL 67 B. SUMMARY AND CONCLUSIONS 69 C. SUGGESTIONS FOR FURTHER STUDY 72 APPENDIX A - A COMPARISON OF NON-PREEMPTIVE PRIORITY AND ALTERNATING PRIORITY SERVICE DISCIPLINES, 74 APPENDIX B - THE STATE SPACE TRANSITION DIAGRAM 77 APPENDIX C - SETTING UP THE BALANCE EQUATION COEFFICIENT MATRIX "A": AN EXAMPLE 79 APPENDIX D - A DERIVATION FOR THE NORMALIZATION CONDITION GIVEN IN [KOTI 77] 84 BIBLIOGRAPHY 86 Gl o s s a r y of N o t a t i o n 89 V L i s t of F i g u r e s 1. R e l a t i o n s h i p Between Parameters &, and o, 37 2. The D i s t r i b u t i o n p(n) f o r p = 0.7, o,= 0.80, (*,= 0.14) 39 3. The D i s t r i b u t i o n p(n) f o r p = 0.5, o , « 0.80, (*,= 0.14) 41 4. The D i s t r i b u t i o n p(n) f o r p = 0.5, oy= 0.95, 0.44) 42 5. Waiting Times as a Fu n c t i o n of * i : P - 0.7, n = 30 c. 47 6. Waiting Times as a Fu n c t i o n of e, : p = 0.5, n = 25 c. 48 7. Waiting Times as a F u n c t i o n of B, : p - 0.3, n = 20 c. ....49 8. Convergence of Bounds f o r P r o b a b i l i t i e s p ( 0 ) , p(4) 58 9. Convergence of Waiting Time R e s u l t s : p - 0.7, o,= 0.80, (*,,= 0.14) 59 10. Convergence of Waiting Time R e s u l t s : p = 0.5, o,= 0.80, 0.14) 60 11. Convergence of Waiting Time R e s u l t s : p = 0.5, o,= 0.95, (p,= 0.44) 61 12. Schematic of a 2-Class M u l t i s e r v e r Queueing System ..74 13. State Space f o r n Z s 78 14. State Space f o r n < s 78 15. M a t r i x "A" For n c=6, s=4 Servers 80 v i Acknowledgement I would l i k e to thank my s u p e r v i s o r , Dr. C.S.K. Leung, f o r h i s guidance and constant a v a i l a b i l i t y d u r i n g the course of the r e s e a r c h and w r i t i n g of t h i s t h e s i s . F i n a n c i a l a s s i s t a n c e i n the form of an NSERC Postgraduate S c h o l a r s h i p , and a U n i v e r s i t y of B r i t i s h Columbia t e a c h i n g a s s i s t a n t s h i p i s a l s o g r a t e f u l l y acknowledged. T h i s work was p a r t i a l l y supported by NSERC r e s e a r c h grant A-1052. 1 I. INTRODUCTION In t h i s study we analyze a c e n t r a l l y c o - o r d i n a t e d , m u l t i c h a n n e l r a d i o communications system. S e r v i c e i s p r o v i d e d to both data messages and v o i c e messages, and each type can be queued when a l l r a d i o channels are busy. One example of such a system may be a modern mobile r a d i o network i n which each mobile can communicate with a c e n t r a l o f f i c e e i t h e r by v o i c e or through an i n t e r a c t i v e computer t e r m i n a l . Requests f o r t r a n s m i s s i o n of messages are sent v i a an a u x i l i a r y channel to a c e n t r a l c o n t r o l l e r . I f a l l the message-carrying r a d i o channels are busy, the c o n t r o l l e r t e m p o r a r i l y denies incoming requests and allows a queue to form. In t h i s way, the c o n t r o l l e r imposes an o r d e r l y s e r v i c e d i s c i p l i n e on the use of a f i n i t e resource — the s a v a i l a b l e channels. Our o b j e c t i v e i s to model t h i s communications system to o b t a i n some measure of the average queueing times f o r each message type and the steady s t a t e p r o b a b i l i t y d i s t r i b u t i o n f o r the number of messages in the system. In a model based on queueing theory the r a d i o channels become s e r v e r s , while the data and v o i c e messages become customers of types 1 and 2 r e s p e c t i v e l y . The queueing a n a l y s i s w i l l i n f a c t r e q u i r e the numerical s o l u t i o n of the continuous-time Markov ch a i n s t a t e e q u a t i o n s . We w i l l s p e c i f i c a l l y o b t a i n numerical r e s u l t s f o r the case of s = 4 channels. An a u x i l i a r y s i g n a l i n g channel i s assumed to e x i s t , but i t w i l l not be i n c l u d e d i n our model. The s e r v i c e d i s c i p l i n e of the c e n t r a l c o n t r o l l e r must not only e f f i c i e n t l y a s s i g n channel use, but a l s o must maintain 2 message queueing times at a c c e p t a b l e l e v e l s . Among the many p o s s i b l e s e r v i c e d i s c i p l i n e s , the most r e l e v a n t to the given p h y s i c a l system a r e : f i r s t - c o m e f i r s t - s e r v e d (no p r i o r i t y ) , c u t o f f p r i o r i t y , non-preemptive p r i o r i t y , and a l t e r n a t i n g p r i o r i t y . Only the l a s t two of these w i l l be given s e r i o u s f u r t h e r c o n s i d e r a t i o n . The f o l l o w i n g chapter d e s c r i b e s the a n a l y t i c a l approach of t h i s study, and o u t l i n e s the numerical techniques of Markov modeling. Chapter III reviews p r e v i o u s work done with the a l t e r n a t i n g p r i o r i t y and non-preemptive p r i o r i t y models, and asse s s e s both with r e s p e c t to t h e i r a n a l y t i c a l and numerical t r a c t a b i l i t y . Chapter IV d e s c r i b e s i n d e t a i l the numerical methods use to s o l v e the chosen model, and numerical r e s u l t s f o r a s e l e c t e d example are presented and d i s c u s s e d i n Chapter V. F i n a l l y , i n Chapter VI the main r e s u l t s from t h i s study are summarized and p o s s i b l e f u t u r e work i s o u t l i n e d . 3 I I . SYSTEM ANALYSIS A. THE APPROACH A n a l y t i c a l s o l u t i o n s are g e n e r a l l y u n a v a i l a b l e f o r most m u l t i s e r v e r queueing systems with p r i o r i t y s e r v i c e d i s c i p l i n e s . Two of the more popular a l t e r n a t i v e s f o r systems a n a l y s i s are s i m u l a t i o n s and numerical s o l u t i o n s , p a r t i c u l a r l y the s o l u t i o n of Markov ch a i n models. The t r a d e o f f between numerical s o l u t i o n and s i m u l a t i o n i s i n i n i t i a l a n a l y t i c a l e f f o r t v ersus a c t u a l program execution time. A numerical s o l u t i o n may r e q u i r e a s i g n i f i c a n t modeling e f f o r t , while s i m u l a t i o n u s u a l l y r e q u i r e s only the s t r a i g h t f o r w a r d t r a n s l a t i o n of system behaviour i n t o a s p e c i a l i z e d s i m u l a t i o n language. However, the l e n g t h of time a s i m u l a t i o n program must run to g i v e a c c e p t a b l e c o n f i d e n c e i n t e r v a l s f o r the measured q u a n t i t i e s i s u s u a l l y g r e a t e r than the execution time of a numerical s o l u t i o n program. As with any computer program, both numerical and s i m u l a t i o n programs r e q u i r e independent checks on t h e i r v a l i d i t y , i t being a c c e p t a b l e to use one as a check on the other. In t h i s i n v e s t i g a t i o n we have r e l i e d p r i m a r i l y on the numerical approach but have a l s o used s i m u l a t i o n to p r o v i d e a d d i t i o n a l v e r i f i c a t i o n of the r e s u l t s . B. MARKOV MODELING Many p r o b a b i l i s t i c systems, i n which incoming customers demand use of c e r t a i n system r e s o u r c e s , can be analyzed e f f e c t i v e l y u s ing a Markov chain model. In the f o l l o w i n g we present a b r i e f summary of Markov ch a i n modeling t e c h n i q u e s , and 4 f o r s i m p l i c i t y , we c o n s i d e r only s t o c h a s t i c systems with time- independent parameters ( s t a t i o n a r y p r o c e s s e s ) . More d e t a i l e d treatments can be found in [BHAR 60], [KLEI 75], and [ROSS 72]. The e s s e n t i a l f e a t u r e of a Markov c h a i n whether i n d i s c r e t e - t i m e or continuous-time i s the Markov P r o p e r t y . That i s , a Markov c h a i n has the p r o p e r t y that i t s present s t a t e completely summarizes how i t s e n t i r e h i s t o r y a f f e c t s i t s f u t u r e . A Markov c h a i n i s formed of a d i s c r e t e set of s t a t e s , each s t a t e being a unique c o n f i g u r a t i o n of the s t a t e v a r i a b l e s chosen to c h a r a c t e r i z e the system. There w i l l be a f i n i t e number of s t a t e v a r i a b l e s , say d , and each v a r i a b l e may, depending on the system, take on e i t h e r a f i n i t e or i n f i n i t e number of d i s c r e t e a l l o w a b l e v a l u e s . The d s t a t e v a r i a b l e s form a d - d i mensional s t a t e space and, i f at l e a s t one v a r i a b l e has an i n f i n i t e range, then there w i l l be an i n f i n i t e number of s t a t e s i n the s t a t e space. For example, i n a queueing system with u n r e s t r i c t e d queue lengths the Markov c h a i n model w i l l be d e f i n e d on an i n f i n i t e s t a t e space. The c h a r a c t e r i s t i c s of the system u n d e r l y i n g the Markov chain model w i l l a l s o determine whether a d i s c r e t e - t i m e or continuous-time r e p r e s e n t a t i o n can be used. In a c ontinuous- time Markov c h a i n , the time between s u c c e s s i v e s t a t e t r a n s i t i o n s i s an e x p o n e n t i a l l y d i s t r i b u t e d continuous random v a r i a b l e with a known (perhaps s t a t e dependent) parameter. An example of a system which can be so modeled i s the M|M|s queueing system. The i n s t a n t s at which s t a t e t r a n s i t i o n s may occur i n a d i s c r e t e - time Markov c h a i n are l a b e l l e d by the i n t e g e r s {0,1,2,... }, and 5 the time between s u c c e s s i v e s t a t e t r a n s i t i o n s i s a g e o m e t r i c a l l y d i s t r i b u t e d d i s c r e t e random v a r i a b l e . D i s c r e t e - t i m e Markov cha i n models may be a p p l i e d to systems which i n h e r e n t l y operate i n d i s c r e t e - t i m e , f o r i n s t a n c e , a d i g i t a l communications system. If the d i s t r i b u t i o n of time between s t a t e t r a n s i t i o n s i s a r b i t r a r y ( e i t h e r i n continuous or d i s c r e t e time), then t h i s process i s c a l l e d semi-Markov. The process can s t i l l be modeled as a Markov ch a i n i f a c e r t a i n set of time i n s t a n t s can be found which together d e f i n e an imbedded d i s c r e t e - t i m e Markov c h a i n . T h i s imbedding technique may be used to model many continuous-time s t o c h a s t i c processes as d i s c r e t e - t i m e Markov c h a i n s . The M|M|s queueing system f o r example can e a s i l y be represented as a continuous-time Markov c h a i n , but a d i s c r e t e - time model i s a l s o p o s s i b l e by imbedding a Markov ch a i n on the set of i n s t a n t s formed of a l l s t a t e t r a n s i t i o n times. The M|G|1 continuous-time process i s not Markov, nor even semi-Markov (with r e s p e c t to number in the system n ( t ) , t ^ O ) , but i t may be s u c c e s s f u l l y modeled as a d i s c r e t e - t i m e Markov chain imbedded on the set of i n s t a n t s c o n s i s t i n g of a l l s e r v i c e completion times. S o l v i n g these imbedded d i s c r e t e - t i m e Markov chains however, gi v e s not the general-time p r o b a b i l i t y d i s t r i b u t i o n of number in the system, but i n s t e a d a d i s t r i b u t i o n f o r p r o p o r t i o n of time spent i n each s t a t e of the imbedded c h a i n . The computed p r o b a b i l i t i e s t h e r e f o r e need to be a d j u s t e d so that they again correspond to s t a t i o n a r y p r o b a b i l i t i e s of the system being i n each s t a t e . T h i s t r a n s f o r m a t i o n makes use of the r e l a t i o n s h i p between s t a t e s of the p a r t i c u l a r imbedded c h a i n and those i n the 6 o r i g i n a l general-time system [GROS 74, p.311 ii.]. C. NUMERICAL TECHNIQUES OF MARKOV MODELING 1. The Markov Chain Equations A numerical s o l u t i o n of a Markov c h a i n model aims to c a l c u l a t e the s t a t i o n a r y p r o b a b i l i t y that the system i s i n each s t a t e of the s t a t e space. From these p r o b a b i l i t i e s i t i s then p o s s i b l e to compute queue l e n g t h d i s t r i b u t i o n s , moments of wa i t i n g time d i s t r i b u t i o n s , and other q u a n t i t i e s of i n t e r e s t . In a continuous-time Markov c h a i n , an equation i s w r i t t e n f o r each s t a t e , b a l a n c i n g the t o t a l t r a n s i t i o n r a t e (or flow) i n t o the s t a t e with the t o t a l t r a n s i t i o n r a t e out of the s t a t e . Denote by tr the row v e c t o r of steady s t a t e p r o b a b i l i t i e s , each component rr i r e p r e s e n t i n g the p r o p o r t i o n of time the system spends i n s t a t e i . The set of balance equations i s then w r i t t e n (column by column) as: £ Q = 0 (2.1) with Q the matrix of t r a n s i t i o n r a t e s , and fJ the n u l l (row) v e c t o r . Since jr i s a p r o b a b i l i t y d i s t r i b u t i o n i t i s normalized by 1± ir± = 1 . (2.2) In a d i s c r e t e - t i m e Markov cha i n a t r a n s i t i o n p r o b a b i l i t y matrix P i s d e f i n e d such that P i s the p r o b a b i l i t y the process w i l l at the next time i n s t a n t move to s t a t e j , given that i t i s c u r r e n t l y i n s t a t e i . The steady s t a t e p r o b a b i l i t y d i s t r i b u t i o n i s d e f i n e d through ir P = n (2.3) 7 and the n o r m a l i z a t i o n (2.2). Here the steady s t a t e p r o b a b i l i t i e s can be i n t e r p r e t e d as the p r o p o r t i o n of t r a n s i t i o n s t h at take the process i n t o s t a t e i . Note that (2.3) may be r e w r i t t e n i n a form s t r u c t u r a l l y s i m i l a r to (2.1) although the steady s t a t e v e c t o r ir i s not d e f i n e d i n the same way: j r ( I - P ) = 0 (2.4) If the s t a t e space i s i n f i n i t e then (2.1) or (2.4) r e p r e s e n t s an i n f i n i t e number of l i n e a r e q u a t i o n s . 2. F i n i t e State Space Assume f i r s t that the s t a t e space i s f i n i t e (N s t a t e s ) so that both (2.1) and (2.4) are (N x N) systems of l i n e a r e q u a t i o n s . A c t u a l l y only (N-1) of these equations are independent, so the n o r m a l i z a t i o n (2.2) must be used to r e p l a c e any one of the N equations i n (2.1) or (2.4). The l i n e a r systems may then be s o l v e d e x a c t l y to o b t a i n steady s t a t e p r o b a b i l i t i e s . S o l u t i o n s may be obtained e i t h e r by d i r e c t or i t e r a t i v e methods. D i r e c t s o l u t i o n s are u s u a l l y based on Gaussian e l i m i n a t i o n and are more e f f i c i e n t when the c o e f f i c i e n t m a t r i c e s are sparse, because then s p e c i a l i z e d data s t r u c t u r e s may be used to a v o i d a computations which i n v o l v e zeros or ones [DUFF 77]. There are a great v a r i e t y of i t e r a t i v e methods [STEW 78] the s i m p l e s t of which i s p o w e r - i t e r a t i o n [WALL 66], In the method of power- i t e r a t i o n , as a p p l i e d to the s o l u t i o n of (2.1), the (k+1)'th i t e r a t e f o r the s o l u t i o n v e c t o r jr i s obtained from the k'th 8 i t e r a t e as f o l l o w s : J L k + 1 = JLk (AQ + I) (2.5) where A i s a s c a l a r c o n s t a n t . The parameter A c o n t r o l s the r a t e of convergence and, although g u i d e l i n e s e x i s t f o r choosing A [STEW 78], i t s best value must u s u a l l y be determined e x p e r i m e n t a l l y . I t e r a t i v e methods are i n general more e f f i c i e n t than d i r e c t methods whenever the c o e f f i c i e n t m a t r i c e s Q or (I - P) are f u l l , or when they are sparse but have a s t r u c t u r e that would f o r c e a Gaussian e l i m i n a t i o n a l g o r i t h m to f i l l - i n many of the zero elements. 3 . I n f i n i t e S tate Space When the s t a t e space i s i n f i n i t e , the l i n e a r system of equations (2.1) or (2.4) i s a l s o i n f i n i t e and so i n most cases cannot be s o l v e d e x a c t l y . There seem to be only two techniques which have developed to s o l v e t r u n c a t e d v e r s i o n s of (2.1) or (2.4) to provide u s e f u l , though approximate, numerical r e s u l t s . The technique of K o t i a h [KOTI 77] i s best e x p l a i n e d by c o n s i d e r i n g the transpose of system (2.1): T T T , Q n = 0 . (2.6) The Markov chain balance equation c o e f f i c i e n t s now appear row- by-row i n Q . T h i s matrix i s t r u n c a t e d f i r s t to m rows and then to n columns, with n chosen so that no c o e f f i c i e n t s from the m balance equations are l o s t . In g e n e r a l n £ m because of the s t r u c t u r e of these e q u a t i o n s . With the c o n s t r a i n t 9 n > 0 (2.7) the problem i s now viewed as an (m x n) l i n e a r program and standard methods may be used to compute upper and lower bounds on q u a n t i t i e s of i n t e r e s t . T h i s technique c o u l d presumably a l s o be a p p l i e d to system (2.4). T h i s method of K o t i a h i s the one used i n the present study and w i l l be d i s c u s s e d i n more d e t a i l l a t e r (see IV - C). The second technique a p p l i e s t o t r u n c a t i o n s of the d i s c r e t e - t i m e l i n e a r system (2.4). R e c a l l that any system modeled as a continuous-time Markov ch a i n may a l s o , with a d d i t i o n a l e f f o r t , be represented as a d i s c r e t e - t i m e Markov c h a i n , and hence (2.4) w i l l a p ply. The "(m x m) northwest c o r n e r " t r u n c a t i o n method was f i r s t developed by Seneta [SENE 67], and was r e c e n t l y extended and much enhanced by Wolf [WOLF 80]. P o s s i b l e a l g o r i t h m s u s i n g Seneta's technique are d i s c u s s e d i n [ALLE 77]. The common approach of both Seneta and Wolf i s to t r u n c a t e the t r a n s i t i o n p r o b a b i l i t y matrix P to m rows and m columns, , .P , and then modify the t r u n c a t e d matrix (m) i n some s p e c i a l way. The s o l u t i o n n to the t r u n c a t e d system converges elementwise to JT : l i m IT , = ir i=1,2,... ,m (2.8) _ ^ Cm) x i In [WOLF 80] s e v e r a l p o s s i b l e m o d i f i c a t i o n s of the t r u n c a t e d matrix , N P are given, one of which i n c l u d e s the technique of Cm; Seneta. For t h i s p a r t i c u l a r v e r s i o n , a s p e c i a l kind of convergence r e s u l t can be given [SENE 67,68], i n which both upper and lower bounds can be found f o r the r a t i o s of elements n.. / i r ± ( i , j =1,2,... ,m). These computations r e q u i r e the 10 i n v e r s e of the matrix ( (m) 1 ~ (m) p ) • F o r the other m o d i f i c a t i o n s t o ( m)P l i s t e d i n [WOLF 80], even l e s s i s known about the convergence p r o p e r t i e s of the technique. For both s e t s of m o d i f i c a t i o n s i t i s not p o s s i b l e to estimate the a b s o l u t e e r r o r s f o r i n d i v i d u a l elements: Ifm)"! ~ ffi I i = 1 ,2, . . . ,m . The advantage of the method of K o t i a h over that of Seneta and Wolf i s i t s a b i l i t y to g i v e upper and lower bounds on s t a t e p r o b a b i l i t i e s no matter what the t r u n c a t i o n m. On the other hand, Wolf's method giv e s only approximate s t a t e p r o b a b i l i t i e s with unknown magnitudes of e r r o r . Consequently, b e f o r e the r e s u l t IT i s judged to be " c l o s e enough" to v_ , the (m) convergence behaviour of the problem under study must be determined by o b t a i n i n g s o l u t i o n s . sn f o r e v e r - i n c r e a s i n g m . 11 I I I . MODEL SELECTION A. BASIC ASSUMPTIONS We c o n s i d e r queueing models of the form M|M|s with some p r i o r i t y a l l o c a t i o n f o r two customer c l a s s e s . W i thin c l a s s e s , the customers are served on a f i r s t - c o m e f i r s t - s e r v e d b a s i s . The s s e r v e r s are i d e n t i c a l and independent of each o t h e r . Customer t r a f f i c a r r i v a l i s modeled as a Poisson process with r a t e X f o r customer type i (i=1,2). The a r r i v a l s of type 1 i and type 2 customers are assumed to be independent. The t o t a l a r r i v a l process i s then a l s o P o isson, with r a t e X. = X, + X.2 • The s e r v i c e times of each customer c l a s s are e x p o n e n t i a l l y d i s t r i b u t e d with mean (? ± ) ' 1 f o r customer type i . The u t i l i z a t i o n f a c t o r f o r each c l a s s i s p± = k± / ( s Kj) and the t o t a l u t i l i z a t i o n i s p = p , + p2 In the mathematical model we assume there i s no l i m i t on the number of customers allowed i n the system. P h y s i c a l systems to which t h i s a n a l y s i s a p p l i e s w i l l of course have f i n i t e queue le n g t h s , but these are assumed to be l a r g e enough so that the p r o b a b i l i t y of a customer being blocked i s n e g l i g i b l e . 12 B. SERVICE DISCIPLINES There are c h i e f l y four s e r v i c e d i s c i p l i n e s which might be c o n s i d e r e d f o r a m u l t i c h a n n e l , mixed v o i c e and data, communications system. The goal i s to s e l e c t one which w i l l minimize message w a i t i n g times, while maximizing use of a v a i l a b l e r e s o u r c e s . We assume that only the d i s t r i b u t i o n s of s e r v i c e time are known beforehand, and not the exact s e r v i c e time of each new customer. Firs t - c o m e f i r s t - s e r v e d (FCFS), [SLAT 73], [KOTI 73], i s no doubt the s i m p l e s t d i s c i p l i n e f o r a m u l t i s e r v e r system. However, i t does have an element of " u n f a i r n e s s " f o r v o i c e / d a t a systems where the average s e r v i c e times f o r the two customer types may t y p i c a l l y d i f f e r by a f a c t o r of 20. Data messages, which are i n h e r e n t l y q u i t e s h o r t , would s u f f e r a d e l a y - t o - s e r v i c e - t i m e r a t i o much g r e a t e r than f o r - v o i c e messages. Consequently the quick-response, i n t e r a c t i v e aspect of data communication would be l o s t . C u t o f f p r i o r i t y , [TAYL 80], [SING 81], makes a v a i l a b l e a g r e a t e r share of the system's resources to customers of one type, u s u a l l y those with s h o r t e s t s e r v i c e time. High p r i o r i t y customers are always admitted to s e r v i c e i f there i s a f r e e s e r v e r . However, low p r i o r i t y customers are allowed s e r v i c e only i f the number of busy s e r v e r s i s l e s s than some c u t o f f l e v e l s c . Customers denied s e r v i c e wait i n p r i o r i t y - t y p e d queues, with FCFS d i s c i p l i n e f o r each queue. C u t o f f p r i o r i t y however, i s not work-conserving [KLEI 76, p.113], meaning that i t i s p o s s i b l e f o r low p r i o r i t y customers to be denied s e r v i c e 13 even while some s e r v e r s stand i d l e . T h i s i s a waste of system r e s o u r c e s , and seems an unwarranted s a c r i f i c e u n l e s s the high p r i o r i t y customers have an "emergency" nature. A l t e r n a t i n g p r i o r i t y assumes that incoming customers are s p l i t i n t o separate queues a c c o r d i n g to t h e i r type. In the case of two queues, the c o n t r o l l e r a l t e r n a t e l y attends each queue. A maximum of k, customers are served from queue 1, then the c o n t r o l l e r switches and a maximum of k 2 customers are served from queue 2. If e i t h e r k, or k 2 i s unbounded, the s e r v i c e i s s a i d to be exhaustive f o r that p a r t i c u l a r queue. When there are more than two customer c l a s s e s , the scheme i s g e n e r a l i z e d to what i s c a l l e d c y c l i c p r i o r i t y . Because of i t s f l e x i b i l i t y , a l t e r n a t i n g p r i o r i t y remains a v i a b l e o p t i o n f o r the r a d i o system under c o n s i d e r a t i o n , and so w i l l be f u r t h e r d i s c u s s e d i n s e c t i o n III - C. Non-preemptive p r i o r i t y (NPP), more d e s c r i p t i v e l y known as h e a d - o f - t h e - l i n e p r i o r i t y , has a q u i t e simple o p e r a t i n g r u l e . Consider there to be only a s i n g l e queue, with a l l high p r i o r i t y customers grouped together at the f r o n t , and a l l low p r i o r i t y customers queued s i m i l a r l y behind. S e r v i c e i s then always from the head of the l i n e . If high p r i o r i t y i s given to the customer c l a s s with the s h o r t e s t mean s e r v i c e time, then i t i s known for s i n g l e s e r v e r NPP systems that the o v e r a l l average customer w a i t i n g time i s minimized [KLEI 76, p.126]. No such r e s u l t has yet been proven f o r m u l t i s e r v e r systems but i t seems reasonable to assume that t h i s a l l o c a t i o n of p r i o r i t y would maintain i t s advantage f o r s > 1 . L a t e r , i n III - D we i n v e s t i g a t e non- 14 preemptive p r i o r i t y i n g r e a t e r d e t a i l . In Appendix A we g i v e a d e t a i l e d comparison of the NPP d i s c i p l i n e and a p a r t i c u l a r a l t e r n a t i n g p r i o r i t y system. C. ALTERNATING PRIORITY MODELS 1. Previous I n v e s t i g a t i o n s C y c l i c p r i o r i t y and e s p e c i a l l y a l t e r n a t i n g p r i o r i t y queueing models with only a s i n g l e server have been analyzed with some degree of success. The f i r s t work was that of A v i - Itzhak, e t . a l . [AVI 65] who analyzed the a l t e r n a t i n g p r i o r i t y model (two customer c l a s s e s ) with exhaustive s e r v i c e to each queue. In t h i s treatment, the s e r v e r switches queues without any intermediate d e l a y s , but l a t e r s t u d i e s r e l a x e d t h i s r e s t r i c t i o n [SYKE 70], [EISE 71]. F u r t h e r g e n e r a l i z a t i o n of the model was f o r multiqueue systems [COOP 69,70],[EISE 72], s t i l l f o r the s i n g l e s e r v e r case. The more general c y c l i c s e r v i c e regime in which up to k, customers are served from queue 1 , then up to k 2 customers from queue 2 , and so on f o r v queues, denoted here by C ( k,,k 2,...,k v) , has only r e c e n t l y been attempted, notably by [NAIR 76] and [SCHL 81] i n which v =2 , and [KUEH 79] i n which v > 2 but k ± =1 f o r a l l queues. A l l of t h i s p r e v i o u s work, however, i s a p p l i c a b l e only to the s i n g l e s e r v e r model, and e x t e n s i o n s to m u l t i p l e s e r v e r s would seem to be extremely d i f f i c u l t . The a n a l y t i c a l i n t r a c t a b i l i t y of m u l t i s e r v e r models a r i s e s from the unknown i d e n t i t i e s of the customers i n s e r v i c e at any p a r t i c u l a r time. For example, i n the s i n g l e s e r v e r case i t i s 15 known that the job i n s e r v i c e at any time i s from the queue the server i s a t t e n d i n g at that moment. With s > 1 s e r v e r s , however, the only d e f i n i t e knowledge about the customers i n s e r v i c e i s that at l e a s t one must be from the queue the group of s e r v e r s i s a t t e n d i n g at that p a r t i c u l a r moment. The i d e n t i t i e s , of the other customers i n s e r v i c e are unknown. 2. Markov Chain Model — Non-exhaustive S e r v i c e Consider now the a l t e r n a t i n g p r i o r i t y C(k,,k 2) m u l t i s e r v e r Markovian system with no sw i t c h i n g d e l a y s . A Markov chai n model f o r such a system has a s t a t e space with f i v e independent dimensions, s i n c e any system s t a t e can be d e s c r i b e d completely by the f o l l o w i n g f i v e v a r i a b l e s : n, the t o t a l number i n the system s 1 f the number of type 1 customers i n s e r v i c e q,, the number i n queue 1 i , an i d e n t i f i e r of the queue c u r r e n t l y being served c, a counter f o r the customers a l r e a d y served from the c u r r e n t queue i n the c u r r e n t s e r v i c e c y c l e . For n f i x e d , say n = n 0 ^ s , then the p o s s i b l e ranges f o r the other four s t a t e v a r i a b l e s a r e : Si,: 0,1,2,... ,s q,: 0,1,2,... , ( n 0 - s ) c • 1f2f3f*«* f ^ l -1f 2 • Not a l l combinations of these s t a t e s can e x i s t , but at l e a s t we can say that the number of s t a t e s with n = n 0 w i l l be p r o p o r t i o n a l to (k,+k 2) . Observe t h a t (k 1+k 2) i s the number 16 of p o s s i b l e c o n f i g u r a t i o n s of the two s t a t e v a r i a b l e s c and i . I f i t were not f o r t h i s f a c t o r , i t w i l l be seen ( I I I - D) that there would be approximately the same number of s t a t e s , given n = n 0 , as i n the 2 - c l a s s non-preemptive p r i o r i t y models. For a l t e r n a t i n g p r i o r i t y models other than the very s i m p l e s t , k., = 1 , k 2 = 1, the number of s t a t e s i n the Markov chain model can be exceedingly l a r g e , and so a numerical s o l u t i o n may become q u i t e c o s t l y . 3. Markov Chain Model — Exhaustive S e r v i c e The exhaustive s e r v i c e v a r i a t i o n may be a p p l i e d to e i t h e r one or both queues. The r e s u l t i n g numerical model turns out to be " s m a l l e r " i n the sense that there are not as many p o s s i b l e s t a t e s f o r a given system p o p u l a t i o n n = n 0 . For example, with exhaustive s e r v i c e to both queues, C( 00, 0 0 ) , a complete Markov cha i n r e p r e s e n t a t i o n w i l l r e q u i r e a s t a t e space of only four dimensions. The corresponding s t a t e v a r i a b l e s are n, s 1 f q l f and i , and f o r n = n 0 > s , the p o s s i b l e ranges of the other v a r i a b l e s a r e : s ^: 0,1,2,... ,s q, : 0,1,2,... , ( n 0 - s ) i : 1,2. Again not a l l combinations of these s t a t e s e x i s t , but we see that the f a c t o r ( k i + k 2 ) f o r the C(k,,k 2) model has been r e p l a c e d by the f a c t o r 2 ( s i n c e i = 1 ,2) f o r t h i s C(°°,°°) model. Thus the number of s t a t e s f o r f i x e d n = n 0 i s about the same as i f k,=t, k2=1 in the p r e v i o u s a l t e r n a t i n g p r i o r i t y 17 system C ( k 1 , k 2 ) . The s o l u t i o n of the exhaustive s e r v i c e system would t h e r e f o r e i n general r e q u i r e much l e s s computational e f f o r t . D. • NON-PREEMPTIVE PRIORITY MODELS 1. Previous I n v e s t i g a t i o n s A n a l y t i c a l s t u d i e s of non-preemptive p r i o r i t y M|M|s queueing models (s > 1) have progressed somewhat f u r t h e r than those of c y c l i c p r i o r i t y systems. F i r s t o b t ained was the average w a i t i n g time f o r members of each p r i o r i t y c l a s s [COBH 54]. U n f o r t u n a t e l y t h i s a n a l y s i s was only p o s s i b l e under the r a t h e r r e s t r i c t i v e assumption that a l l customer c l a s s e s have the same s e r v i c e time d i s t r i b u t i o n . Most subsequent improvements to t h i s work a l s o r e q u i r e d u n i f o r m i t y of s e r v i c e times [DAVI 66], [WILL 80]. Those which allow unequal s e r v i c e times must d i s a l l o w queueing f o r one customer c l a s s a l t o g e t h e r [BHAT 76], or abandon the non-preemptive d i s c i p l i n e i n favor of preemptive p r i o r i t i e s [HALF 72], [GOLD 81], or no p r i o r i t i e s at a l l ( f i r s t - c o m e , f i r s t - s e r v e d ) . The absence of a n a l y t i c a l 0 r e s u l t s f o r the general case of customer c l a s s e s with d i f f e r e n t s e r v i c e time d i s t r i b u t i o n s again can be a t t r i b u t e d to the unknown d i s t r i b u t i o n of customer types i n s e r v i c e at any p a r t i c u l a r time. When a l l customers have the same s e r v i c e time d i s t r i b u t i o n , t h e i r i d e n t i t i e s as members of d i f f e r e n t p r i o r i t y groups disappear a f t e r they have been admitted to s e r v i c e . When s e r v i c e times f o r each c l a s s are d i f f e r e n t , however, then the i d e n t i t i e s of the customers are maintained even a f t e r they have 18 entered s e r v i c e , and the number of customers of each type i n s e r v i c e w i l l have some e f f e c t on the w a i t i n g times of those which have not yet been served. I t seems that attempts at a n a l y t i c a l s o l u t i o n of both c y c l i c p r i o r i t y and non-preemptive p r i o r i t y schemes have f a l l e n upon the same problem, namely the h e t e r o g e n e i t y of the customers i n s e r v i c e at any one time. C y c l i c p r i o r i t y models have allowed d i f f e r e n t s e r v i c e times f o r d i f f e r e n t customer types, but have r e s t r i c t e d the system to one s e r v e r . Non-preemptive p r i o r i t y models have r e s t r i c t e d a l l customer c l a s s e s to a s i n g l e s e r v i c e time d i s t r i b u t i o n , but have allowed m u l t i p l e s e r v e r s . I t should be noted t h a t s i n g l e s e r v e r NPP systems with d i f f e r e n t s e r v i c e times f o r customer c l a s s e s have been s o l v e d [COBH 5 4 ] . However, the complementary problem i n ' c y c l i c p r i o r i t y , a m u l t i p l e s e r v e r model with a l l s e r v i c e time d i s t r i b u t i o n s i d e n t i c a l , seems not yet to have been t r e a t e d . 2. Markov Chain Model A numerical s o l u t i o n of the 2 - c l a s s M|M|s NPP model r e q u i r e s l e s s computational e f f o r t than does the a l t e r n a t i n g p r i o r i t y model. The Markov c h a i n s t a t e space r e q u i r e s only three independent dimensions: n, s,, q, . Compared with the a l t e r n a t i n g p r i o r i t y model C ( k 1 f k 2 ) , we see that the s t a t e v a r i a b l e s c and i have been dropped. Consequently the number of s t a t e s f o r a given n = n 0 > s , i s e s s e n t i a l l y h a l f of what i t would be f o r the s i m p l e s t a l t e r n a t i n g p r i o r i t y systems C(1,1) , or. C C 0 0 , 0 0 ) . T h i s advantage of s i m p l i c i t y i s 19 one reason why the NPP model was s e l e c t e d f o r c l o s e r a n a l y s i s . 20 IV. NUMERICAL SOLUTION TECHNIQUE A. THE STATE SPACE As mentioned i n the p r e v i o u s chapter, the non-preemptive p r i o r i t y model r e q u i r e s a s t a t e space of three independent dimensions. For convenience a s t a t e w i l l be l a b e l l e d by four components (s, s 2 ; q, q 2 ) , where s 1 f s 2 are the number of customers of types 1 and 2 i n s e r v i c e , and q,, q 2 are the number of customers of types 1 and 2 w a i t i n g f o r s e r v i c e . The c e n t r a l c o n t r o l l e r , the d e v i c e which s e l e c t s a w a i t i n g customer f o r s e r v i c e whenever a departure occurs, does not need to be represented by a separate s t a t e v a r i a b l e . I t s behaviour i s t o t a l l y determined by the given s t a t e (s, s 2 ; q, q 2 ) (see Appendix A). I t i s convenient with two customer c l a s s e s to t h i n k of there being only one queue (pooled s t o r a g e ) , with type 1 customers at the f r o n t and type 2's at the back. The t o t a l number of customers in the system i s n = s,+s 2+q 1+q 2 . As t h i s model assumes unbounded queue l e n g t h s , the dimensions q, and q 2 (or n and q,) are a l s o unbounded. When n < s (s= number of s e r v e r s ) then: 0 < s ± < n ( i = 1 ,2) , q,= 0, q 2= 0 and s,+s 2 = n . When n > s , then: 0 < s ± < s (i=1,2), q,,q 2 > 0 and s,+s 2 = s , Q i + Q 2 = n - s . One c h o i c e of three independent dimensions f o r t h i s s t a t e space i s (n,s,,q,) . In what f o l l o w s we choose r a t h e r to use the 21 more convenient s t a t e v e c t o r (s, s 2 ; q i q2) • B. THE BALANCE EQUATIONS The steady s t a t e balance equations are o btained i n continuous-time Markov chain models by equating the t r a n s i t i o n (or flow) r a t e i n t o a p a r t i c u l a r s t a t e with the t r a n s i t i o n r a t e out of the s t a t e . T h i s p r e s c r i p t i o n i s not always easy to f o l l o w f o r systems of d i m e n s i o n a l i t y g r e a t e r than one because o b t a i n i n g the t o t a l flow r a t e i n t o a given s t a t e from i t s neighbours may not be a t r i v i a l matter. An e a s i e r but more mechanical approach to the c o n s t r u c t i o n of the balance equations i s given below. Let P(s! s 2 ; q i q2) be the s t a t i o n a r y p r o b a b i l i t y that the system i s i n the s t a t e (s, s 2 ; q, q 2 ) . These p r o b a b i l i t i e s f o r s t a t e s i n a t h r e e - d i m e n s i o n a l s t a t e space are ordered by a s i n g l e i n d e x i n g v a r i a b l e i (i=1,2,3,... ) to form the i n f i n i t e column v e c t o r of p r o b a b i l i t i e s x^ . Adapting equation (2.1) then: x T Q = 0 T (4.1) — CO — with x and 0 both column v e c t o r s . Given that the system i s — CO — c u r r e n t l y i n s t a t e i then: Q±± = t r a n s i t i o n r a t e out of s t a t e i (negative) Q ±. = t r a n s i t i o n r a t e from s t a t e i to s t a t e j Note that by c o n s t r u c t i o n , a l l rows of Q sum to z e r o . The balance equation c o e f f i c i e n t s appear along the columns of Q . A l l t h a t i s now necessary i s to generate the Q ± j c o e f f i c i e n t s ( u s u a l l y row-by-row) and then from the s t r u c t u r e of the columns 22 of Q , deduce the gen e r a l form of the balance e q u a t i o n s . The s e r v i c e d i s c i p l i n e f o r non-preemptive p r i o r i t y may be s t a t e d as f o l l o w s (assume n>s): At the next departure from the system s e l e c t f o r s e r v i c e a type 1 customer, u n l e s s qi= 0 , i n which case s e l e c t a type 2 customer. T h i s s e r v i c e r u l e governs the a l l o w a b l e s t a t e t r a n s i t i o n s due to departures from the system. Combining these with the t r a n s i t i o n s caused by system a r r i v a l s , a s t a t e space t r a n s i t i o n diagram can be c o n s t r u c t e d (see Appendix B). Once the s e r v i c e r u l e s f o r a queueing system have been c l e a r l y expressed i t i s not a d i f f i c u l t matter to generate the Q.. c o n d i t i o n a l t r a n s i t i o n r a t e s . R e c a l l that i i s the index of the system's c u r r e n t s t a t e , w r i t t e n i= (s, s 2 ; q i q 2 ) > with number of customers n = s 1+s 2+q 1+q 2 • The o b j e c t s t a t e j w i l l have p o p u l a t i o n (n ± 1). Then: O n I T + X. 2 +S 1 H 1 + s 2 * 2 ) n > 0 r I (s, + 1 s 2 • 9 0 0 ) n < s I p j= (s, s 2 m 9 q 1 + i q 2 ) n > s X-2 I (s, S 2 + 1 m f 0 0 ) n < s < (s, s 2 • f q, q 2 + D n > s S 1 K ! * j= ( s , -1 s 2 9 9 0 0 ) n < s j= (s , -1 S 2 + 1 m t 0 q 2 - D n > s .j= (s, s 2 • • r q i - 1 q 2 ) n > s, 'j= (s, s 2-1 • 0 0 ) n < s j = (s, + 1 s 2-1 • 9 q1-1 q 2 ) n > s, q i * j= (s, s 2 • 9 0 q 2 - D n > s (4.2) These t r a n s i t i o n r a t e s are a complete l i s t of a l l a l l o w a b l e t r a n s i t i o n s i n d i c a t e d by the s t a t e space t r a n s i t i o n diagram i n Appendix B. 23 G e n e r a l i z i n g the s t r u c t u r e of the columns of Q , we can now o b t a i n the steady s t a t e balance e q u a t i o n s . ( x , n 2 + s , ( . , + s 2 « 2 ) P ( S , s 2 ) X, P(s,-1 s 2 ) + X 2 P ( s , s 2-1 ) + ( S , + 1 ) * , P(s , + 1 s 2 ) + (S 2+1) n2 P ( s , s 2+1) 0 < n < s-1 (4.3) (X ,+k2 + s, u i+s 2 >. 2) P(s, s 2 ) n = s = X, P(s,-1 s 2 ) + X 2 P(s, s 2-1) + s,m P(s, s 2 ; 1 0) + (s, +1 ) »», P(s, + 1 s 2 - 1 ; 0 1) + ( s 2 +1) u2 P(s,-1 s 2 +1; 1 0) + S 2 K 2 P t s , s 2 ; 0 1) (4.4) (X. ,+X2+s , u , + s 2 u 2 ) P(s, s 2 ; q, q 2 ) n > s+1 X, P(s, s 2 ; q,-1 q 2 ) + X 2 P(s, s 2 ; q, q 2"D + s , (•, P ( s , s 2 ; q , +1 q 2 ) + 6(q,) (s, + l ) 1*1 P(s, + 1 S 2 - 1 ; 0 q 2 + D + ( S 2 + 1) t.2 P(s,-1 s 2+1; q, + 1 q 2 ) + 6(q,) s 2 „ 2 P(s, s 2 ; 0 q 2 + D (4.5) Here we have used the f o l l o w i n g conventions: P(s, s 2 ; q, q 2 ) = 0 , when any index i s nega t i v e , P(s, s 2 ) = P(s, s 2 ; 0 0), 6(q,) = 0 q,= 0 i \0 otherwise . In standard matrix form, the balance equations are w r i t t e n as the transpose of (4.1): QT x = 0 ( 4 . 6 ) The s u c c e s s i v e rows of Q represent the balance equations f o r the s t a t e s i= (s, s 2 ; q, q 2 ) , ordered f i r s t with i n c r e a s i n g n , then with i n c r e a s i n g q, , and f i n a l l y with i n c r e a s i n g s 2 . With t h i s o r d e r i n g of s t a t e s , the n > s pa r t of matrix T Q possesses only a few d i f f e r e n t (s+1 x s+1) r e c u r r i n g b l o c k s of c o e f f i c i e n t s , a f a c t which s i m p l i f i e s the automatic g e n e r a t i o n of the balance e q u a t i o n s . Other o r d e r i n g s with index q 2 r e p l a c i n g q, , or s, r e p l a c i n g s 2 would be e q u a l l y c o n v e n i e n t . Refer to Appendix C(1) f o r f u r t h e r comments and an 24 example. A f i n i t e system of balance equations i s obtained by i n c l u d i n g equations of the form ( 4 . 5 ) with those.of ( 4 . 3 ) and (4.4) u n t i l a l l those s t a t e s f o r which n = n , a c u t o f f parameter, have been represented on the l e f t - h a n d s i d e of (4.5 ) . The right-hand s i d e s of these equations c o n t a i n s t a t e s with n= 0 up to n= n +1 . Consequently, viewed as a system of homogeneous l i n e a r e quations, the n c - t r u n c a t e d model would have a r e c t a n g u l a r c o e f f i c i e n t matrix A, with more columns than rows. The dimensions of t h i s matrix are d e r i v e d i n Appendix C ( 2 ) . C. THE LINEAR PROGRAMMING SOLUTION TECHNIQUE As mentioned in the d i s c u s s i o n of Markov modeling, one of the techniques f o r s o l v i n g an i n f i n i t e set of balance equations i s the l i n e a r programming s o l u t i o n of [KOTI 7 7 ] . From ( 4 . 6 ) , the i n f i n i t e l i n e a r system of balance equations i s w r i t t e n : Q T x = 0 ( 4 . 6 ) — oo — with n o r m a l i z a t i o n : I X-L = 1 . ( 4 . 7 ) i=1 T The f i n i t e matrix A i s obtained by s e l e c t i n g from Q the f i r s t Nj_ rows and Nj columns. In ge n e r a l N j i Nj , and the small e r the d i f f e r e n c e (NJ-NJ- ) , the b e t t e r w i l l be the r e s u l t s produced (see Appendix C ( 2 ) ) . The minimum value of ^ N J _ N I ^ f o r a given N J f i s determined both by the s t r u c t u r e of the Markov c h a i n model, and by the o r d e r i n g of the corresponding balance e q u a t i o n s . 2 5 D e f i n e x as the f i n i t e column v e c t o r of the steady s t a t e p r o b a b i l i t i e s ( x i ; i=1,2,... /N^}. T h i s t r u n c a t i o n of x^ means that the n o r m a l i z a t i o n (4.7) can no longer be a p p l i e d . However, a weaker but bro a d l y a p p l i c a b l e c o n d i t i o n , d e r i v e d from steady s t a t e arguments and (4.7), can be used i n s t e a d (see IV - D): B x = b (4.8) with B a row ve c t o r of constant non-negative c o e f f i c i e n t s , b a s c a l a r p o s i t i v e c o n s t a n t . The t r u n c a t e d problem may now be c a s t as a l i n e a r program (LP): Minimize and maximize each {Z, ; k=1,2,... K] sub j e c t to the c o n s t r a i n t s : A x = 6 B x = b (4.9) x > 0 . The o b j e c t i v e f u n c t i o n s (Z k} may be chosen as any l i n e a r combinations of the s t a t e p r o b a b i l i t i e s x^ which are of i n t e r e s t . For example, i f mean w a i t i n g times are d e s i r e d then these may be expressed i n terms of the x i u s i n g L i t t l e ' s Law (see V - C). To o b t a i n both the maximum and minimum of each w a i t i n g time the LP (4.9) must a l t o g e t h e r be s o l v e d four times. Another a p p l i c a t i o n i s to l e t the Z^ be components of a marginal p r o b a b i l i t y d i s t r i b u t i o n , Z k = P(k) , k=1,2,. . . ,K in which case each P(k) i s a l i n e a r combination of the s t a t e p r o b a b i l i t i e s x± (see V - B). The LP (4.9) must then be so l v e d 2K times to o b t a i n the maximum and minimum values of the p r o b a b i l i t i e s P ( k ) . These numerical v a l u e s form the set of upper bounds {P uCO}, and the set of lower bounds (P^(k)}, (k=1,2,... ,K), f o r the true steady s t a t e p r o b a b i l i t y 26 d i s t r i b u t i o n P(k) of the system. That i s , Pa (k) < P(k) < P u ( k ) , k=1,2,... ,K . (4.10) Note that n e i t h e r the components P £ ^ ) > n o r the components P u ( k ) form a p r o b a b i l i t y d i s t r i b u t i o n themselves, s i n c e i n gene r a l n e i t h e r sum to u n i t y . D. NORMALIZATION CONSTRAINTS We now c o n s i d e r the task of choosing a p p r o p r i a t e c o n s t r a i n t s which w i l l ensure that any s o l u t i o n of the l i n e a r program (4.9) w i l l be c o n s i s t e n t with the n o r m a l i z a t i o n (4.7): oo I x. = 1 . (4.7) i=1 1 E q u i v a l e n t l y , f o r (4.7) we wr i t e co E p(n) = 1 (4.11) n = 0 where p(n) i s the t o t a l p r o b a b i l i t y of n customers i n the system (n>0). These c o n d i t i o n s , c o l l e c t i v e l y c a l l e d n o r m a l i z a t i o n c o n s t r a i n t s , are represented as a g e n e r a l i z a t i o n of (4.8): B x = b (4.12) with B the c o e f f i c i e n t matrix, of dimension (^ x N j ) , b a constant column v e c t o r (^ x 1). These N N c o n s t r a i n t s are assumed to be non-homogeneous e q u a l i t i e s i n v o l v i n g at most only the f i r s t Nj components of x . — 0 0 R e c a l l that the t r u n c a t i o n of the i n f i n i t e system of balance equations means that the o r i g i n a l n o r m a l i z a t i o n (4.7) can no longer be e x a c t l y represented as a c o n s t r a i n t i n an LP. In i t s p l a c e , K o t i a h [KOTI 77] prese n t s without proof the 27 f o l l o w i n g : s-1 E (1 - n/s) p(n) = 1 - p . (4.13) n=0 In Appendix D we d e r i v e (4.13) under the assumption that a s t a t i o n a r y p r o b a b i l i t y d i s t r i b u t i o n f o r number i n the system p(n) e x i s t s , with E r p(n) = 1 (4.11). In other words, the system i s assumed to reach a steady s t a t e . K o t i a h suggests that (4.13) and (4.11) are e q u i v a l e n t f o r a l a r g e ( u n s p e c i f i e d ) c l a s s of queueing systems. However, we know only that (4.11) i m p l i e s (4.13); the reverse need not n e c e s s a r i l y be t r u e . Consider the m u l t i s e r v e r non-preemptive p r i o r i t y queue. I t i s p o s s i b l e to s o l v e the t r u n c a t e d Markov c h a i n model f o r p(n) which s a t i s f y (4.13), but which sum to a value much gr e a t e r that one. C l e a r l y such a s o l u t i o n v i o l a t e s (4.11) because p h y s i c a l l y a l l values of p(n) must be non-negative r e g a r d l e s s of whether they are i n c l u d e d i n the t r u n c a t e d Markov c h a i n model (0 ^ n < n +1) or are not (n > n c + l ) . Thus f o r the queueing system c o n s i d e r e d here, equations (4.11) and (4.13) are not e q u i v a l e n t . We observe that none of the four examples i n . K o t i a h ' s o r i g i n a l paper [KOTI 77] seem to give r i s e to s i m i l a r problems. To preclu d e the p o s s i b i l i t y of o b t a i n i n g LP s o l u t i o n s which v i o l a t e (4.11), an a d d i t i o n a l c o n s t r a i n t must be i n c l u d e d : N J E x ± < 1 (4.14) i = 1 or e q u i v a l e n t l y , n +1 T p(n) < 1 . (4.15) n=0 Mo d i f y i n g K o t i a h ' s o r i g i n a l LP s o l u t i o n technique to use both n o r m a l i z a t i o n c o n d i t i o n s (4.13) and (4.15) i n s t e a d of j u s t 28 (4.13) alone, then should allow i t s extension to models which are not so i n h e r e n t l y "well-behaved" as those c o n s i d e r e d i n [KOTI 77]. To f i t the new c o n s t r a i n t (4.14) i n t o the form (4.12) a new v a r i a b l e y , c a l l e d a " s l a c k v a r i a b l e " , i s i n t r o d u c e d such t h a t : N J E x + y = 1 i=1 (4.16) y £ 0 T h i s v a r i a b l e i s appended to the end of the t r u n c a t e d p r o b a b i l i t y v e c t o r x , which now w i l l have (N^+1) components. The column dimension of c o e f f i c i e n t m a t rices A and B must s i m i l a r l y be i n c r e a s e d by one. E. IRREDUCIBILITY OF THE MARKOV CHAIN The complete m o d i f i e d l i n e a r programming problem may f i n a l l y be w r i t t e n : Maximize and minimize Zy. , a l i n e a r f u n c t i o n of x, subj e c t to x = |^0j (4.17) x > 0 where, A i s the (N xx Nj+1) c o e f f i c i e n t matrix of the N I balance equations, B i s the (%x Nj+1) c o e f f i c i e n t matrix of the N N n o r m a l i z a t i o n c o n s t r a i n t s . In the present a n a l y s i s NJJ = 2, but N and Nj depend on the s e l e c t e d t r u n c a t i o n ^ (see Appendix C ( 2 ) ) . The standard LP s o l u t i o n method i s the simplex a l g o r i t h m [LUEN 73], i n which a s p e c i a l kind of search i s made to determine the optimum of the o b j e c t i v e f u n c t i o n Z k . However, we w i l l show that f o r many Markov ch a i n queueing models the simplex a l g o r i t h m need not be 29 a p p l i e d to the e n t i r e problem (4.17), but only to a small p a r t of i t . T h i s r e s u l t s i n a s u b s t a n t i a l savings i n computer s o l u t i o n time. 1. The S i g n i f i c a n c e of I r r e d u c i b i 1 i t y The n o t i o n of i r r e d u c i b i l i t y i s a well-known c h a r a c t e r i s t i c of some Markov c h a i n s . A Markov c h a i n i s s a i d to be i r r e d u c i b l e i f and only i f every s t a t e can be reached from every other s t a t e in a f i n i t e number of steps [BHAR 60, p.14]. More mathematically, an i r r e d u c i b l e Markov chain i s one i n which the d i s c r e t e - t i m e t r a n s i t i o n p r o b a b i l i t y matrix P cannot be w r i t t e n : P = | P, 0 P 2 • P i 0 Because of the way any continuous-time Markov ch a i n can be represented as a d i s c r e t e - t i m e c h a i n (see II - B), the p r e v i o u s d e f i n i t i o n holds with P r e p l a c e d by Q . Many Markov models of queueing systems are indeed i r r e d u c i b l e Markov c h a i n s . The present NPP system i s no e x c e p t i o n , as can e a s i l y be seen by the s t r u c t u r e of the balance equations (Appendix C ( 3 ) ) . Consider now the N balance equation c o n s t r a i n t s i n the LP (4.17). Since any s t a t e i may be reached from any other s t a t e j , i t f o l l o w s that i f the s t a t i o n a r y p r o b a b i l i t y of s t a t e i i s zero, x.= 0 , then so a l s o must there be zero i p r o b a b i l i t y of the system being i n s t a t e j : x^= 0 . C o n t i n u i n g t h i s reasoning and using the p r o p e r t y of i r r e d u c i b i l i t y , we f i n d x.. = 0 , j = 1,2,... ,H1 . T h e r e f o r e we conclude that i f an i r r e d u c i b l e Markov chain i s to have a non- n u l l s t a t i o n a r y s o l u t i o n , then not one of i t s s t a t e s may have a 30 zero steady s t a t e p r o b a b i l i t y . T h i s o b s e r v a t i o n , which was i n d i r e c t l y used i n [KOTI 77], forms the k e r n e l of our improvements to Kotiah's LP s o l u t i o n method. 2. Improvements to the LP A l g o r i t h m Suppose we apply the simplex a l g o r i t h m to an a r b i t r a r y LP problem with m c o n s t r a i n t s and n v a r i a b l e s (n > m): U x = u (4.18) A b a s i c s o l u t i o n x^ i s d e f i n e d as the s o l u t i o n of (4.18) when a c e r t a i n (n-m) -component subset of {x i} i s set to zero. The remaining m nonzero v a r i a b l e s are c a l l e d b a s i c v a r i a b l e s , and together they form the b a s i s s e t . There are at most f n ] b a s i c s o l u t i o n s . The simplex a l g o r i t h m i n e f f e c t "searches" those b a s i c s o l u t i o n s which are a l s o f e a s i b l e (x^ > 0) f o r the one which optim i z e s the o b j e c t i v e f u n c t i o n Z [LUEN 73]. Now we can invoke the i r r e d u c i b i l i t y p r o p e r t y to show that the number of b a s i c f e a s i b l e s o l u t i o n s to (4.17) i s much l e s s that the general maximum (jj^J • I r r e d u c i b i l i t y guarantees that i f any one of the v a r i a b l e s x.̂  , 1 < i < N-j- , i s set to zero, then a l l the other v a r i a b l e s x̂  , 1 < j * i < N-j- , must a l s o be z e r o . T h i s would v i o l a t e the n o r m a l i z a t i o n c o n s t r a i n t (4.13) and so no b a s i c s o l u t i o n to (4.17) can e x i s t i f any of the f i r s t Nj v a r i a b l e s are excluded from the b a s i s s e t . The b a s i s set must then c o n t a i n a l l of the f i r s t Nj. v a r i a b l e s . The set i s completed by choosing (m-N-j. ) f u r t h e r components of x b out of the remaining (n-N^. ) c a n d i d a t e s . The number of p o s s i b l e b a s i c s o l u t i o n s has thus been reduced from fn\ to /n-Nj m J \m-Nj 31 From (4.17) we f i n d n = Nj+1 , m = Nj+2 , so t h a t : n - Nj> = f N j + l - N j ^ = (NJ+1-NJ.) (NJ-NJ) /2 (4.19) T h i s i s an e x t r a o r d i n a r y r e d u c t i o n i n the number of s o l u t i o n s which must be searched by the simplex a l g o r i t h m . As a consequence, what would have been a p r o h i b i t i v e l y expensive numerical a n a l y s i s has now been made a f f o r d a b l e . F. IMPLEMENTATION OF THE MODIFIED LP ALGORITHM A s p e c i a l s o l u t i o n program was w r i t t e n f o r the LP (4.17) to take f u l l advantage of the computational savings gained by r e c o g n i z i n g the Markov ch a i n ' s i r r e d u c i b i l i t y . The c e n t e r p i e c e of the program i s the s o - c a l l e d " r e v i s e d simplex method" [MURT 81, p.24 f f . ] , the standard computer a l g o r i t h m used to s o l v e g e n e r a l LP problems. However, t h i s method i s a p p l i e d only to determine the i d e n t i t i e s of the l a s t two v a r i a b l e s in the optimum b a s i s s e t ; the f i r s t Rj. v a r i a b l e s i n any b a s i s are a l r e a d y known. In p r a c t i c e t h i s means that the steps of the simplex method are a p p l i e d o n l y to the .(N -N +1) " f r e e " columns of £B] ' "^ R E E " ^N the sense that they are not known a p r i o r i to be a necessary p a r t of a l l b a s i c s o l u t i o n s . The a l g o r i t h m works with the L U - f a c t o r i z a t i o n of the b a s i s matrix. The b a s i s matrix i s the (m x m) square matrix formed from those columns of ^ g j which correspond to v a r i a b l e s i n the c u r r e n t b a s i s s e t . As each new b a s i c s o l u t i o n i s o b t a i n e d d u r i n g the search f o r an optimum, the L U - f a c t o r i z a t i o n must be updated. For t h i s purpose we use the scheme of B a r t e l s - G o l u b [MURT 81]. The s o l u t i o n program r e q u i r e s the user to s p e c i f y two f r e e 32 v a r i a b l e s which w i l l complete the f i r s t b a s i s s e t , i e . y i e l d the f i r s t b a s i c f e a s i b l e s o l u t i o n . We have chosen the v a r i a b l e s (Nj+1) (the s l a c k v a r i a b l e y ) , and (Nj-4) . T h i s c h o i c e has a s i g n i f i c a n c e which w i l l be e x p l a i n e d i n the next chapter (see V - E ) . Besides the p r o p e r t y of i r r e d u c i b i l i t y , a perhaps e q u a l l y important p r a c t i c a l aspect of the LP (4.17) i s the extreme s p a r s i t y of the c o e f f i c i e n t matrix . In f a c t t h i s matrix can be c l a s s i f i e d as super-sparse because the number of d i s t i n c t c o e f f i c i e n t s i s very s m a l l compared with the t o t a l number of nonzero e n t r i e s . Such a matrix can be very e f f i c i e n t l y s t o r e d in compacted form [KALA 71]. The L U - f a c t o r i z a t i o n and the manipulations of the simplex method w i l l preserve some degree of s p a r s i t y (though not s u p e r - s p a r s i t y ) . Consequently, standard sparse matrix data s t r u c t u r e s [GUST 72] can be used throughout the computations. The L U - f a c t o r i z a t i o n of the i n i t i a l b a s i s matrix i s based on a standard Gaussian e l i m i n a t i o n a l g o r i t h m , m o d i f i e d to take advantage of s p a r s i t y . We have used an i n i t i a l s tep of "symbolic" f a c t o r i z a t i o n (a s i m p l i f i e d a d a p t a t i o n of Sherman's NSPIV program [SHER 78a,b]) to determine the changed s p a r s i t y s r u c t u r e of the f a c t o r e d b a s i s matrix. Then with t h i s i n f o r m a t i o n the p u r e l y numerical steps of f a c t o r i z a t i o n are f i n a l l y performed, using an a l g o r i t h m given i n [GUST 72]. In the f a c t o r i z a t i o n step we f i n d again some u s e f u l p e c u l i a r i t i e s i n the s t r u c t u r e of the LP (4.17). In p a r t i c u l a r the (N-j-x Nj) submatrix of A , c a l l i t A, , (which forms by 33 f a r the l a r g e s t p a r t of every b a s i s matrix) e x h i b i t s d i a g o n a l dominance by columns. T h e r e f o r e an L U - f a c t o r i z a t i o n which proceeds along the d i a g o n a l elements (no p i v o t i n g ) i s guaranteed to be n u m e r i c a l l y s t a b l e [REID 74]. The a l g o r i t h m then need not employ any complicated p i v o t i n g s t r a t e g y nor r e q u i r e the f a c i l i t y f o r dynamic row and column i n t e r c h a n g e s . Furthermore, L U - f a c t o r i z a t i o n w i l l be s t a b l e on any symmetric permutation of the rows and columns of A, , that i s , on II A, n T , with n the permutation matrix. The permutation n may then be s e l e c t e d s o l e l y to minimize the c r e a t i o n of nonzero elements in l o c a t i o n s where there were only z e r o s . F i n d i n g a row and column o r d e r i n g to reduce t h i s " f i l l - i n " i s a somewhat h e u r i s t i c p r o c e s s , but i t i s u s u a l l y a worthwhile search s i n c e a good o r d e r i n g can g r e a t l y reduce e x e c u t i o n time and memory c o s t s . An e f f i c i e n t permutation was found to be one i n which the row and column order of A, i s simply r e v e r s e d : the l a s t row i s p l a c e d f i r s t , the s e c o n d - l a s t row i s p l a c e d second, and so on; l i k e w i s e f o r the columns. We found e x p e r i m e n t a l l y f o r A t of order = 1000 that t h i s row and column permutation r e s u l t s i n a very l a r g e r e d u c t i o n i n execution time, at l e a s t by a f a c t o r of t e n . A l l of the m o d i f i c a t i o n s d i s c u s s e d i n t h i s s e c t i o n have been i n c o r p o r a t e d i n t o the LP s o l u t i o n a l g o r i t h m . To t e s t the o p e r a t i o n of the f i n a l program, we a p p l i e d i t to the s o l u t i o n of the M|M|2 FCFS queue. The program s u c c e s s f u l l y d u p l i c a t e d K o t i a h ' s p u b l i s h e d r e s u l t s [KOTI 77] f o r the system. In the next chapter we apply these numerical techniques to s o l v e the M|M|4 NPP 2 - c l a s s queueing model. The e f f e c t i v e n e s s and 34 e f f i c i e n c y of the m o d i f i e d a l g o r i t h m w i l l then be assessed. 35 V. RESULTS A. SYSTEM PARAMETERS We now present numerical r e s u l t s f o r the s = 4 server case of the m u l t i s e r v e r 2 - c l a s s NPP queueing system. To make the correspondence between t h i s queueing model and the communications system i n t r o d u c e d i n chapter I we i d e n t i f y type 1 and type 2 customers as data and v o i c e messages r e s p e c t i v e l y . The mean s e r v i c e times of these two customer types are ((, , ) • ' = 5 s e c , and (it 2 ) " 1 = 1 2 0 sec. The mean a r r i v a l r a t e s X, and X 2 are not d i r e c t l y s p e c i f i e d . Rather, f o r each numerical s o l u t i o n we f i x the t r a f f i c i n t e n s i t y p and the p r o p o r t i o n of type 1 a r r i v a l s to the system, a,. R e c a l l from (II I - A) that X = X,+X2. Then d e f i n e o ± = X ±/ X ( i = 1 ,2) , ( 5 . 1 ) so that i n gen e r a l a± i s the f r a c t i o n of incoming customers which are of type i (oi+o2=1)• A l l mean a r r i v a l r a t e s are thereby d e f i n e d s i n c e : (from Appendix D) p - X. / O_L + a_2_ "\ . (5.2) S \ V 1 t>2 ) The r a t e parameters X,, X 2, m i f i t a l l of which have dimension ( t i m e ) " 1 , may be measured i n any convenient u n i t of time; minutes i n s t e a d of seconds f o r example. Because type 2 customers have on average 24 times the s e r v i c e requirement of type 1 customers, the p r o p o r t i o n s o , , o 2 , of incoming customers do not d i r e c t l y r e f l e c t the d i v i s i o n of system resources between the two types. For example, i n order t o have the system's t o t a l s e r v i c e time a l l o t t e d e q u a l l y 36 there must be 24 new type 1 a r r i v a l s f o r each new type 2 customer. We f o r m a l i z e t h i s n o t i o n by d e f i n i n g p± (i=1,2) as the f r a c t i o n of system resources ("work") spent s e r v i n g customers of type i ( £ i + 0 2 = 1 ) « *i= P±/ P ( i = 1,2). (5.3) I d e n t i f y />i as the work expended by the system to serve c l a s s i customers (from Appendix D), P ± = X.±/ (s „ ± ) ( i = 1 ,2). (5.4) Using (5.1 - 5.4) we can show: », = [ 1 + ( o 2 M )/(a,n2) ]" 1 . (5.5) Then, f o r the above example, = 0.5 when d = 24/25 = 0.96 . F i g u r e 1 shows the r e l a t i o n s h i p between £, and o , f o r v a r i o u s r a t i o s »-i/i>2 . Each curve begins at ay = ty=0 with slope H 2 / M 1 and ends at c ^ p ^ l with slope n^/r<2 . In between, the value of a , at which the slope i s u n i t y , o , * , i s given by o , * = ( M / > 2 ) ' / 2 . (5.6) 1 + ( Y , / ^ ) 1 ' 2 For the c u r r e n t system nl/f2 = 24, and o , * = 0.83 . R e f e r r i n g to F i g u r e 1 we see c l e a r l y that there i s a wide region over which a l a r g e change i n o , produces only a small change in Only when a« > a , * does the d i v i s i o n of work w i t h i n the system (as measured by £,) become s e n s i t i v e to changes i n a , . However, while the systems a n a l y s t i s more i n t e r e s t e d i n p 1 f the user of a communications system i s more f a m i l i a r with o , . In what f o l l o w s then, both parameters w i l l be s p e c i f i e d . 37 F i g u r e 1 - R e l a t i o n s h i p Between Parameters and o , 38 B. THE STEADY STATE PROBABILITY DISTRIBUTION p(n) We f i r s t determine upper and lower bounds f o r each of the o b j e c t i v e f u n c t i o n s {Z k} c o r r e s p o n d i n g to the d i s t r i b u t i o n of number i n the system: p ( n ) , n=0,1,2,... ,n c + 1. R e c a l l that with the t r u n c a t i o n n= n f o r the i n f i n i t e set of balance c e q uations, the LP (4.17) i n c l u d e s s t a t e s x± f o r which n= 0 up to n= n£+1 (see IV - B). In terms of the i n d i v i d u a l s t a t e p r o b a b i l i t i e s P(s, s 2 ; q i q 2 ) we d e f i n e : n E P ( s 1 s 2 ; 0 0 ) 0 < n < s s,=0 (s 2= n-s,) p(n) = (5.7) n-s s E E P(s, s 2 ; q, q 2 ) n > s q,=0 s,=0 ( s 2 = s-s,) (q 2= n-s-q,) F i g u r e 2 shows the upper and lower bounds obtained on p(n) f o r the case />=0.7, o, = 0.B0, £,=0.14, n c=25 . The p l o t i s on a l o g a r i t h m i c s c a l e and f o r c l a r i t y the d i s c r e t e p o i n t s are connected by continuous curves, though s t r i c t l y a histogram r e p r e s e n t a t i o n should be used. The most obvious c h a r a c t e r i s t i c of t h i s curve i s the upward f l a r e on the t a i l end of the upper 1 bound. T h i s f e a t u r e seems to be present i n some degree no matter what set of parameters (p,c,) are chosen. N e i t h e r i s i t s p e c i f i c to t h i s p a r t i c u l a r queueing system. A more d e t a i l e d a n a l y s i s than that given i n [KOTI 77] of the M|M|2 FCFS 2 - c l a s s system r e v e a l s the same behaviour. Such a c h a r a c t e r i s t i c a r i s e s from the way i n which (p^(n)} and ( p u ( n ) } are computed. There are no c o n s t r a i n t s imposed on the sums 39 F i g u r e 2 - The D i s t r i b u t i o n p(n) f o r p = 0.7, o , = 0.80, 0.14) 40 n c +1 n c +1 I P > ) , Z pu(n) , n=0 n=0 because each maximum, p u ( n 0 ) , or each minimum, p ^ ( n 0 ) , i s the optimum of a unique l i n e a r programming problem (see IV - C ) . Consequently, the upward f l a r e i n {p u(n)} i s only the r e s u l t of a g e n e r a l tendency f o r the r e l a t i v e d i f f e r e n c e between the bounds ( i e . ( p u ( n ) - p ^ ( n ) ) / P^(n) ) to i n c r e a s e as n i n c r e a s e s . In some cases the upper and lower bounds f o r p ( n 0 ) where n 0 i s near to (n c+1) can be extremely poor indeed. In g e n e r a l , however, i f n c i s in c r e a s e d with n 0 h e l d c o n s t a n t , the bounds for p ( n 0 ) w i l l improve. More w i l l be s a i d l a t e r about t h i s concept of convergence (see V - F ) . F i g u r e s 3 and 4 are f u r t h e r examples of the upper and lower bounds obtained f o r p ( n ) . Both of these cases are f o r />=0.5 and n c=20, while F i g u r e 3 has a,=0.80 ($,=0.14), and F i g u r e 4 has a , = 0.95 (»3 1=0.44). We observe that f o r a f i x e d c i , g e n e r a l l y t i g h t e r bounds are obtained f o r l e s s c o s t ( s m a l l e r n ) when p i s decreased; compare F i g u r e s 2 and 3. For a f i x e d n and p, t i g h t e r bounds are obtained when o , (or B,) i s made s m a l l e r ; compare F i g u r e s 3 and 4. The general c h a r a c t e r of the bounds obtained f o r p(n) i s not i n c o n s i s t e n t with the p o s s i b i l i t y that p(n) v a r i e s g e o m e t r i c a l l y with n f o r n " l a r g e " . Many queueing systems show t h i s behaviour, even though the exact e x p r e s s i o n f o r p(n) may be more complicated. An example i s the M|M|s FCFS queue, for which p ( n ) a pn when n ^ s. 41 ]0 15 2(T NUMBER IN SYSTEI F i g u r e 3 - The D i s t r i b u t i o n p(n) f o r p = 0.5, o,= 0.80, (/»,= 0.14) 42 i o - i i n - I >- C Q o CC-" CD O c r • _ LO-I p= 0.5 a ,=0.950 =0.442 n6=2Q — i 1 1 10 15 20 NUMBER IN SYSTEM 25 30 F i g u r e 4 - The D i s t r i b u t i o n p(n) f o r p = 0.5, o,= 0.95, 0.44) ' 43 C. MEAN WAITING TIMES 1. Def i n i t ion An important performance measure of any queueing system i s the time a customer of a given c l a s s must wait i n the queue before being served. The e n t i r e continuous d i s t r i b u t i o n of w a i t i n g times i s of i n t e r e s t , but the present LP method i s best s u i t e d to o b t a i n bounds on the average w a i t i n g time. Denoting the mean w a i t i n g time of c l a s s i customers by W±, we have from L i t t l e ' s Law [KLEI 75, p.17]: W. = E(q. ) / \. ( i = 1 ,2) , (5.8) where E ( q i ) i s the average number of type i customers i n the queue. In terms of the s t a t e p r o b a b i l i t i e s P(s, s 2 ; q i q 2 ) then: W. = 1 E 1 \ ± n=s+1 n-s s I I q ± P(s, s 2 ; q, q 2 ) q ±=0 s,=0 ( 5 . 9 ) with q i + q 2 = n-s, s,+s 2 = s, and i=1,2 . There i s one very important d i f f e r e n c e between the e x p r e s s i o n s (5.9) and (5.7) f o r Wi and p ( n ) . Each p(n) can be represented e x a c t l y as the sum of a f i n i t e number of s t a t e p r o b a b i l i t i e s , whereas the exact r e p r e s e n t a t i o n of Wi i s an i n f i n i t e s e r i e s . T h i s same problem o c c u r r e d i n (IV - D) when the implementation of the n o r m a l i z a t i o n (4.11) was being c o n s i d e r e d . Here we apply the same remedy. Truncate the i n f i n i t e sum to n= nc+1 , and d e f i n e the o b j e c t i v e f u n c t i o n Z(W i) to be the e x p r e s s i o n given i n (5.9) with the i n f i n i t e upper l i m i t r e p l a c e d by (n +1). Then, 44 W. > Z(W.) (i=1,2) . (5.10) 1 i The LP method i s used to f i n d the maximum and minimum values of the right-hand, s i d e of (5.10). The minimum w i l l serve as a lower bound f o r W.̂  although i t w i l l not be as t i g h t as i t c o u l d be ( i f n c were g r e a t e r ) . On the other hand the maximum may i n f a c t not be an upper bound f o r Vl± at a l l , depending on the r e l a t i v e magnitude of n,. We must be c a r e f u l to choose n c l a r g e enough so that Z(W i) becomes a very c l o s e approximation to W (5.9). Then, f o r p r a c t i c a l purposes the LP s o l u t i o n s w i l l p r o vide true upper and lower bounds f o r W±. The problem of choosing a " l a r g e enough" n c w i l l be d i s c u s s e d l a t e r i n the s e c t i o n on convergence (V - F ) . 2. The L i m i t i n g Cases: o 1 -> 0, o 1 In t h i s s e c t i o n we determine the l i m i t i n g v alues f o r both W, and W2 as 0 , - ^ 0 , and 0,-^-1 . I t i s easy to determine W ^ O T - M ) and W 2(o 1-»0) because i n these cases the system i s very n e a r l y an M|M|s homogeneous type 1 or type 2 system r e s p e c t i v e l y . Then from [GROS 74 p.98]: v M c . - M ) = P o ( s p . ) s s„ , s! W 2 ( o i - » 0 ) = where, Po = S(i2 \1~P2 k r s-1 I ( S / > ) k=0 k! ( S p ) S (1-P) s! -'1 (5.11) (5.12) (5.13) To c a l c u l a t e W ^d-^O), imagine a s i n g l e type 1 customer e n t e r i n g an M|M|s homogeneous type 2 system. No matter how many type 2 customers are i n the system, t h i s type 1 customer w i l l , 45 because i t Was p r i o r i t y , go d i r e c t l y to the head of the l i n e , and i s guaranteed the next f r e e s e r v e r . I f t h i s customer's w a i t i n g time i s denoted by w 1 f then w, > 0 i f f n > s, and: E(w,|n) = J 0 n < s | ( s x 2 ) " 1 n £ s . Th e r e f o r e , E(w,) = E[ E(w,|n)] = E(w 1| n>s) Pr(n>s) . We d e f i n e VMd-^O) = E(w,). From [GROS 74, p.96] we o b t a i n Pr(n>s), and then: W^oi-^O) = pp (s/> 2) s . (5.14) Su2 (1 - P 2 ) s! The c a l c u l a t i o n of W 2(o 1->1) i s somewhat more d i f f i c u l t . Consider a s i n g l e type 2 customer e n t e r i n g an M|M|s homogeneous type 1 system. T h i s customer does not have p r i o r i t y , and i n f a c t must wait u n t i l the queue e n t i r e l y empties of type 1 customers before i t has a chance to occupy the next f r e e s e r v e r . Let t h i s w a i t i n g time be denoted by w2 . T h i s s i t u a t i o n i s e x a c t l y the same as that d i s c u s s e d by Cooper [COOP 72, pp.220- 223] f o r the behaviour of a " p o l i t e " customer i n an M|M|s homogeneous queue. A p o l i t e customer i s one which d e c l i n e s s e r v i c e as long as there are customers w a i t i n g . Cooper shows, using an a n a l y s i s of the M|M|s busy p e r i o d , that E(w 2| w2>0) = 1 . (5.15) ( , - P , ) 2 SUy Since w2 > 0 i f f n £ s, then: E(w 2|n) = J 0 n < s [ [ ( 1 - p , ) 2 s , . , ] - 1 n > s . Th e r e f o r e , E(w 2) = E[ E(w 2|n)] = E(w 2| n>s) Pr(n>s) . We d e f i n e W 2(c,-»1) = E ( w 2 ) . 46 Again using Pr(n>s) we have: W 2 ( o 1->1) = Po ( s p , ) s . (5.16) s»i, (1 - p ! ) i s! There are some i n t e r e s t i n g r e l a t i o n s h i p s between the four l i m i t i n g v a l u e s of Wi . F i r s t observe from ( 5 . 2 ) that f o r f i x e d p : / i , ( o r > 1 ) = p , and / > 2 ( o i ~ > 0 ) = fi • Making these s u b s t i t u t i o n s , we then d e f i n e R, and R 2 as: R, = W 2 ( o i - » 0) = W 2 ( c , - » 1) = 1 (5.17) W, ( 0 l - » 0) W , ( o , - » 1 ) ( 1-/)) R 2 = W,(o,-» 1 ) = W , U i ^ 1 ) = M 2 (5.18) W j ( o , - » 0) W , ( o , - » 0) u , ( I t can be shown f o r these two r a t i o s t h a t : R, > 1 f o r 0 < p < 1 (5.19) R 2 < 1 f o r 0 < p < (1 - u 2 / u , ) The four extreme values of w a i t i n g time, Wi (a,—>-0), W i(a 1->1), i = 1 , 2 , when p l o t t e d versus a, (or £ } ) form two p a r a l l e l l i n e s . These l i n e s have slope (R 2-1) W ^ C H - ^ O ) , and v e r t i c a l s e p a r a t i o n (R,-1) W , ( a , - » 0 ) . 3. Waiting Time R e s u l t s Now we present the computed upper and lower bounds on w a i t i n g time, p l o t t e d as a f u n c t i o n of the parameter p,, f o r the f o l l o w i n g three cases: F i g u r e 5 p = 0.7 n c = 30 6 0 . 5 25 7 0 . 3 20 . The. r e s u l t s from s i m u l a t i o n s t u d i e s of t h i s queueing system are a l s o shown. These w i l l be d i s c u s s e d l a t e r i n s e c t i o n D. The value s of Ŵ^ at the extreme p o i n t s P i = 0 , = are exact c a l c u l a t i o n s using the techniques of s e c t i o n C ( 2 ) . A l l other 47 48 F i g u r e 6 - Waiting Times as a F u n c t i o n of 0 , : p = 0.5, n = 25 c 49 F i g u r e 7 - Waiting Times as a F u n c t i o n of fi\ : P = 0.3 n = 20 c i: 50 I v a l u e s of W± have been obtained through numerical s o l u t i o n of the LP (4.17). Numerical s o l u t i o n s were computed f o r p,= 0.01 and 0 ! = 0.99 to i l l u s t r a t e the degree to which they approximate the known l i m i t i n g cases of fi,=0, pi = 1 . As can be seen from the graphs, the only s i g n i f i c a n t f a i l u r e of t h i s approximation i s the upperbound of W2 as fi,—>1 , f o r p > 0.5 . In f a c t f o r p= 0.7 the upper bound of W2 f o r £,= 0.99 i s so f a r from the known l i m i t i n g value W 2(o 1—M) that a numerical s o l u t i o n with a much higher n c would be necessary to o b t a i n a more u s e f u l upper bound. To generate the data i n F i g u r e s 5-7, the parameter n c was s e l e c t e d to ensure that the upper and lower bounds f o r each of W, and W2 were reasonably c l o s e together i n the r e g i o n 0 < < 0.2 . T h i s region i s of much p h y s i c a l i n t e r e s t because i t corresponds to a very wide range of a, (the p r o p o r t i o n of data messages): 0 < o, ^ 0.86 . In a d d i t i o n , n c had to be chosen s u f f i c i e n t l y l a r g e to ensure that the e r r o r due to t r u n c a t i o n of the exact e x p r e s s i o n f o r W.̂  (5.9) c o u l d reasonably be n e g l e c t e d (at l e a s t i n the given r e g i o n ) . These w a i t i n g time r e s u l t s a l s o show what was apparent by the p(n) graphs, namely that t i g h t e r bounds are obtained at l e s s c o s t ( s m a l l e r n c) with lower values of p and/or For f i x e d p and fit i t i s g e n e r a l l y t r u e that b e t t e r numerical bounds w i l l be o b t a i n e d only by i n c r e a s i n g the number of equations (higher n c) i n the LP (4.17). Greater convergence of the bounds i s thus d i r e c t l y l i n k e d with the computational c o s t of the numerical s o l u t i o n . These t o p i c s w i l l be d i s c u s s e d 51 l a t e r i n s e c t i o n s F and G . A more e x t e n s i v e LP s o l u t i o n c o u l d be a c o s t l y o p t i o n , and may not even be r e q u i r e d i f some f a i t h can be p l a c e d i n two very h e l p f u l e m p i r i c a l o b s e r v a t i o n s . T h i s d i s c u s s i o n w i l l , however, be d e f e r r e d u n t i l a f t e r the s i m u l a t i o n r e s u l t s have been presented. D. WAITING TIME SIMULATIONS Computer s i m u l a t i o n s of the M|M|4 2 - c l a s s NPP system were performed f o r two reasons: (1) To v e r i f y the v a l i d i t y of the n u m e r i c a l l y o b t a i n e d bounds on the mean w a i t i n g times. (2) To compare the r e l a t i v e c o s t and q u a l i t y of r e s u l t s o b t ained with s i m u l a t i o n s as opposed to numerical s o l u t i o n s u s i n g the LP method. The s i m u l a t i o n r e s u l t s are i n d i c a t e d in F i g u r e s 5-7 by 95% c o n f i d e n c e bands around each "measured" mean w a i t i n g time. A c% c o n f i d e n c e i n t e r v a l i s c a l c u l a t e d from the s t a t i s t i c a l v a r i a t i o n of the s i m u l a t i o n data such that on average the given range w i l l c o n t a i n the true value of the measured q u a n t i t y c times out of every 100 such s i m u l a t i o n s . From among the s e v e r a l methods f o r s t a t i s t i c a l a n a l y s i s of s i m u l a t i o n r e s u l t s now a v a i l a b l e we have chosen the " s u c c e s s i v e independent batch means" technique [FISH 78]. A s i n g l e s i m u l a t i o n run i s made, in which a very l a r g e number of customers are allowed to pass through the system. T h i s very long run i s d i v i d e d i n t o a c e r t a i n number of batches of equal l e n g t h ( i e . each with the same number of customers). From each batch the mean of the q u a n t i t y of i n t e r e s t i s then o b t a i n e d . By making the batches long enough, s u c c e s s i v e batch means become 52 s t a t i s t i c a l l y independent. The degree of independence i s t e s t e d u s i n g the C k s t a t i s t i c [FISH 78, p.238], a q u a n t i t y c l o s e l y r e l a t e d to the c o r r e l a t i o n between neighbouring batch means. Then, using standard techniques, 95% c o n f i d e n c e l e v e l s are o b t a i n e d on the o v e r a l l mean of the measured q u a n t i t y . The i n i t i a l s t a t e of every s i m u l a t i o n run i s a completely empty system. T h e r e f o r e to prevent any b i a s which might be i n t r o d u c e d i n t o the f i n a l r e s u l t s by the t r a n s i e n t s t a r t - u p behaviour, the r e s u l t s of the f i r s t batch are d i s c a r d e d . The s i m u l a t i o n program i t s e l f was w r i t t e n i n the s p e c i a l i z e d GPSS language [BOBI 76], and compiled by the o p t i m i z i n g compiler GPSS/H. Each s i m u l a t i o n run s i m u l t a n e o u s l y produced data f o r W, and W2. T h e r e f o r e the data i n F i g u r e s 5- 7 are the r e s u l t s of 12 d i f f e r e n t s i m u l a t i o n runs, each run d i v i d e d i n t o 20 batches of 4000 customers. I t i s u s u a l l y e a s i e r , i n terms of programming e f f o r t , to simulate a queueing system with the a i d of a s p e c i a l i z e d s i m u l a t i o n language than i t i s to set up and s o l v e the Markov c h a i n model of the system. However, whatever advantage i s gained i n programming e f f o r t c o u l d be l o s t when program running times are c o n s i d e r e d . G e n e r a l l y a l a r g e number of events (customer w a i t i n g times) must be observed before a c c e p t a b l e c o n f i d e n c e i n t e r v a l s f o r the means can be o b t a i n e d . As the r e s u l t s i n d i c a t e , the c o n f i d e n c e i n t e r v a l s are not everywhere as narrow as a systems a n a l y s t might l i k e . I f f o r c e r t a i n values of p and 0! b e t t e r r e s u l t s are d e s i r e d , then g r e a t e r c o s t s must be borne; the width of the c o n f i d e n c e i n t e r v a l s w i l l on 53 average decrease only as N~ 1 / 2 f where N i s the t o t a l number of o b s e r v a t i o n s . E. COMMENTS ON THE WAITING TIME RESULTS There are s e v e r a l o b s e r v a t i o n s , both e m p i r i c a l and t h e o r e t i c a l , which can be made about the c h a r a c t e r of the w a i t i n g time graphs i n F i g u r e s 5, 6, and 7. 1. E m p i r i c a l Observations Combining s i m u l a t i o n data with the n u m e r i c a l l y obtained bounds f o r w a i t i n g times, we may conclude with reasonable c o n f i d e n c e that the computed lower bounds are very near the true steady s t a t e v a l u e s . T h i s e m p i r i c a l f a c t i s e s p e c i a l l y u s e f u l fo r W2, i n which case the upper bound i s o f t e n too l a r g e to be of p r a c t i c a l use. Furthermore, a second e m p i r i c a l o b s e r v a t i o n may be used to v i r t u a l l y e l i m i n a t e much of the work performed by the LP s o l u t i o n a l g o r i t h m . We have observed f o r LP s o l u t i o n s of t h i s p a r t i c u l a r Markov ch a i n model, that the i n i t i a l b a s i c f e a s i b l e s o l u t i o n s p e c i f i e d i n (IV - F) generates the minimum values f o r W,, W2, and most of the p(n) o b j e c t i v e f u n c t i o n s . T h i s has been observed to be g e n e r a l l y t r u e f o r p > 0.5 , and 0, £ 0.1 , a region where a c c e p t a b l e and complete LP s o l u t i o n s become ever more expensive. These two o b s e r v a t i o n s seem to allow a convenient and inexpensive numerical approximation to be made f o r the mean w a i t i n g times W±: Solve the l i n e a r system (4.17) with the i n i t i a l b a s i s set given i n (IV - F ) . C a l c u l a t e W. and assume 54 that these q u a n t i t i e s are f i r s t of a l l lower bounds, and i n a d d i t i o n , are reasonably c l o s e to the unknown t r u e v a l u e s . T h i s procedure, based as i t i s s o l e l y on e m p i r i c a l evidence, i s c o n s t r a i n e d to apply o n l y to t h i s p a r t i c u l a r Markov ch a i n queueing model. No t h e o r e t i c a l support has been found which would allow i t s extension to other c a s e s . 2. Waiting Times i n a Non-preemptive P r i o r i t y System The g e n e r a l c h a r a c t e r of the VJ± vs. r e s u l t s may not at f i r s t be expected. As B ^ i n c r e a s e s more type 1 customers enter the system while the decrease i n the type 2 a r r i v a l r a t e i s r e l a t i v e l y s l i g h t , so why does W, decrease? The answer l i e s not only i n the p a r t i c u l a r assignment of p r i o r i t y , but a l s o i n the g e n e r a l nature of queueing systems with heterogeneous customer c l a s s e s . Because type 1 customers have non-preemptive p r i o r i t y , t h e i r mean w a i t i n g time i s l e s s than that of the type 2 customers, f o r any given p and £, . However, the v a r i a t i o n of Ŵ^ with 0, shown i n F i g u r e s 5-7 has more i n common with the M|M|s FCFS queue than with a p r i o r i t y queue. In g e n e r a l , w a i t i n g times depend on both p and u , i n c r e a s i n g with p and d e c r e a s i n g with u . They cannot be expressed s o l e l y i n terms of p , a s i s u s u a l l y the case f o r the mean number i n the system. In an M|M|s FCFS queue with the same two customer c l a s s e s , the average w a i t i n g time would range from that of a homogeneous type 2 M|M|s queue at B , = 0 , down to that of a type 1 queue at p,= 1 . Although p i s c o n s t a n t , the e f f e c t i v e average s e r v i c e r a t e c o n t i n u o u s l y i n c r e a s e s from s>»2 55 to SMI as 0 , i n c r e a s e s . The w a i t i n g time at 0 , = 1 i s »ii/c2 = 24 times lower than the value at p, = 0 . T h i s can be seen by comparing W ^ d - M ) and V)2(a,->0) , from equations (5.11, 5.12) i n s e c t i o n C(2) . T h e r e f o r e , even though type 1 customers have p r i o r i t y , they spend more time w a i t i n g f o r type 2 customers to leave s e r v i c e than they do w a i t i n g to reach the head of the l i n e . T h i s behaviour i s a d i r e c t r e s u l t of a s s i g n i n g p r i o r i t y to those customers with s h o r t e s t average s e r v i c e times ( g r e a t e s t i>). In t h i s s i t u a t i o n , however, the non-preemptive p r i o r i t y s e r v i c e d i s c i p l i n e takes on an e v e r - i n c r e a s i n g importance as the t r a f f i c i n t e n s i t y p i n c r e a s e s . At some p o i n t , say p= p* , the type 1 customers w i l l begin on average to spend more time j u s t g e t t i n g to the head of the l i n e than they a c t u a l l y spend there w a i t i n g f o r a f r e e s e r v e r . Consequently, the average wait of the p r i o r i t y customers depends more on customers of t h e i r own type than on the n o n - p r i o r i t y customers. Since f o r f i x e d p, X., i n c r e a s e s with p, , - X, = * , p Sn, (5.20) we may then expect that f o r p > p* , the w a i t i n g times of both types of customers w i l l i n c r e a s e as i 1 i n c r e a s e s . For p < p* the system i s dominated by type 2 customers, those with g r e a t e s t mean s e r v i c e time. For p > p* , the system i s dominated by the p r i o r i t y customers. Although s t r i c t l y unproven in t h i s c o n t e x t , a good assumption f o r p* i s obtained from s e c t i o n C(2) by s e t t i n g R 2= 1 (5.18): i e . W (c.-M) = W (d-s-0) (i=1,2). (5.21) 56 Both equations (i=1,2) give the same s o l u t i o n , P* = 1 ~ V Z / K i (n i > e 2 ) • (5.22) For the c u r r e n t model p* = 0.96, which i s too hig h to be of p r a c t i c a l s i g n i f i c a n c e . N e v e r t h e l e s s i t does serve to i l l u s t r a t e how e x t e n s i v e l y the type 2 customers, with t h e i r very long s e r v i c e times, dominate the behaviour of t h i s queueing system. A. CONVERGENCE OF UPPER AND LOWER BOUNDS If the LP s o l u t i o n technique i s to have an advantage over s i m u l a t i o n as a method of systems a n a l y s i s , i t must be able to provide comparable or " b e t t e r " r e s u l t s at lower o v e r a l l c o s t . A given computed r e s u l t i s seen as " b e t t e r " i f the d i f f e r e n c e between the upper and lower bounds i s sm a l l e r than the 95% confid e n c e range obtained from s i m u l a t i o n data. In t h i s s e c t i o n we look more c l o s e l y at the q u a l i t y of r e s u l t s produced using the LP method, while q u e s t i o n s of cost w i l l be d i s c u s s e d " i n the next s e c t i o n . The l i n e a r programming s o l u t i o n technique guarantees a non- i n c r e a s i n g sequence of upper bounds and a non-decreasing sequence of lower bounds as the LP i s solv e d with more and more c o n s t r a i n t s . Adding more balance equations b r i n g s the LP (4.17) c l o s e r i n form to the i n f i n i t e l i n e a r system (4.6) with the exact s o l u t i o n x^. Consequently the bounds on a p a r t i c u l a r o b j e c t i v e f u n c t i o n can be expected to converge s t e a d i l y toward the true steady s t a t e value as n c i n c r e a s e s . To t h i s argument we add the p r o v i s o that the o b j e c t i v e f u n c t i o n s must be able to 57 be expressed using only a f i n i t e subset of the s t a t e p r o b a b i l i t i e s {x±; 0 £ i £ Nj}. Into t h i s c l a s s f a l l the p r o b a b i l i t i e s ( p (n); Q£ n < (n c+1)}. A second c l a s s of o b j e c t i v e f u n c t i o n s are those which can only be d e f i n e d over an i n f i n i t e subset of the s t a t e p r o b a b i l i t i e s . Two examples of i n t e r e s t to us are the mean w a i t i n g times W, and W2. As t y p i c a l examples of convergence behaviour f o r the f i r s t c l a s s of o b j e c t i v e f u n c t i o n s , we have p l o t t e d in F i g u r e 8 the computed bounds f o r p(0) and p(4) as the LP i s so l v e d with ever g r e a t e r n^ . To he l p i n t e r p r e t t h i s graph, r e c a l l that the r e l a t i o n between n^ and m , the number of equations i n the LP, i s given from (4.17) and (C.2) as: m = N x + 2 m = [10 + 5(n -3)(n -2)/2. + (n -3)] + 2 . ' (5.23) c c c I t i s a l s o h e l p f u l to know that the o v e r a l l computational cost of the LP s o l u t i o n i s roughly p r o p o r t i o n a l to (see V - G). To show the convergence of bounds f o r o b j e c t i v e f u n c t i o n s of the second type, we present F i g u r e s 9, 10, and 11. There, the computed bounds f o r W, and W2 are p l o t t e d as a f u n c t i o n of n c , f o r three d i f f e r e n t s e t s of system parameters (/>,<»,). Because o b j e c t i v e f u n c t i o n s of t h i s c l a s s have had to be approximated by f i n i t e t r u n c a t i o n s of t h e i r i n f i n i t e expansions, the e r r o r induced by such a t r u n c a t i o n must be assessed before the r e s u l t s can be i n t e r p r e t e d as upper and lower bounds. For example, c o n s i d e r the mean w a i t i n g times W . R e c a l l from (V - C(1)) that Z(vO i s the o b j e c t i v e f u n c t i o n o b t a i n e d by t r u n c a t i n g the expression f o r W. at n= n +1. . A l s o r e c a l l 58 F i g u r e 8 - Convergence of Bounds f o r P r o b a b i l i t i e s p ( 0 ) , p(4) 59 F i g u r e 9 - Convergence of Waiting Time R e s u l t s : p = 0.7, o,= 0.80, (*,= 0.14) 60 p = 0 . 5 a =0 . 8 0 0 P , = 0 . 1 4 2 ~l 1 1 1 1 1 5 10 15 20 ^ 25 30 sim. F i g u r e 10 - Convergence of Wai t i n g Time R e s u l t s : p = 0.5, o,= 0.80, (*,= 0.14) 61 F i g u r e 11 - Convergence of Wa i t i n g Time R e s u l t s : p = 0.5, 0 1 = 0.95, 0.44) 62 that the computed minimum of Z(W i) w i l l always be a lower bound fo r W± . On the other hand, the computed maximum of Z(W ±) may or may not be an upper bound f o r W±f depending on the degree of t r u n c a t i o n e r r o r . There are thus two opposing f o r c e s which a f f e c t the convergence of the computed maximum of Z(W ±). F i r s t , the maximum of Z(W i) w i l l tend to i n c r e a s e as n c i n c r e a s e s because more and more nonzero terms are being added to the expansion f o r ZfVT) . Secondly, as the LP i s s o l v e d with more and more c o n s t r a i n t s there i s the tendency f o r the maximum to decrease toward the true value of W± . Only when the f i r s t e f f e c t , t h a t of t r u n c a t i o n e r r o r , has been made n e g l i g i b l e i s i t safe to i n t e r p r e t maxlzfw.^)} as an upper bound f o r Vv\ . F i g u r e s 9-11 show a s t r i k i n g d i f f e r e n c e i n the convergence behaviour of the "bounds" f o r W, and W2. The maximum of Z(W 2) i n i t i a l l y seems to be a f f e c t e d by t r u n c a t i o n e r r o r . Soon a peak i s reached, and from there the i n t r i n s i c convergence pr o p e r t y of the LP method dominates, c a u s i n g max{Z(W 2)}, now an upper bound fo r W2, to decrease s t e a d i l y . In c o n t r a s t , the computed maximum of Z(W,) c o n s i s t e n t l y i n c r e a s e s as n • i n c r e a s e s (as shown by the p r e c i s e numerical r e s u l t s ) , i n d i c a t i n g that t r u n c a t i o n e r r o r i s always the dominant f a c t o r . Consequently there , i s no e a s i l y d i s t i n g u i s h e d p o i n t beyond which we can say that max{Z(W,)} i s an upper bound f o r W,. N e v e r t h e l e s s , a type of convergence does take p l a c e , as the d i f f e r e n c e betweeen the maximum and minimum valu e s of Z(W,) s t e a d i l y d e creases. For p r a c t i c a l purposes t h i s i s an e n t i r e l y a c c e p t a b l e behaviour. One must only be c a r e f u l to choose n l a r g e enough so that the 63 two curves connecting the computed l i m i t s of Z(W,) have become n e a r l y h o r i z o n t a l . F i g u r e s 9-11 suggest that the t i g h t n e s s of the numerical bounds obtained f o r a given value of n decreases as e i t h e r or both p and i n c r e a s e . T h i s was observed a l s o i n F i g u r e s 2- 7. No c o n c r e t e convergence r e l a t i o n s h i p has been found, however. In consequence, the user of the LP method of a n a l y s i s w i l l have to assess the convergence c h a r a c t e r i s t i c s of the system fo r at l e a s t a few d i f f e r e n t s e t s of parameters. A f t e r t h i s i n i t i a l e x perience, the user w i l l be able to s e l e c t a value of n c which w i l l ensure, f o r a given set of system parameters, that u s e f u l upper and lower bounds w i l l be computed. G. COMPUTATIONAL COSTS T h i s s e c t i o n examines s e v e r a l p r a c t i c a l a spects of the LP s o l u t i o n program, c h i e f l y those which a f f e c t computational c o s t . In a d d i t i o n , we compare the r e l a t i v e c o s t s of s i m u l a t i o n and s o l u t i o n of the LP. 1. LP S o l u t i o n Cost A very important p r a c t i c a l c h a r a c t e r i s t i c of any LP program using the simplex a l g o r i t h m i s the average number of i t e r a t i o n s , J , executed before an optimum b a s i c s o l u t i o n i s a c h i e v e d . For a general (m x n) LP, experience shows that on average at l e a s t J = m i t e r a t i o n s are r e q u i r e d to o p t i m i z e each o b j e c t i v e f u n c t i o n [LUEN 73, p.55]. In our more s p e c i a l i z e d a l g o r i t h m however, in which a l l but two of the b a s i s v a r i a b l e s are known 64 a p r i o r i , many fewer i t e r a t i o n s are r e q u i r e d . On average (over parameters p, p,) we have found that J ranges i n a roughly l i n e a r f a s h i o n from J = 4 at n c= 6 (m=45), to J = 6.5 f o r n c= 30 (m=l929). R e c a l l that m i s the number of c o n s t r a i n t s i n the LP, which f o r t h i s p a r t i c u l a r queueing model i s given by (5.23). I t i s apparent from these s t a t i s t i c s t h a t an enormous computational savings has been r e a l i z e d through the use of the m o d i f i e d LP technique. A complete LP s o l u t i o n must maximize and minimize a number of d i f f e r e n t o b j e c t i v e f u n c t i o n s f o r a given set of parameters {p, p,, n c ) : W1f W2, and p ( n ) , 0 < n < ( n c + l ) . The t o t a l number of i t e r a t i o n s r e q u i r e d f o r t h i s task can be reduced c o n s i d e r a b l y by employing a " p a r a l l e l s earch" s t r a t e g y i n which at each i t e r a t i o n the new b a s i c s o l u t i o n i s t e s t e d f o r o p t i m a l i t y a g a i n s t a l l remaining o b j e c t i v e f u n c t i o n s . An economy i s achieved whenever a s i n g l e b a s i c s o l u t i o n o p t i m i z e s more than one o b j e c t i v e f u n c t i o n . We have found that with the complete set of (n^+4) o b j e c t i v e f u n c t i o n s l i s t e d above, the average number of i t e r a t i o n s r e q u i r e d per o b j e c t i v e f u n c t i o n i s approximately 1.5 . T h i s value i s roughly independent of the parameters (/>, p 1 r ), although f o r very c l o s e to 0.0 or 1.0 some decrease i s n o t i c e a b l e . To summarize then, J has been reduced from J = m f o r a general LP a l g o r i t h m , to J = 6 f o r the s p e c i a l i z e d LP, and f u r t h e r to J = 1.5 when a p a r a l l e l search i s employed. Computational c o s t p r i m a r i l y depends on the t o t a l number of i t e r a t i o n s necessary to optimize a l l the o b j e c t i v e f u n c t i o n s . 65 The only a d d i t i o n a l expense i s the i n i t i a l set-up of the b a s i s matrix and i t s L U - f a c t o r i z a t i o n . T h i s i s not u s u a l l y a s i g n i f i c a n t f a c t o r u n l e s s only a small number of o b j e c t i v e f u n c t i o n s are being o p t i m i z e d . With the complete set of (n c+4) o b j e c t i v e f u n c t i o n s we have found that the t o t a l e x e c u t i o n cost (CPU time p l u s memory charges) of an LP s o l u t i o n i n c r e a s e s roughly as m2 . Since m i s i t s e l f p r o p o r t i o n a l to f o r nc>> s (see 5.23), then c o s t i s p r o p o r t i o n a l to n," . The a c t u a l s o l u t i o n program was w r i t t e n i n FORTRAN and compiled with the o p t i m i z i n g compiler FORTRAN-H. S i n g l e p r e c i s i o n a r i t h m e t i c was g e n e r a l l y used, except when e: was near 0.0 or 1.0 , or when the computed upper and lower bounds were to .be very c l o s e t o g e t h e r . Use of double p r e c i s i o n i n c r e a s e s execution time by about 50%, and of course i n c u r s e x t r a memory c o s t s as w e l l . As a p a r t i c u l a r example of program performance, c o n s i d e r the run with p = 0.5, B : = 0.44, n £= 20 (m=794), i n s i n g l e p r e c i s i o n . I t r e q u i r e d 31 i t e r a t i o n s to maximize and minimize the 24 o b j e c t i v e f u n c t i o n s . T o t a l execution time was 19 seconds on an AMDAHL-470 V/8 computer. 2. A Comparison with S i m u l a t i o n Costs Included i n F i g u r e s 9-11 are s i m u l a t i o n r e s u l t s f o r each mean w a i t i n g time. R i g i d c o s t comparisons of s i m u l a t i o n and numerical s o l u t i o n are of l i m i t e d g e n e r a l i t y because of the l a r g e number of opt i o n s a v a i l a b l e to users of e i t h e r technique. A d d i t i o n a l l y , there may be a l a r g e d i f f e r e n c e i n e f f o r t i n i t i a l l y r e q u i r e d to develop the r e s p e c t i v e computer programs. 66 However, f o r completeness we present the f o l l o w i n g comparison. The s i m u l a t i o n data f o r each of F i g u r e s 9-11 were gathered from runs of 20 b l o c k s of 4000 customers each. No other s t a t i s t i c s b e s i d e s w a i t i n g times were c o l l e c t e d . To p l a c e the LP s o l u t i o n on an equal f o o t i n g , we c o n s i d e r only the two o b j e c t i v e f u n c t i o n s W,, W2 . A s i n g l e p r e c i s i o n s o l u t i o n with computational c o s t equal to one of the above s i m u l a t i o n s would occur f o r n somewhere between 25 and 30 . While numerical c s o l u t i o n s f o r these two values of n c are separated by a f a c t o r of two i n c o s t , the convergence of the bounds i s s u f f i c i e n t l y slow, so that the f o l l o w i n g q u e s t i o n can be answered: For s i m u l a t i o n s and s o l u t i o n s of the LP (4.17) of equal e x e c u t i o n c o s t , which method p r o v i d e s the b e t t e r r e s u l t s f o r the mean w a i t i n g times? The answer i s wholly unambiguous only f o r F i g u r e 10 (p = 0.5, o , = 0.8), i n which the LP s o l u t i o n produces b e t t e r bounds. For the other two cases the answer depends on whether W, or W2 i s c o n s i d e r e d . We conclude that the LP s o l u t i o n seems to provide b e t t e r r e s u l t s than a s i m u l a t i o n of equal c o s t over the (approximate) range of parameters: p & 0.5, c , £ 0.9, S 0.2 . 67 VI. CONCLUDING REMARKS A. LIMITATIONS OF THE MODEL S i m p l i f y i n g assumptions are necessary d u r i n g the course of any modeling p r o c e s s . They allow the o p e r a t i o n of the p h y s i c a l system under study to be made amenable to mathematical or computational methods. Upon completion of the modeling process the systems a n a l y s t must, however, r e - a s s e s s the assumptions of the model i n the context of the o r i g i n a l p h y s i c a l problem. The a p p l i c a b i l i t y of the present a n a l y s i s of a communications system i s c o n s t r a i n e d by some of the assumptions t r a d i t i o n a l l y made f o r such systems. In a d d i t i o n , a numerical s o l u t i o n of the Markov c h a i n equations f u r t h e r reduces the p o t e n t i a l g e n e r a l i t y of the a n a l y s i s . Perhaps the most obvious l i m i t a t i o n of the model i s that i t pr o v i d e s only a steady s t a t e s o l u t i o n . In r e a l i t y , the t r a n s i e n t behaviour and other time-dependent s o l u t i o n s f o r p e r i o d i c input t r a f f i c may be as important as the e q u i l i b r i u m c o n d i t i o n . The choice of a continuous-time Markov model i s r e l e v a n t to p h y s i c a l systems which operate i n continuous-time, or to those with r e l a t i v e l y short packet l e n g t h s . Even in steady s t a t e , there i s the q u e s t i o n of how w e l l the assumed e x p o n e n t i a l d i s t r i b u t i o n f o r i n t e r a r r i v a l times (Poisson a r r i v a l s ) . r e p r e s e n t s the a c t u a l message a r r i v a l p r o c e s s . However, t h i s assumption i s u s u a l l y an ac c u r a t e r e p r e s e n t a t i o n of r e a l i t y when a communications system serves many equal and independent message sources. The assumption of e x p o n e n t i a l l y 68 d i s t r i b u t e d s e r v i c e times may i n p r a c t i c e not be so w e l l j u s t i f i e d . I f a more gen e r a l r e p r e s e n t a t i o n of s e r v i c e times i s r e q u i r e d , one of the f a m i l y of E r l a n g d i s t r i b u t i o n s may be used. A continuous-time Markov cha i n model i s s t i l l p o s s i b l e although i t would have g r e a t e r complexity and r e q u i r e a more c o s t l y numerical s o l u t i o n . A second set of c o n s t r a i n t s a r i s e s from the demands of the LP s o l u t i o n method i t s e l f . For example, the number of channels (s) may be so l a r g e that the i n c r e a s e d number of s t a t e s renders an economical LP s o l u t i o n i m p o s s i b l e . In g e n e r a l , t h i s comment may be made of the e n t i r e Markov c h a i n modeling p r o c e s s . I f a p a r t i c u l a r system i s of such complexity that a Markov cha i n model would r e q u i r e a l a r g e number of s t a t e v a r i a b l e s , then i t might be w e l l to c o n s i d e r i n advance the use of a l t e r n a t e modeling techniques, p a r t i c u l a r l y s i m u l a t i o n . One assumption which i s always v i o l a t e d by a p h y s i c a l system i s that which allows i n f i n i t e queue l e n g t h s . A r e a l system w i l l have a f i n i t e number, say L, of storage p o s i t i o n s a v a i l a b l e f o r waiting, customers. When a l l L p o s i t i o n s are f i l l e d , a r r i v i n g messages are blocked from e n t e r i n g the queue. To make the b l o c k i n g p r o b a b i l i t y n e g l i g i b l e , L i s chosen l a r g e enough so that the system f u n c t i o n s almost as i f i t had i n f i n i t e w a i t i n g room. Unless L' i s q u i t e s m a l l , an exact numerical s o l u t i o n of the f i n i t e Markov cha i n would not be economical. Otherwise, the LP s o l u t i o n r e q u i r e s a t r u n c a t i o n of the set of balance equ a t i o n s . Because these balance equations are ordered with i n c r e a s i n g n ( t o t a l number i n the system), i t i s apparent 69 with a t r u n c a t i o n at n = n c , that L should be i n t e r p r e t e d as the maximum t o t a l number i n queue, r e g a r d l e s s of customer type. T h i s f a v o r s a system of pooled storage, i n which any customer f o r c e d to queue may be assign e d any one of the L storage p o s i t i o n s . The method of t r u n c a t i o n , and the s t r u c t u r e of the Markov ch a i n s t a t e space i t s e l f , i s not as w e l l s u i t e d to a system with separate queues f o r each customer type. B. SUMMARY AND CONCLUSIONS In t h i s t h e s i s we have set up a Markov ch a i n queueing model of a m u l t i c h a n n e l , combined v o i c e and data communications system, with non-preemptive p r i o r i t y f o r the data messages. No a n a l y t i c a l r e s u l t s are a v a i l a b l e f o r queueing systems of t h i s type. The most c l o s e l y r e l a t e d 2 - c l a s s M|M|s NPP models f o r which some a n a l y t i c a l r e s u l t s e x i s t e i t h e r r e q u i r e a l l s e r v i c e time d i s t r i b u t i o n s to be i d e n t i c a l , or r e q u i r e s = 1. A l i n e a r programming technique was t h e r e f o r e used to o b t a i n numerical bounds on q u a n t i t i e s of i n t e r e s t , most no t a b l y , the average w a i t i n g times of each customer c l a s s . K o t i a h ' s LP s o l u t i o n method c o u l d not be a p p l i e d i n i t s o r i g i n a l form because of the complexity and s t r u c t u r e of the Markov ch a i n model. F i r s t of a l l , the a d d i t i o n a l n o r m a l i z a t i o n c o n s t r a i n t (4.15) was added: n c + 1 E p(n) < 1 . (4.15) n=0 T h i s serves to g e n e r a l i z e the LP method to Markov ch a i n s f o r which the f i r s t c o n s t r a i n t (4.13), 70 s-1 I (1 - n/s) p(n) = 1 - p , (4.13) n=0 i s alone i n s u f f i c i e n t to ensure a c c e p t a b l e s o l u t i o n s . A second improvement i s the computational savings which are r e a l i z e d when the Markov c h a i n ' s p r o p e r t y of i r r e d u c i b i l i t y i s e x p l o i t e d . Both of these changes are widely a p p l i c a b l e to LP s o l u t i o n s of Markov ch a i n models other than the one s t u d i e d here. T h i s t h e s i s c o n t a i n s s e v e r a l r e s u l t s which are not d i r e c t l y r e l a t e d to our use of K o t i a h ' s LP technique. A proof i s given f o r equation (4.13) which shows i t to be a v a l i d steady s t a t e c o n d i t i o n f o r a wide c l a s s of queueing systems. Although i t was i n d i c a t e d i n [KOTI 77] that (4.13) c o u l d be d e r i v e d through d i r e c t summation of the balance equations, the proof given i n Appendix D i s a more general and i n t u i t i v e l y p l e a s i n g r e s u l t . In a d d i t i o n , the present 2 - c l a s s M|M|s NPP queue serves as a counter-example to the p r o p o s i t i o n that (4.13) i s e q u i v a l e n t to (4.11). A second important a n a l y t i c a l r e s u l t of t h i s t h e s i s i s the c l a r i f i c a t i o n of mean w a i t i n g time behaviour i n a heterogeneous 2 - c l a s s NPP queueing system. We r e f e r e s p e c i a l l y to the v a r i a t i o n of w a i t i n g times with the parameter (at constant p), and the r e l a t i o n s between the l i m i t i n g values W i(o 1->0), W ± ( a 1 - » 1 ) , (i=1,2). The p a r t i c u l a r change in the w a i t i n g time behaviour p r e d i c t e d f o r p = p* f u r t h e r i l l u s t r a t e s the behaviour of queueing systems of t h i s type. The primary concern i n u s i n g the LP method to determine bounds on mean w a i t i n g times i s e n s u r i n g that the computed r e s u l t s are a f f e c t e d only n e g l i g i b l y by t r u n c a t i o n e r r o r . 71 Herein l i e s one of the l i m i t a t i o n s of a numerical a n a l y s i s : i f an o b j e c t i v e f u n c t i o n has an i n f i n i t e expansion i t cannot be e x a c t l y computed, the degree of e r r o r i n a t r u n c a t e d approximation u s u a l l y unknown except through e m p i r i c a l s t u d i e s . T h i s i s the reason why higher order moments of the w a i t i n g time d i s t r i b u t i o n s were not computed. Although L i t t l e ' s Law can be g e n e r a l i z e d f o r these q u a n t i t i e s [KLEI 75, p.240], t r u n c a t i o n e r r o r would be much more severe. For q u a n t i t i e s l i k e p ( n ) , however, which have f i n i t e r e p r e s e n t a t i o n s , true upper and lower bounds can always be computed. I n c r e a s i n g the number of balance equations (m) i n the LP reduces the t r u n c a t i o n e r r o r f o r the mean w a i t i n g time o b j e c t i v e f u n c t i o n s . For o b j e c t i v e f u n c t i o n s which can be expressed e x a c t l y i n terms of a f i n i t e number of s t a t e p r o b a b i l i t i e s , the upper and lower bounds converge towards each other as the s i z e of the LP i n c r e a s e s : each component v a r i a b l e becomes more and more c o n s t r a i n e d as a d d i t i o n a l equations are i n c l u d e d . A second c l a s s of o b j e c t i v e f u n c t i o n s are those, such as the mean w a i t i n g times, f o r which an exact r e p r e s e n t a t i o n r e q u i r e s an i n f i n i t e number of the s t a t e p r o b a b i l i t i e s . Adding more balance equations to the LP means the e x p r e s s i o n s f o r these o b j e c t i v e f u n c t i o n s span more nonzero terms. N e v e r t h e l e s s , the r e s u l t s show that at l e a s t the d i f f e r e n c e between the upper and lower bounds decreases as the s i z e of the LP i n c r e a s e s . These b e n e f i t s of i n c r e a s i n g the s i z e of the LP are gained at the expense of a d d i t i o n a l computational e f f o r t : computational c o s t s were found to i n c r e a s e roughly as m2. 72 Compared with simulation,' the LP s o l u t i o n s were found to p r o v i d e b e t t e r r e s u l t s at l e s s c o s t over the approximate range of parameters p < 0.5, a, <, 0.9 . The use of s i m u l a t i o n c o u l d be recommended f o r the a n a l y s i s of systems o p e r a t i n g o u t s i d e of t h i s r e g i o n . Whichever method i s employed, the use of e x t r a p o l a t i o n and other h e u r i s t i c techniques may render an exhaustive formal a n a l y s i s unnecessary. Such h e u r i s t i c s may only suggest themselves, however, a f t e r great f a m i l i a r i t y has been a c q u i r e d with the p a r t i c u l a r Markov c h a i n model. C. SUGGESTIONS FOR FURTHER STUDY There are two main areas which deserve f u r t h e r study. These ar e : (1) the study' of s o l u t i o n techniques f o r i n f i n i t e Markov ch a i n models, (2) the comparison of m u l t i c l a s s , m u l t i s e r v e r systems with v a r i o u s s e r v i c e d i s c i p l i n e s . As d i s c u s s e d i n chapter I I , the two main numerical techniques f o r t r u n c a t i n g and s o l v i n g i n f i n i t e Markov ch a i n s are those of Seneta-Wolf, and K o t i a h . Although we have employed the LP method of K o t i a h , i t would be i n t e r e s t i n g to compare our r e s u l t s with those which c o u l d be obtained using the a l t e r n a t e approach of Seneta and Wolf. I t would be p a r t i c u l a r l y u s e f u l to compare the convergence behaviour of the two methods. Further e f f o r t c o u l d a l s o be d i r e c t e d towards a search f o r convenient and u s e f u l system approximations. One such approximation might be to somehow combine s t a t e s whose i n d i v i d u a l p r o b a b i l i t i e s are not e x p l i c i t l y r e q u i r e d , but whose aggregrate p r o b a b i l i t y i s 73 important. For example, combine s e t s of s t a t e s with f i x e d q,, q 2 , but with d i f f e r e n t s e r v e r c o n f i g u r a t i o n s , i n t o the s i n g l e s t a t e (*; q, q 2 ) . Aside from f u r t h e r work i n the methodology of Markov c h a i n s o l u t i o n s , the techniques themselves might p r o f i t a b l y be a p p l i e d to the a n a l y s i s and comparison of other m u l t i c l a s s , m u l t i s e r v e r queueing systems. For example, a comparison c o u l d be made among the v a r i o u s s e r v i c e d i s c i p l i n e s : c u t o f f p r i o r i t y , preemptive p r i o r i t y , non-preemptive p r i o r i t y , and g e n e r a l a l t e r n a t i n g p r i o r i t y . A l e s s comprehensive comparison might i n c l u d e only an a n a l y s i s of mean w a i t i n g times. L i m i t i n g arguments s i m i l a r to those employed i n t h i s t h e s i s c o u l d be used to estimate the dependence of W± on the system's mixture of customer c l a s s e s (fi±). A l t e r n a t i v e l y , a s i n g l e system might be s t u d i e d i n more d e t a i l , perhaps by making the model correspond more r e a l i s t i c a l l y to a true communications system, or by determining the minimum number of s e r v e r s to ensure a given l e v e l of system performance. 74 APPENDIX A - A COMPARISON OF NON-PREEMPTIVE PRIORITY AND ALTERNATING PRIORITY SERVICE DISCIPLINES In t h i s appendix we d i s c u s s and compare two s p e c i f i c s e r v i c e d i s c i p l i n e s , non-preemptive p r i o r i t y f o r type 1 customers (denoted NPP), and the a l t e r n a t i n g p r i o r i t y case C(°°,1). R e c a l l that C(°°,1) means that queue 1 i s served e x h a u s t i v e l y , then queue 2 has at most one customer admitted f o r s e r v i c e . The two s e r v i c e d i s c i p l i n e s , g e n e r a l a l t e r n a t i n g p r i o r i t y C(k,,k 2) and NPP are i n g e n e r a l q u i t e d i f f e r e n t ; i t i s only the p a r t i c u l a r case C(°°,1) t h a t i s n e a r l y i n d i s t i n g u i s h a b l e from the NPP system. In f a c t , when the r u l e s f o r queue swi t c h i n g are p r o p e r l y chosen, the C(°°,1) system can be made to f u n c t i o n e x a c t l y the same as the NPP d i s c i p l i n e . In the f o l l o w i n g we assume f o r sake of convenience, that n>s , because a l l work-conserving s e r v i c e d i s c i p l i n e s should f u n c t i o n i d e n t i c a l l y whenever n<s . queue 1 , [ x a r r i v a l s c e n t r a l s s e r v e r s c o n t r o l l e r F i g u r e 12 - Schematic of a 2-Class M u l t i s e r v e r Queueing System 75 To e x p l a i n the necessary queue s w i t c h i n g r u l e s we make use of the diagram i n F i g u r e 12 . Each s e r v i c e d i s c i p l i n e may be i n t e r p r e t e d as a set of r u l e s by which the c e n t r a l c o n t r o l l e r of F i g u r e 12 s e l e c t s w a i t i n g customers f o r s e r v i c e . The c o n t r o l l e r i s assumed to be able to sense the i d l e / b u s y s t a t e of each s e r v e r , as w e l l as the empty/not-empty s t a t e of each queue. With t h i s i n f o r m a t i o n the c o n t r o l l e r can d i r e c t w a i t i n g customers to f r e e s e r v e r s , s w i t c h i n g queues i f necessary. Queue t r a n s i t i o n s , represented by changes i n the s t a t e v a r i a b l e i , and a l l other o p e r a t i o n s of the c o n t r o l l e r are assumed to be instantaneous. In the NPP d i s c i p l i n e the c e n t r a l c o n t r o l l e r normally attends queue 1 ( i = l ) . Whenever a server becomes i d l e the c o n t r o l l e r w i l l , i f queue 1 i s not empty, s e l e c t a type 1 customer f o r s e r v i c e . I f queue 1 i s empty and queue 2 i s not, then a type 2 customer i s immediately served (i=2), and the c o n t r o l l e r r e t u r n s to monitor queue 1 ( i = l ) . In one v e r s i o n of the C(°°,1) system which .is not i d e n t i c a l to the NPP d i s c i p l i n e , the c o n t r o l l e r spends s l i g h t l y l e s s time on average observing queue 1. T h i s occurs because the c o n t r o l l e r switches from queue 1 (i=1) to queue 2 (i=2) as soon as i t senses that queue 1 i s empty and that queue 2 i s not. In gene r a l at t h i s i n s t a n t there need not be any f r e e s e r v e r s . If a customer i s i n queue 2 the c o n t r o l l e r r e s e r v e s i t to be served as soon as a s e r v e r becomes i d l e , even i f a type 1 customer a r r i v e s i n queue 1 i n the meantime. When one type 2 customer i s f i n a l l y sent to the f r e e s e r v e r , the c o n t r o l l e r r e t u r n s to 76 monitor queue 1 ( i = l ) . In t h i s same s i t u a t i o n the NPP c o n t r o l l e r would have f i r s t been ob s e r v i n g queue 1 u n t i l a server became a v a i l a b l e and so would have s e l e c t e d f o r s e r v i c e the type 1 customer j u s t a r r i v e d i n queue 1. To make the C(°°,1) d i s c i p l i n e e q u i v a l e n t to non-preemptive p r i o r i t y f o r type 1 customers, the queue s w i t c h i n g of the c o n t r o l l e r must be made server dependent r a t h e r than queue dependent. That i s , the c o n t r o l l e r should switch from queue 1 to queue 2 independently of e x a c t l y when queue 1 becomes empty, and only when a server becomes a v a i l a b l e f o r the next p o t e n t i a l type 2 customer. The s w i t c h i n g r u l e s then turn out to be e x a c t l y e q u i v a l e n t to those d e s c r i b e d above f o r the NPP system. Consequently, t h i s v e r s i o n of the Ci™,}) d i s c i p l i n e would s e l e c t f o r s e r v i c e the same customers i n the same order as would the NPP s e r v i c e d i s c i p l i n e . In f a c t , i t i s not even necessary in a Markov c h a i n model of these simple systems that the o p e r a t i o n of the c o n t r o l l e r be e x p l i c i t l y r e p resented by a s t a t e v a r i a b l e ( i ) , as long as the c o n t r o l l e r i s understood to operate as d e s c r i b e d above. The reason i s that once the s t a t e v a r i a b l e s n, s,, q, have been s p e c i f i e d , the p o s i t i o n of the c o n t r o l l e r i s completely determined, and t h e r e f o r e i i s not an independent s t a t e v a r i a b l e . 77 APPENDIX B - THE STATE SPACE TRANSITION DIAGRAM As a v i s u a l a i d to the development of the steady s t a t e balance equations i t i s u s e f u l to c o n s t r u c t the s t a t e space t r a n s i t i o n diagram. The u t i l i t y of such a diagram, depends c r u c i a l l y on the c h o i c e of s t a t e v a r i a b l e s used to represent the s t a t e space. A f t e r some experimentation we have chosen to s p l i t the s t a t e space of the NPP model i n t o two p i e c e s : (1) n < s , 2-dimensional, with v a r i a b l e s ( s 1 f s 2 ) (2) n 2: s , 3-dimensional, with v a r i a b l e s (s, , q 1 f q 2 ) . For t y p i c a l s t a t e s i n each segment, the c o n d i t i o n a l t r a n s i t i o n r a t e s (Q^ ) to neighbouring s t a t e s are i n d i c a t e d . There can be at most four such t r a n s i t i o n s from each s t a t e , r e p r e s e n t i n g a r r i v a l s and departures of each of the two customer types. Forbidden t r a n s i t i o n s are those p r o h i b i t e d by the s e r v i c e d i s c i p l i n e , or those n a t u r a l l y i mpossible ( f o r example, no type 1 d e p a r t u r e s when s ^ O ) . F i g u r e s 13 and 14 below are one set of s t a t e space t r a n s i t i o n diagrams f o r the m u l t i s e r v e r 2 - c l a s s NPP queueing system. The two diagrams have only the (s+1) s t a t e s f o r n=s (<3i = Q2 = 0) i n common, and t r a n s i t i o n s between the two diagrams along t h i s boundary are noted a p p r o p r i a t e l y . 78 F i g u r e 14 - State Space f o r n ^ s 79 APPENDIX C ~ SETTING UP THE BALANCE EQUATION COEFFICIENT MATRIX "A": AN EXAMPLE T h i s appendix p r e s e n t s f u r t h e r d e t a i l s c o n cerning the s t r u c t u r e of the balance e q u a t i o n s . We a l s o show with an example how the i n f i n i t e system of equations i s ordered and tr u n c a t e d to form matrix A (see (4.9) i n IV - C ) . The three numbered s e c t i o n s of t h i s appendix are i n the order they are re f e r e n c e d i n the main t e x t . Part (1) R e c a l l t hat we found the s t a t e space of the 2 - c l a s s m u l t i s e r v e r non-preemptive p r i o r i t y system to be t h r e e - dimensional (see III - D). However, to set up and solve a system of balance equations the s t a t e s must be ordered s e q u e n t i a l l y i n one dimension. S t a t e s can be indexed i n order of i n c r e a s i n g p o p u l a t i o n n , but w i t h i n a group of s t a t e s with the same n , an o r d e r i n g should be chosen which: (1) f a c i l i t a t e s automatic g e n e r a t i o n of the balance equations, (2) minimizes the e f f o r t r e q u i r e d to f a c t o r i z e A i n t o t r i a n g u l a r components: A = LU (e.g. by min i m i z i n g the f i l l - i n of zero elements). One o r d e r i n g found s a t i s f a c t o r y was to index the s t a t e s f i r s t with i n c r e a s i n g n , then with i n c r e a s i n g q, , and then with i n c r e a s i n g s 2 . The r e s u l t f o r the case of s = 4 s e r v e r s , u s i n g the balance equations (4.3 - 4.5) of IV - B i s seen i n F i g u r e 15. T h i s diagram d i s p l a y s the upper l e f t - h a n d corner of the c o e f f i c i e n t matrix Q T f o r the i n f i n i t e set of balance e q u a t i o n s . The shaded squares represent nonzero c o e f f i c i e n t s . F i g u r e 15 - Matrix "A" For T\.=6, S=4 Servers 81 I n d i c a t e d along the top and s i d e are the groups of s t a t e s f o r which n = 0,1,2,... . The balance equations, f o r s t a t e s with n > s = 4 , d i s p l a y a very r e g u l a r matrix s t r u c t u r e . T h i s i s e a s i l y seen when the c o e f f i c i e n t s are blocked i n t o square submatrices of dimension s+1 = 5 . When the a c t u a l balance equation c o e f f i c i e n t s are w r i t t e n i t i s seen that the e n t i r e matrix of c o e f f i c i e n t s f o r n > s c o u l d be represented u s i n g only f i v e d i f f e r e n t (s+1 x s+1) submatrices. The number of submatrices ( f i v e ) i s independent of s . With such a p r e d i c t a b l e s t r u c t u r e , the t r u n c a t e d matrix A can be e a s i l y generated up to any p r e s e l e c t e d c u t o f f n = n c . Part (2) The f i g u r e shows f o r the p a r t i c u l a r case n = 6 how the i n f i n i t e matrix of c o e f f i c e n t s would be t r u n c a t e d to N-j. equations and Nj v a r i a b l e s . The heavy black l i n e e n c l o s e s a l l of the balance equations f o r n =0,1,2,.. ,nc=6 . Before d e r i v i n g and we f i r s t must determine the number of s t a t e s which e x i s t i n the s t a t e space ( s, s 2 ; q i q 2 ) , fo r any f i x e d p o p u l a t i o n n = n 0 ^ 0 . For each n < s there w i l l be (n+1) s t a t e s s i n c e q,=0t q2=0, and s,+s 2 = n . For n > s , then qi+q2 = n-s , and t h e r e f o r e there are (n-s+1) c o n f i g u r a t i o n s f o r (q, q 2 ) . Since s,+s 2 = s f o r n £ s , the number of c o n f i g u r a t i o n s f o r (s, s 2 ) i s (s+1) . There are then (s+1)(n 0-s+1) s t a t e s f o r any given n = n 0 ^ s . The number of v a r i a b l e s Nj i s equal to the number of s t a t e s f o r which 0 ^ n < n +1 . T h e r e f o r e , with n £ s , c c 82 n c +1 N = 1 + 2 + ... + s + E (s+1)(n-s+1) J n=s or, N = s(s+1)/2 + (s+1)(n- S+2)(n_-s+3)/2 (C.1) J C l_ Then Nj =60 f o r the example n c = 6 . The number of equations N x might at f i r s t appear to be only those f o r which 0 ^ n < n . But on examination of the c balance equations in the nc+1 =7 group, three more equations are found which do not i n v o l v e any more than the N^ v a r i a b l e s a l r e a d y i n c l u d e d (see F i g u r e 15). These three a d d i t i o n a l equations can be i n c l u d e d i n the t o t a l number N^ of balance equation c o n s t r a i n t s . For t h i s example, then N = 4 0 + 3 =43 . Maximizing the number of c o n s t r a i n t s f o r a f i x e d number of v a r i a b l e s i n t h i s way, we are ab l e to o b t a i n the best p o s s i b l e bounds [KOTI 77]. In g e n e r a l , f o r a t r u n c a t i o n at n c , there w i l l be (n,-s+l) a d d i t i o n a l equations, and the tr u n c a t e d matrix A w i l l have dimensions (Nj_ x Nj) ' N j given by (C.1), and n N = 1 + 2 + ... + s + E° (s+1)(n-s+1) + ( n c - s + l ) n=s or, N = s ( s + l ) / 2 + (s+1 )(n c-s+1 )(n c-s+2)/2 .+ (n,-s+1). (C.2) Part (3) Fi g u r e 15 a l s o i l l u s t r a t e s the i r r e d u c i b i l i t y [BHAR 60, p.14] of the continuous-time Markov c h a i n model. In any given row, the s t a t e on the matrix d i a g o n a l can be reached from any of the s t a t e s with nonzero c o e f f i c i e n t s (shaded squares) on the l e f t or r i g h t . T h i s i s the b a s i c s t r u c t u r e of balance equations for many queueing systems; any s t a t e can be reached from any other s t a t e . Hence, the Markov chain i s rreduc i b l e . 84 APPENDIX D - A DERIVATION FOR THE NORMALIZATION CONDITION GIVEN IN [KOTI 77] Consider a queueing system with s i d e n t i c a l s e r v e r s and v customer types. The average customer a r r i v a l r a t e s are X i = a±\ (i=1,2,...,v) , where Z±<*± = 1 > a n c 5 i s t h e t o t a l average a r r i v a l r a t e . The average s e r v i c e times are y ± , (i=1,2...,v). The f o l l o w i n g reasoning i s guided by that of K l e i n r o c k [KLEI 75, p.19]. Assume that a s t a t i o n a r y p r o b a b i l i t y d i s t r i b u t i o n f o r the number of customers i n the system p(n) , e x i s t s , with oo I p(n) = 1 . (D.1) n=0 Assume that a l l customers are e v e n t u a l l y served, 0 < p < 1 . In a d d i t i o n , the system must be work-conserving [KLEI 76, p.113], i n p a r t i c u l a r , no customer can have a s e r v i c e time s h o r t e r or longer than that which i s ob t a i n e d when i t s s e r v i c e time d i s t r i b u t i o n i s sampled. Beyond t h i s p r o v i s o , there are no other r e s t r i c t i o n s to be p l a c e d on e i t h e r the s e r v i c e time or i n t e r a r r i v a l time d i s t r i b u t i o n s . The only a d d i t i o n a l r e s t r i c t i o n on s e r v i c e d i s c i p l i n e i s that i n d i v i d u a l customers have an equal chance of being served by any of the s i d e n t i c a l s e r v e r s . F i r s t we show that the u t i l i z a t i o n f a c t o r p , may be i n t e r p r e t e d as: p = Pr(any s p e c i f i c s e r v e r i s busy at any random t i m e ) . Or, that p = 1 - z , where z = Pr(any s p e c i f i c s e r v e r i s f r e e at any random t i m e ) . During an a r b i t r a r i l y long time i n t e r v a l r , the expected number of a r r i v a l s to one server i s (X./S)T . A l s o d u r i n g T , the busy time of the server i s 85 T(1-Z) , and so the average number of customers served d u r i n g T w i l l be T(1-Z) / E(y) . Here, E(y) i s the expected s e r v i c e time of the customers being served: E(y) = E[ E(y | customer type i n s e r v i c e ) ] = E ^ ) ^ . In i n t e r v a l T , the number of a r r i v a l s roughly matches the number served: U / s ) T = T(1-Z) / E o i y i . As T -> °° , there i s e q u a l i t y , and: U / s ) E. o y = 1 - z i i i E± x i y i / s = 1 ~ z • D e f i n i n g the u t i l i z a t i o n f a c t o r as *  = z±  k±y±/ s ( D - 2 ) then z = 1 - p . (D.3) Now we develop an' a l t e r n a t e e x p r e s s i o n f o r z u s i n g (D.1) and c o n d i t i o n a l p r o b a b i l i t y . z = Pr(any s p e c i f i c s e r v e r i s f r e e at any random time) = E[ Pr(any s p e c i f i c s e r v e r i s f r e e ... | number i n system)] = 1 p(0) + (1- 1/s) p ( D + (1- 2/s) p(2) + ... ... + (1- ( S - 1 ) / S ) p(s-1) + 0 + 0 + 0 + ... s-1 z = E (1 - n/s) p(n) (D.4) n=0 T h e r e f o r e , combining (D.3) and (D.4), the d e s i r e d r e s u l t i s o b t a i n e d : s-1 1 - ft = E (1 - n/s) p(n) , 0<p<1 . (D.5) n=0 T h i s equation appears in the t e x t as (4.13) in IV - D. 86 BIBLIOGRAPHY [ALLE 77] B. A l l e n , R.S. Anderssen, E. Seneta, "Computation of S t a t i o n a r y Measures f o r I n f i n i t e Markov Chains" TIMS S t u d i e s i n the Management Sci e n c e s M.F. Neuts, ed., 7 1977 13-23. [AVI 65] B. A v i - I t z h a k , W.L. Maxwell, 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 " Opns. Res., J_3 1965 306-318. [BART 81] P. B a r t f a i , J . Tomko, Poi n t Processes and Queuing Problems, C o l l o q u i a Mathematica S o c i e t a t i s Janos B o l y a i , 24 (1978) North-Holland, New York, 1981. [BHAR 60] A.T. Bharucha-Reid, Elements of the Theory of Markov Processes and T h e i r A p p l i c a t i o n s , 1st ed. McGraw H i l l , New York, 1960. [BOBI 76] P.A. B o b i l l i e r , B.C. Kahan, A.R. Probst S i m u l a t i o n with GPSS and GPSSV P r e n t i c e - H a l l , Englewood C l i f f s , N.J., 1976. [BUNC 76] J.R. Bunch, D.J. Rose, Sparse Matrix Computations Academic Press, New York, 1976. [COBH 54] A. Cobham, " P r i o r i t y Assignment i n Waiting L i n e Problems", Opns. Res., 2 1954 70-76. [COOP 69] R.B. Cooper, G. Murray "Queues Served i n C y c l i c Order" B e l l S y s t . Tech. J.,- 48(3) 1969 675-689. [COOP 70] R.B. Cooper, "Queues Served i n C y c l i c Order: Waiting Times" B e l l S y s t . Tech. J . , 49(3) 1970 399-413. [COOP 72] R.B. Cooper, I n t r o d u c t i o n to Queueing Theory, Macmillan, New York, 1972. [DAVI 66] R.H. Davis, "Waiting-Time D i s t r i b u t i o n of a M u l t i - s e r v e r P r i o r i t y Queueing System" Opns. Res., J_4 1966 1 33-136. [DUFF 77] I.S. Duff, "A Survey of Sparse Matrix Research" Proc. IEEE, 65(4) 1977 500-535. [EISE 71] M. E i s e n b e r g , "Two Queues with Changeover Times" Opns. Res., 19(2) 1971 386-401. 87 [EISE 72] [EVAN 74] [FISH 78] [GOLD 81] [GROS 74] [GUST 72] [HALF 72] [KALA 71] [KLEI 75] [KLEI 76] [KOTI 73] [KOTI 77] [KUEH 79] M. E i s e n b e r g , "Queues with P e r i o d i c S e r v i c e and Changeover Time" Opns. Res., 20(2) 1972 440-451. D.J. Evans, ed., Software f o r Numerical Mathematics, Academic Press, New York, 1974. G. S. Fishman, P r i n c i p l e s of D i s c r e t e Event S i m u l a t i o n , Wiley, New York, 1978. H. M. Goldberg, "Computation of State P r o b a b i l i t i e s f o r M|M|s P r i o r i t y Queues with Customer C l a s s e s having D i f f e r e n t S e r v i c e Rates" INFOR, J_9(1) 1981 48-58. D. Gross, CM. H a r r i s Fundamentals of Queueing Theory Wiley, New York, 1974. F.G. Gustavson, "Some Basic Techniques f o r S o l v i n g Sparse Systems of L i n e a r Equations" i n [ROSE 71], 41-52. S. H a l f i n , "A P r i o r i t y Queueing Model f o r a Mixture of Two Types of Customers" SIAM J . Appl. Math., 23(3) 1972 369-379. J.E. Kalan, "Aspects of L a r g e - S c a l e , In-Core L i n e a r Programming" Proc. Annual ACM Conference, Chicago, 1971 304-313. L. K l e i n r o c k , Queueing Systems, Volume I: Theory, Wiley, New York, 1975. L. K l e i n r o c k , Queueing Systems, Volume 11: Computer A p p l i c a t i o n s , Wiley, New York, 1976. T.C.T. K o t i a h , N.B. S l a t e r , "On Two-Server Poisson Queues with Two Types of Customers" Opns. Res., 2J_ 1973 597-603. T.C.T. K o t i a h , "On a L i n e a r Programming Technique f o r the Steady-State Behaviour of some Queueing Systems", Opns. Res., 25(2) 1977 289-303. P.J. Kuehn, "Multiqueue Systems with Nonexhaustive C y c l i c S e r v i c e " B e l l S yst. Tech. J . , 58(3) 1979 671-698. [LUEN 73] D.G. Luenberger, I n t r o d u c t i o n to L i n e a r and Nonlinear Programming Addison-Wesley, Reading,Mass., 1973. 88 [MURT 81 ] [NAIR 76] [REID 74] [ROSE 71] [ROSS 72] [SCHL 81] [SENE 67] [SENE 68] [SHER 78a] [SHER 78b] [SING 81] [SLAT 73] B.A. Murtagh, Advanced L i n e a r Programming; < Computation and P r a c t i c e McGraw-Hill, New York, 1981. S.S. N a i r , " A l t e r n a t i n g P r i o r i t y Queues with Non-Zero Switch Rule" Computers and Opns. Res., 3 1976 337-346. J.K. Reid, " D i r e c t Methods f o r Sparse M a t r i c e s " i n [EVAN 74], 29-47. D. J . Rose, R.A. Willoughby Sparse M a t r i c e s and T h e i r A p p l i c a t i o n s Plenum Press, New York, 1971. S.M. Ross, I n t r o d u c t i o n to P r o b a b i l i t y Models Academic Press, New York, 1972. W. S c h l e e - K S s s l e r , "A S i n g l e Server Queue with Two Types of Customers and A l t e r n a t i n g S e r v i c e in Pi e c e s of ̂ and " in [BART 81], 343-357. E. Seneta, " F i n i t e Approximations to I n f i n i t e Non-Negative M a t r i c e s " Proc. Camb. P h i l . S o c , 63 1967 983-992. E. Seneta, " F i n i t e Approximations to I n f i n i t e Non-Negative M a t r i c e s I I : Refinements and A p p l i c a t i o n s " Proc. Camb. P h i l . S o c , 64 1968 465-470. A.H. Sherman, "Algorithms f o r Sparse Gaussian E l i m i n a t i o n with P a r t i a l P i v o t i n g " ACM Trans, on Mathematical Software 4(4) 1978 330-338. A.H. Sherman, "Algorithm 533: NSPIV, A F o r t r a n Subroutine f o r Sparse Gaussian E l i m i n a t i o n with P a r t i a l P i v o t i n g " ACM T r a n s a c t i o n s on Mathematical Software 4(4) 1978 391-398. R. Singh, S. Subba Rao, S.C. Gupta " A n a l y s i s of a Mobile Radio Communication System with Two Types of Customers and P r i o r i t y " I n t . Conf. on Comm., Denver, 1981 IEEE (ICC-1981), v.3 57.4.1-57.4.5 . N.B. S l a t e r , T.C.T. K o t i a h "The Steady-State of a M u l t i s e r v e r Mixed Queue" Adv. i n Appl. Prob., 5 1973 614-631. 89 [STEW 78] W.J. Stewart, "A Comparison of Numerical Techniques i n Markov Modeling" Communications of the ACM, 2±(2) 1978 144-152. [SYKE 70] J.S. Sykes, " S i m p l i f i e d A n a l y s i s of an A l t e r n a t i n g - P r i o r i t y Queue with Setup Times" Opns. Res., _[8 1970 1182-1 1 92. [TAYL 80] I.D.S. T a y l o r , J.G.C. Templeton "Waiting Time i n a M u l t i - s e r v e r C u t o f f - P r i o r i t y Queue, and i t s A p p l i c a t i o n to an Urban Ambulance S e r v i c e " Opns. Res., 28(5) 1980 1168-1188. [WALL 66] V.L. Wallace, R.S. Rosenberg "Markovian Models and Numerical A n a l y s i s of Computer System Behaviour" AFIPS Sp r i n g J o i n t Comp. Conf, 28 1966 141-148 [WILL 80] T.M. W i l l i a m s , "Nonpreemptive M u l t i - s e r v e r P r i o r i t y Queues" J . O p e r a t i o n a l Res. Soc. 31(12) 1980 1105-1107. [WOLF 80] D. Wolf, "Approximation of the I n v a r i a n t Prob- a b i l i t y Measure of an I n f i n i t e S t o c h a s t i c M a t r i x " Adv. i n Appl. Prob., 12 1980 710-726. 90 G l o s s a r y of N o t a t i o n A c o e f f i c i e n t matrix of the N x balance equations A, f i r s t (N-j-x N x) submatrix of A b, b r i g h t - h a n d s i d e constant ( v e c t o r ) of the n o r m a l i z a t i o n c o n s t r a i n t ( s ) B c o e f f i c i e n t matrix of the ^ n o r m a l i z a t i o n c o n t r a i n t s c counter i n the s t a t e space model f o r c y c l i c p r i o r i t y c% g e n e r a l confidence i n t e r v a l f o r s i m u l a t i o n r e s u l t s C ( k , , k 2 , . . , k v ) c y c l i c p r i o r i t y system with v queues d number of s t a t e v a r i a b l e s i n a Markov c h a i n E['] e x p e c t a t i o n operator FCFS f i r s t - c o m e , f i r s t - s e r v e d s e r v i c e d i s c i p l i n e i , j , k i n t e g e r i n d i c e s I i d e n t i t y matrix ^ 1 (m x m) i d e n t i t y matrix J average number of simplex i t e r a t i o n s r e q u i r e d per o b j e c t i v e f u n c t i o n ^ maximum number served d u r i n g phase i of c y c l i c p r i o r i t y K t o t a l number of o b j e c t i v e f u n c t i o n s f o r an LP problem L a f i x e d maximum queue l e n g t h LP l i n e a r program LU a f a c t o r i z a t i o n of a matrix as a product of lower and upper t r i a n g u l a r m a t r i c e s m number of rows i n the LP M|G | 1 s i n g l e - s e r v e r queue with a Poisson a r r i v a l process and a general s e r v i c e time d i s t r i b u t i o n M|M|s s- s e r v e r queue with a Poisson a r r i v a l process and e x p o n e n t i a l l y d i s t r i b u t e d s e r v i c e times 91 n (1) number of columns i n the LP, (2) index f o r number of customers i n a queueing system n 0 f i x e d v alue of n, number i n the system n c t r u n c a t i o n parameter f o r the set of balance equations N (1) t o t a l number of s t a t e s i n a f i n i t e s t a t e space, (2) t o t a l number of measured events i n a s i m u l a t i o n number of balance equations (rows) i n A N number of s t a t e p r o b a b i l i t y v a r i a b l e s a s s o c i a t e d with columns of A N number of n o r m a l i z a t i o n c o n s t r a i n t s (rows) i n B N NPP non-preemptive p r i o r i t y p(n) steady s t a t e p r o b a b i l i t y f o r n customers i n a queueing system p £ ( n ) , p u ( n ) lower and upper bounds on p(n) f o r each n P d i s c r e t e - t i m e Markov cha i n t r a n s i t i o n p r o b a b i l i t y matrix P,, P 2 submatrices of P , .P (m x m) t r u n c a t i o n of P P(k) g e n e r a l d i s c r e t e p r o b a b i l i t y d i s t r i b u t i o n P^(k), P u ( k ) lower and upper bounds on P(k) f o r each k P(s, s 2 ) same as P f s , s 2 ; 0 0) P(s, s 2 ; q, q 2 ) p r o b a b i l i t y of s t a t e (s, s 2 ; q 2 ) q ± s t a t e v a r i a b l e f o r number of type i customers i n the queue Q continuous-time Markov c h a i n t r a n s i t i o n r a t e matrix R, , R 2 r a t i o s of l i m i t i n g v a l u e s of average w a i t i n g times s t o t a l a v a i l a b l e number of s e r v e r s s c c u t o f f l e v e l f o r c u t o f f p r i o r i t y queues s± s t a t e v a r i a b l e f o r number of type i customers i n s e r v i c e t time ( s u p e r s c r i p t ) matrix transpose 92 v (1) number of queues i n c y c l i c p r i o r i t y , (2) number of customer c l a s s e s i n a gene r a l system w± random v a r i a b l e f o r w a i t i n g time of type i customers Wi mean w a i t i n g time f o r type i customers x± an indexed member of the set {Pts, s 2 ; q i q2)} x f i n i t e column v e c t o r of v a r i a b l e s i n the LP, ( s t a t e p r o b a b i l i t i e s p l u s the s l a c k v a r i a b l e ) x^ i n f i n i t e column v e c t o r of the p r o b a b i l i t i e s x i x^ a b a s i c s o l u t i o n f o r a l i n e a r program y (1) s l a c k v a r i a b l e , (2) random v a r i a b l e f o r s e r v i c e time y_̂  random v a r i a b l e f o r s e r v i c e time of a type i customer y average s e r v i c e time of a type i customer z p r o b a b i l i t y that any given server i s f r e e at any random time Z, Ẑ. one of the o b j e c t i v e f u n c t i o n s f o r the LP Z(W i) t r u n c a t i o n of VJ± used as an o b j e c t i v e f u n c t i o n 0 n u l l v e c t o r a± f r a c t i o n of a r r i v i n g customers which are of type i O i * value of i n a 2 - c l a s s system at which the p, vs. O i curve has slope=1 fi± f r a c t i o n of system resources a l l o c a t e d to customers of type i 6(') d i s c r e t e d e l t a f u n c t i o n A convergence parameter i n a matrix i t e r a t i o n technique Poisson a r r i v a l r a t e of type i customers X t o t a l Poisson a r r i v a l r a t e of customers n± e x p o n e n t i a l s e r v i c e r a t e of type i customers TT_ i n f i n i t e row ve c t o r of Markov chain p r o b a b i l i t i e s 93 m-component s o l u t i o n of a t r u n c a t e d Markov c h a i n model permutation matrix u t i l i z a t i o n parameter f o r type i customers t o t a l u t i l i z a t i o n ( t r a f f i c i n t e n s i t y ) parameter a c r i t i c a l value of p f o r NPP m u l t i s e r v e r systems a r b i t r a r y time i n t e r v a l

Cite

Citation Scheme:

    

Usage Statistics

Country Views Downloads
Japan 7 0
Germany 1 1
China 1 3
United States 1 0
City Views Downloads
Tokyo 7 0
Unknown 1 1
Beijing 1 0
Ashburn 1 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}

Share

Share to:

Comment

Related Items