Overlay-based multicast has been proposed as a key alternative for large-scale group communication. There is ample motivation for such an approach, as it delivers the scalability advantages of multicast while avoiding the deployment issues of a network-level solution. As multicast functionality is pushed to autonomous, unpredictable end systems, however, significant performance loss can result from their higher degree of transiency when compared to routers.
Our work explores alternative system designs and techniques for delivering high application performance at relatively low costs and under high degree of transiency, evaluating their performance and associated cost through simulation and wide-area experimentation.People
Group members
- Fabian E. Bustamante, Faculty PI
- Stefan Birrer (Northwester U.)
Papers
Stefan Birrer, Fabián E. Bustamante A Comparison of Resilient Overlay Multicast Approaches Journal Article n IEEE Journal on Selected Areas in Communications (JSAC) -- Special Issue on Advances in Peer-to-Peer Streaming Systems, 25 (9), 2007. @article{CROMA, title = {A Comparison of Resilient Overlay Multicast Approaches}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://www.aqualab.cs.northwestern.edu/wp-content/uploads/2019/02/SBirrerJSAC07.pdf}, year = {2007}, date = {2007-12-03}, journal = {n IEEE Journal on Selected Areas in Communications (JSAC) -- Special Issue on Advances in Peer-to-Peer Streaming Systems}, volume = {25}, number = {9}, abstract = {Overlay-based multicast has been proposed as a key alternative for large-scale group communication. There is ample motivation for such an approach, as it delivers the scalability advantages of multicast while avoiding the deployment issues of a network-level solution. As multicast functionality is pushed to autonomous, unpredictable end systems, however, significant performance loss can result from their higher degree of transiency when compared to routers. Consequently, a number of techniques have recently been proposed to improve overlays' resilience by exploiting path diversity and minimizing node dependencies. Delivering high application performance at relatively low costs and under high degree of transiency has proven to be a difficult task. Each of the proposed resilient techniques comes with a different trade-off in terms of delivery ratio, end-to-end latency and additional network traffic. In this paper, we review some of these approaches and evaluate their effectiveness by contrasting the performance and associated cost of representative protocols through simulation and wide area experimentation.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Overlay-based multicast has been proposed as a key alternative for large-scale group communication. There is ample motivation for such an approach, as it delivers the scalability advantages of multicast while avoiding the deployment issues of a network-level solution. As multicast functionality is pushed to autonomous, unpredictable end systems, however, significant performance loss can result from their higher degree of transiency when compared to routers. Consequently, a number of techniques have recently been proposed to improve overlays' resilience by exploiting path diversity and minimizing node dependencies. Delivering high application performance at relatively low costs and under high degree of transiency has proven to be a difficult task. Each of the proposed resilient techniques comes with a different trade-off in terms of delivery ratio, end-to-end latency and additional network traffic. In this paper, we review some of these approaches and evaluate their effectiveness by contrasting the performance and associated cost of representative protocols through simulation and wide area experimentation. |
Stefan Birrer, Fabián E. Bustamante Resilience in Overlay Multicast Protocols Journal Article In Proc. of the 14th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2006. @article{ROMP, title = {Resilience in Overlay Multicast Protocols}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/SBirrer06ROMP.pdf}, year = {2006}, date = {2006-10-03}, journal = {In Proc. of the 14th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems}, abstract = {One of the most important challenges of self-organized, overlay systems for large-scale group communication lies in these systems ability to handle the high degree of transiency inherent to their environment. While a number of resilient protocols and techniques have been recently proposed, achieving high delivery ratios without sacrificing end-to-end latencies or incurring significant additional costs has proven to be a difficult task. In this paper we review some of these approaches and experimentally evaluate their effectiveness by contrasting their performance and associated cost through simulation and wide-area experimentation.}, keywords = {}, pubstate = {published}, tppubtype = {article} } One of the most important challenges of self-organized, overlay systems for large-scale group communication lies in these systems ability to handle the high degree of transiency inherent to their environment. While a number of resilient protocols and techniques have been recently proposed, achieving high delivery ratios without sacrificing end-to-end latencies or incurring significant additional costs has proven to be a difficult task. In this paper we review some of these approaches and experimentally evaluate their effectiveness by contrasting their performance and associated cost through simulation and wide-area experimentation. |
Stefan Birrer, Fabián E. Bustamante The Feasibility of DHT-based Streaming Multicast Journal Article In Proc. of the 13th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 2005. @article{FDHTSM, title = {The Feasibility of DHT-based Streaming Multicast}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/SBirrer05FDSM.pdf}, year = {2005}, date = {2005-11-03}, journal = { In Proc. of the 13th IEEE/ACM International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems}, abstract = {We explore the feasibility of streaming applications over DHT-based substrates. In particular, we focus our study on the implications of bandwidth heterogeneity and transiency, both characteristic of these systems' target environment. Our discussion is grounded on an initial evaluation of SplitStream, a representative DHT-based cooperative multicast system.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We explore the feasibility of streaming applications over DHT-based substrates. In particular, we focus our study on the implications of bandwidth heterogeneity and transiency, both characteristic of these systems' target environment. Our discussion is grounded on an initial evaluation of SplitStream, a representative DHT-based cooperative multicast system. |
Stefan Birrer, Fabián E. Bustamante Magellan: Performance-based, Cooperative Multicast Journal Article In Proc. of the Tenth International Workshop on Web Content Caching and Distribution, 2005. @article{Magellan, title = {Magellan: Performance-based, Cooperative Multicast}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/SBirrer05MPCM.pdf}, year = {2005}, date = {2005-09-03}, journal = {In Proc. of the Tenth International Workshop on Web Content Caching and Distribution}, abstract = {Among the proposed overlay multicast protocols, tree-based systems have proven to be highly scalable and efficient in terms of physical link stress and end-to-end latency. Conventional tree-based protocols, however, distribute the forwarding load unevenly among the participating peers. An effective approach for addressing this problem is to stripe the multicast content across a forest of disjoint trees, evenly sharing the forwarding responsibility among participants. DHTs seem to be naturally well suited for the task, as they are able to leverage the inherent properties of their routing model in building such a forest. In heterogeneous environments, though, DHT-based schemes for tree (and forest) construction may yield deep, unbalanced structures with potentially large delivery latencies. This paper introduces Magellan, a new overlay multicast protocol we have built to explore the tradeoff between fairness and performance in these environments. Magellan builds a data-distribution forest out of multiple performance-centric, balanced trees. It assigns every peer in the system a primary tree with priority over the peer's resources. The peers' spare resources are then made available to secondary trees. In this manner, Magellan achieves fairness, ensuring that every participating peer contributes resources to the system. By employing a balanced distribution tree with O(log N)-bounded, end-to-end hop-distance, Magellan also provides high delivery ratio with comparable low latency. Preliminary simulation results show the advantage of this approach.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Among the proposed overlay multicast protocols, tree-based systems have proven to be highly scalable and efficient in terms of physical link stress and end-to-end latency. Conventional tree-based protocols, however, distribute the forwarding load unevenly among the participating peers. An effective approach for addressing this problem is to stripe the multicast content across a forest of disjoint trees, evenly sharing the forwarding responsibility among participants. DHTs seem to be naturally well suited for the task, as they are able to leverage the inherent properties of their routing model in building such a forest. In heterogeneous environments, though, DHT-based schemes for tree (and forest) construction may yield deep, unbalanced structures with potentially large delivery latencies. This paper introduces Magellan, a new overlay multicast protocol we have built to explore the tradeoff between fairness and performance in these environments. Magellan builds a data-distribution forest out of multiple performance-centric, balanced trees. It assigns every peer in the system a primary tree with priority over the peer's resources. The peers' spare resources are then made available to secondary trees. In this manner, Magellan achieves fairness, ensuring that every participating peer contributes resources to the system. By employing a balanced distribution tree with O(log N)-bounded, end-to-end hop-distance, Magellan also provides high delivery ratio with comparable low latency. Preliminary simulation results show the advantage of this approach. |
Stefan Birrer, Fabián E. Bustamante, Dong Lu, Peter Dinda, Yi Qiao FatNemo: Multi-Source Multicast Overlay Fat-Tree Journal Article Poster in Proc. of the Second Symposium on Networked Systems Design & Implementation, 2005. @article{FatNemob, title = {FatNemo: Multi-Source Multicast Overlay Fat-Tree}, author = {Stefan Birrer and Fabián E. Bustamante and Dong Lu and Peter Dinda and Yi Qiao}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/SBirrer05NSDI.pdf http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/nsdi05poster.pdf}, year = {2005}, date = {2005-05-03}, journal = {Poster in Proc. of the Second Symposium on Networked Systems Design & Implementation}, abstract = {This poster presents the idea of emulating fat-trees in overlays for multi-source multicast applications. Fat-trees are like real trees in that their branches become thicker the closer one gets to the root, thus overcoming the "root bottleneck" of regular trees. We describes FatNemo, a novel overlay multi-source multicast protocol based on this idea, and present early experimental and analytical results showing the advatanges of this approach. FatNemo organizes its members into a tree of clusters with cluster sizes increasing closer to the root. It uses bandwidth capacity to decide the highest layer in which a peer can participate, and relies on co-leaders to share the forwarding responsibility and to increase the tree's resilience to path and node failures.}, keywords = {}, pubstate = {published}, tppubtype = {article} } This poster presents the idea of emulating fat-trees in overlays for multi-source multicast applications. Fat-trees are like real trees in that their branches become thicker the closer one gets to the root, thus overcoming the "root bottleneck" of regular trees. We describes FatNemo, a novel overlay multi-source multicast protocol based on this idea, and present early experimental and analytical results showing the advatanges of this approach. FatNemo organizes its members into a tree of clusters with cluster sizes increasing closer to the root. It uses bandwidth capacity to decide the highest layer in which a peer can participate, and relies on co-leaders to share the forwarding responsibility and to increase the tree's resilience to path and node failures. |
Stefan Birrer, Fabián E. Bustamante Reef: Efficiently designing and evaluating overlay algorithms Technical Report Department of Computer Science, Northwestern University (NWU-CS-05-14), 2005. @techreport{Reef, title = {Reef: Efficiently designing and evaluating overlay algorithms}, author = {Stefan Birrer and Fabián E. Bustamante}, year = {2005}, date = {2005-02-03}, number = {NWU-CS-05-14}, institution = {Department of Computer Science, Northwestern University}, keywords = {}, pubstate = {published}, tppubtype = {techreport} } |
Stefan Birrer, Fabián E. Bustamante Resilient Peer-to-Peer Multicast from the Ground Up Journal Article In Proc. of the IEEE Network Computing and Applications - Workshop on Adaptive Grid Computing, 2004. @article{P2PMGUb, title = {Resilient Peer-to-Peer Multicast from the Ground Up}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/SBirrer04RGU.pdf http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/nca04nemo.pdf}, year = {2004}, date = {2004-08-03}, journal = {In Proc. of the IEEE Network Computing and Applications - Workshop on Adaptive Grid Computing}, abstract = {One of the most important challenges of peer-to-peer multicast protocols is the ability to efficiently deal with the high degree of churn inherent to their environment. As multicast functionality is pushed to autonomous, unpredictable peers, significant performance losses can result from group membership changes and the higher failure rates of end-hosts when compared to routers. Achieving high delivery ratios without sacrificing end-to-end latencies or incurring additional costs has proven to be a challenging task. This paper introduces Nemo, a novel peer-to-peer multicast protocol that aims at achieving this elusive goal. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We compare the performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show that Nemo can achieve delivery ratios similar to those of comparable protocols (up to 99.98%) under different failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 85%) and control-related traffic. }, keywords = {}, pubstate = {published}, tppubtype = {article} } One of the most important challenges of peer-to-peer multicast protocols is the ability to efficiently deal with the high degree of churn inherent to their environment. As multicast functionality is pushed to autonomous, unpredictable peers, significant performance losses can result from group membership changes and the higher failure rates of end-hosts when compared to routers. Achieving high delivery ratios without sacrificing end-to-end latencies or incurring additional costs has proven to be a challenging task. This paper introduces Nemo, a novel peer-to-peer multicast protocol that aims at achieving this elusive goal. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We compare the performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show that Nemo can achieve delivery ratios similar to those of comparable protocols (up to 99.98%) under different failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 85%) and control-related traffic. |
Stefan Birrer, Fabián E. Bustamante Nemo: Resilient Peer-to-Peer Multicast without the Cost Technical Report Department of Computer Science, Northwestern University (NWU-CS-04-36), 2004. @techreport{Nemo, title = {Nemo: Resilient Peer-to-Peer Multicast without the Cost}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/NWU-CS-04-36.pdf}, year = {2004}, date = {2004-01-03}, number = {NWU-CS-04-36}, institution = {Department of Computer Science, Northwestern University}, abstract = {One of the most important challenges of peer-to-peer multicast protocols is the ability to efficiently deal with the high degree of transiency inherent to their environment. As multicast functionality is pushed to autonomous, unpredictable peers, significant performance losses can result from group membership changes and the higher failure rates of end-hosts when compared to routers. Achieving high delivery ratios without sacrificing end-to-end latencies or incurring additional costs has proven to be a challenging task. This paper introduces Nemo, a novel peer-to-peer multicast protocol that aims at achieving this elusive goal. Based on two simple techniques: (1) co-leaders to minimize dependencies and, (2) triggered negative acknowledgments (NACKs) to detect lost packets, Nemo s design emphasizes conceptual simplicity and minimum dependencies, thus achieving performance characteristics capable of withstanding the natural instability of its target environment. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We compare the scalability and performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show that Nemo can achieve delivery ratios (up to 99.9%) similar to those of comparable protocols under high failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 90%) and control-related traffic (reductions > 20%).}, keywords = {}, pubstate = {published}, tppubtype = {techreport} } One of the most important challenges of peer-to-peer multicast protocols is the ability to efficiently deal with the high degree of transiency inherent to their environment. As multicast functionality is pushed to autonomous, unpredictable peers, significant performance losses can result from group membership changes and the higher failure rates of end-hosts when compared to routers. Achieving high delivery ratios without sacrificing end-to-end latencies or incurring additional costs has proven to be a challenging task. This paper introduces Nemo, a novel peer-to-peer multicast protocol that aims at achieving this elusive goal. Based on two simple techniques: (1) co-leaders to minimize dependencies and, (2) triggered negative acknowledgments (NACKs) to detect lost packets, Nemo s design emphasizes conceptual simplicity and minimum dependencies, thus achieving performance characteristics capable of withstanding the natural instability of its target environment. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We compare the scalability and performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show that Nemo can achieve delivery ratios (up to 99.9%) similar to those of comparable protocols under high failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 90%) and control-related traffic (reductions > 20%). |
Stefan Birrer, Fabián E. Bustamante Resilient Peer-to-Peer Multicast from the Ground Up Technical Report Department of Computer Science, Northwestern University (NWU-CS-03-22), 2003. @techreport{RP2PMGU, title = {Resilient Peer-to-Peer Multicast from the Ground Up}, author = {Stefan Birrer and Fabián E. Bustamante}, url = {http://typica.cs.northwestern.edu/wp-content/uploads/2019/02/NWU-CS-03-22.pdf}, year = {2003}, date = {2003-01-03}, number = {NWU-CS-03-22}, institution = { Department of Computer Science, Northwestern University}, abstract = {One of the most important challenges of peer-to-peer multicast protocols is the ability to efficiently deal with the high degree of churn inherent to their environment. As multicast functionality is pushed to autonomous, unpredictable peers, significant performance losses can result from group membership changes and the higher failure rates of end-hosts when compared to routers. Achieving high delivery ratios without sacrificing end-to-end latencies or incurring additional costs has proven to be a challenging task. This paper introduces Nemo, a novel peer-to-peer multicast protocol that aims at achieving this elusive goal. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We compare the performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show how Nemo can achieve delivery ratios similar to those of comparable protocols (up to 99.98%) under different failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 85%) and control-related traffic. }, keywords = {}, pubstate = {published}, tppubtype = {techreport} } One of the most important challenges of peer-to-peer multicast protocols is the ability to efficiently deal with the high degree of churn inherent to their environment. As multicast functionality is pushed to autonomous, unpredictable peers, significant performance losses can result from group membership changes and the higher failure rates of end-hosts when compared to routers. Achieving high delivery ratios without sacrificing end-to-end latencies or incurring additional costs has proven to be a challenging task. This paper introduces Nemo, a novel peer-to-peer multicast protocol that aims at achieving this elusive goal. We present an extensive comparative evaluation of our protocol through simulation and wide-area experimentation. We compare the performance of Nemo with that of three alternative protocols: Narada, Nice and Nice-PRM. Our results show how Nemo can achieve delivery ratios similar to those of comparable protocols (up to 99.98%) under different failure rates, but at a fraction of their cost in terms of duplicate packets (reductions > 85%) and control-related traffic. |
