交換式以太網(wǎng)物理拓?fù)浒l(fā)現(xiàn)的進(jìn)展與研究

摘要：著重介紹了交換式以太網(wǎng)的物理拓?fù)浒l(fā)現(xiàn)算法，包括基于交換機(jī)生成樹信息的方法、基于地址轉(zhuǎn)發(fā)表的方法和基于探測包的方法；最后指出關(guān)于物理拓?fù)浒l(fā)現(xiàn)的一些研究重點(diǎn)。

關(guān)鍵詞：網(wǎng)絡(luò)管理； 物理拓?fù)浒l(fā)現(xiàn)； 交換式以太網(wǎng)

中圖分類號：TP393.07文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2007)12-0024-04

在早期的以太網(wǎng)中，同一個子網(wǎng)（網(wǎng)段）內(nèi)的多個網(wǎng)絡(luò)終端采用載波偵聽多路訪問和沖突檢測技術(shù)CSMA/CD (carrier sense multiple access/collision detect)共享同一個傳輸媒介，構(gòu)成了一個廣播域。由于廣播域內(nèi)的設(shè)備不能同時訪問傳輸媒介，稱為沖突限制，導(dǎo)致單個以太網(wǎng)廣播域內(nèi)的設(shè)備不能很多，一般只有幾十個，網(wǎng)絡(luò)規(guī)模和拓?fù)浣Y(jié)構(gòu)非常簡單。

交換技術(shù)誕生于20世紀(jì)80年代，是從多端口網(wǎng)橋發(fā)展而來的。其主要目的是為了細(xì)分局域網(wǎng)廣播域。交換式以太網(wǎng)已經(jīng)發(fā)展成為當(dāng)前局域網(wǎng)的主要組網(wǎng)方式。它的組網(wǎng)核心是一個或多個互相連接的以太網(wǎng)交換機(jī)；每個交換機(jī)可以有多個端口；每個端口可與一個交換機(jī)或終端設(shè)備連接，也可與一個共享式hub連接。

網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)是網(wǎng)絡(luò)管理中的一個重要內(nèi)容，主要解決網(wǎng)絡(luò)層和鏈路層的拓?fù)渥詣影l(fā)現(xiàn)問題。早期對網(wǎng)絡(luò)拓?fù)涞难芯恐饕性诰W(wǎng)絡(luò)層上，利用SNMP或通用的ICMP（利用ping、traceroute等工具）^[1，2]。隨著交換技術(shù)的引入，以太網(wǎng)的規(guī)模迅速增加，在同一個子網(wǎng)中可以包含幾百個設(shè)備，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也變得更加復(fù)雜。鏈路層網(wǎng)絡(luò)拓?fù)湫畔τ诰W(wǎng)絡(luò)管理的重要性也隨著突顯出來。鏈路層拓?fù)浒l(fā)現(xiàn)的目標(biāo)是確定網(wǎng)絡(luò)中各種設(shè)備以及這些設(shè)備物理端口之間的連接關(guān)系，通常稱之為物理拓?fù)浒l(fā)現(xiàn)。準(zhǔn)確及時的物理拓?fù)湫畔τ诰W(wǎng)絡(luò)性能監(jiān)測與評估、故障發(fā)現(xiàn)與定位、資源分配與管理、網(wǎng)絡(luò)維護(hù)等一系列工作具有重要意義。比如，對于故障定位來說，通常一個單一的故障可能會引起一系列故障告警風(fēng)暴。這些告警會出現(xiàn)在不同的網(wǎng)絡(luò)設(shè)備上，網(wǎng)絡(luò)設(shè)備之間的連接關(guān)系對于過濾掉次要的告警信息、確定告警源是至關(guān)重要的。

1物理拓?fù)浒l(fā)現(xiàn)的困難

物理拓?fù)浒l(fā)現(xiàn)的目標(biāo)是發(fā)現(xiàn)交換機(jī)等網(wǎng)絡(luò)設(shè)備端口之間的連接關(guān)系。相對于網(wǎng)絡(luò)層（OSI的第三層）的拓?fù)浒l(fā)現(xiàn)，物理拓?fù)洌炊泳W(wǎng)絡(luò)拓?fù)洌┌l(fā)現(xiàn)更加困難。因?yàn)榫W(wǎng)絡(luò)層拓?fù)涫欠浅Ｇ宄模恳粋€路由器都清楚地知道它們的鄰居節(jié)點(diǎn)。物理拓?fù)浒l(fā)現(xiàn)需要面對如下困難：

a）二層設(shè)備的透明性。與三層設(shè)備路由器不同，交換機(jī)設(shè)備對于數(shù)據(jù)傳輸?shù)陌l(fā)送端設(shè)備和接收端設(shè)備是完全透明的，它們根本不知道交換機(jī)的存在，就像在一個共享傳輸媒介的CSMA/CD以太網(wǎng)中傳輸數(shù)據(jù)一樣。

b）網(wǎng)元設(shè)備的異構(gòu)性。拓?fù)浒l(fā)現(xiàn)算法必須能夠正確識別并獲取各種類型的設(shè)備信息，如路由器、交換機(jī)、各種服務(wù)器和工作站等。這些設(shè)備可能是思科（CISCO）、朗訊、北電等大網(wǎng)絡(luò)設(shè)備公司的產(chǎn)品，也可能是不知名公司的產(chǎn)品。

c）復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。一個復(fù)雜的網(wǎng)絡(luò)中可能存在著星型、總線型和環(huán)型網(wǎng)絡(luò)結(jié)構(gòu)，運(yùn)行如IBM SNA、Xero XNS、AppleTalk、TCP/IP和DECnet等多種網(wǎng)絡(luò)協(xié)議。

另外還有很多因素影響著網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)，像網(wǎng)絡(luò)中存在著集線器（hub）等不可管理的設(shè)備、網(wǎng)絡(luò)拓?fù)涞膭討B(tài)變化以及拓?fù)湎嚓P(guān)信息的匱乏等。因此一個適應(yīng)各種網(wǎng)絡(luò)環(huán)境的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法是不存在的。本文主要是針對交換式以太網(wǎng)的物理拓?fù)浒l(fā)現(xiàn)算法。

2物理拓?fù)浒l(fā)現(xiàn)方法

從2000年開始，國內(nèi)外研究人員開始對交換式以太網(wǎng)的物理拓?fù)浒l(fā)現(xiàn)進(jìn)行了較為深入的研究。在標(biāo)準(zhǔn)制定方面，2000年9月，IETF發(fā)布了關(guān)于物理拓?fù)銶IB（PTOPOMIB）的RFC^[3]用于指導(dǎo)網(wǎng)絡(luò)層以下拓?fù)浣Y(jié)構(gòu)的發(fā)現(xiàn)。它定義了標(biāo)志網(wǎng)絡(luò)端口之間連接和發(fā)現(xiàn)SNMP代理的網(wǎng)絡(luò)地址的統(tǒng)一標(biāo)準(zhǔn)。該RFC沒有規(guī)定物理拓?fù)涞陌l(fā)現(xiàn)機(jī)制。它需要拓?fù)浒l(fā)現(xiàn)方法來完成相關(guān)MIB變量的填充。

在發(fā)現(xiàn)方法方面，研究人員提出了基于交換機(jī)生成樹 (spanning tree)的算法^[4，5]、基于地址轉(zhuǎn)發(fā)表(address forwarding table，AFT)的算法^[5，6~11]和基于探測包的算法^[12]。由于交換機(jī)一般均采用地址轉(zhuǎn)發(fā)表進(jìn)行數(shù)據(jù)幀的轉(zhuǎn)發(fā)，基于地址轉(zhuǎn)發(fā)表的算法成為目前適用范圍最為廣泛的通用方法。不加特殊說明，后面所提到的網(wǎng)絡(luò)拓?fù)渚侵妇W(wǎng)絡(luò)物理拓?fù)洹?/p>

2．1基于生成樹信息的方法

為了保證節(jié)點(diǎn)間能夠正常通信，避免廣播風(fēng)暴的發(fā)生，交換式以太網(wǎng)的拓?fù)浣Y(jié)構(gòu)必須是樹型的；然而為了提高網(wǎng)絡(luò)的可靠性，網(wǎng)絡(luò)管理員有時會在局域網(wǎng)段之間設(shè)置并行的兩條或多條路徑，這就會在拓?fù)浣Y(jié)構(gòu)中產(chǎn)生回路。交換機(jī)之間會通過協(xié)商（如使用文獻(xiàn)[13]中生成樹協(xié)議）阻塞部分路徑保證整個網(wǎng)絡(luò)拓?fù)涫且粋€樹型結(jié)構(gòu)。這就是生成樹。交換機(jī)生成樹信息可以從dot1dStp MIB組^[14]中獲取得到。

國內(nèi)外研究人員提出了多種方法利用生成樹信息發(fā)現(xiàn)局域網(wǎng)的網(wǎng)絡(luò)拓?fù)洹＿@些方法在基本原理上是一樣的，都是利用生成樹中的根端口、指派端口及指派網(wǎng)橋之間的關(guān)系確定交換機(jī)之間的連接關(guān)系。比較有代表性的有李濤等人提出的方法^[4]和MyungHee Son等人提出的方法^[5]。文獻(xiàn)[5]指出，利用生成樹信息可以發(fā)現(xiàn)網(wǎng)絡(luò)中的備用鏈路信息。下面以文獻(xiàn)[5]為例說明如何采用生成樹信息構(gòu)造網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。圖 1是一個帶有備用鏈路的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，運(yùn)行生成樹協(xié)議后，網(wǎng)橋C的（C， 2）端口被阻塞，形成了以網(wǎng)橋B1為根的一棵樹；（C， 2）端口被阻塞后，不會發(fā)送任何數(shù)據(jù)包，并且丟棄除STP BPDU（bridge protocol data unit）之外的任何數(shù)據(jù)包。

