Tuesday, November 3, 2009

Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications

I. Stoica, R. Morris, D. Karger, F. Kaashoek, H. Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications," ACM SIGCOMM Conference, 2001.
This paper talked about Chord, a distributed lookup protocol that tries to address the lookup problem (finding the node that has a particular key mapped to it) in a simple and provably correct manner.


Chord Protocol Design
  • Consistent Hashing: The hash function assigns each node and key  an m-bit identifier using SHA-1 by hashing the node's IP address and key value respectively. An interesting issue that the authors analyzed here was what if any malicious node keep on producing keys that hash to a particular node thereby overloading it? However, the authors claim that producing such a set of keys that collide under SHA-1 is equivalent to inverting or decrypting the SHA-1 function and is considered NP-hard.
  • Scalable Key Location: Every node maintains something which is called the finger table. The ith entry in the table at node n corresponds to the tuple < n+2^(i-1), successor(n+2^(i-1)), IP Address>. Now whenever a query to a particular key k is made, the node searches for i and j in the finger table such that n+2^(i-1) <= k < n+2^(j-1) and routes it to successor (n+2^(i-1)). The requests are made in this iterative fashion until the node with the key is found. The authors highlighted that this takes O(log N) lookups in the worst case.
  • Node Joins: To ensure concurrent node joins, chord makes 2 invariants, each node's successor is correctly maintained and for every key k, the node successor (k) is responsible for k. These invariants help in ensuring success of each node join operating. The new node must update its successor with the help of any node that it knows of and fetch its key responsibilities. This takes O(log N*log N) messages.
  • Stabilization: This helps in stabilizing the system in case of frequent disconnects. It works to update predecessor entries, periodically verify a node's immediate successor and periodically refreshes finger table entries. An interesting result was that as long as updating fingers take less time than it takes the network to double its size, lookups will continue to be O(log N) hops.
Finally, the authors evaluated the protocol on an iterative simulator and analyzed numbers for load balancing, path lengths, system behavior in terms of node failures and lookups during stabilization phases. The results matched the design expectations and were encouraging. Apart from a slight mismatch in graph numberings at quite some places, the graphs were pretty easy to read.


Comments

This paper definitely deserves to be one of the highly cited papers in computer science. It was well written, presented a novel solution, the protocol was very simple and yet had strong mathematical backing to prove its correctness. However, there were few issues that Chord was unable to tackle:
  1. Anonymity: Chord doesn't provide anonymity. Its lookup operation runs in predictable time and always results in success or definitive failure.
  2. Network Locality: The node IDs are assigned randomly. This has the disadvantage of chord being unable to utilize network locality in its design.
  3. May result in temporary failures: In case of node joins, it may occur that nodes in an affected region may have incorrect successor pointers, or keys may not have migrated to newly joined nodes resulting in lookup-fail temporarily till the stabilization protocol fixes it.

Looking Up Data in P2P Systems

H. Balakrishnan, F. Kaashoek, D. Karger, R. Morris, I. Stoica, "Looking Up Data in P2P Systems," Communications of the ACM, V. 46, N. 2, (February 2003).
This paper gives a great overview of what was the state-of-art in 2003 in the domain of P2P computing, its advantages, proposed solutions and their limitations.  The authors highlight that P2P systems are attractive due to the following reasons:
  • Low initial setting up cost.
  • Tremendous computation abilities due to aggregation of resources.
  • Fault tolerance due to absence of single point of failure.
Most P2P system design, essentially try to solve the 'lookup' problem which is about finding a data item X that can be stored on one or more dynamic set of nodes in the system. In the past, following approaches had been considered:
  • Maintain central database: Consisting of mappings between file name and location of servers. Napster did this. Advantages are that it is simple to implement and doesn't require many hops, but results in scalability and resilience problems.
  • Hierarchy: Idea on the lines of DNS that lookup should be hierarchical. Disadvantage is that nodes higher in the hierarchy are 'more important' than others and their failure may be catastrophic to some or all parts of the system.
  • Symmetric lookup algorithms: Here, all the nodes are treated as equal. These schemes allow nodes to self-organize into an efficient overlay structure. There are many flavors of these algorithms from Gnutella (broadcast approach) to Chord (logarithmic hop approach).
