IPv6網絡拓撲測量目標選擇技術

產毛寧， 張 宇

(哈爾濱工業大學 計算機科學與技術學院， 哈爾濱 150001)

0 引 言

互聯網向基于 IPv6 的下一代互聯網演進已成為全球普遍共識，目前IPv6的部署和使用正在飛速增長，但是由于IPv6 地址空間巨大，地址規劃復雜，地址空間劃分政策多樣，以及地址實際使用率低等這些不同于IPv4 的問題，使得IPv6 網絡拓撲測量成為一個巨大的挑戰。作為IPv6 網絡拓撲測量的輸入，IPv6 拓撲測量目標選擇技術研究如何通過有效地選擇目標來提高拓撲測量的有效性和完整性。

為了克服上述問題，大量的研究工作從IPv6存活地址列表收集、IPv6地址分析、IPv6地址生成和IPv6網絡拓撲測量的角度展開。IPv6 存活地址列表(Hitlists)的收集技術包括主動技術如隨機探測::1[1]，完整探測每個聲明的/32前綴中的每個/48中的::1地址[2]，rDNS zone 游走，被動技術如基于BGP update或從流量中獲取[3,4]。Gasser等觀察到存活地址列表本身包含聚類，從均衡性和無偏性的角度提出了TUM Hitlist[5]；Ullrich等使用遞歸的算法來發現和提取IPv6地址模式[6]；Foremski等提出了Entropy/IP 系統，使用了貝葉斯模型和聚類分析的機器學習技術來發現IPv6地址結構[7]；Murdock等設計了6Gen目標生成器，利用地址局域性，迭代識別高密集區域[8]。上述工作的主要目標為IPv6網絡主機發現，而非IPv6網絡拓撲發現。CAIDA Ark利用分布式測量點對每個全球聲明的BGP可路由的/48或更短前綴中1個::1地址和1個隨機地址做ICMP-Paris traceroute，但實踐中無法細粒度地抽樣，同時存在大量冗余探測。與本文類似，Beverly等將存活地址列表用于IPv6 接口級網絡拓撲發現[9]，但缺少預測存活地址前綴列表的獨立研究。

本文從IPv6存活地址列表的角度，首先探究多源的IPv6存活地址列表收集技術，用盡可能多的來源保證IPv6存活地址的完整性；然后從多角度分析收集到的IPv6存活地址列表的特征，觀察并總結該列表所體現出特性以及針對IPv6網絡拓撲測量的使用上的指導，為了補充列表采集中的可能缺失和猜測未來可能增長的地址空間，提出IPv6 存活地址前綴列表的預測算法并評估；最后給出IPv6網絡拓撲測量目標生成的技術方案，研究的總體流程如圖1所示。本文的主要貢獻如下：

(1)利用IPv6存活地址列表指導IPv6網絡拓撲測量目標選取。

(2)提出存活地址前綴預測算法。

(3)提出IPv6網絡拓撲測量目標選取的綜合方案。

圖1 目標選取技術總體流程設計

1 IPv6網絡拓撲測量目標選取技術

1.1 IPv6存活地址列表收集與融合

類似于IPv4，IPv6存活地址列表(Hitlist)指一組能夠大體上覆蓋和代表IPv6網絡的地址集合，并具有存活性，地址被分配、部署并在使用中；完整性，覆蓋所有存活的IPv6地址空間；穩定性，地址列表隨著時間變化盡可能小。本文嘗試從5種不同的地址來源獲取IPv6存活地址列表，包括：

(1)Rapid7_FDNS：FDNS數據是Rapid7的Project Sonar公開數據一部分，本文采用其中的fdns_any數據，包括所有對ANY 查詢的回復，通過提取其中的AAAA記錄，最終得到IPv6地址。

(2)CAIDA_Ark：IPv6 拓撲數據集作為CAIDA Ark 平臺測量數據的一部分，通過使用Paris Traceroute技術探測所有聲明的/48或者更短的IPv6前綴中的隨機地址。本文從CAIDA 2月的IPv6拓撲數據里提取路徑中出現所有IPv6地址。

(3)Bitnodes：Bitnodes 通過發現網絡中的所有可達節點來評估比特幣網絡的大小，本文使用Bitnodes提供的API，從節點名稱中提取IPv6地址。

(4)TUM_Responsive：德國TUM 大學通過對IPv6 存活地址列表的研究，提供IPv6 Hitlist服務，本文直接采用服務提供的回復的IPv6地址。

