要約

  • 通常のパケット・ラウンドロビンが均等にするのは送信機会であって、送信バイトではない。ShreedharとVargheseのDRRは各キューに量子を加え、先頭パケットを丸ごと払える間だけ送信し、バックログが残るキューの未使用残高を次の巡回へ繰り越す。
  • DRRの狙いは、低い逐次処理コストで長期スループットの偏差を有界にすることだった。公平性の対象は設定されたキューと重みであり、基本DRRだけでは遅延上限、利用者分類、シェーピング、AQM、輻輳制御、エンドツーエンドQoSは得られない。

三つの時計で同じ瞬間を測る

まず、同じリンクを三つの時計で見る。第一の時計はパケットを数える。二つのキューが一個ずつ送れば、針は同じだけ進む。第二の時計はバイトを数える。パケット長が違えば、針の進みは異なる。第三の時計はリンク占有時間を測る。伝送速度が一定なら、それはバイトの差をほぼそのまま映す。

単純なround robinが公平に見えるのは、第一の時計だけを採用するからだ。ところが、共有される希少資源はパケット番号ではなく、リンク上の送信能力である。小さいパケットを送るキューと大きいパケットを送るキューに同数の手番を与えると、操作は対称でも結果は非対称になる。これは例外的なワークロードではなく、可変長パケットを扱う限り構造的に起こる。

理想的な公平キューイングは、各フローが流体のように同時サービスを受けるモデルを考え、パケットの終了時刻に相当する順序を計算できる。しかし高速なデータパスでは、精密な順序付けに必要な計算や並べ替えが実装コストになる。DRRは瞬間ごとの完全な模倣を捨て、誤差の上限と安価な処理を選んだ。その選択を成立させるのが、キューごとの赤字カウンタである。

一巡しても消えない余り

活動中のキューに調停器が到達すると、そのキューのdeficit counterへ設定済みのquantumを足す。先頭パケットの長さが残高以下なら、パケットを分割せず送信し、そのバイト数を差し引く。残高で次の先頭パケットも払えるなら続ける。払えなければ次のキューへ移る。

ここで余りをゼロにしないことが決定的である。キューがまだバックログを持つ限り、足りなかった残高は次の巡回へ残る。単独の量子より大きいパケットでも、何巡かの加算後には丸ごと送れる。反対にキューが空になれば残高をリセットする。新しく到着した仕事が、以前の待機によって得たわけではないクレジットを相続しないためだ。

「赤字」という名称は、債務や罰金を連想させるが、ここでの数字は利用者がネットワークに負う借金ではない。混雑の価格でもSLA違反額でもない。不可分なパケットのため、その訪問では使えなかったサービス資格を表す局所状態である。連続量として割り当てたいバイトと、丸ごとしか送れないパケットの間をつなぐ会計だ。

同じ量子を持つ二つのキューが常に混んでいるとする。小パケット側は一回の訪問で複数個を送り、大パケット側はある訪問では一個も送れないかもしれない。それでも大パケット側の残高は蓄積される。短い時間窓のパケット数は不揃いでも、長い時間窓の送信バイトは目標比率へ近づき、ずれは最大パケット長に関係する範囲に抑えられる。DRRが均すのは瞬間ではなく、履歴を含むサービス量である。

量子に書き込まれた重み

すべてのキューが同じquantumを持てば、等しいバイト配分が基準になる。量子が二対一なら、両方が継続してバックログを持つ状況で、長期サービスもおおむね二対一へ向かう。したがって、量子は単なるチューニング値ではない。誰にどれだけ容量を配るかという方針を、調停器が実行できる整数にしたものだ。

値には実装上の帰結もある。最大パケットに比べて量子が小さければ、大きなパケットは複数巡回を待ち、活動リストへの訪問も増える。大きな量子は一回に多くのバイトを解放し、サービスのバーストを大きくし得る。「DRRを使っている」という記録だけでは再現性がない。キューごとの量子、想定最大パケット、空キュー時のリセット規則、活動リストの扱いまで残して初めて、当時の公平性を検証できる。

ShreedharとVargheseが1994年のテクニカルレポートと後のSIGCOMM論文で示した焦点は明快だった。ほぼ理想的なスループット公平性を、O(1)の低い処理とハードウェアに載せやすい構造で得る。O(1)という表現は、あらゆるネットワーク問題が定数になるという意味ではない。スケジューリングの各操作が、フロー数に応じた高価な並べ替えを要求しないというデータパス上の性質である。

