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?

ExOR: Opportunistic Multi-Hop Routing for Wireless Networks

The authors in this paper propose a technique that is very different from traditional routing schemes. In traditional routing protocols the receiver of the packet is chosen before forwarding the packet. ExOR proposes forwarding the packet to a set of nodes and later deciding which node will forward the packet to the destination. The idea is to exploit the broadcast nature of wireless medium.

ExOR technique involves:

• Source operating on batches of packets. This is done to reduce the communication involved for synchronization.
  
• The source node adds a list of candidate forwarders (sorted in descending order of priority) to each packet in the batch and forwards the packet to all the candidates. Priority is based on the distance of the node from the destination.
  
• Highest priority node then forwards the packet further with its list of candidate forwarders.
• Remaining forwarders transmit in order but only send packets that have not been acknowledged in the batch maps of the higher priority nodes.
• The forwarders continue to cycle through the priority list until 90% of the packets have been received by the destination.
• Remaining packets use traditional routing.

Without going into too much details I just want to go through the advantages of the scheme and then talk about things that concerned me.

Pros:

1. Takes advantage of the broadcast medium
2. Opportunistically takes advantage of long lossy links
3. Provides reliability through diversity
4. Low priority nodes will most likely not forward packets
5. ExOR protocol improves throughput by a factor of 2 or 4 over ETX since it uses multiple relay nodes to forward the packet to the destination.

Concern:

1. ExOR scheme suggests that forwarders (other than the highest priority forwarder) transmit packet if there are unacknowledged packets that were sent by the higher priority node. This means that the higher priority forwarders have to communicate to other forwarders that the packet has not been acknowledged. This seems to be too much of a communication overhead.
2. There is too much state to be kept with each node. Each node has to store each packet it receives in its buffer.
3. After 90% packets have been received rest of the packets use tradition routing. Also these 90% packets can take different routes. Thus, the rate at which packets are arriving at the receiver may vary a lot.
4. There seems to be not much study about the interference of communication between forwarders.
   

A Performance Comparison of Multi-Hop Wireless Ad Hoc Network Routing Protocols

This paper provides an analysis on the comparison of a variety of multi-hop wireless ad hoc network routing protocols. The ad hoc routing protocols evaluated are:

1. DSDV (Destination Sequenced Distance Vector) - It is a hop-by-hop distance vector routing protocol that requires each node to periodically broadcast routing updates. This guarantees loop free routing. DSDV maintains a routing table that lists the next hop for each destination. Each route update is tagged with a sequence number and route R is updated only if the update message has a higher sequence number than old update message.
   
2. TORA (Temporally-Ordered Routing algorithm) - This is a distributed routing protocol based on link reversal algorithm. It discovers routes on demand, provide multiple routes to a destination, establish routes quickly and minimize the communication overhead by localizing algorithmic reaction to topological changes.
   
3. DSR (Dynamic Source Routing) - The header of each packet carries the complete ordered list of nodes through which the packet must pass.
   
4. AODV (Ad Hoc On-Demand Distance Vector) - This is a combination of both DSR and DSDV.

These four protocols are compared based on:

1. Path Optimality - Number of hops a packet took to reach its destination compared to the length of the shortest path in the network
   
2. Packet Delivery Ratios - Packet loss rate seen by the protocol.
   
3. Routing Overhead - Total number of routing packets transmitted during the simulation

The paper has made a lot of observations in their comparison analysis. It has been observed that both DSDV-SQ and DSR use routes very close to optimal while TORA and AODV-LL have a significant tail, TORA is not designed to find shortest path, DSDV performs well in low node mobility, AODV performs as well as DSR.

Things I would like to take away from the paper is the ns network simulator extension. I agree with Stephen about the point that performance should have been evaluated with several models.

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

This paper talks about ETX metric that ensures finding high-throughput paths in a wireless network. The authors argue that most protocols in wireless networks concentrate on minimizing the hop count when choosing paths for routing. Minimum hop count can maximize the distance traveled in each hop and large travel distances are likely to increase losses due to loss in signal strength. They propose ETX that requires few expected number of transmissions required to deliver packets to the destination.

As stated in the paper "ETX of a link is the predicted number of data transmissions required to send a packet over that link including retransmissions. ETX of a route is the sum of the ETX of each link in the route". Each link's ETX is calculated using forward and reverse delivery ratios of the link. Delivery ratio is the measured probability that a packet(data or ACK) successfully arrives at the recipient.

The main thing to take away from the paper is that the performance of a route is dependent on the packet delivery rate of the links. The packet delivery rate takes into consideration both the directions of communication where one direction is used to sending data and the other is used for sending ACKs.

The ETX metric performs better than shortest hop count routing protocols. It considers lossy links, asymmetric links and interference while choosing the routing path. The issues that still remain unanswered are network load (it does not consider congestion) and adaptiveness to mobility.

ETX is computed by each node broadcasting a probe packet every second. The probe packets sent are of fixed size at an average rate of T. These packets may not depict the same loss rate that the data packets may face. This can happen because data packets may be coming at a much higher rate and their size may be different as well.

Architecture and Evaluation of an Unplanned 802.11 Mesh Network

The authors propose an architecture for wireless mesh network that has four goals:

• Unconstrained node placement
• Omni-directional antennas
• Multi-hop routing
• Optimization of routing for throughput in a slowly changing network
  

These goals provide the ease of deployment which is an important requirement for community wireless networks. The evaluation of the architecture is done by deploying 37 nodes spread over 4 square kilometers of urban area.

The evaluation determines the end-to-end performance of Roofnet and the effect of the design decisions. The measurements are based on:

• Multi-hop TCP data: 15 second one-way bulk TCP transfer between each pair of Roofnet nodes
  
• Single-hop TCP: direct radio link between each pair of routes
  
• Loss matrix: loss rate between each pair of nodes using 1500-byte broadcasts
• Multi-hop density: TCP throughput between a fixed set of four nodes varying the number of Roofnet nodes that are participating in routing

The end-to-end performance of Roofnet is determined by the basic performance, link quality and distance, effect of density and mesh robustness.

I liked the fact that the paper uses a network that is deployed in the real world to evaluate the architecture. This aids in understanding the real-time traffic and how the network works in such scenarios. Another thing to take away from the paper is how the authors have taken great care to provide ease of deployment and maintenance. This aided in deployment of Roofnet by volunteer users.

The evaluation shows that the average throughput decreases to 43% if the best two nodes are lost. This can be a huge problem because you are relying on these two nodes for higher throughput. Another thing that is not clear to me is how crucial is their placement of few nodes at the top of tall buildings? The paper lacks investigating the architecture in terms of the dynamics of the network. It does not handle the effects of user joining/departing and also about varying network performance over time.