Ubicc-215_215

EXPLORING PERFORMANCE LANDSCAPE OF UNSTRUCTURED SEARCH SCHEMES Hong Huang and Rajagopal Reddy Manda Klipsch School of Electrical and Computer Engineering, New Mexico State University, USA {hhuang, rgopal}@nmsu.edu

ABSTRACT Search plays an important role in ubiquitous computing. In this paper, we investigate the expected cost and latency of three unstructured search schemes: broadcast, TTL-based, and random-walk-based search schemes. We build a unified analytical model for unstructured search schemes. We demonstrate, through simulation, that the different search schemes exhibit very different cost and latency tradeoffs, leaving large gaps in the performance landscape. We propose randomized mixing schemes to bridge such performance gaps and bring out new Pareto frontier that offers more diverse performance choice for applications. Keywords: performance modeling, randomized mixing, search methods.

1

INTRODUCTION

Search for information in a network has many important applications in ubiquitous computing, such as route discovery of on-demand routing protocols in wireless ad hoc networks [1], event query in sensor nets [2][3], information lookup in peer-to-peer networks [4], etc. Unstructured search refers to a type of search where no a priori knowledge about the search target is available. Unstructured search is applicable in cases where the network is highly dynamic and maintaining an infrastructure for data lookup is too costly [4]. Unstructured search can be and sometimes is implemented by a broadcast search. However, a broadcast search is very costly and not scalable. A broadcast search is particularly unjustifiable when the target is replicated for robustness and latency reduction as is common with today’s distributed applications. As mentioned in [4], the fundamental problem of broadcast search lies at the lack of granularity of the search action, i.e., either no action or a very costly one--broadcast. To reduce cost and provide for finer granular search actions than broadcast search, a variety of other unstructured search schemes were proposed. Here we focus on two types of such schemes appearing in recent literature: iterative broadcast (TTL-based) schemes, and random-walk-based (RWbased) schemes. In a TTL-based scheme [5][6], a series of broadcasts with increasing scopes are carried out. The scope of a broadcast is determined by the TTL (Time to Live) value carried by a query packet, which limits the number of hops the packet can travel. A TTL-based scheme offers finer granular search actions than a simple broadcast by varying its scope; and promises to reduce cost by trying search actions with smaller cost first in the hope to find the

target without high cost broadcast. However, a TTLbased scheme can be wasteful in overlapped coverage of successive broadcasts and generally causes larger search latency than simple broadcast. In a RW-based search, a query packet carries out a random walk in the network, which continues until the target is found [2][3]. A RW-based scheme has the finest granular search action possible, i.e., visiting a single node; but it can cause large latency. Variations on the basic random walk scheme are possible to reduce latency, e.g., using multiple walkers. There are two main performance metrics for a search scheme [6]: expected cost and expected latency. Expected cost is defined as the expected total number of hops traveled by the query packets generated a particular search scheme. Expected latency is defined as the expected time duration, in the unit of hops (i.e., one hop takes one unit of time), between initiation of the search and the discovery of the target. We do not include the time for the result to travel from the target to the originator, because it has nothing to do with the merits of a search scheme. Previous work most closely related to ours includes the following. TTL-based search on a line is first treated in [5] where an optimization problem is formulated and the competitive ratio to the optimal offline algorithm is obtained. In [6], a dynamical programming formulism for TTL-based scheme is developed, and a randomized strategy for selecting TTL values is shown to achieve the minimum worstcase cost if the target distribution is unknown. Such randomized strategy is pursued further in [7] to develop schemes that achieves lowest cost competitive ratio under constraint of varying delay competitive ratio. An analytical model for TTLbased search using generating function of degree

Ubiquitous Computing and Communication Journal

1

