A QUEUEING ANALYSIS OF A MULTICHANNEL, INTEGRATED VOICE AND COMMUNICATIONS SYSTEM by DENNIS RAYMOND HALLER B.E., University of Saskatchewan, 1980 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE Department We a c c e p t to THE of E l e c t r i c a l this thesis the required © Engineering as conforming standard UNIVERSITY OF B R I T I S H June STUDIES COLUMBIA 1982 D e n n i s Raymond Haller, 1982 DATA In presenting this thesis in partial fulfilment of the requirements f o r an advanced degree at the U n i v e r s i t y of British Columbia, I it freely available for permission agree for purposes may or her that the Library shall reference and study. I extensive be granted by representatives. p u b l i c a t i o n of t h i s t h e s i s allowed without my Department of written Electrical The U n i v e r s i t y of B r i t i s h 2075 Wesbrook Place Vancouver, Canada V6T 1W5 Date: 28 June 1982 make further agree copying of t h i s t h e s i s f o r the Head of my It for is financial permission. Engineering Columbia scholarly Department or understood gain that that by his copying or shall not be i i Abstract A multichannel multiserver queue, representing shorter r a d i o communications with two distinct v o i c e and d a t a m e s s a g e s . average system length, i s given i s modeled as a customer Data, classes the c l a s s non-preemptive with the priority over voice. The chain balance using of model w i t h an i n f i n i t e state and queueing each messages property algorithm i n the system. is used and numerical excellent 0.1 to solved numerically of Kotiah. results. model results are the This d a t a messages b e i n g less the upper bounds, high t o be o f p r a c t i c a l waiting times show them t o be state than cost. system and t o four-channel both s i m u l a t i o n is produces less than t o the p r o p o r t i o n of For other traffic mixtures, f o r waiting times, a r e often too However, t h e l o w e r bounds of the a r e 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 reasonably values. intensity f o r the original The LP method typically 90%. especially use. in detail; traffic corresponds the particular presented. r e s u l t s when t h e d a t a . The times o f t h e Markov improves analyze i s treated Upper distribution Exploitation help steady f o r t h e mean w a i t i n g irreducibility the numerical of the queueing steady obtained and the p r o b a b i l i t y of case mean (LP) t e c h n i q u e Markov s e t of by c o n s i d e r a b l y r e d u c i n g t h e c o m p u t a t i o n a l Simulation validate The i n f i n i t e i s t r u n c a t e d , then bounds a r e t h e r e b y of chain's space. programming customer c l a s s , number about state equations the l i n e a r lower i s analyzed as a continuous-time good approximations to the true . . . 111 Table of X Contents Abstract List i i of Figures v Acknowledgement vi I. INTRODUCTION 1 II. SYSTEM ANALYSIS 3 A. THE APPROACH 3 B. MARKOV MODELING 3 NUMERICAL TECHNIQUES OF MARKOV MODELING The Markov C h a i n E q u a t i o n s F i n i t e S t a t e Space I n f i n i t e S t a t e Space 6 6 7 8 C. 1. 2. 3. III. MODEL SELECTION A. BASIC ASSUMPTIONS B. SERVICE DISCIPLINES C. IV. 11 .. 12 1. 2. 3. ALTERNATING PRIORITY MODELS 14 Previous Investigations 14 Markov C h a i n M o d e l — N o n - e x h a u s t i v e S e r v i c e ..15 Markov C h a i n M o d e l - E x h a u s t i v e S e r v i c e 16 1. 2. NON-PREEMPTIVE PRIORITY MODELS Previous Investigations Markov C h a i n M o d e l D. NUMERICAL SOLUTION TECHNIQUE 17 17 18 20 A. THE STATE SPACE 20 B. THE BALANCE EQUATIONS 21 C. THE LINEAR PROGRAMMING SOLUTION TECHNIQUE 24 D. NORMALIZATION 26 E. 1. 2. F. V. 11 CONSTRAINTS IRREDUCIBILITY OF THE MARKOV CHAIN The S i g n i f i c a n c e o f I r r e d u c i b i 1 i t y Improvements t o t h e LP A l g o r i t h m 28 29 30 IMPLEMENTATION OF THE MODIFIED L P ALGORITHM 31 RESULTS 35 A. SYSTEM PARAMETERS B. THE STEADY STATE PROBABILITY DISTRIBUTION p ( n ) ..38 C. MEAN WAITING TIMES 1. Definition 2. The L i m i t i n g C a s e s : 3. W a i t i n g Time R e s u l t s D. 43 43 44 46 a,-M WAITING TIME SIMULATIONS E. 1. 2. F. G. 1. 2. VI. 35 51 COMMENTS ON THE WAITING TIME RESULTS Empirical Observations Waiting Times i n a Non-preemptive System 53 53 Priority 54 CONVERGENCE OF UPPER AND LOWER BOUNDS 56 COMPUTATIONAL COSTS LP S o l u t i o n Cost A Comparison w i t h S i m u l a t i o n C o s t s 63 63 65 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 ALTERNATING PRIORITY SERVICE DISCIPLINES, PRIORITY APPENDIX B - THE STATE SPACE TRANSITION DIAGRAM AND 74 77 APPENDIX C SETTING UP THE BALANCE EQUATION COEFFICIENT MATRIX "A": AN EXAMPLE 79 APPENDIX D - A DERIVATION FOR THE GIVEN IN [KOTI 77] NORMALIZATION CONDITION 84 BIBLIOGRAPHY 86 Glossary 89 of N o t a t i o n V List of F i g u r e s P a r a m e t e r s &, and o, 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, o= 0.95, 5. Waiting 1. R e l a t i o n s h i p Between 2. Times a s a F u n c t i o n of y * i : P - 37 0.7, 0.44) 42 n = . 30 n = . 25 47 c 6. Waiting Times as a F u n c t i o n of e, : p = 0.5, c 7. Waiting Times as a F u n c t i o n of B, : p - 0.3, 48 n = 20 . ....49 c 8. C o n v e r g e n c e o f Bounds f o r P r o b a b i l i t i e s p ( 0 ) , p ( 4 ) 58 9. C o n v e r g e n c e o f W a i t i n g Time o,= 0.80, (*,,= 0.14) Results: 10. C o n v e r g e n c e of W a i t i n g Time o,= 0.80, 0.14) Results: 11. C o n v e r g e n c e o f W a i t i n g Time o,= 0.95, (p,= 0.44) Results: 12. S c h e m a t i c of a 2 - C l a s s p - 0.7, 59 p = 0.5, 60 p = 0.5, M u l t i s e r v e r Queueing System 61 ..74 13. S t a t e Space for n Z s 78 14. S t a t e Space for n < s 78 15. M a t r i x "A" F o r n = 6 , s=4 c Servers 80 vi Acknowledgement I would Leung, for during like his t o thank my guidance the course and s u p e r v i s o r , Dr. constant of the r e s e a r c h C.S.K. availability and w r i t i n g o f t h i s thesis. Financial Postgraduate Columbia assistance Scholarship, teaching acknowledged. NSERC r e s e a r c h in the grant of an NSERC and a U n i v e r s i t y o f B r i t i s h assistantship This form work A-1052. is also was p a r t i a l l y gratefully supported by 1 I. In this study multichannel INTRODUCTION we radio analyze communications t o b o t h d a t a messages and queued an may interactive messages busy, the sent the message-carrying If a l l controller service available Our obtain In t h i s on objective type is and to the average the steady queueing radio theory the The solution equations. We the c a s e of s = 4 assumed t o e x i s t , only channel such a mobile or through to radio a of central channels incoming are r e q u e s t s and imposes an resource — the state will efficiently analysis specifically it will service discipline assign In a of will continuous-time channels. but times probability system. system for model An not obtain channel use, while the and 2 1 in fact require chain signaling included of the c e n t r a l on the state numerical r e s u l t s for auxiliary be for based types Markov to each distribution c h a n n e l s become s e r v e r s , queueing of t h e communications queueing v o i c e messages become c u s t o m e r s respectively. The be each by v o i c e of a f i n i t e model t h i s i n the numerical example o f the c o n t r o l l e r t h e use can channels. t h e number o f messages and way, type for transmission temporarily denies discipline some measure o f message Requests an i s provided i n which either auxiliary each One via co-ordinated, Service network office terminal. a l l o w s a queue t o f o r m . orderly radio with a c e n t r a l computer are controller. data system. v o i c e m e s s a g e s , and be a modern m o b i l e communicate s centrally when a l l r a d i o c h a n n e l s a r e b u s y . system can a i n our controller channel i s model. must not but a l s o must m a i n t a i n 2 message q u e u e i n g possible times service physical system cutoff priority, priority. Only at acceptable disciplines, are: the first-come two o f most Among priority, these the many r e l e v a n t t o the given first-served non-preemptive the l a s t levels. will (no and be priority), alternating given serious further consideration. The this following chapter study, and o u t l i n e s modeling. Chapter alternating priority assesses both tractability. III the IV describes methods u s e t o s o l v e t h e c h o s e n a selected Finally, example i n Chapter summarized previous to their VI t h e main and p o s s i b l e work priority analytical in detail Markov with the models, from i s outlined. and and n u m e r i c a l the numerical results for and d i s c u s s e d i n C h a p t e r results f u t u r e work of done m o d e l , and n u m e r i c a l are presented approach of techniques non-preemptive respect Chapter numerical reviews and with describes the a n a l y t i c a l this study V. are 3 II. A. THE APPROACH Analytical multiserver Two SYSTEM ANALYSIS solutions queueing and alternatives numerical of Markov c h a i n m o d e l s . and execution significant The only the A effort, while s i m u l a t i o n language. simulation program the time of a n u m e r i c a l computer p r o g r a m , b o t h numerical independent checks on their one check on the relied a primarily simulation B. on the numerical solution effort to provide a d d i t i o n a l requires behaviour is into l e n g t h of acceptable usually time a a confidence greater program. i t being In t h i s numerical require a As than with any s i m u l a t i o n programs r e q u i r e validity, other. may actual usually system solution and versus solution give f o r the measured q u a n t i t i e s execution as of are solution simulation to analysis the However, t h e run disciplines. particularly numerical specialized must service systems analytical straightforward translation intervals u n a v a i l a b l e f o r most t r a d e o f f between time. modeling for solutions, simulation i s in i n i t i a l program generally systems with p r i o r i t y o f t h e more p o p u l a r simulations are acceptable investigation approach but verification have of to we also the use have used results. MARKOV MODELING Many demand use effectively present probabilistic of certain using a brief a systems, system Markov in which resources, c h a i n model. incoming can be In t h e summary of Markov c h a i n m o d e l i n g customers analyzed f o l l o w i n g we techniques, and 4 for simplicity, independent be found essential discrete-time is, consider parameters t r e a t m e n t s can The we or A state system, d has t a k e on infinite states with i n the on The chain an range, state a known system The space. For the (perhaps instants can at or i f at least example, the be are in an state future. variables may, chosen of depending one on number variables a each number of form variable infinite in That states, infinite state be of its finite d the a has number queueing Markov c h a i n system determine can of system model w i l l underlying whether be t i m e between be so m o d e l e d used. In successive i s the l a b e l l e d by the Markov a state An transitions integers example queueing occur or continuous- random v a r i a b l e M|M|s t r a n s i t i o n s may the a discrete-time dependent) parameter. which s t a t e time Markov c h a i n a d i s t r i b u t e d continuous state whether present set state be will 72]. space. representation exponentially which The state also the finite queue l e n g t h s will t i m e Markov c h a i n , an a there c h a r a c t e r i s t i c s of model its each v a r i a b l e s p a c e and, then infinite continuous-time is , and detailed Markov P r o p e r t y . a discrete of time- [ROSS chain that There w i l l values. unrestricted defined d state and i t s entire history affects either allowable with More 75], Markov property system. say - dimensional an the [KLEI i s the i s f o r m e d of the variables, discrete a a unique c o n f i g u r a t i o n to c h a r a c t e r i z e the of systems processes). [BHAR 6 0 ] , continuous-time Markov c h a i n state in s u m m a r i z e s how being stochastic (stationary feature a Markov c h a i n completely only in a with of a system. discrete- {0,1,2,... }, and 5 the t i m e between distributed chain successive discrete m o d e l s may the as (either i s called a Markov which This define as a digital communications system. between continuous state transitions or d i s c r e t e t i m e ) , The p r o c e s s can s t i l l successfully be m o d e l e d Markov technique to queueing may be processes system f o r used as process t o number is not chain. many discrete-time Markov can chain, transition easily chain times. on The gives imbedded chain each probabilities correspond each s t a t e . between state therefore to of the for imbedded probabilities transformation times. however, The of time computed they again of the system being makes use o f s t a t e s of t h e p a r t i c u l a r imbedded c h a i n the on of number i n proportion so t h a t be imbedded chains chain. need t o be a d j u s t e d stationary This Markov probability distribution system, but i n s t e a d a d i s t r i b u t i o n in M|G|1 n o r even semi-Markov Markov discrete-time not the g e n e r a l - t i m e spent the i n t h e s y s t e m n ( t ) , t ^ O ) , but i t may modeled a s a d i s c r e t e - t i m e these be but a d i s c r e t e - s e t 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 c o m p l e t i o n Solving found model example Markov, is this i n s t a n t s c a n be i s a l s o p o s s i b l e by i m b e d d i n g a Markov respect then an imbedded d i s c r e t e - t i m e o f i n s t a n t s formed of a l l s t a t e (with the operate a c o n t i n u o u s - t i m e Markov continuous-time the t o systems which i n h e r e n t l y time stochastic The M|M|s t i m e model set in imbedding represented Markov i f a c e r t a i n s e t of time continuous-time chains. of geometrically Discrete-time semi-Markov. chain together variable. for instance, distribution arbitrary process random be a p p l i e d in d i s c r e t e - t i m e , If state transitions i s a in relationship and t h o s e i n the 6 original C. general-time The Markov C h a i n A numerical calculate state of the state possible to waiting time of a Markov p r o b a b i l i t y that space. compute MODELING Equations solution the s t a t i o n a r y the state, state Denote by queue component spends with length the system i . The rate of steady representing i each out state the proportion set of balance of moments written for (or flow) the state. p r o b a b i l i t i e s , each of time the system equations is = 0 Q fJ the matrix of t r a n s i t i o n t h e 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 n o r m a l i z e d by 1 a discrete-time i s defined will defined i n state ir ± ± = time i . P (2.2) a transition probability is instant rates, 1 . Markov c h a i n such t h a t a t the next currently is then (2.1) with and P into (column by c o l u m n ) a s : £ Q In of of i n t e r e s t . is t r a n s i t i o n rate transition t h e row v e c t o r rr i s in distributions, an e q u a t i o n the t o t a l the t o t a l in state written model aims t o d i s t r i b u t i o n s , and o t h e r q u a n t i t i e s balancing tr chain From t h e s e p r o b a b i l i t i e s i t i s t h e n a c o n t i n u o u s - t i m e Markov c h a i n , each ii.]. [GROS 74, p.311 NUMERICAL TECHNIQUES OF MARKOV 1. In system the probability move t o s t a t e The s t e a d y state the j , given matrix process that i t is probability distribution through ir P = n (2.3) 7 and the normalization probabilities can transitions that (2.3) be may although the (2.2). take be steady the interpreted the rewritten Here process in a as into form steady the state state vector ir i s not j r ( I - P ) = 0 proportion i structurally state . Note similar defined of that to (2.1) i n the same way: If the s t a t e space infinite number of 2. Finite Assume that both State (2.1) one so of s y s t e m s may the then iterative the s t a t e space are (2.4) only (N-1) represents an (N so N in equations Solutions may be these must be (2.1) exactly states) systems of (2.2) solved is finite (N x N) normalization be or or to linear equations used t o (2.4). obtain obtained of are replace The linear steady state e i t h e r by direct or methods. Direct s o l u t i o n s are more e f f i c i e n t because (2.1) equations. (2.4) the probabilities. are that and then Space Actually independent, and linear first equations. any is infinite (2.4) then u s u a l l y b a s e d on when the specialized coefficient data Gaussian elimination matrices s t r u c t u r e s may be are sparse, used to avoid a computations which great v a r i e t y of which is iterative as for a p p l i e d to the the o r ones methods power-iteration iteration, iterate involve zeros [STEW 78] [WALL 6 6 ] , solution solution vector [DUFF 7 7 ] . jr In of the the There are simplest method of (2.1), the i s obtained from a of power- (k+1)'th the k'th 8 iterate as follows: JL where A rate A i s a scalar of c o n v e r g e n c e [STEW 7 8 ] , = JL k + 1 (AQ k constant. and, its The although best + I) (2.5) parameter A controls guidelines exist value must usually the for choosing be determined experimentally. Iterative methods full, methods a r e whenever the o r when t h e y a r e force a zero Gaussian coefficient sparse but elimination matrices have a Q or than direct (I - P) structure that a l g o r i t h m to f i l l - i n are would many of the system of elements. 3. Infinite When t h e equations be which have (2.4) State state (2.1) cannot Space space or is (2.4) developed technique considering There to in then to from the because constraint n m of . T This matrix columns, balance the seem t o be [KOTI of chain balance Q infinite linear and so i n most o n l y two 77] system T n = 0 is numerical best T equations structure are of or results. explained by , . (2.6) i s truncated f i r s t n (2.1) (2.1): equation c o e f f i c i e n t s with cases techniques s o l v e t r u n c a t e d v e r s i o n s of of K o t i a h Q by-row the though approximate, the t r a n s p o s e Markov infinite, i s also solved exactly. to provide useful, The The i n g e n e r a l more e f f i c i e n t chosen lost. these to so t h a t In now appear row- rows and m no coefficients general equations. n £ m With the 9 > n the problem standard i s now v i e w e d methods on q u a n t i t i e s be a p p l i e d of i n t e r e s t . t o system in later ( s e e IV - C ) . (m x n) second discrete-time modeled as additional a and h e n c e corner" system be truncation will discussed Possible m was may with Markov northwest by Seneta by Wolf technique are of both Seneta probability , .P , and t h e n m o d i f y the also, and much e n h a n c e d Seneta's detail any s y s t e m developed using one of "(m x m) The common a p p r o a c h the t r a n s i t i o n columns, first also the a discrete-time The bounds i n more that chain as extended is truncations Recall Markov algorithms i n [ALLE 7 7 ] . i s to truncate rows and (2.4). apply. method [SENE 6 7 ] , and was r e c e n t l y [WOLF 8 0 ] . to and presumably be d i s c u s s e d represented (2.4) and lower technique could applies continuous-time effort, program T h i s method o f K o t i a h technique linear linear t o compute upper This (2.4). (2.7) t h e p r e s e n t study and w i l l The Wolf an may be u s e d used chain, as 0 matrix P to and m the truncated matrix (m) in some s p e c i a l way. n The s o l u t i o n c o n v e r g e s e l e m e n t w i s e t o JT : lim IT, = ir _ In [WOLF 80] matrix , P Cm; N Seneta. ^ several this i=1,2,... possible modifications one o f w h i c h particular upper l o w e r bounds c a n be f o u n d / ir ± ( i , j =1,2,... given version, result n.. c a n be includes convergence and ,m system (2.8) i Cm) x are given, For t o the truncated ,m). the a [SENE 6 7 , 6 8 ] , These of t h e t r u n c a t e d technique special in f o r the r a t i o s computations kind which of of both of elements require the 10 inverse of the modifications about the s e t s of to matrix ( )P m ( (m) listed convergence modifications properties it is errors for Ifm)"! ~ i I i = 1 ,2, . . . ,m . The and advantage Wolf hand, to give method g i v e s o n l y w i t h unknown m a g n i t u d e s IT is F o not the r less possible to and of both estimate the elements: judged to be m. On state Consequently, "close of Seneta l o w e r bounds on approximate error. known For individual upper other is of the t e c h n i q u e . no m a t t e r what t h e t r u n c a t i o n Wolf's result p of t h e method o f K o t i a h o v e r t h a t is i t s ability probabilities ~ (m) ) • i n [WOLF 8 0 ] , even absolute ff 1 enough" the state other probabilities before to the v_ , the must be (m) convergence determined m . behaviour by of obtaining the problem solutions under . n s study for ever-increasing 11 III. A. BASIC ASSUMPTIONS We c o n s i d e r q u e u e i n g priority MODEL SELECTION allocation models of t h e s servers Customer rate are traffic X M|M|s f o r two c u s t o m e r c l a s s e s . t h e c u s t o m e r s a r e s e r v e d on a The form first-come identical arrival f o r customer Within and i n d e p e n d e n t i (i=1,2). basis. of each Poisson some classes, first-served i s modeled as a type with other. process The a r r i v a l s with of type 1 i and type arrival The 2 c u s t o m e r s a r e assumed process service i s then times distributed with utilization factor total utilization In also of customer (? )' p = p, the mathematical class + which t h i s lengths, analysis but these probability is rate class p ± = k 2 are exponentially ± type i . / ( s Kj) The and t h e 2 i n the system. of course a r e assumed t o be l a r g e being total p applies will of a customer The X. = X, + X. • customer model we assume t h e r e t h e number o f c u s t o m e r s a l l o w e d to for 1 ± f o r each is Poisson, with each mean t o be i n d e p e n d e n t . blocked is no limit Physical have enough systems finite so i s negligible that . on queue the 12 B. SERVICE D I S C I P L I N E S There are considered for chiefly a communications minimize service waiting times, while simplest systems where t y p e s may the service-time ratio Consequently the communication would greater usually server. average differ which will maximizing use of the d i s t r i b u t i o n s the exact be for of 20. 80], would than suffer customer messages, a for- voice interactive system's admitted of busy denied 81], [SING those with shortest delay-tomessages. aspect makes resources of d a t a service to time. service customers servers High i f there are i s less wait however, i s n o t w o r k - c o n s e r v i n g [KLEI 76, p . 1 1 3 ] , f o r each queue. f o r low p r i o r i t y customers is a one free service t h a n some in a priority allowed FCFS discipline service available t o customers of with possible voice/data Data queues, is system. lost. the number 7 3 ] , i s no multiserver Customers c of service t i m e s f o r t h e two short, greater [TAYL always [KOTI . it s the one 73], a by a f a c t o r However, low p r i o r i t y if data, of " u n f a i r n e s s " quick-response, of are for service quite much priority, share customers an e l e m e n t inherently Cutoff and ( F C F S ) , [SLAT discipline have typically are be customer. first-served i t does which might voice i s to s e l e c t not However, level goal t i m e a r e known b e f o r e h a n d , and the We mixed only doubt only disciplines assume t h a t First-come type, The resources. t i m e o f e a c h new which service multichannel, system. message available four cutoff priority-typed Cutoff priority meaning t o be d e n i e d that service 13 even w h i l e some s e r v e r s resources, priority and seems of into maximum of controller from is are priority k, according If either alternating priority section III - C. there priority priority, t o be o n l y i s unbounded, t h e service k a and 2 particular class Because single server waiting time yet to been proven so w i l l be has a q u i t e for s > behind. Service that [KLEI 76, allocation further a l l discussed in known low to the priority priority average p.126]. such r e s u l t but from customer the o v e r a l l systems as rule. t i m e , t h e n i t i s known No to radio i s then always i s given of p r i o r i t y Later, there the a s i n g l e queue, w i t h a l l h i g h systems 1 . for simple operating and A its flexibility, (NPP), more d e s c r i p t i v e l y for multiserver this of option mean s e r v i c e i s minimized assume t h a t advantage NPP When i s generalized viable If high p r i o r i t y w i t h the s h o r t e s t queue. t h e scheme similarly of t h e l i n e . In t h e c a s e served customers head type. are 2 together at the f r o n t , the are customers k customers grouped queued customers 1, t h e n t h e or remains consideration, Consider high from queue served priority. under head-of-the-line the are classes, system Non-preemptive system a t t e n d s each queue. k, customer cyclic unless incoming to their s w i t c h e s and a maximum o f called of alternately t o be e x h a u s t i v e f o r t h a t is i s a waste sacrifice assumes t h a t customers more t h a n two what This "emergency" n a t u r e . the c o n t r o l l e r queue 2. said an s e p a r a t e queues two q u e u e s , idle. an u n w a r r a n t e d c u s t o m e r s have Alternating split stand for customer has i t seems r e a s o n a b l e would i n I I I - D we maintain investigate its non- 14 preemptive p r i o r i t y detailed comparison alternating C. in greater d e t a i l . of priority queueing with and a particular especially alternating priority a single s e r v e r have been analyzed system. priority models model et. al. (two queue. any and with some d e g r e e of Itzhak, only success. [AVI 65] customer In t h i s [SYKE 7 0 ] , for single then up to k to queues, denoted here attempted, notably [KUEH 79] this server m o d e l , and extremely The from the by from 2 v and but extensions served without relaxed ± , has =1 cyclic from , and only [SCHL 81] k each this g e n e r a l i z a t i o n of queue 2 C(k,,k ,...,k ) v > 2 queues more g e n e r a l customers are [NAIR 76] priority [COOP 6 9 , 7 0 ] , [ E I S E 7 2 ] , The work, however, in still service queue so on 1 , for v r e c e n t l y been which v =2 f o r a l l queues. i s a p p l i c a b l e only the t o the t o m u l t i p l e s e r v e r s would , All single seem to difficult. analytical unknown particular by Avi- s e r v i c e to studies Further of alternating switches later 71]. case. k, i n which previous but the that exhaustive server customers 2 with systems server i n w h i c h up the [EISE work was analyzed delays, for multiqueue regime first classes) model was the The who treatment, intermediate restriction be discipline a Previous Investigations Cyclic of NPP give ALTERNATING PRIORITY MODELS 1. and the In A p p e n d i x A we time. intractability identities For of the example, of m u l t i s e r v e r m o d e l s customers i n the in service single arises at s e r v e r case any i t is 15 known t h a t server is however, service attending the only i s that servers of t h e j o b i n s e r v i c e a t any t i m e 2. about completely now for the the p a r t i c u l a r moment. system w i t h such a dimensions, since the t o t a l number s t h e number o f t y p e t h e number i, an i d e n t i f i e r c, a counter four state queue n = n any s y s t e m five C(k,,k ) 2 A Markov space with s t a t e c a n be five described variables: 1 customers ^ s , then 0 in service served service served from t h e cycle. the possible ranges f o r the variables are: , (n -s) c 1f2f3f*«* f 0 ^ a l l combinations the to identities, delays. a state i n the current 0,1,2,... proportional has f o r the customers already q,: that priority o f t h e queue c u r r e n t l y b e i n g 0,1,2,... ,s say The i n the system Si,: • the group of i n queue 1 current n f i x e d , say in Service no s w i t c h i n g system by t h e f o l l o w i n g q,, servers, customers be from t h e queue alternating n, 1 f s > 1 the i n s e r v i c e a r e unknown. Markovian independent can With Markov C h a i n M o d e l — N o n - e x h a u s t i v e model other knowledge at that customers multiserver For moment. a t l e a s t one must Consider Not that definite i s attending the other chain at i s from t h e queue l -1f 2 • of these number (k,+k ) 2 . of s t a t e s c a n e x i s t , b u t a t l e a s t we states Observe t h a t with n = n (k +k ) 1 2 0 will be i s t h e number 16 of i possible . configurations I f i t were n o t f o r t h i s that there given would n = n models. model , be as in exhaustive "smaller" for ( I I I - D) non-preemptive models other priority than the very i n t h e Markov a n d so a n u m e r i c a l Markov C h a i n M o d e l — E x h a u s t i v e states and chain solution may costly. service or both queues. v a r i a t i o n may a chain given t o both representation dimensions. q and there be a p p l i e d a r e not system p o p u l a t i o n service four Service The r e s u l t i n g n u m e r i c a l model i n the sense t h a t with exhaustive Markov large, be s e e n c t h e same number o f s t a t e s , 2-class priority variables i t will t h e number o f s t a t e s c a n be e x c e e d i n g l y The l f the alternating 2 3. factor, approximately k., = 1 , k = 1, become q u i t e one 0 For simplest, be o f t h e two s t a t e n = n 0 . 0 C( , ) , 00 either turns out t o many 00 require a state state variables The c o r r e s p o n d i n g i , and f o r n = n queues, will as to > s , the p o s s i b l e possible F o r example, a complete space of are n, only s 1 f ranges of t h e other v a r i a b l e s a r e : s ^: 0,1,2,... ,s q, : 0,1,2,... i : , (n -s) 0 1,2. Again not a l l combinations that the factor (ki+k ) 2 replaced by t h e f a c t o r model. Thus the same a s i f the 2 of these for states the (since number o f s t a t e s k,=t, k =1 2 exist, C(k,,k ) i = 1 ,2) we see model h a s been 2 for for fixed but this n = n 0 in the previous a l t e r n a t i n g C(°°,°°) i s about priority 17 system C(k ,k ) 1 system . 2 would computational The solution therefore in of the general exhaustive require service much less effort. D. • NON-PREEMPTIVE PRIORITY MODELS 1. Previous Analytical Investigations studies of queueing models (s > 1) those of cyclic priority average waiting [COBH 5 4 ] . the rather the time same service have p r o g r e s s e d systems. of this analysis assumption time that priority somewhat First f o r members Unfortunately restrictive non-preemptive was o n l y distribution. times Those which a l l o w t i m e s must d i s a l l o w [BHAT 7 6 ] , [WILL 8 0 ] . queueing all f o r one c u s t o m e r (first-come, [HALF 7 2 ] , class possible under The have subsequent of unequal service service class altogether discipline i n favor of [GOLD 8 1 ] , first-served). the priority uniformity o r abandon t h e n o n - p r e e m p t i v e preemptive p r i o r i t i e s was Most required 66], than a l l customer c l a s s e s improvements t o t h i s work a l s o [DAVI further obtained each M|M|s o r no p r i o r i t i e s absence of at analytical 0 results f o r the general service time unknown distribution particular times identities of again customer can types be with different attributed in service to the at When a l l c u s t o m e r s have t h e same s e r v i c e their identities groups d i s a p p e a r service of customer c l a s s e s distributions time. distribution, case a s members o f d i f f e r e n t a f t e r t h e y have been a d m i t t e d any time priority to service. When f o r e a c h c l a s s a r e d i f f e r e n t , however, t h e n t h e of the customers a r e maintained even a f t e r t h e y have 18 entered service, service will and the have some e f f e c t w h i c h have n o t y e t been It cyclic upon in number o f c u s t o m e r s o f e a c h t y p e i n seems that priority attempts a t any one t i m e . restricted t h e s y s t e m t o one have times restricted time d i s t r i b u t i o n , be n o t e d that with a l l server. t o have been 2. A Markov less priority three Chain NPP The and number of s t a t e s of it what systems i Non-preemptive priority to a single multiple servers. systems with of service I t should different service [COBH 5 4 ] . However, priority, the effort Markov a multiple identical, be , for or. C C C(k , 1 f been n = n the 0 0 than server seems 0 0 state ). k ) 2 . , not we model alternating space r e q u i r e s see t h a t only with the the state Consequently the > s , is essentially half simplest This the NPP Compared dropped. 0 M|M|s does n, s , , q, model have 2-class chain for a given would C(1,1) but have Model computational priority c allowed customer types, time d i s t r i b u t i o n s independent dimensions: variables of the customers m o d e l s have have been s o l v e d solution model. alternating fallen treated. numerical requires schemes have a l l customer c l a s s e s server service those of both priority complementary problem i n ' c y c l i c model of solution the h e t e r o g e n e i t y but have a l l o w e d single times analytical for different times f o r customer c l a s s e s the at Cyclic service models waiting and n o n - p r e e m p t i v e p r i o r i t y t h e same p r o b l e m , namely service the served. different yet on alternating priority advantage of s i m p l i c i t y is 19 one r e a s o n why the NPP model was selected for closer analysis. 20 IV. A. THE NUMERICAL SOLUTION TECHNIQUE STATE SPACE As mentioned i n the model requires priority dimensions. For components (s, s ; customers of types of central controller, the determined Appendix A). being only customers a t the q 2 of assumes (or and the q,, q occurs, state number are 2 does not Its (s, s ; q, 2 storage), 2's the system is (see 2 think 2 . n < s of type The 1 be is q ) the d i m e n s i o n s When The need t o with n = s,+s +q +q queue l e n g t h s , the customer to back. 2 of behaviour (pooled at four for service. classes type 2 (i = = n . , 1 total As this q, and (s= number 2 = s 1 ,2) , q,= 0, q = 2 state space 0 then: ± is are 2 by then: 0 < s < s and s,+s choice s 1 f independent labelled 2 waiting a r e a l s o unbounded. ± One be customer queue and three variable. given two i n the q,) 0 < s < n and s,+s When n > s the of non-preemptive which s e l e c t s a w a i t i n g departure unbounded n and servers) 1 and with front number of c u s t o m e r s model types state one s service, a by i s convenient where device the space 2 in a separate totally there 1 and whenever by state , 2 c u s t o m e r s of represented It q, q ) 2 service a chapter, convenience a state w i l l number for previous of (n,s,,q,) three . (i=1,2), , independent In what q,,q 2 Qi Q2 + dimensions f o l l o w s we > 0 = n - s . for this choose rather t o use the 21 more c o n v e n i e n t B. THE state steady state continuous-time flow) rate out of follow the for state. the mechanical given total not be approach to P(s! s ; 2 i s i n the states single chain m o d e l s by This flow rate a trivial the with the into the a of transition rate always easy than given matter. in transition i s not greater construction obtained equating prescription dimensionality are to one because state from i t s An easier but more the balance equations below. Let for • equations into a particular state n e i g h b o u r s may system 2 balance Markov s y s t e m s of obtaining is q i q2) (s, s ; BALANCE EQUATIONS The (or vector state be the (s, s ; 2 stationary q, q ) 2 in a three-dimensional indexing column v e c t o r q i q2) variable of i . state (i=1,2,3,... probabilities x^ . p r o b a b i l i t y that These probabilities space are ) to the ordered form the Adapting by a infinite equation (2.1) then: x — with x — and 0 CO currently Q Q. ±± ± Note t h a t Q T CO = 0 (4.1) T — b o t h column v e c t o r s . Given in state i = t r a n s i t i o n rate = t r a n s i t i o n rate system is by construction, out of s t a t e i ( n e g a t i v e ) from s t a t e i t o s t a t e j a l l rows of Q sum e q u a t i o n c o e f f i c i e n t s appear a l o n g All i s now (usually the then: balance that that — necessary row-by-row) and i s to generate then from t h e the the to zero. c o l u m n s of Q j ± structure The Q . coefficients of the columns 22 of Q , deduce The stated the general service form of t h e b a l a n c e e q u a t i o n s . d i s c i p l i n e f o r non-preemptive as f o l l o w s (assume n > s ) : select which case s e l e c t a type 2 customer. allowable state system. Combining arrivals, a state (see be 1 customer, This due qi=0 unless service to rule departures can be in governs from these with the t r a n s i t i o n s caused t r a n s i t i o n diagram , the by s y s t e m constructed Appendix B ) . Once clearly Q.. of a type transitions space may At t h e next d e p a r t u r e from t h e system the for service priority the the system's will rules of transition rates. current customers have p o p u l a t i o n + X. On I IT p < S 1 j= * K ! 1 j= j= .j= +s2* (s, + 1 (s, s s (s, (s, S -1 ( s , -1 (s, s S (s, t r a n s i t i o n rates transitions B. indicated are a s matter Recall n = s +s +q +q 'j= ( s , j = (s, + 1 j= ( s , Appendix a queueing written 2 (n ± 1 ) . I X-2 state, +S 1 H 1 2 I r These for expressed i t i s not a d i f f i c u l t conditional number service 1 to that have been generate the i i s the index i= ( s , s ; q i q ) 2 • 2 2 The o b j e c t • 9 2 m 9 2 + 1mf • f 2 0 0 q ) n < s n > s q + D n < s n > s ) q1 i + 0 0 q, 2 ) 2 q -D q ) s -1 • 0 0 ) s - 1 9• q1-1 q ) • 0 q -D s 9 n < s n > s, n > s 9 9 2 2 2 state j n > 0 n < s n > s n > s, s > with Then: 2 ) 2 system + 1t m 0 0 0 ) 2 •• qi-1 r 2 2 2 2 2 2 complete by t h e s t a t e list space qi* (4.2) of a l l allowable t r a n s i t i o n diagram i n 23 Generalizing now the s t r u c t u r e o b t a i n the steady state of the columns of balance 2 2 2 we can 0 < n < s-1 + 2 , equations. (x,n +s,(., s «2) P(S, s ) X, P ( s , - 1 s ) + X P ( s , s -1 ) + (S , + 1 ) * , P(s , + 1 s ) + (S +1) n P ( s , s +1) 2 Q 2 2 2 2 (4.3) 2 (X ,+k + s, i + s . ) P ( s , s ) n = s = X, P ( s , - 1 s ) + X P(s, s -1) + s,m P ( s , s ; 1 0) + ( s , +1 ) »», P ( s , + 1 s - 1 ; 0 1) u 2 2 > 2 2 2 2 2 2 + u ( s +1) 2 2 P(s,-1 2 s +1; + S K 1 0) 2 2 Pts, s ; 2 (X. ,+X +s , u , + s u ) P ( s , s ; q, q ) X, P ( s , s ; q,-1 q ) + X P ( s , s ; q, + s , (•, P ( s , s ; q , +1 q ) + 6 ( q , ) ( s , + l ) 1*1 P ( s , + 1 S - 1 ; 0 q + D + ( S + 1) t. P ( s , - 1 s + 1 ; q, + 1 q ) + 6(q,) s „ P(s, s ; 0 q + D 2 2 2 2 2 2 2 2 2 2 2 2 as the standard matrix form, n , then 2 . the balance x Q = 2 With are written , 2 increasing this (4.6) 0 represent the balance i = ( s , s ; q, q ) with equations of (4.1): s u c c e s s i v e rows o f states i s negative, 2 QT s conventions: 2 the transpose The (4.5) 2 the f o l l o w i n g 2 In 2 2 P ( s , s ; q , q ) = 0 , when any i n d e x P(s, s ) = P(s, s ; 0 0), 6(q,) = 0 q,= 0 \0 otherwise . i q "D 2 2 2 H e r e we have u s e d (4.4) 2 2 2 1) n > s+1 2 2 0 2 q, , ordered and o r d e r i n g of s t a t e s , first finally the equations with with n > s for increasing increasing p a r t of matrix T Q possesses blocks of generation q 2 a few coefficients, of the balance replacing convenient. only q, Refer , or different a fact which equations. s, replacing t o Appendix (s+1 x s+1) simplifies Other s 2 recurring the automatic orderings with would C(1) f o r f u r t h e r be index equally comments a n d an 24 example. A finite including (4.4) equations until parameter, (4.5) . with of system of of a l l those have been balance equations t h e form states (4.5) with f o r which represented on The r i g h t - h a n d s i d e s o f t h e s e n= 0 up t o n= n +1 . homogeneous l i n e a r have a r e c t a n g u l a r c o e f f i c i e n t rows. The dimensions the n = n the , a cutoff side of contain viewed n -truncated c by ( 4 . 3 ) and left-hand equations matrix of obtained those.of Consequently, equations, is states as a system model would A, w i t h more c o l u m n s this matrix are than derived in Appendix C ( 2 ) . C. THE LINEAR PROGRAMMING As m e n t i o n e d the is the techniques the l i n e a r infinite SOLUTION TECHNIQUE in the discussion forsolving programming linear o f Markov m o d e l i n g , an i n f i n i t e solution system of of balance Q T x s e t of balance [KOTI 77]. equations of equations From (4.6), i s written: = 0 — oo one (4.6) — with n o r m a l i z a t i o n : I i=1 1 X-L = . (4.7) T The finite first Nj_ rows and smaller produced for matrix A i s o b t a i n e d by s e l e c t i n g N j columns. the d i f f e r e n c e (NJ-NJ- ) , t h e b e t t e r ( s e e Appendix a given N J f C(2)). i s determined Markov chain model, balance equations. In g e n e r a l and from Nj i Nj , will by the the and the be t h e r e s u l t s The minimum v a l u e o f both Q structure ^ J N _ N I^ of the by t h e o r d e r i n g o f t h e c o r r e s p o n d i n g 25 Define x as t h e f i n i t e probabilities means t h a t column v e c t o r ( x ; i=1,2,... the n o r m a l i z a t i o n This (4.7) c a n no However, a weaker b u t b r o a d l y steady /N^}. i of the steady truncation longer be state of x^ applied. applicable condition, derived s t a t e a r g u m e n t s and ( 4 . 7 ) , c a n be u s e d instead from (see IV - D): B with The B b x = b (4.8) a row v e c t o r o f c o n s t a n t n o n - n e g a t i v e a scalar p o s i t i v e constant. truncated p r o b l e m may now be c a s t coefficients, as a l i n e a r program ( L P ) : M i n i m i z e and m a x i m i z e e a c h {Z, ; k=1,2,... K] subject to the c o n s t r a i n t s : A x = 6 B x = b x > 0 . The objective functions combinations interest. these of marginal which case each and linear which a r e of desired using Z^ then Little's minimum be s o l v e d i s to l e t the 2K x of four Law each times. be components o f a ,K), k=1,2,. . . ,K i s a linear (see V - B ) . ± times t o o b t a i n bounds (k=1,2,... = P(k) , k P(k) probabilities upper i any probability distribution, probabilities the x b o t h t h e maximum application x^ times are i n terms of t h e To o b t a i n Z solved probabilities t i m e t h e LP (4.9) must a l t o g e t h e r Another in may be c h o s e n a s i f mean w a i t i n g be e x p r e s s e d (see V - C ) . k state F o r example, may waiting the (Z } (4.9) combination The LP t h e maximum and P ( k ) . These n u m e r i c a l {P CO}, u for and the of (4.9) the must t h e n be minimum values values steady of form t h e s e t of t h e s e t o f l o w e r bounds true state state (P^(k)}, probability 26 distribution P Note that P (k) (k) of the system. < P(k) neither < the general neither now constraints program k=1,2,... ,K . u components P £ ^ ) > distribution n o (4.10) the components r themselves, since in sum t o u n i t y . NORMALIZATION We That i s , P (k) , form a p r o b a b i l i t y u D. a P(k) CONSTRAINTS consider which w i l l (4.9) w i l l the task ensure that of choosing any s o l u t i o n be c o n s i s t e n t w i t h appropriate of the the n o r m a l i z a t i o n linear (4.7): oo I i=1 Equivalently, x. = 1 . (4.7) 1 f o r (4.7) we write co E p(n) = 1 n=0 where p(n) system is (n>0). normalization of the total These (4.11) probability conditions, constraints, of n customers collectively are represented i n the called as a g e n e r a l i z a t i o n (4.8): B with B b These x = b (4.12) the c o e f f i c i e n t matrix, of dimension a c o n s t a n t column v e c t o r ( ^ x 1 ) . N constraints N equalities are assumed involving a t most o n l y that truncation to (^ be the f i r s t xN j ) , non-homogeneous Nj components o f x . — 00 Recall balance the equations can no l o n g e r In i t s place, means that of the o r i g i n a l be e x a c t l y r e p r e s e n t e d Kotiah [KOTI the 77] infinite system normalization a s a c o n s t r a i n t i n an presents without of (4.7) LP. proof the 27 following: s-1 E n=0 (1 - n / s ) p ( n ) In A p p e n d i x D we d e r i v e stationary p(n) probability exists, system with i s assumed E distribution t o reach queueing systems. (4.13); the reverse multiserver solve a steady (4.13), (4.13) number state. Kotiah for a large need n o t n e c e s s a r i l y be t r u e . Markov priority chain queue. model but w h i c h sum t o a v a l u e for words, the suggests that (unspecified) that (4.11) class implies Consider the I t i s possible to p(n) much g r e a t e r a i n the system In o t h e r However, we know o n l y non-preemptive the truncated for (4.11). (4.13) and (4.11) a r e e q u i v a l e n t of . (4.13) u n d e r t h e a s s u m p t i o n t h a t p(n) = 1 r 1 - p = that which satisfy one. Clearly s u c h a s o l u t i o n v i o l a t e s (4.11) b e c a u s e p h y s i c a l l y a l l v a l u e s o f p(n) must included are not here, (n > n + l ) . that (4.11) none of (4.11), and (4.13) the four equivalently, Kotiah's normalization whether model are examples they a r e (0 ^ n < n +1) not or considered equivalent. in.Kotiah's We original t o s i m i l a r problems. of o b t a i n i n g an a d d i t i o n a l c o n s t r a i n t must LP s o l u t i o n s w h i c h be included: J E x i =1 Modifying rise the p o s s i b i l i t y N or chain of f o r the queueing system 77] seem t o g i v e To p r e c l u d e regardless Markov Thus c [KOTI violate non-negative i n the truncated equations observe paper be ± < n +1 T p(n) n=0 original conditions 1 < (4.14) 1 . (4.15) LP s o l u t i o n t e c h n i q u e (4.13) and (4.15) to instead use both of j u s t 28 (4.13) a l o n e , then are inherently not so should allow i t s extension "well-behaved" to models as those which considered in [KOTI 7 7 ] . To f i t t h e new variable y constraint , called a (4.14) i n t o t h e f o r m "slack variable", is (4.12) a introduced new such that: N J E i=1 This variable probability is vector E. be x The finally 1 y £ 0 (4.16) to the will of c o e f f i c i e n t by end (N^+1) matrices A components. and B modified linear programming problem (4.17) 0 i s t h e ( N x Nj+1) c o e f f i c i e n t balance equations, matrix of the N I B i s t h e ( % x Nj+1) c o e f f i c i e n t m a t r i x normalization constraints. of the N N x analysis truncation solution method special kind objective may f u n c t i o n o f x, A selected must written: the present Markov truncated one. x > In the have M a x i m i z e and m i n i m i z e Zy. , a l i n e a r x = |^0j subject to where, of OF THE MARKOV CHAIN complete be = , w h i c h now increased IRREDUCIBILITY + y appended The column d i m e n s i o n similarly x ^ of s e a r c h Z k . N and Nj d e p e n d (see Appendix C ( 2 ) ) . i s the simplex function chain NJJ = 2, b u t algorithm [LUEN i s made t o d e t e r m i n e However, we will queueing models the simplex The on standard 73], i n which t h e optimum show that algorithm the LP a of t h e for many need not be 29 applied of t o the e n t i r e i t . This solution time. 1. The The problem results a some Markov c h a i n s . if and in a i f every finite mathematically, an s t a t e can be of transition written: = |P P,i 0 small savings i s said reached steps irreducible discrete-time to a i s a well-known A Markov c h a i n number only part i n computer Irreducibi1ity irreducibility of but substantial S i g n i f i c a n c e of n o t i o n of only in (4.17), characteristic t o be from e v e r y [BHAR 60, Markov c h a i n probability irreducible other state p.14]. i s one matrix More i n which P the cannot be • P Because of the 0 P 2 way any continuous-time represented as a d i s c r e t e - t i m e c h a i n definition holds of q u e u e i n g systems are present system NPP structure of the Consider (4.17). state j state i with i s no the Since any , i t follows zero, r e p l a c e d by indeed balance now is P II - B ) , Q . irreducible exception, equations N (see Markov c h a i n can balance as Markov can equation that the stationary , then reached so s e e n by the c o n s t r a i n t s i n the be 0 be The C(3)). may x.= models chains. easily (Appendix previous Many Markov state i if the be f r o m any other probability a l s o must there LP be of zero i probability of the Continuing this system reasoning irreducibility, we conclude i f an null that being find x.. = 0 and then state j : using , j = 1,2,... ,H irreducible stationary solution, in not the 1 Markov c h a i n one of . x^= 0 . property of Therefore we i s t o have a i t s s t a t e s may non- have a 30 zero steady indirectly state used probability. in [KOTI 77], i m p r o v e m e n t s t o K o t i a h ' s LP 2. Improvements t o Suppose we problem with apply m the LP the solution a certain (n-m) remaining together m and The the if the any then one zero. and so Nj must no of the remaining solutions has are {x } variables to excluded called a l l of choosing (n-N^. ) t h u s been the (m-N-j. ) , 1 < (x^ Z to when zero. The variables, > 0) f ] j * exist basis to is the one show that much < N-j- to set. The of further components of x m J to /n-Nj \m-Nj (4.13) first basis The number of also the Nj. v a r i a b l e s . f r o m fn\ zero, constraint i f any that , must first The less guarantees , i s set i those 73]. (4.17) i < N-j- and basic n for property normalization the (4.18) a t most [LUEN to , 1 < candidates. reduced basic Irreducibility x^ LP m): in e f f e c t "searches" (4.17) can from (n > i s set i There are • x.^ arbitrary s o l u t i o n of irreducibility variables contain by of feasible solutions solution are the function (jj^J our (4.18) feasible would v i o l a t e t h e basic then objective t o an variables as set. also maximum other This variables completed the general algorithm algorithm invoke the basic a l l the be the can number of that simplex of u subset basis which are which o p t i m i z e s we = i s defined form t h e solutions Now x -component kernel was method. n nonzero v a r i a b l e s they solutions. basic x^ the which Algorithm simplex constraints observation, forms solution U A basic This b set set out possible is of basic 31 From n This (4.17) we - Nj> is which = an take what recognizing the the program [MURT 81, p.24 general to determine already known. simplex of are £B] ' "^ algorithm works w i t h The matrix of set. search this The for be REE to columns first ^gj As an a this means t h a t " ^ sense that necessary the (m x m) of basic the s o l u t i o n program i n any .(N they the is -N scheme o f requires the to the not known those current during the updated. [MURT specify The matrix. from be are "free" i n the Bartels-Golub user of basis L U - f a c t o r i z a t i o n must the basis solutions. obtained to only in +1) formed to v a r i a b l e s solution used steps are a l l basic square matrix correspond optimum, t h e use part method" variables the by centerpiece is applied the L U - f a c t o r i z a t i o n of which e a c h new method to gained simplex Rj. v a r i a b l e s to the a (4.17) algorithm two only i s the p u r p o s e we last applied N As LP The computer identities the solutions savings "revised However, t h i s In p r a c t i c e the irreducibility. problems. the for computational standard a priori basis written the of a p r o h i b i t i v e l y expensive ALGORITHM ff.], (4.19) algorithm. MODIFIED LP the that: number affordable. Markov c h a i n ' s set; , so been made so-called method columns of of i n the been the the basis For have now = Nj+2 simplex is LP optimum basis the s p e c i a l s o l u t i o n p r o g r a m was advantage m (NJ+1-NJ.) ( N J - N J ) /2 by THE , reduction would a n a l y s i s has full solve = searched IMPLEMENTATION OF A of fNj+l-Nj^ be consequence, F. n = Nj+1 extraordinary must numerical find two 81]. free 32 variables the first (Nj+1) a which will complete basic feasible solution. (the s l a c k v a r i a b l e significance which the first We have c h o s e n y ) , and will be basis set, i e . (Nj-4) . explained the yield variables This choice has i n the next chapter a equally (see V - E ) . Besides important sparsity can be the p r o p e r t y practical of the as is in compacted manipulations sparsity sparse the (though . In because can be fact The extreme this t h e number of very total matrix distinct number efficiently method w i l l preserve and s t r u c t u r e s [GUST 72] can be the some d e g r e e Consequently, of stored LU-factorization super-sparsity). a LU-factorization standard advantage of "symbolic" sructure In the We of standard used throughout (N-j-x N j ) have used u s i n g an step s t r u c t u r e of submatrix an of A is initial the steps we of find t h e LP , call Then take of sparsity with this factorization i n [GUST again (4.17). it to Sherman's changed matrix. based step a d a p t a t i o n of algorithm given factorization i n the basis numerical basis matrix algorithm, modified (a s i m p l i f i e d factored purely performed, peculiarities initial [SHER 7 8 a , b ] ) t o d e t e r m i n e the the the elimination sparsity. of information finally Gaussian of factorization NSPIV p r o g r a m the data (4.17) i s t h e compared w i t h t h e 71]. simplex not LP perhaps computations. The on small [KALA of the the matrix Such a m a t r i x form matrix of super-sparse very nonzero e n t r i e s . irreducibility, aspect coefficient classified coefficients of A, 72]. some In are useful particular , (which forms by 33 far the largest part dominance by columns. proceeds along t o be the numerically employ any facility rows and stable matrix. to minimize where t h e r e be the is u s u a l l y a worthwhile reduce permutation order the the that of A, columns. this row of operation M|M|2 Kotiah's next M|M|4 of the final published NPP we one in time, at 2-class LP queue. queueing for A by a in applied program 77] for numerical model. it greatly efficient and column first, likewise for order a = very f a c t o r of discussed but i s placed of results ordering can An so on; t the in locations row row of selected process, in t h i s solution algorithm. [KOTI these be column the last the n , with costs. s e c o n d , and least The results T then and which the p r o g r a m , we apply may a row memory reversed: i n t o the FCFS chapter and modifications incorporated n not permutation n II A, need Furthermore, nonzero elements column p e r m u t a t i o n the symmetric which require interchanges. found e x p e r i m e n t a l l y and nor s i n c e a good o r d e r i n g i s placed in execution All the We strategy i s a somewhat h e u r i s t i c time row then Finding search i s simply algorithm permutation f o u n d t o be second-last reduction been was The i s , on "fill-in" execution i s guaranteed A, zeros. reduce pivoting) any c r e a t i o n of to (no column , that diagonal LU-factorization s t a b l e on The were o n l y this and exhibits an elements pivoting row will matrix) [REID 7 4 ] . c o l u m n s of permutation solely diagonal f o r dynamic basis Therefore complicated LU-factorization the of e v e r y 1000 large ten. s e c t i o n have To i t to the test the s o l u t i o n of successfully duplicated the system. techniques The In to solve effectiveness the the and 34 efficiency of the m o d i f i e d algorithm will then be assessed. 35 V. A. RESULTS SYSTEM PARAMETERS We now p r e s e n t n u m e r i c a l r e s u l t s of the multiserver correspondence communications and type The mean ((,,)•' X, 2 between system times numerical are 2 of - A) t h a t (it ) " type of thereby defined a ± may 1 minutes instead be (from Appendix X. / O_L Because type service o , of incoming of system 2 order of customers resources in and t h e Recall from ,2) , of (5.1) incoming customers rates are D) a_2_ "\ t>2 ) any type have . (5.2) convenient on average 1 customers, do n o t d i r e c t l y between t o have t h e s y s t e m ' s rates have dimension unit of time; f o r example. 2 customers requirement are f o r each p a,. f i t a l l of which 2 of seconds + 1 X,, X , m i measured Rather, A l l mean a r r i v a l 2 S \V (time)" , 1 fraction (oi+o =1)• - types intensity (i= ± i s the type 1 define X / X i since: r a t e parameters the respectively. s e c . The mean a r r i v a l t o t h e system, Then 2 p The and customer specified. case To make t h e model two traffic 1 arrivals X = X,+X . type 0 1 2 we f i x t h e i n general are these directly ± which = 1 2 o = so t h a t queueing of not solution proportion this system. a s d a t a a n d v o i c e messages = 5 s e c , and X NPP q u e u e i n g s = 4 server i n t r o d u c e d i n c h a p t e r I we i d e n t i f y customers service and (III 2-class f o rthe total the times the the proportions o , , reflect two t y p e s . service 24 time the division F o r example, i n allotted equally 36 there must customer. the be We 24 new type formalize this fraction of c u s t o m e r s of t y p e ( £ i + *i= as customers (from Appendix (5.1 = - 5.4) », Then, various can show: (o the 2 ends = 0.5 a, to serve c l a s s i 1 (5.4) . (5.5) when d = 24/25 = 0.96 between curve £, begins with at which the (M/>2)' = 1 + For the c u r r e n t system to Figure 1 we see w h i c h a l a r g e change at slope . o, and for a = ty=0 with y slope when a« > a,* n /f l n^/r<2 . In i s unity, o,*, clearly i n o, . 2 (Y,/^) ' 1 = 24, 2 / is and o,* that there = 0.83 does the d i v i s i o n the s y s t e m s a n a l y s t i s more of a c o m m u n i c a t i o n s f o l l o w s then, both sensitive of work w i t h i n t h e However, In what Referring over p r o d u c e s o n l y a s m a l l change i n become user . i s a wide r e g i o n £,) while (5.6) 2 (as m e a s u r e d by the serving by o,* Only ]" 2 c ^ p ^ l at of as (5.3) system )/(a,n ) M Each i value the relationship »- /i>2 . H 2 / M 1 and spent (i = 1 ,2). ± [1 + 1 shows t h e ratios between, given (s „ ) f o r t h e above example, Figure slope X. / = (i=1,2) ± ("work") 2 D), ± we p type ( i = 1,2). P t h e work e x p e n d e d by P ± e a c h new ) « 1 ± /> Using = for defining resources P/ Identify i 0 2 arrivals n o t i o n by system i 1 system to changes parameters w i l l be a, in interested i s more f a m i l i a r system with specified. in . p 1 f o,. 37 Figure 1 - Relationship Between P a r a m e t e r s and o, 38 B. THE STEADY STATE PROBABILITY DISTRIBUTION We first objective number with d e t e r m i n e upper functions in the {Z } system: n= l o w e r bounds f o r e a c h o f corresponding to k the t r u n c a t i o n and the p ( n ) , n=0,1,2,... n for p(n) the the distribution , n + 1. Recall c infinite of set of that balance c equations, t h e LP to ( s e e IV - B ) . n= n +1 £ probabilities (4.17) includes In terms of f o r which the 2 Figure 2 shows t h e upper the case />=0.7, o, = 0.B0, connected scale by of this and for continuous representation (s = (q = 2 matter what s e t o f p a r a m e t e r s analysis system the sums given The be c the . The the t a i l present queueing system. 77] i s on a are a histogram characteristic end in p(n) points strictly most o b v i o u s on plot discrete of t h e some (p,c,) are chosen. i n [KOTI A of t h e M|M|2 upper degree Neither more no is i t detailed FCFS 2-class t h e same b e h a v i o u r . a characteristic (p (n)} u particular than that reveals Such and to t h i s seems t o n =25 though flare This n > s s-s,) n-s-q,) l o w e r bounds o b t a i n e d on curves, bound. specific and clarity i s t h e upward feature state 2 2 £,=0.14, s h o u l d be u s e d . curve up 0 < n < s ( s = n-s,) (5.7) 2 2 logarithmic 0 2 2 for n= individual P ( s , s ; q i q ) we d e f i n e : n E P ( s s ; 0 0 ) s,=0 n-s s E E P ( s , s ; q, q ) q,=0 s,=0 1 p(n) = x± states a r e computed. arises from t h e way i n which T h e r e a r e no c o n s t r a i n t s (p^(n)} imposed on 1 39 Figure 2 - The Distribution p(n) 0.14) for p = 0.7, o,= 0.80, 40 n +1 I P > ) n=0 n +1 c c , p (n ), optimum linear a Consequently, a general bounds In tendency to if (n +1) n improve. of convergence obtained n =20, w h i l e has a , = 0.95 d i f f e r e n c e between t h e p p, Figure tighter be which 0 for n increases. p(n ) where 0 poor indeed. held constant, be said We n 0 In g e n e r a l , t h e bounds later compare Figures about this n for less Figures o, a fixed cost (smaller For a f i x e d (or B,) with the possibility for n n even when Figure for 2 a n d 3. when />=0.5 is 4 c i , n ) n made 3 a n d 4. though complicated. p that and o f t h e bounds o b t a i n e d behaviour, a are f o r character with p(n) cases ($,=0.14), observe bounds a r e o b t a i n e d general more of these a,=0.80 bounds a r e o b t a i n e d compare geometrically 3 has 1 inconsistent show t h i s n More w i l l (»3 =0.44). tighter The with p ( n ) . Both i s decreased; smaller; bounds as (see V - F ) . for c generally for relative of 3 and 4 a r e f u r t h e r e x a m p l e s o f t h e u p p e r a n d l o w e r and may the r e s u l t the i s increased c 0 bounds not i s only u c a n be e x t r e m e l y c Figures and i n {p (n)} t h e upper a n d l o w e r p(n ) will concept when ( s e e IV - C ) . u near i s the 0 problem flare for p^(n ), programming ( i e . ( p ( n ) - p ^ ( n ) ) / P^(n) ) t o i n c r e a s e however, for o r e a c h minimum, 0 t h e upward some c a s e s is u unique , u n=0 b e c a u s e e a c h maximum, of Z p (n) p(n) varies "large". Many q u e u e i n g systems the exact expression An example n ^ s. that f o r p(n) i s i s t h e M|M|s f o r p(n) FCFS queue, 41 ]0 15 NUMBER IN Figure 2(T SYSTEI 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 io-i p = 0.5 a ,=0.950 =0.442 n =2Q 6 in-I >- CQo CC-" CD O c r LO-I •_ —i 10 1 15 1 20 25 30 NUMBER IN SYSTEM Figure 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 i o n An the important time before customer being waiting suited the a p e r f o r m a n c e measure of any of served. times mean w a i t i n g t i m e Law [KLEI where E ( q ) continuous = but the In terms system i n the is queue distribution present LP method the average w a i t i n g time. i c u s t o m e r s by W, i s best Denoting we ± of have from p.17]: E(q. ) / \. ( i = 1 ,2) , i s t h e a v e r a g e number of i queue. entire of c l a s s 75, W. c l a s s must w a i t interest, t o o b t a i n bounds on Little's a given The i s of queueing of the type i (5.8) customers state probabilities P(s, in s ; the qi 2 q ) 2 then: W. = \ 1 with ± qi q is expressions represented one (5.9) the and This implementation infinite Z(W ) i upper sum to limit Here to be for the n= the of we n +1 c = s, W i sum and s ; the i=1,2 and of p(n). , and (n +1). 2 . between Each p(n) a finite same define given Then, of in (4.11) remedy. the W i can was with is an when being Truncate the be state ( I V - D) objective i n (5.9) the number of representation the (5.9) q ) difference normalization apply q, 2 same p r o b l e m o c c u r r e d expression r e p l a c e d by P(s, ± important (5.7) as 2 whereas t h e e x a c t series. considered. s,+s very exactly probabilities, infinite 2 s I q s,=0 ± = n-s, + There n-s I q =0 E n=s+1 1 the function infinite 44 W. > Z(W.) The LP method the lower be i s used right-hand, bound (if n fact not relative large W be side an of so t h a t (5.9). Then, true choosing of upper a and l o w e r W W^OT-M) very section 2 n nearly 1 we d e t e r m i n e and respectively. 1 an M|M|s Then from W (oi-»0) = 0,-^-1 entering type 2 an M|M|s customers choose n c approximation to The ± be d i s c u s s e d will problem later of i n the 1 . values I t i s easy i n these Po s„ , cases type 1 for the or both t o determine system type 2 is system I (S/>) k=0 k! W^d-^O), (5.11) (sp. ) s! s \1~P2 s-1 To c a l c u l a t e on t h e t h e LP s o l u t i o n s the l i m i t i n g S(i2 Po = in [GROS 74 p . 9 8 ] : = where, to W. 0, o homogeneous vMc.-M) 2 for will o -> Cases: and W ( o - » 0 ) because 2 careful purposes c may (V - F ) . 0,-^0, as be bounds enough" The L i m i t i n g and We must as i t c o u l d a t a l l , depending ± of serve as a t h e maximum i 2. this n o t be a s t i g h t Z ( W ) becomes a v e r y c l o s e on c o n v e r g e n c e W, The minimum w i l l f o r Vl bound for practical "large (5.10) On t h e o t h e r hand n,. section In (5.10). upper magnitude . t h e maximum a n d minimum v a l u e s f o r W.^ a l t h o u g h i t w i l l enough provide to find were g r e a t e r ) . c (i=1,2) i 1 (5.12) r -'1 k imagine a ( S p ) (1-P) a r e i n the system, s! single homogeneous t y p e 2 s y s t e m . this (5.13) S type 1 No m a t t e r type customer how many 1 customer will, 45 because and i t Was p r i o r i t y , i s guaranteed waiting time go d i r e c t l y the next i s d e n o t e d by w free server. then 1f E(w,|n) = t o t h e head Therefore, E(w,) = = We d e f i n e From 1 we o b t a i n calculation Consider a single 1 system. must (s/> ) (1 - P ) s! 2 i s somewhat type 2 customer until the entering does not queue i t has a chance Let t i m e be d e n o t e d by waiting exactly 223] the for the behaviour homogeneous service using same a s t h a t queue. as long A as there an a n a l y s i s a w 2 2 > 0 the next This 2 an Cooper . M|M|s declines shows, (5.15) SUy J 0 [[(1-p,) s,.,]E[ E ( w | n ) ] E ( w | n>s) P r ( n > s ) . 2 We d e f i n e in i f f n £ s, t h e n : 2 E(w ) = = 2 W (c,-»1) 2 2 2 = E(w ). 2 is that E(w |n) = Therefore, server. situation i s one w h i c h 1 2 free [COOP 72, pp.220- a r e customers w a i t i n g . w >0) = and i n empties of type 1 customer customer ( , - P , ) w priority, by Cooper "polite" polite . o f t h e M|M|s busy p e r i o d , E(w | Since 2 difficult. an M|M|s homogeneous have t o occupy discussed of more entirely customers before this (5.14) 2 2 1 customer . s 2 of W (o ->1) This wait P r ( n > s ) , and t h e n : pp Su fact . E[ E(w,|n)] E ( w | n>s) P r ( n > s ) . W^oi-^O) = type and: V M d - ^ O ) = E(w,). [GROS 74, p.96] The line, customer's i f f n > s, n < s n £ s 1 2 the If this w, > 0 J 0 | (sx )" of 1 n < s n > s . 46 Again using P r ( n > s ) we have: W (o ->1) = 2 There limiting p : are values of It then define The four 1) 0) = W,Ui^ W,(o,-» 1) 0) = M 2 u,( (5.18) f o r these 3. Waiting Now we two r a t i o s that: R, > 1 for 0 < p < 1 R for 0 < 2 1 < of w a i t i n g p < time, W i u 2 / u , ) (a,—>-0), W (a ->1), i two p a r a l l e l } (R -1) W ^ C H - ^ O ) , and 2 1 lines. vertical W,(a,-»0). Time present Results the computed upper and l o w e r p l o t t e d as a f u n c t i o n of the parameter bounds on p,, for cases: Figure The. results from also shown. These w i l l 5 6 p = 0.7 0.5 n = 30 25 7 0.3 20 simulation at using (5.19) (1 - a, ( o r £ ) form slope following three calculations as: 2 2 l have W^^ these (5.17) (R,-1) of Making 1 ( 1-/)) lines values for fixed = These the R that = fi • > 2 R, a n d (5.2) from 1) 1) when p l o t t e d v e r s u s time, observe the four W (c,-» W,(o,-» i=1,2, waiting r e l a t i o n s h i p s between = extreme v a l u e s separation (5.16) W ( o i - » 0) W, ( - » 0) W,(o,-» Wj(o,-» c a n be shown s i /> (oi~ 0) 2 = 2 First and 0 R . i = p , we R, = W . (sp,) (1 - p ! ) s! some i n t e r e s t i n g /i,(or>1) substitutions, Po s»i, 1 s t u d i e s of t h i s be d i s c u s s e d the c extreme the techniques later points of . queueing in system a r e s e c t i o n D. Pi=0, section C(2). = The are exact A l l other 47 48 Figure 6 - Waiting T i m e s as a F u n c t i o n n = 25 c of 0, : p = 0.5, 49 Figure 7 - Waiting T i m e s as a F u n c t i o n n = 20 c of fi\ : P = 0.3 i: 50 I values t h e LP of the have been o b t a i n e d ± (4.17). 0!= and W 0.99 Numerical to illustrate known l i m i t i n g the graphs, solutions cases the o n l y u p p e r b o u n d of p= 0.7 t h e u p p e r bound of known l i m i t i n g much h i g h e r n W fi,—>1 as 2 value W 2 were computed 1 they As can failure of this £,= necessary of 0.01 approximate seen from approximation . i s so that a numerical p,= be p > 0.5 0.99 solution for pi = 1 . , for for 2 W (o —M) would be c fi,=0, significant the numerical the degree t o which of is through In far fact from solution for the with t o o b t a i n a more u s e f u l a upper bound. To generate selected W, to ensure and 0 < W < 0.2 it proportion t o be . waiting be time namely (smaller n ) c For of cost the of also that lower p and (higher n ) c bounds the be is numerical thus together of much very wide 0 < o, ^ 0.86 expression (at l e a s t it range . is generally region interest of a, (the t h a t the e r r o r W.^ (5.9) n c due could region). by of These the p(n) less cost and/or o n l y by i n t h e LP (4.17). linked These each the obtained at p was c In a d d i t i o n , given of obtained solution. n physical apparent bounds a r e directly in for i n the show what was values fit bounds f o r l a r g e to ensure tighter bounds w i l l equations of exact neglected with fixed numerical the results graphs, a messages): sufficiently t o t r u n c a t i o n of reasonably to is the parameter lower close region corresponds chosen u p p e r and reasonably This of d a t a i n F i g u r e s 5-7, that the were 2 because had the data true that increasing Greater with topics the will the better number convergence computational be discussed 51 later be i n s e c t i o n s F and a costly can be placed discussion results D. o p t i o n , and i n two will, G . may very A more e x t e n s i v e not required solution could if some faith helpful empirical observations. however, be have been even be LP deferred until after the This simulation presented. WAITING TIME SIMULATIONS Computer performed simulations f o r two of t h e M|M|4 2 - c l a s s NPP system were reasons: (1) To on verify the v a l i d i t y of t h e mean w a i t i n g t i m e s . (2) To compare the relative cost and quality of results o b t a i n e d w i t h s i m u l a t i o n s as o p p o s e d t o n u m e r i c a l s o l u t i o n s u s i n g t h e LP method. The simulation confidence c% results bands a r o u n d e a c h confidence variation range of interval the will t i m e s out contain of every simulation 100 results independent batch simulation run customers are length batch making run is (ie. the the the Figures "measured" mean waiting calculated such that true value of the from on now made, the in time. A the given c which of analysis the [FISH 7 8 ] . a the same number of quantity long 95% measured q u a n t i t y very interest enough, s u c c e s s i v e large of "successive A system. d i v i d e d i n t o a c e r t a i n number of the by statistical average have c h o s e n technique to pass through each with 5-7 bounds simulations. a v a i l a b l e we means" allowed batches the s e v e r a l methods f o r s t a t i s t i c a l is mean of obtained in data such numerically indicated is simulation From among the long are the single number of This very b a t c h e s of equal customers). i s then batch From obtained. means each By become 52 statistically using independent. the related Then, C statistic k o b t a i n e d on standard the state system. Therefore into final the results of first GPSS optimizing produced the by into It 20 is and 12 batches usually times are considered. (customer waiting confidence intervals results indicate, narrow as of must p and be simulation the c o u l d be must the c o n f i d e n c e the width the in Figures runs, be of and a each 5run be intervals like. desired, before of of t h e c o n f i d e n c e running events As the everywhere If for certain then is acceptable obtained. a r e not Markov advantage number observed to specialized when p r o g r a m large can effort, s o l v e the whatever lost a f o r t h e means better r e s u l t s are borne; aid However, a systems a n a l y s t might 0! by customers. Generally times) the simultaneously the data i t i s t o s e t up effort the in compiled with system. i n programming and i n terms of programming than empty introduced written easier, language gained be are The i s a completely was Therefore 4000 simulation levels s t a r t - u p behaviour, 76], different system means. quantity. E a c h s i m u l a t i o n run 2 queueing the measured itself [BOBI simulate a c h a i n model of confidence run closely discarded. W. of i s tested batch b i a s which might program W, 95% transient are GPSS/H. of neighbouring the any the language for results of independence p.238], a q u a n t i t y simulation batch compiler data mean to prevent simulation specialized between every results the The divided of 78, techniques, overall initial d e g r e e of [FISH to the c o r r e l a t i o n using 7 are The greater intervals as values costs will on 53 average decrease only as N~ where 1 / 2 f N i s the total number of observations. E. COMMENTS ON There THE are theoretical, several w h i c h can waiting time graphs 1. Empirical Combining bounds f o r for be that the the may be used the LP solution algorithm. values This 0, use. for W,, has £ , a region become e v e r These inexpensive initial more two basis empirical character and of the the numerically conclude fact bound t o be reasonable near too the model, the the p(n) where a c c e p t a b l e initial for by s o l u t i o n s of objective and be observation generates generally true useful work p e r f o r m e d f o r LP that true large to second e m p i r i c a l (IV - F) the is especially have o b s e r v e d in most of very is often e l i m i n a t e much of We with obtained the basic minimum functions. p > 0.5 c o m p l e t e LP , and solutions expensive. observations numerical times may upper specified and 2 7. and empirical chain been o b s e r v e d 0.1 waiting Markov W, 6, Furthermore, a to v i r t u a l l y solution the l o w e r bounds a r e This practical feasible about with we computed values. particular data times, of this 5, both Observations i n which case 2 made simulation state W, observations, in Figures waiting confidence steady WAITING TIME RESULTS seem to approximation W: ± set given Solve in the to allow be linear (IV - F ) . made system Calculate a convenient for the mean (4.17) w i t h W. and and the assume 54 that these addition, quantities are procedure, queueing is No expected. this support so why not only i n the p a r t i c u l a r the general classes. priority, their VJ of common w i t h In expressed W^^ for with t h e M|M|s solely assignment any 0, which shown less p and Figures that of a t y p e p,= but £, 1 . that . rate is lies also 5-7 depend with on has in They queue at p and cannot the case Although would B , = 0 the in queue. FCFS queue w i t h w a i t i n g time the more both u . of However, with a p r i o r i t y In an M|M|s 2 M|M|s enter answer than p , a s i s usually of a homogeneous t y p e service The of p r i o r i t y , is the average 1 queue a t 2 arrival at non-preemptive decreasing that not 1 c u s t o m e r s have in customer c l a s s e s , may heterogeneous times i n t e r m s of System with FCFS queue t h a n i n the system. average found 1 customers type systems given two effective chain results decrease? queueing waiting p and with mean number i n the mean w a i t i n g t i m e general, increasing of is Markov been vs. ± W, Because type customers, variation does This cases. decrease slight, customer has in evidence, particular B ^ i n c r e a s e s more t y p e the nature empirical i n a Non-preemptive P r i o r i t y As while bounds, and unknown t r u e v a l u e s . on i t s extension to other system 2 to theoretical relatively type to the g e n e r a l c h a r a c t e r of t h e be of a l l lower solely only W a i t i n g Times The the it apply model. 2. first as to would a l l o w first reasonably c l o s e based constrained are , u , be f o r the the same range from down to p i s constant, the 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 »ii/c2 = 24 seen 0, as increases. times Therefore, than the value at though 1 customers 2 customers w a i t i n g f o r type than they waiting behaviour i s a direct customers with reach result shortest situation, to of average however, the the p increases. customers will priority than on server. customers the than then t o spend customers. *, p > p* for types of customers will i n c r e a s e as p < p* the system i 1 getting there average waiting wait of t h e i r of the own type p, X., by in this the i s dominated priority For c o n t e x t , a good a s s u m p t i o n C ( 2 ) by s e t t i n g W R = 2 (c.-M) = W 1 of both increases. customers. ie. just , the w a i t i n g times is section type 1 (5.20) time. from , the Since f o r fixed t h o s e w i t h g r e a t e s t mean s e r v i c e unproven In service p Sn, that dominated i>). p, , expect For spend d e p e n d s more on c u s t o m e r s those as the t r a f f i c more t i m e the This to priority p= p* say they a c t u a l l y - X, = we may they service (greatest importance Consequently, non-priority increases with (5.11, leave priority times A t some p o i n t , b e g i n on a v e r a g e t h e head of t h e l i n e to non-preemptive intensity free equations head o f t h e l i n e . service t a k e s on an e v e r - i n c r e a s i n g a is T h i s c a n be have p r i o r i t y , assigning discipline for p, = 0 . type more t i m e to 0,= 1 at C(2) . spend this time , from 2 even do waiting W ^ d - M ) and V) (a,->0) by c o m p a r i n g 5.12) i n s e c t i o n lower The by t y p e p > p* 2 customers, , the system Although for p* strictly i s obtained (5.18): (d-s-0) (i=1,2). (5.21) 56 Both equations (i=1,2) g i v e t h e same = P* For the current 1 ~ solution, p* = 0.96, w h i c h model practical significance. Nevertheless illustrate how e x t e n s i v e l y t h e type long service times, dominate (5.22) (n i > e 2 ) • V Z / K i i s t o o h i g h t o be o f i t does 2 customers, the behaviour serve to with their very of t h i s queueing system. A. CONVERGENCE OF UPPER AND LOWER BOUNDS If t h e LP s o l u t i o n simulation provide given as between the confidence i s t o have an a method of s y s t e m s a n a l y s i s , comparable computed technique or " b e t t e r " result upper range i s seen and as lower o b t a i n e d from we l o o k more c l o s e l y results bounds of the LP method, w h i l e q u e s t i o n s o f c o s t next section. The linear increasing sequence sequence of lower constraints. i n form exact solution the of solution upper more b a l a n c e to the i n f i n i t e x^. function true steady data. results will A difference t h e 95% In t h i s section produced using be d i s c u s s e d " i n t h e technique bounds cost. and guarantees a a non- non-decreasing bounds a s t h e LP i s s o l v e d w i t h more and more Adding closer objective programming overall i f the over be a b l e t o i s s m a l l e r than simulation at the q u a l i t y i t must a t lower "better" advantage equations linear Consequently c a n be e x p e c t e d state we a d d t h e p r o v i s o t h a t v a l u e as n b r i n g s t h e LP (4.17) system the t h e bounds on a p a r t i c u l a r t o converge c (4.6) w i t h increases. the o b j e c t i v e steadily To t h i s f u n c t i o n s must toward argument be a b l e t o 57 be expressed using {x±; probabilities probabilities functions infinite subset interest As class a finite 0 £ i £ Nj}. (p(n); objective only Into of of the objective times for functions, is from (4.17) and (C.2) a s : m = N m = [10 + 5 ( n - 3 ) ( n -2)/2. the the computed c , x n^ and error and graph, C(1)) + (n - 3 ) ] c i s roughly c type, proportional we p r e s e n t bounds f o r W, functions by f i n i t e Figures and W different consider truncating Z(vO the an 2 f o r the first in Figure 8 the with ever that the i n t h e LP, + 2 sets to expression of this objective 9, cost functions 10, and 11. class of t h e i r times objective for (5.23) (see V - G). of system parameters t h e mean w a i t i n g the ' There, a r e p l o t t e d as a f u n c t i o n 2 truncations is . the o v e r a l l computational i n d u c e d by s u c h a t r u n c a t i o n that over W. recall have W. at to . before bounds. Recall function For from obtained n= n +1. . be expansions, must be a s s e s s e d W of (/>,<»,). had infinite r e s u l t s c a n be i n t e r p r e t e d a s u p p e r and l o w e r example, of Two e x a m p l e s o f , t h e number o f e q u a t i o n s h e l p f u l t o know t h a t three approximated the m this class + 2 Because o b j e c t i v e the interpret c second for the be d e f i n e d W, show t h e c o n v e r g e n c e o f bounds f o r of n To h e l p t h e LP s o l u t i o n To fall p ( 0 ) and p ( 4 ) a s t h e LP i s s o l v e d between of class we have p l o t t e d relation also state state p r o b a b i l i t i e s . n^ . is the second a r e those which can o n l y greater It A c of examples o f c o n v e r g e n c e b e h a v i o u r computed bounds given this Q£ n < ( n + 1 ) } . t o us a r e t h e mean w a i t i n g typical subset Also (V by recall 58 Figure 8 - Convergence o f Bounds f o r P r o b a b i l i t i e s p ( 0 ) , p(4) 59 Figure 9 - Convergence of W a i t i n g o,= 0.80, (*,= Time R e s u l t s : 0.14) p = 0.7, 60 0.5 a =0 . 8 0 0 P ,=0.142 p = ~l 5 Figure 1 10 1 15 10 - C o n v e r g e n c e o,= 1 20 ^ 1 25 1 30 s i m . o f W a i t i n g Time R e s u l t s : 0.80, (*,= 0.14) p = 0.5, 61 Figure 11 - C o n v e r g e n c e o f W a i t i n g = 0.95, 0 1 Time R e s u l t s : 0.44) p = 0.5, 62 that t h e computed minimum o f Z(W ) w i l l i for or W . On t h e o t h e r ± may n o t be an upper truncation affect the error. hand, ± ±f There a r e thus of Z(W ) will i expansion for ZfVT) . and more c o n s t r a i n t s decrease effect, toward that behaviour there the to interpret terms true value error, maxlzfw.^)} 9-11 show a s t r i k i n g to 2 shown by error there , i s no e a s i l y max{Z(W,)} maximum practical One and must o n l y c increases added the t o the w i t h more maximum bound is i t f o r Vv\ . i n the convergence The maximum o f Z(W ) 2 by t r u n c a t i o n In increases numerical the error. Soon a peak convergence p r o p e r t y of values i s an be c a r e f u l as dominant bound take p l a c e , contrast, bound indicating factor. beyond f o r W,. t o choose n a type betweeen the d e c r e a s e s . For acceptable large that w h i c h we c a n say Nevertheless, o f Z(W,) s t e a d i l y (as Consequently as the d i f f e r e n c e entirely t h e computed n • increases results), point to the f i r s t made n e g l i g i b l e difference steadily. i s an u p p e r purposes t h i s First, O n l y when ± h a s been distinguished minimum W . the i n t r i n s i c i s always c o n v e r g e n c e does n ± 2 precise truncation of which c a u s i n g max{Z(W )}, now an upper decrease the for 2 maximum o f Z(W,) c o n s i s t e n t l y that forces being f o r W, a n d W . r e a c h e d , a n d from t h e r e LP method d o m i n a t e s , of a s an upper seems t o be a f f e c t e d W, are i s the tendency o f t h e "bounds" initially for opposing S e c o n d l y , a s t h e LP i s s o l v e d of t r u n c a t i o n Figures the two t e n d t o i n c r e a s e as b e c a u s e more and more n o n z e r o is d e p e n d i n g on t h e d e g r e e o f t h e c o n v e r g e n c e o f t h e computed maximum o f Z ( W ) . maximum safe bound t h e computed maximum o f Z(W ) may for W bound a l w a y s be a l o w e r behaviour. enough s o t h a t t h e 63 two curves nearly connecting 9-11 bounds o b t a i n e d No of that G. for useful a become experience, u p p e r and observed as either or been found, of t h e LP method of analysis convergence characteristics different s e t s of p a r a m e t e r s . relationship user user will for a given lower decreases has the ensure, n numerical in Figures few section be able s e t of bounds w i l l be of 2- the After to s e l e c t system a value parameters, computed. addition, of 1. LP A very using the = m function however, we the compare (m those the which a f f e c t relative costs aspects of the computational of simulation LP cost. and LP. S o l u t i o n Cost important simplex executed general examines s e v e r a l p r a c t i c a l program, c h i e f l y solution J have COMPUTATIONAL COSTS solution J, the least which w i l l c This In Z(W,) also convergence assess at initial n of t i g h t n e s s of t h e of T h i s was In c o n s e q u e n c e , t h e have t o system t h a t the increase. concrete however. this suggest for a given value p and both will limits horizontal. Figures 7. t h e computed characteristic a l g o r i t h m i s the average b e f o r e an x n) practical iterations [LUEN 73, number of optimum b a s i c s o l u t i o n LP, experience are required p.55]. i n w h i c h a l l but In two of our LP program iterations, i s achieved. shows t h a t on to of any optimize average each more s p e c i a l i z e d the b a s i s v a r i a b l e s at For a least objective algorithm are known 64 a priori, many fewer p, parameters linear fashion n= 30 the LP, c which It computational modified A LP n c number of more LP W a roughly J = 6.5 is that through (over for constraints model statistics realized by the parameters the given an in by enormous use of p the from This ), 1 r new basic solution function. required value although and have per reduced strategy i n which is for functions. An solution optimizes found with that very LP algorithm, to to the function close summarize the above, independent To further tested objective for total be listed i s roughly for a general LP, We The can objective functions is noticeable. J = m specialized task number parameters c search" remaining of (n +l). "parallel iterations . some d e c r e a s e this minimize a set a (n^+4) o b j e c t i v e 1.5 (/>, for 0 < n < whenever a s i n g l e b a s i c objective number of approximately all for a given p(n), required employing i s achieved of and 2 against one functions W, average search in number of s o l u t i o n must m a x i m i z e and 1f set the has average (m=45), t o queueing been iteration than reduced i s the savings complete 1.0 m On ranges 6 c from t h e s e ): optimality economy that J n= i s apparent iterations each at particular objective considerably at for this required. found t h a t J = 4 Recall complete p,, have are technique. different {p, we from (m=l929). (5.23). of p,) iterations then, of to the 0.0 J has 1.5 when a p r i m a r i l y d e p e n d s on the total or been J = 6 J = is for parallel i s employed. Computational iterations cost necessary to optimize a l l the objective number of functions. 65 The only matrix a d d i t i o n a l expense and i t s LU-factorization. significant functions factor (CPU n >> c as actual compiled with precision Since m 0.0 increases the or 1.0 very performance, time by as w e l l . consider execution 2. and mean waiting numerical large with i n Figures time. Additionally, there required 24 cost limited FORTRAN be a e was : upper a n d l o w e r of and Single when double bounds precision 50%, and o f c o u r s e of incurs program : required 31 objective £ iterations functions. 20 to Total V/8 c o m p u t e r . Costs results for each c o m p a r i s o n s o f s i m u l a t i o n and generality because a v a i l a b l e to users of e i t h e r may for p = 0.5, B = 0.44, n = Simulation Rigid increases n," . in except 9-11 a r e s i m u l a t i o n s o l u t i o n are of number o f o p t i o n s initially the cost to As a p a r t i c u l a r example It c FORTRAN-H. 19 s e c o n d s on an AMDAHL-470 A Comparison Included to written Use a (n +4) execution proportional used, about s e t of solution compiler the run w i t h minimize t i m e was was together. (m=794), i n s i n g l e p r e c i s i o n . maximize LP , o r when t h e computed execution memory c o s t s an usually number o f o b j e c t i v e i s proportional was g e n e r a l l y not the t o t a l is itself optimizing close is the complete of s o l u t i o n program arithmetic were t o .be extra found t h a t charges) set-up of the b a s i s small we have s ( s e e 5.23), t h e n c o s t The near . 2 a With memory m only This optimized. functions time p l u s roughly unless are being objective i s the i n i t i a l large difference to develop the respective computer of the technique. in effort programs. 66 However, f o r c o m p l e t e n e s s we The from s i m u l a t i o n data runs statistics LP of on functions computational occur for blocks an of n equal W,, cost the following f o r e a c h of F i g u r e s 9-11 4000 b e s i d e s w a i t i n g times solution objective 20 present W . 2 equal we t o one of and of n To No other place the c o n s i d e r o n l y the precision t h e above 25 gathered each. were c o l l e c t e d . A single somewhere between were customers footing, comparison. 30 . solution two with s i m u l a t i o n s would While numerical c solutions of two slow, f o r these so cost, that which waiting the times? better bounds. solution £ The W, or is 2 0.8), other are the t h e LP answer the W of c S 0.2 wholly cases considered. (approximate) . of by We equal conclude a For execution f o r t h e mean only solution answer than factor answered: unambiguous the a sufficiently be i n w h i c h t h e LP two is better results seems t o p r o v i d e b e t t e r r e s u l t s the can (4.17) the is separated bounds question provides o,= For c o s t over 0.9, solutions (p = 0.5, 10 whether following method Figure c, values i n c o s t , t h e c o n v e r g e n c e of s i m u l a t i o n s and equal two for produces depends on t h a t the LP simulation r a n g e of p a r a m e t e r s : p & of 0.5, 67 VI. A. LIMITATIONS OF THE MODEL Simplifying any modeling system the assumptions process. under study computational are necessary d u r i n g t h e c o u r s e of They a l l o w t h e o p e r a t i o n o f t h e to methods. be made amenable Upon c o m p l e t i o n physical t o mathematical of the modeling i n the context applicability of the o r i g i n a l of the present a n a l y s i s physical such systems. In a d d i t i o n , chain equations further traditionally a numerical reduces problem. of a communications c o n s t r a i n e d by some o f t h e a s s u m p t i o n s solution the p o t e n t i a l or process s y s t e m s a n a l y s t must, however, r e - a s s e s s t h e a s s u m p t i o n s t h e model is CONCLUDING REMARKS of The system made f o r o f t h e Markov generality of the analysis. P e r h a p s t h e most o b v i o u s provides only transient behaviour periodic input condition. relevant or to and physical state, arrivals). reality independent a solution. there is continuous-time represents assumption short the the solutions for as the e q u i l i b r i u m Markov actual lengths. a communications The message an times arrival accurate system model is i n continuous-time, interarrival i s usually message s o u r c e s . packet i s that i t reality, q u e s t i o n o f how w e l l for the In time-dependent systems which o p e r a t e relatively when o f t h e model may be a s i m p o r t a n t distribution However, t h i s state other traffic with exponential of steady The c h o i c e o f t o those steady a limitation Even in t h e assumed (Poisson process. representation s e r v e s many e q u a l and assumption of exponentially 68 distributed service justified. times may I f a more g e n e r a l required, one o f t h e f a m i l y would have numerical A LP greater of E r l a n g second economical complexity itself. that and LP s o l u t i o n impossible. is model w o u l d require a large be well assumption is available To to that of which which the blocking a more c o s t l y waiting Unless solution of Otherwise, the increasing n In g e n e r a l , the renders this is comment modeling process. advance that If a Markov a chain then i t t h e use of a l t e r n a t e simulation. always violated infinite number, s a y customers. functions L' i s quite by a physical queue l e n g t h s . L, o f storage When a l l L A almost f i n i t e Markov c h a i n real positions positions are from e n t e r i n g small, t h e LP s o l u t i o n r e q u i r e s equations. number o f s t a t e s the queue. 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 the system room. in messages a r e b l o c k e d enough s o t h a t with require although number o f s t a t e v a r i a b l e s , allows f o r waiting, make balance possible complexity particularly have a f i n i t e arriving such consider techniques, system w i l l filled, times i s a r i s e s from t h e demands o f the increased system system of s e r v i c e F o r example, t h e number o f c h a n n e l s particular One so w e l l is still may be made o f t h e e n t i r e Markov c h a i n modeling be d i s t r i b u t i o n s may be u s e d . model s e t of c o n s t r a i n t s s o l u t i o n method might not solution. ( s ) may be so l a r g e an practice representation A c o n t i n u o u s - t i m e Markov c h a i n it in large a s i f i t had i n f i n i t e an exact numerical would n o t be e c o n o m i c a l . a truncation of the s e t of Because these b a l a n c e e q u a t i o n s a r e o r d e r e d (total number i n the system), i t i s apparent 69 with a truncation at t h e maximum This total favors forced a n = n , that L should number system of p o o l e d positions. The Markov c h a i n s t a t e space B. SUMMARY AND a storage, any one itself, i s not combined voice non-preemptive p r i o r i t y results are available which some results exist analytical distributions t o be i d e n t i c a l , programming technique bounds on quantities waiting times storage suited to a type. of LP s o l u t i o n because M|M|s either used interest, First model communications messages. No systems of t h i s NPP models for require a l l service to s = 1. obtain most n o t a b l y , A linear numerical the average class. method c o u l d n o t of data or r e q u i r e was t h e r e f o r e of each customer Markov c h a i n m o d e l . constraint L well f o r queueing 2-class form the f o r the data related original as and The most c l o s e l y Kotiah's of we have s e t up a Markov c h a i n q u e u e i n g type. time type. i n w h i c h any c u s t o m e r queues f o r each customer multichannel, analytical r e g a r d l e s s of customer as CONCLUSIONS thesis system, w i t h interpreted method o f t r u n c a t i o n , and t h e s t r u c t u r e o f t h e separate In t h i s of i n queue, t o queue may be a s s i g n e d system with be c the complexity of a l l , be applied in i t s and s t r u c t u r e o f t h e the a d d i t i o n a l normalization (4.15) was a d d e d : n c + 1 E p(n) n=0 This serves to which the f i r s t generalize constraint < 1 . (4.15) t h e LP method t o Markov c h a i n s f o r (4.13), 70 s-1 I n=0 is alone insufficient improvement the i s the Markov B o t h of (1 - n/s) computational property changes are related for thesis to equation condition use [KOTI summation Appendix D is of 77] the counter-example t o the A second heterogeneous to the p), constant W (o ->0), i the ± time on results are the mean NPP relations predicted for concern s y s t e m s of in using the times is waiting only through given pleasing was in result. (4.13) i s e q u i v a l e n t to of We with serves this thesis behaviour refer is in a especially the parameter (at the limiting values particular p = p* change further in the illustrates type. LP method ensuring negligibly it derived proof time this state a result The steady as between (i=1,2). i s given queue system. times A proof Although the intuitively of directly c o u l d be waiting queueing solutions not systems. analytical waiting 1 affected and when is exploited. valid equations, second realized which are a A here. technique. (4.13) mean of q u e u e i n g primary bounds of behaviour behaviour The of W (a -»1), 1 waiting and LP p r o p o s i t i o n that 2 - c l a s s NPP variation studied 2 - c l a s s M|M|s important clarification one i t t o be that solutions. a p p l i c a b l e t o LP of q u e u e i n g a more g e n e r a l present the shows (4.13) irreducibility the balance In a d d i t i o n , t h e (4.11). of of K o t i a h ' s (4.13) w h i c h in , which are several results f o r a wide c l a s s indicated direct than contains our savings widely Markov c h a i n m o d e l s o t h e r This 1 - p = to ensure acceptable chain's these p(n) by to t h a t the truncation determine computed error. 71 Herein an lies one objective exactly function i s the error were be always Increasing reduces the exactly upper of t h e LP for number of the equations to functions span that of true equations number o f which time Law can like upper (m) be p(n), and lower state probabilities. be expressed becomes the A t h e mean requires size more included. an and second waiting infinite more balance LP means t h e e x p r e s s i o n s f o r t h e s e objective terms. l e a s t the d i f f e r e n c e as the increasing size the of size Adding LP objective o t h e r as the s u c h as representation the probabilities, variable are those, in time can towards each component more n o n z e r o at studies. truncation For q u a n t i t i e s functions exact state bounds d e c r e a s e s benefits each an the be truncated p.240], f o r t h e mean w a i t i n g functions which a Little's 75, as a d d i t i o n a l e q u a t i o n s a r e of o b j e c t i v e times, show error bounds c o n v e r g e increases: more c o n s t r a i n e d class [KLEI representations, objective lower in cannot empirical Although more s e v e r e . i n terms of a f i n i t e and through t h e number o f b a l a n c e For error it if computed. truncation functions. of quantities finite be expansion h i g h e r o r d e r moments o f t h e w a i t i n g much however, w h i c h have bounds c a n degree not computed. f o r these would infinite unknown e x c e p t r e a s o n why generalized an the usually distributions l i m i t a t i o n s of a n u m e r i c a l a n a l y s i s : has computed, approximation This of t h e Nevertheless, between the LP effort: were f o u n d m. r o u g h l y as t h e upper results and increases. lower These o f t h e LP a r e g a i n e d a t expense of a d d i t i o n a l c o m p u t a t i o n a l to increase the 2 computational the costs 72 Compared w i t h provide better simulation,' the results at less parameters p < 0.5, a, <, 0.9 be recommended f o r the a n a l y s i s of region. extrapolation exhaustive only and other formal suggest These with the are two (2) the comparison various service As those of results range simulation could of employed, outside the of use of render an Such h e u r i s t i c s may techniques unnecessary. particular main may great familiarity Markov c h a i n areas has model. which deserve with compare effort the could of in chapter Kotiah, those further II, Kotiah. it Wolf. study. two obtained of d i r e c t e d towards a but are have employed the One t o compare the for useful to Further convenient such approximation might probabilities whose a g g r e g r a t e our alternate methods. search s t a t e s whose i n d i v i d u a l required, Markov c h a i n s using two with numerical particularly the chain systems main interesting I t would be u s e f u l system approximations. somehow combine the would be be Markov multiserver A l t h o u g h we convergence behaviour a l s o be infinite solving infinite which c o u l d S e n e t a and explicitly for of multiclass, disciplines. S e n e t a - W o l f , and a p p r o a c h of not heuristic f o r t r u n c a t i n g and method to is to approximate systems o p e r a t i n g s o l u t i o n techniques discussed techniques be use found are: t h e study' of models, and the were FURTHER STUDY (1) LP The method analysis SUGGESTIONS FOR There . over t h e m s e l v e s , however, a f t e r been a c q u i r e d C. Whichever solutions cost of this LP probability are is 73 important. q , but 2 state F o r example, with d i f f e r e n t server from further with configurations, queueing fixed q,, i n t o the s i n g l e priority. those employed dependence (fi ). of in W ± detail, perhaps realistically minimum performance. to a true general Limiting thesis could of s y s t e m might making the number o f s e r v e r s preemptive alternating only similar an to be u s e d t o e s t i m a t e t h e a single communications be made among include arguments applied multiserver priority, and on t h e s y s t e m ' s m i x t u r e by could comparison might times. this Alternatively, ± priority, A l e s s comprehensive o f mean w a i t i n g cutoff chain p r o f i t a b l y be a comparison disciplines: non-preemptive o f Markov of o t h e r m u l t i c l a s s , F o r example, service priority, t h e m s e l v e s might and c o m p a r i s o n systems. various analysis work i n t h e m e t h o d o l o g y the techniques the a n a l y s i s the of s t a t e s 2 solutions, the sets (*; q, q ) . Aside to combine model customer classes be s t u d i e d i n more correspond more s y s t e m , o r by d e t e r m i n i n g to ensure a given level of system 74 APPENDIX A - A COMPARISON OF NON-PREEMPTIVE PRIORITY ALTERNATING PRIORITY SERVICE D I S C I P L I N E S In this appendix service disciplines, customers (denoted C(°°,1). Recall exhaustively, service. only and non-preemptive NPP), that two C(k,,k ) 2 and the C(°°,1) service and NPP NPP switching function system. are properly exactly following we the means that whenever specific for type 1 priority queue 1 is case served one customer admitted for disciplines, general alternating fact, quite i s nearly when the different; i t is indistinguishable rules for queue c h o s e n , t h e C(°°,1) s y s t e m c a n be made t o same as the NPP discipline. assume f o r sake o f c o n v e n i e n c e , t h a t work-conserving identically two priority are in general In compare alternating t h e p a r t i c u l a r c a s e C(°°,1) t h a t from t h e all discuss t h e n queue 2 has a t most The priority we AND service n<s disciplines In n>s , because should function . queue 1 , arrivals Figure [ central controller the s 12 - S c h e m a t i c o f a 2 - C l a s s M u l t i s e r v e r System x servers Queueing 75 To e x p l a i n t h e n e c e s s a r y of the diagram interpreted Figure is in Figure assumed t o be a b l e With 12 . Each r u l e s we make service discipline use may be a s a s e t o f r u l e s by w h i c h t h e c e n t r a l c o n t r o l l e r o f 12 s e l e c t s w a i t i n g server, queue s w i t c h i n g as well this customers to as sense for service. the The c o n t r o l l e r idle/busy state of each t h e empty/not-empty s t a t e o f e a c h q u e u e . information the controller can direct waiting customers t o f r e e s e r v e r s , switching transitions, represented by c h a n g e s i n t h e s t a t e v a r i a b l e and operations a l l other queues i f n e c e s s a r y . of the c o n t r o l l e r are Queue assumed to i , be instantaneous. In attends the queue controller NPP discipline 1 (i=l). will, for service. then type a controller 2 Whenever i f queue customer 1 is I f queue customer returns the is a not 1 the c o n t r o l l e r on average queue switches at this a customer finally sent a type 1 and queue 2 i s not, served ( i = 2 ) , and t h e free spends s l i g h t l y occurs less because time the a s soon In need n o t be any f r e e s e r v e r s . If becomes i d l e , the identical a n d t h a t queue 2 i s n o t . even 1 i n t h e meantime. to select 1 ( i = 1 ) t o queue 2 ( i = 2 ) i s i n queue 2 t h e c o n t r o l l e r i n queue the (i=l). This 1 i s empty instant there soon a s a s e r v e r arrives 1. from queue i t s e n s e s t h a t queue general as observing normally idle o f t h e C(°°,1) s y s t e m w h i c h . i s n o t t h e NPP d i s c i p l i n e , as becomes empty, immediately to controller controller server 1 i s empty t o m o n i t o r queue In one v e r s i o n central server, reserves if a i t t o be type When one t y p e 1 served customer 2 customer i s the c o n t r o l l e r returns to 76 monitor queue controller server the 1 (i=l). would have 1 customer To make t h e priority for and 1 dependent. That to queue 2 independently and only service NPP service Markov c h a i n the as described s,, server the q, to of switching of the In these explicitly the The queue and to fact, simple than potential turn out NPP as of i to be system. select the even n e c e s s a r y in a the a operation state i s understood position empty, would systems t h a t once the queue next d i s c i p l i n e would by the queue 1 1 becomes same o r d e r therefore of from f o r the i t i s not i s that non-preemptive rather then above represented a service switching f o r the Ci™,}) NPP 1 until for switch rules controller reason queue when queue i n the the 1. dependent exactly same c u s t o m e r s as the those described determined, variable. i n queue c o n t r o l l e r should have been s p e c i f i e d , t h e completely state The model of above. observing becomes a v a i l a b l e discipline. long situation would have s e l e c t e d server this version c o n t r o l l e r be (i), made i s , the equivalent Consequently, for be customer. exactly so customers, must 2 been just arrived controller type same C(°°,1) d i s c i p l i n e e q u i v a l e n t type when a this first became a v a i l a b l e type In i s not variable to operate as variables n, state the of controller an is independent 77 APPENDIX B - THE As a visual balance equations transition crucially state the a i d to on the space. state the it diagram. The After development is choice s p a c e of STATE SPACE TRANSITION useful utility of state of NPP of such variables model the to c o n s t r u c t some e x p e r i m e n t a t i o n the DIAGRAM a used we i n t o two steady the , 2-dimensional, with v a r i a b l e s (s (2) n 2: s , 3-dimensional, with v a r i a b l e s (s, , q rates at (Q^ most states ) to four arrivals Forbidden transitions type or those transition system. 13 and diagrams The two 14 split s ) indicated. 2 q ). 1 f 2 the two prohibited transition T h e r e can state, impossible the are common, and one set multiserver d i a g r a m s have o n l y boundary are this 1 f conditional each of those below for along n each to the be representing customer types. by service the (for example, no s^O). i = are from naturally ( < 3 i Q 2 0) = of are 1 d e p a r t u r e s when Figures states transitions departures discipline, segment, t h e neighbouring such and i n each represent pieces: n < s typical space depends have c h o s e n (1) For state diagram, to state the (s+1) of 2-class appropriately. NPP states t r a n s i t i o n s between t h e noted state two space queueing for n=s diagrams 78 Figure 14 - State Space f o r n ^ s 79 APPENDIX C ~ SETTING UP THE BALANCE EQUATION COEFFICIENT MATRIX "A": AN EXAMPLE This appendix structure of example how truncated numbered the balance the i n f i n i t e to of A We concerning also equations show w i t h an is ordered ( s e e (4.9) i n IV - C ) . appendix are in the the order space of and The t h r e e they are text. (1) Recall that we found multiserver non-preemptive dimensional (see system of balance of population same state priority system However, equations in increasing the III - D). sequentially the details equations. form m a t r i x i n t h e main further system s e c t i o n s of t h i s referenced Part presents the one d i m e n s i o n . to facilitates (2) minimizes the e f f o r t required to t r i a n g u l a r components: A = LU (e.g. f i l l - i n of z e r o e l e m e n t s ) . One ordering with increasing using s 2 automatic the balance Figure The up and s o l v e a must be ordered i n order with result equations equations, factorize A by m i n i m i z i n g was t o i n d e x increasing with which: generation of the balance satisfactory n , then . three- n , but w i t h i n a group of s t a t e s (1) increasing be S t a t e s c a n be i n d e x e d n , an o r d e r i n g s h o u l d be c h o s e n found to set states the 2-class the states q, , f o r the case of and first then s = 4 (4.3 - 4.5) o f I V - B into the is with servers, seen in 15. This diagram displays coefficient matrix Q equations. The shaded T the for squares upper the left-hand infinite set r e p r e s e n t nonzero corner of of the balance coefficients. Figure 15 - Matrix "A" For T\.=6, S=4 Servers 81 Indicated which n > s along n = 0,1,2,... . = 4 , display a very easily seen submatrices equation matrix only t h e t o p and s i d e a r e t h e g r o u p s when the coefficients five different is structure, be of into balance that the e n t i r e using The number o f s . n = n is square represented With truncated matrix up t o any p r e s e l e c t e d c u t o f f This actual submatrices. independent the the i t i s seen could (s+1 x s+1) predictable A such c a n be a easily . c (2) The figure shows f o r t h e p a r t i c u l a r infinite matrix equations and of n > s for f o r states with blocked When written states structure. are s+1 = 5 . for (five) Part regular matrix are submatrices equations, coefficients of dimension of c o e f f i c i e n t s generated The b a l a n c e of Nj the balance Before number variables. equations will be n > s , configurations n = n f o r (q, q ) 2 . of c o n f i g u r a t i o n s f o r 0 The q,=0 number f o r which of first Since s,+s (s, s ) 2 variables 0 ^ n < n +1 line Nj . the to N-j. encloses a l l must determine (s, s ; qi 2 For each n < s and s , + s = n . 2 and t h e r e f o r e t h e r e a r e 2 is s t a t e s f o r any g i v e n c truncated space q2=0, t how c ^ 0 . 0 = 6 ,n =6 . i n the s t a t e qi+q2 = n-s , (s+1)(n -s+1) states we states since then be n =0,1,2,.. and population (n+1) would n The h e a v y b l a c k for of s t a t e s which e x i s t any f i x e d then coefficents deriving for number of case = s for i s equal 0 q ) , 2 there For (n-s+1) n £ s , the (s+1) . n = n the There are ^ s . t o t h e number of Therefore, with n £ s , c 82 n +1 E (s+1)(n-s+1) n=s c N = 1 + 2 + ... + s + = s(s+1)/2 J or, N + (s+1)(n-S+2)(n_-s+3)/2 J Then Nj =60 The only f o r t h e example n c number o f e q u a t i o n s N x those balance are f o r which equations found already equations can equation N best n number Figure . bounds matrix . at f i r s t group, three be the 15). three Maximizing A will to These number this 77]. be of the equations N^ variables additional N^ of balance example, then t h e number o f c o n s t r a i n t s in this (n,-s+l) more any more t h a n For [KOTI appear But on e x a m i n a t i o n included i n the t o t a l of v a r i a b l e s possible truncated by =43 , there w i l l c (see be might =7 c constraints. = 4 0 + 3 fixed n +1 w h i c h do n o t i n v o l v e included = 6 . 0 ^ n < n c i n the (C.1) l_ C for a way, we a r e a b l e t o o b t a i n t h e In g e n e r a l , f o r a t r u n c a t i o n a t additional equations, have d i m e n s i o n s (Nj_ x N j ) ' and N j the given ( C . 1 ) , and N = n E° ( s + 1 ) ( n - s + 1 ) 1 + 2 + ... + s + + (n -s+l) c n=s or, N = s ( s + l ) / 2 + (s+1 ) ( n - s + 1 ) ( n - s + 2 ) / 2 c c .+ ( n , - s + 1 ) . (C.2) P a r t (3) Figure 15 also illustrates [BHAR 60, p . 1 4 ] o f t h e c o n t i n u o u s - t i m e any from given any squares) balance reached row, t h e s t a t e of on the the l e f t equations from states any with f o r many q u e u e i n g state. model. In d i a g o n a l c a n be reached coefficients (shaded nonzero This irreducibility Markov c h a i n on t h e m a t r i x or r i g h t . other the i s the basic systems; Hence, any the s t r u c t u r e of state can be Markov c h a i n i s rreduc i b l e . 84 APPENDIX D - A DERIVATION FOR THE NORMALIZATION IN [KOTI 77] Consider v X customer = a\ i ± types. average The arrival , (i=1,2...,v). Kleinrock [KLEI with s average , where rate. customer Z±<*± The The f o l l o w i n g identical = servers arrival > 1 and rates are is a n c 5 average GIVEN service t h e times are r e a s o n i n g i s g u i d e d by t h a t o f 75, p . 1 9 ] . Assume t h a t number system (i=1,2,...,v) ± total y a queueing CONDITION a stationary of customers probability i n the system distribution p(n) , e x i s t s , for the with oo I n=0 Assume In a l l customers addition, [KLEI time that the 76, p . 1 1 3 ] , shorter service p(n) system must in particular, that distribution is service time additional interarrival restriction on s e r v i c e customers have an e q u a l c h a n c e identical servers. First we interpreted show as: random time). server i s free time interval is (X./S)T . that Or, t h a t placed on service when Beyond t h i s its proviso, either distributions. utilization specific server p = 1 - z , where r , the expected during c a n have a obtained discipline a t any random t i m e ) . Also work-conserving i s that the The o n l y individual o f b e i n g s e r v e d by any o f t h e the p = Pr(any is sampled. be 0 < p < 1 . served, be which to or (D.1) no c u s t o m e r t h e r e a r e no o t h e r r e s t r i c t i o n s time . are eventually or longer than time = 1 factor is p , may busy z = Pr(any at of a r r i v a l s T , t h e busy be any specific D u r i n g an a r b i t r a r i l y number s t o one long server time of the s e r v e r i s 85 T(1-Z) T , and will service In be time E(y) the average T(1-Z) of = E[ interval number so the E(y T / E(y) | customer , the , there E Defining the T o y E. i ± = x i i y i / s i s the during expected served: arrivals roughly . matches the utilization ~ 1 ± Now we develop conditional = Pr(any 1 p(0) + server p(D 1/s) z combining i s free server ... Therefore, k s ( . D - 2 ) (D.3) an' a l t e r n a t e e x p r e s s i o n specific (1- . i for z using (D.1) probability. specific Pr(any i as 1 - p z = o y • ±y±/ z E z z factor = / and: 1 - = then = E[ E(y) served in service)] = E ^ ) ^ T(1-Z) = i * = of is equality, U/s) z Here, type number customers served: T -> °° and . customers being U/s) As number of + = + (1- s-1 E n=0 (D.3) a t any i s free ... ( 1 - 2/s) random | number p(2) + and - n/s) in + 0 + 0 + p(n) (D.4), the system)] ... ( S - 1 ) / S ) p(s-1) + 0 (1 time) ... (D.4) desired result is obtained: 1 - ft = This equation s-1 E n=0 appears (1 - n/s) i n the text p(n) as , 0<p<1 (4.13) i n IV . - (D.5) D. 86 BIBLIOGRAPHY [ALLE 77] B. A l l e n , R.S. A n d e r s s e n , E . S e n e t a , "Computation of S t a t i o n a r y M e a s u r e s f o r I n f i n i t e Markov C h a i n s " TIMS S t u d i e s i n t h e Management S c i e n c e s M.F. N e u t s , e d . , 7 1977 13-23. [AVI B. A v i - I t z h a k , W.L. M a x w e l l , L.W. Miller "Queueing w i t h 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. 65] [BART 81] P. B a r t f a i , J . Tomko, P o i n t P r o c e s s e s and Queuing Problems, C o l l o q u i a Mathematica S o c i e t a t i s J a n o s B o l y a i , 24 (1978) North-Holland, New Y o r k , 1981. [BHAR 60] A.T. B h a r u c h a - R e i d , E l e m e n t s of t h e T h e o r y of Markov P r o c e s s e s and T h e i r A p p l i c a t i o n s , 1st e d . McGraw H i l l , New Y o r k , 1960. [BOBI P.A. B o b i l l i e r , B.C. Kahan, A.R. P r o b s t S i m u l a t i o n w i t h GPSS and GPSSV Prentice-Hall, Englewood C l i f f s , N.J., 76] [BUNC 76] J.R. Bunch, D . J . Rose, Sparse Matrix Academic P r e s s , New Y o r k , 1976. [COBH 54] A. Cobham, Problems", [COOP 69] R.B. C o o p e r , G. M u r r a y "Queues S e r v e d i n C y c l i c O r d e r " B e l l S y s t . T e c h . J.,- 48(3) 1969 1976. Computations " P r i o r i t y Assignment i n W a i t i n g L i n e Opns. Res., 2 1954 70-76. 675-689. [COOP 70] R.B. C o o p e r , "Queues S e r v e d i n C y c l i c O r d e r : W a i t i n g Times" B e l l S y s t . T e c h . J . , 49(3) 1970 399-413. [COOP 72] R.B. C o o p e r , Macmillan, [DAVI R.H. D a v i s , "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. 66] I n t r o d u c t i o n t o Queueing New Y o r k , 1972. [DUFF 77] I.S. D u f f , "A S u r v e y o f S p a r s e M a t r i x Proc. IEEE, 65(4) 1977 500-535. [ E I S E 71] M. E i s e n b e r g , Opns. Res., Theory, Research" "Two Queues w i t h C h a n g e o v e r 19(2) 1971 386-401. Times" 87 [EISE 72] M. E i s e n b e r g , "Queues w i t h P e r i o d i c Changeover Time" O p n s . Res., 20(2) 1972 440-451. [EVAN 74] D.J. Evans, ed., Software f o r Numerical Mathematics, Academic P r e s s , New Y o r k , Service and 1974. [FISH 78] G. S. F i s h m a n , Simulation, [GOLD 81] H. M. G o l d b e r g , " C o m p u t a t i o n of S t a t e 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 w i t h Customer C l a s s e s having D i f f e r e n t Service Rates" INFOR, J_9(1) 1981 48-58. [GROS 74] D. G r o s s , C M . Harris F u n d a m e n t a l s of Q u e u e i n g T h e o r y Wiley, New Y o r k , 1974. [GUST 72] F.G. G u s t a v s o n , S p a r s e Systems i n [ROSE 7 1 ] , [HALF 72] S. H a l f i n , "A P r i o r i t y Q u e u e i n g M o d e l f o r a M i x t u r e of Two T y p e s o f C u s t o m e r s " SIAM J . A p p l . Math., 23(3) 1972 369-379. [KALA 71] J.E. Kalan, " A s p e c t s of L a r g e - S c a l e , In-Core L i n e a r Programming" P r o c . A n n u a l ACM C o n f e r e n c e , C h i c a g o , 1971 304-313. [KLEI 75] L. K l e i n r o c k , Q u e u e i n g S y s t e m s , Volume I : Theory, Wiley, New Y o r k , 1975. [KLEI 76] L. K l e i n r o c k , Queueing Computer A p p l i c a t i o n s , [KOTI 73] T.C.T. K o t i a h , N.B. S l a t e r , "On T w o - S e r v e r Queues w i t h Two T y p e s o f C u s t o m e r s " Opns. Res., 2J_ 1973 597-603. [KOTI 77] T.C.T. K o t i a h , "On a L i n e a r Programming T e c h n i q u e f o r t h e S t e a d y - S t a t e B e h a v i o u r of some Q u e u e i n g Systems", Opns. Res., 25(2) 1977 289-303. [KUEH 79] P . J . Kuehn, " M u l t i q u e u e Systems w i t h N o n e x h a u s t i v e Cyclic Service" B e l l Syst. Tech. J . , 58(3) 1979 671-698. [LUEN 73] D.G. L u e n b e r g e r , Introduction to Linear N o n l i n e a r Programming Addison-Wesley, Reading,Mass., 1973. Principles Wiley, New of D i s c r e t e Event York, 1978. "Some B a s i c T e c h n i q u e s of L i n e a r E q u a t i o n s " 41-52. Systems, Wiley, for Solving Volume 11: New Y o r k , 1976. Poisson and 88 [MURT 81 ] B.A. M u r t a g h , A d v a n c e d L i n e a r Programming; C o m p u t a t i o n and P r a c t i c e McGraw-Hill, New Y o r k , 1981. [NAIR 76] 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 w i t h Non-Zero S w i t c h R u l e " Computers a n d Opns. R e s . , 3 1976 337-346. [REID 74] J.K. R e i d , " D i r e c t Methods i n [EVAN 7 4 ] , 29-47. [ROSE 71] D. J . Rose, R.A. W i l l o u g h b y 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 P r e s s , New Y o r k , 1971. [ROSS 72] S.M. R o s s , Introduction to Probability Academic P r e s s , New Y o r k , 1972. [SCHL 81] W. S c h l e e - K S s s l e r , "A S i n g l e S e r v e r Queue w i t h Two Types of Customers and A l t e r n a t i n g S e r v i c e i n P i e c e s of ^ and " i n [BART 8 1 ] , 343-357. [SENE 67] E. S e n e t a , " 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 " P r o c . Camb. P h i l . S o c , 63 1967 983-992. [SENE 68] 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 Applicat ions" P r o c . Camb. P h i l . S o c , 64 1968 465-470. [SHER 78a] A.H. Sherman, "Algorithms f o r Sparse Elimination with P a r t i a l P i v o t i n g " ACM T r a n s , on M a t h e m a t i c a l S o f t w a r e 4(4) 1978 330-338. [SHER 78b] A.H. Sherman, " A l g o r i t h m 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 Partial Pivoting" ACM T r a n s a c t i o n s on M a t h e m a t i c a l S o f t w a r e 4(4) 1978 391-398. [SING 81] R. S i n g h , S. Subba Rao, S.C. Gupta " A n a l y s i s o f a M o b i l e R a d i o C o m m u n i c a t i o n System w i t h Two T y p e s o f C u s t o m e r s a n d P r i o r i t y " I n t . C o n f . on Comm., D e n v e r , 1981 I E E E ( I C C - 1 9 8 1 ) , v.3 57.4.1-57.4.5 . [SLAT 73] N.B. S l a t e r , T.C.T. K o t i a h "The S t e a d y - S t a t e o f a M u l t i s e r v e r M i x e d Adv. i n A p p l . P r o b . , 5 1973 614-631. < f o r Sparse M a t r i c e s " Models Gaussian Queue" 89 [STEW 78] [SYKE 70] W.J. S t e w a r t , "A C o m p a r i s o n o f N u m e r i c a l T e c h n i q u e s i n Markov M o d e l i n g " C o m m u n i c a t i o n s of t h e ACM, 2±(2) 1978 144-152. J.S. Sykes, " S i m p l i f i e d A n a l y s i s o f an A l t e r n a t i n g - P r i o r i t y Queue w i t h S e t u p T i m e s " Opns. Res., _[8 1970 1182-1 1 92. [TAYL 80] I.D.S. T a y l o r , J.G.C. T e m p l e t o n " W a i t i n g 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 t o an U r b a n Ambulance Service" Opns. Res., 28(5) 1980 1168-1188. [WALL 66] V . L . W a l l a c e , R.S. R o s e n b e r g " M a r k o v i a n M o d e l s and N u m e r i c a l A n a l y s i s o f Computer System B e h a v i o u r " AFIPS S p r i n g J o i n t Comp. C o n f , 28 1966 141-148 [WILL T.M. W i l l i a m s , "Nonpreemptive P r i o r i t y Queues" J . O p e r a t i o n a l Res. S o c . 31(12) 1980 1105-1107. 80] [WOLF 80] Multi-server D. W o l f , " A p p r o x i m a t i o n of t h e I n v a r i a n t P r o b 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 A p p l . P r o b . , 12 1980 710-726. 90 Glossary A coefficient A, first b, b matrix (N-j-x N ) x of N o t a t i o n of the submatrix of right-hand side constant constra int(s) B coefficient matrix c counter c% general confidence 2 v number o f s t a t e E['] expectation operator FCFS first-come, first-served i,j,k integer I identity normalization contraints model interval d equations A ^ space priority balance x ( v e c t o r ) of the n o r m a l i z a t i o n of the i n the s t a t e C(k,,k ,..,k ) cyclic N with v service discipline indices matrix (m x m) J a v e r a g e number o f s i m p l e x objective function ^ maximum number s e r v e d d u r i n g p h a s e K total L a fixed LP linear LU a f a c t o r i z a t i o n of a m a t r i x as a product and upper t r i a n g u l a r m a t r i c e s m number o f rows i n t h e LP M|M|s queues i n a Markov c h a i n ^1 M|G | 1 priority for simulation results system variables forcyclic identity matrix number o f o b j e c t i v e iterations required per i of c y c l i c f u n c t i o n s f o r an LP priority problem maximum queue l e n g t h program of lower s i n g l e - s e r v e r queue w i t h a P o i s s o n a r r i v a l and a g e n e r a l s e r v i c e t i m e d i s t r i b u t i o n process s - s e r v e r queue w i t h a P o i s s o n a r r i v a l p r o c e s s a n d 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 (2) n f o r number f i x e d value of 0 n N index of columns i n t h e LP, of customers n, number i n a queueing system i n t h e system t r u n c a t i o n parameter f o r the s e t of balance e q u a t i o n s (1) t o t a l number o f s t a t e s i n a f i n i t e s t a t e s p a c e , (2) t o t a l number o f m e a s u r e d e v e n t s i n a s i m u l a t i o n c number N of b a l a n c e e q u a t i o n s (rows) i n number o f 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 columns of A N number of n o r m a l i z a t i o n constraints A associated (rows) i n with B N NPP non-preemptive p(n) steady state p r o b a b i l i t y queueing system p (n), p (n) P discrete-time £ P,, P lower u submatrices 2 , .P priority (m x m) and upper of general discrete P^(k), P (k) P(s, s ) P(s, s ; q, q ) q Q s s 2 P probability distribution and upper bounds on P ( k ) f o r e a c h k p r o b a b i l i t y of s t a t e v a r i a b l e f o r number t h e queue of type total c (s, s ; 2 i cutoff state t time available level for cutoff variable (superscript) number of matrix transpose 2 customers waiting matrix times servers priority f o r number q ) t r a n s i t i o n rate r a t i o s of l i m i t i n g v a l u e s of average s ± of c o n t i n u o u s - t i m e Markov c h a i n R, , R matrix 2 2 state in ± transition probability same a s P f s , s ; 0 0) 2 2 in a P P(k) lower n customers bounds on p ( n ) f o r e a c h n Markov c h a i n truncation u for of type queues i customers in service 92 v (1) number o f q u e u e s in cyclic (2) number o f c u s t o m e r priority, classes i n a general w random v a r i a b l e W mean w a i t i n g x an i n d e x e d member o f t h e s e t { P t s , s ; q i ± i ± for waiting time of type i customers time f o r type i customers 2 x finite column v e c t o r (state x^ infinite x^ a basic y (1) s l a c k system of v a r i a b l e s p r o b a b i l i t i e s plus column v e c t o r q )} 2 i n t h e LP, the slack variable) of the p r o b a b i l i t i e s solution for a linear x i program variable, (2) random v a r i a b l e for service time y_^ random v a r i a b l e y z average s e r v i c e time of a type i customer p r o b a b i l i t y t h a t any g i v e n s e r v e r i s f r e e a t any random t i m e Z, Z^. one o f t h e o b j e c t i v e Z(W ) truncation 0 null i f o r s e r v i c e t i m e of a t y p e i c u s t o m e r functions o f VJ u s e d a s an o b j e c t i v e ± f r a c t i o n of a r r i v i n g Oi* value p, fi f r a c t i o n of system of t y p e i 6(') discrete delta A convergence parameter ± of vs. Oi Poisson total n exponential TT_ infinite customers which a r e of type i i n a 2 - c l a s s system a t which t h e c u r v e h a s slope=1 Poisson resources a l l o c a t e d t o customers function arrival X ± function vector a ± f o r t h e LP rate row v e c t o r technique of type i customers arrival service i n a matrix i t e r a t i o n rate rate of customers of type i customers o f Markov c h a i n p r o b a b i l i t i e s 93 m-component solution permutation matrix utilization parameter total utilization a critical arbitrary value time of a t r u n c a t e d f o r type (traffic of p interval Markov c h a i n model i customers intensity) parameter f o r NPP m u l t i s e r v e r systems
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- A queueing analysis of a multichannel, integrated voice...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
A queueing analysis of a multichannel, integrated voice and data communications system Haller, Dennis Raymond 1982-12-31
pdf
Page Metadata
Item Metadata
Title | A queueing analysis of a multichannel, integrated voice and data communications system |
Creator |
Haller, Dennis Raymond |
Date | 1982 |
Date Issued | 2010-04-13T15:29:35Z |
Description | A multichannel radio communications system is modeled as a multiserver queue, with two distinct customer classes representing voice and data messages. Data, the class with the shorter average length, is given non-preemptive priority over voice. The queueing model is analyzed as a continuous-time Markov chain with an infinite state space. The infinite set of steady state balance equations is truncated, then solved numerically using the linear programming (LP) technique of Kotiah. Upper and lower bounds are thereby obtained for the mean waiting times of each customer class, and the probability distribution for the number of messages in the system. Exploitation of the Markov chain's property of irreducibility improves the original algorithm by considerably reducing the computational cost. Simulation is used to help analyze the system and to validate the numerical results. The particular four-channel case of the queueing model is treated in detail; both simulation and numerical results are presented. The LP method produces excellent results when the data traffic intensity is less than about 0.1. This corresponds typically to the proportion of data messages being less than 90%. For other traffic mixtures, the upper bounds, especially for waiting times, are often too high to be of practical use. However, the lower bounds of the mean waiting times are of greater use; the simulation results show them to be reasonably good approximations to the true steady state values. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2010-04-13 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065616 |
URI | http://hdl.handle.net/2429/23420 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 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
- Original Record: 1.0065616 +original-record.json
- Full Text
- 1.0065616.txt
- Citation
- 1.0065616.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
Japan | 7 | 0 |
United States | 7 | 0 |
China | 5 | 19 |
Germany | 4 | 9 |
Russia | 3 | 0 |
India | 2 | 0 |
Uganda | 1 | 0 |
City | Views | Downloads |
---|---|---|
Tokyo | 7 | 0 |
Ashburn | 5 | 0 |
Unknown | 5 | 9 |
Shenzhen | 4 | 16 |
Saint Petersburg | 3 | 0 |
San Francisco | 2 | 0 |
Hyderabad | 2 | 0 |
Beijing | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065616/manifest