基于MAC自學(xué)習(xí)的鏈路層拓?fù)浒l(fā)現(xiàn)算法研究

黃 睿，王俊峰

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

1 基于交換機(jī)MAC自學(xué)習(xí)的鏈路層拓?fù)浒l(fā)現(xiàn)算法

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

1.1 前提和假設(shè)

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

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

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

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

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

定理1 Ai中主機(jī)直連的交換機(jī)與Ak中主機(jī)直連的交換機(jī)分別在兩棵子樹(shù)上，這兩棵子樹(shù)沒(méi)有公共節(jié)點(diǎn)，且通過(guò)唯一路徑相連。

圖1 定理1示意圖

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

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

2 算法原理及流程

改進(jìn)的算法主要是利用了各個(gè)主機(jī)通過(guò)發(fā)送源MAC為T(mén)MAC的以太網(wǎng)報(bào)文來(lái)觸發(fā)網(wǎng)絡(luò)中交換機(jī)的MAC學(xué)習(xí)；然后通過(guò)發(fā)送與目的MAC為T(mén)MAC的報(bào)文來(lái)探測(cè)上一個(gè)報(bào)文對(duì)網(wǎng)絡(luò)轉(zhuǎn)發(fā)路徑的影響。

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

2.1 直連到同一交換機(jī)上的主機(jī)簇識(shí)別

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

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

2.2 開(kāi)始網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)

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

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

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

圖2 更新報(bào)文路徑圖

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

3 結(jié)語(yǔ)

本文主要論述了鏈路層拓?fù)浒l(fā)現(xiàn)的基本概念和難點(diǎn)，并針對(duì)交換機(jī)的工作原理特點(diǎn)，提出了一種基于交換機(jī)MAC自學(xué)習(xí)的發(fā)現(xiàn)算法。算法的基本原理是通過(guò)發(fā)送更新報(bào)文更新網(wǎng)絡(luò)中的交換機(jī)的交換轉(zhuǎn)發(fā)表，并通過(guò)測(cè)試報(bào)文來(lái)測(cè)試更新的范圍，將這兩種報(bào)文結(jié)合使用來(lái)達(dá)到網(wǎng)絡(luò)拓?fù)浒l(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.