distribution is described in [15]. Random walk is shown to be an effective search method in sensor nets in [2], and its behavior is examined in [3][12]. Unstructured search in peer-to-peer networks is treated in [4] focusing on target replication strategy. Search in graphs with a power-law degree distribution is treated in [14]. Hybrid search schemes combining broadcast and random walk is discussed in [12]. The contributions of this paper are as follows. Although there are much previous works on unstructured search schemes, there is no systematic exploration of the performance landscape of all unstructured search schemes in one place, delineating the feasible regions of performance tradeoffs. This paper hopes to make progress in this direction: We build a unified analytical model for unstructured search schemes, which is parameterized by the granularities of the search sequences. We demonstrate through simulation that different unstructured search schemes exhibit very different cost and latency tradeoffs, leaving large gaps in the performance landscape. We propose randomized mixing schemes to bridge such performance gaps and bring out new Pareto frontier that offers more diverse performance choice for applications. The paper is organized as follows. In Section 2, we build a unified model for the three unstructured search schemes. In Sections 3-5, we deal with broadcast, TTL-based, RW-based search schemes, respectively. We introduce mixed schemes in Section 6, and conclude in Section 7. 2 A UNIFIED PERFORMANCE MODEL FOR UNSTRUCTURED SEARCH SCHEMES We consider the problem of searching for a target in a network of N nodes. A target is replicated in m copies, locating any of the replicas caused the search successful. We consider a search scheme consisting of a sequence of actions A = [A1, A2,…, Al], where Al is the first search action, A2 the second search action, and so forth, and Al is the terminating action in which the target is found. For an unstructured search scheme, there is no outside clue about the next search action except the history of previous search actions. In a broadcast search, there is a single action: broadcast. In a TTL-based scheme, each action is a limited broadcast with a particular TTL value. In a RW-based scheme, each action is a step in the walk. As we can see, the actions of different search schemes have different granularities, which have performance implications. We write Ci as the cost of performing search action Ai, Di as the average latency caused by Ai,Fi as the probability that Ai fails, with the convention F0 = 1, Fl = 0. The cost of the first search action is always paid outright, but that of a later action, Ci, is paid out only if the previous action failed with the probability

of Fi-1. The search continues until success (i=l). So the expected cost of a search scheme can be written as l

E[C ] =

∑F

(1)

i −1Ci

i =1

It is easy to show the above can be rewritten as l ⎛ i ⎞ ⎜ E[C ] = C j ⎟ ( Fi −1 − Fi ) ⎜ ⎟ i =1 ⎝ j =1 ⎠

∑∑

(2)

The above expression can recognized as a standard formula for computing expected value. For each term in the summation, (Fi - Fi+1) is the probability that search sequence does not succeed in the (i-1)th action but succeeds in the ith action, and the summation in the parenthesis is cost of a search sequence terminating at ith action. We can use a similar approach to write the average latency of a search scheme but for a cautionary note. The latency incurred by Ai generally depends on whether the search is successful or not. Consider, for example, a search action with TTL set to be 10. If the target is within the TTL scope, say 7 hops away, the latency is 7. But if the target is more than 10 hops away, the search action fails and incurs a latency of 10 regardless where the target is located. We write D”i as the latency if the target is within the scope of ith action, i.e., if the action is successful; and D’i as the latency if the target is out of the scope, i.e., if the search action is unsuccessful, which is fixed for a particular action. So, with probability (Fi - Fi+1), i.e., the search sequence does not succeed in the (i-1)th action but succeeds in the ith action, the search latency is D '1 + D '2 + ... + D 'i −1 + D "i

Thus the expected latency can be written as ⎛

l

E[ D ] =

⎞

i −1

∑ ⎜⎜ ∑ D ' + D " ⎟⎟ ( F i =1

j

⎝

i

j =1

⎠

i −1

− Fi )

(3)

Rearranging terms, we have E[D] = E[ DBCast ] + E[ D ']

(4)

where l

E[ DBCast ] ≡

∑ D" (F i

i −1 − Fi )

(5)

i =1

⎛ ⎜ ⎜ i =1 ⎝ l

