M/G/1 wachtsysteem

Voor dit wachtsysteem, waarbij de bedieningsduur een willekeurige kansverdeling kan hebben, beperken wij ons tot het presenteren van de Pollaczek-Khinchine-formule voor de gemiddelde wachttijd.

Van de bedieningsduurverdeling hoeft alleen het gemiddelde, , en de coëfficiënt van variatie gegeven te zijn (ofwel het eerste en tweede moment van de verdeling, want het gemiddelde is en het kwadraat van de coëfficiënt van variatie, ).

De gemiddelde wachttijd is:

Hieruit blijkt hoe de gemiddelde wachttijd bepaald wordt door de coëfficiënt van variatie van de bedieningsduurverdeling. In het geval van een constante bedieningsduur is ; dit geeft ons weer formule (5.51). Bij een negatief exponentieel verdeelde stochastische variabele is . Vergelijken we de en de wachtrij dan is de factor respectievelijk 1. Dat impliceert een verdubbeling van de gemiddelde wachttijd voor de wachtrij ten opzichte van .

De gemiddelde verblijftijd volgt direct uit (5.60) door daar de gemiddelde bedieningsduur bij te tellen:

Het is eenvoudig te verifiëren dat substitutie van 1 voor in bovenstaande formule, formule (5.16) oplevert. Nota bene .

In figuur 5.6 is een grafiek van (5.61) voor verschillende waarden van getekend. De twee extremen komen overeen met de gemiddelde verblijftijd voor respectievelijk het wachtsysteem () en het wachtsysteem (). Hier tussenin ligt de gemiddelde verblijftijd van een wachtsysteem waarbij de coëfficiënt van variatie van de bedieningsduur gelijk is aan 0.7, dus .

 
Figuur: Gemiddelde verblijftijd voor het wachtsysteem.  

Twee experts, Arie en Bernard, zijn het niet eens over hoe ze berichten zullen versturen over een 64 kbit/s link. De volgende berichten komen voor:

Elk bericht heeft ook nog 2 overhead octetten.

Arie wil de lange berichten opdelen in 4 korte berichten, dat geeft volgens hem een korte gemiddelde wachttijd omdat de berichten kort zijn en allemaal van dezelfde lengte. Bernard vind dat geen goed idee omdat er dan meer overhead is (8 octetten voor een lang bericht).

Ze besluiten de twee opties (A: opsplitsen, B: niet opsplitsen) te vergelijken op basis van de geïdealiseerde modellen en .

Gevraagd: Wat is de gemiddelde wachttijd van berichten, voordat ze op de lijn gezet kunnen worden, volgens het respectievelijk het model?

optie A:
De berichten worden verzonden in pakketten van 18 octetten lang. De aankomstintensiteit van pakketten is

De bedieningsduur is de tijd nodig om een pakket op de lijn te zetten. Dit is het aantal bits in een pakket gedeeld door de bitsnelheid van het kanaal. Dit is

De bezettingsgraad van het kanaal is dan :

Volgens (5.51) is dan de gemiddelde wachttijd van een pakket:

optie B:
De berichten worden verzonden in pakketten met lengtes van 18 en 66 octetten. De aankomstintensiteit van pakketten is:

De bedieningsduur is nu op te vatten als een toevalsgrootheid die met kans 200/225 gelijk is aan de tijd nodig om een kort pakket op de lijn te zetten en met kans 25/225 gelijk aan de tijd nodig om een lang pakket op de lijn te zetten. De gemiddelde bedieningsduur is:

De bezettingsgraad van het kanaal is dan

Voor het berekenen van de gemiddelde wachttijd hebben we nog het kwadraat van de coëfficiënt van variatie, , nodig. Met (2.27) en (2.34) berekenen we dit uit het eerste en tweede moment van de bedieningsduurverdeling:

Volgens (5.60) is dan de gemiddelde wachttijd:

In de praktijk is het vaak nog meer van belang om de overschrijdingskans van een bepaalde verblijftijd of wachttijd te kennen dan om te weten wat de gemiddelde verblijftijd of wachttijd is. Het kan bijvoorbeeld zijn dat de gemiddelde wachttijd voldoende klein is, maar dat men wil weten hoe groot de kans is dat een wachttijd van 10 maal de gemiddelde bedieningsduur overschreden wordt. Zowel gebruiker als producent van een systeem moet eisen kunnen stellen, of verifiëren, dat een bepaalde wachttijd, bijvoorbeeld, met slechts 1% kans overschreden wordt.

Voor het wachtsysteem kan de overschrijdingskans van de verblijftijd uit de verdelingsfunctie gehaald worden en bij het systeem volgen overschrijdingskansen van een geheel aantal maal de bedieningsduur uit de evenwichtsverdeling van de Markov-keten. Wat kan er nu gezegd worden van een wachtsysteem?

Het is gelukt om een eenvoudige benaderende formule te vinden voor de percentielen van de wachttijdverdeling van de wachtrij. Laat het x-de percentiel van de wachttijdverdeling zijn. Per definitie is de overschrijdingskans van gelijk aan . De benaderende formule is bijvoorbeeld voor en tot een paar promille nauwkeurig. In de gevallen die we geverifieerd hebben (alle met ) is de afwijking ten opzichte van het exacte resultaat in de orde van een paar procent of minder als en x niet te klein zijn, zeg en x > 90.

De benadering voor het x-de percentiel (de wachttijd die met kans overschreden wordt) is:

In figuur 5.7 is een nomogram gegeven waarmee eenvoudig vastgesteld kan worden hoe groot de toegestane bezettingsgraad is voor een loket als gegeven is dat een bepaalde wachttijd met 1% kans overschreden kan worden. In voorbeeld 5.6 wordt het gebruik van het nomogram nader toegelicht.

 
Figuur: Het 99-ste percentiel van de wachttijdverdeling, , versus bezettingsgraad , versus kwadraat van de coëfficiënt van variatie van de bedieningsduur .  

Gegeven een wachtsysteem met de eis dat de wachttijd met slechts 1% kans langer mag duren dan 10 maal de gemiddelde bedieningsduur.

Gevraagd:

1.   Als , wat is dan de maximaal toegestane belasting ?
2.   Indien de belasting , waar ligt dan het 99-ste percentiel van de wachttijdverdeling voor een en voor een wachtsysteem?

Bij b) is gegeven en voor en voor . De lijn vanaf 0 in de rechter kolom, door 0.69 in de middenbalk komt uit bij:

De lijn vanaf 1 in de rechter kolom, door 0.69 in de middenbalk komt uit bij