网络拓扑发现课件

1第七章网络拓扑发现

27.1拓扑发现概述拓扑发现(TopologyDiscovery)是指发现网元（NetworkElement）并确定网元之间的互连关系，包括互连设备(如路由器、网桥、交换机等)、主机和子网。拓扑发现作为配置管理和故障管理中的一项重要功能，是网络管理的一个重要组成部分。拓扑发现生成的网络拓扑图(NetworkTopologyMap)可以帮助网络管理员掌握网络拓扑结构，迅速定位故障发生地点，确定故障影响的范围，还可以成为发现网元并调用其它管理功能模块的共同出发点。拓扑发现同时也是衡量一个商业网络管理系统成败的重要尺度，在整个网络管理系统的开发中占有相当重要的地位。3涉及到的5个问题(1)确定拓扑构造的网络层次及协议(2)确定网络拓扑信息的采集方法(3)确定收集信息方式(4)确定网络拓扑发现的目标及发现程度(5)确定拓扑发现算法的运行方式4(1)确定拓扑构造的网络层次及协议只有确定了网络的层次和协议，才能明确到底需要采集什么样的信息，才能使这项技术具有比较好的适应性。第二层（MAC）物理拓扑发现和第三层拓扑发现。第二层的拓扑发现方法着重于发现网络设备端口间的物理连接。

第三层的网络拓扑发现方法着重于发现路由设备间的逻辑连接关系。它发现的拓扑结构并不表示网络中设备的真正连接关系，而是“IP数据报转发”意义上的连接关系。

5(2)确定网络拓扑信息的采集方法被动监测技术在所有观测的网络都加入一个探测器，由它来采集信息，并发送到网络管理主机来形成网络的拓扑结构。优点：除了向管理主机递交各个网络的拓扑信息，不产生额外的流量。缺点：探测器被动收集信息，形成网络拓扑时间较长。放置探测器困难主动探测技术通过网络管理主机主动向所有管理网络发送探测包，并采集返回的信息，进行分析最终形成网络的拓扑。优点：能够比较快的形成整个网络的拓扑。缺点：需要产生的流量比较大，并且对于一个十分慢的网络不太适合。6(3)确定收集信息方式采用网络管理信息协议(如SNMP)网络上的设备十分繁杂，不是所有的设备都支持这些管理协议，而且需要对涉及到的网络逐个进行配置。采用通用的协议局限性较小，如基于ICMP等协议来实现的。一般来说所有的IP网络和设备都支持，可靠性比较高，且省去了大量的手工配置。7(4)确定网络拓扑发现的目标及发现程度网络拓扑发现的最终目标是得到一个快速、完整、正确和高效的网络拓扑发现算法或拓扑发现工具。快速：能够实时地发现网络拓扑的结构和变化情况，且保持数据的内部一致性；完整性：在出现最少错误概率的情况下尽可能多地发现一个特定网络内的大部分主机和路由器；正确性：算法应尽力保证拓扑发现结果正确，尽量不出或少出错误；高效性：算法不应消耗过多的网络资源。8(5)确定拓扑发现算法的运行方式分布式拓扑发现通过建立服务器和客户机之间的连接，在服务器端起动拓扑发现过程，将各个探测点处收集到的拓扑信息发送到服务器（？），然后在服务器（？）端对这些信息进行收集和分析，最后得到整个网络完整的拓扑结构。单点发现在一个位置发起并完成拓扑探测。9拓扑发现的重要意义模拟网络为模拟实际网络，分析网络性能、合理扩容和优化网络，必须先得到该网络的拓扑结构。网络优化网络拓扑信息可以帮助网络管理者确定是否需要增加新的路由器，当前硬件是否配置正确，并发现网络中的瓶颈所在和失败的链路，进行网络优化。用户接入方式选择网络拓扑信息可以帮助用户确定自身处于网络中的位置，从而决定服务器的位置以及选择哪一个网络服务提供商可以将网络时延最小化、可用带宽最大化。10拓扑发现的重要意义（续）研究拓扑敏感算法一些新的协议和算法可以在得到网络拓扑信息的基础上改善网络性能。确定镜像服务器的位置根据拓扑信息合理配置镜像服务器的位置以最大可能减少时延，解决瓶颈问题。实行网络服务管理例如：mail，ftp，web，snmp，dns。11拓扑发现的重要意义（续）统计数据的采集及关联分析网络战对于信息作战而言，获得敌方的网络拓扑及与拓扑相关的信息可以灵活有效地组织攻击。12拓扑发现的研究现状有许多研究机构和公司着力于发现网络拓扑结构的研究如CAIDA，NLANR，Jaspvi，GeoBoy，otter，skitter，MINC，HP的InternetMapping项目。大多数网络管理工具都具有拓扑发现的功能如HPOpenview，IBM’sTivoli等，它们大都依赖于简单网络管理协议（SNMP）这一标准协议。而SNMP并不是一种通用的协议，基于SNMP的拓扑发现受到权限的限制，没有权限便不能访问其支持的MIBII信息，也便无法进行拓扑发现。13NLANR(应用网络研究国家实验室)

