基于EMA的網(wǎng)絡(luò)拓?fù)渥詣踊?/h1>
2014-04-29 04:03張寶軍等
計算機時代 2014年5期 關(guān)鍵詞：冪律
張寶軍等
摘 要： 網(wǎng)絡(luò)拓?fù)涞慕ㄔO(shè)在以網(wǎng)絡(luò)平臺為依托的研究領(lǐng)域發(fā)揮著重要的作用，是相關(guān)研究得以展開的基礎(chǔ)。將目前流行的兩種網(wǎng)絡(luò)拓?fù)渖伤惴ā蚍答亙?yōu)先和熱模型算法，與時下最強大網(wǎng)絡(luò)仿真工具OPNET相結(jié)合，給出了一種OPNET平臺上基于EMA的、規(guī)?？煽氐?、仿真度較高的網(wǎng)絡(luò)拓?fù)渥詣踊７椒ā嶒灲Y(jié)果表明，該方法能夠更好地模擬真實網(wǎng)絡(luò)拓?fù)洵h(huán)境，達(dá)到網(wǎng)絡(luò)仿真的規(guī)模要求，滿足相關(guān)領(lǐng)域的研究需要。
關(guān)鍵詞： OPNET； 外部模塊訪問； 正向反饋優(yōu)先； 熱模型； 冪律
中圖分類號：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號：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ò)研究的一個重要方面，研究內(nèi)容主要是通過對真實網(wǎng)絡(luò)拓?fù)涞姆治?，總結(jié)網(wǎng)絡(luò)拓?fù)涓鞴?jié)點分布和相互之間連接的規(guī)律性，設(shè)計網(wǎng)絡(luò)拓?fù)渖伤惴?，從而?chuàng)建高仿真的網(wǎng)絡(luò)拓?fù)淠Ｐ汀?/p>
根據(jù)建模對象不同，網(wǎng)絡(luò)拓?fù)淠Ｐ涂煞譃樽灾斡蚣壨負(fù)浜吐酚善骷壨負(fù)鋬煞N[1]。在自治域（Autonomous System， AS）級拓?fù)淠Ｐ椭?，?jié)點代表自治系統(tǒng)，邊代表自治系統(tǒng)之間的連接關(guān)系；在路由器級拓?fù)淠Ｐ椭校?jié)點代表自治域內(nèi)的路由器，邊代表路由器之間的連接關(guān)系。
自治域級網(wǎng)絡(luò)拓?fù)涿枋龅氖歉咭粋€層次的網(wǎng)絡(luò)節(jié)點（AS）間的互聯(lián)，而路由器級拓?fù)涿枋龅氖且粋€自治域系統(tǒng)內(nèi)路由器節(jié)點間的連接關(guān)系。構(gòu)造Internet網(wǎng)絡(luò)拓?fù)鋾r兩種情況都要考慮。
長期以來人們一直比較關(guān)注自治域級網(wǎng)絡(luò)拓?fù)浣?，其研究?jīng)歷了從經(jīng)驗假設(shè)到客觀分析，從單純的計算機網(wǎng)絡(luò)研究到復(fù)雜系統(tǒng)特征化研究的過程[2]，可分為以下三個階段。
⑴ 第一階段：基于經(jīng)驗的隨機模型階段。
在研究初期，由于缺乏真實測量數(shù)據(jù)的支持，拓?fù)渲荒芙⒃谘芯咳藛T經(jīng)驗假設(shè)的基礎(chǔ)上。最早的網(wǎng)絡(luò)拓?fù)淠Ｐ褪?988年Waxman提出的Waxman模型[3]，這是一種隨機模型。隨機模型沒有反映網(wǎng)絡(luò)拓?fù)涞膶哟翁卣?，無法適用于大規(guī)模的網(wǎng)絡(luò)拓?fù)浣！?/p>
⑵ 第二階段：反映網(wǎng)絡(luò)層次特征的層次模型階段。
最早的層次模型是1996年Doar提出的Tiers（等級）模型[4]，該模型刻畫了Internet所具有的層次特征。之后不久，1997年，Zegura等人提出了另一種層次模型——Transit-Stub模型[5]。層次模型反映了網(wǎng)絡(luò)拓?fù)涞膶哟翁卣鳎軌蛴糜谝?guī)?；W(wǎng)絡(luò)拓?fù)浣?，但是并沒有把握網(wǎng)絡(luò)拓?fù)渥陨淼囊?guī)律性，無法再現(xiàn)真實的網(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ù)涞淖灾斡蚣壨負(fù)淠Ｐ?，即基于冪律的無標(biāo)度模型，其中比較有代表性的有BA[7]，BRITE[8]，Inet[9]，GLP[10]，DP[11]，PFP[12-13]，GLRG[14]，CMU[15]，TANG[16]等。這些現(xiàn)有的自治域級拓?fù)浣Ｋ惴ù蠖蓟趦?yōu)先連接這樣的類似原理，所建模型存在不完備性問題，對于這個問題目前還無有效的解決辦法。
自治域級網(wǎng)絡(luò)拓?fù)溲芯咳缁鹑巛钡耐瑫r，路由器級網(wǎng)絡(luò)拓?fù)涞难芯恳查_始熱門起來。相對于自治域級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，路由器級拓?fù)涓蟪潭壬鲜艿骄W(wǎng)絡(luò)服務(wù)提供商（ISP）各自的技術(shù)水平和用戶需求等相關(guān)因素的影響[1]。已有研究成果[17-18]表明路由器級網(wǎng)絡(luò)拓?fù)渑c自治域級網(wǎng)絡(luò)拓?fù)浯嬖诓灰粯拥纳蓹C理，盡管Faloutsos等人[6]和Magoni 等人[19]驗證了路由器級網(wǎng)絡(luò)拓?fù)渲型瑯哟嬖趦缏煞植继匦?，但是Fabrikant等人的研究指出，無標(biāo)度模型這種不考慮設(shè)計因素的生長模型不適合于描述路由器級拓?fù)?，?yīng)該權(quán)衡資源消耗等因素，尋找具有優(yōu)化設(shè)計特點的生長模型[20]。為此，Li等人基于設(shè)計優(yōu)化方法提出路由器級啟發(fā)式優(yōu)化模型（即熱模型）并制定了新的度量指標(biāo)，這為路由器級拓?fù)浣Ｖ赋隽诵碌姆较騕17-18]，實現(xiàn)了從基于隨機原則的無標(biāo)度網(wǎng)絡(luò)模型到基于設(shè)計原則的全局優(yōu)化模型的轉(zhuǎn)變。
目前，計算機網(wǎng)絡(luò)相關(guān)研究工作大多在網(wǎng)絡(luò)仿真平臺上進(jìn)行，而時下流行的網(wǎng)絡(luò)仿真軟件在網(wǎng)絡(luò)拓?fù)浣５淖詣踊?、?guī)?；蛷?fù)雜度上無法達(dá)到真實網(wǎng)絡(luò)環(huán)境的要求。另一方面，在諸多的拓?fù)渖伤惴ㄖ?，PFP算法和熱模型算法分別是AS級拓?fù)浜吐酚善骷壨負(fù)涞牡湫痛恚瑧?yīng)用最為廣泛，為此，2008年，Gamer等人設(shè)計并實現(xiàn)了一個網(wǎng)絡(luò)拓?fù)渖赡Ｐ蚏eaSE[21]，該模型在自治域級拓?fù)洳捎肞FP算法，而在路由器級拓?fù)洳捎脽崮Ｐ退惴?，模型針對Omnet++設(shè)計，生成符合Omnet++拓?fù)湮募袷降奈募?，?jīng)Omnet++導(dǎo)入后能產(chǎn)生接近真實網(wǎng)絡(luò)環(huán)境的拓?fù)??？紤]到Omnet++在網(wǎng)絡(luò)拓?fù)浠A(chǔ)上的后續(xù)仿真能力和統(tǒng)計分析功能沒有Opnet那么強大，以及Opnet在教育科研領(lǐng)域廣泛的用戶群體，本文基于Opnet的EMA拓?fù)渖杉夹g(shù)，結(jié)合PFP和熱模型算法，設(shè)計并實現(xiàn)了Opnet平臺上的網(wǎng)絡(luò)拓?fù)渥詣踊赡Ｐ汀狤MATG。下面將對EMATG模型作詳盡的介紹。
1 總體方案設(shè)計
EMATG是一個在Opnet平臺上采用EMA技術(shù)的自動化、規(guī)?；母叻抡婢W(wǎng)絡(luò)拓?fù)渖赡Ｐ?，該模型總體方案設(shè)計如圖1所示。
根據(jù)圖1，EMATG實現(xiàn)了自治域級和路由器級兩級拓?fù)?，頂層是基于PFP算法實現(xiàn)的自治域級拓?fù)洌恳粋€自治域系統(tǒng)內(nèi)則是一個基于Hot Model算法的路由器級拓?fù)?。其具體建模過程如下：
首先EMATG根據(jù)網(wǎng)絡(luò)拓?fù)渑渲梦募Q定自治域級拓?fù)湟?guī)模和PFP算法的主要參數(shù)、路由器級拓?fù)涞囊?guī)模和Hot Model算法的主要參數(shù)；然后通過PFP算法確定AS節(jié)點間的連接關(guān)系，通過Hot Model算法確定路由器節(jié)點間的連接關(guān)系；接著按照Opnet EMA文件格式生成Opnet的em.c文件，經(jīng)過Opnet編譯器編譯運行后生成nt.m網(wǎng)絡(luò)拓?fù)淠Ｐ停蛔詈髮⒛Ｐ蛯?dǎo)入Opnet，生成網(wǎng)絡(luò)拓?fù)鋱D。
[讀取網(wǎng)絡(luò)拓?fù)渑渲梦募[自治域級網(wǎng)絡(luò)拓?fù)湓O(shè)計
在整個設(shè)計方案中，EMATG以網(wǎng)絡(luò)拓?fù)渑渲梦募檩斎?，輸出EMA文件，剩下的工作由Opnet網(wǎng)絡(luò)仿真工具完成。EMATG所要做的工作是保證節(jié)點間的連接關(guān)系滿足PFP和Hot Model算法的要求，以及生成的EMA文件符合要求，能夠被Opnet編譯運行，生成相應(yīng)的網(wǎng)絡(luò)模型文件。用戶可通過配置網(wǎng)絡(luò)拓?fù)渑渲梦募砜刂凭W(wǎng)絡(luò)規(guī)模及算法的效果。
2 OPNET網(wǎng)絡(luò)模型生成
PFP算法的實現(xiàn)可參考文獻(xiàn)[12-13]，Hot Model算法可參考文獻(xiàn)[17-18]，這里不再贅述。下面將基于EMA技術(shù)，生成Opnet平臺上的網(wǎng)絡(luò)拓?fù)鋱D。
2.1 EMA文件結(jié)構(gòu)
EMA是Opnet提供的一種文本建模方式，采用類似C語言的方式來描述網(wǎng)絡(luò)拓?fù)淠Ｐ?，在EMA文件中可以對網(wǎng)絡(luò)拓?fù)渲械膶ο筮M(jìn)行描述，這些對象主要是節(jié)點對象和鏈路對象。EMA文件的主要工作是創(chuàng)建對象并設(shè)置對象的屬性。
通過將在Opnet平臺上手動創(chuàng)建的網(wǎng)絡(luò)拓?fù)鋵?dǎo)出為EMA文件，并對多個EMA文件進(jìn)行比較分析，得到EMA文件的結(jié)構(gòu)如圖2所示。
[EMA對象數(shù)組聲明][創(chuàng)建EMA對象][設(shè)置EMA對象屬性][保存EMA模型到模型文件]
在Opnet網(wǎng)絡(luò)拓?fù)渲校酚善?、交換機、服務(wù)器和工作站等都是節(jié)點對象，而10BaseT和PPP_DS3為鏈路對象。設(shè)置EMA對象屬性是EMA文件中最重要的部分，通過函數(shù)Ema_Object_Attr_Set實現(xiàn)，以路由器節(jié)點為例，可以設(shè)置路由器節(jié)點的“名稱”、“節(jié)點模型類型”、“位置坐標(biāo)”、“圖標(biāo)類型”和“所屬子網(wǎng)”等屬性。
在充分了解EMA文件結(jié)構(gòu)的基礎(chǔ)上，結(jié)合前面利用算法生成的節(jié)點及節(jié)點間的連接關(guān)系來創(chuàng)建EMA文本文件。自治域節(jié)點用子網(wǎng)對象描述，路由器、交換機等節(jié)點用節(jié)點對象描述，節(jié)點間連接關(guān)系則用鏈路對象來描述。EMA文本文件的創(chuàng)建就是創(chuàng)建對象、設(shè)置對象屬性的過程。
2.2 模型文件生成
EMA文本文件是類似C語言的網(wǎng)絡(luò)拓?fù)淠Ｐ兔枋稣Z言，其文件擴展名為em.c，該文件需要用Opnet自帶的編譯器OPNET Console進(jìn)行編譯，成功編譯后將生成.x文件，在編譯器中運行該.x文件將生成nt.m文件，該文件即為Opnet的網(wǎng)絡(luò)拓?fù)淠Ｐ臀募芍苯訉?dǎo)入Opnet得到對應(yīng)的網(wǎng)絡(luò)拓?fù)洹?/p>
⑶ 性能分析
至此，在Opnet平臺上創(chuàng)建網(wǎng)絡(luò)拓?fù)涞墓δ芤鸦緦崿F(xiàn)，采用PFP算法和Hot Model算法生成的網(wǎng)絡(luò)拓?fù)?，轉(zhuǎn)換成EMA文件格式后，經(jīng)編譯生成的網(wǎng)絡(luò)拓?fù)淠K文件nt.m已被成功導(dǎo)入Opnet平臺。從整個網(wǎng)絡(luò)拓?fù)涞膭?chuàng)建過程中可以看出：首先，通過編程實現(xiàn)了自動化的網(wǎng)絡(luò)拓?fù)浣?；其次，通過修改網(wǎng)絡(luò)配置文件，可以控制網(wǎng)絡(luò)的規(guī)模；最后，PFP算法和Hot Model算法本身體現(xiàn)了Internet網(wǎng)絡(luò)的規(guī)律性，基于這兩種算法生成拓?fù)渚哂泻芎玫姆抡嫘浴?/p>
下面通過簡單的仿真測試來驗證所生成拓?fù)淠Ｐ偷目捎眯?。測試方法：在Opnet平臺上，利用Opnet提供的仿真功能，對整個網(wǎng)絡(luò)的時延及圖7中HTTP Server_68的吞吐量進(jìn)行仿真，仿真結(jié)果如圖8所示。
從圖8可以看出，拓?fù)浞螼pnet規(guī)范，在Opnet中能夠仿真運行。
4 結(jié)束語
本文基于Opnet EMA文本建模方式，采用PFP算法和Hot Model算法實現(xiàn)了Opnet平臺上的網(wǎng)絡(luò)拓?fù)浣?，該模型包括AS級和路由器級兩個級別，滿足建模自動化、規(guī)?；男枨螅N近真實的互聯(lián)網(wǎng)拓?fù)洵h(huán)境。實驗及仿真結(jié)果驗證了所建模型的可用性。然而，網(wǎng)絡(luò)拓?fù)涞膭?chuàng)建只是研究工作的開始，要將各種網(wǎng)絡(luò)應(yīng)用和協(xié)議搬到該拓?fù)渲羞M(jìn)行仿真還需要做大量的工作，同時網(wǎng)絡(luò)拓?fù)溥€需進(jìn)一步完善，包括IP地址的分配、路由協(xié)議的配置、路由器、交換機的設(shè)置等，目前采用的還只是Opnet默認(rèn)配置，與真實網(wǎng)絡(luò)環(huán)境有一定的差距。我們研究的最終目標(biāo)是創(chuàng)建一個Opnet平臺上的高仿真的Internet拓?fù)淠Ｐ?，使得研發(fā)人員可利用Opnet強大的仿真功能，從事基于Internet的研究與應(yīng)用。參考文獻(xiàn)：
[1] 周苗，楊家海，劉洪波，吳建平.Internet網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報，
2009.20（1）：109-123
[2] 張宇，張宏莉，方濱興.Internet拓?fù)浣＞C述[J].軟件學(xué)報， 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
猜你喜歡
明代虛勞專著及專篇虛勞方藥的分布特性研究計算機應(yīng)用與軟件(2023年2期)2023-03-15 大數(shù)據(jù)時代下冪律分布在醫(yī)學(xué)領(lǐng)域中的應(yīng)用價值空軍軍醫(yī)大學(xué)學(xué)報(2020年2期)2020-05-11 基于冪律分布的房地產(chǎn)泡沫破裂風(fēng)險預(yù)警研究經(jīng)濟(jì)研究導(dǎo)刊(2018年32期)2018-12-21 計算機應(yīng)用與軟件(2018年1期)2018-02-27 在熱愛的事情上冒險雪花(2016年5期)2016-12-13 四川地區(qū)降水冪律指數(shù)研究高原山地氣象研究(2016年1期)2016-11-10 冪律流底泥的質(zhì)量輸移和流場浙江大學(xué)學(xué)報（工學(xué)版）(2016年9期)2016-06-05 對抗冪律意林原創(chuàng)版(2015年10期)2015-05-30 在熱愛的事情上冒險讀者·校園版(2015年22期)2015-05-14 冪律譜模型原子鐘鐘差仿真與噪聲類型辨識測繪科學(xué)與工程(2014年6期)2014-02-27
張寶軍等
摘 要： 網(wǎng)絡(luò)拓?fù)涞慕ㄔO(shè)在以網(wǎng)絡(luò)平臺為依托的研究領(lǐng)域發(fā)揮著重要的作用，是相關(guān)研究得以展開的基礎(chǔ)。將目前流行的兩種網(wǎng)絡(luò)拓?fù)渖伤惴ā蚍答亙?yōu)先和熱模型算法，與時下最強大網(wǎng)絡(luò)仿真工具OPNET相結(jié)合，給出了一種OPNET平臺上基于EMA的、規(guī)?？煽氐?、仿真度較高的網(wǎng)絡(luò)拓?fù)渥詣踊７椒ā嶒灲Y(jié)果表明，該方法能夠更好地模擬真實網(wǎng)絡(luò)拓?fù)洵h(huán)境，達(dá)到網(wǎng)絡(luò)仿真的規(guī)模要求，滿足相關(guān)領(lǐng)域的研究需要。
關(guān)鍵詞： OPNET； 外部模塊訪問； 正向反饋優(yōu)先； 熱模型； 冪律
中圖分類號：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號：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ò)研究的一個重要方面，研究內(nèi)容主要是通過對真實網(wǎng)絡(luò)拓?fù)涞姆治?，總結(jié)網(wǎng)絡(luò)拓?fù)涓鞴?jié)點分布和相互之間連接的規(guī)律性，設(shè)計網(wǎng)絡(luò)拓?fù)渖伤惴?，從而?chuàng)建高仿真的網(wǎng)絡(luò)拓?fù)淠Ｐ汀?/p>
根據(jù)建模對象不同，網(wǎng)絡(luò)拓?fù)淠Ｐ涂煞譃樽灾斡蚣壨負(fù)浜吐酚善骷壨負(fù)鋬煞N[1]。在自治域（Autonomous System， AS）級拓?fù)淠Ｐ椭?，?jié)點代表自治系統(tǒng)，邊代表自治系統(tǒng)之間的連接關(guān)系；在路由器級拓?fù)淠Ｐ椭校?jié)點代表自治域內(nèi)的路由器，邊代表路由器之間的連接關(guān)系。
自治域級網(wǎng)絡(luò)拓?fù)涿枋龅氖歉咭粋€層次的網(wǎng)絡(luò)節(jié)點（AS）間的互聯(lián)，而路由器級拓?fù)涿枋龅氖且粋€自治域系統(tǒng)內(nèi)路由器節(jié)點間的連接關(guān)系。構(gòu)造Internet網(wǎng)絡(luò)拓?fù)鋾r兩種情況都要考慮。
長期以來人們一直比較關(guān)注自治域級網(wǎng)絡(luò)拓?fù)浣?，其研究?jīng)歷了從經(jīng)驗假設(shè)到客觀分析，從單純的計算機網(wǎng)絡(luò)研究到復(fù)雜系統(tǒng)特征化研究的過程[2]，可分為以下三個階段。
⑴ 第一階段：基于經(jīng)驗的隨機模型階段。
在研究初期，由于缺乏真實測量數(shù)據(jù)的支持，拓?fù)渲荒芙⒃谘芯咳藛T經(jīng)驗假設(shè)的基礎(chǔ)上。最早的網(wǎng)絡(luò)拓?fù)淠Ｐ褪?988年Waxman提出的Waxman模型[3]，這是一種隨機模型。隨機模型沒有反映網(wǎng)絡(luò)拓?fù)涞膶哟翁卣?，無法適用于大規(guī)模的網(wǎng)絡(luò)拓?fù)浣！?/p>
⑵ 第二階段：反映網(wǎng)絡(luò)層次特征的層次模型階段。
最早的層次模型是1996年Doar提出的Tiers（等級）模型[4]，該模型刻畫了Internet所具有的層次特征。之后不久，1997年，Zegura等人提出了另一種層次模型——Transit-Stub模型[5]。層次模型反映了網(wǎng)絡(luò)拓?fù)涞膶哟翁卣鳎軌蛴糜谝?guī)?；W(wǎng)絡(luò)拓?fù)浣?，但是并沒有把握網(wǎng)絡(luò)拓?fù)渥陨淼囊?guī)律性，無法再現(xiàn)真實的網(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ù)涞淖灾斡蚣壨負(fù)淠Ｐ?，即基于冪律的無標(biāo)度模型，其中比較有代表性的有BA[7]，BRITE[8]，Inet[9]，GLP[10]，DP[11]，PFP[12-13]，GLRG[14]，CMU[15]，TANG[16]等。這些現(xiàn)有的自治域級拓?fù)浣Ｋ惴ù蠖蓟趦?yōu)先連接這樣的類似原理，所建模型存在不完備性問題，對于這個問題目前還無有效的解決辦法。
自治域級網(wǎng)絡(luò)拓?fù)溲芯咳缁鹑巛钡耐瑫r，路由器級網(wǎng)絡(luò)拓?fù)涞难芯恳查_始熱門起來。相對于自治域級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，路由器級拓?fù)涓蟪潭壬鲜艿骄W(wǎng)絡(luò)服務(wù)提供商（ISP）各自的技術(shù)水平和用戶需求等相關(guān)因素的影響[1]。已有研究成果[17-18]表明路由器級網(wǎng)絡(luò)拓?fù)渑c自治域級網(wǎng)絡(luò)拓?fù)浯嬖诓灰粯拥纳蓹C理，盡管Faloutsos等人[6]和Magoni 等人[19]驗證了路由器級網(wǎng)絡(luò)拓?fù)渲型瑯哟嬖趦缏煞植继匦?，但是Fabrikant等人的研究指出，無標(biāo)度模型這種不考慮設(shè)計因素的生長模型不適合于描述路由器級拓?fù)?，?yīng)該權(quán)衡資源消耗等因素，尋找具有優(yōu)化設(shè)計特點的生長模型[20]。為此，Li等人基于設(shè)計優(yōu)化方法提出路由器級啟發(fā)式優(yōu)化模型（即熱模型）并制定了新的度量指標(biāo)，這為路由器級拓?fù)浣Ｖ赋隽诵碌姆较騕17-18]，實現(xiàn)了從基于隨機原則的無標(biāo)度網(wǎng)絡(luò)模型到基于設(shè)計原則的全局優(yōu)化模型的轉(zhuǎn)變。
目前，計算機網(wǎng)絡(luò)相關(guān)研究工作大多在網(wǎng)絡(luò)仿真平臺上進(jìn)行，而時下流行的網(wǎng)絡(luò)仿真軟件在網(wǎng)絡(luò)拓?fù)浣５淖詣踊?、?guī)?；蛷?fù)雜度上無法達(dá)到真實網(wǎng)絡(luò)環(huán)境的要求。另一方面，在諸多的拓?fù)渖伤惴ㄖ?，PFP算法和熱模型算法分別是AS級拓?fù)浜吐酚善骷壨負(fù)涞牡湫痛恚瑧?yīng)用最為廣泛，為此，2008年，Gamer等人設(shè)計并實現(xiàn)了一個網(wǎng)絡(luò)拓?fù)渖赡Ｐ蚏eaSE[21]，該模型在自治域級拓?fù)洳捎肞FP算法，而在路由器級拓?fù)洳捎脽崮Ｐ退惴?，模型針對Omnet++設(shè)計，生成符合Omnet++拓?fù)湮募袷降奈募?，?jīng)Omnet++導(dǎo)入后能產(chǎn)生接近真實網(wǎng)絡(luò)環(huán)境的拓?fù)??？紤]到Omnet++在網(wǎng)絡(luò)拓?fù)浠A(chǔ)上的后續(xù)仿真能力和統(tǒng)計分析功能沒有Opnet那么強大，以及Opnet在教育科研領(lǐng)域廣泛的用戶群體，本文基于Opnet的EMA拓?fù)渖杉夹g(shù)，結(jié)合PFP和熱模型算法，設(shè)計并實現(xiàn)了Opnet平臺上的網(wǎng)絡(luò)拓?fù)渥詣踊赡Ｐ汀狤MATG。下面將對EMATG模型作詳盡的介紹。
1 總體方案設(shè)計
EMATG是一個在Opnet平臺上采用EMA技術(shù)的自動化、規(guī)?；母叻抡婢W(wǎng)絡(luò)拓?fù)渖赡Ｐ?，該模型總體方案設(shè)計如圖1所示。
根據(jù)圖1，EMATG實現(xiàn)了自治域級和路由器級兩級拓?fù)?，頂層是基于PFP算法實現(xiàn)的自治域級拓?fù)洌恳粋€自治域系統(tǒng)內(nèi)則是一個基于Hot Model算法的路由器級拓?fù)?。其具體建模過程如下：
首先EMATG根據(jù)網(wǎng)絡(luò)拓?fù)渑渲梦募Q定自治域級拓?fù)湟?guī)模和PFP算法的主要參數(shù)、路由器級拓?fù)涞囊?guī)模和Hot Model算法的主要參數(shù)；然后通過PFP算法確定AS節(jié)點間的連接關(guān)系，通過Hot Model算法確定路由器節(jié)點間的連接關(guān)系；接著按照Opnet EMA文件格式生成Opnet的em.c文件，經(jīng)過Opnet編譯器編譯運行后生成nt.m網(wǎng)絡(luò)拓?fù)淠Ｐ停蛔詈髮⒛Ｐ蛯?dǎo)入Opnet，生成網(wǎng)絡(luò)拓?fù)鋱D。
[讀取網(wǎng)絡(luò)拓?fù)渑渲梦募[自治域級網(wǎng)絡(luò)拓?fù)湓O(shè)計
在整個設(shè)計方案中，EMATG以網(wǎng)絡(luò)拓?fù)渑渲梦募檩斎?，輸出EMA文件，剩下的工作由Opnet網(wǎng)絡(luò)仿真工具完成。EMATG所要做的工作是保證節(jié)點間的連接關(guān)系滿足PFP和Hot Model算法的要求，以及生成的EMA文件符合要求，能夠被Opnet編譯運行，生成相應(yīng)的網(wǎng)絡(luò)模型文件。用戶可通過配置網(wǎng)絡(luò)拓?fù)渑渲梦募砜刂凭W(wǎng)絡(luò)規(guī)模及算法的效果。
2 OPNET網(wǎng)絡(luò)模型生成
PFP算法的實現(xiàn)可參考文獻(xiàn)[12-13]，Hot Model算法可參考文獻(xiàn)[17-18]，這里不再贅述。下面將基于EMA技術(shù)，生成Opnet平臺上的網(wǎng)絡(luò)拓?fù)鋱D。
2.1 EMA文件結(jié)構(gòu)
EMA是Opnet提供的一種文本建模方式，采用類似C語言的方式來描述網(wǎng)絡(luò)拓?fù)淠Ｐ?，在EMA文件中可以對網(wǎng)絡(luò)拓?fù)渲械膶ο筮M(jìn)行描述，這些對象主要是節(jié)點對象和鏈路對象。EMA文件的主要工作是創(chuàng)建對象并設(shè)置對象的屬性。
通過將在Opnet平臺上手動創(chuàng)建的網(wǎng)絡(luò)拓?fù)鋵?dǎo)出為EMA文件，并對多個EMA文件進(jìn)行比較分析，得到EMA文件的結(jié)構(gòu)如圖2所示。
[EMA對象數(shù)組聲明][創(chuàng)建EMA對象][設(shè)置EMA對象屬性][保存EMA模型到模型文件]
在Opnet網(wǎng)絡(luò)拓?fù)渲校酚善?、交換機、服務(wù)器和工作站等都是節(jié)點對象，而10BaseT和PPP_DS3為鏈路對象。設(shè)置EMA對象屬性是EMA文件中最重要的部分，通過函數(shù)Ema_Object_Attr_Set實現(xiàn)，以路由器節(jié)點為例，可以設(shè)置路由器節(jié)點的“名稱”、“節(jié)點模型類型”、“位置坐標(biāo)”、“圖標(biāo)類型”和“所屬子網(wǎng)”等屬性。
在充分了解EMA文件結(jié)構(gòu)的基礎(chǔ)上，結(jié)合前面利用算法生成的節(jié)點及節(jié)點間的連接關(guān)系來創(chuàng)建EMA文本文件。自治域節(jié)點用子網(wǎng)對象描述，路由器、交換機等節(jié)點用節(jié)點對象描述，節(jié)點間連接關(guān)系則用鏈路對象來描述。EMA文本文件的創(chuàng)建就是創(chuàng)建對象、設(shè)置對象屬性的過程。
2.2 模型文件生成
EMA文本文件是類似C語言的網(wǎng)絡(luò)拓?fù)淠Ｐ兔枋稣Z言，其文件擴展名為em.c，該文件需要用Opnet自帶的編譯器OPNET Console進(jìn)行編譯，成功編譯后將生成.x文件，在編譯器中運行該.x文件將生成nt.m文件，該文件即為Opnet的網(wǎng)絡(luò)拓?fù)淠Ｐ臀募芍苯訉?dǎo)入Opnet得到對應(yīng)的網(wǎng)絡(luò)拓?fù)洹?/p>
⑶ 性能分析
至此，在Opnet平臺上創(chuàng)建網(wǎng)絡(luò)拓?fù)涞墓δ芤鸦緦崿F(xiàn)，采用PFP算法和Hot Model算法生成的網(wǎng)絡(luò)拓?fù)?，轉(zhuǎn)換成EMA文件格式后，經(jīng)編譯生成的網(wǎng)絡(luò)拓?fù)淠K文件nt.m已被成功導(dǎo)入Opnet平臺。從整個網(wǎng)絡(luò)拓?fù)涞膭?chuàng)建過程中可以看出：首先，通過編程實現(xiàn)了自動化的網(wǎng)絡(luò)拓?fù)浣?；其次，通過修改網(wǎng)絡(luò)配置文件，可以控制網(wǎng)絡(luò)的規(guī)模；最后，PFP算法和Hot Model算法本身體現(xiàn)了Internet網(wǎng)絡(luò)的規(guī)律性，基于這兩種算法生成拓?fù)渚哂泻芎玫姆抡嫘浴?/p>
下面通過簡單的仿真測試來驗證所生成拓?fù)淠Ｐ偷目捎眯?。測試方法：在Opnet平臺上，利用Opnet提供的仿真功能，對整個網(wǎng)絡(luò)的時延及圖7中HTTP Server_68的吞吐量進(jìn)行仿真，仿真結(jié)果如圖8所示。
從圖8可以看出，拓?fù)浞螼pnet規(guī)范，在Opnet中能夠仿真運行。
4 結(jié)束語
本文基于Opnet EMA文本建模方式，采用PFP算法和Hot Model算法實現(xiàn)了Opnet平臺上的網(wǎng)絡(luò)拓?fù)浣?，該模型包括AS級和路由器級兩個級別，滿足建模自動化、規(guī)?；男枨螅N近真實的互聯(lián)網(wǎng)拓?fù)洵h(huán)境。實驗及仿真結(jié)果驗證了所建模型的可用性。然而，網(wǎng)絡(luò)拓?fù)涞膭?chuàng)建只是研究工作的開始，要將各種網(wǎng)絡(luò)應(yīng)用和協(xié)議搬到該拓?fù)渲羞M(jìn)行仿真還需要做大量的工作，同時網(wǎng)絡(luò)拓?fù)溥€需進(jìn)一步完善，包括IP地址的分配、路由協(xié)議的配置、路由器、交換機的設(shè)置等，目前采用的還只是Opnet默認(rèn)配置，與真實網(wǎng)絡(luò)環(huán)境有一定的差距。我們研究的最終目標(biāo)是創(chuàng)建一個Opnet平臺上的高仿真的Internet拓?fù)淠Ｐ?，使得研發(fā)人員可利用Opnet強大的仿真功能，從事基于Internet的研究與應(yīng)用。參考文獻(xiàn)：
[1] 周苗，楊家海，劉洪波，吳建平.Internet網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報，
2009.20（1）：109-123
[2] 張宇，張宏莉，方濱興.Internet拓?fù)浣＞C述[J].軟件學(xué)報， 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
猜你喜歡
計算機應(yīng)用與軟件(2023年2期)2023-03-15
空軍軍醫(yī)大學(xué)學(xué)報(2020年2期)2020-05-11
經(jīng)濟(jì)研究導(dǎo)刊(2018年32期)2018-12-21
雪花(2016年5期)2016-12-13
高原山地氣象研究(2016年1期)2016-11-10
浙江大學(xué)學(xué)報（工學(xué)版）(2016年9期)2016-06-05
意林原創(chuàng)版(2015年10期)2015-05-30
讀者·校園版(2015年22期)2015-05-14
測繪科學(xué)與工程(2014年6期)2014-02-27
