互联网可扩展路由研究

《互联网可扩展路由研究》由会员分享，可在线阅读，更多相关《互联网可扩展路由研究（12页珍藏版）》请在金锄头文库上搜索。

1、第 8 卷第 3 期 信息技术快报 Vol.8 No.3 Information Technology Letter May 2010 39 互联网可扩展路由研究 互联网可扩展路由研究 唐明董唐明董 张国清张国清 杨景杨景 张国强张国强 摘 要:摘 要: 全球路由表的高速膨胀使得当前的互联网域间路由系统的可扩展性面临着严峻的挑战。 为了缩减路由表,很多研究提出了新的路由解决方案。本文在介绍了互联网路由系统现状之后,从较高层次上将存在的路由解决方案分为短期方案、路由架构和可扩展路由算法三部分，着重讨论了路由算法和路由架构这两类工作,对经典的可扩展路由算法和路由架构进行了分析和比较， 最后对尚未解

2、决的问题和未来的研究方向进行了总结和展望。 关键词: 关键词: 域间路由；可扩展性；路由算法；路由架构 如今，互联网域间路由系统的扩展性正面临着十分严峻的挑战1。据统计，基于 IPv4 的全球路由表(global routing table)表项数目前已在 30 万以上，且还在呈现指数级增长2。庞 大的路由表显著增加了路由器的内存和处理器开销， 导致通信延时的增长和路由收敛属性的 恶化。 为了应对路由表的膨胀，网络服务提供商(ISP)采取了以下措施：一、升级路由器硬件； 二、压缩路由表数据结构；三、过滤 IP 前缀。但是升级路由器硬件提高了网络服务提供商 的经营成本， 降低了网络的性价比， 而

3、高端路由器的性能发展能否跟上路由表的膨胀速度还 是一个问题。压缩路由表的数据结构会引起更多的计算代价，不利于路由器的快速反应；过 滤 IP 前缀将导致一些站点不可达。这些措施都没有触及根本问题。许多专家认为，为了从 根本上解决路由扩展问题，修改边界网关协议（Border Gateway Protocol, BGP）甚至建立全 新的路由架构十分必要1。为此，近年来针对互联网路由扩展问题的研究掀起了一个热潮， 从不同技术角度对可扩展的互联网路由进行了探讨， 提出了很多路由解决方案。 本文对这些 工作进行了综述， 分析和比较了它们的基本思想和特点， 并指出了有待解决的问题和未来的 研究方向。 1 背

4、景背景:互联网路由系统现状互联网路由系统现状 互联网是由许多自治系统(Autonomous System，AS)连接而成的。一个自治系统可以自 主决定在内部如何选择路由。 网络运营商通常对自治系统内部的链路分配代价， 然后沿链路 代价之和最小的路径转发流量。这类路由选择协议有 OSPF1、IS-IS2等。对于较大的自治系 统，它的网络通常被分为若干个路由区域以便降低路由复杂性和提高路由扩展性。 在自治系统之间唯一使用的路由协议是 BGP 协议。 每个 BGP 路由器会告诉它的邻居哪 些目的地址前缀标识的站点通过它的网络可达以及需要穿越的自治系统路径。因此，BGP 协议是基于路径向量的。在互联网

5、的边缘网络中，BGP 路由器维护的路由表项数相对较少， 对目的地未知的包使用缺省路由发送。然而在互联网的核心区域，BGP 路由器并不存在缺 省路由，因此该区域又被称为互联网的无缺省区(default-free zone，DFZ)。无缺省区路由器 常常需要为互联网的每个可达的 IP 前缀安装一条路由， 结果导致路由表随着全球 IP 前缀数 量的增加而膨胀。 1 即“Open Shortest Path First”，是一个内部网关协议 2 Intermediate system to intermediate system，中间系统到中间系统。一种内部网关协议 互联网可扩展路由研究 40 互联网

6、域间路由的扩展问题早就存在。IETF3在上世纪 90 年代采用无类别域间路由4一 度有效地降低了全球路由表的膨胀速度。然而,近年来各种反聚合因素的增长使得无类别域 间路由的路由聚合作用逐渐失效，IPv4 前缀数量迅速增加，无缺省区的路由表再度呈现爆 炸式增长。根据互联网架构委员会(IAB)在 2007 年的报告1 ，这些因素主要包括： 1. 与提供商无关的地址 客户网络倾向于使用与提供商无关(provider-independent，PI)的地址，这样在改变提供 商时可以避免重编号(renumbering)对网络设备和主机重新分配 IP 地址。因为现实中重 编号往往要花费很高的代价。PI 前缀

7、由于不能被上级提供商聚合，必须登记到无缺省区的 路由表中。增加的地址前缀不需要客户付费，然而无缺省区路由表将因此而膨胀。 2. 多宿主 多宿主(multi-homing)是指一个站点从多个提供商那里获得服务。多宿主得到广泛应用 的原因在于：提供了备用路由，能够增加连接到互联网的可靠性。一个多宿主的站点可以使 用 PI 地址或 PA(provider-aggregatable)5地址。如果使用 PI 地址，那么 PI 前缀必须出现在它 的所有提供商的路由表中。如果使用 PA 地址，那么 PA 前缀仅能够被分配该地址的提供商 聚合，但是不能被其它提供商聚合。实际上,由于最长前缀匹配规则的存在，为了

