INTRODUCCIÓ ALS MODELS NO EXPONENCIALS I XARXES DE … · Podem considerar dos tipus de xarxes de...

U P C I.O.E. Diplomatura de Estadística

U P CTCiS. Grau-IU UB-UPC INTRODUCCIÓ ALS MODELS NO EXPONENCIALS

INTRODUCCIÓ ALS MODELS NO EXPONENCIALS I XARXES DE CUES

• INTRODUCCIÓ A LES XARXES DE CUES. Concepte de xarxa oberta i tancada. Xarxes obertes i Teorema de Jackson.

• MODELS NO EXPONENCIALS Cua M/G/1: Fòrmula de Pollaczeck-Khintchine. Cua G/M/1: casos Ek/M/1, Hip/M/1, Hyp/M/1. Ús de QTS_EXCEL.

• APROXIMACIONS PER A CUES GI/G/s. Aproximació d’Allen-Cuneen. Aproximacions per a cues congestionades (Heavy Traffic)

U P C

Grau IU UB-UPC. Esteve Codina TCiS Xarxes de Cues.

XARXES DE CUES EXPONENCIALS

Sistemes de cues exponencials formant una xarxa de muntatge de ordenadors o cotxes, per exemple.

Podem considerar dos tipus de xarxes de S.E.:

a) OBERTES. reben entrades de clients procedents de una o varies poblacions externes i que tenen sortides cap a l’exterior;.

b) TANCADES. No reben entrades de poblacions externes ni tenen sortides a l’exterior. Número constant de clientes circulant dins de la xarxa.

Exemple.

Xarxa oberta de S.E.

Exemple. Sistema M/M/s/./N:

Pobl. 2

1

2

3Pobl. 1 Exter.

1 2

U P C


Xarxes Obertes. Teorema de Jackson

Condicions sota les que les xarxes obertes de S.E. presenten propietats per efectuar una anàlisis per descomposició.

1. El S.E. (nodo) i té un número de servidors si de característiques idèntiques entre sí. Els temps de servei de cada servidor tenen distribució exponencial de probabilitats amb capacitat individual de servei μi.

2. La capacitat de la cua en cada S.E. és il·limitada.

3. Els clients que han estat servits en el nus i es reparteixen entre els nusos j ∈ E(i), emergents del i i, amb probabilitats pij > 0 constants al llarg de tota l’evolució del sistema.

4. el temps associat a l’arc (i,j) és zero.

Si totes les arribades externes estan distribuïdes poissonianament i es verifiquen les condicions anteriors llavors s’anomenen xarxes de Jackson i sobre elles pot aplicar-se el resultat del teorema de Jackson (1957) .

U P C


Teorema de Jackson. Segui una xarxa oberta de S.E. verificant les condiciones per a la descomposició anteriors, amb solucions del sistema:

NjprN

iijijj ,,1

1=+=

=λλ

tals que iii s μλ ⋅< per a tot S.E.

i=1,…,N. Llavors cada S.E. es comporta com una cua M/M/si amb entrades

de clientes con taxa iλ i que presentarà en estat estacionari una distribució de probabilitats pròpia de les cues M/M/s i independent de la dels altres sistemes dins de la xarxa.

1

21

1211111

+

=

λ

λ

λ

λ

NNNNN

N

NN ppp

ppp

r

r

U P C


===

→++=

+==

451010

3/22/12/15

10

3

2

1

3213

12

1

λλλ

λλλλλλ

λ

=

−−−→

+

=

05

10

3/112/1012/1001

3/212/1

002/1000

05

10

3

2

1

3

2

1

3

2

1

λλλ

λλλ

λλλ

Pobl. 2

1

2

3Pobl. 1 Exter. 1/2

1/2 1

2/3

1/3

r1=10

r2= 5

U P C


Per tant les xarxes de Jackson exhibeixen de la propietat que la distribució de probabilitats del número de clients en una estació i y el número mig de clients en la estació es pot calcular tractant l’estació i como un modelo M/M/ is amb taxa d’arribades

iλ i taxa de servei per servei iμ .

El procediment d’anàlisis consisteix en els següents punts:

1. Estableix la matriu d’incidències entre nusos, P, constituïda per la probabilitat ijp de cada possible transició de nus.

2. Resoldre el sistema de equacions lineal: Pr ⋅+= λλ .

3. Verificar que iii s μλ ⋅< para i=1,…,N.

4. El número de clientes total en la xarxa, TotalL , és la suma dels clientes en cada

estació de servei: ==

N

iiTotal LL

1.

U P C


5. El temps esperat de permanència al sistema es λTotalL

W = on ==

N

iir

1λ és el

número mig de clients que arriben des de l’exterior al sistema per unitat de temps.

Exemple. Es vol dimensionar la xarxa de S.E. anterior i es disposa de servidors con taxa individual de servei μ = 12. Determinar en cada nus el número mínim de servidors de forma que la xarxa de S.E. presenti estat estacionari i calcular les demores mitjanes en tots els S.E. de la xarxa.

Se sap que les entrades als S.E. 1, 2 i 3 són respectivament: 10, 10, 45. Per tant:

1. Per al nus 1, si s1= 1 , ρ1 = λ1/μ1 = 10/12 <1.

2. Per al nus 2, si s2= 1 , ρ2 = λ2/μ2 = 10/12 <1.

3. Per al nus 3, cal dotar-lo de s3= 4 servidors i llavors ρ3 = λ3/(s3 ⋅μ3) = 45/(4⋅12) <1.

Els nusos 1 i 2 amb un sol servidor són cues de tipus M/M/1 amb les mateixes taxes d’entrada:

P0= 1- ρ1 = 1-10/12 = 1/6;

2/1 ,51 1

121

1

121 ====

−==

λρρ LWWLL

U P C


El nus 3 es comporta com una cua M/M/4:

Si θ=λ3/μ3 =45/12 llavors:

006561,015)1245 4

(!4

181,280

4!4

13!3

12211

11

0 =

⋅+=

∞

=++++=

−−

iiP ρθθθθ

U P C


Exemple

Es disposa de servidors amb taxa de servei μ=2. Per a la xarxa determinar:

a) El número mínim de servidors en cada sistema de espera de forma que s’arribi a l’estatestacionari.

b) La taxa de sortida de clients a l’exterior per als S.E. 3 i 4.

Exter.

1 2 3

4

1/3 1/2 1/2

1/2 1/2

1/2 1/3

1/3

1/2

20

10

=

−−−−−

−−

→

+

=

2000

10

13/12/102/112/12/1

0012/103/101

03/12/102/102/12/1

0002/103/100

2000

10

4

3

2

1

4

3

2

1

4

3

2

1

λλλλ

λλλλ

λλλλ

=

142,17857,12857,2714,5

4

3

2

1

λλλλ

U P C


Per tant, per al sistema d’espera 1 són necessaris 3 servidors, per al nus 2, 2 servidors, per al nus 3 són necessaris 7 servidors i per al nus 4, 9 servidors.

Les sortides a l’exterior per al nus 3 = 12,857/3=4,28.

Les sortides per al nus 4 = 17,142/2=8,571.

Per al nus 1, ρ = λ1/3μ = 0,9523 θ=λ1/μ1 = 5,714/2 = 2,857

1/93.5=0.010690

3!3

12211

1

0 =

∞

=+++=

−

iiP ρθθθ

Per al nus 2, ρ = λ2/2μ = 2,857/4=0,714, θ=λ2/μ = 1,428

1.0211.48 2

20 =+===

λ 2 μ2!(1−ρ )ρθ LWPL

qq

El model M/G/1 Els S.E. que responen a model M/G/1 són aquelles que: o Les arribades segueixen un procés de Poisson amb taxa constant i

igual a λ i són i.i.d. o Els temps de servei obeeixen a una distribució de probabilitat

comuna qualsevol i són i.i.d, d’esperança 1/μ i variança σ2 o Hi ha un únic servidor al sistema.

Per aconseguir que s’arribi a l’estat estacionari n’hi ha prou amb que el factor de càrrega sigui < 1. (ρ <1)

P0=1 - ρ



La fórmula de Pollaczek-Khintchine determina l’esperança matemàtica de la longitud de cua en règim estacionari: Lq

A partir de las fórmules de Little s’obtenen la resta de magnituds, L, W, Wq.

La fórmula reflecteix la influència de la dispersió dels temps de servei

(variança σ2) en el comportament del S.E.:

A major σ2, major serà la longitud mitjana de cua Lq a igualtat de ρ i λ

U P C

I.O.E. Diplomatura de Estadística U P CTCiS. Grau-IU UB-UPC INTRODUCCIÓ ALS MODELS NO EXPONENCIALS

Cas particular M/M/1, tenemos σ2 = 1/μ2 i la fórmula de Pollaczek-Khintchine es converteix en,

coincidint amb el resultat trobat anteriorment. ➨ Cas particular M/Ek/1: la distribució dels tempos de servei és Erlang de paràmetres k y μ = 1/E[x], sa variança és 1/(kμ2) , i en aplicar la fórmula de Pollaczek-Khintchine:



o En el cas M/D/1, la distribució dels temps de servei és constant, de mitjana 1/μ unitats de temps (μ serveis per unitat de temps) y variança σ2 = 0, la fórmula de Pollaczek-Khintchine determina l’expressió de la longitud mitjana de la cua com,



M/D/1 system-size probabilities

0,000,050,100,150,200,250,300,35

0 1 2 3 4 5 6 7 8

size

prob

abilit

y

M/E(k)/1 system-size probabilities

0,000,020,040,060,080,100,12

0 1 2 3 4 5 6 7 8 9 10size

prob

abili

ty

QTS_EXCEL: CASOS M/Ek/1, M/D/1

APROXIMACIÓ DE LA CUA GI/G/s

U P C I.O.E. Diplomatura de Estadística U P CTCiS. Grau-IU UB-UPC INTRODUCCIÓ ALS MODELS NO EXPONENCIALS

Exacta per a M/M/s, M/G/1

Fórmula d’aproximació d’Allen-Cuneen

Per a qualsevol sistema GI/G/s es verifica:


APROXIMACIÓ DE LA CUA GI/G/s

Condicions properes a la saturació: “heavy traffic”

Per a la cua GI/G/s, wq (v.a. temps d’espera en cua) segueix una distr. aprox. exponencial i:

tresteve

Sticky Note

error: 1 és ---- s^2

E(k)/M/1 system-size probabilities

0,000,050,100,150,200,250,30

1 3 5 7 9 11

size

prob

abilit

y

CDF for E(k)/M/1 line waiting times

0,000,200,40

0,600,801,00

0,0 10,0 20,0 30,0

time

cdf

CDF for E(k)/M/1 system waiting times

0,000,200,400,600,801,00

0,0 10,0 20,0 30,0time

cdf

CUA G/M/1

Pràctica 4: QTS_EXCEL: Aproximació d’Allen-Cuneen

U P C I.O.E. Diplomatura de Estadística U P CTCiS. Grau-IU UB-UPC

INTRODUCCIÓ ALS MODELS NO EXPONENCIALS I XARXES DE … · Podem considerar dos tipus de xarxes de...

Documents

Transcript of INTRODUCCIÓ ALS MODELS NO EXPONENCIALS I XARXES DE … · Podem considerar dos tipus de xarxes de...