Brevet FR2765756A1 — publié le 19990108

Dispositif et procédé de commutation de cellules ATM à structure non bloquante. Le domaine de l'invention est celui de la transmission de données numériques. Plus précisément, l'invention concerne la commutation de cellules ATM ("Asynchronous Transmission Mode", ou Mode de Transmission Asynchrone) entre une pluralité de voies entrantes et une pluralité de voies sortantes, notamment dans le cas de services ATM à débit variable. Le principe général de la transmission ATM est bien connu, et de nombreuses techniques ont déjà été proposées pour réaliser des noeuds de commutation entre des entrées et des sorties. Un des critères d'estimation de l'efficacité de ces techniques est le taux de perte de cellules ou, en d'autres termes, le risque de blocage à l'intérieur du noeud de commutation. Selon les techniques connues, et en particulier dans le cadre des services à débit variable, ce risque est relativement important. n peut en effet arriver que des cellules acceptées à une entrée du noeud de commutation ne puissent pas être transférées vers la sortie voulue, du fait d'un encombrement trop important d'un des liens intemes du noeud de commutation. Les techniques les plus couramment mises en oeuvre actuellement sont celles basées sur la structure de Clos, décrite notamment dans "A study of Non Blocking Switching Networks" (une étude des réseaux de commutation non bloquants), par C.Clos (The Bell System Technical Journal, PP 406424, mars 1953). La figure 1 illustre un réseau de Clos. n comprend trois étages: - un étage entrant 11, comprenant une pluralité de matrices 111 à R entrées 112 et K sorties 113 - un étage central, ou intermédiaire 12, comprenant K matrices 121 connectées chacune à une des sorties 113 de chacune des matrices d'entrée 111; - un étage de sortie 13, comprenant autant de matrices 131 que l'étage d'entrée 11, chacune des matrices 131 comprenant chacunes K entrées 132 connectées respectivement aux K matrices 121 de l'étage central 12, et R sorties 133. L'utilisation de plusieurs étages permet de minimiser le nombre de points de connexion et la taille des matrices. Cette technique s'avère efficace lorsque les communications commutées sont à débit fixe. On peut vérifier alors qu'il suffit que K soit supérieur ou égal à 2R-1 pour que le réseau soit non-bloquant. On rappelle qu'il n'y a pas de blocage lorsque toute entrée libre (c'est-à-dire pouvant accepter une nouvelle communication) peut être reliée à toute sortie libre. Le problème essentiel de la technique ATM est qu'elle est appelée à transmettre des communications à débit variable, pouvant à certains instants exiger un débit très faible, voire nul, et à d'autre instant un débit élevé, jusqu'à un débit crête donné. Lorsque l'on met en oeuvre une structure de Clos, on est alors conduit à considérer que chaque communication à un débit fixe, égal à son débit crête. On conçoit aisément que cette approche est particulièrement inefficace, notamment lorsque les communications se font par salves (ou "bursts"), et présentent de longs moment de faible débit. On réserve alors une bande passante élevée en permanence, inutilement. En effet, par exemple, si l'on considère le cas de deux communications à faible taux d'activité mais bande passante élevée lorsqu'elles sont actives, on s'aperçoit qu'elles pourraient utiliser le même chemin, si la probabilité que les instants d'activité soient les mêmes est faible. En revanche, si l'on se base sur le débit crête, la cohabitation sur le même chemin est impossible. On pourrait, pour une structure de commutation donnée, tester à chaque instant la validité des itinéraires choisis, vis-à-vis de la loi de multiplexage spécifique mise en oeuvre. Toutefois, il n'est pas possible de chiffrer a priori le blocage d'un tel réseau, compte-tenu de l'infinité des combinaisons de trafic possibles sur les liens d'entrée et de sortie. L'invention a notamment pour objectif de pallier ces différents inconvénients de l'état de la technique. Plus précisément, un premier objectif de l'invention est de fournir un dispositif et un procédé de commutation de cellules ATM qui soient non bloquants. En d'autres termes, l'invention a pour objectif de fournir un tel dispositif et un tel procédé de commutaion qui puissent assurer la commutation entre toute entrée libre et toute sortie libre. L'invention s'applique notamment à la commutation de communications à débit variable, multiplexées en entrée et/ou en sortie. Pour ce type de système, on définit une loi d'acceptation des trafics garantissant une probabilité de saturation inférieure à un seuil donné (classiquement 10-X). Une communication peut alors être acceptée sur un lien si le trafic total présente une probabilité de saturation acceptable. Selon cette approche, l'invention a pour objectif de fournir un dispositif et un procédé de commutation qui garantissent sur les liens intermédiaires une probabilité de saturation inférieure ou égal à celle acceptée (selon la même loi) sur les liens d'entrée et de sortie. En d'autres termes, un objectif de l'invention est de fournir un tel dispositif et un tel procédé qui soient statistiquement non bloquants. Ces objectifs, ainsi que d'autres qui apparaîtront par la suite, sont atteints selon l'invention à l'aide d'un dispositif de commutation de cellules ATM, comprenant au moins un étage d'entrée et un étage de sortie, chacun desdits étages comprenant au moins deux matrices de commutation, dispositif dans lequel il existe un chemin spécifique entre chaque entrée d'une desdites matrices d'entrée et chaque sortie d'une desdites matrices de sortie, de façon que le flux de données porté par tout lien intermédiaire formant ledit chemin spécifique soit un sous-ensemble des flux portés respectivement par le lien d'entrée et le lien de sortie auxquels il est associés. Ainsi, le dispositif de l'invention met en oeuvre une structure en arbre, à maillage parfait au niveau des liens. De façon avantageuse,on met en oeuvre une même règle de multiplexage sur les liens entrants et les liens sortants de tous lesdits étages. On vérifie aisément que chaque lien intermédiaire ne peut alors transporter qu'un sous-ensemble (ou, dans une situation extrême, le même ensemble) des trafics acceptés sur chaque lien d'entrée et chaque lien de sortie. On est donc sûr que la probabilité de saturation est inférieure ou égale à celle des liens d'entrée et de sortie. En d'autres termes, le réseau de commutation est "transparent", en ce qui concerne la probabilité de blocage. Dès lors qu'un trafic (ou un service) peut être accepté sur une entrée et une sortie, on est sûr qu'il pourra être transmis de l'une à l'autre. Par ailleurs, il est à noter que l'invention est indépendante de la loi de multiplexage adoptée sur les entrées et les sorties. Plusieurs architectures peuvent être envisagées pour réaliser un tel dispositif. 11 peut notamment comprendre deux étages, ledit étage entrant et ledit étage sortant, comprenant chacun N matrices de commutation, chaque matrice dudit étage entrant présentant R entrées et R2 sorties organisées en R jeux de R sorties correspondant chacun auxdites R entrées, chacun desdits jeux de R sorties alimentant une des N matrices de l'étage sortant, chacune desdites matrices de l'étage sortant présentant N.R2 entrées et R sorties, chacune desdites entrées pouvant être dirigées vers l'une quelconque desdites R sorties.. Cette structure suppose cependant de grosses matrices pour le second étage. Un autre mode de réalisation repose sur l'utilisation de trois étages, ledit étage entrant, un étage central et ledit étage sortant, ou: - ledit étage entrant comprend N matrices présentant R entrées et R2 sorties organisées en R jeux de R sorties correspondant chacun à une desdites R entrées, - ledit étage central comprend Rjeux de R matrices associant N entrées à N sorties, chaque jeu de matrices recevant l'un desdits jeux de R sorties. de l'étage entrant, et distribuant ledit jeu de R sorties sur les R matrices qu'il contient, - ledit étage sortant comprend N matrices présentant R2 entrées et R sorties, chacune desdites sorties pouvant recevoir des données d'un jeu de R entrées correspondant respectivement à une sortie d'une matrice de chacun desdits jeux de R matrices dudit étage central. fl est ainsi possible d'utiliser des matrices de taille plus réduite, de type classique. De façon préférentielle, on choisit alors N et R tels que N=2.R2. Cette structure est en effet la plus efficace, notamment pour assurer l'homogénéité entre des réseaux à bande étroite ("narrow band") et à large band ("broad band"). Selon un autre mode de réalisation, le dispositif de l'invention peut comprendre, pour ledit étage entrant, des matrices à une entrée et R sorties dirigées respectivement vers R matrices distinctes de l'étage suivant, et/ou, pour ledit étage sortant, des matrices à R entrées et une sortie, chacune desdites entrées étant connectées respectivement à R matrices distinctes de l'étage précédent. On utilise alors un nouveau type de matrices, spécifiquement adapté à l'invention. Dans ce cas, le dispositif peut également comprendre trois étages, ledit étage entrant, un étage central et ledit étage sortant, lesdits étage entrant et étage central étant organisés en R blocs entrants comprenant chacun N matrices d'entrée à une entrée et R sorties reliées respectivement à l'une des N entrées de R matrices centrales à N entrées et N sorties, et ledit étage de sortie étant organisé en N blocs sortants comprenant chacun R matrices de sortie à R entrées et une sortie, chacune desdites matrices de sortie d'un desdits N blocs sortants étant reliée à une des matrices centrales de chacun desdits blocs entrants. L'invention concerne également un procédé de commutation de cellules ATM, dans un dispositif de commutation comprenant au moins un étage d'entrée et un étage de sortie, chacun desdits étages comprenant au moins deux matrices de commutation, caractérisé en ce qu'il comprend les étapes de: - démultiplexage dans ledit étage entrant, associant à chacune de ses entrées autant de sorties qu'il y a de matrices de commutation dans l'étage suivant; - multiplexage dans ledit étage sortant, associant à chacune de ses sorties autant d'entrées qu'il y a de matrices de commutation dans l'étage précédent. Avantageusement, on met en oeuvre une même règle de multiplexage sur les liens entrants et les liens sortants de tous lesdits étages. D'autres caractéristiques et avantages de l'invention apparaîtront plus clairement à la lecture de la description suivante de modes de réalisation préférentiels de l'invention, donnés à titre de simples exemples illustratifs et non limitatifs, et des dessins annexés, parmi lesquels: - la figure 1, déjà discutée en préambule, présente le principe connu d'un réseau de Clos; la figure 2 présente un schéma de principe d'un réseau de commutation selon l'invention, comprenant deux étages; la figure 3 illustre un autre mode de réalisation d'un réseau de commutation à trois étages; - les figures 4A et 4B illustrent une structure avantageuse, basée sur le réseau de la figure 3, et qui permet d'assurer aussi bien des transferts large bande (fig.4B) que bande étroite (figAA). - la figure 5 présente également un réseau de commutation à trois étages selon l'invention, utilisant des matrices 1 x R. L'invention concerne donc un dispositif, ou réseau, de commutation de cellules ATM non bloquant, à multiplexage statistique, notamment pour des services ATM à débit variable. La figure 2 illustre le principe général de l'invention dans le cas d'un réseau à deux étages, un étage entrant 21 et un étage sortant 22. L'étage entrant 21 comprend N matrices d'entrée 2111 à 211N' qui reçoivent chacune R liens entrants (ou entrées) 2121 à 212R et qui disposent de R.N liens intermédiaires 213i.i à 213R.N L'étage sortant 22 comprend N matrices de sortie 2211 à 221N qui reçoivent également chacunes R.N liens intermédiaires 2221, à 222N,R et délivrent R sorties 2231 à 223ru Chacun des liens 212in 2l3Jet 223k respecte la même loi d'acceptation des trafics (par exemple une probabilité de saturation inférieure à 1X) Les matrices d'entrée 21 i sont organisées de façon que chaque entrée 212i puisse être dirigée vers l'une quelconque des matrices 22j de l'étage sortant. En d'autres termes, on met en oeuvre une structure en arbre, qui permet de définir N connexions possibles (N étant ici le nombre de matrices de l'étage de sortie) pour chaque entrée. De la même façon, chaque matrice 221i i de l'étage de sortie peut recevoir des données de chaque entrée 212j de l'étage d'entrée. Chacun des liens intermédiaires 222k arrivant dans une matrice 221i peut être transmis sur l'une quelconque de ses sorties 2231. On vérifie ainsi aisément qu'il n'y a aucun risque de blocage sur les liens intermédiaires 222k. ll porte en effet toujours: - un sous-ensemble (ou, éventuellement l'ensemble complet) du trafic qui était accepté sur le lien d'entrée d'où il est issu ; et - un sous-ensemble (ou éventuellement l'ensemble complet) du trafic qui était accepté sur le lien de sortie auquel il aboutit. Or, par définition, le trafic accepté sur ces liens d'entrée et de sortie respecte la loi de multiplexage prédéfinie. On notera toutefois que la structure de la figure 2 nécessite de grosses matrices pour le second étage, du fait du nombre important de connexions possibles. 11 est possible de mettre en oeuvre l'invention avec des matrices de taille plus réduite, en construisant un réseau de commutation à trois étages, tel que celui illustré en figure 3. L'étage entrant 31 comprend N matrices 3111 à 311N associant chacune R entrées 312j à 312R à R2 sorties 313i,i à313RR. Symétriquement, l'étage sortant 33 présente également N matrices 3311 à 331N qui reçoivent chacune R2 entrées 3321,1 à 332RR et délivrent chacune R sorties 3311 à 333R L'étage intermédiaire, ou central, 32 comprend quant à lui R groupes de R matrices NxN 3211,1 à 321R R. Les liens entre les différents étages sont organisés de façon que chaque entrée d'une matrice 311 de étage d'entrée puisse être transmise à l'une quelconque des R matrices 321i,1 à 321jR correspondantes. De la même façon, chaque matrice de sortie 311j peut recevoir des données de chaque matrice 32 1k de l'étage central. Plus précisément, chaque lien de sortie 331 i peut recevoir des données de l'une quelconque des R matrices 321 l,j à 321Rj. On vérifie que, de même que dans le cas de la figure 2, et pour les mêmes raisons, ce réseau de la figure 3 est non bloquant. A titre d'exemple, ce réseau peut être mis en oeuvre à l'aide de matrices 16 x 16 classiques. Pour un réseau à 16 x 3 = 58 liens ATM à 622 Mb/s, équivalent aux réseaux de type connu à 58 liens (ou 16 x 4 limités à 80%), on utilise: - 16 matrices d'entrée/sortie utilisées en 3 x 9; - 9 matrices centrales utilisées en 16 x 16, soit 25 matrices 16 x 16, pour 24 dans le réseau de type connu. La technique de l'invention nécessite donc un matrice supplémentaire. Mais en contrepartie, elle permet le multiplexage de tous les types de services (y compris à 600 Mb/s). Pour des services à 10 ou 20 Mb/s de crête, par exemple, le multiplexage permet de raccorder jusqu'à cinq fois plus de trafic. Ainsi, la technique de l'invention permet d'envisager un débit de 3000 Mb/s, alors qu'un réseau fonctionnant sur la base du débit crête seul, sans tenir compte de la sporadicité, ne peut bien sûr commuter que 600 Mb/s par lien. En pratique, ce lien subit d'ailleurs de plus une restriction à un débit maximum de 150 Mb/s (sinon, l'expansion devrait être encore plus grande). De façon avantageuse, les valeurs N et R sont choisies de façon que N = 2R2. Cela permet d'assurer simplement l'homogénéité entre le réseau "bande étroite" et le réseau "large bande", ainsi que cela est illustré par les figures 4A et 4B. Dans cet exemple, N vaut 32, et R vaut 4. Les matrices 41 de l'étage d'entrée et 42 de l'étage de sortie sont des matrices 16 x 16. Les matrices 43 de l'étage central sont des matrices 32 x 32. Le cas de l'invention, décrit en relation avec la figure 3, correspond à la figure 4B. On peut passer simplement à un situation en bande étroite, telle qu'illustrée par la figure 4A. I1 suffit de mettre en oeuvre 16 entrées par matrice 41 et 16 sorties par matrice 42. L'ensemble du dispositif de commutation reste inchangé. Dans la pratique, le passage se fera plutôt de la situation "bande étroite" (figure 4A) à la situation "large bande" (figure 4B). I1 suffit pour cela de mettre en oeuvre un sous-équipement (seulement 4 entrées ou 4 sorties) et acheminement restreint dans les matrices d'entrée et de sortie. La figure 5 illustre un autre mode de mise en oeuvre de la technique de l'invention. Au lieu d'utiliser des matrices de type connu (NxN) de façon incomplète, on met en oeuvre des matrices spécialement conçues, de type 1 x R (associant une entrée à R sorties ou, symétriquement, R entrées à un sortie). Selon cette technique, on peut distinguer R blocs d'entrées 411 à41r et N blocs de sorties 421 à 42N. Chaque bloc d'entrée 41j se décompose en: - N matrices d'entrée 4111 à 411NI comprenant chacune une entrée unique 4121 à 412N et R sorties 41311 à 413N,R. Dans ce mode de réalisations on vérifie très facilement que chaque entrée est associée à R liens correspondant respectivement aux R matrices de l'étage suivant; - R matrices centrales 4141 à 414R, présentant chacune N entrées et N sorties. Chaque entrée correspond à une matrice d'entrée distincte. Chacun des N blocs de sortie 42i comprend R matrices 4211 421R, présentant chacune une unique sortie 4221 422R et recevant R liens 423i,1 à 423i,R issus respectivement des R blocs d'entrée 411 41R. A nouveau, selon cette structure, on vérifie que chaque lien 413i ne porte qu'un sous-ensemble du trafic de l'entrée à laquelle il est associé, et que chaque lien 423 ne porte qu'un sous-ensemble du trafic de la sortie à laquelle il est associé. Cette structure met en évidence le fonctionnement de l'invention, à savoir un démultiplexage des trafics entrants, puis un remultiplexage des trafics sortants. On notera par ailleurs, que les matrices utilisées sont de taille optimale. Il apparait également clairement sur cette figure 5, que la structure de l'invention permet très facilement la diffusion, ce qui est important, notamment pour les services "large bande". Bien sûr, l'utilisation de matrices 1 x R, décrite dans un système à trois étages, peut être aisément adaptée à la situation à deux étages de la figure 2. REVENDICATIONS 1. Dispositif de commutation de cellules ATM, comprenant au moins un étage d'entrée (21; 31) et un étage de sortie (22 ; 33), chacun desdits étages comprenant au moins deux matrices de commutation (211j, 22lez 311j, 321j, 331k 411j, 414j, 422k ; 41, 42, 43), caractérisé en ce qu'il existe un chemin spécifique entre chaque entrée (212i ; 3 12i 412i) d'une desdites matrices d'entrée et chaque sortie (223j ; 333j ; 442j) d'une desdites matrices de sortie, de façon que le flux de données porté par tout lien intermédiaire (213i, 222j ; 313i, 332j; 413j, 423j) formant ledit chemin spécifique soit un sous-ensemble des flux portés respectivement par le lien d'entrée et le lien de sortie auxquels il est associés. 2. Dispositif de commutation selon la revendication 1, caractérisé en ce qu'on met en oeuvre une même règle de multiplexage sur les liens entrants et les liens sortants de tous lesdits étages. 3. Dispositif de commutation selon l'une quelconque des revendications 1 et 2, caractérisé en ce qu'il comprend deux étages, ledit étage entrant (21) et ledit étage sortant (22), comprenant chacun N matrices de commutation, chaque matrice (211 i) dudit étage entrant présentant R entrées (212i) et R.N sorties (213j) organisées en R jeux de N sorties correspondant chacun auxdites R entrées, chacun desdits jeux de N sorties alimentant les N matrices (221k) de l'étage sortant, chacune desdites matrices de l'étage sortant présentant N.R entrées (2221) et R sorties (223m), chacune desdites entrées pouvant être dirigées vers l'une quelconque desdites R sorties. 4. Dispositif de commutation selon l'une quelconque des revendications 1 et 2, caractérisé en ce qu'il comprend trois étages, ledit étage entrant (31), un étage central (32) et ledit étage sortant (33), caractérisé en ce que: - ledit étage entrant (31) comprend N matrices (311i) présentant R entrées (312j) et R2 sorties (313k) organisées en R jeux de R sorties correspondant chacun à une desdites R entrées, - ledit étage central (32) comprend R jeux de R matrices (3211) associant chacune N entrées à N sorties, chaque jeu de matrices recevant l'un desdits jeux de R sorties de l'étage entrant, et distribuant ledit jeu de R sorties sur les R matrices qu'il contient, - ledit étage sortant (33) comprend N matrices (331 ru) présentant R2 entrées (332n) et R sorties (333p), chacune desdites sorties pouvant recevoir des données d'un jeu de R entrées correspondant respectivement à une sortie d'une matrice de chacun desdits jeux de R matrices dudit étage central. 5. Dispositif de commutation selon l'une quelconque des revendications 3 et 4, caractérisé en ce que N = 2R2. 6. Dispositif de commutation selon l'une quelconque des revendications 1 à 5, caractérisé en ce que ledit étage entrant comprend des matrices (411 i) à une entrée et R sorties dirigées respectivement vers R matrices distinctes de l'étage suivant. 7. Dispositif de commutation selon l'une quelconque des revendications 1 à 6, caractérisé en ce que ledit étage sortant comprend des matrices (421i) à R entrées et une sortie, chacune desdites entrées étant connectées respectivement à R matrices distinctes de l'étage précédent. 8. Dispositif de commutation selon les revendications 6 et 7, caractérisé en ce qu'il comprend trois étages, ledit étage entrant, un étage central et ledit étage sortant, lesdits étage entrant et étage central étant organisés en R blocs entrants (41i) comprenant chacun N matrices d'entrée (411j) à une entrée (412k) et R sorties (413l) reliées respectivement à l'une des N entrées de R matrices centrales (414m) à N entrées et N sorties, et ledit étage de sortie étant organisé en N blocs sortants (42n) comprenant chacun R matrices de sortie (421p) à R entrées (423q) et une sortie (422r), ,chacune desdites matrices de sortie d'un desdits N blocs sortants étant reliée à une des matrices centrales de chacun desdits blocs entrants. 9. Procédé de commutation de cellules ATM, dans un dispositif de commutation comprenant au moins un étage d'entrée et un étage de sortie, chacun desdits étages comprenant au moins deux matrices de commutation, caractérisé en ce qu'il comprend les étapes de: - démultiplexage dans ledit étage entrant, associant à chacune de ses entrées autant de sorties qu'il y a de matrices de commutation dans l'étage suivant; - multiplexage dans ledit étage sortant, associant à chacune de ses sorties autant d'entrées qu'il y a de matrices de commutation dans l'étage précédent. 10. Procédé de commutation selon la revendication 9, caractérisé en ce qu'on met en oeuvre une même règle de multiplexage sur les liens entrants et les liens sortants de tous lesdits étages.