IP级网络拓扑测量技术的研究与实现

薛健等

摘要：对现有的常用的两种网络拓扑测量技术进行了分析研究，实现了基于traceroute技术的网络拓扑测量系统并用其测量了中国网络，通过与Iplane的测量结果对比评价了其可用性。首先讨论了基于SNMP协议的拓扑测量方法，并指出其优缺点。随后讨论了基于traceroute技术的拓扑测量方法，描述了基于traceroute技术的拓扑测量系统的设计构架和关键技术。最终利用拓扑测量系统测量了中国网络拓扑，然后将其测量结果同Iplane测量的中国网络拓扑进行复杂网络特征分析。通过特征对比发现，测量系统挖掘出的拓扑呈现出更显著的非相称性、更弱的聚集和更短的距离，证明了该系统的可用性。

关键词：SNMP协议； traceroute技术； 拓扑测量； 复杂网络

中图分类号：TP393 文献标识码：A文章编号：2095-2163（2014）01-0094-04

0引言

伴随着全球互联网络规模的不断扩大以及计算机软件和硬件技术的飞速发展，当今的互联网络已经变得愈加庞大和复杂，这一过程致使人们对网络本身将缺乏准确的表述和认识，并在一定程度上制约了对当前网络资源的有效利用，限制了网络技术的发展。为了深入了解当前全球网络，人们开始着手对网络特征进行研究。其中，网络拓扑的发现在整个网络特征研究中即占有十分重要的地位。对网络拓扑结构的深入研究与探讨，便于对整个网络进行宏观管理，同时对国家及地区的网络安全也起着至关重要的作用。

1IP级网络拓扑测量的常用方法

IP级网络拓扑测量是发现待测网络元素的IP地址间的互联情况。目前，IP级网络拓扑的测量主要有两种方式：基于SNMP协议[1]的测量方式和基于traceroute技术[2]的测量方式。

1.1基于SNMP协议的网络拓扑测量方法

SNMP协议（Simple Network Management Protocol，简单网络管理协议）包含在IETF（Internet Engineering Task Force， 互联网工程工作小组）定义的协议簇中，属于一种TCP/IP体系下的应用层协议。该协议使得网络管理者同代理之间传递管理指令和数据成为可能，已在很多的应用中被广泛采用。

1.1.1SNMP的管理模型

SNMP的管理模型[3]如图1所示。从体系结构上进行描述，主要包括三个关键元素。

（1）SNMP管理站

管理站通常可以理解为某个网络中的一台单机设备，网络管理员可以通过管理站同系统进行信息交互。其工作方式类似于C/S体系结构（Client/Server，客户端/服务器）下的客户端。管理站可以接收网络管理员或某种应用发出的操作请求，也可以接收来自系统代理的数据信息。

（2）SNMP管理代理

管理代理通常运行在某个共享网络中支持SNMP协议的部件上，这是一种可以应答来自SNMP管理站发出的请求的软件，其地位同C/S体系结构中的服务器极为相似。管理代理可以收到从SNMP管理站发出的SNMP请求，并根据需要对其进行响应，SNMP管理代理也可以通过异步发送的方式向管理站提供某些非请求数据。

（3）管理信息库

MIB（Management Information Base，管理信息库）是通过SNMP协议进行访问的数据库，所有支持SNMP协议的代理均保证能够应答对MIB信息库中的对象信息的查找请求；任何支持SNMP协议的网络管理站应该确保自身欲对代理的请求信息都应包含在MIB数据库的数据范围内。

1.1.2算法描述

算法可以通过SNMP请求获取目标网络中各个路由器中的路由表数据并进行综合分析，从而获得目标网络中路由器及子网之间的连接情况。

基于SNMP协议的拓扑测量算法过程如下[4]：

（1）任意选择待测网络中的某台路由器作为初始化的起点路由器，将其压入待发现路由队列。

（2）从队列中弹出队首路由器作为当前路由器。发送SNMP请求，读取当前路由器中的MIB数据库，从中提取其路由表。

（3）遍历MIB路由表。如果表中的记录为直接连接，则将目的子网掩码同目的IP地址进行与运算，从而获得当前路由器与这个目的网络的连接情况；如果记录为间接连结且与当前路由器直接连接的下一跳路由器不在待发现路由器队列中，则将下一跳路由器压入待发现路由器队列的队尾，同时将其压入已发现路由器队列队尾。

（4）若待发现队列为空，则终止算法。否则，从待发现路由器队列中弹出队首路由器并将其作为当前路由器，返回第二步继续执行。

