NobrElméleti feladatok kidolgozása/nobr

Ez az oldal a korábbi SCH wikiről lett áthozva.

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: példák kidolgozása

Valószínűségszámítási alapfogalmak

Mikor nevezünk memóriamentesnek egy eloszlást? Bizonyítsa be, hogy az exponenciális eloszlás memóriamentes!

Egy eloszlás akkor memóriamentes, ha egy esemény bekövetkezésének valószínűsége nem függ attól, hogy az előző bekövetkezés óta mennyi idő telt el.

Egy esemény bekövetkezésének első időpontja: $\eta$

Exponenciális eloszlás eloszlásfüggvénye: $F(\eta )=P(\eta \leq t)=1-e^{-\lambda t}$.

Annak valószínűsége, hogy az esemény t idő után fog bekövetkezni: $P(\eta >t)=e^{-\lambda t}$

Exponenciális eloszlás memóriamentes, hiszen:

$P(\eta >t+\Delta t|\eta >t)={\frac {P(\eta >t+\Delta t,\eta >t)}{P(\eta >t)}}={\frac {P(\eta >t+\Delta t)}{P(\eta >t)}}={\frac {e^{-\lambda (t+\Delta t)}}{e^{-\lambda t}}}=e^{-\lambda \Delta t}=P(\eta >t)$, azaz valóban független a bekövetkezés ideje az előző bekövetkezés idejétől.

Sorolja fel a Poisson folyamat összes tanult tulajdonságát! Ahol tudja mutassa meg e tulajdonságok kapcsolatát!

• t idő alatt az érkezések számának eloszlása $\lambda t$ paraméterű Poisson eloszlású: $P(\eta =k)={\frac {(\lambda t)^{k}}{k!}}e^{-\lambda t}$
• $\Delta t$ idő alatt 0 érkezés valószínűsége $1-\lambda \Delta t+\sigma (\Delta t)$, 1 érkezés valószínűsége: $\lambda \Delta t+\sigma (\Delta t)$, 1-nél több érkezés valószínűsége: $\sigma (\Delta t)$
• érkezési időközök független $\lambda$ paraméterű exponenciális eloszlásúak
• független Poisson folyamatok összege is Poisson folyamat
• Poisson folyamat független p valószínségű szűrése is Poisson folyamat

Tulajdonságok kapcsolata: minden $\Delta t$ intervallumban azonos az érkezés valószínűsége -> örökifjú érkezési időköz -> exponenciális eloszlású érkezési időköz

Mérés és szimuláció

Mit jelent a teljesítményjellemzők pontbecslése és milyen hátrányait látja?

A teljesítményjellemzők pontbecslésén a mért értékek matematikai átlagával történő becslést értjük. A $\gamma$ valószínűségi változó átlagának becslése $n$ kísérlet eredménye alapján:

${\overline {\gamma }}(n)={\frac {1}{n}}\sum _{i=1}^{n}{\gamma _{i}}$

A pontbecslés hátránya, hogy nem tudunk semmit a becslés pontosságáról (pl. mi van, ha a változó szórása óriási?). Szeretnénk, ha a becsült érték hibája valamekkora valószínűséggel egy meghatározott intervallumon belül maradna. => Intervallumbecslés: $P(|{\overline {\gamma }}(n)-E(\gamma )|\leq \Delta )=1-\alpha$, ahol $1-\alpha$: a konfidenciaszint, $\Delta$: a konfidencia intervallum hosszának a fele.

Mit jelent a batch mintavételezés és mire használják?

A batch mintavételezés azt jelenti, hogy egy csokorba gyűjtenek m db mintát, ezeknek az átlagát veszik, majd $n_{b}$ db ilyen csokrot előállítanak és ezeknek is az átlagát veszik és ezzel becsülik meg a valószínűségi változó értékét. A becslést akkor használják, amikor a minták értéke nem független egymástól. Pl. az egymást követő igények rendszerben eltöltött ideje függ egymástól egy adott batch-en belül. Viszont különböző batch-ek között már nem áll fenn a függőség, így ezeket is átlagolva a függőség által okozott mintavételi hiba kiküszöbölhető.

Hogyan változik a szimulációs és méréses vizsgálatok pontossága a mintaszám növelésével? Mikor tudunk erre egyértelmű összefüggést adni?

A méréses vizsgálat pontosságát a valószínűségi változó szórása adja meg. Ha ismert a $\gamma$ v.v. szórása ($\sigma _{\gamma }$), akkor n minta esetén a pontosság: $\sigma _{\gamma }(n)={\frac {\sigma _{\gamma }}{\sqrt {n}}}$, azaz a minták számát $N^{2}$-re növelve a szórás N-ed részére csökken, ugyanakkor N-ed részére csökken a konfidencia intervallum szélessége is.

