idnits 2.17.1 draft-ietf-avt-rtpsample-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == No 'Intended status' indicated for this document; assuming Proposed Standard == It seems as if not all pages are separated by form feeds - found 0 form feeds but 10 pages Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (May 25, 1999) is 9100 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Missing reference section? '1' on line 389 looks like a reference -- Missing reference section? '2' on line 393 looks like a reference -- Missing reference section? '3' on line 397 looks like a reference -- Missing reference section? '4' on line 402 looks like a reference Summary: 5 errors (**), 0 flaws (~~), 2 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet Engineering Task Force Audio/Video Transport wg 2 Internet Draft J. Rosenberg, H. Schulzrinne 3 draft-ietf-avt-rtpsample-04.txt Bell Laboratories/Columbia U. 4 May 25, 1999 5 Expires: November 1999 7 Sampling of the Group Membership in RTP 9 STATUS OF THIS MEMO 11 This document is an Internet-Draft and is in full conformance with 12 all provisions of Section 10 of RFC2026. 14 Internet-Drafts are working documents of the Internet Engineering 15 Task Force (IETF), its areas, and its working groups. Note that 16 other groups may also distribute working documents as Internet- 17 Drafts. 19 Internet-Drafts are draft documents valid for a maximum of six months 20 and may be updated, replaced, or obsoleted by other documents at any 21 time. It is inappropriate to use Internet- Drafts as reference 22 material or to cite them other than as work in progress. 24 The list of current Internet-Drafts can be accessed at 25 http://www.ietf.org/ietf/1id-abstracts.txt 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html. 30 The IETF has been notified of intellectual property rights claimed in 31 regard to some or all of the specification contained in this 32 document. For more information consult the online list of claimed 33 rights. 35 Abstract 37 In large multicast groups, the size of the group membership table 38 maintained by RTP (Real Time Transport Protocol) participants may 39 become unwieldy, particularly for embedded devices with limited 40 memory and processing power. This document discusses mechanisms for 41 sampling of this group membership table in order to reduce the memory 42 requirements. Several mechanisms are proposed, and the performance of 43 each is considered. 45 1 Introduction 46 RTP, the Real Time Transport protocol [1], mandates that RTCP packets 47 be transmitted from each participant with a period roughly 48 proportional to the group size. The group size is obtained by storing 49 a table, containing an entry for each unique SSRC seen in RTP and 50 RTCP packets. As members leave or time out, entries are deleted, and 51 as new members join, entries are added. The table is thus highly 52 dynamic. 54 For large multicast sessions, such as an mbone broadcast or IP based 55 TV distribution, group sizes can be extremely large, on the order of 56 hundreds of thousands to millions of participants. In these 57 environments, RTCP may not always be used, and thus the group 58 membership table isn't needed. However, it is highly desirable for 59 RTP to scale well for groups with one member to groups with one 60 million members, without human intervention to "turn off" RTCP when 61 its no longer appropriate. This means that the same tools and systems 62 can be used for both small conferences and TV broadcasts in a smooth, 63 scalable fashion. 65 Previous work [2] has identified three major scalability problems 66 with RTP. These are: 68 1. Congestion due to floods of RTCP packets in highly dynamic 69 groups 71 2. Large delays between receipt of RTCP packets from a single 72 user 74 3. Large size of the group membership table 76 The reconsideration algorithm helps to alleviate the first of these. 77 This document addresses the third, that of large group size tables. 79 Storage of an SSRC table with one million members, for example, 80 requires at least four megabytes. As a result, embedded devices with 81 small memory footprints may have difficulty under these conditions. 82 To solve this problem, SSRC sampling has been proposed. SSRC sampling 83 uses statistical sampling to obtain a stochastic estimate of the 84 group membership. There are many issues that arise when this is done. 85 This document reviews these issues and discusses the mechanisms which 86 can be applied by implementors. 88 2 Basic Operation 90 The basic idea behind SSRC sampling is simple. Each participant 91 maintains a key K of 32 bits, and a mask M of 32 bits. Assume that m 92 of the M bits in the mask are 1, and the remainder are zero. When an 93 RTCP packet arrives with some SSRC S, rather than placing it in the 94 table, it is first sampled. The sampling is performed by ANDing the 95 key and the mask, and also ANDing the SSRC and the mask. The 96 resulting values are compared. If equal, the SSRC is stored in the 97 table. If not equal, the SSRC is rejected, and the packet is treated 98 as if it were never received. 100 The key can be anything, but is usually chosen to be the SSRC of the 101 user who is performing the sampling. 103 This sampling process can be described mathematically as: 105 D = (K*M == S*M) 107 Where the * operator denotes AND and the = operator denotes a test 108 for equality. D represents the sampling decision. 110 According to the RTP specification, the SSRC's used by session 111 participants are chosen randomly. If the distribution is also 112 uniform, it is easy to see that the above filtering will cause 1 out 113 of 2**m SSRC's to be placed in the table, where m is the number of 114 bits in the mask, M, which are one. Thus, the sampling probability p 115 is 2**-m. 117 Then, to obtain an actual group size estimate, L, the number of 118 entries in the table N is multiplied by 2**m: 120 L = N * 2**m 122 Care must be taken when choosing which bits to set to 1 in the mask. 123 Although the RTP specification mandates randomly chosen SSRC, there 124 are many known implementations which do not conform to this. In 125 particular, the ITU H.323 [3] series of recommendations allows the 126 central control element, the gatekeeper, to assign the least 127 significant 8 bits of the SSRC, while the most significant are 128 randomly chosen by RTP participants. 130 The safest way to handle this problem is to first hash the SSRC using 131 a cryptographically secure hash, such as MD5 [4], and then choose 32 132 of the bits in the result as the SSRC used in the above computation. 133 This provides much better randomness, and doesn't require detailed 134 knowledge about how various implementations actually set the SSRC. 136 2.1 Performance 137 The estimate is more accurate as the value of m decreases, less 138 accurate as it increases. This can be demonstrated analytically. If 139 the actual group size is G, the standard deviation to mean of the 140 estimate L (coefficient of variation) is: 142 sqrt{(1 - 2**-m)/(2**-m * L} 144 This equation can be used as a guide for selecting the thresholds for 145 when to change the sampling factor, as discussed below. For example, 146 if the target is a 1% standard deviation to mean, the sampling 147 probability p==2**-m should be no smaller than .5 when there are ten 148 thousand group members. More generally, to achieve a desired standard 149 deviation to mean ration of T, the sampling probability should be no 150 less than: 152 p > 1 / (1 + G*(T**2)) 154 3 Increasing the Sampling Probability 156 The above simple sampling procedure would work fine if the group size 157 was static. However, it is not. A participant joining an RTP session 158 will initially see just one participant (themselves). As packets are 159 received, the group size as seen by that participant will increase. 160 To handle this, the sampling probability must be made dynamic, and 161 will need to increase and decrease as group sizes vary. 163 The procedure for increasing the sampling probability is easy. A 164 participant starts with a mask with m=0. Under these conditions, 165 every received SSRC will be stored in the table, so there is 166 effectively no sampling. At some point, the value of m is increased. 167 This implies that approximately half of the SSRC already in the table 168 will no longer match the key under the masking operation. In order to 169 maintain a correct estimate, these SSRC must be discarded from the 170 table. New SSRC are only added if they match the key under the new 171 mask. 173 The decision about when to increase the number of bits in the mask is 174 also simple. Lets say an RTP participant has a memory with enough 175 capacity to store C entries in the table. The best estimate of the 176 group is obtained by the largest sampling probability. This also 177 means that the best estimate is obtained the fuller the table is. A 178 reasonable approach is therefore to increase the number of bits in 179 the mask just as the table fills to C. This will generally cause its 180 contents to be reduced by half. Once the table fills again, the 181 number of bits in the mask is further increased. 183 4 Reducing the Sampling Probability 185 If the group size begins to decrease, it may be necessary to reduce 186 the number of bits in the mask. Not doing so will result in extremely 187 poor estimates of the group size. Unfortunately, reducing the number 188 of bits in the mask is more difficult than increasing them. 190 When the number of bits in the mask increases, the user compensates 191 by removing those SSRC which no longer match. When the number of bits 192 decreases, the user should theoretically add back those users whose 193 SSRC now match. However, these SSRC are not known, since the whole 194 point of sampling was to not have to remember them. Therefore, if the 195 number of bits in the mask is just reduced without any changes in the 196 membership table, the group estimate will instantly drop by exactly 197 half. 199 To compensate for this, some kind of algorithm is needed. Two 200 approaches are presented here: a corrective-factor solution, and a 201 binning solution. 203 4.1 Corrective Factors 205 The idea with the corrective factors is to add in or multiply the 206 group size estimate by some corrective factor to compensate for the 207 change in sample mask. The corrective factors should decay as the 208 "fudged" members are eventually learned about and actually placed in 209 the membership list. 211 The multiplicative factor starts at 2, and gradually decays to one. 212 The additive factor starts at the difference between the group size 213 estimate before and after the number of bits in the mask is reduced, 214 and decays to 0 (this is not always half the group size estimate, as 215 the corrective factors can be compounded, see below). Both factors 216 decay over a time of c*L(ts), where c is the average RTCP packet size 217 divided by the RTCP bandwidth for receivers, and L(ts) is the group 218 size estimate just before the change in the number of bits in the 219 mask at time ts. The reason for this constant is as follows. In the 220 case where the actual group membership has not changed, those members 221 which were forgotten will still be sending RTCP packets. The amount 222 of time it will take to hear an RTCP packet from each of them is the 223 average RTCP interval, which is cL(ts). Therefore, by cL(ts) seconds 224 after the change in the mask, those users who were fudged by the 225 corrective factor should have sent a packet and thus appear in the 226 table. We chose to decay both functions linearly. This is because the 227 rate of arrival of RTCP packets is linear. 229 What happens if the number of bits in the mask is reduced once again 230 before the previous corrective factor has expired? In that case, we 231 compound the factors by using yet another one. Let fi() represent the 232 ith correction function. If ts is the time when the number of bits in 233 the mask is reduced, we can describe the additive correction factor 234 as: 236 / 0 , t < ts 237 | ts + cL(ts-) - t 238 fi(t) = |( L(ts-) - L(ts+)) ---------------- ,ts ts + cL(ts-) 242 and the multiplicative factor as: 244 / 1 , t < ts 245 | 246 | ts + 2cL(ts-) - t 247 | ----------------- , ts < t < ts + cL(ts-) 248 | cL(ts-) 249 | 250 1 , t > ts + cL(ts-) 252 Note that in these equations, L(t) denotes the group size estimate 253 obtained including the corrective factors except for the new factor. 254 ts- is the time right before the reduction in the number of bits, and 255 ts+ the time after. As a result, L(ts-) represents the group size 256 estimate before the reduction, and L(ts+) the estimate right after, 257 but not including the new factor. 259 Finally, the actual group size estimate L(t) is given by: 261 ----- 263 L(t) = / fi(t) + N*(2**m) 264 ----- 265 i 267 for the additive factor, and: 269 ------ 270 | | 271 | | 272 L(t)= | | N*(2**m)*fi(t) 274 for the multiplicative factor. 276 Simulations showed that both algorithms performed equally well, but 277 both tended to seriously underestimate the group size when the group 278 membership was rapidly declining. This is demonstrated in the 279 performance data below. 281 4.2 Binning Algorithm 283 In order to more correctly estimate the group size even when it was 284 rapidly decreasing, a binning algorithm can be used. The algorithm 285 works as follows. There are 32 bins, same as the number of bits in 286 the sample mask. When an RTCP packet from a new user arrives whose 287 SSRC matches the key under the masking operation, it is placed in the 288 mth bin (where m is the number of ones in the mask) otherwise it is 289 discarded. 291 When the number of bits in the mask is to be increased, those members 292 in the bin who still match after the new mask are moved into the next 293 higher bin. Those who don't match are discarded. When the number of 294 bits in the mask is to be decreased, nothing is done. Users in the 295 various bins stay where they are. However, when an RTCP packet for a 296 user shows up, and the user is in a bin with a higher value than the 297 current number of bits in the mask, it is moved into the bin 298 corresponding to the current number of bits in the mask. Finally, the 299 group size estimate L(t) is obtained by: 301 31 302 ---- 304 L(t) = / B(i) * 2**i 305 ---- 306 i=0 308 Where B(i) are the number of users in the ith bin. 310 The algorithm works by basically keeping the old estimate when the 311 number of bits in the mask drops. As users arrive, they are gradually 312 moved into the lower bin, reducing the amount that the higher bin 313 contributes to the total estimate. However, the old estimate is still 314 updated in the sense that users which timeout are removed from the 315 higher bin, and users who send BYE packets are also removed from the 316 higher bin. This allows the older estimate to still adapt, while 317 gradually phasing it out. It is this adaptation which makes it 318 perform much better than the corrective algorithms. The algorithm is 319 also extremely simple. 321 4.3 Comparison 323 The algorithms are all compared via simulation in Table 1. In the 324 simulation, 10,001 users join a group at t=0. At t=10,000, 5000 of 325 them leave. At t=20,000, another 5000 leave. All implement an SSRC 326 sampling algorithm, unconditional forward and BYE reconsideration. 327 The table depicts the group size estimate from time 20,000 to time 328 25,000 as seen by the single user present throughout the entire 329 session. In the simulation, a memory size of 1000 SSRC was assumed. 330 The performance without sampling, and with sampling with the 331 additive, multiplicative, and bin-based correction are depicted. 333 As the table shows, the bin based algorithm performs particularly 334 well at capturing the group size estimate towards the tail end of the 335 simulation. 337 Time No Sampling Binned Additive Multiplicative 338 ---- ----------- ------ -------- -------------- 339 20000 5001 5024 5024 5024 340 20250 4379 4352 4352 4352 341 20500 3881 3888 3900 3853 342 20750 3420 3456 3508 3272 343 21000 3018 2992 3100 2701 344 21250 2677 2592 2724 2225 345 21500 2322 2272 2389 1783 346 21750 2034 2096 2125 1414 347 22000 1756 1760 1795 1007 348 22250 1476 1472 1459 582 349 22500 1243 1232 1135 230 350 22750 1047 1040 807 80 351 23000 856 864 468 59 352 23250 683 704 106 44 353 23500 535 512 32 32 354 23750 401 369 24 24 355 24000 290 257 17 17 356 24250 198 177 13 13 357 24500 119 129 11 11 358 24750 59 65 8 8 359 25000 18 1 2 2 361 4.4 Sender Sampling 363 Care must be taken in handling senders when using SSRC sampling. 364 Since the number of senders is generally small, and they contribute 365 significantly to the computation of the RTCP interval, sampling 366 should not be applied to them. However, they must be kept in a 367 separate table, and not be "counted" as part of the general group 368 membership. If this is done, the group size estimate will be inflated 369 to overemphasize the senders. 371 This is easily demonstrated analytically. Let Ns be the number of 372 senders, and Nr be the number of receivers. The membership table will 373 contain all Ns senders and (1/2)**m of the receivers. The total group 374 size estimate in the current draft is obtained by 2**m times the 375 number of entries in the table. Therefore, the group size estimate 376 becomes: 378 L(t) = (2**m) Ns + Nr 380 which exponentially weights the senders. 382 This is easily compensated for in the binning algorithm. A sender is 383 always placed in the 0th bin. When a sender becomes a receiver, it is 384 moved into the bin corresponding to the current value of m, if its 385 SSRC matches the key under the masked comparison operation. 387 5 Bibliography 389 [1] H. Schulzrinne, S. Casner, R. Frederick, and V. Jacobson, "RTP: a 390 transport protocol for real-time applications," Request for Comments 391 (Proposed Standard) 1889, Internet Engineering Task Force, Jan. 1996. 393 [2] J. Rosenberg and H. Schulzrinne, "Timer reconsideration for 394 enhanced RTP scalability," (San Francisco, California), March/April 395 1998. 397 [3] International Telecommunication Union, "Visual telephone systems 398 and equipment for local area networks which provide a non-guaranteed 399 quality of service," Recommendation H.323, Telecommunication 400 Standardization Sector of ITU, Geneva, Switzerland, May 1996. 402 [4] R. Rivest, "The MD5 message-digest algorithm," Request for 403 Comments (Informational) 1321, Internet Engineering Task Force, Apr. 404 1992. 406 6 Authors' Addresses 408 Jonathan Rosenberg 409 Bell Laboratories, Lucent Technologies 410 101 Crawfords Corner Rd. 411 Holmdel, NJ 07733 412 USA 413 Rm. 4C-526 414 email: jdrosen@bell-labs.com 416 Henning Schulzrinne 417 Columbia University 418 M/S 0401 419 1214 Amsterdam Ave. 420 New York, NY 10027-7003 421 USA 422 email: schulzrinne@cs.columbia.edu