一種具有負載平衡的虛擬計算環境拓撲

鄧曉衡，張連明，劉毅，趙扶搖, 陳志剛

(1. 中南大學 信息科學與工程學院，湖南 長沙，410083;2. 湖南師范大學 物理與信息科學學院，湖南 長沙，410081)

基于 Internet的虛擬計算環境(Internet based virtual computing environment, iVCE)[1]中的資源、用戶具有動態性，一方面，表現在資源、用戶加入虛擬計算環境具有動態性；另一方面，虛擬計算環境中在線的資源、用戶個體和系統整體網絡拓撲也處于一種動態的演化過程中，因此，虛擬計算環境的動態演化對于系統的性能有何影響、如何演化才能促進系統優化，成為互聯網環境領域越來越熱的研究問題。對Internet以及 Internet上的大型分布式應用系統的分析研究發現，其網絡的拓撲結構并不是隨機網絡，也不是規則網絡，而是介于其間的復雜網絡[2-4]，網絡拓撲結構對于系統的性能具有極其重要的意義。對互聯網網絡拓撲建模，形成了一些重要拓撲模型(如隨機圖拓撲模型[5])和基于層次結構的拓撲模型(如 Transit-Stub[6])以及基于節點度的互聯網拓撲模型(如 Inet[7]、動態模型BA[8])等。這些研究成果對于探索拓撲特性和拓撲結構等對網絡行為以及網絡性能的影響，最終改善網絡技術、提高網絡服務性能以及設計新型基于互聯網的應用系統拓撲等均具有重要意義。

1 Gnutella網絡拓撲分析

1.1 iVCE與Gnutella

在虛擬計算環境中，資源和用戶都被虛擬化成自主元素。自主元素會基于應用的需求，在互聯網上搜尋相應的虛擬計算環境，進而根據自己的興趣需求加入到某一個虛擬共同體中[1]。自主元素也可以作為一個超級自主元素來創建一個虛擬共同體，并發布自己的信息，允許別的用戶和資源加入到本虛擬共同體中，其組織結構如圖1所示。網絡拓撲分為2層：上層主要由超級自主元素組成，下層主要由一般自主元素組成。超級自主元素承擔更多的系統管理和通信消息轉發功能，普通自主元素則主要發起請求或提供相應的應用服務。

圖1 虛擬計算環境服務組織結構Fig.1 Service organizing structure of virtual computing environment

Gnutella是P2P計算的典型代表之一，在互聯網上擁有大量的用戶，具有廣泛的影響。最初的Gnutella協議由于采用扁平的拓撲結構和簡單的flooding的資源搜索機制而缺乏擴展性且性能較差；Gnutella2則采用二層覆蓋網體系結構，如圖2所示。

圖2中，少數超級節點(super peers)構成了覆蓋網的頂層，super peers相互連接通信，負責消息路由轉發；絕大部分是葉子節點(leaf peers)，它們構成底層覆蓋網。leaf peer 通過super peer連接到頂層，葉子節點將自己共享內容的哈希值上傳到與其連接的超級節點上，不負責查詢消息的轉發工作；若一個節點沒有找到合適的 super peer接入網絡，則將其設置變成super peer，其本質仍為一般節點，未實現超級節點功能，不與葉子節點相連，只能與網絡中的超級節點建立連接。Gnutella 2采用動態查詢的資源搜索方法，當查詢請求發出后有足夠的合適結果返回，當滿足用戶需求時，就中止查詢過程，在頂層網絡中只需很低的TTL(Time-To-Live)即可。由此可見：iVCE和Gnutella的網絡拓撲構造具有相似特征，對iVCE的拓撲建模，擬利用當前對Gnutella網絡拓撲測量的結果，利用其拓撲結構以其對應的擬合模型對iVCE拓撲結構建模。

圖2 Gnutella網絡的兩層結構Fig.2 Two-tier structure of Gnutella

1.2 Gnutella網絡拓撲分析

Gnutella作為P2P應用典型的代表，Jovanovic[9]對早期的Gnutella網絡拓撲進行測量，發現Gnutella網絡拓撲節點的分布呈現冪律和小世界特性。Stutzbach等[10]針對Gnutella網絡的分層特性，構造拓撲爬行器，分析了 Gnutella網絡中超級節點(super-peers)、葉子節點(leaf-peers)等度分布特性，指出Gnutella網絡節點度分布不服從冪律。劉剛等[11]構造支持Gnutella v0.4協議的拓撲爬行器，分析其拓撲快照，發現Gnutella網絡的小世界特性，驗證網絡中存在度指數冪律特征，王勇等[12]通過設計高效的網絡爬蟲測量Gnutella的拓撲數據分析發現其拓撲節點度分布呈現分3段冪率分布，拓撲具有小世界網絡特性。其拓撲特征總體表現為如下。

