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

余达明，张 震

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

数据中心网络是云计算的基础，许多在线服务，如搜索、邮件、视频流以及基础设施服务，如GFS（Google file system）、Map-Reduce、BigTable等，都是通过数据中心网络为用户提供服务的。数据中心网络是由海量服务器、存储设备和网络设备构成的一个网络结构。这意味着，数据中心网络结构的设计对整个数据中心网络的性能起着重要作用。

根据服务器是否参与数据转发，数据中心网络结构可以划分为两类：以交换机为中心的互连结构和以服务器为中心的互连结构。典型的以交换机为中心的数据中心网络结构通常为层次型结构，并且能支持部署数以万计的服务器。与此相对，以服务器为中心的数据中心网络结构借助服务器的网络接口卡（network interface controller,NIC）完成数据转发。通过大量服务器NIC 之间的连接以及低端交换机的使用，避免了以交换机为中心方案的布线复杂和高昂的交换机成本。

近年来，随着数字化信息的普及，网络数据量呈现海量增长。为了处理这些海量增长的数据，许多大型数据中心被构建起来。这些大型数据中心中含有海量的硬件、软件和数据资源，可以动态为数百万用户提供服务。然而，随着网络数据量和用户数量的不断增加，数据中心需要不断扩展，例如：谷歌的数据中心的数据量大概每年翻一番。随着5G 网络在世界各地投入使用，全球范围内接入到互联网的终端设备将大大增加。因此，未来数据的增加速度将比以往更快。数据量的增长对数据中心网络的设计提出了更高的要求：

（1）高扩展性：为了应对快速增长的业务需求和数据量，数据中心网络需要不断地添加设备以提升整个网络的计算和储存能力，而在扩展过程中，当前网络的性能不会受到影响。

（2）高带宽：随着不同在线应用的出现，数据中心的流量特性也发生了巨大变化，从原来80%的外部用户与数据中心内部服务器之间交互的“南北”流量，变为80%的需要大量服务器协同完成工作的“东西”流量。高带宽是数据中心网络性能的重要指标。

（3）高容错率：设备和链路的故障会严重影响数据中心网络的性能。随着数据中心规模的不断变大，故障也会变得越发频繁。如何在故障条件下保持网络的整体性能也是设计网络结构的巨大挑战。

（4）成本效益：当前数据中心的花费主要由四部分组成，45%用于服务器（中央处理器、内存和存储系统），25%用于基础设施（电力调配和散热），15%用于能耗（电力成本），15%用于网络（链路、传输设备）。数据中心网络的设计必须在性能和成本之间取得平衡。

为此，本文提出了一种基于笛卡尔乘积图的新型数据中心网络结构FSDC（flexible and highly scalable data center network）。采用不同结构的基础图可以构建不同类型的笛卡尔乘积图。基于不同的笛卡尔乘积图，可以采用商用端口交换机和2 端口服务器构建不同类型的FSDC 数据中心网络结构。由于笛卡尔乘积图底层基础图的不同，FSDC 数据中心网络可以以不同的规模进行扩展，具有良好的灵活性和高可扩展性。

通过对FSDC 拓扑性质的分析、能耗对比分析以及吞吐量模拟实验，结果表明，与当前其他数据中心网络结构相比，FSDC 在性能和成本效益方面取得了良好的平衡。

1 相关工作

随着近年来大数据以及云计算的快速发展，学术界和工业界都对数据中心网络开展了许多研究工作。

考虑到传统三层结构的不足，Fares 等人提出了一种改进的三层结构，即FatTree。该结构可使用大量链路和小型交换机进行扩展，通过部署大量的冗余交换机和链路，FatTree 能实现1：1 的超额订购。VL2和Potland都是基于FatTree 的结构构建的，它们分别通过平面寻址和分层寻址提供“即插即用”的功能。然而，FatTree 的可扩展性受限于交换机端口数目，即，如果需要扩展FatTree，则必须更换高层的交换机以提供更多的交换机端口。随着层数的不断增加，FatTree的构建成本会不断升高。

DCell是一种递归定义的数据中心结构，DCell结构中的服务器具有多端口网卡。高层的DCell 通过一定数量的底层DCell 互相连接而构建。DCell 利用其分布式容错路由协议将流量均匀分散到不同链路当中，以实现高容错和高带宽。DCell 使用多端口服务器和复杂的布线来替代昂贵的核心交换机，而使用多端口的服务器会增加成本开销。

