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]