14-09-2012, 05:29 PM
Revisiting Dynamic Query Protocols in Unstructured Peer-to-Peer Networks
Revisiting Dynamic Query Protocols.pdf (Size: 744.3 KB / Downloads: 35)
Abstract
In unstructured peer-to-peer networks, the average response latency and traffic cost of a query are two main performance
metrics. Controlled-flooding resource query algorithms are widely used in unstructured networks such as peer-to-peer networks. In this
paper, we propose a novel algorithm named Selective Dynamic Query (SDQ). Based on mathematical programming, SDQ calculates
the optimal combination of an integer TTL value and a set of neighbors to control the scope of the next query. Our results demonstrate
that SDQ provides finer grained control than other algorithms: its response latency is close to the well-known minimum one via
Expanding Ring; in the mean time, its traffic cost is also close to the minimum. To our best knowledge, this is the first work capable of
achieving a best trade-off between response latency and traffic cost.
INTRODUCTION
PEER-TO-PEER overlay networks, running at the application
layer, perform scheduling and routing without any
knowledge of the underlying physical networks. Various
peer-to-peer systems have became the most popular Internet
applications and a major portion of the Internet traffic is
attributed to them.
Topologies of peer-to-peer systems can be divided into
three different categories: centralized, decentralized but
structured, and decentralized and unstructured. Napsterlike
[15] centralized systems have their resource directories
hosted at some central servers. A centralized topology
scales poorly and suffers from the single-point-of-failure
problem. Chord [25] and Tapestry [30] are decentralized,
but their network topologies are highly structured and their
resources are placed by distributed-hash-table algorithms. It
is not surprising that these topologies are sensitive to the
extremely transient join/leave/failure behaviors of peers,
which is, unfortunately, an intrinsic characteristic of
Internet peer-to-peer applications.
RELATED WORK
To allow resource querying in unstructured peer-to-peer
networks, two main categories of query protocols are
developed. Controlled-flooding-based algorithms, as the
name suggests, control the iterative flooding process: instead
of blind flooding, an integer TTL value is carried in each
packet of an individual query round; the scope of the
flooding can then be controlled. Controlled-flooding-based
algorithms are widely used in unstructured networks such as
wireless ad hoc networks [5], [6]. Expanding Ring (ER) is the
first such protocol [5]. Several researchers [14], [20] have
compared the performance of ER [5] with other algorithms in
peer-to-peer networks. The Gnutella developer community
proposed the Dynamic Query (DQ) technique to retrieve
enough results at a low traffic cost [12]; Jiang and Jin
analyzed the DQ protocol and then proposed an enhanced
version (DQ+) [17], [18] to reduce response latency.
INTUITION OF OUR ALGORITHM
Before delving into the details, we present our intuition
first. In DQ+ [17], when there are many residual neighbors
at one round, only one query packet is propagated to only
one neighbor, trying to retrieve all the residual results. In a
Gnutella system with the average degree D ¼ 24, assume
that there is one iteration of DQ+ with next neighbor degree
d ¼ 12, and the expected horizon Hne ¼ 8;324. In this case,
nTTL ¼ 3:10 should be used according to (2). We also
assume that there are other 26 neighbors left with different
degrees; 10 peers among them have the total degrees of 357.
The observation is that the query could be completed within
one iteration, by sending these 10 neighbors together with
nTTL ¼ 2 query packets (we will provide a detailed
analysis on how to calculate this value in Section 5.3). It is
obvious that the optimal utilization of neighbor heterogeneity
is not achieved yet.
Impacts of Other Factors
Impact of network scale. Fig. 3 shows the algorithm
performances in different network scales. Again, the
replication value is 0.01 and 50 results are required. There
are four different Power Laws topologies, generated using
[23], with 40, 80, 120, and 160 K nodes, respectively.
All algorithms maintain stable performance. Again, SDQ
archives the best overall control of both traffic cost
and response latency than others. At least in tens of
thousands scale, the network scale has no obvious impact
on query algorithms.
CONCLUSION
Traffic cost and response latency are two critical metrics for
resource query algorithms in unstructured peer-to-peer
networks. In this paper, we propose a novel protocol in this
paper: SDQ, which calculates an optimal combination of an
integer TTL value and a set of neighbors for the next query
round. Our experiments demonstrate that SDQ provides a
fine-grained control: its latency is close to the well-known
minimum one via ER; in the mean time its traffic cost is also
small. Through extensive simulations.