摘要：網(wǎng)絡(luò)拓撲發(fā)現(xiàn)是網(wǎng)絡(luò)工程的一個重要的研究子分支，是實現(xiàn)網(wǎng)絡(luò)管理的基礎(chǔ)性環(huán)節(jié)。同時，網(wǎng)絡(luò)拓撲發(fā)現(xiàn)是對宏觀網(wǎng)絡(luò)進行科學(xué)布局的基礎(chǔ)，也是進行網(wǎng)絡(luò)建設(shè)、網(wǎng)絡(luò)信息、網(wǎng)絡(luò)協(xié)議設(shè)計與評價以及相關(guān)網(wǎng)絡(luò)算法改進的重要依據(jù)。在介紹網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的概念的基礎(chǔ)上，重點分析了基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)原理，探討了其發(fā)現(xiàn)效率優(yōu)化措施。

關(guān)鍵詞：拓撲發(fā)現(xiàn) Traceroute 優(yōu)化措施

中圖分類號：TP393.08 文獻標志碼：Ａ文章編號：１６７３－２９１Ｘ（２０11）26－０287－02

一、網(wǎng)絡(luò)拓撲發(fā)現(xiàn)

網(wǎng)絡(luò)拓撲是指網(wǎng)絡(luò)元素及其之間的連接關(guān)系。這里所講的網(wǎng)絡(luò)元素，既可以是路由器，也可以是交換機、網(wǎng)橋等，還可以是客戶端、服務(wù)器，甚至是子網(wǎng)、AS等。這里所講的網(wǎng)絡(luò)，既可是抑制局域網(wǎng)，也可以是互聯(lián)網(wǎng)，也可以是互聯(lián)網(wǎng)的一部分。而網(wǎng)絡(luò)拓撲發(fā)現(xiàn)，就是發(fā)現(xiàn)并確定網(wǎng)絡(luò)元素及其之間的連接關(guān)系。

按照發(fā)現(xiàn)方法對網(wǎng)絡(luò)拓撲發(fā)現(xiàn)進行分類，可分為主動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)和被動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)。所謂主動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)，是指將一組精心設(shè)計的數(shù)據(jù)注入被探測的網(wǎng)絡(luò)，通過對網(wǎng)絡(luò)反饋信息進行分析，得到網(wǎng)絡(luò)的拓撲連接情況。例如，各種基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法，就是典型的主動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)?；赟NMP的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)，從原理上也應(yīng)歸類為主動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法。由于主動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)可以根據(jù)探測需要，由探測發(fā)起者對探測數(shù)據(jù)進行專門設(shè)計，因此適用情形較廣，可以探測網(wǎng)絡(luò)范圍可以很大，并且可通過提高注入數(shù)據(jù)包的科學(xué)性和合理性，不斷提高網(wǎng)絡(luò)拓撲探測的準確度。主動式網(wǎng)絡(luò)拓撲探測的缺點主要是探測數(shù)據(jù)包將增大網(wǎng)絡(luò)的負荷。在大規(guī)模多點探測中，診治有可能導(dǎo)致網(wǎng)絡(luò)性能的嚴重降低。在極端的情況下，由于注入數(shù)據(jù)報嚴重改變了網(wǎng)絡(luò)負荷，甚至探測到的網(wǎng)絡(luò)拓撲與實際情況不相符。

而被動式網(wǎng)絡(luò)拓撲發(fā)現(xiàn)，則是指對網(wǎng)絡(luò)元素間的數(shù)據(jù)進行偵聽，通過對偵聽得到的數(shù)據(jù)進行分析，進而得出網(wǎng)絡(luò)的拓撲連接情況。例如，通過偵聽路由器間的OSPF交換數(shù)據(jù)包來探測網(wǎng)絡(luò)拓撲的方法，就是一種被動式的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法。被動式的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法不向網(wǎng)絡(luò)注入數(shù)據(jù)包，因此對網(wǎng)絡(luò)負荷的影響較小。但由于被偵聽的只是局部網(wǎng)絡(luò)，因此往往通過分析也只能得到局部網(wǎng)絡(luò)的拓撲情況。另外，偵聽得到的數(shù)據(jù)可能存在很多不真實的數(shù)據(jù)，如不能對數(shù)據(jù)進行有效的分析處理，則有可能得到不真實的網(wǎng)絡(luò)拓撲圖。

