Download - Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Transcript
Page 1: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Sisteme cu pierderi - continut

• Recapitulare: modelul simplu de trafic

• Modelul Poisson ( numar de clienti, numar de servere

• Aplicatii in modelarea la nivel de flux a traficului de date streaming

• Modelul Erlang ( numar de clienti , n servere unde )

• Aplicatii in modelarea traficului telefonic in trunchiul de retea

• Modelul binomial (clienti: , servere: )

• Modelul Engset (clienti: , servere )

• Aplicatii in modelarea traficului telefonic in retelele de acces

∞ ∞

n < ∞∞

k < ∞ n k=k < ∞ n k<

Modelul simplu de trafic

• Rata de sosire a clientilor in sistem (clienti pe unitatea de timp)

– = timpul mediu intersosiri

• Clientii sunt serviti de un numar n de servere paralele

• Cand un server e ocupat el serveste cu rata (clienti pe unitatea de timp)

– = timpul mediu de servire al unui client

• Exista pozitii pentru clienti in sistem

– Cel putin n pozitii de servire si cel mult m pozitii de asteptare

• Clientii blocati (care sosesc atunci cand sistemul este plin) sunt pierduti

1/ λλ

1/ μμ

n m+

Page 2: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Sistemul infinit

• Numar infinit de servere , fara pozitii de asteptare

– Nici un client nu e pierdut sau nici macar nu are de asteptat pentru a fi servit

• Uneori,

– Acest tip de sistem ipotetic poate fi utilizat pentru a obtine rezultateaproximative referitoare la comportamentul unui sistem real ( cu capacitate finita)

• Intotdeauna ,

– ofera limitele in ceea ce priveste performanta unui sistem real (cu capacitate finita a sistemului)

– Este mult mai usor de a analiza dupa aceea modelele de capacitate finita

n = ∞ 0m =

Sisteme pure cu pierderi

• Numar finit de servere , n pozitii de servire, fara pozitii de asteptare

( ).

– Cand sistemul e plin (cu toate cele n servere ocupate ) in momentul sosiriiunui client acesta e pierdut

• Din punctul de vedere al clientilor este important de stiu

– Care este probabilitatea ca sistemul sa fie plin cand el soseste?

0m =n < ∞

Page 3: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Modelul Poisson

• Definitie: Modelul Poisson reprezinta urmatorul model simplu de trafic:

– Infinit numar de clienti independenti:

– Timpii intersosiri sunt variabile IID si au o distributie exponentiala de medie:

• Deci clientii sosesc potrivit unui proces poisson de intensitate

– Numar infinit de servere:

– Timpii de servire sunt variabile IID distribuite exponential de medie

– Nu exista pozitii de asteptare:

• Modelul Poisson:

– Utilizand notatia Kendal acesta este o coada de asteptare de tipul

– Sistem infinit si deci fara pierderi

• Notatii:

– = intensitatea traficului

1/ μ

k = ∞

/ /M M ∞

1/ λ

n = ∞

λ

0m =

/ /M M ∞

/A = λ μ

Diagrama tanzitiilor de stare

• Fie numarul de clienti in sistem la momentul t

– Sa presupunem ca la un anumit moment de timp t si

sa consideram ce se intampla pe un interval scurt de timp

• Poate sosi un nou client cu probabilitatea ceea ce determinao tranzitie

• Daca , atunci cu probabilitatea un client poateparasi sistemul ceea ce determina o tranzitie:

• Procesul este in mod clar un proces Markov cu urmatoarea diagrama a tranzitiilor:

• Procesul este un proces de nastere si moarte ireductibil cu un spatiu al starilor infinit

1i i→ +

( )X t

{0,1,2, }S = …

( )h o hλ +( , ]t t h+

0i > ( )i h o hμ +

( )X t i=

1i i→ −

( )X t

( )X t

Page 4: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Probabilitatea de stare (1)

• Ecuatiile echilibrelor locale (LBE)

• Relatia de normare:

1

1

0

( 1)

( )( 1) 1

, 0,1,2,!

i i

i i i

i

i

i

ALBE

i i

Ai

i

+

+

π λ = π + μ

λπ = π = π

+ μ +

π = π = …

( )

00 0

1

1

00

1 ( )!

!

!

i

ii i

iA A

i

iA

i

AN

i

Ae e

i

Ae

i

∞ ∞

= =−∞

− −

=

π = π =

⎛ ⎞⎜ ⎟⇒ π = = =⎜ ⎟⎝ ⎠

⇒ π =

∑ ∑

Probabilitatea de stare (2)

• Probabilitatea de stare respecta o distributie de tip Poisson:

• Observatie: PROBABILITATEA DE STARE nu depinde de distributia timpul de servire

– inseamna ca e valida pentru orice distributie a timpilor de servire de medie

– Aceasta inseamna ca in locul modelului putem considera unul maigeneral / /M G ∞

2

( )

{ } , 0,1,2,!

[ ] , [ ]

iA

i

X Poisson A

AP X i e i

i

E X A D X A

−= = π = =

= =

1/ μ/ /M M ∞

Page 5: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Aplicatie: modelarea traficului de date la nivel de flux

• Modelul Poisson poate fi aplicat pentru modelarea traficului de date la nivel de flux

– Clientul: fluxul UDP cu rata constanta a bitilor (CBR)

– = rata de sosire a fluxului(numarul de fluxuri pe unitatea de timp)

– = durata medie a fluxului (unitati de timp)

– = intensitatea traficului

– r = rata bitilor in cadrul unui flux (unitati de date pe unitati de timp)

- N = numarul de fluxuri din sistem• Cand rata totala de transmisie depaseste capacitatea liniei

se pierd biti

– Raportul de pierdere da raportul intre traficul pierdut si cel oferit:

/A = λ μ

λ

1

[( ) ] [( ) ] 1( )

[ ] [ ] !

iA

lossi n

E Nr C E N n Ai n e

E Nr E N A i

∞+ +−

= +

− −ρ = = = −∑

1/h = μ

lossρ

C nr=Nr

Multiplexing gain

• Se determina in cele ce urmeaza valoarea traficului A astfel incat

• Multiplexing gain este data de intensitatea traficului pe unitatea de capacitate

(trafic normalizat) ca functie de capacitatea n.

1%lossρ </A n

Page 6: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Modelul Erlang

• Definitie: Modelul ERLANG reprezinta urmatorul model simplu de trafic:

– Infinit numar de clienti independenti:

– Timpii intersosiri sunt variabile IID si au o distributie exponentiala de medie:

• Deci clientii sosesc potrivit unui proces Poisson de intensitate

– Numar finit de servere:

– Timpii de servire sunt variabile IID distribuite exponential de medie

– Nu exista pozitii de asteptare:

• Modelul Erlang:

– Utilizand notatia Kendall acesta este o coada de asteptare de tipul

– Sistem cu pierderi pur

• Notatii:

– = intensitatea traficului

1/ μ

k = ∞

/ / /M M n n

1/ λ

n < ∞

λ

0m =

/ / /M M n n

/A = λ μ

Diagrama tanzitiilor de stare

• Fie numarul de clienti in sistem la momentul t

– Sa presupunem ca la un anumit moment de timp t si

sa consideram ce se intampla pe un interval scurt de timp

• Poate sosi un nou client cu probabilitatea ceea ce determina o tranzitie

• Daca , atunci cu probabilitatea un client poate parasisistemul ceea ce determina o tranzitie:

• Procesul este in mod clar un proces Markov cu urmatoarea diagrama a tranzitiilor:

• Procesul este un proces de nastere si moarte ireductibil cu un spatiu al

starilor finit

1i i→ +

( )X t

{0,1,2, , }S n= …

( )h o hλ +( , ]t t h+

0i > ( )i h o hμ +

( )X t i=

1i i→ −

( )X t

( )X t

Page 7: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Probabilitatea de stare (1)

• Ecuatiile echilibrelor locale (LBE)

• Relatia de normare:

1

1

0

( 1)

( )( 1) 1

, 0,1,2, ,!

i i

i i i

i

i

i

ALBE

i i

Ai n

i

+

+

π λ = π + μ

λπ = π = π

+ μ +

π = π = …

00 0

1

00

1 ( )!

!

n ni

ii i

ni

i

AN

i

A

i

= =−

=

π = π =

⎛ ⎞⎜ ⎟⇒ π =⎜ ⎟⎝ ⎠

∑ ∑

Probabilitatea de stare (2)

• Probabilitatea de stare respecta o distributie de tip Poisson trunchiata:

• Observatie: PROBABILITATEA DE STARE nu depinde de distributia timpului de servire

– inseamna ca e valida pentru orice distributie a timpilor de servire de medie

– Aceasta inseamna ca in locul modelului putem considera unul

mai general / /M G ∞

0

2

!{ } , 0,1,2,

!

[ ] , [ ]

i

i nj

j

AiP X i iAj

E X A D X A

=

= = π = =

= =

1/ μ

/ /M M ∞

Page 8: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Formula Erlang -A

Face posibila calcularea probabilitatii de ocupare succesiva a i resurse dintr-un grupde n resurse , caruia i se ofera traficul A de natura Poissoniana.

Formula Erlang-A

Aplicatie: Se calculeaza succesiv probabilitatea de a avea ocupate 0,1,2,……n elemente pastrand de fiecare data acelasi volum de trafic oferit A (=5)

0

!{ } , 0,1,2, ,

!

i

i nj

j

AiP X i i nAj=

= = π = =

Formula Erlang –A- Modelul de trafic Erlang- sau PCT1(Pure chance traffic..)

0

!{ } , 0,1,2, ,

!

i

i nj

j

AiP X i i nAj=

= = π = =

0,018384510

0,0567699

0,06618438

0,1058957

0,1482536

0,17790575

0,17790574

0,1423253

0,08539382

0,05415751

0,00683150

i

Page 9: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Formula Erlang -A

• Aplicatie: Acelasi volum de trafic (A=5) este oferit unor sisteme de numai 4 respectiv 5 resurse

• Situatiile de prelucrare cu A/n>1

• Duc la un volum important de trafic pierdut:

• 39,8% pt n=4 si 28,48% pt i=5

• In cazul n=10 traficul pierdut era de 1,8%

E(n,A)=

0,28483

5

0,28483E(n,A)=

0,39816

4

0,227850,318493

0,136730,191122

0,054690,076451

0,010930,015290

n=5n=4

Capac sistemului

Stareagrupului

de resurse

Blocarea de timp

• Blocarea de timp proabilitatea ca toate cele n servere sa fie ocupate la un moment de timp arbitrar = fractiunea de timp cat cele n servere sunt ocupate.

• Pentru un proces stationar Markov aceasta e data de probabilitatea starii n a sistemului ( probabilitatea ca sistemul sa se afle in starea n):

tB

0

!: { }

!

n

t n nj

j

AnB P X nAj=

= = = π =

Page 10: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Blocarea de apel

• Blocarea de apel = este proabilitatea ca un nou client care soseste sa gaseascatoate cele n servere ocupate = fractiunea de clienti care sosesc si sunt pierduti.

• Totusi datorita sosirilor de tip Poisson si proprietatii PASTA probabilitatea ca un client care soseste sa gaseasca toate cele n servere ocupate este egala cu probabilitateaca toate cele n servere sa fie ocupate la un moment dat de timp,

• Altfel spus, blocarea de apel este egala cu blocarea de timp:

• Aceasta reprezinta formula de blocarea Erlang sau formula Erlang B.

cB

0

!

!

n

C t nj

j

AnB BAj=

= =

Formula Erlang-B

Relatii de calcul iterativ:

• Unde 1( , )c nB E n A=

1

1 1

(0, ) 1

1 11

( , ) ( 1, )

E A

k

E k A A E k A

=

= +−

Page 11: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Formula Erlang-B

Numarul mediu de cereri prezente in sistem masoara de fapt traficul scursde sistemul de prelucrare si se calculeaza cu:

• Atat traficul scurs cat si cel pierdut nu mai au caracter Poissonian

00 0

1

1

!

(1 ( , ))

( , )

[...]

[...]

n nk

kk k

AB n k k

k

B A E n A

C AE n A

VarZ factor de iregularitate

E

= == = π = π

= −=

=

∑ ∑

2,180,6171Factor de iregularitate

2,085,279,5varianta

0,968,549,5medie

Trafic pierdutTrafic scursTrafic oferit

Page 12: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Aplicatie: modelarea traficului telefonic in trunchiul de retea

• Modelul Erlang poate fi aplicat pentru modelarea traficului telefonic intr-un trunchide retea unde numarul potentialilor utilizator este mare.

– Clientul: apelul

– = rata de sosire a apelului (apeluri pe unitatea de timp)

– = durata medie de mentinere a apelului (unitati de timp)

– = intensitatea traficului

– n = capacitatea liniei (numarul de canale)

• Un apel este pierdut cand toate cele n canale sunt ocupate cand soseste un nouapel.

– Blocarea de apel da probabilitatea unui astfel de eveniment

/A = λ μ

λ1/h = μ

0

!

!

n

c nj

j

AnBAj=

=

Multiplexing gain

• Se determina in cele ce urmeaza valoarea traficului A astfel incat

• Multiplexing gain este data de intensitatea traficului pe unitatea de capacitate

(trafic normalizat) ca functie de capacitatea n.

1%cB </A n

Page 13: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Modelul Binomial

• Definitie: Modelul binomial reprezinta urmatorul model simplu de trafic:

– Numar finit de clienti independenti:

• Clienti de tip on-off( altermand intre activitate si inactivitate)

– Timpii de inactivitate sunt variabile IID si au o distributie exponentiala de medie:

– Numarul de servere este egal cu numarul de clienti :

– Timpii de servire sunt variabile IID distribuite exponential de medie

– Nu exista pozitii de asteptare:

• Modelul Binomial :

– Utilizand notatia Kendall acesta este o coada de asteptare de tipul:

– deasemena un sistem finit fara pierderi (lossless)

• Tipul de client on-off:

1/ μ

k < ∞

/ / / /M M k k k

n k=1/ υ

0m =

/ / / /M M k k k

• Un observator plasat la intrarea sistemului vede ca rata de sosire a cererilor de la grupul celor k surse scade pe masura ce creste numarul cererilor in curs de prelucrare. La limita daca sistemul este ocupat cu prelucrarea unui numar k de apeluri simultane inseamna ca toate sursele sunt in sarcina si nu mai soseste nici o cerere noua. Deci rata globala λ a grupului surselor este o functie de numarul de cereri de serviciu, adica de starea sistemului.

• Totusi fiecare sursa are o rata de emisie proprie, care este constanta siindependenta de starea mediului inconjurator. Acest parametru notat poate fidefinit si ca rata medie de emisie a unei cereri individuale de serviciu. Inseamna ca

reprezinta durata medie de stationare a unitatii cerere in sursa de cereri.

υ

1/ υ

( )n

n

k n

n

λ = − υ

μ = μ

Page 14: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Tipul de client on-off (1)

• Fie variabila care reprezinta starea clientului j ( ) la momentul t

– Starea 0 = inactiv, starea 1 = activ = in servire

– Consideram ceea ce se intampla pe un interval scurt de timp :

• Daca , atunci cu probabilitatea

clientul poate deveni activ ceea ce determina o tranzitie

• Daca , atunci cu probabilitatea

clientul devine inactiv ceea ce determina o tranzitie:

• Procesul este in mod clar un proces Markov cu urmatoarea diagrama a tranzitiilor:

• De notat ca procesul este un proces de nastere si moarte ireductibil cu un spatiu al starilor finit

1 0→

( )jX t {0,1,2, , }j k= …

( )h o hυ +( , ]t t h+

( ) 0jX t =

( )h o hμ +0 1→

( ) 1jX t =

( )jX t

( )jX t

{0,1}S =

Tipul de client on-off (2)

• Ecuatiile echilibrelor locale (LBE)

• Relatia de normare (N):

• Probabilitatea de stare a unui singur client respecta o distributie Bernoulli cu probabilitatea succesului

– Traficul oferit este

• Putem deduce de aici ca probabilitatea de stare a intregului sistem respecta o distributie binomiala

/ ( )υ υ+μ

( ) ( ) ( ) ( )0 1 1 0

j j j jυπ υ = π μ ⇒ π = π

μ

0 1 0 0 1(1 ) 1 ,j j j j jυ μ υπ + π = π + = ⇒ π = π =

μ υ+μ υ+μ

/ ( )υ υ+ μ

( , / ( ))Bin k υ υ+μ

Page 15: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

!( ) (1 ) ,

!( )!

1

i i n i in n

nP X i C p p C

i n i

p

p

−= = − =−

ν=ν + μ

μ− =

ν + μ

( , ); ( , / ( ))Bin n p Bin k υ υ+μ

Diagrama tanzitiilor de stare

• Fie numarul de clienti activi in sistem

– Sa presupunem ca la un anumit moment de timp t si

sa consideram ce se intampla pe un interval scurt de timp

• Daca atunci cu probabilitatea un client inactiv poate devine activ ceea ce determina o tranzitie

• Daca , atunci cu probabilitatea un client activ poatedeveni inactiv, ceea ce determina o tranzitie:

• Procesul este in mod clar un proces Markov cu urmatoarea diagrama a tranzitiilor:

• Procesul este un proces de nastere si moarte ireductibil cu un spatiu al starilor finit

1i i→ +

( )X t

{0,1,2, , }S k= …

( ) ( )k i h o h− υ +( , ]t t h+

0i > ( )i h o hμ +

( )X t i=

1i i→ −

( )X t

i k<

( )X t

Page 16: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Probabilitatea de stare (1)

• Ecuatiile echilibrelor locale (LBE)

• Relatia de normare:

1

1

0 0

( ) ( 1)

( )( )

( 1)

!0,1,2, ,

!( )!

i i

i i

i ii

i k

k i i

k iLBE

i

kC i k

i k i

+

+

π − υ = π + μ

− υπ = π

+ μ

υ υ⎛ ⎞ ⎛ ⎞π = π = π =⎜ ⎟ ⎜ ⎟− μ μ⎝ ⎠ ⎝ ⎠

00 0

1

00

1 ( )

1

k k ii

i ki i

k i k kik

i

C N

C

= =−

=

υ⎛ ⎞π = π =⎜ ⎟μ⎝ ⎠

⎛ ⎞υ υ μ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟⇒ π = = + =⎜ ⎟ ⎜ ⎟ ⎜ ⎟⎜ ⎟μ μ υ+μ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

⎝ ⎠

∑ ∑

Probabilitatea de stare (2)

• Probabilitatea de stare respecta o distributie de tip Binomiala:

• Observatie: PROBABILITATEA DE STARE nu depinde de distributia timpul de servire

– inseamna ca e valida pentru orice distributie a timpiloe de servire de medie

– Aceasta inseamna ca in locul modelului putem considera unulmai general / /M G ∞

( )22

( , ) ( , )

{ } ,

0,1, ,

[ ] ( ) , [ ] (1 )( )

i k i k ii i

i k k

X Bin k vezi Bin n p

P X i C C

i k

k kE X np D X np p k

υυ+μ

υ μ υ μ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞= = π = =⎜ ⎟ ⎜ ⎟ ⎜ ⎟ ⎜ ⎟μ υ+μ υ+μ υ+μ⎝ ⎠ ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

=

υ υ μ υμ= = = − = =

υ+μ υ+μ υ+μ υ+μ

1/ μ

/ /M M ∞

Page 17: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Modelul Engset

• Definitie: Modelul Engset reprezinta urmatorul model simplu de trafic:

– numar finit de clienti independenti:

• Clienti de tip on-off( altermand intre activitate si inactivitate)

– Timpii de inactivitate sunt variabile IID si au o distributie exponentiala de medie:

– Numarul de servere este mai mic decat numarul de clienti :

– Timpii de servire sunt variabile IID distribuite exponential de medie

– Nu exista pozitii de asteptare:

• Modelul Engset:

– Utilizand notatia Kendall acesta este un sistem de tipul

– Sistem cu pierderi pur

• Tipul de client on-off:

• Daca sist e plin cand un client inactiv incearca sa devina activ, starteaza o nouaperioada de inactivitate

1/ μ

k < ∞

/ / / /M M n n k

n k<1/ υ

0m =

/ / / /M M n n k

Diagrama tanzitiilor de stare

• Fie numarul de clienti activi in sistem

– Sa presupunem ca la un anumit moment de timp t si

sa consideram ce se intampla pe un interval scurt de timp

• Daca atunci cu probabilitatea un client inactiv poate devine activ ceea ce determina o tranzitie

• Daca , atunci cu probabilitatea un client activ poatedeveni inactiv ceea ce determina o tranzitie:

• Procesul este in mod clar un proces Markov cu urmatoarea diagrama a tranzitiilor:

• Procesul este un proces de nastere si moarte ireductibil cu un spatiu al starilor finit

1i i→ +

( )X t

{0,1,2, , }S n= …

( ) ( )k i h o h− υ +( , ]t t h+

0i > ( )i h o hμ +

( )X t i=

1i i→ −

( )X t

i n<

( )X t

Page 18: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Probabilitatea de stare (1)

• Ecuatiile echilibrelor locale (LBE)

• Relatia de normare:

1

1

0 0

( ) ( 1)

( )( )

( 1)

!0,1,2, ,

!( )!

i i

i i

i ii

i k

k i i

k iLBE

i

kC i n

i k i

+

+

π − υ = π + μ

− υπ = π

+ μ

υ υ⎛ ⎞ ⎛ ⎞π = π = π =⎜ ⎟ ⎜ ⎟− μ μ⎝ ⎠ ⎝ ⎠

00 0

1

00

1 ( )

n n ii

i ki i

n iik

i

C N

C

= =−

=

υ⎛ ⎞π = π =⎜ ⎟μ⎝ ⎠

⎛ ⎞υ⎛ ⎞⎜ ⎟⇒ π = ⎜ ⎟⎜ ⎟μ⎝ ⎠

⎝ ⎠

∑ ∑

Probabilitatea de stare (2)

• Probabilitatea de stare respecta o distributie de tip Binomiala trunchiata:

• Observatie: traficul oferit este

• PROBABILITATEA DE STARE nu depinde de distributia timpul de servire si a timpilor de inactivitate

– inseamna ca e valida pentru orice distributie a timpilor de servire de medie

– Si orice distributie a timpilor de inactivitate

– Aceasta inseamna ca in locul modelului putem considera unulmai general / / / /G G n n k

{ } , 0,1, ,

i i k iik

ii k n nj j k j

j jk k

j o j o

C

P X i C i n

C C

= =

υ υ μ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟μ υ+μ υ+μ⎝ ⎠ ⎝ ⎠ ⎝ ⎠= = π = = =

υ υ μ⎛ ⎞ ⎛ ⎞ ⎛ ⎞⎜ ⎟ ⎜ ⎟ ⎜ ⎟μ υ+μ υ+μ⎝ ⎠ ⎝ ⎠ ⎝ ⎠

∑ ∑

/ ( )kυ υ+μ

/ / / /M M n n k

1/ μ1/ υ

Page 19: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Blocarea de timp

• Blocarea de timp = proabilitatea ca toate cele n servere sa fie ocupate la un moment de timp arbitrar = fractiunea de timp cat cele n servere sunt ocupate.

• Pentru un proces stationar Markov aceasta e data de probabilitatea starii n a sistemului ( probabilitatea ca sistemul sa se afle in starea n):

tB

0

: { }

nnk

t n n jj

kj

C

B P X n

C=

υ⎛ ⎞⎜ ⎟μ⎝ ⎠= = = π =

υ⎛ ⎞⎜ ⎟μ⎝ ⎠

Blocarea de apel (1)

• Blocarea de apel este probabilitatea ca un nou client care soseste sa gaseasca toate cele n servere ocupate = fractiunea de clienti care sosesc si sunt pierduti.– In cadrul modelului Engset sosirile nu reprezinta un proces Poisson si

ca atare nu se poate aplica proprietatea PASTA .

– probabilitate de stare pe care un client care soseste o vede difera de cea de echilibru statistic. Altfel spus, blocarea de apel nu este egalacu blocarea de timp in cadrul modelului Engset.

cB

0

!

!

n

C t nj

j

AnB BAj=

⎛ ⎞⎜ ⎟⎜ ⎟

= =⎜ ⎟⎜ ⎟⎜ ⎟⎜ ⎟⎝ ⎠

Page 20: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Blocarea de apel (2)

• Fie probabilitatea de a avea i clienti activi in sistem cand un client inactivdevine activ ( ceea ce numim o sosire)

• Consideram un interval lung de timp– Pe durata acestui interval timpul mediu petrecut in starea i este

– Pe durata acestui interval numarul mediu de clienti care sosesc ( care vad totisistemul in starea i ) este

– Pe durata intregului interval, numarul mediu de clienti care sosesc este

• Astfel:

*iπ

( ) jj k j T− υπ∑

i Tπ

( ) ik i T− υπ

(0, )T

*

0 0

( ) ( ), 0,1, ,

( ) ( )

i ii n n

j jj j

k i T k ii n

k j T k j= =

− υπ − ππ = = =

− υπ − π∑ ∑

Blocarea de apel (3)

• Se poate demonstra ca:

• Daca exprimam explicit dependenta acestor probabilitati de numarul total de consumatori gasim:

• Altfel spus un client care soseste vede un sistem in echilibru statistic in care exista cu un client mai putin.

*( ) ( 1), 0,1, ,i ik k i nπ = π − = …

1*

10

0,1, ,

iik

i n jj

kj

C

i n

C

−=

υ⎛ ⎞⎜ ⎟μ⎝ ⎠π = =

υ⎛ ⎞⎜ ⎟μ⎝ ⎠

Page 21: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Blocarea de apel (2)

• Alegand obtinem urmatoarea formula pentru probabilitatea de apel:

• Astfel, pentru Modelul Engset blocarea de apel intr-un sistem cu k consumatoriegaleaza blocarea de timp dintr-un sistem cu consumatori:

• Aceasta este formula de blocare Engset

i n=

1k −

*( ) ( ) ( 1) ( 1)c n n tB k k k B k= π = π − = −

1

10

( )( ) ( 1)

( )

n nk

c t n

j jk

j

CB k B k

C

−=

υμ= − =υμ∑

Aplicatie: modelarea traficului telefonic in retelele de acces

• Modelul Engset poate fi aplicat pentru modelarea traficului telefonic in retelele de acces in care numarul de potentiali utilizatori ai unei legaturi este moderat

– Clientul: apelul

– = rata de sosire a apelului per utilizator inactiv (apeluri pe unitateade timp)

– = timpul mediu de mentinere a apelului (unitati de timp)

– = numarul de potentiali utilizatori

– n = capacitatea liniei ( canalele)

• Un apel este pierdut cand toate cele n canale sunt ocupate cand soseste apelul

– Blocarea de apel da probabilitatea unui astfel de eveniment

1/ μ

υ

1

10

nnk

c n jj

kj

C

B

C

−=

υ⎛ ⎞⎜ ⎟μ⎝ ⎠=

υ⎛ ⎞⎜ ⎟μ⎝ ⎠

cB

k

Page 22: Recapitulare: modelul simplu de trafic ∞ ∞ · Sisteme cu pierderi - continut • Recapitulare: modelul simplu de trafic • Modelul Poisson ( numar de clienti, numar de servere

Multiplexing gain

• Se presupune ca o linie de acces este incarcata de de potentialiutilizatori

• Se determina in cele ce urmeaza intensitatea traficului astfel incat

• Multiplexing gain este data de intensitatea traficului pe unitatea de capacitate

(trafic normalizat) ca functie de capacitatea n.

1%cB </ ( )kυ υ+μ

100k =

/ ( ( ))k nυ υ+μ