网络拓扑发现课件.ppt

1、1第七章第七章 网络拓扑发现网络拓扑发现 27.1 拓扑发现概述拓扑发现概述n拓扑发现拓扑发现(Topology Discovery)是指发现网元（是指发现网元（Network Element）并确定网元之间的互连关系，包括互连设备）并确定网元之间的互连关系，包括互连设备(如路由如路由器、网桥、交换机等器、网桥、交换机等)、主机和子网。、主机和子网。n拓扑发现作为配置管理和故障管理中的一项重要功能，是网络拓扑发现作为配置管理和故障管理中的一项重要功能，是网络管理的一个重要组成部分。管理的一个重要组成部分。拓扑发现生成的网络拓扑图拓扑发现生成的网络拓扑图(Network Topology Map

2、)可以帮助网可以帮助网络管理员掌握网络拓扑结构，迅速定位故障发生地点，确定故障络管理员掌握网络拓扑结构，迅速定位故障发生地点，确定故障影响的范围，还可以成为发现网元并调用其它管理功能模块的共影响的范围，还可以成为发现网元并调用其它管理功能模块的共同出发点。同出发点。拓扑发现同时也是衡量一个商业网络管理系统成败的重要尺度，拓扑发现同时也是衡量一个商业网络管理系统成败的重要尺度，在整个网络管理系统的开发中占有相当重要的地位。在整个网络管理系统的开发中占有相当重要的地位。3涉及到的涉及到的5个问题个问题n(1)确定拓扑构造的网络层次及协议确定拓扑构造的网络层次及协议n(2)确定网络拓扑信息的采集方法

3、确定网络拓扑信息的采集方法n(3)确定收集信息方式确定收集信息方式n(4)确定网络拓扑发现的目标及发现程度确定网络拓扑发现的目标及发现程度n(5)确定拓扑发现算法的运行方式确定拓扑发现算法的运行方式4(1)确定拓扑构造的网络层次及协议确定拓扑构造的网络层次及协议n只有确定了网络的层次和协议，才能明确到底需要采集什么样只有确定了网络的层次和协议，才能明确到底需要采集什么样的信息，才能使这项技术具有比较好的适应性。的信息，才能使这项技术具有比较好的适应性。n第二层（第二层（MAC）物理拓扑发现和第三层拓扑发现。）物理拓扑发现和第三层拓扑发现。n第二层的拓扑发现方法着重于发现网络设备端口间的物理连接

4、。第二层的拓扑发现方法着重于发现网络设备端口间的物理连接。 n第三层的网络拓扑发现方法着重于发现路由设备间的逻辑连接第三层的网络拓扑发现方法着重于发现路由设备间的逻辑连接关系。它发现的拓扑结构并不表示网络中设备的真正连接关系，关系。它发现的拓扑结构并不表示网络中设备的真正连接关系，而是而是“IPIP数据报转发数据报转发”意义上的连接关系。意义上的连接关系。 5(2)确定网络拓扑信息的采集方法确定网络拓扑信息的采集方法n被动监测技术被动监测技术在所有观测的网络都加入一个探测器，由它来采集信息，并发送在所有观测的网络都加入一个探测器，由它来采集信息，并发送到网络管理主机来形成网络的拓扑结构。到网络

5、管理主机来形成网络的拓扑结构。优点：除了向管理主机递交各个网络的拓扑信息，不产生额外的优点：除了向管理主机递交各个网络的拓扑信息，不产生额外的流量。流量。缺点：探测器被动收集信息，形成网络拓扑时间较长。缺点：探测器被动收集信息，形成网络拓扑时间较长。放置探测放置探测器困难器困难 n主动探测技术主动探测技术通过网络管理主机主动向所有管理网络发送探测包，并采集返回通过网络管理主机主动向所有管理网络发送探测包，并采集返回的信息，进行分析最终形成网络的拓扑。的信息，进行分析最终形成网络的拓扑。优点：能够比较快的形成整个网络的拓扑。优点：能够比较快的形成整个网络的拓扑。缺点：需要产生的流量比较大，并且对

6、于一个十分慢的网络不太缺点：需要产生的流量比较大，并且对于一个十分慢的网络不太适合。适合。6(3)确定收集信息方式确定收集信息方式n采用采用网络管理信息协议网络管理信息协议(如如SNMP)网络上的设备十分繁杂，不是所有的设备都支持这些管理协议，而网络上的设备十分繁杂，不是所有的设备都支持这些管理协议，而且需要对涉及到的网络逐个进行配置。且需要对涉及到的网络逐个进行配置。n采用采用通用的协议通用的协议局限性较小，如基于局限性较小，如基于ICMP等协议来实现的。一般来说所有的等协议来实现的。一般来说所有的IP网网络和设备都支持，可靠性比较高，且省去了大量的手工配置。络和设备都支持，可靠性比较高，且

