Summary: Chord

Do not mistake this short post for a lack of enthusiasm about the Chord paper: at my fourth read or so, I find little to criticize or emphasize, except to list the things that are cool about it.

cool:

• this isn't just academic rumbling: a distributed hash table is an immensely useful storage primitive  for just about any class of application I can think of.
  
• it would have been a mistake to bake into the overlay any logic having to do with value storage: this would only serve to limit the class of applications that could use the service.  Instead, Chord simply maps ids to nodes, allowing synchronous access via lookup() and allowing a callback mechanism to asynchronously alert the application of topology changes.
• the property that lookups are resolved via O(log N) messages with high probability is not only amazingly scalable, but easily verified by reasoning about the overlay structure and routing algorithm.
• the finger tables are a good example of the correct use of soft-state: they are a performance optimization, unnecessary for correctness and inferrable from a bare graph.
• stabilization provably works, even under conditions of concurrent joins and failures.

less cool:

• most of the guarantees of Chord rely on the guarantees of the consistent hashing algorithm proposed by Karger, which unlike Chord is not so easy to understand.
• the authors clearly privilege scalability over performance: a small to medium sized Chord installation probably resolves lookups via more hops than are really necessary.

Summary: DHT Survey

This was a good overview: there isn't much to say about it because most of the material is straightforward.  The authors follow the evolution of search over P2P overlays, from the naive broadcast search of gnutella, to the hierarchical broadcast approach of kazaa, to the forwarding approach of Freenet.  From here, academic answers to the forwarding approach like Chord and Pastry enforce structure over the overlay to allow them to make certain guarantees about robustness and performance.  These solutions are quite similar: all offer name-host hash mapping, resolving gets and puts by routing towards the node responsible for a given key.  They differ in the underlying topological structure of the overlay that is used to bound the complexity of lookup, storage and stabilization operations.  The notions of unidirectionality and symmetry as axes around which to classify the various DHT implementations goes a long way in explaining the practical differences between them.

Summary: Active Networks

The authors address the concerns about efficiency and security that have been associated with the active network argument from its inception, and do a fairly good job of demonstrating that a careful implementation (not the current one ;) ) can perform reasonably and provide an acceptable level of safety.  Protection issues are addressed through code signing and type fingerprinting: users are prevented from running arbitrary code by using a call-by-reference approach where the pointer is an MD5 hash of the registered code chunk, and the connection between different code chunks that must share soft state is indicated via signatures.   Resource management issues are addressed much as they are in the internet of today: a combination of restrictive APIs, TTLs and general optimism about user cooperation is employed.  The performance analysis is not particularly rigorous: the prototype is slow, presumable because 1.) java is slow, 2.) copying the network stack into userland is slow 3.) their capsule approach is generally slow, and the authors attempt to separate the latencies associated with each component in order to speculate about how a kernel-mode c implementation might perform.

 What the authors fail to do, at least in my opinion, is demonstrate convincingly that there are really compelling applications for the technology, or even that it would be easy to build existing technology using this approach: I agree with Ari.  This was a fun paper to read because in spite of the argument in the introduction, it's  a good example of pure research that will never be realized in the field.  If safe, proven and on-board technologies like RED are almost universally left disabled by conservative network admins because a suboptimal equilibrium is preferable to any risk or uncertainty, it is safe to say that technology like this will never be adopted.

Summary: RON

 A naive overlay network that hides the underlying link structure is only as reliable as its substrate, but overlays that are aware of the base network can actually add a transparent reliability layer: TCP/IP is itself an example.  Like all good ideas, the motivation for RON can be simply and convincingly stated -- and like many systems, the unexpected complexity of the implementation is something of a disappointment. 

The problem is that in implementing a system that can route packets and react more quickly to route outages than core internet routing, you basically need to implement core internet routing in your overlay.  In the process, it becomes clear that the reason BGP reacts slowly to outages is that it damps route topology changes to prevent oscillation: preferring stability to sensitivity was a deliberate design choice.  Detecting an outage is, after all, not straightforward in a distributed system.  

