Retele cu cozi în serie

Retelele Jackson se bazeaza pe procese de nastere si moarte multidimensionale, care extind pe cele unidimensionale prezentate în paragraful 4.8.

Pentru prezentarea modelului, consideram o retea de calculatoare cu doua noduri de retea legate în serie ca în figura 5.5 în care tranzactiile sosite la coada nodului 1, dupa un flux Poisson cu rata λ, asteapta sa fie prelucrate de serverul nodului 1.

Fig. 5.5

Dupa prelucrarea unei tranzactii de acest server, ea trece la coada nodului 2 unde asteapta sa fie prelucrata de serverul acestui nod, timp în care serverul 1 selecteaza o noua tranzactie din coada sa pentru prelucrare, conform disciplinei aleasa pentru coada. Conform teoremei lui BURKE sosirile la coada nodului 2 sunt tot Poissoniene de parametru λ + μ₁, unde μ₁ este rata prelucrarii serverului 1.

În cele ce urmeaza vom nota cu:

λ rata sosirii tranzactiilor în retea.

μ_i, rata prelucrarii în nodul i (de catre serveul i)

Q_i(τ) = numarul tranzactiilor din nodul i de retea la momentul τ, .

Urmarim sa determinam probabilitatea ca la momentul τ sa avem n₁ tranzactii în nodul 1 si n₂ tranzactii în nodul 2, adica:

P(n₁,n₂,τ) = P(Q₁(τ) = n₁ Q₂(τ) = n₂).

Pentru aceasta vom calcula succesiv urmatoarele probabilitati:

P(0,0,τ + Δτ) = probabilitatea de a nu avea tranzactii la nici un nod la momentul τ+Δτ.

P(0,n₂,τ + Δτ) = probabilitatea de a avea doar în nodul 2, n₂ tranzactii la momentul τ+Δτ.

P(n₁,0,τ + Δτ) = probabilitatea de a avea doar în nodul 1, n₁ tranzactii la momentul τ+Δτ.

P(n₁,n₂,τ + Δτ) = probabilitatea de a avea n₁ tranzactii în nodul 1 si n₂ tranzactii în nodul 2 la momentul τ+Δτ.

Evident:

P(0,0,τ + Δτ) = P(0,0,τ) ·(1- λΔτ) + P(0,1,τ)μ₂ ·Δτ · (1- λΔτ) + 0(Δτ)

P(0,0,τ + Δτ) = P(0,0,τ) - λP(0,0,τ)Δτ + μ₂P(0,1,τ)Δτ + 0(Δτ)

Trecând la limita dupa Δ τ 0 obtinem:

P( 0,n₂,τ + Δτ) = P(0,n₂,τ)[1- λΔτ)[1- μ₂Δτ] + P(1,n₂ -1,τ)·μ₁Δτ[1- λΔτ)[1-μ₂Δτ]+

+P(0,n₂ +1,τ)·μ₂Δτ[1-λΔτ) + 0(Δτ) =

= -(μ₂ + λ)P(0,n₂,τ)+ μ₁P(1,n₂ - 1,τ) + μ₂P(0,n₂ + 1,τ)+

Trecând la limita dupa Δτ 0 obtinem:

P(0,n₂,τ) = -(λ + μ₂)P(0,n₂,τ) + μ₁P(1,n₂-1,τ) + μ₂P(0,n₂ +1,τ)

Analog

P(n₁,0,τ + Δτ) = P(n₁,0,τ)[1 - λΔτ)[1 - μ₁Δτ] + P(n₁ - 1,0,τ) ·

· λΔτ[1 - μ₁Δτ] + P(n₁,1,τ) · μ₂Δτ[1- λΔτ)[1 - μ₁Δτ] + 0(Δτ)

= -(μ₁ + λ)P(n₁,0,τ) + λP(n₁-1,0,τ) + μ₂P(n₁,1,τ)+

Astfel:

P(n₁,0,τ) = -(λ + μ₁)P(n₁,0,τ) + λP(n₁-1,0,τ) + μ₂P(n₁,1,τ)

În sfârsit:

P(n₁,n₂,τ + Δτ) = P(n₁,n₂,τ)[1 - λΔτ)[1 - μ₁Δτ][1 - μ₂Δτ] +

+ P(n₁ - 1,n₂,τ)·λΔτ·[1 - μ₁Δτ][1 - μ₂Δτ] +

+ P(n₁,n₂ +1,τ)·[1 - λΔτ)[1 - μ₁Δτ] μ₂Δτ +

+P(n₁ +1,n₂ -1,τ)·[1 λΔτ) ·μ₁Δτ·(1 - μ₂Δτ) + 0(Δτ)

-(μ₁ + μ₂ + λ)·P(n₁,n₂,τ)+λP(n₁-1,n₂,τ)+

+ μ₂·P(n₁,n₂ +1,τ) + μ₁P(n₁+1,n₂ -1,τ)+

Trecând la limita dupa Δ τ 0 obtinem:

