Recapitulare: modelul simplu de trafic ∞ ∞ · PDF fileSisteme cu pierderi -...

Click here to load reader

  • date post

    05-Oct-2019
  • Category

    Documents

  • view

    8
  • download

    0

Embed Size (px)

Transcript of Recapitulare: modelul simplu de trafic ∞ ∞ · PDF fileSisteme cu pierderi -...

  • 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