王占豐，程光，胡超，李晗，翁年鳳，曹華平

（1. 東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 211189；2. 東南大學(xué)網(wǎng)絡(luò)空間安全學(xué)院，江蘇 南京 211189；3. 解放軍陸軍工程大學(xué)指揮控制工程學(xué)院，江蘇 南京 210007；4. 國(guó)家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100020；5. 南京電訊技術(shù)研究所, 江蘇 南京 210007）

1 引言

當(dāng)前，互聯(lián)網(wǎng)已成為人類(lèi)社會(huì)的基礎(chǔ)設(shè)施，政治、經(jīng)濟(jì)、文化、科技、教育等無(wú)不因?yàn)榛ヂ?lián)網(wǎng)的出現(xiàn)而發(fā)生深刻革命[1]。伴隨著接入技術(shù)的持續(xù)進(jìn)步和硬件成本不斷下降，網(wǎng)絡(luò)深入到人類(lèi)世界的任意角落，萬(wàn)物互聯(lián)已成為現(xiàn)實(shí)。為了更好地使用和管控網(wǎng)絡(luò)，人們迫切地希望了解網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[2-4]，網(wǎng)絡(luò)空間測(cè)繪與態(tài)勢(shì)感知成為一個(gè)炙手可熱的領(lǐng)域[5-9]，國(guó)內(nèi)外一些知名企業(yè)紛紛開(kāi)展相關(guān)研究，建立了許多態(tài)勢(shì)感知平臺(tái)和知識(shí)庫(kù)，如 Zoomeye、Censys、Shodan、FOFA等。

在網(wǎng)絡(luò)態(tài)勢(shì)分析中，只有將測(cè)量獲得的邏輯拓?fù)渑c物理拓?fù)溥M(jìn)行映射，才能將觀測(cè)到的網(wǎng)絡(luò)事件與網(wǎng)絡(luò)設(shè)備進(jìn)行關(guān)聯(lián)[10-19]，這就需要采用別名解析技術(shù)。具體來(lái)說(shuō)，別名解析技術(shù)就是從網(wǎng)絡(luò)測(cè)量結(jié)果中找出屬于同一設(shè)備的IP地址集合，該項(xiàng)技術(shù)廣泛應(yīng)用于路由器級(jí)拓?fù)浒l(fā)現(xiàn)、跟蹤溯源和態(tài)勢(shì)分析中。別名解析在 2000年左右曾受到廣泛關(guān)注，先后有Mercator、iffinder、Ally等著名的測(cè)量工具和平臺(tái)被提出，但這些測(cè)量工具和平臺(tái)存在測(cè)量開(kāi)銷(xiāo)較大和使用范圍有限的問(wèn)題[20-24]。由于IPv4地址在2016年已經(jīng)耗盡，世界各國(guó)都在加緊推進(jìn)IPv6網(wǎng)絡(luò)的建設(shè)。由于IPv4和IPv6相互不兼容，針對(duì)IPv4的別名解析技術(shù)無(wú)法完全適應(yīng)新的網(wǎng)絡(luò)架構(gòu)，從而涌現(xiàn)出一批新的研究成果。為了對(duì)別名解析技術(shù)形成較為全面的了解，通過(guò) EI、SCI、知網(wǎng)、萬(wàn)方等文獻(xiàn)檢索工具對(duì)別名解析（alias resolution）、別名、IPID、時(shí)間戳等關(guān)鍵詞的相關(guān)論文進(jìn)行了檢索。在論文檢索過(guò)程中，以相關(guān)文獻(xiàn)綜述及重要的算法入手，并將所涉及的相關(guān)文獻(xiàn)進(jìn)行了拓展閱讀，檢索內(nèi)容覆蓋了國(guó)內(nèi)外主要研究團(tuán)隊(duì)的最新成果。

別名解析方法從原理上大體分為基于測(cè)量的別名解析算法、基于推斷的別名解析算法和綜合方法3類(lèi)。基于測(cè)量的別名解析算法向不同的IP地址發(fā)送探測(cè)分組，通過(guò)分析響應(yīng)分組的內(nèi)容或特征來(lái)判定2個(gè)或多個(gè)IP是否屬于同一臺(tái)路由器?；谕茢嗟膭e名解析算法通過(guò)構(gòu)建IP拓?fù)浠騃P接口名稱(chēng)來(lái)推斷不同的IP地址是否屬于同一臺(tái)路由器?；跍y(cè)量的別名解析方法更為準(zhǔn)確，但是對(duì)于不響應(yīng)測(cè)量或者響應(yīng)不完整的網(wǎng)絡(luò)設(shè)備，基于推斷的別名解析算法也是一種補(bǔ)充。因此，綜合方法是將幾種別名解析方法組合起來(lái)從而進(jìn)行更為全面和準(zhǔn)確的判別[25]的一種方法。從技術(shù)發(fā)展過(guò)程看，別名解析方法逐漸從IPv4網(wǎng)絡(luò)發(fā)展到IPv6網(wǎng)絡(luò)，從小范圍的網(wǎng)絡(luò)擴(kuò)展到整個(gè)IP地址空間。

2 IP別名解析概述

2.1 典型的別名關(guān)系

路由器一般有多個(gè)接口，每個(gè)接口配有不同的IP地址，如果用一個(gè)接口的IP地址代表該路由器，則其他接口的IP地址稱(chēng)為別名[25]。 別名關(guān)系推斷是網(wǎng)絡(luò)測(cè)量中的一個(gè)難題，該問(wèn)題最早由Pansiot等[26]提出。如圖1(a)所示，2個(gè)測(cè)量點(diǎn)S1和S2測(cè)量到目的主機(jī) D的路徑時(shí)，得到的 IP路徑分別為S1→…→R11→R'31→R41→…→D 和 S2→…→R21→R31→R41→…→D。如果不能推斷路由器R'3和路由器R3為同一臺(tái)路由器，則會(huì)得到圖1(b)所示的拓?fù)浣Y(jié)構(gòu)。圖1中表示路由器的接口。

圖1 IP別名關(guān)系示意

文獻(xiàn)[27]將所有的IP別名關(guān)系分為3種情況。

1) 對(duì)稱(chēng)路由別名關(guān)系。從不同方向測(cè)量2條路徑，如果在網(wǎng)絡(luò)中2個(gè) IP處于對(duì)稱(chēng)位置，如圖 2中的接口IP1y和IP2y、IP1z和IP2z屬于同一臺(tái)路由器，且互為別名，這種互為別名的IP往往具有相同的30 bit網(wǎng)絡(luò)標(biāo)識(shí)。

圖2 IP路徑中存在對(duì)稱(chēng)路段的別名關(guān)系

2) 相同后繼別名關(guān)系。若測(cè)量發(fā)現(xiàn)的IP邏輯鏈路＜IPx，IPy＞和＜IPw, IPy＞具有相同的后繼節(jié)點(diǎn)，則IPx和IPw互為別名，這種情況又稱(chēng)為三角別名，如圖3所示。

3) 平行路徑別名關(guān)系。如圖 4中的 2條路徑L1=IP1x→…→IP1y→…→IP1z，L2=IP2x→…→IP2y→…→IP2z，若IP1y和IP2y屬于同一臺(tái)路由器，則這種情況稱(chēng)為平行別名。這種情況出現(xiàn)在從同一個(gè)方向進(jìn)行探測(cè)，出現(xiàn)負(fù)載均衡，或者由不同的路由器策略造成。

圖3 IP路徑中具有相同后繼的別名關(guān)系

圖4 平行路徑別名關(guān)系

2.2 別名解析基本思路

目前，別名解析算法已達(dá) 20余種，然而從別名解析過(guò)程來(lái)看，所有別名解析算法主要分為3個(gè)環(huán)節(jié)：1) 別名集合篩選，2) 數(shù)據(jù)探測(cè)與分析，3) 別名判定，如圖5所示。

圖5 別名解析算法的一般流程

別名集合篩選主要指將那些可能互為別名的IP地址集從探測(cè)目標(biāo)網(wǎng)絡(luò)中過(guò)濾出來(lái)，從而減小搜索范圍，也稱(chēng)為別名過(guò)濾技術(shù)[27-28]。這種別名過(guò)濾往往是通過(guò)分析潛在的別名關(guān)系或者 RFC文檔中關(guān)于路由器接口的分配規(guī)范來(lái)完成的，如Palmtree等算法在探測(cè)的目標(biāo)集合構(gòu)建時(shí)就考慮如何采用先驗(yàn)知識(shí)來(lái)減少測(cè)量開(kāi)銷(xiāo)。

數(shù)據(jù)探測(cè)與分析主要依據(jù)別名判定的原理進(jìn)行數(shù)據(jù)測(cè)量與分析，如基于測(cè)量的別名解析算法通過(guò)測(cè)量獲取的響應(yīng)分組的IPID[23]、路徑信息[29]、時(shí)間戳[30]等信息，而基于推斷的別名解析算法則分析網(wǎng)絡(luò)的路徑關(guān)系[31]和拓?fù)鋄32]來(lái)為別名判定做準(zhǔn)備。

別名判定則是確定2個(gè)或多個(gè)IP是否為別名，主要依據(jù)是RFC文檔或者路由器的配置規(guī)范。伴隨著人工智能技術(shù)的發(fā)展和大數(shù)據(jù)技術(shù)的流行，一些基于機(jī)器學(xué)習(xí)的算法也逐步得到了應(yīng)用，如TreeNet采用決策樹(shù)的思想來(lái)進(jìn)行別名關(guān)系的判定[25]；DisCarte算法采用析取邏輯規(guī)劃來(lái)進(jìn)行別名判定[33]，AliasCluster算法采用貝葉斯網(wǎng)絡(luò)推斷模型與鏈?zhǔn)酵评磉壿媮?lái)進(jìn)行別名判定[34]。

