Échantillonnage de la taille du groupe dans RTP

Statut de ce mémoire

Le présent mémoire définit un protocole expérimental pour la communauté de l'Internet. Il ne spécifie aucune sorte de norme de l'Internet. La discussion et les suggestions pour son amélioration sont bienvenues. La distribution du présent mémoire n'est soumise à aucune restriction.

Notice de copyright

Copyright (C) The Internet Society (2000). Tous droits réservés.

Résumé

Dans les grands groupes de diffusion groupée, la taille du tableau des membres du groupe conservée par les participants en RTP (protocole de transport en temps réel) peut devenir ingérable, particulièrement pour les appareils incorporés qui ont une mémoire et une puissance de traitement limitées. Le présent document expose des mécanismes pour échantillonner ce tableau des membres du groupe afin de réduire les exigences de mémoire. Plusieurs mécanismes sont proposés, et les performances de chacun sont examinées.

1.   Introduction

RTP, le protocole de transport en temps réel [1], rend obligatoire que les paquets RTCP soient transmis de chaque participant avec une périodicité grossièrement proportionnelle à la taille du groupe. La taille du groupe est obtenue en mémorisant un tableau qui contient une entrée pour chaque SSRC (source de synchronisation) unique vu dans les paquets RTP et RTCP. Alors que les membres quittent ou arrivent en fin de temporisation, les entrées sont supprimées, et lorsque de nouveaux membres adhèrent, des entrées sont ajoutées. Le tableau est donc très dynamique.

Pour de grandes sessions de diffusion groupée, telles qu'une diffusion sur mbone ou une distribution de télévision fondée sur IP, les tailles de groupe peuvent être extrêmement grandes, de l'ordre de centaines de milliers ou de millions de participants. Dans ces environnements, RTCP peut n'être pas toujours utilisé, et donc le tableau des membres du groupe n'être pas nécessaire. Cependant, il est très souhaitable que RTP s'adapte bien aux groupes d'un seul membre autant qu'aux groupes d'un million de membres, sans intervention humaine pour "débrancher" RTCP lorsqu'il n'est plus approprié. Cela signifie que les mêmes outils et systèmes peuvent être utilisés aussi bien pour les petites conférences que pour les diffusions de télévision d'une façon douce et échelonnable.

Les travaux précédents [2] ont identifié trois problèmes majeurs d'échelonnabilité avec RTP. Ce sont :

1.   L'encombrement dû aux flux de paquets RTCP dans des groupes très dynamiques ;

2.   De grands délais entre la réception de paquets RTCP provenant d'un seul utilisateur ;

3.   La grande taille du tableau des membres du groupe.

L'algorithme de reconsidération [2] aide à atténuer le premier de ces problèmes. Le présent document traite du troisième, qui est celui des tableaux de groupes de grande taille.

La mémorisation d'un tableau SSRC d'un million de membres, par exemple, exige au moins quatre méga-octets. Il en résulte que les appareils incorporés avec de petites capacités de mémoire peuvent avoir des difficultés dans ces conditions. Pour résoudre ce problème, l'échantillonnage de SSRC a été proposé. L'échantillonnage de SSRC utilise l'échantillonnage statistique pour obtenir une estimation stochastique des membres du groupe. De nombreux problèmes surgissent lorsque ceci est fait. Le présent document passe en revue ces problèmes et discute des mécanismes qui peuvent être appliqués par les développeurs. En particulier, il se concentre sur trois méthodes pour adapter la probabilité de l'échantillonnage lorsque le nombre des membres du groupe varie. Il est important de noter que l'IETF a reçu une notification de revendication de droits de propriété intellectuelle à l'égard de tout ou partie de la spécification contenue dans le présent document, et en particulier sur une des trois mécanismes : l'algorithme d'emboîtage (binning) décrit ci-dessous. Pour des informations complémentaires; consulter la liste en ligne des revendications de droits. Les deux autres approches présentées sont inférieures à l'algorithme d'emboîtage, mais sont incluses car on pense qu'elles ne sont pas grevées d'IPR.