BCube利用服务器的多端口进行拓扑的连接。将数据中心硬件设备部署在集装箱中，减轻了BCube 布线的问题，最大化其链路资源丰富的优势，使得部署更加简单。当需要扩展时，只需互连若干个规模相同的集装箱即可。此外，BCube 使用多端口服务器互连多个交换机，并把路由线路的选择放置在服务器上。实验证明，BCube 能支持各种带宽密集型的应用程序，并且拥有良好的容错能力，但是大规模使用多端口服务器不可避免地会带来开销增加。

XDCent使用多端口的服务器进行数据中心网络结构的构建，并且与BCube 的连接模式非常相似。XDCent首先依照BCube的互连方式构建数据中心网络，直到各个服务器只剩余1 个端口。然后，利用各服务器剩余的端口，采用非完整复合图方式进行连接，确保了整个结构能持续扩展。

FiConn是一种以服务器为中心数据中心结构，采用2 端口的服务器和低端商用交换机构建。与DCell 相似，FiConn 也是通过递归方法构建的。与DCell 不同，FiConn 在递归扩展过程中会预留一部分服务器端口用于以后的扩展。也就是说，FiConn 的扩展过程不受交换机端口数和服务器端口数的限制。在FiConn 中，同一层但不同分区的部分进行通信时，只依赖于一条链路，导致对分带宽较低，吞吐量和容错性受到较大的影响。

不同于现有的结构，本文提出了一种全新数据中心网络结构FSDC，它拥有以下的特性：

（1）灵活扩展：FSDC 不仅拥有高扩展性，并且能根据现实需求来选择不同的扩展规模。

（2）成本效益：FSDC 具有较好的成本能耗优势。

（3）高容错性：FSDC 提供了一种高效的容错路由机制来应对数据中心可能出现的各种类型故障，保证了通信效率。

2 FSDC 网络架构

本章首先介绍笛卡尔乘积图的定义；随后给出FSDC 网络结构的构建方法，并且分析其拓扑特性；最后根据其拓扑特性设计出FSDC 结构的路由算法。表1 列出了本文中常用的一些符号。

表1 文中常用符号Table 1 Denotations used in this paper

2.1 乘积图的定义与性质

笛卡尔乘积图可以由两个无向图和构成，即=⊗，其具体定义如下：

笛卡尔乘积图=⊗中的节点与边的定义如下：

（1）节点定义：={(,)|∈,∈}。

（2）边定义:={(,)|=且(,)∈，或=且(,)∈}。

如图1 所示，乘积图由和构成，其中为四节点环图，为三节点环图。

图1 笛卡尔乘积图Fig.1 Cartesian product graph

根据定义1，可以推断出图的度数等于图和图度数之和。这表示，只要和的度数之和等于，就能灵活地构建具有相同度数的不同种类的笛卡尔乘积图。

2.2 FSDC 结构

FSDC 是一种基于笛卡尔乘积图，并通过递归的方式构建的数据中心网络结构，其中笛卡尔乘积图G=⊗⊗…⊗是由1 个和(-1)个通过笛卡尔乘积获得，这里被称为基础图，被称为扩展图。由笛卡尔积的定义可知，图G可以通过扩展图继续进行扩展，扩展形成的G的节点数量是G的倍，其中为扩展图节点数量。

选择节点数为的环图和-1 个节点数为的环图来构建一个笛卡尔乘积图G。利用台2 口服务器连接一个端口交换机组成FSDC 的基本单元，称之为。将G中的所有节点用替换，再通过服务器的备用端口连接不同的。最后，能够获得一个FSDC(,)结构。FSDC 的具体定义如下：

FSDC(,)结构中节点和边的定义：

（1）交换机和服务器分别定义为(x…;0)和(x…;)，其中1 ≤≤(-1),0 ≤x≤(-1),0 ≤≤(-1),1 ≤≤。

（2）在FSDC(,)中存在三种类型的边：

①交换机与服务器之间的边：

②第1 层的服务器与服务器之间的边：

③第层服务器与服务器之间的边：

其 中，+(-1)(-1)≤≤+(-1)-1,′=2(+-)--,′=(+x)mod。

图2 是FSDC 结构的一个示例，一个6 端口交换机连接6 个服务器形成一个，使用去替换图1 中的节点，进而得到一个(3,4) 结构。此外，通过不同的笛卡尔乘积图，采用相同类型的交换机可以构建出不同种类的FSDC 结构。如图3，使用了相同类型的6 端口交换机可以构建另一种FSDC结构(3,3)。

图2 FSDC2(3,4)结构Fig.2 FSDC2(3,4) structure

图3 FSDC2(3,3)结构Fig.3 FSDC2(3,3)structure

