張 恬， 毛 力， 張兆心， 王曉鋒

(1.江南大學(xué)信息工程學(xué)院，江蘇無錫214122；2.哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001)

0 引 言

網(wǎng)絡(luò)模擬軟件是研究網(wǎng)絡(luò)技術(shù)、評估網(wǎng)絡(luò)設(shè)計方案以及診斷網(wǎng)絡(luò)故障的有力工具。在新技術(shù)的研究過程中，實際網(wǎng)絡(luò)系統(tǒng)的實現(xiàn)往往是代價較高或不現(xiàn)實的，為了減少投資風(fēng)險，降低網(wǎng)絡(luò)實現(xiàn)費用，模擬就成了最佳可供選擇的測試、評估和驗證手段之一。NS2(networksimulator，version2)[1-2]是其中一種比較具有代表性的模擬軟件，由UCBerkeley等開發(fā)而成，應(yīng)用了一些比較成熟的方法，并作為一款優(yōu)秀的開源軟件被廣泛使用。

隨著計算機網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)規(guī)模逐步擴大，網(wǎng)絡(luò)模擬中路由策略的計算開銷與存儲空間變得更大，網(wǎng)絡(luò)路由模擬也成為了研究的熱點問題之一[3]。目前網(wǎng)絡(luò)路由模擬策略主要分為兩類：一類是Flat策略，即靜態(tài)路由模擬策略[4]，該策略中路由表的計算與存儲涉及所有節(jié)點，使得路由模擬需要較大的計算與存儲開銷；另一類則是Nixvector策略[5]，該策略雖然只在路由需要的時候計算并不進(jìn)行存儲，減少了存儲開銷，但是由于同一條路由信息需要不斷計算，又大大增加了計算開銷。

針對當(dāng)前路由策略存在的上述問題，本文分析了靜態(tài)路由模擬策略的缺陷，提出了一種簡化的NS2路由模擬策略。該策略首先將模擬節(jié)點分為路由器節(jié)點和終端節(jié)點兩大類，進(jìn)行路由計算時，只有計算頻繁的路由器節(jié)點參與；進(jìn)行地址分類器設(shè)置時，計算不頻繁的終端節(jié)點選擇性參與。與Flat策略相比，該策略只計算和存儲路由器節(jié)點的路由信息，選擇性存儲與計算終端節(jié)點的路由信息，降低了路由模擬的計算和存儲開銷；與Nixvector策略相比，該策略將參與計算的路由信息進(jìn)行靜態(tài)存儲，降低了路由模擬的計算開銷。

1 NS2 靜態(tài)路由模擬策略

1.1 靜態(tài)路由模擬策略原理分析

NS2默認(rèn)的路由策略是靜態(tài)路由模擬策略，路由計算是由網(wǎng)絡(luò)拓?fù)渲械乃泄?jié)點作為鄰接矩陣和連接代價，采用Dijkstra的all-pairsSPF算法計算出每個節(jié)點的下一跳nh，通過存放下一跳nh的鄰接矩陣，計算出完整的路由。地址分類器設(shè)置需要對所有節(jié)點的地址分類器進(jìn)行設(shè)置，使分類器各個接口指向正確的出鏈路，根據(jù)加載到每個節(jié)點上的路由信息來選路。

在模擬靜態(tài)路由模擬策略的過程中，路由的確定根據(jù)從終端節(jié)點發(fā)送的數(shù)據(jù)包選取一個合適的路由路徑，并找到相應(yīng)的下一跳節(jié)點。按照上述方法就可以完成所有數(shù)據(jù)包的接收，雖然不影響擴大模擬規(guī)模，但每次模擬一個新的數(shù)據(jù)包發(fā)送、接收過程都需要遍歷全局拓?fù)湟杂嬎懵酚桑鋾r間復(fù)雜度很大。

1.2 對靜態(tài)路由模擬方法缺陷的分析

在模擬過程中，最重要且最耗時的地方有兩處：① 建立和計算路由表，它需用到全部節(jié)點，但所有度為1的節(jié)點不具有路由功能；② 對所有節(jié)點的地址分類器進(jìn)行設(shè)置，但并不是所有的節(jié)點都參與了分組的發(fā)送、接收或傳遞。

