# ECMP（等コスト多重経路ルーティング） ## 定義 ECMP（Equal-Cost Multi-Path ルーティング）とは、宛先に向かう複数の等コスト経路が存在する場合、トラフィックをそれらの経路に分散させるルーティング手法である。RFC 2992（C. Hopps, 2000）で定義される。 OSPF-ECMP などの実装では以下の 3 つの分散方式が提案されている: 1. **ラウンドロビン・ランダム化**: 順番に経路を選択。パケット再順序問題が発生しやすく、特に TCP に悪影響。 2. **領域分割（リージョンスプリッティング）**: プレフィックスをより長いマスクで分割。大規模ネットワークでは 600,000 以上のルーティングテーブルエントリが必要になり非現実的。 3. **ハッシュ方式**: 送受信アドレスなどのヘッダフィールドをハッシュし、出力ポートを決定。フロー粒度で分散されるためパケット再順序を防げるが、フロー帯域幅を考慮しないため偏りが生じやすい。 ## Fat-Tree における ECMP の採用と限界 Fat-Tree トポロジ（[[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]]）では任意のポッド間ホスト対に (k/2)² 本の等コスト経路が存在するが、標準 ECMP には以下の問題がある。 **採用の背景**: - 大規模クラスタで帯域を確保するための「マルチルーテッドツリー」には多重経路技術が必要 - 既存の多くのエンタープライズスイッチが ECMP をサポート **実装上の限界**: - **多重数の制限**: 現在の ECMP 実装は 8〜16 多重経路に制限。k=48 の Fat-Tree で必要な (k/2)²=576 の等コスト経路には遠く及ばない - **転送表の爆発的増加**: OSPF-ECMP では下位ポッドスイッチが他のすべてのサブネットに対して (k/2) プレフィックスを保持する必要があり、総エントリ数は k×(k/2)² となる。25,000 ホスト構成では約 600,000 エントリが必要で、コスト増・探索レイテンシ増の原因になる - **帯域考慮なし**: ハッシュ方式はフロー帯域幅を考慮しないため、単純な通信パターンでも過剰購読が発生しうる **Fat-Tree 論文の解決策**（二段ルーティングテーブル）: プレフィックス/サフィックスの二段探索により、転送表エントリ数をスイッチあたり最大 k エントリ以内に抑えながらフロー分散を実現する。宛先 IP の下位バイト（ホスト ID）をエントロピー源として確定的に分散させ、パケット再順序を防ぐ。 ## 横断的知見 - **ECMP の限界が Fat-Tree 二段ルーティングの誕生を促した**: 標準 ECMP の多重数制限（8〜16）と転送表の爆発的増加が Fat-Tree の独自ルーティング手法設計を必要とした。この構造的な問題は Fat-Tree 以降のデータセンターでも共通の課題として残っており、現代の大規模 AI クラスタでは BGP ECMP の限界が再び議論されている。(Source: [[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]]) - **ハッシュ衝突による帯域幅損失の定量化**: Hedera([[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]])は Fat-Tree と ECMP を同時に採用した実データセンターでのハッシュ衝突影響を Monte Carlo シミュレーションで定量化した。k=48 のファットツリーで 1 ホストあたりのフロー数が少ない場合(エレファントフロー支配的)、ハッシュ衝突は二分帯域幅を平均 **60.8%** 損失させる。一方、並列フローが 1,000/ホストになると損失は 2.5% に留まる。すなわち Fat-Tree が提唱したトポロジ的優位性(完全二分帯域幅)は、ECMP という転送プロトコルの限界によってエレファントフロー時に著しく損なわれる。Fat-Tree 論文(SIGCOMM 2008)と Hedera 論文(NSDI 2010)を並べることで、「トポロジ設計」と「フロースケジューリング」が独立に解かれていた問題だが実際には不可分であることが明確になる。(Source: [[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]], [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]]) - **ECMP が適切に機能する条件**: フロー数が十分多い(多対多 all-to-all で 1,000+ フロー/ホスト)場合はハッシュ衝突の影響が平均化される。Hedera は閾値(実装では 100 Mbps = ホストリンク容量の 10%)以下のマウスフローを引き続き ECMP に任せることで、両アプローチを組み合わせる。ECMP は廃棄でなく補完として位置付けられた。(Source: [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]]) ## 未解決の問い - 現代の高速スイッチでは ECMP の多重数上限が向上しているか。Fat-Tree 規模での ECMP は今なら標準実装で対応可能か。 - 大規模 AI クラスタ（100,000 GPU 超）では、Fat-Tree 二段ルーティングに相当するカスタム経路制御が引き続き必要か、それとも SRv6・BGP ECMP で十分か。 - Hedera が 2010 年に示した「エレファントフロー検知 → 動的再配置」パターンは、現代の高速(400 GbE+)データセンターで実現可能か。スケジューリング間隔をサブ秒にするための技術的障壁は何か。 - RDMA / RoCEv2 を使う AI 学習クラスタでは ECMP のフロー単位ハッシングが PFC(Priority Flow Control)のデッドロックを誘発しうる。ECMP ハッシュ衝突と PFC デッドロックは同一の根本原因から派生するか。 ## 関連 - 概念: [[データセンターネットワークトポロジ]] / [[負荷分散]] / [[データセンター輻輳制御]] / [[フロースケジューリング]] - ソース: [[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]] / [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]] ## 出典 - [[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]] - [[@2010__NSDI__Hedera - Dynamic Flow Scheduling for Data Center Networks]](ECMP のハッシュ衝突を Monte Carlo シミュレーションで定量化。エレファントフロー時に最大 60.8% の二分帯域幅損失を実測) - RFC 2992: C. Hopps, "Analysis of an Equal-Cost Multi-Path Algorithm," IETF, 2000.