要約

  • 比例公平性は同じ速度を配ることではない。選ばれた速度ベクトルと、実行可能なあらゆる代替案を比べ、各フローの相対変化の合計が正にならないことを求める。単一フローの観測だけでは判定できない。
  • Kellyの1997年のモデルは利用者の効用とネットワークの容量配分を分解した。1998年にはFrank Kelly、Aman Maulloo、David Tanが、重み付き対数目的をprimal型とdual型の分散速度制御へ結び付けた。
  • シャドープライスは必ずしも請求額ではなく、Lyapunov関数は指定されたモデルの安定性証拠である。フローの識別、重み、経路、遅延、雑音が変われば、証明できる範囲も変わる。

一つの速度には比較対象が入っていない

二つの転送が同じボトルネックを通るとする。一方が六、他方が四の速度を得た。各フローは自分の値を測れるが、全リンクの容量を守る別の割り当てがどれだけ存在するかは見えない。自分が速いという事実も、二者が同じ速度だという事実も、それだけでは公平性の証明にならない。

比例公平性の判定は、選ばれた実行可能なベクトルから始まる。別の実行可能なベクトルを一つ取り、各フローについて差分を現在の速度で割る。その相対変化を全フローで合計し、どの代替案でも正にならなければ、元の配分を比例公平と呼ぶ。

「比例」は配られる容量の見た目ではなく、比較する変化を指す。単一ボトルネック、同一重みという単純な条件では等分に見えることがある。しかし複数の資源をまたぐ経路や異なる重みが入れば、同じ速度になるとは限らない。

したがって証拠は速度一個ではなく、全ベクトル、経路と資源の対応、容量、そして何を一フローと数えたかで構成される。同一主体が接続を十本に分け、別の主体が一つに集約されれば、アルゴリズムが動く前に公平性の対象が変わっている。

1997年の分解は利用者の内心を集めなかった

Charging and rate control for elastic traffic では、調整可能な速度から利用者が得る価値を、増加しつつ厳密に凹な効用関数で表す。経路は有限のリンク容量を消費する。システム全体は容量を超えない範囲で効用の合計を最大化する。

Kellyの工夫は、全問題を一台の計算機に集めないことだった。利用者は提示された価格に対して局所的に選び、ネットワークは容量制約に沿って配分する。Lagrange乗数が両者を媒介する。あるリンクの乗数は、追加の一単位を通す暗黙の費用、または容量を一単位増やすシャドープライスと読める。

論文は、利用者が単位時間当たりの支出を選び、ネットワークが支出一単位当たりの速度を比例公平にする構成も扱う。利用者の選択とネットワークの配分が均衡すると、システム最適が得られる。

しかしシャドープライスは、まず制約付き最適化の変数である。現実の請求書に同じ数字が載るとは限らない。均衡も、実在の利用者が安定した効用関数を公開することや、その料金制度に同意したことを証明しない。分解が秘密の効用を中央へ渡さずに済む代わりに、重みと価格の意味は別途明示しなければならない。

一つの目的に二種類の局所ループを付けた

1998年の論文はKelly、Aman Maulloo、David Tanの共著である。容量制約の下で、速度の対数を重み付きで足した値を最大化する。対数の微分によって絶対量ではなく相対変化が現れ、資源の制約は経路ごとのシャドープライスへ分解される。

中央で直接解けば、計算機は全体状態を知る必要があり、その通信自体が遅延と障害にさらされる。そこで著者らは二つの分散方式を調べた。

primal型では資源が負荷に応じて輻輳指示を出し、送信元が増加と減少を行う。雑音をならす主な場所は端点である。加算的増加・乗算的減少との関係は読み取れるが、実運用中のすべてのTCPがこの連続時間モデルそのものだという意味ではない。

dual型では資源が超過需要に応じてシャドープライスを更新し、経路の速度は通過資源の価格合計へ応答する。経済学なら価格調整、制御工学なら明示的なフィードバックループと呼ぶ。同じ全体目的を、異なる場所で情報処理する構成である。