Further, the authors discussed about various issues in implementing the DHT which involves a load balanced way of mapping keys on nodes (which I will discuss more in the Chord blog entry) and the design of 1-Dimensional Routing lookup algorithms like Chord, Tree-based routing algorithms like Pastry and Multiple Dimensions routing algorithms like CAN. Each of them have their own set of advantages and disadvantages and it is really a matter of tradeoffs and performance metrics that would decide which is the best.

Comments

In the end, the authors raised some very good questions on the future of P2P computing. I particularly found the concept of proximity routing quite interesting.
  • Proximity Routing: Broadly, I would define it as the overall motive of taking a particular file from the user that is closest to me in terms of routing distance, thereby minimizing network bandwidth utilization as well as latency. However, there is a trade-off in such a design of assigning consecutive IDs to nodes in the same network as that network's failure can cause a consecutive chunk of nodes to go offline thereby affecting performance. It would be interesting to know if some system leverages this trade-off and has come up with a hybrid heuristic of sorts.
Further, as an interesting aside, these system always talked about a uni-directional way of locating files. That is if I want to search for key K, I initiate a request in only 1 direction, and move towards getting the key. What about a system that could send multiple requests to adjacent nodes something on the lines of how gossip protocols work? One obvious negative would be additional network utilization but it would be interesting to know if it could result in quicker lookups. This option makes much more sense with multicore processors and multi-threaded applications where they all can simultaneously send lookup requests.

Thursday, October 29, 2009

Active Network Vision and Reality: Lessons from a Capsule-Based System

D. Wetherall, "Active Network Vision and Reality: Lessons from a Capsule-Based System," 17th Symposium on Operating Systems Principles," (December 1999).
 Active Networks are a novel approach to network architecture in which customized programs are executed within the network at various network elements along the path to the destination. The source node is empowered to run routines on various active node on its path to the destination which not only aids in experimenting new Internet services and facilitates their easy deployment but also enables dynamic routing on a per-application basis.  Various performance and security issues that may result from the execution of untrusted and mobile code are dealt by ANTS as follows:
  • Security Issues:  Constraints have been placed on the forwarding routine disallowing changes in path and certification by a third party CA is required to impose additional security. Further, hashes are used to perform integrity checks.
  • Performance Issues: Upper limits are placed on the size (16 KB) and running time on the subroutine codes for security as well as performance purposes. Further, ANTS active network toolkit also uses active caching and loads code on-demand before execution.
Overall, this seems like a great idea. It gives the source node the ability of dynamically choosing the best suited forwarding routine on a per-application basis. No doubt, this service needs to be deployed in an incremental fashion in the Internet, something that the author did not address explicitly. However, despite being a good clean slate design idea, it raises quite a few issues:
  1. Violation of strict end-to-end principle. Does the performance increase justify this?
  2. Limitations on the type of services due to size and runtime limitations on code execution.
  3. Security issues arising from execution of third party code still remain a concern. I personally felt that relying on third party certifying authority was not very clearly explained. Moreover, even though limits were placed on size and runtime of code, the system may be still vulnerable to coordinated attacks which have DDoS like nature.
  4. Maybe I missed it, but I failed to see if there would be any incentive to the ISP to allow active node routers in the path.

Resilient Overlay Networks

D. Andersen. H. Balakrishnan, F. Kaashoek, R. Morris, "Resilient Overlay Networks," 18th Symposium on Operating Systems Principles, (December 2001).
 Resilient Overlay Network is an architecture that allows distributed Internet applications to detect and recover from path outages and periods of degraded performance within a matter of seconds. The idea is that by building an application level overlay network, we can achieve an increase in performance as well as reliability. The overall concept of RON involves a small group of nodes spread across the network in multiple ISPs. They keep pinging each other and help in creating a global state of 'link healths' (similar to link state concept) and decide to overlay packets between hosts either directly or through intermediate host(s) based on the global link health information. This helps in circumventing policy restrictions imposed by ISPs, helps it in adapting to network conditions or helps in customizing to various applications such as video/voice etc.

