P-Grid覆蓋網(wǎng)絡(luò)的加速收斂構(gòu)建算法*

宋瑋 趙躍龍

(華南理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣東廣州 510006)

結(jié)構(gòu)化 P2P覆蓋網(wǎng)絡(luò)按照一定的邏輯拓?fù)浣Y(jié)構(gòu)將系統(tǒng)物理層的節(jié)點(diǎn)相互連接起來(lái).在覆蓋網(wǎng)絡(luò)提供的加入、路由、查找、退出等基本功能之上可實(shí)現(xiàn)不同的應(yīng)用服務(wù).目前已有的建立在覆蓋網(wǎng)絡(luò)之上的P2P數(shù)據(jù)存儲(chǔ)系統(tǒng)有:使用MIT提出的Chord覆蓋網(wǎng)絡(luò)建立的開放文件存儲(chǔ)環(huán)境 CFS[1];使用Berkeley提出的Tapestry覆蓋網(wǎng)絡(luò)建立的Ocean-Store[2];使用微軟亞洲研究院提出的Xring覆蓋網(wǎng)絡(luò)建立的面向較少更新的存儲(chǔ)系統(tǒng)BitVault[3]以及清華大學(xué)提出的采用Tourist路由算法建立的面向?qū)ο蟮拇鎯?chǔ)系統(tǒng)Granary[4].覆蓋網(wǎng)絡(luò)層是整個(gè)P2P存儲(chǔ)系統(tǒng)運(yùn)行的基礎(chǔ),其特性影響到整個(gè)系統(tǒng)的特性,是系統(tǒng)成功與否的關(guān)鍵.

P-Grid覆蓋網(wǎng)絡(luò)是一個(gè)分布式信息管理的P2P平臺(tái),具有完全分散管理、自組織[5-6]、基于動(dòng)態(tài) IP的數(shù)據(jù)管理(更新)[7-8]、分布式負(fù)載平衡[9-10]等特點(diǎn).覆蓋網(wǎng)的構(gòu)建基于隨機(jī)算法和本地交互,面向低在線率的節(jié)點(diǎn)環(huán)境,該網(wǎng)絡(luò)既具有虛擬樹的結(jié)構(gòu),能以樹的形式組織資源實(shí)現(xiàn)系統(tǒng)的層次化管理,提高資源查找效率,又?jǐn)[脫了基于樹的覆蓋網(wǎng)絡(luò)結(jié)構(gòu)(如MPPBTree[11],BATON[12])中對(duì)根節(jié)點(diǎn)的依賴,非葉節(jié)點(diǎn)并不對(duì)應(yīng)實(shí)際的對(duì)等節(jié)點(diǎn),各節(jié)點(diǎn)最終成為葉節(jié)點(diǎn).整個(gè)樹的構(gòu)建過(guò)程不需要中心協(xié)調(diào),節(jié)點(diǎn)隨機(jī)漫步導(dǎo)致的相遇是樹構(gòu)建的動(dòng)力,這樣一來(lái),樹形成的速度(即收斂性)便是一個(gè)關(guān)鍵,它嚴(yán)重影響整個(gè)系統(tǒng)的性能.文中重點(diǎn)在兩種情況下討論了PGrid的收斂性,改進(jìn)了原有算法以加快構(gòu)建速度,為今后建立在其上的應(yīng)用系統(tǒng)提供更好的支撐.

1 P-Grid概述

1.1 P-Grid數(shù)據(jù)結(jié)構(gòu)

文獻(xiàn)[5-6]描述了P-Grid系統(tǒng)中基于虛擬二叉搜索樹的覆蓋網(wǎng)絡(luò)及路由算法.系統(tǒng)中每個(gè)對(duì)象,包括對(duì)等節(jié)點(diǎn)和數(shù)據(jù)對(duì)象都擁有一個(gè)二進(jìn)制索引值,對(duì)等節(jié)點(diǎn)還擁有路徑值(表示為path(peer)),表明節(jié)點(diǎn)在二叉樹中的路徑,動(dòng)態(tài)形成于虛擬二叉樹的構(gòu)建過(guò)程.每個(gè)對(duì)等節(jié)點(diǎn)根據(jù)其路徑值對(duì)應(yīng)一個(gè)索引值區(qū)間;每個(gè)對(duì)等節(jié)點(diǎn)含有兩類信息:數(shù)據(jù)索引信息和路由信息.數(shù)據(jù)索引信息是存儲(chǔ)索引值最大前綴與節(jié)點(diǎn)路徑值相同的數(shù)據(jù)對(duì)象的索引信息.圖 1所示的P-Grid實(shí)例中節(jié)點(diǎn)4的路徑值為010,則存儲(chǔ)以 010為前綴的數(shù)據(jù)對(duì)象的索引信息.節(jié)點(diǎn)路由信息形成路由表,表中每一層路由項(xiàng)指向樹中與該節(jié)點(diǎn)在路徑值某位上具有相反值的節(jié)點(diǎn)信息.如節(jié)點(diǎn) 4中第二層路由項(xiàng) 00:7說(shuō)明路徑值第二位與節(jié)點(diǎn)4相反的是節(jié)點(diǎn) 7.這樣當(dāng)節(jié)點(diǎn) 4收到查找索引值00*的請(qǐng)求時(shí),就可以將其轉(zhuǎn)發(fā)到節(jié)點(diǎn)7.

圖1 P-Grid實(shí)例Fig.1 P-Grid example

1.2 P-Grid構(gòu)建過(guò)程

P-Grid中節(jié)點(diǎn)被假設(shè)局部隨機(jī)相遇,而不考慮是何種原因相遇.相遇后根據(jù)雙方已有的路徑值劃分并負(fù)責(zé)索引值空間,路徑值做相應(yīng)的調(diào)整.節(jié)點(diǎn)路徑的初始值表達(dá)為*,說(shuō)明其初始負(fù)責(zé)全體索引值空間.下面簡(jiǎn)單描述文獻(xiàn)[5]中的P-Grid構(gòu)建算法.節(jié)點(diǎn)相遇有3種情況:(1)兩節(jié)點(diǎn)原有路徑值相同(CASE1).如path(a1)=10,path(a2)=10,則兩者對(duì)10*空間進(jìn)一步劃分,或者二者互為冗余節(jié)點(diǎn)共同負(fù)責(zé)10*空間;劃分后path(a1)=100,負(fù)責(zé)100*空間; path(a2)=101,負(fù)責(zé)101*空間.(2)兩節(jié)點(diǎn)路徑值是一個(gè)子串關(guān)系(CASE2和CASE3).如path(a1)=10, path(a2)=101,此時(shí)讓path(a1)=100.(3)兩節(jié)點(diǎn)負(fù)責(zé)不同的空間(CASE4),如path(a1)=10, path(a2)=01,則兩節(jié)點(diǎn)根據(jù)自身的路由信息,相互把對(duì)方推薦給在另一空間的其它節(jié)點(diǎn);若a1的一條路由表項(xiàng)為0:a3,則說(shuō)明a3負(fù)責(zé)0*空間,a1將a2推薦給 a3,a2將和 a3根據(jù)相遇情況選擇處理方式,這有可能再次產(chǎn)生推薦;這樣,整個(gè)二進(jìn)制索引值空間被動(dòng)態(tài)地劃分并被各對(duì)等節(jié)點(diǎn)管理.

1.3 P-Grid的收斂性

P-Grid的路徑長(zhǎng)度是動(dòng)態(tài)變化無(wú)限制的,這也是它和其它覆蓋網(wǎng)絡(luò)的區(qū)別.因此收斂性表現(xiàn)為在節(jié)點(diǎn)規(guī)模一定的前提下,多少次交互后每個(gè)節(jié)點(diǎn)的路徑不再變化,或是到達(dá)指定的長(zhǎng)度,或是達(dá)到其它的限制條件.文獻(xiàn)[5]通過(guò)實(shí)驗(yàn)指出了 3個(gè)參數(shù)對(duì)交互次數(shù)的影響:(1)推薦(遞歸)深度recmax,即CASE4導(dǎo)致再次推薦的次數(shù).recmax=0表示不推薦,即,若出現(xiàn)CASE4情況相遇節(jié)點(diǎn)相互不推薦,這導(dǎo)致整個(gè)構(gòu)建過(guò)程的交互次數(shù)較多.采用適當(dāng)?shù)纳疃戎悼梢允菇换コ晒Φ母怕试龃?但遞歸深度過(guò)大反而會(huì)導(dǎo)致節(jié)點(diǎn)過(guò)度細(xì)化,而使交互次數(shù)增多,文獻(xiàn)實(shí)驗(yàn)指出recmax=2較好.(2)最大路徑長(zhǎng)度k.這里并不是將P-Grid的路徑長(zhǎng)度限制為k,而是指在節(jié)點(diǎn)個(gè)數(shù)允許的情況下,想達(dá)到的 k越長(zhǎng)則需要的交互次數(shù)越多.(3)節(jié)點(diǎn)每層路由項(xiàng)中節(jié)點(diǎn)的個(gè)數(shù)refmax,refmax為在CASE4情況下進(jìn)行節(jié)點(diǎn)推薦的最大個(gè)數(shù),推薦的個(gè)數(shù)越多,交互次數(shù)越多,文獻(xiàn)實(shí)驗(yàn)指出當(dāng)推薦選擇一個(gè)節(jié)點(diǎn)時(shí)效果最好.下面討論的收斂速度的提升是在指定k、recmax、refmax以及推薦個(gè)數(shù)的基礎(chǔ)上進(jìn)行的.

