【摘要】：i基于DHT的結(jié)構(gòu)化P2P網(wǎng)絡(luò),無論是在傳統(tǒng)的分布式系統(tǒng)中還是在新的計算模式中都有著大量的研究和應用。經(jīng)過10多年的發(fā)展,其基礎(chǔ)理論和核心技術(shù)趨于穩(wěn)定,研究者關(guān)注的重點也轉(zhuǎn)向了實際應用中面臨的問題,負載均衡問題是其中很重要的一個方面。傳統(tǒng)應用中的“熱點”問題,在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中同樣存在,同時由于節(jié)點的能力與傳統(tǒng)服務器有著天壤之別,使得在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中實現(xiàn)負載均衡變得更為重要;節(jié)點的動態(tài)性、異構(gòu)性以及拓撲失配等因素使得在結(jié)構(gòu)化P2P網(wǎng)絡(luò)中實現(xiàn)負載均衡難度更大。本文圍繞結(jié)構(gòu)化P2P網(wǎng)絡(luò)中由于查詢分布不均勻帶來的負載均衡問題展開深入研究。主要工作包括以下幾個方面:(1)嚴重偏斜的查詢?nèi)菀讓е孪到y(tǒng)中維護熱門數(shù)據(jù)的節(jié)點的負載遠遠高于其它節(jié)點,采用復制/緩存技術(shù)能有效地平衡節(jié)點的負載。結(jié)構(gòu)化P2P網(wǎng)絡(luò)中復制/緩存技術(shù)的應用由來已久,為了提高系統(tǒng)可靠性和數(shù)據(jù)可用性研究者提出了大量的復制方案,并從效率、數(shù)據(jù)保持、數(shù)據(jù)一致性等方面進行了理論分析,但缺乏從負載均衡的角度對相關(guān)方法進行理論分析的研究。針對該問題,以Chord網(wǎng)絡(luò)為例,創(chuàng)新地用與源數(shù)據(jù)的相對位置對結(jié)構(gòu)化P2P網(wǎng)絡(luò)中副本放置策略與查詢命中率之間的關(guān)系進行了深入分析,發(fā)現(xiàn)了隨著副本到源數(shù)據(jù)距離的減少命中概率呈指數(shù)性增長等規(guī)律。(2)在基于DHT的SOA、搜索引擎等系統(tǒng)中,一方面由于用戶訪問高度偏斜產(chǎn)生的“熱點”會嚴重影響系統(tǒng)的可用性;另一方面,基于單關(guān)鍵字進行多屬性資源的定位必然會嚴重影響系統(tǒng)的效率。針對上述問題,提出一種支持負載均衡的多屬性資源定位方法 QFMA:以MAAN為基礎(chǔ),將同一資源的描述信息存儲到多個節(jié)點上;采用沿路復制的方法在路由路徑上“捎帶”發(fā)布“熱門”關(guān)鍵字所在節(jié)點的狀態(tài)信息;其它查詢根據(jù)這些狀態(tài)在路由過程中進行目標切換,將“熱門”關(guān)鍵字所在節(jié)點的負載分流到負載較輕的節(jié)點上,從而實現(xiàn)系統(tǒng)的負載均衡。QFMA在支持多關(guān)鍵字查詢的同時,能夠有效平衡熱點的負載,且副本管理開銷較小。(3)結(jié)構(gòu)化P2P網(wǎng)路中,網(wǎng)絡(luò)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)往往不一致,即存在拓撲失配現(xiàn)象。拓撲失配一方面會導致查詢定位延時較高;另一方面會增加自治系統(tǒng)間的路由和數(shù)據(jù)傳輸。結(jié)構(gòu)化P2P網(wǎng)絡(luò)中復制/緩存是消除“熱點”實現(xiàn)負載均衡的有效手段,然而副本創(chuàng)建、副本維護、查詢調(diào)度等操作必然會帶來額外的路由和數(shù)據(jù)傳輸開銷。針對如何降低復制/緩存的開銷、減少自治系統(tǒng)間路由等問題,提出了一種基于鄰近節(jié)點復制的負載均衡算法PB-Chord:以網(wǎng)絡(luò)中公共的DNS服務器為參照點,位置臨近的節(jié)點在加入網(wǎng)絡(luò)時進行聚簇,熱門數(shù)據(jù)在本簇空閑節(jié)點上復制,任意節(jié)點都擁有本簇所有節(jié)點的負載狀態(tài)信息、數(shù)據(jù)對象信息,在查詢過程中利用這些信息提高路由定位效率,同時利用這些信息進行無中心的查詢調(diào)度,實現(xiàn)簇內(nèi)節(jié)點的負載均衡。理論分析和實驗結(jié)果表明PB-Chord能夠在實現(xiàn)系統(tǒng)負載均衡的同時,有效減小系統(tǒng)的通信開銷,提高系統(tǒng)的路由定位效率。(4)在大規(guī)模、動態(tài)的P2P網(wǎng)絡(luò)中獲取全局負載狀態(tài)是一項極具挑戰(zhàn)的工作。針對這一現(xiàn)狀,提出了一種能夠在大規(guī)模結(jié)構(gòu)化P2P網(wǎng)絡(luò)中有效獲取全局負載狀態(tài)的算法Hermes:基于PushPull模式的Gossip算法實現(xiàn)狀態(tài)信息的傳播;給出了一種新穎的算法對全局狀態(tài)進行壓縮以減小傳輸和存儲開銷。理論分析和實驗結(jié)果表明,在N個節(jié)點的網(wǎng)絡(luò)中只需要log N-2個周期就可以將任意節(jié)點上的狀態(tài)傳播到整個網(wǎng)絡(luò)中;如果節(jié)點負載符合Zipf分布,只需要很小的存儲空間就可以存儲大規(guī)模網(wǎng)絡(luò)的全局狀態(tài)信息;在節(jié)點狀態(tài)變化率不高的情況下,通信開銷較小,同時可以保證全局狀態(tài)較高的準確性。
[Abstract]:I DHT-based structured P2P networks have a lot of research and applications, both in traditional distributed systems and in new computing models. After more than 10 years of development, its basic theory and core technology tend to be stable. Researchers have also turned their attention to practical application problems, load balancing is one of them. One important aspect is that the "hot spot" problem in traditional applications exists in structured P2P networks as well. At the same time, the ability of nodes is so different from that of traditional servers that load balancing in structured P2P networks becomes more important. It is more difficult to achieve load balancing in structured P2P networks. This paper focuses on the load balancing problem caused by uneven query distribution in structured P2P networks. The main work includes the following aspects: (1) serious skewed queries easily lead to the load of nodes maintaining hot data in the system is much higher than that of other nodes. Replication/caching technology can effectively balance the load of nodes.The application of replication/caching technology in structured P2P networks has a long history.In order to improve system reliability and data availability,researchers have proposed a large number of replication schemes,and made theoretical analysis from the aspects of efficiency,data retention,data consistency,etc. In view of this problem, the relationship between replica placement strategy and query hit rate in structured P2P networks is analyzed creatively by using the relative position of the replica and the source data. It is found that the hit probability is exponential with the decrease of the distance between the replica and the source data. (2) In DHT-based SOA, search engines and other systems, on the one hand, the "hot spots" caused by high skewness of user access will seriously affect the availability of the system; on the other hand, multi-attribute resource location based on single keyword will inevitably seriously affect the efficiency of the system. Balanced multi-attribute resource location method QFMA: Based on MAAN, the description information of the same resource is stored on multiple nodes; the state information of the node where the "hot" keyword is located is "piggybacked" by copying along the route; other queries switch targets according to these states during the route, and the "hot" keyword is "piggybacked". In structured P2P networks, the logical structure and physical structure of the network are often inconsistent, that is, there are topologies. On the one hand, topological mismatch will lead to high latency of query location; on the other hand, it will increase routing and data transmission between autonomous systems. Replication/caching in structured P2P networks is an effective means to eliminate "hot spots" and achieve load balancing. However, replica creation, replica maintenance, query scheduling and other operations will inevitably lead to additional operations. Routing and data transmission overhead. In order to reduce the overhead of replication/caching and the routing between autonomous systems, a load balancing algorithm PB-Chord based on replication of neighboring nodes is proposed. Any node has the load status information of all nodes in the cluster. The data object information can be used to improve the efficiency of routing and positioning in the process of query. At the same time, the information can be used for centrless query scheduling to achieve load balancing of nodes in the cluster. Theoretical analysis and experimental results show that PB-Chord can achieve load balancing in the cluster. (4) It is a challenging task to obtain global load state in large-scale, dynamic P2P networks. In view of this situation, this paper proposes an efficient way to obtain global load state in large-scale structured P2P networks. Hermes: A Gossip algorithm based on PushPull mode is proposed to transmit state information. A novel algorithm is presented to compress the global state to reduce the transmission and storage overhead. Theoretical analysis and experimental results show that in N-node networks, only log N-2 cycles are needed to propagate the state of any node to the whole. If the node load conforms to the Zipf distribution, only a small storage space is needed to store the global state information of the large-scale network.
【學位授予單位】：國防科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2013
【分類號】：TP393.02