7、省去了大量的手工配置。7(4)确定网络拓扑发现的目标及发现程度确定网络拓扑发现的目标及发现程度n网络拓扑发现的最终目标是得到一个网络拓扑发现的最终目标是得到一个快速、完整、正确和高效快速、完整、正确和高效的网络拓扑发现算法或拓扑发现工具。的网络拓扑发现算法或拓扑发现工具。快速快速：能够实时地发现网络拓扑的结构和变化情况，且保持数据：能够实时地发现网络拓扑的结构和变化情况，且保持数据的内部一致性；的内部一致性；完整性完整性：在出现最少错误概率的情况下尽可能多地发现一个特定：在出现最少错误概率的情况下尽可能多地发现一个特定网络内的大部分主机和路由器；网络内的大部分主机和路由器；正确性正确性：算法应

8、尽力保证拓扑发现结果正确，尽量不出或少出错：算法应尽力保证拓扑发现结果正确，尽量不出或少出错误；误；高效性高效性：算法不应消耗过多的网络资源。：算法不应消耗过多的网络资源。8(5)确定拓扑发现算法的运行方式确定拓扑发现算法的运行方式n分布式拓扑发现分布式拓扑发现通过建立服务器和客户机之间的连接，在服务器端起动拓扑发现通过建立服务器和客户机之间的连接，在服务器端起动拓扑发现过程，将各个探测点处收集到的拓扑信息发送到过程，将各个探测点处收集到的拓扑信息发送到服务器（？）服务器（？），然后在然后在服务器（？）服务器（？）端对这些信息进行收集和分析，最后得到整端对这些信息进行收集和分析，最后得到整个网

9、络完整的拓扑结构。个网络完整的拓扑结构。n单点发现单点发现在一个位置发起并完成拓扑探测。在一个位置发起并完成拓扑探测。9拓扑发现的重要意义拓扑发现的重要意义n模拟网络模拟网络为模拟实际网络，分析网络性能、合理扩容和优化网络，必须先为模拟实际网络，分析网络性能、合理扩容和优化网络，必须先得到该网络的拓扑结构。得到该网络的拓扑结构。n网络优化网络优化网络拓扑信息可以帮助网络管理者确定是否需要增加新的路由器，网络拓扑信息可以帮助网络管理者确定是否需要增加新的路由器，当前硬件是否配置正确，并发现网络中的瓶颈所在和失败的链路，当前硬件是否配置正确，并发现网络中的瓶颈所在和失败的链路，进行网络优化。进行网

10、络优化。n用户接入方式选择用户接入方式选择网络拓扑信息可以帮助用户确定自身处于网络中的位置，从而决网络拓扑信息可以帮助用户确定自身处于网络中的位置，从而决定服务器的位置以及选择哪一个网络服务提供商可以将网络时延定服务器的位置以及选择哪一个网络服务提供商可以将网络时延最小化、可用带宽最大化。最小化、可用带宽最大化。10拓扑发现的重要意义（续）拓扑发现的重要意义（续）n研究拓扑敏感算法研究拓扑敏感算法一些新的协议和算法可以在得到网络拓扑信息的基础上改善网络一些新的协议和算法可以在得到网络拓扑信息的基础上改善网络性能。性能。n确定镜像服务器的位置确定镜像服务器的位置根据拓扑信息合理配置镜像服务器的位

11、置以最大可能减少时延，根据拓扑信息合理配置镜像服务器的位置以最大可能减少时延，解决瓶颈问题。解决瓶颈问题。n实行网络服务管理实行网络服务管理例如：例如：mail，ftp，web，snmp，dns。11拓扑发现的重要意义（续）拓扑发现的重要意义（续）n统计数据的采集及关联分析统计数据的采集及关联分析n网络战网络战对于信息作战而言，获得敌方的网络拓扑及与拓扑相关的信息可对于信息作战而言，获得敌方的网络拓扑及与拓扑相关的信息可以灵活有效地组织攻击。以灵活有效地组织攻击。12拓扑发现的研究现状拓扑发现的研究现状n有许多研究机构和公司着力于发现网络拓扑结构的研究有许多研究机构和公司着力于发现网络拓扑结构