2 提高收斂速度的改進(jìn)算法

提高收斂速度的改進(jìn)算法基于以下兩個(gè)前提:

(1)忽略節(jié)點(diǎn)動(dòng)態(tài)性對(duì)構(gòu)建過(guò)程中路由維護(hù)帶來(lái)的影響,將提高兩個(gè)在線節(jié)點(diǎn)交互的有效性與路由維護(hù)看成獨(dú)立的兩個(gè)內(nèi)容,不管算法如何改進(jìn)都無(wú)法影響節(jié)點(diǎn)的上線和離線行為,所以將節(jié)點(diǎn)的動(dòng)態(tài)行為對(duì)構(gòu)建的影響看成是一個(gè)不變的量,不再計(jì)入評(píng)價(jià)范圍內(nèi).

(2)P-Grid不僅僅用于動(dòng)態(tài)的P2P系統(tǒng),還可以作為任何一個(gè)分布式應(yīng)用需求下的基礎(chǔ)結(jié)構(gòu).PGrid的構(gòu)建過(guò)程在分布式應(yīng)用中可位于兩個(gè)不同階段:第一,在完全新的分布式應(yīng)用中P-Grid的構(gòu)建位于初始化階段,節(jié)點(diǎn)專用于該應(yīng)用,此時(shí)節(jié)點(diǎn)上不存在任何數(shù)據(jù)索引信息;第二,在已有的分布式應(yīng)用中,由于某種原因,要求利用P-Grid重建基礎(chǔ)結(jié)構(gòu),此時(shí)節(jié)點(diǎn)上將保留原有的共享數(shù)據(jù)索引信息.下面的討論與改進(jìn)將從構(gòu)建前節(jié)點(diǎn)無(wú)數(shù)據(jù)索引和有數(shù)據(jù)索引兩方面進(jìn)行.

