Regular Papers

Unified Framework and an Algorithm for Searching inPure P2P—Hop-value-based Query-packet Forwarding
Masato Uchida† and Shinya Nogami
Abstract
In pure peer-to-peer (P2P) file sharing applications and protocols using a flooding-based query algorithm, a large number of control packets (query packets) are transmitted on the network to search for target files. This flooding-based query-packet-forwarding algorithm is clearly not scalable because it willlead to an overhead, such as an overwhelming amount of query traffic and a high CPU load, as more servents (servent = server + client) join the overlay network. To solve such problems, this paper proposes a
new query algorithm based on a unified framework that describes a wide variety of query algorithms forpure P2P. This framework determines the number of destinations for query packets based on the hop
value recorded in received query packets. Simulation results revealed that the proposed query algorithm
can reduce the overhead in the flooding-based query algorithm without decreasing the success rate of
retrieval regardless of the density of target files in the network.

1. Introduction
The past few years have seen the development ofseveral new file sharing applications and protocols
based on the pure peer-to-peer (P2P) model, which
does not have any servers to support clients. In thismodel, every client acts as a server. These so-called“servents” (servent = server + client) form a decentralized and unstructured application-level overlay
network on the physical layer, by connecting to existing servents.
Several pure P2P applications pass messages (packets) that implement file sharing among servents on
the overlay network. For example, query packets fortarget files are broadcast on the overlay network. This
flooding-based query-packet-forwarding algorithm(flooding-based query algorithm) is clearly not scalable because it will obviously lead to an overhead,such as an overwhelming amount of query traffic anda high CPU load, as more servents join the overlay
network. Against this background, the possibility of† NTT Service Integration Laboratories
Musashino-shi, 180-8585 Japan
E-mail: uchida.masato@lab.ntt.co.jp

Vol. 2 No. 6 June 2004

multiple random walks (k-random walks) on a pureP2P network to find target files has been discussed[1]. In the k-random walks, a requesting node sends kquery packets, and each query packet takes its own
random walk on the network. Although anothersearch algorithm has been studied [2], it needs anadditional function to cache query results that cannot
be obtained by the usual pure P2P protocols.
This paper first provides a unified framework thatcan describe a wide variety of query algorithms.
Based on this framework, we then propose a newquery algorithm that can reduce the overhead without
decreasing the success rate of retrieval regardless ofthe density of the target files in the network. Ourframework includes the flooding-based query algorithm, which can determine the number of destinations for query packets based on the hop value
recorded in received query packets. Note that the hopvalue is information that the query packet usually has.
We evaluated three query algorithms within theframework (flooding, k-random walk, proposed) bysimulation, where the algorithms ran on a model
drawn from actual topology data accessible to thepublic [3].

43Regular Papers

2. Flooding-based query algorithm
Several pure P2P applications, such as Gnutella andits clones, pass query packets that implement filesharing between servents on the overlay network.
Specifically, each servent forwards the received
query packets to all of its neighbors. Each packet’s
header contains a time-to-live (TTL) field. TTL isused in the same fashion as in the IP protocol: at eachhop its value is decremented until it reaches zero, at
which point the packet is discarded. That is, TTL
shows how many times the packet will be forwarded
by servents before it is removed from the network.
Each packet’s header also contains a hop field. Thehop value is incremented at each hop. That is, the hop
value is the number of times the packet has been forwarded.
3. Unified framework for query algorithms
This section first provides a unified framework thatallows us to describe a wide variety of query algorithms. Then, we give examples of how algorithms
are set up within the framework.
The key idea of the proposed framework is to utilize
the hop value h recorded in the received query packets when they are forwarded (Figs. 1 and 2). That is,a servent forwards the received query packet to someof its neighbors according to h, while a servent thatuses the flooding-based query algorithm forwards thereceived query packet to all of its neighbors regardless of h.
The proposed framework is outlined in Figs. 1 and2, where the crossed circle is connected with the cir-n
N1 (h) = 0k
N2 ( h ) = 1for h ≤ d1, ( d1: constant ),for h > d1for h ≤ d2, ( d2 , k: constant ).
for h > d2Obviously, N1(h) is equivalent to the flooding-based
query algorithm, and N2(h) is equivalent to the k-random walks when d2 = 0. This means that the proposed