E[ D '] ≡

⎞ D ' j ⎟ ( Fi −1 − Fi ) = ⎟ j =1 ⎠

i −1

∑∑

Ubiquitous Computing and Communication Journal

l −1

∑F D' i

i

(6)

i =1

2

In the above, E[DBcast] expresses the expected latency for a search that expands in scope until successful without incurring the latency of failed actions. This part of latency is the same as the latency of a broadcast search, which is independent of the particular search scheme used and represents the minimum latency of any search scheme. E[D’] collects the latency incurred due to failed actions, and is dependant of the particular search scheme in question. The above formulism is general without regard to any particular search scheme in question. Before proceed further, we list our assumptions. A1 The cost of a search action (a single step) in a random walk is 1. A2 The cost of a search action that requires broadcasting to n nodes is n, i.e., Ci = Ni in equations (1) and (2). A3 The m target replicas are independently, identically distributed among the nodes. The above assumptions are admittedly idealistic, but they are used here to focus on the issue intrinsic to the merits of a particular search scheme and exclude external factors such as network conditions, implementation efficiency, etc. Assumption A1 holds only if the links are lossless, which is not true in practical situations. However, introducing loss requires specification of loss probability, which is some extraneous detail outside the scope of our discussion. Similarly, A2 holds only if the implementation of broadcast is perfect, again more idealism than realism. Broadcast is known to cause redundancy and inefficiency, to mitigate which methods have been devised [8]. Again, such details fall out of the scope of the present discussion, and similar approximation is used in [4]. Assumption A3 implies the probability of success depends only on the number of nodes visited, and has nothing to do with the identities of visited nodes. In other words, the failure probability Fi is solely a function of nodes visited so far, Ni, i.e., Fi = F ( Ni )

(7)

The particular form of F depends on the distribution of the replicas. Now we are ready for the following proposition. Proposition 2.1 A: The expected cost is parameterized by and thus depends only on the search sequence [N1, N2,…, Nl], regardless the network topology. B: The expected latency depends on both the search sequence and network topology. Proof: The validity of the statement A is apparent by combing equations (1) and (7). The validity of the statement A derives from the fact that different latencies are incurred in different network topologies to cover the same number of nodes. For, example, it incurs just one-hop latency to cover all

nodes in the network if the topology is a complete graph; whereas it incurs n/2-hop latency if the topology is a ring of n nodes. Q.E.D. In the following, we provide bounds on minimum expected cost and latency, and identify search schemes that achieve these bounds. First, we define an idealized random walk. Definition 2.1 An idealized random walk is one that visits a distinctive node in every step. Proposition 2.2 The minimum expected cost among all unstructured search schemes is N

Cmin =

∑ F ( j − 1)

(8)

j =1

where F(j-1) is defined in the sense of (7). This minimum expected cost can be achieved by an idealized random walk. Proof: First, we show that for an arbitrary search scheme, its expected cost is at least Cmin. Suppose the scheme’s search action sequence is [A1, A2,…, Al], and the corresponding node coverage sequence being [N1, N2,…, Nl = N]. It is clear that Ci >= ΔNi =Ni - Ni1, since it takes at least a cost of ΔNi to cover ΔNi nodes. So we have l

E[C ] =

∑

l

Fi −1Ci ≥

i =1

∑

l

Fi −1ΔNi =

i =1

∑ F (N

i −1 ) ΔN i

i =1

The right-hand side of the inequality cab be recognized as the discrete integration of Fi with a step size of ΔNi on the N-axis, with support intervals as N1 + ΔN2 + ΔN2 +… + ΔNl = [1, 2, … N]. Since Fi is a non-increasing function of Ni, so we have l

∑

N

Fi −1ΔN i ≥

i =1

∑ F ( j − 1) = j =1

l

∑( F (N

i −1 ) +

F ( Ni −1 + 1) + ... + F ( Ni −1 + ΔNi − 1) )

i =1

Second, an idealized random walk is a sequential visit of each node. Without loss of generality, let the sequence be j=1, 2,…, N, and thus incurs the expect the minimum cost of N

∑ F ( j − 1)

Q.E.D.

j =1

The next proposition is obvious, and we state without proof. Proposition 2.2 The minimum expected latency is the minimum expected distance in hops between the originator and any one of target replicas, which can be achieved by a broadcast search.

Ubiquitous Computing and Communication Journal

3

In next three sections, we derive cost and latency models for three classes of unstructured search schemes: broadcast, TTL-based, and RW-based. To compute the expected cost and latency, one needs to have a specific probability distribution for replicas in the network. In the following, we assume replicas are distributed uniformly in the network, which is a common case, e.g., in DHT-based data lookup scheme in peer-to-peer networks [4]. Thus, given m replicas, the failure probability of a search action that covers Ni nodes of N nodes in the network is ⎛ N ⎞ Fi = ⎜1 − i ⎟ ⎝ N⎠

3

m

(9)

A broadcast search consists of a single action, i.e., broadcast. Its cost is fixed with E[CBCast] = N, however the expected latency is not so trivial. To make tractable analysis, we assume that a network lives in a d-dimensional space, where the originator resides in the center of the space. According to A3, the probability that a target resides in a particular space is proportional to the volume of the space. The probability that a target (at random distance x) is less than r hops away can be computed as d

Pr

⎡ ⎛ r ⎞d ⎤ ≡ P ( x ≤ r ) = 1 − ⎢1 − ⎜ ⎟ ⎥ ⎢⎣ ⎝ R ⎠ ⎥⎦

m

m

And according to Proposition 2.2, the expected latency of a broadcast search can be calculated as the expected minimum distance between originator and the targets.

E[ DBCast ] =

∫

R

0

m

rdPr = −

Γ(m) ≅ 2π m

∫

L

0

⎡ ⎛ r ⎞d ⎤ rd ⎢1 − ⎜ ⎟ ⎥ ⎢⎣ ⎝ R ⎠ ⎥⎦

1 Γ(m)Γ( + 1) d = mR 1 Γ(m + + 1) d

N Γ(m) 3 2Γ ( m + ) 2

(11)

m

(10)

where Γ( ) is the gamma function. For d = 2, which is our main focus here, we have N = απR2, with α being the node density. The node density, defined as the

m−

1 2 e− m

⎛ ⎛ 1 ⎞⎞ ⎜1 + O ⎜ ⎟ ⎟ ⎝ m ⎠⎠ ⎝

We have, for arbitrary dimension and large m,

E[ DBCast ] ≅ Rm

4

where R is the radius of the network in hops. The probability that minimum distance between the originator and the m target replicas is no larger than r hops is m

E[ DBCast ] = m

In passing, we note that for large m [9],

BRAODCAST SEARCH

⎛r⎞ Pr ≡ P ( x ≤ r ) = ⎜ ⎟ ⎝R⎠

number of nodes per square hop, depends on the nodal degree and the network topology in question. Expressions of α can be obtained only for some special cases. For example, it is straightforward to show that α = 1 for a square grid with nodal degree of four, α = 2/√3 for hexagonal grid with nodal degree of six, etc. Since the density only introduces a scalar factor, we will, without loss of generality, use the value of one in the following. Thus, in a 2-D space, we have R = (N/π)1/2, and,

⎛1 1⎞ −⎜ + ⎟ ⎝ 2 d ⎠ Γ( 1

d

+ 1)

(12)

TTL-BASED SEARCH SCHEMES

A TTL-based search consists of a sequence of broadcasts with increasing TTL values, with the last action being a network-wide broadcast. To motivate our analysis, we consider the first two actions in a TTL-based search, i.e., A1 and ,A2 with increasing TTL values, covering N1 and N2 nodes, incurring costs of C1 and C2, respectively. Note that the node coverage of A2 includes that of A1. We consider two options: a) a sequence of search actions [A1, A2], or b) a single action A2. Clearly, these two options have the same probability of success at the conclusion of the search. However, their costs are different, i.e., Ca = C1 + F1 C2 for option a, and Cb = C2, for option b. Option a is preferable to b only if C1 + F1C2 < C2. Rearranging terms, we have the following lemma, which was similarly stated in [6] but is derived here using simpler argument. Lemma 4.1 The cost of a search action A2 can be reduced by using a sequence of search actions [A1, A2], if the inequality holds: F1 < 1 −

