摘 要： 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中進行組播消息的傳遞情況，模擬結(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，滿足：
?。╟n，pn，rn）（（cn，pn，rn）Tcn=c）
?。╟n，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)先的方式進行擴散。第一步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
（cl，pl，rl）：=（cn，pn，lastDiffPos）
end
else
if（pn[rn]=p0[rn]）/*上一跳是沿著Linkr的*/
if（lastDiffPos=-1）
?。╟l，pl，rl）：=（cn，pn，r0）
else
?。╟l，pl，rl）：=（cn，pn，lastDiffPos）
end
else/*上一跳是沿著Linkp的*/
（cl，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
?。╟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)前對等點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）
（cl，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.