Minimizing Routing State for Light-weight Network Simulation

Huang, Polly
Heidemann, John

Abstract

We introduce an O(N) routing mechanism, referred to as algorithmic routing. It minimizes the memory consumption for routing states in network simulations. Our computation shows that for network simulations size of the Internet, algorithmic routing can potentially reduce memory requirement by three orders of magnitude to hierarchical routing in Internet-like hierarchy and an additional three orders of magnitude to flat shortest path routing. To evaluate the efficiency of algorithmic routing in practice, we implement the mechanism on ns-2. With network topologies randomly generated by GT-ITM, we compare the memory and run-time consumption of flat, hierarchical and algorithmic routing

Keywords

algorithmic
routing
abstraction

Notes

Related Papers

Bibtex

 @inproceedings{huang.heidemann_algo01,
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",
}

Back to Intro By Author By Importance By Keyword By Title By Reference