Title
Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables
Abstract
Distributed hash tables (DHTs) share storage and routing responsibility among all nodes in a peer-to-peer network. These networks have bounded path length unlike unstructured networks. Unfortunately, nodes can deny access to keys or misroute lookups. We address both of these problems through replica placement. We characterize tree-based routing DHTs and define MaxDisjoint, a replica placement that creates route diversity for these DHTs. We prove that this placement creates disjoint routes and find the replication degree necessary to produce a desired number of disjoint routes. Using simulations of Pastry (a tree-based routing DHT), we evaluate the impact of MaxDisjoint on routing robustness compared to other placements when nodes are compromised at random or in a contiguous run. Furthermore, we consider another route diversity mechanism that we call neighbor set routing and show that, when used with our replica placement, it can successfully route messages to a correct replica even with a quarter of the nodes in the system compromised at random. Finally, we demonstrate a family of replica query strategies that can trade off response time and system load. We present a hybrid query strategy that keeps response time low without producing too high a load.
Year
DOI
Venue
2011
10.1109/TDSC.2009.49
Dependable and Secure Computing, IEEE Transactions
Keywords
Field
DocType
file organisation,peer-to-peer computing,query processing,telecommunication network routing,trees (mathematics),MAXDISJOINT,distributed hash tables,pastry,peer-to-peer network,route diversity replica placement,share storage,tree-based routing,Distributed systems,distributed hash tables,peer-to-peer networks,replica placement,robustness.,routing
Replica,Pastry,Static routing,Key-based routing,Computer science,Computer network,Network topology,Robustness (computer science),Distributed computing,Scalability,Hash table
Journal
Volume
Issue
ISSN
8
3
1545-5971
Citations 
PageRank 
References 
5
0.48
27
Authors
2
Name
Order
Citations
PageRank
Cyrus Harvesf150.48
Blough, D.M.241429.82