RFC 2762
Sampling of the Group Membership in RTP
RFC 2762: Sampling of the Group Membership in RTP 💖
okay bestie, RFC 2762 is an Experimental doc from the Network Working Group, dated February 2000. The authors are J. Rosenberg (dynamicsoft) and H. Schulzrinne (Columbia U.) 🎀 The memo is an experiment, not an Internet standard, and the header doesn't list anything it obsoletes or updates ✨
Status of This Memo
this memo defines an Experimental Protocol for the Internet community 🧪 it does not specify an Internet standard of any kind. the authors are asking for discussion and suggestions for improvement, and the memo can be distributed freely with no limits 🦋
Copyright Notice
Copyright (C) The Internet Society (2000). All Rights Reserved. 💜
Abstract
okay so picture a massive multicast group where the table tracking every member of the group (RTP: Real Time Transport Protocol) gets absolutely huge 😭 that's a real problem for tiny embedded devices with not much memory or processing power. this doc looks at ways to sample that membership table so it takes up less memory 💅 it proposes several mechanisms and looks at how well each one performs 🔥
1 Introduction ✨
RTP, the Real Time Transport Protocol [1], says that RTCP packets get sent from each participant on a period that's roughly proportional to the group size 🌸 to know the group size, you store a table with an entry for every unique SSRC seen in RTP and RTCP packets. when members leave or time out, their entries get deleted, and when new members join, entries get added. so the table is super dynamic, like, constantly changing 💀
big multicast sessions, like an mbone broadcast or IP-based TV distribution, can have group sizes that are absolutely massive, somewhere from hundreds of thousands to millions of participants 😳 in those settings RTCP might not always be used, so the membership table isn't needed. still, it's really desirable for RTP to scale nicely from groups with one member all the way up to groups with one million members, and to do that without a human having to "turn off" RTCP when it's no longer appropriate 🙈 that way the same tools and systems work for small conferences and TV broadcasts, smoothly and at any scale 🌈
previous work [2] found three big scalability problems with RTP:
- Congestion due to floods of RTCP packets in highly dynamic groups;
- Large delays between receipt of RTCP packets from a single user;
- Large size of the group membership table.
the reconsideration algorithm [2] helps with the first one 👑 this document is about the third one, the problem of large group size tables 🫶
a membership table with one million SSRCs, for example, needs at least four megabytes of storage. so embedded devices with small memory can really struggle in those conditions 😭 to fix that, people proposed SSRC sampling. SSRC sampling uses statistical sampling to get a stochastic estimate of the group membership 🦋 there are lots of issues that come with doing that. this document goes through those issues and talks about the mechanisms implementors can use 💖 in particular it focuses on three methods for adapting the sampling probability as the group membership changes. it's important to know that the IETF has been told about intellectual property rights claimed for some or all of the specification in this document, and specifically for one of the three mechanisms: the binning algorithm described below 🚨 for more info, check the online list of claimed rights. the two other approaches are considered inferior to the binning algorithm, but they're included because they're believed to be unencumbered by IPR 🍓
2 Basic Operation 🧚
okay so the core idea of SSRC sampling is honestly simple 💅 each participant keeps a 32 bit key K and a 32 bit mask M. say m of the bits in the mask are 1, and the rest are 0. when an RTCP packet arrives with some SSRC S, it doesn't go straight into the table. instead it gets sampled first. the sampling works by ANDing the key with the mask, and also ANDing the SSRC with the mask, and then comparing the two results. if they're equal, the SSRC gets stored in the table. if they're not equal, the SSRC is rejected, and the packet is treated as if it had never been received at all 🙈
the key can be anything, but it's usually derived from the SSRC of the user doing the sampling 🌸
the sampling process can be written mathematically like this:
D = (K*M == S*M)where the * operator means AND and the == operator tests for equality. D is the sampling decision ✨
according to the RTP specification, the SSRCs used by session participants are chosen randomly. if the distribution is also uniform, the filtering above ends up putting 1 out of 2m SSRCs in the table, where m is the number of bits in the mask M that are one 🎀 so the sampling probability p is 2-m 💜
to get an actual group size estimate, L, you multiply the number of entries in the table, N, by 2**m:
L = N * 2**mbe careful about which bits you set to 1 in the mask 👀 even though the RTP specification requires randomly chosen SSRCs, lots of known implementations don't follow that. for example, the ITU H.323 [3] series of recommendations lets the central control element, the gatekeeper, assign the least significant 8 bits of the SSRC, while the most significant bits are randomly chosen by RTP participants 💀
the safest fix is to first hash the SSRC with a cryptographically secure hash, such as MD5 [4], and then pick 32 of the bits in the result to use as the SSRC in the computation above 🔥 that gives much better randomness, and you don't need detailed knowledge of how different implementations actually set the SSRC 🫶
2.1 Performance 📈
the estimate gets more accurate as m decreases, and less accurate as m increases 🦋 you can show this analytically. if the actual group size is G, the ratio of the standard deviation to the mean of the estimate L (the coefficient of variation) is:
sqrt((2**m - 1)/G)this equation is a handy guide for picking the thresholds for when to change the sampling factor, which gets covered below 🧚 for example, if your target is a 1% standard deviation to mean, the sampling probability p=2**-m should be no smaller than .5 when there are ten thousand group members 💅 more generally, to get a desired standard deviation to mean ratio of T, the sampling probability should be no less than:
p > 1 / (1 + G*(T**2))3 Increasing the Sampling Probability 🌈
the simple sampling procedure above would work fine if the group size stayed static. but it doesn't stay static 😭 a participant joining an RTP session will initially see just one participant, themselves. as packets come in, the group size that participant sees will keep growing. so the sampling probability has to be dynamic, and it'll need to go up and down as group sizes change 💖
increasing the sampling probability is the easy part ✨ a participant starts with a mask where m=0. under those conditions every received SSRC gets stored in the table, so there's effectively no sampling. at some point, m gets increased by one. that means about half of the SSRCs already in the table won't match the key under the masking operation anymore. to keep the estimate correct, those SSRCs must be discarded from the table 🙈 and new SSRCs only get added if they match the key under the new mask 🎀
deciding when to increase the number of bits in the mask is also pretty straightforward 💅 say an RTP participant has enough memory to store C entries in the table. the best estimate of the group comes from the largest sampling probability. that also means the best estimate comes when the table is as full as possible 🔥 so a reasonable approach is to increase the number of bits in the mask just as the table fills up to C. that generally cuts its contents roughly in half on average. once the table fills up again, the number of bits in the mask gets increased again 🦋
4 Reducing the Sampling Probability 📉
if the group size starts to decrease, the number of one bits in the mask might need to go down too 👀 if you don't do that, the group size estimates end up being extremely poor 💀 unfortunately, reducing the number of bits in the mask is harder than increasing them 😭
when the number of bits in the mask increases, the user compensates by removing the SSRCs that no longer match 🧚 when the number of bits decreases, the user should theoretically add back the SSRCs that now match. but those SSRCs aren't known, because the whole point of sampling was to not have to remember them 🙈 so if the number of bits in the mask gets reduced without any changes to the membership table, the group estimate will instantly drop by exactly half 📉
to make up for that, 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 👑 but there's also a discussion of the corrective-factor solution, for completeness and for comparison, and also because it's believed to be unencumbered by IPR 🫶
4.1 Corrective Factors 💅✨
okay so the big idea with corrective factors is that there are two ways to fix the group size estimate. Option one: you add a corrective factor to the estimate. Option two: you multiply the estimate by a corrective factor. Either way, the goal is to make up for the change in sample mask 🎀 Also, these factors should decay as the "fudged" members eventually get learned about and actually land in the membership list 🦋
The additive factor starts at the difference between the group size estimate before and after the number of bits in the mask gets reduced. It then decays to 0. (Fun twist: this is not always half the group size estimate, because corrective factors can stack up, more on that below 👀) The multiplicative corrective factor starts at 2 and gradually decays to 1. Both factors decay over a time of cL(ts-), where c is the average RTCP packet size divided by the RTCP bandwidth for receivers, and L(ts-) is the group size estimate just before the change in the number of bits in the mask at time ts.
Why this constant though? 🤔 Picture this: the actual group membership hasn't changed, so the people who got forgotten are still sending RTCP packets. The amount of time it takes to hear one RTCP packet from each of them is the average RTCP interval, which is cL(ts-). So by cL(ts-) seconds after the mask change, everyone who was fudged by the corrective factor should have sent a packet and shown up in the table. We decided to decay both functions linearly, because the rate at which RTCP packets arrive is linear too. ✨
Now, what happens if the number of bits in the mask gets reduced again before the previous corrective factor has expired? 😭 Then we compound the factors by adding yet another one. Let fi() represent the ith additive correction function, and gi() the ith multiplicative correction function. If ts is the time when the number of bits in the mask is reduced, the additive correction factor looks like this:
/ 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 looks like this:
/ 1 , t < ts
|
| ts + 2cL(ts-) - t
gi(t) | ----------------- , ts < t < ts + cL(ts-)
| cL(ts-)
|
\ 1 , t > ts + cL(ts-)Quick note on the notation 🧚 In these equations, L(t) means the group size estimate including the corrective factors, except for the new factor. ts- is the time right before the reduction in the number of bits, and ts+ is the time right after. So L(ts-) is the estimate before the reduction, and L(ts+) is the estimate right after, still not including the new factor.
Finally, the actual group size estimate L(t) is given by the following. For the additive factor:
-----
\
L(t) = / fi(t) + N*(2**m)
-----
iand for the multiplicative factor:
------
| |
| |
L(t)= | | N*(2**m)*gi(t)Simulations showed that both algorithms performed equally well, but both tended to seriously underestimate the group size when the group membership was rapidly declining [5]. You'll see that in the performance data below 📉💀
Let's do an example with the additive factor, because it's so good 🍓 The group size is 1000, c is 1 second, and m is two. With a mask this size, a participant will, on average, observe 250 users (N = 250). At t=0, the user decides to reduce the number of bits in the mask to 1. So 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, let's assume N has increased to 375 (this will, on average, be the case if the actual group size hasn't changed). At time 500, the additive factor is 250. That gets added to 2**m times N, which is 750, giving 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 gets computed. This one starts at L(ts-) (which is 1000) minus L(ts+). And L(ts+) is computed without the new factor: it's the first additive factor at this time (250) plus 2**m (1) times N (375), which comes out to 625. So the new additive factor starts at 1000 - 625 (375), and decays to 0 in 1000 seconds. Stacking is real, bestie 👑
4.2 Binning Algorithm 🗂️🌈
To estimate the group size more correctly even when it's rapidly decreasing, you can use a binning algorithm. Here's how it works. There are 32 bins, the same as the number of bits in the sample mask. When an RTCP packet from a new user arrives whose SSRC matches the key under the masking operation, it gets placed in the mth bin (where m is the number of ones in the mask). Otherwise, it's discarded. 🙈
When the number of bits in the mask is going to be increased, the members in each bin who still match after the new mask get moved into the next higher bin. Those who don't match get discarded. When the number of bits in the mask is going to be decreased, nothing happens. Users in the various bins just stay where they are. However, when an RTCP packet for a user shows up and that user is in a bin with a higher value than the current number of bits in the mask, they get moved into the bin matching the current number of bits in the mask. Finally, the group size estimate L(t) is obtained by:
31
----
\
L(t) = / B(i) * 2**i
----
i=0Where B(i) is the number of users in the ith bin.
The vibe of this algorithm is basically "keep the old estimate when the number of bits in the mask drops." As users arrive, they gradually get moved into the lower bin, which shrinks how much the higher bin contributes to the total 📉 But the old estimate is still updated, in the sense that users who time out get removed from the higher bin, and users who send BYE packets also get removed from the higher bin. So the older estimate can keep adapting while being gradually phased out 🦋 That adaptation is why it performs way better than the corrective algorithms. Plus, it's extremely simple. Iconic 💖
4.3 Comparison 📊💅
All the algorithms are compared via simulation in Table 1. In the simulation, 10,001 users join a group at t=0. At t=10,000, 5000 of them leave. At t=20,000, another 5000 leave. All of them implement an SSRC sampling algorithm, unconditional forward reconsideration, and BYE reconsideration. The table shows the group size estimate from time 20,000 to time 25,000, as seen by the single user who stays present through the entire session. The simulation assumed a memory size of 1000 SSRC. The performance without sampling is shown, along with sampling using the additive, multiplicative, and bin-based corrections.
As the table shows, the bin-based algorithm is particularly good at capturing the group size estimate toward the tail end of the simulation 🌸
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 24.4 Sender Sampling 📣🎀
Care must be taken when handling senders while using SSRC sampling 💅 Since the number of senders is generally small, and they contribute significantly to the computation of the RTCP interval, sampling should not be applied to them. However, they must be kept in a separate table, and not "counted" as part of the general group membership. If they are counted as part of the general group membership and aren't sampled, the group size estimate gets inflated, overemphasizing the senders. 😤
This is easy to show analytically 🧮 Let Ns be the number of senders, and Nr be the number of receivers. The membership table will contain all Ns senders and (1/2)m of the receivers. The total group size estimate in the current memo is obtained by taking 2m times the number of entries in the table. So the group size estimate becomes:
L(t) = (2**m) Ns + Nrwhich exponentially weights the senders. Yikes 💀
Good news though: it's easy to compensate for this in the binning algorithm. A sender is always placed in the 0th bin. When a sender becomes a receiver, it's moved into the bin corresponding to the current value of m, if its SSRC matches the key under the masked comparison operation. ✨
5 Security Considerations 🔐🦋
The use of SSRC sampling doesn't appear to introduce any additional security considerations beyond those described in [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.
Here's where it gets dramatic 😭 When SSRC sampling is used, the problem can be amplified if a participant is not applying a hash to the SSRC before matching it against their key. This is because an attacker can send many packets, each with a different SSRC, that match the key. That would cause the group size to inflate exponentially. However, with a random hash applied, an attacker cannot guess which SSRC will match against the key. In fact, an attacker will have to send 2m different SSRC before finding one that matches, on average. Of course, a match causes an increase of group membership by 2m. But because of sampling, an attacker will have to send many packets before any effect can be observed 🙃
6 Acknowledgements 💜
The authors wish to thank Bill Fenner and Vern Paxson for their comments 🫶
7. Bibliography ✨
okay so this is the reading list 📚 bestie, and every single entry matters because the spec leans on them 🫶
- [1] Schulzrinne, H., Casner, S., Frederick, R. and V. Jacobson, "RTP: a transport protocol for real-time applications", RFC 1889, January 1996. 🎀
- [2] J. Rosenberg and H. Schulzrinne, "Timer reconsideration for enhanced RTP scalability", IEEE Infocom, (San Francisco, California), March/April 1998. 🦋
- [3] 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. 🌸
- [4] Rivest, R., "The MD5 message-digest algorithm", RFC 1321, April 1992. 🧚
- [5] Rosenberg, J., "Protocols and Algorithms for Supporting Distributed Internet Telephony," PhD Thesis, Columbia University, Dec. 1999. Work in Progress. 💜
8. Authors' Addresses 💅
Jonathan Rosenberg
dynamicsoft 200 Executive Drive West Orange, NJ 07052 USA
EMail: jdrosen@dynamicsoft.com
Henning Schulzrinne
Columbia University M/S 0401 1214 Amsterdam Ave. New York, NY 10027-7003 USA
EMail: schulzrinne@cs.columbia.edu
9. Full Copyright Statement ⭐
Copyright (C) The Internet Society (2000). 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.
Acknowledgement 🫶
Funding for the RFC Editor function is currently provided by the Internet Society.
📦 where this page comes from
- ietf: rfc2762 2000-02
- 💖 girlified by claude-haiku-5-5 on : a language model's rewrite of the original, under its terms