C1 C2

(13)

Specializing to our model, and under the assumptions A1-A3, we have C1 = N1, C2 = N2, and the inequality becomes

Ubiquitous Computing and Communication Journal

4

the condition below m

N ⎛ N ⎞ F1 = ⎜1 − 1 ⎟ < 1 − 1 N2 ⎝ N⎠

∂E[CTTL ] = − fi −1m + mpi +1 fi m −1 = 0 ∂fi

It holds only if m > 1, since N is the total number of nodes in the network and can not be less than N2. So we have: Corollary 4.1 If m = 1, the cost of a search action A2 is no more than that of a sequence of search actions [A1, A2]. We generalize Corollary 4.1 in the following proposition. Proposition 4.1 Under assumptions A1 and A3, and if the number of replicas is one, the cost of a broadcast search is no more than that of a TTL-based search. Proof: We use Corollary 4.1 recursively. Consider a TTL-based search scheme consists of a search sequence [A1, A2,…, Al]. Apply Corollary 4.1 to the subsequence [A1, A2], which can be replaced with a single action A2, resulting in a new search sequence [A2, A3,…, Al], which has a cost no more than that of the original sequence. Applying Corollary 4.1 again to the new sequence, and so forth, and eventually we can reduce the original sequence to a single action Al, i.e., a broadcast, with a cost no more than that of the original sequence. Q.E.D. The above proposition implies that a TTL-based search is competitive to a broadcast search only if m >1. We now proceed to calculate the expected cost and latency of a TTL-based scheme. In our model, a TTL-based search scheme consists of a sequence of actions, A1, A2, …Al, with Ci = Ni, and Cl = N, where Ni is the number of nodes covered in the ith round. Using (1), We calculate the expected cost as l

E[CTTL ] =

∑

l

Fi −1Ci =

i =1

l

=N

∑

∑ i =1

⎛ N ⎞ Ni ⎜ 1 − i −1 ⎟ N ⎠ ⎝

m

Equation (15) provides a recursive relationship that determines fi+2 given fi+1 and fi (note that pi = 1 - fi). The optimal solution is given by testing the values of the expected cost at fi’s given by the recursive equation and at the boundary fi = 0 (since fi <= 1, and fi’s are strictly decreasing after each search action). Exact solution of the above set of nonlinear equations is difficult. However, we can try different f1’s (note that f0 = 0) and determine a family of sequences. The family of sequences provides different cost and latency tradeoffs and includes one that has the minimum cost. We calculate the expected latency using (4) and (6). l −1

E[ DTTL ] = E[DBCast ] +

∑F D i

i

i =1

l −1

∑

l −1

Fi Di =

i =1

m

⎛ N ⎞ hi ⎜ 1 − i ⎟ = β N ⎠ ⎝ i =1

