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.

Router grafting is a recently proposed technology (Keller et al., NSDI’10) that permits migrating one local endpoint of a session between two routers without having to inform the remote one. By doing so, it permits reconfiguring several aspects of an IP network without imposing downtimes or inflicting severe and potentially dangerous changes to BGP. In this paper the authors looks at the potential of putting router grafting to work for the benefit of traffic engineering. The main idea is that an optimal traffic engineering depends among others on the characteristic of the traffic matrix to be served. Router grafting allows reshaping a traffic matrix by selecting the ingress and egress points at which traffic is received and handed over to other networks. Therefore, it has the potential to improve traffic engineering by applying it on an easier to handle, reshaped traffic matrix. The authors formulate a generalized traffic engineering problem that includes the extra degree of freedom, propose two heuristics for solving it, and present evaluation results based on Internet2 traffic. These results point to a potential improvement of around 20% due to router grafting. An interesting paper making the case for router grafting more concrete by putting it into the context of traffic engineering and evaluating using real traffic data. The reviewers criticized almost consistently the assumption that traffic is handed over between networks over a single link, pointing to the fact that peering or customerprovider relationships typically require two networks to meet at multiple points. A second suggestion for improvement was to consider in the evaluation more realistic data regarding the availability of alternative points to which an existing link can be migrated (eg, factoring practical aspects like the existence of ports and circuits for moving the traffic to the new end-point). One could look, for example, at some Internet Exchange Points (IXP) and provide a more concrete quantification of benefits based and their actual tenants and the costs for moving to alternative sites. Finally, a more in-depth look at the source behind the demonstrated 20% performance gain would benefit this paper. Where does it come from? Is it connected to diurnal traffic patterns or is it a one-shot improvement that once performed requires no further alternation of inter-connection points? Overall, a solid performance evaluation work that leaves some interesting questions open for future study.

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.