如果用n表示整個拓?fù)鋱D中的節(jié)點數(shù)量，則路由計算的時間復(fù)雜度是O(n3)，同時需要維護(hù)n2的路由表；地址分類器設(shè)置的時間復(fù)雜度是O(n2)，需要對n個節(jié)點進(jìn)行分類器設(shè)置。隨著n的增加，運行時間和存儲空間都將快速增長，這顯然不適合大型網(wǎng)絡(luò)事件的模擬。為此本文提出了一種簡化的路由模擬策略。

2 NS2簡化路由模擬策略

2.1 簡化路由模擬策略原理

根據(jù)節(jié)點在網(wǎng)絡(luò)拓?fù)渲械淖饔眠M(jìn)行分類[6]：

定義1 路由器節(jié)點：用于實現(xiàn)分組轉(zhuǎn)發(fā)，一般不與代理及應(yīng)用相連，主要功能類似實際網(wǎng)絡(luò)中的路由器節(jié)點。

定義2 終端節(jié)點：度為1且只與路由器節(jié)點相連，通常與代理及應(yīng)用相連，但不具有路由功能。

定義3 終端路由器節(jié)點：直接與終端節(jié)點相連的路由器節(jié)點。

針對上述定義，網(wǎng)絡(luò)模擬拓?fù)淠Ｐ椭械墓?jié)點可分為實現(xiàn)分組轉(zhuǎn)發(fā)的路由器節(jié)點和網(wǎng)絡(luò)應(yīng)用的終端節(jié)點。Internet實際上是一個具有分層管理結(jié)構(gòu)的系統(tǒng)，存在大量的終端節(jié)點，并且數(shù)量遠(yuǎn)遠(yuǎn)多于路由器節(jié)點。例如局域網(wǎng)系統(tǒng)，一系列終端節(jié)點通過一個終端路由器節(jié)點與外部網(wǎng)絡(luò)進(jìn)行通信[7]。考慮到路由器節(jié)點的路由信息計算復(fù)雜、使用頻繁，終端節(jié)點和終端路由器之間的路由關(guān)系是固定的，終端路由器節(jié)點是終端節(jié)點發(fā)送和接收分組的必經(jīng)之路，終端節(jié)點的路由信息計算簡單、使用不頻繁，本文提出了一種簡化路由模擬策略，其具體思路是：針對計算復(fù)雜、使用頻繁的路由信息采用靜態(tài)存儲的方法；針對計算簡單、使用不頻繁的路由信息則采用選擇計算的方法，即只對參與分組發(fā)送、傳遞的終端節(jié)點和路由器節(jié)點進(jìn)行分類器設(shè)置。下面對簡化路由模擬策略做進(jìn)一步闡釋。

2.2 簡化路由模擬策略實現(xiàn)

為了實現(xiàn)上述思路從以下4個方面對靜態(tài)路由模擬策略進(jìn)行簡化：

(1)節(jié)點分類：在靜態(tài)路由模擬策略中統(tǒng)一建立s個節(jié)點，在簡化路由策略中s個節(jié)點分為m個終端節(jié)點(Trouter)，編號為0～m 1，n個路由器節(jié)點，編號為n～n+m 1，同時標(biāo)記終端節(jié)點在OTcl和C++中的對象。

(2)減少鄰接矩陣維數(shù)：對所有鏈路，若鏈路兩端均不是終端節(jié)點，即為使用頻繁的路由器節(jié)點時將鏈路代價插入到代價鄰接矩陣中；若有一端為終端節(jié)點，將與終端節(jié)點相連的終端路由器節(jié)點設(shè)置為另一端節(jié)點。這樣減少了靜態(tài)模擬策略中代價鄰接矩陣維數(shù)，維數(shù)由s×s變?yōu)閚×n。

(3)簡化查找下一跳：使用頻繁的路由器節(jié)點對或發(fā)送與接收分組的終端節(jié)點對(i，j)查找路由表R(i，j)時，如果兩端不是終端節(jié)點則下一跳nh=R(i，j)；如果i為終端節(jié)點則nh=node[i]->Trouter；如果j為終端節(jié)點，而i不是終端節(jié)點則nh=R(i，node[j]->Trouter)；如果j為終端節(jié)點，而i也是終端節(jié)點則nh=j；相比靜態(tài)路由模擬策略減少了對路由表的查找時間，從而降低了時間復(fù)雜度和存儲空間。

