acm sigcomm

Interdomain routing has been extensively studied over the past decade by both research and industrial communities. While tremendous knowledge and understanding have been gained on various aspects of the Interdomain routing (including routing policies), there are some gaps that remain to be filled. What make this paper interesting and distinguish itself from many other paper on interdomain routing policies is that this paper intended to bridge one of these knowledge gaps by conducting a survey on business relationships and routing policies used by individual autonomous systems in practice. About 100 network operators responded to the survey and answered questions about their routing policies, billing models, and thoughts on routing security. The paper presented survey results and discussed their implications. While most of results provided a systematic view of interdomain routing policies used in practice and on the extent to which common modeling assumptions about routing policies actually hold on the Internet, some of the findings are quite interesting and require deeper understanding on their implications. For example, the survey results showed that 90% of operators disabled MRAI timer which is used to rate limit update messages between neighboring BGP-speaking routers. This paper provided a good starting point on some of these findings. Follow up studies that look deeper into these findings would be of great interest to the research community and can potentially impact network operators for setting their policies in the future. One limitation of this paper is that survey results only represented a somewhat bias view from the 100 operators who were questioned and responded. Having said that, I believe these results provided very useful information on the operational reality of interdomain routing policies. Researchers and students who work on the interdomain routing area would find this survey beneficial.

This paper focuses on improving the scalability and robustness of simulations for analyzing interdomain routing techniques. There are two challenges with inter-domain routing simulations (as outlined by the paper): (i) The running time of simulations on large AS graphs can be very high – O(|V|^3) for an AS graph with |V| vertices. For an empirical AS graph with 36K nodes, it will take several months to finish. (ii) The lack of ground truth information makes assessing the accuracy and robustness of routing techniques difficult. To address the first challenge, the author develops a novel routing tree algorithm that takes only O(|V|^2) time to compute paths between all source-destination pairs in an AS graph with |V| vertices, which is significantly faster than the state of the art. The algorithm exploits the fact that realworld AS graphs are typically very sparse, with only around 4*|V| edges as opposed to O(|V|^2) edges. It computes all the paths by performing a specialized three-stage breadth-first search (BFS) on the AS graph. To further improve the scalability in the context of repeated simulations, the paper develops lightweight faster amortized algorithms that achieve 5-times speedup compared to running repeated simulations. The idea is to run a single computation for all-pairs paths once and saving and reusing the intermediate results for subsequent iterations. Since the algorithms can be run independently across destinations, Map-reduce style parallelization is used to achieve another 200-times speedup. This is very good! Regarding robustness, the paper proposes to perform repeated simulations with varied parameters – this becomes computationally feasible because of the significantly reduced run-time. While it is arguable whether repeated simulations alone suffice to cope with the lack of ground truth, the approach helps better understand the impact of the imperfect data and modeling assumptions and is therefore clearly valuable. Overall, a very nice paper. The core ideas are both interesting and useful. The techniques proposed in the paper should really become the common practice in future large-scale simulation studies of interdomain routing.