基于EMA的網絡拓撲自動化建模

張寶軍等

摘 要： 網絡拓撲的建設在以網絡平臺為依托的研究領域發揮著重要的作用，是相關研究得以展開的基礎。將目前流行的兩種網絡拓撲生成算法——正向反饋優先和熱模型算法，與時下最強大網絡仿真工具OPNET相結合，給出了一種OPNET平臺上基于EMA的、規模可控的、仿真度較高的網絡拓撲自動化建模方法。實驗結果表明，該方法能夠更好地模擬真實網絡拓撲環境，達到網絡仿真的規模要求，滿足相關領域的研究需要。

關鍵詞： OPNET； 外部模塊訪問； 正向反饋優先； 熱模型； 冪律

中圖分類號：TP312 文獻標志碼：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 引言

網絡拓撲的研究一直是網絡研究的一個重要方面，研究內容主要是通過對真實網絡拓撲的分析，總結網絡拓撲各節點分布和相互之間連接的規律性，設計網絡拓撲生成算法，從而創建高仿真的網絡拓撲模型。

根據建模對象不同，網絡拓撲模型可分為自治域級拓撲和路由器級拓撲兩種[1]。在自治域（Autonomous System， AS）級拓撲模型中，節點代表自治系統，邊代表自治系統之間的連接關系；在路由器級拓撲模型中，節點代表自治域內的路由器，邊代表路由器之間的連接關系。

自治域級網絡拓撲描述的是更高一個層次的網絡節點（AS）間的互聯，而路由器級拓撲描述的是一個自治域系統內路由器節點間的連接關系。構造Internet網絡拓撲時兩種情況都要考慮。

長期以來人們一直比較關注自治域級網絡拓撲建模，其研究經歷了從經驗假設到客觀分析，從單純的計算機網絡研究到復雜系統特征化研究的過程[2]，可分為以下三個階段。

⑴ 第一階段：基于經驗的隨機模型階段。

在研究初期，由于缺乏真實測量數據的支持，拓撲只能建立在研究人員經驗假設的基礎上。最早的網絡拓撲模型是1988年Waxman提出的Waxman模型[3]，這是一種隨機模型。隨機模型沒有反映網絡拓撲的層次特征，無法適用于大規模的網絡拓撲建模。

⑵ 第二階段：反映網絡層次特征的層次模型階段。

最早的層次模型是1996年Doar提出的Tiers（等級）模型[4]，該模型刻畫了Internet所具有的層次特征。之后不久，1997年，Zegura等人提出了另一種層次模型——Transit-Stub模型[5]。層次模型反映了網絡拓撲的層次特征，能夠用于規模化網絡拓撲建模，但是并沒有把握網絡拓撲自身的規律性，無法再現真實的網絡環境。

⑶ 第三階段：基于冪律的無標度模型階段。

自1995年起，大規模的網絡拓撲測量工作開始展開，為網絡拓撲研究搜集了大量的數據。這些數據為網絡拓撲規律性的發現提供了依據。1999年，從大量網絡拓撲數據中，Faloutsos等人發現Internet拓撲結構存在冪律（power-law）[6]分布特性。隨著冪律分布特性的揭示，出現了能夠反映更大規模Internet網絡拓撲的自治域級拓撲模型，即基于冪律的無標度模型，其中比較有代表性的有BA[7]，BRITE[8]，Inet[9]，GLP[10]，DP[11]，PFP[12-13]，GLRG[14]，CMU[15]，TANG[16]等。這些現有的自治域級拓撲建模算法大都基于優先連接這樣的類似原理，所建模型存在不完備性問題，對于這個問題目前還無有效的解決辦法。

自治域級網絡拓撲研究如火如荼的同時，路由器級網絡拓撲的研究也開始熱門起來。相對于自治域級網絡拓撲結構，路由器級拓撲更大程度上受到網絡服務提供商（ISP）各自的技術水平和用戶需求等相關因素的影響[1]。已有研究成果[17-18]表明路由器級網絡拓撲與自治域級網絡拓撲存在不一樣的生成機理，盡管Faloutsos等人[6]和Magoni 等人[19]驗證了路由器級網絡拓撲中同樣存在冪律分布特性，但是Fabrikant等人的研究指出，無標度模型這種不考慮設計因素的生長模型不適合于描述路由器級拓撲，應該權衡資源消耗等因素，尋找具有優化設計特點的生長模型[20]。為此，Li等人基于設計優化方法提出路由器級啟發式優化模型（即熱模型）并制定了新的度量指標，這為路由器級拓撲建模指出了新的方向[17-18]，實現了從基于隨機原則的無標度網絡模型到基于設計原則的全局優化模型的轉變。

目前，計算機網絡相關研究工作大多在網絡仿真平臺上進行，而時下流行的網絡仿真軟件在網絡拓撲建模的自動化、規模化和復雜度上無法達到真實網絡環境的要求。另一方面，在諸多的拓撲生成算法中，PFP算法和熱模型算法分別是AS級拓撲和路由器級拓撲的典型代表，應用最為廣泛，為此，2008年，Gamer等人設計并實現了一個網絡拓撲生成模型ReaSE[21]，該模型在自治域級拓撲采用PFP算法，而在路由器級拓撲采用熱模型算法，模型針對Omnet++設計，生成符合Omnet++拓撲文件格式的文件，經Omnet++導入后能產生接近真實網絡環境的拓撲。考慮到Omnet++在網絡拓撲基礎上的后續仿真能力和統計分析功能沒有Opnet那么強大，以及Opnet在教育科研領域廣泛的用戶群體，本文基于Opnet的EMA拓撲生成技術，結合PFP和熱模型算法，設計并實現了Opnet平臺上的網絡拓撲自動化生成模型——EMATG。下面將對EMATG模型作詳盡的介紹。

