From eyh5@ee.cornell.edu Mon Dec 3 13:31:23 2001 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 fB3IVMT18295 for ; Mon, 3 Dec 2001 13:31:22 -0500 (EST) Received: from photon.ece.cornell.edu (photon.ece.cornell.edu [128.84.81.138]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fB3IS4M21012 for ; Mon, 3 Dec 2001 13:28:04 -0500 Date: Mon, 3 Dec 2001 13:28:05 -0500 (EST) From: Edward Hua X-X-Sender: To: Subject: 615 Paper # 69 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Bayeux: AN Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination Shelly Q. Zhuang, Ben, Y. Zhao, Anthony D. Joseph, Randy H. Katz, John D. Kubiatowicz This paper proposes Bayeux, which is essentially Tapestry with multicast operations. Bayeux is used in distributing streaming multimedia applications from a single source (publisher) to a large receiver group. It has the capability to scale to thousands of nodes in the network, is fault-tolerant to link and node failures, and combines randomness for load balancing with locality for efficient use of network bandwidth. Bayeux uses the Tapestry mechanism as its location and routing substrate, and on top of it is the application-specific multicast operation. Because randomized node IDs naturally group themselves into sets sharing common suffixes, a multicast packet does not have to be duplicated when traversing the network until it encounters receiver nodes whose identifiers become divergent in the next nodeID digit. Also, the maximum number of overlay hops by Bayeux multicast delivery operation is bounded by the total number of digits in the underlying Tapestry's node IDs. The base architecture of Bayeux is straightforward. When a server node has a session to advertise, it creates a tuple, hashes it into a 160-bit identifier, and sends this identifier using the Tapestry operations to a root node for advertisement. The root node now will have a pointer to point where the session is located. When multiple clients request the session from the root node, they first know the same tuple a priori, use the same hashing function to get the identifier, and then request the session service from the root node using the Tapestry operation. The root node then performs a multicast membership operation to establish a receiver group for receiving the advertised session service. In maintaining the multicast membership tree, four control messages are exchanged between the root node and the client nodes. They are JOIN, TREE, LEAVE, and PRUNE. A node joins the multicast session by sending a JOIN message towards the root, which then replies with a TREE message. Notice here the JOIN and TREE can take on different paths. When a router receives the TREE message, it adds the new member node ID to the list of receiver node IDs that it's responsible for and updates its forwarding table. When a node decides to leave the multicast membership, it sends a LEAVE message to the root, which then returns the PRUNE message. Along the path, the routers delete leaving node's ID from their receiver node lists. Further enhancements to improve the scalability of Bayeux multicast operations are made. One is the tree partitioning, in which multiple root nodes, instead of a single root node, are used that may form disjoint membership trees of their own. The advantages of this arrangement are two-fold: 1) it eliminates the single point of failure problem associated with a single root node, and 2) a member node may choose a root node closest to itself to reach the desired session, thus saving both delay and bandwidth consumption. Another improvement is called receiver identifier clustering. This is the scheme for smartly naming node IDs so that local member nodes to a root node may share the longest possible suffix, thus reducing session packet replication. From wbell@CS.Cornell.EDU Mon Dec 3 14:04:56 2001 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 fB3J4uT24493 for ; Mon, 3 Dec 2001 14:04:56 -0500 (EST) Received: from dhcp-190.rover.cornell.edu (dhcp-190.rover.cornell.edu [128.84.24.190]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA26226 for ; Mon, 3 Dec 2001 14:04:55 -0500 (EST) Subject: 615 PAPER #69 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.99.1+cvs.2001.11.07.16.47 (Preview Release) Date: 03 Dec 2001 14:04:34 -0500 Message-Id: <1007406297.914.35.camel@brute> Mime-Version: 1.0 69) Bayeux: An Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination Bayeux is a multicast architecture built on top of Tapestry which uses the connectivity information in Tapestry in order to do efficient multicast data dispersal. By using Tapestry's suffix based routing, they avoid unicasting packets to all subscribers from a single sender, and instead, duplicate packets only at every branch of the tapestry suffix tree. I found the protocol description to be incredibly terse, with little description of how it actually works. I do believe that such a facility could be built on top of Tapestry, but was unconvinced that this was a reasonable thing to do. No analysis of the overhead of such a mechanism was presented, but my intuition is that it is quite high, because although duplicating packets at suffix points makes sense when the nodes suffix has something to do with locality on the network, Tapestry makes no such guarantee, and while splitting on suffixes works well on the Tapestry space, this has no correlation to the amount of actual network hops. They state that it would be a useful optimization to allocate Tapestry suffixes to correspond to the actual network proximity, but that seems to defeat the purpose of the scalability of Tapestry, and makes me wonder why we've left the ip address space and gone to an overlay network. They present a decent number of ways to use alternate routing information in order to get better data dispersal, which I found useful, but there was little evaluation of the tradeoffs between bandwidth usage and overall gain. For all of these methods it seems to be critically important to understand the mapping between the Tapestry id space and the underlying ip address space, but this fact is completely ignored. This seems to be the fatal flaw of all this work-- one can build primitives on top of these infrastructures, but if they don't provide significantly better guarantees than ip alone, the cost does not justify the use, and Tapestry does not motivate that it's gain is significant enough to justify it's deployment across the global Internet. From avneesh@csl.cornell.edu Tue Dec 4 11:20:08 2001 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 fB4GK8628869 for ; Tue, 4 Dec 2001 11:20:08 -0500 (EST) content-class: urn:content-classes:message Subject: 615 Paper 69 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Tue, 4 Dec 2001 11:23:26 -0500 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <97C142C1212ED545B0023A177F5349C40A0A28@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 69 Thread-Index: AcF84ABKwkPXyjmgRz+NcjlhkfSk9w== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id fB4GK8628869 Bayeux This paper describes the implementation of Bayeux, an application level multicast system , which is built upon the Tapestry routing architecture, thus deriving its falt tolerance properties. A Bayeux multicast session consists of a session name and a UID. A 160 bit hash key of this tuple is formed, a a file is created with this identifier, which placed at the root of the multicast tree. Clients which need to join, should know the unique tuple. The group membership operations consist of JOIN,LEAVE,TREE and PRUNE. JOIN messages result in the root sending a TREE message to the client. NOdes within this route would add the client ID in their receiver ID list for subsequent packet forwarding. The authors evaluate the performance of the multicast implementation over simple unicast in terms of link stress. They also investigate issues of tree partitioning due to having just one multicast root. This problem can be easily alleviated by the Tapestry substrate since it provides an easy mechanism for creating multiple root nodes. Tapestry guarantees to find a root with high probablity. Other optmizations to reduce duplicate packet delivery is to carry out receiver identifier clustering in order to group nodes which might share the first m bits of a node ID. Simulations based on this show favorable results. An interesting evaluation is that of the First Reachable Link selection protocol in order to ensure high probability of succesful packet delivery on this multicast network. This method does not use duplicate packets, but instead involves pervious history of link quality to be taken into account when calculating the next best link. When a new link is chosen , the membership state is also propagated. I think that this work was quite interesting, not in view of introducing a novel idea, but actually showing the strenghts of the Tapestry routing protocol and its degree of extensibility for multicast routing. There is one thing that I could not understand and that was how the Tapestry IDs were related to IP address space. From ramasv@CS.Cornell.EDU Tue Dec 4 11:48:20 2001 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 fB4GmK604095 for ; Tue, 4 Dec 2001 11:48:20 -0500 (EST) Subject: cs615 PAPER 69 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Tue, 4 Dec 2001 11:48:20 -0500 content-class: urn:content-classes:message X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F29E@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 69 Thread-Index: AcF843riIpowh89MSBG6AU1pcntBrQ== 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 fB4GmK604095 Bayeux: An architecture for scalable and fault-tolerant wide are data dissemincation. Bayeux is a tree based multicast protocol desgined for streaming multimedia on top of tapestry routing protocol. Streaming multi-media applications have the property of having several consumers of information while a singe source. This fits neatly on top of the tapestry architecture since the source can be considered to be the root server for the media-files and the consumers, the different client of tapestry. As shown in the paper it is quite trivial to establish a logical tree of routing from source to multiple destinations based on the tapestry architecture. Such a tree would have a very short depth (10 for 160-bit node ids) and a constant fan-out (16). The quality of multi-media streams relies extremely upon a metric called jitter - that measures the inter-arrival time between succesive packets. Since tapestry architecture has a constant tree-rebuilding process in the background upon node and link failures, it would be extremely difficult to guarantee low jitter. Further tapestry assumes an underlying overlay network routing architecture (internet) that does not guarantee any bound for the jitter. These restrictions may prove tapestry an unsuitable solution for the proposed problem. Bayeux proposes to overcome this problem partly by routing duplicate packets through secondary neighbors in the routing tree. While the paper claims that such duplicate paths taken would soon converge (thus limiting the overhead) it is not clear why as contrary to what is stated in the paper the multicast tree is rooted at the source and not the destination. In addition to that the tapestry routing algorithm relies on timeouts when routing through secondary neighbors and hence might increase the jitter quite high. Further, bayeux proposes to make nodes proximal in the physical topology also to be proximal in the virtual topology. This might weaken the fault tolerance and robustness gurantees of tapestry. From c.tavoularis@utoronto.ca Tue Dec 4 12:04:34 2001 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 fB4H4X606754 for ; Tue, 4 Dec 2001 12:04:33 -0500 (EST) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 37244]) by bureau6.utcc.utoronto.ca with ESMTP id <238582-22507>; Tue, 4 Dec 2001 12:04:19 -0500 Received: by webmail3.ns.utoronto.ca id <414677-225>; Tue, 4 Dec 2001 12:04:13 -0500 To: COM S 615 Subject: 615 PAPER 69 Message-ID: <1007485453.3c0d020d0764c@webmail.utoronto.ca> Date: Tue, 04 Dec 2001 12:04:13 -0500 (EST) 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 Bayeux is an application-level multicast system intended for streaming multimedia from one or few source to large number of destinations. Bayeux employs Tapestry for routing and location. It builds a distribution tree for multicast while trying to minimize delay and bandwidth use, while handling link and node failures. The goal is to build an efficient network of unicast connections using Tapestry, and then create a data distribution tree rooted at the source and reaching all multicast members. Tapestry forwarding achieved index-by-index can be exploited for multicasting purposes by multiplexing data packets and diverging when an index has changed. Bayeux uses Tapestry’s data location service to publish multicast session with the hash of a unique tuple at the root node. The root node advertises the session, and clients that can identify the session can join by sending a JOIN message to the root. The root replies with a TREE message, such that routers in the forwarding path maintain a list of receiver node Ids. A node can send a LEAVE message to remove itself from the session, which triggers a PRUNE message from the root to notify forwarding routers of the change. Bayeux was evaluated according to relative delay penalty with respect to Tapestry, and physical link stress to measure load balancing. It was shown that overall link stress is lower in Bayeux than in unicast. This paper also provides scalability enhancements on top of Tapestry. Tapestry allows Bayeux to load-balance across multiple root nodes using tree partitioning. The root nodes containing the same object are organized into a tapestry network, and each advertises he object. Clients join to the closest root hence the load is distributed. Tapestry also enables clustering of receiver nodes by id, which further reduces link stress. Bayeux demonstrates an efficient use of the Tapestry infrastructure, and seems to demonstrate the potential to support wide-area multimedia dissemination. It would be useful to actually demonstrate the performance of Bayeux in a real-world scenario. From mh97@cornell.edu Tue Dec 4 13:17:58 2001 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 fB4IHw619531 for ; Tue, 4 Dec 2001 13:17:58 -0500 (EST) Received: from mars (syr-66-24-28-66.twcny.rr.com [66.24.28.66]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id NAA06428 for ; Tue, 4 Dec 2001 13:17:56 -0500 (EST) From: "hao ming" To: "'Emin Gun Sirer'" Subject: 615 PAPER 69 Date: Tue, 4 Dec 2001 13:17:26 -0500 Message-ID: <000501c17cef$ed6bfdb0$6801a8c0@mars> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2627 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Bayeux: An Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination Shelley Q. Zhuang, Ben Y. Zhao, Anthony D. Joseph, Randy H. Katz, John D. Kubiatowicz This paper presents a application of Tapestry for multicast. The key of efficient multicasting is to reduce the data Duplication. Because of the routing algorithms of Tapestry, the nodes with similar suffix can be group together and data duplication only happens when there is diverge of forwarding. Further, Bayuex gets the necessary properties like fault Tolerance, load balancing and scalability from the Tapestry. The algorithms adopted by Bayeux is follows: 1. each session s IDed by a tuple which is broadcast to the network. Each client send explicit Join message to root to join the tree and forwarding tree is set up when root sends Tree message back to the requesting client. 2. for scalability and elimination of single root node failure, the multiple roots of Tapestry is used and clients will join the tree rooted at the nearest root node. This is very good. 3. explicit clients clustering by assigning to the neighbors nodes with longest suffix. 4. fault tolerance. Tapestry provides two good properties for tolerance. One is backup route for each entry in the routing table. The second is the converging feature of naming system of Tapestry. Based on these two properties, the paper proposes five fault resilient delivery protocols. Basically, different ways choosing backup paths result in those different protocols, including proactive duplication which duplicate data simply to its first backup path; application specific information duplication which I like most. For streaming materials, data can be divided into several channel to transfer different quality data. Higher resolution data is losable; and other protocols considering delay, link traffic metrics. comments: 1. Tapestry provides really some nice features which is just what multicasting streaming multimedia application needs. They really select a very good application for Tapestry. 2. on the physical link stress, I do not think Bayeux is much better than the worst case IP unicast in F.4 because it looks most of links have same stress number like Bayeux. -ming From daehyun@csl.cornell.edu Tue Dec 4 13:45:24 2001 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 fB4IjO623961 for ; Tue, 4 Dec 2001 13:45:24 -0500 (EST) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id NAA76352 for egs@cs.cornell.edu; Tue, 4 Dec 2001 13:45:19 -0500 (EST) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200112041845.NAA76352@wilkes.csl.cornell.edu> Subject: 615 PAPER 69 To: egs@CS.Cornell.EDU Date: Tue, 4 Dec 2001 13:45:19 -0500 (EST) 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 presents Bayeux which is an efficient application-level multicast system that scales to arbitrarily large receiver groups while tolerating failures in routers and network links. Bayeux is base on Tapestry. Streaming multimedia applications are growing at an incredible rate and they require a large scale multicast mechanism. Using unicast mechanism for this purpose is completely impractical. Bayeux is an efficient, source-specific, explicit-join, application-level multicast system. It combines randomness for load balancing with locality for efficient use of network bandwidth. It is based on Tapestry which uses a prefix-based routing scheme and provides a simple protocol which organizes the multicast receivers into a distribution tree. Bayeux multicast session is identified by a tuple . It maps the tuple into a 160 bit identifier by SHA-1 and create a file with that identifier and place it on the root node. Then, it advertises the document by the Tapestry's data location services. Client that wants to join a session performs the same operations to generate the file name and query for it using Tapestry. Then the root node receives this message and allows it to perform the required membership operations. A member joins the session by sending a JOIN message to the root, which then replies with a TREE message. When a router receives a TREE message, it adds the new member ID to the list of receiver IDs and updates the forward table. For leaving the session, the similar operations are performed with LEAVE and PRUNE messages. From samar@ece.cornell.edu Tue Dec 4 13:55:40 2001 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 fB4Ite625771 for ; Tue, 4 Dec 2001 13:55:40 -0500 (EST) Received: from aquinas.ee.cornell.edu (aquinas.ee.cornell.edu [128.84.236.57]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fB4IqHM19155 for ; Tue, 4 Dec 2001 13:52:17 -0500 Date: Tue, 4 Dec 2001 13:54:02 -0500 (EST) From: Prince Samar X-Sender: samar@aquinas.ee.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 69 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Bayeux: An Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination. Bayeux is an application-level multicasting system built on top of the Tapestry location and routing scheme. The tree-based, source-specific, explicit-join multicast service is designed for dissemination of streaming multimedia on the internet. The design goals for Bayeux have been scalability, efficiency and fault-resilience. The Bayeux multicast session is identified by the tuple . For session advertisement, a 160 bit hash of this tuple is formed and a trivial file with this name is formed and kept at the multicast session's root node. Tapestry's location service can then be used to advertize this document. JOIN, LEAVE, TREE and PRUNE messages are used to form the multicast tree. A JOIN message is sent by a node willing to join the tree, and it receives the TREE message as an acknowledgement. A LEAVE message from a member node is followed by a PRUNE message by the root to enable the leave operation. To increase the scalability, Bayeux uses tree-partitioning and receiver clustering. Tree partitioning is done to create multiple roots and thus reduce the load on the single node and eliminate a single point of failure. Receiver identifier clustering allows local nodes to share the longest possible suffix. This may reduce the length of the path, but at the same time decreases fault tolerance by increasing the dependence on the same local set of nodes. Bayeux utilizes Tapestry's redundant routing paths for fault-resilient packet delivery. Reliance on time-outs has the potential of increasing the delay, thus affecting the performance of delay-sensitive streaming multimedia. From teifel@csl.cornell.edu Tue Dec 4 14:00:27 2001 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 fB4J0R626696 for ; Tue, 4 Dec 2001 14:00:27 -0500 (EST) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id fB4J0LG23922 for ; Tue, 4 Dec 2001 14:00:21 -0500 (EST) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Tue, 4 Dec 2001 14:00:21 -0500 (EST) From: "John R. Teifel" To: Subject: 615 PAPER 69 Message-ID: <20011204130850.E23385-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Bayeux: Bayeux is an architecture for scalable and fault-tolerant wide-area data dissemination. It provides efficient application-level multicast which scales to large receiver groups while tolerating failures in the network topology. Bayeux introduces specific load-balancing mechanisms to replicate root nodes and obtain more efficient bandwidth utilization. Bayeux uses the Tapestry architecture to achieve the above properties while also keeping the transmission overhead low. They evaluate their network performance based on two performance metrics, the relative delay penalty and the physical link stress. This work is part of the OceanStore project and they are continuing to evaluate its effectiveness in their simulation environment. It is not clear why their underlying hierarchical infrastructure is better than the other systems such as the projects at MIT, Microsoft, etc. From gupta@CS.Cornell.EDU Tue Dec 4 14:41:10 2001 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fB4JfA603810 for ; Tue, 4 Dec 2001 14:41:10 -0500 (EST) From: Indranil Gupta Received: (from gupta@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id fB4JfAv19107 for egs@cs.cornell.edu; Tue, 4 Dec 2001 14:41:10 -0500 (EST) Message-Id: <200112041941.fB4JfAv19107@zinger.cs.cornell.edu> Subject: 615 PAPER 69 To: egs@CS.Cornell.EDU Date: Tue, 4 Dec 2001 14:41:10 -0500 (EST) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Bayeux: an architecture for scalable and fault-tolerant wide-area data dissemination, Zhuang, Zhao, Joseph, Katz, and Kubiaowitz. Reviewer: Indranil Gupta This paper discusses multicast overlay schemes on top of the Tapestry routing framework. The algorithm is very similar to multicast routing in Pastry, where objects are associated with an id in the name space, and trees are constructed from receivers by including all nodes on the path to the root. The major deviation from Pastry's algorithms are that multiple roots are used in Bayeux, and that Bayeux talks about fault-tolerant packet delivery. Comments: - The Bayeux schemes for 'fault-resilient' routing (by using backup paths) tolerate only a certain number of failures (message losses, node crashes) in the network. In that sense, it only seems to be 'best-effort' fault-tolerance. There is no analysis of the behavior of Bayeux for applications that require *reliable* delivery of packets. Ack-based or nak-based protocols, such as SRM and RMTP, that are typically used for Internet multicast groups, are known to have scalability problems, in terms of message implosion with rising multicast group size. From papadp@ece.cornell.edu Tue Dec 4 15:15:44 2001 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 fB4KFi610269 for ; Tue, 4 Dec 2001 15:15:44 -0500 (EST) Received: from plato (plato.ece.cornell.edu [128.84.81.135]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fB4KCKM21750; Tue, 4 Dec 2001 15:12:20 -0500 Date: Tue, 4 Dec 2001 15:19:10 -0500 (EST) From: "Panagiotis (Panos) Papadimitratos" X-X-Sender: To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 69 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of : "Bayeux: an architecture for scalable and Fault-tolerant wide-area data dissemination," by S.ZQ.Zhuang et al Panagiotis Papadimtratos papadp@ece.cornell.edu Bayeux extends Tapestry by providing a multicast delivery protocol at the application level as well. The oblect location infrastructure provided by Tapestry lets bayeux naturally built logical trees rooted at the network location that stores data and wishes to initiate a multicast session. The fault-tolerance properties provided by Tapesty are enhanced here, at the expense of transmission overhead with packet duplication. Moreover, Bayeux partitions the logical trees so that it reduces the processing overhead of the root nodes. In particular, the multicast operation is facilitated by the route aggregation, which practically keeps the tree fanout low, i.e., equal to the name/address base. Moreover, delivery to multiple tree nodes does not imply that a packet has to be duplicated: it is sufficient to send one replica per address prefix. Also, the tree depth depends on the size of the name space. The root node advertises the session (i.e., the file id) which is stored at intermediate nodes, as described in Tapestry. As nodes join/leave the session, which is source- and data- specific, the requests propagate to the root of the tree. In order to balance this load, the authors propose to partition not only the trees but also oranize the nodes so that the access different trees according to the network proximity. The issue of network proximity in the light of the location-independent addressing schemes is recurring in the relevant literature, and sounds contradictory for schemes to backtrack to the ideas of an architecture that they had a priori rejected for their purposes.