网络拓扑快速发现方法分析范文

网络拓扑结构研究对自治域协议安全分析、网络提供商（ISP）优化网络性能和网络安全管理意义重大。网络拓扑发现根据路由等网络元素存储的转发路径信息或网络主动测量获取的逐跳路径信息，对网络拓扑结构进行获取和分析。网络拓扑发现方法分为基于路由转发表、基于简单网络管理协议（SNMP）和管理信息库（MIB）信息以及基于因特网控制报文协议（ICMP）3种路径探测分析方法。基于路由转发表的方法利用边界网关协议（BGP）和开放式最短路径优先协议（OSPF）等路由协议，对自治域间和自治域内进行网络拓扑发现。该方法优点是速度快以及网络负载小，缺点是发现范围有限，范围仅取决于获取路由转发表的网络范围；基于SNMP和MIB信息的方法是通过SNMP访问路由器、交换机或网桥中的MIB库，通过MIB库中的IP路由表、接口表及其他信息分析网络拓扑结构。该方法优点是实现简单、速度快且准确率高，缺点是MIB库的访问权限难以获取，无法对整个互联网进行网络拓扑发现。基于ICMP的路径探测分析方法一般使用回送请求和回送应答，通过存活时间（TTL）设置，对互联网拓扑路径进行发现，通常包含地址集构造探测、存活主机探测、路径和时延信息探测以及拓扑结构生成与显示4个阶段。该方法优点是探测地址可灵活选择以及不依赖路由器或交换机的访问权限，缺点是网络负载大且速度慢。上述3种网络拓扑发现方法各有优缺点。由于互联网地址规模庞大、自治域间和自治域内路由协议不同以及众多网络元素访问权限获取难度大，因此对互联网网络拓扑发现主要采用基于ICMP的网络拓扑发现方法。随着互联网网络拓扑结构研究的不断深入，发现了互联网网络拓扑结构的各种特性，如幂率特性、鲁棒且脆弱性和聚集特性［4］等，以及网络拓扑结构的不同度量指标（节点度分布、聚集系数、介数、核数和平均路径长度）等其他特性。利用上述网络拓扑结构特性可优化拓扑结构发现方法，提高拓扑结构发现效率，降低正常网络流量的扰动。鉴于ICMP的网络拓扑发现方法存在注入网络数据量大和时效不高等问题，将互联网结构特性与网络拓扑发现方法结合，提出了一种基于路径前缀匹配和双向探测的网络拓扑发现方法，从而降低了注入网络的流量负载，有效提高了网络拓扑发现的时间效率。

1路径探测

Traceroute是最早利用ICMP进行报文传输路径探测的工具，由VanJacobson在1989年开发［5］。其原理是发送报文TTL递增的用户数据报协议（UDP）报文，在探测报文从源端到目的端的传送路径中每经过一个路由其报文TTL值自动减1，当报文TTL值为0时，路由器向源端返回报文TTL超时的报文，当到达目的端时，由于UDP端口选择较大（＞1024）的目的端口，将返回端口不可达报文。因此设置首个探测报文TTL值为1，后续探测报文TTL值逐次加1，可根据返回的TTL超时报文和目的端返回的端口不可达报文中IP地址，获取源端到目的端的网络路径信息。

Skitter是由加利福尼亚大学互联网应用数据分析中心（CAIDA）开发的分布式网络测量工具，在美国、英国、加拿大和法国等国家分别部署了24个测量点。基于传输控制协议（TCP）报文实现Traceroute，使用常用端口可确保报文到达目的端时通过防火墙的过滤规则。24个测量点共用由971080个IPv4地址构成的目标地址集，每3d完成一次对地址集的路径及报文往返时间（RTT）的测量循环。Mercator与Skitter类似，采用分布式测量方法对大规模网络的拓扑结构和链路时延进行测量。主要区别：Mercator采用启发式地址集随机生成机制，可自适应构造探测地址集，而不依赖于解析BGP路由表和域名解析服务（DNS）数据库等手段。Mercator通过改进Traceroute实现2个目标：1）任意位置部署；2）无需额外输入，仅依赖有限TTL值探测报文，但Mercator启发式地址生成机制可能产生较大的探测流量。Rocketfuel针对ISP网络拓扑结构进行发现和构造，采用直接探测机制和路由器接口聚合机制以提高拓扑结构发现和构造效率。直接探测机制利用BGP路由表对经过ISP的探测路径进行筛选，减少了探测地址和路径数量。路由器接口聚合机制可根据探测路径中路由接口特征，识别相同路由器的不同接口并聚合为唯一的路由器地址，从而提高拓扑结构发现的准确性和效率。以上方法分别针对基于ICMP的网络拓扑发现的不同方面，解决了分布式网络拓扑发现、启发式地址集构造和路由器接口聚合等问题。对于每个测量点，注入网络数据量大和时间效率低仍是影响互联网网络拓扑发现的重点问题。本文根据互联网网络结构特点，改进了互联网网络拓扑发现方法，从而降低了探测数据流量并提高了时间效率。

2双向探测

