iDocSlide.Com

Free Online Documents. Like!

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Share

Description

Modeling gossip-based content dissemination and search in distributed networking

Tags

Transcript

Modeling gossip-based content dissemination and search in distributed networking
Siyu Tang
a,
⇑
, Eva Jaho
b
, Ioannis Stavrakakis
b
, Ioannis Koukoutsidis
c
, Piet Van Mieghem
a
a
Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands
b
National and Kapodistrian University of Athens, Department of Informatics and Telecommunications, Ilissia, 157 84 Athens, Greece
c
University of Peloponnese, Department of Telecommunications Science and Technology, End of Karaiskaki St., 22100 Tripolis, Greece
a r t i c l e i n f o
Article history:
Received 16 February 2010Received in revised form 26 July 2010Accepted 1 October 2010Available online 8 October 2010
Keywords:
Distributed networkingContent dissemination/searchGossip-based algorithms
a b s t r a c t
Thispaperpresentsarigorousanalyticstudyofgossip-basedmessagedisseminationschemesthatcanbeemployed for content/service dissemination or discovery in unstructured and distributed networks.When using random gossiping, communication with multiple peers in one gossiping round is allowed.The algorithms studied in this paper are considered under different network conditions, depending onthe knowledge of the state of the neighboring nodes in the network. Different node behaviors, withrespect to their degree of cooperation and compliance with the gossiping process, are also incorporated.From the exact analysis, several important performance metrics and design parameters are analyticallydetermined.Basedontheproposedmetricsandparameters,theperformanceofthegossip-baseddissem-ination or search schemes, as well as the impact of the design parameters, are evaluated.
2010 Elsevier B.V. All rights reserved.
1. Introduction
The problemof disseminatingandsearchingfor content
1
in dis-tributed and unstructured networks – such as typical peer-to-peer(P2P) and ad hoc networks – is challenging. Content disseminationcan be realized in two ways: either the content itself is disseminatedor, instead, an advertisement message indicating its availability andlocation is spread. Searching for content is typically achievedthrough the dissemination of a query looking for the content itself or for the information about its location. In both cases, a messageneeds to be disseminated. For content dissemination, this messagecontains either the content itself, or the advertisement informationabout the content. During content searching, the message to be dis-seminated is a search query looking for the content. Consequently, ascheme that effectively disseminates the message, would be applica-ble to all the aforementioned problems and such a scheme is thefocus of this paper.
We consider gossip-based (or commonly referred to asepidemic-based) message dissemination schemes that emerge asan approach to maintain simple, scalable, and fast content dissem-ination and searching in today’s distributed networks. In thispaper, two major contributions are achieved.First of all, distributed systems nowadays are large-scale andhighlydynamic.Therefore,peersmayonlycommunicatewithasub-set of peers in the network, and they have to update their views of the network periodically with others to ensure reliability
2
duringinformation dissemination. However, performing an exact analysisof the gossip-based information dissemination process with dynamicpeer partial views is extremelydifﬁcult. As we will show in AppendixA.1, the major challenge of analyzing the aforementioned problem isto deﬁne the dissemination process rigorously. The total number of states that it requires to describe the entire system exactly is2
ð
N
þ
1
Þ
2
þ
N
þ
1
. Hence,an exact analysis of sucha scenario requires a verylarge state space, which is computationally not feasible.
Secondly, to guarantee the reliability of gossip-based informa-tion dissemination, it is preferred to achieve
uniformity
3
duringneighbor selection, as underlined in [6]. Consequently, we aremotivated to perform an exact analytic modeling of gossip-basedmessage dissemination schemes under the assumption of uniformselection of multiple neighbors over the entire distributed network.The self-concerned nature and social dimensions of the peers is alsocaptured, by incorporating the notion of cooperation. Importantperformance metrics, that can reﬂect the performance of thegossip-based algorithms, are also determined analytically: e.g. thedistribution of the gossiping rounds to achieve a certain networkcoverage, or to discover content located in one or more locations.In addition, the impact of key factors such as (a) the number of
0140-3664/$ - see front matter
2010 Elsevier B.V. All rights reserved.doi:10.1016/j.comcom.2010.10.001
⇑
Corresponding author. Tel.: +31 062 1712278; fax: +31 015 27 81774.
E-mail addresses:
S.Tang@tudelft.nl (S. Tang), ejaho@di.uoa.gr (E. Jaho), ioan-
nis@di.uoa.gr (I. Stavrakakis), gkouk@uop.gr (I. Koukoutsidis), P.F.A.VanMieghem@-
tudelft.nl (P.V. Mieghem).
1
Information, content and message are interchangeable terms in this paper, as wellas peers and nodes.
2
By reliability, we mean that every peer in the network can be notiﬁed by theinformation to be disseminated.
3
By
uniformity
, we refer to the case that peers can choose their neighborsuniformly from the entire network.
Computer Communications 34 (2011) 765–779
Contents lists available at ScienceDirect
Computer Communications
journal homepage: www.elsevier.com/locate/comcom
neighbors to forward the message to, (b) the level of cooperation of the nodes, and (c) the number of content replicas available whensearching for it, etc., are evaluated. Our modeling, as well as the eval-uated metrics, provide insights in selecting proper design parame-ters so as to achieve a targeted performance.
The rest of the paper is organized as follows. In Section 2, we re-view two major assumptions when employing gossip-based con-tent dissemination schemes, and previous work performed withrespect to the two assumptions. Section 3 presents preliminarydeﬁnitions and the description of the gossip-based message dis-semination algorithms under study. Section 4 describes theanalytic models developed for the study of the algorithms, alongwith the metrics to be employed to assess the effectiveness of the considered schemes. Related work on spreading a rumor, thatappears in [18], is also discussed in this section. In Section 5, we
present the analytic results and a discussion about the impact of the key design parameters. In Section 6, we conclude the paper.
2. Gossip-based information dissemination models:background and related works
In recent years, gossip-based algorithms, which mimic thespread of disease or rumor, have been considered as efﬁcient androbust means for database maintenance and replication [4],information dissemination [6], topology construction [11], peer
membership management [16], data aggregation [12] and failure
detection [22]. It has also been implemented in many real-worldapplications: e.g. in Tribler [19], gossip-based algorithms are usedto update and maintain peer information; in CoolStreaming [23],video content delivery is scheduled by using the gossip-basedalgorithm; in wireless ad hoc networks [10], routing information
is updated between neighbors in an epidemic manner.It is commonlyassumed that, a random node
i
in the distributednetwork (with
N
+ 1 nodes) maintains a list of
m
peers (1
6
m
6
N
),which is referred to as a
peerlist L
i
, to communicate with. Thedimension,
l
i
=
dim
(
L
i
), of the vector
L
i
is deﬁned as the size of peer-list
L
i
. Usually, a node
i
is not allowed to appear in its own peerlist
L
i
, meaning that
i
R
L
i
. If the peerlist contains all the other peers inthe network, i.e.
l
i
=
N
, we say that the peer has a
complete view
of the network.If apeer
i
onlyknowsa subsetof peers inthe network,meaning that 1
6
l
i
<
N
, the peer is then said to have a
partial view
of the network. In the following, we review some previous workthat studied the performance of gossip-based algorithms associ-ated withthe aforementioned twoassumptions: completeand par-tial view of the network.
2.1. Peer complete view
In the early study of gossip-based information disseminationalgorithms, it is assumed that every peer knows all the other peers:that is, each peer has a complete view of the network (
l
i
=
N
). Thisassumption applies in a distributed network with moderate net-worksize,e.g.hundredsofnodes;andhasbeenstudiedinmanythe-oretical papers, e.g. Demers et al. [4] for database maintenance,Birmanet al.[2] forreliablemulticasting,Karp et al.[14] inthe case
of information dissemination, Kempe et al. [15] and Jelasity et al.[12] regarding gossip-based information aggregation. A completeview of peers, however, is not a realistic assumption in large-scaledistribution networks. Because distribution systems such as P2Pnetworksandadhocnetworksarefeaturedwithfrequentpeerjoin-ingsanddepartures.Thus,itisdifﬁculttoupdatethecompletenodemembership in a highly dynamic system. Moreover, maintaining acomplete view of peers at every node in the network incurs extraoverload as a result of frequent exchanges of peer information aswell as increased database maintenance functionalities.
2.2. Dynamic peer partial view
To design a scalable gossip-based information disseminationalgorithm in large-scale distributed networks, the partial view of peersistakenintoaccount.Inthiscase,arandompeer
i
onlydissem-inates the information to a subset of peers in the system, i.e.1
6
l
i
<
N
. In orderto guarantee thereliabilityofgossip-basedinfor-mationdissemination,andtocopewithpeerdynamics,theviewofapeerneedstobeperiodicallyupdated,accordingtosomepeerlistex-changeschemes.Byperiodicallyexchangingpeerlists,thefreshness(in terms of the age and availability) of peers can be updated. A de-tailed description of different peerlist exchange schemes can befound in [13]. There are many papers that have studied the perfor-mance of gossip-based algorithms from different aspects. For in-stance, Eugster et al. [5] and Ganesh et al. [9] evaluated the
performance of gossip-based algorithms with dynamic peer partialviews during information dissemination. Kermarrec et al. [16] re-lated the reliability of information dissemination to several systemparameters,e.g.systemsize,failurerates,andnumberofgossiptar-gets.Theinﬂuenceofdifferentnetworktopologiesindisseminatinginformation can be found in [8]. In [21], an exact as well as a mean-
ﬁeldapproximateanalyticmodelofspreadingvirusinageneralandﬁxednetworktopologyisproposed.Themodelin[21]considersthevirus spread in an undirected graph characterized by a symmetricadjacency matrix
A
. The epidemic threshold, which is associatedwiththelargesteigenvalueofthematrix
A
isalssrcorouslydeﬁned.
2.3. Uniformity during neighbor selection
As mentioned in [6], the assumption of uniform peer selectionguarantees the reliability (which is the focus of this paper) of infor-mation dissemination. Uniform neighbor selection can be easilysatisﬁed when peers have a complete view of the network. In thecase where peers only have partial views, we assume that the uni-formity can be achieved, by properly initializing the peerlists, andby employing appropriate peerlist exchange schemes. For instance,in [5], a lightweight probabilistic broadcast algorithm is proposed,so that uniformly distributed individual views can be maintained,regardless of the peerlist size
l
i
of a random peer
i
. However, thedesign of such peerlist exchange schemes, and of peer selectionmethodologies with partial views is out of the scope of this paper.
3. Preliminary deﬁnitions and algorithm description
We focus on the gossip-based information dissemination prob-lem under the fundamental assumption of uniform neighbor selec-tion over the entire network. The exact analysis of modelinggossip-basedinformationdisseminationwhenpeershavedynamic,partial views is not feasible, as illustrated in Appendix A.1. Theassumption of complete uniformity during neighbor selectionallows exact modeling and performance analysis, as discussed byPittel [18] and Karp et al. [14] in the case of informationdissemina-
tion, and by Kempe et al. [15] regarding gossip-based informationaggregation. The above papers studied parallel communication inwhicheachpeerselectsasingleneighborinthenetworktocommu-nicatewithateverystep,whichcanbeinefﬁcientifthereareseveralneighborsavailable.Therefore,wearemotivatedtoanalyzethenet-work performance under the circumstance that random communi-cation with multiple peers is allowed. The level of cooperation bythe peers is also considered.We consider gossip-based information dissemination andsearching over a distributed network with
N
+ 1 peers, where aunique
identiﬁcation number
(ID)
i
, 1
6
i
6
N
+ 1, is assigned to eachpeer. The information to be propagated can be a ﬁle, a music, a vi-deo, a search query or a control message. In a gossip-based scheme,
766
S. Tang et al./Computer Communications 34 (2011) 765–779
communication between neighbors takes place periodically, whichis commonly deﬁned as
gossiping rounds
. To achieve uniformity, weassume that uniform selection of multiple neighbors in one gossip-ing round is performed, and neighbor communication is deliveredover a connecting physical or virtual link. The node that initiatesthe message dissemination process is referred to as the
initiator
,which is assumed to be the only informed node at the beginningof the process. Any node that receives the message will becomean
informed
one, and will remain informed thereafter. In the ﬁrstround (
r
= 1) the initiator selects randomly
k
neighbors
4
or
gossip-ing targets
, 1
6
k
6
N
, to forward the message to. In each round, allthe informed nodes select
k
gossiping targets randomly and inde-pendently to forward the message to. The number of informednodes, in round
r
, denoted by
X
r
, is non-decreasing with
r
. Similarly,the process of the number of
uninformed
nodes, denoted by
U
r
=
N
+ 1
X
r
, which refers to the nodes that have not receivedthe message by round
r
, is non-increasing.
A node in the network, participating in the gossiping process asexpected, is classiﬁed as
cooperative
. Such nodes always acceptmessages forwarded to them, become informed and forward themessage to others according to the rules. If a node is not coopera-tive, it is referred to as
non-cooperative
. The non-cooperative nodesare presented in social and P2P networks as a consequence of re-source-preservation concern or simply selﬁsh attitude of the peers.In this paper, the level of cooperation in the network will be cap-tured by the
cooperation probability
b
, 0 <
b
6
1, associated witheach node. Nodes with cooperation probability
b
= 1 are alwayscooperative. Nodes with
b
= 0 are in essence not part of the net-work and this degenerate case is not considered. The followingassumptions are made regarding
b
to facilitate the analysis: (1)
b
is time-invariant and common to all nodes; (2) Once a node deci-des to be cooperative (or non-cooperative), it is cooperative (ornon-cooperative) to all nodes that select it in the same round;(3) In each round, a node decides to be cooperative or non-cooper-ative independently of its choices in previous rounds and of thechoices of others. Once a node decides to be cooperative, it partic-ipates in the dissemination until the end of the gossiping process.The degree of cooperation is similar as the gossiping probabilityimplemented in gossip-based routing protocols, see [10]. However,we allow (cooperative) nodes to forward the same content again,because they may choose different neighbors to gossip with inthe next round. The overall objective of employing gossip-basedalgorithm is to disseminate the message as fast as possible, so thatevery node in the network is aware about the message.Many variants of gossip-based algorithms exist based on vari-ous criteria and levels of information availability. In this paper,we study two fundamental cases which are distinguished by thepolicy of choosing gossiping targets, namely, the
blind
and
smart gossiping-target
selection schemes (in short, the blind and smartselection schemes). We describe the two schemes in more detailsin the sequel. Practical issue such as the maintenance of gossipinghistory is not the focal point of this paper.
3.1. The blind gossiping-target selection scheme
Under this scheme, no information about the status (informedor not informed) of the neighbors is available. The
k
gossiping tar-gets are selected randomly from the
N
neighbors. This scheme isthus referred to as blind gossiping-target selection, and is illus-trated in Fig. 1. In round
r
= 1, all
k
= 2 gossiping targets cooperate.In round
r
= 2, all the three informed nodes (1, 2 and 3) select eachother as gossiping targets. Thus, the number of informed nodes re-mains the same (
X
2
=
X
3
= 3). In round
r
= 3, all the three informednodes select different gossiping targets, in which nodes 4, 5, 6, 7are uninformed nodes, and node 2, 3 are informed ones. Sincenodes 5 and 6 decide to be non-cooperative in this round (1
b
la-belled in the corresponding link), the number of informed nodes inround
r
= 4 is
X
4
= 5. The blind gossiping-target selection schememodels a network with anonymous peers, or the case in whichnodes do not keep log ﬁles with all the neighbors that they havecontacted. We consider the blind gossiping-target selectionscheme as the worst case because repetitious selection of gossipingtargets may slow down the speed of information dissemination.
3.2. The smart gossiping-target selection scheme
In the smart gossiping-target selection scheme, it is assumedthat the nodes know the identity of their neighbors, and have thecomplete information about their status, in terms of being or notbeing informed about the message under dissemination. Suchinformation is piggybacked on the periodically exchanged controlpackets, as part of the standard neighborhood discovery process.In this way, the knowledge about node status are provided to theneighboring nodes, so that a node can avoid sending the same mes-sage to the nodes that already knew it. The smart selection leads toa faster message dissemination compared to the blind one, as al-ready informed nodes are avoided, as shown in Fig. 2. The smartselection serves as the optimal case for information dissemination.If
N
+ 1
X
r
<
k
, every node will be informed, meaning
X
r
+1
=
N
+ 1in the next round, because it is sufﬁcient that an informed nodechooses less than
k
targets.
4. Analysis of the gossip-based message dissemination
In this section, a rigorous and exact analysis of the proposedgossip-based message dissemination schemes is presented. Anearly study of the information dissemination problem is found in[18]. In each round, every informed person passes on the informa-tion to
k
= 1 neighbors, selected randomly and independently of allits previous choices and of all the choices of the other
N
people. Aperson may choose itself as gossiping target. Pittel [18] has derivedthe exact expression for the transition probabilities of the process{
X
r
,
r
P
1} with
k
= 1 as follows
Pr
½
X
r
þ
1
¼
j
j
X
r
¼
i
¼
N
þ
1
i j
i
ð
N
þ
1
Þ
i
P
j
it
¼
0
ð
1
Þ
t
j
it
ð
j
t
Þ
i
if
j
i
P
00 if
j
i
<
0
8><>:
ð
1
Þ
where
i
is the number of informed nodes in round
r
, and
j
is thenumber of informed nodes in round
r
+ 1.
Although the asymptotic behavior when each informed personpasses the rumor to
k
neighbors at every round is discussed in[18], the exact model is not given. In this paper, we extend the ex-act analysis to the general case with
k
P
1 in Appendix A.4, byapplying the framework developed in this section.Under the assumption of random neighbor selection over thecomplete
N
+ 1 nodes in the network, the process of the numberof the informed nodes at the beginning of round
r
, {
X
r
,
r
P
1} canbe modeled as a discrete Markov chain (MC) with state space
S
= {1,2,
. . .
,
N
+ 1}. Let
P
denote the (
N
+ 1)
(
N
+ 1) transitionprobability matrix. Each entry in
P
,
P
ij
= Pr[
X
r
+1
=
j
j
X
r
=
i
], denotesthe probability that the MC moves from state
i
to state
j
in one
4
In P2P networks, every peer is provided a list of peers to communicate with. Insome applications, such as BitTorrent [3], the maximum number of peers that a nodecan connect with is limited to certain threshold, depending on the speciﬁcconﬁguration. Our assumption of selecting
k
neighbors aims to incorporate suchimplementation in real-world distributed networks. In practice, we have
k
N
.However, we do not make such constraint during the analytic study, so that 1
6
k
6
N
is possible.
S. Tang et al./Computer Communications 34 (2011) 765–779
767
round. We denote the
probability state vector s
[
r
] in round
r
by
s
[
r
] = [
s
1
[
r
],
s
2
[
r
],
. . .
,
s
N
+1
[
r
]], where
s
i
[
r
] = Pr[
X
r
=
i
]. Clearly, the ini-tial probability state vector is
s
[0] = [1,0,0,0,
. . .
,0].The number of informed nodes after every round never de-creases, and thus
X
r
+1
P
X
r
, such that the transition probability ma-trix
P
is an upper triangular matrix, with all zeros in the lowertriangular part of
P
. The (
N
+ 1)-state MC has an
absorbing state
5
be-cause the network never leaves state
N
+ 1 when all the nodes are in-formed. The steady state vector is just the absorbing state of
p
= [0 0 0
. . .
1]. In this triangular matrix
P
, the diagonal entries arethe corresponding eigenvalues of
P
. The diagonal element on the lastrow is
P
N
+1,
N
+1
= 1, which is the absorbing state.
In the sequel, the state transition probabilities are derived byemploying a combinatorial approach. This approach is inspired bythe occupancy problem in the balls and bins model introduced intheAppendix,whentheinformednodesareballs,andthegossipingtargets are bins. Finally, performance metrics are proposed for thetwo schemes accordingly.
4.1. The transition probabilities P
ij
4.1.1. The blind gossiping-target selection scheme
Under this scheme, a node chooses its gossiping-target ran-domly from the
N
neighbors in the network (excluding itself).The transition probabilities can be calculated by applying the ballsand bins model as introduced in Appendix A.3.
4.1.1.1. Cooperative nodes with
b
= 1.
In order for the MC to movefrom state
i
to state
j
,
z
=
j
i
new nodes will need to be selectedby the
i
informed ones, after the current round. Under the blindselection algorithm, each of the
i
informed nodes selects
k
differentneighbors from the set of
j
1 nodes (a node is not allowed tochoose itself as target) blindly. The
z
new nodes should be selectedat least once, by the
i
informed nodes. Otherwise the Markov pro-cess cannot arrive at state
j
.Determining
P
ij
is analogous to ﬁnding the probability of ran-domly placing
r
groups of
k
balls to
n
1 bins (colored in redand white), with at least
m
=
z
red bins being occupied, as de-scribed in Appendix A.3. The operation of the
i
informed nodes,selecting
k
different neighbors from the set of
j
1 nodes, is equiv-alent to placing the
r
groups of
k
balls to the
n
1 bins, excludingthe white bin that has the same numbering as the group of balls.Selecting the
z
new nodes is analogous to the placement of ballsto the
m
red bins. Gossiping-target selection from the set of
i
in-formed ones is analogous to placing the balls to the
n
m
whitebins. Finally, the
z
new nodes are selected at least once, which isequivalent to requiring that at least the
m
red bins are occupied.The transition probabilities of
P
ij
are derived by substituting
m
=
z
,
n
=
j
,
r
=
i
in (26)where
N
þ
1
i z
is the number of ways to choose
z
new nodesamong the set of
N
+ 1
i
uninformed nodes at state
i
, and
N k
i
isthe total number of ways that
i
nodes can choose
k
differentneighbors.Thenon-zeroelementsin
P
arediscussedbytreatingtherelationof
i
1and
k
properly.Theﬁrstconﬁnementof
i
1
P
k
or
i
1 <
k
speciﬁesa similarconditioningas
n
1
m
P
k
or
n
1
m
<
k
in(26). The second conﬁnement of
i
6
j
6
min{
N
+ 1,
i
(
k
+ 1)} or
k
+ 1
6
j
6
min{
N
+ 1,
i
(
k
+ 1)} deﬁnes the minimum and maximumnumber of informed nodes that appears in state
j
.
When
i
1
P
k
, it is possiblethateach informednode selectsits
k
targets from the set of
i
nodes that are already informed. TheMarkov process remains in state
i
, indicating the minimumboundary of
j
=
i
. If the
i
nodes select their neighbors differently
Fig. 1.
Illustration of the blind gossiping-target selection scheme with
k
= 2 and 0 <
b
6
1. The shaded circle indicates an informed node. A dotted line between two nodesindicates communication between them in the previous round.
P
ij
¼
N
þ
1
i z
N k
i
P
z t
¼
0
ð
1
Þ
t
z t
j
1
t k
i
if
i
1
P
k
and
i
6
j
6
min
f
N
þ
1
;
i
ð
k
þ
1
Þ
g
N
þ
1
i z
N k
i
P
j
1
kt
¼
0
ð
1
Þ
t
z t
j
1
t k
i
if
i
1
<
k
and
k
þ
1
6
j
6
min
f
N
þ
1
;
i
ð
k
þ
1
Þ
g
0 otherwise
8>>>>>>><>>>>>>>:
ð
2
Þ
5
An absorbing state i is a recurrent state with the probability of returning to state i asP
ii
= 1.
768
S. Tang et al./Computer Communications 34 (2011) 765–779
from the set of
N
+ 1
i
uninformed ones, there will be maxi-mally
i
(
k
+ 1) informed ones in the next round. Notice that
i
(
k
+ 1) can never be larger than the total number of nodes inthenetwork,
j
= min{
N
+ 1,
i
(
k
+ 1)}servesastheupperboundary.
In case of
i
1 <
k
,
k
(
i
1) uninformed nodes have to beselected so that an informed node can choose
k
different neigh-bors successfully. The minimum value of
j
is thus, bounded by
k
+ 1. The upper boundary of
j
6
min{
N
+ 1,
i
(
k
+ 1)} holds asdescribed above.Under the blind selection algorithm, it is assumed that neighborselection is performed from the rest of the
N
neighbors in the net-work. A variation of the blind selection scheme is to select
k
differ-ent neighbors out of the
N
+ 1 nodes, which is also considered as ageneral setting of the rumor spreading problem in [18]. Thisassumption models an extreme case where a node has no knowl-edge about the identity of its neighbors, even about itself. In thispaper, we only present the mathematical analysis for the case of selecting
k
neighbors from the
N
+ 1 nodes in Appendix A.4. Sinceit is a variation of the blind selection algorithm, we do not evaluateits performance.
4.1.1.2. Non-cooperative nodes with 0 <
b
< 1.
Under this case, not allselected new nodes may decide to cooperate. Consequently, if outof the assumed
z
=
s
i
new selected nodes, exactly
j
i
of themdecide to cooperate, a state transition from
i
to
j
will occur. Let
B
(
z
,
j
i
,
b
) denotes the probability that there are exactly
j
i
coop-erative nodes out of the
z
new ones, given by
B
ð
z
;
j
i
;
b
Þ¼
z j
i
b
j
i
ð
1
b
Þ
z
ð
j
i
Þ
ð
3
Þ
with 0
6
j
i
6
z
.
By properly invoking (2) and (3),
P
ij
is derived for the generalcase of 0 <
b
< 1 aswhere
d
= min{
N
+ 1,
i
(
k
+ 1)}.
4.1.2. Smart gossiping-target selection scheme
Given
i
informed nodes in the network, and that each of themselects
k
different neighbors from the remaining
N
+ 1
i
unin-formed ones, the problem is analogous to the balls and bins modeldescribed in Appendix A.2, with the balls being the
i
informednodes and the bins being the
N
+ 1
i
uninformed nodes.
4.1.2.1. Cooperative nodes with
b
= 1.
Under this scheme, the transi-tion probabilities can be derived by applying (23), substituting
r
=
i
,
n
=
N
+ 1
i
,
m
=
N
+ 1
j
, and
n
m
=
z
, where
z
denotes the num-ber of new nodes selected by the
i
informed ones. Thus, we have
P
ij
¼
p
N
þ
1
j
ð
i
;
N
þ
1
i
;
k
Þ
if
N
þ
1
i
P
k
and
i
þ
k
6
j
6
min
f
N
þ
1
;
i
ð
k
þ
1
Þ
g
1 if
N
þ
1
i
<
k
and
j
¼
N
þ
10 otherwise
8><>:
ð
5
Þ
where
j
=
i
+
z
and
p
N
þ
1
j
ð
i
;
N
þ
1
i
;
k
Þ¼
N
þ
1
iN
þ
1
j
N
þ
1
ik
i
X
z
kt
¼
0
ð
1
Þ
t
z t
z
t k
i
ð
6
Þ
Notice that (6) is valid only for
N
+ 1
i
P
k
. When
N
+ 1
i
<
k
,the entirenetwork is informedwith probability 1.The conditioningof
i
+
k
6
j
6
i
(
k
+ 1) deﬁnes the minimum and maximum numberof informed nodes that appears in state
j
. If all the
i
informed nodeschoose the same
k
neighbors, there are minimally,
i
+
k
informednodes at the next state. In case that all the informed nodes choosetheir neighbors differently, the number of informed nodes at state
j
is bounded by min{
N
+ 1,
i
(
k
+ 1)}.
4.1.2.2. Non-cooperative nodes with 0 <
b
< 1.
If
s
denotes the num-ber of informed nodes at the next round,
P
is
is computed from(5). Out of the
z
newly chosen nodes, there should be
j
i
cooper-ative nodes so that the process arrives at state
j
. The probabilitythat
j
i
out of the
z
nodes are cooperative is computed from (3)
Fig. 2.
Smart gossiping-target selection with
k
= 2 and 0 <
b
6
1. The gossiping targets are randomly selected among the set of uninformed neighbors.
P
ij
¼
P
d
s
¼
jN
þ
1
i z
N k
i
sum
z t
¼
0
ð
1
Þ
t
z t
s
1
t k
i
B
ð
z
;
j
i
;
b
Þ
if
i
1
P
k
and
i
6
j
6
min
f
N
þ
1
;
i
ð
k
þ
1
Þ
g
P
d
s
¼
k
þ
1
N
þ
1
i z
N k
i
P
s
1
kt
¼
0
ð
1
Þ
t
z t
s
1
t k
i
B
ð
z
;
j
i
;
b
Þ
if
i
1
<
k
and
i
6
j
6
min
f
N
þ
1
;
i
ð
k
þ
1
Þ
g
0 otherwise
8>>>>>>><>>>>>>>:
ð
4
Þ
S. Tang et al./Computer Communications 34 (2011) 765–779
769

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x