本站小編為你精心準備了互聯網拓撲結構中的彈性網絡特征參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《東北大學學報》2016年第四期

摘要:

選取CAIDA機構數量級為107的互聯網拓撲數據，對IPv4，IPv6與AS級互聯網網絡規模、標準網絡結構熵、網絡平均路徑長度和網絡度分布冪指數進行了分析．結果表明，互聯網具有可擴展性與魯棒性;互聯網拓撲結構具有彈性網絡特征，且隨互聯網的拓撲演化，彈性網絡特征愈發明顯．互聯網彈性網絡特征的發現，使借鑒生物學思想指導互聯網宏觀拓撲研究成為可能．

關鍵詞:

互聯網拓撲;互聯網彈性網絡特征;可擴散性;魯棒性;生命特征

互聯網誕生至今，其網絡宏觀拓撲結構時刻都在發生著變化，隨著需求的提高，其演化速度變得更快，網絡結構的復雜性也變得更明顯［1－2］．這意味著，互聯網的復雜拓撲結構不再是一個工業化的機械結構，人們不得不放棄對互聯網的絕對控制．有物理學家曾預言，“凡有生命，有進化的地方都會出現不同程度的無標度之冪律現象”，互聯網逐步向互操作的方向發展，并最終會進化出生命特征，其進化過程甚至會在“自我監督”下完成［3］．國內外學者嘗試從互聯網宏觀拓撲中尋找特征規律，以期從中提取生命特征［4］，進而證明互聯網絡的生命屬性，但業界尚未認同這些猜測［2］．在該研究背景下，本文定義了彈性網絡及其特征，以互聯網常規特征量(網絡規模、標準網絡結構熵、網絡平均路徑長度和網絡度分布冪指數)描述彈性網絡特征的可擴展性與魯棒性，以期從互聯網宏觀拓撲中發現彈性網絡特征．并以此為基礎，探索、觀察互聯網的生命跡象，通過直接建立在碳世界(以碳為基本元素的生物界)與硅世界(以硅為基本元素的計算機互聯網領域)間微妙而明確的關系，為從互聯網宏觀拓撲中提取生命特征提供理論依據，使借鑒生物學思想指導互聯網宏觀拓撲研究成為可能．

1實驗基礎:數據來源與相關定義

本文所涉及數據取自CAIDA(thecooperativeassociationforinternetdataanalysis)Ark探測項目，抽樣2009～2013年共60個月IPv4，IPv6與AS級互聯網全網宏觀拓撲數據，數據量級大于107，以月為探測單元，分別探究3種互聯網絡的彈性特征．根據Barabasi的研究證實了測量較少目的源點(抽樣數據)便足以獲取互聯網全網拓撲本質特性［5］．分析之前，給出如下定義．定義1彈性網絡:本文將彈性網絡描述為一種兼具擴展性和魯棒性的網絡，網絡拓撲既可在不受外界控制的情況下進行擴展、發生變化，也可容納因外界干擾引起的變化，甚至對外界的攻擊表現出自愈性和恢復性．其中，可擴展性指在常態下，網絡規模等基本網絡拓撲特征不受外界控制不斷發展壯大的能力．魯棒性指對于微小擾動，網絡仍保持其拓撲結構或性能完好無損不變或幾乎不變的能力［6］．定義2網絡規模包括網絡中的節點數N和連邊數E，是互聯網最基本的拓撲特征．隨時間增長，網絡中節點與邊的演化情況簡潔直觀地體現了網絡不斷擴大、發展的趨勢．定義3網絡結構熵［7］:從宏觀角度描述了復雜網絡的拓撲結構狀態穩定程度，結構狀態越不穩定，可擴展性越大，熵越大，反之越小;從微觀層面，它是系統微觀狀態發生改變的可能性大小，亦是系統組成單元混亂程度的度量，系統愈是存在變化的動力，系統內部愈混亂，熵愈大，反之愈小［8－9］．定理1當網絡拓撲結構呈完全均勻狀態時，網絡被認為是最混亂、均勻且無序的．該極端情況下的網絡拓撲，由于自身的不穩定性而具有最強的演化潛力，即最強的可擴展性，此時網絡結構熵最大，即Hmax=lnN．定理2當網絡為星形結構時，結構最不均勻，是一種極端“專制”的集權式網絡，此時網絡秩序性最優，網絡由于極強的秩序性使得網絡拓撲極其穩定，因此，星形網絡在不受外界干擾的情況下，不具演化潛力或可擴展性．

