KAD網(wǎng)絡(luò)負(fù)載均衡技術(shù)研究*

史建燾，張宏莉

（哈爾濱工業(yè)大學(xué)計(jì)算機(jī)網(wǎng)絡(luò)與信息安全技術(shù)研究中心 哈爾濱150001）

1 引言

分布式散列表(distributed Hash tables,DHT)技術(shù)的出現(xiàn)擴(kuò)展了對(duì)等網(wǎng)絡(luò)用戶的規(guī)模，徹底釋放了用戶的共享下載需求。相比之前的P2P網(wǎng)絡(luò)，DHT網(wǎng)絡(luò)具有可擴(kuò)展性好、可靠性高等優(yōu)點(diǎn)，但是網(wǎng)絡(luò)節(jié)點(diǎn)的異構(gòu)性也給這一技術(shù)的發(fā)展提出了許多挑戰(zhàn)。作為為數(shù)不多的在實(shí)際環(huán)境下實(shí)現(xiàn)的DHT系統(tǒng)，利用Kademlia協(xié)議[1]的eMule軟件的KAD網(wǎng)絡(luò)已經(jīng)擁有了數(shù)以百萬的用戶群，在Internet上產(chǎn)生了一定的影響。KAD協(xié)議是基于二進(jìn)制異或運(yùn)算（XOR）度量距離的DHT協(xié)議，每個(gè)KAD節(jié)點(diǎn)擁有一個(gè)128位的唯一標(biāo)識(shí)，所有節(jié)點(diǎn)構(gòu)成一個(gè)二叉樹結(jié)構(gòu)。通過若干操作實(shí)現(xiàn)對(duì)數(shù)據(jù)項(xiàng)映射的存儲(chǔ)和獲取。一個(gè)健壯的DHT系統(tǒng)中，不同節(jié)點(diǎn)應(yīng)該以很高的概率分配到相同數(shù)量的目標(biāo)對(duì)象，從而保證系統(tǒng)的高可靠性和容錯(cuò)性。然而，由于應(yīng)用環(huán)境的特殊性和網(wǎng)絡(luò)節(jié)點(diǎn)的異構(gòu)性，實(shí)際系統(tǒng)中并沒有真正實(shí)現(xiàn)節(jié)點(diǎn)間負(fù)載的均衡性，KAD網(wǎng)絡(luò)同樣如此。本文通過測量實(shí)驗(yàn)發(fā)現(xiàn)由于關(guān)鍵詞使用頻率的差異，導(dǎo)致KAD網(wǎng)絡(luò)中以關(guān)鍵詞作為鍵值的文件索引負(fù)載在不同節(jié)點(diǎn)上的分配是不均衡的，這嚴(yán)重限制了KAD網(wǎng)絡(luò)的擴(kuò)展性和可用性。如何提高KAD網(wǎng)絡(luò)這方面的負(fù)載均衡性是本文的研究重點(diǎn)。

