Design and evaluation of a protocol for automated hierarchical address assignment

One way to attack the problem of growing routing tables in networks is hierarchical addressing. When addresses are distributed manually by the network administrator, maintaining a good hierarchical address allocation can be difficult, especially if the domain is large. This paper presents a protocol to self-organize a routing domain with hierarchical addresses that are closely matched to the underlying network topology. Once the protocol assigns addresses, we examine the shortest-path routing tables for every router. Our studies indicate that 95% of the routing tables calculated are within one entry of optimal, where an optimal routing table is defined as one entry per next-hop router. In addition, these results are robust across networks of various sizes and in networks with various numbers of cycles. The protocol's address allocation is efficient, with minimal waste of address space. Furthermore, our experiments indicate that the choice of which router initiates the protocol does not significantly affect the quality of the resulting routing tables nor the efficiency of the address allocation.