網絡拓撲快速發現方法分析范文

本站小編為你精心準備了網絡拓撲快速發現方法分析參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

網絡拓撲結構研究對自治域協議安全分析、網絡提供商（ISP）優化網絡性能和網絡安全管理意義重大。網絡拓撲發現根據路由等網絡元素存儲的轉發路徑信息或網絡主動測量獲取的逐跳路徑信息，對網絡拓撲結構進行獲取和分析。網絡拓撲發現方法分為基于路由轉發表、基于簡單網絡管理協議（SNMP）和管理信息庫（MIB）信息以及基于因特網控制報文協議（ICMP）3種路徑探測分析方法?；诼酚赊D發表的方法利用邊界網關協議（BGP）和開放式最短路徑優先協議（OSPF）等路由協議，對自治域間和自治域內進行網絡拓撲發現。該方法優點是速度快以及網絡負載小，缺點是發現范圍有限，范圍僅取決于獲取路由轉發表的網絡范圍；基于SNMP和MIB信息的方法是通過SNMP訪問路由器、交換機或網橋中的MIB庫，通過MIB庫中的IP路由表、接口表及其他信息分析網絡拓撲結構。該方法優點是實現簡單、速度快且準確率高，缺點是MIB庫的訪問權限難以獲取，無法對整個互聯網進行網絡拓撲發現?；贗CMP的路徑探測分析方法一般使用回送請求和回送應答，通過存活時間（TTL）設置，對互聯網拓撲路徑進行發現，通常包含地址集構造探測、存活主機探測、路徑和時延信息探測以及拓撲結構生成與顯示4個階段。該方法優點是探測地址可靈活選擇以及不依賴路由器或交換機的訪問權限，缺點是網絡負載大且速度慢。上述3種網絡拓撲發現方法各有優缺點。由于互聯網地址規模龐大、自治域間和自治域內路由協議不同以及眾多網絡元素訪問權限獲取難度大，因此對互聯網網絡拓撲發現主要采用基于ICMP的網絡拓撲發現方法。隨著互聯網網絡拓撲結構研究的不斷深入，發現了互聯網網絡拓撲結構的各種特性，如冪率特性、魯棒且脆弱性和聚集特性［4］等，以及網絡拓撲結構的不同度量指標（節點度分布、聚集系數、介數、核數和平均路徑長度）等其他特性。利用上述網絡拓撲結構特性可優化拓撲結構發現方法，提高拓撲結構發現效率，降低正常網絡流量的擾動。鑒于ICMP的網絡拓撲發現方法存在注入網絡數據量大和時效不高等問題，將互聯網結構特性與網絡拓撲發現方法結合，提出了一種基于路徑前綴匹配和雙向探測的網絡拓撲發現方法，從而降低了注入網絡的流量負載，有效提高了網絡拓撲發現的時間效率。

1路徑探測

Traceroute是最早利用ICMP進行報文傳輸路徑探測的工具，由VanJacobson在1989年開發［5］。其原理是發送報文TTL遞增的用戶數據報協議（UDP）報文，在探測報文從源端到目的端的傳送路徑中每經過一個路由其報文TTL值自動減1，當報文TTL值為0時，路由器向源端返回報文TTL超時的報文，當到達目的端時，由于UDP端口選擇較大（＞1024）的目的端口，將返回端口不可達報文。因此設置首個探測報文TTL值為1，后續探測報文TTL值逐次加1，可根據返回的TTL超時報文和目的端返回的端口不可達報文中IP地址，獲取源端到目的端的網絡路徑信息。

Skitter是由加利福尼亞大學互聯網應用數據分析中心（CAIDA）開發的分布式網絡測量工具，在美國、英國、加拿大和法國等國家分別部署了24個測量點?；趥鬏斂刂茀f議（TCP）報文實現Traceroute，使用常用端口可確保報文到達目的端時通過防火墻的過濾規則。24個測量點共用由971080個IPv4地址構成的目標地址集，每3d完成一次對地址集的路徑及報文往返時間（RTT）的測量循環。Mercator與Skitter類似，采用分布式測量方法對大規模網絡的拓撲結構和鏈路時延進行測量。主要區別：Mercator采用啟發式地址集隨機生成機制，可自適應構造探測地址集，而不依賴于解析BGP路由表和域名解析服務（DNS）數據庫等手段。Mercator通過改進Traceroute實現2個目標：1）任意位置部署；2）無需額外輸入，僅依賴有限TTL值探測報文，但Mercator啟發式地址生成機制可能產生較大的探測流量。Rocketfuel針對ISP網絡拓撲結構進行發現和構造，采用直接探測機制和路由器接口聚合機制以提高拓撲結構發現和構造效率。直接探測機制利用BGP路由表對經過ISP的探測路徑進行篩選，減少了探測地址和路徑數量。路由器接口聚合機制可根據探測路徑中路由接口特征，識別相同路由器的不同接口并聚合為唯一的路由器地址，從而提高拓撲結構發現的準確性和效率。以上方法分別針對基于ICMP的網絡拓撲發現的不同方面，解決了分布式網絡拓撲發現、啟發式地址集構造和路由器接口聚合等問題。對于每個測量點，注入網絡數據量大和時間效率低仍是影響互聯網網絡拓撲發現的重點問題。本文根據互聯網網絡結構特點，改進了互聯網網絡拓撲發現方法，從而降低了探測數據流量并提高了時間效率。

2雙向探測

基于ICMP的網絡拓撲發現方法普遍采用TTL單向增長Traceroute方法，對測量點到目標網絡設備的網絡路徑進行測量，如圖1所示。其中，TTL－x為探測端TTL為x的探測報文；ICMP－TE為路由丟棄TTL超時報文時的響應報文；ICMP－DU為目標網絡地址的目標端口不可達響應報文。探測端向目標網絡設備發送TTL由1開始，以1為步長遞增的TCP，UDP或ICMP報文。當TTL＝i的探測報文發送后，等待接收路由器Ri的超時返回報文或目標網絡設備的端口不可達報文，并記錄路徑第i跳的路由接口地址以及報文RTT或目標網絡設備報文往返時間。若接收時間超時，則對TTL＝i路由地址重新探測。連續3次探測失敗后，則認為該路由為匿名路由，設置該路由接口地址為NULL并對TTL＝i＋1的路由地址繼續進行探測。若連續3個路由均無法探測成功，則認為該目標網絡設備無法到達，放棄該網絡設備的路徑探測。按照目前Traceroute方法對多個IP地址進行測量時，由于互聯網網絡結構的聚集特點，路徑中大量路由節點將會重復探測。圖2給出了網絡聚集結構特點，當從探測點s1到目標網絡設備d1，d2和d3進行測量時，路由器R1將會在每次測量中進行探測。由于互聯網網絡規模龐大，對整個互聯網網絡拓撲結構的發現和測量的工作量將是巨大的和重復的，故增加了探測數據流量和時間代價。針對互聯網網絡拓撲結構特點以及網絡拓撲發現方法重復探測率高的問題，提出了雙向探測的網絡拓撲結構發現方法。

3前綴匹配哈希表與TTL切割線

在雙向探測Traceroute方法TTL遞減過程中，需要每次對返回的超時報文地址進行查表，其結果決定是否繼續遞減探測。前綴匹配表的結構對網絡拓撲發現發送的探測流量和時間效率產生較大影響，應從查詢速度和表的大小2方面考慮，使用哈希表能較好地滿足以上2項要求。探測端負責維護1個哈希表組，分別以每個TTL值建立1個哈希表，第i個哈希表為從探測端出發第i跳的常見路由地址及其前i－1跳的路徑信息。隨著TTL的增加，路由器地址將以指數級增加。為了控制哈希表規模，當TTL＝i的路由地址在哈希表查詢失敗時，該地址和路徑前綴信息不插入哈希表，而插入待哈希列表。利用定期掃描待哈希列表對哈希表進行更新，從而確保命中率以及哈希表規?？煽?。根據文獻，互聯網作為小世界網絡，其節點平均距離是19個連接，因此取中間值10作為初始TTL切割線，分別建立TTL＝1～TTL＝10的10個哈希表。探測過程中不斷掃描待哈希列表對哈希表更新，對10個哈希表的命中率進行分析，將命中率最高的TTL值作為分割線，對小于分割線的TTL段和大于分割線的TTL段進行遞減和遞增探測。