∑

l −1

∑

1

pi d fi m

i =1

where hi is the TTL value (hop count) for the ith action, which can be expressed as 1

hi = β pi d

where β being a constant determined by network topology. For 2-D space, which is our interest here, we have, noting that is node density is 1, π hi 2 = pi N , and thus β = π , and therefore

(14)

pi fi −1m

E[ DTTL ] = E[ DBCast ] +

1

l −1

∑ π

N i fi m

(16)

i =1

i =1

where pi ≡

(15)

Ni and fi ≡ 1 − pi . N

Clearly, the expected cost depends on the vectors {fi} or its complement {pi}, where fi indicates the proportion of nodes covered in the ith search action, and pi being its complement. We choose {pi} or {fi} to minimize the expected cost. Obviously, fi and pi, being probabilities, are constrained within the interval of [0, 1]. Thus, we have a constrained optimization problem. According to the KuhnTucker conditions for constrained optimization, the fi’s that minimize the expected cost fall into two cases: a) located at the constrain boundary, i.e., fi = 0 or 1, or b) located inside the interval and subject to

Simulation results are shown in Figure 1 for a network with N = 1000, and m = 2, 4,.., 10. The network topology is generated randomly with average degree of five. The expected cost and latency as a function of p1 (the proportion of nodes covered in the first action) are plotted in the figure. From the figure one can see that the expected cost is small in the region of small p1, deceasing in a very gradual way to a minimum, and then rising quickly to become large at large p1, see Figure 1 (a). The implication is that the expected cost is insensitive to the selection of p1 as long as it is small. This turns out to be quite useful in practical implementation because there is no need to painstakingly search for

Ubiquitous Computing and Communication Journal

5

the optimal p1, any choice would be fine as long as it is a small number. 1000 m=2 m=4 m=6 m=8 m=10

900

800

700

E[C]

600

500

400

300

200

100

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

p1

(a) 20

18

m=2 m=4 m=6 m=8 m=10

16

m

s ⎞ ⎛ Fi = ⎜ 1 − i ⎟ = fi m N ⎝ ⎠

14

12 E[D]

fundamental problem for MRW is that there is no communication between walkers once they are released. So even if one walker finds the target, other walkers would continue until they individually find the target, incurring large cost. One way to rectify this problem is to make random walkers terminate probabilistically at each additional step. However, this leaves open the possibility that all the walkers might terminate before the target is found. Our solution is to make one persistent walker that never terminates, assisted by k non-persistent walkers, which survive with probability of q at each step. The persistent walker guarantees the search is always successful, while the non-persistent walkers speculatively wander away trying to reduce latency. In the following, we discuss expected cost and latency of SRW and MRW sequentially. We model a SWR search scheme as a sequence of actions, A1, A2, …Al, with Ci = 1, Di= 1, and l >= N. Let si indicate the number of distinct nodes visited in the first i steps, then probability of failure to find any of m replicas of the target is given by (since search for each replica has to fail), (17)

10

8

where fi = 1 −

6

si N

(18)

4

We calculate the expected cost using (1)

2

0

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

p1

(b) Figure 1: Expected cost E[C] (a) and latency E[D] (b) versus p1 for TTL-based schemes.

l −1

l

E[CSRW ] =

∑

Fi −1Ci =

i =1

5

RW-BASED SEARCH SCHEMES

In a RW-based search, a query packet visits nodes sequentially and terminates when the target is found. There are a variety of ways to carry out a RW-based search. One way is to employ a single random walker (SRW). Such a search, if it is ideal, incurs minimal cost according to Proposition 2.2, but it also causes large latency. To lower latency, multiple random walkers (MRW) can be released simultaneously, but with large increase in cost. A

i

m

(19)

i =0

We compute expected latency as l −1

l

The expected latency shows an opposite trend: it increases quickly to a maximum in the small p1 regime, then decreases monotonically and eventually saturates at large p1, see Figure 1 (b). Particularly, the maximum latency occurs roughly around the point where minimum cost occurs, indicating that reduced expected cost comes at the expense of increased latency.

∑f

E[ DSRW ] =

∑F

i −1 Di

i =1

=

∑f

i

m

(20)

i =0

The expected latency can be computed the same way as the cost since each step incurs a fixed latency (one unit), which is not true in other search schemes. A distinguishing fact for SRW is that the expected cost is the same as the expected latency. For other search schemes, expected cost is generally larger than the expected latency. This is because, for an action covering Ni nodes, the cost is paid outright as Ni, but the latency can be smaller than Ni if the target is found before every node is covered. Such inequality does not apply to SRW because each step is elementary, incurring unit cost and latency. There remain to be determined the values of si. There is no exact expression for si, though asymptotic expressions do exist [10]. One such expression says