Szimuláció esetében a mintaszám növekedésével azonos pontosság mellett a szimulációs idő megnövekszik. Amennyiben a szimulációs időt változatlanul kívánjuk hagyni, a mintaszám növekedésével a pontosság csökken.

Egyértelmű összefüggést a mintaszám és a pontosság között csak a valós rendszeren elvégzett mérések és a számított / szimulált eredmények összevetésével lehet adni.

Hogyan állítana elő adott eloszlású (ál)véletlen számokat?

Vegyünk egy 0 és 1 közötti egyenletes eloszlású X v.v-t. Legyen az elérni kívánt eloszlás eloszlás függvénye F. A kívánt eloszlású v.v.-t a F ^-1(X) képlet állítja elő. (Korábban itt tévesen azt írtam, hogy a sűrűségfüggvényt kell invertálni, pedig az többnyire nem invertálható.)

Hogyan állítana elő egyenletes eloszlású, [0-1) intervallumba eső (ál)véletlen számokat? Milyen kérdéseket jelent (ál)véletlen számok előállítása során a kezdőérték megválasztása?

Kongruencián alapuló álvéletlenszám generátor: $U_{i}=(aU_{i-1})mod(m)$, ahol m egy pozitív egész szám, $a$ pedig a véges test egy eleme. A maximális elérhető véletlen ciklus hossza: $\Phi (m)$, azaz az m-hez relatív prímek száma. A generált számot m-mel elosztva épp a [0-1) intervallumban levő számot kapunk.

Mint látható, az $a$ kezdőérték megválasztásától nagymértékben függ, hogy mekkora lesz a véletlen ciklus hossza. Pl. m=7, a=3 esetén a ciklus hossza maximális, 6 lesz, míg pl. a=1 esetén csak 1.

Milyen módszert alkalmazna a szimulációs kísérletek leállítására?

• Idő alapú leállási feltétel: ha a szimulációs idő elér egy bizonyos értéket, a szimuláció leáll.
• Esemény alapú leállási feltétel: ha egy bizonyos véletlen esemény bekövetkezik, a szimuláció leááll.
• Statisztikai alapú leállás: pl. ha a kívánt pontosságot elértük, a szimuláció leállhat.
• Kombinált leállási feltétel: az előző három kombinációja.

Markov láncok

Adja meg a diszkrét idejű Markov láncok egyensúlyi eloszlása létezésének feltételét véges és végtelen állapottér esetén! Ismertesse az egyensúlyi egyenleteket és alkalmazásukat állapotcsoportok esetén!

Véges állapottér esetén a diszkrét idejű Markov lánc stabil (létezik egyensúlyi eloszlása), ha a lánc irreducibilis és aperiodikus.

Végtelen állapottér esetén a diszkrét idejű Markov lánc stabil, ha a lánc irreducibilis, aperiodikus és pozitív visszatérő. Végtelen, irreducibilis, aperiodikus Markov-láncra elégséges feltétel a Foster kritérium.

Foster kritérium: irreducibilis és aperiodikus Markov láncra ha $\exists I\geq 0,C>0,\Delta >0$ úgy, hogy:

$k\leq I:E[X_{n+1}|X_{n}=k]\leq C$

$k>I:E[X_{n+1}|X_{n}=k]\leq k-\Delta$.

Egyensúlyi egyenletek (egyenlet a j. állapotra):

$\sum _{i\neq j}{p_{i}p_{ij}}=p_{j}\sum _{j\neq k}{p_{jk}}$, azaz a j. állapotba belépés valószínűsége megegyezik a j. állapotba kilépés valószínűségével.

Egyensúlyi egyenletek alkalmazása állapotcsoportok esetén:

$\sum _{i\in U}{p_{i}}\sum _{j\in D}{p_{ij}}=\sum _{j\in D}{p_{j}}\sum _{k\in U}{p_{jk}}$, azaz az U állapotcsoportból kilépés fluxusa megegyezik a D állapotcsoportba belépés fluxusával.

Adja meg folytonos idejű Markov láncok egyensúlyi eloszlása létezésének feltételét véges es végtelen állapottér esetén, ismertesse az egyensúlyi egyenleteket és alkalmazásukat állapotcsoportok esetén!

Véges állapottér esetén a folytonos idejű Markov lánc stabil (létezik egyensúlyi eloszlása), ha a lánc irreducibilis.

Végtelen állapottér esetén a folytonos idejű Markov lánc stabil, ha a lánc irreducibilis és pozitív visszatérő. Elégséges feltétel a Foster kritérium teljesülése.

