【計算機專業(yè)優(yōu)秀論文】基于SNMP的網(wǎng)絡拓撲結構發(fā)現(xiàn)

1、畢業(yè)設計畢業(yè)設計( (論文論文) ) 題題 目目 基于基于 snmpsnmp 的網(wǎng)絡拓撲結構發(fā)現(xiàn)的網(wǎng)絡拓撲結構發(fā)現(xiàn) 學院名稱學院名稱 計算機科學與技術學院計算機科學與技術學院 指導教師指導教師 職職 稱稱 班班 級級 學學 號號 學生姓名學生姓名 年 月 日 目目 錄錄 摘摘 要要.iiiiii abstractabstract.iviv 第一章第一章 緒緒 論論.1 1 1.1 課題背景及意義 .1 1.2 本文的研究目標及文章組織 .2 1.2.1 研究目標.2 1.2.2 文章組織.3 第二章第二章 網(wǎng)絡拓撲發(fā)現(xiàn)概述網(wǎng)絡拓撲發(fā)現(xiàn)概述.4 4 2.1 網(wǎng)絡拓撲發(fā)現(xiàn)概述.4 2.1.1 網(wǎng)絡

2、拓撲發(fā)現(xiàn)概念 .4 2.1.2 網(wǎng)絡拓撲發(fā)現(xiàn)對象 .4 2.1.3 網(wǎng)絡拓撲發(fā)現(xiàn)前的準備工作 .4 2.1.4 常用的網(wǎng)絡拓撲發(fā)現(xiàn)技術 .5 2.2 snmp 協(xié)議介紹.8 2.2.1 snmp 的發(fā)展 .8 2.2.2 snmp 的協(xié)議層次 .9 2.2.3 snmp 管理模型 .9 2.2.4 snmp 協(xié)議報文和通信原語 .11 2.2.5 使用 snmp 協(xié)議時所涉及的內容.13 第三章第三章 網(wǎng)絡拓撲發(fā)現(xiàn)算法的研究網(wǎng)絡拓撲發(fā)現(xiàn)算法的研究.1818 3.1 基本算法 .18 3.2 基于 arp 和 snmp 的拓撲發(fā)現(xiàn)算法 .19 3.3 使用 dns 區(qū)域傳輸和廣播 ping 的拓

3、撲發(fā)現(xiàn)算法 .19 3.4 使用 dns 區(qū)域傳輸和 traceroute 的拓撲發(fā)現(xiàn)算法 .20 3.5 使用 traceroute 進行探測的拓撲發(fā)現(xiàn)算法 .22 3.6 基于 ospf 和 snmp 的拓撲發(fā)現(xiàn)算法 .24 3.7 骨干網(wǎng)拓撲發(fā)現(xiàn)算法 .25 第四章第四章 基于基于 snmpsnmp 的網(wǎng)絡拓撲發(fā)現(xiàn)算法的實現(xiàn)的網(wǎng)絡拓撲發(fā)現(xiàn)算法的實現(xiàn).2727 4.1 算法的原理.27 4.2 算法描述 .31 4.2.1 算法中用到的 mib 組.31 4.2.2 網(wǎng)絡拓撲發(fā)現(xiàn)的流程.33 4.2.3 網(wǎng)絡拓撲發(fā)現(xiàn)算法的實現(xiàn).35 第五章第五章 基于基于 javajava 技術的網(wǎng)絡拓撲

4、結構生成技術的網(wǎng)絡拓撲結構生成.3838 5.1 基于 web 和 java 可視化的研究 .38 5.1.1 層次型的可視化結構.39 5.1.2 java applet 在系統(tǒng)中的應用 .39 5.2 數(shù)據(jù)庫的設計 .40 5.3 拓撲結構可視化的實現(xiàn) .43 5.3.1 java applet 的實現(xiàn) .43 5.3.2 可視化模塊的實現(xiàn).44 5.3.3 對數(shù)據(jù)庫的訪問.47 5.3.4 結果展示.48 第六章第六章 總結與展望總結與展望.5050 6.1 總結 .50 6.2 展望 .50 參考文獻參考文獻.5151 致致 謝謝.5353 基于基于 snmpsnmp 的網(wǎng)絡拓撲結構生

5、成的網(wǎng)絡拓撲結構生成 劉 祺 南華大學計算機學院 2004 級 3 班 摘摘要要：隨著計算機網(wǎng)絡技術的發(fā)展和 internet 在全世界范圍內的普及，計 算機網(wǎng)絡的規(guī)模變得日益龐大，網(wǎng)絡結構也十分復雜，這使得人們對網(wǎng)絡管理 的需求越來越迫切。網(wǎng)絡拓撲發(fā)現(xiàn)技術是網(wǎng)絡管理中的一項基本功能。正確的 網(wǎng)絡拓撲信息和直觀的網(wǎng)絡拓撲圖能夠直接有效地為網(wǎng)絡管理人員提供整體性 的網(wǎng)絡結構和狀態(tài)。如何快速、準確地獲取網(wǎng)絡拓撲信息是當今各網(wǎng)絡機構共 同關注的問題。本文就是研究網(wǎng)絡拓撲發(fā)現(xiàn)技術和構造網(wǎng)絡拓撲圖的技術。 本文首先闡述網(wǎng)絡拓撲發(fā)現(xiàn)的相關概念和原理，介紹了常用的可被用來進 行網(wǎng)絡拓撲發(fā)現(xiàn)的技術，并從負載、

6、速度、準確性和使用范圍等幾個方面對各 種技術進行了分析和比較，得出以基于 snmp 協(xié)議的網(wǎng)絡拓撲發(fā)現(xiàn)技術速度最快， 使用范圍也最廣泛。利用 snmp 協(xié)議分析 mib 庫中的路由表、接口表等有關變量,從 而得到網(wǎng)絡拓撲圖的有關信息。最后，以 java 為工具.構造網(wǎng)絡拓撲圖。 關鍵詞：關鍵詞：snmp；mib；java；網(wǎng)絡拓撲發(fā)現(xiàn)；網(wǎng)絡拓撲發(fā)現(xiàn)算法 abstractabstract: : with the development of the technology of computer networks and the worldwide popularity of internet，t

7、he scale of computer networks is getting bulky and the structure of network is becoming more complex. therefore clients demand of network management becomes more urgent. topology discovery is a kind of important function of the network management. correct topology information can provide the whole n

8、etwork structure and states to network administrator directly and effectively. it is a common issue for those net work institutes to discover and obtain network topology information quickly and accurately. the purpose of this thesis is to study the technique of topology discovery, then improve on th

