随着IT建设成本和用户需求的增长, 越来越多的大型网络服务业, 如美国谷歌、微软、亚马逊等, 均利用规模经济的优势建立起百万级的云计算数据中心^[1].预计未来, 单个数据中心的规模将扩大到更高的量级.采用模块化的方式构建超大规模数据中心, 是当前的一个发展趋势.模块化网络的基本构建原理为:首先, 将一定规模的服务器按照特定拓扑结构互连并置入模块内(如集装箱), 形成基本的构建模块; 然后, 将大量这样的模块再进一步通过模块间的特定拓扑结构进行互连, 构造出更大规模的数据中心网络.由于模块化数据中心(modular data center, 简称MDC)的模块内、外结构可以分开设计, 因此极大地降低了超大规模数据中心构建和维护的复杂度.然而, 当前对于数据中心网络结构的研究主要集中在单个数据中心网络的大规模构造以及MDC的模块内互连结构, 而对于模块间应采用什么样的互连方式以支持超大规模数据中心构建的研究较少.

如何设计模块之间的互连结构是一个极具挑战性的课题, 原因主要有以下3点.

● 第一, 高带宽需求.数据中心需要支撑许多带宽密集型的应用, 如分布式文件系统^[2-4]、分布式执行引擎^{[5, 6]}以及一些在线数据密集型应用^[7], 这些典型应用往往需要在上千个模块中的成千上万台服务器上处理数据, 因此, 一个好的设计方案应确保在各种互连设置下模块间均具备较高的通信容量.

● 第二, 平缓的性能下降(graceful performance degradation).目前提出的数据中心网络普遍采用廉价的商业硬件搭建而成, 由于集装箱内的设备是工厂预制的, 空间和操作上的限制使其出现故障不易在线维护, 因此, 模块间互连网络的设计不仅应具有高容错特性, 还应确保网络设备出现故障时网络容量不会迅速下降.

● 第三, 灵活、可持续的扩展性.随着数据中心网络承载的数据量不断增长, 数据中心的规模持续扩大, 不可避免地需要对数据中心网络进行增量部署.因此, 不仅要求MDC网络具有可持续、可扩展能力, 还要尽量减少扩展过程中对已有结构的影响.

针对上述问题, 本文提出了一种适用于构建超大规模MDC的模块间互联结构MDKautz(modularized data center Kautz network).MDKautz借鉴MDCube^[8]结构的优点, 利用模块中各交换机预留的高速上行端口直接连接所有模块.所不同的是, MDKautz结构采用具有最优拓扑性质的常量度数网络结构Kautz图^[9]将模块互连, 实现模块内、外互连及路由解耦实现高带宽和高容错.MDKautz结构很好地解决了上述3个挑战:第一, 模块内外松耦合的互联设计和路由算法为模块之间提供了较高的聚合带宽; 第二, 多条模块间不相交平行多路径确保网络具有良好的容错能力; 第三, 采用增大网络的直径扩展网络以及增加单个模块中可用的10Gbps上行端口数扩展网络两种适用于不同应用场景的扩展方法, 突破了传统MDC网络的扩展性受限于模块内可用上行端口数的限制, 进一步满足构建大规模数据中心网络的需要.

本文第1节介绍相关工作.第2节介绍MDKautz网络的研究背景及后续分析中需要用到的重要结论.第3节详细阐述MDKautz结构的设计思路.第4节对MDKautz网络的静态性能与流量分布进行分析.第5节描述实验过程与结果分析.第6节对全文进行总结.

1 相关工作

作为数据中心与云计算的基础支撑技术, 数据中心网络成为近年来学术界研究的热点.目前提出的数据中心网络结构按照服务器是否参与转发, 大体可以分为两类:一类是以交换机为中心的结构, 另一类是以服务器为中心的结构.在以交换机为中心的结构中, 路由工作均由交换机完成, 因此, 交换机需要根据规模的扩展和应用需求不断升级.在以服务器为中心的结构中, 路由工作部分或全部由服务器承担, 交换机只提供简单的纵横式(cross-bar)交换功能.在这类结构中, 服务器往往通过多个网口接入网络, 而且存在大量冗余的网络链路和等价路由路径, 这些因素为更好地支持数据中心内各种流量模式提供了有利条件.

以交换机为中心的结构其设计思路有两种:一种是采用全新的结构取代传统树形结构, 另一种则是在原有树形结构的基础上增强其通信能力以提高二分带宽.二分带宽为将一个网络等分为两部分所需要切断的最小链路的带宽和^[10], 它直接关系到拓扑结构的吞吐能力, 二分带宽越大, 则网络容量越高, 对故障的容错能力越强. Fat-tree^[11]结构实际上同构于Clos网络^[12], 能够为网络提供1:1的带宽收敛比(oversubscription)^[11], 即服务器之间实现无阻塞(non-blocking)通信, 如图 1所示.PortLand^[13]和VL2^[14]都采用了普通商业交换机构建3层Fat-tree结构, 不同之处在于, VL2在Clos网络的高层使用了容量更高的10GbE交换机以减少布线复杂度.增强型树结构是在树形结构原有链路的基础上增加更快捷的链路如60G频段的无线链路^[15]或光互连^{[16, 17]}提高网络的局部通信能力, 因为对于百万级的大规模数据中心来说, 全带宽通信即服务器间能够以网卡的最大速率进行通信往往很难实现也并非必须的, 根据通信的局部性原则, 加强通信密集区域的连接能力能够缓解热点和拥塞, 从而提高网络整体吞吐量.

