摘  要： P2P網絡廣播使用廣度優先的泛洪方式，導致對等點的處理負荷過大，網絡流量激增，容易造成網絡阻塞。在分析ComNET及組播的基礎上，提出設計一個分布式算法，使一對多的消息傳遞變得高效而不含冗余，以此來解決ComNET中的組播問題。

　　關鍵詞： P2P；組播；ComNET；分布式算法

　　P2P[1]網絡廣播使用廣度優先的泛洪方式，根據對等點網絡拓撲的不同，可能有大部分節點會被廣播消息重復到達。重復到達的消息不僅增加了對等點的處理負荷，而且大大地增加了網絡流量，容易造成網絡阻塞。

　　通過實驗可以簡單地模擬廣度優先的泛洪算法[2]在ComNET中進行組播消息的傳遞情況，模擬結果如圖1所示。

　　數據統計過程如下。首先使用簡單的廣度優先算法在指定的組內傳播消息，當一個對等點收到一個組播消息后，記住它曾經收到此消息，然后直接把消息發送到它所有鄰居。重復訪問次數是統計所有對等點收到的重復消息的總數（一個對等點可能收到多個重復消息，統計時算實際重復的次數，而不是一次），圖1（a）所示為重復的次數隨著網絡規模的增大的情況，而圖1（b）則給出了重復消息個數占發送消息總數的比例。從圖1中可以看到，無論在比率還是絕對數量上，重復消息的量都是很驚人的。比如當對等點數目為2 M時，有131 917個消息是無用、重復接收的，占發送出去的消息總數140 119的94.14%。這些重復的消息嚴重禍害著互聯網絡。

　　本文主要研究討論如何在ComNET指定的對等點組中廣播消息。方法是首先研究簡單的情況，即Cayley圖Γ上的組播情況。然后再推廣到動態網絡ComNET上。

　　1 ComNET及組播分析

　　現實中一般很少需要在整個網絡中轉發消息，因而暫不考慮在整個ComNET上廣播消息的情況，而把問題集中在如何在某個指定的對等點組中廣播消息，稱之為組播。問題的更形式化的定義[3]如下。

　　1.1 Γ中的組播

　　給定Cayley圖Γ以及起始頂點P0=（c，p，r），給出以P0為根的一顆轉發樹T，滿足：

　　（cn，pn，rn）（（cn，pn，rn）Tcn=c）

　　（cn，pn，rn）（（（cn，pn，rn）cn=c）（cn，pn，rn）T）

　　1.2 ComNET中的組播：

　　給定一個動態覆蓋網絡ComNET以及起始對等點P0=（c，p，r），給出以P0為根的一顆轉發樹T，且滿足：

　　（cn，pn，rn）（（cn，pn，rn）TAPlockall（c，cn，k））

　　（cn，pn，rn）（（（cn，pn，rn）APlockall（c，cn，k））（cn，pn，rn）T）

　　1.3 Γ中的組播的缺點

　　圖Γ的一級聚集系數該值較大。較大的聚集系數在直觀上來看是指“一個頂點的鄰居很可能也相互是鄰居”，雖然增大CC1不僅可以增加“瀏覽功能”的可用性以及增強魯棒性，但較大的CC1對組播是一場噩夢。可以通過圖2來說明情況。

　　假設組播的起始頂點是P0，并且組播使用廣度優先的方式進行擴散。第一步P0會把消息擴散到它的所有4個鄰居中，其中包括P1、P2、P3；接著在第二步，由于P3同時又是P1和P2的鄰居，所以P3（邏輯上）同時收到它們發出的組播消息。同理P1會同時收到P2和P3的組播消息；P2會收到P1和P3的組播消息。因此僅在兩個時間步內，P1，P2和P3就總共收到了3個相同的消息，而且這些都只是所有消息副本中的很少的一部分，隨著擴散規模的擴大，被重復到達的頂點以及重復到達的次數將會大大增加，因而在Γ中使用簡單的廣度優先策略來實現組播并不是一種明智的選擇。

　　2 ComNET組播樹實現

　　2.1 算法思路

　　在Γ上組播消息的關鍵是生成組播樹，也就是說轉發關系圖不能含有環，因此只要找出一個分布式算法來確定一條從組播樹根P0到其他組播樹頂點P的唯一路徑就能解決組播問題。事實上，可以把要求再降低一點，只需找出一個算法routeLastHop[4]用于計算從P0到P的路徑中頂點P的上一跳，然后執行以下算法框架groupCast[5]即可。

　　輸入：當前頂點P的標識符（c，p，r）以及組播樹根標識符（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））

　　把組播消息轉發到（cn，pn，rn）

　　end

　　end

　　end

　　輸入：頂點Pn的標識符（cn，pn，rn）以及組播樹根標識符（c0，p0，r0）。

　　輸出：唯一地確定從（c0，p0，r0）到（cn，pn，rn）的路由路徑中，（cn，pn，rn）的上一跳頂點的標識符（cl，pl，rl）。

