Seau à jetons

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme du seau à jetons (token bucket en anglais) permet 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é.

Utilisation[modifier | modifier le code]

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

Fonctionnement[modifier | modifier le code]

L'algorithme du seau à jetons est très voisin de celui du seau percé. 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 ».

Notes et références[modifier | modifier le code]

  1. Douglas Comer, TCP/IP - Architecture, protocoles et applications, 5ème édition, p. 525, Pearson Education France, 2006, ISBN 2-7440-7186-2