2互聯網拓撲可擴展性演化分析

由定義1可知，彈性網絡特征的可擴展性為網絡在不受外界控制情況下，網絡拓撲不斷發展、演化的能力，整個過程由網絡拓撲自組織完成．網絡拓撲演化由網絡內部微觀擾動引起［10，12］，并借由外部拓撲表現為基本屬性的變化，如網絡規模(節點與邊)演化及標準網絡結構熵的動態演化情況．故借由上述二者的演化規律，對IPv4，IPv6與AS級網絡的彈性網絡特征的可擴展性進行了分析．

2.1網絡規模演化以2009～2013年(以月為探測時間單元)探測數據為基礎，根據定義2，對IPv4，IPv6與AS級網絡規模(節點數N與連邊數E)時序演化進行觀察與分析．圖1為N與E的時序演化，即隨時間的增加網絡中節點與邊的變化情況．由圖1a和1b可知，IP級網絡中節點與邊的增長情況存在明顯伴隨關系．在圖1a中IPv4網絡節點與邊的數量級已突破105，伴隨著IPv4地址分配殆盡，可供擴展的空間逐漸萎縮，整個探測期間IPv4網絡規模在小漲落中呈緩慢增長趨勢．在圖1b中IPv6節點與邊的數量級僅為104，但IPv6節點與邊數增長趨勢極明顯，在5年的探測范圍內，節點數從5545增長至58510，連邊數從5765增長至65678，漲幅均在10倍以上．在圖1c中AS級網絡節點與邊增長趨勢并未像IP級呈現一致性，其節點數量級為104，在探測期間其節點數增長平緩，連邊數量級從104升至105．可見，3種網絡規模在不斷擴大，網絡拓撲擴展演化趨勢明顯．

2.2互聯網宏觀拓撲標準網絡結構熵演化由定義3可知，網絡結構熵描述網絡拓撲的不穩定(不確定)性，即拓撲變化的內在動力，是網絡拓撲的擴展潛力．對IPv4，IPv6與AS級互聯網2009～2013年內所有探測時間單元(共60個月)標準網絡結構熵進行計算，結果如圖2所示．由圖2可知，IPv4，IPv6與AS級互聯網標準網絡結構熵均在時序上不斷增大，只是增大程度不同．網絡結構熵作為一個描述系統狀態的函數，其變化可直接反映系統狀態的演化方向．將此3種網絡結構熵演化情況進行對比，不同協議及不同探測尺度下的互聯網的標準網絡結構熵存在差異，比較結果為AS級＞IPv4＞IPv6．說明互聯網IP級宏觀拓撲較AS級拓撲更具確定性，AS級網絡拓撲具有更強的演化擴展潛力．比較IP級網絡結構熵發現，IPv4網絡拓撲較IPv6具有更強的拓撲可變性．可見，從上層宏觀角度觀察到的互聯網拓撲雖不及微觀尺度的IP級互聯網表現得穩定，卻具有相對較強的可擴展性．根據定理1，標準網絡結構熵最大值為1，即便是標準網絡結構熵值最大的AS級網絡，其量級也僅為10－1，遠非均勻網絡，因此，無論從宏觀還是微觀來看，互聯網仍是宏觀有序的拓撲結構，所觀察到的熵值增大的趨勢只是網絡拓撲演化自組織過程中的一個微觀特征表象．IPv6平穩未見明顯漲勢的熵值也可看作此過程中一次相變之后暫時的穩態，可以說，互聯網拓撲結構的擴展是在一次次的自組織過程中完成的．

3互聯網拓撲魯棒性演化分析

根據定義1，網絡拓撲魯棒性指對于外界的微小擾動，網絡仍保持其拓撲(或者功能)完好無損(維持不變或幾乎不變)的能力，對于外界的攻擊具有自愈能力和自適應性［13］．前人多以網絡連通性來衡量網絡魯棒性，如Albert等［14］便以平均路徑長度、網絡聚集系數和度分布冪指數衡量網絡拓撲魯棒性．本節以此為理論根據，從網絡結構性出發，通過觀察描述上述特征量的動態演化，對IPv4，IPv6與AS級網絡的彈性網絡特征魯棒性進行分析．

3.1互聯網平均路徑長度演化Albert等分別在其研究中指出，平均路徑長度是衡量網絡魯棒性的重要拓撲特征量，網絡平均路徑長度越短，網絡數據傳輸效率越高，網絡中個別節點失效等微小擾動對網絡通信造成致命打擊的可能性越小，即網絡魯棒性越好．根據式(3)對實驗數據進行統計計算，3種拓撲形態下互聯網數據傳輸效率演化如圖3所示．在圖3a中IPv4網絡的平均路徑長度始終保持在15.5上下，整體演化趨勢較為平穩，但存在明顯波動，2013年后期呈現小幅下降趨勢，至15左右;在圖3b中IPv6網絡平均路徑長度整體呈上升趨勢，探測前期基本保持在11～12之間，在探測的后半段時間IPv6網絡平均路徑長度出現較大波動，在2013年的后5個月，網絡平均路徑長度升至15，并在這個水平上保持平穩態勢;在圖3c中AS級網絡平均路徑長度演變相對平緩，通過放大其漲落，發現AS級網絡平均路徑長度上升趨勢緩慢，在整個探測期未見明顯波動．3種網絡平均路徑長度比較結果為IPv4＞IPv6＞AS級，AS級網絡在宏觀拓撲上表現出較IP級網絡更強的魯棒性．AS級網絡平均路徑長度之所以小，是因為數據包在網絡中由起始點到目的節點的轉發過程中，可能經過多個自治域，而在自治域內部，數據的轉發需多個邊界路由器．對于IP級互聯網來說，IPv6網絡數據轉發能力優于IPv4網絡，可見IPv6網絡魯棒性更強．

3.2互聯網網絡度分布冪指數演化對于冪律分布有p(k)～k－α，p(k)是度值為k的節點出現的概率，α為冪指數．在以往的研究中，多數學者以α量化網絡均勻程度，度分布越冪律(冪指數α介于2～3之間)，網絡越呈現無標度網絡的特性，其網絡拓撲所表現出的魯棒性就越強［14］．以2009～2013年的探測數據為基礎，每年選取1月與7月2個探測單元，計算IPv4，IPv6與AS級網絡度分布冪指數統計α，見表1．可見IPv4網絡冪指數在探測期間始終大于2，演化趨勢平緩，說明IPv4網絡的無標度特征十分明顯，網絡中度值很高的“中心節點”(HUB)只占節點總數很少一部分，而小度值節點大量存在，且度值接近;IPv6與AS網絡冪指數均在1.8左右，說明網絡中HUB節點偏多，HUB節點與小度值節點在網絡中均占一定比例．但對于技術類網絡(如互聯網)，實現并維持這樣的網絡，意味著要持續注入大量的資金及技術成本，這增大了實際實現過程的難度．但是，IPv6與AS級網絡度分布冪指數均呈緩慢增長趨勢，說明這2種網絡正逐漸向著度分布更冪律、魯棒性更強的無標度網絡演化．互聯網的無標度特性不僅進一步地證實物理學家關于無標度網絡具有生命特征的預言，也展示了真實互聯網兼具集權結構的秩序與均權扁平的無序兩種屬性．一方面，為保證通信效率，必須存在HUBs;另一方面，受成本制約HUBs又不能太多，因此互聯網冪指數會傾向處于2～3之間［14］，演化出無標度網絡的魯棒性．可見，互聯網宏觀拓撲秩序既不會由于大量HUBs而導致極端專制，也不會存在所有節點度值相近而導致均權和無序．為實現利益最大化，人類只得放棄對互聯網的精確控制，將互聯網作為一個宏大智慧生命體，嘗試引入生物學思想，使其更好地實現生命的自適應能力．

4結論

1)網絡規模從外觀上描述了互聯網具有擴展潛力;標準網絡結構熵則從網絡拓撲演化內在動力入手，兩者共同描述了彈性網絡特征的可擴展性．并且，IPv4與AS級網絡熵值逐漸增大，而IPv6熵值演化趨勢平緩，說明互聯網拓撲結構是不斷由混沌向穩態發展，再向混沌演化的，每一次穩態中秩序的產生都是通過系統自組織推動的．2)IPv4，IPv6與AS級互聯網均表現出無標度網絡特性，且網絡連通性不斷增強，數據傳輸效率不斷優化，宏觀自適應性不斷增強，3種網絡魯棒性增強，即網絡面對微擾更易恢復原有或形成更穩定的拓撲狀態．這也印證了互聯網跨層級間的連接越來越多(尤其是國家骨干網、區域網絡和國際骨干網之間，各城域網也直接與骨干網互連)，從而降低路由跳數、減少網絡瓶頸、縮短網絡時延.

作者：劉曉 趙海 張君 王進法 單位：東北大學 計算機科學與工程學院