2.   Fonctionnement de base

L'idée de base derrière l'échantillonnage de SSRC est simple. Chaque participant conserve une clé K de 32 bits,et un gabarit M de 32 bits. On suppose que m des bits du gabarit sont à 1, et le reste est à zéro. Lorsque un paquet RTCP arrive avec une SSRC S, plutôt que de la placer dans le tableau, elle est d'abord échantillonnée. L'échantillonnage est effectué en appliquant l'opérateur logique ET sur la clé et le gabarit, et en répétant cette opération sur la SSRC et le gabarit. Les valeurs résultantes sont comparées. Si elles sont égales, la SSRC est mémorisée dans le tableau. Sinon, la SSRC est rejetée, et le paquet est traité comme si il n'avait jamais été reçu.

La clé peut être n'importe quoi, mais elle est habituellement déduite de la SSRC de l'utilisateur qui effectue l'échantillonnage.

Le processus d'échantillonnage peut être décrit mathématiquement comme :

D = (K*M == S*M)

O* l'opérateur * note ET et l'opérateur == note l'essai d'égalité. D représente la décision d'échantillonnage.

Conformément à la spécification de RTP, les SSRC utilisées par les participants à une session sont choisis de façon aléatoire. Si la distribution est aussi uniforme, il est aisé de voir que le filtrage ci-dessus va provoquer le placement dans le tableau de 1 sur 2**m SSRC, où m est le nombre de bits dans le gabarit, M, qui est un. Et donc, la probabilité d'échantillonnage p est 2**-m.

Alors, pour obtenir une estimation de la taille du groupe réel, L, le nombre des entrées dans le tableau N est multiplié par 2**m :

L = N * 2**m

Il faut faire attention à bien choisir quels bits mettre à 1 dans le gabarit. Bien que la spécification RTP rende obligatoire des SSRC choisies de façon aléatoire,il y a beaucoup de mises en œuvre connues qui ne s'y conforment pas. En particulier, la série de Recommandations UIT-T H.323 [3] permet à l'élément ce contrôle central, le portier, d'allouer les 8 bits de moindre poids de la SSRC, alors que les bits de poids fort sont choisis de façon aléatoire par les participants à RTP.

La façon la plus sûre de traiter ce problème est de commencer par hacher la SSRC en utilisant un hachage cryptographiquement sûr, tel que MD5 [4], puis de choisir 32 des bits du résultat comme SSRC utilisée dans le calcul ci-dessus. Cela donne un bien meilleur aléa, et n'exige pas une connaissance détaillée de la façon dont les diverses mises en œuvre établissent réellement la SSRC.

2.1   Performances

L'estimation est plus précise lorsque la valeur de m décroît, et moins précise lorsque elle s'accroît. Cela peut être démontré analytiquement. Si la taille réelle du groupe est G, le ratio de l'écart type et de la moyenne de l'estimation L (coefficient de variation) est : sqrt((2**m - 1)/G)

Cette équation peut être utilisée comme guide pour choisir les seuils pour savoir quand changer le facteur d'échantillonnage, comme exposé plus loin. Par exemple, si la cible est un écart type de 1% par rapport à la moyenne, la probabilité de l'échantillon p=2**-m ne devrait pas être inférieure à 0,5 lorsque il y a dix mille membres du groupe. De façon plus générale, pour réaliser un écart type désiré à un ration moyen de T, la probabilité de l'échantillon ne devrait pas être inférieure à : p > 1 / (1 + G*(T**2))

3.   Accroître la probabilité de l'échantillon

