Clos Network Topology 再入門

1. CLOS Network Demystifying DC Network Topologies Masayuki Kobayashi
2. Motivation • 現在のデータセンターネットワークで広く採⽤されているデザインファミリに “Clos Network” があ り、これは ”Clos” や “IP Fabric” または “Spine-Leaf” といった⾔葉で⼀括にされている。 • この設計の原点は1953年に発表された、回線交換網が抱えるスケールアップ問題を、スイッチを多 段接続しスケールアウトすることで、接続ノード数が増加してもより少ないコストでノンブロッキ ングネットワークを実現できるというシステム理論に由来する。 • しかし現代のデータセンターファブリックを設計するにあたって、この応⽤可能な理論の背景にあ る数学的な考察や、構造化された思考プロセスでアプローチできる者は少ない。 • そこで、計算機科学における従来の Clos Network の基本的な概念とその設計について、トポロジに 注⽬して紐解くことで、現在のDC Networkにおける Clos Network の実装と本質に迫る。 • 「技術の変化は振り⼦でなく螺旋である」という考えのもと、半世紀以上前の技術に戻ってきたよ うに⾒えて、進化しているキーファクターが何であるのかを理解するための⼀助となる。
3. Motivation https://tarepan.hatenablog.com/entry/2019/10/06/195058 http://dev1.blog.btrax.com/jp/2013/11/26/spiral/%EF%BC%89 lٕज़ͷมԽ͸ɺΑ͘ৼΓࢠʹྫ͑ΒΕ·͢ɻͰ΋ৼΓࢠͰ͸ͳ͘ɺͲͪΒ͔ͱ͍͏ͱཐટʢΒͤΜʣͷΑ͏ͳ΋ͷͩͱࢥ͍ͬͯ ·͢ɻಉ͡ͱ͜Ζʹ໭͖͍ͬͯͯΔΑ͏ʹݟ͑ͯɺલճͷपظ͔Β͸ࠩ෼͕͋Δɻࠩ෼ͱɺͦͷࠩ෼ΛՄೳʹٕͨ͠ज़ɻ Ҏલͱಉ͡ͱ͜Ζʹ໭͖͍ͬͯͯΔΑ͏ʹݟ͑ͯɺ࣮͸ਐԽ͍ͯ͠Δ෦෼ͷΩʔϑΝΫλʔ͕ॏཁͳΜͰ͢Ͷɻ ͕ͦ͜ݟ͑ͳ͍ͱʮͦΕ͸೥લʹ௨ͬͨಓͩʯΈ͍ͨͳɺ࿝֐ൃݴ͔΋͠Εͳ͍͜ͱΛݴͬͯ͠·͍·͢ɻz 技術選定の審美眼。時代を超えて⽣き続ける技術と、破壊的な変化をもたらす技術を⾒極める（前編）。デブサミ2018 https://www.publickey1.jp/blog/18/2018.html
4. Objective • ネットワークトポロジや関連するデザインファミリについて正確に理解し、論理的に説明できるよ うになる。 • ハードウェア性能やビジネス要求などのパラメータから、最も 性能・拡張性・コスト の観点で優 れたネットワーク構成を論理的に導出できるようになるための基礎理論を習得する。 • ネットワークアーキテクチャから、そのメリットとトレードオフを推測し⾒極められるようになる。 • 限定されたドメインにおいてトポロジが規則的であり数式的に表現可能であることは、ソフトウェ アによるネットワーク制御との親和性が⾼いことを理解し、旧世代的な⼈間の運⽤を極⼒排除した SDN世代のネットワーク運⽤の基盤を実現する。
5. Data Center Network Topologies それぞれのデザインパターンの背後にある共通の概念と、構造化された思考プロセスは何か https://engineering.fb.com/2019/03/1 4/data-center-engineering/f16- minipack/ https://logmi.jp/tech/articles/323317 https://techblog.yahoo.co.jp/entry/20200323819517/ https://en.wikipedia.org/wiki/Clos_network DCN市場に溢れる “Clos Network Topology” パケット交換網 (IP Clos) 計算機科学分野での “Clos Network Topology” 回線交換網
6. Switching Performance 転送能⼒や転送遅延などのネットワークシステムの性能を決める要素は3つある 本資料は最初にネットワークトポロジに着⽬する Topology Routing Algorithm Flow Control
7. Network Topologies - Direct vs Indirect ネットワークトポロジーは2種類ある Torus/Hypercube/Mesh Fat Tree/Crossbar/MIN(Clos) Direct Indirect
8. Direct 直接網 計算ノードがネットワークの内側に位置する 計算ノードとネットワークノードの境界が曖昧 超低遅延を必要とする環境 HPCの領域で広く採⽤される https://corporate-blog.global.fujitsu.com/fgb/2020-11-13/taking-on-the-challenge-of- covid-19-the-birth-of-six-dimensional-interconnect-technology-for-the- supercomputer-fugaku-part-1/ スーパーコンピューター「富岳」の6次元トーラス接続
9. Direct https://www.usenix.org/conference/nsdi22/presentation/gibson Google Aquila – Dragonfly Topology
10. Indirect 間接網 計算ノードがネットワークのエッジに位置する 計算ノードとネットワークノードの境界が明確 超低遅延に不向き ⾼いスループットが必要な環境 複数のアプリケーションが同じネットワークを共有 典型的なデータセンターネットワークの領域
11. Network Topologies - Direct vs Indirect Pictures taken from “Cloud Data Centers and Cost Modeling”, by Morgan Kaufmann, 2015
12. Indirect Network Past and Present
13. Crossbar Switch https://en.wikipedia.org/wiki/Crossbar_switch The art of multiplexing https://medium.com/@marceloboeira/the-art-of-multiplexing-36fc5b22a34e
14. Crossbar Switch すべての送信元と宛先をつなぐパスが存在する 衝突(競合)が発⽣しない限り、すべてのパスが利⽤可能 異なる宛先への同時通信は衝突しない(ノンブロッキング) 接続ノード数(N)が少ない場合に適する 交点(クロスポイント)の数 は O(N^2) 現代の並列コンピュータでは NoC に置き換えられた IP packet switching では現在でも利⽤される Clos Network の Clos は⼈名由来なのでこの Cross ではない (Network-on-Chip)
15. Crossbar “Fabric” https://www.grotto-networking.com/BBSwitchArch.html fabric: ⽣地, 布, 織物
16. Crossbar Switch Scaling https://www.grotto-networking.com/BBSwitchArch.html より⼤きなファブリックに交換してスケールさせる ラインを後から追加することができない スイッチのコスト(クロスポイント数)が増⼤する 典型的なスケールアップモデル ⼩さなサイズのスイッチファブリックのネットワークで⼤きなスイッチファブリックを構築するアプローチへ
17. M N M N Crossbar Switch
18. Multistage Interconnection Networks (MINs) Switching Element(SE) と呼ばれる小規模なスイッチを多段接続して構成する スケールアウトモデル これまで多くの異なるMINアーキテクチャが考案され、Closは歴史的に最も成功した
19. Multistage Interconnection Networks (MINs) stage stage module module module module stage module module Ingress stage Middle stage Egress stage
20. Multistage Interconnection Networks (MINs) クロスバーファブリックはノンブロッキングを実現するが、MINは構成によって異なる 2x2スイッチで2ステージのMINを構成した場合、 A -> E が占有中の時、B -> Fへの利⽤可能な経路が無い https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/
21. Multistage Interconnection Networks (MINs) 2ステージでもノンブロッキングネットワークを実現できるが、 この場合のオーダー(クロスポイント数)は 2x4x4 = 32 となり、クロスバーより悪化する。 https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/ ノンブロッキングを実現しつつ、クロスバーファブリックよりコストの低いアーキテクチャが必要になる
22. Classification of MINs MINは構成⽅法によって以下の特性に分類される Blocking (ブロッキング) 宛先が異なっていても経路上で衝突する Non-Blocking (ノンブロッキング) 宛先が異なっていていれば常に経路上で衝突しない Rearrangeable (リアレンジブル) 宛先が異なっていていれば衝突しない経路をスケジュール可能
23. Blocking Output Port Contention 同じ出⼒ポート(宛先)が選択された状態 Path Contention 宛先が異なっていても同じパスが選択された状態
24. Blocking Network Banyan(Butterfly) Network Delta Network Omega Network Baseline Network Generalized Cube Clos network (Blocking Configuration) Banyan tree 熱帯に分布する⽊。複雑なパターンで交差する根を持つ。
25. 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
26. Delta Network – Destination Routing 8x8 Delta Network
27. Delta Network – Destination Routing 8x8 Delta Network
28. Delta Network – Output Port Contention 8x8 Delta Network
29. Delta Network – Path Contention 8x8 Delta Network
30. Delta Network https://www.janog.gr.jp/meeting/janog33/doc/janog33-bgp-nkposong-1-ja.pdf
31. Omega Network Delta Networkと同じくBanyan Network の⼀例 Nlog(2)N/2 パーフェクトシャッフルという接続で構成される 1bit 左シフトした番号に接続する⽅法 Self Routing 特性を持ち Destination Routing が可能 各ステージに対応するbitに注⽬して転送先を決定 0 の場合: 上のポートから送信 1 の場合: 下のポートから送信 どのポートから送信しても任意の宛先に到達可能 8x8 Omega Network
32. Omega Network – Destination Routing 8x8 Omega Network
33. Omega Network – Path Contention 8x8 Omega Network
34. Baseline Network Omega Networkと同じくBanyan Network の⼀例 Nlog(2)N/2 シャッフル⽅法が変更された構成 Destination Routing が可能 8x8 Baseline Network
35. Butterfly Network https://www.researchgate.net/publication/238832945_A_virtually_nonblocking_self- routing_permutation_network_which_routes_packets_in_Olog_2_N_time https://en.wikipedia.org/wiki/Butterfly_network
36. Rearrangeable https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/ 既存のパスを再配置(リアレンジ)する A -> F のパスも利⽤可能になる B -> H, D -> E が占有中のため、A -> F の利⽤可能なパスが無い
37. Rearrangeable Network Benes Network Clos network (Rearrangeble Configuration)
38. Benes Network – Rearrangeable Clos Baseline + Inverse Baseline 構成
39. Non-Blocking Network Batcher-Banyan Network Clos Network (Non-Blocking Configuration)
40. Batcher-Banyan Network ⼊⼒で並び替えることでノンブロッキ ングになる (Bitonic Sorting Network)
41. Batcher-Banyan Network
42. Issues of MINs スイッチングエレメントの相互接続の複雑さ 全体のパスを決定することの複雑さ 複数の接続要求を同時に満たすことができるかどうかを判断する難しさ 再配置するパスとそれらを移動する場所を⾒つけることの難しさ (Slepian-Duguid定理)
43. 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) 中間ステージの数でブロッキング特性を調節可能
44. Clos Network - Crosspoint growth クロスバーファブリックと⽐較すると、 N=36 を境にクロスポイント数が逆転する。 Nが⼤きくなるにつれてクロスポイントが節約される C. Clos, “A Study of Non-Blocking Switching Networks”, Bell System Technical Journal, The, vol 32, no 2, bll 406–424, Mrt 1953.
45. Clos Network ⼊出⼒数をn, 中間ステージのスイッチ数をmとして 以下の条件でネットワークの性質が決定する。 Non-Blocking: m ≧ 2n -1 Rearrangeable: m ≧ n Blocking: m ＜ n スイッチの⼊出⼒数と個数がすべてのステージで異なっても良い
46. Clos Network – Rearrangeable Configuration https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/
47. 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 を満たす。 よって、リアレンジブルになる。
48. Clos Network – Rearrangeable Configuration https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/ 5 stage Clos Network になる 4x4の中間スイッチを2x2のスイッチで置き換える
49. Clos Network – Rearrangeable Configuration https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part1/ これは結果的にBenes Network を導出したことになる 再配置可能なノンブロッキングネットワークを再帰的 に構築できることを証明した
50. 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 を満たす。 よって、ノンブロッキングになる。
51. Clos Network – Non-Blocking Configuration 【問題】 8 ⼊⼒ 8 出⼒の Clos Network をノンブロッキングで構築するためには、各ステージでどのよ うなスイッチを接続すれば良いか。
52. 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 を満たす。 よって、ノンブロッキングになる。
53. Clos Network Theorem • Non-Blocking: m ≧ 2n -1 : Clos定理 • Rearrangeable: m ≧ n : Slepian Duguid定理 (Paullʼs matrix ) • Blocking: m ＜ n
54. Clos Network Theorem https://www.telematica.polito.it/app/uploads/2018/07/02-clos.pdf
55. Clos Network History https://ja.wikipedia.org/wiki/Clos%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF Closネットワークが最初に考案されたときは、クロスポイントの数は、スイッチングシステムの総コストによく近 似できた。この事実は電気機械式クロスバーには重要だったが、相互接続を直接シリコンに実装することが可能 であるVLSIの出現や、⽐較的⼩さなボードのクラスタには不要であったため、重要性は薄れていった。 ところが、光ファイバーの接続をベースとした⾮常に⼤規模な相互接続構造を持つ複雑なデータセンターの出現 によって、Closネットワークは再び重要性を取り戻した[3]。 Closネットワークの⼀種であるBenešネットワークは、 近年の応⽤先として機械学習での利⽤を⾒い出した[4]。
56. DCNW
57. Tree Topology 典型的なDCNWはツリートポロジ 階層が深いほどボトルネックになりやすい 上位のスイッチほど⾼価になる(コスト増) ⼤量のコモディティイーサネットスイッチを活⽤して、⾼性能・低コストのDCNWを⽬指す流れに Pictures taken from “Cloud Data Centers and Cost Modeling”, by Morgan Kaufmann, 2015
58. 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. ⾮常に有名な論⽂
59. 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
60. From Clos to “Leaf and Spine” topology Clos Topology Spine-Leaf Topology スイッチモジュールは⼀⽅向 すべてのパスは3つのモジュールを経由する スイッチモジュールは双⽅向 すべてのパスは1もしくは3つのモジュールを経由する
61. Unidirectional vs Bidirectional Unidirectional MIN Bidirectional MIN Pictures taken from “Interconnection Networks: An Engineering Approach”, by Duato, Yalamanchili and Ni, 2003
62. 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
63. High Radix, High Levels Network Radix Levels Levels Radix
64. Fat Tree k個のレベルを持つバイナリファットツリーに接続されているノードの総数（N） K=4 N(4)=15 Pictures taken from “Cloud Data Centers and Cost Modeling”, by Morgan Kaufmann, 2015
65. K-ary Fat Tree 1種類のコモディティスイッチでNWを構成 すべてのスイッチでポート数が等しいと仮定 スイッチのポート数 = Pod数 = K 4-ary Fat Tree
66. From Clos to “K-ary Fat Tree” topology https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
67. K-ary Fat Tree 4-ary Fat Tree
68. K-ary Fat Tree hTps://packetpushers.net/demysUfying-dcn-topologies-clos-fat-trees-part2/ Fat Tree(Clos NW)の⼀般化公式
69. K-ary Fat Tree 現実の制約(空間, 電⼒)を無視した設計 ⼤量のHWとケーブリングコストが発⽣ オーバサブスクリプションを未考慮 コストが莫⼤になるため、そのままの適⽤は困難 K=48 の Fat Tree Pictures taken from “Cloud Data Centers and Cost Modeling”, by Morgan Kaufmann, 2015
70. 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/
71. 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/
72. https://engineering.linkedin.com/blog/2016/03/the-linkedin-data-center-100g-transformation Design examples for Fat-tree 公開されている事例を元に、理論を検証する
73. 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/
74. 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/
75. Design examples for Fat-tree - LinkedIn • Top-Spineを再配置してグルーピングする (Mid-Spineの 1 はTop-Spineグループ1へ接続) https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
76. Design examples for Fat-tree - LinkedIn • 馴染みの構成が出現する https://packetpushers.net/demystifying-dcn-topologies-clos-fat-trees-part2/
77. Design examples for Fat-tree - LinkedIn • 馴染みの構成が出現する
78. Design examples for Fat-tree - Facebook • 同様に検証可能 https://www.usenix.org/conference/nsdi21/presentation/abhashkumar https://engineering.fb.com/2014/11/14/production-engineering/introducing-data-center-fabric-the-next-generation-facebook-data-center-network/
79. Design practices • 各ポートが25/50/100Gに対応している64x100Gのスイッチを採⽤する • スイッチ間の接続は100Gとする • サーバー接続は25Gである • ラックあたり最⼤48台のサーバ収容で、最⼤300ラックまで拡張する計画がある • ToRでは4:1のオーバーサブスクリプションレートを適⽤する 【問題1】 以下の条件を元に、性能・拡張性・構築コストの観点で効果的なネットワークを設計せよ。 またその根拠を数値を⽤いて論理的に説明せよ。
80. Design practices • 各ポートが25/50/100Gに対応している64x100Gのスイッチを採⽤する • スイッチ間の接続は100Gとする • サーバー接続は25Gである • ラックあたり最⼤48台のサーバ収容で、最⼤300ラックまで拡張する計画がある • ToRでは4:1のオーバーサブスクリプションレートを適⽤する • ToRはラックあたり2台設置し冗⻑する 【問題2】 以下の条件を元に、性能・拡張性・構築コストの観点で効果的なネットワークを設計せよ。 またその根拠を数値を⽤いて論理的に説明せよ。
81. Design pracQces 【問題3】 広く採⽤されているIP Clos NWの設計で、中間層のスイッチを対応するSpine Planeにまとめて 接続する⽅法がある。この意図と利点が何か説明せよ。
82. Switching Performance 転送能⼒や転送遅延などのネットワークシステムの性能を決める要素は3つある 次回はルーティング設計に着⽬する（続く） Topology Routing Algorithm Flow Control