漏れやすいバケツ

漏れやすいバケツは、水が注がれる平均速度がバケツの漏れ速度を超えるか、バケツの容量を超える水を一度に入れると、常に漏れているバケツが溢れるという例えに基づくアルゴリズムです。これは、一連の離散イベントが平均速度とピーク速度または頻度の定義された制限に準拠しているかどうかを判断するために使用できます。たとえば、これらのイベントに関連付けられたアクションをこれらの速度に制限したり、速度に準拠するまでイベントを遅らせたりできます。また、準拠を確認したり、平均速度のみに制限したり、つまり平均からの変動を除去したりするためにも使用できます。

これは、パケット交換コンピュータネットワークおよび通信ネットワークにおいて、パケットの形式でのデータ送信のトラフィックポリシング、トラフィックシェーピングおよびスケジューリングの両方に使用され、^{[注 1]}帯域幅とバースト性（トラフィックフローの変動の尺度）に対する定義された制限に従います。

リーキーバケットの一種である汎用セルレートアルゴリズムは、非同期転送モード（ATM）ネットワーク^[1]のUPCおよびNPCのユーザ・ネットワーク間インターフェース、ネットワーク間インターフェース、またはネットワーク間インターフェースで、ネットワークを経由する接続の過剰なトラフィックレベルから保護するために推奨されています。汎用セルレートアルゴリズムまたは同等のアルゴリズムは、 ATMネットワークへの ネットワークインターフェースカードによる送信をシェーピングするためにも使用できます。

リーキー バケットの少なくとも一部の実装は、トークン バケットアルゴリズムのミラー イメージであり、同等のパラメーターが与えられた場合、まったく同じイベントのシーケンスが決定され、同じ制限に準拠するか準拠しないかが決まります。

この水漏れバケツのアナロジーを適用する2つの異なる方法が文献に記載されています。^{[2] [3] [4] [5]}これらは、2つの異なるアルゴリズムを提供しているように見えますが、どちらも水漏れバケツアルゴリズムと呼ばれ、通常は他の方法とは関係ありません。これにより、水漏れバケツアルゴリズムとその特性が何であるかについて混乱が生じています。

あるバージョンでは、バケットはトラフィックのフローやイベントのスケジュールとは別のカウンタまたは変数です。^{[2] [4] [5]}このカウンタは、トラフィックまたはイベントが制限に準拠しているかどうかを確認するためだけに使用されます。カウンタは、チェックが行われているポイントにパケットが到着するかイベントが発生すると増加します。これは、バケツに水が断続的に追加されるのと同じです。カウンタは一定の割合で減少しますが、これはバケツから水が漏れるのと同じです。結果として、カウンタの値はバケツの水位を表します。パケットが到着するかイベントが発生したときにカウンタが指定された制限値を下回っている場合、つまりバケツがオーバーフローしない場合は、帯域幅とバースト性の制限、または平均レートとピークレートのイベント制限に準拠していることを示します。このバージョンは、ここではメーターとしてのリーキーバケットと呼ばれます。

2番目のバージョンでは、バケツはトラフィックの流れの中のキューです。^[3]このキューは、そのフローを直接制御するために使用されます。パケットは到着するとキューに入れられます。これは、バケツに追加される水に相当します。これらのパケットは、通常、固定レートで（先着順で）キューから削除されます（先着順）。これは、バケツから水が漏れることに相当します。この構成では、適合性をチェックするのではなく、強制します。出力が固定レートで処理される場合（およびパケットがすべて同じ長さである場合）、結果として生じるトラフィックストリームには必然的にバースト性やジッターがなくなります。したがって、このバージョンでは、トラフィック自体がバケツを通過する水に類似しています。このバージョンは、ここではキューとしての漏れやすいバケツと呼ばれています。

