Brevet FR2631760A1 — publié le 19891124

PROCEDE ET DISPOSITIF DE TRANSMISSION D'UN PAQUET DE DONNEES La présente invention se rapporte à un procédé et à un dispositif de transmission d'un paquet de données entre un émetteur et des récepteurs. I1 est à noter que, dans ce qui suit, le terme abonné sera souvent préféré au terme récepteur et que les termes diffusé et destinataire représenteront un abonné désigné pour recevoir un message contenu dans le paquet. Dans ce document il est fait appel aux notions de flèche et de paquet fléché, dans le domaine de la transmission de paquets Une flèche est un numéro de code placé dans un paquet et utilisé, par exemple par un commutateur, pour diriger le paquet vers une de ses sorties. Les paquets munis de flèches, aussi appelés paquets fléchés, - ont été conçus pour effectuer une liaison point à point, c'est à dire entre un émetteur et un seul récepteur ; les flèches, dont est muni le paquet au moment de son élaboration, indiquent le trajet à suivre, dans le réseau, entre l'émetteur et le récepteur. La technique des paquets fléchés permet une commutation très rapide et se prête donc à tous les types d'applications: téléphonie, transmission de données en temps réel, etc... Dans sa conception initiale, le paquet fléché n'a pas été employé pour la diffusion à des destinataires multiples puisque, comme il a été vu plus avant, il est prévu seulement pour une liaison point à point. Il y a cependant la possibilité de diffusion vers des destinataires multiples d'une même information, à travers un serveur de diffusion placé dans le noeud origine qui se charge d'envoyer autant de paquets qu'il y. a de noeuds sur lesquels sont branchés des destinataire de cette même information. le but de la présente invention est de proposer un procédé de commutation rapide d'un paquet de données entre un émetteur et une multitude de diffusés, en évitant d'avoir à dupllquer l'information et, par coriséquent, de provoquer des pointes de trafic sur les artères comme dans le cas où la même informstion destinée à plusieurs diffusés est acheminée dans autant de paquets que de diffusés. Et ce procédé sera décrit à l'aide d'un réseau présentant une technologie qui ne diffère de l'art connu que pour l'élaboration et le traitement de paquets. Ceci est obtenu en utilisant des paquets fléchés de conception nouvelle. La présente invention concerne un procédé de transmission d'un paquet de données dans un réseau de communication comportant des noeuds de commutation réunis par des artères, utilisant des paquets fléchés où l'information à transmettre est précédée d'au moins une flèche destinée à indiquer un trajet à parcourir par le paquet dans le réseau, caractérisé en ce qu'il consiste à élaborer des paquets de diffusion comportant une seule flèche avec, dans cette flèche, un identificateur de diffusion c'est à dire un champ permettant une identification de l'émetteur du paquet et des diffusés auxquels il est destiné, et un numéro de séquence c'est à dire un champ permettant de distinguer les uns des autres les paquets munis d'un même identificateur, à lire, dans chaque noeud atteint par le paquet, en fonction de l'identificateur de diffusion, une liste préétablie des artères par lesquelles le paquet doit être rediffusé et un numéro d'ordre, et à n'autoriser la rediffusion du paquet par les artères de la existe, que si le numéro de séquence est égal au numéro d'ordre et, dans ce cas, à incrémenter le numéro d'ordre. La présente invention sera mieux comprise et d'autres caractéristiques apparaîtront à l'aide de la description ci-après et des figures s'y rapportant qu-i représentent - la figure 1, le schéma simplifié d'un réseau de communication - la figure 2, un exemple de composition d'un paquet fléché selon l'art connu - les figures 3a et 3b, des schémas de paquets conçus pour la mise en oeuvre du procédé selon l'invention - la figure 4, un schéma plus détaillé d'un élément de la figure 1 dans le cas d'utilisation de paquets selon les figures 3a et 3b - la figure 5, une table programmable utilisée dans un élément de la figure 4. Sur les différentes figures les éléments correspondants sont désignés par les même repères. Dans les différents schémas les dispositifs détaillés utilisés pour élaborer les paquets et effectuer leur traitement et relevant de la technologie courante, ntont pas été représentés en vue de rendre les dessins plus clairs et de simplifier ltexposé. Par contre cette élaboration et ces traitements à effectuer sont précisés dans l'exposé. La figure 1, est une vue partielle d'un réseau comprenant des noeuds de commutation dont sept , N1 à N7, apparaissent sur la figure ; ces noeuds sont interconnectés, selon une structure maillée, par des artères où les communications sont multiplexées ; le type de multiplexage employé n'intervenant pas dans la compréhension de l'invention ne sera pas précisé. Chaque noeud de commutation comporte un commutateur qui, lui-même, comporte dans les exemples qui vont être décrits, huit points de raccordement pour les artères.Ces points de raccordement, identifiés par des numéros allant de O à 7, comportent chacun une entrée et une sortie ; l'artère relative au point O est utilisée pour le trafic se terminant localement dans le noeud, tel que le trafic des abonnés raccordés au noeud ou que le trafic d'échange de signalisation entre l'organe de commande du noeud et les organes de commande des noeuds voisins. L'exemple décrit considère un émetteur ou diffuseur de paquets, Tell, qui est raccordé au noeud N1; et qui désire envoyer des données constituées par une même information, vers des diffusés raccordés aux trois noeuds N3, N4 et N7, afin d'établir une conférence avec quatre diffusés : un diffusé RI associé au noeud N3, deux diffusés R21, R22 associés au noeud N4 et un diffusé R3 associé au noeud N7.Au moment où débute la conférence les diffusés destinataires des paquets provenant du diffuseur Ell sont connus des noeuds sur lesquels ils sont raccordés, grâce à une table préprogrammée ou grâce à l'envoi, par le diffuseur Ell, d'instructions préalables désignant les diffusés ; comme il ressortira de ce qui sera vu plus loin cette désignation des diffusés peut se faire soit, selon l'art connu, à l'aide de paquets fléchés ordinaires soit selon l'invention. Pour envoyer son information le diffuseur Ell pourrait établir trois communications indépendantes et simultanées puisqu'il a été considéré qu'il y avait en tout trois noeuds sur lesquels étaient branchés des destinataires ; ce procédé, selon l'art connu, présente le risque de provoquer des pointes de trafic sur les artères. Pour envoyer son message le diffuseur Ell peut comme cela va être décrit ci-après, utiliser une fonction distribuée de diffusion, dans laquelle les données sont acheminées systématiquement dans tout le réseau par une technique dite dinondation ; chaque noeud se charge de participer à l'inondation, comme il sera vu plus tard, de prendre en compte ou non l'information et de la diffuser vers ceux de ses abonnés qui sont destinataires. La figure 2 montre quel format il est connu de donner a à un paquet d'informations pour une liaison point à point. Les paquets successifs sont séparés par des fanions constitués par le code "Ol111110", ce code ne peut jamais être rencontré en dehors des fanions gracie à l'insertion après tout groupe de cinq "1" consécutif d'un "O" dit de transparence, selon la procédure définie par la norme ISO 3309. Ces "O" de transparence sont éliminés, par la suite des données transmises entre fanions. Le paquet débute par un champ d'adressage constitué par une suite de flèches qui servent à guider le paquet de proche en proche. Lorsque le paquet entre dans un noeud de commutation, la flèche qui est en tête indique le numéro de l'artère par laquelle il doit sortie du noeud. Cette flèche est "effeuillée" par le commutateur. Lorsque la flèche de tête est à "O" cela signifie que le paquet est arrivé au noeud du destinataire, le champ suivant donne alors son adresse locale. Dans un système multi- service, dans lequel le traitement final subi par les données dépend de l'application, un dernier champ de commande donne la référence du protocole applicable . Après ces champs d'entête le paquet contient les données utilisateur complétées éventuellement de données auxiliaires exigées par le protocole (numéro d'ordre, séquence de contrôle de trame, etc...). Cette technique a l'avantage de permettre de confier l'aiguillage des paquets à un automate matériel, donc très rapide, ce qui permet d'atteindre un flux très important et un temps de transit très court, compatIble notamment avec l'application téléphonique. Cette technique est bien adaptée à la réalisation de liaisons point à point. Ce qui suit va montrer comment il est possible de l'adapter à la technique dite d'inondation. La figure 3a représente un paquet de diffusion au moment de sa création par l'émetteur Tell ; dans ce paquet les champs d'adresse locale, de commande et de données utilisateur sont identiques à ceux de la figure 2 et seront appelés "informations" dans ce qui suit et il en sera de même avec la figure 3b. Le paquet est encadré par des fanions et comporte une flèche de diffusion XYZT et les informations La flèche de diffusion est composée de quatre champs X, Y, Z et T. X est l'élément binaire 1, il indique la diffusion et permet de différencier les paquets de diffusion des paquets de - communication point à point.Y est un identificateur de diffusion, il va permettre d'ldentifler sans ambiguïté, dans le réseau, une diffusion donnée, c'est à dire un émetteur Eli - et ses diffusés R1, R21, R22, R3 ; il comporte n-1=7 éléments binaires, dans l'exemple décrit. Z est un numéro de séquence cyclique, c'est å dire un numéro qui identifie un paquet donné dans une diffusion, une diffusion d'information étant une suite de paquets diffusés ; il comporte m=8 éléments binaires dans l'exemple décrit.T est un code de redondance relatif à YZ, pour protéger contre les erreurs de transmission ; il comporte p=5 éléments binaires dans l'exemple décrit et il est .à noter que ce code pourrait être déterminé relativement à XYZ mais que, X étant toujours égal à 1 dans un paquet de diffusion, il suffit de la déterminer relativement à YZ. La figure 3b, représente un paquet de communication point à point au moment de sa création par l'émetteur Tell ; ce paquet correspond au paquet de la figure 2 dans lequel un zéro est placé devant chaque flèche ordinaire permettant ainsi de distinguer l'un de l'autre les paquets selon la figure 3a et ceux selon la figure 3b qui sont, l'un et l'autre, utilisés dans le réseau selon la figure 1. La figure 4, est un schéma d'un noeud devant recevoir et émettre un paquet de diffusion. Le noeud représenté est le noeud N2 de la figure 2. Ce noeud comporte, comme les autres noeuds du réseau, huit unités de jonction, Ujo à Uj7, relatives aux huit artères raccordées au noeud, un bus B et un serveur de diffusion Sd ; dans les unités de fonction les joncteurs d'entrée et de sortie ont été représentés.Un paquet arrive sur un joncteur d'entrée (trajet repéré par un 1 dans un cercle), est reconnu comme un paquet de diffusion grâce à X=l ; ce paquet est alors envoyé vers le serveur de diffusion (trajet repéré par un 2 dans un cercle) et ce serveur renvoie le paquet vers les joncteurs de sortie (trajets repérés par des 3 dans des cercles) et la transmission se fait, sur des artères parmi les artères 0,1..., i, ...7, en fonction de Y comme il sera vu plus tard, si et seulement si ZT est valide, comme il sera également vu plus tard ; ceci est réalisé en éliminant la flèche de diffusion XYZT pour le paquet renvoyé sur l'artère locale, O, et en conservant la même flèche XYZT pour les autres artères. Dans chaque noeud de commutation la réexpédition des paquets sur les artères est déterminée par une technique présentée å la figure 5. Dans chaque serveur de diffusion une table programmable ,Tp, donne en fonction de la valeur de l'identificateur de diffusion, Y, une liste de réexpédition, L, formée de huit éléments binaires a7 à aO qui, selon qu'ils sont nuls ou égaux à 1, déterminent si le paquet doit être réexpédié ou non sur chacune des huit artères correspondantes. Le numéro de séquence1 Z, a pour but la ségrégation des paquets reçus en diffusion afin de ne traiter un paquet que s'il est reçu pour la première fois ; pour chaque diffusion Y les paquets émis par le noeud qui a l'émetteur Ell sont accompagnés d'un numéro de séquence inscrit dans Z et incrémenté à chaque nouveau paquet émis (numérotation modulo m 2m avec m nombre de bits de Z, égal à 8 dans l'exemple décrit). La figure 5 montre que, dans la table Tp, existe également, pour chaque entrée Y, un numéro d'ordre, V, formé de m=8 éléments binaires, b8 à bl, qui indiquent le numéro de séquence du prochain paquet à recevoir. Si le numéro de séquence, Z, du paquet reçu est égal au numéro d'ordre V (bm. . . bl), la recopie est validée et la valeur de V est incrémentée, sinon le paquet est arrêté. La figure 5 montre que dans la table existe aussi, pour chaque entrée Y, p=5 éléments binaires c5 à cl, qui indiquent le code de redondance R qui doit accompagner le YZ du paquet reçu ; si cette valeur R et le champ T -du paquet reçu sont identiques, la transmission du paquet est validée, sinon le paquet est arrêté. 1l est à noter que cette valeur peut, dans des variantes à exemple décrit, ne pas figurer dans la table programmable mais être calculée dans le serveur en fonction du YZ reçu. En reprenant l'exemple de la figure 1 une diffusion Y peut donc entre définie de la manière suivante - N1 diffuse sur les artères 1 et 2 vers les noeuds N2, N3 - N2 diffuse sur les artères 2 et 7 vers les noeuds N3, N4 - N3 diffuse sur les artères 2, 3 et O vers les noeuds N2 et N5, ainsi que vers le diffusé local R1 - N4 diffuse sur les artère 1, 4, 5, 6 et 0, vers les noeuds N2, N7, N6 et N5 ainsi que vers les diffusés locaux R21, R22 - N5 diffuse sur les artères 2, 3, 4 vers les noeuds N4, N3 et N6 - N6 diffuse sur les artères 4 et 5 vers les noeuds N5 et N4 et - N7 ne diffuse que sur l'artère 0, vers le diffusé local R3. 1l est à noter qu'il est également possible de limiter l'inondation, pour cette même diffusion, en choisissant, par exemple, la liste de diffusion suivante - N1 diffuse sur les artères l et 2, vers N2, N3 - N2 ne diffuse que sur l'artère 7 vers N4 - N3 ne diffuse que sur l'artère 0, c'est à dire localement vers R1 - N4 diffuse sur les artères 4 et 0, vers N7 et localement vers R21, R22 - N5 et N6 ne diffusent pas - N7 ne diffuse que sur l'artère 0, c'est à dire localement vers R3. L'invention concerne en particulier, mais pas uniquement, le domaine de la conférence téléphonique où se pose le problème de l'envoi de messages longs et à durée indéterminée. La présente invention n'est pas limitée à l'exemple décrite et aux variantes qui ont été envisagées dans ee qui précède, c'est ainsi en particulier que le champ T relatif au code de redondance peut être supprimé ou réduit à un seul élément binaire relatif à un code de parité. 1l est même possible de supprimer le champ X à condition de n'envoyer dans le réseau que les paquets de diffusion et donc aucun paquet de transmission point à point du type de celui représenté à la figure 3b. REVENDICATIONS 1. Procédé de transmission d'un paquet de données dans un réseau de communication comportant des noeuds de commutation (N1-N7) réunis par des artères, utilisant des paquets fléchés où l'information à transmettre est précédée d'au moins une flèche destinée à indiquer un trajet à parcourir par le paquet dans le réseau, caractérisé en ce qu'il consiste à élaborer des paquets de diffusion comportant une seule flèche avec, dans cette flèche, un identificateur de diffusion (Y) c'est à dire un champ permettant une identification de l'émetteur (El i) du paquet et des diffusés (R1, R2ly R22, R3) auxquels il est destiné, et un numéro de séquence c'est à dire un champ (Z) permettant de distinguer les uns des autres les paquets munis d'un même identificateur, à lire, dans chaque noeud atteint par le paquet, en fonction de l'identificateur de diffusion, une liste préétablie des artères par lesquelles le paquet doit être rediffusé et un numéro d'ordre, et à n'autoriser la rediffusion du paquet par les artères de la liste, que si le numéro de séquence est égal au numéro d'ordre et, dans ce cas, à incrémenter le numéro d'ordre. 2. Procédé selon la revendieation 1, caractérisé en ce qu'il consiste à élaborer également des paquets ordinaires, pour des communications point à point, munis de flèches successives et à associer un repère (X) aux flèches, ce repère ayant une valeur donnée (1) pour une flèche d'un paquet de diffusion et une valeur différente (O) pour une flèche d'un paquet ordinaire. 3. Procédé selon la revendication 1, caractérisé en ce que la flèche des paquets de diffusion comporte un champ (T) dans lequel est inscrit un code de redondance relatif au moins à une partie (YZ) du contenu de la flèche. 4. Dispositif de transmission d'un paquet de données dans un réseau de communication comportant des noeuds de commutation (N1-N7) réunis par des artères, utilisant des paquets fléchés où l'information à transmettre est précédée d'au moins une flèche destinée å indiquer un trajet à parcourir par le paquet dans le réseau, chaque noeud comportant un serveur (Sd), caractérisé en ce que le serveur comporte une table programmable (Tp) dans laquelle, au moins pour certains paquets reçus, dits paquets de diffusion, qui comportent une flèche munie d'un identificateur de diffusion (Y) et un numéro de séquence (Z) du paquet, est inscrite une liste -de réexpédition (L) qui, en fonction de l'identificateur de diffusion d'un paquet de diffusion- reçu, donne les artères du noeud par lesquelles le paquet reçu doit être réexpédié, en ce que, pour une diffusion locale le paquet est réexpédié par le serveur sans sa flèche et est réexpédié avec sa flèche pour une diffusion vers un autre noeud, en ce que la table (Tp) donne également, en fonction de l'identificateur (Y) un numéro de paquet attendu et en ce que le serveur (Sd) autorise la réexpédition et incrémente le numéro de paquet attendu si le numéro de séquence et le numéro de paquet attendu sont égaux.