2. 广西民族大学信息科学与工程学院, 南宁 530006;
3. 山东大学网络与信息中心, 济南 250100
2. School of Information Science and Engineering, Guangxi University for Nationalities, Nanning 530006, China;
3. Network and Information Center, Shandong University, Jinan 250100, China
边界网关协议(BGP)是目前唯一广泛使用的域间路由协议，对维护自治系统间路由连通性有重要的作用。随着Internet发展，BGP路由表规模不断膨胀，同时还发现BGP路由系统存在路由波动和慢收敛等现象。BGP协议面临的这些挑战促使人们围绕以BGP路由表为对象展开一系列研究工作。
1988年Merit开始收集外部网关协议(EGP)路由表[1]。90年代中期，BGP路由表收集和分析工作在许多自治系统(AS)内开展起来[2, 3, 4]。其中成果较为显著的是Huston[5]基于Routeviews[4]项目采集的路由信息分析了BGP路由表的规模变化情况。
然而，随着Internet服务提供商(ISP)多种对等(peer)关系和多宿主(multi-homing)连接的建立，Internet域间路由系统的规模不断膨胀，AS数和核心网络BGP转发表项的增长非常显著，路径多样性以及路径质量(包含性能)测量开始成为研究热点。
1997年11月BGP路由表与转发表的比值为15.7，2009年6月其比值已扩大至35.6[5]，这说明ISP之间有更多的可达路径，Internet网络拓扑越发密集，AS路径多样性趋势越发明显。2001年，Nayak等[6]通过跟踪路由(tranceroute)方法，最早对AS级别的路径多样性进行了初步研究，可是这些研究仅仅依靠简单的测度并且测试度很小。Tei1eira[7, 8]等开始尝试应用图论的方法来研究路径多样性，但是这类方法忽略了复杂网络中的AS关系以及AS的出入度等内在因素，因此准确度较低。Zhang 和Wang等[9, 10]指出互联网确实存在比默认路径更短延迟的路径。
本文基于BGP IPv4路由表，提出了一种域间路径特性分析模型，设计了基于算法的实验统计框架，研究了AS规模增长、 AS类型分布和域间路径特性等。
1 域间路径特性及其影响因素分析 1.1 域间路径特性描述近年来，互联网拓扑和路由的测量研究一直是评价、改进和完善互联网技术的基础性工作。通过对路由系统中路由数据的采集、测量和分析，可以获得域间路径特性相关指标，客观地评价现有路由系统的性能，并分析其影响因素，从而指导网络工程设计。域间路径特性可以分为3类： 第1类是AS规模及其变化，通过对其展开测量研究，便于理解互联网规模的发展趋势； 第2类是路径多样性，通过开展域间路径多样性的量化研究，有效支持域间多路径路由的设计； 第3类是路径长度，通过分析域间路径基于长度属性的分布，更加深入地理解现今互联网使用何种类型的路径进行流量传输。
域间路径多样性是Internet网络空间内AS路径属性所呈现出的广泛范围的变化和不同，常用于描述Internet网络空间内路径对象属性的差异，属于AS级别的路径多样性。路径多样性的丰富程度不仅反映出路径的绝对数量，而且也表现出基于不同属性的路径的分布情况。路径长度指的是路径所含中间AS的数量，针对最短路径和默认路径(BGP选取的“最优路径”)进行测量分析，有助于理解互联网协议及其基础设施的整体效率，提高域间路由的服务质量和性能。本文按照相关策略将底层互联网的AS路径进行分类，通过统计不同AS路径的数量和长度，实现域间路径特性及其多样性分析。
1.2 影响因素分析作为全球最大的分布式信息系统，互联网是由许多独立的AS互联而成。互联网早期是一种典型的层次结构，整个互联网大致分成三层： Tier1、 Tier2和Tier3。Tier1层由全世界范围内的长距离承载网络构成，属于这一层的ISP称为Tier1的ISP； Tier2层通常由跨越州甚至国家的承载网络构成； Tier3层通常由地区级的承载网络构成。Tier2和Tier3的ISP通常通过高一层ISP互相连接起来，而同层的ISP相互连接。例如，Tier2的ISP仅连接到Tier1的ISP，但不会连接到Tier2层的其他ISP。这种互联结构是一种层次化的路由体系，在这种层次结构中路径的多样性是十分有限的。然而，随着互联网结构的不断演进与发展，最初的互联网组织结构发生了巨大变化。为了提高互联网访问的可靠性和健壮性，以及满足特定的商业目的，AS之间的互联关系引入了2种重要的连接技术： 对等互联(peering)和多宿主(multi-homing)。
对等互联是2个规模相当的AS之间建立连接，免费为彼此的客户提供流量传输，以缩短客户访问网络服务的延时，或是满足其他的商业目的。多宿主技术可以为AS访问互联网提供多条传输路径，因此AS可以利用该技术获取的多条路径进行并行流量传输以提高传输效率，或者将其中一条或多条路径设置为备份路径(即在主路径拥塞或中断时能够切换到替代路径上)以缩短故障恢复的时间、保证业务的正常使用。而且多宿主的连接方式在网络运营商中间引入了商业竞争(如价格和服务竞争)，降低了客户访问网络服务的成本。以上2种技术的普遍应用改变了传统互联网的体系结构，提高了互联网的复杂度，带来以下主要变化：
1) 加速了路由表规模的增长，在路由表中同一目的网络前缀对应的路由表项急剧增长，同时吸引更多边缘AS加入互联网，增加了互联网中AS和网络前缀的规模；
2) 使得同一网络目的前缀对应的不同路径通过BGP路由宣告到互联网中，极大丰富了路径多样性，改善了互联网的路由性能。
2 域间路径特性分析模型本节介绍域间路径特性分析模型，首先引入BGP路由决策与宣告模型，了解互联网中所使用AS路径的生成原理，然后介绍利用图论进行路径多样性分析建模的方法。
2.1 BGP路由决策与宣告BGP路由选择包括路由导入、路由决策和路由宣告这3个基本环节。在路由导入处理中，BGP路由器根据ISP配置的本地策略，对接收到的路由进行处理，如果符合本地策略则修改相关路由属性后导入，例如ISP通过配置客户(customer)路由比供应商(provider)路由具有更高的局部属性(local preference)，从而影响BGP路由器选择前者； 如果违反本地策略则将路由丢弃。路由决策指的是BGP路由器在选择某个目的网络的路由时，根据优先级比较规则，选择唯一1条最优路由装入转发表中。路由宣告指的是BGP路由器按照本地策略决定是否宣告该路由到邻居BGP路由器中，且针对一个目的网络仅宣告一条最佳路由，而且AS在进行路由宣告时需要考虑商业关系的限制，即遵循2条指导原则[11, 12]： AS能宣告它自身和客户路由给供应商和对等服务商； AS能接收客户的所有路由，也会宣告所有的路由给客户。
与域内路由协议的“高效路由”目标不同，BGP路由最初设计主要考虑的是在互联网范围内具有较高的扩展性，为了实现这个目标，BGP使用路径矢量协议，而且主要考虑基于策略而非性能的路由。
2.2 路径多样性分析模型在互联网路由的相关研究中，图论是网络路由建模的一个基本工具。在本章进行的域间路由研究中，将一个网络建模为一个有向图G=(V，E，A)，它是由一个非空有限集合V、 有序对集合E和属性集合A组成，其中V称为图G的节点集，元素v∈V表示一个AS； E称为图G的边集，元素eij或e(vi，vj)∈E为V中元素的有序对构成的边，它是从vi到vj的一条弧； A称为图G中所有边对应的商业关系集，元素aij∈A为边e(vi，vj)构成的商业关系。给定G和2个节点s和t，若对任意k ∈[1，n－1]都有(vk，vk-1 )∈E,则p=(s=v1，v2，…，t=vn)是图G的一条从v1到vn的路径，记做p={ek,k+1| k=1，2，…，n－1}。为了更好地应用图论模型分析域间路径多样性，现给出以下定义：
定义1 图G中边eij的前后AS节点构成的商业关系分为3类： 客户-供应商商业关系(customer-provider)、 对等服务商业关系(peer-peer)和供应商-客户商业关系(provider-customer)，对应的aij分别为0、 1和2。
由定义1可知，路径上任意中间AS节点对应的前后边所构成的商业关系组合为9种，根据BGP路由宣告时遵循的商业关系限制，其中4种违反商业策略，5种满足商业策略[11, 12]。若此AS节点前后边构成的商业关系组合违反商业策略限制，则称此AS节点是违反商业策略的； 反之则称其为符合商业策略的。若一条路径中存在违反商业策略的中间AS节点，则称此路径是违反商业策略的； 反之则称其为符合商业策略的。部分符合商业策略的路径经过BGP的路由宣告后，会在互联网中传播，然后安装在BGP路由表中，这部分路径被称为符合选路策略，最后经过BGP的选路决策机制后，某个网络目的前缀对应的可达路径中只有一条会被选为默认路径，安装到转发表中负责转发流量。
3 数据集介绍本文使用的数据集来自美国Oregon大学高级网络中心的Routeviews项目，其主要目标是： 从多个不同自治系统的角度获取全球Internet的路由系统视图。Routeviews项目中的任意一台路由器使用外部边界网关协议(EBGP)对等会话与多个AS相连，将其收集到的路由信息存储起来； 这些路由器不通告任何信息给邻居以免对全球域间系统造成影响。Routeviews项目上采集的BGP路由表数据有2种格式： Cisco 格式和Zebra格式。本文中实验选用的BGP路由表来自route-views3.routeviews.org路由器，分别获取2007年5月—2012年5月期间，每月1日零时总共60张Cisco格式路由表，目前该路由器与19个AS建立了26个对等会话，各项性能比较稳定，捕获了当前Internet较为完整的域间路由视图。
4 实验设计与分析框架 4.1 总体设计框架本文分别从全局拓扑和局部拓扑这2种角度出发，研究域间路径的特性及其多样性： 从全局拓扑的角度出发，统计AS规模和满足选路策略条件下的AS路径长度； 从局部拓扑的角度出发，统计不同约束条件下(如满足商业策略等)的AS路径数目。基于BGP路由表中路由信息(如AS_PATH和网络前缀等)的处理分析来实现全局拓扑下AS规模和路径长度的统计。将BGP路由表转换为商业关系邻接表，通过构建局部拓扑的方法，实现局部拓扑下路径多样性的统计。
为了完成上述实验目标，本文开发了相应的算法。具体数据分析框架见图1，主要由1个数据处理模块和3个相关算法组成：
|
| 图 1 域间路径特性分析框架 |
1) 预处理与格式转换(pre-computation and format conversion,PCFC)。
负责将不同格式的BGP路由表文件转换成统一的数据分析格式，另外根据实验的不同需要，可以对数据进行预处理如增加特定处理字段等，根据需要可以进一步将BGP路由表文件转换成基于商业关系的互联网拓扑文件。
2) AS类型判定(AS type classification,ASTC)。
负责对AS进行分类处理并统计各个类型中AS的数量如存根AS、 核心AS和拥有供应商的穿越 AS的分布情况。
3) 路径多样性分析(path diversity analysis，PDA)。
利用局部拓扑构造算法统计局部拓扑中源节点－目的节点对(s，t)之间全部可达路径数目分布、满足商业策略路径数目分布、违反选路策略路径数目分布和违反商业策略路径数目分布。
4) 路径长度分析 (path quality analysis,PQA)。
统计和分析满足选路策略条件下默认AS路径和最短AS路径长度的分布以及随时间的变化趋势。
4.2 BGP路由属性介绍与提取BGP路由表是由路由表项组成的，每一条路由表项除了记录网络目的前缀以及下一跳AS外，还包含有若干属性。BGP属性是BGP进行路由决策和控制的重要信息，根据权限不同主要分为2大类： 公认属性和可选属性。在公认属性中，应用最为广泛的为AS_PATH属性，它是由一系列AS号组成，表示该路由经过的AS的有序集，也就是记录了一条完整的AS路径。当BGP发布者发布路由给内部邻居时，BGP不修改路由的AS_PATH属性。当BGP发布者发布路由给外部邻居时，本地系统应该把自己的AS号作为序列的最后一个元素加在序列的最后面。AS_PATH不仅可以用来作为路由选路的一种度量，而且可以作为一种手段来避免环路。本节通过提取路由表中所有路由表项对应的AS_PATH信息，抽取所含AS路径，实现AS路径长度和AS规模统计。
4.3 路径多样性分析框架由于底层网络的路径数目统计准确性较低且开销较大，为了减少网络拓扑规模，本文考虑通过构建互联网局部拓扑的方式，研究局部拓扑下的路径特性以及多样性丰富程度。基本研究思路包括4个步骤： 首先给定随机源—目的AS节点对(s，t)，s为所使用BGP路由表所属AS，t通过随机获取； 其次遍历BGP路由表，获取归属于t的网络目的前缀对应的所有路由表项，分析路由表项中包含的AS_PATH信息，提取(s，t)间所有可达(BGP路由表中出现的且满足BGP选路策略的)AS路径； 再次基于(s，t)及其可达AS路径，使用本文提出的局部拓扑构造算法ST，从全局网络拓扑中抽取局部拓扑； 最后基于获取的局部拓扑，使用本文提出的路径搜索算法MCBF计算路径多样性。
4.3.1 局部拓扑构造算法为了更好地构造局部拓扑，本文提出了局部拓扑构造算法ST。ST算法采用了一种启发式方法构造精简和高效的局部拓扑。ST算法的核心思路是： 基于BGP路由表，获取随机点对(s，t)之间的可达AS路径并构成路径集P，收集所有路径上AS节点的邻居信息，通过发现AS节点及其对应的邻居AS节点在互联网拓扑中的连接，实现局部拓扑的抽取。ST算法具体思路如下：
1) 基于BGP路由表，获取(s，t)之间的可达AS路径并构建路径集P。
2) 选取P中的一条路径并计算该路径所含的AS节点v，根据BGP路由表转换得到的基于商业关系的互联网拓扑文件，查找互联网拓扑中是否存在此v节点的某一邻居节点vn，且节点vn处于P中某一BGP路径上。若存在节点vn，则将节点vn、 边e(v，vn)及其商业关系属性加入到子拓扑中。
3) 遍历P中所有BGP路径，重复以上操作，完成基于(s，t)之间局部拓扑的抽取。
4.3.2 多路径计算与统计基于节4.3.1 构造的局部拓扑，为了有效计算(s，t)之间满足各种约束关系的路径数目，本节提出了多路径计算算法MCBF和统计算法SA。MCBF的核心思路是： 给定(s，t)的局部拓扑，采用广度优先搜索方法遍历局部拓扑，从而获取满足随机点对之间的全部路径。在获得所选随机点对的全部路径后，SA用来统计随机点对之间满足各个约束关系的路径的基本思想如下：
1) 给定一条路径，根据域间路径特性分析模型中讨论的商业关系限制，判断路径是否满足商业关系，若满足商业关系则将其标注为0。
2) 给定一条满足商业关系限制的路径，若此路径出现在BGP路由表中，则这条路径是满足BGP选路策略的，将其标注为1。
3) 其他路径标记为2。
4) 最后，对所有随机点对的全部路径进行分类计算和统计。
5 实验结果本文将具体给出AS类型与节点规模、路径多样性和路径长度这3部分的实验结果。
5.1 AS类型与规模根据2012年1月1日零时BGP路由表的数据，Internet中仅有16.5%的AS为穿越AS，83.5%的AS为节点度较小的末端AS，末端AS中有近50.0%的AS为多宿主AS。大量多宿主AS的存在使得BGP路由表中同一个前缀对应的路由数目急剧增多甚至翻倍，加剧了BGP路由表规模的膨胀，同时也带来了域间路由震荡等问题。图2给出了IPv4 AS规模随时间的变化趋势： 2007年5月之后AS年平均增长率为10.0%左右，年平均增长数量为3 200，相比2000年之前51.0%的年平均增长率有明显下降； 与此同时，末端多宿主AS的规模在2008年之前增长迅速，2008年之后增长放缓且低于AS总量的增长速率。
|
| 图 2 AS规模增长 |
实验中随机获取1 000个源节点-目的节点对(s，t)，针对(s，t)之间的路径进行分类并统计其分布。图3给出了(s，t)之间路径数目的分布情况： 1) 低于2 177条“违反选路策略”的路径的节点对占比为20.0%，即80.0%的节点对有2 177条以上的路径“违反选路策略”； 2) 低于4 909条“违反商业策略”的路径的节点对占比为20.0%，即80.0%的节点对有4 909条以上的路径“违反商业策略”。以上统计分析说明，尽管现今互联网底层具有丰富的路径多样性，然而大部分路径因不符合自治系统间商业策略或其选路策略，不能成为自治系统的候选路径。因此，未来诸如多路径路由等新型路由服务可以充分挖掘互联网蕴藏的丰富的路径多样性，从而改善路由可靠性和提供差异化路由服务。图4为局部拓扑中节点数目对路径多样性的影响： 在局部拓扑构造过程中，随着拓扑中发现节点数目的增多，拓扑内的路径多样性也变得越来越丰富，因此通过扩展节点的本地拓扑视野可以有效挖掘底层网络的路径多样性。
|
| 图 3 路径多样性与新颖性统计 |
|
| 图 4 节点数目对路径多样性的影响 |
基于BGP路由表，统计满足选路策略的AS路径长度分布以及变化趋势。图5给出了BGP路由表中平均默认AS路径长度、平均AS路径长度和平均最短AS路径长度随时间变化的趋势。数据显示： 这3种长度在2009年之前均呈现下降的趋势(如平均默认AS路径长度在2007年5月为3.64,2009年4月为3.09，减幅为15.1%)，而在2009年之后则较为稳定(如平均默认AS路径长度在2009年5月为3.19，2012年5月为3.20，最大波动幅度为5.70%)； 并且平均默认AS路径长度介于平均最短AS路径长度和平均AS路径长度之间，网络趋向于扁平化。图6给出了BGP路由表中平均默认AS路径长度的分布，研究结果发现： 互联网中91.7%的网络中间最多经过4跳便可以到达，其中使用最多的默认AS路径长度为3跳所占比例为49.8%； 默认AS路径是策略选择的结果而不是最短路径，20.0%的地址前缀并没有使用最短路径转发流量，路径存在进一步优化的可能。
|
| 图 5 平均默认路径长度变化 |
|
| 图 6 默认路径长度分布 |
本文基于BGP路由表，针对域间路径特性进行了相关的统计分析工作，主要分析结果显示： 现今IPv4网络蕴藏着丰富的路径多样性，80.0%的随机节点对之间具有7 300条以上的可达路径，然而BGP并没有充分挖掘底层网络的路径多样性，宣告并选择单一路径转发流量影响了路由可靠性并导致无法提供差异化路由服务； BGP路由表中 20.0%的默认路径并非最短路径，提高了网络拥塞和丢包等网络故障发生的概率，存在进一步路径优化的可能； 随着IPv4网络到IPv6网络的过渡，IPv4 AS呈现稳定的线性增长。以上的分析结果为评估互联网发展的相关工作提供了数据依据，同时可以有效支持未来互联网新型路由服务的研究。
| [1] | Huston G. Analyzing the Internet's BGP routing table[J]. The Internet Protocol Journal, 2001, 4(1):2-15. |
| [2] | Huston G. BGP table report[EB/OL].[2013-01-15]. http://bgp.potaroo.net. |
| [3] | Smith P. Routing summaries at APNIC[EB/OL].[2013-01-15]. http://www.apnic.net/stats/bgp. |
| [4] | The University of Oregon's Advanced Network Technology Center. University of Oregon Route Views Project.[EB/OL].[2013-01-15]. http://www.routeviews.org/. |
| [5] | Huston G. AS6447 BGP routing table analysis reports[EB/OL].[2009-11-09]. http://bgp.potaroo.net/as6447/. |
| [6] | Nayak K,Mckeman D. Measuring provider path diversity from traceroute data:Work in progress[EB/OL].[2009-11-09]. . |
| [7] | Teileira R. Marzullo K, Savage S, et al. In search of path diversity in ISP networks[C]//proc of ACM SIGCOMM 2003. New York, NY, USA:ACM, 2003:313-318. |
| [8] | Teileira R, Marzullo K, Savage S, et al. Characterizing and measuring path diversity of Internet topologies[C]//Proc of ACM SIGMETRICS 2003. New York, NY, USA:ACM, 2003:304-305. |
| [9] | Zheng H, Lua E, Pias M, et al. Internet routing policies and round-trip times[C]//Proc of 6th International Workshop on Passive and Active Network Measurement. Boston, MA, USA, 2005:236-250. |
| [10] | Wang G, Zhang B. Towards network triangle inequality violation aware distributed systems[C]//Proc of the ACM/IMC Conference. San Diego, CA, USA:ACM, 2007:175-188. |
| [11] | Huston G. Interconnection, peering andsettlements[J]. Internet Protocol Journal, 1999, 2(2):2-23. |
| [12] | Baake P, Wichmann T. On the economics of internet peering[J].Netnomics, 1998, 1(1):89-105. |