Measuring the effectiveness of hierarchical address assignment

Hierarchical, topology-based addressing has long been considered crucial to routing and forwarding scalability. Recently, however, a number of research efforts are considering alternatives to this traditional approach. With the goal of informing such research, we investigated the efficiency of address assignment in the existing (IPv4) Internet-that is, the assignment of prefixes to ASes. In particular, we ask the question: "Exactly how much does addressing hierarchy help us at the interdomain level?" To do so, we first define a notion of efficiency or locality based on the total number of bit-hops required to advertise all prefixes in the Internet in BGP, and compute this quantity for the current Internet using RouteViews data. In order to quantify how far from "optimal" the current Internet is, we assign prefixes to ASes "from scratch" in a manner that preserves observed semantics, using three increasingly strict definitions of equivalence. These results provide an indication of the efficiency of addressing at the interdomain level in the current Internet.