Kendallova klasifikace obsluhových systémů

Autor: P. Hampl <hamplp(at)fel.cvut.cz>, Pracoviště: České vysoké učení technické v Praze, FEL, Téma: QoS, Vydáno dne: 29. 12. 2005

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:

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í

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.