よくわかるLinux帯域制限

2014/10/08

yuya.yaguchi

矢口です。

みなさんはLinuxのtcという機能をご存知でしょうか。送信するパケットの帯域制御を行うことができる大変強力な機能で、グリーでもいくつかの用途で使用されています。

具体的な事例の一つはRedisです。Redisではreplicationを新規に開始する際やfailoverが発生しmasterが切り替わった際(特に2.6系)にストアされている全データが転送されます。しかし帯域制限をかける機能がないため、ネットワーク帯域を圧迫してしまう危険性があります。また通常のクライアントとの通信でも大量のクエリにより予想以上の帯域を使用してしまう可能性があります。このような場合にtcを用いることでRedisの使用する帯域をコントロールできます。

このように有用なtcですが残念なことに日本語/英語ともにわかりやすい解説や詳細な情報は多くありません。

私も社内において使われていたtcの設定に問題が見つかり、修正が必要になった際に初めて触れたのですが情報が少なく苦労しました。

この文章はその数少ないドキュメント（参考文献の項目に記載してあります）やカーネルのコードを読みながら理解した内容について社内向けにまとめたものです。

Abstract

LinuxにはQoSやTraffic Control(tc)と呼ばれるIPパケットの送信制御機構があります。tcは様々な目的に利用することができますが、最も一般的な利用方法は特定のソフトウェア/セッションの帯域を制限したい場合でしょう。
大きなトラフィックを発生させるソフトウェアの多くはbwlimitといったパラメータを持ちトラフィックを制限できるようになっていますが、中にはそのような機能を保たないものもあります。例えばRedisは新しいReplicationを張る際にストアされたデータすべてをネットワークをいっぱいに使って送信しようとします。
tcを利用することでこのような通信の帯域使用を一定値に制限し、同じサーバー/スイッチ/ルーターを使用する他の通信に影響を及ぼすことを防ぐことができます。

この文章ではtcについて帯域制限に利用する機能を中心に原理・実装を解説し、実用的な設定方法を説明していきたいと思います。

より具体的な設定の指針等については別ドキュメントにまとめましたのでそちらをご確認ください。
Linux TC (帯域制御、帯域保証) 設定ガイドライン

Traffic Controlのコンセプト

Traffic Controlは送信したいパケットをschedulerと呼ばれるものに通すことで行われます。schedulerはキューイング規則(Queueing discipline: qdisc)とも呼ばれ、パケットを一時的に格納し、順番を並べ替えたり、遅延させたり、破棄したりすることができます。以下qdiscと呼びます。

qdiscは極めて高度で複雑な構造となっていますが、外部からのインターフェースはとてもシンプルなものとなっています。外部から見たqdiscの操作は主に2つしかありません。enqueueとdequeueです。

qdiscがない場合のパケット送信

まずqdiscが存在しないと仮定した場合を考えてみましょう。パケット送信は以下の図のようにプロトコル層がdevice driverにパケットを渡す処理となっています。

# packet send

プロトコル層 -> (送信される予定のパケット) --> device driver

# packet send

プロトコル層 -> (送信される予定のパケット) --> device driver

qdiscはこのプロトコル層とdevice driverの間に入ります。

enqueue

enqueueは送信される予定のパケットをqdiscに格納しようとする処理です。主にTCPなどのプロトコル層から呼び出されます。enqueueは失敗することもあり、その場合はそのパケットはdropします。どのような場合にenqueueが成功しどのような場合に失敗するかはqdisc内部で判断され、外部には結果のみが伝わります。

# packet enqueue

プロトコル層 --> (送信される予定のパケット) --> qdisc
                                       |
                                       v
　　　　　　 　　        　　　　　　 　   drop

# packet enqueue

プロトコル層 --> (送信される予定のパケット) --> qdisc

　　　　　　　　　　　　　　　 drop

dequeue

dequeueはqdiscに格納されたパケットを取り出し、デバイスドライバに渡す処理です。dequeueもenqueueと同様に失敗する場合があります。失敗は単にqdiscが空の場合にも発生しますし、何らかの理由で格納されているパケットをqdiscが送信したくない場合にも発生します。どのような場合に成功しどのような場合に失敗するかはqdisc内部で判断され、外部には結果のみが伝わります。

