Brevet FR2527401A1 — publié le 19831125

PROCEDE ET DISPOSITIF D'ALLOCATION DETERMINISTE EXPLICITE DU JETON DANS UN RESEAU LOCAL DISTRIBUE DE TRANSMISSION AVEC PRIORITES. La présente invention concerne un procédé de transmission de l'al- location, à différentes stations qui peuvent émettre ou recevoir des messages, d'un droit à émettre, appelé jeton, le dit jeton ne pouvant être alloué qu'à une seule station à la fois parmi toutes les stations faisant partie d'un réseau local de communications; dans ce type de réseaux, d'une part, quand une station détient le jeton, elle peut elle a même le devoir d'émettre un ou plusieurs messages et/ou de transmet- tre le jeton à une autre station, d'autre part, quand une station n'a pas le jeton, elle "écoute" les messages transitant sur le réseau et, parmi tous ces messages, elle "guette" plus spécialement les messages qui gèrent la transmission du jeton. La transmission du jeton peut s'effectuer selon un premier mode dit aléatoire comme dans le procédé connu sous le nom de CSMACD (Carrier Sense Multiple Access with Collision Detection); procédé suivant lequel chaque station peut revendiquer le jeton à tout instant. La transmission du jeton peut aussi s'effectuer selon un deuxième mode dit déterministe, soit de manière implicite comme dans le procédé décrit dans la demande de brevet français N O 81 07 558, soit de manière explicite au niveau d'une trame particulière de transmission du jeton contenant l'adresse fonctionnelle ou physique de la station à laquelle le jeton va être alloué. Le procédé selon la présente invention s'applique à la transmission du jeton selon le dit mode déterministe explicite. L'article intitulé "Token-passing ring" paru dans la revue "Electronies" du 5 Mai 1982, page 78 et suivantes, donne un bon aperçu des techniques actuelles; le pro Jet de standard IEEE 802 que l'on peut se procurer auprès de l"'Institute of Electrical and Electronics Engineers" donne de bonnes précisions sur les procédés et dispositifs connus. Dans les procédés déterministes explicites connus, toutes les sta- tions sont sur le même anneau logique, chaque station connaît à chaque instant son successeur bien que, au fur et à mesure de la mise en route et de l'arrêt des différentes stations, le successeur d'une station puisse changer dans le temps En tout état de cause, les procédés connus ne prévoient de connecter les stations du réseau qu'à une seule adresse et sur un seul anneau logique, de plus, le jeton ne circule sur l'anneau logique que de manière cyclique, de telle sorte qu'une station est obligée d'attendre que son prédécesseur lui transmette le jeton pour pouvoir émettre, et ceci une seule fois par cycle. Ces caractéristiques des procédés connus ne vont pas sans inconvé- nients car il arrive souvent que certaines stations aient besoin d'émet- tre plus souvent que d'autres; le procédé selon la présente invention a pour but de remédier à ces inconvénients. En effet, selon la présente invention, un procédé de transmission du jeton entre les stations est particulièrement remarquable en ce que, les stations sont réparties, et ordonnées séquentiellement, dans plusieurs anneaux logiques de priorités différentes. Le jeton circule alors successivement dans chaque anneau et les stations affectées à l'anneau le plus prioritaire obtiendront le jeton avant les autres stations; de plus, la circulation du jeton sera systé- matiquement interrompue au bout d'un temps prédéterminé pour être affecté à nouveau à l'anneau le plus prioritaire; ainsi les stations de l'anneau le plus prioritaire recevront le jeton plus souvent que les autres. Pour améliorer encore la souplesse d'affectation du jeton, la présente invention est encore particulièrement remarquable en ce que, chaque station pourra être pourvue de plusieurs adresses, ces diverses adresses d'une même station pouvant être affectées à un même anneau logique ou disséminées dans plusieurs anneaux logiques, dans ce cas, on dira que le jeton est alloué non plus à une station mais à une adresse et ainsi, une même station pourra recevoir le jeton plusieurs fois, et donc plus souvent que les autres stations, puisqu'elle recevra le jeton à chaque fois que celui-ci sera alloué à une des adresses dont elle est pourvue. On comprendra mieux l'intérêt de l'invention au moyen de la des- cription d'un cas pratique avec des évaluations chiffrées le tout à titre d'exemple non limitatif. Examinons le cas d'un réseau local comportant parmi d'autres types de stations, d'une part une ou plusieurs stations de type demandeur de service et d'autre part, une ou plusieurs stations de type serveur de service. Un exemple typique de serveur est une station capable de fournir à un demandeur des documents, textes et/ou figures, de format A 4 ou autre, ces documents étant stockés sous forme d'enregistrements optiques digitaux comportant entre 1 et 4 Mégabits; ce type de serveur sera appelé DOR dans la suite du texte. Le débit d'un DOR étant de l'ordre de 2,4 Mégabits par seconde, alors que le débit du réseau étant par exemple de l'ordre de 4 Mégabits par seconde, si l'on veut limiter pour des raisons de coût la taille du tampon de sortie du DOR à, par exemple, 16 kilobits ( 2 K byte), le tampon de sortie sera plein au bout de 16 000/2 400 000 = 6,66 milli- secondes, il faudra donc que le DOR obtienne le jeton toutes les 6 mil- lisecondes pour pouvoir vider son tampon de sortie en émettant une trame de 16 kilobits à destination du demandeur; l'ensemble des trames reçues par le demandeur lui permettra de reconstituer l'image et, par exemple, de l'afficher sur un écran. On voit bien, dans cet exemple chiffré non limitatif, que pour des raisons d'économie de réalisation -tampon de sortie limité à 16 K bits- il faut que le jeton soit impérativement alloué au DOR au bout d'un temps prédéterminé qui serait ici de 6 millisecondes; le DOR doit bénéficier d'une priorité. A part la raison d'économie, il peut y avoir des raisons de quali- té de service -temps total acceptable par le demandeur pour obtenir la transmission de l'image complète qui nécessitent également de donner une priorité à certaines stations. Le DOR doit bénéficier d'une priorité d'allocation du jeton car il ne peut attendre que son prédécesseur lui transmette le jeton puisque le temps d'attente serait fonction du nombre de stations connectées sur l'anneau logique et du trafic de ces stations et pourrait donc être supérieur au dit temps prédéterminé de 6 millisecondes. Dans cet exemple, la mise en oeuvre du procédé selon l'invention consiste à affecter le ou les DOR à un premier anneau logique le plus prioritaire et à affecter les autres stations à un ou plusieurs autres anneaux logiques de priorités plus basses; ainsi, chaque anneau logique, de priorité Pl à Pp, comporte donc une ou plusieurs stations adres- sées de 51 àa Ss, la station active ayant la plus petite adresse %mina étant considérée comme le point d'entrée initial de l'anneau considéré. Le parcours normal du jeton pourrait être de parcourir chaque anneau en entier au moins une fois en commençant par l'anneau le plus prioritaire attaqué par son point d'entrée initial, puis en parcourant successivement les autres anneaux dans l'ordre des priorités décroissan- tes; l'adresse de chaque station étant alors composée de la concaténa- tion de la priorité de l'anneau et de l'adresse de la station sur l'anneau o elle se trouve: As =|Pil J Sj, chaque adresse est ainsi unique dans le réseau, mais ce parcours du jeton ne serait qu'une -simple transposition des procédés connus. En fait, selon l'invention, le parcours du jeton que nous venons de décrire va être perturbé par l'interruption due à l'écoulement de l'intervalle de temps prédéterminé; lors de cet événement, quel que soit l'emplacement du jeton, celui-ci, conformément à l'invention, devra remonter au point d'entrée initial de l'anneau le plus prioritaire; cette remontée peut ne pas s'effectuer directement pour sauvegarder les adresses de retour; en conséquence, la première station interrompue par l'écoulement de l'intervalle de temps prédéterminé transmettra le jeton non pas à son successeur comme elle aurait dû le faire selon les procé- dés connus mais elle transmettra le jeton au point d'entrée initial de l'anneau de priorité immédiatement supérieure à l'anneau sur lequel se trouve la station interrompue; le point d'entrée ainsi atteint, sachant comme toutes les autres stations du réseau que le temps prédéterminé est écoulé, mémorisera l'adresse de retour dans l'anneau qui vient de lui transmettre le jeton puis transmettra immédiatement le jeton à un anneau de priorité supérieure et ainsi de suite jusqu'à ce que le jeton arrive dans l'anneau le plus prioritaire; ainsi, le jeton sera à nouveau dispo- nible pour le DOR Bien entendu, l'intervalle de temps prédéterminé aura une valeur telle que additionnée au temps maximum de remontée du jeton, temps qui dépend notamment du nombre d'anneaux logiques, le jeton arrive au DOR en temps voulu pour vider le tampon de sortie dont la taille a été volontairement limitée. Le déclanchement du comptage du temps prédéterminé s'effectue à chaque arrivée du jeton dans l'anneau le plus prioritaire. Lorsque le jeton redescendra vers les anneaux les moins prioritai- res, il recommencera à parcourir chaque anneau en entier sauf lorsqu'il arrivera sur l'anneau o se trouve la station qui avait été interrompue car, dans ce cas, le jeton sera immédiatement affecté à la station qui n'avait pas pu utiliser le jeton à cause de l'interruption. Si une deuxième interruption se produit au cours de la descente du jeton avant d'avoir atteint l'anneau précédemment interrompu, le m&me procédé itératif est exécuté. Ainsi le jeton parcourt le réseau multianneaux suivant l'ordre connu des adresses As des stations mais selon l'invention le jeton est constamment rappelé vers l'anneau le plus prioritaire selon un processus itératif dont l'effet est d'allouer le jeton plus souvent aux anneaux les plus prioritaires et donc aux stations affectées à ces anneaux. 252740 1 Dans le cas d'un réseau comportant quatre anneaux logiques, une bonne affectation des stations serait: sur l'anneau de priorité O -la plus forte les serveurs DOR ou autres ayant le même type d'exigences; sur l'anneau de priorité 1, les terminaux synchrones par exemple télé- phone digitalisé; sur l'anneau de priorité 2, les terminaux asynchrones de type serveurs; sur l'anneau de priorité 3, les terminaux asynchrones de type demandeurs. Le nombre total de stations et leur répartition dans les anneaux logiques est fonction du débit du réseau et du trafic entre les sta- tions. Dans certains cas il peut être intéressant de dissocier la notion de station et la notion d'adresse de station de telle sorte que, selon un procédé complémentaire au précédent et faisant aussi partie de l'invention, il soit possible qu'une station quelconque possède plusieurs adresses; chacune de ces adresses d'une même station quelcon- que est alors, dans le réseau, affectée de la priorité de l'anneau dans lequel elle se trouve; ainsi une station peut être doublement privilé- giée, d'une part grâce à ses adresses multiples, d'autre part grâce au niveau de priorité de chacune de ses adresses; un poste téléphonique digitalisé supportant un gros trafic est un bon exemple de station justifiant plusieurs adresses qui, dans ce cas non limitatif, seraient toutes dans le même anneau de priorité 1 ci-dessus décrit. Durant le déroulement normal du procédé selon l'invention et lorsque la dernière station du dernier anneau a eu le jeton, c'est que le jeton a accompli un tour complet de l'anneau le moins prioritaire avant que le temps prédéterminé ne se soit écoulé; dans ce cas, et toujours en restant dans le cadre de l'invention, le procédé comporte deux options: soit le jeton continue à circuler sur l'anneau le moins prioritaire en attendant l'interruption, soit le jeton remonte directe- ment au point d'entrée de l'anneau le plus prioritaire sans attendre l'interruption. Le procédé d'allocation du jeton, objet de l'invention, s'applique à des réseaux appelés distribués, par opposition aux réseaux appelés centralisés, les trames de transmission du jeton sont des trames spéci- fiques -pour plus de détails à ce sujet voir IEEE 802 déjà cité-; lorsque la trame spécifique à l'allocation du jeton à l'anneau le plus prioritaire, ou au point d'entrée initial de cet anneau, est détectée par les stations du réseau qui "guettent" en permanence, le comptage du temps prédéterminé commence dans toutes les stations qui, toutes, possè- dent le dispositif adéquat, par exemple un circuit RC connu. REVENDICATIONS: 1 Procédé de transmission de l'allocation, à des stations qui peuvent émettre ou recevoir des messages, d'un droit à émettre appelé jeton, le dit jeton ne pouvant être alloué qu'à une seule station à la fois parmi toutes les stations faisant partie d'un réseau local de communications, le dit jeton étant attribué successivement à chaque sta- tion selon un ordre logique préétabli de leurs adresses, caractérisé en ce que, les stations sont réparties, et ordonnées séquentiellement, dans plusieurs anneaux logiques de priorités différentes. 2 Procédé de transmission selon la revendication 1 caracté- risé en ce que une ou plusieurs adresses peut être affectée à une seule des dites stations, le dit jeton étant alors alloué séquentiellement aux diverses adresses et non plus aux stations. 3 Procédé de transmission selon la revendication 2 caracté- risé en ce que une station quelconque ayant plusieurs adresses peut avoir chacune de ses adresses affectée à un même ou à plusieurs des dits anneaux logiques de priorités différentes. 4 Procédé de transmission selon l'une quelconque des reven- dications précédentes caractérisé en ce que le jeton circule de station en station ou d'une adresse à la suivante, en priorité dans l'anneau logique ayant la plus grande priorité puis de proche en proche jusqu'à l'anneau logique de plus basse priorité. Procédé de transmission selon la revendication 4, dont chaque anneau logique comporte une station prédéterminée, ou déterminée dynamiquement, qui se reconnaît elle-même comme étant le point d'entrée initial de l'anneau logique, caractérisé en ce que l'abandon d'un anneau logique vers un anneau de plus faible priorité s'effectue lorsque le jeton a effectué un tour complet de l'anneau logique à abandonner. 6 Procédé de transmission selon la revendication 5, caracté- risé en ce que lorsque le jeton passe d'un premier anneau logique à un deuxième anneau logique de plus faible priorité, il est affecté à l'adresse de station qui suit immédiatement l'adresse de la dernière station ayant utilisé le jeton lorsque celui-ci était affecté pour la dernière fois à ce dit deuxième anneau logique de plus faible priorité. 7 Procédé de transmission selon la revendication 5 ou 6, caractérisé en ce que l'abandon d'un anneau logique vers un, anneau de plus forte priorité s'effectue lorsqu'un certain temps prédéterminé s'est écoulé depuis la dernière allocation du jeton à l'anneau logique le plus prioritaire. 8 Procédé de transmission selon la revendication 7 caracté- risé en ce que chaque station, ou adresse, nouvellement connectée et ne sachant pas si le dit temps prédéterminé s'est écoulé, effectue une ten- tative d'allocation du jeton à un anneau logique plus prioritaire que l'anneau logique sur lequel elle se trouve lorsque le jeton lui est alloué pour la première fois. 9 Procédé de transmission selon la revendication 7 ou 8 caractérisé en ce que, la remontée du jeton d'un premier anneau logique vers un deuxième anneau logique de plus forte priorité s'effectue de telle sorte que le jeton soit alloué au point d'entrée initial du dit deuxième anneau logique de plus forte priorité. Procédé de transmission selon la revendication 9, caracté- risé en ce que un anneau logique de priorité intermédiaire qui reçoit le jeton alors que le dit temps prédéterminé s'est écoulé, transmet immédiatement le jeton à un anneau logique de priorité supérieure. 11 Procédé de transmission selon l'une quelconque des reven- dications précédentes, caractérisé en ce que l'anneau le moins priori- taire garde le jeton tant que le dit temps prédéterminé ne s'est pas écoulé. 12 Procédé de transmission selon l'une quelconque des reven- dications 1 à 10, caractérisé en ce que l'anneau le moins prioritaire transmet le jeton à l'anneau le plus prioritaire lorsque le jeton a par- couru entièrement le dit anneau le moins prioritaire. 13 Dispositif et ensemble de dispositifs identiques implémen- tés dans chaque station pour la mise en oeuvre du procédé selon l'une quelconque des revendications précédentes.