メーターとしてのリーキーバケツは、トークンバケットアルゴリズムとまったく同じです（その鏡像です）。つまり、リーキーバケツに水を追加するプロセスは、適合パケットが到着したときにトークンバケットからトークンを削除するプロセスとまったく同じです。リーキーバケツから水が漏れるプロセスは、トークンバケットに定期的にトークンを追加するプロセスとまったく同じです。また、リーキーバケツがオーバーフローしないというテストは、トークンバケットに十分なトークンが含まれており、アンダーフローしないというテストの鏡像です。したがって、同等のパラメータが与えられれば、2つのアルゴリズムは同じトラフィックを適合または非適合として見なします。キューとしてのリーキーバケツは、メーターとしてのリーキーバケツの特別なケースと見なすことができます。^[6]

ジョナサン・S・ターナーは、リーキー・バケット・アルゴリズムのオリジナルの記述で有名で^[7]、次のように説明しています。「接続で送信する各ユーザーに関連付けられたカウンターは、ユーザーがパケットを送信するたびに増加し、定期的に減少します。カウンターが増加時にしきい値を超えると、ネットワークはパケットを破棄します。ユーザーは、カウンターが減少するレート(平均帯域幅を決定)としきい値の値(バースト性の尺度)を指定します。」^[2]この場合、バケット(カウンターに類似)は、パケットを直接制御するキューとしてではなく、パケットの適合性をテストするためのメーターとして使用されます。

本質的に同じメーターバージョンのアルゴリズムである汎用セルレートアルゴリズムの別の説明は、ITU-T の勧告 I.371 およびATM フォーラムのUNI仕様で提供されています。^{[4] [5]ターナーの説明[2]}のパケットとセルという用語が同等である説明は、ITU-T によって次のように提供されています。「連続状態のリーキーバケットは、実数値の内容が時間単位あたり 1 単位の内容の連続速度で排出され、適合セルごとに増分Tで内容が増加する有限容量のバケットと見なすことができます...セルの到着時にバケットの内容が制限値τ以下の場合、セルは適合しています。それ以外の場合、セルは非適合です。バケットの容量 (カウンターの上限) は ( T + τ )です。」^[5]これらの仕様では、バケツの容量が有限であるため、適合性試験時のバケツの内容物が限界値を超え、セルが不適合となった場合、バケツはそのまま残され、つまり、バケツが溢れてしまうような水は追加されないとも規定されています。

David E. McDysan と Darrel L. Spohn は、ITU-T/ATM フォーラムの説明についてコメントしています。その中で、彼らは「リーキー バケットのアナロジーでは、[ATM] セルは実際にはバケットを通過しません。適合許可のチェックのみが通過します」と述べています。^[6]しかし、文献の説明では珍しいことに、McDysan と Spohn はリーキー バケット アルゴリズムをキューとして参照し、「トラフィック シェーピングの 1 つの実装では、実際にセルがバケットを通過することに注意してください」と述べています。^[6]

ITU-T 版のアルゴリズムの動作を説明するにあたり、マクダイサンとスポーンは「待ち行列理論でよく使われる架空のグレムリンの概念」を引用している。^[6]このグレムリンはバケツの水位を検査し、水位が限界値τ を超えている場合はアクションを起こす。トラフィック ポリシングでは、トラップ ドアを開けて到着したパケットをドロップし、水がバケツに入るのを防ぐ。トラフィック シェーピングでは、フラップを押し上げて到着したパケットを遅延させ、バケツの水位がτを下回るまでパケットが水を送らないようにする。

ターナーと ITU-T/ATM フォーラムによる説明の違いは、ターナーの説明はトラフィック ポリシングに特化しているのに対し、ITU-T/ATM フォーラムの説明はトラフィック ポリシングとトラフィック シェーピングの両方に適用できることです。また、ターナーは、カウンタの内容は適合パケットによってのみ影響を受けるべきであり、カウンタが制限を超えない場合にのみ増加されるべきであるとは述べていません。つまり、ターナーはバケットの容量またはカウンタの最大値が有限であるとは明示的に述べていません。^{[注 2]}

トラフィック ポリシングまたはトラフィック シェーピングのいずれかで使用できるメーターとしてのリーキー バケット アルゴリズムの動作概念の説明は、各仮想接続またはユーザーに関連付けられた固定容量のバケットとして説明できます。バケットは固定速度で漏れます。バケットが空になると、漏れが止まります。パケットが準拠するには、特定の量の水をバケットに追加できる必要があります。準拠パケットによって追加される特定の量は、すべてのパケットで同じにすることも、パケットの長さに比例することもできます。この量の水によってバケットがオーバーフローする場合、パケットは準拠せず、バケット内の水は変更されません。