(4)去除未參加分組發(fā)送與接收的終端節(jié)點：為進(jìn)一步減少模擬運行時間和存儲空間，引入數(shù)組，用來記錄參與分組發(fā)送與接收的終端節(jié)點的編號。對終端節(jié)點進(jìn)行地址分類時，如果與數(shù)組中的編號匹配則進(jìn)行計算，否則跳過尋找下一個相匹配的節(jié)點。

經(jīng)過上述分析就形成了對靜態(tài)路由模擬策略的簡化，具體結(jié)構(gòu)示意圖如圖1所示。

圖1 簡化路由模擬策略

2.3 簡化路由模擬策略性能分析

(1)由于對計算復(fù)雜、使用頻繁的路由信息是通過路由計算獲得的，所以只需維護(hù)一個含有n個路由器節(jié)點的路由表，可以使時間復(fù)雜度由O((n+m)3)降低到O(n3)。整個路由計算的時間將會明顯的減少，同時只需維護(hù)n2規(guī)模的路由表，相比原有(m+n)2的路由表，存儲空間也有很大的下降。

(2)對地址分類器設(shè)置的簡化，只對路由器節(jié)點和鏈路中參與分組發(fā)送與接收的終端節(jié)點進(jìn)行分類器設(shè)置。如果網(wǎng)絡(luò)中有p個終端節(jié)點參與了分組發(fā)送與接收，時間復(fù)雜度變?yōu)镺((n+p)2)(p<=m)，與原有時間復(fù)雜度O((n+m)2)相比(實際鏈路中參與分組發(fā)送與接收的p比m少很多)，整個計算時間將會有顯著的減少，同時由于只對n個路由器節(jié)點和鏈路中參與分組發(fā)送與接收的p個終端節(jié)點，進(jìn)行分類器設(shè)置，存儲空間也會有所下降。

靜態(tài)的路由模擬與簡化的路由模擬時間開銷和存儲開銷對比表分別如表1和表2所示(n，m，p分別表示路由器節(jié)點數(shù)目，終端節(jié)點數(shù)目，參與分組發(fā)送或接收的終端節(jié)點數(shù)目)。

表1 時間開銷對比

表2 存儲開銷對比

3 實驗與結(jié)果分析

3.1 簡單網(wǎng)絡(luò)拓?fù)鋵嶒?/h3>

采用簡單網(wǎng)絡(luò)拓?fù)鋵嶒瀬眚炞C簡化路由模擬策略的真實性。如圖2所示，該拓?fù)浣Y(jié)構(gòu)共有9個節(jié)點，R1-R3為路由器節(jié)點，T1-T6為終端節(jié)點。分別采用靜態(tài)路由模擬策略和簡化路由模擬策略進(jìn)行兩次模擬。建立ftp連接，模擬時間為50S。查看自帶記錄文件(trace文件)發(fā)現(xiàn)，兩次模擬實驗的記錄結(jié)果完全一致。由此可以說明簡化路由模擬策略的真實性。

圖2 簡單網(wǎng)絡(luò)拓?fù)?/p>

3.2 大規(guī)模網(wǎng)絡(luò)模擬實驗

實驗運行環(huán)境為PC機一臺，在NS2模擬器上實現(xiàn)了簡化的路由模擬策略，并將其與靜態(tài)路由模擬策略進(jìn)行了比較。實驗中的拓?fù)浣Y(jié)構(gòu)采用了流行的NEM拓?fù)渖善鱗8]產(chǎn)生。共生成3組數(shù)據(jù)：1000個節(jié)點(100個路由器節(jié)點和900個終端節(jié)點)，2000個節(jié)點(200個路由器節(jié)點和1800個終端節(jié)點)，3000個節(jié)點(400個路由器節(jié)點和2600個終端節(jié)點)。

