摘 要: 通過對網(wǎng)絡(luò)編碼理論和現(xiàn)有P2P文件共享系統(tǒng)的深入研究,設(shè)計了一種基于線性網(wǎng)絡(luò)編碼的P2P文件共享系統(tǒng)。該系統(tǒng)的優(yōu)點是解決了現(xiàn)有P2P文件共享系統(tǒng)中存在的不能充分利用網(wǎng)絡(luò)資源、“種子”節(jié)點突然退出造成文件下載不完等問題。實驗結(jié)果表明,該系統(tǒng)克服了現(xiàn)有系統(tǒng)中存在的問題,同時也提高了整個系統(tǒng)的吞吐量并增強了系統(tǒng)的穩(wěn)定性。
關(guān)鍵詞: 對等網(wǎng)絡(luò);網(wǎng)絡(luò)編碼;比特洪流
對等網(wǎng)絡(luò)P2P(Peer-to-Peer Network)是分布式系統(tǒng)與計算機(jī)結(jié)合的產(chǎn)物,是采用對等模式工作的計算機(jī)網(wǎng)絡(luò),它開發(fā)了網(wǎng)絡(luò)中每個節(jié)點的網(wǎng)絡(luò)能力?;赑2P的文件共享系統(tǒng)擺脫了原有基于客戶/服務(wù)器(C/S)體系結(jié)構(gòu)集中式訪問模式的束縛,通過匯集網(wǎng)絡(luò)邊緣可用資源提供服務(wù),現(xiàn)已成為Internet上下載大文件的主流模型。但是現(xiàn)有的P2P文件共享系統(tǒng)也存在一些問題:
?。?)如果“種子”節(jié)點突然離開P2P網(wǎng)絡(luò),可能造成網(wǎng)絡(luò)中其余計算機(jī)不能完整地下載源文件。
?。?)一個好的數(shù)據(jù)塊調(diào)度算法時間復(fù)雜度高,執(zhí)行效率低,這將影響到客戶端的下載時間。
?。?)在現(xiàn)有的P2P通信網(wǎng)絡(luò)中,信息的傳輸都是從源節(jié)點出發(fā),經(jīng)過中間節(jié)點的存儲轉(zhuǎn)發(fā)到目的節(jié)點。在這個過程中,中間節(jié)點起著中繼作用,其并未對收到的信息做任何處理,這種傳統(tǒng)的通信模式很難達(dá)到網(wǎng)絡(luò)的最大吞吐量。
本文在對網(wǎng)絡(luò)編碼和現(xiàn)有的P2P文件共享系統(tǒng)工作原理研究的基礎(chǔ)上,提出了一種基于線性網(wǎng)絡(luò)編碼的文件共享系統(tǒng)實現(xiàn)方案。利用網(wǎng)絡(luò)編碼的優(yōu)勢,來解決現(xiàn)有P2P文件共享系統(tǒng)中存在的問題,完善和增強系統(tǒng)的性能。
1.3 線性網(wǎng)絡(luò)編譯碼器實現(xiàn)算法說明及性能分析
在實際工作中,P2P網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)經(jīng)常會隨著節(jié)點的加入或退出發(fā)生變化,所以網(wǎng)絡(luò)編碼采用隨機(jī)線性網(wǎng)絡(luò)編碼[4],即網(wǎng)絡(luò)節(jié)點對編碼系數(shù)是隨機(jī)選取的,并且對輸入數(shù)據(jù)包進(jìn)行線性操作,其具有良好的拓?fù)溥m應(yīng)性。但從網(wǎng)絡(luò)編碼原理分析可知,網(wǎng)絡(luò)編碼算法時間復(fù)雜度較高,因此,本文在編譯碼器的實現(xiàn)程序中采取了一些優(yōu)化策略,以盡可能降低計算量,提高編譯碼的速度。策略如下:
?。?)有限域運算。編譯碼過程中需要有大量的有限域乘除運算,本程序采用離散對數(shù)方法來減少運算量。利用有限域中特殊元素生成元,將有限域中任何非零元素唯一的表示為生成元的指數(shù)形式,因此有限域元素相乘除的運算都可轉(zhuǎn)化為指數(shù)運算。
?。?)對源文件采用“代”(Generation)劃分[3]。P2P網(wǎng)絡(luò)中等待下載的文件通常都在百兆以上,數(shù)量龐大的源文件分組使相應(yīng)的編碼矩陣和解碼矩陣維數(shù)很大,加劇了編譯碼運算過程中的運算量。本文對源文件采用“代”劃分的方法,以達(dá)到有效降低編譯碼矩陣維數(shù)、簡化運算量的目的。
?。?)稀疏矩陣。網(wǎng)絡(luò)編碼的編碼系數(shù)是隨機(jī)選擇的,隨機(jī)選擇的編碼系數(shù)是均勻分布的,編碼系數(shù)中零的個數(shù)很少,所以程序的編碼矩陣選擇使用稀疏矩陣[5],這樣可以有效降低編譯碼計算量。
基于隨機(jī)線性網(wǎng)絡(luò)編碼的原理和上述算法優(yōu)化策略,本文采用C++在Linux環(huán)境下實現(xiàn)了傳統(tǒng)的線性網(wǎng)絡(luò)編碼編譯碼器和隨機(jī)線性網(wǎng)絡(luò)編碼編譯碼器(采用上述優(yōu)化策略)。用100 MB的文件在兩種編譯碼器上分別測試了分組大小從64 KB到2 MB的編譯碼運行速率。通過分析圖2的編譯碼器性能圖可以得到,經(jīng)過優(yōu)化策略的編譯碼器性能明顯優(yōu)于傳統(tǒng)網(wǎng)絡(luò)編碼的編譯碼器。實驗結(jié)果證明,將上述策略應(yīng)用于網(wǎng)絡(luò)編碼的編譯碼器是有效的,所以選擇合適大小的分組可以充分發(fā)揮編譯碼器的性能。
2 線性網(wǎng)絡(luò)編碼在P2P文件共享系統(tǒng)中的應(yīng)用
當(dāng)前,BitTorrent是使用最為廣泛的P2P文件共享系統(tǒng)之一[6]。通過對BitTorrent系統(tǒng)工作原理、線性網(wǎng)絡(luò)編碼理論的研究和分析,將本文提出的線性網(wǎng)絡(luò)編譯碼器應(yīng)用到BitTorrent客戶端系統(tǒng)中,實現(xiàn)基于線性網(wǎng)絡(luò)編碼的P2P文件共享系統(tǒng)。圖3是基于線性網(wǎng)絡(luò)編碼的BitTorrent系統(tǒng)框架圖。該系統(tǒng)主要由5個模塊組成:(1)傳輸機(jī)制模塊:提供Socket的通信,收發(fā)消息。(2)編碼器模塊:對數(shù)據(jù)進(jìn)行編碼。如果當(dāng)前的節(jié)點是種子節(jié)點,就對原始數(shù)據(jù)進(jìn)行編碼;如果是非種子節(jié)點,就對當(dāng)前收到的同一“代”的編碼過的數(shù)據(jù)進(jìn)行再次編碼。(3)線性檢測模塊:對收到數(shù)據(jù)包的編碼向量進(jìn)行線性相關(guān)性的檢測。如果線性無關(guān),將該數(shù)據(jù)包存放在臨時文件中;如果線性相關(guān),將該數(shù)據(jù)包拋棄;如果臨時文件存放的線性無關(guān)的數(shù)據(jù)包達(dá)到一定數(shù)量,就可以進(jìn)行譯碼。(4)譯碼器模塊:對收到編碼過的數(shù)據(jù)包進(jìn)行譯碼,恢復(fù)源文件。(5)成員管理模塊:讓當(dāng)前客戶端能夠與系統(tǒng)中一定數(shù)目的其他客戶端建立連接,并在運行過程中實現(xiàn)對與其連接的其他客戶端進(jìn)行淘汰和更新。
將基于線性網(wǎng)絡(luò)編碼的BitTorrent文件共享系統(tǒng)運行在實驗室實際的網(wǎng)絡(luò)環(huán)境中(12臺PC)。在實驗過程中,將種子節(jié)點中途退出。實驗最終結(jié)果表明,其余客戶端都可以正確地下載完源文件。通過對實驗結(jié)果進(jìn)一步分析得到一些結(jié)論:(1)該系統(tǒng)可以解決P2P網(wǎng)絡(luò)中“種子”突然退出可能造成的文件下載不完的問題;(2)基于網(wǎng)絡(luò)編碼的BitTorrent并沒有比普通的BitTorrent性能快很多,這是由于編碼和譯碼時間復(fù)雜度比較高,從而影響系統(tǒng)的整體性能。
P2P文件共享系統(tǒng)已經(jīng)成為了Internet的主要應(yīng)用之一。本文實現(xiàn)了一種基于線性網(wǎng)絡(luò)編碼的P2P文件共享系統(tǒng)。該系統(tǒng)可以提高網(wǎng)絡(luò)的吞吐量、增強系統(tǒng)的可靠性并提高下載成功率。由于網(wǎng)絡(luò)編碼存在著計算復(fù)雜度高的問題,雖然在編譯碼器的實現(xiàn)方法中結(jié)合了一些有效策略,可以降低部分計算量,但是編譯碼器的計算量開銷依然很大,因此研究降低網(wǎng)絡(luò)編碼的復(fù)雜性,實現(xiàn)最小代價的網(wǎng)絡(luò)編碼,具有重要的理論意義和使用應(yīng)用價值。
參考文獻(xiàn)
[1] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000, 46(4):1204-1216.
[2] LI S Y R, YEUNG R W, Ning Cai. Linear network coding[J]. IEEE Transactions on Information Theory, 2003,49(2):371-381.
[3] CHOU P A, WU Y N, JAIN K. Practical network coding[C]. The 41st Allerton Conference on Communication, Control and Computing Monticello, Kluwer,2003.
[4] HO T, MEDARD M, KOETTER R, et al. A random linear network coding approach to multicast[J]. IEEE Transactions on Information Theory, 2006,52(10):4413-4430.
[5] MA G, XU Y, LIN M, et al. A content distribution system based on sparse linear network coding[C]. Proceedings of the 3rd Workshop on Network Coding, Theory, and Applications (NETCOD 2007), 2007.
[6] GKANTSIDIS C, RODRIGOUE Z. Network coding for large scale content distribution[C]. INFOCOM 2005, 2005(4):2235-2245.