黃 睿 ，王 易

（1.重慶電子工程職業(yè)學(xué)院，重慶 401331；2.東北財(cái)經(jīng)大學(xué)，遼寧 大連 116025；3.重慶信息職業(yè)技術(shù)學(xué)院，重慶 萬(wàn)州 404000）

0 引 言

互聯(lián)網(wǎng)技術(shù)興起的時(shí)候，對(duì)網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)的研究就已開(kāi)始起步。ICMP作為最早在TCP/IP網(wǎng)絡(luò)協(xié)議，被廣泛運(yùn)用到網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)中，這主要依賴(lài)于兩個(gè)網(wǎng)絡(luò)工具:Ping和Traceroute。Ping主要用于探測(cè)網(wǎng)絡(luò)的狀況，確定存活的主機(jī)；traceroute則用來(lái)追蹤報(bào)文的傳送路徑。典型的如Mercator算法[1]CNRG算法[2]都是利用了Traceroute工具來(lái)發(fā)現(xiàn)Internet的骨干拓?fù)?。其中前者是結(jié)合了啟發(fā)式算法[3]，進(jìn)行多次有限跳的主動(dòng)探測(cè)；后者則是從BGP(邊界網(wǎng)關(guān)協(xié)議)的路由信息開(kāi)始，逐步發(fā)現(xiàn)每個(gè)探測(cè)域的路由器與連接關(guān)系，最后對(duì)得到的結(jié)果進(jìn)行合并[4]。由CAIDA項(xiàng)目組設(shè)計(jì)的基于通用協(xié)議的拓?fù)錅y(cè)量工具Skitter則是先用Traceroute主動(dòng)探測(cè)轉(zhuǎn)發(fā)路徑[5]，然后通過(guò)BGP表來(lái)推測(cè)Internet內(nèi)部各自治域間的結(jié)構(gòu)。為了提高發(fā)現(xiàn)路徑的準(zhǔn)確性，解決同一個(gè)路由器多個(gè)IP的問(wèn)題[6]，針對(duì)ICMP方法的特點(diǎn)，文獻(xiàn)[7]又提出了別名探子和路徑探子的概念，別名探子識(shí)別同一臺(tái)路由器的所有IP，路徑探子仍采用了Traceroute，用來(lái)探測(cè)路徑上的路由器。算法中，很好地利用了這兩種探子的功能[8]，因此把算法的基本流程視作采用通用協(xié)議進(jìn)行拓?fù)浒l(fā)現(xiàn)的典型。

基于通用協(xié)議的算法采用了Ping和Traceroute工具，屬于主動(dòng)探測(cè)算法[9]，即由探測(cè)源主動(dòng)向待測(cè)網(wǎng)絡(luò)注入探測(cè)流量數(shù)據(jù)，因此會(huì)使用大量ICMP數(shù)據(jù)包，從而導(dǎo)致大量ICMP數(shù)據(jù)包占用網(wǎng)絡(luò)帶寬，網(wǎng)絡(luò)負(fù)載重，在算法的實(shí)現(xiàn)上也有很大的難度。此外，主動(dòng)探測(cè)在一定程度上也等同于網(wǎng)絡(luò)入侵，存在潛在的隱患，在網(wǎng)絡(luò)管理安全意識(shí)加強(qiáng)的今天，許多設(shè)備會(huì)通過(guò)防火墻等防護(hù)措施禁用ICMP包，造成了拓?fù)浣Y(jié)構(gòu)的不準(zhǔn)確和不完整。本文提供一個(gè)統(tǒng)一的標(biāo)準(zhǔn)和工具，簡(jiǎn)化網(wǎng)絡(luò)管理工作[10]。

1 簡(jiǎn)單網(wǎng)絡(luò)協(xié)議

20世紀(jì)90年代初，由J·D·Case等人提出了名為“簡(jiǎn)單網(wǎng)絡(luò)管理協(xié)議（SNMP）”的 RFC1157[11]，之后又由K·McCloghrie等人提出了基于TCP/IP協(xié)議的管理信息庫(kù)MIB-II。

SNMP的出現(xiàn)為網(wǎng)絡(luò)管理帶來(lái)了極大的便利，也給網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)提供了新的思路和方法。在SNMP出現(xiàn)以后，Glenn Mansfield等人率先提出了一種基于SNMP的網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)方法[12]，這種算法第一次提出了采用從MIB中讀取路由表的方式來(lái)獲得拓?fù)湫畔⑦M(jìn)行拓?fù)浒l(fā)現(xiàn)的思路，與通用協(xié)議相比，這種方法的特點(diǎn)是速度快，簡(jiǎn)單易實(shí)現(xiàn)，但通用性較差，要求所有目標(biāo)設(shè)備必須支持SNMP協(xié)議。

2 基于SNMP的第三層網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)

