# VL2: A Scalable and Flexible Data Center Network Navigation: [[Albert Greenberg]] | [[James Hamilton]] | [[VL2]] | [[Valiant Load Balancing]] > [!abstract] > クラウドサービスのデータセンターにおいてアジリティ(任意のサーバを任意のサービスに動的割り当て)とコスト効率を両立するため、VL2 ネットワークアーキテクチャを提案する。VL2 は (1) フラットアドレッシングによる柔軟なサーバ配置、(2) Valiant Load Balancing(VLB)によるトラフィックの均一分散、(3) エンドシステムによるアドレス解決 の 3 要素を組み合わせ、均一高帯域・サービス間分離・レイヤ 2 セマンティクスを実現する。Clos トポロジと実績あるネットワーク技術(OSPF・ECMP・IP エニーキャスト)を基盤とし、スイッチのハードウェア変更なしに今日から導入可能。75 台サーバのプロトタイプで 2.1TB シャッフルを 94% 効率・公平性指数 0.99 超で実証した。 ## 論文情報 | 項目 | 内容 | |---|---| | 著者 | [[Albert Greenberg]], James R. Hamilton ([[James Hamilton]]), Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A. Maltz, Parveen Patel, Sudipta Sengupta | | 所属 | [[Microsoft Research]] | | 発表 | SIGCOMM 2009 (Barcelona, 2009-08-17) | | PDF | `.raw/papers/vl2-sigcomm09.pdf` | ## 概要 ### 解決する問題 2009年当時のデータセンターネットワークは 3 つの根本的欠陥を持っていた。 1. **帯域不足と過剰サブスクリプション**: 階層型ツリートポロジでは上位リンクが 5:1〜80:1 で過剰サブスクリプションされ、サーバプールが分断される。ToR の上位リンクが 2.5:1〜8:1、ツリー最上位が 80:1 という実測値。 2. **リソース断片化**: サーバの IP アドレスがネットワーク位置に紐づくため、サービス間でサーバを再割り当てすると IP 再設定と VLAN 変更が必要。仮想マシン(VM)の移行も VLAN 外に出ると IP を変えなければならない。 3. **可用性の低さ**: コアルータ・アグリゲーションスイッチの障害が広範囲に波及。8 つの本番データセンター(数十万台規模)の 1 年分ログを分析すると、20% の障害で冗長コンポーネントが全滅した。 実測データセンタートラフィック(1,500 ノードクラスタ、2 ヶ月)の分析結果: - **トラフィックパターンの高ボラティリティ**: 50〜60 クラスタで近似しても誤差が大きく、予測可能な周期性がない。1 パターンの継続時間は中央値で 100 秒以下。 - **フローサイズ分布**: マウスフロー(数 KB)が多数だが、バイト数の大半は 100MB〜1GB のゾウフロー。 - **同時接続数の二峰性**: 平均約 10 フロー/サーバが 60%以上、100 フロー超が 10% 以上。 ### 提案手法: VL2 アーキテクチャ VL2 の 3 原則: 1. **ランダム化で高ボラティリティに対処** — VLB によるランダム経路選択 2. **実績あるネットワーク技術の活用** — IP ルーティング・ECMP・エニーキャスト・マルチキャスト(スイッチ変更不要) 3. **エンドシステムへの機能委譲** — サーバ側の shim レイヤ(VL2 エージェント)で経路制御 #### Clos トポロジ ![[wiki/sources/_attachments/vl2-sigcomm09/fig-clos-topology.png]] *図: VL2 の折り畳み Clos ネットワーク。Intermediate スイッチ(スパイン)と Aggregation スイッチ(リーフ)の間が完全二部グラフ。スイッチ間リンクは 10G、サーバ間は 1G。* 折り畳み Clos ネットワーク(2段スイッチ)で構成: - **Intermediate スイッチ(スパイン)**: $D_A/2$ 台。全スパインが同一エニーキャストアドレス(LA: 10.1.1.1)を共有。 - **Aggregation スイッチ(リーフ)**: $D_I$ 台。各スパインと完全二部グラフで接続。 - **ToR スイッチ**: $D_A D_I / 4$ 台。各 ToR は 2 台の Aggregation スイッチに上流接続。 - **サーバ**: ToR 1 台あたり $20(D_A D_I / 4)$ 台。 スイッチ間リンクはサーバリンクより高速(現行設計: スイッチ間 10G / サーバ 1G)。このギャップを活用することで、Fat-tree より少ないケーブル数でフロー分散が容易になる。 Intermediate スイッチ 1 台の障害で帯域幅が $1/n$ だけ減少するという緩やかな劣化特性を持つ(従来の 1:1 冗長と対比)。$D=144$ ポートスイッチ(当時 1 台 1 万ドル)を使えば 100K サーバまでノーオーバサブスクリプションで接続可能。 #### VL2 のアドレス体系と VLB ![[wiki/sources/_attachments/vl2-sigcomm09/fig-vlb-forwarding.png]] *図: VLB によるパケット転送。送信元 S (AA: 20.0.0.55) がランダムな Intermediate スイッチ経由で宛先 D (AA: 20.0.0.56) に IP-in-IP で送達。* VL2 は 2 種類の IP アドレス空間を使い分ける: | 種別 | 略称 | アドレス空間 | 役割 | |---|---|---|---| | Application Address | AA | 20/8 | サービスが使うフラットな名前。トポロジ的意味を持たない | | Location Address | LA | 10/8 | スイッチとインターフェースの位置。OSPF で広告 | パケット転送フロー: 1. サーバが AA 宛にパケットを送信 → VL2 エージェントが ARP をインターセプト 2. VL2 エージェントがディレクトリサービスに AA→LA を問い合わせ 3. ランダムに選んだ Intermediate スイッチの LA(エニーキャスト)をアウターヘッダに付加し IP-in-IP カプセル化 4. ECMP が複数パスを経由して Intermediate スイッチへ届ける(スパイン間均等分散) 5. Intermediate スイッチがデカプセル、宛先 ToR の LA で再カプセル、ToR が最終デカプセルして AA へ届ける [[Valiant Load Balancing]](VLB)の利点: - 全 Intermediate スイッチが同一エニーキャストアドレスを持つため、スイッチ障害時に VL2 エージェントへの通知不要(ECMP が自動で生きているスイッチに振り分け) - ホストの 5 タプルハッシュ値を外部 IP ソースアドレスに入れて ECMP ハッシュを改善(一部安価スイッチの制限への対応) #### ディレクトリサービス 2 層アーキテクチャ: - **ディレクトリサーバ**(読み取り最適化、3〜5 台): AA→LA キャッシュを保持、エージェントのルックアップに応答。30 秒ごとに RSM から同期。 - **RSM サーバ**(書き込み最適化、3〜5 台): Paxos 合意で強整合性を保証。 - エージェントはランダムに選んだ 2 台のディレクトリサーバに並列問い合わせ。先着応答を採用。 - 古いキャッシュは「実際にパケットが届かなかった時点で」リアクティブに修正(帯域・CPU の無駄を省く)。 #### 後方互換性 - **ARP**: ディレクトリシステムに置換。ブロードキャストを排除。 - **DHCP**: ToR の DHCP リレーエージェントがユニキャストで DHCP サーバへ転送。 - **ブロードキャスト/マルチキャスト**: サービスごとに IP マルチキャストアドレスを割り当て。VL2 エージェントがブロードキャストをレート制限。 - **インターネット向けトラフィック**: フロントエンドサーバは AA に加えて LA も付与。BGP で外部広告。 ## 新規性 1. **既存スイッチハードウェアの無変更採用**: Fat-tree は専用ルーティングプリミティブが必要、Monsoon は L2 ベースで既存 L3 フォールトトレラント機構を再発明。VL2 は OSPF・ECMP・エニーキャストなど既存 L3 技術のみで実現。 2. **VLB のデータセンター内スイッチファブリックへの応用**: VLB は元来並列プロセッサの通信向けにパケットスイッチ向けに提案されたが、データセンター環境のフローレベル適用を実証。 3. **トラフィック実測に基づく設計**: 初の本番データセンタートラフィック実測研究を兼ね、ボラティリティが高くランダム分散が有効であることを実証。 ## 実験設定 **プロトタイプ**: 75 台サーバ + 10 台スイッチ(Intermediate 2 台 / Aggregation 3 台 / ToR 5 台) - スイッチ: Broadcom 5704/5660 ASIC。10G Ethernet ポート。OSPF・ECMP・IP-in-IP デカプセルをラインレートでサポート。 - サーバ: TCP 拡張統計(congestion window・RTT)をカーネルでロギング。 **ディレクトリ評価**: 最大 40 台マシン(3〜5 RSM ノード + 3〜5 ディレクトリサーバ + 残はエージェントエミュレーション) ## 実験結果 ### 均一高帯域(全対全シャッフル) 75 台サーバ間での 2.1TB メモリ間シャッフル: - 完了時間: 395 秒 - コアリンク平均使用率: 約 80% - 集計スループット: 58.8 Gbps (効率 94%) - TCP 公平性指数: 0.99 超(1.0 が完全公平) - 比較: 従来の 5:1 オーバサブスクリプション設計では同量のシャッフルに約 5 倍の時間が必要 ### VLB 公平性 Aggregation→Intermediate のリンク利用量の Jain 公平性指数が全 Aggregation スイッチにわたり平均 0.98 超。流量の多さが統計的多重化の恩恵をもたらす。 ### サービス間分離 - サービス 1 の長期 TCP フロー中にサービス 2 が急増しても、サービス 1 のスループット低下なし。 - 短寿命 TCP コネクション(マウスフロー)のバーストに対しても同様に分離を維持。TCP の輻輳制御がホースモデル適合性を自然に強制。 ### リンク障害後の収束 ![[wiki/sources/_attachments/vl2-sigcomm09/fig-convergence-after-failure.png]] *図: Intermediate スイッチへのリンクを順次切断・復元。OSPF による再収束は各障害後 1 秒未満。帯域幅が段階的に低下・回復する緩やかな劣化特性を示す。* OSPF が 1 秒未満で再収束。最後の 1 台の Intermediate スイッチのみが残る極端な障害でも、VLB と ECMP が利用可能な帯域の約 80% を維持。 ### ディレクトリサービス性能 3 台のディレクトリサーバで: - **ルックアップ**: 75K lookups/秒 で P99 < 1ms - **更新**: 35K updates/秒 で P99 < 200ms - **スケーラビリティ**: ルックアップ容量はディレクトリサーバ数に線形比例(1台あたり 17K/秒)。100K サーバのデータセンターで最悪ケース 100 万同時ルックアップ/秒を捌くのに約 60 台が必要(全サーバの 0.06%)。 ### VLB 対最適ルーティング比較 実測トラフィック行列に対するリンク最大使用率の比較: - **適応型ルーティング**(各 TM を個別最適化): 最重リンク使用率を 1.0 に正規化 - **VLB**: 最重リンク使用率が適応型より約 5% 高い。中央値リンクは同等。 - **最善の鈍感ルーティング**: VLB とほぼ同等 → VLB は適応型ルーティングと比べて複雑さが大幅に低いにもかかわらず、最重リンク使用率の差はわずか 5%。 ## 考察 **コストと規模**: - $D=144$ ポートスイッチ(1台 1万ドル): 100K サーバをノーオーバサブスクリプションで接続可能 - $D=24$ ポートスイッチ(1台 1千ドル): 約 10K サーバ - VL2(ノーオーバサブスクリプション)のコスト ≒ 従来ネットワーク(5:1 オーバサブスクリプション)のコスト - 従来ネットワークをノーオーバサブスクリプションにすると VL2 比で約 5 倍の費用 **トポロジ選択の妥当性**: 実測ボラティリティ(50〜60 クラスタで誤差が大)は、少数のトラフィック行列に最適化するアダプティブルーティングが実用的でないことを示す。ランダム化 VLB がこの環境に最適なアプローチである。 **象フロー問題**: VLB + ECMP のフロー単位分散において、長寿命のゾウフローが偏在すると一部リンクに輻輳が集中するリスクがある。実験では本番データセンタートラフィックでは問題にならなかった。TCP が輻輳を検知した場合に大フローのハッシュを変えて経路を変える簡易機構で対処可能。 ## 強み / 弱点・課題 ### 強み - **今日から導入可能**: スイッチのハードウェア変更不要。既存 ASIC の標準機能(OSPF・ECMP・IP-in-IP)のみ使用。 - **シンプルな設計**: VLB のランダム化が複雑なトラフィックエンジニアリングを不要にする。 - **実測根拠**: 本番データセンタートラフィック・障害データに基づいた設計選択。 - **段階的障害耐性**: Intermediate スイッチ 1 台の障害で帯域が $1/n$ 減少するだけ(従来の広範囲ダウンと対比)。 ### 弱点・課題 - **フロー単位 VLB の限界**: パケット単位分散(VLB 理論の前提)ではなくフロー単位のため、少数の象フローがある場合に偏りが生じうる。 - **TCP 依存**: ホースモデル適合はエンドツーエンド TCP 輻輳制御に委ねる。UDP などの非協調的なトラフィックには脆弱。 - **ディレクトリシステム単一障害点**: Paxos RSM で高可用性を確保するが、RSM 選出ラグ(約 10 秒)が障害時に発生。 - **OSPF 再収束**: OSPF のデフォルトタイマーではリンク回復時の利用開始に 30 秒かかる(障害検知は 1 秒未満だが、復元は遅延)。 - **規模の前提**: スイッチ間リンクがサーバリンクより速いことが前提。このギャップがなくなれば VLB の有効性が低下。 ## 関連 - アーキテクチャ概念: [[Valiant Load Balancing]] / [[マルチプレーンClosトポロジ]] / [[データセンター輻輳制御]] - エンティティ: [[Albert Greenberg]] / [[James Hamilton]] / [[VL2]] / [[Microsoft Research]] - 関連論文: Fat-tree ([[@2008__SIGCOMM__Fat-Tree]])・DCell・BCube・Monsoon との比較 ## 出典 - Greenberg A. et al. "VL2: A Scalable and Flexible Data Center Network." SIGCOMM 2009.