存储系统容错及阵列编码
|
摘要
磁盘的容错问题是大规模存储系统设计中不能回避的一个重要的问题。容错编码理论为提高存储系统数据的可靠性提供了有效的手段。
针对存储系统的一些特点,一类性能良好的二进制阵列码兼顾了系统的容错能力、编码计算复杂度和更新复杂度,被公认是存储系统容错较好的解决方案。然而此类编码并不如通信编码理论那样具有坚实的理论基础和丰富的成果。
目前,存储系统中使用比较广泛的是一些双容错的阵列码。这些编码存在着一些限制,例如：都需要将码长限制为素数才能达到其最优性能；向多容错的扩展也都比较困难。论文的重要工作体现在以下三个方面：
首先,本文在对目前常用的双容错的阵列码进行总结的基础上,使用组合数学工具,给出了一种系统的阵列码定义及表示方法；进而分析了码的标准化表示及阵列码的一些基本特性,为进一步的深入研究打下坚实的理论基础。
其次,为了根据特定的优化目标,构造出实用的编码,文本对下列两种编码结构进行了讨论：
1、校验可分阵列码。为了说明这种结构的本质规律,论文研究了置换向量代数的相关特性,并利用此工具指出了校验可分阵列码的容错性能与校验支撑置换的圈分解的关系。根据这一结论,论文利用已知的组合构造方法一哈密尔顿拉丁方构造了LS (Latin Square)阵列编码。本文证明了双容错LS码是对已有的几种双容错水平编码的统一及扩展。进而,论文使用置换向量代数构造了多容错的LS码,为校验可分阵列建立了理论的框架。此外,论文还对固定编码周期下码长限制的问题进行了研究,利用LS码的层叠构造给出了一种解决方案。
2、循环阵列码。借鉴线性编码理论的思想,论文研究了循环阵列码的基本理论,并给出了一种循环阵列码的基本构造。在此基础上,研究了最长最低密度阵列码的构造,给出了此种编码码长的上界。利用组合结构’'NRB" (Near Resolvable Balanced Incomplete Block Designs),本文给出了一种3容错最长最低密度阵列码的构造,并给出了编码清晰的代数描述,为进一步的深入研究打下基础。
最后,文章从存储系统的整体可靠性角度,以FULL-2码为例,利用阵列修复模型研究了非MDS (Maximum Distance Separable)码的实际容错能力,为系统编码方案的选择提供了数据依据。
本文的工作尝试使阵列编码这一领域的一些现有零散结论系统化,并为它们建立统一的理论基础。
Fault-tolerant is an important issue to a large-scale storage systems. Coding theory provides an effective way to improve the reliability of data storage system.
Accounting into the system's fault tolerance, coding computational complexity, and update complexity of storage systems, a class of binary array codes is regard as a good solution. But comparing to communication coding theory, there are no such a solid theoretical foundation and rich results to array codes. At present, only some 2-erasure array codes are used in storage systems, and the code length of those array codes are usually limited to prime numbers in order to achieve those optimal performance. Moreover, they are usually hard to be expanded to the multiple fault-tolerant case.
This thesis firstly summarizes the current commonly used 2-erasure array codes,then gives a systematic definitions of array codes with the language of combinatorics. Base on the definitions,we give a standardized representation of array codes,and then study some basic characteristics of array codes.
In order to construct exactly codes for specific optimized goals,the thesis studies two basic classes array codes,they are:
1.Parity-dividable array code:
In order to illustrate the law of this structure, the thesis; develops a kind of permutation-vector algebra as a research tool. With this tool,we find out the relations between the parity map permutation's circle structure and the code's fault-tolerant ability. With the well-known combinatorial structure--latin square, we construct a class of 2-erasure codes which is proved to be the expansion of several known 2-erasure codes. Further-more,with permutation-vector algebra, we gives the multi-fault-tolerant construction of LS-code. In addition, to break the limit of the short code length,we construct a class of codes named Cascade-Latin code.
2.Cyclic array codes.
The thesis gives some basic structures of cyclic array codes.Base on this, we study the longest lowest-density array codes. First we gives the upper bound to the code length of those codes. With a well known combinatorics structure:"NRB" (Near Resolv-able Balanced Incomplete Block Designs), the article presents a 3-erasure longest lowest-density array codes named T-code.
Finally, from the overall perspective, the thesis analyze the reliability of storage system base on FULL-2 code. The analysis point out that those non-MDS codes are also has good performance in some case.
The article try to build a systematic theory frame to the array codes. This is very useful to the further research.
针对存储系统的一些特点,一类性能良好的二进制阵列码兼顾了系统的容错能力、编码计算复杂度和更新复杂度,被公认是存储系统容错较好的解决方案。然而此类编码并不如通信编码理论那样具有坚实的理论基础和丰富的成果。
目前,存储系统中使用比较广泛的是一些双容错的阵列码。这些编码存在着一些限制,例如：都需要将码长限制为素数才能达到其最优性能；向多容错的扩展也都比较困难。论文的重要工作体现在以下三个方面：
首先,本文在对目前常用的双容错的阵列码进行总结的基础上,使用组合数学工具,给出了一种系统的阵列码定义及表示方法；进而分析了码的标准化表示及阵列码的一些基本特性,为进一步的深入研究打下坚实的理论基础。
其次,为了根据特定的优化目标,构造出实用的编码,文本对下列两种编码结构进行了讨论：
1、校验可分阵列码。为了说明这种结构的本质规律,论文研究了置换向量代数的相关特性,并利用此工具指出了校验可分阵列码的容错性能与校验支撑置换的圈分解的关系。根据这一结论,论文利用已知的组合构造方法一哈密尔顿拉丁方构造了LS (Latin Square)阵列编码。本文证明了双容错LS码是对已有的几种双容错水平编码的统一及扩展。进而,论文使用置换向量代数构造了多容错的LS码,为校验可分阵列建立了理论的框架。此外,论文还对固定编码周期下码长限制的问题进行了研究,利用LS码的层叠构造给出了一种解决方案。
2、循环阵列码。借鉴线性编码理论的思想,论文研究了循环阵列码的基本理论,并给出了一种循环阵列码的基本构造。在此基础上,研究了最长最低密度阵列码的构造,给出了此种编码码长的上界。利用组合结构’'NRB" (Near Resolvable Balanced Incomplete Block Designs),本文给出了一种3容错最长最低密度阵列码的构造,并给出了编码清晰的代数描述,为进一步的深入研究打下基础。
最后,文章从存储系统的整体可靠性角度,以FULL-2码为例,利用阵列修复模型研究了非MDS (Maximum Distance Separable)码的实际容错能力,为系统编码方案的选择提供了数据依据。
本文的工作尝试使阵列编码这一领域的一些现有零散结论系统化,并为它们建立统一的理论基础。
Fault-tolerant is an important issue to a large-scale storage systems. Coding theory provides an effective way to improve the reliability of data storage system.
Accounting into the system's fault tolerance, coding computational complexity, and update complexity of storage systems, a class of binary array codes is regard as a good solution. But comparing to communication coding theory, there are no such a solid theoretical foundation and rich results to array codes. At present, only some 2-erasure array codes are used in storage systems, and the code length of those array codes are usually limited to prime numbers in order to achieve those optimal performance. Moreover, they are usually hard to be expanded to the multiple fault-tolerant case.
This thesis firstly summarizes the current commonly used 2-erasure array codes,then gives a systematic definitions of array codes with the language of combinatorics. Base on the definitions,we give a standardized representation of array codes,and then study some basic characteristics of array codes.
In order to construct exactly codes for specific optimized goals,the thesis studies two basic classes array codes,they are:
1.Parity-dividable array code:
In order to illustrate the law of this structure, the thesis; develops a kind of permutation-vector algebra as a research tool. With this tool,we find out the relations between the parity map permutation's circle structure and the code's fault-tolerant ability. With the well-known combinatorial structure--latin square, we construct a class of 2-erasure codes which is proved to be the expansion of several known 2-erasure codes. Further-more,with permutation-vector algebra, we gives the multi-fault-tolerant construction of LS-code. In addition, to break the limit of the short code length,we construct a class of codes named Cascade-Latin code.
2.Cyclic array codes.
The thesis gives some basic structures of cyclic array codes.Base on this, we study the longest lowest-density array codes. First we gives the upper bound to the code length of those codes. With a well known combinatorics structure:"NRB" (Near Resolv-able Balanced Incomplete Block Designs), the article presents a 3-erasure longest lowest-density array codes named T-code.
Finally, from the overall perspective, the thesis analyze the reliability of storage system base on FULL-2 code. The analysis point out that those non-MDS codes are also has good performance in some case.
The article try to build a systematic theory frame to the array codes. This is very useful to the further research.
引文
[1]Sheng Lin, Chi Zhang, Gang Wang, Xiaoguang Liu and Jing Liu."Reliability Analysis for Full-2 Code" [J]. I-SPAN,2009,09(10):454-459.
[2]Sheng Lin, Gang Wang, Douglas S. Stones, Xiaoguang Liu and Jing Liu."T-Code: 3-Erasure Longest Lowest-Density MDS Codes" [J]. IEEE Journal on Se-lected Areas in Communications,2010, V28(2):289-296.
[3]Sheng Lin, Gang Wang, Xiaoguang Liu, Jing Liu."A Cascade-Latin Scheme to Tolerate Double Disk Failures in RAID Architectures" [J]. Journal of Elec-tronics China,2010,accepted(0):1.
[4]王刚,董沙莎,林胜,刘晓光,刘璟.”利用图的完全1-因子分解构造双容错数据布局”[J].电子学报,2006,34(12A)：2447-2450.
[5]Gang Wang, Sheng Lin, Xiaoguang Liu, Guangjun Xie, Jing Liu."Combinatorial Constructions of Multi-Erasure-Correcting Codes with Independent Parity Sym-bols for Storage Systems" [J]. The 13th IEEE Pacific Rim International Sym-posium on Dependable Computing,2007,07(1):61-68.
[6]Gang Wang, Sheng Lin, Xiaoguang Liu, Guangjun Xie, Jing Liu. "Generalizing RDP codes using the combinatorial method" [J]. The 7th IEEE International Symposium on Networking Computing and Applications,2008,08(1):93-100.
[7]Wang Gang, Liu Xiaoguang, Lin Sheng, Xie guangjun, Liu Jing."Constructing Liberation codes using Latin squares" [J]. The 14th IEEE Pacific Rim Inter-national Symposium on Dependable Computing,2008,08(1):73-80.
[8]Gang Wang, Xiaoguang Liu, Sheng Lin, Guangjun Xie and Jing Liu. "Construct-ing Double-Erasure HoVer codes Using Latin Squares" [J]. The 14th Inter-national Conference on Parallel and Distributed Systems,2008,08(1):533-540.
[9]Gang Wang, Xiaoguang Liu, Sheng Lin, Guangjun Xie and Jing Liu."Constructing Double- and Tripe-erasure-correcting Codes with High Availability Using Mirroring and Parity Approaches" [J]. IThe 13th International Conference on Parallel and Distributed Systems,2007,07(1):1.
[10]Gang Wang, Sheng Lin, Xiaoguang Liu and Jing Liu. "Representing X-Code Us-ing Latin Squares" [J]. PRDC,2009,09(Nov):1.
[11]L Hellerstein, G A Gibson, R M Karp, R H Katz, and D A Patterson. "Coding Techniques for Handling Failures in Large Disk Arrays" [J]. Algorithmica,1994,12(3):182-208.
[12]Davtd A Patterson, Garth Gibson, and Randy H Katz. "A Case for Redundant Ar-rays of Inexpensive Disks (RAID)" [J]. ACM Special Interest Group on Man-agement of Data,1988,88(1):109-116.
[13]Bianca Schroeder, Garth A Gibson."Disk Failures in the Real World:What Does an MTTF of 1,000,000 Hours Mean to You?" [J].5th USENIX Conference on File and Storage Technologies,2007,07(1):1.
[14]Lihao Xu,Jehoshua Bruck."X-Code:MDS Array Codes with Optimal Encoding" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,1999,45(1):1.
[15]Lihao Xu, Vasken Bohossian Jehoshua Bruck,David G Wagner."Low-Density MDS Codes and Factors of Complete Graphs"[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,1999,45(6):1.
[16]Cheng Huang,Lihao Xu."STAR:An Efficient Coding Scheme for Correct-ing Triple Storage Node Failures" [J]. IEEE Transactions on Computers ,2008,57(1):1.
[17]Marion Blaum John L Fan,Lihao Xu. " Soft Decoding Of Several Classes Of Array Codes " [J]. IEEE Transactions on Information Theory,2004,50(1):31--46.
[18]Marion Blaum,Jehoshua Bruck, Jai Menon. "EVENODD:An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures " [J]. IEEE TRANSACTIONS ON COMPUTERS,1995,44(2):1.
[19]Marion Blaum, Jim Brady Jehhosua Bruck,Jai Menon. "EVENODD:An Opti-mal Scheme for Tolerating Double Disk Failures in RAID Architectures" [J]. ACM SIGARCH Computer Architecture News,1994,22(1):245-254.
[20]Marion Blaum, Jehoshua Bruck,Alexander Vardy. "MDS Array Codes with Inde-pendent Parity Symbols" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,1996,42(2):1.
[21]Marion Blaum, Ron M Roth."On Lowest Density MDS Codes" [J]. IEEE Information theory workshop,1998,98(1):1.
[22]Mario Blaum, John L Fan,Lihao Xu."Soft Decoding of Several Classes of Ar-ray Codes" [J]. Proc of IEEE International Symposium on Information The-ory,2002,02(1):1.
[23]James S Plank."The RAID-6 Liberation Codes" [J].6th USENIX Conference on File and Storage Technologies,2008,08(l):1.
[24]James S Plank."A New MDS Erasure Code for RAID-6" [J]. Technical Re-port of University of Tennessee,2007,07(602):1.
[25]James S Plank. "Erasure Codes for Storage Applications" [J].4th Usenix Con-ference on File and Storage Technologies San Francisco,2005,05(1):1.
[26]James S Plank. "Enumeration of Optimal and Good Cauchy Matrices for Reed-Solomon Coding" [J]. Technical Report CS-05-570 of University of Ten-nessee,2005,05(1):1.
[27]James Lee Hafner."WEAVER Codes:Highly Fault Tolerant Erasure Codes for Storage Systems" [J].4th USENIX Conference on File and Storage Tech-nologies,2005,05(1):1.
[28]James Lee Hafne."Hover Erasure Codes for Disk Arrays" [J]. IBM Research Report,2005,RJ10352(1):1.
[29]Jeff R Hartline. "R5X0:An Efficient High Distance Parity-Based Code with Opti-mal Update Complexity" [J]. IBM Research Report,2004,RJ10322(A0408-005):1.
[30]Jeff R Hartline,KK Rao."Notes on Reliability Models for Non-MDS Erasure Codes" [J]. IBM Research Report,2006, RJ10391(1):1.
[31]Yuval Cassuto,Jehoshua Bruck."Cyclic Lowest Density MDS Array Codes" [J]. IEEE TRANSACTIONSON INFORMATION THEORY,2009,55(4):1.
[32]Erez Louidor Ron M Roth."Lowest-Density MDS Codes over Extension Alpha-bets" [J]. IEEE Intel Symposium on Information Theory,2003,03(1):1.
[33]Robert H Morelos-Zaragoza, Tadao Kasami, Shu Lin, and Hideki Imai."On Block-Coded Modulation Using Unequal Error Protection Codes Over Rayleigh-Fading Channels" [J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1998,46(1):1.
[34]Robert Morelos-Zaragoza."A Plotkin-Alamouti Superposition Coding Scheme for Cooperative Broadcasting in Wireless Networks" [J]. arXiv,2009,09012270(1):15.
[35]R.Johannesson V Pavlushkov, V V Zyablov."Achieving Unequal Error Protec-tion viaWoven Codes:Construction and Analysis" [J]. Information Pro-cesses,2005,05(1):1.
[36]Michele Albano Stefano Chessa."Replication vs Erasure Coding in Data Centric Storage for Sensor Networks" [J]. Universit'a di Pisa Dipartimento di Infor-matica Technical Report,2008, TR-08(09):1.
[37]Peter Corbett, Bob English, Atul Goel."Row-Diagonal Parity for Double Disk Failure Correction" [J]. Proceedings of the Third USENIX Conference on File and Storage Technologies San Francisco, CA,2004,31 (2):1.
[38]Ping-Hsun Hsieh, Ing-Yi Chen, Yu-TingLin, Sy-Yen Kuo."An XOR Based Reed-SolomonAlgorithm forAdvanced RAID Systems " [J]. Proceedings of the 19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Sys-tems,2004,1550(5774):1.
[39]Rebecca L Collins, James S Plank. "Assessing the Performance of Erasure Codes in the Wide-Area" [J]. The International Conference on Dependable Systems and Networks IEEE,2005,05(1):1.
[40]Dae-Woong Kim,Soon-Ho Lee,and Chan-Ik ParK. " Balanced RM2:An Im-proved Data Placement Scheme for Tolerating" [J]. LECTURE NOTES IN COMPUTER SCIENCE,2004,04(1):1.
[41]张江陵,冯丹.”海量信息存储”[M]. China:科学出版社,2003：1
[42]Colbourn, C J and Dinitz, J H."Handbook of Combinatorial Designs,Second Edition" [M]. US:CRC press,2006:1
[43]Philippe Flajolet,Robert Sedgewick."Analytic Combinatorics " [M]. Britain:Cambridge University Press,2009:1.
[44]Shu Lin,Daniel J Costello,Jr."Error Control Coding " [M]. China:China Ma-chine Press,2007:1
[45]Fred S Roberts,Barry Tesman."Applied Combinatorics" [M]. China:China Machine Press,2007:1.
[46]柯召,孙绮.”数论讲义”[M]. China:高等教育出版社,2005：1.
[47]Derek J S Robinson. "A Course in the Theory of Groups (Graduate Texts in Math-ematics)" [M]. US:Springer,1995:1.
[48]Brian Mortimer."Permutation Groups (Graduate Texts in Mathematics)" [M]. US:Springer,1996:1.
[49]David C Lay."Linear Algebra and Its Applications" [M]. US:Addison Wesley, 2002:1.
[50]Bela Bollobas."Modern Graph Theory " [M]. US:Springer,1998:1.
[51]J H 威尔金森,译者,石钟慈邓健新.”代数特征值问题”[M]. China:科学出版社,2003：1.
[52]A. Papoulis, S U Pillai."Probability, Random Variables and Stochastic Processes" [M]. Fr:McGraw-Hill College,2005:1.
[53]William Feller."An Introduction to Probability Theory and Its Applications Vol 2" [M]. US:Wiley,1971:1.
[54]William Feller."An Introduction to Probability Theory and Its Applications Vol 1" [M]. US:Wiley,1968:1.
[55]Richard P. Stanley."Enumerative Combinatorics, Volume 1" [M]. BR:Cambridge University Press,1999:1.
[56]Richard P. Stanley."Enumerative Combinatorics, Volume 2" [M]. BR:Cambridge University Press,1999:1
[57]Ronald L Graham, Donald E. Knuth, Oren Patashnik."Concrete Mathematics:A Foundation for Computer Science (2nd Edition)" [M]. US:Addison-Wesley Pub Co,2002:1.
[58]Donald E Knuth."The Art of Computer Programming-Volume 4 Fascicle 4-Generating All Trees History of Combinatorial Generation " [M]. China:机械工业出版社,2007：1.
[59]沈灏.”组合设计理论(第二版)”[M]. China:上海交通大学出版社,2008：1
[60]Joseph J Rotman."Advanced Modern Algebra " [M]. China:机械工业出版社,2007：1.
[61]J H van Lint, R M Wilson."A Course in Combinatorics" [M]. BR:Cambridge University Press,2001:1.
[62]Roger A Horn."Matrix Analysis " [M]. BR:Cambridge University Press, 1990:1
[63]Zhe-Xian Wan."Lectures on Finite Fields and Galois Rings" [M]. US:World Scientific Publishing Company,2003:1.
[64]林东岱.”代数学基础与有限域”[M]. China:高等教育出版社,2006：1.
[65]贝尔热,卜月华译.”超图——有限集的组合学”[M]. China:东南大学出版社,2002：1.
[66]王新梅,肖国镇.”纠错码——原理与方法”[M]. China:西安电子科技大学出版社,2001：1.
[67]沈世镒,陈鲁生.”信息论与编码理论”[M]. China:科学出版社.2008：1.
[68]徐明曜.”有限群导引(上册)(第2版)”[M]. China:科学出版社,2001：1.
[69]徐明曜.”有限群导引(下)”[M]. China:科学出版社,2001：1.
[70]孙继广.”矩阵扰动分析(第二版)”[M]. China:科学出版社,2001：1.
[71]刘璟.”计算机算法引论——设计与分析技术”[M]. China:科学出版社,2004：1.
[72]Yuval Cassuto. "Coding Techniques for Data-Storage Systems" [J]. PHD Thesis of California Institute of Technology Pasadena,2008,2008(1):1.
[73]Thomas Johannes Emil Schwarz."Reliability and Performance of Disk Arrays" [J]. PHD Thesis of University of California San Diego,1994,1994(1):1.
[74]谢广军.”基于SSD的虚拟化存储系统若干问题研究”[J].南开大学博士论文,2009,2009(1)：1.
[75]Darryn Bryant."A Family of Perfect Factorisations of Complete Bipartite Graphs" [J]. Journal of Combinatorial Theory,2002,SeriesA(98):328-342.
[76]Ian M Wanless."Atomic Latin Squares based on Cyclotomic Orthomorphisms" [J]. The electronic journal of combinatorics,2005,2005(1):1.
[77]Robert G Gallager."Low-Density Parity-Check Codes" [J]. IRE TRANSACTIONS,1963,IT-8(1):21-28.
[78]Tuvi Etzion, Moshe Schwartz."Perfect Constant-Weight Codes" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2004,50(9):1.
[79]D.H.Smith,L A Hughes,andS.Perkins. "A New Table of Constant Weigh t Codes of Length Greater than 28" [J]. Electron J Combin,2008,2008(1):1.
[80]David J C Mackay."Good Error-Correcting Codes Basded on Very Sparese Matrices" [J]. IEEE TRANSACTIONSON INFORMATION THEORY, 1999,45(2):1.
[81]Michael Mitzenmacher."Digital Fountains:A Survey and Look Forward" [J]. Information Theory Workshop,2004,2004(1):1.
[82]Michael Luby."LT Codes" [J]. Proceedings of the 43rd Symposium on Foun-dations of Computer Science,2002,1822(2):271.
[83]Michael G Luby, Michael Mitzenmacher,M Amin Shokrollahi,and Daniel A Spielman. "Efficient Erasure Correcting Codes" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2001,47(2):1.
[84]John W Byers,Boston,Michael Luby,Michael Mitzenmacher."Accessing Multi-ple Mirror Sites in Parallel:Using Tornado Codes to Speed Up Downloads" [J]. IEEE INFOCOM,1999,99(1):1.
[85]Michael G Luby, Michael Mitzenmacher, M Amin Shokrollahi."Analysis of Ran-dom Processes via And-Or Tree Evaluation " [J]. Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms,1998,98(1):364-373.
[86]Reed, IS and Solomon"Polynomial codes over certain finite fields" [J]. Jour-nal of the Society for Industrial and Applied Mathematics,1960,60(1):1.
[87]Charle J Colbourn,Jeffrey, H Dinitz. "Mutually orthogonal Latin squares:a brief survey of constructions" [J]. Journal of Statistical Planning and Infer-ence,2001,95(1):1.
[88]Yeow Meng Chee,San Ling."Constructions for q-Ary Constant-Weight Codes" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2007,53(1):1.
[89]Chih-Shing Tau and Tzone-I Wang."Efficient Parity Placement Schemes for Tol-erating Triple Disk Failures in RAID Architectures" [J]. Proceedings of the 17 th International Conference on Advanced Information Networking and Applica-tions,2003,03(1):1.
[90]Jon G Elerath,Michael Pecht."Enhanced Reliability Modeling of RAID Storage Systems" [J].37th Annual IEEE/IFIP International Conference on Depend- able Systems and Networks,2007,07(1):1.
[91]W K Lin, D M Chiu, Y B Lee."Erasure Code Replication Revisited" [J]. Proceedings of the Fourth International Conference on Peer-to-Peer Computing ,2004,4(1):1.
[92]Kaushik Srinivasan, Charles J Colbourn."Failed disk recovery in double erasure RAID arrays" [J]. Journal of Discrete Algorithms 5,2007,07(1):115-128.
[93]eccpage."Argrithm of RS Code[Online]" [M]. US:www dot eccpage dot com ,2005:1.
[94]research."差独立集[Online]" [M]. US:www dot research dot att dot com/njas/sequences/A025582/,2009:1.
[95]wikipedia."Artin's conjecture [Online]" [M]. US:en dot wikipedia dot org/wiki/,2009:1.
[96]att."Primes with primitive root 2[Online]" [M]. US:www dot research dot att dot com/njas/sequences/A001122,2009:1.
[2]Sheng Lin, Gang Wang, Douglas S. Stones, Xiaoguang Liu and Jing Liu."T-Code: 3-Erasure Longest Lowest-Density MDS Codes" [J]. IEEE Journal on Se-lected Areas in Communications,2010, V28(2):289-296.
[3]Sheng Lin, Gang Wang, Xiaoguang Liu, Jing Liu."A Cascade-Latin Scheme to Tolerate Double Disk Failures in RAID Architectures" [J]. Journal of Elec-tronics China,2010,accepted(0):1.
[4]王刚,董沙莎,林胜,刘晓光,刘璟.”利用图的完全1-因子分解构造双容错数据布局”[J].电子学报,2006,34(12A)：2447-2450.
[5]Gang Wang, Sheng Lin, Xiaoguang Liu, Guangjun Xie, Jing Liu."Combinatorial Constructions of Multi-Erasure-Correcting Codes with Independent Parity Sym-bols for Storage Systems" [J]. The 13th IEEE Pacific Rim International Sym-posium on Dependable Computing,2007,07(1):61-68.
[6]Gang Wang, Sheng Lin, Xiaoguang Liu, Guangjun Xie, Jing Liu. "Generalizing RDP codes using the combinatorial method" [J]. The 7th IEEE International Symposium on Networking Computing and Applications,2008,08(1):93-100.
[7]Wang Gang, Liu Xiaoguang, Lin Sheng, Xie guangjun, Liu Jing."Constructing Liberation codes using Latin squares" [J]. The 14th IEEE Pacific Rim Inter-national Symposium on Dependable Computing,2008,08(1):73-80.
[8]Gang Wang, Xiaoguang Liu, Sheng Lin, Guangjun Xie and Jing Liu. "Construct-ing Double-Erasure HoVer codes Using Latin Squares" [J]. The 14th Inter-national Conference on Parallel and Distributed Systems,2008,08(1):533-540.
[9]Gang Wang, Xiaoguang Liu, Sheng Lin, Guangjun Xie and Jing Liu."Constructing Double- and Tripe-erasure-correcting Codes with High Availability Using Mirroring and Parity Approaches" [J]. IThe 13th International Conference on Parallel and Distributed Systems,2007,07(1):1.
[10]Gang Wang, Sheng Lin, Xiaoguang Liu and Jing Liu. "Representing X-Code Us-ing Latin Squares" [J]. PRDC,2009,09(Nov):1.
[11]L Hellerstein, G A Gibson, R M Karp, R H Katz, and D A Patterson. "Coding Techniques for Handling Failures in Large Disk Arrays" [J]. Algorithmica,1994,12(3):182-208.
[12]Davtd A Patterson, Garth Gibson, and Randy H Katz. "A Case for Redundant Ar-rays of Inexpensive Disks (RAID)" [J]. ACM Special Interest Group on Man-agement of Data,1988,88(1):109-116.
[13]Bianca Schroeder, Garth A Gibson."Disk Failures in the Real World:What Does an MTTF of 1,000,000 Hours Mean to You?" [J].5th USENIX Conference on File and Storage Technologies,2007,07(1):1.
[14]Lihao Xu,Jehoshua Bruck."X-Code:MDS Array Codes with Optimal Encoding" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,1999,45(1):1.
[15]Lihao Xu, Vasken Bohossian Jehoshua Bruck,David G Wagner."Low-Density MDS Codes and Factors of Complete Graphs"[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,1999,45(6):1.
[16]Cheng Huang,Lihao Xu."STAR:An Efficient Coding Scheme for Correct-ing Triple Storage Node Failures" [J]. IEEE Transactions on Computers ,2008,57(1):1.
[17]Marion Blaum John L Fan,Lihao Xu. " Soft Decoding Of Several Classes Of Array Codes " [J]. IEEE Transactions on Information Theory,2004,50(1):31--46.
[18]Marion Blaum,Jehoshua Bruck, Jai Menon. "EVENODD:An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures " [J]. IEEE TRANSACTIONS ON COMPUTERS,1995,44(2):1.
[19]Marion Blaum, Jim Brady Jehhosua Bruck,Jai Menon. "EVENODD:An Opti-mal Scheme for Tolerating Double Disk Failures in RAID Architectures" [J]. ACM SIGARCH Computer Architecture News,1994,22(1):245-254.
[20]Marion Blaum, Jehoshua Bruck,Alexander Vardy. "MDS Array Codes with Inde-pendent Parity Symbols" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,1996,42(2):1.
[21]Marion Blaum, Ron M Roth."On Lowest Density MDS Codes" [J]. IEEE Information theory workshop,1998,98(1):1.
[22]Mario Blaum, John L Fan,Lihao Xu."Soft Decoding of Several Classes of Ar-ray Codes" [J]. Proc of IEEE International Symposium on Information The-ory,2002,02(1):1.
[23]James S Plank."The RAID-6 Liberation Codes" [J].6th USENIX Conference on File and Storage Technologies,2008,08(l):1.
[24]James S Plank."A New MDS Erasure Code for RAID-6" [J]. Technical Re-port of University of Tennessee,2007,07(602):1.
[25]James S Plank. "Erasure Codes for Storage Applications" [J].4th Usenix Con-ference on File and Storage Technologies San Francisco,2005,05(1):1.
[26]James S Plank. "Enumeration of Optimal and Good Cauchy Matrices for Reed-Solomon Coding" [J]. Technical Report CS-05-570 of University of Ten-nessee,2005,05(1):1.
[27]James Lee Hafner."WEAVER Codes:Highly Fault Tolerant Erasure Codes for Storage Systems" [J].4th USENIX Conference on File and Storage Tech-nologies,2005,05(1):1.
[28]James Lee Hafne."Hover Erasure Codes for Disk Arrays" [J]. IBM Research Report,2005,RJ10352(1):1.
[29]Jeff R Hartline. "R5X0:An Efficient High Distance Parity-Based Code with Opti-mal Update Complexity" [J]. IBM Research Report,2004,RJ10322(A0408-005):1.
[30]Jeff R Hartline,KK Rao."Notes on Reliability Models for Non-MDS Erasure Codes" [J]. IBM Research Report,2006, RJ10391(1):1.
[31]Yuval Cassuto,Jehoshua Bruck."Cyclic Lowest Density MDS Array Codes" [J]. IEEE TRANSACTIONSON INFORMATION THEORY,2009,55(4):1.
[32]Erez Louidor Ron M Roth."Lowest-Density MDS Codes over Extension Alpha-bets" [J]. IEEE Intel Symposium on Information Theory,2003,03(1):1.
[33]Robert H Morelos-Zaragoza, Tadao Kasami, Shu Lin, and Hideki Imai."On Block-Coded Modulation Using Unequal Error Protection Codes Over Rayleigh-Fading Channels" [J]. IEEE TRANSACTIONS ON COMMUNICATIONS, 1998,46(1):1.
[34]Robert Morelos-Zaragoza."A Plotkin-Alamouti Superposition Coding Scheme for Cooperative Broadcasting in Wireless Networks" [J]. arXiv,2009,09012270(1):15.
[35]R.Johannesson V Pavlushkov, V V Zyablov."Achieving Unequal Error Protec-tion viaWoven Codes:Construction and Analysis" [J]. Information Pro-cesses,2005,05(1):1.
[36]Michele Albano Stefano Chessa."Replication vs Erasure Coding in Data Centric Storage for Sensor Networks" [J]. Universit'a di Pisa Dipartimento di Infor-matica Technical Report,2008, TR-08(09):1.
[37]Peter Corbett, Bob English, Atul Goel."Row-Diagonal Parity for Double Disk Failure Correction" [J]. Proceedings of the Third USENIX Conference on File and Storage Technologies San Francisco, CA,2004,31 (2):1.
[38]Ping-Hsun Hsieh, Ing-Yi Chen, Yu-TingLin, Sy-Yen Kuo."An XOR Based Reed-SolomonAlgorithm forAdvanced RAID Systems " [J]. Proceedings of the 19th IEEE International Symposium on Defect and Fault Tolerance in VLSI Sys-tems,2004,1550(5774):1.
[39]Rebecca L Collins, James S Plank. "Assessing the Performance of Erasure Codes in the Wide-Area" [J]. The International Conference on Dependable Systems and Networks IEEE,2005,05(1):1.
[40]Dae-Woong Kim,Soon-Ho Lee,and Chan-Ik ParK. " Balanced RM2:An Im-proved Data Placement Scheme for Tolerating" [J]. LECTURE NOTES IN COMPUTER SCIENCE,2004,04(1):1.
[41]张江陵,冯丹.”海量信息存储”[M]. China:科学出版社,2003：1
[42]Colbourn, C J and Dinitz, J H."Handbook of Combinatorial Designs,Second Edition" [M]. US:CRC press,2006:1
[43]Philippe Flajolet,Robert Sedgewick."Analytic Combinatorics " [M]. Britain:Cambridge University Press,2009:1.
[44]Shu Lin,Daniel J Costello,Jr."Error Control Coding " [M]. China:China Ma-chine Press,2007:1
[45]Fred S Roberts,Barry Tesman."Applied Combinatorics" [M]. China:China Machine Press,2007:1.
[46]柯召,孙绮.”数论讲义”[M]. China:高等教育出版社,2005：1.
[47]Derek J S Robinson. "A Course in the Theory of Groups (Graduate Texts in Math-ematics)" [M]. US:Springer,1995:1.
[48]Brian Mortimer."Permutation Groups (Graduate Texts in Mathematics)" [M]. US:Springer,1996:1.
[49]David C Lay."Linear Algebra and Its Applications" [M]. US:Addison Wesley, 2002:1.
[50]Bela Bollobas."Modern Graph Theory " [M]. US:Springer,1998:1.
[51]J H 威尔金森,译者,石钟慈邓健新.”代数特征值问题”[M]. China:科学出版社,2003：1.
[52]A. Papoulis, S U Pillai."Probability, Random Variables and Stochastic Processes" [M]. Fr:McGraw-Hill College,2005:1.
[53]William Feller."An Introduction to Probability Theory and Its Applications Vol 2" [M]. US:Wiley,1971:1.
[54]William Feller."An Introduction to Probability Theory and Its Applications Vol 1" [M]. US:Wiley,1968:1.
[55]Richard P. Stanley."Enumerative Combinatorics, Volume 1" [M]. BR:Cambridge University Press,1999:1.
[56]Richard P. Stanley."Enumerative Combinatorics, Volume 2" [M]. BR:Cambridge University Press,1999:1
[57]Ronald L Graham, Donald E. Knuth, Oren Patashnik."Concrete Mathematics:A Foundation for Computer Science (2nd Edition)" [M]. US:Addison-Wesley Pub Co,2002:1.
[58]Donald E Knuth."The Art of Computer Programming-Volume 4 Fascicle 4-Generating All Trees History of Combinatorial Generation " [M]. China:机械工业出版社,2007：1.
[59]沈灏.”组合设计理论(第二版)”[M]. China:上海交通大学出版社,2008：1
[60]Joseph J Rotman."Advanced Modern Algebra " [M]. China:机械工业出版社,2007：1.
[61]J H van Lint, R M Wilson."A Course in Combinatorics" [M]. BR:Cambridge University Press,2001:1.
[62]Roger A Horn."Matrix Analysis " [M]. BR:Cambridge University Press, 1990:1
[63]Zhe-Xian Wan."Lectures on Finite Fields and Galois Rings" [M]. US:World Scientific Publishing Company,2003:1.
[64]林东岱.”代数学基础与有限域”[M]. China:高等教育出版社,2006：1.
[65]贝尔热,卜月华译.”超图——有限集的组合学”[M]. China:东南大学出版社,2002：1.
[66]王新梅,肖国镇.”纠错码——原理与方法”[M]. China:西安电子科技大学出版社,2001：1.
[67]沈世镒,陈鲁生.”信息论与编码理论”[M]. China:科学出版社.2008：1.
[68]徐明曜.”有限群导引(上册)(第2版)”[M]. China:科学出版社,2001：1.
[69]徐明曜.”有限群导引(下)”[M]. China:科学出版社,2001：1.
[70]孙继广.”矩阵扰动分析(第二版)”[M]. China:科学出版社,2001：1.
[71]刘璟.”计算机算法引论——设计与分析技术”[M]. China:科学出版社,2004：1.
[72]Yuval Cassuto. "Coding Techniques for Data-Storage Systems" [J]. PHD Thesis of California Institute of Technology Pasadena,2008,2008(1):1.
[73]Thomas Johannes Emil Schwarz."Reliability and Performance of Disk Arrays" [J]. PHD Thesis of University of California San Diego,1994,1994(1):1.
[74]谢广军.”基于SSD的虚拟化存储系统若干问题研究”[J].南开大学博士论文,2009,2009(1)：1.
[75]Darryn Bryant."A Family of Perfect Factorisations of Complete Bipartite Graphs" [J]. Journal of Combinatorial Theory,2002,SeriesA(98):328-342.
[76]Ian M Wanless."Atomic Latin Squares based on Cyclotomic Orthomorphisms" [J]. The electronic journal of combinatorics,2005,2005(1):1.
[77]Robert G Gallager."Low-Density Parity-Check Codes" [J]. IRE TRANSACTIONS,1963,IT-8(1):21-28.
[78]Tuvi Etzion, Moshe Schwartz."Perfect Constant-Weight Codes" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2004,50(9):1.
[79]D.H.Smith,L A Hughes,andS.Perkins. "A New Table of Constant Weigh t Codes of Length Greater than 28" [J]. Electron J Combin,2008,2008(1):1.
[80]David J C Mackay."Good Error-Correcting Codes Basded on Very Sparese Matrices" [J]. IEEE TRANSACTIONSON INFORMATION THEORY, 1999,45(2):1.
[81]Michael Mitzenmacher."Digital Fountains:A Survey and Look Forward" [J]. Information Theory Workshop,2004,2004(1):1.
[82]Michael Luby."LT Codes" [J]. Proceedings of the 43rd Symposium on Foun-dations of Computer Science,2002,1822(2):271.
[83]Michael G Luby, Michael Mitzenmacher,M Amin Shokrollahi,and Daniel A Spielman. "Efficient Erasure Correcting Codes" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2001,47(2):1.
[84]John W Byers,Boston,Michael Luby,Michael Mitzenmacher."Accessing Multi-ple Mirror Sites in Parallel:Using Tornado Codes to Speed Up Downloads" [J]. IEEE INFOCOM,1999,99(1):1.
[85]Michael G Luby, Michael Mitzenmacher, M Amin Shokrollahi."Analysis of Ran-dom Processes via And-Or Tree Evaluation " [J]. Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms,1998,98(1):364-373.
[86]Reed, IS and Solomon"Polynomial codes over certain finite fields" [J]. Jour-nal of the Society for Industrial and Applied Mathematics,1960,60(1):1.
[87]Charle J Colbourn,Jeffrey, H Dinitz. "Mutually orthogonal Latin squares:a brief survey of constructions" [J]. Journal of Statistical Planning and Infer-ence,2001,95(1):1.
[88]Yeow Meng Chee,San Ling."Constructions for q-Ary Constant-Weight Codes" [J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2007,53(1):1.
[89]Chih-Shing Tau and Tzone-I Wang."Efficient Parity Placement Schemes for Tol-erating Triple Disk Failures in RAID Architectures" [J]. Proceedings of the 17 th International Conference on Advanced Information Networking and Applica-tions,2003,03(1):1.
[90]Jon G Elerath,Michael Pecht."Enhanced Reliability Modeling of RAID Storage Systems" [J].37th Annual IEEE/IFIP International Conference on Depend- able Systems and Networks,2007,07(1):1.
[91]W K Lin, D M Chiu, Y B Lee."Erasure Code Replication Revisited" [J]. Proceedings of the Fourth International Conference on Peer-to-Peer Computing ,2004,4(1):1.
[92]Kaushik Srinivasan, Charles J Colbourn."Failed disk recovery in double erasure RAID arrays" [J]. Journal of Discrete Algorithms 5,2007,07(1):115-128.
[93]eccpage."Argrithm of RS Code[Online]" [M]. US:www dot eccpage dot com ,2005:1.
[94]research."差独立集[Online]" [M]. US:www dot research dot att dot com/njas/sequences/A025582/,2009:1.
[95]wikipedia."Artin's conjecture [Online]" [M]. US:en dot wikipedia dot org/wiki/,2009:1.
[96]att."Primes with primitive root 2[Online]" [M]. US:www dot research dot att dot com/njas/sequences/A001122,2009:1.