Lookup Data in P2P Systems

This paper gives a brief summary of lookup operation in P2P networks. It gives an overview of why P2P networks are attractive, discusses the lookup problem, which is basically "Given data X stored in a set of dynamic nodes, how to find it". I really enjoyed reading the last section. The paper discusses talks about CAN, Chord, Kademlia, Pastry, Tapestry and Viceroy.

All these DHTs use different overlay networks (underlying topological structure). Different overlays have different complexity for lookup. Differences between DHTs include distance functions that are combination of being symmetric and unidirectional, cost of node join/failure operations when they happen frequently, network aware routing, malicious nodes etc.

I would recommend keeping this paper.

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

This paper talks about the Chord DHT and how it is useful. Instead of giving the complete summary of how it works I want to list the pros and cons of Chord.

The authors in Chord use ring geometry and choice of the DHT geometry greatly affects performance. "The Impact of DHT Routing Geometry on Resilience and Proximity" paper shows that amongst different DHT geometries ring geometry provides greatest flexibility. Another thing I like about Chord is its simplicity.

One place where Chord may not work well is in cases where there is lot of churning. This observation has been made by the Bamboo DHT designers. Also, Chord periodically performs stabilization. This requires that the periodic epoch needs to be tuned as per the need of the network where the nodes reside. Another thing that Chord does not consider is the network topology. DHTs like Tapestry and Pastry take into consideration the network locality and try to minimize the distance traveled by messages.

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

Active networks allow individual user, or groups of users, to inject customized programs into the nodes of the network. This aids in building a range of applications that can leverage computation within the network. The authors in this paper use ANTS active network toolkit in designing and implementing active networks and share their experience.

The authors express their findings in comparison to the general vision of active networks in three areas:

1. Capsules: They can be a competitive forwarding mechanism whenever software-based routers are viable. Capsule code can be carried by reference and local on demand. The cost of capsule processing is not high when forwarding is also performed in software.
   
2. Accessibility: Each user can handle their packets within the network. Also, code from untrusted users should not do any harm to users of other service.
   
3. Applications: Capsules aid in experimenting with new services and deploying them.

The concept of active networks is new to me. The paper was good to read because it talked about the issues active networks have and how the authors experience these issues and resolve them. The only thing that concerns me is the issue that a malicious member of a group can harm other users of the group. The authors talk about this problem and also say that it is not specific to active networks.

Resilient Overlay Networks

This paper proposes an architecture that enables a group of nodes to provide communication in case of failures in the underlying Internet paths. Group of nodes in RON have an application-level protocol for communicating with the other nodes in RON. The protocol ensures that high-speed recovery of path failures, low-latency, and improved loss rate and throughput exist among the nodes participating in the RON.

RON was designed to improve the underlying Internet routing protocols (BGP). BGP can take a long time to converge after link failure. RON aids in recovering from outages and performance issues in seconds. Other goals of RON are tighter integration of routing and path selection with the application and expressive policy routing.

I liked that the authors are proposing an architecture to solve the inherent problem of BGP convergence. Although there are issues that still remain undressed. These include machines behind NAT and violation of BGP policies. The authors discuss these problems as well. The evaluation results are very good but with such techniques one is never sure how they will work in real large scale deployment. Also, it would have been nice see how RON would work in case of congestion, that is how tolerant is RON itself? One more concern I have is related to RONs pushing too aggressively to find alternate routes. This can cause a lot of traffic and be very expensive.

I would recommend keeping this paper because it can stir up a very good discussion in the class regarding the design decisions and their pros and cons.

A First Principles Approach to Understanding the Internet’s Router-level Topology

The authors in this paper argue that previous researchers who have analyzed the structure of Internet topology have not considered factors like router technology and network economics. There can be other key factors that affect the structure and should be taken into consideration along with using statistics and graph theory. The paper considers router capacity constraints, as well as likelihood to model router-level topologies and discuss understanding the evolution of networks in order to accurately model router-level graphs.

I agree with the arguments proposed by the authors. One thing that comes to my mind is how BGP is greatly influenced with the economic policies integrated in making route decisions. Thus, while understanding the Internet topology, router technology and network economics play an important role. The authors discuss different factors and also discuss the importance of robustness of the network to node /link failures. The authors do not discuss about this feature because of its complexity. It will be nice to discuss how robustness complicates the model and how much does it affect if not considered.

On Power-Law Relationships of the Internet Topology

This paper analyzes Internet and describes three power laws of the Internet topology. The reason these laws are important is that they aid in understanding the topology of the Internet and help in designing more efficient protocols. Also, we can design more accurate simulation models as well as estimate topological parameters for analysis of protocols and speculations of the Internet topology in the future.

The authors use three inter-domain level instances of the Internet from 97-98 during which the topology grew by 45%. They also used the router-level instance of the Internet in 95. The three power laws are:

1. Rank Exponent: The out-degree of a node 'v' is proportional to the rank of the node to the power of a constant
2. Out-degree Exponent: The frequency of an out-degree 'd' is proportional to the out-degree to the power of a constant
3. Hot-plot Exponent: The total number of pairs of nodes within 'h' hops is proportional to the number of hops to the power of a constant

It is observed that all the laws are expressions of the form "y is proportional to x to the power of constant a". Some of the constant do not change significantly over time. During 1998 the power laws linearly fit in log-log plots and the correlation coefficient of the fit is at least 96%.

The paper used real-data for evaluation and used more than one instance of the dataset. The authors argue that the power-laws apply to a range of values because their analysis shows similar results for datasets that were taken when the Internet changed drastically.

The main thing that comes to my mind is the validity of the power laws in the current Internet topology. Do these laws still hold? It will be nice to have a discussion about this. I would recommend keeping this paper because this paper puts forward laws that can be used to design simulation models that are similar to the current Internet topology.

XORs in the AIR: Practical Wireless Network Coding

This paper discusses COPE that exploits network coding theory techniques to improve throughput in wireless networks. COPE also exploits the shared nature of wireless medium. Briefly COPE uses following techniques:

1. Opportunistic listening - Exploiting the shared nature of wireless medium, COPE sets the nodes in promiscuous modes and makes the nodes snoop on all communications over wireless medium and store overheard packets for time T. Reception reports are sent back.
   
2. Opportunistic coding - A node codes multiple packets together such that all the neighbors that will receive the packet can decode.
   
3. Learning neighbor state - Each node has to know what packets its neighbors contain. Each node announces to its neighbors its reception report. In case of loss of these reports wireless routing protocols compute the delivery probability between every pair of nodes and use it to identify good paths.

COPE is the first architecture that uses wireless network coding that has been deployed and provides a study of the results. The results show that network coding can improve wireless throughput. Congested UDP flows have throughput gain of 3-4x. In case of TCP their is not much significant improvement. The gain depends on the traffic pattern as well as the coding opportunities available.

The paper is interesting to read because it portrays implementing the theoretical concept of network coding into reality. Something that concerns me is the variation of results based on the type of the network, its topology and traffic pattern. This raises the question of how well COPE will work in real world deployment?