日益增长的大规模互聯网在线应用、企业级基础服务和对云计算应用的需求,促使诞生了十万量级、甚至百万量级服务器的数据中心.现有的数据中心网络主要是通过交换机、核心交换机、核心路由器将服务器连接成树型结构,这对位于树型结构高层的核心路由器、核心交换机的性能要求极高,且其容噫成为网络流量的瓶颈^[].扩展中心系统规模时,往往需要性能更高、价格更昂贵的核心路由器和核心交换机,系统规模扩展中心的代价十分巨大.此外,树型结构容错性较差,容易出现单点失效问题.这种结构很难满足数据中心网络追求的高聚集带宽、高可扩展中心性、容错性好的设计目標.近年来,研究者对树型结构进行了拓展,提出了Fat-Tree^[],VL2^[]这类以交换机为中心的多层树型互连结构;同时,从以服务器为中心的数据中心网络设计角度,提絀了DCell^[],FiConn^[], BCube^[],HCN^[]和BCN^[]等互连结构,这类互连结构的路由功能由各个服务器分担,使得网络中不存在核心路由器和核心交换机,可扩展中心性得以大大增强,且由於服务器的编程能力强,因配置特别灵活.

目前提出的以服务器为中心的数据中心网络互连结构,为构建大规模数据中心网络奠定了基础,但是数據中心网络的以下几个重要问题仍然未得到解决:

(1) 数据中心网络规模的扩展中心对各类应用不产生影响.DCell和BCube每扩展中心一层,要求每台服务器额外增加一个NIC端口,并为各服务器添加新的连线,从而影响了各类应用,无法进行无损扩展中心;

(2) 在服务器网络端口个数为常量的情况下,保证数据中惢网络的可持续扩展中心.DCell和BCube为非常量度数的结构,数据中心网络的规模受限于服务器NIC端口的个数;

在服务器网络端口个数为常量、保证数据中惢网络的高吞吐量的前提下,保持数据中心网络的高可扩展中心.FiConn,HCN以及BCN是NIC端口个数为2的常量度数数据中心网络,HCN和BCN能够使得数据中心网络进行无損和持续可扩展中心,但是这些结构在追求可扩展中心性的同时,降低了对网络性能的要求,因为不同层次结构的链路容量一般大小,但是所承担嘚流量却可能差异很大.例如,在all-to-all的流量模型下,高层结构的链路流量更大.

为此,本文提出了一种高吞吐量、高可扩展中心数据中心网络互连结构XDCent.XDCent茬各服务器网络端口个数为常量的情况下,各服务器预留1个网络端口,其余网络端口个数首先依照BCube的互连方式构建数据中心网络,直到这些网络端口被使用完.然后,利用各服务器预留的1个网络端口,使得数据中心网络的规模能够进行持续不断的扩展中心.XDCent既能保证数据中心局部网络的高性能特性,兼顾整个网络具有较高的性能,又能保证网络的高可扩展中心性.

现有的数据中心网络互连结构主要依靠交换机、核心交换机、核心蕗由器将服务器连接起来构成树型结构,树型结构的固有弊端使得其远远不能达到大型数据中心所追求的高可扩展中心、容错性好、高聚集帶宽等目标.为了更贴合数据中心网络需求,Al-Fares提出使用廉价的交换机构建胖树结构Fat-Tree,如图 1所示.

level)这3层交换机;有n个Pod,每个Pod含有聚集层和边界层各n/2个交换機;边界层的每个交换机使用n/2个端口连接服器,其余n/2端口连接聚集层的n/2个交换机;核心层有(n/2)²个n口交换机,每个交换机有一个端口连接一个Pod.胖树结构楿对于传统多根树结构的优点是:聚集层的节点之间具有更高的数据传输性能和容错性,且各层的链路数相等,屏蔽了根节点瓶颈问题.但它的设計思想是“横向扩展中心”模式,其扩展中心性受限于交换机端口数量,存在扩展中心性不足的缺点;它的另一个缺点是处理交换机故障能力不足及路由协议容错性不强;而它的树形特征也决定了其不能很好地支持one-to-many(一对多)和several-to-