Egyensúlyi egyenletek (egyenlet a j. állapotra):

$\sum _{i\neq j}{p_{i}q_{ij}}=p_{j}\sum _{k\neq j}{q_{jk}}$

Egyensúlyi egyenletek alkalmazása állapotcsoportok esetén:

$\sum _{i\in U}{p_{i}}\sum _{j\in D}{q_{ij}}=\sum _{j\in D}{p_{j}}\sum _{k\in U}{q_{jk}}$

Milyen feltételek mellett stabil egy folytonos idejű Markov lánc és mi a stabilitás következménye?

A Markov lánc stabil, ha létezik egyensúlyi eloszlása (annak feltételét lásd feljebb). A stabilitásból következik, hogy a $PQ=0$ egyenlőségnek a $\sum _{i\in S}{p_{i}}=1$ feltétel mellett csak egyetlen megoldása van, mégpedig a határeloszlás. Az egyenletben szereplő $P=[p_{1},p_{2},...]$ az egyensúlyi valószínűségvektor, $Q$ pedig a rátamátrix.

Mit jelent az öröklődés fogalma diszkrét Markov láncok esetén?

Az öröklődés azt jelenti, hogy ha egy Markov lánc irreducibilis, akkor ha bármely állapota aperiodikus, minden állapot, azaz a teljes lánc is az. Ugyanígy irreducibilis diszkrét Markov lánc egy állapota ha visszatérő, akkor valamennyi állapota és így a lánc is az.

Milyen eloszlású a diszkrét idejű Markov láncokban az állapotok tartásideje?

Az állapotok tartásideje geometriai eloszlású, hiszen annak valószínűsége, hogy a rendszer az i. állapotot az n. pillanatban hagyja el: $P(\tau _{i}=n)=p_{ii}^{n-1}(1-p_{ii})$

Ismertesse a bolyongásokat! Mikor stabil egy bolyongás? Határozza meg a bolyongások egyensúlyi eloszlását!

A bolyongás egy olyan diszkrét idejű véges Markov lánc, melyben minden állapotból csak egy állapotot lehet felfele vagy lefele lépni, kivéve a 0. és az N. állapotot, mert onnan csak felfele ill. csak lefele lehet lépni.

A bolyongás stabil, ha a felfele lépés valószínűsége kisebb, mint a lefele lépés valószínűsége.

Egyensúlyi eloszlása:

Az egyensúlyi egyenletekből rekurzívan felírható: $p_{k}={\frac {b_{k-1}}{d_{k}}}p_{k-1}=p_{0}\prod _{i=1}^{k}{\frac {b_{k-1}}{d_{k}}}$, ahol $0<k\leq N$, $b_{k-1}$ a k-1. állapotból felfelé lépés, $d_{k}$ a k. állapotból lefelé lépés valószínűsége.

Mivel $\sum _{i\in S}{p_{i}}=1$, ezért $p_{0}={\frac {1}{1+\sum _{k=1}^{N}{\prod _{i=1}^{k}{\frac {b_{i-1}}{d_{i}}}}}}$

Ismertesse a születési-halálozási folyamatokat. Adja meg a stabilitás feltételét, valamint ismertesse az egyensúlyi eloszlás származtatásának módját!

A születési-halálozási folyamat egy olyan folytonos idejű Markov lánc, melyben minden állapotból csak egy állapotot lehet felfele vagy lefele lépni, kivéve a 0. (és véges esetben az N. állapotot), mert onnan csak felfele (ill. csak lefele) lehet lépni. A felfele lépést születésnek, a lefelé lépést halálozásnak nevezzük. A születési intenzitást általában $\lambda$-val, a halálozásét $\mu$-vel jelöljük.

A születési-halálozási folyamat stabil, ha a születés intenzitása kisebb, mint a halálozás intenzitása, azaz $0\leq \lambda <\mu <\infty$

Egyensúlyi eloszlása:

Az egyensúlyi egyenletekből rekurzívan felírható: $p_{k}={\frac {\lambda _{k-1}}{\mu _{k}}}p_{k-1}=p_{0}\prod _{i=1}^{k}{\frac {\lambda _{k-1}}{\mu _{k}}}$, ahol $0<k\leq N$, $\lambda _{k-1}$ a k-1. állapotbani születés, $\mu _{k}$ a k. állapotbani halálozós intenzitása.

Mivel $\sum _{i\in S}{p_{i}}=1$, ezért $p_{0}={\frac {1}{1+\sum _{k=1}^{N}{\prod _{j=1}^{k}{\frac {\lambda _{j-1}}{\mu _{j}}}}}}$

Little-formula

Ismertesse a Little formulát és a formula érvényességi feltételeit!