某些別名解析算法對(duì)上述 3個(gè)環(huán)節(jié)進(jìn)行了簡(jiǎn)化 ， 如 Mercator[20]、 iffinder[21]、 Passenger[29]、DisCarte[33]、Pamplona-traceroute[35]等算法將前 2 個(gè)環(huán)節(jié)合并為一個(gè)步驟，即從探測(cè)數(shù)據(jù)中獲取可能的別名集合。本文將別名解析算法分為IPv4別名解析和IPv6別名解析兩大類(lèi)，再分別將兩類(lèi)算法進(jìn)行細(xì)分，對(duì)典型算法的原理進(jìn)行闡述。

3 IPv4別名解析技術(shù)

3.1 基于測(cè)量的別名解析方法

3.1.1 基于同源地址的別名解析算法

基于同源地址的別名解析算法是最早的一類(lèi)別名解析方法，由 Pansiot等[26]提出，在網(wǎng)絡(luò)拓?fù)錅y(cè)量工具 Mercator[20]及別名解析工具 iffinder[21]中均采用了該方法。這種方法通過(guò)主動(dòng)探測(cè)來(lái)解析IP地址別名。根據(jù)RFC1393[36]，向一個(gè)IP地址發(fā)送一個(gè)具有較高端口號(hào)、TTL為255的分組，如果返回的“端口不可達(dá)”ICMP分組源地址與目的地址不同，則說(shuō)明該地址與被探測(cè)的目標(biāo)地址是同一臺(tái)路由器上的2個(gè)別名，如圖6所示。對(duì)于2個(gè)可能互為別名的IP地址，若響應(yīng)分組的原地址相同，也說(shuō)明這2個(gè)IP地址互為別名。

圖6 基于同源地址的別名解析算法原理示意

這種別名解析方法的優(yōu)點(diǎn)在于不會(huì)產(chǎn)生誤判，缺點(diǎn)是會(huì)受到路由器配置的影響，發(fā)現(xiàn)別名的完整性不高。在不考慮網(wǎng)絡(luò)擁塞的情況下，當(dāng)出現(xiàn)以下2種情況時(shí)，該算法無(wú)法發(fā)現(xiàn)別名[21]：1) 如果路由器被配置為“采用收到分組的目的地址作為響應(yīng)分組的源地址”，那么通過(guò)響應(yīng)分組將無(wú)法發(fā)現(xiàn)別名；2) 路由器不響應(yīng)高端口的ICMP測(cè)量，據(jù)統(tǒng)計(jì)網(wǎng)絡(luò)中約有 10%的核心路由器從來(lái)不響應(yīng)未知高端口的探測(cè)分組。

為了提高IP別名的識(shí)別率，使用該技術(shù)時(shí)可以通過(guò)以下3個(gè)方面進(jìn)行優(yōu)化[20-21]：

1) 可對(duì)同一個(gè)接口重復(fù)發(fā)送多個(gè)探測(cè)分組，因?yàn)椴煌瑫r(shí)刻的響應(yīng)分組會(huì)有所不同；

2) 改變分組的封裝方式，因?yàn)椴煌到y(tǒng)在探測(cè)時(shí)返回的結(jié)果會(huì)有所不同；

3) 從不同的地理位置發(fā)起測(cè)量，因路由策略不同，從不同位置發(fā)起的探測(cè)響應(yīng)情況會(huì)有所不同。

基于同源地址的別名解析算法雖然是為 IPv4網(wǎng)絡(luò)而設(shè)計(jì)，但是經(jīng)改進(jìn)后可以適用于 IPv6網(wǎng)絡(luò)中，適用的范圍較廣且準(zhǔn)確度高。

3.1.2基于IPID的別名解析算法

基于IPID的別名解析算法主要通過(guò)IP分組的標(biāo)識(shí)變化來(lái)進(jìn)行別名關(guān)系判別。在網(wǎng)絡(luò)中，IP分組是通過(guò)分組首部的標(biāo)識(shí)字段（簡(jiǎn)稱(chēng)IPID）來(lái)區(qū)別的，IPID可以標(biāo)識(shí)不同IP分組的多個(gè)分片從而進(jìn)行重裝。每個(gè)路由器都具有一個(gè)全局的計(jì)數(shù)器，每發(fā)送一個(gè)IP數(shù)據(jù)分組，IPID加1，全局計(jì)數(shù)器為路由器的多個(gè)網(wǎng)絡(luò)接口所共享。由于 IPID的值是單調(diào)遞增的，那么由同一臺(tái)路由器發(fā)出的連續(xù)分組應(yīng)具有連續(xù)的 IPID值，據(jù)此原理，當(dāng)對(duì)同一臺(tái)路由器的不同IP地址發(fā)送探測(cè)分組時(shí)，則返回分組的IPID值應(yīng)該是連續(xù)或者相近的。這種方法不受路由器返回分組配置策略的影響。

1) Ally算法

文獻(xiàn)[23]在網(wǎng)絡(luò)測(cè)量系統(tǒng) Rocketfuel中提出了基于IPID值進(jìn)行別名解析的工具Ally。Ally是在Mercator的基礎(chǔ)上提出的，該算法同時(shí)綜合基于相同源地址的技術(shù)，分析路由器選擇的TTL初始值及路由器對(duì)速率限制(rate limiting)情形來(lái)對(duì)別名關(guān)系進(jìn)行判別。圖7給出了Ally中使用IPID進(jìn)行別名解析的基本過(guò)程。首先，對(duì)2個(gè)候選IP地址先后發(fā)送2個(gè)探測(cè)分組，從響應(yīng)分組中獲取的IPID分別為x和y。然后，對(duì)上述2個(gè)IP再發(fā)送2個(gè)探測(cè)分組，獲得的響應(yīng)分組的IPID分別為w和z。若返回的IPID滿(mǎn)足關(guān)系x＜y＜w＜z，且w與x的值十分接近，則說(shuō)明2個(gè)IP互為別名。在實(shí)際網(wǎng)絡(luò)中，考慮分組的亂序等因素，只要x與y之差小于一定的閾值，仍可以認(rèn)為2個(gè)IP為別名關(guān)系。Ally算法受閾值的影響較大，一般閾值設(shè)置為 200，可以根據(jù)發(fā)送分組間隔長(zhǎng)短進(jìn)行調(diào)整。文獻(xiàn)[23]的實(shí)驗(yàn)證實(shí)了這種技術(shù)存在錯(cuò)判和解析不完全的問(wèn)題。同時(shí)，這種技術(shù)還有一個(gè)缺點(diǎn)，即效率比較低，需要O(n2)次的成對(duì)測(cè)試，在慢速網(wǎng)絡(luò)和不響應(yīng)的路由器較多的情況下，別名解析的耗時(shí)會(huì)很長(zhǎng)。

圖7 Ally別名判別的原理

為了提高別名解析的效率，文獻(xiàn)[23]對(duì)別名解析的范圍采用啟發(fā)式算法進(jìn)行了限定：一是采用DNS系統(tǒng)中的層次化命名，對(duì)高度相似的域名進(jìn)行別名判定，如chi-sea-oc12.chicago.isp.net與chi-sfooc48.chicago.isp.net；二是對(duì)于返回的 TTL值較為接近的IP進(jìn)行別名關(guān)系判定；三是利用別名的傳遞關(guān)系進(jìn)行判定，如若IP1與IP2互為別名，IP2與IP3互為別名，則說(shuō)明IP1與IP3互為別名。

Ally算法的不足之處在于容易受到網(wǎng)絡(luò)性能影響，從而導(dǎo)致分組亂序，其應(yīng)用范圍受到路由器是否采用共享IPID計(jì)數(shù)器的制約。

2) RadarGun算法

Bender等[37]發(fā)現(xiàn)共享一個(gè)IPID計(jì)數(shù)器的2個(gè)IP接口，在相近時(shí)間段內(nèi)其響應(yīng)分組的變化趨勢(shì)十分接近，從而提出了算法RadarGun。該算法不再對(duì)IPID值的連續(xù)性進(jìn)行比較，而是為每個(gè)IP進(jìn)行一組探測(cè)，分析不同IP響應(yīng)結(jié)果構(gòu)成的IPID時(shí)間序列變化趨勢(shì)的近似性。若變化趨勢(shì)一致，則認(rèn)為 2個(gè)IP互為別名，否則不是別名關(guān)系，如圖8所示。RadarGun具體做法如下。

① 首先，對(duì)于n個(gè)待判別的IP接口，不是針對(duì)每2個(gè)進(jìn)行測(cè)量，而是針對(duì)每個(gè)IP進(jìn)行一個(gè)序列的探測(cè)，從而得到不同的IPID序列。設(shè)存在3個(gè)IP地址IPa、IPb、Pc，RadarGun依次對(duì)3個(gè)IP進(jìn)行測(cè)量，返回的 IPID序列如下：A1,B1,C1,A2,B2,C2, …。如此，針對(duì)每個(gè)IP得到一個(gè)IPID序列，以IPa為例，表示為{ti,Ai}，其中，ti表示第i時(shí)刻，Ai表示第i時(shí)刻的IPID，0＜i＜N，N表示測(cè)量的次數(shù)。

