Forêts couvrantes et application aux transmissions bidirectionnelles

Télécharger le fichier original (Mémoire de fin d’études)

Canal à eﬀacements de paquets

En général, les eﬀacements ne concernent pas seulement quelques bits, mais plutôt des ensembles de bits, pouvant atteindre plusieurs Giga-octets. Il convient alors de présenter un nouveau un modèle de canal, le canal à eﬀacements de paquets. Sur ce canal, on ne considère plus des mots de 1 unique bit, mais des groupements de bits : des paquets.
Sur un tel canal, soit les paquets sont transmis sans altération, soit ils sont totalement eﬀacés. L’intégrité du paquet est le plus souvent garantie par un système de détection d’erreur sur l’ensemble de celui-ci grâce à un CRC. Un CRC est notamment utilisé pour vérifier l’intégrité des paquets des protocoles TCP et UDP, tels que décrit dans [47], ou encore le CRC (pour Cyclic Redundancy Code ) du protocole Ethernet décrit dans [1]. Le calcul d’un CRC est comparable au calcul d’une fonction de hashage, tel que la fonction de hashage MD5 inventée par Ronald Rivest en 1991 dans [50]. Ce modèle de canal permet de décrire le comportement de nombreux systèmes dans lesquels de l’information peut être sujette à eﬀacements. Les paquets peuvent être eﬀacés pour deux raisons principales : soit ils sont totalement eﬀacés, soit ils ont subi trop d’erreurs pour qu’on puisse retrouver l’information originale, et on les considère comme eﬀacés en choisissant des les ignorer. Dans le protocole UDP par exemple, un paquet subissant une altération sur un unique bit est considéré comme erroné.
Exemple 1 : transmissions unidirectionnelles par paquets Les systèmes de communi-cation modernes suivent une organisation en couches (modèle OSI ). Une couche a pour but de fournir un services aux couches supérieures, en fonction d’un protocole particulier. Au sein de ces couches, les données sont regroupées au sein de paquets, qui sont alors traités indépendam-ment les uns des autres. Ces paquets peuvent être altérés ou eﬀacés durant leur transmission.
— on dit d’un paquet qu’il est eﬀacé lorsqu’il n’arrive pas à destination, par exemple à cause d’erreurs de routage sur le réseau. Un paquet peut aussi être eﬀacé à cause de l’encombrement d’un nœud du système (le buﬀer d’un routeur est plein par exemple),
— un paquet est altéré si un ou plusieurs bits de ses subissent une modification. Ces alté-rations peuvent provenir de perturbations sur le signal transmis sur le canal. Si aucun code correcteur n’est utilisé pour réparer, il est alors considéré comme erroné.
Le protocole UDP (pour User Datagram Protocol) est un des principaux protocoles de télécom-munication utilisés par Internet. Il fait partie de la couche transport du modèle OSI, quatrième couche de ce modèle, comme TCP. Il a été défini par David P. Reed et est détaillé dans la RFC 768. Le rôle de ce protocole est de permettre la transmission de données (sous forme de paquets) de manière simple entre deux entités, chacune étant définie par une adresse IP et un numéro de port. L’intégrité des données est assurée par une somme de contrôle. Un paquet UDP est constitué d’un entête (ou header en anglais), et de ses données. L’entête contient le numéro de port source, le numéro de port destinataire, la longueur des données, et une somme de contrôle. La somme de contrôle (ou checksum en Anglais) est un nombre qu’on ajoute à un message à transmettre permettant au récepteur de vérifier que le message envoyé et le message reçu sont bien les mêmes. C’est une forme de contrôle par redondance, qui permet de détecter une ou plusieurs erreurs susceptibles d’apparaître dans un message, mais pas de connaître leurs positions dans ce message, et donc de les corriger. Une somme de contrôle étant généralement plus petite que le message qu’elle accompagne, l’ensemble des valeurs qu’elle peut prendre est aussi bien plus petit que celui des messages. Par conséquent, plusieurs messages partagent la même somme de contrôle, et des erreurs de type « faux-positif » peuvent advenir, ce qui fera passer un message erroné pour un message valide aux yeux du récepteur. La somme de contrôle inclut également les adresses IP de la source et de la destination. Pour être transmis et acheminé au destinataire sur le réseau, un paquet UDP doit être encapsulé dans un paquet IP. La figure 1.3 représente l’entête d’un paquet UDP encapsule dans un paquet IP.
Le protocole TCP (pour Transmission Control Protocol) décrit dans [48], développé en 1973 puis adopté par Arpanet en 1983, est un protocole de transport fiable documenté dans la RFC 7931 de l’IETF. C’est un protocole de transmission en mode connecté, ce qui signifie qu’il repose sur l’établissement d’une connexion (handshacking) entre les deux entités préalablement à l’envoi de toute donnée utile. Il permet la transmission fiable d’informations sur un canal de transmission bruité, en permettant au destinataire de demander la retransmission d’éventuels paquets erronés ou eﬀacés, via notamment l’envoi de paquets ACK ou NACK. Dans le modèle OSI, il correspond à la couche transport, intermédiaire de la couche réseau et de la couche session.
Le protocole que nous utilisons pour transmettre de l’information via la diode Elips-SD est donc le protocole UDP. Le protocole TCP ne peut absolument pas être utilisé pour fiabiliser une transmission transitant par une diode réseau, puisqu’il repose sur l’envoi par le récepteur de paquets à l’émetteur, ce que la diode interdit. D’autres raisons peuvent interdire l’emploi d’un tel protocole :
— Le canal de retour peut ne pas exister (c’est le cas dans les liaisons satellitaires unidi-rectionnelles [11]).
— Dans le cas d’une transmission multicast ou broadcast [10], le nombre de destinataires peut poser problème. Chaque récepteur subit des pertes diﬀérentes, et retransmettre séparément à chacun d’eux reviendrait à retransmettre toute l’information.
— Si le temps de latence de la transmission est important, il peut être contraignant d’utiliser le protocole TCP : il se peut en eﬀet qu’on ait à redemander de nombreuses fois un paquet avant de le recevoir. Dans certains cas, la perte d’un paquet n’est pas nécessairement problématique, mais dans le cas de données chiﬀrées, un seul paquet eﬀacé conduit géné-ralement à une grande quantité d’information non-exploitable. Dans le cadre de futures transmissions spatiales, le temps de latence sera très important, et il faudra sûrement avoir recours à des codes correcteurs pour réduire le nombre d’itérations nécessaires au protocole TCP : cette problématique est notamment étudiée dans [11].
Exemple 2 : distribution de données Dans le cas ou un émetteur unique souhaite dis-tribuer de l’information à de nombreux destinataires, tout en ne sachant pas quand ceux-ci seront disponibles, il est possible d’adopter la solution du broadcast disk, ou disque de diﬀusion à grande échelle en français [5]. Le principe est de transmettre en boucle l’information afin que des récepteurs subissant beaucoup de pertes, ou ayant à se déconnecter, puissent reconstituer l’information. Ce type de solution a cependant un coût de réception important, correspondant à la quantité d’information reçue en double. Un récepteur qui n’aura pas reçu le dernier pa-quet émis devra attendre que l’émetteur ait émis tous les autres paquets avant de l’obtenir. Ce coût pour les récepteurs peut être réduit grâce à l’emploi d’un code correcteur. L’ajout de redondance permet alors au récepteur d’exploiter le contenu diﬀusé dès qu’il aura reçu assez d’information. Dans ce cas de figure, les codes à eﬀacements sans rendement utilisés comme une “fontaine numérique”, [12] que nous décrivons par la suite, peuvent s’avérer performants et adaptés.
Exemple 3 : stockage de données distribué Dans le cas du stockage distribué, les données peuvent être stockées à plusieurs endroits diﬀérents. Cette répartition a plusieurs objectifs :
— garantir que les données sont disponibles, même en cas de panne de certaines unités de stockage et minimiser la l’information totale nécessaire à leur émission ( [62]).
— diminuer le temps nécessaire à la récupération des données, en demandant à plusieurs unités de stockage de les transmettre séparément.
La méthode la plus simple consiste à dupliquer les données sur plusieurs supports de données. Cependant, ceci nécessite une importante consommation mémoire au total, pour une qualité de service assez faible. Supposons par exemple qu’on dispose d’une base de donnée d’1 teraoctet, et de 10 sites de stockages. Une solution sans code correcteur consisterait à répliquer la base de donnée entière sur les 10 sites, ce qui représentera 10 teraoctets au total. La solution avec code à eﬀacements consiste à appliquer un code correcteur sur cette base de donnée, puis à répartir l’information obtenue sur les 10 sites. La quantité d’information totale est alors nécessairement supérieure à 1 teraoctet, mais peut être inférieure à 10 teraoctets, tout en restant tolérante à la panne d’un ou plusieurs de ces sites (suivant la taille et la dimension du code utilisé).

