Error Control and Support for Large-Scale Multicast Applications

Large-scale distributed applications often require data to be distributed from one or more of the participants to many or all of the others. This is most efficiently handled by multicast. Unfortunately, multicast in the Internet suffers from many problems, several of which have been addressed by the research conducted as part of this project:

1. Loss
   One of the foremost problems is the unreliability of the Internet multicast service: some studies have shown over 30% packet loss, making it a challenge to communicate. Even much lower loss rates are a problem in large-scale applications, as the retransmit requests can easily flood the sender, resulting in so-called sender implosion. As part of this project, lightweight multicast services (LMS) were developed and improved, that make efficient propagation and fulfillment of retransmit requests possible, allowing for a simple and effective implementation of reliable multicast protocols on top of this service. To avoid additional load on the source and improve response time, the system aggregates and directs the retransmit request to a close-by participant that did not suffer the loss.
2. Congestion Control
   With multicast gaining attraction, it becomes important to ensure that multicast traffic does not overload the network or unnecessarily impair other traffic, a mechanism commonly known as congestion control. This is an especially challenging task in multicast, due to the heterogeneity of the link conditions. A subtle balance needs to be found between quick response to congestion and avoiding constant switching of the worst-case link, which would result in the transmit rate dropping to zero. Our result, SRM/CC, combines these mechanisms and is able to find this balance.
3. Availability and Simplicity
   The above mechanisms provide for efficient solution of two main problems at a minimal network overhead. During the project it became clear that multicast would not be as quickly and widely deployed as expected: many users would be unable to get multicast service from their network providers. We thus started looking at end-system multicast (ALMI) and dedicated-server multicast (AMcast). Our results are very promising and became a driving force behind many other research projects on self-organizing and/or structured overlay networks.
4. Scalability
   Multicast routing information is a major burden on Internet routers. We developed Imprecise Multicast Routing to trade significant savings in router memory and state information, as well as in processing complexity, against a small penalty in additional traffic.
5. Applications
   A network function is nothing without applications using it. One of the most promising applications is Media-on-Demand, for entertainment as well as for education and information. Our research in that area resulted in the first scalable, simple, and practicable mechanism whose performance is basically indistinguishable from the theoretical optimum. In addition, it supports a wide variety of scenarios, including pure one-way communication, with no data transmitted from the receivers to the sender.

Key Results

The following lists some of the key achievements of our research (for more results and details, see the publications below):

• LMS was one of the first to propose partial offloading of router functions to nearby hosts. It partially initiated and heavily influenced the design of PGM, a mechanism for reliable multicast that is widely deployed in the Internet.
• ALMI was one of the first to propose self-organizing overlay networks on top of the Internet to perform some function that was not or not satisfactorily offered by the underlying network. It builds on the Internet philosophy that the network should only be burdened by work that cannot efficiently be done in end systems. It has spurred significant interest in this area and many research projects, that use end systems to build higher-order network topologies.
• Media-on-Demand is likely become a major source of network traffic. We show that Fuzzycast, a simple, semi-randomized algorithm that is much more efficient than previous mechanisms and whose performance is basically indistinguishable from the theoretical optimum.

Publications

Participants

• Wei Deng
• Ramaprabhu Janakiraman
• Christos Papadopoulos
• Guru Parulkar
• Sherlia Shi
• Jonathan S. Turner
• Marcel Waldvogel