1.1.3基于SNMP协议的网络拓扑测量方法的优缺点

基于SNMP协议的方法的优点是算法的测量结果通常较为完整和精确，同时还具有易于实现，测量过程开销较小的特点。而其缺点主要表现在其对带测量的网络要求支持SNMP协议，且普适性较弱。

1.2基于traceroute技术的网络拓扑测量方法

traceroute方式通过测量源向目标节点发起traceroute测量以探测各个主机和中间路由器IP接口间的连接。基于traceroute技术的测量可归类为基于ICMP协议的测量，而基于ICMP的测量方式具有限制少，适用性强的特点。但基于traceroute的网络拓扑测量属于主动测量，测量过程中需发送大量的ICMP数据包，这会增加网络的负担；同时实现起来相对基于SNMP的测量方式也更为复杂，程序的执行效率也比较低。即便如此，由于基于traceroute的测量方式在大规模网络拓扑发现中具有更强的普适性，因此在现代网络拓扑发现中得到广泛的应用。

1.2.1网络拓扑测量系统的整体设计

网络拓扑测量系统旨在获得并控制公开、可控的traceroute服务器向一个或多个目标IP同时发起traceroute测量，而将返回的结果整理成特定的形式后，再由后续的图特征分析模块对结果进行分析。网络拓扑测量系统的整体设计如图2所示。

1.2.2网络拓扑发现系统的基本构成

整个拓扑测量系统共含有四个主要模块，各个模块的功能和关键技术概括如下：

（1）服务器采集模块

全球公开的traceroute服务器Url列表往往由相关的组织机构或个人以网页的形式对外发布，如traceroute.org上就有公开的约1 000个分布于全球各地的traceroute服务器Url。服务器采集模块的功能就是从相应的traceroute服务器列表网页中获取全部有效的traceroute服务器Url，并将其存入数据库中。同时，服务器采集模块会定期检测服务器列表中Url的有效性，并及时更新数据库信息，以保证其时效性。

（2）测量数据采集模块

测量数据采集模块的功能是读取目标IP地址列表，利用服务器采集模块收集的traceroute服务器向所有目标IP发起traceroute测量，同时获取服务器端返回的结果，再提交给数据整理模块对结果进行分析整理。

（3）数据整理模块

数据整理模块利用Python的BeautifulSoup库和正则表达式，首先在返回的网页中定位traceroute结果所在的标签，然后在该标签中抽取出traceroute路径中每跳的IP地址，形成一条由源点服务器到目标IP的完整的IP级路径，并将其存入到与源服务器对应的文件中。通常网络拓扑的测量结果由多个文件组成，每个文件描述某个源traceroute服务器到其测量的所有目标IP的traceroute路径。

（4）拓扑分析模块

拓扑分析模块可以对最终获得的拓扑图进行显示或复杂网络特征提取。通常拓扑图的显示可以依靠现有的软件，如Ciada[5]的Otter。拓扑图的分析采用复杂网络特征提取的方法来分析大规模网络的真实特征，寻找其结构、动力学和功能的内在规律。2测量系统的测量结果分析

考虑利用网络拓扑测量系统发现中国的IP级网络拓扑，然后从华盛顿大学的Iplane服务测量的全球拓扑中提取中国网络拓扑，并将其结果同测量系统发现的结果进行复杂网络特征分析。通过特征对比表明了测量系统的可用性。

首先，从Iplane上获取其测量的全球拓扑，将这个网络拓扑命名为IPLTopo。然后，利用GeoIP从Iplane的目标IP集中筛选出所有位于中国的IP地址，形成一个中国目标IP集CNTarget。随后，利用拓扑测量系统以CNTarget为目标进行测量，获取系统测量的全球拓扑TmpTopo。最终，利用数据整理模块从TmpTopo和IPLTopo中分别提取出中国的网络拓扑。其中，Iplane测量的中国拓扑称为IplaneTopo，系统测量的中国拓扑称为MyTopo。MyTopo与IplaneTopo的统计特征如表1所示。网络拓扑是一种无权无向图，设链接数为m，节点数为n。

2.1平均节点度

平均节点度用来表示无向连通图的疏密程度，通常用k来表示，其中k=2m/n。由表1可以看出IplaneTopo的k值更大，表明Iplane发现的拓扑图更加密集。这是由于MyTopo的测量源点更为丰富，决定了其可发现网络中的大部分低密度的节点，并使得所有节点中低密度节点的比例很高，由此导致其平均节点度偏低。而IplaneTopo相对较少的测量源点更多地却只能发现介数[6]较高的高度节点，使得结果的平均节点度更高。