② 為了保證算法的有效性，RadarGun會(huì)過(guò)濾一些無(wú)效的序列，如不響應(yīng)的分組超過(guò)整個(gè)序列25%的、IPID為0或常數(shù)的、IPID為非線(xiàn)性序列的[37]等序列。

③ 對(duì)任意 2個(gè)有效的序列引入采樣距離函數(shù)進(jìn)行檢驗(yàn)，具體如下。

對(duì)于任意 2 個(gè)序列{ti,Ai}、{tj,Bj}，若tA,i＜tB,j＜tA,i+1，采用線(xiàn)性插值法獲得序列{ti,Ai}在tB,j時(shí)刻的IPID估值IDA,est，然后計(jì)算IDB,j與估值的距離δB,j=|IDA,est-IDB,j|，采用同樣的方法計(jì)算δA,j，最后計(jì)算2個(gè)序列的平均距離，如式(1)所示。

④判別2個(gè)IP地址是否為別名。如果ΔA,B＜200，則2個(gè)IP互為別名；如果ΔA,B＞1 000，則不是別名關(guān)系；如果200≤ΔA,B≤1 000，則需要進(jìn)一步分析。

RadarGun雖然能夠解決分組亂序所帶來(lái)的問(wèn)題，然而該算法仍然是基于閾值的，仍會(huì)受到網(wǎng)絡(luò)性能等因素的影響。

圖8 RadarGun別名判別的原理

3) MIDAR

Ally和RadarGun雖然在一定程度上能夠提高別名的解析效率，但是要對(duì)整個(gè) IP地址空間或者大量IP地址進(jìn)行解析，則需要做進(jìn)一步優(yōu)化。Keys等[38]對(duì)Ally和RadarGun算法從2個(gè)方面進(jìn)行了改進(jìn)：①如何對(duì)目標(biāo)集進(jìn)行測(cè)量，并對(duì)所有的O(N2)個(gè)別名關(guān)系進(jìn)行判別；② 如何降低假陽(yáng)率以提高別名解析的正確性。MIDAR（monotonic ID-based alias resolution tool）通過(guò)優(yōu)化采樣間隔，引入單調(diào)邊界檢驗(yàn)函數(shù)（MBT, the monotonic bounds test），采用多種探測(cè)方法來(lái)提高響應(yīng)率，提出多個(gè)測(cè)量點(diǎn)協(xié)助測(cè)量及通過(guò)滑動(dòng)平均窗口來(lái)提高算法的擴(kuò)展性。

MIDAR的工作原理較為復(fù)雜，實(shí)際上是一個(gè)復(fù)雜的別名解析系統(tǒng)，適用于大型網(wǎng)絡(luò)測(cè)量平臺(tái)及大規(guī)模的別名解析，總體分為5個(gè)階段。

① 估計(jì)階段（estimation stage）

估算階段主要解決2個(gè)問(wèn)題：一是對(duì)不同的目標(biāo)主機(jī)選擇合適的測(cè)量方法；二是確定采樣時(shí)間間隔。測(cè)量時(shí)將所有待定的IP地址集合平均地分配到所有的測(cè)量點(diǎn)上，對(duì)每個(gè)目標(biāo)IP采用所有的方法進(jìn)行嘗試。

② 發(fā)現(xiàn)階段（discovery stage）

發(fā)現(xiàn)階段主要判斷 IP地址是否采用同一個(gè)IPID計(jì)數(shù)器。根據(jù)估計(jì)階段確定的測(cè)量速度來(lái)確定測(cè)量的滑動(dòng)窗口，并采用最佳的測(cè)量方法對(duì)所有IP發(fā)起測(cè)量，對(duì)所有交疊時(shí)間序列進(jìn)行檢測(cè)。檢測(cè)采用前文所述的MBT算法。

③ 消除階段（elimination stage）

對(duì)可能是別名關(guān)系的IP地址對(duì)重復(fù)使用MBT函數(shù)計(jì)算從而減少假陽(yáng)率。為了進(jìn)一步減少探測(cè)分組，將所有的IP構(gòu)建在一棵拓?fù)錁?shù)上，對(duì)所有劃分在同一棵子樹(shù)的IP別名對(duì)進(jìn)行探測(cè)，每棵子樹(shù)探測(cè)10次，其中，每棵子樹(shù)的間隔不超過(guò)整個(gè)樹(shù)空間距離的5%。實(shí)驗(yàn)表明這種探測(cè)僅多使用15%的流量。

④ 驗(yàn)證階段（corroboration stage）

驗(yàn)證階段采用消除階段的方法對(duì)所有的 IP進(jìn)行探測(cè)，但所驗(yàn)證的IP地址僅是消除階段不能確定別名關(guān)系的IP地址集，因此輸入集合更小。

⑤ 別名推斷階段（final alias inference）

前3個(gè)階段對(duì)IP地址對(duì)進(jìn)行了篩選，驗(yàn)證階段僅對(duì)位于同一棵子樹(shù)上的IP接口進(jìn)行別名檢驗(yàn)，而別名推斷階段將對(duì)所有別名的關(guān)系進(jìn)行分析從而進(jìn)行綜合判定。如A和B互為別名，B和C也互為別名，然而判定出A和C不是別名關(guān)系，則說(shuō)明判定中存在誤判，將這些可能存在誤判的別名從集合中移除。

4) Pamplona-traceroute

基于IPID的別名解析算法研究分為2個(gè)方面，一方面是不斷提高算法精度，另一方面是在控制預(yù)測(cè)精度的情況下，通過(guò)減少測(cè)量開(kāi)銷(xiāo)，提高算法效率。Pamplona-traceroute在上述2個(gè)方面進(jìn)行了嘗試，將測(cè)量與推斷隱含于 traceroute測(cè)量過(guò)程，基于IPID的間隔和變化規(guī)律來(lái)進(jìn)行別名關(guān)系推斷[35]，具體分為3個(gè)階段。

第一階段進(jìn)行測(cè)量，通過(guò)分析獲取響應(yīng)的IP地址、TTL、響應(yīng)分組的IPID和響應(yīng)分組的時(shí)間戳。該算法支持UDP、TCP和ICMP等3種不同類(lèi)型的探測(cè)，為了避免負(fù)載均衡的影響采用了成對(duì)的探測(cè)分組。

第二階段將所有測(cè)量數(shù)據(jù)發(fā)送到一個(gè)測(cè)量服務(wù)器，從這些數(shù)據(jù)中篩選出采用共享 IPID計(jì)數(shù)器的路由器。

第三階段進(jìn)行別名解析，將所有的分組中時(shí)間戳較為接近的IP地址對(duì)按照類(lèi)似于Ally的方式進(jìn)行分析，如IPID必須是單調(diào)增加的、IPID必須小于一定的閾值、分組的時(shí)延小于一定的閾值等。

Pamplona-traceroute算法將拓?fù)錅y(cè)量與別名解析進(jìn)行了融合，并通過(guò)對(duì) traceroute進(jìn)行了改造，從實(shí)驗(yàn)對(duì)比結(jié)果看該算法精度高于其他算法。但是該算法需要大規(guī)模的測(cè)量設(shè)施并需要節(jié)點(diǎn)間的協(xié)調(diào)，因此在實(shí)施過(guò)程中存在一定的困難。

相比基于相同源地址的別名判別算法，基于IPID的別名判別算法可以提高別名解析的完整性，同時(shí)具有較高準(zhǔn)確度，但同樣存在著漏判和誤判的不足，主要原因如下：① 算法中閾值的選擇受到網(wǎng)絡(luò)性能和設(shè)備特征的影響，此外探測(cè)分組在中間路由器重新排隊(duì)等因素都會(huì)對(duì)該閾值產(chǎn)生影響，如果閾值設(shè)置太大，解析的結(jié)果就會(huì)存在假陽(yáng)，反之，就會(huì)漏報(bào)；② 一些路由器會(huì)將路由器的計(jì)數(shù)器設(shè)置為0或者不使用計(jì)數(shù)器，這種情況下此類(lèi)算法失效；③ 有些路由器共享一個(gè)計(jì)數(shù)器但是為每個(gè)接口單獨(dú)計(jì)數(shù)，這樣互為別名的2個(gè)接口之間的IPID值就不再接近了；④ 存在與探測(cè)源跳數(shù)相同的2個(gè)不同路由器具有相近的 IPID值的情況，雖然這種情形的概率很小。

3.1.3 基于時(shí)間戳字段的別名解析算法

IP協(xié)議中包含一個(gè)預(yù)定義IP時(shí)間戳選項(xiàng)，啟用此選項(xiàng)后，若分組經(jīng)過(guò)路由器的IP包含在預(yù)定義IP地址集中，則該路由器會(huì)在分組中添加自己的時(shí)間戳。使用該選項(xiàng)時(shí)，預(yù)定義IP數(shù)不能超過(guò)4個(gè)，而且路由器會(huì)按照預(yù)先定義的次序逐一進(jìn)行標(biāo)記。據(jù)此可知，如果2個(gè)IP互為別名，所添加的時(shí)間戳應(yīng)該相同。根據(jù)上述發(fā)現(xiàn)，Sherry等[30]提出了一種基于時(shí)間戳的別名解析算法Timestamp。