眾所周知，網(wǎng)絡(luò)層位于OSI七層模型中的第三層，所以網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)又稱(chēng)為三層拓?fù)浒l(fā)現(xiàn)。工作在網(wǎng)絡(luò)層的主要設(shè)備是路由器，網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)的目的是發(fā)現(xiàn)路由器和路由器、路由器和子網(wǎng)間的連接關(guān)系。網(wǎng)絡(luò)層拓?fù)鋵?duì)于明晰主干網(wǎng)結(jié)構(gòu)，把握被管理網(wǎng)絡(luò)的整體特征有重要作用。網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)又被稱(chēng)作邏輯拓?fù)浒l(fā)現(xiàn)，其獲取的連接關(guān)系并非網(wǎng)絡(luò)設(shè)備的實(shí)際物理連接關(guān)系，比如路由器與子網(wǎng)的連接必然通過(guò)連接子網(wǎng)內(nèi)某設(shè)備的具體端口來(lái)實(shí)現(xiàn)，而在網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)中，并不關(guān)心具體的設(shè)備端口和子網(wǎng)內(nèi)的設(shè)備信息，而把這個(gè)子網(wǎng)看作一個(gè)整體對(duì)待，如圖1所示。

圖1 網(wǎng)絡(luò)層拓?fù)鋱D

3 基于SNMP的第三層網(wǎng)絡(luò)拓?fù)湓惴ǚ治?/h2>

如圖2所示，算法首先從程序運(yùn)行的主機(jī)開(kāi)始，讀取主機(jī)MIB庫(kù)的路由表，找到ipRouteDest值為0.0.0.0的表項(xiàng)，根據(jù)前面所述可知，該表項(xiàng)為缺省網(wǎng)關(guān)對(duì)應(yīng)的表項(xiàng)。再查看對(duì)應(yīng)的ipForwarding值，當(dāng)值為1時(shí)，即可確定該缺省網(wǎng)關(guān)為路由器。獲取對(duì)應(yīng)的ipRouteNextHop值，即為此主機(jī)設(shè)置的缺省路由器的IP地址。將此路由器加到待測(cè)路由器隊(duì)列，作為拓?fù)浒l(fā)現(xiàn)開(kāi)始的種子路由器。向該種子路由器發(fā)送SNMP讀取請(qǐng)求消息，獲取該種子路由的ipRouteTable值。然后遍歷該ipRouteDest值下ipRoute-Type的每一個(gè)實(shí)例，值為3的查找其對(duì)應(yīng)的ipRouteDest與ipRouteMask，將其相與后加入子網(wǎng)隊(duì)列，記住其直連關(guān)系；值為4的查找其對(duì)應(yīng)的ipRouteNextHop，判定該ipRouteNextHop與原路由器直連，將ipRouteNextHop加入待測(cè)路由器隊(duì)列，記住其直連關(guān)系。對(duì)該路由器所有表項(xiàng)遍歷完成以后，將其對(duì)應(yīng)的ipRouteNextHop從待測(cè)路由器隊(duì)列中刪除。然后查看待測(cè)路由器隊(duì)列，將其中的路由器取出進(jìn)行相同處理，直到待測(cè)隊(duì)列為空，算法停止。

圖2 SNMP網(wǎng)絡(luò)層算法流程圖

4 原算法存在的問(wèn)題與改進(jìn)

對(duì)上述算法進(jìn)行仔細(xì)分析，發(fā)現(xiàn)存在多址問(wèn)題，即當(dāng)一個(gè)路由器只有一個(gè)IP時(shí)，按照上述方法能夠達(dá)到網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)的目的，但若一個(gè)路由器有多個(gè)IP，則會(huì)使得到的拓?fù)鋱D出現(xiàn)偏差。根據(jù)上述算法的原理可知，在讀取MIB中的每一條記錄時(shí)，是把每一條記錄作為一個(gè)設(shè)備實(shí)例來(lái)看待，也是將一個(gè)ipRouteNextHop對(duì)應(yīng)為一臺(tái)路由器。但實(shí)際情況是，一臺(tái)路由器常常有多個(gè)IP。那么當(dāng)一臺(tái)路由器的IP不止一個(gè)時(shí)，算法就會(huì)把同屬于一臺(tái)路由器的不同ipRouteNextHop當(dāng)成不同的路由器來(lái)處理，造成拓?fù)浣Y(jié)構(gòu)發(fā)現(xiàn)的偏差。例如在圖3中，實(shí)際情況是R3、R4分別與R5的A1、A2端口直連，但因?yàn)镽5的A1和A2上分別有不同的IP地址，故R3、R4的ipRouteNextHop值不相同。因此，算法就會(huì)將A1、A2對(duì)應(yīng)的兩個(gè)ipRouteNextHop處理成兩臺(tái)不同的路由器，導(dǎo)致得到的拓?fù)鋱D出現(xiàn)錯(cuò)誤。

圖3 路由器多址問(wèn)題

圖4 解決了路由器多址問(wèn)題的算法