(5)TUM_Seeds：德國TUM大學的Hitlist服務作為一個收集項目，本身也采用了不同的收集源，根據其倉庫中的實際數據，包括有Alexa、CAIDA_dnsname、CT(Certifcate Transparency)、Zonefiles、Openipmap和Traceroute，其中前4個根據提取的域名，查詢AAAA記錄，來獲取IPv6地址；Openipmap為從RIPE ipmap 項目中提取的IPv6地址；Traceroute為對所有其它源中的地址Traceroute再提取所有的路由器IPv6地址。本文將該倉庫里不同來源地址綜合作為一個收集源。

最后對不同來源存活地址列表清洗再合并，得到融合后的IPv6地址存活列表。由于收集到的地址中還包括特殊目的的全球單播地址，如過渡方案中的6to4地址等，需根據IANA提供的最新全球單播地址分配做篩選。

1.2 IPv6存活地址特征分析

為了探究IPv6 存活地址列表在IPv6網絡拓撲測量上的最佳實踐，有必要對收集到的IPv6存活地址列表深度分析，觀察IPv6地址空間的部署和使用，揭示IPv6地址結構上的聚類，總結IPv6存活地址列表對IPv6網絡拓撲測量目標選取上的指導作用。IPv6地址一般可以分為網絡前綴和接口標識兩部分。

1.2.1 IPv6網絡前綴分析

IPv6網絡前綴一般指IPv6地址的前64比特。本文為了拓展討論將前綴長度放寬至128比特，選擇長度范圍[32,128]來分析前綴，/32作為下屆，因為/32前綴通常是區域性互聯網注冊機構(Regional Internet Registries，RIRs)分配給本地互聯網注冊機構(Local Internet Registries，LIRs)的最小塊，128是IPv6地址的最大長度。輸入為不同來源的IPv6存活地址列表，并嘗試從頻率分布，相鄰長度前綴關聯性，密度3個角度分析IPv6前綴。首先從IPv6存活地址列表中提取不同長度前綴列表，再依次進行以下分析：

(1)不同長度前綴頻率分布分析。統計不同長度前綴列表中的不同前綴頻率。

(2)相鄰長度前綴關聯性分析。Plonka等介紹了前綴聚集計數比率(Aggregate Count Ratio，ACR)[10]，對于給定的N個地址，將其聚合成不同長度的前綴，接著對于給定前綴長度p，聚集計數np作為不同/p包含的地址數量，并設定p為0時np為1，則rp=np+x/np，其中x代表相鄰前綴的長度差，單位為比特。本文依次取x為 4、8、12和16計算ACR。

(3)不同前綴長度密度分析。統計不同長度前綴列表中不同前綴包含的IPv6存活地址數M，再計算各長度前綴列表中M的四分位數。

1.2.2 IPv6接口標識分析

IPv6接口標識一般指IPv6地址的后64比特，從生成類別上可以分為人工指定和算法自動生成兩種，不同的生成方案見表1。張千里等總結了不同的接口標識生成方案，其中人工指定的方案包括[11]：

(1)基于低字節的接口標識(Low-byte)生成方案，一般指的是除最低兩個字節外接口標識的大部分設為0。

(2)基于IPv4地址(Embed-IPv4)的生成方案，一般指將IPv4地址作為接口標識的最后4個字節或者將IPv4地址的每個字節對應編碼到最后的4個16比特中。

(3)基于服務、端口號(Embed-port)的生成方案，一般指將服務器的端口號或編號嵌入到接口標識中。

(4)基于單詞(wordy-based)的生成方案，一般指使用易于記憶的單詞代替16進制數字作為接口標識。

算法自動生成的方案包括：

(1)基于MAC地址的IEEE EUI-64(IEEE-based)的生成方案，通常由48位的硬件地址，中間嵌入0xfffe得到，使得接口標識綁定機器硬件且全局唯一。

(2)保護用戶隱私的生成方案，一般隨機生成且隨時間變化而變化。

(3)穩定、語義不透明的生成方案，目的是為了解決臨時地址變化頻繁導致的復雜的網絡管理和部署問題，接口標識隨機生成但對同一子網、同一網絡接口產生地址相同。

(4)綁定地址與主機的生成方案，源于局域網內安全風險與多宿主機，生成IID隨機，一般有加密生成接口標識方案和基于哈希的地址生成方式。本文使用addr6工具統計融合后IPv6存活地址列表中不同接口標識生成方案的占比，分析不同方案的實際部署和使用情況。

表1 常見的接口標識生成方案

1.3 IPv6存活地址前綴列表預測

