Optimizing IP Address Assignment on Network Topologies

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

Flux Technical Note 2005-04
July 2005

Flux Research Group
University of Utah, School of Computing

emulab.net

Note

This FTN has been superceded by FTN 2006-02.

Abstract

We consider the problem of optimizing the assignment of IP addresses to nodes in a network. An effective assignment takes into account the natural hierarchy present in the network and assigns addresses in such a way as to minimize the sizes of routing tables on the nodes. Optimized 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 that we are considering and point to several of the practical considerations that distinguish our problem from related theoretical work. We then outline several of the algorithmic directions we have explored, some based on previous graph partitioning work and others based on our own methods. A key underpinning of our methods is a concept we call Routing Equivalence Sets (RES), which provides a metric that quantifies the extent to which routes to sets of destinations can be aggregated. We present a comparative assessment of the strengths and weaknesses of our methods on a variety of real and automatically generated Internet topologies.

Full paper:

• PDF