トークンバケット

トークンバケットは、パケット交換ネットワークおよび通信ネットワークで使用されるアルゴリズムです。パケット形式のデータ送信が、帯域幅とバースト性(トラフィックフローの不均一性または変動の尺度)の定義された制限に準拠しているかどうかを確認するために使用できます。また、帯域幅とバースト性に設定された制限に準拠する送信のタイミングを決定するためのスケジューリング アルゴリズムとして使用することもできます。ネットワーク スケジューラを参照してください。

トークン バケット アルゴリズムは、固定容量のバケットのアナロジーに基づいています。このバケットには、通常、バイト単位または所定のサイズの単一パケットを表すトークンが固定レートで追加されます。パケットが定義された制限に準拠しているかどうかを確認する場合、バケットを検査して、その時点で十分なトークンが含まれているかどうかを確認します。十分なトークンが含まれている場合は、適切な数のトークン (たとえば、パケットのバイト長に等しい数) が削除 (「キャッシュイン」) され、パケットが渡されて、たとえば送信されます。バケットに十分なトークンがない場合、パケットは準拠していないとみなされ、バケットの内容は変更されません。準拠していないパケットは、さまざまな方法で処理できます。

• 削除される可能性があります。
• バケット内に十分なトークンが蓄積されると、後続の送信のためにキューに入れられる場合があります。
• これらは送信される可能性がありますが、非準拠としてマークされ、ネットワークが過負荷になった場合は後でドロップされる可能性があります。

適合フローは、平均レートからトークンがバケットに追加されるレートまでのトラフィックを含むことができ、バケットの深さによって決まるバースト性を持ちます。このバースト性は、ジッター許容度、つまり平均レートの制限から予想されるよりもどれだけ早くパケットが適合するか（到着または送信されるか）またはバースト許容度または最大バースト サイズ、つまりある有限期間内に平均レベルよりもどれだけ多くのトラフィックが適合するかのいずれかで表現されます。

トークン バケット アルゴリズムは、概念的には次のように理解できます。

• トークンは毎秒バケットに追加されます。${\displaystyle 1/r}$
• バケットには最大でトークンを保持できます。バケットがいっぱいのときにトークンが到着した場合、そのトークンは破棄されます。${\displaystyle b}$
• nバイトのパケット（ネットワーク層PDU ）が到着すると、
  • バケット内に少なくともn 個のトークンがある場合、バケットからn 個のトークンが削除され、パケットがネットワークに送信されます。
  • 使用可能なトークンがn 個未満の場合、バケットからトークンは削除されず、パケットは非準拠と見なされます。

1 秒ごとに 1 つのトークンをバケットに追加するために必要なクロック解像度がないプラットフォームでこのアルゴリズムを実装する場合は、別の定式化を検討する必要があります。トークン バケットを S ミリ秒ごとに更新できる場合、S ミリ秒ごとに追加するトークンの数 = です。 ${\displaystyle 1/r}$${\displaystyle (r*S)/1000}$

長期的には、適合パケットの出力はトークン レートによって制限されます。 ${\displaystyle r}$

最大可能転送速度をバイト/秒単位で表し ます。${\displaystyle M}$

次に最大バースト時間、つまりレートが完全に利用される時間です。 ${\displaystyle T_{\text{max}}={\begin{cases}b/(Mr)&{\text{ if }}r<M\\\infty &{\text{ else }}\end{cases}}}$${\displaystyle M}$

最大バーストサイズは${\displaystyle B_{\text{max}}=T_{\text{max}}*M}$

トークン バケットは、トラフィック シェーピングまたはトラフィック ポリシングのいずれかで使用できます。トラフィック ポリシングでは、非準拠パケットは破棄 (ドロップ) されるか、優先度が下げられます (輻輳がある場合に下流のトラフィック管理機能がドロップするため)。トラフィック シェーピングでは、パケットは準拠するまで遅延されます。トラフィック ポリシングとトラフィック シェーピングは、通常、過剰なトラフィックまたは過度にバースト的なトラフィックからネットワークを保護するために使用されます (帯域幅管理と輻輳回避を参照)。トラフィック シェーピングは、通常、ホストのネットワーク インターフェイスで使用され、ネットワークのトラフィック管理機能によって送信が破棄されるのを防ぎます。

