Brevet FR2625056A1 — publié le 19890623

L'invention concerne un circuit de commutation rapide de paquets. Les réseaux de commutation de paquets sont largement utilisés dans les transmissions de données, car ils utilisent de façon économique les ressources des canaux de transmission; ils demandent aux terminaux d'émission et de réception de n'être mis en connexion que lorsque des données sont réellement transmises, et non pendant les périodes d'inactivité- entre transmissions. En particulier, des données sont transmises par paquets contenant chacun l'adresse du terminal de réception. La commutation de paquets dans le réseau doit être capable de lire l'adresse dans chaque paquet et d'aiguiller rapidement le paquet vers la destination correcte. Une conception bien connue de commutation rapide de paquets utilise un réseau de commutation auto- aiguilleur comprenant plusieurs éléments de commutation à 2 x 2 points de croisement qui travaillent en fonction de bits individuels contenus dans l'adresse du paquet. Les éléments de commutation sont interconnectés de façon à assurer l'aiguillage automatique d'un paquet vers l'adresse correcte pourvu qu'aucune collision avec d'autres paquets ne se produise en cours de route. Un problème posé par cette conception de commutation de paquets est que, lorsque des collisions se produisent, l'un des deux paquets en collision est aiguillé vers une mauvaise adresse. Une solution apportée par l'art antérieur à ce problème consiste à utiliser un réseau de tri ou un réseau d'interruption pour trier ou autrement traiter de façon préalable les paquets avant qu'ils entrent dans le réseau de commutation autoaiguilleur. De cette manière, il est possible d'assurer un aiguillage correct des paquets destinés à différentes adresses, sans col- lision. Cependant, ce principe ne résout pas le problème des paquets multiples ayant la même adresse de destination. Ces paquets continuent d'entrer en collision, ce qui a pour résultat d'aiguiller certains d'entre eux vers une mauvaise adresse. Un but de l'inventioh est donc de proposer un système de commutation de paquets qui résout efficacement le problème des collisions et présente une haute qualité de commutation de paquets en assurant que chaque paquet atteint l'adresse correcte. Un système de commutation de paquets selon l'invention comprend plusieurs terminaux extérieurs de sortie, plusieurs terminaux extérieurs d'entrée destinés à recevoir des paquets d'entrée, chaque paquet contenant l'adresse d'un terminal extérieur de sortie, un réseau auto-aiguilleur de commutation, plusieurs moyens de mise en file d'attente, à raison d'un connecté à chaque terminal extérieur d'entrée, destinés à recevoir des. paquets d'entrée des terminaux extérieurs d'entrée et à les stocker momentanément dans des files d'attente fonctionnant sur le principe premier entré, premier sorti, afin d'émettre les paquets de devant, se trouvant dans ces files d'attente, vers le réseau auto-aiguilleur de commutation, et à supprimer les paquets de devant de ces files d'attente en réponse à des signaux d'accusé de réception, et plusieurs moyens de vérification d'adresses, à raison d'un connecté à chaque terminal extérieur de sortie, destinés à recevoir des paquets du réseau auto-aiguilleur de commuta- tion, à vérifier leurs adresses et, si un paquet a été aiguillé vers l'adresse correcte, à l'envoyer au terminal extérieur connecté de sortie et renvoyer un signal d'accusé de réception au moyen de file d'attente par l'intermédiaire du réseau auto-aiguilleur de commutation. L'invention sera décrite plus en détail en regard des dessins annexés à titre d'exemple nullement limitatif et sur lesquels: la figure 1 est un schéma simplifié illustrant une forme de réalisation de l'invention; et les figures 2A à 2D sont des schémas simplifiés illustrant le fonctionnement des éléments de commutation de la figure 1. On décrira a présent une forme de réalisation de l'invention en référence au schéma de la figure 1. La figure 1 montre un nouveau système de commutation de paquets comprenant un réseau auto-aiguilleur 1 de commuta- tion comportant plusieurs terminaux d'entrée 1-10 à 1-17 et plusieurs terminaux de sortie 1-20 à 1-27, plusieurs terminaux extérieurs d'entrée 10-0 a 10-7, plusieurs terminaux extérieurs de sortie 20-0 à 20-7, plusieurs moyens de mise en file d'attente 30-0 à 30-7, fonctionnant sur le principe premier entré, premier sorti (FIFO), interposés entre les terminaux extérieurs d'entrée 10-0 à -7 et les terminaux d'entrée 1-10 à 1-7 du réseau auto- aiguilleur de commutation, et plusieurs moyens 40-0 à 40-7 de vérification d'adresse interposés entre des terminaux de sortie 1-20 à 1-27 du réseau auto-aiguilleur 1 de commuta- tion et les terminaux extérieurs de sortie 20-0 à 20-7. Le réseau autoaiguilleur 1 de commutation comprend des éléments de commutation 1-1 à 34 à. 2 x 2 points de croisement qui fonctionnent de façon autonome conformément à des bits individuels se trouvant dans l'information d'adresse des paquets. Les éléments de commutation 1-1 à 1- 4 travaillent en fonction du bit le moins significatif de l'adresse du paquet, les éléments de commutation 2-1 à 2-4 travaillent en fonction du bit immédiatement plus signi- ficatif et les éléments de commutation 3-1 à 3-4 travail- lent en fonction du bit le plus significatif. En d'autres termes, les éléments de commutation sont agencés en plusieurs étages et les éléments de commutation se trouvant dans les étages respectifs prennent l'un des états de commutation en fonction du bit correspondant de l'informa- tion d'adresse du paquet appliqué a leur entrée. La façon dont les éléments de commutation 1-1 à 3-4 travaillent est illustrée sur les figures 2A a 2D. Chaque élément de commutation comporte deux accès d'entrée et deux accès de sortie qui seront appelés les accès supérieurs et inférieurs d'entrée et de sortie. Lorsqu'un paquet est reçu à un premier des deux accès d'entrée d'un élément de commutation, l'élément de commutation lit le bit d'adresse du paquet concerné et prend un état dans lequel ledit premier des accès d'entrée est connecté à l'accès de sortie supérieur pour commuter le paquet vers l'accès de sortie supérieur si le bit est un "0", ou prend un état dans lequel ledit premier des accès d'entrée est connecté vers l'accès de sortie inférieur pour commuter le paquet vers] '"cs de sortie inférieur si le bit est un "1". Lorsqu, -.ement de commutation ne reçoit qu'un paquet, il peut toujours commuter le paquet de cette manière. Lorsque l'élément de commutation reçoit simultanément deux paquets d'entrée, si les bits d'adresse de ces paquets sont différents, l'élément de commutation fonctionne comme illustré sur les figures 2A et 2B, commutant ainsi les deux paquets vers l'accès de sortie correct. Si les bits d'adresse concernés des deux paquets ont des valeurs identiques, condition appelée collision, l'un des deux accès d'entrée est connecté sur l'accès correct de sortie, de sorte que l'un des paquets d'entrée est commuté vers s l'accès correct de sortie, mais l'autre accès d'entrée est connecté sur l'accès incorrect de sortie, de sorte que l'un des paquets d'entrée est commuté vers l'accès incorrect de sortie, comme illustré sur les figures 2C et 2D. Sur ces figures 2C et 2D, le paquet inférieur est commuté vers l'accès correct de sortie et le paquet supérieur est commuté sur l'accès incorrect de sortie. Chaque élément de commutation conserve l'état dans lequel il a été amené par un bit d'adresse d'un paquet jusqu'à ce qu'il reçoive un autre paquet. Les éléments de commutation sont capables d'un transfert bidirectionnel de signaux. En particulier, ils permettent non seulement le passage des paquets dans un sens, des accès d'entrée vers les accès de sortie, mais également le passage de signaux d'accusé de réception, décrit ci-après, dans l'autre sens, des accès de sortie vers les accès d'entrée. Les éléments de commutation 1-1 à 3-4 sont interconnectés selon le principe bien connu d'auto- aiguillage illustré sur la figure 1. On peut aisément vérifier que, interdisant les collisions, ce principe d'interconnexion aiguille toujours un paquet vers le terminal de sortie correct. Les moyens de mise en file d'attente 30-0 à 30- 7 fonctionnent de la manière suivante. Ch d- tes moyens 30-0 à 30-7 de mise en file d'attente comp--- 'e mémoire destinée à stocker provisoirement les paquets dans une file d'attente premier entré, premier sorti. Lorsqu'un paquet est reçu d'un terminal extérieur d'entrée, il est rattaché à l'arrière de la file d'attente. A un signal d'horloge TS produit de façon répétée, par exemple périodiquement par un moyen de commande 50, si la file d'attente n'est pas vide, le paquet se trouvant à l'avant de la file d'attente est transmis au réseau auto-aiguilleur i de commutation qui l'aiguille vers l'un des terminaux de sortie 1-20 à 1-27 et donc vers les moyens de vérification d'adresse 40-0 à 40-7. Le mime signal d'horloge TS est fourni à la totalité des moyens 30-0 à 307 de mise en file d'attente, de sorte qu'ils émettent tous leurs paquets en même temps. Après l'émission d'un paquet, un moyen de mise en file d'attente peut recevoir un signal d'accusé de réception AS de l'un des moyens 40-0 à 40-7 de vérification d'adresse par l'intermédiaire du réseau auto-aiguilleur 1 de commutation. Lorsqu'un moyen de mise en file d'attente reçoit un tel signal AS d'accusé de réception, il élimine le paquet de devant de sa file d'attente. Si un moyen de mise en file d'attente ne reçoit pas un tel signal d'accusé de récep- tion, il n'élimine pas son paquet de devant et, par conséquent, le même paquet est de nouveau émis à l'arrivée du signal d'horloge suivant TS. Chacun des moyens 40-0 à 40-7 de vérification d'adresse vérifie l'adresse du paquet reçu du réseau auto- aiguilleur i de commutation. Si un paquet a été aiguillé vers l'adresse correcte, c'est-à-dire vers les moyens de vérification d'adresse connectés au terminal extérieur de sortie ayant l'adresse du paquet, les moyens de vérifica- tion d'adresse le transmettent au terminal extérieur de sortie et renvoient un signal d'accusé de réception AS, par l'intermédiaire du réseau auto-aiguilleur 1 de commutation, indiquant que le paquet a été correctement reçu. Etant donné que les éléments de commutation du réseau auto- aiguilleur 1 de commutation sont encore dans le même état à ce moment, le signal d'accusé de réception refait le chemin du paquet en sens inverse, atteignant le moyen de mise en file d'attente (l'un des moyens 30-0 à 307) duquel le paquet est provenu. Si un paquet a été aiguillé vers une adresse incorrecte, les moyens de vérification d'adresse ne le transmettent pas au terminal extérieur de sortie et ne renvoient pas de signal d'accusé de réception. Le paquet de devant dans le moyen de mise en file d'attente n'est donc pas supprimé et est retransmis lorsque le signal d'horloge 2625056' TS est de nouveau appliqué aux moyens de mise en file d'attente. Le fonctionnement de ce nouveau système de commutation de paquet sera illustré pour un cas dans lequel trois paquets sont appliques simultanément en entrée, comme montré sur la figure 1. Un premier paquet, adressé au terminal extérieur de sortie 20-7 (adresse binaire 111), est reçu au terminal d'entrée extérieur 10-5. Un deuxième paquet, adressé au terminal extérieur de sortie 20-5 (adresse binaire 101), est reçu au terminal extérieur d'entrée 10-7. Un troisième paquet, également adressé au terminal extérieur de sortie 20-5, est reçu au terminal extérieur d'entrée 10-1. On supposera qu'aucun autre paquet n'est présent dans le système et, par conséquent, ces trois paquets gagnent immédiatement l'avant des files d'attente dans les moyens 30-1, 30-5 et 30-7 de mise en file d'attente et sont transmis simultanément au réseau auto- aiguilleur 1 de commutation. Le premier paquet est aiguillé le long du chemin 2 en passant par les éléments de commutation 1-3, 2- 4 et 3-4 jusqu'au moyen 40-7 de vérification d'adresse qui vérifie son adresse et détermine qu'il a atteint la destination correcte. Le moyen 407 de vérification d'adresse transmet donc ce paquet au terminal extérieur 20- 7 de sortie et renvoie un signal d'accusé de réception (représenté par la ligne tiretée sur le dessin) le. long du chemin 2 pour notifier au moyen 30-5 de mise en file d'attente que le paquet a été correctement reçu. Le moyen -5 de mise en file d'attente élimine alors ce paquet de sa file d'attente et se trouve prêt à émettre un autre paquet & l'instant suivant. De façon similaire, le deuxième paquet est aiguillé sur le chemin 3 par l'intermédiaire des éléments de commutation 1-4, 2-4 et 3-2 jusqu'au moyen 40-5 de vérification d'adresse. Etant donné qu'il atteint l'adresse correcte, il est transmis au terminal extérieur 20-5 de sortie et un signal d'accusé de réception est renvoyé au moyen 30-7 de mise en file d'attente qui supprime alors ce paquet de sa file d'attente. Le troisième paquet est aiguillé le long du chemin 4 par l'intermédiaire des éléments de commutation 1- 1 et 2-3 jusqu'à l'élément de commutation 3-2 o il entre en collision avec le deuxième paquet. Le résultat est que le troisième paquet est aiguillé vers une mauvaise adresse: en particulier, il est transmis au moyen 40-1 de vérifica- tion d'adresse. En détectant l'adresse incorrecte, le moyen -1 de vérification d'adresse ne transmet pas ce paquet au terminal extérieur 201 de sortie et ne renvoie pas de signal d'accusé de réception. Par conséquent, ce paquet reste dans le moyen 30-1 de mise en file d'attente et sera de nouveau émis à l'instant suivant. Etant donné qu'un paquet n'est pas supprimé avant d'être reçu à l'adresse correcte, tout paquet continue d'être émis jusqu'à ce qu'il atteigne sa destina- tion prévue. Les paquets mal aiguillés restent dans le système de communication sans être mal distribués ou perdus. Le nouveau système de commutation de paquets supprime donc l'inefficacité des systèmes de commutation de paquets de l'art antérieur dans lesquels les paquets mal aiguillés sont distribués à un mauvais terminal extérieur de sortie o ils sont abandonnés et doivent être retransmis depuis le terminal extérieur d'entrée. Le nouveau système de commutation de paquets combine donc une grande vitesse de commutation avec une haute qualité de commutation. Il va de soi que de nombreuses modifications peuvent être apportées au système de commutation de paquets décrit et représenté sans sortir du cadre de l'invention. En particulier, le réseau auto-aiguilleur de commutation peut avoir une configuration différente de celle montrée sur la figure 1 et le nombre de terminaux d'entrée et extérieurs de sortie peut être modifié comme demandé par la dimension du système de commutation de paquets. REVENDICATIONS 1. Système de commutation de paquets, carac- térisé en ce qu'il comporte plusieurs. terminaux extérieurs (20-0 à 20-7) de sortie, plusieurs terminaux extérieurs (10-0 & 10-7) d'entrée destinés à recevoir des paquets d'entrée contenant chacun une information d'adresse désignant un terminal extérieur de sortie, plusieurs moyens de mémorisation (30-0 à 30-7) associés respectivement aux terminaux extérieurs d'entrée, plusieurs moyens (40-0 à 40- 7) de vérification d'adresse associés respectivement aux terminaux extérieurs de sortie, le système comprenant un réseau de commutation ayant des terminaux d'entrée (1-10 à 1-17) associés respectivement aux moyens de mémorisation et couplés aux terminaux extérieurs respectifs d'entrée par l'intermédiaire des moyens associés de mémorisation, et des terminaux de sortie (1-20 à 1-27) associés respectivement aux moyens de vérification d'adresse et couplés aux terminaux extérieurs respectifs de sortie par l'inter- médiaire des moyens associés de vérification d'adresse, ledit réseau de commutation étant capable d'aiguiller de façon autonome des paquets reçus à l'un quelconque des terminaux d'entrée vers le terminal de sortie couplé aux terminaux extérieurs de sortie et désigné par l'information d'adresse du paquet, chacun des moyens de mémorisation recevant des paquets d'entrée du terminal extérieur associé d'entrée et les mémorisant temporairement, et transmettant les paquets mémorisés au terminal associé d'entrée du réseau de commutation, chacun des moyens de vérification d'adresse recevant des paquets dudit réseau de commutation, vérifiant les adresses desdits paquets et, si un paquet qu'il a reçu possède une information d'adresse désignant le terminal extérieur associé de sortie, transmettant ledit paquet audit terminal extérieur associé de sortie et renvoyant un signal d'accusé de réception AS aux moyens de mémorisation par l'intermédiaire du réseau de commutation, lesdits moyens de mémorisation supprimant les paquets mémorisés en réponse audit signal d'accusé de réception. 2. Système suivant la revendication 1, caractérisé en ce qu'il comporte en outre un moyen (50) de commande qui délivre de façon répétée un signal d'horloge (TS) à tous les moyens de mémorisation, lesquels, en réponse au signal d'horloge, transmettent le paquet mémorisé au réseau de commutation. 3. Système selon la revendication 2, carac- térisé en ce que chacun des moyens de mémorisation comprend un moyen (300 à 30-7) de mise en file d'attente qui mémorise le paquet provenant des terminaux extérieurs d'entrée dans des files d'attente premier entré,premier sorti, transmet les paquets d'avant desdites files au réseau de commutation en réponse audit signal d'horloge, et supprime le paquet d'avant desdites fi-les d'attente en réponse au signal d'accusé de réception. 4. Système selon la revendication 1, carac- térisé en ce que le réseau de commutation comprend plusieurs éléments de commutation (1-1 à 3-4) dont chacun prend de façon autonome un premier de ses états de commutation en réponse à l'information d'adresse du paquet appliquée à son entrée, conserve ledit premier état jusqu'à ce qu'un autre paquet soit reçu et peut permettre le passage des paquets dans un sens et permettre le passage des signaux d'accusé de réception dans le sens opposé. 5. Système selon la revendication 4, carac- térisé en ce que les éléments de commutation du réseau de commutation sont agencés en plusieurs étages et chacun des éléments de commutation se trouvant dans les étages respectifs prend ledit premier de ses états de commutation en réponse au bit correspondant de l'information d'adresse des paquets appliquée à son entrée.