IPv6視角下的因特網AS級拓撲分析

來源:用戶上傳      作者:魏鎮韓, 劉桂英

　　摘要：文章基于一種從真實IPv6分組轉發路徑中解析而來的AS鏈路數據集，分析對比了2012至2021年全球因特網AS級拓撲的特性。結果表明，近十年來全球自治系統基礎設施發展迅速，參與實際因特網IPv6流量的自治系統數量及其鏈路數均有顯著增長，但不同年份的AS級拓撲體現出相似的拓撲特性。經長期發展，IPv6視角下全球網絡核心仍只有較少量節點且與普通節點之間在不同測度上還存在明顯區分，度分布繼續表現出冪律特性。
　　關鍵詞：因特網;IPv6;自治系統;AS級拓撲;冪率
　　中圖分類號：TP393 文獻標識碼：A
　　文章編號：1009-3044（2022）32-0071-03
　　1 概述
　　準確分析因特網拓撲結構有助于預測、改善因特網性能及提高健壯性。因特網拓撲通常分為兩個層次，路由器級拓撲圖反映路由器之間邏輯連接關系，而自治系統級拓撲圖反映自治系統（Autonomous System，AS）之間邏輯連接關系。AS表示一個單獨管理機構控制之下的網絡，是全球因特網路由系統中的“路由策略單元”。AS相互之間依據商業協議交換流量，其相互關系定義了因特網高層次拓撲，提供了全球網絡生態系統的技術、經濟、政策和安全需求的洞察。
　　構建AS級拓撲通常依靠以下3種數據源：（1）BGP蹤跡采集器。采集器是一個與商業ISP網絡通過BGP會話建立對等關系的測量設備，從其對等方接收BGP報文，周期性備份所有采集的BGP表及更新報文，但不向對等方通告任何前綴。RouteViews[1]和RIPE RIS[2]作為兩個主要測量項目，部署采集器并使BGP數據可被全球研究人員獲取。（2）IRR路由信息。因特網選路注冊機構（Internet Routing Registrie， IRR）為ISP協調全球選路策略提供相應幫助。ISP可在IRR中注冊自己的選路策略。IRR數據庫由運營商手工維護，多數信息基于自愿來提供，有關信息不夠完整或陳舊，甚至不正確，屬于一種人工維護數據。（3）traceroute數據。Chang等人[3]首次提出從tracerout路徑中通過聚合生成AS拓撲的方法。利用BGP路由表信息將traceroute路徑中每個IP地址映射到它所屬AS，得到AS級轉發路徑，聚合相同AS節點得到AS級拓撲。
　　不同數據源的數據含義和完整性均有不同[4]。BGP蹤跡采集器提供的數據從選路系統視角反映因特網拓撲，稱為基于控制平面的AS級拓撲。IRR數據較特殊，其可靠性和實效性都不如其他數據源，生成的是人工創造的拓撲紀錄，稱為基于管理平面的AS級拓撲。而通過traceroute機制獲取的AS級拓撲源于實際分組轉發路徑，是反映網絡實際流量的拓撲，稱為基于數據平面的AS級拓撲。1999年Faloutsos兄弟[5]首次揭示了因特網自治系統級拓撲的冪律（power-law）特征，是拓撲特性分析中最重要研究成果。路由器級拓撲中是否存在冪律仍有不同結論[6]。冪律的發現深刻影響了因特網拓撲建模方式，但目前也出現了區別于冪律分布這種全局統計模型的其他模型[7]。近來研究表明AS級拓撲的連接越來越緊密，結構越來越復雜[8]，網絡鏈路的演化是推動互聯網演化的主導力量[9]，故對AS級拓撲進行繼續研究是必要的。
　　2 基于IPv6路由的AS鏈路數據集
　　應用因特網數據分析中心（Center for Applied Internet Data Analysis， CAIDA）使用拓撲測量平臺Archipelago（Ark）通過并行化工具執行針對IP目標的traceroute測量，將17-18個探測器組成一個探測組以100pps的速度探測所有探測目標，目前有三個探測組處于活動狀態，每個探測組均獨立進行探測。每48小時探測一次所有IPv4前綴（/24）中的隨機地址；每24-48小時探測一次所有在因特W中被實際通告的IPv6前綴（/48）中的隨機地址。
　　CAIDA使用RouteViews BGP數據來識別每個響應IP地址所對應的自治系統，并將原始探測的IP路徑轉換為一個AS之間的鏈路集合。該過程可能由于以下原因導致潛在失真：（1）IP地址無法轉換到AS：一些IP地址在拓撲探測中出現但是沒有被任何AS通告。（2）AS集合：一個聚合的AS集合通告了某個前綴。（3）多起源AS（Multi-origin ASes， MOASes）：多個獨立的AS通告了相同的地址前綴。一旦IP地址被映射到AS，將出現兩種AS鏈路類型：直接鏈路，其中兩個鄰接的IP地址映射到不同AS；間接鏈路，其中兩個不同AS的IP地址被無法識別AS的一跳或多跳所分開（因某些跳未響應或未能識別某跳地址所屬AS）。CAIDA的AS鏈路數據集中，間接鏈路將注解出AS之間缺失IP跳的數量。
　　3 AS級拓撲分析
　　3.1 基本分析
　　本文使用CAIDA提供的基于IPv6路由的AS鏈路數據集作為原始數據，從2012到2021年各提取數天全球AS級鏈路數據進行拓撲分析。表1列舉了歷年AS級拓撲節點總數、直接鏈路節點數、直接鏈路數及平均度等基本數據。
　　原始數據包含直接鏈路和間接鏈路。實際分析發現，間接鏈路準確性存在很大疑問。如2021年數據中，若采信所有間接鏈路，AS 33915將具有2509條AS鏈路，其AS等級（鄰居數量）總排名高居第5，但實際上該AS隸屬沃達豐（荷蘭）電信公司，作為一個地區級自治系統其真實等級并不高，結論顯然錯誤，這是因為該AS與其他AS之間存在大量間接鏈路，之間僅僅存在一跳無法識別其AS的IP地址。除AS節點總數，以下分析只統計直接鏈路及相應節點。
　　表1中節點總數指所有鏈路（含間接鏈路）中出現的AS數量，參與實際IPv6流量的AS數量在10年間明顯增加6倍，從一個側面反映出因特網在IPv6方面持續快速發展。表中顯示直接鏈路節點數占節點總數大約在95%至97%之間。令拓撲節點總數為n，鏈路總數為m，則拓撲平均度定義為[k=2m/n]，表示最粗粒度的連通性特性。平均度較高表示其網絡連通性在平均意義上也較好。盡管節點和鏈路數近10年來均顯著增加，全球因特網AS級拓撲平均度位于4.8至6.5之間，表明AS級拓撲平均連通性長期穩中有增，增長趨勢較緩。