Codes correcteurs

Nous savons grâce aux travaux de Claude Shannon parus en 1948 [53] qu’il est possible de transmettre de l’information sur un canal bruité via l’utilisation d’un codage adéquat. Dans un premier temps, nous entendrons par erreurs les altérations ou eﬀacements subis par les messages transmis. Le code que nous présentons dans cette thèse est un code à eﬀacements, par la suite nous nous concentrerons donc sur les eﬀacements uniquement.

Définitions

Le code correcteur que nous présentons est un code à eﬀacements linéaire par bloc non-MDS systématique. Dans un premier temps, il convient de rappeler certaines notions et définitions inhérentes à la théorie des codes correcteurs.
Definition 6. On appelle corps fini (ou corps de Galois) un ensemble d’éléments pour lequel sont définies l’addition, la soustraction, la multiplication et la division. Pour tout entier premier p et entier m, il existe un unique corps fini à q = pm éléments, qu’on note GF (q) ou Fq.
Un code correcteur C est un ensemble de mots de longueur n, chaque mot étant une suite de n symboles appartenant à un corps fini GF (q) (qu’on peut aussi appeler alphabet). Ces mots sont obtenus grâce à une application , que l’on applique à un ensemble de mots sources plus courts à k symboles, k n. Le code correcteur que nous présentons est un code linéaire systématique par bloc. Cette famille de codes correcteurs possède une structure d’espace vectoriel, ce qui en fait des codes pratiques à utiliser.
Definition 7. On appelle code C de dimension k et de longueur n un sous-espace vectoriel de dimension k de l’espace vectoriel Fnq. On dit du code C qu’il est un [n; k] code, et on appelle ses éléments les mots du code C.
On appelle mot de longueur n sur l’alphabet A une suite de n symboles appartenant à l’alphabet A. L’architecture des ordinateurs reposant sur le bit, nous utiliserons la plupart du temps le corps F2m. Dans le cas particulier de Fn2, l’addition et la soustraction reviennent à l’opération XOR bit à bit. On appelle symboles (ou lettres) les éléments du corps fini sur lequel travaille le code. Ces éléments forment les mots du code. L’ensemble des symboles peut être appelé un alphabet.
Definition 8. On appelle rendement d’un [n; k] code C de dimension k et de longueur n le rapport R = k=n.
Plus ce ratio est proche de 0, plus le code possède de redondance, et inversement, plus il est proche de 1, moins il en possède.
Definition 9. On appelle encodage une application de l’ensemble GF (qk) dans GF (qn), qui permet d’obtenir les mots de longueur n du code à partir des mots sources de longueur k.
Les codes correcteurs se diﬀérencient suivant leur fonction d’encodage , ayant des com-plexités calculatoires diﬀérentes, et oﬀrant au code une capacité de correction plus ou moins grande. Definition 10. On appelle matrice génératrice d’un code la matrice de l’application linéaire de l’encodage Fkq dans Fnq dont l’image est le code.
Les lignes de la matrice génératrice G 2 M(Fq)k;n forment une base de l’espace vectoriel du code. Soit X un élément de Fkq et G la matrice génératrice d’un [n; k] code. X est encodé en un mot de code Y 2 Fnq comme ceci : Y = XG. Lorsque le mot source se retrouve dans le mot encodé, on parle alors de code systématique. La matrice génératrice d’un code systématique contient alors la matrice identité. Si le code est systématique de dimension k et de longueur n, et que par conséquent sa matrice génératrice Gsystmatique contient la matrice identité Idk, on peut alors noter Gsystmatique = [IdkjC].
Definition 11. Soit C un [n; k] code. On dit que H 2 M(Fq)(n k);n est une matrice de parité de C si et seulement si 8X 2 C; HX = 0 et H est de rang plein.
L’application correspondant à cette matrice a comme noyau les éléments du code. On peut obtenir la matrice de parité H d’un code systématique à partir de sa matrice génératrice G de la façon suivante : H = [ HT jIdn k]:
En eﬀet, soit Y 2 C un mot du code C :
HY T = H(XG)T
= HGT XT
= fIdkjCgT XT
= CT + CTXT = 0:
Le décodage d’un code correcteur ayant pour but de retrouver le mot X le plus probablement envoyé (et donc le plus proche du mot reçu Y ), il est nécessaire d’introduire une notion de dis-tance entre mots. Cette distance, appelée distance de Hamming, découle du poids de Hamming. Quand l’alphabet est le corps F2, le poids de Hamming d’un mot est alors le nombre de 1 dans ce mot (le nombre de bits égaux à 1 de ce mot).
Definition 12. Le poids de Hamming d’un mot X est le nombre de symboles de X diﬀérents du symbole nul. La distance de Hamming entre deux mots X et Y est le nombre de positions auxquelles les symboles de ces mots diﬀèrent. Ainsi, la distance entre deux mots X et Y est égale au poids de Hamming de X Y .
La notion de distance de Hamming nous amène à nous intéresser à la distance séparant les mots d’un code, et plus particulièrement à la plus petite distance possible entre deux mots du code. On appelle cette distance la distance minimale du code, souvent notée dmin. Dans le cas des codes linéaires, cette distance est aussi le minimum des poids des mots non-nuls du code.
Un [n; k] code de distance minimale d sera noté [n; k; d] code. Les capacités de correction d’un code linéaire dépendent fortement de sa distance minimale. Celle-ci nous donne une borne sur le nombre de correction garanties par le code. Un code correcteur de distance minimale dmin permet de corriger un mot si dmin 2t + e + 1, avec t le nombre d’erreurs et e le nombre d’eﬀacements subis par ce mot. Cette distance minimale possède une borne, appelée borne de Singleton [55], qui dépend de la longueur et de la dimension du code : dmin n k + 1. Les codes dont la distance minimale atteint cette borne, appelés des codes MDS, pour Maximum Distance Separable, possèdent une capacité de correction optimale.
Definition 13. Un [n; k; d] code est dit MDS (pour Maximum Distance Separable) si et seulement si
n k = d 1
On dit que ce code atteint la borne de Singleton.
Exemple : code à répétitions Pour récapituler les définitions énoncées précédemment, appliquons les à un code correcteur simple : le code à répétition. Supposons qu’on souhaite transmettre des mots (ou messages) de longueur k = 1 seul symbole, avec des symboles ap-partenant à F32, en envoyant chaque symbole 2 fois. Les mots transmis sont alors de longueur n = 2k = 2, et le code est alors un [2; 1] code linéaire, de dimension k = 1 et de longueur n = 2.
La distance minimale dmin de ce code est 2, car pour toute paire (X; Y ) de deux mots diﬀérents du code, le poids de Hamming de X Y est de 2. En eﬀet, comme on peut le voir dans la table [1.1] les mots 011 011 et 101 101 ont deux symboles qui diﬀèrent, leur distance de Hamming est donc de 2. Elle correspond aussi au poids le plus faible parmi les mots non-nuls du code, or tous les mots de notre code ont un poids de 2, à l’exception de 000 000. Ce code est donc un [2; 1; 2] code. Il n’atteint pas la borne de Singleton et est donc non-MDS, car n k 6= d 1. Ce code à répétition saura décoder convenablement un mot X transmis et devenu le mot Y , si X a subi t erreurs et e eﬀacements, avec 2 2t + e + 1. Il saura donc décoder un mot ayant subi un unique eﬀacement, mais ne saura pas décoder un mot ayant subi une erreur, ou plus de un eﬀacement.
La matrice génératrice G de ce code est : (11), et sa matrice de parité M est (1). Le code à répétition est un code systématique, car chaque mot source se retrouve dans le mot code lui correspondant.

