The following will be discussed in this chapter: M/G/1 queue, pollaczek-khinchin (P-K) formula, embedded markov chain observed at departure epochs, pollaczek-khinchin transform equation,queues with vacations, priority queueing. | Lecture Networking theory & fundamentals - Chapter 9&10 TCOM 501: Networking Theory & Fundamentals Lectures 9 & 10 M/G/1 Queue Prof. Yannis A. Korilis 1 10-2 Topics M/G/1 Queue Pollaczek-Khinchin (P-K) Formula Embedded Markov Chain Observed at Departure Epochs Pollaczek-Khinchin Transform Equation Queues with Vacations Priority Queueing 10-3 M/G/1 Queue Arrival Process: Poisson with rate λ Single server, infinite waiting room Service times: Independent identically distributed following a general distribution Independent of the arrival process Main Results: Determine the average time a customer spends in the queue waiting service (Pollaczek-Khinchin Formula) Calculation of stationary distribution for special cases only 10-4 M/G/1 Queue – Notation Wi : waiting time of customer i X i : service time of customer i Qi : number of customers waiting in queue (excluding the one in service) upon arrival of customer i Ri : residual service time of customer i = time until the customer found in service by customer i completes service Ai : number of arrivals during the service time X i of customer i Service Times X1, X2, , independent identically distributed RVs Independent of the inter-arrival times Follow a general distribution characterized by its pdf f X ( x ) , or cdf FX ( x ) Common mean E [ X ] = 1/ µ Common second moment E [ X 2 ] 10-5 M/G/1 Queue State Representation: {N (t ) : t ≥ 0} is not a Markov process – time spent at each state is not exponential R(t) = the time until the customer that is in service at time t completes service {( N (t ), R (t )) : t ≥ 0} is a continuous time Markov process, but the state space is not a countable set Finding the stationary distribution can be a rather challenging task Goals: Calculate average number of customers and average time-delay without first calculating the stationary .
