EBSN:一种新型全结构模块化数据中心模型*

韩冬 肖文俊 李梅生

（1.华南理工大学 计算机科学与工程学院，广东 广州510006；2.华南理工大学 软件学院，广东 广州510006；3.广东金融学院 计算机科学系，广东 广州510520）

云服务的发展驱动了数据中心的发展.在数据中心，上万台服务器通过网络连接实现搜索、电子邮件、分布式计算等服务.数据中心网（DCN）架构的研究目标是如何将众多的服务器连接起来，以满足云服务的需求.传统的数据中心网架构大多采用胖树模型［1］或其衍生形式［2-4］，将商用交换机以树状结构分层部署.在胖树模型中，为了满足带宽的需求，核心层和汇聚层的交换机必须使用高端高速交换机，这使数据中心网的构建成本居高不下.此外，为了提供必要的容错性，传统数据中心网使用了大量的冗余设备，这样也增加了建设成本.

为更经济、更快捷地部署数据中心，2007年SUN 公司的黑盒项目首次提出了模块化数据中心（MDC）概念［5］.模块化数据中心是指在标准集装箱中安装上千台服务器、一定数量的交换设备以及必要的电源设备和冷却设备而构成的数据中心.模块化数据中心既可独立使用，也可作为可插拔模块进行连接，以构建更大规模的数据中心.由于MDC 具有部署便捷、灵活性强、易扩展等优点，众多企业都将其作为设计数据中心的解决方案［6］.微软公司在建设芝加哥数据中心时大规模使用模块化数据中心，在该数据中心有近三分之二的服务器部署在标准集装箱中［7］.

文中提出了一种可应用于模块化数据中心的架构EBSN.该架构基于Biswapped 网络（BSN）［8-9］，每台服务器仅需很少的网络接口，通过少量的普通商用迷你交换机将大量的服务器进行连接，即可满足吞吐量的要求.EBSN 采用以服务器为中心的架构，将路由选择策略交由服务器完成，通过源路由协议完成选路过程，并通过容错路由保证架构的性能.

1 相关模型

为了优化传统数据中心网架构，业界提出了一些新的模型方案，如DCell［10］、FiConn［11］、DPillar［12］、MCube［13］、BCN［14］、雪花结构［15］等，这些都是实现数据中心网大规模服务器互连的网络架构，其共同点是服务器的网络接口数量较少且使用普通商用交换机，从而降低建设成本，并保证网络带宽和通信要求.但以上方案不适用于模块化数据中心.模块化数据中心具有如下特点：①封装入集装箱的服务器仅为1 000～2 000 台，而非上万台；②服务器和网络设备一旦封装好，几乎不再更换，因此必须保证MDC 中的容错性和通信容量；③每个集装箱中所使用的交换机为仅有8 个网络端口的普通商用迷你交换机，因此需要以服务器为中心架构［16］才能满足业务的需要.目前针对MDC 的模型有BCube［17］和SCautz［18］.

1.1 BCube

在BCube［17］中，每台服务器有几个网络接口（NIC，一般不超过4 个），服务器通过NIC 与普通商用交换机连接构成整体架构.BCube 以递归方式生成，每个BCubek由n 个BCubek-1和nk个n 口交换机连接形成.实现时，由基础单元BCube0组成BCube1，进而组成BCube2，直至BCubek.每个BCube0由一个n 口交换机和n 台服务器组成.在BCubek中，每台服务器都有k+1 个NIC，并按akak－1...a0（ai∈［0，n－1］，i ∈［0，k］）的形式将其编址；每个交换机按照〈l，sk-1sk-2…s0〉（sj∈［0，n－1］，j∈［0，k－1］）的形式编址，其中l 表示交换机所处的层.图1是一个k=1、n=2 的BCube1结构.

图1 k=1、n=2 的BCube1 结构Fig.1 BCube1 structure with k=1 and n=2

在BCube 中，两台服务器相邻是指这两台服务器连接到同一台交换机.若相邻的两台服务器所连接的交换机位于第i 层，则两台服务器地址中的ai位不同.在BCube 中，采用海明距离来表示两台服务器之间的距离，因此对于BCubek，两台服务器的最大距离为k+1.通过改变不同的ai位的值就可以实现在BCube 模型中的路由，这种路由方式本质上与维数路由是一样的.

文献［17］中通过构造一个非完全结构的BCube3模型封装了2 048 台服务器，但该模型所需的8 口迷你交换机达到1 280 台，且存在交换机端口闲置的情况.

1.2 SCautz

