基于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.