トークン バケット アルゴリズムは、データベース IO フローの制御にも使用されます。^[1]このアルゴリズムでは、制限は IOPS にも帯域幅にも適用されず、両者の線形結合に適用されます。トークンを IO 要求の重みとその長さの正規化された合計として定義することにより、アルゴリズムは前述の関数の時間微分が必要なしきい値を下回るようにします。

トークン バケット アルゴリズムは、文献に記載されている2 つのバージョンのリーキー バケットアルゴリズムのいずれかと直接比較できます。 ^{[2] [3] [4] [5]}この比較可能なバージョンのリーキー バケットは、関連する Wikipedia のページで、メーターとしてのリーキー バケット アルゴリズムとして説明されています。これはトークン バケットのミラー イメージであり、準拠パケットは、トークン バケット アルゴリズムで準拠パケットによって削除されるトークンに相当する流体を有限容量のバケットに追加し、この流体は一定速度で排出されます。これは、トークンが固定速度で追加されるプロセスに相当します。

ただし、リーキー バケット アルゴリズムの別のバージョン^[3]があり、関連する Wikipedia ページでキューとしてのリーキー バケット アルゴリズムとして説明されています。これは、リーキー バケットをメーターとして使用する特殊なケースであり、バケットを通過する適合パケットによって説明できます。したがって、キューとしてのリーキー バケットはトラフィック シェーピングにのみ適用でき、一般に出力パケット ストリームがバースト的になることを許可しません (つまり、ジッターがありません)。したがって、トークン バケット アルゴリズムとは大きく異なります。

リーキー バケット アルゴリズムのこれら 2 つのバージョンは、どちらも同じ名前で文献に記載されています。このため、このアルゴリズムの特性とトークン バケット アルゴリズムとの比較に関してかなりの混乱が生じています。ただし、基本的に、この 2 つのアルゴリズムは同じであり、正しく実装され、同じパラメータが指定されている場合、まったく同じパケットが適合パケットと非適合パケットとして認識されます。

階層型トークンバケット（HTB）は、Linuxのクラスベースキューイング（CBQ）キューイング規則のより高速な代替手段です。^[6]これは、制限されたクライアントが全体の帯域幅を飽和させないように、 各クライアントのダウンロード/アップロード速度を制限するのに役立ちます。

概念的には、HTB は階層的に配置された任意の数のトークン バケットです。デバイス上の主要な出力キューイング規則 ( qdisc ) は、ルート qdisc と呼ばれます。ルート qdisc には 1 つのクラスが含まれます。この単一の HTB クラスには、 rateとceil の2 つのパラメータが設定されます。これらの値は最上位クラスと同じである必要があり、リンクで使用可能な合計帯域幅を表します。

HTB では、rate は特定のクラスで使用できる保証帯域幅を意味し、ceil (ceil の略) はクラスが消費できる最大帯域幅を示します。クラスが保証を超える帯域幅を要求すると、両方の ceil に達しない限り、親から帯域幅を借りることができます。階層型トークン バケットは、Linux トラフィック制御システム用のクラスフル キューイング メカニズムを実装し、rate と ceil を提供して、ユーザーが特定のトラフィック クラスへの絶対帯域幅を制御したり、追加の帯域幅が使用可能になったときに (ceil まで) 帯域幅の分配比率を示したりできるようにします。

最上位クラスの帯域幅を選択する場合、トラフィック シェーピングは LAN とインターネット間のボトルネックでのみ役立ちます。通常、これは LAN 全体が DSL またはT1接続 によってサービスされている家庭やオフィスのネットワーク環境の場合に当てはまります。

• レート制限
• トラフィックシェーピング
• セマフォのカウント

• John Evans、Clarence Filsfils (2007)。『マルチサービス ネットワーク向け IP および MPLS QoS の導入: 理論と実践』。Morgan Kaufmann。ISBN 978-0-12-370549-5。
• Ferguson P.、Huston G. (1998)。サービス品質: インターネットおよび企業ネットワークでの QoS の提供。John Wiley & Sons, Inc. ISBN 0-471-24358-2。