Optimisation et application du codage réseau dans l'architecture des futurs réseaux sans fils

Network coding (NC) is a new technique in which transmitteddata is encoded and decoded by the nodes of the network inorder to enhance throughput and reduce delays. Usingalgebraic algorithms, encoding at nodes accumulates varioustransmissions in fewer ones and decoding restores thesetransmissions. NC requires fewer transmissions to transmit allthe data but more processing at the nodes. NC can be appliedat any of the ISO layers. However, the focus is mainly on thenetwork layer level.In this work, we introduce novelties to the NC paradigm with theintent of building easy to implement NC protocols in order toimprove bandwidth usage, enhance QoS and reduce the impactof losing packets in lossy networks. Several challenges wereraised by this thesis concerning details in the coding anddecoding processes and all the related mechanisms used todeliver packets between end nodes. Notably, questions like thelife cycle of packets in coding environment, cardinality of codedmessages, number of byte overhead transmissions andbuffering time duration were inspected, analytically counted,supported by many theorems and then verified throughsimulations. When the packet loss problem was addressed,methods used in this thesis to closely investigate the behaviorof the network as a response to the loss led to the proposition ofnovel mechanisms to overcome this loss and to help reducingthe overhead caused by packet loss.In the first part of the thesis, an overview of NC is conductedsince triggered by the work of Alshwede et al. NC techniquesare then detailed with the focus on linear and binary NC. Thesetechniques are elaborated and embellished with examplesextracted from different scenarios to further help understandingthe advantages and disadvantages of each of these techniques.In the second part, a new address correlated NC (ACNC)protocol is presented and two approaches using ACNC protocolare introduced, the centralized approach where decoding isconducted at end nodes only and the distributed decodingapproach where each node in the network participates in thedecoding process. Centralized decoding is elaborated by firstpresenting its decision models and the detailed decoding at endnodes procedure. Moreover, the cardinality of received codedmessages and the buffering requirements at end nodes areinvestigated and the concepts of aging and maturity wereintroduced. The distributed decoding approach is presented asa solution to reduce the overhead on end nodes by distributingthe decoding process and buffering requirements tointermediate nodes.Loss and recovery in NC are examined for both centralized anddistributed approaches. For the centralized decoding approach,two mechanisms to limit the impact of loss are presented. Tothis effect, the concept of closures and covering sets areintroduced and the covering set discovery is conducted onundecodable messages to find the optimized set of packets torequest from the sender in order to decode all received packets.For the distributed decoding, a new hop-to-hop reliabilitymechanism is proposed that takes advantage of the NC itselfand depicts loss without the need of an acknowledgementmechanism.Le codage de réseau (CR) est une nouvelle technique reposant, sur la réalisation parles noeuds du réseau, des fonctions de codage et de décodage des données afin d’améliorerle débit et réduire les retards. En utilisant des algorithmes algébriques, le codageconsiste à combiner ensemble les paquets transmis et le décodage consiste à restaurerces paquets. Cette opération permet de réduire le nombre total de transmissions de paquetspour échanger les données, mais requière des traitements additionnels au niveaudes noeuds. Le codage de réseau peut être appliqué au niveau de différentes couches ISO.Toutefois dans ce travail, sa mise en noeuvre est effectuée au niveau de la couche réseau.Dans ce travail de thèse, nous présentons des techniques de codage de réseau s’appuyantsur de nouveaux protocoles permettant d’optimiser l’utilisation de la bande passante,d’améliorer la qualité de service et de réduire l’impact de la perte de paquets dans lesréseaux à pertes. Plusieurs défis ont été relevés notamment concernant les fonctions decodage/décodage et tous les mécanismes connexes utilisés pour livrer les paquets échangésentre les noeuds. Des questions comme le cycle de vie des paquets dans le réseau, lacardinalité des messages codés, le nombre total d’octets transmis et la durée du tempsde maintien des paquets ont été adressées analytiquement, en s’appuyant sur des théorèmes,qui ont été ensuite confirmés par des simulations. Dans les réseaux à pertes, lesméthodes utilisées pour étudier précisément le comportement du réseau conduisent à laproposition de nouveaux mécanismes pour surmonter cette perte et réduire la charge.Dans la première partie de la thèse, un état de l’art des techniques de codage de réseauxest présenté à partir des travaux de Alshwede et al. Les différentes techniquessont détaillées mettant l’accent sur les codages linéaires et binaires. Ces techniques sontdécrites en s’appuyant sur différents scénarios pour aider à comprendre les avantages etles inconvénients de chacune d’elles.Dans la deuxième partie, un nouveau protocole basé sur la corrélation des adresses(ACNC) est présenté, et deux approches utilisant ce protocole sont introduites ; l’approchecentralisée où le décodage se fait aux noeuds d’extrémités et l’approche distribuéeoù chaque noeud dans le réseau participe au décodage. Le décodage centralisé est élaboréen présentant d’abord ses modèles de décision et le détail du décodage aux noeuds d’extrémités.La cardinalité des messages codés reçus et les exigences de mise en mémoiretampon au niveau des noeuds d’extrémités sont étudiées et les notions d’âge et de maturitésont introduites. On montre que le décodage distribué permet de réduire la charge surles noeuds d’extrémité ainsi que la mémoire tampon au niveau des noeuds intermédiaires.La perte et le recouvrement avec les techniques de codage de réseau sont examinés pourles deux approches proposées. Pour l’approche centralisée, deux mécanismes pour limiterl’impact de la perte sont présentés. A cet effet, le concept de fermetures et le concept dessous-ensembles couvrants sont introduits. Les recouvrements optimaux afin de trouverl’ensemble optimal de paquets à retransmettre dans le but de décoder tous les paquetsreçus sont définis. Pour le décodage distribué, un nouveau mécanisme de fiabilité saut àsaut est proposé tirant profit du codage de réseau et permettant de récupérer les paquetsperdus sans la mise en oeuvre d’un mécanisme d’acquittement