發(fā)布時間：2018-08-28 07:48

【摘要】：i基于DHT的結構化P2P網絡,無論是在傳統(tǒng)的分布式系統(tǒng)中還是在新的計算模式中都有著大量的研究和應用。經過10多年的發(fā)展,其基礎理論和核心技術趨于穩(wěn)定,研究者關注的重點也轉向了實際應用中面臨的問題,負載均衡問題是其中很重要的一個方面。傳統(tǒng)應用中的“熱點”問題,在結構化P2P網絡中同樣存在,同時由于節(jié)點的能力與傳統(tǒng)服務器有著天壤之別,使得在結構化P2P網絡中實現負載均衡變得更為重要;節(jié)點的動態(tài)性、異構性以及拓撲失配等因素使得在結構化P2P網絡中實現負載均衡難度更大。本文圍繞結構化P2P網絡中由于查詢分布不均勻帶來的負載均衡問題展開深入研究。主要工作包括以下幾個方面:(1)嚴重偏斜的查詢容易導致系統(tǒng)中維護熱門數據的節(jié)點的負載遠遠高于其它節(jié)點,采用復制/緩存技術能有效地平衡節(jié)點的負載。結構化P2P網絡中復制/緩存技術的應用由來已久,為了提高系統(tǒng)可靠性和數據可用性研究者提出了大量的復制方案,并從效率、數據保持、數據一致性等方面進行了理論分析,但缺乏從負載均衡的角度對相關方法進行理論分析的研究。針對該問題,以Chord網絡為例,創(chuàng)新地用與源數據的相對位置對結構化P2P網絡中副本放置策略與查詢命中率之間的關系進行了深入分析,發(fā)現了隨著副本到源數據距離的減少命中概率呈指數性增長等規(guī)律。(2)在基于DHT的SOA、搜索引擎等系統(tǒng)中,一方面由于用戶訪問高度偏斜產生的“熱點”會嚴重影響系統(tǒng)的可用性;另一方面,基于單關鍵字進行多屬性資源的定位必然會嚴重影響系統(tǒng)的效率。針對上述問題,提出一種支持負載均衡的多屬性資源定位方法 QFMA:以MAAN為基礎,將同一資源的描述信息存儲到多個節(jié)點上;采用沿路復制的方法在路由路徑上“捎帶”發(fā)布“熱門”關鍵字所在節(jié)點的狀態(tài)信息;其它查詢根據這些狀態(tài)在路由過程中進行目標切換,將“熱門”關鍵字所在節(jié)點的負載分流到負載較輕的節(jié)點上,從而實現系統(tǒng)的負載均衡。QFMA在支持多關鍵字查詢的同時,能夠有效平衡熱點的負載,且副本管理開銷較小。(3)結構化P2P網路中,網絡的邏輯結構和物理結構往往不一致,即存在拓撲失配現象。拓撲失配一方面會導致查詢定位延時較高;另一方面會增加自治系統(tǒng)間的路由和數據傳輸。結構化P2P網絡中復制/緩存是消除“熱點”實現負載均衡的有效手段,然而副本創(chuàng)建、副本維護、查詢調度等操作必然會帶來額外的路由和數據傳輸開銷。針對如何降低復制/緩存的開銷、減少自治系統(tǒng)間路由等問題,提出了一種基于鄰近節(jié)點復制的負載均衡算法PB-Chord:以網絡中公共的DNS服務器為參照點,位置臨近的節(jié)點在加入網絡時進行聚簇,熱門數據在本簇空閑節(jié)點上復制,任意節(jié)點都擁有本簇所有節(jié)點的負載狀態(tài)信息、數據對象信息,在查詢過程中利用這些信息提高路由定位效率,同時利用這些信息進行無中心的查詢調度,實現簇內節(jié)點的負載均衡。理論分析和實驗結果表明PB-Chord能夠在實現系統(tǒng)負載均衡的同時,有效減小系統(tǒng)的通信開銷,提高系統(tǒng)的路由定位效率。(4)在大規(guī)模、動態(tài)的P2P網絡中獲取全局負載狀態(tài)是一項極具挑戰(zhàn)的工作。針對這一現狀,提出了一種能夠在大規(guī)模結構化P2P網絡中有效獲取全局負載狀態(tài)的算法Hermes:基于PushPull模式的Gossip算法實現狀態(tài)信息的傳播;給出了一種新穎的算法對全局狀態(tài)進行壓縮以減小傳輸和存儲開銷。理論分析和實驗結果表明,在N個節(jié)點的網絡中只需要log N-2個周期就可以將任意節(jié)點上的狀態(tài)傳播到整個網絡中;如果節(jié)點負載符合Zipf分布,只需要很小的存儲空間就可以存儲大規(guī)模網絡的全局狀態(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.
【學位授予單位】：國防科學技術大學
【學位級別】：博士
【學位授予年份】：2013
【分類號】：TP393.02

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

8 祁彥;徐昌彪;尤齊;畢遠梅;;容遲網絡中的隨機路由算法研究[J];數據通信;2008年05期

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

10 趙龍華;康京山;;分組網中的路由選擇方法與實現[J];無線電通信技術;1993年05期

相關會議論文 前10條

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

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

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

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

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

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

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

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

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

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

相關重要報紙文章 前10條

1 楊帆;路由可控網絡增強網絡性能[N];中國計算機報;2003年

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

3 ;選擇效率最高ISP的路由控制[N];網絡世界;2001年

4 ;骨干路由器的軟硬件體系結構[N];人民郵電;2001年

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

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

7 本期專家：王春海 劉曉輝;專家坐堂之網絡篇[N];電腦報;2003年

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

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

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

相關博士學位論文 前5條

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

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

3 劉德輝;結構化P2P網絡中的負載均衡技術研究[D];國防科學技術大學;2013年

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

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

相關碩士學位論文 前10條

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

2 尤齊;容斷網絡中的擺渡路由算法研究[D];重慶大學;2009年

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

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

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

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

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

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

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

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

，

本文編號：2208750