　　lastDiffPos為p0與pn的除第r0位的最后一個（從左到右）不同位的下標，如果找不到則為-1。

　　if（r0=rn）

　　if（lastDiffPos=-1）

　　（cl，pl，rl）：=（c0，p0，r0）

　　else

　　（cl，pl，rl）：=（cn，pn，lastDiffPos）

　　end

　　else

　　if（pn[rn]=p0[rn]）/*上一跳是沿著Linkr的*/

　　if（lastDiffPos=-1）

　　（cl，pl，rl）：=（cn，pn，r0）

　　else

　　（cl，pl，rl）：=（cn，pn，lastDiffPos）

　　end

　　else/*上一跳是沿著Linkp的*/

　　（cl，pl，rl）：=（cn，m（pn，p0，rn），rn）

　　end

　　end

　　問題的復雜度集中在算法routeLastHop。Γ上路由的算法如下所示，而算法routeLastHop實際上是該路由算法的逆過程。

　　輸入：當前頂點的標識符（c1，p1，r1）以及目標頂點的標識符（c3，p3，r3）。

　　輸出：下一跳頂點的標識符（c2，p2，r2）。

　　if（c1=c3（p1=p3（r1=r3）then

　　目標頂點已經到達

　　else

　　if（c1=c3（p1=p3）then

　　（c2，p2，r2）：=（c3，p3，r3）/*第二階段*/

　　else/*下面屬于第一階段*/

　　if（lock（c1，c3，r1）（lock（p1，p3，r1））then

　　/*跳離當前地區，使得可以修正標識符的其他維*/

　　r2是不滿足lock（c1，c3，r2）或不滿足lock（p1，p3，r2）的整數，且優先選擇非r3的整數。

　　c2：=c1

　　p2：=p1

　　else

　　if（┐lock（p1，p3，r1））then/*修正組內標識符的當前維*/

　　p2：=m（p1，p3，r1）

　　c2：=c1

　　r2：=r1

　　else/*修正組標識符的當前維*/

　　c2：=m（c1，c3，r1）

　　p2：=p1

　　r2：=r1

　　end

　　end

　　end

　　end

　　輸入：當前對等點P的標識符（c，p，r）以及組播樹根標識符（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））

　　把組播消息轉發到（cn，pn，rn）

　　end

　　end

　　end

　　輸入：對等點Pn的標識符（cn，pn，rn）以及組播樹根標識符（c0，p0，r0）。

　　輸出：唯一地確定從（c0，p0，r0）到（cn，pn，rn）的路由路徑中，（cn，pn，rn）的上一跳對等點的標識符（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）

　　（cl，pl，rl）：=（cn，pn，r0）

　　else

　　（cl，pl，rl）：=（cn，pn，lastDiffPos）

　　end

　　else/*上一跳是沿著Linkp的*/

　　（cl，pl，rl）：=（cn，APm（pn，p0，rn，k），rn）

　　end

　　end

　　2.2 ComNET中的組播算法

　　在第2節中本文給出了Γ中的組播算法，事實上只需要在適當的地方使用謂詞“APlock”代替謂詞“=”就可以得到在ComNET中組播的算法雛形。但是，另一方面，ComNET的動態性導致對等點與Γ上的頂點并不是一一對應的，這又需要對ComNET中的具體組播算法作出相應的修改。

　　先給出組播算法，然后再分析ComNET和Γ上的這些算法有何不同。

　　輸入：兩個對等點標識符P1=（c1，p1，r1）、P2=（c2，p2，r2）以及組播樹根對等點標識符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來說明其中的原因。

　　假設組播的根對等點P0=（01，10111，1），則使用算法routeLastHopDHT計算Pn=（01，1111，2）的上一跳對等點的標識符得到的結果是Pl=（cl，pl，rl）=（01，1111，1）。從圖3中可以看到，區域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都會在第二步同時發送組播消息給Pn。

　　為了消除圖3中遇到的情況的方法是在多個組成這個區域的對等點中（如上述的P1、P2和P3），唯一地選擇一個（如P2）作為代表來發送組播消息，而這個代表的選擇標準則表示在2.2節的算法中。當一個對等點被該算法判定為相對于組播樹根對等點P0的組內標識符最親密地鎖定pl，則該對等點就被選為代表。如對于圖3，容易得到┐isClosetLock（P1，Pl），isClosetLock（P2，Pl）以及┐isClosetLock（P3，Pl），因而P2被選為區域Pl的代表，負責發送組播消息給Pn。

　　組播的提出實際上是為了克服基于泛洪的廣播算法的種種缺陷，使一對多的消息傳遞變得高效而不含冗余，以此來解決ComNET中的組播問題。

　　參考文獻

　　[1] 張聯峰，劉乃安，錢秀檳，等.綜述：對等網（P2P）技術[J].2003（12）：142-145.

　　[2] 石鋒，吳建平.組播擁塞控制綜述[J].軟件學報，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] 宋建濤，沙朝鋒，楊智應，等.語義對等網構造及搜索機制研究[J].計算機研究與發展，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.