互联网路由扩展性现状分析

1、互联网路由扩展性现状分析来源：IT168 HYPERLINK 2010-07-15 10:22:35Internet起源于美国国防部高级研究计划署资助开发的阿帕网(ARPANET),最初 它只是分布于美国4所著名大学的4个节点互联组成的数据分组交换网，网速 56 kbit/s，但在后续的40多年中，Internet得到了快速发展和迅速普及，根 据Internet系统协会2009年7月发布的数据显示，Internet已成为超过6亿 个节点，核心节点系统处理能力达到每秒太比特级的全球超级信息系统。随着Internet规模的不断扩大，全球边界网关协议(BGP)路由表呈现出“超线性” 增长的态势，数据

2、显示全球BGP转发信息表(FIB)已从20世纪90年代末期的5 万余条爆增至2010年的30万余条，如图1所示。有专家预测在未来15年内可 能会增至200万条，2050年甚至可达到1 000万条1，路由表的“超线性”增 长以及由其所引出的一系列问题将导致Internet体系结构和路由机制的扩展性 面临巨大的挑战2。全球BGP路由表的“超线性”增长需要BGP路由器采用容量更大、查询速度更快 的存储器(动态随机存取存储器、静态随机存取存储器、三重内容可寻址存储器) 保存路由信息表(RIB)和FIB;由于每条路由表项的维护包括新建、撤销、更新等 都需要发布BGP通告，路由表的增长增加了 BGP通告发

3、布的数量和频率，使更多、 更频繁的BGP路由更新注入Internet核心，从而形成了 Internet网络中的“路 由更新搅动”，导致路由的不稳定、路由器计算FIB的负担加重以及路由收敛时 间的延长;另外，路由表查询速度要求的提高和计算负荷的增大导致更大的功耗， 因此需要更大型的供电系统和散热系统。全球BGP路由表的“超线性”增长以及 由此引发的一些列问题无疑增加了网络的运营成本，影响Internet的发展。因 此，路由扩展性问题引起了学术界和工业界的广泛关注。1影响互联网路由扩展性因素2006年10月，鉴于由于互联网规模不断扩大带来的一系列问题，互联网架构委 员会(IAB)在荷兰阿姆斯特丹就

4、Internet路由技术举行了路由和寻址专题讨论 会，并在会后形成了分析和研究互联网路由扩展性问题的报告RFC4984。研究人 员普遍认为导致互联网路由扩展性问题的主要因素是IP地址的语义重载、站点 多归属、流量工程、提供商独立地址、反前缀劫持。1.1 IP地址的语义重载目前的IP地址具有双重语义，一方面它是表示主机身份的端点标志符，另一方 面它又是表示网络拓扑位置的定位符。端点标志符原则上应该与网络拓扑独立， 在网络或主机改变拓扑位置的时候，端点标志符应该保持不变，但目前的IP地 址却担负了这种目标并不一致的双重角色。IP地址的语义重载是站点多归属、流量工程、PI地址导致路由系统出现扩展问题

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

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

7、.4提供商独立地址PI的分配站点的IP地址不由ISP分配，而是直接向区域Internet注册机构(RIR)申请获 得，这类IP地址与ISP无关，被称为提供商独立(PI)地址。PI地址可以帮助用 户在更换ISP时避免重新编址，但由于PI地址不由ISP分配，因此ISP也无法 将此地址块聚合，只能向外单独通告此网络的详细地址前缀。因此PI地址也破 坏了地址的可聚合性，使越来越多的用户网络地址注入Internet核心路由表。1.5反前缀劫持Internet是一个开放的分布式系统，其路由的通告、更新和撤销等都是由各AS 决定的。一些AS可能出于恶意或由于网络管理员的错误配置，向外通告不属于 自己的地址前

8、缀，导致目的为这些地址的数据分组被错误地引导到该AS而无法 到达原本的目的地，这种现象被称为前缀劫持。为了抵御前缀劫持的攻击，目前 AS 一般采用为较重要的服务如域名服务器(DNS)向外通告尽可能长的前缀(至少 24位)，所以反前缀劫持技术的使用也导致了全球路由表的增长6。众所周知，目前的路由技术都是基于拓扑的，拓扑聚合是目前保证路由系统扩展 性的唯一实际方法。但上述情况在不同程度上都破坏了 Internet地址的可聚合 性，导致了全球BGP路由表的快速膨胀，引发了 Internet路由扩展性的问题， 影响了 Internet的扩展性，最终将影响Internet的持续发展。Internet路由

9、 扩展性成为下一代Internet必须解决的首要问题之一。2 Internet路由扩展性研究状况Internet路由扩展性的研究工作得到了互联网技术领域学术界和工业界的高度 关注，国际上的一些著名研究机构在该方向上进行了大量的研究并相继提出了一 些初步方案，比较著名的方案有：加州大学洛杉矶分校提出的eFIT7、麻省理 工大学提出的LANI8、加州大学伯克利分校提出的HLP9、伊利诺伊大学提出 的ROFL、康奈尔大学提出的核心路由器完整覆盖(CRIO)和虚拟聚合(VA)、美国 波特兰第一基础研究院提出的IVIP、思科公司提出的LISP、爱立信公司提出的 HIP 和 Christian Vogt

10、提出的 Six/One 以及 Patrick Frejborg 提出的 HIPv4 等。 此外，也有一些学者将关注点转移到其他一些相关研究领域上，例如压缩路由， 希望通过其他研究领域的一些研究成果推动路由系统可扩展问题的解决。Internet研究任务组(IRTF)为此也建立了路由研究工作组(RRG)进行路由扩展 性问题的研究，eFIT、LISP、IVIP、Six/One都成为了 RRG的提案，HIPv4等一 些方案在RRG中还处于提交讨论阶段。目前，解决互联网路由扩展性的方案基于拓扑聚合的较多，大致可分为两种类型: 一种是虚拟聚合类，这类方案的主要思想是保留BGP路由系统不变，在其上搭建 覆盖

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

12、过将拓扑上不可聚合的连续地址前缀虚拟聚合成虚拟前缀 (VP)，达到减小BGP路由表规模的目的。VP是一个覆盖了地址空间较大部分的 超级前缀，是对多个子前缀(目前传统网络的网络前缀)的虚拟聚合。聚合代理是 针对某个VP来说的，它负责存储这个VP所覆盖的所有子前缀及每个子前缀对应 的隧道出口路由器的地址，实现虚拟聚合功能。虚拟聚合类方案虽然减小了路由 表，但却存在拉长转发路径的问题。CRIO是较早提出虚拟前缀的一种方案，聚合代理在CRIO中被称为VP-TS，它作 为隧道起点(TS)存储了对应VP中的每个子前缀的映射信息(子前缀以及对应的 TE)，并负责将数据分组通过隧道传送到隧道终点(TE)，即此

13、子前缀所属提供商 的边缘路由器(PE)并向管理域内的其他BGP路由器通告这个VP。CRIO的数据分组转发过程如图2所示，用户网络A中的一台主机欲发送数据分 组给用户网络B中的一台主机，其中路由器PE3是VP /8的VP-TS，它 将通过隧道技术虚拟聚合/8覆盖的所有子前缀，例如/24。入口路由器PE1、出口路由器PE2分别属于不同的AS，整个转发流程如下：PE3向PE1发送VP的BGP通告，PE1的路由表添加一条路由信息(/8， PE3);CE1向PE1发送一个/24的数据分组；PE1在路由表中未查询到/24的路由信息，但查到路由信息(/8, PE3)于是将该数据分组转发给PE3;PE3存有/

14、24的映射信息(/24，PE2)，根据此映射信息，PE3 将数据分组通过隧道发往TE PE2;PE2知道要通过CE2才能到达/24网络，因此将数据分组去掉封装报头 后转发给CE2。整个转发路径为CE1-PE1-PE3-PE2-CE2，但若PE1存有/24的映射 消息，路径为CE1fPE1fPE2fCE2。由此可见，CRIO在实现地址聚合的同时却 将分组的转发路径拉长了。实施CRIO方案时，BGP路由器只需要存储到Internet的入网点(POP)的路由以 及VP-TS的路由。全球的大型提供商共有几千个POP，如果VP被定为/8，整个 地址空间共有256个VP，这样传统路由器的路由表(RIB)规

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

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

17、隧道技术虚拟聚合分散的子前缀成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的基本思路

