第８期２００８年８月电子学报Ｖ０１．３６Ａｕｇ．Ｎｏ．８２００８ＡＣＴＡⅡＥ叨ｉ０ＮＩＣＡＳＩＮＩＣＡ网络拓扑发现新算法及其实现陈福１一，杨家海２，一，杨扬１（１．北京科技大学计算机科学与技术系，北京１０００８３；２．清华大学信息网络工程研究中心，北京１０００８４；３．清华大学信息与科学国家实验室。北京ｌｏｏｏｓ４）摘要：本文首先提出一种面向口主干网的启发式网络拓扑发现算法．该算法基于启发式、贪心法的思想，具有ｍ地址的自动推理和查找范围的自我调整，因而具备较强的自适应性．进而提出了一个数据链路层拓扑发现算法．该算法与已有的算法相比重点解决了无生成树协议工作下数据链路层拓扑发现、主机的拓扑构造以及集线器或无口地址的交换机等所谓的哑设备发现问题．同时阐述了一种新的数据结构类型并给出其数学定义、专有操作及该数据结构在算法中的应用．算法已经实现并应用到我们自己开发的软件中，同时在清华大学网络研究中心实验网络环境中进行了实际测试和验证，达到了很好的效果．关键词：拓扑发现；树型图；网络层；数据链路层文献标识码：Ａ中图分类号：ＴＦ３０１文章编号：０３７２－２１１２（２００８）０８．１６２０－０６ＮｅｗＡｌｇｏｒｉｔｈｍｓｏｎＩＰＮｅｔｗｏｒｋＴｏｐｏｌｏｇｙＤｉｓｃｏｖｅｒｙａｎｄＩｔｓＩｍｐｌｅｍｅｎｔ（１．伪Ⅻｆ＂洲矿ｃ０咄＆切Ｗ删％如ｌ锄ｙ，‰毋ｏｆＳｃ妇Ⅸ删乃由魄ｙ蜥，＆溉１０００８３，ａＩ讹；２．‰ＮｅｔｗｏｒｋＲｅｓｅａｒｃｈ＆ｍｅｒｏｆ乃咖咖ｍＵｎｉｖｅｒｓｉｔｙ，死如ｇ妇Ｕｎｉｖｅｒｓｉｔｙ，＆伽喈１０００８４，Ｃｈｉｎａ；ＣＩ－ＩＥＮＦｕｌ，一，ＹＡＮＧＪｉａ－｝ｌａｉ２”，ＹＡＮＧＹａｎ９１３．乃咖ＵｎｉｖｅｒｓｉｔｙＮａｔｉｏｒｍＺ厶如锨），ｙＡｂｓｔ隐ｃｔ：ｐｈｙｓｉｃａｌｔｏｐｏｌｏｇｙｉｎｏｆＩｎｆｏｒｍａｔｉｍＳｃｉｅｎｃｅａｎｄＴｅｃｈｏｎｏ／ｏｇｙ，啪１０００８，踟ｍ）ｓｅａｒｃｈＩｎｔｉｆｆｓｐａｐｅｒ，Ｗｅｐｒｅｓｅｎｔｔｗｏｎｏｖｅｌａｌｇｏｒｉｔｈｍｓ，０ｆ譬ｆｏｒｄｉｓｃｏｖｅｒｙ］ｏｇｉｃａｌｔｏｐｏｌｏｇｙ，ａｂｅ妇ｏ∞ｆｏｒｄｉｓｃ叭咄ａｌｇｏｒｉｔｈｍｓ，ｃ锄ｂｅｄｏｍａｉｎ，ｉｔｈａｓｓｌｌ＇ｏｎｇａｄａｐ【ａｂｉｌｉ—ｈｅｔｅｒｏｇｅｔ脚ｕｓＩＰｎｅｔｗｏｒｋｓ．Ｔｈｅａｌｇｏｒｉｔｈｍｆｏｒｌｏｇｉｃａｌｎｅｔｗｏｒｋ，ｗｈｉｃｈａｄｏｐｔｈｅｕｒｉｓｍ＼ｇｒｅｅｌｙａｐｐｌｉｅｄｔｏｌａｒｇｅｓｃａｌｅＩＰｎｅｔｗｏｒｋ．Ｆｏｒｔｉｅｓ．Ａｎｏｔｈｅｒｎｏｖｅｌｄａｔａｔｌ－，ｅ出ｏｒｉｔｔｍａＣａｌｌｓｅｌｆｄｅｄｕｃｅＩＰａｄｄｒｅｓｓｅｓ，ａａｊｕｓｔｔｈｅａｌｇｏｒｉｔｈｍｉｓｐｒｅｓｅｎｔｅｄｆｏｒｐｈｙｓｉｃａｌｔｏｐｏｌｏｇｙｗｈｉｃｈｉｎｃｌｕｄｅｓｓｗｉｔｃｈｅｓ，ｈｏｓｔｓａｎｄｈｕｂｓ．Ａｔｔｈｅ鞠盯ｔｔｉｍｅ，ａｎｅｗＴｒｅｅｌｉｋｅ—Ｇｒａｐｈｉｃｓｆｏｒｔｏｐｏｌｏｇｙｄｉｓｃｏｖｅｒｙｉｓｔｈｉｓｄａｔａｓｍｌｃｔ眦ｎａｍｅｄｐｆ嚣即ｔｅｄｗｉｔｈｐｆｅｃｉｓｅｍａｔｈｅｍａｔｉｃｄｅｆｉｎｉｔｉｏｎ，ｒｅｌａｔｉｏｎｓｈｉｐｎｏｓｅｔｔｏａｎｄｇｅｔｐｒｏｐｒｉｅｔａｒｙ０１）啪６∞Ｏｌｌｓｍｌｃｌｌｌｒｅ．ＴｈｅａｌｇｏｒｉｆｌⅡｎ，ｗｈｉｃｈＷｅｐｒｅｓｅｎｔｉｎｔｈｉｓｐａｐｅｒ，ｄｏｅｓａｒｅｂａｓｅｔｈｅＯｉｌｔｈｅＳＴＰｐｒ呦ｃｏｌｔｈｅｉｎｆｏｒｍａｔｉｏｎｏｆｔｏｐｏｌｏｇｙ．Ｓｏ．ｔｈｅｒｅｆｅｗｐｒｅｃｏｎｄｉｔｉｏｎｓｔｏｔｈｅｐａｐｅｒｉｎＰｅｒｌｉｎＴｓｉｎｇｈｕａＵｎｉｖｅｒｓｉｔｙｏｗｎｒｅｓｅａｒｃｈｎｅｔｗｏｒｋ．Ｔｈｅｔｈａｔｏｕｒｅｘｌ础ｅｎｔａｌａｌｇｏｒｉｔｈｍ．Ｗｅｈａｖｅｉｍ＃ｎ蟹ｎｔｅｄｒｅｓｕｌｔｓｃｌｅａｒｌｙｖａｌｉｄａｔｅ叫ａｌｇｏｒｉｔｌｍａ，ｄｅ棚堪吲咖ａｌｇｏｒｉｔｈｍｐｒｅｓｅｎｔｅｄｉｎ吐凰ａｌｇｏｒｉｆｌ＇ｍａ啪ｃｏｎｓｉｓｔｅｎｔｌｙｄｉｓｃｏｖｅｒｔｈｅａｃｃｕｒａｔｅｐｈｙｓｉｃａｌｎｅｔｗｃｘｋｔｏｐｏｌｏｇｙｗｉｔｈｒｅａｓｏｎａｂｌｙｓｍａｌｌｒｕｎｎｉｎｇ－ｔｉｍｅ把蛳－ｍｅｎｔｓ．Ｋｅｙｗｏｒｄｓ：ｔｏｐｏｌｏｇｙｄｉｓｃｏｖｅｒｙ；ｔｒｅｅｌｉｋｅ－ｇｒａｔ蚰ｃｓ；ｎｅｔｗｏｒｋ；ｄａｔａｌｉｎｋｌ引言网络管理中的配置管理主要功能为发现网络拓扑结构、管理网络设备．而管理网络设备的基础是已知网络设备及其拓扑结构．因此，网络拓扑发现是网络管理的基础．网络拓扑发现目的在于获取网络节点的存在性信息及其之间的拓扑关系，并籍此绘制拓扑结构．网管人员通过拓扑结构定位网络故障、发现网络瓶颈，从而优化网络运行．对于小型网络，网管人员可以手工管理网络拓扑．但大型网络设备之间的拓扑关系异常复杂，无法手工管理网络拓扑．自动网络拓扑发现是指计算机程序自动发现网络逻辑或物理拓扑、网络节点间拓扑、探测目标网络、发现网元设备，并绘出网络拓扑图．口网络逻辑层包括路由器、子网拓扑，物理拓扑主要针对收稿Ｆ｛期：２００７－０６－１３；修回口期：２００８－０３—１ｌ交换机、集线器、主机工作站等．目前对咿网络层拓扑发现研究较多，该领域算法相对比较成熟ｕｏＪ．但这些算法均基于路由转发表，而转发表数据量极大，据此发现效率很低．与网络层拓扑发现研究相比，针对数据链路层拓扑发现研究相对较少．由于网络层拓扑信息不能反映子网内的网络单元物理连接关系从而使网管人员对物理拓扑信息知之甚少，这极大削弱了网管人员查找、排除网络故障的能力．因此对物理拓扑发现的研究具有重要意义．本文提出的ＩＰ网络交换层拓扑发现算法基于启发式和贪心法的思想，通过源点逐步向外围拓展，并在条件具备时通过ＢＧＰ和ＡＲＰ协议进一步提高发现效率，具有很强的自适应性．本算法突破了基于路由表拓扑发现耗时、低效的缺点，极大提高了发现效率．基金项目：国家自然科学基金（Ｎｏ．６０６７３１６０，Ｎｏ．９０４１２０１２，Ｎｏ．６０４７３０８３）；国家８６３高技术研究发展计划（Ｎｏ．２００７ＡＡ０１２２３４，Ｎｏ．２００５ＡＡｌ０３１１０－２）万方数据 第８期陈福：网络拓扑发现新算法及其实现１６２１目前物理拓扑发现集中于具有生成树协议（ｓＴＰ）工作的交换机之间的连接关系．文献［４］使用ＳＮＭＰ公有ＭＩＢ变量在单子网、多子网和存在Ｖ３＿ＡＮ的情况下的链路层拓扑发现问题．文献［５］采用基本相同的方法发现单子网、多子网、主机和路由器的连接关系，但增加了对网络服务拓扑的查询．２０００年ＩＥＩＦ曾提出针对物理拓扑的ＲＦＣ，定义了拓扑信息的ＭＩＢ变量Ｌ６Ｊ．文献［７，８］提出的针对链路层的算法都是基于ＳＴＰ协议、地址信息完全情况下的解决方法．文献［９］将拓扑发现转换为数学问题并利用数学工具发现，解决了多子网转发表转发信息不完整情况下的拓扑发现问题．根据ＳＴＰ协议确定交换机之间、交换机与主机之间以及交换机、集线器、主机之间的连接关系，在很多文献中均有阐述．而实际网络环境中未启动ＳＩＰ协议的情况非常普遍，因此仅根据ＳＴＰ协议进行拓扑发现必然不是完整的链路层拓扑图．由于这些设备大多与终端用户非常接近，从而对用户网络服务质量具有重要影响．本文提出的算法重点解决无ＳＴＰ协议工作的情况下数据链路层拓扑发现、主机拓扑构造以及集线器或没有ＩＰ地址的交换机等所谓的哑设备发现问题．该算法填补了无ｓ口协议工作的数据链路层拓扑发现的空白，是非常有意义的工作．２基于地址猜测的启发式交换层拓扑发现算法２．１算法的基础理论引理１路由器的标识确定：由于路由器具有多个接口，必须唯一标识路由器．如图ｌ（口）所示，通过路由器Ａ、Ｂ均可以发现路由器Ｃ．但却是Ｃ的两个不同接口．因此需要将ｃ１、Ｑ两个接口合并标识为同一设备．本文首先使用路由器的Ｌｏｏｐｂａｃｋ地址，其次采用所有接口中数值最大的接口作为路由器的标识接口地址．（∞路由器台井（６）网络地址推断图１多址路由器合并与网络地址推断引理２子网地址猜测：网络层拓扑发现算法目的在于发现路由器及其子网的拓扑连接．图１（ｂ）中Ｒｌ、Ｒ２、Ｒ３为路由器，由图１（ｂ）可以看出，每个路由器可能带若干子网，路由器之间相互连接．但直接相连的两台路由器之间客观上也形成了只有两个口地址的子网．假设以Ｒ１作为种子Ⅲ开始拓扑发现，可从Ｒ１的管理信息库（ＭＩＢ）中取出每个交换机的接口地址和子万 方数据网掩码，并据此计算出各个子网的子网地址．设从ＭＩＢ中取出的路由器的接口地址集合为ＩＰ—ＳＥＴ＝｛茗Ｉ茗∈路由器的接口地址｝从ＭＩＢ中取出的子网掩码地址集合为：Ｍａｓｋ—ＳＥＴ＝｛ＹＩｙＥ路由器的子网掩码｝由于一个接口地址对应一个子网掩码，而且接口地址与其对应的子网掩码两者逻辑相与可以得到网络号．即，Ｖ凰∈，Ｐ—ＳＥＴ可以唯一确定一个Ｋ∈Ｍａｓｋ—ＳＥＴ，即置卜Ｋ．令：五＝置＆Ｋ，则有五构成一新的集合，为子网地址集合，设该集合为Ｓｕｂ—Ｎｅｔ．根据Ｐ地址规范，可以从子网掩码推测可能的碑地址．综上，得出计算可能伊地址的方法：（１）Ｖ置∈ＩＰ—ＳＥＴ唯一确定一Ｋ∈Ｍａｓｋ—ＳＥＴ，即置卜Ｋ．（２）将两者相与，即Ｚ＝Ｘｉｔ暨ｇｉ．（３）根据子网掩码得到非０部分的可能值与五相加．就可以得到一可能Ⅲ地址集合，设该集合为Ｇｕｓｅｅ．ＩＰ—Ｓｅｔ．引理３ＢＧＰ协议端点路由器的确定：如启动了ＢＧＰ协议，由于基于该协议通信的设备必然是路由器．本算法突出之处其一就是如路由器启动了ＢＧＰ协议则通过该协议取得和路由器直接交互的端到端结点信息．通过该信息可直接确定设备的类型、连接关系．引理４子网范围的自适应调整：如两个路由器直接相连接，子网掩码范围一般为２５５．２５５．２５５．２５２，但由于各种原因可能将其配置为２４８、２４０、２２４、１９２或１２８．本算法具有一定自适应性，如果为２５２未能发现路由器设备，程序将自动调整为２４８、２４０、２２４、１９２或１２８．２．２网络层拓扑发现算法描述ＴｏｐｏＤｉｓｖｅｒ（ＩＰ—ＡｄｄＩＰ，ｃｈａｒ＊Ｃｏｍｍｕｎｎｉｔｙ，ｉｒａｄｅｐｔ｝１）｛ｊｕｄｇｅＤｅｖｉｃｅＴｙｐｅ（ｇａｔｅｗａｙＩＰ，ｇａｔｅＣｏｍｍｕｎｎｉｔｙ，）；ｉｆ（ＩＰ！＝路由器）｛Ｒｅｔｕｒｎ｝将种子口放人发现队列；判断ＣＯＭＭＵＮＩＴＹ；珊ｌ如（发现深度小于规定深度Ｏｒ发现队列！＝ｎｕｎ）｛从发现队列中取得待发现地址；，将该设备所有接口地址放入到接口集合中；取待发现路由器端口地址、子嘲掩码；ＳｕｂＡｄｄ＝ｇａｔｅｗａｙｌＰｎＭａｓｋＡｄｄ；推断町能口地址；取启动ＢＧＰ协议）｛通过ＢＧＰ获得该路由器连接端点集；｝１６２２电子／／Ｎ断该地址对应设备的存在状态和设备类型．Ⅱ（路由器）｛判断该路由器器是否已经发现；Ⅱ（该路由器器没有被发现过）｛将该地址存入到待发现队列；将待发现地址和设备作为—个连接放入结果集；｝｝｝返回发现结果集；｝３数据链路层拓扑发现新算法基础理论３．１相关概念根据交换机工作原理和ＳＴＰ协议，并充分比较已有方法基础上，本文提出无ＳＴＰ协议工作数据链路层拓扑发现算法，借鉴ＳＴＰ协议思想，根据各个交换设备到网关的距离判断子网内各个交换机的拓扑连接关系．为便于阐述给出下述定义：根交换机：直接与网关相连接的交换机．交换域：与一个网关相连接的主机、集线器、交换机等组成的网络设备．交换机上行口：与网关连接距离最近的端口．交换机下行口：除了上行端口外，与下级的级联交换机、集线器或主机相连接的端口．下行完全集：某一交换机以下所有交换机构成的集合．上行完全集：在上行交换域中交换机的集合．下行交换域：由某交换机及其以下各个设备组成的数据链路层网络．上行交换域：在整个交换域中除了本交换机和本交换机下行交换域之外的交换域．上行交换机：通过本交换机的上行端口与本交换机直接相连的交换机．下行交换机：通过本交换机的下行端口与本交换机直接相连的交换机．３．２前提假设可假设一个交换机下行完全集是以树型结构组织的．依据：一个交换域交换机之间的连接关系只可能是树或图型结构，如是图型关系则在此交换域中必启动了ＳＴＰ协议，否则将形成回路．而若启动ＳＴＰ协议，其拓扑可由ＳＴＰ协议得到，具体方法参见文献［４～９］．本算法是在无ＳＴＰ协议工作情况下获取网络拓扑的方法．因此，本算法假设交换机之问的连接关系是树型结构．３．３无ＳＴＰ协议工作的链路层拓扑发现引理引理１无ＳＴＰ协议工作的链路层以下交换机上万 方数据学报２００８正行端口、下行端口的确定：在无ＳＴＰ协议工作的链路层交换机转发表中目的地址为网关的表项所对应的端口即为该交换机的上行端口．该交换机其余端口为下行接口，该结论不言自明，毋用证明．引理２交换域根交换机的确定：根据前述假设，交换机下行完全集为树型结构．在该树型结构中，任一交换机通过其上行端口转发的转发表数目一定大于其下行交换机上行端口转发的转发表数目．且在该交换域中的根交换机一定是通过本交换机上行端口转发的转发条目最少的那个交换机．证明：如图２所示，设在网关的下行交换域中存在任意两个交换机，其中交换机Ｓ１为交换机｜ｓ２的上行交换机，｜ｓ２为交换机Ｓ１的下行交换机．由图２可看出，交换机Ｓｌ的交换域＝Ｓｌｌ＋Ｓ１２＋．ｓ１３．其中Ｓ１３为Ｓｌ的上行完全集为，ｓＩＩ＋Ｊｓｌ２为Ｓｌ的下行完全集．．ｓ２的交换域＝Ｓ２１＋．ｓ筮．其中Ｓ２ｌ为Ｓ２上行完全集，Ｓ２１为Ｓ２的下行完全集．图２网关交换域Ｓ２＋．ｓ２ｌ＋Ｓ２２＝｜ｓｌ＋Ｓ１１＋Ｓｉ２＋Ｓ１３（１）其中，Ｓ笠和Ｓ１２只相差交换机Ｓ２本身，因此可以认为如＝Ｓ１２．同时我们也忽略交换机Ｓｉ、Ｓ２．因此由式１得到：Ｓ２ｌ＝Ｓｌｌ＋Ｓ１３（２）因此，可以推导出：Ｓ２ｌ≥Ｓ１３引理３交换域中的交换机拓扑生成树的确定：任一交换机下行完全集与该交换机下行完全集中所有交第８期陈福：网络拓扑发现新算法及其实现１６２３换机下行完全集之和的差就是该交换机的下行交换机集合．如果已知根交换机，则可以通过根交换机的转发表求得该交换机域的下行完全集，进而求得该交换机下行完全集中所有交换机下行完全集，因此可以得到根交换机的下行交换机，通过递归使用本结论即可得到该交换域的交换机拓扑信息．图３是实际网络的模型，交换机Ｓ．的下行完全集为Ｓｌｌ’交换机．ｓ１的下行交换机集合为｛＿ｓ２、Ｓ３、＆……｝．交换机｜ｓ２的下行完全集为．ｓ２ｌ、Ｓ３的下行完全集为Ｓ３１、Ｓ４的下行完全集为｜ｓ４ｌ，．…··Ｓ。的下行完全集为＆１．我们可以看出交换机Ｓｌ的下行完全集Ｓ１１＝Ｓ２＋Ｓ３＋Ｓ４＋…＋＆＋￥２１＋Ｓｎ＋￥４１＋……Ｒ１．因此交换机ｓ１的下行交换机集合Ｓ２＋Ｓ３＋Ｓ４＋图３交换机拓扑生成图图４哑设备发现示意图万 方数据……＋＆＝Ｓｌｌ一｛Ｓ２１＋＿ｓ３１＋＆１＋……＆１｝引理４集线器或没有Ⅲ地址交换机的发现：通过结论２能确定若干交换机处于交换机拓扑生成树的同一层次而且具有相同的上行交换机，则在这些交换机之上必然存在一个集线器或没有口地址交换机设备．证明：应用公理２，可以从图４中得到和图３完全相同的交换机拓扑生成树，并且也可以知道交换机Ｊｓ．的下行交换机的转发端口．因此由图４可以明显看出若干交换机如果通过集线器接入到上行交换机，则在其上行交换机上必然具有相同转发端口．４一种新型数据结构一树型图的提出４．１树型图逻辑特点及定义在进行拓扑发现过程中，我们发现在交换机交换域的下行端口转发信息中存在一个类似与树、但实质却是图的一种数据结构，类似于树的依据：（１）本算法解决在没有ＳＴＰ协议工作的情况下二层拓扑发现问题．因此该拓扑一定是一树型结构，因为如不是树型结构则必然存在回路，如果存在回路又没有ＳＴＰ协议消除冗余路线则必然造成转发死循环，因此实际物理连接一定是树结构．（２）在交换域各个交换机的下行端口转发表中一定不含其兄弟和祖先结点的转发信息．因为这样的转发信息一定通过上行端口转发．而且在该生成树深度相同的各个结点的交换机的向下转发表一定不包含其兄弟结点的信息从而具有树型结构的典型特点．（３）无论是真实的物理连接还是下行端口转发表均存在唯一的根结点．因为交换域中任一交换机的下行端口集合必然包含所有下行交换域交换机的物理地址．因此我们说具有图的特点．简言之，该数据结构是具有树的特点的图．下面给出树型图数学定义．树型图（Ｔｒｅｅｌｉｋｅ—Ｇｒａｐｈｉｃｓ）是一个包含ｎ个结点的有限集，在任意一棵非空树型图中：（１）有且仅有一个特定的称为根的结点（Ｒｏｏｔ）．（２）当ｎ＞ｌ时，其余结点可分为ｍ（ｍ＞０）个互不相交的有限集乃，兄，…％，其中每一个集合本身又符合本定义，并且称为根的子树型图（ＳｕｂＴｒｅｅｌｉｋｅ—Ｇｒａｐｈ．ｉｃｓ）．（３）任意一个结点都有指向其任意一个子孙的信息．这此一点与普通的树型结构截然不同．Ａｍ＂Ｔｒｅｅｌｉｋｅ—Ｇｒａｐｈｉｃｓ｛数据对象Ｄ：Ｄ是具有相同特性的数据元素的集和，称为顶点集．数据关系Ｒ：１６２４电子学报２００８焦若Ｄ为空集，则称为空树型图；若Ｄ仅含一个数据元素，则Ｒ为空集，否则Ｒ＝｛Ｈ｝，日是如下二元关系：（１）在Ｄ中存在唯一的称为根的数据元素ｒｏｏｔ，它在关系日下无前驱；（２）若口｛ｒｏｏｔ｝≠少，则存在口｛ｒｏｏｔ｝的一个划分Ｄ１，Ｄ２，……，Ｄ。（ｍ＞０），对任意＿『≠ｋ（１≤Ｊ，Ｉ｜｝≤ｍ）有ＤｊｎＤｋ＝①，且对任意的ｉ（１≤ｉ≤ｍ），唯一存在数据元素毛∈Ｄｉ，有＜ｒｏｏｔ，筏＞∈日；（３）对应于Ｄ－ｔｒｏｏｔ｝的划分，Ｈ－｛＜ｒｏｏｔ，戈ｌ＞，……，＜ｒｏｏｔ，戈。＞｝有唯一的一个划分日１，的某一结点子孙域）｛从ＴｒｅｅＲｅｓｕｌｔＱｕｅｕｅ删除该节点；将ＴＧＡｒｃ中的这一结点加入到ＴｒｅｅＲｅ．ｓｕｌｔＱｕｅｕｅ；｝｝ｒｅｔｕｒｎＴｒｅｅＲｅｓｕｈＱｕｅｕｅ；５无ＳｒＰ协议工作的数据链路层拓扑发现算法ＤａｔａＬｉｎｋＴｏｐｏＤｉｓｖｅｒ（ＩＰ—ＡｄｄｇａｔｅｗａｙＩＰ，ｃｈａｒ＊ｇａｔｅＣｏｍ－ｍｕｎｎｉｔｙ，ＩＰ—ＡｄｄＭａｓｋＡｄｄ）｛日２，……，巩（ｍ＞０），对任意＿『≠ｋ（１≤，，ｋ≤ｍ）有弓ｎ凰＝西，且对任意的ｉ（１≤ｉ≤ｍ），Ｈｉ是现上的二元关系，（现，｛Ｅ｝）是一棵符合本定义的树型图，称为根ｒｏｏｔ的子树型图．（４）Ｖ口∈Ｄ，口的子孙集合Ｗ，ＶＷ∈形，则必然存在关系ＶＲ＝｛＜ｔ，，埘＞Ｉｚ，∈Ｄ，Ｗ∈Ｗ且Ｐ（口，埘），＜＂，埘＞表示从ｙ到肜的弧，谓词Ｐ（移，埘）定义了弧＜口，Ｗ＞的意义或信息｝．基本操作Ｐ：对树和图的摹本操作均可移值到对树型图的操作，但本文重点阐述对我们有意义的操作一将该数据结构转换为树结构ＴＧｔｏＴｒｅｅ（ＴＧ，＆ｒ）．该操作实质上也完成了拓扑发现的工作，即无生成树协议工作情况下数据链路层拓扑信息的获得．｝４．２树型图基本操作ＴＧｔｏＴｒｅｅ（ＴＧ。＆Ｔ）算法描述．盹ｔｏＴｒｅｅ（１＿｜Ｇ，＆Ｔ）｛／／利用树型图生成对应的生成树ＱｕｅｕｅＴｒｅｅＱｕｅｕｅ；／／定义一个队列ＩｎｉｔＱｕｅｕｅ（＆ＴｒｅｅＱｕｅｕｅ）ＯｕｅｕｅＴｒｅｅＲｅｓｕｈＱｕｅｕｅ；／／定义一个队列ＩｎｉｔＱｕｅｕｅ（＆ＴｒｅｅＲｅｓｕｈＱｕｅｕｅＱｕｅｕｅ）ＴＧＮｏｄｅＬｉｎｋＥｌｅｌｉｌ＊Ｐ：ＴＧＮｏｄｅｊｕｄｇｅＤｅｖｉｃｅＴｙｐｅ（ｇａｔｅｗａｙＩＰ，ｇａｔｅＣｏｍｍｕｎｎｉｔｙ，）；／／判断是否为路由设备叔给出的ＩＰ设备不是路由器）｛返回｝ＳｕｂＡｄｄ＝ｇａｔｅｗａｙｌＰｎＭａｓｋＡｄｄ；／／计算当前网关该端口的网络号应用ＡＲＰ协议取得当前网关交换域的活动ＩＰ地址集合ＡＪｌ一Ⅲ；在口地址集合仙一Ⅲ中求得交换机地址集合ＳｗｉｔｃｈＳｅｔ；／／应用公理二在网关交换域中交换机地址集合ＳｗｉｔｃｈＳｅｔ中的根结点交换机ｆｏｒｅａｃｈＳｗｉｔｃｈ（ＳｗｉｔｃｈＳｅｔ）｛／／通过ｆｏｒｅａｃｈ循环寻找ｇｅｔＰｏｒｔＮｕｍ（Ｓｗｉｔｃｈ，ＳｗｉｔｃｈＣｏｍｍｕｎｉｔｙ）；通过上行端口转发的表项数目最少的交换机．ｔｅｍｐ２ｉｆ（ｔｅｍｐＭＩＮ＞ｔｅｍｐ）｛ｔｅｍｐＭＩＮ＝ｔｅｍｐ；｝｝ＲｏｏｔＩＰ＝ｔｅｍｐＳｗｉｔｃｈ；／／根结点交换机得到树型图ｒｉＧ；｝６实验验证与分析作者已编程实现上述算法１，并将其发布为ＷｅｂＳｅｒｖｉｃｅ．通过服务发布的内容包括：（１）发现的路由器集合．（２）已发现的路由器名称、接口地址、子网掩码和网络号的集合．（３）拓扑连接关系序偶的集合．通过在下一代中国教育科研网（ＣＥＲＮＥＴ２）上测试，算法完全达到了预期的功能．发现的ＣＥＲＮＥＩ［２拓扑连接设备与时间如图５（ｏ）所示，同时将该．算法在中国高速互连研究试验网络（ＮＳＦＣＮＥＴ）和中国教育科研网（ＣＥＲＮＥＴ）上实ｔｒｅｅＮｏｄｅ＝ＴＧ．ｎｏｄｅｓ［０］；Ｐ＝ｔｒｅｅＮｏｄｅ．ｏｆｆｓｐｒｉｎｇ；利用树型图生成对应的生成树Ⅱ挑（Ｔｃ，＆Ｔ）；Ｗｈｉｌｅ（Ｐ！＝ＮＵＬＬ）ＥｎＱｕｅｕｅ（＆ＴｒｅｅＱｕｅｕｅ，Ｐ）；Ｐ＝Ｐ－＞ｎｅｘｔ；｝ＴｒｅｅＲｅｓｕｌｔＱｕｅｕｅ＝ＴｒｅｅＱｕｅｕｅ；ＴＧＮｏｄｅＬｉｎｋＥｌｅｍ＊ＴＧＡｒｅ；３＂ＧＥｌｅｍＴｙｐｅｏｆｆｓｐｒｉｎｇ—ＩＤ；／／子孙Ⅲｗｈｉｌｅ（ＴＧＡｒｅ！＝ＮＵＬＬ）｛ＤｅＱｕｅｕｅ（＆ＴｒｅｅＱｕｅｕｅ。＆ＴＧＡｒｃ）；ｏｆｆｓｐｒｉｎｇ—ＩＤ＝ＴＧＡｒｃ．ｏｆｆｓｐｒｉｎｇ—ＩＤ；ＴＧＡｒｃ＝ＴＧ．ｎｏｄｅｓ［ｏｆｆｓｐｒｉｎｇ—ＩＤ］；Ｉｆ（ＴＧＡｒｃ中的某一结点子孙域＝ＴｒｅｅＲｅｓｕｌｔＱｕｅｕｅ万方数据 第８期陈福：网络拓扑发现新算法及其实现１６２５验，均验证该算法的有效性和高效率．由于无ＳＴＰ协议工作，目标网络规模不应该太大，否则就应该运行ＳＴＰ协议消除回路．因此作者在清华大学网络中心搭建了图５（ｂ）所示的工作环境，并采用Ｐｅｒｌ语言实现了原型系统，通过实验证明该算法的有效性，在极短的时间内发现了全部设备，达到了预期的效果．７结束语本文提出的口网络交换层拓扑发现算法突破了基于路由表方法的耗时、低效的缺点，通过推测、验证逐步从发现起点向外围拓展，并在条件允许时根据ＢＧＰ和ＡＲＰ协议进一步提高发现效率，与已有工作相比本算法具有Ｐ地址自动推理和查找范围自我调整因而具有很强的自适应性．该算法具有较高效率，实验结果和实际应用均表明该算法的高效性、实用性．本文提出另一算法解决了ＳＴＰ协议工作数据链路层拓扑发现问题的理论基础并实现了算法．同时引出一种新型数据结构类型Ｔｒｅｅｌｉｋｅ—Ｇｒａｐｈｉｃｓ．本文从理论到实现从根本上解决了相应约束条件的拓扑发现问题．参考文献：［１］ＢｃｎｏｉｔＤｏｎｎｅｔ，ＰｈｉｌｉｐｐｅＲａｏｌｌｌｔ，１＂ｍａｔｔＦｒｉｅｄｍａｎ．ＥｆｆｉｃｉｅｎｔＡＩ—Ｎｅｔｌｎｖｅｎｔ０皤ｙｇＹａｎｄ—２８４．辍２堍懋２１３９４，繇：。氍２１９，２４３，２１３，１３ｌ◇ｉｎ（６）耗费的时间变化图ｓｅｆｖｉ∞ＴｃＩｐｃｄｏ舒ＤｉｓｃａｖｅｒｙＳｙｓｔｅｍ［ＡＪ．Ｔｅｌ删ｃａｔｉｏｍＴｏｐｏｌｏｇｙｌ－Ｉｅｔｅｍ删Ｎｅｔｗ豳：慨ＮｅｔｗⅨ－ｋＳｍｉｔｅ—ＰＩａｒＩｎｉｌ培Ｓｙｍｐｏｓｉ岫［Ｃ］．Ｖｉｅｍｌａ：Ｈｅｍｌｅ咖，２００４．２７９ＭＩＢ．Ｉｎｌｅｍｅｔ［６］Ｂｉｅｎｎ锄Ａ，Ｊｂ峨Ｋ．１ｍｙｓｉｅａｌ２９２２［Ｓ］．＆：ｐＩ啪ｂ盯２０００．［７］ＹｕｒｉＤｉｓｃ叫ｅｒｙｉｎＲ雕Ｂ佗ｉｔｂａｒｔ，‰Ｇ甜－ｏｆａｌａｋｉｓ，ＣｌｉｆｆＭａｒｔｉｎ，ｅｔａ１．ＴｏｐｏｌｏｇｙＨｅｔｅｍｇｅｎｅｏ吣ＰＮｅｔｗｏｒｋｓｌＡ］．ｎＤｃ∞ｄｉｌｌｇｓｏｆＩＮＮ３ＣＯＭ２０００［Ｃ］．Ｔｅｌ－Ａｖｉｖ．－ＩＥＥＥＩＮＮ）ＣＯＭ，２０００．２６５一Ｚ７４．［８］ＹｕｒｉＢｒｅｉｔｌ柏ｒｔ，ｈ恤∞Ｇａｍｆａｌａｂｓ，战ａ１．Ｔｃ｜ｐｏｌｏｇｙｈｃ姐Ｄｇ脚印峪口Ｎｅｔｗｏｒｋｓ：ｔｈｅＩＥＥＥ／ＡＣＭ４１４．Ｎｅｔｄｉｓｃａｖｅｒｙｉｎｇｏｒｉｔｈｍｓｆｏｒｌａｒｇｅ－ｓｃａｌｅｔｏｐｏｌｏｇｙ２００５ＡａＭＳＩ（瓣Ｉ∞ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｌｌｆ粼ｏｎＭｏｄｅｔｉｎｇｏｆｄｉｓｃｏｖｅｒｙ【ＡＪ．Ｐｒｏｃｏｆ位ＭｅａＩＴｒａｍ，咖ＯｎＮｅｔｗａ＇幽ｇ，２１１０４．，１２（３）：４０１—ｉｎｖｅｎｔⅨｙｓｙｓｔｅｍ［Ｊ］．ｓｕｒｅｍｅｎｔａｎｄ刎．３２７—３３８．ｅ￡ｙｆｂｒＣ（和ｐＩＩｔｅｆＳｙｓｔｅｍｓ［Ｃ］．Ａ例Ｐｒｅｓｓ，［９］Ｙａｍ∞ｓ岫，动ｉｌＩｌｅｉｄｉｓｃｏｖｅｒｙＷｕ，蕊ｑｉ粕ｇＳｈ．Ｔｈｅｏｎｐｈｙ剃ｍｐｏｌｏｇｙＴｅｄ瑚ｌｏｇｙ，ｆｏｒｓｗｉｔｃｌＨｌｅｔｂｅｍｅｔｂａｓｅｄｃ（ｍ啦：ｃｌｉ册ｓｍ锄砌Ｄｇ［２］ＤａｎｉｅｌＧ．Ｗａｄｄｉｎｇｔｏｎ，ＦａｎｇｚｈｅＣｈａｎｇ，ｅｔａ１．Ｔｏｐｏｌｏｇｙｄｉｓｃｏｖ－Ｏｆｔｅｃｌｌｎｉｑｕｅ［Ｊ］．ｃｂ皿衄瞰血捌姗锄ｄ２００５［ｃ］．正髓Ｉｎｔｅｍａｔｉｏｍｌ—４７．ｐｕｂｌｉｃⅢｖ６Ｎｅｔｗｏｒｋｓ［Ａ］．ＰｒｏｃＡＣＭＳＩＧａ０ＭＭＣｏｍｐ岫Ｃｏｌｍａｔｍｉｃａｔｉｏａ＆婀鲫［Ｃ］．Ａａ垤Ｐｒｅｓｓ，２００５．５９—６８．ｓｙ叫妇２００５，１（１２—１４）：４４Ｉｎｆｏｒｍａｔｉｏｎ［３］Ｎｉｃｋ糊ＩｎｔｅｍｅｔｒｏＩｎｊｎｇ【ＡＪ．ＰｒｏｃｏｆｔｈｅＡｏ订ＳＩＧ℃洲Ｗｏｒｋ－ｓｂ印ＯｎＦｕｔｕｒｅＤｉｒｅｃｔｉｏｎｓＦｅａｍｓｔｅｒ，ＨａｆｔＢａｌａｋｒｉｓｈｎａｎ．Ｔｏｗａｒｄｓａｌｏｇｉｃｆｏｒｗｉｄｅ－作者简介：陈播男，１９７３年生于辽宁朝阳，北京科技大学／清华大学联合培养博士，研究生，讲师．研究方向：服务管理、网络管理、虚拟现实技术、ｉｎＮｅｔｗｏｒｋＡｒｃｈｉｔｅｃＵⅡｅ［Ｃ］．枷ＮｅｔｌｎｖｅｎｔｏｒｙＰｒｅｓｓ．２００３．２８９—３００．［４］ＹｍｉＢｒｅｉｔｂａｒｔ，ＭｉｎｏｓｏｇｙｄｉｓｃｏｖｅｒｙｉｎＧａｒｏｆａｌａｋｉｓ，ＢｅｎＪａｉ，Ｃｌｉｆｔｏｎ，ｅｔａ１．Ｔｏｐｏｉ．嵌入式系统．ｓｙｓｔｅｍ［Ｊ］．皿／ＡａｖＩ（３）：加ｌ一４１４．［５］Ｎａｒａｙａｎｋ艟∞舒租飘玛ＩＰｎｅｔｗｏｒｋｓ：ｔｈｅＴｒａｎｓａｃｔｉｏｎｓＯｎＢｌｎａｉｌ＿，ｄ】目击ｍｍ＠删．ⅢＮｅｔｗｏｒｋｉｎｇ．２００４。１２ＰＰＳ，ＢｒｉｅｔｂａｒｔＹ，ＧａｒｏｆａｌａｋｉｓＭ，ｅｔａ１．Ｐｈｙｓｉｃａｌａｎｄ万方数据 网络拓扑发现新算法及其实现
作者：作者单位：
陈福， 杨家海， 杨扬， CHEN Fu， YANG Jia-hai， YANG Yang
陈福,CHEN Fu(北京科技大学计算机科学与技术系,北京,100083;清华大学信息网络工程研究中心,北京,100084)， 杨家海,YANG Jia-hai(清华大学信息网络工程研究中心,北京
,100084;清华大学信息与科学国家实验室,北京,100084)， 杨扬,YANG Yang(北京科技大学计算机科学与技术系,北京,100083)电子学报
ACTA ELECTRONICA SINICA2008,36(8)1次
刊名：英文刊名：年，卷(期)：被引用次数：
1.Yantao Sun;Zhimei Wu;Zhiqiang Sh The physical topology discovery for switched ethernet based onconnections reasoning technique[会议论文] 2005
2.Yuri Breitbart;Minos Garofalakis Topology discovery in heterogeneous IP Networks:the Net inventorysystem 2004(03)
3.Yuri Breitbart;Minos C;arofalakis;Ctiff Martin Topology Discovery in Heterogeneous IP Networks2000
4.Bierman A;Jones K Physical Topology MIB 2000
5.Narayan P P S;Brietbart Y;Garofalakis M Physical and Service Topology Discovery in HeterogeneousNetworks:the Net Inventory System 2004
6.Yun Breitbart;Minos Garofalakis;Ben Jai;Clifton Topol-ogy discovery in heterogeneous IPnetworks:the Netlnventory system[外文期刊] 2004(03)
7.Nick Feamster;Haft Balakrishnan Towards a logic for wide-area Imteenet routing 20038.Daniel G.Waddington;Fangzhe Chang Topology discov-ery for public IPv6 Networks 20059.Benoit Donner;Philippe Raoult;Timur Friedman Effcient AI-gorithms for large-scale topologydiscovery 2005
1.张晨.杨云.许宁 多结点IP网络中的拓扑发现[期刊论文]-商场现代化 2009(14)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_dianzixb200808026.aspx