La procédure simple d'échantillonnage ci-dessus devrait bien fonctionner si la taille du groupe est statique. Cependant, elle ne l'est pas. Un participant qui se joint à une session RTP va initialement voir juste un participant (lui-même). Lorsque les paquets sont reçus, la taille du groupe telle que vue par ce participant va augmenter. Pour traiter cela, la probabilité d'échantillonnage doit être rendue dynamique, et elle aura besoin d'augmenter et diminuer avec la variation de la taille du groupe.

La procédure pour augmenter la probabilité de l'échantillonnage est aisée. Un participant commence avec un gabarit où m = 0. Dans ces conditions, chaque SSRC reçue sera mémorisée dans le tableau, de sorte qu'il n'y a effectivement pas d'échantillonnage. À un certain point, la valeur de m est augmentée de un. Cela implique que approximativement la moitié des SSRC qui sont déjà dans le tableau ne vont plus correspondre à la clé qui est derrière l'opération de mise au gabarit. Afin de conserver une estimation correcte, ces SSRC doivent être éliminées du tableau. Les nouvelles SSRC ne sont ajoutées que si elle correspondent à la clé qui derrière le nouveau gabarit.

La décision sur le moment d'augmenter le nombre de bits dans le gabarit est aussi simple. Disons qu'un participant RTP a une mémoire avec assez de capacité pour mémoriser C entrées dans le tableau. La meilleure estimation du group est obtenue par la plus grande probabilité d'échantillon. Cela signifie aussi que la meilleure estimation est obtenue lorsque le tableau est le plus rempli. Une approche raisonnable est donc d'augmenter le nombre de bits dans le gabarit juste au moment ou le tableau est rempli jusqu'à C. Cela va généralement causer la réduction de moitié de son contenu en moyenne. Une fois que le tableau se remplit à nouveau, le nombre de bits du gabarit est à nouveau augmenté.

4.   Réduire la probabilité de l'échantillon

Si la taille du groupe commence à diminuer, il peut être nécessaire de réduire le nombre de bits à un dans le gabarit. Ne pas le faire débouche sur de très mauvaises estimations de la taille du groupe. Malheureusement, réduire le nombre de bits dans le gabarit est plus difficile que de les augmenter.

Lorsque le nombre de bits du gabarit augmente, l'utilisateur compense en retirant les SSRC qui ne correspondent plus. Lorsque le nombre de bits diminue, l'utilisateur devrait théoriquement rajouter ces utilisateurs dont la SSRC correspond maintenant. Cependant, ces SSRC ne sont pas connues, car tout l'intérêt de l'échantillonnage tient justement à ne pas se souvenir d'elles. Donc, si le nombre de bits du gabarit est juste réduit sans changement du tableau des membres, l'estimation du groupe va instantanément chuter exactement de moitié.

Pour compenser cela, il est nécessaire d'utiliser une sorte d'algorithme. Deux approches sont présentées ici : une solution de facteur correctif, et une solution d'emboîtage. La solution d'emboîtage est plus simple à comprendre et est plus efficace. Cependant, nous incluons l'exposé de la solution du facteur correctif pour être complet et avoir une comparaison, et aussi parce que il est estimé qu'elle n'est pas grevée d'IPR.

4.1   Facteurs correctifs

L'idée avec les facteurs correctifs est de prendre une approche parmi deux. Dans la première, un facteur correctif est ajouté à l'estimation de la taille du groupe, et dans la seconde, l'estimation de la taille du groupe est multipliée par un facteur de correction. Dans les deux cas, l'objet est de compenser le changement du gabarit d'échantillon. Les facteurs de correction devraient décliner lorsque à la fin on en sait plus sur les membres "fondants" et qu'ils sont en fait placés dans la liste des membres.

