Summary: PLayer

I thought PLayer was an interesting application of the DOA/i3 concept of using indirection to decouple logical and physical paths, in an environment where it could actually be useful.  I never really bought the idea of indirection through NATs and packet filters scattered across the WAN, if only because I believed no one would trust such an infrastructure as they would a physical expression of the same logical path: people like the idea that they are literally "behind" some firewall.  But nobody likes cabling a datacenter and no one is comfortable with the idea that the security of their colo is enforced merely by the physical ordering of cables and switches.  

It's ambitious (and somewhat beyond my understanding) to try to pull this off at level 2, encapsulating ethernet frames in new frames and introducing forwarding cycles at a layer that typically isn't well-equipped to handle them.  I remember that at the RADlab retreat the PLayer presentation got some resistance from the Cisco industry reps; something about this approach breaking the spanning tree protocols.... I forget the details.

Summary: DOT

I'm not sure how I feel about this one.  Certainly the premise is valid: many applications that move bytes have to reimplement the actual byte-moving routines (this is an example of the end2end argument in practice, I suppose), so a clean architectural separation between control and data plane in such applications means not only reuse and economy of mechanism, but a decoupling of the evolutions of the two planes, which may progress at different speeds or change for different reasons.  OK.  

Separation of control and data isn't a novel idea.   Didn't FTP have a control session, and a subsequent data transfer on another port?  Second, I feel like there's an e2e argument latent in this discussion: except for the simplest protocols, most applications (take rsync) have some fairly complex end2end semantics.  Take the gcp protocol that they propose: it does not encrypt the data it sends, which would be a dealbreaker for many, if not most users of SCP.  To encrypt the data and behave more like SCP breaks the clean division of planes: now the data stream needs to flow through both loci of control and data logic.

Summary: DTN

Neat paper.  I think the most meaningful criticism I can make is that the authors are not so much proposing a new technology (certainly they are, but it's fairly simple, and is merely sketched in the paper), but making the controversial observation that in "challenged" networks, it may no longer be reasonable to expect any sort of connection-oriented protocols.  The theme of the postal service appears, in the authors' vision, on both sides of the current internet: that is to say, the internet is modeled after the postal service, and DTN is a postal-like service overlaid on the internet.  Statistical multiplexing is every bit as flexible as the postal model, but higher levels of the communication stack sacrifice this flexibility for stronger guarantees. 

I had never though about the idea of "terrestrial mobile networks."  I don't think the authors have a good solution yet for dealing with capacity issues at DTN gateways and the general logistical issues associated with "shipping": busses carrying bits are likely often full, or underutilized.  Of course, logistics is a well studied area from which we can learn lessons.  

The authors anticipate the criticism that the basic DTN idea could be well approximated by an "everything over email" approach to communication, albeit with weaker semantics.

Summary: XTrace

I have to be careful what I criticize about this paper as I know some of my classmates have worked extensively within the xtrace framework.  My initial reaction to the concept was that it was a great idea that would never work.  The attractiveness of the approach is obvious to anyone who has ever tried to debug a distributed system: without these sort of causal traces, it amounts to (when done properly) a merge-sort over a set of application and network logs, sorted by timestamp, from multiple hosts, unifying by eye the correlated events.  Format differences (imagine lining up tcpdump and apache logs) and clock skew make the inference of causation more or less impossible.  

XTrace to the rescue.  Annotating the actual datapath is in some ways a core-stateless approach that avoids a lot of the Lamportian issues of time and clocks: the lineage of next pointers creates partial orders over the logged events. This makes causal inference straightforward: follow a node along pointers to the sink.  I love the idea.  Somehow, the synchronous action of assigning the next pointers does not significantly slow down the augmented applications.

I guess I won't believe until I've instrumented an application with Xtrace that it's actually easy to do.  Are there already generic implementations of IP,TCP,DNS, and clients that make adoption a possibility?  A good trace will always begin at a client, but that's the last place that we'd expect to see any adoption.  

where is figure 8?

Summary: DOA

Walfish et al. take the i3 ideas of logical indirection and the stacking of identifiers and apply them to a specific domain: finding a way to achieve the functionality provided by NATs and packet filters in a way that is consistent with the tenets of the original internet design.  This is a very interesting discussion: I believe that the idea works but am not convinced that it is well-motivated.  Like i3, a DHT-based rendezvous architecture allows end hosts to explicitly place themselves (logically) "behind" delegates that perform middlebox functions without requiring the topology to reflect the logical structure.  By assigning each host a "true" unique identifier, firewalls and NATs can be rethought as first-class internet citizens rather than as stealth entities that violate layering boundaries or override TCP attributes like outgoing ports.

Are they making the internet architecture safer and more flexible, or are they merely finding a way to show that they've observed the tenets with which the paper begins?  I am not sure.  It is certainly the case that explicit identification could make services like SIP compatible with private address spaces without requiring  difficult, application-specific hacks.

This and the i3 paper are the first pieces we've read this semester that address the issue of security at all.

Summary: i3

It's rather obvious, but I will state nonetheless that the real beauty of i3 is its simplicity.  The idea alone is compelling, and straightforward enough to implement (not necessarily to adopt!) that a proof-of-concept is not really necessary.  It is enough to observe that the current internet conflates the notion of identity (and group membership) and address, while in the real world the two are quite separate: a single person can have multiple homes (mobility), and a single set of christmas cards tend to be sent to a large set of addresses (multicast).  A single level of indirection -- regardless of the implementation choices -- takes care of these issues, allowing rendezvous-based communication that decouples identity from location.   The idea of id stacks is a particularly powerful construct.  A form of logical source routing, it allows the arbitrary composition of services, an idea explored in more detail in the DOA paper.  

Adoption is obviously an issue for systems of this kind.  It is not enough to listen on an address to provide a service: it is now necessary to aggressively re-pin a trigger record in the DHT.  Clients can cache results of lookups, but must refresh them frequently to accommodate server mobility.

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.

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/

;)