Ubiquitous Computing and Communication Journal

6

where RR is probability that the walker will return to the originator. But such asymptotic expression is not useful. For the use of a RW-based search makes little sense if i gets as large as N, let alone infinity, because one might as well use broadcast with the same cost but much less latency. We think that, in a practical implementation, one will not use pure random walk simply for the sake of its theoretical purity, because it is patently inefficient, i.e., visiting previously visited nodes repeatedly. Instead, some optimization will be used in practical implementation, such as using a flag to indicate previous visits. Therefore, in a practical implementation, the behavior of a random walker approaches that of a idealized walker, i.e., si Æi, to the extent that optimization is done. We now turn to MRW. In MRW, in addition to one persistent random walker that terminates only if the target is found, k independent, identical, nonpersistent random walkers are also released, each having a probability of 1-q to terminate at each step. Since the random walkers are independent, we calculate the expected cost of MRW as

and are avoided unless all neighbors are flags, in which the walker marches on a flagged node regardless. The expected cost and latency as a function of q, the survival probability, are plotted in Figure 2, which is the case for m = 2. Plots for other m values show similar feature, thus are omitted. 750

k=1 k=2 k=3 k=4 k=5

700

650

600

550 E[C]

si → (1 − PR )i as i → ∞

500

450

400

350

300 0.5

0.55

0.6

0.65

0.7

0.75

0.8

0.85

0.9

0.95

1

q

(a) 340

330

⎡ l −1 ⎤ E[CMRW ] = k ⎢ Pi fi m ⎥ + ⎣⎢ i =0 ⎦⎥

∑f

i

m

k=1 k=2 k=3 k=4 k=5

320

(21)

i =0

310 E[D]

∑

l −1

where Fi is given by (17), and Pi is the probability that a walker is still alive after ith step, and is given by Pi =

(22)

1 − q l +1

The expected latency is determined by the minimum of those among multiple walkers, whose population at ith step is Ki = 1 + kPi

(23)

The search continues only if all Ki walkers fail to find any of m replicas, so the expected latency is l −1

∑f

290

280

q i − q l +1

E[ DMRW ] =

300

i

mKi

(24)

i =0

By varying k and q, we can construct a family of RW-based schemes. Simulation results are shown in Figure 2 for a network with N = 1000, random topology and average degree being five, and with one persistent walker plus one to five non-persistent walkers. To approximate practical, optimized implementation, previously visited nodes are flagged,

270 0.5

0.55

0.6

0.65

0.7

0.75 q

0.8

0.85

0.9

0.95

1

(b) Figure 2: Expected cost E[C] (a) and latency E[D] (b) versus q for RW-based scheme

From the figure, one can see that large performance variation occurs only where q is close to 1. Roughly after q is smaller than 0.9, the expected cost and latency fast converges to those achieved by a single persistent walker. Figure 2 also shows the tradeoff between expected cost and latency, i.e., latency can be reduced, at the expense of increased cost, by either increasing the number of non-persistent walkers (k) or reducing the survive probability (q). An important point, which will be elaborated in the next section, is that the cost-latency tradeoff here exhibits a very different feature from that of TTL-based schemes, comparing Figures 1 and 2.

Ubiquitous Computing and Communication Journal

7

MIXED SEARCH SCHEMES

BCast

900

800

TTL 700

RW

E[C]

600

500

400

300

200

100

0

0

50

100

150

200

250

300

350

E[D]

(a) 1000

900

BCast 800

700

TTL

600

E[C]

In this section, we examine more closely the performance landscape of different unstructured search schemes, and introduce mixed schemes to provide more diverse cost and latency tradeoffs. In the following, we will simplify notion by using CA, DA to indicate E[CA], E[DA] of a particular search scheme A, respectively. We start by laying down some preparations. Definition 6.1 The feasible region of a search scheme in the performance space consists of the union of expected cost and latency pairs, each realizable using an instance of the search scheme. Definition 6.2 A search scheme A dominates a search scheme B if C A ≤ CB ,and DA ≤ DB . Definition 6.3 A search scheme is Paretooptimal [11] if it is dominated by no other search scheme, and the set of all search schemes that are Pareto-optimal forms the Pareto-frontier. Definition 6.4 A mixed scheme between two search schemes A and B is a randomized scheme that selects A with a certain probability p and B with the probability 1-p. Proposition 6.1 The feasible region of a mixed scheme is convex. Proof: Consider two schemes A and B in the feasible region, with expected cost and latency of CA, CB, DA, DB, respectively. For any p in [0, 1], a mixed scheme with expected cost and latency of pCA+(1p)CB, pDA+(1-p)DB, is realizable. Therefore the feasible region is convex. Q.E.D. Equipped with the above background, let us examine the cost-latency tradeoffs of three types unstructured search schemes discussed previously. Simulation results for a network of 1000 nodes, random topology and average degree being five, are shown in Figure 3. Broadcast consists of a point in the performance region, incurring minimum latency but largest cost. TTL-based schemes consist of a family of schemes parameterized by p1, the proportion of nodes covered by the first action. TTLbased schemes achieve a slightly larger latency than broadcast but can incur significantly lower cost, especially for large m (number of replicas) and optimized p1, see Figure 3(c). RW-based schemes consist of a family of schemes parameterized by k (= 1-5), the initial number of walkers, and q, the survival probability. In the figure, individual curves correspond to a particular value of k, with large k curves lying higher. RW-based schemes can achieve lowest cost, especially for small m, see Figure 3(a); but it incurs largest latency. A remarkable fact about Figure 3 is that different search schemes exhibit very different cost-latency tradeoffs, leaving conspicuous gaps between them.

