基于traceroute的運營商網關的識別算法

劉家志，王 勇，周潤林，肖 達，楊 榆

(1.北京郵電大學計算機科學與技術學院，北京100876;2.國家計算機網絡應急技術處理協調中心，北京100029)

1 概述

由于用戶在正常使用網絡時可能出現各種各樣的問題，如:訪問某些網站速度非常慢或者根本連接不上。這就需要定位到導致這些問題具體的故障點，通過準確定位問題所在就可以快速地對問題進行處理。然而在每時每刻都在飛速發展變化的網絡中，隨著計算機網絡技術的發展和Internet在全世界范圍內普及計算機網絡的規模變得越來越龐大，網絡結構也越來越復雜，對網絡故障排查變得日益重要和困難。網絡拓撲中的關鍵節點應該起著最根本的作用，目前大部分有關網絡關鍵節點的識別工作都是圍繞圖論展開的。討論節點重要性的方法有許多，主要有兩種方法:(1)“核與核度”理論[1]的識別方法，此理論定義“核”為那些在系統中起到支配性作用的節點構成的集合。“核度”的計算是則是通過測評某個節點被刪除后對整個網絡連通性的影響程度定義。(2)測度指標識別方法，即設計一些測度指標區分網絡中節點的差別。已提出的測度指標主要有:節點的度、介數、特征向量、子圖中心、瓶頸點等。度數[2]的測度是利用節點的直接連接節點的數目衡量和描述節點重要程度，介數[3]則是網絡中所有節點對之間通過該節點的最短路徑的條數，介數越大，節點越重要[4]。

上述兩種方法是普遍情況對網絡上的節點進行重要性判定和識別，它們泛而不專。由于不同的網絡都具有自己的特點，所以很難將上述方法直接應用于某個特定的網絡進行識別網絡關鍵節點。文中綜合考慮和借鑒前人的研究成果，并充分結合運營商網絡結構的特點以及網關的特點提出了一個專門用于識別運營商網關ip的算法，其中包含了提取運營商信息跳變路徑中跳變點ip等對于網關概念針對性強的步驟。

眾所周知網關是進行不同網絡間通信的必須一環，不同網絡之間網關間完成信息傳遞之后再從網關把信息傳遞到分布廣泛的本網絡其他路由器上，從而實現不同網絡之間的通信。

通過Linux上的traceroute工具，在合理全面的選取源、目標地址(ip)的條件下進行測量，在測得結果數據上運用以設計好的識別算法進行一系列處理，最終得到疑似運營商網關的ip地址。以此作為網絡管理以及排查故障的重要考察節點。

2 traceroute簡介

2.1 traceroute

traceroute是Linux系統下的一個電腦網絡工具是一個探索網絡結構的有效工具，在Windows系統也有類似的工具tracert。它能夠顯示發送的數據包在ip網絡經過的所有路由器的ip地址。traceroute最簡單的基本用法是:終端中輸入”traceroute”+網址或ip。traceroute程序是利用ICMP協議設計的。第一步，traceroute發送一個生存時間為1的數據包到目的ip，第一個路由器接收到此數據包時，它將生存時間減1。這樣生存時間就變為0，這是根據ICMP協議該路由器會將此數據包舍棄，然后送回一個“ICMP超時”的消息，收到這個超時消息后，在改路由器不是匿名路由器的情況下便可以得到這路徑上的第一個ip地址，接著將生存周期加1再次發送一樣的數據包到目的ip，返回第二個ip信息......依此規律繼續進行發包、收包直到到達目標數據包送達目標ip。最后一次發送為一次成功送達，所以目標ip不會送回“ICMP超時”的消息。traceroute是通過一個叫“ICMP port unreachable”的消息判斷是否送到達目的地的，實現原理是:發送traceroute請求時選擇送達的端口號是一個一般不會用的數字，所以當此數據包到達目的地后該主機會送回一個這個“ICMP port unreachable”信息，而當traceroute收到這個消息時，就知道目標ip已到達[5]。

比如對百度的網址在Linux終端下輸入“traceroute www.renren.com”，屏幕上顯示如圖1所示。