Overall, the analysis was definitely encouraging. It was observed that overlay network reacted to failures in a matter of seconds as opposed to BGP which takes many minutes before restoring original flow. An interesting phenomenon was observed that RON paths were actually shorter that BGP paths. My only point of critique/concern with this paper would be as to how feasible would be its wide deployment? Wouldn't the ISPs be concerned about the fact that overlay networks mess with their traffic engineering? Wouldn't this make them take steps against it? Further, issues involving large scale deployment (and probably resulting congestion due to control place information) aren't really tackled in the paper. It would be interesting to discuss these aspects in class.

Tuesday, October 27, 2009

On Inferring Autonomous System Relationships in the Internet

L. Gao, "On Inferring Autonomous System Relationships in the Internet," IEEE/ACM Transactions on Networks, V. 9, N. 6, (December 2001), pp. 733-745.
 This paper talked about how the author classified various types of routes that appeared in BGP routing tables based on AS relationships and presented an heuristic algorithm that inferred these relationships from the routing table. The underlying theme of this paper was that connectivity does not imply reachability. So, in order to study the sturcutre of the Internet, it is not just sufficient to study the graph topologies as reachability also depends a lot on inter domain policies between different ASes managed by different ISPs.

ASes may fall into one or more of the following categories: Provider, Customer, Peer or Sibling. Based on this, we can have following Relationships:
  • Customer-AS: AS exports all its routes, other customer's routes as well as provider and peer routes to the customer.
  • AS-Provider: AS usually doesn't export its provider and peer routes and only exports customer routes.
  • AS-Peer: AS can export its routes and its customers' routes but usually doesn't export its provider or peer routes.
  • AS-Sibling: AS exports its routes, routes of customers as well as provider and peer routes.
The essential theme of this paper is the 'Valley Free Property" that exists in the Internet between different ASes.  Intituively, considering Customer --> Provider relationship to be "going upwards", Provider --> Customer relationship to be "going downwards", and Peer --> Peer and Sibling --> Sibling relationships to be at the "same level", Gao proved that the Internet can never have a "Valley". This helped her to propose an algorithm that could identify quite accurately how the various ASes were connected. The first phase of the algorithm consisted of walking on a path connecting various ASeS and finding for each node, its set of neighbors as well as its out-degree. This then classified AS pairs into provider-customer or sibling relationships. Then the second phase identified AS pairs that did not have a peering relationships and finally the third phase assigned peering relationships to AS pairs.


Comments

The paper was well written, clear in explanation and it was particularly helpful to understand the algorithm due to the incremental way it was proposed. My only concern would be how much accurate these identification of relationships can be? As highlighted, the repository for BGP routing relationships is not always accurate and peering relationships might well be protected by contractual agreements. Doesn't this puts an open question on the results?

On Power-Law Relationships of the Internet Topology

M. Faloutsos, P. Faloutsos, C. Faloutsos, "On Power-Law Relationships of the Internet Topology," ACM SIGCOMM Conference, (September 1999).
This paper talks about some very interesting power laws that exist in the Internet. Despite the widespread randomness of the Internet, the authors discover some surprisingly simple power laws of the Internet topology. These were discovered by extensive real world measurement data and using least square fit methods subsequently on the plots. The correlation coefficients of 96% or higher imply that the power laws are more that just a coincidental discovery.

Power-laws are expressions of the form y = k * x^a where k and a is a constants, x and y are the measures of interest. The entire work is based on extensive measurements of the Internet. The authors had to their disposal 4 datasets, 3 of which consisted of inter-domain topology data from Nov 1997 to Dec 1998 and the 4th consisted of the router topology data in 1995. The following were the 3 power laws discovered:

Power-Law 1 (rank exponent): The outdegree, dv, of a node v, is proportional to the rank of the node, rv, to the power of a constant R.

Power-Law 2 (outdegree exponent): The frequency fd of an outdegree d is proportional to the outdegree of the power of a constant O.

Power-Law 3 (eigen exponent): The eigenvalues of a graph are proportional to the order of the graph to the power of a constant E.

Comments

