データセンターネットワーク：Clos/Fat-Tree トポロジ

なぜ従来のツリー型では足りなくなったのか

古典的なエンタープライズLANは、アクセス・ディストリビューション・コアの 3層ツリー で組まれてきました。この形は、トラフィックの大半が端末から外部へ抜ける 南北（north-south） 方向だった時代には合理的でした。ところが分散ストレージ、マイクロサービス、分散学習が主流になると、トラフィックは サーバー間を横に流れる東西（east-west） が支配的になります。ツリー型ではサーバー同士が通信するたびに上位のコアへ登って降りる必要があり、頂点のリンクに負荷が集中して詰まります。上位ほど帯域を増やす必要が生じ、超高速・高価なシャーシ型コアに依存する構造になってしまうのです。

この行き詰まりへの解が、安価で同一スペックの箱型スイッチを多数並べて広帯域を合成する Clos／Fat-Tree です。L2の転送原理そのものは /network/ethernet-switching-internals/ のままで、変わるのは「どう配線して帯域をスケールさせるか」という構造の設計です。

Clos ネットワークの起源と無閉塞性

Clos ネットワークは1953年に Charles Clos が電話交換網の論文で定式化した、多段クロスバ の理論です。少数ポートの小さなスイッチ（クロスバ）を入力段・中間段・出力段の3段に組み合わせ、巨大な1枚のクロスバと同等の接続能力を、はるかに少ない素子数で実現します。

核心は 無閉塞（non-blocking） という性質です。これは「空いている入力と空いている出力の組であれば、必ず経路を確保できる」ことを指します。無閉塞には強さの段階があり、Clos の定理は、入力段1台あたりのポート数を n としたとき、中間段のスイッチ数 m が m ≥ 2n − 1 なら既存接続を一切張り替えず常に経路を張れる 厳密無閉塞（strictly non-blocking）、m ≥ n なら既存接続の張り替えを許せば収容できる 再配置可能無閉塞（rearrangeably non-blocking） が成立することを示しました。データセンターの文脈ではこの「素子を増やせば任意の入出力ペアに帯域を約束できる」という性質を、パケット網に移植して使っています。

Fat-Tree とスパインリーフ：木を「太らせる」発想

Fat-Tree は1985年に Charles Leiserson が提唱した、Clos を木構造として再解釈したトポロジです。通常の木は根に近いほどリンクが細く詰まりますが、Fat-Tree は 根に近づくほど枝（帯域）を太くする ことで上位の輻輳を解消します。実装としては「太い1本のリンク」ではなく、同じ容量のリンクを複数本束ねて等価な太さを合成します。

現代のデータセンターで主流の スパインリーフ（spine-leaf） は、この Fat-Tree を実用上もっとも素直な2段に落とし込んだ形です。

• リーフ（leaf／ToR）: ラック上部に置かれ、サーバーを直接収容するスイッチ。下り口にサーバー、上り口に全スパインを接続する。
• スパイン（spine）: リーフ同士を束ねるバックボーン。サーバーは直結せず、すべてのリーフと1本ずつ つながる。

配線規則は単純で、各リーフは全スパインに必ず接続し、リーフ同士・スパイン同士は直接つながない というものです。この規則から、どのサーバーからどのサーバーへ向かう通信も リーフ → スパイン → リーフ の ちょうど3ホップ（リーフ・スパイン・リーフを数えて） で到達し、経路長が均一になります。レイテンシが予測しやすいのはこの均一性の帰結です（帯域とレイテンシの関係は /network/bandwidth-latency/ を参照）。

決定的な違いは冗長リンクの扱いです。古典L2では複数経路はループの原因なので /network/spanning-tree-internals/ が片側を論理遮断し、半分の帯域を捨てていました。スパインリーフは逆に 全スパインを同時に使い切る ことを前提に設計され、ここで ECMP が要になります。

二分割帯域とオーバーサブスクリプション比

この種のトポロジの性能を測る基準が 二分割帯域（bisection bandwidth） です。定義は「ネットワークをサーバー数が等しい2つに分割したとき、その境界をまたぐリンク帯域の合計の最小値」です。直感的には「最悪の分け方をしたとき、左半分と右半分の間に残る帯域」であり、全サーバーが反対側の相手と同時通信する最悪パターンでの実効帯域を表します。スパインリーフでは、各リーフからスパイン側へ向かう 上りリンク（uplink）の総帯域 が境界帯域を律します。

