Példák kidolgozása

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

%TOC{depth="2"}%

Lásd még: elméleti kérdések kidolgozása

Réselt adatcsatorna

2005.01.06/B, 1. feladat

Egy réselt adatátviteli rendszerbe egy időrésben λ paraméterű Poisson-eloszlással érkeznek csomagok. (A Poisson-folyamatból következően az aktuális kiszolgálás megkezdése után, a következő kiszolgálás megkezdése előtt.) Egy nem ideális kiszolgáló csatorna áll rendelkezésre, amely — amennyiben van benne igény — annak kiszolgálását az adott időrésben 0<γ≤1 valószínűséggel befejezi a korábbi időrésektől függetlenül, illetve 1-γ valószínűséggel nem fejezi be, hanem a következő időrésben tovább folytatja. Minden csomag egységnyi hosszúságú puffertt igényel. Az érkező igények mind a kiszolgálóba, mind a pufferbe beléphetnek, ha az szabad.

1. Rajzolja fel a fenti rendszer állapotgráfját, ha végtelen a puffer hossza! Az állapotgráf áttekinthetetlen lenne, ezért állapotmátrixot rajzolok. Az időrés hossza legyen _t_. Ekkor annak a valószínűsége, hogy egy időrésben _k_ igény érkezik, λt paraméterű Poisson-eloszlás szerint alakul: [math]y_k = \frac{(\lambda t)^k}{k!}\mathrm{e}^{-\lambda t} [/math] Az állapotátmeneti mátrix: [math] P = \begin{array}{c|cccc} & 0 & 1 & 2 & \cdots \\ \hline 0 & y_0 & y_1 & y_2 & \cdots \\ 1 & \gamma y_0 & (1-\gamma)y_0 + \gamma y_1 & (1-\gamma)y_1 + \gamma y_2 & \cdots \\ 2 & 0 & \gamma y_0 & (1-\gamma)y_0 + \gamma y_1 & \cdots \\ 3 & 0 & 0 & \gamma y_0 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \end{array} [/math] Pl. 1→1 állapotátmenet akkor történik, ha 0 igény érkezik (y₀) és nincs kiszolgálás (1-γ) vagy 1 igény érkezik (y₁) és van kiszolgálás (γ).
2. Adja meg a rendszer kihasználtságát! Mikor stabil ez a rendszer? Az átlagos kiszolgálási idő az időrés hosszának és az egy igény kiszolgálásához szükséges időrések átlagos számának szorzata: E[x] = t*1/γ. A rendszer akkor stabil, ha az átlagos érkezési időköz nagyobb, mint az átlagos kiszolgálási idő: 1/λ > E[x], azaz 1/λ > t/γ. A rendszer kihasználtsága a Little-formulából számítható: ρ = E[X_S] = λE[x] = λt/γ.
3. Rajzolja fel a rendszer állapotgráfját, ha a puffer hossza 2! Az állapotokat úgy jelölöm, hogy a sorszámuk az időrés végén a rendszerben lévő igények számával legyen egyenlő. [math] \begin{array}{c|cccc} & 0 & 1 & 2 & 3 \\ \hline 0 & y_0 & y_1 & y_2 & 1-y_0-y_1-y_2 \\ 1 & \gamma y_0 & (1-\gamma)y_0 + \gamma y_1 & (1-\gamma)y_1 + \gamma y_2 & 1-y_0-y_1-\gamma y_2 \\ 2 & 0 & \gamma y_0 & (1-\gamma)y_0 + \gamma y_1 & 1-y_0-\gamma y_1 \\ 3 & 0 & 0 & \gamma y_0 & 1-\gamma y_0 \end{array} [/math]
4. Adja meg az utóbbi esetben a rendszer kihasználtságát és az igényvesztés valószínűségét ismert állapotvalószínűségek feltételezésével! Kihasználtság: a következő időrésben akkor dolgozik a kiszolgáló, ha a rendszer nem p₀ állapotban van ⇒ ρ = 1-p₀. Veszteség valószínűség: ha a rendszer p₃ állapotban volt, 1 valószínűséggel veszik el a beérkező igény. Ha p₂-ben volt, egy igény még belefér a pufferbe, de az adott időrésben a többi el fog veszni. Tehát p_v > p₃, de nem tudom pontosan megmondani, hogy mennyi.

2006.12.19, 1. feladat