9、e question of algorithms and implement an accurate and effective topology information discovery module. this paper introduces the related knowledge, concept and commonly-used technology about network topology discovery and makes an analysis and synthetic comparison among them from the subject of loa

10、d, speed, accuracy and applied scope, the algorithm of network topology discovery based on snmp is the most fast and widely applied. the method uses some m ib variables such as iprouting table and interface table to analyze the network topology. at last, using java as tool construct network topology

11、 map. keykey wordswords：snmp; mib; java; network topology discovery; algorithm of topology discovery 第一章第一章 緒緒 論論 1.11.1 課題背景及意義課題背景及意義 隨著計算機及通訊技術的飛速發(fā)展，計算機網(wǎng)絡已經(jīng)滲透到社會經(jīng)濟生活 的各個方面，對社會進步與經(jīng)濟發(fā)展起著越來越重要的作用，也使人們的工作 甚至生活方式發(fā)生了巨大的變革。網(wǎng)絡規(guī)模的激增，網(wǎng)絡復雜性和異構性的焦 點化，使得網(wǎng)絡管理問題上升到了網(wǎng)絡建設的戰(zhàn)略性位置。網(wǎng)絡管理，就是監(jiān) 視、組織和控制網(wǎng)絡通信服務和信息處理所必需的各種活動

12、的總稱，確保網(wǎng)絡 長時間、正常的運行，并當其出現(xiàn)故障的時候盡快的發(fā)現(xiàn)、修復故障，使其最 大限度的發(fā)揮其應有的效益1。 在當今的信息化社會里，計算機網(wǎng)絡的穩(wěn)定和可靠運行可以說己經(jīng)成為我 們生活的一個基本保障。一個完善的網(wǎng)絡管理系統(tǒng)是計算機網(wǎng)絡能夠可靠和穩(wěn) 定運行的保證，也是進行網(wǎng)絡性能分析、網(wǎng)絡配置和安全管理等的依據(jù)。 網(wǎng)絡故障是影響網(wǎng)絡性能的重要因素，網(wǎng)管軟件應能對發(fā)生問題的網(wǎng)絡進 行故障檢測、定位和診斷分析，然后向系統(tǒng)網(wǎng)絡管理員提交網(wǎng)絡故障分析報告， 以便解決問題，提高網(wǎng)絡可用性及服務質量。早期的網(wǎng)管系統(tǒng)大多采用命令行 方式，這嚴重影響網(wǎng)管軟件的可操作性，而現(xiàn)代網(wǎng)管軟件通常都采用圖形用戶 界

13、面進行操作。網(wǎng)絡拓撲的自動發(fā)現(xiàn)是實現(xiàn)網(wǎng)絡拓撲圖形顯示的技術關鍵，而 路徑搜索是故障定位的重要內容。 所謂拓撲發(fā)現(xiàn)(topology discovery)是指發(fā)現(xiàn)網(wǎng)絡元素并確定網(wǎng)絡元素之 間的互連關系，包括互連設備(如路由器、網(wǎng)橋、交換機等)、主機和子網(wǎng)。拓 撲發(fā)現(xiàn)作為配置管理和失效管理中的一項重要功能，是網(wǎng)絡管理的一個重要組 成部分。拓撲發(fā)現(xiàn)同時也是衡量一個商業(yè)網(wǎng)絡管理系統(tǒng)成敗的重要尺度，在整 個網(wǎng)絡管理系統(tǒng)的開發(fā)中占有相當重要的地位。本論文的重點之一就是研究適 合于中小型網(wǎng)絡(如:校園網(wǎng))的拓撲自動發(fā)現(xiàn)算法。 網(wǎng)絡拓撲圖(network topology map)是拓撲結構的可視化表現(xiàn)形式，

14、拓撲 發(fā)現(xiàn)生成的網(wǎng)絡拓撲圖可以幫助網(wǎng)絡管理員掌握網(wǎng)絡拓撲結構，迅速定位失效 地點，確定失效影響的范圍，還可以成為拾取網(wǎng)絡元素并調用其它管理功能模 塊的共同出發(fā)點。隨著 www 的出現(xiàn)，基于 web 技術的網(wǎng)絡管理成為網(wǎng)絡管理的 一種新的趨勢，它使網(wǎng)絡管理不再需要地理位置、具體平臺和專業(yè)技能等要求， 從而給網(wǎng)絡管理帶來許多方便。 目前，在網(wǎng)絡管理標準中，主要有兩大網(wǎng)絡管理體系：iso 的 cmis/cmip(公共管理信息服務及協(xié)議)和 ietf 的 snmp(簡單網(wǎng)絡管理協(xié)議)，它 們從不同的技術觀點來看待網(wǎng)絡管理問題。其中 cmip 龐大、復雜，是一個大而 全的協(xié)議，難以理解、不易實現(xiàn)，且使用

15、時 cmip 的資源占用量是 snmp 的數(shù)十 倍，所以并沒有得到工業(yè)界的廣泛支持l;而 ietf 的 snmp 設計簡單、易于實 現(xiàn)，所以一經(jīng)提出就得到了工業(yè)界的廣泛響應，許多公司相繼推出了基于 snmp 協(xié)議標準的網(wǎng)絡管理系統(tǒng)和產(chǎn)品，如 sun 公司的 sunnetmanager，hp 的 openview，ibm 的 netview/6000 等等。本文所研究實現(xiàn)的網(wǎng)絡拓撲發(fā)現(xiàn)算法也 是建立在 snmp 協(xié)議基礎上的。 1.21.2 本文的研究目標及文章組織本文的研究目標及文章組織 .1 研究目標研究目標 上面一節(jié)中已經(jīng)說到在網(wǎng)絡管理軟件中,構造網(wǎng)絡拓撲是一個重要功能,能

16、 否提供一個直觀、全面的網(wǎng)絡拓撲結構是網(wǎng)絡管理的關鍵,在網(wǎng)絡拓撲的構成過 程中,會涉及這樣幾個問題: (1) 在實際網(wǎng)絡系統(tǒng)中會涉及到不同的設備平臺, 彼此之間有不同的信息表示格式,如何通過一個較為通用的接口獲取設備的拓撲 信息; (2)需要哪些信息能夠反映設備的連接狀態(tài); (3) 如何對獲取到的拓撲信 息進行進一步的處理,以直觀的形式展現(xiàn)給用戶。 在目前網(wǎng)絡運行中, snmp (簡單網(wǎng)絡管理協(xié)議) 得到了極為廣泛的應用,主 要的設備都能夠支持該協(xié)議,同時該協(xié)議提供了極為豐富的 mib (管理信息庫) 變量供網(wǎng)絡管理使用。因此 snmp 成為獲取網(wǎng)絡信息的重要方式。 圖 1.1 設計框架 如圖

