积分商城

最新搜索： KEIL KEA128 STC 虚拟电子实验室 电源 路径规划
您现在的位置是：首页 > 技术资料 > 数据中心中路由编码的可行性研究
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

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

资料介绍

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


部分文件列表

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

【关注B站账户领20积分】

部分页面预览

（完整内容请下载后查看）
第 １１ 期  
电ꢀ  
ꢀ
子ꢀ  
ꢀ
学ꢀ  
ꢀ
报
Ｖｏｌ．４５ꢀ Ｎｏ．１１  
Ｎｏｖ．ꢀ ２０１７  
２０１７ 年 １１ 月  
ＡＣＴＡ ＥＬＥＣＴＲＯＮＩＣＡ ＳＩＮＩＣＡ  
数据中心中路由编码的可行性研究  
丁炳辰１，李卫忠１，唐永康２  
（１．空军工程大学防空反导学院，陕西西安 ７１００５１； ２．国防科学技术大学计算机学院，湖南长沙 ４１００７３）  
ꢀ ꢀ 摘ꢀ 要：ꢀ 修复带宽最优并不代表修复通信量也是最优的，后者与物理网络拓扑有着密切联系．本文基于路由编  
码的思想减少修复通信量．首先，基于信息流图对物理网络中数据的传递过程进行建模，证明得出了满足路由编码可  
行的充要条件，并发现路由编码可以基于再生码实现．然后，针对数据中心网络设计的特点，为 Ｆａｔ⁃ｔｒｅｅ 设计了一个工  
作在应用层的协议来生成修复树，为 ＣａｍＣｕｂｅ 设计了一个启发式算法来生成修复树．关于最小存储再生码的数据修复  
过程的仿真实验表明，路由编码可以有效地降低修复通信量，２ 种修复树生成方案在各自适合的网络中均有较好性  
能：在帮助节点数较小时，Ｆａｔ⁃ｔｒｅｅ 和 ＣａｍＣｕｂｅ 中的修复通信量分别降低了大约 ５０％和 ３０％．  
关键词： ꢀ 数据中心； 物理网络； 修复带宽； 修复通信量； 再生码  
中图分类号： ꢀ ＴＰ３０２ư ８ꢀ ꢀ ꢀ 文献标识码： ꢀ Ａꢀ ꢀ ꢀ 文章编号： ꢀ ０３７２⁃２１１２ （２０１７）１１⁃２７４２⁃１２  
电子学报 ＵＲＬ： ｈｔｔｐ：／ ／ ｗｗｗ．ｅｊｏｕｒｎａｌ．ｏｒｇ．ｃｎꢀ  
ＤＯＩ： １０．３９６９／ ｊ．ｉｓｓｎ．０３７２⁃２１１２．２０１７．１１．０２３  
Ｆｅａｓｉｂｉｌｉｔｙ Ｓｔｕｄｙ ｏｆ Ｒｏｕｔｉｎｇ Ｃｏｄｅｓ ｉｎ Ｄａｔａｃｅｎｔｅｒｓ  
ＤＩＮＧ Ｂｉｎｇ⁃ｃｈｅｎ１ ，ＬＩ Ｗｅｉ⁃ｚｈｏｎｇ１ ，ＴＡＮＧ Ｙｏｎｇ⁃ｋａｎｇ２  
（１．Ａｉｒ ａｎｄ Ｍｉｓｓｉｌｅ Ｄｅｆｅｎｓｅ Ｃｏｌｌｅｇｅ，Ａｉｒ Ｆｏｒｃｅ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ＇ａｎ，Ｓｈａａｎｘｉ ７１００５１，Ｃｈｉｎａ；  
２．Ｃｏｌｌｅｇｅ ｏｆ Ｃｏｍｐｕｔｅｒ，Ｎａｔｉｏｎａｌ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｄｅｆｅｎｓｅ Ｔｅｃｈｎｏｌｏｇｙ，Ｃｈａｎｇｓｈａ，Ｈｕｎａｎ ４１００７３，Ｃｈｉｎａ）  
Ａｂｓｔｒａｃｔ：ꢀ Ｒｅｐａｉｒ ｔｒａｆｆｉｃ ｉｓ ｎｏｔ ａｌｗａｙｓ ｏｐｔｉｍａｌ ｗｈｅｎ ｒｅｐａｉｒ ｂａｎｄｗｉｄｔｈ ｉｓ ｏｐｔｉｍａｌ．Ｔｈｅ ｆｏｒｍｅｒ ｉｓ ｒｅｌａｔｉｖｅ ｔｏ ｐｈｙｓｉｃａｌ ｎｅｔ⁃  
ｗｏｒｋ ｔｏｐｏｌｏｇｙ．Ｔｈｉｓ ｐａｐｅｒ ａｉｍｅｄ ａｔ ｒｅｄｕｃｉｎｇ ｒｅｐａｉｒ ｔｒａｆｆｉｃ ｂａｓｅｄ ｏｎ ｒｏｕｔｉｎｇ ｃｏｄｅｓ． Ｆｉｒｓｔ，ｗｅ ｍｏｄｅｌｅｄ ｄａｔａ ｔｒａｎｓｍｉｓｓｉｏｎ ｉｎ  
ｐｈｙｓｉｃａｌ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｉｎｆｏｒｍａｔｉｏｎ ｆｌｏｗ ｇｒａｐｈ ｓｏ ｔｈａｔ ｗｅ ｃｏｕｌｄ ｇｅｔ ｔｈｅ ｎｅｃｅｓｓａｒｙ ａｎｄ ｓｕｆｆｉｃｉｅｎｔ ｃｏｎｄｉｔｉｏｎ ｔｏ ｆｅａｓｉｂｉｌｉｔｙ  
ｏｆ ｒｏｕｔｉｎｇ ｃｏｄｅｓ．Ａｎｄ ｗｅ ｆｏｕｎｄ ｔｈａｔ ｒｏｕｔｉｎｇ ｃｏｄｅｓ ｃｏｕｌｄ ｂｅ ｒｅａｌｉｚｅｄ ｂａｓｅｄ ｏｎ ｒｅｇｅｎｅｒａｔｉｎｇ ｃｏｄｅｓ．Ｔｈｅｎ，ｗｅ ｄｅｓｉｇｎｅｄ ａ ｐｒｏｔｏ⁃  
ｃｏｌ ｗｏｒｋｉｎｇ ｏｎ ａｐｐｌｉｃａｔｉｏｎ ｌａｙｅｒｓ ｔｏ ｇｅｎｅｒａｔｅ ｒｅｐａｉｒ ｔｒｅｅｓ ｉｎ Ｆａｔ⁃ｔｒｅｅ，ａｎｄ ａ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ ｔｏ ｇｅｎｅｒａｔｅ ｒｅｐａｉｒ ｔｒｅｅｓ ｉｎ  
ＣａｍＣｕｂｅ，ｗｈｉｃｈ ｗｅｒｅ ｂｏｔｈ ｉｎ ａｇｒｅｅｍｅｎｔ ｗｉｔｈ ｔｈｅｉｒ ｏｗｎ ｄｅｓｉｇｎ ｆｅａｔｕｒｅｓ ｏｆ ｄａｔａｃｅｎｔｅｒ ｎｅｔｗｏｒｋｓ．Ｓｉｍｕｌａｔｉｏｎｓ ａｂｏｕｔ ｄａｔａ⁃ｒｅｐａｉｒ  
ｐｒｏｃｅｓｓｅｓ ｉｎ ｓｙｓｔｅｍｓ ｕｓｉｎｇ ｍｉｎｉｍｕｍ⁃ｓｔｏｒａｇｅ ｒｅｇｅｎｅｒａｔｉｎｇ ｃｏｄｅｓ ｓｈｏｗ ｔｈａｔ ｒｏｕｔｉｎｇ ｃｏｄｅｓ ｃａｎ ｒｅｄｕｃｅ ｒｅｐａｉｒ ｔｒａｆｆｉｃ ｅｆｆｉｃｉｅｎｔｌｙ，  
ａｎｄ ｐｅｒｆｏｒｍａｎｃｅ ｏｆ ｔｈｅ ｔｗｏ ｇｅｎｅｒａｔｉｏｎ ｓｃｈｅｍｅｓ ｏｆ ｒｅｐａｉｒ ｔｒｅｅｓ ａｒｅ ｂｏｔｈ ｇｏｏｄ ｉｎ ｔｈｅｉｒ ｏｗｎ ａｄａｐｔｅｄ ｎｅｔｗｏｒｋｓ．Ｉｎ ｆａｃｔ，ｒｅｐａｉｒ  
ｔｒａｆｆｉｃ ｈａｄ ａｂｏｕｔ ５０％ ａｎｄ ３０％ ｒｅｄｕｃｔｉｏｎｓ ｉｎ Ｆａｔ⁃ｔｒｅｅ ａｎｄ ＣａｍＣｕｂｅ ｒｅｓｐｅｃｔｉｖｅｌｙ ｗｈｅｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｐｒｏｖｉｄｅｒｓ ｗａｓ ｓｍａｌｌ．  
Ｋｅｙ ｗｏｒｄｓ：ꢀ ｄａｔａｃｅｎｔｅｒ；ｐｈｙｓｉｃａｌ ｎｅｔｗｏｒｋｓ；ｒｅｐａｉｒ ｂａｎｄｗｉｄｔｈ；ｒｅｐａｉｒ ｔｒａｆｆｉｃ；ｒｅｇｅｎｅｒａｔｉｎｇ ｃｏｄｅｓ  
的复制方式已难以适应数据中心对磁盘利用率和容错  
能力的需求［１］ ．纠删码（ｅｒａｓｕｒｅ ｃｏｄｅｓ）［２］ 以其高存储利  
１ꢀ 引言  
ꢀ ꢀ 数据中心可以形成规模化效应，即较大的数据中  
心有更低的单位成本，所以数据中心通常包含上千台  
到上百万台的服务器，对于这种规模的服务器集群，由  
软件或硬件故障引起的存储节点离线、数据丢失等（统  
称为节点失效）已成为一种常态，而大型分布式存储系  
统的可靠性是数据中心的基础，因此数据中心需要存  
储冗余数据来提高可靠性．  
用率和容错能力的优势得到越来越广泛的关注与应  
用
［３］ ．但是传统的纠删码有较高的修复代价［４，５］ ．例如，  
Ｆａｃｅｂｏｏｋ Ａｎａｌｙｔｉｃｓ Ｈａｄｏｏｐ ｃｌｕｓｔｅｒ 对所存储的总数据的  
８％使用了 Ｒｅｅｄ⁃ｓｏｌｏｍｏｎ 编码，而这 ８％的数据产生的修  
复通信量占了总网络通信量的将近 ２０％［６］ ．这也成为了  
传统纠删码没有被存储系统广泛采用的主要原因．  
Ｄｉｍａｋｉｓ 等 人［７］ 提 出 的 再 生 码 （ ｒｅｇｅｎｅｒａｔｉｎｇ  
ｃｏｄｅｓ）［８］ 达到了单节点存储容量与单节点修复带宽（ｒｅ⁃  
随着数据中心的数据量以指数的趋势增长，简单  
收稿日期：２０１６⁃０８⁃０１；修回日期：２０１６⁃１２⁃０７；责任编辑：马兰英  
第ꢀ １１ꢀ 期  
丁炳辰：数据中心中路由编码的可行性研究  
２７４３  
ｐａｉｒ ｂａｎｄｗｉｄｔｈ）的最优折衷（ｏｐｔｉｍａｌ ｔｒａｄｅｏｆｆ），通过连接  
更多的帮助节点降低了修复带宽．虽然再生码有最优的  
修复带宽，但并不意味着修复通信量（ ｒｅｐａｉｒ ｔｒａｆｆｉｃ） 也  
是最优的．文献［７］基于星型逻辑网络进行分析，每个帮  
助节点与新节点直接相连，距离为 １ 跳，此时的修复带  
宽等于修复通信量，但这是理想化的，实际中帮助节点  
与新节点之间的距离往往不止 １ 跳．Ｚｅｎｇ 等人［９］ 考虑了  
物理网络拓扑和路由器对修复时间和修复通信量的影  
响，提出了路由器执行编码操作的思想，使得路由器输  
出的数据量小于输入的数据量，但是没有讨论路由器  
中编码方式的可行性．Ｚｈａｎｇ 等人［１０］ 也考虑了物理网络  
拓扑对修复通信量的影响，但是仅基于最大距离可分  
（ｍａｘｉｍｕｍ ｄｉｓｔａｎｃｅ ｓｅｐａｒａｂｌｅ，ＭＤＳ）编码，没有考虑帮助  
节点的增加对编码的可行性及修复通信量的影响．  
本文围绕降低修复通信量的问题，指出了修复带  
宽与修复通信量的差别：修复带宽仅仅是修复过程中  
帮助节点生成的修复数据总量，它是修复通信量的下  
界，后者受数据中心的物理网络拓扑的影响．本文贡献  
有以下几点：  
Ｆａｃｅｂｏｏｋ ｗａｒｅｈｏｕｓｅ ｃｌｕｓｔｅｒ 中，单节点修复通常占 ９８％  
以上［３，１１］ ．因此本文仅考虑单节点失效情形．  
定义 １  
（１）新节点：替代失效节点的可用的存储节点．失效  
节点上的数据需要在该节点上得以恢复．  
（２）帮助节点：利用本地存储的数据帮助新节点恢  
复丢失数据的存储节点．  
（３）修复数据：修复过程中帮助节点利用本地相关  
数据生成的用于修复的数据．  
（４）修复带宽：所有修复数据的数据总量，记为 γ．  
（５）修复通信量：所有修复数据经过网络中实际的  
链路最终到达新节点时产生的通信总量，记为 γｔ ．  
根据定义 １，当帮助节点与新节点间距离均为 １ 跳  
＝
时，γｔ γ．但这是理想化的，物理网络中帮助节点与新节  
点之间的距离往往不止 １ 跳．因此，γ 是 γｔ 的下界．  
２．１ꢀ 数据中心网络  
数据中心的关键设计是集群中所有服务器之间的  
互联网络，其网络设计必须满足 ５ 个特殊要求：低延迟、  
高带宽、低成本、消息传递接口通信支持和容错［１２］ ．在  
数据中心中的任何两个服务器节点间应该建立多个路  
径，并通过在冗余服务器之间“复制” 数据和计算来实  
现服务器容错，不应该存在会将整个系统拖垮的单点  
路径或单 点故障． 数据中心的网 络 主 要 有 ２ 种 设 计  
方式：  
（１）将信息流图（ ｉｎｆｏｒｍａｔｉｏｎ ｆｌｏｗ ｇｒａｐｈ） 模型拓展  
到更一般的情形，即物理网络中有中间节点的树状结  
构，通过分析证明得出了满足路由编码可行的充要条  
件，即，中间节点输出数据量的下界以及存储量与修复  
带宽的最优折衷．  
（２）为两种设计方式不同的数据中心网络———Ｆａｔ⁃  
ｔｒｅｅ 与 ＣａｍＣｕｂｅ———分别设计了修复树的生成方案．  
（１）以交换机为中心，交换机用于连接服务器，服  
务器不需要做任何修改．比如典型的 Ｆａｔ⁃ｔｒｅｅ［１３］ ，如图 １  
（ａ）所示，服务器节点都在底层，边缘交换机用于连接  
服务器节点，集群化交换机、边缘交换机和它们的叶节  
点服务器构成一个集装器，核心交换机提供不同集装  
器间的路径．胖树结构在任何两个服务器之间提供了多  
条路径，相应的，路由表也提供了额外的路由路径．  
２ꢀ 准备工作  
ꢀ ꢀ 相比容易发生节点暂时离线的对等分布式存储系  
统，数据中心中节点的规划都是良好的，发生单节点失  
效的概 率 远 高 于 发 生 多 节 点 失 效 的 概 率， 例 如 在  
ꢀ ꢀ （２）以服务器为中心，该设计会修改运行在服务器  
上的操作系统，使用特殊的驱动程序来转发网络数据  
包，仍需要组织交换机来实现互连，如 ＢＣｕｂｅ［１４，１５］ ．Ｃｏｓｔａ  
等人［１６］ 进一步强化服务器在网络中的角色，提出了一  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

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

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号