nlc202301131355

　　表2列舉了2021年AS等級前十位的AS基本信息，多數AS在歷年等級排名中均位于前列。盡管只從鄰居數量來確定AS等級具有一些局限性，但鄰居數量反映了AS與因特網其他網絡實體的互聯互通程度。從歷年分析結果看，長期以來等級排名較前的AS基本屬于歐美國家且十分穩定，說明西方發達國家在因特網基礎設施建設上仍具有巨大優勢。
　　3.2 測度分析
　　拓撲測度從不同視角描述了因特網拓撲特性，本文分析其中常用的四種測度。實際分析表明，歷年AS級拓撲均展現相似拓撲特性，限于篇幅以下僅顯示2021年測度分析圖。
　　3.2.1 度分布
　　節點度定義為節點的鄰居數量，度分布P（k）=n（k）/n表示一個隨機選取節點其度值為k的概率，n表示節點總數，n（k）表示度值為k的節點數。盡管是局部特性，但度分布提供了網絡結構的全局觀察。度分布可用冪率形式[P（k）∝k-γ]來描述[5]，γ表示冪指數。冪律意味著少數節點擁有非常多的鏈路，而大多數節點只擁有少量鏈路。
　　使用補累積分布函數描述拓撲度分布，對數坐標下符合冪律的分布將表現為一條直線。圖1顯示2021年AS級拓撲原始度分布數據及擬合曲線?？煽闯鰧嶋HArk數據表現為一條近似直線，基本認為符合冪律分布。表3列舉了歷年度分布擬合曲線的誤差平方和SSE及確定系數R-Square數值。SSE表示擬合數據與原始數據對應點的誤差平方和，越趨近0則擬合越好。R-Square定義為SSR和SST之比，其中SSR表示擬合數據與原始數據均值之差的平方和，SST表示原始數據與其均值之差的平方和。確定系數取值范圍為[0，1]，越接近1則擬合效果越好。表3顯示歷年拓撲度分布均表現出明顯冪律特性。
　　3.2.2 聯合度分布
　　聯合度分布表示一條隨機鏈路其兩端節點度值分別為k1和k2的概率：P（k1，k2）～m（k1，k2）/m，m表示鏈路數，m（k1，k2）表示兩端節點度值分別為k1及k2的鏈路數。本文使用聯合度分布的一個單變量概要統計量，稱為平均鄰居連通性，表示度值為k的節點其鄰居平均度[Knn（k）=kkmaxk'P（k'|k）]，k’表示k度節點其鄰居的度值，kmax表示鄰居的最大度值。平均鄰居連通性體現了給定度值的節點連接高度值節點或低度值節點的傾向。圖2顯示了2021年AS拓撲平均鄰居連通性點圖。多數節點其度值范圍位于10～200之間，而度值適中的節點其鄰居在度值上的差異較大。當k取一個特定較低值時其Knn（k）能達到較高值，說明高度值節點的鄰居多數為較低度值節點，而較低度值節點的鄰居則可能具備高度值，高度值節點想要獲取較高的鄰居平均度是較困難的。
　　3.2.3 聚類
　　節點i所有鄰居之間的鏈路總數與其可能的鏈路總數之比稱為聚類，表示了節點鄰居之間形成一個集團的緊密程度。令Mnn（k）是k度節點其鄰居之間的平均鏈路數，則k度節點的鄰居之間最大可能鏈路數為k（k-1）/2，局部聚類表示為k度節點鄰居之間的平均鏈路數與最大可能鏈路數之比：C（k）=2Mnn（k）/k（k-1）。圖3顯示了2021年AS級拓撲局部聚類點圖。較高度值的節點或較低度值的節點其局部聚類值均較低。這是因為節點度值越高，其鄰居也越多，鄰居之間越來越難保持較高的緊密性；而節點度值越低，其鄰居越少，鄰居之間的連接也較少。圖中顯示度值在100左右的節點其鄰居之間的局部聚類值是最高的。
　　3.2.4 富人俱樂部連通性
　　富人俱樂部描述了少量度值較高的節點（富節點）傾向于相互連接從而形成核心團體這一現象，反映了因特網在結構上的等級性質。這并不意味著富節點大部分鏈路直接指向其他富節點，事實上富節點擁有相當多鏈路，而只有少數鏈路連接其他俱樂部成員。網絡中前r個度值最大的節點定義為富人俱樂部成員，這些節點之間實際鏈路數與可能存在的鏈路總數之比稱為富人俱樂部連通性。圖4將富人俱樂部連通性表示一個函數φ（r/n），r/n表示由節點總數n歸一化的節點等級，若φ（r/n）為1則表示此等級的所有節點之間都存在直接連接。圖中顯示隨著俱樂部成員的增加φ（r/n）值隨之降低，降低趨勢從平緩下降轉為快速下降，這個轉折處實際上意味著網絡核心與外圍的分界，可看出網絡核心節點比例不超過節點總數的0.1%。
　　4 結論
　　本文基于CAIDA所提供的AS鏈路數據集，分析對比了2012至2021年基于IPv6數據的因特網AS級拓撲特性。分析結果表明，近十年來參與實際因特網IPv6流量的自治系統數量及其鏈路數均增長明顯，長期以來AS級拓撲的平均度平穩中有緩慢提升。不同年份因特網AS級拓撲在多個測度上均表現出相似的性質，從IPv6這個視角看，因特網AS級拓撲的度分布仍舊表現出冪律特性。
　?、考文献?
　　[1] University of Oregon Route Views Project[EB/OL]. http：//www. route-views.org.
　　[2] RIPE RIS Raw Data[EB/OL]. http：//www.ris.ripe.net.
　　[3] Chang H， Jamin S， Willinger W. Inferring AS-level Internet topology from router-level path traces[C]. Denver， Proceedings of SPIE ITCom 2001， 2001：196-207.
　　[4] Mahadevan P， Krioukov D， Fomenkov M， et al. Lessons from three views of the internet topology[J]. Physics， 2005， 95-B（11）：1450-1452.
　　[5] Faloutsos M， Faloutsos P， Faloutsos C. On power-law relationships of the Internet topology[J]. ACM SIGCOMM Computer Communication Review， 1999， 29（4）： 251-262.
　　[6] Spring N， Mahajlan R， Wetherall D. Measuring ISP topologies with Rocketfuel[J]. ACM SIGCOMM Computer Communication Review. 2002， 32（4）： 133-145.
　　[7] Jiao B， Zhang W. Structural Decomposition Model for the Evolution of AS-Level Internet Topologies[J]. IEEE Access， 2020， 8：175277-175296.
　　[8] 陳龍，劉沛佳. AS級網絡拓撲的節點動態性演化行為分析[J].北京工業大學學報，2018，44（4）： 546-552.
　　[9] Liu Xiao， Wang Jinfa， Jing Wei， et al. Evolution of the Internet AS-level topology：From nodes and edges to components[J].Chinese Physics B，2018，27（12）：204-214.
　　【通聯編輯：代影】

nlc202301131355

轉載注明來源:http://www.hailuomaifang.com/8/view-15444087.htm