要約

  • Keshavのモデルでは、連続して送った二つのパケットを、経路上で最も遅いレート配分サーバーが最も大きく引き離す。ACKの間隔は、一つの会話に割り当てられたボトルネック・サービス率の雑音を含む推定値になった。
  • その推定値は、そのまま送信速度にはならない。キュー目標値、ファジィ指数平均、安定な制御則、意図的な送信停止による再校正が、遅延・雑音・ドリフトを別々に扱った。
  • パケットペアは一般のインターネット帯域を証明しない。方式は公平キューイングに近いスケジューラーを前提とし、FCFS網、無損失、アプリケーション到達やサービス品質を保証しなかった。

観測できない空のキュー

自分のフローがすでに待ち行列を作っていれば、連続するACKのテンポからサービスの進み方を推測できる。難しいのは、キューが空のときだ。隣り合う仕事がなければ、スケジューラーの拍子は表に出ない。

Keshavは2019年の回想で、1989年12月、Berkeleyの喫茶店でこの問題を考えていたと記している。答えは、観測のために最小の待ち行列を作ることだった。二つを背中合わせに送れば、第一のパケットがサービスを受ける間、第二のパケットがその後ろに立つ。複数のノードを通っても、対象フローへのサービスが最も遅い場所が二つを最大に離す。戻るACKがその間隔を保てば、ルーターに明示的な速度フィールドを追加せずに推定できる。

ただし、この回想は査読論文ではなく、そう明記された編集ノートである。研究史についての本人の証言として読めるが、性能の独立検証ではない。またKeshav自身が、Samar SinghとAshok Agrawalaもほぼ同時期に同じ発想へ独立に到達し、共同研究へまとめたと書いている。SIGCOMM論文の著者はKeshavだが、パケットペアを一人だけの発明として扱うことはできない。

二という数ではなく、スケジューラーが状態を読める形にした

論文が想定したのはRate Allocating Server、すなわちFair QueueingやVirtual Clockに近いラウンドロビン型の出力サービスである。アクティブな各会話は、比較的識別可能な間隔で自分のパケットを処理される。他の会話の順番を含む一巡の時間が、その会話から見たサービス時間になる。

連続パケットは、送信側が作る間隔をほぼゼロにする。経路上で最も長い一巡時間が二つを引き離し、その後のより速いサーバーは、モデル上その差を閉じない。観測可能性を作ったのは探針の神秘ではなく、キュー規律の意味だった。

だから論文は通常のFCFS網へこの議論を拡張しなかった。先着順では、別フローの一時的なバーストが対象フローの見かけのサービスを急変させる。同じ二つのパケットでも、安定した一会話分の割当てを読むことはできない。観測器は、システムが外に残す構造以上のものを取り出せない。

ACK間隔は眺めではなく、汚れた領収書だった

送信側が受け取るのはボトルネックそのものではない。二つのACKが復路で異なる待ち時間を受ければ、間隔は伸びも縮みもする。正方向でも、ボトルネックより後のノードが二つへ異なる遅延を加えられる。受信側で測って値を返せば復路雑音の一部は減るが、下流の影響までは消えない。

そこで論文は、観測されたサービス率に雑音があるとした。真の割当て率も、アクティブな会話の参加・離脱で変わる。最後の測定値は過去の値であり、次の区間にそのまま適用できる保証はない。

Kalman推定器は形式的には魅力的だったが、システム雑音と観測雑音の分散を外から与えなければならない。Keshavは実用上の弱点とみなし、ファジィ規則で指数平均の重みを変えた。安定して見えるときは履歴を重くし、変化が強いときは直近値を重くする。「ファジィ」は根拠を捨てる言葉ではなく、忘却速度をどう切り替えるかという公開された方針だった。

安定性証明はモデルの外へ持ち出せない

制御器は最後の推定サービス率を送信率としてコピーしたのではない。未確認パケット数、RTT、推定サービス率、推定ボトルネック・キュー長を合わせ、目標となるキュー位置を選んだ。

論文中の B/2 は説明のための選択である。キューが空に近いと、サービスの番が来ても送る物がなく帯域を失う。満杯に近いと、遅延と損失の危険が増す。対称な雑音分布を仮定して中間を置いたのであり、別の目標値も選べると明記されている。

最初の制御則は極が単位円上にあり、漸近安定ではなかった。極配置パラメーターを導入すると、論文の線形モデルでは極を内側へ動かせた。連続時間版では、RTTごとだけでなく、探針が戻るたびに動作できた。証明は重要だが、線形性、流体近似、RASの可観測性、雑音仮定を受け継ぐ。同じ名称の全実装に配られる証明書ではない。

送信を止めて、推定値を現実へつなぎ直す

推定値から次の推定値を作り続けると、誤差が蓄積し得る。内部で一貫した数字が、実キューから離れていくこともある。

論文の再同期は、効率を一時的に捨てる手順だった。特別なペアを送り、そのACKが戻るまで後続を止める。後ろから新しいパケットが来なければ、対象会話のボトルネック・キューは空になる。そこで推定キュー長をゼロへ戻す。費用はおよそ一RTT分の未使用帯域である。

これは推定の出自を回復する行為だった。不確実な数字をさらに平滑化する代わりに、ゼロだと検証できる条件を作る。停止は失敗ではなく、校正のための制御だった。

レート制御だけでは無損失も保証しない。論文は、運転点を選ぶレート制御とは別に、未確認量を制限するウィンドウを保守的な上限として置いた。後者は会話ごとのバッファー前提を伴う。一方の約束を、もう一方の成果として数えることはできない。

二つのパケットが証明しなかったもの

1991年論文はシミュレーションを定性的に要約したが、詳細は博士論文などに委ね、実ネットワーク測定を今後の作業とした。線形モデルはウィンドウとの相互作用を十分に表せず、Gaussian white noiseや単一会話の視点にも制約がある。

後世のpacket-dispersion研究がリンク容量やavailable bandwidthを扱ったとしても、その意味を過去へ逆輸入してはならない。ここで推定したのはRAS条件下で一会話に割り当てられたサービス率であり、物理回線速度、空き容量、エンドツーエンド・スループット、損失回避、アプリケーション到達ではない。

Cambridgeの公式略歴は、KeshavのBerkeley、Bell Labs、Cornell、WaterlooからCambridgeへ至る経歴を記す。本人のサイトは、Keshavが語順上は最後に置かれるgiven nameだとも説明する。この研究の現在的な価値は、観測値と成立条件を切り離さなかった点にある。間隔だけではなく、スケジューラー、経路、時刻、雑音が一緒に残って初めて、その数字は制御へ入れる。

出典