定義1 數(shù)據(jù)索引的消耗 數(shù)據(jù)索引在節(jié)點(diǎn)上的存儲(chǔ)除了帶來(lái)存儲(chǔ)上的消耗.還帶來(lái)其它的消耗,如某一數(shù)據(jù)是熱點(diǎn)數(shù)據(jù),則將為存儲(chǔ)它的索引的節(jié)點(diǎn)帶來(lái)較高的訪問(wèn)頻率,這可看成對(duì)節(jié)點(diǎn)的一種消耗.這里并不區(qū)分特定的消耗類型,每一個(gè)數(shù)據(jù)索引將因?yàn)槠渥陨頂?shù)據(jù)的特點(diǎn)給節(jié)點(diǎn)帶來(lái)不同的消耗.同時(shí)假設(shè)數(shù)據(jù)索引的消耗是可分的,即當(dāng)一個(gè)數(shù)據(jù)索引被復(fù)制到另一個(gè)節(jié)點(diǎn)上時(shí),其消耗也將被分割一部分到該節(jié)點(diǎn);而當(dāng)一個(gè)索引被轉(zhuǎn)移至另一節(jié)點(diǎn)時(shí),則其消耗也被轉(zhuǎn)移.

定義2 節(jié)點(diǎn)的意愿 每個(gè)節(jié)點(diǎn)會(huì)根據(jù)自己的資源現(xiàn)狀給出承擔(dān)數(shù)據(jù)索引消耗的總意愿,如設(shè)置訪問(wèn)次數(shù)的上限防止對(duì)數(shù)據(jù)索引的過(guò)多的查詢.

定義3 節(jié)點(diǎn)的負(fù)載 存儲(chǔ)數(shù)據(jù)索引值帶來(lái)的總消耗稱為節(jié)點(diǎn)的負(fù)載.

定義4 節(jié)點(diǎn)的初始負(fù)載量loadpercentage 節(jié)點(diǎn)在進(jìn)入交互前因?yàn)槠渌蚨哂械呢?fù)載量,用節(jié)點(diǎn)的負(fù)載與節(jié)點(diǎn)意愿的比值表示.

定義5 Ignore-of-Load構(gòu)建算法 構(gòu)建過(guò)程中不考慮節(jié)點(diǎn)的初始負(fù)載量.

定義6 Care-of-Load構(gòu)建算法 構(gòu)建過(guò)程中考慮節(jié)點(diǎn)的意愿及初始負(fù)載量.

定義7 數(shù)據(jù)索引路徑符合度satisfy 一個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)索引中符合與節(jié)點(diǎn)路徑具有最大前綴關(guān)系的索引個(gè)數(shù)百分比.節(jié)點(diǎn)路徑為“*”時(shí)路徑符合度為1.

定義 8 收斂狀態(tài)參數(shù) 描述交互算法的狀態(tài),用于衡量收斂性,采用路徑長(zhǎng)度k和符合度 satisfy兩個(gè)參數(shù).在Care-of-Load情況下,受節(jié)點(diǎn)意愿的限制,導(dǎo)致本該能轉(zhuǎn)移的數(shù)據(jù)索引無(wú)法轉(zhuǎn)移,因此要求已存在的索引都轉(zhuǎn)移到具有最大前綴關(guān)系的節(jié)點(diǎn)上所需的交互次數(shù)非常大,所以應(yīng)該設(shè)置一定的符合度來(lái)描述收斂狀態(tài).

定義9 收斂速度 達(dá)到指定收斂狀態(tài)參數(shù)值產(chǎn)生的節(jié)點(diǎn)交互次數(shù).

2.1 Ignore-of-Load構(gòu)建算法

每次交互引起的路徑變化程度以及推薦的成功率影響交互的次數(shù).原有構(gòu)建算法中路徑的改變以“1位”為單位,如:兩節(jié)點(diǎn)a1、a2相遇,path(a1)= 01001、path(a2)=01,向下劃分后路徑為path(a1)= 01001、path(a2)=011.對(duì)于a2需要更多的交互才能使其路徑向下延伸.為了充分利用每次交互的信息,減少交互的次數(shù),給出如下式所示的改進(jìn)1:

即直接將a2的路徑延長(zhǎng)為path(a2)=01000,使其最后一位與a1相反,a2與 a1交換前4層的路由.

根據(jù)原構(gòu)建算法,節(jié)點(diǎn)p向節(jié)點(diǎn)q推薦節(jié)點(diǎn)r采用的推薦方式有兩種,一種是在 p的路由表中隨機(jī)選取節(jié)點(diǎn)r[5],另一種是選取p的路由表中與q具有最大共同前綴的節(jié)點(diǎn)[9],但文獻(xiàn)并未對(duì)這兩種方式做出比較.通過(guò)觀察節(jié)點(diǎn)的路由表的特點(diǎn),以path(q)=101、path(p)=01為例,若p的路由表第一層為1:a3(111),a4(100),a5(101),a6(10110),可以看出選擇推薦a6和a5會(huì)使q路徑向下劃分,而選擇a3則在q和 a3的交互過(guò)程中需要在第二層進(jìn)行推薦,若推薦的節(jié)點(diǎn)不合適還要進(jìn)行第三層的推薦,a4比 a3的情況好一點(diǎn),只需要在第三層推薦一次.根據(jù)該特點(diǎn)給出改進(jìn)2以提高推薦的成功率:

p從路由表中首選一個(gè)以 q路徑為子串的節(jié)點(diǎn);若沒(méi)有,則選與q同路徑的節(jié)點(diǎn);若再?zèng)]有,則再選與q具有最大共同前綴的節(jié)點(diǎn);若還是沒(méi)有,則最后隨機(jī)選.

2.2 Care-of-Load構(gòu)建算法

在構(gòu)建覆蓋網(wǎng)絡(luò)的過(guò)程中,數(shù)據(jù)索引會(huì)隨著節(jié)點(diǎn)路徑的形成而轉(zhuǎn)移到具有最大前綴關(guān)系的節(jié)點(diǎn)上.這里討論 3種思路,采用路徑長(zhǎng)度及符合度作為收斂狀態(tài)參數(shù).

