基于MAC自学习的链路层拓扑发现算法研究

黄 睿，王俊峰

(1.重庆电子工程职业学院，重庆 401331；2.东北财经大学，辽宁大连 116025）

1 基于交换机MAC自学习的链路层拓扑发现算法

目前绝大多数交换机都具有端口转发表的MAC学习功能。本文提出利用交换机的MAC自学习功能来获取交换机间的连接结构，该算法由网络上的多台主机共同完成，不要求交换机支持SNMP，能够发现网络上所有二层交换机的连接结构。

1.1 前提和假设

(1)将待测网络中的交换机标识为Si，待测网络上的主机标识为Hi。(2)保证网络中的每台待测交换机都至少连接有一台主机，这些主机在网络拓扑发现过程中都处于存活状态，并且它们都处于一个广播域中，将其分别记为H1～Hn。(3)每一台主机都对应着有一个MAC地址，分别记为MAC1～MACn，n为待测网络内符合前提(2)的主机数量。(4)网络中的交换机都正确地学习到MAC1～MACn。(5)网络由若干个交换机连接而成,其数目和拓扑结构不详。(6)在一个以太网的广播域内不能出现环路，因此可以把以太网的拓扑结构看成一个多叉树的结构。

1.2 算法相关定义

定义1：将一个网络中不存在的MAC地址记为TMAC，该MAC地址的值可以任取，但不能与待测网络内主机和交换机的MAC地址相冲突。定义2：若主机Hi向主机Hj发送的一个目的MAC为MACj（即Hj的MAC地址），源MAC为TMAC的报文，则把这种报文定义为更新报文。如果该更新报文的目的MAC为报文发送主机自身的MAC，则将这种更新报文称为自更新报文。定义3：若主机Hi向主机Hj发送的一个目的MAC为TMAC，源MAC为MACi（即Hi的MAC地址）的报文，则把这种报文定义为测试报文。定义4：若主机Hi发送的测试最终报文由主机Hj收到，则将测试报文经过的交换机集合记成Pi,j。定义5：如果在一个主机集合Ak内，由Hk向所有Ak内所有其他主机发送更新报文，则这些主机发送的测试报文都将被Hk所收到，称Hk为原始接收者。

1.3 算法相关定理

假设Hk为主机集合Ak的原始接收者。在Ak内任意选择两台主机Hi,Hj(i≠k，j≠k)。Hi向Hj发送一个更新报文。然后Ak中所有主机（包括Hk）发送测试报文，当发送完毕之后，将Hi和Hi收到的测试报文发送主机加入集合Ai，并将Ai中的主机从Ak中移去[4]。

定理1 Ai中主机直连的交换机与Ak中主机直连的交换机分别在两棵子树上，这两棵子树没有公共节点，且通过唯一路径相连。

图1 定理1示意图

图1直观地展示了定理1的涵义。可以看出在Hi向Hj发送了更新报文之后交换机上TMAC出现的端口位置，S4、S5、S6连接的主机发送的测试报文将被S3收到。S2、S7连接的主机发送的测试报文将被Hk收到。故而可以分成如图1所示的两棵树。

定理2 定义一个主机集合A，如果集合A内的任意一台主机发送自更新报文后，其余主机发送测试报文都能被该主机收到，则可判定集合A的主机是直接连接在一个交换机下。

2 算法原理及流程

改进的算法主要是利用了各个主机通过发送源MAC为TMAC的以太网报文来触发网络中交换机的MAC学习；然后通过发送与目的MAC为TMAC的报文来探测上一个报文对网络转发路径的影响。

算法大体上分为两个过程，第一个过程是识别直连到一台交换机上的所有主机。前提已经说过，要求待测网络内的每台交换机都至少直连有一台主机，本算法的基本思路就是通过交换机直连的主机簇来标识一台交换机。因此，第一个过程识别了每台交换机所直连的主机簇，实际上就相当于获得了待测网络内被这些主机簇所包围的不同交换机。第一个过程完成以后，会得到多个主机集合，每个集合内的主机分别连接在同一台交换机下，第二个过程就从上述每个主机集合中任选一个参与网络拓扑发现。

2.1 直连到同一交换机上的主机簇识别

识别过程的理论基础来自定理2，即如果集合A中的任意主机发送自向更新报文后，其他主机发送的测试报文该主机都能收到，则集合A内的主机直连到同一台交换机。利用这一原理，本算法提出了这样一种思路，具体流程如下：(1)由主机Hk广播更新报文到待测网络的所有主机。(2)将待测网络内的所有主机加入集合Ak。(3)从Ak中任选一台未被标记过的主机Hi，Hi向自己发送一个更新报文，然后标记Hi。(4)Ak中除Hi外的所有主机发送测试报文。(5)将Hi和Hi收到的测试报文发送主机放入集合Ai，并将其从Ak中删除。(6)将得到的集合Ak和Ai分别重复(3)～(5)的处理流程，直到分裂得到的集合为空或者集合内的元素都已被标记。(7)按照以上流程处理完毕后得到的每个集合都为直连在同一台交换机上的主机集合。

从步骤(5)可以看出，随着算法的进行，Ak中的元素最终会全部转移至分裂出来的各个Ai中，即Ak最终为空，又根据步骤(6)可知，最后剩下的非空集合其实都是Ai集合。按照(3)～(5)中对Ai集合内元素的要求，可知Ai中的主机为自更像报文发送主机和该主机在自更新报文发送收到的测试报文的发送主机。又因为按照步骤(6)的要求，最终得到的集合内的主机都已经被标记过，即都发送过了自更新报文。

2.2 开始网络拓扑发现

经过上述步骤的处理即可以识别直连到同一个交换机的主机簇，后续只需要从每个主机簇中各选择一台主机参与网络拓扑发现。下文所述及的主机都分属于与不同交换机直连的主机簇。H1～Hn分属不同的主机簇。改进后的算法描述如下：(1)将H1～Hn加入到集合Ak中。(2)Hk发送一个广播更新报文到集合的每台主机。(3)在集合Ak中选择两个Hi,Hj,(i≠k，j≠k，且Hi->Hj未标记)。Hi->Hj发送一个更新报文，标记Hi->Hj已测试。(4)Ak内所有主机发测试报文，把Hi和Hi收到的测试报文的发送主机加入到Ai中，把Ai中的主机从Ak中移除。(5)若Ak=覫，转入(3)；否则转入(6)。(6)清除所有测试标记，Ai和Ak内的所有主机发送自更新报文。(7)从Ai中任选一个Hm，Ak中任选一个Hn，Hm->Hn发送更新报文。(8)两集合内所有主机发送测试报文，对Hm收到的测试报文发送主机，若其属于Ai，则加入集合Ai’（Hm也加入Ai’），若其属于Ak，则将其加入集合Ak’。(9)Ai’和Ak’内所有主机发送自更新报文，从Ai’中任选一个Hi’，Ak’中任选一个Hj’，Hi’-Hj’>未标记。Hi’->Hj’发送一个更新报文，标记Hi’->Hj’已测试。(10)Ai’和Ak’内所有主机发送测试报文，若Hi’收到测试报文数大于1，转入(9)，若Hi’收到测试报文数等于1，则该测试报文发送主机必为Hj’，转入(11)。(11)清除所有测试标记，判定Hi’所直连的交换机与Hj’所直连的交换机直连。(12)若Ai、Ak内主机数大于1，对Ai和Ak分别重复(2)～(11)的处理流程，否则算法结束。

上述网络拓扑发现的流程可以概括为两个部分。第一个部分是步骤(2)～(5)，实现了对待处理集合进行分裂。按照定理1的结论，可以知道分裂成的两个非空集合必然是通过一条路径连接的两颗子树，这条唯一路径的两端各是一台交换机，是分属于两个集合下的某台主机的直连交换机。因此，第二个部分步骤(6)～(11)的目的就是要找到这两台主机，从而就找到了对应的两台交换机的直连关系。

步骤(6)中使两个集合内所有主机发自更新报文，如此一来就使得任何主机的测试报文都无法发出去。步骤(7)从两个集合中分别取一台主机Hm和Hn，Hm向Hn发更新报文。因为网络中不存在环路，故可知这条报文路径所经过的交换机两两直连（首尾除外），而且将这两个集合连起来的那两台交换机必在该路径上。该更新报文只流经这条唯一路径，因此只会更新Hm至Hn路径上交换机的转发表，对其他不在路径上的交换机没有影响。

图2 更新报文路径图

图2显示了Hm至Hn发送更新报文之后，各个交换机上TMAC出现的端口。可以看出，除了更新报文经过的路径上的交换机外，其他交换机端口未发生变化。步骤(8)所有主机发送测试报文，根据步骤(6)可知，除了Hm至Hn路径内的交换机外，其他交换机直连主机的测试报文都无法发出去，也就是上图所示的情况。所以Hm收到的测试报文的发送主机全都是Hm至Hn路径上的交换机的直连主机。按步骤(8)的方法将这些主机分别加入两个集合，则集合Ak和Ai必是通过Ai’中的某台主机的直连交换机和Ak’中某台主机的直连交换机连接起来的。后续步骤(9)～(11)，则是通过对Ai’和Ak’找到两集合主机间最短报文路径来获取直连的交换机。当Hi’收到的测试报文只有一个时，表明Hi’直连的交换机和Hj’直连的交换机间没有其他交换机，故可知这两台交换机直连。不断重复上述过程，就能够获得所有交换机间的连接关系。

3 结语

本文主要论述了链路层拓扑发现的基本概念和难点，并针对交换机的工作原理特点，提出了一种基于交换机MAC自学习的发现算法。算法的基本原理是通过发送更新报文更新网络中的交换机的交换转发表，并通过测试报文来测试更新的范围，将这两种报文结合使用来达到网络拓扑发现的目的。

[1]Bo Li,Jingsha He,Henghua Shi.Improving the Efficiency ofNetwork Topology Discovery[C].The 3rd.InternationalConferenceon Grid and Pervasive Computing，2001.

[2]Bruce Lowekamp,David Hallaron,Thomas R.Gross.Topology Discovery for Large EthernetNetworks[C].SIGCOMM 2001:240-248.

[3]Y.Breitbart,M.Garofalakis,C.Martin,R.Rastogi,S.Seshadri,A.Silberschatz.Topology Discovery in heterogeneous IPnetwork[C].IEEE INFOCOM,2000(3):268-278.

[4]Umer Uzair,Hafiz Farooq Ahmad,Arshad Ali,HirokiSuguris.An EfficientAlgorithm for EthernetTopology Discovery in Large Multi-subnetNetworks[C].IEEE,2007.