Multicast Communication in Ad Hoc Networks CMPE 257 Wireless Networking SET 6 Multicast Routing in MANETs Group Communications Conference Scenario Rescue Disaster Scenario Battlefield Scenario April 05 UCSC CMPE257 April 05 1 Overview UCSC CMPE257 CMPE257 2 Multicasting Main differences stem from the type of routing structure used to connect sources with receivers of multicast group M AODV ODMRP CAMP PUMA April 05 UCSC A multicast group is defined with a unique group identifier 3 Nodes may join or leave the multicast group anytime In traditional networks the physical network topology does not change often In a MANET the physical topology can change often April 05 UCSC CMPE257 4 1 AODV Multicasting Royer00Mobicom Each multicast group has a group leader Group leader is responsible for maintaining group sequence number which is used to ensure freshness of routing information AODV Group Sequence Number Similar to sequence numbers for AODV unicast First node joining a group becomes group leader In our illustrations we will ignore the group sequence numbers However note that a node makes use of information received only with recent enough sequence number A node on becoming a group leader broadcasts a Group Hello message April 05 UCSC CMPE257 5 UCSC CMPE257 Group leader E L C J C J G G D K H A B Group and multicast tree member B N N Tree but not group member UCSC D K A April 05 Group leader E L H 6 Joining the Multicast Tree AODV AODV Multicast Tree Multicast tree links April 05 N wishes to join the group it floods RREQ Route Request RREQ CMPE257 7 April 05 UCSC CMPE257 8 2 Joining the Multicast Tree AODV Joining the Multicast Tree AODV Group leader E Group leader E L L C C J J G G H D K H A B N B N wishes to join the group N Route Reply RREP April 05 CMPE257 9 April 05 Group leader E L C J D K A B N Group member N has joined the group Tree but not group member CMPE257 CMPE257 10 Data is delivered along the tree edges maintained by the Multicast AODV algorithm If a node that does not belong to the multicast group wishes to multicast a packet G H UCSC Sending Data on the Multicast Tree Multicast tree links UCSC N wishes to join the group Multicast Activation MACT UCSC Joining the Multicast Tree AODV April 05 D K A 11 It sends a non join RREQ which is treated similar in many ways to RREQ for joining the group As a result the sender finds a route to a multicast group member Once data is delivered to this group member the data is delivered to remaining members along multicast tree edges Considerable overhead for sending data w o joining April 05 UCSC CMPE257 12 3 Leaving a Multicast Tree AODV Leaving a Multicast Tree AODV Multicast tree links Group leader E L C J J wishes to leave the group Since J is not a leaf node it must remain a tree member Group leader E L C J G G H D K H A B B N UCSC N CMPE257 13 Leaving a Multicast Tree AODV April 05 UCSC CMPE257 Group leader E L L C C J J G G H D K A B H A MACT prune D K N Node N has removed itself from the multicast group N wishes to leave the multicast group CMPE257 MACT prune B N UCSC 14 Leaving a Multicast Tree AODV Group leader E April 05 D K A April 05 J has left the group 15 Now node K has become a leaf and K is not in the group So node K removes itself from the tree as well April 05 UCSC CMPE257 16 4 Leaving a Multicast Tree AODV Handling a Link Failure AODV Multicasting Group leader E L C J G H D K When a link X Y on the multicast tree breaks the node that is further away from the leader is responsible to reconstruct the tree say node X Node X which is further downstream transmits a Route Request RREQ A B N Only nodes that are closer to the leader than node X s last known distance are allowed to send RREP in response to the RREQ to prevent nodes that are further downstream from node X from responding Nodes N and K are no more in the multicast tree April 05 UCSC CMPE257 17 April 05 Handling Partitions AODV UCSC CMPE257 CMPE257 18 Merging Partitions AODV When failure of link X Y results in a partition the downstream node say X initiates Route Request If a RREP is not received in response then node X assumes that it is partitioned from the group leader A new group leader is chosen in the partition containing node X If node X is a multicast group member it becomes the group leader else a group member downstream from X is chosen as the group leader April 05 UCSC 19 If the network is partitioned then each partition has its own group leader When two partitions merge group leader from one of the two partitions is chosen as the leader for the merged network April 05 The leader with the larger identifier remains group leader UCSC CMPE257 20 5 Merging Partitions AODV Merging Partitions AODV Each group leader periodically sends Group Hello Assume that two partitions exist with nodes P and Q as group leaders and let P Q Assume that node A is in the same partition as node P and that node B is in the same partition as node Q Assume that a link forms between nodes A and B A Assume that node A receives Group Hello originated by node Q through its new neighbor B Node A asks exclusive permission from its leader P to merge the two trees using a special Route Request P B Node A sends a special Route Request to node Q Node Q then sends a Group Hello message with a special flag All tree nodes receiving this Group Hello record Q as the leader Q April 05 UCSC CMPE257 21 Merging Partitions AODV April 05 UCSC CMPE257 22 Merging Partitions AODV RREQ can I repair partition P A A B B P RREP Yes Hello Q Q April 05 Q UCSC CMPE257 23 April 05 UCSC CMPE257 24 6 Merging Partitions AODV Merging Partitions AODV P P A Group Hello update B RREQ repair Q A B Q Q becomes leader of the merged multicast tree New group sequence number is larger than most recent ones known to P and Q both April 05 UCSC CMPE257 25 April 05 Similar to unicast AODV Uses leaders to maintain group sequence numbers and to help in tree maintenance Excessive use of RREQs can lead to multicast tree instability UCSC CMPE257 27 To construct the multicast mesh A sender node wishing to send multicast packets periodically floods a Join Query packet throughout the network April 05 26 ODMRP requires cooperation of nodes wishing to send data to the multicast group CMPE257 On Demand …