2.2.1 以路徑為主導(dǎo)的構(gòu)建算法

以路徑為主導(dǎo)的算法指節(jié)點(diǎn)路徑的向下延伸與數(shù)據(jù)索引的轉(zhuǎn)移是獨(dú)立的,即節(jié)點(diǎn)路徑向下延伸不受節(jié)點(diǎn)意愿和索引消耗的影響,而數(shù)據(jù)索引的轉(zhuǎn)移則是在每次節(jié)點(diǎn)相遇時(shí)根據(jù)雙方的路徑和意愿盡量將索引轉(zhuǎn)移到對(duì)方.因此該算法的實(shí)現(xiàn)直接在2.1節(jié)的兩個(gè)改進(jìn)上進(jìn)行,在每個(gè)CASE結(jié)束后加入數(shù)據(jù)索引交換環(huán)節(jié).最優(yōu)交換是一個(gè)最優(yōu)組合問(wèn)題,這里不考慮最優(yōu)化的問(wèn)題,只關(guān)心盡可能多地進(jìn)行索引的交換.交換分冗余和轉(zhuǎn)移兩種,當(dāng)兩節(jié)點(diǎn)路徑值相同時(shí),相互冗余數(shù)據(jù)索引,否則根據(jù)對(duì)方路徑轉(zhuǎn)移.一個(gè)數(shù)據(jù)索引被冗余到目標(biāo)節(jié)點(diǎn)上,意味著減輕源節(jié)點(diǎn)一半的消耗,則索引消耗也將被分割一半到目標(biāo)節(jié)點(diǎn);而一個(gè)索引被轉(zhuǎn)移目標(biāo)節(jié)點(diǎn),則其消耗也被轉(zhuǎn)移.

2.2.2 以數(shù)據(jù)索引為主導(dǎo)的構(gòu)建算法

采用2.2.1節(jié)的算法每個(gè)節(jié)點(diǎn)可以很快達(dá)到指定的最大路徑長(zhǎng)度,但符合度低,為了達(dá)到指定的符合度則需要花費(fèi)更多的交互次數(shù).文獻(xiàn)[8]給出了考慮數(shù)據(jù)索引的思路:當(dāng)兩個(gè)節(jié)點(diǎn)相遇,若每個(gè)節(jié)點(diǎn)都能將兩個(gè)節(jié)點(diǎn)所擁有的所有數(shù)據(jù)索引全部放下,則兩節(jié)點(diǎn)冗余,否則就分區(qū).但該文獻(xiàn)假設(shè)所有節(jié)點(diǎn)是同質(zhì)的且具有相同的意愿,并且節(jié)點(diǎn)的意愿僅體現(xiàn)為愿意管理的數(shù)據(jù)索引個(gè)數(shù),數(shù)據(jù)索引之間無(wú)差別.這里結(jié)合節(jié)點(diǎn)的意愿和索引消耗對(duì)文獻(xiàn)[8]的算法進(jìn)行擴(kuò)展,形成以數(shù)據(jù)索引為主導(dǎo)的構(gòu)建算法.算法中路徑的延長(zhǎng)不是任何時(shí)候都可以進(jìn)行的,即,原算法CASE1中先進(jìn)行是否冗余(isRedundent)和是否下分(isDivide)的判斷,在CASE2和CASE3中先進(jìn)行是否延伸路徑的判斷(isExtend).

isDivide的思路如下:Max(Min)表示兩個(gè)節(jié)點(diǎn)中具有高(低)意愿的節(jié)點(diǎn);Ci是節(jié)點(diǎn)i中與兩節(jié)點(diǎn)路徑都不符的索引消耗總和;Preferi表示節(jié)點(diǎn)i的意愿;Totall表示兩個(gè)節(jié)點(diǎn)中以path+l為路徑的索引消耗總和,path表示兩節(jié)點(diǎn)的路徑(此時(shí)路徑相同),l∈{0,1}.當(dāng)存在l∈{0,1}使

成立時(shí),則可以下分,即下分依賴于即將形成的兩個(gè)分區(qū)中的索引是否可以分別放在兩個(gè)節(jié)點(diǎn)中.

isRedundent的思路如下:Ax表示節(jié)點(diǎn)x中與相遇節(jié)點(diǎn)共有的且符合路徑的數(shù)據(jù)索引消耗總和,Bx表示節(jié)點(diǎn) x獨(dú)有且符合路徑的數(shù)據(jù)索引消耗總和, a1和a2表示相遇的兩個(gè)節(jié)點(diǎn),當(dāng)下式成立才能進(jìn)行冗余:

對(duì)于isExtend,只有當(dāng)長(zhǎng)路徑的節(jié)點(diǎn)能夠完全接受短路徑轉(zhuǎn)過(guò)來(lái)的索引消耗時(shí),短路徑才能向下延伸一位.

2.2.3 具有符合度調(diào)整的構(gòu)建算法

在2.2.2節(jié)算法中,盡管符合度相對(duì)較高,但路徑的延伸過(guò)程非常慢,若每個(gè)節(jié)點(diǎn)的意愿足夠大將導(dǎo)致一個(gè)節(jié)點(diǎn)放置所有的數(shù)據(jù)索引,而這樣的結(jié)果對(duì)于構(gòu)建P-Grid意義不大.因?yàn)镻-Grid路由結(jié)構(gòu)的建立是本研究的主要任務(wù),構(gòu)建過(guò)程會(huì)影響索引的分布,這里僅僅期望索引能隨構(gòu)建過(guò)程達(dá)到一個(gè)較好的調(diào)整.

為了在收斂速度及符合度間獲得一個(gè)平衡,對(duì)2.2.1節(jié)算法進(jìn)行改進(jìn),形成具有符合度調(diào)整的算法.算法中的函數(shù)Peer.FindPeer()用于在節(jié)點(diǎn)交互結(jié)束后各自依據(jù)自身的路由信息盡量將索引轉(zhuǎn)移到合適的節(jié)點(diǎn),以此提升符合度.Peer.FindPeer()算法如下:

