A Reliable Multicast Framework for Light-weight Sessions andApplication Level FramingSally Floyd, Van Jacobson, Steven McCanneLawrence Berkeley Laboratory, University of California, Berkeley, CA 94720floyd, van, [email protected] LiuUniversity of Southern California, Los Angeles, CA [email protected] ZhangXerox PARC, 3333 Coyote Hill Road, Palo Alto, CA [email protected] 7, 1995ABSTRACTThis paper1describes SRM (Scalable Reliable Multicast), areliable multicast framework for application level framingand light-weight sessions. The algorithms of this frameworkare efficient, robust, and scale well to both very large net-works and very large sessions. The framework has beenprototyped in wb, a distributed whiteboard application, andhas been extensively tested on a global scale with sessionsranging from a few to more than 1000 participants. Thepaper describes the principles that have guided our design,including the IP multicast group delivery model, an end-to-end, receiver-based model of reliability, and the applicationlevel framing protocol model. As with unicast communica-tions, the performance of a reliable multicast delivery algo-rithm depends on the underlying topology and operationalenvironment. We investigate that dependence via analysisand simulation, and demonstrate an adaptive algorithm thatuses the results of previous loss recovery events to adapt thecontrol parameters used for future loss recovery. With theadaptive algorithm, our reliable multicast delivery algorithmprovides good performance over a wide range of underlyingtopologies.1 IntroductionSeveral researchers have proposed generic reliable multicastprotocols, much as TCP is a generic transport protocol forreliable unicast transmission. In this paper we take a dif-Supported by the Director, Office of Energy Research, Scientific Com-puting Staff, of the U.S. Department of Energy under Contract No. DE-AC03-76SF00098.Supported in part by the Advanced Research Projects Agency, moni-tored by Fort Huachuca under contract DABT63-94-C-0073.1An earlier version of this paper appeared in ACM SIGCOMM 95. Thisversion corrects errors in the graphs of that earlier version.ferent view: unlike the unicast case where requirements forreliable, sequenced data delivery are fairly general, differ-ent multicast applications have widely different requirementsfor reliability. For example, some applications require thatdelivery obey a total ordering while many others do not.Some applications have many or all the members sendingdata while others have only one data source. Some applica-tions have replicated data, for example in an-redundant filestore, so several members are capable of transmitting a dataitem while for others all data originates at a single source.These differences all affect the design of a reliable multi-cast protocol. Although one could design a protocol for theworst-case requirements, e.g., guarantee totally ordered de-livery of replicated data from a large number of sources, suchan approach results in substantial overhead for applicationswith more modest requirements. One cannot make a singlereliable multicast delivery scheme that simultaneously meetsthe functionality, scalability and efficiency requirements ofall applications.The weakness of “one size fits all” protocols has longbeen recognized. In 1990 Clark and Tennenhouse proposed anew protocol model called Application Level Framing (ALF)which explicitly includes an application’s semantics in thedesign of that application’s protocol [CT90]. ALF was laterelaborated with a light-weight rendezvous mechanism basedon the IP multicast distribution model, and with a notionof receiver-based adaptation for unreliable, real-time appli-cations such as audio and video conferencing. The result,known as Light-Weight Sessions (LWS), has been very suc-cessful in the design of wide-area, large-scale, conferencingapplications. This paper further evolves the principles ofALF and LWS to add a framework for scalable reliable mul-ticast (SRM).ALF says that the best way to meet diverse applicationrequirements is to leave as much functionality and flexibility1as possible to the application. Therefore our algorithms aredesigned to meet only the minimal definition of reliable mul-ticast, i.e., eventual delivery of all the data to all the groupmembers, without enforcing any particular delivery order.We believe that if the need arises, machinery to enforce aparticular delivery order can be easily added on top of thisreliable delivery service.The design is also heavily based on the group deliverymodel that is the centerpiece of the IP multicast protocol[D91]. In IP multicast, data sources simply send to thegroup’s multicast address (a normal IP address chosen froma reserved range of addresses) without needing any advanceknowledge of the group membership. To receive any datasent to the group, receivers simply announce that they are in-terested (via a “join” message broadcast on the local subnet)— no knowledge of the group membership or active sendersis required. Each receiver joins and leaves the group indi-vidually, without affecting the data transmission to any othermember. Our multicast delivery framework further enhancesthe multicast group concept by maximizing information anddata sharing among all the members, and strengthens the in-dividuality of membership by making each member respon-sible for its own correct reception of all the data.Finally, our design attempts to follow the core design prin-ciples of TCP/IP. First, we require only the basic IP deliverymodel — best-effort with possible duplication and reorder-ing of packets — and build the reliability on an end-to-endbasis. No change or special support is required from the un-derlying IP network. Second, in a fashion similar to TCPadaptively setting timers or congestion control windows, ouralgorithms dynamically adjust their control parameters basedon the observed performance within a session. This allowsapplications using this model to adapt to a wide range ofgroup sizes, topologies and link bandwidths while maintain-ing robust and high performance.The paper proceeds as follows: Section 2 discusses gen-eral issues for reliable multicast delivery. Section 3 describesin detail the reliable multicast algorithm embedded in thewb implementation. Section 4 discusses the performanceof the algorithm in simple topologies such as chains, stars,and bounded-degree trees, and Section 5
View Full Document
Unlocking...