在以服务器为中心的结构中, 服务器提供多个网络端口用于互连并参与包转发.DCell^[18]是一个采用递归方式定义的多层网络结构.DCell中的每台服务器提供多个网络端口, 能够支持的服务器规模以接近2的指数次方扩展.DCell结构的不足之处是网络中的流量分布不均衡, 最底层网络承担了过多的流量, 极大地限制了网络的最大聚合带宽.此外, DCell的网络规模受限于服务器的网络端口数, 不具备良好的持续扩展能力.FiConn^[19]在DCell的基础上进一步将服务器的网络端口数固定为2, 提出服务器网络端口受限时的可扩展互连结构FiConn. FiConn与DCell采用相似的层次化方式构建, 但每层仅使用服务器上的备用网络端口来连接, 且无需增加服务器端的其他硬件成本.同时, 与DCell结构相比, FiConn结构极大地降低了配线成本, 但节约的链接数是以损失部分网络容量为代价的, 因此, FiConn结构的链路利用率较低.

BCube^[20]和SCautz^[21]是针对MDC设计的以服务器为中心的模块内互联结构.BCube结构中的服务器以Generalized hypercube^[22]进行组织, 具有多个网络端口的服务器连接到多个层次的小型交换机, 任意两个服务器之间没有直接连接.该结构的最大优势是链路资源非常丰富且流量分布较均衡, 如图 2所示.但BCube必须分配给每个服务器更多的NIC端口, 一般最多为4个, 因此, BCube网络规模的扩展也受限于服务器的网口数.SCautz结构通过服务器的网络端口和交换机的少量冗余端口将网络连接成一个Kautz图, SCautz具有丰富的并行路径, 能够很好地支持数据中心的多模式通信.但SCautz对服务器网络端口数的需求量较大, 从而其网络规模的扩展也受限于服务器的网口数.如, 构建一个规模仅为1280的网络需要每台服务器提供10个网络端口.

MDCube和uFix^[23]是针对MDC网络模块间互连设计的结构.uFix是针对异构集装箱容器互连提出的网络结构.它通过模块内服务器预留的网络端口, 将采用不同互连结构的模块连接成intensive mesh结构, 要求每个模块至少预留一定数量的服务器空闲端口进行模块之间的互连, 但模块间的连线个数取决于模块内预留的网络端口数量, 使得模块间的链路成为整个网络的带宽瓶颈, 从而限制了整个网络的性能和可靠性.与本文工作最接近的是MDCube结构, 如图 3所示.MDCube是一个多维的拓扑结构, 用于连接采用BCube构建的数据中心集装箱.它可以连接的数据中心集装箱的个数是所有维度上可容纳的集装箱数量的乘积.但是, MDCube是针对模块内结构BCube设计的模块间互连结构, 并通过模块内、外连接和路由的紧耦合实现高带宽和高容错.且MDCube的相邻模块间仅靠一对交换机的高速端口连接, 模块间可用的通信带宽有限且可靠性较差.同时, 其扩展性也受限于模块中可用的高速端口数.

2 研究背景

MDKautz对模块内的拓扑结构不做特殊要求, 广泛适用于各类新型结构, 只要模块内具有充足的10G上行带宽.本文以CH结构^[24]为例.CH结构是我们提出的一种常量度数的、以服务器为中心的新型互连结构, 由固定网络端口个数的服务器和廉价的商用交换机搭建.由于他具有良好的可扩展性、容错性和较高的网络容量, 且随着网络故障率的升高, 其性能下降非常平缓, 因此, 选择CH结构作为构建超大规模数据中心的模块内互连结构是合适且可行的.本节主要介绍CH结构及其拓扑特性并给出Kautz图的定义及相关结论.

2.1 CH结构

CH结构采用递归定义的层次设计, 其基本构件为具有固定网络端口的服务器和交换机.CH结构定义为C(n, m), 其中, n(n≥1) 表示服务器端口个数, m(m≥0) 表示CH结构的层次.C(n, 0) 由一台具有n个网络端口的服务器连接n台交换机构成; C(n, m)(m≥1) 由n^m台具有n个网口的服务器连接n个C(n, m-1) 构成.定义C(n, m)由编号为0~n-1的n个C(n, m-1) 组成, 每个C(n, m-1) 中包括n^m台交换机.则C(n, m)的构建方法为:将第m层中第i(i∈[0, n^m-1])台服务器的第j(j∈[0, n-1])个网口与第j个C(n, m)中的第i台交换机相连, 如图 4(a)所示.

CH网络中的节点(包括交换机和服务器)用唯一的m元组定义.服务器的编号定义为s_ms_m-1…s_i+1ns_i-1… s₁s₀(s_i∈[0, n], i∈[0, m]), 交换机的编号定义为x_mx_m-1…x_i…x₁x₀(x_i∈[0, n-1], i∈[0, m]).其中, n所在的位标识了服务器所在的层次.编号为s_ms_m-1…s_i+1ns_i-1…s₁s₀的服务器连接n台交换机, 这n台交换机的编号仅在第j维不同, 可表示为s_ms_m-1…s_i+1t_js_i-1…s₁s₀(t_j∈[0, n-1]).例如, 在n=2, k=3的C(2, 3) 结构中, 服务器2000连接2台交换机, 分别为0000和1000, 如图 4(b)所示.

CH结构具有以下几个已经被文献[22]证明的性质.需要特别说明的是, 本文中令服务器到交换机为1跳, 因此, CH的直径为原文中描述的2倍.

(1) CH结构的直径为2(m+1).

(2) CH结构中任意两台服务器之间有n条边不相交并行路径.

(3) CH结构的网络规模为N=(m+1)n^m, 交换机规模为n^m+1.

