基于EMA的網(wǎng)絡(luò)拓?fù)渥詣?dòng)化建模

張寶軍等

摘 要： 網(wǎng)絡(luò)拓?fù)涞慕ㄔO(shè)在以網(wǎng)絡(luò)平臺(tái)為依托的研究領(lǐng)域發(fā)揮著重要的作用，是相關(guān)研究得以展開的基礎(chǔ)。將目前流行的兩種網(wǎng)絡(luò)拓?fù)渖伤惴ā蚍答亙?yōu)先和熱模型算法，與時(shí)下最強(qiáng)大網(wǎng)絡(luò)仿真工具OPNET相結(jié)合，給出了一種OPNET平臺(tái)上基于EMA的、規(guī)模可控的、仿真度較高的網(wǎng)絡(luò)拓?fù)渥詣?dòng)化建模方法。實(shí)驗(yàn)結(jié)果表明，該方法能夠更好地模擬真實(shí)網(wǎng)絡(luò)拓?fù)洵h(huán)境，達(dá)到網(wǎng)絡(luò)仿真的規(guī)模要求，滿足相關(guān)領(lǐng)域的研究需要。

關(guān)鍵詞： OPNET； 外部模塊訪問； 正向反饋優(yōu)先； 熱模型； 冪律

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）05-05-05

Abstract： The network topology generation plays an important role in those researches that rely on the network platform. It's the basis for outspreading researches. PFP and hot model， two popular network topology generation algorithms， are introduced. The algorithms are combined with the most powerful network simulation platform， the OPNET. A large scale and high simulation network topology automatic modeling method based on ARM is given. Experimental result shows that the network topology generated by the method can simulate the real network topology environment better， and meet the scale requirement of network simulation and correlative researches.

Key words： OPNET； EMA； PFP； hot model； power law

0 引言

網(wǎng)絡(luò)拓?fù)涞难芯恳恢笔蔷W(wǎng)絡(luò)研究的一個(gè)重要方面，研究內(nèi)容主要是通過對(duì)真實(shí)網(wǎng)絡(luò)拓?fù)涞姆治?，總結(jié)網(wǎng)絡(luò)拓?fù)涓鞴?jié)點(diǎn)分布和相互之間連接的規(guī)律性，設(shè)計(jì)網(wǎng)絡(luò)拓?fù)渖伤惴ǎ瑥亩鴦?chuàng)建高仿真的網(wǎng)絡(luò)拓?fù)淠Ｐ汀?/p>

根據(jù)建模對(duì)象不同，網(wǎng)絡(luò)拓?fù)淠Ｐ涂煞譃樽灾斡蚣?jí)拓?fù)浜吐酚善骷?jí)拓?fù)鋬煞N[1]。在自治域（Autonomous System， AS）級(jí)拓?fù)淠Ｐ椭?，?jié)點(diǎn)代表自治系統(tǒng)，邊代表自治系統(tǒng)之間的連接關(guān)系；在路由器級(jí)拓?fù)淠Ｐ椭?，?jié)點(diǎn)代表自治域內(nèi)的路由器，邊代表路由器之間的連接關(guān)系。

自治域級(jí)網(wǎng)絡(luò)拓?fù)涿枋龅氖歉咭粋€(gè)層次的網(wǎng)絡(luò)節(jié)點(diǎn)（AS）間的互聯(lián)，而路由器級(jí)拓?fù)涿枋龅氖且粋€(gè)自治域系統(tǒng)內(nèi)路由器節(jié)點(diǎn)間的連接關(guān)系。構(gòu)造Internet網(wǎng)絡(luò)拓?fù)鋾r(shí)兩種情況都要考慮。

長期以來人們一直比較關(guān)注自治域級(jí)網(wǎng)絡(luò)拓?fù)浣＃溲芯拷?jīng)歷了從經(jīng)驗(yàn)假設(shè)到客觀分析，從單純的計(jì)算機(jī)網(wǎng)絡(luò)研究到復(fù)雜系統(tǒng)特征化研究的過程[2]，可分為以下三個(gè)階段。

⑴ 第一階段：基于經(jīng)驗(yàn)的隨機(jī)模型階段。