12、的研究如如CAIDA，NLANR，Jaspvi，GeoBoy，otter，skitter，MINC，HP的的Internet Mapping项目。项目。n大多数网络管理工具都具有拓扑发现的功能大多数网络管理工具都具有拓扑发现的功能如如HP Openview，IBMs Tivoli等，它们大都依赖于简单网络管理等，它们大都依赖于简单网络管理协议（协议（SNMP）这一标准协议。而）这一标准协议。而SNMP并不是一种通用的协议，并不是一种通用的协议，基于基于SNMP的拓扑发现受到权限的限制，没有权限便不能访问其支的拓扑发现受到权限的限制，没有权限便不能访问其支持的持的MIBII信息，也便无法进行拓扑

13、发现。信息，也便无法进行拓扑发现。13NLANR(应用网络研究国家实验室应用网络研究国家实验室)National Laboratory for Applied Network Research 14CAIDA (国际国际Internet数据分析合作组织数据分析合作组织) cooperative association for internet data analysisUsing the Walrus visualisation tool 15CAIDA（2）16nA graph visualisation showing the topology of the core of the Int

14、ernet from mid-January 2000.17nThis large graph shows the router level connectivity of the Internet as measured by Hal Burch and Bill Cheswicks Internet Mapping Project.nThe work is being commercially developed by Lumeta.18nA topology map of a core network of a medium-sized ISP. nIt was created usin

15、g an automatic network discovery tool called Mercator developed as part of the Scan project by Ramesh Govindan, Anoop Reddy and colleagues, at the Information Sciences Institute, USA. 19A simple dot map of wireless antennas in the USA20For more informationnhttp:/www.cybergeography.org/atlas/topology

16、.html21研究趋势n以太网的规模越来越大，发现以太网的规模越来越大，发现物理拓扑物理拓扑（即第二层拓扑，交换机、（即第二层拓扑，交换机、路由器与主机之间的连接关系）引起一些公司的注意路由器与主机之间的连接关系）引起一些公司的注意nCisco开发的开发的CDP（Cisco Discover Protocol）、）、Bay的的（Networks Optivity Enterprise）、）、Intel、Fluke（LanMapShot）等）等n Bell实验室、实验室、Carnegie Mellon 大学等大学等nIETF制定了制定了物理拓扑的管理信息库（物理拓扑的管理信息库（Bridge M

17、IB） 22网络拓扑发现的难点网络拓扑发现的难点n发现网络拓扑是一项挑战性的工作，因为互联网是发现网络拓扑是一项挑战性的工作，因为互联网是各种网络的各种网络的集合体集合体，这些网络不但设备、软件差异很大，而且可能被，这些网络不但设备、软件差异很大，而且可能被不同不同的组织所管理的组织所管理，他们的组织、运营、安全等措施互不相同。，他们的组织、运营、安全等措施互不相同。n网络网络规模越来越大规模越来越大，而且，而且变化非常快变化非常快（特别是无线网络），更（特别是无线网络），更增加了拓扑发现的难度。增加了拓扑发现的难度。23拓扑发现的基本原理和方法拓扑发现的基本原理和方法n基于网络管理协议的拓扑

18、发现基于网络管理协议的拓扑发现包括第三层和第二层拓扑发现包括第三层和第二层拓扑发现n基于网络主动探测和测量的拓扑发现基于网络主动探测和测量的拓扑发现包括基于网络常用工具的方法（如包括基于网络常用工具的方法（如ping，traceroute等）等）n基于端到端组播测量的拓扑发现基于端到端组播测量的拓扑发现n无线网络的拓扑发现无线网络的拓扑发现247.2 基于网络管理协议的拓扑发现基于网络管理协议的拓扑发现n目前大多数商业化的网管软件都是基于目前大多数商业化的网管软件都是基于SNMP，借助网络设备，借助网络设备中的代理，通过访问管理信息库（中的代理，通过访问管理信息库（MIB）中的变量来实现网络）

19、中的变量来实现网络管理功能（包括管理功能（包括性能、故障、计费、配置、安全管理五个功能性能、故障、计费、配置、安全管理五个功能域域）。）。nMIB含有对路由表和转发表及接口的描述含有对路由表和转发表及接口的描述，因此使得拓扑构造，因此使得拓扑构造成为可能，不但可以构造出成为可能，不但可以构造出网络层设备（路由器、网关）的连网络层设备（路由器、网关）的连接关系，而且也可构造出接关系，而且也可构造出链路层设备（网桥、交换机）的连接链路层设备（网桥、交换机）的连接关系。关系。25基于基于SNMP的网络层拓扑发现的网络层拓扑发现MIB262728基于基于SNMP的网络层拓扑发现的网络层拓扑发现nifT

