導語：拓撲發(fā)現(xiàn)算法之議一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

摘要：作為配置管理的核心和資源管理的基礎，完整、精確并且具備可視化友好界面的網(wǎng)絡拓撲是檢測網(wǎng)絡故障、分析網(wǎng)絡性能的基礎，介紹了網(wǎng)絡物理拓撲發(fā)現(xiàn)的分類，基于SNMP設備的MIN-II和Bridge-MIB管理信息庫，分別設計了網(wǎng)絡層拓撲發(fā)現(xiàn)算法和數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)算法，經(jīng)測試，算法能夠準確的發(fā)現(xiàn)網(wǎng)絡層設備及連接關(guān)系，能夠比較準確的對數(shù)據(jù)鏈路層進行拓撲發(fā)現(xiàn)。

關(guān)鍵詞：拓撲發(fā)現(xiàn)算法；MIB-II；Bridge-MIB；

隨著網(wǎng)絡規(guī)模的不斷擴大和網(wǎng)絡拓撲結(jié)構(gòu)的日益復雜，網(wǎng)絡管理的地位變得越來越重要，有效、可靠的網(wǎng)絡管理已經(jīng)成為網(wǎng)絡系統(tǒng)正常運行的關(guān)鍵。OSI參考模型網(wǎng)絡管理標準中定義了網(wǎng)絡管理的5大功能，分別是故障管理、配置管理、性能管理、安全管理和計費管理[1]，其中配置管理是進行網(wǎng)絡管理的前提，其主要功能是網(wǎng)絡拓撲發(fā)現(xiàn)和各類設備的配置信息管理。網(wǎng)絡拓撲結(jié)構(gòu)是網(wǎng)絡中各節(jié)點之間互聯(lián)關(guān)系的一種表示，拓撲結(jié)構(gòu)通常被構(gòu)建成一個圖形，對網(wǎng)絡拓撲進行發(fā)現(xiàn)是對網(wǎng)絡管理系統(tǒng)最基本的功能要求，所謂拓撲發(fā)現(xiàn)是指通過某種算法探測和識別特定網(wǎng)絡中的網(wǎng)絡元素和各網(wǎng)絡元素之間連接關(guān)系，并以字符、圖形等方式將拓撲進行顯示。作為配置管理的核心和資源管理的基礎，完整、精確并且具備可視化友好界面的網(wǎng)絡拓撲結(jié)構(gòu)是檢測網(wǎng)絡故障、分析網(wǎng)絡性能的基礎[2]。

根據(jù)拓撲發(fā)現(xiàn)算法涉及的TCP/IP網(wǎng)絡層次，一般可以將網(wǎng)絡拓撲發(fā)現(xiàn)分為網(wǎng)絡層和數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)兩個層次，網(wǎng)絡層拓撲發(fā)現(xiàn)主要實現(xiàn)網(wǎng)絡層路由設備的探測、子網(wǎng)以及連接關(guān)系的發(fā)現(xiàn)，數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)的主要工作是二層設備與主機的探測及其連接關(guān)系的確定，好的拓撲發(fā)現(xiàn)算法能夠快速、準確的發(fā)現(xiàn)網(wǎng)絡中的三層和二層網(wǎng)絡設備，進而確定網(wǎng)絡拓撲[3]，利用SNMP網(wǎng)絡設備的MIB-II和Bridge-MIB管理信息庫，是進行網(wǎng)絡物理拓撲發(fā)現(xiàn)的常見方法，下邊對基于MIB-II和Bridge-MIB的拓撲發(fā)現(xiàn)算法進行討論。

1網(wǎng)絡層設備拓撲發(fā)現(xiàn)

探測三層（網(wǎng)絡層）設備最基本的方法是獲取網(wǎng)絡中路由設備的路由表（RoutingTable），路由表中記錄了目標IP地址（ipRouteDest）的下一條地址（ipRouteNextHop）以及數(shù)據(jù)的傳送方向等信息。支持SNMP的設備會將自己的路由表放在管理信息庫（ManagemnetInformationBase，MIB）中，因此，可以通過SNMP獲取遠端三層設備的路由表。

根據(jù)三層網(wǎng)絡設備SNMP的特點，設計如下拓撲發(fā)現(xiàn)算法：

Foreachrouterinrouter_set