在研究初期，由于缺乏真實(shí)測量數(shù)據(jù)的支持，拓?fù)渲荒芙⒃谘芯咳藛T經(jīng)驗(yàn)假設(shè)的基礎(chǔ)上。最早的網(wǎng)絡(luò)拓?fù)淠Ｐ褪?988年Waxman提出的Waxman模型[3]，這是一種隨機(jī)模型。隨機(jī)模型沒有反映網(wǎng)絡(luò)拓?fù)涞膶哟翁卣?，無法適用于大規(guī)模的網(wǎng)絡(luò)拓?fù)浣！?/p>

⑵ 第二階段：反映網(wǎng)絡(luò)層次特征的層次模型階段。

最早的層次模型是1996年Doar提出的Tiers（等級(jí)）模型[4]，該模型刻畫了Internet所具有的層次特征。之后不久，1997年，Zegura等人提出了另一種層次模型——Transit-Stub模型[5]。層次模型反映了網(wǎng)絡(luò)拓?fù)涞膶哟翁卣?，能夠用于?guī)?；W(wǎng)絡(luò)拓?fù)浣?，但是并沒有把握網(wǎng)絡(luò)拓?fù)渥陨淼囊?guī)律性，無法再現(xiàn)真實(shí)的網(wǎng)絡(luò)環(huán)境。

⑶ 第三階段：基于冪律的無標(biāo)度模型階段。

自1995年起，大規(guī)模的網(wǎng)絡(luò)拓?fù)錅y量工作開始展開，為網(wǎng)絡(luò)拓?fù)溲芯克鸭舜罅康臄?shù)據(jù)。這些數(shù)據(jù)為網(wǎng)絡(luò)拓?fù)湟?guī)律性的發(fā)現(xiàn)提供了依據(jù)。1999年，從大量網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)中，F(xiàn)aloutsos等人發(fā)現(xiàn)Internet拓?fù)浣Y(jié)構(gòu)存在冪律（power-law）[6]分布特性。隨著冪律分布特性的揭示，出現(xiàn)了能夠反映更大規(guī)模Internet網(wǎng)絡(luò)拓?fù)涞淖灾斡蚣?jí)拓?fù)淠Ｐ?，即基于冪律的無標(biāo)度模型，其中比較有代表性的有BA[7]，BRITE[8]，Inet[9]，GLP[10]，DP[11]，PFP[12-13]，GLRG[14]，CMU[15]，TANG[16]等。這些現(xiàn)有的自治域級(jí)拓?fù)浣Ｋ惴ù蠖蓟趦?yōu)先連接這樣的類似原理，所建模型存在不完備性問題，對(duì)于這個(gè)問題目前還無有效的解決辦法。

自治域級(jí)網(wǎng)絡(luò)拓?fù)溲芯咳缁鹑巛钡耐瑫r(shí)，路由器級(jí)網(wǎng)絡(luò)拓?fù)涞难芯恳查_始熱門起來。相對(duì)于自治域級(jí)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，路由器級(jí)拓?fù)涓蟪潭壬鲜艿骄W(wǎng)絡(luò)服務(wù)提供商（ISP）各自的技術(shù)水平和用戶需求等相關(guān)因素的影響[1]。已有研究成果[17-18]表明路由器級(jí)網(wǎng)絡(luò)拓?fù)渑c自治域級(jí)網(wǎng)絡(luò)拓?fù)浯嬖诓灰粯拥纳蓹C(jī)理，盡管Faloutsos等人[6]和Magoni 等人[19]驗(yàn)證了路由器級(jí)網(wǎng)絡(luò)拓?fù)渲型瑯哟嬖趦缏煞植继匦?，但是Fabrikant等人的研究指出，無標(biāo)度模型這種不考慮設(shè)計(jì)因素的生長模型不適合于描述路由器級(jí)拓?fù)洌瑧?yīng)該權(quán)衡資源消耗等因素，尋找具有優(yōu)化設(shè)計(jì)特點(diǎn)的生長模型[20]。為此，Li等人基于設(shè)計(jì)優(yōu)化方法提出路由器級(jí)啟發(fā)式優(yōu)化模型（即熱模型）并制定了新的度量指標(biāo)，這為路由器級(jí)拓?fù)浣Ｖ赋隽诵碌姆较騕17-18]，實(shí)現(xiàn)了從基于隨機(jī)原則的無標(biāo)度網(wǎng)絡(luò)模型到基于設(shè)計(jì)原則的全局優(yōu)化模型的轉(zhuǎn)變。

