# Valiant Load Balancing ## 定義 Valiant Load Balancing(VLB)は、通信経路を宛先に依存せずランダムな中間ノード経由で分散することで、任意のトラフィック行列に対してホットスポットのないパケット交換ネットワークを実現するルーティング手法である。1982 年に Leslie Valiant が並列プロセッサ向けの超立方体トポロジで提案した。 VLB の本質的な性質は「任意のトラフィック行列をランダム化によって平均ケースに変換する」点にある。最良ケースのトラフィックパターンを犠牲にしつつ、最悪ケースを含むすべてのケースを同一の平均ケースとして扱うことで、複雑な適応型トラフィックエンジニアリングなしに帯域保証を提供する。 ### 理論的保証 VLB の基礎定理(ホースモデルを前提): - 各送信元から出るトラフィックと各宛先に入るトラフィックがそれぞれリンク容量以内に収まる(ホースモデル)場合、中間ノードへの等割合での分散によりネットワーク全体でホットスポットが発生しない。 - 数学的には「非干渉パケット交換ネットワーク」の実現に相当し、回路交換の「非閉塞ネットワーク」に対応する。 ### VL2 でのデータセンターへの適用 [[VL2]]([[@2009__SIGCOMM__VL2 - A Scalable and Flexible Data Center Network]])は VLB を初めてデータセンターのスイッチファブリックに適用した。 実装方法: 1. すべての Intermediate スイッチ(スパイン)に**同一エニーキャストアドレス**を付与。 2. 送信元サーバの VL2 エージェントがパケットをエニーキャスト LA でカプセル化 → ECMP が複数パスのうちいずれかの Intermediate スイッチへ届ける(VLB の「ランダム中間ノード選択」をエニーキャスト + ECMP で実現)。 3. Intermediate スイッチがデカプセルして宛先 ToR の LA へ再カプセル、最終的に ToR がデカプセルしてサーバへ届ける。 この設計により: - **フロー単位分散**(パケット単位ではない)で順序逆転なし - スイッチ障害時はエニーキャストアドレスの ECMP が自動的に生きているスイッチへ迂回。VL2 エージェントへの通知不要 - 5 タプルハッシュ値を外部 IP ソースアドレスに書き込むことで、一部安価スイッチの ECMP ハッシュ精度不足を補完 ## 横断的知見 - **VLB とアダプティブルーティングの性能差は実際のデータセンタートラフィックでは小さい**: VL2 の実測では、最重リンクの利用率が VLB は適応型ルーティング比で約 5% 高いに過ぎない。中央値リンクでは同等。トラフィックパターンの高ボラティリティ(50〜60 クラスタで誤差が大きく予測不能)がランダム化の有効性を高めている。(Source: [[@2009__SIGCOMM__VL2 - A Scalable and Flexible Data Center Network]]) - **フロー単位 VLB の有効性はリンク速度ギャップに依存する**: VL2 では Intermediate スイッチ間リンクがサーバリンクの 10 倍(1G 対 10G)速い。このギャップにより、フロー単位分散でも少数の象フローが偏在した場合の輻輳リスクが統計的に低下する。コアリンクがサーバリンクと同速になると、フロー単位 VLB だけでは不十分となり、フローレット分散(flowlet switching)などの補完が必要になる可能性がある。(Source: [[@2009__SIGCOMM__VL2 - A Scalable and Flexible Data Center Network]]) - **VLB は AI/GPU クラスタの集団通信(All-Reduce)には非自明**: VLB はランダム中間経由であらゆる TM を平均ケースに変換するが、AI 学習の All-Reduce は特定のリングまたはツリーパターンに沿った通信が多く、ランダム分散によってむしろバレット(障害)通信のオーバーヘッドが増す場合がある。マルチプレーン Clos などより近年のアーキテクチャとの比較・評価は未検討。(Source: [[@2009__SIGCOMM__VL2 - A Scalable and Flexible Data Center Network]]) ## 未解決の問い - **フローレット分散(flowlet switching)との組み合わせ**: VL2 はフロー単位 VLB で象フロー偏在リスクを許容するが、フローレットスイッチングと組み合わせると偏在はどの程度解消されるか。実データセンタートラフィックでの評価はあるか。 - **AI/ML ワークロードへの VLB 適用**: 現代の GPU クラスタでは集団通信が支配的。All-Reduce のツリー/リングパターンはホースモデルに適合するか、VLB はこれらに対しても最適か。 - **ECMP ハッシュ衝突と象フロー問題**: ECMP のフローハッシュ衝突で複数の大フローが同一リンクに集中した場合の影響と、再ハッシュ(elephant flow rerouting)の有効性は実際どの程度か。 - **VLB とロッシー(パケット損失あり)動作の相性**: PFC を使わないロッシーファブリック(Ultra Ethernet Consortium 推進)で VLB を使うと、ランダム中間経由で経路長が増えた分だけ損失確率が上がる。設計上の許容範囲は? ## 関連 - 応用システム: [[VL2]] / [[@2009__SIGCOMM__VL2 - A Scalable and Flexible Data Center Network]] - 関連概念: [[マルチプレーンClosトポロジ]] / [[データセンター輻輳制御]] / [[負荷分散]] - エンティティ: [[Albert Greenberg]] / [[Microsoft Research]] ## 出典 - [[@2009__SIGCOMM__VL2 - A Scalable and Flexible Data Center Network]] — データセンタースイッチファブリックへの初の VLB 適用と実証評価