トークンバケット
このアルゴリズムを概念的に説明すると以下のようになる。
トークンは 1 / r {\displaystyle 1/r} 秒おきにバケットに追加される。
バケットは最大 b 個のトークンを保持できる。バケットが満杯の場合、新たなトークンは捨てる。
nバイトのパケット (PDU) が到着すると、n 個のトークンを削除し、そのパケットをネットワークに送り出す。
空いているトークンが n 個未満の場合、トークンは削除せず、そのパケットは non-conformant 状態とされる。
このアルゴリズムは最大 b バイトまでのバースト転送を許容するが、長期的に見れば (conformat) パケットの転送レートは r {\displaystyle r} という定数で制限される。non-conformant パケットには以下のようないくつかの扱い方がある。
捨てる。
バケット内の空きトークンが十分な数になるまでキューイングしておく。
non-conformant という印を付けて構わずに転送する。ただし、ネットワークが高負荷状態であればどこかで捨てられる可能性がある。
1 / r {\displaystyle 1/r} 秒おきにトークンを追加するには、その装置のクロックがそれより細かくなければならない。そうでない装置では、実装には別の定式化を必要とする。Sミリ秒おきにトークバケットを更新できる場合、Sミリ秒おきに追加するトークン数は ( r ∗ S ) / 1000 {\displaystyle (r*S)/1000} となる。