SCautz 模型［18］采用无向Kautz图作为基图.对于Kuatz 图UK（d，k），其定点集V=Zkd，边集E={（X，Y）|X=x1x2...xk，Y=x2x3...xkv，v∈Zd，v≠xk}，其中，Zd={0，1，…，d}，Zkd={x1x2...xk|xi∈Zd，xi≠xi+1，1≤i＜k}.由定义可知，无向Kautz 图是d 正则图，直径为k，且有dk+dk+1个顶点和dk+dk+1条边.

SCautz 模型中的设备有两类：具有多个NIC 的服务器和迷你商用交换机.服务器以无向Kautz 图UK（d，k）的顶点形式编址为字符串a0a1...ak，其中ai∈Zd∧ai≠ai+1；交换机以相同方式编址为s0s1s2...st，其中si∈Zd∧si≠si+1，t＜k.在SCautz 模型中，交换机分为Sleft和Sright两类，Sleft连接地址串左边t 位为s0s1s2...st的服务器，Sright连接地址串右边t 位为s0s1...st的服务器.此外，服务器之间可按照无向Kautz 图的边生成方式连接，即地址为a0a1...ak的服务器A 与地址为{a0a1...aku|u∈Zd，u≠ak}或{va0a1...ak-1|v∈Zd，v≠a0}的服务器直连.图2是一个无向Kautz 图UK(2，2).

图2 无向Kautz 图UK(2，2)Fig.2 Undirected Kautz graph UK(2，2)

为实现用256 台低端商用交换机连接2 048 台服务器并获得好的性能，SCautz 模型在每台服务器中使用了5 张双端口网卡，这大大超出了文献［17］中所建议的网络端口数.

1.3 Biswapped 网络（BSN）模型

BSN［8-9］是以规模为n 的任意图Ω 为因子网络，由2n 个与Ω 同构的因子网络构成，BSN 又被记为BSN（Ω）.在BSN（Ω）中，所有的因子网络（簇）被等分为两部分，并按如下方式连接这些簇：一部分的簇g 中的点p 与另一部分的簇p 中的点g 相连.如果将每个簇视为一个超点，那么BSN（Ω）可视为这些超点经簇间连接形成的完全二部图Kn，n.图3是以4 阶环网C4为因子网络的BSN.

设Ω 为因子网络，g 为由因子网络Ω 所形成的簇，p 为簇中的一个点，i 表示Biswapped 网络Σ 中的某一部分，取值为0 或1，则Biswapped 网络具有如下的良好性质.

图3 由C4 组成的Biswapped 网络Fig.3 A Biswapped network using C4

性质1Σ 中的顶点度数|Σ|等于Ω 中的顶点度数|Ω|+1，且Σ 中顶点〈i，g，p〉的度degΣ（〈i，g，p〉）等于Ω（或簇g）中任一顶点的度数degΩ（g）+1.

性质2Σ 的直径D（Σ）与Ω 的直径D（Ω）存在如下关系：D（Σ）=2D（Ω）+2.

性质3如果因子网络Ω 中存在哈密顿圈，则Σ 也存在哈密顿圈.

性质4如果因子网络Ω 是连通的，且任一顶点度数degΩ（g）=δ，则Σ中任意两点〈i，g1，p〉与〈i，g2，p〉（g1≠g2）之间存在δ+1 条点不交路径.

在BSN 中，如果其因子网络具有Cayley 图特性，则BSN 也具有相应的对称性、点传递性和容错性，这就是BSN 的设计目标.

但对于BSN 结构，仅仅靠普通商用迷你交换机不足以将MDC 中大量的服务器互连，必须将其进行适当扩展以满足MDC 的需求.

2 EBSN 模型

EBSN 同样以规模为n 的网络作为因子网络，由4n2个因子网络构成.在EBSN 中，因子网络称为基本单元，2n 个基本单元互连构成一个组，2n 个组之间互连形成EBSN.

EBSN 中的服务器以（C，BU，S）形式表示，其中，C 表示服务器所在的组，BU 表示服务器所在的基本单元，S 为服务器在基本单元中的编号.EBSN中服务器的互连规则如下：

（1）服务器（Ci，BUi，Si）与（Ci，BUi，Sj）通过交换机互连；

（2）服务器（Ci，BUi，Si）与（Ci，BUj，Sj）互连，当且仅当BUi=n+Sj且Si=BUj或BUj=n+Si且Sj=BUi；

（3）服务器（Ci，BUi，Si）与（Cj，BUi，Sj）互连，当且仅当Ci=n+Sj且Si=Cj或Ci=n+Sj且Si=Cj.