目前，計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)研究工作大多在網(wǎng)絡(luò)仿真平臺(tái)上進(jìn)行，而時(shí)下流行的網(wǎng)絡(luò)仿真軟件在網(wǎng)絡(luò)拓?fù)浣５淖詣?dòng)化、規(guī)?；蛷?fù)雜度上無法達(dá)到真實(shí)網(wǎng)絡(luò)環(huán)境的要求。另一方面，在諸多的拓?fù)渖伤惴ㄖ?，PFP算法和熱模型算法分別是AS級(jí)拓?fù)浜吐酚善骷?jí)拓?fù)涞牡湫痛?，?yīng)用最為廣泛，為此，2008年，Gamer等人設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)網(wǎng)絡(luò)拓?fù)渖赡Ｐ蚏eaSE[21]，該模型在自治域級(jí)拓?fù)洳捎肞FP算法，而在路由器級(jí)拓?fù)洳捎脽崮Ｐ退惴?，模型針?duì)Omnet++設(shè)計(jì)，生成符合Omnet++拓?fù)湮募袷降奈募?，?jīng)Omnet++導(dǎo)入后能產(chǎn)生接近真實(shí)網(wǎng)絡(luò)環(huán)境的拓?fù)??？紤]到Omnet++在網(wǎng)絡(luò)拓?fù)浠A(chǔ)上的后續(xù)仿真能力和統(tǒng)計(jì)分析功能沒有Opnet那么強(qiáng)大，以及Opnet在教育科研領(lǐng)域廣泛的用戶群體，本文基于Opnet的EMA拓?fù)渖杉夹g(shù)，結(jié)合PFP和熱模型算法，設(shè)計(jì)并實(shí)現(xiàn)了Opnet平臺(tái)上的網(wǎng)絡(luò)拓?fù)渥詣?dòng)化生成模型——EMATG。下面將對(duì)EMATG模型作詳盡的介紹。

1 總體方案設(shè)計(jì)

EMATG是一個(gè)在Opnet平臺(tái)上采用EMA技術(shù)的自動(dòng)化、規(guī)?；母叻抡婢W(wǎng)絡(luò)拓?fù)渖赡Ｐ?，該模型總體方案設(shè)計(jì)如圖1所示。

根據(jù)圖1，EMATG實(shí)現(xiàn)了自治域級(jí)和路由器級(jí)兩級(jí)拓?fù)?，頂層是基于PFP算法實(shí)現(xiàn)的自治域級(jí)拓?fù)?，每一個(gè)自治域系統(tǒng)內(nèi)則是一個(gè)基于Hot Model算法的路由器級(jí)拓?fù)洹Ｆ渚唧w建模過程如下：

首先EMATG根據(jù)網(wǎng)絡(luò)拓?fù)渑渲梦募Q定自治域級(jí)拓?fù)湟?guī)模和PFP算法的主要參數(shù)、路由器級(jí)拓?fù)涞囊?guī)模和Hot Model算法的主要參數(shù)；然后通過PFP算法確定AS節(jié)點(diǎn)間的連接關(guān)系，通過Hot Model算法確定路由器節(jié)點(diǎn)間的連接關(guān)系；接著按照Opnet EMA文件格式生成Opnet的em.c文件，經(jīng)過Opnet編譯器編譯運(yùn)行后生成nt.m網(wǎng)絡(luò)拓?fù)淠Ｐ停蛔詈髮⒛Ｐ蛯?dǎo)入Opnet，生成網(wǎng)絡(luò)拓?fù)鋱D。

[讀取網(wǎng)絡(luò)拓?fù)渑渲梦募[自治域級(jí)網(wǎng)絡(luò)拓?fù)湓O(shè)計(jì)