Timestamp算法分為4步：首先向所有可能為別名的 IP發(fā)送分組(A|AXXX)排除那些會(huì)增加額外時(shí)間戳的分組，其中X表示一個(gè)不會(huì)出現(xiàn)在測(cè)量路徑上的IP地址；然后針對(duì)可能互為別名的2個(gè)IP地址A和B，從不同的測(cè)量點(diǎn)發(fā)送 2個(gè)探測(cè)分組(A|ABAB)和(B|BABA)，每個(gè)探測(cè)點(diǎn)測(cè)量5次；所有出現(xiàn)4次時(shí)間戳的IP地址為別名。對(duì)出現(xiàn)2次時(shí)間戳的2個(gè)IP進(jìn)行時(shí)鐘測(cè)試，要求時(shí)間戳單調(diào)非減而且90%的時(shí)間戳都是相同的，通過(guò)時(shí)鐘測(cè)試后再判定其是否為循環(huán)路徑，從而判定其是否為別名。

由于Timestamp采用了ICMP協(xié)議，而ICMP的端口不可達(dá)會(huì)引發(fā)錯(cuò)誤直接插入探測(cè)載荷中，再發(fā)回測(cè)量主機(jī)。Marchetta等[39]提出的 Pythia算法采用 UDP協(xié)議來(lái)構(gòu)建分組，同時(shí)在一個(gè)測(cè)量過(guò)程中引入多個(gè)別名IP，從而減小測(cè)量開(kāi)銷(xiāo)。Pythia算法分為2個(gè)階段：1) 預(yù)先準(zhǔn)備階段；2) 別名解析。在預(yù)先準(zhǔn)備階段采用與Timestamp相近的方式獲得支持時(shí)間戳路由器及相關(guān)IP集合，對(duì)別名集合進(jìn)行過(guò)濾。在別名解析階段，具體分為3個(gè)步驟：① 從別名集合中選擇一個(gè)IP地址A作為基準(zhǔn)，然后提取可能和該IP互為別名的IP集合β；② 從IP集合β中選擇4個(gè)IP構(gòu)成分組(A|ABCD)，然后通過(guò)返回的時(shí)間戳發(fā)現(xiàn)別名，如果B不是別名，將B從IP集合β中移除，否則加入別名集合，同時(shí)重新構(gòu)建探測(cè)分組，如(A|ACDE)；③ 重復(fù)上述過(guò)程直到對(duì)所有IP都進(jìn)行了別名解析。與其他別名解析算法相比，Pythia算法一次可以最多測(cè)試4個(gè)IP地址的別名關(guān)系，提高了別名的發(fā)現(xiàn)效率。

Pythia算法的不足是測(cè)試別名的關(guān)系數(shù)目有限，而且僅限于網(wǎng)絡(luò)的前幾跳，因此，這種算法適用于網(wǎng)絡(luò)邊緣靠近測(cè)量點(diǎn)的地方，對(duì)于距離測(cè)量點(diǎn)較遠(yuǎn)的路由器無(wú)法采用該方法進(jìn)行探測(cè)，需部署大量測(cè)量節(jié)點(diǎn)才能得到較為全面的結(jié)果。

3.1.4 基于路由記錄的別名解析算法

Sherwood等[29]提了一種基于路由記錄來(lái)推斷別名的算法Passenger，該算法在traceroute分組的報(bào)頭中加入了路由記錄（RR, record route）選項(xiàng)，路由器收到分組后會(huì)將路由器地址加入到分組頭部中并更新頭部的偏移量。實(shí)際上 traceroute發(fā)現(xiàn)的路徑與路由記錄的路徑并不重合。RR記錄的是路由器出向接口(outgoing interface)的地址，而ICMP分組記錄的是進(jìn)向接口(incoming interface)的地址，因此當(dāng)TTL=1時(shí)，RR中不會(huì)有任何記錄，而當(dāng)TTL=2時(shí)，RR中記錄的IP接口就是TTL=1時(shí)ICMP分組返回地址的別名，依次類(lèi)推即可以進(jìn)行別名推斷，具體如圖9所示。由于IP頭部長(zhǎng)度有限，RR記錄的路徑長(zhǎng)度最多不超過(guò) 9跳。在traceroute測(cè)量中引入使用分組路由記錄功能具有以下好處：1) 從某種程度上可以發(fā)現(xiàn)那些不響應(yīng)ICMP測(cè)量的路由器；2) 可以發(fā)現(xiàn)隱藏的路由器；3)發(fā)現(xiàn)多連接的路由器；4) 發(fā)現(xiàn)中間路徑中前9跳內(nèi)路徑的不穩(wěn)定性。

圖9 Passenger算法原理

Sherwood等[33]又對(duì) Passenger算法進(jìn)行了改進(jìn)，提出了DisCarte算法，在原有算法上引入了析取邏輯規(guī)劃（DLP, disjunctive logic programming）對(duì)別名推斷過(guò)程進(jìn)行形式化表示。DisCarte算法的求解過(guò)程十分復(fù)雜，大致分為2個(gè)階段：1) 數(shù)據(jù)預(yù)處理，根據(jù)不同廠商對(duì)于路由記錄協(xié)議的實(shí)現(xiàn)對(duì)數(shù)據(jù)進(jìn)行分析；2) DLP求解，也就是將所有的判別轉(zhuǎn)換為邏輯表達(dá)式，然后進(jìn)行求解。

基于路由器記錄的別名解析算法雖然引入了新的別名解析思路，但也存在一些不足：1) 采用RR選項(xiàng)的分組會(huì)引起路由器的過(guò)濾，或被入侵檢測(cè)系統(tǒng)視為入侵流量；2) 不同的路由器廠商對(duì)于RFC791[40]的實(shí)現(xiàn)規(guī)則不盡相同，需要對(duì)不同廠商的協(xié)議實(shí)現(xiàn)細(xì)節(jié)進(jìn)行分析，要考慮循環(huán)路由、防火墻、協(xié)議實(shí)現(xiàn)、隱匿節(jié)點(diǎn)、路徑長(zhǎng)度等眾多因素。此類(lèi)算法對(duì)路由器的要求較高，可以作為一種輔助的別名解析方法，用于提高解析的正確率。

3.1.5 基于IGMP的路由器別名解析方法

隨著多播技術(shù)被廣泛地應(yīng)用于視頻、音頻等領(lǐng)域，越來(lái)越多的路由器開(kāi)始支持網(wǎng)際組管理協(xié)議（IGMP, internet group management protocol）。高歌等[41]提出了一種基于IGMP的路由器別名解析方法，其工作原理是向目標(biāo)路由器發(fā)送IGMP組播分組中的Ask_Neighbors分組，目標(biāo)路由器收到探測(cè)分組后會(huì)返回給源地址一個(gè) Neighbors_Reply分組。根據(jù)協(xié)議，目標(biāo)路由器會(huì)將其接口信息、鄰居接口的信息及該路由器接口的相關(guān)屬性信息放入返回的分組中。以圖10為例，測(cè)量節(jié)點(diǎn)對(duì)目標(biāo)路由器R1發(fā)起探測(cè)，路由器R1收到探測(cè)分組后發(fā)送一個(gè)響應(yīng)分組，此分組信息包含路由器R1的接口地址和接口屬性信息，以及與其相連的鄰居路由器 R2～R4的接口地址和部分接口屬性信息。在某些情況下，分組返回的所有信息并不完整，可能是部分接口信息，因此需要對(duì)不同的端口進(jìn)行探測(cè)從而保證完信息的整性。

圖10 基于IGMP的別名解析過(guò)程實(shí)例

高歌等[41]提出的算法是在 mrinfo工具上改進(jìn)而來(lái)的，原始的mrinfo收到一個(gè)響應(yīng)分組后就停止接收，當(dāng)同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行探測(cè)時(shí)會(huì)導(dǎo)致數(shù)據(jù)丟失。為了避免上述情況的發(fā)生，改進(jìn)后 mrinfo+按照IP地址對(duì)收到分組進(jìn)行比對(duì)，如果收到來(lái)自相同源地址的分組則丟棄，否則進(jìn)行處理提取接口作為別名。在測(cè)試環(huán)境中，此算法探測(cè)的效率和準(zhǔn)確性方面要高于其他別名解析算法，但是其受到路由器是否支持IGMP協(xié)議的限制。根據(jù)文獻(xiàn)[41]對(duì)94 280個(gè)IP地址的探測(cè)結(jié)果表明，僅有9 797個(gè)目標(biāo)地址響應(yīng)探測(cè)，然而在實(shí)際網(wǎng)絡(luò)中這個(gè)響應(yīng)比例可能會(huì)更低，并且大量的路由器會(huì)對(duì)IGMP探測(cè)進(jìn)行過(guò)濾[42]。

此算法由于探測(cè)分組會(huì)被過(guò)濾而導(dǎo)致算法的可用程度大幅下降，僅可作為一種補(bǔ)充性的測(cè)量方法，無(wú)法在網(wǎng)絡(luò)中普遍使用。

3.2 基于推斷的別名解析算法

3.2.1 基于DNS域名的別名推斷算法

基于DNS域名的別名解析算法(DASAR, DNS based alias resolution)是對(duì)IP地址的域名進(jìn)行DNS反向查詢(xún)，然后通過(guò)域名的語(yǔ)義分析來(lái)推斷域名的別名關(guān)系[32]。其基本思想是，對(duì)路由器的多個(gè)接口地址做反向 DNS地址查詢(xún)，將域名劃分為不同的段，然后按照逆序進(jìn)行對(duì)比。例如，sl-bb21-lon-14-0.sprintlink.net和 sl-bb21-lon-8-0.sprintlink.net所對(duì)應(yīng)的IP地址是別名，根據(jù)“l(fā)on”可以猜測(cè)2個(gè)域名屬于同一臺(tái)倫敦的主干路由器，而“14-0”“8-0”可能對(duì)應(yīng)于路由器上的端口。

