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级拓扑原始度分布数据及拟合曲线。可看出实际Ark数据表现为一条近似直线，基本认为符合幂律分布。表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
转载注明来源:https://www.xzbu.com/8/view-15444087.htm
