(3.238.173.209) 您好!臺灣時間:2021/05/16 21:33
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:林語亭
研究生(外文):Yu-Ting Lin
論文名稱:使用里德所羅門碼加強大型磁碟陣列系統之可靠度
論文名稱(外文):Enhancing RAID System Reliability Using Reed Solomon Code
指導教授:郭斯彥郭斯彥引用關係
指導教授(外文):Sy-Yen Kuo
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:英文
論文頁數:78
中文關鍵詞:錯誤更正碼可靠度里德所羅門碼磁碟陣列
外文關鍵詞:RAIDreliabilityReed Solomon CodeRS
相關次數:
  • 被引用被引用:0
  • 點閱點閱:220
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
隨著網際網路及各種多媒體資料庫的發展,一個大型的儲存系統(如大型磁碟陣列系統)可以說是越來越重要,除了必須提供高速的介面供使用者存取,還必須提供非常穩定的資料保存環境,以防寶貴的資料因為各種可能的狀況而喪失。為了達到如此的目的,釵h系統容錯的方式便應運而生。我們希望能透過硬體或軟體的方式,使得資訊能夠可靠且正確的來做傳遞或是保存以因應各種可能使資料受到威脅的可能狀況(諸如熱雜訊、機器故障、不佳的保存環境或傳播通道等)。在各種容錯技術中,又以錯誤更正碼為最重要。不同的錯誤更正碼常被設計用來適應在各種不同的環境中,以因應各種環境可能遇到的資訊喪失。

本論文將提出的針對”大型磁碟陣列系統”所設計的特用”里德所羅門碼”演算法,便是使用發展已趨成熟的里德所羅門碼,針對大型磁碟陣列系統特有的環境所做的特別改良與設計,用來因應兩顆以上磁碟同時失效的狀況in RAID system,使失效硬碟的資料能夠完整的恢復,使系統能在不中斷的狀況下正常的運作。
Because of rapid development of inter-net and multi-media data bases, need for a big storage system becomes more and more important. The advanced storage system must provide rapid data processing ability and stable storage environment in order to avoid data losing. For the purpose mentioned above, many fault-tolerant methods are derived. We hope that information can be transmitted and stored correctly by some methods using software or hardware when there are disturbances, like heat noise, broken machine, noisy transmitting channel and so on. Error control coding is the most important method within all error concealing methods. Different error correcting codes are designed in different environments in order to avoid error losing.

In the thesis, we will use Reed Solomon Code which is designed according to properties of advanced RAID system to handle two disk failures in RAID system. Therefore, the failed data in disks can be recovered and system still can work as usual without broken.
Contents

Chinese Abstract

English Abstract

1 Introduction ...…………...…………………………………………………………1
1.1 Motivation and Purpose of the Thesis……………………….…………….…..2
1.2 RAID (Redundant Array of Inexpensive Disks)………………………………3
1.2.1 RAID 0………………………………………………………………...4
1.2.2 RAID 1…………………………………………………………..…….4
1.2.3 RAID 0+1……………………………………………………………...6
1.2.4 RAID 5………………………………………………………………...6
1.2.5 RAID 6………………………………………………………………...7
1.3 Proposed algorithm and contributions ………………………………………...8
1.4 Organization of the thesis……………………………………………………...8
2 Introduction of Reed Solomon Code…………………………………………..10
2.1 Basic properties of RS codes……………………………………………………..11
2.2 The basic concepts of finite field and BCH codes….............................................12
2.2.1 Finite Field……………………………………………………………..12
2.2.2 The construction of ………………………………………….15
2.2.3 BCH bound (Designed Distance)………………………………………19
2.3 Basic Design flow and Encoding of RS Codes…………………………………..19
2.3.1 Basic Design of RS codes……………………………………………...19
2.3.2 Systematic coding………………………………………………..…….21
2.4 Decoding of RS Codes…………………………………………………………...23
2.4.1 Peterson-Gorenstein-Zierler decoding algorithm………………………23
2.4.2 Decoding agorithms used in industrial circles……………………..…..25
3 Construction of RAID6 system………………………………………………...28
3.1 Data Mapping from Hard disks to RS code……………………………………...28
3.2 Design flow and Data writing (Encoding of RS codes)………………………….30
3.2.1 Basic Design flow and encoding…………………………………...…..30
3.2.2 Data Update…………………………………………………………….32
3.2.3 Shortened Code………………………………………………………...33
3.3 Data reading(Decoding of RS codes)…………………………………………….34
4 System Optimization and Related Circuits Design……………………..…….39
4.1 Circuits Design for Multiplier……………………………………………………40
4.1.1 General Multiplier……………………………………………………...40
4.1.2 Constant Multiplier……………………………………….……………42
4.2 System Optimization and Circuits Implementation of RS code Codec
for RAID 6 Architectur……………..……………………………………………44
4.2.1 Selection of Roots for Generator Polynomial………………………….44
4.2.2 Design for RS Encoder…………………………………………………45
4.2.3 Design of RS Decoder………………………………………………..51
5 Comparisons and analysis with the existing RAID-6 algorithm……………..54
5.1 EvenOdd Code………………………………………………………………..….54
5.2 comparisons between EvenOdd Code and RS Code…………………………..…57
5.2.1 data mapping…………………………………………………………...58
5.2.2 Update Complexity…………………………………………………….58
5.2.3 Analysis of coding computation……………………………………...59
5.3 A comparison sheet.………………………………………………………………62
6 Conclusions and Future works…………………………………………………64
6.1 conclusions……………………………………………………………...………..64
6.2 Future work………………………………………………………………………65