基于 DNS域名的別名推斷算法的準(zhǔn)確性依賴(lài)于域名命名方式，不同ISP可能采用不同的命名方式，因此對(duì)于不同ISP需要設(shè)計(jì)不同的推理規(guī)則，同時(shí)域名信息更新的及時(shí)性和命名的范圍都會(huì)影響算法的使用范圍。這種算法雖然簡(jiǎn)單，但是其準(zhǔn)確性和使用范圍都有限。趙洪華等[28]對(duì)中國(guó)、日本、韓國(guó)等國(guó)家的路由器分析表明，路由器端口采用域名進(jìn)行標(biāo)注的在所有路由器端口中的比例很低，因此，這種算法無(wú)法大規(guī)模使用，可作為一種補(bǔ)充性的解析方法。

3.2.2 基于拓?fù)涞膭e名推斷算法

基于拓?fù)涞膭e名推斷算法利用 IP地址的連接關(guān)系和約束對(duì) IP的別名關(guān)系進(jìn)行推斷，其基本方法如下：對(duì)可能是別名關(guān)系的 IP地址對(duì)采用 traceroute測(cè)量路徑信息，然后將這些信息構(gòu)建成一張有向圖，其中，節(jié)點(diǎn)為路由器接口的 IP地址，邊表示2個(gè)IP地址間是否存在一條鏈路，方向是從測(cè)量源到目的地址的測(cè)量方向。Spring等[32]總結(jié)出2條規(guī)則來(lái)進(jìn)行別名關(guān)系分析，具體如下。

1) 具有相同直接后繼的IP地址可能互為別名一般路由器之間的連接為點(diǎn)對(duì)點(diǎn)方式，在這種情況下具有相同直接后繼的 IP地址可能互為是別名。通過(guò)拓?fù)錅y(cè)量獲得IPA、IPB、IPC的連接關(guān)系如圖 11(a)所示，其中 IPC為 IPA和 IPB相同后繼，如果路由器之間是點(diǎn)對(duì)點(diǎn)連接，則它們之間路由器拓?fù)淙鐖D11(b)所示。

圖11 具有相同后繼的IP地址是別名

2) 在同一條traceroute路徑中出現(xiàn)的IP地址不是別名

這條規(guī)則的前提是網(wǎng)絡(luò)中不存在循環(huán)路徑，對(duì)于采用多路訪(fǎng)問(wèn)技術(shù)或交換網(wǎng)絡(luò)連接路由器的情形，這種方法就會(huì)產(chǎn)生誤判。實(shí)際上這一規(guī)則并不用于判斷別名關(guān)系，而是用于排除不可能為別名關(guān)系的IP地址對(duì)，從而減少測(cè)量和判別的IP地址對(duì)的數(shù)目，對(duì)于一個(gè)長(zhǎng)度為n的路徑，此規(guī)則就可以減少Cn2次判別計(jì)算。

基于以上原則，一些利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)來(lái)進(jìn)行別名關(guān)系推測(cè)的算法被提出，如 AAR[31]、APAR[43]、Kapar[44]等。

1) AAR別名解析算法

基于上述規(guī)定，Gunes等[31]提出了AAR (analytical alias resolution)別名解析算法，其基本思想是對(duì)任意一條網(wǎng)絡(luò)路徑從2個(gè)方向進(jìn)行測(cè)量，獲得該路徑上所有路由器兩側(cè)的IP地址，然后通過(guò)比較分析判定往返路徑中同一跳的IP是否滿(mǎn)足“/30”和“/31”的情況，對(duì)稱(chēng)路由如圖12所示。

圖12 對(duì)稱(chēng)路由示意

Gunes等[31]對(duì)南衛(wèi)理公會(huì)大學(xué)（SMU,Southern Methodist University）和耶魯大學(xué)（Yale University）之間的往返路徑采用 traceroute進(jìn)行了測(cè)量，得到的路徑如表1所示。通過(guò)檢驗(yàn)，可以發(fā)現(xiàn)從第2行到第10行中往返2個(gè)方向上的IP地址均滿(mǎn)足屬于“/30”或“/31”的同一個(gè)子網(wǎng)，如 129.119.0.249和 206.223.141.90互為別名，206.223.141.89和206.223.141.69互為別名。由此，可以得到SMU和耶魯大學(xué)（表1和圖13中簡(jiǎn)寫(xiě)為Yale）的網(wǎng)絡(luò)連接拓?fù)?，如圖13所示。

表1 trcaceroute雙向測(cè)量獲得的網(wǎng)絡(luò)路徑

圖13 SMU和耶魯大學(xué)的網(wǎng)絡(luò)連接拓?fù)?/p>

Gunes等[13]在Abilene網(wǎng)絡(luò)中對(duì)AAR別名解析算法進(jìn)行了測(cè)試，與其他算法相比，該算法在開(kāi)銷(xiāo)和完整性方面具有很大優(yōu)勢(shì)。然而，這種算法在實(shí)際應(yīng)用中存在著很大的局限性，因?yàn)槠鋽?shù)據(jù)采集必須是端到端的雙向測(cè)量。為獲得這樣的數(shù)據(jù)，必須進(jìn)行端與端之間2個(gè)方向的協(xié)作，因此在大規(guī)模網(wǎng)絡(luò)中，這種方法難以實(shí)施。

2) APAR

為了克服 AAR算法的不足，Gunes等[43]又提出一種基于分析和探測(cè)的別名解析器（APAR, analytic and probe-based alias resolver）。APAR 不僅考慮了路由器之間的點(diǎn)對(duì)點(diǎn)連接的情況，還考慮了多個(gè)連接的情況，這就意味著必須拓展子網(wǎng)的范圍。該算法共分為 2個(gè)步驟：① 從收集的路徑信息中提取可能是別名集合的數(shù)據(jù)集；② 使用別名子網(wǎng)對(duì)別名進(jìn)行解析。

在子網(wǎng)段提取階段，APAR在traceroute探測(cè)到的大量地址中推斷子網(wǎng)信息。首先，將所有的IP地址中具有相同“/22”前綴的地址劃分為一個(gè)子網(wǎng)（或子集）。然后，檢驗(yàn)這些地址是否滿(mǎn)足正確性約束、完整性及處理次序3個(gè)約束條件，其中準(zhǔn)確性約束是指若這個(gè)子網(wǎng)中的任何一個(gè)廣播地址出現(xiàn)在traceroute數(shù)據(jù)中，則該子網(wǎng)不為真；完整性約束是指在 traceroute路徑中至少發(fā)現(xiàn)一半的子網(wǎng)地址；處理次序是指首先對(duì)完整率高的先處理，對(duì)于完整率相同的則處理涉及路徑較多的子集。

在形成子集后，對(duì)子集的判定又有3個(gè)規(guī)則，分別為：無(wú)循環(huán)路徑、相同鄰居節(jié)點(diǎn)和距離測(cè)度[45]。無(wú)循環(huán)路徑是指所有可能為別名的任意2個(gè)IP不能出現(xiàn)在同一跳路徑上。相同鄰居節(jié)點(diǎn)是指2個(gè)互為別名的IP具有相同的前繼節(jié)點(diǎn)或后繼節(jié)點(diǎn)，或者這些節(jié)點(diǎn)互為別名。距離測(cè)度是指從一個(gè)測(cè)量點(diǎn)到互為別名關(guān)系的 IP測(cè)量獲得路徑長(zhǎng)度應(yīng)該相同或者接近。其中，最后一個(gè)規(guī)則是個(gè)可選條件，在可以進(jìn)行測(cè)量時(shí)使用。

3) Kapar算法

APAR具有更高的準(zhǔn)確性，同時(shí)考慮了路由器多連接的情況。Keys等[44]對(duì) APAR進(jìn)行了改進(jìn)和優(yōu)化，提出了Kapar算法，該算法避免了將所有的路徑信息存儲(chǔ)到內(nèi)存中，提高了算法性能。與APAR相反，Kapar算法在測(cè)量數(shù)據(jù)上通過(guò)一個(gè)檢測(cè)合并使用最少的信息，具體如下。

① Kapar將所有的路徑數(shù)據(jù)劃分為3跳分段數(shù)據(jù)。

② 通過(guò)分析路徑文件生成不可能存在別名關(guān)系的子網(wǎng)的列表，子網(wǎng)長(zhǎng)度在24位以上。

③ 為每個(gè)路徑分配一個(gè)ID，存儲(chǔ)所有的IP信息，根據(jù)這些信息可以分析是否存在循環(huán)路徑。

此外，Kapar還從其他幾個(gè)方面改進(jìn)了 APAR算法，具體如下。

① 可以使用其他來(lái)源的別名集合，如通過(guò)指紋解析獲得的別名集合。

② 在子網(wǎng)信息階段，采用了更加嚴(yán)格的算法來(lái)判定點(diǎn)到點(diǎn)的子網(wǎng)。

③ 在別名推測(cè)階段，對(duì)鄰接關(guān)系采用了更加嚴(yán)格的判定算法。

④ 綜合使用多個(gè)觀測(cè)點(diǎn)獲得TTL數(shù)據(jù)來(lái)降低別名解析假陽(yáng)率。

總體而言，基于推斷的別名解析算法在原理上更加復(fù)雜，這些方法大多借助網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)進(jìn)行推斷，為了獲取全面的網(wǎng)絡(luò)拓?fù)涞刂沸畔?，必須進(jìn)行分布式測(cè)量，從而導(dǎo)致算法實(shí)現(xiàn)起來(lái)較為困難。因此，此類(lèi)算法在有測(cè)量數(shù)據(jù)集或者分布式平臺(tái)的情況下才能更好地得到應(yīng)用。

