Procédé de communication de données mis en œuyre par un système d'aiguillage dans un réseau pair à pair

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 d'initialisation du 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 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 à 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 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 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 préliminaire le modèle de réseaux de pairs connu de l'homme du métier sous le nom de « réseau hypercube complet de dimension n », les avantages et les limites de ce modèle.

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 « chunks »).

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

Il a été démontré dans le document « Y. Liu, "On the minimum delay peer-to-peer video streaming : how realtime can it be?" in MULTIMEDIA '07 : Proceedings of the l$ ^h international conférence on Multimedia. New York, NY, USA : ACM, 2007, pp. 127-136» 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 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 ^{n l} < N <2 ⁿ -l où n est un entier naturel, le temps de diffusion optimal est n intervalles de temps. Nous décrivons maintenant comment les transmissions peuvent être organisées lorsque le nombre N de pairs est de la forme N = 2 ⁿ -1.

Etant donné que chaque pair transmet un bloc de données par intervalle de 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° + 7\ + ...+2 ^{n l} .

Puisque l'on fait l'hypothèse qu'il existe 2 ⁿ -l 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 les suivantes, chaque élément de la séquence identifiant le numéro du 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, 9, 9, 6, 5, 4, 4, 4, 1}

{9, 8, 8, 6, 5, 4, 4, 4, 1} II 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 « 0 » 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 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.

La séquence composée exclusivement d'éléments binaires de valeur « 0 » est non significative, puisqu'elle correspondrait à l'émission répétée du même bloc de données.

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

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) et (2) par la séquence unique : 1, 4, 4, 4, 1, le temps étant compté de droite à gauche de 1 à 5 avant de se répéter.

Cette relation entre l'identifiant du pair et la séquence de transmission se résume de la façon suivante :

Règle 1 : 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, un pair dont l'identifiant comporte un « 1 » à la position k=t modulo n transmet un bloc pour la dernière fois.

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 à l'instant t-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 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 numéros de blocs égaux modulo n.

1.1.3. Détermination des destinataires des blocs

On note e, le nombre binaire constitué de « 0 » avec un seul « 1 » en position i. Les règles suivantes définissent à qui un bloc doit être transmis. Cette méthode 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+e _t .

Puisque b+e _t +e _t =b, le pair destinataire b+e _t envoie aussi un bloc au pair b à l'instant t.

On notera qu'un pair envoie des blocs et ne reçoit des blocs que de n pairs différents, dits Voisins'. La Table 1 illustre quels blocs sont transmis et reçus par le pair d'identifiant 01001.

Table 1

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 N = 2n - 1 pairs. En effet :

- un pair dont l'identifiant comporte un « 0 » à 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 b comporte 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 3).

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 « descendants » 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 bloc de données p.

Proposition 2 : Il 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érieur à son propre niveau mais en aucun cas avec des pairs de son niveau.

Proposition 3 : Selon le Lemme 3, un pair recevant un bloc de données d'un niveau supérieur doit le retransmettre ; conformément au Lemme 2, un pair recevant un bloc de données d'un niveau inférieur ne le retransmet pas.

De façon corollaire (corollaire 1), si un pair de niveau I doit envoyer un bloc de données k fois, 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 I et tous ses autres descendants de niveau 1-1 ou inférieur. Ses descendants de niveaux 1+1 et I ne retransmettent pas le bloc de données.

Proposition 4 : Un pair de niveau I a n-l descendants directs de niveau 1+1, I descendants directs de niveau 1-1, I descendants de niveau I, tous ses autres descendants de niveaux 1-1 ou inférieur. Ses descendants de niveaux 1+1 et I ne retransmettent pas le bloc de données.

Proposition 5 : Un pair de niveau I a n-l ancêtres directs de niveau 1+1, I ancêtres directs de niveau 1-1, I ancêtres de niveau I, tous ses autres ancêtres de niveaux 1+1 ou supérieur. Les blocs reçus des ascendants de niveau 1-1 et I ne sont pas retransmis.

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 « 0 » dans leur identifiant reçoivent le bloc n transmissions après la source, 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 « 0 » 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-l+2)D. Le pair spécial dont l'identifiant ne comporte que des « 1 » a un délai de propagation de nD.

Un tel réseau 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 populations de N pairs, N différent de 2 ⁿ -l, conformément à l'invention.

Malheureusement, il ne s'applique que lorsque le nombre N de pairs dans le réseau est du type 2 ⁿ -l, 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 complets de dimension n', ou plus simplement Yè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 pour envoyer un bloc de données à un seul autre pair ; conformément à 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 ;

- 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 0 ou 1 fixée, commune à tous les pairs) ; cette notion s'applique aux identifiants : un identifiant est d'ordre i s'il comprend un nombre i dudit élément binaire bO ;

- 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.

- règle définissant l'ordre d'attribution des identifiants : pour un entier n, une population de N pairs, avec N < 2 ⁿ -l, et un élément binaire bO, on attribue à chacun des pairs un identifiant codé sur n bits ; lorsque l'hypercube est incomplet, les identifiants sont attribués selon une règle d'attribution, définissant un ordre d'attribution des niveaux existants compte-tenu de la dimension n du réseau :

soit en affectant en priorité le niveau d'ordre le plus élevé et en procédant ensuite par niveau d'ordre décroissant ;

soit au contraire en affectant en priorité le niveau d'ordre le plus bas et en procédant ensuite par niveau d'ordre croissant.

L'ordre d'attribution des identifiants de même niveau est indifférent. Quel que soit l'ordre d'attribution choisi, dans le cas d'un hypercube incomplet, un ou plusieurs niveaux peuvent ne pas être attribués. Il peut en outre y avoir un niveau attribué seulement partiellement.

Dans la suite de ce document, on choisira « 0 » pour l'élément binaire prédéterminé, et les identifiants seront attribués dans l'ordre décroissant du nombre de « 0 » dans leurs identifiants, à l'exception de l'identifiant ne comportant que des « 0 », réservé à la source. Cet ordre d'attribution est illustré par les listes ordonnées représentées infra aux figures 1 à 3 ;

- niveau suivant le niveau L : niveau dont les identifiants sont attribués après ceux du niveau L , selon la règle d'attribution des identifiants dans le réseau ; lorsque les niveaux sont, conformément à la règle d'attribution, attribués par ordre décroissant, le niveau suivant un niveau d'ordre i est le niveau d'ordre i-1 ;

- niveau précédent le niveau L : niveau dont les identifiants sont attribués avant ceux du niveau L, selon la règle d'attribution des identifiants dans le réseau ; lorsque les niveaux sont, conformément à la règle d'attribution, attribués par ordre décroissant, le niveau précédent un niveau d'ordre i est le niveau d'ordre i+1 ;

- pair présent : un pair ayant une adresse dans le réseau ;

- destinataire théorique d'un bloc de données : pair susceptible de recevoir ce bloc de données, ce destinataire théorique étant déterminé conformément à ladite règle générale, à partir du numéro du bloc de données et de l'identifiant du pair lui transmettant ce bloc. On notera qu'un pair destinataire théorique ainsi déterminé peut être présent ou absent dans le réseau ;

- récepteur théorique : il s'agit d'un destinataire théorique d'un destinataire théorique, autrement dit d'un pair auquel un destinataire théorique serait susceptible de transmettre un bloc de données, un récepteur théorique étant déterminé à partir du numéro du bloc et de l'identifiant du destinataire théorique, selon ladite règle générale.

- pair à identifier : pair devant recevoir un nouvel identifiant suite à la détection d'un événement dans le réseau ; - pair à notifier : pair conservant son identifiant mais devant être informé suite à la détection d'un événement dans le réseau ;

- voisins d'un pair : destinataires théoriques, déterminés selon la règle générale, présents dans le réseau, auxquels ce pair est susceptible d'envoyer un bloc de données.

- séquence de fin : séquence faisant partie d'un identifiant de pair, située dans les positions binaires les moins significatives de l'identifiant et composée d'un nombre de bits à « 0 » (ce nombre pouvant être nul) suivi d'un bit à « 1 » à gauche.

Dans la suite du document on utilise la notation suivante :

