ルータとqueue

2008/10/2-1

インターネットでは、ルータ(router)と呼ばれるネットワーク機器がパケットをバケツリレーのように宛先に届ける事で通信が行われます。例えば、家にあるSOHOルータもルータです。各ルータは、受け取ったパケットをどの接続インターフェースに転送するかだけを考えてパケットを次のルータ(ノード、ホスト)へと手渡します。

ルータは、パケットを受け取ってから次のルータに渡すまでqueue(キュー、待ち行列)に保持します。例えば、回線容量(帯域)以上の転送要求を受け取った時には、queueにパケットが徐々に溜まっていきます。そして、パケットによる混雑が「これ以上無理！」というレベルに到達するとパケットが破棄されてしまいます。このような混雑している状況は輻輳(ふくそう)と呼ばれます。

輻輳状況をルータでどのような処理をするかという課題に対して、queue制御を行うという手法があります。ここでは、queueの制御方法をいくつか紹介したいと思います。

FIFO(First In First Out) queue

いわゆる普通のqueueです。全ての基本です。

最初に入ったものが最初に出て行きます。一般的に、FIFO queueには決まった長さがあり、パケットがその長さに入りきらないと破棄されます。そのため、パケットが破棄されるかされないかは、パケットが到着した瞬間のFIFO queueのつまり具合に左右されます。

Tail Drop

一番尻尾が破棄されるモデルです。混雑しているFIFO queueに後ろから入ろうとして失敗してパケットが消えてしまうというイメージでしょうか。

Random Drop on Full

queueが埋まった時点でqueueの中に入っているパケットがランダムに選ばれて破棄されるモデルです。

FQ (Fair Queueing)

かなり古い方式です。名前の通り、Fair(公平)にするためのqueueing方式です。

具体的には、フロー(それぞれの通信)毎にqueueを作ってしまうという方式です。それぞれのフロー毎にqueueを作って、実際に出力されるパケットは各queueから順番に出て行くround robin方式になります。このようにフロー毎にqueueを作れば、パケットを多く出して帯域を消費しているqueueは勝手に詰まっていき、パケットを多く出していないフローのqueueはスカスカになります。

Fairにすることを考えた時、これほどFairに出来る方式はないのではないかというぐらい各フローが「平等」に帯域を分け合います。

FQの問題点は、あまりにトラフィックが多過ぎるルータでは利用しにくいことです。あまりにフローの数が多くなりすぎると、大量にqueueを作成しなくてはならなくなり、スケールしなくなります。

FQそのものでは、フローとは何かは明言されていないので、状況に応じて何をフローとするかは規定できます。例えば、特定のホストとホストの通信をまとめてフローとするのか、特定のポート番号でのTCPによる通信をフローとするのかは条件設定次第です。

RED (Random Early Detection)

FQよりは新しい方式ですが、かなり古い方式です。実際にはあまり使われていませんが、考え方に美しさがあります。

REDでは、queueに含まれるパケットをランダムに選んで破棄します。こうやって書くと何だか理不尽で意味不明に聞こえるかも知れませんが、この「ランダムに捨てる」というところにこそ、REDのアルゴリズムとしての美しさはあります。

REDがランダムにパケットを破棄するのは、TCPを前提としているためです。 TCPは、パケットロス(パケット喪失)を輻輳の兆候として捉えます。 TCPでは、輻輳を検知すると利用する帯域を削減します。具体的には、出すパケットの量を減らして混雑を緩和させようとします。混雑しているところに、さらに多くの混雑の原因を突っ込むと、結局はパケットが落ちるばっかりになってしまって、通信効率が著しく低下するためです。インターネットが設計された当初は、TCPにこのような輻輳回避機構はありませんでしたが、にっちもさっちも行かなくなってしまったために、TCPに協調してネットワーク帯域を譲り合う機構が含まれるようになりました。

REDでは、この「TCPが混雑回避しようとする」仕組みを利用しています。 queueがあまり埋まっておらず、スカスカの間はパケットは破棄されません。 queueの量がある一定量(threshold:閾値)を定常的に超えるようになると、REDが作動しはじめます。 queueに溜まっているパケットの量が多くなればなるほど、ランダムに落とされるパケットの割合は増加して行き、最終的にはFIFO queueのdrop tailと同じように全ての入力パケットが破棄されるようになります。

REDが何故ランダムにパケットを破棄するかですが、これは、ランダムにやっていれば帯域を多く利用している通信によるパケットが破棄されやすくなるからです。そこを流れるパケットの量が多ければ、自ずと落とされるパケット数も多くなるだろうという考え方です。

REDの思想はTCPが前提ではありますが、TCP以外に対して全く意味がないというわけではありません。 TCP以外であってもパケットロスを検知して利用帯域を調整してくれる通信方式であれば影響を受けて利用帯域を調整してくれます。また、言う事を聞かない悪い子のためのペナルティボックスというものが必要か漏れないという話も一応論文中には書いてあります。

REDは、アルゴリズム的には非常に美しいのですが、あまり運用されているのを見たことがありません。可能な限りパケットは落としたくないのが人情です。また、トラフィックが非常に大量にあるルータでは1つの通信でパケットを破棄して消費帯域を削減させたとしても、その削減量は全体から見るとスズメの涙にしか見えません。例えば、100万本の通信があるところで、1本のTCPだけが利用帯域を自重したとしても、全体に与える影響は皆無です。

一方で、論文では良く見る方式です。現状では美しいけど実運用には向かない方式と言えるかも知れません。

なお、REDはECN(Explicit Congestion Notification)とセットになる場合もありますが、まあ、それは細かい話なので割愛します。

CBQ (Class Based Queueing)

これもなかなか歴史がある方式です。

CBQの特徴としては、その名の通り、クラスという概念でリンクの帯域を割り振ることです。クラスは、それぞれ設定された帯域のシェアを満たすようにqueueからパケットを転送していきます。ただし、ネットワークが利用されていない時には設定以上のネットワーク帯域を占有できるようにもなっています。

[論文3 Figure 2]より

さらに、各クラス内に階層を作ることも出来ます。クラス内の下位クラスは上位クラスが利用可能な帯域の範囲内で好きなフローに対して帯域を割り振る事ができます。

[論文3 Figure 3]より

最後に

ここで紹介しているもの以外にも色々あるので、興味がある方は深く調べてみて下さい。結構面白いです。

参考文献

[1] : "On packet switches with infinite storage", John Nagle, IEEE Transactions on Communications, 35(4):435-438, April 1987.

[2] : "Random Early Detection Gateways for Congestion Avoidance", Sally Floyd and Van Jacobson, IEEE/ACM Transaction on Networking, Vol.1. No.4, August 1993

[3] : "Link-sharing and Resource Management Models for Packet Networks", Sally Floyd and Van Jacobson, IEEE/ACM Transactions on Networking, Vol. 3 No. 4, pp. 365-386, August 1995