Seau à jetons

Cet article ne cite pas suffisamment ses sources (septembre 2020).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Le seau à jetons (token bucket) est un algorithme permettant de contrôler le débit passant par un nœud d'un réseau informatique. Il est souvent confondu à tort avec le seau percé (leaky bucket).

Utilisation

L'algorithme du seau à jetons permet de contrôler le débit d'un flux passant par un nœud sur un réseau^[Comment ?]. Il est utilisé en particulier pour fluidifier des échanges irréguliers (shaping)^{[Lesquels ?]} ou pour limiter un débit (policing)^[Comment ?], mais n'est pas limité à ces seules applications^{[réf. nécessaire]}^{[Lesquelles ?]}.

Fonctionnement

L'algorithme du seau à jetons est très voisin de celui du seau percé^{[réf. souhaitée]}. La différence principale est que l'algorithme du seau à jetons permet de régler directement le débit en bits par seconde, alors que l'algorithme du seau percé envoie les paquets à un rythme régulier, qu'ils soient gros ou petits, ce qui empêche de régler le débit^[1].

Une analogie simple permet de comprendre l'algorithme :

Soit un seau percé en son fond : si le seau n'est pas vide alors le contenu s'y écoule avec un débit constant.
La taille du seau représente la quantité d'informations qui peut y être stockée, mesurée en nombre d'octets.
Lorsqu'un paquet arrive, s'il reste suffisamment d'espace dans le seau, il y est placé. Sinon, le seau déborde (paquet en excès).

Les paquets en excès sont en général jetés. Ils peuvent aussi être mis en attente, ou marqués comme non-conformes avant d'être envoyés.

L'algorithme peut être implémenté de la façon suivante :

Un compteur est incrémenté à intervalles réguliers.
Le compteur ne peut pas dépasser un certain seuil.
Quand un paquet de n octets arrive, si le compteur est plus grand que n, on lui soustrait n, et on envoie le paquet.
S'il n'est pas possible de soustraire n du compteur, le compteur reste inchangé, et le paquet est considéré « en excès ».