Compound graph based hybrid data center topologies

doi:10.1007/s11704-015-4483-5

Front. Comput. Sci.

2015, Vol. 9

Issue (6) : 860-874 https://doi.org/10.1007/s11704-015-4483-5

RESEARCH ARTICLE

Compound graph based hybrid data center topologies

Lailong LUO¹,Deke GUO^1,^*(

),Wenxin LI²,Tian ZHANG³,Junjie XIE¹,Xiaolei ZHOU¹

1. Science and Technology on Information Systems Engineering Laboratory, National University of Defense Technology, Changsha 410073, China
2. Network and Cloud Computing Laboratory, Dalian University of Technology, Dalian 116024, China
3. School of InformationManagement,Wuhan University,Wuhan 430070, China

Download: PDF(658 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

In large-scale data centers, many servers are interconnected via a dedicated networking structure, so as to satisfy specific design goals, such as the low equipment cost, the high network capacity, and the incremental expansion. The topological properties of a networking structure are critical factors that dominate the performance of the entire data center. The existing networking structures are either fully random or completely structured. Although such networking structures exhibit advantages on given aspects, they suffer obvious shortcomings in other essential fields. In this paper, we aim to design a hybrid topology, called R3, which is the compound graph of structured and random topology. It employs random regular graph as a unit cluster and connects many such clusters by means of a structured topology, i.e., the generalized hypercube. Consequently, the hybrid topology combines the advantages of structured as well as random topologies seamlessly. Meanwhile, a coloring-based algorithm is proposed for R3 to enable fast and accurate routing. R3 possesses many attractive characteristics, such as the modularity and expansibility at the cost of only increasing the degree of any node by one. Comprehensive evaluation results show that our hybrid topology possesses excellent topology properties and network performance.

Keywords data center networking compound graph hybrid topology routing design

Corresponding Author(s): Deke GUO

Just Accepted Date: 22 April 2015 Issue Date: 10 November 2015

Cite this article:

Lailong LUO,Deke GUO,Wenxin LI, et al. Compound graph based hybrid data center topologies[J]. Front. Comput. Sci., 2015, 9(6): 860-874.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-015-4483-5
https://academic.hep.com.cn/fcs/EN/Y2015/V9/I6/860

1	Al-Fares M, Loukissas A, Vahdat A. A scalable, commodity data center network architecture. ACM SIGCOMM Computer Communication Review, 2008, 38(4): 63−74 https://doi.org/10.1145/1402946.1402967
2	Greenberg A, Hamilton J, Jain N, Kandula S, Kim C, Lahiri P, Maltz D, Patel P, Sengupta S. VL2: a scalable and flexible data center network. ACM SIGCOMM Computer Communication Review, 2009, 39(4): 51−62 https://doi.org/10.1145/1594977.1592576
3	Guo D, Chen T, Li D, Li M, Liu Y, Chen G. Expandable and costeffective network structures for data centers using dual-port servers. IEEE Transactions on Computers, 2013, 62(7): 1303−1317 https://doi.org/10.1109/TC.2012.90
4	Shin J Y, Wong B, Sirer E G. Small-world datacenters. In: Proceedings of the 2nd ACM Symposium on Cloud Computing. 2011, <?Pub Caret?>2 https://doi.org/10.1145/2038916.2038918
5	Singla A, Hong C, Popa L, Godfrey P B. Jellyfish: networking data centers randomly. In: Proceedings of USENIX Symposium on Networked Systems Design and Implementation. 2012, 12: 17
6	Gyarmati L, Trinh T A. Scafida: a scale-free network inspired data center architecture. ACM SIGCOMM Computer Communication Review, 2010, 40(5): 4−12 https://doi.org/10.1145/1880153.1880155
7	Singla A, Godfrey P B, Kolla A. High throughput data center topology design. In: Proceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation. 2014, 29−41
8	Bhuyan L N, Agrawal D P. Generalized hypercube and hyperbus structures for a computer network. IEEE Transactions on Computers, 1984, 100(4): 323−333 https://doi.org/10.1109/TC.1984.1676437
9	Bollobás, B. Random Graphs. New York: Springer, 1998 https://doi.org/10.1007/978-1-4612-0619-4_7
10	Reitz F, Pohl M, Diehl S. Focused animation of dynamic compound graphs. In: Proceedings of the 13th IEEE International Conference on Information Visualisation. 2009, 679−684 https://doi.org/10.1109/iv.2009.24
11	Guo C, Wu H, Tan K, Shi L, Zhang Y. Lu, S. Dcell: a scalable and faulttolerant network structure for data centers. ACM SIGCOMM Computer Communication Review, 2008, 38(4): 75−86 https://doi.org/10.1145/1402946.1402968
12	Guo D, Chen H, He Y, Jin H, Chen C, Chen H, Shu Z, Huang, G. KCube: a novel architecture for interconnection networks. Information Processing Letters, 2010, 110(18): 821−825 https://doi.org/10.1016/j.ipl.2010.06.010
13	Guo D, Li C, Wu J, Zhou X. DCube: a family of high performance modular data centers using dual-Port servers. Elsevier Journal of Computer Communication, 2013, 53: 13−25 https://doi.org/10.1016/j.comcom.2014.07.003
14	Xie J, Guo D, Xu J, Luo L, Teng X. Efficient multicast routing on BCube-based data centers. KSII Transactions on Internet and Information Systems, 2014, 8(12): 4343−4355
15	Bondy J A, Murty U S R. Graph Theory with Applications. London: Macmillan, 1976 https://doi.org/10.1007/978-1-349-03521-2
16	Brélaz D. New methods to color the vertices of a graph. Communications of the ACM, 1979, 22(4): 251−256 https://doi.org/10.1145/359094.359101
17	Aljazzar H, Leue S. K∗: a heuristic search algorithm for finding the K shortest paths. Artificial Intelligence, 2011, 175(18): 2129−2154 https://doi.org/10.1016/j.artint.2011.07.003
18	Giannini E, Botta F, Borro P, Risso D, Romagnoli P, Fasoli A, Mele M R, Testa E, Mansi C, Savarino V. Platelet count/spleen diameter ratio: proposal and validation of a non-invasive parameter to predict the presence of oesophageal varices in patients with liver cirrhosis. Gut, 2003, 52(8): 1200−1205 https://doi.org/10.1136/gut.52.8.1200
19	Guo J, Liu F, Zeng D, Lui J, Jin, H. A cooperative game based allocation for sharing data center networks. In: Proceedings of IEEE International Conference on Computer Commnication. 2013, 2139−2147 https://doi.org/10.1109/infcom.2013.6567016
20	Guo J, Liu F, Huang X, Lui, J. On efficient bandwidth allocation for traffic variability in datacenters. In: Proceedings of IEEE International Conference on Computer Commnication. 2014, 1572−1580 https://doi.org/10.1109/infocom.2014.6848093
21	Misra J, Gries D. A constructive proof of Vizing’s theorem. Information Processing Letters, 1992, 41(3): 131−133 https://doi.org/10.1016/0020-0190(92)90041-S
22	Liu V, Halperin D, Krishnamurthy A, Thomas E A. F10: A faulttolerant engineered network. In: Proceedings of USENIX Symposium on Networked Systems Design and Implementation. 2013, 399−412
23	Chen K, Singla A, Singh A, Ramachandran K, Xu L, Zhang Y, Wen X, Chen Y. OSA: an optical switching architecture for data center networks with unprecedented flexibility. IEEE/ACMTransactions on Networking, 2014, 22(2): 498−511 https://doi.org/10.1109/TNET.2013.2253120
24	Guo C, Lu G, Li D, Wu H, Zhang X, Shi Y, Tian C, Zhang Y, Lu S. BCube: a high performance, server-centric network architecture for modular data centers. ACM SIGCOMM Computer Communication Review, 2009, 39(4): 63−74 https://doi.org/10.1145/1594977.1592577
25	Wu H, Lu G, Li D, Guo C, Zhang Y. MDCube: a high performance network structure for modular data center interconnection. In: Proceedings of the 5th ACM International Conference on Emerging Networking Experiments and Technologies. 2009, 25−36 https://doi.org/10.1145/1658939.1658943
26	Li D, Xu M, Zhao H, Fu X. Building mega data center from heterogeneous containers. In: Proceedings of the 19th IEEE International Conference on Network Protocols. 2011, 256−265 https://doi.org/10.1109/icnp.2011.6089059
27	Zhou X, Zhang Z, Zhu Y, Li Y, Kumar S, Vahdat A, Zhao B Y, Zheng, H. Mirror mirror on the ceiling: flexible wireless links for data centers. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 443−454 https://doi.org/10.1145/2377677.2377761
28	Hamedazimi N, Qazi Z, Gupta H, Vyas S, Samir R D, Jon P L, Himanshu S, Ashish T. FireFly: a reconfigurable wireless data center fabric using free-space optics. In: Proceedings of ACM Special Interest Group on Data Communication. 2014, 319−330 https://doi.org/10.1145/2740070.2626328

[1]

Supplementary Material-Highlights in 3-page ppt

Download

[1]	Xianpeng HUANGFU, Deke GUO, Honghui CHEN, Xueshan LUO. KMcube: the compound of Kautz digraph and M?bius cube[J]. Front Comput Sci, 2013, 7(2): 298-306.

Viewed

Full text

Abstract

Cited

Shared

Discussed