Codes à eﬀacements

Cette thèse présente un code correcteur pour le canal à eﬀacements tel que présenté dans la figure [1.2]. Dans un premier temps nous présentons le principe général sur lequel reposent l’utilisation et le fonctionnement de ces codes. Prenons l’exemple suivant : nous souhaitons transmettre k symboles sur un canal à eﬀacements dont la probabilité d’eﬀacements vaut p. Definition 14. On appelle probabilité d’eﬀacements p la probabilité qu’un symbole transmis sur un canal soit eﬀacé.
Afin de fiabiliser convenablement cette transmission, nous devons choisir correcteur dont le rendement R est inférieur à la capacité 1 p du canal.
Tout d’abord, nous allons encoder les k symboles du message sources en n k symboles codes. Ces n symboles peuvent alors être transmis. p n symboles vont en moyenne être eﬀacés, et le récepteur disposera alors de (1 p) n paquets.
Si le récepteur a à sa disposition k paquets ou plus, il a une chance de décoder les symboles eﬀacés et de reconstruire le message original. A contratio, le décodage échoue automatiquement si le récepteur dispose de moins de k paquets.

Codage par paquets

Les codes à eﬀacements travaillent généralement sur les paquets fournis d’un protocole de transmission. Les codes corrigeant des altérations de données s’exécutent sur des petites quan-tités d’information (quelques milliers de bits), les codes à eﬀacements travaillent sur des mots pouvant atteindre plusieurs mégaoctets. En général, on les utilise juste en dessous de la couche application, là où les unités de données transmises sont grandes (paquets IP). On les appelle donc souvent codes correcteurs de niveau applicatif (ou codes AL-FEC) pour “Application-Level Forward Error Correction”. Ils protéger des ensembles de données divisées en paquets. Le code correcteur et la manière dont le code organise et encode les données est appelé un code AL-FEC.
Nous avons vu précédemment que ces paquets ont des tailles qui peuvent atteindre plu-sieurs milliers d’octets, et que rien ne garantit qu’ils aient tous la même taille. Dans le cas de paquets ayant diﬀérentes tailles, on pourra se rapporter au cas des paquets de taille constante en utilisant du padding (remplissage des paquets avec des 0 pour leur faire atteindre la taille désirée). Néanmoins, cette méthode impose d’avoir recours à de l’information inutile, ce que nous chercherons à éviter : idéalement, on préférera travailler directement sur des paquets ayant la taille adéquat. A partir de maintenant nous considérerons que les paquets d’un même bloc ont tous la même taille.