定理1 網(wǎng)橋連接定理^[5]。對于網(wǎng)橋A和B，如果（A， i）端口有一個指派網(wǎng)橋B，則A和B直接連接在一起。

利用定理1，文獻(xiàn)[5]給出了建立網(wǎng)橋之間連接關(guān)系的方法。以圖 1為例，端口（B，1）的指派網(wǎng)橋是A，指派端口是（A，1）。根據(jù)定理1可以判斷出（B，1）和（A，2）相連；同樣可以判斷出（C，1）和（A，2）相連。上述方法對于阻塞端口（C，2）同樣適用。它的指派網(wǎng)橋是B，指派端口是（B，2）。因此可以判定（C，2）和（B，2）相連。對于端口（B，3）和（C，3），由于連接的不是網(wǎng)橋設(shè)備，不參與生成樹協(xié)議，要想判斷這些端口的連接關(guān)系，必須借助于地址轉(zhuǎn)發(fā)表。

基于生成樹信息的方法的優(yōu)點(diǎn)在于時間和空間消耗較小，可以發(fā)現(xiàn)局域網(wǎng)中的備用鏈路；缺點(diǎn)是許多交換機(jī)不支持生成樹協(xié)議，適用范圍受到一定限制，并且該方法不能發(fā)現(xiàn)交換機(jī)與主機(jī)之間的連接關(guān)系。

2．2基于地址轉(zhuǎn)發(fā)表的方法

上面提出的兩種方法均可以應(yīng)用于多子網(wǎng)的拓?fù)浒l(fā)現(xiàn)。它們需要計算任意一對節(jié)點(diǎn)之間的連接關(guān)系，計算量比較大。筆者在文獻(xiàn)[11]中針對單子網(wǎng)的情況，提出了一種更為簡潔的拓?fù)浒l(fā)現(xiàn)新算法。該方法把網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)看做一棵拓?fù)錁洌丫W(wǎng)絡(luò)節(jié)點(diǎn)之間的連接關(guān)系分為直系關(guān)系和旁系關(guān)系，并給出一組判定定理用于確定網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接關(guān)系。該算法利用以太網(wǎng)拓?fù)浣Y(jié)構(gòu)是無環(huán)的樹型結(jié)構(gòu)這一特點(diǎn)（現(xiàn)有算法大多忽視了這一點(diǎn)，把網(wǎng)絡(luò)拓?fù)渥鳛楦鼮閺?fù)雜的網(wǎng)狀結(jié)構(gòu)處理），能夠有效減少拓?fù)浒l(fā)現(xiàn)的時間，通過對連接沖突的處理，保證拓?fù)浒l(fā)現(xiàn)的準(zhǔn)確性。

2．2．3其他方法

Richard Black等人^[12]中提出一種不需要使用地址轉(zhuǎn)發(fā)表和STP的拓?fù)浒l(fā)現(xiàn)算法。其基本思想是在主機(jī)上設(shè)置一個代理進(jìn)程，產(chǎn)生一些探測包，利用網(wǎng)卡工作在混雜模式下可以接收到所在網(wǎng)段內(nèi)的所有數(shù)據(jù)包這一特性判斷設(shè)備之間的連接關(guān)系。這種方法可以判斷出交換機(jī)之間、交換機(jī)和主機(jī)之間的連接關(guān)系；缺點(diǎn)是需要在每個主機(jī)設(shè)備上都設(shè)置一個代理進(jìn)程，這對一個較大型網(wǎng)絡(luò)來說是不太可能的事情。本文提出的解決辦法是把進(jìn)程代理集成到操作系統(tǒng)中。目前來看，該方法還不是一個普遍適用的解決辦法。

3主要問題和發(fā)展方向

總體來說，上述方法，特別是基于非完整地址轉(zhuǎn)發(fā)表的方法已經(jīng)較好地解決了交換式以太網(wǎng)的物理拓?fù)浒l(fā)現(xiàn)問題。但是在該領(lǐng)域仍然有很多問題需要深入研究和解決。

a）需要研究這些拓?fù)浒l(fā)現(xiàn)方法和PTOPOMIB^[3]的結(jié)合問題，即如何利用這些方法來為PTOPOMIB對象進(jìn)行賦值，從而允許各種不同的拓?fù)浒l(fā)現(xiàn)方法通過SNMP結(jié)合在一起，在不同的網(wǎng)絡(luò)環(huán)境下采用不同的拓?fù)浒l(fā)現(xiàn)算法，提高拓?fù)浒l(fā)現(xiàn)算法的可擴(kuò)展性。

