リーキーバケット

リーキーバケット（英: leaky bucket）とは、トラフィックシェーピングなどで使われるアルゴリズムである。一般にこのアルゴリズムはネットワークに注入されるデータの転送レートを制御するのに使われ、データ転送レートの「バースト性」を平準化する。

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

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

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

原理

リーキーバケットはネットワークに送信するトラフィックに対して、その転送レートを制御する。名前の通り、穴の開いたバケツに相当し、様々な流量の水流がそのバケツに流れ込むと、そこまでの流量がどうであっても小さな穴からは一定の水流が流れ出す。同様にリーキーバケット・アルゴリズムは様々なバースト性のトラフィックを一定のトラフィックに変換する機構を提供する。

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

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

• 底に穴のあるバケツがあるとする。
• バケツの容量は、そこに溜め込めるデータの量を示している。
• バケツの大きさが $b$ バイトだとすると、空の状態で $b$ バイトまで溜め込めることを意味する。
• 空き容量より大きなパケットが到着した場合、捨てるかキューイングされる。空き容量より小さいパケットの場合はそのままバケツに入れる。
• バケツの穴からは一定レートのデータ、例えば $r$ バイト毎秒のデータが出て行く。

ATMネットワークのトラフィックシェーピングで使っている Generic Cell Rate Algorithm (GCRA) はリーキーバケット・アルゴリズムと等価である。

道路交通との対比

道路交通でたとえると、リーキーバケットは4車線の道路を1車線に収束させる場合に相当する。1車線への進入間隔を制御することでトラフィックが全体として動けるようになる。この手法の利点は、主要幹線（ネットワーク）へ流入する交通量が予測でき制御できる点である。この際の問題点は、バケット容量を遥かに超える交通量があるとき、進入間隔との関係でバケット容量を超えるトラフィックを捨てることになる点である。

実装の非効率性

リーキーバケットは、利用可能なネットワークリソースを効率的に利用していない。バケットから流出するレートは固定なので、トラフィックが少ない状態でもネットワークリソース（帯域幅など）を有効利用できない。従って、リーキーバケットだけではリソースに余裕がある場合に個別のフローをバースト的に転送するといった融通が利かない。一方、トークンバケットはバースト性のあるトラフィックを許容する。リーキーバケットとトークンバケットを両方実装することで、ネットワークへのトラフィックを効率的に制御できる。

参考文献

• Ferguson P., Huston G., Quality of Service: Delivering QoS on the Internet and in Corporate Networks, John Wiley & Sons, Inc., 1998.

関連項目

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