IPv4 Address Allocation and the BGP Routing Table Evolution

The IP address consumption and the global routing table size are two of the vital parameters of the Internet growth. In this paper we quantitatively characterize the IPv4 address allocations made over the past six years and the global BGP routing table size changes during the same period of time. About 63,000 address blocks have been allocated since the beginning of the Internet, of which about 18,000 address blocks were allocated during our study period, from November 1997 to August 2004. Among these 18,000 allocations, 90\% of them started being announced into the BGP routing table within 75 days after the allocation, while 8\% of them has not been used up to now. %% LZ: is the follow 45% of allocated, or 45% of advertised prefixes? Among all the address blocks that have ever been used, 45\% of them were split into fragments smaller than the original allocated blocks; without these fragmentations, the current BGP table would have been about half of its current size. Furthermore, we found that the evolution of BGP routing table consists of both the appearance of new prefixes and the disappearance of old prefixes. While the change of the BGP routing table size only reflects the combined results of the two processes, the dynamics of either process is much higher than that of the BGP table size. %% LZ: this last sentence needs to be revised once we get the revised section 7 Finally, we classify routing prefixes into \emph{covering} and \emph{covered} ones, and examine their evolution separately. For the covered prefixes, which account for almost half of the BGP table size, we infer their practical motives such as multihoming, load balancing, and traffic engineering, etc., via a classification method