Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

A Graph-Theoretic Perspective > Object Storage and Lookup - Pg. 34

34 CHAPTER 2 Peer-to-Peer Concepts The graph diameter is the maximum distance between any two nodes in the graph. From an overlay routing perspective, graph diameter provides a worst-case path length for sending a message between any two nodes in the overlay under static conditions. Consequently, graph diameter is an important parameter for comparing various geometries that might be used in an overlay. Each peer in the overlay has a number of adjacent peers to which it has a direct connection. The number of such adjacencies is the degree of the peer. Outgoing degree is the number of adjacencies from the current peer to its neigh- bors. Incoming degree is the number of adjacencies to the current peer from its neighbors. A routing path is the sequence of edges or hops from the peer sending the message to the peer which is the target of the message. The routing path is recur- sive (Figure 2.5A) if each successive peer along the path forwards the message to the next peer in the path. The routing path is iterative (Figure 2.5B) if each suc- cessive peer along the path replies to the sender with the next-hop information. The sender then forwards the message to the next hop. An iterative path, though less efficient than a recursive path in terms of number of messages, allows the sender to determine the progress of the delivery. Object Storage and Lookup A set of objects S is stored in the P2P overlay. Each object s has a unique identifier sid and a binding with the peer that stores it (p,s) . In a distributed hash table (DHT), the object ID space and the peer ID space are the same, and each peer p with predeccessor q is responsible for sid s such pid p . On average, the number of objects p is responsible that pid q < sid for is | S | / | V | . The DHT has at least two operations, insert(sid, s) and s ¼ lookup(sid) , which use key-based routing to store and retrieve objects in the DHT, respectively, according to their sid . In key-based routing, the object key or sid is used as the overlay address for the DHT messages. Thus an insert mes- sage with destination equal to sid s is routed to that peer that is responsible for sid . Peers at intermediate hops forward the insert message using the sid as the destination address. 4 3 2 1 1 2 4 3 A B FIGURE 2.5 (A) Recursive and (B) iterative routing paths.