Transcript gossip-MASS - Duke University

SmartGossip: A Reliable Broadcast
Service for Wireless Sensor Networks
Romit Roy Choudhury
Dept. of ECE, Duke University
Joint work with
Pradeep Kyasanur (Google)
Indranil Gupta (UIUC)
1
Problem
 Broadcast in Sensor Networks
 A widely used service
 Network layer functions heavily depend on it
 Examples:
• Directed Diffusion
• Unicast or multicast routing
• Instruction / code dissemination
• Query propagation
2
Approaches
 Several approaches evolved over time
Broadcast
Storm
Complex
algo
Single point
of failures
Load
Balance
3
Recent Past
 Gossiping = Probabilistic flooding
 Nodes forward with probability, p
Source
4
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Heads
5
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Heads
6
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Heads
Heads
7
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Heads
Heads
8
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Tails
Heads
Heads
Heads
Tails
9
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Tails
Heads
Heads
Heads
Tails
10
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Tails
Tails
Heads
Heads
Heads
Heads
Tails
11
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Tails
Tails
Heads
Heads
Heads
Heads
Tails
12
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Tails
Tails
Heads
Heads
Heads
Heads
Heads
Tails
Tails
13
Recent Past
 Gossip based broadcast
 Nodes forward with probability, p
Source
Tails
Tails
Tails
Heads
Heads
Heads
Heads
For carefully chosen ‘p’
1. Simple,
the
message
reaches all nodes
2. Fault
tolerant
in minimal transmissions
3. Load-balanced
Heads
Tails
Tails
14
We Ask …
 Given some topology deployment
 How do we choose a suitable value of “p” ?
But,
for this
One
option
is toexample,
simulate
simulation
will be
the gossipresult
offline,
p = 1 “p”
and determine
15
We Ask …
 Given some topology deployment
 How do we choose a suitable value of “p” ?
 Even if topology is homogeneous
 It may change over time due to failure and mobility
16
We Ask …
 Given some topology deployment
 How do we choose a suitable value of “p” ?
 Even if topology is homogeneous
 It may change over time due to failure and mobility
Say computed p = 0.85
17
We Ask …
 Given some topology deployment
 How do we choose a suitable value of “p” ?
 Even if topology is homogeneous
 It may change over time due to failure and mobility
Fails
Say computed p = 0.85
18
We Ask …
 Given some topology deployment
 How do we choose a suitable value of “p” ?
 Even if topology is homogeneous
 It may change over time due to failure and mobility
Say computed p = 0.85
15% of packets
will not reach
these nodes
19
We Ask …
 Given some topology deployment
 How do we choose a suitable value of “p” ?
 Even if topology is homogeneous
 It may change over time due to failure and mobility
 Finally, what if topology is not known a priori ?
 How can you choose “p” ?
20
We Argue …
A broadcast service necessary
that customizes itself to the underlying topology
and
repairs itself with failures and mobility
21
Smart Gossip
 Intuition
 Identify which of YOUR friends get to know
gossips earlier than you do
• Request those friends to gossip more
 Friends who get to know gossips later than you will
request you to gossip more
 You choose your gossip probability as:
• MAX value of all requests from YOUR friends
22
For Example …
 When H spreads a gossip
 F gets gossip only from G
 F asks G to always gossip
 Thus, pG = 1.0
 B receives gossip from A,C,D,E,F
 B also observes that A,C,D,E received gossip from F
• Indicates that B must depend only on F (parent)
• A,C,D,E and B are independent (siblings)
 B asks F to always gossip, thus pF = 1.0
23
For Example …
 B asks F to always gossip,
thus pF = 1.0
 B does not require siblings
A,C,D,E to gossip at all
 Thus pA = 0, pC = 0, pD = 0, pE = 0
Observe that only 2 transmissions
(from G and F) are sufficient for broadcast
24
Protocol Details
 For first gossip pkt, nodes transmit with p=1

Enables nodes to deduce neighbor dependences

Transmitters piggyback pkt with parent-id from
which it received the pkt

Nodes record transmitter-id, and its parent-id,
and deduce parent, child, sibling relationships …
… see next slide
25
Deducing Relationships
SA
S
Child = {A}
A
Parent = {A}
B
C
E
Parent = {A}
26
Deducing Relationships
S
Child = {A}
A
Child = {B}
Parent = {A}
B
AB
C
Parent = {B}
E
Parent = {A}
Sibling = {B}
27
Deducing Relationships
S
Child = {A}
A
Parent = {A}
B
Child = {B}
C
Parent = {B}
AE E
Parent = {A}
Sibling = {B}
28
Deducing Relationships
S
Child = {A}
A
Sibling = {E}
Parent = {A}
B
Child = {B,E}
C
Parent = {B,E}
E
Parent = {A}
Sibling = {B}
29
Choosing Probabilities
 Each node calculates number of parents ( k )
 Assume 99% assurance necessary for gossip
 Node suggests each parent to gossip using ‘p’:
0.99 = ( 1 – (1 - p)k )
 Each node receives multiple requests of ‘p’
 Uses Max { pi } as its own gossip probability
S
A
B
C
Parent={B,E}
E
30
Choosing Probabilities
 Each node calculates number of parents ( k )
 Assume 99% assurance necessary for gossip
 Node suggests each parent to gossip using ‘p’:
0.99 = ( 1 – (1 - p)k )
 Each node receives multiple requests of ‘p’
 Uses Max { pi } as its own gossip probability
S
p = 1.0
A
p = 1.0
p = 1.0
B
p = 0.9
C
p = 0.9
E
31
Choosing Probabilities
 Each node calculates number of parents ( k )
 Assume 99% assurance necessary for gossip
 Node suggests each parent to gossip using ‘p’:
0.99 = ( 1 – (1 - p)k )
 Each node receives multiple requests of ‘p’
 Uses Max { pi } as its own gossip probability
p = 1.0
S
p = 1.0
A
p = 0.9
B
E
p=0
C
p = 0.9
32
The Bigger Picture
Src
33
Reliability (Details in paper)
 Node Failures
 Node failures affect broadcast
 Source node flags packet periodically (p=1)
 Allows for updating dependences
 Link Losses
 Node requests upstream nodes to retransmit
• We require each node to buffer few packets
 Children overhear this request
 Children do not request retransmissions themselves
34
Evaluation
 Qualnet Simulator, ver 3.7
 Metrics used
 Average Reception Percentage
 Average Forwarding Percentage
 Resilience to link/node failures
35
Percolation
Smart Gossip
Adaptive Overhead
Adaptive Neighbor
36
Forwarding Overhead
37
Adaption to Node Failures
Nodes gossip more to compensate for other failing nodes
38
Conclusion
 Broadcast is an important problem
 Gossip is good – but not practical for sensor nets
 Need to adapt gossip based on topology / failures
 Smart Gossip
 Form dependence graphs using distributed protocol
 Dependence relations suggest suitable probability
 Results
 Overheads are low, and yet good percolation
 Robust to node and link failures
39
Questions?
40
Protocol Details
 For first gossip pkt, nodes forward with p=1

This is to let nodes deduce topology dependences

When forwarding, node A piggybacks the packet
with parent-id from which it received the gossip

If parent-id of received packet is a neighbor of B
A
AS
S
S
A
B
C
41
Percolation
Smart Gossip
Adaptive Overhead
Adaptive Neighbor
42
Deducing Relationships
 Assume gossip sent by node i to node j
 If parent (i)  Neighbor (j)
• Parent ( j )  i
SA
S
Child = {A}
A
Parent = {A}
B
C
E
Parent = {A}
43
Deducing Relationships
 Assume gossip sent by node i to node j
 If parent (i)  Neighbor (j)
• Parent ( j )  i
 If parent (i)  Neighbor (j)
• If parent (i)  Parent (j), then Sibling ( j )  i
• If parent (i)  Sibling (j), then Children ( j )  i
• If parent (i)  Children (j), then Children ( j )  i
S
Child = {A}
A
Child = {B}
Parent = {A}
B
AB
C
Parent = {B}
E
Parent = {A}
Sibling = {B}
44
Deducing Relationships
 Assume gossip sent by node i to node j
 If parent (i)  Neighbor (j)
• Parent ( j )  i
 If parent (i)  Neighbor (j)
• If parent (i)  Parent (j), then Sibling ( j )  i
• If parent (i)  Sibling (j), then Children ( j )  i
• If parent (i)  Children (j), then Children ( j )  i
S
Child = {A}
A
Parent = {A}
B
Child = {B}
C
Parent = {B}
AE E
Parent = {A}
Sibling = {B}
45
Deducing Relationships
 Assume gossip sent by node i to node j
 If parent (i)  Neighbor (j)
• Parent ( j )  i
 If parent (i)  Neighbor (j)
• If parent (i)  Parent (j), then Sibling ( j )  i
• If parent (i)  Sibling (j), then Children ( j )  i
• If parent (i)  Children (j), then Children ( j )  i
S
Child = {A}
A
Sibling = {E}
Parent = {A}
B
Child = {B,E}
C
Parent = {B,E}
E
Parent = {A}
Sibling = {B}
46
Robustness
 Nodes/Links fail with time
 Topology changes
 Gossip probabilities need to be revised
 Gossip source periodically sets flag in packet
 All nodes use p=1 for flagged packets
47
Wireless Losses
 Resilience toward wireless losses necessary
 If F does not get a packet, all its dependents will
also not get it
 SmartGossip:
 F requests its parents for missing pkt (seq # j)
 F piggybacks { j } in following gossip packets
 Nodes A,B,C,D,E do not request for packet j
• They know that F is trying to retrieve it
48