算法思路:為了解決路由多址問(wèn)題，必須對(duì)上面所描述的基本算法進(jìn)行修正。基本思路就是將待測(cè)隊(duì)列中同屬于一臺(tái)路由器的IP地址進(jìn)行歸并，而在ip組的ipAddrTable，記錄了設(shè)備所有的IP地址信息。在ipAddrTable中，每個(gè)ipAdEntAdd實(shí)例代表設(shè)備的一個(gè)IP地址，因此，只要遍歷ipAdEntAdd的每個(gè)實(shí)例，就能獲得一臺(tái)設(shè)備的所有IP地址，從而確定哪些IP代表了一臺(tái)路由器。

算法流程:改進(jìn)的算法從這一點(diǎn)入手，每次從待測(cè)隊(duì)列中取出一個(gè)新的待處理IP之后（記為A），先遍歷隊(duì)列中其他IP對(duì)應(yīng)的ipAddrTable，這樣就能獲取每個(gè)待處理路由器的所有IP。判斷A是否在某個(gè)路由器的IP集合中，若在，則可知A與該路由器在待測(cè)隊(duì)列中的那個(gè)IP（記為M）同屬一個(gè)路由器，因此將M從待測(cè)隊(duì)列中刪除，這樣最終得到的待測(cè)隊(duì)列中的IP必然分屬不同路由器。改進(jìn)后的算法流程圖如圖4所示。

5 算法對(duì)比分析與總結(jié)

基于SNMP通用的網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)算法獲取信息的方式較為便捷，算法實(shí)現(xiàn)簡(jiǎn)單，而且發(fā)現(xiàn)效率較高、網(wǎng)絡(luò)負(fù)載較小，但由于只設(shè)定了對(duì)一個(gè)IP進(jìn)行尋址，若同個(gè)路由器有多個(gè)IP地址，則會(huì)出現(xiàn)尋址錯(cuò)誤。本文中提出的改進(jìn)SNMP算法，通過(guò)設(shè)定特殊的IP遍歷路徑，能對(duì)IP進(jìn)行準(zhǔn)確的判定，由此解決了路由器多址問(wèn)題，能夠在路由器有多個(gè)IP地址的情況下得到正確的拓?fù)浣Y(jié)構(gòu)。

與所有基于SNMP的網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)算法相同，改進(jìn)SNMP算法有效的前提是必須保證待測(cè)網(wǎng)絡(luò)內(nèi)的所有路由器都支持SNMP，并且由于可能不知道一臺(tái)路由器的共同體口令，因此沒(méi)有訪問(wèn)權(quán)限，在這種情況下就根本不能通過(guò)SNMP獲取路由器的信息，無(wú)法獲得正確的拓?fù)浣Y(jié)構(gòu)。最后，因?yàn)樵O(shè)備的SNMP協(xié)議需要手工啟用和配置，如果某臺(tái)設(shè)備雖然支持SNMP，但未啟用，同樣也無(wú)法獲取到該設(shè)備的信息。

表1 改進(jìn)SNMP算法和通用SNMP算法的對(duì)比

[1]Aman Shaikh,Mukul Goyal,Albert Greenberg,et.An OSPF Topology Server:Design and Revolution[J].http://www.cis.ohio－state.edu/～mukul/jsac.pdf

[2]BruceLowekamp,DavidHallaron,ThomasR.Gross.Topology Discovery for Large Ethernet Networks[C].SIGCOMM 2001:237－248.

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

[4]James F.Kurose,Keith W.Rose.計(jì)算機(jī)網(wǎng)絡(luò):自頂向下方法與Internet特色[M].北京:機(jī)械工業(yè)出版社,2008.

[5]W.Richard Stevens.TCP/IP協(xié)議詳解[M].北京:機(jī)械工業(yè)出版社,2008

[6]楊凱,馬季蘭.基于SNMP的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法的研究[J].電腦開(kāi)發(fā)與應(yīng)用,2008,21(3):64－66.

[7]劉亞莉,孫亞民.基于SNMP的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)自動(dòng)發(fā)現(xiàn)研究[J].微型機(jī)與應(yīng)用，2004.23(4):28－31.

[8]李琳,李杰.基于SNMP的網(wǎng)絡(luò)層拓?fù)浒l(fā)現(xiàn)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2007(8):39－42.

[9]凌軍,曹陽(yáng),李莉,等.基于ARP和SNMP的網(wǎng)絡(luò)拓?fù)渥詣?dòng)發(fā)現(xiàn)算法[J].武漢大學(xué)學(xué)報(bào).2001,47(1):67－70.

[10]丘林,張建忠.基于端口流量的物理網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法研究[J].計(jì)算機(jī)工程與應(yīng)用.2002,38(22):17l－172.

[11]張偉明,羅軍勇,寇曉蕤,蔡延榮.網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)中的路由器別名識(shí)別[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(13):143－146.

[12]R.Siamwalla.Discovering Internet Topology[A].IEEE Proceeding－IEEE INFOCOM 1999[C].New York:IEEE Press.1999:50－66.