FSDC：灵活的高可扩展数据中心网络结构

doi:10.3778/j.issn.1673-9418.2010007

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (4): 855-864.DOI: 10.3778/j.issn.1673-9418.2010007

FSDC：灵活的高可扩展数据中心网络结构

余达明, 张震⁺()

暨南大学信息科学技术学院,广州 510632

收稿日期:2020-10-09 修回日期:2021-01-11 出版日期:2022-04-01 发布日期:2021-01-25
通讯作者: + E-mail: zzhang@jnu.edu.cn
作者简介:余达明（1992—）,男,广东珠海人,硕士研究生,主要研究方向为数据中心网络。
张震（1975—）,男,吉林长春人,博士,教授,硕士生导师,主要研究方向为互连网络、并行与分布式计算、代数图论等。
基金资助:
国家自然科学基金(61872165);广东省自然科学基金(2020A1515010619)

FSDC: Flexible and Highly Scalable Data Center Network Structure

YU Daming, ZHANG Zhen⁺()

College of Computer Science and Technology, Jinan University, Guangzhou 510632, China

Received:2020-10-09 Revised:2021-01-11 Online:2022-04-01 Published:2021-01-25
About author:YU Daming, born in 1992, M.S. candidate. His research interest is data center networks.
ZHANG Zhen, born in 1975, Ph.D., professor, M.S. supervisor. His research interests include interconnection network, parallel and distributed computing, algebraic graph theory, etc.
Supported by:
National Natural Science Foundation of China(61872165);Natural Science Foundation of Guangdong Province(2020A1515010619)

摘要/Abstract

摘要：

随着互联网络数据量的急速增长和在线服务的不断增加,数据中心的网络规模不断扩大。如何构建一个能灵活扩展,具有成本效益,同时在网络进行扩展时能保持其拓扑性质不变的数据中心网络结构,已成为一个颇具挑战性的问题。笛卡尔乘积图是一种具有高可扩展性的复合图,它由基础图构造而来,通过使用笛卡尔乘积图能更灵活地构建任何规模的网络结构。基于笛卡尔乘积图,提出一种新型的数据中心网络结构,称为FSDC。FSDC使用商用 $m$ 端口交换机和 $2$ 端口服务器构建而成。与其他的数据中心网络结构相比,FSDC具有更好的灵活性和可扩展性。FSDC可以使用不同的基础图构建相同度的笛卡尔乘积图,因此可以构造不同的FSDC结构,并可以通过使用相同类型的 $m$ 端口商品交换机来按不同的比例扩展。对FSDC的直径、对分带宽等拓扑性质进行了分析;基于节点间存在多条路径的性质,设计了一种容错路由算法。通过与其他数据中心网络结构进行对比分析和模拟实验,结果表明,FSDC具有良好的灵活性、可扩展性以及较好的成本能耗优势。

关键词: 数据中心网络, 灵活性, 可扩展性, 笛卡尔乘积图

Abstract:

With the rapid growth of interconnect network data volume and the continuous increase of online services, the scale of data center networks expands constantly. How to build a flexible expanded and cost-effective data center network structure, while maintaining its topological properties unchanged when the network is expanded, has become a challenging problem. Cartesian product graph, a type of compound graph with high scalability, is constructed by using base graphs. It can be used to more flexibly build any scale network architectures. Based on the Cartesian product graph, this paper proposes a new type of data center network structure called FSDC (flexible and highly scalable data center network), which is constructed using commercial m-port switches and 2-port servers. Compared with other data center network structures, FSDC has better flexibility and scalability. FSDC can use different basic graphs to construct Cartesian product graphs of the same degree, so different FSDC structures can be constructed, and can be expanded in different proportions by using the same type of m-port commodity switches. In addition, this paper analyzes the topological properties of FSDC, such as the diameter, the bisection bandwidth. Based on the property of multiple paths between nodes in Cartesian product graphs, a fault-tolerant routing algorithm is designed. Through comparative analysis and simulation experiments with other data center network structures, the results show that FSDC has good flexibility, scalability, and better cost and energy consumption advantages.

Key words: data center network, flexibility, scalability, Cartesian product graph

中图分类号:

TP393

余达明, 张震. FSDC：灵活的高可扩展数据中心网络结构[J]. 计算机科学与探索, 2022, 16(4): 855-864.