C(n,k) = C _n ^k = n ! / k ! (n-k) !.

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 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 œuvre 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 ».

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 :

- des moyens de 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 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 :

- 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 L auquel 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.

Corrélativement, l'invention concerne un procédé de contrôle d'un réseau pair à pair, ce procédé étant mis en œuvre par une unité de gestion, comportant :

- une étape de sélection d'une dimension n du réseau ;

- une étape de détermination des pairs présents dans le réseau ; - une étape d'attribution à chacun desdits 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 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

- d'informations permettant à ce système d'aiguillage de déterminer le caractère complet, vide ou incomplet du niveau de référence L auquel 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.

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 présents, 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.

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 pair à pair, ce procédé étant mis en œuvre par une unité de gestion, comportant :

- une étape de sélection d'une dimension n du réseau ;

- 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 identifiants comprenant un nombre j d'un élément binaire prédéterminé ; et

- une étape d'envoi, à 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 L auquel 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 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 2 ⁿ -l pairs, pour l'appliquer à un réseau pair à pair comportant un nombre quelconque de pairs. 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 principal 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 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.

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.

Par ailleurs, 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 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 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 ;

- détermination des pairs auxquels un nouvel identifiant doit être attribué en raison de l'occurrence de cet événement, appelés « pairs à identifier » ;

- attribution, à au moins un pair à identifier, d'un identifiant appartenant au niveau d'attribution Lk ;

- détermination des pairs conservant leurs identifiants mais impactés par l'événement, dits « pairs à notifier »;

- fourniture, à au moins un système d'aiguillage en charge d'au moins un pair à identifier, du nouvel identifiant de ce pair ;

- fourniture, à 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 :

- si le niveau de référence L, auquel appartient l'identifiant de ce pair à identifier ou à notifier est complet ; - si le niveau L-l, 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 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 à l'initialisation du réseau pour qu'ils puissent modifier leurs comportements pour réagir à cet événement.

II 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.

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.

Par consé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 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 niveaux, si le dernier niveau Lderatt est complet ;

- le seul pair à identifier est le nouveau pair ; et

- les pairs à notifier sont :

- les voisins du nouveau pair ; et

- les pairs du niveau d'attribution Lk et du niveau Lk+1, précédant le niveau Lk dans l'ordre d'attribution des niveaux, lorsque le niveau d'attribution Lk est devenu complet suite à l'arrivée du nouveau pair.

Dans un mode particulier de réalisation, les pairs à notifier comprennent en outre les pairs du niveau Lk+2, si l'identifiant du nouveau pair est le premier identifiant attribué dans son niveau.

Dans un mode particulier de réalisation, lorsque l'événement précité correspond au départ d'un pair sortant parmi les pairs présents :

- lorsque l'identifiant du pair sortant appartient au dernier niveau Lderatt dans lequel les identifiants ont été attribués, aucun pair n'est à identifier, l'identifiant du pair sortant devenant disponible et les pairs à notifier comprennent les voisins du pair sortant ; et lorsque ce n'est pas le cas :

-le seul pair à identifier est un pair quelconque dont l'identifiant appartient au dernier niveau Lderatt, dit « pair remplaçant », ce pair remplaçant étant identifié par l'identifiant du pair sortant, l'identifiant du pair remplaçant devenant disponible ; et

-lesdits pairs à notifier 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 dudit pair sortant, les pairs des niveaux Lderatt et Lderatt+1.

Dans un mode particulier de réalisation de l'invention, les pairs à notifier comprennent en outre les pairs du niveau Lderatt+2 si l'identifiant du pair sortant ou du pair remplaçant était le seul de son niveau.

Dans un mode particulier de réalisation de l'invention, le procédé de contrôle comporte:

- une étape 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 d'obtention et d'envoi de cette adresse à ce système d'aiguillage.

Cette caractéristique permet avantageusement à un système d'aiguillage d'obtenir l'adresse d'un pair destinataire même si celui-ci qui ne fait pas partie de ses voisins au sens de la règle générale des réseaux hypercubes complets.

Dans un mode particulier de réalisation de l'invention, le procédé selon l'invention permet de construire le réseau contrôlé par l'unité de gestion selon l'invention par fusion de deux sous-réseaux. Cette fusion constitue un événement au sens de l'invention.

Plus précisément, dans un mode particulier de réalisation, le réseau est obtenu par fusion d'un premier sous-réseau, et d'un deuxième sous-réseau, tous les deux de dimension n- 1, le premier sous-réseau ayant un niveau complet de plus que ledit deuxième sous-réseau et le niveau d'ordre n-1 du réseau est constitué par :

- les identifiants appartenant au niveau n-2 du premier sous-réseau, complétés, dans une position dite d'insertion, par l'élément binaire prédéterminé ; et

- par un identifiant dit identifiant pivot, constitué par n-1 éléments binaires prédéterminés, complétés, dans la position d'insertion, par l'élément binaire complémentaire, cet identifiant pivot étant attribué à un pair dit pair pivot choisi dans un niveau incomplet si le dernier niveau des identifiants attribués dans le premier sous-réseau ou le dernier niveau des identifiants attribués dans le deuxième sous-réseau est incomplet, et sinon dans un quelconque de ces deux niveaux si les deux sont complets ;

- chacun des autres niveaux d'ordre W du réseau étant constitué par :

- les identifiants du niveau d'ordre W-l, suivant l'ordre W du premier sous- réseau, ces identifiants étant complétés, dans la position d'insertion, par l'élément binaire prédéterminé ; et par - les identifiants du niveau d'ordre W du deuxième sous-réseau, ces identifiants étant complétés, dans leur position d'insertion, par l'élément binaire complémentaire. Dans un mode particulier de réalisation, la dimension n du réseau est choisie en fonction du nombre N de pairs présents dans le réseau de telle sorte que le nombre de niveaux attribués est égal à n/2 .

Cette caractéristique permet avantageusement d'obtenir des délais de diffusion courts.

Selon un deuxième aspect, l'invention vise aussi un système d'aiguillage apte à être utilisé dans un réseau pair à pair, ce système comportant :

- des moyens de détermination conformément à une règle de diffusion des données dans le réseau, d'un ensemble d'au plus n pairs destinataires auxquels un pair doit transmettre un bloc de données numéroté reçu par ce pair, en fonction d'un identifiant comprenant des éléments binaires et destiné à identifier ledit pair, et de la dimension n dudit réseau,

- ladite règle étant sélectionnée à partir d'informations permettant de déterminer le caractère complet, vide ou incomplet d'un niveau dit de référence L auquel appartient ledit identifiant, et d'au moins un niveau suivant ledit niveau de référence dans un ordre prédéfini d'attribution des niveaux, un niveau étant constitué par l'ensemble des identifiants de pairs comprenant un nombre j d'un élément binaire prédéterminé;

- ladite règle étant:

- la règle des hypercubes complets de dimension n, dite « règle générale » si une condition sur ces informations est satisfaite ;

- une autre règle déterminée en tenant compte de ces informations dans tous les autres cas.

Corrélativement, l'invention vise un procédé de communication de données mis en œuvre par un système d'aiguillage dans un réseau pair à pair, ce procédé comportant :

- une étape de détermination conformément à une règle de diffusion des données dans le réseau, d'un ensemble d'au plus n pairs destinataires auxquels un pair doit transmettre un bloc de données numéroté reçu par ce pair, en fonction d'un identifiant comprenant des éléments binaires et destiné à identifier ce pair, et de la dimension n dudit réseau,

- la règle étant sélectionnée à partir d'informations permettant de déterminer le caractère complet, vide ou incomplet d'un niveau dit de référence L auquel appartient cet identifiant, et d'au moins un niveau suivant ce niveau de référence dans un ordre prédéfini d'attribution des niveaux , un niveau étant constitué par l'ensemble des identifiants de pair comprenant un nombre j d'un élément binaire prédéterminé ;

- la règle étant:

- la règle des hypercubes complets de dimension n, dite « règle générale » si une condition sur lesdites informations est satisfaite ; - une autre règle déterminée en tenant compte desdites informations dans tous les autres cas.