負(fù)載均衡作為DHT系統(tǒng)重要的性能評(píng)價(jià)指標(biāo)已經(jīng)成為了當(dāng)前研究的熱點(diǎn)，大多數(shù)研究工作都是以ID空間作為研究對(duì)象的[2]。認(rèn)為理想狀態(tài)下，DHT系統(tǒng)的負(fù)載均衡是指每個(gè)節(jié)點(diǎn)負(fù)責(zé)管理的ID空間應(yīng)該根據(jù)其軟硬件承載能力按比例分配。解決這類負(fù)載均衡問題的辦法多是采用虛擬服務(wù)器的方式，該方法最初由參考文獻(xiàn)[3]提出，考慮了節(jié)點(diǎn)軟硬件能力的差異以及網(wǎng)絡(luò)結(jié)構(gòu)的異構(gòu)性，將一個(gè)物理節(jié)點(diǎn)虛擬為在ID空間內(nèi)獨(dú)立的幾個(gè)邏輯節(jié)點(diǎn)，并使系統(tǒng)中負(fù)責(zé)某一ID空間存儲(chǔ)任務(wù)的節(jié)點(diǎn)數(shù)大致相當(dāng)。但該方法增加了網(wǎng)絡(luò)的波動(dòng)性，導(dǎo)致網(wǎng)絡(luò)維護(hù)代價(jià)增大。參考文獻(xiàn)[4]對(duì)虛擬服務(wù)器方法進(jìn)行了改進(jìn)，大幅度提高了該方法的性能。參考文獻(xiàn)[5]研究了具有超級(jí)節(jié)點(diǎn)的層次化DHT系統(tǒng)下的負(fù)載均衡問題。以上研究都是以負(fù)載在整個(gè)ID空間上的均勻分布作為假設(shè)的，而本文的研究以參考文獻(xiàn)[6]的研究為基礎(chǔ)，認(rèn)為實(shí)際KAD系統(tǒng)中文件索引信息在ID空間上的分布是不均勻的，參考文獻(xiàn)[6]提出的解決方法是通過存儲(chǔ)和搜索過程中過濾無用關(guān)鍵詞來防止某一ID子空間負(fù)載過重。但是，實(shí)際應(yīng)用中很難提供完備的無用關(guān)鍵詞集合，單獨(dú)依靠這種方法很難完全解決文件索引的負(fù)載均衡問題。本文從KAD協(xié)議本身出發(fā)，在文件索引發(fā)布和搜索階段對(duì)節(jié)點(diǎn)區(qū)域的負(fù)載進(jìn)行控制，引入多重目標(biāo)ID的方法分散熱點(diǎn)關(guān)鍵詞的負(fù)載，使系統(tǒng)在全局范圍內(nèi)達(dá)到負(fù)載均衡，從而保證KAD系統(tǒng)的健壯性和可用性。

2 負(fù)載分布測量

2.1 KAD資源發(fā)布機(jī)制

KAD的資源發(fā)布過程分為文件索引信息發(fā)布和源節(jié)點(diǎn)發(fā)布兩部分。本文的研究內(nèi)容僅涉及第一個(gè)發(fā)布過程：文件索引信息的發(fā)布，本節(jié)僅對(duì)這一過程做簡單介紹。文件索引信息的發(fā)布涉及3個(gè)基本操作。

（1）候選節(jié)點(diǎn)收集（lookup）

對(duì)于給定的目標(biāo)鍵值 （目標(biāo)ID），lookup操作通過鄰居節(jié)點(diǎn)之間的并發(fā)迭代查找，提供ID空間中可能負(fù)責(zé)目標(biāo)ID的一些候選節(jié)點(diǎn)。其中初始節(jié)點(diǎn)并發(fā)查找分支數(shù)為α，后繼節(jié)點(diǎn)并發(fā)查找分支數(shù)為β。除了初始節(jié)點(diǎn)采用α=3路并發(fā)查找外，后繼節(jié)點(diǎn)會(huì)根據(jù)不同的操作目的選擇并發(fā)迭代分支數(shù)。如果后續(xù)操作是發(fā)布（publish）操作，采用β=4路并發(fā)查找；后續(xù)操作是搜索（search）操作，則采用β=2路并發(fā)查找。當(dāng)查找收斂到發(fā)現(xiàn)不了新節(jié)點(diǎn)時(shí)，Lookup操作停止，去掉和目標(biāo)ID的公共前綴小于8的節(jié)點(diǎn)后，返回一個(gè)候選節(jié)點(diǎn)列表（candidate list）。

（2）發(fā)布

