论文部分内容阅读
互联网在近年来面临严峻的路由可扩展性问题,具体体现为核心网络路由器中路由表规模和路由更新数量的快速增加。本文提出了基于自治域编址的可扩展路由机制用以解决该问题。本文分别综述了路由可扩展性的测量工作和解决路由可扩展性的方案。路由可扩展性的测量工作从互联网路由表规模和路由更新两个角度,研究两者的增长规律和增长原因。路由可扩展性的方案包括编址类方案、核心/边缘分离方案、移除方案和聚合方案,这四种方式都能提高路由可扩展性并各有优缺点。本文主要从地址分配角度(包括域内和域间两个方面)测量路由可扩展性及其变化规律。从域内地址聚合角度将前缀分为连续碎片、不连续碎片、聚合非碎片和吸收非碎片,发现大部分前缀由于地址分配因素形成。从域间地址聚合的角度,提出指标“兄弟前缀距离”用以衡量前缀被聚合的可能性,发现新分配前缀的聚合可能性逐渐降低。测量表明了合理的地址分配对路由可扩展性的重要性。本文提出基于自治域的无类编址和路由机制(CABA):在编址结构上反向嵌入AS号码将前缀和AS号码进行关联,并通过PA方式分配AS号码促进路由信息在域间的聚合;在路由机制上限制AS拆分和发布更细小的前缀。因此从地址分配和使用两方面减少了对路由可扩展性的影响。本文提出了混合源路由机制(HSR)对CABA机制进行扩展。HSR在CABA的基础上引入了不可见自治域的概念,不可见自治域不对外宣告路由信息,可以在增加不可见自治域的同时不增加网络中的路由信息。同时,HSR也解决了不可见自治域的通信问题,它使报文在离开不可见自治域时携带路由信息并根据该路由信息返回不可见自治域。本文提出了域间不相交多路径路由(DIMR),提高CABA的路径多样性以增强对流量工程的支持,为了降低多路径路由对路由可扩展性的影响,每条宣告前缀最多计算两条路径,并要求两条路径尽可能不相交。DIMR将两条AS路径看作一个整体(路径对),发现两条不相交AS路径可以形成AS环,且AS环也能分成两条不相交路径。因此DIMR包含了一个基于路径对的路由选择算法,该算法可以让更多的AS找到不相交AS路径。本文还证明了该路由算法的收敛性,并提出路由策略的实现方法和两种无环报文转发方法。