20基于aft的链路层自动拓扑发现算法

《20基于aft的链路层自动拓扑发现算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

基于AFT的链路层自动拓扑发现算法刘玉华「2余胜生I周敬利I李艳红21（华中科技大学计算机科学与技术学院武汉430074）2（华中师范大学计算机科学系武汉430079）摘要分析了链路层拓扑发现的重要性和现状，讨论了基于BridgeMIB库的AFT信息拓扑发现技术的理论、模型和原理，提出了在交换域内基于AFT的链路层拓扑发现的一个通用算法，给出了算法伪代码及详细描述，最后对该发现算法进行了小结.关键词链路层拓扑，交换域，交换机，AFT,发现算法ALinkLayerAutomaticTopologyDiscoveryAlgorithmBasedonAFTLIUYuhuau2,YUShengsheng1,ZHOUJingli!,LIYanhong21（CollegeofComputerScienceandTechnology,HuazhongUniversityofScienceandTechnology,Wuhan,China430074）2（DepartmentofComputerScience.CentralChinaNormalUniversity,Wuhan,China430079）Abstract:Afteranalyzingtheimportanceandcurrentstatusofalinklayertopologydiscovery,itisdiscussedthatthetheory,modelandprincipleoftopologydiscoverytechnologyarebasedonBridgeMIB'AFT•InthispaperageneralalgorithmofalinklayertopologydiscoverybasedonAFTispresented,itspseudocodealongwiththedetaileddescriptionisgivenoutalso.Atlastaconclusionofalinklayertopologydiscoveryalgorithmissummarized.Keywords:Alinklayertopology,switcheddomain,switch,discoveryalgorithm1.引言随着IP网络自动拓扑发现技术的开发，网络层（第3层）的发现技术己渐趋成熟，并且相对于链路层（第2层）拓扑发现而言，实现第3层拓扑发现也容易一些.网络层主要元索是路由器、逻辑网段与子网，路由器为了实现在网络小选路的基本功能，其路由表通过学习可获取整个网络中路由分布信息⑴，因此一个路由器可辨识与自身相邻的路由器和所连接的子网，网络层拓扑发现正是利用路由器这一特性來进行的.然而第3层拓扑发现仅能覆盖IP网络内一部分元素及连接关系，它不能俘获链路层物理设备，包括交换机、网桥、hubs和一些没有运行SNMP代理的路由器Z间的复杂连接关系.而交换机、网桥、hubs都是第2层网络互连的重要设备，它们应用在LAN组网中，当今LAN的主流以太网技术就是链路层技术.越来越多的交换机分布在以太网中，通过子网微划分以提供更大帶宽，这种网络架构趋势还将持续增长.在这种情形下，传统网管对于在交换网络中的端对端连接控制，链路潜在冲突或设备故障等管理能力严重削弱，所以为了提高网络效率，发现链路层物理设备在网络中的分布及其连接关系是实现众多现代网管任务的先决条件.对于链路层的拓扑发现目前还没有成熟的技术和方法，由于第2层物理设备固有的透明性，使其拓扑发现成为困难与挑战.一些硬件提供商，如cisco和Intel已设计了针对各自企业产品的拓扑发现协议与工具，但它们不适于异构的多供应商网络环境.近年来专业工作者已逐渐意识到 物理拓扑的重要性，国际IETF组织还制定了RFC2922协议标准⑵，设计了一个物理拓扑SNMP管理信息库，另外也有专家试图制定专门的链路层发现协议LLDP等⑴,但是这些标准和协议并不完善，还不能起到实质性作用.本文在对链路层拓扑发现研究基础上2®,基于网络设备广泛支持的SNMP协议和交换机BridgeM1B库中地址转发表(AFT)[7'81,对异构IP网络的数据链路层物理拓扑发现提出了一种通用算法，该算法能够较好解决链路层拓扑发现难题.2.理论与模型2.1概念与模型定义1.计算机网络可用无向图G二rv,E)表示,其屮V表示网络屮节点集合，E表示节点Z间相连的边集合，网络中的元素在图G屮以节点U表示，网络中设备间连接在图G中以边£表示，且ve^E.定义2.网络G中子网"为一个最大IP地址集合，同一子网中任意两个节点可以在第3层或3层以上互相通信，而不同子网节点要经过路由器才能互相通信.IP网络主干由路市器一路由器，路由器一子网组成，路由器将IP网分解为多个子网或逻辑网段，以有效阻止网络小的广播风暴.子网通常由交换机一交换机，交换机一主机构成,由于子网内大量分布交换机，它会带来桥接循环和子网内广播风暴，为了解决这一问题，在交换机间运行“生成树协议(STP)”來阻塞一些端口以使交换机间的闭合回路断开，只有生成树上的交换机端口才能转发数据帧，从而避免循环和广播风暴，支持冗余拓扑.定义3.对于一个运行生成树协议的最大交换机集合S,若在G屮存在连接两台交换机的一条路径，这条路径所经过的节点均在集合S中，我们称这样的交换机集合S为交换域.交换域1交换域2[了交换域o•子网o•路由器I―交换机图1管理域网络G示意图Fig.1TheexampleofthenetworkGinthemanagingarea在分布式系统屮，管理对象的集合叫做管理域，网络G就是一个受管对象集合，我们称它为管理域•在管理域中每个网络元素有唯一的IP地址和定义相应IP子网范围的掩码•图1表示计算机网络G为一个管理域，图中路由器Rl,R2与R3两两相连，它们又分别连接子网1,子网2和子网3,这些属于第3层主干网发现内容.而子网1由于运行一个单独STP实例，所以交换域1由单个子网组成，而交换域2包含子网2和子网3,运行另一个STP实例，所以交换域2为多子网拓扑结构.在子网屮，例如交换机S4与S5可直接通信，而S3若与S4通信，尽管它们有直接的物理连接，但由于它们不在同一子网内，则要通过R2,R3才能互相通信.一个交换域可能包括单个子网N,也可能包括多个不同的子网ENi(i=l,2,・・・n),其区别在于根交换机选举的性质不同和管理者对于交换域规模和使用BPDU通信量开销的决策上.本文以交换域为目标范I韦I,探讨链路层拓扑发现问题. 2.2链路层拓扑发现原理交换机首要功能是自动学习通过自身各个端口数据帧的源MAC地址，并将其与对应的端口号一块存入本交换机的地址转发表AFT中，成为与本交换机相连的交换机、网桥或其它网络设备的物理地址，交换机的工作原理就是将AFT表屮MAC地址作为目的地址来作出转发帧或过滤帧的决定的.在此我们也利用AFT表中MAC地址在交换域屮从根交换机开始，采用树的广度优先遍历方法，搜索与之相匹配的交换机，逐一找出全部交换机之间的连接关系.在子网内交换机通过预处理，可以尽量学习到完整的MAC信息，而交换机跨子网通信时，市于须经过路市器转发，所以物理上直连的处在不同子网中的交换机端口学习到的MAC地址是不完整的，因此在交换域内，同一子网内和不同子网间交换机直连的判定条件是不同的.定义4.在交换域中，第厂个交换机记为S”&的第丿•个端口记为S“.S“端口学习到的数据帧的源MAC地址集合记为由此可以看11!,交换机Si的AFT屮MAC地址由》A“组成，其屮n为交换机端口计数.我J=i们用Yuri文章中引理⑷作为判断两个交换机端口％•和％在交换域内直连的条件：定理1.在同一子网内,交换机端口®与j直连,当且仅当AyDAkl=0且AijUAki二M,其中M为子网内所有设备的物理地址集合.定理2.在不同子网屮，交换机端口S“与S灯直连，当且仅当AijnAkl=^且怨包含S&的MAC地址.在链路层交换机除了与交换机直连外，它还可以与路由器、主机相连.特别是一些桌面交换机，他们通常位于交换机生成树的叶节点，直连全部主机到桌面.2.3链路层拓扑发现信息采集进行链路层发现，主要用到RFC-1213定义的MIB-II库和RFC-1443定义的BridgeMIB库中信息.在MIB-II中要用到ip组、System组.ip组中的ipNetToMediaTable表是一个1P地址转换表，他将设备的IP地址ipNetToMediaNetAddress映射到它的MAC物理地址ipNetoMediaPhysAddress+*,信息采集时，利用这种映射关系找出子网内设备；表中索引项ipNetToMedialflndex的值与ip组屮的ipAddrTable表屮的索引项值相同，在ipAddrTable表中可搜寻到索引值的子网掩码ipAdEntNetMask,以计算设备所在子网号.另外，在判断设备类型时要用到System组中的SysServices变量，它表明设备工作在OSI物理层到应用层之间相应层次，若与ip组中的ipForwarding转发变量值结合，可判定设备是否为交换机类型.对检索出的交换机，采集其BridgeMIB库的dotldStp组屮dotldStpDesignateRoot变量值，值相同的交换机，根据生成树规则归为同一交换域.进行链路层发现，最重要的是利用BridgeMIB库中dot1dBase组和dotldTP组信息.在dot1dBase组屮交换机的MAC地址被对象dot1dBaseBridgeAddress定义，而dot1dBaseNumports对象则标明交换机端口数li;在dot1dBasePortTable表中可查到dot1dBaseport端口与dot1dBasePortlflndex接口索引的映象.在dotldTP组屮，地址转发表dotldTpFdbTable（即AFT表，见表1）包括目的MAC地址dotldTpFdbAddress对象和相应的dotldTpFdbPort端口号对象，还有该端口的状态信息dotldTpFdbStatus,该参数表明端口MAC地址是自身物理地址还是通过学习得來的目的地址等，通过端口记录的目的地址，数据帧被转发到目的设备.在dotlTpFdbTable表川，同一端口Sij的MAC地址组成该交换机Si的Aij地址集合.表1交换机的地址转发表AFT(即dotldTpFdbTable表)TableITheAddressForwardTableofaswitch (dotldTpFdbTable)dot1dTpFdbAddressdotldTpFdbPortdotldTpFdbStatus0004287522la13learned(3)0005324209cl21sclf(4)00042875221b14lcarncd(3)000501c997ff13learned(3)3.链路层自动拓扑发现算法基于上述理论与模型基础，我们设计了一个链路层拓扑发现算法.算法首先从与子网相连路rti器的路rti表中寻找子网内设备和交换机，并以交换域为目标范围，从根交换机开始,采用遍历生成树方法，利用定理1与定理2规则，逐级分层搜索交换机和其它设备分布及端口之间的连接关系.3.1链路层自动拓扑发现算法链路层自动拓扑发现算法定义了4个队列：路由器队列、链路层设备队列、交换机队列和拓扑发现(临时)队列，以下是算法的伪代码：routerList=FindRoutersInSubnets(D);//step1for(eachrinrouterList){//step2dv=retrieveMIB(r);addElement(dv,deviceList);}for(eachdindeviceList){//step3if(run_agent(d)&&isSwitch(d)){if(retrieveBridgeMIB(d,"dot1dStpDesignateRoot")=md){makeFlag(d/'switchH);addElement(d,switchList);confirmFlag(Hfalse,d,switchList);)removeElement(d,deviceList);}}ping_switch(switchList);//step4for(eachiinswitchList)retriveBridgeMIB(i);//stepMi=getMACSubnet(Nj);clearList(discoverList);s=findRootSwitch(switchList);//step6confirmFlag(Htrue,s,switchList);addElement(s,discoverList);drawDevice(s);while(!empty(discoverList)){//step7Si=removeElement(discoverList);for(eachportjofswitchSj){//step8Aq二FindMACSet(j,Si);if(find_match(Ajj,switchList,Sk)){//step8」S1=findSubnet(Si);S2=findSubnet(Sk)；Aki=FindMACSet(l,Sk);if(S1二S2&&AijUAk)=Msi&&Ajj0Akl=①){//(l)addSSLink(Sjj,Sk.i);}elseif(S1匸S2&&AqAAkI=①){//(2)addSSLink(Sij,Su)；}else{continue;}confirmFlag("trueM,Sk,switchList);〃(3)addElement(Sk,discove「List);drawDevice(Sk)；}else{//step8.2 find_match(AijdeviceList,h);addSHLink(Sj,j,h);drawDevice(h);}}}//step93.2算法详细描述以下是算法的详细描述：stepl获取交换域内连接子网的所有路由器的队列routerList,参数D表示交换域；step2对于routerList中的每一个路由器，访问其MIB-II库中的ipNetToMediaTable表，构造ipNetToMediaNetAddress（IP地址）ipNetToMediaPhysAddress（MAC地址）所代表的设备，同时根据ipNetToMedialflndex接口索引在MIB-II库的ipAddrTable表中查找相应的值ipAdEntNetMask以确定该设备的子网掩码，进而计算其所属的子网，将此设备加入到队列deviceList中;step3对于队列deviceList中的每一个设备，若该设备存活并且运行了SNMP代理，则检索其MIB库中的sysServices和ipForwarding值來判定设备类型（交换机、路由器或主机），并对deviceList中该设备标志其类型.若所标设备类型为交换机，则检索其BridgeMIB库屮的变暈dotldStpDesignateRoot值确定交换域（md表示某一交换域值），如果为同一交换域则按顺序编号加入到交换机队列switchLisfp,并初始化“确定”标志为false,然后将其从队列deviceList中移出；step4子网屮全部设备依次向交换机队列的交换机做ping操作，以使端口学习到完整的MAC地址；step5访问队列switchList屮的每一个交换机的BridgeMIB库，提取其AFT地址转发表（dot1dTpFdbTable）,端口数目（dotldBaseNumports）和端口表（dotldBasePortTable）等信息，Mi依次为各子网N内设备的MAC地址集合；step6将队列discoverList清空，找出队列switchList内"根交换机”，将此设备的"确定”标志置为true,将它加入到队列discoverList中，在拓扑图中绘出该设备；step7若队列discoverList非空，则从屮移出一个待检测交换机S）；否则，转step9；step8对交换机Si的每一个端口j,提取该端口学习到的所有MAC地址集合A©；8.1若集合Ay存在与switchList中某设备Sk的MAC地址相匹配，进一步统计Sk的各个端口|学习到的所有MAC地址集合Akl；（1）如果Si与Sk屈于同一子网，同时AijUAk尸Msi且AijQAk尸①，为子网内设备的MAC地址集合，则交换机Si的端口j与交换机Sk的端口1直接相连，转（3）；（2）如果&与5不属于同一子网，但由于Aq包含Sk的MAC地址，且AijQAki二①，则交换机&的端口j与交换机Sk的端口1直接相连；（3）在队列switchList中将Sk的"确定”标志置为true,并将其加入到队列discoverList中，在拓扑图中绘出交换机Sk，转step8；8.2若集合Ajj的每一个MAC地址与switchList屮所有设备的MAC地址都不匹配，再从队列deviceList中查找物理MAC地址与之匹配的设备h,若存在，则交换机Si的端口j与设备h直接相连，在拓扑图中绘出设备h；转step7；step9结朿.4.小结我们在智能网络管理系统中实现了上述通用链路层拓扑发现算法，在发现主干网拓扑结构后，程序能自动检测交换域内子网，并进行链路层拓扑发现和图形显示.程序也能限定交换域和子网，直接开始链路层的拓扑发现，能准确获取路由器一交换机、交换机一交换机、交换机一主机的分布及其端口级的复杂连接关系.该算法由于需增加额外通信开销来保证交换机端口学习MAC地址的完整性，所以它适于中小规模子网负载的链路层拓扑发现技术中使用.由于IP子网普遍支持SNMP和运行生成树协议，因此该算法在目前也是最通用、最简洁、最行之有效的链 路层拓扑发现方法.基金项目：湖北省自然科学基金(No.2001ABB013)资助.参考文献[1JK.McCloghrieandM.Rose.ManagementInformationBaseforNetworkManagementofTCP/IP-basedinternets:MIB・I].InternetRFC-1213.Mar.1991[2]A.Bierman,K.Jones.PhysicalTopologyMIBRFC-2922.Sept..2000[3]PaulCongdon・LinkLayerDiscoveryProtocolandMIB.V1.0May20.2002[4]YuriBreitbart,MinosGarofalakis,etc.TopologyDiscoveryinHeterogeneousIPNetworks.IEEEINFOCOM2000:Volume1,265-274,2000,TelAviv,Isral..|5|BruceLowekamp,DavidR.O'Hallaron,etc・TopologyDiscoveryforLargeEthernetNetworks・SIGCOMr()l,August27-31,2(X)1,USA[6]郑海，张国清.物理网络拓扑发现算法的研究.计算机研究与发展.2002年3月.pp264-268.ZhenghaiandZhangGuo-qing・AnAlgorithmforPhysicalNetworkTopologyDiscovery・Jouralofcomputerresearchanddevelopment.March2002.pp264-268.|7]WilliamStallings.SNMP,SNMPv2,SNMPv3,andRMON1and2.Addison-WesleyLongman,Inc.1999.(ThirdEdition)[8]E.Dcckcr,P.Langillc,etc.DefinitionsofManagedObjectsforBridges.InternetRFC-1493.July1993作者简介：刘玉华，副教授，瞎士研究生.主要研究方向为计算机网络与通信、网络管理.E-mail:yhliu@ccnu.edu.cn.余胜生，教授，博士生导师.主要硏究领域为计算机网络多媒体通信与高性能网络存储.周敬利，教授，博上生导师，主要研究领域为计算机多媒体网络通信，高性能网络接口和网络存储.