Aller au contenu

Seau à jetons

Un article de Wikipédia, l'encyclopédie libre.

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

[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[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

[modifier | modifier le code]

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 ».

Notes et références

[modifier | modifier le code]
  1. Douglas Comer, TCP/IP - Architecture, protocoles et applications, 5e édition, p. 525, Pearson Education France, 2006, (ISBN 2-7440-7186-2)