# packet dequeue

qdisc --> (送信される予定のパケット) --> device driver

# packet dequeue

qdisc --> (送信される予定のパケット) --> device driver

qdiscの一覧と目的、仕組み

この章では主なqdiscの一覧とその目的と仕組みについて説明します。

classless qdisc

classlessなシンプルなqdiscについて説明します。

PFIFO

PFIFO(Packet First-In First-Out)は最初に入ったパケットが最初に出ていくシンプルなqdiscです。
P(Packet)というプレフィックスがついているのは格納できるパケットの限界をパケット数で規定しているからです。限界をByteで規定できるBFIFOというものもあります。

PFIFO_FAST

PFIFO_FASTはPFIFOにパケットの優先度(Priority: prio)を考慮する機能を追加したものです。内部に複数のqueueを持っており、enqueueの際にIPヘッダのTOSを読み優先度で分類してqueueに格納します。dequeueの際は優先度の高いqueueから先に取り出されます。
このPFIFO_FASTはLinuxのデフォルトqdiscとなっています。
また、格納できるpacket数は指定がない場合tx_queue_lenとなります。この値はifconfigコマンドのtxqueuelenの項目で確認/変更することができます。

SFQ

SFQ(Stochastic Fair Queuing)はセッションごとに公平にパケット送信機会を得ることができるqdiscです。
PFIFOで多数のパケットを送信するセッションで帯域やqdiscがいっぱいとなっている場合、あまりパケットを送信しないセッションがパケットを送信しようとしても、enqueueできずdropしてしまったり、既に多数のpacketがqdiscに格納されていてdequeueするまでに長い時間がかかることがあります。このような場合にPFIFOの代わりにSFQを使用することでこのようなセッションがパケットをdropせずに迅速に送信できる可能性を高めることができます。
ただしSFQを使用することでlatencyが大きくなってしまうという欠点が存在します。

SFQでは多数のqueueとハッシュテーブルを用意し、パケットを所属するセッションに応じたqueueに格納します。dequeueでは各queueを順番にまわり(Round Robin)パケットを取り出します。また1つのqueueから一定数のパケットを取り出すと強制的に次のqueueに取り出す対象を移します。
同一セッションかどうかを判定するのにはハッシュ値のkeyにはdestination address, source address, protocol番号が使用されます。プロトコルがTCP, UDPなどの場合はsource port, destination portも使用されます。

TBF

TBF(Token Bucket Filter)はbitrateを制御するためのqdiscです。
Token Bucketという概念を用いることでbitrate制限を実現しています。
Token Bucketは時間経過によりtokenが追加されるバケツでパケットをdequeueする際にdequeueしたパケットのbyte数分tokenを消費します。tokenをすべて消費しバケツが空になった状態ではdequeueが失敗します。
指定したbitrateより少ないbitrateの分しか送信しようとしているパケットがないときにはバケツにはtokenが貯まります。貯まっているtokenの分のパケットについては連続してdequeueを行うことができ、これを burst と呼びます。
パラメータとしてburst（バケツの大きさ）とbitrate（時間あたりのバケツへのtokenの供給量）を指定することでパケット送信の特性をコントロールできます。

なぜこのようなややこしい仕組みとなっているかは後の章「bitrateとtimer解像度」で説明します。

※なおバケツというのはあくまでメタファーであり、実装上はtokensといった名前のint型の変数です。そのためburstを大きくして例えば10MBにしても何かのバッファとして10MBメモリを多く消費するといったことはありません。
（このあたりは詳しく調べていないのですが、パケット送信において消費するメモリを決定するのは/proc/sys/net/core/wmem_default, /proc/sys/net/core/wmem_max, /proc/sysy/net/ipv4/tcp_wmem, 各qdiscのlimitなどでしょう）

classful qdisc