リーキー バケットをメーターとして使用することは、トラフィック シェーピングまたはトラフィック ポリシングのどちらにも使用できます。たとえば、ATM ネットワークでは、汎用セル レート アルゴリズムの形式で、仮想チャネル (VC) または仮想パス (VP) 上のトラフィックの帯域幅とバースト性を、VC または VP のセル到着レートと最大ジッタ (到着間隔の変動) の指定制限と比較するために使用されます。トラフィック ポリシングでは、これらの制限に適合しないセル (不適合セル) はドロップされるか、輻輳がある場合に下流のトラフィック管理機能によってドロップされるように優先順位が下げられることがあります。トラフィック シェーピングでは、セルは適合するまで遅延されます。トラフィック ポリシングとトラフィック シェーピングは、UPC および NPC で、過剰なトラフィックまたは過度にバースト的なトラフィックからネットワークを保護するためによく使用されます (帯域幅管理と輻輳回避を参照)。トラフィック シェーピングは、ホストのネットワーク インターフェイスでよく使用され、帯域幅またはジッタの制限を超えた送信がネットワークのトラフィック管理機能によって破棄されるのを防ぎます。 (スケジューリング (コンピューティング)およびネットワーク スケジューラを参照してください。)

リーキーバケットアルゴリズムは、リーキーバケットカウンタでランダム（確率的）プロセスの速度を測定するためにメーターとして使用することもできます。リーキーバケットカウンタは、イベントの平均またはピークレートが許容可能な背景レベルを超えて増加したときにオーバーフローによって示すために使用できます。^[8]たとえば、このようなリーキーバケットカウンタは、修正可能なメモリエラーが突然発生したときや、平均レートが徐々に大幅に増加したときに検出するために使用できます。これは、差し迫った修正の失敗を示している可能性があります。^[9]

リーキー バケット カウンタにおけるリーキー バケット アルゴリズムの使用は、メーターとして使用されるという点で、トラフィック管理における使用に似ています。基本的に、イベントは説明内のパケットを置き換え、各イベントによって一定量の水がバケツに追加されます。イベントの結果としてバケツがオーバーフローする場合、イベントは制限外イベントに関連付けられたアクションをトリガーする必要があります。一部の実装^{[8]は Turner の説明[2]}と類似しているように見えます。つまり、カウンタが取る最大値に明示的な制限はなく、カウンタがしきい値を超えると、放出間隔に相当する期間よりも大幅に長い期間が経過するまで、カウンタは以前の状態に戻らない可能性があります。放出間隔は、そうでなければ適合するイベントによって増加する可能性があります。ただし、他の実装では、オーバーフロー中にカウンタを増分しない場合があります。これにより、後続のイベントが適合しているかどうかを正しく判断できます。

リーキーバケットアルゴリズムをメーターとして使用する場合、トラフィックの制限は帯域幅と出力のバースト性になります。^{[4] [5] [注 3]}接続の帯域幅制限とバースト性制限は、トラフィック契約で指定できます。帯域幅制限は、パケットレート、ビットレート、またはパケット間の送信間隔として指定できます。バースト性制限は、遅延変動許容値または最大バーストサイズ (MBS) として指定できます。

リーキー バケット アルゴリズムの複数のインスタンスを使用して、複数の契約パラメータ セットを接続に同時に適用できます。各インスタンスは、帯域幅とバースト性の制限を取ることができます。「汎用セル レート アルゴリズム」の「デュアル リーキー バケット コントローラ」を参照してください。

バケットが漏洩する速度によって帯域幅の制限が決定されます。これは Turner ^[2]によって平均速度と呼ばれ、ITU-T ではその逆数が放出間隔と呼ばれています。この間隔が何であるかを説明するには、パケットの長さが固定されていると最も簡単です。したがって、この説明の最初の部分ではこれを前提とし、可変パケット長の影響については別途検討します。

先行するトラフィックによってちょうどいっぱいになったバケツ、つまり最大許容バーストがすでに発生している、つまり帯域幅とジッターの制限に適合する最短時間で最大数のパケットまたはセルが到着したばかりのバケツを考えてみましょう。次のパケットが適合するまでの最小間隔は、バケツがパケットによって送られた水の量を正確に漏らすのにかかる時間であり、その時点でパケットがテストされ適合すると、バケツはもう一度ちょうどいっぱいになります。したがって、バケツがいっぱいになると、パケットが適合できる最大速度は、各パケット間のこの間隔になります。

Turner ^[2]はこのレートを平均と呼んでおり、その逆数が平均間隔であることを意味しています。ただし、平均レートと間隔が何であるかについては、多少の曖昧さがあります。パケットはより低いレートで到着する可能性があるので、これは固定値ではなく上限であり、せいぜい平均レートの最大値と呼ぶことができます。また、最大バーストが発生する期間中は、パケットはより短い間隔で到着するため、これよりも高いレートになります。したがって、無限大よりも短い期間では、実際の平均レートはこれよりも大きくなる可能性があり (必ずしもそうとは限りません)、平均間隔は放出間隔よりも小さくなる可能性もあります (必ずしもそうとは限りません)。したがって、この曖昧さのため、以降は放出間隔という用語を使用します。ただし、長期平均間隔が取り得る最小値は放出間隔になる傾向があることは依然として事実です。

可変長パケットの場合、バケットに追加される量はパケット長に比例しますが、パケットが適合できる最大速度はパケット長によって異なります。パケットが適合するためにバケットが満杯から漏れなければならない量が、パケットが追加する量であり、これがパケット長に比例する場合は、バケットを埋めた前のパケットとの間隔も比例します。したがって、可変長パケットの特定の送信間隔を指定することはできず、帯域幅制限はビット/秒またはバイト/秒で明示的に指定する必要があります。

遅延変動許容度は、パケットの長さが固定されている場合に説明するのが最も簡単です。したがって、この説明の最初の部分ではこれを前提とし、可変パケット長の影響については別途検討します。

ITU-T は、バケットの容量よりT (適合セルごとにバケットの内容が増加する量)少ない制限値τを定義しており、バケットの容量はT + τになります。この制限値は、パケットが正確に送信間隔で到着した場合に通常予想されるよりも、パケットがどれだけ早く到着できるかを指定します。

次のような状況を想像してください。バケツからは 1 秒あたり 1 単位の水が漏れるので、限界値τとパケットによって追加される水の量Tは、実質的に秒単位です。このバケツは最初は空なので、パケットがバケツに到着しても、水T を追加してもバケツは完全には満たされず、バケツの容量はτ未満になります。そのため、次のパケットが到着するときには、バケツの容量がT – τだけ空になっていれば、この条件は満たされます。そのため、これら 2 つのパケットの間隔は、Tよりも最大τ短くなる場合があります。

これは、シーケンス内の複数のパケットにも適用されます。次の状況を想像してください。バケツは再び空から始まるため、到着する最初のパケットは明らかに適合しています。次に、適合するパケット数Nが、適合するのに最短時間で到着すると、バケツはちょうどいっぱいになります。最後の ( N番目) のパケットが適合するには、バケツから先行するN – 1 個のパケットから十分な量の水 ( ( N – 1)  ×  T秒分) が漏れ​​て、この時点で限界値τにちょうど達している必要があります。したがって、漏れた水は ( N – 1)  ×  T – τであり、漏れは 1 秒あたり 1 単位であるため、漏れるのにちょうど ( N – 1)  ×  T – τ秒かかりました。したがって、 N 個のパケットすべてが到着して適合できる最短時間は( N – 1)  ×  T – τ秒であり、これは、パケットが正確に放出間隔で到着していた場合にかかった時間よりも ちょうどτ短くなります。

ただし、バケットが前のパケットでいっぱいになっていない場合にのみ、パケットはT未満の間隔で到着します。バケットがいっぱいになっている場合は、次のパケットが適合する前にバケットがT の全量だけ空になっている必要があります。したがって、 T未満で到着するパケットによってこのバケットのスペースが使い果たされると、後続のフレームはT以上の間隔で到着する必要があります。ただし、バケットがいっぱいにならない場合は、フレームはより長い間隔で到着する可能性があります。バケットは空になるとリークが停止するため、T を超える間隔で蓄積できる許容範囲には常に制限 ( τ ) があります。