在最新的eMule實(shí)現(xiàn)中，選擇距離目標(biāo)ID最近的10個(gè)節(jié)點(diǎn)，通過Kademlia2_publish_key_req消息將映射發(fā)布到這些目的節(jié)點(diǎn)上。目的節(jié)點(diǎn)會(huì)返回Kademlia2_publish_res消息，消息包含一個(gè)代表當(dāng)前目的節(jié)點(diǎn)負(fù)載的load標(biāo)識(shí)，其值表示0～100的百分?jǐn)?shù)，KAD網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的負(fù)載上限是50 000。也就是說，如果load=100，表示目的節(jié)點(diǎn)上存儲(chǔ)的索引信息已經(jīng)達(dá)到50 000條，繼續(xù)在該節(jié)點(diǎn)上發(fā)布的索引信息會(huì)被丟棄。

（3）搜索

選擇距離目標(biāo)ID最近的候選節(jié)點(diǎn)，通過Kademlia2_search_key_req消息，請求候選節(jié)點(diǎn)提供有關(guān)目標(biāo)關(guān)鍵詞的文件索引。候選節(jié)點(diǎn)收到該消息后，隨機(jī)返回最多300個(gè)符合條件的索引項(xiàng)，并通過Kademlia2_publish_res消息返回。初始節(jié)點(diǎn)在收集滿300個(gè)結(jié)果或者搜索超時(shí)后，立即停止搜索操作。

2.2 測量系統(tǒng)的設(shè)計(jì)

為了獲取文件索引負(fù)載的分布情況，需要對(duì)KAD網(wǎng)絡(luò)進(jìn)行測量分析。出于不同的目的，本文的測量系統(tǒng)采用主動(dòng)測量和被動(dòng)測量兩種方法。圖1是整個(gè)測量系統(tǒng)的示意。

（1）主動(dòng)測量

主動(dòng)測量方法包括KAD爬蟲和基于主動(dòng)測量的虛擬客戶端。其中KAD爬蟲負(fù)責(zé)搜索網(wǎng)絡(luò)中一定ID空間范圍內(nèi)的活動(dòng)節(jié)點(diǎn)，是通過構(gòu)造針對(duì)一系列特殊目標(biāo)ID的lookup操作，獲取目標(biāo)節(jié)點(diǎn)部分或全部路由表的方法實(shí)現(xiàn)的，具體實(shí)現(xiàn)過程類似參考文獻(xiàn)[7]。虛擬客戶端負(fù)責(zé)并發(fā)Kademlia2_publish_key_req請求，收集活動(dòng)節(jié)點(diǎn)Kademlia2_publish_res消息中的load負(fù)載標(biāo)識(shí)以及測量lookup操作得到的候選節(jié)點(diǎn)與目標(biāo)ID的距離分布。

（2）被動(dòng)測量

被動(dòng)測量通過設(shè)計(jì)虛擬客戶段，將其節(jié)點(diǎn)ID設(shè)置為與目標(biāo)ID非常接近的值，然后插入KAD網(wǎng)絡(luò)，接收來自其他節(jié)點(diǎn)的索引發(fā)布和關(guān)鍵詞搜索請求，統(tǒng)計(jì)和分析流量的分布情況和自身負(fù)載變化規(guī)律。

2.3 測量結(jié)果

（1）負(fù)載分布

