楊國(guó)玲，王曉鋒，毛 力

（江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫214122）

0 引 言

當(dāng)前，網(wǎng)絡(luò)模擬已成為研究網(wǎng)絡(luò)行為和評(píng)價(jià)網(wǎng)絡(luò)協(xié)議的的重要手段［1，2］。但隨著網(wǎng)絡(luò)規(guī)模越來越大，結(jié)構(gòu)越來越復(fù)雜，網(wǎng)絡(luò)模擬的高資源消耗問題 （大量的計(jì)算及存儲(chǔ)開銷）也日益突出。目前針對(duì)該問題的研究主要集中于簡(jiǎn)化網(wǎng)絡(luò)模擬模型，即通過提高網(wǎng)絡(luò)模擬的抽象度，來降低計(jì)算及存儲(chǔ)開銷。其中，文獻(xiàn) ［3］提出一種基于local－area拓?fù)涑橄笏惴?，該方法首先把網(wǎng)絡(luò)劃分成多個(gè)本地域，然后對(duì)每一個(gè)本地域進(jìn)行抽象來降低拓?fù)湟?guī)模。文獻(xiàn) ［4］提出一種基于焦點(diǎn)區(qū)域折疊的拓?fù)涑橄蠓椒ǎ@種方法把網(wǎng)絡(luò)分成焦點(diǎn)區(qū)域和非焦點(diǎn)區(qū)域，通過對(duì)非焦點(diǎn)區(qū)域的樹形收縮來降低網(wǎng)絡(luò)規(guī)模。文獻(xiàn) ［5］提出一種基于主機(jī)刪減的蠕蟲模擬方法，該方法按比例對(duì)主機(jī)進(jìn)行縮減來減少模擬開銷。文獻(xiàn) ［6］提出一種基于聚合系數(shù)的拓?fù)涑橄笏惴ǎㄟ^樹形抽象和權(quán)值估算抽象來縮小網(wǎng)絡(luò)規(guī)模。文獻(xiàn) ［7］和文獻(xiàn) ［8］則分別通過刪除全部主機(jī)節(jié)點(diǎn)和部分路由節(jié)點(diǎn)、刪除部分主機(jī)節(jié)點(diǎn)來縮減網(wǎng)絡(luò)拓?fù)洹?/p>

上述文獻(xiàn)中的抽象算法普遍存在抽象率低或模擬真實(shí)性無法保證的問題。其中，文獻(xiàn) ［3，4，6－8］有效地縮減了拓?fù)湟?guī)模，提高了模擬效率，但其真實(shí)性無法保證；文獻(xiàn) ［5］為了保證模擬真實(shí)性，只刪減了部分主機(jī)節(jié)點(diǎn)，抽象度較低。針對(duì)上述問題，本文提出了一種高真實(shí)性的拓?fù)湔郫B方法HFTF （high fidelity topology folding），該方法先通過對(duì)大規(guī)模網(wǎng)絡(luò)拓?fù)溥M(jìn)行路由刪減和主機(jī)抽象來形成小規(guī)模的網(wǎng)絡(luò)拓?fù)?，然后在此基礎(chǔ)上分析了抽象后模擬結(jié)果的失真情況，并進(jìn)行了相應(yīng)補(bǔ)償，從而在有效提高模擬效率的同時(shí)，保證了模擬結(jié)果的真實(shí)性。

1 拓?fù)湔郫B算法

本文提出了一種基于拓?fù)湔郫B的抽象算法，該算法分為兩步：第一步遞歸刪除度為1的路由節(jié)點(diǎn)；第二步對(duì)主機(jī)節(jié)點(diǎn)進(jìn)行抽象。相關(guān)定義如下 （其中V 表示路由節(jié)點(diǎn)，H 表示主機(jī)節(jié)點(diǎn)）：

定義1 L （Vi，Vj）表示在節(jié)點(diǎn)Vi和Vj之間的鏈路。

定義2 HostNumber （Vi）表示節(jié)點(diǎn)Vi所帶的主機(jī)數(shù)。

定義3 Degree （Vi）表示節(jié)點(diǎn)Vi的度數(shù)。該算法采用無向路由拓?fù)?，因此每個(gè)節(jié)點(diǎn)的度數(shù)就是與其相連的（不包括與主機(jī)相連的）鏈路的個(gè)數(shù)。

