張曄 張宇

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.

引言

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

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

1局部網(wǎng)絡(luò)的拓?fù)錅y量方法

1.1局部網(wǎng)絡(luò)的測量任務(wù)集生成

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

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