11-08-2012, 11:53 AM
Replica Placement for Route Diversity in Tree-Based Routing Distributed Hash Tables
replica.pdf (Size: 1.99 MB / Downloads: 29)
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
INTRODUCTION
PEER-TO-PEER (p2p) networks are a popular substrate for
building distributed applications because of their efficiency,
scalability, resilience to failure, and ability to selforganize.
The p2p architecture relies on the distribution of
responsibility among hundreds of thousands, if not millions,
of nodes in the network. Therefore, if a small set of nodes fail
to serve data objects, properly maintain routing information,
or route messages, the integrity of a very large-scale system
may be compromised.
The efficiency of lookups has become a central focus of
p2p design because many popular applications, like name
resolution, publish-subscribe, and IP communication, rely
on a lookup service as a core functionality. A p2p distributed
hash table (DHT) may be used to provide this functionality.
DHTs [25], [26], [33], [34] structure the network topology in a
way that enables routing algorithms to produce lookup
paths of bounded length (typically OðlogNÞ).
RELATED WORK
To place our work in context, we discuss related work on
replica placement, peer-to-peer routing security, and general
peer-to-peer security issues.
Replica Placement
Replica placement has long been studied in the realm of
distributed computing. Many studies have compared the
performance of different placement schemes in terms of
quality of service, availability, and time to recovery in
different types of serverless systems [6], [9], [19], [22]. The
first DHT-based replication schemes were only concerned
with availability and thus local replication, i.e., replicas
placed close to the master copy in the ID space, was used
[26], [33]. As detailed herein, such placements have very
little routing robustness.
A very important paper, which proposed the first
deterministic nonlocal replica placement scheme for
DHT-based systems, was that of Ghodsi et al. [12]. This
paper discussed a set of symmetric replica placement schemes
that, for a replication degree of d, divide the ID space into
equivalence classes, each of size d. If an object with its ID in a
particular equivalence class is replicated, replicas are placed
at all IDs in the class. This is a very general definition, which
is completely independent of routing. Thus, for a particular
DHT structure, some such schemes could produce a large
number of disjoint routes while others might produce very
few.
Peer-to-Peer Routing Security
A number of works that look to improve routing security
are centered around the notion of route diversity. For
example, Artigas et al. propose Cyclone, an equivalencebased
routing scheme deployed over an existing structured
peer-to-peer overlay [2]. Independent lookup paths are
created by routing across different equivalence classes.
Since the paths are independent and do not differ in the
destination, Cyclone does not naturally mitigate the effects
of storage and retrieval attacks. Furthermore, each peer is
required to maintain additional routing information, which
incurs overhead. In contrast, our replica placement creates
disjoint routes without requiring any additional routing
state or modifying the underlying routing scheme.
Intuition behind MaxDisjoint Placement
To create route diversity in Pastry via replica placement, it
is necessary to place replicas such that a given replica set
will use a diverse set of routing table entries for every
possible source node. We use an example to provide the
necessary intuition. Consider a Pastry ring with id space of
size 64 and prefix matching in base-4 digits. We show the
Pastry routing table structure graphically for a hypothetical
node 121 in Fig. 1.
Suppose we wish to replicate an object with id 101 in this
Pastry ring. Node 121 routes to this object through the
routing table entry marked “10x” in Fig. 1. Suppose we
replicate the object with the id 111 to target the routing table
entry “11x” in the example. This approach creates an
additional disjoint route for any lookups for object 101
originating at node 121. One route is forwarded via the
entry “10x” and the other is forwarded via “11x.” However,
consider another source node 221. This node routes to the
object 101 and 111 through the same entry marked “1xx”
and, therefore, does not gain an additional disjoint route.
Evaluation of Disjoint Routes
The desired number of disjoint routes d is one of the tunable
inputs to the MAXDISJOINT algorithm. Controlling the level
of fault tolerance is an important design parameter and,
therefore, d is a very useful input. In this section, we will
formally prove that the algorithm indeed creates d disjoint
routes in support of the intuition provided in earlier
sections.
In our analysis, we assume that routing is performed in
an identifier space of size N with branching factor B. All of
our analytical results are proved within the context of a full
DHT, but we will show, through experimentation, that
these properties hold even in sparsely populated DHTs.