制限値τ は、パケットが予想よりもどれだけ早く到着できるかを定義するため、ソースから適合性テストが実行されるポイントまでの最大遅延と最小遅延の差の制限となります (パケットがジッターなしで生成されると仮定)。したがって、ATM ではこのパラメータに対してセル遅延変動許容値 (CDVt) という用語が使用されます。

一例として、遅延変動の原因として考えられるのは、スイッチの出力で多数のパケット ストリームが多重化されている場合です。これらの接続の帯域幅の合計が出力の容量よりも小さいと仮定すると、到着したパケットはすべて最終的に送信できます。ただし、パケットの到着が独立している場合 (たとえば、スイッチの異なる入力に到着する場合)、複数のパケットが同時に、またはほぼ同時に到着することがあります。出力は一度に 1 つのパケットしか送信できないため、他のパケットは送信の順番が来るまでバッファにキューイングする必要があります。このバッファにより、パケットが入力に到着してから出力によって送信されるまでの間に追加の遅延が発生します。この遅延は、バッファにすでにキューイングされている他のパケットの数に応じて異なります。同様の状況は、複数のパケットが同じまたは同様のリリース時間を持つ場合にホストの出力 (ネットワーク インターフェイス コントローラ内) で発生する可能性があり、この遅延は通常、仮想出力バッファの遅延としてモデル化できます。

可変長パケットの場合、特定のパケットによって追加される水の量はその長さに比例するため、τ はパケットが到着したときにバケツがどれだけいっぱいになるかの制限とは見なされません。これはパケット サイズによって変わるためです。ただし、このレベルから空になるまでにかかる時間は、帯域幅制限でパケットが送信された場合に予想されるよりもどれだけ早くパケットが到着できるかを示します。したがって、適合テストが適用されるポイントまでの転送遅延の最大変動は許容可能であり、最大遅延変動の許容範囲となります。

制限値または遅延変動許容値は、1 つのパケットに必要な容量を超えるバケットの超過深度によって決定されるバーストで到着できるパケットの数も制御します。したがって、MBS はバースト性またはジッターの尺度でもあり、バースト性を MBS として指定して、そこから制限値τ を導出することも、ジッターまたは遅延変動許容値または制限値として指定して、そこから MBS を導出することもできます。

パケットのバーストまたは塊は、送信間隔Tによって決定されるよりも高いレートで到着する場合があります。これは、バースト内のパケットが連続して到着する場合の物理層接続のライン レートである可能性があります。ただし、ATM の場合と同様に、許容度はより低いレート (その場合は持続セル レート(SCR)) に適用され、パケット (セル) のバーストはより高いレートで到着しますが、物理層のライン レート (その場合はピーク セル レート (PCR)) よりも低くなります。MBS は、上位層のパケットを転送するために必要なセルの数 ( 「セグメント化と再アセンブリ」を参照) である可能性があります。この場合、パケットは SCR によって決定される最大帯域幅で送信され、パケット内のセルは PCR で送信されます。これにより、パケットの最後のセルとパケット自体は、セルが SCR で送信された場合よりも大幅に早く到着します。送信期間 = (MBS-1)/PCR ではなく (MBS-1)/SCR です。 PCR でのこのバーストは、SCR での送信よりも、スイッチ出力バッファなどの共有リソースに大幅に高い負荷をかけるため、バッファ オーバーフローやネットワーク輻輳が発生する可能性が高くなります。ただし、MBS セルがライン レートで連続して送信および到着することを可能にする 制限値τ _{SCRを持つ SCR での送信よりも、これらのリソースにかかる負荷は少なくなります。}

制限値が十分に大きい場合、複数のパケットがバーストで到着しても準拠できます。バケットが空から始まる場合、到着する最初のパケットによってTが追加されますが、次のパケットが到着するまでに内容がτ未満であれば、これも準拠します。各パケットが到着するのにδかかると仮定すると、τ (バケットが制限値から空になるまでの時間として表される) が、放出間隔から最小到着間隔T  – δ を引いた値以上であれば、2 番目のパケットは最初のパケットとともにバーストとして到着した場合でも準拠します。同様に、τ が( T  – δ ) × 2以上であれば、3 つのパケットがバーストで到着することになります。

