Jonathon Duerig, Robert Ricci, John Byers (Boston University), Jay Lepreau
University of Utah Flux Group Technical Note 2006-02
February 2006
Flux Research Group
School of Computing, University of Utah
50 S. Central Campus Drive Rm. 3190
Salt Lake City, Utah 84112-9205 USA
We consider the problem of leveraging topological information to automate the assignment of IP addresses to nodes in a network. An effective assignment exploits the natural hierarchy in the network, and thus assigns addresses so as to minimize the sizes of routing tables on the nodes. Automated IP address assignment primarily benefits emulators and simulators, where scale precludes manual assignment. Because it happens to minimize routing table sizes, it can also benefit large networks with legacy routers.
We formalize the problem and point to several practical considerations that distinguish our problem from related theoretical work. We then describe several of the algorithmic directions and metrics we have explored, some based on previous graph partitioning work and others based on our own methods. We compare our algorithms on a variety of real and automatically generated router-level Internet topologies. Our two best algorithms, yielding the highest quality namings, can assign addresses to networks of 5000 routers, comparable to today's largest single-owner networks, in 2.4 and 58 seconds. The first has been in production use in the Emulab network testbed for over two years.
Full paper:
Shorter and modestly revised version: