本文關(guān)鍵詞： 網(wǎng)絡(luò)編碼 分布式存儲 節(jié)點(diǎn)修復(fù) 網(wǎng)絡(luò)信息流圖 數(shù)據(jù)容錯(cuò)　出處：《西南交通大學(xué)》2012年碩士論文　論文類型：學(xué)位論文

【摘要】：圖靈獎(jiǎng)獲得者Jim Gray在其獲獎(jiǎng)演說時(shí),對全球數(shù)據(jù)量的增長給出了一條新的經(jīng)驗(yàn)定律：未來每18個(gè)月產(chǎn)生的數(shù)據(jù)量等于有史以來的數(shù)據(jù)量之和!近些年,IT行業(yè)的飛速發(fā)展與互聯(lián)網(wǎng)的廣泛應(yīng)用,帶來了全球信息資源的爆炸性增長,各種應(yīng)用對存儲系統(tǒng)提出了越來越高的要求。分布式存儲系統(tǒng),因其廉價(jià)性及高擴(kuò)展性等優(yōu)點(diǎn),而倍受人們關(guān)注,理所應(yīng)當(dāng)?shù)爻蔀榱撕Ａ繑?shù)據(jù)存儲的首要選擇。然而,由于分布式存儲系統(tǒng)中各個(gè)存儲節(jié)點(diǎn)的可用性不高,為保證數(shù)據(jù)可靠性,系統(tǒng)會(huì)頻繁的進(jìn)行節(jié)點(diǎn)修復(fù)。因此,如何有效地進(jìn)行節(jié)點(diǎn)修復(fù)就成為了亟待解決的問題,對其進(jìn)行的深入的研究,具有很重要的現(xiàn)實(shí)意義。 根據(jù)網(wǎng)絡(luò)編碼定理,分布式存儲系統(tǒng)中的節(jié)點(diǎn)修復(fù)問題可以抽象成為一個(gè)基于網(wǎng)絡(luò)信息流圖的數(shù)據(jù)傳輸模型,從而可以利用圖論中網(wǎng)絡(luò)流的相關(guān)理論來分析節(jié)點(diǎn)修復(fù)時(shí)帶寬消耗的理論下界。之前的大部分研究主要針對的是單節(jié)點(diǎn)修復(fù)的情形,然而,實(shí)際中多節(jié)點(diǎn)同時(shí)修復(fù)的情形非常常見�，F(xiàn)有的針對多節(jié)點(diǎn)同時(shí)修復(fù)的模型都是非對稱的,這會(huì)增加實(shí)際系統(tǒng)設(shè)計(jì)的復(fù)雜度。針對此問題,本文在現(xiàn)有模型的基礎(chǔ)上,提出了一種對稱的多節(jié)點(diǎn)協(xié)作修復(fù)模型(Symmetric Mutually Cooperative Recovery, SMCR),使得每個(gè)待修復(fù)的新節(jié)點(diǎn)之間可以進(jìn)行等量的數(shù)據(jù)交換,并且計(jì)算出了模型在不同冗余度下節(jié)點(diǎn)修復(fù)帶寬的理論下界。 最后,本文將SMCR修復(fù)模型與不協(xié)作的節(jié)點(diǎn)修復(fù)模型進(jìn)行比較。經(jīng)過數(shù)值分析,發(fā)現(xiàn)在節(jié)點(diǎn)數(shù)據(jù)冗余度較低時(shí),SMCR的修復(fù)帶寬的理論下界好于不協(xié)作的修復(fù)模型。在數(shù)據(jù)冗余度比較高時(shí),SMCR的修復(fù)帶寬的理論下界與不協(xié)作的各有優(yōu)劣,不同的參數(shù)會(huì)出現(xiàn)不同的結(jié)果。隨后,本文對其進(jìn)行了深入的分析,給出了一止匕SMCR修復(fù)模型好于不協(xié)作的節(jié)點(diǎn)修復(fù)模型的充分條件,為實(shí)際分布式存儲系統(tǒng)的設(shè)計(jì)提供了的理論指導(dǎo)。
[Abstract]:In his speech, Turing Prize winner Jim Gray presented a new empirical law on the growth of global data volumes: the amount of data generated every 18 months over the next 18 months is equal to the sum of data in history! In recent years, the rapid development of IT industry and the wide application of the Internet have brought the explosive growth of global information resources. Because of its advantages such as low cost and high scalability, it has attracted much attention and become the first choice of mass data storage. However, the availability of each storage node in distributed storage system is not high. In order to ensure the reliability of the data, the system will frequently carry out node repair. Therefore, how to effectively repair the node has become a problem to be solved. Has very important realistic significance. According to the network coding theorem, the node repair problem in distributed storage system can be abstracted into a data transmission model based on network information flow graph. Therefore, we can use the theory of network flow in graph theory to analyze the theoretical lower bound of bandwidth consumption in node repair. Most of the previous studies focus on the case of single node repair, however. In practice, multi-node repair is very common. Existing models for multi-node simultaneous repair are asymmetric, which will increase the complexity of the actual system design. Based on the existing models, a symmetric Mutually Cooperative Recovery, a symmetric multi-node cooperative repair model, is proposed in this paper. The SMCRO makes it possible to exchange the same amount of data between each new node to be repaired and calculates the theoretical lower bound of the repair bandwidth of the model under different redundancy. Finally, this paper compares the SMCR repair model with the non-cooperative node repair model. Through numerical analysis, it is found that the node data redundancy is low. The theoretical lower bound of repair bandwidth of SMCR is better than that of non-cooperative repair model. When the data redundancy is high, the theoretical lower bound and non-cooperation of SMCR have their own advantages and disadvantages. Different parameters will produce different results. Then, this paper gives a thorough analysis of the SMCR repair model is better than the non-cooperative node repair model sufficient conditions. It provides theoretical guidance for the design of distributed storage system.
【學(xué)位授予單位】：西南交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2012
【分類號】：TP333

【共引文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳榮軍;Dijkstra算法的應(yīng)用[J];常州工學(xué)院學(xué)報(bào);1999年02期

2 黨愷謙;關(guān)于圖的圈的一個(gè)充分條件[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1990年01期

3 黨愷謙;2連通的k正則偶圖的周長[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1991年01期

4 黨愷謙;k正則的2.■_(1.3)圖的周長[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1991年03期

5 黨愷謙;圖的周長[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1993年01期

6 黨愷謙;無爪圖的周長[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1993年06期

7 車向凱;具有二分劃(A_1,A_2)的2-連通偶圖為(A_1,A_2)Hamilton連通的一個(gè)充分條件[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年01期

8 黨愷謙;圖的周長[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1996年05期

9 車向凱;3-連通無爪圖的周長[J];東北大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年03期

10 張忠?guī)�，，唐小�?非負(fù)權(quán)最短路問題的一種簡便算法[J];電子科技大學(xué)學(xué)報(bào);1995年05期

相關(guān)會(huì)議論文 前1條

1 賈傳亮;許保光;池宏;計(jì)雷;;基于網(wǎng)絡(luò)流的航空公司飛行員人力資源規(guī)劃模型[A];中國優(yōu)選法統(tǒng)籌法與經(jīng)濟(jì)數(shù)學(xué)研究會(huì)第七屆全國會(huì)員代表大會(huì)暨第七屆中國管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

相關(guān)博士學(xué)位論文 前8條

1 陳春妹;路網(wǎng)容量研究[D];北京工業(yè)大學(xué);2002年

2 侯新民;網(wǎng)絡(luò)（圖）廣義直徑的研究[D];大連理工大學(xué);2002年

3 袁宗明;天然氣集輸管網(wǎng)系統(tǒng)最優(yōu)規(guī)劃研究[D];西南石油學(xué)院;2002年

4 毛華;偏序集理論在擬陣論中的應(yīng)用[D];西安電子科技大學(xué);2002年

5 楊有龍;基于圖形模型的智能優(yōu)化[D];西北工業(yè)大學(xué);2003年

6 趙國鋒;基于IP/MPLS骨干網(wǎng)的動(dòng)態(tài)業(yè)務(wù)流量矩陣測量及應(yīng)用研究[D];重慶大學(xué);2003年

7 艾達(dá);視頻通信抗分組丟失技術(shù)研究[D];西安電子科技大學(xué);2006年

8 肖秦琨;基于動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)的智能自主優(yōu)化機(jī)制研究[D];西北工業(yè)大學(xué);2006年

相關(guān)碩士學(xué)位論文 前10條

1 王立欣;關(guān)于樹的整和數(shù)的研究[D];河北工業(yè)大學(xué);2000年

2 吳夢虹;一類圈優(yōu)美圖的研究[D];河北工業(yè)大學(xué);2002年

3 冷俊敏;電力AM/FM/GIS綜合管理系統(tǒng)的開發(fā)[D];華北電力（北京）大學(xué);2002年

4 孫海娜;超圖各參數(shù)間的關(guān)系以及超圖的邊色數(shù)問題[D];浙江師范大學(xué);2002年

5 胡紅萍;有向圖Hamilton性質(zhì)的研究[D];華北工學(xué)院;2002年

6 邵澤玲;外平面圖的松弛競賽色數(shù)[D];河北工業(yè)大學(xué);2003年

7 王洪順;GIS在交通管理中的應(yīng)用以及最短路徑分析的實(shí)現(xiàn)研究[D];新疆農(nóng)業(yè)大學(xué);2003年

8 夏新海;物流配送車輛調(diào)度優(yōu)化研究[D];武漢理工大學(xué);2004年

9 王鵬;LDPC碼的編譯碼原理及編碼設(shè)計(jì)[D];西安電子科技大學(xué);2004年

10 劉書香;遺傳算法在礦山運(yùn)輸車輛優(yōu)化調(diào)度中的應(yīng)用研究[D];西安建筑科技大學(xué);2004年

本文編號：1467309