このバーストの最大サイズMは、送信間隔T、最大ジッタ許容値τ、パケットの送受信にかかる時間δから次のように計算できます。 ^[4]

${\displaystyle M=\left\lfloor 1+{\frac {\tau }{T-\delta }}\right\rfloor }$

同様に、特定のMBSを与えるジッタ許容値τの最小値は、MBSから次のように計算できる。^[4]

${\displaystyle \tau =\left(M-1\right)\left(T-\delta \right)}$

ATM の場合、技術的には MBS は SCR 許容値にのみ関係しますが、上記の式では、各パケットが到着するまでの時間δは PCR のセルの送信間隔T _PCRであり、送信間隔Tは SCR の送信間隔T _SCRです。MBS はセグメント化されたパケットを転送するために必要なセルの数であるため、上記の制限値τは SCR の値τ _SCRになります。ただし、PCR のセルが遅延変動の影響を受ける UNI またはNNIでは、SCR の制限値と PCR の制限値τ _SCR + τ _PCRになります。

可変長パケットの場合、最大バースト サイズはバースト内のパケットの長さによって決まり、最大バースト サイズの単一の値はありません。ただし、入力ストリームのバイト レート、リークの同等のバイト レート、およびバケットの深さから、合​​計バースト長をバイト単位で指定することは可能です。

リーキー バケット アルゴリズムは、トークン バケットアルゴリズムと対比されることがあります。ただし、メーターとしてのリーキー バケットの上記の動作概念は、トークン バケット アルゴリズムと直接比較できます。その説明は、この記事で次のように示されています。

• トークンは 1/ r秒ごとにバケットに追加されます。

• バケットには最大b 個のトークンを保持できます。バケットがいっぱいのときにトークンが到着した場合、そのトークンは破棄されます。

• 「n」バイトのパケット（ネットワーク層PDU）[ sic ] ^{[注 1]が到着すると、} n個のトークンがバケットから削除され、パケットがネットワークに送信されます。

• 使用可能なトークンがn 個未満の場合、バケットからトークンは削除されず、パケットは非準拠と見なされます。

これは、上で繰り返した操作の概念と比較することができます。

• 各仮想接続またはユーザーに関連付けられた固定容量バケットは、固定レートでリークします。

• バケツが空になれば、漏れは止まります。

• パケットが準拠するには、バケツに特定の量の水を追加できる必要があります。準拠するパケットによって追加される特定の量は、すべてのパケットに対して同じにすることも、パケットの長さに比例することもできます。

• この量の水によってバケツの容量を超える場合、パケットは適合せず、バケツ内の水はそのまま残ります。

ご覧のとおり、これら 2 つの説明は本質的に互いに鏡像になっています。1 つはバケットに定期的に何かを追加し、適合パケットの場合はゼロの制限まで何かを削除します。もう 1 つは、適合パケットの場合はバケットの容量の制限まで定期的に何かを削除し、追加します。では、適合パケットのトークンを追加し、固定レートで削除する実装は、リーキー バケットの実装でしょうか、それともトークン バケットの実装でしょうか。同様に、適合パケットの水を削除し、固定レートで水を追加する実装では、どのアルゴリズムが使用されていますか。実際、どちらも実質的に同じです。つまり、リーキー バケットとトークン バケットの両方の実装です。これらは、異なる方法で記述された同じ基本アルゴリズムです。これが、同等のパラメータが与えられた場合、2 つのアルゴリズムがまったく同じパケットを適合または非適合と見なす理由を説明しています。したがって、リーキー バケット アルゴリズムとトークン バケット アルゴリズムの実装の特性とパフォーマンスの違いは、実装の違いから完全に生じます。つまり、基礎となるアルゴリズムの違いから生じるものではありません。

