QoS（9）帯域制御の制御方法 トークンバケット/リーキーバケット/万能リーキーバケットモデルとは

優先制御とポリシングでは「トークンバケット」、シェーピングでは「リーキーバケット」と呼ばれる制御方法を使用することが多い。幾つかの例を交え、トークンバケットとリーキーバケットの説明をしたい。ちなみに、Backet はバケツのことだ。

トークンバケット

トークンバケットは、基本的にはポリシングの制御モデルだ。図1 の様に、トークンバケットでは、トークン供給機が一定間隔で「トークン(送信権コイン)」を生成しバケツに溜める。受信パケットがポリシング機構通過時に、パケット長に見合う量のトークンがあれば、パケットは通過し送信される。この時、パケット長に相当するトークンがバケツから取り出される。パケット長に見合うトークンがない場合、パケットは廃棄され、トークンは変化しない。トークンバケットモデルでは、パケットはキューに蓄えられない。ポリシング機構に到着するたびに、都度送信か廃棄かを判定する。

トークンバケットは、バースト送信を許容するモデルでもある。図2 の様に、バケツに十分なトークンが溜まっていると、複数のパケットが一括してバースト状に送信される。バケツに入るトークン量の範囲内でバースト量を決めることができる。パケットの到着タイミング、パケットの長さとバースト量しきい値で、バースト送信するパケット数が決まる。図2 では、3つのパケットを順次受信し、「1」と「2」のパケットはトークンが十分あり通過したが、「3」はトークンが足りないため廃棄された。

トークンバケットには特有の用語がある(表1)。用語の内容は図3 を参照いただきたい。この例では、Be は 20480 Byte、Bc は 2048 Byte 、Tcは 0.1 秒に設定されているが、パケット送信がないためトークンは最大値(Be)の 20480 Byte まで積み上がっている。Be でバケツは一杯になったため、これ以上のトークンは受け取らない。一般的にはビット数で表現するが、分かり易くするためバイト数で表現している。

略語	名称	意味
CIR	Committed Information Rate	定期的にバケツに供給されるトークン量(平均レート:ビット/秒) トークンバケットの単位は「ビット」 CIR= Bc/ Tc の関係になる
Bc	Burst Committed	一度に取り出せるトークン量(ビット) Be の範囲内で設定でき、バースト量が決まる
Be	Burst Exceed	バケツに溜められるトークンの最大量 Be を超えるトークンは廃棄される
Tc	Token Create	定期的に供給されるトークンの時間間隔 Tc 時間ごとに Bc 分のトークンがバケツに供給される

図4 は、トークンバケットの動作例だ。この例では、全てのパケット長は 1024バイトで、バースト許容値(Bc)は 2048バイトになっている。1024バイト長のパケットは、トークンが十分あれば、2個まではバースト送信されるが、3個以上は通過できず廃棄される。トークンは、パケット送信のたびに都度パケットの長さ分減算される。

リーキーバケット

リーキーバケット(穴開きバケツ)は、基本的にはシェーピングの制御モデルだ。図5 の様に、蛇口から注いだ水がバケツの穴から常に一定量漏れ出すモデルだ。ネットワークに置き換えると、パケットがバケツに流れ込み、穴から一定の速度で流れ出すモデルになる。不規則な間隔でバケツに入ったパケットは、一定の間隔で規則正しくバケツの穴から漏れ出ていく。パケットはバケツに入るだけ蓄積することができる。

流入量が漏れ出る量より多いと、バケツは一杯になり溢れる。溢れたパケットは捨てられる。流入量が十分ありバケツにパケットが溜まった状態では、バケツから漏れ出すパケットは規則正しく流れ出すが、バケツが空になると漏れ出すパケットが「歯抜け」になる。ジッタの発生だ。バケツの構造は単純な FIFO(First Input First Output :ファイフォ)だ(図6)。

「リーキーバケット」を「トークンバケット」風に書くと、図7 の様になる。大きな違いが2つある。一つは、バケツにはパケットが入り、パケットを蓄積できるキューになっている。もう一つは、判定部(シェーピング機構)ではパケットを廃棄せず、キューの入り口で廃棄されることだ。

リーキーバケットの実態は、単純なFIFO(First Input First Output :ファイフォ)キューだ。このキューの動作を決めるパラメータは「出力帯域」「最大パケット長」と「キューの深さ (バケツの大きさ)」の3つだ。最大パケット長は、VLAN タグ付きイーサネットでは 1522バイトだ。キューの深さは装置設計者の考え方次第だが、帯域制御専用装置では、1秒程度パケットを連続受信できるキューを備えている。

リーキーバケットの主な実現方法は次の3つだ。

「固定長パケット」では、リーキーバケットの動作を決めるパラメータは、「出力帯域」と「キューの深さ」だけになり、動作は単純だ、「可変長パケット」になると少し複雑な動作をする。まずは、「固定長パケット」で説明しよう。

固定長パケット動作

図8 では、1秒間に10パケットを等間隔で送信するモデルだ。パケットの送信間隔は、 0.1 秒になる。送信の可否を決めるクレジット(Credit)は、初期状態の 0 からリニアに増加し、0.1 秒後にパケット送信クレジットは「1」になり、パケットの送信が可能になる。

この時点でバケツ(キュー)にパケットがあれば、送信を開始する。図8 ではパケットをまだ受信していないので、クレジット「1」を維持する。トークンバケットでは、バケツが一杯になるまでトークンを供給し続ける。しかし、リーキーバケットではバーストを避けるためクレジット「1」を超えてはいけない。

図9 は、10個のバースト受信パケットを平滑化する例だ。図8 と同様に、1秒間に10パケット送信する想定モデルになっている。初期段階でバースト受信した10個の固定長パケットが、0.1秒ごとに送信されている。リーキーバケットの固定長パケットモデルは、バーストが全くない理想的なシェーピングができる。

クレジットは、初期状態「0」からリニアに増加し、0.1秒後に「1」になる。クレジットが「1」になりキューにパケットがあると送信を開始する。同時にクレジット値は減算され、「1」→「0」に変わる。再びクレジットが増加し「1」になるまでは、パケットは送信できない。この動作を繰り返すことで、0.1秒ごとに規則正しくパケットは送信される。

図10 の様に、キューが空になりパケットが無い状態ではパケットを送信できないため、パケット受信まで待ち状態が続く。キューにパケットが無い状態では、パケット間隔は想定した時間より広くなる。

可変長パケット動作

イーサネットは、64 ~1522 バイトの間でパケット長が変わる。リーキーバケットモデルは、可変長パケットでは少し複雑な動きをする。固定長パケットの場合は、一定時間間隔で1パケット分の送信クレジットを与えればよいが、可変長パケットではこの手は使えない。出力帯域を決めるパラメータとして次の何れかを使用する必要がある。まずは、一般的な「Byte または bit レート」のケースを説明したい。

Byte または bit レート制御

バイト数で「送信クレジット」を与える場合、クレジットの最大値はイーサネットの最大 長(1522Byte)以上でなければならない。1522Byte 未満では、FIFO から最大長のパケットを取り出せず動作しなくなる。

図11 では、1 秒間に 500 バイトパケット 10 個を等間隔で送信することを想定したモデルだ。パケットの送信間隔は 0.1 秒になる。送信の可否を決めるクレジット(Credit)は、初期状態の「0」からリニアに増加し、0.1 秒後に 500 バイト相当分まで増加する。ここまでは固定長パケットと同じだ。しかし、可変長パケットではクレジットを「最大パケット長」まで加算しなければならない。クレジットは、そのまま増え続け、約0.3 秒後に 1522 バイト相当に達し、ここで増加が止まる。

この方式では、0.1 秒後に 500 バイトパケットが送信可能になり、0.3 秒後には 1522 バイトパケットが送信できる。最も小さい 64 バイトパケットは、0.013 秒後には既に送信可能になっている。つまり、可変長パケットでは「受信パケット≦クレジット」であれば、パケットを送信できる。クレジットがパケットより小さい場合は、送信できない

図12 は、10個のバースト受信パケットを平滑化する例だ。図11 と同様に、1秒間に 500バイトパケットを 10 パケット送信するモデルになっている。初期段階でバースト受信した10個の500バイトパケットが、0.1秒ごとに送信されている。この条件では、リーキーバケットの可変長パケットモデルも、バーストが全くない理想的なシェーピングができている。

クレジットは、初期状態「0」からリニアに増加し、0.1秒後に「500バイト相当」になる。クレジットがパケット長と一致したところで、キューにパケットがあると送信を開始する。送信と同時にクレジット値は減算され、「500バイト相当」→「0」に変わる。再びクレジットが増加し「500バイト相当」になるまでは、パケットは送信できない。この動作を繰り返すことで、0.1秒ごとに規則正しくパケットは送信される。

図13 は、バーストが解消できないケースだ。キューに格納された複数パケット分のクレジットがあると、バースト送信が起きる。この例では、2パケット受信、3パケット受信のいずれもバースト送信となり、シェーピングできていない。