1000

500

400

RW

300

200

100

0

0

20

40

60

80

100

120

140

160

180

90

100

E[D]

(b) 1000

900

BCast

800

700

TTL 600

E[C]

6

500

400

300

RW 200

100

0

0

10

20

30

40

50

60

70

80

E[D]

(c) Figure 3: Expected cost E[C] versus latency E[D] for broadcast (BCast), TTL-based, and RW-based search schemes, shown with m=2 (a), m=5 (b) and m=10 (c). Dotted lines indicate Pareto frontiers of the mixed scheme.

In the following, we focus on TTL-based and RW-based schemes, omitting broadcast because of its deficiency. We call a TTL-based scheme as latency-preferred since its expected latency is low and insensitive to the parameter (p1), which is largely

Ubiquitous Computing and Communication Journal

8

limited by the E[DBCast] term in (16). However, its expected cost can vary widely with the selection of the parameter. On the other hand, we call RW-based scheme as cost-preferred since it exhibits the opposite behavior: its expected cost is low and relatively insensitive to choice of the parameters (k, q), but its expected latency vary widely with selection of the parameters. Further explanation, based on the analytical model, of difference in cost-latency characteristic appears in the appendix. TTL-based and RW-based schemes are modeled after broadcast and idealized random walk, which incurs minimum latency and cost, respectively. Therefore, the fact that TTL-based schemes are latency-preferred and RW-based schemes are costpreferred is not surprising in retrospect. Due to the peculiar performance characteristic of each type of scheme, any particular type may not satisfy the requirement of an application. Applications with varying cost-latency requirements can be best served if a more diverse Pareto frontier is accessible. This can be accomplished by mixing TTL-based and RWbased schemes. The dotted lines in Figure 3 indicate the Pareto frontiers of the mixed scheme, and is constructed based on the following proposition. Proposition 6.2 The Pareto frontier of mixing two families of search schemes A and B consists of parts of the Pareto frontiers of A and B, namely LA and LB, and the Pareto frontier of the linear combination of points on LA and LB. Proof: We prove that any point, P, in the feasible region of the mixed scheme is dominated by the proposed Pareto frontier of in the proposition. P can come from only three sources: feasible region of a pure A scheme, that of a pure B scheme, and linear combinations (mixing) of scheme A and B. In case that P is from a pure A region, P is dominated by some point on LA. In case that P is from a pure B region, P is dominated by some point on LB. In case that P is from a linear combination of points P1 of A scheme and P2 of B scheme, P is dominated by a linear combination of points PA and PB, where PA and PB are on LA and LB and dominates P1 and P2, respectively, refer to Figure 4. Q.E.D. We provide a simple example to demonstrate the value of a mixed scheme. Suppose an application has the requirement: E[C] < C0 and E[D] < D0. Such requirement is satisfied only by a mixed scheme and is not satisfied by either of the pure schemes, refer to Figure 4. A cautionary note before we conclude: a mixed scheme achieves the cost-latency point only in the expected sense, but the variance can be large. However, often times application quality of service requirements are expressed in terms of expected performance metrics, and mixed schemes are useful to achieve performance tradeoffs otherwise inaccessible to pure schemes.

7

CONCLUSION

Unstructured search have high potential for large-scale, highly dynamic networks, and it provides a rich field for research endeavors. Broadcast, TTL-based, RW-based schemes represent some typical instances of unstructured search. However, there exists large gap in performance landscape between these pure schemes. Mixed schemes can help to bridge the performance gap. This is important because different applications require different performance tradeoff, which the mixed scheme can provide where a pure scheme can not.

E[C]

LA P1 PA

P2

C0

LB PB

D0

E[D]

Figure 4: Pareto frontier of a mixed scheme can satisfy application requirement (shaded region) otherwise not satisfied by a pure scheme.

