Andrew R. Curtis
S. Keshav
ABSTRACT
Fundamental limitations of traditional data center network architectures have led to the development of architectures that provide enormous bisection bandwidth for up to hundreds of thousands of servers. Because these architectures rely on homogeneous switches, implementing one in a legacy data center usually requires replacing most existing switches. Such forklift upgrades are typically prohibitively expensive; instead, a data center manager should be able to selectively add switches to boost bisection bandwidth. Doing so adds heterogeneity to the network's switches and heterogeneous high-performance interconnection topologies are not well understood. Therefore, we develop the theory of heterogeneous Clos networks. We show that our construction needs only as much link capacity as the classic Clos network to route the same traffic matrices and this bound is the optimal. Placing additional equipment in a highly constrained data center is challenging in practice, however. We propose LEGUP to design the topology and physical arrangement of such network upgrades or expansions. Compared to current solutions, we show that LEGUP finds network upgrades with more bisection bandwidth for half the cost. And when expanding a data center iteratively, LEGUP's network has 265% more bisection bandwidth than an iteratively upgraded fat-tree.
- J. H. Ahn, N. Binkert, A. Davis, M. McLaren, and R. S. Schreiber. Hyperx: topology, routing, and packaging of efficient large-scale networks. In Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis (SC '09), 2009. Google Scholar
Digital Library
- M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. In SIGCOMM, 2008. Google ScholarDigital Library
- V. E. Beneš. Mathematical Theory of Connecting Networks and Telephone Traffics. Academic Press, 1965.Google Scholar
- T. Benson, A. Anand, A. Akella, and M. Zhang. Understanding data center traffic characteristics. In Proceedings of the 1st ACM workshop on Research on enterprise networking (WREN), 2009. Google ScholarDigital Library
- C. Clos. A study of non-blocking switching networks. Bell System Technical Journal, 32(5):406--424, 1953.Google ScholarCross Ref
- A. R. Curtis, S. Keshav, and A. López-Ortiz. LEGUP: Using heterogeneity to reduce the cost of data center network upgrades. Technical report, University of Waterloo, 2010.Google Scholar
- N. G. Duffield, P. Goyal, A. Greenberg, P. Mishra, K. K. Ramakrishnan, and J. E. van der Merive. A flexible model for resource management in virtual private networks. In SIGCOMM, 1999. Google ScholarDigital Library
- L. Epstein and A. Levin. An APTAS for generalized cost variable-sized bin packing. SIAM J. Comput., 38(1):411--428, 2008. Google ScholarDigital Library
- A. Ford, C. Raiciu, M. Handley, and S. Barre. TCP extensions for multipath operation with multiple addresses. IETF, 2009.Google Scholar
- A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, C. Kim, P. Lahiri, D. Maltz, P. Patel, and S. Sengupta. VL2: a scalable and flexible data center network. In SIGCOMM, 2009. Google ScholarDigital Library
- A. G. Greenberg, J. R. Hamilton, D. A. Maltz, and P. Patel. The cost of a cloud: research problems in data center networks. Computer Communication Review, 39(1):68--73, 2009. Google ScholarDigital Library
- C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, C. Tian, Y. Zhang, and S. Lu. BCube: a high performance, server-centric network architecture for modular data centers. In SIGCOMM, 2009. Google ScholarDigital Library
- C. Guo, H. Wu, K. Tan, L. Shi, Y. Zhang, and S. Lu. Dcell: a scalable and fault-tolerant network structure for data centers. In SIGCOMM, 2008. Google ScholarDigital Library
- U. Hoelzle and L. A. Barroso. The Datacenter as a Computer: An Introduction to the Design of Warehouse-Scale Machines. Morgan and Claypool Publishers, 2009. Google ScholarDigital Library
- K. Holmberg and D. Yuan. A lagrangian heuristic based branch-and-bound approach for the capacitated network design problem. Operations Research, 48(3):461--481, 2000. Google ScholarDigital Library
- F. K. Hwang and D. S. Richards. Steiner tree problems. Networks, 22(1):55--89, 1992.Google ScholarCross Ref
- D. S. Johnson, A. Demers, J. D. Ullman, M. R. Garey, and R. L. Graham. Worst-case performance bounds for simple one-dimensional packing algorithms. SIAM J. on Comput., 3(4):299--325, 1974.Google ScholarCross Ref
- S. Kandula, S. Sengupta, A. Greenberg, and P. Patel. The nature of datacenter traffic: Measurements & analysis. In IMC, 2009. Google ScholarDigital Library
- A. Kershenbaum. Telecommunications network design algorithms. McGraw-Hill, 1993. Google ScholarDigital Library
- J. Kim, W. J. Dally, and D. Abts. Flattened butterfly: a cost-efficient topology for high-radix networks. SIGARCH Comput. Archit. News, 35(2), 2007. Google ScholarDigital Library
- M. Kodialam, T. V. Lakshman, and S. Sengupta. Maximum throughput routing of traffic in the hose model. In Infocom, 2006.Google ScholarCross Ref
- E. L. Lawler and D. E. Wood. Branch-and-bound methods: A survey. Operations Research, 14(4):699--719, 1966.Google ScholarDigital Library
- C. E. Leiserson. Fat-trees: universal networks for hardware-efficient supercomputing. IEEE Trans. Comput., 34(10):892--901, 1985. Google ScholarDigital Library
- J. Mudigonda, P. Yalagandula, M. Al-Fares, and J. C. Mogul. SPAIN: COTS data-center ethernet for multipathing over arbitrary topologies. In NSDI, 2010. Google ScholarDigital Library
- R. N. Mysore, A. Pamboris, N. Farrington, N. Huang, P. Miri, S. Radhakrishnan, and V. Subram. Portland: A scalable fault-tolerant layer 2 data center network fabric. In SIGCOMM, 2009. Google ScholarDigital Library
- C. Raiciu, C. Pluntke, S. Barre, A. Greenhalgh, D. Wischik, and M. Handley. Data center networking with multipath TCP. In Hotnets, 2010. Google ScholarDigital Library
- A. Rasala and G. Wilfong. Strictly non-blocking WDM cross-connects for heterogeneous networks. In STOC, 2000. Google ScholarDigital Library
- A. Tavakoli, M. Casado, T. Koponen, and S. Shenker. Applying NOX to the datacenter. In HotNets-VIII, 2009.Google Scholar
- H. Wu, G. Lu, D. Li, C. Guo, and Y. Zhang. MDCube: a high performance network structure for modular data center interconnection. In CoNEXT, 2009. Google ScholarDigital Library
- R. Zhang-Shen and N. McKeown. Designing a predictable internet backbone with Valiant load-balancing. In Thirteenth International Workshop on Quality of Service (IWQoS '05), 2005. Google ScholarDigital Library
Index Terms
- LEGUP: using heterogeneity to reduce the cost of data center network upgrades
Recommendations
Flattened Butterfly Topology for On-Chip Networks
With the trend towards increasing number of cores in a multicore processors, the on-chip network that connects the cores needs to scale efficiently. In this work, we propose the use of high-radix networks in on-chip networks and describe how the ...
Scalable high-radix router microarchitecture using a network switch organization
As the system size of supercomputers and datacenters increases, cost-efficient networks become critical in achieving good scalability on those systems. High-radix routers reduce network cost by lowering the network diameter while providing a high ...
Silicon-photonic network architectures for scalable, power-efficient multi-chip systems
ISCA '10Scaling trends of logic, memories, and interconnect networks lead towards dense many-core chips. Unfortunately, process yields and reticle sizes limit the scalability of large single-chip systems. Multi-chip systems break free of these areal limits, but ...
Comments