要約

  • 1988年のDECbit方式では、ルーターは平均キュー長が1パケット以上になってからビットを立てた。その平均は固定時間ではなく、キューの繁忙期と空き時間の周期に合わせて求められた。
  • 送信側は一つの印に即応せず、現在のウィンドウで半数以上が印付きならウィンドウを8分の7にし、そうでなければ一つだけ増やした。

「混んでいる」を1か0で伝えるのは簡単に見える。難しいのは、その1をいつ書き、いくつ戻ったときに負荷を下げるかである。K. K. RamakrishnanとRaj JainがSIGCOMM 1988で示した方式は、この二つを同じ瞬間の判断にしなかった。パケットのビット幅は最小でも、その前後には時間を使った評価があった。

キュー自身の周期を物差しにする

共著論文 “A Binary Feedback Scheme for Congestion Avoidance in Computer Networks with a Connectionless Network Layer” では、混雑を検出したルーターが宛先方向のパケットに印を付ける。後段のルーターが空いていても、すでに立ったビットは消さない。宛先はその情報をトランスポート層の確認に載せて返し、送信元が飛行中のパケット数を調整する。これはJain単独の発明としてではなく、Ramakrishnanとの共同研究として扱うべき成果である。

検出に使うのは一瞬のキュー長ではない。処理中のパケットも含めた平均キュー長が1以上なら印を付ける。平均区間は、直前の完全な繁忙期とアイドル期に、現在の繁忙期の経過部分を加えたものだった。キューが満ち、空になり、再び仕事を受ける流れが観測の長さを決める。

固定した時間幅なら実装は分かりやすいが、往復遅延の違う経路に同じ意味を持たせにくい。指数移動平均は、すでに終わったバーストの影響を残すことがある。独立した測定時計は、似た状態のルーターから異なる評価を生む可能性もある。再生周期に合わせる手法は、古すぎる記憶と短すぎる反応の間を取る試みだった。

1パケットという境界も、将来の全ネットワークに通用する絶対値ではない。論文の考え方では、それを上回る平均キューは、ボトルネックの処理量を増やさずに待ち時間だけを積み上げる。一方、低すぎる負荷なら使える容量が残る。利用率と遅延を両方見るための運用上の閾値であり、普遍的な最適値の証明ではない。

返ってきた印をまとめて読む

送信元にはもう一つの時間フィルターがある。前のウィンドウと現在のウィンドウの合計に相当する確認を待ち、現在のウィンドウに対応するビットを評価する。少なくとも半数が混雑を示せば、ウィンドウを現在値の87.5％、すなわち8分の7にする。半数未満なら一つ増やす。

この構成なら、孤立した一つの印が直ちに減速命令にはならない。加算的な増加は空き容量を少しずつ探り、限定した乗算的減少は過度な揺れを避けながら圧力を下げる。論文は0.875を実装の容易さと振動の抑制から選んだと説明する。別の箇所にある0.8の例は整数丸めが公平性を崩す場面を示すもので、採用された係数ではない。

評価では、複数利用者、ランダムなパケット長、異なる経路、衛星リンク、サービス時間の変化、新しい送信元の参加などがシミュレーションされた。著者らは、その範囲で効率、適応性、公平性を報告した。設計の比較材料として重要だが、現代のインターネット全体を測った結果でも、協力しない送信元を含むあらゆる環境の保証でもない。

方式を導入するだけでは協力は生まれない

A. MankinとK. Ramakrishnanが1991年にまとめた RFC 1254 は、ゲートウェイの混雑制御を概観し、DECbitの平均1パケットという閾値と、二つのウィンドウにまたがる8分の7の応答を紹介した。分類はInformationalであり、この方式をインターネット標準として命じた文書ではない。

同RFCは協力の難しさにも触れる。ルーターが印を付けても、実際に送信量を下げるのは端末である。印を無視する利用者は短期的に帯域を多く取り、待ち時間や損失を協力する利用者に押し付けられるかもしれない。すべてのホストとゲートウェイを一度に更新することもできない。共通資源の制御は、技術仕様だけでなく移行とインセンティブの問題になる。

Washington Universityの現行プロフィールはJainをDECbitの共同発明者とし、DECnet、OSI、Frame Relay、ATMで「さまざまな形」に実装されたと記す。この表現が示すのは広い影響であって、すべてが1988年の手順をそのまま再現したという証明ではない。同大学の2017年の受賞記事は、性能解析と混雑制御にわたる研究歴の中にこの成果を位置付けている。

情報源と限界

本稿は1988年の共著論文、Informational RFC、大学の公式ページに基づく。現在の導入数を数えたものではなく、現行方式との性能比較や、後世のあらゆる明示的通知との直接的系譜を主張しない。次の監視論は記録された制御構造からの編集上の推論である。AI編集肖像の本人確認にはWashington Universityの公開写真を用い、背景の研究室は創作した。