17、 1.1 所示，本文的研究目標是開發(fā)一個通過基于 snmp 協(xié)議的網(wǎng)絡拓撲 發(fā)現(xiàn)算法來獲取路由信息，對采集后信息進行分析后，利用 java 技術在 web 的 環(huán)境中進行網(wǎng)絡拓撲結構（網(wǎng)絡拓撲圖）生成的系統(tǒng)。 .2 文章組織文章組織 本文首先在第二章中對網(wǎng)絡拓撲發(fā)現(xiàn)的一些常用技術進行了簡介，并著重 介紹了 snmp 協(xié)議的相關內容，第三章研究了基于不同協(xié)議的網(wǎng)絡拓撲發(fā)現(xiàn)算法， 第四章中介紹本系統(tǒng)的拓撲發(fā)現(xiàn)算法和實現(xiàn)技術，第 5 章介紹了網(wǎng)絡拓撲結構 生成的實現(xiàn)。 第二章第二章 網(wǎng)絡拓撲發(fā)現(xiàn)概述網(wǎng)絡拓撲發(fā)現(xiàn)概述 確定個規(guī)模較大且經(jīng)常變化的網(wǎng)絡拓撲結構是很困難的，但準確的拓撲信 息

18、在網(wǎng)絡管理方面起著很重要的作用，通過網(wǎng)絡拓撲信息我們可以判斷當前設 備的配置是否合理，同時它也為網(wǎng)絡故障的排除提供了重要的依據(jù)。 2.12.1 網(wǎng)絡拓撲發(fā)現(xiàn)概述網(wǎng)絡拓撲發(fā)現(xiàn)概述 .1 網(wǎng)絡拓撲發(fā)現(xiàn)概念網(wǎng)絡拓撲發(fā)現(xiàn)概念 網(wǎng)絡拓撲發(fā)現(xiàn)就是探測網(wǎng)絡拓撲機構信息，形象地描述網(wǎng)絡設備間的互連 關系。網(wǎng)絡拓撲可表示為一張無向圖 g=(n，e)，其中 n 是節(jié)點集，表示網(wǎng)絡中 的互連設備，有時候也可能是由這些設備組成的子網(wǎng)甚至是一個自治系統(tǒng) (autonomous system)；e 是邊集，表示這些設備或者網(wǎng)絡之間的連接關系7。 .2 網(wǎng)絡拓撲發(fā)現(xiàn)對象網(wǎng)絡拓撲發(fā)現(xiàn)對象 拓撲

19、發(fā)現(xiàn)的對象分為兩種，一種是設備的發(fā)現(xiàn)，包括:子網(wǎng)、路由器、交換 機、主機、接口等，甚至網(wǎng)絡本身也是發(fā)現(xiàn)對象;另一種是發(fā)現(xiàn)網(wǎng)絡元素之間的 物理布局與互連關系，其中包括路由器和路由器的連接、路由器和子網(wǎng)的連接、 路由器和交換機的連接等。設備本身的互連關系構成了拓撲發(fā)現(xiàn)的所有內容。 .3 網(wǎng)絡拓撲發(fā)現(xiàn)前的準備工作網(wǎng)絡拓撲發(fā)現(xiàn)前的準備工作 網(wǎng)絡拓撲發(fā)現(xiàn)需要明確的問題有幾個方面: 第一，需要確定拓撲發(fā)現(xiàn)要針對網(wǎng)絡層次的哪一層。只有明確了網(wǎng)絡的層 次，才能明確到底什么樣的信息需要采集，才能使算法有較好的適應性。 第二，確定采用的是被動監(jiān)測技術還是主動監(jiān)測技術來采集網(wǎng)絡拓撲信息。 被動監(jiān)測技

20、術即在所有觀測的網(wǎng)絡中都加入一個探測器，其優(yōu)點是僅向網(wǎng)絡管 理主機遞交各個網(wǎng)絡的拓撲信息，無額外流量，負擔小，但花費時間長。對大 型網(wǎng)絡來說，將探測器安裝到所涉及的各個網(wǎng)絡中并不實際。主動監(jiān)測技術即 網(wǎng)絡管理主機向所有管理網(wǎng)絡發(fā)探測包，采集返回信息，優(yōu)點是速度快，缺點 是產(chǎn)生流量大，對低速網(wǎng)絡不太合適。 第三，確定用何種方式收集信息。對于收集信息的方式，一種是采用網(wǎng)絡 管理信息協(xié)議來收集網(wǎng)絡的信息，另一種是采用一種通用的協(xié)議來實現(xiàn)對于網(wǎng) 絡信息進行采集，利用 icmp、dns 等協(xié)議向網(wǎng)絡上的設備發(fā)送消息包/接收消息 包來獲取網(wǎng)絡拓撲信息，并且在對已有信息進行分析以及處理的基礎上進一步 獲取更

21、多的信息，從而可以收集到整個網(wǎng)絡的拓撲信息。 .4 常用的網(wǎng)絡拓撲發(fā)現(xiàn)技術常用的網(wǎng)絡拓撲發(fā)現(xiàn)技術 1)ping ping 是用于 ip 網(wǎng)絡的最早的工具之一，用它來檢查一個節(jié)點是否啟動并 運行以及測量它的往返時間，通常關聯(lián)到源主機和目的主機3。這意味著我們 能夠使它來發(fā)現(xiàn)忽略下層網(wǎng)絡的信息，在某些情況下這是理想的結果。例如當 我們想要測量在幾對節(jié)點之間通信的性能而不關心網(wǎng)絡的其他部分時。ping 工 具主要用于檢測目的主機是否在網(wǎng)絡中存活，ping 一個存活的主機回應的時間 一般為微妙級或毫秒級，對一個關機的主機或不存在的主機，回應時間為 205，這樣就影響了 ping 的效率

22、。 另一個使用 ping 的途徑是定向的廣播 ping。這意味著所發(fā)送的目的地址 為一個子網(wǎng)的廣播地址，這個子網(wǎng)的所有節(jié)點必須對這個廣播 ping 進行相應。 這樣有助于快速發(fā)現(xiàn)子網(wǎng)內所有的主機(通過保存對 ping 做出回應的所有節(jié)點 的 ip 地址)。但當前的網(wǎng)絡中我們不能使用 ping 的廣播特性，因為這個特性是 網(wǎng)絡的一個安全漏洞，它可能被拒絕服務攻擊所利用。 2)traceroute 由 van jacobson 編寫的 traceroute 程序是一個能更深入探索 tcp/ip 協(xié)議 的方便可用的工具。盡管不能保證從源端發(fā)往目的端的兩份連續(xù)的 ip 數(shù)據(jù)報具 有相同的路由，但是大多

