Analysis of the IPv4 Address Space Delegation Structure

The Internet has grown tremendously in terms of the number of users who rely on it and the number of organizations that are connected to it. Characterizing how this growth affects its structure and topology is vitally important to determine the fundamental characteristics and limitations that must be handled, such as address space exhaustion; understanding the process of allocating and delegating address space can help to answer these questions. In this paper, we analyze BGP routing data to study the structure and growth of IPv4 address space allocation, fragmentation and usage. We explore the notion of delegation relationships among prefixes and use this information to construct an autonomous system (AS) delegation tree. We show that delegation in the Internet is not significantly correlated to the underlying topology or AS customer-provider relationships. We also analyze the fragmentation and usage of address space over a period of five years and examine prefixes that are delegated by organizations vs. those that are not delegated. We notice that the address space usage due to delegating prefixes is increasing at the same rate as the address space usage due to non-delegating prefixes. This indicates that fragmentation rate of the address space is actually almost a constant with respect to total address usage. Additionally, we show that most delegation is performed by a small number of organizations, which may aid in the implementation of a public-key infrastructure for the Internet.