Friday, September 5, 2008

Why to increase additively and decrease multiplicitively

In section 1.2 of this paper on congestion avoidance in computer networks, the authors present a summarized overview of the types of decision making that a system can incorporate, ranging from centralized to decentralized. They justify their decision to use a decentralized system.

I appreciated the way they articulate the classification of algorithms for managing distributed resources (centralized vs. decentralized). It is essentially one of the question we are wrestling with in the Chukwa project, and also the RAD Lab project. I intend to read some of the papers they reference when they describe this spectrum.

Zooming out, the overall thing that makes this paper amazing is the way they formalize, quantify, and visualize their algorithms.

Every systems paper should attempt to emulate the methodology found in this one. They begin by clearly articulating the problem being solved (Section 1.4) and defining the solution space (imagine a matrix with three rows: additive/multiplicitive/non-linear, and two columns: increase/decrease). They then construct a concrete mathematical model to quantify the performance impacts of the various points in the design space (the 2D vector representation of the Dynamics (2.1) was genius) which of course leads to an elegant, intuitive solution.

This paper seems to be missing empirical experimentation showing that the proposed optimal solution actually works in reality.

No comments: