Wat is het Token Bucket-algoritme?

Het token bucket-algoritme is een mechanisme voor verkeersvormgeving en snelheidsbeperking dat in computernetwerken wordt gebruikt om de gegevensstroom te controleren.

Wat is het Token Bucket-algoritme?

Het token bucket-algoritme is een techniek voor netwerkverkeersbeheer die de hoeveelheid en snelheid van gegevens verzonden via een netwerk. Het werkt door tokens te genereren tegen een vaste snelheid en deze in een logische container te plaatsen, een zogenaamde bucket. Elk token vertegenwoordigt toestemming om een ​​bepaalde hoeveelheid data te verzenden, meestal één pakket of een bepaald aantal. bytes.

Wanneer gegevens moeten worden verzonden, worden tokens uit de bucket verwijderd met een snelheid die overeenkomt met de grootte van de verzonden gegevens. Als er voldoende tokens beschikbaar zijn, worden de gegevens direct verzonden; zo niet, dan wordt de verzending uitgesteld totdat er voldoende tokens zijn verzameld.

De bucket heeft een maximale capaciteit, wat korte pieken in het verkeer mogelijk maakt wanneer de bucket overtollige tokens bevat, maar hanteert ook langetermijnlimieten om aanhoudende congestie te voorkomen. Deze aanpak maakt het token-bucketalgoritme zeer geschikt voor scenario's die zowel gecontroleerde als niet-gecontroleerde tokens vereisen. bandbreedte gebruik en flexvermogen om variabele verkeerspatronen te verwerken.

Hoe werkt het Token Bucket-algoritme?

Het token-bucketalgoritme werkt door tokens te genereren met een constante, vooraf gedefinieerde snelheid en deze in een logische bucket met een vaste maximale capaciteit te plaatsen. Elk token vertegenwoordigt doorgaans toestemming om een ​​specifieke hoeveelheid data te verzenden, zoals één byte of één pakket. Wanneer een apparaat of toepassing wil gegevens verzenden, moet het tokens uit de bucket verbruiken die gelijk zijn aan de omvang van de gegevens.

Als er voldoende tokens beschikbaar zijn, worden de gegevens direct verzonden, wat zorgt voor een soepele overdracht en korte pieken in het dataverkeer ondersteunt. Als er niet voldoende tokens beschikbaar zijn, plaatst het systeem de gegevens in een wachtrij of wacht het tot er meer tokens beschikbaar zijn, waardoor de ingestelde snelheidslimiet wordt gehandhaafd.

De emmer kan ongebruikte tokens tot aan de maximale capaciteit opslaan, waardoor de algoritme om plotselinge pieken in het verkeer op te vangen zonder de gemiddelde transmissiesnelheid te overschrijden. Dit mechanisme zorgt voor een gecontroleerde, efficiënte gegevensstroom en biedt tegelijkertijd flexmogelijkheid voor tijdelijke verkeerspieken.

Token Bucket-algoritmeparameters

Hieronder vindt u een tabel met de belangrijkste parameters van het token-bucket-algoritme:

Waarvoor wordt het Token Bucket-algoritme gebruikt?

Het token-bucketalgoritme wordt gebruikt voor verkeersvorming, snelheidsbeperking en bandbreedtebeheer in computernetwerken. Het zorgt ervoor dat de gegevensoverdracht binnen bepaalde limieten blijft en staat korte pieken van dataverkeer toe wanneer er overcapaciteit beschikbaar is.

Veelvoorkomende toepassingsgevallen zijn onder meer het beheren van uitgaand verkeer van servers, het beheren van de toewijzing van bandbreedte op netwerkinterfaces, het afdwingen Service Level Agreements (SLA's)en het voorkomen van netwerkcongestie. Het algoritme wordt op grote schaal geïmplementeerd in routers, schakelaars, firewallsen kwaliteit van de dienstverlening (QoS) mechanismen om voorspelbare netwerkprestaties te leveren en eerlijkheid tussen gebruikers of toepassingen te behouden.

Hoe implementeer je het Token Bucket-algoritme?

Om het token-bucketalgoritme te implementeren, volgt u deze algemene stappen, die zowel in software als in hardware-gebaseerde systemen:

1. Initialiseer de bucketDefinieer de maximale bucketcapaciteit (B), die het aantal tokens vertegenwoordigt dat de bucket kan bevatten. Stel de tokengeneratiesnelheid (r) in, die bepaalt hoeveel tokens er per tijdseenheid worden toegevoegd.
2. Genereer tokens in de loop van de tijdVoeg continu tokens toe aan de bucket met de ingestelde snelheid. Als de bucket zijn maximale capaciteit bereikt, worden extra tokens verwijderd om te voorkomen dat de burstlimiet wordt overschreden.
3. Gegevensoverdrachtverzoeken verwerkenControleer elke keer dat een pakket of data-eenheid moet worden verzonden, de bucket op beschikbare tokens. Het aantal benodigde tokens is afhankelijk van de grootte van de data (bijvoorbeeld één token per byte of per pakket).
4. Verkeer toestaan ​​of vertragenAls er voldoende tokens beschikbaar zijn, verwijder dan de vereiste tokens uit de bucket en sta onmiddellijke transmissie toe. Als er onvoldoende tokens zijn, stel de transmissie dan uit totdat er meer tokens zijn verzameld of verwijder het verkeer, afhankelijk van het implementatiebeleid.
5. Herhaal het procesVul tokens continu aan en beheer verkeersaanvragen, zodat het gemiddelde bandbreedtegebruik binnen de geconfigureerde limieten blijft en tijdelijke pieken worden ondersteund.

Wat zijn de voordelen van het Token Bucket-algoritme?

Het token bucket-algoritme biedt verschillende voordelen voor netwerkverkeersbeheer:

• Maakt verkeerspieken mogelijk. In tegenstelling tot strikte snelheidsbeperkende algoritmen staat het korte bursts van gegevensoverdracht toe, zolang er tokens zijn verzameld, waardoor flexmogelijkheid voor variabele verkeerspatronen.
• Soepele regeling van het gemiddelde tarief. Hiermee wordt een gemiddelde transmissiesnelheid op lange termijn afgedwongen, waardoor het totale bandbreedtegebruik binnen vastgestelde grenzen blijft zonder dat dit ten koste gaat van de prestaties tijdens perioden met weinig verkeer.
• Efficiënt bandbreedtegebruik. Door tijdelijke pieken toe te staan ​​en de gemiddelde snelheid te regelen, wordt het gebruik van netwerkbronnen gemaximaliseerd zonder dat er voortdurende congestie ontstaat.
• Eenvoud en lage overheadkosten. Het algoritme is relatief eenvoudig te implementeren met minimale rekenkundige overhead, waardoor het geschikt is voor hardware- en softwaresystemen.
• Voorkomt opstoppingen. Door overtollig verkeer te vertragen of te blokkeren wanneer tokens niet beschikbaar zijn, voorkomt u netwerkcongestie en blijft de servicekwaliteit behouden.
• Ondersteunt de kwaliteit van de dienstverlening. Het integreert goed met QoS-frameworks, waardoor een eerlijke verdeling van de bandbreedte en prioritering van verkeer mogelijk is.

Wat zijn de nadelen van het Token Bucket-algoritme?

Het token-bucket-algoritme heeft ondanks zijn voordelen verschillende nadelen. flexbekwaamheid:

• Garandeert geen constante outputsnelheid. Hoewel het de gemiddelde transmissiesnelheid regelt, zijn er wel pieken in het verkeer mogelijk. Deze kunnen kortdurende pieken in het verkeer veroorzaken, waardoor downstream-apparaten overbelast kunnen raken als ze niet goed worden beheerd.
• Vereist nauwkeurig tijdmanagement. Nauwkeurige tokengeneratie is cruciaal voor een correcte werking. Inconsistente timing als gevolg van systeemvertragingen of klokafwijkingen kan de snelheidshandhaving verstoren.
• Beperkte controle over de burstgrootte. De grootte van de toegestane bursts is afhankelijk van de capaciteit van de bucket, maar het afstemmen van deze parameter kan lastig zijn. Een te kleine bucket vermindert de burst. flexmogelijkheid; te groot kan leiden tot overmatige verkeerspieken.
• Overheadkosten voor het onderhoud van de staat. Het algoritme vereist voortdurende registratie van het aantal tokens en de tijdsintervallen, wat het beheer van de status complexer maakt, vooral in snelle of grootschalige netwerken.
• Niet effectief voor verkeerspolitie alleen. Hoewel het verkeer vormgeeft en bursts toestaat, moet het mogelijk worden gecombineerd met andere mechanismen (bijvoorbeeld een lekkende emmer of streng toezicht) om strikte naleving van bandbreedtelimieten in gevoelige omgevingen te garanderen.

Token Bucket versus Leaky Bucket-algoritme

Hier is een duidelijke vergelijkingstabel van het token bucket- en het leaky bucket-algoritme: