基于多协议的跨VLAN的异构多子网物理拓扑研究

马晓波，苏依拉，仁庆道尔吉

（内蒙古工业大学 信息工程学院，内蒙古 呼和浩特 010080）

0 引 言

异构网络主要是指由不同品牌、不同类型的设备和系统所组建的计算机网络。对种类繁多的网络设备所搭建的异构网络进行有效管理已经成为一个网络系统高效运转的关键因素。由于VLAN间的子网不允许直接进行通信，需要通过三层通信才能实现VLAN间的互相访问，而且网络中存在不同厂商的网络设备，这些设备具有多样性且支持不同通信协议，没有为物理拓扑发现直接提供所需的信息。因此，设计一种基于异构跨VLAN的多子网物理拓扑发现方法，具有实际的工作价值和进一步推广的意义。

对现有的几种物理网络拓扑发现算法做了深入的研究分析：基于AFT的物理拓扑发现算法要求网络中周期性地产生额外流量用以维护AFT的完整，并且对于哑设备的判断需要单独进行考虑，而且随着网络规模的不断扩大，要求在短时间内准确获得设备的MAC地址会有一定的困难；基于端口流量的物理拓扑发现算法虽然简单，但仍需要进行大量运算，一般只能用于对其他拓扑发现算法进行补充；基于ARP的物理拓扑发现算法需要三层网络支持；基于STP的物理拓扑发现算法不能够直接发现网桥与路由器、主机等设备的连接关系。综合对比上述算法，本文提出一种综合利用STP和AFT信息的组合式拓扑发现算法，算法借助SNMP取得交换机所维护的MIB库中生成树和地址转发表的相关信息，经过查找对比，从而判定出交换机及其他网络设备的连接关系，在此基础上根据获取到的VLAN的OID信息进行判断，完成VLAN的处理工作，最终获得跨VLAN的异构多子网的物理拓扑结构。

1 基于STP和基于AFT的物理拓扑发现方法

1.1 基于AFT的物理拓扑发现算法

算法过程描述如下：

1）定义交换域中所有交换机的集合；

2）对于每个集合，分别取出一台交换机Si，遍历其每个端口Si j；

3）若交换机Si的端口Sij已经与其他设备的端口互联，则转到步骤2）执行；

4）若Aij∪Akl=U且Aij∩Ak l=∅，则交换机Si的端口Si j与交换机Sk的端口Skl直连。若Aij中含有主机或者路由器的MAC地址，则交换机Si的端口Si j与路由器或者交换机直连。

该算法主要利用Bridge MIB⁃Ⅱ的地址转发表中二层设备间的物理连接关系以及特殊场景下的共享网络。由于所有交换机都基于AFT转发数据，因此能够访问其所需的AFT。但要求交换机都能够支持SNMP协议，而对于网络底层的设备并不能统一地支持SNMP协议，这在一定程度上产生了局限性。由于该算法对网络环境具有较高的要求，所以在现实网络中难以保证交换机的地址转发表AFT始终完整。

1.2 基于STP的物理拓扑发现算法

算法过程描述如下：

1）分配内存并初始化；

2）对网络中临时交换机集合所包含的各个交换机进行信息探测，获取其IP及MAC地址；

3）根据交换机的IP地址，通过SNMP访问临时集合所包含交换机的MIB库；

4）采用广度优先遍历的方法，将根交换机的信息加入到交换机集合中，并创建搜索指针指向根交换机；

5）以根交换机MAC地址为索引，将根端口为索引的MAC地址处于临时集合中的交换机依次查找出来，然后加入到交换机集合；

6）重复搜索直到所有的交换机均加入到交换机集合中；

7）若临时集合中还有未按索引查找到的交换机，则查询交换机的指定网桥，如网桥不存在则将该交换机加入至交换机集合，然后将指针指向该交换机，重复步骤4）~步骤6），如存在指定网桥则说明有集线器等共享网络设备相连；

8）遍历数据，查询交换机的端口信息；

9）排除指定网桥；

10）查询交换机的阻塞端口所对应的指定网桥，将其连接信息填入到相应的端口信息中；

11）Ping网络内的所有设备，并访问交换机的地址转发表，填入信息。

