推荐星级：

数据中心中路由编码的可行性研究

更新时间：2019-12-25 05:37:28 大小：2M 上传用户：zhiyao6 查看TA发布的资源 标签：数据中心 下载积分：1分评价赚积分（如何评价?）打赏收藏评论(0) 举报

资料介绍

修复带宽最优并不代表修复通信量也是最优的,后者与物理网络拓扑有着密切联系.本文基于路由编码的思想减少修复通信量.首先,基于信息流图对物理网络中数据的传递过程进行建模,证明得出了满足路由编码可行的充要条件,并发现路由编码可以基于再生码实现.然后,针对数据中心网络设计的特点,为Fat-tree设计了一个工作在应用层的协议来生成修复树,为CamCube设计了一个启发式算法来生成修复树.关于最小存储再生码的数据修复过程的仿真实验表明,路由编码可以有效地降低修复通信量,2种修复树生成方案在各自适合的网络中均有较好性能:在帮助节点数较小时,Fat-tree和CamCube中的修复通信量分别降低了大约50%和30%.

部分文件列表

文件名	大小
数据中心中路由编码的可行性研究.pdf	2M

立即下载

【关注视频号领20积分】【关注公众号立即送20积分】

部分页面预览

（完整内容请下载后查看）

第１１期

电ꢀ

ꢀ

子ꢀ

ꢀ

学ꢀ

ꢀ

报

Ｖｏｌ．４５ꢀ Ｎｏ．１１

Ｎｏｖ．ꢀ ２０１７

２０１７年１１月

ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡ

数据中心中路由编码的可行性研究

丁炳辰^１，李卫忠^１，唐永康^２

（１．空军工程大学防空反导学院，陕西西安７１００５１；２．国防科学技术大学计算机学院，湖南长沙４１００７３）

ꢀ ꢀ 摘ꢀ 要：ꢀ 修复带宽最优并不代表修复通信量也是最优的，后者与物理网络拓扑有着密切联系．本文基于路由编

码的思想减少修复通信量．首先，基于信息流图对物理网络中数据的传递过程进行建模，证明得出了满足路由编码可

行的充要条件，并发现路由编码可以基于再生码实现．然后，针对数据中心网络设计的特点，为Ｆａｔ⁃ｔｒｅｅ设计了一个工

作在应用层的协议来生成修复树，为ＣａｍＣｕｂｅ设计了一个启发式算法来生成修复树．关于最小存储再生码的数据修复

过程的仿真实验表明，路由编码可以有效地降低修复通信量，２种修复树生成方案在各自适合的网络中均有较好性

能：在帮助节点数较小时，Ｆａｔ⁃ｔｒｅｅ和ＣａｍＣｕｂｅ中的修复通信量分别降低了大约５０％和３０％．

关键词： ꢀ 数据中心；物理网络；修复带宽；修复通信量；再生码

中图分类号： ꢀ ＴＰ３０２ư ８ꢀ ꢀ ꢀ 文献标识码： ꢀ Ａꢀ ꢀ ꢀ 文章编号： ꢀ ０３７２⁃２１１２（２０１７）１１⁃２７４２⁃１２

电子学报ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｅｊｏｕｒｎａｌ．ｏｒｇ．ｃｎꢀ

ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０３７２⁃２１１２．２０１７．１１．０２３

ＦｅａｓｉｂｉｌｉｔｙＳｔｕｄｙｏｆＲｏｕｔｉｎｇＣｏｄｅｓｉｎＤａｔａｃｅｎｔｅｒｓ

ＤＩＮＧＢｉｎｇ⁃ｃｈｅｎ^１，ＬＩＷｅｉ⁃ｚｈｏｎｇ^１，ＴＡＮＧＹｏｎｇ⁃ｋａｎｇ^２

（１．ＡｉｒａｎｄＭｉｓｓｉｌｅＤｅｆｅｎｓｅＣｏｌｌｅｇｅ，ＡｉｒＦｏｒｃｅＥｎｇｉｎｅｅｒｉｎｇＵｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ，Ｓｈａａｎｘｉ７１００５１，Ｃｈｉｎａ；