定義4 a表示主機(jī)抽象系數(shù)。

1.1 遞歸刪除算法

算法具體描述如下：

（1）procedure router deletion

（2） for each Viinit Degree（Vi）＝0

（3） end for

（4） for each L（Vi，Vj）

（5） if L（Vi，Vj）exit do

（6） Degree（Vi）＋＋，Degree（Vj）＋＋；

（7） end if

（8） end for

（9） if exit Degree（Vi）＝1do

（10） for each Vi

（11） if Degree（Vi）＝1and L（Vi，Vj）exit do

（12） record Vi；

（13） HostNum（Vj）＝HostNum（Vi）＋HostNum（Vj）；

（14） delete Vi；

（15） delete L（Vi，Vj）；

（16） end if

（17） end for

（18） for each Viinit Degree（Vi）＝0

（19） end for

（20） for each L（Vi，Vj）

（21） if L（Vi，Vj）exit do

（22） Degree（Vi）＋＋，Degree（Vj）＋＋；

（23） end if

（24） end for

（25） end if

（26）end procedure

其中，（2）－（3）初始化路由節(jié)點(diǎn)度數(shù)為0；（4）－（8）計(jì)算路由節(jié)點(diǎn)度數(shù)；（9）－（25）遞歸刪除拓?fù)渲卸葹?的路由節(jié)點(diǎn)，并把其所帶的主機(jī)節(jié)點(diǎn)歸并到與之相連的另一個(gè)路由節(jié)點(diǎn)上，然后再重新計(jì)算度數(shù)，直到所有節(jié)點(diǎn)的度數(shù)都不為1。

通過圖1進(jìn)行舉例說明，為描述方便，令每個(gè)路由器帶4個(gè)主機(jī)，“□”代表路由節(jié)點(diǎn)，“○”代表主機(jī)節(jié)點(diǎn)。

圖1 部分原始拓?fù)?/p>

經(jīng)過遞歸刪除算法，圖1簡(jiǎn)化得到的結(jié)果如圖2所示。

圖2 遞歸刪除算法之后的拓?fù)?/p>

1.2 主機(jī)抽象算法

算法具體描述如下：

（1）procedure host abstraction

（2） for each Vido

（3） HostNum （Vi）＝HostNum （Vi）／a

（4） end for

（5）end procedure

以上 （1）－（5）使每個(gè)路由器上的主機(jī)數(shù)按抽象系數(shù)（a）進(jìn)行縮減。

針對(duì)圖2，若取a 為4，則圖2 經(jīng)過主機(jī)抽象算法后，變?yōu)閳D3的拓?fù)洹?/p>

圖3 主機(jī)抽象之后的拓?fù)?/p>

2 拓?fù)湔郫B后鏈路的失真分析及補(bǔ)償

由HFTF算法分析可知：經(jīng)過第一步的路由刪減，部分路由節(jié)點(diǎn)和鏈路會(huì)被刪除，即和原始拓?fù)湎啾?，同樣的?shù)據(jù)包傳輸經(jīng)過路由節(jié)點(diǎn)和鏈路會(huì)變少，這必然會(huì)導(dǎo)致發(fā)送時(shí)延和傳播時(shí)延的降低；經(jīng)過第二步的主機(jī)抽象，使主機(jī)的數(shù)量變?yōu)樵瓉淼?／a，而這也會(huì)導(dǎo)致流入網(wǎng)絡(luò)的流量速率降低、從而導(dǎo)致排隊(duì)時(shí)延以及丟包率的降低。這兩方面會(huì)對(duì)模擬結(jié)果的真實(shí)性造成影響，具體分析與補(bǔ)償方法如下所示。

2.1 排隊(duì)時(shí)延和丟包率的失真分析及補(bǔ)償

基于經(jīng)典的DropTail隊(duì)列管理算法來分析。原始拓?fù)涞南嚓P(guān)變量定義如下：

F：路由器Vi上的出鏈路L 相對(duì)應(yīng)的緩沖隊(duì)列；

L（t）：F 在t時(shí)刻隊(duì)列字節(jié)長(zhǎng)度；

Q（t）：數(shù)據(jù)包的排隊(duì)延遲；

B：鏈路L 的帶寬，則Q（t）＝L（t）／B；

F（t）：t時(shí)刻流入隊(duì)列F 的流量速率；