该算法可以得到网络设备的物理连接关系，也可以发现大部分的哑交换机及其MAC地址与所连端口的关系，还可以发现局域网中的备用链路，发现的准确率较高。由于端口的STP信息少于端口的AFT信息，所以该算法拥有较低的时间复杂度，该算法不能够直接发现网桥与路由器、主机等设备的连接关系，同时也有可能使部分设备不支持STP协议，因此，可考虑在STP发现算法的基础上应用基于AFT的发现算法，进一步完成对整个网络的拓扑发现。

2 改进的物理拓扑发现方法

2.1 改进基于STP的拓扑发现算法

网络中的交换机通过定期交互BPDU（网桥协议数据单元）完成生成树的计算，选出数据转发端口和阻塞端口，然后将阻塞端口禁用，构造一个无环的、逻辑上的树，当网络中出现故障导致网络的物理结构发生变化时，交换机会再次根据BPDU信息重新计算并生成无环网络。

本文所用到的定义：拥有最小桥ID的交换机被称为根桥；除根桥外，其他交换机称为非根桥；在非根桥设备上负责向根桥转发数据的端口称为根端口；指定交换机也称为指定网桥，由处于同一子网下（即相同网段）的交换机选举得出；指定交换机向本网段转发配置消息的端口即为指定端口；转发端口包括根端口和指定端口，用来转发数据流量；除转发端口外的其他端口都处于阻塞状态，称为阻塞端口。

推论1：在STP网络中，如果两个有直接关系的端口都为根端口，说明两个端口必定处于同一条物理链路，由此可推出必处于同一网段，这样就会在同一网段内存在两条路径到达根桥设备，从而形成环路，该推论与STP的定义矛盾。

推论2：在STP网络中，如果两个有直连关系的端口都为非根端口，首先说明两端口必定处于同一条物理链路，由此可推出它们必定处于同一网段，并对该网段的数据帧进行转发，无根端口，同一网段下无根端口与根桥设备相连和前置条件相矛盾。

由上述两个推论过程可知，当两交换机的端口间存在物理连接时，有可能是一个端口发送的BPDU消息被另一个端口接收，则可推断出这两个端口中必定有一个为根端口。由此可以得出，存在直连关系的两个端口不可能同时为非根端口，如果两个非根端口处于同一网段，则必有一个端口无法转发数据，即为阻塞端口。就单台设备而言，非根桥设备的转发端口的指定交换机都是该设备本身。

根据上述推论结合MIB库中dot1dStp Port Table表的对象值可推导出如下判断规则：

设备连接关系判断规则1：设交换机Si的某个根端口为Sij，Si j的指定交换机为Sk，当交换机的非根端口Sk l与Si j的指定端口信息相等时，可知端口Skl发送的BPDU被端口Sij接收，所以可以推断出交换机Si与Sk之间必定存在物理链接，即端口Sij与端口Sk l直连。

设备连接关系判断规则2：设交换机Si的某个非根端口为Si j，交换机Sk的某个非根端口为Skl，当Sij的指定交换机为Sk且Si j与Sk l的指定交换机相同时，即端口Sk l的指定交换机为设备本身，如果端口Sij为阻塞端口，则其阻塞端口的指定交换机不是设备本身，可以判断出端口Si j与端口Sk l直连，且该端口用于连接备份链路。

设备连接关系判断规则3：设交换机的某个非根端口为Sij，若Sij与子网内边缘设备（例如主机、路由器等）直接连接，可获取MIB⁃Ⅱ中的sysService变量判断该设备是否提供二层服务，根据OID信息区分出主机设备为路由器或主机之后，可知端口Ai j内必定含有直连主机MAC地址信息。

将上述设备连接关系的判断规则在实际中进行应用时，只需将规则与dot1dStpPortTable表中的对应信息结合，根据生成树协议的特点，便可判定出相应设备间的连接关系。利用规则1可以准确获取交换机间的连接关系；利用规则2可以发现交换机的冗余链路。

2.2 改进基于AFT的拓扑发现算法

先将交换域构建成一棵无向树，若某交换域中只含有一个子网，则Ai j就在交换域所构建的无向树的路径中，交换机端口Sij所能到达的节点的集合，如果AFT表是完整的，那么Aij就包含生成树的路径中全部节点的集合。值得注意的是，当交换域中不止含有一个子网时，上述情况不适用。当交换域中有多个子网时，尽管该交换域中的所有交换机端口的地址转发表都完整也无法得到唯一的拓扑连接关系。本文构建的基于AFT的拓扑发现算法主要是对树型剪裁算法进行改进。

