A Scalable Peer-to-peer Lookup Protocol for Internet Application - Annotated Bibliography Example

Node location is always the major problem of a peer to peer application. A solution to this problem would be the implementation of Chord. It works by assigning a key to a node thus data location and any data queries become very efficient. In addition to that, chord is very scalable. INTRODUCTION Peer-to-peer systems basically do not have a centralized location, thus they are characterized by features such as redundant storage, permanence, anonymity, search, authentication and hierarchical naming. Despite this rich set of features, the core operation in most peer-to-peer systems is their effective search capability of data items (Look up protocol is efficient), data item accuracy, performance and simplicity. SYSTEM MODEL Chord addresses the following problems with the model that it has been designed with. Load balance: this is done by assigning keys to each node or data item. This is implemented through its hash function. Decentralization: All nodes are equally important. Scalability: a Chord look up can grow as large as it can, so do the costs associated with it. Availability: Chord automatically shows what tables are new and those that have failed so as to allow or easy key disbursement. Flexible naming: Chord allows for flexible mapping of names to its keys. CHORD APPLICATIONS Cooperative mirroring: this is where organizations can be able to store and use each other’s data. Time-shared storage where an individual may wish to make data available at their request and the server occasionally available. Distributed indexes so as to assist in data search. Large-scale combinatorial search that is searching that involves a variety of keys for data search. References Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek, and H.Balakrishnan, "Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications" Abstract—Content-Addressable Network (CAN) is a distributed infrastructure that aims to make improvise the use of hash tables. INTRODUCTION A hash table is a data structure used to map “keys” into data items. With that, hash table functions are implemented in Content-Addressable Network (CAN). The CAN model has its advantages such as its scalability, fault-tolerant and it completely self-organizes itself. Other variables such as its scalability, robustness and low-latency properties are better demonstrated through simulation. CAN is constructed in 3 steps: 1. First step is for the new node to look for a node existing in the CAN. 2. Secondly, using the CAN routing mechanisms, it must find a node whose zone will be split. 3. Thirdly, the neighbors of the split zone must be noticed so that routing can include the new node. Related Systems Domain Name System: stores key value pairs of the domain name or IP address. When compared to CAN, CAN is more general than the DNS and again CAN resolves name resolution is independent thus the two systems’ designs are different. Publius Publius is a Web publishing system that is highly resistant to censorship while it provides anonymous publishing. CAN design can be implemented in the Publius design so enable it to access a large number of servers. Peer-to-peer file sharing systems: used to share files in the network. Common file sharing systems include, Napster and Gnutella. References S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Shenker, "A Scalable Content-Addressable Network" Abstract— Pastry is a scalable and distributed object locator and routing substrate for wide-area peer-to-peer applications. Its main goal is to perform routing, data storage, data sharing, group communication and naming on larger networks and that is where it strength lies. When its presented with a message and a key, a Pastry node routes the message to the node with the specified nodeId. For referral purposes, each Pastry node keeps concurrent data records with reference to nodeId space, and notifies applications of new node arrivals, node failures and recoveries. Pastry takes into account the network locality; it seeks to minimize the distance a sent or received message travels. Pastry is completely decentralized, scalable, and self-organizing; it automatically adapts to the arrival, departure and failure of nodes with the use of ode ID’s. INTRODUCTION Peer-to-peer Internet applications have been popularized through file sharing applications like Napster, Gnutella and FreeNet. Thus peer- to-peer systems have revolutionized and implemented technical aspects such as decentralized control, self- organization, adaptation and scalability. Peer-to-peer applications are thus distributed systems where the nodes have identical capabilities and all communication between the nodes is symmetric. Related Work File sharig facilities In use include: Gnutella and Freenet. The Napster is a music exchange service that uses the peer-to-peer systems but in essence it’s is not a fully peer to peer facility as it uses a centralized database. Sharing of data files on these systems is quite reliable. In Gnutella, using broadcast messages on a broadcast protocol limits the system’s scalability and thus incurs a high bandwidth usage. Both Gnutella and Freenet are not guaranteed to provide the desired results although Pastry, along with Tapestry, Chord and CAN can be used to find the desired results as they are both second generation peer to peer routing and location schemes. Pastry and Tapestry are slightly different in their network locality capabilities and in their quest to support replication, again Pastry is less complex. The Chord protocol is closely related to both Pastry and Tapestry. References Rowstron and P. Druschel, "Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-Peer Systems"  Abstract— this is a system that uses a novel XOR-based met- ric topology. The topology has the property that every message exchanged conveys or re- inforces useful contact information. The system exploits this information to send parallel, asynchronous query messages that tolerate node failures without imposing timeout delays on users. INTRODUCTION Kademlia is a peer-to-peer distributed hash table (DHT) that seeks to combine provable consistency and performance, , latency-minimizing routing, and a symmetric, unidirectional topology. Its characteristics are that it seeks to reduce the number of configuration messages nodes that is should send. Kademlia also introduces a parameter, α, that allows people to gain constant bandwidth for asynchronous lowest-latency hop selection and it also delays free fault recovery. Kademlia Protocol The Kademlia protocol consists of four Remote Procedure Callss: ping, store, find node, and find value. The ping RPC requests to find whether a node is online. store instructs a node to store a key value and pair it for later retrieval. Find node takes a 160-bit ID as an argument. The recipient of the RPC returns the IP address, UDP port, Node ID. It also triples for the k nodes it knows about closest to the target ID. These triple values come back from a single k-bucket, or they may come from multiple k-buckets if the closest k-bucket is not full. The RPC recipient must return k items (else when there are fewer than k nodes in all its k-buckets combined then it returns all nodes it is aware of.) Find value finds IP address, UDP port, Node ID. It then triples when it has received a store for the RPC key. It then returns the stored value. Routing Table Kademlia’s routing table structure is simple due to the protocol that has been used to implement it. The routing table is a binary tree whose leaves are k-buckets. Each k-bucket contains nodes with some common prefix of their IDs. The prefix is the k-bucket’s position in the binary tree. Thus, each k-bucket covers some range of the ID space, and together the k-buckets cover the entire 160-bit ID space with no overlap. Nodes in the routing tree are allocated dynamically, as needed.1 References P. Maymounkov and D. Mazi`eres, "Kademlia: A Peer to Peer Information System Based on the XOR Metric" Ben Y. Zhao, John Kubiatowicz, and Anthony Joseph. Tapestry: an infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01- 1141, U.C. Berkeley, April 2001. Read More