Le facteur additif commence à la différence entre l'estimation de la taille du groupe avant et après que le nombre de bits du gabarit soit réduit, et diminue à 0 (ce n'est pas toujours la moitié de l'estimation de la taille du groupe, car les facteurs correctifs peuvent être arrangés, voir ci-dessous). Le facteur de correction multiplicatif commence à 2, et décline graduellement jusqu'à un. Les deux facteurs déclinent au fil du temps de cL(ts-), où c est la moyenne de la taille de paquet RTCP divisée par la bande passante RTCP pour les receveurs, et L(ts-) est l'estimation de la taille du groupe juste avant le changement du nombre de bits dans le gabarit à l'instant ts. La raison de cette constante est la suivante. Dans le cas où l'appartenance au groupe réel n'a pas changée, les membres qui ont été oubliés vont quand même envoyer des paquets RTCP. Le temps nécessaire pour entendre un paquet RTCP de chacun d'eux est l'intervalle RTCP moyen, qui est cL(ts-). Donc, cL(ts-) secondes après le changement du gabarit, les utilisateurs qui ont été "fondus" par le facteur de correction devraient avoir envoyé un paquet et donc apparaître dans le tableau. Nous choisissons de faire décroître les deux fonctions de façon linéaire, parce que le taux d'arrivé des paquets RTCP est linéaire.

Qu'arrive t-il si le nombre de bits dans le gabarit est réduit encore une fois avant que le facteur de correction précédent ne soit arrivé à expiration ? Dans ce cas, on arrange les facteurs en en utilisant un autre. Soit fi() qui représente la i ème fonction additive de correction, et gi() la i ème fonction multiplicative de correction. Si ts est le moment où le nombre de bits dans le gabarit est réduit, on peut décrire le facteur de correction additif comme :

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

        \

et le facteur multiplicatif comme :

      / 1                 , t < ts

      |

      | ts + 2cL(ts-) - t

gi(t) | ----------------- , ts < t < ts + cL(ts-)

      |      cL(ts-)

      |

      \ 1                 , t > ts + cL(ts-)

Noter que dans ces équations, L(t) note l'estimation de la taille du groupe obtenue en incluant les facteurs de correction à l'exception du nouveau facteur. ts- est le moment juste avant la réduction du nombre de bits, et ts+ le moment juste après. Il en résulte que L(ts-) représente l'estimation de la taille du groupe avant la réduction, et L(ts+) l'estimation juste après, mais sans inclure le nouveau facteur.

Finalement, l'estimation de la taille du groupe réelle L(t) est donnée par :

       -----

       \

L(t) = /     fi(t) + N*(2**m)

       -----

        i

pour le facteur additif, et :

     ------

      |  |

      |  |

L(t)= |  | N*(2**m)*gi(t)

pour le facteur multiplicatif.

Les simulations ont montré que les deux algorithmes fonctionnent également bien, mais tous deux tendent à sérieusement sous estimer la taille du groupe lorsque l'appartenance au groupe décline rapidement [5]. Ceci est démontré dans les données de performances ci-dessous.

