Samenvatting

In moderne, pakket-geschakelde telecommunicatiesystemen wordt informatie (zoals e-mail, geluid, beelden) getransporteerd in de vorm van kleine data-pakketjes (of ``cellen'') door een netwerk van verbindingen en routers. De Quality-of-Service (kwaliteit van de telecommunicatiedienst) die door zo'n netwerk wordt geleverd kan verslechteren door verschijnselen zoals het verloren raken van pakketjes (ten gevolge van overstroming van buffers) en onwenselijk grote vertragingen. Deze aspecten van het systeem worden goed beschreven door wachtrij-modellen; daarom is de studie van dergelijke modellen zeer relevant voor het zodanig ontwerpen van de systemen dat de telecommunicatiedienst met de gewenste kwaliteit wordt gerealiseerd. Dit proefschrift beschrijft een aantal methoden voor het efficiënt schatten van verlies-kansen in diverse wachtrijmodellen van communicatiesystemen. De nadruk ligt op de simulatie van zeldzame gebeurtenissen met behulp van importance-sampling, maar enkele analytische, asymptotische en numerieke resultaten komen ook aan de orde.

Een deel van dit proefschrift is gewijd aan zaken die te maken hebben met het schatten van de kans op ``consecutive loss'': het verliezen van meerdere opeenvolgend bij het wachtsysteem aankomende cellen. Een analytische berekening van deze kans wordt gegeven voor diverse elementaire wachtrijen (M/G/1/k en G/M/m/k), evenals een simulatieprocedure gebaseerd op importance sampling voor M/G/1/k. Bovendien wordt een M/M/1/k-wachtsysteem met meerdere bronnen beschouwd; in dit systeem wordt de kans op verlies van opeenvolgende cellen van één van deze bronnen analytisch berekend.

Het andere deel van dit proefschrift gaat over de schatting van overstromingskansen in netwerken van wachtsystemen. Hiertoe worden op importance-sampling gebaseerde simulatiemethoden beschouwd, waarbij diverse adaptieve technieken (meestal gebaseerd op cross-entropy) worden toegepast om de optimale kansmaatverandering te benaderen. Twee klassen van kansmaatverandering worden beschouwd: die welke niet expliciet van de toestand van het model afhangen (bijv. een ``statische'' verandering van de aankomst- en bedieningssnelheid), en die welke wel expliciet van de toestand van het model afhangen (bijv. een aparte wijziging van de aankomst- en bedieningssnelheid voor elke toestand). De methoden met een toestandsonafhankelijke kansmaatverandering blijken behoorlijk effectief te zijn, en resulteren in de meeste gevallen in een asymptotisch efficiënte simulatie; er zijn echter ook enkele tegenvoorbeelden gevonden. Gebruik van een toestandsafhankelijke kansmaatverandering leidt in alle geteste gevallen tot een asymptotisch efficiënte simulatie, ook in die gevallen waarin geen goede toestandsonafhankelijke kansmaatverandering bekend is. De toestandsafhankelijke methode is alleen maar toegepast op Markovse netwerken, maar enkele mogelijkheden om de methode uit te breiden tot niet-Markovse netwerken worden kort besproken. Verder beschrijft dit proefschrift een eenvoudige numerieke methode om overstromingskansen in eenvoudige Jackson-netwerken te berekenen; deze methode is gebruikt om de resultaten van bovengenoemde simulatiemethoden te controleren.

In de loop van het werk aan de twee bovengenoemde hoofdproblemen zijn ook nog enkele andere interessante subproblemen en gerelateerde zaken onderzocht. De daarbij verkregen resultaten zijn ook nuttig in andere contexten:

  1. asymptotische uitdrukkingen voor de kansverdeling van de verstreken en resterende bedieningsduur op het moment dat de inhoud van een M/G/1 wachtsysteem een hoog niveau bereikt;
  2. asymptotisch efficiënte simulatiemethoden gebaseerd op importance-sampling voor het schatten van kansen van gebeurtenissen van de vorm X_1 + X_2 + ... + X_n < Y , waar X_i positieve, onafhankelijke maar identiek verdeelde stochastische variabelen zijn, en Y ook een positieve stochastische variabele is (toepasbaar in bijv. betrouwbaarsheidsmodellen);
  3. een uitbreiding van de centrale limiet-stelling naar exponentieel getilte stochastische variabelen (toepasbaar in bewijzen van asymptotische efficiëntie).