基于ICMP的网络拓扑发现方法普遍采用TTL单向增长Traceroute方法，对测量点到目标网络设备的网络路径进行测量，如图1所示。其中，TTL－x为探测端TTL为x的探测报文；ICMP－TE为路由丢弃TTL超时报文时的响应报文；ICMP－DU为目标网络地址的目标端口不可达响应报文。探测端向目标网络设备发送TTL由1开始，以1为步长递增的TCP，UDP或ICMP报文。当TTL＝i的探测报文发送后，等待接收路由器Ri的超时返回报文或目标网络设备的端口不可达报文，并记录路径第i跳的路由接口地址以及报文RTT或目标网络设备报文往返时间。若接收时间超时，则对TTL＝i路由地址重新探测。连续3次探测失败后，则认为该路由为匿名路由，设置该路由接口地址为NULL并对TTL＝i＋1的路由地址继续进行探测。若连续3个路由均无法探测成功，则认为该目标网络设备无法到达，放弃该网络设备的路径探测。按照目前Traceroute方法对多个IP地址进行测量时，由于互联网网络结构的聚集特点，路径中大量路由节点将会重复探测。图2给出了网络聚集结构特点，当从探测点s1到目标网络设备d1，d2和d3进行测量时，路由器R1将会在每次测量中进行探测。由于互联网网络规模庞大，对整个互联网网络拓扑结构的发现和测量的工作量将是巨大的和重复的，故增加了探测数据流量和时间代价。针对互联网网络拓扑结构特点以及网络拓扑发现方法重复探测率高的问题，提出了双向探测的网络拓扑结构发现方法。

3前缀匹配哈希表与TTL切割线

在双向探测Traceroute方法TTL递减过程中，需要每次对返回的超时报文地址进行查表，其结果决定是否继续递减探测。前缀匹配表的结构对网络拓扑发现发送的探测流量和时间效率产生较大影响，应从查询速度和表的大小2方面考虑，使用哈希表能较好地满足以上2项要求。探测端负责维护1个哈希表组，分别以每个TTL值建立1个哈希表，第i个哈希表为从探测端出发第i跳的常见路由地址及其前i－1跳的路径信息。随着TTL的增加，路由器地址将以指数级增加。为了控制哈希表规模，当TTL＝i的路由地址在哈希表查询失败时，该地址和路径前缀信息不插入哈希表，而插入待哈希列表。利用定期扫描待哈希列表对哈希表进行更新，从而确保命中率以及哈希表规模可控。根据文献，互联网作为小世界网络，其节点平均距离是19个连接，因此取中间值10作为初始TTL切割线，分别建立TTL＝1～TTL＝10的10个哈希表。探测过程中不断扫描待哈希列表对哈希表更新，对10个哈希表的命中率进行分析，将命中率最高的TTL值作为分割线，对小于分割线的TTL段和大于分割线的TTL段进行递减和递增探测。

4试验验证

网络拓扑结构发现方法的评价标准分为完备性、时间效率、网络负载和准确性4方面。其中，完备性指拓扑发现可能获取的网络覆盖范围是否对所有网络设备进行发现；时间效率从网络拓扑结构发现所需时间衡量方法优劣性；网络负载指网络探测过程中对网络流量的影响大小；准确性针对网络拓扑发现结果与真实网络的误差进行分析。为了对基于ICMP的双向网络拓扑发现方法的网络负载、时间效率和准确性进行分析，本文对中国教育网的所有网段利用ICMPping进行扫描获取探测地址集，共获得活跃的主机地址10713个，针对该地址集分别使用传统Traceroute和双向探测Traceroute方法进行试验对比。传统Traceroute方法以TTL＝1递增探测，双向探测Traceroute方法以TTL＝10为初始值，哈希表大小设为100，目标地址集为中国教育网内活跃的主机中随机抽取不同规模的10个地址集，其探测结果从完备性、时间效率、网络负载和准确4方面对比。1）完备性双向探测Traceroute方法仅针对探测过程进行改进，未涉及改进探测地址集的生成技术。因此，从完备性角度，该方法与传统Traceroute方法相同。2）时间效率从探测地址集随机抽取1000，2000，…，10000个地址建立不同规模的探测地址集10个，探测地址集完成探测所需时间如图4所示。由图4可见，双向探测与传统Traceroute方法相比，降低了探测时间，且在一定规模的探测地址集内，随地址集规模的增大，降低探测时间的程度也随之增加。3）网络负载网络拓扑发现探测所需流量是网络拓扑发现的一个重要因素，探测过程应尽可能降低正常网络业务流量的干扰。利用上述10个探测地址集，对探测过程中的发包数进行统计，如图5所示。由图5可见，双向探测方法注入网络的数据流量较传统Traceroute方法较少，故降低了对正常网络业务数据流量的影响。4）准确性由于难以获取实际网络拓扑结构，本文仅对双向探测和传统Traceroute方法的准确性进行对比，以获取目标网络地址完全路径的比例为参考标准，在一定程度上可反映网络拓扑发现方法的准确性。利用上述10个探测地址集，其中最后一跳能够到达目标网络设备IP地址的数量比例如表1所示。由表1可见，在地址集中目标网络设备的探测结果中，获取完全路径的目标网络设备约为59％。因对中国教育网全部网段ping扫描需持续约30h，而教育网中活跃主机的IP地址在一定时间范围内会发生变化，因此不能获得地址集中所有IP地址的网络路径。从准确性角度，双向探测方法与传统Traceroute方法差别不大，均能获得活跃主机的网络路径信息。

5结束语

目前，基于ICMP的网络拓扑发现方法是互联网网络拓扑结构发现的主要方法，利用ICMP对互联网网络结构发现的各项目和工具均存在注入网络数据流量大和时间效率低的问题。本文使用TTL双向探测和前缀匹配哈希表对传统TTL单向递增的Traceroute方法进行改进，对中国教育网中活跃主机进行了扫描和探测。试验表明，双向探测的网络拓扑结构发现方法能够减少正常网络业务数据流量的扰动，并减少互联网拓扑结构发现所需时间。

作者：王志钊 陆余良 杨国正 单位：合肥电子工程学院网络系