[PDF] Queuing Networks 23 mars 2017 BCMP networks

View - Download Queuing Networks

Previous PDF

Next PDF

IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Queuing Networks

Florence Perronnin

Polytech'Grenoble - UGA

March 23, 2017

F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 1 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Outline1Introduction to Queuing Networks

2Refresher: M/M/1 queue

3Reversibility

4Open Queueing Networks

5Closed queueing networks

6Multiclass networks

7Other product-form networks

F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 2 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works Introduction to Queuing NetworksSingle queues have simple results

They are quite robust to slight model variations

We may have multiple contention resources to model: I servers

Icommunication links

Idatabases

with various routing structures. Queuing networks are direct results for interaction of classical single queues with probabilistic or static routing. F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 3 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Outline1Introduction to Queuing Networks

2Refresher: M/M/1 queue

3Reversibility

4Open Queueing Networks

5Closed queueing networks

6Multiclass networks

7Other product-form networks

F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 4 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Refresher: M/M/1

M/M/1 queueInnite capacity

Poisson() arrivalsExp() service timesFIFO discipline

Denition

is the trac intensit y of the queueing system. . . .01. ..i-1ii+1

Number of clientsX(t) in the system follows abirth a nddeath p rocess.F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 5 / 46

IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Results for M/M/1 queue1Stable if and only if <12Clients follow a geometric distribution8i2?; i= (1)i3Mean number of clients?[X] =(1)4Average response time?[T] =1 0 100 200 300 400 500 600 700 800 900 1000

0 0.2 0.4 0.6 0.8 1

response time traffic loadresponse time M/M/1 F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 6 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

M/M/1/K

In reality, buers are nite: M/M/1/K is a queueing system with blo cking .K . . .01K-1K

Results for M/M/1/K queue

Geometric distribution with nite state space

(i) =(1)i1K+1F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 7 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

M/M/c.

.1 2 c ccic. . . icccResults for M/M/c queue

Stability condition C ;cii!ific C ;c1c! c iifi>cwhere= and with C ;c=1P c1 i=0ii!+cc!11=cF. Perronnin (UGA)Queuing NetworksMarch 23, 2017 8 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 9 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Outline1Introduction to Queuing Networks

2Refresher: M/M/1 queue

3Reversibility

4Open Queueing Networks

5Closed queueing networks

6Multiclass networks

7Other product-form networks

F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 10 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

ReversibilityDenition

A continuous-time Markov chainX(t) is time-reversible if and only if there exist a probability distributionsuch that8(i;j)2 E2; iqij=jqjiTheorem thedistribution is also the stationary distribution.Proof

Check the balance equations.

F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 11 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

ReversibilityProposition

An ergodic birth and death process is time-reversible.

Proof. . .01. ..i-1ii+1

i+212i+1i

01i2i1ii+1

i1By induction: 1

00=112Supposei1i1=ii. Then

i(i+i) =i+1i+1+i1i1Which givesii=i+1i+1.F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 12 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Burke's theoremTheorem

The output process of an M/M/s queue is a Poisson process that is independent of the numb erof customers in the queue. Sketch of Proof.ii+1 X(t) increases by 1 at ratei(Poisson process). Reverse process increases by 1 at ratei+1=iby reversibility.F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 13 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Outline1Introduction to Queuing Networks

2Refresher: M/M/1 queue

3Reversibility

4Open Queueing Networks

Tandem queues

Acyclic networks

Backfeeding

Jackson networks

Open networks of M/M/c queues

5Closed queueing networks

6Multiclass networks

7Other product-form networksF. Perronnin (UGA)Queuing NetworksMarch 23, 2017 14 / 46

IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Tandem queues

21LetX1andX2denote the number of clients in queues 1 and 2 respectively.Lemma

X

1andX2are independent rv's.Proof

Arrival process at queue 1 is Poisson() so future arrivals are independent

ofX1(t).By time reversibilityX1(t) is independent of past departures.Since these departures are the arrival process of queue 2,X1(t) andX2(t)

are independent. F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 15 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Tandem queuesTheorem

The number of clients at server 1 and 2 are independent and