Summary: EXOR / XOR

I really enjoyed these papers but am low on time to get these posts in, so I am going to combine them.

Both begin with the observation that although it may be convenient to treat wireless routing graphs as though they were wired networks, it doesn't make sense.  Issues like hidden terminals, the capture effect and asymmetric links frustrate this model, making layering violations like forcing reliable transfer facilities into the link layer mandatory for reasonable performance.  Instead of maintaining this model and hacking the protocols to mask the problems, both papers argue that wireless routing should embrace the broadcast nature of the medium: blast as much information onto the grid as possible.

The first paper (EXOR, as in logical exclusive OR, as in, an exclusive OR of the recipients of a broadcast message is elected as the forwarder) uses multi-pathing and synchronization to address the issue of lossy links.  The decision about who is the next-hop forwarder is made AFTER all the candidate forwarders receive the message: ideally, the node among them closest to the destination should send as many of the packets it can, saving hops.  Even better, assuming lossy links it is likely that this ideal forwarder has received only a subset of the total transmission: in lock step, after its transmission, the other candidates have opportunities to forward on the subset of packets not already transmitted by higher priority hosts.   Thus, messages are sent in parallel through several paths in the network, and it is easy to see how this improves throughput and reduces retransmissions.  On the surface, this sounds like it could be a complicated and message-expensive approach (consensus and leader election protocols are hard) but the paper shows how the order and timing can be decided deterministically.  

The second paper (XOR, as in bitwise exclusive OR), though inspired by similar principles, takes a quite different approach.  Given broadcast (actually, pseudo-broadcast, for the reliability reasons discussed) communication, many bottlenecked topologies could benefit by increasing the information content of individual packets (this means fewer transmissions generally AND passing more data through a congested network).  The idea is to broadcast coded packets containing the XOR'd information from as many native packets as possible, with the constraint that the next node must have received ALL component packets except the one destined to it.  Given this constraint and a packet header with the list of packet ids encoded in the payload, it is a simple matter to repeatedly XOR the packet with all of the component packets: the result is the new native packet addressed to you.  The authors show that the potential information gain due to this form of compression is 2, but that because this approach allows greater utilization of networks with full queues, the actual gain is much greater than that: in fact, with the right topology and congestion conditions is it unbounded.

Summary: ETX

I found the discussion here a bit repetitive but the overall contribution compelling.  Although wireless networks have an especially high penalty per hop (a node cannot simultaneously send and receive, so pipelining is impossible and adding a hop to a route effectively halves the throughput), metrics based solely on hop count are unlikely to choose the best routes, in general because they will make an arbitrary choice among several routes with the same hop count.  A better metric is an estimated transmission count, that takes into account asymmetry and counts retransmissions due to loss into the total.  ETX calculates a probability of delivery based on the receipt of regularly spaced probe packets: the probability of receiving a packet from a neighbor is the ratio of received to expected probes in a given time window.  To accommodate asymmetry, each node must also forward its own results (according to the above calculation) to its neighbors.  Only in this way can a given node have both a sense of receipt probability over a given link (determined by expected vs. received probes along that link) and send probability (determined by the receipt probability forwarded from the other side).  The ETX is then 1/sendP*recvP -- a perfect link will have probabilities of 1 in the denominator and estimate a single transmission.  