【相似文獻】

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

1 肖曉麗;黃敏;張衛(wèi)平;;一種新型的高吞吐量路由量度[J];中南大學學報(自然科學版);2009年02期

2 倪明放;王曦;武欣嶸;陳建文;于戰(zhàn)科;;多約束最優(yōu)路由選擇和不相交路由選擇問題[J];軍事通信技術(shù);2010年04期

3 葛明珠;徐利亞;雷淑君;;車載網(wǎng)中一種基于鏈路穩(wěn)定度的路由方法[J];信息安全與技術(shù);2012年09期

4 周修廉;;分布式系統(tǒng)中訊息傳遞最佳路由的選擇[J];哈爾濱科學技術(shù)大學學報;1982年02期

5 涂金格;分布式雙環(huán)計算機網(wǎng)的最佳路由算法[J];計算機應用;1991年05期

6 費愛軍;路由服務器宣告誕生[J];通訊產(chǎn)品世界;1995年08期

7 劉偉科;孟曉景;;一種服務質(zhì)量路由算法的改進[J];福建電腦;2006年01期

8 祁彥;徐昌彪;尤齊;畢遠梅;;容遲網(wǎng)絡(luò)中的隨機路由算法研究[J];數(shù)據(jù)通信;2008年05期

9 喻嘉;聞英友;趙宏;;無線傳感器網(wǎng)絡(luò)中分段貪婪地理路由算法[J];控制與決策;2011年02期