4試驗驗證

網絡拓撲結構發現方法的評價標準分為完備性、時間效率、網絡負載和準確性4方面。其中，完備性指拓撲發現可能獲取的網絡覆蓋范圍是否對所有網絡設備進行發現；時間效率從網絡拓撲結構發現所需時間衡量方法優劣性；網絡負載指網絡探測過程中對網絡流量的影響大??；準確性針對網絡拓撲發現結果與真實網絡的誤差進行分析。為了對基于ICMP的雙向網絡拓撲發現方法的網絡負載、時間效率和準確性進行分析，本文對中國教育網的所有網段利用ICMPping進行掃描獲取探測地址集，共獲得活躍的主機地址10713個，針對該地址集分別使用傳統Traceroute和雙向探測Traceroute方法進行試驗對比。傳統Traceroute方法以TTL＝1遞增探測，雙向探測Traceroute方法以TTL＝10為初始值，哈希表大小設為100，目標地址集為中國教育網內活躍的主機中隨機抽取不同規模的10個地址集，其探測結果從完備性、時間效率、網絡負載和準確4方面對比。1）完備性雙向探測Traceroute方法僅針對探測過程進行改進，未涉及改進探測地址集的生成技術。因此，從完備性角度，該方法與傳統Traceroute方法相同。2）時間效率從探測地址集隨機抽取1000，2000，…，10000個地址建立不同規模的探測地址集10個，探測地址集完成探測所需時間如圖4所示。由圖4可見，雙向探測與傳統Traceroute方法相比，降低了探測時間，且在一定規模的探測地址集內，隨地址集規模的增大，降低探測時間的程度也隨之增加。3）網絡負載網絡拓撲發現探測所需流量是網絡拓撲發現的一個重要因素，探測過程應盡可能降低正常網絡業務流量的干擾。利用上述10個探測地址集，對探測過程中的發包數進行統計，如圖5所示。由圖5可見，雙向探測方法注入網絡的數據流量較傳統Traceroute方法較少，故降低了對正常網絡業務數據流量的影響。4）準確性由于難以獲取實際網絡拓撲結構，本文僅對雙向探測和傳統Traceroute方法的準確性進行對比，以獲取目標網絡地址完全路徑的比例為參考標準，在一定程度上可反映網絡拓撲發現方法的準確性。利用上述10個探測地址集，其中最后一跳能夠到達目標網絡設備IP地址的數量比例如表1所示。由表1可見，在地址集中目標網絡設備的探測結果中，獲取完全路徑的目標網絡設備約為59％。因對中國教育網全部網段ping掃描需持續約30h，而教育網中活躍主機的IP地址在一定時間范圍內會發生變化，因此不能獲得地址集中所有IP地址的網絡路徑。從準確性角度，雙向探測方法與傳統Traceroute方法差別不大，均能獲得活躍主機的網絡路徑信息。

5結束語

目前，基于ICMP的網絡拓撲發現方法是互聯網網絡拓撲結構發現的主要方法，利用ICMP對互聯網網絡結構發現的各項目和工具均存在注入網絡數據流量大和時間效率低的問題。本文使用TTL雙向探測和前綴匹配哈希表對傳統TTL單向遞增的Traceroute方法進行改進，對中國教育網中活躍主機進行了掃描和探測。試驗表明，雙向探測的網絡拓撲結構發現方法能夠減少正常網絡業務數據流量的擾動，并減少互聯網拓撲結構發現所需時間。

作者：王志釗 陸余良 楊國正 單位：合肥電子工程學院網絡系