(1) 節點度呈多種特征分布。Gnutella網絡分為上層/底層2層節點，如圖2所示，2層中的節點實現的功能、采取的連邊策略各不相同，上層節點的度(Super to super peers)與其降序序列中的等級之間分三段符合冪律分布；網絡中超級節點對葉節點度數(Super to leaf peers)與其降序序列中的等級之間分2段符合冪律分布；葉節點連接的超級節點度(Leaf to super peers)與其降序序列中的等級之間分三段符合冪律分布。度的頻率分布(Degree-frequency distribution)特征刻畫Gnutella網絡拓撲度頻率分布特性。葉節點到上層節點(Leaf to super peers)連接的度概率分布具有較強的冪律特性；超級節點到葉節點(Super to leaf peers)連接的度概率密度呈“鐘型”分布；上層節點之間(Super to super peers)連接的度概率密度分布呈現“雙峰正態分布”特性。Super節點承擔Gnutella網絡消息路由功能，是整個網絡的骨架，節點度頻率分布得比較均勻，節點之間的地位比較“平等”，因受客戶端軟件鄰居維護策略的影響。

(2) 拓撲具有小世界特性。同時擁有大聚集系數(Clustering coefficient)和小的平均路徑長度(Average path length)2個統計特征的網絡，是具有小世界特性的網絡。通過Gnutella拓撲的上層節點之間的聚集系數Cactual和平均特征路徑長度Lactual，與各次快照拓撲圖對應的隨機圖的聚集系數Crandom和特征路徑長度的均值Lrandom進行比較，可以證明Gnutella網絡的小世界特性。 Stutzbach等測量了 Gnutella網絡數據和 3類典型的具有小世界特性的網絡拓撲數據進行比較[15]，結果如表 1所示。Gnutella網絡拓撲圖滿足Cactual＞＞Crandom，且 Lactual≈ Lrandom，即實際網絡具有小世界特性。Gnutella網絡的聚集系數比文獻[14]中的測量結果有所增長，表明Gnutella網絡在不斷成長時，變得越來越緊密，不利于Gnutella網絡中使用洪泛消息路由機制， Gnutella網絡比對應的隨機網絡更容易產生冗余消息。

表1 小世界網絡特性Table 1 Property of small-world network

2 虛擬計算環境拓撲建模與構造

iVCE的網絡拓撲與當前互聯網系統的拓撲具有一定相似之處，但從iVCE的自主元素加入與退出的機制來看，其網絡拓撲不可能完全等同于現有復雜網絡模型。

2.1 iVCE網絡拓撲構造的思想

iVCE從產生到生長到一定的穩定的規模，從而維持一種動態的狀態，其網絡規模經歷了一種迅速擴大，然后進入一種緩慢增加，最后進入一種動態平衡狀態的過程。在這個過程中，有些自主元素分化為超級自主元素，同時在超級自主元素的組織管理下形成一些虛擬共同體，即形成社區效應；另外，在自主元素不斷加入iVCE時，建立許多新的自主元素間的連接，也有許多自主元素在退出iVCE，或者沒有退出iVCE，其連接自主元素在改變。因此，iVCE的網絡模型不僅需要能夠同時再現小世界效應和無標度特性，而且在具體演化過程中實際的統計性質要符合實際。目前，大部分網絡增長模型每一時間步都是加入一個新的節點，網絡規模隨時間呈線性增長。然而，在現實世界中，網絡規模一般隨時間的變化是非線性的。在iVCE中，在1個單位時間間隔內，可能有多個新節點同時加入系統，而且隨著系統規模的增大，同時加入的新節點數也隨之增多，整個系統的規模呈幾何級數增長。在網絡規模增長的過程中，部分節點會退出網絡，最后加入與退出節點達到一種平衡。在此，針對網絡演化的實際情況，提出一種包括網絡產生、成長、成熟三階段的網絡模型。

2.2 iVCE網絡拓撲構造過程

