基于矩阵变换和可调节环的部分重复码构造

目前在构造部分重复码(Fractional Repetition Codes, FRC)的研究方法中发现,大多数是基于同构的分布式存储系统,但实际的存储系统往往需要满足异构的特性.为此,本文提出了两种构造异构FRC的方法,一种是基于矩阵变换构造的异构FRC,该方法用于构造重复度为2,节点存储容量异构的FRC,相比用正则图构造的同构FRC,具有算法计算复杂度低,更符合现实存储系统的优点;另外,本文还提出了运用可调节环构造FRC的方法,用于构造重复度为2或3的FRC,即可得到节点存储容量同构的FRC也可得到异构的FRC.与现有的FRC对比分析,发现本文构造的FRC在节点存储容量上具有异构的特点,修复局部性好,同时构造算法运算复杂度低,可以大范围的选择参数,构造结构简单直观.     

自适应可分解部分重复码的扩展构造

部分重复(Fractional Repetition, FR)码能够实现精确无编码修复,修复复杂度低且修复带宽成本小。在动态分布式存储系统中,要求FR码的节点存储开销和数据块重复度会随机动态变化。为了使FR码更灵活地适应动态分布式存储系统,该文提出利用超图实现自适应可分解FR码的扩展构造方法。具体地,建立超图中边和顶点与FR码中节点和数据块的对应关系,通过增加或删除超图中对应边和顶点,实现超图的扩展构造,进而得到存储系统规模和存储文件规模变化时自适应可分解FR码的扩展构造。基于这种方法,能够扩展构造出给定参数范围内所有自适应可分解FR码,列举了存储节点数20以内的所有参数。自适应可分解FR码与常见的简单再生码(Simple Regenerating Codes, SRC)和RS(Reed-Solomon)码相比,在修复局部性和修复带宽开销方面具有一定优势。     

一类具有最大分支数的16阶0-1矩阵构造

具有最大分支数的0—1可逆矩阵被广泛应用于分组密码的扩散结构设计中。为构造16阶该类矩阵,将16阶0—1矩阵划分为以4阶0-1矩阵为单元的4阶块矩阵,根据特征和域上重量均为2的4维0-1向量相加后所得向量的重量分布特点,在行置换同构意义下构造满足某种特殊结构的4阶0．1矩阵单元组,以此为基础,根据Hadamard矩阵的结构特点,利用矩阵的分块构造思想,给出一类分支数达到最大值8的16阶0-1可逆矩阵和对合矩阵构造方法,并在行置换同构意义下给出对合矩阵的计数。     

图因子分解的故障节点快速修复

为了提高分布式存储系统中故障节点的修复效率, 提出一种新的部分重复(fractional repetition, FR)码的构造算法. 该算法利用完全图的因子分解进行构造, 称为CGFBFR (complete graph factorization based FR)码. 该算法首先对完全图进行因子分解, 分解完成以后确定完全图的因子分解个数, 根据需要存储数据块的重复度来选择完全图的因子个数, 将完全图选中的因子所有顶点当做分布式存储系统中需要存储的数据块, 然后对选中因子图的边进行标记, 标记的边当做分布式数据节点进行存储. 最后根据选中的因子的顶点和边生成编码矩阵, 在分布式存储系统中按照编码矩阵中的数据对数据块分别进行存储. 实验仿真结果显示, 本文提出的一种新的部分重复码构造算法, 与分布式存储系统中的里所(reed-solomon, RS)码、简单再生码(simple regenerating codes, SRC)以及最新的循环可变部分重复(variable fractional repetition, VFR)码相比, 在系统修复故障节点时, 能够快速地修复故障节点, 有效降低了故障节点的修复带宽开销、修复局部性、修复复杂度, 而且构造过程简单, 同时可以灵活选择构造参数, 广泛适用于分布式存储系统中.     

简单无向图的同构判定方法

给出了矩阵同构变换、简单无向图距离矩阵、距离矩阵列和向量以及图的距离谱的定义, 将基于邻接矩阵的同构判定条件推广到简单无向图距离矩阵. 针对简单无向连通图的同构判定问题: 给出了基于距离矩阵特征多项式的同构判定条件; 进一步, 为避免计算误差对判定结果的影响, 给出了基于距离矩阵的秩与列和向量的同构判定条件. 上述两个判定条件均是充要条件且均具有多项式时间复杂度.     

