Minimizing Routing State for Light-Weight Network Simulation

Polly Huang and John Heidemann
USC/Information Sciences Institute

Abstract

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.

Availability

This paper is available in several formats: abstract web page with pointers and cites, gzip'ed postscript, PDF, paper copies can be obtained by mail to the authors. Copyright terms for this paper appear below.

Reference

Huang01b

Polly Huang and John Heidemann. Minimizing Routing State for Light-Weight Network Simulation. In Proceedings of the International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p. to appear. Cincinnati, Ohio, USA, IEEE. August, 2001. <http://www.isi.edu/~johnh/PAPERS/Huang01b.html>.

@inproceedings{Huang01b,
	author = "Polly Huang and John Heidemann",
	title = "Minimizing Routing State for Light-Weight Network Simulation",
	booktitle = "Proceedings of the  International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems",
	year = "2001",
	publisher = "{IEEE}",
	address = "Cincinnati, Ohio, USA",
	month = "August",
	pages = "to appear",
	keywords = "network simulation, routing abstraction",
	url = "http://www.isi.edu/~johnh/PAPERS/Huang01b.html",
	psurl = "http://www.isi.edu/~johnh/PAPERS/Huang01b.ps.gz",
	pdfurl = "http://www.isi.edu/~johnh/PAPERS/Huang01b.pdf",
	otherpsurl = "http://www.tik.ee.ethz.ch/~huang/publication/algo-routing-mascots01.ps.gz",
	otherpdfurl = "http://www.tik.ee.ethz.ch/~huang/publication/algo-routing-mascots01.pdf",
}

Copyright

This paper is copyright © 2001 by its authors. Permission to make digital or hard copies of part or all of this work for personal use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that new copies bear this notice and the full citation on the first page. Abstracting with credit is permitted.

To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission of the authors.