3.2.3 基于機(jī)器學(xué)習(xí)的別名推斷算法

在前期研究的結(jié)果上，AliasCluster算法[34]將機(jī)器學(xué)習(xí)的方法引入到別名解析中，試圖僅采用traceroute而不增加測(cè)量開(kāi)銷(xiāo)來(lái)實(shí)現(xiàn)別名解析。該算法分為2個(gè)階段，具體如下。

階段1 通過(guò)traceroute測(cè)量收集數(shù)據(jù)，分析獲得的3個(gè)數(shù)據(jù)特征（IP子網(wǎng)、出入度、跳數(shù)等），采用貝葉斯網(wǎng)絡(luò)推斷模型推斷2個(gè)IP互為別名的概率。

階段2 考慮到一個(gè)路由器可能具有多個(gè)別名地址或者缺乏足夠推斷信息，引入鏈?zhǔn)酵评矸椒▽?個(gè)IP地址視為一個(gè)聚類(lèi)，如果2個(gè)聚類(lèi)的相似性較為接近就進(jìn)行合并，從而通過(guò)推斷發(fā)現(xiàn)新的 IP地址別名關(guān)系。

AliasCluster算法采用了機(jī)器學(xué)習(xí)的方式，精度受到參數(shù)設(shè)置影響，但是為設(shè)計(jì)新的解析算法指明了方向，特別是在缺乏足夠探測(cè)信息的網(wǎng)絡(luò)條件下。

除了AliasCluster算法外，Grailet等[25]提出TreeNet和 Sherwood等[33]提出的 DisCarte算法也引入了機(jī)器學(xué)習(xí)的思想和方法，本文分別在3.3.2節(jié)和3.1.4節(jié)進(jìn)行詳述。

綜上所述，機(jī)器學(xué)習(xí)方法的引入使別名解析過(guò)程中可以使用多種探測(cè)數(shù)據(jù)和指紋信息，采取更加復(fù)雜的邏輯推理，從而提高別名解析效率，因此如何更好地使用機(jī)器學(xué)習(xí)方法來(lái)進(jìn)行別名解析將成為新的研究方向之一。

3.3 綜合測(cè)量法

實(shí)際上隨著基于測(cè)量和基于推斷兩類(lèi)算法研究的不斷深入，為了減少測(cè)量復(fù)雜度，提高測(cè)量精度，一些綜合性的別名探測(cè)算法被提出，如Palmtree 算法[46]、TreeNet算法[25]。

3.3.1 Palmtree算法

Tozal等[46]綜合考慮路由器接口IP地址的分配方案與同源地址IP別名解析的原理，在此基礎(chǔ)上提出了Palmtree算法，該算法的基本思想如下。

1) 首先探測(cè)目標(biāo)的IP地址是否活躍。

2) 如果探測(cè)的目標(biāo)IP是活躍的，則分析探測(cè)節(jié)點(diǎn)到目標(biāo)IP的跳數(shù)。

3) 根據(jù)RFC 4632中路由器接口的分配方案，對(duì)“/31”或“/30”的子網(wǎng)中的IP地址進(jìn)行探測(cè)，然后采用同源地址的方法判斷別名關(guān)系。

該算法聲稱(chēng)可以將探測(cè)的復(fù)雜度降低到線(xiàn)性復(fù)雜度，實(shí)際上在缺乏全局先驗(yàn)知識(shí)的情況下，其探測(cè)復(fù)雜度也是較大的。因此，該算法可以適用于對(duì)特定網(wǎng)絡(luò)的別名判定。

3.3.2 TreeNet算法

Grailet等[25]提出了一種綜合各種測(cè)量方法的別名解析算法 TreeNet，該算法分為 3個(gè)步驟：首先，通過(guò)拓?fù)錅y(cè)量將所有的 IP別名劃分為小的集合，從而避免了大規(guī)模探測(cè)，劃分時(shí)所有IP節(jié)點(diǎn)的路徑跳數(shù)不能超過(guò) 1跳，拓?fù)涮綔y(cè)中采用ExploreNET算法[47]；然后，采集所有別名的指紋信息，主要包括TTL值、端口不可達(dá)分組源地址、IPID、DNS的解析結(jié)果及時(shí)間戳信息；最后，將上述采集的信息，按照指紋信息的可信度進(jìn)行分類(lèi)，依次為UDP探測(cè)的響應(yīng)、IPID序號(hào)、DNS解析結(jié)果等，從而進(jìn)行綜合的別名解析。TreeNet算法可以看做是iffinder、Kapar等算法的結(jié)合體，實(shí)驗(yàn)證明該算法可以采用較少的探測(cè)分組實(shí)現(xiàn)與MIDAR、Kapar類(lèi)似的精度。

TreeNet算法需要集合多種別名解析工具，實(shí)現(xiàn)方法較為復(fù)雜，但其精度和準(zhǔn)確度都是較高的，適用于大規(guī)模的別名解析。

4 IPv6別名解析技術(shù)

IPv6協(xié)議不僅擴(kuò)展了IPv4地址空間的范圍，而且對(duì) IP分組的分組格式等方面也做了修改[48]，如 IPv6網(wǎng)絡(luò)層不再支持大數(shù)據(jù)分組的再分組與重裝，而是由應(yīng)用層負(fù)責(zé)完成，同時(shí)IPv6增強(qiáng)了對(duì)組播和流控制的支持、自動(dòng)配置及更高的安全性和較小的路由表。由于種種原因，IPv6標(biāo)準(zhǔn)雖然已經(jīng)提出了20多年，但是仍然沒(méi)有得到廣泛的部署和使用，僅在部分骨干網(wǎng)絡(luò)和試驗(yàn)網(wǎng)絡(luò)中得到了應(yīng)用[40]。隨著IPv4地址的耗盡，IPv6的部署進(jìn)度不斷加快。據(jù)統(tǒng)計(jì)，全球IPv6的BGP（border gateway protocol）前綴通告呈現(xiàn)出指數(shù)級(jí)增長(zhǎng)，超過(guò) 6 000個(gè) AS（autonomous system）宣告了IPv6可達(dá)，約占所有AS數(shù)的15%，因此，研究IPv6的網(wǎng)絡(luò)拓?fù)浼皠e名解析正變得更加緊迫[49]。

由于IPv6網(wǎng)絡(luò)與IPv4網(wǎng)絡(luò)設(shè)計(jì)上的差異，許多可以用于 IPv4網(wǎng)絡(luò)的別名解析技術(shù)無(wú)法應(yīng)用于IPv6網(wǎng)絡(luò)。先后有一些研究者提出了基于源路由、誘發(fā)式IPID的IPv6別名解析技術(shù)和基于前綴的別名解析算法，如 Atlas[50]、RMP[51]、TBT[52]、Speedtrap[53]、UAv6[54]等算法。

4.1 基于源路由的別名解析算法

路由器在檢查分組跳數(shù)限制之前通常會(huì)先處理路由擴(kuò)展頭部。Atlas對(duì)2個(gè)可能互為別名關(guān)系的IP地址對(duì)(x,y)，將向y發(fā)送跳數(shù)限制設(shè)置為到x跳數(shù)的UDP分組。如果2個(gè)IP互為別名，則會(huì)收到“跳數(shù)超出限制”和“端口不可達(dá)”的響應(yīng)分組。文獻(xiàn)[51]發(fā)現(xiàn)在所有響應(yīng)分組中，“跳數(shù)超出限制”的響應(yīng)分組主要是由路由器的注入端口產(chǎn)生。因此，要發(fā)現(xiàn)y的別名，必須將分組的超時(shí)限制設(shè)置為y的跳數(shù)，從測(cè)量點(diǎn)V通過(guò)x和y向目標(biāo)地址D發(fā)起測(cè)量，才會(huì)收到來(lái)自于y的超時(shí)響應(yīng)分組，這樣就需要一個(gè)足夠大的地址集，來(lái)尋找互為別名的IP地址。Qian等[55]又提出在IPv6分組的頭部加入一個(gè)亂序的比特序列，從而通過(guò)多個(gè)測(cè)量點(diǎn)發(fā)起測(cè)量捕獲別名關(guān)系。

基于源路由的別名解析算法不足在于：1) 路由器是否支持源路由，若不支持則方法無(wú)效；2) 上述算法采用UDP協(xié)議，如果不支持UDP協(xié)議則方法無(wú)效。因此，基于源路由的別名解析算法只適用于部分路由器。

4.2 基于誘發(fā)式IPID的別名解析算法

4.2.1 TBT算法

Robert等[52]利用 IPv6的特點(diǎn)提出了一種誘發(fā)式IPID的別名解析算法（TBT, too-big trick），其基本過(guò)程如下。首先，測(cè)量點(diǎn)發(fā)送一個(gè)1 300 B的數(shù)據(jù)分組，這個(gè)分組超過(guò)了IPv6協(xié)議MTU的1 280 B限制，同時(shí)又小于IPv4協(xié)議的MTU限制的1 500 B，因此當(dāng)接收者收到該數(shù)據(jù)分組時(shí)會(huì)將數(shù)據(jù)分組返回給發(fā)送者。此時(shí)，測(cè)量點(diǎn)再根據(jù)IPv6協(xié)議發(fā)出一個(gè)“Too Big”分組，探測(cè)目標(biāo)收到此分組會(huì)將發(fā)送緩存設(shè)為1 280 B。然后，測(cè)量點(diǎn)再發(fā)送一個(gè)1 300 B的測(cè)量分組，探測(cè)目標(biāo)會(huì)將分組拆分為2個(gè)分組進(jìn)行發(fā)送并加入分段ID。此后，測(cè)量點(diǎn)發(fā)送的分組都會(huì)進(jìn)行類(lèi)似拆分，而同一個(gè)路由器不同端口發(fā)送的分組的ID必然相近，因此可以判定出別名關(guān)系。TBT算法如圖14所示。這種誘發(fā)式的別名探測(cè)方法準(zhǔn)確率十分高，而且減少了測(cè)量數(shù)據(jù)。