20、able 接口表，其中接口表，其中ifIndex（接口索引）、（接口索引）、ifDesc（接（接口描述）、口描述）、ifType（接口类型）、（接口类型）、ifPhysAddress（接口的物（接口的物理地址），可用来构造拓扑；理地址），可用来构造拓扑；nipForwarding 1代表可转发数据（具网关功能），代表可转发数据（具网关功能），2代表代表不转发数据（不具有网关功能）；不转发数据（不具有网关功能）；nsysServices 指示节点所提供的服务，若主机在第指示节点所提供的服务，若主机在第i层提供层提供了服务，则了服务，则Li对应相应的层数，对应相应的层数，sysServices的值

21、为：的值为：m=sum2(Li-1)，Li=1,2,3,4,7分别对应物理层，链路层，网分别对应物理层，链路层，网络层，传输层，应用层。例如若络层，传输层，应用层。例如若sysServices的值为的值为7，则它是，则它是路由器；路由器；nIpNetToMediaTable可以访问相连的终端设备的可以访问相连的终端设备的IP地址。地址。29基于基于SNMP的网络层拓扑发现的网络层拓扑发现n初始化网关队列，子网队列，连接队列；初始化网关队列，子网队列，连接队列；n把缺省网关放入网关队列中；把缺省网关放入网关队列中；nwhile（网关队列非空）（网关队列非空）n 从网关队列中取出一个网关，为从网关

22、队列中取出一个网关，为CurrentGateway；n 访问访问CurrentGateway路由表；路由表；n 把路由表中的各把路由表中的各ipRouteNextHop不重复地放到网关队列中；不重复地放到网关队列中；n 把各把各ipRouteDest不重复地放到子网队列中；不重复地放到子网队列中；n 把把CurrentGateway与各与各ipRouteNextHop的连接不重复地放到连接队的连接不重复地放到连接队 列中；列中；n if（ipRouteNextHop属于属于ipRouteDest子网）子网）n 把把ipRouteNextHop与与ipRouteDest的连接放到连接队列中；的连

23、接放到连接队列中；n if（ipRouteNextHop与与CurrentGateway的地址相同）的地址相同）n 把把CurrentGateway与与ipRouteDest的连接放到连接队列中；的连接放到连接队列中；n307.2.2 基于交换表信息的链路层拓扑发现基于交换表信息的链路层拓扑发现n局域网规模的逐渐庞大使得如何局域网规模的逐渐庞大使得如何发现物理拓扑发现物理拓扑越来越引起了研越来越引起了研究人员的注意，目前的方法大都究人员的注意，目前的方法大都基于网桥基于网桥MIB数据（分组转发数据（分组转发表信息）来推算网桥之间的连接关系，即发现物理拓扑表信息）来推算网桥之间的连接关系，即发现

24、物理拓扑。n每个交换机都采用逆向学习算法，并运行了生成树协议每个交换机都采用逆向学习算法，并运行了生成树协议（spanning tree，RFC1493），无环路。），无环路。 Bridge MIB中可能中可能包含有所有可达节点的交换表，也可能仅包含部分可达节点的包含有所有可达节点的交换表，也可能仅包含部分可达节点的交换表，针对这两种情况分别说明。交换表，针对这两种情况分别说明。31基于完全表交换信息的拓扑发现基于完全表交换信息的拓扑发现n令令Sij 为交换机为交换机Si的第的第j个端口，个端口，Aij 为为Sij收到的数据帧的收到的数据帧的源源MAC地址集（地址集（Si转发表的子集）。转发表

25、的子集）。n令令a（b）为交换机）为交换机a到到节点节点b的转发端口。的转发端口。n相互连接的交换机网络中的两种情况相互连接的交换机网络中的两种情况 1.各交换机属于同一子网各交换机属于同一子网2.各交换机属于不同子网（留给大家思考）各交换机属于不同子网（留给大家思考）32基于完全表交换信息的拓扑发现基于完全表交换信息的拓扑发现-算法算法n1 发现节点发现节点：由由ipAddrTable发现子网，由发现子网，由ipRouteTable发现路由器，由发现路由器，由ipForwarding及有无及有无Bridge MIB判断交换机。判断交换机。n2 发现边：发现边：若若 （u是所有节点集合）且是所

