中國Ｉｎｔｅｒｎｅｔ路由級跳數測量與分析
2008-12-31 00:00:00馬建國席明賢林益民李幼平
計算機應用研究 2008年7期
摘 要：采用分布式主動測量技術在七個測量源點對抽樣的6 476活動主機同時展開測量。測量共返回32 893條有效測量數據，數據分析之后得出中國Internet路由級跳數分布圖；計算出未加權平均跳數是14.938 89和加權平均跳數值為15.613 73。
關鍵詞：跳數測量； 網絡測量； 因特網特征
中圖分類號：TP393.03 文獻標志碼：A
文章編號：1001-3695(2008)07-2112-03
Chinese Internet router-level hop count measurement and analysis
MA Jian-guo1， XI Ming-xian1， LIN Yi-min1， LI You-ping2
(1.School of InformationEngineering ， SouthwestUniversityofScience Technology， Mianyang Sichuan 621010， China; 2.Dept. of Information Electronic Engineering， ChinaAcademy of Engineering Physical， Beijing 100080， China ）
Abstract:Measured sampled 6 754 active hosts at 7 measure sources with technology of distributedactivemeasurementat the same time. The measurement returned 32 893 effective datas totally.After analyzing these datas，gave the Chinese Internet router-level hop count distribution and calculated the un-weighted average hop count was 14.938 89 and the weighted average hop count was 15.613 73.
Key words：hop count measurement; network measurement; Internet properties
隨著Internet規模的持續擴大和結構的日益復雜，Internet已成為一種高度異構的、開放的復雜系統，給Internet的管理和分析帶來了一系列的困難。網絡測量[1]作為了解和認知互聯網的基本手段，多年來一直是網絡研究的重點領域之一。通過網絡測量可以獲得Internet各種重要的性能參數，這些測量參數正是人們理解和分析Internet內在本質的基礎。Load Kelvin[2]曾經在一次演講中說：“當我們可以測量并且用數字表達我們談論的東西的時候，我們才算得上對此有所了解；如果我們不能測量或者是不能用數字表達所談論的東西，那么我們對此的了解就是貧乏不足的。”
跳數[3]是數據包從源端到達目的端所必須通過的路由器個數，跳數測量是網絡測量的一部分，是理解網絡行為簡單有效的途徑。目前，國外已有多個組織和大學對Internet跳數展開了研究工作，并取得一定的成果。但是我國還沒有研究機構專門針對跳數展開測量與研究。鑒于這種情況，網絡測量研究小組在李幼平院士、馬建國教授的指導下進行了此次跳數測量與研究工作。目的是了解中國Internet路由級的跳數分布情況，同時為互補結構網絡與Internet的性能對比研究提供數據資料。
1 網絡測量、跳數測量的分類
網絡測量[1]就是遵照一定的方法和技術，利用軟件和硬件工具來測量或驗證表征網絡性能指標的一系列活動的總和。網絡測量主要分為拓撲測量和性能測量兩大類；網絡測量的方法主要分為主動測量和被動測量兩種。
跳數測量屬于網絡拓撲測量的范疇，是研究和分析網絡可達性與網絡距離的主要途徑之一。跳數測量的分類主要根據測量的層次來劃分，分為數據鏈路層、路由級層、自治域層、網頁層。跳數測量的方法分為兩類：基于SNMP的方法和基于ICMP的方法。前者主要通過訪問 MIB 庫進行拓撲關系的獲取，由于權限的關系，適合于在具有管轄權的網絡范圍內進行跳數測量，CAIDA的skiter就是采用此方式進行測量的；后者主要通過traceroute原理實現，可用于Internet 上的大規模網絡測量。
2 相關研究
目前，國際上成立了許多與跳數測量有關的科研機構，對Internet跳數展開研究和測量的組織有：CAIDA(cooperative association for Internet data analysis）、NIMI（national Internet mea-surement infrastructure）等。 CAIDA利用布置在全球的多個skitter進行主動測量，得出互聯網平均跳數為13.11跳[4，5]。Bradley Huffaker等人在文獻[6]中給出他們的跳數測量結果如表1所示；在文獻[7~15]中介紹了近幾年國內外網絡測量相關的研究項目及拓撲測量的研究方法。
近年來，隨著Internet的快速發展，我國Internet用戶數量已位居世界第二，但是我國針對Internet展開測量和研究的科研機構相對較少，明顯與我國Internet的蓬勃發展速度不相符。國內的中國科學院計算所、國防科學技術大學、哈爾濱工業大學、西南交通大學等單位在基于ICMP的IP拓撲探測力面的技術比較成熟。但是除了哈爾濱工業大學計算機科學技術與工程系實現了一個大規模網絡拓撲測量之外，目前還未見有其他方面Internet的大規模網絡測量與分析的相關報道。中國科學院計算所的張國慶與英國University College London的周石分別在2003年和2005年對中國Internet的AS級的網絡拓撲結構展開測量[16，17]；哈爾濱工業大學的姜譽博士在其博士論文[18]中對Internet拓撲測量給出了一個較為全面的綜述，還討論了Internet路由級測量中的幾個要解決的問題和IXP對AS級拓撲生成的影響。 目前只有世界網絡Linkwan[19]在北京、上海設立了兩個測量服務器。到目前為止，國內還未見有科研機構對中國Internet路由級跳數進行大規模網絡測量與分析的文獻及相關報道。
3 關鍵問題
3．1 測量工具
目前對網絡跳數展開測量有多種方法，主要有基于ICMP的traceroute程序和基于分析BGP路由信息的方法。本研究小組在測量中采用了基于ICMP開發的traceroute程序。具體來說，跳數測量工具是通過類似tracert的程序，每隔一定時間進行一次。該程序主動向目標主機發送ICMP探測包，然后等待ICMP的響應包，由此來記錄經過的每個路由節點的信息，從而實現跳數測量功能。Traceroute 程序的探測距離(30 跳)作為最大探測跳數，最大的RTT為1 000 ms，同時當連續3跳出現等待超時就終止本條路徑的探測，既不影響探測效率，也不影響路徑的準確性。測量軟件中核心代碼如下：
3．2 測量源點的選擇
為了敘述方便，給出如下定義：
(k，m)-tr 跳數測量[18]。將從k個小同的源點分別向m個不同的目標采用無源路由的traceroute機制進行轉發路徑測量跳數的方法統稱為((k，m)-tr跳數測量。
在進行(k，m)-tr測量時，選擇測量源點是一個很關鍵的問題。因為我國Internet IP地址范圍巨大，直接針對整個Internet路由級主機進行跳數測量將耗費大量的人力物力及浪費網絡資源，并且存在許多不可預測的問題。因此在此次測量中只設置了7個測量源點進行跳數測量。而且巴黎大學的J. L.Guillaume和M.Latapy教授的研究結果[20]表明，合理地選擇小規模的測試源點集和目的源點集也能得到很好的測量結果；L.D.Asta[21]等人還通過大量的數學論證了這一觀點。
3．3 測量目標地址集的選擇
跳數測量目標的選取對Internet跳數測量的結果有著重要的影響，如果測量目標選擇不恰當，可直接導致測量的不完全性。例如，研究小組最開始從我國各IP段隨機抽取測量目標IP地址進行測量實驗，但是在小規模實驗之后發現，抽樣出來的大部分測量目標主機是處于非活動狀態的，主要原因是該主機不存在或該主機屏蔽測量。因此考慮從全國的網吧地址中抽樣測量目標地址集。網吧的主機基本上處于活動狀態，而且基本上不屏蔽基于ICMP的測量工具。筆者選用的2006年5月29日發布的純真 QQWry IP地址數據庫[22]，該數據庫包含10萬條左右IP地址信息，由全國各地網民維護，實時更新。抽樣的原則[18]是使測量過程具有覆蓋完全、低負載、高效和弱感知性。研究小組根據此原則編寫了一套IP地址篩選程序，從QQWry數據庫的10萬余條記錄中篩選出活動主機6 476個，抽樣后得到的測量目標集的完備性的證明在文獻[18]中有詳細的論述。
4 實驗及結果分析
筆者于2006年6月開始對中國的Internet路由級跳數情況展開測量。這次測量選擇了七個城市作為測量源點，分別是綿陽、蘭州、青島、杭州、深圳、沈陽、北京。為了提高測量效率和節約測量時間，在每個測量源點的主機上將6 476個目標主機分為12個進程同時測量，此次測量共返回32 893個有效記錄。在對測量記錄進行整理之后，得出中國Internet路由級平均跳數為14.939的結果，并且給出了中國的Internet路由級跳數樣本分布圖，如圖1所示。從圖中可以看出我國Internet路由級跳數主要分布在14～17跳之間，有17 510個樣本記錄，占樣本的53.233 2％。
為了進一步研究中國的Internet路由級跳數概率分布圖情況，在第一次測量的基礎上分時段多次對測量目標集的地址進行測量，得出中國Internet路由級跳數概率分布圖，如圖2所示。
5 修正結果
在測量過程中采用的是用一個測試源點代表一個大區域進行測試。由于不同地區的主機數量不同，其對測量結果的貢獻也不同，有必要對測量數據進行加權處理才能更有效地反映真實的Internet跳數分布情況和平均跳數。根據CNNIC(中國Internet絡信息中心)2006年1月發布的“第17次中國互聯網絡發展狀況統計報告”[23]的中國IP地址，按地域分布的情況如表2所示。
按地域分布對測量記錄進行歸類整理，分為綿陽、蘭州、青島、杭州、深圳、沈陽、北京七個測量源點區域，每個區域代表的IP地址都有一些共性。每個測量源點區域所代表的地區和IP地址比率如圖3所示。
假設要測某個區域的跳數情況，區域在某個時刻T的所有活動主機的數量是N。將區域A內所有活動主機的數量N看做集合X和集合Y，集合X作為源點集，集合Y作為目標點集。從集合X中的所有節點出發，到集合Y中的所有節點的測量組合集就是所考察的區域A的跳數樣本。權值計算過程（圖4）如下：S1+S2+S3=N；從集合X中的S1、S2、S3子集中選擇一個測量源點A到集合Y中的S1、S2、S3三個子集中的活動主機集N1、N2、N3作為一次測量。從集合X中的測量源點A出發到集合Y的(N1+N2+N3)集中的任一個主機的測量權值為P=(Pi×Pj×Si)/Nj。其中：Pi代表該區域IP地址所占的比率；Pj代表測量目標區域IP地址所占的比率；Si代表測量源點的主機個數；Nj代表測量目標的活動主機數。因此每個測量源點對應目標地址集中每個省市的測量權值就可以計算出來。例如綿陽測量點的個數為1，在有效記錄中遼寧的主機數量為217，于是就有217個測量對；每個測量對的測量權值為P=(0.116×0.04×1)/217=0.000 021 8。其中：0.116是綿陽代表的地區占大陸地區主機數量的比例；0.04是遼寧省占大陸地區主機數量的比例，依次可以得到對以綿陽為測量源點到全國其他各省市的權值。因此就可以算出綿陽區域出發測量的跳數H1=∑nk=1Pk(H1+H2+…+Hn）。其中：Pk為測量源點到全國其他各省市的權；H1 、H2 、Hn 為測量源點到目標地址集的跳數。其他六個測量源的跳數也可按照計算得到。算出的加權平均跳數H=∑6k=1Pk(H1+H2+…+H7)=15.613 73；加權方差為S2=∑ni=1Pi(Hi-H)2=9.638 959；加權標準差為S=∑ni=1Pi(Hi-H)2=3.104 667。
6 結束語
跳數測量是網絡拓撲研究的一個重要組成部分，通過此次測量對我國Internet的內在特性有了進一步的認知。隨著網絡測量的相關理論和測量技術的發展，人們對網絡的認知會越來越深入，從而不斷地推動網絡技術向前發展。
網絡測量中還有許多關鍵技術值得研究。例如，網絡性能指標量化與模型化分析的問題；對網絡未來狀況進行趨勢預測；對海量測量數據進行數據挖掘和分析；測量過程的可視化以及由測量所引起的擁塞問題等都是需要進一步研究的內容。
參考文獻：
［1］談杰，李星.網絡測量綜述[J].計算機應用研究，2006，23(2):5-7.
[2]THOMPSON W，KELVIN L.Popular lectures and addresses[M]//Bartlett’s Familiar Quotations.14th ed.
Boston:Little Brownlo，1968:723.
[3]RFC文檔[EB/OL].(1993-01)[2006-06-12].http://oss.org.cn/man/develop/rfc/RFC1393.txt.
[4]CAIDA.Skiter [EB/OL].(1999-10-08)[2007-04-19]. http://www.caida.org/tools/measurement/skitter/RSSAC/.
[5]BEGTASEVOC F，VAN M P.Measurements of the hop count in Internet[C]//Proc of Passive and Active Measurement.2001.
[6]HUFFAKER B，FOMENKOV M，PLUMMER D J，et al.Distance me-trics in the Internet[C]//Proc of IEEE International Telecommunication Symposium.2002.
[7]PAXSON V. End-to-end routing behavior in the Internet[J].IEEE/ACM Trans on Networking，1997，5(5):601-615.
[8]MAHADEVAN P，KROVKOV D，FOMENKOV M.The Internet AS level topology:three data sources and one definitive metric[J].ACM SIGCOMM Computer Communication Review， 2006，36(1):16-26.
[9]NLANR[EB/OL].[2006-06-16].http://moat.nlanr.net/.
[10]RIPE Network Coordination Center.Routing information service[EB/OL].(2005)[2006-06-16].http://www.ripe.net/.
[11]Universityof Oregon.Route views project[EB/OL].[2006-06-16].http://www.routeviews.org/.
[12]University of Michigan.Topology project[EB/OL].[2006-06-16].http://topology.eecs.umich.edu/.
[13]ISMA Workshops. Internet statistic and metrics analysis[EB/OL].(2005)[2007-01-12].http://www.caida.org/outreach/isma/9602/.
[14]LAKHINA A，BYERS J W，CROVELLA M，et al.Sampling Biases in IP topology measurements [C]//Proc of the 22nd Annual Joint Conference on Computer and Communication Societies.2003:332-341.
[15]BI Jing-ping， WU Qi， LI Zhong-cheng. Measuring the Internet using public traceroute servers[C]//Proc of the 28th Annual IEEE Confe-rence on Local Computer Networks.Washington DC:IEEE Computer Society，2003:303-304.
[16]ZHOU Shi.MONDRAGON R J.Analyzing and modelling the AS-level Internet topology[EB/OL].(2003-06-30)[2006-06-16].http://arxiv.org/abs/cs.NI/0303030.
[17]ZHOU Shi，ZHANG Guo-qiang，ZHANG Guo-qing.The Chinese Internet AS-level topology[EB/OL].(2005-11-29)[2006-12-04].http://arxiv.org/abs/cs.NI/0511101.
[18]姜譽.Internet 路由器級拓撲測量與分析技術研究[D].哈爾濱: 哈爾濱工業大學， 2005.
[19]Linkwan[EB/OL].[2006-06-16].http://www.linkwan.com/gb/broadmeter/tracemap/traceroute.htm#China.[20]GUILLAUME J L，LATAPY M.Relevance of massively distributedexplorations of the Internet:simulation results[C]//Proc of the 24th Annual IEEE Conference on Local Computer Networks.Washington DC:IEEE Computer Society，2005:1084-1094.
[21]DALL’ASTA L，HAMELIN-HAMELIN L，BARRAT A，et al.A statistical approach to the traceroute-like explorationof networks:theory and simulations[C]//Proc of the 1st International Conference on Combinatorial and Algorithmic Aspects of Networking.2004:13-14.
[22]QQWry[EB/OL].[2006-06-16].http://www.cz88.net.
[23]CNNIC.第17次中國互聯網絡發展狀況統計報告[EB/OL].(2006-07)[2007-04-16].http://www.cnnic.cn/uploadf:les/pdf/2006/7/19/103651.pdf.
注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”