注目すべき点は、リーキー バケット アルゴリズムをメーターとして使用すると、ジッターやバースト性のある適合出力パケット ストリームを許可できること、トラフィック ポリシングやシェーピングに使用できること、可変長パケットに実装できることです。

キューとしてのリーキー バケットは、基本的に、バースト性やジッターを除去するために固定レートで処理される単純なFIFOバッファまたはキューを説明する方法です。Andrew S. Tanenbaumは、著書Computer Networks (旧版) で、次のように説明しています。「リーキー バケットは有限のキューで構成されています。パケットが到着すると、キューに空きがあればキューに追加され、空きがなければ破棄されます。クロック ティックごとに 1 つのパケットが送信されます (キューが空でない限り)。」^[3]したがって、キューとしてのリーキー バケットの実装は、常にトラフィック シェーピング機能の形式になります。

ご覧のとおり、この実装は、パケットが常に固定レートで送信されるという制限があります。これを強調するために、Tanenbaum は「リーキー バケット アルゴリズムは、[入力] トラフィックがどれだけバースト的であっても、平均レートで固定された出力パターンを強制します」とも述べています。^[10]ただし、この主張は、キューが空にならない限り厳密に当てはまります。平均到着レートがクロック ティックのレートよりも低い場合、または入力が十分にバースト的であるため、損失によって残りのレートがクロック ティック レートを下回る場合 (つまり、入力ストリームのギャップが十分に長く、キューが空になるほど小さい場合)、出力ストリームにギャップが発生します。

さらなる制約として、キュー トラフィック シェーピング機能としてのリーキー バケットは、ティックでパケットを送信するだけであるため、UPC および NPC と同等のネットワーク内で使用される場合、パケットの転送にも固定位相が課されます。一方、転送を制御するためにリーキー バケット メーターを使用する場合、パケットは、任意のローカル クロックに従ってではなく、前のパケットまたは、すでに準拠している場合はその到着時間に対して準拠するとすぐに送信されます。逆に、転送遅延のコンテキストでは、時間の経過とともに、準拠している入力パケット ストリームの位相と異なる可能性があるこの固定位相の課せは、遅延変動、つまりジッターを構成します。この特定の方法で発生するジッターは、キュー シェーピング機能としてのリーキー バケットの両側にある 2 つの個別の測定ポイント間の移動時間として遅延が測定される場合にのみ観察できます。ただし、リアルタイム データ転送のコンテキストでは、受信データの遅延を決定するのはこのエンドツーエンドの遅延です。したがって、キューとしてのリーキー バケットは、トラフィック シェーピングのリアルタイム伝送には適していません。

リーキー バケット アルゴリズムをキューとして使用して可変長パケットを制限することは、固定長パケットの場合よりも大幅に複雑です。Tanenbaum は、可変長パケットの「バイト カウント」リーキー バケットについて次のように説明しています。「各ティックで、カウンタが n に初期化されます。キューの最初のパケットのバイト数がカウンタの現在の値よりも少ない場合、そのパケットは送信され、カウンタはそのバイト数だけ減算されます。カウンタが十分に大きい限り、追加のパケットを送信することもできます。カウンタがキューの次のパケットの長さを下回ると、次のティックまで送信が停止し、その時点で残りのバイト数が [n] にリセットされ、フローが継続されます。」^[3]固定長パケットのバージョンと同様に、この実装は送信のフェーズに強い影響を及ぼし、結果としてエンドツーエンドの遅延が変動し、リアルタイムのトラフィック シェーピングには適さなくなります。

キューとしてのリーキーバケットは、出力にジッターを生じさせずに、トラフィックを指定された帯域幅にシェーピングする場合にのみ使用できます。[ ^10]これは、たとえば帯域幅管理の一部としてネットワーク内で使用されることもありますが、ホストのネットワークインターフェイスでのトラフィックシェーピングに適しています。リーキーバケットアルゴリズムは、Nginxの ngx_http_limit_conn_moduleモジュールで、単一のIPアドレスからの同時接続数を制限するために使用されます。^[11]

キューとしてのリーキーバケットアルゴリズムの場合、このアルゴリズムに定義されている唯一の制限は、その出力の帯域幅です。^{[10] [注3]}

