Transcript Anonymous Gossip: Improving Multicast Reliability in Mobile Ad

Anonymous Gossip:
Improving Multicast
Reliability in Mobile Ad-Hoc
Networks
Ranveer Chandra , Kenneth P. Birman
Department of Computer Science
Cornell University
ICDCS 2002
AARON LEE
1
Outline
Abstract
 Introduction
 MAODV
 The Gossip Protocol
 Simulation
 Conclusion

AARON LEE
2
Abstract:
Propose a reliable multicast protocol
 Improve packet delivery and decease the
variation of packets received by different
nodes
 Two Phase Procedure

 Send
message using any Multicast protocol
 Use Anonymous Gossip to ensure the most
member receive the packets
AARON LEE
3
Introduction:
What is an Ad-Hoc Network?
Wireless medium
 Mobile nodes
 No fixed infrastructure for communication
 Applications: warfront

AARON LEE
4
Introduction:
The Model
A graph with ‘n’ nodes
 A node can move in any direction with any
speed
 Connectivity is based on transmission
power and land features
 Frequently changing connectivity and
neighborhood of the nodes.

AARON LEE
5
Introduction:
Salient Features
Dynamic Topologies
 Bandwidth Constrained Links
 Energy Constrained Operation
 Limited Security

AARON LEE
6
Multicast Routing Protocols

Tree based: MAODV, AMRIS
 Multicast
performed over an underlying
tree structure.

Mesh based: ODMRP, MCEDAR
 Multicast
over a mesh, or presence of
alternate paths

None of them try to recover packets lost
during reconfiguration
AARON LEE
7
MAODV: (Multicast Ad Hoc
On-demand Distance Vector):
Group Member
Tree Member
AARON LEE
8
MAODV: Operation
Route Reply
 Route Discovery
 Link breakages
 Partitioned Trees
 Leaving a group

AARON LEE
9
Desired Properties
Improved delivery rate
 Reduced variation in the number of
packets received by the group members.

AARON LEE
10
A Modified Protocol
Proceed as a combination of 2 subprotocols

Any existing protocol is used to multicast
messages (MAODV in our case)
ii. The Gossip Protocol recovers lost
messages.
i.
AARON LEE
11
The Gossip Protocol
 A node
randomly selects a group member.
 Sends a message history
 The receiver checks to see if it has any
extra messages
 The nodes then exchange messages and
recover the ones that are lost.
AARON LEE
12
Gossip Protocol: Issues
 How
does a node know the group
membership?
 With whom does it gossip?
 What is the direction of information
exchange?
 How is message history maintained?
AARON LEE
13
Group Membership
Maintaining group membership:
 Wired Networks: Easy because of domain
sub-domain hierarchy
 Ad-Hoc Networks: Very expensive to
maintain information about all the group
members.
 Is it necessary to know the other group
members?
AARON LEE
14
Anonymous Gossip
Randomly select one of the neighbors in
the multicast tree.
 Construct a gossip message and send it
along the selected node.
 On receiving a gossip message either
forward it along the outgoing links or
accept it with some probability if it is a
group member.

AARON LEE
15
Anonymous Gossip
C
B
D
E
A
AARON LEE
16
Ensuring Locality of Gossip

Gossiping with a near member
 Ensures

reduced traffic
Gossiping with a distant node
 Able
to recover messages that were lost in an
entire locality.
Gossip locally with a very high probability and
occasionally with distant nodes
AARON LEE
17
Ensuring Locality of Gossip
Each node maintains a field called
‘nearest_member’
 Has the information of the nearest
member by taking the link along the next
hop node.
 The probability of taking the next hop is
inversely proportional to the
‘nearest_member’ value.

AARON LEE
18
Example
2
3
B
G
1
2
A
2
3
H
C
2
D
1
2
F
AARON LEE
E
19
Probability Function
k1
k0
2
k2
kN
1
.
.
1
5
.
Smaller nearst_numbrer value is chossen with higher probability
Larger nearst_numbrer value is chossen with lower probability
AARON LEE
20
Tree Overloading

All gossip messages are sent along the
multicast tree:
 Extra
traffic on these links makes the tree
congested
 Shorter routes may exist
 During tree repair no gossip messages can be
