楊國玲，王曉鋒，毛 力

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

0 引 言

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

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

1 拓撲折疊算法

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

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

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

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

定義4 a表示主機抽象系數(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é)點度數(shù)為0；（4）－（8）計算路由節(jié)點度數(shù)；（9）－（25）遞歸刪除拓撲中度為1的路由節(jié)點，并把其所帶的主機節(jié)點歸并到與之相連的另一個路由節(jié)點上，然后再重新計算度數(shù)，直到所有節(jié)點的度數(shù)都不為1。

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

圖1 部分原始拓撲

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

圖2 遞歸刪除算法之后的拓撲

1.2 主機抽象算法

算法具體描述如下：

（1）procedure host abstraction

（2） for each Vido

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

（4） end for

（5）end procedure

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

針對圖2，若取a 為4，則圖2 經(jīng)過主機抽象算法后，變?yōu)閳D3的拓撲。

圖3 主機抽象之后的拓撲

2 拓撲折疊后鏈路的失真分析及補償

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

2.1 排隊時延和丟包率的失真分析及補償

基于經(jīng)典的DropTail隊列管理算法來分析。原始拓撲的相關(guān)變量定義如下：

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

L（t）：F 在t時刻隊列字節(jié)長度；

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

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

F（t）：t時刻流入隊列F 的流量速率；

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

Tmax：緩沖隊列的最大長度。

同理定義拓撲折疊后的相關(guān)變量L′（t），B′，F(xiàn)′（t），Q′（t），T′max。由HFTF算法可知，拓撲折疊之后主機數(shù)量變?yōu)樵瓉淼?／a，這會導(dǎo)致流入拓撲的流量速率也變?yōu)樵瓉淼?／a，則流入每個路由器隊列的流量速率也應(yīng)為1／a，即

為了保證模擬結(jié)果的真實性，這里令拓撲折疊后的L的帶寬、緩沖隊列的最大長度均為原來的1／a （下面會分析在此條件下丟包率以及排隊時延的真實性），即

原始拓撲的丟包率p（t）為

t時刻的隊列長度與丟包率滿足如下關(guān)系

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

拓撲折疊后的丟包率p′（t）為

拓撲折疊后的L′（t）和p′（t）的關(guān)系為

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

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

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

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

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

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

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

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

D：鏈路L的傳播時延。

假設(shè)數(shù)據(jù)包從m 節(jié)點傳到n節(jié)點，在原始拓撲中所經(jīng)過的鏈路為L1，L2，…，Li，…，在拓撲折疊后的拓撲中所經(jīng)過的鏈路為L1′，L2′，…，Lj′，…，則在原始拓撲中的數(shù)據(jù)包時延為

拓撲折疊后的數(shù)據(jù)包時延為 （D′為拓撲折疊后鏈路的傳播時延）

因為拓撲折疊過后會導(dǎo)致數(shù)據(jù)包時延降低 （經(jīng)過的節(jié)點和鏈路變少），此時要保證模擬結(jié)果的真實性，需在m 到n的鏈路上加上一個延遲補償Δd，其值為

由2.1分析可知，在拓撲折疊前后

即在拓撲折疊后剩余節(jié)點的排隊時延和在原始拓撲中的排隊時延相等。由HFTF算法可知：刪除的路由節(jié)點都是邊緣節(jié)點，而邊緣節(jié)點的擁塞程度通常不高，其排隊時延可以忽略不計，則式 （14）可以寫成

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

3 實驗驗證

為了驗證 HFTF 算法的有效性，本文采用基于NS2［9，10］的Slammer蠕蟲進行模擬實驗，網(wǎng)絡(luò)拓撲采用3組分別有50，100，150個路由節(jié)點的拓撲模型 （把拓撲中度為1的路由節(jié)點設(shè)為邊界路由器，每個邊界路由器連接64個主機節(jié)點，并將這些主機全部設(shè)為弱點主機），抽象系數(shù)a的取值為4。

3.1 拓撲折疊前后的規(guī)模比較

由圖4可以看出3組拓撲在拓撲折疊前后的規(guī)模對比：對50個路由節(jié)點，原始拓撲中節(jié)點數(shù)量是2290，折疊后為575，規(guī)模減少了74.89%；對100個路由節(jié)點，拓撲折疊前后的節(jié)點個數(shù)分別是4260和1071，減少了74.86%；對150個路由節(jié)點，折疊前后的節(jié)點個數(shù)分別為6870、1741，減少了74.66%。由此可以看出，此算法可以在很大程度上縮減網(wǎng)絡(luò)拓撲的規(guī)模。

圖4 拓撲在折疊前后規(guī)模比較

3.2 拓撲折疊前后模擬時間的比較

由圖5可以看出，3 組拓撲在折疊前后運行時間的對比：對于50 個路由節(jié)點，折疊前后的模擬時間分別為578s、14s，降低了97.58%；對100 個路由節(jié)點，折疊前后的模擬時間分別是4171s、79s，降低了98.11%；對150個路由節(jié)點，折疊前后的模擬時間分別是5721s和124s，降低了97.83%。由此可以看出，此算法可以縮短模擬運行時間97%以上。

圖5 拓撲在折疊前后模擬時間比較

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

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

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

圖6 蠕蟲模擬在拓撲折疊前后的真實性比較

4 結(jié)束語

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

［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］.高技術(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）.［張兆心，杜躍進，王克，等.基于焦點折疊的網(wǎng)絡(luò)模擬拓撲抽象模型 ［J］.通信學(xué)報，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)鷺.基于主機節(jié)點刪減的網(wǎng)絡(luò)蠕蟲模擬方法研究 ［J］.計算機工程與設(shè)計，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ù)的拓撲抽象算法 ［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ò)模擬中拓撲抽象算法的研究［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］.計算機系統(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中隊列調(diào)度算法的擴展［J］.系統(tǒng)仿真學(xué)報，2006，18 （2）：521－525.］