交換式以太網物理拓撲發現的進展與研究

摘要：著重介紹了交換式以太網的物理拓撲發現算法，包括基于交換機生成樹信息的方法、基于地址轉發表的方法和基于探測包的方法；最后指出關于物理拓撲發現的一些研究重點。

關鍵詞：網絡管理； 物理拓撲發現； 交換式以太網

中圖分類號：TP393.07文獻標志碼：A

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

在早期的以太網中，同一個子網（網段）內的多個網絡終端采用載波偵聽多路訪問和沖突檢測技術CSMA/CD (carrier sense multiple access/collision detect)共享同一個傳輸媒介，構成了一個廣播域。由于廣播域內的設備不能同時訪問傳輸媒介，稱為沖突限制，導致單個以太網廣播域內的設備不能很多，一般只有幾十個，網絡規模和拓撲結構非常簡單。

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

網絡拓撲發現是網絡管理中的一個重要內容，主要解決網絡層和鏈路層的拓撲自動發現問題。早期對網絡拓撲的研究主要集中在網絡層上，利用SNMP或通用的ICMP（利用ping、traceroute等工具）^[1，2]。隨著交換技術的引入，以太網的規模迅速增加，在同一個子網中可以包含幾百個設備，網絡拓撲結構也變得更加復雜。鏈路層網絡拓撲信息對于網絡管理的重要性也隨著突顯出來。鏈路層拓撲發現的目標是確定網絡中各種設備以及這些設備物理端口之間的連接關系，通常稱之為物理拓撲發現。準確及時的物理拓撲信息對于網絡性能監測與評估、故障發現與定位、資源分配與管理、網絡維護等一系列工作具有重要意義。比如，對于故障定位來說，通常一個單一的故障可能會引起一系列故障告警風暴。這些告警會出現在不同的網絡設備上，網絡設備之間的連接關系對于過濾掉次要的告警信息、確定告警源是至關重要的。

1物理拓撲發現的困難

物理拓撲發現的目標是發現交換機等網絡設備端口之間的連接關系。相對于網絡層（OSI的第三層）的拓撲發現，物理拓撲（即二層網絡拓撲）發現更加困難。因為網絡層拓撲是非常清楚的，每一個路由器都清楚地知道它們的鄰居節點。物理拓撲發現需要面對如下困難：

a）二層設備的透明性。與三層設備路由器不同，交換機設備對于數據傳輸的發送端設備和接收端設備是完全透明的，它們根本不知道交換機的存在，就像在一個共享傳輸媒介的CSMA/CD以太網中傳輸數據一樣。

b）網元設備的異構性。拓撲發現算法必須能夠正確識別并獲取各種類型的設備信息，如路由器、交換機、各種服務器和工作站等。這些設備可能是思科（CISCO）、朗訊、北電等大網絡設備公司的產品，也可能是不知名公司的產品。

c）復雜的網絡拓撲結構。一個復雜的網絡中可能存在著星型、總線型和環型網絡結構，運行如IBM SNA、Xero XNS、AppleTalk、TCP/IP和DECnet等多種網絡協議。

另外還有很多因素影響著網絡拓撲發現，像網絡中存在著集線器（hub）等不可管理的設備、網絡拓撲的動態變化以及拓撲相關信息的匱乏等。因此一個適應各種網絡環境的網絡拓撲發現算法是不存在的。本文主要是針對交換式以太網的物理拓撲發現算法。

2物理拓撲發現方法

從2000年開始，國內外研究人員開始對交換式以太網的物理拓撲發現進行了較為深入的研究。在標準制定方面，2000年9月，IETF發布了關于物理拓撲MIB（PTOPOMIB）的RFC^[3]用于指導網絡層以下拓撲結構的發現。它定義了標志網絡端口之間連接和發現SNMP代理的網絡地址的統一標準。該RFC沒有規定物理拓撲的發現機制。它需要拓撲發現方法來完成相關MIB變量的填充。

在發現方法方面，研究人員提出了基于交換機生成樹 (spanning tree)的算法^[4，5]、基于地址轉發表(address forwarding table，AFT)的算法^[5，6~11]和基于探測包的算法^[12]。由于交換機一般均采用地址轉發表進行數據幀的轉發，基于地址轉發表的算法成為目前適用范圍最為廣泛的通用方法。不加特殊說明，后面所提到的網絡拓撲均是指網絡物理拓撲。

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

為了保證節點間能夠正常通信，避免廣播風暴的發生，交換式以太網的拓撲結構必須是樹型的；然而為了提高網絡的可靠性，網絡管理員有時會在局域網段之間設置并行的兩條或多條路徑，這就會在拓撲結構中產生回路。交換機之間會通過協商（如使用文獻[13]中生成樹協議）阻塞部分路徑保證整個網絡拓撲是一個樹型結構。這就是生成樹。交換機生成樹信息可以從dot1dStp MIB組^[14]中獲取得到。

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

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

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

基于生成樹信息的方法的優點在于時間和空間消耗較小，可以發現局域網中的備用鏈路；缺點是許多交換機不支持生成樹協議，適用范圍受到一定限制，并且該方法不能發現交換機與主機之間的連接關系。

2．2基于地址轉發表的方法

上面提出的兩種方法均可以應用于多子網的拓撲發現。它們需要計算任意一對節點之間的連接關系，計算量比較大。筆者在文獻[11]中針對單子網的情況，提出了一種更為簡潔的拓撲發現新算法。該方法把網絡拓撲結構看做一棵拓撲樹，把網絡節點之間的連接關系分為直系關系和旁系關系，并給出一組判定定理用于確定網絡節點之間的連接關系。該算法利用以太網拓撲結構是無環的樹型結構這一特點（現有算法大多忽視了這一點，把網絡拓撲作為更為復雜的網狀結構處理），能夠有效減少拓撲發現的時間，通過對連接沖突的處理，保證拓撲發現的準確性。

2．2．3其他方法

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

3主要問題和發展方向

總體來說，上述方法，特別是基于非完整地址轉發表的方法已經較好地解決了交換式以太網的物理拓撲發現問題。但是在該領域仍然有很多問題需要深入研究和解決。

a）需要研究這些拓撲發現方法和PTOPOMIB^[3]的結合問題，即如何利用這些方法來為PTOPOMIB對象進行賦值，從而允許各種不同的拓撲發現方法通過SNMP結合在一起，在不同的網絡環境下采用不同的拓撲發現算法，提高拓撲發現算法的可擴展性。

b）Ad hoc網絡和傳感器網絡等新型網絡的拓撲發現問題。像Ad hoc中節點的移動性，網絡拓撲動態性、不穩定的鏈路狀態等問題均會給網絡拓撲發現和拓撲刷新等帶來非常大的挑戰。

c）IPv6帶來的新問題。需要研究IPv6網絡大地址空間、層次化地址結構等特點對拓撲發現的影響問題。

此外，VLAN網絡、重疊網絡的拓撲發現，非交換式以太網的拓撲發現等方面還需要更多深入的研究。

4結束語

物理拓撲發現是網絡管理的一個主要內容。本文主要介紹當前國內外學者在物理拓撲研究方面的最新進展以及筆者在該方面工作中所取得的一些研究成果；指明了物理拓撲研究中目前尚待解決的一些問題，可以幫助研究人員在這方面少走彎路，更快地深入到關鍵問題的研究當中。

參考文獻：

[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]李濤，石志強，吳志美.橋接局域網2層拓撲結構自動發現[J].計算機科學，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]鄭海，張國清.物理網絡拓撲發現算法的研究[J].計算機研究與發展，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]孫延濤，吳志美，石志強.一種基于地址轉發表的交換式以太網拓撲發現算法[J].軟件學報，2006，17（12）：2565-2576.

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