FR 2932630 A1 20091218 FR 0853893 A 20080612 Procédé et dispositif de construction d'un codage réseau pour la transmission de paquets de données, produit programme d'ordinateur et moyen de stockage et support d'enregistrement correspondants. 1. DOMAINE DE L'INVENTION Le domaine de l'invention est celui des techniques de codage réseau (parfois aussi appelé codage sur réseau ou codage de réseau), c'est-à-dire des techniques liées à la théorie de l'information et utilisant des codes réalisant l'utilisation de la capacité de transport d'information d'un réseau. Plus précisément, l'invention concerne une technique de construction d'un codage réseau adapté à la transmission de paquets de données, dans un réseau de communication maillé, depuis un ensemble S de M noeuds sources vers un ensemble D de N noeuds destinations, avec M>l et N>1. Les transmissions considérées sont multidiffusion (aussi appelé � multicast � par la suite), c'est-à-dire que chaque message envoyé par un noeud source est destiné à l'ensemble des noeuds destination de D. Les autres noeuds (c'est-à-dire autres que les noeuds sources et noeuds destinations) sont des noeuds relais, utilisés pour retransmettre les messages sources envoyés par les noeuds sources. De plus, les transmissions considérées sont supposées sans délai (le délai de transmission est supposé nul ainsi que le temps de traitement des opérations dans les noeuds relais). Enfin, la topologie du réseau est supposée connue, c'est-à-dire l'ensemble des qualités radio entre deux noeuds communicants est connu, basé par exemple sur le RSSI (pour � Radio Signal Strength Indication � en anglais, ou � mesure de la puissance d'un signal reçu � en français) ou le SNR (pour � Signal Noise Ratio � en anglais, ou � rapport signal à bruit� en français). L'invention s'applique notamment, mais non exclusivement, dans un contexte de médium partagé. Dans un tel contexte, l'invention s'applique à des systèmes de transport d'informations tels que des réseaux sans fil dont tous les membres utilisent une même bande de fréquences en accès à division temporelle (TDM, pour �Time Division Multiplexing � en anglais) ou bien des ensembles de calculateurs partageant un bus commun. Les techniques de codage réseau sont très récentes et n'ont aujourd'hui pas d'application commerciale connue autre que le système � Avalanche � (marque déposée) proposé par Microsoft Corp. Des essais sur des réseaux sans fil ont toutefois été effectués avec des résultats encourageants (voir l'article : S. Katti, H. Rahul, W. Hu, D. Katabi, M. Médard, J Crowcroft, "XORs in the air: Practical Wireless Network Coding". SIGCOMM 2006). On remarquera que l'utilisation d'un codage réseau peut être catastrophique si le réseau n'est pas entièrement prêt et adapté à ce code. En effet, dans le cas d'inadaptation, au lieu de recevoir des informations qui sont partiellement exploitables, certains noeuds peuvent ne recevoir que des informations inexploitables. 2. ARRIÈRE-PLAN TECHNOLOGIQUE 2.1 Théorie des graphes Le réseau est modélisé par un graphe G=(V,E), V étant un ensemble fini de K noeuds (appelés � vertices � en anglais), V= {x,, . . . , xK}, et E Ç V x V un ensemble fini d'arêtes qui connectent les noeuds. L'ensemble E est un ensemble ordonné de couples (xi, xi), avec x; et xj appartenant à v, ces couples étant appelés arêtes connectées, arcs ou liens (appelés � edges � en anglais). Un noeud de V modélise une entité communicante dans le réseau (par exemple un ordinateur, un haut-parleur, un amplificateur...) tandis qu'un arc (xi, xj) indique un lien de communication (par exemple une communication radio suffisamment � bonne �, c'est-à-dire au dessus d'un certain seuil de puissance radio reçue) entre les deux entités communicantes x; et xj. Remarque d'implémentation : un graphe G peut être représenté par sa matrice d'adjacente A = (a;,) qui correspond à une rnatrice carrée d'ordre K. Un élément ai a une valeur de : > 0 s'il n'existe pas d'arc de x; vers xj, > 1 s'il existe un arc de x; vers xj, Donc la condition (x;,xl) E E (condition utilisée dans les figures 6 et 10) peut s'écrire en terme d'implémentation a;j=l. Et respectivement (x;,x1) E peut s'écrire en terme d'implémentation a;i=0. 3 Un élément appartenant à l'ensemble Suc(x) = {y 1 (x, y) E E} est considéré comme un successeur de x. De même, un élément appartenant à l'ensemble Pred(x) _ {y I (y, x) E E} est considéré comme un prédécesseur de x. Le réseau étudié est constitué d'un ensemble S={S,,S,,...SM} de M noeuds 5 sources et d'un ensemble D={D,,D,,..DN} de N noeuds destinations. D'un point de vue du graphe, ceci signifie que : V i =1..M, Pred(S;) = 0 Vj=1..NdeD,Suc(Dj)=0 On appelle chemin entre un noeud x, et un noeud xp un ensemble ordonné de 10 noeuds {x,,x,,..,xp} tel que (xi, x;+,) E E pour i = 1, . . . , (pùl). Un chemin peut aussi s'écrire {(xl,x2),..,(x;,x;+,),...,(xp_,,xp)} avec (x,,xk+,) EE pour k = 1, . . . , (pùl). On appelle k chemins disjoints, k ensembles qui n'ont pas deux noeuds consécutifs en commun, soit d'un point de vue � graphique �, deux arcs en commun. Notons T un ensemble de k chemins disjoints. On définit alors : 15 1. Soit (x, y) E E (un lien du graphe;), (x, y) E T si et seulement s'il existe un chemin de T qui contient (x,y) 2. Soit x E V (un sommet du graphe), x E T si et seulement s'il existe un chemin de T qui contient x. Définition importante : On appelle deux chemins disjoints entre un ensemble S 20 et un noeud d, deux ensembles ordonnés de noeuds {xäx,,..,xp,d} et {y,,y,,..,yq,d} tels que : - (x;,x;+1)EEpour i=1,...,(pù1) et (x, d) E E (y;,y;+,)EEpour j=1,...,(qù1) et(yq,d)EE - x, E S, y, E S et x,?y, 25 - di=1..(p-I),Vj=1..(q-1), ? ()f;,y;+i)et(xp,d)? yq,d) On définit alors que les � noeuds sources associés � à un ensemble de deux chemins disjoints entre S et d sont les deux noeuds sources de S : x, et y, (les points de départ des chemins disjoints). 4 La définition se généralise très facilement pour un ensemble de k chemins disjoints. Les � noeuds sources associés � à un ensemble de k chemins disjoints entre S et d sont les k noeuds sources de S, points de départ des k chemins disjoints. Une remarque clé est la suivante : un ensemble S de k noeuds sources est dit capable d'envoyer simultanément un paquet (différent pour chaque noeud source) à un noeud destination d si et seulement si il existe k chemins disjoints entre S et d dans le graphe. L'ensemble S est alors qualifié de � cohérent � relativement au noeud destination d. Cette notion de cohérence d'un ensemble de noeuds sources relativement à un noeud destination est maintenant illustrée avec la figure 12. Ce réseau est constitué de quatre noeuds sources a, b, c et d (S = {a, b, c, d}), trois noeuds relais e, f et g, et deux noeuds destinations h et i (les identifiants lettres sont utilisés pour plus de clarté). L'ensemble S1, sous-ensemble de S, constitué des noeuds sources a et b peut-il communiquer avec (c'est-à-dire est-il cohérent relativement à) le noeud destination h ? La réponse est oui car il existe bien deux chemins disjoints 11 et 12 entre S1 et d : 1. 11 = {a,e,h} = {(a,e),(e,h)} 2. 12 = {b,g,h} = {(b,g),(g,h)} Par contre, l'ensemble S2 constitué des noeuds sources a, b et c ne peut pas communiquer avec (c'est-à-dire n'est pas cohérent relativement à) le noeud destination h. En effet, il n'existe pas trois chemins disjoints entre S2 et h. D'ailleurs, dans ce graphe, il n'existe pas trois chemins disjoints entre n'importe quel sous-ensemble de S constitué de trois noeuds sources et le noeud destination h. Donc le nombre de noeuds sources capables d'émettre simultanément un paquet à h est 2. Le noeud a envoie une information x, à travers le chemin 11 et le noeud b envoie une information xe à travers le chemin 12. L'état de l'art donne une (et une seule) solution pour trouver le nombre maximal de chemins disjoints entre S et d, ainsi qu'un ensemble de chemins disjoints correspondant à cette unique solution. La technique connue utilise un cas particulier de l'algorithme du Ford & Fulkerson (se repor.er à "Maximum Flow through a Network" Canadian Journal of Mathematics, 8 , pp 399-404, 1956) qui donne une solution itérative pour trouver un nombre maximal de chemins disjoints en temps polynomial entre une source s et une destination d. La solution est itérative car l'algorithme part d'un ensemble vide T et détermine à chaque itération un nouveau chemin disjoint à ajouter par un algorithme de marquage (plus précisément, une itération peut remettre en cause plusieurs chemins de T tant qu'à la fin de l'itération le cardinal de T a augmenté). 11 est à noter que le graphe d'application de l'algorithme est particulier car il ne doit pas posséder un ensemble de noeuds sources mais un unique noeud source. Pour cela, un graphe G' est construit de la manière suivante. Un nouveau noeud, appelé super-source Sv, est introduit et relie chaque noeud source de S, c'est-à-dire qu'un lien est ajouté entre le nouveau sommet Sv et chaque noeud de S. L'algorithme de Ford- Fulkerson détermine alors le nombre maximum de chemins disjoints entre Sv et d et l'ensemble T des chemins disjoints associés. Or vu la construction de notre graphe, à chaque chemin disjoint est associé un unique noeud source. Donc, le nombre maximum de chemins disjoints entre Sv et d est égal au nombre maximum de chemins disjoints entre l'ensemble S et d, et les chemins disjoints entre S et d sont les chemins entre Sv et d moins les liens qui ont été ajoutés entre Sv et les noeuds sources de S. Le diagramme de flot de l'algorithme de Ford-Fulkerson est décrit dans la figure 13. L'algorithme débute à l'étape 1300 avec un ensemble vide T de chemins disjoints. Puis l'étape 1305 recherche un nouveau chemin disjoint en marquant les noeuds de manière très proche de l'algorithme de marquage décrit par la suite dans la figure 10 (les différences sont expliquées lors de la description de la figure 10). Si le noeud destination est marqué (test positif à l'étape 1310), ceci correspond au fait que nous pouvons ajouter un nouveau chemin disjoint à T (étape 1315). Sinon fin de l'algorithme (étape 1320), on a trouvé l'ensemble maximal de chemins disjoints. L'étape 1315 qui ajoute un nouveau chemin disjoint dans T est expliqué par la suite avec la figure Il. La remarque importante à noter est que l'algorithme décrit ci-dessus donne le nombre maximal de chemins disjoints entre S et d et un seul ensemble maximal de chemins disjoints entre S et d, ce qui implique un seul ensemble de noeuds sources. Dans le cadre de la figure 12, l'algorithme aurait indiqué qu'il existe au maximum deux chemins disjoints entre S={a,b,c,d} et h. Il aurait donné un seul ensemble maximum de chemins disjoints, par exemple 1l et 12 et donc le couple de noeuds sources (a,b). Mais il est à noter que cette solution n'est pas unique. Les couples (a,c),(a,d),(b,c),(b,d) auraient aussi été possibles mais par contre l'algorithme indique qu'aucun triplet de noeuds sources n'est possible. Remarque d'implémentation : un ensemble de chemins disjoints T peut être représenté par sa matrice d'adjacence B = (b;j) qui correspond à une matrice carrée d'ordre K. Un élément b;d a une valeur de : 0 si l'arc (x;,xl) n'est un lien d'aucun chemin disjoint de T, > l si l'arc (x;,xj) est un lien d'un chemin disjoint de T (que d'un unique chemin car les chemins sont disjoints). Donc la condition (x;,xj) E T (condition utilisée dans les figures 6 et 10) peut s'écrire en terme d'implémentation b=1. Et respectivement (x;,xj) EA T peut s'écrire en terme d'implémentation b;j=0. 2.2 Codage réseau La question est de savoir le nombre maximum de noeuds sources capables d'émettre simultanément, non pas à un seul noeud destination, mais à un ensemble de noeuds destinations. Par la suite, on note Fq un corps fini constitué de q éléments. Ainsi, s bits consécutifs d'un paquet constitue un symbole sur le corps Fq avec q=2`. L'état de l'art donne la réponse suivante à la question précitée : soit S un ensemble de M noeuds sources, s'il existe M chemins disjoints entre S et chaque noeud destination d'un ensemble D de N noeuds destinations, alors les M noeuds sources sont capables d'émettre simultanément en multicast vers l'ensemble D si les noeuds relais sont autorisés à combiner linéairement leur paquets entrant sur un corps fini suffisamment grand. Cette condition est appelée par la suite � condition de codage réseau � (� Network Coding condition � en anglais). Ce résultat est une conséquence directe du travail précurseur de R. Ahlswede and co. (voir l'article : R. Ahlswede, N. Cai, S.-Y. R. Li and R.W. Yeung "Network Information Flow" I.E.E.E. Transactions on Information Theory Vol 46, No 4, pp 1204-1216, July 2000). On appelle par la suite schéma de codage, la valeur des coefficients des combinaisons linéaires. Un exemple classique de codage réseau est illustré sur la figure 14. L'ensemble S est composé des noeuds sources a et b. L'ensemble D des noeuds destinations est composé des noeuds e et f. La condition de codage réseau est bien vérifiée : > Le cardinal de S est deux. - Il existe deux chemins disjoints entre S et e : 11={a,e} et 12={b,c,d,e} - Il existe deux chemins disjoints entre S et f : 11={a,c,d,f} et 12={b,f} Donc un codage réseau est bien possible. Un exemple de codage réseau est donné sur le corps F, avec l'opération binaire XOR noté G. Le noeud source a (respectivement b) envoie l'information xa (respectivement xh). Le noeud relais c décide de combiner ces deux informations xa O+ xh. Puis le noeud relais d transfère xa O+ xh aux noeuds destinations e et f. x,, (resp. xh) ont été reçues directement par le noeud destination e (resp. f). Le noeud destination e, qui reçoit xa et xa O+ Xb, peut reconstruire xh = x� + xa O+ xh. Le noeud destination e, qui reçoit xh et xa O+ xh, peut reconstruire xa = xa xh O+ xh. Donc les deux noeuds destinations de l'ensemble D ont reçu xa et xh Cet exemple est intéressant car aucun schéma de routage n'aurait réussi. 2.3 Limites de l'état de l'art Dans l'état de l'art, on sait déterminer une borne supérieure (aussi appelé � capacité du réseau � et notée C) sur le nombre maximal de noeuds sources capables d'envoyer simultanément, en multicast, un paquet (différent pour chaque noeud source) à tous les N noeuds destinations de l'ensemble D. Cette borne se calcule de la manière suivante : a) Pour chaque noeud destination d; parmi les N noeuds destinations de D, détermination du nombre maximal de noeuds sources C; (aussi appelée � capacité du noeud destination d �) capable d'atteindre le noeud d; par des chemins disjoints, b) La borne supérieure est égale à c = Min (C;), avec i= 1...N. Le nombre de noeuds sources capables d'envoyer simultanément un paquet à D en multicast est alors inférieur ou égal à C. Si la borne C calculée est égale à m, alors la condition précitée de codage réseau garantit que le nombre de noeuds sources capables d'envoyer simultanément un paquet à D est égal aussi à m, c'est-à-dire tous les noeuds sources de l'ensemble S. En revanche, l'art antérieur n'enseigne pas, dans le cas où C est inférieur à m, comment trouver le nombre maximal de noeuds sources capables de faire du multicast simultané. Cette situation où C est inférieur à m, signifie que le réseau maillé n'est pas adapté aux nombre de sources. Or, il est important de pouvoir apporter une réponse à cette question car cette situation est assez courante, notamment dans un réseau maillé sans-fil à capacité limité qui peut être fortement perturbé par des obstacles fixes tel des meubles, canapés, individus fixes qui dégradent fortement les transmissions entre les entités communicantes durant l'état de marche du système. En reprenant l'exemple de la figure 12, il existe uniquement deux chemins disjoints entre S={a,b,c,d} et le noeud destination h, et aussi deux chemins disjoints entre S et le noeud destination i. On a donc : M=4 et C=2. La condition précitée de codage réseau n'est donc pas respectée (il nexiste pas quatre chemins disjoints entre S et chacun des noeuds destinations h et i). En outre, l'art antérieur n'enseigne pas. dans ce cas (C Un autre objectif d'au moins un mode de réalisation de l'invention est de fournir une telle technique qui permette de déterminer le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet (différent pour chaque noeud source) à tous les N noeuds destinations de l'ensemble D (c'est-à-dire en multicast, chaque paquet envoyé par un noeud source devant être reçu par l'ensemble D). Un autre objectif d'au moins un mode de réalisation de l'invention est de fournir une telle technique qui permette de déterminer la liste complète des ensembles maximaux de noeud sources (sous-ensembles de S) capables d'envoyer simultanément un paquet (différent pour chaque noeud source) à tous les N noeuds destinations de l'ensemble D. Un autre objectif d'au moins un mode de réalisation de l'invention est de fournir une telle technique permettant de donner le schéma de codage des noeuds relais (c'est-à-dire quels sont les noeuds relais qui participent et quels sont les paquets retransmis), permettant à un ensemble maximal de noeuds sources déterminé par l'invention d'envoyer simultanément en multicast à l'ensemble D des noeuds destinations. Un autre objectif d'au moins un mode de réalisation de l'invention est de fournir une telle technique pouvant s'appliquer à un réseau de communication comprenant un médium partagé. Un autre objectif d'au moins un mode de réalisation de l'invention est de fournir une telle technique qui soit simple à mettre en oeuvre et peu coûteuse en ressources de calcul. 4. EXPOSÉ DE L'INVENTION Dans un mode de réalisation particulier de l'invention, il est proposé un procédé de construction d'un codage réseau adapté à la transmission de paquets de données, dans un réseau de communication maillé, depuis un ensemble S de M noeuds sources vers un ensemble D de N noeuds destinations, ledit procédé comprenant les étapes suivantes : A) détermination d'une liste initiale L1 comprenant tous les ensembles cohérents de noeuds sources de cardinal card_src relativement à un premier noeud destination, un ensemble cohérent de noeuds sources relativement à un noeud destination donné d étant un ensemble dont tous les noeuds sources peuvent envoyer simultanément, via des noeuds relais. un paquet audit noeud destination donné d ; 10 B) détermination d'une liste modifiée L comprenant le ou les ensembles cohérents de noeuds sources, s'il(s) existe(nt) parmi ladite liste initiale L1, qui est (sont) également cohérent(s) relativement à chacun des autres noeuds destinations de l'ensemble D, distincts dudit premier noeud destination ; C) si ladite liste modifiée L n'est pas vide, sélection parmi ladite liste modifiée L d'un ensemble cohérent de noeuds sources ; D) construction d'un codage réseau impliquant un sous-réseau comprenant : * l'ensemble cohérent de noeuds sources sélectionné, * lesdits noeuds destinations, et * les noeuds relais via lesquels les noeuds sources dudit ensemble cohérent de noeuds sources sélectionné envoient leurs paquets de données auxdits noeuds destinations. Ainsi, dans ce mode de réalisation particulier, l'invention repose sur une approche tout à fait nouvelle et inventive consistant à déterminer un sous-réseau pouvant supporter un codage réseau, c'est-à-dire un sous-réseau pour lequel la condition précitée de codage réseau est vérifiée. Il est à noter que pour certaines topologies du réseau, il se peut qu'aucun sous-réseau ne puisse être déterminé et donc qu'aucun codage réseau ne puisse être construit. De façon avantageuse, card_src est égal à une borne supérieure C, et en ce que ledit procédé comprend une étape de détermination de ladite borne supérieure C définie par : C = Min (Ci), avec i E{1..N} et Ci le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet de données au noeud destination di, avec di ED. Ainsi, on améliore la qualité du codage réseau construit et on optimise l'utilisation de la bande passante du réseau puisqu'on maximise le nombre de noeuds sources du sous-réseau sur lequel est construit le codage réseau. Avantageusement, ledit premier noeud destination est un noeud destination dont le nombre maximal Cd de noeuds sources capables de lui envoyer simultanément un paquet de données est égal à C. Ainsi, on optimise l'algorithme en coût de traitement. Selon une caractéristique avantageuse, l'étape A) de détermination de ladite liste initiale LI comprend les étapes suivantes : i détermination du nombre maximal Cd de noeuds sources capables d'envoyer simultanément un paquet de données au premier noeud destination ; ii détermination d'un premier ensemble cohérent ST de noeuds sources de cardinal Cd et d'un premier ensemble T de Cd chemins disjoints correspondant ; iii- initialisation de ladite liste initiale L 1 avec ledit premier ensemble cohérent ST de noeuds sources de cardinal Cd ; iv- sélection dudit premier ensemble cohérent ST de noeuds sources de cardinal Cd et dudit premier ensemble T de Cd chemins disjoints correspondant ; v- à partir de l'ensemble cohérent STse, de noeuds sources de cardinal Cd sélectionné et de l'ensemble T,e, de Cd chemins disjoints correspondant, détermination, s'il en existe au moins un, d'un autre ensemble cohérent ST' de noeuds sources de cardinal Cd et d'un autre ensemble T" de Cd chemins disjoints correspondant ; vi- ajout à ladite liste initiale Ll dudit autre ensemble cohérent ST' de noeuds sources de cardinal Cd ; vii- sélection dudit autre ensemble cohérent ST' de noeuds sources de cardinal Cd et dudit autre ensemble T' de Cd chemins disjoints correspondant, puis réitération des étapes v à vii. Ainsi, on réduit le temps de traitement puisqu'on trouve les ensembles cohérents de noeuds sources de la liste L sans tester tous les ensembles possibles de noeuds sources. Avantageusement, ladite étape v comprend les étapes suivantes : - sélection des noeuds sources n'appartenant pas à Tse,, formant un ensemble Sc de noeuds sources candidats initiaux à la création d'un nouveau chemin disjoint non compris dans Tse, ; à partir de chaque noeud source de l'ensemble Sc, et de manière itérative de noeud en noeud, marquage : * avec une première valeur de marquage, de noeuds candidats à la création d'un nouveau chemin disjoint non compris dans TSe,, et * avec une deuxième valeur de marquage, de noeuds candidats à se retirer afin de supprimer un chemin disjoint compris dans Tom, ; - en fonction du résultat dudit marquage, détermination du chemin disjoint à supprimer de Tee, et du nouveau chemin disjoint à ajouter dans TSe,, pour obtenir ledit autre ensemble T' ; - détermination des noeuds sources appartenant audit autre ensemble T' et formant ledit autre ensemble cohérent ST'. Ainsi, on réduit le temps de traitement puisque la liste L est construite de manière itérative : chaque nouvel autre ensemble cohérent de noeuds sources de la liste L est obtenu à partir d'un ensemble cohérent de noeuds sources déjà présent dans la liste L. Donc, on ne teste pas tous les ensembles possibles de noeuds sources. De façon avantageuse, l'étape v est réitérée, pour l'ensemble cohérent STse, de noeuds sources de cardinal Cd sélectionné et l'ensemble TSe, de Cd chemins disjoints correspondant, sur un nouveau graphe de réseau G' obtenu en ôtant d'un graphe de réseau courant : - le noeud source, appelé noeud source supprimé, qui appartient à l'ensemble Tse, 15 mais pas à l'autre ensemble T' ; - les liens dont une extrémité est ledit noeud source supprimé. Ainsi, on réduit le temps de traitement puisque chaque nouvel ensemble cohérent obtenu est forcément un ensemble qui n'est pas dans la liste L, ce qui nous garantit l'étude de tous les ensembles possibles sans nécessité de vérifier qu'un ensemble a déjà 20 été testé lors d'une itération précédente. Avantageusement, l'étape B) de détermination de ladite liste modifiée L comprend : - suite à une étape d'obtention de coefficients C;, avec i E{1..N}, où C; est le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet 25 de données au noeud destination d;, avec d; ED ; une étape de test de cohérence itérée pour chacun des autres noeuds destinations de l'ensemble D, suivant un ordre croissant desdits coefficients C. Ainsi, on réduit le temps de traitement puisque l'algorithme détermine tous les ensembles cohérents uniquement pour un seul noeud destinataire et non pour tous : un 30 noeud destinataire testé, en dehors du premier noeud testé, vérifie seulement la cohérence des ensembles cohérents des noeuds destinataires déjà testés. Donc au fur et à mesure des 10 noeuds destinataires testés, le nombre d'opérations diminue car le nombre d'ensembles diminue. Ainsi il serait inutile, par exemple, pour un noeud destinataire de déterminer ses 10 ensembles de 2 noeuds sources cohérents si le noeud précédent testé a seulement un unique ensemble de 2 noeuds sources cohérents. De plus, en prenant comme ordre des noeuds testés, le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet de données, le nombre d'opérations à réaliser est optimisé. En effet, il serait, par exemple, inutile de tester la cohérence d'un ensemble de 3 noeuds sources si le noeud destinataire testé ne peut recevoir au maximum que 2 noeuds sources en simultané. De façon avantageuse, l'étape B) de détermination de ladite liste modifiée L comprend une étape d'initialisation de ladite liste modifiée L avec ladite liste initiale L1 et, pour chaque autre noeud destination d' de l'ensemble D, une étape de mise à jour de ladite liste modifiée L comprenant les étapes suivantes : a) sélection d'un ensemble S de noeuds sources de la liste modifiée L, non encore vérifié ; b) vérification si ledit ensemble S est cohérent relativement audit autre noeud destination d' et détermination, en cas de vérification négative, d'un autre ensemble S' de noeuds sources cohérent relativement audit autre noeud destination d' ; c) si l'ensemble S est cohérent relativement audit autre noeud destination d', l'ensemble S est gardé dans la liste modifiée L, sinon : - suppression de l'ensemble S de la liste modifiée L ; et - vérification si l'autre ensemble S' est compris dans la sous-liste : en cas de vérification positive, l'autre ensemble S' est considéré vérifié et gardé dans la liste modifiée L ; d) sélection d'un nouvel ensemble S de la liste modifiée L, non encore vérifié, et retour à l'étape b). Ainsi, on réduit le temps de traitement puisque le test de cohérence, en cas d'échec de cohérence d'un ensemble, donne un autre ensemble compris dans la liste modifiée. Ainsi, on n'a pas besoin de tester tous les ensembles de la liste modifiée. Avantageusement, si à l'issue de l'étape B) ladite liste modifiée L est vide, le procédé comprend les étapes suivantes : a) détermination de M', avec : M' = card_src ù p, où p est un pas de décrémentation ; (3) détermination d'une nouvelle liste initiale L1 comprenant tous les ensembles cohérents de noeuds sources de cardinal M' relativement audit premier noeud destination ; Y) réitération de l'étape B) avec ladite nouvelle liste initiale LI et si à l'issue de l'étape B), ladite liste modifiée L n'est pas vide, passage à l'étape C), sinon retour à l'étape a). Ainsi, on détermine la capacité réelle Cr, du réseau (c'est-à-dire le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet à tous les noeuds destinations de D) et la liste des ensembles de noeuds sources associés (de cardinal CCe). Ceci permet d'optimiser l'utilisation de la bande passante du réseau. Dans un autre mode de réalisation, l'invention concerne un produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur. Ce produit programme d'ordinateur comprend des instructions de code de programme pour la mise en oeuvre du procédé précité (dans l'un quelconque de ses différents modes de réalisation), lorsque ledit programme est exécuté sur un ordinateur. Dans un autre mode de réalisation, l'invention concerne un moyen de stockage lisible par ordinateur, éventuellement totalement ou partiellement amovible, stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur pour mettre en oeuvre le procédé précité (dans l'un quelconque de ses différents modes de réalisation). Dans un autre mode de réalisation, l'invention concerne un support d'enregistrement, centralisé ou distribué, contenant un fichier de données lisible par ordinateur, ledit fichier de données contenant un codage réseau résultant de la mise en oeuvre du procédé précité (dans l'un quelconque de ses différents modes de réalisation), ledit codage réseau étant stocké dans ledit fichier de données sous la forme d'un jeu de coefficients associés aux noeuds relais compris dans ledit sous-réseau et définissant comment lesdits noeuds relais doivent combiner des paquets qu'ils reçoivent pour construire des paquets qu'ils émettent. 15 Dans un autre mode de réalisation, l'invention concerne un dispositif de construction d'un codage réseau adapté à la transmission de paquets de données, dans un réseau de communication maillé, depuis un ensemble S de M noeuds sources vers un ensemble D de N noeuds destinations, ledit dispositif étant caractérisé en ce qu'il comprend : A) des moyens de détermination d'une liste initiale L1 comprenant tous les ensembles cohérents de noeuds sources de cardinal card_src relativement à un premier noeud destination, un ensemble cohérent de noeuds sources relativement à un noeud destination donné d étant un ensemble dont tous les noeuds sources peuvent envoyer simultanément, via des noeuds relais, un paquet audit noeud destination donné d ; B) des moyens de détermination d'une liste modifiée L comprenant le ou les ensembles cohérents de noeuds sources, s'il(s) existe(nt) parmi ladite liste initiale L1, qui est (sont) également cohérent(s) relativement à chacun des autres noeuds destinations de l'ensemble D, distincts dudit premier noeud destination ; C) des moyens de sélection, si ladite liste modifiée L n'est pas vide, parmi ladite liste modifiée L d'un ensemble cohérent de noeuds sources ; D) des moyens de construction d'un codage réseau impliquant un sous-réseau comprenant : * l'ensemble cohérent de noeuds sources sélectionné, * lesdits noeuds destinations, et * les noeuds relais via lesquels les noeuds sources dudit ensemble cohérent de noeuds sources sélectionné envoient leurs paquets de données auxdits noeuds 25 destinations. 5. LISTE DES FIGURES D'autres caractéristiques et avantages de l'invention apparaîtront à la lecture de la description suivante, donnée à titre d'exemple indicatif et non limitatif, et des dessins annexés, dans lesquels : 30 ^ la figure 1 représente un premier exemple de réseau maillé sans fil dans lequel peut être mis en oeuvre le procédé selon l'invention ; ^ la figure 2 représente l'architecture d'un dispositif selon un mode de réalisation particulier de l'invention ; ^ la figure 3 présente un organigramme d'un mode de réalisation particulier du procédé de construction d'un codage réseau selon l'invention ; ^ la figure 4 décrit un algorithme de détermination de la capacité du réseau et de la liste des ensembles de noeuds sources, correspondant à l'étape 310 de la figure 3; ^ les figures 5a et 5b décrivent un algorithme de détermination de la liste des ensembles de noeuds sources pour un unique noeud destination, correspondant à l'étape 425 de la figure 4 ; ^ la figure 6 décrit un algorithme de marquage du graphe réseau, correspondant à l'étape 515 de la figure 5b ; ^ la figure 7 décrit un algorithme de détermination, à partir d'un ensemble de chemins disjoints, d'un autre ensemble de chemins disjoints, correspondant à l'étape 530 de la figure 5b ; ^ la figure 8 décrit un algorithme de mise à jour de la liste des ensembles de noeuds sources pour un noeud destination, correspondant à l'étape 440 de la figure 4 ; ^ la figure 9 décrit un algorithme qui teste si un ensemble de noeuds sources est capable d'envoyer simultanément un paquet à un noeud destination, correspondant à l'étape 815 de la figure 8 ; ^ la figure 10 décrit un algorithme de recherche d'un nouveau chemin disjoint entre un noeud source et un noeud destination, correspondant à l'étape 915 de la figure 9 ; ^ la figure 11 décrit un algorithme de construction d'un nouveau chemin disjoint entre un noeud source et un noeud destination, correspondant à l'étape 920 de la figure 9 ; ^ la figure 12, déjà décrite en relation avec l'art antérieur, permet d'illustrer la notion de cohérence d'un ensemble de noeuds sources relativement à un noeud destination ; ^ la figure 13, déjà décrite en relation avec l'art antérieur, présente le diagramme de flot de l'algorithme de Ford-Fulkerson ; 30 ^ la figure 14, déjà décrite en relation avec l'art antérieur, illustre un exemple de codage réseau ; la figure 15 représente un second exemple de réseau maillé sans fil, permettant d'illustrer les résultats de différentes étapes du procédé de construction d'un codage réseau selon un mode de réalisation particulier de l'invention. 6. DESCRIPTION DÉTAILLÉE La figure 1 représente un premier exemple de réseau maillé sans fil dans lequel peut être mis en oeuvre le procédé selon l'invention Les noeuds 100, 105 et 110 sont des entités désirant envoyer des paquets d'information de taille fixe. Ils sont appelés noeuds sources et l'ensemble de ces M (=3) noeuds sources est noté S. Les noeuds 115, 120 et 125 sont des entités qui ont pour fonction de relayer les paquets reçus. Ils ne produisent aucune information. Ces noeuds sont appelés noeuds relais. Ils ont la possibilité de relayer un paquet qui est une combinaison des paquets qu'ils ont reçus (comme déjà discuté ci-dessus). Les noeuds 130,135 et 140 sont des entités destinataires, qui attendent les paquets d'information envoyés par les noeuds sources. Ces noeuds sont appelés noeuds destinations. L'ensemble des N noeuds destinations est noté D. Une communication 145 entre deux noeuds est soit de type filaire soit de type sans-fil. Dans le cadre du mode de réalisation préférée, les communications sont de type sans-fil. Une communication a deux états : valide ou invalide. Une communication entre deux noeuds s et d est considérée valide s'il n'existe aucun obstacle entre s et d et si la distance entre s et d n'est pas trop grande. On suppose alors que la transmission est sans erreur, c'est-à-dire que l'information reçue par d est identique à l'information envoyée par s. Pour cela, l'homme de l'art peut utiliser un code de blocs linéaires type Reed-Solomon pour encoder l'information. Il fixera par rapport à un taux d'erreur prédéterminé du canal radio la taille du code. Un obstacle fixe 147 (meubles, canapé,...) peut casser une communication par exemple entre le noeud R2 et D2. La communication 146 est alors considérée invalide. Les transmissions considérées sont multicast, c'est-à-dire que chaque paquet envoyé par un noeud source est destiné à l'ensemble des noeuds destination de D (130, 135 et 140). La figure 2 illustre un mode de réalisation non limitatif d'un dispositif de communication (200) selon un mode de réalisation particulier de l'invention. L'invention se réalise indifféremment comme un programme exécuté sur une machine de calcul reprogrammable (un PC, un DSP, ou un microcontrôleur) ou sur une machine de calcul dédiée (un ensemble de portes logiques comme un FPGA ou un ASIC). L'invention est soit intégré dans un noeud source de la figure 1 ou dans un noeud central. Le dispositif est classiquement composé d'une unité centrale de calcul (CPU) 210, une mémoire vive (RAM) 205, une mémoire de stockage de masse 220, une mémoire morte (ROM) 215. De plus, il comprend d'une interface réseau 235 afin de communiquer avec d'autres dispositifs de communication distants 245 à travers un réseau 240 filaire ou non. Une interface homme-machine 225 est utilisée afin que l'utilisateur entre les paramètres d'entrée nécessaires à l'invention (identifiant des noeuds sources, des noeuds destinations, la qualité des liens du réseau entre deux dispositifs de communication). Une interface donnée 230, qui est en relation avec l'application, reçoit soit les données de l'application à destination de dispositifs distants, soit des données de dispositifs distants destinées à l'application. L'ensemble de ces blocs est relié par un bus 250. Le CPU 210 exécute le programme qui déroule le procédé de l'invention. Les diverses variables sont mémorisées en mémoire vive. Les moyens algorithmiques nécessaires sont détaillés dans les parties suivantes. La figure 3 présente un organigramme d'un mode de réalisation particulier du procédé de construction d'un codage réseau selon l'invention (algorithme de sélection des noeuds participant au codage réseau). Cet algorithme est réalisé au démarrage du système. L'étape 300 a pour but de récupérer la topologie du réseau, c'est-à-dire de récupérer l'état des communications entre les noeuds, la liste des noeuds sources et la liste des noeuds destinations. Cette topologie peut être connue des noeuds du réseau par construction si le réseau est fixe et si le nombre de noeuds est constant. Il est aussi certain que ces informations peuvent être introduites par l'utilisateur après l'installation d'un système par l'intermédiaire du module 225. L'étape 305 construit le graphe de réseau à partir de la topologie du réseau. Chaque entité communicante est modélisée par un noeud du graphe et chaque communication considérée valide entre deux entités est modélisée par un lien entre deux noeuds (et donc chaque communication considérée non valide n'est pas modélisée dans le graphe). Dans le graphe, plusieurs liens existent entre un premier noeud et plusieurs seconds noeuds lorsque le premier noeud est capable d'envoyer simultanément, dans le réseau réel auquel correspond le graphe, des paquets différents vers les seconds noeuds (chacun des seconds noeuds reçoit un paquet différent). Par exemple, sur la figure 1, il existe un premier lien entre le noeud S1 et le noeud RI et un second lien entre le noeud Si et le noeud R2. En outre, dans le graphe, plusieurs liens existent entre plusieurs premiers noeuds et un second noeud lorsque les premiers noeuds sont capables d'envoyer simultanément, dans le réseau réel auquel correspond le graphe, des paquets différents vers le second noeud (chacun des premiers noeuds envoie un paquet différent au second noeud). Par exemple, sur la figure 1, il existe un premier lien entre le noeud R1 et le noeud Dl et un second lien entre le noeud R2 et le noeud Dl. Dans le réseau réel auquel correspond le graphe, l'envoi simultané de paquets différents peut être réalisé par exemple : � soit par une transmission réellement simultanée sur différents média, avec un médium différent pour la transmission de chaque paquet ; ^ soit par une transmission sur un médium partagé en accès multiple par répartition dans le temps (TDMA, pour � Time Division Multiple Access � en anglais), avec un intervalle de temps différent pour la transmission de chaque paquet. L'étape 310 détermine à partir du graphe de réseau : premièrement la capacité du réseau, c'est-à-dire le nombre maximum de noeuds sources capables d'envoyer simultanément un paquet à tous les noeuds de D, et deuxièmement la liste complète des 20 ensembles de noeuds sources L. Cet algorithme est décrit plus précisément dans la figure 4. Puis, l'étape 315 choisit un ensemble de noeuds sources So dans la liste L. Ce choix peut être arbitraire ou déterministe (le premier de la liste). Une autre alternative est de fixer des priorités à chaque noeud source et de choisir l'ensemble de noeuds sources qui contient les noeuds sources les plus prioritaires. Puis, l'étape 320 détermine le schéma de codage des noeuds relais, c'est-à-dire les coefficients à attribuer aux noeuds relais pour que ceux-ci effectuent une combinaison des messages qu'ils ont reçus. Le codage réseau est effectué sur un graphe de réseau modifié Gmod qui ne prend en compte que les noeuds sources de So. Les autres noeuds sources du graphe sont supprimés. Les coefficients à attribuer aux noeuds relais sont alors calculés suivant la méthode décrite ci-après. Soit So un ensemble des noeuds sources capable d'émettre simultanément en multicast à D, So étant un sous-ensemble de S, de cardinal h : So={S,,..,Sh}. Soit Gmod, le sous-graphe associé ne contenant que les noeuds de So. La construction proposée des coefficients nécessite que le nombre de liens entrants dans un noeud destination ne soit pas plus grand que le nombre de noeuds sources, donc h liens entrants car on doit avoir h chemin disjoints entre l'ensemble So et chaque noeud destination. Pour ce faire, pour chaque noeud destination d;, on détermine un ensemble de h chemins disjoints entre So et di, noté Ti. Chaque T, pouvant être vu comme un sous-graphe de Gmod. Le procédé crée alors un graphe Goy, égal à l'union des Tj, c'est-à-dire que Goy comprend tous les noeuds et tous les liens compris au moins une fois dans un Ti. Tous les noeuds relais de Gop, (noeuds qui ne sont pas source ou destination) effectuent un codage réseau sur l'ensemble des paquets qu'ils reçoivent, c'est-à-dire qu'ils retransmettent systématiquement un paquet qui est une combinaison linéaire des paquets qu'ils ont reçu. Soit Ri un noeud relais, supposons qu'il ait reçu les paquets a,, a,,..., a, alors il envoie au réseau le paquet suivant : y, = a,a, avec a, , a,,...,ai appartenant au corps ' fini Fq. Cette addition s'effectue en réalité sur tous les symboles du paquet : = s a' .a,�*) 21 où y,' et a;" sont respectivement le kième symbole de y et de a;. Il est à noter que les opérations d'addition et de multiplication sont alors effectuées dans Fq. Le noeud destination di qui reçoit les paquets y,,y,,...,y1 doit alors résoudre l'équation : [y,',y,',...,y",'] = C [xäx,,...,xh] où C est appelée la matrice codante pour le noeud destination di dans le graphe multicast Gapä xä ...,x, étant les paquets envoyés respectivement par les noeuds S),..,Sh . Chaque élément de C est une combinaison linéaire de a,'. La représentation algébrique de la matrice est obtenue directement de manière itérative de l'équation (*). L'équation (*) représente un système d'équation linéaire qui peut être résolu par l'algorithme de Gauss-Jordan : la matrice C est transformée en matrice triangulaire. Elle doit être de rang h afin d'être inversible et donc de retrouver la valeur de [x,,x,,...,xh] à partir de [yIl faut que son déterminant soit différent de zéro. Cette condition doit être vraie pour tous les noeuds destinations. Donc l'équation suivante doit être vérifiée : F(a)= det(C,) ...det(CM) =0 (1) Or det(C,) ...det(CM) est un polynôme multi varié pour les variables a dans le corps Fq de degré maximal M. De ce fait, si q>M, il existe des coefficients a; tel que la condition soit vérifiée. De ce fait pour calculer les coefficients, l'algorithme est le suivant : (1) Initialisation de q à q=M+1 (2) on tire aléatoirement les a;' sur le corps Fq (3) On vérifie que la condition 1 est respectée (4) Si oui, fin de l'algorithme, sinon réitération de q avec q+l La condition (2) impose l'utilisation d'un générateur pseudo aléatoire à sortie dans le corps fini utilisé. Un tel générateur s'obtient par exemple en faisant une bijection entre les sorties d'un générateur suivant une loi normale ramenée à un intervalle [l qj dans l'ensemble des entiers (voir l'article suivant : W.Press, S. Teukolsky, W.Vetterling, B. Flannery, "Numerical recipes in C". W.Press, S. Teukolsky, W.Vetterling, B. Flannery, Cambridge University Press 2"d ed. 1992), puis en prenant l'élément du corps fini correspondant à la bijection. Il est à noter que chaque noeud destination di, pour résoudre le système d'équations linéaires, utilise une seule fois l'algorithme de Gauss-Jordan pour inverser la matrice C. dès qu' il a reçu les coefficients. L'algorithme de Gauss-Jordan est connu de l'homme de l'art. Puis, l'étape 325 est un protocole de diffusion des coefficients. Plusieurs techniques de diffusion sont connues de l'homme de l'art pour diffuser des informations dans un réseau maillé (de type inondation de données dans un protocole maillé, en anglais � flooding protocol �). A la fin de cette diffusion, chaque noeud source de So débute l'envoi des paquets d'information sur le réseau et chaque noeud relais envoie des paquets qui sont des combinés des paquets qu'il a reçu à partir des coefficients déterminés à l'étape 320. Les noeuds sources n'appartenant pas à So n'envoient aucun paquet sur ce medium. La figure 4 décrit l'algorithme de détermination de la capacité C du réseau et de la liste des ensembles de noeuds sources, correspondant à l'étape 310 de la figure 3. On appelle capacité d'un noeud destination D; le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet (différent pour chaque noeud source) au noeud D. On appelle capacité du réseau le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet (différent pour chaque noeud source) à l'ensemble D. L'étape 400 détermine séparément la capacité C; de chaque noeud destination D. La remarque importante est de voir que cela revient à déterminer un ensemble maximal de chemins disjoints (un ensemble de chemin de cardinal maximum) entre l'ensemble S et Di, et de sélectionner les � noeuds sources associés �. En effet, chaque paquet envoyé par un � noeud source associé � Si � suit � le chemin disjoint entre Sj et Di. Or pour calculer le nombre maximum de chemins disjoints entre un ensemble et un noeud d, il suffit d'utiliser un algorithme de max-flot comme le Ford-Fulkerson, méthode connue par l'homme de l'art. Par contre, il faut noter que l'algorithme doit être appliqué sur un graphe de réseau qui contient un unique noeud source et non un ensemble de noeuds sources S et il faut que le noeud destination étudié D; soit un noeud destination au sens de la théorie des graphes, soit Suc(D;) = 0. Le graphe construit en 305 doit être modifié pour cette étape. Pour cela, on crée un graphe de réseau avec une super-source Sv qui 3 relie chaque noeud source de S, c'est-à-dire qu'un lien est ajouté entre le nouveau sommet Sv et chaque noeud de S. De plus, pour chaque noeud destination Di étudié, le noeud Di doit être un noeud destination au sens de la théorie des graphes, donc il faut supprimer les liens sortant de Di. Appelons Gi, ces nouveaux graphes associés à chaque noeud destination Di, l'algorithme de Ford-Fulkerson détermine alors le nombre maximum de chemins disjoints entre Sv et chaque D et bien sûr détermine les chemins disjoints associés Di (qui sont stockés). Or vu la construction de notre graphe, à chaque chemin disjoint est associé un unique noeud source. Donc, le nombre maximum de chemins disjoints entre Sv et Di est égal au nombre maximum de chemins disjoints entre l'ensemble S et Di et correspond alors à la capacité C; de Di. L'étape 405 détermine la borne supérieure de la capacité du réseau en prenant le minimum de la capacité de chaque noeud destination Di. L'étape 410 vérifie si la capacité est égale à M ou pas. Dans le cas où cette capacité C est égale à m, la borne supérieure est atteinte d'après l'art antérieur. La liste L est donc réduite à un seul ensemble de noeuds sources qui est S. Sinon, l'étape suivante (415) est exécutée et le problème est nouveau. L'étape 415 classe les noeuds destinations selon la valeur de la capacité de chacun trouvée dans l'étape 400. L'ordre défini est le suivant : Dk Suite à l'étape 425, on passe à alors à l'étape 470 pour étudier le noeud destination classé deuxième. Une liste d'étude L est initialisée à L1. L'étape 435 construit un graphe de réseau unicast optimisé G'; par rapport à celui créé dans l'étape 400, G;, i étant dans ce cas l'indice du noeud destination étudié. Pour cela, on reprend le graphe G; et on supprime les noeuds sources qui ne sont contenus dans aucun ensemble de la liste L. Cette manipulation permet d'optimiser le temps de traitement. Se basant sur G';, l'étape 440 met à jour la liste L, c'est-à-dire qu'elle peut supprimer des éléments de la liste, c'est-à-dire des ensembles de noeuds sources � non compatibles � avec le noeud destination étudié. Cet algorithme est décrit précisément 20 dans la figure 8. L'étape 450 vérifie si la liste L est vide. Si oui, rien ne sert de continuer avec cette capacité, les ensembles de noeuds sources étudiés de la liste L ont un cardinal trop grand. Il faut alors réduire la capacité initiale (étape 455) recherchée, ceci voulant dire qu'aucun ensemble de C noeuds sources ne peut envoyer simultanément un paquet à 25 l'ensemble D. Puis le test de l'étape 460 (décrit ultérieurement) est effectué. Sinon on vérifie dans l'étape 445 si tous les noeuds destinations ont été testés. Si oui, fin de l'algorithme (étape 475), sinon on retourne à l'étape 430. Si l'algorithme s'arrête de cette manière à l'étape 475, ceci signifie : ^ que C n'est pas nulle, C représentant alors la capacité réelle du réseau ; que L n'est pas vide et contient tous les ensembles de noeuds sources de cardinal C, C étant la valeur maximale par rapport aux contraintes du réseau. L'étape 460 vérifie si la capacité est nulle ou pas. Si oui, fin de l'algorithme. La 5 liste L est vide. Aucun noeud source ne peut atteindre l'ensemble des noeuds destinations. Sinon on passe à l'étape 465. L'étape 465 reconstruit une nouvelle liste L I avec des ensembles de noeuds sources réduits car la capacité à été réduite dans l'étape 455. Donc le but de cette étape est de créer des ensembles de cardinal (C-1) à partir d'ensembles de cardinal C. La 10 méthode la plus simple est de récupérer tous les noeuds sources présents dans la liste LI initiale (de cardinal C) et de créer toutes les combinaisons possibles de taille (C-1). Le nombre de combinaisons est égale à : /card(L) card(L)! \C -1 (card(L)ùC+l)!(Cù1)! Donnons un exemple. Si la liste L1 avant l'étape 465 était L1={(1,2,3),(1,3,4)} 15 (L1 liste initiale établie à l'étape 425) avec des ensembles de noeuds sources de cardinal 3, l'étape 465 modifie cette liste de la manière suivante : ^ Nouvelle capacité étudiée : C=C-1=2 ^ Noeuds Sources contenus dans Ll : 1,2,3,4 ^ Création d'une liste LI avec des éléments de cardinal 2 : L1= 20 {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} Il faut alors de nouveau tester cette liste LI pour les autres noeuds destinations. On retourne donc à l'étape 470. Les figures 5a et 5b décrivent un algorithme de détermination de la liste L des ensembles de noeuds sources pour un unique noeud destination d, correspondant à l'étape 25 425 de la figure 4. La division en deux figures 5a (étapes 505 et 510) et 5b (étapes 515 à 555) fait apparaître l'aspect récursif de l'algorithme. Les paramètres d'entrée sont : un graphe de réseau multicast récupéré de l'étape 305 ; 30 un noeud destination d récupéré de l'étape 420 ; 26 ^ un ensemble maximal Td de Cd chemins disjoints récupéré de l'étape 400 correspondant au noeud destination d ; ^ un ensemble maximal Sd de noeuds sources associés à Td (un noeud source par chemin disjoint). L'étape 505 initialise la liste L avec un élément, l'ensemble Sd. Le but est de trouver tous les autres ensembles maximaux de manière optimale sans tester toutes les combinaisons possibles d'ensemble de noeuds sources. L'étape 510 construit la liste complète, selon un algorithme détaillé et expliqué dans la figure 5b. La figure 5b étant l'algorithme générique, les trois paramètres d'entrée correspondant respectivement au graphe étudié, à l'ensemble initial de chemins disjoints et à l'ensemble initial de noeuds sources associés sont notés respectivement Gdur, T et ST. Cette étape 510 est lancée avec les paramètres suivants : G, Td et Sd. L'étape 515 effectue un marquage sur le graphe. Ce marquage, expliqué clans la figure 6, consiste à sélectionner itérativement les noeuds du graphe candidats à la création d'un nouveau chemin disjoint non compris dans T, et à choisir les noeuds candidats à se retirer afin de supprimer un chemin de T. Itérativement, car chaque noeud marque un autre noeud si un arc existe entre les deux. Une information clé du marquage des noeuds de l'étape 515 est de savoir si au moins un noeud source de ST a été marqué (test de l'étape 520). Si aucun noeud source n'a été marqué, ceci signifie que pour le graphe courant G,ur, il n'y a pas d'autre ensemble de chemins disjoints que T donc pas d'autre ensemble de noeuds sources que ST. Donc fin de l'algorithme 555. Sinon il existe d'autres chemins disjoints et on passe à l'étape 525. Dans l'étape 525, le premier noeud source marqué est sélectionné (noté S,) et 25 avec l'étape 550 l'invention étudie tous les noeuds sources de ST marqués par l'algorithme de marquage (515). L'étape 530 détermine alors un autre ensemble de chemins disjoints T' à partir de T comprenant un ensemble de noeuds sources ST' différent de ST. Cet algorithme est décrit dans la figure 7. L'étape 535 ajoute ce nouvel ensemble de noeuds source ST' 30 dans la liste L. L'étape 540 correspond en fait à l'étape 510, c'est-à-dire que l'algorithme que nous décrivons, est un algorithme récursif. Par contre les trois paramètres sont maintenant les suivants : 1. Gc ir (Gcär- S,), c'est-à-dire le graphe courant étudié moins le noeud source SI et moins les liens associés à celui-ci ({(S,,y) ou (y, S,) pour tout y EV�,r} avec G�,r=(Vcur,Ecur)}) 2. T=T' 3. ST = ST' La modification des paramètres d'entrées T et ST permet de trouver d'autres 10 ensembles de noeuds sources. La modification du paramètre 1 permet de ne pas retomber sur des ensembles déjà trouvés et donc de revenir sur nos pas. L'étape 545 vérifie si tous les nceuds sources marqués par l'algorithme de marquage ont été étudiés. Si oui, fin de l'algorithme (étape 555), sinon, étape 550. Une optimisation de l'algorithme est possible au niveau de l'étape 540. En effet, 15 celle-ci peut être exécutée uniquement si le nombre de noeuds sources restant dans le graphe est strictement supérieur à la capacité Cd étudiée (le cardinal des ensembles de chemins disjoints et des noeuds sources). En effet, si celui-ci est inférieur ou égal, ceci ne sert à rien de relancer l'étape 540 car on est sur que l'algorithme de marquage ne trouvera pas d'autres ensembles de noeuds sources. 20 La détermination des ensembles de noeuds sources s'effectue sous forme d'arbre. Par exemple, supposons un réseau avec quatre noeuds sources, 1,2,3,4. Supposons que la capacité Cd est égale à 2 et que Sd soit égale à (1,2) (le premier ensemble maximal trouvé lors de l'étape 400). En appliquant l'algorithme, à partir de (1,2), on peut par exemple trouver le couple de noeuds sources (1,3) et le couple de noeuds sources (2,4). 25 Cela veut dire plus précisément que les noeuds sources 1 et 2 ont été marqués par 515. A partir du noeud 1 (resp. 2), on a trouvé par l'étape 530, l'ensemble (2,4) (resp. (1,3)). La liste L est maintenant égale à L={(1,2),(1,3),(2,4)}. On appliquera l'étape 540 mais : une première fois avec le graphe moins le noeud source 1, et l'ensemble de noeuds sources (2,4). Le résultat est alors (3,4) (ce qui signifie que le noeud 2 a 30 été marqué) ; 28 une deuxième fois avec le graphe moins le noeud source 2, et l'ensemble de noeuds sources (1,3). Le résultat est alors (3,4) (ce qui signifie que le noeud 1 a été marqué). On devrait de nouveau appliquer l'étape 540 avec un graphe qui a les noeuds sources 3 et 4. Si on utilise l'optimisation de la remarque, cette étape ne sera pas réalisée car le nombre de noeuds sources restants dans le graphe est égal à la capacité du réseau. La figure 6 décrit l'algorithme de marquage du graphe réseau, correspondant à l'étape 515 de la figure 5b. Les paramètres d'entrée sont les suivants : ^ un graphe de réseau G, avec un ensemble S de noeuds sources et d le noeud destination étudié ; ^ un ensemble maximal T de Cd chemins disjoints ; ^ ST l'ensemble des noeuds sources associé à T. Rappelons que le but du marquage est de trouver d'autres ensembles maximaux de Cd chemins disjoints impliquant d'autres ensembles de noeuds sources. L'idée principale est de remplacer un chemin disjoint de T par un autre chemin disjoint contenant un noeud source (ce nouveau chemin doit être disjoint de tous les chemins de T). Ainsi, on construit un autre ensemble T' qui diffère de T d'un chemin. D'un point de vue ensemble, on construit un ensemble de noeuds sources ST' différent de ST par un noeud source. Pour construire ce nouveau chemin, les noeuds non compris dans T et qui se portent candidats à la création d'un chemin disjoint sont marqués positivement. Pour supprimer un nouveau chemin de T, des nceuds compris dans T qui se portent candidats à se retirer afin de supprimer le chemin, sont marqués négativement. L'étape 600 sélectionne les noeuds sources non compris dans ST (l'ensemble de ces noeuds est notés Sc) et ajoute ces noeuds dans un bloc mémoire noté FIFO_cand_à_tester. De plus, tous ces nceuds sont marqués positivement car ils sont candidats par définition à faire partie d'un nouveau chemin disjoint. Le bloc mémoire FIFO_cand_à_tester permet de stocker au fur et à mesure les noeuds marqués et de trouver d'autres noeuds candidats à partir de ceux-ci. En effet l'algorithme de marquage est itératif et est similaire à un algorithme de parcours complet d'un graphe. Dit d'une autre manière, partant de Sc, itérativement l'algorithme va marquer positivement les noeuds atteignables jusqu'à trouver un noeud de T, appelé noeud d'accroche. Ce marquage positif va lui permettre de créer le nouveau chemin appelée la partie de chemin remplaçante. Puis à partir de ce noeud d'accroche, l'algorithme va marquer négativement (alternativement négativement et positivement) les noeuds atteignables de T jusqu'à trouver (au moins) un autre noeud de S compris dans ST. Ce marquage négatif va lui permettre de créer la partie du chemin dit partie de chemin à remplacer (l'étape 530 effectuera le remplacement de la partie de chemin à remplacer par la partie de chemin remplaçante). L'étape 605 initialise tous les noeuds du graphe à � non marqué �. L'étape 610 extrait un noeud u du bloc mémoire FIFO_cand_à_tester (qui est géré suivant le principe : premier élément entré, premier élément sorti). L'étape 615 sélectionne un premier noeud v du réseau (on suppose que tous les noeuds du réseau ont un identifiant). L'étape 620 vérifie si un noeud v peut être candidat pour faire partie d'un nouveau chemin disjoint, ou plus précisément d'incrémenter le chemin, c'est-à-dire lui ajouter le lien (u,v) tout en gardant la notion de disjoint. Le lien (u,v) est alors candidat pour faire partie de la partie de chemin remplaçante. Trois contraintes doivent être vérifiées : 1. v non marqué ; 2. (u,v) EE : il faut un lien entre u et v pour continuer le chemin de u vers v ; 3. (u,v) eT : Il ne faut pas que lien soit dans T sinon le chemin ne sera pas disjoint. Si v vérifie ces trois contraintes, alors v est marqué positivement et fait partie des candidats à continuer le chemin provenant de u, étape 625. Le marqueur de v, soit u, est gardé en mémoire. Attention, dans la terminologie courante (et dans la suite de l'invention), u est appelé le prédécesseur de v, noté II(v). Ceci signifie que u sera traité avant v par la suite (figure7). Ne pas confondre avec le terme appelé aussi prédécesseur utilisé dans la théorie des graphes (voir la partie associée). Ceci est nécessaire pour l'étape 530 qui permet de construire le nouveau chemin disjoint. De plus, le noeud v est mis dans le bloc mémoire FIFO_cand_a_tester pour continuer itérativement l'algorithme de marquage. Puis l'étape 650, décrit ultérieurement, est effectuée. Si au moins une des trois contraintes de l'étape 620 n'est pas respectée, alors étape 630. 30 L'étape 630 vérifie si un noeud v de T peut être candidat pour se retirer afin de supprimer un chemin de T, c'est-à dire supprimer le lien (v,u) d'un chemin disjoint de T. Le lien (v,u) est alors candidat pour faire partie de la partie de chemin à remplacer. Trois contraintes doivent être vérifiées : 1. v non marqué. 2. (v,u) EE : il faut un lien entre u et v pour continuer le chemin de u vers v 3. (v,u) ET : Il faut que le lien appartienne à T. Si v vérifie ces trois contraintes, alors étape 635 sinon étape 650. L'étape 635 vérifie si v est un noeud source. Si oui, v est stocké (étape 645). On a remonté tout l'ensemble T jusqu'au noeud source et on a trouvé notre partie de chemin à remplacer. Sinon, v est marqué négativement et fait partie des candidats à se retirer (étape 640). Le marqueur de v, soit u, est gardé en mémoire. De plus, le noeud v est mis dans le bloc mémoire FIFO_cand_à_tester pour continuer itérativement l'algorithme de marquage. Puis étape 650. L'étape 650 vérifie que tous les noeuds du réseau ont été testés. Si oui, on passe à l'étape 660, sinon le noeud suivant v est étudié (étape 655) , puis retour à l'étape 620. L'étape 660 vérifie que tous les noeuds marqués ont été testés. Si oui, fin de l'algorithme (étape 665), sinon on retourne à l'étape 610. La figure 7 décrit l'algorithme de détermination, à partir d'un ensemble de chemins disjoints T, d'un autre ensemble de chemins disjoints T', qui diffère d'un chemin, correspondant à l'étape 530 de la figure 5b. L'algorithme se fonde sur le marquage effectué par le bloc 515 et sur le noeud source de départ S, sélectionné soit à l'étape 525 soit à l'étape 550. Pour construire le nouveau chemin de T', premièrement, ce procédé sélectionne le chemin de T partant de S,. Puis, il supprime une partie de ce chemin, précédemment identifiée comme partie de chemin à remplacer, c'est-à-dire les noeuds et liens � rencontrés � marqués négativement partant de S. Puis, une fois sorti de l'ensemble T par un noeud d'accroche, l'algorithme ajoutera une partie de chemin remplaçante, c'est-à-dire les noeuds et liens � rencontrés marqués positivement partant du noeud d'accroche. � rencontrés � se base sur les prédécesseurs des noeuds stockés par l'algorithme de marquage (étape 515). 31 De plus, Sc, l'ensemble des noeuds sources non compris dans T est utilisé dans le procédé pour déterminer la fin de l'algorithme. C'est-à-dire que lorsqu'en recréant un nouveau chemin, on trouve un chemin issu d'un noeud source précédemment non utilisé, on a trouvé une nouvelle solution d'ensemble de noeuds sources de capacité maximale. Dans un premier temps, T' est initialisé à T (étape 700) et le concept de l'algorithme est de supprimer des liens de T et d'en ajouter d'autres (pour remplacer un chemin par un autre). L'étape 705 initialise le noeud t à s, et l'étape 710 initialise le noeud u au prédécesseur de S,. Puis l'étape 715 regarde si t est marqué négativement. Si oui, le lien (tu) est supprimé de T' (720). Sinon (u,t) est ajouté à T' (725). Puis étape 735. L'étape 735 vérifie si u est égal à un élément de Sc:. Si oui, fin de l'algorithme (étape 740), le nouveau chemin est construit entièrement. Si lors de l'étape 735, u n'est pas un élément de Sc ou suite à l'étape de suppression de chemin (étape 720), l'étape 730 est effectuée. Cette étape se base sur les prédécesseurs stockés pour avancer dans la construction du nouveau chemin. t est initialisé à u et u au prédécesseur de u. Puis, on retourne à l'étape 715. La figure 8 décrit un algorithme de mise à jour de la liste L des ensembles de noeuds sources pour un noeud destination, correspondant à l'étape 440 de la figure 4. Le procédé vérifie si chaque ensemble de noeuds sources de L est capable d'envoyer simultanément un paquet à un noeud destination donné noté d. Si oui, l'élément est gardé dans L sinon il est supprimé de L. Notons L(m), m=1..card(L) (card(L) : nombre d'éléments de L), un élément de la liste. L'étape 800 initialise tous les éléments à � non testé �. Ce label � testé/non testé � est introduit car l'algorithme va tester tous les éléments de L par l'étape 830 (plus d'explication à l'étape 815). Puis étape 805 qui prend le premier élément de L, noté L(m) avec m égal à 1, pour effectuer la procédure de test. Puis étape 810, qui vérifie si l'élément étudié est considéré testé ou pas. Si oui, étape 825, sinon étape 815. L'étape 815 teste si l'ensemble L(m) est capable d'envoyer simultanément un paquet à d. Le résultat de l'algorithme est noté R, un ensemble de noeuds sources. En effet, le résultat n'est pas binaire mais renvoie un ensemble de noeuds sources ce qui va nous permettre de ne pas tester tous les éléments de la liste (avantage de l'algorithme). Cette 32 étape 815 est détaillée dans la figure 9. L'étape 820 vérifie si R est égal à L(m). Si oui, L(m) est capable d'envoyer simultanément un paquet à d, donc L(m) reste dans la liste L et étape 825. Sinon L(m) n'est pas capable d'envoyer simultanément un paquet à d, et L(m) est supprimé de L, étape 835. Par contre, le résultat R peut appartenir à L. L'étape 840 vérifie donc si R appartient à L. Pour cela, on teste un par un tous les éléments de L à partir de l'indice m que l'on vient de tester et on s'arrête dès que l'ensemble a été trouvé ou dès que toute la liste a été étudiée. Si oui, R est considéré testé (845) (l'ensemble R=L(i) (i>m) est marqué � testé �) et donc on gagne une étape 815 pour cet ensemble. Puis étape 825. L'étape 825 vérifie si tous les éléments de L ont été testés. Si oui fin de l'algorithme 850. Sinon, on passe à l'étude de l'élément suivant (étape 830, puis étape 810). La figure 9 décrit l'algorithme qui leste si un ensemble de noeuds sources L(m) est capable d'envoyer simultanément un paquet à un noeud destination d, correspondant à l'étape 815 de la figure 8. L'algorithme est une version modifiée de l'algorithme de Ford-Fulkerson, une version adaptée et plus performante pour notre problème. En effet, contrairement à l'algorithme de Ford-Fulkerson, l'algorithme ne recherche pas le nombre maximum de chemins disjoints mais veut rechercher un nombre de chemins pré-déterminé C, qui contiennent chacun un noeud particulier (un noeud source de L(m)). L'algorithme initialise à vide l'ensemble T des chemins disjoints (étape 900) et l'étape 905 initialise une variable Nb_chemins à 0. L'étape 910 vérifie si le nombre de chemins à trouver C a été atteint (élément caractérisant par rapport au Ford-Fulkerson). En effet, on est sûr d'atteindre le nombre de chemins car la capacité pour ce noeud destination Cd est obligatoirement supérieure à c car l'étape 415 a trié les noeuds destinations par rapport à leur capacité (note : le bloc parent de la figure 9 est l'étape 440). De plus, l'algorithme est fait de telle manière (voir plus précisément figure 10) qu'au bout de C itérations, si L(m) de cardinal C est capable d'envoyer simultanément un paquet à d, alors le résultat est L(m). Si le nombre de chemins à trouver C a été atteint, étape 935. Sinon étape 915 qui a pour but de rechercher un nouveau chemin disjoint. L'étape 915 est décrite précisément dans la figure 10. C'est aussii un algorithme de marquage des noeuds du 33 réseau. Puis étape 920 qui construit le nouveau chemin disjoint à partir du marquage de l'étape 915 (étape 920 plus précisément décrite en figure 11). Puis l'étape 925 qui incrémente la variable nb_chemins, et on retourne à l'étape 910. L'étape 935 récupère les noeuds sources (correspondant aux noeuds initiaux des 5 chemins disjoints) compris dans T, ceux-ci sont stockés dans R, puis fin de l'algorithme (étape 940). La figure 10 décrit l'algorithme de recherche d'un nouveau chemin disjoint entre un noeud source et un noeud destination, correspondant à l'étape 915 de la figure 9. Cet algorithme est un algorithme de marquage comme utilisé dans la figure 6. Il 10 est très proche de celui utilisé par l'algorithme de Ford-Fulkerson mais est nouveau par l'étape 1000. En effet contrairement à l'algorithme de Ford-Fulkerson, le marquage initial n'est pas quelconque. L'algorithme de marquage doit d'abord essayer de construire des chemins disjoints comprenant les noeuds sources initiaux de L(m). Rappelons que l'algorithme doit obligatoirement trouver des chemins disjoints 15 comprenant L(m) si ceux-ci existent (contrairement à l'algorithme de Ford-Fulkerson qui trouve un ensemble quelconque de chemins disjoints). L'étape 1000 utilise un bloc mémoire appelé LIFO_cand_à_tester qui teste les noeuds sources de la manière suivante : dernier noeud source introduit, premier noeud source testé. Dans ce bloc sont introduits initialement les noeuds sources de S non compris dans L(m). Puis les noeuds 20 sources de L(m). On garantit ainsi que si L(m) est un ensemble de noeuds sources � compatible � pour la destination considérée, alors L(m) sera la première à satisfaire l'algorithme de marquage effectuée ici, sinon une alternative à L(m) sera trouvée. Remarque : dans cet algorithme, il est nécessaire d'utiliser pour le bloc mémoire LIFO_cand_à_tester une politique de gestion du type � dernier noeud source introduit, 25 premier noeud source sorti � contrairement à la figure 6, où pour le bloc mémoire FIFO_cand_à_tester. la gestion est libre (celle du type � premier entré premier sorti � a été choisie dans le mode préféré car c'est la plus connue de l'état de l'art). Les étapes suivantes ne sont pas nouvelles et sont celles utilisées dans l'algorithme de marquage du Ford-Fulkerson. L'étape 1005 extrait un noeud u du bloc 30 LIFO_cand_à_tester (dernier noeud introduit). L'étape 1010 sélectionne un premier noeud v du réseau (on suppose que tous les noeuds du réseau ont un identifiant). L'étape 1015 vérifie si un noeud v peut être candidat pour faire un nouveau chemin disjoint, ou plus précisément d'incrémenter le chemin, c'est-à-dire lui ajouter le lien (u,v) tout en gardant la notion de disjoint. Trois contraintes doivent être vérifiées : 1. v non marqué ; 2. (u,v) EE : il faut un lien entre u et v pour continuer le chemin de u vers v ; 3. (u,v) eT : Il ne faut pas que lien soit dans T sinon le chemin ne sera pas disjoint. Si v vérifie ces trois contraintes, alors v est marqué positivement et fait partie des candidats à continuer le chemin provenant de u, étape 1020. Le marqueur de v, soit u, est gardé en mémoire. Ceci est nécessaire pour l'étape 920 qui permet de construire le nouveau chemin disjoint. De plus, le noeud v est mis dans le bloc mémoire LIFO_cand_à_tester pour continuer itérativement l'algorithme de marquage. Puis étape 1035. Si au moins une des trois contraintes n'est pas respectée, alors étape 1025. L'étape 1025 vérifie si un noeud v de T peut être candidat pour se retirer afin de remettre en cause un chemin de T, c'est-à-dire supprimer le lien (v,u) d'un chemin disjoint de T afin d'avoir le nombre de chemin voulu (bien s^yr ce lien supprimé de T sera remplacé par un autre lien lors de l'algorithme de marquage positif). Trois contraintes doivent être vérifiées : 1. v non marqué ; 2. (v,u) EE : il faut un lien entre u et v pour continuer le chemin de u vers v ; 3. (v,u) ET : il faut que le lien appartienne à T. Si v vérifie ces trois contraintes, alors étape 1030 sinon étape 1035. L'étape 1030 marque v négativement. Le marqueur de v, soit u, est gardé en mémoire. De plus, le noeud v est mis dans le bloc mémoire LIFO_cand_à_tester pour continuer itérativement l'algorithme de marquage. Puis étape 1035. L'étape 1035 vérifie que tous les noeuds du réseau ont été testés. Si oui, étape 1045, sinon le noeud suivant v est étudié, étape 1040, puis retour à 1015. L'étape 1045 vérifie que tous les noeuds marqués ont été testés. Si oui, fin de l'algorithme (étape 1050), sinon on retourne à l'étape 1005. La figure 11 décrit l'algorithme de construction d'un nouveau chemin disjoint entre un noeud source et un noeud destination, correspondant à l'étape 920 de la figure 9. 35 Cet algorithme n'est pas caractérisant et est celui utilisé par l'algorithme de Ford-Fulkerson. De ce fait, on peut mettre en lumière la différence avec celui décrit dans la figure 7 : ^ Figure 7 : la construction d'un chemin disjoint se réalise itérativement à partir d'un noeud source jusqu'à un autre noeud source ; ^ Figure 11 : la construction d'un chemin disjoint se réalise itérativement à partir du noeud destination jusqu'à un noeud source. Cette différence s'explique par le fait que les deux algorithmes n'ont pas le même but : pour la figure 7, le but est de remplacer un chemin par un autre alors que pour la figure Il, le but est de trouver un nouveau chemin. L'étape 1100 initialise le noeud t à d et l'étape 1105 initialise le noeud u au prédécesseur de d. L'étape 1110 vérifie si 1: est égal à un élément de S. Si oui, fin de l'algorithme (étape 1135). Sinon étape 1115, qui regarde si t est marqué négativement. Si oui, le lien (t,u) est supprimé de T (étape 1120). Sinon (u,t) est ajouté à T (étape 1125). Puis étape 1130. L'étape 1130 se base sur les prédécesseurs stockés pour avancer dans la construction du nouveau chemin. t est initialisé à u et u au prédécesseur de u. Puis retour à l'étape 1110. La figure 15 représente un second exemple de réseau maillé sans fil, permettant d'illustrer les résultats de différentes étapes du procédé de construction d'un codage réseau selon un mode de réalisation particulier de l'invention. Dans cet exemple, l'ensemble S est composé des noeuds {a,b,c,d} et l'ensemble D est composé des noeuds {h,i}. Les étapes A à E ci-après résument un mode de réalisation particulier de l'invention, décrit en détail ci-dessus, en relation avec les figures 3 à l 1. Etape A : détermination du nombre maximal Ch de noeuds sources capables d'envoyer simultanément un paquet au noeud destination h et détermination d'un ensemble maximal de noeuds sources. Résultat de l'étape A : Ch = 2, Listh = {(a,b)} Etape B : à partir de cet ensemble maximal de noeuds sources de cardinal 2, détermination si d'autres ensembles maximaux existent et si oui, détermination d'autres ensembles. 36 Résultat de l'étape B : Ch = 2, List, = {(a,b),{a,c},(b,c)} Etape C : détermination de la liste complète des ensembles maximaux de noeuds sources capables d'envoyer simultanément un paquet au noeud h (itération de l'étape B). Résultat de l'étape C : C, = 2, List, = {(a,b),(a,c),(a,d),(b,c),(b,d)} Etape D : détermination si un ensemble de noeuds sources de cardinal C est capable d'envoyer un paquet à un ensemble D de noeuds destinations et détermination de la liste complète des ensembles de noeuds sources : ^ Détermination de la capacité C : C = min(C,,C;) = min(2,2) = 2 ; ^ Détermination de la liste complète des ensembles de noeuds sources capables d'envoyer simultanément un paquet au noeud destination correspondant à la capacité C : dans notre exemple, les deux noeuds destinations h et i sont possibles. On choisit h pour être en adéquation avec les étapes précédentes B et C; ^ Test si chaque ensemble de noeuds sources est capable d'envoyer simultanément 15 un paquet à chaque autre noeud destination de D, soit ici le noeud i. Résultat de l'étape D : C = 2, L = {(a,c),(b,c)}. Les éléments (a,b),(a,d) et (b,d) ont été supprimés. Etape E : détermination du nombre maximum Cr, de noeud sources capables d'envoyer simultanément un paquet à l'ensemble D et détermination de la liste complète 20 des noeuds sources. Résultat de l'étape E : Cr, = 2, L = {(a,c),(b,c)}. La liste complète est celle de l'étape précédente D vu qu'à l'étape précédente, elle n'était pas vide. REVENDICATIONS1. Procédé de construction d'un codage réseau adapté à la transmission de paquets de données, dans un réseau de communication maillé, depuis un ensemble S de M noeuds sources vers un ensemble D de N noeuds destinations, ledit procédé étant caractérisé en ce qu'il comprend les étapes suivantes : A) détermination (310 ; 425) d'une liste initiale LI comprenant tous les ensembles cohérents de noeuds sources de cardinal card_src relativement à un premier noeud destination, un ensemble cohérent de noeuds sources relativement à un noeud destination donné d étant un ensemble dont tous les noeuds sources peuvent envoyer simultanément, via des noeuds relais, un paquet, différent pour chaque noeud source, audit noeud destination donné d ; B) détermination (310 ; 430, 435, 440, 445) d'une liste modifiée L comprenant le ou les ensembles cohérents de noeuds sources, s'il(s) existe(nt) parmi ladite liste initiale L1, qui est (sont) également cohérent(s) relativement à chacun des autres noeuds destinations de l'ensemble D, distincts dudit premier noeud destination ; C) si ladite liste modifiée L n'est pas vide, sélection (315) parmi ladite liste modifiée L d'un ensemble cohérent de noeuds sources ; D) construction (320) d'un codage réseau impliquant un sous-réseau comprenant : * l'ensemble cohérent de noeuds sources sélectionné, * lesdits noeuds destinations, et * les noeuds relais via lesquels les noeuds sources dudit ensemble cohérent de noeuds sources sélectionné envoüent leurs paquets de données auxdits noeuds destinations. 2. Procédé selon la revendication 1, caractérisé en ce que card_src est égal à une borne supérieure C, et en ce que ledit procédé comprend une étape (400, 405) de détermination de ladite borne supérieure C définie par : C = Min (C;), avec i E{ LN} et C; le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet de données au noeud destination d;, avec d; ED. 3. Procédé selon la revendication 2, caractérisé en ce que ledit premier noeud destination est un noeud destination dont le nombre maximal Cd de noeuds sources capables de lui envoyer simultanément un paquet de données est égal à C. 38 4. Procédé selon l'une quelconque des revendications 1 et 2, caractérisé en ce que l'étape A) de détermination (310 ; 425) de ladite liste initiale LI comprend les étapes suivantes : i détermination du nombre maximal Cd de noeuds sources capables d'envoyer simultanément un paquet de données au premier noeud destination ; ii détermination d'un premier ensemble cohérent ST de noeuds sources de cardinal Cd et d'un premier ensemble T de Cd chemins disjoints correspondant ; iii initialisation (505) de ladite liste initiale LI avec ledit premier ensemble cohérent ST de noeuds sources de cardinal Cd ; iv- sélection dudit premier ensemble cohérent ST de noeuds sources de cardinal Cd et dudit premier ensemble T de Cd chemins disjoints correspondant ; v- à partir de l'ensemble cohérent STSe, de noeuds sources de cardinal Cd sélectionné et de l'ensemble TSe, de Cd chemins disjoints correspondant, détermination (530), s'il en existe au moins un, d'un autre ensemble cohérent ST' de noeuds sources de cardinal Cd et d'un autre ensemble T' de Cd chemins disjoints correspondant ; vi- ajout (535) à ladite liste initiale L1 dudit autre ensemble cohérent ST' de noeuds sources de cardinal Cd ; vii- sélection dudit autre ensemble cohérent ST' de noeuds sources de cardinal Cd et dudit autre ensemble T' de Cd chemins disjoints correspondant, puis réitération (540) des étapes v à vii. 5. Procédé selon la revendication 4, caractérisé en ce que ladite étape v (530) comprend les étapes suivantes : - sélection (600) des noeuds sources n' appartenant pas à TSe,, formant un ensemble Sc de noeuds sources candidats initiaux à la création d'un nouveau chemin disjoint non compris dans TSe, ; - à partir de chaque noeud source de l'ensemble Sc, et de manière itérative de noeud en noeud, marquage (605 à 660) : * avec une première valeur de marquage, de noeuds candidats à la création d'un nouveau chemin disjoint non compris dans T,e,, et * avec une deuxième valeur de marquage, de noeuds candidats à se retirer afin de supprimer un chemin disjoint compris dans TCe, ; 30 39 - en fonction du résultat dudit marquage, détermination (700 à 735) du chemin disjoint à supprimer de TSe, et du nouveau chemin disjoint à ajouter dans T,e,, pour obtenir ledit autre ensemble T' ; - détermination des noeuds sources appartenant audit autre ensemble T' et formant ledit autre ensemble cohérent ST'. 6. Procédé selon l'une quelconque des revendications 4 et 5, caractérisé en ce que l'étape v est réitérée, pour l'ensemble cohérent STSe, de noeuds sources de cardinal Cd sélectionné et l'ensemble TSe, de Cd chemins disjoints correspondant, sur un nouveau graphe de réseau G' obtenu en ôtant (540) d'un graphe de réseau courant : - le noeud source, appelé noeud source supprimé, qui appartient à l'ensemble TSe, mais pas à l'autre ensemble T' ; - les liens dont une extrémité est ledit noeud source supprimé. 7. Procédé selon l'une quelconque des revendications 1 à 6, caractérisé en ce que l'étape B) de détermination de ladite liste modifiée L comprend : - suite à une étape d'obtention (400) de coefficients C;, avec i E{1..N}, où C; est le nombre maximal de noeuds sources capables d'envoyer simultanément un paquet de données au noeud destination d;, avec d; ED ; - une étape de test de cohérence (435) itérée pour chacun des autres noeuds destinations de l'ensemble D, suivant un ordre croissant desdits coefficients C; (415, 420, 470, 445, 430). 8. Procédé selon l'une quelconque des revendications 1 à 7, caractérisé en ce que l'étape B) de détermination de ladite liste modifiée L comprend une étape d'initialisation (505) de ladite liste modifiée L avec ladite liste initiale LI et, pour chaque autre noeud destination d' de l'ensemble D, une étape de mise à jour (440) de ladite liste modifiée L comprenant les étapes suivantes : a) sélection (805) d'un ensemble S de noeuds sources de la liste modifiée L, non encore vérifié ; b) vérification (815) si ledit ensemble S est cohérent relativement audit autre noeud destination d' et détermination (815), en cas de vérification négative, d'un autre 30 ensemble S' de noeuds sources cohérent relativement audit autre noeud destination d' ;40 c) si l'ensemble S est cohérent relativement audit autre noeud destination d', l'ensemble S est gardé dans la liste modifiée L, sinon : - suppression (835) de l'ensemble S de la liste modifiée L ; et - vérification (840) si l'autre ensemble S' est compris dans la sous-liste : en 5 cas de vérification positive, l'autre ensemble S' est considéré vérifié (845) et gardé dans la liste modifiée L ; d) sélection (830) d'un nouvel ensemble S de la liste modifiée L, non encore vérifié, et retour à l'étape b). 9. Procédé selon l'une quelconque des revendications 1 à 8, caractérisé en ce que, si 10 à l'issue de l'étape B) ladite liste modifiée L est vide, le procédé comprend les étapes suivantes : a) détermination (455) de M', avec : M' = card_src ù p, où p est un pas de décrémentation ; I) détermination (465) d'une nouvelle liste initiale L1 comprenant tous les 15 ensembles cohérents de noeuds sources de cardinal M' relativement audit premier noeud destination ; y) réitération de l'étape B) avec ladite nouvelle liste initiale LI et si à l'issue de l'étape B), ladite liste modifiée L n'est pas vide, passage à l'étape C), sinon retour à l'étape a). 20 10. Produit programme d'ordinateur téléchargeable depuis un réseau de communication et/ou enregistré sur un support lisible par ordinateur et/ou exécutable par un processeur, caractérisé en ce qu'il comprend des instructions de code de programme pour la mise en oeuvre du procédé selon au moins une des revendications 1 à 9, lorsque ledit programme est exécuté sur un ordinateur. 25 11. Moyen de stockage lisible par ordinateur, stockant un programme d'ordinateur comprenant un jeu d'instructions exécutables par un ordinateur pour mettre en oeuvre le procédé selon au moins une des revendications 1 à 9. 12. Support d'enregistrement, centralisé ou distribué, contenant un fichier de données lisible par ordinateur, caractérisé en ce que ledit fichier de données contient un 30 codage réseau résultant de la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 9, ledit codage réseau étant stocké dans ledit fichier de données sous 41 la forme d'un jeu de coefficients associés aux noeuds relais compris dans ledit sous-réseau et définissant comment lesdits noeuds relais doivent combiner des paquets qu'ils reçoivent pour construire des paquets qu'ils émettent. 13. Dispositif de construction d'un codage réseau adapté à la transmission de paquets de données, dans un réseau de communication maillé, depuis un ensemble S de M noeuds sources vers un ensemble D de N noeuds destinations, ledit dispositif étant caractérisé en ce qu'il comprend : A) des moyens de détermination d'une liste initiale L1 comprenant tous les ensembles cohérents de noeuds sources de cardinal card_src relativement à un premier noeud destination, un ensemble cohérent de noeuds sources relativement à un noeud destination donné d étant un ensemble dont tous les noeuds sources peuvent envoyer simultanément, via des noeuds relais, un paquet, différent pour chaque noeud source, audit noeud destination donné d ; B) des moyens de détermination d'une liste modifiée L comprenant le ou les ensembles cohérents de noeuds sources, s'il(s) existe(nt) parmi ladite liste initiale L1, qui est (sont) également cohérent(s) relativement à chacun des autres noeuds destinations de l'ensemble D, distincts dudit premier noeud destination ; C) des moyens de sélection, si ladite liste modifiée L n'est pas vide, parmi ladite liste modifiée L d'un ensemble cohérent de noeuds sources ; D) des moyens de construction d'un codage réseau impliquant un sous-réseau comprenant : * l'ensemble cohérent de noeuds sources sélectionné, * lesdits noeuds destinations, et * les noeuds relais via lesquels les noeuds sources dudit ensemble cohérent de noeuds sources sélectionné envoient leurs paquets de données auxdits noeuds destinations.