Brevet FR2719958A1 — publié le 19951117

Domaine de l'invention. La présente invention conceme un procédé de réduction de volume des données échangées entre systèmes informatiques. Son domaine est celui des systèmes informatiques qui échangent des données en utilisant des réseaux publics ou privés de transmission de données, et plus particulièrement des réseaux de transmission par paquets suivant la recommandation X25 du CCITT. Cependant, étant donné que l'invention agit au niveau quatre du modèle OSI à sept niveaux. elle peut etre appliquée à tout système de transmission de données par blocs où il serait nécessaire de transmettre, en plus des données, un élément de qualification de données non homogène avec celles-ci. Etat de la technique. Définitions. Afin de faciliter la compréhension du fonctionnement du procédé, il convient d'effectuer certains rappels et conventions de désignation. Les recommandations X25 et V42bis du CCITT sont supposées connues, ainsi que le modèle de normalisation OSI à sept niveaux. Un réseau public (ou privé) de transmission de données par paquets suivant la recommandation X25 du CCITT sera par commodité désigné par "réseau public (ou privé) X25". De même, la recommandation X25 du CCITT sera par commodité désignée par "X25". Les données échangées entre deux systèmes informatiques sont constituées de groupes de caractères (en général des octets), le nombre de caractères d'un groupe pouvant être quelconque (mais non nul). Ces groupes seront par commodité désignés par le terme d'usage courant de "blocs". Un bloc peut être par exemple un élément de structure de base de données, le contenu d'un écran d'affichage, ou même un caractère isolé. Ces blocs sont créés par le système informatique émetteur au niveau OSI 4 (application origine), puis remis à un élément de niveau OSI 3 de ce système, qui va en assurer le transfert jusqu'à son élément homologue du système informatique récepteur, qui lui-même les remettra à l'application destinataire du niveau OSI 4. La transmission d'un bloc par un réseau X25 va s'effectuer au niveau OSI 3 par découpage de ce bloc en paquets, dont la taille maximale est convenue entre les éléments du réseau, ces paquets étant ensuite transmis au destinataire par le réseau. Un bloc pouvant être découpé en plusieurs paquets, chaque paquet comporte, dans son champ d'en-tête, une indication binaire appelée "bit M", une valeur 1 indiquant que le paquet concerné n'est pas le demier paquet constituant le bloc, une valeur 0 indique le dernier paquet constituant le bloc. Un bloc va donc être transmis sous forme d'une succession de N paquets comportant un "bit M" à 1 (N pouvant être nul) et d'un paquet comportant un "bit M" à 0. La recommandation X25 du CCITT associe aux blocs échangés un élément de service "qualificateur de données" (ou "bit Q"), utilisé au niveau des applications (niveau OSI 4) qui exploitent les données échangées. Ces applications peuvent effectuer un traitement différent sur les blocs reçus suivant la valeur de ce qualificateur binaire (0 ou 1). Un bloc comporte toujours un qualificateur de données. La présence de cette caractéristique explique que l'invention est particulièrement efficace dans le cas de l'utilisation d'un réseau X25. Un ensemble constitué d'un qualificateur de données et d'un bloc de données sera par commodité appelé "message". Les systèmes informatiques sont de plus en plus souvent connectés entre eux, en vue de pouvoir échanger rapidement des informations de niveau applicatif. De nombreux systèmes informatiques utilisent avantageusement comme support de communication des réseaux de transmission X25, publics ou privés. L'augmentation de la vitesse de calcul de ces systèmes et des volumes d'informations échangés ont fait ressortir le point faible de ces supports de communication, à savoir leur faible débit utile (le débit utile étant défini comme le rapport du volume des données échangées au temps écoulé à les échanger). Ce débit est limité par la vitesse maximale des équipements de transmission mis en oeuvre ainsi que par des considérations économiques, notamment sur les réseaux publics. De plus, I'échange de données informatiques entre deux équipements connectés à un réseau taxé est confronté, outre le problème déjà évoqué, au coût de la taxation par le réseau du transport des données, un élément de ce coût étant fonction du volume des données transportées, la comptabilisation de ce volume étant en général faite par unités indivisibles de taxation (principe de taxation similaire à celui du réseau téléphonique commuté). II paraît donc utile de compresser les données échangées (pour en réduire le volume, et donc la vitesse apparente de leur transmission), ainsi que d'émettre sur le réseau, autant que possible, des paquets de taille égale ou légèrement inférieure à un multiple de la taille des unités de taxation du réseau (pour optimiser le coût du transport). Les données ainsi compressées seront transmises par le réseau de transport au système informatique récepteur qui, après les avoir décompressées, pourra restituer les données originales à l'application de traitement. Afin d'optimiser le coût du transport, il apparaît intéressant d'effectuer la compression non sur des paquets (niveau OSI 3), mais sur les messages (niveau OSI 4) , c'est à dire avant de confier les données au service de transport. De plus, le niveau OSI 4 est certainement plus facile d'accès à un programmeur d'application informatique que les niveaux OSI inférieurs. Ainsi, par exemple, un message "origine" de 1500 octets représentant sans compression 12 paquets de 128 octets et 24 unités de taxation de 64 octets serait compressé en un message de 438 octets (par exemple) représentant 7 unités de taxation. L'expérience montre que l'efficacité de la compression croît avec la taille des messages à échanger. II est donc avantageux de regrouper plusieurs messages en un seul message plus long pour en effectuer une compression plus efficace, et de transmettre ce dernier message compressé. Mais il faut tenir compte du fait que les messages destinés à la transmission sur un réseau X25 peuvent comporter des éléments de services "qualificateur de données" différents d'un message à l'autre, rendant impossible la simple concaténation des données des messages. Le but de l'invention est donc de fournir un procédé -de mise en oeuvre simple (niveau OSI 4), -permettant de diminuer le volume des données traversant le réseau de transport, -permettant la transmission d'un qualificateur de données par message, -permettant de réduire le coût du transport des données. Exposé de l'invention. L'invention concerne un procédé de compactage et de décompactage de données appliqué à l'échange de messages entre au moins un système informatique émetteur et au moins un système informatique récepteur reliés entre eux par un réseau de transmission de données, en vue de réduire le volume des données échangées ainsi que le coût éventuel de leur transport sur un réseau public ou privé à facturation du volume transporté par unité de taxation. Le procédé s'applique au niveau OSI 4 (niveau utilisateur) et agit sur des suites de un ou plusieurs messages consécutifs de longueur quelconque. Le procédé effectue la compression des données à l'émission, message par message, suivant l'algorithme de compression décrit dans la recommandation V42bis du CCITT, puis leur décompression à la réception suivant l'algorithme inverse. Le procédé permet de transmettre à l'application destinataire les qualificateurs de données respectifs des messages échangés, par codage de ces qualificateurs à l'émission et décodage à la réception. Le procédé permet de générer sur un réseau taxé des paquets de longueur multiple de celle des unités de taxation du réseau, ou du moins d'une longueur optimale. Le procédé de compactage est utilisé par le système informatique émetteur des messages, le procédé de décompactage par le système informatique récepteur. Le procédé est indépendant de la taille de paquet choisie, de la taille des messages à transmettre et de leur nombre. Compactage. Le procédé de compactage associe à une suite S de messages Mn issue du système informatique émetteur et à destination du système informatique récepteur, chaque message Mn étant constitué d'un qualificateur de données Qn et de données Dn, un message "composite" C. Ce message composite C, destiné à être expédié vers le système informatique récepteur, dispose des éléments suffisants pour la reconstitution ultérieure des données des messages originaux et de leurs qualificateurs respectifs par le système informatique récepteur utilisant le procédé de décompactage de l'invention sur les messages reçus. Le message composite C est constitué de la façon suivante (Figure 1): Pour chaque message Mn provenant du système informatique émetteur, il est formé un bloc intermédiaire In constitué: -d'un octet Hn représentatif du qualificateur de données Qn , placé en première position du bloc intermédiaire, les octets Hi étant donnés par une fonction bijective de codage des qualificateurs Qi, cette fonction étant connue du procédé de décompactage. (Cet octet sera traité par le procédé de décompactage par la fonction inverse, qui permettra alors de restituer le qualificateur de données original). -d'un ensemble Kn de bits représentant la suite des index résultant de la compression des données Dn du message à l'aide de l'algorithme de compression décrit dans la recommandation V42bis du CCITT. (Rappel : les séquences de caractères sont remplacées par les index d'un "dictionnaire de compression", créé au fur et à mesure de la compression, le nombre maximal des index possibles étant limité à une valeur dite "taille du dictionnaire" Ainsi, aucun index ne peut être supérieur à cette taille de dictionnaire. Lors de l'opération de décompression, ces index de dictionnaire permettront de reconstituer le dictionnaire de compression, et ainsi les données du message original). La taille du dictionnaire doit être choisie de valeur inférieure à 4095, afin que les index du dictionnaire puissent être exprimés par éléments de 12 bits. Cette taille est convenue avec le procédé de décompactage, afin que le dictionnaire de décompression ait la même taille que celle du dictionnaire de compression. Une taille de dictionnaire de 4095 constitue le meilleur compromis entre la facilité de réalisation et le taux de compression obtenu. L'ensemble Kn est donc formé d'une concaténation d'éléments de 12 bits étant la représentation binaire des index résultants de la compression des données Dn. En particulier, sa longueur en nombre de bits est un multiple de 12. -d'un élément X indiquant la fin du message et constitué -d'une suite de 12 bits étant la représentation binaire d'un nombre compris entre 4095 (inclus) et la taille du dictionnaire (exclue), la valeur de ce nombre étant convenue avec le procédé de décompactage. Par exemple, pour une taille choisie de dictionnaire de 4000 index, X pourrait être constitué de la suite 11111011 0100, représentant le nombre 4020. -et si le nombre de bits constituant l'ensemble Kn est un multiple de 8, d'une suite complémentaire de 4 bits de valeur 0, soit la représentation 0000, afin que le nombre de bits constituant le bloc intermédiaire In soit un multiple de 8. Cet élément X peut être considéré comme un index "spécial" du dictionnaire, de valeur supérieure à la taille du dictionnaire, index dont la présence constitue donc en quelque sorte une "erreur" au sens de l'algorithme décrit dans la recommandation V42bis du CCITT, aucune donnée ne pouvant être associée à cet index. L'avantage de cet élément de 12 bits est son homogénéité avec la suite d'index résultant de la compression. (Cet élément sera détecté lors de sa réception par le procédé de décompactage et transformé en information de fin de message). Le message composite C est formé de la concaténation des blocs intermédiaires In successifs formés comme indiqué ci-dessus. Dans un but de synchronisation du procédé avec un système informatique émetteur de données qui fournirait des messages Mn séparés par un court intervalle de temps t, un temporisateur de surveillance TS dont la valeur Tm est choisie supérieure à cet intervalle de temps est armé à chaque fin de formation d'un bloc intermédiaire In et désarmé en début de formation d'un bloc intermédiaire ln+1 suivant le bloc intermédiaire In (Figure 2). Lorsque ce temporisateur arrive à échéance, le message composite C est considéré comme complet et terminé (Figure 3). La valeur Tm de TS doit pouvoir être ajustée pour s'accorder avec la cadence de réception des messages Mn successifs par le procédé, en vue d'obtenir des messages composites les plus longs possibles, sans pour cela retarder éxagérément la fin de la constitution de ces messages. L'ajustement optimal de Tm est obtenu par l'expérimentation de plusieurs valeurs. L'émission du message composite C sur un réseau taxé peut avoir lieu de manière simultanée à sa création, dès lors que sa longueur devient suffisante, en le découpant en blocs de taille égale à un multiple de la taille d'une unité de taxation UT (inférieure ou égale à la taille de paquet choisie), sauf peut-être en fin du message composite C, où le bloc peut avoir une longueur inférieure. Les blocs ainsi formés sont alors confiés dès leur formation au niveau OSI 3 du système informatique émetteur, qui se chargera de leur acheminement vers son homologue récepteur dans des conditions optimales de rentabilité du point de vue de la taxation (Figure 4). II est donc évident que le dernier bloc (de taille inférieure à la taille d'une unité de taxation UT) du message composite C est confié au niveau OSI 3 à l'échéance du temporisateur TS. Dans le cas où l'émission sur le réseau s'effectue de manière simultanée à la constitution du message composite C, le procédé, connaissant la taille du dernier bloc à émettre, peut donc, en fonction de l'écart d de cette taille avec celle d'une unité de taxation, décider d'anticiper l'échéance du temporisateur TS, et de procéder avant cette échéance à l'émission du bloc (Figure 5). La perte d'efficacité en matière de taxation est minime compte tenu du gain de temps obtenu. De manière plus technique, cela revient à donner à TS une valeur variable t fonction de la différence d entre la taille d'une unité de taxation et celle du prochain bloc à confier au niveau OSI 3, valeur d'autant plus faible que la différence est faible, mais non négative. Par exemple, une telle fonction pourrait être de la forme t=f(d)=Tm(1-kd/UT), Tm et k étant des valeurs à déterminer par expérimentation (il faut remarquer que le cas UT=0 signifie qu'il n'y a pas de taxation par le réseau, et donc que le temporisateur TS n'a plus d'utilité en ce cas). Décompactage. Le niveau OSI 3 du système informatique récepteur fournit le message composite R identique au message composite C original, éventuellement découpé en plusieurs blocs ou paquets, qu'il concatène dans ce cas pour obtenir le message R. Le procédé de décompactage associe à un message composite R reçu par le système informatique récepteur et provenant du procédé de compactage du système informatique émetteur une suite S de messages Mn , chaque message Mn étant constitué d'un qualificateur de données Qn et de données Dn. La suite S de messages Mn est identique à la suite originale compactée par le procédé de l'invention et émise par le système informatique émetteur. Cette suite S de messages Mn est obtenue par analyse du message composite R, de la façon suivante (Figure 6): -Le premier octet du message R fournit, par application à sa valeur de la fonction de décodage inverse à celle de codage des qualificateurs par le procédé de compactage, le qualificateur de données Q1 à associer au message M1 -Les octets suivants sont considérés comme une suite de bits qui est analysée successivement par groupes de 12 bits consécutifs jusqu'à la reconnaissance de l'élément X de 12 bits (ou index "spécial" décrit dans le procédé de compactage), de valeur convenue avec le procédé de compactage, qui délimite la fin des données compressées correspondant aux données D1 du message M1. Les groupes de 12 bits ainsi analysés forment les valeurs des index du dictionnaire créé à la compression par le procédé de compactage, qui vont fournir, par application de l'algorithme de décompression décrit dans la recommandation V42bis du CCITT, le "dictionnaire de décompression" et donc les séquences de caractères dont la concaténation fournit les données D1 du message M1. Si le nombre bits ainsi analysés, y compris les 12 bits de l'élément X, n'est pas un multiple de 8, les 4 bits suivants sont analysés et leur valeur ignorée, afin de resynchroniser l'analyse sur un alignement par octets. Le message M1 peut alors être remis au système informatique récepteur qui va l'exploiter. -L'octet du message R occupant la position suivant le demier bit analysé foumit par son décodage le qualificateur de données Q2. -Le traitement des octets suivants, jusqu'à la reconnaissance de l'élément X, va fournir par décompression les données D2 constituant le message M2, de la même manière que pour le message M1. Et plus généralement, l'analyse du message R jusqu'à sa fin foumira les qualificateurs Qn et les données Dn constituant les messages Mn. La suite S originale de messages Mn est donc reconstituée et peut être exploitée par l'application du système informatique récepteur. Le procédé de décompactage peut être appliqué simultanément à la réception du message R, dès lors que la longueur de R est suffisante pour permettre son application. Application industrielle. Le procédé de l'invention, agissant au niveau applicatif (niveau OSI 4), peut donc être réalisé comme une sorte de 'filtre logiciel' à intercaler entre une application existante et le niveau OSI 3. La réalisation du procédé peut cependant, suivant les systèmes informatiques considérés, présenter des difficultés, par exemple au niveau de la taille de mémoire nécessaire à son fonctionnement, à celui du langage de programmation utilisé, de l'hétérogénéité des systèmes informatiques émetteurs et récepteurs, etc.. Le procédé pourrait en ce cas être avantageusement réalisé sur un système calculateur électronique autonome SCA externe au système informatique SY1 et connecté entre ce système et le réseau de transmission (Figure 7). Ce système SCA assurerait les fonctions de connexion et de transport des niveaux OSI 3 et inférieurs, vers le système informatique SY1 d'une part, et le réseau d'autre part, afin de pouvoir disposer au niveau OSI 4 des données provenant de SY1 ou à destination de celui-ci. Les données Sr, reçues de SY1, se verraient appliquer le procédé de compactage de l'invention P, les messages composites C résultants étant envoyés au système informatique distant via le réseau. Réciproquement, le procédé de décompactage de l'invention P serait appliqué aux messages composites R reçus du système informatique distant, les suites Sr ainsi reconstituées étant retransmises vers le système SYl. La figure 7 montre l'architecture OSI et l'interconnexion d'un tel système SCA. Cette réalisation aurait l'avantage de n'apporter aucune modification au système informatique SY1 considéré, et pourrait, en cas de réalisation industrielle, permettre une mise en oeuvre rapide du procédé, à la portée d'utilisateurs ne disposant pas des connaissances techniques nécessaires à la réalisation du procédé sur leur système informatique, ou ne souhaitant pas le réaliser eux-mêmes. Par exemple, un tel système SCA, conçu en vue de son utilisation dans un environnement de réseau X25, devrait comporter au minimum -deux connexions physiques correspondant aux connexions utilisées par le système informatique d'une part, le réseau d'autre part, et supportant chacune une transmission synchrone de vitesse supérieure ou égale à celle de l'élément auquel elle est reliée, -un processeur de calcul de puissance suffisante, -une capacité de mémoire adaptée, -des éléments logiciels constituant les couches OSI 3 et inférieures, -une connexion permettant un dialogue entre un utilisateur et le SCA, en vue par exemple de l'introduction des valeurs des différents paramètres (taille UT, paramètres X25, valeur de TS, etc...). REVENDICATIONS 1. Procédé de compactage et de décompactage de données appliqué à l'échange de messages entre au moins un système informatique émetteur et au moins un système informatique récepteur reliés entre eux par un réseau de transmission de données, en vue de réduire le volume des données échangées ainsi que le coût éventuel de leur transport sur un réseau public ou privé à facturation du volume par unité de taxation, caractérisé en ce qu'il s'applique au niveau OSI 4 et agit sur une suite S de un ou plusieurs messages consécutifs Mn constitués chacun d'un qualificateur de données Qn et de données Dn de longueur quelconque échangée entre une application émettrice et une application réceptrice, en transformant cette suite S en un message composite compacté C destiné à être transporté par le réseau puis décompacté à destination pour fournir la suite originale S à l'application réceptrice, en ce qu'il effectue la compression des données Dn des messages Mn à l'émission, puis leur décompression à la réception, avec intégration dans les données compressées d'un élément X indiquant la fin de chaque message, cet élément étant homogène aux données compressées, en ce qu'il transmet à l'application réceptrice les qualificateurs de données respectifs Qn des messages Mn émis par l'application émettrice, par codage de ces qualificateurs à l'émission et décodage à la réception, en ce qu'il découpe un message composite C à émettre sur un réseau taxé en blocs de longueur multiple de celle des unités de taxation UT du réseau, ou du moins d'une longueur optimale en ce qui concerne la taxation. 2. Procédé suivant la revendication 1, caractérisé en ce que le compactage associe à une suite S de messages Mn issue du système informatique émetteur et à destination du système informatique récepteur, chaque message Mn étant constitué d'un qualificateur de données Qn et de données Dn, un message "composite" C constitué de la concaténation de blocs intermédiaires In formés, pour chaque message Mn de la suite S: -d'un octet Hn représentatif du qualificateur de données Qn , placé en première position du bloc intermédiaire In, les octets Hi étant donnés par une fonction bijective de codage des qualificateurs Qi, cette fonction étant connue du procédé de décompactage. -d'un ensemble Kn de bits représentant la suite des index résultant de la compression des données Dn du message Mn à l'aide de l'algorithme de compression décrit dans la recommandation V42bis du CCITT, la taille du dictionnaire étant choisie de valeur inférieure à 4095, afin que les index du dictionnaire puissent être exprimés par éléments de 12 bits. -d'un élément X indiquant la fin du message et constitué -d'une suite de 12 bits étant la représentation binaire d'un nombre compris entre 4095 (inclus) et la taille du dictionnaire (exclue), dont la valeur est convenue avec le décompactage. -et si le nombre de bits constituant l'ensemble Kn est un multiple de 8, d'une suite complémentaire de 4 bits de valeur 0, soit la représentation binaire 0000, afin que le nombre de bits constituant le bloc intermédiaire In soit un multiple de 8. 3. Procédé suivant l'une quelconque des revendications 1 et 2, caractérisé en ce qu'un temporisateur de surveillance TS est armé à chaque fin de formation d'un bloc intermédiaire In et désarmé en début de formation d'un bloc intermédiaire In+l suivant le bloc intermédiaire In. Lorsque ce temporisateur arrive à échéance, le message composite C est considéré comme complet et terminé. 4. Procédé suivant l'une quelconque des revendications 1 à 3 caractérisé en ce que le message composite C peut être découpé en blocs de taille égale à un multiple de la taille d'une unité de taxation UT (inférieure ou égale à la taille de paquet choisie), sauf peut-être en fin du message composite C, où le bloc peut avoir une longueur inférieure, ces blocs étant confiés au niveau OSI 3 du système informatique émetteur en vue de leur émission sur un réseau taxé. 5. Procédé suivant l'une quelconque des revendications 1 à 4, caractérisé en ce que la valeur t du temporisateur TS peut être rendue variable en fonction de la différence d entre la taille d'une unité de taxation UT et celle du prochain bloc à confier au niveau OSI 3, valeur d'autant plus faible que la différence est faible, mais non négative. 6. Procédé suivant l'une quelconque des revendications 1 à 5, caractérisé en ce que le décompactage associe à un message composite R reçu par le système informatique récepteur une suite S de messages Mn , chaque message Mn étant constitué d'un qualificateur de données Qn et de données Dn, la suite S de messages Mn étant identique à la suite originale émise par le système informatique émetteur. 7 Procédé suivant l'une quelconque des revendications I à 6, caractérisé en ce que cette suite S de messages Mn est obtenue par analyse du message composite R, de la façon suivante: -Le premier octet du message R fournit, par application à sa valeur de la fonction de décodage inverse à celle de codage des qualificateurs par le procédé de compactage, le qualificateur de données Q1 à associer au message M1 -Les octets suivants sont considérés comme une suite de bits qui est analysée successivement par groupes de 12 bits consécutifs jusqu'à la reconnaissance de l'élément X de 12 bits, qui délimite la fin des données compressées correspondant aux données D1 du message M1. -Les groupes de 12 bits ainsi analysés forment les valeurs des index du dictionnaire créé à la compression par le compactage, et fournissent, par application de l'algorithme de décompression décrit dans la recommandation V42bis du CCITT, les séquences de caractères dont la concaténation fournit les données D1 du message M1. -Si le nombre bits ainsi analysés, y compris les 12 bits de l'élément X, n'est pas un multiple de 8, les 4 bits suivants sont analysés et leur valeur ignorée, afin de resynchroniser l'analyse sur un alignement par octets. -L'octet du message R occupant la position suivant le demier bit analysé foumit par son décodage le qualificateur de données Q2. -Le traitement des octets suivants, jusqu'à la reconnaissance de l'élément X , va foumir par décompression les données D2 constituant le message M2, de la même manière que pour le message M1. -Et plus généralement, l'analyse du message R jusqu'à sa fin fournira les qualificateurs Qn et les données Dn constituant les messages Mn. 8. Procédé suivant la revendication 7, caractérisé en ce que le procédé de décompactage peut être appliqué simultanément à la réception du message R, dès lors que la longueur de R est suffisante pour permettre son application.