基于半監督聚類的局部網絡拓撲測量任務選取方法

張曄 張宇

Abstract： This paper proposes a selection scheme of measurement task based on semi-supervised clustering， aiming at improving the discovery efficiency on IP addresses in local network that connected to external network. Three main approaches are conducted. Firstly， a small part of measurement tasks is selected to perform measurements as marker samples， and calculate centroids of all the known classes. Then， clustering is implemented using the distances from unlabeled samples to centroids. At last， measurement tasks are generated from the unlabeled samples that are far from all the centroids， by iterating this way until no any new class can be found. The parameters of the semi-supervised clustering are determined by the control variable. The measurement efficiency of the tasks is analyzed via the obtained number of IP addresses in local network that connected to external network. Furthermore， the aggregation ability of overall algorithm can be evaluated using clustering external indicator.

引言

網絡拓撲測量是發現網絡結構的一種重要方式，拓撲測量中以traceroute作為最常見的技術手段。Pansiot等人[1]最早運用traceroute來發現路由器級別的網絡拓撲結構。20世紀末，南加州大學（university of southern California）開啟了SCAN項目[2]，并發現了十五萬的網絡節點。CAIDA（Center for Applied Internet Data Analysis）的Ark平臺從2007年開始一直在全球執行分布式拓撲測量。近年來，網絡測量相關研究更加深入，Reza等人于2015年總結了之前十幾年內研發的網絡測量技術，對拓撲的粒度進行了細化，分為接口級別、路由器級別、POP級別和AS級別。同時，又專題討論了每個級別的相關測量技術，再對其中的問題和限制做出了分析[3]；Holterbach等人[4]在2015年通過基于RIPE Atlas的開放測量平臺的實驗，發現多用戶并發測量會影響測量精確度的問題，提出了設計測量平臺亟需注意的各類因素；Augustin等人[5]則綜合了多方的拓撲測量數據有效分析了IXP之間的連接關系。

互聯網由大量的局部網絡（AS自治域，國家）組成，分析局部網絡如何與外部網絡進行連接是了解網絡拓撲結構的關鍵步驟。局部網絡對外連接方式受商業關系、地理位置等因素影響，無法從運營商、IXP處直接獲得大量局部網絡對外連接信息，于是從traceroute測量結果中分析拓撲數據是獲取相關信息的一種主要方式。在已有的網絡測量工作中，主要通過對局部網絡執行長時間、大規模的測量，最后從測量結果中獲取局部網絡對外連接IP地址。分析歷史測量數據發現，大量的traceroute路徑經過相同的局部網絡對外連接IP地址，于是推測此現象和traceroute的測量點、目的節點相關。本文將以此為出發點，利用traceroute中測量點和目的節點的屬性對測量任務進行半監督聚類[6-8]，旨在利用少量的已知測量數據預測traceroute的測量結果，選擇最具測量意義的測量任務以減少不必要的測量，發現大量局部網絡對外連接IP地址。最后，利用本算法選擇多個局部網絡的拓撲測量任務，研究得知只是選擇3.5%的局部網絡測量任務集就可以發現90%以上的局部網絡對外連接IP地址，并利用聚類方法的評價標準[9]對算法進行評價，結果表明算法有良好的類別聚合能力，在實際測量工作有著很好的應用前景。

1局部網絡的拓撲測量方法

1.1局部網絡的測量任務集生成

Traceroute任務由測量點和目的節點組成。為了獲取良好的局部網絡的拓撲數據，就需要尋獲數目眾多、且呈發散式分布的一系列測量點。可以利用第三方網站（如traceroute.org）和搜索引擎（用Google搜索關鍵字Looking Glass）等方法來收集全世界的Looking Glass服務器，這些服務器以Web接口的方式提供免費traceroute測量服務，目前已收集穩定的1 000個服務器可執行traceroute測量，并且還設計了高并發測量系統調用測量點接口，所有接口可并發執行測量任務。為了更好地分析測量點屬性來調度測量點，利用抓包工具獲取測量點的源IP地址，分析源IP地址即會發現這些traceroute服務器分布在56個不同的國家和地區，滿足分布廣泛的需求。

測量局部網絡時，從局部網絡外的每個接口（部分接口有多個測量點）中輪流選擇一個測量點加入測量點集；目的IP地址集需滿足在局部網絡中具有代表性且目的IP地址之間拓撲間隔較遠的要求，先利用地理定位數據庫（ip2Location）獲取局部網絡的IP地址段，按照設計的目的IP地址集規模對IP地址段進行切分，所有的IP地址段將切分成相同的規模，從每個IP地址段中隨機選擇一個活躍的IP地址（用ping測試是否連通）加入目的IP地址集。測量點集和目的IP地址集作笛卡爾乘積記為測量任務集，具體如圖1所示，因此測量任務集中的每個任務元素為一次traceroute。