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+

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 rezultate

aproximative 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 sosirii unui 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 < ∞

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 determina

o tranzitie • Daca , atunci cu probabilitatea un client poate

parasi 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

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 A LBE

i i

A i i

+

+

π λ = π + μ

λ π = π = π

+ μ +

π = π = …

( )

0 0 0

1 1

0 0

1 ( ) !

!

!

i

i i i

i A A

i

i A

i

A N i

A e e i

A e 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 mai

general / /M G ∞

2

( )

{ } , 0,1,2, !

[ ] , [ ]

i A

i

X Poisson A

AP X i e i i

E X A D X A

−= = π = =

= =

∼

…

1/ μ / /M M ∞

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 ( ) [ ] [ ] !

i A

loss i 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

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 parasi

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 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

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 A LBE

i i

A i n i

+

+

π λ = π + μ

λ π = π = π

+ μ +

π = π = …

0 0 0

1

0 0

1 ( ) !

!

n n i

i i i

n i

i

A N 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 n j

j

A iP X i i A j

E X A D X A

=

= = π = =

= =

∑

…

1/ μ

/ /M M ∞

Formula Erlang -A

Face posibila calcularea probabilitatii de ocupare succesiva a i resurse dintr-un grup de 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