Table des matières

Introduction
1 Transmissions et codes correcteurs
1.1 Généralités
1.1.1 Canal de communication
1.1.2 Canal binaire à effacements
1.1.3 Canal à effacements de paquets
1.2 Codes correcteurs
1.2.1 Définitions
1.2.2 Codes à effacements
1.2.3 Codage par paquets
1.2.4 Équivalence symboles-paquets
1.3 Evaluation des codes correcteurs
1.3.1 Probabilité d’erreur de décodage
1.3.2 Métriques associées à l’efficacité d’un code correcteur
1.3.3 Terminologie associée aux probabilités d’erreur
1.3.4 Complexité algorithmique
1.3.5 Méthodes d’évaluation des performances d’un code
1.4 Codes MDS
1.4.1 Codes Reed-Solomon pour le canal à effacements
1.4.2 Matrices de Vandermonde
1.5 Codes LDPC
1.5.1 Représentation des codes LDPC
1.5.2 Encodage des codes LDPC
1.5.3 Décodage des codes LDPC
1.6 Codes sans rendement
1.6.1 Codes LT
1.6.2 Distribution des degrés
2 Faux traut
2.1 Introduction
2.1.1 Cas d’utilisation et motivations
2.1.2 Définitions
2.2 Pseudo-codes
2.3 Analyse théorique
2.3.1 Complexité algorithmique de l’encodage
2.3.2 Complexité algorithmique du décodage
2.3.3 Complexité linéaire
2.3.4 Analyse de la capacité de correction
2.4 Simulations
2.4.1 Simulations de l’encodage
2.4.2 Simulations du décodage
2.4.3 Capacité de correction
2.5 Canal à erreurs et théorème des restes Chinois
2.5.1 Adaptation au canal à erreurs
2.5.2 Limitations de cette méthode
3 Optimisation, graphes et calcul modulaire
3.1 PPCM maximal d’un ensemble dont la somme est fixée
3.1.1 Fonction de Landau
3.1.2 Simulations de décodage avec la méthode de Landau
3.1.3 PPCM maximal d’un ensemble dont la somme et le cardinal sont fixés : algorithme brute force
3.1.4 Simulations de décodage avec la méthode brute-force
3.1.5 Conclusion
3.2 Enumération de forêts dans les graphes bipartis et capacité de correction
3.2.1 Système d’équations et graphe de Rook
3.2.2 Graphe de Rook et probabilité exacte d’erreur du décodage – Algorithme de Stones
3.2.3 Calculs exacts et formules closes par interpolation
3.2.4 Comparaisons entre théorie et simulations
3.3 Forêts couvrantes et application aux transmissions bidirectionnelles
3.3.1 Graphes bipartis, Forets couvrantes et retransmission minimale
3.3.2 HARQ – Hybrid Automatic Repeat reQuest
3.3.3 Protocole HARQ et Fauxtraut
3.3.4 Résultats expérimentaux
4 Allocation de ressources temporelles et couplages
4.1 Couplage temporel
4.2 Algorithme d’approximation
4.3 Algorithme de kernelisation
4.4 Etude numérique
4.4.1 Jeux de données
4.4.2 Hypothèse de test
4.4.3 Résultats
4.4.4 Discussion
4.5 Conclusion et perspectives
Conclusion