An important take-away from this paper is that most of the distributions of interest are skewed (as illustrated by the power law) which makes the use of 'average values' totally misleading while studying the Internet. Power laws are no doubt really helpful in predicting the future of the internet and as well as studying the performances of new protocols that are being created for the Internet. However, my only point of critique about this otherwise very well written paper would be an inadequate analysis of why exactly these power laws hold in the Internet. As highlighted by the authors in the beginning, that in case of some drastic changes in policies or topologies, these power laws may fail to hold. I think it would have been really great had the authors talked a bit more about what these 'drastic changes' may be. Specifically, what are the underlying assumptions that make the power law hold. This would have been very important particularly in the current scenario in which the whole Internet is divided into various ASes and their policy decisions have the potential of having considerable effect on the Internet routing.

Monday, October 19, 2009

White Space Networking with Wi-Fi like Connectivity

P. Bahl, R. Chandra, T. Moscibroda, R. Murty, M. Welsh, "White Space Networking with Wi-Fi like Connectivity", ACM SIGCOMM Conference, (August 2009).
This paper presented WhiteFi, the first WiFi like system constructed on top of UHF white spaces. WiFi builds on a technique called SIFT (Signal Interpretation before Fourier Transform) that helps in reducing the time to detect transmissions in variable width systems by analyzing raw signals in time domain. To elaborate the problem in a bit more detail, FCC recently has permitted the use of unlicensed devices in the frequency band of 180 MHz to 512 MHz comprising of 30 channels (21 to 51 with the exception of 37) of 6 MHz each. This opened up a great opportunity of have a WiFi like system on this White Space instead of conventional ISM bands. However, FCC directive requires that communication must not interfere with already existing communication on the channel due to TV channels or microphones. This makes the problem very interesting due to 3 characteristics:
  • Spatial Variation: 'Channel use'  is dependent on the location of sender and receiver. Hence there should be a way of communicating as to which channels are busy and which of them are available.
  • Spectrum Fragmentation: The UHF white space are often fragmented due to presence of incumbents. The size of each fragment can vary from 1 channel to several. A bigger contiguous channel = More Throughput! So it is the responsibility of the protocol to look for contiguous channels.
  • Temporal Variation: UHF band also suffers from temporal variation due to widespread use of microphones. Hence the protocol was designed to be robust to these changes in band availability.
The WhiteFi protocol takes all the above characteristics into account and was developed on the KNOWS hardware prototype. The spectrum assignment policy involves the exchange of a spectrum map and airtime utilization vector between the AP and the client to find out which of the channels are free for use at both the ends. Such a design tackles the problem of spatial variation. Further, once the AP gets the utilization vector, given a range of UHF channels, it calculates the MCham (multichannel airtime metric) and chooses the set of channels with maximum MCham. Further, SIFT is used for efficient variable bandwidth signal detection. The authors propose 2 algorithm choices for the same -- the Linear SIFT-Discovery Algorithm (L-SIFT) or the Jump SIFT-Discovery Algorithm (J-SIFT). J-SIFT outperforms L-SIFT when number of channels is greater than 10.

The evaluation was done using a combination of simulations and experiments and the results pretty much matched the expectations. J-SIFT pretty outperformed both Baseline non-SIFT and Linear SIFT in time taken to discover the AP. Overall WhiteFi due to its adaptive nature was successful in asserting its supremacy over any other static optimal implementation of channel communication policy. Particularly, figure 14 was a treat to watch that highlighted how well the protocol behaved to changes temporal changes in spectrum.

Critiques

This is definitely one of the very good papers we have read as part of this course. Not only does it tackle a very real problem, it presents a efficient and optimal solution which works despite the stringent constraints laid down by FCC. However, I have few comments on this paper:
  1. I thought the paper lacked some analysis on how does the protocol behaves when multiple microphone users interfere on a regular basis (that is how efficient is the J-SIFT based channel hopping). Though Fig. 14 provided some insight, it would have been great to have a deeper analysis involving throughput/overhead over a relatively long period of time.
  2. Theoretically, all the channels could be busy when someone wants to communicate. Isn't that a big usability issue -- 'My Internet may or may not work'! Is it really the case? Can all frequencies between 180-512MHz be assigned for TV/Microphone transmissions?