P2P系統中一種負載均衡的超級節點選擇策略

朱永瓊

摘要 傳統的分層P2P網絡拓撲構造存在超級節點服務能力偏低的問題，特別是在對時延要求高的應用中，超級節點的服務能力偏低將不能滿足應用的需求。本文研究一種超級節點負載均衡的層次化網絡拓撲構造方法，該方法在選擇超級節點時不僅考慮節點的容量還將節點的剩余負載作為重要參考指標。在同等條件下，本方法可提高網絡呑吐量，減少網絡流量開銷，為P2P網絡的大規模應用提供了實用基礎。

【關鍵詞】P2P網絡 負載均衡 超級節點

1引言

P2P技術已經發展了16年，成為互聯網上最主要的應用。隨著P2P用戶激烈的增長，P2P網絡己經呈現海量化、分散化、動態化的特征。那么，在巨大的P2P網絡中如何進行高效的資源定位是P2P領域亟需解決的關鍵難題之一。2004年Liu在Infocom會議上指出，優化拓撲是提高P2P系統搜索效率的一種有效途徑。在P2P網絡結構中，層次化P2P網絡是最主流、研究最多并且應用最廣的一種網絡結構，最早由Yang，J在2003年提出[1]。后來在該思想體系下發展出了眾多具有典型特點的網絡模型。2007年，Gian等人提出了SG2[2]，一種延時受限的超級節點選擇算法，將節點間延時小于系統閾值的能力強的節點選出作為超級節點來保證數據的同步。2009年，Hung-Chang Hsiao在[3]中指出P2P網絡無論在網絡拓撲結構還是通訊機制方面都具有小世界SW模型特征，它依據特征路徑長度和聚類系數選擇超級節點，但是此方法不可避免地具有與結構化P2P系統類似的缺點。2010年，Jung-Shian Li使用完美差異圖模型對層次化P2P網絡進行優化[4]，2013年，Shreyas提出了一種自適應的超級節點選擇算法[5]，選擇超級節點依據節點的響應距離。國內也早己開展了此方面的研究。如2006年中科院計算所的夏啟志提出一種基于索引的P2P網絡模型IS2P2P[6]。2007年東北大學的張騫給出了基于領域的P2P信任模型的定義，然后在此基礎上提出了一種針對無結構化P2P網絡的自適應拓撲進化協議[7]。

傳統的分層拓撲構造存在篩選出的超級節點服務能力偏低的問題，特別是在對時延要求高的應用中，超級節點的服務能力偏低將不能滿足應用的需求。因此，本文擬研究一種超級節點負載均衡的層次化網絡拓撲構造方法，研究的內容包括：超級節點選擇模型、節點加入和退出方法等。該方法可使選出的超級節點在同等條件下，提供更短的搜索長度，更少的網絡流量開銷，為P2P網絡的大規模應用提供了實用基礎。

2拓撲構造

在層次化網絡拓撲構造過程中，超級節點和普通節點的劃分僅僅依賴系統提供的閾值，將系統中超過閾值的所有節點都設定為超級節點，普通節點隨機連到超級節點上。每當超級節點收到一個葉子節點的連接請求，只要不超過其最大連接數就立即連接，而沒有考慮到添加該葉子節點的連接就必須承擔該葉子節點的查詢工作量，增大了該超級節點的查詢負載。事實上，網絡中往往存在“熱區”，大量的查詢請求都被轉發到少數容量大的節點，導致節點間的負載極度不均衡，降低了網絡吞吐量。因此，建立超級節點負載均衡模型是層次化P2P網絡拓撲構造必須解決的關鍵問題。

2.1系統模型

給定一個P2P系統，初始狀態下節點根據現有的網絡協議如Internet相互連在一起，每一個節點能和其他節點通信，每一個節點都知道自己的IP地址和端口號。網絡是動態變化的，節點可以自由的加入和離開。

每一個節點都有個鄰居節點列表，記錄的是該節點所有的鄰居信息。節點鄰居是網絡節點的子集，鄰居列表的內容定義著整個網絡拓撲。鄰居列表的動態變化，網絡拓撲也不斷變化。

