Research On AS Based Scalable Routing Mechanism

In recent years, the Internet faces great routing scalability issue, e.g. the rapid increasing routing table of DFZ routers and increasing routing updates received. In this thesis, we propose an AS-based scalable addressing and routing scheme to address this issue.This thesis summarizes the related work of measuring routing scalability issue and proposals to address it. Measurements toward Internet routing scalability are carried out from two perspectives of increasing routing table size and increasing routing updates,which further study the laws of their growth. Routing scalability solutions include addressing, core/edge separation, elimination and aggregation. All the four solutions can increase the routing scalability but each one has its advantage and disadvantage.This thesis measures the routing scalability and its trends over time from the perspective of address allocation(including both inter-domain and intra-domain aspects). From the perspective of aggregatablity of intra-domain addresses, prefixes are classified into four categories: continuous and discontinuous fragments, aggregated and absorbed nonfragments. And this thesis finds that most prefixes are caused by address allocation. From the perspective of aggregatablity of inter-domain addressess, we propose a metric named”Brothers prefix distance(BPD)” to measure the likelihood of aggregating a prefix and find that most prefixes are due to inappropriate allocation of IP address. All in all, the work implies that inappropriate allocation of IP address is of importance to the routing scalability.This thesis proposes the Class AS-Based addressing and routing scheme(CABA),which embeds an AS number reversely into IPv6 addressing format. CABA proposes to allocate AS numbers as PA addresses, to faciliate the aggregation of corresponding prefixes. It further keeps ASes from prefix-splitting when announcing their prefixes. Therefore, CABA increases the routing scalability from both address allocation and usage perspectives.This thesis presents the hybrid source routing mechanism(HSR) to extend CABA.HSR introduces the concept of invisible AS, which doesn't advertise prefixes into the global routing system, so as to increase the number of ASes while not increasing routing information. At the same time, HSR also solves the problem of communication between an invisible AS and other ASes. It makes packets carry routing information while leaving invisible AS, so as to return the invisible AS refering to such information.This thesis proposes Disjoint Inter-domain Multipath Routing(DIMR), which increase the path diversity of CABA to faciliate traffic engineering. In order to reduce the impact on routing scalability, all ASes should calculate at most two paths toward a single prefix and the two paths should overlap as little as possible. DIMR regards two disjoint AS paths as a whole(path pair) and discover that two disjoint AS paths form an AS circle and an AS circle can be split into two disjoint paths. Therefore, DIMR contains a pathpair based routing algorithm, which faciliates more ASes to discover disjoint paths. This thesis also proves the convergence of the routing algorithm, and proposes an approach to support routing policy and packet forwarding approaches of DIMR.