EPDKS: An Efficient Proximity-based Distributed K-Ary Structured Overlay Network

L.O. Alima and S. Beauport (Belgium)


Distributed Systems, Peer-to-Peer Systems, Overlay Net works, Distributed K-Ary Search, DHT, Self-Organizing Systems.


Structured peer-to-peer overlay networks provide a means for interconnecting a large set of computing nodes called peers in a distributed, scalable and self-organizing man ner. Typically in such systems, each peer maintains con tact information about a small subset of other peers called neighbors. These neighbors are often chosen to ensure that each lookup operation takes a logarithmic number of over lay hops under normal conditions. Relying solely on the number of overlay hops as the metric for the quality of the lookup operation is not sufficient both for the appli cations using the overlay network and, for the effective use of the underlying communication network which is typi cally the Internet. DKS [1] is a P2P middleware built upon the principle we called distributed K−ary search, which ensures that any lookup takes O(logK(N)) overlay hops, where N is the number of nodes in the system and K is the search arity. In a DKS overlay network, proximity is not considered. As a result, end-to-end latencies could be sig nificantly large. In this paper we present EPDKS, a novel structured peer-to-peer overlay network that is based on the distributed K−ary search principle. EPDKS takes prox imity into account by combining round-trip times and the number of IP hops for interconnecting peers, thereby re ducing end-to-end latencies and making effective use of the underlying network. Furthermore, we propose improve ments for some of the algorithms currently implemented in the DKS. Simulation results confirm our expectations that EPDKS ensures lower end-to-end latencies and smaller number of IP hops when compared to DKS.

Important Links:

Go Back