P(n₁,n₂ +1,τ) = -(λ + μ₁ + μ₂)·P(n₁,n₂,τ) + λP(n₁ -1,n₂,τ) +

+ μ₁P(n₁ +1,n₂ -2,τ) + μ₂·P(n₁,n₂ +1,τ)

În concluzie, pentru modelul de retea de calculatoare cu cozi în serie, se obtine urmatorul sistem de ecuatii diferentiale:

În cazul general, acest sistem este extrem de dificil de rezolvat. În cazul echilibrului asimptotic stabil se stie ca pentru orice n₁,n₂ 0 exista

.

Distributia de probabilitate p(n₁,n₂) a starii de echilibru asimptotic stabil, furnizeaza o descriere a comportarii medii a retelei de calculatoare pe termen lung. În aceasta conditie sistemul de mai sus devine:

Vom considera

p(n₁,n₂) = 0, "n₁ < 0 sau "n₂ < 0

μ₁p(0,n₂) = 0

μ₂p(n₁,0) = 0.

relatii care sunt firesti daca ne gândim la interpretarea lor.

Astfel μ₁p(0,n₂) este probabilitatea prelucrarii unei tranzactii în nodul 1, dar în acest nod nu avem tranzactii si astfel μ₁p(0,n₂) = 0. Analog μ₂p(n₁,0) = 0.

În aceste ipoteze, sistemul de ecuatii corespunzatoare starii de echilibru asimptotic stabil, se reduce la o singura ecuatie si anume:

λp(n₁ -1,n₂) + μ₁p(n₁ +1,n₂ -1) + μ₂p(n₁,n₂ +1) = (λ + μ₁ + μ₂)p(n₁,n₂)

Din aceasta relatie deducem ca în caz de echilibru asimptotic stabil, fluxul fiecarei stari se conserva, adica pentru fiecare stare, fluxul de intrare coincide cu fluxul de iesire din aceasta stare.

La aceasta relatie se adauga relatia evidenta

Daca notam cu starea retelei corespunzatoare cazului în care în nodul 1 exista n₁ tranzactii si în nodul 2 exista n₂ tranzactii, din relatia de mai sus observam ca starile la care si de la care avem tranzactii în starea sunt:

ca intrari ale starii

ca iesiri pentru .

Interactiunea dintre aceste stari este data prin diagrama din figura 5.6

Fig 5.6

Întrucât în orice sistem în echilibru stabil, rata fluxului de intrare într-o stare este aceeasi cu rata fluxului de iesire din acea stare, si aceasta pentru fiecare stare a sistemului, rezulta ca în cazul nostru scriind aceasta relatie de conservare a fluxului pentru starea , obtinem:

Rata fluxului de intrare pentru = λp(n₁-1,n₂)+μ₁p(n₁+1,n₂)+μ₂p(n₁,n₂+1).

Rata fluxului de iesire din = (λ + μ₁ + μ₂) · p(n₁,n₂).

Din conditia de conservare a fluxului în obtinem relatia:

λp(n₁-1,n₂) + μ₁p(n₁ + 1,n₂) + μ₂ · p(n₁,n₂ + 1) = (λ + μ₁ + μ₂) · p(n_1, n₂)

care este chiar relatia echivalenta cu sistemul probabilitatilor în caz de echilibru asimptotic stabil.

Observam ca daca asezam într-o retea rectangulara n₁On₂, starile vecine lui , atunci fiecare rata de flux are câte o directie bine precizata si anume: de la stânga la dreapta ↓ μ₂ de sus în jos si μ₁ directia SE-NV.

Întrucât în reteaua de calculatoare cu cozi în serie considerata, cele doua noduri de retea sunt independente, Jackson vine cu ideea de a cauta solutia sistemului corespunzator starii de echilibru asimptotic stabil sub forma unui produs, adica p(n₁,n₂)=p₁(n₁)·p₂(n₂), unde p_i(n_i) reprezinta probabilitatea de a avea în nodul i, n_i tranzactii în starea de echilibru asimptotic stabil si astfel încât:

Cu aceasta alegere ecuatia de mai sus devine:

μ₁p₁(n₁ + 1) p₂(n₂ - 1) + λp₁(n₁ - 1) p₂(n₂) + μ₂p₁(n₁) p₂(n₂ +1)=

= (λ + μ₁ + μ₂ ) · p₁(n₁)p₂(n₂). (1)

Pentru n₁ = n₂ = 0 si folosind ipotezele de mai sus obtinem ecuatia:

μ₁p₁(1)p₂(-1) + λp₁(-1)p₂(0) + μ₂p₁(0)p₂(1) = (λ + μ₁ + μ₂) · p₁(0)p₂(0)

μ₂p₁(0)p₂(1) = λp₁(0)p₂(0) p₁(0)[μ₂p₂(1) - λp₂(0)] = 0.

Cazul 1. Daca p₁(0) = 0 luând în relatia (1) de mai sus n₁ = 0 obtinem:

μ₁p₁(1)p₂(n₂ - 1) + λp₁(-1)p₂(n₂) + μ₂p₁(0)p₂(n₂ + 1) = (λ + μ₁ + μ₂) · p₁(0)p₂(n₂)

Folosind ipotezele de mai sus si p₁(0) = 0 obtinem:

μ₁p₁(1) · p₂(n₂-1) = 0

Daca p₁(1) = 0 se demonstreaza ca p₁(n₁) = 0 pentru oricare n ≥ 0.

Daca p₂(n₂ - 1) = 0 rezulta ca p₂(n₂) = 0 pentru orice n₂ > 0.

Ambele situatii sunt false.

Cazul 2. Daca μ₂p₂ (1) - λp₂(0) = 0 p(1) = p₂(0). (2)

Cu aceasta valoare venim în relatia (1) dupa care facem n₂ = 0.

Avem:

μ₁p₁(n₁ + 1)p₂(-1) + λp₁(n₁ - 1)p₂(0) + μ₂p₁(n₁)p₂(1) =

= (λ + μ₁ + μ₂) · p₁(n₁)p₂(0)

Rezulta:

λp₁(n₁ - 1)p₂(0) + μ₂p₁(n₁)p₂(1) = (λ + μ₁) · p₁(n₁)p₂(0)

Înlocuind p₂(1) cu valoarea sa din relatia (2) obtinem:

p₂(0)[λp₁(n₁ - 1) - (λ + μ₁) · p₁(n₁)] + μ₂p₁(n₁) ·p₂(0) = 0.

p₂(0)[λp₁(n₁ - 1) - μp₁(n₁)] = 0.

Daca p₂(0) = 0 se arata ca mai sus ca se obtin valori nule pentru p₁ si p₂, ceea ce este fals.

Rezulta deci ca p₁(n₁) =p₁(n₁ - 1) pentru orice n₁ ≥ 0.

Scriind aceasta relatie sub forma = , k ≥ 1 si efectuând produsul =obtinem si deci

Din relatia ,

daca< 1, pentru ca seria sa fie convergenta.

Notam cu ρ_{1 =} si numim ρ₁ factor de utilizare în nodul de retea 1.

Deci pentru ρ₁ (0,1) avem p₁(n) = (1 - ρ₁)ρ₁ⁿ_, n ≥ 0, (3)

Folosim acest rezultat în relatia (1) dupa care facem n₁ = 0.

Obtinem:

μ₁p₁(1)p₂(n₂ - 1) + λp₁(-1)p₂(n₂) + μ₂p₁(0)p₂(n₂ + 1) = (λ + μ₁ + μ₂) · p₁(0)p₂(n₂).

Din ipoteze rezulta:

μ₁p₁(1)p₂(n₂ - 1) + μ₂p1(0)p₂(n₂ + 1) - (λ + μ₂) · p₁(0)p₂(n₂) = 0

Înlocuind p₁ cu valoarea gasita obtinem:

μ₁·p₁(0)p₂(n₂ - 1) + μ₂p₁(0)p₂(n₂ + 1) - (λ + μ₂) · p₁(0)p₂(n₂) = 0

p₁(0)[λp₂(n₂ - 1) + μ₂p₂(n₂ + 1) - (λ + μ₂)] =0

Am vazut mai sus ca p₁(0) 0 si astfel:

λ[p₂(n₂ - 1) - p₂(n₂)] = μ₂[p₂(n₂) - p₂(n₂ + 1)], n₂ ≥ 1.

Scriind aceasta relatie sub forma:

λ[p₂(k -1) - p₂(k)] = μ₂[p₂(k) - p₂(k + 1)], k ≥ 1 si sumând dupa k de la 1 la n₂ obtinem:

,

relatie echivalenta cu:

λ[p₂(0) - p₂(n₂)] = μ₂[p₂(1) - p₂(n₂ + 1)]

Dar din (2) p₂(1) = p₂(0). Înlocuind aceasta mai sus obtinem:

p₂(n₂ + 1) = p₂(n₂)

Procedând ca mai sus obtinem succesiv:

Din

daca < 1 pentru ca seria sa fie convergenta.

Notam cu si numim ρ₂ factor de utilizare în nodul 2.

Astfel pentru ρ₂(0,1) obtinem:

, (4)

Din relatiile (3), (4) si din p(n₁, n₂) = p₁(n₁) · p₂(n₂) obtinem solutia starii de echilibru asimptotic stabil a modelului ca fiind:

unde .

Rezultatul obtinut pentru o retea de calculatoare cu doua noduri de retea în serie, se poate generaliza la cazul a N noduri de retea legate în serie.

Daca reteaua de calculatoare Σ contine N noduri de retea legate în serie, vom nota cu starea retelei corespunzatoare cazului în care pentru în nodul de retea i existau n_i tranzactii.

De asemenea notam cu p(n₁,n₂,.n_N) =, probabilitatea ca reteaua sa fie în starea .