摘要 本文分析了现有的以太网链路层拓扑发现算法，在此基础上提出了改进算法，给出了算法的基本实现方法。新算法放宽了原算法中的条件限制，使得算法的应用范围更广，适应性更强。新算法可以发现网络中原算法无法发现的设备。
关键词 链路层 拓扑 SNMP
1 引言
随着计算机性能的提高及通信量的巨增，传统局域网已经愈来愈超出了自身的负荷，交换式以太网技术应运而生，大大提高了局域网的性能。与过去基于网桥，集线器，路由器的共享媒体的局域网拓扑结构相比，网络交换机能显着的增加带宽。交换技术的加入，就可以建立地理位置相对分散的网络，使局域网交换机的每个端口可平行、安全、同时的互相传输信息，而且使局域网可以高度扩充。局域网交换机根据使用的网络技术可分为：以太网交换机、令牌环交换机、FDDI交换机、ATM交换机、快速以太网交换机。由于以太网的简单与易用性，所以目前大部分的LAN均采用了以太网交换机与快速以太网交换机作为自己的网络交换设备。本文中的链路层拓扑发现正是针对以太网中的二层设备。
国内对拓扑发现技术的研究还集中在三层拓扑发现上，忽视了二层拓扑发现的重要性。在内网或者局域网，往往都是以交换机为中心来连接机器，而三层拓扑发现是无法实现这样的网络环境下的拓扑发现的。
2 现有链路层拓扑发现算法
从交换机工作原理上我们能够发现，交换机并未提供一种有效、直接的方法确定其直接连接的设备。对于一个异构的网络我们唯一可行的方法就是利用SNMP中的MIBⅡ bridge组的信息（各个厂家都实现），得到交换机的地址转发表，并分析其特性，找到一个合理的算法，来确定物理网路的拓扑关系。
链路层拓扑自动发现算法的目标是找出子网内交换机与交换机、交换机与路由器、交换机与主机之间的连接关系。其中找出交换机与交换机之间的连接关系是链路层拓扑自动发现的关键所在。贝尔实验室的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地址互换，然后发送ICMP查询响应报文，该响应报文的目标MAC地址与IP不对应是无效报文，不能够有效的增强转发表的完备性。并且这种算法大大的增加了额外的网络报文，其数量级为O（（交换机＋路由器）2）。
另外此算法要求所有交换机都能取得其SNMP信息，并且HUB只能在其叶端口上。但在复杂的网络结构中有的交换机虽然支持SNMP协议，但出于安全考虑或设置问题无法取得其SNMP信息，而且有些网络会出现交换机之间通过一个HUB进行连接，这两种情况基本算法都无法解决。
3 算法改进
链路层拓扑自动发现算法的困难在于网络信息的获取，在实际的网络环境中，各种网络设备为节约资源或网络安全等原因，对网络拓扑结构相关信息的采集设置了种种苛刻的条件。改进算法的出发点在于降低算法对拓扑信息特别是地址转发表的完备性的要求，并且通过简单而有效的手段满足这种降低后的要求。
考虑到物理网络主链路中有可能存在哑设备（无法获取SNMP数据的交换机、HUB的统称）的存在，新算法放宽了交换机（所有可以获取到SNMP数据的交换机的统称）与交换机必须直接连接的限制，扩展为交换机端口可以通过哑设备与多台交换机相连，这使的算法的应用范围更广，适应性更强。
3.1 算法的理论基础
为了更好的描述新的链路层拓扑发现算法，这里对已有定义进行补充：
定义6：标志节点：当运行算法的主机在预发现的子网中时，将此主机命名为标志节点，若不在，则将目标子网中，转发运行算法主机发出的数据报文的路由器定义为标志节点。
定义7：上行端口：指端口对应的地址转发表中出现标志节点MAC地址的端口
定义8：下行端口：指端口对应的地址转发表中没有出现标志节点MAC地址
的端口。
定义9：Si的MAC地址：令交换机Si的MAC地址表示为Si_MAC。
定义10：令交换机Si下行端口Sij的Lij（j＝1,2,…,N）的和为Li，则Li＝{ ij|Lij所对应端口Sij为下行端口}
定义11：令交换机Si下行端口Sij的Dij（j＝1,2,…,N）的和为Di，则Di＝{ ij|Dij所对应端口Sij为下行端口}
定义12：任意非叶端口Sij，Lij必不为空集，Lij集合中的某台交换机Sk，其Lk最大，则Sk为Sij的最大子树根节点（如果存在多个交换机其L值相同，则任选一个）。
结论1：交换机非叶端口与交换机直接相连判定：交换机Si其下行非叶端口Sij的MAC表的集合Aij等于其最大子树的根节点Sk的所有下行端口的MAC表的和再加上Sk的MAC地址即Aij＝Ak ＋ Sk_MAC，则Si通过下行端口Sij与Sk的上行端口直接连接。
结论2：交换机非叶端口与哑设备直接相连判定：交换机Si其下行非叶端口Sij的MAC表的集合Aij大于其最大子树的根节点Sk的所有下行端口的MAC表的和再加上Sk的MAC地址。Aij Ak ＋ Sk_MAC。则Si通过下行端口Sij与哑设备相连，Sk通过上行端口与哑设备直接相连。
3.2 算法描述及实现
改进算法的基本描述
⑴ 获取子网内所有路由器、交换机、主机的列表，确定IP地址与MAC地址的对应关系以及标志节点。
⑵ ping子网内所有活动设备。
⑶ 读取每台交换机的地址转发表。
⑷ 判断标志节点的连接情况，将与其最近的交换机设置为根交换机，加入到交换机发现队列。
⑸ 取出交换机发现队列中的首个交换机，确定其下行端口的连接关系。如果是叶端口则根据结论3判断其与哑设备、主机路由器的连接关系，如果不是叶端口则根据结论1、2判断其连接关系，将新发现的交换机加入到交换机发现队列的尾部。
⑹ 循环5，直到交换机队列中为空，算法结束。
算法实现分为三个过程。令N为子网地址。Init(N) 初始化程序，LinkLayer(N) 主二层拓扑发现程序， DealSubTree(F，Fp，Temp，L2_Temp，Hub_Num)算法的核心，负责处理交换机端口Fp的连接关系。
Init(N) 函数
⑴ 对子网内所有IP地址空间发送ICMP请求报文，得到所有的活动设备并将其赋值给Alive，
⑵ 确定标志节点：如果是管理服务器所在的子网，标志节点为管理服务器，其它子网为traceroute程序返回的最后一个路由器，将其赋值给Root。
⑶ 收集拓扑信息：对子网内每一活动设备发送SNMP报文，判断其设备类型，对于三层设备加入到三层设备的集合中并得到其IP地址与MAC地址的映射表，对于二层设备加入到二层设备的集合中，并确定其上行端口。
LinkLayer(N)
⑴ 调用Init(N)收集信息。
⑵ 确定根交换机
⑶ 取出交换机发现队列中的第一个交换机F，对其各个下行端口进行处理（调用DealSubTree(F，Fp，Temp，L2_Temp，Hub_Num)处理连接关系），并将新发现的交换机加入到发现队列中。
⑷ F的各个端口处理完毕后，跳到第3步。
⑸ 发现队列中的所有交换机都处理完毕。算法结束。
DealSubTree(F，Fp，Temp，L2_Temp，Hub_Num)，F是父节点的交换机，Fp是交换机F的一个下行端口。Temp为Fp端口的MAC地址表。L2_Temp为Fp端口上二层设备MAC地址的集合。Hub_Num为哑设备数组的下标。
⑴ 如果Fp为非叶端口则对Fp的子树行处理，找到其根节点，建立连接。如果子树的根为交换机则直接建立其与Fp的连接关系。如有子树的根为哑设备则继续处理哑设备与其它交换机的连接关系，并将这些交换机加入到发现队列中。
⑵ 如果Fp为叶端口则根据结论3判断其所在网段交换机与哑设备、主机、路由器的连接关系。
选用某单位网络室的网络环境作为算法测试环境，其子网地址为192.168.100.0，子网掩码是255.255.255.0。子网内包括1台路由器，40多台主机，通过4台Cisco Calayst2950系列交换机以及多个HUB互连，所有的交换机都可以获取到SNMP数据。通过多次运行该算法探测拓扑，综合后所得结果与实际的物理网络基本一致。
4 结束语
本文对以太网链路层拓扑发现的算法进行了研究，提出了初步的改进算法。改进算法对原算法条件进行了扩展，使其适用范围更广。但算法中哑设备的发现是基于发现程序运行时，交换机端口所连设备的个数的判定，但是这种情况有可能是一种实际连接的假象，有可能交换机的一个端口确实通过一个哑设备连接多个设备，但是只有一个设备是活动的，则地址转发表只能学习到一个MAC地址，这样此算法将无法发现这种1：n的关系，而只能误认为是直接连接。这种局限不能通过一次拓扑发现有效的解决，只能通过多次发现，并且根据历史信息，综合才能得到正确的网络结构。
参考文献：
[1] Yuri Breitbart, Minos Garofalakis, Cliff Martin, Rajeev Rastogi, S.Seshadri，Avi Silberaschatz. Topology Discovery in Heterogeneous IP Networks. IEEE INFOCOM 2000.
Thomas M.ThomasⅡ. Cisco 网络互联设备. 前导工作室译. 北京：机械工业出版.
郑海，张国清. 物理网络拓扑发现算法的研究. 计算机研究与发展，2002，39(3).
Bruce Lowekamp, David R. O’Hallaron, Thomas R. Gross. Topology Discovery for Large Ethernet Networks. 2002
Yigal Bejerano, Yuri Breitbart, Minos Garofalakis, Rajeev Rastogi. Physical Topology Discovery for Large Multi-Subnet Networks. 2002