路由策略的性能指標(biāo)主要包括路由計算時間、地址分類器設(shè)置時間、模擬運行時間以及存儲空間大小。圖3至圖6分別給出了不同節(jié)點規(guī)模條件下，上述4個指標(biāo)在兩種路由模擬策略下的變化曲線。在拓?fù)溥B接和模擬應(yīng)用完全相同的前提下，兩種路由模擬策略在4個指標(biāo)下的差異主要緣于路由策略的區(qū)別。

圖3顯示的是不同節(jié)點規(guī)模下所需的路由計算時間。隨著拓?fù)湟?guī)模增大，采用靜態(tài)路由模擬策略的路由計算時間快速增大，而采用簡化的路由模擬策略的路由時間增大緩慢，比靜態(tài)路由模擬策略的時間開銷減少了約99%，相對于大規(guī)模復(fù)雜模擬運行所需時間，簡化的路由模擬策略更合適。

圖3 路由計算時間對比

圖4 節(jié)點分類器設(shè)置時間對比

圖5 模擬運行時間對比

圖6 存儲空間對比

圖4和圖5給出了不同節(jié)點規(guī)模下兩種路由模擬策略的地址分類器設(shè)置時間及完成模擬所需時間的比較。根據(jù)圖4和圖5的結(jié)果，地址分類器設(shè)置時間和運行時間分別比靜態(tài)路由模擬策略減少了75%和61%，也顯示出了簡化的路由模擬策略的優(yōu)越性。

圖6顯示的是不同節(jié)點規(guī)模下所需的總存儲空間大小，由路由計算部分和地址分類器設(shè)置部分的存儲空間組成。隨著節(jié)點數(shù)的增加，靜態(tài)路由模擬策略的存儲空間也急劇增大，而簡化的路由模擬策略的存儲空間緩慢增長。因此，簡化的路由模擬策略相比靜態(tài)路由模擬策略更能節(jié)約內(nèi)存空間，這就意味著可以擴大模擬網(wǎng)絡(luò)規(guī)模，從而提高NS2模擬器的效率。

4 結(jié)束語

當(dāng)前靜態(tài)路由模擬策略中大規(guī)模網(wǎng)絡(luò)模擬需要相當(dāng)長的運行時間和存儲空間，為減少模擬運行所需的時間開銷和存儲開銷，本文分析了靜態(tài)路由模擬策略的缺陷及其形成原因，提出了簡化的NS2路由模擬策略。該策略將網(wǎng)絡(luò)模擬中的路由信息進(jìn)行分類簡化，改進(jìn)了路由計算和地址分類器設(shè)置，從而避免大量終端節(jié)點的路由存儲和遍歷計算，有效提高了模擬運行效率。多組實驗結(jié)果表明，相對于傳統(tǒng)的靜態(tài)路由模擬策略，該策略更適合大規(guī)模網(wǎng)絡(luò)環(huán)境下復(fù)雜應(yīng)用的模擬。

[1] The network simulator NS-2[EB/OL].http://www.isi.edu/nsnam/ns,2005.

[2] 徐雷鳴,趙耀.NS與網(wǎng)絡(luò)模擬[M].北京:人民郵電出版社,2003.

[3] 郝志宇,云曉春,張宏莉.并行網(wǎng)絡(luò)模擬中的遠(yuǎn)程路由計算和查找方法[J].通信學(xué)報,2007,28(6):66-72.

[4] Chen J,Gupta D,Vishwanath K,et al.Routing in an Internet scale network simulator[C].Proceedings of the IEEE International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems.Washington DC,USA:IEEE Computer Society,2004.

[5] 郝志宇,云曉春,張宏莉.MTree_Nix網(wǎng)絡(luò)模擬路由計算與查找策略[J].電子學(xué)報,2008,3(3):477-481.

[6] Hao Zhiyu,Yun Xiaochun,Zhang Hongli.Tnrm based simulation of Internet worm propagation[C].St.Thomas,US:Proceeding of the Fourth IASTED International Conference Communications,Internet,and Information Technology,2006:183-184.

[7] Yihua He,Georgos Siganos,Michalis Fal Outsos,et al.Lord of the links:A framework for discovering missing links in the Internet topology[J].IEEE/ACM Transactions on Networking,2009,17(2):391-404.

[8] Magoni D.Network topology analysis and internet modeling with Nem[J].International Journal of Computers and Applications,2005,27(4):252-259.