監査記録も分ける必要がある。primal型なら、どの資源がどの指示を出し、端点がいつ速度を変えたか。dual型なら、負荷推定、各資源の価格、経路での集計、提示速度を残す。最終スループットだけでは、約束された仕組みが働いたかを判別できない。

安定性の証明は境界を消さなかった

規則性の仮定の下で、三人は微分方程式系のLyapunov関数を構成した。その関数を最大化する点が安定点となり、軌道はそこへ収束する。局所更新が全体の最適化に結び付くことを、単なる期待ではなく数学的な証人で示した。

同じ論文は初期モデルの不足も明記する。確率的な揺らぎと時間遅れを最初の系から外し、その後に安定点近傍で分析する。ゲインを大きくすれば収束が速くなる一方、均衡付近のばらつきが増え得る。遅れがあると応答を急にするほど安定性を損なう場合がある。価格関数が単調でなければ、内部最大点が消えたり複数の停留点が現れたりする。

Kellyの後年のレビューでは、遅延不安定性と確率的不安定性が別の制約を持つことが強調される。個々のフローが知るのは自分の輻輳経験と戻り時間だけで、競合数や経路上の資源数さえ直接は分からない。

Lyapunov関数は特定の動力学に対する証拠であり、あらゆる実装の保証書ではない。異なるRTT、短い転送、経路変更、実キュー、測定誤差、戦略的な送信元を自動的に覆わない。最終的に収束しても、その前に終わるアプリケーションには遅過ぎることがある。

公平性の単位は数式の外で決まった

式は主体を定めた後の速度を比較できる。主体が接続なのか、利用者なのか、アプリケーションなのか、企業なのかは決めない。この粒度は配分権力そのものである。複数接続を安価に作れる側と、一つのトンネルに束ねられた側では、同じ式でも結果が違う。

重みも自然に生える値ではない。支出、協調的な資源持分、優先度などを表せる。既定の重みに対して比例公平でも、重みの決め方が不透明なら制度全体が公平とは限らない。

そこで証明には、数学上のフローと現実の主体を結ぶ台帳が要る。誰が識別子を作れるか、いつ集約するか、重みを誰が付けるか、他者が検証できるか、どの時点の経路と容量を固定したかを示す。運用状態が変われば、古い実行可能集合の証明も現在の事実ではなくなる。

これは比例公平性の弱点というより、正しい権限境界である。明示された前提の下でベクトルを判定できるが、正当な代表者や権利を式自身が選ぶわけではない。

Kellyは全体目的を動作中の反応へ接続した

Royal SocietyはFrank Kellyの研究を、確率過程、ネットワーク、最適化、大規模系の自己調整に位置付ける。彼の仕事の強みは、効用と希少性、制約と乗数、フィードバックと安定性という三つの言語を同じ検証可能な枠に置いたことにある。

著者性は狭めてはならない。1998年論文はKelly、Maulloo、Tanの仕事であり、先行する輻輳制御も、その後のネットワーク効用最大化も、多くの研究者から成る。人物記事は共同成果を個人所有へ変換する免許ではない。

Heng LuのMinimum Initial Specificationは、現在から当てる分析レンズであって、当時の意図を示す史料ではない。相互運用には、フロー識別、容量、信号、互換性の最小限で決定的な意味が必要になる。一方で、すべての効用や将来の制御方式を中央へ固定する必要はない。変更は実装、運用、検証、自発的採用によって事実になる。

Kellyの遺産は「公平」という印章ではない。局所信号から全体性質へ至る道筋と、その道筋を検証するための領収書である。誰を数え、どの代替案が可能で、重みと制約が何で、どの信号が速度を動かし、収束前に何が起きたのか。それを示せないシステムは、比例公平を主張しても実験を公開していない。

出典