NationalLaboratoryforAppliedNetworkResearch

14CAIDA(国际Internet数据分析合作组织)

cooperativeassociationforinternetdataanalysisUsingtheWalrusvisualisationtool

15CAIDA（2）16AgraphvisualisationshowingthetopologyofthecoreoftheInternetfrommid-January2000.17ThislargegraphshowstherouterlevelconnectivityoftheInternetasmeasuredbyHalBurchandBillCheswick'sInternetMappingProject.Theworkisbeingcommerciallydevelopedby

Lumeta.18Atopologymapofacorenetworkofamedium-sizedISP.ItwascreatedusinganautomaticnetworkdiscoverytoolcalledMercatordevelopedaspartoftheScanprojectbyRameshGovindan,AnoopReddyandcolleagues,attheInformationSciencesInstitute,USA.19AsimpledotmapofwirelessantennasintheUSA20Formoreinformation/atlas/topology.html21研究趋势以太网的规模越来越大，发现物理拓扑（即第二层拓扑，交换机、路由器与主机之间的连接关系）引起一些公司的注意Cisco开发的CDP（CiscoDiscoverProtocol）、Bay的（Network’sOptivityEnterprise）、Intel、Fluke（LanMapShot）等

Bell实验室、CarnegieMellon大学等IETF制定了物理拓扑的管理信息库（BridgeMIB）

22网络拓扑发现的难点发现网络拓扑是一项挑战性的工作，因为互联网是各种网络的集合体，这些网络不但设备、软件差异很大，而且可能被不同的组织所管理，他们的组织、运营、安全等措施互不相同。网络规模越来越大，而且变化非常快（特别是无线网络），更增加了拓扑发现的难度。23拓扑发现的基本原理和方法基于网络管理协议的拓扑发现包括第三层和第二层拓扑发现基于网络主动探测和测量的拓扑发现包括基于网络常用工具的方法（如ping，traceroute等）基于端到端组播测量的拓扑发现无线网络的拓扑发现247.2基于网络管理协议的拓扑发现目前大多数商业化的网管软件都是基于SNMP，借助网络设备中的代理，通过访问管理信息库（MIB）中的变量来实现网络管理功能（包括性能、故障、计费、配置、安全管理五个功能域）。MIB含有对路由表和转发表及接口的描述，因此使得拓扑构造成为可能，不但可以构造出网络层设备（路由器、网关）的连接关系，而且也可构造出链路层设备（网桥、交换机）的连接关系。25基于SNMP的网络层拓扑发现

MIB262728基于SNMP的网络层拓扑发现ifTable

——接口表，其中ifIndex（接口索引）、ifDesc（接口描述）、ifType（接口类型）、ifPhysAddress（接口的物理地址），可用来构造拓扑；ipForwarding

——1代表可转发数据（具网关功能），2代表不转发数据（不具有网关功能）；sysServices

