On-demand computation of policy based routes for large-scale network simulation

Michael Liljenstam, David M. Nicol

Research output: Contribution to journalConference articlepeer-review


Routing table storage demands pose a significant obstacle for large-scale network simulation. On-demand computation of routes can alleviate those problems for models that do not require representation of routing dynamics. However, policy based routes, as used at the interdomain level of the Internet through the BGP protocol, are significantly more difficult to compute on-demand than shortest path intradomain routes due to the semantics of policy based routing and the possibility of routing divergence. We exploit recent theoretical results on BGP routing convergence and measurement results on typical use of BGP routing policies to formulate a model of typical use and an algorithm for on-demand computation of routes that is guaranteed to terminate and produces the same routes as BGP. We show empirically that this scheme can reduce memory usage by orders of magnitude and simultaneously reduce the route computation time compared to a detailed model of the BGP protocol.

Original languageEnglish (US)
Pages (from-to)215-223
Number of pages9
JournalProceedings - Winter Simulation Conference
StatePublished - 2004
EventProceedings of the 2004 Winter Simulation Conference - Washington, DC, United States
Duration: Dec 5 2004Dec 8 2004

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Computer Science Applications


Dive into the research topics of 'On-demand computation of policy based routes for large-scale network simulation'. Together they form a unique fingerprint.

Cite this