考慮到IPv6存活地址列表由于收集來源的缺失如不包括非公開數據源，和限制如缺少長時間的積累，可能帶來的不完整性，以及IPv6地址部署和使用的快速增長帶來的滯后性，有必要設計一種方法能夠根據已知收集的IPv6存活地址列表，預測未被收集的潛在存活和未來可能部署和使用的地址，作為IPv6網絡拓撲測量目標的補充來提高拓撲發現的完整性。IPv6存活地址前綴列表指一組包含IPv6存活地址的前綴集合。本文為了更完整地探測特定IPv6可路由前綴R下的目標網絡拓撲，基于收集的IPv6存活地址列表，從網絡拓撲測量中按前綴均勻抽樣的常用方法出發，提出IPv6存活地址前綴列表預測算法PrefixPrediction，即根據IPv6存活地址列表提取前綴集合，再結合多層級密度聚類和啟發式后綴拓展，來預測未被收集的IPv6存活地址前綴列表，最終作為拓撲測量目標生成的一部分。

根據實踐中地址分配體現出的層級性，以半字節即4比特為單位劃分；和局部聚集性，分配的地址聚集在相鄰或相近的前綴下，本文提出的算法核心思想為針對特定IPv6可路由前綴R下的目標網絡，根據R包含的IPv6 存活地址列表HL中提取的IPv6 存活地址前綴列表，預測固定長度為L的IPv6 存活地址前綴列表。R的長度LR∈[32,64]，L∈{40,48,…,64}。對于用32位16進制數xj表示的IPv6地址Xi，則包含n個地址的HL形式化表示(1)：

HL={X1,X2,…,Xi,…,Xn}，

(1)

(1)多層級密度聚類。按不同前綴長度32～64，以8位間隔來劃分層級，采用32作為最小長度，而64比特的位置一般作為網絡標識和接口標識的分界。對于層級Levelp形式化表示(2)：

(2)

(3)

(4)

(5)

結合(1)(2)步，得到Levelp的預測的IPv6存活前綴列表HPLp，形式化表示為式(6)：

(6)

最終合并不同HPLp得到輸出HPL。

1.4 IPv6網絡拓撲測量目標選取

在IPv6網絡拓撲測量目標選取一般采用對BGP路由前綴列表均勻隨機抽樣的策略。基于這種均勻隨機抽樣的方法，本文從IPv6存活地址列表的角度出發，分為兩步選取IPv6網絡拓撲測量的目標：

(1)對存活地址列表按/64前綴均勻隨機抽取；

(2)根據IPv6存活地址前綴列表預測算法，得到預測的/64前綴列表，并對每個前綴拼接隨機接口標識，最終合并這兩步的輸出。基于IPv6存活地址列表的IPv6網絡拓撲測量目標選取的綜合方案如圖2所示。

圖2 目標選取的綜合方案

2 實驗結果與分析

2.1 IPv6存活地址列表收集與融合

合并不同來源的存活地址列表，得到融合的IPv6存活地址列表約17M。不同來源的IPv6存活地址列表統計結果見表2，可以觀察到不同來源在融合的IPv6 存活地址列表中貢獻的差異。其中，獨占：融合的IPv6 存活地址列表中僅由該源提供的地址數量；占比：采用該源的地址與融合的IPv6 存活地址列表交集數占融合的IPv6 存活地址列表的比例。可以發現不同來源占比以及獨占比差距不大，CAIDA_Ark 甚至基本一致，說明這些不同來源背后采集技術的不同，導致不同來源存活地址列表獨立性強，都應該被采用。

表2 IPv6存活地址列表統計

2.2 IPv6存活地址特征分析

IPv6存活地址特征主要針對最終融合的IPv6存活地址列表。

2.2.1 IPv6網絡前綴分析

不同長度前綴頻率分布結果如圖3所示。數據包括最終融合的IPv6存活地址列表Total及其最主要的3個收集來源，Rapid7_FDNS、CAIDA_Ark和TUM_Responsive，可以觀察到不同來源IPv6存活地址列表的頻率分布存在共性，隨著前綴長度的增加，在[32,64]的區間內呈現明顯的上升趨勢，而在[64,128]的區間內趨于平緩，表明存在大量的IPv6存活地址聚集在64長度以下的IPv6前綴中。

圖3 IPv6存活地址列表不同長度前綴頻率分布

融合IPv6存活地址列表的不同長度前綴ACR值分布如圖4所示。可以觀察到不同相鄰前綴的長度差下ACR值隨著前綴長度的增長，總體在[32,64]區間變化大且多呈現下降趨勢，在[64,128]區間變化較小且增減交替，相鄰前綴的長度差越小，ACR值變化越多，表明相鄰前綴的長度差越小，越能反應相鄰前綴的差異。

圖4 IPv6存活地址列表不同長度前綴ACR值分布

融合IPv6存活地址列表的不同長度前綴密度分布如圖5所示。可以觀察到[32,64]區間內前綴長度越短，相對地址密度越大，在前綴長度[40,128]區間包含存活地址數的中位數都為1，甚至在[60,128]上四分位數和下四分位數也為1，表明該區間的大多數前綴僅包含1個存活地址，同時[32,40]區間的中位數都不超過10，表明IPv6存活地址列表中不同長度的特定前綴包含存活地址都偏少，數值在1～10之間，呈現出低密度性。

