Brevet FR2970139A1 — publié le 20120706

Arrière-plan de l'invention L'invention se situe dans le contexte des réseaux de télécommunications et vise plus particulièrement un procédé de communications dans un réseau de type 'pair à pair' ~ utilisé pour distribuer des données numériques dans le réseau. De façon connue, les critères de performance suivants peuvent être utilisés pour les réseaux pair à pair: le temps dinitia!isationdu réseau, l'intervalle de temps entre le moment où le données sont émises par la source et le moment où elles sont reçues par tous les pairs du réseau, l'adaptabilité du réseau à réagir aux arrivées et aux départs des 10 pairs. Dans l'état actuel de la technique, les réseaux pair à pair ont soit une architecture de diffusion dite « non-structurée », dans laquelle chaque échange de données utiles est précédé d'un échange de données de signalisation entre pairs, soit une architecture de diffusion dite « structurée », dans laquelle chaque pair est apte à 15 déterminer à partir d'une règle de fonctionnement du réseau avec quels pairs il doit communiquer, et quelles données il doit échanger. Les réseaux à architecture « non-structurée » sont plus adaptables aux arrivées et départs des pairs, mais présentent plusieurs inconvénients, à savoir notamment un encombrement du réseau dû aux messages de signalisation et un de temps de 20 transmission différent entre la source et les différents pairs. Ce deuxième inconvénient dégrade fortement la qualité des transmission des flux de données destinées à être reçues rapidement et avec peu d'écart entre les différents pairs, comme par exemple les flux audio-vidéo contenant des actualités où des événements sportifs. Les réseaux basés sur une architecture de diffusion de données structurée 25 peuvent transmettre les données dans des temps optimisés et proches pour tous les pairs, mais sont fortement perturbés lorsqu'un pair arrive dans le réseau ou sort du réseau. 1.1 Présentation des réseaux hyper cubes complets Pour la bonne compréhension de l'invention, on présente de façon pnélwnüna/re /c modèle de réseaux de pairs connu de l'homme du métier sous le nom de « réseau hyper cube complet de dimension n », les avantages et les limites de ce modele. 30 35 2 1.1.1. Contexte On se place plus précisément dans le contexte d'un réseau de pairs dans lequel les flux de données sont divisés en blocs de données numérotés (en anglais «chunk6»). Nous supposerons qu'en l'absence de perte dans le réseau, un pair est apte à recevoir et à transmettre un bloc de données par intervalle de temps (slot). 1.1.2. Diffusion optimale et identifiants des pairs 10 Il a été démontré dans le document « Y. Liu, "On the minimum utlay /nasr*to- /mæarwdeo streaming : /xxw//ealtimeuan/fber in MULTIMEDIA V7: Proceedings of the 15th international conference on Multimedia, New York, NY, USA ACM, 2007, pp. 127 /36» que le temps de diffusion optimal était obtenu lorsque tous les pairs continuent à transmettre un bloc de données jusqu'à ce que tous les pairs l'aient reçu. Le temps de 15 diffusion optimal s'entend en nombre de transmission de blocs. Cela revient à doubler le nombre de pairs en possession du bloc de données concerné à chaque transmission jusqu'à la dernière. Une conséquence du résultat démontré dans cet article est que, pour une population de pairs N telle que 2»'z Nous décrivons maintenant comment les transmissions peuvent être organisées lorsque le nombre N de pairs est de la forme N 211 -t. Etant donné que chaque pair transmet un bloc de données par intervalle de 25 temps, un pair recevant un bloc de données doit nécessairement le retransmettre aux autres pairs jusqu'à ce que les N pairs l'aient reçu, avec N = 2° + 21 + ...+2»'1. Puisque l'on fait l'hypothèse qu'il existe 2n-t pairs, tous arrêtent de transmettre le bloc de données au même moment. Les séquences de transmissions possibles par pairs sont donc !e6 suivantes, chaque élément de ia séquence identifiant le numéro du 30 bloc de données à transmettre au cours d'un intervalle de temps correspondant à cet élément, le temps s'écoulant de droite à gauche, du premier vers le dernier élément : {9,9\7, 7, 5, 4, 3, 3, 3} !9. 6, 5, 4, 4, 4, 1} Il existe une bijection entre ces séquences et les séquences suivantes : {1, 0, 1, 0, 1, 1, 1, 0, 0} {1, 0, 0, 1, 1, 1, 0, 0, 1} {1, 1, 0, 1, 1, 1, 0, 0, 1} dans lesquelles le bit « 1 » est placé aux positions pour lesquelles un bloc de données est transmis pour la dernière fois, le bit « O » occupant les autres positions. Un bit à « 1 » dans la séquence identifie l'intervalle de temps au cours duquel un bloc est transmis pour la dernière fois et le nombre de bits « 0 » à sa droite le 10 nombre de fois où ce même bloc est retransmis. Ces séquences peuvent être répétées périodiquement après n intervalles de temps pour diminuer la complexité. Dans ce cas, une séquence de longueur n, composée d'éléments binaires de valeur « 0 » et de « 1 » suffit pour représenter toutes les séquences de blocs pouvant être émises par un pair. 15 La séquence composée exclusivement d'éléments binaires de valeur «U» est non significative, puisqu'elle correspondrait à l'émission répétée du même bloc de donnéæs. On attribue à chaque pair un identifiant unique de longueur n et la séquence de transmission de blocs de données correspondante. Autrement dit, chaque pair est 20 représenté par une séquence binaire unique qui dicte son comportement. Par exemple, pour n=5, le réseau comportant 31 pairs, le pair d'identifiant 01001 est programmé pour transmettre la séquence de blocs : 6, 4, 4, 4, 1 (1), suivie par : 11, 9/ 9, 9, 6 (2) 25 Si les séquences de transmissions sont périodiques, les numéros de blocs et les intervalles de temps peuvent être représentés modulo n, et les séquences (1) e±(2) par la séquence unique : 1, 4, 4, 4, 1, le temps étant compté de dnoitæà gauche de 1 à 5 avant de se répéter. Cette relation entre l'identifiant du pair et la séquence de transmission se 30 résume de !a façon suivante : A l'instant t=k, un pair continue à envoyer le même bloc qu'à l'instant t'=k-1, si et seulement si la représentation binaire de son identifiant comporte un « 0 » à la position k-1, modulo n. Ainsi, tin pair dont l'identifiant comporte un « 1 » à la position ~=t modulo n 35 trnnsmet un bloc, la dot nieie fois. 4 Règle 2 Un pair avec un « 1 » en position i de son identifiant transmet les blocs de numéro k=i modulo n. Cette règle permet de définir quels sont les blocs de données transmis par un pair. Ainsi, si un pair a un « 1 » dans son identifiant à la position k à l'instant t (où t=k modulo n), il transmettra le bloc qui a été transmis par la source à !'instæntt-n, soit le bloc k modulo n. Les règles 1 et 2 permettent de déduire le Lemme 1 suivant : Lemme 1 : Un pair transmet autant de blocs de données différents dans une séquence de temps n qu'il y a de « 1 » dans la représentation binaire de son ~O identifiant. En particulier, le pair d'identifiant 11111 transmet tous les blocs une seule fois, et le pair d'identifiant 00001 transmet 5 fois les blocs transmis aux instants t tels que t modulo n = 1, ce pair étant le premier à transmettre ces blocs. Dans la suite de la description on ne distinguera pas les indices de temps ni les 15 numéros de blocs égaux modulo n. 1.1.3. Détermination des destinataires des blocs On noteei le nombre binaire constitué de«O»avec un seul « 1 » en position i. Les règles suivantes définissent à qui un bloc doit être transmis. Cette méthode 20 permet une diffusion sur toute la population N. Règle 3 : A l'instant t, un pair d'identifiant binaire b envoie un bloc au pair d'identifiant binaire b+et. Puisque b+*t+et=b, le pair destinataire b++t envoie aussi un bloc au pair b à l'instant t. 2~ On notera qu'un pair envoie des blocs et ne reçoit des blocs que de n pairs différents, dits 'voisins'. 30 La Table 10ustre quels blocs sont transmis et reçus par le pair d'identifiant 01001. Intervalle Identifiant du Na Bloc envoyé N° Bloc reçu de temps voisin 1 01000 1 4 2 01011 4 2 3 01101 4 3 4 00001 4 1 5 11001 1 5 5 Proposition 1 : La Règle 1, la Règle 2 et la Règle 3 définissent une structure de diffusion optimale pour un flux dans un réseau de /V=2n - 1 pairs. En effet : - un pair dont l'identifiant comporte un « U» à la position k, reçoit le bloc k à l'instant k pour lequel il s'agit de la dernière transmission du bloc (Lemme 2) ; et - un pair dont l'identifiant bcornporte un « 1 » en position k, reçoit le bloc k' à l'instant k, où k' est la position du prochain « 1 » à la gauche de k dans b (Lemme Il résulte de ces deux lemmes qu'un pair reçoit tous les blocs, et que pour un pair d'identifiant b donné, les blocs retransmis sont reçus « à temps », à savoir dans l'intervalle de temps (slot) qui précède l'intervalle de temps (slot) au cours duquel le bloc doit être retransmis. Les séquences de transmissions définies précédemment définissent un réseau hypercube complet de dimension n, avec un nombre constant de pairs N = 2n - 1, et un algorithme de diffusion structurée sur ce réseau. Dans la suite de la description, on appellera « dæsoandantS» d'un pair b pour un bloc de données p, les pairs qui reçoivent une copie de ce bloc directement de b ou les descendants de ces pairs pour le paquet p. Proposition 2 : I! résulte de la Règle 3 déjà énoncée qu'un pair n'échange des données qu'avec des pairs de niveau supérieur ou inféheurà son propre niveau 25 mais en aucun cos avec des pairs de son niveau. Proposition 3 : Selon le Lemme 3, un pair recevont un bloc de données d'un niveau superieur dort le retransmettre conformernent àu emme 2, un pair tecevant ` ,iv,a/. n!~r/""' ^" !p 6 De façon corollaire (corollaire 1), si un pair de niveau ! doit envoyer un bloc de données kfois. cela signifie que ce pair a un descendant direct de niveau 1+1, k-1 descendants directs de niveau 1-1, k-1 descendants de niveau 1 et tous ses autres descendants de niveau 1-1 ou inférieur. Ses descendants de niveaux 1+1 et 1 ne 5 retransmettent pas le bloc de données. Proposition 4 : Un pair de niveau ! a n-1 descendants directs de niveau 1+1, 1 descendants directs de niveau 1-1, ! descendants de niveau 1, tous ses autres descendants de niveaux 1-1 ou inférieur. Ses descendants de niveaux 1+1 et ! ne retransmettent pas le bloc de données. 10 Proposition 5 : Un pair de niveau ! a n-1 ancêtres directs de niveau 1+1, ! ancêtres directs de niveau 1-1, ! ancêtres de niveau !, tous ses autres ancêtres de niveaux 1+1 ou supérieur. Les blocs reçus des ascendants de niveau 1-1 et 1 ne sont pas retransmis. 15 1.1.4 Délais On évalue le délai maximum d'un bloc pour un pair A compté depuis l'instant auquel la source l'a transmis. On évalue tout d'abord de délai en nombre de transmissions. Tous les pairs avec un « U» dans leur identifiant reçoivent le bloc n transmissions après la source, 20 avec un délai n. Le pair spécial dont l'identifiant ne comporte que des « 1 » reçoit tous les blocs juste avant la dernière transmission avec un délai n-l. On s'intéresse ensuite aux délais de propagation. Soit D le temps moyen mis par un bloc de données pour atteindre une destination après sa transmission par la source. Durant sa vie, un bloc de données peut soit rester dans un pair (autrement dit être transmis plusieurs fois) soit descendre d'un niveau ou monter d'un niveau pour sa dernière transmission. Donc un pair de niveau i avec un « O» dans son identifiant reçoit un bloc après qu'il a atteint le niveau 1+1 et a été renvoyé au niveau I. Soit un temps de propagation pour le pair de (n-1+2)D. Le pair spécial dont l'identifiant ne comporte que des « 1 » a un délai de propagation de nD. Un 1el reseau présente des performances très intéressantes, rappelées à la proposition 1 ci-dessus. Ces délais serviront de comparaison lorsque la structure sera adaptée à des 7 Malheureusement, il ne s'applique que lorsque le nombre N de pairs dans le réseau est du type 2n-1, et ne sait donc pas traiter de façon satisfaisante l'arrivée d'un pair dans le réseau ou le départ d'un pair du réseau. L'invention propose notamment de résoudre ces inconvénients. Objet et résumé de l'invention, Définitions et notations utilisées dans l'invention Dans la suite de ce document, on appellera 'la règle des réseaux hypercubes 10 complets de dimension n', ou plus simplement 'règle générale', l'algorithme de diffusion structuré présenté au chapitre précédent. Cette règle générale reprend notamment les règles Règle 1. « Règle xxx » énoncées dans ce document. On définit également les notions suivantes qui seront utilisées par la suite : - intervalle de temps : intervalle de temps (ou slot en anglais) utilisé par un pair 15 pour envoyer un bloc de données à un seul autre pair ; onnfonnérnentà l'invention, les intervalles de temps ne sont pas égaux et tiennent compte du temps de propagation et des éventuelles retransmissions du bloc ; - dimension n du réseau :, le nombre maximum de bits (nommés également éléments binaires) utilisés pour coder l'identifiant d'un pair dans le réseau ; 20 - niveau d'ordre i l'ensemble des identifiants de pairs (et par extension, l'ensemble des pairs correspondants) ayant un nombre i d'un élément binaire prédéterminé bO (de valeur O ou 1 fixée, commune à tous les pairs) ; cette notion s'applique aux identifiants : un identifiant est d'ordre i a'il comprend un nombre i dudit élément binaire bO ; 25 - niveau complet : niveau dont tous les identifiants ont été attribués à un pair du réseau ; - niveau vide, : niveau dont aucun identifiant n'a été attribué à un pair du réseau} - niveau incomplet :, niveau qui n'est ni complet, ni vide. 30 - règle definîssant l'ordre d'attribution des identifiants : pour un entier n, une population de N pairs, avec N Dans la suite du document on utilise la notation suivante : C(n,k) = QI L'invention vise un mécanisme structuré de diffusion de données dans un réseau pair à pair avec un nombre quelconque de pairs, qui s'adapte aux arrivées et départs des 10 pairs, et qui change uniquement localement le fonctionnement du réseau. L'invention vise plus précisément les systèmes d'aiguillage du réseau, les pairs du réseau, l'unité de gestion du réseau et les procédés mis en oeuvre par ces entités, respectivement nommés « procédé de communication de données », « procédé de diffusion de donnéeS» et « procédé de contrôle ». 15 Ainsi, et selon un premier aspect, l'invention concerne une unité de gestion apte à être utilisée dans un réseau pair à pair, cette unité de gestion comportant : - desnnVyensde sélection d'une dimension n du réseau; - des moyens de détermination des pairs présents dans le réseau ; - des moyens d'attribution à chacun desdits pairs présents d'un identifiant 20 comprenant des éléments binaires, l'attribution des identifiants se faisant en respectant un ordre prédéfini d'attribution des niveaux, un niveau étant constitué par l'ensemble des identifiants comprenant un nombre j d'un élément binaire prédéterminé ; - des moyens de fourniture, à au moins un système d'aiguillage en charge d'au moins un pair présent : 25 - de l'identifiant de ce pair présent ; et - d'informations permettant à ce système d'aiguillage de déterminer le caractère complet, vide ou incomplet du niveau de référence Lauquæ! appartient l'identifiant de ce pair présent et d'au moins un niveau suivant ce niveau de référence dans l'ordre d'attribution des niveaux. 30 Corrélativement, l'invention concerne un procedé de contrôle d'un réseau pair à pair, ce procédé étant mis en oeuvre par une unité de gestion, comportant : - une étape de sélection d'une dimension n du réseau ; - une étape de détermination les pairs présents dans le réseau ; - une étape d'attribution a chacun desdits pairs presents d'un identifiant 10 un ordre prédéfini d'attribution des niveaux, un niveau étant constitué par l'ensemble des identifiants comprenant un nombre j d'un élément binaire prédéterminé; - une étape de fourniture, à au moins un système d'aiguillage en charge d'au moins un pair présent : ~ - de l'identifiant de ce pair présent; et -dinfnrmations permettant à ce système d'aiguillage de déterminer le caractère complet, vide ou incomplet du niveau de référence Lauque! appartient l'identifiant de ce pair présent et d'au moins un niveau suivant ce niveau de référence dans l'ordre d'attribution des niveaux. 10 Dans un mode préféré de réalisation, le procédé de contrôle suivant l'invention comprend en outre une étape de détermination, pour chacun des pairs pvAaanta, d'un système d'aiguillage en charge de ce pair présent, apte à créer une liste ordonnée apte à contenir au moins un pair destinataire auquel cet pair présent doit transmettre un bloc de données qu'il a reçu. 15 Dans un mode de réalisation, le système d'aiguillage peut être incorporé dans le pair dont il est en charge. Dans ce cas l'invention vise par conséquent un procédé de contrôle d'un réseau pæirà pair, ce procédé étant mis en oeuvre par une unité de gestion, comportant : - une étape de sélection d'une dimension n du réseau ; 20 - une étape de détermination des pairs présents dans le réseau ; - une étape d'attribution à chacun des pairs présents d'un identifiant comprenant des éléments binaires, l'attribution des identifiants se faisant en respectant un ordre prédéfini d'attribution des niveaux, un niveau étant constitué par l'ensemble des identifîants comprenant un nombre j d'un élément binaire prédéterminé ; et 25 - uneétaped'envui,à chacun des pairs présents, - de son identifiant; et - d'informations permettant au pair présent de déterminer le caractère complet, vide ou incomplet du niveau de référence Lauque! appartient l'identifiant de ce pair présent et d'au moins un niveau suivant le niveau de référence dans l'ordre d'attribution 30 des niveaux. L'invention propose de modifier la méthode connue des réseaux hypercubes complets de dimension n, limitée dans l'état actuel de la technique aux réseaux de 2n-l. pairs, pour l'appliquer à un roseau pair à pair comportant un nombre quelconque de pairs. 11 Dans la suite de la description, les « autres règles » au sens de l'invention sont référencées « Rxx », afin de ne pas les confondre avec les règles Règle 1, Règle 2 et Règle 3 des réseaux hypercubes complets. D'une façon générale, le rôle prindpal de l'unité de gestion est de déterminer ~ les niveaux du réseau et d'attribuer les identifiants aux pairs du réseau d'une façon originale, les voisins de chacun des pairs étant déterminés conformément à la règle générale des hypercubes complets de dimension n. L'unité de gestion fournit ensuite à chaque système d'aiguillage en charge d'un pair présent, l'identifiant de ce pair et des informations lui permettant de déterminer si 10 l'identifiant de ce pair appartient à un niveau complet, et si au moins un de ses niveaux suivants est complet, incomplet ou vide, ainsi que l'adresse et l'identifiant de chacun de ses voisins. Ces informations permettent au système d'aiguillage de déterminer parfaitement le comportement du pair considéré, autrement dit de déterminer quels sont les blocs de données qu'il doit retransmettre et à qui. 15 De façon très avantageuse, l'unité de gestion selon l'invention est capable de gérer un réseau comportant un nombre quelconque de pairs. Parai!!eucS/ il est remarquable de noter que l'unité de gestion ne fournit à un système d'aiguillage en charge d'un pair que l'identifiant de ce pair et des informations locales à l'environnement de ce pair, c'est-à-dire concernant le niveau auquel ce pair 20 appartient, ainsi que au moins un niveau suivant. Dans un mode particulier de réalisation, les informations envoyées par l'unité de gestion permettent au système d'aiguillage de déterminer si le niveau L-1 est complet ou vide. Dans un autre mode particulier de réalisation, les informations envoyées par 25 l'unité de gestion permettent en outre au système d'aiguillage de déterminer si le niveau L-2 est vide. Dans un mode particulier de réalisation, le procédé de contrôle selon l'invention comporte, sur réception d'un évènement déterminé, les étapes suivantes : - détermination d'un niveau d'attribution Lk; 30 - détermination des pairs auxquels un nouvel identifiant doit être attribué en raison de l'occurrence de cet événement, appelés « painaà identifier » ; - attribution, à au moins un pair à identifier, d'un identifiant appartenant au niveau d'attribution Lk} - detcrminætion des pairs conservant leurs identifiants nnais impactés par !'évenemcnt 35 (lits palis à [-Minet 12 - fourniture, à au moins un système d'aiguillage en charge d'au moins un pair à identifier, du nouvel identifiant de ce pair ; -fnurniture, à au moins un système d'aiguillage en charge d'au moins un pair à identifier ou à notifier, d'informations lui permettant de déterminer au moins : 5 - si le niveau de référence L, auquel appartient l'identifiant de ce pair à identifier ou à notifier est complet - si le niveau L-1, suivant le niveau L dans l'ordre d'attribution des niveaux, est complet ou vide. Dans un mode particulier de réalisation, l'unité de gestion fournit en outre, à au 10 moins un système d'aiguillage en charge d'au moins un pair à identifier ou à notifier, des d'informations lui permettant de déterminer si le niveau L-2 est vide. Ainsi, l'unité de gestion selon l'invention détermine les pairs impactés par un événement survenant dans le réseau, et communique aux systèmes d'aiguillage en charge de ces pairs les informations du même type que celles communiquées à 15 l'initialisation du réseau pour qu'ils puissent modifier leurs comportements pour réagir à cet événement. Il est fondamental de bien noter, que l'invention n'impacte le fonctionnement du réseau que localement, seuls les systèmes d'aiguillage en charge des pairs impactés par l'événement recevant des informations de l'unité de gestion. 20 L'unité de gestion selon l'invention peut en particulier réagir aux événements constitués par l'arrivée d'un nouveau pair dans le réseau lorsqu'un niveau du réseau au moins est incomplet et par le départ d'un pair du réseau. Parconséquent, dans un mode particulier de réalisation du procédé de contrôle, lorsque l'événement précité correspond à l'arrivée d'un nouveau pair dans un réseau dont 25 au moins un niveau est incomplet : - ledit niveau d'attribution Lk est : - le dernier niveau Lderatt, dans lequel les identifiants ont été attribués si ce niveau n'est pas complet ou - le niveau Lderatt -1, suivant le niveau Lderatt dans l'ordre d'attribution des 30 niveaux, si le dernier niveau Lderatt est complet ' !e seul pair à identifier est le nouveau pair et - les pairs à notifier sont : - !esvoisins du nouveau pair~ et - !es pair, 4'~ n/vcno d'aMT/n`ttinn Lk et du niveau Lh+1, précédant te niveau 1 'e 35 dans rote 1 Ittribution niveau Dans un mode particulier de réalisation, le pair selon l'invention comporte en outre un sous-système pour sélectionner une règle utilisée pour déterminer cet ensemble, ce sous-système étant conforme à un sous-système de sélection de règle d'un système d'aiguillage tel que mentionné ci-dessus. L'invention concerne aussi un procédé de diffusion de données mis en oeuvre par un pair dans un réseau pair à pair, ce procédé comportant : - une étape de réception d'un bloc de données numéroté ; - une étape d'obtention des adresses de l'ensemble des pairs destinataires du bloc, ces pairs destinataires étant déterminés par un système d'aiguillage mettant en oeuvre un procédé de communication de données tel mentionné ci-dessus ; et - une étape de transmission dudit bloc de données numéroté à au moins un pair destinataire dudit ensemble. Dans un mode particulier de réalisation, le système d'aiguillage selon l'invention comporte : un sous-système de sélection de règle comportant - des moyens d'obtention desdites informations ; et des moyens de sélection de la règle à partir desdites informations ; et un sous-système de détermination de pairs destinataires comprenant lesdits moyens de détermination de l'ensemble des pairs destinataires. Dans un mode particulier de réalisation de l'invention, l'unité de gestion selon 15 l'invention comporte en outre un sous-système pour sélectionner une réale utilisée pour 21 pair, ce sous-système étant conforme à un sous-système de sélection de règle d'un système d'aiguillage tel que mentionné ci-dessus. L'unité de gestion selon l'invention peut aussi comporter un sous-système pour déterminer cet ensemble, ce sous-système étant conforme à un sous-système de ~ détermination de pairs destinataires d'un système d'aiguillage tel que mentionné ci-dessus. Dans un mode particulier de réalisation, les différentes étapes du procédé de communication de données, les différentes étapes du procédé de contrôle et différentes étapes du procédé de diffusion selon l'invention sont déterminées par des instructions de 10 programmes d'ordinateurs. En conséquence, l'invention vise aussi un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en oeuvre par un ordinateur, ce programme comportant des instructions adaptées à la mise en oeuvre d'au moins une partie des étapes d'un procédé de communication de données tSl que mentionné ci- 15 dessus. Dans un mode particulier de réalisation, ce programme comporte des instructions pour ne mettre en oeuvre qu'une étape parmi l'étape de sélection de règle et l'étape de détermination des pairs destinataires. Dans un autre mode de réalisation, il comporte des instructions pour mettre en oeuvre ces deux étapes. De même, l'invention vise également un programme d'ordinateur sur un 20 support d'informations, ce programme étant susceptible d'être mis en oeuvre par un ordinateur, ce programme comportant des instructions adaptées à la mise en oeuvre des étapes du procédé de contrôle tel que mentionné ci-dessus. L'invention vise également un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en oeuvre par un ordinateur, 25 ce programme comportant des instructions adaptées à la mise en oeuvre des étapes du procédé de diffusion tel que mentionné ci-dessus. Ces programmes peuvent utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, hel que dans une forme partiellement compilée, ou dans n'importe 30 quelle autre forme souhaitable. L'invention vise aussi un support d'informations lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci dessus. Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker !e programme. Par exemp!e, le support peut comporter un moyen de 22 microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque disque dur. D'autre part, le support d'informations peut être un support transmissible tel qu'un aignal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon l'invention peut être en padjcu!ierté!échargé sur un réseau de type Internet. Alternativement, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question. Brève description des dessins D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci-dessous en référence aux dessins qui en illustrent un exemple de 15 réalisation dépourvu de tout caractère limitatif. Sur les figures : - la figure 1 représente des niveaux d'identifiants de pairs dans un réseau de dimension 4, conformément à un mode particulier de réalisation de l'invention ~!a figure 2 représente deux exemples d'ordres d'attribution des niveaux de la figure 1 selon un mode particulier de réalisation de l'invention ; 20 - la figure 3 représente, sous forme d'organigramme, les principales étapes d'un procédé de diffusion selon un mode particulier de réalisation de l'invention ; - la figure 3a représente un pair conforme à un mode particulier de réalisation de l'invention ; - les figures 4 et 5 représentent, sous forme d'organigramme, les principales 25 étapes d'un procédé de contrôle, mis en oeuvre par une unité de gestion conforme à un mode particulier de réalisation de l'invention ; - la figure 6 représente un changement de dimension de réseau effectué par une unité de gestion conformément à un mode particulier de réalisation de l'invention ; -!es figures 7 et 8 représentent, sous forme d'organigramme, les principales 30 étapes d'un procédé de communication de données, mis en oeuvre par un dispositif de communication de données selon un premier mode particulier de réalisation de l'invention ; - !eafiounss 9 et 1D représentent, sous forme d'organigramme, les principales ëiopes d'Vn procédé de communication de donnees, mis en oeuvre par un disposftif de 5 conlnlunicaUon ~e données se/on on deuxi~n~e Mode porUru!ier de /éa!isæboo de 10 23 - les figures 11 et 11a représentent un exemple d'obtention d'une liste ordonnée étendue conformément à un mode particulier de réalisation de l'invention ; - la figure 11b représente un exemple d'obtention d'un identifiant de base conformément à un mode particulier de réalisation de l'invention ; ~ - la figure 11c représente un exemple d'obtention d'un identifiant de base Confonnérnentà un autre mode particulier de réalisation de l'invention ; - la figure 12 représente un système d'aiguillage conforme à un mode particulier de réalisation de l'invention, sous la forme d'un dispositif d'aiguillage ; et - la figure 13 représente une unité de gestion conforme à un mode particulier 10 de réalisation de l'invention. Description détaillée d'un premier mode de réalisation de l'invention Nous allons maintenant décrire une unité de gestion 10 et un système 15 d'aiguillage DA conformes à un premier mode de réalisation de l'invention. On rappelle que l'invention se situe dans le contexte d'un réseau de N pairs, ce réseau étant organisé en niveaux ordonnés. La figure 1 représente, dans un réseau de dimension 4, quatre niveaux d'identifiants, ces niveaux L3, L2, L1, LU étant ordonnés dans l'ordre décroissant du 20 nombre de «O»dans leurs identifiants. Conformément au mode particulier de réalisation de l'invention décrit ici, les identifiants des pairs sont attribués par l'unité de gestion 10, par ordre de niveau décroissant, et pris dans un ordre quelconque au sein d'un même niveau. La figure 2 présente deux exemples d'ordres d'attribution. 25 La figure 13 représente une unité de gestion 10 conforme à un mode particulier de réalisation. Dans le mode de réalisation décrit ici, cette unité de gestion 10 a l'architecture matérielle d'un ordinateur. Elle comporte un processeur 11, une mémoire morte 12, une mémoire vive 13, une mémoire non volatile réinscriptible 14 et des moyens de 30 communication 15 avec les systèmes d'aiguillage en charge des pairs du réseau. Ces moyens de communication 15 peuvent être de moyens de communication interne, via un bus de de données, et/ou externe via le réseau. Lo mémoire motte 12 constitue un support conforme à l'Invention, lisible par le processeur 11 at sur !oqoe! esL en/egisbe un prognarnmne dbrdinaieor Prr^')_ compncnant des inst/ucMons pou/ !'cxëcuLion des e1apes criorucëdé de cmnbÜ!e ',` l'invention iitt 24 La mémoire morte 12 mémorise aussi un élément binaire bO, en l'espèce le bit «O», ce bit étant utilisé par l'unité de gestion 10 pour construire les identifiants des pairs comme décrit à la figure 1. La mémoire non volatile réinscriptible 14 comporte un registre pour mémoriser la ~ dimension n du réseau. Cette dimension n doit respecter l'inégalité N 30 3.1.1 Gestion de l'arrivée d'un nouveau pair dans le réseau Dans le mode de rea!isohon décrit ici, si l'événement précité correspond à l'arrivée ARR d'un nouveau pair NPPi dans le réseau, un niveau au moins de ce réseau étant incomplet : - rc niveau d'ottribuMor Lk(étape G8D) est yedernier niveau LUerott dons !eque! - le nouveau pair NPPi est le seul pair Pjm à identifier, avec un nouvel identifiant choisi dans le niveau d'attribution Lk ; et - les pairs Pqr à notifier (étape G210) sont les voisins de ce nouveau pair, et les pairs du niveau d'attribution Lk et du niveau précédent Lk+1 si le niveau d'attribution a été complété par l'arrivée du nouveau pair. 3.1.2 Gestion du départ d'un pair du réseau Dans le mode de réalisation décrit ici, si l'événement précité correspond au départ DEP d'un pair sortant PSj du réseau (étape G110), si l'identifiant de ce pair sortant 10 appartient au dernier niveau Lderatt dans lequel les identifiants ont été attribués, aucun pair n'est à identifier, et l'identifiant du pair sortant devient disponible. En revanche, si l'identifiant du pair sortant n'appartient pas au dernier niveau Lderatt dans lequel les identifiants ont été attribués : - le seul pair Pjm à identifier (étape G130) est un pair quelconque du dernier 15 niveau Lderatt, dit « pair remplaçant », ce pair remplaçant étant identifié par l'identifiant du pair sortant. L'identifiant du pair remplaçant devient disponible ; - les pairs Pqr à notifier (étape G210) sont les voisins du pair sortant et du pair remplaçant et, si le dernier niveau Lderatt dans lequel les identifiants ont été attribués était complet avant le départ du pair sortant, les pairs de ce niveau Lderatt et du niveau 20 Lderatt+1 précédent. 3.1.3 Communication d'adresse Dans le mode de réalisation décrit ici, le procédé de contrôle selon l'invention 25 comporte en outre : - une étape G63 de réception d'une requête émise par un système d'aiguillage pour obtenir l'adresse d'un pair identifié dans la requête ; et - une étape G65 d'obtention et d'envoi de cette adresse à ce système d'aiguillage. 30 31.4 Fusion de deux sous-réseaux Nous décrivons un réseau de diffusion de données comportant N pairs, basé sur un hypercube partiel, avec N Dans un mode particulier de rea!isaUon, la dimension n du réseau est choisie par !'unité de gestfon en fonction du nombre N de pairs présents dans !e réseau de telle sorte 30 En gardant une taille limitée pour la proforéseaux linéaires, et des demi bes on obtient à la fois des délais de propagation et des délais de transmission courts. On effet, on note que les hypercubes partiels avec un nombre de niveaux égal à n/2 ont des propriétés intéressantes en terme de performance, comme démontré ci-dessous. On suppose qu'il existe un niveau ! incomplet avec ! = (n/2) - 1 Cette valeur maximise C(n-1, !)n à savoir la taille du premier sous-niveau, égale dans ce caSà [(n-1/ n/2 - 1). 10 Elle permet de stocker le nombre maximum de pairs pour un nombre k donné de sous-niveaux, en gardant des délais faibles. Comme ! 3.2 Fonctionnement général d'un système d'aiguillage du réseau 25 On décrit maintenant le comportement d'un système d'aiguillage DA dans un premier mode de réalisation. II met en oeuvre le procédé de communication de la figure 7. Ses moyens 115 de communication sont aptes à obtenir ou à recevoir, au cours d'une étape P10, la dimension n du réseau et un identifiant unique IDi destiné à identifier 30 un pair. Le processeur 111 est apte à obtenir !'e!ëment binaire [DO au cours d'une étape P10 et à déterminer, au cours d'une étape P20 le niveau L de réference auquel appartient son identifiant IDL Ses moyens 115 de communication !/.i permettent d'obtenir ou de recevoir, aV 35 cours d'une etape P30 des nfornIdIlOn', IUr tMIner SI Ce HlVeaU de 31 référence L est complet et si le niveau L-i suivant ce niveau de référence est complet ou vide. Le processeur 111 permet au système d'aiguillage DAi de déterminer (étapes P50, P60) une règle de diffusion des données dans le réseau à partir de ces informations. Dans ce premier mode de réalisation, cette règle est la règle Ades hypercubes complets de niveau n si le niveau L-1 est complet, dans tous les autres cas, une autre règle R1, R21 ou R22 déterminée en tenant compte des informations reçues à l'étape P30. Plus précisément, dans ce mode de réalisation, la règle R1 est choisie si 10 l'identifiant du pair considéré appartient à un niveau Lcomplet, le niveau L-1 étant vide. Cette règle est détaillée ci-dessous. 3.2.1 Règle R1 On considère d'abord une réalisation possible dans le cas où la population est telle que le dernier niveau d'attribution est complet, ce qui signifie qu'il y a 15 suffisamment de pairs présents pour utiliser tous les identifiants dans ce dernier niveau. On utilise alors la règle de routage suivante : Règle 5 : Dans un groupe de pairs incomplet avec un dernier niveau 1 complet et un niveau 1-1 vide, lorsque le pair destinataire théorique est absent, le pair émetteur envoie son bloc de données au seul pair du niveau ! auquel le pair 20 destinataire théorique l'aurait envoyé d'après la règle générale. Proposition 6 : Dans un groupe de pairs incomplet avec un dernier niveau ! complet et un niveau 1-1 vide, si le routage est effectué en appliquant la Règle 3 et la Règle 5, tous les pairs reçoivent les blocs de données à temps. Cela garantit que le délai total de diffusion (en l'absence de délai de propagation) est de n intervalles de 25 temps. En effet, les blocs de données sont propagés correctement et dans les temps. Soit b un pair de niveau ! supposé recevoir un bloc d'un pair d'identifiant b' de niveau 1-1 dans un groupe complet de pairs ; b' est inutilisé. Puisque b' envoie son bloc de données au niveau supérieur, b ne retransmet pas son bloc. Cette 30 transmission ne peut donc en aucun cas induire de retard. Soit b" le pair qui aurait envoyé le bloc de données à b', b" étant au niveau I. Lorsque b" essaie d'envoyer son bloc à b', il dëtermine que l 'Identifiant b' n'est pas attribué, et il envoie le bloc au dernier destinataire de b' soit b. b reçoit donc tous ses blocs de données, et b est l'unique destine-bon de transmission pour !e pair b" dans l'intervalle de temps. 32 b' est le destinataire théorique absent au sens de l'invention ; et b" est le pair qui met en oeuvre l'invention. Une implémentation possible de la règle RI correspond aux étapes P500 à 5 P560 de la figure 8. Dans ce mode de réalisation, cette règle comporte plus précisément une étape P500 de détermination confonnémentà la règle Rgénéna!e, à partir du numéro K d'un bloc numéroté BKet de !'identifiant I0 du pair mettant en oeuvre l'invention, d'une liste ordonnée L04 comportant les identifiants IDTij des pairs destinataires théoriques de ce 10 bloc BK.; Puis, pour chacun des identifiants IDTij des destinataires théoriques pris dans l'ordre de la liste ordonnée k04, on teste au cours d'une étape P550 si cet identifiant IDTij appartient au niveau L-i. Si c'est le cas, la règle R1 comporte une étape P510 de détermination des 15 récepteurs théoriques RTKi auxquels le destinataire théorique serait susceptible de transmettre le bloc numéroté BK. Au cours d'une étape P520, le pair mettant en oeuvre l'invention obtient, parmi les récepteurs théoriques RTKi, le pair destinataire PD dont l'identifiant appartient au niveau L. 20 Ce pair destinataire PD est ensuite ajouté au cours d'une étape P390, à la liste ordonnée LDk de pairs destinataires. L'étape d'ajout de ce pair comprend une sous-étape d'obtention de l'adresse du pair. L'obtention de l'adresse du pair peut consister, par exemple, en l'émission d'une requête contenant l'identifiant du pair destinataire vers l'unité de gestion, L'unité de 25 gestion reçoit cette requête au cours d'une étape G63 et envoie, au cours d'une étape G65, un message contenant l'adresse du pair identifié dans la requête. Le système d'aiguillage mettant en oeuvre l'invention reçoit le message contenant l'adresse du pair destinataire. Alternativement, l'adresse du paire destinataire peut être envoyée par l'unité de gestion lors d'une étape G60 d'envoi à chacun des systèmes d'aiguillage en charge 30 des pairs présents, de l'identifiant et de l'adresse de chacun des voisins de ces pairs présents, ou lors d'une étape G220 d'envoi à chacun des systèmes d'aiguillage en charge des pairs Pjm à identifier suite à la détection d'un événement, de !'identifiant et de l'adresse de chacun des voisins de ces pairs pjm à idenb[ier. Cette adresse est reçue par !C dispositif système mettant en oeuvre l'invention 33 réinscriptible 114. L'adresse du pair destinataire peut être obtenue par lecture dans cette mémoire non-volatile réinscriptible. Lmrsqu1l est déterminé à l'étape P550 que l'identifiant IDTij de destinataire théorique appartient au niveau L+1, le pair identifié par !'identUiantIC7Tij est ajouté à la liste ordonnée LDkd8 pairs destinataires. 3.2.2 Dernier niveau incomplet comportant au maximum C(n-1, 1) pairs La proposition 6 ne s'applique pas lorsque le dernier niveau 1 est incomplet. La Règle 5 permet aux pairs de niveau ! de rebondir sur les pairs absents de niveau 1-1 10 et de transmettre un bloc aux pairs de niveau!. Mais lorsque le niveau ! est incomplet, il peut se produire une transmission vers un pair absent, soit une transmission perdue. Comme, toutes les transmissions doivent être utiles dans chacun des intervalles de temps, certains blocs de données nécessaires n'atteindront pas des destinataires. 15 Dans le mode de réalisation décrit ici, on utilise une structure de diffusion qui utilise les relations des coefficients binomiaux. Un niveau ! est composé de toutes les combinaisons binaires de longueur n cornprenant! « O». II yen a C(n, !). Le niveau ! doit recevoir n.C(n, 1) blocs de données de ses voisins. Selon la 20 proposition 4 : n.C(n,!) =U+1\.{(n,!+1) +(n-!+1),C(n,1-1). Cette relation permet d'identifier le saut suivant. Proposition 7 : Le nombre maximum de pairs dans un niveau 1 incomplet qui peuvent recevoir leurs blocs de données uniquement du niveau supérieur est : 25 x=(!+1).[(n, 1+1)/n =[(n-1, !). ()nconsidère [(n-1, !) pairs ou moins dans un niveau ! incomplet. Ces pairs sont dits appartenir à un premier sous-niveau. On peut démontrer comment tous les pairs de ce premier sous-niveau 1 peuvent recevoir tous les blocs de données du niveau 1+1. Il y a au plus C(n-1, 1) pairs 30 dans ce sous-niveau. Ils peuvent être représentés sur n-1 bits d1. . .d1 dans lesquels 1 sont' égamO»^ Pour trouver, l'émetteur du bloc de données k au pair A identifié on considère le pair fictif Bi de niveau !, dans un système de niveau ! complet avec l'identifiant rf^.l...dk1dd obtenu en inserant un 1 en position k dans !'identifiant 35 34 Pair Position du bit Btantdomré que Bk a un 1 en position k, il retransmet le bloc k. Il reçoit donc Uoraqu'il est présent) le bloc k d'un unique pair Ck du niveau supérieur 1+1. Puis Ck transmet ce bloc au pair A. Cela définit un ancêtre unique pour chaque bloc et chaque pair dans le premier sous-niveau. ~ Or, il n'est pas nécessaire que chaque pair du niveau 1+1 transmette plus de 1+1 blocs au premier sous-niveau. En effet, considérons un pair C de niveau 1+1 qui transmet le bloc k à l'instant i au niveau I. L'identifiant de C possède un 1 en position ket des «O» de la position k-1 à la position i (avec d/=Opour 'dek-1b i+1). 10 Donc à l'instant i, le pair C transmet le bloc k à l'unique pair du sous-niveau ! d'identifiant de longueur n-1 dn...dk+Iclk.l...di,11di_1 ...di. On peut en déduire la règle de routage suivante ; Règle 6 : Dans un groupe de pairs incomplet, un pair du dernier niveau 1+1 complet route un paquet comme décrit précédemment, si le pair A correspondant est présent 15 au niveau inférieur L Pour tout pair dans le premier sous niveau d'un niveau ! incomplet, n opportunités de transmission ont été utilisées par les pairs du niveau 1+1 qui auraient du être adressées aux autres pairs du niveau 1+1. Donc chaque pair présent dans le premier sous-niveau (ou éventuellement ses descendants) doit transmettre n 20 blocs de données aux pairs qui ne les ont pas reçus. Pour identifier quels blocs de données à rmtournerà quels pairs, on procède de la façon suivante. Snitdn.4...di l'identifiant de longueur n-1 d'un pair A au premier sous-niveau. A ce pair A on peut associer n pairs Bk en insérant un « 1 » entre dk+1 et dk dans 25 l'identifiant de A pour k allant de 1 à n. Pour chaque pair Bk, A ou l'un de ses descendants doit transmettre le bloc de données k au pair Dk d'identifiant d^..x}k+10dk/..dz. 30 D^ est le pair a qui [k aurait envoyé le bloc k si A n'avait pas été présent. Cela définit une bkicd!nn entre !es blocs 711 n^oni pas été reçus am niveau !+l AdV 35 niveau 1+1) à cause de la présence de A au niveau 1 incomplet et les blocs retransmis par le pair A (ou l'un de ses descendants) au niveau !+1. Ceci se résume dans la règle de routage et dans la proposition suivante. Règle 7 : Dans un groupe de pairs incomplet, un pair du dernier niveau ! ~ incomplet (ou ses descendants) renvoie les blocs de données aux pairs de niveau 1+1 comme il vient d'être décrit. Proposition 8 : Dans un groupe de pairs incomplet, avec un dernier niveau ! incomplet, si les pairs sont routés suivant les règles 3, 5, 6, et 7, tous les pairs reçoivent leurs blocs de données. 10 Le premier sous-niveau peut être interprété connnoe !a mnaximunn de C(n-1, !) source virtuelles étant donné que les pairs de ce niveau ne s'appuient pas sur des pairs de niveau équivalent ou inférieur pour recevoir leurs blocs de données. Ces sources virtuelles peuvent avoir à diffuser leurs blocs aux éventuels autres pairs du niveau 1 incomplet. Si ces sources génèrent des sous-réseaux linéaires, le délai de ces 15 sous-réseaux croit linéairement avec leurs tailles. Ces sources peuvent aussi générer de nouveaux réseaux partiels (hypercubes). En tout état de cause, le niveau supérieur 1+1 requiert que lui soient retransmis C(n, !+1) blocs depuis ce niveau incomplet. Une organisation possible d'un niveau incomplet dans un réseau linéaire est 20 présentée infra. Toutefois cette organisation peut mener à un nombre total de retransmissions d'un bloc (depuis son émission initiale) qui est sous-optimale. II en résultera des délais et des retards, dans le cas de la diffusion d'un flux vidéo, qui peuvent être désagréables pour les utilisateurs. Nous présenterons plus loin comment le dernier niveau non vide peut être organisé pour que la diffusion des blocs dans le 25 réseau soit optimale, c'est-à-dire obtenue en moins de [log2(N)] retransmissions depuis l'émission initiale, quel que soit le taux de remplissage de ce niveau. 3.2.3. Topologie linéaire de niveau 1 incomplet On se place dans le cas où les pairs de niveau 1 restants sont organisés en 30 réseaux linéaires prenant leurs origines dans des sources d'un premier sous-niveau. Dans un réseau linéaire, chaque pair, mis à part la source, a un ancêtre unique. Chaque pair reçoit tous ses blocs de donnees de son ancêtre On peut définir des sous-niveaux successifs dépendant de la distance, en nombre de sauts, en partant du premier sousnivcoo. 36 Le dernier descendant dans un réseau linéaire a la responsabilité de transmettre les blocs de données qu'il a reçu aux voisins d'une source virtuelle de niveau 1+1, comme défini dans la Règle 7. Dans un mode particulier de réalisation un pair appartenant à un réseau linéaire ~ se voit attribué un identifiant comportant deux composantes. Une première composante identique à l'identifiant sur n-1 bits à l'origine du réseau linaire auquel il appartient. Et une deuxième composante numérique incrémentée de la valeur « un » à chaque rajout d'un pair dans le réseau linéaire. Pour chaque bloc de donnée numéroté k, les pairs appartenant à un réseau linéaire et le pair du niveau !+1 auquel le dernier pair du réseau 10 linéaire doit retransmettre le bloc kfonnent une liste ordonnée LOE, telle que décrite dans la figure 11, générée à partir d'un numéro de bloc k et d'un identifiant générateur obtenu en plaçant le bit « 1 » en position « k* dans l'identifiant à l'origine du réseau linéaire. Ce mode de réalisation des listes de diffusion LOE dans un dernier niveau non vide du réseau présente un caractère de simplicité extrême en terme de gestion du 15 réseau lors des arrivées et des départs de pairs. Par contre, comme nous allons le montrer, il aboutit à des délais sous-optimaux. Nous montrons dans la suite une méthode alternative de réalisation des listes LOE, plus complexe à gérer, mais optimale en termes de nombre de retransmissions avant réception finales d'un bloc. Il peut être nécessaire d'ajouter plusieurs sous-niveaux avant d'obtenir C(n, !) 20 pairs présents pour former un niveau 1 complet. La profondeur maximum de ces réseaux linéaires avant que ce nombre soit atteint est bornée comme mentionné dans la proposition suivante. Proposition 9 : Un niveau incomplet 1 peut être décomposé dans un nombre n/n-1 maximum de réseaux, chacun de taille C/n-1, !\, à l'exception du dernier sous- 25 niveau. En effet, le niveau I étant incomplet, il est composé de moins de [(n. !) pairs. Ceux-ci peuvent être distribués Sur [1n-1, !\ possibles réseaux linéaires. Chacun a donc une longueur maximum CYn, U/ C(n-1, D = n (n-l) 30 Ce rapport décroît de n à 1 lorsque ! varie de n-1 à O. Pour ! dans FO ; n-ll/ ce rapport est inférieur ou égal à1+1, car : (n/n-l) y- /n-1U 20 ].2.4 Règles 21 et 22 De retour à l'étape P30, dans le premier mode de réalisation, - une règle R21 est choisie si le niveau L-1 est non vide, ce qui signifie que le pair 25 considéré ne se situe pas sur le dernier niveau où les identifiants ont été attribués - une règle R22 est choisie si le niveau L-1 est vide, le niveau L n'étant pas complet. Chacune de ces règles R21, R22 utilise des routines pour obtenir un identifiant 30 de base et une liste ordonnée étendue LOE dont l'obtention va maintenant être décrite en référence aux figures 11, 11a, 11b et 11c. 3.2.4.1 Identifiant de base D'une façon générale, un identifiant de base IDBqk est associé à un Identifiant de pair quelconque TDqet à numro Kq dun bloc de données numéroté quelconque. 35 Dans un modo , qsallon, idenlifiaut de hase est obtenu par une étape !e~~/~mmhon d:/ dcnUhan\ ~e pav ~'/emn~q1 38 IDq , suivie d'une étape P710 d'obtention dudit identifiant de base IDBqk à partir dudit identifiant de pair quelconque IDq par déplacement de la séquence de fin SEQq dans l'identifiant de pair quelconque IDq à une position Kq correspondant audit numéro de bloc quelconque, les autres éléments binaires de l'identifiant de pair quelconque IDq ~ étant décalés. Alternativement, l'identifiant de base est obtenu par une étape P701 de détermination d'une séquence de fin SEQq de l'identifiant de pair quelconque 3Dq,suivie d'une étape P711 de permutation circulaire des éléments binaires dudit identifiant de pair quelconque IDq de manière à placer ladite séquence de fin SEQq à une position Kq 10 correspondant audit numéro de bloc quelconque. D'une façon générale, quel que soit le mode de réalisation de l'invention, les règles R21 et R22 doivent utiliser la même méthode d'obtention de l'identifiant de base. 3.2.4.2 Liste ordonnée étendue LOE 15 D'une façon générale, la liste LOEest obtenue à partir d'un identifiant générateur IDGiet d'un bloc 8K de données numéroté K. Au cours d'une étape P600, on détermine un niveau d'ordre G, dit niveau générateur, auquel appartient cet identifiant générateur IDGj. Puis, au cours de la même étape P600, on détermine une liste ordonnée LOIjk 20 comportant une partie seulement des identifiants appartenant au niveau générateur G à partir de l'identifiant générateur IDGJ et du numéro K dudit bloc numéroté BK. Au cours d'une étape P610, on détermine une liste LDTjk des destinataires théoriques du bloc BK, auxquels le pair identifié par l'identifiant génénateurIDC0 serait susceptible de transmettre ledit bloc numéroté BK selon ladite règle générale R. 25 Puis, au cours d'une étape P620, on obtient, dans ladite liste LDTjk des destinataires théoriques, le pair dont l'identifiant IDE appartient au niveau G+1, dit identifiant d'extension. La liste ordonnée étendue LOE est obtenue, au cours d'une étape P630, en ajoutant l'identifiant IDE d'extension en dernière position dans la première liste ordonnée 30 LObk. 35 39 3.2.4.3 Obtention de l'identifiant de base et de la liste ordonnée étendue LOE dans un premier exemple On considère le dernier niveau L du réseau. Il peut être incomplet ou complet. Co niveau contient au maximum C(n,L) pairs. Ces pairs peuvent être classifiés en 1+1 ~ sous-niveaux : C(n,L) =C(n-1,L)+C}n-2,L-1)+ +C/n-L-1,U\. Dans ce mode de réalisation, le premier sous-niveau comprend les pairs avec un bit à «1» à droite, suivi de n-1 bits à gauche, dont L bits à «0». Le deuxième sous-niveau comprend les pairs avec les deux bits les plus à droite 10 à «10» à droite, suivi de n-2 bits à gauche, dont (L -1) bits à « O », et ainsi de suite jusqu'au dernier sous-niveau composé du seul pair avec L bitmà « o » à droite suivis d'un bit à «1»,suivi de(n-L-1) bits sans «0»à gauche. On appelle « séquence de fin » (wtn]i!er» en anglais) les bits à droite qui caractérisent un sous-ensemble. 15 Pour déterminer comment un pair 'A' appartenant à un sous-niveau du niveau L reçoit les blocs de données, on doit chercher ses ascendants dans le niveau L+l. On considère les bits qui composent une « séquence de Mn*, une telle séquence étant composée d'un nombre de « O» (ce nombre pouvant être nul) suivi d'un bit à « 1 » à gauche. 20 Cette 'séquence de fin' est décalée dans l'identifiant du pair 'A'. II existe n possibilités de décalage de la 'séquence de fin', et pour chaque possibilité le bit à « 1 » de la séquence prend une position différente dans l'identifiant de niveau n résultant. L'identifiant résultant du décalage plaçant le bit à « 1 » de la séquence de fin en une position k est l« L'ascendant (en général indirect du pair dans le niveau L pour le bloc de données k est le mëme que celui de son « identifiant de bose» pour le bloc k, c'est-à-dire l'ascendant, pour ce bloc de données k, du pair identifié par l'identifiant obtenu par 35 [e d~ra!age de !a ëquence de fin' dans !'identifiant de A tel que le bit « 1" est en On considère par exemple un niveau 2 incomplet dans un hypercube de dimension 5, et l'identifiant ' 10110'. Cet identifiant correspond à l'identifiant du pair `A/ du sous-niveau avec la 'séquence de fin '10'. L'ascendant, Ak, d8A pour le bloc de données Bk de numéro 4 est ~ le même que l'ascendant du pair '11001' pour ce bloc, où on reconnaît que `11001' est l'identifiant de base de A pour le bloc 4. Cet ascendanLAh a pour identifiant '11000' d'après la règle générale. II est à noter que d'autres identifiants de niveau 2 peuvent avoir le même ascendant Ak pour le bloc de donnée Bk de numéro 4 avec ce même procédé. Par exemple l'identifiant '10011' lorsqu'on place le '1' de sa 'séquence de fin '1" 10 en position 4 donne l'identifiant `11081', a le même ascendant Ak pour le le bloc de numéro 4. L'ensemble des pairs ayant un même identifiant de base, j, pour un bloc de numéro k peuvent être regroupés regroupés dans une liste LOIjk. Ainsi à tout desLinaLaioyj d'un bloc Bk provenant d'un niveau supérieur d'après 15 la règle générale, on peut associer une liste LOljk d'identifiants dans le même niveau que le destinataire. Cette association est biunivoque. Par ailleurs, tout pair A, pour tout bloc k, 8ppartientà une et une seule liste LO1jkqui peut être obtenue à partir de l'identifiant de base de A pour le bloc k. Cette liste peut être ordonnée, ce qui définit un processus de diffusion du bloc Bk parmi les pairs de la liste. Cet ordre est arbitraire, mais on peut 20 établir une règle pour ordonner de façon systématique les identifiants dans la liste. Une règle possible est d'ordonner les identifiants suivant la longueur décroissante de la taille de leur 'séquence de fin'. Ceci est illustré dans les séquences présentées à titre d'exemple dans la Table IV. Tout destinataire j d'un bloc 8k provenant d'un niveau supérieur doit 25 retransmettre ce bloc vers un destinataire j1 unique dans le niveau supérieur d'après la règle générale. Ainsi à tout destinataire j d'un bloc Bk provenant d'un niveau supérieur, on peut associer une liste étendue ordonnée LOE d'identifiants égale à la liste LO1ikà laquelle on a rajouté en fin de liste l'identifiant jl. Ainsi les listes LOE, obtenues à partir d'identifiants de base d'un niveau L et de 30 numéros de bloc k, définissent une règle possible, R22, de retransmission d'un bloc k par les pairs du niveau L. La table III représente les ascendants et descendants pour chaque bloc de données échangé par !æ pair` 10110' dont !a séquence de fin est 10 ». 5 Bloc de données 1 2 3 4 5 ascendant) + 1 00011 00110 10100 11000 10001 ascendant direct - - 11001 - pair 10110 01011 10110 10101 11001 10101 descendant direct 01011 10110 10101 11001 10101 descendant) + 1 01010 10100 10001 10001 00101 Table III La table IV représente comment le pair 10001' appartenant au niveau 3 de référence choisit ses descendants appelés 'pairs destinataires' PD pour chaque bloc de données dans le dernier niveau non vide, soit L = 2 dans cet exemple. Dans cet exemple on crée autant de listes ordonnées LOE que de destinataires du pair `10001' dans le niveau suivant d'après la règle générale. Pour chaque un intervalle de temps donné représenté par un '0' dans son identifiant, le pair `10001' possède un destinataire j dans le niveau inférieur, auquel on associe une liste LOE comme suit : Intervalle de temps 2 3 4 Bloc de données 5 5 5 Destinataire théorique 10011 10101 11001 ler choix 11100 10110 10011 2ème choix 01110 01011 01001 3ème choix 00111 00101 - 4ème choix 00011 - Table IV Dans cet exemple, le pair 10001' envoie le bloc k, initialement destiné à un pair j dans le niveau suivant d'après la règle générale, au premier pair présent dans la liste ordonnée LOE. Il existe au moins un tel pair présent car le dernier identifiant dans !a liste LOE appartient au même niveau que '10001' qui est nécessairement complet car suivi d'un niveau non vide. Un pair Pi clans le dernier niveau, recevant un bloc numéroté k, recherchera à quelle liste LUE partient. U traonmettro lb bloc au prochain pal pro tint riens U liste. 42 Ainsi l'ensemble des listes LOE définissent un processus de diffusion des blocs dans le dernier niveau non vide, tel que tout pair présent dans ce niveau reçoit tous les blocs quelques soient les pairs présents ou non dans le niveau. De plus ces listes assurent que les pairs du niveau précédent le dernier niveau recevront du niveau ~ inférieur les blocs qu'ils n'ont pas reçu du niveau supérieur et qu'il leur manque pour compléter leurs séquences de blocs. L'ensemble des listes LOE permettent aussi aux pairs du niveau supérieur, L+1, de déterminer vers quels pairs ils doivent transmettre un bloc numéroté k lorsque cette transmission doit se faire vers le niveau L suivant la règle général. Un tel pair A' du 10 niveau L+1, devant transmettre le bloc k à un pair A" du niveau L, détermine la liste LOE tel que le ferait un pair du niveau L si A" était son identifiant de base pour le bloc k. Le pair A' transmet alors le bloc k au premier pair présent dans la liste LOE. Ceci montre comment obtenir la liste LOE pour la règle 21 ci-dessous. La règle de constitution des listes LOE et la diffusion des blocs à l'intérieur de 15 ces listes assurent qu'au pire des cas les blocs diffusés suivant ces listes seront reçus après un nombre tohal de transmissions inférieur à r!ng,(N)-I depuis leur émission par la source, où [!og2(N)7eet le premier entier supérieur ou égal au logarithme en base « 2 » de N. Cette borne étant respectée si la dimension « n » du réseau est choisie telle que 2nkN 3.2.4.4 Obtention de l'identifiant de base et de la liste ordonnée étendue LOE dans un deuxième exemple On considère un pair 'A'. L'identifiant de ce pair possède une séquence de fin définie comme dans l'exemple précédant. Nous allons définir un nouveau procédé RA2 pour associer un « identifiant de base » au pair 'Ar pour tout bloc k. Suivant ce nouveao procédé!' identifiant de base » de `A" pour un bloc k est obtenu en décalant circulairement b totalité de l'Identifiant de la longueur de 1 iclerdifiant) tel que le bit 1 de sa séqueneu (le fin e ietiouve hvi 43 par exemple l'identifiant «».Toute les rotations circulaires peuvent s'obtenir en réitérant la rotation circulaire précédente. Comme précédemment il existe n possibilités de rotation, et pour chaque possibilité le bit à « 1 » de la séquence de fin prend une position différente dans ~ l'identifiant de niveau n résultant. L'identifiant résultant de la rotation plaçant le bit à « 1 » de la séquence de fin en une position keSt 1« 1 5 La table VI représente comment le pair '10001' appartenant au niveau 3 de référence choisit ses descendants appelés 'pairs destinataires' PD pour chaque bloc de données dans le dernier niveau non vide, soit L 2 dans cet exemple. Dans cet exemple on crée autant de listes ordonnées LOE que de destinataires du pair '10001' dans le niveau suivant d'après la règle générale. Pour chaque intervalle 2~ de temps donné représenté par un`O'dans son identifiant, le pair 10001' possède un dæotnatainej dans le niveau inférieur, auquel on associe une liste LOE comme suit : 10 45 Intervalle de temps 2 4 Bloc de données 5 Destinataire théorique 10011 10101 11001 _ _ ler choix 11100 101 0 10011 _ 2ème choix 01110 01011 01001 3ème choix 00111 00101 _ 4ème choix 00011 Table VI Dans cet exemple, le pair `1001'envoie le bloc k, initialement destiné à un pair j dans le niveau suivant d'après la règle générale, au premier pair présent dans la liste ordonnée LOE. Il existe au moins un bel pair présent car le dernier identifiant dans 5 la liste LOE appartient au même niveau que '10001' qui est nécessairement complet car suivi d'un niveau non vide. Un pair Pi dans le dernier niveau, recevant un bloc numéroté k, recherchera à quelle liste LOE il appartient. Il transmettra le bloc au prochain pair présent dans la liste. Ainsi l'ensemble des listes LOE définissent un processus de diffusion des blocs 10 dans le dernier niveau non vide, tel que tout pair présent dans ce niveau reçoit tous les blocs quelques soient les pairs présents ou non dans le niveau. De plus ces listes assurent que les pairs du niveau précédent le dernier niveau recevront du niveau inférieur les blocs qu'ils n'ont pas reçu du niveau supérieur et qu'il leur manque pour compléter leurs séquences de blocs. 15 La règle de constitution des listes L0Eet la diffusion des blocs à l'intérieur de ces listes assurent qu'au pire des cas les blocs diffusés suivant ces listes seront reçus après un nombre total de transmissions inférieur à r!ogz(N)l depuis leur émission par la source, où r!ogz(N)l est le premier entier supérieur ou égal au logarithme en base « 2 » de N. Cette borne étant respectée si la dimension « n » du réseau est choisie telle que 2n- 20 1S0 3.2.6 Règle R22 5 La règle R22 de diffusion d'un bloc BK de données numéroté s'applique si une deuxième condition est satisfaite. Dans le premier mode de réalisation décrit ici, cette deuxième condition est que le niveau de référence L auquel appartient le pair mettant en oeuvre l'invention est 10 incomplet. Lorsque cette deuxième condition est satisfaite, la règle R22 comporte une étape P400 de détermination d'un identifiant IDBik dit identifiant source, à partir de l'identifiant IDi du pair mettant en oeuvre l'invention et du numéro K du bloc BK. La règle R22 détermine ensuite, au cours d'une étape P410, la liste ordonnée 15 étendue LOE, oornmned^à décrit en néfévenceà la figure 11 ; à partir de l'identifiant de source IDBik et du numéro K du bloc numéroté BK. Au cours d'une étape P420, la règle R22 recherche l'identifiant IDi du pair mettant en oeuvre l'invention dans la liste ordonnée étendue LOE. Puis, au cours d'une étape P420, la règle R22 permet de déterminer un pair destinataire 20 PD identifié par le premier identifiant attribué A4 suivant l'identifiant I0 dans la liste ordonnée étendue LOE. Ce pair destinataire PD est ensuite ajouté au cours d'une étape P390, à la liste ordonnée LDk de pairs destinataires. Description d'un deuxième mode de réalisation de l'invention 4.1 Fonctionnement de l'unité de gestion Dans ce deuxième mode de réalisation de l'invention, l'unité de gestion communique aux systèmes d'aiguillage en charge des pairs présents à l'étape G50, en 30 plus des informations permettant aux systèmes d'aiguillage de déterminer si le niveau de référence L auquel appartient l'identifiant d'un pair considéré est complet et si le niveau L-1 est complet ou vide, des informations permettant à ce système d'aiguillage de detei miner si le niveau L-2 est vide. Lorsqu'un evencn/enLest détecté, !'unité de gestion envoie aux étapes G220 et 25 48 plus des informations décrites en référence au premier mode de réalisation, des d'informations Vernlettantà ce pair de déterminer si le niveau L-2 est vide. Lorsque l'évènement est constitué par l'arrivée d'un nouveau pair NPPi dans le réseau, les pairs Porà notifier de cet événement à l'étape G220, sont, en plus de ceux ~ décrits en référence au premier mode de réalisation, les pairs du niveau Lk+2, si l'identifiant dudit nouveau pair NPPi est le premier identifiant attribué dans son niveau. Lorsque l'évènement est constitué par le départ d'un pair sortant du réseau, les pairs Mlrà notifier à l'étape G230 comprennent, en plus de ceux décrits en référence au premier mode de réalisation, les pairs du niveau Lk+2 si l'identifiant du pair sortant PSj 10 ou du pair remplaçant PR était le seul de son niveau. 15 Dans ce mode de réalisation, le système d'aiguillage doit recevoir, de l'unité de 20 gestion, les informations lui permettant de déterminer si le niveau L est complet, si le niveau L-1 est complet ou vide, et si le niveau L-2 est vide. Dans ce mode de réalisation, le système d'aiguillage utilise la règle générale R des hypencubascomp!ets Si le niveau L-2 n'est pas vide. Dans ce mode de réalisation, le système d'aiguillage mettant en oeuvre 25 l'invention n'utilise jamais la règle R1. Il utilise la règle R21 si L-1 n'est pas vide (étape P100). %l utilise la règle R22 si le niveau L-1 est vide. Dans ce mode de réalisation l'étape P190 d'ajout du pair destinataire PD à la liste ordonnée LDk de pairs destinataires est similaire à l'étape P 390. 30 4.3 ImplénigntAtiorimatérielre Dans le deuxième mode de réalisation, l'architecture matérielle de l'unité de gestion et du système d'aiguillage est Identique à celle décrite en /ëkireoccaux figures 12 ct 13. 4.2 Fonctionnement du système d'aiguillage Le fonctionnement du système d'aiguillage dans ce deuxième mode de réalisation est décrit en référence aux figures 9 et 10. Ces figures sont similaires aux figures 7 et 8 pour les étapes P100, P300, P110, P310, P120, P320, P130, P330, P160, P360, P170, P370, correspondant à la règle R21 et pour les étapes P200, P400, P210, P410, P220, P420, correSpondantà la règle R22. 35 Seuls les programmes d'ordinateur iit PGVI2 sonf modifiés en c qui concerne les 49 4.4 Fonctionnement général d'un pair du réseau ~ On décrit maintenant le comportement d'un pair du réseau, en référence aux figures 3 et 3a. Dans le mode de réalisation décrit ici, ce pair Pi a l'architecture matérielle d'un ordinateur. Il comporte un processeur 21, une mémoire morte 22, une mémoire vive 23, une mémoire non volatile réinscriptible 24, des moyens de communication 25 avec les 10 systèmes d'aiguillage et des moyens de communication 26 avec les autres pairs du réseau. Lorsque le système d'aiguillage est incorporé dans le pair Pi, les moyens de communication 25 sont internes à ce pair et peuvent être constitués par un bus de données. 15 Lorsque le système d'aiguillage est externe au pair Pi, les moyens de communication 25 et 26 peuvent être identiques. La mémoire morte 22 constitue un support conforme à l'invention, lisible par le processeur 21 et sur lequel est enregistré un programme d'ordinateur PGM3 comprenant des instructions pour l'exécution des étapes d'un procédé de diffusion selon l'invention 20 dont les principales étapes seront décrites en référence à la figure 3. Ce pair comporte des moyens 26 de réception de données numériques diffusées sous forme de blocs numérotés BK. Il reçoit un bloc de données au cours d'une étape T1O, il obtient ensuite au cours d'une étape T20 la liste ordonnée LDk pouvant contenir au moins un pair destinataire de ce bloc de données BK numéroté, cette liste étant créée 25 par un système d'aiguillage DA mettant en oeuvre l'invention. Dans un mode particulier de réalisation de l'invention le système d'aiguillage peut être intégré audit pair, dans ce cas l'étape T20 d'obtention utilise une communication interne, via un bus de données. Alternativement, si le système d'aiguillage DA est intégré à l'unité de gestion, 30 l'étape T20 d'obtention utilise une communication externe, via le réseau. Le pair utilise les moyens de communications 26 avec les autres pairs du rëseæu pour transmettre ensuite au cours d'une étape T30 le bloc de données BK numéroté à chaque pair appartenant à la liste ordonnée LDk des pairs destinataires.