Roch Guerin

Introducing short papers at conext 2013

Roch Guérin, Olivier Bonaventure
Appears in: 
CCR April 2013

There have been many recent discussions within the computer science community on the relative roles of conferences and journals [1, 2, 3]. They clearly offer different forums for the dissemination of scientific and technical ideas, and much of the debate has been on if and how to leverage both. These are important questions that every conference and journal ought to carefully consider, and the CoNEXT Steering Committee recently initiated a discussion on this topic.

Functionality-rich versus minimalist platforms: a two-sided market analysis

Soumya Sen, Roch Guerin, and Kartik Hosanagar
Appears in: 
CCR October 2011

Should a new "platform" target a functionality-rich but complex and expensive design or instead opt for a bare-bone but cheaper one? This is a fundamental question with profound implications for the eventual success of any platform. A general answer is, however, elusive as it involves a complex trade-off between benefits and costs. The intent of this paper is to introduce an approach based on standard tools from the field of economics, which can offer some insight into this difficult question.

Message-Efficient Dissemination for Loop-Free Centralized Routing

Haldane Peterson, Soumya Sen, Jaideep Chandrashekar, Lixin Gao, Roch Guerin, and Zhi-Li Zhang
Appears in: 
CCR July 2008

With steady improvement in the reliability and performance of communication devices, routing instabilities now contribute to many of the remaining service degradations and interruptions in modern networks. This has led to a renewed interest in centralized routing systems that, compared to distributed routing, can provide greater control over routing decisions and better visibility of the results.

Public Review By: 
Dmitri Krioukov

Distributed routing is hard. There are too many problems with it. Not to solve them is a “revolutionary clean slate” (henceforth, all quotes are from the reviewers’ comments). For example, let routing be no longer distributed, but again centralized -- 4D, for example. Routers no longer route, they just forward. A separate, centralized routing systems computes all the routes, translates them into FIBs, and uploads the latter to forwarders, reborn routers. Unfortunately, many problems remain, they just grow some “wrinkles”. One of such problems, characteristic of any routing, “centralized or not”, is transient loops and associated communication complexity, i.e., the number of control messages per network topology change. This paper deals with the “wrinkles” of this problem in the centralized settings.
Specifically, the problem formulation is as follows. For each destination, the forwarding paths in a steady state form a directed acyclic graph (DAG) containing all the forwarding elements (FEs) in the network. After a topology change, such DAG transforms into a new DAG. If the union of the old and new DAGs has cycles, then there exists at least one FE update ordering that would produce transient routing loops for the corresponding destination. Consider now the union, across all destinations, of the cycle parts present in the new DAGs. If this union has no its own cycles, which is the case, for example, for all single link or node failures, then the topological sorting of this union clearly yields an FE ordering that can be used to update each FE only once, for all destinations, and without forming any transient loops. However, if this union has cycles, then such ordering does not exist, and the task is to split all destinations into a minimum number of update groups, such that all FEs are updated once per group. The authors propose a simple greedy heuristic for this NP-hard problem.
All the four reviewers liked the paper. All four, however, believe that convergence time is an evaluation metric, which is more important, at least from the practical standpoint, than message complexity that the authors focus on. One reviewer finds the greedy approach too simplistic for this NP-hard problem: “Better heuristics are likely possible, but evaluation does not tell how far the algorithm is from the optimal solution” in cases when it can be found, e.g., for single link or node failures. The authors only “provide information about the reduction in the number of messages” compared to the naive approach, in which each FE is updated once per destination. Another reviewer expresses perhaps the most fundamental concern with the problem formulation itself. Why do “all FEs have to update their FIBs the same number of times as the number of destination groups”? Different FEs may have to be updated different numbers of times, thus reducing the overhead compared to the authors’ approach. In other words, “the approach in the paper is not a real message minimization approach. The restriction imposed by destination grouping is unnecessary.” (See “Loop-Free Updates of Forwarding Tables” by J. Fu, et al.).
In summary, the paper deals with one of the fundamental problems in routing, the minimization of convergence costs, this time in the centralized settings, and under the no-transient-loops constraint. The paper makes it clear that these costs cannot scale better than linearly with the network size, and proposes a simple, easy-to-implement heuristic to minimize them in cases when this scaling is worse than linear.

Syndicate content