10 趙龍華;康京山;;分組網(wǎng)中的路由選擇方法與實現(xiàn)[J];無線電通信技術(shù);1993年05期

相關(guān)會議論文 前10條

1 黃勇;胡健生;;基于系統(tǒng)綜合性能的通信路由選擇[A];開創(chuàng)新世紀的通信技術(shù)——第七屆全國青年通信學術(shù)會議論文集[C];2001年

2 孟廣平;;多出口鏈路均衡路由方法研究[A];中國計量協(xié)會冶金分會2010年會論文集[C];2010年

3 顧曉燕;劉峰;;無線Mesh網(wǎng)絡(luò)擁塞感知跨層路由算法設(shè)計與仿真[A];中國電子學會第十五屆信息論學術(shù)年會暨第一屆全國網(wǎng)絡(luò)編碼學術(shù)年會論文集（下冊）[C];2008年

4 熊翱;;基于可用性的傳輸網(wǎng)鏈路路由算法[A];2006年全國通信軟件學術(shù)會議論文集[C];2006年

5 陳瑾平;徐昊;楊綠溪;;一種適用于中繼增強型蜂窩網(wǎng)的路由選擇與比例公平性聯(lián)合調(diào)度算法[A];第十四屆全國信號處理學術(shù)年會(CCSP-2009)論文集[C];2009年

6 李婷;;多約束條件下的QoS路由算法研究[A];第十二屆中國青年信息與管理學者大會論文集[C];2010年

7 游向東;;無線mesh網(wǎng)路由分析[A];2007中國科協(xié)年會——通信與信息發(fā)展高層論壇論文集[C];2007年

