Transcript PPT Format

Multicasting
• Multicasting is the process by which data is set to
multiple recipients.
• Simplest but a very inefficient way is to initiate multiple
unicast sessions.
• Usually multicast is receiver driven – a receiver becomes
a multicast group member and receives multicast data; but
it could also be source driven.
• Reliability difficult – UDP usually used for disseminating
data.
• An extreme example of multicast is global broadcast
wherein data is relayed to all users in the network.
• Two popular methods: Source based, Core based.
• A multicast group does not necessarily have a single
source  group communications
Popular Multicast Protocols
• DVMRP –Distance Vector Based – built on top of
RIP.
• CBT – Core Based Tree – choose a core at the
center of the network – all packets are routed
through core.
• PIM – Protocol Independent Multicast : application
layer; two modes; sparse mode and dense mode;
each mode is similar to one of the two above
schemes.
• None are dynamic enough for the ad hoc
network.. cannot cope with mobility.
Multicasting in Ad Hoc Networks
• Receivers usually join the multicast session by issuing
something like a join message.
• In ad hoc networks, the protocol should minimize the
overhead consumed in maintaining the multicast
session.
• Various protocols have been proposed. We will look
at a few.
Multicast using AODV
• By Elizabeth Royer and Charlie Perkins
•Multicasting using AODV uses messaging similar to
that used in unicast.
• RREQ and RREP messages.
• The protocol is geared towards receiver initiated
multicast.
• Each multicast group has with it an associated
group leader.
• This leader is responsible for maintaining the
multicast “group sequence number”.
• Nodes can join and leave the group at any time.
Multicast group
member
Route Discovery
Multicast tree
member
Group Leader
R
R
• Node that wishes to join or wishes
to send data to a multicast group
creates an RREQ.
• The destination address is the IP
address of the multicast group and
the RREQ includes the last known
sequence number of the group.
• JOIN is indicated via a flag.
• It broadcasts RREQ to neighbors.
?
• If it is a join request, only a group
member may respond. Else, a node
with a route to the group may reply.
• If no route is available, the node receiving the RREQ creates
a reverse route entry and forwards the RREQ.
• Source node would wait for a certain period and if
no response is received it would reply with the
broadcast ID increased by 1.
• This is done for some pre-specified number of
times.
• When a node receives a join RREQ it adds an
“unactivated” entry for the source of the RREQ in its
multicast route table.
• Each next-hop entry also has an associated ACTIVE
flag.
• If this flag is false the node does not forward
packets along that link.
• The route reply message propagates
as in AODV for unicast operations.
• How is that ?
R
R
• Respond if it is a router for the
multicast group tree (either member or
tree node) and if its recorded sequence
number for the multicast group is at
least as great as that in the RREQ
(why?).
• Naturally group leader can always
respond.
?
• The recipient node would include the
requesting node’s multihop info in its
table and generates an RREP.
• It unicasts the RREP along the reverse path recorded.
• Each intermediate node adds a forward entry into its multicast
route table.
Activation/De-activation of Multicast Route
• The source of the Join message receives multiple
RREP messages.
• Thus, an explicit message is required to ensure that
one of the paths is grafted onto the tree.
• This is done at the end of the discovery interval by
the source node.
• It keeps track of the route with the largest
multicast group sequence number.
• If there are ties, it chooses the shortest hop count
to the multicast tree.
R
R
R
• It then issues a Multicast activation
message (MACT) to the selected next
hop and sets its Activated flag for this
next hop.
• The next hop it activates the route
(sets flags for both links) and sends its
own MACT message to the next hop.
• This continues until the originator of
the RREP message is reached.
• At this point, the new path to the
multicast tree has been determined.
Leaving the group
• This MACT message is also used if a node wishes to
revoke its multicast group member status.
• If it is a leaf node and it wishes to leave the group it
may do so and prune itself out from the tree.
• Non-leaf nodes can leave the group, but they cannot
prune themselves out of the tree.
• A leaf node that wishes to leave, unicasts a MACT
message and sets the PRUNE flag set to its next hop.
• It deletes this info from its multicast routing table.
• If this makes the next hop a leaf, and the node is not a
group member, it may prune itself out of the tree.
Pruning
R
R
R
Path of
MACT
message
with
PRUNE
flag set
R
R
R
Multicast Tree Maintenance
• As nodes move, the links in the multicast tree are prone
to failure.
• Each multicast link requires ongoing maintenance to ensure
that other multicast tree members are always reachable.
• Two forms of maintenance:
• Repairing a broken tree branch following a link-break.
• Reconnecting after a network partition.
Link breaks
• If no data packets have been seen recently, a node should
hear hello packets from each of its next hops (on either
side) every hello interval.
• The data could be anything –RREQ, RREP, actual data
• If no message (of any type) is received within certain time
(called hello_life), it is inferred that the node is now out of
range – repair is required.
• When a link breaks, the node downstream of the break,
that is, the node away from the multicast group leader is
responsible for the repair.
• This distinction is required since, if nodes on both sides
try to repair the tree, it may lead to a loop.
• The downstream node that we just mentioned,
broadcasts an RREQ message.
• It also includes its distance from the group leader.
• Only those member nodes that are at least that close
can respond to this RREQ.
• This prevents nodes from the same side of the tree
from responding – thereby creating loops.
• Notice here – why not generate sequence number ?
• A small TTL can be set to begin with to make sure
that the repair is local.
• If nothing is received, then the RREQ can be
broadcast across the network.
• A node can respond to the RREQ by sending a RREP
if :
• It is a part of the multicast tree.
• It has a fresh enough multicast group sequence
number.
• Its hop count to the multicast group leader is smaller
than that indicated by the extension field of the
RREQ.
• At the end of the discovery period, our
“downstream” node selects its next hop and unicasts
a MACT message to it to activate the link.
Link Repair
Group
Leader
R
R
R
R
R
R
R
• The node that is responsible for the repair also
informs its downstream nodes of the new hop count.
• In order to indicate this new hop count, the message
sent will have the UPDATE Flag set.
• It is possible that due to this link breakage, some
upstream nodes become leaf nodes. If these nodes are
not multicast group members, they may prune
themselves from the tree.
• If the node initiating the repair fails in its first
attempt to reconnect, it re-tries for a predetermined additional number of attempts.
• If after this, it does not receive a response, it
deems that the network is partitioned.
Upon Network Partition
• When the Network is partitioned, if the node attempting
to repair the link is a group member, it becomes the group
leader.
• If it is not a group member, and the failure of the link
has caused the node to become a leaf node, it prunes itself
from the tree by sending a prune message to its next-hop.
• This node, would then, if it is a group member, becomes
the group leader. Else it proceeds as the previous node.
• If the node initiating the repair is not a group member,
and it has more than one downstream link, it cannot prune
itself from the tree. Of course, it is not eligible to become
the group leader.
• It then selects one of its next hops and unicasts a MACT
message with the Group Leader flag set.
• This would indicate that the next group member who
receives this message should become the group member.
• If the next hop is a group member, it becomes the
leader.
• If not, it unicasts it to one of its next-hop neighbors.
• Finally a group leader is selected.
• Note now, that there are two leaders for the multicast
group.
Re-Connecting Partitioned Trees
• It is possible that two partitions can reconnect in time due
to topological changes in the network.
• The Group Hello (GRPH) message is used in such a case to
reconnect the partitioned trees.
• This GRPH message is periodically broadcast by the group
leader across the network.
• It contains the IP address of the leader and the network.
• If a multicast group member from a different partition
receives this message, it notices that this contains group
leader info. that is different from its own records.
• The repair of the multicast tree is now initiated by
the group leader who has the lower IP address.
• Why not both try ?  To avoid loops.
• The group leader with this lower IP address (GL1)
unicasts a RREQ message to the other group leader
(GL2) using the node from which the GRPH was
received.
•The RREQ message has a sequence number and the
REPAIR flag is set.
• Any nodes from GL2’s partition who receive this,
should forward the message along the tree towards
GL2.
• When GL2 receives this message, it chooses the larger
of the two sequence numbers (the one received and the
one it has currently) and then it increments this value
by 1.
• It includes this in the RREP message and unicasts it
back to GL1. The REPAIR flag is set.
• The RREP message, they add the next-hop entry to
their multicast route table and activate it.
•If any node on GL1’s multicast tree receive this RREP
message they will forward this towards GL1.
• When GL1 receives’ this message, the two trees are
re-connected.
References
• Chapter 6 of book.
• Elizabeth M. Royer and Charles E. Perkins.
"Multicast Operation of the Ad-hoc On-Demand
Distance Vector Routing Protocol." Proceedings of
MobiCom '99, Seattle, WA, August 1999, pp. 207218.
• http://www.cs.ucsb.edu/~eroyer/publications.html
ADVANTAGES:
• Retains good properties of AODV. Can inter-operate
with it.
• Fairly simple. No need to continually send multicast
info – on-demand.
DISADVANTAGES:
• Not scalable.
• Location of group member could cause performance
to differ.
On Demand Multicast Routing Protocol (ODMRP)
• Invented by Mario Gerla’s group at UCLA.
•Maintains a mesh instead of a tree.
• This would avoid control overhead required for
tree maintenance.
• Group membership and multicast routes are
established by the “source” and updated on
demand.
• Like most on-demand protocols this procedure
requires a route request and a route reply.
The JOIN REQUEST message
• When a multicast source has packets to send, it
periodically advertises to the entire network, a member
advertisement packet called the “JOIN REQUEST”.
• Notice here that it is the source that initiates the
multicast !
• When a node receives the JOIN REQUEST, it stores
the ID of the upstream node from which it received
the message (if it is not a duplicate) and does a local
re-broadcast of the packet.
• When this JOIN REQUEST reaches a multicast
receiver it creates or updates its entry in its “Member
Table”  includes next hop neighbor from whom the
packet was received.
Forming the Forwarding Group
•When a node finds valid entries in its Member Table,
it locally broadcasts a JOIN TABLE to its neighbors.
• When a node receives this JOIN TABLE message it
checks if the next-node entry of one of the entries
matches its own ID.
• If it does, the receiving node realizes that it is on
the path to the source and therefore joins the
“Forwarding Group”.
• It sets what is known as the forwarding group flag
FG-flag and broadcasts its own JOIN TABLE
message.
• JOIN TABLE is propagated all the way to the
source.
Forming a Mesh Structure
• Although the data forwarding is done along the
shortest path, redundant information is stored during
the flooding process.
• This mesh would include all paths between any
source receiver multicast pair. (Note: there could be
multiple sources and receivers).
• Note that a multicast member could be a
forwarding group member for other multicast
members.
• This mesh provides richer connectivity among
multicast tree members.
Example
S1
I1
R1
R2
S2
I2
R3
Sender
Next
Node
S1
I1
S2
I2
Sender
Next
Node
S1
S1
Join Table of R1
Join Table of I1
• The arrows indicate the flow of JOIN TABLE messages.
• Note that I2 forwards packets to all three receivers but from
different sources.
• However, if the need arises, it can also forward packets from
the second source to R1.
Soft State
• In ODMRP no control messages are required to be sent to
join or leave the group.
• If a multicast source wants to leave the group it simply
stops sending the JOIN REQUEST packets.
• If a receiver wants to leave, it removes the corresponding
entries in the Member table and does not transmit the
JOIN TABLE for that group.
• Nodes in the forwarding group are demoted to nonforwarding nodes if not refreshed (no JOIN TABLES
received) before they time-out.
• However, this process may be expensive.
ADVANTAGES OF ODMRP:
• Simple to implement.
• On-Demand advantages.
• Mesh structure would offer alternate paths  more
robust than a tree.
DISADVANTAGES OF ODMRP
• Not scalable
• Soft state maintenance might result in significant
overhead.
• For mesh structure redundant info. may be
significant.
References
• S.Lee, M.Gerla and C-C.Chiang, “On Demand Multicast
Routing Protocol”, Proceedings of IEEE WCNC (Wireless
Communications and Networking Conference), 1999.
• S.Lee et al, “A Performance Comparison Study of Ad
Hoc Wireless Multicast Protocols”, Proceedings of
INFOCOM 2000. (contains info about other multicast
protocols as well).
Other Multicast Protocols
• CAMP: Core Assisted Mesh Protocol – by JJ et al.
uses multiple core nodes. Better than CBT.
• AMRIS: Ad hoc Multicast Routing Protocol using
Increasing ID Numbers: by C-K Toh et al. Establishes a
shared tree for data forwarding.
• More details in Reference 2, in previous slide and
references mentioned therein.
Because of ICNP, no class next Tuesday
which is 11/13.