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

* Kendallova klasifikace obsluhových systémů

Vydáno dne 29. 12. 2005 (24697 přečtení)

Pro stručné a přehledné vyjádření typu obsluhového systému v teorii hromadné obsluhy se vžilo použití Kendallovy klasifikace. Cílem tohoto článku je seznámit čtenáře se základním členěním obsluhových systémů a použitím Kendallova značení.


Kendall classification of service systems
Abstract
To present service system in waiting-line theory in a short and general way the Kendall classification is used. Purpose of this paper is to show to the reader basic segmentation of service system and signification of Kendall use.


Popis obsluhového systému

Pod pojmem systém hromadné obsluhy1 nebo též zkráceně obsluhový systém (OS) si můžeme představit jakýkoliv systém zajišťující obsluhu požadavků (zákazníků), jež obsluhu po systému požadují. Obsluhové systémy jsou součástí našeho každodenního života aniž si to vlastně uvědomujeme. Například pokud někde čekáme (na vlak, u pokladny na lístek do kina, u lékaře) jsme vlastně zákazníkem (požadavkem) daného obsluhového systému. Systémy hromadné obsluhy samozřejmě nalezneme i v telekomunikacích, kde se například používají pro dimenzování svazků, spojovacích polí, řídících prvků ...

image01

Obr. 1 Schéma jednoduchého obsluhového systému

Schéma jednoduchého obsluhového systému je znázorněno na obr 1. Pro popis obsluhových systému se používá model skládající se z:

  • N obsluhových linek (serverů) určených k obsluze požadavků přicházejících z S zdrojů,
  • R míst určených k čekání požadavků,
  • řízení obsluhového systému (formálně uvedeno pro úplnost).

Požadavky, které systém obsluhuje, vznikají ve zdrojích a přicházejí jako tzv. vstupní tok do obsluhového systému. Při vstupu požadavku do systému, je řízením OS rozhodnuto, bude-li požadavek systémem obsloužen, nebo bude odmítnut. Při přijetí požadavku do systému je buď přímo započata obsluha daného požadavku (pokud je volná obsluhová linka), nebo požadavek čeká na obsluhu. Po skončení obsluhy požadavek opouští obsluhový systém a stává se součástí výstupního toku obsloužených požadavků.

Kendallova klasifikace

Je tomu již přes padesát let od doby, kdy David George Kendall publikoval [1] své značení OS:

A / B / N , (1)

význam jednotlivých písmen je uveden v tab.1.

Tab.1: Význam písmen Kendallova značení
písmeno popis
A distribuční funkce intervalů mezi příchody
B distribuční funkce doby obsluhy
N počet obsluhových linek (přirozené číslo nebo symbol ∞)

Původní Kendallovo značení (1) ponechává neurčeny další důležité charakteristiky systému jakými jsou: maximální počet čekajících (délka fronty), způsob výběru zákazníků z fronty, atd. O tyto údaje bylo postupně původní Kendallovo značení rozšířeno [3]:

A / B / N / K / S / X (2)

význam prvních tří písmen zůstává shodný s původním Kendallovým značením (tab. 1) a význam rozšiřujících písmen je uveden v tab. 2.

Tab.2: Význam písmen rozšiřujících původní Kendallovo značení
písmeno popis
K maximální počet požadavků v systému (počet obsluhových linek plus počet míst pro čekající , K=N+R) nebo pouze počet míst pro čekající (K=R)
S počet zdrojů požadavků (zákazníků), neuvádí se pokud je nekonečný
X režim fronty: FCFS (First Come - First Served), FIFO (First In - First Out), FCLS (First Come - Last Served), LIFO (Last In - Last Out), SIRO (Service In Random Order), RAND(Random)

Je nutné upozornit na jistou nejednoznačnost použití čtvrtého písmene K. Autoři na tomto místě uvádějí buď maximální počet požadavků v systému (K=N+R) nebo jen počet míst pro čekající požadavky.

Na pozicích písmen A a B se vžilo použití následujících písmen značících danou distribuční funkci intervalů mezi jednotlivými příchody (pro A) nebo distribuční funkci doby obsluhy (pro B):

