Topology Design for Large-Scale Interconnection Networks

A Modern Approach
1. Auflage 2026
ISBN: 978-1-394-36251-6
Verlag: John Wiley & Sons Inc

Buch, Englisch, 400 Seiten

Transforming Network Topology Design from Art to Science

For decades, the design of large-scale network topologies has relied heavily on heuristic intuition and bottom-up engineering experience. While classic structures like Fat-tree have achieved immense success, the underlying mathematical principles governing their performance have remained largely implicit. This book introduces the first general framework capable of systematically generating and optimizing large-scale network topologies through a rigorous top-down approach. It reveals the hidden mathematical principles behind successful engineering designs, using Ramanujan graphs and combinatorial designs to achieve the optimal trade-off among various performance metrics. From clarifying the success of classic Fat-tree topology to designing future-proof AI clusters, this framework provides a universal blueprint for next-generation interconnection networks.

It is an essential guide for researchers, engineers, industry professionals and students seeking to master the topology design and analysis of interconnection networks.

Topics explored in this book include: - Mathematical background of topology design, including basic graph theory, algebra graph theory and combinatorial design
- A unified topology design flow, including intra-module design, connection design, inter-module design, and finalization
- Reinterpretation and evolution of several representative topology design instances, including families of fat-tree, HyperX, Dcell, and Bcube
- The design method of brand-new topologies from scratch and guiding principles for the selection of design patterns and parameters
- Applications to intelligent computing center (AI Cluster) and other emerging scenarios
- Future directions of topology design, including both theoretical exploration and practical extension

Autoren/Hrsg.

Shao, Ziyu

Deng, Yichi

Fachgebiete

• Mathematik | Informatik Mathematik Geometrie
• Mathematik | Informatik EDV | Informatik Computerkommunikation & -vernetzung
• Technische Wissenschaften Elektronik | Nachrichtentechnik Nachrichten- und Kommunikationstechnik

Inhaltsverzeichnis

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

Über Autor(innen)

ZIYU SHAO is a Professor and the Director of the Network Intelligence Center at the School of Information Science and Technology, ShanghaiTech University, Shanghai, China. He was a Visiting Research Fellow with the EE department at Princeton University; a Visiting Professor at the EECS department, University of California at Berkeley; and a Visiting Scientist at the Simons Institute for the Theory of Computing at Berkeley.

YICHENG DENG is a Postgraduate Student at ShanghaiTech University, studying under the supervision of Dr. Ziyu Shao. She is a student member of the IEEE.