トークンバケット

トークンバケット（英: token bucket）とは、ネットワークへのデータ流入量を制御するアルゴリズムの一種であり、バースト性のあるデータ送信を許容する。いくつかの用途があるがトラフィックシェーピングの手法として使うことが多い。
なお、バケット (bucket) とは、バケツのことであり、転送すべきネットワークトラフィックを集積する抽象化されたコンテナである（実装は例えばバッファやキュー）。
トラフィックシェーピングのアルゴリズム.
トラフィックシェーピングでは、トークンバケットのほかにリーキーバケットも使われる。この2つは誤って混同されやすい。これらは性質も異なり、目的も異なる。大きな違いは、リーキーバケットがデータ転送レートの上限を設定するのに対して、トークンバケットはデータ転送レートの平均に制限を課して、ある程度のバースト性を許容する。
概要.
トークンバケットは、バケット内のトークンの存在に基づいてトラフィックの転送をいつ行うかを指示する制御機構である。バケットには複数のトークンがあり、それぞれがあるバイト列単位に対応したり、事前に設定した大きさの1つのパケットに対応している。バケット内のトークンはパケットを送信する際に削除される。ネットワーク管理者は何バイトの転送に何個のトークンを対応させるかを設定する。トークンがあるとき、トラフィックを転送できる。バケット内にトークンがないとき、パケットを転送することはできない。従って、個別のフローに十分なトークンが割り当てられていて、バーストしきい値が適切に設定されていれば、そのフローはバースト的に転送可能である。
トークンバケット・アルゴリズム.
このアルゴリズムを概念的に説明すると以下のようになる。
このアルゴリズムは最大 "b" バイトまでのバースト転送を許容するが、長期的に見れば ("conformat") パケットの転送レートは formula_2 という定数で制限される。"non-conformant" パケットには以下のようないくつかの扱い方がある。
formula_1 秒おきにトークンを追加するには、その装置のクロックがそれより細かくなければならない。そうでない装置では、実装には別の定式化を必要とする。Sミリ秒おきにトークバケットを更新できる場合、Sミリ秒おきに追加するトークン数は formula_4 となる。
階層型トークンバケット.
階層型トークンバケット (hierarchical token bucket、HTB) は、Linux での Class Based Queueing (CBQ) というキューイング規則の代替となる高速化手法である。
HTB は、そのリンク上の帯域幅の利用を制御する補助となる。HTBは物理的には単一のリンクを複数の低速なリンクのように扱い、その個々の低速リンクごとに異なる種類のトラフィックを担わせる。物理リンクを仮想的な複数のリンクに分割する設定や、個々のパケットをどのリンクで送るかの設定が必要となる。
すなわち、HTBはクライアントマシンのダウンロード/アップロードの転送レートを制限する際に特に役立つ。転送レートを制限したクライアントは、ネットワーク全体の帯域幅を使い切ってしまうことがない。