根据笛卡尔积的定义，图G可以通过扩展图进一步扩展形成G。基于G，FSDC 网络结构也可由层的FSDC(,)扩展为+1层的FSDC(,)。FSDC(,) 是由个FSDC(,)构成的。如图4 所示，(3,4)结构可进一步扩展为(3,4)结构。

图4 FSDC3(3,4)结构Fig.4 FSDC3(3,4)structure

在FSDC 中，每个服务器使用一个端口连接中的交换机，使用另一个端口来互联不同中的服务器。此外，服务器(x…;)由两部分组成，其中，(x…)表示服务器所在的序列号，表示中服务器的序列号。当∈[1,-1]时，当前服务器为第一层服务器，而当∈[+(-1)(-1),+(-1)-1]时，当前服务器为第(+1)层服务器。

根据定义1和定义2，可以推论出定理1和定理2。

在FSDC(,)中，交换机数量为×t，服务器数量为××t，边数量为3(××t)/2。

FSDC(,)中，的数量等于G的节点数，而一个包含1台交换机和台服务器。因此，交换机数量为×t，而服务器数量为××t。此外，因为FSDC(,)中所有服务器端口都占用，所以边的数量为3(××t)/2。

FSDC(,)中服务器数量为FSDC(,)中的服务器数量的倍，其中为的节点数量(≥2)。

由定理1 可得，FSDC(,)包含××t台服务器，而FSDC(,)包含××t台服务器。因此：

根据定理2，当FSDC 结构由-1 层扩展为层时，整个网络扩大了倍。

作为拓扑属性，直径可用于衡量互联网络中的通信时延，直径小意味着网络中通信延迟低。以()表示图的直径，其中图的直径为图中任意两顶点之间的最短距离的最大值。

由于FSDC(,) 中的服务器总数为=××t，FSDC(,)的直径为(logN)。这表示FSDC(,)结构的直径较小。

当互连网络的边数与带宽相等时，对分带宽可以定义为将网络的节点集合划分为两个相等子集合时所需移除边数的最小值。如果网络具有较大的对分带宽，则说明该网络具有更高的吞吐量和更好的容错性。对于数据中心网络而言，可以假设当前网络的边数与带宽相等，则通过将拓扑划分为两个大小相等的子结构，然后计算其中一个子结构的边数量，以此来表示当前网络的对分带宽。

FSDC(,)的对分带宽不大于3(××t)/4。

FSDC(,)的对分带宽可以分为以下三种条件讨论：

（1）是偶数

当为偶数时，FSDC(,)的拓扑为对称结构。通过移去第层一部分边来将FSDC(,)划分为两个大小相等子结构。因为FSDC(,)包含3(××t)/2条边，所以子结构的边数少于3(××t)/4。

（2）是奇数，是偶数

由图2 可知，当满足条件（2）时，FSDC(,)也是对称结构。因此，该结构也能划分为两个完全相等的子结构，但需要移除的边分布在第1 层到第层。故每个子结构的边数少于3(××t)/4。

（3）和都是奇数

如图3，当尝试使用条件（2）中描述的方法将网络分为两个相同部分时，其中一个结构会比另一个结构多一个。但是，随着网络规模的增长，可以逐渐忽略这个多余的，因为它在子结构中所占比例越来越少，即对结构的影响逐渐减少，所以可以把这两个子结构视为大小相等。因此子结构的边数少于3(××t)/4。

因为FSDC(,)中包含的服务器数量为=××t，所以其对分带宽为()。

容错路由算法可以绕过故障设备或链路，并快速到达目标节点。根据FSDC(,)的连接模式，当网络扩展到第层时，第层的服务器使用其备用端口互连不同的。针对FSDC，本文提出了一种容错路由算法，此路由算法主要利用笛卡尔乘积图中不同节点之间存在多条路径的性质。算法1 的路由原理是，对于任何一对不同位(x,y)(0 ≤≤-1),在第(+1)层的两个服务器之间存在一条边或路径，可以转换不同位为相同位。因此，源服务器到目标服务器的路径可以通过递归计算得到。

FSDC 容错路由算法

算法1描述了如何从源服务器发送数据到目标服务器的详细过程。首先，通过函数-()得到和之间不同位(x≠y)的数量（第1 行），如果等于0，则和在同一个，可以直接返回路径即可（第2 行）。否则，寻找一对不同位，并将该不同位的对所在的层次位置返回给（第3 行）。使用参数、x和y，可以得到一条第(+1)层的链路(,′),通过该链路可以将x转换为y（第4 行）。接下来，测试该链路的状态，若链路正常，则返回由(,)，(,′)，(′,)组成的完整路径（第5 行）；若链路失效，则寻找第(+1)层中其他的链路(,′),通过该链路可以将u转换为y。然后，构建一条中间路径(,′)来绕过当前失效的链路（第6～8 行）。最后，返回一条由(,)、(,′)、(′,)组成的路径。

