CMPE 257 Wireless and Mobile Networking Spring 2002 Week 5 CMPE 257 Spring 2002 1 Multicast Communication in Ad Hoc Networks Group Communications Conference Scenario Rescue Disaster Scenario Battlefield Scenario CMPE 257 Spring 2002 2 Multicast routing classification Routing Protocols Table Driven Proactive AMRoute CAMP WRP On Demand Reactive M AODV CMPE 257 Spring 2002 AMRIS ODMRP 3 Overview AMRoute AMRIS ODMRP M AODV CAMP Flooding and Variations CMPE 257 Spring 2002 4 Multicasting A multicast group is defined with a unique group identifier Nodes may join or leave the multicast group anytime In traditional networks the physical network topology does not change often In MANET the physical topology can change often CMPE 257 Spring 2002 5 Multicasting in MANET Need to take topology change into account when designing a multicast protocol Several new protocols have been proposed for multicasting in MANET CMPE 257 Spring 2002 6 On Demand Multicast Routing Protocol ODMRP ODMRP requires cooperation of nodes wishing to send data to the multicast group To construct the multicast mesh A sender node wishing to send multicast packets periodically floods a Join Data packet throughout the network Periodic transmissions are used to update the routes CMPE 257 Spring 2002 7 On Demand Multicast Routing Protocol ODMRP Each multicast group member on receiving a Join Data broadcasts a Join Table to all its neighbors Join Table contains sender S next node N pairs next node N denotes the next node on the path from the group member to the multicast sender S When node N receives the above broadcast N becomes member of the forwarding group When node N becomes a forwarding group member it transmits Join Table containing the entry S M where M is the next hop towards node S CMPE 257 Spring 2002 8 On Demand Multicast Routing Protocol ODMRP Assume that S is a sender node S N M A D C B Join Data T Multicast group member CMPE 257 Spring 2002 9 On Demand Multicast Routing Protocol ODMRP N S M Join Data A Join Data Join Data T D C B Multicast group member CMPE 257 Spring 2002 10 On Demand Multicast Routing Protocol ODMRP S N M A Join Table S M T D C B Join Table S C Multicast group member CMPE 257 Spring 2002 11 On Demand Multicast Routing Protocol ODMRP Join Table S N S T F N M A D F C B Join Table S N F marks a forwarding group member CMPE 257 Spring 2002 12 On Demand Multicast Routing Protocol ODMRP Join Table S S N S F M A F C B F T D Multicast group member CMPE 257 Spring 2002 13 On Demand Multicast Routing Protocol ODMRP F S N M A F C B F T D Join Data T Multicast group member CMPE 257 Spring 2002 14 On Demand Multicast Routing Protocol ODMRP F S N M F A Join Table T C F F C B T D Join Table T T Join Table T D Join Table T C Multicast group member CMPE 257 Spring 2002 15 ODMRP Multicast Delivery A sender broadcasts data packets to all its neighbors Members of the forwarding group forward the packets Using ODMRP multiple routes from a sender to a multicast receiver may exist due to the mesh structure created by the forwarding group members CMPE 257 Spring 2002 16 ODMRP No explicit join or leave procedure A sender wishing to stop multicasting data simply stops sending Join Data messages A multicast group member wishing to leave the group stops sending Join Table messages A forwarding node ceases its forwarding status unless refreshed by receipt of a Join Table message Link failure repair taken into account when updating routes in response to periodic Join Data floods from the senders CMPE 257 Spring 2002 17 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 Similar to sequence numbers for AODV unicast First node joining a group becomes group leader A node on becoming a group leader broadcasts a Group Hello message CMPE 257 Spring 2002 18 AODV Group Sequence Number 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 CMPE 257 Spring 2002 19 AODV Multicast Tree Multicast tree links Group leader E L C J G H D K A B Group and multicast tree member N Tree but not group member CMPE 257 Spring 2002 20 Joining the Multicast Tree AODV Group leader E L C J G H D K A B N N wishes to join the group it floods RREQ Route Request RREQ CMPE 257 Spring 2002 21 Joining the Multicast Tree AODV Group leader E L C J G H D K A B N N wishes to join the group Route Reply RREP CMPE 257 Spring 2002 22 Joining the Multicast Tree AODV Group leader E L C J G H D K A B N N wishes to join the group Multicast Activation MACT CMPE 257 Spring 2002 23 Joining the Multicast Tree AODV Multicast tree links Group leader E L C J G H D K A B N Group member N has joined the group Tree but not group member CMPE 257 Spring 2002 24 Sending Data on the Multicast Tree Data is delivered along the tree edges maintained by the Multicast AODV algorithm If a node which does not belong to the multicast group wishes to multicast a packet 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 CMPE 257 Spring 2002 25 Leaving a Multicast Tree AODV Multicast tree links Group leader E L C J J wishes to leave the group G H D K A B N CMPE 257 Spring 2002 26 Leaving a Multicast Tree AODV Since J is not a leaf node it must remain a tree member Group leader E L C J J has left the group G H D K A B N CMPE 257 Spring 2002 27 Leaving a Multicast Tree AODV Group leader E L C J G H D K A B MACT prune N N wishes to leave the multicast group CMPE 257 Spring 2002 28 Leaving a Multicast Tree AODV Group leader E L C J G H A MACT prune D K B Node N has removed itself from the multicast group N Now node K has become a leaf and K is not in the group So node K removes itself from the tree as well CMPE 257 Spring 2002 29 Leaving a Multicast Tree AODV Group leader E L C J G H D K A B N Nodes N and K are no more in the multicast tree CMPE 257 Spring 2002 30 Handling a Link …