From wbell@CS.Cornell.EDU Wed Oct 3 11:34:29 2001 Return-Path: Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f93FYTo05030 for ; Wed, 3 Oct 2001 11:34:29 -0400 (EDT) Received: from [192.168.1.103] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA26317 for ; Wed, 3 Oct 2001 11:34:26 -0400 (EDT) Subject: 615 PAPER #22 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.14.99+cvs.2001.09.29.08.08 (Preview Release) Date: 03 Oct 2001 11:34:14 -0400 Message-Id: <1002123277.1127.7.camel@brute> Mime-Version: 1.0 22) Multicast Operation of the Ad hoc On-Demand Distance Vector Routing Protocol This paper introduces extensions ot AODV to support multicast groups [many-to-many communication.] The key insight is that by integrating multicast routing into a unicast routing protocol, you gain information over implementing them seperately and reduce network utilization for control messages by combining them into single opreration. Multicast operation works by using all regular AODV routing nodes as routing nodes for multicast operation, and adding various multicast group information to their routing state. Specifically, in the same vein as AODV, when a member wishes to join a multicast group, he sends a RREQ to the multicast group, which sets up a reverse path from a group node to himself, and enables that path as being a part of the multicast tree. Once routes are established, when a sender [who does not need to be part of the multicast group] wishes to send, they send to the leader of the group. From there, the node is relayed to all next neighbor nodes to the recipient node and forwarded to the multicast routers for this group in the network. Note that this forwarding can redundently forward packets to the same routers multiple times, but that they are dropped if identical packets are seen in the small window of time. Group leaders are responsible for keeping track of the current sequence number and broadcasting it throughout the tree periodically via group_hello messages. It wasn't clear what the overhead for this was over unicast routing using AODV, but it seemed small, which is a useful angle to look at things from. Given that most traffic on an Ad-Hoc network is unicast, one wants a multicast protocol that is always available but yet doesn't use much resources when multicast groups were not in use. I thought the discussion of the results was good, although I wasn't convinced as to the accuracy of the simulation-- they tended to use alot of random distributions for communication models, and I have a feeling that that tended to make their results look better than they should have. From viran@csl.cornell.edu Wed Oct 3 21:09:58 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f9419vo14629 for ; Wed, 3 Oct 2001 21:09:57 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f9419qF26133 for ; Wed, 3 Oct 2001 21:09:52 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Wed, 3 Oct 2001 21:09:52 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 22 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper describes how to extend AODV to provide multicast routing using a tree structure to connect nodes. The route discovery is similar to the unicast protocol -- a node joins a multicast group by broadcasting a RREQ and waiting for the corresponding RREP from a node in the group with a sequence equal or greater than that in the RREQ. Once the requesting node starts receiving RREPs and selects the path with the freshest sequence number and smallest number of hops, it sends a MACT message to the first hop on the path to activate the route. (I believe this extra MACT message is to prevent loops from forming because of multiple possible routes) This paper was interesting in that AODV now supports both unicast and multicast modes using the same basic protocol. The simulations were again a little disappointing, relying on the goodput ratio to evaluate the protocol. The control overhead graphs were rather useless, because they simply gave the number of messages being transmitted for control, with no mention of the actual data messages sent. It's interesting however to note that the number of Group hello messages was quite large, which may turn out to be a bottleneck in maintaining multicast groups. Also, the broadcast flooding to discover multicast groups is an undesirable feature of this algorithm, although they suggest the concept of core nodes in future work to alleviate this problem. From avneesh@csl.cornell.edu Wed Oct 3 23:15:27 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f943FRo28204 for ; Wed, 3 Oct 2001 23:15:27 -0400 (EDT) Subject: 615 Paper 22 Date: Wed, 3 Oct 2001 23:15:38 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Message-ID: <97C142C1212ED545B0023A177F5349C4053ACB@capricorn.ds.csl.cornell.edu> Content-Class: urn:content-classes:message X-MS-Has-Attach: X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 22 Thread-Index: AcFMgtcbUDFTbWa9SrukoLrfMmIKjw== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f943FRo28204 Multicast operation of the Adhoc On-Demand Distance Vector Routing Protocol Summary/Critique: This paper discusses the extensions made to the AODV protocol to support multicast operation. Multicast operation is beneficial in reducing control traffic, since a minimum number of messages may be needed to disseminate information to all members within a multicast group. The basic properties of AODV are preserved in the sense that a node still needs to send a RREQ to join a multicast group, and the subsequent RREPs set up a reverse path from a node which is part of the multicast group, to the node. Sequence numbers are used to ensure the loop free properties and the path with newest sequence number is preferred for routing information. The RREP also now includes a field called Mgroup_Hop, which is the distance from the source node to a member in the multicast group In the implementation, two more tables need to be added, these are a Multicast Route table and a Request table, the latter being an optimization since the entries in this table represent the group leaders. By checking who a group leader is, a node can just unicast a RREQ instead of utilizing a broadcast.Local connectivity management is done in the same way as before for the unicast part, i.e. by using 'Hello Messages'. However, for the multicast implementation, a 'Group Hello' is used, which is propagated across the entire network. The MUlticast algorithm is extended to include a new message: MACT, which is used in the initial multicast route activation. The MACT is actually unicast to a selected next best hop that a node come to know of, after its rte_discovery procedure. The main idea of having this MACT message is so that there aren't multiple paths to any tree node. I think that the most interesting part of the multicast implementation was how link breakages and subsequent network partitions are managed. Network partitions, one detected cause nodes to separate into multicast groups with their own leaders, if two multicast groups are in the vicinity of one another, they merge with only one leader (reconnection). Care is taken to prevent loop formation. The simulations that have been shown, give a fair idea of the performance of the protocol, with its multicast implementation. It is important to note the decrease in goodput ratio when due to increased likelihood of collisions, since multiple nodes must receive the data packet contrary to what happens in the unicast case. An interesting variation in group hello messages for the larger network between a particular speed range was also noticed. The main overhead is the reformation of the multicast trees when node mobility is high. From daehyun@csl.cornell.edu Thu Oct 4 10:02:18 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94E2Ho05414 for ; Thu, 4 Oct 2001 10:02:17 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id KAA47730 for egs@cs.cornell.edu; Thu, 4 Oct 2001 10:02:12 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200110041402.KAA47730@wilkes.csl.cornell.edu> Subject: 615 PAPER 22 To: egs@CS.Cornell.EDU Date: Thu, 4 Oct 2001 10:02:12 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper extends AODV to support multicast as well as unicast. Basically, this algorithm uses the same mechanism for unicast as conventional AODV. But, it adds several features for multicast. This algorithm maintains the additional tables for multicast; 1. Multicast Route Table: This table contains informations for multicast routing. The entries are similar to those of unicast route table except that next hops can be multiple. 2. Request Table: This table is used only for optimization. It maintains RREQ information which might be used to avoid broadcast later. This algorithm uses a new messages called Multicast Activation (MACT). This message is used in two ways - Selecting and Pruning. 1. Selecting: When a node wants to join a multicast group, it broadcasts RREQ messages and receives RREP messages. If it gets multiple RREQ messages it selects a route with greatest sequence number and shortest path, then sends a MACT message. 2. Pruning: When a node decides to terminate its membership in the multicast group and it is a leaf node of the multicast tree, it can prune itself by sending MACT message with P_flag set prune. In my opinion, one strong point of this paper they integrated unicast, multicast and broadcast into one routing protocol. As they said, this will have a synergy effect. Because network information can be shared, the protocol overhead will be reduced, both in the communication and computation aspect; Control messages can be saved and table management can be simplified. From c.tavoularis@utoronto.ca Thu Oct 4 10:32:04 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94EW3o09105 for ; Thu, 4 Oct 2001 10:32:04 -0400 (EDT) Received: from webmail1.ns.utoronto.ca ([128.100.132.24] EHLO webmail1.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 40629]) by bureau6.utcc.utoronto.ca with ESMTP id <238405-25958>; Thu, 4 Oct 2001 10:31:28 -0400 Received: by webmail1.ns.utoronto.ca id <126208-22900>; Thu, 4 Oct 2001 10:31:18 -0400 To: COM S 615 Subject: 615 PAPER 22 Message-ID: <1002205874.3bbc72b2ddd9f@webmail1.ns.utoronto.ca> Date: Thu, 04 Oct 2001 10:31:14 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper presents a novel extension to the AODV protocol to support unicast, multicast and broadcast routing. To accomplish this, AODV enables on-demand construction of multicast routing trees with unique group identifications. The advantage of combining these functions is that unicast routing can benefit from multicast routing knowledge, and vice versa. AODV assumes symmetric communication links. As in original AODV, routes are created via the broadcast of route discoveries incurring request and reply messages. A reverse route is created with the propagation of RREQ, and the forward route is created when the destination unicasts a RREP back to the source. Routes are chose based on highest sequence number and least number of hops. Nodes maintain a route table with next hop information for each destination, and a multicast table for groups for which they operate as routers. Multicast records (and routes) only become official when a Multicast Activation (MACT) is received and the Enabled flag is set. A node will eventually delete a record if no MACT has been received; therefore MACT preserves single routes, without loops. A node will update these tables each time it receives RREQs and RREPs. For the purpose of optimization, nodes will also maintain request tables with multicast group information that it overhears. If it chooses to join a group, it may already have a path to the leader in its request table and can unicast a RREQ, with J-flag set, to join. Any up-to-date member of the multicast group can reply to a join request. If a requesting node doesn’t receive a reply after rreq-retries, it declares itself group leader. The group leader maintains the multicast sequence number and periodically broadcasts it through Group Hello messages to the entire network. The sequence number is increased with each Group Hello for freshness. Whenever a new group leader is elected, it broadcasts a special Group-Hello message with U-flag set. Additional multicast maintenance functions are included to handle node mobility. Pruning allows non-group member routing nodes to be removed from the path via MACT (P-flag set) transmission if they become a leaf in the multicast tree. Periodic hello messages maintain connectivity and determine link fractures. In the event of link failure, the downstream node attempts to rejoin the group path with a RREQ with J-flag set. A group-hop-count metric ensures that the reconstruction is not with further downstream nodes, which would create a useless loop. A TTL parameter attempts to keep recovery local, but a network-wide broadcast will be performed if necessary. If this is not successful, a partition has been detected. If the repairing node is a group member, it becomes a new group leader. Otherwise, it forwards the responsibility to its neighbor with a MACT with GL-flag set, and then prunes itself. Finally, if a partitioned group (multiple leaders) detects other members of its group through Group Hello Messages, the leader with the higher IP address repairs connection between the partitions and relinquishes leadership to the other leader. In simulation, it was assumed that there was no aid from the MAC layer to resolve packet collision. Multicast increases the risk of collision since multiple destinations are trying to be reached simultaneously. In this case, the AODV suffered from packet loss, but the goodput was acceptable even in mobility. AODV with multicast support has a desirable function and allows multicast groups to be created on the fly, such that the first member of the group declares itself leader. AODV supports multicast by non-group member nodes. I thought the authors should have simulated simultaneous operation of multicast and unicast, since this is a realistic situation. In the event of critical data transmission, if a multicast group becomes partitioned, should a node sending to this group be aware that it is only reaching part of the group? From eyh5@ee.cornell.edu Thu Oct 4 10:34:20 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94EYKo09224 for ; Thu, 4 Oct 2001 10:34:20 -0400 (EDT) Received: from hegel (hegel.ee.cornell.edu [128.84.236.63]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f94EZBR13031 for ; Thu, 4 Oct 2001 10:35:11 -0400 Date: Thu, 4 Oct 2001 10:34:17 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 22 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Multicast Operation of the Ad-hoc On-Demand Distance Vector Routing Protocol Elizabeth M. Royer and Charles E. Perkins This paper adds a new feature, multicast operation, to the Ad-hoc On-demand Distance Vector (AODV) routing protocol introduced in the previous paper by Royer and Perkins. A mobile node wishing to join a multicast tree either sends a unicast RREQ packet if it has knowledge of a mutlicast group leader or broadcasts the RREQ packet to its neighbors. A broadcast RREQ packet may be retransmitted a number of times until a certain threshold, defined as rreq_retries, has reached, in which case the mobile node shall remain stand-alone. This algorithm on multicast operation has a very good multicast tree maintenance scheme, in which link breakages and partitioned trees may be repaired and reconnected promptly. The flexibility of the tree expansion and contraction has given the ad hoc mobile network a large degree of scalability. It seems that the addition of the multicast operation has required a rather drastic increase in the control information to correctly execute the underlying logic. Also, the multicast operation requires a separate routing protocol that is substantially different and more complex than that of the unicast routing algorithm. Therefore, it is not so obvious whether the gains extracted from the multicast operation outweigh the added computational and logical complexity of the mobile nodes of the network. Finally, it is this writer's belief that multicast operation, if indeed implemented, should be used only as an optional feature in any ad-hoc wireless network. In most situations, in a small- to medium-scaled ad-hoc network, multicast operation may be replaced with general broadcast transmission to notify all nodes of the network. While multicast transmission may limit the target nodes, it may not be a practical scheme in a real-life scenario, and the gain of implementing such a feature may not justify the operational cost. From gupta@CS.Cornell.EDU Thu Oct 4 10:56:00 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94Eu0o12000 for ; Thu, 4 Oct 2001 10:56:00 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 22 Date: Thu, 4 Oct 2001 10:55:59 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D430202E3E8@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 22 Thread-Index: AcFM5KrKEJmgUrXPEdW1vgCgydyP2Q== From: "Indranil Gupta" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f94Eu0o12000 Multicast operation of the ad-hoc on-demand distance vector routing protocol, Royer and Perkins. Reviewer: Indranil Gupta The authors extend their AODV protocol to accomodate multicast routing trees - the new protocol is called MAODV. The protocol is on-demand, with new members propagating RREQ messages to discover the nearest multicast tree member, in a way very similar to the AODV's route discovery. Intermediate nodes from the new node to the existing tree, also join the multicast tree. The first node in the tree is the leader, and is responsible for periodically sending out group_hello messages, with incremented sequence numbers. Other nodes simply choose the nearest neighbor that has the shortest route to the destination - this avoids loops. The tree reactively repairs broken links and changing topology of the network. The multicast tree is pruned at intermediate nodes when a leaf node leaves the group. On a link breakage, the node downstream of the breakage is responsible for repairing its link to the multicast tree. The protocol also handles rejoining of two partitions of the same multicast group tree. Simulation results exdhibit several properties of the protocol, but there is no comparison to other alternagtives for multicast routing. Tree-based protocols are found to have scalability problems in Internet-based scenarios. SRM, RMTP, the 'best' reliable multicast protocols, often go into pahological states with multiple requests and repairs being sent per multicast - studies have shown that beyond 80-90 nodes, these protocols impose a linear overhead per message per member. It will not be surprising if MAODV, being a tree-based protocol, suffers from the same scalability problems. For example, as the size of the multicast group n increases, the frequency of a link breakage somewhere in the tree rises linearly with n ,and average cost to repair each of these breakages also rises linearly with n - this points to an O(n^2) overhead, which is bad for scalability (it is precisely this that kills the scalability of SRM and RMTP). Alternatives to scalability include 1) core-based protocols such as CAMP: these may be sufficient to scale up to several hundreds of nodes, or 2) gossip-based protocols, which prove to outperform SRM and RMTP in wired networks. From teifel@csl.cornell.edu Thu Oct 4 11:00:21 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94F0Lo12244 for ; Thu, 4 Oct 2001 11:00:21 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f94F0FH60694 for ; Thu, 4 Oct 2001 11:00:15 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 4 Oct 2001 11:00:15 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 22 Message-ID: <20011004105337.G14118-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII royer & perkins: This paper presents the multicast operation of AODV routing protocols. Like unicast AODV, multicast AODV builds routes (multicast trees) as needed to connect multicast group members. AODV routes are discovered on-demand and use a broadcast route discovery mechanism. The authors combine unicast and multicast AODV into the same protocol. In addition to the normal route table, there is a multicast route table. A Request table is also needed to keep track of the multicast group IP address, and the requesting node IP address. Route discovery in AODV occurs on-demand and only occurs after a route request/route reply discovery cycle. In addition to the unicast messages, multicast needs an additional message type called Multicast Activiation. Once again graphs of simulations, have no distribution bars. Not overly impressed with a 50 node, fixed size LxL simulation. Has anyone done any simulation work that investigates the LxL area issue (won't say any more about this, because I just realized it may be a potential research area). Figure 3, seems to be saying that for a fixed room area unicast is better than multicast in terms of goodput ratios--is this really supposed to be true? From ranveer@CS.Cornell.EDU Thu Oct 4 11:32:30 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94FWUo16752 for ; Thu, 4 Oct 2001 11:32:30 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 22 Date: Thu, 4 Oct 2001 11:32:30 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D430203EDD1@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 22 Thread-Index: AcFM6dYHx6m81bdiEdW5awCQJ59Etw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f94FWUo16752 Multicast Operation of the Ad hoc On-Demand Distance Vector Routing Protocol This paper describes a tree-based on demand multicast routing protocol, that depends on AODV to provide the unicast functionalities. The core of the tree is the Group Leader, who periodically broadcasts a group hello message to propagate the information about the group. Joins and Repairs follow a RREQ, RREP cycle, with the join having an extra MACT to graft edges into the tree. MAODV is a simple protocol, that easily extends AODV to facilitate the multicast capability. However, there are a few problems: a) it is too dependent on AODV to be used with other unicast protocols. This is a deployment problem. b) Scalability: could potentially be bad because of tree maintenance. c) Group hellos: Are broadcast, so should not be used to update the distance from the greoup leader, since this might not be the optimal d) stability: Is unstable, due to the tree structure. e) Simulaton: What is goodput in multicast??? From ramasv@CS.Cornell.EDU Thu Oct 4 12:14:29 2001 Return-Path: Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94GESo21932 for ; Thu, 4 Oct 2001 12:14:28 -0400 (EDT) X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: cs615 PAPER 22 Date: Thu, 4 Oct 2001 12:14:28 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F275@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 22 Thread-Index: AcFM76R9SX3ma7aLR2S+o77zpqKgsA== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f94GESo21932 Multicast Operation of the Ad Hoc On Demand Distance Vector Routing Protocol This paper presents an extension of AODV to include multicast operation. MAODV builds and maintains a multicast tree as an under-lying structure for disseminating packets to the members of a multicast group. The MAODV protocol works more or less on the same line as the corresponding unicast routing protocol, sharing route table entries with each other. The multicast tree consists of both the group members and additional nodes that perform only relaying operation. MAODV operations consists of joining, repair and pruning. Join operation either by a group member or a source involves a route discovery broadcast to the multicast tree (any group member in the multicast tree). After receiving route replies an extra message called MACT is sent to activate the selected route. Link breakages are repaired by the downstream node in a multicast tree. Downstream nodes are marked based on the distance along the tree to a selected group member called group leader. Link breakage repair also involves a local broadcast of route discovery. Pruning operation is done when members leave a group or non-member nodes in the tree are made unnecessary. The group leader is expected to send periodic broadcasts throughout the network decalring its exixtance. This mechanism is requied for merging partitioned trees and to select downstream nodes for tree repair. This feature reduces the scalability of the protocol. Further if the network is reasonably big, several link breakages might occur concurrently making the multicast tree broken at most of the times. As such the reliability of multicast suffers extremely lot. Further the operations involving partition mergers and link breakages could create loops in the multicast tree making the protocol very unstable. The paper does not provide adequate simulations to measure the performance of the protocol. Goodput is not a good measure for performance of multicast protocols. Two good things about the paper include, combining unicst and multicast operations (sharing tables), not requiring membership information to be known at all places (except the group leader). A mobile ad hoc setting I believe needs a mesh based multicast structure that can take several simultaneous link breakages. From andre@CS.Cornell.EDU Thu Oct 4 12:46:39 2001 Return-Path: Received: from sundown.cs.cornell.edu (sundown.cs.cornell.edu [128.84.96.20]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94Gkco25651; Thu, 4 Oct 2001 12:46:38 -0400 (EDT) Received: from khaffy (mail@cs-annex-1-09.cs.cornell.edu [128.84.96.39]) by sundown.cs.cornell.edu (8.11.3/8.11.3/R-3.6) with ESMTP id f94Gkai15036; Thu, 4 Oct 2001 12:46:37 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.31 #1 (Debian)) id 15p63E-0000FK-00; Thu, 04 Oct 2001 12:48:24 +0200 Date: Thu, 4 Oct 2001 12:48:23 +0200 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Subject: 615 PAPER 22 Message-ID: <20011004124823.B692@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= Multicast in AODV AODV is the well know on demand routing, the source node adds a sequence number to its request to date it, and intermediate nodes are allowd to learn route and answer route req. if they have fresher information than what the source asks. (the seq. number prevents stale routes and loops). AODV related questions: What to do when the source / intermediary nodes have the choice between even fresher routes or shorter ones (the fresher being longer). I assume AODV is conservative, and takes the fresher. Is there always a severe risk of broken route / loop in not doing so? Technical detail, when a node forward back an anwser to a RREQ, it should also use its best available return path to sender, not the one from the first query it received, in order to find sorter routes. The multicast protocol by itself is nice, the incoming node is connected with the link the closet to the tree. This does not necessarly leads to the minimum spanning tree, but could be close to in most of the cases. (The node asks for the multicast IP it wants to reach, and the nodes on the multicast tree or knowing how to reach the tree anwser its request.) The route aquisisions are shared between uni and multicast. Questions: why is there a need for a proactive recovery of the multicast tree? They can partition even when they shouldn't, since when a linl breaks, they only look for short routes to the tree, when they could need to o on the other side of the failure (imagine two subnets connected by 2 gateways, and the one you use breaks). I have the feeling that the receonnect after partitionning only by chance. But do we care? Furthermore, a node who thinks it can reconnect two partitions takes the leadership. It is easy to fight against malicious nodes wanting to take the leadership by forcing the leader of the reconnecting net to take the overall leadership (would need more malicous node to gain power). There could be conflicts with concurrent updates. -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From samar@ece.cornell.edu Thu Oct 4 14:22:09 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94IM9o07773 for ; Thu, 4 Oct 2001 14:22:09 -0400 (EDT) Received: from plato (plato.ece.cornell.edu [128.84.239.28]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f94IN0R19494 for ; Thu, 4 Oct 2001 14:23:00 -0400 Date: Thu, 4 Oct 2001 14:24:45 -0400 (EDT) From: Prince Samar X-X-Sender: To: Emin Gun Sirer Subject: 615 PAPER 22 In-Reply-To: <200110041810.f94IAG602148@hoho.cs.cornell.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII 22) Multicast Operation of the Ad-hoc On-Demand Distance Vector Routing Protocol This paper introduces the Multicast extension of AODV to facilitate many-to-many communication in an ad hoc network. The control of the multicast tree is distributed which is necessary to avoid any single point of failure. Having a multicast extension to the unicast protocol AODV is advantageous in many ways as the protocol can accomplish unicast, multicast and broadcast communication with apparently less utilization of resources. The multicast algorithm, MAODV, utilizes RREQ/RREP messages in a way similar to the original algorithm. A multicast group leader, which is the first member of the group, maintains the multicast group sequence number and desseminates this message to the group by periodic group Hello messages. A node sends a RREQ message when it wishes to join a multicast group. This RREQ may be unicast or broadcast depending on the information available at the node. A RREP to a join RREQ may only be initiated by a member of the multicast group whereas for a regular RREQ, any node with a fresh enough route to the multicast group may respond. As the source node may possibly receive more than one RREPs for the RREQ it initiated, it should select one of these to be added to the multicast tree. The source node selects the route with the greatest sequence number and the shortest hop count and unicasts a Multicast Activation (MACT) to the next hop in this selected route. The nodes receiving the MACT message activate the entry for the source node in the multicast route table. Nodes which no longer want to be a part of the multicast tree can prune themselves off (provided they are a leaf in the tree) by sending a MACT message to the upstream node with the prune flag on. The tree reactively repairs broken links due to ropology changes. The downstream node is responsible for this repair. The simulation results show some of the important characteristics of the protocol. However it would have been nice to see a comparison with some other multicast protocol. The mutlicast is based on tree and so raises some questions about the scalability of the scheme to larger networks. The algorithm may have some stability problems due to dependence on tree structure. Also, when is it really worth finding and maintaining a multicast tree as against having unicast routing, given the high costs associated with multicasting? From haom@csl.cornell.edu Thu Oct 4 14:48:15 2001 Return-Path: Received: from mauchly.csl.cornell.edu (mauchly.csl.cornell.edu [132.236.71.68]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f94ImFo10901 for ; Thu, 4 Oct 2001 14:48:15 -0400 (EDT) Received: from localhost (haom@localhost) by mauchly.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id OAA83742 for ; Thu, 4 Oct 2001 14:48:10 -0400 (EDT) (envelope-from haom@mauchly.csl.cornell.edu) X-Authentication-Warning: mauchly.csl.cornell.edu: haom owned process doing -bs Date: Thu, 4 Oct 2001 14:48:09 -0400 (EDT) From: Ming Hao To: Emin Gun Sirer Subject: 615 PAPER 22 In-Reply-To: <200110041810.f94IAG602148@hoho.cs.cornell.edu> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Multicast Operation of the Ad_hoc On_Demand Distance Vector Routing Protocol by Elizabeth M. Royer ands Charles E. Perkins the motive of supporting multi-cast is that it is desirable feature though it is not necessary. though there are some algorithms supporting this feature, but they either depends on underlying routing algorithm or have central point failure. this paper proposes AODV which integrate unicast and mulit-cast together without single point of failure. the biggest advantage of this integration approach is that it can reduce the control overhead. the algorithm work in the following way: it maintains three tables on each node. two routing table for unitcast and multicast each, and a request table for optimization. for each multicast group, there is group leader. and a multicasting tree is rooted on the leader. when multicasting to the group, messages are sent to leader first and then down to all the other ,members. the route is discovered in the same way as unicast, using req and rep loop. only tree member can reply join request. for pure routing request, any node has a fresh enough route can respond. in order to find shortest one, a new message type mact is added. it is used to activate selected best toute to the group. group hello messages are used to update each member's route. it is also used to merge partitioned group. because of link failure and leaving of group members, route prunning is supported by the algorithm. when partition happens, a new group leader is selected. i have several questions/conmemnts to the algorithm. 1. hello message. is it necessary? sending hello message is based on assumption that the rout will be used again if it is used once. otherwise, it is useless to send hello message to adapt to the changing topology. So it may be better to just assume that the node does not move. 2. if the multicast group maintains only a tree structure, it implies that the message to the group must be sent to the leader first, then to the other members. is it more desirable for nodes maintain both successor and predecessor to accelerate the multicast? i think the paper does this. i am not sure. 3. is it necessary to have a group leader? it is obvious that sending to the leader insdead sending to the nearest group member is not a good idea when multicasting. the only reason needing a leader is to avoid multiple merging. but it is totally ok to have loop existing among group members. what needs to avoid is the loop among the pure tree touters which are not group members. 4. mact can be saved by keeping multiple routes. In general, the simulation results are very primitive. basically, it justs explored the goodput and message numbers in some scenenarios. there is no comparison with other multicast algorithms. it did not simulate the benefits gained by integrating unicast and multicast together though it mentioned the advantages of integration. -ming Ming Hao PH.D Candidate, EE mh97@cornell.edu Cornell University Office: (607) 255-0817 Ithaca, NY 14853 http://www.ee.cornell.edu/~haom/