摘要摘要：在大中型计算机网络中，网络管理是确保网络持续正常运行的关键，而网络管理的基础是网络拓扑发现。网络层拓扑结构自动发现技术已颇为成熟，链路层因为其透明性，导致发现难度较大。阐述了国内外网络拓扑发现算法研究现状，重点对链路层网络拓扑发现算法进行了研究。
关键词关键词：拓扑结构；自动发现；链路层；SNMP
DOIDOI：10.11907/rjdk.1511331
中图分类号：TP312
文献标识码：A文章编号文章编号：16727800（2016）002005703
0引言
当前，网络管理已逐步实现智能化、可视化，网络拓扑自动发现是网络管理实现故障快速发现和准确定位的重要参考。随着网络拓扑结构和组成的日渐复杂，人工维护网络拓扑越发困难，自动发现网络拓扑结构的需求更加强烈。纵观国内外关于自动发现网络拓扑结构的研究，网络层设备发现技术已经较为成熟，而链路层发现因其透明性，仍值得深入探究。
1国内外研究现状
近年来，互联网变得更加复杂且庞大，对互联网进行网络拓扑发现也变得愈加困难和复杂。因此，关于网络拓扑结构发现的研究是一项具有挑战性的工作，尤其在工程领域和军事工业领域有着巨大应用价值。国内外很多专家和机构对网络拓扑结构发现进行了大量研究。
数据链路层的拓扑发现能方便地使用简单网络管理协议，HwaChim Lin等通过Bridge的信息库管理方式将交换机的连接信息采集出来，这样做会导致拓扑发现结果不准确。著名贝尔实验室的Yuri Breitbart、卡耐基梅隆大学的Brucelowekamp，以及我国相关学者[13]分别在地址转发表的基础上进行了物理拓扑发现算法的改进。Breitbart算法是在各网桥地址转发表均一致的基础上改进的，因此该算法利用Bridge地址转发表来探测获取拓扑信息；Bruce的算法主要适用于网络中使用了Hub所产生拓扑发现问题的情况。国内学者通过对现有网络增加额外流量来维护转发表，从而改进了网络拓扑发现算法，并且成功实现了链路层网络拓扑发现。
2链路层拓扑发现
因为网络拓扑结构包括网络层和链路层。一般目标
网络内包括主机、集线器、交换机、路由器等设备。链路层中的连接关系主要有网络设备与交换机之间的连接、交换机与交换机之间的连接。
链路层拓扑信息在网络管理中非常重要，但该信息内容很难得到。以太交换机硬件相互之间的透明性，导致链路层拓扑发现异常复杂。子网中交换机只有在执行生成树协议STP时才与相邻设备进行信息交换，并且该协议也并非在所有环境中都可以使用。交换机可以保存转发数据库，交换机主程序将收到的数据包参照该数据库将数据包转发到相应的端口。链路层拓扑发现有这些信息即可，这些信息可以利用SNMP协议的标准MIB来获取。交换机之间的连接关系确定了整个局域网的拓扑结构[4]。
图1为链路层模型图，包含了多个交换机、主机。交换机可以和其它交换机通过各自的端口相连，主机可与交换机相连，也能够连接在集线器上。图1中，交换机设备和集线器等设备组成的局域网能够被分为交换设备集合P与端点集合C。在图中表示为：P={C，D，A，B}，C={Z，X，W，Y}。交换机能够通过各端口使该网络的其它设备连接到一起。集线器是用来将若干台主机设备连接到一台交换机的同一个端口的设备。本文称不支持SNMP的交换机为哑交换机。
在以太局域网中，交换机和交换机以及转发集的连接关系绝不会是环路，即便本来有环路，交换机也能够利用STP算法选择一个不存在环路的路径。若从某节点发出的报文经过交换机的某个端口，则该交换机可以记录该报文的源地址和对应的端口。在以后的数据传输中，如果交换机发现接收到发往该地址的报文，就会自动地转发到对应的端口，这些数据包的源地址和对应端口的关系构成了交换机的FDB。然而在交换机的FDB中，每个端口都是和多个设备的物理地址对应，对于某个交换机的端口，将物理地址所从属的设备集合叫作该端口的转发集。在图1中， FxC能够代表交换机C的x端口转发集，假设x为1，有F1C={A，Z ，B，D ，X，W}，如果某端口连接的所有设备都被包含在该端口的转发集中，则说明该转发集完整，从图中可知F1C是完整的[5]。
2.1交换机之间的直接连接定理
假设两个不同的交换机节点互相连接，而且没有任何其它设备在它们之间，则称该连接是直接连接。如果有其它设备在两个节点的中间，则称该连接是间接连接。需要注意的是：直接连接仅仅是间接连接的特殊情况。由图1可知，交换机设备B与A通过端口4和1直接连接，交换机C和交换机A通过1和1端口间接连接。
从链路层拓扑发现的原理可知，若可以得出两个交换机的某些端口之间是否有直接连接关系，就能够容易地得出该网络中的交换机互联关系，则交换机和主机的连接关系也可以很容易被发现。在图1中，假设F1B与F1C全是完整的，也即F1C={A，B，W，X，D，Z}，F1B={C，Y}。可以得出结论：F1B∩F1C=ф（空集），F1B∪F1C=N（N是图中主机设备的全集）。此结论的得出并非巧合，原因是：假设两个交换机设备通过端口x和y进行直接连接，并且路径中也没有任何其它网络设备，则以两交换机相连处为中间线，该网络中主机设备可以分成两部分：一部分是端口x所对应一侧，也即FxA，另一部分是端口y所对应一侧，也即FyB。因此，FxA∪FyB=N。
可以这样描述直接连接定理：如果FxA和FyB同时都完整，则A通过x端口和B的y端口进行直连的充要条件为：FxA∩FyB=ф并且FxA∪FyB=N。
通过上述直接连接定理，能够很容易地遍历局域网中所有交换机的FDB，之后再对不同交换机的端口转发集作“并”运算操作，若运算结果为全集并且“交”运算操作的结果是空集，则可以说这两个交换机通过这两个端口直接连接。然而。直接连接方法存在一个很大缺陷，即必须要求交换机的端口转发集全部是完整的。但在实际应用中，当网络规模不断扩大时，几乎不可能获得完整的端口转发集。因此，上述直接连接定理的方法就不适用实际网络环境了。
2.2交换机之间的间接连接定理
与直接连接定理不同，间接连接定理方法的思想是：通过反证法，依次否决掉没有可能的连接。通过反证法判断连接的例子如图2所示。
首先可以假设交换机A与交换机B间接连接，然后判定此连接是否和交换机A、B中的FDB信息相矛盾。若找不出矛盾，则可以说该连接可能存在；若有一条矛盾，就可以说该连接肯定不存在。由图2可知，交换机A与B的连接可以有6种关系，如图3所示。
假设A、B通过端口1、1进行间接相连，图2表示了图3列举的第一种情况。在以太局域网中，交换机设备相互连接成树状的结构，不能存在环路。因此，此时该网络应该被分成3个部分。首先是交换机A的2和3端口连接的设备；其次是交换机B的2端口所连接的设备；然后是交换机A、B和两者中间的设备。但是事实是：第一部分为F2A∪F3A，第二部分为F2B，这两部分不可以有交集。因为（F2A∪F3A）∩ F2B ≠ф，所以该事实情况和交换机A通过端口1和交换机B的端口1相连是矛盾的。事实上，除非两个端口之间是间接连接，则不同交换机上的两个端口转发集不能有相同的元素。如果有相同的元素，就相当于某个设备同一时刻存在于网络的不同位置，这显然不正确。图3中列出了5种情况，很显然只有第5种情况正确，其它情况都不对。真实的情况是交换机A和B通过端口1和2相连，该连接不一定是直接相连，也可能是间接连接。
间接连接判定交换机连接关系可以不用完全获取所有交换机的端口转发集，利用已知信息排除所有不可能存在的连接即可。 首先依次组合两个交换机的所有端口，分别对交换机剩下端口的转发集做并运算，然后将得到的两个转发集再做交集运算。如果结果为空，则说明两个交换机相连，直接相连是间接相连的一种特殊情况。
2.3通过间接连接定理判定直接连接关系
假设目标子网内，交换组成的集合是G。由STP协议可知，交换机之间是构成树的组织结构。选择任意交换机Si作为根交换机节点，设Si经过n个端口和其余交换机构成间接连接结构，则可以将G-{Si}构造成一个划分Ti，该划分中可以包括n个元素，并且每一个元素都是与Si的某个p端口进行间接连接的交换机设备集合，可以设为Gp。在Gp内选中交换机Sj，能够推出：Sj与Si之间一定是通过某个端口q、端口p进行间接连接。如果Sj没有经过端口q和Gp中其它交换机（记录Si的p端口转发集）间接连接，则能够判断出Sj与Si通过端口q和p是直接连接。
3结语
网络拓扑结构自动发现包括网络层拓扑发现和链路层拓扑发现，网络层拓扑发现已发展成熟。本文详细介绍了链路层拓扑发现中用到的“直接连接定理”和“间接连接定理”，通过此两种定理可以快速、有效地勾画出链路层设备拓扑结构，使得完全拓扑结构发现得以实现，对现代网络管理意义重大。
参考文献参考文献：
[1]宋翠.网络拓扑发现算法的研究[J].企业导报，2014（16）：137146.
[2]焦彦平，李唱，陈东宁.基于协议的网络拓扑发现算法研究[J].科技创新导报，2014（20）：4650.
[3]牛新征，梁帆，周明天.基于无线传感器的物联网网络拓扑发现算法研究[J].计算机科学，2012（4）：118122.
[4]吴远，李润知，刘亚珂.网络拓扑发现算法的分析[J].电子技术应用，2006，32（8）：2831.
[5]刘海华，王萍萍.基于生成树算法的链路层拓扑发现研究[J].计算机技术与发展，2008，32（5）：101104.
责任编辑（责任编辑：孙娟）