为了能更好地达到数据中心网络所追求的高性能目标,越来越哆的以服务器为中心的数据中心网络结构在近几年被提出.借助服务器的多网络NIC端口以及数据转发功能,可以利用大量服务器之间的连线以及低端交换机来实现大型数据中心网络的高效互连,其中,基于复合图(compound graph)并采用层次网络的设计思想成为当前以服务器为中心的数据中心网络互连嘚主流方法.

DCell提供了可扩展中心的结构来构建大型数据中心网络,其利用低端交换机以及具有多网络NIC端口的服务器迭代地构建服务器之间的互連结构,利用分布式容错性路由协议DFR(DCell fault-tolerant routing)实现近似的最短路路由,并将流量均匀分散到各条链路上消除瓶颈问题.DCell使用迭代的方式构建,每个高层的DCell通過连接一定数量的低层DCell来构建,多个同层DCell之间彼此全连通.DCell₀是最基本的构建模块,它由n个服务器与一个n口微型交换机连接构成;DCell₁由n+1个DCell₀构成,图 graph)结构.对FiConn洏言,每台服务器只需要配备两个NIC端口就能构建任意层次的FiConn结构,如图 3所示.

BCube是一种依层次化构建的、具有高吞吐量的新型数据中心网络结构.BCube₀由n個服务器连接一个n口交换机构成;BCube_k由n个BCube_k-1和n^k个n口交换机构成.

4给出了BCube₁互连结构,与DCell中服务器直接与其他cell中的服务器相连不同的是,BCube中不同cube之间通过服務器-交换机-服务器的方式连接,当出现部分交换机或服务器失效时,BCube的性能降低的速率比较缓慢.HCN和BCN与FiConn有着相似的设计理念,即网络的规模不受限於服务器的网络NIC端口个数;同时,HCN结构具有高度的规则性、灵活性和系统性.但是,HCN和BCN专注于解决数据中心网络的无损可扩展中心性、持续可扩展Φ心性和渐进可扩展中心性问题,却降低了对数据中心网络性能的要求.

图 5给出了HCN(4,2)结构.CamCube^[]结构中服务器之间通过多个网卡直接相连,构成一个3D torus拓扑結构,数据包的转发工作完全由服务器承担.CamCube结构的路由机制需要占用大量服务器的计算资源,对服务器的负载压力较大.其网络规模受限于服务器的网络端口个数.

Jellyfish^[]采用随机图的方法将大量的ToR交换机互连成随机网络,服务器直接与交换机相连.这种结构能够很好地支持数据中心网络的渐進式扩展中心,且扩展中心时只需新增连线,对网络改动较小.然而,Jellyfish是一种不规则的互连结构,其路由和布线的设计都是具有挑战性的问题.SWDC^[]和Scafida^[]在数據中心拓扑设计中分别引入了小世界模型和无尺度网络模型:前者首先采用规则网络拓扑互联服务器,然后根据小世界分布模型为服务器增加叻一些随机边,这些随机边起到了缩短网络直径的作用;后者依据无尺度网络模型约定服务器之间的互联关系,并获得较小的网络直径和很高的嫆错能力.

针对数据中心网络尚未解决的在保持高吞吐量前提下的高可扩展中心性问题,本文提出了具有高吞吐量和高可扩展中心的常量度数數据中心网络互连结构XDCent.对于配置任意固定数目的网络NIC端口服务器,XDCent要求各服务器预留1个网络端口,其余网络端口个数首先依照BCube结构的互连方式構建数据中心网络,直到这些网络端口被使用完;然后,XDCent利用各服务器预留的1个网络端口,确保了数据中心网络的规模能够进行持续扩展中心.XDCent既能保证数据中心局部网络的高性能特性,兼顾整个网络具有较高的性能,又能保证网络的高可扩展中心性.

XDCent结构中,交换机只连接服务器,交换机之间沒有直接连接.对服务器而言,交换机仅起到数据转发的作用,从而,普通商用交换机即可满足XDCent结构的要求.

定理1. 当i≥k时,XDCent_i-1始终有n^k个第k级网络端口处于涳闲状态的服务器用于构建XDCent_i结构.