如图4所示，EBSN 模型中的每个组都是一个BSN，服务器000、001、010、011、020、021、030、031构成一个BSN.EBSN 模型通过扩展，使服务器000、001、100、101、200、201、300、301 也构成一个BSN，且与第1 个BSN 正交于基本单元00.因此，EBSN模型也可视为由多个基本单元以BSN 形式按正交方式构成.

图4 Ω=C2 的EBSN（Ω）Fig.4 EBSN（Ω）with Ω=C2

设Ω 是规模为n 的因子网络，令Γ=EBSN（Ω），则EBSN 具有如下性质.

性质5如果因子网络Ω 是Cayley 图，则Γ 是点可迁的.

性质6|Γ|=4n2|Ω|.

性质7Γ 中的顶点度数=Ω 中顶点度数+2，因此EBSN 是一个正则图.

性质8Γ 的直径D（Γ）与Ω 的直径D（Ω）之间存在如下关系：D（Γ）=4D（Ω）+3.

性质9当由因子网络Ω 构成的Biswapped 网络具有哈密顿圈时，Γ 也有哈密顿圈.

3 EBSN 的路由策略

ESBN 的路由协议需要解决如下3 个问题：①由于ESBN 在构造中没有使用路由器，传统的基于路由器的路由协议如OSPF 不再适用，必须有针对ESBN 模型的路由策略；②传统的路由策略大多为分布式路由，由数据包所经过的路径上的每个路由设备独立寻路，这种方式在EBSN 中将不可避免地产生转发回路，故在ESBN 中不应使用分布式路由方式，而应使用源路由方式；③MDC 中的设备发生故障不可避免，且故障设备不易于替换，因此路由策略必须具有良好的容错性以保证数据包的正常转发.

EBSN 的路由EBRouting 采用源路由方式，充分利用了EBSN 模型的特点，可以实现单点路由、多点路由和容错路由.

3.1 单点无错路由

EBSN 的路由过程可分为组间路由和组内路由两个部分.从源服务器（Cs，BUs，Ss）到目的服务器（Cd，BUd，Sd)（s≠d）的路由过程中，组间路由实现从组Cs到组Ct的寻路，组内路由则在组Ct中实现从BUs到BUd的寻路.如前面所述，由于EBSN 模型是将若干个BSN 通过正交方法而得到，因此EBSN模型中的组间路由和组内路由可以使用同样的路由算法，从而降低算法设计的难度.

从（Cs，BUs，Ss）到（Cd，BUd，Sd）的EBRouting 算法如下：

在EBRouting 中，如果只使用下一跳地址，在转发时还需要通过计算获知通过哪一个网络接口转发.为了提高转发效率，在EBRouting 中采用网络接口号来标识下一跳，路由时可按照网络接口号进行转发.

3.2 多径路由

在MDC 中，服务器之间往往通过多径路由来提高网络流量和传输效率.在构造多径路由时，最常见的方法是构造点不交路径.在EBSN 中，同样可以通过构造多条点不交路径来实现多径路由.

如文献［19］所述，在BSN 中任一节点可以有不超过其相邻节点数量的点不交路径.在EBSN 中，任一节点都处于BSN 模型中，因此也可以利用BSN的点不交路径来构造多径路由.

对于EBSN 中的节点（Cs，BUs，Ss），至少可选择3个相邻节点（Cs，BUs，Ss1）、（Cs2，BUs，Ss2）及（Cs，BUs3，Ss3），其中（Cs，BUs，Ss1）与（Cs，BUs，Ss）满足服务器互连规则1，且Ss1与Cs、BUs、Ss都不同；（Cs2，BUs，Ss2）与（Cs，BUs，Ss）满足服务器互连规则2，（Cs，BUs3，Ss3）与（Cs，BUs，Ss）满足服务器互连规则3.

同理，目标节点（Cd，BUd，Sd）也有3 个邻节点（Cd，BUd，Sd1）、（Cd2，BUd，Sd2）及（Cd，BUd3，Sd3）分别与目标节点满足互连规则1、2、3.

在构建多径路由时，在节点（Cs，BUs，Ss1）、（Cs2，BUs，Ss2）、（Cs，BUs3，Ss3）与节点（Cd，BUd，Sd1）、（Cd2，BUd，Sd2）、（Cd，BUd3，Sd3）之间分别建立路由.通过此方式建立的路由，可能产生点相交的情况.当两条路径点相交时，则可以按照BSN 的方式更新相交的路径节点，找到边不交的路径.