{

ifrouterexsits(interfacetable){next;}

getipRouteTable;

getipAddrTableaddtointerface_table;

ForeachentryinipRouteTable

{

if(ipRouteType=indirect)

{

swapipRoutDestwithitsinterfaceifexsits(nterface_table);

if(ipRouteDestnot_in(router_set)

{

AddRoutertorouterset;

}

Addrouter->ipRouteDesttoedge_set;

}

}}

算法通過遍歷和分析三層設備的MIB，確定設備類型和設備間的連接關(guān)系，最后確定三層設備網(wǎng)絡拓撲結(jié)構(gòu)，使用該算法對某網(wǎng)絡中運行拓撲發(fā)現(xiàn)，結(jié)果如圖1所示。

2數(shù)據(jù)鏈路層設備拓撲發(fā)現(xiàn)

二層（數(shù)據(jù)鏈路層）設備的探測是在三層設備探測的基礎上增加路由器到交換機、交換機到交換機、交換機到主機之間的連接關(guān)系。網(wǎng)絡中的交換機同時負責維護自己的生成樹狀態(tài)表（SpanningTreeProtocol，STP）和MAC地址轉(zhuǎn)發(fā)表（ForwardData-Base，F(xiàn)DB）,并保存在標準SNMPv2-SMI（StructureofManagementInformation，管理信息結(jié)構(gòu)）中。

二層網(wǎng)絡拓撲發(fā)現(xiàn)的復雜性在于以太網(wǎng)交換機等設備的透明性。鄰居設備交換信息主要通過生成樹協(xié)議（SpanningTreeProtocol，STP）實現(xiàn)。交換機保留MAC地址和接口狀態(tài)（網(wǎng)內(nèi)主機的MAC地址與交換機端口的對應關(guān)系）的主要載體是MAC轉(zhuǎn)發(fā)表（FDB），F(xiàn)DB可以通過SNMP的Bridge-MIB來訪問?？梢院唵蔚耐ㄟ^Bridge-MIB計算得出設備之間的物理連接的關(guān)系，但由于Bridge-MIB存在時間老化、某些二層設備未配置管理IP導致網(wǎng)管無法訪問以及設備學習不全等情況，導致很難通過計算得到一張精確的拓撲結(jié)構(gòu)，這些問題需要采用特有的算法、特定技術(shù)來解決[4]。根據(jù)數(shù)據(jù)鏈路層網(wǎng)絡設備MIB-II及Bridge-MIB的特點，基本算法描述如下：

Foreachswitchinswitch_set

{

getdot1dTpFdbTable;

ifipAddisaswitch&isonlyiponthatport

{

drawedgebetweenthem;

}

}

由于二層網(wǎng)絡中還存在著啞設備、集線器等不可網(wǎng)管的設備，因此該算法對設備的發(fā)現(xiàn)還不夠完整，還需使用直接連接定理和間接連接定理進行優(yōu)化，算法如下：

ForeachSinST

{

Foreach''''x''''inPT(S)

{

ForeachEiinPAT(S,PT)

{

ForeachEkinPAT(S,PT)otherthanEi

{

If(EkdisconnectsSandEi)

{//(S)x-a(Ei)b-y(Ek)

deleteEkfromSandSfromEk;

deletePAT(Ek,y'''')fromPAT(S,x);

deletePAT(s.x'''')fromPAT(Ek,y);

applysameproceduretoallentriesinPAT(Ek,y'''')andPAT(S,x'''');

}

}

}

}}

拓撲發(fā)現(xiàn)結(jié)果如圖2所示。

3結(jié)束語

文章對基于SNMP的TCP/IP網(wǎng)絡層拓撲發(fā)現(xiàn)和數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)算法進行研究。根據(jù)網(wǎng)絡設備MIB-II和Bridge-MIB管理信息庫的特點，分別設計了網(wǎng)絡層拓撲發(fā)現(xiàn)和數(shù)據(jù)鏈路層拓撲發(fā)現(xiàn)算法。在校園網(wǎng)環(huán)境下對算法進行驗證，經(jīng)驗證，算法能夠準確的發(fā)現(xiàn)網(wǎng)絡層設備及其之間的連接關(guān)系，但是對于數(shù)據(jù)鏈路層設備和連接關(guān)系的發(fā)現(xiàn)還不夠準確，這是由于由于二層是設備的Bridge-MIB存在時間老化、啞設備以及設備學習不全等原因?qū)е碌?，要計算得到精確的拓撲結(jié)構(gòu)，還需要整合多種拓撲發(fā)現(xiàn)工具并對算法進行進一步優(yōu)化[5]，這也是需要進一步研究的方向。