最左邊一列為序號，中間單位為ms的3個數據是3次發送數據包測得返回時間。最后的ip為到目標地址www.renren.com經過的ip。

2.2 traceroute測量平臺概述

圖1 traceroute www.renren.com 的結果圖

測量平臺為已構建好的“互聯網寬帶速率測量平臺”，分布于全國各運營商網絡內不同網絡類型的上網計算機。

平臺的功能特點:權威、可信、準確地測量數據采集;強大的數據分析;直觀可視的數據展示。

平臺基于圖2所示的“互聯網虛擬計算環境試驗床”(以下簡稱“試驗床”)搭建。

試驗床包含虛擬資源層、資源管理層、任務層、應用層組成，虛擬資源層由分布在全國的眾多虛擬資源組成，虛擬資源可以執行任何計算任務。平臺位于試驗床的應用層內，將虛擬資源作為測量點，通過任務層向試驗床中的虛擬資源下發測量任務，并收集返回。

圖2 互聯網虛擬計算環境試驗床

2.3 測量網站的選取

位于試驗床虛擬資源層中的測量點分布31個省份和直轄市，所在網絡從屬于電信、聯通、移動、教育網、鐵通等5個運營商，以共享和動態撥號2種方式接入網絡，涵蓋 1M、2M、4M、6M、8M、10M、20M、50M等8種帶寬類型。

將中國分布于31個省份及直轄市的電信、聯通、移動、鐵通和教育網的網站ip作為訪問對象。由于任務目標網站ip全部覆蓋于各省和運營商，所以具有較強代表性和科學性。

2.4 測量方法

主要測量端對端路徑上所經過的路由器ip，由于在Linux系統下有直接可以利用的同名工具traceroute，所以可直接調用。平臺采用如下測試方法

基本原理是通過程序在Linux系統下實現通過traceroute對所有被測網站的追蹤測量。

每個網站首頁的測試過程如下

首先，將所測網站首頁地址或ip和traceroute命令拼接并執行。

然后，將所測數據逐條路徑存入xml文件中。

最后，將xml結果文件由平臺自動返回到ftp上以供下載。

所以需要做的就是將任務下發機器所在省份和運營商代號和被測網站首頁地址或ip逐條存入文本文件中，發放此兩文件至平臺即可。

3 運營商網關的識別算法設計

3.1 算法原理

根據網關的特點、運營商網絡結構的特點以及相關理論，總結并提出以下運營商網關ip需具有的特點或滿足的條件。

(1)網關的定義提到網關是不同網絡間通信必須經過的，且運營商信息變化的點才可能是網關。

(2)圖3為ISP的網絡結構，顯然ISP的路由器呈層狀分布，由于網關不大量存在，因此網關的ip應該在traceroute路徑中多次出現，并且如果一個路由器是網關，那么它就應該可以一層一層的連接到省份覆蓋非常廣的底層路由器。這樣的話在數據充分覆蓋且科學的情況下，它們幾乎都出現在骨干層或者核心層。

圖3 ISP網絡結構圖

3.2 基于traceroute的運營商網關的識別算法設計

(1)在traceroute得到的xml形式的結果數據中提取出所有路徑上的ip內容并通過網絡查詢ip的工具依次查詢每個ip所在的省份和運營商信息。

(2)在每條路徑上提取出運營商改變的兩個跳變點的ip以及相對應的運營商和省份信息。

(3)遍歷全部結果路徑，提取含有(2)中得到的ip且該ip在此路徑上是運營商跳變點的路徑。

(4)對(2)中得到的所有ip都進行下述操作，使每一個(2)中的ip都能得到一系列省份。

將ip帶入(3)中得到的所有路徑中去，得到滿足下述條件的一系列省份:該省份位于路徑頭或尾;該省份所在路徑中有ip且ip為運營商跳變點;此省份的運營商信息與ip的運營商相同。

(5)從(4)步結果中統計出屬于每個ip的不同省份的個數并排序。

(6)連接省份越多說明該ip越可能位于ISP網絡結構中的上層即骨干層或核心層，同時也滿足網關的特點的描述。