M ~ Exponenciální rozložení intervalů mezi příchody, (doby obsluhy)
D ~ Deterministické (konstantní intervaly mezi příchody nebo konstantní doba obsluhy)
Ek ~ Erlangovo rozložení k-tého řádu (E1=M)
Hk ~ Hyperexponenciální rozložení k-tého řádu
Kn ~ rozložení s n stupni volnosti
GI ~ nezávislé příchody (General Independent)
G ~ obecné (General), tj. jakékoliv rozložení
GMPP ~ Generally Modulated Poisson Process: - poissonovský proces s proměnnou intenzitou
MMPP ~ Markov Modulated Poisson Process (Markovovsky modulovaný poissonovský proces): - speciální případ GMPP (intenzita se mění (moduluje) Markovovským řetězcem)
SPP ~ Switched Poisson Process (přepínaný poissonovský proces): - jde o dva vzájemně se střídající poissonovské procesy (M)
IPP ~ Interrupted Poisson Process (přerušovaný poissonovský proces): - speciální případ SPP, kde intenzita jednoho z toků je nulová

Pro dimenzování telekomunikačních sítí založených na spojování okruhů se nejčastěji používá Markovovský model M/M/N/0. Avšak s postupným rozvojem nových telekomunikačních služeb (převážně multimediálních) se začal významně měnit i charakter vstupních toků nabízených těmto systémům a také charakter doby obsluhy. Tato výrazná změna vedla k tvorbě nových modelů [4]. Mezi dnes nejpoužívanější patří MMPP/M/N/0, IPP/M/N/0.

Dalším významným milníkem v teorii hromadné obsluhy bylo zavedení systémů pracujících s diskrétním časem (ve všech doposud uvedených rozloženích je čas uvažován jako spojitý). Pro systémy tohoto typu se začaly vyvíjet nové modely [4] :

GEOM ~ geometrické rozložení: - Bernoulliho proces
GMDP ~ Generally Modulated Deterministic Process: - determinstický proces s proměnnou intenzitou
MMDP ~ Markov Modulated Deterministic Process (Markovovsky modulovaný deterministický proces): - speciální případ GMDP (změna intenzity je určena Markovovským řetězcem)
SDP ~ Switched Deterministic Process (přepínaný deterministický proces)
IDP ~ Interrupted Deterministic Process (přerušovaný deterministický proces)
SBBP ~ Switched Batch Bernoulli Process: - zvláštní případ Bernoulliho procesu se skupinovými příchody [5]

Pozn.: V případě prioritních toků nebo priorit v obsluze se lze setkat s označením ® nad daným písmenem.

Příklady použití Kendallova značení

  • M / M / N / 0 - jde o Erlangův model:
    • exponenciální rozložení intervalů mezi příchody (systém s poissonovským vstupním tokem),
    • exponenciálně rozdělená doba obsluhy,
    • N obsluhových linek,
    • počet míst pro čekající R=0, OS se ztrátou (bez možnosti čekání).
  • H2 / D / 1 / ∞
    • hyperexponenciální rozložení intervalů mezi příchody (druhého řádu),
    • doba obsluhy je konstantní (neměnná pro všechny požadavky),
    • systém má jednu obsluhovou linku pro obsluhu přicházejících požadavků,
    • délka fronty není omezena,
    • vzhledem k tomu, že není uveden režim fronty, implicitně se předpokládá režim fronty FIFO.
  • M+M / D+Ek / N / 0
    • vstupní tok se skládá z dvou rozdílných (nezávislých) vstupních toků typu M (každý má jinou intenzitu λ),
    • doba obsluhy požadavků prvního vstupního toku je konstantní a doba obsluhy požadavků druhého vstupního toku má Erlangovo rozložení k-tého řádu,
    • systém má N obsluhových linek,
    • příchozím požadavkům není dovoleno čekat na obsluhu, pokud nejsou přímo vzaty do obsluhy, jsou systémem odmítnuty (systém se ztrátami).

Popis nejčastěji používaných rozložení