3.3 容错路由

服务器（交换机）故障是任何数据中心都无法避免的问题.传统的数据中心可通过更换设备保障数据中心的运行，而在MDC 中更换设备是不太可能的，因此，为了保证MDC 的正常工作，路由算法必须提供足够的容错性.

在EBSN 中，每台服务器都要定期查询互连服务器/ 交换机的状态，以获知其是否处于正常工作状态.综合来说，设备故障主要有3 种：服务器故障（宕机）、服务器NIC 故障以及交换机故障.从发送方来看，这3 种故障的表现形式具有很大的相似性.当接收方的服务器出现故障或接收方的NIC 出现故障时，发送方都无法接收到响应报文，可一并视为链路故障；当交换机出现故障时，发送方将无法与同一基本单元中的其他服务器通信.因此，在EBSN 中需要解决的故障主要为链路故障和交换机故障.

在EBSN 中，可采取再路由的方式来规避故障设备，实现容错路由.如图5所示，有数据包从服务器src 发送至服务器dst.在服务器src 上使用EBRouting 源路由策略得到的路径是将数据包转发至服务器s1，再转发至服务器s2，s2直接转发至t1，最后经服务器t2到达目的服务器dst，即路径为src-＞s1-＞…-＞s2-＞t1-＞…-＞t2-＞dst.现假定s2未能收到从t1返回的查询响应，则当数据包到达服务器s2时，由于存在故障，无法转发至服务器t1.此时，服务器s2将进行本地再路由，再次执行EBRouting 算法，重新确定一条可达目的服务器dst 的路径，并将该路径附加到原路径中s2之后，得到新的路径.

图5 EBSN 的再路由Fig.5 Rerouting in EBSN

采用本地再路由方法需要注意是否产生回路.为避免产生回路，EBSN 中的再路由方法要求再路由时将第1 跳强制指定为与s2相连且未发生故障的服务器r1，而非交换机，进而经r2转发至目的服务器dst.

4 仿真与结果分析

构造EBSN 时仅需要使用服务器和普通八口商用交换机.首先将8 台服务器与交换机连接，构成基本单元.16 个基本单元通过服务器的网络接口按照Biswapped 网络方式连接后形成组，最后将16 个组通过服务器的网络接口连接，构成完整的EBSN网络.通过EBSN 的连接方式可以实现2 048 台服务器的连接，且仅需256 台交换机.图6为32 台服务器所构成的EBSN.

图6 32 台服务器构成的EBSNFig.6 EBSN consisting of 32 servers

由性质4 可知，在EBSN 中，由于因子网络的直径为1，故该网络的直径为7.

在仿真试验中使用BCube（8，3）作为对照模型.BCube（8，3）由2 个完全的BCube（8，2）和1 个部分BCube（8，2）组成，共有2 048 台服务器.为了与BCube的配置相同，在仿真时，在服务器之间以及服务器与交换机之间使用1Gb/s 的链路.对于MDC，当封装在集装箱中的服务器或交换机发生故障时的容错吞吐量，尤其是全部对全部的吞吐量是一个关键的性能度量指标.在BCube 中，每台服务器都有4 个网络接口且平均路径长为3.75，而在EBSN 中，每台服务器仅有3 个网络接口且平均路径长为5.37，故EBSN 的聚合瓶颈带宽（ABT）会小于BCube.

当服务器发生故障时，BCube 和EBSN 都出现性能衰减，如图7（a）所示.这是因为在以服务器为中心的结构中，服务器是数据包转发的重要组成部分.BCube 通过选择通信路径的方式旁路故障服务器，当故障服务器数量较少时，BCube 的吞吐量衰减趋势稍明显，这是由于可用通信路径的减少影响了BCube 的吞吐量，但随着故障服务器数量的增多，BCube 的吞吐量衰减趋缓.EBSN 通过容错路由旁路故障服务器，当故障服务器数量较少时，旁路故障服务器能保证吞吐量所受影响较小，但当故障服务器的数量超过总数的10%时，由于旁路所带来的开销导致性能衰减趋势增大.

当交换机发生故障时，BCube 的性能衰减明显，如图7（b）所示.其原因是BCube 中所有的路径都必须经过交换机，故交换机故障对BCube 的影响极大.而对于EBSN，当交换机发生故障时，可以通过服务器之间的互连绕行，以保证整个系统的性能，故性能衰减情况优于BCube.

图7 服务器/交换机故障时ABT 的衰减Fig.7 Degradation of ABT when server/switch failed

5 结论