P(n1;n2) =

1 n1 1 1 2 n2 1

1Proof

By independence ofX1andX2the joint probability is the product of M/M/1 distributions.This result is called ap roduct-formresult fo rthe tandem queue.

This product form also appears in more general

net works of queues. F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 16 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Acyclic networks

Example of a feed-forward network:

p jlp k0 p l0 l ki j p j0p i0p jk 0i 0j 0k 0lp ilp ikExponential service times output ofiis routed tojwith probabilitypijexternal trac arrives atiwith rate0ipackets exiting queueileave the system with probabilitypi0.Routing matrix: R=0 B

B@0pijpikpil

p ji0pjkpjl p kipkj0pjl p lipljplk01 C CAF. Perronnin (UGA)Queuing NetworksMarch 23, 2017 17 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Decomposition of a Poisson ProcessProblem

N(t) Poisson process with rateZ(n) sequence of iid rv'sBernoulli(p) independent ofN. Suppose thenth trial is performed at thenth arrival of the Poisson process.Result

Resulting processM(t)

of successes is

Poisson(p).Process of failuresL(t)

is

P oisson(1p)and

is indep endent of M(t).Bernoullip

1-pPoisson()Poisson(p)

Poisson((1p))F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 18 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Acyclic networksTotal arrival rateat no dei:i

(1iK). p jlp k0 p l0 l ki j p j0p i0p jk 0i 0j 0k 0lp ilp ikNo feedback: using Burke theorem, all internal ows are Poisson! Thus we can considerKindependentM/M/1 queues with P oissona rrivals with ratei, where i=0i+KX j=0 jpjii.e. ~ =~0+~Rin matrix notation.Stability condition

All queues must be stable independently:i< i,8i= 1;2;:::;K:F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 19 / 46

IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

BackfeedingExample

Switch transmitting frames with random errors. A NACK is sent

instantaneously if the frame is incorrect.Frame success probability isp.ArrivalsPoisson(0)Frame transmission timesExp ()

p 1-p

0F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 20 / 46

IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Backfeeding

p 1-p

0Remark

Arrivals are not Poisson anymore!

Result

The departure process is still Poisson with ratep.Proof in [Walrand, An Introduction to Queueing Networks, 1988].

F. Perronnin (UGA)Queuing NetworksMarch 23, 2017 21 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Backfeeding: steady-state

p 1-p

0Balance equations:

(0)0=p(1) (n)(0+p) =0(n1) +p(n+ 1);n>0Actual arrival rate=0+ (1p);so0=pwhich gives (0)=(1) (n)(+) =(n1) +(n+ 1);n>0M/M/1!

The unique solution is:

(n)= 1 n 10p 0p nF. Perronnin (UGA)Queuing NetworksMarch 23, 2017 22 / 46 IntroRefresher Reversibilit yOp ennet worksClosed net worksMulticlass net worksOther net works

Tandem queues

Acyclic net works

Backfeeding

Jackson net works

Op ennet worksof M/M/c queues

Jackson networks: example

l ki jquotesdbs_dbs25.pdfusesText_31

[PDF] bcmr 2016 participation 955 dont bcmr 2016 - Anciens Et Réunions

[PDF] BCMRD Release Notes

[PDF] BCN, prix culture, communiqué presse jd

[PDF] Bcom POSTE These CONDOR-SET

[PDF] BCP - Bourse en ligne CDM

[PDF] BCP-AwArd GOLDPREISTRäGER DES BEST OF CORPORATE

[PDF] BCPST - Lycée Saint - France

[PDF] bcpst - SCEI - Anciens Et Réunions

[PDF] BCPST 1.2 Lycée Pierre de Fermat Année 2010

[PDF] BCPST 2 - Anciens Et Réunions

[PDF] BCPST Manipulation d`images 2016-2017 Ce TP est en tr`es grande

[PDF] BCQS – Formation Qualité « La pratique de l`audit interne »

[PDF] BCR FISH DNA Probe, Split Signal Code Y5403

[PDF] bcr-1 wireless controller user manual bedienungsanleitung

[PDF] BCR-ABL - Santé Et Remise En Forme