Lavg：緩沖隊(duì)列數(shù)據(jù)包的平均字節(jié)長(zhǎng)度；

Tmax：緩沖隊(duì)列的最大長(zhǎng)度。

同理定義拓?fù)湔郫B后的相關(guān)變量L′（t），B′，F(xiàn)′（t），Q′（t），T′max。由HFTF算法可知，拓?fù)湔郫B之后主機(jī)數(shù)量變?yōu)樵瓉淼?／a，這會(huì)導(dǎo)致流入拓?fù)涞牧髁克俾室沧優(yōu)樵瓉淼?／a，則流入每個(gè)路由器隊(duì)列的流量速率也應(yīng)為1／a，即

為了保證模擬結(jié)果的真實(shí)性，這里令拓?fù)湔郫B后的L的帶寬、緩沖隊(duì)列的最大長(zhǎng)度均為原來的1／a （下面會(huì)分析在此條件下丟包率以及排隊(duì)時(shí)延的真實(shí)性），即

原始拓?fù)涞膩G包率p（t）為

t時(shí)刻的隊(duì)列長(zhǎng)度與丟包率滿足如下關(guān)系

其中，φ（x）的取值為：若x＞0，φ（x）＝1；若x≤0，φ（x）＝0。

拓?fù)湔郫B后的丟包率p′（t）為

拓?fù)湔郫B后的L′（t）和p′（t）的關(guān)系為

結(jié)合式 （2）、式 （5）得

結(jié)合式 （1）、式 （2）、式 （6）得

對(duì)比式（3）和式 （7）、式 （4）和式 （8），可以看出p（t）與p′（t），L （t）與aL′ （t）均滿足同一組關(guān)系式，則有

由定義可知拓?fù)湔郫B前后的數(shù)據(jù)包的排隊(duì)時(shí)延分別為：Q（t）＝L（t）／B、Q′（t）＝L′（t）／B′，結(jié)合式 （2）、式（10）可推出

由式 （9）、式 （11）可以看出，通過引入補(bǔ)償方法（把鏈路的帶寬及緩沖隊(duì)列的最大長(zhǎng)度均縮減為原來的1／a），即可保證網(wǎng)絡(luò)拓?fù)渲信抨?duì)時(shí)延和丟包率的真實(shí)性。

2.2 傳播時(shí)延和發(fā)送時(shí)延的失真分析及補(bǔ)償

數(shù)據(jù)包時(shí)延包括排隊(duì)時(shí)延，發(fā)送時(shí)延和傳播時(shí)延。相關(guān)定義如下：

Lp：數(shù)據(jù)包的長(zhǎng)度，則發(fā)送時(shí)延為L(zhǎng)p／B；

D：鏈路L的傳播時(shí)延。

假設(shè)數(shù)據(jù)包從m 節(jié)點(diǎn)傳到n節(jié)點(diǎn)，在原始拓?fù)渲兴?jīng)過的鏈路為L(zhǎng)1，L2，…，Li，…，在拓?fù)湔郫B后的拓?fù)渲兴?jīng)過的鏈路為L(zhǎng)1′，L2′，…，Lj′，…，則在原始拓?fù)渲械臄?shù)據(jù)包時(shí)延為

拓?fù)湔郫B后的數(shù)據(jù)包時(shí)延為 （D′為拓?fù)湔郫B后鏈路的傳播時(shí)延）

因?yàn)橥負(fù)湔郫B過后會(huì)導(dǎo)致數(shù)據(jù)包時(shí)延降低 （經(jīng)過的節(jié)點(diǎn)和鏈路變少），此時(shí)要保證模擬結(jié)果的真實(shí)性，需在m 到n的鏈路上加上一個(gè)延遲補(bǔ)償Δd，其值為

由2.1分析可知，在拓?fù)湔郫B前后

即在拓?fù)湔郫B后剩余節(jié)點(diǎn)的排隊(duì)時(shí)延和在原始拓?fù)渲械呐抨?duì)時(shí)延相等。由HFTF算法可知：刪除的路由節(jié)點(diǎn)都是邊緣節(jié)點(diǎn)，而邊緣節(jié)點(diǎn)的擁塞程度通常不高，其排隊(duì)時(shí)延可以忽略不計(jì)，則式 （14）可以寫成

