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.