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.
このメモはインターネットコミュニティのためにExperimentalプロトコルを定義します。それはどんな種類のインターネット標準を指定しません。改善のための議論や提案が要求されています。このメモの配布は無制限です。
Copyright Notice
著作権表示
Copyright (C) The Internet Society (2000). All Rights Reserved.
著作権（C）インターネット協会（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ベースのTV配信のような大きなマルチキャストセッションについては、グループの大きさは、参加者の何百万人に数十万人のために、非常に大きくなることがあります。これらの環境では、RTCPは、常に使用することはできませんので、グループメンバーシップテーブルは必要ありません。 RTPは、1万人の会員を持つグループへの一つのメンバーを持つグループのためによくスケールするためにしかし、それはもはや適切なときRTCP「をオフにしない」ための人間の介入なしに、非常に望ましいです。これは、同じツールやシステムがスムーズに、スケーラブルな方法で小さな会議やテレビ放送の両方に使用できることを意味します。
Previous work [2] has identified three major scalability problems with RTP. These are:
以前の研究は、[2] RTPとの三の大スケーラビリティの問題を特定しました。これらは：
The reconsideration algorithm [2] helps to alleviate the first of these. This document addresses the third, that of large group size tables.
再考アルゴリズム[2]はこれらの最初のを軽減するのに役立ちます。この文書では、大規模なグループサイズのテーブルのことを第三に対処しています。
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.
百万メンバーとSSRCテーブルのストレージは、例えば、少なくとも4メガバイトが必要です。その結果、少ないメモリ容量を持つ組み込みデバイスは、これらの条件の下で困難を有することができます。この問題を解決するために、SSRCのサンプリングが提案されています。 SSRCサンプリングは、グループメンバーシップの確率的推定値を得るために、統計的サンプリングを使用しています。これが行われるときに発生する多くの問題があります。この文書では、これらの問題を検討し、実装によって塗布することができるメカニズムについて説明します。特に、グループメンバーシップが変化するサンプリング確率を適応させるための三つの方法に焦点を当てています。 IETFは、この文書に含まれる仕様の一部またはすべてについて記載知的財産権を通知されたことに注目することが重要であり、3つのメカニズムの一つに、特に：下記のビニングアルゴリズム。詳細については、要求された権利のオンラインリストを参照してください。提示他の二つのアプローチがビニングアルゴリズムに劣っているが、それらは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 Sで到着すると、それが最初にサンプリングされます。サンプリングは論理積によって、キーとマスク、および論理積SSRC及びマスクを行います。得られた値が比較されます。等しい場合、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)
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のは、ランダムに選択されています。分布も均一である場合、上記フィルタリングは、mは1であるマスクのビット、Mの数であるテーブル内に配置される2のうち1 ** M SSRCのを引き起こすであろうことを確認することは容易です。 M - したがって、サンプリング確率pが2 **です。
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
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を選択したが、これに準拠していない多くの既知の実装があります。最も重要な、ランダムRTP参加者によって選択されている間、特に、お薦めのITU H.323 [3]シリーズは、中央制御要素、ゲートキーパー、SSRCの最下位8ビットを割り当てることを可能にします。
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.
この問題を処理するための最も安全な方法は、第1のハッシュにSSRCは、上記の計算に使用される[4]、及びその結果のビット32を選択例えばMD5等の暗号的に安全なハッシュを使用してSSRC、です。これは、はるかに優れたランダム性を提供し、様々な実装が実際に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である場合、推定値L（変動係数）の平均値に対する標準偏差の比です。
sqrt((2**m - 1)/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万グループメンバーが存在する場合に0.5よりも小さくてはなりません。より一般的には、Tの比率を意味する所望の標準偏差を達成するために、サンプリング確率が以上であってはなりません。
p > 1 / (1 + G*(T**2))
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セッションに参加する参加者は、最初はただ一人の参加者（自分自身）が表示されます。パケットが受信されると、その参加者から見たグループのサイズが大きくなります。これに対処するには、サンプリング確率を動的に行う必要があり、グループの大きさが変わるので増減する必要があります。
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つの方法のいずれかを取ることです。最初に、補正係数は、グループサイズ推定値に加算され、そして第二に、グループサイズの推定値は、補正係数が乗算されます。両方の場合において、目的は、試料マスクの変化を補償することです。 「fudged」のメンバーは、最終的に学びましたし、実際にメンバーシップのリストに配置されているよう是正要因が崩壊しなければなりません。
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に減衰します。 cは受信機のためのRTCP帯域幅で割った平均RTCPパケットサイズであり、そしてL（TS-が）だけのビット数の変更前のグループサイズの推定値であるCL（TS-）の時、上因子減衰の両方時間tsのマスク。次のようにこの定数の理由はあります。実際のグループメンバーシップが変更されていない場合は、忘れたそれらのメンバーはまだRTCPパケットを送信します。それが彼らのそれぞれからのRTCPパケットを聞くためにかかる時間の量は、CL（TS-）で平均RTCP間隔、です。したがって、CLで（TS-）秒マスクの変更後、是正要因によりfudgedたそれらのユーザーはパケットを送信しているはずですので、テーブルに表示されます。私たちは、直線的に両方の機能を減衰することを選びました。 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の（）は、i番目の加算補正機能、及びGI（）は、i番目乗法補正関数を表します。 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-は右ビットの数の減少、および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であり、そして時間500において、時刻tsにおけるゼロ+ CL（TS-）= 1000まで減衰、Nは、（実際のグループのサイズが変更されていない場合、これは、平均して、ケースになる）375に増加していると仮定することができます。時間500において、添加率が250がこれは1000今のグループサイズの見積もりが得られ、750でN、M倍** 2に追加されると、ユーザは、再度マスクのビット数を削減することを決定しますその結果、m = 0です。他の添加物率が計算されます。この因子は、L（1000）（TS-）で始まり、マイナスL（TS +）。 L（TS +）は、新たな因子なしで計算されます。それは、この時間（250）プラス2 ** M（1）回N（375）における第1の添加因子です。これは結果として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個のビンがあります。新しいユーザからのRTCPパケットは、そのSSRCマスキング演算下キーと一致した到着すると、それはそうでなければ廃棄される（mは、マスク内の1の数である）、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:
マスクのビット数を増加させる場合には、まだ新しいマスクをした後、一致binにそれらのメンバーは次の上位のビンに移動されます。一致していない人は破棄されます。マスク内のビット数が減少する場合、何もしません。彼らがどこにあるさまざまなビンのユーザーがご利用いただけます。ユーザのための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）はi番目のビン内のユーザー数はどこにあります。
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.
このアルゴリズムは、マスクのビット数が低下した場合、基本的に古い推定値を維持することによって動作します。ユーザーが到着すると、それらは徐々に高くビンは、合計推定に寄与する量を減少させる、より低いビンに移動されます。しかし、昔の推定値は、まだタイムアウトし、ユーザーが高いビンから除去され、BYEパケットを送信し、ユーザーはまた、より高いビンから削除されているという意味で更新されます。これは、徐々にそれを段階的に廃止しながら、古い見積もりはまだ、適応することができます。それは、是正のアルゴリズムよりもはるかに優れて行います。この適応したものです。アルゴリズムはまた、非常に簡単です。
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に、シミュレーションを介して比較され、10001人のユーザがt = 0でグループに参加します。それらのトン= 10,000 5000のままにしておきます。トン= 20,000別の5000休暇で。すべてのSSRCサンプリングアルゴリズム、無条件前方再考とBYEの見直しを実施。表は、セッション全体を通して存在する単一のユーザによって見られるように、時刻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.
表が示すように、ビンに基づくアルゴリズムは、シミュレーションの最後尾に向かってグループサイズ推定値を捕捉するのに特に良好に機能します。
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）**メートルが含まれています。現在のメモの総グループサイズ推定値は、テーブル内のエントリの2 ** m倍数によって得られます。したがって、グループサイズの見積もりは次のようになります。
L(t) = (2**m) Ns + Nr
L（T）=（2 ** m）のN S個の+ 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 **は異なるSSRC mは送信する必要があります。もちろん、マッチの効果は、2 ** Mによるグループメンバーシップの増加を引き起こします。しかし、サンプリングを使用すると、攻撃者が影響を観察することができる前に多くのパケットを送信しなければならないことを意味します。
6 Acknowledgements
6つの謝辞
The authors wish to thank Bill Fenner and Vern Paxson for their comments.
作者は彼らのコメントのためにビルフェナーとバーン・パクソンに感謝したいです。
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.、フレデリック、R.と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.ローゼンバーグとH. Schulzrinneと、 "強化RTPスケーラビリティのためのタイマーの見直し"、IEEEインフォコム、（サンフランシスコ、カリフォルニア州）3月/ 1998年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、ITU、ジュネーブ、スイス、1996年5月の電気通信標準化部門。
[4] Rivest, R., "The MD5 message-digest algorithm", RFC 1321, April 1992.
[4]リベスト、R.、RFC 1321、1992年4月 "MD5アルゴリズムをメッセージダイジェスト"。
[5] Rosenberg, J., "Protocols and Algorithms for Supporting Distributed Internet Telephony," PhD Thesis, Columbia University, Dec. 1999. Work in Progress.
[5]ローゼンバーグ、J.、「プロトコルおよびアルゴリズム分散型インターネット電話、支援する」博士論文、コロンビア大学、進行中の12月、1999年の作業を。
8 Authors' Addresses
8本の著者のアドレス
Jonathan Rosenberg dynamicsoft 200 Executive Drive West Orange, NJ 07052 USA
ジョナサン・ローゼンバーグdynamicsoft 200エクゼクティブドライブウェストオレンジ、NJ 07052 USA
EMail: jdrosen@dynamicsoft.com
メールアドレス：jdrosen@dynamicsoft.com
Henning Schulzrinne Columbia University M/S 0401 1214 Amsterdam Ave. New York, NY 10027-7003 USA
ヘニングSchulzrinneとコロンビア大学のM / S 0401 1214アムステルダムアベニュー。ニューヨーク、NY 10027-7003 USA
EMail: schulzrinne@cs.columbia.edu
メールアドレス：schulzrinne@cs.columbia.edu
9 Full Copyright Statement
9完全な著作権声明
Copyright (C) The Internet Society (2000). All Rights Reserved.
著作権（C）インターネット協会（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 Editor機能のための基金は現在、インターネット協会によって提供されます。