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.

Date

2001

Authors

Polly Huang, John Heidemann

Conference

MASCOTS 2001, Proceedings Ninth International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems

Pages

108-116

Publisher

IEEE