P2P!

The truth is, P2P is a really cool research topic, even if its number one application is sharing content illegally. Thus, I'm spending this post discussing the primary role of P2P: looking up data (which arguably most early P2P applications got wrong). The paper I'll be addressing most is Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications.

First, it should be clear that lookup is not inherently an easy task. Or at least if we assume that we want resiliency to failures, i.e. no central database, or even a collection of root databases under some hierarchical scheme (like DNS). Given that, a straw man approach would be something like broadcasting the message out ... but that clearly sucks. We would prefer a solution that bothers the least number of nodes possible. The authors of [CHORD] present an O(log N) solution! They do have an assumption, of course, which is that the individual nodes are willing to store information about content that they might not themselves actually have (i.e. they store a pointer(s) to who does actually have the content, but they are the ones responsible for resolving any lookups for that data).

Some key parts of Chord:

• Essentially a distributed hash table.
• Uses consistent hashing, which has the nice property that each node in the system sees approximately an equal number of keys, and when a node joins or leaves the system only O(1/N) keys need to be moved to a new node.
• Avoids the requirement that every node knows about every other node. Each node only needs to store information about O(log N) nodes; this is especially helpful in routing and keeps lookups at O(log N).
• Was implemented for correctness, i.e. handles potentially conflicting concurrent operations (joining or leaving, failure, etc) well.

The authors show a few simulations of Chord, as well as one real Internet prototype, in which it scales well as the number of nodes increases. I'm curious, however, how well this performs in smaller settings where latencies are actually much lower (like within a single data center). Lots of applications are being written in distributed styles where they have lookup needs that they would like to perform efficiently. I'm curious if the design decisions that went into Chord in any way limit it from performing as optimally as it could in a smaller data center like environment ... or if there are instead much better mechanisms for doing lookups there.

Overlay Networks

I'm addressing two papers in this post: Resilient Overlay Networks [RON] and Active network vision and reality: lessons from a capsule-based system [ACTIVE]. Both papers are attempting to address the shortcomings of the existing Internet architecture.

The authors of [RON] propose creating an overlay network with three goals in mind, "(i) failure detection and recovery in less than 20 seconds; (ii) tighter integration of routing and path selection with the application; and (iii) expressive policy routing".