8、保证 PA 前 缀可以经过它的提供商可达， 往往该提供商也需要单独发布该前缀。 因此不管哪一种情况都 将导致前缀聚合失效。 3. 流量工程 流量工程(traffic engineering, TE)的目的是让某些互联网流量避免使用特定的网络路径。 使用流量工程的既包括提供商网络也包括客户网络， 具体原因有负载平衡、 降低费用和安全 需求等。在 BGP 级，如果要对某块地址实施流量工程，那么网络运营商必须将该地址前缀 从原来的较短前缀中分裂出来单独发布到全球路由表中。 上述因素使得 IPv4 前缀不断分裂，全球路由表中的前缀粒度越来越细，数量越来越多。 尽管全球路由表的规模受到 IPv4 的地址

9、空间的约束，但是这并不意味着路由表的膨胀速度 会减缓。随着 IPv6 的广泛部署和应用，由于 IPv6 能够提供庞大的地址空间，可能导致全球 路由表项数以更快的速度增长。基于以上因素，很多专家认为，提高互联网路由系统的扩展 性已经迫在眉睫。 2 互联网可扩展路由研究分类互联网可扩展路由研究分类 为了降低路由表规模和解决互联网路由的扩展问题， 目前已经提出了许多解决方案。 根 据着眼点的不同这些解决方案从较高层次上可以分为三类。 1. 短期方案 短期方案大多是对 BGP 协议提出增量式的修改， 并且以提高 BGP 路由的收敛属性和降 低时延为主。Forgetful routing6 3可以降低路

10、由表所占用的内存空间。它的基本思想是选择3 Internet Engineering Task Force，互联网工程任务组 4 Classless Inter-Domain Routing，CIDR。一个用于给用户分配 IP 地址以及在互联网上有效地路由 IP 数据包的对 IP 地址进行归类的方法 5 可由提供商聚合的地址 6 有译成“健忘路由” 第 8 卷第 3 期 信息技术快报 Vol.8 No.3 Information Technology Letter May 2010 41 性地丢弃路由表中的部分替代路由， 只有在必要时才从邻接路由器那里获取。 它不需要改变 BGP 协议且基本不

11、影响路由的收敛属性。 但是 Forgetful routing 并没有减少 IP 前缀数量和路 由表的增长速度，因此是一个短期方案。考虑到短期方案并不能真正提高路由扩展性，本文 中不作具体讨论。 2. 路由架构 从中长期来解决路由扩展性的目标出发， 很多研究人员提出了新的路由架构， 其中许多 是 IRTF7 8的提案。 绝大多数的新路由架构都是考虑在现有域间路由系统中增加一个间接的 中间层(indirection layer)，使域间的扁平路由架构变成分层的。中间层将 IP 地址空间分离为 主机标识和路由标识两部分，后者在路由时作为位置符使用，并建立它们之间的映射；或者 更激进一些，中间层可能

12、引入一种新的名字空间作为路由标识空间，将 IP 地址空间映射到 该名字空间。包在传递过程中由中间层在某个阶段将主机标识用路由标识替换来穿越互联 网。路由标识要么是能够聚合的，要么具有较大的粒度，使得路由标识的数量是可控的，从 而缩减路由表。 基于路由标识的类型和来源，可以将新的路由架构分成核心-边缘分离、位置符/标识符 分离、基于自治系统号的路由、基于虚拟聚合对象的路由等；根据路由架构以改变主机为主 还是以改变网络为主可以分为基于主机的和基于网络的； 而根据包传递过程中使用路由标识 替换主机标识时是改写包地址还是对包进行封装，可以将新路由架构分为地址重写(address rewriting)的

13、和映射与封装的(map (5). 对映射系统引入的利益关系，即谁付费、谁受益还需要有更深入的理解。比如映射系统 谁来部署，是否需要向用户收费等。 另一方面， 面向未来互联网的可扩展路由理论仍然值得进一步研究。 这方面的工作目前 聚焦在寻求比地址聚合更好的可扩展路由算法，如紧凑路由、贪心路由等。地址聚合是当前 互联网唯一使用的可扩展路由机制。 然而互联网自治系统级拓扑结构逐渐从树状演化成网状 （mesh） ，呈现无标度特征。一些专家认为，地址聚合在本质上越来越与域间拓扑结构背离， 故从长期来看， 扩展性将受到限制。 因此有必要充分考虑互联网的结构和演化特性来设计高 效的路由算法，为新的可扩展路由

14、方案提供理论与实践指导。 参考文献： 参考文献： 1 Meyer D, Zhang L, Fall K, Report from the IAB workshop on routing and addressing, The Internet Architecture Board, 2007. 2 BGP Routing Table Analysis Reports, http:/ 3 Karpilovsky E and Rexford J, Using forgetful routing to control BGP table size, In CoNEXT, 2006. 4 Kleinr

15、ock L, Kamoun F, Hierarchical routing for large networks: Performance evaluation and optimization, Computer Networks, 1:155174, 1977. 5 Massey D, Wang L, Zhang B, and Zhang L, A proposal for scalable Internet routing and addressing, Internet Draft, http:/www.ietf.org/internet-drafts/draft-wang- ietf-efit-00.txt, 2007, 2. 6 Tsuchiya P, The landmark hierarchy: A new hierarchy for routing in very large networks, In Proceedings of ACM SIGCOMM, 1988. 7 Stoica I, Morris R, Karger D, Kaashoek MF, and Balakrishnan H, Chord: A scalable peer-to-peer lookup service for internet applic