基于自治域编址的可扩展路由机制研究

发布时间：2018-06-20 09:25

本文选题：路由可扩展性 + 大规模路由　；参考：《清华大学》2015年博士论文

【摘要】：互联网在近年来面临严峻的路由可扩展性问题,具体体现为核心网络路由器中路由表规模和路由更新数量的快速增加。本文提出了基于自治域编址的可扩展路由机制用以解决该问题。本文分别综述了路由可扩展性的测量工作和解决路由可扩展性的方案。路由可扩展性的测量工作从互联网路由表规模和路由更新两个角度,研究两者的增长规律和增长原因。路由可扩展性的方案包括编址类方案、核心/边缘分离方案、移除方案和聚合方案,这四种方式都能提高路由可扩展性并各有优缺点。本文主要从地址分配角度(包括域内和域间两个方面)测量路由可扩展性及其变化规律。从域内地址聚合角度将前缀分为连续碎片、不连续碎片、聚合非碎片和吸收非碎片,发现大部分前缀由于地址分配因素形成。从域间地址聚合的角度,提出指标“兄弟前缀距离”用以衡量前缀被聚合的可能性,发现新分配前缀的聚合可能性逐渐降低。测量表明了合理的地址分配对路由可扩展性的重要性。本文提出基于自治域的无类编址和路由机制(CABA):在编址结构上反向嵌入AS号码将前缀和AS号码进行关联,并通过PA方式分配AS号码促进路由信息在域间的聚合;在路由机制上限制AS拆分和发布更细小的前缀。因此从地址分配和使用两方面减少了对路由可扩展性的影响。本文提出了混合源路由机制(HSR)对CABA机制进行扩展。HSR在CABA的基础上引入了不可见自治域的概念,不可见自治域不对外宣告路由信息,可以在增加不可见自治域的同时不增加网络中的路由信息。同时,HSR也解决了不可见自治域的通信问题,它使报文在离开不可见自治域时携带路由信息并根据该路由信息返回不可见自治域。本文提出了域间不相交多路径路由(DIMR),提高CABA的路径多样性以增强对流量工程的支持,为了降低多路径路由对路由可扩展性的影响,每条宣告前缀最多计算两条路径,并要求两条路径尽可能不相交。DIMR将两条AS路径看作一个整体(路径对),发现两条不相交AS路径可以形成AS环,且AS环也能分成两条不相交路径。因此DIMR包含了一个基于路径对的路由选择算法,该算法可以让更多的AS找到不相交AS路径。本文还证明了该路由算法的收敛性,并提出路由策略的实现方法和两种无环报文转发方法。
[Abstract]:In recent years, the Internet is faced with severe routing scalability problem, which is embodied in the rapid increase of routing table size and the number of routing updates in core network routers. In this paper, an extensible routing mechanism based on autonomous domain addressing is proposed to solve this problem. This paper summarizes the measurement of routing scalability and the solution of routing scalability. The measurement of routing extensibility is based on the scale of routing table and the update of routing, and the growth rules and reasons of both are studied. Routing scalability schemes include addressing class scheme, core / edge separation scheme, removal scheme and aggregation scheme. These four schemes can improve routing scalability and have their own advantages and disadvantages. In this paper, routing scalability and its variation are measured from the point of view of address assignment (including intra-domain and inter-domain). From the perspective of intra-domain address aggregation, the prefixes are divided into continuous fragments, discontinuous fragments, polymerized non-fragments and absorbed non-fragments. It is found that most prefixes are formed by address assignment factors. From the point of view of inter-domain address aggregation, the index "brother prefix distance" is proposed to measure the possibility of prefix aggregation, and it is found that the aggregation possibility of newly assigned prefixes decreases gradually. The measurement shows the importance of reasonable address allocation to routing scalability. In this paper, we propose a classless addressing and routing mechanism based on autonomous domains: backward embedding as numbers in the addressing structure to correlate the prefix and as numbers, and allocate as numbers to facilitate the aggregation of routing information between domains through PA. The routing mechanism limits as splitting and publishing smaller prefixes. Therefore, the impact on routing scalability is reduced in terms of address allocation and usage. In this paper, the hybrid source routing mechanism (HSRs) is proposed to extend the CABA mechanism. HSR introduces the concept of invisible autonomous domain on the basis of Caba. The invisible autonomous domain does not declare routing information. You can add invisible autonomous domains without adding routing information in the network. At the same time, HSR also solves the communication problem of invisible autonomous domains, which enables packets to carry routing information when leaving invisible autonomous domains and return to invisible autonomous domains according to the routing information. In this paper, disjoint multipath routing between domains is proposed to improve the diversity of CABA paths to enhance support for traffic engineering. In order to reduce the impact of multipath routing on routing scalability, each declared prefix calculates up to two paths. It is also required that the two paths should not intersect as much as possible. DIMR regards the two as paths as a whole. It is found that the two disjoint as paths can form as rings and the as rings can be divided into two disjoint paths. Therefore, DIMR includes a routing algorithm based on path pairs, which allows more as to find disjoint as paths. This paper also proves the convergence of the routing algorithm, and proposes the implementation of the routing strategy and two non-loop packet forwarding methods.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP393.0

【相似文献】