節點是異構的，它們的計算能力和容量各不相同，網絡連接的帶寬都不同，所以每個節點能連接的節點的個數都有限制。假定節點的容量為Ci，代表節點ni的處理能力，假定每一個節點都知道它自己的能力。網絡中任意兩個節點ni，nj之間的RTT延遲就是節點間的延時距離，以（ni，nj）表示。

2.2超級節點的選擇

在本文中，超級節點的選擇不僅關注節點的容量還要關注節點的負載均衡。不是選擇容量最大的節點作為超級節點，而是根據其剩余負載的能力和節點的容量，選出合適的節點作為超級節點，從而能提高網絡的吞吐量。

假定N中存放的是延時范圍內的所有節點，本文的目標是從N中選出一個容量大并且負載均衡的節點作為超級節點。假定系統定義的葉子節點和超級節點間的延時不能超過t，超級節點之間的延遲不能超過t+k。 是節點的平均容量值，Ri是節點的剩余容量。那么對于網絡中的任意節點ni，nj和節點之間的延時d（ni，nj），問題描述為：

（1）每一個節點不是超級節點就是葉子節點；

（2）對于每一個葉子節點ni和超級節點Sm，有d（ni，Sm）≦t；

（3）對于任兩個超級節點Sm和Sn，有d（Sm，Sn）≦t+k；

（4）對于任一個超級節點Sm，其容量超過 ，并保證其Ri是最小的。

節點的容量必須大于系統的平均容量值 才可能成為超級節點。而系統的平均容 是根據系統中節點容量的平均值的k倍。

假定有n個節點加入了網絡，那么

k是系統參數，k≧1。

節點的負載主要由三部分組成：

（1）節點的維護負載。每個節點需要周期性的通過ping/pong消息對連接進行維護，處理節點的加入離開，和緩存表的維護。

（2）節點的查詢負載。每個節點都能夠接收查詢消息并處理它們。

（3）節點的響應負載。一旦節點命中查詢，節點會發送響應消息沿原路返回。

表1給出超級節點的選取過程。

超級節點己經選出，需要對范圍內的其他所有節點建立連接。葉子節點與超級節點的連接過程如表2所示。endprint

在超級節點與葉子節點的連接過程中，需要對已經建立連接的節點做標記，即將選出的超級節點將標記為超級節點sp，其他的節點標記為葉子節點。不管是超級節點還是葉子節點，只要是打標的節點，以后的探測消息均不會在該節點進行轉發。由于節點的探測是廣播的方式，因此對已建立連接的節點做標記，會明顯的減少廣播過程中的消息傳遞，從而減少網絡開銷。

3結束語

P2P網絡的拓撲管理協議作為一個基礎協議，為上層豐富的P2P應用提供了服務節點選擇的支撐，是非常重要的一個研究方向。本文提出的超級節點選擇算法，充分的考慮了節點的負載均衡，與傳統方法相比，系統的服務能力明顯提升。

參考文獻

[1] Yang， J， An efficient interest-group based search mechanism in unstructured peer-to-peer networks， IEEE Computer Society，2003.

[2] Jesi， G.P.，"Proximity-aware superpeer over lay topologies"，Network and Service Management， IEEE Transactions on computer lecture p.74-83，2007.

[3] Hung-Chang， Hsiao，"Building Sma11-World Peer-to-Peer Networks Based on Hierarchical Structures"， IEEE Transact ions on Parallel and Distributed Systems， vol.20， pp.1023-1037，2009.

[4] Jung-Shian，Li，"An Efficient Superpeer Overlay Construction and Broadcasting Scheme Based on Perfect Difference Graph"，IEEE Transactions on Parallel and Distributed Systems，vol.21，pp.594-606，2010；

[5] Shah， Shreyas Shailesh，"Adaptive server selection in peer-to-peer networks"，San Diego State University，2013.

[6]夏啟志，謝高崗，閔應驊，李忠誠.IS2P2P：一種基于索引的結構化P2P網絡模型[J].計算機學報，2006.

[7]張騫，張霞，劉積仁.一種有效的Peer-to-Peer自適應拓撲進化協議[J].軟件學報，2007.endprint