Brevet FR2904904A1 — publié le 20080215

-1- 2904904 Méthode et système pour la résolution du problème de conflit dans un canal de communication partagé Les systèmes informatiques modernes sont devenus de plus en plus ouverts, dans la mesure où ils sont dotés de moyens plus ou moins sophistiqués, leur permettant d'entrer en dialogue ou en échange d'informations avec d'autres systèmes, moyennant des supports de communication. Un exemple très courant est le cas de réseaux d'ordinateurs connectés entre eux et situés géographiquement dans un endroit tout en constituant un réseau local. En se partageant un moyen physique de communication commun qu'on désigne par canal de communication, chaque dispositif a le droit d'utiliser ce canal afin de communiquer avec n'importe quel élément communiquant liée au réseau. Mais, ceci nécessite la mise en place d'un protocole qui gère l'accès au canal. Historiquement il y a deux grandes familles de protocoles qui gère l'accès au canal de communication : les protocoles à accès contrôlé et les protocoles à compétition. Les protocoles à compétition fonctionnent sur le multiplexage temporel, où chaque hôte possède une partie de la communication disponible, il y a donc réservation de la bande passante. De nombreux inconvénients sont inhérents à cette technologie : réseau fermé, difficulté de gestion, peu performant, nombre de machines limité. Par contre, les protocoles à compétition ne nécessitent aucune réservation préalable de la bande passante. Le plus de ces protocoles est le protocole CSMA/CD (Carrier Sense Multiple Acces / Collision Detection ; accès partagé par écoute de la porteuse / à détection de collisions). Dans ce protocole on commence d'abord par la détection de l'état du support de communication pour savoir s'il est occupé ou non, afin de voir la possibilité de communication. Si le canal est libre, la transmission commence tout en écoutant la canal. Si les données transmises ne sont pas les mêmes que celles écoutées dans le canal, le processus de transmission est arrêté et il y' a déclaration d'une collision sur le canal. Chaque dispositif ayant contribué à la provocation de cette collision, déclenche le mécanisme de résolution du problème de collision, en différant sa prochaine transmission à des instants liés à des nombres aléatoires générés dans chaque dispositif. Ainsi, chaque dispositif décrémente sa valeur aléatoire et le premier arrivant à 0, prend le canal et débute sa transmission . Ce protocole présente un défaut majeur : au fur et à mesure que le nombre de dispositifs connectés au réseau augmente, la probabilité d'avoir des collisions augmente, par conséquent le débit global de la transmission dans le canal diminue. Pour améliorer ce protocole, plusieurs solutions ont été apportées, le brevet US005717889A propose un circuit accompagné d'un algorithme de réduction des 2904904 -2- collisions. Dans les mêmes réseaux un autre dispositif dédié à la réduction des collisions a été proposé dans le brevet EP 1269692B 1. Le brevet WO 2005/099182 Al propose un protocole de résolution de contention dans un canal partagé. Le canal est partagé de telle sorte que plusieurs stations peuvent se 5 combattre pour le canal afin d'avoir l'exclusivité de communiquer à travers ce canal. Les stations qui ne gagnent pas le combat sont éliminées, mais elles peuvent combattre pour le canal pendant les prochaines contentions. Le principe de ce protocole consiste en ce que une station qui combat pour le canal génère un nombre aléatoire ou pseudo aléatoire appartenant à un intervalle compris entre 0 et 1. Le nombre aléatoire de chaque station est 10 vérifié s'il appartient à une fenêtre ayant ses bornes inférieure et supérieure dans un intervalle. Ces bornes inférieure et supérieure sont modifiées une ou plusieurs fois jusqu'à ce que cette fenêtre contienne une unique station. Cette station sera celle qui a gagné la contention et elle prendra la ligne pour communiquer. Le protocole CSMA/CD n'est pas utilisable dans les réseaux locaux sans fils, c'est une 15 version modifiée de ce protocole qui tient compte des contraintes de la transmission radio qui a été utilisée pour ce type de réseaux. Il s'agit du protocole CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance ; accès partagé par écoute de la porteuse / à évitement de collisions). Ce mécanisme impose l'envoie d'un accusé de réception ( ACK ) pour chaque paquet reçu correctement. Le principe de CSMA/CA est d'écouter le canal 20 avant d'émettre puis de tenter d'obtenir l'accès. Une des situations suivantes peut se présenter: si le canal est inoccupé lorsqu'un noeud cherche à transmettre des données, celui-ci envoie ses paquets après une temporisation. si le canal est occupé, le noeud attend la fin de la transmission pour gagner le droit 25 d'accès au canal. Lorsque sa temporisation expire et le canal est toujours inoccupé, le noeud peut enfin envoyer ses paquets. Dans un environnement où plusieurs noeuds sont en concurrence pour l'accès au canal, c'est celui qui a choisi la temporisation la plus courte qui gagne le droit d'accès au canal. Les autres noeuds attendent simplement la fin de la transmission pour 30 avoir le droit de tenter à nouveau l'accès au canal. Puisque la temporisation est aléatoire ( uniformément distribuée ) et effectuée pour chaque paquet, le canal est équitablement accessible à tous les noeuds. Le protocole CSMA/CA permet de gérer les collisions tout en palliant aux contraintes dues aux transmissions radio. Par contre les mécanismes mis en place alourdissent les échanges 35 ce qui rend les performances plus faibles qu'un réseau filaire. De plus, au fur et à mesure 2904904 -3- que le nombre de dispositifs connectés au réseau augmente, la probabilité d'avoir des collisions augmente, par conséquent le débit global de la transmission dans le canal diminue. A tout cela, il faut rajouter que dans certaines situations, cette méthode d'accès souffre d'une dégradation considérable du débit utile. En effet, dans un réseau local sans fil typique, quelques noeuds peuvent avoir des conditions défavorables autour d'eux, ayant comme résultat la mauvaise qualité de leurs transmissions radio. S'il y a au moins un noeud avec un débit de transmission bas, le débit utile des noeuds transmettant avec le débit de transmission le plus élevé est dégradé en dessous du débit utile du noeud le plus lent. Un tel comportement pénalise les noeuds rapides et favorise les lents. La raison de cette anomalie s'explique par le fait que le protocole CSMAICA garantit une probabilité à long terme d'accès au canal égale pour tous les noeuds. Quand un noeud occupe le canal pendant une longue période, parce que son débit de transmission est bas, il pénalise d'autres noeuds qui emploient un débit de transmission plus élevé. Notre invention s'inscrit dans le domaine de résolution du problème de conflit de partage d'un canal de communication. La solution qu'on propose dans cette invention se caractérise par les propriétés suivantes : c'est une technique totalement distribuée sans aucune centralisation, elle ne nécessite donc pas la présence d'un arbitre pour la gestion des communications à travers le canal. - elle est basée sur une méthode de combat au cours duquel chaque dispositif communiquant ( DC) utilise un Code Général de Contention ( CGC) . c'est une technique qui garantit un débit global constant et indépendant du nombre de dispositifs de communication (DC ) partageant le canal. c'est une technique qui permet la mise en place de plusieurs stratégies d'accès au canal personnalisées pour chaque DC ce qui offre plus de flexibilité et de souplesse pour une gestion efficace du réseau. Notre invention utilise un dispositif de communication ( figure 1 ) constitué de deux parties : 30 - la première partie représente le système hôte 101 chargé de traiter les données qui sont échangées à travers le canal de communication. - la deuxième partie que nous appelons UAC ( Unité pour l'Accès au Canal) (102) permet au hôte d'accéder au canal. Elle réalise l'interface entre le hôte et le canal de communication 108. L'UAC est composée de quatre modules : 35 - un module d'émission sur le canal (n{), cette émission peut être bloquée à travers un 5 10 15 20 25 2904904 -4système de blocage d'émission (107). - un module de réception de données présentes sur le canal (105). - un module de détection de l'état du canal (104). - un module de traitement et de contrôle (103) qui réalise la préparation des données 5 échangées entre le canal et le hôte. Ce module commande également le système de blocage d'émission. De plus, notre invention utilise une méthode qui permet aux modules d'émission et de détection de l'état du canal de fonctionner en même temps. En supposant que l'unité d'information transmise sur le canal est soit dans l'état logique A soit dans l'état logique B 10 et le module de transmission activé, le module de détection sera alors configuré pour détecter soit la présence de l'état A si le module d'émission transmet l'état B, soit la présence de l'état B si le module d'émission transmet l'état A. En revanche, si le module d'émission n'est pas activé, le module de détection est configuré pour détecter la présence de l'état A ou de l'état B sur le canal. Ce dernier mode de fonctionnement est utilisé pour 15 détecter l'état occupé ou inoccupé du canal avant de lancer la procédure de combat pour l'obtention du canal. Ce système permet donc à un DC de détecter l'état du canal pendant qu'il transmet et ceci quelque soit le type du canal. D'autre part, avec notre méthode, on peut envisager une transmission de l'information sous 20 forme série sur un seul canal de communication ou une transmission sous forme parallèle sur plusieurs sous canaux simultanément. Dans le cas de la transmission en parallèle, le DC décrit dans la figure 2, est équipé de plusieurs UACi ( avec 1 K , K étant le nombre de sous canaux ). Chaque UACi (201 à 204) gère la communication sur le sous canal SCH; (205 à 208 qui 25 lui est associé. Dans ce mode de fonctionnement, la commande de blocage du module d'émission de chaque UACi peut être générée soit en interne par le module de traitement soit en externe par tous les UACi avec j > i . A chaque fois qu'un UACj est bloqué, la commande de blocage est transmise vers tous les UACi avec i Trm : le DC ne peut pas entrer dans le combat (étape 101), il doit passer dans le mode réception jusqu'à ce que le canal redevienne à nouveau inoccupé (étapes 308 et 309). Ceci est illustré dans l'exemple de la figure 5 où le canal passe de l'état inoccupé (MO) à l'état occupé (511). Dans cet exemple on peut constater que : - les postes DC1 et DC2 sont autorisés à entrer dans le combat car ils ont terminé leur temporisation To 505 avec le canal toujours inoccupé ( 501 et 502). 2904904 -6- - DC3 a détecté l'occupation du canal alors que la durée -restante pour qu'il termine sa temporisation To 505 est Tr 520 Trma : DC4 n'entre pas dans le combat et il passe dans le mode réception (501). Si la condition d'entrée dans le combat est vérifiée, le DC désirant obtenir le canal de communication, lance la procédure de combat dont le principe est le suivant : 10 on considère un ensemble de DC désirant tous transmettre dans un même canal. L'objectif du combat est de faire ressortir parmi eux un unique DC qui va occuper le canal de communication : on l'appellera le DC gagnant ( l'unicité du gagnant exige que tous les CGC des différents DC combattants soient différents entre eux ). Pour se faire, chaque DC ayant vérifié la condition d'entrée dans le combat précédemment 15 définie, met en oeuvre son CGC qui est constitué d'une série de m éléments Xi avec 15 i m. Tous les éléments Xi ont la même durée 'r de transmission sur le canal. Chaque élément Xi peut avoir un des deux états logiques : A ou B. La procédure de combat consiste à appliquer une méthode de comparaison décentralisée à travers le canal entre les valeurs des CGC de différents DC qui sont différents entre eux. Le DC gagnant est celui 20 qui présente le CGC représentant la plus grande valeur ( en logique maximale ). Celui-ci est unique puisque nous avons imposé que tous les CGC soient différents entre eux. On peut obtenir le même résultat en déclarant gagnant le DC qui possède un CGC avec la plus petite valeur ( en logique minimale ). Dans le cas d'une transmission en série, la durée de la procédure de comparaison est 25 m x i, alors quelle est égale à 'r dans le cas d'une transmission en parallèle. Le déroulement de la comparaison décentralisée dans le cas d'une transmission en série consiste en ce que tous les DC transmettent dans le canal leurs éléments Xi (avec 15_ i min, dans ce cas le DC est éliminé du combat (étape 01). Le système de blocage d'émission 107 arrête alors la transmission du reste des éléments Xi de son CGC et le DC devient récepteur. Il est à noter que cette décision d'arrêter le combat n'est prise par le DC que si son détecteur de l'état de canal (104) détecte la présence de l'état A pendant une 20 durée de temps supérieure une valeur tmin . Si Cette condition n'est pas vérifiée, le DC n'est pas éliminé et peut alors continuer le combat en passant à la transmission de l'élément Xi+1 (étape 605) après la fin de la transmission de l'élément Xi. Cette procédure continue jusqu'à la transmission du dernier élément X. du CGC. A la fin de la transmission de l'élément X. il reste un seul combattant : c'est le DC gagnant (étape 25 612). Le fonctionnement de la procédure de combat dans le cas d'une transmission série est illustré dans l'exemple de la figure 8. Dans cet exemple, on considère 5 DC qui ont tous vérifié la condition d'accès au combat. Les CGC affectés à ces 5 DC sont donnés dans 30 la figure 7. On peut noter l'évolution suivante : - pendant la période Ti (801), les combattants éliminés sont DC1 et DC5 (810) car ils émettent chacun l'élément Xl qui est à l'état B en présence de l'état A e,0) sur le canal. Les combattants restants sont DC2, DC3 et DC4 car ils émettent chacun leur élément X1 qui est à l'état A. 35 2904904 -8- - pendant la période T2 (80g), le combattant éliminé est DC4 (M) car il émet son élément X2 qui est à l'état B en présence de l'état A sur le canal (820). DC2 et DC3 vont poursuivre le combat pour les mêmes raisons rencontrées pendant la période Ti (801). - pendant la période T3 (803), DC2 et DC3 poursuivent le combat (812) car ils émettent 5 chacun leur élément X3 qui est à l'état B en l'absence de l'état A dans le canal (M). - pendant la période T4 (8.04), DC2 et DC3 vont poursuivre le combat (812) pour les mêmes raisons rencontrées pendant la période T3 (801. - pendant la période T5 (805), DC2 et DC3 vont poursuivre le combat (812) parce qu'ils émettent chacun l'élément X5 qui est à l'état A. 10 - pendant la période T6 (806), DC2 et DC3 vont poursuivre le combat 812 pour les mêmes raisons rencontrées pendant la période T4 804). - pendant la période T7 (807), DC3 est éliminé 813 car il émet l'élément X7 qui est à l'état B en présence de l'état A sur le canal (820). DC2 continue d'émettre car il émet son élément X7 qui est à l'état A. 15 - pendant la période T8 (808), DC2 émet son dernier élément X8 qui est à l'état A. C'est le seul DC qui n'a pas été éliminé : DC2 est donc le combattant gagnant 814). Dans le cas d'une transmission en parallèle, le mécanisme de comparaison repose sur le même principe que celui qui a été décrit dans la procédure de comparaison série tout 20 en réalisant une comparaison pendant un seul intervalle de temps 'r entre les m éléments des CGC de tous les combattants. Pour cela, on associe à chaque élément Xi du CGC une unité UAC d'indice i : UAC; ( avec 1 'min, alors les 25 modules d'émissions de toutes les unités UAC ( avec j Revendications 1- Procédé pour la résolution du problème de conflit dans l'accès à un canal de communication unique partagé par plusieurs dispositifs de communication (DC ) caractérisé en ce qu'il met en oeuvre une procédure de combat, au cour duquel les DC combattants occupent le canal, en mettant en oeuvre une technique appelée comparaison décentralisée via ce canal pour la détermination du maximum ou du minimum et permettant à chaque DC participant au combat après une durée fixe et indépendante du nombre de combattants de sortir dudit combat soit gagnant, s'il possède un Code Général de Contention ( CGC ) ayant la valeur maximale ou minimale selon la logique adoptée, auquel cas il continue l'occupation du canal, soit perdant, auquel cas il libère le canal. 2- Procédé selon la revendication 1 caractérisé en ce qu'il utilise un module de détection de l'état du canal et que, si le module d'émission du système envoie un élément ayant un état logique A sur le canal, le dit module de détection est configuré pour détecter la présence de l'état logique B complément de l'état logique A sur ce canal. 20 3- Procédé selon la revendication 1 caractérisé en ce que la dite technique de comparaison décentralisée dégage à la fin du combat, après une durée fixe correspondant à la durée de transmission de tous les éléments du CGC sur le canal, un unique DC gagnant à condition que chaque DC combattant possède un CGC, ayant la même longueur que tous les autres CGC et une valeur différente 25 de celles de tous les autres DC combattants . 4- Procédé selon les revendications 1 et 3 caractérisé en ce que la dite technique de comparaison décentralisée s'opère en série ou en parallèle entre les éléments des CGC des DC combattants selon le type de canal de communication utilisé. 5- Procédé selon les revendications 1, 3 et 4 caractérisé en ce que le CGC est généré en interne par chaque DC désirant entrer dans le combat pour gagner le canal de communication. 10 15 30 35 2904904 -14- 6- Procédé selon les revendications 1,3 à 5 caractérisé en ce que le CGC est constitué d'un ou de plusieurs registres d'éléments organisés de la même façon par tous les DC de telle sorte à mettre en place différentes stratégies d'accès au canal de communication, les dites stratégies d'accès au canal de communication comprenant une stratégie garantissant l'unicité d'accès au canal avec priorité fixe et prédéfinie, une stratégie garantissant l'unicité avec priorité paramétrable, une stratégie garantissant l'unicité avec équité partielle, et une stratégie garantissant une équité totale entre les DC. 7- Procédé selon la revendication 6 caractérisé en ce que, si la stratégie d'accès au canal de communication est une stratégie garantissant l'unicité d'accès au canal avec priorité fixe et prédéfinie, elle est basée sur l'utilisation du CGC composé d'un registre contenant le code identificateur qui permet d'identifier chaque DC d'une manière unique parmi les autres DC, permettant ainsi de dégager systématiquement un gagnant unique du combat, celui qui possède le code identificateur avec la valeur maximale ou minimale selon la logique adoptée. 8- Procédé selon la revendication 6 caractérisé en ce que, si la stratégie d'accès au canal de communication est une stratégie garantissant l'unicité avec équité 20 partielle, elle est basée sur l'utilisation du CGC composé d'un registre contenant le code identificateur du DC précédé d'un registre contenant un code aléatoire, permettant ainsi de dégager systématiquement un gagnant unique du combat tiré au hasard avec une probabilité, qui n'est pas la même pour tous les DC combattants, mais qui dépend de la valeur contenu dans le registre identificateur 25 de chaque DC. 9- Procédé selon la revendication 6 caractérisé en ce que, si la stratégie d'accès au canal de communication est une stratégie garantissant l'unicité avec priorité paramétrable, elle est basée sur l'utilisation du CGC composé d'un registre contenant le code identificateur du DC précédé soit d'un registre de compte contenant un code variable non aléatoire soit d'un registre contenant un code aléatoire précédé d'un registre de compte contenant un code variable non aléatoire, permettant ainsi de dégager systématiquement un gagnant unique du combat avec la possibilité de faire varier la priorité d'accès au canal selon une loi prédéfinie au niveau de chaque DC combattant. 5 10 15 30 35 5 2904904 -15- 10- Procédé selon la revendication 6 caractérisé en ce que, si la stratégie d'accès au canal de communication est une stratégie garantissant l'équité totale, elle est basée sur l'utilisation du CGC contenant uniquement un code aléatoire, permettant ainsi d'avoir la même probabilité entre les DC combattants pour gagner le canal, mais l'unicité du gagnant n'est pas garantie car plusieurs DC peuvent avoir la même valeur du CGC après le tirage au sort. 15 20 25 30 35