二、 Traceroute的網(wǎng)絡(luò)拓撲發(fā)展

基本的Traceroute程序和經(jīng)過改進的Traceroute方法有多種，但其基本的原理都是一樣的。如圖1是一個簡單的網(wǎng)絡(luò)，節(jié)點A為探測遠點，目標節(jié)點D，F(xiàn)是已知的（或僅僅是地址已知的），而中間各節(jié)點及其連接關(guān)系都是未知的。為了得到網(wǎng)絡(luò)拓撲，從探測遠點A分別向目標節(jié)點D，E發(fā)送經(jīng)過設(shè)計的探測數(shù)據(jù)報，并同時記錄數(shù)據(jù)在傳送過程中各種間節(jié)點B，C，E的回饋信息。通過分析這些回饋信息，就可以得到網(wǎng)絡(luò)的拓撲結(jié)構(gòu)。雖然基本原理都相同，但不同的基于Traceroute的拓撲發(fā)現(xiàn)方法，其具體實現(xiàn)辦法也有所不同。

基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的主要優(yōu)點：一是可以不受網(wǎng)絡(luò)管轄范圍的限制。很多的Traceroute方法不依賴于路由器的某一特定功能，而是靠采集網(wǎng)絡(luò)中可以正常傳輸?shù)男畔矸治鐾負浣Y(jié)構(gòu)，因此可以對跨域的網(wǎng)絡(luò)拓撲結(jié)構(gòu)進行探測分析。二是主動性強，因此，探測發(fā)起人完全可以根據(jù)自身的需要和被探測網(wǎng)絡(luò)的實際情況，合理選擇適當?shù)幕赥raceroute的拓撲發(fā)現(xiàn)方法，甚至重新設(shè)計一種新的方法，使探測者具有很大的主動性。

基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)也有其固有的缺點，這主要有：第一，因為基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)從其本質(zhì)上屬于一種主動式的網(wǎng)絡(luò)測量方法，并且方法的基本原理限制了此方法，要向網(wǎng)絡(luò)注入大量的數(shù)據(jù)報。這一方面會造成網(wǎng)絡(luò)負荷的增加，可能對網(wǎng)絡(luò)的正常通信產(chǎn)生影響；另一方面，甚至由于網(wǎng)絡(luò)負荷的改變產(chǎn)生一種“由于進行測量而產(chǎn)生的測量誤差”，造成拓撲發(fā)現(xiàn)結(jié)果的失真。第二，從目前的研究現(xiàn)狀來看，基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法對網(wǎng)絡(luò)層拓撲發(fā)現(xiàn)有比較好的效果，但對鏈路層發(fā)現(xiàn)沒有很好的辦法。這主要是因為鏈路層設(shè)備對于路由器來講是透明的，因此靠路由追蹤發(fā)現(xiàn)鏈路層設(shè)備及其連接關(guān)系的難度很高。第三，基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)的效率一般比較低。進行一次拓撲發(fā)現(xiàn)操作，一般情況下只能發(fā)現(xiàn)很少數(shù)量的網(wǎng)絡(luò)設(shè)備，有時甚至只能發(fā)現(xiàn)一個網(wǎng)絡(luò)設(shè)備或連接。因此，此方法一般需要很高的設(shè)備資源占用和時間開銷。雖然存在明顯的缺點，但由于基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法不依賴于路由器的特定功能這一顯著優(yōu)點，使得該方法在跨域的網(wǎng)絡(luò)拓撲探測中還是得到了廣泛的應(yīng)用。特別是隨著網(wǎng)絡(luò)安全環(huán)境變得越來越惡劣，迫使大部分的路由器都關(guān)閉了SNMP，基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)方法受到越來越廣泛的重視，已經(jīng)成為面向大規(guī)?；ヂ?lián)網(wǎng)絡(luò)探測的主要方法。

三、拓撲發(fā)現(xiàn)優(yōu)化策略分析

（一）改進探測報文發(fā)送策略

在基于Traceroute的網(wǎng)絡(luò)拓撲發(fā)現(xiàn)中，可以采取各種不同的策略發(fā)送探測報文，不同發(fā)送策略的發(fā)送效率也有很大不同。