由式 （16）可知，要保證拓?fù)湔郫B后數(shù)據(jù)包從m 到n時(shí)延的真實(shí)性，需要加上一個(gè)延遲補(bǔ)償Δd，其值為m 到n之間所有被刪除鏈路的發(fā)送延遲和傳播延遲總和。

3 實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證 HFTF 算法的有效性，本文采用基于NS2［9，10］的Slammer蠕蟲進(jìn)行模擬實(shí)驗(yàn)，網(wǎng)絡(luò)拓?fù)洳捎?組分別有50，100，150個(gè)路由節(jié)點(diǎn)的拓?fù)淠Ｐ?（把拓?fù)渲卸葹?的路由節(jié)點(diǎn)設(shè)為邊界路由器，每個(gè)邊界路由器連接64個(gè)主機(jī)節(jié)點(diǎn)，并將這些主機(jī)全部設(shè)為弱點(diǎn)主機(jī)），抽象系數(shù)a的取值為4。

3.1 拓?fù)湔郫B前后的規(guī)模比較

由圖4可以看出3組拓?fù)湓谕負(fù)湔郫B前后的規(guī)模對(duì)比：對(duì)50個(gè)路由節(jié)點(diǎn)，原始拓?fù)渲泄?jié)點(diǎn)數(shù)量是2290，折疊后為575，規(guī)模減少了74.89%；對(duì)100個(gè)路由節(jié)點(diǎn)，拓?fù)湔郫B前后的節(jié)點(diǎn)個(gè)數(shù)分別是4260和1071，減少了74.86%；對(duì)150個(gè)路由節(jié)點(diǎn)，折疊前后的節(jié)點(diǎn)個(gè)數(shù)分別為6870、1741，減少了74.66%。由此可以看出，此算法可以在很大程度上縮減網(wǎng)絡(luò)拓?fù)涞囊?guī)模。

圖4 拓?fù)湓谡郫B前后規(guī)模比較

3.2 拓?fù)湔郫B前后模擬時(shí)間的比較

由圖5可以看出，3 組拓?fù)湓谡郫B前后運(yùn)行時(shí)間的對(duì)比：對(duì)于50 個(gè)路由節(jié)點(diǎn)，折疊前后的模擬時(shí)間分別為578s、14s，降低了97.58%；對(duì)100 個(gè)路由節(jié)點(diǎn)，折疊前后的模擬時(shí)間分別是4171s、79s，降低了98.11%；對(duì)150個(gè)路由節(jié)點(diǎn)，折疊前后的模擬時(shí)間分別是5721s和124s，降低了97.83%。由此可以看出，此算法可以縮短模擬運(yùn)行時(shí)間97%以上。

圖5 拓?fù)湓谡郫B前后模擬時(shí)間比較

3.3 模擬結(jié)果的真實(shí)性比較

為了更好的說明HFTF算法的真實(shí)性，每組實(shí)驗(yàn)中都采用3組數(shù)據(jù)來做比較，這3組數(shù)據(jù)分別是原始拓?fù)淠M結(jié)果、拓?fù)湔郫B但沒有鏈路補(bǔ)償?shù)哪M結(jié)果和拓?fù)湔郫B并且加上鏈路補(bǔ)償?shù)哪M結(jié)果。比較結(jié)果如圖6所示 （橫坐標(biāo)為時(shí)間t，豎坐標(biāo)為t時(shí)刻感染的主機(jī)節(jié)點(diǎn)數(shù)量）。

通過圖6 （a）－（c）可以看出，采用HFTF算法的蠕蟲模擬感染曲線與原始拓?fù)涞牡母腥厩€幾乎完全一致，比不加鏈路補(bǔ)償?shù)耐負(fù)湔郫B算法具有更高的真實(shí)性。由此可以看出本文提出的高真實(shí)性拓?fù)湔郫B算法在降低網(wǎng)絡(luò)拓?fù)湟?guī)模，減少模擬運(yùn)行時(shí)間的前提下，仍可以保證結(jié)果的高真實(shí)性。

圖6 蠕蟲模擬在拓?fù)湔郫B前后的真實(shí)性比較

4 結(jié)束語

