Transcript lecture-broadcast

Wireless Networking & Mobile Computing
ECE 299.02 Spring 2007
Ian Wong
Adapted from Ni et al
1
The Broadcast Storm Problem in a
Mobile Ad-Hoc Network
Sze-Yao Ni, Yu-Chee Tseng, YuhShyan Chen, Jang-Ping Sheu
2
Background
3
What are we looking at?
 Mobile Ad-hoc networks
 No dedicated servers/base stations for the entire
network
 Units can move freely
 Utilizes CSMA without CD
Adapted from Ni et al
4
If you don’t know where they are…
What do you do?
5
Broadcast!
Adapted from Ni et al
6
Broadcast!
Hi!!!
Adapted from Ni et al
7
Broadcast!
Adapted from Ni et al
8
So, what’s the problem?
 Wireless CSMA inherently without CD, so a
transmitter cannot inherently be aware of
collisions
 Broadcasts are spontaneous
 They happen whenever they need to
 Broadcasts aren’t reliable
 A RTS/CTS and even an ACK are too much to ask
for!
Adapted from Ni et al
9
We’ve lost our reliable transport!
10
How would it happen?
In a very nice, linear system…it
works…
Adapted from Ni et al
11
But…?
Seven transmissions when only three
It’s like a flood! Hence….flooding!
are required!
Adapted from Ni et al
12
So, the problem ends up being…
 Redundant rebroadcasts
 Propagating (rebroadcasting) an old packet to a
node is pointless!
 Increased contention
 Spending time propagating an old packet consumes
unnecessary bandwidth
 Increased collisions
 Without backoff mechanisms and RTS/CTS,
collisions occur more frequently
Adapted from Ni et al
13
So, about rebroadcasts…
 They can be expensive! Use with caution!
• Where INTC(d) is the intersection area, where d є {0,r}
 If d = r, then πr2 – INTC(r) ≈ 0.61πr2
 Maximal improvement of at most 61%
 Average Improvements
• ≈ 0.41πr2 for the first
• ≈ 0.19πr2 for the second
• < 0.05πr2 for the fifth…
Adapted from Ni et al
14
Besides sheer area, once we’ve heard
the first broadcast…
15
…who’s the first to speak?
An analysis of Contention
 The probability of contention can be
calculated by:
 In the simplest case, when two receive the
same broadcast, the chance of contention is
≈ 59%
 This probability increases with increasing local
density
Adapted from Ni et al
16
…Can you hear me now? Collisions!
 CSMA/CA backs off if the carrier is busy
 But,
 Overly quiet channels may lead many nodes to
expend their backoff and transmit at the same
time
 No RTS/CTS dialogue precludes forewarning
 Without CD (collision detection), the host will
waste bandwidth until packet transmission
completes
Adapted from Ni et al
17
So, given these problems…
…how could we solve them?
18
What if…
…only a few need to yell?
An exercise in probability…
19
A Probabilistic Approach
 What does it mean?
 Always yelling once you’ve heard something
• Probability of P = 1
 Maybe yelling once you’ve heard something
• Probability of P < 1
 Assumptions
 Assumes that the topology of the network is fairly
dense, or that the probabilities are selected based
on the network topology
Adapted from Ni et al
20
So, since it’s probabilistic…
…what are the chances that it’ll be
effective?
21
First…what is effective?
 Performance metrics
 Reachability
• Total # of reachable nodes/# of initially reachable nodes
 Saved ReBroadcast
• SRB = (r-t)/r
 Average latency
• tlast rebroadcast – tfirst broadcast
Adapted from Ni et al
22
Now that we’ve got metrics…
…how does our theory fare?
23
Analysis of Probabilistic Propagation
 SRB decreases by ~(1-P) as P increases
 Broadcast latency increases as P increases, but more
sparse networks complete broadcasting faster
 Why?
