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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9 李威;;華為L(zhǎng)STP路由選擇域和鏈路選擇域設(shè)置原理及應(yīng)用[A];內(nèi)蒙古通信學(xué)會(huì)2005年年會(huì)論文集[C];2005年

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

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

1 楊帆;路由可控網(wǎng)絡(luò)增強(qiáng)網(wǎng)絡(luò)性能[N];中國(guó)計(jì)算機(jī)報(bào);2003年

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

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

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

5 陳代壽;新型骨干路由器面向ISP[N];中國(guó)計(jì)算機(jī)報(bào);2000年

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

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

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

9 李連、朱愛(ài)紅、糜玉林;VLAN有什么用[N];中國(guó)電腦教育報(bào);2002年

10 易觀國(guó)際分析師 郭飛;無(wú)線Mesh還有三道坎[N];中國(guó)計(jì)算機(jī)報(bào);2007年

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

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

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

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

4 郭雅;基于拓?fù)洹⒌乩砑熬W(wǎng)絡(luò)編碼感知的VANETs路由協(xié)議研究[D];華中科技大學(xué);2012年

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2208750