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