Egy réselt adatátviteli rendszerebe egy időrésben p₀, p₁, p₂ valószínűséggel időrésenként 0, 1, 2 igény érkezik, aszinkron módon, azaz az aktuális kiszolgálás megkezdése után. Egy kiszolgáló csatorna van, amely az igényeket γ paraméterű geometriai eloszlás szerint szolgálja ki. Minden csomag egységnyi hosszúságú puffert igényel. Az érkező igények mind a kiszolgálóba, mind a pufferbe beléphetnek, ha az szabad.

1. Rajzolja fel a rendszer állapotgráfját, ha végtelen a puffer hossza! Az állapotgráf helyett állapotátmeneti mátrixot rajzolok: [math] \begin{array}{c|cccccc} & 0 & 1 & 2 & 3 & 4 & \cdots \\ \hline 0 & p_0 & p_1 & p_2 & 0 & 0 & \cdots \\ 1 & \gamma p_0 & (1-\gamma) p_0+\gamma p_1 & (1-\gamma) p_1+\gamma p_2 & (1-\gamma) p_2 & 0 & \cdots \\ 2 & 0 & \gamma p_0 & (1-\gamma) p_0+\gamma p_1 & (1-\gamma) p_1+\gamma p_2 & (1-\gamma) p_2 & \cdots \\ 3 & 0 & 0 & \gamma p_0 & (1-\gamma) p_0+\gamma p_1 & (1-\gamma) p_1+\gamma p_2 & \cdots \\ 4 & 0 & 0 & 0 & \gamma p_0 & (1-\gamma) p_0+\gamma p_1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \end{array} [/math]
2. Adja meg a rendszer kihasználtságát! Mikor stabil a rendszer? Ha _T_ az időrés hossza
   • Egy igényt átlagosan 1/γ időrés alatt lehet kiszolgálni, azaz E[x] = T/γ.
   • Egy időrésben átlagosan p₁+2p₂ igény érkezik. Az átlagos érkezési intenzitás E[λ] = (p₁+2p₂)/T
   A Little-formula alapján ρ = E[λ]E[x] = (p₁+2p₂)/γ. A rendszer akkor stabil, ha ρ<1
3. Rajzolja fel a rendszer állapotgráfját, ha a puffer hossza 2! Feltételezem, hogy ha több igény érkezik, mint amennyi belefér a pufferba, akkor csak a túlcsorduló igények vesznek el, nem az összes. Az állapotátmeneti mátrix: [math] \begin{array}{c|cccc} & 0 & 1 & 2 & 3 \\ \hline 0 & p_0 & p_1 & p_2 & 0 \\ 1 & \gamma p_0 & (1-\gamma) p_0+\gamma p_1 & (1-\gamma) p_1+\gamma p_2 & (1-\gamma) p_2 \\ 2 & 0 & \gamma p_0 & (1-\gamma) p_0+\gamma p_1 & (1-\gamma) p_1+p_2 \\ 3 & 0 & 0 & \gamma p_0 & (1-\gamma) p_0+p_1+p_2 \\ \end{array} [/math] Megjegyzés: mivel p₀+p₁+p₂=1, a mátrix jobb alsó mezőjét írhatnánk akár 1-γp₀ alakban is.
4. Adja meg az utóbbi esetben a rendszer kihasználtságát és az igényvesztés valószínűségét ismert állapotvalószínűségek feltételezésével! Kihasználtság: ρ = 1-p₀. Igényvesztés valószínűsége:
   • 0 és 1 állapotban nem veszhet el igény
   • 2 állapotban (1-γ)p₂ valószínűséggel veszik el 1
   • 3 állapotban (1-γ)p₁+γp₂ valószínűséggel veszik el 1 és (1-γ)p₂ valószínűséggel 2.
   Ha az állapotvalószínűségeket S₀, S₁, S₂, S₃-mal jelöljük, egy időrés alatt átlagosan S₂(1-γ)p₂ + S₃((1-γ)p₁+γp₂) + 2S₃(1-γ)p₂ igény veszik el. Az érkező igények száma p₁+2p₂, tehát az igényvesztés valószínűsége [math] p_v = \frac{ S_2 (1-\gamma) p_2 + S_3 ((1-\gamma) p_1 + \gamma p_2) + 2 S_3 (1-\gamma) p_2 }{ p_1 + 2 p_2 } [/math]

M/G/1 és M/G/1/1 rendszerek

2005.01.06/B, 2. feladat