23、數(shù)情況下是這樣的。traceroute 程序可以讓我們看到 ip 數(shù)據(jù)報從一臺主機到另一臺主機所經(jīng)過的路由。traceroute 程序還可以讓我 們使用 ip 源路由選項。 traceroute 程序使用 icmp 報文和 ip 首部中的 itl 字段(生存周期)。其原 理如下:開始時，源主機將 ip 報文的 ttl 值設置為 1，發(fā)送至目的主機，第一 個路由器收到此報文后，將 ttl 值減 1，丟棄此報文，并發(fā)送一個超時的 icmp 報文給源主機，信源接收到此報文后，解析出第一個路由器的地址。然后，源 主機將 ttl 為 2 的報文發(fā)送給目的主機，第一個路由器把它的 ttl 值減 1 后轉

24、發(fā)給第二個路由器，第二個路由器收到后再減 1，報文 ttl 值變?yōu)?0，該路由器 丟棄此報文，并發(fā)送一個類型為超時的 icmp 報文給源主機。這樣就得到了第二 個路由器的地址。如此循環(huán)下去，直至報文正確到達，源主機得到了通往目的 主機的路由。通過 traceroute 還能得到從源主機到這條路徑上任何一個節(jié)點的 往返延時。traccroute 和 ping 都有當目的節(jié)點不存在時時間延遲較大的缺點。 并且當路徑上的路由器對源節(jié)點發(fā)送的包不相應時，traceroute 可能產(chǎn)生錯誤 的結果。 3)snmp 隨著 internet 的迅速發(fā)展，作為 internet 標準的 tcp/ip 協(xié)議也在

25、發(fā)展。 tcp/ip 技術是連接異構網(wǎng)絡的有效工具，目前己經(jīng)成為事實上的標準，這樣基 于 tcp/ip 的 snmp 由于易于實現(xiàn)，也成了網(wǎng)絡管理事實上的標準。每個設備的 mib 中存儲了設備所運行的進程、表現(xiàn)方式和可以讀取的一切信息。利用 snmp 協(xié)議，可以獲得所需的設備信息，根據(jù)這些信息來構造網(wǎng)絡拓撲關系。筆者將 在后面對該協(xié)議進行詳細的介紹。 4)dns 一個域的域名服務器(dns)維持該域內的每個名字到其 ip 地址的綁定。大 多數(shù)域名服務器通過“區(qū)域傳輸”命令返回該域內名字的列表。由此理論上 dns 的域轉換可以發(fā)現(xiàn)域內的所有主機和服務器。這種技術快速、準確、開銷 小。但是發(fā)現(xiàn)不準

26、確，因為用 dhcp 獲取 ip 地址的主機并沒有 dns 服務，而且， 有的網(wǎng)絡因為安全原因關閉了 dns 域轉換服務1。 5)arp 地址解析協(xié)議(arp)在 ip 地址和物理地址之間做映射。arp 協(xié)議是一個基 礎協(xié)議，它的運行對于應用程序或系統(tǒng)管理員來說一般是透明的9。有以下優(yōu) 點:第，arp 是動態(tài)的。之所以稱為動態(tài)的是因為這個過程是自動完成的，一般 應用程序用戶或系統(tǒng)管理員不必關心。第二，arp 是一個標準并且對每個支持 tcp/ip 的設備都可用，與鏈路協(xié)議無關。第三，arp 可用于 ip 子網(wǎng)，提供在一 個路由 intemet 中設備間通信非常簡單的方法。 6)其它技術 路由信

27、息協(xié)議(rip) rip 協(xié)議是一種距離向量路由協(xié)議，它要求路由器每個節(jié)點存放到各個目 標節(jié)點的距離。距離指到達目標節(jié)點所經(jīng)過的跳數(shù)。rip 要求所有或部分路由 器侮隔 30 秒向相鄰路由器發(fā)送自己完整的路由表，同時接收其他相鄰路由器發(fā) 送來的路由表項更新報文，將其距離值與其本身的路由表進行比較更新。每個 路由表項設定相應的定時器，若在六個路由器廣播周期內沒有收到該路由表項 的更新報文，則認為該路由表項失敗，并在 240 秒后將其從路由表中刪除。 利用 rip 協(xié)議，可以從路由器設備中提取通過該設備的所有 ip 地址或 ip 子網(wǎng)的路由信息表，構造出拓撲信息連接表，但 rip 沒有子網(wǎng)地址的概

28、念，沒 有端口級的拓撲連接信息3。并且要求所有的路由器支持 rip 協(xié)議。 開放最短路徑優(yōu)先(ospf)協(xié)議 ospf 是除 rip 外的另一個內部網(wǎng)關協(xié)議，運行在一個自治系統(tǒng)中，與采用 距離向量的 rip 協(xié)議不同的是，ospf 是一個鏈路狀態(tài)協(xié)議。距離向量的意思是 rip 發(fā)送的報文包含一個距離向量(跳數(shù))。每個路由器根據(jù)它所接收到鄰站的 這些距離向量來更新自己的路由表。在一個鏈路狀態(tài)協(xié)議中，路由器并不與其 臨站交換距離信息。它采用的是每個路由器主動地測試與其鄰站相連鏈路的狀 態(tài)，將這些信息發(fā)送給它的其他鄰站，而鄰站將這些信息在自治系統(tǒng)中傳播出 去，每個路由器接收這些鏈路狀態(tài)信息，并建立起

29、完整的路由表6。 通過訪問自治系統(tǒng)每個區(qū)域中某個路由器相關的 ospf 路由表信息，可以構 造整個自治系統(tǒng)的網(wǎng)絡拓撲圖。 對以上網(wǎng)絡拓撲發(fā)現(xiàn)的各種技術的分析比較如下表 2.1，從這張表中可以 看出，網(wǎng)絡拓撲發(fā)現(xiàn)的各種技術各有利弊。 表 2.1 各種拓撲發(fā)現(xiàn)技術的比較 pingtraceroutesnmpdnsarposrf rip 適用性 所有網(wǎng)絡 域 所有網(wǎng)絡域 多數(shù)網(wǎng)絡 域 少數(shù)網(wǎng)絡 域 所有網(wǎng)絡 域 少數(shù)網(wǎng)絡 域 網(wǎng)絡負 載 低高低低低低 速度慢慢快快快快 準確性較準確較準確較準確較準確較準確準確 2.22.2 snmpsnmp 協(xié)議介紹協(xié)議介紹 由于本論文是基于 snmp 協(xié)議下的，所

