トークンバケット

トークンバケット（英: token bucket）とは、ネットワークへのデータ流入量を制御するアルゴリズムの一種であり、バースト性のあるデータ送信を許容する。いくつかの用途があるがトラフィックシェーピングの手法として使うことが多い。

なお、バケット (bucket) とは、バケツのことであり、転送すべきネットワークトラフィックを集積する抽象化されたコンテナである（実装は例えばバッファやキュー）。

トラフィックシェーピングのアルゴリズム

トラフィックシェーピングでは、トークンバケットのほかにリーキーバケットも使われる。この2つは誤って混同されやすい。これらは性質も異なり、目的も異なる。大きな違いは、リーキーバケットがデータ転送レートの上限を設定するのに対して、トークンバケットはデータ転送レートの平均に制限を課して、ある程度のバースト性を許容する。

概要

トークンバケットは、バケット内のトークンの存在に基づいてトラフィックの転送をいつ行うかを指示する制御機構である。バケットには複数のトークンがあり、それぞれがあるバイト列単位に対応したり、事前に設定した大きさの1つのパケットに対応している。バケット内のトークンはパケットを送信する際に削除される。ネットワーク管理者は何バイトの転送に何個のトークンを対応させるかを設定する。トークンがあるとき、トラフィックを転送できる。バケット内にトークンがないとき、パケットを転送することはできない。従って、個別のフローに十分なトークンが割り当てられていて、バーストしきい値が適切に設定されていれば、そのフローはバースト的に転送可能である。

トークンバケット・アルゴリズム

このアルゴリズムを概念的に説明すると以下のようになる。

• トークンは $1/r$ 秒おきにバケットに追加される。
• バケットは最大 b 個のトークンを保持できる。バケットが満杯の場合、新たなトークンは捨てる。
• nバイトのパケット (PDU) が到着すると、n 個のトークンを削除し、そのパケットをネットワークに送り出す。
• 空いているトークンが n 個未満の場合、トークンは削除せず、そのパケットは non-conformant 状態とされる。

このアルゴリズムは最大 b バイトまでのバースト転送を許容するが、長期的に見れば (conformat) パケットの転送レートは $r$ という定数で制限される。non-conformant パケットには以下のようないくつかの扱い方がある。

• 捨てる。
• バケット内の空きトークンが十分な数になるまでキューイングしておく。
• non-conformant という印を付けて構わずに転送する。ただし、ネットワークが高負荷状態であればどこかで捨てられる可能性がある。

$1/r$ 秒おきにトークンを追加するには、その装置のクロックがそれより細かくなければならない。そうでない装置では、実装には別の定式化を必要とする。Sミリ秒おきにトークバケットを更新できる場合、Sミリ秒おきに追加するトークン数は $(r*S)/1000$ となる。

階層型トークンバケット

階層型トークンバケット (hierarchical token bucket、HTB) は、Linux での Class Based Queueing (CBQ) というキューイング規則の代替となる高速化手法である。

HTB は、そのリンク上の帯域幅の利用を制御する補助となる。HTBは物理的には単一のリンクを複数の低速なリンクのように扱い、その個々の低速リンクごとに異なる種類のトラフィックを担わせる。物理リンクを仮想的な複数のリンクに分割する設定や、個々のパケットをどのリンクで送るかの設定が必要となる。

すなわち、HTBはクライアントマシンのダウンロード/アップロードの転送レートを制限する際に特に役立つ。転送レートを制限したクライアントは、ネットワーク全体の帯域幅を使い切ってしまうことがない。

参考文献

• Ferguson P., Huston G., Quality of Service: Delivering QoS on the Internet and in Corporate Networks, John Wiley & Sons, Inc., 1998. ISBN 0-471-24358-2.
• Andrew S. Tanenbaum, Computer Networks, 3rd Edition, Prentice-Hall, 1996.

関連項目

• リーキーバケット
• トラフィックシェーピング

外部リンク

• HTB home - Linux用パケットスケジューラ