Preface xi
Acknowledgments xv
Acronyms xvi
1 Introduction 1
1.1 Motivation 1
1.2 Overview of the Design Framework 3
1.3 Existing Works 4
1.3.1 Concrete Topology Designs 4
1.3.2 Search-based Topology Designs 11
1.4 Mathematical Background I: Graph Theory 12
1.4.1 Undirected Graph 12
1.4.2 Order and Node Degree 12
1.4.3 Path 13
1.4.4 Distance and Diameter 13
1.4.5 Connectivity 14
1.4.6 Special Undirected Graphs 14
1.5 Mathematical Background II: Expander Graph 18
1.5.1 Expansion Constant 18
1.5.2 Spectra of Graphs 19
1.5.3 Ramanujan Graph 20
1.6 Mathematical Background III: Combinatorial Design Theory 22
1.6.1 Overview of Block Design 22
1.6.2 Balanced Incomplete Block Design 24
1.6.3 Pairwise Balanced Design and Group Divisible Design 29
1.6.4 The Relationships Among Extended Block Designs 34
1.7 Subgraph Options 35
1.7.1 Block Incidence Graph 35
1.7.2 Transversal Design Graph 38
2 A Unified Design Framework 41
2.1 Categorization of Nodes 42
2.2 Ingredients of Topology Design 43
2.2.1 Components and Their Interfaces 44
2.2.2 Interconnections among Components 48
2.3 A Unified Topology Design Procedure 58
2.3.1 Design Procedure 58
2.3.2 Decoupling of Topology Design 63
2.4 Guiding Principles and Concrete Tools 64
2.4.1 Performance Metrics 65
2.4.2 Guiding Principles 76
2.4.3 Concrete Tools 79
2.5 Revisit of Existing Topologies 99
2.5.1 Fat-Tree 101
2.5.2 Aspen Trees 102
2.5.3 AB Fat-Tree 103
2.5.4 Subway 106
2.5.5 HyperX 106
2.5.6 Dragonfly 107
2.5.7 DCell 108
2.5.8 BCube 110
3 Evolution of Classical Topologies 113
3.1 Evolution of Switch-centric Topologies 114
3.1.1 Evolution of Tree-like Topologies 114
3.1.2 Evolution of HyperX-like Topologies 157
3.2 Evolution of Server-centric Topologies 170
3.2.1 Evolution of DCell-like Topologies 174
3.2.2 Evolution of BCube-like Topologies 176
4 Systematic Framework for Generic Topology Design 179
4.1 Overview 179
4.2 Patterns of Topology Design 180
4.2.1 Exploration of Design Patterns 181
4.2.2 Naming of Design Patterns 183
4.3 Parameters of Design Patterns 185
4.3.1 Relationships and Constraints Among Parameters 185
4.3.2 Parameters Under Each Design Pattern 195
4.4 Performance Metrics of Design Patterns 208
4.4.1 Scalability 208
4.4.2 Cost 210Contents ix
4.4.3 Latency 212
4.4.4 Throughput 216
4.4.5 Fault-tolerance 220
4.5 Guidelines on Selection of Design Patterns 220
4.5.1 Analysis on Option Selection for Each Term 220
4.5.2 Demonstrations by Existing Topologies 229
4.6 Guidelines on Determination of Parameter Values 231
4.6.1 Parameter Determination Scheme 231
4.6.2 Demonstrations by Various Design Patterns 236
5 Applications and Future Work 271
5.1 Topology Design for AI Clusters 271
5.1.1 Single Domain System 272
5.1.2 Dual-domain System: Scale-up and Scale-out 275
5.1.3 A Unified Topology Design Scheme for Dual-domain Systems 278
5.1.4 3D Torus 314
5.2 Future Work 314
5.3 Epilogue: The End of the Beginning 315
Appendix: A Proofs 317
A.1 Proofs for Chapter 1 317
A.1.1 Proof of Lemma 1.4 317
A.1.2 Proof of Corollary 1.4 318
A.1.3 Proof of Lemma 1.5 318
A.1.4 Proof of Lemma 1.6 318
A.1.5 Proof of Lemma 1.7 319
A.1.6 Proof of Lemma 1.8 320
A.1.7 Proof of Lemma 1.9 320
A.1.8 Proof of Corollary 1.5 322
A.1.9 Proof of Lemma 1.11 322
A.2 Proofs for Chapter 2 322
A.2.1 Proof of Theorem 2.1 322
A.2.2 Proof of Theorem 2.2 323
A.2.3 Proof of Theorem 2.3 323
A.2.4 Proof of Theorem 2.4 323
A.2.5 Proof of Theorem 2.5 324
A.2.6 Proof of Theorem 2.6 324
A.2.7 Proof of Lemma 2.1 324
A.3 Proofs for Chapter 3 325
A.3.1 Proof of Theorem 3.1 325x Contents
A.3.2 Proof of Theorem 3.2 327
A.4 Proofs for Chapter 4 329
A.4.1 Proof of Lemma 4.1 329
A.4.2 Proof of Lemma 4.2 333
A.4.3 Proof of Lemma 4.3 333
A.4.4 Proof of Lemma 4.4 336
A.4.5 Proof of Lemma 4.5 340
A.4.6 Proof of Lemma 4.6 340
A.4.7 Proof of Lemma 4.7 341
A.4.8 Proof of Lemma 4.8 342
A.4.9 Proof of Lemma 4.9 343
A.4.10 Proof of Lemma 4.10 343
A.4.11 Proof of Lemma 4.11 344
A.4.12 Proof of Lemma 4.12 344
A.4.13 Proof of Lemma 4.13 345
A.4.14 Proof of Lemma 4.14 346
A.4.15 Proof of Lemma 4.15 346
A.4.16 Proof of Lemma 4.16 347
A.4.17 Proof of Lemma 4.17 348
A.4.18 Proof of Lemma 4.18 349
A.4.19 Proof of Lemma 4.19 356
A.4.20 Proof of Lemma 4.20 358
References 363
Index 373
