rfc2762.txt

RFC 的详细文档！

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.

Abstract

   In 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 Introduction

   RTP, the Real Time Transport Protocol [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



Rosenberg & Schulzrinne       Experimental                      [Page 1]

RFC 2762                      RTP Sampling                 February 2000


   systems can be used for both small conferences and TV broadcasts in a
   smooth, scalable fashion.

   Previous work [2] 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 [2] 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.

2 Basic Operation

   The basic idea behind SSRC sampling is simple. Each participant
   maintains a key K of 32 bits, and a mask M of 32 bits. Assume that m
   of the bits in the mask are 1, and the remainder are zero. When an
   RTCP packet arrives with some SSRC S, rather than placing it in the
   table, it is first sampled. The sampling is performed by ANDing the
   key and the mask, and also ANDing the SSRC and the mask. The
   resulting values are compared. If equal, the SSRC is stored in the
   table. If not equal, the SSRC is rejected, and the packet is treated
   as if it has never been received.

   The key can be anything, but is usually derived from the SSRC of the
   user who is performing the sampling.




Rosenberg & Schulzrinne       Experimental                      [Page 2]

RFC 2762                      RTP Sampling                 February 2000


   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 [3] 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 [4], 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.

2.1 Performance

   The estimate is more accurate as the value of m decreases, less
   accurate as it increases. This can be demonstrated analytically. If
   the actual group size is G, the ratio of the standard deviation to
   mean of the estimate L (coefficient of variation) is:

   sqrt((2**m - 1)/G)

   This equation can be used as a guide for selecting the thresholds for
   when to change the sampling factor, as discussed below. For example,
   if the target is a 1% standard deviation to mean, the sampling






Rosenberg & Schulzrinne       Experimental                      [Page 3]

RFC 2762                      RTP Sampling                 February 2000


   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))

3 Increasing the Sampling Probability

   The above simple sampling procedure would work fine if the group size
   was static. However, it is not. A participant joining an RTP session
   will initially see just one participant (themselves). As packets are
   received, the group size as seen by that participant will increase.
   To handle this, the sampling probability must be made dynamic, and
   will need to increase and decrease as group sizes vary.

   The procedure for increasing the sampling probability is easy. A
   participant starts with a mask with m=0. Under these conditions,
   every received SSRC will be stored in the table, so there is
   effectively no sampling. At some point, the value of m is increased
   by one. This implies that approximately half of the SSRC already in
   the table will no longer match the key under the masking operation.
   In order to maintain a correct estimate, these SSRC must be discarded
   from the table. New SSRC are only added if they match the key under
   the new mask.

   The decision about when to increase the number of bits in the mask is
   also simple. Let's say an RTP participant has a memory with enough
   capacity to store C entries in the table. The best estimate of the
   group is obtained by the largest sampling probability. This also
   means that the best estimate is obtained the fuller the table is. A
   reasonable approach is therefore to increase the number of bits in
   the mask just as the table fills to C. This will generally cause its
   contents to be reduced by half on average. Once the table fills
   again, the number of bits in the mask is further increased.

4 Reducing the Sampling Probability

   If the group size begins to decrease, it may be necessary to reduce
   the number of one bits in the mask. Not doing so will result in
   extremely poor estimates of the group size. Unfortunately, reducing
   the number of bits in the mask is more difficult than increasing
   them.

   When the number of bits in the mask increases, the user compensates
   by removing those SSRC which no longer match. When the number of bits
   decreases, the user should theoretically add back those users whose
   SSRC now match. However, these SSRC are not known, since the whole



Rosenberg & Schulzrinne       Experimental                      [Page 4]

RFC 2762                      RTP Sampling                 February 2000


   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.

4.1 Corrective Factors

   The idea with the corrective factors is to take one of two
   approaches. In the first, a corrective factor is added to the group
   size estimate, and in the second, the group size estimate is
   multiplied by a corrective factor. In both cases, the purpose is to
   compensate for the change in sample mask. The corrective factors
   should decay as the "fudged" members are eventually learned about and
   actually placed 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 is reduced,
   and decays to 0 (this is not always half the group size estimate, as
   the corrective factors can be compounded, see below). The
   multiplicative corrective factor starts at 2, and gradually decays to
   one. 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. The reason for this constant
   is as follows. In the case where the actual group membership has not
   changed, those members which were forgotten will still be sending
   RTCP packets. The amount of time it will take to hear an RTCP packet
   from each of them is the average RTCP interval, which is cL(ts-).
   Therefore, by cL(ts-) seconds after the change in the mask, those
   users who were fudged by the corrective factor should have sent a
   packet and thus appear in the table. We chose to decay both functions
   linearly. This is because the rate of arrival of RTCP packets is
   linear.

   What happens if the number of bits in the mask is reduced once again
   before the previous corrective factor has expired? In that case, we
   compound the factors by using 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, we can describe the additive correction factor as:




Rosenberg & Schulzrinne       Experimental                      [Page 5]

RFC 2762                      RTP Sampling                 February 2000


            / 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 [5]. This is demonstrated in the
   performance data below.



Rosenberg & Schulzrinne       Experimental                      [Page 6]