30、以筆者在這里著重的介紹一下 snmp。 snmp(簡單網(wǎng)絡管理協(xié)議)是目前最流行的一個網(wǎng)絡管理協(xié)議。作為應用層 上的協(xié)議，它主要通過一組 internet 協(xié)議及其所依附的資源提供網(wǎng)絡管理服務。 利用 snmp 管理工作站可以遠程管理所有支持這種 snmp 的網(wǎng)絡設備，包括監(jiān)視 網(wǎng)絡狀態(tài)、修改網(wǎng)絡設備配置、接收網(wǎng)絡事件警告等。 .1 snmpsnmp 的發(fā)展的發(fā)展 snmp 在 1989 年作為基于 tcp/ip 互聯(lián)網(wǎng)的一個標準而被廣為接收和采用。 1991 年發(fā)布了 snmp 的一個補充 rmon(remote network monitoring:遠程網(wǎng)絡監(jiān) 控)。rmo

31、n 擴充了 snmp 的功能，包括對 lan 的管理以及對依附于這些網(wǎng)絡的設 備的管理。1993 年，snmp 的改進版 snmpv2 開始發(fā)布，自此，原來的 snmp 便被 稱為 snmpvl。最初的 snmpv2 最大的特色是增加了安全特性，因此被稱為安全 版的 snmpvl。但不幸的是，經(jīng)過兒年試用，snmpv2 并沒有得到廠商和用戶的積 極響應，并且也發(fā)現(xiàn)自身還存在一些嚴重缺陷，因此，在 1996 年正式發(fā)布的 snmpv2 中，安全特性被刪除了。這樣，snmpv2 對 snmpvl 的改進程度便受到了 很大的削弱。總的來講，snmpv2 對 snmpvl 的改進主要包括以下三個方面:

32、支持 分布式管理、改進的管理信息結構(smi)和增強了管理信息通信協(xié)議的能力。最 后，在 1998 年發(fā)布了 snmpv3，它定義了 snmp 的安全性以及將來改進的總體結 構，在 snmpv3 介紹文檔中對 snmpv3 的表述為:snmpv3 等于 snmpv2 加上安全和 管理。snmpv3 預定于 snmpv2 一起使用，但也可以和 snmpv1 一起使用1。 .2 snmpsnmp 的協(xié)議層次的協(xié)議層次 簡單網(wǎng)絡管理協(xié)議(snmp)是一個應用層的協(xié)議，它用于實現(xiàn)網(wǎng)絡設備之間 管理信息的交換。使用 snmp 來訪問網(wǎng)絡設備的 mib 數(shù)據(jù)庫，網(wǎng)絡管理員可以迅 速發(fā)現(xiàn)影響

33、網(wǎng)絡性能的問題并解決問題1。 snmp 工作于 udp 協(xié)議之上，因此使用它在主機間通訊時無需先建立連接。 這種方法降低了系統(tǒng)開銷，但對報文到達的正確性不做保證。 snmp 將管理問題分為兩個部分，并為每個部分定義了標準。第一部分是有 關信息通信規(guī)則的，協(xié)議定義了管理機上的客戶軟件如何與代理通信，同時定 義了管理機與代理交換消息的格式和含義以及名字與地址的形式。第二部分有 關被管理的數(shù)據(jù)，協(xié)議定義網(wǎng)絡設備必須保存的數(shù)據(jù)項和每個數(shù)據(jù)項的名字以 及用于表示名字的語法。 .3 snmpsnmp 管理模型管理模型 snmp 的網(wǎng)絡管理模型如圖 2.1 所示，包括四個關鍵元素1： 圖 2

34、.1 snmp 管理模型 l)管理工作站:一般是一個單機設備或者是一個共享網(wǎng)絡中的一員。無論是 哪種情況，管理站都是管理者作為網(wǎng)絡管理員與網(wǎng)絡管理系統(tǒng)的接口。 2)管理代理:當前主流路由器、交換機等設備現(xiàn)在都支持 snmp 操作，即對 來自管理站的 snmp 信息查詢和請求做出響應，同時還可能異步的通過 trap 操 作主動向管理站提供一些重要的非請求信息。 3)管理信息庫:描述了所有可以由 snmp 管理的信息的集合，其中每個信息 元素都稱為一個對象。任何支持 snmp 協(xié)議的代理都應該能夠對 mib 中定義的對 象的信息的查詢做出響應，任何使用 snmp 協(xié)議的網(wǎng)絡管理站也都應該知道它能

35、夠從代理那里得到的信息都在 mib 定義的范圍內。 4)網(wǎng)絡管理協(xié)議:管理站和代理之間是通過 snmp 網(wǎng)絡管理協(xié)議連接的， snmp 協(xié)議是一個應用層協(xié)議，使用網(wǎng)絡層提供的 udp 傳輸服務來傳遞消息、 ， 標準的代理監(jiān)聽端口為 161。當一個網(wǎng)管應用要求得到代理端的信息的時候， 它就向 snmp 核心進程提出這個請求，核心進程從本地的 mib 中得到所需的對象 的信息，然后構造 snmp 請求報文，最后將此報文使用 udp 協(xié)議發(fā)送到代理進程 的 161 端口上。代理進程在收到這個請求后，訪問其本地的 mib 庫以取出管理 站所需信息，然后構造 snmp 響應報文，最后使用 udp 協(xié)議將

36、此報文發(fā)送給管理 站。管理站的 snmp 核心進程再將得到的信息傳遞給管理站上的網(wǎng)管應用就完成 了一次信息交換。 .4 snmpsnmp 協(xié)議報文和通信原語協(xié)議報文和通信原語 1)snmp 協(xié)議報文 (l)snmp 協(xié)議的報文格式如下1: 圖 2.2 snmp 報文格式 (2)一個 snmp 實體傳遞一個報文給另一個 snmp 實體的過程: 首先，利用上面的格式，構造一個 pdu。 其次，連同源地址、目的地址和共同體名，將該 pdu 傳給認證服務，由認 證服務進行必要的數(shù)據(jù)轉換，然后返回結果。 再次，協(xié)議實體構造一個 snmp 報文，包括一個版本號、共同體名和由認證 服務返回的

37、結果。 最后，用基本編碼規(guī)則，為報文進行編碼，并將編碼結構傳給傳輸服務。 (3)一個 snmp 實體在接收 snmp 報文時的過程: 首先，對報文進行基本語法檢查，如果解析錯誤，就拋棄該報文。 其次，驗證 snmp 版本號，如果不匹配，就拋棄報文。 最后，協(xié)議實體將用戶名字、源地址、目的地址和報文中的 pdu 部分傳給 認證服務:如果失敗，認證服務給 snmp 協(xié)議實體發(fā)信號，指示它產(chǎn)生一個 snmp trap 報文以及拋棄該報文。 2)變量綁定 當管理站想要得到一個特定代理的特定 mib 組中的所有標量對象信息時， 它 可以發(fā)送一個請求所有標量的報文，并且得到一個包含所有值的響應。這 樣可以