iVCE網絡拓撲模型依然采用圖G= (V , E ) 來表示。其中：圖G是一個無向簡單連通圖，有N個節點，M條邊；V={v1, v2, …, vN}代表節點集合；E={e1, e2, …,eM}?V×V，代表邊的集合。令 di表示節點 vi的連接度，顯然1≤di≤N-1。同時，稱D={d , d2, …, dN}為圖G的度序列。Dmax-i為節點vi的最大連接度數，由iVCE中自主元素的貢獻資源數量和處理能力決定；INTi為vi的興趣值，區分自主元素的應用類型，從而決定vi的分組、聚集情況。

iVCE網絡拓撲生成過程如下。

(1) 網絡產生。網絡從第1個自主元素開始成長，在網絡成長開始階段，為保持網絡的健壯性，當網絡規模在閾值Ninit以下時，比如Ninit=20，稱其為原始網絡，網絡中的自主元素不管是超級自主元素還是普通自主元素，相互之間采用全連接，但節點vi的度di不能超過 Dmax-i的限制。為了網絡實現過程的更好可行性及健壯性，生成核心網絡時，節點的 Dmax-i可設置為相同。此階段每次只新增加1個自主元素，網絡規模呈線性增長。

(2) 網絡加速成長。當網絡規模大于 Ninit時，網絡成長速度加快，每次加入網絡多個自主元素，同時網絡還有一定的自主元素開始退出網絡，加入自主元素數量由當前網絡的規模決定。有研究表明，網絡成長呈幾何級數規模增加，因此，模型中每次增加自主元素數為α×N，退出自主元素數為β×N。其中：β=α×N/Nmax；Nmax為網絡預設的最大規模；N為網絡當前的規模，當網絡規模達到Nmax時，有β=α；α和β分別為加入因子和退出因子，其取值為0～1。

(3) 成熟網絡維護。網絡規模達到 Nmax后，網絡進入一個動態、穩定運行狀態，此時，加入網絡的自主元素和退出網絡的自主元素基本維持平衡。網絡規模不是絕對不變的，而是約束在Nmax附近變化，因此，需要在加入、退出的自主元素數中引入隨機的擾動量，范圍在1～maxN 之間。每次產生2個隨機數NRan1和NRan2，假定NRan2＞NRan2，若N＞Nmax，則加入自主元素數為Nα×+NRan2，退出自主元素數為Nβ×+NRan1，反之亦然。

① 自主元素的加入。前面已提及一次加入自主元素的數目，在自主元素生成過程中，以比較小的概率Psuper如5%生成自主元素，使其Dmax-i≥50，該類自主元素作為超級自主元素，以較大的概率(1-Psuper)來生成普通自主元素，使其Dmax-i＜50，為普通的葉子自主元素。對于所生成自主元素的最大連接度 Dmax的分布，采用正態分布比較符合實際；且網絡的閾值設為動態可調，以網絡的某個整體狀態參數作為反饋，來調高或調低閾值。生成自主元素后，則考慮自主元素連接入網，Dmax決定最大連接鄰居的數量，NINTi決定了與哪些自主元素相連。

i) 加入葉子自主元素，只選擇與NINTi相同的超級自主元素相連，如有多個NINTi，則選擇多個超級自主元素連接。因此，提出基于負載壓力的連接節點選擇策略，選擇連接的對象時，主要考慮負載壓力，即自主元素當前連接度/自主元素最大連接度的比值Di/Dmax-i，連接時，優先選擇Di/Dmax-i小的自主元素連接。因為其具有較小的負載，故具有承擔新的任務、連接的能力。

ii) 超級自主元素加入，即加入Dmax-i≥50的自主元素。首先，將其當做葉子自主元素加入網絡，可以保證興趣一致的自主元素組成一個虛擬共同體；然后，再增加一定數量的邊比如Dmax×10%連接到其他超級自主元素上。至于連接對象的選擇，同樣優先連接超級自主元素中負載壓力較小的自主元素。

② 自主元素的退出。

i) 普通葉子自主元素退出。將該自主元素從拓撲圖中刪除，同時刪除所有與該自主元素連接的邊，并修改連接自主元素的度di。

ii) 超級自主元素退出。將該自主元素從拓撲圖G中刪除，同時刪除所有與該自主元素連接的邊，并修改連接自主元素的度di。若與之相連接的葉子自主元素的度為 0，則需要將該自主元素作為一個新的葉子自主元素加入到當前網絡中。

該拓撲生成器是iVCE仿真模擬平臺的一部分，用 C++語言在linux環境下實現，對數據結構多次優化，具有很好的計算性能和較高存儲效率，在 Intel 2.0GHz CPU的主機上，8 min可以生成具有十萬數量級規模的拓撲，還可以根據需要展示拓撲生成過程。

