張寶軍等
摘 要: 網(wǎng)絡(luò)拓?fù)涞慕ㄔO(shè)在以網(wǎng)絡(luò)平臺(tái)為依托的研究領(lǐng)域發(fā)揮著重要的作用,是相關(guān)研究得以展開(kāi)的基礎(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; 外部模塊訪問(wèn); 正向反饋優(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è)重要方面,研究?jī)?nèi)容主要是通過(guò)對(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汀?/p>
根據(jù)建模對(duì)象不同,網(wǎng)絡(luò)拓?fù)淠P涂煞譃樽灾斡蚣?jí)拓?fù)浜吐酚善骷?jí)拓?fù)鋬煞N[1]。在自治域(Autonomous System, AS)級(jí)拓?fù)淠P椭?,?jié)點(diǎn)代表自治系統(tǒng),邊代表自治系統(tǒng)之間的連接關(guān)系;在路由器級(jí)拓?fù)淠P椭?,?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í)兩種情況都要考慮。
長(zhǎng)期以來(lái)人們一直比較關(guān)注自治域級(jí)網(wǎng)絡(luò)拓?fù)浣?,其研究?jīng)歷了從經(jīng)驗(yàn)假設(shè)到客觀分析,從單純的計(jì)算機(jī)網(wǎng)絡(luò)研究到復(fù)雜系統(tǒng)特征化研究的過(guò)程[2],可分為以下三個(gè)階段。
⑴ 第一階段:基于經(jīng)驗(yàn)的隨機(jī)模型階段。
在研究初期,由于缺乏真實(shí)測(cè)量數(shù)據(jù)的支持,拓?fù)渲荒芙⒃谘芯咳藛T經(jīng)驗(yàn)假設(shè)的基礎(chǔ)上。最早的網(wǎng)絡(luò)拓?fù)淠P褪?988年Waxman提出的Waxman模型[3],這是一種隨機(jī)模型。隨機(jī)模型沒(méi)有反映網(wǎng)絡(luò)拓?fù)涞膶哟翁卣?,無(wú)法適用于大規(guī)模的網(wǎng)絡(luò)拓?fù)浣!?/p>
⑵ 第二階段:反映網(wǎng)絡(luò)層次特征的層次模型階段。
最早的層次模型是1996年Doar提出的Tiers(等級(jí))模型[4],該模型刻畫(huà)了Internet所具有的層次特征。之后不久,1997年,Zegura等人提出了另一種層次模型——Transit-Stub模型[5]。層次模型反映了網(wǎng)絡(luò)拓?fù)涞膶哟翁卣?,能夠用于?guī)?;W(wǎng)絡(luò)拓?fù)浣#遣](méi)有把握網(wǎng)絡(luò)拓?fù)渥陨淼囊?guī)律性,無(wú)法再現(xiàn)真實(shí)的網(wǎng)絡(luò)環(huán)境。
⑶ 第三階段:基于冪律的無(wú)標(biāo)度模型階段。
自1995年起,大規(guī)模的網(wǎng)絡(luò)拓?fù)錅y(cè)量工作開(kāi)始展開(kāi),為網(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ù)淠P?,即基于冪律的無(wú)標(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ù)浣K惴ù蠖蓟趦?yōu)先連接這樣的類似原理,所建模型存在不完備性問(wèn)題,對(duì)于這個(gè)問(wèn)題目前還無(wú)有效的解決辦法。
自治域級(jí)網(wǎng)絡(luò)拓?fù)溲芯咳缁鹑巛钡耐瑫r(shí),路由器級(jí)網(wǎng)絡(luò)拓?fù)涞难芯恳查_(kāi)始熱門(mén)起來(lái)。相對(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等人的研究指出,無(wú)標(biāo)度模型這種不考慮設(shè)計(jì)因素的生長(zhǎng)模型不適合于描述路由器級(jí)拓?fù)?,?yīng)該權(quán)衡資源消耗等因素,尋找具有優(yōu)化設(shè)計(jì)特點(diǎn)的生長(zhǎng)模型[20]。為此,Li等人基于設(shè)計(jì)優(yōu)化方法提出路由器級(jí)啟發(fā)式優(yōu)化模型(即熱模型)并制定了新的度量指標(biāo),這為路由器級(jí)拓?fù)浣V赋隽诵碌姆较騕17-18],實(shí)現(xiàn)了從基于隨機(jī)原則的無(wú)標(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ù)浣5淖詣?dòng)化、規(guī)?;蛷?fù)雜度上無(wú)法達(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ù)渖赡P蚏eaSE[21],該模型在自治域級(jí)拓?fù)洳捎肞FP算法,而在路由器級(jí)拓?fù)洳捎脽崮P退惴?,模型針?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ì)分析功能沒(méi)有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ù)渖赡P?,該模型總體方案設(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ù)?。其具體建模過(guò)程如下:
首先EMATG根據(jù)網(wǎng)絡(luò)拓?fù)渑渲梦募Q定自治域級(jí)拓?fù)湟?guī)模和PFP算法的主要參數(shù)、路由器級(jí)拓?fù)涞囊?guī)模和Hot Model算法的主要參數(shù);然后通過(guò)PFP算法確定AS節(jié)點(diǎn)間的連接關(guān)系,通過(guò)Hot Model算法確定路由器節(jié)點(diǎn)間的連接關(guān)系;接著按照Opnet EMA文件格式生成Opnet的em.c文件,經(jīng)過(guò)Opnet編譯器編譯運(yùn)行后生成nt.m網(wǎng)絡(luò)拓?fù)淠P?;最后將模型?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ò)模型文件。用戶可通過(guò)配置網(wǎng)絡(luò)拓?fù)渑渲梦募?lái)控制網(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語(yǔ)言的方式來(lái)描述網(wǎng)絡(luò)拓?fù)淠P?,在EMA文件中可以對(duì)網(wǎng)絡(luò)拓?fù)渲械膶?duì)象進(jìn)行描述,這些對(duì)象主要是節(jié)點(diǎn)對(duì)象和鏈路對(duì)象。EMA文件的主要工作是創(chuàng)建對(duì)象并設(shè)置對(duì)象的屬性。
通過(guò)將在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文件中最重要的部分,通過(guò)函數(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)系來(lái)創(chuàng)建EMA文本文件。自治域節(jié)點(diǎn)用子網(wǎng)對(duì)象描述,路由器、交換機(jī)等節(jié)點(diǎn)用節(jié)點(diǎn)對(duì)象描述,節(jié)點(diǎn)間連接關(guān)系則用鏈路對(duì)象來(lái)描述。EMA文本文件的創(chuàng)建就是創(chuàng)建對(duì)象、設(shè)置對(duì)象屬性的過(guò)程。
2.2 模型文件生成
EMA文本文件是類似C語(yǔ)言的網(wǎng)絡(luò)拓?fù)淠P兔枋稣Z(yǔ)言,其文件擴(kuò)展名為em.c,該文件需要用Opnet自帶的編譯器OPNET Console進(jìn)行編譯,成功編譯后將生成.x文件,在編譯器中運(yùn)行該.x文件將生成nt.m文件,該文件即為Opnet的網(wǎng)絡(luò)拓?fù)淠P臀募?,可直接?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)建過(guò)程中可以看出:首先,通過(guò)編程實(shí)現(xiàn)了自動(dòng)化的網(wǎng)絡(luò)拓?fù)浣#黄浯?,通過(guò)修改網(wǎng)絡(luò)配置文件,可以控制網(wǎng)絡(luò)的規(guī)模;最后,PFP算法和Hot Model算法本身體現(xiàn)了Internet網(wǎng)絡(luò)的規(guī)律性,基于這兩種算法生成拓?fù)渚哂泻芎玫姆抡嫘浴?/p>
下面通過(guò)簡(jiǎn)單的仿真測(cè)試來(lái)驗(yàn)證所生成拓?fù)淠P偷目捎眯浴y(cè)試方法:在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é)束語(yǔ)
本文基于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)建只是研究工作的開(kāi)始,要將各種網(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ù)淠P?,使得研發(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)曉惠,錢(qián)亞冠,周志敏.Internet拓?fù)浣Ec演化綜述[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