通過(guò)分析可知一個(gè)節(jié)點(diǎn)中需要轉(zhuǎn)移的索引所具有的特點(diǎn),如路徑為 0101的節(jié)點(diǎn),其不合路徑的數(shù)據(jù)索引可分為 1、00、011、0100 4類,這正好與每層路由表項(xiàng)的前綴是一致的.因此可以考慮在路由表中選擇節(jié)點(diǎn)進(jìn)行索引的轉(zhuǎn)移以提高符合度,但由轉(zhuǎn)移導(dǎo)致的交互也應(yīng)該統(tǒng)計(jì)進(jìn)入交互總數(shù).此外存在一個(gè)現(xiàn)象,即節(jié)點(diǎn)a、b經(jīng)過(guò)CASE1、CASE2、CASE3向下延伸后,a的最后一層路由表項(xiàng)往往只有一個(gè)節(jié)點(diǎn)b,或是b的最后一層路由表項(xiàng)只有一個(gè)節(jié)點(diǎn)a,此時(shí)再次進(jìn)行轉(zhuǎn)移意義不大,需要利用倒數(shù)第二層表項(xiàng)來(lái)提高符合度.以a(0101)節(jié)點(diǎn)為例,若倒數(shù)第二層路由表項(xiàng)為011:a3(011),且a3的最后一層路由為010:a4(010),a5(0101),a6(0100),則若能挑出a6,將a上形如 0100的索引轉(zhuǎn)過(guò)去,將會(huì)提高a的符合度.

3 算法分析

3.1 Ignore-of-Load算法中路由更新相關(guān)問(wèn)題

每個(gè)節(jié)點(diǎn)由于承擔(dān)路由功能而成為路由表項(xiàng)中的一員,節(jié)點(diǎn)的路徑是推薦的依據(jù).路由的更新來(lái)自于兩節(jié)點(diǎn)交互時(shí)充分交換最新信息.這里不討論如何設(shè)計(jì)出更好、更新的算法,側(cè)重分析在采用與原算法相同的更新算法下,Ignore-of-Load構(gòu)建算法是否會(huì)加重更新的負(fù)擔(dān),以及未及時(shí)更新的路由信息是否對(duì)推薦產(chǎn)生影響.

(1)路由更新的負(fù)擔(dān)與節(jié)點(diǎn)路徑改變的概率相關(guān).考慮到節(jié)點(diǎn)路徑的改變導(dǎo)致路由需要更新,將路由更新的負(fù)擔(dān)定義為整個(gè)系統(tǒng)中單位時(shí)間內(nèi)路徑改變的節(jié)點(diǎn)個(gè)數(shù).設(shè)每個(gè)節(jié)點(diǎn)在每次相遇中改變路徑的概率是s,在一定的時(shí)間段t內(nèi),有n個(gè)節(jié)點(diǎn)相遇,則單位時(shí)間內(nèi)改變路徑的節(jié)點(diǎn)為ns/t個(gè).在節(jié)點(diǎn)相遇頻率不變的情況下,s越大,則更新負(fù)擔(dān)越大.

(2)原算法一次相遇中節(jié)點(diǎn)路徑改變的概率為1/2len(p),改進(jìn) 1不影響路徑改變概率.設(shè)節(jié)點(diǎn) p的路徑為l1l2…llen,lj(0,1),j[1,len],節(jié)點(diǎn)路徑的改變來(lái)自于與同路徑或前綴為 l1l2…llen的節(jié)點(diǎn)相遇.設(shè)索引值均勻分布,節(jié)點(diǎn)相遇的概率平等,不存在過(guò)多的節(jié)點(diǎn)負(fù)責(zé)某些分區(qū),則與相遇的節(jié)點(diǎn)第一位相同的概率為1/2,在第一位相同的情況下第二位相同的概率為1/22,這樣在前l(fā)en-1位相同下最后一位相同的概率為 1/2len(p),則路徑改變的概率為1/2len(p).

按照改進(jìn) 1的延伸方法也不能導(dǎo)致負(fù)責(zé)某些特定分區(qū)的節(jié)點(diǎn)增多,如對(duì)于path(a1)=01與path(a2)= 01001相遇,使path(a1)=01000,這并不意味著負(fù)責(zé)0100區(qū)域的節(jié)點(diǎn)增多,因?yàn)楦鶕?jù)P-Grid結(jié)構(gòu)若存在path(a2)=01001,則必然會(huì)存在路徑為1*、00*、011*、0101*的節(jié)點(diǎn),而節(jié)點(diǎn)相遇的概率是一樣的,這樣仍然不存在過(guò)多的節(jié)點(diǎn)負(fù)責(zé)某些分區(qū),從而不影響路徑改變概率.

從上面可知路徑改變的概率不變,這樣改進(jìn) 1不會(huì)加重更新的負(fù)擔(dān).

(3)延時(shí)更新的節(jié)點(diǎn)路徑不會(huì)導(dǎo)致改進(jìn) 2低于原算法的收斂速度.節(jié)點(diǎn)路徑的變化是在前一次的路徑基礎(chǔ)上向下延伸,必定存在前綴關(guān)系.這樣對(duì)于未及時(shí)更新的節(jié)點(diǎn),在改進(jìn) 2中只是降低了它被推薦的可能性.以path(q)=101、path(p)=01為例,若p當(dāng)前的路由表第一層為1:a3(111),a4(100), a5(101),a6(10);而 a6(10)實(shí)際的路徑為a6(10110),這樣根據(jù)改進(jìn) 2,a5被優(yōu)先選擇,但這種選擇仍然優(yōu)于原算法隨機(jī)方法或原算法最大前綴方法.因此改進(jìn)算法不會(huì)低于原算法的收斂速度.

3.2 改進(jìn)算法產(chǎn)生二叉樹的特性

