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

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.