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