定理1：叶交换机只有一个端口的AFT含有其他交换机的地址。

定理2：中间交换机要么至少有两个端口的AFT含有其他交换机的地址，要么一个端口的AFT含有其他交换机的地址并且至少存在一个端口含有的叶子节点地址分布在其他交换机的不同端口上。

树型剪裁算法的主要思想：如果一棵树的叶子节点被摘除，被摘光叶子的树的分叉就会变成新的叶子节点，以此类推直到这棵树被逐步裁剪完。改进的树型剪裁算法适用于多子网交换域的网络，不需要定期发送数据流量来尽量保持AFT表的完整。下面介绍改进算法的核心思想：

1）定义交换机的集合为H（集合H中包含交换机的地址以及交换机端口的地址转发表）；

2）利用文献[1]中已经证明的基本推理规则进行AFT的扩展；

3）确定叶交换机Sk，找出交换机Si中只有一个Aij包含其他交换机地址的交换机作为备选的叶交换机（根据其是否在H中确定）（定理1），然后再根据定理2去掉其中的中间交换机，最后将所有叶交换机从H中剪掉。若叶交换机的某个下行端口中出现了多个叶子地址，则表示该叶子与HUB等哑设备相连；

4）更新交换机集合H中的地址转发表。在剩余端口的Ai j中，交换机的地址为剪掉的叶交换机端口含有的地址全部更新成叶交换机Sk的地址（该过程等同于将剪掉的Sk用新的叶节点进行了替换），然后将重复项进行合并，再转到步骤3），直至H中只含有根节点。

改进后的算法复杂度为O（n2），n表示网络中节点的个数。算法只需利用交换机的地址转发表，对主机的地址转发表没有要求，而在现今的网络中很多主机是不支持SNMP协议的。所以，改进后的算法能够适用于现实中的网络环境。

2.3 组合STP和AFT的拓扑发现算法

2.3.1 算法理论依据

组合式算法的合并思想是从STP算法的根节点开始，先找到AFT算法中所输出的对应节点，然后把这个节点作为AFT算法的新根节点，以此类推。这样，就可以每次都从相同的根节点去进行广度优先遍历，然后再对节点的连接关系进行合并。对任意节点Si的合并规则：

1）如果STP算法和AFT算法对某个节点端口Sij的连接关系发现结果相同，则保留STP算法的发现结果，忽略AFT算法的发现结果；

2）如果AFT算法发现了某个节点端口Si j和某个设备存在直接连接关系，而在STP算法中没有相关的发现，则对这个连接关系进行补充；

3）如果STP算法和AFT算法对某个节点端口Sij的连接关系发现结果不同，则认为存在哑设备（比如HUB）连接了该节点端口Sij与所发现的不同设备，即通过加一个哑设备将不同设备进行合并。

广度优先遍历完成后，就完成了所有节点的连接关系合并。这样，组合式算法中算法合并阶段的算法复杂度就从O（n2）降到了O(nlogn)，节省了拓扑发现的时间。而且对于STP算法没有发现的相应主机、路由器等设备的连接关系，可与AFT算法的相应发现结果进行合并，这样就整合了两种拓扑发现算法的优势，不仅对交换机之间的拓扑连接关系进行了补充，又对非交换设备的连接关系进行了补充。

合并算法运行结束后，再对可能出现的共享介质做进一步判断，下面对共享介质在网络中的场景予以分析：

场景1：当共享介质位于交换域的边缘，处在交换机和主机设备间，用来连接主机设备时，对设备连接关系判断规则并没有影响，可以正常获得主机与交换机的连接关系。

场景2：当共享介质位于两台交换机之间用以代替两台交换机之间的直连物理链路时，此时利用规则1无法判断并获取共享介质信息。

场景3：当共享介质位于多台交换机之间时（两台以上），会有两个以上的根端口存在直连关系，此时规则1不成立。

针对上述场景，推导出如下连接关系的判断规则：

