Minimizing Routing State for Light-weight Network Simulation
Journal
IEEE International Symposium on Modeling, Analysis and Simulation on Computer and Telecommunication System (MASCOTS 2001)
Pages
108-116
Date Issued
2001-08
Author(s)
John Heidemann
Abstract
We introduce a routing mechanism, referred to as algorithmic routing. It is a viable routing alternative for network simulations with minimal space complexity-O(N). In theory and for simulations the size of the Internet, algorithmic routing has the potential of reducing memory requirements by several orders of magnitude. In practice and through ns-2 simulations on random topologies, we find memory consumption of algorithmic routing exhibits a similar scaling property. However, routes computed by algorithmic routing are not all the shortest. Although we find the relative difference is below 10% for more than 80% of the routes, we are cautious about its applicability to general network simulations. With further discussion on the impacts of the distortion, we derive a set of guidelines and recommend users to apply this technique only when suitable.
Type
conference paper