26、有节点集合）且 ，则则Sij与与Skl相连。相连。若若Sij是叶子端口（不与任何交换相连）且是叶子端口（不与任何交换相连）且Aij包含路包含路由器由器R的的MAC地址，则地址，则Sij与路由器与路由器R相连。相连。若存在交换机集若存在交换机集SB，节点集，节点集SE，令，令有：有： ， ，有，有a(b)=a(c)，则，则S中在中在SB当中当中包含一个共享网段（集线器），使包含一个共享网段（集线器），使S中各节点互联。中各节点互联。uAAklijklijAA EBSSSBSaScb ,33例子：引理：如果引理：如果 且且 ，则端口，则端口 与端口与端口 直接直接相连接相连接。klijAAklij

27、AAijSklS347.3 基于主动探测的拓扑发现基于主动探测的拓扑发现n利用网络上用来对利用网络上用来对Internet控制和管理的协议（如控制和管理的协议（如ICMP）以及）以及其它服务（如其它服务（如DNS域名服务）提供的信息。域名服务）提供的信息。n通过测试网络端到端的性能（其中包含了内部网络结构，即拓通过测试网络端到端的性能（其中包含了内部网络结构，即拓扑的信息）所蕴涵的信息来构造。扑的信息）所蕴涵的信息来构造。357.3.1 基于基于ICMP的拓扑发现的拓扑发现n美国南加利福尼亚大学信息科学研究所美国南加利福尼亚大学信息科学研究所SCAN研究组研究得到研究组研究得到一个探测工具一个

28、探测工具Mercator该工具采用类似于该工具采用类似于traceroute用跳数受限的用跳数受限的UDP分组进行拓分组进行拓扑构造：扑构造：（1）初始集的选择）初始集的选择: 根据一个主机的地址来判断有效的网络根据一个主机的地址来判断有效的网络地址，并假定相邻的网络地址有效，而且从测试主机自身开地址，并假定相邻的网络地址有效，而且从测试主机自身开始，这样不需要预先构造探测地址集；始，这样不需要预先构造探测地址集；（2）源选路的路由器）源选路的路由器：单点探测可能会漏掉交叉链路，因：单点探测可能会漏掉交叉链路，因此采用此采用源选路源选路的路由器，使探测分组从每个相邻的路由器都的路由器，使探测分

29、组从每个相邻的路由器都进行探测；进行探测；（3）无效端口发送）无效端口发送UDP分组分组:由于路由器可能会有多个接口，由于路由器可能会有多个接口，因此给路由器的无效端口发送因此给路由器的无效端口发送UDP分组，如果返回的分组，如果返回的Port Unreachable ICMP分组的源地址与探测的地址不同则认为分组的源地址与探测的地址不同则认为是多端口路由器。是多端口路由器。367.3.1 基于基于ICMP的拓扑发现的拓扑发现n利用利用ICMP进行网络拓扑发现的步骤如下：进行网络拓扑发现的步骤如下：（1）确定探测点确定探测点，在每个探测点，在每个探测点确定临时地址组确定临时地址组，选择时可根据

30、，选择时可根据已有的积累及网络地址分配的预先知识；已有的积累及网络地址分配的预先知识；（2）在每一探测点用）在每一探测点用ping逐个探测临时组中地址的存活性（如存逐个探测临时组中地址的存活性（如存活加入永久组），并用活加入永久组），并用traceroute跟踪中间路由器，向无效端口发跟踪中间路由器，向无效端口发送送UDP分组发现多端口路由器，由网络地址划分子网，相应信息分组发现多端口路由器，由网络地址划分子网，相应信息存入对应链表中，同时根据子网地址扩充临时地址组。重复执行存入对应链表中，同时根据子网地址扩充临时地址组。重复执行直至遍历完毕；直至遍历完毕；（3）将各探测点的获得的链表进行综合

31、，）将各探测点的获得的链表进行综合，构造主干拓扑构造主干拓扑；（4）在子网内搜索可能存活的主机，）在子网内搜索可能存活的主机，构造子网拓扑构造子网拓扑。377.3.1 基于基于ICMP的拓扑发现的拓扑发现n具有一定的普遍性，能在一定的程度上发现网络拓扑。具有一定的普遍性，能在一定的程度上发现网络拓扑。n能粗略的发现第三层拓扑。能粗略的发现第三层拓扑。n受网管人员干预，获得的信息很有限。受网管人员干预，获得的信息很有限。n搜索的时间太长。搜索的时间太长。387.3.2 基于端到端性能测试的拓扑推算基于端到端性能测试的拓扑推算n通过测量不但可以获得端到端的性能（如时延、丢包率），而通过测量不但可以

