Internet Engineering Task Force AVT/RMT WG Internet Draft Hofmann/Nonnenmacher/Rosenberg/Schulzrinne draft-hnrs-rmt-avt-feedback-00.txt Bell Laboratories,Columbia U. June 24, 1999 Expires: December, 1999 A Taxonomy of Feedback for Multicast STATUS OF THIS MEMO This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as work in progress. The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract When distributing information through multicast, it is often neccessary to solicit feedback from receivers. This feedback can be to report on reception quality, indicate loss of packets, or acknowledge receipt of data. There is a range of feedback mechanisms possible, ranging from polling to periodic multicast feedback. This document presents a taxonomy of these various mechanisms, with a discussion of the pros and cons of each approach and a discussion of applicability. 1 Introduction A number of protocols used on the Internet to distribute information through multicast make use of feedback. This feedback is provided to report on some aspect of the data delivery - ranging from positive or negative acknowledgements of individual packets to summary statistics Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 1] Internet Draft multicast feedback June 24, 1999 of reception quality. One such protocol is the Real Time Transport Protocol (RTP), specified in RFC1889 [1]. RTP distributes real time multimedia over multicast (it also supports unicast). Participants in an RTP session provide multicast feedback back to the group. This feedback includes reception statistics (such as loss, delay, and jitter) and participant data (name, email address, and phone number). The feedback is sent to the entire multicast group, so that it is seen by all other receivers. Each participant sends feedback to the group periodically, with a period proportional to the group size. While this mechanism is general purpose, and scales from small to large groups, it may not be appropriate for broadcast-like distribution. Another example class of protocols are reliable multicast protocols [2][3][4] [5]. Many of these rely on feedback from receivers to the sender, other receivers, or specific repair stations, in order to perform recovery. Multicast feedback may make sense in other applications as well. As such, this document provides a taxonomy of the feedback mechanisms that can be used for multicast. For each mechanism, the pros and cons are discussed, along with its applicability to certain scenarios and classes of feedback problems. Our eventual aim is to try and use this taxonomy to develop a common multicast feedback protocol which can meet the needs of both reliable multicast and RTCP. 2 Network Support for Feedback One important issue to keep in mind when classifying feedback for multicast is whether there is support from network elements or not. At one extreme, protocols like RTCP provide fully distributed, unassisted feedback. Routers provide no assistance in distributing it, and there are no additional network servers that need to be deployed for it. On the other end of the spectrum are reliable multicast protocols like the one proposed by Papadopoulos, Parulkar and Varghese [6] which makes use of new forwarding services in routers to reduce feedback implosion. In between these two extremes are protocols which make use of network servers, but with these servers at the application layer, not in the forwarding path. There are many examples of this from the space of reliable multicast protocols, including [7]. In the taxonomy below, we do not explicitly differentiate between protocols with network support (router-based or server-based) and Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 2] Internet Draft multicast feedback June 24, 1999 those without. Rather, this distinction is implicit in its classification. 3 The Axes of Multicast Feedback The mechanisms for feedback can be classified based on a tuple, with each entry in the tuple representing a different aspect of the feedback mechanism. Each component of the tuple represents an axis in the space of multicast feedback protocols. Each subsection below discusses one of the axes. 3.1 Feedback Destination Who will receive the feedback? At one extreme, the entire set of participants in the group can receive the feedback. At the other extreme, a single user (whether they are a member of the group or not) can receive the feedback. In the middle are cases where only partial subsets of users receive the feedback. In the case of reliable multicast, this subset might be grouped by loss correlation (those receivers who suffer similar losses are grouped together) or network proximity. So, in summary, the feedback destination can generally be one of one, subset, or all. 3.2 Feedback Mechanism The feedback mechanism is closely related to, but not the same as, feedback destination. It refers to the "how" of the feedback distribution. The feedback mechanism can be multicast, to the same group as the data was sent to. This is useful when the feedback destination is the entire group. Alternatively, the feedback mechanism can be multicast, but to a different group (perhaps one that is administratively scoped), or to the same group but with a different TTL. This would allow the feedback to target a subset of the receiver population. Use of such a mechanism usually requires a mapping from the feedback to the specific group or scope. Such mappings can be dynamic (based on group size, for example), or static. In other cases, the feedback can be sent to a unicast address. This address may be the address of the sender, or perhaps of some separate collection station (providing feedback to a specific user). When the address is a separate station, some means is needed to obtain this address. This can be done by placing the address in the data. Or, the address can be determined through some separate state distribution protocol. For example, LGMP [4] distributes the identity and status Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 3] Internet Draft multicast feedback June 24, 1999 information of active collection stations (Group Controllers) through a separate protocol. Receivers use this information for localized self-evaluation and for selection of an appropriate collection station. Unicast can also be used as a means for feedback to all group members or a subset therein. A separate station (or set of stations), can act as a collection point. Receivers unicast the feedback to the station, and the station unicasts it back to the specified set of receivers. This, of course, requires the station to have knowledge of group participants. Hybrid schemes exist as well. In particular, unicast can be used to send the feedback to a collection station, which then distributes it to the receivers using multicast. In summary, the set of possible feedback mechanisms includes multicast (same group), multicast (different group), unicast, or hybrid. 3.3 Feedback Source Who sends feedback? There is a wide range of possibilities here. All receivers may be required to send feedback. This is needed in protocols like RTP, where the feedback contains information that is different from each receiver. In addition, when intermediate servers provide aggregation of information, all receivers may be required to provide their feedback to an aggregation station. At the other extreme is feedback from a single member. This type of feedback is often used in conjunction with redundant content (see section 3.4). In between are cases where a subset provides feedback. This subset can be determined in many ways: statistical sampling: In this case, each receiver randomly decides to send feedback. The probability that they do send the feedback can be set by an external entity [8], or be computed in a distributed fashion based on some other parameters. Statistical sampling is useful in large groups where feedback from all participants would be too substantial. parameterized: In this case, the receivers send feedback if they meet some kind of criteria. For example, all receivers with loss rates exceeding 5% might send feedback, while all others do not. explicit selection: In this case, some external third party may Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 4] Internet Draft multicast feedback June 24, 1999 explicitly select the group of receivers who should send feedback. 3.4 Feedback Content What information does the feedback contain? We refer not to the actual parameters, but to the high level semantics it conveys. The feedback content can be one of the following: individualized: In this case, the content of the feedback is the reception quality, loss reports, or other feedback as reported by individual stations. This is the case in RTCP. redundant: In this case, the content of the feedback is the reception quality, loss reports, or other feedback as reported by individual stations. However, the nature of the feedback is that it is identical across those receivers providing the feedback. As a result, it may only be necessary for a single receiver to actually send the feedback. An example of this case are reliable multicast protocols where the feedback is the NAK for a specific packet. Each participant that has not received the packet sends an identical NAK. The information is redundant - only one of these is needed - if the retransmission is multicast. aggregated: The feedback delivered to the receivers is aggregate information. It represents a summary of the information which may have been provided by the data receivers. Use of aggregated feedback usually implies a unicast or hybrid delivery mechanism, with intermediate aggregating nodes. Placement, configuration, and communications between these nodes can be complex. As an alternate, group participants can act as aggregators. However, this still requires election procedures to choose the aggregators. Furthermore, the feedback from a set to the aggregator must be limited, and therefore cannot use the same multicast group and scope as the original request. 3.5 Flow Control Flow control is an integral component of feedback for multicast. Since the number of receivers reporting feedback can be large, the potential for congestion in the network and at specific hosts is large. In this section, we consider some of the flow control mechanisms which have been applied to help alleviate this problem. One approach is to use periodic feedback. Periodic feedback is useful when the information it contains is timely and needed continuously, and must be transmitted often. For scalability purposes, when the Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 5] Internet Draft multicast feedback June 24, 1999 feedback is delivered to the entire receiver population, the interval is made to scale with the number of participants sending feedback. This requires each participant to hear the feedback, in order to obtain a group estimate. Or, a single entity can maintain group size and distribute it to the other participants. This is the mechanism used in RTP. When periodic feedback is sent to specific collection stations or a subset of the population, scaling of the period may not be needed. In other cases, the feedback is in response to a particular event, which we call a poll. A poll might be an explicit request for feedback, or it can be detection of a lost packet. In these cases, periodic feedback is not appropriate. To provide some amount of congestion control, receivers who wish to send feedback do not do so immediately after the generating event. Rather, they wait some amount of time randomly selected, and then send feedback. If the feedback is redundant, and sent to the multicast group, choosing a feedback interval that is weighted towards larger values has been demonstrated to be useful [9] [10]. Both exponential and hyperexponential distributions have been proposed. When a participant sees a feedback from another participant, it cancels transmission of its own packet. The use of weighted feedback intervals causes fewer packets to be sent (since only one is needed), at the cost of longer latencies. When the feedback is from all participants, or from a sampled set, use of weighted distribution is not useful. However, it is advantageous to spread the feedback out over a specific interval, to avoid feedback implosion. Another mechanism for congestion control, similar to the periodic approach, is to use a token passed among the receivers. Only receivers with the token can send feedback. The mechanism requires the establishment of a virtual ring around the receivers, and works well for small to medium sized groups [11]. 4 Common Cases Although the three axes of the feedback classification are largely independent, not all combinations make sense. In fact, there are certain combinations that are very useful, and occur frequently in other protocols. 4.1 Group Periodic Feedback Destination: all Feedback Mechanism: multicast, same group Feedback Source: all Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 6] Internet Draft multicast feedback June 24, 1999 Feedback Content: individualized reports Flow Control: periodic This type of feedback is sent to the entire multicast group by every participant. The feedback is sent periodically. This type of feedback is especially useful in small to medium sized groups, for distributing timely information (such as reception quality) that is useful for all participants. RTP and SAP [12] are examples of this type. This type of feedback doesn't rely on any central entity to play the role of a poller or aggregator. As such, it is ideal for distributed applications, especially wide area ones, where coordination of central control is difficult and undesirable. In order to scale well, the feedback interval must generally scale with group size. This causes the mechanism to be less useful as group sizes increase. The information becomes less and less timely; however, timeliness was the main motivation for periodic transmission in the first place. 4.2 Polled Feedback Destination: one Feedback Mechanism: unicast Feedback Source: subset, randomly selected Feedback Content: individualized reports Flow Control: poll This type of feedback is unicast back to a specific host. Only a subsample of the population responds, and the response is generated after a poll arrives. An example of this approach is [8]. 4.3 Nielsen Feedback Destination: one Feedback Mechanism: unicast Feedback Source: subset, randomly selected Feedback Content: individualized reports Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 7] Internet Draft multicast feedback June 24, 1999 Flow Control: periodic This feedback mechanism can basically be summarized as the "Nielsen" approach. It is useful in particular for getting samples of feedback from a large population. Examples include television ratings, receiver population, or average reception quality. With a large population, only a small sampling is needed for a reasonable estimation of the average value for a parameter of interest. The feedback is sent unicast, since in this application other participants are not interested in the feedback. This mechanism is only useful for groups where there is a single party that is solely interested in the feedback. Usually this is the case for broadcast applications. 4.4 Per Packet NAK based Reliable Multicast Feedback Destination: one Feedback Mechanism: multicast Feedback Source: one Feedback Content: redundant Flow Control: poll This type of feedback mechanism is common to many reliable multicast protocols. The NAKs are the feedback, and they are sent to the entire group. The feedback is redundant, so that only one participant need respond. Since the NAK's occur in response to a loss event, they are event driven. The mechanism is broadly applicable to feedback in one-to-many and many-to-many groups, ranging in size from small to large. 4.5 Aggregated Reliable Multicast Feedback Destination: one Feedback Mechanism: unicast Feedback Source: all Feedback Content: aggregated Flow Control: periodic Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 8] Internet Draft multicast feedback June 24, 1999 This is another type of mechanism used in reliable multicast protocols, such as RMTP [5] and LGMP [4]. The feedback on packet reception is sent by all participants, but the information is unicast to aggregation stations which aggregate and pass it on. 5 Security Considerations It is important to note that when the feedback is sent to some separate address identified in the data, a significant denial of service attack is enabled. An attacker can send data containing the address of the target of the attack. Other parameters of the feedback might be controllable, allowing the attacker to force a flood of feedback to be sent to the target. For this reason, protocols which convey addresses for the destination of the feedback must ensure the destination can be authenticated. More generally, whenever the parameters of the feedback can be controlled in any message, authentication is required. Feedback can also contain sensitive information. This is particularly the case of the "Nielsen" application described above. In these cases, it may be important for the data to be sent unicast to a specific host. This avoids having the feedback propagate to competitors through multicast. Data encryption may be important as well, but may still not be sufficient if the feedback is sent multicast. Simply counting the number of feedback packets may reveal sensitive information, making multicast inappropriate. 6 Conclusion We have described a taxonomy for multicast feedback protocols, based on classification of the feedback along three axes: (1) where the feedback is sent, (2) who sends the feedback, and (3) when it the feedback sent. There is a range of values for each axes, and the appropriateness of the value depends on the application, group size, and desired timeliness of the feedback. We used our classification to show how existing mechanisms fit in. Future work is to further explore the possibility of unifying the various feedback protocols with a single feedback protocol. The first step in this process is to understand the range of requirements imposed by these feedback mechanisms. That is the purpose of this document. 7 Bibliography [1] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: a transport protocol for real-time applications," Request for Comments (Proposed Standard) 1889, Internet Engineering Task Force, Jan. 1996. Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 9] Internet Draft multicast feedback June 24, 1999 [2] J. Nonnenmacher, E. Biersack, and D. Towsley, "Parity-based loss recovery for reliable multicast transmission," ACM Computer Communications Review , vol. 27, pp. 289--300, Oct. 1997. ACM SIGCOMM'97, Sept. 1997. [3] S. Floyd, V. Jacobson, C.-G. Liu, S. McCanne, and L. Zhang, "A reliable multicast framework for light-weight sessions and application level framing," vol. 5, pp. 784--803, Dec. 1997. [4] M. Hofmann and M. Rohrmuller, "Impact of virtual group structure on multicast performance," in Fourth International COST 237 Workshop , (Lisbon, Portugal), pp. 165--180, Springer Verlag, Dec. 1997. [5] J. C. Lin and S. Paul, "RMTP: a reliable multicast transport protocol," in IEEE Infocom , (San Fransisco, Californialifornia), Mar. 1996. [6] C. Papadopoulos, G. Parulkar, and G. Varghese, "An error control scheme for large-scale multicast applications," in IEEE Infocom , (San Francisco, California), p. 1188, March/April 1998. [7] H. W. Holbrook, S. K. Singhal, and D. R. Cheriton, "Log-based receiver-reliable multicast for distributed interactive simulation," ACM Computer Communications Review , vol. 25, pp. 328--341, Oct. 1995. [8] J.-C. Bolot, T. Turletti, and I. Wakeman, "Scalable feedback control for multicast video distribution in the internet," in ACM Sigcomm , (London, England), pp. 58--67, ACM, Aug. 1994. [9] J. Nonnenmacher and E. W. Biersack, "Optimal multicast feedback," in IEEE Infocom , (San Francisco, California), p. 964, March/April 1998. [10] J. Rosenberg and H. Schulzrinne, "Timer reconsideration for enhanced RTP scalability," in IEEE Infocom , (San Francisco, California), March/April 1998. [11] J.Chang and N.Maxemchuk, "A broadcast protocol for broadcast networks," in IEEE Globecom , Dec. 1993. [12] M. Handley, C. Perkins, and E. Whelan, "Session announcement protocol," Internet Draft, Internet Engineering Task Force, June 1999. Work in progress. Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 10] Internet Draft multicast feedback June 24, 1999 Full Copyright Statement Copyright (c) The Internet Society (1999). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Hofmann/Nonnenmacher/Rosenberg/Schulzrinne [Page 11]