It was considerably less painful to write this than it was to read the paper.

Summary: Multi-Hop Wireless Ad Hoc Network Routing Protocols

On the surface, Broch et al. merely present a comparison of four ad-hoc multi-hop wireless routing protocols in terms of routing overhead, delivery ratio of packets and path optimality under a simulation of a mobile network.  Pulling this off required a huge quantity of work and amounts to an impressive piece of research.  First the ns event simulator had to be extended to accurately model wireless link conditions including signal attenuation, restricted packet capture conditions, and a MACA/MACAW link layer.  Then each of the competing routing protocols had to be implemented from the spec, and in the process, optimizations were added.

DSDV resembles traditional distance vector routing protocols, but it augmented with a sequence number to allow the rapid replacement of broken routes: a best path sort sorts first by sequence, and among the highest sequences routes choses the one with lowest cost.  TORA is an on-demand protocol that focuses on route correction and low disruptiveness instead of optimality: small route adjustments are made as locally as possible to reduce route discovery overhead.  DSR is a straightforward source routing protocol, and as such is significantly different from the other approaches: packets are routed not via next-hop but following the complete ordered list of hops provided by the client.  Clients learn of routes through route requests, and nodes reply to these requests based on fragments of source routes that they have promiscuously overheard from other senders.  The newcomer AODV is a hybrid: hop-wise routing tables are maintained via on-demand mechanisms.

TORA crumbles under load and DSDV performs predictably OK, as we might have predicted.  DSR does really well almost across the board.  Its overhead (in terms of messages) is very low because learning routes promiscuously is basically free, but overhead in terms of stored state is likely to be high.

Summary: Unplanned 802.11b

A completely ad-hoc deployment and evaluation is in some ways the polar opposite of a catalogue of modeling best practices.  And yet, as a proof of concept for the mesh approach (as opposed to an access point-based approach) this study is extremely compelling.  The set of goals are both pragmatic and differentiating: the first design decision of unconstrained placement produces an intuitively accurate model of what a real deployment would look like.  That multi-hop routing approaches that favor high-bandwidth links even if they are lossy is an ideal approach is not immediately obvious: we would expect a combination of a lossy link with high levels of congestion (because the high bandwidth makes the route frequently chosen by other nodes) to cause lots of transport-level issues.  Further, the idea that multi-hop routing over many short links can be preferable to a single-hop route is likewise not intuitive in a wired framework: in fact, many routing protocols use hops alone as a naive cost measure.   Because these approaches are not intuitive, the positive results are especially compelling.

At some points in the evaluation I lost sight of what it was that they were trying to evaluate.  All-pairs connectivity may be a good measure of the robustness of a mesh network, but since (I assume) the primary goal of the mesh was internet connectivity for members, I would have expected the otherwise very pragmatic approach of the authors to focus on a more specific interaction of gateway placement with general mesh density.

Summary: Modeling Wireless Links

The second in a set of empirically focused papers, an alternate title for this work could have been "how NOT to model wireless networks".   The authors mercilessly call out many published experimental results as basically broken, and unfortunately many of these examples are too domain-specific to generalize to a meaningful lesson. Only the last two criticisms -- experiments should include state-of-the-art technology, and should be reproducible -- ring true in a broad sense.  Maybe these approaches are indeed all broken, but I found this pretty aggressive.

There is certainly value in treating WLAN, satellite and cellular in one piece of research.  However different these link types may be, they share the same principal problem with regard to the transport layer.  Because they are less reliable than wired links, data corruption, loss, and changes in bandwidth (not to mention issues associated with handoffs, etc) are bound to occur.  But because TCP treats packet loss as an indication of congestion, it will invariably react to the unreliability of the underlying network by backing off, and the extent of the backoff will depend on the interaction of the packet loss and the window size, resulting in either some retransmissions or actual timeouts.

For the first time, I'd like to vote that we drop this paper from the syllabus.   It was not a memorable piece of work.