——指示节点所提供的服务，若主机在第i层提供了服务，则Li对应相应的层数，sysServices的值为：m=sum{2^(Li-1)}，Li=1,2,3,4,7分别对应物理层，链路层，网络层，传输层，应用层。例如若sysServices的值为7，则它是路由器；IpNetToMediaTable——可以访问相连的终端设备的IP地址。29基于SNMP的网络层拓扑发现初始化网关队列，子网队列，连接队列；把缺省网关放入网关队列中；while（网关队列非空）{从网关队列中取出一个网关，为CurrentGateway；访问CurrentGateway路由表；把路由表中的各ipRouteNextHop不重复地放到网关队列中；把各ipRouteDest不重复地放到子网队列中；把CurrentGateway与各ipRouteNextHop的连接不重复地放到连接队列中；

if（ipRouteNextHop属于ipRouteDest子网）把ipRouteNextHop与ipRouteDest的连接放到连接队列中；

if（ipRouteNextHop与CurrentGateway的地址相同）把CurrentGateway与ipRouteDest的连接放到连接队列中；}307.2.2基于交换表信息的链路层拓扑发现局域网规模的逐渐庞大使得如何发现物理拓扑越来越引起了研究人员的注意，目前的方法大都基于网桥MIB数据（分组转发表信息）来推算网桥之间的连接关系，即发现物理拓扑。每个交换机都采用逆向学习算法，并运行了生成树协议（spanningtree，RFC1493），无环路。BridgeMIB中可能包含有所有可达节点的交换表，也可能仅包含部分可达节点的交换表，针对这两种情况分别说明。31基于完全表交换信息的拓扑发现令Sij为交换机Si的第j个端口，Aij

为Sij收到的数据帧的源MAC地址集（Si转发表的子集）。令a（b）为交换机a到节点b的转发端口。相互连接的交换机网络中的两种情况各交换机属于同一子网各交换机属于不同子网（留给大家思考）32基于完全表交换信息的拓扑发现-算法1发现节点：由ipAddrTable发现子网，由ipRouteTable发现路由器，由ipForwarding及有无BridgeMIB判断交换机。2发现边：若（u是所有节点集合）且，则Sij与Skl相连。若Sij是叶子端口（不与任何交换相连）且Aij包含路由器R的MAC地址，则Sij与路由器R相连。若存在交换机集SB，节点集SE，令有：，，有a(b)=a(c)，则S中在SB当中包含一个共享网段（集线器），使S中各节点互联。33例子：引理：如果且，则端口与端口直接相连接。347.3基于主动探测的拓扑发现利用网络上用来对Internet控制和管理的协议（如ICMP）以及其它服务（如DNS域名服务）提供的信息。通过测试网络端到端的性能（其中包含了内部网络结构，即拓扑的信息）所蕴涵的信息来构造。357.3.1基于ICMP的拓扑发现美国南加利福尼亚大学信息科学研究所SCAN研究组研究得到一个探测工具Mercator该工具采用类似于traceroute用跳数受限的UDP分组进行拓扑构造：

（1）初始集的选择:根据一个主机的地址来判断有效的网络地址，并假定相邻的网络地址有效，而且从测试主机自身开始，这样不需要预先构造探测地址集；

（2）源选路的路由器：单点探测可能会漏掉交叉链路，因此采用源选路的路由器，使探测分组从每个相邻的路由器都进行探测； （3）无效端口发送UDP分组:由于路由器可能会有多个接口，因此给路由器的无效端口发送UDP分组，如果返回的PortUnreachableICMP分组的源地址与探测的地址不同则认为是多端口路由器。367.3.1基于ICMP的拓扑发现利用ICMP进行网络拓扑发现的步骤如下：（1）确定探测点，在每个探测点确定临时地址组，选择时可根据已有的积累及网络地址分配的预先知识；（2）在每一探测点用ping逐个探测临时组中地址的存活性（如存活加入永久组），并用traceroute跟踪中间路由器，向无效端口发送UDP分组发现多端口路由器，由网络地址划分子网，相应信息存入对应链表中，同时根据子网地址扩充临时地址组。重复执行直至遍历完毕；（3）将各探测点的获得的链表进行综合，构造主干拓扑；（4）在子网内搜索可能存活的主机，构造子网拓扑。377.3.1基于ICMP的拓扑发现具有一定的普遍性，能在一定的程度上发现网络拓扑。能粗略的发现第三层拓扑。受网管人员干预，获得的信息很有限。搜索的时间太长。387.3.2基于端到端性能测试的拓扑推算通过测量不但可以获得端到端的性能（如时延、丢包率），而且能够推算出网络内部的性能，甚至网络内部拓扑结构。相比于单播测试而言，组播测试能够推算更多的内部关联信息。基本方法：基于端到端丢包的组播拓扑推算基于时延的组播拓扑推算397.4无线网络的拓扑发现无线网络拓扑发现比有线网络复杂的多对于有固定接入点的无线局域网，可通过SNMP访问MAC层、物理层的管理信息库MIB来构造拓扑。若采用了MobileIP协议，则可访问移动IPMIB来辅助拓扑发现。而对于无中心点的Adhoc网络，可采用路由协议来构造拓扑。目前adhoc网络的路由协议可分为两类：Proactive路由（表驱动路由）Reactive路由（按需路由）

