Minimizing Routing State for Light-Weight Network Simulation

Huang, Polly and Heidemann, John

citation

Polly Huang and John Heidemann 2001. Minimizing Routing State for Light-Weight Network Simulation. Proceedings of the International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (Cincinnati, Ohio, USA, Aug. 2001), to appear. [PDF]

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.

reference

@inproceedings{Huang01b,
  author = {Huang, Polly and Heidemann, John},
  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},
  sortdate = {2001-08-01},
  project = {ant, vint},
  jsubject = {network_simulation},
  publisher = {IEEE},
  address = {Cincinnati, Ohio, USA},
  month = aug,
  pages = {to appear},
  jlocation = {johnh: pafile},
  keywords = {network simulation, routing abstraction},
  url = {https://ant.isi.edu/%7ejohnh/PAPERS/Huang01b.html},
  psurl = {https://ant.isi.edu/%7ejohnh/PAPERS/Huang01b.ps.gz},
  pdfurl = {https://ant.isi.edu/%7ejohnh/PAPERS/Huang01b.pdf},
  otherpsurl = {http://www.tik.ee.ethz.ch/%7ehuang/publication/algo-routing-mascots01.ps.gz},
  otherpdfurl = {http://www.tik.ee.ethz.ch/%7ehuang/publication/algo-routing-mascots01.pdf}
}