この現象は、1522バイトの1/2以下のパケット(761バイト以下)を受信したときに起きる。しかし、現実のシェーピングは、映像ストリームやファイル転送に施すことが多い。これらのパケットは、通常 1000バイト以上の大きさがあるため、現実にはこの現象は極めてまれだ。余り心配することではない。

パケット間隔制御

一般的なシェーパは「Byte または bit レート制御」が圧倒的に多い。パケット間隔制御の事例は少ない。実装が非常に面倒なためだ。パケット間隔制御を行うためには、 1本1本の TCP セッションや映像フローを識別し、個別のキューを用意しなければならない。また、パケット間隔を高精度に制御するためには、1マイクロ秒からナノ秒オーダーの間隔制御が必要になる。当然、コストアップするためスイッチやルータに実装されることは稀で、帯域制御専用機に実装されることになる。パケット間隔制御は、1つのフローに長さの異なるパケットが混在しても、バーストは起きない。最も優れたシェーピング機構だ。

動作原理は、送信したパケットの長さ(時間)に応じて次のパケットとのギャップを調整することで帯域制御を行う。帯域計算は、パケットの先頭から次のパケットの先頭までを1サイクルとして計算する。バースト受信やパケット長変動に対応し、確実に帯域を制御できるが、バケツが空になるとパケット間ギャップが想定以上に広がり、フロー全体(例えば1本の映像)の平均帯域が低くなる。

図14 上段の例では、100Mbps イーサネットで最初のパケットは 500Byte(40μ 秒)、2番目のパケットは 1000Byte(80μ秒)の長さで、それぞれ次のパケットとの間隔は、40μ秒と80μ秒になっている。パケット送信時間はサイクルの 50% で帯域
は 50Mbps になる。下段の例は、パケット長は同じだがパケット間隔が 160μ秒と 320μ秒になっている。パケット送信時間はサイクルの 20% で帯域は 20Mbps になる。

万能リーキーバケットモデル?

「トークンバケット」はポリシング、「リーキーバケット」はシェーピングの制御モデルとして話を進めてきた。しかし、ここで説明したモデル以外にも考え方の異なるモデルや、パラメータ制御が異なるモデルが多数ある。例えば、Ethernet TSN は「リーキーバケット」でシェーピングを実現しているが、クレジットの加減算や判定方法が異なる。詳しくは次回以降に紹介したいと思っている。

今回紹介した「リーキーバケット」はシェーピングに機能を絞ったモデルだ。「Leaky bucket as a queue」とも呼ばれるモデルで、機能が少なく比較的分かり易いモデルだ。リーキーバケットのもう一つのモデルは「Leaky bucket as a meter」で、一つのモデルでポリシングとシェーピングを実現できる。この方式のポリシングは、トークンバケットと同じだが、パラメータ構成が合わせ鏡の様に逆転している。非常に便利なモデルである反面、多機能なため分かりづらい面のある。今回は概念の紹介にとどめたい。興味のある方は、英語版の Leaky bucket Wikipedia を参照いただきたい。ITUT の 関連文献もここから探すことができる。

	トークンバケット	リキーバケット Leaky bucket as a queue	リーキーバケット Leaky bucket as a meter
実現する機能	ポリシング	シェーピング	ポリシング & シェーピング
			※万能リーキーバケットモデル？

Leaky bucket as a meter

このモデルでは、パケットはバケツに入らない。穴開きバケツからは常に一定量の水が漏れだしている。パケットが判定ポイントに到着し、バケツの水位が判定レベル以下だとパケットを出力する。この時、パケットの長さに応じた水滴がバケツに注ぎ込まれ減算される。これが基本的な動作だ(図15)。この図にはないが、クレジット加算機構とパケット長相当クレジットの減算機構が必要だ。

このモデルのポリシング動作では、パケットが出力される動作は基本動作と同じだ。判定ポイントで、バケツの水位が判定レベルを超えていると、この時点でパケットを廃棄しパケットの長さに応じた水滴も捨てられ減算しない。パケットの廃棄場所やバケツの水の出し入れの考え方は「トークンバケット」と同じだ(図16)。

このモデルのシェーピング動作は、パケットが出力される動作は基本動作と同じだ。判定ポイントで、バケツの水位が判定レベルを超えていると、この時点でパケットを止めるだけだ。パケットの廃棄もパケットの長さに応じた水滴の廃棄もない。パケットはキューに蓄積され、キューに収まらない場合は、キューの末尾で廃棄される(図17)。