Reference

Appendix
cm.java – construction of the list of constant multipliers in
gp.java – to compute the number of XOR gates used by encoding.


List of Figures


1.1:Block diagram of a typical data transmission or storage system……………….....2
1.2 RAID level 0………………………………………………………………………4
1.3 RAID level 1……………………………………………………………………....5
1.4 RAID level 0+1……………………………………………………………………5
1.5 RAID level 6………………………………………………………………………7
2.1: The mathematical background of RS codes……………………………………..12
2.2:Systematic coding………………………………………………………………..22
2.3:Decoding flow of Reed Solomon Code………………………………………….26
3.1:Encode m(x) by RS Encoder……………………………………………………..29
3.2:Data Mapping…………………………………………………………………….29
4.1: Circuit diagram for a general multiplier in GF(24 )……………………………..41
4.2: Logic-circuit diagram of ……………………………………………….42
4.3: General CRC division circuits………………………………………………..…46
4.4:Circuit to solve 2 erasures……………………………………………………..…52
5.1: Structure of EvenOdd Code……………………………………………………..55
5.2: Encoding of an (7,5) EvenOdd Code…………………………………………....56
5.3: Decoding of an (7,5) EvenOdd Code (2-erasures)……………………………....56
5.4: 3-Dimention structure of EvenOdd Code……………………………………..…58
5.5:The number of XOR gates to encode m bytes of RS code……………………….60
5.6:The number of XOR gates to encode m*(m-1) bytes…………………………....61

List of Tables


2.1:Operation Table for GF(3)………………………………………………………..14
2.2:Primitive polynomials……………………………………………………………16
2.3:elements in ……………………………………………………………..17
3.1:Elements in …………………………………………………………….30
4.1:Elements in GF(24 )………………………………………………………………39
4.2:List of Contant Multiplier for ………………………………………….44
4.3:List of Checksum Table…………………………………………………………..48
5.1: a comparison sheet between RS code and EvenOdd Code…………………...…63
Bibliography


[1] D.V. Sarwate, N. R. Shanbhag, ”High-Speed Architectures for Reed-Solomon Decoders”, IEEE Transactions on VLSI,2001

[2] Error-Control Coding for Data Network, I.S. Reed and X. Chen,Kluwer, 1999.

[3] M. Blaum, J. Brady, J. Bruck, and J. Menon, “ EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures,” IEEE Trans. Comput., vol 44, pp. 192-202, Feb. 1995.

[4] J. S. Plank. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Software – Practice& Experience, 27(9):995–1012, September 1997.

[5] J . S. Plank. Correction to the 1997 Tutorial on Reed-Solomon Coding. Technical Report UT-CS-03-504, University of Tennessee, April, 2003.

[6] Blaum, M.; Brady, J.; Bruck, J.; Menon, J.; “EVENODD: an optimal scheme for
tolerating double disk failures in RAID architectures”, Computer Architecture, 1994., Proceedings the 21st Annual International Symposium on , 1994 , Page(s): 245 -254

