# Fat-Tree ## 定義 Fat-Tree は、上位階層へ行くほどリンク帯域または並列経路を太くして、リーフ間通信のボトルネックを避けるデータセンターネットワークトポロジである。AI/HPC クラスタでは GPU ノード間の all-to-all / all-reduce 通信を支える基盤として、Clos 型 fabric や rail-optimized topology と併用される。 **ROFT(Rail-Optimized Fat-Tree)** は、Spine 間の転送コストを抑えるため業界で広く採用される Fat-Tree の変種である(原典: NVIDIA SuperPOD Reference Architecture, 2023)。GPU をインデックスで「レール」にグルーピングし、同一インデックスの GPU を同一 Leaf スイッチへ接続することで、Spine を跨ぐ通信を削減する。訓練トラフィックには有効だが、静的なレール割り当てのため、送信元・宛先が動的に変化するトラフィックパターンでは特定 Leaf スイッチ・リンクへの集中(トポロジ誘発輻輳)を招きやすい。(Source: [[@2026__X__Next-generation LLM Inference Network - How ZCube Alleviates Network Bottlenecks]]) **Fat-Tree には二つの異なる起源がある**: 元祖 Fat-Tree は C. E. Leiserson が 1985 年に IEEE Trans. Comput. 誌へ発表した並列計算機向け相互接続網であり、プロセッサをリーフノードに配置し上位階層へ行くほどチャネル容量(帯域幅)を太くする設計を指した(原典: Leiserson, "Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing", 1985)。一方、[[Mohammad Al-Fares]] らが SIGCOMM 2008 で提案した k-ary Fat-Tree([[@2008__SIGCOMM__A Scalable Commodity Data Center Network Architecture]])は、この帯域幅漸増モデルを [[Clos Network]] として再定式化し、同一仕様のコモディティスイッチのみで構成する設計に落とし込んだものである。両者は「上位ほど太い」という直感は共有するが、後者は Clos Network の理論的枠組み(Non-Blocking/Rearrangeable条件)に明示的に基づく点で異なる。(Source: [[@2022__SpeakerDeck__Clos Network Topology 再入門]]) **Folded Clos = Spine-Leaf トポロジ**: Fat-Tree(非folded Clos Network)の入力段・出力段スイッチを中央で折りたたむと、一方向ファブリック(全パスが3モジュール経由)から双方向ファブリック・パケット交換(全パスが1または3モジュール経由)へ転換する。この Folded Clos は Spine-Leaf トポロジとして知られ、入出力数の大きいスイッチを使うネットワークは High Radix Network と呼ばれる。(Source: [[@2022__SpeakerDeck__Clos Network Topology 再入門]]) ## 横断的知見 - [[Hawkeye]] は K=4 Fat-Tree(20 スイッチ)を評価環境に使い、PFC provenance graph による RDMA 異常診断を示した。([[@2025__SIGCOMM__Hawkeye - Diagnosing RDMA Network Performance Anomalies with PFC Provenance]]) - [[SAKURAONE]] は open Ethernet/RoCEv2 で rail-optimized leaf-spine を構成し、Fat-Tree/Clos 系の多経路設計を AI HPC へ適用する実例を与える。([[@2026__MLSys2026__SAKURAONE - An Open Ethernet-Based AI HPC System]]) - LLM 訓練では物理トポロジが並列化配分と直接結びつく。pipeline parallelism が pod を跨ぐと通信比率が上がり、MFU が低下する。 - **Fat-Tree と [[Dragonflyトポロジ]] のコスト構造は本質的に異なる**: Fat-Tree は直径が小さく適応ルーティング不要だが、全体帯域を確保するため上位スイッチに多数のポートを集約し、大規模化でスイッチコストが急増する。Dragonfly は直径 3 だが、接続数を O(N^(2/3)) から O(N^(1/2)) に削減でき、大規模時のケーブルコスト比で 2 倍以上の優位性を持つ。ただし Dragonfly は敵対的トラフィックパターンで適応ルーティングを要し、実装の複雑さが増す。(Source: [[@2008__ISCA__Technology-Driven, Highly-Scalable Dragonfly Topology]], [[@2009__IEEE-Micro__Cost-Efficient Dragonfly Topology for Large-Scale Systems]]) - **Rail-only トポロジは Fat-Tree のスパイン層を完全に削除する**: [[@2023__arXiv__Rail-only - A Low-Cost High-Performance Network for Training LLMs with Trillion Parameters]] は LLM 訓練のスパースな通信パターンに着目し、スパイン層を削除してコスト 38-77%・消費電力 37-75% を削減しつつ訓練性能を維持できることを示した。Fat-Tree が提供する全二分帯域は LLM 訓練では大半が未使用であるという観察が、このアーキテクチャを正当化している。(Source: [[@2023__arXiv__Rail-only - A Low-Cost High-Performance Network for Training LLMs with Trillion Parameters]]) - **[[@2022__SC__HammingMesh - A Network Topology for Large-Scale Deep Learning|HammingMesh]] は Fat-Tree のサブネットワークを符号理論で最適に繋ぐ**: [[@2022__SC__HammingMesh - A Network Topology for Large-Scale Deep Learning]] は、2 次元並列化に対して完全帯域分離を提供しつつ、汎用トラフィック用のグローバル帯域も維持する。Fat-Tree が提供する均一な全二分帯域に対し、HammingMesh は AI ワークロードの通信局所性に特化することで低コスト化を実現する。(Source: [[@2022__SC__HammingMesh - A Network Topology for Large-Scale Deep Learning]]) - **ROFT の静的レール割り当ては、PD 分離推論の動的トラフィックパターンと構造的にミスマッチする**: ROFT は GPU インデックスに基づく静的なレール-Leaf 割り当てにより訓練の All-Reduce のような規則的パターンには有効だが、[[Prefill-Decode分離]] 推論では KV Cache 転送の送信元・宛先・トラフィック量が動的に変化するため、レール割り当てが負荷分散に自然に結びつかなくなる。[[ZCube]] はこの問題に対し、静的レール構造を撤廃してスイッチ間を完全二部グラフで結び、GPU ペアごとに一意な最適パスを持たせることで、訓練・推論両方のトラフィックパターンに適応する。ROFT/Fat-Tree が「訓練ワークロードの規則性」を前提に設計されているのに対し、ZCube は「推論ワークロードの不確実性」を設計の出発点に置く点で対照的である。(Source: [[@2026__X__Next-generation LLM Inference Network - How ZCube Alleviates Network Bottlenecks]]) - **K-ary Fat Tree はレベル数Lとポート数kで規模を一般化公式として導出できる**: L段のFat-Treeにおけるコアスイッチ数は(k/2)^(L-1)、収容ホスト数は2(k/2)^L、総スイッチ数は(2L-1)(k/2)^(L-1)として一般化される。2段(L=2)のFT(32,2)はポート数k=32で最大2,048台のサーバしか収容できないため、LinkedInが50,000台規模のスケール要件を満たすには3段(L=3)のFT(64,3)が必要になる。理論上のFT(64,2)構成は最大2,048台の収容上限にすぐ達するため「現実には適用困難」とスライドは指摘しており、段数選択が理論的な一般化公式と実運用の収容要件の突き合わせで決まることを示す具体例になっている。(Source: [[@2022__SpeakerDeck__Clos Network Topology 再入門]]) - **LinkedIn・Facebookの実運用マルチプレーン構成は、Spine層の理論的再配置から導出されるという点で [[マルチプレーンClosトポロジ]] が扱うNIC分割型マルチプレーンとは異なる起源を持つ**: LinkedIn(2016年、100G Transformation)はTop-Spineを4グループ(Plane 1〜4)に再配置し、Mid-Spineの各スイッチが対応するPlaneへのみ接続する構成を取る。Facebook(NSDI'21、F16)も同様にSpine SwitchをSpine Plane 1〜4へ分割する。両者ともFat-Tree(3-stage Clos)の理論的構造からSpine層を意図的にグルーピングし直すことで導出されており、[[マルチプレーンClosトポロジ]] が扱う「800G NICを複数の100G物理プレーンに分割する」というNIC側の分割とは異なる、Spine層側でのプレーン化である。両者を混同しないよう注意が必要。(Source: [[@2022__SpeakerDeck__Clos Network Topology 再入門]]) ## 未解決の問い - Fat-Tree 上の RDMA/PFC 異常診断は、評価用 K=4 より大きい多テナント fabric で線速を保てるか。 - AI 訓練の並列化構成(TP/PP/DP/EP)に対し、Fat-Tree、rail-only、Dragonfly、HammingMesh のどれが最も扱いやすいか。ワークロードの MoE 化が進むと all-to-all 通信が増え、Rail-only の前提(スパース通信)が崩れる可能性がある。 - Fat-Tree の全二分帯域保証は、AI 訓練以外のマルチテナントワークロード（ストレージ・RPC 等）との混在環境で引き続き必要か。ワークロード特化トポロジ（Dragonfly/HammingMesh/Rail-only）はマルチテナント運用にどう適応できるか。 - ROFT のレール割り当てが破綻する条件(トラフィック非対称性の閾値)は定量化されているか。[[ZCube]] のような代替トポロジへの移行が正当化される「非対称性がどの程度になったら」という基準は、[[@2026__X__Next-generation LLM Inference Network - How ZCube Alleviates Network Bottlenecks]] には示されていない。 - Leiserson(1985)のオリジナルFat-Tree(ハードウェア効率の良いスーパーコンピュータ向け相互接続網)とAl-Fares(2008)のk-ary Fat-Tree(データセンター向けClos再定式化)は、直接の系譜(後者が前者を参照・拡張したもの)なのか、それとも「上位ほど太い」という直感が独立に再発見されたものなのか、両論文の直接比較は本wikiで未検証。 ## 関連 - 概念: [[RDMA]] / [[オープンネットワーキング]] / [[RDMAネットワーク監視]] / [[LLM分散学習]] / [[並列化戦略]] / [[ZCube]] / [[Prefill-Decode分離]] / [[Clos Network]] / [[マルチプレーンClosトポロジ]] - ソース: [[@2025__SIGCOMM__Hawkeye - Diagnosing RDMA Network Performance Anomalies with PFC Provenance]] / [[@2026__MLSys2026__SAKURAONE - An Open Ethernet-Based AI HPC System]] / [[@2008__ISCA__Technology-Driven, Highly-Scalable Dragonfly Topology]] / [[@2022__SC__HammingMesh - A Network Topology for Large-Scale Deep Learning]] / [[@2023__arXiv__Rail-only - A Low-Cost High-Performance Network for Training LLMs with Trillion Parameters]] / [[@2026__X__Next-generation LLM Inference Network - How ZCube Alleviates Network Bottlenecks]] / [[@2022__SpeakerDeck__Clos Network Topology 再入門]] ## 出典 - [[@2025__SIGCOMM__Hawkeye - Diagnosing RDMA Network Performance Anomalies with PFC Provenance]] - [[@2026__MLSys2026__SAKURAONE - An Open Ethernet-Based AI HPC System]] - [[@2026__X__Next-generation LLM Inference Network - How ZCube Alleviates Network Bottlenecks]](ROFT の定義とトポロジ誘発輻輳の実測、ZCube との対比) - [[@2022__SpeakerDeck__Clos Network Topology 再入門]](Clos Network Theorem、Leiserson起源との対比、Folded Clos=Spine-Leaf、K-ary Fat Tree一般化公式、LinkedIn/Facebook実運用例)