TTL thop h

TTL thop h

TTL t–1
hop h+1

TTL t–1
hop h+1

Fig. 1. Query packet forwarding algorithm for N(h) ≤ n.
Circle and square objects indicate servents andquery packets, respectively.

44

cled circle, closed circles, and open circles. When thecrossed circle receives a query packet (squaredsquare) whose TTL is t and hop value is h from thecircled circle, it performs the following procedure.
Step 1: If t = 0, the crossed circle drops the query
packet; otherwise, it determines the numberof destinations N(h).
Step 2: If N(h) ≤ n, the crossed circle selects N(h)servents (closed circles) randomly from n servents without multiplicity (Fig. 1); otherwise,
it selects N(h) servents (closed circles) randomly from the n servents with multiplicity(Fig. 2), excluding the servent that transmitted the incoming query packet (circled circle).
Step 3: The crossed circle decrements t and increments h of the received query packet. Then, it
forwards the query packets (crossed squares)
to the selected servents.
We can construct various query algorithms basedon the above by setting N(h) appropriately. For example, the definition enables us to describe both theflooding-based query algorithm and k-random walks
within the framework by setting N(h) as follows.

Fig. 2. Query packet forwarding algorithm for N(h) > n.
Circle and square objects indicate servents andquery packets, respectively.

NTT Technical Review

Regular Papers

framework is a natural extension of the notion ofquery algorithms.
Next, we propose a new query algorithm based on
the above framework. It is defined as follows.

N3 ( h ) =nfor h ≤ d3

1n 1+ h − d3for h > d3

, ( d3 : constant ).

In N3(h), the number of destinations for query packets that will be forwarded decreases as the hop value
grows depending on the nodal degree. There are
numerous similar examples to N3(h). For example,
n for h ≤ d ′N ′( h ) = , ( d ′: constant ),1 for h > d ′for h ≤ d ′′
nN ′′(h) = , ( d ′′: constant ).
n − (h − d ′′ ) for h > d ′′However, we found heuristically that N3(h) gives better performance than the examples we tried in simulations. Finding the best form of N(h) theoretically is
still an open problem.
4. Simulation
In this section, we consider the appropriate forms ofN(h) that can reduce the number of query packets
without decreasing the success rate of retrieval. To
achieve this, we compared the performance of N1(h),N2(h), and N3(h) through simulation. Though N(h)can take other values, we can obtain a rough approximation by evaluating these forwarding algorithms.
We also used real topology data accessible to the public [3]. Statistics about these data are listed in Table
1, where the edge is a link between two nodes and thedegree of a node is the number of edges that the node
has.

4.1 Preparation
We performed the simulation on the proposed
framework as follows.
Step 1: Select topology t from crawl1, . . . , crawl6,
where the set of servents forming a network isdescribed by Ct.
Step 2: For each topology, place a target file, which
will be searched for, on all servents included
in Ct with probability (density) p, where thenumber of placements is described byNumPlace.
Step 3: For each placement, randomly select a servent, which will search for the target file,from Ct, where the number of selections isNumQuery.
Step 4: Transmit the query packets generated by eachselected servent, based on the proposed
framework in Section 3.
Note that, for each set of topology t and probabilityp, statistics can be collected NumPlace × NumQuerytimes through the above simulation. In this paper, wecollected the following statistics concerning both
success rate of retrieval and overhead of query algorithm, where i = 1, . . . , NumPlace × NumQuery.
st,p(i): A value describing whether or not target
files will be found before the search terminates (i.e., the value is 1 when the target
files are found at least once and 0 otherwise).
gt,p(i): Number of (all) generated query packets
that each node in the network must process
before the search terminates (i.e., the average number of (all) existing query packets
in the network before the search terminates).
vt,p(i): Number of visited nodes before the searchterminates.
dt,p(i): Number of duplicated query packets thateach node in the network must process
before the search terminates, where thenumber of duplicated query packets isdefined as gt,p(i) – vt,p(i).