32、获得端到端的性能（如时延、丢包率），而且能够推算出网络内部的性能，甚至网络内部拓扑结构。且能够推算出网络内部的性能，甚至网络内部拓扑结构。n相比于单播测试而言，组播测试能够推算更多的内部关联信息。相比于单播测试而言，组播测试能够推算更多的内部关联信息。n基本方法：基本方法：基于端到端基于端到端丢包丢包的组播拓扑推算的组播拓扑推算基于基于时延时延的组播拓扑推算的组播拓扑推算397.4 无线网络的拓扑发现无线网络的拓扑发现n无线网络拓扑发现比有线网络复杂的多无线网络拓扑发现比有线网络复杂的多对于有固定接入点的无线局域网，可通过对于有固定接入点的无线局域网，可通过SNMP访问访问MAC层、物层、物理

33、层的管理信息库理层的管理信息库MIB来构造拓扑。来构造拓扑。若采用了若采用了Mobile IP协议，则可协议，则可访问移动访问移动IP MIB来辅助拓扑发现。来辅助拓扑发现。而对于无中心点的而对于无中心点的Ad hoc网络，可网络，可采用路由协议采用路由协议来构造拓扑。来构造拓扑。n目前目前ad hoc网络的路由协议可分为两类：网络的路由协议可分为两类：Proactive路由路由（表驱动路由）（表驱动路由）Reactive 路由路由（按需路由）（按需路由） 407.4 无线网络的拓扑发现无线网络的拓扑发现nProactive路由（表驱动路由）路由（表驱动路由）OLSR（Optimized Li

34、nk State Routing Protocol）, WRP（Wireless Routing Protocol）每个节点连续学习拓扑，可获得整个网络的部分拓扑每个节点连续学习拓扑，可获得整个网络的部分拓扑在拓扑快变时，更新拓扑信息的代价非常大，拓扑基本不变时又浪在拓扑快变时，更新拓扑信息的代价非常大，拓扑基本不变时又浪费很多资源费很多资源nReactive 路由（按需路由）路由（按需路由）AODV（Ad Hoc On Demand Distance Vector）, DSR（Dynamic Source Routing）该类协议基于查询响应机制，如需要立即启动一个路由搜索进程该类协议基于查

35、询响应机制，如需要立即启动一个路由搜索进程缺点：对数据的时延较大缺点：对数据的时延较大n这两类协议都不能及时有效地构造出节点之间的所有物理连接关这两类协议都不能及时有效地构造出节点之间的所有物理连接关系，另外节点的移动性导致链路频繁的更替。系，另外节点的移动性导致链路频繁的更替。417.4 无线网络的拓扑发现无线网络的拓扑发现n无线网络拓扑发现的一般方法：无线网络拓扑发现的一般方法：基于群首管理信息库的拓扑发现基于群首管理信息库的拓扑发现基于移动代理的拓扑发现基于移动代理的拓扑发现基于分层树的分群机制的拓扑发现基于分层树的分群机制的拓扑发现基于网状网的拓扑发现基于网状网的拓扑发现42基于群首管

36、理信息库的拓扑发现基于群首管理信息库的拓扑发现nW.Chen等人提出了等人提出了ad hoc 网络管理协议网络管理协议ANMP（Ad hoc Network Management Protocol）。）。该协议使用该协议使用一组分布的节点集（或者称为群首，一组分布的节点集（或者称为群首，cluster head）保）保持该节点及其邻居信息，采用分层的机制收集拓扑信息持该节点及其邻居信息，采用分层的机制收集拓扑信息。群首节。群首节点因地理位置或连接情况动态选择，通过群首中的点因地理位置或连接情况动态选择，通过群首中的MIB收集拓扑收集拓扑信息。信息。该方法的缺点在于该方法的缺点在于维持群首维持群

37、首MIB需要开销需要开销，而且节点的移动可能，而且节点的移动可能导致导致MIB过期过期，从而不能提供完整的链路信息。，从而不能提供完整的链路信息。43基于移动代理的拓扑发现基于移动代理的拓扑发现nR. RoyChoudhury等人提出了基于移动代理的分布式拓扑发现等人提出了基于移动代理的分布式拓扑发现策略。策略。每个节点运行一个代理，周期性的收集拓扑信息，并将其分发到网每个节点运行一个代理，周期性的收集拓扑信息，并将其分发到网络中的其它节点。络中的其它节点。该方法不能提供瞬时的网络拓扑，发现完整的网络拓扑需要很长的该方法不能提供瞬时的网络拓扑，发现完整的网络拓扑需要很长的时间，并且需要分发很多

