Basic Queueing Theory M/M/* Queues

Basic Queueing Theory

M/M/* Queues

These slides are created by Dr. Yih Huang of George

Mason University. Students registered in Dr.

Huang's courses at GMU can make a single

machine-readable copy and print a single copy of

each slide for their own reference, so long as each

slide contains the copyright statement, and GMU

facilities are not used to produce paper copies.

Permission for any other use, either in machinereadable or printed form, must be obtained from

the author in writing.

CS 756

1

Introduction

Queueing theory provides a mathematical

basis for understanding and predicting the

behavior of communication networks.

Basic Model

Arrivals

Departures

Queue

CS 756

Server

2

1

Major parameters:

¨C interarrival-time distribution

¨C service-time distribution

¨C number of servers

¨C queueing discipline (how customers are taken

from the queue, for example, FCFS)

¨C number of buffers, which customers use to wait

for service

A common notation: A/B/m, where m is the

number of servers and A and B are chosen from

¨C M: Markov (exponential distribution)

¨C D: Deterministic

¨C G: General (arbitrary distribution)

CS 756

3

M/M/1 Queueing Systems

Interarrival times are exponentially

distributed, with average arrival rate ¦Ë.

Service times are exponentially distributed,

with average service rate ?.

There is only one server.

The buffer is assumed to be infinite.

The queuing discipline is first-come-firstserve (FCFS).

CS 756

4

2

System State

Due to the memoryless property of the

exponential distribution, the entire state of

the system, as far as the concern of

probabilistic analysis, can be summarized by

the number of customers in the system, i.

¨C the past/history (how we get here) does

not matter

When a customer arrives or departs, the

system moves to an adjacent state (either i+1

or i-1).

CS 756

5

State Transition Diagram

¦Ë

0

¦Ë

1

?

¦Ë

2

?

¦Ë

3

?

¦Ë

¦Ë

4

?

5

?

?

¦Ë

In equilibrium,

i+1

i

Let Pi = P{system in state i}

We have ¦Ë Pi = ? Pi +1

CS 756

?

The rate of

movements in

both directions

should be equal

6

3

Equations from the state transition diagram:

¦Ë P0 = ? P1

¦Ë P1 = ? P2

¦Ë P 2 = ? P3

Solve

¦Ë

?

¦Ë

P2 = ?

P

1

P

k

=

0

= ¦Ñ P0

1

= ¦Ñ ( ¦Ñ P0 ) = ¦Ñ 2 P 0

P

P

= ¦Ñk

P

0

What is ¦Ñ ?

CS 756

7

Since

¡Þ

k =0

Pk =

¡Þ

k =0

¦ÑP

k

0

=1

we have

1

1? ¦Ñ

P

0

=1

P

0

= 1? ¦Ñ .

That is, Pk = ¦Ñ k (1 ? ¦Ñ ).

Note that ¦Ñ must be less than 1, or else the

system is unstable.

CS 756

8

4

Average Number of Customers

N=

¡Þ

k =0

kP k = (1 ? ¦Ñ )

¡Þ

k ¦Ñk = ?

k =0

CS 756

9

Average delay per customer (time in queue

plus service time):

N

1

T= =

¦Ë ? ?¦Ë

Average waiting time in queue:

1

1

¦Ñ

W=

? =

? ?¦Ë ? ? ?¦Ë

Average number of customers in queue:

¦Ñ2

N Q = ¦ËW =

1? ¦Ñ

CS 756

10

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download