Dans un mode particulier de réalisation, le procédé de communication de données selon l'invention comporte une étape de sélection de règle comprenant:

- une étape d'obtention des informations précitées ; et

- une étape de sélection de la règle à partir de ces informations.

Cette étape de sélection et l'étape de détermination de l'ensemble des pairs destinataires peuvent être mises en œuvre par le pair.

Dans une première variante :

- l'étape de détermination de l'ensemble des pairs destinataires est mise en œuvre par le pair ; et

l'étape de sélection est mise en œuvre par une unité de gestion apte à attribuer les identifiants de pair selon l'ordre prédéfini d'attribution.

Dans une deuxième variante, l'étape de sélection et l'étape de détermination de l'ensemble des pairs destinataires sont mises en œuvre par une unité de gestion apte à attribuer les identifiants de pair selon l'ordre prédéfini d'attribution.

Ainsi, conformément à l'invention, pour chaque pair, un système d'aiguillage déduit le fonctionnement de ce pair à partir des informations qu'il reçoit de l'unité de gestion.

Il est important de noter qu'un système d'aiguillage peut être en charge :

- de la totalité des pairs, le système d'aiguillage pouvant être intégré dans l'unité de gestion ;

d'une partie seulement des pairs du réseau ;

d'un seul pair, le système d'aiguillage pouvant être intégré à ce pair.

Dans ce dernier cas, l'invention vise par conséquent un procédé de communication de données mis en œuvre par un pair dans un réseau pair à pair, ce procédé comportant :

- une étape d'obtention d'un identifiant comprenant des éléments binaires et destiné à identifier ce pair ;

- une étape d'obtention d'une dimension n du réseau,

- une étape de détermination d'un niveau de référence L auquel appartient cet identifiant, un niveau étant constitué par l'ensemble des identifiants de pair comprenant un nombre j d'un élément binaire prédéterminé ;

- une étape d'obtention d'informations permettant au pair mettant en œuvre l'invention de déterminer le caractère complet, vide ou incomplet du niveau de référence et d'au moins un niveau suivant ce niveau de référence dans un ordre prédéfini d'attribution des niveaux ;

- une étape de sélection à partir de ces informations d'une règle de diffusion des données dans le réseau à appliquer par le pair mettant en œuvre l'invention, cette règle étant : - la règle des hypercubes complets de dimension n, dite « règle générale » si une condition sur ces informations est satisfaite ;

- une autre règle déterminée en tenant compte de ces informations dans tous les autres cas.

Ainsi, dans ce mode de réalisation, chaque pair déduit sa propre règle de fonctionnement des informations qu'il reçoit de l'unité de gestion.

Il est remarquable de constater qu'un pair se comporte exactement comme dans un réseau hypercube complet de dimension n de l'art antérieur, lorsque la condition est satisfaite et selon une autre règle dans les autres cas.

Grâce à cette caractéristique, le comportement d'un pair diffère de celui des réseaux hypercubes complets uniquement pour les derniers niveaux attribués.

Comme cela sera expliqué plus en détail plus loin, une autre règle, différente de la règle des hypercubes complets, sert à déterminer pour au moins un pair présent considéré, une liste d'au plus n pairs destinataires, qui tienne compte des pairs destinataires théoriques de ce pair qui sont absents du réseau.

Grâce à cette autre règle, les pairs destinataires théoriques qui sont absents du réseau seront remplacés par au plus un autre pair. D'autres réajustements peuvent en outre être effectués lors de la définition de la liste d'au plus n pairs destinataires qui définit le comportement du pair considéré.

Cette autre règle est appliquée conditionnellement à la situation dans laquelle se trouve le pair dont la liste est à définir. Pour déterminer si cette autre règle s'applique, on détermine notamment si le niveau auquel appartient ce pair est complet, vide ou incomplet. Le niveau suivant dans l'ordre d'attribution des niveaux est également examiné.

On résout ainsi le problème général de la recherche de nouvelles routes de transmission des bloc de données, tout en évitant à chaque pair d'avoir besoin d'émettre à un débit supérieur à un débit d'origine, correspond au débit de ce pair dans l'hypercube complet.

Dans un mode de réalisation de l'invention, les informations précitées permettent au système d'aiguillage de déterminer si le niveau de référence L est complet et si le niveau L-1 est complet ou vide ; la condition est satisfaite si le niveau L-1 est complet.

Dans un autre mode de réalisation de l'invention, les informations précitées permettent au système d'aiguillage de déterminer si le niveau de référence L est complet, si le niveau L-1 est complet ou vide, et si le niveau L-2 est vide ; la condition est satisfaite si le niveau L-2 n'est pas vide.

Dans un mode préféré de réalisation ledit procédé comprend en outre une étape de création d'une liste ordonnée apte à contenir au moins un pair destinataire auquel ledit pair doit transmettre un bloc de données reçu par ledit pair. Cette liste ordonnée de pairs destinataires peut contenir, pour un numéro de bloc de données, zéro, un, ou plusieurs pairs destinataires.

Dans un mode particulier de réalisation, lorsque la condition n'est pas satisfaite, l'autre règle utilise une liste ordonnée étendue obtenue à partir d'un identifiant générateur et d'un bloc de données numéroté par :

- une étape de détermination d'un niveau d'ordre G, dit niveau générateur, auquel appartient l'identifiant générateur ;

- une étape de détermination d'une première liste ordonnée comportant une partie seulement des identifiants appartenant au niveau générateur à partir de l'identifiant générateur et du numéro du bloc numéroté ;

- une étape de détermination d'une liste des destinataires théoriques dudit bloc auxquels le pair identifié par ledit identifiant générateur serait susceptible de transmettre ledit bloc numéroté selon ladite règle générale ;

- une étape d'obtention, dans ladite liste des destinataires théoriques, du pair dont l'identifiant appartient au niveau G+l, précédant le niveau générateur G dans l'ordre d'attribution des niveaux, dit identifiant d'extension ;

- la liste ordonnée étendue étant obtenue en ajoutant l'identifiant d'extension en dernière position dans la première liste ordonnée.

Dans un mode particulier de réalisation, l'autre règle utilise un procédé d'association qui, à un identifiant de pair et à un numéro d'un bloc de données numéroté, associe un identifiant de base.

Dans un mode de réalisation, le procédé d'association comprend :

- une étape de détermination d'une séquence de fin de l'identifiant de pair ;

- une étape d'obtention de l'identifiant de base à partir de l'identifiant de pair par déplacement de la séquence de fin dans l'identifiant de pair à une position correspondant au numéro de bloc, les autres éléments binaires dudit identifiant de pair étant décalés.

Dans un mode de réalisation, le procédé d'association comprend :

- une étape de détermination de la séquence de fin de l'identifiant de pair ;

- une étape d'obtention dudit identifiant de base à partir dudit identifiant de pair par permutation circulaire des éléments binaires de l'identifiant de pair de manière à placer la séquence de fin à une position correspondant au numéro de bloc.

Dans un mode de réalisation, l'étape de détermination d'une première liste ordonnée comprend

- une sous-étape de détermination, pour au moins un identifiant du niveau générateur, d'un identifiant de base associé selon le procédé d'association à cet identifiant du niveau générateur et au numéro du bloc numéroté ; - la première liste ordonnée étant constituée par les identifiants appartenant au niveau générateur, dont les identifiants de base associés sont égaux à cet identifiant générateur.

Dans un mode préféré de réalisation, l'autre règle de diffusion d'un bloc de données numéroté, comprend, lorsqu'une lorsque le niveau L-l n'est pas vide :

- une étape de détermination, conformément à ladite règle générale, à partir du numéro K du bloc de données numéroté et de l'identifiant du pair, d'une deuxième liste ordonnée comportant les identifiants des pairs destinataires théoriques du bloc de données numéroté ;

- et pour chacun des identifiants des destinataires théoriques pris dans l'ordre de ladite deuxième liste ordonnée, si l'identifiant de destinataire théorique appartient au niveau L-l :

- une étape de détermination d'une liste ordonnée étendue à partir de l'identifiant de destinataire théorique et du numéro du bloc de données numéroté ;