Par exemple, considérons le calcul du facteur additif. La taille du groupe est 1000, c est 1 seconde, et m est deux. Avec un gabarit de cette taille, un participant va, en moyenne, observe 250 (N = 250) utilisateurs. À t=0, l'utilisateur décide de réduire le nombre de bits dans le gabarit à 1. Il en résulte que L(0-) est 1000, et L(0+) est 500. Le facteur additif commence donc à 500, et décline à zéro au temps ts + cL(ts-) = 1000. À l'instant 500, supposons que N a augmenté à 375 (cela va, en moyenne, être le cas si la taille réelle du groupe n'a pas changée). À l'instant 500, le facteur additif est 250. Ceci est ajouté 2**m fois à N, qui est 750, d'où résulte une estimation de la taille du groupe de 1000. Maintenant, l'utilisateur décide de réduire à nouveau le nombre de bits dans le gabarit, de sorte que m=0. Un autre facteur additif est calculé. Ce facteur commence à L(ts-) (qui est 1000), moins L(ts+). L(ts+) est calculé sans le nouveau facteur ; c'est le premier facteur additif à ce moment (250) plus 2**m (1) fois N (375). Cela fait 625. Il en résulte que le nouveau facteur additif commence à 1000 - 625 (375), et décline à 0 en 1000 secondes.

4.2   Algorithme d'emboîtage

Afin d'estimer plus correctement la taille du groupe même lorsque elle décroît rapidement, on peut utiliser un algorithme d'emboîtage. L'algorithme fonctionne comme suit. Il y a 32 boîtes, le même que le nombre de bits dans le gabarit d'échantillon. Lorsque arrive un paquet RTCP d'un nouvel utilisateur dont la SSRC correspond à la clé qui est derrière l'opération de mise au gabarit, il est placé dans la m ème boîte (où m est le nombre de uns dans le gabarit) autrement, il est éliminé.

Lorsque le nombre de bits doit être augmenté dans le gabarit, les membres qui sont dans la boîte et qui correspondent encore avec le nouveau gabarit sont déplacés dans la nouvelle boîte supérieure. Ceux qui ne correspondent pas sont éliminés. Lorsque le nombre de bits dans le gabarit doit être diminué, on ne fait rien. Les utilisateurs dans les diverses boîtes restent où ils sont. Cependant, lorsque un paquet RTCP pour un utilisateur apparaît, et que l'utilisateur est dans une boîte avec une valeur supérieure au nombre actuel de bits dans le gabarit, il est déplacé dans la boîte correspondant au nombre actuel de bits du gabarit. Finalement, l'estimation de la taille du groupe L(t) est obtenue par :

        31

       ----

       \

L(t) = / B(i) * 2**i

       ----

       i=0

où B(i) est le nombre d'utilisateurs dans la i ème boîte.

L'algorithme fonctionne à la base en conservant la vieille estimation lorsque le nombre de bits diminue dans le gabarit. Lorsque les utilisateurs arrivent, ils sont graduellement déplacés dans la boîte inférieure, ce qui réduit la quantité de la contribution des boîtes supérieures à l'estimation totale. Cependant, la vieille estimation est toujours mise à jour en ce sens que les utilisateurs qui arrivent en fin de temporisation sont retirés de la boîte supérieure, et les utilisateurs qui envoient des paquets BYE sont aussi retirés de la boîte supérieure. Cela permet à la plus vieille estimation de s'adapter encore, alors qu'elle s'élimine graduellement. C'est cette adaptation qui fait qu'il a de meilleures performances que les algorithmes correctifs. L'algorithme est aussi extrêmement simple.

4.3   Comparaison

Les algorithmes sont tous comparés par simulation dans le tableau 1. Dans la simulation, 10 001 utilisateurs rejoignent un groupe à t = 0. À t = 10 000, 5000 d'entre eux quittent. À t = 20 000, 5000 autres quittent. Tous mettent en œuvre un algorithme d'échantillonnage de SSRC, la reconsidération inconditionnelle de transmission et la reconsidération de BYE. Le tableau décrit l'estimation de la taille du groupe de l'instant 20 000 à l'instant 25 000 comme il est vu par le seul utilisateur présent tout au long de la session entière. Dans la simulation, une taille de mémoire de 1000 SSRC est supposée. Les performances sont décrites sans échantillonnage, et avec échantillonnage et correction fondée sur le facteur additif, le facteur multiplicatif, et l'emboîtage.

Comme le montre le tableau, l'algorithme fondé sur l'emboîtage a des performances particulièrement bonne pour capturer l'estimation de la taille du groupe vers la partie finale de la simulation.

4.4   Échantillonnage de l'envoyeur

Il faut faire attention lorsque on traite des envoyeurs en utilisant l'échantillonnage de SSRC. Comme le nombre d'envoyeurs est généralement faible, et qu'ils contribuent de façon significative au calcul de l'intervalle RTCP, l'échantillonnage ne devrait pas leur être appliqué. Cependant, ils doivent être gardés dans un tableau séparé, et ne pas être "comptés" au titre des membres du groupe général. Si ils sont comptés au titre des membres du groupe général, et ne sont pas échantillonnés, l'estimation de la taille du groupe va être gonflée pour sur représenter les envoyeurs.

Ceci est facilement démontré analytiquement. Soit Ns le nombre d'envoyeurs, et Nr le nombre de receveurs. Le tableau des membres va contenir tous les Ns envoyeurs et (1/2)**m des receveurs. L'estimation de la taille totale du groupe dans le présent mémoire est obtenue par 2**m fois le nombre d'entrées dans le tableau. Donc, l'estimation de la taille du groupe devient : L(t) = (2**m) Ns + Nr ce qui pondère exponentiellement les envoyeurs.

Ceci est facilement compensé dans l'algorithme d'emboîtage. Un envoyeur est toujours placé dans la 0 ème boîte. Lorsque un envoyeur devient un receveur, il est déplacé dans la boîte correspondant à la valeur actuelle de m, si sa SSRC correspond à la clé de l'opération de comparaison au gabarit.

5.   Considérations pour la sécurité

L'utilisation de l'échantillonnage de SSRC ne paraît pas introduire de considérations supplémentaires pour la sécurité au delà de celles décrites dans [1]. En fait, l'échantillonnage de SSRC, tel que décrit ci-dessus, peut aider un peu à réduire les effets de certaines attaques.

RTP, lorsque il est utilisé sans l'authentification des paquets RTCP, est susceptible d'attaques par mystification. Les attaquants peuvent injecter de nombreux paquets RTCP dans le groupe, chacun avec une SSRC différente. Cela va faire croire aux participants à RTCP que l'appartenance au groupe est beaucoup plus élevée qu'elle n'est en réalité. Le résultat est que chaque participant va finir par ne transmettre de paquets RTCP que peu fréquemment, sinon pas du tout. Lorsque l'échantillonnage de SSRC est utilisé, le problème peut être amplifié si un participant n'applique pas de hachage à la SSRC avant de la confronter à la clé. C'est pourquoi un attaquant peut envoyer de nombreux paquets, chacun avec une SSRC différente, qui correspond à la clé. Cela pourrait causer une inflation exponentielle de la taille du groupe. Cependant, avec l'application d'un hachage aléatoire, un attaquant ne peut pas deviner quelles SSRC vont encore correspondre à la clé. En fait, un attaquant devra envoyer 2**m SSRC différentes avant d'en trouver une qui corresponde, en moyenne. Bien sûr, l'effet d'une correspondance cause une augmentation des membres du groupe de 2**m. Mais, l'utilisation de l'échantillonnage signifie qu'un attaquant devra envoyer beaucoup de paquets avant qu'un effet soit observable.

6.   Remerciements

Les auteurs tiennent à remercier Bill Fenner et Vern Paxson pour leurs commentaires.

7.   Bibliographie

[1]]   H. Schulzrinne, S. Casner, R. Frederick et V. Jacobson, "RTP : protocole de transport pour applications en temps réel", janvier 1996., RFC 1889.

[2]   J. Rosenberg and H. Schulzrinne, "Timer reconsideration for enhanced RTP scalability", IEEE Infocom, (San Francisco, California), mars/avril 1998.

[3]   Union Internationale des Télécommunications, Secteur de la normalisation des télécommunications, "Systèmes et équipements de visiophone pour les réseaux de zone locale qui fournissent une qualité de service non garantie", Recommandation H.323, Genève, Confédération Helvétique, mai 1996.

[4]   R. Rivest, "Algorithme de résumé de message MD5", RFC 1321, avril 1992. (Information)

[5]   Rosenberg, J., "Protocols and Algorithms for Supporting Distributed Internet Telephony," Thèse de doctorat, Université de Columbia, décembre 1999. Travail en cours.

8.   Adresse des auteurs

9.   Déclaration de copyright

Remerciement

Le financement de la fonction d’édition des RFC est actuellement fourni par Internet Society.