几种线性部件的构造

本文研究了线性部件的构造方式,给出了域GF(2)和域GF(28)上分支数达到最优的线性部件。在域GF(2)上,我们给出了分支数为4的所有4×4级矩阵,在域GF(28)上通过线性码、柯西矩阵、Hadamard矩阵三种方式构造了具有最优扩散性的线性部件。     

基于两代树的低密度校验码校验矩阵构造方法

针对传统的低密度校验(LDPC)码稀疏矩阵构造算法不易实现或可能得到的结果不满足条件的缺陷,给出了一种新颖的基于两代树结构的低密度校验矩阵的构造搜索算法。该算法采用人们熟悉的树型数据结构,可以较为合理地表示稀疏校验矩阵中行与列中非零元素的跳转关系。结果表明,结合蚁群算法在路径搜索方面的优势,采用这种基于两代树的搜索算法,具有算法简单、容易实现的优点。更进一步,如果考虑到非规则码的构造中外信息的引入,可以很容易地将该算法应用在非规则码的构造中。     

图同构的矩阵初等变换判定及算法设计

判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵。不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等。另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题。文章提出了一个简单有效的判断图同构的方法。首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构。最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应。     

基于循环差集的低密度奇偶校验码的构造

基于组合设计中的循环差集,提出一种构造准循环低密度校验(Quasi-Cyclic LDPC)码的方法。所构造的正则Quasi-Cyclic LDPC码的校验矩阵中不存在长度为4的环,并且可以用简单线性移位寄存器实现编码。仿真结果表明,在和积迭代译码下,采用该方法构造的码具有较好的性能。     

一种低复杂度的准循环LDPC码构造

基于RU算法校验矩阵的结构,提出一种准循环低密度奇偶校验(QC-LDPC)码构造方法,即合理选择各子阵,使 和 均为下双对角矩阵,从而实现复杂度为 的编码。仿真结果表明,构造的QC-LDPC码不但编码简单,而且在加性高斯白噪声信道中的纠错性能优于采用随机构造的QC-LDPC和实用化的Block-LDPC码。在误比特率为10-6时,可获得0.3 dB的信噪比增益。     

基于节点共边的异构部分重复码构造

为了满足分布式存储系统的动态存储和异构存储, 本文提出一种基于节点共边的异构部分重复码(heterogeneous fractional repetition codes based on node common edge, HFRC-NCE)的构造算法. 具体地, 将MDS码编码后的数据块分为冷数据块和热数据块, 结...     

一种基于多层次校验的低恢复成本纠删码

随着纠删码在分布式存储系统中的实际应用,纠删码为存储系统提供了更加优秀的存储效率,但当节点丢失时,相较于传统副本技术更多的网络传输带宽开销成为了造成系统性能瓶颈的关键因素。为了解决MDS编码高带宽开销对系统性能的影响,一类新型编码方案——分组码被应用在分布式存储系统中,相较于传统MDS编码能够有效地降低节点修复时的数据传输量,从而减少网络带宽需求。在Pyramid分组码的基础上进行层次扩展,提出一种HLRC（hierarchical local repair codes）纠删码。HLRC相较于LRC引入了层次编码模型,将原始数据块构建为编码矩阵,根据层次进行分别编码,生成包含数据块范围不同的局部校验块;每个层次包含的数据块数量不同,可以保证修复节点时的低修复成本,同时还拥有较高的存储效率。HLRC相较于Pyramid拥有额外的校验块冗余,能够降低校验块出错和多节点出错时的恢复开销。在基于Ceph的分布式存储系统中的实验结果表明,HLRC与Pyramid等分组码相比,单节点修复开销最高可降低48.56%,多节点修复开销最高可降低25%。     

分布式存储系统中的预测式纠删码研究