- une étape d'obtention du pair destinataire identifié par le premier identifiant attribué dans la liste ordonnée étendue ; et

- une étape d'ajout dudit pair destinataire à la liste de pairs destinataires;

- et, lorsque l'identifiant de destinataire théorique appartient au niveau L+l, précédant le niveau de référence L dans l'ordre d'attribution des niveaux, une étape d'ajout du pair identifié par cet identifiant à la liste de pairs destinataires.

Dans un mode particulier de réalisation, cette caractéristique particulière permet de gérer le comportement d'un pair dont l'identifiant appartient à un niveau L complet, le niveau L- 1 étant incomplet.

Dans un autre mode particulier de réalisation, cette caractéristique particulière permet de gérer le comportement d'un pair dont l'identifiant appartient à un niveau L complet, le niveau L-l étant complet ou incomplet, et le niveau L-2 étant vide.

Dans un autre mode de réalisation, la détermination de l'autre règle de diffusion d'un bloc de données numéroté, comprend, lorsqu'une deuxième condition est satisfaite :

- une étape de détermination d'un identifiant dit « identifiant de base », à partir de l'identifiant de pair et du numéro du bloc ;

- une étape de détermination de ladite liste ordonnée étendue à partir de cet identifiant de base et du numéro du bloc numéroté ;

- une étape de recherche de l'identifiant de pair dans la liste ordonnée étendue ;

- une étape de détermination d'un pair destinataire identifié par le premier identifiant attribué suivant l'identifiant de pair dans ladite liste ordonnée étendue ; et

- une étape d'ajout de ce pair destinataire à ladite liste de pairs destinataires.

Cette caractéristique particulière permet de gérer le comportement d'un pair dont l'identifiant appartient au dernier niveau. Dans un mode particulier de réalisation, la deuxième condition est satisfaite lorsque le niveau L-1 est vide, le niveau L étant incomplet.

Dans un autre mode particulier de réalisation, la deuxième condition est satisfaite lorsque le niveau L-1 est vide.

Dans un mode particulier de réalisation, la détermination de l'autre règle de diffusion d'un bloc de données numéroté, comprend, lorsque le niveau L-1 est vide, et lorsque le niveau de référence L est complet, les étapes suivantes :

- une étape de détermination conformément à ladite règle générale, à partir du numéro dudit bloc numéroté et dudit identifiant, d'une quatrième liste ordonnée comportant les identifiants des pairs destinataires théoriques dudit bloc ;

- et pour chacun desdits identifiants des destinataires théoriques pris dans l'ordre de ladite quatrième liste ordonnée, si ledit identifiant de destinataire théorique appartient audit niveau L-1,

- une étape de détermination des récepteurs théoriques auxquels ledit destinataire théorique serait susceptible de transmettre ledit bloc numéroté ;

- une étape d'obtention, parmi lesdits récepteurs théoriques, du pair destinataire dont l'identifiant appartient au niveau de référence L ; et

- une étape d'ajout dudit pair destinataire à ladite liste de pairs destinataires;

- et, lorsque ledit identifiant de destinataire théorique appartient au niveau L+l, une étape d'ajout du pair identifié par cet identifiant à ladite liste de pairs destinataires.

Dans ce mode de réalisation, un pair du niveau L se substitue à ses destinataires théoriques de niveau L-1 absents pour émettre les blocs de données vers les pairs destinataires de son propre niveau L. Selon un troisième aspect, l'invention vise aussi un pair apte à être utilisé dans un réseau pair à pair, ce comportant :

- des moyens de réception d'un bloc de données numéroté ;

- des moyens d'obtention des adresses de l'ensemble des pairs destinataires du bloc de données numéroté, ces pairs destinataires étant déterminés par un système d'aiguillage mettant en œuvre un procédé de communication de données tel que mentionné ci-dessus ; et

- des moyens de transmission du bloc de données numéroté à au moins un pair destinataire de cet ensemble.

Dans un mode particulier de réalisation, le pair selon l'invention comporte en outre 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 mentionné ci- dessus. 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 œuvre 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 œuvre 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 l'invention comporte en outre un sous-système pour sélectionner une règle utilisée pour déterminer l'ensemble des pairs destinataires d'un bloc de données numéroté reçu par un 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 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 œuvre par un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre d'au moins une partie des étapes d'un procédé de communication de données tel que mentionné ci-dessus. Dans un mode particulier de réalisation, ce programme comporte des instructions pour ne mettre en œuvre 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 œuvre ces deux étapes.

De même, l'invention vise également un programme d'ordinateur sur un support d'informations, ce programme étant susceptible d'être mis en œuvre par un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre 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 œuvre par un ordinateur, ce programme comportant des instructions adaptées à la mise en œuvre 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, tel que dans une forme partiellement compilée, ou dans n'importe 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 le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy dise) ou un disque dur.

D'autre part, le support d'informations peut être un support transmissible tel qu'un signal é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 particulier télé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 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 ;

- la 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 ; - 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 étapes d'un procédé de contrôle, mis en œuvre 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 ;

- les figures 7 et 8 représentent, sous forme d'organigramme, les principales étapes d'un procédé de communication de données, mis en œuvre par un dispositif de communication de données selon un premier mode particulier de réalisation de l'invention ;

- les figures 9 et 10 représentent, sous forme d'organigramme, les principales étapes d'un procédé de communication de données, mis en œuvre par un dispositif de communication de données selon un deuxième mode particulier de réalisation de l'invention ;

- les figures 11 et lia 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 conformément à 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 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 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, Ll, L0 étant ordonnés dans l'ordre décroissant du nombre de « 0 » 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.

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 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.

La mémoire morte 12 constitue un support conforme à l'invention, lisible par le processeur 11 et sur lequel est enregistré un programme d'ordinateur PGM2 comprenant des instructions pour l'exécution des étapes d'un procédé de contrôle selon l'invention dont les principales étapes seront décrites en référence aux figures 4 à 6.

La mémoire morte 12 mémorise aussi un élément binaire bO, en l'espèce le bit « 0 », 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 < 2 ⁿ où N est le nombre de pairs dans le réseau.

Dans l'exemple de réalisation décrit ici, l'unité de gestion 10 mémorise les adresses ADij des pairs présents du réseau dans une base de données 17.

La figure 12 représente un système d'aiguillage DA conforme à un premier mode particulier de réalisation de l'invention.

Dans le mode de réalisation décrit ici, ce système d'aiguillage DA est un dispositif ayant l'architecture matérielle d'un ordinateur. Il comporte un processeur 111, une mémoire morte 112, une mémoire vive 113, une mémoire non volatile réinscriptible 114 et des moyens de communication 115 avec l'unité de gestion 10 et avec les pairs du réseau. On notera que ces moyens de communication 115 peuvent être de moyens de communication interne, via un bus de de données, et/ou externe via le réseau selon que le système d'aiguillage est incorporé ou non dans l'unité de gestion.

La mémoire morte 112 constitue un support conforme à l'invention, lisible par le processeur 111 et sur lequel est enregistré un programme d'ordinateur PGM1 comprenant des instructions pour l'exécution des étapes d'un procédé de communication de données selon l'invention dont les principales étapes seront décrites en référence aux figures 7 , 8, 11 et l ia. La mémoire non volatile réinscriptible 114 du système d'aiguillage DA comporte en particulier des registres pour mémoriser pour chaque pair dont il a la charge, un identifiant unique IDi reçu de l'unité de gestion 10.

Le processeur 11, la mémoire vive 12 et la mémoire morte 13 de l'unité de gestion 10 sont aptes à déterminer les identifiants de chacun des niveaux du réseau.

Dans le mode de réalisation décrit ici, l'unité de gestion 10 comporte, dans sa mémoire non volatile réinscriptible 14, les identifiants des pairs PPim présents dans le réseau.

En référence à la figure 4, l'unité de gestion 10 est apte à déterminer, au cours d'une étape G10, la dimension n du réseau, et à la mémoriser dans la mémoire non volatile réinscriptible 14.

Le programme PGM2 comporte des instructions pour permettre à l'unité de gestion 10, lorsqu'elles sont exécutées par le processeur 11, de déterminer, au cours d'une étape G25, les pairs PPim présents dans le réseau.

