Network Working Group J. Rosenberg Request for Comments: 2762 dynamicsoft Category: Experimental H. Schulzrinne Columbia U. February 2000 Sampling of the Group Membership in RTP Status of this Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved.
AbstractIn large multicast groups, the size of the group membership table maintained by RTP (Real Time Transport Protocol) participants may become unwieldy, particularly for embedded devices with limited memory and processing power. This document discusses mechanisms for sampling of this group membership table in order to reduce the memory requirements. Several mechanisms are proposed, and the performance of each is considered. 1], mandates that RTCP packets be transmitted from each participant with a period roughly proportional to the group size. The group size is obtained by storing a table, containing an entry for each unique SSRC seen in RTP and RTCP packets. As members leave or time out, entries are deleted, and as new members join, entries are added. The table is thus highly dynamic. For large multicast sessions, such as an mbone broadcast or IP-based TV distribution, group sizes can be extremely large, on the order of hundreds of thousands to millions of participants. In these environments, RTCP may not always be used, and thus the group membership table isn't needed. However, it is highly desirable for RTP to scale well for groups with one member to groups with one million members, without human intervention to "turn off" RTCP when it's no longer appropriate. This means that the same tools and
systems can be used for both small conferences and TV broadcasts in a smooth, scalable fashion. Previous work  has identified three major scalability problems with RTP. These are: 1. Congestion due to floods of RTCP packets in highly dynamic groups; 2. Large delays between receipt of RTCP packets from a single user; 3. Large size of the group membership table. The reconsideration algorithm  helps to alleviate the first of these. This document addresses the third, that of large group size tables. Storage of an SSRC table with one million members, for example, requires at least four megabytes. As a result, embedded devices with small memory capacity may have difficulty under these conditions. To solve this problem, SSRC sampling has been proposed. SSRC sampling uses statistical sampling to obtain a stochastic estimate of the group membership. There are many issues that arise when this is done. This document reviews these issues and discusses the mechanisms which can be applied by implementors. In particular, it focuses on three methods for adapting the sampling probability as the group membership varies. It is important to note that the IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document, and in particular to one of the three mechanisms: the binning algorithm described below. For more information consult the online list of claimed rights. The two other approaches presented are inferior to the binning algorithm, but are included as they are believed to be unencumbered by IPR.
This sampling process can be described mathematically as: D = (K*M == S*M) Where the * operator denotes AND and the == operator denotes a test for equality. D represents the sampling decision. According to the RTP specification, the SSRC's used by session participants are chosen randomly. If the distribution is also uniform, it is easy to see that the above filtering will cause 1 out of 2**m SSRC's to be placed in the table, where m is the number of bits in the mask, M, which are one. Thus, the sampling probability p is 2**-m. Then, to obtain an actual group size estimate, L, the number of entries in the table N is multiplied by 2**m: L = N * 2**m Care must be taken when choosing which bits to set to 1 in the mask. Although the RTP specification mandates randomly chosen SSRC, there are many known implementations which do not conform to this. In particular, the ITU H.323  series of recommendations allows the central control element, the gatekeeper, to assign the least significant 8 bits of the SSRC, while the most significant are randomly chosen by RTP participants. The safest way to handle this problem is to first hash the SSRC using a cryptographically secure hash, such as MD5 , and then choose 32 of the bits in the result as the SSRC used in the above computation. This provides much better randomness, and doesn't require detailed knowledge about how various implementations actually set the SSRC.
probability p=2**-m should be no smaller than .5 when there are ten thousand group members. More generally, to achieve a desired standard deviation to mean ratio of T, the sampling probability should be no less than: p > 1 / (1 + G*(T**2))
point of sampling was to not have to remember them. Therefore, if the number of bits in the mask is just reduced without any changes in the membership table, the group estimate will instantly drop by exactly half. To compensate for this, some kind of algorithm is needed. Two approaches are presented here: a corrective-factor solution, and a binning solution. The binning solution is simpler to understand and performs better. However, we include a discussion of the corrective- factor solution for completeness and comparison, and also because it is believed to be unencumbered by IPR.
/ 0 , t < ts | ts + cL(ts-) - t fi(t) = |( L(ts-) - L(ts+)) ---------------- , ts < t < ts+cL(ts-) | cL(ts-) | 0 , t > ts + cL(ts-) \ and the multiplicative factor as: / 1 , t < ts | | ts + 2cL(ts-) - t gi(t) | ----------------- , ts < t < ts + cL(ts-) | cL(ts-) | \ 1 , t > ts + cL(ts-) Note that in these equations, L(t) denotes the group size estimate obtained including the corrective factors except for the new factor. ts- is the time right before the reduction in the number of bits, and ts+ the time after. As a result, L(ts-) represents the group size estimate before the reduction, and L(ts+) the estimate right after, but not including the new factor. Finally, the actual group size estimate L(t) is given by: ----- \ L(t) = / fi(t) + N*(2**m) ----- i for the additive factor, and: ------ | | | | L(t)= | | N*(2**m)*gi(t) for the multiplicative factor. Simulations showed that both algorithms performed equally well, but both tended to seriously underestimate the group size when the group membership was rapidly declining . This is demonstrated in the performance data below.
As an example, consider computation of the additive factor. The group size is 1000, c is 1 second, and m is two. With a mask of this size, a participant will, on average, observe 250 (N = 250) users. At t=0, the user decides to reduce the number of bits in the mask to 1. As a result, L(0-) is 1000, and L(0+) is 500. The additive factor therefore starts at 500, and decays to zero at time ts + cL(ts-) = 1000. At time 500, lets assume N has increased to 375 (this will, on average, be the case if the actual group size has not changed). At time 500, the additive factor is 250. This is added to 2**m times N, which is 750, resulting in a group size estimate of 1000. Now, the user decides to reduce the number of bits in the mask again, so that m=0. Another additive factor is computed. This factor starts at L(ts-) (which is 1000), minus L(ts+). L(ts+) is computed without the new factor; it is the first additive factor at this time (250) plus 2**m (1) times N (375). This is 625. As a result, the new additive factor starts at 1000 - 625 (375), and decays to 0 in 1000 seconds.
The algorithm works by basically keeping the old estimate when the number of bits in the mask drops. As users arrive, they are gradually moved into the lower bin, reducing the amount that the higher bin contributes to the total estimate. However, the old estimate is still updated in the sense that users which timeout are removed from the higher bin, and users who send BYE packets are also removed from the higher bin. This allows the older estimate to still adapt, while gradually phasing it out. It is this adaptation which makes it perform much better than the corrective algorithms. The algorithm is also extremely simple.
Time No Sampling Binned Additive Multiplicative ---- ----------- ------ -------- -------------- 20000 5001 5024 5024 5024 20250 4379 4352 4352 4352 20500 3881 3888 3900 3853 20750 3420 3456 3508 3272 21000 3018 2992 3100 2701 21250 2677 2592 2724 2225 21500 2322 2272 2389 1783 21750 2034 2096 2125 1414 22000 1756 1760 1795 1007 22250 1476 1472 1459 582 22500 1243 1232 1135 230 22750 1047 1040 807 80 23000 856 864 468 59 23250 683 704 106 44 23500 535 512 32 32 23750 401 369 24 24 24000 290 257 17 17 24250 198 177 13 13 24500 119 129 11 11 24750 59 65 8 8 25000 18 1 2 2
This is easily compensated for in the binning algorithm. A sender is always placed in the 0th bin. When a sender becomes a receiver, it is moved into the bin corresponding to the current value of m, if its SSRC matches the key under the masked comparison operation. 1]. In fact, SSRC sampling, as described above, can help somewhat in reducing the effect of certain attacks. RTP, when used without authentication of RTCP packets, is susceptible to a spoofing attack. Attackers can inject many RTCP packets into the group, each with a different SSRC. This will cause RTP participants to believe the group membership is much higher than it actually is. The result is that each participant will end up transmitting RTCP packets very infrequently, if ever. When SSRC sampling is used, the problem can be amplified if a participant is not applying a hash to the SSRC before matching them against their key. This is because an attacker can send many packets, each with different SSRC, that match the key. This would cause the group size to inflate exponentially. However, with a random hash applied, an attacker cannot guess those SSRC which will match against the key. In fact, an attacker will have to send 2**m different SSRC before finding one that matches, on average. Of course, the effect of a match causes an increase of group membership by 2**m. But, the use of sampling means that an attacker will have to send many packets before an effect can be observed.  Schulzrinne, H., Casner, S., Frederick, R. and V. Jacobson, "RTP: a transport protocol for real-time applications", RFC 1889, January 1996.  J. Rosenberg and H. Schulzrinne, "Timer reconsideration for enhanced RTP scalability", IEEE Infocom, (San Francisco, California), March/April 1998.
 International Telecommunication Union, "Visual telephone systems and equipment for local area networks which provide a non- guaranteed quality of service," Recommendation H.323, Telecommunication Standardization Sector of ITU, Geneva, Switzerland, May 1996.  Rivest, R., "The MD5 message-digest algorithm", RFC 1321, April 1992.  Rosenberg, J., "Protocols and Algorithms for Supporting Distributed Internet Telephony," PhD Thesis, Columbia University, Dec. 1999. Work in Progress.
Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.