1 總體方案設計

EMATG是一個在Opnet平臺上采用EMA技術的自動化、規模化的高仿真網絡拓撲生成模型，該模型總體方案設計如圖1所示。

根據圖1，EMATG實現了自治域級和路由器級兩級拓撲，頂層是基于PFP算法實現的自治域級拓撲，每一個自治域系統內則是一個基于Hot Model算法的路由器級拓撲。其具體建模過程如下：

首先EMATG根據網絡拓撲配置文件決定自治域級拓撲規模和PFP算法的主要參數、路由器級拓撲的規模和Hot Model算法的主要參數；然后通過PFP算法確定AS節點間的連接關系，通過Hot Model算法確定路由器節點間的連接關系；接著按照Opnet EMA文件格式生成Opnet的em.c文件，經過Opnet編譯器編譯運行后生成nt.m網絡拓撲模型；最后將模型導入Opnet，生成網絡拓撲圖。

[讀取網絡拓撲配置文件][自治域級網絡拓撲設計

在整個設計方案中，EMATG以網絡拓撲配置文件為輸入，輸出EMA文件，剩下的工作由Opnet網絡仿真工具完成。EMATG所要做的工作是保證節點間的連接關系滿足PFP和Hot Model算法的要求，以及生成的EMA文件符合要求，能夠被Opnet編譯運行，生成相應的網絡模型文件。用戶可通過配置網絡拓撲配置文件來控制網絡規模及算法的效果。

2 OPNET網絡模型生成

PFP算法的實現可參考文獻[12-13]，Hot Model算法可參考文獻[17-18]，這里不再贅述。下面將基于EMA技術，生成Opnet平臺上的網絡拓撲圖。

2.1 EMA文件結構

EMA是Opnet提供的一種文本建模方式，采用類似C語言的方式來描述網絡拓撲模型，在EMA文件中可以對網絡拓撲中的對象進行描述，這些對象主要是節點對象和鏈路對象。EMA文件的主要工作是創建對象并設置對象的屬性。

通過將在Opnet平臺上手動創建的網絡拓撲導出為EMA文件，并對多個EMA文件進行比較分析，得到EMA文件的結構如圖2所示。

[EMA對象數組聲明][創建EMA對象][設置EMA對象屬性][保存EMA模型到模型文件]

在Opnet網絡拓撲中，路由器、交換機、服務器和工作站等都是節點對象，而10BaseT和PPP_DS3為鏈路對象。設置EMA對象屬性是EMA文件中最重要的部分，通過函數Ema_Object_Attr_Set實現，以路由器節點為例，可以設置路由器節點的“名稱”、“節點模型類型”、“位置坐標”、“圖標類型”和“所屬子網”等屬性。

在充分了解EMA文件結構的基礎上，結合前面利用算法生成的節點及節點間的連接關系來創建EMA文本文件。自治域節點用子網對象描述，路由器、交換機等節點用節點對象描述，節點間連接關系則用鏈路對象來描述。EMA文本文件的創建就是創建對象、設置對象屬性的過程。

2.2 模型文件生成

EMA文本文件是類似C語言的網絡拓撲模型描述語言，其文件擴展名為em.c，該文件需要用Opnet自帶的編譯器OPNET Console進行編譯，成功編譯后將生成.x文件，在編譯器中運行該.x文件將生成nt.m文件，該文件即為Opnet的網絡拓撲模型文件，可直接導入Opnet得到對應的網絡拓撲。

⑶ 性能分析

至此，在Opnet平臺上創建網絡拓撲的功能已基本實現，采用PFP算法和Hot Model算法生成的網絡拓撲，轉換成EMA文件格式后，經編譯生成的網絡拓撲模塊文件nt.m已被成功導入Opnet平臺。從整個網絡拓撲的創建過程中可以看出：首先，通過編程實現了自動化的網絡拓撲建模；其次，通過修改網絡配置文件，可以控制網絡的規模；最后，PFP算法和Hot Model算法本身體現了Internet網絡的規律性，基于這兩種算法生成拓撲具有很好的仿真性。

下面通過簡單的仿真測試來驗證所生成拓撲模型的可用性。測試方法：在Opnet平臺上，利用Opnet提供的仿真功能，對整個網絡的時延及圖7中HTTP Server_68的吞吐量進行仿真，仿真結果如圖8所示。

從圖8可以看出，拓撲符合Opnet規范，在Opnet中能夠仿真運行。

4 結束語

本文基于Opnet EMA文本建模方式，采用PFP算法和Hot Model算法實現了Opnet平臺上的網絡拓撲建模，該模型包括AS級和路由器級兩個級別，滿足建模自動化、規模化的需求，貼近真實的互聯網拓撲環境。實驗及仿真結果驗證了所建模型的可用性。然而，網絡拓撲的創建只是研究工作的開始，要將各種網絡應用和協議搬到該拓撲中進行仿真還需要做大量的工作，同時網絡拓撲還需進一步完善，包括IP地址的分配、路由協議的配置、路由器、交換機的設置等，目前采用的還只是Opnet默認配置，與真實網絡環境有一定的差距。我們研究的最終目標是創建一個Opnet平臺上的高仿真的Internet拓撲模型，使得研發人員可利用Opnet強大的仿真功能，從事基于Internet的研究與應用。參考文獻：

[1] 周苗，楊家海，劉洪波，吳建平.Internet網絡拓撲建模[J].軟件學報，

2009.20（1）：109-123

[2] 張宇，張宏莉，方濱興.Internet拓撲建模綜述[J].軟件學報， 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] 關曉惠，錢亞冠，周志敏.Internet拓撲建模與演化綜述[J]. 電訊技術，

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