Érvényességi feltételek: a rendszer veszteségmentes és munkamegőrző, valamint léteznek az $E[\lambda ]=\lim _{t\to \infty }\lambda _{t}$ és az $E[T]=\lim _{t\to \infty }T_{t}$ határértékek, ahol $T_{t}$ az igények által eltöltött átlagos idő a (0,t) intervallumban.

Little formula: a fenti érvényességi feltételek teljesülése esetén $E[X]=E[\lambda ]E[T]$

<a name="Little_bizonyitas">

Bizonyítsa a Little formula helyességét!

Ezen a helyen volt linkelve a little_biz.gif nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

$\alpha (t)$ : az érkezések száma a $(0,t)$ intervallumban

$\beta (t)$ : a távozások száma a $(0,t)$ intervallumban

$X(t)=\alpha (t)-\beta (t)$ : az igények száma a rendszerben a $t$ időpontban

Az $\alpha (t)$ és $\beta (t)$ közötti terület nagysága: $\int _{0}^{t}X(\tau )d\tau$

Másrészt ez felírható így is: $\sum _{i=1}^{\alpha (t)}T_{i}$

$X_{t}={\frac {1}{t}}\int _{0}^{t}X(\tau )d\tau ={\frac {1}{t}}\sum _{i=1}^{\alpha (t)}T_{i}={\frac {\alpha (t)}{t}}{\frac {\sum _{i=1}^{\alpha (t)}T_{i}}{\alpha (t)}}$

$X_{t}=\lambda _{t}T_{t}$

ha $X_{t}\rightarrow E[X],\lambda (t)\rightarrow \lambda ,T_{t}\rightarrow E[T],{\frac {\alpha (t)}{t}}\rightarrow E[\lambda ],{\frac {\beta (t)}{t}}\rightarrow E[\lambda ]$

Tehát $E[X]=E[\lambda ]E[T]$

Mi a Little-formula lényege? Alkalmazza a formulát egy rendszer különböző részeire! Miért eredményes a kiszolgálóra való alkalmazás?

A Little formula összefüggést ad a rendszerben sorbanálló entitások száma és az átlagos érkezési ráta, valamint az átlagos rendszerben eltöltött idő között. Minél nagyobb a rendszerben eltöltött idő, annál több lesz a sorban állók száma. Továbbá minél nagyobb az átlagos érkezési ráta, annál többen fognak sorban állni.

Alkalmazása szerverre: $E[X_{s}]=E[\lambda ]E[x]$ Alkalmazása sorra/bufferre: $E[X_{w}]=E[\lambda ]E[W]$ Alkalmazása veszteséges rendszerre: $E[X]=(1-p_{loss})E[\lambda ]E[T]$

TODO: miért eredményes a kiszolgálóra való alkalmazás?

Hasonlítsa össze a folyamegyensúly és a Little-formula alkalmazásának feltételeit és a formulát, s alkalmazza mindkettőt az M/M/1 rendszerre!

Folyamegyensúly alkalmazásának feltételei: veszteségmentes, stabil sorbanállási rendszerben létezniük kell az $E[\lambda ]=\lim _{t\to \infty }\lambda _{t}$ és az $E[S]=\lim {t\to \infty }S_{t}$ határértékeknek.

Folyamegyensúly: a fenti feltételek teljesülése esetén $E[\lambda ]=E[S]$

A folyamegyensúly tehát akkor alkalmazható, ha az érkezési intenzitás és a távozási (kiszolgálási) intenzitás határértéke létezik. A Little-formula pedig a fentiek szerint akkor, ha az érkezési intenzitás és a rendszerben levő igények által eltöltött átlagos idő határértéke létezik. A folyamegyensúly tehát mintegy a kiszolgáló rendszer szempontjából (kiszolgálási intenzitás) írja le ugyanazon követelményt, amelyet a Little-formula a kiszolgálandó igények szempontjából (várható rendszerben töltött idő) fogalmaz meg.

Folyamegyensúly az M/M/1 rendszerre:

Érkezés: $E[\lambda ]=\sum _{i}\lambda _{i}p_{i}=\lambda$

Távozás: $E[S]=\sum _{i}\mu _{i}p_{i}=\mu (1-p_{0})$, ahonnan $E[\lambda ]=E[S]$ miatt $p_{0}=1-{\frac {\lambda }{\mu }}$

Little-formula az M/M/1 rendszerre:

Érkezés: $E[\lambda ]=\sum _{i}\lambda _{i}p_{i}=\lambda$

Rendszerben töltött átlagos idő: $E[T]=E[x]+E[W]$