设交换机Si的根端口为Si j，Sij的指定交换机为Sk，当交换机的非根端口Sk l与端口Sij的指定端口信息相等时，端口Sij与Sk l直连，若此时还有其他端口Smn与端口Sk l的指定端口信息相等，则在交换机Si，Sk，Sm之间存在共享介质。

根据设备连接关系判断规则1还可以得出，当端口Sij和Skl直接连接时，若Aij∩Akl≠{∅}，则这两个端口间存在共享介质。

共享介质连接关系判断规则1：当共享介质位于网络边缘用以接入主机设备的时候，对网络拓扑结构不产生影响，那么交换机Aij中所包含的MAC地址均为主机MAC地址，利用设备连接关系判断规则3可得出交换机、共享介质及下联所有主机的连接关系，从而得出场景1的拓扑关系。

共享介质连接关系判断规则2：根据设备连接关系判断规则1，如果当有Aij∩Akl≠{∅}时，则可得出在交换机Si与Sk之间存在有共享介质，并且通过Sij端口与Skl端口进行连接，从而推出场景2的拓扑关系。

共享介质连接关系判断规则3：当交换机Si在满足设备连接关系判断规则1的情况下，根端口Sij与多个端口的指定端口信息相等时，则说明交换机端口Sij连接有共享介质，相等的端口同时接入共享介质，从而推导出场景3的拓扑关系。

2.3.2 算法描述

具体算法的实现步骤简述如下：

1）利用SNMP协议取得交换机列表与生成树端口表，并读取相应的地址转发表信息。

2）根据设备连接关系判断规则得到交换机的端口之间的连接关系，从而得出交换机与交换机的直连关系。

3）运行改进的树型剪裁算法，得到AFT算法的拓扑发现结果。

4）运行广度优先的组合式算法，合并STP算法和AFT算法的拓扑发现结果。

5）将连接关系中各端口出现的频率进行统计，如果某一个端口出现的频率多于一次，则该端口与共享介质间存在连接，再取得剩余端口的地址转发表，如果交集为非空，则两端口间存在共享介质。

6）根据设备连接关系判断规则3收集步骤2）推导出的与交换机相连的主机的MAC地址信息。如果该端口中主机数量大于1，则该端口连有共享介质，再根据共享介质连接关系判断规则对共享介质连接关系进行推导。

7）获取交换机的VLAN标识dot1qPvid，将取值相同者置于同一集合，dot1qPvid取值即为VLAN号。

8） 获 取 索 引 值 dot1qVLANIndex、列 表dot1qVLANCurrentEgressPorts的内容，得出每个VLAN的所有端口信息。值得注意的是，对VLAN信息进行处理时，dot1qVLANIndex参数不能直接被读取，可通过SNMP提 供 的GetAll List（）方 法（SNMPv1版 本 采 用getnext（）方法）得到对应的OID与Value。然后将条目中的索引值分离出来即可得到每个VLAN所包含的交换机以及端口的信息。

9）根据获取到的设备信息进行判别，收集设备的OID信息。

具体的拓扑发现流程如图1所示。

图1 拓扑发现流程图

2.3.3 算法测试验证

基于实际情况，选用某公司的网络作为测试网络。该网络环境相对较复杂，可以满足本课题研究的异构性（满足厂商的多样性）。整个网络划分了上百个VLAN，且符合现代较为主流的网络规划标准，完全可以满足本课题对于多子网的网络环境要求。由于网络规模相对比较大，系统的拓扑发现时间在3 min左右，进一步验证了本组合式物理拓扑发现算法在真实网络环境中的有效性和可行性。

图2 是对该公司的部分网络进行测试所得的结果。

图2 实际网络测试结果

3 结 语

准确的网络拓扑结构对于网络管理、安全管理、性能分析等起着非常重要的作用。本文以基于STP的算法为基础，利用改进后基于AFT的算法进行扩充，最后根据合并规则将两种算法的拓扑发现结果进行有效的融合，实现了跨VLAN的异构多子网的物理拓扑发现，避开了网络拓扑发现协议不一致，网络设备多样性等带来的困难，在地址转发表不完整的情况下能够准确、全面、高效地发现网络设备。实验表明，算法从完整率、准确率、网络负载等指标的综合情况来看，有一定的优势，并且可以作为一种有效的算法应用到实际的跨VLAN的异构多子网环境中，具备一定的实用价值和推广意义。