Pro distribuční funkce F, hustoty pravděpodobnosti f, střední hodnoty E a rozptyly D platí následující vztahy:

  1. Exponenciální rozložení (M):

    - distribuční funkce:
    image02
    (3)
    - hustota pravděpodobnosti:
    image03
    (4)
    - střední hodnota a rozptyl:
    image04
    image05
    (5)
  2. Rozložení s pravidelnými (deterministickými) příchody (D):

    - distribuční funkce:
    image06
    (6)
    - frekvenční funkce:
    image07

    a

    image08
    (7)
    - střední hodnota a rozptyl:
    image09
    image10
    (8)
  3. Erlangovo rozložení k-tého řádu (Ek):

    - distribuční funkce:
    image11
    (9)
    - hustota pravděpodobnosti:
    image12
    (10)
    - střední hodnota a rozptyl:
    image13
    image14
    (11)
  4. Hyperexponenciální rozložení k-tého řádu (Hk):

    - distribuční funkce:
    image15
    image16
    image17
    (12)
    - hustota pravděpodobnosti:
    image18
    (13)
    - střední hodnota a rozptyl:
    image19
    image20
    (14)

Distribuční funkce a hustoty pravděpodobnosti výše uvedených rozložení jsou zobrazeny na obrázcích č. 2 a 3.

image21

Obr. 2 Hustoty rozložení f(t) M, Ek, D a Hk pro E(t) = 120 s

image22

Obr. 3 Distribuční funkce F(t) rozložení M, Ek, D a Hk pro E(t) = 120 s

Z obr. 2 a 3 je zřejmé, že exponenciální rozložení tvoří „hranici“ mezi hyperexponenciálním a Erlangovým rozložením. Rozložení s pravidelnými příchody je limitním případem Erlangova rozložení k-tého řádu pro k®, při konstantní střední hodnotě.

Závěr

Cílem článku bylo seznámit čtenáře s Kendallovou klasifikací a podat přehledný návod k použití Kendalova značení. Další vývoj v oblasti teorie hromadné obsluhy si sice vyžádal rozšíření o další prvky značení (K, S, X) oproti původnímu Kendallovu návrhu. Přesto však je nutné zdůraznit, že pravě David George Kendall se svým uceleným pohledem na třídění OS, významnou měrou přispěl k zjednodušení zápisu a zpřehlednění dělení různých typů systému hromadné obsluhy.

Tento příspěvek vznikl za podpory grantu FRVŠ "Dimenzování obsluhového systému pro multimediální služby" č.: 2477/2005 a v rámci projektu NPV 1ET300750402.

Literatura a odkazy

[1] Kendall, D. G. Stochastic processes occurring in the theory of queues and their analysis by the method of the imbedded Markov chain. In The Annals of Mathematical Statistics Vol.24, 1953, s. 338–354.
[2] Biography - from St.Andrews University [online]. 1998 [cit. 2005-11-16]. Dostupný z WWW: <http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Kendall.html>.
[3] ITC, ITU-D SG2. Handbook “TELETRAFFIC ENGINEERING”. 2005. 350 s. Dostupný z WWW: <http://oldwww.com.dtu.dk/teletraffic/handbook.html>.
[4] ROBERTAZZI, T. G. Computer Network and Systems: Queueing Theory and Performance Evaluation. 3rd edition. Springer, 2000. 410 s. ISBN 0-387-95037-0.
[5] HASHIDA, O., TAKAHASHI, Y., SHIMOGAWA, S. Switched Batch Bernoulli Process(SBBP) and the Discrete-Time SBBP/G/1 Queue with Application to Statistical Multiplexer Performance. In IEEE Journal on Selected Areas in Communicatins. 1991. ISSN 0733-8716 .
[6] Bibliografické citace [online]. 2004-2005 [cit. 2005-11-16]. Dostupný z WWW: <http://www.citace.com/>.




1 Systém hromadné obsluhy poskytuje obsluhu většímu počtu zákazníků, nejde tedy o jednorázové posloužení jednotlivci.


Autor:        P. Hampl
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ů.