Summary: DNS Performance and the Effectiveness of Caching

Jung et al. use an analysis of real DNS traffic (and traffic causally related to DNS) to challenge some of the foundational assumptions of the DNS design: namely, that higher TTLs lead to higher cache hit rates, and that lower TTLs lead to decreased performance.  On the surface these assumptions are perfectly reasonable: higher TTLs keep entries cached for a longer time, so assuming a random temporal distribution of requests, we would expect this to result in a higher likelihood of hits.  Lower TTLs mean more frequent invalidation of cache entries, and hence more load on the servers at the top of the hierarchy: in the DNS design,  reducing load on centralized resources is perhaps a more important application of caching than reducing lookup latency.

The refutation of these assumptions would have been difficult to carry out without real traces, as the relationship between TTL and cache hit ratio is affected unexpectedly by two properties of the distribution of real requests.  First, name requests follow a heavy-tailed distribution, which means that although caching is immensely helpful for the head of the distribution, no amount of increasing resources or cache sharing will do much to reduce misses on the tail.  Second, it turns out that most traffic has such significant temporal locality that high TTLs do little to improve the cache hit ratio: a minute or two will usually do.

[no time to finish this post: this will have to do]

Summar: DNS

I think we often trivialize the DNS, partly because the basic lookup service it provides is so simple, and partly because it has been the subject of so many exploits.  Its weak, time-based consistency semantics make it difficult to reason about the system's behavior: an administrator is supposed to tune the TTL to adjust the tradeoff between stale data and performance, without any clear guidelines for which values to choose.  It is easy to ignore the fact that the DNS was deliberately designed to be a system that can accomodate massive growth while dividing responsibility and accountability evenly among the stakeholders in the namespace, and that it has been tremendously successful in meeting these goals.   The loose structure and variable hierarchy of the zone mechanism gives a level of  extensibility and "responsibility indirection" appropriate to the real internet: organizations can and should host their own name servers, but need not: high-gravity internet entities like ASs can provide this as a service to their customers.  The simplicity of the current protocol is largely the effect of usage and not design: the extensibility features of the DNS type system are mostly unused.

This paper has one my favorite quotes from a CS paper ever: 

"Distributing authority for a database does no distribute a corresponding amount of expertise.  Maintainers fix things until they work, rather than until they work well, and want to use, not understand, the systems they are provided."

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.