２．ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒ，ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ４１００７３，Ｃｈｉｎａ）

Ａｂｓｔｒａｃｔ：ꢀ Ｒｅｐａｉｒｔｒａｆｆｉｃｉｓｎｏｔａｌｗａｙｓｏｐｔｉｍａｌｗｈｅｎｒｅｐａｉｒｂａｎｄｗｉｄｔｈｉｓｏｐｔｉｍａｌ．Ｔｈｅｆｏｒｍｅｒｉｓｒｅｌａｔｉｖｅｔｏｐｈｙｓｉｃａｌｎｅｔ⁃

ｗｏｒｋｔｏｐｏｌｏｇｙ．Ｔｈｉｓｐａｐｅｒａｉｍｅｄａｔｒｅｄｕｃｉｎｇｒｅｐａｉｒｔｒａｆｆｉｃｂａｓｅｄｏｎｒｏｕｔｉｎｇｃｏｄｅｓ．Ｆｉｒｓｔ，ｗｅｍｏｄｅｌｅｄｄａｔａｔｒａｎｓｍｉｓｓｉｏｎｉｎ

ｐｈｙｓｉｃａｌｎｅｔｗｏｒｋｓｂａｓｅｄｏｎｉｎｆｏｒｍａｔｉｏｎｆｌｏｗｇｒａｐｈｓｏｔｈａｔｗｅｃｏｕｌｄｇｅｔｔｈｅｎｅｃｅｓｓａｒｙａｎｄｓｕｆｆｉｃｉｅｎｔｃｏｎｄｉｔｉｏｎｔｏｆｅａｓｉｂｉｌｉｔｙ

ｏｆｒｏｕｔｉｎｇｃｏｄｅｓ．Ａｎｄｗｅｆｏｕｎｄｔｈａｔｒｏｕｔｉｎｇｃｏｄｅｓｃｏｕｌｄｂｅｒｅａｌｉｚｅｄｂａｓｅｄｏｎｒｅｇｅｎｅｒａｔｉｎｇｃｏｄｅｓ．Ｔｈｅｎ，ｗｅｄｅｓｉｇｎｅｄａｐｒｏｔｏ⁃

ｃｏｌｗｏｒｋｉｎｇｏｎａｐｐｌｉｃａｔｉｏｎｌａｙｅｒｓｔｏｇｅｎｅｒａｔｅｒｅｐａｉｒｔｒｅｅｓｉｎＦａｔ⁃ｔｒｅｅ，ａｎｄａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｔｏｇｅｎｅｒａｔｅｒｅｐａｉｒｔｒｅｅｓｉｎ

ＣａｍＣｕｂｅ，ｗｈｉｃｈｗｅｒｅｂｏｔｈｉｎａｇｒｅｅｍｅｎｔｗｉｔｈｔｈｅｉｒｏｗｎｄｅｓｉｇｎｆｅａｔｕｒｅｓｏｆｄａｔａｃｅｎｔｅｒｎｅｔｗｏｒｋｓ．Ｓｉｍｕｌａｔｉｏｎｓａｂｏｕｔｄａｔａ⁃ｒｅｐａｉｒ

ｐｒｏｃｅｓｓｅｓｉｎｓｙｓｔｅｍｓｕｓｉｎｇｍｉｎｉｍｕｍ⁃ｓｔｏｒａｇｅｒｅｇｅｎｅｒａｔｉｎｇｃｏｄｅｓｓｈｏｗｔｈａｔｒｏｕｔｉｎｇｃｏｄｅｓｃａｎｒｅｄｕｃｅｒｅｐａｉｒｔｒａｆｆｉｃｅｆｆｉｃｉｅｎｔｌｙ，

ａｎｄｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｔｗｏｇｅｎｅｒａｔｉｏｎｓｃｈｅｍｅｓｏｆｒｅｐａｉｒｔｒｅｅｓａｒｅｂｏｔｈｇｏｏｄｉｎｔｈｅｉｒｏｗｎａｄａｐｔｅｄｎｅｔｗｏｒｋｓ．Ｉｎｆａｃｔ，ｒｅｐａｉｒ

ｔｒａｆｆｉｃｈａｄａｂｏｕｔ５０％ａｎｄ３０％ｒｅｄｕｃｔｉｏｎｓｉｎＦａｔ⁃ｔｒｅｅａｎｄＣａｍＣｕｂｅｒｅｓｐｅｃｔｉｖｅｌｙｗｈｅｎｔｈｅｎｕｍｂｅｒｏｆｐｒｏｖｉｄｅｒｓｗａｓｓｍａｌｌ．

Ｋｅｙｗｏｒｄｓ：ꢀ ｄａｔａｃｅｎｔｅｒ；ｐｈｙｓｉｃａｌｎｅｔｗｏｒｋｓ；ｒｅｐａｉｒｂａｎｄｗｉｄｔｈ；ｒｅｐａｉｒｔｒａｆｆｉｃ；ｒｅｇｅｎｅｒａｔｉｎｇｃｏｄｅｓ

的复制方式已难以适应数据中心对磁盘利用率和容错

能力的需求^［１］．纠删码（ｅｒａｓｕｒｅｃｏｄｅｓ）^［２］以其高存储利

１ꢀ 引言

ꢀ ꢀ 数据中心可以形成规模化效应，即较大的数据中

心有更低的单位成本，所以数据中心通常包含上千台

到上百万台的服务器，对于这种规模的服务器集群，由

软件或硬件故障引起的存储节点离线、数据丢失等（统

称为节点失效）已成为一种常态，而大型分布式存储系

统的可靠性是数据中心的基础，因此数据中心需要存

储冗余数据来提高可靠性．

用率和容错能力的优势得到越来越广泛的关注与应

用

^［３］．但是传统的纠删码有较高的修复代价^{［４，５］}．例如，

ＦａｃｅｂｏｏｋＡｎａｌｙｔｉｃｓＨａｄｏｏｐｃｌｕｓｔｅｒ对所存储的总数据的

８％使用了Ｒｅｅｄ⁃ｓｏｌｏｍｏｎ编码，而这８％的数据产生的修

复通信量占了总网络通信量的将近２０％^［６］．这也成为了

传统纠删码没有被存储系统广泛采用的主要原因．

Ｄｉｍａｋｉｓ等人^［７］提出的再生码（ｒｅｇｅｎｅｒａｔｉｎｇ

ｃｏｄｅｓ）^［８］达到了单节点存储容量与单节点修复带宽（ｒｅ⁃

随着数据中心的数据量以指数的趋势增长，简单

收稿日期：２０１６⁃０８⁃０１；修回日期：２０１６⁃１２⁃０７；责任编辑：马兰英

第ꢀ １１ꢀ 期

丁炳辰：数据中心中路由编码的可行性研究

２７４３

ｐａｉｒｂａｎｄｗｉｄｔｈ）的最优折衷（ｏｐｔｉｍａｌｔｒａｄｅｏｆｆ），通过连接

更多的帮助节点降低了修复带宽．虽然再生码有最优的

修复带宽，但并不意味着修复通信量（ｒｅｐａｉｒｔｒａｆｆｉｃ）也

是最优的．文献［７］基于星型逻辑网络进行分析，每个帮

助节点与新节点直接相连，距离为１跳，此时的修复带

宽等于修复通信量，但这是理想化的，实际中帮助节点

与新节点之间的距离往往不止１跳．Ｚｅｎｇ等人^［９］考虑了

物理网络拓扑和路由器对修复时间和修复通信量的影

响，提出了路由器执行编码操作的思想，使得路由器输

出的数据量小于输入的数据量，但是没有讨论路由器

中编码方式的可行性．Ｚｈａｎｇ等人^［１０］也考虑了物理网络

