Hoofdstuk 5: wachtlijnmodellen in discrete tijd en hun toepassing bij de prestatie-analyse van telecommunicatiesystemen • Inleiding • Buffers en buffergedrag • Enkele concrete toepassingen I statistische multiplexers I schakelelementen • Bufferanalysetechnieken I I I I de analytische methode de numerieke methode computersimulatie experimentering • Typische resultaten en praktisch nut van bufferanalyse • Wiskundige beschrijving van discrete-tijd-buffersystemen I buffersystemen, opslagcapaciteit, wachtlijndiscipline, synchrone transmissie, ingangsproces, uitgangsproces • Verkorte notatie voor discrete-tijd-buffersystemen • Evenwichtsvoorwaarde en performantie van buffersystemen • De stelling van Little • Discrete toevalsgrootheden en genererende functies I discrete toevalsgrootheden en massafuncties I genererende functies I inverteren van genererende functies 1 Inleiding tot hoofdstuk 5 • In vorige hoofdstukken I analyse van elementaire (zuiver Markoviaanse) wachtlijnmodellen in continue tijd I geen bespreking van meer complexe modellen in continue tijd zoals M |G|1 of G|M |m • In hoofdstukken 5 en 6 I introductie tot discrete-tijd-wachtlijntheorie I gebruikte wiskundige technieken zijn wel zeer analoog als degene die bij M |G|1 of G|M |m aan bod zouden komen I bespreking van enkele (relatief eenvoudige) modellen en analysetechnieken uit de discrete-tijd-wachtlijntheorie I toepassing hiervan bij de studie van “buffers” voor de tijdelijke opslag van digitale informatie in telecommunicatiesystemen en –netwerken 2 Buffers • Algemeen I buffers worden in (moderne) digitale communicatiesystemen en –netwerken gebruikt voor de tijdelijke opslag van informatie, wanneer deze informatie niet onmiddellijk kan worden verstuurd naar haar bestemming, op het ogenblik dat zij gegenereerd wordt of in een bepaald punt van het systeem of netwerk aankomt I buffers zijn aanwezig in diverse types van netwerkelementen • Enkele voorbeelden I statistische multiplexers (statistical multiplexers), die gebruikt worden om een veelheid aan gebruikers toe te laten dezelfde communicatiekanalen op een effici¨ente manier met elkaar te delen I schakelelementen (switching elements) en schakelnetwerken (switching networks), gebruikt in de knooppunten van communicatienetwerken, om informatie door te schakelen naar de juiste bestemming I snelheidsaanpassers (rate adapters), die de overgang verzorgen tussen kanalen met verschillende transmissiesnelheden I verkeersomvormers (traffic shapers), die gebruikt worden om onregelmatige of grillige (“bursty”) informatiestromen om te zetten naar verkeerspatronen (“traffic patterns”) met gunstiger statistische eigenschappen I herordeningseenheden (resequencing units), die tot taak hebben de originele volgorde te herstellen van sequenties van (samenhorende) informatie-eenheden wanneer deze orde in de loop van het transport over het communicatiesysteem werd verstoord 3 Omstandigheden waarin buffers gebruikt worden • Buffers worden onder meer gebruikt I wanneer het genereren van informatie niet goed is afgestemd op de transportmogelijkheden van het systeem ∗ transportmogelijkheden zijn doorgaans vrij deterministisch ∗ b.v. een communicatiekanaal heeft gewoonlijk een vaste transmissiesnelheid, uitgedrukt in bits per seconde ∗ informatiebronnen (traffic sources) of gebruikers (users) van een netwerk genereren vaak informatie op een meer onregelmatige wijze ∗ b.v. periodes van hevige activiteit afgewisseld met (lange) passieve periodes I wanneer er een zekere vorm van competitie bestaat tussen verschillende informatiestromen voor wat betreft het gebruik van een gemeenschappelijke communicatie-infrastructuur I wanneer de communicatiekanalen waarlangs de informatie wordt verstuurd onderhevig zijn aan storingen of onderbrekingen I wanneer een herordening van informatie-eenheden (of een egalisatie van hun tijdsvertragingen) is vereist ∗ verschillende eenheden van een informatiestroom kunnen verschillende paden met verschillende geassocieerde tijdsvertragingen hebben gevolgd • Taak van buffers I tijdelijk overaanbod van informatie opvangen in afwachting van latere gelegenheid tot verzending • Buffers zijn bijzonder soort wachtlijnsystemen I klanten zijn de te versturen informatie-eenheden I servers zijn de kanalen waarlangs de informatie verstuurd wordt I bediening correspondeert met de transmissie van informatie uit de buffer 4 Buffergedrag • Belang van inzicht in het gedrag van buffers I performantie van een digitaal communicatiesysteem kan er in belangrijke mate mee samenhangen I er kan informatieverlies (loss) optreden wanneer een buffer helemaal volzet raakt I een informatiestroom kan ongewenste tijdsvertragingen (delay) of vertragingsvariaties (delay variation) ondergaan in een buffer I (variabele) tijdsvertragingen zijn vooral schadelijk voor zgn. real time diensten zoals bijvoorbeeld spraak (voice) of videoconferenties, maar vormen niet zo’n groot probleem voor bijvoorbeeld computergegevens (data) I informatieverlies wordt beter verdragen door spraak (vanwege de aanwezige redundantie), maar kan absoluut niet getolereerd worden bij data 5 Buffers en discrete-tijd-wachtlijntheorie • Synchrone transmissie - discrete tijd I gegevens worden opgesplitst in blokken van vaste of variabele lengte, gewoonlijk pakketten (packets) genaamd I andere termen: cellen (cells), data-eenheden (data units), berichten (messages), . . . , afhankelijk van de context I pakketten worden als onafhankelijke entiteiten verstuurd en hun transmissietijd is eveneens constant of variabel I tijd wordt ingedeeld in slots of tijdsslots (time slots) van vaste lengte, zodanig dat per slot een vaste hoeveelheid informatie kan verstuurd worden I de opeenvolgende transmissies van pakketten worden gesynchroniseerd op de vooraf vastgelegde slotgrenzen I in geval van pakketten van vaste lengte volstaat 1 slot gewoonlijk precies voor de transmissie van 1 pakket I voor pakketten van variabele lengte kunnen 1 of meerdere slots vereist zijn I gezien de slotgrenzen een rij van discrete tijdstippen vormen, is discrete-tijd-wachtlijntheorie het middel bij uitstek om het gedrag van hoger vermelde buffers te bestuderen • Trafiekstudies I trafiekstudies bestuderen het wachtlijntheoretisch gedrag van informatiestromen in een telecommunicatienetwerk I belangrijk toepassingsgebied: breedbandige ge¨ıntegreerde digitale netwerken, gebaseerd op de ATM-technologie (ATM = Asynchronous Transfer Mode) of de IP-technologie (IP = Internet Protocol) I in hoofdstukken 5 en 6 is er een zekere wisselwerking tussen fundamenteel theoretische concepten en meer toepassingsgerichte aspecten 6 Performantiematen van buffers • Belangrijkste kenmerkende grootheden van buffers I bufferbezetting I verlieskans I vertragingstijd • Bufferbezetting (buffer occupancy, buffer contents) I geeft hoeveelheid in de buffer opgestapelde informatie aan, uitgedrukt in een geheel aantal pakketten, al dan niet inclusief de pakketten wiens transmissie aan de gang is I gewoonlijk gemodelleerd als een discrete toevalsveranderlijke en gekarakteriseerd aan de hand van de bijhorende distributie (via massafunctie of genererende functie), de momenten, de quantielen of percentielen, ... • Verlieskans (loss probability) of verliesfractie (loss fraction, loss ratio) I kans om pakketten te verliezen ten gevolge van een volle buffer I fractie van alle zich bij de buffer aanbiedende pakketten die in de buffer niet binnenraken omdat hij helemaal volzet is • Vertragingstijd (queueing delay, delay) I totale tijd (uitgedrukt in een geheel aantal slots) die een pakket doorbrengt in de buffer tussen aankomst en vertrek, al dan niet inclusief de tijd vereist voor transmissie I discrete toevalsveranderlijke, gekenmerkt aan de hand van hetzij zijn distributie (massafunctie, genererende functie), hetzij zijn momenten, hetzij zijn quantielen of percentielen, ... 7 Toepassing: statistische multiplexers • Conceptueel diagram gebruikers slot buffer 1 2 N communicatiekanaal pakket • Werking I I I I I I I I I N gebruikers willen pakketten versturen over zelfde kanaal tijd ingedeeld in slots: 1 slot vereist voor transmissie van 1 pakket verschillende markeringen voor verschillende gebruikers als meerdere gebruikers een pakket wensen te versturen tijdens hetzelfde slot, treedt er een transmissieconflict op pakketten die niet ogenblikkelijk kunnen worden verstuurd worden een tijdlang opgeslagen voor latere verzending multiplexer beschikt hiertoe over bufferruimte in de multiplexer worden pakketten van verschillende gebruikers door elkaar gemengd op toevallige wijze: statistische multiplexer zolang de buffer niet ledig is, worden pakketten uit de buffer verstuurd aan een tempo van 1 pakket per slot effici¨ente techniek: kanaal is in gebruik van zodra tenminste 1 gebruiker informatie te versturen heeft 8 Toepassing: schakelelementen • Conceptueel diagram buffers 1 1 2 2 N N ingangen uitgangen • Werking I systeem met N ingangen en N uitgangen I op elke ingang aankomst van ten hoogste 1 pakket per slot I elk van deze pakketten kan bestemd zijn voor elk van de N mogelijke uitgangen van het schakelelement (routering) I taak van schakelelement bestaat erin aankomende pakketten door te geven naar gewenste uitgang(en) I aparte markeringen alnaargelang de bestemming der pakketten I als tijdens zelfde slot op meerdere ingangen pakketten aankomen voor zelfde uitgang: uitgangsconflict I oplossing: een aantal pakketten een tijdlang opslaan I schakelelement heeft daarom nood aan bufferruimte I buffers kunnen aan de uitgangszijde (zie figuur) of de ingangszijde of zelfs in een intermediaire positie voorzien worden I uitgangsbuffers voor individuele uitgangen strikt gescheiden of 1 enkele gemeenschappelijke bufferruimte (shared buffer) voor alle bestemmingen samen (effici¨enter) 9 Bufferanalysetechnieken - 1 • Bedoeling van bufferanalyse I gedrag van buffers bepalen in termen van de gebruikelijke prestatiematen: bufferbezetting, verlieskans, vertragingstijd • De analytische methode I vertrekpunt: mathematisch model voor buffersysteem in kwestie (aankomstproces, bedieningsproces, opslagcapaciteit, gebruikte wachtlijndiscipline, . . . ) I gebaseerd op inzicht in de mechanismen die het buffergedrag bepalen: opstellen van systeemvergelijkingen die een verband leggen tussen de relevante performantiegrootheden (bufferbezetting, vertragingstijd) en de modelparameters I gebruik van wiskundige technieken om te komen tot een analytische “oplossing” van de systeemvergelijkingen, waaruit dan formules in gesloten of halfgesloten gedaante worden afgeleid voor de gewenste performantiematen • De numerieke methode I analoog als analytische methode, maar systeemvergelijkingen worden numeriek opgelost I numerieke waarden i.p.v. symbolische waarden voor alle modelparameters I vereist effici¨ente numerieke procedures om grote matrices te inverteren, eigenwaarden en eigenvectoren te zoeken, . . . I parameterafhankelijkheid van bekomen resultaten is minder evident, vermits numerieke procedure moet worden herbegonnen voor elke individuele keuze van modelparameters • Complexiteit van de berekeningen kan gereduceerd worden I specifieke structuur van buffermodel benutten 10 Bufferanalysetechnieken - 2 • Computersimulatie I buffer wordt gesimuleerd, d.w.z. nagebootst in software I gebruik van randomgeneratoren om aankomsten in de buffer en vertrekken uit de buffer te simuleren I buffergedrag wordt bekomen uit “metingen” op softwareversie van systeem (bijhouden van tellers, opbouwen van histogrammen) I voordeel: om het even welk systeem, hoe complex ook, kan gesimuleerd worden I nadelen: ∗ parameterafhankelijkheid van de resultaten slechts moeizaam te bekomen ∗ (voor gegeven parameterwaarden) allerlei speciale voorzieningen en mogelijks zeer lange simulatietijden vereist om betrouwbare resultaten te verkrijgen ∗ vooral moeilijk voor fenomenen die slechts met een heel lage probabiliteit optreden (rare events) I redenen: ∗ in geval van simulatie bestudeert men in feite slechts 1 (of een beperkt aantal) realisatie(s) van het buffergedrag, waarvan niet a priori verzekerd is dat deze wel typisch is (of zijn) ∗ fenomeen dat men wenst te bestuderen moet in de loop van de simulatie een voldoend aantal keren optreden • Experimentering I gelijkaardig met computersimulatie, maar metingen worden uitgevoerd op het werkelijke fysische systeem (of op een prototype) I voordeel: absolute zekerheid dat alle mogelijke aspecten van het systeem op correcte manier in rekening worden gebracht I nadeel, naast de nadelen reeds vermeld bij computersimulatie, is dat men het systeem werkelijk fysisch moet bouwen 11 Typische resultaten en praktisch nut van bufferanalyse • Klassieke resultaten van bufferanalyse I grafiek van gemiddelde bufferbezetting of gemiddelde vertragingstijd als functie van de bezettingsgraad of belasting (load) I belasting = verhouding van de snelheid waarmee informatie zich aan de ingang van de buffer aanbiedt tot de snelheid waarmee informatie uit de buffer kan verwijderd worden I grafiek van variantie op bufferbezetting of vertragingstijd als functie van de belasting I grafiek van staartprobabiliteiten (tail probabilities) van bufferbezetting (of vertragingstijd), d.w.z. kans dat bufferbezetting (of vertragingstijd) meer zou bedragen dan X pakketten (of X slots) als functie van X, voor grote waarden van X – grafiek van verlieskans (packet loss ratio of PLR) in eindige buffer met opslagruimte voor X pakketten, als functie van X • Praktische toepassingen van bufferanalyse I bij ontwerp: dimensionering van buffers in netwerkelementen met het oog op het verzekeren van een vooropgegeven maximale verlieskans I bij ontwerp: schatten van tijdsvertraging (packet transfer delay) tengevolge van buffering en grootte van de mogelijke variatie hierop (delay jitter, packet delay variation) I operationeel: bepaalde vormen van verkeersregeling (traffic control), bijvoorbeeld call acceptance control of connection admission control (CAC) I mogelijke CAC-regel: nieuwe verbindingen slechts aanvaard zolang verlieskans in (ingangs)multiplexer beneden zekere drempelwaarde blijft I vereist kennis van verlieskans voor gegeven ingangsverkeer en derhalve bufferanalyse 12 Wiskundige beschrijving van discrete-tijd-buffersystemen - 1 • Bedoeling I abstracte beschrijving van buffersystemen los van eventuele praktische toepassingen uit de telecommunicatiewereld • Belangrijkste elementen I I I I I algemene structuur van een buffersysteem opslagcapaciteit wachtlijndiscipline synchrone transmissie ingangsproces ∗ globale of meer gedetailleerde beschrijving ∗ tussenaankomsttijden of aantal aankomsten per slot I uitgangsproces ∗ aantal uitgangskanalen ∗ transmissietijd ∗ beschikbaarheid van de uitgangskanalen ∗ synchrone aard van de transmissie • Verkorte notatie voor discrete-tijd-buffersystemen I uitbreidingen van Kendall-notatie voor discrete tijd 13 Wiskundige beschrijving van discrete-tijd-buffersystemen - 2 • Algemene structuur van een buffersysteem BUFFERSYSTEEM ingangslijnen uitgangslijnen I buffer of buffersysteem is tijdelijke opslagplaats voor digitale informatie die wacht om verstuurd te worden I werking is principieel eenvoudig: ∗ pakketten komen in het buffersysteem aan via de ingangslijnen (input lines) of ingangskanalen (input channels) ∗ in de buffer wachten zij hun beurt af om naar hun (volgende) bestemming te worden verstuurd ∗ transmissie uit de buffer gebeurt via de uitgangslijnen (output lines) of uitgangskanalen (output channels) • Opslagcapaciteit (buffergrootte, bufferlengte) I maximale hoeveelheid informatie die kan worden opgeslagen I gewoonlijk uitgedrukt in een geheel aantal pakketten I verlies van informatie mogelijk in geval van eindige opslagcapaciteit I liefst zo klein mogelijk om totale kost en complexiteit van de buffer en grootte van de tijdsvertragingen te reduceren I voldoende groot om verlies van informatie te reduceren I verlieskans in de praktijk gewoonlijk “uiterst klein” (van de orde van 10−4 tot 10−12 ) I buffersysteem kan in vele gevallen wiskundig gemodelleerd worden als systeem met oneindige bufferlengte (ook in deze cursus) 14 Wiskundige beschrijving van discrete-tijd-buffersystemen - 3 • Wachtlijndiscipline I geheel aan criteria of regels om volgorde en eventueel precieze manier van transmissie van informatie uit de buffer te bepalen I vaak first-come-first-served (FCFS), d.w.z. voorrang voor pakketten die reeds langst in de buffer aanwezig zijn • Synchrone transmissie I informatie wordt opgesplitst in pakketten van vaste of variabele lengte I tijdsas wordt ingedeeld in slots van constante lengte I transmissies van pakketten worden gesynchroniseerd op de vooraf vastgelegde discrete rij van slotgrenzen I in deze cursus wordt steeds synchrone transmissie op de uitgangslijnen van buffersystemen ondersteld I corresponderende buffersystemen zullen wij aanduiden met de term discrete-tijd-buffersystemen I praktische verwezenlijking van synchrone transmissie vereist het gebruik van een klok I slotlengte = klokperiode I slot = klokinterval 15 Wiskundige beschrijving van discrete-tijd-buffersystemen - 4 • Ingangsproces van een buffersysteem I beschrijft de wijze waarop en de mate waarin pakketten zich bij het buffersysteem aanbieden via de ingangslijnen I wordt gewoonlijk stochastisch beschreven • Globale of meer gedetailleerde beschrijving I globale beschrijving: globale aankomststroom (aggregated arrival stream) via alle ingangslijnen samen wordt gekarakteriseerd I meer gedetailleerde beschrijving: ieder ingangskanaal of groep van ingangskanalen wordt afzonderlijk behandeld • Tussenaankomsttijden of aantal pakketten per slot I klassieke manier van werken: ∗ tussenaankomsttijden (interarrival times) en mogelijks ook de hoeveelheid pakketten per aankomst (bulk size) modelleren als stochastische variabelen ∗ al dan niet identisch gedistribueerd ∗ al dan niet onderling statistisch onafhankelijk I typisch voor discrete tijd: ∗ aankomstproces gekarakteriseerd via sequentie van (al dan niet identisch gedistribueerde) discrete toevalsveranderlijken, een per tijdsslot, die aanduiden hoeveel pakketten er tijdens de opeenvolgende slots in de buffer aankomen ∗ ongecorreleerd aankomstproces indien toevalsveranderlijken in kwestie onderling statistisch onafhankelijk zijn ∗ gecorreleerd aankomstproces indien dit niet zo is ∗ aankomstproces is volledig gespecifieerd indien de (gezamenlijke) waarschijnlijkheidsdistributie van bedoelde toevalsveranderlijken wordt opgegeven 16 Wiskundige beschrijving van discrete-tijd-buffersystemen - 5 • Uitgangsproces van een buffersysteem I beschrijft de mate waarin en de wijze waarop aan de pakketten in de buffer de mogelijkheid wordt geboden het buffersysteem te verlaten I belangrijkste elementen: aantal uitgangskanalen, transmissietijd van ieder pakket, mate waarin uitgangskanalen beschikbaar zijn, synchrone aard van de transmissie • Aantal uitgangskanalen I bepaalt hoeveel pakketten gelijktijdig, d.w.z. parallel met elkaar, kunnen worden verzonden uit de buffer I uitgangskanalen al dan niet identisch • Transmissietijd I transmissietijd van een pakket via een uitgangskanaal geeft aan hoeveel slots dit uitgangskanaal in totaal benomen wordt om dit pakket te verzenden I wordt verondersteld alleen gehele waarden aan te nemen I in het algemeen gemodelleerd als een (positieve) discrete toevalsgrootheid I in heel wat toepassingen heeft de relevante eenheid van informatie een constante grootte (uitgedrukt in b.v. bytes) en is de transmissietijd deterministisch gelijk aan 1 slotlengte I variabele transmissietijd voor pakketten van variabele lengte of ten gevolge van toevallige storingen in de uitgangskanalen waardoor meerdere verzendingspogingen kunnen noodzakelijk zijn 17 Wiskundige beschrijving van discrete-tijd-buffersystemen - 6 • Beschikbaarheid van de uitgangskanalen I uitgangslijnen kunnen onderhevig zijn aan (min of meer) toevallige onderbrekingen I aantal beschikbare uitgangslijnen is dan veranderlijk in de tijd I onderbrekingen kunnen aan allerlei factoren te wijten zijn: ∗ defecten ∗ eerder stelselmatige onderbrekingen wanneer uitgangskanalen moeten worden gedeeld met ander communicatiesysteem dat (tijdelijk) hogere prioriteit heeft (b.v. spraak voorrang op data) I modellering: toevalsveranderlijken die aangeven hoeveel uitgangskanalen beschikbaar zijn tijdens opeenvolgende slots I statistische beschrijving van uitgangsproces vereist dan ook specifi¨eren van (gezamenlijke) distributie van deze toevalsveranderlijken I ongecorreleerd uitgangsproces of gecorreleerd uitgangsproces naargelang toevalsveranderlijken in kwestie statistisch onafhankelijk zijn of niet • Synchrone aard van de transmissie I particulariteit in verwerkingsproces bij discrete-tijd-buffersystemen, vanwege synchrone aard van transmissie op uitgangslijnen I transmissie van pakket begint (en eindigt) noodzakelijkerwijze op een slotgrens I pakketten die in ledige buffer aankomen worden niet noodzakelijk onmiddellijk “bediend”: moeten desgevallend wachten tot begin van eerstvolgende slot I uitgangskanalen kunnen nooit actief kunnen zijn tijdens een slot indien de buffer ledig was bij het begin van dit slot 18 Verkorte notatie voor discrete-tijd-buffersystemen • Analoog aan de Kendall-notatie in continue tijd • Twee verschillende vormen: A|B|m|K of A0 − B − m − K I I I I I A → distributie van interarrivaltijd (in slots) A0 → distributie van aantal aankomsten per slot (in pakketten) B → distributie van transmissietijd (in slots) m → aantal parallelle uitgangslijnen (geheel getal of ∞) K → totale opslagcapaciteit (in pakketten) • Keuzemogelijkheden voor A, B en A0 I I I I I I I I I Bern → Bernoulli-distributie Binom → binomiale distributie D → deterministische distributie (constante toevalsgrootheid) G → algemene discrete distributie, d.w.z., niet nader gespecifieerd; afkorting G van “general” Geom → geometrische distributie GI → zelfde betekenis als G, maar hier wordt bovendien benadrukt dat de betrokken toevalsgrootheden onderling onafhankelijk zijn; afkorting GI van “general independent” M → zelfde betekenis als Geom indien gebruikt als waarde voor A of B ; niet gebruikelijk als waarde voor A0; afkorting M van “Markovian” of “memoryless” Pois → Poissondistributie U →(discrete) uniforme distributie • Reductie tot 3 symbolen indien K = ∞ I A|B|m of A0 − B − m • Typische voorbeelden I GI|Geom|4|200 I Binom − D − 2 19 Evenwichtsvoorwaarde en performantie van buffersystemen - 1 • Gedrag van buffersysteem wordt bepaald door I I I I ingangsproces uitgangsproces opslagcapaciteit wachtlijndiscipline • Sommige karakteristieken zijn inherent verbonden met de omgeving waarin het buffersysteem wordt gebruikt I aankomstintensiteit der pakketten I onderbrekingsproces van uitgangslijnen • Andere karakteristieken zijn door ontwerper nog vrij te kiezen I buffergrootte I aantal uitgangskanalen I wachtlijndiscipline • Ontwerper moet parameters zodanig kiezen dat systeem voldoet aan zekere eisen van performantie • Essenti¨ele eis: stochastisch regime (evenwicht) I gekenmerkt door de eigenschap: gemiddelde uitgangsintensiteit = gemiddelde effectieve aankomstintensiteit • Evenwichtsvoorwaarde of stabiliteitsvoorwaarde I gemiddelde hoeveelheid informatie die per slot binnenkomt mag de gemiddelde transmissiemogelijkheden per slot niet overtreffen (en er gewoonlijk ook niet aan gelijk zijn) I gemiddelde effectieve aankomstintensiteit (via de ingangskanalen) moet kleiner zijn dan gemiddelde transmissiecapaciteit (via de uitgangskanalen) 20 Evenwichtsvoorwaarde en performantie van buffersystemen - 2 • Oneindige opslagcapaciteit I evenwichtsvoorwaarde is essentieel om oneindige werkopstapeling (bufferbezetting, vertragingstijden) te vermijden • Eindige opslagcapaciteit I geen echte evenwichtsvoorwaarde: bestaan van stochastisch regime altijd verzekerd I toch beperking voor gemiddelde (aangeboden) aankomstintensiteit om grote verliezen te vermijden • In de praktijk wordt steeds ondersteld I gemiddelde hoeveelheid informatie die zich per slot bij de ingang van het buffersysteem aanbiedt is (veel) kleiner dan de gemiddelde hoeveelheid informatie die per slot kan verstuurd worden • Belangrijkste performantiegrootheden I bufferbezetting (buffer occupancy, buffer contents): aantal pakketten aanwezig in de buffer ∗ systeembezetting (system contents): inclusief pakketten wiens transmissie bezig is ∗ wachtlijnbezetting (queue contents): exclusief deze pakketten I verlieskans I vertragingstijd (delay): verblijftijd van een pakket in de buffer ∗ systeemtijd (system time): inclusief de transmissietijd van het pakket ∗ wachttijd (waiting time): exclusief de transmissietijd van het pakket 21 Stelling van Little • Universeel resultaat uit de wachtlijntheorie I ook toepasbaar op discrete-tijd-buffersystemen • Aangepaste versie/formulering voor discrete-tijd-buffersystemen I beschouw discrete-tijd-buffersysteem in regime I E[u]: gemiddelde bufferbezetting (in pakketten) bij het begin van een willekeurig slot I λ: gemiddelde effectieve aankomstintensiteit (pakketten per slot) I E[d]: gemiddelde verblijftijd (in slots) van een pakket in de buffer vanaf het einde van het slot waarin dit pakket in het buffersysteem binnenkwam tot het einde van het slot waarop dit pakket de buffer weer verlaat • Stelling van Little: van zodra λ, E[d] en E[u] betekenisvol zijn, geldt E[u] = λ · E[d] • Bewijs: aanpassingen vereist t.o.v. bewijs in continue tijd • Veel vrijheidsgraden bij toepassing van de stelling I “systeem”: entiteit of verzameling waar pakketten binnenkomen, enige tijd verblijven en dan weer weggaan I “pakketten”: elementen die deze entiteit al dan niet bevolken • Enkele mogelijkeden I toepassing op een subsysteem van een discrete-tijd-buffersysteem I toepassing op bepaalde klasse van pakketten, onafgezien van de eventuele aanwezigheid van andere klassen I (totale) verblijftijden van de pakketten in het systeem bestaan uit meerdere niet-aaneensluitende tijdsintervallen 22 Discrete toevalsgrootheden en genererende functies • Discrete toevalsgrootheden in de context van discrete-tijd-buffersystemen I I I I I aantal aankomsten per slot aantal beschikbare uitgangskanalen tijdens een slot transmissietijd van een pakket uitgedrukt in slots aantal pakketten opgestapeld in een buffer (bufferbezetting) aantal slots door een pakket doorgebracht in een buffer (vertragingstijd) • Massafunctie van een gehele discrete toevalsgrootheid X x(n) , Prob[X = n] , n≥0 • Genererende functie van een gehele discrete toevalsgrootheid X h X(z) , E z X i = ∞ X x(n) z n n=0 • Interessante eigenschappen van genererende functies I analytisch/begrensd karakter binnen de open resp. gesloten eenheidscirkel van het complexe z -vlak I normeringsvoorwaarde I probabiliteitsgenererende eigenschap I momentengenererende eigenschap I genererende functie van een som van statistisch onafhankelijke toevalsgrootheden wordt gegeven door het product van de genererende functies van deze toevalsgrootheden 23 Inverteren van genererende functies • Gegeven: X(z), genererende functie waarvoor een uitdrukking is gekend in een gebied van het complexe vlak • Gevraagd: bepaal x(n) voor alle n ≥ 0, zodanig dat binnen het convergentiegebied ∞ X n x(n) z X(z) = n=0 • Inversie via afleiding van X(z) in het punt z = 0 ˛ 1 dnX(z) ˛˛ , n≥0 x(n) = n! dz n ˛z=0 I onderstelt gemakkelijke berekening van n-de afgeleide • Inversie via reeksontwikkeling I gegeven uitdrukking voor X(z) in reeks ontwikkelen rond het punt z = 0 via om het even welke ad-hoc-methode I x(n) als co¨effici¨ent van z n in deze reeksontwikkeling aflezen I vrij effici¨ent indien X(z) op een niet te ingewikkelde manier is uitgedrukt in termen van (eenvoudiger) functies waarvan de reeksontwikkeling is gekend/berekend • Inversie via complexe contourintegratie en residurekening I x(n) is co¨effici¨ent van z −1 in de (Laurent)reeksontwikkeling van de functie X(z) · z −1−n rond haar pool z = 0, d.w.z. het residu van de functie X(z) · z −1−n in z = 0: h i −1−n x(n) = Resz=0 X(z) · z I effectief berekenen als contourintegraal of via de residustelling van Cauchy uit de complexe analyse I details: zie cursusnota’s 24
© Copyright 2024 ExpyDoc