38、減輕網(wǎng)絡管理的通信負擔。為了實現(xiàn)上述的對象交換，所有的 snmppdu 都包括一個變量綁定的域。這個域由一系列對象實例標識符和這些對象實例的 值組成。 3)通信原語 snmp 定義了 5 種通信原語實現(xiàn)管理進程和代理進程之間的交互信息，它們 分別是1:(l)get-request 原語:get- request pdu 由網(wǎng)絡管理站的 snmp 實體 發(fā)出。它包括的域山前血的報文格式中給出。pdu 類型說明這是 get-request pdu。request-id 是發(fā)送實體為每個請求分配一個編號，用以標識同一代理的 多個未完成的請求，variable-binding 是經(jīng)過 2)操作的被請求

39、的對象實例列表。 管理代理的 snmp 實體在接收一個 get-request pdu 后，通過返回一個 get- response pud 作為響應。如果代理的 snmp 實體能夠為收到的 pdu 中變量綁定 列表的所有變量提供值，則 get-response pdu 為變量綁定域中每個變量賦一個 值。如果其中任何一個變量的不能得到，則所有變量的值均不返回。 (2)get-next-request 原語:與 get-request 操作有相同的數(shù)據(jù)格式和相同 的數(shù)據(jù)交換模式。它們的操作都是原子同步方式，即要么所有的請求值都被返 回，要么一個也不返回。不同之處是:get-request pdu

40、 的變量綁定列表中的每 個變量指的是將要被返回的對象實例，而對于 get-next-request pdu，每個變 量將要返回的是按字典排序的下一個對象實例的值。get-next-request pdu 的 工作模式使得管理站可以動態(tài)發(fā)現(xiàn)一個 mib 視圖的結構，同時也為檢索一個未 知的表提供了有效的方法。這時，代理返回的是列表中每個對象標識的按字典 排序的下一個對象實例的值。 (3)set-request 原語:由管理進程發(fā)出，請求設置進程中一個或多個變量 的值。 (4)get-response 原語:由代理進程發(fā)出的，向管理進程返回的一個或多個 變量的值，它是 set-request 操作

41、的相應。 (5)trap 原語:代理進程主動發(fā)出的報文，通知管理進程有某事發(fā)生。 .5 使用使用 snmpsnmp 協(xié)議時所涉及的內容協(xié)議時所涉及的內容 管理信息庫管理信息庫 mibmib 管理信息庫 mib(management information base)是網(wǎng)絡管理系統(tǒng)中所有被 管理元素信息的數(shù)據(jù)庫23。數(shù)據(jù)庫中的元素是網(wǎng)管中的被管資源，且被管資 源以對象來表示，每個對象表示被管資源某一方面的屬性。通過對這些對象的 存取訪問，就可以得到網(wǎng)絡設備的所有靜態(tài)或動態(tài)內容，涵蓋網(wǎng)絡性能、配置、 路由和故障等各個方面。每個對象又包含若干信息變量，每

42、個信息變量包含如 下信息:變量名、變量的數(shù)據(jù)類型、變量的讀寫屬性、變量的值。 l)mibl)mib 的數(shù)據(jù)結構的數(shù)據(jù)結構 mib 是一個樹形結構的數(shù)據(jù)庫，樹中的每個節(jié)點都是一個對象，mib 就是由 一系列的對象組成，如下圖所示: system(1) interface(2) at(3) ip(4) icmp(5) tcp(6) udp(7) egp(8) org(3) ccitt(0)iso-joint-ccitt(2) intemet(l) diretory(1) dod(6) mgmt(2)private(4) enterprises(1) experimental(3) m

43、ib- ..1 root iso(1) 圖 2.3 mib 的樹型結構 root 為 mib 樹的根節(jié)點，它有三個子樹: iso(1)：由 iso 管理。 ccitt(0)：由 ccitt 管理。 iso-joint-ccitt(2):由 150 和 ccitt 共同管理。 在 iso(l)節(jié)點下由一些其它的子樹，其中 0rg(3)是 iso 為其他組織定義的 子樹。在 org(3)子樹下，一個值得引起注意的特殊節(jié)點是 dod(6)，該節(jié)點被分 配給了美國國防部使用。dod(6)節(jié)點下的一個子樹 internet(l)分配給 internet 體系結構委員會來管理

44、。 在 internet(1)節(jié)點下包括了四棵子樹: (l)directory(1)子樹 該子樹保留給 051 目錄服務，以備將來使用。 (2)mgmt(2)子樹 該子樹用于那些在 iab( internet 體系結構委員會)所批準認可的管理信息 庫的定義，目前有兩個版本:mib-i 和 mib-。由于在任何配置中都只能有一個 mib 存在，因此兩個版本的 mib 提供相同的對象標識符?，F(xiàn)在使用的大多是 mib-。 mgmt(2)子樹的 mib(2)子樹下定義了目前使用最廣泛的各種對象，一般稱 它們“組” 。在它下面定義的組分別為: system 組:提供被管理設備的總體信息。 interfa

45、ces 組:提供網(wǎng)絡實體的物理層接口的信息，包括配置信息 和每個接口上發(fā)生的事件的統(tǒng)計信息。 ip 組:提供了一個網(wǎng)絡節(jié)點中有關 ip 實現(xiàn)和操作的信息。在網(wǎng)絡管 理系統(tǒng)中使用非常廣泛。 at 組:設備的地址轉換信息，在 mib-下，該組內容在 ip 組中。 icmp 組:包括了有關 icmp 的實現(xiàn)和操作的信息。保存了對各種類型 的 icmp 信息的接受和發(fā)送的統(tǒng)計結果。 tcp 組:主要用于對流量控制、丟失重傳和網(wǎng)絡擁擠等問題的解決。 udp 組:提供有關 udp 發(fā)送和接收的數(shù)據(jù)包信息。 egp 組:由有關實體的 egp 信息和一個記錄每個 egp 鄰居信息的表組 成。 snmp 組:包

46、括有關 snmp 實現(xiàn)和操作的信息。 (3)experimental(3)子樹 該子樹下包含了在 internet 試驗中使用的對象。 (4)private(4)子樹 該子樹用來指定用戶擴展定義的對象。網(wǎng)絡管理系統(tǒng)訪問最多的部分是該 子樹下的 enterprises(l)節(jié)點。該節(jié)點下的每個子樹分配給一個企業(yè)，而企業(yè) 必須先向認 b 登記注冊它們自己的廠商代碼，然后就可以在該代碼下創(chuàng)建它們 自己的對象。 2)從代理獲得 mib 變量的實現(xiàn) 為了對 mib 對象有更深的了解，這里對 mib 變量獲取的過程進行簡單介紹。 代理作為服務器方，后臺運行著一個等待進程，這個進程不斷等待來自網(wǎng) 絡管理者的

