Brevet FR2476414A1 — publié le 19810821

"Procédé pour la transmission de paquets de données" Procédé pour la transmission de paquets de données de plusieurs sous-stations vers une station principale par l'intermédiaire d'un canal commun suivant lequel la station principale émet un signal de synchronisation qui, à la réception dans les sous-stations, indique le début d'une période qui est divisée en une succession de tranches de temps d'égale durée, et les sous- stations dans lesquelles un paquet est prêt à être transmis à la station principale transmettent ce paquet à la station principale dans une tranche de temps sélectionnée de manière quelconque dans la dite succession de tranches de temps, et la station principale établit une classification de tranches de temps à succès ou à mutilation selon que le paquet de données reçu dans une tranche de temps est non mutilé ou mutilé. L'invention se rapporte aussi à un système servant à utiliser ce procédé qui, dans la bibliographie y afférente, est habituellement indiqué par la dénomination "slotted A L O H A" ccoe cela apparaîtra, par exemple, dans l'article cité à titre de référence 1). Il ressort également de cet article que cette stratégie connue "slotted A L O H A" ne peut être utilisée avec succès que lorsque des mesures suffisantes sont prises pour éviter que le symàe atteigne iun état instable lorsqu'un trafic important lui est présenté. Plus particulièrement, un tel état instable se présente si, pour une offre de trafic importante, la trans- rmission de paquets de données à. partir des sous-stations vers la station principale devient inefficace par le fait que le nombre de paquets transmis mutilés augmente, ce qui signifie une augmentation du nombre de paquets à retransmettre qui, à leur tour, mènent à une inefficacité accure et donnent finalement un blocage complet du système. Pour éviter cette instabilité, on a déja proposé diverses stratégies basées sur des considerations théoriques détaillées pour les- quelles on peut se référer, par wenple, aux références 2 à 6 incluse. Compte non tenu du fait que dans la plupart des cas aucune mise en oeuvre directe des mesures de conduite proposées pour éviter la dite difficulté ne peut être extraite de ces pticabsons, ces stratégies connues ont toutes l'inconvénient d'annihiler l'accès libre quelconque à tout moment des sous-stations au canal de transmission et ainsi la simplicité et la robustesse du système, propriétés qui sont précisement considérées ccmme étant les plus importantes. L'invention vise à déduire de la qualité d'une tranche de temps (avec mutilation, sans mutilation) une évaluation, pour chaque jeu de conditions de radiopropagation, du nomebre de sous-stations qui émettent, et à traduire cette évaluatiion en une simple opération de commande de la station principale, opération qui élimine l'instabilité et donne à tous les mobiles des chances égales pour l'émission à succès d'un paquet de données et qui permet un "throughput" au-delà de la barrière c/c de la stratégie ordinaire "slotted A L 0 H A", caract6risé en ce que dans la station principale, sur base de la constatation du nombre de tranches de temps à succès et à mutilation, le nombre ai+, de transches de temps d'une trame i/l suivante est déterminé de telle façon qu'il soit tenu compte des probabilités conditionnelles de tranches de temps à succès et à mutilation, en connaissance du nombre de sous-stations qui émettent dans une tranche de temps, le dit nombre de tranches de temps étant choisi en fonction de la valeur attendue à posteriori, selon l 'équation = gi ' bgi + s si b i- si o r est l'évaluation du nombre de paquets qui sont prêts à être transmis à la station principale, gi le nombre de ticnhes de temps dans les- quelles un paquet mutilé est transmis dans la trame i, si le nombre de tranches de temps dans lesquelles un paquet non mutilé est transmis dans la trame i, bgi la valeur attendue a posteriori du nombre mtoyen de tranches de temps dans lesquelles un paquet mutilé est transmis dans la trame i et bsi la valeur attendue a posteriori du nombre tmoyen de tranches de temps dans lesquelles un paquet non mutilé est transmis dans la trame i. Grâce au procédé conforme à l'invention, le nombre de tranches de temps disponibles aux sous-stations est une fonction de l'évaluation continuellement remise à jour du nombre de sous-stations qui sont prêtes à transmettre un paquet de données. Le nomibre de tranches de temps est ainsi adapté aux besoins. Pour une évaluation correcte, il faut autant de tranches de temps, pas moins, mais pas plus non plus. Cette stratégie A L O H A dynamique a pour effet que le système est stable et peut, en outre, ent2aner une meilleure efficacité, étant donné que le nombre moyen de tranches de temps par période peut être inférieur au ncmbre fixe de tranches de temps par période qui est nécessaire pour l'utilisation de la stratégie connue "slotted A L O H A". Référence: 1. Leonard Kleinroch and Simon S. Lam "Packet Switching in a Multiaccess Broadcast Channel: Performance Evaluation", IEEE Transactiosn on Communications, Vol. CDM-23, no. 4, avril 1975, pp. 410-424. 2. Sirmon S. Lam and Leonard Kleinrock: "Packet Switching in a Multiaccess Broadcast Channel: Dynamic Control Procedures" IEE Transactions on Communications, Vol. CDM-23, no. 9, Septembre 1975, pp. 891-904. 3. G. Fayolle et A1., "Stability and Control of Packet-Switching Broadcast Channels", IRIA - Laboratoire de REcherche en Informatique et Automatique, Rapport de Recherche no. 116, Avril 1975. 4. Hirmmi Okada et A1., "Analysis and Application of Framed A L O H A Channel in Satellite Packet-Switching Networks - F A D R A Method" Electronics and Coamuni- cations in Japan, Vol. 60 - B, no. 8, 1977, pp. 72-80. 5. Leonard Kleinroch and Y. Yemini, "An optimal adaptive Scheme for Multiple Access Broadcast Ccmmunication", Conference Record 1978, International Conference on Ccmmtunicatiosn, Vol. 1, pp. 7.2.1. - 7.2.5. 6. John I. Capetanakis, "Conention resolving tree algorithms for multiaccess Channels", IMEE Communication Conference Boston 1979, pp. 24.6.4. - 24.6.5. L'invention et ses avantages seront décrits ci-après avec référence au dessin annexé, dans lequel: la Fig. 1 illustre un système pour la transmission de paquets de données entre une station principale et plusieurs sous-stations; la Fig. 2 illustre un organigramme des fonctions d'ordinateur exécutées dans la station principale pour réaliser le procédé conforme à l'invention. Le système représenté sur la Fig. 1 pour la transmission de paquets de données corporte une station principale A et un certain nombre de sousstations mobiles ou fixes géographiquement dispersées B1, B2, B3,... Bn. La station principale A est pourvue d'un ordinateur central 1 carportant un circuit d'horloge associé 2 et un appareil périphérique ayant la forme d'un modem 3. La station principale comporte, en outre, deux émetteursrécepteurs 4, 5 qui sont connectés par l'intermédiaire d'un réseau de matrice de commutation 6 et du dit modem 3 à l'ordinateur central 1. Les sous-stations B1, B2, B3,... Bn sont toutes de construc- tion semblable et comportent chacune un ordinateur qui est connecté à un émetteur-récepteur par l'interm diaire d'un appareil périphérique. Le système décrit jusqu'à présent est connu et sert à la transmission de paquets de données qui transmettent chacun un seul message et qui ont tous la même longueur. Plus particulièrement, chaque paquet est formé d'un nombre déterminé de bits d'identification et de con- trôle, d'un nombre déterminé de bits d'information et d'un nombre déterminé de bits de parité. Les bits de parité dans chaque paquet sont utilisés pour un code de détection d'erreur cyclique. Le système dispose de deux canaux pour la transmission par radio de paquets de données, à savoir un premier canal pour la transmission de paquets de données de la station princopale A vers les sous-stations B1, B2, B3,... Bn et un second canal pour la transmission de paquets de données des sous-stations B1, B2, B3, 3O... Bn vers la station principale A. Ces deux canaux de transmission par radio travaillent au mme débit binaire. La transmission de paquets de données de la station principale vers les sous-stations ne suscite aucune difficulté, étant donné que l'émetteur peut être commandé et que l'utilisation d'une mémoire tampon dans l'ordinateur central de la station principale permet d'émettre les paquets de données pour les sous- stations par l'intermndiaire du premier canal dans un ordre de f476414 succession déterminé, par exemple par l'intermédiaire d'un schéma de priorité déterminé. La transmission de paquets de données des sous- stations vers la station principale est cependant moins simple, étant donné que ces paquets de données ne peuvent pas être ordonnés sans plus pour être transmis successivement par l'intermédiaire du second canal vers la station principale. Le système utilise à cet effet le procédé connu selon lequel la station principale émet, par 1 'intermédiaire du second canal, un signal de synchronisation qui, à sa réception dans les sous-stations, indique le début d'une période qui est divisée en une succession de tranches de temps d'égale durée, les sous-stations qui sont prêtes à émettre un paquet de donnees vers la station principale, transmettant ce paquet dans une tranche de temps sélectionnée de manière quelconque dans la dite succession de tranches de temps et la station principale établit une classification de tranches de temps à succès ou à mutilation, selon que le paquet de données reçu dans une tranche de temps est non mutilé ou mutilé. Un paquet de données émis par une sous-station peut être reçu mutilé dans la station principale à la suite d'erreurs de deux sortes, à savoir: (1) des erreurs apparaissant de manière aléatoire qui sont provoquées par le bruit, et (2) des erreurs qui sont provoquées par des interférences qui peuvent apparaitre à la suite de la sélection simultanée d'une et même tranche de temps par plus d'une sous-station. Les erreurs du second type, qui nt pniéez E cdes imteerances apparaîtront surtout lorsque de nombreuses sous-stations essayent d'utiliser simultanément le canal de transmission comniun. Les erreurs dues-ux interférences limitent par conséquent le nombre d'utilisateurs du canal de transmission commun et l'efficacité du système. Cette perte d'efficacité peut, comme décrit plus haut et comme expliqué en détail dans la dite référence 3), facilement mener à une instabilité du système, c'est-à-dire à un effondrement total de la possibilité de transmission. Selon l'invention, cette difficulté due à l'instabilité peut être évitée d'une manière particulièrement élégante si, dans la station principale le nombre de tranches de temps d'une période ou trame suivante est adapté sur base de la constation du nombre de tranches de temps à succès et a mutilation et compte tenu des probabilités conditionnelles de tranches de temps à succès et a mutilation, en connaissance du nombre de sous-stations qui émettent dans une tranche de temps. Le procédé conforme à l'invention, non seulement empêche le système de passer à un état instable dans le cas d'une offre de trafic importante, mais en outre il a pour effet, par le fait que le nombre de tranches de temps par période est adapté aux besoins évalués, d'augmenter l'efficacité et d'améliorer le rendement. Le procédé conforme à l'invention a en outre l'avantage important de pouvoir être mis en oeuvre d'une manière simple. Pour une forme-d'exécution préférée du système conforme à l'invention, chaque période est subdivisée en un certain nombre de trames consécutives et l'adaptation du nombre de tranches de temps est réalisée par variation du nombre de tranches de temps par trame et/ou du nombre de trames par période. Pour cette forme d'exécution, le signal de synchronisation émis par la station principale indique, lors de sa réception dans les sous-stations, le début de chacune des trames. Plus particulièrement, le signal de synchronisation est alors formé par une première valeur numérique transmise sous une forme codée qui indique le nombre de trames par période et au moins une seconde valeur numérique transmise sous une forme codée qui indique le numéro d'ordre de la trame correspon- dante dans la période, ainsi que par une troisième valeur numérique transmise sous une forme codée qui indique le nombre de tranches de temps de la trame en question. Le nombre de tranches de temps par trame et/ou le nombre de trames par période est alors variable et est déterminé dans la station principale en fonction des besoins évalués. Ceci peut être réalisé d'une manière simple. A cet usage, il suffit en effet que les données concernant l'état mutilé ou non des paquets reçus dans la station principale soient traitées à l'aide de l'ordinateur central 1 selon un programme déterminé. Le programme réalise un algorithme dont l'organigramme est représenté sur la Fig. 2 et qui est basé sur deux niveaux d'information de réaction. Au niveau 1, on évalue le degré d'augmentation ou de diminution du nombre de paquets prêts à être transmis à la station principale en fonction de la constatation des paquets transmis non mutilés et mutilés. Cette information de niveau 1 détermine le nombre de tranches de temps de la première trame de la période. Au niveau 2, l'évaluation du nombre de pa- quets prêts à tre transmis à la station principale est mise à jour (updated) chaque fois à l'aide du résultat dela trame précédente. L'information de niveau 2 est dé- terminante pour le nombre de tranches de temps de la tra- me suivante et pour l'adjonction ou la non-adjonction d'une nouvelle trame à la période en question. Les légendes indiquées dans l'organigramme de la Fig. 2 ont la signification suivante: Variables évaluation de l'augmentation par unité de temps du nombre de sous-stations qui sont prêtes à transmettre un paquet évaluation du nombre de paquets prêts à être transmis à lastation principale t temps écoulé depuis la dernière période de trans- mission i numéro de trame a. nombre de tranches de temps de la trame i t. moment o débute la trame i s. nombre de tranches de temps dans lesquelles est transmis un paquet nnn mutilé dans la trame i gi nombre de tranches de temps dans lesquelles est transmis un paquet mutilé dans la trame i Yi (t1' S1i gl' t2, s2' g2' i g.i) histoire des trames. Fonctions et constantes f évalue au départ de Yi. Ceci peut s'effectuer, par exemple, de la manière suivante: A= Si-j / (ti - ti-100) j=o f évalue t au départ de sl, gi, ai et de la valeur précédente de P. Ceci peut s'effectuer, par exem- ple, de la manière suivante: =g.xb.+.xb. -s. = gi X bgi + S si i o 247641,4 bgi = 1,81 + 0,56 a représente la valeur attendue a a. posteriori du nombre moyen de tranches de temps dans lesquelles un paquet mutilé est transmis dans la tra- me i et bi = o,96 + 0,21 t représente la valeur attendue a posteriori du nombre moyen de tranches de temps dans lesquelles un paquet non mutilé est transmis dans la trame i g détermine le nombre de tranches de temps dans la tra- me suivante. Ceci peut s'effectuer, par exemple, de la manière suivante: a. = max 1, int (M7 1r indique la valeur limite inférieure de f; en dessous de cette valeur, aucune nouvelle trame n'est mise en route. Cette valeur limite peut, par exemple, être 1 = 0,5. émet- une fonction de sortie qui émet la valeur numérique qui indique le nombre de tranches de temps a. de la i trame i, en tant que partie du signal de synchronisa- tion reçit-est une fonction d'entrée qui extrait des paquets re- çus le nombre de paquets s. transmis non mnutilés et le m nombre de paquets gi transmis mutilés et extrait de l'horloge le moment ti o débute la trame numéro i. Il est clair que l'invention n'est pas limitée à la forme d'exécution préférée décrite plus haut, mais que, en fonction de l'utilisation ou de l'application du système, une forme d'exécution sans division de la pério- de de transmission en un certin nombre de trames succes- sives est aussi possible et que l'essence de l'invention doit par conséquent 8tre recherchée dans l'adaptation du nombre de tranches de temps par période de transmission. Il convient de noter, en outre que, sur la Fig. 2, le petit bloc BGNP désigne le début d'une période, BGNF le début d'une trame, NDF la fin d'une trame et DNP la fin d'une période. REVENDICATIONS: 1. Procéd pour la transmission de paquets de données de plusieurs sousstations vers une station principale par l'intermédiaire d'un canal commun suivant lequel la station principale émet un signal de syndichnsaon qui, à la réception dans les sous-stations, indique le début d'une trame qui est divisée en une succession de tranches de temps d'égale durée, et les sous-stations dans lesquelles un paquet est prêt à être transmis à la station principale transmettent ce paquet à la station principale dans une tranche de temps sélectionnée de manière quelconque dans la dite succession de tranches de temps, et la station principale établit un dénombrement de tranches de temps avec mutilation et sans mutilation selon que le paquet de données reçu dans une tranche de temps est respectivement non mutilé et mutilé, caractérisé en ce que dans la station principale, le nombre de tranches de temps d'une trame suivante estdih sur la base du nombre de tranches de temps sans mutilation et avec mutilation compté au cours de l'évolution antérieure des trames, et en ce que le nombre de tranches de temps comipris dans une trame et transmis aux sous-stations comme une partie du signal de synchronisation. 2. Procédé selon la revendication 1, caractérisé en ce que le nombre de tranches de temps d'une trame suivante est déterminé de façon qu'il soit tenu compte des probabilités conditionnelles de tranches de temps sans mutilation et avec mutilation, en connaissance du nombre de sous-stations qui émettent dans une tranche de temps, ledit nombre de tranches de temps étant choisi en fonction de la valeur attendue à posteriori, selon l'équation M=gi bg.+s.. b -s. igi si 5 o Mest 1 'évaluation du nombre de paquets qui sont prêts à être transmis à la station principale, gi le nombre de tranches de temps dans lesquelles un paquet mutilé a été transmis dans la trame i, sir le nombre de tranches de temps dans lesquelles un paquet non mutilé a été transmis dans la trame i, b gi la valeur attendue a posteriori du nombre de sousstations qui émettent simultanéement dans une tranche de temps, alors que cette tranche de temps comporte un paquet non mutilé. 3. Procédé selon la revendication 1, caractérisé en ce que les trames sont groupées en périodes, qui cormportent chacune une suite de trames, les sous-stations étant commandées de façon qu'elles n'émettent dans und période que si elles disposent d'un paquet au début de cette période.