Automatic IP Address Assignment on Network Topologies

Jonathon Duerig, Robert Ricci, John Byers (Boston University), Jay Lepreau

Flux Technical Note FTN–2006–02
February 11, 2006

Flux Research Group
University of Utah, School of Computing

emulab.net

Abstract

We consider the problem of automating the assignment of IP addresses to nodes in a network. An effective assignment exploits the natural hierarchy in the network and assigns addresses in such a way as to minimize the sizes of routing tables on the nodes. Automated IP address assignment benefits simulators and emulators, where scale precludes manual assignment, large routing tables can limit network size, and realism can matter. It benefits enterprise networks, where large routing tables can overburden the legacy routers frequently found in such networks.

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 present a comparative assessment of 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.

Full paper:

• PDF