407.4无线网络的拓扑发现Proactive路由（表驱动路由）OLSR（OptimizedLinkStateRoutingProtocol）,WRP（WirelessRoutingProtocol）每个节点连续学习拓扑，可获得整个网络的部分拓扑在拓扑快变时，更新拓扑信息的代价非常大，拓扑基本不变时又浪费很多资源Reactive路由（按需路由）AODV（AdHocOnDemandDistanceVector）,DSR（DynamicSourceRouting）该类协议基于查询－响应机制，如需要立即启动一个路由搜索进程缺点：对数据的时延较大这两类协议都不能及时有效地构造出节点之间的所有物理连接关系，另外节点的移动性导致链路频繁的更替。417.4无线网络的拓扑发现无线网络拓扑发现的一般方法：基于群首管理信息库的拓扑发现基于移动代理的拓扑发现基于分层树的分群机制的拓扑发现基于网状网的拓扑发现42基于群首管理信息库的拓扑发现W.Chen等人提出了adhoc网络管理协议ANMP（AdhocNetworkManagementProtocol）。该协议使用一组分布的节点集（或者称为群首，clusterhead）保持该节点及其邻居信息，采用分层的机制收集拓扑信息。群首节点因地理位置或连接情况动态选择，通过群首中的MIB收集拓扑信息。该方法的缺点在于维持群首MIB需要开销，而且节点的移动可能导致MIB过期，从而不能提供完整的链路信息。43基于移动代理的拓扑发现R.RoyChoudhury等人提出了基于移动代理的分布式拓扑发现策略。每个节点运行一个代理，周期性的收集拓扑信息，并将其分发到网络中的其它节点。该方法不能提供瞬时的网络拓扑，发现完整的网络拓扑需要很长的时间，并且需要分发很多消息，因而效率不高且消耗带宽。44基于分层树的分群机制的拓扑发现BudhadityaDeb等人提出了一种用于无线传感器网络（wirelessadhocsensornetworks）的采用分层树的分群响应的拓扑发现算法（TopDisc）。该方法基于无线通信媒体的广播性质（每个节点通过监听信道能知道在其通信范围内其它节点的存在），找出一组群首（clusterheader）节点，这些群首节点将其邻节点信息传给根结点（监控节点），大大减少了通信开销。分群方法的目标归于两点（1）寻找一个元素最少的群首集（集覆盖问题）（2）用群首集构造最小树，即对两个目标进行组合优化45基于网状网的拓扑发现RanveerChandra等人提出基于网状网（Mesh-based）的拓扑发现算法，该方法分为两步扩散阶段（Diffusionphase），协调（coordinator）节点广播拓扑请求消息，每个节点接收并重新广播这条消息后，构造本地邻居信息，更新相应的数据结构。收集阶段（Gatheringphase），所有节点向协调节点转发本地邻居信息。为保证算法的可靠性，每一个节点接收k个来自父节点的请求，重新广播它们。同时为了保证广播的稳健性，采用了改进的RTS/CTS机制。结果表明，该方法能在包含不稳定链路的情况下正常工作。461物理层网络拓扑发现方法发现途径AFTARPSTP流量方法交换机-地址转发表地址解析协议表ipNetToMediaTable(ARP表)生成树协议流量判断缺点完整性;snmp

