摘 要： 介紹了幾種常見的網(wǎng)絡拓撲" title="網(wǎng)絡拓撲">網(wǎng)絡拓撲發(fā)現(xiàn)工具，從負載、速度、準確性及適用范圍幾個方面對各工具的執(zhí)行效果進行了對比；分類歸納了常用的網(wǎng)絡拓撲發(fā)現(xiàn)的方法；分析了利用這些方法實現(xiàn)的七種拓撲發(fā)現(xiàn)算法，并針對每種算法詳細列出了其優(yōu)缺點。給出了對網(wǎng)絡拓撲發(fā)現(xiàn)算法進行評價的標準及其量化的表示形式。
關鍵詞： 拓撲發(fā)現(xiàn) 算法 SNMP ICMP
近年來，由于計算機網(wǎng)絡的迅速發(fā)展，有效的網(wǎng)絡管理得到了越來越多的重視，而獲得最新的網(wǎng)絡拓撲結構" title="拓撲結構">拓撲結構對于網(wǎng)絡管理至關重要。因為網(wǎng)絡具有動態(tài)特性，并且網(wǎng)絡規(guī)模日益增大，利用人工維護網(wǎng)絡的拓撲圖幾乎不可能。因此，網(wǎng)絡拓撲自動發(fā)現(xiàn)技術的研究廣泛開展起來。Cornell大學的CNRG研究組、美國南加州大學USC(University of Southern California)的SCAN研究組和Internet數(shù)據(jù)分析合作組織CAIDA(Cooperative Association for Internet Data Analysis)等都在該領域進行了大量的研究工作，并取得了很多成果。網(wǎng)絡拓撲發(fā)現(xiàn)涉及到網(wǎng)絡體系結構的各個層次，可以利用很多協(xié)議設計不同的算法。各種算法的性能差距很大，各有所長。判斷一種算法優(yōu)劣的指標主要是：負載、速度和準確性等，具體說就是一個算法在不過多增加網(wǎng)絡負載的前提下，盡量提高收斂速度和準確性。以前的網(wǎng)絡拓撲發(fā)現(xiàn)算法主要集中精力在發(fā)現(xiàn)網(wǎng)絡的邏輯拓撲(基于第三層的)，這些算法忽略了第二層的網(wǎng)絡設備(交換機或網(wǎng)橋)的連接。即使提供了第二層的網(wǎng)絡拓撲發(fā)現(xiàn)，也是針對具體的網(wǎng)絡設備，不具有通用性。近年來，出現(xiàn)了一些通用的基于第二層的網(wǎng)絡拓撲發(fā)現(xiàn)算法。
1 拓撲發(fā)現(xiàn)的常用工具
1.1 ARP協(xié)議
每個支持地址解析協(xié)議ARP(Address Resolution Protocol)的網(wǎng)絡設備中都維護著一張ARP表，該表中記錄了該設備所連接的以太網(wǎng)中網(wǎng)絡設備的IP地址和MAC地址的對應關系。根據(jù)ARP表的這個特點，可以從一臺已知的路由器或交換機的ARP表發(fā)現(xiàn)其連接的以太網(wǎng)中其他網(wǎng)絡設備，再從這些新發(fā)現(xiàn)的設備中區(qū)分出路由器和交換機，并繼續(xù)根據(jù)這些設備的ARP表進行網(wǎng)絡設備發(fā)現(xiàn)。依此類推，就得到了整個網(wǎng)絡的拓撲結構。
1.2 SNMP協(xié)議
利用簡單網(wǎng)絡管理協(xié)議SNMP(Simple Network Management Protocol)，一個管理工作站可以遠程管理所有支持這種協(xié)議的網(wǎng)絡設備，包括監(jiān)視網(wǎng)絡狀態(tài)、修改網(wǎng)絡設備配置和接收網(wǎng)絡事件警告等。SNMP協(xié)議利用管理信息庫MIB(Management Information Base)管理網(wǎng)絡設備的配置和狀態(tài)信息，每個支持SNMP的被管理設備都維護了一些MIB庫。其中，最常用的是MIBII(RFC-1213)和Bridge-MIB(RFC-1493)。
1.3 ICMP協(xié)議
在網(wǎng)絡拓撲發(fā)現(xiàn)中主要利用了Internet控制消息協(xié)議ICMP(Internet Control Message Protocol)的echo(回應)請求、echo應答和超時這三種報文。拓撲發(fā)現(xiàn)中常用的工具Ping就是利用ICMP的echo報文發(fā)現(xiàn)網(wǎng)絡的連通性，而Traceroute則是利用ICMP超時報文發(fā)現(xiàn)網(wǎng)絡中兩節(jié)點間的路徑。Mercator算法就是利用啟發(fā)式規(guī)則和限制跳數(shù)的Traceroute進行拓撲發(fā)現(xiàn)[1]。
1.4 DNS Zone Transfer
域名服務器DNS(Domain Name Service)中保存了域內(nèi)的主機名和IP地址的對應關系列表?！皕one transfer”命令可以使DNS服務器返回域內(nèi)所有域名的列表，所以DNS Zone Transfer可被用來發(fā)現(xiàn)域內(nèi)的主機和路由器。
1.5 其他拓撲發(fā)現(xiàn)工具
利用路由信息協(xié)議RIP(Routing Information Protocol)、開放最短路徑優(yōu)先協(xié)議OSPF(Open Shortest Path First)或邊界網(wǎng)關協(xié)議BGP(Border Gateway Protocol)可以獲得路由設備中存儲的路由信息。利用該信息發(fā)現(xiàn)新的路由設備并判斷設備之間的連接關系。從而發(fā)現(xiàn)整個網(wǎng)絡的拓撲結構。CNRG提出的拓撲發(fā)現(xiàn)算法和CAIDA的Skitter算法都利用了BGP協(xié)議。表1列出了上述方法在執(zhí)行效果(負載、速度、準確性和適用范圍)上的對比。
2 網(wǎng)絡拓撲發(fā)現(xiàn)常用方法
2.1 基于第三層的拓撲發(fā)現(xiàn)常用方法
第三層的網(wǎng)絡拓撲發(fā)現(xiàn)方法著重于發(fā)現(xiàn)路由設備間的邏輯連接關系。它發(fā)現(xiàn)的拓撲結構并不表示網(wǎng)絡中設備的真正連接關系，而是“IP數(shù)據(jù)報轉發(fā)”意義上的連接關系。下文介紹了三種基于第三層的拓撲發(fā)現(xiàn)的啟發(fā)式規(guī)則：
規(guī)則1：利用廣播Ping進行子網(wǎng)" title="子網(wǎng)">子網(wǎng)猜測。
給定一個IP地址，可利用本規(guī)則猜測該地址所屬的子網(wǎng)掩碼：
for(MskLen=31；MskLen>7；MskLen--) {//構造主機號全為0或全為1的廣播地址
BrdcstAddrs=CnstructBrdcstAddr(MskLen)；//ping構造的廣播地址
ResultCount=BrdcstPing(BrdcstAddrs)；//若每個廣播地址都獲得了回復，算法結束，返回當前猜測的子網(wǎng)掩碼長度
if(ResultCount>=2)
return MskLen；
}
本規(guī)則的基本思想是遞減猜測子網(wǎng)掩碼的長度，對每個猜測的子網(wǎng)掩碼構造廣播ping地址，如果主機對構造的廣播地址有回應則說明猜測的子網(wǎng)掩碼是正確的[2]。
規(guī)則2：利用一組地址進行子網(wǎng)猜測。
假設知道地址集A中的IP地址同屬于一個子網(wǎng)，可利用本規(guī)則猜測這組地址所屬的子網(wǎng)地址。
①計算A的按位與BitwiseAND{A}和它的按位或BitwiseOR{A}；
?、谥鹞粚Ρ菳itwiseAND{A}和BitwiseOR{A}，找出第一個" title="第一個">第一個不相同的位；
?、蹖⒉襟E②中找到的位和其后的各位設置為0，猜測子網(wǎng)掩碼；
?、軐⒉襟E③中的結果分別與BitwiseAND{A}進行按位與，算出子網(wǎng)號。
本規(guī)則的基本思想是：對比地址集A的按位與和按位或的結果，找出第一個不相同的位，則子網(wǎng)掩碼在該位一定為0即該位及其后的各位都只能是主機號，而不可能是子網(wǎng)號。從而判斷出子網(wǎng)掩碼的長度，而子網(wǎng)地址則可通過BitwiseAND{A}與子網(wǎng)掩碼做按位與運算得出[2]。
啟發(fā)式規(guī)則2在以太網(wǎng)上的應用示例如圖1所示。以圖1為例執(zhí)行本規(guī)則,因這組地址的前三個字段相同，故不失一般性，只對第四個字段進行運算：
?、貰itwiseAND{A}=10000000，BitwiseOR{A}= 10111111；
?、贐itwiseAND{A}與BitwiseOR{A}在第三位不同；
?、圩泳W(wǎng)掩碼的最后一個字節(jié)一定為ab000000(ab為11，10或00)；
?、軐b000000與10000000(BitwiseAND{A})進行按位與,結果形如c0000000(c為1或0)。
規(guī)則3：猜測域內(nèi)的有效地址。
本規(guī)則可被用來推測已知的子網(wǎng)地址空間中有效的IP地址。其算法描述如下。
while(AliveIPList Not NULL) {
this=getIP(AliveIPList)；//獲得this后的N個地址，存入臨時地址集
GetFollowingIPs(this，N)；//this的最后一個字節(jié)為1、65、129或193
if(GetLastByte(this)=1 or 65 or 129 or 193)//選取與this具有相同前綴的N個地址，存入臨時地址集
GetIPsWithSamePrefix(this，N)；
}
N的選擇非常重要，若N過大，則能夠獲得所有的有效地址，但也會包含一些無效地址；若N太小，則發(fā)現(xiàn)的大部分地址是有效的，但同時也會遺漏一些有效地址[2]。
2.2 基于第二層的拓撲發(fā)現(xiàn)常用方法
基于第二層的拓撲發(fā)現(xiàn)方法著重于發(fā)現(xiàn)網(wǎng)絡設備端口間的物理連接?；诘诙拥耐負浒l(fā)現(xiàn)常用的2種方法如下。
(1)利用生成樹協(xié)議
以太網(wǎng)中的交換機和網(wǎng)橋都維護了一個地址轉發(fā)表，其中為每個端口保存了其轉發(fā)過的數(shù)據(jù)幀的源MAC地址，若地址轉發(fā)表是完備的，則可利用生成樹協(xié)議推導出如下三條定理，用來判斷兩個端口間的連接關系：
定理中的Si表示交換機i；Sij表示交換機i的第j個接口；Aij表示與Sij相關的地址轉發(fā)表中的MAC地址的集合，即Aij中的MAC地址都是從Sij收到的數(shù)據(jù)幀的原地址；Uijkl 表示Aij∪Akl。
?、偌僭OSij和Skl是不同的接口，如果Aij和Akl的交集不為空，則Sij與Skl沒有直連[3]；
?、诩僭Ot是至少包含兩臺交換機Sp和Sq的子網(wǎng)，如果Aij和Akl的交集為空并且Uijkl包含且僅包含Sp和Sq中的一個，則Sij與Skl沒有直連[3]；
?、奂僭OAij和Akl的交集為空，且Aij和Apt的交集為空，如果Uijkl=Uijpt并且Si和Sk屬于同一個子網(wǎng)而Sp屬于不同的子網(wǎng)，則Sij與Skl沒有直連[3]。
(2)利用端口的流量統(tǒng)計
通過對網(wǎng)絡設備的各個端口的流量數(shù)據(jù)進行統(tǒng)計，并結合其他的第二層網(wǎng)絡拓撲發(fā)現(xiàn)方法，可判斷出端口間的直連關系。
3 網(wǎng)絡拓撲發(fā)現(xiàn)的常用算法
3.1 基于SNMP和Ping的算法
算法的主要步驟是將探測源模擬成一個網(wǎng)管站與SNMP Agent通信，先取得探測源的默認網(wǎng)關，存入待探測隊列ToDoList。依次取出ToDoList中的IP，獲得該IP的MIB庫中的ipRouteTable中的數(shù)據(jù)。當ipRouteType= indirect時，可以利用ipRouteNextHop獲得路由器-路由器的連接，并將ipRouteDest存入ToDoList；當ipRouteType = direct時，利用ipRouteDest可以獲得當前路由器連接的子網(wǎng)。然后Ping子網(wǎng)內(nèi)的每個IP地址，析取ICMP回應報文的IP地址，確定出子網(wǎng)內(nèi)活動主機的信息。當ToDoList所有IP均被處理后，生成網(wǎng)絡拓撲結構圖" title="結構圖">結構圖。
3.2 基于廣播Ping和DNS Zone Transfer的算法
算法的主要步驟是首先利用DNS Zone Transfer獲得域內(nèi)設備的IP地址并存入臨時地址集，然后依次從臨時地址集中取出地址，進行以下操作，直到臨時地址集為空：利用Ping判斷該地址是否有效，若有效則將該地址存入有效地址集，并且利用廣播Ping猜測該地址所在的子網(wǎng)地址。Ping該子網(wǎng)的廣播地址，將有回復的IP歸入該子網(wǎng)，并且加入到臨時地址集。
3.3 基于Traceroute和DNS Zone Transfer的算法
算法的主要步驟是首先利用DNS Zone Transfer獲得域內(nèi)設備的IP地址并存入臨時地址集，然后依次從臨時地址集中取出地址存入this_addr，進行以下步驟，直到臨時地址集為空：利用Ping判斷該地址是否有效，若有效則將該地址存入有效地址集。Traceroute this_addr，判斷出this_addr連接的路由器地址，然后利用啟發(fā)式規(guī)則2猜測this_addr所屬的子網(wǎng)地址。
3.4 基于Ping和Traceroute的算法
算法的主要步驟是首先隨機選取域內(nèi)形式為*.1的地址并將它們存入臨時地址集，然后依次從臨時地址集中取出地址存入this_addr，進行以下步驟，直到臨時地址集為空：利用Ping判斷該地址是否有效，若有效則將該地址存入有效地址集并且根據(jù)啟發(fā)式規(guī)則3將更多的地址加入臨時地址集。Traceroute this_addr，判斷出this_addr連接的路由器地址，然后利用啟發(fā)式規(guī)則2猜測this_addr所屬的子網(wǎng)地址。
3.5 基于SNMP和ARP的算法
算法的主要步驟是將探測源模擬成一個網(wǎng)管站與SNMP Agent通信，先取得探測源的默認網(wǎng)關，存入待探測隊列ToDoList。依次取出ToDoList中的IP，獲得該IP的MIB庫中ipRouteTable數(shù)據(jù)，當ipRouteType=direct時，利用ipRouteDest可以獲得當前路由器連接的子網(wǎng)；當ipRouteType=indirect時，可以利用ipRouteNextHop獲得路由器-路由器的連接，并將ipRouteDest存入ToDoList。獲得ifToMediaNetAddress中的IP，判斷其屬于哪個子網(wǎng)。當ToDoList所有IP均被處理后，生成網(wǎng)絡拓撲結構圖。本算法與基于SNMP和Ping的算法的區(qū)別在于利用ARP表獲得子網(wǎng)中的活動IP，因此提高了算法的速度，減輕了負載，但是卻可能漏掉一些活動IP。
3.6 基于OSPF和Ping的算法
算法的主要步驟是先利用OSPF或RIP協(xié)議生成的路由信息獲得路由設備以及子網(wǎng)間的連接關系，然后利用Ping獲得子網(wǎng)中的活動主機的信息。
3.7 基于BGP和Traceroute的算法
算法的主要步驟是先利用BGP路由信息區(qū)分出Internet上的各個域，利用Ping獲得每個域中的活動主機，Traceroute這些活動主機，利用路徑信息結合BGP路由信息生成Internet主干網(wǎng)的拓撲信息。本算法主要用于發(fā)現(xiàn)Internet主干網(wǎng)的拓撲信息。
表2對以上算法的優(yōu)缺點進行了總結。
4 網(wǎng)絡拓撲發(fā)現(xiàn)算法的評價方法
(1)速度?？捎盟惴▓?zhí)行所花費的時間來衡量。算法執(zhí)行的時間分為兩部分：采集信息生成拓撲結構的時間；將生成的表示拓撲關系的數(shù)據(jù)結構以圖形化的形式顯示出來的時間。
(2)負載。因為一個算法中對網(wǎng)絡造成的負載可能由多個部分引起，如在基于SNMP的算法中，給網(wǎng)絡引入的負載包括獲得拓撲信息的SNMP數(shù)據(jù)包和為判斷一個地址是否有效所引入的ICMP報文(利用Ping引入的)?？紤]到大部分拓撲發(fā)現(xiàn)算法中都會用到基于ICMP的工具(Ping、Traceroute)，并且由ICMP所引入的負載遠遠大于其他因素引入的負載，所以可以用一個算法用到的所有ICMP報文在網(wǎng)絡中所經(jīng)歷的總跳數(shù)(hop)代表該算法對網(wǎng)絡造成的負載[2]。按照這個定義，對于Ping，假設對每個節(jié)點Ping 2次，則要判斷一個H跳處的設備是否有效所需要引入的負載是4H；對于Traceroute，假設對每個路由器發(fā)送兩個探測包，這樣對于一個在h(1≤h≤H)跳處的設備，所引入的負載是4h，則要Traceroute一個H跳處的設備所引入的負載是1到H的算術級數(shù)的4倍。
(3)完整性。可用算法發(fā)現(xiàn)的網(wǎng)絡設備數(shù)量占實際網(wǎng)絡中設備數(shù)量的百分比表示。
(4)準確性?？捎盟惴鎸Χ鄠€可選的拓撲結構的可能性來表示。
本文從協(xié)議、規(guī)則、算法及評價標準幾個方面對網(wǎng)絡拓撲發(fā)現(xiàn)技術進行了介紹，提出了量化評價網(wǎng)絡拓撲發(fā)現(xiàn)算法的方法。為初步接觸網(wǎng)絡拓撲發(fā)現(xiàn)的人員提供了全面、詳細的參考，同時也為產(chǎn)生新的網(wǎng)絡拓撲發(fā)現(xiàn)算法提供基礎研究。
參考文獻
1 施 鋒，吳秋峰.網(wǎng)絡多層拓撲發(fā)現(xiàn)算法的分析[J].網(wǎng)絡信息技術，2004；23(3)：30～32
2 Siamwalla R，Sharma R，Keshav S.Discovering Internet topol-ogy[C].In：Proceedings of IEEE INFOCOM，1999
3 Breitbhart Y，Garofalakis M，Martin C et al.Topology discov-ery in IP heterogeneous networks[C].In：Proceedings of IEEE INFOCOM，2000
4 王志剛，王汝傳，王紹棣等.網(wǎng)絡拓撲發(fā)現(xiàn)算法的研究[J].通信學報，2004；25(8)：36～43
5 熊 坤，寇曉蕤，范元書等.網(wǎng)絡拓撲發(fā)現(xiàn)算法定性分析[J].計算機工程與應用，2004；(14)：136～137
6 Lowekamp B，Hallaron D R，Gross T R.Topology discovery for large ethernet networks[C].In：Proceedings of SIGCOMM，2001
7 Bejerano Y，Breitbart Y，Garofalakis M et al.Physical discov-ery for large multi-subnet networks[C].In：Proceedings of IEEE INFOCOM，2003