TBT算法雖然具有較高的準(zhǔn)確性，但是探測(cè)的數(shù)據(jù)量相對(duì)于IPv4的IPID方法的數(shù)據(jù)量要大很多，同時(shí)探測(cè)的次數(shù)隨著別名數(shù)的增加迅速增加，會(huì)帶來(lái)較大的網(wǎng)絡(luò)負(fù)載。

圖14 TBT別名解析算法原理

4.2.2 Speedtrap

Luckie[53]將誘發(fā)式的IPID探測(cè)技術(shù)與IPv4別名解析中的單調(diào)邊界測(cè)試函數(shù)相結(jié)合，提出了IPv6的別名解析工具Speedtrap，從而可以進(jìn)行整個(gè)網(wǎng)絡(luò)范圍內(nèi)的數(shù)據(jù)IP別名解析。Speedtrap別名解析的基本過(guò)程如下。

1) 通過(guò)測(cè)量確定響應(yīng)分組中帶有 IPID的網(wǎng)絡(luò)接口集合，目的是過(guò)濾掉那些不響應(yīng)測(cè)量和采用隨機(jī)計(jì)數(shù)器的路由器。實(shí)際上除了 Jupiter路由器外，華為、思科、惠普等多數(shù)路由器都響應(yīng)測(cè)量。

2) 確定哪些接口可能共享一個(gè)計(jì)數(shù)器，即哪些 IP位于同一臺(tái)路由器上。將響應(yīng)網(wǎng)絡(luò)接口的IPID按照時(shí)間劃分為不同的組，然后對(duì)不同的2個(gè)接口地址進(jìn)行探測(cè)，形成備選的別名關(guān)系集合。

3) 將不同路由器上的計(jì)數(shù)器進(jìn)行區(qū)分，對(duì)可能是別名的IP進(jìn)行反復(fù)測(cè)量，這樣使不位于同一臺(tái)路由器的接口返回的IPID差距變大，若IPID不再滿(mǎn)足MBT約束則將其從別名集合中刪除。

4) 對(duì)IP別名進(jìn)行探測(cè)和確認(rèn)。對(duì)還在別名集合中的任意 2個(gè)接口進(jìn)行測(cè)量，檢測(cè)其是否滿(mǎn)足MBT條件，從而進(jìn)一步確認(rèn)其別名關(guān)系。

采用Speedtrap對(duì)52 969個(gè)IP接口進(jìn)行了測(cè)量和分析，共耗時(shí)9 h，其中5.5 h用于確定接口的響應(yīng)分組是否包含IPID。實(shí)驗(yàn)表明有17 002個(gè)接口響應(yīng)測(cè)量，發(fā)現(xiàn)了11 181臺(tái)路由器。探測(cè)時(shí)間較長(zhǎng)的原因是：為了誘發(fā)路由器對(duì)IPv6分組進(jìn)行分組，需要發(fā)射的分組要比IPv4大46倍（至少1 280 B），由于數(shù)據(jù)量較大，故探測(cè)時(shí)間較長(zhǎng)。在真實(shí)網(wǎng)絡(luò)的訓(xùn)練集中測(cè)試發(fā)現(xiàn)，Speedtrap的正確性可以達(dá)到99%以上。

相對(duì)于TBT算法，Speedtrap的效率得到了提升，但是TBT算法和Speedtrap算法都需要接口共享計(jì)數(shù)器才能實(shí)現(xiàn)。統(tǒng)計(jì)表明，在實(shí)際部署的路由器中，僅有32%的路由器采用共享的計(jì)數(shù)器[53]，因此，這類(lèi)算法只能適用于部分路由器。

4.3 基于前綴的別名解析算法

Padmanabhan等[54]通過(guò)對(duì)IPv6端到端的IP地址配置方式進(jìn)行了研究，發(fā)現(xiàn)在 IPv6中采用了與IPv4相似的配置方式，多數(shù)采用“/126”前綴?；诖颂岢隽薝Av6算法，該算法分為2個(gè)階段，具體如下。

1) 進(jìn)行可能的別名集合探測(cè)。對(duì)一個(gè) IP的“/126”子網(wǎng)進(jìn)行探測(cè)，如果該前綴所包括的4個(gè)IP地址均能響應(yīng)ICMPv6的探測(cè)，則不會(huì)出現(xiàn)任何別名，當(dāng)有2個(gè)IP地址響應(yīng)時(shí)才能出現(xiàn)別名，設(shè)不響應(yīng)的地址為X1、X2，返回的源地址為Y，將其記錄下來(lái)。

2) 對(duì)于可能的別名集合進(jìn)行檢測(cè)。為了檢驗(yàn)是否為別名，采用 traceroute或路徑的最大傳輸單元來(lái)進(jìn)行檢測(cè)。如果某個(gè)X1位于Y的路徑上后一跳，則說(shuō)明X1不可能為別名，反之亦然。

UAv6算法提出了一種新的別名解析方法，但是該算法的復(fù)雜度較高，同時(shí)與IPv4中的相同源地址方法原理基本相似，不受路由器計(jì)數(shù)器及源路由的影響，可以與其他IPv6別名解析算法進(jìn)行互補(bǔ)，從而提高解析的全面性。

5 算法對(duì)比與分析

5.1 算法綜合分析

別名解析算法設(shè)計(jì)原理各異，適用于不同網(wǎng)絡(luò)環(huán)境。下面從算法的準(zhǔn)確性、完整性、開(kāi)銷(xiāo)、易用性、使用范圍等幾個(gè)不同的角度對(duì)這些算法進(jìn)行綜合對(duì)比，從而發(fā)現(xiàn)別名解析算法研究趨勢(shì)，如表 2所示。

準(zhǔn)確性：推斷的別名關(guān)系是否正確。

完整性：對(duì)別名是否能夠發(fā)現(xiàn)測(cè)量范圍內(nèi)的所有別名關(guān)系。

開(kāi)銷(xiāo)：用于探測(cè)別名所用探測(cè)分組的數(shù)量。當(dāng)需要發(fā)送分組越多時(shí)，網(wǎng)絡(luò)流量和時(shí)間越多，效率越低，反之，效率就越高。

簡(jiǎn)易性：算法使用是否簡(jiǎn)易，是否需要很多外部條件支持，即算法實(shí)現(xiàn)的難易程度。

協(xié)議：算法適用的IP協(xié)議，包括IPv4和IPv6。

適用場(chǎng)景：算法的部署方式以及范圍。

時(shí)間：論文發(fā)表時(shí)間。

實(shí)際上在各種別名解析算法中，主要有3個(gè)影響算法使用的因素：適用范圍、準(zhǔn)確性和效率。眾所周知，如果算法能夠集中部署，則大規(guī)模應(yīng)用較為容易；如果需要分布式測(cè)量往往不易實(shí)現(xiàn)。基于探測(cè)的算法中，如基于同源地址的 Mercator[24]、iffinder[25]、Alas[50]算法，基于 IPID 的 Ally[23]、RadarGun[37]、MIDAR[38]、TBT[52]、Speedtrap[53]等均可以通過(guò)集中部署的方式來(lái)實(shí)現(xiàn)，而基于圖論或拓?fù)涞乃惴ㄍ枰笠?guī)模的分布式測(cè)量來(lái)實(shí)現(xiàn)，在實(shí)際操作中難以實(shí)現(xiàn)，因此，這些算法往往借助于Ark、PlanetLab等大型測(cè)量項(xiàng)目才可以部署。

為了對(duì)算法的準(zhǔn)確性和效率有個(gè)全面的認(rèn)識(shí)，對(duì)典型算法的精度和時(shí)間效率進(jìn)行了對(duì)比，結(jié)果如圖 15所示，該結(jié)果綜合了 Garcia-Jimenez[35]、Padmanabhan[54]等實(shí)驗(yàn)結(jié)果。考慮到實(shí)驗(yàn)的差別，本文參照相關(guān)論文進(jìn)行了定性對(duì)比。從圖中可以發(fā)現(xiàn)基于同源地址的算法最為準(zhǔn)確，而采用 IPID的算法次之，基于網(wǎng)絡(luò)拓?fù)涞耐茢嗨惴▌t需要較大的開(kāi)銷(xiāo)，同時(shí)無(wú)法保證算法準(zhǔn)確性，在以后的算法設(shè)計(jì)中應(yīng)充分考慮上述因素。

為了進(jìn)一步說(shuō)明算法的演化過(guò)程理清研究思路，采用圖形進(jìn)行了展示，具體如圖16所示。從算法的演化過(guò)程可以發(fā)現(xiàn)，基于IPID及拓?fù)涞乃惴ㄗ疃?，也是發(fā)展最為迅速的研究方向，同時(shí)新的算法綜合考慮了各種要素，綜合運(yùn)用各種別名指紋，而采用時(shí)間戳、路由記錄字段的算法則研究的較少。此外，可以發(fā)現(xiàn)針對(duì)IPv6的別名解析算法由于IPv6的快速部署而受到重視，成為這幾年研究的熱點(diǎn)。但I(xiàn)Pv6別名解析算法主要集中在IPID或者是同源地址的方法，而采用拓?fù)渫茢嗟乃惴ㄝ^少。這主要是因?yàn)镮Pv6在近幾年才得到了大規(guī)模部署，其測(cè)量數(shù)據(jù)較少，缺乏必要的數(shù)據(jù)支撐。

