この節は、バンド幅が 100メガビット以上になるような、 バックボーンの経路に関する解説を意図して書かれました。 自宅の ADSL モデムなどとは異なるアプローチが必要になります。
インターネットにおけるルータのキューの通常の動作は、 tail-drop と呼ばれます。 tail-drop は、ある量まではキューを行い、 「溢れた」トラフィックをすべて破棄します。これは非常に不公平であり、 再送の衝突 (retransmit synchronization) の原因にもなります。 再送の衝突が起こると、限界に達したルータで突然の破棄がバースト的に生じ、 それがまたしばらく後に再送のバーストを生じさせ、 混雑したルータはまた限界に達することになります。
接続における一時的な混雑に対処するため、 バックボーンルータでは大きなキューが用意されていることが多いです。 しかし残念ながら、このようなキューはスループットには良いのですが、 遅延 (latency) が大きくなりますし、 TCP 接続では混雑時のバーストが非常に大きくなってしまいます。
この tail-drop の特性は、 インターネットにおいてだんだん厄介な問題になってきています。 ネットワークに優しくないアプリケーションの利用が増加してきたからです。 このため Linux カーネルでは RED が提供されています (RED は Random Early Detection の略。またその動作から、 Random Early Drop とも呼ばれます)。
RED はこの問題についての万能薬ではありません。 指数的な backoff を正しく実装していないアプリケーションは、 いずれにしても不公平にバンド幅を獲得してしまうことになります。 しかし RED を用いれば、スループットや遅延に関して、 他の接続に大きな害を与えることはなくなります。
RED は、ハードリミットに達する前に、フローからパケットを統計的に破棄します。 こうすると混雑したバックボーンの接続を、より穏やかに減速でき、 再送の衝突を防ぐことができます。 これはキューのサイズを小さく、遅延を一定に保ちつつ、 早めにパケットを破棄するので、TCP が自分の「公正な」速度を より早く発見するのにも役立ちます。 ある特定の接続においてパケットが破棄される確率は、 送ったパケットの数にではなく、バンド幅の利用率に比例します。
公平なキューイングで必要とされる、 複雑なセッションごとの状態追跡が無理であるようなバックボーンに対し、 RED は適したキューです。
RED を使うには、3 つのパラメータ min, max, burst を決める必要があります。 min は破棄を始める際のキューサイズ (の最小値)、 max はこのアルゴリズムで留めておきたいソフトリミット (最大値)、 burst は「バースト通過」が可能な最大パケット数です。
min を計算するには、基本キューイング遅延 (base queueing latency) の最大許容値にバンド幅をかけます。例えば 64kbit/s の ISDN 接続に対し、 基本キューイング遅延を 200ms まで認める場合、min は 1600 バイトとなります。 min を小さくしすぎるとスループットは悪化しますし、 大きくしすぎると latency が劣化します。なお min を小さくしても、 遅い接続で対話的セッションの反応を良くするために MTU を小さくするのと同じ効果は得られません。
衝突を防ぐには、max は少なくとも min の 2 倍にしなければなりません。 遅い接続で min も小さいときは、おそらく max は min の 4 倍以上にするほうが良いでしょう。
burst は RED アルゴリズムのバーストに対する反応を決めます。 burst は min/avpkt より大きくしなければなりません。 私が実験したところでは、(min+min+max)/(3*avpkt) でうまく動作するようです。
また、limit と avpkt の設定も必要です。 limit は安全弁となる値で、キューの中身が limit バイトを越えると、 RED は tail-drop に「変化」します。私は大体の場合、limit を max の 8 倍に設定します。avpkt はパケットサイズの平均値です。 MTU が 1500 バイトの高速なインターネット接続では、 1000 にしておけばよいでしょう。
技術的な情報は、 Sally Floyd と Van Jacobson による RED キューイングの論文をご覧ください。