L'unité de gestion 10 est apte à attribuer, au cours d'une étape G30, un identifiant unique à chacun des pairs présents. Dans le mode de réalisation décrit ici, les identifiants sont attribués aux pairs dans l'ordre décroissant des niveaux, les identifiants étant pris dans un ordre quelconque au sein d'un même niveau. Elle utilise pour cela, l'élément binaire bO, en l'espèce « 0 », cet élément étant lu dans la mémoire morte 12 au cours de la même étape G10.

Dans cet exemple, les pairs sont ordonnés selon le nombre de « 0 » dans leurs identifiants, comme cela est représenté à la figure 1. Pour un entier n et une population N < 2 ⁿ , l'unité de gestion 10 attribue aux pairs un identifiant, les identifiants ayant le plus de « 0 » possibles étant attribués en premier. L'identifiant particulier ayant tous les bits à 0 est, dans les exemples décrits, réservé pour la source du flux de données. L'ordre d'attribution parmi les identifiants ayant le même nombre de bits à « 0 » est indifférent. L'ordre d'attribution peut être illustré par les listes ordonnées de la figure 2.

Dans un mode de réalisation, l'unité de gestion détermine, lors d'une étape G26, pour chacun desdits pairs présents PPim, un système d'aiguillage DAi en charge de ce pair.

Le programme PGM2 comporte des instructions pour permettre à l'unité de gestion 10, lorsqu'elles sont exécutées par le processeur 11, de déterminer, au cours d'une étape G40, les voisins VPij de chacun des pairs présents PPim, en appliquant la règle générale R déjà décrite des réseaux hypercubes complets de dimension n.

On rappelle que les voisins d'un pair sont les destinataires théoriques présents auquel ce pair est susceptible d'envoyer un bloc de données.

Dans ce premier mode de réalisation, l'unité de gestion 10 est apte à fournir, au cours d'une étape G50, à chaque système d'aiguillage DAi en charge d'au moins un pair présent PPim l'identifiant IDim de ce pair PPim et des informations permettant de déterminer si le niveau de référence L auquel appartient l'identifiant IDim est complet, et si le niveau L-l suivant ce niveau de référence dans l'ordre des niveaux est vide ou complet. Ces informations peuvent par exemple être constituées par le nombre total de niveaux dans lesquels des identifiants ont été attribués ainsi que le dernier niveau complet.

L'unité de gestion 10 est en outre apte à fournir, au cours d'une étape G60, à chacun des pairs présents PPim, l'identifiant et l'adresse de chacun de ses voisins.

3.1 Fonctionnement général de l'unité de gestion

Dans le premier mode de réalisation décrit ici, l'unité de gestion 10 selon l'invention est apte à détecter un certain nombre d'événements impactant le réseau aux étapes G70 ou G110 qui seront décrites ci-dessous.

Lorsqu'un événement est détecté, l'unité de gestion détermine, au cours d'une étape G90 ou G130, d'éventuels pairs Pjm à identifier et le cas échéant, l'identifiant de ces pairs, ces identifiants étant choisis (étape G200) dans un niveau dit d'attribution Lk déterminé à l'étape G80 ou G120.

En référence à la figure 5, au cours d'une étape G210, l'unité de gestion détermine ensuite quels sont les pairs Pqr à notifier suite à l'événement détecté.

L'unité de gestion 10 envoie ensuite (étape G220) à chacun des systèmes d'aiguillage DAj en charge d'au moins un pair à identifier, le nouvel identifiant IDjm de ce pair, l'identifiant et l'adresse de chacun de ses voisins, et des informations lui permettant de déterminer si le niveau de référence L auquel appartient son identifiant est complet, et si le niveau L-l suivant ce niveau de référence dans l'ordre des niveaux est vide ou complet.

Puis l'unité de gestion envoie (étape G230) à chacun des systèmes d'aiguillage DAq en charge d'au moins un pair Pqr à notifier, des informations lui permettant de déterminer, si le niveau de référence L auquel appartient son identifiant est complet, et si le niveau L-l suivant ce niveau de référence dans l'ordre des niveaux est vide ou complet. L'identifiant des pairs à notifier n'est pas modifié.

Dans ce premier mode de réalisation, il n'est pas nécessaire que l'unité de gestion 10 envoie des informations aux systèmes d'aiguillage leur permettant de déterminer si le niveau L- 2 est vide, ce qui explique pourquoi cette référence est placée entre parenthèses aux étapes G220, G230.

Conformément à l'invention, la détermination du niveau Lk d'attribution dans lequel les nouveaux identifiants sont choisis, les pairs à identifier et les pairs à notifier sont choisis en fonction de l'événement. 3.1.1 Gestion de l'arrivée d'un nouveau pair dans le réseau

Dans le mode de réalisation 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 : - le niveau d'attribution Lk (étape G80) 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 ce dernier niveau si ce dernier niveau est complet ;

- 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 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 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 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 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.

3.1.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 < 2 ⁿ , n entier quelconque, où les délais croissent comme n.

Lorsque le nombre N varie, il peut être nécessaire d'augmenter la dimension n si N augmente, ou il peut être souhaitable, pour des questions de délais, de diminuer la dimension n si N diminue. Là encore, conformément à l'invention, chaque pair sait déterminer comment se comporter pendant la transition.

Le changement de dimension peut consister en une augmentation de dimension, celle-ci s'appliquant à deux réseaux hypercubes partiels avec une différence de profondeur de un niveau.

Le changement de dimension peut aussi consister en une diminution de la dimension dans le cas d'un seul hypercube partiel.

On rappelle qu'une même source peut diffuser des blocs de données dans deux réseaux hypercubes. Selon la Règle 3, les n pairs du premier niveau n-1 doivent théoriquement envoyer un bloc au niveau supérieur, c'est à dire à la source.

Puisque c'est superflu, chacun de ces pairs peut envoyer un bloc de données à son pair homologue au sommet d'un second hypercube et initier une autre propagation.

Si de plus, ces pairs envoient ce bloc pendant le premier intervalle de temps après la réception du bloc émis par la source, les deux structures disséminent les blocs de données avec un intervalle de temps de décalage par rapport au cas de la structure unique.

On se place maintenant dans ce contexte.

Dans un mode de réalisation de l'invention illustré à la figure 6, le procédé de contrôle selon l'invention permet de construire le réseau de pair HO de dimension n par fusion d'un premier sous-réseau Hl, et d'un deuxième sous-réseau H2, tous les deux de dimension n-1, le premier sous-réseau Hl ayant un niveau complet de plus que le deuxième sous-réseau H2.

Dans ce mode de réalisation, le niveau n-1 du réseau HO est constitué par :

- les identifiants appartenant au niveau n-2 du premier sous-réseau Hl, ces identifiants étant complétés, dans une position dite d'insertion, par un bit « 0 » ; et par

- un identifiant pivot dont l'identifiant est constitué par n-1 bits « 0 » complétés, dans la position d'insertion par l'élément binaire « 1 ».

Dans ce mode de réalisation, l'identifiant pivot est attribué à un pair dit « pair pivot » choisi prioritairement dans un niveau incomplet si le dernier niveau des identifiants attribués d'au moins un des deux sous-réseaux Hl, H2 est incomplet, et sinon, dans de ces deux derniers niveaux.

Dans le mode de réalisation décrit ici, chacun des autres niveaux Lw d'ordre W dudit réseau H0 est constitué par :

- les identifiants du niveau d'ordre W-l du premier sous-réseau Hl, ces identifiants étant complétés, dans la position d'insertion, par le bit « 0 » ; et par

- les identifiants du même niveau d'ordre W du deuxième sous-réseau H2, ces identifiants étant complétés, dans la position d'insertion, par le bit « 1 ».

Inversement, dans un mode particulier de réalisation, l'unité de gestion 10 selon l'invention est apte à appliquer le mécanisme inverse pour séparer le réseau H0 en deux sous- réseaux Hl, H2 de dimension n-1, le premier sous réseau ayant un niveau incomplet de plus que le deuxième sous réseau.

