RFC2762 日本語訳
2762 Sampling of the Group Membership in RTP. J. Rosenberg, H.Schulzrinne. February 2000. (Format: TXT=25796 bytes) (Status: EXPERIMENTAL)
プログラムでの自動翻訳です。
英語原文
Network Working Group J. Rosenberg Request for Comments: 2762 dynamicsoft Category: Experimental H. Schulzrinne Columbia U. February 2000
コメントを求めるワーキンググループJ.ローゼンバーグの要求をネットワークでつないでください: 2762dynamicsoft Category: 実験的なH.SchulzrinneコロンビアU.2000年2月
Sampling of the Group Membership in RTP
RTPのグループ会員資格の標本抽出
Status of this Memo
この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.
Copyright(C)インターネット協会(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.
大きいマルチキャストグループでは、RTP(本当のTime Transportプロトコル)でグループ会員資格テーブルのサイズは、関係者が限られたメモリと処理能力で特に組み込み機器に扱いにくくなるかもしれないと主張しました。 メモリ要件を減らして、このドキュメントはこのグループ会員資格テーブルの標本抽出のためにメカニズムについて議論します。 数個のメカニズムが提案されます、そして、それぞれの性能は考えられます。
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(レアルTime Transportプロトコル[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
mbone放送かIPベースのテレビの分配などの大きいマルチキャストセッションのために、グループサイズは非常に大きい場合があります、何百万人もの関係者への何十万の注文に関して。 これらの環境で、RTCPはいつも使用されるかもしれないというわけではありません、そして、その結果、グループ会員資格テーブルは必要ではありません。 しかしながら、RTPがグループのために1人のメンバーと共に100万人のメンバーでグループによく比例するのは、非常に望ましいです、それがもう適切でないときにRTCPを「オフにする」人間の介入なしで。 そしてこれがそんなに同じツールを意味する。
Rosenberg & Schulzrinne Experimental [Page 1] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[1ページ]RFC2762RTP
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:
前の仕事[2]は3つの重大なスケーラビリティ問題をRTPと同一視しました。 これらは以下の通りです。
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]は、これらの1番目を軽減するのを助けます。 このドキュメントは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つのメカニズムの1つに含まれた仕様いくつかかすべてに関して要求された知的所有権について通知されたことに注意するのは重要です: 以下で説明された捨てるアルゴリズム。 詳しい情報に関しては、要求された権利のオンラインリストに相談してください。 他のアプローチが提示した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 Sと共にそれをテーブルに置くよりむしろ到着するとき、それは最初に、抽出されます。 標本抽出はキーとマスクがANDingによって実行されて、また、ANDing SSRCとマスクを実行されます。 結果として起こる値は比較されます。 等しいなら、SSRCはテーブルに格納されます。 同輩でないなら、SSRCは拒絶されます、そして、パケットはまるでそれを一度も受け取ったことがないかのように扱われます。
The key can be anything, but is usually derived from the SSRC of the user who is performing the sampling.
キーを何かであることができますが、通常、標本抽出を実行しているユーザのSSRCから得ます。
Rosenberg & Schulzrinne Experimental [Page 2] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[2ページ]RFC2762RTP
This sampling process can be described mathematically as:
このサンプリング・プロセスを数学的に以下と説明できます。
D = (K*M == S*M)
D=(S K*M=*M)
Where the * operator denotes AND and the == operator denotes a test for equality. D represents the sampling decision.
*オペレータがどこでANDを指示するか、そして、=オペレータは平等のためのテストを指示します。 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がマスクのビットの数、1であるMであるテーブルに置くのがわかるのは簡単です。 したがって、標本抽出確率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を得るために、2**mはテーブルNのエントリーの数に掛けられます:
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にどのビットを設定したらよいかを選ぶとき、注意しなければなりません。 SSRCが手当たりしだいに選ばれたRTP仕様命令ですが、これに従わない多くの知られている実現があります。 特に、集中管理要素、門番は推薦の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.
ハンドルへのこの問題が最初にSSRC使用を論じ尽くすことである最も安全な方法で、aは暗号で細切れ肉料理を固定します、MD5[4]などのように、そして、SSRCが中で上の計算を使用したので、結果における32ビットはその時、選ばれます。 これは、はるかに良い偶発性を提供して、様々な実現が実際にどうSSRCを設定するかに関する詳細な知識を必要としません。
2.1 Performance
2.1 パフォーマンス
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
いつ標本抽出要素を変えているか間、敷居を選択するのにガイドとしてこの方程式を使用できます、以下で議論するように。 例えば、標本抽出目標が意味する1%の標準偏差であるなら
Rosenberg & Schulzrinne Experimental [Page 3] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[3ページ]RFC2762RTP
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=2**mはそこであるのに、.5が1万人のグループのメンバーであるより小さいはずがありません。 より一般に、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セッションに参加する関係者は初めは、ちょうど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.Thisへのテーブル中詰めでコンテンツを平均的に半減させるようにマスクのビットの数を増加させることです。 テーブルが再びいったんいっぱいになると、マスクのビットの数はさらに増加します。
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
マスクのビットの数が増加すると、ユーザは、もう合っていないそれらのSSRCを取り外すことによって、代償します。 ビットの数が減少すると、ユーザは理論的に、SSRCが現在合っているそれらのユーザを加え返すべきです。 しかしながら、全体以来これらのSSRCは知られていません。
Rosenberg & Schulzrinne Experimental [Page 4] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[4ページ]RFC2762RTP
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.
これを補うために、ある種のアルゴリズムが必要です。 2つのアプローチがここに提示されます: 調整策の要素解決、および捨てる解答。 捨てる解決策は、理解しているのが、より簡単であり、よく振る舞います。 しかしながら、私たちは、完全性と比較の調整策要素解決について議論を含んでいて、また、IPRで邪魔されないと信じられているので、含んでいます。
4.1 Corrective Factors
4.1 調整策の要素
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つを取ることです。 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の時間、マスクのビットの数における変化のすぐcが平均したRTCP帯域幅が受信機のために割られたRTCPパケットサイズであり、L(t)がグループサイズ見積りである(t)前で時間tで腐食します。 この定数の理由は以下の通りです。 実際のグループ会員資格が変化していなくて、それらがメンバーである場合では、どれが忘れられたかはまだ発信しているRTCPパケットがそうするでしょう。 それぞれのそれらからRTCPパケットを聞くにはかかる時間は平均したRTCP間隔です。(その間隔はcL(t)です)。 したがって、調整策の要素によってごまかされたそれらのユーザは、マスクにおける変化の秒後のcL(t)パケットを送って、その結果、テーブルに現れるべきです。 私たちは、直線的に両方の機能を腐食するのを選びました。 これは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:
前の調整策の要素が期限が切れる前にマスクのビットの数がもう一度減少するなら、何が起こりますか? その場合、私たちは、さらに別の1つを使用することによって、要素を合成します。 fi()にithの付加的な修正機能を表させてください。そうすれば、兵士の()はithの乗法的な修正機能をさせます。 tがマスクのビットの数が減少する時であるなら、私たちは、付加的な修正率を以下と説明できます。
Rosenberg & Schulzrinne Experimental [Page 5] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[5ページ]RFC2762RTP
/ 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-) \
/0、t<t| t+cL(t)--t fi(t)=|(L(t)--L(t+)) ---------------- , t<t<t+cL(t)| Cl(t)| 0 t>t+cL(t)\
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-)
/1、t<t| | t+2cL(t)--t兵士の(t)| ----------------- , t<t<t+cL(t)| Cl(t)| 1円、t>t+cL(t)
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)が新しい要素以外の調整策の要素を含んでいて、得られたグループサイズ見積りを指示することに注意してください。tは+後の時間のビット、およびtの数の減少の前の時間権利です。 その結果、L(t)が減少の前にグループサイズ見積りを表して、L(t+)がまさしく後の見積りを表して、唯一の包含でないのは新しい要素です。
Finally, the actual group size estimate L(t) is given by:
以下でL(t)を与えるという最終的に実際のグループサイズ見積り
----- \ L(t) = / fi(t) + N*(2**m) ----- i
----- \L(t)=/fi(t)+N*(2**m)----- i
for the additive factor, and:
そして、付加的な要素のために:
------ | | | | L(t)= | | N*(2**m)*gi(t)
------ | | | | L(t)=| | N*(2**m)*兵士です。(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]を傾けていたとき、真剣にグループサイズを過小評価する傾向がありました。 これは以下の性能データに示されます。
Rosenberg & Schulzrinne Experimental [Page 6] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[6ページ]RFC2762RTP
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で始まって、1000年に時間t+cL(t)=ゼロに腐食します。 調節してください。500 Nが375まで増加したと(実際のグループサイズが変化していないなら、これは平均的にそうになるでしょう)仮定させます。 時500に、付加的な要素は250です。 これは2**m回のNに加えられます。(1000年のグループサイズ見積りをもたらして、それは、750です)。 今、ユーザが、再びマスクのビットの数を減少させると決めるので、そのmは0と等しいです。 別の付加的な要素は計算されます。 この要素はL(t)(1000である)でL(t+)を引いて始まります。 L(t+)は新しい要素なしで計算されます。 最初の添加物がこのとき(250)と2つの**m(1)回数N(375)を因数分解するということです。 これは625です。 その結果、新しい付加的な要素は、625 1000--(375)で始まって、1000秒以降、0に腐食します。
4.2 Binning Algorithm
4.2捨てるアルゴリズム
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
31 ---- \L(t)=/B(i)*2**i---- i=0
Where B(i) are the number of users in the ith bin.
B(i)がith容器のユーザの数であるところ。
Rosenberg & Schulzrinne Experimental [Page 7] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[7ページ]RFC2762RTP
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に送るユーザから取り除かれるユーザが、より高い容器から外されるという意味でまだ古い見積りをアップデートしています。 これで、より古い見積りは徐々にそれを段階的に廃止している間、まだ適合しています。 それが調整策のアルゴリズムよりはるかによく働くこの適合です。また、アルゴリズムも非常に簡単です。
4.3 Comparison
4.3 比較
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.
Table1でのシミュレーションで比べて、アルゴリズムはすべてです。 シミュレーションで、1万1人のユーザがt=0で仲間に入ります。 1万、それらのt=5000では、いなくなってください。 t=20,000では、別の5000はいなくなります。 すべてがSSRC標本抽出アルゴリズム、無条件の前進の再考、およびBYE再考を実行します。 全体のセッションの間中出席しているシングルユーザーによって見られるようにテーブルは時間20,000から時間25,000までのグループサイズ見積りについて表現します。 シミュレーションで、1000SSRCの記憶容量は想定されました。 標本抽出のはない添加物がある標本抽出による性能であり、乗法的で、容器ベースの修正は表現されます。
As the table shows, the bin based algorithm performs particularly well at capturing the group size estimate towards the tail end of the simulation.
テーブルが示すように、容器に基づいているアルゴリズムはよく特にグループサイズ見積りをシミュレーションの末端に向かって得るのに働きます。
Rosenberg & Schulzrinne Experimental [Page 8] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[8ページ]RFC2762RTP
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
時間いいえ標本抽出は乗法的な状態で添加物を捨てました。---- ----------- ------ -------- -------------- 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
4.4 Sender Sampling
4.4 送付者標本抽出
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
L(t)=(2**m)ナノ秒+Nr
which exponentially weights the senders.
送付者に指数関数的に重荷を負わせます。
Rosenberg & Schulzrinne Experimental [Page 9] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[9ページ]RFC2762RTP
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番目の容器に置かれます。 送付者が受信機になるとき、それはmの現行価値に対応する容器に動かされます、SSRCが仮面の比較操作でキーに合っているなら。
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.
RTCPパケットの認証なしで使用されると、RTPはスプーフィング攻撃に影響されやすいです。 攻撃者はそれぞれ異なったSSRCと共に多くのRTCPパケットをグループに注ぐことができます。 これで、RTP関係者は、グループ会員資格が実際によりはるかに高いと信じるでしょう。 結果は各関係者が結局RTCPパケットを非常にまれに伝えるということです、かつてなら。SSRC標本抽出が使用されているとき、それらのキーに対してそれらを合わせる前に関係者が細切れ肉料理をSSRCに適用する予定でないなら、問題は増幅できます。 これは攻撃者がそれぞれ異なったSSRCがあるキーに合っている多くのパケットを送ることができるからです。 これで、グループサイズは指数関数的にふくらませられるでしょう。 しかしながら、無作為の細切れ肉料理が適用されている状態で、攻撃者はキーに対して合っているそれらのSSRCを推測できません。 事実上、攻撃者は1つを見つけるmの異なったSSRC前の平均で合っている2**を送らなければならないでしょう。 もちろん、マッチの効果はグループ会員資格の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.ジェーコブソン、「RTP:」 「リアルタイムのアプリケーションのためのトランスポート・プロトコル」、RFC1889、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 Infocom、(サンフランシスコ(カリフォルニア))、1998年3月/4月。
Rosenberg & Schulzrinne Experimental [Page 10] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[10ページ]RFC2762RTP
[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] 国際電気通信連合、「展示は非保証されたサービスの質を提供するローカル・エリア・ネットワークのためにシステムと設備に電話をします」、Recommendation H.323、ITUのTelecommunication Standardization Sector、ジュネーブ(スイス)1996年5月。
[4] Rivest, R., "The MD5 message-digest algorithm", RFC 1321, April 1992.
[4] 1992年4月、最もRivestなR.、「MD5メッセージダイジェストアルゴリズム」RFC1321。
[5] Rosenberg, J., "Protocols and Algorithms for Supporting Distributed Internet Telephony," PhD Thesis, Columbia University, Dec. 1999. Work in Progress.
[5] ローゼンバーグ、J.、「支持のためのプロトコルとアルゴリズムはインターネット電話を分配した」博士Thesis、コロンビア大学、1999年12月。 進行中で、働いてください。
8 Authors' Addresses
8人の作者のアドレス
Jonathan Rosenberg dynamicsoft 200 Executive Drive West Orange, NJ 07052 USA
ジョナサンローゼンバーグdynamicsoft200Executive Driveニュージャージー07052ウェストオレンジ(米国)
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/S0401 1214アムステルダムAve。 ニューヨーク、ニューヨーク10027-7003米国
EMail: schulzrinne@cs.columbia.edu
メール: schulzrinne@cs.columbia.edu
Rosenberg & Schulzrinne Experimental [Page 11] RFC 2762 RTP Sampling February 2000
2000年2月を抽出するローゼンバーグとSchulzrinneの実験的な[11ページ]RFC2762RTP
9 Full Copyright Statement
9 完全な著作権宣言文
Copyright (C) The Internet Society (2000). All Rights Reserved.
Copyright(C)インターネット協会(2000)。 All rights reserved。
This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English.
それに関するこのドキュメントと翻訳は、コピーして、それが批評するか、またはそうでなければわかる他のもの、および派生している作品に提供するか、または準備されているかもしれなくて、コピーされて、発行されて、全体か一部広げられた実現を助けるかもしれません、どんな種類の制限なしでも、上の版権情報とこのパラグラフがそのようなすべてのコピーと派生している作品の上に含まれていれば。 しかしながら、このドキュメント自体は何らかの方法で変更されないかもしれません、インターネット協会か他のインターネット組織の版権情報か参照を取り除くのなどように、それを英語以外の言語に翻訳するのが著作権のための手順がインターネットStandardsの過程で定義したどのケースに従わなければならないか、必要に応じてさもなければ、インターネット標準を開発する目的に必要であるのを除いて。
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機能のための基金は現在、インターネット協会によって提供されます。
Rosenberg & Schulzrinne Experimental [Page 12]
ローゼンバーグとSchulzrinne実験的です。[12ページ]
一覧
スポンサーリンク