Table 1. Topology data statistics.
Data namecrawl1.log

crawl2.log

crawl3.log

crawl4.log

crawl5.log

crawl6.log

Number of nodes

737

1568

653

435

2282

1406

Number of edges

803

1906

738

459

2765

1583

Average degree2.1791

2.431122.26034

2.11034

2.423312.25178

Variance of degree

4.02762

31.111349.319726.5579

17.24678.59948

Maximum degree

18186

14364

10861

Vol. 2 No. 6 June 200445

Regular Papers

Using these statistics, we can define the following
criteria, where |Ct| is the number of elements included in the set Ct. We evaluated the simulation resultsfor each set of topology t and probability p using
these criteria.
St,p: Probability of finding the target object before
the search terminates.
NumPlace∗NumQuery

St , p =∑i=1

st , p(i )NumPlace ∗ NumQueryGt,p: Overhead of an algorithm measured by theaverage number of generated query packets
that each node in the network must process.
NumPlace∗NumQuery

Gt , p =gt , p(i )1 ∑i=1
Ct NumPlace ∗ NumQuery

Dt,p: Overhead of an algorithm measured by theaverage number of duplicated query packets
that each node in the network must process.
NumPlace∗NumQuery

Dt , p =dt , p(i )1 ∑i=1
Ct NumPlace ∗ NumQuery

110.9

0.9

0.8

0.8

0.7

0.7
Scrawl5,0.01

Scrawl5,0.05

4.2 Results and discussion
The simulation results are shown in Figs. 3–6,
where the parameter values used for these simulations are listed in Table 2. The results are summa-

0.6
0.5
0.4
0.3

0.1
00.01

0.5
0.4
N1
N2
N3

0.2
0.1
1

0.1

0.6

0.3

N1
N2
N3

0.2

10

Gcrawl5,0.05

Fig. 3. Success rate of retrieval (Scrawl5,0.05) versus theaverage number of generated query packets pernode (Gcrawl5,0.05). The horizontal axis is a log scale.

46

rized in Table 3. Although these figures are forcrawl5, the results were almost the same even whenother topology data was used.
We measured the overheads of algorithms by Gt,pand Dt,p. Note that the average number of generated
query packets per node (Gt,p) and the average numberof duplicated query packets per node (Dt,p) increased
as the values of d1, k, and d3 rose.
As we can see from Fig. 3, which is for p = 0.05,
N2(h) and N3(h) found target files with higher probability than N1(h), when N1(h), N2(h), and N3(h) used
the same number of generated query packets. Additionally, we can see from Fig. 4, which is for p = 0.01,
that N1(h) and N3(h) found the target files with higher probability than N2(h), when N1(h), N2(h), andN3(h) used the same number of generated query packets. This means that N3(h) found the target files witha smaller number of generated query packets regardless of the value of p, although N1(h) found target files
with a smaller number of generated query packets
only when p was low, and N2(h) found target fileswith a smaller number of generated query packets
only when p was high.
Moreover, as we can see from Fig. 5, which is for p= 0.05, N3(h) found target files with higher probability than N1(h) and N2(h), when N1(h), N2(h), andN3(h) used the same number of duplicated querypackets. Additionally, as we can see from Fig. 6,
which is for p = 0.01, N1(h) and N3(h) found the target files with higher probability than N2(h), whenN1(h), N2(h), and N3(h) used the same number of
duplicated query packets. This means that N3(h)

00.01

0.1

110

Gcrawl5,0.01

Fig. 4. Success rate of retrieval (Scrawl5,0.01) versus theaverage number of generated query packets pernode (Gcrawl5,0.01). The horizontal axis is a log scale.

NTT Technical Review

1

1

0.9

0.9

0.8

0.8

0.7

0.7
Scrawl5,0.01

Scrawl5,0.05

Regular Papers

0.6
0.5
0.4
0.3

0.1
00.0001

0.001

0.5
0.4

0.2
0.1
0.1

0.01

0.6

0.3

N1
N2
N3

0.2

N1N2
N3

1

00.0001

0.001

