Thursday, October 30, 2008

Chord

This paper describes in detail the design and implementation of Chord DHT system. It is a dynamic system that allows efficient content retrieval based on key value pairs and without centralized coordination.

The central idea to CHord is consistent hashing to allow some ways of balancing the load on different nodes in the chord ring. To further enhance the performance, Chord uses finger tables to allow O(log n) look up time of a particular key in the ring.

There are a couple of issues in this paper that were not clearly addressed. Issues such as fault recovery and migration of state between nodes on a planned take down of a node seems central to the correct functioning and operation of chord ring but received very little attention.

Another problem with this design is the latency in the lookup. Although Log(n) in terms of number of nodes in the hash space, the delay is still significant. Also each hop in the chord ring is an overlay and might translate into multiple hops in IP.

Overall, I still like this DHT compared to others in that it is simple to follow and works reasonably well. As system designers, in many cases, we tend to over design a system and makes it difficult to get implementation right. At some point, law of diminishing return kicks in and it is better to use the simpler design. I think Chord strikes a balance between simplicity and functionality, which is why it is one of the more popular DHTs.

Looking up data in P2P systems

This paper discusses reason behind P2p DHT like systems. Main reason for it is for fault tolerant data look up. They depend on symmetric lookup instead of hierarchical lookup. This way, no single failure is going to bring down the network , however, they tend to not scale as well.

The paper compares different DHT systems based on how they organize the data structure for key lookup. (tree vs. skiplist) and poses a number of open problems.

I like this paper because it gives a gentle introduction to set of problems in DHT and motivation behind it. It also gives nice taxonomy of different DHT project, which serves as a nice lead in to Chord.

Active Network

This paper talks about Active Network. Active networks allows per packet specific processing and embed the processing inside of packet using the concept of a capsule. This gives the network the flexibility to adapt to different need quickly and allows rapid deployment of new protocols.

The main problem that I see and author recognize in this setting is security and performance. To address security, they are using a restricted subset of Java. However, I don't think they are considering the problem of resource exhaustion. Of course, they have a certificate based solution as back up. However, that is very heavy weight, and usually the root trust has to be traced to one entity. I doubt all the networks in the world would trust a single entity to certify active code running in their networks. Subtle problems such as routing loops can occur simply because of a bug. Performance is also a critical issue. If the active content is not cached at the node, loading the node could introduce significant latency.

I like this paper in the curriculum because it introduces necessary background of active networks and gives some reflection on the experience of implementing such a toolkit.

Sunday, October 26, 2008

RON

This paper describes an overlay network that is designed to improve recovery time in routing when failure happens and integrate path selection and routing more tightly with distributed applications. They argue that BGP infrastructure takes too long to stabilize.
Ron addresses this by forming a relatively small scale overlay network and maintain link state information to other Ron nodes. It actively sends out probes periodically to detect outage relatively quickly.

I like this paper because it gives a clear goal of overlay networks. It is usually designed to solve a particular issue that is difficult to solve without overhauling entire routing protocol. (in this case, BGP) However, just by limiting the scale of the problem and implementing functionality at application level, RON provides a practical path to deploy such systems. I think that is generally a big win for overlay networks and that's why they have been such active research areas.

Tuesday, October 21, 2008

Power Laws of Internet

The authors proposed thee laws of power relationships on the topology of the Internet and used measurement studies on a sample of the Internet to validate these proposals.
1. The outdegree of a node is proportional to the rank of the node to the power of a constant.
This is useful to estimate the number of edges in the Internet as the function of number of nodes.
2. The frequency of an outdegree is proportional to the outdegree to the power of a constant.
3. The eigen values of a graph is proportional to the order to some power of a constant.

I find this paper to be somewhat strange. The author proposed three laws based on some intuition and used specific sample to validate those claims. This somehow lacks rigor and it seems to be that there is no way to know if the same law holds today without redoing a comprehensive measurement. Perhaps there is something significant that I am missing, but I find this paper to lack some rigor and I was hardly convinced after reading it.

Thursday, October 9, 2008

XORs in The Air: Practical Wireless Network Coding