Adapted from Ni et al
24
One Mississippi, Two Mississippi…
Using Counters!
25
Counting sheep…
 Why count?
 Similar to deterministic probability
 How do we do it?
 After hearing a message for the first time, start a
counter and count the number of overheard
repeats
 If after a random backoff the number of counts
does not exceed threshold, rebroadcast the
message
 If the number of repeats exceeds the threshold
before the time has elapsed, then do not
propagate the message
Adapted from Ni et al
26
I count one sheep, two sheep,…
 High RE in C ≥ 3
 SRB decreases with decreasing density
 Why?
 27% to 67% savings for higher density maps
 Low latency
Adapted from Ni et al
27
Why transmit purely at random…
…when you can transmit only if you
gain an advantage?
28
Leveraging distances!
 Instead of simply counting, let’s improve
that…why not look at additional coverage?
 Define minimum amount of extra coverage
calculated by πr2 – INTC(r)
• Define a minimum distance D that provides at least a
certain amount of additional coverage
 Out of all overheard transmissions, determine the
distance dmin to the closest node.
 If distance dmin < D, don’t transmit…
 If distance dmin > D, propagate!
Adapted from Ni et al
29
Do levers work?




Ds selected as effective comparisons for Counter schemes
Equally high RE as counter
SRB significantly lower (10% to 37%)
Higher latency
 If counter and distance are so similar, why all these issues?
 At higher data rates, SRB and RE drops. Why?
Adapted from Ni et al
30
More area?
Is there a better way to estimate
extra coverage?
31
Location, location, location!
 Given that we know relative distances, what
about absolute distances?
 Acquire the location of broadcasting hosts to
precisely estimate coverage
• Use external positioning devices, like GPS
 Improves Distance-based topology
 Recalculate effective area when you hear each new
retransmission
Adapted from Ni et al
32
Absolute location locates absolutely…but
does it help absolutely…?
 High RE
 High SRB
 Lowest latency of four statistical/geometrical
methods
Adapted from Ni et al
33
Aside from statistics and geometry…
…how else can you maximize your
throughput?
34
Clusters
 Go on…make little groups and talk to who’s
around you…
 Each host knows who’s around it
 One card, low draw to see who gets to be the local
cluster head
 Local heads draw between one another to figure
out who is a global head
 How does this help?
 Only the cluster heads need to retransmit to the
cluster
 Gateways need to retransmit between cluster
heads
 Members just sit and listen
Adapted from Ni et al
35
This ain’t no cluster…
 Highest consistent SRB
 Lowest latency
 Significant drop in RE at low densities
Adapted from Ni et al
36
So…
 One problem. Five approaches…
 V(aries), H(igh), M(edium), L(ow)
Effectiveness





Probabilistic
Counting
Distance
Location
Clustering
Adapted from Ni et al
RE
SRB
Latency
V
H
H
H
V
V
M
L
H
H
M
L
M
L
L
37
Not just probabilistic, but better!
 Gossiping (Probabilistic Flooding)
 Difference from ideal situations and packet
collision issues due to phase transitions – small
changes can cause large changes [3]
 Hypergossiping [2]
 Partition nodes
• Efficient intra-partition forwarding
• Retransmit an adequate subset of messages on partition
joins
 Adapt gossiping probability to node density to
reduce broadcast storms
Adapted from Ni et al
38
References
[1] Sze-Yao Ni, Yu-Chee Tseng, Yuh-Shyan Chen, Jang-Ping Sheu. The Broadcast
Storm Problem in a Mobile Ad-Hoc Network
[2] Abdelmajid Khelil, Pedro Jose Marron, Christian Becker, Kurt Rothermel
Hypergossiping: A Generalized Broadcast Strategy for Mobile Ad Hoc
Networks
[3] Yoav Sasson David Cavin Andr´e Schiper. Probabilistic Broadcast for Flooding in
Wireless Mobile Ad hoc Networks
Adapted from Ni et al
39