Ha ismerjük E[x] és E[W] értékét, akkor $E[X]=E[\lambda ]E[T]$ számítható. Ha E[X]-et és E[x]-et ismerjük, akkor szintén számítható E[T] és így E[W] is, stb.

Számítógépes modellezés

Mik a számítógépes rendszerek fő modellezési lépései Markov-modellek építése esetén?

1. rendszer állapotainak meghatározása
2. állapotok számozása
3. állapotátmeneti intenzitások meghatározása
4. állapotegyenletek felírása
5. egyenletek megoldása
6. teljesítményjellemzők előállítása a megoldásból

Mik a számítógépes rendszerek modellezése során az állapotok meghatározásának illetve az állapotegyenletek felírásának jellegzetes kérdései?

Állapotok meghatározásának kérdései:

• Milyen jellemzők adják az állapotokat?
• Minél finomabb a modell, annál több az állapot.
• Többféle igénytípus vagy több puffer esetén az állapottér exponenciálisan nő.

Állapotegyenletek felírásának jellegzetes kérdései:

• Egyensúlyi helyzetben ∀ állapotra Σbelépési intenzitás = Σkilépési intenzitás.
• Ugyanez igaz állapotcsoportokra is.
• A fenti két egyenlettípust tartalmazó egyenletrendszer összefüggő, de a Σállapotvalószínűség = 1 egyenletet hozzávéve már egyértelműen megoldható.

Mik a számítógépes rendszerek modellezése során az állapotátmeneti intenzitások meghatározásának, illetve a teljesítményjellemzők meghatározásának jellegzetes kérdései?

• Minden állapotnál meg kell adni a lehetséges szomszédos állapotokat és az állapotváltások intenzitásait.
• Ilyen például az igényérkezés, amikor a rendszer egy kisebb sorhosszt jelképező állapotból egy nagyobb sorhosszt jelképező állapotba lép át.
• Az állapotváltás intenzitása az állapotváltás fajtájától függ, például egy igénybeérkezést leíró váltás az igények generálásának intenzitásával, egy kiszolgálást leíró váltás a kiszolgálás intenzitásával lesz arányos.

Mik a számítógépes rendszerek modellezése során az állapotok számozásának, illetve az állapotegyenletek megoldásának jellegezetes kérdései?

• Az állapotokat érdemes egységes konvenció alapján számozni.
• Több kiszolgálót tartalmazó rendszerekben többdimenziós állapotteret kell kezelni.
• Az egyes dimenziók megszámlálható végtelen méretűek is lehetnek.

Az állapotegyenletekre vonatkozó megállapításokat lásd egy korábbi kérdésben.

z-transzformáció

Mi a z-transzformáció lényege és milyen területeken használják a rendszerek teljesítőképességi modellezésében?

f_n sorozat z-transzformáltja: $F(z)=\sum _{n=0}^{\infty }f_{n}z^{n}$

Diszkrét eloszlások momentumait, illetve diszkrét Markov-láncok tranziens és egyensúlyi állapotvalószínűségeit lehet vele meghatározni zárt formában a hatványsorok eszköztárával.

Összetett érkezés és kiszolgálás

Hogyan modellezne csoportos érkezéseket és csoportos kiszolgálást?

Csoportos érkezés: tegyük fel, hogy az érkezési folyamat λ paraméterű Poisson, és p_k valószínűséggel érkezik _k_ igény. Ekkor az állapotátmeneti gráf i→i+k élére p_kλ-t kell írni. Visszafele csak i→i-1 élek vannak μ intenzitással.

Ezen a helyen volt linkelve a csoportos_erkezes.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Csoportos kiszolgálás: az előbbi fordítottja azzal a különbséggel, hogy ha az _i_ állapotban _k_ igényt szolgálnánk ki és k > i, akkor a 0 állapotba vezet μ_k intenzitású él.

Ezen a helyen volt linkelve a csoportos_kiszolgalas.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Hogyan modellezne lépcsős érkezéseket és kiszolgálásokat?

Lépcsős érkezés:

Ezen a helyen volt linkelve a lepcsos_erkezes.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Lépcsős kiszolgálás:

Ezen a helyen volt linkelve a lepcsos_kiszolgalas.png nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Ismertesse az összetett és phase-type típusú kiszolgálási idő eloszlások modellezésének lényegét és alkalmazási lehetőségeit!

A hálózat exponenciális kiszolgálókból áll, a kiszolgálási fokozatok sorrendje Markov-lánccal írható le. A Markov-láncot reprezentáló gráf élein lesznek a kiszolgálók. A fázis típusú rendszer a következő paraméterekkel írható le:

• _A_: tranziens állapotok halmaza, _B_: nyelő állapotok halmaza.
• Q_AA illetve Q_AB rátamátrix.
• α kezdeti valószínűségvektor.