当网络中不存在任何设备故障或链路失效的情况下，算法1 的路由路径会构建从源服务器和目标服务器之间的最短路径。例如，若图2 中网络设备和链路都正常，源服务器和目标服务器分别为[0,2;1]和[2,1;2]，则路由算法构建的最短路径如下：

当网络中存在设备故障或链路失效的情况时，容错路由算法会通过检测，绕过故障设备或链路，通过有效的链路建立从源服务器到目标服务器的一条非最优路径。例如，若图2 中源服务器和目标服务器分别为[0,2;1]和[2,1;2]，而[0,1;3]到[1,1;4]的链路失效。算法1 在到达服务器[0 ,1;3]，发现链路失效后，会即时选择一个中间服务器[0,1;4]绕过当前失效的链路，则整个路由路径为：

3 性能比较

本章将FSDC 与其他数据中心网络结构的性能进行对比，包括FatTree、BCube、DCell 和FiConn 等结构。分析比较的内容包括：网络拓扑性质、可扩展性、吞吐量、成本和能耗等。为了便于比较，假设所有数据中心结构包含相同数量的服务器，并且使用相同类型的端口交换机。

3.1 拓扑性质

网络拓扑性质对数据中心网络的性能有重大影响，如直径可以用于衡量网络中的通信时延，网络直径小代表当前网络中通信时延低。对分带宽可以衡量网络的吞吐量和容错性，较大的对分带宽意味着较高的网络吞吐量和更好的容错性。表2 列出了FatTree、BCube、DCell、FiConn 和FSDC 的主要拓扑性质，包括可扩展性、灵活性、直径、对分带宽、交换机数量和边的数量等。

由表2 可知，FatTree 的直径为2 乘以它的拓扑高度，即直径为2 lb。DCell 和FiConn 直径的准确值未知，但它们的上界都为2 logN-1。BCube 是所有结构中网络直径最小的，其直径为logN。而FSDC与DCell、FiConn 的直径相近，为logN。

表2 FSDC 与其他数据中心网络结构的性质比较Table 2 Characteristics comparison of FSDC with other data center network structures

FatTree和BCube的对分带宽都为/2，而DCell、FiConn 确切的对分带宽仍然未知，但它们的下界为/(4 logN) 。FSDC 的对分带宽的上界为3/4，其值与FatTree、BCube 相似，但大于DCell 和FiConn。

3.2 可扩展性

如表2 所示，BCube 和DCell 的扩展受限于所使用服务器的端口数。当数据中心需要扩展时，需要服务器增加更多的NIC 端口。因为每次扩展都预留了服务器端口，FiConn 的扩展性不会受限于交换机端口数和服务器端口数。FatTree 和FSDC 的扩展性则受限于交换机的端口数，这表示当交换机的端口数被使用完时，将无法添加设备到这些网络结构中。唯一的解决办法是把当前网络使用的交换机更换为端口数量更多的交换机。FatTree 结构能容纳的服务器数量过少，如使用196 端口交换机构建的FatTree，最多只能部署1 882 384 台服务器。表3 展示了FatTree 和FSDC 使用相同端口交换机所构建的网络能容纳的服务器数量，可以看到FSDC 的服务器数量远高于FatTree。此外，多端口交换机的价格会比较昂贵，如果大量使用来构建数据中心的话会使得成本非常高。因此，随着规模的不断扩大，FatTree的构建成本会急速增加。

大多数以服务器为中心的数据中心网络结构是通过递归式构建的，而这些结构会存在这样一个问题，即，每次扩展服务器的数量会出现海量的增加。例如，使用8 端口交换机构建一个DCell 网络结构，包含72 台服务器，包含5 256 台服务器，而的服务器数量为27 630 792。这种扩展方式不符合现实的需求，并且会带来大量的资源浪费。如定理2 所述，每次扩展过程中，FSDC 结构的服务器数量可以增加到原来的倍。这意味着，通过选择不同的参数，FSDC 可以具有更好的可扩展性。

3.3 灵活性

对于FatTree、FiConn、DCell 和BCube 等数据中心网络结构而言，当确定了构建数据中心网络结构的交换机类型之后，即交换机端口数确定之后，这些数据中心网络的结构就已经固定了，其构建灵活性较差。