The authors of [ACTIVE] also propose to create an overlay network, however, they state their main goal as simply "allow untrusted users to control the handling of their own packets within the network", which, more or less, is the aim of item (i) and (ii) of [RON], however, [ACTIVE] makes it much more explicit and therefore seems to have been harshly criticized (why would I ever want someone else's code to run on my router!).

While the authors of [ACTIVE] do mention that loss information is "clearly useful for congested-related services", they don't seem to make loss detection and recovery a top motivation for their work. (Because, come on, their work can effectively subsume [RON] ...)

In [RON] however, loss is a huge, if not the ultimate motivation. The issue is this: when routes are lost in the network the existing BGP protocol is ineffective, taking on the order of minutes to stabilize a new route. For lots of applications, this is unacceptable (consider a VoIP call, not only will we get "disconnected" but I can't even call back and try again ... unless I wait for a few minutes). As the authors of [RON] point out, the users perception of a "disconnected" connection is not on the order of several minutes like BGP imposes, but someone might be willing to hang out as long as about 20 seconds.

Of course, measuring path outages is hard, which [RON] makes clear. This reinforces, once again, that perhaps, while simple and elegant, using only a single bit of information for congestion and loss is unacceptable! I liked their discussion of failures: they categorized them in terms of either the network's perspective or the applications. The network sees link failures and path failures while an application sees only outages and performance failures.

In general, between both [RON] and [ACTIVE] I was a little concerned about adding this "hammer" on top of the existing Internet architecture. The authors of [RON] even acknowledge the fact that it is unclear how effective a RON will actually be if it became a standard (specifically, what happens when everyone is sending "active probes" to figure out route information ... I mean, should active probes actually be the way we figure out routes?!).

In the case of [RON], why can't we try and get a more responsive BGP to get fast detection and recovery? Why can't we get a better TCP as the basis for applications (so that they can more tightly integrate)?

In  the case of [ACTIVE], do programmers really want, or need, or make decisions about routing/forwarding at each and every hop? They even say themselves, "... it is clear that greater application experiences is needed to judge the utility of active networks. No single application ("killer app") that proves the value of extensibility has emerged, and none is likely to ..."!

Speaking of extensibility, I disagree with the analogue that the authors of [ACTIVE] draw in saying that "Active networks are no different in this regard than extensible operating systems, databases, or language implementations". I don't see it so optimistically ... when you are using disparate resources managed by lots of different people (unlike code running in an operating system on ONE computer) then extensibility is clearly not always what you may want (again, I don't want some other person's code to execute on my router!).

The authors of [ACTIVE] do provide some other valuable insights. Specifically, that systematic change is difficult and it seems necessary to be able to do experimentation without requiring deployment. Of course, isn't that what PlanetLab was for? In addition, the authors of [ACTIVE] discussed how their work may clash with the end-to-end argument, but they claim that it is not an issue (and lots of deployed services already do things that break the end-to-end argument ... firewalls, proxies, etc).

Ultimately, it seems that the authors of [ACTIVE] see their work as being most compelling for network layer service evolution ... which seems like a good fit.

Multi-Hop Wireless Routing

In continuation of the multi-hop wireless discussion from previous posts, I'm discussing some salient points from two papers, A High-Throughput Path Metric for Multi-Hop Wireless Routing [ETX] and A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols [COMPARE].

Again, the motivation for researching routing policies for multi-hop wireless networks should be clear ... the problem changes drastically when you move away from the typical access point wireless communication (wireless communication is not more than one hop).   

The authors of [COMPARE] evaluated four different routing protocols based on three metrics: packet delivery ratio, routing overhead, and path optimality. Packet delivery ratio is exactly like what it sounds like and comparable to link loss ratios in [ETX] (which will be discussed shortly). Routing overhead is exactly what it sounds like as well. Path optimality is an interesting metric because it, as of this paper: "in the absence of congestion or other 'noise', path optimality measures the ability of the routing protocol to efficiently use network resources by selecting the shortest path from a source to a destination".

Before I divulge on the results of [COMPARE] I feel it is a fair time to motivate [ETX], whose premise was exactly: the most efficient paths through multi-hop networks may not always be the shortest ... i.e. shortest path is a bad metric for path optimality. The authors of [ETX] provide examples of such scenarios, but the crux of the problem comes down to the fact that not all wireless links are high-throughput and lossless. Rather, they again reinforce an important point: a single hop that delivers only 50% of packets might be less useful as two hops that each deliver 100% of packets.

In [COMPARE] the authors allude to the possible problems of shortest path optimality as "congestion or other 'noise'". It turns out, as was shown in [ETX], that there is a lot of lossy links ... a.k.a. links that suffer from a lot of 'noise' (interference, etc). In addition, many of these links are asymmetric. That is, sending packets one direction has a higher delivery ratio than the other direction. This is clearly an issue with respect to most wireless protocols because while data may only be sent in one direction, an ACK must be sent in the other direction. Ultimately the authors of [ETX] designed a new protocol called ETX (Expected Transmission Count) that is based on delivery ratios, asymmetry in the delivery ratios, and interference over longer routes.

A few more thoughts:

• The authors of [COMPARE] claim that wireless networks have a fundamental limitation to wired networks for sending broadcast packets due to the fact that there is no medium to reserve for all "nodes in proximity". Two thoughts here: (1) it seems like you could augment the RTS/CTS scheme to allow for a node to broadcast a message to all nodes that can hear the RTS/CTS; (2) the multi-hop wireless protocols of Roofnet don't use RTS/CTS either.
• The authors of [COMPARE] focused their studies on mobility and movement (which naturally changed the network topology) while the authors of [ETX] have a more subtle assumption that the wireless nodes are stationary (they at least assume this in Roofnet).
• DSR (dynamic source routing) seemed to be the best candidate for environments like those simulated in the [COMPARE] paper (highly mobile). 

More on Wireless ...

Two more papers discussing wireless technologies, Modeling Wireless Links for Transport Protocols [MODELING] and Architecture and Evaluation of an Unplanned 802.11b Mesh Network [ROOFNET].

The authors of [MODELING] were intent on showing the dismal state of modeling and analyzing existing wireless deployments and suggesting alternative, hopefully better, characteristics to use for modeling. I found this study to be a bit dry, but I did have a few of the take-away points:

• There is a definite tension between changing wireless links versus transport protocols. I actually alluded to this in a previous post where I mentioned the hurdle researchers have in the wireless space, because it is not clear where you need to make compromises for either the wireless protocols or the transport protocols.
• TCP is not robust in the face of new link layer technologies. IN FACT, it is rather ironic that TCP is sensitive to packet reorderings! The original design goals of networks were to be robust in the face of lost links, lost packets, or packets traveling down different paths ... yet this is clearly not the case with TCP. IN ADDITION, TCP performs poorly when corrupted packets are received ... TCP has been over-optimized for link layers that are perfect (like ethernet). IN ADDITION, spurious timeouts due to link layer retransmissions are a severe problem and the transport protocols (like TCP) inflate transmit timers because they are agnostic of these link layer retransmissions (again, it seems that TCP has been over-optimized for an ethernet like link layer).  
• The packet loss==congestion signal is inadequate in wireless networks because packet loss might be due to errors ... do we need more explicit signals?
• A possible solution might be to push information about the link layers into the transport protocols (and maybe even vice-versa as well) ... but doesn't this break the nice abstraction we had before?

The authors of [ROOFNET] showed how an ad-hoc mesh network could be deployed using 802.11b technology. Interesting take-away points:

• In the authors words, "the highest-throughput routes often involve links with relatively high link-level loss rates, since a single-hop route with 40% loss can deliver more data than a two-hop route with perfect links. In addition, because the 802.11b bit-rates are at roughly power-of-two intervals, a high bit-rate with up to 50% loss is preferable to the next-lowest bit-rate." Interesting!
• Fast short hops are the best policy (as determined by their routing algorithm Srcr).
• The majority of nodes use many of their neighbors ... I actually didn't quite understand this conclusion. Does this mean that the majority of nodes have constantly fluctuating best routes to gateways?
• Multi-hop has a throughput advantage over long low-quality single-hop because it can exploit lots of short high-quality links ... and the overhead of retransmissions appears to be low enough.
• Roofnet does not use RTS/CTS ... in fact they have shown that it does not improve performance in their network!

An interesting link between the two papers was that [MODELING] claimed that out-of-order delivery or corrupted delivery is shown to be beneficial for real-time applications by decreasing delay, and this is especially true when there are multiple wireless links in the path. However, because none of the connections tested in [ROOFNET] were of the real-time nature, they did not conclude the same thing nor did they show how a new transport protocol might have excelled in their network.