ここで重要になるのが オーバーサブスクリプション比（oversubscription ratio） です。1台のリーフについて、下り帯域（サーバー向き総容量）対 上り帯域（スパイン向き総容量） の比で定義します。

オーバーサブスクリプション比 = 下り帯域(サーバー側) : 上り帯域(スパイン側)

例: リーフが
  - サーバー向け 48ポート × 25Gbps = 1200 Gbps（下り）
  - スパイン向け 6ポート × 100Gbps = 600 Gbps（上り）
比 = 1200 : 600 = 2 : 1
→ サーバーが一斉に上り方向へ送ると、上りが半分しか無く輻輳しうる

比が 1:1 なら、全サーバーが同時に最大速度で外向き通信しても上りが詰まりません。これが 無閉塞（フルバイセクション） な構成です。比が 2:1、3:1 と大きくなるほど上り帯域を間引いてコストを下げた構成で、その代わり全サーバー全力通信時には輻輳が起きえます。設計とは、想定する東西トラフィックの同時性とコストを天秤にかけて、この比をどこに置くかを決める作業に他なりません。

ECMP：複数スパインへ「均す」中核アルゴリズム

スパインが N 台あれば、あるリーフから別のリーフへは N 本の等価な経路 が存在します。これらをどう使い切るかが ECMP（Equal-Cost Multi-Path） です。ルーティング（OSPF や BGP）が同コストの複数経路を見つけたとき、ECMP はそれらすべてをフォワーディングテーブルに残し、パケットを分散させます。リンクステート計算の基礎は /network/ospf-spf-internals/ と地続きで、違いは「最良1本だけ残す」のではなく「同コスト全部を残す」点です。

分散の単位は パケットごと ではなく フローごと が基本です。理由は、パケット単位でばらまくと同一フロー内のパケットが別経路を通って到着順が乱れ、上位のTCPが再送やウィンドウ縮小を起こすためです。そこで一般的なハッシュ法では、不変なフロー識別子からスパインを選びます。

ECMP のフロー単位ハッシュ（概念）
  key = hash(送信元IP, 宛先IP, プロトコル,
             送信元ポート, 宛先ポート)        # 5-tuple
  選択スパイン = ECMPメンバ[ key mod スパイン台数 ]
  → 同一フローは常に同じスパインへ（順序保存）
  → 異なるフローは台数分に散らばる（負荷分散）

この方式は多数の小フローが行き交う環境では均等に近づきますが、少数の巨大フロー（エレファントフロー）が同じスパインへ落ちると、そのリンクだけ偏って詰まる ハッシュ衝突による不均衡 が起きます。これを緩和するのが、フロー内をさらに細かい単位に砕いて分散する flowlet 方式や、混雑を測って動的に経路を選ぶ適応型負荷分散です。

トポロジの系統：いつ・何が分岐したか

帯域スケールの考え方は、年代を追って次のように分岐してきました。

分岐の軸は一貫して「増え続ける東西トラフィックを、安価な箱の水平増設でどう吸収するか」です。Clos の無閉塞理論が出発点にあり、Fat-Tree が木への翻訳を与え、商用スイッチの低価格化が実装を可能にし、ECMP が理論上の複数経路をパケット網で現実の負荷分散に変えました。

まとめ

Clos／Fat-Tree は、「少数素子で無閉塞な交換を合成する」という1953年の理論を、安価な同型スイッチの水平増設へと翻訳したものです。スパインリーフはその実用2段版で、全リーフを全スパインに結ぶ均一構造により、東西トラフィックを予測可能なホップ数でさばきます。性能の物差しは二分割帯域であり、設計の自由度はリーフの上り口と下り口の比＝オーバーサブスクリプション比に凝縮されます。1:1なら無閉塞、比を上げればコスト優先。そして理論上の複数経路を現実の帯域に変えるのが、フロー単位ハッシュで順序を保ちつつ全スパインへ均す ECMP です。垂直に積み上げる時代から、水平に並べて均す時代へ——その移行を一望できれば、現代データセンター網の骨格はつかめます。