トークンバケット

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

概要

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

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

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

アルゴリズム

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

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

バリエーション

毎秒1トークンをバケットに追加するために必要なクロック分解能を持たないプラットフォーム上でこのアルゴリズムを実装する場合、別の定式化を検討すると良いでしょう。トークンバケットをSミリ秒ごとに更新できる場合、Sミリ秒ごとに追加するトークンの数は = となります。 1/r{\displaystyle 1/r}（r∗S）/1000{\displaystyle (r*S)/1000}

プロパティ

平均レート

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

バーストサイズ

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

次に最大バースト時間、つまりレートが完全に利用される時間です。 T最大＝{b/（M−r） もし r<M∞ さもないと {\displaystyle T_{\text{max}}={\begin{cases}b/(Mr)&{\text{ if }}r<M\\\infty &{\text{ otherwise }}\end{cases}}}M{\displaystyle M}

最大バーストサイズはB最大＝T最大∗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 ]これは、制限されたクライアントが全体の帯域幅を飽和させないように、 各クライアントのダウンロード/アップロード速度を制限するのに役立ちます。

同じ送信帯域幅を共有する 3 つのクライアント。

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

HTBにおいて、rateは特定のクラスで利用可能な保証帯域幅を意味し、ceil（ceilの略）はクラスが消費できる最大帯域幅を示します。クラスが保証帯域幅を超える帯域幅を要求する場合、両方のceilに達しない限り、親から帯域幅を借りることができます。Hierarchical Token Bucketは、Linuxトラフィック制御システムにクラスフルキューイングメカニズムを実装し、rateとceilを提供することで、ユーザーが特定のトラフィッククラスへの絶対帯域幅を制御できるだけでなく、追加の帯域幅が利用可能になった場合（ceilまで）の帯域幅配分比率を指定することもできます。

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

参照

参考文献

  1. ^ 「混合読み取り/書き込みワークロード向けの新しいIOスケジューラアルゴリズムの実装」 2022年8月3日。 2022年8月4日閲覧。
  2. ^ Turner, J.,通信における新たな方向性（あるいは情報化時代への道？） IEEE Communications Magazine 24 (10): 8–15. ISSN 0163-6804 , 1986. 
  3. ^ a b Andrew S. Tanenbaum, Computer Networks, Fourth Edition , ISBN 0-13-166836-6、Prentice Hall PTR、2003年、401ページ。
  4. ^ ATMフォーラム、ユーザーネットワークインターフェース（UNI）、v. 3.1、 ISBN 0-13-393828-X、Prentice Hall PTR、1995年。
  5. ^ ITU-T、「B ISDNにおけるトラフィック制御と輻輳制御」、勧告I.371、国際電気通信連合、2004年、付録A、87ページ。
  6. ^ 「Linux HTBホームページ」 。 2013年11月30日閲覧。

さらに読む

  • ジョン・エヴァンス、クラレンス・フィルスフィルス（2007年）『マルチサービスネットワークにおけるIPおよびMPLS QoSの導入：理論と実践』モーガン・カウフマン、ISBN 978-0-12-370549-5。
  • Ferguson P.、Huston G. (1998). 『サービス品質：インターネットと企業ネットワークにおけるQoSの提供』John Wiley & Sons, Inc. ISBN 0-471-24358-2。
「 https://en.wikipedia.org/w/index.php?title=Token_bucket&oldid=1331882157#Hierarchical_token_bucket」から取得