KAD系統(tǒng)中負(fù)責(zé)某一關(guān)鍵詞的節(jié)點(diǎn)在ID空間上是相鄰的，本文以ID值的8位公共前綴來標(biāo)記對(duì)應(yīng)的ID子區(qū)間。通過測量實(shí)驗(yàn)統(tǒng)計(jì)了負(fù)責(zé)關(guān)鍵詞the(0xe3)、China(0xe6)、dream(0xca)、Baidu(0xe4)的4個(gè)ID子區(qū)間內(nèi)的節(jié)點(diǎn)負(fù)載狀況。具體過程是通過爬蟲獲得ID子空間內(nèi)的所有節(jié)點(diǎn)，由索引發(fā)布模塊向所有節(jié)點(diǎn)發(fā)送Kademlia2_publish_key_req消息，收集節(jié)點(diǎn)回饋消息中攜帶的load負(fù)載標(biāo)識(shí)。實(shí)驗(yàn)發(fā)現(xiàn)最近節(jié)點(diǎn)一般與關(guān)鍵詞ID有23～24個(gè)相同公共前綴，從最近節(jié)點(diǎn)開始，以公共前綴數(shù)排序統(tǒng)計(jì)了節(jié)點(diǎn)的平均負(fù)載情況。結(jié)果如圖2所示，關(guān)鍵詞the和China所在子區(qū)間節(jié)點(diǎn)負(fù)載最重，距離較遠(yuǎn)的節(jié)點(diǎn)也有較大負(fù)載，這是因?yàn)檫@兩個(gè)關(guān)鍵詞屬于高頻關(guān)鍵詞。關(guān)鍵詞Baidu所在區(qū)間的節(jié)點(diǎn)負(fù)載較輕，只有距離關(guān)鍵詞ID最近的一些節(jié)點(diǎn)有一些負(fù)載，較遠(yuǎn)節(jié)點(diǎn)幾乎沒有負(fù)載。由此可見，以關(guān)鍵詞為鍵值的文件索引信息在KAD網(wǎng)絡(luò)的不同子區(qū)間的分布是不均勻的，存在一些超負(fù)荷區(qū)域。

（2）流量統(tǒng)計(jì)

為了發(fā)現(xiàn)負(fù)載強(qiáng)度對(duì)網(wǎng)絡(luò)中節(jié)點(diǎn)性能的影響，通過被動(dòng)測量實(shí)驗(yàn)統(tǒng)計(jì)了不同子區(qū)間內(nèi)，節(jié)點(diǎn)在單位時(shí)間接收到的消息數(shù)。測量節(jié)點(diǎn)ID分別被設(shè)置為與關(guān)鍵詞the、dream和盜夢空間的ID，即成為網(wǎng)絡(luò)中距離目標(biāo)關(guān)鍵詞最近的節(jié)點(diǎn)。表1的結(jié)果是當(dāng)節(jié)點(diǎn)路由表達(dá)到穩(wěn)定狀態(tài)后的1 h內(nèi)收到的消息數(shù)?？梢?，負(fù)責(zé)關(guān)鍵詞the的節(jié)點(diǎn)接收到的消息數(shù)最多，其中發(fā)布消息將近是查詢消息的10倍，而其他兩個(gè)關(guān)鍵詞發(fā)布消息僅是查詢消息的3～4倍?？梢园l(fā)現(xiàn)，大量的發(fā)布消息會(huì)集中在負(fù)責(zé)常用詞的ID空間，位于這一區(qū)域的節(jié)點(diǎn)常常付出更多的通信開銷。

表1 不同ID空間流量統(tǒng)計(jì)結(jié)果

（3）候選節(jié)點(diǎn)正確性

候選節(jié)點(diǎn)收集過程對(duì)KAD網(wǎng)絡(luò)的索引發(fā)布和搜索非常重要，正確的候選節(jié)點(diǎn)可以提高搜索命中率。理論上如果節(jié)點(diǎn)在ID空間上的分布是均勻的，一個(gè)具有大約400萬（≈222）個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)，相鄰節(jié)點(diǎn)的距離約為2128-22，也就是說相鄰節(jié)點(diǎn)ID公共前綴的長度約為22位。筆者通過爬蟲獲得了網(wǎng)絡(luò)中距離某一關(guān)鍵詞ID最近的10個(gè)節(jié)點(diǎn)，與真正客戶端候選節(jié)點(diǎn)收集過程得到的結(jié)果進(jìn)行了對(duì)比。結(jié)果見表2，主動(dòng)測量實(shí)驗(yàn)的結(jié)果與理論分析值很接近；而實(shí)際客戶端由于搜索并發(fā)數(shù)的限制，除了前幾個(gè)節(jié)點(diǎn)，并沒有得到所有最近的10個(gè)節(jié)點(diǎn)，也就是說實(shí)際客戶端得到的后幾個(gè)候選節(jié)點(diǎn)動(dòng)態(tài)性較大。對(duì)于高頻關(guān)鍵詞，由于索引信息量很大，大量距離較遠(yuǎn)的節(jié)點(diǎn)也會(huì)分配到一些索引信息，這就大大降低了其他節(jié)點(diǎn)的搜索命中率。為了改進(jìn)KAD網(wǎng)絡(luò)這種索引信息分配不均衡問題，提高搜索過程中索引信息的命中率，本文對(duì)索引信息的發(fā)布和搜索過程做了一定的改進(jìn)。

