Brevet FR2678794A1 — publié le 19930108

La présente invention a pour objet un concentrateur égalisateur de charge numérique, c'est-à-dire un circuit numérique d'interconnexion à plusieurs étages comprenant un premier nombre d'entrées supérieur à un second nombre de sorties, les charges utiles aux entrées étant réparties uniformément aux sorties. Elle est utilisable dans les systèmes de transmission de données, et, par exemple, dans des commutateurs numériques du type Knock-out. Un commutateur du type Knock-out est un commutateur dans lequel chaque entrée a un chemin d'accès à chacune des sorties, c'est-àdire qu'il est sans blocage interne. Afin d'éviter toute possibilité de collision interne il est pourvu de files d'attente de sortie. Ainsi, des données, transmises sous forme de paquets, par exemple, se présentant simultanément sur plusieurs entrées peuvent être acheminées sur la même sortie, via un circuit d'interface. Ce circuit d'interface comprend notamment, pour chaque sortie, N circuits de filtrage respectivement connectés aux N entrées du commutateur et un concentrateur N/L connecté à la sortie considérée via une file d'attente. Les circuits de filtrage, qui assurent l'auto-acheminement des paquets, identifient l'adresse de destination de chacun de ces paquets et retransmettent au concentrateur ceux qui sont destinés à la sortie considérée. Le concentrateur utilise un algorithme particulier pour sélectionner un nombre prédéterminé L de paquets présentés sur ses N entrées, L étant inférieur à N. Ces paquets sélectionnés sont stockés dans ladite file d'attente selon l'ordre d'arrivée. Le taux de perte d'information au cours de cette concentration N/L est considéré comme négligeable puisqu'étant inférieur au taux de perte du aux autres éléments de circuits. Ainsi, par exemple, avec un nombre d'entrées N grand et avec L égal à 8, le taux de perte est inférieur à 10-6 Le principe de base de la sélection des L paquets parmi N est un algorithme analogue à un tournoi à élimination (knock-out) directe à chaque tour. Dans un concentrateur à N entrées et L sorties il est procédé à L tours. L'élément de base du concentrateur est un commutateur à deux entrées et deux sorties, une seule étant "gagnante" : lorsque deux paquets arrivent un seul est sélectionné, cette sélection se faisant de façon aléatoire. A ce stade la charge utile est toujours concentrée vers les premières de sortie. Ensuite, pour égaliser la charge, on utilise un réseau Oméga avec un algorithme de routage approprié. La présente invention a donc pour objet un concentrateur à perte qui présente l'avantage de pouvoir être réalisé à l'aide de circuits de base plus simples et donc d'un prix de revient moins élevé que le concentrateur de type Knock-out. Le concentrateur de la présente invention, comprenant 2K entrées et 2K/P sorties, K et P étant des nombres entiers multiples de 2, se caractérise par le fait qu'il comprend essentiellement L, (L K-L étages de concentration constitués chacun respectivement de 2K/2, 2K/4, , ..., 2K/n, ..., 2K/P concentrateurs élémentaires à deux entrées et une sortie. Une autre caractéristique du concentrateur de l'invention réside dans le fait que les L premiers étage de commutation sont suivis du maillage Oméga inverse. Une autre caractéristique du concentrateur de l'invention réside dans le fait que le maillage entre lesdits concentrateurs élémentaires consiste à connecter deux sorties successives d'un étage aux deux entrées d'un concentrateur élémentaire de l'étage suivant. Une autre caractéristique du concentrateur de l'invention réside dans le fait que chaque concentrateur élémentaire à deux entrées et une sortie est simplement une porte logique du type OU, les paquets non significatifs étant remis à zéro par l'algorithme de routage. Les différents objets et caractéristiques de l'invention seront maintenant détaillés dans la description qui va suivre, donnée à titre d'exemple non limitatif, en se reportant aux figures annexées qui représentent: - la figure 1, un exemple de réalisation d'un concentrateur à 8 entrées et 4 sorties du type Knock-out fonctionnellement équivalent au concentrateur de la présente invention; - la figure 2, un exemple de réalisation d'un concentrateur égalisateur de charge à 32 entrées et 4 sorties conçu conformément à la présente invention; - la figure 3, un réseau du type Oméga inverse à 32 entrées; On décrira tout d'abord, en se reportant au schéma de la figure 1, un exemple de réalisation d'un concentrateur de type Knock-out. Le concentrateur de la figure I est un concentrateur 8/4, c'est-àdire qu'il comprend 8 entrées el à e8 et 4 sorties sl à s4. Il est composé de 4 étages R1 à R4. Les entrées el-e2, e3-e4, eS-e6 et e7-e8 sont connectées respectivement à des entrées non référencées de concentrateurs élémentaires C11, C12, C13 et C14 du premier étage Rt. Une sortie de chacun de ces concentrateurs élémentaires est connectée respectivement à une entrée de deux concentrateurs élémentaires C21 et C22 du second étage R2, l'autre sortie de ces concentrateurs élémentaires C11 à C14 étant respectivement connectée à une entrée de deux concentrateurs élémentaires C15 et C16 du premier étage R1 et ainsi de suite, une sortie du dernier concentrateur C17 du premier étage étant connectée à la sortie sl via 5 circuits TP1 à TP5. Ces derniers circuits sont des circuits de temporisation apportant un retard équivalent à la transmission d'un élément binaire à travers chacun des concentrateurs élémentaires. On conserve ainsi en sortie le synchronisme de l'entrée. A la fin de la première "manche", c'est-à-dire après le passage par les quatre premiers concentrateurs C11 à C14, les quatre "vainqueurs", c'est-à-dire les quatre paquets choisis de façon aléatoires parmi les huit se présentant aux entrées el à e8, sont retransmis aux entrées des deux concentrateurs C15 et C16 du premier étage R1. Deux seulement de ces paquets, les "vainqueurs" de la "seconde manche", sont retransmis respectivement aux entrées d'un concentrateur élémentaire C17 de cet étage, et un seul, le "vainqueur" de la troisième et dernière "manche", à la sortie st via les cinq circuits de temporisation TP1 à TP5. Pendant ce temps, les quatre "éliminés" de la première manche sont retransmis respectivement aux entrées des concentrateurs élémentaires C2t et C22 du second étage R2. Seuls deux paquets sont alors retransmis respectivement aux entrées d'un concentrateur élémentaire C23 de cet étage, les entrées d'un autre concentrateur C24 de ce même étage recevant les paquets rejetés par les concentrateurs C15 et C16 du premier étage lors de la "seconde manche". Le fonctionnement du circuit de concentration de la figure 1 se poursuit de façon analogue à ce qui vient d'être décrit : à la fin de la troisième et dernière "manche" quatre paquets de données sont respectivement retransmis aux sorties sl à s4. Grâce aux circuits de temporisations TPi cette retransmission est synchronisée. On remarque que le paquet retransmis sur la sortie sl est sorti "vainqueur" de toutes les "manches", le paquet retransmis sur la sortie s2 de toutes les "manches" moins une et ainsi de suite. La charge de sortie est donc bien concentrée sur les premières lignes de sortie. Pour égaliser cette charge, on a ensuite recours à un réseau Oméga OM de L entrées et L sorties (L= 4 selon l'exemple choisi), pourvu d'un algorithme de routage tournant de type connu. La réalisation du concentrateur de type Knock-out de la figure 1 nécessite des circuits d'une complexité relative mais néanmoins réelle et donc d'un prix de revient non négligeable. On remarque, notamment, le nombre élevé de circuits de temporisation pour la réalisation du concentrateur 8/4 du schéma de la figure 1. On décrira maintenant, en se reportant au schéma de la figure 2, un exemple de réalisation d'un concentrateur à 32 entrées et 4 sorties conçu conformément à la présente invention. Le concentrateur de la figure 2 se compose d'un réseau Oméga inversé tronqué à deux étages ST1 et ST2 suivi de trois étages ST3, ST4 et ST5 de concentrateurs élémentaires. Un réseau Oméga est un réseau de type connu appartenant à la classe des réseaux "delta", eux-mêmes dérivés des réseaux dits "banyan", réseaux multi-étages dont une des caractéristiques réside dans le fait qu'ils comprennent un trajet bien défini entre une entrée quelconque et une sortie quelconque. Comme les réseaux delta, les réseaux Oméga sont également caractérisés par le fait que le routage à travers ces réseaux est commandé à t'aide d'éléments binaires internes. Un réseau Oméga à N entrées et N sorties, N étant un multiple de 2, constitué d'éléments de commutation élémentaires ou commutateurs binaires de base à 2 entrées et 2 sorties comprend K = Log2N étages, chaque étage comprenant N/2 éléments de commutation. I1 est auto-acheminant et utilise une adresse de destination à K éléments binaires. D'une façon générale, le réseau Oméga peut fonctionner aussi bien en mode synchrone qu'en mode asynchrone. Mais, alors qu'il peut commuter des paquets simultanés et en parallèle, c'est un réseau bloquant, c'est-à-dire qu'il peut y avoir collision entre des paquets qui sont alors soit perdus soit retardés. La loi de maillage d'un réseau Oméga N x N qui est une matrice d'interconnexion de Log2N colonnes et de N/2 lignes est la suivante: - pour toute colonne de commutateurs binaires de base, la sortie i est connectée à l'entrée j = RotG(i) de la colonne suivante dans le sens de la transmission, i étant un nombre binaire de Log2N éléments binaires et RotG(i) étant le nombre binaire obtenu à partir de i par une rotation à gauche de i d'une position (on notera de même RotD(i) une rotation à droite). - les colonnes de commutateurs binaires de base sont numérotées dans l'ordre décroissant K-t, K-2, ..., 0 dans le sens de la transmission. - les fils d'interconnexion sont numérotés de bas en haut, un fil ayant deux numéros différents selon qu'il est considéré comme la sortie d'un commutateur binaire de base ou comme l'entrée du commutateur binaire suivant. I1 en est de même pour les fils d'entrée de la matrice, car le même maillage s'applique entre les entrées de la matrice et les entrées de la première colonne de commutateurs. La numérotation des fils de sortie est la même, que ce soit comme sorties de la matrice ou comme sorties de la dernière colonne de commutateurs binaires de base. On dit que ce maillage réalise un mélange parfait entre les colonnes dans le sens que la moitié haute et la moitié basse des sorties sont mélangées régulièrement aux entrées. Le réseau Oméga inverse s'obtient par symétrie du réseau Oméga par rapport à une droite verticale. I1 peut aussi se définir aisément en s'inspirant de la loi de maillage du réseau Oméga précédemment citée et en substituant, par exemple, RotD à RotG et en inversant l'ordre des colonnes qui devient alors 0, 1, ..., K-t selon le sens de la transmission. Le concentrateur de la figure 2 annexée est donc construit à partir d'un tel réseau dont il ne comporte que les premiers étages. Plus précisément, le schéma de la figure 2 représente un concentrateur à 32 entrées inO à in31 et 4 sorties sc0 à sc3 qui se présente sous la forme d'un réseau d'interconnexion à 2K = 32 entrées (K = 5), dont les L= 2 premiers étages (L CB231 suivis du maillage Oméga inverse ; ces 2 premiers étages sont connectés à K-L=3 étages de concentration ST3 à ST5 constitués chacun respectivement de 2K/2 = 16, 2K/4 8 et 2K/8 = 4 concentrateurs élémentaires 2/1, c'est-à-dire des concentrateurs élémentaires à deux entrées et une sortie tels que les concentrateurs CE302, CE304, CE310, CE312 et CE314 de l'étage ST3, CE401, CE403, CE406 et CE407 de l'étage ST4 et les concentrateurs CE500 à CE503 de l'étage ST5. Le maillage entre ces concentrateurs élémentaires consiste à connecter deux sorties successives (suc46, sc47) d'un étage (ST4) aux deux entrées d'un concentrateur élémentaire (CE503) de t'étage suivant (ST5). Un concentrateur élémentaire tel que le concentrateur CE503, est simplement une porte logique du type OU. Selon la technologie choisie, plusieurs étages de concentration peuvent être confondus. On suppose qu'un travail préparatoire sur les cellules à transmettre est effectué pendant leur routage dans le réseau et que ce travail est tel qu'une cellule vide ou éliminée soit remise à zéro. Le concentrateur à pertes de l'invention peut donc bien être réalisé à l'aide de circuits élémentaires particulièrement simples donc d'un prix de revient peu élevé et pouvant être mis en oeuvre en technologie à très haute densité On montrera maintenant, en se reportant au schéma de la figure 3 que la séquence de sortie du réseau Oméga inverse tronqué est une séquence égalisateur. On considère une séquence S1, S2, ..., Sq, ..., St où Sq est l'ensemble des cellules sur les lignes de sortie d'un réseau d'interconnexion à l'instant q. On dit alors que cette séquence est une séquence égalisateur si elle réalise l'égalisation des charges sur les lignes de sortie pour une durée suffisamment longue. On considère un réseau Oméga inverse d'ordre K=5 tel que représenté par le schéma de la figure 3, c'est-à-dire, comme on l'a vu précédemment, un réseau Oméga inverse d'interconnexion à 2K 32 entrées comprenant 5 étages AT1 à AT5 constitués chacun de 2K/2 16 commutateurs binaires de base, suivis du maillage Oméga inverse précédemment défini. On suppose que l'algorithme de routage suivant soit appliqué aux cellules à transmettre avant leur entrée dans le réseau de la figure 3: - à chaque instant t, les cellules libres, par l'intermédiaire d'un compteur d'adresses décrémenté d'une unité à l'arrivée de chaque cellule libre, sont routées successivement dans le sens circulaire descendant des sorties du réseau Oméga inversé et les cellules occupées, par l'intermédiaire d'un compteur d'adresses incrémenté d'une unité à l'arrivée de chaque cellule occupée, sont routées successivement dans le sens circulaire montant de ces sorties. Une description plus complète de ce fonctionnement est donnée dans la demande de brevet n" 90 11535 déposée le 19 Septembre 1990 au nom de la demanderesse pour "multiplexeur asynchrone".Pour ne prendre en compte qu'un nombre maximum de 2L cellules occupées, ou significatives, les autres cellules sont transformées en cellules vides, ou non significatives qui sont toutes remises à zéro par une simple porte logique du type ET dont une autre entrée est à la valeur zéro, c'est-à-dire qu'elles sont éliminées; - la valeur initiale utilisée pour attribuer les adresses d'arrivée des cellules significatives à chaque instant t est celle qui suit la dernière adresse attribuée à l'instant t-t. On remarque que seule la partie Oméga inverse tronqué nécessite des éléments binaires de routage, que le nombre d'étages dans cette partie est toujours L, quelque soit K, et que le routage dans cette partie est sans collision. On considère donc le réseau Oméga inverse complet correspondant au réseau Oméga inverse tronqué de la figure 2: on observe que, par construction, les groupes de 2K-L (soit 25-3 = 4) adresses consécutives à la sortie de L =3 étages se trouvent complètement et régulièrement entrelacés à la sortie du réseau complet. En effet, en considérant un groupe GSA de 8 adresses consécutives à l'entrée de t'étage AT3 de rang 3 on voit qu'il leur correspond 8 adresses possibles de sortie de cet étage réparties en 2 groupes distincts de 4 adresses consécutives. Soit GST celui de ces deux groupes qui constitue les entrées des deux commutateurs binaires de base successifs de rang 14 et 15 de l'étage AT4 de rang 4, c'est-à-dire les deux commutateurs représentés à la partie supérieure de cet étage. Afin de pouvoir suivre de façon plus aisée les cheminements possibles correspondant au groupe incident GSA, ceux-ci ont été représentés en traits plus épais. Les sorties des deux commutateurs binaires de rang respectif 14 et 15 de l'étage AT4 constituent les entrées des deux commutateurs binaires de base respectivement de rang 7 et 15 de l'étage AT5 de rang 5. Les sorties de ces commutateurs sont respectivement connectées aux sorties de rang 7, 23, 15et31. On voit que, de la même façon, le second groupe de sorties de t'étage AT3 correspondant au groupe d'entrées GSA de cet étage constitue les entrées des deux commutateurs binaires de base de rang 6 et 7 de l'étage AT4 pour finalement constituer les sorties 3, 11, 19 et 27 du réseau après leur aiguillage par les commutateurs binaires de rang 3 et 11 de l'étage ARTS. Les 8 adresses consécutives du groupe GSA se trouvent donc bien complètement et régulièrement entrelacées à la sortie du réseau Oméga inverse complet. Cette propriété découle de la définition même de la loi de maillage par rotation à droite qui réalise une inversion des éléments binaires de poids fort et des éléments binaires de poids faible entre les deux ensembles des adresses de sortie, c'est-à-dire après L=3 étages et après K = 5 étages, comme le montre le schéma de la figure 3. Autrement dit, après avoir été aiguillé par L=3 étages d'un réseau Oméga inverse, l'ensemble des adresses de sortie des cellules significatives se trouve réparti dans au plus 2L groupes consécutifs disjoints, et chaque groupe contient toute les adresses de sortie finales qui ont une partie de poids faible (L éléments binaires) commune et qui se différencient seulement par les (K-L) éléments binaires de poids fort. En conséquence, chaque groupe ne peut contenir, au plus, qu'une adresse significative. Comme d'après les caractéristiques de l'algorithme de routage cité précédemment, on ne prend en compte que 2P cellules significatives et comme les autres cellules sont remises à zéro, les concentrateurs élémentaires qui suivent le réseau Oméga tronqué déduit du réseau de la figure 3 ne modifient en rien les cellules significatives. Les cellules qui sont aiguillées vers les groupes consécutifs sortiront vers les adresses consécutives du concentrateur de la figure 2. Ce qui montre que la séquence de sortie du circuit de concentration de la présente invention est une séquence égalisateur. I1 est bien évident que la description qui précède n'a été fournie qu'à titre d'exemple non limitatif et que de nombreuses variantes peuvent être envisagées sans sortir pour autant du cadre de l'invention. REVENDICATIONS 1 - Concentrateur numérique à 2K entrées et 2K/P sorties, K et P étant des nombres entiers multiples de 2, caractérisé par le fait qu'il comprend essentiellement L, (L K-L étages de concentration (ST3, ST4, ST5) constitués chacun respectivement de 2K/2, 2K/4, ..., 2K/n, ..., 2K/P concentrateurs élémentaires (CE304, CE401, CE502, ...) à deux entrées et une sortie (scO, scl, sc2, sc3). 2 - Concentrateur numérique tel que défini en 1, caractérisé par le fait que les L premiers étage de commutation (ST t, ST2) sont suivis du maillage Oméga inverse. 3 - Concentrateur numérique tel que défini en 2, caractérisé par le fait que le maillage entre lesdits concentrateurs élémentaires (CE302, CE401, CE501, ...) consiste à connecter deux sorties successives (sc46, sc47) d'un étage (ST4) aux deux entrées d'un concentrateur élémentaire (CE503) de l'étage suivant. 4 - Concentrateur numérique tel que défini en 3, caractérisé par le fait qu'il comprend un compteur d'adresses décrémenté d'une unité à t'arrivée de chaque cellule libre, pour router successivement dans le sens circulaire descendant des sorties du réseau Oméga inversé les cellules libres successives et un compteur d'adresses incrémenté d'une unité à l'arrivée de chaque cellule occupée, pour router successivement dans le sens circulaire montant des sorties de ce réseau Oméga inverse les cellules occupées successives, ledit concentrateur comprenant également des moyens pour limiter le nombre de cellules acceptées et pour remettre à zéro les autres cellules. 5 - Concentrateur numérique tel que défini en 4, caractérisé par le fait que chaque concentrateur élémentaire (CE503) à deux entrées (sc46, sc47) et une sortie (sc0) est constitué essentiellement d'une porte logique du type OU.