簡化的NS2路由模擬策略

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

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

0 引 言

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

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

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

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

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

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

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

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

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

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

2 NS2簡化路由模擬策略

2.1 簡化路由模擬策略原理

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

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

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

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

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

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

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

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

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

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

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

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

圖1 簡化路由模擬策略

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

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

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

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

表1 時(shí)間開銷對比

表2 存儲開銷對比

3 實(shí)驗(yàn)與結(jié)果分析

3.1 簡單網(wǎng)絡(luò)拓?fù)鋵?shí)驗(yàn)

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

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

3.2 大規(guī)模網(wǎng)絡(luò)模擬實(shí)驗(yàn)

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

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

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

圖3 路由計(jì)算時(shí)間對比

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

圖5 模擬運(yùn)行時(shí)間對比

圖6 存儲空間對比

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

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

4 結(jié)束語

當(dāng)前靜態(tài)路由模擬策略中大規(guī)模網(wǎng)絡(luò)模擬需要相當(dāng)長的運(yùn)行時(shí)間和存儲空間，為減少模擬運(yùn)行所需的時(shí)間開銷和存儲開銷，本文分析了靜態(tài)路由模擬策略的缺陷及其形成原因，提出了簡化的NS2路由模擬策略。該策略將網(wǎng)絡(luò)模擬中的路由信息進(jìn)行分類簡化，改進(jìn)了路由計(jì)算和地址分類器設(shè)置，從而避免大量終端節(jié)點(diǎn)的路由存儲和遍歷計(jì)算，有效提高了模擬運(yùn)行效率。多組實(shí)驗(yàn)結(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ì)算和查找方法[J].通信學(xué)報(bào),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ì)算與查找策略[J].電子學(xué)報(bào),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.