b）Ad hoc網(wǎng)絡(luò)和傳感器網(wǎng)絡(luò)等新型網(wǎng)絡(luò)的拓?fù)浒l(fā)現(xiàn)問題。像Ad hoc中節(jié)點(diǎn)的移動性，網(wǎng)絡(luò)拓?fù)鋭討B(tài)性、不穩(wěn)定的鏈路狀態(tài)等問題均會給網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)和拓?fù)渌⑿碌葞矸浅４蟮奶魬?zhàn)。

c）IPv6帶來的新問題。需要研究IPv6網(wǎng)絡(luò)大地址空間、層次化地址結(jié)構(gòu)等特點(diǎn)對拓?fù)浒l(fā)現(xiàn)的影響問題。

此外，VLAN網(wǎng)絡(luò)、重疊網(wǎng)絡(luò)的拓?fù)浒l(fā)現(xiàn)，非交換式以太網(wǎng)的拓?fù)浒l(fā)現(xiàn)等方面還需要更多深入的研究。

4結(jié)束語

物理拓?fù)浒l(fā)現(xiàn)是網(wǎng)絡(luò)管理的一個主要內(nèi)容。本文主要介紹當(dāng)前國內(nèi)外學(xué)者在物理拓?fù)溲芯糠矫娴淖钚逻M(jìn)展以及筆者在該方面工作中所取得的一些研究成果；指明了物理拓?fù)溲芯恐心壳吧写鉀Q的一些問題，可以幫助研究人員在這方面少走彎路，更快地深入到關(guān)鍵問題的研究當(dāng)中。

參考文獻(xiàn)：

[1]DONNET B， RAOULT P， FRIEDMAN T， et al.Efficient algorithms for large-scale topology discovery[C]//Proc of ACM SIGMETRICS. New York:ACM Press， 2005:327-338.

[2]GOVINDAN R， TANGMUNARUNKIT H. Heuristics for Internet map discovery[C]//Proc of IEEE INFOCOM. New York:IEEE Press， 2000:1371-1380.

[3]BIERMAN A，JONES K.RFC 2922， Physical topology MIB[S].[S.l.]:Cisco System Inc， 2000.

[4]李濤，石志強(qiáng)，吳志美.橋接局域網(wǎng)2層拓?fù)浣Y(jié)構(gòu)自動發(fā)現(xiàn)[J].計算機(jī)科學(xué)，2003，30(12):6-8， 15.

[5]SON M H， JOO B S， KIM B C， et al. Physical topology discovery for metro Ethernet networks[J].ETRI Journal，2005， 27(4):355-366.

[6]BREITBART Y， GAROFALAKIS M， MARTIN C， et al. Topology discovery in heterogeneous IP networks[C]//Proc of IEEE INFOCOM.New York: IEEE Press，2000:265-274.

[7]BREITBART Y， GAROFALAKIS M， JAI B， et al. Topology discovery in heterogeneous IP networks:the net inventory system[J].IEEE/ACM Trans on Networking， 2004， 12(3): 401-414.

[8]LOWEKAMP B， O’HALLARON D R， GROSS T R. Topology discovery for large Ethernet networks[C]//Proc of ACM SIGCOMM.New York:ACM Press， 2001:237-248.

[9]鄭海，張國清.物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究[J].計算機(jī)研究與發(fā)展，2002，39(3):264-268.

[10]BEJERANO Y， BREITBART Y， GAROFALAKIS M， et al. Physical topology discovery for large multisubnet networks[C]//Proc of IEEE INFOCOM. New York:IEEE Press，2003:342-352.

[11]SUN Yantao， SHI Zhiqiang，WU Zhimei. A discovery algorithm for physical topology in switched Ethernets[C]//Proc of the 30th Annual IEEE Conference on Local Computer Network. Sydney:[s.n.]，2005.

[12]BLACK R， DONNELLY A， FOURNET C. Ethernet topology discovery without network assistance[C]//Proc of the 12th IEEE International Conference on Network Protocols. Berlin:[s.n.]， 2004:328- 339.

[13]IEEE 8021.D—1990， Media access control (MAC) bridges[S].1990.

[14]DECKER E，LANGILLLE P，RIJSINGHANIA， et al. RFC 1493， Definitions of managed objects for bridges[S]. 1993.

[15]孫延濤，吳志美，石志強(qiáng).一種基于地址轉(zhuǎn)發(fā)表的交換式以太網(wǎng)拓?fù)浒l(fā)現(xiàn)算法[J].軟件學(xué)報，2006，17（12）：2565-2576.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”