表2 候選節(jié)點(diǎn)正確性測量結(jié)果

3 改進(jìn)的索引信息發(fā)布策略

3.1 發(fā)布過程

改進(jìn)的資源發(fā)布過程如算法1所示。先通過lookup過程選擇離關(guān)鍵詞ID最近的10個(gè)節(jié)點(diǎn)加入候選隊(duì)列。與傳統(tǒng)的發(fā)布過程不同，改進(jìn)算法從隊(duì)列的第10個(gè)節(jié)點(diǎn)開始前向分3輪選擇發(fā)布節(jié)點(diǎn)。統(tǒng)計(jì)前兩輪節(jié)點(diǎn)返回的負(fù)載值，如果大于系統(tǒng)預(yù)設(shè)的該節(jié)點(diǎn)最大負(fù)載閾值，則在輪次內(nèi)累加負(fù)載值。如果該累加值超過最大誤差值D=5%，則表明負(fù)責(zé)該關(guān)鍵詞的節(jié)點(diǎn)區(qū)間負(fù)載過重。改進(jìn)算法在下一輪將通過lookup過程選擇新的節(jié)點(diǎn)區(qū)間發(fā)布該關(guān)鍵詞信息，ID偏移量L=2120，即散列值的8位二進(jìn)制公共前綴加1。最多會(huì)有以hash、hash+L、hash+2L為中心的3個(gè)ID空間負(fù)責(zé)負(fù)載量較大的關(guān)鍵詞，通過更多的節(jié)點(diǎn)分擔(dān)了負(fù)載。在最大負(fù)載MaxLoad的參數(shù)選擇上，對(duì)于負(fù)責(zé)原散列hash的第10到第7個(gè)節(jié)點(diǎn)，MaxLoad=45%；第6到第4個(gè)節(jié)點(diǎn)，MaxLoad=65%；負(fù)責(zé)散列hash+L的第6到第4個(gè)節(jié)點(diǎn)，MaxLoad=35%。

算法1：m-Publish(hash)

{C0,C1,…,C9}←Lookup(hash);

ContactSet←{C9,C8,C7,C6};

for round←0 to 2 do

SumLoad=0;

for p∈ContactSet do

p.load←publish(p);

if round<2 then

SumLoad+=Max(p.load-p.MaxLoad,0);

if SumLoad>D then

{C0,C1,…,C9}←Lookup(hash+L));

if round=0 then

ContactSet←{C3,C4,C5};

if round=1 then

ContactSet←{C0,C1,C2};

3.2 搜索過程