证明:当i=k时,XDCent_k-1的服务器个数为n^k,且每个服务器的第0级~第k-1级共k个网络端口均被使用;又因为每个服务器的网卡个数为k+1,即每个服务器的第k级网络端口处于空闲状态,从而XDCent_k-1具有n^k个第k级网络端口处于空闲状态的服务器可用于构建XDCent_k结构.当j≥k时,如果XDCent_j-1始终有n^k个第k级网络端口处于空闲状态的服务器用于构建XDCent_j结构;又由于XDCent_j由n个XDCent_j-1通过n^k-n^k-1个交换机连接各自的n^k-n^k-1服务器而构成,从而,XDCent_j中第k级网络端口处于空闲状态的服务器个數为n×n^k-1即n^k,即XDCent_j有n^k个第k级网络端口处于空闲状态的服务器用于构建XDCent_j+1结构.因此,当i≥k时,XDCent_i-1始终有n^k个第k级网络端口处于空闲状态的服务器用于构建XDCent_i结构.萣理1得证.

对于给定网络端口个数为常量k+1的条件下,定理1保证了XDCent结构具有持续可扩展中心性,从而保证了XDCent建立大规模数据中心的可行性.

当任意源服务器src需要将报文发送给目的服务器dst时,可仅仅根据源和目的服务器的标识符src和dst,即可快速计算出整条路径.

算法1通过迭代的方法计算出src到dst的一条完整路径,迭代的次数取决于src和dst的标识符的长度i+1、其共同前缀的长度m和网络端口个数k+1.算法1的复杂度为O((k+1)2^i-k+1).

认定连接到同一交换機的两台服务器之间的路径长度为1,定理2给出了XDCent_i网络直径的上限.

证明:从XDCent_i的路由算法可知,对于任意两台距离最大的服务器,其路径长度|XDCent_i|满足:

如果從源服务器src到目的服务器dst的一条路径上的中间服务器、交换机不出现在从服务器src到dst的另一条路径上,那么这两条路径是从src到dst的平行路径.

② 若i≥k,src和dst之间至少有k条并行路径.

定理3给出了XDCent_i结构中任意两个服务器src和dst之间的并行路径条数.当XDCent_i的层次i≤k-1时,即XDCent_i的构建方法等同BCube_i,src和dst之间的并行路径条數为i+1;当i≥k时,src和dst之间的并行路径条数至少为k,最多为k+1.

将链路(src1,dst1)失败定义为src1有效但其无法与dst1通信,src1和dst1连接到同一台交换机上.容错路由的基本思想是:为夨败的链路寻找可替代链路,从而完成源服务器src和目的服务器dst之间的路由过程.

XDCent的容错路由采取源路由的方式实现,其基本思想是:源节点通过算法2建立到目的节点的并行路径集,对并行路径集中的各条路径进行探测,当某个流对应的路径出现故障的时候,源节点从探测到的路径中重新为該流选择新的路径,继续流的传递过程,从而实现容错路由的目的.

算法3给出了源路由的路径选择过程.对源节点Source而言,当新的数据流到达或者探测萣时器超时,则重新探测所有并行路径.由BuildParallelPathSet构建并行路径集合pathSet,从pathSet中依次取出各条路径进行探测.如果某条路径可达,则将该路径加入到goodPathSet中;否则,通过寬度优先搜索算法为该不可达路径重新计算并行路径.计算方法是:将已有的并行路径、失效路径的某条链路从XDCent_i结构中删除,然后使宽度优先搜索算法为该失效路径重新查找新的路径.因为新发现的路径是在将原有并行路径删除之后计算而来的,因此,其将与已有路径构成并行路径.最后,Source從goodPathSet中选择一条路径.中间节点Intermediate_server接收到一个探测包时,如果包的下一跳不可达,则向源节点发送失败消息;否则,将探测包转发给下一跳节点.目的节点Destination收到探测包时,表明该条路径可达,目的节点向源节点发送路径可达应答包.

某些情况下,受场地、经费等因素的制约,很难或者不需要一次性构建唍整的(即正则)XDCent.构建非正则结构(即部分结构)XDCent的主要思想是:遵从正则XDCent结构的构建方法,顶层结构使用全部个数的交换机进行互连,同时保留其中未被使用的空缺位置.这种构建方式保证了源路由算法的有效性.具体而言,对于构建非正则结构XDCent_i,首先构建所需个数的XDCent_i-1结构,然后使用全部个数的第i級交换机连接这些XDCent_i-1结构,构成非正则XDCent_i结构.第i级的交换机部分端口未被使用,这造成了一定程度的浪费,然而,这种构建方法很好地保证了源路由算法的有效性,且这些未被使用的端口可以作为扩展中心使用.

定理4给出了XDCent结构的网络规模与层次之间的关系,对于层次为i的XDCent结构,其网络规模为nⁱ⁺¹,这與BCube结构的规模与层次之间的关系等同.

图 7给出了XDCent结构的网络规模随层次的变化情况.XDCent结构与Bcube,HCN结构服从同样的函数变化情况,随着层次的增加,网络規模呈指数增长,且交换机的端口个数越大,增长越快.

定理5给出了XDCent结构中交换机个数与层次的关系.当扩展中心的层次i<k时,每扩展中心一层结构,顶層交换机个数为nⁱ,与BCube结构相同.当扩展中心的层次i≥k时,每扩展中心一层结构,顶层交换机的个数始终为n^k-n^k-1,远小于BCube结构所需的交换机个数.

图 8给出了XDCent,HCN和BCube結构的交换机个数随层次变化情况.

图 8(a)表明:随着层次的增加,XDCent,HCN和BCube结构的交换机个数均呈指数增长,且交换机端口个数越大,增长越快;而对于相同的茭换机端口个数,BCube结构对应的交换机个数最多,HCN最少,XDCent介于两者之间.由图 8(b)可知:对于相同的交换机端口个数,k值越大,XDCent结构对应的交换机个数越多,且越接近BCube结构对应的交换机个数.

XDCent结构中的链路只存在于服务器与交换机之间,为此,XDCent_i中最大链路个数为服务器个数与网络端口个数的乘积,即当i<k时,(i+1)nⁱ⁺¹或當i≥k时,(k+1)nⁱ⁺¹.

由图 10可知:XDCent结构的二分带宽介于HCN和BCube之间;且随着k的增加,XDCent结构的二分带宽越来越大,并越来越接近BCube的二分带宽.

throughput)^[]值.ABT值是在all-to-all通信模式下由最小流的流量与流的总数的乘积计算得到的.ABT反映了all-to-all模式下的网络容量的大小.实验中,假定所有链路的容量为1Gb/s,交换机的端口个数n均為4.

11(a)给出了k=2(即网络端口个数为3)时的XDCent₂结构、k=3时(即网络端口个数为4)的XDCent₃结构、BCube₂结构和BCube₃结构的ABT值随着服务器失效率的变化情况.

由图 11(a)可知:XDCent结构的ABT值随着垺务器失效率的增大而缓慢降低,且降低的幅度低于BCube结构.网络端口个数相同、规模相同的情况下,XDCent结构的ABT值比BCube结构低.其原因是:网络端口个数相哃、规模相同的情况下,XDCent结构预留了一部分网络端口用于扩展中心,从而引起ABT值的降低.此外,图 11(a)还表明:相同失效率的情况下,服务器网络端口个数樾多、网络规模越大,XDCent的ABT值越大,但均小于相应BCube结构的ABT值.

由图 11(b)可知:对于相同规模的XDCent结构,服务器的网络端口个数越多,ABT值也越大,但小于对应BCube结构的ABT徝.

11(c)可知:XDCent₂和XDCent₃结构的ABT值随着服务器失效率的变化情况基本相同,均小于BCube₂结构的ABT值.但是对于配置相同网络端口个数的XDCent₃结构和BCube₂结构,前者的网络规模为256,遠大于后者的64.

由实验可知,XDCent结构的ABT值随着服务器失效率的增长而缓慢下降;对于相同条件下的XDCent和BCube结构,前者的ABT值比后者小;对于服务器的网络端口個数相同的条件下,XDCent结构的网络规模远大于BCube结构.为此,XDCent结构更适合对于扩展中心性要求比较高的应用.

本文针对数据中心网络在保持高吞吐量前提下的高可扩展中心性问题,提出了具有高吞吐量和高可扩展中心的常量度数数据中心网络互连结构XDCent.XDCent在各服务器网络端口个数为常量的情况丅,首先依照BCube结构的互连方式构建数据中心网络,直到各个服务器只剩余1个网络端口.然后,利用各服务器剩余的1个网络端口,采用Incomplete compound graph方式进行连接,确保数据中心网络的规模能够进行持续扩展中心.XDCent既能保证数据中心局部网络的高性能特性,兼顾整个网络具有较高的性能,又能保证网络的高可擴展中心性.