1	Course Overview Introduction and History Data in Wireless Cellular Systems Data in Wireless Local Area Networks Internet Protocols Routing and Ad-Hoc Networks some slides in this section are from the Tutorial on Mobile Ad Hoc Networks: Routing, MAC and Transport Issues, prepared by Nitin Vaidya, see http://www.cs.tamu.edu/faculty/vaidya/presentations.html TCP over Wireless Link Services and Service Discovery System Support for Mobile Applications
2	Routing
3	Routing Problem: Find the lowest cost path between any two nodes Factors: Static: topology Dynamic: load
4	Distance Vector Each node maintains a set of triples: (Destination, Cost, NextHop) Each node sends updates to (and receives updates from) its directly connected neightbors periodically (on the order of several seconds) whenever its table changes (called triggered update) Each update is a list of pairs: (Destination, Cost) Update local table if receive a “better” route smaller cost came from next-hop Refresh existing routes; delete if they time out
5	Example Routing table at node B
6	Routing Example Example 1 F detects that link to G has failed F sets distance to G to infinity and sends update to A A sets distance to G to infinity since it uses F to reach G A receives periodic update from C with 2-hop path to G A sets distance to G to 3 and sends update to F F decides it can reach G in 4 hops via A
7	Routing Loops Example 2 Link from A to E fails A advertises distance of infinity to E B and C advertise a distance of 2 to E B decides it can reach E in 3 hops; advertises this to A A decides it can reach E in 4 hops; advertises this to C C decides that it can reach E in 5 hops...... Heuristics to break routing loops set infinity to 16 split horizon split horizon with poison reverse
8	Link State Strategy: Send to all nodes (not just neighbors) information about directly connected links (not entire routing table). Link State Packet (LSP) id of the node that created the LSP cost of link to each directly connected neighbor sequence number (SEQNO) time-to-live (TTL) for this packet Reliable Flooding store most recent LSP from each node forward LSP to all nodes but one that sent it generate new LSP periodically; increment SEQNO start SEQNO at 0 when reboot decrement TTL of each stored LSP; discard when TTL=0
9	Route Calculation Dijkstra's shortest path algorithm N denotes set of nodes in the graph l(i,j) denotes non-negative cost (weight) for edge (i,j) s /in N denotes this node M denotes the set of nodes incorporated so far C(n) denotes cost of the path from s to node n M = {s} for each n in N - {s} C(n) = l(s,n) while (N ° M) M = M union {w} such that C(w) is the minimum for all w in (N-M) for each n in (N-M) C(n) = MIN (C(n), C(w)+l(w,n))
10	Routing Example
11	Route Propagation Idea: Impose a second hierarchy on the network that limits what routers talk to each other. (The first hierarchy is the address hierarchy that governs how packets are forwarded.) Autonomous System (AS) corresponds to an administrative domain examples: University, company, backbone network assign each AS a 16-bit number Two-level route propagation hierarchy interior gateway protocol (each AS selects its own) exterior gateway protocol (Internet-wide standard)
12	Popular Interior Gateway Protocols RIP: Route Information Protocol developed for XNS distributed with Unix distance-vector algorithm based on hop-count OSPF: Open Shortest Path First recent Internet standard uses link-state algorithm supports load balancing supports authentication
13	EGP: Exterior Gateway Protocol Overview designed for tree-structured Internet concerned with reachability, not optimal routes Protocol messages neighbor acquisition: one router requests that another be its peer; peers exchange reachability information neighbor reachability: one router periodically tests to see if the other router is still reachable; exchange HELLO/ACK messages; uses a k-out-of-n rule routing updates: peers periodically exchange their routing tables (distance-vector)
14	BGP-4: Border Gateway Protocol Assumes the Internet is an arbitrarily interconnected set of AS's. Define local traffic as traffic that originates at or terminates on nodes within an AS, and transit traffic as traffic that passes through an AS, we can classify AS's into three types: Stub AS: an AS that has only a single connection to one other AS; such an AS will only carry local traffic. Multihomed AS: an AS that has connections to more than one other AS, but refuses to carry transit traffic. Transit AS: an AS that has connections to more than one other AS, and is designed to carry both transit and local traffic.
15	BGP-4: Border Gateway Protocol Each AS has: One or more border routers One BGP speaker that advertises: local networks other reachable networks (transit AS only) gives path information
16	Mobile Ad Hoc Networks Formed by wireless hosts which may be mobile Without (necessarily) using a pre-existing infrastructure Routes between nodes may potentially contain multiple hops
17	Mobile Ad Hoc Networks May need to traverse multiple links to reach a destination
18	Mobile Ad Hoc Networks (MANET) Mobility causes route changes
19	Why Ad Hoc Networks ? Ease of deployment Speed of deployment Decreased dependence on infrastructure
20	Many Applications Personal area networking cell phone, laptop, ear phone, wrist watch Military environments soldiers, tanks, planes Civilian environments taxi cab network meeting rooms sports stadiums boats, small aircraft Emergency operations search-and-rescue policing and fire fighting
21	Many Variations Fully Symmetric Environment all nodes have identical capabilities and responsibilities Asymmetric Capabilities transmission ranges and radios may differ battery life at different nodes may differ processing capacity may be different at different nodes speed of movement Asymmetric Responsibilities only some nodes may route packets some nodes may act as leaders of nearby nodes (e.g., cluster head)
22	Many Variations Traffic characteristics may differ in different ad hoc networks bit rate timeliness constraints reliability requirements unicast / multicast / geocast host-based addressing / content-based addressing / capability-based addressing May co-exist (and co-operate) with an infrastructure-based network
23	Many Variations Mobility patterns may be different people sitting at an airport lounge New York taxi cabs kids playing military movements personal area network Mobility characteristics speed predictability direction of movement pattern of movement uniformity (or lack thereof) of mobility characteristics among different nodes
24	Challenges Limited wireless transmission range Broadcast nature of the wireless medium Hidden terminal problem (see next slide) Packet losses due to transmission errors Mobility-induced route changes Mobility-induced packet losses Battery constraints Potentially frequent network partitions Ease of snooping on wireless transmissions (security hazard)
25	Hidden Terminal Problem
26	Research on Mobile Ad Hoc Networks Variations in capabilities & responsibilities X Variations in traffic characteristics, mobility models, etc. X Performance criteria (e.g., optimize throughput, reduce energy consumption) + Increased research funding = Significant research activity
27	The Holy Grail A one-size-fits-all solution Perhaps using an adaptive/hybrid approach that can adapt to situation at hand Difficult problem Many solutions proposed trying to address a sub-space of the problem domain
28	Assumption Unless stated otherwise, fully symmetric environment is assumed implicitly all nodes have identical capabilities and responsibilities
29	Flooding for Data Delivery Sender S broadcasts data packet P to all its neighbors Each node receiving P forwards P to its neighbors Sequence numbers used to avoid the possibility of forwarding the same packet more than once Packet P reaches destination D provided that D is reachable from sender S Node D does not forward the packet
30	Flooding for Data Delivery
31	Flooding for Data Delivery
32	Flooding for Data Delivery
33	Flooding for Data Delivery
34	Flooding for Data Delivery
35	Flooding for Data Delivery
36	Flooding for Data Delivery
37	Flooding for Data Delivery
38	Flooding for Data Delivery: Advantages Simplicity May be more efficient than other protocols when rate of information transmission is low enough that the overhead of explicit route discovery/maintenance incurred by other protocols is relatively higher this scenario may occur, for instance, when nodes transmit small data packets relatively infrequently, and many topology changes occur between consecutive packet transmissions Potentially higher reliability of data delivery Because packets may be delivered to the destination on multiple paths
39	Flooding for Data Delivery: Disadvantages Potentially, very high overhead Data packets may be delivered to too many nodes who do not need to receive them Potentially lower reliability of data delivery Flooding uses broadcasting -- hard to implement reliable broadcast delivery without significantly increasing overhead Broadcasting in IEEE 802.11 MAC is unreliable In our example, nodes J and K may transmit to node D simultaneously, resulting in loss of the packet in this case, destination would not receive the packet at all
40	Flooding of Control Packets Many protocols perform (potentially limited) flooding of control packets, instead of data packets The control packets are used to discover routes Discovered routes are subsequently used to send data packet(s) Overhead of control packet flooding is amortized over data packets transmitted between consecutive control packet floods
41	Ad-Hoc Networking: MANET Mobile Ad-hoc Networks (manet) at IETF: http://www.ietf.org/html.charters/manet-charter.html A "mobile ad hoc network" (MANET) is an autonomous system of mobile routers (and associated hosts) connected by wireless links routers are free to move randomly and organize themselves arbitrarily; thus, the network's wireless topology may change rapidly and unpredictably The primary focus of the working group is to develop and evolve MANET routing specification(s) and introduce them to the Internet Standards track. The goal is to support networks scaling up to hundreds of routers.
42	Ad-Hoc Networking: DSDV DSDV: Destination-Sequenced Distance Vector protocol basic idea: destination provides freshness indication, not intermediate nodes each mobile host is a router periodic broadcasts with sequence numbers significant new information triggers broadcast updates link breakages (metric ¥) are significant two criteria for route selection: sequence number guarantee maximal freshness (top priority) metric comparison for lowest cost protocol supports incremental and full updates some routes in forwarding table might not be advertised
43	Destination-Sequenced Distance-Vector (DSDV) Each node maintains a routing table which stores next hop towards each destination a cost metric for the path to each destination a destination sequence number that is created by the destination itself Sequence numbers used to avoid formation of loops Each node periodically forwards the routing table to its neighbors Each node increments and appends its sequence number when sending its local routing table This sequence number will be attached to route entries created for this node
44	Destination-Sequenced Distance-Vector (DSDV) Assume that node X receives routing information from Y about a route to node Z Let S(X) and S(Y) denote the destination sequence number for node Z as stored at node X, and as sent by node Y with its routing table to node X, respectively
45	Destination-Sequenced Distance-Vector (DSDV) Node X takes the following steps: If S(X) > S(Y), then X ignores the routing information received from Y If S(X) = S(Y), and cost of going through Y is smaller than the route known to X, then X sets Y as the next hop to Z If S(X) < S(Y), then X sets Y as the next hop to Z, and S(X) is updated to equal S(Y)
46	Ad-Hoc Networking: DSDV Example
47	Ad-Hoc Networking: DSDV Example
48	Ad-Hoc Networking: DSDV Example
49	DSDV Evaluation DSDV good for small ad-hoc networks Brute-force approach to larger networks requires periodic advertisements and global dissemination of connectivity information each node has to keep complete list of routes
50	AODV: Improvement on DSDV AODV intends to improve on DSDV shortcomings basic idea: create routes only “on demand” to eliminate overhead of periodic broadcasts problem: if purely “on demand”, could lead to long latencies before first packet gets transmitted AODV assumes symmetric links between two nodes discover new nodes in neighborhood using local hello messages primary objectives of AODV: broadcast discovery packets only when necessary distinguish between local connectivity changes and general topological maintenance disseminate information about local changes only to those neighboring mobiles that are likely to need information
51	AODV Route Requests (RREQ) are forwarded via flooding When a node re-broadcasts a Route Request, it sets up a reverse path pointing towards the source AODV assumes symmetric (bi-directional) links When the intended destination receives a Route Request, it replies by sending a Route Reply Route Reply travels along the reverse path set-up when Route Request is forwarded
52	Route Requests in AODV
53	Route Requests in AODV
54	Route Requests in AODV
55	Reverse Path Setup in AODV
56	Reverse Path Setup in AODV
57	Reverse Path Setup in AODV
58	Route Reply in AODV
59	Route Reply in AODV An intermediate node (not the destination) may also send a Route Reply (RREP) provided that it knows a more recent path than the one previously known to sender S To determine whether the path known to an intermediate node is more recent, destination sequence numbers are used The likelihood that an intermediate node will send a Route Reply when using AODV not very high A new Route Request by node S for a destination is assigned a higher destination sequence number. An intermediate node which knows a route, but with a smaller sequence number, cannot send Route Reply
60	Forward Path Setup in AODV
61	Data Delivery in AODV
62	Timeouts A routing table entry maintaining a reverse path is purged after a timeout interval timeout should be long enough to allow RREP to come back A routing table entry maintaining a forward path is purged if not used for a active_route_timeout interval if no is data being sent using a particular routing table entry, that entry will be deleted from the routing table (even if the route may actually still be valid)
63	Link Failure Reporting A neighbor of node X is considered active for a routing table entry if the neighbor sent a packet within active_route_timeout interval which was forwarded using that entry When the next hop link in a routing table entry breaks, all active neighbors are informed Link failures are propagated by means of Route Error messages, which also update destination sequence numbers
64	Route Error When node X is unable to forward packet P (from node S to node D) on link (X,Y), it generates a RERR message Node X increments the destination sequence number for D cached at node X The incremented sequence number N is included in the RERR When node S receives the RERR, it initiates a new route discovery for D using destination sequence number at least as large as N When node D receives the route request with destination sequence number N, node D will set its sequence number to N, unless it is already larger than N
65	Link Failure Detection Hello messages: Neighboring nodes periodically exchange hello message Absence of hello message is used as an indication of link failure Alternatively, failure to receive several MAC-level acknowledgement may be used as an indication of link failure
66	Why Sequence Numbers in AODV To avoid using old/broken routes To determine which route is newer To prevent formation of loops Assume that A does not know about failure of link C-D because RERR sent by C is lost Now C performs a route discovery for D. Node A receives the RREQ (say, via path C-E-A) Node A will reply since A knows a route to D via node B Results in a loop (for instance, C-E-A-B-C )
67	Optimization: Expanding Ring Search Route Requests are initially sent with small Time-to-Live (TTL) field, to limit their propagation Common approach to limit flooding If no Route Reply is received, then larger TTL tried
68	Summary: AODV Routes not included in packet headers Nodes maintain routing tables containing entries only for routes that are in active use At most one next-hop per destination maintained at each node Other protocols may maintain several routes for a single destination Unused routes expire even if topology does not change
69	AODV Example
70	AODV Example Suppose MH1 moves away from MH2 towards MH7 and has active sessions with MH3 and MH6: MH2 notices that its link to MH1 is broken MH2 checks its routing table and finds that its link to MH1 was actively in use by MH3 and MH4 MH2 unicasts an ¥-metric route update, with an incremented destination sequence number, to MH3 and MH4. MH3 may subsequently issue a new route request for MH4 MH4 also notes that its route to MH1 was actively in use and forwards a ¥ -metric route update to MH6 the ¥-metric route update for MH1 may also be included in the next periodic limited broadcast issued by MH2 MH6 may subsequently issue a new route request for MH1 any subsequent route request for MH1 which is satisfied by a route reply through MH2 may cause MH2 to update its route table
71	AODV Performance Evaluation Nodes move randomly with geographic region speed chosen from uniform distribution between 0.4 and 0.8 meters/second once they arrive at random location, rest for period chosen from uniform distribution between 60 and 300 seconds 2 nodes can communicate directly (are neighbors) if they are less than 10 meters apart
72	AODV Performance Evaluation
73	AODV Performance Evaluation Voice: longer packets, resulting in more collisions and longer queue lengths at intermediate nodes, which in turn delays RREQ and RREP messages and increases route acquisition latency Bandwidth efficiency slightly higher, since number of “control” messages the same, but more data being send
74	DSR: Dynamic Source Routing Source Routing: sender of packet determines complete sequence of nodes along path and lists them in packet header use dynamic route discovery to determine path advantages: no periodic routing advertisement messages saves bandwidth when there is little change in network saves battery power (no need to send/receive messages) ad-hoc networks have many redundant links, which cause flooding of routing messages no assumption of link symmetry possible to react to changes faster than state-based or distance-vector based protocols better opportunities for route caching and maintenance of alternative routes, compared to AODV
75	Dynamic Source Routing (DSR) When node S wants to send a packet to node D, but does not know a route to D, node S initiates a route discovery Source node S floods Route Request (RREQ) Each node appends own identifier when forwarding RREQ
76	Route Discovery in DSR
77	Route Discovery in DSR
78	Route Discovery in DSR
79	Route Discovery in DSR
80	Route Discovery in DSR
81	Route Discovery in DSR
82	Route Discovery in DSR Destination D on receiving the first RREQ, sends a Route Reply (RREP) RREP is sent on a route obtained by reversing the route appended to received RREQ RREP includes the route from S to D on which RREQ was received by node D
83	Route Reply in DSR
84	Route Reply in DSR Route Reply can be sent by reversing the route in Route Request (RREQ) only if links are guaranteed to be bi-directional To ensure this, RREQ should be forwarded only if it received on a link that is known to be bi-directional If unidirectional (asymmetric) links are allowed, then RREP may need a route discovery for S from node D Unless node D already knows a route to node S If a route discovery is initiated by D for a route to S, then the Route Reply is piggybacked on the Route Request from D. If IEEE 802.11 MAC is used to send data, then links have to be bi-directional (since Ack is used)
85	Dynamic Source Routing (DSR) Node S on receiving RREP, caches the route included in the RREP When node S sends a data packet to D, the entire route is included in the packet header hence the name source routing Intermediate nodes use the source route included in a packet to determine to whom a packet should be forwarded
86	Data Delivery in DSR
87	When to Perform a Route Discovery When node S wants to send data to node D, but does not know a valid route node D
88	Route Error (RERR)
89	DSR Optimization: Route Caching Each node caches a new route it learns by any means When node S finds route [S,E,F,J,D] to node D, node S also learns route [S,E,F] to node F When node K receives Route Request [S,C,G] destined for node, node K learns route [K,G,C,S] to node S When node F forwards Route Reply RREP [S,E,F,J,D], node F learns route [F,J,D] to node D When node E forwards Data [S,E,F,J,D] it learns route [E,F,J,D] to node D A node may also learn a route when it overhears Data packets
90	DSR Optimizations Route cache intermediate nodes learn about routes by “snooping” on route request/reply messages and/or routing data intermediate nodes may learn routes by listening to route discovery through neighboring nodes
91	DSR Optimizations piggy-backing data onto route discovery to reduce latency if node that is not target replies to route request, special attention is needed to make sure that the data is forwarded to final destination reflecting shorter routes usually, as nodes move closer, they will also move out of range in existing route, so route maintenance will take care of this alternatively, run network interfaces in promiscuous mode, listen to who is in your neighborhood and see whether routes in cache can be shortened
92	DSR Optimizations handling network partitions if nodes cannot communicate, lots of failed route request messages, with corresponding overhead limit route requests using exponential backoff algorithm eavesdrop on route error packets (promiscuous mode) error packets detail hop that is down other nodes can update/invalidate routes that use this hop in their cache keep negative information (hops that are down) in cache for a brief period to make sure new routes do not use outdated hop
93	Use of Route Caching When node S learns that a route to node D is broken, it uses another route from its local cache, if such a route to D exists in its cache. Otherwise, node S initiates route discovery by sending a route request Node X on receiving a Route Request for some node D can send a Route Reply if node X knows a route to node D Use of route cache can speed up route discovery can reduce propagation of route requests
94	Use of Route Caching
95	Use of Route Caching: Speed up Route Discovery
96	Use of Route Caching: Reduce Propagation of Route Requests
97	Route Caching: Beware! Stale caches can adversely affect performance With passage of time and host mobility, cached routes may become invalid A sender host may try several stale routes (obtained from local cache, or replied from cache by other nodes), before finding a good route This is particularly bad for protocols such as TCP, where the sender will timeout, assume severe congestion, and drastically reduce the rate at which data is sent.
98	Dynamic Source Routing: Advantages Routes maintained only between nodes who need to communicate reduces overhead of route maintenance Route caching can further reduce route discovery overhead A single route discovery may yield many routes to the destination, due to intermediate nodes replying from local caches
99	Dynamic Source Routing: Disadvantages Packet header size grows with route length due to source routing Flood of route requests may potentially reach all nodes in the network Care must be taken to avoid collisions between route requests propagated by neighboring nodes insertion of random delays before forwarding RREQ Increased contention if too many route replies come back due to nodes replying using their local cache Route Reply Storm problem Reply storm may be eased by preventing a node from sending RREP if it hears another RREP with a shorter route
100	Dynamic Source Routing: Disadvantages An intermediate node may send Route Reply using a stale cached route, thus polluting other caches This problem can be eased if some mechanism to purge (potentially) invalid cached routes is incorporated.
101	DSR Performance
102	DSR Performance
103	Ad-Hoc Routing Schemes
104	Comparison On-Demand vs. Table-Driven
105	Comparison of Source-Initiated Protocols
106	Ad-Hoc Routing Algorithm Performance each paper/proposal tends to come with its own set of performance evaluations, based on some simulated environment similar to location management proposals, no common performance evaluation framework exists one study (November 1998): implement a number of proposals in NS and evaluate them, compare relative advantages and disadvantages catch: study done by authors of DSR, which ends up being found superior
107	Ad-Hoc Routing: Performance Comparison Movement Model: 1500m x 300m space user picks random location, moves there at a speed randomly distributed between 0 and 20 meters/sec stay at new location for pause time second, repeat Communication Model: 10, 20, or 30 CBR sources, sending 4 packets/sec packet size is fixed at 64 bytes all communication peer-to-peer, starts at times uniformly distributed between 0 and 180 seconds transmission range of 250 meters for each radio
108	Ad-Hoc Routing: Performance Comparison
109	Ad-Hoc Routing: Performance Comparison Performance Metrics: packet delivery ratio routing overhead path optimality Not considered: latency to establish route goodput route failures (i.e., routes break and connection times out before new route can be established)
110	Ad-Hoc Routing: Performance Comparison
111	Ad-Hoc Routing: Performance Comparison
112	Ad-Hoc Routing: Performance Comparison
113	Ad-Hoc Routing: Performance Comparison Conclusions of study: each protocol performs well in come cases and has drawbacks in others DSR performs predictably delivers virtually all data packets at low mobility rate and speed fails to converge as node mobility increases AODV performs nearly as well as DSR at all mobility rates and speeds accomplishes its goal of eliminating source routing overhead requires transmission of many routing overhead packets is more expensive than DSR of high rates of node mobility
114	Future Issues: Heterogeneous Interfaces
115	Future Issues: Hierarchical Networks
116	Future Issues: Integration with Internet
117	Future Issues: Integration with Mobile IP
118	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
119	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
120	AODV Multicasting 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
121	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
122	AODV Multicast Tree
123	Joining the Multicast Tree: AODV
124	Joining the Multicast Tree: AODV
125	Joining the Multicast Tree: AODV
126	Joining the Multicast Tree: AODV
127	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
128	Leaving a Multicast Tree: AODV
129	Leaving a Multicast Tree: AODV
130	Leaving a Multicast Tree: AODV
131	Leaving a Multicast Tree: AODV
132	Leaving a Multicast Tree: AODV
133	Handling a Link Failure: AODV Multicasting 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) Only nodes which 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
134	Handling Partitions: AODV When failure of link (X,Y) results in a partition, the downstream node, say X, initiates Route Request If a Route Reply 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
135	Merging Partitions: AODV 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 The leader with the larger identifier remains group leader
136	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
137	Merging Partitions: AODV 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 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
138	Merging Partitions: AODV
139	Merging Partitions: AODV
140	Merging Partitions: AODV
141	Merging Partitions: AODV
142	Summary: Multicast AODV Similar to unicast AODV Uses leaders to maintain group sequence numbers, and to help in tree maintenance
143	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 throughput the network Periodic transmissions are used to update the routes
144	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
145	On-Demand Multicast Routing Protocol (ODMRP) Assume that S is a sender node
146	On-Demand Multicast Routing Protocol (ODMRP)
147	On-Demand Multicast Routing Protocol (ODMRP)
148	On-Demand Multicast Routing Protocol (ODMRP)
149	On-Demand Multicast Routing Protocol (ODMRP)
150	On-Demand Multicast Routing Protocol (ODMRP)
151	On-Demand Multicast Routing Protocol (ODMRP)
152	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
153	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