P(t időpontban nyelőben vagyunk) = 1-αe^Q_AAth, ahol _h_ 1-esekből álló oszlopvektor.

Alkalmazás sormodellekben: a rendszert leíró folytonos Markov-lánc állapottere = {rendszerben lévő jobok száma} × {fázisok száma}

Sorbanállási rendszerek

Ismertesse a sorbanállási rendszerek Kendall-féle jelölésrendszerét!

A/B/c/d/e − x

• A:   az érkezési időközök eloszlásának típusa.
  

Lehetőségek:

• • M : emlékezetmentes eloszlás (folytonos időben markovi) exponenciális eloszlás
  • Geom: emlékezetmentes eloszlás (diszkrét időben markovi) geometriai eloszlás
  • D: determinisztikus eloszlás
  • G: általános eloszlás (egyes -főleg régebbi - irodalmakban egyúttal független és azonos általános eloszlás)
  • GI: (egyes újabb irodalmakban ezt használják a független, azonos, általános eloszlás jelölésére)

• B:   a kiszolgálási idő eloszlásának típusa.
  • Lehetőségek: ld. A

• c:   a kiszolgáló egységek száma
  • Véges vagy végtelen is lehet.

• d:   a rendszer kapacitása
  • Beleértve a kiszolgáló egységet is!

• e:   az igényforrások száma
  • Véges vagy végtelen is lehet.

• x:   kiszolgálási elv
  • FIFO (FCFS) – First In First Out (First Come First Served)
  • LIFO (LCFS) – Last In First Out (Last Come First Served)
  • RO – Random Order
  • RR – Round Robin
  • PS – Processor Sharing
  • Priority

Mi az Erlang-C formula jelentése? Milyen sorbanállási rendszerhez kapcsolódik ez a formula és hogyan?

A formula az M/M/m sorban mutatja meg a várakozás (azaz a foglaltság) valószínűségét. Ez a valószínűség az M/M/m sort leíró Markov lánc m, m+1, m+2, ... állapotvalószínűségeinek összegeként adódik.

M/G/1

Ismertesse az M/G/1 rendszer modellezésének problémáját, a modellezés megoldásának elvét!

Az alapgond az, hogy az X(t) rendszerbeli igények száma nem emlékezetmentes. A rendszer mégis modellezhető Markov lánccal mégpedig úgy, hogy a kiszolgálás befejezésekor, diszkrét időpontokban vizsgáljuk a rendszert, és az ilyenkor rendszerben lévő igények számát tekintjük állapotoknak.

Az állapotátmenetek evolúciós egyenlettel írhatók le:

• X_i = a rendszerben lévő igények száma az _i_. kiszolgálás végén.
• Y_i = az _i_. kiszolgálás alatt beérkező új igények száma.

A két változó között felírható a következő összefüggés: X_i+1 = (X_i-1)⁺ + Y_i+1

Az evolúciós egyenletből levezethető a Pollaczek—Hincsin-féle várható érték formula. A képlet megadja az átlagos várakozási időt a kihasználtságból, illetve a kiszolgálási idő eloszlásának várható értékéből és relatív szórásnégyzetéből. A többi teljesítményjellemző a Little-formula alapján számolható.

Ismetesse a hátralévő idő paradoxonát és mutassa meg, bogy a hátralévő kiszolgálási időre vonatkozó eredmények hogyan alkalmazhatók az M/G/1 rendszerek vizsgálatában!

Hátralevő idő paradoxon: az érkezési időközök exponenciális eloszlásúak, viszont a kiszolgálási idő, és így a következő érkezésig hátralevő idő már NEM az! Mi lesz a hátralevő idő eloszlása? Mi a várható értéke?

Jelölés: η: véletlen időtartam v.v., γ: az η időintervallum belsejében az intervallum végéig hátralevő idő

Várható hátralevő idő: $E[\gamma ]=E[\eta ]{\frac {1+C_{\eta }^{2}}{2}}$

Alkalmazás M/G/1 rendszer esetén:

Várható várakozási idő: $E[W]={\frac {\sigma }{1-\sigma }}E[x]{\frac {1+C_{s}^{2}}{2}}$ (Pollaczek-Hincsin várhatóérték formula)

Várható rendszerben eltöltött idő: $E[T]=E[x]+E[W]$

Rendszerbeli igények várható száma: $E[X]=E[\lambda ]E[T]$ (Little-formula felhasználása)

Milyen hasonlóság és milyen különbség van az M/G/1 rendszer és a réselt csatornán való csomagtovábbítás modellezése között?

