互联网路由扩展性研究状况分析

基金项目：国家重点基础研究发展规划 (“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地址空间中引入了层次结构保证路由体系结构的扩展性。下面就这些方案中的几种主要技术进行分析介绍。

2.1 虚拟聚合
    这类方案一般是通过将拓扑上不可聚合的连续地址前缀虚拟聚合成虚拟前缀(VP)，达到减小BGP路由表规模的目的。VP是一个覆盖了地址空间较大部分的超级前缀，是对多个子前缀(目前传统网络的网络前缀)的虚拟聚合。聚合代理是针对某个VP来说的，它负责存储这个VP所覆盖的所有子前缀及每个子前缀对应的隧道出口路由器的地址，实现虚拟聚合功能。虚拟聚合类方案虽然减小了路由表，但却存在拉长转发路径的问题。

    CRIO是较早提出虚拟前缀的一种方案，聚合代理在CRIO中被称为VP-TS，它作为隧道起点(TS)存储了对应VP中的每个子前缀的映射信息(子前缀以及对应的TE)，并负责将数据分组通过隧道传送到隧道终点(TE)，即此子前缀所属提供商的边缘路由器(PE)并向管理域内的其他BGP路由器通告这个VP。

    CRIO的数据分组转发过程如图2所示，用户网络A中的一台主机欲发送数据分组给用户网络B中的一台主机，其中路由器PE3是VP 24.0.0.0/8的VP-TS，它将通过隧道技术虚拟聚合24.0.0.0/8覆盖的所有子前缀，例如24.1.1.0/24。入口路由器PE1、出口路由器PE2分别属于不同的AS，整个转发流程如下：

• PE3向PE1发送VP的BGP通告，PE1的路由表添加一条路由信息(24.0.0.0/8，PE3)；
• CE1向PE1发送一个24.1.1.0/24的数据分组；
• PE1在路由表中未查询到24.1.1.0/24的路由信息，但查到路由信息(24.0.0.0/8，PE3)于是将该数据分组转发给PE3；
• PE3存有24.1.1.0/24的映射信息(24.1.1.0/24，PE2)，根据此映射信息，PE3将数据分组通过隧道发往TE PE2；
• PE2知道要通过CE2才能到达24.1.1.0/24网络，因此将数据分组去掉封装报头后转发给CE2。

    整个转发路径为CE1→PE1→PE3→PE2→CE2，但若PE1存有24.1.1.0/24的映射消息，路径为CE1→PE1→PE2→CE2。由此可见，CRIO在实现地址聚合的同时却将分组的转发路径拉长了。

    实施CRIO方案时，BGP路由器只需要存储到Internet的入网点(POP)的路由以及VP-TS的路由。全球的大型提供商共有几千个POP，如果VP被定为/8，整个地址空间共有256个VP，这样传统路由器的路由表(RIB)规模就可以从105量级减少到103量级，大大减少了BGP路由的计算量和路由表的大小；同时，路由器中存储的路由指向终点(大型提供商的POP)也会非常的稳定，从而减少了BGP信息的更新频率。文献11对CRIO进行了仿真试验(如图3所示)：采用在所有的ISP上随机部署VP，或在每个ISP内部署所有的VP，或所有的ISP内部路由都是最短路径的3种不同VP部署策略，考察转发表大小与路径长度的关系，结果表明在平均路径长度增加很少的情况下，第一个策略使部署了CRIO的FIB的规模减小一个数量级，其他两个方案则使FIB的规模减小到未部署CRIO的FIB的1/5左右，BGP RIB的规模则可以减少近两个数量级。

    CRIO虽然能够缓解目前路由系统所面临的路由表膨胀压力，但是它尚存一些待解决的问题，当多个ISP同时部署VP-TS时，如何解决转发路径可能被多次拉长的问题目前尚不清楚；CRIO使数据分组的转发路径拉长，增加了数据分组在路由器内的处理时间，从而增加了传送时延；由于CRIO使用隧道技术，封装也会导致带宽、CPU资源的开销增加；VP-TS集中了所有发往被聚合的子前缀的流量，很容易成为网络“瓶颈”；此外，CRIO缺乏对移动性的支持；以上这些问题都有待相关研究人员作进一步的研究。

    VA是IETF GROW工作组的提案之一，用于解决当前路由扩展性。VA与CRIO一样，使用隧道技术虚拟聚合分散的子前缀成VP。在VA中，聚合代理被称为汇聚点路由器(APR)。VA的部署范围仅限于ISP内，所以作为隧道起点的APR存储VP内的每个子前缀及对应的远端AS的边界路由器(ASBR)地址，并负责将数据分组通过隧道传送到隧道终点，即远端AS的边界路由器(ASBR)地址，如图4所示。VA保持BGP路由器中的RIB不变，只是阻止RIB中的一些表项加载到BGP路由器的FIB中，这是VA与CRIO的一个不同之处。VA的隧道并不跨越多ISP，解封装数据分组的任务由本地ISP的边缘路由器完成，无需与其他ISP进行协作，这是VA与CRIO的另一区别。由于VA与CRIO的基本思路相似，所以也存在与CRIO一样的问题。此外，由于VA只压缩了路由器中FIB规模，RIB的快速增长仍未得到解决。

2.2 标志和位置标志分离

2.2.1 主机驱动型
    主机驱动型是指在主机协议栈的网络层和传输层之间加入主机标志层的分离类型，主机标志负责标志主机，网络地址负责数据分组的寻址和传送，应用连接不再与IP地址绑定，而是与主机标志绑定，网络层IP地址只作为网络层使用的位置标志，用于数据分组的路由转发。IP地址的变更对传输层以上透明，从而IP地址的改变可以不中断已经建立的应用连接，达到支持主机移动性和多归属的目的。HIP是主机驱动型的典型方案，主要要解决主机的安全和移动性问题，如果所有的IP网络都部属HIP，所有的主机都使用全新的名字空间作为主机标志，IP地址仅用于路由，IP地址就可完全按照网络拓扑分配，IP地址恢复可聚合性，从而彻底解决路由扩展性的问题。

    HIP在网络层和传输层中间插入主机标志层(HIL)，实现了身份与位置标志的分离，引入主机标志层后的协议体系结构如图5右侧协议栈所示。HIP引进一个新的加密的命名空间，该命名空间引入了3个新的标志符：主机标志符(HI)、主机标志标签(HIT)和局部标志符(LSI)。主机标志符唯一地标志了每台连接到Internet上的主机，每个主机可以有多个HI。HI可以用不对称加密算法中公/私密钥对的公钥来表示，由于不同的加密算法所拥有的密钥长度不一样，因此，在实际使用时，通常用128位定长的HIT来代替HI标志主机身份，HIT是对HI的某种哈希变换，与IPv6地址等长，在应用程序中使用非常方便，同时为了和现有的IPv4地址兼容，HIP协议还定义了LSI，作为局部系统中使用的主机标志符。HIP协议的基本交换是一个使用公钥作为主机标志并建立HIP基本交换加密的4次握手过程，它可以保证通信的安全性。

    在HIP体系结构中的两台主机在进行通信时，发起方首先要通过查询DNS和映射系统获得通信对端的标志和位置标志集，然后两台主机再通过HIP基本交换建立安全关联，开始双向数据传输。

    由此可见，在HIP体系结构中由于主机标志层的引入，使得原来传输层和网络层之间的紧耦合得以解耦，应用程序只看到一对不变的源、目的HIT，移动与多宿主对应用程序来说是透明的。此外，HIP通过引入汇聚服务器(RVS)用来维护移动节点的当前位置信息，保证节点移动能够不中断通信。

    HIP也存在一定的缺陷：

• HIP不支持组播；
• 需要大量部署RVS以解决主机移动问题，如果利用现有的DNS，需增强动态更新的处理能力；
• HIP主机之间的通信需要对数据包进行加密和解密，增加CPU的额外负担；
• HIP的主机标志采用扁平结构，不具备合理的商业模型；
• HIP的部属需要对主机协议栈进行修改，对Internet影响较大。

2.2.2 路由器驱动型
    路由器驱动型方案将整个Internet划分为边缘网络与核心网络，边缘网络内部使用PI地址，既作为主机的标志符也用于内部的路由寻址；核心网络使用PA地址，用于核心网络的路由；边界路由器将数据分组中的目的PI地址改为核心网络的PA地址，实现边缘网络与核心网络分离。路由器驱动型方案使用PI地址前缀作为网络标志符，PA地址作为该网络接入Internet的拓扑位置，从而分离了边缘网络的IP地址前缀的双重语义，保证了Internet的路由扩展性。

    LISP是这类方案中的一种典型方案，LISP将地址空间分为端点标志(EID)和路由位置符(RLOC)。EID可以唯一地标志边缘网络内的主机，在边缘网络内既用于路由也用于主机标志，EID的前缀作为边缘网络的标志符。RLOC标志网络位置，在核心网络中用于路由。LISP还定义了入口隧道路由器(ITR)和出口隧道路由器(ETR)。

    LISP将边缘网络内外主机间的通信路径分成图6所示的3个部分：边缘网络内从源主机到ITR(绿色)的路径部分，使用EID路由；从ITR到ETR的隧道路径部分(红色)，使用RLOC路由；从ETR到目的主机的路径部分，使用EID路由(紫色)。下面就以主机A向主机B发送数据分组的过程为例说明LISP的主要原理：

• 数据分组首先被转发到ITR(路由器E)；
• ITR在本地映射缓存中查找目的EID到RLOC的映射，如果查找到对应的RLOC，则为数据分组添加一个外部LISP包头，该LISP包头中包括ETR和ITR的RLOC地址，将封装好的数据分组发送到核心网的边界路由器J；
• 核心网利用RLOC地址进行路由，将数据分组发送到ETR(即路由器I)；
• ETR接收到数据分组后进行解封装，再将解封装后的数据分组通过目的远端标志进行路由并发送到目的主机B。

    如果ITR没有找到所需的映射信息，则需要先向映射系统发送请求映射信息的消息(映射请求、数据探针)。映射系统是LISP系统的一个重要组件，工作在路由系统的控制平面，负责处理ITR没存所需映射信息的情况。LISP目前已提出了4类映射系统，分别为：内容分发覆盖网络服务(CONS)、非新颖的EID到RLOC的映射数据库(NERD)、穿越合作系统的EID映射多播(EMACS)、可替代的逻辑拓扑(ALT)。当前的LISP原型系统采用的是ALT机制。

    LISP-ALT由ALT路由器组成，通过通用路由协议封装(GRE)隧道相互连接，在BGP路由系统之上组成一个树形拓扑结构的逻辑覆盖网络，覆盖网络负责将映射请求信息和数据探针(数据探针的内部地址EID和外部地址RLOC相同)转发至存有被请求的EID到RLOC映射信息的ETR，ALT路由器之间使用BGP协议通告EID前缀的可达性信息，这些EID前缀的可达性信息在树形拓扑结构的覆盖网络中逐层汇聚，如图7所示。

    LISP将边缘网络与核心网络分离，整个核心网的路由器使用PA地址，实现了核心网络的拓扑聚合，从而减小了DFZ中的路由表规模，并能够支持可扩展的站点多归属和流量工程；边缘网络由于使用EID作为地址空间，因此在更换ISP时无需重新编址。LISP方案不必修改核心路由器，仅要对边缘路由器作一定的修改，对目前已有的网络基础设施改动较少。当然，LISP也存在一些缺点，由于采用隧道机制，存在最大传输单元(MTU)问题，且需要消耗一定的带宽；LISP对移动性支持有限；未来Internet的需求之一是移动性，对移动性的有限支持是LISP亟待解决的重要问题之一；LISP引入了映射系统，方案的部署开销仍需进一步评估。

3 结束语
    Internet路由扩展性问题是目前互联网技术领域一个需要解决的重要问题，与IPv4相比，IPv6具有更大的地址空间，但由于IPv6地址的结构、分配与IPv4并无区别，随着IPv4地址的枯竭，IPv6的部署进程在不断加快，Internet路由扩展性问题的解决将更加迫切。本文在对影响Internet路由扩展性的若干因素进行分析的基础上，重点介绍了互联网技术领域学术界和工业界提出的几种典型解决方案，这些方案虽然在一定程度上部分解决了路由扩展性的问题，但是仍然存在进一步完善和改进的空间，Internet路由扩展性的研究已是当今互联网技术领域最活跃的一个研究内容。可以预见，为了Internet能够持续、稳定、快速的发展，未来的互联网路由系统应该具有更好的扩展性，能够可扩展地支持多归属、流量工程、移动性，并支持安全性，能够简化重新编址，具备向后兼容性，支持IPv4和IPv6，并能够保证路由质量，支持互联网的增量部署。

4 参考文献
[1] MEYER D, ZHANG L, FALL K, et al. Report from the IAB workshop on routing and addressing[R]. IETF RFC 4984. 2007.
[2] HUSTON G. Analyzing the Internet’s BGP routing table[J]. The Internet Protocol Journal, 2001,4(1):2-15.
[3] ABLEY J, LINDQVIST K, DAVIES E, et al. IPv4 multihoming practices and limitations[R]. IETF RFC 4116. 2005.
[4] LIU Xiaomei, XIAO Li. A survey of multihoming technology in stub networks: Current research and open issues[J]. IEEE Network Magazine, 2007, 21(3):32-40.
[5] AWDUCHE D, MALCOLM J, AGOGBUA J, et al. Requirements for traffic engineering over MPLS[R]. IETF RFC 2702.1999.
[6] MENTH M, HARTMANN M, TRAN-GIG P, et al. Future Internet routing: Motivation and design issues[J].Information Technology, 2008, 50(6):358-366.
[7] MASSEY D, WANG Lan, ZHANG Beichuan, et al. A scalable routing system design for future Internet[C]// Proceedings of the ACM SIGCOMM Workshop on Large Scale Attack Defense (LSAD '07), Aug 27-31, 2007, Kyoto, Japan. New York, NY,USA: ACM, 2007:790-796.
[8] BALAKRISHNAN H, LAKSHMINARAYANAN K, RATNASAMY S, et al. A layered naming architecture for the Internet[C]// Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM’04), Aug 30 Sep 3, 2004, Portland, OR, USA. New York, NY,USA: ACM, 2004:343-352 .
[9] SUBRAMANIAN L, CAESAR M, EE C T, et al. HLP: A next generation inter - domain routing protocol [C]//Proceedings of Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM’05), Aug 22-26, 2005, Philadelphia, PA, USA. New York, NY,USA: ACM, 2005:13-14.

收稿日期：2010-01-29

[摘要] Internet的快速发展对路由扩展性造成了巨大的压力。为了Internet能够持续、稳定、快速的发展，互联网技术领域学术界和工业界提出了一些针对Internet的路由扩展性的解决方案。文章基于Internet面临的路由扩展性问题，分析导致问题的原因；在对影响Internet路由扩展性的若干因素进行分析的基础上，重点介绍互联网技术领域学术界和工业界提出的一些典型解决方案；在对Internet路由扩展性问题行总结的基础上，提出未来Internet路由系统的需求。

[关键词] Internet路由系统；边界网关协议；可扩展性

[Abstract] 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.

[Keywords] Internet routing system; BGP; scalability