特性1 Ignore-of-Load構(gòu)建算法、以路徑為主導(dǎo)的構(gòu)建算法及具有符合度調(diào)整的Care-of-Load構(gòu)建算法產(chǎn)生的是一棵完全二叉樹.指定最大路徑長(zhǎng)度,在節(jié)點(diǎn)數(shù)量足夠的情況下,短路徑的節(jié)點(diǎn)總會(huì)與長(zhǎng)路徑的節(jié)點(diǎn)相遇從而延伸直到所有的節(jié)點(diǎn)都達(dá)到最大路徑,并且根據(jù)P-Grid的構(gòu)建特性,節(jié)點(diǎn)路徑的每一位上都至少存在一個(gè)節(jié)點(diǎn)與之具有相反位.

特性2 Ignore-of-Load構(gòu)建算法、以路徑為主導(dǎo)的構(gòu)建算法及具有符合度調(diào)整的Care-of-Load構(gòu)建算法最終產(chǎn)生前綴碼.與特性 1的分析類似,如果存在一個(gè)節(jié)點(diǎn),它是另一個(gè)節(jié)點(diǎn)的前綴,則說(shuō)明構(gòu)建還未完成,前一個(gè)節(jié)點(diǎn)必定會(huì)向下延伸,且最后一位相反.

特性3 以數(shù)據(jù)為主的Care-of-Load構(gòu)建算法不保證產(chǎn)生前綴碼.原因在于路徑的向下延伸受節(jié)點(diǎn)意愿的制約,使得路徑停留在某個(gè)長(zhǎng)度.

3.3 數(shù)據(jù)索引查找成功率

設(shè)路徑長(zhǎng)度為k,節(jié)點(diǎn)數(shù)為N,則第h層各分區(qū)擁有的平均節(jié)點(diǎn)數(shù)為N/2h,h[0,k],定義T為單個(gè)節(jié)點(diǎn)擁有的符合路徑的索引占其負(fù)責(zé)分區(qū)的總索引數(shù)比例,一般使refmax≤N/2h并對(duì)所有層取相同值,節(jié)點(diǎn)在線概率為Pr,則Care-of-Load構(gòu)建算法中對(duì)數(shù)據(jù)索引的查找成功率為(1-(1-Pr)refmax)k× T.當(dāng)不考慮節(jié)點(diǎn)的離線情況時(shí)Pr=1,則成功查找率由T決定.

最壞情況下的成功查找次數(shù)為log2(N/r′)× refmaxΘ(log2N),r′為負(fù)責(zé)最低層分區(qū)的節(jié)點(diǎn)平均個(gè)數(shù).

4 模擬實(shí)驗(yàn)

模擬實(shí)驗(yàn)采用P2P模擬器Peersim[13],PeerSim是一個(gè)Java編寫的模擬P2P Overlay的軟件.使用Peersim提供的占用較少資源的Cycle-based的模擬方式,模擬實(shí)驗(yàn)共同參數(shù)定義為:recmax=2,最大路徑長(zhǎng)度k=6,refmax=10,推薦時(shí)采用1個(gè)節(jié)點(diǎn).

4.1 Ignore-of-Load構(gòu)建算法的模擬實(shí)驗(yàn)

節(jié)點(diǎn)規(guī)模 N分別為 400、600、1000時(shí),對(duì)原算法隨機(jī)版、原算法最大前綴版及 3個(gè)改進(jìn)算法(改進(jìn) 3為 1和 2的組合)分別執(zhí)行 100次后的平均交互次數(shù)如圖2所示.

圖2 5種Ignore-of-Load算法的交互次數(shù)Fig.2 Number of communications times of five Ignore-of-Load algorithms

由圖 2可見,3個(gè)改進(jìn)算法帶來(lái)的效果是非常明顯的.特別是改進(jìn) 3,交互次數(shù)的減少量超過(guò)原算法最大前綴版的50%.

4.2 Care-of-Load構(gòu)建算法的模擬實(shí)驗(yàn)

數(shù)據(jù)索引的消耗以及數(shù)據(jù)索引的副本個(gè)數(shù)采用平均分布和Zip f分布,在不同的分布下分別比較3種Care-of-Load構(gòu)建算法在交互過(guò)程中的交互次數(shù)及查找失敗率.

4.2.1 平均分布

節(jié)點(diǎn)規(guī)模 N=400,每個(gè)節(jié)點(diǎn)的意愿數(shù)量級(jí)為103,平均分布在[1000,10000]之間,數(shù)據(jù)索引規(guī)模M=1000,數(shù)量級(jí)為 102,平均分布在[100,1 000]之間,數(shù)據(jù)索引在每個(gè)節(jié)點(diǎn)中存儲(chǔ)的概率是平等的.

3個(gè)算法在一次構(gòu)建過(guò)程中平均路徑長(zhǎng)度及符合度的變化趨勢(shì)如圖 3所示,設(shè)隨機(jī)進(jìn)行 20000次交互.

圖3 3種Care-of-Load構(gòu)建算法平均路徑長(zhǎng)度及平均符合度的變化趨勢(shì)Fig.3 Average path length and average satisfaction of three Care-of-Load algorithms

從圖 3可見,以路徑為主導(dǎo)的算法在路徑的延伸上很快,但符合度的下降也很迅速;以索引為主導(dǎo)的算法正好相反;具有符合度調(diào)整的算法效果是兩者的折中,并且符合度可以達(dá)到最好.同時(shí)由圖 3可見,3種算法中,數(shù)據(jù)的轉(zhuǎn)移跟不上路徑延伸的速度,當(dāng)路徑達(dá)到指定長(zhǎng)度后,接下來(lái)的交互僅僅是在進(jìn)行數(shù)據(jù)索引的交換,而這個(gè)過(guò)程是緩慢的.