3 虛擬計算環境拓撲特性分析

為了分析生成的iVCE網絡拓撲的性質，根據上面的方法對網絡規模、網絡增長因子、自主元素興趣數以及超級節點的比例等多個參數分別進行調整，在同一組參數條件下重復10次生成網絡，對網絡的度分布情況、簇系數以及平均最短路徑長度分別統計求平均值。

根據需要拓撲生成過程中引入了幾個參數。為考察同時加入 iVCE節點的數量，引入增長率α(0＜α＜1)，表示同時加入節點數占當前節點數的比例；超級節點和普通節點連接其他節點的數量不同，引入區別參數超級節點度閾值Dthresh；iVCE中的節點可以基于共同的興趣而形成相互交互的自治組，因此，引入興趣數nint。

3.1 iVCE網絡拓撲的度分布

在不同網絡規模下研究增長率α對所生成網絡的度分布的影響。增長率α選取0.01，0.10和0.20，網絡規模選取10 000和40 000；興趣數量為5；以超級節點的最少度數為閾值Dthresh=50，超級節點所占比例為5%。重復進行10次仿真實驗，所得到的度分布的平均值如圖3所示。從圖3可見：增長率α在相當寬的取值范圍內(0＜α＜1)，網絡的度分布都呈正態分布規律，其峰值約為0.065，出現在節點數為28處。在3(a)中除了最高峰外，在閾值50處還有1個比較明顯峰值較低的峰。這主要是因為在拓撲生成的第1個階段，構造了一個節點度數相同的全連接核心網絡。

選取增加因子α=0.1，將興趣數由原來的5變化為10，閾值由50改為60，在不同網絡規模下多次實驗，結果如圖4所示。從圖4可見：不同網絡規模下的次級峰明顯，網絡規模越大，次級峰高度越低。

圖3 不同增加因子α下節點度分布Fig.3 Node degree distribution with various increasing factors

從圖4可見：多條曲線基本重合，表明網絡規模、網絡中節點興趣數對其影響較少，網絡規模較少時抖動較嚴重。進一步，將興趣數保持為5，增長因子為0.1，將節點超級節點的比例由5%改為10%，在不同網絡規模下多次實驗，得到網絡度分布如圖4(c)所示。從圖 4(c)可見：節點度分布更加集中，分布中心變為18，峰值達到0.09。由上述實驗發現節點度分布主要與超級節點所占比例相關，該比例越低，則度分布正態分布范圍更廣。

3.2 iVCE網絡拓撲的簇系數

不同參數下網絡簇系數分布見圖5。從圖5可見：在α＜1時，簇系數隨增長因子的變化不大；當網絡的規模從10 000逐步增加到100 000時，簇系數隨網絡規模增大而減少，變化規律與無標度網絡模型一致；當將超級節點的比例由 5%增加為 10%，超級節點的連接度的閾值由50變為60時，超級節點連接度閾值對于簇系數的改變不大；但是，當超級節點比例變為10%時，簇系數明顯增加；在網絡規模為100 000時，增加比例達50%。

圖4 不同興趣數、閾值和超級節點比例下節點度分布Fig.4 Node degree distribution with various interests and thresholds

3.3 iVCE網絡拓撲的平均最短距離

圖5 不同參數下網絡簇系數分布Fig.5 Cluster coefficient distribution with various parameters

平均最短距離是復雜網絡的一個重要統計特性，小的平均最短距離意味著網絡具有小世界特性。對不同增長率下生成網絡的平均最短距離進行計算，結果如圖6所示。從圖6可看出：隨著網絡規模從10 000遞增到100 000，網絡平均最短路徑長度L從5.3增加到6.8。

圖6 不同參數條件下網絡平均最短路徑長度Fig.6 Average shortest path length with various parameters

同時發現：網絡增長因子對L影響不大，增長因子大的網絡，其L也略大。將超級節點的比例由5%增加為 10%，相應地將超級節點連接度的閾值由 50變為60，發現當超級節點比例增加為10%時，平均最短路徑長度增加 0.2；當超級節點連接度閾值增加為60時，平均最短路徑長度在網絡規模比較小時基本保持不變，但當網絡規模不斷增大時，長度明顯降低；當節點數達到 100 000時，平均最短路徑長度由 7.1減少為6.5。