47、服務請求，當收到來自代理的請求時，經(jīng)過語法分析、消息認證等 過程后，從自己的 mib 庫中得到管理者所請求的 mib 變量的值，最后取出相應 的應答。從代理獲取 mib 變量要經(jīng)過如下幾步: (l)建立管理者和代理之間的連接 首先，作為客戶方的管理者要主動和服務方的網(wǎng)絡代理建立通信機制，因 為 snmp 是基于無連接的用戶數(shù)據(jù)報協(xié)議(udp)，所以這里使用無連接的數(shù)據(jù)報 層。首先構造 socket，然后使用 bind 系統(tǒng)調用進行地址綁定是用來給已建立 的 socket 分配任一地址和端口號。把 internet 地址設為 inaddr-any，系統(tǒng)將 會在可選擇的本機地址中選擇一個可用的地址

48、進行綁定。綁定后，就可以利用 此套接口進行通信了。 (2)構造協(xié)議數(shù)據(jù)單元(pdu) snmp 消息是通過 snmppdu 來傳送的，所以在發(fā)送 snmp 消息之前必須構造 協(xié)議數(shù)據(jù)單元(pdu)。根據(jù)用戶的輸入信息，構造一個 pdu 數(shù)據(jù)結構，構造一個 可以用來傳送信息的 pdu，將所請求的對象放入變量綁定列表，并將變量綁定 加入到 pdu 中。 (3)協(xié)議數(shù)據(jù)單元構造好后，發(fā)送請求。send to 系統(tǒng)調用將獲取目的地址 并發(fā)送報文。 (4)接受代理的響應。 (5)讀取數(shù)據(jù)。 snmpsnmp apiapi 基于 snmp 的網(wǎng)絡拓撲發(fā)現(xiàn)的基礎就是利用 snm

49、p 協(xié)議向網(wǎng)絡設備發(fā)送 snmp get 請求，因此實現(xiàn) snmp 協(xié)議就成為整個系統(tǒng)實現(xiàn)的關鍵一步。我們可以利用 許多公司提供的 snmp 的開發(fā)工具包 (snmp api)來開發(fā)網(wǎng)絡拓撲發(fā)現(xiàn)的相應程)子。 目前比較流行的 snmp 的開發(fā)工具包就是 cmu 大學的 ucd-snmp18，hp 公 司的 snmp+19，advent 公司的 jsnmp20和 microsoft 公司的 winsnmp，它 們各有優(yōu)缺點。這里筆者就不一一介紹了。 第三章第三章 網(wǎng)絡拓撲發(fā)現(xiàn)算法的研究網(wǎng)絡拓撲發(fā)現(xiàn)算法的研究 這里筆者將討論和分析幾種主要拓撲發(fā)現(xiàn)的算法，它們將上一章中介紹的 幾種網(wǎng)絡拓撲基本技術組

50、合在了一起。筆者覺得通過對這些算法的介紹，能夠 擴充讀者的思路，以便比較各個網(wǎng)絡拓撲發(fā)現(xiàn)的算法的優(yōu)缺點。 3.13.1 基本算法基本算法 本論文討論的拓撲發(fā)現(xiàn)算法是在下述算法的基礎上擴展完成的，該算法的 描述如下： 1、確定一個 ip 地址的“臨時”集合，這些 ip 地址對應著存在或不存在的 主機和路由器。 2、對集合里的每一個元素，作如下處理: a、驗證這個 ip 地址是否可達; b、如果可達，將此地址不重復的加入到“永久”集合中; c、一用這個地址產(chǎn)生更多的 ip 地址，并把這些新產(chǎn)生的地址加入到臨時 集合中。 對基本算法的一些說明: 1、算法中存在兩個集合，分別為臨時集合和永久集合。臨時

51、集合中存放著 等待被訪問的 ip 地址，這些地址也許并不存在。永久集合中存放著實際存在并 可達的 ip 地址。在下面具體算法的初始狀態(tài)下，臨時集合被設置成不同的初始 值(詳見具體算法)，而永久集合通常為空集。 2、拓撲發(fā)現(xiàn)算法的一個重要思想是通過某個己知的 ip 地址來獲取更多的 ip 地址，以此不斷的擴大拓撲發(fā)現(xiàn)的地址范圍。在具體的各種算法中，利用臨 時集合中的某個可達地址產(chǎn)生更多 ip 地址的方法各不相同，下面兒個小節(jié)將詳 細介紹這些方法，這里只是做一個籠統(tǒng)的概括。 3、當算法完成以后，拓撲發(fā)現(xiàn)的結果由路由器連接關系、路由器和子網(wǎng)連 接關系、子網(wǎng)、主機四個隊列表示出來。隊列中的每一項都含有

52、一些附加的信 息，如:主機名稱、路由器的接口、數(shù)量和類型等等。這些信息被存儲在文件或 數(shù)據(jù)庫中。接下來將討論在這個算法基礎上產(chǎn)生的一系列具體算法。 3.23.2 基于基于 arparp 和和 snmpsnmp 的拓撲發(fā)現(xiàn)算法的拓撲發(fā)現(xiàn)算法 這是一個最簡單的算法，它假設域中所有主機都運行 snmp。這種算法首先 獲得起始主機的缺省路由器，然后通過發(fā)出 snmp 請求報文來訪問該路由器的路 由表和 arp(地址解析協(xié)議)表，分別得到與之相鄰的路由器和主機，接著算法 循環(huán)遍歷所有的路由器和主機直到遇到一個指定域之外的主機為止9。具體算 法描述如下: 1、初始化臨時集合和永久集合，臨時集合=起始路由器

53、，永久集合為空 集; 2、對臨時集合里的每一個路由器，作如下處理: a、ping 該路由器; b、如果路由器處于活動狀態(tài)，將它加入到永久集合中; c、用 snmp 方法獲取路由器的 arp 地址表，并把地址表中的主機加入土機 隊列: d、將主機列表加入到永久集合中; e、用 snmp 方法獲取路由器的路由表，并把路由表中的路由器加入路由器 隊列; f、將路由器列表加入到永久集合中; g、將路由器列表加入到臨時集合中。 這種算法的優(yōu)點是它的速度非?？?，其缺點是它無法檢測到?jīng)]有運行 snmp 的主機或路由器，因此它能發(fā)現(xiàn)到的主機和路由器數(shù)目與實際情況可能相差較 大。根據(jù)4的測試，在 comell.

