关键字:Internet路由系统；边界网关协议；可扩展性

英文摘要:Rapid improvement of the Internet has imposed significant pressure on its routing scalability. However, in order to maintain this rapid improvement in a continuous and stable way, some solutions for the scalability problem in routing system have been proposed by academia and the Internet technology industry. In this paper, we first introduce the problem of routing scalability faced by the Internet. Then we analyze the root causes of the problem, and introduce some of the abovementioned solutions. Finally, we conclude on the scalability problem of Internet routing and the requirements of the future Internet routing system.

英文关键字:Internet routing system; BGP; scalability

基金项目：国家重点基础研究发展规划 (“973”计划)课题 (2009CB320504)；国家高技术研究发展计划资助(“863”计划)课题(2007AA01Z206, 2009AA01Z210)

Internet起源于美国国防部高级研究计划署资助开发的阿帕网(ARPANET)，最初它只是分布于美国4所著名大学的4个节点互联组成的数据分组交换网，网速56 kbit/s，但在后续的40多年中，Internet得到了快速发展和迅速普及，根据Internet系统协会2009年7月发布的数据显示，Internet已成为超过6亿个节点，核心节点系统处理能力达到每秒太比特级的全球超级信息系统。

随着Internet规模的不断扩大，全球边界网关协议(BGP)路由表呈现出“超线性”增长的态势，数据显示全球BGP转发信息表(FIB)已从20世纪90年代末期的5万余条爆增至2010年的30万余条，如图1所示。有专家预测在未来15年内可能会增至200万条，2050年甚至可达到1 000万条[1]，路由表的“超线性”增长以及由其所引出的一系列问题将导致Internet体系结构和路由机制的扩展性面临巨大的挑战[2]。

全球BGP路由表的“超线性”增长需要BGP路由器采用容量更大、查询速度更快的存储器(动态随机存取存储器、静态随机存取存储器、三重内容可寻址存储器)保存路由信息表(RIB)和FIB；由于每条路由表项的维护包括新建、撤销、更新等都需要发布BGP通告，路由表的增长增加了BGP通告发布的数量和频率，使更多、更频繁的BGP路由更新注入Internet核心，从而形成了Internet网络中的“路由更新搅动”，导致路由的不稳定、路由器计算FIB的负担加重以及路由收敛时间的延长；另外，路由表查询速度要求的提高和计算负荷的增大导致更大的功耗，因此需要更大型的供电系统和散热系统。全球BGP路由表的“超线性”增长以及由此引发的一些列问题无疑增加了网络的运营成本，影响Internet的发展。因此，路由扩展性问题引起了学术界和工业界的广泛关注。

1 影响互联网路由扩展性因素

2006年10月，鉴于由于互联网规模不断扩大带来的一系列问题，互联网架构委员会(IAB)在荷兰阿姆斯特丹就Internet路由技术举行了路由和寻址专题讨论会，并在会后形成了分析和研究互联网路由扩展性问题的报告RFC4984。研究人员普遍认为导致互联网路由扩展性问题的主要因素是IP地址的语义重载、站点多归属、流量工程、提供商独立地址、反前缀劫持。

1.1 IP地址的语义重载

目前的IP地址具有双重语义，一方面它是表示主机身份的端点标志符，另一方面它又是表示网络拓扑位置的定位符。端点标志符原则上应该与网络拓扑独立，在网络或主机改变拓扑位置的时候，端点标志符应该保持不变，但目前的IP地址却担负了这种目标并不一致的双重角色。IP地址的语义重载是站点多归属、流量工程、PI地址导致路由系统出现扩展问题的根源。专家认为未来主机标志与网络位置标志的分离对路由系统的可扩展性来说十分必要。

1.2 站点多归属

具有连接到多个服务提供商能力的站点被称为多归属站点[3]。站点多归属能使站点在某一个ISP故障的时候为网络提供其他可用连接，增强网络的可靠性和可恢复性。目前至少有60%的接入服务器(AS)是多归属的，这个数字还在不断上升[4]。为了保证数据分组经过多个ISP仍能到达正确的站点，为多归属站点提供Internet服务的所有服务提供商都必须向外单独通告该站点的IP地址前缀，因此站点多归属破坏了地址的可聚合性，导致细小的地址块注入到Internet核心路由表中，它是导致目前路由扩展性问题的主要原因之一。

1.3 流量工程

