John Heidemann

Minimizing Routing State for Light-Weight Network Simulation

TitleMinimizing Routing State for Light-Weight Network Simulation
Publication TypeConference Paper
Year of Publication2001
AuthorsP. Huang, and J. Heidemann
Date Publishedaug
Conference LocationCincinnati, Ohio, USA

We introduce a routing mechanism, referred to as algorith- mic routing. It is a viable routing alternative for network simulations with minimal space complexity–-O(N). In theory and for simulations size of the Internet, algorithmic routing has the potential of reducing memory requirement by several orders of magnitude. In practice and through ns- 2 simulations on random topologies, we find memory con- sumption of algorithmic routing exhibits a similar scaling property. However, routes computed by algorithmic routing are not all the shortest. Although we find the relative differ- ence is below 10% for more than 80% of the routes, we are cautious about its applicability to general network simula- tions. With further discussion on impacts of the distortion, we derive a set of guidelines and recommend users to apply this technique only when suitable.