8 余菁菁;梁滿貴;;向量網(wǎng)交換與路由分離方法的研究[A];中國電子學會第十六屆信息論學術(shù)年會論文集[C];2009年

9 李威;;華為LSTP路由選擇域和鏈路選擇域設(shè)置原理及應用[A];內(nèi)蒙古通信學會2005年年會論文集[C];2005年

10 張平;李正斌;徐安士;;OBS網(wǎng)絡(luò)中基于預測的一種路由新方法[A];光電技術(shù)與系統(tǒng)文選——中國光學學會光電技術(shù)專業(yè)委員會成立二十周年暨第十一屆全國光電技術(shù)與系統(tǒng)學術(shù)會議論文集[C];2005年

相關(guān)重要報紙文章 前10條

1 楊帆;路由可控網(wǎng)絡(luò)增強網(wǎng)絡(luò)性能[N];中國計算機報;2003年

2 ;以路由為中心的城域網(wǎng)方案[N];人民郵電;2001年

3 ;選擇效率最高ISP的路由控制[N];網(wǎng)絡(luò)世界;2001年

4 ;骨干路由器的軟硬件體系結(jié)構(gòu)[N];人民郵電;2001年

5 陳代壽;新型骨干路由器面向ISP[N];中國計算機報;2000年

6 李艷玲;天融信網(wǎng)絡(luò)衛(wèi)士防火墻雙址路由降低教育網(wǎng)成本[N];中國計算機報;2003年

7 本期專家：王春海 劉曉輝;專家坐堂之網(wǎng)絡(luò)篇[N];電腦報;2003年

8 中國電信北京研究院 陳運清 胡琳;打造可靠的IP城域核心網(wǎng)[N];人民郵電;2005年

9 李連、朱愛紅、糜玉林;VLAN有什么用[N];中國電腦教育報;2002年

10 易觀國際分析師 郭飛;無線Mesh還有三道坎[N];中國計算機報;2007年

相關(guān)博士學位論文 前5條

1 張祖平;規(guī)則網(wǎng)絡(luò)容錯路由算法及可靠組播的研究[D];中南大學;2005年

2 赫衛(wèi)卿;無線Mesh網(wǎng)絡(luò)中高效公平媒體訪問控制協(xié)議與路由協(xié)議研究[D];中國科學技術(shù)大學;2011年

3 劉德輝;結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的負載均衡技術(shù)研究[D];國防科學技術(shù)大學;2013年

4 郭雅;基于拓撲、地理及網(wǎng)絡(luò)編碼感知的VANETs路由協(xié)議研究[D];華中科技大學;2012年

5 王雷;高性能并行計算機互聯(lián)網(wǎng)絡(luò)容錯模型及其路由算法研究[D];湖南大學;2005年

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

1 謝孟杰;容遲網(wǎng)絡(luò)中低資源消耗的傳染路由研究[D];北京理工大學;2011年

2 尤齊;容斷網(wǎng)絡(luò)中的擺渡路由算法研究[D];重慶大學;2009年

3 李理;基于認證的安全路由體系結(jié)構(gòu)的研究[D];清華大學;2010年

4 鄒杰;能量高效的非均勻分簇路由算法研究[D];長沙理工大學;2012年

5 黃健美;多下一跳路由算法研究[D];解放軍信息工程大學;2010年

6 王鵬飛;人工蜂群算法在無線Mesh網(wǎng)絡(luò)中的應用研究[D];遼寧科技大學;2013年

7 王秀君;網(wǎng)絡(luò)中可靠路由算法的研究[D];山東師范大學;2008年

8 魏飛飛;基于ZigBee的無線網(wǎng)絡(luò)傳感系統(tǒng)的研究[D];大連海事大學;2012年

9 陳群;無線網(wǎng)絡(luò)中編碼感知機會路由的研究[D];浙江工業(yè)大學;2012年

10 王玲;多跳多接口無線網(wǎng)絡(luò)中的協(xié)作路由[D];湖南大學;2013年

，

本文編號：2208750