在整個(gè)設(shè)計(jì)方案中，EMATG以網(wǎng)絡(luò)拓?fù)渑渲梦募檩斎?，輸出EMA文件，剩下的工作由Opnet網(wǎng)絡(luò)仿真工具完成。EMATG所要做的工作是保證節(jié)點(diǎn)間的連接關(guān)系滿足PFP和Hot Model算法的要求，以及生成的EMA文件符合要求，能夠被Opnet編譯運(yùn)行，生成相應(yīng)的網(wǎng)絡(luò)模型文件。用戶可通過配置網(wǎng)絡(luò)拓?fù)渑渲梦募砜刂凭W(wǎng)絡(luò)規(guī)模及算法的效果。

2 OPNET網(wǎng)絡(luò)模型生成

PFP算法的實(shí)現(xiàn)可參考文獻(xiàn)[12-13]，Hot Model算法可參考文獻(xiàn)[17-18]，這里不再贅述。下面將基于EMA技術(shù)，生成Opnet平臺(tái)上的網(wǎng)絡(luò)拓?fù)鋱D。

2.1 EMA文件結(jié)構(gòu)

EMA是Opnet提供的一種文本建模方式，采用類似C語言的方式來描述網(wǎng)絡(luò)拓?fù)淠Ｐ?，在EMA文件中可以對(duì)網(wǎng)絡(luò)拓?fù)渲械膶?duì)象進(jìn)行描述，這些對(duì)象主要是節(jié)點(diǎn)對(duì)象和鏈路對(duì)象。EMA文件的主要工作是創(chuàng)建對(duì)象并設(shè)置對(duì)象的屬性。

通過將在Opnet平臺(tái)上手動(dòng)創(chuàng)建的網(wǎng)絡(luò)拓?fù)鋵?dǎo)出為EMA文件，并對(duì)多個(gè)EMA文件進(jìn)行比較分析，得到EMA文件的結(jié)構(gòu)如圖2所示。

[EMA對(duì)象數(shù)組聲明][創(chuàng)建EMA對(duì)象][設(shè)置EMA對(duì)象屬性][保存EMA模型到模型文件]

在Opnet網(wǎng)絡(luò)拓?fù)渲?，路由器、交換機(jī)、服務(wù)器和工作站等都是節(jié)點(diǎn)對(duì)象，而10BaseT和PPP_DS3為鏈路對(duì)象。設(shè)置EMA對(duì)象屬性是EMA文件中最重要的部分，通過函數(shù)Ema_Object_Attr_Set實(shí)現(xiàn)，以路由器節(jié)點(diǎn)為例，可以設(shè)置路由器節(jié)點(diǎn)的“名稱”、“節(jié)點(diǎn)模型類型”、“位置坐標(biāo)”、“圖標(biāo)類型”和“所屬子網(wǎng)”等屬性。

在充分了解EMA文件結(jié)構(gòu)的基礎(chǔ)上，結(jié)合前面利用算法生成的節(jié)點(diǎn)及節(jié)點(diǎn)間的連接關(guān)系來創(chuàng)建EMA文本文件。自治域節(jié)點(diǎn)用子網(wǎng)對(duì)象描述，路由器、交換機(jī)等節(jié)點(diǎn)用節(jié)點(diǎn)對(duì)象描述，節(jié)點(diǎn)間連接關(guān)系則用鏈路對(duì)象來描述。EMA文本文件的創(chuàng)建就是創(chuàng)建對(duì)象、設(shè)置對(duì)象屬性的過程。

2.2 模型文件生成

EMA文本文件是類似C語言的網(wǎng)絡(luò)拓?fù)淠Ｐ兔枋稣Z言，其文件擴(kuò)展名為em.c，該文件需要用Opnet自帶的編譯器OPNET Console進(jìn)行編譯，成功編譯后將生成.x文件，在編譯器中運(yùn)行該.x文件將生成nt.m文件，該文件即為Opnet的網(wǎng)絡(luò)拓?fù)淠Ｐ臀募?，可直接?dǎo)入Opnet得到對(duì)應(yīng)的網(wǎng)絡(luò)拓?fù)洹?/p>

⑶ 性能分析

