Brevet FR2534764A1 — publié le 19840420

PROCEDE ET DISPOSITIF DE DEMANDE D'ALLOCATION DE RESSOURCE DANS UN COMMUTATEUR A STRUCTURE REPARTIE La présente invention concerne un procédé et un dispositif de demande d'allocation de ressource dans un commutateur à structure répartie. Un commutateur à structure répartie se présente sous la forme d'un graphe, c'est-à-dire d'un ensemble de noeuds reliés entre eux par des mailles, chaque noeud n'étant relié qu'à un nombre "n" d'autres noeuds (ses adjacents). Dans ce type de commutateur, un noeud est au moins constitué d'une unité de communication qui a pour fonction de commuter des données utiles (parole, paquets conformes à l'avis X25 du CCITT.. et d'acheminer des messages de service. Une unité de communication se compose ellemême d'un circuit de commutation qui fonctionne sous la-commande d'une logique de communication. Sur l'unité de communication viennent se greffer des ensembles satellites, ou unités fonctionnelles. Ce sont l'unité d'adaptation (ou interface avec - le monde extérieur) et l'unité de traitement (contenant le logiciel nécessaire au traitement des communications, à la maintenance et à l'exploitation du commutateur). L'invention s'applique particulièrement à un commutateur à structure répartie dans lequel les unités fonctionnelles des différents noeuds ont des ressources (matérielles ou logicielles) différentes, et dans lequel chaque unité fonctionnelle connaît entièrement ses propres ressources mais ignore complètement les ressources des autres unités fonctionnelles Suivant l'invention, lorsqu'une unité fonctionnelle recherche une ressource, elle interroge toutes les unités fonctionnelles du commutateur en leur envoyant un message de demande d'allocation de ressource.L'intérêt de cette solution est de minimiser les données de chaque unité fonctionnelle, de simplifier les mises à jour et de rendre les unités fonctionnelles indépendantes de la topologie du graphe, et donc indépendantes des pannes et des extensions du commutateur L'invention peut également s'appliquer à un commutateur à struc ture répartie dans lequel les unités fonctionnelles des différents noeuds ont des ressources identiques, ces ressources étant partagées entre les différents noeuds du commutateur. Suivant l'invention, lorsqu'une unité fonctionnelle recherche une ressource disponible à un instant donné, elle interroge toutes les unités fonctionnelles du commutateur en leur envoyant un message de demande d'allocation de ressource. Cette solution étant choisie, il est alors nécessaire de pouvoir acheminer une demande émise (sous forme de message de demande d'allocation de ressource) par une unité fonctionnelle donnée, vers toutes les autres unités fonctionnelles. Cet acheminement de message d'une unité fonctionnelle donnée vers toutes les autres unités fonctionnelles est aussi appelé par la suite acheminement en mode diffusion. On connaît deux modes d'acheminement de messages dans un commutateur à structure répartie: le mode déterministe et le mode adaptatif. Le mode déterministe consiste à indiquer dans l'en-tête du message la suite des noeuds à traverser pour atteindre le destinataire, la commutation de messages suivant ce mode s'apparentant ainsi à la commutation de circuits. Ce mode est utilisé pour commuter des données utiles entre deux unités d'adaptation déterminées mais est inopérant pour le mode diffusion car il nécessiterait la connaissance par chacun des noeuds de la topologie complète du graphe. Or ceci est exclu pour des raisons déjà citées. Le mode adaptatif repose sur la notion d'arbre des chemins. II s'agit d'une construction logique dans laquelle chaque noeud du graphe sait auquel de ses adjacents il doit envoyer un message pour qu'il atteigne n'importe quel noeud du graphe connaissant l'identité de ce noeud. On voit que par itération le message peut ainsi atteindre son destinataire. Le mode adaptatif permet donc d'envoyer un message à n'importe quel noeud du graphe sans avoir à rechercher un chemin. Ce mode d'acheminement pourrait être utilisé pour envoyer une demande à tous les noeuds du commutateur (envoi de n messages successivement par le demandeur), mais il consomme une trop grande puissance de traitement.De plus, dans un commutateur dans lequel le principe de commutation est du type "paquet-file d'attente", c'est-à-dire dans lequel, indépendemment des pannes, un paquet a une probabilité non nulle d'être perdu à chaque fois qu'il traverse une file d'attente, ce mode n'offre aucune sécurité vis-a-vis de la perte des messages. La présente invention a également pour objet un procédé et un dispositif d'acheminement - de messages de demande d'allocation de ressource qui présente une parfaite sécurité et un moindre coût. Selon l'invention, le procédé d'acheminement de messages de demande d'allocation de ressource, d'un noeud, appele noeud demandeur, vers tous les autres noeuds du commutateur, est tel que le noeud demandeur envoie un message de demande d'allocation de ressource à tous ses adjacents et que tout noeud qui reçoit ce message l'envoie à son tour à tous ses adjacents. Cette caractéristique permet d'obtenir une très grande sécurité dans l'acheminement des messages en mode diffusion. En effet si "p" est la probabilité de perte d'un message lorsqu'il passe d'un noeud à l'un de ses - adjacents (toutes causes confondues) la probabilité pour qu'un méssage acheminé en mode diffusion conformément à 15invention n'atteigne pas un noeud donné est ph ("n" étant le nombre de noeuds adjacents du noeud considéré). I1 est donc possible de perdre un très grand nombre de messages à des endroits différents du commutateur sans que la propagation des messages en mode diffusion en soit affectée. Si cette caractéristique permet bien de minimiser l'influence des pannes sur l'acheminement des messages en mode diffusion, elle risque toutefois de conduire très rapidement à une multiplication incontrôlée du nombre de messages se propageant à l'intérieur du commutateur pour une mêe diffusion. C'est pourquoi, suivant une autre caractéristique de l'invention, tout - noeud qui reçoit un même message de demande d'allocation de ressource provenant de plusieurs de ses adjacents ne réémet ce message qu'une seule fois à destination de tous ses adjacents. Cette caractéristique permet, en combinaison avec la précédente, d'accroître la sécurité de transmission tout en minimisant le coût. Les objets et caractéristiques de l'invention apparaîtront plus clairement à la lecture de la description suivante d'un exemple de réalisation, ladite description étant faite en relation avec les dessins ci-annexés dans lesquels: - la figure la représente un commutateur à structure répartie dans lequel est mis en oeuvre le procédé de demande d'allocation de ressource suivant l'invention. - la figure -lb représente la même chose que la figure la, le commutateur étant affecté de pannes. - la figure 2 représente le contenu des messages de demande d'allocation de ressource acheminés suivant l'invention. - la figure 3 représente un dispositif de demande d'allocation de ressource conforme à l'invention. Sur la figure la on a représenté un exemple de commutateur dans lequel est mis en oeuvre le procédé conforme à l'invention. Ce commutateur comporte un certain nombre de noeuds (seize à titre d'exemple) représentés par des ronds, reliés entre eux par des mailles représentées par des traits. Le commutateur est rebouclé sur lui-même, de sorte que les noeuds extrêrnes sont également reliés entre eux. A titre d'exemple chaque noeud est relié à quatre autres noeuds (ses adjacents) par quatre mailles. Sur cette figure on a représenté un noeud E demandeur de ressource. Ce noeud E émet donc un message de demande d'allocation de ressource vers tous les autres noeuds du commutateur. On a montré plus particulièrement l'ensemble des chemins empruntés par ce message pour atteindre un noeud destinataire D. Suivant l'invention, le noeud demandeur E envoie ce message à tous ses adjacents, ce message empruntant alors les mailles 1, dans le sens indiqué par les flèches. Chaque noeud relié au noeud demandeur E par une maille 1 envoie ensuite ce message à tous ses adjacentes, ce message empruntant alors les mailles 2. Ce message emprunte également les mailles 1 dans le sens inverse des flèches pour retourner vers le noeud demandeur E mais, pour des raisons de simplification, on a représenté seulement sur ce dessin le sens de propagation du noeud demandeur E vers le noeud destinataire D. Chaque noeud relié à un autre noeud par une maille 2 envoie ensuite ce message à tous ses adjacents, ce message empruntant alors les mailles 3. Chaque noeud relié à un autre noeud par une maille 3 envoie ensuite ce message à tous ses adjacents, ce message empruntant alors les mailles 4, certaines des mailles 4 étant directement reliées au noeud destinataire D. L'intérêt de ce procédé d'acheminement apparaît sur la figure lb représentant le même commutateur que celui de la figure la mais dans lequel deux noeuds (repérés par des croix) sont isolés du reste du commutateur en raison de pannes. On voit sur cette figure que le message en mode diffusion émis par le noeud E est bien reçu par le noeud D malgré l'existence de ces pannes. il n'en serait par de même avec les modes d'acheminement connus, dans le cas où le chemin unique pour aller du noeud E au noeud D, déterminé suivant l'un de ces modes, emprunterait l'un des noeuds en panne. Le procédé d'acheminement conforme à l'invention offre donc-une sécurité nettement supérieure aux procédés classiques. Il apparaît également sur les figures la et lb que le procédé d'acheminement suivant l'invention tend à accroître le trafic relatif à la diffusion à l'intérieur du commutateur.- Pour éviter cet inconvénient, il est prévu qu'un noeud tel que le noeud Ng qui reçoit un même message de demande d'allocation de ressource venant de ses différents adjacents Ng, N2, N3 et N4, ne reémette ce message qu'une seule fois vers tous ses adjacents. Pour obtenir ce résultat, les messages de demande d'allocation de ressource ont une structure du type représenté sur la figure 5 c'est-à-dire comportant les informations suivantes: - une information TYP indiquant qu'il s'agit d'un message de demande d'allocation de ressource, - une information NOPE identifiant le noeud demandeur, - une information NDC indiquant le numéro attribué à cette demande par le noeud demandeur. Ce numéro prend une nouvelle valeur à chaque nouvelle demande émanant d'un même noeud demandeur et est ainsi assimilable à l'instant d'émission d'une demande par ce noeud Il est par exemple augmenté d'une unité à chaque nouvelle demande, - une information INFO contituant la demande d'allocation de ressource proprement dite. Le rôle des informations NDC et NOPE dans l'obtention du résultat cité précédemment apparaîtra au cours de la description du dispositif de demande d'allocation de ressource représenté sur la figure 3. Ce dispositif équipe chacun des noeuds du commutateur. Il comporte une mémoire 10 du type FIFO (premier entré, premier sorti) destinée à stocker les messages acheminés suivant le mode diffusion et reconnus grâce à l'information TYP. Cette mémoire FIFO 10 permet de rendre parfaitement asynchrones la réception des messages et leur traitement. Ce traitement des messages est effectué au moyen d'une mémoire 1I à accès aléatoire placée en sortie de la mémoire FIFO de réception 10, d'une mémoire 12 à accès aléatoire adressée et écrite respectivement avec les informations NOPE et NDC du message en cours de traitement, et d'un comparateur 13 destiné à comparer l'information NDC du message en cours de traitement avec une-information NDDT fournie par la mémoire 12 adressée au même instant par l'information NOPE du message en cours de traitement. Le dispositif de demande d'allocation de ressource comporte encore un circuit 14 de génération d'en-tête de messages de demande d'allocation de ressource et une mémoire FIFO d'émission 15. Suivant le résultat de la comparaison effectuée par le comparateur 13, la mémoire 12 est ou non mise à jour et le message en cours de traitement est ou non transmis à la mémoire FIFO d'émission 15, après lui avoir juxtaposé l'en-te te fournie par le circuit 14. Ce dispositif fonctionne de la façon suivante. L'information NDDT représente le numéro attribué par le noeud dem an- deur (identifié par l'information NOPE) à la demande précédant celle traitée actuellement et identifiée par l'information NDC. Si NDC est égal à NDDT + 1, il s'agit d'une nouvelle demande. Le comparateur 13 commande alors d'une part la mise à jour de l'information NDDT (c'est-à-dire son remplacement par l'information NDC) dans la mémoire 12, d'autre part le transfert du message à la mémoire FIFO d'émission 15, après juxtaposition à ce message d'un en-tête fourni par le circuit 14 également activé par le comparateur 13, cet en-tête assurant l'aiguillage, par le circuit de commutation du noeud considéré, de ce message vers tous les noeuds adjacents du noeud considéré ainsi que vers les unités fonctionnelles de ce noeud. Si NDC est égal à NDDT, il assagit d'un message déjà reçu et le comparateur 13 ne commande pas son transfért à la mémoire FIFO d'émission 15. Si d'autres cas se produisent, le message n'est pas transféré à la mémoire FIFO d'émission 15 et le comparateur 13 incrémente un compteur de fautes 16. L'information NDC est codée sur "I" éléments binaires. On voit donc que lorsqu'un noeud n'est plus en séquence avec les autres noeuds du commutateur (par exemple à la suite d'un redémarrage) il y a au plus 2 - 1 messages de perdus mais l'ensemble repasse dans son état normal de fonctionnement sans nécessiter aucun dispositif d'initialisation. La présente invention offre de plus la possibilité de réguler le trafic. Dans le commutateur auquel s'applique l'invention, il n'existe actuellement aucun dispositif centralisé de supervision susceptible d'activer une régulation du trafic lorsque le trafic nominal est dépassé. Par contre, chaque demande d'allocation de ressource quel qu'en soit le noeud origirie, nécessitant un traitement dans tous les noeuds du commutateur, chaque noeud est à même d'estimer la charge globale du commutateur et d'activer localement un mécanisme de contrôle de congestion. Pour cela, on procéde de la manière suivante: - on compte par période de temps le nombre de diffusion traitées, - on détecte les surcharges prolongées, - en cas de surcharge, on refoule les nouvelles demandes. La présente invention offre également la possiblité de détecter les pannes des mailles adjacentes d'un noeud considéré. Pour cela on procède de la manière suivante: - lorsqu'on détecte le premier message d'une nouvelle diffusion on active un processus qui mémorise le fait que l'on recoive le message par chaque noeud adjacent; - lorsqu'on reçoit le dernier message d'une diffusion on libère le pro cessùs; - on observe parallelement le nombre de processus engagés et lorsque leur nombre dépasse un certain seuil, on déclenche une analyse des processus bloqués qui permet de déterminer statistiquement la maille en faute. A titre d'exemple, le procédé et le dispositif d'acheminement de messages en mode diffusion suivant l'invention ont été décrits plus particulièrement dans le cadre de leur application à un commutateur à structure répartie. Il est néanmoins possible, sans rien changer au principe de l'invention, de les appliquer à un système de traitement de données quelconque à structure répartie. REVENDICATIONS 1. Procédé de demande d'allocation de ressource dans un commutateur à structure répartie constitué de noeuds reliés entre eux par des mailles, caractérisé en ce que tout noeud demandeur de ressource envoie un message de demande d'allocation de ressource à tous les noeuds du commutateur. 2. Procédé selon la revendication 1, dans lequel chaque noeud du commutateur est relié à n autres noeuds, appelés adjacents du noeud considéré, par n mailles, caractérisé en ce que tout noeud demandeur de ressource envoie un message de demande-d'allocation de ressource à tous ses adjacents et en ce que tout noeud qui reçoit ce message l'envoie à son tour à tous ses adjacents, tout noeud qui reçoit un même message de demande d'allocation de ressources provenant de plusieurs de ses adja- cents ne reémettant ce message qu'une seule fois à destination de tous ses adjacents. 3. Procédé selon l'une des revendication 1 et 2, caractérisé en ce que tout message de demande. d'allocation de ressource émis par un noeud demandeur de diffusion à un instant d'émission donné, contient des informations permettant d'identifier ce noeud (NOPE) et cet instant d'émission (NDC). 4. Dispositif de mise en oeuvre du procédé selon les revendications 1, 2 et 3, caractérisé en ce qu'il équipe chacun des noeuds du commutateur et en ce qu'il comporte des moyens de réception des messages de demande d'allocation de ressource venant de noeuds adjacents au noeud considéré, des moyens de traitement des messages reçus aptes à distinguer les messages relatifs à de nouvelles demandes d'allocation de ressource de ceux relatifs à des demandes d'allocation de ressource déjà traitées, et des moyens d!émission vers tous les noeuds adjacents au noeud considéré des messages reçus relatifs à de nouvelles demandes d'allocation de ressource. 5. Dispositif selon la revendication 4, caractérisé en ce que les moyens de réception comportent une mémoire FIFO de réception (10). 6. Dispositif selon l'une des revendications 4 et 5, caractérisé en ce que les moyens de traitement comportent une première mémoire à accès aléatoire (11) placée en sortie des moyens de réception, une seconde mémoire à accès aléatoire (12) adressée et écrite respectivement par les informations du message de demande d'allocation de ressource permettant d'identifier respectivement le noeud demandeur (NOPE) et l'instant d'émission du message (NDC), un comparateur (13) apte à comparer l'information permettant d'identifier l'instant d'émission (NDC) du message reçu et l'information lue dans la seconde mémoire à accès aléatoire (12) et à commander la mise à jour de la seconde mémoire à accès aléatoire et le transfert du message traité vers les moyens d'émission, suivant le résultat de la comparaison. 7. Dispositif selon l'une des revendications 4, 5 et 6, caractérisé en ce que les moyens d'émission comportent une mémoire FIFO d'émission (15) dans laquelle sont stockés les messages fournis par les moyens de traitement, chacun de ces messages étant associé à un en-tête fourni par un circuit de génération (14) et indiquant que ce message doit être transmis à tous les noeuds adjacents du noeud considéré.