Plus précisément, pour tout niveau I tel que l ₀ +l <= I < n, on compose un niveau I de HO en joignant le niveau 1-1 de Hl et le niveau I de H2. On obtient ainsi le nombre désiré de pairs dans le niveau I :

C(n, 1-1) + C(n, I) = C(n+1, I)

Le cas particulier du niveau l=n est obtenu avec le niveau n-1 de Hl et un pair additionnel du niveau incomplet de H 1 ou H2.

La transition d'une diffusion des blocs de données via les sous-réseaux Hl et H2 vers une diffusion via le réseau HO peut s'effectuer progressivement et de façon asynchrone. En particulier des transmissions peuvent s'effectuer en parallèle en dimension n et n-1. Pour cela la source peut diffuser des blocs en leur adjoignant une information indiquant que la dimension du réseau va changer. Les pairs recevant cette information calculent leur nouvel identifiant suivant leur appartenance à Hl ou H2 comme décrit précédemment. Ils déterminent les identifiants des pairs avec lesquels ils sont susceptibles d'échanger des blocs dans la nouvelle dimension. Si ces identifiants correspondent à des pairs dont ils ne possèdent pas l'adresse, ils envoient une requête au gestionnaire (étape G63) afin d'obtenir (étape G65) les adresses des pairs correspondants à ces nouveaux identifiants. La source émettra les blocs en leur adjoignant la nouvelle dimension. Un pair recevant un bloc avec l'ancienne dimension rediffusera ce bloc suivant les règles de diffusion dans l'ancienne structure. Un même pair recevant un bloc avec la nouvelle dimension rediffusera ce bloc suivant les règles de diffusion dans la nouvelle structure. Cette implémentation assure que tous les pairs reçoivent tous les blocs y compris pendant la phase de transition d'une dimension à une autre.

Cette même implémentation peut être utilisée pour réduire la dimension d'un réseau HO de dimension n en deux sous-réseaux de dimensions n-1.

Dans un mode particulier de réalisation, la dimension n du réseau est choisie par l'unité de gestion en fonction du nombre N de pairs présents dans le réseau de telle sorte que le nombre de niveaux attribués est égal à n/2.

En gardant une taille limitée pour la profondeur k des réseaux linéaires, et des demi- hypercubes, 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 I incomplet avec I = (n/2) - 1

Cette valeur maximise C(n-1, l)n à savoir la taille du premier sous-niveau, égale dans ce cas à C(n-1, n/2 - 1). Elle permet de stocker le nombre maximum de pairs pour un nombre k donné de sous-niveaux, en gardant des délais faibles.

Comme I <= n/2, n/(n-l) <=2 et deux sous-niveaux suffisent pour composer le niveau I complet suivant avec I = (n/2) - 1.

On suppose qu'il existe k de ces sous-niveaux et on obtient que pour un hypercube incomplet de profondeur I = (n/2) -1, le délai maximum en terme de temps de transmission est n + k - 1 (5)

et en terme de délai total de propagation

((n/2) + k + 2) (6)

En gardant une taille limitée pour la profondeur k des réseaux linéaires, et des demi- hypercubes, on obtient à la fois des délais de propagation et des délais de transmission courts.

3.2 Fonctionnement général d'un système d'aiguillage du réseau

On décrit maintenant le comportement d'un système d'aiguillage DA dans un premier mode de réalisation.

Il met en œuvre 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 un pair.

Le processeur 111 est apte à obtenir l'élément binaire bO au cours d'une étape P10 et à déterminer, au cours d'une étape P20 le niveau L de référence auquel appartient son identifiant IDi.

Ses moyens 115 de communication lui permettent d'obtenir ou de recevoir, au cours d'une étape P30 des informations lui permettant de déterminer si ce niveau de référence L est complet et si le niveau L-1 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 R des hypercubes complets de niveau n si le niveau L-1 est complet, dans tous les autres cas, une autre règle RI, 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 RI est choisie si l'identifiant du pair considéré appartient à un niveau L complet, le niveau L-1 étant vide. Cette règle est détaillée ci-dessous.

3.2.1 Règle RI

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 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 I 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 I auquel le pair 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 I 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 temps.

En effet, les blocs de données sont propagés correctement et dans les temps. Soit b un pair de niveau I 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 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 destination de transmission pour le pair b" dans l'intervalle de temps.

Dans cette démonstration :

b est un récepteur théorique au sens de l'invention ;

- b' est le destinataire théorique absent au sens de l'invention ; et

b" est le pair qui met en œuvre l'invention.

Une implémentation possible de la règle RI correspond aux étapes P500 à 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 conformément à la règle R générale, à partir du numéro K d'un bloc numéroté BK et de l'identifiant IDi du pair mettant en œuvre l'invention, d'une liste ordonnée L04 comportant les identifiants IDTij des pairs destinataires théoriques de ce bloc BK. ;

Puis, pour chacun des identifiants IDTij des destinataires théoriques pris dans l'ordre de la liste ordonnée L04, on teste au cours d'une étape P550 si cet identifiant IDTij appartient au niveau L-l.

Si c'est le cas, la règle RI comporte une étape P510 de détermination des 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 œuvre l'invention obtient, parmi les récepteurs théoriques RTKi, le pair destinataire PD dont l'identifiant appartient au niveau L. 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 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 œuvre 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 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 l'identifiant et de l'adresse de chacun des voisins de ces pairs Pjm à identifier.

Cette adresse est reçue par le dispositif système mettant en œuvre l'invention lors d'une étape P25 et peut être mémorisée ensuite dans la mémoire non-volatile réinscriptible 114. L'adresse du pair destinataire peut être obtenue par lecture dans cette mémoire non- volatile réinscriptible.

Lorsqu'il est déterminé à l'étape P550 que l'identifiant IDTij de destinataire théorique appartient au niveau L+1, le pair identifié par l'identifiant IDTij est ajouté à la liste ordonnée LDk de pairs destinataires.

3.2.2 Dernier niveau incomplet comportant au maximum C(n-1, I) pairs

La proposition 6 ne s'applique pas lorsque le dernier niveau I est incomplet. La Règle 5 permet aux pairs de niveau I de rebondir sur les pairs absents de niveau 1-1 et de transmettre un bloc aux pairs de niveau I.

Mais lorsque le niveau I 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.

Dans le mode de réalisation décrit ici, on utilise une structure de diffusion qui utilise les relations des coefficients binomiaux.

Un niveau I est composé de toutes les combinaisons binaires de longueur n comprenant I « 0 ». Il y en a C(n, I).

Le niveau I doit recevoir n.C(n, I) blocs de données de ses voisins. Selon la proposition 4 :

n.C(n, I) = (l+l).C(n, 1+1) + (n-l+l).C(n, 1-1).

Cette relation permet d'identifier le saut suivant. Proposition 7 : Le nombre maximum de pairs dans un niveau I incomplet qui peuvent recevoir leurs blocs de données uniquement du niveau supérieur est :

x = (l+l).C(n, l+l)/n = C(n-1, I).

On considère C(n-1, I) pairs ou moins dans un niveau I incomplet. Ces pairs sont dits appartenir à un premier sous-niveau.

On peut démontrer comment tous les pairs de ce premier sous-niveau I peuvent recevoir tous les blocs de données du niveau 1+1. Il y a au plus C(n-1, I) pairs dans ce sous- niveau. Ils peuvent être représentés sur n-1 bits d _n -i...di dans lesquels I sont égaux à « 0 ».

Pour trouver, l'émetteur du bloc de données k au pair A identifié d _n -i...di on considère le pair fictif B _k de niveau I, dans un système de niveau I complet avec l'identifiant d _n- i...d _k ld _k -i...di obtenu en insérant un 1 en position k dans l'identifiant de A de longueur n- 1 (voir Table II).