This paper describes COPE, an encoding scheme that takes advantage of the wireless broadcast communication pattern to mix packets from different sources together to increase the amount of information conveyed using a fixed amount of packets sent.

This is definitely a neat idea. However, this scheme seems rather complex to implement because it violates so many assumptions that network applications now assumes. TCP scheme will likely not work well with this either since the batching of packets can be seen as a source of delay.

Wednesday, October 8, 2008

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

This paper describes a technique that combines MAC layer and routing together. This breaks the conventional layering structure in network protocol, but offers better throughput as now it takes advantage of the slight chance that some packets might get "lucky" and travel further than it could reliably transfer.
The main problem with this scheme is how to prevent the overhead of communication between the recipients from overwhelming the benefit the scheme might offer. ExOR did the following:
1. batching of packets
2. use of batch map with packet transfer so that information is transferred at the same time as verifying the previous hop's transfer.
However, because this scheme is not compatible with existing TCP protocol, dedicated proxy is required to convert TCP connections into this kind of connection. This could be an obstacle that prevents its wide deployment. Many other technically superior solutions are not deployed because of compatibily issues.

Sunday, October 5, 2008

A High-Throughput Path Metric for Multi-Hop Wireless Routing

This paper describes the underlying routing protocol used in Roofnet, called ETX (expected transmission count). The key idea is that wireless medium breaks the assumption that link is either working or not working. Minimal hop count can be suboptimal because the smaller the number of hop is, the chance of a weak link increases. Instead, ETX considers three factors: transmission loss ratio, assymmetry in the network link quality, interference causing reduction in throughput as the number of hops increase.

I liked the paper because this scheme neatly integrats all of the three mentioned dimensions that affect the throughput of the route. It also has extensive evaluation to prove the ETX is more optimal than minimum hop count in most cases.

The environment described in this paper is very similar to that of Roofnet. Certainly in a loosely connected Roofnet environment, because ETX considers link quality in its routing decision, it provides better quality routes. However, if the environment is changed to a densely connected, corporate environment, would ETX's overhead of link probing make it unsuitable candidate to use in these settings? Even in roofnet, some parts of it (i.e. near MIT campus) would be much densely connected. In these settings, I would argue interference is much more important factor to consider than loss ratio. Smart channel allocation will probably provide a much better gain in throughput.

Thursday, October 2, 2008

Architecture and Evaluation of an Unplanned 802.11b Mesh Network

Compared to the previous paper, which takes the route of simulation, this paper is much more convincing since it carries a physical deployment in a real environment. There are so many factors not modeled(or difficult to model correctly) that can have significant impact on network performance in complex urban neighborhood. (Obstruction, interference , etc.)

The main contribution of the paper is the evaluation of the multi hop routing performance and their routing protocol Srcr which tries to find highest useful throughput rate between any pairs of nodes. It seems plausible in urban environment because of the high density of quality links, this sort of sharing between different home users can boost speed even higher (due to time multiplexing) and possibly guard against outage of a single provider.

Modeling Wireless Links for Transport Protocol

This paper summarizes a series of issues in current modeling of wireless links and how these inaccuracies can lead to potentially incorrect design decisions for transport protocol. As the underlying link layer characteristics change, the upper layer would need to adapt as well to perform optimally.

This paper characterizes many aspects and details of wireless network that makes it so hard to get accurate model. However, after reading it, I only feel that no matter how careful my model is, it is still not going to represent reality accurately enough. Certainly modeling is much more efficient to evaluate a new protocol or a proposal to change an existing protocol, but all I got from the paper is that modeling is probably never going to be good enough. Now I feel to make a very convincing argument, I will need real deployment data. Perhaps modeling would only serve as a first level filter in a feasibility study.

That leads to my second question. Given limited time to develop a model just to check if my protocol has a chance to perform well, which of these characteristics should I consider. This was not answered in the paper, and I feel that would benefit me and other network researchers a lot.

This paper is still an excellent paper to read, since it summarizes many link layer characteristics in different wireless networks that directly lead to many decisions that we made at the transport layer. It also serves well in the curriculum as a lead-in to a number of more detailed wireless papers.