Analysis of Hierarchical Addressing in Different Deployment Ways

Abstract

Hierarchical addressing (HA) is a crucial component of the Internet for routing scalability. Recently, the global routing table size shows an explosive growth. To solve the scalability issue, some solutions propose to use HA in a global deployment way. However, it may cause some Autonomous System (AS) being assigned with massive prefixes. This could be a big challenge for the hosts, routers, ASes and DNS. By modeling the AS-level topology of the Internet as a hierarchical graph, we theoretically prove that with the lower position of HA deployment, arbitrary AS gets smaller amount of prefixes, while the routing table sizes of some ASes are monotonically increasing including the global routing table size. In order to solve both the excessive prefix problem and the routing scalability issue, we evaluate AS’s prefix amount and the size of routing tables considering different ways of HA deployment based on real Internet topology. Compared with the current Internet topology, we obtain better results in HA deployments. With our solution, the excessive prefix problem is solved and the global Forwarding Information Base (FIB) size could be reduced to 56% or even only 32% of the one in current Internet.