2.2节点度分布

当图为非对称时，A为负数，表示低度节点与高度节点互联的情况出现得较为频繁；反之若图是对称的，则A为正数。由图4中的A值可以看出，MyTopo较IplaneTopo不相称性更加显著。这就表明网络拓扑测量系统发现了一部分度数较高的节点同很多度数较低节点相连接的情况，相应部分网络通常是用来给终端提供网络接入的边缘子网络。薛健，等：IP级网络拓扑测量技术的研究与实现

2.4聚集

在一个无向图中，通常用一个节点的相邻节点的链接数除以k（k-1）/2来计算度数为k的节点的局部聚集c。其中用c来表示c的均值，可以用该形式作为一种度量来描绘小世界[9]的现象。表示图的传递性的T也可以作为另一种表述图聚集性的单位，即用其表示当节点v1与节点v2，v3分别连接，则v2和v3两节点也相连的概率。通过图4可以看出，IplaneTopo的两个聚集特征均强于MyTopo，这点同之前发现的IplaneTopo的k较大、高度节点比例较大的特征相吻合。

2.5距离分布

在无向图中，通常表示任选图中任意两个节点且两者最短距离为d的概率时，用P（d）来描述。由于P（d）的概率密度函数类似于高斯分布，因此可用均值d和方差σ来对其分布进行表述。d的最大值dmax用来表示图的直径。由图4可以看出，MyTopo的三个值均比IplaneTopo的小，这是由于MyTopo的拓扑规模较IplaneTopo的更大，其中包括了更多的网络节点以及链接，从而使得图中任意两点间包含更加丰富的路径，且具更多的捷径。

3结束语

本文分析了现有的两种网络拓扑测量技术—基于SNMP协议的网络拓扑测量方法和基于traceroute技术的网络拓扑测量方法。首先，描述SNMP方法的管理模型及算法实现，指出了其适用范围较小，不适合大规模网络拓扑测量的缺点；然后介绍了基于traceroute技术的网络拓扑测量系统整体架构及各个模块的主要功能。随后，利用拓扑测量系统测量了中国网络拓扑，并将其测量结果同Iplane测量的中国网络拓扑进行复杂网络特征对比。通过对比发现，测量系统挖掘出的拓扑更加完整精确，证明了该系统具有一定的代表性和可用性。

当然，系统的设计也存在着许多不足，主要有两点。一是系统目前只能在一台机器上采取串行的方式运行，每个测量周期时间均较长。可以考虑采取分布式测量的方式并发运行系统进行测量，其后再将各自的结果进行整合。如此则一个测量周期的时间可以大幅缩短。二是为了获得更为全面的网络拓扑信息，可以考虑将系统的测量结果同其它的拓扑发现项目的测量成果进行合并，如caida的skitter[10]、DIMES等。这就使得测量结果更加完整，节省了主动测量的开销，同时又进一步缩短了测量周期。

参考文献：

[1]胡延平，王连杰，刘武，等. 基于ICMP的网络性能分析[J]. 计算机工程与设计，2003（4）：30-32.

[2]CHAN S H G. Traceroute-based topology inference without network coordinate estimation[C]//Proceedings of the Symposium on Information and Network Security of ICC 2008， 2008，5：300-391.

[3]杨安义，朱华清，王继龙.一种改进的基于SNMP的网络拓扑发现算法及实现[J]. 计算机应用， 2007（10）： 2412-2413， 2419.

[4]刘琳琳. 网络拓扑发现技术的研究和实现[D].西安：西安电子科技大学，2006：25-35.

[5]BROIDO A， CLAFFY K. Internet topology： Connectivity of IP graphs. SPIE International symposium on Convergence of IT and Communication[C]//Society of Photo-Optical Instrumentation Engineers， Denver， CO.2001：172-187.

[6]GOH K I， KAHNG B， KIM D. Universal behavior of load distribution in scale-free networks[J]. Physical Review Letters， 2001，87（27）：278-701.

[7]FALOUTSOS M， FALOUTSOS P， FALOUTSOS C. On power-law relationships of the internet topology[J].SIGCOMM Computer Communication Review， 1999，29：140-259.

[8]NEWMAN M E J. Structure and function of complex networks[J]. SIAM Review. 2003，45（2）：167-256.

[9]WATTS D J， STROGATZ S H. Collective dynamics of 'small-world' networks[J].Nature， 1998，393：439-450.

[10]张君，赵海，康敏. Skitter与Ark探测架构下AS级Internet拓扑分析[J]. 计算机科学， 2010（11）：38-40.