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的快速增长仍未得到解决。