キューの境界はアルゴリズムの外から来る

DRRは、目の前に置かれたキューの正体を調べない。十の顧客が一つの共有キューへ分類され、一人の顧客が別の専用キューを持てば、等量子のDRRが公平に扱うのは二つのキューである。十一人の顧客ではない。巨大フローと短い対話フローが同じキューに入れば、キュー内の先頭順序による待ちも残る。

だから、公平性の説明はスケジューラ名で終われない。分類キーは何か。キューは利用者、フロー、トンネル、アプリケーション、優先度のどれを表すのか。未分類のトラフィックはどこへ入るのか。障害切替や設定変更でカウンタはどう扱われるのか。これらはDRRの数式が決める事項ではなく、運用者が公平の母集団を決める統治面である。

監査も同じ境界をまたがなければならない。インターフェース総量だけでは各キューの配分は分からない。パケット数だけなら、最初の単位誤りを繰り返す。分類器の版、キュー構成、量子、活動期間、パケット長、送信バイト、繰越残高を結び付けた記録が必要になる。誰を一つにまとめ、誰を独立させたかが見えなければ、正確なカウンタも曖昧な政策を忠実に実行するだけだ。

帯域が公平でも、待ち時間は公平とは限らない

基本DRRの長期スループット保証から、個々のパケットの遅延上限を導くことはできない。あるキューは他の活動キューの訪問を待ち、その中でも先に並んだパケットを待つ。活動キュー数、量子、最大パケット長、到着の偏りが待ち時間を変える。原論文も基本方式のスループット公平性と遅延境界を区別し、遅延制約へ向けた拡張を論じている。

DRRは到着率を整形せず、送信元の輻輳窓を変えず、捨てるパケットやECNマークの時機も単独では決めない。シェーパは流入の時間構造を、AQMはキューの信号と廃棄を、輻輳制御はエンドホストの送信行動を担う。RFC 7567がAQMの文脈でスケジューリングを別の機能として扱うのも、この混同を避けるためである。

この区別は、性能説明の誇張を防ぐ。「重みどおりのバイトが送られた」はDRRに関する証拠になり得るが、「99パーセンタイル遅延を満たした」には別の測定と仕組みが要る。分類ミスを量子変更で治すことも、総需要がリンク容量を超える状態を公平な配分だけで消すこともできない。

George Vargheseが残したデータパスの考え方

UCLAの公式プロフィールは、George VargheseをコンピュータサイエンスのDistinguished ProfessorおよびJonathan B. Postel Chairとし、network algorithmics、検証、サイバーセキュリティ、未来のインターネットを研究分野として挙げる。MITで博士号を取得し、Washington University in St. LouisとUC San Diegoで教員を務め、Microsoft Researchを経て2016年にUCLAへ移った。

ACM SIGCOMMは2014年にSIGCOMM Awardを授与し、Internet Hall of Fameは2021年の殿堂入り紹介で、M. Shreedharと共にDRRを発明したことや、Cisco GSRなどで歴史的に使われたことを記している。受賞歴は技術命題の証明ではないが、アイデアが論文内のモデルから実装可能なネットワーク機構へ移った影響を示す。

DRRにはVargheseの研究で繰り返される姿勢が見える。高速経路のボトルネックを抽象的に嘆くのではなく、状態の持ち方を変えて高価な操作を避ける。精密さを捨てるのではなく、何の誤差をどこまで許すかを明示する。小さなカウンタは、その設計判断を一パケットごとに実行する装置だった。

カウンタを読むには来歴が要る

運用中に比率が崩れたとき、原因は一つではない。量子が変わったのか、パケット長分布が変わったのか、キューの母集団が変わったのか、あるいは一方がバックログを失って未使用容量を他方が使ったのか。短いスナップショットでは区別できない。複数巡回を覆う履歴と、設定変更の時刻を重ねる必要がある。

逆に、バイト比率が設定値へ近いからといって、利用者が同じ経験を得たとも限らない。共有キュー内で一部のフローが待ち、別のAQMで損失が偏り、経路の別区間で遅延が生じることがある。DRRの証拠は強いが局所的だ。その局所性を守ることが、アルゴリズムの価値を小さくするのではなく、誤った主張から守る。

出典