Brevet FR2539935A1 — publié le 19840727

La présente invention se rapporte aux systèmes de trans- mission de données, ou téléinformatique, et plus particulière- ment à des procédés pour détecter la collision de messages transmis sur un réseau de transmission de données multipoint. Les réseaux de transmission de données multipoint per- mettent à-une série de stations, telles que par exemple des ordinateurs, des terminaux, des imprimantes, des dispositifs analogiques, etc de communiquer entre eux au moyen d'une ou plusieurs voies partagées. Dans de nombreux réseaux locaux à large bande,chaque station communique avec d'autres stations du réseau en uti- lisant les techniques bien connues de multiplexage à divi- sion de fréquences Des émissions provenant de toutes les stations sont couplées par une Ligne d'émission commune,ap- pelée fréquemment la "voie ascendante",à un dispositif de retransmission électrique,appelé une"tête de ligne" La tête de ligne retransmet les signaux à une ligne de réception com- mune,appelée généralement la "voie descendante" Chaque sta- tion est couplée aux lignes d'émission et de réception res- pective communes au moyen d'un modem Ainsi l'émetteur (modu- lateur) de chaque modem est couplé à la voie ascendante et le récepteur (le démodulateur) est couplé à la voie descendante. Dans certains systèmes de réseaux à large bande, la voie ascendante et la vois descendante partagent un unique câble coaxial Les deux voies fonctionnent à deux fréquences por- teuses différentes afin de permettre au modem de chaque sta- tion de différencier les émissions des réceptions Dans de tels systèmes, le dispositif de tête de ligne transpose les signaux émis dans la fréquence appropriée pour la réception. Dans d'autres systèmes à large bande, deux lignes de transmission séparées sont utilisées de sorte que le dispo- sitif de tête de ligne retransmet les signaux appliqués sur la voie ascendante à la voie descendante sans qu'il soit né- cessaire d'effectuer un changement de fréquence. Dans le cas o de grandes longueurs de cable sont uti- lisées le temps nécessaire à un signal émis pour se propager le long de la voie ascendanted'émission jusqu'à la tête de ligne puis sur la voie descendante de réception jusqu'à ce qu'il soit reçu par la station émettrice peut avoir une durée importante Par exemple, si l'on considère la Fig 1 à la- quelle on se référera brièvement, supposons que la station Z commence à émettre un message au temps t O Avant que le si- gnal de la station Z ait pu traverser la tête de ligne et être détecté sur la voie de réception par l'émetteur-récepteur Y, supposons que l'émetteur-récepteur Y, ne détectant aucun câble en activité, commence à émettre son propre message au temps tl Il en résulte qu'il se produit une collision des si- gnaux et, de ce fait, il est nécessaire de prévoir dans le système de transmission un mécanisme approprié quelconque de détection des collisions afin d'éviter le chaos. La présente invention fournit un procédé de détection des collisions qui comporte l'emploi de systèmes de code cou- ramment utilisés pour vérifier qu'un message exempt d'erreur a été reçu Par conséquent, la présente invention est facile à mettre en oeuvre et est compatible avec les procédés d'accès au câble par priorité,tels que l'accès multiple à détection de la porteuse (CSMA) (voir, par exemple, le brevet US no 4 234 952). Par conséquent, l'invention a pour objet un procédé pour détecter les collisions entre des messages numériques trans- mis sur un système de transmission à réseau de câbles communs. Une station émettrice émet initialement un signal indicateur ou drapeau sur la voie d'émission du câble commun, indiquant qu'un message numérique est sur le point d'être transmis En commençant au premier bit du message numérique, la station émettrice commence à calculer un code de contrôle cyclique par redondance (CCR) pour le message numérique pendant que celuici est émis Après que N bits du message ont été émis, la station émettrice met en mémoire la valeur en cours du code CCR Une fois que le message complet a été émis, la sta- tion émet alors un second signal indicateur ou drapeau indi- quant que le message numérique a été complètement émis La station émettrice contrôle alors la voie de réception et dès qu'elle détecte un drapeau, elle commence à calculer une va- leur CCR pour N bits du message tels que reçus Si la valeur CCR calculée pour le signal reçu ne correspond pas à la va- leur CCR mise en mémoire du message précédemment émis, il est admis qu'une collision s'est produite En outre, si la station émettrice ne parvient pas à détecter un drapeau après que le double du temps de propagation d'aller-retour maximal (T) se soit écoulé (le "créneau de collision") il est alors également admis qu'une collision s'est produite Dans le cas o une collision s'est produite, la station émettrice peut alors ré-émettre son message conformément à une procédure pré- déterminée quelconque,telle que celle prévus dans les systèmes à accès multiple à détection de la porteuse. D'autres caractéristiques de l'invention apparaîtront à la lecture de la description qui va suivre et à l'examen des dessins annexés dans lesquels: la Fig 1 est un schéma-bloc qui représente un système de transmission à large bande caractéristique dans lequel plusieurs stations sont couplées à des câbles d'émission et de réception communs; la Fig 2 est une représentation de la disposition d'un message numérique caractéristique utilisé par la présente in- vention; et la Fig 3 est un organigramme des étapes qui constituent le procédé de la présente invention. L'invention concerne un procédé pour détecter des colli- sions entre des messages numériques sur un système de trans- mission à réseau de câbles communs Dans la description qui va suivre, on a mentionné, aux fins de l'explication, des valeurs spécifiques,desconfigurations de système particulières, etc afin de faciliter une pleine compréhension de la pré- sente invention Cependant, il apparaîtra clairement aux spé- cialistes de la technique que la présente invention peut être mise en oeuvre sans ces détails spécifiques Dans d'autres cas, on a représenté sous forme de schémas-blocs des circuits et des opérations logiques bien connus pour ne pas obscurcir inutilement la présente invention. Sur la Fig I à laquelle on se référera maintenant, on a représenté un système de transmission de données à large bande caractéristique Une série de stations-(A, B, Y, Z) sont couplées à une voie d'émission 10 et à une voie de réception 15 La voie d'émission 10 est électriquement cou- plée à la voie de réception 15 par l'intermédiaire d'un dis- positif de tête de ligne 18 Ainsi, les stations A-Z par- tagent toute une ligne drémission et une ligne de réception communes Les messages émis par une station sur la voie d'é- mission 10 sont retransmis par la tête de ligne 18 et sont appliqués sur la voie de réception 15 pour permettre la ré- ception par une station particulière Au moyen d'un adres- sage approprié, comme il est bien connu, une station peut transmettre un message à une autre station spécifique à l'in- térieur du réseau On comprendra que bien que la Fig 1 re- présente un réseau à large bande qui utilise deux lignes, des systèmes utilisant un unique câble coaxial sont également cou- ramment construits et peuvent être également employés par la présente invention Dans de tels systèmes à une seule ligne, le dispositif de tête de ligne 18 effectue le changement de fréquence nécessaire ainsi que la retransmission, comme in- diqué ci-dessus. Comme représenté, la station Z est séparée de la tête de ligne 18 d'une distance dz De même, l'émetteur-récepteur Y est séparé de la tête de ligne 18 d'une distance dy Par con- séquent, il existe un retard propre à chaque station parti- culière pour qu'elle puisse détecter sa propre émission de données, étant donné que le signal doit se propager jusqu'à la tête de ligne et revenir jusqu'à la station émettrice sur la voie de réception 15 -En outre, il existe des retards fi- nis liés à l'électronique tant de la station (et notamment du modem) que de la tête de ligne 1-8 Sur la Fig 1, le retard de propagation rencontré par la station pour détecter son propre signal émis sur la voie de réception 15 est relative- ment court pour les stations A et B et relativement long pour les stations Y et Z. Supposons à titre d'exemple que les stations Y et-Z soient relativement étroitement proches l'une de l'autre et aient, par conséquent, des retards de propagation aller-retour T approximativement égaux, retards qui, sur la Fig 1, co- respondent au retard de propagation maximal pour le réseau (les stations Y et Z sont les plus éloignées de la tête de ligne) Si, à un temps t O, la station Y commence à émettre un message sur la voie d'émission 10, les deux stations Y et Z recevront l'émission de Y approximativement au même instant, après un retard T Cependant, on comprendra que la station Z peut commencer à émettre son propre message à tout moment avant expiration de la période de temps T étant donné que la station Z n'aura pas encore détecté une quelconque activité sur la voie de réception 15 Dans le cas le plus défavorable la station Y ne sera pas capable de détecter une collision entre les messages avant l'expiration d'une période de temps de 2 T après le début de l'émission par la station Y de son propre message En d'autres termes, une station émettrice qui n'a pas détecté une collision au cours d'une période de 2 T après qu'elle a commencé à émettre son propre message ne sera plus ensuite l'objet d'une collision Aux fins de la présente description,on a appelé cette période ( 2 T) qui re- présente le double du retard de propagation aller retour maximal pour un réseau particulier, le "créneau de collision". Le créneau de collision est principalement une fonction- de la topologie du système Dans la présente description, le créneau de collision sera exprimé en nombre équivalent de "temps de bit" Si la vitesse de transmission par une station est de D bits/seconde, le créneau de collision est défini comme étant de 2 TD temps de bits (dans le cas o le retard de propagation aller-retour maximal T pour le réseau est éga- lement exprimé en secondes) Ainsi, pour assurer une détec- tion non ambiguë des collisions, la longueur minimale de tout message numérique émis sur le système de transmission doit être de 2 TD bits. Nous référant maintenant à la Fig 2, la plupart des ré- seaux de transmission à grande vitesse utilisent des trans- missions de données auto-synchronisées Les données sont co- dées de telle sorte qu'un récepteur peut se synchroniser auto- matiquement sur l'horloge de l'émetteur Toutes les émissions commencent par une configuration de bits répétée appelée un préambule ( 22) Le préambule est suivi d'une autre configura- tion de bits appelée un drapeau ( 24) pour indiquer le début de l'émission effective des données Habituellement, la lon- gueur de message minimale ( 2 TD) est calculées en commençant après le dernier bit du drapeau 24. Typiquement, après que les données( 25)qui constituent le message numérique ont été émises par une station émettrice, une séquence de contrôle de trame (SCT) 26 qui contient un code de contrôle cyclique par redondance (CCR) ou un autre code détecteur d'erreur est émiseavant l'émission d'un dra- peau final ( 28) qui indique que le message de données a été complètement transmis De nombreux algorithmes de code CCR ont été imaginés en vue d'être utilisés pour déterminer si le signal reçu contient ou non une erreur dans le message numé- rique Le code CCR comprend un agencement particulier non ambigu de bits qui définissent la séquence de contrôle de trame 26 Le code CCR est calculé pour un message numérique pendant qu'il est émis par une station En général, il est commode pour comprendre les codes cycliques de considérer les bits qui composent le message de données à émettre comme étant les coefficients d'une équation polynomiale Voir, par exemple, R J Cypser;"Communications Architecture for Distributed Systems (Architecture de transmission pour sys- tèmes répartis) section 11 6 (Addison, Wesley Publishing Co). Etant donné que la structure et les algorithmes particuliers utilisés pour le calcul des codes CCR sont bien connus, on ne les décrira pas en détail dans la présente description. La présente invention proposeun procédé pour détecter la collision de messages numériques transmis sur un réseau à câbles communs, tel que celui représenté sur la Fig 1. Supposonsià titre -d'exemple, que la station Z commence à émettre un message sur la voie d'émission 10 au temps t O. Comme représenté sur l'organigramme de la Fig 3 ainsi que sur la Fig 2, la station Z émet un préambule 22 puis un drapeau de début de message (DDM) 24 avant d'émettre le mes- sage de données 25 En commençant par le premier bit du mes- sage de données 25, et pour N bits suivants, la station Z, tout en émettant le message de données sur la voie d'émis- sion 10,calcule la valeur CCR en utilisant des moyens de cal- cul d'algorithme CCR prédéterminés et bien connus La valeur du code CCR pour les N bits qui suivent le dernier bit du dra- peau est mise en mémoire par la station émettrice à l'aide de moyens électroniques numériques 'bien connus La station Z émet alors la séquence de contrôle de trame (SCT) (qui, dans le mode de réalisation actuellement préféré,comprend le code CCR pour la totalité du message numérique) et une sé- quence de bits de drapeau de fin de message (FDM) 28 En pra- tique, le nombre N de bits correspond au créneau de collision ( 2 TD) (N= 2 TD) et il est déterminé par la topologie particu- lière du réseau Ainsi, dans le mode de réalisation actuelle- ment préféré, tous les messages de données 25 doivent avoir une longueur d'au moins N bits afin d'assurer une détection non ambiguë descollisions La station émettrice contrôle si- multanément la voie de réception 15 afin de détecter la pré- sence d'une séquence de bits de drapeau DDM. Si la station émettrice (par exemple, la station Z) ne parvient pas, après avoir transmis son drapeau DDM 24, à dé- tecter un drapeau sur la voie de réception 15 pendant la période du créneau de collision, la station admet qu'une collision s'est produite. Si la station émettrice détecte un drapeau sur la voie de réception 15, l'émetteur-récepteur commence à calculer la valeur CCR pour N bits du message reçu Si la valeur CCR pour N bits du message émis n'est pas égale à la valeur CCR pour N bits du message reçu la station admet qu'ils'est produit une collision. Une fois qu'il a été admis qu'une collision s'est pro- duite, la station peut ré-émettre son message sur la voie d'émission 10 conformément à une quelconque hiérarchie pré- déterminée telle que, par exemple, celle d'un accès multiple à détection de la porteuse avec un système de détection des collisions On notera que, dans le cas d'une erreur de transmission (provoquéepar exemple,par une erreur transi- toire ou autre erreur aléatoire),une telle erreur sera détec- tée comme une collision présumée par la présente invention étant donné que les valeurs CCR calculée et mise en mémoire ne concorderont pas. Ainsi, la présente invention propose un procédé pour détecter des collisions entre des messages dans un système de transmission à réseau de câbles communs qui est simple à mettre en oeuvre en utilisant les algorithmes CCR de détec- tion des erreurs existants La présente invention est d'une très grande souplesse d'utilisation étant donné qu'elle ne dépend pas du débit binaire ni de la position particulière d'une quelconque station dans le système de transmission. Bien que l'on ait décrit l'invention en se référant aux Fig. 1 à 3, et en mettant l'accent sur les réseaux de transmis- sion à large bande, il est bien entendu que les Figures n'ont été données qu'à titre d'exemple et ne doivent pas être inter- prétées comme limitant d'une quelconque manière la portée de l'invention. Il est envisagé que les spécialistes de la technique puissent aporter de nombreux changements et modifications à la structure des messages et à la séquence d'étapes de trai- tement de la présente invention sans sortir pour cela du cadre ni s'écarter de l'esprit de l'invention. REVENDICATIONS 1 Procédé utilisé, dans un système de transmission de don- nées ayant des première et seconde stations (Y, Z) couplées à une ligne commune ( 10, 15), par la première station pour déterminer si un message émis par ladite première station est ou non entré en collision avec un message émis par la se- conde station, ce procédé étant-caractérisé en ce qu'il con- siste: à calculer la valeur d'un code prédéterminé pour N bits du message émis; à mettre en mémoire la valeur de ce code après N bits; à recevoir le message sur la ligne et à calculer le code prédéterminé pour N-bits du message reçu; à comparer la valeur du code mis en mémoire à la valeur du code calculé pour le message reçu, de telle sorte qu'une collision est détectée si le code mis en mémoire et le code calculé ne concordent pas. 2 Procédé selon la revendication 1, caractérisé en ce qu'on admet qu'une collision s'est produite si la première station ne reçoit pas le message émis après une période de 2 T, T étant le retard temporel de propagation maximal pour qu'un message émis sur la ligne soit reçu. 3 Procédé selon la revendication 2, caractérisé en ce que le code prédéterminé est un code de contrôle cyclique par redondance (CCR). 4 Procédé selon la revendication 3, caractérisé en ce que le message comporte un premier signal du drapeau ( 24) émis sur la ligne qui indique que le message est sur le point- d'être émis, le code de contrôle cyclique par redondance (CCR) étant calculé en commençant par le premier bit qui suit l'émission du signal de drapeau. 5 Procédé selon la revendication 4, caractérisé en ce que le code de contrôle cyclique par redondance (CCR) pour le message reçu est calculé pour N bits après réception du premier signal de drapeau. 6 Procédé selon la revendication 5, caractérisé en ce que la ligne commune comprend une voie d'émission ( 10) et une voie de réception ( 15), chacune des stations étant cou- plée à ces deux voies de sorte que les stations émettent sur la voie d'émission et reçoivent sur la voie de réception. 7 Procédé selon la revendication 5, caractérisé en ce que le nombre (N) des bits à utiliser pour calculer les valeurs du code de contrôle cyclique par redondance (CCR) correspond au nombre de bits émis pendant le temps 2 T. 8 Procédé selon la revendication 7, caractérisé en ce que le message comporte un signal de drapeau indiquant que le message a été émis dans sa totalité. 9 Procédé utilisé,dans un système de transmission ayant des première et seconde stations (Y, Z) couplées à des voies d'é- mission ( 10) et de réception ( 15), ces voies étant connectées à une tdte-de ligne ( 18), par la première station pour déter- miner si un message émis par la première station est entré en collision avec un message émis par la seconde station, ce pro- cédé étant caractérisé en ce qu'il consiste: à calculer la valeur d'un code de contrôle cyclique par redondance (CCR) pour N bits du message, N correspondant à 2 DT, formule dans laquelle D = vitesse de transmission de la première station; et T = temps de retard de propagation maximal du système pour qu'un message émis sur la voie d'émission ( 10) soit reçu sur la voie de réception ( 15) après avoir traversé la tête de ligne ( 18); à mettre en mémoire la valeur du code de con- trôle cyclique par redondance (CCR) après N bits; à recevoir le message sur la voie de réception ( 15) et à calculer une valeur de code de contrôle cyclique par redondance (CCR); à comparer la valeur du code de contrôle cyclique par redon- dance mis en mémoire à la valeur du code de contrôle cy- clique par redondance calculé pour le message reçu; de sorte qu'une collision est détectée si les valeurs des codes de con- trôle cyclique par redondance mis en mémoire et calculé ne concordent pas. Procédé selon la revendication 9, caractérisé en ce qu'on admet qu'une collision s'est produite si la première station ne reçoit pas le message émis après qu'une période de 2 T s' est écoulée. 11 Procédé selon la revendication 10, caractérisé en ce que la première station contrôle la voie de réception ( 15) pendant une période de 2 T. 12 Procédé selon la revendication 11, caractérisé en ce que le message comporte un premier signal de drapeau (Z 4) qui précède l'émission du message, le code de contrôle cy- clique par redondance (CCR) étant calculé en commençant par le premier bit qui suit la transmission du signal de drapeau. 13 Procédé selon la revendication 12, caractérisé en ce que le code de contrÈle cyclique par redondance (CCR) du mes- sage reçu est calculé pour lest N bits qui suivent la récep- tion du premier signal de drapeau ( 24). 14 Procédé selon la revendication 13, caractérisé en ce que la première station ré-émet le message conformément à une procédure prédéterminée si une collision a été détectée. Procédé selon la revendication 14, caractérisé en ce que le message comporte un second drapeau ( 18) indiquant que le message a été émis dans sa totalité.