Dcell: a scalable and fault-tolerant network structure for data centers

ABSTRACT

A fundamental challenge in data center networking is how to efficiently interconnect an exponentially increasing number of servers. This paper presents DCell, a novel network structure that has many desirable features for data center networking. DCell is a recursively defined structure, in which a high-level DCell is constructed from many low-level DCells and DCells at the same level are fully connected with one another. DCell scales doubly exponentially as the node degree increases. DCell is fault tolerant since it does not have single point of failure and its distributed fault-tolerant routing protocol performs near shortest-path routing even in the presence of severe link or node failures. DCell also provides higher network capacity than the traditional tree-based structure for various types of services. Furthermore, DCell can be incrementally expanded and a partial DCell provides the same appealing features. Results from theoretical analysis, simulations, and experiments show that DCell is a viable interconnection structure for data centers.

REFERENCES

• 1: S. B. Akers , B. Krishnamurthy, A Group-Theoretic Model for Symmetric Interconnection Networks, IEEE Transactions on Computers, v.38 n.4, p.555-566, April 1989 [doi>10.1109/12.21148]
• 2: S. Arnold. Google Version 2.0: The Calculating Predator, 2007. Infonortics Ltd.
• 3: Luiz André Barroso , Jeffrey Dean , Urs Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, v.23 n.2, p.22-28, March 2003 [doi>10.1109/MM.2003.1196112]
• 4: A. Carter. Do It Green: Media Interview with Michael Manos, 2007. http://edge.technet.com/Media/Doing-IT-Green/.
• 5: Jeffrey Dean , Sanjay Ghemawat, MapReduce: simplified data processing on large clusters, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.10-10, December 06-08, 2004, San Francisco, CA
• 6: Jose Duato , Sudhakar Yalamanchili , Ni Lionel, Interconnection Networks: An Engineering Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 7: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.15-15, November 06-08, 2006, Seattle, WA
• 8: Sanjay Ghemawat , Howard Gobioff , Shun-Tak Leung, The Google file system, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 9: T. Hoff. Google Architecture, July 2007. http://highscalability.com/google-architecture.
• 10: Intel. High-Performance 1000BASE-SX and 1000BASE-LX Gigabit Fiber Connections for Servers. http://www.intel.com/network/connectivity/resources/doc_library/data_sheets/pro1000mf_mf-lx.pdf.
• 11: Michael Isard , Mihai Budiu , Yuan Yu , Andrew Birrell , Dennis Fetterly, Dryad: distributed data-parallel programs from sequential building blocks, Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, March 21-23, 2007, Lisbon, Portugal
• 12: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 13: K. Liszka, J. Antonio, and H. Siegel. Is an Alligator Better Than an Armadillo? IEEE Concurrency, Oct-Dec 1997.
• 14: Dmitri Loguinov , Anuj Kumar , Vivek Rai , Sai Ganesh, Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863999]
• 15: J. Moy. OSPF Version 2, April 1998. RFC 2328.
• 16: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995]
• 17: Behrooz Parhami, Introduction to Parallel Processing: Algorithms and Architectures, Kluwer Academic Publishers, Norwell, MA, 1999
• 18: Jon Postel. Internet Protocol. RFC 791.
• 19: L. Rabbe. Powering the Yahoo! network, 2006. http://yodel.yahoo.com/2006/11/27/powering-the-yahoo-network/.
• 20: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 21: H. Jay Seigel, W. Nation, C. Kruskal, and L. Napolitando. Using the Multistage Cube Network Topology in Parallel Supercomputers. Proceedings of the IEEE, Dec 1989.
• 22: J. Snyder. Microsoft: Datacenter Growth Defies Moore's Law, 2007. http://www.pcworld.com/article/id,130921/article.html.
• 23: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Design

Keywords:
data center, fault-tolerance, network topology, throughput