Analýza obsluhového systému s prioritami

Tento příspěvek se zabývá analýzou obsluhového systému typu M+M/M/1/∞ (dle Kendallovy klasifikace) se slabou prioritou. Analýza zkoumá vliv parametrů vstupních toků na střední dobu zdržení požadavků v systému. Za účelem vypracování analýzy byl vyhotoven simulační program a analytický popis systému.

---

Priority system analysis

Abstract

This paper deals with service system analysis type M+M/M/1/∞ (according to Kendall classification) with low priority. This analysis checks influence of input stream parameters on average time of request delay in system. In order to make this analysis a simulation program and analytical description of system were written.

---

S rozvojem multimediálních služeb rostou požadavky kladené na datové sítě. Multimediální služby obvykle vyžadují přenos v reálném čase, a proto jsou velmi citlivé na zpoždění, které je v datových sítích (pracujících na principu přepínání paketů) mimo jiné ovlivněno provozem v síti. Proto jsou za účelem minimalizace vlivu zatížení sítě na zpoždění paketů multimediálních služeb do síťových uzlů implementovány prioritní mechanismy.

Prioritní mechanismy zmenšují zpoždění paketů, které vyžadují přednostní obsluhu. Při implementaci priorit je tedy nutné rozdělit provoz v síti do tzv. prioritních tříd. Rozdělení se provádí s ohledem na citlivost služby na zpoždění. Jednotlivým prioritním třídám se přiřazuje číslo, které označuje přednost v obsluze. Je zavedená konvence, že paket z třídy s nižším číslem je přednostně obsloužen před paketem z třídy s vyšším číslem (tzn. paket s nižším číslem prioritní skupiny má vyšší prioritu).

Prioritní mechanismy je možné rozdělit podle způsobu, jakým zacházejí s pakety, které jsou v obsluze. Rozlišujeme:

• Slabou prioritu (Non pre-emptive priority)
• Silnou prioritu (Pre-emptive priority)

Silná priorita zajišťuje, že přijde-li do systému s obsazenými obsluhovými linkami paket, který má vyšší prioritu než paket v obsluze, je obsluha paketu s nižší prioritou přerušena nebo ukončena (pozn. podle způsobu přerušení, resp. ukončení obsluhy se silné priority dále dělí na mechanismy s dokončením obsluhy a bez dokončení obsluhy). Přijde-li do systému s obsazenými obsluhovými linkami paket se stejnou nebo nižší prioritou, než má paket v obsluze, pak je příchozí paket zařazen do fronty a jeho další zpracování se řídí číslem prioritní třídy (prioritou) a režimem fronty (obvykle FIFO).

Slabá priorita zajišťuje, že příchozí pakety jsou v případě obsazení všech obsluhových linek řazeny do fronty bez ohledu na prioritu paketů, které jsou v obsluze. Po uvolnění obsluhové linky jsou pakety brány do obsluhy podle priority a režimu fronty. V zařízeních, která se dnes běžně používají v uzlových bodech sítě (např. směrovače, přepínače), se výhradně setkáváme pouze se slabou prioritou.

Předpoklady analýzy

Zajímá-li nás, jaký přínos představuje zavedení slabé priority do uzlového bodu sítě, musíme provést analýzu vlivu priorit na zpoždění všech toků (prioritních i neprioritních). Provedení takovéto analýzy v uzlovém bodu reálné sítě by bylo náročné, ne-li nemožné, a proto přijmeme určité zjednodušující předpoklady [3], které nám umožní popsat uzlový bod sítě pomocí matematického modelu obsluhového systému s čekáním. Předpokládejme tedy, že uzlový bod sítě může být popsán pomocí obsluhového systému M+M/M/1/∞ dle Kendallovy klasifikace a že pakety jsou požadavky nabízené na tento systém. Dále předpokládejme existenci dvou prioritních tříd (tj. na systém jsou nabízeny dva toky s různou prioritou) a ustáleného stavu. Předpoklad ustáleného stavu zajišťuje, že veškeré pravděpodobnostní charakteristiky jsou časově invariantní. Záměrně byl zvolen systém s „nekonečným“ počtem míst na čekání, protože střední doba zdržení u tohoto systému je vždy větší než u systému s konečným počtem míst na čekání. S přihlédnutím k výše uvedeným předpokladům můžeme pro prioritní třídu x zavést následující pojmy:

• x číslo prioritní třídy
• A_x střední hodnota nabízeného provozního zatížení (nabídka)
• λ_x intenzita příchodů (pozn. Pokud je index x vynechán, pak platí λ=λ₁=λ₂)
• µ _x intenzita obsluhy
• t_osx střední doba obsluhy (pozn. Pokud je index x vynechán, pak platí t_os=t_os1=t_os2)
• A celková nabídka (součet A_x)
• E[D_x] střední doba zdržení

Hlavním cílem analýzy je nalézt vztah mezi základními parametry vstupních toků (střední hodnota nabízeného provozního zatížení, střední doba obsluhy) a střední dobu zdržení požadavku v systému. Nalezení tohoto vztahu je možné buď pomocí analytického řešení systému, nebo pomocí simulace.

Analytické řešení střední doby zdržení požadavku v systému M+M/M/1/∞ se slabou prioritou bylo odvozeno v [1] Proto jsou zde uvedeny pouze výsledné vztahy:

(1)

(2)

Simulační program byl napsán v programovacím jazyce Object Pascal a je založen na metodě Monte Carlo. Následující tabulka znázorňuje přehled parametrů simulace, které byly použity pro zpracování analýzy.

Analýza

První krok analýzy byl zaměřen na závislost E[D₁] na A₁ za předpokladu, že střední doba obsluhy je pro oba toky stejná. Následující obrázek ukazuje, jak je E[D₁] ovlivněna A₁, když je A₂ konstantní. Obrázek zachycuje analytické řešení i simulaci.

Obr. 1 Závislost E[D₁] na A₁

Podobně jako je znázorněna na obr. 1 závislost E[D₁] může být znázorněna závislost E[D₂] na A₁. Následující obrázek (obr. 2) zachycuje, že E[D₂] je silně ovlivněna nabídkou A₁. Všimněme si, že s růstem A₁ k hodnotě 1-A₂ dochází k prudkému růstu E[D₂] do nekonečna (1) (2). To odpovídá předpokladu, že celková nabídka na obsluhový systém nemůže být větší než počet obsluhových linek (v našem případě jedna).

Obr. 2 Závislost E[D₂] na A₁

Na obr. 1 je vidět, že E[D₁] je ovlivněna A₂. Tuto závislost podrobně zachycuje následující obrázek.

Obr. 3 Závislost E[D₁] na A₂

Z obr. 3 je zřejmé že E[D₁] závisí na A₂ lineárně,což může být vysvětleno tím, že s rostoucí nabídkou A₂ roste pravděpodobnost jevu, kdy požadavek s nižší prioritou je v obsluze právě v okamžiku příchodu požadavku s vyšší prioritou.

Doposud jsme předpokládali, že střední doba obsluhy je stejná pro oba toky. Nyní tento předpoklad opustíme a podíváme se, jak je ovlivněna E[D₁] a E[D₂] střední dobou obsluhy t_os2. Protože analytické řešení pravděpodobností stavů je předmětem dalšího výzkumu, znázorňuje následující obrázek pouze výsledky simulace.

Obr. 4 Závislost E[D₁], E[D₂] na t_os2

Závěr

Byla provedena analýza se zaměřením na střední dobu zdržení požadavků v obsluhovém systému typu M+M/M/1/∞ se slabou prioritou. Byla popsána závislost střední doby zdržení požadavků v systému na střední hodnotě nabízeného provozního zatížení a střední době obsluhy požadavků vstupních toků. Výsledky analýzy zachycují obr. 1, obr. 2, obr. 3 a obr. 4. V rámci analýzy bylo též porovnáno analytické řešení se simulací. Další práce bude zaměřena na přínos priorit z hlediska volby rozložení doby obsluhy a na vliv základních parametrů vstupních toků na rozptyl doby zdržení požadavků v obsluhovém systému.

Tento článek vznikl za podpory grantu IGS CVUT 2005, Projekt č. CTU0505213.

Literatura

[1] KONOPKA, Lukas. Delay of Packets in Queuing System with Priorities. Proceeding RTT 2005. Ostrava: VŠB 2005.
[2] GROSS, Donald. HARRIS, M. Carl. Fundamentals of Queuing Theory (Third Edition). New York: John Wiley & Sons 1998.
[3] NOVÁK, J., KŘÍŽOVSKÝ, F. Spojovací systémy I - Přednášky. Praha: ČVUT.