流量工程就是要实现运营网络的性能优化，它通过对Internet流量的测量、建模、规划和控制等科学原理和技术方法达到实现特定性能的目的，流量工程的目的是在优化网络资源利用率和流量性能的同时提供可靠高效的网络运营[5]。流量工程能帮助ISP降低运营成本(让流量通过较低成本的路径)、优化部署策略(较高优先级的流量通过较好质量的路径)、保证负载均衡，目前在ISP处得到广泛应用。但是目前的流量工程主要靠通过解聚合IP地址前缀、向全球路由系统注入更详细(更长)的地址前缀、利用更多、更频繁的BGP更新达到对流量的控制，因而在优化网络性能的同时也会导致全球BGP路由表的相应膨胀。

1.4 提供商独立地址PI的分配

站点的IP地址不由ISP分配，而是直接向区域Internet注册机构(RIR)申请获得，这类IP地址与ISP无关，被称为提供商独立(PI)地址。PI地址可以帮助用户在更换ISP时避免重新编址，但由于PI地址不由ISP分配，因此ISP也无法将此地址块聚合，只能向外单独通告此网络的详细地址前缀。因此PI地址也破坏了地址的可聚合性，使越来越多的用户网络地址注入Internet核心路由表。

1.5 反前缀劫持

Internet是一个开放的分布式系统，其路由的通告、更新和撤销等都是由各AS决定的。一些AS可能出于恶意或由于网络管理员的错误配置，向外通告不属于自己的地址前缀，导致目的为这些地址的数据分组被错误地引导到该AS而无法到达原本的目的地，这种现象被称为前缀劫持。为了抵御前缀劫持的攻击，目前AS一般采用为较重要的服务如域名服务器(DNS)向外通告尽可能长的前缀(至少24位)，所以反前缀劫持技术的使用也导致了全球路由表的增长[6]。

众所周知，目前的路由技术都是基于拓扑的，拓扑聚合是目前保证路由系统扩展性的唯一实际方法。但上述情况在不同程度上都破坏了Internet地址的可聚合性，导致了全球BGP路由表的快速膨胀，引发了Internet路由扩展性的问题，影响了Internet的扩展性，最终将影响Internet的持续发展。Internet路由扩展性成为下一代Internet必须解决的首要问题之一。

2 Internet路由扩展性研究状况

 Internet路由扩展性的研究工作得到了互联网技术领域学术界和工业界的高度关注，国际上的一些著名研究机构在该方向上进行了大量的研究并相继提出了一些初步方案，比较著名的方案有：加州大学洛杉矶分校提出的eFIT[7]、麻省理工大学提出的LANI[8]、加州大学伯克利分校提出的HLP[9]、伊利诺伊大学提出的ROFL、康奈尔大学提出的核心路由器完整覆盖(CRIO)和虚拟聚合(VA)、美国波特兰第一基础研究院提出的IVIP、思科公司提出的LISP、爱立信公司提出的HIP和Christian Vogt提出的Six/One以及Patrick Frejborg提出的HIPv4等。此外，也有一些学者将关注点转移到其他一些相关研究领域上，例如压缩路由，希望通过其他研究领域的一些研究成果推动路由系统可扩展问题的解决。Internet研究任务组(IRTF)为此也建立了路由研究工作组(RRG)进行路由扩展性问题的研究，eFIT、LISP、IVIP、Six/One都成为了RRG的提案，HIPv4等一些方案在RRG中还处于提交讨论阶段。

目前，解决互联网路由扩展性的方案基于拓扑聚合的较多，大致可分为两种类型：一种是虚拟聚合类，这类方案的主要思想是保留BGP路由系统不变，在其上搭建覆盖网，将比较细小的前缀的路由表项从BGP路由系统中提取出来，存储在覆盖网上，如CRIO、VA；另一种类型是基于身份标志和位置标志分离的思想，将IP地址的主机身份标志与网络位置标志分离，此类方案又可细分为主机驱动型(例如HIP)和路由器驱动型(例如LISP、eFIT、IVIP、Six/One)。另外，LANI将命名空间分为多层例如主机标志层、路由层、服务标志层；HLP是一个代替BGP的新的域间路由协议；ROFL的路由基于扁平结构的标志符；HIPv4通过在IPv4地址空间中引入了层次结构保证路由体系结构的扩展性。下面就这些方案中的几种主要技术进行分析介绍。