网络编码在分布式存储系统中运用的研究

摘要

网络编码由R.Alswede于“Network Information Flow”一文中首次提出，它彻底改变了传统路由的存储转发模式，允许中间节点对收到的数据包进行信息重组，从而达到多播通信网络的容量上界。Acedanski等人在“How good is random linear coding baseddistributed networked storage“一文中更是将网络编码的思想引入到存储技术中，提出了一种随机线性编码方案。网络编码自提出以来就受到了各界学者的密切关注。
　　近年来，随着互联网的飞速发展，网络信息量呈指数级的增长，信息技术产业已将其技术重心转移至对存储技术的研究。传统的客户机/服务器存储模型已无法满足人们日益增长的存储需求。分布式存储主要利用网络中闲置的存储空间，通过网络技术将网络中的闲置PC机组合起来搭建成信息存储资源池。因其良好的可扩展性和低廉的价格得到了广泛的运用。有人提出将网络编码技术运用于分布式存储系统中。研究表明，将网络编码应用于分布式存储系统不仅能够节约带宽消耗，还能很好的实现负载均衡，增强系统的健壮性，对分布式存储系统的发展和改进意义重大。
　　本文首先对Acedanski等人提出的基于随机线性编码的存储方案进行了研究，对比了复制、纠删码等常见存储方案，得出随机线性编码存储方案能在消耗更少额外存储带宽的情况下以较高的概率完成源文件重构的结论。接着，本文针对网络编码方案对分布式存储系统下基于再生码的节点修复技术进行了研究。该修复技术最大的优点在于无需下载整个源文件就可实现失效节点的修复，能大大减少节点修复时的带宽开销。相关文献证明了再生码方案存在两个极值点即:最小存储带宽再生点(Minimum storageregeneration points，MSR)和最小节点修复带宽再生点(Minimum bandwidth regenerationpoints，MBR)。本文对其对应的两种编码修复技术:最小存储再生码(Minimum storageregeneration code，MSRC)和最小带宽再生码(Minimum bandwidth regeneration code，MBRC)进行了深入的研究。通过本文的数值计算结果表明基于MBRC的编码修复技术能在节点修复时实现带宽消耗的最小值。文章最后对基于网络编码的MBRC方案进行了仿真实现，基于VC++6.0平台对MBRC方案的数据分布、数据重构、失效节点修复几个过程进行了模拟仿真。利用仿真结果验证了MBRC方案的有效性。

目录

声明

摘要

第1章 绪论

1．1 课题研究背景和意义

1．2 本课题的研究内容

1．3 本文主要内容组织结构

第2章 相关理论基础

2．1 网络编码概述

2．1．1 网络编码研究背景

2．1．2 网络编码研究现状

2．1．3 经典的容量网络模型

2．1．4 网络编码模型

2．2 网络编码的算法设计

2．2．1 线性网络编码

2．2．2 网络编码的可译条件

2．3 纠删码概述

2．4 本章小结

第3章 分布式存储系统相关存储技术的研究

3．1 分布式存储系统简介

3．1．1 分布式存储系统的特点

3．1．2 典型的分布式存储系统及相关冗余策略

3．2 相关存储机制研究背景

3．2．1 分布式存储系统的存储机制

3．2．2 无编码分块存储方案

3．2．3 完全复制冗余存储方案

3．2．4 纠删码冗余存储方案

3．2．5 纠删码vs．完全复制

3．2．6 随机线性编码冗余存储方案

3．3 不同存储方案分析

3．3．1 无编码分块存储方案

3．3．2 纠删码冗余存储方案

3．3．3 随机线性编码存储方案

3．4 数值比较

3．5 本章小结

第4章 分布式存储系统节点修复技术的研究

4．1 常见节点修复技术

4．1．1 复制方案的修复技术

4．1．2 纠删码方案的修复技术

4．1．3 混合编码方案的修复技术

4．2 再生码的修复技术

4．3 文件分块数与节点修复带宽定量分析

4．4 系统可靠性与节点修复带宽定量分析

4．4．1 节点的可靠性界定

4．4．2 修复模型

4．4．3 数值比较

4．4．4 结果分析

4．5 冗余度与系统可靠性定量分析

4．5．1 数值比较

4．6 相同容错情况下冗余存储与带宽开销定量分析

4．7 本章小结

第5章 MBRC的仿真实现

5．1 MBRC执行过程

5．1．1 MBRC的实现原理

5．1．2 MBRC的数据分布过程

5．1．3 MBRC的节点修复过程

5．1．4 MBRC的文件重构过程

5．2 基于随机网络拓扑的仿真结果

5．2．1 仿真流程图

5．2．2 仿真事件驱动模型

5．2．3 仿真结果分析

5．3 改进型仿真

5．3．1 文件大小与计算负载之间的关系

5．4 数值比较

5．5 本章小结

结论

致谢

参考文献

攻读硕士学位期间发表的论文