從網絡的生成過程和網絡屬性的統計分析情況來看，網絡的度分布、簇系數、平均最短距離比較穩定，參數值的改變對其分布影響較少。影響網絡屬性變化的重要因素是網絡節點動態加入和退出過程的連接方案以及拓撲維護的策略，iVCE網絡采用基于負載壓力的連接節點選取，使得網絡節點度分布呈現正態分布，因此，能夠較好地實現負載的均衡分配，同時，網絡的穩定性和可靠性均比較好，一批處理能力強的超級節點具有較高的連接度，從而保證了網絡整體的生存性比較好。從網絡的效率方面來看，網絡具有冪率分布基本一致的平均最短路徑長度，具有小世界網絡的特征，從而保證消息傳輸的開銷較少。

4 結論

(1) 在對Gnutella為代表的P2P系統的拓撲進行分析的基礎上，基于復雜網絡模型，提出了一種包括產生、成長和成熟運行三階段同時多節點快速增長的網絡拓撲生成方法。

(2) 該方法通過控制網絡增長因子、超級節點比例、興趣數以及超級節點閾值，生成具有一定值的節點度分布頻率、聚集系數、平均節點間最短路徑長度屬性指標的網絡拓撲。分析形成的網絡拓撲發現生成的iVCE拓撲具有很強的穩定性。

(3) 采用基于負載壓力的節點連接選擇策略使得整個網絡具有良好的負載均衡的效果，能基于超級節點能力分配合適的連接節點，而不會出現超大連接度節點，提高了系統的可靠性。

[1] 盧錫城, 王懷民, 王戟. 虛擬計算環境 iVCE: 概念與體系結構[J]. 中國科學 E輯: 信息科學, 2006, 36(10): 1081-1099.LU Xi-cheng, WANG Huai-min, WANG Ji. Internet-based virtual computing environment[J]. Science in China Ser E.Information Sciences , 2006 , 36 (10): 1081-1099

[2] Faloutsos C, Faloutsos M, Faloutsos P. On power-law relationships of the Internet topology[C]//Proc of the ACM SIGCOMM. New York, 1999: 251-262.

[3] Albert R, Jeong H, Barabasi A L. Error and attack tolerance in complex networks[J]. Nature, 2000, 406: 387-482.

[4] Newman M. Properties of highly clustered networks[J]. Physical Review E, 2003, 68: 026121.

[5] Erd?s P, Rényi A. On the evolution of Random graphs[M].Hungary: Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 1959: 290-297.

[6] Calvert K L, Doar M. Modeling Internet topology[J]. IEEE Communications Magazine, 1997, 35(6): 160-163.

[7] Winick J, Jamin S. Inet-3.0: Internet topology generator[R].Technical Report, CSE-TR-456-02, Department of EECS.University of Michigan, Michigan, USA, 2002.

[8] Albert R, Barabari A L. Topology of evolving networks: local events and university[J]. Physical Review Letters, 2000, 85(24):5234-5237.

[9] Jovanovic M A. Modeling large-scale peer-to-peer networks and a case study of Gnutella[D]. Ohio: University of Cincinnati,2001: 102-113.

[10] Stutzbach D, Rejaie R, Sen S. Characterizing unstructured overlay topologies in modern P2P file-sharing systems[J].IEEE-ACM Transactions on Networking, 2008, 16(2): 267-280.

[11] 劉剛. 對等網絡的測量、模型化與分析[D]. 哈爾濱: 哈爾濱工業大學計算機學院, 2005: 80-89.LIU Gang. Measurements, modeling and analysis of peer-to-peer networks[D]. Harbin: Harbin Institute of Technology. School of Computer, 2005: 80-89.

[12] 王勇, 云曉春, 李奕飛. 對等網絡拓撲測量與特征分析[J]. 軟件學報, 2008, 19(4): 981-992.WANG Yong, YUN Xiao-chun, LI Yi-fei. Measuring and characterizing topologies of P2P networks[J]. Journal of Software, 2008, 19(4): 981-992.

[13] Nowak M A. Five rules for the evolution of cooperation[J].Science, 2006, 314: 1560-1563.

[14] Pouwelse J P, Garbacki P, et al. The Bittorrent P2P file-sharing system: Measurements and analysis[C]//Castro M, van Renesse R, ed. Peer-to-Peer Systems IV, IPTPS 2005. Ithaca:Springer-Verlag, 2005: 205-216.

[15] Watts D J. Networks, dynamics and the small world phenomenon[J]. American Journal of Sociology, 1999, 105(2):493-527.

[16] Albert R, Barabási A. A statistical mechanics of complex networks[J]. Reviews of Modern Physics, 2002, 74(1): 47-97.