Egy sorbanállási rendszerbe független azonos eloszlású időközönként λ paraméterű Poisson folyamat szerint érkeznek igények. Minden igény két fokozatban igényel kiszolgálást: az első fokozatban μ paraméterű, exponenciális eloszlásút, majd a második fokozatban α valószínűséggel 0 idejű, illetve 1-α valószínűséggel _T_ idejű determinisztikus eloszlásút. Adja meg a rendszer jellemzőit, ha

1. egy kiszolgáló van és nincs puffer: A rendszer M/G/1/1 sor. Alapvető jellemzői:
   • 1. fokozat: σ_μ² = 1/μ², E[x_μ] = 1/μ
   • 2. fokozat: σ_T² = 0, E[x_T] = (1-α)T
   • Teljes kiszolgálási idő: E[x] = E[x_μ]+E[x_T] = 1/μ+(1-α)T.
   • Teljes szórásnégyzet: σ² = σ_μ²+σ_T² = 1/μ² a soros kapcsolás miatt
   • Relatív szórásnégyzet: C_S² = σ²/E[x]² = 1/(1+(1-α)μT)²
   • Adja meg a rendszer kihasználtságát! A rendszer veszteséges, ezért a Little-formula nem használható. A rendszer E[x] ideig dolgozik, aztán 1/λ ideig vár a következő igényre, ezért a kihasználtsága ρ = E[x]/(E[x]+1/λ).
   • Határozza meg a veszteséget! p_v = ρ, mert egy igény pontosan akkor veszik el, ha foglalt a kiszolgálóhoz érkezik, aminek ρ a valószínűsége.
2. egy kiszolgáló van és végtelen puffer:
   • Adja meg a rendszer modelljét! Ilyenkor M/G/1 sorról beszélünk. A rendszer evolúciós egyenlettel modellezhető.
     • Legyen X_i az _i_. kiszolgálás végén a rendszerben lévő igények száma (i≥0, X₀=0).
     • Legyen Y_i az i-1. és az _i_. kiszolgálás vége között érkező igények száma (i≥1).
     Ekkor X_i+1 = (X_i-1)⁺+Y_i+1.
   • Adja meg a stabilitás feltételét! A rendszer akkor stabil, ha λE[x] < 1, azaz 1/μ+(1-α)T < 1/λ.
   • Adja meg a rendszerbeli igények várható számát! [math] \mathrm{E}[W] = \frac{\rho}{1-\rho} \mathrm{E}[x] \frac{1+C_S^2}{2} = \frac{\lambda \mathrm{E}[x]^2}{1-\lambda \mathrm{E}[x]} \frac{1+C_S^2}{2} [/math] [math] \mathrm{E}[X] = \lambda \mathrm{E}[T] = \lambda (\mathrm{E}[W] + \mathrm{E}[x]) = \dots [/math]
3. Mennyivel tér el ezen rendszerben a rendszerbeli várható igények száma attól a rendszertől, amelynem várható kiszolgálási ideje ugyanekkore, de a két — nem nulla idejű — fokozatot két különböző kiszolgáló látja el? A Burke-tétel szerint az exponenciális fokozat M/M/1 olyan sorként működik, aminek a kimenete λ paraméterű Poisson-folyamat. A rendszer tehát felbontható egy λ bemeneti intenzitású M/M/1 és egy (1-α)λ bemeneti intenzitású M/D/1 sorra. A két E[T]-t az M/G/1 sorok speciális eseteként számolom.
   • [math] \mathrm E[X_\mu] = \lambda \mathrm E[T_\mu] = \frac{\lambda}{\mu-\lambda} [/math]
   • [math] \mathrm E[X_T] = (1-\alpha)\lambda \mathrm E[T_T] = (1-\alpha)\lambda \left( T + \frac{1}{2} \frac{(1-\alpha)\lambda T^2}{1-(1-\alpha)\lambda T} \right) [/math]
   • [math] \mathrm E[X] = \mathrm E[X_\mu] + \mathrm E[X_T] [/math]
   E[X] kisebb lesz, mint az egykiszolgálós esetben, mert a két kiszolgáló párhuzamosan működik.

2006.11.22. zh4 példa

Adott egy kiszolgáló rendszer, amelybe az igények λ paraméterű Poisson folyamat szerint érkeznek. Az igények két fokozatban igényelnek kiszolgálást: az elsőben T₁, míg a másodikban T₂ paraméterű determiniszikust. Három esetet vizsgálunk:

1. A puffer végtelen:
   • Milyen típusú ez a rendszer? Egy kiszolgáló van. Az igény két fokozatban igényel kiszolgálást, de mivel az egyes fokozatokra külön-külön nem vonatkoznak kérdések, összevonhatjuk őket egy T₁+T₂ paraméterű determinisztikus fokozattá. A rendszer tekinthető M/D/1-nek.
   • Adja meg a rendszer stabilitásának feltételét! Akkor stabil, ha az átlagos érkezési időköz nagyobb, mint a kiszolgálás ideje, azaz 1/λ > T₁+T₂
   • Mekkora a rendszer kihasználtsága? A Little-formula alapján ρ = λE[x] = λ(T₁+T₂)
   • Mekkora a rendszerbeli igények számának várható értéke? M/D/1 rendszerben [math] \mathrm{E}[X] = \lambda \mathrm{E}[T] = \lambda D + \frac{1}{2} \frac{(\lambda D)^2}{1-\lambda D} = \lambda (T_1+T_2) + \frac{1}{2} \frac{(\lambda (T_1+T_2))^2}{1-\lambda (T_1+T_2)}. [/math] A levezetést lásd itt.
2. A rendszerben nincs puffer:
   • Mikor stabil a rendszer? Mindig stabil.
   • Mekkora a rendszer kihasználtsága? A Little-formula nem használható, mert a rendszer veszteséges.
     A rendszer T₁+T₂ tölt kiszolgálással, aztán átlagosan 1/λ ideig vár a következő igényre. Ezért a rendszer kihasználtsága [math] \rho = \frac{T_1+T_2}{1/\lambda+T_1+T_2}. [/math]
   • Mekkora az igényvesztés valószínűsége? Akkor veszik el egy igény, ha foglalt kiszolgálóhoz érkezik, tehát p_v = ρ.
3. Hogyan változna a rendszer modellje és hogyan változnának a rendszerparaméterek az előző két esetben, ha az első és a második fokozatban a determinisztikus helyett μ₁=1/T₁ és μ₂=1/T₂ paraméterű exponenciális eloszlás lenne?
   • Mikor stabil a rendszer? Akkor, ha az átlagos érkezési időköz nagyobb, mint a kiszolgálás átlagos ideje, azaz 1/λ > 1/μ₁+1/μ₂ = T₁+T₂. Tehát a két rendszer ugyanakkor stabil.
   • Mekkora a rendszer kihasználtsága? A Little-formula alapján ρ = λE[x] = λ(1/μ₁+1/μ₂) = λ(T₁+T₂).
   • Mekkora az igényvesztés valószínűsége? Mivel végtelen a pufferméret, nem veszik el igény.

2006.12.19, 2. feladat

Egy sorbanállási rendszerbe független azonos eloszlású időközönként λ₁ és λ₂ paraméterű Poisson eloszlás szerint érkeznek igények. Az 1. típusú igények μ paraméterű exponenciális eloszlású, míg a 2. típusú igények D paraméterű determinisztikus eloszlású kiszolgálást igényelnek.

1. Egy kiszolgáló van és nincs puffer:
   • Adja meg a rendszer kihasználtságát! A rendszerbe λ₁+λ₂ intenzitással érkeznek az igények. Egy igény λ₁/(λ₁+λ₂) valószínűséggel 1. típusú és λ₂/(λ₁+λ₂) valószínűséggel 2. típusú. A rendszer működése periodikus. Először átlagosan 1/(λ₁+λ₂) ideig vár a következő igényre, aztán az érkező igény típusától függően átlagosan 1/μ vagy _D_ ideig szolgálja ki. A rendszer kihasználtsága: [math] \rho = \frac{ \frac{\lambda_1}{\lambda_1+\lambda_2} \frac{1}{\mu} + \frac{\lambda_2}{\lambda_1+\lambda_2} D }{ \frac{1}{\lambda_1+\lambda_2} + \frac{\lambda_1}{\lambda_1+\lambda_2} \frac{1}{\mu} + \frac{\lambda_2}{\lambda_1+\lambda_2} D } = \frac{ \lambda_1 / \mu + \lambda_2 D } { 1 + \lambda_1 / \mu + \lambda_2 D } [/math]
   • Határozza meg a veszteséget! A veszteség megegyezik a kihasználtsággal. p_v = ρ