3種算法在不同的loadpercentage下同時(shí)達(dá)到指定路徑長(zhǎng)度和符合度(satisfy=0.8)所需的交互次數(shù)如圖4所示.考慮到以數(shù)據(jù)索引為主導(dǎo)的算法在路徑延伸上的缺陷,參數(shù)設(shè)置為當(dāng)loadpercentage= 0.2,0.3,0.4時(shí),指定k=2.8,4,5;loadpercentage= 0.5,0.6,0.7,0.8時(shí),k=5.5.以路徑為主導(dǎo)的算法和具有符合度調(diào)整的算法k=6.

圖4 3種Care-of-Load構(gòu)建算法的交互次數(shù)Fig.4 Number of communications of three Care-of-Load algorithms

圖4所示結(jié)果說(shuō)明:(1)當(dāng)loadpercentage≤0.5時(shí),以路徑為主導(dǎo)的算法的交互次數(shù)偏小,其原因之一為較小的loadpercentage使得當(dāng)路徑達(dá)到指定長(zhǎng)度時(shí),無(wú)需過(guò)多的交互用于數(shù)據(jù)索引的交換,但隨著loadpercentage的增加,需要大量的交互用于數(shù)據(jù)索引的交換;原因之二為構(gòu)建過(guò)程的終止條件satisfy=0.8是一個(gè)較容易達(dá)到的條件,若將satisfy設(shè)置得更高(如satisfy=0.9),則該算法不如具有符合度調(diào)整的算法(見圖5).另外在loadpercentage偏大時(shí)表現(xiàn)良好的算法才有意義,因?yàn)檩^小的loadpercentage無(wú)法體現(xiàn)出初始負(fù)載對(duì)構(gòu)建過(guò)程帶來(lái)的影響. (2)當(dāng)loadpercentage≤0.5時(shí),以數(shù)據(jù)索引為主導(dǎo)的算法的交互次數(shù)偏小,但存在 2.2.3節(jié)中所述的缺陷,每個(gè)節(jié)點(diǎn)將放置所有的數(shù)據(jù)索引,而這樣的結(jié)果對(duì)于構(gòu)建P-Grid意義不大.(3)具有符合度調(diào)整的算法在具有較大loadpercentage時(shí)表現(xiàn)良好,因?yàn)橥ㄟ^(guò)符合度的調(diào)整,使得節(jié)點(diǎn)交互具有針對(duì)性.

圖5 Zipf分布下的交互次數(shù)Fig.5 Number of communications Zipf distribution

以數(shù)據(jù)為主導(dǎo)的算法和具有符合度調(diào)整的算法對(duì)初始數(shù)據(jù)索引的查找失敗率如表1所示.loadpercentage的取值在0.2～0.8之間,并采用了一個(gè)混合比例即每個(gè)節(jié)點(diǎn)的loadpercentage隨機(jī)在0.2～0.8之間取值;每個(gè)初始值下兩類算法各產(chǎn)生 20個(gè)P-Grid結(jié)構(gòu),對(duì)每個(gè)結(jié)構(gòu)查詢 2000次,統(tǒng)計(jì)失敗的次數(shù);為了比較兩類算法對(duì)查找的影響,設(shè)節(jié)點(diǎn)總是在線.表1中A和C表示以數(shù)據(jù)為主導(dǎo)的算法失敗次數(shù)和節(jié)點(diǎn)擁有索引占分區(qū)平均比例,即 3.3節(jié)中定義的T;B和D表示具有符合度調(diào)整的算法失敗次數(shù)和節(jié)點(diǎn)擁有索引占分區(qū)平均比例.表 1所示結(jié)果說(shuō)明:(1)查找失敗率與節(jié)點(diǎn)擁有索引占分區(qū)平均比例相關(guān),如119≈2000×(1-0.92);(2)當(dāng)loadpercentage為0.2～0.4時(shí),A與C的值不符合(1)的結(jié)論,原因在于,其路徑長(zhǎng)度不超過(guò) 4,分區(qū)擁有的索引多,但因?yàn)槭Ｓ嘁庠复?所以每個(gè)節(jié)點(diǎn)都極大地放置了該分區(qū)的索引,使得整體查找失敗率減少;(3)隨著loadpercentage的增加,具有符合度調(diào)整的算法表現(xiàn)出較好的查找效果,原因在于有針對(duì)性地轉(zhuǎn)移了數(shù)據(jù).

表1 平均分布下的查找失敗率Table 1 Search failure rate in average distribution

4.2.2 Zipf分布

文獻(xiàn)[14]總結(jié)出 P2P環(huán)境下副本的數(shù)量和流行程度遵循Zipf分布.模仿文獻(xiàn)[15]產(chǎn)生Zipf分布數(shù)據(jù)的方式,選定一個(gè)特定的文檔將其中出現(xiàn)的不同的單詞個(gè)數(shù)(1793)作為數(shù)據(jù)索引個(gè)數(shù),單詞出現(xiàn)的頻率(不超過(guò)850)作為索引的消耗,并且同時(shí)作為索引的副本個(gè)數(shù),使得數(shù)據(jù)索引的消耗以及索引的副本個(gè)數(shù)符合Zipf分布.設(shè)置節(jié)點(diǎn)規(guī)模為1 000,數(shù)據(jù)索引規(guī)模M=1793.3種算法的平均路徑長(zhǎng)度及符合度的變化趨勢(shì)與平均分布下的趨勢(shì)一致,這里不再給出圖形結(jié)果.

比較以路徑為主導(dǎo)的算法和具有符合度調(diào)整的算法在不同的loadpercentage下,同時(shí)達(dá)到指定k=6和satisfy=0.9所需的交互次數(shù)如圖5所示.根據(jù)2.2.3節(jié)中的分析,這里不再比較以數(shù)據(jù)為主導(dǎo)的算法,因?yàn)樽罱K的平均路徑長(zhǎng)度都在 2到 3的范圍內(nèi),這樣的構(gòu)建意義不大.