8

APPENDIX

We provide more detailed explanation, based on the analytical models developed earlier, the costlatency tradeoffs of TTL-based and RW-based schemes, which can be quantified by the cost-latency slope, defined in an obvious way as dC/dD. For TTL-based scheme, using (14) and (16), we have dCTTL dCTTL dp1 = = dD dDTTL TTL m N dp1

− ( N + C '2 + ) f1m ⎛ p1 1 ⎞ ⎜ − ⎟ + D '2 + π p1 ⎝ f1 2m ⎠

where in the last expression we separate out the leading term and the rest of the terms in dCTTL/dp1 and dDTTL/dp1, respectively. Exact evaluation of dCTTL/dDTTL is difficult, but we can gain some insight by just examining the ratio of the leading terms, since the individual terms decays rapidly as O(fim), and with significant jumps in TTL value (thus fi) for successive search actions. The ratio of the leading

Ubiquitous Computing and Communication Journal

9

terms (LT) is ⎛ N ⎛ dCTTL ⎞ ⎜ ⎟ = O ⎜⎜ m ⎝ dDTTL ⎠ LT ⎝ mf1

⎞ ⎟⎟ ⎠

which explains the large cost-latency slope of TTLbased schemes in Figure 3 (because N is large). We proceed in a similar manner with the RWbased schemes, the difference being that now we have two parameters (k, q), and that fi decreases slowly without jump (decrement being at most 1/N). Thus a leading term approximation does not provide much insight here. We write the full expressions below, using (21) and (24).

∂CRW ∂DRW

∂CRW ∂DRW

q

k

∂CTTL = ∂k ∂DTTL ∂k ∂CTTL ∂q = ∂DTTL ∂q

l −1

∑P f

i i

i =0 l −1

= m

q

∑P f

i i

m

mKi

ln fi

i =0

l −1

i =0 l −1

= m k

dPi

∑ dq dPi

∑ dq

fi m

fi mKi ln fi

i =0

From the above, we can explain the smaller costlatency slope by the absence of the √N term as with TTL-based schemes. Further, we can attribute the m factor in the denominator to the fact that the slope becomes smaller with larger m, as shown in Figure 3.

9

Randomization, in Proc. ACM MobiCom (2004). [7] N. Chang and M. Liu: Controlled Flooding Search with Delay Constraints, in Proc. IEEE INFOCOM (2006). [8] Ni, S.Y., Tseng, Y.C., Chen, Y.S., Sheu, J.P.: The Broadcast Storm Problem in a Mobile Ad Hoc Network, in Proc. ACM MobiCom (1999). [9] D. Zwillinger: CRC Standard Mathematical Tables and Formulae, Chapman & Hall/CRC (2003). [10] B. H. Hughes: Random Walks and Random Environments, Volume 1: Random Walks, Clarendon Press, Oxford (1995). [11] M. J. Osborne, and A. Rubenstein: A Course in Game Theory, MIT Press (1994). [12] M. M. Christos Gkantsidis and A. Saberi: Random walks in peer-to-peer networks, in Proc. of INFOCOM (2004). [13] Gkantsidis, C., Mihail, M., Saberi, A.: Hybrid search schemes for unstructured peer-to-peer networks, in Proc. of INFOCOM (2005) [14] L. A. Adamic, R. M. Lukose, B. Huberman, and A. R. Puniyani: Search in power-law networks, Physical Review E., vol. 64, no. 046135 (2001). [15] R. Gaeta, G. Balbo, S. Bruell, M. Gribaudo, M. Sereno: A simple analytical framework to analyze search strategies in large-scale peer-topeer networks, Performance Evaluation, Vol. 62, Issue 1-4, (2005)

REFERENCES

[1] E. M. Royer and C.-K. Toh: A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks, IEEE Personal Communications, Vol 6, no. 2, pp. 46-55 (1999). [2] D. Braginsky and D.Estrin: Rumor Routing Algorithm for Sensor Networks, in Proc. International Conference on Distributed Computing Systems (2002). [3] S. Shakkottai: Asymptotics of Query Strategies over a Sensor Network, in Proc. IEEE INFOCOM (2004). [4] E. Cohen and S. Shenker: Replication Strategies in Unstructured Peer-to-Peer Networks, in Proc. ACM SIGCOMM (2002). [5] Y. Baryshinikov, E. Coffman, P. Jelenkovic, P. Momcilovic, and D. Rubenstein: Flood Search under the California Split Rule, Operations Research Letters, vol. 32, no. 3, pp. 199-206, (2004). [6] N. Chang and M. Liu: Revisiting the TTL-based Controlled Flooding Search: Optimality and

Ubiquitous Computing and Communication Journal

10