(4) CH结构的二分带宽为$ \left\{ {\begin{array}{*{20}{l}} {{n^{m + 1}}, \;\;\;\;\;\;\;\;n 为偶数 }\\ {{n^m}(n-1), {\rm{ }}n为奇数 } \end{array}} \right.. $

2.2 CH结构的其他性质

本节将论证CH结构的其他几个属性, 这些结论主要用于后续设计MDKautz结构模块间的路由算法和分析MDKautz结构的特性.

(1) CH结构中, 任意两台交换机间的最长最短路径为2(m+1).

证明:根据CH结构的编号规则, 编号差1位的任意两台交换机连接到同一台服务器, 则它们之间的最短路径为2.由于网络中交换机的编号最多差m+1位, 路由时通过逐位校正上一跳交换机编号中的一位建立一系列中间交换机, 因此, 交换机间的最长最短路径为2(m+1).

(2) CH结构中, 任意一台服务器与交换机之间的最长最短路径为2m+1.

证明:从上述证明过程中很容易得出该结论.

(3) CH结构中, 任意两台交换机之间有m+1条边不相交并行路径.

证明:已知CH结构中任意两台服务器之间有m+1条边不相交并行路径, 根据CHRouting路由算法, 分别连接到任意两台服务器的两台交换机之间也有m+1条边不相交并行路径, 得证.

(4) CH结构中, 任意一台服务器与交换机之间有m+1条边不相交并行路径.

证明:同上.

2.3 Kautz图

Kautz图由于其良好的特性被广泛应用于并行计算和P2P网络^[25]中, 因此, 本文基于Kautz图设计MDKautz结构.Kautz图记为K(d, k), 其中, d(d≥1) 表示节点出/入度, k(k≥1) 表示直径.图 5所示为度和直径均为2的Kautz图.Kautz图的节点集记为V={x_k…x_i…x₁|x_i∈[0, d], i∈[1, k]}, 对K(d, k)中每个标识为x_k…x_i…x₁的节点V都有d条出边, 即对任意α∈{0, 1, 2, …, d}-{x₁}, 节点V都有一条到节点V'={x_k-1…x_i…x₁α}的出边.

Kautz图具有如下已被证明的性质.

(1) K(d, k)的出、入度均为d.

(2) K(d, k)的节点规模为d^k+d^k-1, 边的数量为d(d^k+d^k-1).

(3) K(d, k)的二分宽度为$ \frac{{(d + 1){d^k}}}{{2k}}. $

3 MDKautz结构

MDKautz采用CH结构作为模块内互连结构, 并采用常量度数的网络结构Kautz图作为模块间的互连结构以支持超大规模数据中心.然而, 将数据中心网络中的数百个模块连接起来, 不仅需要设计合适的网络结构, 还要设计合理的连接方式和路由策略.首先, MDC网络将模块看作黑盒以适应各类模块内互连结构, 因此, 要求模块间的互连和路由与模块内部无关; 其次, 应确保模块内部能够提供足够的空闲端口用于更大规模的网络互连, 即提供可持续扩展能力; 再次, 模块之间应该有足够的链路, 以提高网络的容量和可靠性; 最后, 应合理分配模块提供的端口, 尽量使端口的使用率较为平均, 确保当通信的源端和目的端过于密集的情况下, 流量能够被分流至不同的端口上, 从而达到均衡流量、减少热点的目的.从本节开始, 将逐一解决上述问题.

3.1 构建方法

MDKautz利用模块内大量未被使用的交换机预留的高速端口、采用Kautz图将CH网络互连起来. MDKautz网络中, 交换机仅作为交叉结构连接模块内部和模块之间的服务器, 因此, MDKautz是以服务器为中心的网络结构.每个交换机提供1个高速端口作为CH模块对外连接的端口, 因此, 模块内交换机的数量即为该模块对外提供的端口的数量.根据CH结构的性质(3) 和Kautz图的性质(1) 得出$ d = \frac{1}{2}{n^{m + 1}} $, 故将MDKautz网络记为M(n, m, k).

在MDKautz网络中有两种类型的链路, 即, 模块内交换机与服务器之间互连的本地普通链路和模块间交换机之间互连的远程高速链路, 因此, 每个交换机由其所属CH模块的ID及其在模块中的ID共同标识, 即交换机节点(x, y)表示为{(x, y)|x=x_k…x_i…x₁, y=y_m…y_j…y₀, i∈[1, k], j∈[0, m]}, 其中, x表示CH模块的ID, y表示交换机在CH网络中的ID.M(n, m, k)中, 远程链路的起点和终点分别连接到不同CH模块内相应的交换机节点对上, 连接规则为:首先, 将CH模块中的所有参与互连的交换机节点随机划分成数量相等的两部分, 分别作为远程链路的出、入节点, 并将他们的ID分别按升序排列; 然后, 对远程出、入链路分别进行排序, 根据Kautz图的定义, 将模块x_k… x_i…x₁到模块x_k-1…x_i…x₁α的远程出链路定义为第i条出链路, 其中, $ i = \left\{ {\begin{array}{*{20}{l}} {(\alpha-{x_k} + d + 1)\bmod (d + 1), {\rm{ }}{x_k} \ne {x_1}}\\ {(\alpha-{x_k} + d)\bmod (d + 1), {\rm{\;\;\;}}{x_k} = {x_1}} \end{array}} \right. $, 模块x_k…x_i…x₁的第i条出链路也是相应模块x_k…x_i…x₁α的第i条入链路, 因此, 每个模块的$ \frac{1}{2}{n^{m + 1}} $条出链路和入链路也可以分别按升序排列; 最后, 将任意模块的第i条出链路替换为两个模块间的远程连接, 即一个模块的第i个出节点到相应模块的第i个入节点之间的远程连接.

MDKautz的构建算法如算法1所示.

算法1. BuildMDKautz(x, x', swid_out, swid_in).

输入:节点x=x_kx_k-1…x_i…x₁, 数组swid_out[d]和swid_in[d]分别存放按升序排列的输出、输入交换机节点编号.

输出:MDKautz拓扑.

1. for (i=0; i≤d^k+d^k-1; i++)

2.   visitedcid=0;      //设置所有模块未访问

3. cid₁=x_kx_k-1…x_i…x₁;

4. EnQueue(Q, cid₁);

5. While (!QueueEmpty(Q))

6.   DeQueue(Q, cid₁);

7.   if (!visited cid₁        //cid₁未访问

8.    visited cid₁=1;        //设置当前模块访问过

9.    for (i=0; i≤d; i++)

10.       if (i≠x_k)

11.       cid₂=cid₁左移一位最右补i;

12.      if (!visited cid₂)        //cid₂未访问

13.         EnQueue(Q, cid₂);

14.       if (x_k≠x₁)

15.          j=(i-x_k+d+1) mod (d+1);         //cid₁的第j条出边

16.      else

17.         j=(i-x_k+d) mod (d+1);        //cid₁的第j条出边

18.       swid₁=swid_out[j];          //cid₁的第j个输出交换机

19.      swid₂=swid_in[j];          //cid₂的第j个输入交换机

20.      connect (cid₁, swid₁) and (cid₂, swid₂);

21. return;

以图 6为例, 实线和虚线分别表示每个模块的第0条和第1条出边, 对于模块21而言, 它到12之间的远程出链路为第0条出链路, 则交换机节点(21, 00) 为模块21的第0个出交换机, 交换机节点(12, 01) 为模块12的第0个入交换机; 模块21到10之间的远程出链路为第1条出链路, 则交换机节点(21, 11) 为模块21的第1个出交换机, 交换机节点(10, 10) 为模块10的第1个入交换机.

3.2 单路径路由

根据M(n, m, k)结构的构建规则, 建立分级路由策略, 即模块内部路由采用CH结构的路由算法, 模块间的路由采用Kautz图的最短路径路由算法, 从而得到M(n, m, k)结构的单路径路由算法, 如算法2所示.

算法2. MDKautzRouting(src, dst).

输入:源节点src=x_kx_k-1…x₁, 目的节点dst=y_ky_k-1…y₁, 二者均定义为{cid, sid};

输出:路径path.

1. c1=src; c2=dst; path=()

2. pref=CommSuffixPreffix(c1.cid, c2.cid);         //c1的后缀与c2的前缀的共同部分

3. l=Length(pref);

4. if (l==k)       //源节点和目的节点在一个模块内

5.    path=CHRouting(c1, c2);        //CH单路径路由算法

6. else

7.  for (i=0; i < k-l; i++)

8.     c2.cid=c1.cid左移一位最右补y_k-l-i;

9.    (sw₁, sw₂)=GetLink(c1.cid, c2.cid);          //连接两个模块的交换机对

10.    path1=CHRouting(c1, sw₁);         //CH中服务器与交换机之间的路由

11.    path=path+path1+(sw₁, sw₂);

12.    c1=c2;

13. if (c2.cid=dst.cid)       //同属于一个模块

14.   path1=CHRouting(c2, dst);

15.   path=path+path1;

16. return path;

函数GetLink返回算法1定义的连接到两个不同模块c1.cid和c2.cid的交换机对, 具体路由方法通过c1.cid的第i个出节点到c2.cid的第i个入节点之间的链路实现, 其中, $ i = \left\{ {\begin{array}{*{20}{l}} {(\alpha-{x_k} + d + 1)\bmod (d + 1), {\rm{ }}{x_k} \ne {x_1}}\\ {(\alpha-{x_k} + d)\bmod (d + 1), {\rm{\;\;\;}}{x_k} = {x_1}} \end{array}} \right. $.模块内服务器间或交换机间的路由采用CH结构的路由算法, 尽管CH结构仅定义了服务器之间的路由算法, 交换机之间的路由仍可以通过与其直接相连的服务器采用相同的算法实现.

仍以图 6为例, 假设源节点src=(21, 21), 目的节点des=(20, 02).源节点所在模块ID src.cid=21, 目的节点所在模块ID des.cid=20, 共同前/后缀长度为0, 因此, 二者不在同一模块内, 得出源节点的下一跳模块为tmp.cid=12, 计算出连接两个模块的交换机对为(21, 00) 和(12, 01), 从而得出路由路径为

path={(21, 21), (21, 00), (12, 01), (12, 11), (20, 10), (20, 02)}.

3.3 平行多径路由

当网络流量均衡时, 单路径路由能够满足通信的需要.但数据中心的流量往往并不均衡, 常常伴随突发流量.在突发流量模式下, 由于单路径路由算法总是选择最短路径可能导致低效的网络带宽, 从而降低数据中心网络的性能.因此, 我们通过设计并行多径路由平衡模块间流量, 加速端到端的传输, 提高路由的容错能力, 从而使整个网络达到高吞吐量.

定理1. MDKautz网络中, 任意两台服务器之间存在d条中间模块不相交路径, 中间模块不相交路径指一条路径上的中间模块不重复出现在另一条路径上.

证明:设源服务器所在模块的ID为a=a_ka_k-1…a_l+1a_l…a₁, 目的服务器所在模块的ID为b=b_kb_k-1… b_k-l+1b_k-l…b₁, 他们ID重叠部分的长度为l.要证明从源服务器到目的服务器之间存在d条中间模块不相交路径, 只需证明从a到b存在d条中间模块不相交路径.根据Kautz图的定义, 节点a有d条出边, 则a有d个不相同的下一跳节点, 从这些节点到b可生成d条路径.若从a到b的一条路径a=a_k…a_l+1a_l…a₁→a_k-1…a_l+1a_l… a₁b_k-l→…→a_l…a₁b_k-l…b₁=b用〈a_k…a_l+1a_l…a₁b_k-l…b₁〉表示, 则这d条路径可以表示为以下3种形式.

Ⅰ. 〈a_k…a_l+1a_l…a₁b_k-l…b₁〉;

Ⅱ. 〈a_k…a_l+1a_l…a₁αb_k-l…b₁〉;

Ⅲ. 〈a_k…a_l+1a_l…a₁βχb_k-l…b₁〉,

其中, a≠β≠χ∩α≠a₁∩α≠b_k∩α≠b_k-l∩β≠a₁∩χ≠b_k∩χ≠b_k-l∩χ≠a_l+1.

下面证明这d条路径为边不相交路径.因为α≠β≠b_k-l, 所以这3条路径从节点a出发的下一跳节点均不相同; 同理, 节点b的上一跳节点也都不相同.令n_Ⅰ, n_Ⅱ, n_Ⅲ分别为路径Ⅰ~路径Ⅲ上的任意一个中间节点, 则有:

$ \begin{array}{l} {n_{\rm{I}}} = {a_z}...{a_{l + 1}}{a_l}...{a_1}{b_{k-l}}...{b_{z-l + 1}}, \\ {n_{\rm{II}}} = {a_m}...{a_{l + 1}}{a_l}...{a_1}\alpha {b_{k-l}}...{b_{m - l + 2}}, \\ {n_{\rm{III}}} = {a_p}...{a_{l + 1}}{a_l}...{a_1}\beta \chi {b_{k - l}}...{b_{p - l + 3}}, \end{array} $

其中, z, m, p∈[1, k].

假设路径Ⅰ和路径Ⅱ不是边不相交的, 那么n_Ⅰ=n_Ⅱ, 得出a_z=a_m∩a₁=a₂∩α=a₁, 与原结论矛盾.因此, 路径Ⅰ和路径Ⅱ是边不相交的.同理可以证明路径Ⅰ和路径Ⅲ、路径Ⅱ和路径Ⅲ都是边不相交的, 原命题得证.

注意到, 定理1中描述的中间模块不相交路径并非真正的边不相交(edge-disjoint)路径, 即一条路径上的中间节点(服务器和交换机)不重复出现在另一条路径上.因为源模块中从服务器到d条输出交换机的路径上节点一定有重复, 目的模块中, 从d条输入交换机到服务器的路径上节点也有重复, 因此, 源模块和目的模块有可能成为整个网络流量的瓶颈, 在第4.2节中有详细论证.

算法3描述了构造d条模块不相交路径的过程.该算法生成的路径最多经过k+1个中间不相交模块, 仅比最短路径算法多经过2个模块.

算法3. MDisjointRouting(src, dst).

输入:源节点src, 目的节点dst, 二者均定义为{cid, sid}.

输出:路径集pathSet.

1. c1=src; c2=dst; path={}; counter=0;

2. pref=CommSuffixPreffix(c1.cid, c2.cid);

3. l=Length(pref);

4. if (l==k)

5. pathSet=CHParallelRouting(c1, c2);        //CH平行多径路由算法

6. else

7. P₁=MDKautzRouting(src, dst);

8.  add P₁ to pathSet;         //一条长度不大于k的最短路径

9. for (i=0; i≤d; i++)        //counter条长度为k+1的路径

10. if (i≠x₁ & & i≠y_k & & i≠x_l+1 & & i≠y_k-l)

11. out_src.cid=c1.cid左移一位最右补i;

12. in_dst.cid=c2.cid右移一位最左补i;

13.    if (out_src.cid≠uout_src.cid & & in_dst.cid≠uin_dst.cid)

14. P₂=MDKautzRouting(src, out_src)+MDKautzRouting(out_src, in_dst)+MDKautzRouting(in_dst, dst);

15. add P₂ to pathSet;

16. out_src.cid=uout_src.cid;

17. uin_dst.cid=in_dst.cid;

18. counter++;

19.   if (counter+1≠d)          //(d-counter-1) 条长度为k+2的路径

20. for (i=0; i≤d; i++)

21. for (j=0; j≤d; j++)

22. if (i≠j & & i≠x₁ & & j≠y_k & & i≠y_k-l & & j≠x_l+1)

23. out_src.cid=c1.cid左移一位最右补i;

24. in_dst.cid=c2.cid右移一位最左补j;

25. if (out_src.cid≠uout_src.cid & & in_dst.cid≠uin_dst.cid)

26.   P₃=MDKautzRouting(src, out_src)+MDKautzRouting(out_src, in_dst)+MDKautzRouting(in_dst, dst);

27. add P₃ to pathSet;

28. uout_src.cid=out_src.cid;

29. uin_dst.cid=in_dst.cid;

30. return pathSet;

3.4 容错路由

单路径路由策略无法应对路由过程中节点和链路出现故障的情况, 容错路由算法则能够在处理链路故障的同时, 有效利用网络中的并行路径获得高聚合吞吐量.利用MDKautz结构具有多条模块不相交路径的特性, 设计了一种分级的容错路由算法, 将模块内和模块间的路由解耦, 模块内由CH容错路由算法维护, 利用CH容错路由算法处理模块内部的路由失效; 模块之间的路由路径由源节点决定, 利用MDKautz平行多径路由算法处理模块间的路由失效并均衡整个网络的流量.

该容错路由算法采用松散源路由的方式实现, 如算法4所示.其基本思想是:源节点在并行路径中任选一条作为路由路径, 并将经过的中间模块的ID存储到数据包头中.中间节点不参与路由选择, 只基于包头中的ID转发相应的数据包, 并判断下一跳是否可达.如果模块间的链路或连接模块的交换机节点失效, 则向源节点发送路由错误消息, 源节点收到消息后, 利用算法3重新选择一条并行路径, 算法3中的模块不相交并行路径恰好能够确保新选择的路径不经过失效链路.模块内部失效的节点或链路直接由CH容错路由算法处理, 而无需通知源节点.

算法4. MDFTRouting(src, dst).

输入:源节点src=x_kx_k-1…x₁, 目的节点dst=y_ky_k-1…y₁, 二者均定义为{cid, sid}.

输出:路径SelectPath.

源节点:

when a pkt arrives:

1.   SelectPath={};

2.   pathSet=MDisjointRouting(src, dst);

3.    path=pathSet.remove();        //任意选择一条路由路径

4.    SelectPath.add(path);

5. when a path failure msg received:

6.    path=BFS(pathSet, SelectPath);    //宽度优先搜索另一条并行路径

7.    if (path exists)

8.      SelectPath.add(path);

9.   else

10.     return error;

11.  return SelectPath(path);

中间节点:

when a pkt is received:

1.    if (next hop is not available)

2.     Send path failure msg to src;

3.    return;

4.   Forward(pkt);

注意到, 模块内的路由完全由CH的容错路由算法决定, 因此, 如果有多个数据流经过同一个模块, 不对流加以标识则可能产生包乱序; 再者, 模块间的链路可能被多个数据流占用, 也可能发生包乱序.因此, 我们在源节点中用flow_id标识数据包, 后续的路径选择则基于源、目的节点ID和flow_id这3个参数进行.

3.5 扩展性分析

MDKautz网络模块间的互连结构为Kautz图, 利用Kautz图的特性, 如果将构成MDKautz网络的每个模块看作一个虚拟节点, 则MDKautz网络具备两种适用于不同应用场景的扩展方式.

● 第1种扩展方式通过固定单个模块的度数d, 增大网络的直径k扩展网络.

这种扩展方式利用Kautz图能够不改变节点度数进行扩展的特性, 使网络具备无限可持续扩展的能力.但这种扩展方式的不足之处在于其渐进扩展的粒度较大, 如果用Δ表示每次扩展至少需要增加的模块个数, 则Δ=d^k+1+d^k-(d^k+d^k-1).当d较大时, D≈d^k+1, 即随着k的增加, 其渐进扩展的粒度呈指数增长, 且增大网络直径将导致节点编号和互连关系的改变, 而重新部署网络将影响到数据中心的各类应用.针对这种情况, 我们可以利用非正则Kautz图Quasi-Kautz结构^[23]构建具有任意规模和常量度数的不完全Kautz图, 使网络具备渐进扩展的能力, 且仅需要少量地调整现有网络结构, 具体实现可参考文献[23], 本文不再赘述.

● 第2种扩展方式通过固定网络的直径k, 增加单个模块的度数d扩展网络.

这种扩展方法利用Kautz图的另一个特性, 即K(d, k)是K(d+1, k)的导出子图^[24], 可以在不改变已有节点编号和互连关系的情况下扩展原网络结构, 以满足数据中心网络的无损扩展需求.通常, 数据中心网络的构建过程并非一蹴而就, 初始构建网络时往往不需要连接很大规模的集装箱模块, 因此可选择模块内部分可用的高速上行端口将一定数量的模块互连起来, 空闲的那部分高速端口即可用于支持后续扩展.目前, 数据中心单个集装箱容器内的服务器数量为1K~4K^{[1, 8]}, 对于CH结构, 当网络规模为1 024时, 其交换机数量为256, MDKautz网络至少能够支持约16 908 288个集装箱互连; 对于BCube结构, 当网络规模为2 304时, 其交换机数量为96, MDKautz网络至少能够支持约5 419 008个集装箱互连.在网络建设初期, 可根据实际需要确定k值, 通过增加d实现对网络的持续扩展, 因此, 采用此扩展方法完全能够满足当前一段较长时期内的实际需求, 即能够满足数据中心网络的实际可持续扩展需求.但这种扩展方式同样存在渐进扩展粒度较大的问题, 仍然用Δ表示每次扩展至少需要增加的模块个数, 则Δ=(d+1)^k+(d+1)^k-1-(d^k+d^k-1), 当k取2时, Δ=4d+2, 即随着模块度数的增加, 其渐进扩展的粒度呈线性增长.针对这种情况, 我们仍可以在扩展时采用非正则Quasi-Kautz结构构建不完全MDKautz网络, 通过少量调整现有网络结构实现对模块的渐进部署.

综上所述, 两种扩展方法各有利弊, 部署时, 可根据实际需要选择不同的扩展策略.当模块内没有多余可用上行端口时, 可采用第1种方法扩展网络; 第2种扩展方法则更适用于模块内尚有足够可用的上行端口的情况.

4 性能评估 4.1 MDKautz的静态性能

本节主要分析MDKautz的静态性能, 包括网络规模、直径和二分宽度.数据中心网络的规模表示他所支持的服务器数量的最大值, 反映了网络的扩展性; 数据中心网络的直径表示网络中任意两台服务器之间最短路径的最大值, 直径越短, 网络中点对点延迟就越小, 节点间的数据交换也越便捷; 而二分宽度是衡量数据中心网络带宽利用率的重要指标, 二分宽度越大网络容量越高, 对故障的容错能力越强.

定理2. M(n, m, k)的网络规模为$ \frac{{(m + 1){n^{k(m + 1)-1}}}}{{{2^k}}}({n^{m + 1}} + 2). $

证明:由M(n, m, k)的定义可得, CH模块总数为d^k+d^k-1, 每个模块包含的服务器个数为n^m(m+1), 且$ d = \frac{1}{2}{n^{m + 1}} $.因此, 网络规模为${n^m}(m + 1) \times ({d^k} + {d^{k-1}}) = \frac{{(m + 1){n^{k(m + 1)-1}}}}{{{2^k}}}({n^{m + 1}} + 2). $

分别给定MDKautz的模块内结构参数n=2, m=7, MDCube的模块内结构参数n=32, m=1, 使得两个网络中单个模块的规模相同.图 7比较了两种网络的模块个数随相应参数的变化情况.不难看出, MDKautz能够支持的模块个数随k的增加呈指数增长, 其规模的扩展不受限制; 而MDCube支持的模块, 其增长率随维度的增加而降低, 说明MDCube的规模受模块内可用上行端口的限制.相比之下, MDKautz更具有规模和可持续扩展优势.

一般情况下, 当k=2时, 即可支持规模逾百万甚至千万的超大规模数据中心.例如, 由C(2, 7) 构建的M(2, 7, 2) 网络中, 单个模块的规模为1 024, 共16 512个模块, 则总网络规模为16 908 288.

定理3. M(n, m, k)网络的直径为2m(k+1)+3k.

证明:由Kautz图的定义可知:在M(n, m, k)网络中, 任意两台服务器节点之间最多经过包括源、目的模块在内的k+1个模块, 因此, 模块间的远程链路最多有k条.根据第2.2节的属性(1) 和属性(2) 可得:源模块中, 源服务器节点与任意交换机节点之间的最长最短路径为2m+1;中间模块中, 任意交换机节点之间的最长最短路径为2(m+1);目的模块中, 任意交换机节点与目的服务器节点之间的最长最短路径为2m+1.因此, 任意两台服务器之间的最长最短路径即直径为2(2m+1)+2(m+1)(k-1)+k=2m(k+1)+3k.

由于MDKautz的模块内结构CH的直径大于BCube, 为了更公平地对比模块间的互联结构, 同样采用BCube作为MDKautz的模块内结构, 给定BCube的参数为n=32, k=1, 图 8给出了其直径随网络规模变化的情况.可以看出, MDKautz的直径的增长率小于MDCube, 当网络规模超过百万后, MDKautz的直径更优.当k=2时, 由C(2, 7) 构建的MDKautz网络的最长最短路径为54.实际通信过程中, 服务器间的路径长度是小于这个上限值的, 因为网络中任意两台服务器间都有多条并行路径, 采用最短路径路由算法极大地降低了走最长路径的概率.

定理4. M(n, m, k)网络的二分宽度为$\frac{{{n^{k(m + 1)}}}}{{k{2^{k + 1}}}}\left( {\frac{1}{2}{n^{m + 1}} + 1} \right) $.

证明:由Kautz图的性质3和$ d = \frac{1}{2}{n^{m + 1}} $, 容易得证.

在便于分析, 同时不影响分析结论的前提下, 假设MDCube在各维度上互连的模块数量相等, 则其二分宽度可以表示为$\left\{ {\begin{array}{*{20}{l}} {\frac{{{N^2}-1}}{4}{N^{D-1}}, {\rm{ }}N为奇数}\\ {\frac{{{N^2}}}{4}(1 + {N^{D-1}}), {\rm{ }}N为偶数} \end{array}} \right. $, 其中, $ N = \frac{{{n^m}(m + 1)}}{D} + 1 $表示每个维度包含的模块个数.

图 9给出了单个模块的规模相同时, 两种结构的二分宽度随网络规模的变化情况.可以看出, 两种结构的二分宽度均随网络规模的增大而增大, MDKautz的二分宽度明显优于MDCube.

4.2 流量分布与ABT

All-to-All通信模式广泛应用于MapReduce等应用中.ABT(aggregate bottleneck throughput)是数据中心网络中衡量all-to-all通信的一个评价指标, 表示网络内各数据流获得的最小带宽与网络内所有数据流总和的乘积, 反映了数据中心网络在all-to-all通信模式下的网络容量.ABT较大, 也意味着all-to-all通信的时长更短.在all-to-all通信模式下, 数据中心网络中的流量由模块内数据流和模块间数据流两部分组成, 模块内数据流指每台服务器与同一模块内的其他所有服务器进行通信时产生的数据流; 模块间数据流指每台服务器与其他所有不同模块内的所有服务器进行通信产生的网络流.由此, MDKautz网络和MDCent网络中数据流的分布情况可用如下定理表示.

定理5.假设整个MDKautz网络都处于all-to-all的流量模式下, 即网络中任意两台服务器之间存在一对数据流.若采用MDKautzRouting算法, 则每条普通链路上承载的数据流的数量为

$ \left( {2m + 1-\frac{{2m}}{n} + \frac{{n-1}}{n}(k-1)(m + 1)} \right)\frac{{(N - t)}}{n}. $

每条高速链路上承载的数据流的数量为$ (k-1)(m + 1)\frac{{(N-t)}}{n} $, 其中, t和N分别为CH模块和MDKautz网络中服务器的数量.

证明:根据CH_m结构的性质3可知, 单个CH_m模块的服务器个数t=n^m(m+1), 交换机个数g=n^m+1, 由M(n, m, k)结构的定义可知:网络包含的模块总数为M, 网络规模N=tM.有向普通链路的个数为2nN, 有向高速链路的个数为$ \frac{1}{2}gM. $在all-to-all流量模式下, MDKautz网络中所有模块间数据流的数量为M(M-1)t².

在CH_m网络中, 所有服务器到任意交换机A的路径长度可以分成i组, 第G_i组包括所有距离A为2i-1(i∈[1, m+1])跳的服务器.每组中的服务器数量可表示为$ (m + 1)C_m^i{(n-1)^i}$, 则服务器到交换机的平均路径长度为

$ {h_1} = \frac{1}{{(m + 1){n^m}}}\sum\limits_{i = 0}^m {[(2i + 1)(m + 1)C_m^i{{(n-1)}^i}]} = 2m + 1 -\frac{{2m}}{n}. $

同理, 计算出任意两台交换机之间的平均路径长度${h_2} = \frac{1}{{{n^{m + 1}}- 1}}\sum\limits_{i = 1}^{m + 1} {[2iC_{m + 1}^i{{(n-1)}^i}]} = \frac{{2(n -1)t}}{{n(t -1)}}(m + 1). $

在M(n, m, k)中, 任意两台服务器节点之间最多经过包括源、目的模块在内的k+1个模块, 由于中间模块通常为几十到数百不等, 所以本文忽略目的模块中服务间的数据流, 并认为经过的中间模块的平均数量为k-1, 则平均每条模块间数据流所要经过的普通链路的数量近似可表示为2h₁+(k-1)h₂.由于CH中所有链路的使用都是平等和均衡的, 因此, 每条普通链路上承载的流的数量为

$ \frac{{(2{h_1} + (k-1){h_2})M(M-1){t^2}}}{{2nN}} = \left( {2m + 1-\frac{{2m}}{n} + \frac{{n - 1}}{n}(k - 1)(m + 1)} \right)\frac{{(N - t)}}{n}. $

同理, 每条高速链路上的流的数量为$ \frac{{kM(M-1){t^2}}}{{\frac{1}{2}gM}} = 2k(m + 1)\frac{{(N-t)}}{n} $.

由定理5可知, 普通链路和高速链路传输的数据流的数量不同.因此, 要实现无阻塞地all-to-all通信, 二者所需提供的链路带宽也不尽相同.高速链路和普通链路所承载的数据流数量之比, 决定了all-to-all通信时模块间互联结构与模块内互联结构所需提供的聚合带宽, 也决定了整个模块化数据中心网络是否存在性能瓶颈.由定理5可得出, 这一比率为$ r = \frac{{m + 1}}{{2m + 1-\frac{{2m}}{n} + k\frac{{n-1}}{n}(m + 1)}}. $

因此, 对于一个由16 512个CH模块构成的M(2, 7, 2) 网络, 假设普通链路的容量为1, 那么all-to-all流量模式下其所需的高速链路容量为2.7Gbps, 即高速链路只需提供2.7Gbps的带宽即可避免成为瓶颈, 实现无阻塞的all-to-all传输.而目前普通商用交换机单个高速端口的带宽为10Gbps, 因此, 高速链路不会成为整个MDKautz网络的性能瓶颈.

从定理5的证明过程中还可以得出以下推论.

推论1. MDKautz网络的瓶颈链路为模块内普通链路, 故其ABT为$ N{\left( {\frac{{2m + 1}}{n} + \frac{{(k-1)(n-1)(m + 1)-2m}}{{{n^2}}}} \right)^{ - 1}}. $

图 10给出了MDKautz(k=2) 与MDCube(D=2) 的ABT随网络规模的变化规律, 二者的ABT均随网络规模的增大呈线性增长趋势, 当n > 6时, MDKautz的ABT大于MDCube的ABT.

5 模拟实验

在超大规模数据中心中, 服务器和交换机都不可避免地遇到各种故障, 而且故障发生时往往无法即刻定位并修复.因此, 我们更关注存在网络失效的情况下模块内、外的容错路由策略是否能够确保MDKautz网络的性能呈现平缓下降的趋势.在本节中, 我们在Eclipse6.0平台下编写了模拟程序, 选取k=2时的MDKautz网络作为评估对象, 选取D=2时的典型MDCube网络作为比较对象.令模块内部普通链路的速率为1Gbps, 而不同模块间高速链路的速率为10Gbps.

第1个实验测试不同规模的MDKautz网络中2个模块间通信的ABT.该实验模拟MapReduce的reduce过程, 即每个reducer从所有mapper中取回数据, 产生一个all-to-all的流量模式.在该流量模式下, 当服务器/交换机的失效率从0%达到20%时, 观察2个模块间通信时网络的ABT的变化情况.假设模块内部普通链路的速率为1Gbps, 而不同模块间高速链路的速率为10Gbps(如图 11所示).

从图 11中可以看出:单个模块的规模t越大, MDKautz网络中2个模块之间的ABT越大.因为当服务器的网络端口数一定时, 单个模块中交换机的数量随规模的增大而增加, 因此能够提供给模块间的通信链路也随之增多.与此同时, 随着链路故障率的上升, MDKautz网络的性能始终是平缓下降的, 这是因为MDKautz网络的模块内部和模块之间均存在多条并行路径, 因此任意一对服务器间存在多条富连接, 在网络失效的情况下, 冗余的通信路径确保任意两台服务器间总有一条连通的链路.根据ABT还可以算出每台服务器实际获得的吞吐量, 以规模为2 304为例, 当链路失效率为0时, 2个模块间(共64台服务器)的最大可达聚合吞吐量为45.304.因此, 在网卡线速为1Gbps的条件下, 每台服务器实际获得的吞吐量为0.71Gbps.

在目前提出的模块间互连结构中, MDCube结构拥有最优网络容量和容错性能, 因此, 第2个实验比较单个模块规模相同、网络规模不同的MDKautz和MDCube网络中2个模块间通信的ABT.结果表明, 图 12(a)、图 12(b)中, MDKautz的ABT大于MDCube, 而图 12(c)、图 12(d)正好相反.这是因为单个模块的规模相同时, 模块内的交换机数量决定了模块间互连的链路数, 从而决定了网络容量的大小.在图 12(a)的参数配置下, MDKautz中单个模块对外能够提供的交换机端口数均大于MDCube, 所以其相应的ABT也大于MDCube, 而图 12(b)中, MDKautz的单个模块对外能够提供的交换机端口数均小于MDCube, 所以其相应的ABT也比MDCube小.同时, 当20%的链路失效率发生时, MDCube的ABT性能平均下降50%, 而MDKautz只有38%.因此, 随着网络失效率的增加, MDKautz的性能下降更为平缓.

6 结论

本文针对超大规模MDC网络的互连问题提出了一种新型网络结构MDKautz.MDKautz利用模块内大量未被使用的交换机预留高速端口将模块以Kautz图互连, 构造出具有高带宽、高容错和灵活可持续扩展性的超大规模数据中心网络.模块内外松耦合的互连设计和路由算法为模块之间提供了较高的聚合带宽; 多条模块间不相交平行多路径确保网络具有良好的容错能力; 且能够通过少量地调整现有网络结构, 使网络的扩展不受限于模块内的可用高速端口数, 从而进一步满足大规模数据中心对无损扩展和持续扩展的需求.MDKautz能够广泛适用于连接各种模块内的互联结构, 且均能达到较理想的网络性能.数学分析和模拟实验结果表明:MDKautz结构具有良好的拓扑特性和通信性能, 能够以较小的直径构建出较大规模的网络, 同时具有更大的二分带宽, 对构建超大规模MDC网络是可行的.