摘 要： P2P網(wǎng)絡(luò)廣播使用廣度優(yōu)先的泛洪方式，導(dǎo)致對等點的處理負(fù)荷過大,，網(wǎng)絡(luò)流量激增,，容易造成網(wǎng)絡(luò)阻塞。在分析ComNET及組播的基礎(chǔ)上,，提出設(shè)計一個分布式算法，使一對多的消息傳遞變得高效而不含冗余,，以此來解決ComNET中的組播問題,。
關(guān)鍵詞： P2P；組播,；ComNET,；分布式算法
P2P[1]網(wǎng)絡(luò)廣播使用廣度優(yōu)先的泛洪方式，根據(jù)對等點網(wǎng)絡(luò)拓?fù)涞牟煌?，可能有大部分?jié)點會被廣播消息重復(fù)到達(dá),。重復(fù)到達(dá)的消息不僅增加了對等點的處理負(fù)荷，而且大大地增加了網(wǎng)絡(luò)流量,，容易造成網(wǎng)絡(luò)阻塞,。
通過實驗可以簡單地模擬廣度優(yōu)先的泛洪算法[2]在ComNET中進(jìn)行組播消息的傳遞情況，模擬結(jié)果如圖1所示,。
數(shù)據(jù)統(tǒng)計過程如下,。首先使用簡單的廣度優(yōu)先算法在指定的組內(nèi)傳播消息，當(dāng)一個對等點收到一個組播消息后,，記住它曾經(jīng)收到此消息,，然后直接把消息發(fā)送到它所有鄰居。重復(fù)訪問次數(shù)是統(tǒng)計所有對等點收到的重復(fù)消息的總數(shù)（一個對等點可能收到多個重復(fù)消息,，統(tǒng)計時算實際重復(fù)的次數(shù),，而不是一次），圖1（a）所示為重復(fù)的次數(shù)隨著網(wǎng)絡(luò)規(guī)模的增大的情況,，而圖1（b）則給出了重復(fù)消息個數(shù)占發(fā)送消息總數(shù)的比例,。從圖1中可以看到,，無論在比率還是絕對數(shù)量上，重復(fù)消息的量都是很驚人的,。比如當(dāng)對等點數(shù)目為2 M時,，有131 917個消息是無用、重復(fù)接收的,，占發(fā)送出去的消息總數(shù)140 119的94.14%,。這些重復(fù)的消息嚴(yán)重禍害著互聯(lián)網(wǎng)絡(luò)。
本文主要研究討論如何在ComNET指定的對等點組中廣播消息,。方法是首先研究簡單的情況,，即Cayley圖Γ上的組播情況。然后再推廣到動態(tài)網(wǎng)絡(luò)ComNET上,。
1 ComNET及組播分析
現(xiàn)實中一般很少需要在整個網(wǎng)絡(luò)中轉(zhuǎn)發(fā)消息,，因而暫不考慮在整個ComNET上廣播消息的情況,，而把問題集中在如何在某個指定的對等點組中廣播消息,，稱之為組播。問題的更形式化的定義[3]如下,。
1.1 Γ中的組播
給定Cayley圖Γ以及起始頂點P0=（c,，p，r）,，給出以P0為根的一顆轉(zhuǎn)發(fā)樹T,，滿足：
（cn,，pn,，rn）（（cn，pn,，rn）Tcn=c）
（cn,，pn,，rn）（（（cn，pn,，rn）cn=c）（cn,，pn，rn）T）
1.2 ComNET中的組播：
給定一個動態(tài)覆蓋網(wǎng)絡(luò)ComNET以及起始對等點P0=（c,，p,，r），給出以P0為根的一顆轉(zhuǎn)發(fā)樹T,，且滿足：
?。╟n,，pn，rn）（（cn,，pn,，rn）TAPlockall（c，cn,，k））
?。╟n，pn,，rn）（（（cn,，pn，rn）APlockall（c,，cn,，k））（cn，pn,，rn）T）
1.3 Γ中的組播的缺點
圖Γ的一級聚集系數(shù)該值較大,。較大的聚集系數(shù)在直觀上來看是指“一個頂點的鄰居很可能也相互是鄰居”，雖然增大CC1不僅可以增加“瀏覽功能”的可用性以及增強魯棒性,，但較大的CC1對組播是一場噩夢,。可以通過圖2來說明情況,。
假設(shè)組播的起始頂點是P0,，并且組播使用廣度優(yōu)先的方式進(jìn)行擴散。第一步P0會把消息擴散到它的所有4個鄰居中,，其中包括P1,、P2、P3,；接著在第二步,，由于P3同時又是P1和P2的鄰居，所以P3（邏輯上）同時收到它們發(fā)出的組播消息,。同理P1會同時收到P2和P3的組播消息,；P2會收到P1和P3的組播消息。因此僅在兩個時間步內(nèi),，P1,，P2和P3就總共收到了3個相同的消息，而且這些都只是所有消息副本中的很少的一部分,，隨著擴散規(guī)模的擴大,，被重復(fù)到達(dá)的頂點以及重復(fù)到達(dá)的次數(shù)將會大大增加，因而在Γ中使用簡單的廣度優(yōu)先策略來實現(xiàn)組播并不是一種明智的選擇,。
2 ComNET組播樹實現(xiàn)
2.1 算法思路
在Γ上組播消息的關(guān)鍵是生成組播樹,，也就是說轉(zhuǎn)發(fā)關(guān)系圖不能含有環(huán),，因此只要找出一個分布式算法來確定一條從組播樹根P0到其他組播樹頂點P的唯一路徑就能解決組播問題。事實上,，可以把要求再降低一點,，只需找出一個算法routeLastHop[4]用于計算從P0到P的路徑中頂點P的上一跳，然后執(zhí)行以下算法框架groupCast[5]即可,。
輸入：當(dāng)前頂點P的標(biāo)識符（c,，p，r）以及組播樹根標(biāo)識符（c0,，p0,，r0）。
輸出：無,。
forall（（cn,，pn，rn）in P的鄰居集合）
if（c0=cn）
?。╟l,，pl，rl）：=routeLastHop（（cn,，pn,，rn），（c0,，p0,，r0））
if（（c，p,，r）=（cl,，pl，rl））
把組播消息轉(zhuǎn)發(fā)到（cn,，pn,，rn）
end
end
end
輸入：頂點Pn的標(biāo)識符（cn，pn,，rn）以及組播樹根標(biāo)識符（c0,，p0，r0）,。
輸出：唯一地確定從（c0，p0,，r0）到（cn,，pn，rn）的路由路徑中,，（cn,，pn,，rn）的上一跳頂點的標(biāo)識符（cl，pl,，rl）,。
lastDiffPos為p0與pn的除第r0位的最后一個（從左到右）不同位的下標(biāo)，如果找不到則為-1,。
if（r0=rn）
if（lastDiffPos=-1）
?。╟l，pl,，rl）：=（c0,，p0，r0）
else
?。╟l,，pl，rl）：=（cn,，pn,，lastDiffPos）
end
else
if（pn[rn]=p0[rn]）/*上一跳是沿著Linkr的*/
if（lastDiffPos=-1）
（cl,，pl,，rl）：=（cn，pn,，r0）
else
?。╟l，pl,，rl）：=（cn,，pn，lastDiffPos）
end
else/*上一跳是沿著Linkp的*/
?。╟l,，pl，rl）：=（cn,，m（pn,，p0，rn）,，rn）
end
end
問題的復(fù)雜度集中在算法routeLastHop,。Γ上路由的算法如下所示，而算法routeLastHop實際上是該路由算法的逆過程,。
輸入：當(dāng)前頂點的標(biāo)識符（c1,，p1，r1）以及目標(biāo)頂點的標(biāo)識符（c3，p3,，r3）,。
輸出：下一跳頂點的標(biāo)識符（c2，p2,，r2）,。
if（c1=c3（p1=p3（r1=r3）then
目標(biāo)頂點已經(jīng)到達(dá)
else
if（c1=c3（p1=p3）then
（c2,，p2,，r2）：=（c3，p3,，r3）/*第二階段*/
else/*下面屬于第一階段*/
if（lock（c1,，c3，r1）（lock（p1,，p3,，r1））then
/*跳離當(dāng)前地區(qū)，使得可以修正標(biāo)識符的其他維*/
r2是不滿足lock（c1,，c3,，r2）或不滿足lock（p1，p3,，r2）的整數(shù),，且優(yōu)先選擇非r3的整數(shù)。
c2：=c1
p2：=p1
else
if（┐lock（p1,，p3,，r1））then/*修正組內(nèi)標(biāo)識符的當(dāng)前維*/
p2：=m（p1，p3,，r1）
c2：=c1
r2：=r1
else/*修正組標(biāo)識符的當(dāng)前維*/
c2：=m（c1,，c3，r1）
p2：=p1
r2：=r1
end
end
end
end
輸入：當(dāng)前對等點P的標(biāo)識符（c,，p,，r）以及組播樹根標(biāo)識符（c0，p0,，r0）,。
輸出：無。
forall（（cn,，pn,，rn）in P的鄰居集合）
if（APlockall（c0，cn,，k））
?。╟l,，pl，rl）：=routeLastHopDHT（（cn,，pn，rn）,，（c0,，p0，r0））
if（r=rl（isClosetLock（p,，pl,，p0））
把組播消息轉(zhuǎn)發(fā)到（cn，pn,，rn）
end
end
end
輸入：對等點Pn的標(biāo)識符（cn,，pn，rn）以及組播樹根標(biāo)識符（c0,，p0,，r0）。
輸出：唯一地確定從（c0,，p0,，r0）到（cn，pn,，rn）的路由路徑中,，（cn，pn,，rn）的上一跳對等點的標(biāo)識符（cl,，pl，rl）,。
lastDiffPos是除r0外最大的不滿足謂詞APlock（p0,，pn，i,，k）的i,，如果找不到則為-1。
if（r0=rn）
if（lastDiffPos=-1）
?。╟l,，pl，rl）：=（c0,，p0,，r0）
else
（cl,，pl,，rl）：=（cn,，pn，lastDiffPos）
end
else
if（APlock（pn,，p0,，rn，k））/*上一跳是沿著Linkr的*/
if（lastDiffPos=-1）
?。╟l,，pl，rl）：=（cn,，pn,，r0）
else
（cl,，pl,，rl）：=（cn，pn,，lastDiffPos）
end
else/*上一跳是沿著Linkp的*/
?。╟l，pl,，rl）：=（cn,，APm（pn，p0,，rn,，k），rn）
end
end
2.2 ComNET中的組播算法
在第2節(jié)中本文給出了Γ中的組播算法,，事實上只需要在適當(dāng)?shù)牡胤绞褂弥^詞“APlock”代替謂詞“=”就可以得到在ComNET中組播的算法雛形,。但是，另一方面,，ComNET的動態(tài)性導(dǎo)致對等點與Γ上的頂點并不是一一對應(yīng)的,，這又需要對ComNET中的具體組播算法作出相應(yīng)的修改。
先給出組播算法,，然后再分析ComNET和Γ上的這些算法有何不同,。
輸入：兩個對等點標(biāo)識符P1=（c1，p1,，r1）,、P2=（c2，p2,，r2）以及組播樹根對等點標(biāo)識符P0=（c0,，p0，r0）,。
輸出：若（c1,，p1,，r1）相對于（c0，p0,，r0）最親密鎖定（c2,，p2，r2）,，則true,，否則false。
for（i：=0…|p1|-1）
if（i（|p2|（p2[i]=（*（）
if（i<|p0|）
if（p1[i]（p0[i]）
返回false
end
else
if（p1[i]（（0（）
返回false
end
end
else
if（p1[i]（p2[i]）
返回false
end
end
end
返回true
以上算法只用了謂詞APlock代替謂詞“=”,，以及使用操作APm代替操作m。?祝上的謂詞“=”并沒有改成ComNET中的APlockall,，而是改成了isClosetLock,。用圖3來說明其中的原因。
假設(shè)組播的根對等點P0=（01,，10111,，1），則使用算法routeLastHopDHT計算Pn=（01,，1111,，2）的上一跳對等點的標(biāo)識符得到的結(jié)果是Pl=（cl，pl,，rl）=（01,，1111，1）,。從圖3中可以看到,，區(qū)域Pl一共由3個頂點組成，分別是P1=（c1,，p1,，r1）=（01，111100,，1）,，P2=（c2，p2,，r2）=（01,，11111，1）以及P3=（c3,，p3,，r3）=（01，111101,，1）,，因而必定有APlockall（p1,，pl，k）,、APlockall（p2,，pl，k）以及APlockall（p3,，pl,，k）。所以,，即使使用APlockall（p,，pl，k）代替圖53第四行中的p=pl,，也無法得到ComNET下正確的組播算法,，因為此時對等點P1，P2和P3都會在第二步同時發(fā)送組播消息給Pn,。
為了消除圖3中遇到的情況的方法是在多個組成這個區(qū)域的對等點中（如上述的P1,、P2和P3），唯一地選擇一個（如P2）作為代表來發(fā)送組播消息,，而這個代表的選擇標(biāo)準(zhǔn)則表示在2.2節(jié)的算法中,。當(dāng)一個對等點被該算法判定為相對于組播樹根對等點P0的組內(nèi)標(biāo)識符最親密地鎖定pl，則該對等點就被選為代表,。如對于圖3,，容易得到┐isClosetLock（P1，Pl）,，isClosetLock（P2,，Pl）以及┐isClosetLock（P3，Pl）,，因而P2被選為區(qū)域Pl的代表,，負(fù)責(zé)發(fā)送組播消息給Pn。
組播的提出實際上是為了克服基于泛洪的廣播算法的種種缺陷,，使一對多的消息傳遞變得高效而不含冗余,，以此來解決ComNET中的組播問題。
參考文獻(xiàn)
[1] 張聯(lián)峰,，劉乃安,，錢秀檳，等.綜述：對等網(wǎng)（P2P）技術(shù)[J].2003（12）：142-145.
[2] 石鋒,，吳建平.組播擁塞控制綜述[J].軟件學(xué)報,，2002，13（8）：253-260.
[3] ABERER K,， ALIMA L O,， GHODSI A,， et al. The essence of P2P： a reference architecture for overlay networks[C]. Fifth IEEE International Conference on Peer-to-Peer Computing， 2009：11-20.
[4] 宋建濤,，沙朝鋒,，楊智應(yīng)，等.語義對等網(wǎng)構(gòu)造及搜索機制研究[J].計算機研究與發(fā)展,，2010,，41（4）：645-652.
[5] FAST A， JENSEN D,， LEVINE B N. Creating social networks to improve peer-to-peer networking[R]. KDD′05 Proceedings of the eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data,， 2005：568-573.