YU Daming, ZHANG Zhen. FSDC: Flexible and Highly Scalable Data Center Network Structure[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(4): 855-864.

图/表 10

表1 文中常用符号

Table 1 Denotations used in this paper

符号	含义
$m$	交换机的端口数
$k$	FSDC结构的层数
$n$	基础图的节点数
$t$	扩展图的节点数
$s$	服务器的序号

表1 文中常用符号

Table 1 Denotations used in this paper

符号	含义
$m$	交换机的端口数
$k$	FSDC结构的层数
$n$	基础图的节点数
$t$	扩展图的节点数
$s$	服务器的序号

图1 笛卡尔乘积图

Fig.1 Cartesian product graph

图2 FSDC2(3,4)结构

Fig.2 FSDC2(3,4)structure

图3 FSDC2(3,3)结构

Fig.3 FSDC2(3,3)structure

图4 FSDC3(3,4)结构

Fig.4 FSDC3(3,4)structure

表2 FSDC与其他数据中心网络结构的性质比较

Table 2 Characteristics comparison of FSDC with other data center network structures

拓扑性质	FatTree	BCube	DCell	FiConn	FSDC
扩展受限于服务器端口	否	是	是	否	否
扩展受限于交换机端口	是	否	否	否	是
灵活性	差	差	差	差	好
交换机数量	$5 N / m$	$lo g_{m} (N - 1) / m$	$N / m$	$N / m$	$N / m$
边数量	$3 N$	$N lo g_{m} N$	$\leq (1 + (lblo g_{m} N) / 2) N$	$1.5 N$	$1.5 N$
直径	$2 lb N$	$lo g_{m} N$	$\leq 2 lo g_{m} N - 1$	$\leq 2 lo g_{m} N - 1$	$t lo g_{t} N$
对分带宽	$N / 2$	$N / 2$	$\leq N (4 lo g_{m} N)$	$\leq N (4 lo g_{m} N)$	$\leq 3 N / 4$

表2 FSDC与其他数据中心网络结构的性质比较

Table 2 Characteristics comparison of FSDC with other data center network structures

拓扑性质	FatTree	BCube	DCell	FiConn	FSDC
扩展受限于服务器端口	否	是	是	否	否
扩展受限于交换机端口	是	否	否	否	是
灵活性	差	差	差	差	好
交换机数量	$5 N / m$	$lo g_{m} (N - 1) / m$	$N / m$	$N / m$	$N / m$
边数量	$3 N$	$N lo g_{m} N$	$\leq (1 + (lblo g_{m} N) / 2) N$	$1.5 N$	$1.5 N$
直径	$2 lb N$	$lo g_{m} N$	$\leq 2 lo g_{m} N - 1$	$\leq 2 lo g_{m} N - 1$	$t lo g_{t} N$
对分带宽	$N / 2$	$N / 2$	$\leq N (4 lo g_{m} N)$	$\leq N (4 lo g_{m} N)$	$\leq 3 N / 4$

表3 服务器数量的比较

Table 3 Comparison of the number of servers

交换机端口数	FatTree	FSDC(3,4)	FSDC(3,5)	FSDC(4,3)	FSDC(5,3)
8	128	1 536	3 000	864	1 080
12	432	24 576	75 000	7 776	9 720
16	1 024	393 216	1 875 000	69 984	87 480
24	3 456	100 663 296	1 171 875 000	5 668 704	7 085 880
32	8 192	25 769 803 776	732 421 875 000	459 165 024	573 956 280

图5 不同结构的吞吐量

Fig.5 Throughput of different structures

表4 设备价格与能耗

Table 4 Price and power consumption of devices

设备	型号	端口	价格/$	功耗/W
交换机	T1600G-18T	16	89	13.3
	T1600G-28T	24	128	20.4
	T1600G-52T	48	259	32.8
NIC	EXPI9402PT	2	47	7.0
NIC	EXPI9404PT	4	116	10.0

图6 成本、能耗和链路花费的对比

Fig.6 Comparison of cost, power, and links

参考文献 31

[1]	BARROSO L A HÖLZLE U. The datacenter as a com-puter: an introduction to the design of warehouse-scale machines[M]// Synbook Lectures on Computer Architec-ture. [S.l.]: Morgan & Claypool Publishers, 2009.
[2]	GHEMAWAT S, GOBIOFF H, LEUNG S T. The Google file system[C]// Proceedings of the 19th ACM Symposium on Operating Systems Principles, New York, Oct 19-22, 2003. New York: ACM, 2003: 29-43.
[3]	DEAN J, GHEMAWAT S. MapReduce: simplified data pro-cessing on large clusters[J]. Communications of the ACM, 2008, 51(1):107-113.
[4]	CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: a dis-tributed storage system for structured data[J]. ACM Transa-ctions on Computer Systems, 2008, 26(2):1-26.
[5]	ISARD M, BUDIU M, YU Y, et al. Dryad: distributed data-parallel programs from sequential building blocks[C]// Pro-ceedings of the 2nd ACM SIGOPS/EuroSys European Con-ference on Computer Systems, Lisbon, Mar 21-23, 2007. New York: ACM, 2007: 59-72.
[6]	DENG Y. What is the future of disk drives, death or rebirth[J]. ACM Computing Surveys, 2011, 43(3):1-27.
[7]	SINGH A, ONG J, AGARWAL A, et al. Jupiter rising: a de-cade of Clos topologies and centralized control in Google’s datacenter network[J]. ACM SIGCOMM Computer Communi-cation Review, 2015, 45(4):183-197.
[8]	WU K S, XIAO J, NI L M. Rethinking the architecture de-sign of data center networks[J]. Frontiers of Computer Sci-ence, 2012, 6(5):596-603.
[9]	BENSON T, AKELLA A, MALTZ D A. Network traffic char-acteristics of data centers in the wild[C]// Proceedings of the 10th ACM SIGCOMM Internet Measurement Conference, Melbourne, Nov 1-3, 2010. New York: ACM, 2010: 267-280.
[10]	AVIN C, SCHMID S. Toward demand-aware networking: a theory for self-adjusting networks[J]. ACM SIGCOMM Com-puter Communication Review, 2018, 48(5):31-40.
[11]	GREENBERG A G, HAMILTON J R, MALTZ D A, et al. The cost of a cloud: research problems in data center net-works[J]. ACM SIGCOMM Computer Communication Re-view, 2009, 39(1):68-73.
[12]	CHIARAVIGLIO L, D’ANDREAGIOVANNI F, LANCEL-LOTTI R, et al. An approach to balance maintenance costs and electricity consumption in cloud data centers[J]. IEEE Transactions on Sustainable Computing, 2018, 3(4):274-288. DOI URL
[13]	DAY K, AL-AYYOUB A E. The cross product of intercon-nection networks[J]. IEEE Transactions on Parallel and Dis-tributed Systems, 1997, 8(2):109-118.
[14]	PERES B S, DE OLIVEIRA SOUZA A O, GOUSSEVSK-AIA O, et al. Distributed self-adjusting tree networks[C]// Proceedings of the 2019 IEEE Conference on Computer Communications, Paris, Apr 29-May 2, 2019. Piscataway: IEEE, 2019: 145-153.
[15]	FOERSTER K T, SCHMID S. Survey of reconfigurable data center networks: enablers, algorithms, complexity[J]. ACM SIGACT News, 2019, 50(2):62-79. DOI URL
[16]	LU Y F, GU H X. Flexible and scalable optical intercon-nects for data centers: trends and challenges[J]. IEEE Communi-cations Magazine, 2019, 57(10):27-33.
[17]	AL-FARES M, LOUKISSAS A, VAHDAT A. A scalable, commodity data center network architecture[J]. ACM SIG-COMM Computer Communication Review, 2008, 38(4):63-74.
[18]	GREENBERG A G, HAMILTON J R, JAIN N, et al. VL2: a scalable and flexible data center network[C]// Procee-dings of the ACM SIGCOMM 2009 Conference on Appli-cations, Technologies, Architectures, and Protocols for Com-puter Communications, Barcelona, Aug 16-21, 2009. New York: ACM, 2009: 51-62.
[19]	NIRANJAN MYSORE R, PAMBORIS A, FARRINGTON N, et al. Portland: a scalable fault-tolerant layer 2 data center network fabric[C]// Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, Barcelona, Aug 16-21, 2009. New York: ACM, 2009: 39-50.
[20]	GUO C, WU H, TAN K, et al. Dcell: a scalable and fault-tolerant network structure for data centers[C]// Proceedings of the ACM SIGCOMM 2008 Conference on Data Commu-nication, Seattle, Aug 17-22, 2008. New York: ACM, 2008: 75-86.
[21]	GUO C, LU G, LI D, et al. BCube: a high performance, server-centric network architecture for modular data centers[C]// Proceedings of the ACM SIGCOMM 2009 Conference on Data Communication, Barcelona, Aug 16-21, 2009. New York: ACM, 2009: 63-74.
[22]	朱桂明, 谢向辉, 郭得科, 等. 一种高吞吐量、高可扩展数据中心网络结构[J]. 软件学报, 2014, 25(6):1339-1351.
	ZHU G M, XIE X H, GUO D K, et al. High performance expandable data center networking structure[J]. Journal of Software, 2014, 25(6):1339-1351.
[23]	LI D, GUO C X, WU H T, et al. FiConn: using backup port for server interconnection in data centers[C]// Proceedings of the 28th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, Rio de Janeiro, Apr 19-25, 2009. Piscataway: IEEE, 2009: 2276-2285.
[24]	ERICKSON A, STEWART I A, NAVARIDAS J, et al. The stellar transformation: from interconnection networks to data-center networks[J]. Computer Networks, 2017, 113:29-45. DOI URL
[25]	PARHAMI B. Introduction to parallel processing: algori-thms and architectures[M]. Berlin, Heidelberg: Springer, 2006.
[26]	XIE J J, DENG Y H. mtCloudSim: a flow-level network si-mulator for multi-tenant cloud[C]// Proceedings of the 22nd IEEE International Conference on Parallel and Distributed Systems, Wuhan, Dec 13-16, 2016. Washington: IEEE Com-puter Society, 2016: 332-339.
[27]	AL-FARES M, RADHAKRISHNAN S, RAGHAVAN B, et al. Hedera: dynamic flow scheduling for data center net-works[C]// Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation, Apr 28-30, 2010. New York: ACM, 2010: 281-296.
[28]	ALIZADEH M, GREENBERG A G, MALTZ D A, et al. Data center TCP (DCTCP)[C]// Proceedings of the ACM SIGCOMM 2010 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communica-tions, New Delhi, Aug 30-Sep 3, 2010. New York: ACM, 2010: 63-74.
[29]	WU C, BUYYA R. Cloud data centers and cost modeling: a complete guide to planning, designing and building a cloud data center[M]. San Francisco: Morgan Kaufmann, 2015.
[30]	ABTS D, MARTY M R, WELLS P M, et al. Energy pro-portional datacenter networks[C]// Proceedings of the 37th International Symposium on Computer Architecture, Saint-Malo, Jun 19-23, 2010. New York: ACM, 2010: 338-347.
[31]	HELLER B, SEETHARAMAN S, MAHADEVAN P, et al. Elastictree: saving energy in data center networks[C]// Proceedings of the 7th USENIX Conference on Networked Systems Design and Implementation, San Jose, Apr 28-30, 2010. New York: ACM, 2010: 249-264.

编辑推荐 0

Metrics

阅读次数

全文

350

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	9	97	0	244

来源	本网站	其他网站

次数	335	15
比例	96%	4%

摘要

397

最新录用	在线预览	正式出版

45	0	352

	来源	本网站

	次数	397
	比例	100%

FSDC：灵活的高可扩展数据中心网络结构

FSDC: Flexible and Highly Scalable Data Center Network Structure

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 31

相关文章 6

编辑推荐 0

Metrics

[1]	李宇珺，彭智勇，吴瑕，兰海，彭煜玮. IPI：灵活高效的对象代理数据库索引结构[J]. 计算机科学与探索, 2018, 12(8): 1191-1201.
[2]	余雅君，刘峥，徐明伟. 数据中心网络TCP Incast问题研究[J]. 计算机科学与探索, 2017, 11(9): 1361-1378.
[3]	罗红兵，张晓霞 . MPI集合通信性能可扩展性研究与分析[J]. 计算机科学与探索, 2017, 11(2): 252-261.
[4]	程彬，李大力，徐传福，刘巍，王光学，邓小刚. 面向高阶精度CFD的JFNK算法及其并行计算[J]. 计算机科学与探索, 2017, 11(1): 61-69.
[5]	蔡岳平，晏尧，周丽，刘军. 基于AWGR的光电混合数据中心网络架构设计[J]. 计算机科学与探索, 2014, 8(10): 1195-1205.
[6]	吕晨, 房俊, 韩燕波. 采用元组聚类的增量式数据分区方法[J]. 计算机科学与探索, 2011, 5(8): 719-729.