基于笛卡尔乘积图的性质，可以通过选择不同的基础图和扩展图，使用相同类型的交换机来构造不同类型的FSDC 结构。如表3 所示，当使用16 端口交换机可以构建不同类型的FSDC 结构，这些FSDC结构具有不同的服务器数量，其扩展性也有很大的弹性空间。由此可见，FSDC 结构比其他数据中心网络结构具有更好的灵活性，更适合于构建大规模的数据中心网络。

表3 服务器数量的比较Table 3 Comparison of the number of servers

3.4 吞吐量

为比较不同结构的吞吐量，本文使用mtCloudSim模拟器进行流量模拟。mtCloudSim 是基于文献[27]提出来的方法，用于模拟现实中数据中心的数据流的转发过程。mtCloudSim 使用图来表示数据中心网络结构，其中链路对应结构中的边。根据文献[28]，机架之间不同服务器的往返时间（round-trip time，RTT）约为100 μs。因此可以把流的RTT 设置为从源主机到目标主机之间最短距离乘以100 μs。对于数据集，本文使用了文献[27]中的综合流工作负载，其中包含80 000个流，总大小为4 TB。最小的流为1 KB，最大的流为1 GB，主机范围从0 到4 096，且工作流的产生是随机生成的。

模拟实验构建了5 个不同的拓扑结构，分别为FatTree、BCube、DCell、FiConn 和FSDC。实验中设定不同结构的服务器数量约为5 000 台，链路的传输速率设置为2 Gbit/s。图5 展示了5 个数据中心结构的吞吐量变化与完成转发所需的时间。由于有大量的交换机和冗余链路，FatTree 和BCube 不仅实现了约为300 Gbit/s 的最高带宽，而且还最先完成了数据的传输。DCell 和FSDC 则在使用较少的交换机和链路情况下，实现了较好的吞吐量，约为280 Gbit/s。此外FSDC 的数据传输时长只比FatTree 和BCube 多10 s。FiConn的吞吐量只有250 Gbit/s，并且传输时长比其他结构多出几十秒。这与FiConn的连接模式，即不同部分之间只有一条链路互连，有很大的关系。当链路的带宽完全被占用时，传输被严重延迟。

图5 不同结构的吞吐量Fig.5 Throughput of different structures

3.5 成本与能耗

成本和能耗是建立数据中心网络需要考虑到的两个重要因素。为了全面分析这两个因素，本文构建了4 种不同规模的数据中心网络，其服务器数量分别为1 024、2 048、4 096 和8 192 台。

表4 中列举出在构建网络时所用到的交换机和NIC 设备的价格与能耗。因为网络规模相等且使用相同类型的服务器，所以可以忽略服务器的价格与能耗。尽管交换机和NIC 的价格随市场变动，但不同价格不会影响比较结果。

表4 设备价格与能耗Table 4 Price and power consumption of devices

如图6 所示，BCube 和DCell 的总成本和总能耗比其他的结构更高，这是因为它们的服务器需要装配具有多端口的NIC。FatTree使用了最多数量的交换机，因此其交换机成本比其他结构更大。而FiConn 和FSDC 则是这些结构中成本和能耗最低的。由于链路数量也是一个影响成本的重要因素，图6 也给出了不同结构的链路数量的变化。

从图6 可知，随着网络的不断扩展，FiConn 和FSDC 的成本、能耗和链路数量保持着较低的增长速度。而FSDC 具有比FiConn 更好的灵活性、可扩展性和吞吐量，因此FSDC 结构更适合于以低成本构建一个低能耗的数据中心网络。

图6 成本、能耗和链路花费的对比Fig.6 Comparison of cost,power,and links

4 结束语

本文提出了一种基于笛卡尔乘积图的新型数据中心网络结构FSDC。通过选择不同的基础图和扩展图，可以实现不同比例的灵活扩展。在分析了FSDC 的拓扑特性的前提下，提出一种基于笛卡尔乘积图性质的容错路由算法。最后通过与其他数据中心网络结构的对比和分析，说明了FSDC 在直径、对分带宽和扩展性方面具有良好的平衡。

FSDC 结构是通过两个环图之间的笛卡尔积所构建的数据中心网络结构。未来可以尝试用其他不同的图来构建笛卡尔乘积图，以此获得具有更好拓扑特性的数据中心网络。此外，除了以服务器为中心和以交换机为中心的方案外，如何使用笛卡尔乘积图构建其他类型的数据中心网络也是未来的工作之一。