38、消息，因而时间，并且需要分发很多消息，因而效率不高且消耗带宽效率不高且消耗带宽。44基于分层树的分群机制的拓扑发现基于分层树的分群机制的拓扑发现nBudhaditya Deb等人提出了一种用于无线传感器网络等人提出了一种用于无线传感器网络（wireless ad hoc sensor networks）的采用分层树的分群）的采用分层树的分群响应的拓扑发现算法（响应的拓扑发现算法（TopDisc）。）。该方法基于无线通信媒体的广播性质（每个节点通过监听信道能该方法基于无线通信媒体的广播性质（每个节点通过监听信道能知道在其通信范围内其它节点的存在），找出一组群首（知道在其通信范围内其它节点的存在）

39、，找出一组群首（cluster header）节点，这些群首节点将其邻节点信息传给根结点（监控）节点，这些群首节点将其邻节点信息传给根结点（监控节点），大大减少了通信开销。节点），大大减少了通信开销。分群方法的目标归于两点分群方法的目标归于两点（1）寻找一个元素最少的群首集（集覆盖问题）寻找一个元素最少的群首集（集覆盖问题）（2）用群首集构造最小树，即对两个目标进行组合优化）用群首集构造最小树，即对两个目标进行组合优化45基于网状网的拓扑发现基于网状网的拓扑发现nRanveer Chandra等人提出基于网状网（等人提出基于网状网（Mesh-based）的拓）的拓扑发现算法，该方法分为两步扑发

40、现算法，该方法分为两步扩散阶段（扩散阶段（Diffusion phase），），协调（协调（coordinator）节点广播拓扑）节点广播拓扑请求消息，每个节点接收并重新广播这条消息后，构造本地邻居请求消息，每个节点接收并重新广播这条消息后，构造本地邻居信息，更新相应的数据结构。信息，更新相应的数据结构。收集阶段（收集阶段（Gathering phase），），所有节点向协调节点转发本地邻所有节点向协调节点转发本地邻居信息。居信息。n为保证算法的可靠性，每一个节点接收为保证算法的可靠性，每一个节点接收k个个来自父节点的请求，来自父节点的请求，重新广播它们。同时为了保证广播的稳健性，采用了改进的

41、重新广播它们。同时为了保证广播的稳健性，采用了改进的RTS/CTS机制。机制。n结果表明，该方法能在包含不稳定链路的情况下正常工作。结果表明，该方法能在包含不稳定链路的情况下正常工作。461 物理层网络拓扑发现方法物理层网络拓扑发现方法发现途径AFTARPSTP 流量 方法交换机-地址转发表地址解析协议表ipNetToMediaTable(ARP表)生成树协议 流量判断缺点完整性;snmp snmp;适用于局域网完整性snmp;stp耗资源;snmp;运算繁471基于AFT的物理层拓扑发现:已有算法引理：如果引理：如果 且且 ，则端口，则端口 与端口与端口 直接直接相连接相连接。klijAAk

42、lijAAijSklS482. 通用单子网物理拓扑发现算法：流量判断n第第 个端口接收到的流量为个端口接收到的流量为 ，发送的流量为，发送的流量为 。n流量测量流量测量。 a.若若 为为hub，有有进而有进而有 （1）b.若若 为哑交换机，为哑交换机，有有 （2）linloutloE,1 ,NllNioutNiinii, 1, 1oENioutinil, 1NioutNiiniNi, 1, 1492 通用单子网物理拓扑发现算法：流量判断502通用单子网物理拓扑发现算法：算法描述n将无向图看成一个控制节点是根的树，各叶节点逐渐向其父节点收缩，叶节点的上行端口连接到其父节点相应的下行端口上，吸收了

43、叶节点的父节点进而为新的叶节点，逐渐向根节点所连的交换机收缩。当一个下行端口有多个叶节点时，就进行端口流量判断，看是由哑交换机还是由hub将其连在一起。512 通用单子网物理拓扑发现算法：实施步骤1.在控制节点，依次向子网中各网元进行ping操作；2.首先将交换机、路由器及主机各列为一个集合，以及网元集合；3.列出网元的上行端口和下行端口集合；4.数据运算，最终可视化。522 通用单子网物理拓扑发现算法：仿真532通用单子网物理拓扑发现算法：SNMP- MIBmib2-interface-ifTable-ifEntry-ifInOctets(1.3.6.1.2.1.2.2.1.10):收收mi

