# A Scalable, Commodity Data Center Network Architecture Navigation: [[index]] | [[データセンターネットワークトポロジ]] | [[ECMP]] > [!abstract] > 今日のデータセンターは膨大な集約帯域幅要件を持つ数万台のコンピュータを収容することがある。ネットワークアーキテクチャは通常、上位層に向かうほど特殊化・高価になるルーティング・スイッチング要素のツリーで構成される。残念ながら、最高級の IP スイッチ・ルータを導入しても、結果として生じるトポロジはネットワーク端でのエッジ帯域幅の 50% しかサポートできず、なおかつ莫大なコストを要する。データセンターノード間の非均一な帯域幅はアプリケーション設計を複雑にし、全体的なシステム性能を制限する。 > > 本論文では、数万個の要素で構成されるクラスタの全集約帯域幅をサポートするために、主として商用のイーサネットスイッチを活用する方法を示す。商用コンピュータのクラスタが特殊化された SMP および MPP をほぼ置き換えたのと同様に、適切に設計・接続された商用スイッチが現在の高級ソリューションより低コストで高性能を提供できると主張する。このアプローチはエンドホストのネットワークインタフェース・オペレーティングシステム・アプリケーションへの変更を必要とせず、イーサネット・IP・TCP と完全に後方互換性がある。 ## 論文情報 | 項目 | 内容 | |---|---| | タイトル | A Scalable, Commodity Data Center Network Architecture | | 著者 | Mohammad Al-Fares, Alexander Loukissas, Amin Vahdat | | 所属 | University of California, San Diego (UCSD) | | 媒体 | ACM SIGCOMM 2008 | | 発表日 | 2008年8月17〜22日（Seattle, Washington） | | DOI/URL | http://ccr.sigcomm.org/online/files/p63-alfares.pdf | ## 概要 [[Mohammad Al-Fares]] ら UCSD の研究者が SIGCOMM 2008 で発表した論文。Fat-Tree トポロジ（Charles Clos が 1953 年に設計した Clos ネットワークの特殊形）を安価な商用イーサネットスイッチで構成することで、数万台規模のデータセンタークラスタに対して全二分帯域幅（full bisection bandwidth）を実現する手法を提案した。k ポートスイッチのみを用いた均質構成、二段ルーティングテーブル、フロー分類器、中央フロースケジューラという四層の経路制御手法を組み合わせ、Ethernet/IP/TCP との完全な後方互換性を維持しながら既存の階層型設計比で約 77% のコスト削減を実現した。 ## 問題設定 **既存のツリー型トポロジの帯域制限** **図1: 従来の 3 層階層型データセンターネットワーク** ![[_attachments/fattree-sigcomm08/fig01-three-tier-topology.png]] (図1. コア／集約／エッジの 3 層構成。ホストとスイッチ間はGigE、スイッチ間は10GigE。Source: Al-Fares+ 2008.) 大規模クラスタでは 2 層または 3 層のスイッチツリーが標準的に採用されてきた。3 層設計（コア・集約・エッジ）は 2 層設計より大規模に対応できるが、以下の問題を抱える。 - **帯域の非対称性**: エッジスイッチ間での通信は全帯域を使えるが、スイッチ階層を上に移動するほど帯域が細る。ルートへの接続が最大のボトルネックになる。 - **過剰購読（オーバーサブスクリプション）**: 典型的な設計では 2.5:1〜8:1 の過剰購読が発生し、最悪の場合は有効帯域の 12.5% しか使えない。 - **コストの非線形増加**: 1:1 の過剰購読比で 20,000 ホストを収容するには約 3,700 万ドルを要し、さらに高速化には高級スイッチが必須。 - **ECMP の限界**: 既存の ECMP 実装は 8〜16 多重経路に制限され、大規模 Fat-Tree 環境に必要な多様性を提供できない。また、経路数に対して転送表エントリが乗算的に増加する。 **図2: ホスト数とコストの関係（過剰購読比別）** ![[_attachments/fattree-sigcomm08/fig02-cost-vs-hosts.png]] (図2. Fat-Tree は 1:1 過剰購読比で既存設計より大幅に安価。Source: Al-Fares+ 2008.) ## 提案手法 ### Fat-Tree トポロジ Clos ネットワークの特殊例として k-ary Fat-Tree を構成する。 **図3: k=4 の Fat-Tree トポロジ（アドレス付き）** ![[_attachments/fattree-sigcomm08/fig03-fattree-k4.png]] (図3. k=4 の Fat-Tree。コア・集約・エッジの 3 層、4 ポッド構成。破線が 10.0.1.2→10.2.0.3 の転送経路。Source: Al-Fares+ 2008.) **構造の特徴**: - k ポッドで構成され、各ポッドは 2 層（エッジ・集約）× k/2 スイッチ - コアスイッチは (k/2)² 個。各コアスイッチはすべての k ポッドに接続 - k ポートスイッチで k³/4 ホストをサポート（k=48 で 27,648 ホスト） - **均質性**: すべてのスイッチ要素が同一。安価な商用部品を全層に活用可能 - **再配置可能非閉塞（rearrangeably non-blocking）**: 任意の通信パターンに対して全二分帯域幅を飽和させる経路集合が存在する **アドレス設計**: プライベート 10.0.0.0/8 空間内で体系的なアドレッシング。 - ポッドスイッチ: `10.pod.switch.1` - コアスイッチ: `10.k.j.i` - ホスト: `10.pod.switch.ID`（ID は 2〜k/2+1） - 各エッジスイッチが /24 サブネット（k/2 ホスト）を担当 ### 二段ルーティングテーブル 既存の単一経路 IP 転送ではすべての等コスト経路のうち 1 本しか選択されず、Fat-Tree の冗長経路を活用できない。本論文は二段プレフィックス探索を提案する。 **一段目**（主テーブル）: 左端一致の /m プレフィックス。サブネット宛ての終端プレフィックスまたは /0 デフォルトルート。 **二段目**（副テーブル）: 右端一致の /m サフィックス。宛先 IP の下位バイト（ホスト ID）に基づいてアップリンクポートを分散。 ポッドスイッチのルーティングテーブルは k/2 プレフィックスと k/2 サフィックスの合計 k エントリ以内に収まる。TCAM で実装すれば lookup レイテンシへの影響は最小限。 ### 二段探索の TCAM 実装 左端エントリ（プレフィックス）をアドレス的に小さい領域に、右端エントリ（サフィックス）を大きい領域に格納することで、両方にマッチする場合は左端エントリを優先するセマンティクスを CAM の「数値最小の一致を出力」特性で実現する。 ### フロー分類器（動的マルチパス） TCP のパケット順序保証のため、同一フロー（送受信 IP アドレスが同一の一連のパケット）を常に同一ポートに転送しつつ、数秒ごとに最高負荷ポートから最低負荷ポートへ最大 3 フローを再配置するヒューリスティックを採用する。ソフトステートのため、状態消失時は二段ルーティングにフォールバック可能。 ### 中央フロースケジューラ（大規模フロー向け） インターネットトラフィックは長尾分布を示し、少数の大規模長寿命フローが帯域の大半を占める。大規模フローを検出したエッジスイッチが中央スケジューラに通知し、スケジューラはすべてのリンク状態をグローバルに把握して競合のない経路を割り当てる。 k=48, 27,648 ホストの構成でも、スケジューラは 5.6MB のメモリと 0.8ms 以下の配置時間で動作する。 ### 障害耐性 各スイッチが隣接機器との BFD（Bidirectional Forwarding Detection）セッションを維持し、リンク・スイッチ障害を検知する。障害情報を周囲のスイッチにブロードキャストし、影響を受けるポートへの新規フロー割り当てを停止することで経路を迂回させる。 ### 電力・発熱 **図6: 帯域幅当たりの電力消費・発熱比較** ![[_attachments/fattree-sigcomm08/fig06-power-per-gbps.png]] (図6. GigE スイッチは 10GigE スイッチより帯域幅当たり電力約半分、発熱約 1/3。Source: Al-Fares+ 2008.) 商用 GigE スイッチは 10GigE スイッチに比べ、帯域幅当たりの電力が約半分、発熱が約 1/3。27,648 ホスト構成での試算では、Fat-Tree は階層型設計に対して 56.6% の電力削減・56.5% の発熱削減を実現する。 ## 新規性 - **商用スイッチのみで full bisection bandwidth**: 既存の ECMP ベースアーキテクチャや高級スイッチを用いた設計が解決できなかった、商用 GigE スイッチのみを用いた全二分帯域幅の実現。 - **転送表サイズの線形抑制**: 二段ルーティングにより、スイッチごとの転送表エントリ数を k 以内に抑制。OSPF-ECMP の経路数乗算的増加問題を回避。 - **TCP 互換のマルチパス**: パケット再順序問題を起こさずにマルチパスを実現するフロー単位の転送制御。 - **均質スイッチ構成**: 全スイッチが同一仕様のため、障害耐性・管理が簡単で、商用価格下落の恩恵を全層で受けられる。 ## 実験設定 Click モジュラーソフトウェアルータで k=4 の Fat-Tree（16 ホスト・20 スイッチ）をプロトタイプ実装。10 台の物理サーバ上で仮想化し、リンク帯域を 96 Mbps に制限して評価。比較対象は 3.6:1 過剰購読比の階層型ツリー。 NetFPGA による TCAM 実装プロトタイプも構築し、100 行以下のコード変更で測定可能なルックアップレイテンシ増加なしに二段ルーティングを実装できることを確認した。 ## 実験結果 **表2: 各手法の有効二分帯域幅（理想値に対する割合）** | テストケース | 従来ツリー | 二段テーブル | フロー分類 | フロースケジューラ | |---|---|---|---|---| | ランダム | 53.4% | 75.0% | 76.3% | **93.5%** | | Stride(1) | 100.0% | 100.0% | 100.0% | 100.0% | | Stride(2) | 78.1% | 100.0% | 100.0% | 99.5% | | Stride(4) | 27.9% | 100.0% | 100.0% | 100.0% | | Stride(8) | 28.0% | 100.0% | 100.0% | 99.9% | | 最悪: ポッド間受信 | 28.0% | 50.6% | 75.1% | **99.9%** | | 最悪: 同 ID 発信 | 27.8% | 38.5% | 75.4% | **87.4%** | Fat-Tree の理想二分帯域幅は 1.536 Gbps。 **主な発見**: - 従来ツリーは全ポッド間通信で最大 28% にまで低下。 - 二段テーブルはランダム通信で 75% を達成。同じホスト ID のフローが同一ポートに集中する確率 50% がボトルネック。 - フロー分類器は最悪ケースで 75% を達成するが、局所的知識のみでコアスイッチ渋滞を防げない場合がある。 - フロースケジューラはグローバル知識を活用し、ランダムで 93%、ほぼすべてのケースで最高性能。 ## 考察 - **静的テーブルの限界**: 二段テーブルは k が小さい場合に同一サフィックスへの衝突が多発する。k が大きくなるほど性能が改善するという予測があるが、本論文では k=4 の小規模検証のみ。 - **フロースケジューラの前提**: 中央スケジューラは Fat-Tree の規則的なトポロジを仮定しており、任意ネットワークへの適用は困難。ただし Fat-Tree の規則性がスケジューラを簡略化する。 - **配線複雑性**: Fat-Tree は多数のスイッチとケーブルを要する。ポッドスイッチとコアの集中配置によるパッケージング（図8）で外部配線を削減できる。 - **後方互換性**: エンドホスト・OS・アプリケーションの変更不要。スイッチのファームウェア修正は 100 行以下。 **図8: 提案パッケージング構成** ![[_attachments/fattree-sigcomm08/fig08-packaging.png]] (図8. ポッドスイッチ（48 スイッチを 1 ユニット化）を各ポッドに配置し、外部ケーブルはポッド間とコア間のみ。Source: Al-Fares+ 2008.) ## 強み / 弱点・課題 **強み**: - 均質な商用スイッチのみで 27,648 ホストの全二分帯域幅を実現し、コストを 1/4 以下に削減 - Ethernet/IP/TCP との完全後方互換。既存のアプリケーション・OS を変更不要 - 障害耐性が豊富な冗長経路に支えられている **弱点・課題**: - k=4 のプロトタイプのみで実証。k=48 での大規模展開は未検証（シミュレーション・推定ベース） - 中央フロースケジューラは単一障害点のリスクがある（論文では「複製可能」と述べるのみ） - 二段テーブルの k が小さいケースでの帯域効率は 75% 止まり - ARP・マルチキャストなどのブロードキャストドメイン管理への言及なし - 実際の電力・発熱値はデータシート値であり、実環境での検証は今後の課題と明記 ## 関連 - [[データセンターネットワークトポロジ]] — Fat-Tree をはじめとするデータセンターネットワーク設計の概念集約 - [[ECMP]] — 等コスト多重経路ルーティング。Fat-Tree での採用と限界 - [[マルチプレーンClosトポロジ]] — Clos ネットワークの現代的発展形 - [[AIデータセンタートポロジ]] — Fat-Tree が現代 AI データセンターの源流 - [[Mohammad Al-Fares]] — 筆頭著者 - [[Amin Vahdat]] — 共著者・UCSD 教授 ## 出典 - Al-Fares, M., Loukissas, A., Vahdat, A. "A Scalable, Commodity Data Center Network Architecture." ACM SIGCOMM 2008, pp. 63–74.