改進(jìn)的索引搜索過程如算法2所示。同樣通過lookup過程選擇10個(gè)節(jié)點(diǎn)加入候選隊(duì)列，第一輪先從后4個(gè)節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)發(fā)出搜索請求，如果該節(jié)點(diǎn)返回的索引信息超過預(yù)設(shè)的閾值rMax，則再通過lookup過程選擇hash+L空間內(nèi)的節(jié)點(diǎn)加入候選隊(duì)列，并且將rMax值增加150；否則，繼續(xù)向前選擇節(jié)點(diǎn)。第二輪選擇新隊(duì)列的后3個(gè)節(jié)點(diǎn)隨機(jī)發(fā)送請求，過程與第一輪類似。這樣最多會(huì)把hash、hash+L、hash+2L的3個(gè)ID空間內(nèi)的一定節(jié)點(diǎn)加入候選隊(duì)列。從第3輪開始同傳統(tǒng)算法相同，選擇最近的候選節(jié)點(diǎn)進(jìn)行搜索，這樣保證了算法的搜索效率。對(duì)負(fù)載較大的關(guān)鍵詞，會(huì)更多地從較遠(yuǎn)節(jié)點(diǎn)獲得索引信息，從而保證了更多的返回值。在MaxRefer參數(shù)選擇上，對(duì)負(fù)責(zé)原散列hash的第10到第7個(gè)節(jié)點(diǎn)，MaxRefer=150；第6到第4個(gè)節(jié)點(diǎn)，MaxRefer=200；負(fù)責(zé)散列hash+L的第6到 第4個(gè)節(jié)點(diǎn)，MaxRefer=100，第3到第1個(gè)節(jié)點(diǎn)，MaxRefer=150。

算法2：m-Search(hash)

{C0,C1,…,C9}←Lookup(hash);

Candidates←{C0,C1,…,C9};

ContactSet←{C9,C8,C7,C6};

round←0;rMax←300;

while references.size()

if round<2 then

p←ContactSet.getRandom();

R←search(p);references.add(R);

if R.size()>p.MaxRefer then

{C0,C1,…,C9}←Lookup(hash+L);

rMax+=150;

if round=0 then

Candidates.add({C0,C1,…,C5});

ContactSet←{C0,C1,…,C5};

if round=1 then

Candidates.add{C0,C1,C2};

ContactSet←{C0,C1,C2};

else

p←Candidates.getFirst();

.add(search(p));

Candidates.remove(p);

retrun references;

4 仿真實(shí)驗(yàn)

本節(jié)通過仿真實(shí)驗(yàn)驗(yàn)證前面所提出的方法，仿真程序以一個(gè)離散事件模擬引擎為基礎(chǔ)，實(shí)現(xiàn)了基本的eMule的KAD協(xié)議。為提高仿真效率，節(jié)點(diǎn)空間的規(guī)模為3個(gè)連續(xù)的具有8位公共ID前綴的子空間。節(jié)點(diǎn)數(shù)目按照真實(shí)環(huán)境的比例分配，假設(shè)網(wǎng)絡(luò)已經(jīng)達(dá)到穩(wěn)定狀態(tài)，每個(gè)子空間保證有15 000個(gè)在線節(jié)點(diǎn)，節(jié)點(diǎn)上下線頻率以采集到的真實(shí)環(huán)境下的數(shù)據(jù)為基礎(chǔ)。仿真實(shí)驗(yàn)以一個(gè)給定的關(guān)鍵詞生成文件索引。和真實(shí)協(xié)議一樣，發(fā)布成功后每個(gè)索引在存儲(chǔ)節(jié)點(diǎn)上保留24 h的模擬時(shí)鐘時(shí)間。通過一個(gè)模擬客戶端以每秒20個(gè)索引的頻率在KAD網(wǎng)絡(luò)發(fā)布文件索引。索引量基本飽和后，通過搜索過程提取當(dāng)前系統(tǒng)中的文件索引，客戶端分別采用傳統(tǒng)算法和改進(jìn)算法進(jìn)行發(fā)布和搜索操作。