由圖 5可見,具有符合度調(diào)整的算法的效果較好.當(dāng)loadpercentage=0.8時(shí),以路徑為主導(dǎo)的算法交互次數(shù)已超過(guò) 100000次,因此未在圖上顯示.

具有符合度調(diào)整的算法對(duì)初始數(shù)據(jù)索引的查找失敗率如表 2所示.同前,這里不再比較以數(shù)據(jù)為主導(dǎo)的算法的失敗率.

表2 Zip f分布下的查找失敗率Table 2 Search failure rate in Zip f distribution

loadpercentage的取值在0.2～0.8之間,并采用了一個(gè)混合比例.每個(gè)初始值下兩類算法各產(chǎn)生 20個(gè)P-Grid結(jié)構(gòu),對(duì)每個(gè)結(jié)構(gòu)查詢 10000次,統(tǒng)計(jì)失敗的次數(shù).表 2中符號(hào)定義與表1相同.從實(shí)驗(yàn)結(jié)果可知,具有符合度調(diào)整的算法的查找失敗率與 T相關(guān),并且查找成功率在90%左右.

5 結(jié)語(yǔ)

(1)P-Grid構(gòu)建算法的收斂速度是影響建立在其上系統(tǒng)性能的關(guān)鍵因素,文中針對(duì)構(gòu)建的兩種初始情況Ignore-of-Load和Care-of-Load,對(duì)原構(gòu)建算法進(jìn)行改進(jìn);改進(jìn)的算法能保持原算法的分散性和自組織性,且不增加路由更新的負(fù)擔(dān).

(2)模擬實(shí)驗(yàn)結(jié)果表明,Ignore-of-Load構(gòu)建算法能減少原算法交互次數(shù)的50%以上;具有符合度調(diào)整的Care-of-Load構(gòu)建算法在交互次數(shù)上表現(xiàn)良好,并且對(duì)數(shù)據(jù)索引的查找成功率在90%左右.

[1] Dabek F,Kaashoek M,Karger D.W ide-area cooperative storage with CFS[C]∥ACM Symposium on Operating Systems Princip les.New York:ACM,2001:202-215.

[2] Kubiatowicz J,Wells C,Zhao Ben.Oceanstore:an architecture for global-scale persistent storage[J].ACM SIgpan Notices,2000,35(11):190-201.

[3] Zhang Zheng,Lian Qiao,Lin Shi-ding.Bitvault:a highly reliab le distributed data retention p latform[J].ACM SIGOPSOperating Systems Review,2007,41(2):27-36.

[4] 胡進(jìn)鋒,洪春輝,鄭緯民.一種面向?qū)ο蟮腎nternet存儲(chǔ)服務(wù)系統(tǒng)Granary[J].計(jì)算機(jī)研究與發(fā)展,2007,44 (6):1071-1079.

Hu Jin-feng,Hong Chun-hui,Zheng Wei-min.Granary:an architecture of object oriented internet storage service [J].Journal of Computer Research and Development, 2007,44(6):1071-1079.

[5] Karl Aberer.P-Grid:a self-organizing access structure for P2P information system s[C]∥Proceedings of the 9th International Conference on Cooperative Information Systems.Berlin/Heidelberg:Springer,2001:179-194.

[6] Karl A,Magdalena P.Im proving data access in P2P systems[J].IEEE Internet Computing,2002,6(1):58-67.

[7] Karl A,Anwitaman D,Manfred H.Effcient,self-contained handling of identity in Peer-to-Peer systems[J].IEEE Transactions on Knowledge and Data Engineering,2004, 16(7):858-869.

[8] Manfred H,Anwitaman D,Karl A.Handling identity in Peer-to-Peer systems[C]∥Proceedings of the 14th International Workshop on Database and Expert Systems App lications.Washington:IEEE Computer Society,2003: 942-946.

[9] Karl A,Anwitaman D,Manfred H.Multifaceted simultaneous load balancing in DHT-based P2P systems:a new game with old balls and bins[EB/OL].(2005-01-01). http:∥www.p-grid.org/publications/papers/SelfStar2005. pdf.

[10] Karl A,Anwitaman D,Manfred H.The quest for balancing peer load in structured Peer-to-Peer systems[EB/OL]. (2003-01-01).http:∥www.p-grid.org/pub lications/ papers/TR-IC-2003-32.pdf.

[11] Xu Li-bo,Wu Guo-xin,You Feng-qin.A structured P2P system withmatch path and probability balance tree[C]∥Proceedings of the First International Multi-Symposiums on Computer and Computational Sciences:Volume 2. Washington:IEEEComputer Society,2006:167-174.

[12] Jagadish H V,Beng C O,Quang H V.BATON:a balanced tree structure for Peer-to-Peer networks[C]∥Proceedings of the 31st International Conference on Very large Data Bases.Norway-Trondheim:VLDB Endowment,2005:661-672.

[13] Márk J,Alberto M,Gian P J,et al.PeerSim:a Peer-to-Peer simulator[EB/OL].(2009-01-01).http:∥peersim.sourceforge.net/.

[14] 張?zhí)?lè),查冰,王勁林.對(duì)等網(wǎng)絡(luò)上數(shù)據(jù)分布模型的分析[J].電子技術(shù)應(yīng)用,2006,32(1):46-47.

Zhang Tai-le,Zha Bin,Wang Jin-lin.Analysis of content distribution in P2P files-share system[J].Application of Electronic Technique,2006,32(1):46-47.

[15] 劉德輝,周寧,尹剛,等.QFMA:一種支持負(fù)載均衡的多屬性資源定位方法 [J].計(jì)算機(jī)學(xué)報(bào),2008,31 (8):1376-1382.

Liu De-Hui,Zhou Ning,Yin Gang,et al.QFMA:an approach for multi-attribute resource addressing with load balancing[J].Chinese Journal of Computers,2008,31 (8):1376-1382.