纠删码消耗的存储空间较少,获得的数据可靠性较高,因此被分布式存储系统广泛采用。但纠删码在修复数据时较高的修复成本限制了其应用。为了降低纠删码的修复成本,研究人员在分组码和再生码上进行了大量的研究。由于分组码和再生码属于被动容错方式,对于一些容易出现失效的节点,采用主动容错的方式能更好地降低修复成本,维护系统的可靠性,因此,提出了一种主动容错的预测式纠删(Proactive basic-Pyramid, PPyramid)码。PPyramid码利用硬盘故障预测方法来调整basic-Pyramid码中冗余块和数据块之间的关联,将预测出的即将出现故障的硬盘划分到同一小组,使得在修复数据时,所有的读取操作在小组内进行,从而减少读取数据块的个数,节省修复成本。在基于Ceph搭建的分布式存储系统中,在修复多个硬盘故障时,将PPyramid码与其他常用的纠删码进行对比。实验结果表明,相比basic-Pyramid码,PPyramid码能降低6.3%～34.9%的修复成本和减少7.6%～63.6%的修复时间,相比LRC码、pLRC码、SHEC码、DLRC码,能降低8.6%～52%的修复成本和减少10....     

基于多斜率码链的阵列纠删码

针对当前大多阵列纠删码容错能力偏低以及构造时需要满足的约束条件较强的问题,提出一类基于码链构造的阵列纠删码。该阵列纠删码使用不同斜率码链组织数据元素和校验元素间的关系,从而能达到理论上不受限制的容错能力;而在构造时避开了类似素数约束的强约束条件,易于实用和扩展。仿真实验结果表明,相对于RS（Reed-Solomon）码,基于多斜率码链阵列纠删码在运算效率上的提升超过了2个数量级;在固定的容错能力下,存储效率能随着条块尺寸的增加而提高。此外,该类阵列码的修复代价和更新代价为一个固定常量,不会随着系统规模的扩大或容错能力的提高而增加。     

一类精确修复多个错误的Suh-Ramchandram码*

再生码因能有效的减少修复带宽更适用于分布式存储系统。利用干扰对齐技术,对于任意的参数 满足 且 ,Suh和Ramchandram构造了一类修复一个失效节点时,可达到最优修复带宽的最小存储再生码。 Chen和Shum证明了对于参数满足 的Suh-Ramchandram再生码,可以合作修复多个失效节点。基于Suh-Ramchandram再生码,给出了参数为 的编码结构,并说明这种参数为 的最小存储再生码为一类可修复多个失效节点的Suh-Ramchandram 再生码,而且这类码在修复单个或多个节点的失效时均可达到最优的修复带宽。     

虚拟网络存储系统自适应数据分配策略

在虚拟网络存储系统中通常包含各种异构的存储设备节点。基于同构系统的传统数据分配和放置策略并不能针对异构存储设备的性能差异来进行数据分配,降低了虚拟网络存储系统的性能。该文提出一种自适应的数据分配策略,能够根据存储设备节点的性能差异有效地进行数据分配。实验证明,该策略能够充分发挥异构存储设备的性能,有效解决虚拟网络存储系统的数据放置不平衡问题,提高虚拟网络存储系统的利用率。     

基于网格存储系统的自适应数据分配策略

在网格存储系统中通常包含各种异构的存储设备节点.基于同构系统的传统数据分配和放置策略并不能针对网格存储系统中异构存储设备的性能差异来进行数据分配,降低了网格存储系统的性能.提出一种自适应的数据分配策略(AD).通过运用基于虚拟磁盘性能的自适应分配策略和自适应的数据副本创建策略,AD能够根据存储设备节点的性能差异有效的进行数据分配.实验证明,自适应的数据分配策略能够充分发挥异构存储设备的性能,有效解决网格存储系统的数据放置不平衡问题,提高网格存储系统的利用率.     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法,与多副本技术相比,能够以较低的存储开销提供较高的数据可靠性;然而,纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题,提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集,然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码,以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量,从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时,依然保留着较高的容错能力,且为满足分布式存储系统的不同需求,可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示,与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比,RGRC只需要增加少量的存储开销,就能降低单节点修复14%~61%的修复成本,同时减少14%~58%的修复时间。