[7] S. Baylor, P. Corbett, and C. Park. Efficient method for providing fault tolerance against double device failures in multiple device systems, January 1999. U. S. Patent 5,862,158.

[8] E. R. Berlekamp. Key Papers in the Development of Coding Theory. IEEE Press, New York, NY, 1974.

[9] E. R. Berlekamp. Algebraic Coding Theory. Aegean Park Press, Walnut Creek, CA, 1984.

[10] M. Blaum and R. M. Roth. On lowest density MDS codes. IEEE Transactions on Information Theory, 45:46–59, 1999.

[11] A. Brown and D. A. Patterson. Towards availability benchmarks: A case study of software RAID systems. In Proceedings of the USENIX Technical Conference, pages 263–276, 2000.

[12] P. Chen, E. Lee, G. Gibson, R. Katz, and D. Patterson. RAID: high-performance, reliable secondary storage. ACM Computing Surveys, 26:145–185, 1994.

[13] B. E. Clark, F. D. Lawlor, W. E. Schmidt-Stumpf, T. J. Stewart, and J. D. Timms, Jr. Parity spreading to enhance storage access, August 1998. U. S. Patent 4,761,785.

[13] R. G. Gallager. Low-Density Parity-Check Codes. MIT Press, Cambridge, MA, 1962.

[14] G. A. Gibson, L. Hellerstein, R. M. Karp, R. H. Katz, and D. A. Patterson. Failure correction techniques for large disk arrays. In Proceedings of International Conference on Architectural Support for Programming Languages and Operating Systems, pages 123–132, Boston, MA, 1989.

[15] J. H. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Francisco, CA, 2003.

[16] I. N. Herstein. Topics in Algebra. John Wiley and Sons, New York, NY, 1985.

[17] R. Lidl and H. Niederreiter. Introduction to finite fields and their applications. Cambridge University Press, Cambridge, UK, 1994.

[18] M. Luby. LT codes. In Proceedings of the 43rd Annual IEEE Symposium on the Foundations of ComputerScience, pages 271–280, 2002.

[19] M. G. Luby, M. Mitzenmacher, A. Shokrollahi, and D. A. Spielman. Efficient erasure correcting codes. IEEE Transactions on Information Theory, 47:569–584, 2001.

[20] D. J. C. MacKay. Information Theory, Inference, and Learning Algorithms. http://www.inference.phy.cam.ac.uk/mackay/itprnn/.

[21] F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. Northolland, Amsterdam, The Netherlands, 1977.

[22] P. Massiglia. The RAID Book. The RAID Advisory Board, Inc., St. Peter, MN, 1997.

[23] J. D. McCalpin. Sustainable memory bandwidth in current high performance computers. http://home.austin.rr.com/mccalpinpapers/bandwidth/bandwidth.html.

[24] D. Patterson, G. Gibson, and R. H. Katz. Reliable arrays of inexpensive disks (RAID). In Proceedings of the ACM SIGMOD Conference, pages 109– 116, 1988.

[25] Mandana Vaziriy, Nancy Lynchy and Jeannette Wingz, Proving Correctness of a Controller Algorithm for the RAID Level 5 System

[26] F. Preparata and M. Shamos. Computational Geometry: an Introduction. Springer-Verlag, 1988.

[27] I. S. Reed and G. Solomon. Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8:300–304, 1960.

[28] A. Shokrollahi. Raptor codes, 2003.

[29] D. P. Siewiorek and R. S. Swarz. Reliable Computer Systems: Design and Evaluation. A. K. Peters, Ltd., Natik, MA, 1998.

[30] Storage Performance Council. SPC benchmark. http://www.storageperformance.org.

[31] L. Xu and J. Bruck. X-code: MDS array codes with optimal encoding. IEEE Transactions on Information Theory, pages 272–276, 1999.
[32] G. V. Zaitsev, V. A. Zinovev, and N. V. Semakov. Minimum-check-density codes for correcting bytes of errors. Problems in Information Transmission, 19:29–37, 1983.
[33] E. Anderson, R. Swaminathan, A. Veitch, G. Alvarez, and J. Wilkes. Selecting raid levels for disk arrays. In Conference on File and Storage Technologies (FAST), pages 189–201, 2002.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