Výsledky výzkumu a další informace nejen
z oblasti přístupových telekomunikačních sítí.
Access server ISSN 1214-9675
Server vznikl za podpory Grantové agentury ČR.
15. ročník
Dnešní datum: 18. 11. 2017  Hlavní stránka | Seznam rubrik | Ke stažení | Odkazy  

Doporučujeme
Knihu o FTTx

Matlab server - on-line výpočty a simulace

E-learning - on-line kurzy

Trainingpoint - školení z oblasti TELCO a ICT

Kontakt
KTT FEL ČVUT
Napište nám

Redakční rada - pokyny pro autory a recenzenty

Copyright

QoS

* Analýza obsluhového systému s prioritami

Vydáno dne 05. 01. 2006 (4022 přečtení)

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
• Ax 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í λ=λ12)
• µ x intenzita obsluhy
• tosx střední doba obsluhy (pozn. Pokud je index x vynechán, pak platí tos=tos1=tos2)
• A celková nabídka (součet Ax)
• E[Dx] 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:

analyza_vz1
(1)

analyza_vz2
(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.

analyza_tab1

Analýza

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

analyza_obr1

Obr. 1 Závislost E[D1] na A1

Podobně jako je znázorněna na obr. 1 závislost E[D1] může být znázorněna závislost E[D2] na A1. Následující obrázek (obr. 2) zachycuje, že E[D2] je silně ovlivněna nabídkou A1. Všimněme si, že s růstem A1 k hodnotě 1-A2 dochází k prudkému růstu E[D2] 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).

analyza_obr2

Obr. 2 Závislost E[D2] na A1

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

analyza_obr3

Obr. 3 Závislost E[D1] na A2

Z obr. 3 je zřejmé že E[D1] závisí na A2 lineárně,což může být vysvětleno tím, že s rostoucí nabídkou A2 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[D1] a E[D2] střední dobou obsluhy tos2. 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.

analyza_obr4

Obr. 4 Závislost E[D1], E[D2] na tos2

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.



Autor:        
L. Konopka
Pracoviště: České vysoké učení technické v Praze, FEL

Informační e-mail Vytisknout článek
Projekty a aktuality
01.03.2012: PROJEKT
Výzkum a vývoj nového komunikačního systému s vícekanálovým přístupem a mezivrstvovou spoluprací pro průmyslové aplikace TA02011015

01.01.2012: PROJEKT
Vývoj adaptabilních datových a procesních systémů pro vysokorychlostní, bezpečnou a spolehlivou komunikaci v extrémních podmínkách VG20122014095

09.10.2010: PROJEKT
Výzkum a vývoj datového modulu 10 Gbit/s pro optické a mikrovlnné bezdrátové spoje, FR-TI2/621

09.01.2010: PROJEKT
Sítě s femtobuňkami rozšířené o řízení interference a koordinaci informací pro bezproblémovou konektivitu, FP7-ICT-2009-4 248891

09.11.2008: PROJEKT
Ochrana člověka a techniky před vysokofrekvenčním zářením, FI-IM5/202

20.06.2008: Schválení
Radou pro výzkum a vývoj jako recenzovaný časopis

01.04.2007: PROJEKT
Pokročilá optimalizace návrhu komunikačních systémů pomocí neuronových sítí, GA102/07/1503

01.07.2006: Doplnění sekce pro registrované

12.04.2005: Zavedeno recenzování článků

30.03.2005: Výzkumný záměr
Výzkum perspektivních informačních a komunikačních technologií MSM6840770014

29.11.2004: Přiděleno ISSN

04.11.2004: Spuštění nové podoby Access serveru

18.10.2004: PROJEKT
Optimalizace přenosu dat rychlostí 10 Gbit/s, GA102/04/0773

04.09.2004: PROJEKT
Specifikace kvalitativních kritérií a optimalizace prostředků pro vysokorychlostní přístupové sítě, NPV 1ET300750402

04.06.2004: PROJEKT
Omezující faktory při širokopásmovém přenosu signálu po metalických párech a vzájemná koexistence s dalšími systémy, GA102/03/0434

Web site powered by phpRS PHP Scripting Language MySQL Apache Web Server

NAVRCHOLU.cz

Tento web site byl vytvořen prostřednictvím phpRS - redakčního systému napsaného v PHP jazyce.
Na této stránce použité názvy programových produktů, firem apod. mohou být ochrannými známkami
nebo registrovanými ochrannými známkami příslušných vlastníků.