大規(guī)模網(wǎng)絡(luò)模擬中的高資源消耗問題已受到越來越多的關(guān)注，針對(duì)大規(guī)模網(wǎng)絡(luò)模擬中現(xiàn)有算法普遍存在的抽象率低或模擬真實(shí)性無法保證的問題，本文提出一種高真實(shí)性拓?fù)湔郫B模擬方法，該方法首先通過遞歸刪除算法和主機(jī)抽象算法來降低網(wǎng)絡(luò)拓?fù)湟?guī)模，提高抽象率，然后通過鏈路參數(shù)補(bǔ)償以及端到端延遲補(bǔ)償來確保模擬結(jié)果的真實(shí)性?；谌湎x模擬的實(shí)驗(yàn)驗(yàn)證了該方法可以降低網(wǎng)絡(luò)規(guī)模74%以上，減少模擬運(yùn)行時(shí)間97%以上，并且結(jié)果仍具有很高的真實(shí)性。

［1］WANG J，YU X，YAN J.Research on network simulation abstract technology based on simplicity theory ［C］／／Proceedings of International Conference on Wireless Networks and Information Systems.Shanghai，China：IEEE Computer Society，2009：186－192.

［2］WANG X，F(xiàn)ANG B，ZHANG H，et al.A model for estimating the performance of synchronous parallel network simulation［J］.International Journal of Modelling and Simulation，2008，28 （1）：100－107.

［3］LI Qiao，ZHANG Zhaoxin.An Internet router－level topology aggregation algorithm based on local－area ［J］.Chinese High Technology Letters，2011，21 （9）：922－927 （in Chinese）.［李喬，張兆心.基于local－area的Internet路由級(jí)拓?fù)涑橄笏惴?［J］.高技術(shù)通訊，2011，21 （9）：922－927.］

［4］ZHANG Zhaoxin，DU Yuejin，WANG Ke，et al.Topology aggregation model based on focus folding for network simulation［J］.Journal on Communications，2012，33 （7）：9－21 （in Chinese）.［張兆心，杜躍進(jìn)，王克，等.基于焦點(diǎn)折疊的網(wǎng)絡(luò)模擬拓?fù)涑橄竽Ｐ?［J］.通信學(xué)報(bào)，2012，33 （7）：9－21.］

［5］WANG Xiaofeng，GUAN Lu.Research on network worm simulation method based on host node reduction ［J］.Computer Engineering and Design，2012，33 （10）：3687－3691 （in Chinese）. ［王曉鋒，關(guān)鷺.基于主機(jī)節(jié)點(diǎn)刪減的網(wǎng)絡(luò)蠕蟲模擬方法研究 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2012，33 （10）：3687－3691.］

［6］DING Zhenquan，DONG Kaikun.Topology aggregation algorithm based on polymerization coefficient［J］.Computer Engineering，2012，38 （6）：111－115 （in Chinese）. ［丁振全，董開坤.基于聚合系數(shù)的拓?fù)涑橄笏惴?［J］.計(jì)算機(jī)工程，2012，38 （6）：111－115.］

［7］WANG Meijun，ZHANG Zhaoxin，LI Bin.Topology abstraction algorithm for parallel network simulation ［J］.Microcomputer Information，2011，27 （9）：169－171 （in Chinese）.［王美君，張兆心，李斌.并行網(wǎng)絡(luò)模擬中拓?fù)涑橄笏惴ǖ难芯浚跩］.微計(jì)算機(jī)信息，2011，27 （9）：169－171.］

［8］Hwangnam K，Jennifer H，Hyuk L.TranSim：Accelerating simulation of large－scale IP networks through preserving network invariants［J］.Computer Networks，2008，52 （15）：2924－2946.

［9］WANG Bo，ZHOU Zhiwei.Comparative analysis on network simulation software NS2and OPNET ［J］.Computer System and Application，2010，19 （6）：90－95 （in Chinese）.［王波，周志偉.網(wǎng)絡(luò)模擬軟件NS2與OPNET 的剖析比較 ［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2010，19 （6）：90－95.］

［10］GAO Wenyu，WANG Jianxin，CHEN Songqiao.Extension of queue scheduling algorithm in NS2 ［J］.Journal of System Simulation，2006，18 （2）：521－525 （in Chinese）.［高文宇，王建新，陳松喬.網(wǎng)絡(luò)仿真軟件NS2中隊(duì)列調(diào)度算法的擴(kuò)展［J］.系統(tǒng)仿真學(xué)報(bào)，2006，18 （2）：521－525.］