Etant donné que Bk a un 1 en position k, il retransmet le bloc k. Il reçoit donc (lorsqu'il est présent) le bloc k d'un unique pair C _k du niveau supérieur 1+1. Puis C _k 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 k et des « 0 » de la position k-1 à la position i d _n -i...d _k -nld _k -i...di-nOdi_i ...di (avec d,=0 pour j de k-1 à i+1).

Donc à l'instant i, le pair C transmet le bloc k à l'unique pair du sous-niveau I d'identifiant de longueur n-1 d _n ...d _k -nd _k -i...di-nldi_i ...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 au niveau inférieur I.

Pour tout pair dans le premier sous niveau d'un niveau I 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 blocs de données aux pairs qui ne les ont pas reçus. Pour identifier quels blocs de données à retourner à quels pairs, on procède de la façon suivante.

Soit d _n -i...di l'identifiant de longueur n-1 d'un pair A au premier sous-niveau. A ce pair A on peut associer n pairs B _k en insérant un « 1 » entre d _k +i et d _k dans l'identifiant de A pour k allant de 1 à n.

Pour chaque pair B _k , A ou l'un de ses descendants doit transmettre le bloc de données k au pair D _k d'identifiant

D _k est le pair à qui Ck aurait envoyé le bloc k si A n'avait pas été présent. Cela définit une bijection entre les blocs qui n'ont pas été reçus au niveau 1+ 1 (du niveau 1+ 1) à cause de la présence de A au niveau I incomplet et les blocs retransmis par le pair A (ou l'un de ses descendants) au niveau 1+ 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 I 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 I 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.

Le premier sous-niveau peut être interprété comme le maximum de C(n-1, I) 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 I incomplet. Si ces sources génèrent des sous-réseaux linéaires, le délai de ces 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+ 1) blocs depuis ce niveau incomplet.

Une organisation possible d'un niveau incomplet dans un réseau linéaire est 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. Il 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 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. Topoloqie linéaire de niveau I incomplet

On se place dans le cas où les pairs de niveau I restants sont organisés en 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 données 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 sous-niveau.

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+1 auquel le dernier pair du réseau linéaire doit retransmettre le bloc k forment 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 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, I) pairs présents pour former un niveau I 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 I peut être décomposé dans un nombre n/n-l maximum de réseaux, chacun de taille C(n-1, 1), à l'exception du dernier sous-niveau.

En effet, le niveau I étant incomplet, il est composé de moins de C(n, I) pairs. Ceux-ci peuvent être distribués sur C(n-1, I) possibles réseaux linéaires. Chacun a donc une longueur maximum

C(n, l) / C(n-l, I) = n / (n-l)

Ce rapport décroit de n à 1 lorsque I varie de n-l à 0.

Pour I dans [0 ; n-l], ce rapport est inférieur ou égal à 1+1, car : (n/n-l) <= 1+1 < = > l ² - (n-l).l <=0

Une limite plus fine est obtenue si l'hypercube est au moins à moitié plein : n/(n-l)

<=2.

Dans tous les cas, pour des réseaux linéaires de longueur maximum k et pour un hypercube incomplet de profondeur I, le délai maximum en terme de durée de transmission est égal à

n + k - 1 (3)

alors que le délai maximum en termes de délai de propagation total est

(n - I + k + 1).D (4)

Pour obtenir ces limites, il suffit de calculer le délai d'un bloc ayant descendu le sous- réseau linéaire le plus long et remonté à un pair dans le dernier niveau complet. Cela peut se produire qu'un bloc de données soit envoyé au niveau 1+1 depuis le niveau supérieur au plus n- 2 fois. Il est finalement renvoyé au niveau 1+1.

On obtient le nombre limite de transmissions total n + k - 1.

Notons que l'on ré-obtient un délai n si k=l et seulement un délai n+1 si k=2.

De la même façon, les blocs de données reçus au niveau 1+1 depuis le niveau supérieur ont subi un délai total de propagation de

(n-l).D

Les blocs de données peuvent ensuite subir un délai maximum de kD à travers le sous-réseau linéaire et un délai D pour retourner à leur pair de destination au niveau 1+1, soit un délai maximum total :

(n-l+k+l).D

3.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-l est non vide, ce qui signifie que le pair 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-l est vide, le niveau L n'étant pas complet. Chacune de ces règles R21, R22 utilise des routines pour obtenir un identifiant de base et une liste ordonnée étendue LOE dont l'obtention va maintenant être décrite en référence aux figures 11, lia, 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 IDq et à numéro Kq d'un bloc de données numéroté quelconque.

Dans un mode de réalisation, cet identifiant de base est obtenu par une étape P700 de détermination d'une séquence de fin SEQq de l'identifiant de pair quelconque 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 IDq , 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 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

D'une façon générale, la liste LOE est obtenue à partir d'un identifiant générateur IDGj et d'un bloc BK 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 LOljk 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érateur IDGj serait susceptible de transmettre ledit bloc numéroté BK selon ladite règle générale R.

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+l, 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 LOljk.

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. Ce 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-l) + ... + C(n-L-1, 0).

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» à droite, suivi de n-2 bits à gauche, dont (L -1) bits à « 0 », et ainsi de suite jusqu'au dernier sous-niveau composé du seul pair avec L bits à « 0 » à droite suivis d'un bit à « 1 », suivi de (n - L - 1) bits sans « 0 » à gauche.

On appelle « séquence de fin » (« trailer » en anglais) les bits à droite qui caractérisent un sous-ensemble.

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 fin », une telle séquence étant composée d'un nombre de « 0 » (ce nombre pouvant être nul) suivi d'un bit à « 1 » à gauche.

Cette 'séquence de fin' est décalée dans l'identifiant du pair 'Α'.

Il 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 Γ « identifiant de base » de l'identifiant de A pour le bloc k.

Nous allons définir un premier procédé d'association RAI qui, à un identifiant de pair

IDq et à un numéro Kq de bloc BKq de données numéroté, associe un identifiant de base obtenu par déplacement de la séquence de fin SEQq dans l'identifiant de pair IDq à une position Kq correspondant au numéro Kq de bloc BKq, les autres éléments binaires dudit identifiant de pair IDq étant décalés.

L'ascendant (en général indirect) du pair 'A' dans le niveau L+ l pour le bloc de données k est le même que celui de son « identifiant de base » pour le bloc k, c'est-à-dire l'ascendant, pour ce bloc de données k, du pair identifié par l'identifiant obtenu par le décalage de la 'séquence de fin' dans l'identifiant de A tel que le bit « 1 » est en position k.

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, de A pour le bloc de données Bk de numéro 4 est le même que l'ascendant du pair Ί 100 pour ce bloc, où on reconnaît que Ί 100 est l'identifiant de base de A pour le bloc 4. Cet ascendant Ak a pour identifiant '11000' d'après la règle générale. Il 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 T de sa 'séquence de fin Ί" en position 4 donne l'identifiant Ί 100 , 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 dans une liste LOljk. Ainsi à tout destinataire j d'un bloc Bk provenant d'un niveau supérieur d'après 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, appartient à une et une seule liste LOljk qui 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 é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 Bk provenant d'un niveau supérieur doit retransmettre ce bloc vers un destinataire j l 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 LOljk à laquelle on a rajouté en fin de liste l'identifiant j l.

Ainsi les listes LOE, obtenues à partir d'identifiants de base d'un niveau L et de 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 le pair ¹ 10110' dont la séquence de fin est « 10 ».

Table III

La table IV représente comment le pair 'ΙΟΟΟ 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 'ΙΟΟΟ dans le niveau suivant d'après la règle générale. Pour chaque un intervalle de temps donné représenté par un Ό' dans son identifiant, le pair 'ΙΟΟΟ 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