The authors mention early in the paper that another alternative would have been to use a generic overlay in combination with a modified protocol like OSPF.  I don't understand why they couldn't have augmented OSPF with their custom "loss minimizer" in order to prove the basic point that a routing overlay network could provide faster recovery for route loss on the WAN.

Summary: First Principles

This was another one of those "how NOT to do it" papers, and like Sally Floyd's how not to model wireless networks paper, it left me a bit cold: it breaks a lot down without doing much to rebuild.

It is interesting (and somewhat surprising) to see the effect on internet monitoring that the work of Falutsous et al. had between 1999 and 2004.  If we write network modeling tools to randomly generate network structures while maintaining the invariance of certain power laws, we do so because we assume that those power laws capture something intrinsic and identifying about real networks.  That certain proportions remain invariant as scale increases is certainly interesting but is not necessarily helpful!  Real networks evolve based on local factors like demand, capacity, and to some degree planning for future growth, and a first principles approach would begin with such axioms, rather than on observing a constant across snapshots and inferring that this constant somehow captures the important properties of the network structure.

The examples of degree-preserving rewiring do make the power law approach seem arbitrary, just like the power law approach made other approaches to characterizing networks like central tendency in outdegree seem arbitrary.  Finding a minimal encoding of the information necessary to predict and model general networks is not an easy problem and Li et al. do not even attempt to solve it: they are content to hack away at other attempts to do so.

Summary: Power Laws

Without making too many excuses for myself, I want to point out that I don't really understand the maths, and engage with material like this at the level of analogy.  A power law describes a relationship, usually one of exponential decrease, between variables that exhibits scale invariance: that is to say, the curve (or line, if plotted in log-log scale) looks the same regardless of the scale of the dependent and independent variables.  This relates to the interesting property of "self-similarity" made famous by popular interest in fractals and chaos theory: the coastline of England (besides being infinitely long), if viewed and continuously decreasing scale, resembles itself at each level of scale.  Finding power laws that are invariant over the internet as it both grows and mutates would be very handy indeed not merely for modeling, but for provisioning the future internet.

As the paper points out, many natural phenomena follow a power law with a "magic" exponent constant, the Zipfian and Pareto distributions being among the most famous.  The authors show power law relationships (independent-dependent) between rank and outdegree, outdegree and frequency, and  hop count and the number of neighbors with k hops, where the exponent is largely invariant over the (rather closely placed) observations.

The obvious criticism is that there are not nearly enough data points to make this determination: the authors are assuming scale invariance with little evidence.  Further, they don't seem particularly confident in their own assertions.   Were they in a rush to publish first?

Summary: TAG

I'll try to tone down my excitement about this paper, but suffice it to say that work like this is the reason that I want to be in school.  The first observation is that in-network aggregation, a fairly well studied problem in shared-nothing databases, is even more relevant to ad-hoc sensor networks because of the power cost of transmission.  In the database arena, the idea of decomposing and "pushing down" aggregate functions into a distributed dataflow overlay graph is an attempt to reduce the message complexity of the distributed computation, on the assumption that the ethernet network connecting a cluster of servers will become a bottleneck.  In an ad-hoc sensor network, reduced message complexity translates directly to longer lifetime.  Because of the broadcast medium, there are also new opportunities to repair overlays by snooping to recover lost state.

The taxonomy of aggregate functions is really impressive: I feel like there is little else to publish (sadly) about the subject of online aggregation.  I would only point out that "count distinct" can, when the data is partitioned appropriately with respect to the query, be reduced to to a distributive partial state problem: count distinct evaluated at the leaves and sum() at the intermediate nodes.  This obvious but often ignored optimization is pointed out in an otherwise terrible recent paper: http://www.springerlink.com/content/05710782r4232566/

;)