Peer to peer (P2P) networks have using commonly used for tasks such as file sharing or file distribution, and for building distributed applications in large scale network. Their performance measures are generally based on simulation methods software such as NS-2, P2PSim, OpenNet, etc. Hence, the absence of a validation of the simulation model is a critical issue. In this paper, we propose a new analytical model derived from (8), to evaluate the performance of HPM protocol (hierarchical Peer-to-Peer model). Performance is done principally in terms of total download time of requested resources in the P2P network, and then we analyze the impact of various parameters associated with the heterogeneity of nodes.
The P2P paradigm has emerged as a solution to
some limitations of the classical methods of resource
sharing based on the paradigm Client / Server. It is
a distributed system without or with minimal central
authority and with varying computational power at
each machine. Its applications are varied, we cite as
an example: the multicast application, parallel
computing, file sharing, IP telephony, instant messaging,
search engines, etc. This type of network is generally
characterized by a good scalability (scaling) and
a very high dynamic (churn rate), for more details
about this topic see (
P2P networks have seen an unprecedented
development that was accompanied by a significant increase
in their complexity. So, we focus in this paper on
analytical models, because of the interest in their
high speed resolution. Indeed, when considering
making a change to the system, decisions will lead
to very high cost, and it is very useful to have
analytical solution with their much reduced computing
time. Analytical and mathematical frameworks let us
to model and study the performance of the P2P
networks, and several models have been proposed
in order to investigate the dynamics of this kind
of systems, many researches are focused on the
Markov chain based modeling , (
The goal of this paper is to propose an analytical
model for evaluating the performance of the HPM
(hierarchical Peer-to-Peer model) (
We interest about structured P2P architecture, because it is more efficient in terms of lookup and download resources, and more complicated to implement. For this, the analytical model is slightly more interesting to take into account the system characteristics and evaluate the performance of the corresponding architecture in a very short time, and give a good insight into the operation of the systems under study at low cost, compared to other performance evaluation techniques of P2P networks like measurement and simulation approaches. Analytical models are least expensive and give the modeler deep insight into the main characteristics of the system.
In this work, we want, exactly, to answer the
question: using the HPM, how long does it take a
requested resource to lookup and download? To
answer this question, we use a queuing model with
structured P2P system, we consider two types of
nodes, the relay and the end peer nodes as
described in HPM, we use also a single class open
queuing network to evaluates the delays in a relay
nodes, we model each relay node as G/G/1 queue
(
The rest of this paper is organized as follows: next section gives a background and related work on Peer to Peer networks and existing performances evaluation methods, we describe and analysis the proposed models existing in the literature. Section 3 describes our proposed model. In section 4, we validate our model; finally, we conclude and give some perspectives.
In this section we give a brief description of P2P network and different classes of associated mathematical models.
P2P Systems offer an important opportunity for a large number (hundreds of thousands) of nodes to cooperate in order to share resources via a widely distributed network. Nodes of the network, are an equal participant, and there are no nodes with special facilitating or administrative roles. Since the service is distributed to all participating nodes, the system is expected to scale well even when the network is very large. Avoiding bottlenecks and likely with good fault tolerance, the P2P paradigm is suitable for large-scale distributed environments where nodes (called also peers) can share their resources (eg. computing power, storage capacity, bandwidth) as an autonomous and decentralized. Due to its advantages, several areas have already taken advantage of this paradigm (eg. file sharing, sharing computing capacity and exchange instant messages). A peer can play the role of client when it consuming resources, and the role of server when it offered resources, router when it spreads requests received from other nodes in the system, and host data source when sharing their data with other peers. There are many different P2P systems, each one with various advantages and disadvantages. They differ both in their object query mechanism and in their logical topology, we therefore distinguish three families of P2P systems: centralized systems,decentralized (structured and unstructured) systems, and hybrid systems.
server that is responsible to relate directly all connected peers and to identify the files offered by different clients. The advantage of this technique lies in the centralized indexing all directories and titles of shared files by the subscribers in the network. Clients send queries to the server, and it returns a list of peers currently connected to the service and who’s shared the desired files. The file transfer will be done between final users and not by the server. Under these conditions and at any time, files are found stored on the central server. Such centralized approach does not scale well and have a single point of failure, (e.g., Napster).
Decentralized Unstructured Systems (DUSy): it is called also the pure P2P systems in which all nodes play equivalent roles, there are no servers or nodes privileged, each node has high degree of autonomy. Nodes are organized arbitrarily using flooding (broadcast or random walks) for the content discovery. To find a resource, a request will be sent from a peer to another until it reaches the client that has the desired object. To avoid flooding the network for too long, the system associates each request a timer TTL ”Time To Live”, the value assigned to the TTL is usually 7 (as in Http). When it reaches zero, the query is not returned. The major disadvantage of this mechanism comes from the expiration of TTL before the course of the entire network, which can lead to failure of research although the desired file is available on the P2P network, and usually, these networks do not scale well, because of the high amount of signaling traffic. On the other hand, they present a very high level of anonymity. The most known examples of these networks are Gnutella and FreeNet .
emergence of structured P2P systems is due to the
problem of large number of messages exchanged
in unstructured P2P systems. Nodes should be
structured in a precise geometrical form, and in
general, they consist in some variant of a Distributed
Hash Table (DHT) technology. These networks are
constructed in a structured overlay where each node
maintains a specific set of contents (or a set of
content location indexes), this information is often
used to guide the routing of the requests / messages
in the system. Therefore, the content searches are
deterministic and efficient. As examples of their
systems, we can cote: Chord, HPM (
Hybrid Systems (HSy): hybrid P2P network is more complex to implement, as it combines both centralized and distributed network. A network of this type is based on a set of servers managing a group of users according to the centralized architecture. Each server is then connected to other servers according to the distributed architecture.
In this way, if a user searched a file that is not indexed by the server to which it is attached, it then forwards the request to another server. This architecture can benefit from better bandwidth while reducing the query traffic.
In this paper, we are interested in the structured
P2P architecture in general and particularly HPM
(
One of the main characteristics of HPM is the routing optimization at IP level, as it takes into consideration the physical proximity while minimizing the number of hops for lookup process (cost lookup). The authors evaluated the performance of HPM with simulation, the metric they are taken: cost lookup, size of data structure, number of rings at each level and the number of rings and level for HPM with IPv6 and IPv4 address format. However, in our work, we evaluate the system with analytical model in term of total download time of requested resource, and capture the impact of nodes level characteristics on the performance of HPM.
Mathematical models can be used to predict system behavior. Among both techniques: simulation and analytic modeling that can be used at the design stage, this one is much less expensive. Also, with the availability of very powerful and effective general purpose modeling tools, analytic models are becoming increasingly more cost effective than simulation. Many researches are focused on this modeling method for evaluating the performance of P2P systems; the most significant classification of the modeling techniques we found in the literature, they are classified into four models: Markov chain models, fluid flow models, and queuing network models. In most cases, these models are used to describe the performance of the whole system and stochastic characteristics of a peer, they are clearly able to reflect the effect of different parameters on P2P systems performance, they permit efficient and detailed exploration of the parameter space to evaluate the effect of not just only single parameter, but also the combined effect of variation of several parameters. However, many of these models are based on unrealistic assumption like peers having global information about the state of all peers, simplifying assumption on the underlying network topology, and on the arrivals and departures of peers.
In the following, we present the different analytical
models used to evaluate the performance of P2P
networks:
Fluid Flow Model: An homogenous branching
process is used to study the service capacity
of BitTorrent-like P2P file sharing network in the
transient regime and a simple Markovian Model is
presented in (
In (
Markov Chain Model: Birth and Death Markov
model based structured peer-to-peer networks are
studied on (
of P2P file sharing systems is presented in (
In this section we develop our proposition model,
which consists of modeling the HPM structured
P2P system, and evaluate its performances with
an analytical method. This work is an extension
of (
HPM is organized as a set of hierarchical rings
composed of nodes, we interested in two types of
nodes: relays and peers nodes. Each relay acts as
a gateway to one or more rings, and peers are
the nodes residing in the various ring. We take
as example the scenario below: three relays (R1,
R2 and R3) and four rings as shown in figure 2.
When a peer P2 in ring 2 searches a file that is
on peer P9 in ring4, the request (packet) should be
transferred through the R1 and R2 relays to get the
file that on P9, (the principal detailed of the lookup
and download of resources in HPM is described
in (
j : expected service rate at relay j: 1=E(Sj ) j = j, CS00j = [V arSj ]=[E(Sj )2] CS00j : scv or variability of service time at relay pij : for each pair (i,j), probability of a packet going to relay j after completing service at relay i
We focus on the network queuing delays and the delays at the end peers, using a queuing model. We break up the system into two components: the relay nodes, modeled with single class open network, GI/G/1 OQNS, and the end peers modeled with M/G/1/K Processor Shared.
In our proposition, we use a decomposition method
(
We model each relay nodes by a GI/G/1 to allow
for arbitrary arrival and service time distribution.
Traffic to a network relay can be rather irregular and
does not necessarily follow a Poissonien distribution
(
To find the relay network delay, we should pass through three steps: Step 1. Analysis of interaction between relays of the networks, Step 2. Evaluation of performance measures at each relay, Step 3. Evaluation of performance measures for the whole network.
Step 1. Analysis of interaction between relays of
the networks
(
n 0j + ∑ ij ; f orj = 1; ::n;
i=1 where ij = pij i, is the expected arrival rate at station j from station i.
We also get : j = j = j ; 0 j 1; (ii)the squared coefficient of variation (scv) for the arrival process or variability of interarrival time. The expected (external) departure rate to station 0 from station j is given by :
The expected number of packets in the jth relay,
including one in service, is given by using Little’s law:
E[NCj ] = j + j E[WQj ]
(
n 0j or ∑ j=1
j0 vj = E(Kj ) = j = 0: Throughput or total external rate of traffic into the relays : .
The expected number of visits
The s.c.v. of arrival time can be approximated by
Traffic variability equation (
n Ca2j = wj ∑ i=0 ij Ca2i + 1 j wj = 1 1 1 + 4(1
j )2(xj xj = ∑n i=0( ijj )2 : wj 1) ; E(wj ) = j (Ca2j + CS2j )g( j ; Ca2j ; CS2j )
The total number of packets in the network is:
NC =
n
∑ NCi :
i=1
E[TNr] =
NC
0
(
The HPM architecture is composed of peers and
relays, each relay is attached to a number of rings;
in turn harbor the end peer. In the previous section,
we provided a queuing delay at the intermediate
relay, and in this subsection, we give and develop
a queuing model for the end peer and provide
expression of the expected time takes to service a
requesting resource. We model each end peer as
M/G/1/m Processor sharing. The choice of this last is
motivated by the fact that, the service time depends
on the size of the resource being downloaded and
resource size distribution is typically heavy-tailed,
so the service time cannot be modeled as an
exponential process. For this, we are motivated to
choice an arbitrary distributions for the time services
and taking generalized model for resource size, and
the arrival process follows the Poisson process with
rate di, since the SCV of the arrival process at the
end peers equals 1, the demonstration of this result
is given in (
State probabilities pk are given by:
pk = 1 k(1m+)1 ; Pl = 1m(1m+1) ; =
diX^ ; (
The expression of query search time is the time taken for the entire search process to terminate; it differs from one architecture to another, depending on the research technique used. In this work, we consider a structured architecture to evaluate this parameter, which is the HPM, so, the neighbor relationship between peers and data locations is strictly defined. Searching in such systems is therefore determined by the particular network architecture. The search technique employed to lookup the requesting resource in this architecture is defined as follow: Each ring k at level i, used the ith part of data key for the lookup process, when a peer in ring k if the requestor node belongs to, the request succeeds on this ring k, if the resource does not exist on the active covered ring, the search is done on ring level i + 1, or i 1, in a deterministic manner the cost of the search process is O(∑m
i=1 log2(ni)), where, ni is the number of nodes on the covered ring at level i on which the request succeeded.
The query process terminates when the last of
the responses finds it’s way back to the source.
The expected time elapsed between the query
generation and termination is thus:
where [∑iN (E[WQi ] + i)]=NR represent the average
queuing delay at a relay, and [WQi ] is given
previously in Eq.(
C is the cost of the lookup in HPM architecture, and is given by:
m C = O(∑ log2(ni);
i=1 d give the approximate distance for random graph, it represent the shortest path between two random chosen nodes on the relay graph: d = ln(NR 1)(z^2 z^1) (ln(z^2=z^1)) ln(z^12) ; where z^i is the average number of i hop neighbors and NR is the total number of nodes in the relay graph:
NR NR z^1 = [ ∑ Aij]=NR; z^2 = [ ∑ IA^(i; j)]=NR i;j=1 i;j=1;i̸=j A is the relay adjacency matrix, A^ = A2 and IA(i; j) defined as:
IA^(i; j) = { 1; ifA^ij > 0;
0; otherwise
We arrived at the expression that gives the total download time of resource, which is the time elapsed from when the query was generated until the entire resource is downloaded, with O(i) copies of the resource in the network, which is generated by the Zipf’s Law :
O(i) = Von=i H (V ); where H (V ), is the harmonic number of order of V and defined as:
V H (V ) = ∑ 1=i : i=1 The given formula in Section 3:2:1: gives us the total time it takes a packet takes to get the customer E[TNR], so the download time is determined by the time spent by the last packet sent by the slower peer to reach the destination.
The time when the last packet reaches the edge of the network is when the slower peer is done transmitting it’s allocated resource part i.e. after E[TWP ] seconds. The packet, then spends a further E[TNR] in the network.
The expected service time for data transfer at the slower peer is:
E[TWP ] =
B=O(i)
C=E[NWP ]
O(i) number of copies of the resource in the network E[NWP ] is the expected number of files serving at any point in time
1 j E[NWP ] = ∑[∑ i p(i)]P (m = j)
j=0 i=0
Thus, the total download time, E[TD], is given by:
(
E[T ] = E[TD] + E[TQS] (18)
In this paper, we have presented the performance evaluation models for P2P systems, which of these P2P overlay networks is best suited depends on the application and its required functionalities and performance metrics (e.g. scalability, network routing performance, location service, file sharing, content distribution, and so on).
We have summarized various recent works on
performance modeling of such systems that have
been proposed in the literature, offering an insightful
and useful overview of system properties, focus of
analyses and results of each work studying.
A novel analytical model derived from work in (
As future work, we envision to take into account the behavior of nodes and we will study the online-offline transition, which may influence the performance of the system, and especially on the download time of a resource.
Method
(
Architecture Focus of Analyses and
Results
CIA,DIFA,DIHA Generality, flexibility of
modeling,analyze the effect of
freeloaders, files and user
behavior.
(
MMo,Bpr
DUSy (BitTorrent)
Study service capacity and
fairness. P2P system achieves
favorable scaling in terms of
average download delay with
increasing load.
(
FMo
HFflow (5)
(
QMo(OQN) Do not capture all aforementioned phases of the sharing process, namely flash crowd, steady state. Not account the query search time (propagation delay), not treated the structured architecture.
Not capture the effect of the differences in the file size of different request on the sys performance, access rate and varying load on different peer not modeled, ignore the effect of the network topology.
Performance of individual user not degrades significantly, the average delays scale well in the offered load Not account for queuing effects and heterogeneities in the network. Not account for queuing effects in the network, and heterogeneities in hosts and the network. The assumption about global knowledge of all peers for peer selection