至此，在Opnet平臺(tái)上創(chuàng)建網(wǎng)絡(luò)拓?fù)涞墓δ芤鸦緦?shí)現(xiàn)，采用PFP算法和Hot Model算法生成的網(wǎng)絡(luò)拓?fù)?，轉(zhuǎn)換成EMA文件格式后，經(jīng)編譯生成的網(wǎng)絡(luò)拓?fù)淠K文件nt.m已被成功導(dǎo)入Opnet平臺(tái)。從整個(gè)網(wǎng)絡(luò)拓?fù)涞膭?chuàng)建過程中可以看出：首先，通過編程實(shí)現(xiàn)了自動(dòng)化的網(wǎng)絡(luò)拓?fù)浣?；其次，通過修改網(wǎng)絡(luò)配置文件，可以控制網(wǎng)絡(luò)的規(guī)模；最后，PFP算法和Hot Model算法本身體現(xiàn)了Internet網(wǎng)絡(luò)的規(guī)律性，基于這兩種算法生成拓?fù)渚哂泻芎玫姆抡嫘浴?/p>

下面通過簡單的仿真測試來驗(yàn)證所生成拓?fù)淠Ｐ偷目捎眯?。測試方法：在Opnet平臺(tái)上，利用Opnet提供的仿真功能，對(duì)整個(gè)網(wǎng)絡(luò)的時(shí)延及圖7中HTTP Server_68的吞吐量進(jìn)行仿真，仿真結(jié)果如圖8所示。

從圖8可以看出，拓?fù)浞螼pnet規(guī)范，在Opnet中能夠仿真運(yùn)行。

4 結(jié)束語

本文基于Opnet EMA文本建模方式，采用PFP算法和Hot Model算法實(shí)現(xiàn)了Opnet平臺(tái)上的網(wǎng)絡(luò)拓?fù)浣?，該模型包括AS級(jí)和路由器級(jí)兩個(gè)級(jí)別，滿足建模自動(dòng)化、規(guī)?；男枨螅N近真實(shí)的互聯(lián)網(wǎng)拓?fù)洵h(huán)境。實(shí)驗(yàn)及仿真結(jié)果驗(yàn)證了所建模型的可用性。然而，網(wǎng)絡(luò)拓?fù)涞膭?chuàng)建只是研究工作的開始，要將各種網(wǎng)絡(luò)應(yīng)用和協(xié)議搬到該拓?fù)渲羞M(jìn)行仿真還需要做大量的工作，同時(shí)網(wǎng)絡(luò)拓?fù)溥€需進(jìn)一步完善，包括IP地址的分配、路由協(xié)議的配置、路由器、交換機(jī)的設(shè)置等，目前采用的還只是Opnet默認(rèn)配置，與真實(shí)網(wǎng)絡(luò)環(huán)境有一定的差距。我們研究的最終目標(biāo)是創(chuàng)建一個(gè)Opnet平臺(tái)上的高仿真的Internet拓?fù)淠Ｐ?，使得研發(fā)人員可利用Opnet強(qiáng)大的仿真功能，從事基于Internet的研究與應(yīng)用。參考文獻(xiàn)：

[1] 周苗，楊家海，劉洪波，吳建平.Internet網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報(bào)，

2009.20（1）：109-123

[2] 張宇，張宏莉，方濱興.Internet拓?fù)浣＞C述[J].軟件學(xué)報(bào)， 2004.15

（8）：1220-1226

[3] Waxman B. M. Routing of Multipoint Connections[J]. IEEE Journal

on Selected Areas in Communications，1988.6（9）：1617-1622

[4] Doar M. B. A Better Model for Generating Test Networks[C]. In：

Proc. of the GLOBECOM'96. London： IEEE，1996：86-93

[5] Zegura E. W.， Calvert K. L.， Donahoo M. J. A Quantitative

Comparison of Graph-Based Models for Internet Topology[J]. IEEE/ACM Trans. on Networking，1997.5（6）：770-783

[6] Faloutsos M.， Faloutsos P.， Faloutsos C. On Power-Law

Relationships of The Internet Topology[J]. ACM SIGCOMM Computer Communication Review，1999.29（4）：251-262