2. Egy kiszolgáló van és végtelen puffer:
   • Adja meg a rendszer modelljét! M/G/1 rendszer, jellemzőit a következő részfeladatokban számoljuk.
   • Adja meg a stabilitás feltételét! [math] \displaystyle{ \mathrm{E}[x] = \frac{\lambda_1}{\lambda_1+\lambda_2} \frac{1}{\mu} + \frac{\lambda_2}{\lambda_1+\lambda_2} D } [/math] Akkor stabil, ha E[x] < 1/(λ₁+λ₂), azaz λ₁/μ+λ₂D < 1
   • Hogyan határozná meg a rendszerbeli igények várható számát! [math] \displaystyle{ \mathrm{E}[x^2] = \frac{\lambda_1}{\lambda_1+\lambda_2} \mathrm{E}[x_\mu^2] + \frac{\lambda_2}{\lambda_1+\lambda_2} \mathrm{E}[x_D^2] = \frac{\lambda_1}{\lambda_1+\lambda_2} \frac{2}{\mu^2} + \frac{\lambda_2}{\lambda_1+\lambda_2} D^2 } [/math] [math] \displaystyle{ C_S^2 = \frac{\sigma[x^2]}{\mathrm{E}[x]^2} = \frac{\mathrm{E}[x^2] - \mathrm{E}[x]^2}{\mathrm{E}[x]^2} = \frac{\mathrm{E}[x^2]}{\mathrm{E}[x]^2}-1 } [/math] [math] \displaystyle{ \rho = (\lambda_1+\lambda_2) \mathrm{E}[x] = \lambda_1 \mathrm{E}[x_\mu] + \lambda_2 \mathrm{E}[x_D] = \lambda_1 / \mu + \lambda_2 D } [/math] [math] \displaystyle{ \mathrm{E}[X] = (\lambda_1+\lambda_2) \mathrm{E}[T] = (\lambda_1+\lambda_2) (\mathrm{E}[x] + \mathrm{E}[W]) = (\lambda_1+\lambda_2) (\mathrm{E}[x] + \frac{\rho}{1-\rho} \mathrm{E}[x] \frac{1+C_S^2}{2}) } [/math]
3. Mennyivel tér el ezen rendszerben a rendszerbeli igények várható száma attól a rendszertől, amelyben a kétféle igényt két különböző kiszolgáló szolgálja ki, mindkettő előtt végtelen pufferrel? Mekkora lenne ekkor a kiszolgálók átlagos kihasználtsága? A rendszer felbontható egy párhuzamosan működő M/M/1 és M/D/1 rendszerre. Az igények átlagos száma
   • az elsőben [math] \mathrm{E}[X_\mu] = \frac{\lambda_1}{\mu-\lambda_1} [/math];
   • a másodikban [math] \mathrm{E}[X_D] = \lambda_2 D + \frac{1}{2} \frac{(\lambda_2 D)^2}{1-\lambda_2 D} [/math].
   A teljes rendszerben lévő igények átlagos számát a kettő összege adja. A részletes levezetés itt található.
4. Adja meg a rendszer állapotgráfját, ha egy kiszolgáló van, a 2. típusú igények kiszolgálási ideje is exponenciális eloszlású 1/D paraméterrel, és a rendszerben egy puffer van, amelyik bármelyik típusú igényt tudja fogadni. Mekkora lenne ekkor az igényvesztés valószínűsége ismert állapotvalószínűségeket feltételezve? Az állapottérben két jellemző van lekódolva:
   • a rendszerben lévő igények száma és
   • az éppen kiszolgálás alatt lévő igény típusa.
   Az ábrán nem mindig tudtam jelezni, de a λ nyilak mindig jobbra, a μ és 1/D nyilak mindig balra mutatnak.

   	μ * λ<sub>1</sub>/(λ<sub>1</sub>+λ<sub>2</sub>)
   		/-----\ 
   	  |		 |
   	  V	λ<sub>1</sub>  |	λ<sub>1</sub>
   	  o------>o------>o ...
   	 / \	  /
   λ<sub>1</sub> /	\	/ μ * λ<sub>2</sub>/(λ<sub>1</sub>+λ<sub>2</sub>)
     /	  \ /
    o		 X
     \	  / \ 
   λ<sub>2</sub> \	/	\ (1/D) * λ<sub>1</sub>/(λ<sub>1</sub>+λ<sub>2</sub>)
   	 \ /	  \ 
   	  o------>o------>o ...
   	  ^	λ<sub>2</sub>  |	λ<sub>2</sub>
   	  |		 |
   	  \_______/
   (1/D) * λ<sub>2</sub>/(λ<sub>1</sub>+λ<sub>2</sub>)

   Az igényvesztés valószínűsége végtelen puffernél 0, véges puffernél p_m lenne.

-- Peti - 2007.01.12.