摘要 本文 分析 了现有的以太网链路层拓扑发现算法，在此基础上提出了改进算法，给出了算法的基本实现 方法 。新算法放宽了原算法中的条件限制，使得算法的 应用 范围更广，适应性更强。新算法可以发现 网络 中原算法无法发现的设备。
关键词 链路层 拓扑 SNMP
1 引言
随着 计算 机性能的提高及通信量的巨增，传统局域网已经愈来愈超出了自身的负荷，交换式以太网技术应运而生，大大提高了局域网的性能。与过去基于网桥，集线器，路由器的共享媒体的局域网拓扑结构相比，网络交换机能显著的增加带宽。交换技术的加入，就可以建立地理位置相对分散的网络，使局域网交换机的每个端口可平行、安全、同时的互相传输信息，而且使局域网可以高度扩充。局域网交换机根据使用的网络技术可分为：以太网交换机、令牌环交换机、FDDI交换机、ATM交换机、快速以太网交换机。由于以太网的简单与易用性，所以 目前 大部分的LAN均采用了以太网交换机与快速以太网交换机作为自己的网络交换设备。本文中的链路层拓扑发现正是针对以太网中的二层设备。
国内对拓扑发现技术的 研究 还集中在三层拓扑发现上，忽视了二层拓扑发现的重要性。在内网或者局域网，往往都是以交换机为中心来连接机器，而三层拓扑发现是无法实现这样的网络环境下的拓扑发现的。
2 现有链路层拓扑发现算法
从交换机工作原理[2]上我们能够发现，交换机并未提供一种有效、直接的方法确定其直接连接的设备。对于一个异构的网络我们唯一可行的方法就是利用SNMP中的MIBⅡ bridge组的信息（各个厂家都实现），得到交换机的地址转发表，并分析其特性，找到一个合理的算法，来确定物理网路的拓扑关系。
2.1 现有算法描述
链路层拓扑自动发现算法的目标是找出子网内交换机与交换机、交换机与路由器、交换机与主机之间的连接关系。其中找出交换机与交换机之间的连接关系是链路层拓扑自动发现的关键所在。贝尔实验室的Yuri Breitbart给出了基本算法[1,4,5]。算法 理论 基础和描述如下：
定义l：令交换机，路由器组成的二层主干结构为图N，N中第i台交换机为Si,其第j个端口为Sij。
定义2：令任意端口Sij，Dij表示交换机Si的地址转发表中通过端口Sij 收到的数据帧中源MAC地址集合。
定义3：令任意端口Sij, Lij表示交换机Si的地址转发表中通过端口Sij收到的数据帧的源MAC地址为交换机的集合。
定义4：若一台交换机Si其端口Sij的Lij中未出现其它交换机的MAC地址，则称端口Sij为叶端口。
定义5：端口Sij是完全的，是指在给定子网中任何设备D发出的数据帧可以通过端口Sij到达Si，则D的MAC地址必出现在Lij中。
引理1：如果Lij∪Lkl=u（u指子网内所有交换机的合集）且Lij∩Lkl＝∮（∮空集）则端口Sij与端口Skl直接连接[1]。
引理2：若路由器或主机与交换机Si的Sij直接相连，当且仅当Sij是叶端口，且Lij中包含路由器或主机的MAC地址[1]。
Procedure FindInterConnections(S1, S2,... ,Sn, R1, R2,...,Rm)
/* S1, S2,...,Sn are the switches of a subnet S */
/* R1, R2,...,Rm are the routers of the subnet S */
begin
for each switch Si do
for each interface j of Si do {
If Sij 已经判定
continue
else {
If Lij ∪ Lkl = u and Lij ∩ Lkl＝∮)
Sij与Skl直接相连，生成新的连接
/* Sij 与Skl相匹配*/
}
}
for each router Rk do
for each switch Si do
for each interface j of Si do
If Sij 是叶端口且 Lij 包含Rk的MAC地址
Sij与Rk直接相连
/* Sij 与Rk相匹配*/
end
2.2 算法所存在的 问题
基本算法本身要求每台交换机的地址转发表必须完整（每台交换机必须知道其他交换机所对应的端口），但这在现实的网络中很难实现。为此Yuri Breitbart[1]专门设计出一种mping程序：对原有的ping程序进行修改，利用rawsocket将管理节点发出的icmp响应请求报文中的源IP地址改为给定的目标交换机的IP地址，目的IP地址为网络中其它主干设备的地址。当其他主干设备接收到ICMP查询请求报文后，将向给定的目标交换机发送ICMP查询响应报文，则给定的目标交换机地址转发表中就会增加目的设备的MAC地址。这种mping程序在原理上是正确地，但在一些安全配置严格的网络中这种设置虚假源IP地址的数据报文将被路由器、防火墙所过滤，使mping程序不能达到预期的效果。即使在一个宽松的网络环境中，有的目的设备在接收到ICMP查询请求报文后并不进行ARP操作，而是简单地将接收到的数据帧的源MAC地址与目的MAC地址互换[3]，然后发送ICMP查询响应报文，该响应报文的目标MAC地址与IP不对应是无效报文，不能够有效的增强转发表的完备性。并且这种算法大大的增加了额外的网络报文，其数量级为O（（交换机＋路由器）2）。
另外此算法要求所有交换机都能取得其SNMP信息，并且HUB只能在其叶端口上。但在复杂的网络结构中有的交换机虽然支持SNMP协议，但出于安全考虑或设置问题无法取得其SNMP信息，而且有些网络会出现交换机之间通过一个HUB进行连接，这两种情况基本算法都无法解决。
3 算法改进
链路层拓扑自动发现算法的困难在于网络信息的获取，在实际的网络环境中，各种网络设备为节约资源或网络安全等原因，对网络拓扑结构相关信息的采集设置了种种苛刻的条件。改进算法的出发点在于降低算法对拓扑信息特别是地址转发表的完备性的要求，并且通过简单而有效的手段满足这种降低后的要求。
考虑到物理网络主链路中有可能存在哑设备（无法获取SNMP数据的交换机、HUB的统称）的存在，新算法放宽了交换机（所有可以获取到SNMP数据的交换机的统称）与交换机必须直接连接的限制，扩展为交换机端口可以通过哑设备与多台交换机相连，这使的算法的应用范围更广，适应性更强。
3.1 算法的理论基础
为了更好的描述新的链路层拓扑发现算法，这里对已有定义进行补充：
定义6：标志节点：当运行算法的主机在预发现的子网中时，将此主机命名为标志节点，若不在，则将目标子网中，转发运行算法主机发出的数据报文的路由器定义为标志节点。[3]
定义7：上行端口：指端口对应的地址转发表中出现标志节点MAC地址的端口[3]
定义8：下行端口：指端口对应的地址转发表中没有出现标志节点MAC地址