[7] Albert R.， Barabasi A. L. Topology of Evolving Networks： Local

Events and Universality[J]. Physical Review Letters，2000.85（24）：5234-5246

[8] Medina A.， Lakhina A.， Matta I.， Byers J. BRITE： An Approach to

Universal Topology Generation[C].In： Proc. of the MASCOTS 2001， Washington： IEEE Computer Society，2001：346-353

[9] Winick J.， Jamin S. Inet-3.0： Internet Topology Generator[M].

Technical Report， CSE-TR-456-02， Ann Arbor： University of Michigan，2002.

[10] Bu T.， Towsley D. On Distinguishing Between Internet Power

Law Topology Generators[C].In：Proc. of the IEEE INFOCOM 2002， Vol 2. New York： IEEE，2002：638-647

[11] Park S. T.， Pennock D. M.， Giles C. L. Comparing Static and

Dynamic Measurements and Models of the Internet's AS Topology[C]. In： Proc. of the IEEE INFOCOM， 2004

[12] Zhou S.， Mondragon R. J. Accurately Modeling the Internet

Topology[J]. Physical Review E，2004.70（6）：066108-066115

[13] Zhou S.， Zhang G. Q.， Zhang G. Q.， Zhuge Z. R. Towards a

Precise and Complete Internet Topology Generator[C]. In Proc. of ICCCAS，2006.3：1830-1834

[14] Aiello W.， Chung F.， Lu L. Y. A Random Graph Model for

Massive Graphs[C]. In： Proc. of the ACM STOC 2000， Portland： ACM Press，2000：171-180

[15] Palmer C. R.， Steffan J. G. Generating Network Topologies That

Obey Power Laws[C]. In： Proc. of the GLOBECOM 2000， Vol 1. San Francisco： IEEE，2000：434-438

[16] Sagy B.， Mira G.， Avishai W. An Incremental Super-Linear

Preferential Internet Topology Model[M]. In： Proc. of the Passive and Active Measurement Workshop （PAM），2004.

[17] Alderson D.， Li L.， Willinger W. Understanding Internet

Topology： Principles， Models and Validation[J]. ACM Trans. on Networking，2005.13（6）：1205-1218

[18] Doyle J. C.， Alderson D.， Li L.， Low S.， Roughan M.， Shalunov

S.， Tanaka R.， Willinger W. The "Robust Yet Fragile" Nature of the Internet[J]. Proc. of the National Academy of Sciences USA，2005.102（41）：14497-14502

[19] Magoni D.， Pansiot J. J. Internet Topology Modeler Based on

Map Sampling[C]. In： Proc. of the ISCC 2002， Taormina： IEEE，2002：1021-1027

[20] Fabrikant A.， Koutsoupias E.， Papadimitriou C. H. Heuristically

Optimized Trade-Offs： A New Paradigm for Power Laws in the Internet[C]. In： Proc. of the Int'l Colloquium on Automata， Languages and Programming （ICALP），2002.

[21] Gamer T.， Scharf M. Realistic Simulation Environments for

IP-based Networks[C]. Proceedings of the 1st international conference on Simulation tools and techniques for communications， networks and systems，2008.

[22] Zhou S.， Mondragon R. J. Towards Modeling the Internet

Topology： the Interactive Growth Model[J]. Teletraffic Science and Engineering，2003.5：121-130

[23] 關(guān)曉惠，錢亞冠，周志敏.Internet拓?fù)浣Ｅc演化綜述[J]. 電訊技術(shù)，

2011.51（11）：121-128

[24] Pastor-satorras R.， Vazquez A.， Vespignani A. Dynamical and

Correlation Properties of the Intemet[J]. Physical Review Letters，2001.87（25）：1-4

[25] Vazquez A.， Pastor-satorras R.， Vespignani A. Large-Scale

Topological and Dynamical Properties of the Internet[J]. Physical Review E，2002.65（6）：066130-066141

[26] Chen Q.， Chang H.， Govindan R.， et al. The Origin of Powerlaws

in Intemet Topologies Revisited[ C]. Proceedings of the Twenty-First Annual Joint Conference of the IEEE Computer and Commications. [S.l.]： IEEE，2002.2（1）：608-617