Különbség: réselt csatornán a csomagok ún. időrésekben érkeznek. p valószínűséggel 1, 1-p valószínűséggel 0 csomag. M/G/1 rendszerben a csomagok exponenciális eloszlás szerint érkeznek.

Hasonlóság: mind a réselt csatornán mind az M/G/1 rendszerben a csomagokra csak időrésenként egy diszkrét időpontban, vagy az időrés elején, vagy az időrés végén tekintünk. Ez utóbbi esetben azért, hogy a modellezés egyszerűsödjön (másképp ugyanis a hátralevő idő eloszlását is ismernünk kellene, hiszen a kiszolgálás ideje nem memóriamentes!). Hasonlóság még, hogy mindkét rendszerben alkalmazható a Little-formula.

Adja meg az M/G/1 rendszer átmenetvalószínűségeit! Milyen időpontokra igazak ezek az átmenetvalószínűségek?

Evolúciós egyenlet: $X_{n+1}=X_{n}+Y_{n+1}-\chi (X_{n})$, ahol $\chi (X)$ értéke 0, ha a rendszer üres, 1, ha a rendszerben van kiszolgálandó igény.

Átmenetvalószínűségek az evolúciós egyenletből: $P(X_{n+1}=j|X_{n}=i)=P(Y_{n+1}=j-i+\chi (X_{n}))$

Veszteségmentes hálózatok

Mi a Burke tétel? Mik a tétel következményei tandem és aciklikus hálózatok esetén?

Stabil M/M/m sor kimeneti folyamata is Poisson az érkezési folyamat paraméterével.

Megjegyzés: M/M/1 hálózat stabilitásának feltétele: ${\frac {\lambda }{\mu }}<1$

Tandem hálózatok esetén:

Két sorbakapcsolt M/M/1 kiszolgáló esetén (állapotaikat $(k_{1},k_{2})$ párral jelölve), ha ${\frac {\lambda }{\mu _{1}}}<1$ és ${\frac {\lambda }{\mu _{2}}}$ teljesül, akkor a két kiszolgáló sorba kapcsolásával keletkező hálózat akkor stabil, ha $\lambda <min(\mu _{1},\mu _{2})$.

Aciklikus hálózatok esetén:

Aciklikus, előre csatolt, sorba kapcsolt k db hálózatok esetén teljesül, hogy $p_{k_{1},k_{2},...,k_{N}}=\prod _{i=1}^{N}p_{k_{i}}$, azaz a teljes rendszer egy állapotvalószínűsége kiszámítható az egyes fokozatok megfelelő állapotvalószínűségeinek szorzataként.

Ismertesse a nyílt sorbanállási hálózatok lényegét, és a kapcsolódó legfontosabb összefüggéseket!

A hálózat N db csomópontot tartalmaz, az i. csomópontban $m_{i}$ db kiszolgáló működik, melyeknek kiszolgálási intenzitása $\mu _{i}$.

Az igények háromféleképp mozoghatnak a rendszerben:

• a rendszeren kívülről egy új igény érkezik az j. csomópontba $\gamma _{j}$ paraméterű Poisson eloszlás szerint
• a rendszer i. csomópontjából a j. csomópontjába lép át egy igény r_ij i,j=1,2,...,N valószínűséggel
• a az i. csomóponton keresztül egy igény távozik a rendszerből $1-\sum _{k=1}^{N}r_{ik}$ i,k=1,2,...,N valószínűséggel

Csomópontok eredő érkezési intenzitása: $\lambda _{i}=\gamma _{i}+\sum _{j=1}^{N}\lambda _{j}r_{ji}$ i=1,2,...,N

Nyílt sorbanállási hálózat stabilitásának feltétele: $\lambda _{i}<m_{i}mu_{i}$ i=1,2,...,N

Egyensúlyi egyenlet az N. állapotra:

$p_{N}[\sum _{i=1}^{N}{\gamma _{i}}+\sum _{i=1}^{N}{\alpha _{i}(k_{i})\mu _{i}}]=\sum _{i=1}^{N}{p_{N_{i,0}}\alpha _{i}(k_{i}+1)\mu _{i}r_{i,0}}+\sum _{j=1}^{N}{p_{N_{0,j}}\gamma _{i}\delta _{i}(k_{i})}+$ $+\sum _{i=1}^{N}{\sum _{j=1}^{N}{p_{N_{i,j}}\alpha _{i}(k_{i+1})\mu _{i}r_{i,j}}}$

Mi a különbség a zárt és a nyílt sorbanállási hálózatok között? Mi a hasonlóság?

A zárt sorbanállási hálózat a nyílt egy olyan speciális esete, amelyben új igény nem érkezhet és nem is hagyhatja el a rendszert, azaz csak az i. csomópontból a j. csomópontba való átlépés megengedett. A különbség tehát, hogy a zárt hálózatban az igények száma állandó, míg nyílt hálózat esetén változó.

A hasonlóság abból adódik, hogy a zárt hálózat gyakorlatilag ugyanolyan, mint egy nyílt hálózat, ha az igények nem távoznak el a rendszerből, és nem is érkeznek újak. Az egyensúlyi egyenlet is ugyanúgy írható fel a zárt rendszerre, csak értelemszerűen a kilépő és a bejövő valószínűségeket nem kell figyelembe venni, kizárólag az átlépések valószínűségét.

Réselt rendszerek

Ismertesse a réselt csatornán való csomagtovábbítás modellezésének módszerét!

A réselt csatornán való csomagtovábbítást egy speciális bolyongásként modellezhetjük, amelynek állapottere végtelen.

• Érkezés: egy időrésen belül p valószínűséggel 1 csomag érkezik és 1-p valószínűséggel 0 csomag.
• Kiszolgálás: ha van csomag a rendszerben, az időrés végén q valószínűséggel 1 csomagot továbbít, 1-q valószínűséggel 0 csomagot.
• A kiszolgálási elv: FIFO
• Rendszerállapot: az időrés elején a továbbításra váró csomagok száma ($X_{i}$)

Az evolúciós egyenlet és így a Markov lánc kétféleképpen alkotható meg:

1) egy időrésben előbb továbbítjuk a csomagot, majd azután érkezik új csomag: $X_{n+1}=(X_{n}-V_{n+1})^{+}+Y_{n+1}$

2) egy időrésben előbb érkezik az új csomag, majd azután történik a továbbítás: $X_{n+1}=(X_{n}-V_{n+1}+Y_{n+1})^{+}$

Mit jelent az ALOHA csatorna modellezésében a 0-adrendű és a „pontos” modell? Milyen eredményt szolgáltat réselt esetben a 0-adrendű modell?

A 0-adrendű modell az érkezési folyamatot Poisson-folyamatnak tekinti, és nem vesz tudomást arról, hogy befolyásolja az érkezéseket a ütközések miatti ismétlés.

A pontos modell figyelembe veszi azt is, hogy mi volt a várakozási idő eloszlása a csomagismétlés előtt.

A 0-adrendű modellben _g_ a bejövő intenzitás és _T_ a rés mérete. Az egy résben érkező igények számának eloszlása G=gT paraméterű Poisson-eloszlás. A sikeres átvitel valószínűsége (hasznos kihasználtság) Ge^-G, a kihasználtság maximális értéke 1/e. A csomagismétlések átlagos száma e^G.

Mi a különbség a réselt rendszerek esetén a korai és késői érkezés között? Mutasson példát rá állapotgráffal, kihasználtsággal, evolúciós egyenlettel!

• Korai (szinkron) érkezés: az igények a rések legelején érkeznek és azonnal megkezdődhet a kiszolgálásuk.
• Késői (aszinkron) érkezés: az igények bármikor érkezhetnek és a következő rés elején kezdődhet meg a kiszolgálásuk.

Evolúciós egyenlet:

• Y_i = az _i_. időrésben érkező igények száma (i=1...∞)
• X_i = az _i_. időrés végén a rendszerben lévő igények száma (i=0...∞)
• _k_ kiszolgálónk van, amik egy igényt 1 időegység alatt szolgálnak ki

• Korai érkezés: X₀=0, X_i+1=(X_i+Y_i+1-k)⁺, ahol (n)⁺ jelentése max(n, 0).
• Késői érkezés: X₀=0, X_i+1=(X_i-k)⁺+Y_i+1.

Az állapotgráf az evolúciós egyenlet alapján könnyen felrajzolható.

A kihasználtság a következőképpen számolható, ha végtelen a pufferméret:

ρ =	E[egy időrésben érkező igények száma]
	E[egy időrésben továbbított igények száma | van annyi a pufferben]

Speciális eset: _p_ valószínűséggel jön igény. Ha van igény, _q_ valószínűséggel továbbítódik. ρ = p/q

Hogyan interpretálható a kiszolgálási idő réselt csatorna esetén?

Legyen T az időrés hossza, $\gamma$ pedig annak valószínűsége, hogy az igényt az adott időrésben kiszolgáljuk. A kiszolgálást idejét úgy értelezhetjük, mint a kiszolgáláshoz szükséges időrések száma és az időrés hosszának szorzata, azaz ${\frac {1}{\gamma }}T$

-- Peti - 2007.01.10.

-- NeoXon - 2008.01.12.

-- Csapszi - 2008.01.15.