18、相似，所以也存在与CRIO 一样的问题。此外，由于VA只压缩了路由器中FIB规模，RIB的快速增长仍未 得到解决。2.2标志和位置标志分离2.2.1主机驱动型主机驱动型是指在主机协议栈的网络层和传输层之间加入主机标志层的分离类 型，主机标志负责标志主机，网络地址负责数据分组的寻址和传送，应用连接不 再与IP地址绑定，而是与主机标志绑定，网络层IP地址只作为网络层使用的位 置标志，用于数据分组的路由转发。IP地址的变更对传输层以上透明，从而IP 地址的改变可以不中断已经建立的应用连接，达到支持主机移动性和多归属的目 的。HIP是主机驱动型的典型方案，主要要解决主机的安全和移动性问题，如果 所有的

19、IP网络都部属HIP，所有的主机都使用全新的名字空间作为主机标志， IP地址仅用于路由，IP地址就可完全按照网络拓扑分配，IP地址恢复可聚合性， 从而彻底解决路由扩展性的问题。HIP在网络层和传输层中间插入主机标志层(HIL)，实现了身份与位置标志的分 离，引入主机标志层后的协议体系结构如图5右侧协议栈所示。HIP引进一个新 的加密的命名空间，该命名空间引入了 3个新的标志符：主机标志符(HI)、主机 标志标签(HIT)和局部标志符(LSI)。主机标志符唯一地标志了每台连接到 Internet上的主机，每个主机可以有多个HI。HI可以用不对称加密算法中公/ 私密钥对的公钥来表示，由于不同的加密

20、算法所拥有的密钥长度不一样，因此， 在实际使用时，通常用128位定长的HIT来代替HI标志主机身份，HIT是对HI 的某种哈希变换，与IPv6地址等长，在应用程序中使用非常方便，同时为了和 现有的IPv4地址兼容，HIP协议还定义了 LSI，作为局部系统中使用的主机标志 符。HIP协议的基本交换是一个使用公钥作为主机标志并建立HIP基本交换加密 的4次握手过程，它可以保证通信的安全性。在HIP体系结构中的两台主机在进行通信时，发起方首先要通过查询DNS和映射 系统获得通信对端的标志和位置标志集，然后两台主机再通过HIP基本交换建立 安全关联，开始双向数据传输。由此可见，在HIP体系结构中由于主

21、机标志层的引入，使得原来传输层和网络层 之间的紧耦合得以解耦，应用程序只看到一对不变的源、目的HIT，移动与多宿 主对应用程序来说是透明的。此外，HIP通过引入汇聚服务器(RVS)用来维护移 动节点的当前位置信息，保证节点移动能够不中断通信。HIP也存在一定的缺陷:HIP不支持组播;需要大量部署RVS以解决主机移动问题，如果利用现有的DNS，需增强动态更新 的处理能力；HIP主机之间的通信需要对数据包进行加密和解密，增加CPU的额外负担；HIP的主机标志采用扁平结构，不具备合理的商业模型；HIP的部属需要对主机协议栈进行修改，对Internet影响较大。2.2.2路由器驱动型路由器驱动型方案将

22、整个Internet划分为边缘网络与核心网络，边缘网络内部 使用PI地址，既作为主机的标志符也用于内部的路由寻址;核心网络使用PA地 址，用于核心网络的路由；边界路由器将数据分组中的目的PI地址改为核心网络 的PA地址，实现边缘网络与核心网络分离。路由器驱动型方案使用PI地址前缀 作为网络标志符，PA地址作为该网络接入Internet的拓扑位置，从而分离了边 缘网络的IP地址前缀的双重语义，保证了 Internet的路由扩展性。LISP是这类方案中的一种典型方案，LISP将地址空间分为端点标志（EID）和路由 位置符（RLOC）。EID可以唯一地标志边缘网络内的主机，在边缘网络内既用于路 由也

23、用于主机标志，EID的前缀作为边缘网络的标志符。RLOC标志网络位置，在 核心网络中用于路由。LISP还定义了入口隧道路由器（ITR）和出口隧道路由器 （ETR）。LISP将边缘网络内外主机间的通信路径分成图6所示的3个部分：边缘网络内 从源主机到ITR（绿色）的路径部分，使用EID路由；从ITR到ETR的隧道路径部 分（红色），使用RLOC路由；从ETR到目的主机的路径部分，使用EID路由（紫色）。 下面就以主机A向主机B发送数据分组的过程为例说明LISP的主要原理：数据分组首先被转发到ITR（路由器E）;ITR在本地映射缓存中查找目的EID到RLOC的映射，如果查找到对应的RLOC， 则为

24、数据分组添加一个外部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相同)转发至存有被