黃 睿，王俊峰

(1.重慶電子工程職業(yè)學(xué)院，重慶 401331；2.東北財經(jīng)大學(xué)，遼寧大連 116025）

1 基于交換機MAC自學(xué)習(xí)的鏈路層拓撲發(fā)現(xiàn)算法

目前絕大多數(shù)交換機都具有端口轉(zhuǎn)發(fā)表的MAC學(xué)習(xí)功能。本文提出利用交換機的MAC自學(xué)習(xí)功能來獲取交換機間的連接結(jié)構(gòu)，該算法由網(wǎng)絡(luò)上的多臺主機共同完成，不要求交換機支持SNMP，能夠發(fā)現(xiàn)網(wǎng)絡(luò)上所有二層交換機的連接結(jié)構(gòu)。

1.1 前提和假設(shè)

(1)將待測網(wǎng)絡(luò)中的交換機標識為Si，待測網(wǎng)絡(luò)上的主機標識為Hi。(2)保證網(wǎng)絡(luò)中的每臺待測交換機都至少連接有一臺主機，這些主機在網(wǎng)絡(luò)拓撲發(fā)現(xiàn)過程中都處于存活狀態(tài)，并且它們都處于一個廣播域中，將其分別記為H1～Hn。(3)每一臺主機都對應(yīng)著有一個MAC地址，分別記為MAC1～MACn，n為待測網(wǎng)絡(luò)內(nèi)符合前提(2)的主機數(shù)量。(4)網(wǎng)絡(luò)中的交換機都正確地學(xué)習(xí)到MAC1～MACn。(5)網(wǎng)絡(luò)由若干個交換機連接而成,其數(shù)目和拓撲結(jié)構(gòu)不詳。(6)在一個以太網(wǎng)的廣播域內(nèi)不能出現(xiàn)環(huán)路，因此可以把以太網(wǎng)的拓撲結(jié)構(gòu)看成一個多叉樹的結(jié)構(gòu)。

1.2 算法相關(guān)定義

定義1：將一個網(wǎng)絡(luò)中不存在的MAC地址記為TMAC，該MAC地址的值可以任取，但不能與待測網(wǎng)絡(luò)內(nèi)主機和交換機的MAC地址相沖突。定義2：若主機Hi向主機Hj發(fā)送的一個目的MAC為MACj（即Hj的MAC地址），源MAC為TMAC的報文，則把這種報文定義為更新報文。如果該更新報文的目的MAC為報文發(fā)送主機自身的MAC，則將這種更新報文稱為自更新報文。定義3：若主機Hi向主機Hj發(fā)送的一個目的MAC為TMAC，源MAC為MACi（即Hi的MAC地址）的報文，則把這種報文定義為測試報文。定義4：若主機Hi發(fā)送的測試最終報文由主機Hj收到，則將測試報文經(jīng)過的交換機集合記成Pi,j。定義5：如果在一個主機集合Ak內(nèi)，由Hk向所有Ak內(nèi)所有其他主機發(fā)送更新報文，則這些主機發(fā)送的測試報文都將被Hk所收到，稱Hk為原始接收者。

1.3 算法相關(guān)定理

假設(shè)Hk為主機集合Ak的原始接收者。在Ak內(nèi)任意選擇兩臺主機Hi,Hj(i≠k，j≠k)。Hi向Hj發(fā)送一個更新報文。然后Ak中所有主機（包括Hk）發(fā)送測試報文，當發(fā)送完畢之后，將Hi和Hi收到的測試報文發(fā)送主機加入集合Ai，并將Ai中的主機從Ak中移去[4]。

定理1 Ai中主機直連的交換機與Ak中主機直連的交換機分別在兩棵子樹上，這兩棵子樹沒有公共節(jié)點，且通過唯一路徑相連。

圖1 定理1示意圖

圖1直觀地展示了定理1的涵義?？梢钥闯鲈贖i向Hj發(fā)送了更新報文之后交換機上TMAC出現(xiàn)的端口位置，S4、S5、S6連接的主機發(fā)送的測試報文將被S3收到。S2、S7連接的主機發(fā)送的測試報文將被Hk收到。故而可以分成如圖1所示的兩棵樹。

定理2 定義一個主機集合A，如果集合A內(nèi)的任意一臺主機發(fā)送自更新報文后，其余主機發(fā)送測試報文都能被該主機收到，則可判定集合A的主機是直接連接在一個交換機下。

2 算法原理及流程

改進的算法主要是利用了各個主機通過發(fā)送源MAC為TMAC的以太網(wǎng)報文來觸發(fā)網(wǎng)絡(luò)中交換機的MAC學(xué)習(xí)；然后通過發(fā)送與目的MAC為TMAC的報文來探測上一個報文對網(wǎng)絡(luò)轉(zhuǎn)發(fā)路徑的影響。

算法大體上分為兩個過程，第一個過程是識別直連到一臺交換機上的所有主機。前提已經(jīng)說過，要求待測網(wǎng)絡(luò)內(nèi)的每臺交換機都至少直連有一臺主機，本算法的基本思路就是通過交換機直連的主機簇來標識一臺交換機。因此，第一個過程識別了每臺交換機所直連的主機簇，實際上就相當于獲得了待測網(wǎng)絡(luò)內(nèi)被這些主機簇所包圍的不同交換機。第一個過程完成以后，會得到多個主機集合，每個集合內(nèi)的主機分別連接在同一臺交換機下，第二個過程就從上述每個主機集合中任選一個參與網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。

2.1 直連到同一交換機上的主機簇識別

識別過程的理論基礎(chǔ)來自定理2，即如果集合A中的任意主機發(fā)送自向更新報文后，其他主機發(fā)送的測試報文該主機都能收到，則集合A內(nèi)的主機直連到同一臺交換機。利用這一原理，本算法提出了這樣一種思路，具體流程如下：(1)由主機Hk廣播更新報文到待測網(wǎng)絡(luò)的所有主機。(2)將待測網(wǎng)絡(luò)內(nèi)的所有主機加入集合Ak。(3)從Ak中任選一臺未被標記過的主機Hi，Hi向自己發(fā)送一個更新報文，然后標記Hi。(4)Ak中除Hi外的所有主機發(fā)送測試報文。(5)將Hi和Hi收到的測試報文發(fā)送主機放入集合Ai，并將其從Ak中刪除。(6)將得到的集合Ak和Ai分別重復(fù)(3)～(5)的處理流程，直到分裂得到的集合為空或者集合內(nèi)的元素都已被標記。(7)按照以上流程處理完畢后得到的每個集合都為直連在同一臺交換機上的主機集合。

從步驟(5)可以看出，隨著算法的進行，Ak中的元素最終會全部轉(zhuǎn)移至分裂出來的各個Ai中，即Ak最終為空，又根據(jù)步驟(6)可知，最后剩下的非空集合其實都是Ai集合。按照(3)～(5)中對Ai集合內(nèi)元素的要求，可知Ai中的主機為自更像報文發(fā)送主機和該主機在自更新報文發(fā)送收到的測試報文的發(fā)送主機。又因為按照步驟(6)的要求，最終得到的集合內(nèi)的主機都已經(jīng)被標記過，即都發(fā)送過了自更新報文。

2.2 開始網(wǎng)絡(luò)拓撲發(fā)現(xiàn)

經(jīng)過上述步驟的處理即可以識別直連到同一個交換機的主機簇，后續(xù)只需要從每個主機簇中各選擇一臺主機參與網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。下文所述及的主機都分屬于與不同交換機直連的主機簇。H1～Hn分屬不同的主機簇。改進后的算法描述如下：(1)將H1～Hn加入到集合Ak中。(2)Hk發(fā)送一個廣播更新報文到集合的每臺主機。(3)在集合Ak中選擇兩個Hi,Hj,(i≠k，j≠k，且Hi->Hj未標記)。Hi->Hj發(fā)送一個更新報文，標記Hi->Hj已測試。(4)Ak內(nèi)所有主機發(fā)測試報文，把Hi和Hi收到的測試報文的發(fā)送主機加入到Ai中，把Ai中的主機從Ak中移除。(5)若Ak=覫，轉(zhuǎn)入(3)；否則轉(zhuǎn)入(6)。(6)清除所有測試標記，Ai和Ak內(nèi)的所有主機發(fā)送自更新報文。(7)從Ai中任選一個Hm，Ak中任選一個Hn，Hm->Hn發(fā)送更新報文。(8)兩集合內(nèi)所有主機發(fā)送測試報文，對Hm收到的測試報文發(fā)送主機，若其屬于Ai，則加入集合Ai’（Hm也加入Ai’），若其屬于Ak，則將其加入集合Ak’。(9)Ai’和Ak’內(nèi)所有主機發(fā)送自更新報文，從Ai’中任選一個Hi’，Ak’中任選一個Hj’，Hi’-Hj’>未標記。Hi’->Hj’發(fā)送一個更新報文，標記Hi’->Hj’已測試。(10)Ai’和Ak’內(nèi)所有主機發(fā)送測試報文，若Hi’收到測試報文數(shù)大于1，轉(zhuǎn)入(9)，若Hi’收到測試報文數(shù)等于1，則該測試報文發(fā)送主機必為Hj’，轉(zhuǎn)入(11)。(11)清除所有測試標記，判定Hi’所直連的交換機與Hj’所直連的交換機直連。(12)若Ai、Ak內(nèi)主機數(shù)大于1，對Ai和Ak分別重復(fù)(2)～(11)的處理流程，否則算法結(jié)束。

上述網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的流程可以概括為兩個部分。第一個部分是步驟(2)～(5)，實現(xiàn)了對待處理集合進行分裂。按照定理1的結(jié)論，可以知道分裂成的兩個非空集合必然是通過一條路徑連接的兩顆子樹，這條唯一路徑的兩端各是一臺交換機，是分屬于兩個集合下的某臺主機的直連交換機。因此，第二個部分步驟(6)～(11)的目的就是要找到這兩臺主機，從而就找到了對應(yīng)的兩臺交換機的直連關(guān)系。

步驟(6)中使兩個集合內(nèi)所有主機發(fā)自更新報文，如此一來就使得任何主機的測試報文都無法發(fā)出去。步驟(7)從兩個集合中分別取一臺主機Hm和Hn，Hm向Hn發(fā)更新報文。因為網(wǎng)絡(luò)中不存在環(huán)路，故可知這條報文路徑所經(jīng)過的交換機兩兩直連（首尾除外），而且將這兩個集合連起來的那兩臺交換機必在該路徑上。該更新報文只流經(jīng)這條唯一路徑，因此只會更新Hm至Hn路徑上交換機的轉(zhuǎn)發(fā)表，對其他不在路徑上的交換機沒有影響。

圖2 更新報文路徑圖

圖2顯示了Hm至Hn發(fā)送更新報文之后，各個交換機上TMAC出現(xiàn)的端口?？梢钥闯觯烁聢笪慕?jīng)過的路徑上的交換機外，其他交換機端口未發(fā)生變化。步驟(8)所有主機發(fā)送測試報文，根據(jù)步驟(6)可知，除了Hm至Hn路徑內(nèi)的交換機外，其他交換機直連主機的測試報文都無法發(fā)出去，也就是上圖所示的情況。所以Hm收到的測試報文的發(fā)送主機全都是Hm至Hn路徑上的交換機的直連主機。按步驟(8)的方法將這些主機分別加入兩個集合，則集合Ak和Ai必是通過Ai’中的某臺主機的直連交換機和Ak’中某臺主機的直連交換機連接起來的。后續(xù)步驟(9)～(11)，則是通過對Ai’和Ak’找到兩集合主機間最短報文路徑來獲取直連的交換機。當Hi’收到的測試報文只有一個時，表明Hi’直連的交換機和Hj’直連的交換機間沒有其他交換機，故可知這兩臺交換機直連。不斷重復(fù)上述過程，就能夠獲得所有交換機間的連接關(guān)系。

3 結(jié)語

本文主要論述了鏈路層拓撲發(fā)現(xiàn)的基本概念和難點，并針對交換機的工作原理特點，提出了一種基于交換機MAC自學(xué)習(xí)的發(fā)現(xiàn)算法。算法的基本原理是通過發(fā)送更新報文更新網(wǎng)絡(luò)中的交換機的交換轉(zhuǎn)發(fā)表，并通過測試報文來測試更新的范圍，將這兩種報文結(jié)合使用來達到網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的目的。

[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.