Transcript Reliable Multicast Protocols for MANET

Reliable Multicast
Protocols for MANET
Reporter : 吳政鴻
Date : 2005/5/17
1
Outline
• An Overview of MANET
• An Overview of Reliable Multicast Protocol
• Automatic Retransmission reQuest Based
Reliable Multicast Protocols (ARQ-Based)
– Reliable Multicast Algorithm (RMA)
– Reliable Adaptive Light Weight Multicast Transport
protocol (RALM)
– Reliable, Adaptive, Congestion-Controlled Adhoc
Multicast Transport Protocol (ReAct)
2
• Gossip-Based Reliable Multicast Protocols
– Anonymous Gossip (AG)
– Route Driven Gossip (RDG)
• Forward Error Correction (FEC) Based
Reliable Multicast Protocols
– Reliable Multicast Data Distribution Protocol
(RMDP)
• Comparisons
• Conclusions
3
An Overview of MANET
• Definition
• Characteristics
• Limitations
4
Definition
• Mobile ad hoc network(MANET), or simply ad hoc
network, comprises nodes that freely and dynamically
self-organize into arbitrary and temporary network
topology without any infrastructure support.
(Chlamtac,Conti,andLiu,2003)
• Nodes are communication devices comprise of laptop
computer, PDA, mobile phone and etc. Nodes formanet
work to communicate with each other.
• Networking infrastructure refers to the facility of which
the sole purpose is to carry the data generated by each
node to the respective destination node
5
Characteristics
• Infrastructure-less or with minimum
infrastructure support
• Self-organizing and self-managing
• Multi-hop
6
Infrastructure-less or
with minimum
infrastructure support
• A Pure ad hoc network does not have, or
simply does not rely on infrastructure
support (for routing, network management,
and etc.)
• A hybrid ad hoc network consists of both
client nodes and infrastructure nodes,i.e.
nodes whose function is merely
transporting traffic for the client nodes
• Hybrid networks are more common
7
Self-organizing and selfmanaging
• Since network infrastructure is not
available, the nodes must organize and
maintain the network by themselves
8
Multi-hop
• Since each node can route traffic for the
others, multi-hopping is possible.
• Single hop ad hoc network does not form a
large scale network
9
Limitations
• Ad hoc network is not a one size fit all
measure.
Its current limitations are listed below:
– Killer application has not turned up
– Acceptance by users is unclear
– Delay caused by multi-hopping
– Quality of service is difficult to be guaranteed
– Prone to security threat
10
An Overview of Reliable
Multicast Protocol
•
•
•
•
What is Multicast Communication?
What is Reliable Multicast?
What is Reliable Multicast use in MANET?
Three categories according to the recovery
mechanisms being used
11
What is Multicast
Communication?
• Group communication mechanism
– Provides one-to-many and many-to-many
communication
• Efficient dissemination of messages
– Network-based duplication (when needed)
– Multicast retransmissions
– Bandwidth savings
– Parallel delivery at multiple locations
12
IP Multicast
Communication
13
Example IP Multicast
Use (Access Grid )
14
What is Reliable
Multicast?
• Properties similar to TCP
• Application-level program
• Uses IP Multicast as the underlying communication
mechanism
• Reliable and ordered delivery of messages within a
group
• Tracks group membership
• IETF Reliable Multicast Transport Working Group is
defining standardized building blocks
15
Example Reliable
Multicast Use (Remote
Instrument Access)
16
What is Reliable
Multicast use in
MANET ?
• Reliable multicast becomes a very challenging
research problem due to high packet loss rate
pertained to MANET
• Reliable multicast solutions proposed for wired
network can not be directly ported for MANET
–
–
–
–
link breakages
route changes
concentrated retransmissions
concentrated retransmissions and heavy overhead
17
Three categories
according to the
recovery mechanisms
being used
• Automatic Retransmission Request (ARQ)based
– Lost packets are retransmitted by the sources until
they are recovered at all the receivers
• gossip-based
– multicast packets are repeatedly transmitted for a few
times by a few of the multicast members in a peer-topeer fashion
• Forward Error Correction (FEC)-based
– embed redundant data (e.g., erasure code) in each
packet before transmitting.
18
• Automatic Retransmission reQuest
Based Reliable Multicast Protocols
(ARQ-Based)
– Reliable Multicast Algorithm (RMA)
– Reliable Adaptive Light Weight Multicast
Transport protocol (RALM)
– Reliable, Adaptive, Congestion-Controlled
Adhoc Multicast Transport Protocol (ReAct)
19
Reliable Multicast
Algorithm (RMA)
• Assumption
• Protocol description
• Advantage versus Disadvantage
20
Assumption
• RMA is a multicast protocol supporting
reliable transmission via acknowledgement
from receivers and retransmissions from
the sources
• RMA assumes that the sources have the
full knowledge of group membership via
JOIN or ACK messages
21
Protocol description
• RMA works in two phases:
– multicast
– retransmission
• Two types of multicast messages to the
group member
– MKNOWN
• unicast
– MUNKNOWN
• broadcast
22
• Source waits for MACKs for a period of time after
the messages being sent out
• If the source is not able to collect all the MACKs
from all the group members, the source enters
the retransmission phase and sends a
MUNKNOWN message with a flag in
RETRANSMIT field
• Receiver could broadcast MACK to the source
(BMACK), if a return path is not valid
23
Hello Message
24
MKNOWN
Message
25
MUKNOWN
Message
26
MACK
Message
27
BMACK
Message
28
Advantage versus
Disadvantage
• Advantage
– The sender guarantees retransmissions of lost
packets
– less message forwarding and less bandwidth
usage
• Disadvantage
– all the receivers must send ACKs back to the
sender == >> Feedback implosion
29
Reliable Adaptive Light
Weight Multicast Transport
protocol (RALM)
• Assumption
• Protocol description
• Advantage versus Disadvantage
30
Assumption
• RALM assumes that the group
membership is known to the sources
• This enables the sources to maintain a
Receiver List
31
Protocol description
• Source selects a node from the receiver
list as a feedback receiver in a roundrobin fashion and notifies it together with
the data packets
• The feedback receiver is responsible for
replying ACK or NACK to the source until
it collects all data packets
32
• If Source receives a NACK, it enters the
retransmission phase by slowing down
the transmission rate first and retransmits
the lost packets to the group until ACK to
the lost packets are received and the
current feedback receiver successfully
obtains all the packets
33
• This single-node feedback approach is
effective when packet losses are due to
congestion at a bottleneck link
34
Receiver List
B
A
C
B
D
C
A
Rec
Fee
Rec
Rec
C
B
D
35
36
37
Advantage versus
Disadvantage
• Advantage
– RALM also reduces control overhead by
requiring one receiver at a time
– Effectively reduces the burden at the sender in
receiving and processing the feedbacks and
reduces congestion around the sender
== >> Solve Feedback implosion
• Disadvantage
– RALM works well for static MANET
38
Reliable, Adaptive,
Congestion-Controlled Adhoc
Multicast Transport Protocol
(ReAct)
• Assumption
• Protocol description
• Advantage versus Disadvantage
39
Assumption
• source-oriented component works the
same as RALM
40
Protocol description
• ReAct adds a new recovery mechanism
“local recovery” to RALM
• Local recovery occurs right after the
receiver detects a lost packet
• the receiver requests one of the upstream
group members (recovery node) starting
from the closest one
41
• The recovery node responses with the
expect packets if it has them or it rejects
the request
• Upon receiving the rejection, the receiver
will retry recovery by choosing a farther
away upstream node as a recovery node
• Only after several failures of the local
requests, the receiver sends a NACK to
the source for retransmission
42
A
C
B
Packet Loss
43
Advantage versus
Disadvantage
• Advantage
– Local recover gets missing packets faster
than source-oriented retransmission, reduces
the burden/congestion at the source, and
alleviates potential feedback implosion
problem
• Disadvantage
– when local recovery frequently fails and
source recovery is triggered all the time
44
• Gossip-Based Reliable Multicast
Protocols
– Anonymous Gossip (AG)
– Route Driven Gossip (RDG)
45
Anonymous Gossip (AG)
• Assumption
• Protocol description
• Advantage versus Disadvantage
46
Assumption
• Implements gossip-based recovery on top
of a multicast operation
• Gossip-messages only contain sequence
numbers for missing packets
• Routing information of MAODV at receiver
side is adopted for sending gossips
47
Protocol description
• AG works in two phases:
– multicast
• Source sends multicast packets in best-effort
– Recovery
• runs at background for recovering lost packets
• a group member periodically transmits a
gossip request message about missing
and successfully received packets to a
pseudo-randomly selected neighbor node
48
• If receiver receiving the gossip request
– non-group-member neighbor simply forwards
the packet to one of its neighbors
– Group-member neighbor will accept and reply
the gossip message with a certain probability
• This procedure ends until a node replies
the gossip message or the lifetime of the
message expires.
49
Multicast
Protocol
+
Classical
Gossip
=
Probabilistic
Reliability
• Works in background with multicast
protocol.
• Members “gossip” randomly with other
members to recover lost messages.
• Probabilistic reliability guarantees.
50
Classical Gossip
S
D
51
Anonymous Gossip
S
D
52
Informed Gossip
S
D
53
Advantage versus
Disadvantage
• Advantage
– AG is a reliable multicast protocol that does not
require membership information.
– To reduce the network traffic, gossip requests are
sent to nearer members with higher probability than to
farther members.
– AG operates independent of topology changes
• Disadvantage
– AG can not guarantee the missing packets will be
answered eventually
54
Route Driven Gossip
(RDG)
• Assumption
• Protocol description
• Advantage versus Disadvantage
55
Assumption
• RDG does not use full multicast
membership information, but partial
knowledge
• RDG builds on top of a MANET unicast
routing protocol DSR
56
Protocol description
• each existing member will only reply to the
solicitation with a probability, resulting in a partial
membership view at the joining node
• A gossip message generated at each session
contains both new data packets and packet IDs
of missing packets
• The gossip message is sent to F (fan out
parameter) other group members randomly
picked up from its partial member view
57
• each new data packet will be gossiped for
a few number of times (quiescence
threshold) to ensure its spreading
58
Data Structures
Identifier
4
5
0
Group identifier
5
JOIN
RECEIVEGREQUEST
1
Data buffer
• new
0
3
• old
0
GOSSIP
5
RECEIVEGOSSIP
1
View
LEAVE
• active
• passive
fanout
2
• remove
1
0
1
F
Push
Pull
quiescence
threshold
τq
Data packets, digests of
missing packets, view
59
16
11
3
6
12
10
15  9, 10
7
4
19
12
Infected
13
9
6
20
10
16
11
9
9  3, 5
5  1, 19
7
10  1, 13
13  10, 15 19
2  1, 8
8
Round 1
3
13
15
17
1
2
8
16
18
15  5, 3
9  10, 13
4
10  2, 8
14
6
5
10
7
Round 0
11
20
15
12
17
2
3
18
5
14
1
19
13
9
6
20
15
16
11
9
18
5
3
13
5
4
18
20
15
12
10
14
14
17
1
7
2
2
8
Round 2
Susceptible
17
1
All
members
4
receive the
message.
19
Crashed Member
8
Round 3
Non member nodes
60
Advantage versus
Disadvantage
• Advantage
– RDG eliminates burdens at sources for handling
retransmission; instead, every group member
participates in loss recovery
– The performance of the protocol can be turned
through the parameters fan out and quiescence
threshold
• Disadvantage
– RDG can not guarantee reliable delivery of all the
packets
61
• Forward Error Correction (FEC) Based
Reliable Multicast Protocols
– Reliable Multicast Data Distribution
Protocol (RMDP)
62
Reliable Multicast Data
Distribution Protocol
(RMDP)
• Assumption
• Protocol description
• Advantage versus Disadvantage
63
Assumption
• FEC transmits redundant data with the
original data transmission
• the k packets will be encoded in to n
(n > k) packets. The n packets include
redundant information
64
Protocol description
• RMDP is a hybrid FEC+ARQ protocol for
reliable distribution of bulk data receivers
• After it receives k different packets, it
decodes for the original source data
• The source adjusts its sending pointer to
the packet where the largest number of
packets is requested by different receivers
65
66
Advantage versus
Disadvantage
• Advantage
– FEC technique helps RMDP to tolerant packet losses and to
recover from losses with less feedback packets to the sources
==>> Solve Feedback implosion
– when errors or packet losses happen at the receiver, original data
can be reconstructed using the ones received
• Disadvantage
– RMDP incurs long packet latency because a receiver has to
wait for the reception of k packets before it can decode and
delivery them to applications
– Using the redundant data to increase packet length
67
Comparisons
68
Conclusions
• classification based on the recovery
mechanisms
• The analyses and comparisons will help in
choosing a suitable reliable multicast
protocol for specific network conditions
69
REFERENCES
• Beini Ouyang and Xiaoyan Hong, Yunjung Yi, A Comparison of
Reliable Multicast Protocols for Mobile Ad Hoc Networks, IEEE,
2005.
• Thiagaraja Gopalsamy, Mukesh Singhal, D. Panda and P.
Sadayappan, A Reliable Multicast Algorithm for Mobile Ad hoc
Networks, IEEE, 2002.
• Ken Tang, Katia Obraczka, Sung-Ju Lee, Mario Gerla, Reliable
Adaptive Lightweight Multicast Protocol, IEEE, 2003.
• Ken Tang, Katia Obraczka, Sung-Ju Lee, Mario Gerla, A Reliable,
Congestion-Controlled Multicast Transport Protocol in Multimedia
Multi-hop Network, IEEE, 2002.
70
• Ranveer Chandra, Venugopalan Ramasubramanian, Kenneth P.
Birman, Anonymous Gossip: Improving Multicast Reliability in Mobile
Ad-Hoc Networks, IEEE, 2001.
• Jun Luo, Patrick Th. Eugster, Jean-Pierre Hubaux, Route Driven
Gossip: Probabilistic Reliable Multicast in Ad Hoc Networks, IEEE,
2003.
• Luigi Rizzo, Lorenzo Vicisano, RMDP: an FEC-based Reliable
Multicast protocol for wireless, CiteSeer, 1998.
71
• END
72