接続の帯域幅制限は、トラフィック契約で指定できます。帯域幅制限は、パケットまたはフレーム レート、バイトまたはビット レート、またはパケット間の送信間隔として指定できます。

リーキー バケットをキューとして実装すると、利用可能なネットワーク リソースを効率的に使用できません。一定の間隔でのみパケットを送信するため、トラフィック量が非常に少なく、ネットワーク リソースの大部分 (特に帯域幅) が使用されていない状況が多数発生します。したがって、キューとしてのリーキー バケットの実装には、個々のフローをポート速度までバーストさせるメカニズムが存在せず、ネットワークでリソースの競合が発生しないときにネットワーク リソースを事実上消費します。ただし、トークン バケットとリーキー バケットをメーターとして実装すると、出力トラフィック フローにバースト特性を持たせることができます。

リーキー バケット アルゴリズムの 2 つのバージョンを分析すると、キューとしてのバージョンはメーターとしてのバージョンの特殊なケースであることがわかります。

固定長キューを使用して実装され、遅延要素を形成し、リークバケツをメーターとして使用してサービスされる固定長パケットのトラフィックシェーピング機能を想像してください。また、このメーターのバケツの深さがパケットによって追加される量に等しい、つまり、限界値τがゼロであると想像してください。ただし、適合性テストは、キューの先頭のパケットが送信され、その水が追加される、放出間隔の間隔でのみ実行されます。この水は次の放出間隔中に漏れ出し (または次の適合性テストを実行する直前に除去)、次のパケットがその時点で、またはその後の放出間隔で適合できるようになります。サービス機能は、同じ深さのトークンバケツの観点から見ることもできます。この場合、バケツがいっぱいでない場合、1 つのパケットに十分なトークンが放出間隔で追加されます。この実装では、バースト到着パターン (キューの深さによって制限される) を持つパケットを受信し、常に放出間隔の正確な (整数の) 倍数である間隔で送信します。

しかし、上記のトラフィック シェーピング機能におけるリーキー バケットをメーター (またはトークン バケット) として実装することは、キューとしてのリーキー バケットの説明とまったく同じです。^[3]メーター バージョンの遅延要素はキュー バージョンのバケットです。メーター バージョンのバケットはキューを処理するプロセスであり、リークは、発行間隔がティック間隔と同じになるようにします。したがって、固定長パケットの場合、キューとしてのリーキー バケットの実装は、リーキー バケット (またはトークン バケット) をメーターとして使用するトラフィック シェーピング機能の特殊なケースであり、制限値τは 0 であり、適合性をテストするプロセスは可能な限り低いレートで実行されます。

可変長パケットのキューとしてのリーキー バケットは、メーターとしてのリーキー バケットの特殊なケースと同等であるとも説明できます。提案された実装^[3]は、固定長実装と同様に、キューがバケットではなく遅延要素であるトラフィック シェーピング機能と見なすことができ、キューを処理する機能は、この場合、トークン バケットとして明示的に指定されます。トークン バケットは、適合パケットに対して減算され、固定レートで増加します。したがって、メーターとしてのリーキー バケットとトークン バケットは同等であるため、可変長パケットのキューとしてのリーキー バケットも、メーターとしてリーキー バケット (またはトークン バケット) を使用するトラフィック シェーピング機能の特殊なケースです。

リーキー バケットを可変長パケットのキューとして、トークン バケットの特定の実装として、またはトラフィック シェーピングのメーターとしてのリーキー バケットとして見ると、興味深い結果があります。メーターのバケットには深さ n があり、トークン バケットの場合と同様に、この深さによって出力トラフィックのバースト性が決まります (おそらく、パケットに必要なトークンの平均数または最小数に関連して)。したがって、この「バイト カウント」リーキー バケットをメーターとしての出力のバースト性を定量化することは可能ですが、すべてのパケットが最大長でない場合は意味がありません。ただし、出力のバースト性を定義できるこの能力は、入力がいかにバースト的であっても、リーキー バケット (キューとして) は必ず固定レートの出力を行うという主張と完全に矛盾しています。

• 流動的なキュー
• 一般的なセルレートアルゴリズム
• トークンバケット
• 交通契約
• UPC と NPC