[要約] RFC 2762は、RTPのグループメンバーシップのサンプリングに関する規格です。その目的は、RTPセッション内のグループメンバーシップの状態を定期的にサンプリングすることで、ネットワークの状態を監視し、適切なアクションを実行することです。
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
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.
Copyright（c）The Internet Society（2000）。無断転載を禁じます。
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.
大規模なマルチキャストグループでは、RTP（リアルタイムトランスポートプロトコル）の参加者が維持するグループメンバーシップテーブルのサイズは、特に限られたメモリおよび処理能力を備えた埋め込みデバイスでは扱いにくい場合があります。このドキュメントでは、メモリ要件を削減するために、このグループメンバーシップテーブルのサンプリングのメカニズムについて説明します。いくつかのメカニズムが提案されており、それぞれのパフォーマンスが考慮されます。
1 Introduction
1はじめに
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.
RTPは、リアルタイムトランスポートプロトコル[1]であり、RTCPパケットを各参加者からグループサイズにほぼ比例して送信することを義務付けています。グループサイズは、RTPおよびRTCPパケットで見られる各SSRCのエントリを含むテーブルを保存することによって取得されます。メンバーが出発またはタイムアウトすると、エントリが削除され、新しいメンバーが参加すると、エントリが追加されます。したがって、テーブルは非常に動的です。
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.
MBONEブロードキャストやIPベースのテレビ分配などの大規模なマルチキャストセッションの場合、グループサイズは非常に大きく、数十万人から数百万人の参加者が順に大きくなる可能性があります。これらの環境では、RTCPが常に使用されるとは限らないため、グループメンバーシップテーブルは必要ありません。ただし、RTPが適切でない場合にRTCPを「オフ」するという人間の介入なしに、1人のメンバーから100万人のメンバーを持つグループを持つグループのグループに対して、RTPが適切にスケーリングすることが非常に望ましいです。これは、同じツールとシステムを、スムーズでスケーラブルな方法で、小さな会議とテレビ放送の両方に使用できることを意味します。
Previous work [2] has identified three major scalability problems with RTP. These are:
以前の研究[2]は、RTPの3つの主要なスケーラビリティ問題を特定しました。これらは：
1. Congestion due to floods of RTCP packets in highly dynamic groups;
1. 非常に動的なグループにおけるRTCPパケットの洪水による混雑。
2. Large delays between receipt of RTCP packets from a single user;
2. 単一のユーザーからのRTCPパケットの受領の間の大きな遅延。
3. Large size of the group membership table.
3. グループメンバーシップテーブルの大きなサイズ。
The reconsideration algorithm [2] helps to alleviate the first of these. This document addresses the third, that of large group size tables.
再考アルゴリズム[2]は、これらの最初のものを軽減するのに役立ちます。このドキュメントでは、3番目のドキュメント、大規模なグループサイズテーブルの3番目に対応しています。
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.
たとえば、100万人のメンバーを持つSSRCテーブルの保管には、少なくとも4メガバイトが必要です。その結果、メモリ容量が小さい埋め込みデバイスは、これらの条件下で困難になる可能性があります。この問題を解決するために、SSRCサンプリングが提案されています。SSRCサンプリングは、統計サンプリングを使用して、グループメンバーシップの確率的推定値を取得します。これが行われたときに発生する多くの問題があります。このドキュメントは、これらの問題をレビューし、実装者が適用できるメカニズムについて説明します。特に、グループメンバーシップが異なるため、サンプリング確率を適応させるための3つの方法に焦点を当てています。IETFは、このドキュメントに含まれる仕様の一部またはすべて、特に3つのメカニズムのいずれかに関して主張されている知的財産権について通知されていることに注意することが重要です。詳細については、請求権のオンラインリストを参照してください。提示された他の2つのアプローチは、ビニングアルゴリズムよりも劣っていますが、IPRによって妨げられていないと考えられているため、含まれています。
2 Basic Operation
2基本操作
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.
SSRCサンプリングの背後にある基本的なアイデアは簡単です。各参加者は、32ビットのキーKと32ビットのマスクMを維持します。マスク内のビットのmが1で、残りがゼロであると仮定します。rtcpパケットがテーブルに配置するのではなく、いくつかのSSRCを使用して到着すると、最初にサンプリングされます。サンプリングは、キーとマスクのAnding、およびSSRCとマスクのAndingによって実行されます。結果の値が比較されます。等しい場合、SSRCはテーブルに保存されます。等しくない場合、SSRCは拒否され、パケットは受け取ったことがないかのように扱われます。
The key can be anything, but is usually derived from the SSRC of the user who is performing the sampling.
キーは何でもできますが、通常、サンプリングを実行しているユーザーのSSRCから派生します。
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.
*演算子が表現し、==演算子が平等のテストを示します。dはサンプリングの決定を表します。
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.
RTP仕様によると、セッション参加者が使用するSSRCはランダムに選択されます。分布も均一な場合、上記のフィルタリングにより2 ** m SSRCのうち1がテーブルに配置されることがわかります。ここで、Mはマスクのビット数、M、1つです。したがって、サンプリング確率pは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を掛けます。
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.
マスクで1に設定するビットを選択するときは、注意する必要があります。RTP仕様はSSRCをランダムに選択したことを義務付けていますが、これに準拠していない多くの既知の実装があります。特に、ITU H.323 [3]の一連の推奨事項により、中央制御要素であるゲートキーパーは、SSRCの最も重要な8ビットを割り当てることができますが、最も重要なものはRTP参加者によってランダムに選択されます。
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.
この問題を処理する最も安全な方法は、MD5 [4]などの暗号化されたハッシュを使用してSSRCを最初にハッシュし、上記の計算で使用したSSRCとして結果のビットの32を選択することです。これにより、はるかに優れたランダム性が提供され、さまざまな実装が実際にSSRCをどのように設定するかについての詳細な知識は必要ありません。
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:
推定値は、Mの値が減少するにつれてより正確で、増加するにつれて精度が低くなります。これは分析的に実証できます。実際のグループサイズがgの場合、標準偏差と推定値の平均（変動係数）の比は次のとおりです。
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 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:
この方程式は、以下で説明するように、サンプリング係数を変更する時期のしきい値を選択するためのガイドとして使用できます。たとえば、ターゲットが平均する1％の標準偏差である場合、サンプリング確率p = 2 ** -Mは、1万人のグループメンバーがいる場合、.5よりも小さくなければなりません。より一般的には、Tの平均比との目的の標準偏差を達成するには、サンプリング確率は次のとおりです。
p > 1 / (1 + G*(T**2))
3 Increasing the Sampling Probability
3サンプリング確率を増やします
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.
上記の単純なサンプリング手順は、グループサイズが静的であれば正常に動作します。しかし、そうではありません。RTPセッションに参加する参加者は、最初に1人の参加者（それ自体）のみが表示されます。パケットが受信されると、その参加者が見ているグループサイズが増加します。これを処理するには、サンプリング確率を動的にする必要があり、グループサイズが異なるにつれて増加および減少する必要があります。
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.
サンプリング確率を増やす手順は簡単です。参加者は、m = 0のマスクから始めます。これらの条件下では、受信したすべてのSSRCがテーブルに保存されるため、サンプリングは事実上ありません。ある時点で、mの値は1つ増加します。これは、既にテーブル内にあるSSRCの約半分が、マスキング操作の下でキーと一致しなくなったことを意味します。正しい推定値を維持するために、これらのSSRCはテーブルから破棄する必要があります。新しいSSRCは、新しいマスクの下のキーと一致する場合にのみ追加されます。
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.
マスク内のビット数をいつ増やすかについての決定も簡単です。RTP参加者がテーブルにCエントリを保存するのに十分な容量を持つメモリがあるとしましょう。グループの最良の推定値は、最大のサンプリング確率によって取得されます。これはまた、テーブルがより充実しているほど最良の見積もりが得られることを意味します。したがって、合理的なアプローチは、テーブルがCに満たされるのと同じように、マスク内のビット数を増やすことです。これにより、一般に、その内容は平均して半分に減少します。テーブルが再び満たされると、マスク内のビット数がさらに増加します。
4 Reducing the Sampling Probability
4サンプリング確率の削減
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.
グループサイズが減少し始めた場合、マスク内の1ビット数を減らす必要がある場合があります。そうしないと、グループサイズの推定が非常に低くなります。残念ながら、マスク内のビット数を減らすことは、それらを増やすよりも困難です。
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 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.
マスク内のビット数が増加すると、ユーザーは一致しなくなったSSRCを削除することで補償します。ビットの数が減少すると、ユーザーはSSRCが一致するユーザーを理論的に追加する必要があります。ただし、サンプリングの全体的なポイントはそれらを覚えておく必要がないため、これらのSSRCは不明です。したがって、マスク内のビット数がメンバーシップテーブルに変更されずに削減された場合、グループの推定値は即座に正確に半分に低下します。
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.
これを補うには、何らかのアルゴリズムが必要です。ここでは、2つのアプローチを示します。矯正因子ソリューションとビニングソリューションです。ビニングソリューションは、理解し、パフォーマンスを向上させるのが簡単です。ただし、完全性と比較のための矯正因子ソリューションの議論、およびIPRによって妨げられていないと考えられているためです。
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.
修正要因を伴うアイデアは、2つのアプローチのいずれかをとることです。1つ目では、グループサイズの推定値に是正係数が追加され、2番目では、グループサイズの推定値に修正因子を掛けます。どちらの場合も、目的はサンプルマスクの変化を補うことです。「ファディングされた」メンバーが最終的に学習され、実際にメンバーシップリストに配置されるため、修正因子は崩壊する必要があります。
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.
加法因子は、マスク内のビット数が減少し、0に減少する前後のグループサイズの推定値の差から始まります（これは、正しい因子をさらに複雑にすることができるため、グループサイズの推定値の半分ではありません。以下を参照してください。）。乗法矯正因子は2から始まり、徐々に1に減衰します。どちらの要因もCL（TS-）の時代に減衰します。ここで、Cは平均RTCPパケットサイズをRTCP帯域幅でレシーバーの帯域幅で割ったものであり、L（TS-）は、ビット数の変更の直前にグループサイズの推定値です。時間tsのマスク。この定数の理由は次のとおりです。実際のグループメンバーシップが変更されていない場合、忘れられたメンバーはまだRTCPパケットを送信します。それぞれからRTCPパケットを聞くのにかかる時間は、平均RTCP間隔であり、CL（TS-）です。したがって、マスクの変更からCL（TS-）秒までに、修正因子によってファディングされたユーザーはパケットを送信してテーブルに表示されるはずです。両方の関数を直線的に減衰させることを選択しました。これは、RTCPパケットの到着率が線形であるためです。
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:
以前の是正因子が失効する前に、マスク内のビット数が再び減少した場合はどうなりますか？その場合、さらに別の要因を使用して因子を悪化させます。fi（）は、ith添加剤補正関数を表し、gi（）をith乗算補正関数を表します。TSがマスク内のビット数が減少する時間である場合、添加剤補正係数を次のように説明できます。
/ 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.
これらの方程式では、l（t）は、新しい因子を除く是正因子を含めて得られたグループサイズの推定値を示すことに注意してください。TS-は、ビット数が減少する直前の時間であり、その後の時間です。その結果、L（TS-）は、削減前のグループサイズの推定値を表し、L（TS）は直後の推定値を表しますが、新しい要因は含まれません。
Finally, the actual group size estimate L(t) is given by:
最後に、実際のグループサイズの推定値l（t）は次のように与えられます。
-----
\
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.
シミュレーションは、両方のアルゴリズムが同様にうまく機能することを示しましたが、グループメンバーシップが急速に減少しているとき、両方ともグループサイズを深刻に過小評価する傾向がありました[5]。これは、以下のパフォーマンスデータで実証されています。
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.
例として、加法因子の計算を検討してください。グループサイズは1000、Cは1秒、Mは2です。このサイズのマスクを使用すると、参加者は平均して250人（n = 250）のユーザーを観察します。t = 0で、ユーザーはマスク内のビット数を1に減らすことを決定します。その結果、L（0-）は1000であり、L（0）は500です。したがって、加算係数は500から始まり、減衰TS CL（TS-）= 1000でゼロになります。時間500では、Nが375に増加したと仮定します（これは、実際のグループサイズが変更されていない場合に平均します）。時間500で、添加係係数は250です。これは2 ** m回Nに追加されます。これは750です。これにより、グループサイズの推定値は1000になります。現在、ユーザーはマスクのビット数を再び減らすことを決定します。そのため、m = 0。別の加算係数が計算されます。この因子は、l（ts-）（1000）、minus l（ts）で始まります。L（TS）は、新しい要因なしで計算されます。これは、この時点（250）と2 ** m（1）倍N（375）での最初の添加因子です。これは625です。その結果、新しい追加因子は1000-625（375）から始まり、1000秒で0に減少します。
In order to more correctly estimate the group size even when it is rapidly decreasing, a binning algorithm can be used. The algorithm works as follows. There are 32 bins, 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 is placed in the mth bin (where m is the number of ones in the mask) otherwise it is discarded.
グループサイズが急速に減少している場合でも、グループサイズをより正しく推定するために、ビニングアルゴリズムを使用できます。アルゴリズムは次のように機能します。サンプルマスクのビット数と同じ32個のビンがあります。SSRCがマスキング操作の下でキーと一致する新しいユーザーからRTCPパケットが到着すると、MTHビン（Mはマスク内の数）に配置されます。
When the number of bits in the mask is to be increased, those members in the bin who still match after the new mask are moved into the next higher bin. Those who don't match are discarded. When the number of bits in the mask is to be decreased, nothing is done. Users in the various bins stay where they are. However, when an RTCP packet for a user shows up, and the user is in a bin with a higher value than the current number of bits in the mask, it is moved into the bin corresponding to the current number of bits in the mask. Finally, the group size estimate L(t) is obtained by:
マスク内のビットの数が増えると、新しいマスクが次の高ビンに移動した後もまだ一致するビンのメンバー。一致しない人は捨てられます。マスク内のビット数が減少する場合、何も行われません。さまざまなビンのユーザーは、彼らがいる場所にとどまります。ただし、ユーザーのRTCPパケットが表示され、ユーザーがマスク内の現在のビット数よりも高い値のビンにいると、マスク内の現在のビット数に対応するビンに移動します。最後に、グループサイズの推定値l（t）は次のように取得されます。
31
----
\
L(t) = / B(i) * 2**i
----
i=0
Where B(i) are the number of users in the ith bin.
ここで、B（i）はITHビンのユーザーの数です。
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.
アルゴリズムは、マスクのビット数が低下したときに基本的に古い見積もりを維持することで機能します。ユーザーが到着すると、徐々に下部ビンに移動し、より高いビンが総推定値に寄与する量を減らします。ただし、古い見積もりは、より高いビンからタイムアウトが削除され、さようならパケットを送信するユーザーも高いビンから削除されるという意味でまだ更新されます。これにより、古い見積もりがまだ適応し、徐々に段階的に段階的になります。この適応は、修正アルゴリズムよりもはるかに優れたパフォーマンスを発揮します。アルゴリズムも非常に簡単です。
The algorithms are all 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 implement an SSRC sampling algorithm, unconditional forward reconsideration and BYE reconsideration. The table depicts the group size estimate from time 20,000 to time 25,000 as seen by the single user present throughout the entire session. In the simulation, a memory size of 1000 SSRC was assumed. The performance without sampling, and with sampling with the additive, multiplicative, and bin-based correction are depicted.
アルゴリズムはすべて、表1のシミュレーションを介して比較されます。シミュレーションでは、10,001人のユーザーがt = 0のグループに参加します。t = 10,000で、そのうち5000が去ります。T = 20,000では、さらに5000の休暇があります。すべてがSSRCサンプリングアルゴリズム、無条件の前方再考、およびさようなら再検討を実装します。この表は、セッション全体に存在する単一のユーザーが見たように、時間20,000から25,000までのグループサイズの推定値を示しています。シミュレーションでは、1000 SSRCのメモリサイズが想定されました。サンプリングなし、および加法、乗法、およびビンベースの補正を使用したサンプリングを伴うパフォーマンスが描かれています。
As the table shows, the bin based algorithm performs particularly well at capturing the group size estimate towards the tail end of the simulation.
表が示すように、BINベースのアルゴリズムは、シミュレーションのテールエンドに向けてグループサイズの推定値をキャプチャするのに特にうまく機能します。
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
Care must be taken in handling senders when 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 be "counted" as part of the general group membership. If they are counted as part of the general group membership, and are not sampled, the group size estimate will be inflated to overemphasize the senders.
SSRCサンプリングを使用する際には、送信者の取り扱いに注意する必要があります。送信者の数は一般的に少なく、RTCP間隔の計算に大きく貢献するため、サンプリングを適用しないでください。ただし、それらは別のテーブルに保管する必要があり、一般的なグループメンバーシップの一部として「カウント」される必要はありません。それらが一般的なグループメンバーシップの一部としてカウントされ、サンプリングされていない場合、送信者を強調するためにグループサイズの推定値が膨らみます。
This is easily demonstrated 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 2**m times the number of entries in the table. Therefore, the group size estimate becomes:
これは分析的に簡単に実証されます。NSを送信者の数とし、NRを受信機の数とします。メンバーシップテーブルには、すべてのNS送信者とレシーバーの（1/2）** mが含まれます。現在のメモの総グループサイズ推定値は、テーブル内のエントリの数の2 ** m倍で取得されます。したがって、グループサイズの推定値は次のとおりです。
L(t) = (2**m) Ns + Nr
which exponentially weights the senders.
これは、送信者に指数関数的に重み付けされます。
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.
これは、ビニングアルゴリズムで簡単に補償されます。送信者は常に0番目のビンに配置されます。送信者がレシーバーになると、SSRCがマスクされた比較操作の下でキーと一致する場合、Mの現在の値に対応するビンに移動します。
5 Security Considerations
5つのセキュリティ上の考慮事項
The use of SSRC sampling does not 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.
SSRCサンプリングの使用は、[1]に記載されているものを超えて追加のセキュリティ上の考慮事項を導入するようには見えません。実際、上記のように、SSRCサンプリングは、特定の攻撃の効果を減らすのに多少役立ちます。
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.
RTPは、RTCPパケットの認証なしで使用される場合、スプーフィング攻撃の影響を受けやすくなります。攻撃者は、それぞれ異なるSSRCを持つグループに多くのRTCPパケットを注入できます。これにより、RTPの参加者は、グループメンバーシップが実際よりもはるかに高いと信じるようになります。その結果、各参加者はRTCPパケットを非常にまれに送信することになります。SSRCサンプリングを使用すると、参加者がキーと一致する前にSSRCにハッシュを適用していない場合、問題は増幅できます。これは、攻撃者がキーと一致するSSRCが異なる多くのパケットを送信できるためです。これにより、グループサイズが指数関数的に膨張します。ただし、ランダムなハッシュを適用すると、攻撃者はキーと一致するSSRCを推測できません。実際、攻撃者は平均して一致するものを見つける前に、2 ** mの異なるSSRCを送信する必要があります。もちろん、一致の効果により、グループメンバーシップが2 ** m増加します。ただし、サンプリングの使用は、攻撃者が効果を観察する前に多くのパケットを送信する必要があることを意味します。
6 Acknowledgements
6謝辞
The authors wish to thank Bill Fenner and Vern Paxson for their comments.
著者は、Bill FennerとVern Paxsonのコメントに感謝したいと考えています。
7 Bibliography
7書誌
[1] Schulzrinne, H., Casner, S., Frederick, R. and V. Jacobson, "RTP: a transport protocol for real-time applications", RFC 1889, January 1996.
[1] Schulzrinne、H.、Casner、S.、Frederick、R。and V. Jacobson、「RTP：リアルタイムアプリケーション用の輸送プロトコル」、RFC 1889、1996年1月。
[2] J. Rosenberg and H. Schulzrinne, "Timer reconsideration for enhanced RTP scalability", IEEE Infocom, (San Francisco, California), March/April 1998.
[2] J. RosenbergとH. Schulzrinne、「RTPスケーラビリティの向上に対するタイマーの再考」、IEEE Infocom（カリフォルニア州サンフランシスコ）、1998年3月/4月。
[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.
[3] 国際電気通信ユニオン、「保証されていないサービス品質を提供するローカルエリアネットワーク向けの視覚電話システムと機器」、推奨H.323、1996年5月、スイス、ジュネーブのITUの電気通信標準化セクター。
[4] Rivest, R., "The MD5 message-digest algorithm", RFC 1321, April 1992.
[4] Rivest、R。、「The Md5 Message-Digest Algorithm」、RFC 1321、1992年4月。
[5] Rosenberg, J., "Protocols and Algorithms for Supporting Distributed Internet Telephony," PhD Thesis, Columbia University, Dec. 1999. Work in Progress.
[5] Rosenberg、J。、「分散インターネットテレフォニーをサポートするためのプロトコルとアルゴリズム」、博士論文、コロンビア大学、1999年12月。
8 Authors' Addresses
8著者の住所
Jonathan Rosenberg dynamicsoft 200 Executive Drive West Orange, NJ 07052 USA
Jonathan Rosenberg Dynamicsoft 200エグゼクティブドライブウェストオレンジ、ニュージャージー07052 USA
EMail: jdrosen@dynamicsoft.com
Henning Schulzrinne Columbia University M/S 0401 1214 Amsterdam Ave. New York, NY 10027-7003 USA
ヘニングシュルツリンヌコロンビア大学M/S 0401 1214 AMSTERDAM AVE. NEW YORK、NY 10027-7003 USA
EMail: schulzrinne@cs.columbia.edu
9 Full Copyright Statement
9完全な著作権声明
Copyright (C) The Internet Society (2000). All Rights Reserved.
Copyright（c）The Internet Society（2000）。無断転載を禁じます。
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.
RFCエディター機能の資金は現在、インターネット協会によって提供されています。