基于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