朱永瓊

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

【關鍵詞】P2P網(wǎng)絡 負載均衡 超級節(jié)點

1引言

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

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

2拓撲構造

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

2.1系統(tǒng)模型

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

每一個節(jié)點都有個鄰居節(jié)點列表，記錄的是該節(jié)點所有的鄰居信息。節(jié)點鄰居是網(wǎng)絡節(jié)點的子集，鄰居列表的內(nèi)容定義著整個網(wǎng)絡拓撲。鄰居列表的動態(tài)變化，網(wǎng)絡拓撲也不斷變化。

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

2.2超級節(jié)點的選擇

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

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

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

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

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

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

節(jié)點的容量必須大于系統(tǒng)的平均容量值 才可能成為超級節(jié)點。而系統(tǒng)的平均容 是根據(jù)系統(tǒng)中節(jié)點容量的平均值的k倍。

假定有n個節(jié)點加入了網(wǎng)絡，那么

k是系統(tǒng)參數(shù)，k≧1。

節(jié)點的負載主要由三部分組成：

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

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

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

表1給出超級節(jié)點的選取過程。

超級節(jié)點己經(jīng)選出，需要對范圍內(nèi)的其他所有節(jié)點建立連接。葉子節(jié)點與超級節(jié)點的連接過程如表2所示。endprint

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

3結束語

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

參考文獻

[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網(wǎng)絡模型[J].計算機學報，2006.

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