Optimizing IP Address Assignment and Static Routing at Large Scale

by
Jonathon Duerig

Advised by
Jay Lepreau

Network emulation is a hybrid technique that com- bines real and simulated elements of a network. Our group has pioneered the development of highly auto- mated network emulators. These testbeds allows re- searchers to study the behavior of their applications in a laboratory environment that resembles the real Inter- net. These researchers set up experiments, particular configurations which model various situations they wish to learn about. A testbed also allows experimentation on networks that look not like today's Internet, but tomorrow's, or today's Internet under massive attack.
A continuing research challenge is scaling network emulation to tens of thousands of hosts. The research outlined in this abstract tackles a particular scaling problem that had limited emulated networks to a few hundred nodes.

Before we can run an emulation, IP addresses must be assigned to all hosts in the network. If IP ad- dresses are assigned poorly, many network applications (routers, firewalls, etc.) behave unrealistically. In par- ticular, routes must be calculated for every host. When the network topologies are small, simple techniques are sufficient for assigning IP addresses and calculating, storing, and distributing routes. However, these prob- lems are a serious barrier to large-scale network emula- tion.

Our research uses three techniques that, together, solve the time and space problems of routing when the number of hosts is greater than 10,000. First, we run an algorithm we've developed to infer the hierarchical structure of the network topology. We use this hier- archy to guide the assignment of IP addresses to the nodes. These two steps approximate how IP address assignment happens in the real Internet. Second, the routing table of each host is compressed by aggregat- ing similar routes. The effectiveness of the compres- sion is improved by the hierarchical IP address assign- ment. Third, we dramatically reduce the route calcu- lation time by distributing the calculation.

The time complexity of route calculation has been reduced from O(n2 ·log (n)+nm) to O(n·log (n))+m. In practice, this means that the time to calculate routes for a 10,000 host topology has been reduced from more than two hours to less than a second. The aggregate size of all the routing tables remains O(n2), because no compression is possible in the worst case. However, the compression algorithm guarantees that edge hosts only have one route, and IP assignment significantly reduces the number of routes required by central hosts.

While we have solved several of the issues raised by routing and IP address assignment, many interesting problems remain. Humans are still much better at IP address assignment than our automated program is. Route compression with human-assigned IP addresses is 160effective. It is probable that different assignment techniques work better on different graphs. We have to find a way to compare graphs to test this assumption. This would also allow us to better evaluate the consis- tency of our algorithms. Ideally, our results are similar on similar graphs. Finally, an interesting related prob- lem which we are exploring is a way to quantitatively measure the degree of hierarchy in a graph.