44、b2-interface-ifTable-ifEntry-ifOutOctets(1.3.6.1.2.1.2.2.1.16):发发mib2-dot1bridge-dot1dBasePortTable(1.3.6.1.2.1.17.1.4):AFT 542通用单子网物理拓扑发现算法: MIB访问实例 55IP层网络拓扑发现方法发现发现途径途径路由表路由表 ARPDNS,OSPF,RIP ICMP/UDP性能性能方法方法snmp-mib地址解析地址解析协议表协议表域名解析域名解析路由协议路由协议主动探测主动探测丢包率丢包率,时延时延 缺点缺点snmp;路路由功能由功能 适于局域适于局域网网 权限权

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

46、网关对应的内侧网关得到外侧网关对应的内侧网关 577.5 基于基于ICMP和和UDP的拓扑发现实例的拓扑发现实例改进的网络拓扑探测的总体思想为改进的网络拓扑探测的总体思想为l使用不可达端口使用不可达端口UDP得到目的地址的得到目的地址的TTL值，并判断其是否值，并判断其是否是路由器上的外侧接口；是路由器上的外侧接口；l使用使用TTL值为目标地址值为目标地址TTL值减值减1的的ICMP探测得到其内侧网探测得到其内侧网关地址；关地址；l用子网区分算法区分外侧子网用子网区分算法区分外侧子网。 改进算法的优势改进算法的优势l不再发送记录路由不再发送记录路由ICMP包，节省了探测时间和网络资源；包，节省

47、了探测时间和网络资源；l而且还解决了而且还解决了9跳以外连接不能确定的问题。跳以外连接不能确定的问题。 58几个术语几个术语n（1）子网的网关）子网的网关探测包由探测发起方到达目标子网时需要经过的该子网中的路由探测包由探测发起方到达目标子网时需要经过的该子网中的路由器，子网中的其它路由器在此并不称为器，子网中的其它路由器在此并不称为“子网的网关子网的网关”。n（2）子网的）子网的TTL值值探测发起方到目标子网的网关的距离向量，即为使发送的探测发起方到目标子网的网关的距离向量，即为使发送的IP包能包能到达该子网必须在到达该子网必须在IP包的包的TTL字段所设置的最小值，同样可定义字段所设置的最小

48、值，同样可定义主机的主机的TTL值。值。59几个术语几个术语n（3）路由器的内侧接口）路由器的内侧接口路由器逻辑上面对探测方的那个接口（路由器逻辑上面对探测方的那个接口（IP地址），即探测包进入地址），即探测包进入路由器的入口。其它接口则称为外侧接口路由器的入口。其它接口则称为外侧接口。 607.5.1 算法的几个关键技术算法的几个关键技术n1.由远及近探测由远及近探测通常使用的通常使用的ping和和 traceroute程序采用程序采用 由近及远探测由近及远探测。拓扑探测如图所示，拓扑探测如图所示，A为探测方为探测方，需要探测需要探测F、G子网的情况子网的情况。在。在A处以处以F为目标地址，

49、为目标地址，TTL值依次置为值依次置为1，2，3，4发送发送IP包，于是包，于是A依次收到由依次收到由B，C，D，F回复的回复的ICMP包，从而得到包，从而得到A到到F支路的支路的拓扑情况。同样探测拓扑情况。同样探测G时也要发送时也要发送4个个IP包，包，A到到D的支路又被探的支路又被探测一次，这样当网络规模较大时（如测一次，这样当网络规模较大时（如G子网含有许多主机）就会子网含有许多主机）就会造成很大的资源浪费。造成很大的资源浪费。61 前面算法不能区分前面算法不能区分9 9跳外同一路由器上的子网，子网区跳外同一路由器上的子网，子网区分算法。分算法。B1B1与与C2C2，C3C3估算的掩码长

50、度一定等于估算的掩码长度一定等于B1B1与与C1C1估算的掩码长度，估算的掩码长度，B1B1与与D2D2，D3D3估算的掩码长度一定等于估算的掩码长度一定等于B1B1与与D1D1估算的掩码长度，估算的掩码长度，而只有而只有B1B1与与B2B2，B3B3估算的掩码长度既大于估算的掩码长度既大于B1B1与与C1C1估算的掩码长估算的掩码长度，也大于度，也大于B1B1与与D1D1估算的掩码长度，利用此亲近关系可知估算的掩码长度，利用此亲近关系可知 B1B1，B2B2，B3B3属于同一子网。属于同一子网。mb1c1 = mb1c2 mbmb1d1= mb1d2 mb mb1b2mb 622.跳跃式跳跃