Wachtsystemen met cyclische bediening

De toepassing van token-ring-protocollen in Local Area Networks heeft bijgedragen tot uitgebreide belangstelling voor wachtsystemen met cyclische bediening. Hierbij is er één server (het transmissie kanaal) en zijn er meer wachtrijen (de stations). De server loopt de wachtrijen cyclisch af om eventuele klanten te bedienen. (We vermijden het woord loket, omdat bij het spreken over ``een loket dat de klanten afloopt,'' de spraakverwarring compleet zal zijn).

Het model van cyclische bediening heeft ook toepassing in de analyse van een processor die verschillende stromen van taken verwerkt, zonder dat de ene stroom prioriteit heeft over de andere. Omdat we ook rekening houden met omschakeltijden kan het model ook gebruikt worden in een situatie waarbij de server na het beëindigen van een bediening niet direct aan een volgende klant kan beginnen maar eerst gedurende tenminste één omschakeltijd niet beschikbaar is.

Met een N-dimensionale toestandsruimte voor een systeem met N wachtrijen, wordt een exacte analyse van bijvoorbeeld de evenwichtsverdeling zeer complex. Alleen voor speciale gevallen, zoals N=2 of een systeem waarbij alle N wachtrijen dezelfde parameters hebben, zijn er exacte oplossingen gevonden. Voor algemenere gevallen zij er diverse benaderende oplossingen.

In 1987 publiceerden Boxma en Meister in het tijdschrift Performance Analysis een goede benadering die practisch bruikbaar en vrij algemeen is. In deze sectie willen wij deze benadering presenteren en een toepassing geven. De benadering geeft een uitdrukking voor de gemiddelde wachttijd voor elke wachtrij.

Het model is geïllustreerd in figuur 5.8. De aankomsten van klanten bij elke wachtrij (queue) worden verondersteld een Poisson-proces te vormen. De aankomstintensiteit bij wachtrij i is . De bedieningsduur van een klant kan willekeurig verdeeld zijn, waarbij alleen het eerste moment en het tweede moment gegeven hoeft te zijn. De index i geeft aan dat elke wachtrij zijn eigen bedieningsduurverdeling kan hebben.

 
Figuur: Nummero's i-1, i en i+1 van N wachtrijen met cyclische bediening.  

Met een omschakeltijd kan bijvoorbeeld voor een token-ring LAN de tijd gemodelleerd worden die het LAN nodig heeft om de permissie tot zenden (de token) door te geven van station i naar station i+1. In het algemene model is de omschakeltijd een stochastische variabele. De tijd die verstrijkt na beëindiging van bediening bij queue i, totdat de volgende bediening bij queue i+1 begint is een stochastische variabele met gemiddelde en variantie .

De wachtrijen zijn genummerd . Na wachtrij i is wachtrij i+1 aan de beurt. De term i+1 moet ook zo opgevat worden dat na wachtrij N wachtrij 1 weer aan de beurt is; we hebben het immers over cyclische bediening.

We definiëren nog de volgende grootheden (uitgedrukt in aankomstintensiteit , gemiddelde bedieningsduur en gemiddelde omschakeltijd ):

De tijd die nodig is voor één volledige cyclus is een stochastische variabele die we aangeven met . We kunnen beredeneren wat de verwachtingswaarde van is. Namelijk, het gemiddelde aantal klanten dat per cyclus aankomt bij wachtrij i is . De hoeveelheid werk die dit met zich meebrengt is . Zoveel tijd moet de server ook gemiddeld per bezoek aan wachtrij i besteden. Daarna volgt een omschakeltijd van gemiddeld . Voor de hele cyclus sommeren we dit van i=1 tot en met i=N om de gemiddelde cyclustijd te krijgen:

Hieruit kunnen we oplossen:

Zolang de evenwichtsverdeling bestaat, is dit resultaat algemeen geldig. Het is onafhankelijk van de wijze van bedienen: exhaustive (alle aanwezige klanten bij wachtrij i worden in één bezoek van de server bediend) of non-exhaustive (ten hoogste één klant per wachtrij wordt bediend per bezoek van de server).

De evenwichtsverdeling bestaat alleen indien voor elke wachtrij het aanbod van klanten kleiner is dan wat er per cyclus verwerkt wordt. De voorwaarde voor het bestaan van de evenwichtsverdeling kan inzichtelijk gemaakt worden voor het model dat de server doorgaat naar de volgende wachtrij nadat een klant van een wachtrij bediend is (non-exhaustive service). In dat geval moet voor elke wachtrij de verwachtingswaarde van het aantal klanten dat aankomt per cyclus kleiner dan 1 zijn: , voor elke waarde van i. Dit leidt direct tot de volgende evenwichtsvoorwaarde:

De benaderingsformule van Boxma en Meister geldt voor non-exhaustive service. De formule is op het eerste gezicht wat indrukwekkend, maar, zoals we zullen zien zijn in de toepassingen sommige termen gelijk aan nul of zijn bijvoorbeeld alle termen van een sommatie aan elkaar gelijk.

De gemiddelde wachttijd bij queue i wordt gegeven door:

Vaak zal men te maken hebben met modellen waarbij alle wachtrijen verondersteld worden dezelfde aankomstintensiteit en bedieningsduurverdeling te hebben. Als dan ook de omschakeltijd onafhankelijk is van i spreken we van een symmetrisch model. In het symmetrische geval is formule (5.101) niet meer een benadering, maar geeft exact de gemiddelde wachttijd.

In het asymmetrische geval is de formule een betere benadering naarmate alle wachtrijen verder van verzadiging zijn, d.w.z. naarmate voor alle i de waarden van het product verder van 1 ligt.

30 PC's moeten verbonden worden met een file-server voor het vastleggen van de transacties die met de PC gedaan worden. Men eist van de data-communicatie verbinding dat de gemiddelde responstijd (=wachttijd + transmissietijd) kleiner is dan 200 ms. De berichten die verzonden worden naar de file-server hebben een lengte van 1000 octetten. De tijd die verstrijkt tussen het genereren van twee opeenvolgende berichten vanuit één PC veronderstellen we negatief exponentieel verdeeld. Gemiddeld genereert één PC 1 bericht per seconde.

Arie stelt voor om de PC's via één 1 Mbit/s token-ring met de file-server te verbinden. Ondanks de omschakeltijd van 5 ms tussen ``einde transmissie'' van de ene PC en ``begin transmissie'' van de volgende, zou dit snel genoeg moeten zijn.

Bernard wil elke PC een vaste 64 kbit/s verbinding geven met de file-server. ``Want,'' zegt hij, ``die token-ring is nog niet eens 16 keer sneller dan zo'n vaste verbinding (dan praat ik nog niet over de omschakeltijden) dus kan je daarmee nooit 30 PC's aan.''

Gevraagd: Wat is voor de twee verschillende opties de gemiddelde responstijd?

Voor de optie van Arie (token-ring) passen we formule (5.101) toe. Eerst zetten we de benodigde parameters op een rijtje:

Invullen geeft dan:

Bij deze wachttijd moeten we nog optellen de transmissie-tijd

om te komen tot een responstijd van

Voor de optie van Bernard is het model van toepassing voor elke PC. De transmissietijd wordt verkregen door de berichtlengte, 8000 bits, te delen door de transmissiesnelheid 64000 bit/s. Dit geeft:

De responstijd wordt gegeven door (5.52) met voor ingevuld de waarde van , en voor de waarde van . Dit geeft: