網路拓撲生成

網路拓撲生成,是通過對現實網路進行建模,然後利用模型生成網路拓撲的方法。它與網路拓撲發現是不同的,後者是從一台設備出發,探測周圍的網路拓撲的方法。

概述

在計算機網路研究中,經常需要對新的應用程式、體系結構或者協定等進行評估,因此基於真實網路的網路模擬就成了計算機網路研究的一種重要方法。由於網路存在多樣性和複雜性,影響網路模擬穩定性的重要因素就是所使用的網路拓撲模型。用儘量能反映真實網路的模型作為對真實網路環境的一種抽象,使之作為網路模擬的基本輸入,是取得正確結果的必要條件。

目前的網路拓撲生成模型主要是建立在隨機模型、層次結構模型或冪律模型的基礎上,常用的拓撲生成方法/模型有Waxman,Tiers,Transit-stub,BA,Inet等。其中Waxman為隨機模型,Tiers和Transit-stub建立在層次結構的基礎上,BA和Inet都是基於冪律模型。Brite和Inet則是典型的拓撲生成器,可以基於前述的模型進行網路拓撲的模擬生成,通過其生成的網路拓撲數據對於研究實際生活中的網路狀況和協定性能有很重要的作用。

網路拓撲生成,作為網路模擬的前端輸入,是網路模擬的重要內容,也是決定網路模擬真實性和可靠性的重要因素。對網路拓撲生成的研究是當今網路研究領域的重要課題,而對真實世界中網路拓撲的研究和模擬,則是最佳化現有網路、開發下一代網路協定、測試新網路協定的基礎。

網路拓撲生成是一個新興的研究領域,始於20世紀90年代,在近幾年得到了較大的發展。其中Boston大學的brite、UMich大學的inet、LouisPasteur大學的nem等都是比較流行的網路拓撲生成器。

網路拓撲模型

研究路由協定,對於研究者來講,直接在商業網路上進行路由測試是基本做不到的,並且在某個網路上測試會將測試結果局限於該網路上。此外,在特定的網路上表現良好的路由協定,當該網路的拓撲結構發生變化或移植到其他不同的網路時,不一定能表現出同樣的性能。因此,路由協定通常先在隨機網路上進行測試。

從表面上看,網路中各節點的分布似乎是均勻的,主機的接入和斷開具有很大的隨機性,因而,網路整體的拓撲結構應當呈現均勻分布的特性,或者說其節點的度(degree)是均勻分布的(度指連到特定節點的鏈路數目)。但是通過對大量的實際數據研究表明,實際網路的度分布呈冪律(Power-Law)分布特性,這說明了在網路中既有大量連線鬆散的節點,也存在一些連線緊密的節點,而且各個標度的節點都廣泛存在。

利用NS-2進行網路仿真需要建立合適的網路拓撲模型來反映真實網路拓撲的某些本質的特性(如接點度的分布)。現在主流的網路拓撲模型主要有隨機型、層次型和冪律型三類。

(1)隨機型,即認為網路拓撲圖處於一個完全無序的狀態,在大尺度上是均一的最早的隨機模型是由Waxman提出來的。Waxman認為節點之間的連線機率與其距離相關,服從泊松分布,距離越近,機率越大。

(2)層次型,來自對網路結構所具有的層次特徵的認識,在同一層上的節點出度接近,不同層間節點出度差別很大。對同一層上的節點布置借用Waxman模型方法。

(3)冪律型,1999年,Faloutsos等人對NLANR(NationalLabforAppliedNetworkResearch)在1997-1998年間的3份BGP數據以及1995年的一份tracerouter測量數據進行分析,發現網路拓撲中存在著冪律規律。

拓撲生成器的發展

拓撲生成器是拓撲生成算法的軟體實現,是生成拓撲的工具,其設計目標可歸納為3點:

(1)代表性,即生成的拓撲圖要能夠準確反映實際網路拓撲的各個方面;

(2)包含性,即將許多生成模型合併在一起,提供一個通用的拓撲生成工具;

(3)兼容性,即為網路模擬應用程式(如NS-2)以及可視化工具(如CAIDA的Otter[7])提供接口。

為了實現這些目標,一個拓撲生成器主要包括3個功能模組:

(1)格式轉換:由於目前沒有統一的拓撲數據檔案格式標準,所以拓撲生成器要具有在各種拓撲測量數據,拓撲生成器輸入輸出數據以及網路模擬軟體輸入數據之間進行檔案格式轉換的功能。

(2)拓撲生成:這是拓撲生成器的核心,除了根據已有的拓撲生成算法實現冪律之外,還要依據其他度量來產生拓撲圖。

(3)拓撲分析:根據拓撲生成模組中所採用的度量來對拓撲數據進行統計分析,給出度量的值。

拓撲生成器的發展經歷如下過程:

*Waxman

Waxman是第一代發展起來的拓撲生成器。此生成器在Erdös-Renyi隨機圖模型的基礎上產生隨機圖,但是它包括一些網路特殊特徵,比如把節點放置在平面上,利用一定的機率來連線兩個節點。

*GT-ITM

GT-ITM最大的特點就是提供了Transit-Stub(TS)模型,此模型集中於對分層結構網路的再生成。TS模型將AS域劃分為Transit類和Stub類。在該模型中,Transit節點彼此互聯構成一個節點群,一個或多個Transit節點群構成拓撲圖的核心,而Stub節點分布在Transit節點群四周與Transit節點相連。

*Inet

Inet是密西根大學於1999~2002年間開發的一個AS級拓撲產生器,最新發布的是3.0版本。其特點是利用route-views.oregon-ix.net上從1997年11月到2002年2月間的大量BGP數據來確定拓撲度量的值,可信性很高。Inet採用PLGR算法與優先附著實現冪律,重視連通性(最小節點覆蓋),並針對最大團尺寸和聚類係數做了最佳化。Inet使用簡便,只需在命令行輸入拓撲圖節點總數即可。

*BRITE2.1

其特點在於“通用”。首先,它實現了Waxman模型和BA算法,並可以用自頂向下和自底向上兩種方法來產生GT-ITM層次模型;其次,它為多個網路模擬程式提供接口,包括NS-2、SSFomnet++、JSim,並支持可視化工具Otter。BRITE產生路由器層、AS層以及分層結構拓撲圖,並可為連線分配頻寬和延遲,具有圖形用戶接口。

相關詞條

相關搜尋

熱門詞條

聯絡我們