Link Lifetimes and Randomized Neighbor Selection in DHTs

Author(s)

Zhongmei Yao, University of DaytonFollow
Dmitri Loguinov, Texas A & M University - College Station

Document Type

Conference Paper

Publication Date

4-2008

Publication Source

INFOCOM 2008. The 27th Conference on Computer Communications. IEEE

Abstract

Several models of user churn, resilience, and link lifetime have recently appeared in the literature [12], [13], [34], [35]; however, these results do not directly apply to classical Distributed Hash Tables (DHTs) in which neighbor replacement occurs not only when current users die, but also when new user arrive into the system, and where replacement choices are often restricted to the successor of the failed zone in the DHT space. To understand neighbor churn in such networks, this paper proposes a simple, yet accurate, model for capturing link dynamics in structured P2P systems and obtains the distribution of link lifetimes for fairly generic DHTs. Similar to [8], our results show that deterministic networks (e.g., Chord [28], CAN [24]) unfortunately do not extract much benefit from heavy-tailed user lifetimes since link durations are dominated by small remaining lifetimes of newly arriving users that replace the more reliable existing neighbors. We also examine link lifetimes in randomized DHTs equipped with multiple choices for each link and show that users in such systems should prefer neighbors with smaller zones rather than larger age as suggested in prior work [13], [30]. We finish the paper by demonstrating the effectiveness of the proposed min-zone neighbor selection for heavy-tailed user lifetime distributions with the shape parameter alpha obtained from recent measurements [4], [31].

ISBN/ISSN

0743-166X

Document Version

Published Version

Comments

Permission documentation is on file.

Copyright

Copyright © 2008 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.

Place of Publication

Phoenix, AZ

Peer Reviewed

yes

Keywords

P2P networks, peer-to-peer, DHTs, Distributed Hash Tables, neighbor replacement, link lifetime, neighbor churn

Sponsoring Agency

IEEE

eCommons Citation

Yao, Zhongmei and Loguinov, Dmitri, "Link Lifetimes and Randomized Neighbor Selection in DHTs" (2008). Computer Science Faculty Publications. 11.
https://ecommons.udayton.edu/cps_fac_pub/11