sent
Cached Gossip with some probability!!!
AARON LEE
21
Cached Gossip

Maintain a member cache:
 Add
a member on receiving a reply of an
anonymous gossip request.
 Delete a member if no route to it is known or it
does not reply to a certain number of gossip
requests.
 Each entry is a three tuple of the address,
distance and ‘last_gossip_time’ to the node.
AARON LEE
22
Sending Gossip Requests
In each gossip round:
 Use anonymous gossip with some
probability.
 If cached gossip is chosen:
 Select
near members with a very high
probability.
 Among them select the one with the least
‘last_gossip_time’.
AARON LEE
23
Cached Gossip
C
B
D
E
(E, 2) A
(C, 2)
AARON LEE
24
Other Data Structures
Data Structures at each group member:
 History Table: A bounded FIFO buffer of
received messages.
 Lost Table: Fixed size buffer to store
sequence numbers of lost messages.
 Lost Buffer: The most recent entries of the
Lost Table.
AARON LEE
25
Data Structures
Example:
History Table: Msg1, Msg5, Msg7, … Msgn
Lost Table: 2 3 4 6 …….
Lost Buffer: 2 3
Expected Sequence Number: n+1
AARON LEE
26
Gossip Request Message
Group Address
 Source Address
 Lost Buffer
 Size of Lost Buffer
 Expected Sequence Number

AARON LEE
27
The Protocol
Each group member periodically sends a
gossip request message
 On receiving a gossip request the receiver
checks to see if it has a copy of the
requested messages.
 It then unicasts any messages found back
to the requester.
* Push would be expensive

AARON LEE
28
The Protocol
Gossip Reply
Msgs 6, 3
A
Gossip Request
B
History table: msg1, msg4, msg5
History table: msg1… msg6
Lost Table: 2, 3
Lost Table:
Lost Buffer: 3
Lost Buffer:
Expected Sequence Number: 6
Expected Sequence Number: 7
AARON LEE
29
Simulation Results






Used GloMoSim
AG is implemented over MAODV and
improvement is measured.
200m x 200m area
40 nodes and 13 group members
Random waypoint mobility model
One node sent 2201 packets to the multicast
group over 440 seconds.
AARON LEE
30
Packet Delivery vs Transmission Range
max speed = 0.2m/sec
AARON LEE
31
Packet Delivery vs Transmission Range
max speed = 2.0 m/sec
AARON LEE
32
Packet Delivery vs Transmission Range
max speed = 0.2m/sec
max speed = 2.0 m/sec
Low transmission power => less connectivity and hence reduced performance.
AARON LEE
33
Packet Delivery vs Maximum Speed
AARON LEE
34
Packet Delivery vs Maximum Speed
AARON LEE
35
Packet Delivery vs Maximum Speed
Increased Speed => frequent link breakages and hence reduced performance
AARON LEE
36
Packet Delivery vs Number of Nodes
AARON LEE
37
Results
Gossip significantly improves the number
of packets delivered.
 The variation in the number of packets
received by the different group members is
reduced
 Resulting protocol is more scalable.

AARON LEE
38
Conclusions and Future Work
A more reliable underlying multicast
protocol would yield much better results.
 Anonymous Gossip can be implemented
over any multicast protocol without much
overhead.
 Gossip for Routing

AARON LEE
39
AARON LEE
40

MAODV(Multicast Ad Hoc On-demand Distance Vector):
AARON LEE
41
MAODV: Route Discovery





Source Node sends
RREQ
Sets ‘J’ Flag if joining
Retry for some time if
unsuccessful
Become group leader
if still unsuccessful
Other nodes set up
reverse route entries
AARON LEE
42
MAODV: Route Reply




Only tree members can
respond to a join request.
RREP is generated and
unicast to the source
RREP has address of
group member and
distance from closest tree
member
Intermediate nodes also
update their tables on
receiving an RREP. AARON LEE
43
MAODV: Route Activation




Selects route based on seq
# and hopcount
Unicasts a MACT to the
selected next hop
On receiving MACT, the
node updates entry in
multicast route table
Unicasts its own MACT if it
is not a tree member.
AARON LEE
44