54、edu 域中，這種算法只能發(fā)現(xiàn) 10%的路由器和 92%的主機。 3.33.3 使用使用 dnsdns 區(qū)域傳輸和廣播區(qū)域傳輸和廣播 pingping 的拓撲發(fā)現(xiàn)算法的拓撲發(fā)現(xiàn)算法 這種算法假定域能夠執(zhí)行 dns 區(qū)域傳輸和廣播 ping。它首先通過發(fā)送 dns 區(qū)域傳輸報文得到域中所有主機和路由器的列表，然后使用 ping 來確定這些主 機是否可達，并通過子網(wǎng)猜測算法來確定每個子網(wǎng)的網(wǎng)絡標識，最后為了得到 在 dns 區(qū)域傳輸中沒有發(fā)現(xiàn)的節(jié)點，算法直接向通過上一步所發(fā)現(xiàn)的子網(wǎng)發(fā)送 廣播 ping，并將發(fā)回響應的節(jié)點添加入主機列表4。具體算法描述如下: 1、初始化臨時集合和永久集合，臨時集合=

55、通過 dns 傳輸，報文得的域主 機和路由器，永久集合為空集; 2、臨時集合里的每一個節(jié)點，作如下處理: a、ping 該節(jié)點; b、如果節(jié)點活著，將它加入到永久集合中，否則讀取下一個節(jié)點; c、通過子網(wǎng)猜測算法來確定該節(jié)點所在子網(wǎng)的網(wǎng)絡標識; d、將子網(wǎng)加入到永久集合中; e、如果該子網(wǎng)沒有訪問過，在它內部發(fā)送廣播 ping 報文; f、對做出回應的主機作如下處理: 將該主機加入子網(wǎng)隊列中; 將該主機加 入臨時集合 這種算法的基礎是子網(wǎng)猜測。子網(wǎng)猜測的目的是確定某一個 ip 地址所在子 網(wǎng)的網(wǎng)絡標識，也就是子網(wǎng)掩碼。本節(jié)所描述的算法中運用的子網(wǎng)猜測使用了 廣播 ping 這個工具。該算法的思

56、想是:首先將某一 ip 地址對應得子網(wǎng)掩碼長度 設置為最大值 31:然后根據(jù)這個 ip 地址和假設的子網(wǎng)掩碼構造0和255 的定向廣播地址，并發(fā)送 ping 報文;如果有兩個以上的的主機對 ping 做出了回 應，那么說明前面設置的子網(wǎng)掩碼是正確的，否則，將子網(wǎng)掩碼的長度減 1， 繼續(xù)重復上面的步驟，直到找到匹配的掩碼為止。該子網(wǎng)猜測算法可以用于支 持廣播 ping 的域，它比較精確，但速度慢，并對每一個 ip 地址都需要很大的 開銷。 因此使用 dns 區(qū)域傳輸和廣播 ping 的拓撲發(fā)現(xiàn)算法無論從速度還是完整性 方面都有著較大的欠缺，首先因為它使用了廣播 ping 進行網(wǎng)絡發(fā)現(xiàn)，所以它的

57、速度相當慢; 其次，由于安全性等原因，在許多網(wǎng)絡中是禁止使用 dns 區(qū)域傳 輸和廣播 ping 的，在這種情況下將不能得到網(wǎng)絡的完整拓撲4。 3.43.4 使用使用 dnsdns 區(qū)域傳輸和區(qū)域傳輸和 traceroutetraceroute 的拓撲發(fā)現(xiàn)算法的拓撲發(fā)現(xiàn)算法 這種算法同樣假定域能夠執(zhí)行 dns 區(qū)域傳輸。它首先通過發(fā)送 dns 區(qū)域傳 輸請求報文得到域中所有主機和路由器的列表，然后使用 ping 確定每一個主機 是否可達，接著在探測點和正在測試的節(jié)點之間發(fā)送 traceroute 報文，以得到 路徑中的所有路由器信息。通過這種方式我們可以找出距離我們主機最近的路 由器，這樣我們

58、就可以歸類出所有具有相同缺省路由器的主機的 ip 地址，并且 據(jù)此猜測出子網(wǎng)地址7。 本節(jié)所運用的子網(wǎng)猜測方法是在對一組已知的 ip 地址進行“與”和“或” 位運算，從而對這組 ip 地址所在的子網(wǎng)的網(wǎng)絡標識進行猜測。假設三個主機， ip 地址分別是 al、a2 和 a3，它們都與某一個路由器的同一個接口直接相連， 該接口的 ip 地址是 a。要找到主機所在的子網(wǎng)以及相應的子網(wǎng)掩碼，基本的思 想是首先將 ai、a2、a3 和 a 按位相與，根據(jù)同一子網(wǎng)內的 ip 地址具有相同的 網(wǎng)絡前綴這個原則，可以大致得到這四個 ip 地址所處子網(wǎng)的網(wǎng)絡標識。然后再 將它們按位進行或操作，或操作得出的結果表

59、示子網(wǎng)地址空間至少應該覆蓋幾 位(結果是“1”的位)。將“與”和“或”運算的結果結合起來，可以作出更精 確的判斷。當然，四個 ip 地址不一定能完全的判斷出網(wǎng)絡地址和子網(wǎng)掩碼，但 有一點是肯定的，知道越多數(shù)量的與路有器同一接口直接相連的主機 ip 地址， 網(wǎng)絡地址和子網(wǎng)掩碼的猜測就越精確。為實現(xiàn)以上算法，需要定義兩個 hash 表 cumulativeands和 cumulativeors，其中一個保存路由器各接口 ip 地址 和它的所有主機 ip 地址進行“與”運算的結果，另一個則保存它們進行“或” 操作的結果。當然，在進行子網(wǎng)猜測之前首先要確定主機與路由器哪個接口直 接相連4。 具體的拓撲

60、發(fā)現(xiàn)算法如下: 1、初始化臨時集合和永久集合，臨時集合=通過 dns 傳輸，報文得的域主 機和路由器，永久集合為空集； 2、初始化 cumulativeands和 cumulativeors為空； 3、對臨時集合里每一個節(jié)點，作如下處理： a、ping 該節(jié)點； b、如果節(jié)點活著，將它加入到永久集合中，否則讀取下一個節(jié)點； c、traceroute 該節(jié)點； d、從 traceroute 結果中獲得該節(jié)點直接相連的路由器（traceroute 的最 后一跳路由器就是與該節(jié)點直接相連的路由器） ； e、用 dns lookup 查找；找到此路路由器的所有 ip 地址； f、將此路由器的每一個 i