1．“packet to packet”：探測源發(fā)送一個探測報文，直到收到一個反饋報文或者等待時間超時，再發(fā)送下一個探測報文。這是一種傳統(tǒng)的探測報文發(fā)送策略，因此探測效率很低。特別是當某一跳沒有反饋時，由于必須等待超時，更加降低了探測效率。對于packet by packet發(fā)送策略的改進，重點在于合理設(shè)置超時等待時間。

2．“hop by hop”：設(shè)對每一跳的探測次數(shù)為k，探測源按照事先預(yù)設(shè)地一個延時值（通常k為50ms），依次向某一跳發(fā)送完畢全部的k個探測報文后，等待收到反饋或超時后，再轉(zhuǎn)向?qū)ο乱惶奶綔y?！癶op by hop”策略在效率上要優(yōu)于“packet to packet”策略。

3．“Concurrent”：探測源向依次向所有的探測跳數(shù)發(fā)送完畢全部的探測報文，相鄰探測報文之間的時間間隔是一個預(yù)設(shè)值（通常也為50ms）。由于不等待反饋，因此“Concurrent”策略的效率比上述兩種策略都高。然而，為了實現(xiàn)“Concurrent”策略，探測源必須預(yù)知到目標節(jié)點的TTL值。一種可能的方法是，喜愛那個目標節(jié)點發(fā)送Fing探測報文，然后通過解析反饋報文獲取到目標節(jié)點的TTL值。另一種可能的方法是，以一個很大的TTL值向目標發(fā)送Traceroute探測報文，根據(jù)目標節(jié)點的ICMP反饋報文，估算到目標節(jié)點的TTL。

（二）主機可達性篩選和探測停止規(guī)則的合理設(shè)置

當探測報文發(fā)送策略選定以后，影響探測效率的主要因素便是路由器反饋ICMP報文的時間或者是等待超時的時間。在traceroute.org上所公布的探測源中，通過選定20個探測源向50個隨機的目的節(jié)點進行探測試驗發(fā)現(xiàn)在開始幾跳時RTT值很小，隨著跳數(shù)的增加，RTT值逐漸增大。探測的RTT值一般都在數(shù)毫秒到400毫秒之間，實驗發(fā)現(xiàn)的最大RTT值為504毫秒。而傳統(tǒng)Traceroute的超時等待時間默認為3毫秒?？梢姵瑫r等待時間要大大高于正常的報文反饋往返時間。由于傳統(tǒng)的Traceroute在目標主機不可達時，會議是否達到設(shè)定的最大TTL值（默認為30）作為探測停止的條件，因此會浪費大量時間在等待超時上。顯而易見，在探測進行之前，先對目標節(jié)點進行可達性探測是有意義的。

收稿日期：2011-07-18

作者簡介：叢靖坤（1989-），男，黑龍江綏化人，學(xué)生，從事軟件工程研究。

參考文獻：

[1] 楊國正.計算機網(wǎng)絡(luò)拓撲發(fā)展技術(shù)研究[J].家損及工程與設(shè)計，2006，（5）.

[2] 張巍，沈富可.網(wǎng)絡(luò)拓撲判斷的研究[J].電腦知識與技術(shù)，2007，（7）.

[3] 樂潔. Traceroute及其在網(wǎng)絡(luò)拓撲發(fā)現(xiàn)中的應(yīng)用[J].微計算機信息，2005，（8）.

The network topology discovery of Traceroute and its efficiency optimizing measure

CONG Jing-qun

(Computer science and technology school，Suihua college，Suihua 152061，China)

Abstract: It is an important research sub- branch of the network engineering that the network 拓 rush toward to discover， is a foundation link that carries out the network management.At the same time， it is the foundation to the macroscopic network carries on science layout that the network topology toward to discover， is also an importance that carries on the network construction， network information， the network agreement design and evaluations and the related network calculate way improvements according to. In introducing the foundation of the concept that the network 拓 rushes toward to discover， the point analyzes to rush toward to discover the principle according to the Traceroute network topology， inquirying into it discovers that the efficiency is excellent to turn the measure.

Key words: topology discovery ; Traceroute; optimizing measure

[責(zé)任編輯王 莉]