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

Michael Liljenstam, David M. Nicol

Research output: Contribution to journalConference article

Abstract

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
Volume1
StatePublished - Dec 1 2004
EventProceedings of the 2004 Winter Simulation Conference - Washington, DC, United States
Duration: Dec 5 2004Dec 8 2004

Fingerprint

Network Simulation
Routing
Network protocols
Dynamic Routing
Semantics
Internet
Data storage equipment
Terminate
Shortest path
Divergence
Table
Demand
Policy
Model

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Computer Science Applications

Cite this

On-demand computation of policy based routes for large-scale network simulation. / Liljenstam, Michael; Nicol, David M.

In: Proceedings - Winter Simulation Conference, Vol. 1, 01.12.2004, p. 215-223.

Research output: Contribution to journalConference article

@article{cd699ff8ef3046448ff6e928eca1e817,
title = "On-demand computation of policy based routes for large-scale network simulation",
abstract = "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.",
author = "Michael Liljenstam and Nicol, {David M.}",
year = "2004",
month = "12",
day = "1",
language = "English (US)",
volume = "1",
pages = "215--223",
journal = "Proceedings - Winter Simulation Conference",
issn = "0891-7736",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

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

AU - Liljenstam, Michael

AU - Nicol, David M.

PY - 2004/12/1

Y1 - 2004/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=17744390610&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=17744390610&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:17744390610

VL - 1

SP - 215

EP - 223

JO - Proceedings - Winter Simulation Conference

JF - Proceedings - Winter Simulation Conference

SN - 0891-7736

ER -