Střední hodnota doby zdržení požadavku v obsluhovém systému s čekáním

Queuing service system and request mean delay time

Abstract

Z důvodů minimalizace zpoždění paketů jsou do síťových zařízení (směrovačů) implentovány prioritní mechanismy zajišťující přednostní obsloužení paketů toku citlivého na zpoždění. Vliv přínosu priorit na střední hodnotu doby zdržení paketu v síťovém uzlu lze zkoumat pomocí modelu obsluhového systému M/M/1/∞ (viz též článek Kendallova klasifikace obsluhových systémů).

Článek obsahuje teoretické odvození a na závěr konkrétní příklad (pozn. redakce).

Doba zdržení

Pro odvození doby zdržení paketu v síťovém uzlu – směrovači - je nutné přijmout určité zjednodušující předpoklady. Předpokládejme, že směrovač lze popsat jako obsluhový systém s čekáním M/M/1/∞, který obsluhuje dva nezávislé toky s různou prioritou. Nechť λ₁, λ₂ jsou intenzity příchodů (pozn. λ₁ je intenzita prioritního toku.), λ₁+λ₂ celková intenzita příchodů a µ intenzita obsluhy.

Vzhledem k předcházejícím předpokladům lze za předpokladu rovnovážného stavu - časové invariantnosti pravděpodobnostních charakteristik - určit rovnice stacionárních pravděpodobností stavů p_m,n,r. Tj. pravděpodobnosti, že v systému je m požadavků vyšší priority, n požadavků nižší priority a požadavek priority r je v obsluze.

Pro vyřešení soustavy rovnic (1) lze použít generující funkce. Definujme

S využitím Littlova vzorce a rovnic (3) můžeme určit střední dobu zdržení požadavků obou toků – E[X₁], E[X₂] tak, že platí

Pro získání závislosti střední doby zdržení na intenzitě příchodů - λ₁ a λ₂, je nutné plně určit generující funkci H(y,z). Úpravou rovnic (1) lze nalézt vztahy

Nyní rozdělme funkci H(y,z) (2) na dvě části H₁(y,z), H₂(y,z). Součtem rovnic (5) s přihlédnutím k rovnicím (2) po algebraické úpravě dostáváme

Obdobně pro H₂(y,z) dostaneme ze soustavy rovnic (6)

Úplné určení funkce H(y,z) vyžaduje určení P₁₁(z) a P₀₂(z). Funkce P₁₁(z) a P₀₂(z) určíme z rovnic (1) a (2). Platí

Z rovnic (2), (7), (8), (9) a (10) odvodíme vztah pro generující funkci H(y,z) ve tvaru

Užitím (4) dostaneme pro E[X₁] a E[X₂]

Příklad

Předpokládejme, že do síťového uzlu realizovaného směrovačem přichází dva toky paketů s nabídkami A₁=A₂=0,1 erl (A₁=λ₁/µ A₂=λ₂/µ. Intenzita obsluhy je pro oba toky stejná µ=1/tos =1/120. Dále předpokládejme, že tok s nabídkou A₁ je prioritní (tj. má vyšší prioritu než tok s nabídkou A₂ ), router má nekonečnou kapacitu paměti a že rozdělení doby mezi příchody požadavků a doby obsluhy jsou exponenciální. Zajímá nás, jaké je průměrné zpoždění paketů ve směrovači.

Za výše uvedených předpokladů je možné popsat směrovač pomocí obsluhového systému s čekáním. K výpočtu zpoždění (střední hodnoty doby zdržení požavku v obsluhovém systému) je pak možné použít vztahy (12). Výsledky jsou uvedeny v následující tabulce.

Kromě výsledku příkladu jsou uvedeny v tabulce č.1 výsledky pro další velikosti nabídek A₁, A₂ a pro různé velikosti střední doby obsluhy t_os. Zajímala-li by nás závislost středních dob zdržení požadavků na nabídce, obdrželi bychom následující grafy.

Obr. 1 Závislost střední doby zdržení E[D₁] na nabídce A₁

Na obrázku č. 1 je znázorněna závislost střední doby zdržení prioritního toku E[D₁] na nabídce A₁. Zobrazeny jsou průběhy pro nabídky toku s nižší prioritou A₂=0 erl až A₂ =1 erl. Všimněme si, že střední doba zdržení prioritního toku vždy od určité hodnoty nabídky A₁ začíná strmě růst do nekonečna a že tato hodnota se liší pro různé velikosti nabídky A₂. Tomu odpovídá fakt, že pro obsluhový systém s čekáním by neměla celková nabídka A=A₁+A₂ být větší než počet obsluhových linek (v našem případě jedna).

Obr. 2 Závislost střední doby zdržení E[D₁] na nabídce A₂

Na obrázku č. 2 je znázorněna závislost střední doby zdržení prioritního toku E[D₁] na nabídce neprioritního toku A₂. Jedná se o lineární závislost naznačující, že velikost nabídky A₂ ovlivňuje střední dobu zdržení prioritního toku E[D₁] . To může být na první pohled matoucí. Uvědomíme-li si však, že veškeré použité veličiny mají nahodný charakter, zjistíme, že s rostoucí nabídkou A₂ roste pravděpodobnost výskytu jevu příchodu prioritního požadavku do systému v okamžiku obsluhy neprioritního požadavku. S růstem této pravděpodobnosti dochází k nárustu střední hodnoty doby zdržení E[D₁].

Obr. 3 Závislost střední doby zdržení E[D₂] na nabídce A₁

Obr. 4 Závislost střední doby zdržení E[D₂] na nabídce A₂

Na obrazcích č. 3 a č. 4 jsou znázorněny závislosti střední doby zdržení požadavků neprioritního toku E[D₂] na nabídkách A₁ a A₂.

Závěr

Příspěvek se zaměřuje na odvození střední doby zdržení toků o intenzitách λ₁ a λ₂, z nichž tok první je prioritní (tzv. slabá priorita), v obsluhovém systému představujícím síťový uzel (směrovač). Byly odvozeny vztahy (12). Díky omezenému rozsahu článku bylo použito speciálního zápisu vztahů a některé vypočetní operace byly pouze naznačeny.

Do budoucna se plánuje porovnání vztahů (12) se simulací, odvození rozptylu a provedení analýzy pro další rozdělení doby obsluhy, která by věrněji modelovala reálný datový tok.

Tento příspěvek vznikl za podpory grantu č. 1ET300750402 Grantové Agentury Akademie Věd České Republiky.

Literatura

[1] Morse, P.M. Queues, Inventories and Maintenance. New York: Wiley. 1958
[2] Gross, Donald. Harris, M. Carl. Fundamentals of Queuing Theory (Third Edition). John Wiley & Sons. New York. 1998
[3] Konopka, Lukáš. Delay of Packets in Queuing System with Priorities. Sborník RTT 2005. VŠB Ostrava. 2005