classful qdiscとはclass(階層を持った分類）構造を持ったqdiscです。ここでのclassにはオブジェクト指向などにおけるclassの意味合いはないことに注意してください。主なclassful qdiscにHTBがあります。

classful qdiscの仕組み

classful qdiscは内部に複数のqdiscを持ち、enqueueされようとしているパケットはいずれかの内部qdiscに格納されます。classful qdiscにおいては内部でのenqueue処理が2つに分かれます。classifyと内部qdiscへのenqueueです。

classify、class構造、内部qdiscについてそれぞれ説明していきます。

classify

※筆者はclassについては詳しくないため、下記の記述は正確でない可能性があります。

classifyはfilterからどの内部qdiscに格納するべきかを決定する処理です。

下記のコマンドを例にしてみましょう。

# コマンド例
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb default 20
tc class add dev bond0.1230 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc class add dev bond0.1230 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb
tc class add dev bond0.1230 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip sport 6379 0xffff flowid 1:10

# コマンド例

tc qdisc del dev eth0 root

tc qdisc add dev eth0 root handle 1: htb default 20

tc class add dev bond0.1230 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc class add dev bond0.1230 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb

tc class add dev bond0.1230 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip sport 6379 0xffff flowid 1:10

このコマンドのうち3-5行目は実はclassifyには関係がありません。

# コマンド例(classifyに関係する箇所のみ)
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb default 20
tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip sport 6379 0xffff flowid 1:10

# コマンド例(classifyに関係する箇所のみ)

tc qdisc del dev eth0 root

tc qdisc add dev eth0 root handle 1: htb default 20

tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip sport 6379 0xffff flowid 1:10

1:10といった数字が難解に思えるでしょう。この数字はclassidと呼ばれ、majorid:minoridという書式になっています。
今回のコマンドにはわずかなclassしか登場しませんが内部的にはもっとたくさんのclassidが存在します。たとえばmajorid 1の中には1:0, 1:1, 1:2, ..., 1:100, 1:1000, ...といったclassidが存在します。classifyではこの中で最も小さな番号から分類に利用しようと試みます。今回の例では次にようになります。

1:0を確認する
1:0はfilterである。IPパケットがTCP、UDPなどであった場合にsource portが6379であるか確認し、そうであれば1:10に分類し、classifyを完了する。
2に該当しなかった場合、他にfilterがないため、defaultで設定された1:20に分類し、classifyを完了する。

class構造

先ほどのコマンド例ではclassifyのルールだけでなくclass構造も定義していました。今回の例だと下図のような構造になります。

# コマンド例
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb default 20
tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip sport 6379 0xffff flowid 1:10

# コマンド例

tc qdisc del dev eth0 root

tc qdisc add dev eth0 root handle 1: htb default 20

tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc filter add dev eth0 protocol ip parent 1:0 prio 1 u32 match ip sport 6379 0xffff flowid 1:10

# クラス図

  root(1:)
     |
    1:1
     |
  ------
  |     |
1:10  1:20

# クラス図

root(1:)

1:1

------

| |

1:10 1:20

classifyではパケットがこのtreeのような構造のいずれかの葉(leaf)に分類されるようなルールを設定する必要があります。
では、このclass構造はどのように利用されるのでしょうか。実はそれはclassful qdiscの実装に任されています。

内部qdisc

内部qdiscはclassfulなqdiscの内部で使用されるqdiscです。一般的にはclassless qdiscであるPFIFOやSFQなどが使用されます。
class構造の葉(leaf)となる要素にはかならずqdiscが1つ付属します。

以下の例ではclassful qdiscであるAのleafとなる1:10と1:20の内部qdiscとしての処理をBとCに行わせるようhandleしています。
ここではBとCに新たなmajorid 100:と200:を与えていますが、PFIFOはclassless qdiscであるため大きな意味は持ちません。他のmajoridとかぶらないものを指定すれば問題ありません。

# コマンド例
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb default 20 # qdisc A
tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc qdisc add dev eth0 parent 1:10 handle 100: pfifo limit 1000 # inner qdisc B
tc qdisc add dev eth0 parent 1:20 handle 200: pfifo limit 1000 # inner qdisc C

# コマンド例

tc qdisc del dev eth0 root

tc qdisc add dev eth0 root handle 1: htb default 20 # qdisc A

tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc qdisc add dev eth0 parent 1:10 handle 100: pfifo limit 1000 # inner qdisc B

tc qdisc add dev eth0 parent 1:20 handle 200: pfifo limit 1000 # inner qdisc C

# クラス図と内部qdisc

   root(1:)
      |
     1:1
      |
  ---------
  |        |
1:10     1:20
  |        |
B(100:)  C(200:)

# クラス図と内部qdisc

root(1:)

1:1

---------

| |

1:10 1:20

| |

B(100:) C(200:)

なお、内部qdiscは指定を省略した場合にも暗黙的に作成されます。HTBの場合PFIFOが作成されます。

# コマンド例
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb default 20 # qdisc A
tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

# 以下のコマンドと同等の指定が暗黙的に行われる
# tc qdisc add dev eth0 parent 1:10 handle &lt;XXXX&gt;: pfifo limit $<tx_queue_len>
# tc qdisc add dev eth0 parent 1:20 handle &lt;XXXX&gt;: pfifo limit $<tx_queue_len>

# コマンド例

tc qdisc del dev eth0 root

tc qdisc add dev eth0 root handle 1: htb default 20 # qdisc A

tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

# 以下のコマンドと同等の指定が暗黙的に行われる

# tc qdisc add dev eth0 parent 1:10 handle <XXXX>: pfifo limit $<tx_queue_len>

# tc qdisc add dev eth0 parent 1:20 handle <XXXX>: pfifo limit $<tx_queue_len>

HTB

HTB(Hierarchical Token Bucket)は階層構造とTBF機能を持ったclassful qdiscです。TBFと比較すると以下のような機能が追加されています。

トラフィックを分類してトラフィックごとに帯域制限を行うことができる
分類されたトラフィックが確実に使用できる帯域を確保する帯域保証ができる
classのtree構造を持つことができ、その中で帯域を譲りあうことができる。

HTBでは各classが使用できる帯域を指定することができます。あらためて今まで利用してきた例を見てみましょう。

# コマンド例
tc qdisc del dev eth0 root
tc qdisc add dev eth0 root handle 1: htb default 20 # qdisc A
tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb
tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

# コマンド例

tc qdisc del dev eth0 root

tc qdisc add dev eth0 root handle 1: htb default 20 # qdisc A

tc class add dev eth0 parent 1: classid 1:1 htb rate 1000Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:10 htb rate 200Mbit ceil 200Mbit burst 10Mb cburst 10Mb

tc class add dev eth0 parent 1:1 classid 1:20 htb rate 800Mbit ceil 1000Mbit burst 10Mb cburst 10Mb

rate と ceil が帯域についての指定です。この2つの概念について説明するのはとても難しいのですが、一般的な使用方法においてのことについてのみですと比較的簡単なものとなります。
またburstとcburstはそれぞれrateとceilに対応するtoken bucketのsizeとなります。後述する方法で計算・設定してください。
HTBにも同様の機能があった、ceilから説明していきます。

ceil

ceilはそのclassが使用することができる最大の帯域、つまり帯域制限の値です。上記の例ですと1:1は1000Mbits/sに、1:10は200Mbits/sに、1:20は1000Mbits/sに制限されています。

ceilを指定するとき、子のceilのうち最大のものが親のceilと同一かそれ以下になるようにしてください。さもないと、挙動の説明が大変難しいものとなります。ただし合計値の計算は厳密である必要はなく、概ね合っていれば実用上の問題はありません。

ceilが明示的に指定されない場合、rateと同一の値となります。

rate

rateはclass構造の最上位とそれ以外で意味合いが異なります。

最上位では単にbitrateの上限を意味します。これはceilと同じです。そのため最上位classではrate=ceilとすることを推奨します。

それ以外の箇所ではrateはそのclassに保証されている帯域です。上記の例ですと1:1には1000Mbits/sが、1:10には200Mbits/sが、1:20には800Mbits/sが使用できることが保証されています。

rateを指定するとき、子のrateの合計が親のrateと同一かそれ以下になるようにしてください。さもないと、挙動の説明が大変難しいものとなります。ただし合計値の計算は厳密である必要はなく、概ね合っていれば実用上の問題はありません。
今回の例ですと
200Mbits/s+800Mbits/s=1000Mbit/s
で親のrateと子のrateの合計が同一のものとなっています。

注意点として、実際には1000Mbits/sよりも速度がでない回線を使用する場合、1:10と1:20が2対8の割合で回線を分け合える訳「ではない」です。番号が小さい1:10のパケットが優先的に送信され、quantum(後述)で指定したByte数送信すると次の1:20に切り替わります。そのため、送信するパケットのByte数が大きいときは1対1に近い比率となります。
rateは親のrateが保証されているという前提で子に分け与えられています。指定したrateの中で最も親となるものの子供の合計、この例ですと1:10と1:20の合計の1000Mbit/sはこの設定を行う者自信がなんらかの方法で保証する必要があります。

帯域(rate)の分けあい

ある程度の帯域を保証したいが、保証した帯域を常に使用しつづける訳ではないというトラフィックは往々にして存在します。HTBではそのようにして確保したものの使用していない帯域を、別のトラフィックが必要している場合はそちらに分けあたえることができます。これはHTBのドキュメントや実装ではborrowやlendという表現を用いていますが、借りたものを返したりするわけではないので、分けあいや分け与えという表現が適切でしょう。
具体的にはパケットをdequeueする際、以下のようなロジックで分けあいが発生します。

mainoridの小さいleaf classからrate token bucketを確認し、tokenが残っていればそれを使用する。親、その親（いれば）、...、rootのrate token bucketからも同じ量のtokenを減らす。
leaf classのrate token bucketが空の場合、別のleaf classのパケット送信に処理を移す。
すべてのleaf classでパケットdequeueができないが、いずれかのleafのqdiscにパケットが存在する場合、leafの1つ上の階層の親のclass達を調べ始める。
親をたどっていきtokenが残っているclassが存在しないか調べる。みつかった場合にはその親とそこよりも上のclassからtokenを減らす。子のtokenは減らさない。

以下のような構成からdequeueするシナリオを考えてみましょう。1tokenは1byteと結びつけられることにします。

class 1:1  has 300 tokens
class 1:10 has 200 tokens
class 1:20 has 100 tokens
qdisc B    has 100bytes * 1 packet
qdisc C    has 100bytes * 2 packets 

   root(1:)
      |
     1:1
      |
  ---------
  |        |
1:10     1:20
  |        |
B(100:)  C(200:)

class 1:1 has 300 tokens

class 1:10 has 200 tokens

class 1:20 has 100 tokens

qdisc B has 100bytes * 1 packet

qdisc C has 100bytes * 2 packets

root(1:)

1:1

---------

| |

1:10 1:20

| |

B(100:) C(200:)

最初にleaf classからdequeueが試みられます。番号が若い1:10からdequeueが行われます。

class 1:1  has 300 -> 200 tokens
class 1:10 has 200 -> 100 tokens
class 1:20 has 100 tokens
qdisc B    has 100bytes * 1 -> 0 packet
qdisc C    has 100bytes * 2 packets

class 1:1 has 300 -> 200 tokens

class 1:10 has 200 -> 100 tokens

class 1:20 has 100 tokens

qdisc B has 100bytes * 1 -> 0 packet

qdisc C has 100bytes * 2 packets

次のdequeueでは1:10からdequeueできるpacketは存在しないため、1:20からdequeueが行われます。

class 1:1  has 200 -> 100 tokens
class 1:10 has 100        tokens
class 1:20 has 100 ->   0 tokens
qdisc B    has 0 packet
qdisc C    has 100bytes * 2 -> 1 packets

class 1:1 has 200 -> 100 tokens

class 1:10 has 100 tokens

class 1:20 has 100 -> 0 tokens

qdisc B has 0 packet

qdisc C has 100bytes * 2 -> 1 packets

これで1:20のtokenは0になりました。次のdequeueで再び1:20からdequeueを行おうと試みるのですがtokenが足りません。
そこでleafの1つ上の階層(1:1)からのdequeueが試みられます。1:1にはまだtokenがありますね。

class 1:1  has 100 ->   0 tokens
class 1:10 has 100        tokens
class 1:20 has   0        tokens
qdisc B    has 0 packet
qdisc C    has 100bytes * 1 -> 0 packets

class 1:1 has 100 -> 0 tokens

class 1:10 has 100 tokens

class 1:20 has 0 tokens

qdisc B has 0 packet

qdisc C has 100bytes * 1 -> 0 packets

1:20に与えられたtokenは使い果たしていたものの1:1にtokenが残っていたため無事にdequeueが行えました。これが分けあいです。

なお、当然ですが1:10などがtokenを使い切っていた場合にはその親の1:1のtokenも減ってしまうため、分けあいはできないことになります。

ちなみに、最後の状態でBにパケットがenqueueされ、dequeueしようとするとどうなるのでしょうか。

class 1:1  has   0 tokens
class 1:10 has 100 tokens
class 1:20 has   0 tokens
qdisc B    has 100bytes * 0 -> 1 packet
qdisc C    has 0 packets

class 1:1 has 0 tokens

class 1:10 has 100 tokens

class 1:20 has 0 tokens

qdisc B has 100bytes * 0 -> 1 packet

qdisc C has 0 packets

こうなります。

class 1:1  has   0 -> -100 tokens
class 1:10 has 100 ->    0 tokens
class 1:20 has   0         tokens
qdisc B    has 100bytes * 1 -> 0 packet
qdisc C    has 0 packets

class 1:1 has 0 -> -100 tokens

class 1:10 has 100 -> 0 tokens

class 1:20 has 0 tokens

qdisc B has 100bytes * 1 -> 0 packet

qdisc C has 0 packets

なんと1:1のtokensが-100になってしまいました。このようにtoken bucketはマイナスの値をとることもできます。

quantum

quantumとはdequeue対象のclassを強制的に切り替える機能のしきい値[Byte]です。デフォルトでは以下の擬似コードのように算出されます。r2qはRate To Quantumの略でrate[Byte/Sec]からquantumへ変換する係数で、デフォルト値は10です。

quantum' = rate[Byte/Sec] / r2q
if quantum' < 1000
  quantum = 1000
else if quantum' > 200000
  quantum = 200000
else
  quantum = quantum'

quantum' = rate[Byte/Sec] / r2q

if quantum' < 1000

quantum = 1000

else if quantum' > 200000

quantum = 200000

else

quantum = quantum'

quantumは小さすぎると内部的なclassのlookup処理が増えパフォーマンスに影響し、大きすぎると特定のclassのみがdequeueし続けることとなります。通常はr2q=10のままで問題ないでしょう。
r2qからの計算でquantumが1000未満や200000を超える時、kernelで以下のような警告がでます。無視しても構いませんがquantumを明示的に指定することで警告を避けることができます。

HTB: quantum of class %X is small. Consider r2q change.
HTB: quantum of class %X is big. Consider r2q change.

1 2	HTB: quantum of class %X is small. Consider r2q change. HTB: quantum of class %X is big. Consider r2q change.

bitrateとtoken bucketとtimer解像度

token bucketの説明でbucket size/buffer/burstなどの名前で呼ばれていたパラメータについて説明します。なぜこのようなものが必要なのでしょうか。一定量までは速度制限をかけたくない場合にburstという概念は便利そうですが、むしろ一瞬でもbitrateを超えることは避けたいと思うことがほとんどなのではないでしょうか。

token bucketの実装

これまでの説明ではtoken bucketはこのような仕組みだと説明しました

+のタイミングでtoken増加量が1packet分になる

         |dequeue  |dequeue  |dequeue  |dequeue  |dequeue  |dequeue
<ol>
<li>> (time)

+のタイミングでtoken増加量が1packet分になる

<ol>

<li>> (time)

しかし実際には上図のようにtokenがpacketを送信できる量たまった瞬間にdequeueされるわけではありません。「Traffic Controlのコンセプト」で書いたように、外部からdequeue要求が来たタイミングでしかdequeueすることができません。詳しくは次の「bitrateとdequeue機会」で説明しますが、dequeue機会は制御できないタイミングで発生し、その間隔は10ms以上になることもあります。

この10msという数字はLinuxのHigh Resolution Timer(hrtimer)でのイベント発生の最小間隔です。token bucketの実装にはこのhrtimerが使用されています。そしてこのtimerの解像度はkernelのビルドオプションによって異なりますが10ms(1000HZ)や4ms(250HZ)であることが多いです。

手元のUbuntuでは以下のコマンドで確認することができ250HZ=4msでした。RedHat系では1000HZ=1msであることが多いそうです。

$ cat /boot/config-`uname -r` | grep HZ
CONFIG_NO_HZ_COMMON=y
# CONFIG_HZ_PERIODIC is not set
CONFIG_NO_HZ_IDLE=y
# CONFIG_NO_HZ_FULL is not set
CONFIG_NO_HZ=y
CONFIG_RCU_FAST_NO_HZ=y
# CONFIG_HZ_100 is not set
CONFIG_HZ_250=y
# CONFIG_HZ_300 is not set
# CONFIG_HZ_1000 is not set
CONFIG_HZ=250
CONFIG_MACHZ_WDT=m

$ cat /boot/config-`uname -r` | grep HZ

CONFIG_NO_HZ_COMMON=y

# CONFIG_HZ_PERIODIC is not set

CONFIG_NO_HZ_IDLE=y

# CONFIG_NO_HZ_FULL is not set

CONFIG_NO_HZ=y

CONFIG_RCU_FAST_NO_HZ=y

# CONFIG_HZ_100 is not set

CONFIG_HZ_250=y

# CONFIG_HZ_300 is not set

# CONFIG_HZ_1000 is not set

CONFIG_HZ=250

CONFIG_MACHZ_WDT=m

このようなtimerの事情を反映させると以下のような図になります。

action:                                   |dequeue*5          |dequeue*5
timer callback:                           +                   +
tokens in the bucket: 0 1   2   3   4   5 | 0   1   2   3   4 | 0   1   2
token increase:         +   +   +   +   + | +   +   +   +   + | +   +   +
time:                  -------------------|10ms---------------|20ms--------->

action: |dequeue*5 |dequeue*5

timer callback: + +

tokens in the bucket: 0 1 2 3 4 5 | 0 1 2 3 4 | 0 1 2

token increase: + + + + + | + + + + + | + + +

time: -------------------|10ms---------------|20ms--------->

ここでbucket sizeを考えてみましょう。bucket sizeを2としてみましょう

action:                                   |dequeue*2          |dequeue*2
timer callback:                           +                   +
tokens in the bucket: 0 1   2   2   2   2 | 0   1   2   2   2 | 0   1   2
token increase:         +   +   +   +   + | +   +   +   +   + | +   +   +
time:                  -------------------|10ms---------------|20ms--------->

action: |dequeue*2 |dequeue*2

timer callback: + +

tokens in the bucket: 0 1 2 2 2 2 | 0 1 2 2 2 | 0 1 2

token increase: + + + + + | + + + + + | + + +

time: -------------------|10ms---------------|20ms--------->

dequeueできる量が減ってしまいました。このようにbucketが小さすぎるとdequeue間隔よりも小さな間隔で溢れてしまうのです。制限したbitrateを超えてしまうのも問題ですが、制限したbitrateに達しないのもまた問題ですね。

burst, cburstの理論値の算出

このようにbitrateが小さすぎる現象を避けるためのbucket size(buffer, burst)の最小値の計算は以下のようになります。

burst[Bytes] = bitrate[bits/s] / 8 * timer_resolution[sec]

希望するbitrateが100Mbits/s、タイマ解像度が10msの場合次のようになります。

100Mbits/s / 8 * 10ms
= 100 * 10^6 / 8 * 10 * 10^-3
= 100 / 8 * 10 * 10^3
= 125kBytes

なおHTBにおいてburst, cburst値を明示しない場合、自動計算が行われるのですが、その値はrateが1000Mbits/sの場合に1600Bytesと言った極めて低く使い物にならない値です。これらの値はかならず明示的に指定するようにしてください。

dequeue機会の発生する頻度

前章でtimerの解像度がdequeue機会の発生する頻度と関係するという話をしましたが、残念ながらdequeue機会はtimerの解像度と完全に一致するわけではありません。HTBを使用している場合における、dequeue機会はこれだけあります。

プロトコル層からpacketをqdiscにenqueueすることに成功したとき
device driverからのパケット送信完了の報告（ハードウェア割り込み）が発生したとき
HTBが設定したtimerのcallbackが発生したとき（注: 頻度はtimerの最小間隔の10msなどであるとは限らない、もっとおおきな間隔のtimerが設定される場合もある）
その他いろいろ

timer解像度はburst値を設計する上で、重要な指針となりますが実際のdequeue機会はそれよりも短い間隔でも長い間隔でも発生するのです。

そのため、実運用でのburst値はかならず実際にbitrateを測定しながら調整を行う必要があります。私が調整を行った時は前章での理論値の4倍〜10倍程度で実測値が安定しました。

実運用での注意点

パケット送受信は多くのパラメータや機能が関わる極めて複雑な機構です。安定した運用を実現するためにはこのドキュメントに挙げた項目以外にも関係する設定やパラメータを洗い出し、適切な値を設定した上で、念入りに検証を行う必要があります。よく調整される値としては以下のようなものがあります。

/proc/sys/net/core
rmem_default, rmem_max, wmem_default, wmem_max
/proc/sys/net/ipv4
tcp_mem, tcp_rmem, tcp_wmem

また、場合によっては誤った設定でも一時的にパフォーマンスがでてしまうケースがあることにも注意が必要です。

例えばHTBにおいてburst値が低すぎる場合でも内部qdiscがPFIFOでlimitが1000などに設定されていると、その分だけはenqueueを続けられ、前章のdequeue機会の「プロトコル層からpacketをqdiscにenqueueすることに成功したとき」を得られるため、PFIFOのlimitに達するまではそれなりのbitrateが出てしまい、途中から失速するという不可解な挙動を生み出します。この挙動は内部qdiscを明示的に指定せず、txqueuelen(=PFIFO limit)がデフォルト値として1000などに設定されていた場合も発生し、より原因の特定を困難にします。
また同様に内部qdiscにSFQを使用した場合も、巨大なトラフィックを発生させているセッション以外のセッションでのパケット送信はenqueueが成功する仕組みになっているため、「プロトコル層からpacketをqdiscにenqueueすることに成功したとき」のdequeue機会を得られ、不安定ながらタイマ解像度による制約により出ないと考えられる高いbitrateとなることがあります。

用語集

device: Linuxでネットワークインターフェースとして認識されているものです、eth0といった名前になっていることが多いEthernetポートなど物理的な実態があるものも、lo(local loopback)のようにソフトウェア的に実装されているものもあります。
device driver: deviceのコア部分です。送信においてはqdiscを抜けたパケットを実際に送信したり、送信が完了した際にそれを通知する割り込みを発生させたりします。

その他

本ドキュメントではtcの設定にiproute2のtcコマンドを用いてますがtcng(Traffic Control Next Generation)というツールが存在し、より人間的な文法でtcの設定を行えるようです。
私は試していませんが、これからtcを導入する方はこちらの利用を検討してもいいかもしれません。

まとめ

このドキュメントではHTBを中心にPFIFO, PFIFO_FAST, SFQなど帯域制限・帯域保証の設定に関係することのあるtcのqdiscやその設定項目について説明しました。このドキュメントと別に記載したガイドラインをあわせることで安定したtc運用の一助となれば幸いです。

参考文献

https://github.com/torvalds/linux
もっとも参考になりとても正しいです。qdiscの実装はnet/schedあたりに置かれています。

Traffic Control HOWTO
比較的新しく読みやすいです。(2006年)

Linux Advanced Routing & Traffic Control HOWTO
古いが一部こちらにしか乗っていない情報も存在します。

Linux Advanced Routing & Traffic Control HOWTO
上記ドキュメントの日本語訳

Differentiated Service on Linux HOWTO