筆者根據(jù)節(jié)點(diǎn)ID值對(duì)每個(gè)子空間內(nèi)的節(jié)點(diǎn)進(jìn)行了分組，組間ID距離相等，每組大概有8個(gè)真實(shí)節(jié)點(diǎn)，由于大量文件索引發(fā)布在距目標(biāo)ID較近的節(jié)點(diǎn)中，每個(gè)子空間只抽取了最近的32個(gè)分組并記錄下節(jié)點(diǎn)的平均負(fù)載。實(shí)驗(yàn)結(jié)果如圖3所示，當(dāng)客戶端采用傳統(tǒng)方法時(shí)，大量節(jié)點(diǎn)出現(xiàn)了過飽和現(xiàn)象，其中距離目標(biāo)ID最近的2個(gè)分組中，所有節(jié)點(diǎn)的負(fù)載率達(dá)到了100%，大量文件索引發(fā)布在距目標(biāo)ID較遠(yuǎn)的節(jié)點(diǎn)上。而采用了改進(jìn)的索引發(fā)布算法后，目標(biāo)子空間的文件負(fù)載大大降低，基本達(dá)到了算法所控制的閾值，并且相鄰子空間的部分節(jié)點(diǎn)也分擔(dān)了大量的負(fù)載。模擬實(shí)驗(yàn)還記錄了當(dāng)索引發(fā)布達(dá)到飽和后，單位時(shí)間內(nèi)能搜索到的最新文件的數(shù)量。由于大量候選節(jié)點(diǎn)達(dá)到了飽和狀態(tài)，很多文件索引在傳統(tǒng)協(xié)議下無法被成功發(fā)布和提取，實(shí)驗(yàn)獲得的最新文件的提取率僅為18.7%；而采用改進(jìn)方法后，文件的提取率可以達(dá)到89.3%。由此可見，改進(jìn)的索引發(fā)布和搜索算法，能夠大幅提高KAD網(wǎng)絡(luò)的健壯性和文件發(fā)布效率。

5 結(jié)束語

基于DHT結(jié)構(gòu)的P2P網(wǎng)絡(luò)的發(fā)展給當(dāng)今的互聯(lián)網(wǎng)注入了活力，為用戶提供了更多的便利和實(shí)惠。但是，由于應(yīng)用環(huán)境的特殊性和網(wǎng)絡(luò)節(jié)點(diǎn)的異構(gòu)性，大多數(shù)DHT網(wǎng)絡(luò)都存在著各種負(fù)載不均衡問題，需要進(jìn)一步的優(yōu)化和改進(jìn)。本文通過測量實(shí)驗(yàn)發(fā)現(xiàn)了擁有大量用戶群的eMule的KAD網(wǎng)絡(luò)下，索引資源在ID空間上的分布是不均勻的，網(wǎng)絡(luò)中存在的一些負(fù)載過重節(jié)點(diǎn)會(huì)威脅到用戶對(duì)系統(tǒng)的正常使用。為了解決這一問題，本文提出了一種基于多重目標(biāo)ID的索引發(fā)布和搜索機(jī)制，仿真實(shí)驗(yàn)表明該方法能夠有效地提高索引負(fù)載分配的均衡性。

1 Maymounkov P,Mazieres D.Kademlia:a peer-to-peer information system based on the XOR metric.Proceedings of the International Workshop on Peer-to-Peer Systems,Cambrige,USA,2002:53～65

2 Godfrey P B,Stoica I.Heterogeneity and load balance in distributed Hash tables.Proceedings of IEEE INFOCOM,Miami,FL,USA,2005

3 Rao A，Lakshminaraynan K,Surana S,et al.Load balancing in structured P2P systems.Proceedings of the 2nd International Workshop Peer-to-Peer Systems,Berkeley,USA,2003:68～79

4 Hung-Chang Hsiao,Che-Wei Chang.A symmetric load balancing algorithm with performance guarantees for distributed hash tables.IEEE Transactions on Computers,2012(1)

5 張宇翔，張宏科.一種層次結(jié)構(gòu)化P2P網(wǎng)絡(luò)中的負(fù)載均衡方法.計(jì)算機(jī)學(xué)報(bào)，2010，33（9）

6 Steiner M,Effelsberg W,En-Najjary T,et al.Load reduction in the KAD peer-to-peer system.Proceedings of the Fifth International Workshop on Databases,Information Systems and Peer-to-Peer Computing,Austria,2007

7 Steiner M,En-Najjary T,Biersack E W.Long term study of peer behavior in the KAD DHT.IEEE/ACM Transactions on Networking,2009,17(5):1 371～1 384