4 實驗結果與分析

實際測量成功返回的路徑條數為17360條，平均路徑長度約為10.59，其中98%以上路徑運營商信息均只跳變一次。路徑長度分布如圖4所示。

將算法具體應用在返回數據上的具體操作流程如圖5所示。

對測量返回數據實施上述具體操作步驟后得到的最終部分結果(n從大到小排列)如表1所示。

圖4 traceroute平均路徑長度分布圖

圖5 實現算法實際操作流程圖

表1 算法統計結果

通過觀察結果，發現各個相同運營商的“疑似”網關ip都比較相似，即至少前兩位相同(移動為:221.176.*.*;電信為:202.97.*.*;聯通為:聯通:219.158.*.*)。猜測是相同路由器的不同接口或者是以一個路由組的形式共同完成網關任務，實現網關功能。于是對這些ip的第3位的情況進行統計，即

統計ip第3位出現數字的范圍情況:

通過對“疑似”網關ip群體的統計發現絕大多數ip(均大于90%，其中移動為100%，電信為94%，聯通為97%)落在下列范圍:

移動:221.176.15－24.*

電信:202.97.15.* 和202.97.44－63.*

聯通:219.158.4－39.*

統計在這些范圍上的ip在總的結果路徑中出現的次數和百分比如表2所示。

表2 路由組出現頻數頻率

將這些ip作為上述算法中(2)得到的ip進行接下來的一系列操作，統計得到結果如表3所示。

表3 路由組版算法統計結果

同時也發現這3個不同運營商的省份信息都是北京市或者廣東省，都是對應運營商的骨干網所在地。

從上述統計結果中可以看出所猜測并合并的ip組具備下列特性:

ip前兩位相同，并且第三位鎖定的范圍不大且范圍內ip均屬同一省份統一運營商。

在所有的結果路徑中，ip組中的出現的百分比非常高，覆蓋絕大多數路徑。

ip組作為路徑中運營商跳變點的同時連接到所有的不同省份。

在traceroute采集數據全面且正確的情況下，關于3大運營商網關由ip組構成和實現網關作用的猜想具有一定的說服力。

中國3大運營商的疑似網關ip為

中國移動:221.176.15－24.*

中國電信:202.97.15.* 和 202.97.44－63.*

中國聯通:219.158.4－39.*

所以3大運營商很可能是以上述ip組作為網關完成互相之間通信，即使不是，這些ip組也肯定是在各自運營商網絡結構中起著重要樞紐作用的骨干路由器ip，確定其同樣可以很大程度上幫助解決快速排錯、定位等問題

5 結束語

針對網絡管理中排錯定位困難等問題，首先定位在各個運營商網絡中處于核心樞紐地位的網關路由器這個方法，從而大幅度簡化定位故障的復雜度，為此依據網關以及運營商網絡的特點設計了一個基于traceroute的運營商網關的識別算法。在實際已存在的云平臺上運用traceroute工具對實際網絡中的數據進行的測量，并對結果數據運用此算法進行一系列處理。在得到結果后意外發現，疑似網關的ip大多相近。把ip通過合理的合并后在返回結果中做了相應的數據統計并重復部分算法步驟，發現合并路由組基本滿足ISP網關ip的要求，最終得到疑似網關的ip組。從而為以后網絡管理中的定位以及排錯提供方便。

致謝:感謝北郵青年科研創新計劃(2013RC0311)對本文的資助

[1] 許進.一種研究系統的新方法——核與核度[J].系統工程與電子技術，1994，(6):1－10.

[2] Wang X .Complex networks:Topology，dynamics and synchronization[J].International Journal of Bifurcation and Chaos，2012，12(5).

[3] Freeman L C.Centrality in social networks[J].Conceptual clarification.Social Networks，1979，1:215－239.

[4] 楊汀依.復雜網絡關鍵節點識別技術研究[D].南京:南京理工大學，2011.

[5] 陳星星.基于概率包標記的IP追蹤策略研究[D].長沙:湖南大學，2006.