5.2 未來(lái)研究方向

通過(guò)前文分析可以發(fā)現(xiàn) IPv4別名解析研究比較成熟，而針對(duì)IPv6的研究則處于起步階段，為此結(jié)合別名解析中的3個(gè)階段提出如下建議。

表2 別名解析技術(shù)對(duì)比

圖15 不同算法精度和復(fù)雜度的對(duì)比

1) 別名空間的選擇

別名空間選擇目的在于縮小可能互為別名的 IP地址范圍，從而減少探測(cè)開(kāi)銷(xiāo)，提高解析效率。在 IPv4空間中，由于地址空間有限，隨著計(jì)算能力的提高和網(wǎng)絡(luò)帶寬的擴(kuò)展，一些快速掃描技術(shù)如 Zmap[56]、Masscan[57]等可以在很短時(shí)間內(nèi)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)空間的掃描，從而為 IPv4的別名解析提供數(shù)據(jù)支撐。但是，IPv6地址空間十分巨大，按照現(xiàn)有的掃描速度需要1030年才能掃描結(jié)束[58]。在如此稀疏的 IP地址空間中要想縮小別名的搜索范圍有2種方法，一是挖掘路由器別名分配規(guī)律，二是通過(guò)全量測(cè)量發(fā)現(xiàn)所有活躍IP地址。

圖16 別名解析算法演化過(guò)程

針對(duì)如何發(fā)現(xiàn)路由器別名的分配規(guī)律，文獻(xiàn)[38]對(duì)IPv4別名進(jìn)行了分析。圖17是22 515對(duì)IP別名中2個(gè)IP地址的距離的累計(jì)分布概率，即2個(gè)互為別名的IP地址如果將其轉(zhuǎn)換為整數(shù)后的差異。從圖中可以發(fā)現(xiàn)在一個(gè)“/24”（即 IP之間的差小于128）位IP子網(wǎng)內(nèi)互為別名的IP地址不足30%，而一個(gè)“/16”（即IP之間的差小于65 536）位子網(wǎng)中互為別名的IP地址約為50%，這說(shuō)明即便在密度很高的IPv4網(wǎng)絡(luò)中，IP地址別名的距離也較大。在IPv6網(wǎng)絡(luò)中，IP地址資源更為豐富，因此試圖發(fā)現(xiàn)路由器的別名的分配規(guī)律來(lái)縮小別名的探測(cè)范圍變得更加困難。

圖17 IP別名之間的距離累計(jì)分布函數(shù)

針對(duì)如何發(fā)現(xiàn)所有活躍IP地址的問(wèn)題，解決方案為實(shí)現(xiàn)對(duì) IPv6空間的快速探測(cè)，從而根據(jù)IPv6的接口分布規(guī)律來(lái)進(jìn)行別名關(guān)系搜索。關(guān)于IPv6地址空間的快速探測(cè)研究有很多[59]，如DNS解析、被動(dòng)流量解析、traceroute測(cè)量等方法。據(jù)統(tǒng)計(jì)，在國(guó)外IPv6網(wǎng)絡(luò)較為普及，如美國(guó)、印度等超過(guò)50%的流量為IPv6流量，而探測(cè)發(fā)現(xiàn)的活躍 IPv6地址僅有 5×107個(gè)[60]，僅為一小部分，因此未來(lái)如何快速探測(cè)活躍IP地址是影響IP別名解析效率的關(guān)鍵。

2) 算法指紋特征的選取

在進(jìn)行別名解析算法的設(shè)計(jì)過(guò)程中，最主要的是設(shè)計(jì)別名識(shí)別的指紋特征。圖 16給出了主要?jiǎng)e名解析算法的演化過(guò)程，這些算法大致可以分為 3類(lèi)，即基于 IPID的算法、基于拓?fù)渫茢嗟乃惴捌渌惴?。其中前兩?lèi)算法由于得到了多數(shù)路由器的支持而得到了廣泛的應(yīng)用，而基于路由記錄、IGMP協(xié)議的算法由于多數(shù)路由器不支持甚至禁用，很難進(jìn)一步研究。因此，在算法的指紋選擇時(shí)，要選擇更加具有代表性的指紋特征才能使算法在更加廣泛的范圍中應(yīng)用。實(shí)際上，目前算法采用的很多指紋特征并沒(méi)有得到廣泛的支持。

Salutari等[61]通過(guò)大規(guī)模測(cè)量研究了路由器采用 IPID的情況，發(fā)現(xiàn)大多數(shù)路由器或主機(jī)采用常數(shù)IPID（39%）或局部計(jì)數(shù)器（34%），采用全局計(jì)數(shù)器的約占18%，無(wú)規(guī)律的約占7%和采用隨機(jī)數(shù)IPID的約占2%。在五類(lèi)IPID中，只有采用全局模式的路由器才能用于定位，這一測(cè)量結(jié)果說(shuō)明采用IPID進(jìn)行大規(guī)模的別名解析并不具有普適性。同時(shí)，Marchetta等[62]對(duì)1 400多個(gè)AS中 32.7萬(wàn)個(gè)目標(biāo)進(jìn)行了測(cè)量，經(jīng)分析發(fā)現(xiàn)有32.4%的路由器支持時(shí)間戳字段。這說(shuō)明目前作為 IP別名解析的主要方向的基于 IPID的方法僅能發(fā)現(xiàn)較小一部分的別名，而要提高 IP別名解析的準(zhǔn)確性，則要借助于全面的指紋特征。特別是針對(duì) IPv6協(xié)議進(jìn)行深入分析，發(fā)現(xiàn)其在路由記錄、組播協(xié)議、時(shí)間戳等方面的特征，豐富別名判別的指紋特征集合。

3) 基于機(jī)器學(xué)習(xí)的判定方法

別名解析本質(zhì)上是一個(gè)判別問(wèn)題，即判定2個(gè)或者多個(gè)IP是否互為別名，其判別依據(jù)是IP的域名、TTL、拓?fù)湮恢?、IPID連續(xù)性、出入度等，然而由于網(wǎng)絡(luò)中情況十分復(fù)雜，無(wú)法采用一種方式進(jìn)行全面的分類(lèi)，或者無(wú)法獲得完整的數(shù)據(jù)，必須采用多種指紋相結(jié)合的方式。在機(jī)器學(xué)習(xí)中，有很多基于多特征分類(lèi)或判別的方法，或者實(shí)現(xiàn)復(fù)雜推理的算法，機(jī)器學(xué)習(xí)技術(shù)的引入應(yīng)重點(diǎn)考慮以下2個(gè)方面。

① 不再借助于一個(gè)單獨(dú)的特征而是多個(gè)指紋特征，因此需要構(gòu)建全面的推理過(guò)程，如算法DisCarte中采用了析取邏輯規(guī)劃[33]，用以進(jìn)行復(fù)雜邏輯的推理，從而提高算法判別的全面性。

② 在算法中應(yīng)當(dāng)考慮不完全信息的處理，比如在拓?fù)浞治鲋型枰柚诖笠?guī)模分布測(cè)量，但是現(xiàn)實(shí)中無(wú)法實(shí)現(xiàn)，如 AliasCluster算法中采用的鏈?zhǔn)酵评磉壿?，就可以避免信息不完全所帶?lái)的別名誤判。因此，在推理中采用不確定性決策、灰色理論、貝葉斯網(wǎng)絡(luò)、決策樹(shù)等方法來(lái)構(gòu)建完善的推理過(guò)程。

6 結(jié)束語(yǔ)

別名解析技術(shù)是實(shí)現(xiàn)網(wǎng)絡(luò)空間從邏輯拓?fù)涞轿锢硗負(fù)溆成涞年P(guān)鍵步驟，同時(shí)也是網(wǎng)絡(luò)空間測(cè)量領(lǐng)域的技術(shù)難題。由于缺乏大規(guī)模的數(shù)據(jù)驗(yàn)證，別名解析技術(shù)的準(zhǔn)確性一直受到質(zhì)疑。然而由于網(wǎng)絡(luò)空間安全戰(zhàn)略的需要，必須進(jìn)一步提高別名解析算法的性能。別名解析不僅需要深入了解網(wǎng)絡(luò)協(xié)議細(xì)節(jié)、IP地址分配規(guī)律和網(wǎng)絡(luò)拓?fù)渲R(shí)，還需要借助于大規(guī)模網(wǎng)絡(luò)測(cè)量基礎(chǔ)設(shè)施進(jìn)行數(shù)據(jù)測(cè)量、收集及分析。特別是隨著IPv6的廣泛部署，在測(cè)量和分析上出現(xiàn)了許多新的問(wèn)題，如在IPv6網(wǎng)絡(luò)空間中實(shí)現(xiàn)別名集合快速獲取，低開(kāi)銷(xiāo)的快速測(cè)量、別名關(guān)系的準(zhǔn)確推斷等。要解決這些新問(wèn)題就必須采用新的方法，在算法的設(shè)計(jì)中應(yīng)當(dāng)采用多種特征信息，引入機(jī)器學(xué)習(xí)的方法，從而提高別名解析的準(zhǔn)確性和完整性，為網(wǎng)絡(luò)空間拓?fù)錁?gòu)建、態(tài)勢(shì)感知、追蹤溯源等業(yè)務(wù)應(yīng)用提供數(shù)據(jù)支撐。