1er 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 'ΙΟΟΟ 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 la liste LOE appartient au même niveau que 'ΙΟΟΟ 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 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+l, 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 niveau L+l, 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 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 à riog ₂ (N)1 depuis leur émission par la source, où riog ₂ (N)1 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 2 ^{n l} <N<2 ⁿ . C'est aussi le cas des blocs reçus après une transmission suivant la règle générale. Etant donné que ces deux règles permettent de diffuser tous les blocs à tous les pairs, ceci démontre que ce procédé de diffusion permet à tous les pairs de recevoir tous leurs blocs en moins de riog ₂ (N)1 transmissions depuis leur émission par la source. Il est de plus possible de diminuer la moyenne du nombre total de transmissions des blocs par les pairs depuis leur émission par la source. Ceci peut être obtenu en attribuant d'abord les identifiants avec les 'séquences de fin' les plus longues dans le dernier niveau non vide.

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 'Α'. 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 'A' pour tout bloc k. Suivant ce nouveao procédé Γ « identifiant de base » de 'A' pour un bloc k est obtenu en décalant circulairement la totalité de l'identifiant de 'A' (sur la longueur de l'identifiant) tel que le bit « 1 » de sa séquence de fin se retrouve en position k. Une rotation circulaire d'un identifiant « a _n a _n -i...ai » de longueur n produit par exemple l'identifiant « a _n- i...aia _n ». 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 k est Γ « identifiant de base » de l'identifiant de A pour le bloc k dans ce deuxième exemple.

L'ascendant (en général indirect) du pair 'A' dans le niveau L+ l pour le bloc de données k est celui qu'aurait son « identifiant de base » pour le bloc k dans la règle générale de l'hypercube.

On considère par exemple un niveau 2 incomplet dans un hypercube de dimension 5, et l'identifiant ' 10110'.

Cet identifiant correspond à l'identifiant d'un pair 'A' du sous-niveau avec la 'séquence de fin '10'. L'ascendant, Ak, de A pour le bloc de données Bk de numéro 4 est le même que l'ascendant du pair '11010' pour ce bloc, où on reconnaît que '11010' est l'identifiant de base de A pour le bloc 4 obtenu par rotation circulaire de 2 positions vers la gauche de l'identifiant ' 10110'. Cet ascendant Ak a pour identifiant '11000' d'après la règle générale. Il 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 '01011' lorsqu'on place le T de sa 'séquence de fin Ί" en position 4 donne l'identifiant '11001', 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 dans une liste LOl'jk. Une différence importante de cette liste par rapport à celle définie dans l'exemple précédent est que la liste LOl'jk est la même pour tous les blocs k. Ainsi un pair dans un niveau incomplet appartient à une seule liste de diffusion, ce qui limite le nombre de pairs à notifier lors de son arrivée ou lors de son départ. Cette liste peut être ordonnée soit en fonction d'un ordre arbitraire soit suivant une règle. Une règle possible peut être de placer en tête de liste les pairs avec la plus grande séquence de fin. Ceci est illustré dans les séquences présentées à titre d'exemple dans le Tableau VI suivant.

Tout destinataire j d'un bloc Bk provenant d'un niveau supérieur doit retransmettre ce bloc vers un destinataire jl unique dans le niveau supérieur d'après la règle générale. C'est en particulier le cas pour l'identifiant de base auquel est associé la liste LO'ljk, identifiant qui possède un unique destinataire jl pour le bloc Bk dans le niveau L+1. Ainsi à toute liste LO'ljk on peut associer une liste étendue ordonnée LOE d'identifiants égale à la liste LO'ljk dans laquelle on a inséré l'identifiant jl.

Ainsi les listes LOE, obtenues à partir d'identifiants de base d'un niveau L et de numéros de bloc k, définissent une règle possible, R22, de diffusion d'un bloc k parmi les pairs du niveau L et les pairs du niveau L+1 sensés recevoir le bloc k du niveau L d'après la règle générale.

La table V représente les ascendants et descendants pour chaque bloc de données échangé par le pair ¹ 10110' dont la séquence de fin est « 10 ». Dans ce tableau on a choisi, à titre d'exemple, d'ordonner les listes LOE suivant la longueur décroissante des séquences de fin en plaçant en fin de liste l'unique identifiant de niveau L+1.

Table V

On remarque que le pair ¹ 10110' possède le même descendant 'ΟΙΟΙ quelque soit le bloc k, descendant dont l'identifiant est obtenu par rotation circulaire de ¹ 10110'.

La table VI représente comment le pair 'ΙΟΟΟ 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 'ΙΟΟΟ dans le niveau suivant d'après la règle générale. Pour chaque intervalle de temps donné représenté par un 'Ο' dans son identifiant, le pair ' ΙΟΟΟΓ possède un destinataire j dans le niveau inférieur, auquel on associe une liste LOE comme suit :

Table VI

Dans cet exemple, le pair 'ΙΟΟΟ 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 la liste LOE appartient au même niveau que 'ΙΟΟΟ 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 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.

La règle de constitution des listes LOE et 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 à riog ₂ (N)1 depuis leur émission par la source, où riog ₂ (N)1 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 2 ^{n l} <N<2 ⁿ . C'est aussi le cas des blocs reçus après une transmission suivant la règle générale. Etant donné que ces deux règles permettent de diffuser tous les blocs à tous les pairs, ceci démontre que ce procédé de diffusion permet à tous les pairs de recevoir tous leurs blocs en moins de riog ₂ (N)1 transmissions depuis leur émission par la source.

II est de plus possible de diminuer la moyenne du nombre total de transmissions des blocs par les pairs depuis leur émission par la source. Ceci peut être obtenu en attribuant d'abord les identifiants avec les 'séquences de fin' les plus longues dans le dernier niveau non vide. 3.2.5 Règle R21

Dans le premier mode de réalisation décrit ici, la règle R21 comprend une étape P310 de détermination, conformément à la règle R générale, à partir du numéro K du bloc BK et de l'identifiant IDi, du pair considéré d'une liste ordonnée L03 comportant les identifiants IDTij des pairs destinataires théoriques du bloc BK.

Puis, pour chacun des identifiants IDTij des destinataires théoriques pris dans l'ordre de cette liste ordonnée L03, on teste, au cours d'une étape P320, si cet identifiant IDTij appartient au niveau L-l.

Si c'est le cas, la règle R21 comporte une étape P360 de détermination de la liste ordonnée étendue LOE, comme décrit précédemment en référence à la figure 11, à partir de l'identifiant IDTij de destinataire théorique et du numéro K du bloc numéroté BK.

Au cours d'une étape P370, la règle R21 permet d'obtenir un pair destinataire PD identifié par le premier identifiant attribué A3 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.

Lorsqu'il est déterminé à l'étape P320 que l'identifiant IDTij de destinataire théorique appartient au niveau L+l, le pair identifié par l'identifiant IDTij est ajouté à 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 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 œuvre 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 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 l'identifiant et de l'adresse de chacun des voisins de ces pairs Pjm à identifier.

Cette adresse est reçue par le système d'aiguillage mettant en œuvre l'invention lors d'une étape P25 et peut être mémorisée ensuite dans la mémoire non-volatile réinscriptible 114. L'adresse du pair destinataire peut être obtenue par lecture dans cette mémoire non- volatile réinscriptible. 3.2.6 Règle R22

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 œuvre l'invention est 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 œuvre 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 étendue LOE, comme déjà décrit en référence à 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 œuvre 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 PD identifié par le premier identifiant attribué A4 suivant l'identifiant IDi 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 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-l est complet ou vide, des informations permettant à ce système d'aiguillage de déterminer si le niveau L-2 est vide.

Lorsqu'un événement est détecté, l'unité de gestion envoie aux étapes G220 et G230, aux systèmes d'aiguillage en charge des pairs à notifier et des pairs à identifier, en plus des informations décrites en référence au premier mode de réalisation, des d'informations permettant à 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 Pqr à 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 Pqr à 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 ou du pair remplaçant PR était le seul de son niveau.

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, PI 10, 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.

Dans ce mode de réalisation, le système d'aiguillage doit recevoir, de l'unité de 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 hypercubes complets si le niveau L-2 n'est pas vide.

Dans ce mode de réalisation, le système d'aiguillage mettant en œuvre l'invention n'utilise jamais la règle RI .

Il utilise la règle R21 si L- l n'est pas vide (étape P100).

II utilise la règle R22 si le niveau L- l 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.

4.3 Implémentation matérielle

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 référence aux figures 12 et 13.

Seuls les programmes d'ordinateur PGM l et PGM2 sont modifiés en ce qui concerne les étapes Pl i, P21, P26, P31, P41, P51, P61. 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 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.

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 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 T10, 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 par un système d'aiguillage DA mettant en œuvre 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, 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éseau 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.