Scalable simulation of complex network routing policies

Andrew Ian Stone, Steven DiBenedetto, Michelle Mills Strout, Daniel Massey

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Modern routing protocols for the internet implement complex policies that take more into account than just path length. However, current routing protocol simulators are limited to either working with hard-coded policies or working on small networks (1000 nodes or less). It is currently not possible to ask questions about how the routing tables will change on all of the autonomous systems (e.g., AT&T, Sprint, etc.) in the internet, given a change in the routing protocol. This paper presents a routing policy simulation framework that enables such simulations to be done on resources that are readily available to researchers, such as a small set of typical desktops. We base the policy simulation framework on the Routing Algebra Meta-Language (RAML), which is a formal framework for specifying routing policies. Our theoretical contributions include proving that the signatures and the meet operation induced by the preference operator in RAML define a semilattice and that routing policy simulation frameworks are analogous to data-flow analysis frameworks. The main problem we address is that direct implementation of routing policy simulation has scaling issues due to the O(n2) memory requirements for routing tables. However, due to properties of routing algebras specified in RAML, we are able to segment the simulation problem into multiple runs that propagate route information for subsets of the network on each run. This strategy enables us to perform a simulation that does not exceed system memory on typical desktops and enables the 43 minute, parallel simulation of a real network topology (33k nodes) and an approximation of the common BGP protocol.

Original languageEnglish (US)
Title of host publicationCF 2010 - Proceedings of the 2010 Computing Frontiers Conference
Number of pages9
StatePublished - 2010
Externally publishedYes
Event7th ACM International Conference on Computing Frontiers, CF'10 - Bertinoro, Italy
Duration: May 17 2010May 19 2010

Publication series

NameCF 2010 - Proceedings of the 2010 Computing Frontiers Conference


Conference7th ACM International Conference on Computing Frontiers, CF'10


  • data-flow analysis
  • metarouting
  • parallel
  • performance
  • routing
  • simulation

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Scalable simulation of complex network routing policies'. Together they form a unique fingerprint.

Cite this