Upgrade to PRO for Only $50/Year—Limited-Time Offer! 🔥

Clos Network Topology 再入門

Clos Network Topology 再入門

Masayuki Kobayashi

February 22, 2022
Tweet

More Decks by Masayuki Kobayashi

Other Decks in Technology

Transcript

  1. Motivation • 現在のデータセンターネットワークで広く採⽤されているデザインファミリに “Clos Network” があ り、これは ”Clos” や “IP

    Fabric” または “Spine-Leaf” といった⾔葉で⼀括にされている。 • この設計の原点は1953年に発表された、回線交換網が抱えるスケールアップ問題を、スイッチを多 段接続しスケールアウトすることで、接続ノード数が増加してもより少ないコストでノンブロッキ ングネットワークを実現できるというシステム理論に由来する。 • しかし現代のデータセンターファブリックを設計するにあたって、この応⽤可能な理論の背景にあ る数学的な考察や、構造化された思考プロセスでアプローチできる者は少ない。 • そこで、計算機科学における従来の Clos Network の基本的な概念とその設計について、トポロジに 注⽬して紐解くことで、現在のDC Networkにおける Clos Network の実装と本質に迫る。 • 「技術の変化は振り⼦でなく螺旋である」という考えのもと、半世紀以上前の技術に戻ってきたよ うに⾒えて、進化しているキーファクターが何であるのかを理解するための⼀助となる。
  2. Objective • ネットワークトポロジや関連するデザインファミリについて正確に理解し、論理的に説明できるよ うになる。 • ハードウェア性能やビジネス要求などのパラメータから、最も 性能・拡張性・コスト の観点で優 れたネットワーク構成を論理的に導出できるようになるための基礎理論を習得する。 •

    ネットワークアーキテクチャから、そのメリットとトレードオフを推測し⾒極められるようになる。 • 限定されたドメインにおいてトポロジが規則的であり数式的に表現可能であることは、ソフトウェ アによるネットワーク制御との親和性が⾼いことを理解し、旧世代的な⼈間の運⽤を極⼒排除した SDN世代のネットワーク運⽤の基盤を実現する。
  3. Network Topologies - Direct vs Indirect Pictures taken from “Cloud

    Data Centers and Cost Modeling”, by Morgan Kaufmann, 2015
  4. Multistage Interconnection Networks (MINs) stage stage module module module module

    stage module module Ingress stage Middle stage Egress stage
  5. Multistage Interconnection Networks (MINs) 2ステージでもノンブロッキングネットワークを実現できるが、 この場合のオーダー(クロスポイント数)は 2x4x4 = 32 となり、クロスバーより悪化する。

    https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/ ノンブロッキングを実現しつつ、クロスバーファブリックよりコストの低いアーキテクチャが必要になる
  6. Blocking Network Banyan(Butterfly) Network Delta Network Omega Network Baseline Network

    Generalized Cube Clos network (Blocking Configuration) Banyan tree 熱帯に分布する⽊。複雑なパターンで交差する根を持つ。
  7. Delta Network Banyan Network の⼀例 ⽚⽅のリンクは直進、もう⼀⽅は2n離れて接続 Self Routing 特性を持ち Destination

    Routing が可能 各ステージに対応するbitに注⽬して転送先を決定 0 の場合: 上のポートから送信 1 の場合: 下のポートから送信 どのポートから送信しても任意の宛先に到達可能 ⼊⼒数 N : ステージ数: log(2)N ステージあたりのスイッチ数: N/2 全体のスイッチ数: Nlog(2)N/2 8x8 Delta Network
  8. Omega Network Delta Networkと同じくBanyan Network の⼀例 Nlog(2)N/2 パーフェクトシャッフルという接続で構成される 1bit 左シフトした番号に接続する⽅法

    Self Routing 特性を持ち Destination Routing が可能 各ステージに対応するbitに注⽬して転送先を決定 0 の場合: 上のポートから送信 1 の場合: 下のポートから送信 どのポートから送信しても任意の宛先に到達可能 8x8 Omega Network
  9. Clos Network C. Clos, “A Study of Non-Blocking Switching Networks”,

    Bell System Technical Journal, The, vol 32, no 2, bll 406– 424, Mrt 1953. 1938年にEdson Erwinが発明した概念 1952年にCharles Closが形式化し発表 最⼩3ステージで構成される完全結合MIN 対称ネットワークで⼊⼒数は⼆乗 (N = n^2) 中間ステージの数でブロッキング特性を調節可能
  10. Clos Network ⼊出⼒数をn, 中間ステージのスイッチ数をmとして 以下の条件でネットワークの性質が決定する。 Non-Blocking: m ≧ 2n -1

    Rearrangeable: m ≧ n Blocking: m < n スイッチの⼊出⼒数と個数がすべてのステージで異なっても良い
  11. Clos Network – Rearrangeable Configuration hRps://packetpushers.net/demysSfying-dcn-topologies-clos-fat-trees-part1/ N=8, n=2 とすると、 1st

    , 3rd stage のスイッチ数は N/n = 4 2nd stage の 4x4スイッチ数は m = 2 これは m ≧ n を満たす。 よって、リアレンジブルになる。
  12. Clos Network – Non-Blocking Configuration https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/ N=4, n=2 とすると、 1st

    , 3rd stage のスイッチ数は N/n = 2 2nd stage の 2x2スイッチ数は m = 3 これは m ≧ 2n-1 を満たす。 よって、ノンブロッキングになる。
  13. Clos Network – Non-Blocking Configuration 【問題】 8 ⼊⼒ 8 出⼒の

    Clos Network をノンブロッキングで構築するためには、各ステージでどのよ うなスイッチを接続すれば良いか。
  14. Clos Network – Non-Blocking Configuration 【問題】 8 ⼊⼒ 8 出⼒の

    Clos Network をノンブロッキングで構築するためには、各ステージでどのよ うなスイッチを接続すれば良いか。 N=8, n=2 とすると、 1st , 3rd stage のスイッチ数は N/n = 4 2nd stage の 4x4スイッチ数は m = 3 これは m ≧ 2n-1 を満たす。 よって、ノンブロッキングになる。
  15. Clos Network Theorem • Non-Blocking: m ≧ 2n -1 :

    Clos定理 • Rearrangeable: m ≧ n : Slepian Duguid定理 (Paullʼs matrix ) • Blocking: m < n
  16. A scalable, commodity data center network architecture Al-Fares M, Loukissas

    A, Vahdat A. A scalable, commodity data center network architecture, SIGCOMMʼ08, August 17–22, 2008, pp. 63–74. ⾮常に有名な論⽂
  17. Fat Tree – Special Instance of a Clos Network https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/

    ⼀⽅向ファブリックから双⽅向ファブリック(パケット交換)への転換 Folded Clos は Spine-Leafトポロジとして知られ、 ⼊出⼒数の⼤きいスイッチを使うネットワークを High Radix Network と呼ぶ。 中央で折りたたむ Folded Clos (Non-Folded) Clos
  18. From Clos to “Leaf and Spine” topology Clos Topology Spine-Leaf

    Topology スイッチモジュールは⼀⽅向 すべてのパスは3つのモジュールを経由する スイッチモジュールは双⽅向 すべてのパスは1もしくは3つのモジュールを経由する
  19. Unidirectional vs Bidirectional Unidirectional MIN Bidirectional MIN Pictures taken from

    “Interconnection Networks: An Engineering Approach”, by Duato, Yalamanchili and Ni, 2003
  20. Fat Tree C. E. Leiserson, “Fat-Trees: Universal Networks for Hardware-Efficient

    Supercomputing”, IEEE Trans. Comput., vol 34, no 10, bll 892–901, 1985. ネットワークがツリー構造で配置され、 プロセッサがリーフノードとして機能する。 ツリーを上に移動すると、スイッチ間でより多くの帯域幅 を利⽤できる。 https︓//en.wikipedia.org/wiki/Fat_tree Radix Levels
  21. Design examples for Fat-tree 3-Stage Clos構成のネットワークで、 32ポートのスイッチがあり、各ポートが25/50/100Gに対応していると仮定し サーバー接続(ダウンリンク)は25G、アップリンクの接続は100Gであると想定。 k =

    32, L = 2 FT(32,2) • k/2ポートをアップリンク、k/2ポートをダウンリンクに分割 • アップリンク16ポート、ダウンリンク16ポート • Leafのダウンリンクは 16x100G = 64x25G に変換可能※ • 最⼤16台のSpine • 最⼤32台のLeaf • 最⼤32x64=2,048台のサーバ ※ 実際に1台のLeafスイッチでサーバ64台をサポートすることは考えにくい 3-Stage Clos https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
  22. Design examples for Fat-tree 5-Stage Clos構成のネットワークで、 32ポートのスイッチがあり、各ポートが25/50/100Gに対応していると仮定し サーバー接続(ダウンリンク)は25G、アップリンクの接続は100Gであると想定。 • k/2ポートをアップリンク、k/2ポートをダウンリンクに分割

    • アップリンク16ポート、ダウンリンク16ポート • Leafのダウンリンクは 16x100G = 64x25G に変換可能※ • 最⼤256台のTop Level Spine • 最⼤512台のLeaf • 最⼤512x64=32,768台のサーバ 5-Stage Clos k = 32, L = 3 FT(32,3) ※ 実際に1台のLeafスイッチでサーバ64台をサポートすることは考えにくい https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
  23. Design examples for Fat-tree - LinkedIn • 32x100Gのスイッチがあり、各ポートが25/50/100Gに対応している • スイッチ間の接続は50G

    • サーバー接続は25G、アップリンクは50Gである • ラックあたり最⼤48台のサーバ収容で、50k+のスケール要件 • 32x100G = 64x50G • FT(64,2)は最⼤2,048台しか収容できないためFT(64,3)が必要 • K=64個のPod • 各Podにはk/2=32台のLeaf, 32台のMid-Spine • 32個のTop-Spineのセットの内部に32台 k = 64, L = 3 FT(64,3) ⾮常に巨⼤な構成でこのままでは現実的ではない https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
  24. Design examples for Fat-tree - LinkedIn • Leafで 6:1 のオーバサブスクリプションを適⽤する

    • 25Gx48=1,200Gbps に対して、アップリンクは50Gx4=200Gbps Leaf 1,200Gbps 200Gbps 6:1 6:1 1:1 1:1 https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
  25. Design examples for Fat-tree - LinkedIn • Top-Spineを再配置してグルーピングする (Mid-Spineの 1

    はTop-Spineグループ1へ接続) https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
  26. Design practices • 各ポートが25/50/100Gに対応している64x100Gのスイッチを採⽤する • スイッチ間の接続は100Gとする • サーバー接続は25Gである • ラックあたり最⼤48台のサーバ収容で、最⼤300ラックまで拡張する計画がある

    • ToRでは4:1のオーバーサブスクリプションレートを適⽤する 【問題1】 以下の条件を元に、性能・拡張性・構築コストの観点で効果的なネットワークを設計せよ。 またその根拠を数値を⽤いて論理的に説明せよ。
  27. Design practices • 各ポートが25/50/100Gに対応している64x100Gのスイッチを採⽤する • スイッチ間の接続は100Gとする • サーバー接続は25Gである • ラックあたり最⼤48台のサーバ収容で、最⼤300ラックまで拡張する計画がある

    • ToRでは4:1のオーバーサブスクリプションレートを適⽤する • ToRはラックあたり2台設置し冗⻑する 【問題2】 以下の条件を元に、性能・拡張性・構築コストの観点で効果的なネットワークを設計せよ。 またその根拠を数値を⽤いて論理的に説明せよ。