Dcrawl5,0.05

0.1

0.01Dcrawl5,0.01

1Fig. 5. Success rate of retrieval (Scrawl5,0.05) versus theaverage number of duplicated query packets per
node (Dcrawl5,0.05). The horizontal axis is a log scale.

Fig. 6. Success rate of retrieval (Scrawl5,0.01) versus theaverage number of duplicated query packets per
node (Dcrawl5,0.01). The horizontal axis is a log scale.

Table 2. Parameter values.

Table 3. Results of simulations.

NumPlace

20

NumQuery200

TTL (0)*7p0.01, 0.05

d10, 1, 2, 3, 4, 5, 6

d20d30, 1, 2, 3, 4, 5, 6, 7

k10, 20, 40, 80, 160, 320, 640

N1Gt, p
Dt, p

N2N3

p = 0.01

good

bad

good

p = 0.05

bad

goodgoodp = 0.01

goodbadgoodp = 0.05

badbadgood* The initial value of TTL defined by requesting servent

found target files with a smaller number of duplicated query packets regardless of the value of p,
although N1(h) found the target files with a smaller
number of generated query packets only when p was
low, and N2(h) found target files with a larger numberof duplicated query packets regardless of the value ofp. This is because if the query algorithm based on
N2(h) is used, the requesting servent’s neighbors must
transmit numerous redundant query packets when k ishigh. We therefore conclude that N3(h) can find target
files with fewer query packets without duplication,
regardless of the value of p, if the values of the parameters listed in Table 2 are appropriately adjusted,although N1(h) can find target files with fewer query
packets without duplication only when p is low, andN2(h) can find target files with fewer query packets by
duplication only when p is high.

Vol. 2 No. 6 June 2004

5. Conclusion and further study
This paper proposed a new query algorithm basedon a unified framework which describes a wide variety of query algorithms for pure P2P such as theflooding-based query algorithm and the k-random
walks. The proposed query algorithm can reduce theoverhead without decreasing the success rate ofretrieval regardless of the density of the target files in
the network, where our framework can determine thenumber of destinations for query packets based on thehop value recorded in received query packets. Morespecifically, simulation study found that the newquery algorithm is a better query algorithm than theflooding-based query algorithm and the k-random
walks. Based on the above, we can conclude that thenumber of servents to which the query packet will beforwarded should be small as the hop value increases
like N3(h). The results in this paper are useful for
designing a scalable query algorithm for pure P2P.
47

Regular Papers

References
Masato Uchida
[1]

[2]

[3]

Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker, “Search and Replication in Unstructured Peer-to-Peer Networks,” Proceedings of the 16th
Annual ACM International Conference on Supercomputing, NewYork City, U.S.A., June 2002.
K. Sripanidkulchai, “The Popularity of Gnutella Queries and Its
Implications on Scalability,” http://www-2.cs.cmu.edu/kunwadee/research/p2p/gnutella.html.
http://crawler.limewire.org/data.html

Communication Traffic & Service Quality
Project, NTT Service Integration Laboratories.
He received the B.E. and M.E. degrees in information engineering from Hokkaido University,Sapporo, Hokkaido in 1999 and 2001, respectively. In 2001, he joined NTT Service Integration Laboratories, Tokyo, Japan. He is a memberof the Institute of Electronics, Information andCommunication Engineers of Japan (IEICE). He
received the research award (IEICE Communication Quality Technical Group) in 2003 and the
young investigators’ award (IEICE) in 2004.

Shinya Nogami
Senior Research Engineer, Communication
Traffic & Service Quality Project, NTT Service
Integration Laboratories.
He received the B.E., M.E., and D.Eng.
degrees in electrical and communications engineering from Tohoku University, Sendai in 1979,1981, and 1984, respectively. In 1984, he joinedNippon Telegraph and Telephone Public Corporation (now NTT) where he has been researchingtraffic design and the performance evaluation of
information communications and switching systems. He is a member of the Communications
Society of the IEEE and the Information Processing Society of Japan, and he has been an
associate editor of IEICE Trans. on Communications since 2003.

48

NTT Technical Review