文中提出了一种新的模块化数据中心网络模型EBSN.该模型采用服务器中心架构，模型中的服务器只有3 个网络接口，且仅需使用普通商用迷你交换机.与BCube 的不完全结构相比，EBSN 具有完整的结构.在EBSN 中可实现单点路由、多径路由和容错路由，且减少了对交换机数量的要求.仿真结果表明，EBSN 具有良好的性能和容错性.今后将研究EBSN 模型的负载均衡和资源调度等问题.

［1］Leiserson C E.Fat-trees：universal networks for hardwareefficient supercomputing［J］.IEEE Transactions on Computers，1985，100（10）：892-901.

［2］Al-Fares M，Loukissas A，Vahdat A.A scalable，commodity data center network architecture ［C］//Proceedings of the ACM SIGCOMM 2008 Conference on Data Communication.New York：ACM，2008：63-74.

［3］Niranjan Mysore R，Pamboris A，Farrington N，et al.Port-Land：a scalable fault-tolerant layer 2 data center network fabric ［J］.SIGCOMM Computer Communication Review，2009，39（4）：39-50.

［4］Wang C，YuanY.A high performance，low-cost network architecture for data centers ［C］//Proceedings of 2010 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery.Huangshan：IEEE，2010：284-287.

［5］Waldrop M M.Data center in a box ［J］.Scientific American，2007，297（2）：90-93.

［6］Katz R H.Tech titans building boom ［J］.IEEE Spectrum，2009，46（2）：40-54.

［7］新浪科技.揭秘微软全球最大数据中心：集装箱放置服务器［EB/OL］.（2009-11-03）［2014-04-01］.http：//tech.sina.com.cn/it/2009-11-03/10353559696.shtml.

［8］Xiao Wenjun，Chen Weidong，He Mingxin，et al.Biswapped networks and their topological properties ［C］//Proceedings of the Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing.Qingdao：IEEE，2007：193-198.

［9］Xiao Wenjun，Parhami Behrooz，Chen Weidong，et al.Biswapped networks：a family of interconnection architectures with advantages over swapped or OTIS networks［J］.International Journal of Computer Mathematics，2011，88（13）：2669-2684.

［10］Guo Chuanxiong，Wu Haitao，Tan Kun，et al.DCell：a scalable and fault-tolerant network structure for data centers［J］.ACM SIGCOMM Computer Communication Review，2008，38（4）：75-86.

［11］Li Dan，Guo Chuanxiong，Wu Haitao，et al.FiConn：using backup port for server interconnection in data centers ［C］//Proceedings of 2009 IEEE INFOCOM.Rio de Janeiro：IEEE，2009：2276-2285.

［12］Liao Y，Yin D，Gao L.Dpillar：scalable dual-port server interconnection for data center networks ［C］//Proceedings of the 19th International Conference on Computer Communications and Networks.Zurich：IEEE，2010：1-6.

［13］Wang C，Yuan Y，Wei Y.MCube：a high performance and fault-tolerant network architecture for data centers［C］//Proceedings of 2010 International Conference on Computer Design and Applications.Qinhuangdao：IEEE，2010：V5-423-V5-427.

［14］Guo Deke，Chen Tao，Li Dan，et al.BCN：expansible network structures for data centers using hierarchical compound graphs ［C］//Proceedings of 2011 IEEE INFOCOM.Shanghai：IEEE，2011：61-65.

［15］刘晓茜，杨寿保，郭良敏，等.雪花结构：一种新型数据中心网络结构［J］.计算机学报，2011，34（1）：76-85.Liu Xiao-qian，Yang Shou-bao，Guo Liang-min，et al.Snowflake：a new-type network structure of data center［J］.Chinese Journal of Computers，2011，34（1）：76-85.

［16］Chen K，Hu Chengchen，Zhang Xin，et al.Survey on routing in data centers：insights and future directions［J］.IEEE Network，2011，25（4）：6-10.

［17］Guo C，Lu G，Li D，et al.BCube：a high performance，server-centric network architecture for modular data centers ［J］.ACM SIGCOMM Computer Communication Review，2009，39（4）：63-74.

［18］Huang Feng，Lu Xicheng，Li Dongsheng，et al.SCautz：a high performance and fault-tolerant datacenter network for modular datacenters ［J］.Science China Information Sciences，2012，55（7）：1493-1508.

［19］Chen W，Xiao W.Constructing node-disjoint paths in biswapped networks（BSNs） ［C］//Proceedings of the 3rd International Conference on Grid and Pervasive Computing Workshops.Kunming：IEEE，2008：256-261.