snmp;适用于局域网完整性snmp;stp耗资源;snmp;运算繁471基于AFT的物理层拓扑发现:已有算法引理：如果且，则端口与端口直接相连接。482.通用单子网物理拓扑发现算法：流量判断第个端口接收到的流量为，发送的流量为。流量测量。a.若为hub，有进而有（1）b.若为哑交换机，有（2）492通用单子网物理拓扑发现算法：流量判断502通用单子网物理拓扑发现算法：算法描述将无向图看成一个控制节点是根的树，各叶节点逐渐向其父节点收缩，叶节点的上行端口连接到其父节点相应的下行端口上，吸收了叶节点的父节点进而为新的叶节点，逐渐向根节点所连的交换机收缩。当一个下行端口有多个叶节点时，就进行端口流量判断，看是由哑交换机还是由hub将其连在一起。512通用单子网物理拓扑发现算法：实施步骤在控制节点，依次向子网中各网元进行ping操作；首先将交换机、路由器及主机各列为一个集合，以及网元集合；列出网元的上行端口和下行端口集合；数据运算，最终可视化。522通用单子网物理拓扑发现算法：仿真532通用单子网物理拓扑发现算法：SNMP-MIBmib2-interface-ifTable-ifEntry-ifInOctets(..1.10):收mib2-interface-ifTable-ifEntry-ifOutOctets(..1.16):发mib2-dot1bridge-dot1dBasePortTable(..4):AFT542通用单子网物理拓扑发现算法:MIB访问实例

55IP层网络拓扑发现方法发现途径路由表

ARPDNS,OSPF,RIP

ICMP/UDP性能方法snmp-mib地址解析协议表域名解析路由协议主动探测丢包率,时延

缺点snmp;路由功能

适于局域网

权限;协议普及时间长;耗资源耗资源;运算繁567.5基于ICMP和UDP的拓扑发现实例网络拓扑探测的总体思想为使用不可达端口UDP得到目的地址的TTL值，并判断其是否是路由器上的外侧接口；如果是外测接口，则使用TTL值为目标地址TTL值减1的ICMP探测得到其内侧网关地址；用带记录路由选项的ICMP区分9跳内外侧子网；然后使用UDP得到外侧网关对应的内侧网关577.5基于ICMP和UDP的拓扑发现实例改进的网络拓扑探测的总体思想为使用不可达端口UDP得到目的地址的TTL值，并判断其是否是路由器上的外侧接口；使用TTL值为目标地址TTL值减1的ICMP探测得到其内侧网关地址；用子网区分算法区分外侧子网。

改进算法的优势不再发送记录路由ICMP包，节省了探测时间和网络资源；而且还解决了9跳以外连接不能确定的问题。

58几个术语（1）子网的网关探测包由探测发起方到达目标子网时需要经过的该子网中的路由器，子网中的其它路由器在此并不称为“子网的网关”。（2）子网的TTL值探测发起方到目标子网的网关的距离向量，即为使发送的IP包能到达该子网必须在IP包的TTL字段所设置的最小值，同样可定义主机的TTL值。59几个术语（3）路由器的内侧接口路由器逻辑上面对探测方的那个接口（IP地址），即探测包进入路由器的入口。其它接口则称为外侧接口。

607.5.1算法的几个关键技术1.由远及近探测通常使用的ping和

traceroute程序采用

由近及远探测。拓扑探测如图所示，A为探测方，需要探测F、G子网的情况。在A处以F为目标地址，TTL值依次置为1，2，3，4发送IP包，于是A依次收到由B，C，D，F回复的ICMP包，从而得到A到F支路的拓扑情况。同样探测G时也要发送4个IP包，A到D的支路又被探测一次，这样当网络规模较大时（如G子网含有许多主机）就会造成很大的资源浪费。61

前面算法不能区分9跳外同一路由器上的子网，子网区分算法。B1与C2，C3估算的掩码长度一定等于B1与C1估算的掩码长度，B1与D2，D3估算的掩码长度一定等于B1与D1估算的掩码长度，而只有B1与B2，B3估算的掩码长度既大于B1与C1估算的掩码长度，也大于B1与D1估算的掩码长度，利用此亲近关系可知B1，B2，B3属于同一子网。mb1c1=mb1c2

＜mbmb1d1=mb1d2

＜mbmb1b2≥mb