拓扑对修复通信量的影响，但是仅基于最大距离可分

（ｍａｘｉｍｕｍｄｉｓｔａｎｃｅｓｅｐａｒａｂｌｅ，ＭＤＳ）编码，没有考虑帮助

节点的增加对编码的可行性及修复通信量的影响．

本文围绕降低修复通信量的问题，指出了修复带

宽与修复通信量的差别：修复带宽仅仅是修复过程中

帮助节点生成的修复数据总量，它是修复通信量的下

界，后者受数据中心的物理网络拓扑的影响．本文贡献

有以下几点：

Ｆａｃｅｂｏｏｋｗａｒｅｈｏｕｓｅｃｌｕｓｔｅｒ中，单节点修复通常占９８％

以上^{［３，１１］}．因此本文仅考虑单节点失效情形．

定义１

（１）新节点：替代失效节点的可用的存储节点．失效

节点上的数据需要在该节点上得以恢复．

（２）帮助节点：利用本地存储的数据帮助新节点恢

复丢失数据的存储节点．

（３）修复数据：修复过程中帮助节点利用本地相关

数据生成的用于修复的数据．

（４）修复带宽：所有修复数据的数据总量，记为 γ．

（５）修复通信量：所有修复数据经过网络中实际的

链路最终到达新节点时产生的通信总量，记为 γ_ｔ．

根据定义１，当帮助节点与新节点间距离均为１跳

＝

时，γ_ｔγ．但这是理想化的，物理网络中帮助节点与新节

点之间的距离往往不止１跳．因此，γ 是 γ_ｔ的下界．

２．１ꢀ 数据中心网络

数据中心的关键设计是集群中所有服务器之间的

互联网络，其网络设计必须满足５个特殊要求：低延迟、

高带宽、低成本、消息传递接口通信支持和容错^［１２］．在

数据中心中的任何两个服务器节点间应该建立多个路

径，并通过在冗余服务器之间“复制” 数据和计算来实

现服务器容错，不应该存在会将整个系统拖垮的单点

路径或单点故障．数据中心的网络主要有２种设计

方式：

（１）将信息流图（ｉｎｆｏｒｍａｔｉｏｎｆｌｏｗｇｒａｐｈ）模型拓展

到更一般的情形，即物理网络中有中间节点的树状结

构，通过分析证明得出了满足路由编码可行的充要条

件，即，中间节点输出数据量的下界以及存储量与修复

带宽的最优折衷．

（２）为两种设计方式不同的数据中心网络———Ｆａｔ⁃

ｔｒｅｅ与ＣａｍＣｕｂｅ———分别设计了修复树的生成方案．

（１）以交换机为中心，交换机用于连接服务器，服

务器不需要做任何修改．比如典型的Ｆａｔ⁃ｔｒｅｅ^［１３］，如图１

（ａ）所示，服务器节点都在底层，边缘交换机用于连接

服务器节点，集群化交换机、边缘交换机和它们的叶节

点服务器构成一个集装器，核心交换机提供不同集装

器间的路径．胖树结构在任何两个服务器之间提供了多

条路径，相应的，路由表也提供了额外的路由路径．

２ꢀ 准备工作

ꢀ ꢀ 相比容易发生节点暂时离线的对等分布式存储系

统，数据中心中节点的规划都是良好的，发生单节点失

效的概率远高于发生多节点失效的概率，例如在

ꢀ ꢀ （２）以服务器为中心，该设计会修改运行在服务器

上的操作系统，使用特殊的驱动程序来转发网络数据

包，仍需要组织交换机来实现互连，如ＢＣｕｂｅ^{［１４，１５］}．Ｃｏｓｔａ

等人^［１６］进一步强化服务器在网络中的角色，提出了一

全部评论(0)

暂无评论

评论赚积分>>

上传资源上传优质资源有赏金

数据中心中路由编码的可行性研究

资料介绍

部分文件列表

部分页面预览

相关下载

全部评论(0)

热门标签

最新上传

热门下载

推荐下载

专栏首页