امروز سه شنبه ، ۱۴۰۱/۰۳/۰۳
بدان

آکورد: سرویس جستجوی نظیر در نظیر برای برنامه های اینترنتی: بخش 2: | Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications: part 2:

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

2- Related Work:

While Chord maps keys onto nodes, traditional name and lo- cation services provide a direct mapping between keys and val- ues.

A value can be an address, a document, or an arbitrary data item.

Chord can easily implement this functionality by storing each key/value pair at the node to which that key maps.

For this reason and to make the comparison clearer, the rest of this section assumes a Chord-based service that maps keys onto values.

DNS provides a host name to IP address mapping [15].

Chord can provide the same service with the name representing the key and the associated IP address representing the value.

Chord re- quires no special servers, while DNS relies on a set of special root servers.

DNS names are structured to reflect administrative boundaries; Chord imposes no naming structure.

DNS is specialized to the task of finding named hosts or services, while Chord can also be used to find data objects that are not tied to particular machines.

The Freenet peer-to-peer storage system [4, 5], like Chord, is decentralized and symmetric and automatically adapts when hosts leave and join.

Freenet does not assign responsibility for documents to specific servers; instead, its lookups take the form of searches for cached copies.

This allows Freenet to provide a degree of anonymity, but prevents it from guaranteeing retrieval of existing documents or from providing low bounds on retrieval costs.

Chord does not provide anonymity, but its lookup operation runs in predictable time and always results in success or definitive failure.

The Ohaha system uses a consistent hashing-like algorithm for mapping documents to nodes, and Freenet style query routing [18].

As a result, it shares some of the weaknesses of Freenet.

Archival Intermemory uses an off-line computed tree to map logical ad- dresses to machines that store the data [3].

The Globe system [2] has a wide-area location service to map object identifiers to the locations of moving objects.

Globe arranges the Internet as a hierarchy of geographical, topological, or administrative domains, effectively constructing a static world-wide search tree, much like DNS.

Information about an object is stored in a particular leaf domain, and pointer caches provide search short cuts [22].

The Globe system handles high load on the logical root by partitioning objects among multiple physical root servers using hash-like techniques.

Chord performs this hash function well enough that it can achieve scalability without also involving any hierarchy, though Chord does not exploit network locality as well as Globe.

The distributed data location protocol developed by Plaxton et al - [19], a variant of which is used in OceanStore [12], is perhaps the closest algorithm to the Chord protocol.

It provides stronger guarantees than Chord: like Chord it guarantees that queries make a logarithmic number hops and that keys are well balanced, but the Plaxton protocol also ensures, subject to assumptions about net- work topology, that queries never travel further in network distance than the node where the key is stored.

The advantage of Chord is that it is substantially less complicated and handles concurrent node joins and failures well.

The Chord protocol is also similar to Pastry, the location algorithm used in PAST [8].

However, Pastry is a prefix-based routing protocol, and differs in other details from Chord.

CAN uses a -dimensional Cartesian coordinate space (for some fixed ) to implement a distributed hash table that maps keys onto values [20].

Each node maintains state, and the lookup cost is.

Thus, in contrast to Chord, the state maintained by a CAN node does not depend on the network size , but the lookup cost increases faster than.

If , CAN lookup times and storage needs match Chord’s.

However, CAN is not designed to vary as (and thus ) varies, so this match will only occur for the “right” corresponding to the fixed.

CAN requires an additional maintenance protocol to periodically remap the identifier space onto nodes.

Chord also has the advantage that its correctness is robust in the face of partially incorrect routing information.

Chord’s routing procedure may be thought of as a one- dimensional analogue of the Grid location system [14].

Grid relies on real-world geographic location information to route its queries; Chord maps its nodes to an artificial one-dimensional space within which routing is carried out by an algorithm similar to Grid’s.

Chord can be used as a lookup service to implement a variety of systems, as discussed in Section 3.

In particular, it can help avoid single points of failure or control that systems like Napster possess [17], and the lack of scalability that systems like Gnutella display because of their widespread use of broadcasts [10].