22-02-2013, 04:25 PM
Locating Equivalent Servants over P2P Networks
Locating Equivalent.PDF (Size: 600.52 KB / Downloads: 25)
Abstract
While peer-to-peer networks are mainly used to
locate unique resources across the Internet, new interesting
deployment scenarios are emerging. Particularly, some applications
(e.g., VoIP) are proposing the creation of overlays for the
localization of services based on equivalent servants (e.g., voice
relays). This paper explores the possible overlay architectures
that can be adopted to provide such services, showing how an
unstructured solution based on a scale-free overlay topology
is an effective option to deploy in this context. Consequently,
we propose EQUATOR (EQUivalent servAnt locaTOR), an unstructured
overlay implementing the above mentioned operating
principles, based on an overlay construction algorithm that well
approximates an ideal scale-free construction model. We present
both analytical and simulation results which support our overlay
topology selection and validate the proposed architecture.
Index Terms—Distributed services, equivalent servants, peerto-
peer overlays, scale-free topology.
INTRODUCTION
WHILE in the past few years the resource sharing services
across the Internet focused on generic storage
(e.g., distributed file systems, remote disks), content (e.g.,
file sharing, video streaming), and CPU cycles, the recent
emerging of the cloud computing paradigm might push this
vision even further. According to this scenario, the world
will be populated by thin and light computing devices acting
mainly as frontends, while the computation and the user’s data
reside elsewhere, in the “cloud”. In those services, two groups
of entities are defined: “users”, that ask for a given service,
and “servants” that are actually in charge of providing the
service. Servants can be composed of millions of processing
platforms either sparse across the Internet, or concentrated in
special datacenters. Users do not care about their physical
location: they are interested in getting the service, no matter
which servant is actually providing it.
RELATED WORK
During the last few years, structured (e.g., Chord [6],
Kademlia [7]) and unstructured (e.g., Gnutella [8], KaZaA [9])
P2P solutions have started to be adopted as building blocks for
the definition of more complete P2P systems able to provide
arbitrarily complex distributed services. For example, [10]
and [11] present two similar unstructured architectures for
the provision of Grid-like services. Other solutions have been
proposed in the context of video distribution (e.g., [12], [13]).
On the structured side, some example of these architectures
have been presented in [14]–[17].
However, all these proposals address a problem that is
different from the scenario we have in mind, where users
are interested in locating one of the many available servants.
Even more important, they do not investigate the effects of the
overlay topology on the performance of this type of resource
lookup in order to determine the best overlay technology for
the given service.
The equivalence of servants is considered in [18]–[20]. In
[18], the authors propose a scheme for CPU cycle sharing over
an unstructured P2P network. They consider the unbalanced
node degree distribution, which may result in real overlay
networks, as a possible obstacle to the lookup effectiveness
of the system and, consequently, they propose mechanisms
to overcome these limitations. In this paper, we show instead
how an unbalanced node degree distribution (specifically, a
scale-free topology), if properly exploited, ensures high lookup
performance. Peer-to-peer SIP (P2PSIP [19]) proposes to use
a DHT to support lookups of relay nodes among all the
equivalent participating peers, which can be done by randomly
selecting a target node and then moving over the DHT to
reach this target. Our previous work [20] explores the idea
of a service based on equivalent servants, but it limits its
application to a distributed connectivity service in a SIP
infrastructure.
Structured overlays
We first investigate the possibility to deploy a structured
overlay based on a general DHT, as it has been proposed in
[19] for the P2PSIP architecture.
Since in our scenario all peers provide the same functionality
(i.e., we have only one resource provided by many nodes),
the number of copies predominates over the number of distinct
services and therefore the ability of DHTs to locate a specific
resource is of little help. Therefore, [19] proposes to use the
DHT in a more clever way: queries are performed by randomly
selecting a target key and then moving in the overlay to reach
this target.
Since it does not cause further complexity and possibly
improves the system performance, we introduce an additional
feature to this querying mechanism: during the lookup process,
any node encountered along the path is checked for availability
and can be selected as a servant for the querying user. Notice
that this operating mode makes the approach independent of
the adopted DHT. In fact, only the overlay topology (which is
a regular graph in existing DHTs) is of interest in our context.
In other words, we adopt the topology of a generic DHT, with a
fixed number of neighbors for each node, but we use a different
routing mechanism. This solution will be however referred to
as DHT in the rest of the paper.
Unstructured overlays
An efficient unstructured overlay is characterized by high
lookup performance and small amount of traffic required to
maintain the overlay. Both parameters are influenced by the
topology and the operating principles (e.g., how nodes spread
information) of the overlay. This section elaborates on these
aspects in the context of services based on equivalent servants,
proposing to adopt a scale-free topology and motivating this
choice.
An interesting lookup solution that avoids the deleterious
traffic overhead generated by flooding-based queries is the
adoption of a service lookup based on random walks [21]
encompassing a bounded number of nodes. Within this technique,
the service request is forwarded, at each node, to a peer
randomly selected among its neighbors. If the encountered
node is available or knows an available servant, the procedure
terminates. The knowledge of nodes can be improved through
proper advertisement messages containing the node itself
and/or other participating peers, thus implementing a so called
epidemic dissemination algorithm.
Further properties of the unstructured scale-free overlay
Scale-free networks offer some other properties which could
be interesting for the deployment of service-oriented overlays.
First of all, we show how the average blocking probability
can be further lowered by reducing the number of nodes
from which users can start random walks in order to locate
a servant. In particular, since one of the key ideas under the
adoption of a scale-free topology is to preferably direct queries
toward hubs.
EQUATOR
The previous section demonstrated the effectiveness of an
unstructured network based on a scale-free topology. However,
both the Barabási-Albert model, adopted for the scale-free
construction, and the lookup mechanisms deriving from this
approach make some assumptions that cannot be satisfied in
the real world; particularly, we envision four problems in
the model that require some real-world adaptations. In fact,
the Barabási-Albert model requires (i) a global knowledge
of nodes and (ii) their popularity in order to perform the
preferential attachment; (iii) hubs are supposed to index an
arbitrarily large number of servants, which are used to satisfy
incoming service requests; finally, (iv) nodes are considered
static, i.e., the model does not consider nodes joining and
leaving the network.
CONCLUSION
This paper focuses on service-oriented overlays where users
are interested to locate any of the many available overlay
peers in the shortest time, i.e., the offered service is based
on equivalent servants. Existing solutions, either structured or
unstructured, can support these services but are not optimized
for this purpose, which however is growing in importance due
to the spread of many applications which need these specific
features (e.g., a proxy node to anonymize a communication).