622.跳跃式IP探测根据实际网络特征，一般子网掩码设置都是前部分为连续的1后部分为连续的0，子网所能容纳的主机数则为2n-2个，由此特征可以提高探测效率。假如探得某IP地址X.Y.Z.4属于某一子网（判断属于同一子网的条件是几个IP地址探得的网关相同），那么可以初步判定子网掩码的低三位为0，因此知道X.Y.Z.5，X.Y.Z.6，X.Y.Z.7都属于此子网，可以直接跳过这几个地址，而继续探测IP地址X.Y.Z.8是否仍属于此子网。当某个子网含有大片连续IP地址时，由于避免了IP地址逐个加一去探测，可以大大提高探测速度和效率。633.多线程探测ICMP包的级别较低，传输时延较大，采用多线程技术对多个IP地址同时探测，从而大大提高探测速度，同时限制线程的数量以调整探测对网络造成的负担。多线程要解决的一个问题是对于收到的回复包如何判断是由哪个线程发送的探测包引起的，这需要在发送包中加入能够在回复包中返回的编号来解决。利用UDP首部中的长度信息作为编号，不同的探测包具有不同的长度。647.5.2拓扑发现算法描述网络拓扑探测的总体思想：使用UDP得到目的地址的TTL值，并判断其是否是路由器上的外侧接口；然后使用TTL值为目标地址TTL值减1的ICMP探测得到其内侧网关地址，若内侧网关还没有探测则使用新的线程去探测；得到内侧网关后使用跳跃式算法探测下一个地址直到得出目标地址所在子网的拓扑。若目的地址在9跳内则使用带记录路由选项的ICMP得到其外侧网关，同时使用延伸算法得到几个邻近子网的地址并开启新的线程探测，直到探测的跳数超过所设置的门限为止。657.6组播网拓扑发现实例IP组播强制网络在数据流分布树的分叉处进行信息包的复制，而不是由信源主机或服务器多次重复地发送相同的数据包。复制复制R1R3R4R5R6R2XBDCA多播组G多播组G多播组G667.7拓扑可视化拓扑可视化的关键就是为每一个网络节点分配坐标，然后将具有连接的网络节点用线连接就形成了网络拓扑图。一个网络节点就是一个IP地址，需要将属于同一子网的节点和路由器上的各个接口之间用线连接起来，而且这些节点和连线尽量不互相遮挡。67CAIDAPlankton项目对NLANR的WebCache分层拓扑图686970拓扑可视化算法举例一种按子网模块递归分配坐标，并使用矩形节点来简化计算的拓扑可视化方法。该子网中有些节点是像B、C、D

等只含一个IP地址的简单节点，有些则作为路由节点与其它子网相连接，将这些节点和其所连接的子网看成一个大的复杂节点，如子网A和子网E，这些节点内部结构又与当前子网类似，其占据空间的计算与当前子网相同，形成递归。71拓扑可视化算法举例计算出当前子网中所有节点所各自占据的空间，然后按均匀分配的原则将这些节点排列在矩形的四周，当前子网所占据的空间大小就是图中所示的虚线矩形大小。将每个节点底（内？）部中心与子网中心用线连接起来表示它们处于同一子网。为了使连线刚好连接到复杂节点的网关上，在复杂节点中分配坐标时需要把网关分配在整个子网矩形的底（内）部中央处。7273拓扑可视化算法举例74单点拓扑发现的比较方法发现

IP数发包数量多线程耗时(分)完整度正确度改进ping97379否约80不完整有错判改进tracert94277否约80不完整有错判基于UDP&ICMP97122是4.15基本完整无错判75分布式网络拓扑发现：综述单点网络拓扑发现：单点发现的网络拓扑都是树状的，而实际的网络是一个有环路、有交叉的网络；由于探测策略，单点发现的网络拓扑只扫描了一部分网络地址；单点拓扑发现将所有的流量和运算都加在了一台主机及其对应的链路上，造成局部重负载；有的网络设备很可能不支持探测所需的协议或命令，这样，从某些位置发起的单点探测就可能效果较差，或无法进行；单点拓扑发现的结果对某些连接的判断可能是不确切的。分布式网络拓扑发现：提高发现的快速性、准确性和完整性；利于实际的应用，比如，可以进行网络优化、智能路由等。76分布式拓扑（DNMAI）：实验室的测试网络77DNMAI上分布式拓扑发现的参数输入界面：78主控站得到的单点拓扑结果：79监控站5得到的单点拓扑结果：80