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: 24. 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

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

Vydáno dne 16. 12. 2005 (6517 přečtení)

Rozdílný charakter datového a multimediálního toku vedl s rozvojem multimediálních služeb ke zvýšení nároků na datové sítě. Obzvláště citlivou se ukázala otázka zpoždění paketů multimediálního toku.


Queuing service system and request mean delay time
Abstract
Different character of data and multimedia stream, along with development of multimedia services, led to increase of requirements for data networks. Delay of multimedia stream packet became a very sensitive problem to solve in those networks.


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ť λ1, λ2 jsou intenzity příchodů (pozn. λ1 je intenzita prioritního toku.), λ12 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ů pm,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.

zdrzeni_v1
(1)

Pozn. p0 odpovídá p0,0,0 . p0=1-λ/µ.

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

zdrzeni_v2
(2)

H(y,z) je generující funkce pro dvě prioritní třídy bez ohledu na to, který požadavek je v obsluze. Všimněme si, že H(1,1)=1, H1(1,1)=λ1/µ , H2(1,1)=λ2/µ a p0=1-λ/µ. Označme střední počet požadavků v systému jako E[X1] a E[X2]. Potom platí

zdrzeni_v3
(3)

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

zdrzeni_v4
(4)

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

zdrzeni_v5
(5)

zdrzeni_v6
(6)

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

zdrzeni_v7
(7)

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

zdrzeni_v8
(8)

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

zdrzeni_v9
(9)

zdrzeni_v10
(10)

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

zdrzeni_v11
(11)

Užitím (4) dostaneme pro E[X1] a E[X2]

zdrzeni_v12
(12)

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 A1=A2=0,1 erl (A11/µ A22/µ. Intenzita obsluhy je pro oba toky stejná µ=1/tos =1/120. Dále předpokládejme, že tok s nabídkou A1 je prioritní (tj. má vyšší prioritu než tok s nabídkou A2 ), 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.

zdrzeni_t1

Kromě výsledku příkladu jsou uvedeny v tabulce č.1 výsledky pro další velikosti nabídek A1, A2 a pro různé velikosti střední doby obsluhy tos. 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.

zdrzeni_obr1

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

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

zdrzeni_obr2

Obr. 2 Závislost střední doby zdržení E[D1] na nabídce A2

Na obrázku č. 2 je znázorněna závislost střední doby zdržení prioritního toku E[D1] na nabídce neprioritního toku A2. Jedná se o lineární závislost naznačující, že velikost nabídky A2 ovlivňuje střední dobu zdržení prioritního toku E[D1] . 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 A2 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[D1].

zdrzeni_obr3

Obr. 3 Závislost střední doby zdržení E[D2] na nabídce A1

zdrzeni_obr4

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

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

Závěr

Příspěvek se zaměřuje na odvození střední doby zdržení toků o intenzitách λ1 a λ2, 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



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ů.