圖5 IPv6存活地址列表不同長度前綴密度分布

2.2.2 IPv6 接口標識分析

IPv6接口標識(IID)分析的結果見表3。可以觀察到，隨機化的地址在不同來源中占據大部分，為50%～80%，表明大多數接口標識是隨機的，而基于IPv4地址和端口號的生成方案地址在不同來源中占比較小，基于低字節和IEEE EUI-64方案的地址占比相對較多。此外，不同收集來源下接口標識生成方案占比分布不同，除隨機化地址外，Rapid7_FDNS中基于低字節方案的地址最多，而CAIDA_Ark 和 TUM_Responsive 中EUI-64地址最多。

表3 不同IID模式在存活地址列表中占比統計

綜上，融合的IPv6存活地址列表呈現高聚集，即大量地址聚集在較短的前綴中；多層次，即長度差越小，越能反應相鄰前綴的差異性；低密度，即不同長度前綴包含存活地址數的中位數為1～10；接口標識不可預測性，即大部分接口標識是隨機的。

2.3 IPv6存活地址前綴列表預測

為了評估預測算法的效果，針對特定/32前綴網絡，對IPv6存活地址列表過濾得到/64存活前綴列表，對該列表的隨機50%作為訓練集，剩余50%作為測試集，計算本文算法PrefixPrediction(PP)的正確率，并與Entropy/IP(EIP)結果作比較。預測集：輸出的與測試集相同數量的預測前綴列表；正確率：預測集與測試集的交集占測試集的比例。本文在3個數據集H1、H2和H3做實驗，實驗結果見表4。

表4 PrefixPrediction與Entropy/IP實驗結果對比

實驗結果表明，本文的前綴預測算法PrefixPrediction正確率相比Entropy/IP 高，在1.4～5.5倍之間，同時二者預測前綴的交集小，有強互補性。預測集增長下的正確率變化趨勢如圖6所示，可以發現隨著預測集增長，PrefixPrediction比Entropy/IP正確率都要高，二者的正確率都呈現線性增趨勢，表明兩種算法的預測能力都具有穩定性。

圖6 預測集增長下正確率變化趨勢

2.4 IPv6拓撲測量目標選取

為了驗證本文基于IPv6存活地址列表的IPv6網絡拓撲測量目標選取方法的效果，針對特定/32可路由前綴的目標網絡，分別采用本文方法HS和按/64均勻隨機抽樣方法URS，對一定數量目標采用ICMP-paris的探測方法，對比結果的節點數和鏈接數。目標網絡包括T1(2001:16b8::/32)、T2(2a02:06b8::/32)和T3(240e:00e0::/32)。本文方法中對存活地址列表按/64均勻隨機抽樣數的2倍，相應的URS為從均勻隨機抽樣的地址中再隨機抽取該數量；traceroute路徑中發現的不同IPv6接口地址數；traceroute路徑中發現的不同IPv6接口地址連接數。本文對3個數據集T1、T2和T3分別采用不同測量點做實驗，實驗結果見表5。

實驗結果表明，本文基于IPv6存活地址列表的IPv6網絡拓撲測量目標選取方法HS比均勻隨機抽樣方法URS明顯提高了拓撲發現的完整性，拓撲新發現率在94%以上，拓撲發現結果隨探測目標增長變化如圖7和圖8所示，HS相比URS結果表現一直要好。拓撲的完整性即發現的節點數和鏈接數，拓撲新發現率即HS相比URS新發現的節點和鏈接占HS的比率。

表5 HS和URS 實驗結果對比

圖7 發現節點數隨探測測量目標數增長變化

圖8 發現鏈接數隨探測目標數增長變化

3 結束語

本文提出一種IPv6 網絡拓撲測量目標選取技術，用于提高IPv6網絡拓撲測量的有效性和完整性。首先，收集并融合不同來源的IPv6存活地址列表得到約17M的地址；其次，分析了IPv6存活地址列表的特征，發現融合存活地址列表呈現出高聚集、多層次、低密度和接口標識不可預測性，提出了IPv6 存活地址前綴列表的預測算法PrefixPrediction，對比Entropy/IP預測的正確率更高，發現二者結果具有強互補性；最后，給出了IPv6網絡拓撲測量目標選取的綜合方案HS，對比URS明顯提高拓撲發現的完整性，拓撲新發現率超過94%。未來將進一步豐富收集技術，提高IPv6存活地址列表的完整性，結合多種IPv6存活地址前綴預測算法來提高預測正確率，從而更深入地進行IPv6網絡拓撲測量的研究。