Show description

Due to peers joining and leaving the overlay, the overlay graph G is dynamic. 4), we say that the overlay proceeds through a temporal sequence Gi(Vi, Ei), Giþ1(Viþ1, Eiþ1), Giþ2(Viþ2, Eiþ2), . . When a peer p0 joins Gi at time i, the overlay join operation causes the overlay to become Giþ1(Viþ1, Eiþ1), where V iþ1 ¼ Vi [ {p0 } and Eiþ1 ¼ Ei [ {(p0 , m)} [ {(n, p0 )}. That is, the join operation adds p0 to the set of nodes and adds at least one incoming and at least one outgoing link between p0 and some other node in the overlay.

The identifier space has size, an ordering relationship, a distance relationship, and an equality test. Since it is used for addressing, it must be efficient for storage and routing. The number of peers and resources that are represented in the identifier space could be very large, so it must be scalable. It must be location independent so that moving the device doesn’t affect its addressability. For message routing to converge, the identifier space should support a metric such that at any position in the address space some distance to the target can be computed.

These properties include the degree distribution of nodes in the graph, which effects load distribution, and the diameter of the graph, which affects the hop count in query routing. Graph properties for networks found in many different phenomena—ranging from manmade networks such as the Internet and the hyperlink topology formed by the World Wide Web to social networks, epidemics, and physical systems—have been extensively studied. Surprisingly, there are important classes of graphs that can describe a large range of such real-world phenomena.