Centralized and distributed addresscorrelated networkprotocols
Optimisation et application du codage réseau dans l'architecture des futurs réseaux sans fils
Résumé
Network coding (NC) is a new technique in which transmitted
data is encoded and decoded by the nodes of the network in
order to enhance throughput and reduce delays. Using
algebraic algorithms, encoding at nodes accumulates various
transmissions in fewer ones and decoding restores these
transmissions. NC requires fewer transmissions to transmit all
the data but more processing at the nodes. NC can be applied
at any of the ISO layers. However, the focus is mainly on the
network layer level.
In this work, we introduce novelties to the NC paradigm with the
intent of building easy to implement NC protocols in order to
improve bandwidth usage, enhance QoS and reduce the impact
of losing packets in lossy networks. Several challenges were
raised by this thesis concerning details in the coding and
decoding processes and all the related mechanisms used to
deliver packets between end nodes. Notably, questions like the
life cycle of packets in coding environment, cardinality of coded
messages, number of byte overhead transmissions and
buffering time duration were inspected, analytically counted,
supported by many theorems and then verified through
simulations. When the packet loss problem was addressed,
methods used in this thesis to closely investigate the behavior
of the network as a response to the loss led to the proposition of
novel mechanisms to overcome this loss and to help reducing
the overhead caused by packet loss.
In the first part of the thesis, an overview of NC is conducted
since triggered by the work of Alshwede et al. NC techniques
are then detailed with the focus on linear and binary NC. These
techniques are elaborated and embellished with examples
extracted from different scenarios to further help understanding
the 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 protocol
are introduced, the centralized approach where decoding is
conducted at end nodes only and the distributed decoding
approach where each node in the network participates in the
decoding process. Centralized decoding is elaborated by first
presenting its decision models and the detailed decoding at end
nodes procedure. Moreover, the cardinality of received coded
messages and the buffering requirements at end nodes are
investigated and the concepts of aging and maturity were
introduced. The distributed decoding approach is presented as
a solution to reduce the overhead on end nodes by distributing
the decoding process and buffering requirements to
intermediate nodes.
Loss and recovery in NC are examined for both centralized and
distributed approaches. For the centralized decoding approach,
two mechanisms to limit the impact of loss are presented. To
this effect, the concept of closures and covering sets are
introduced and the covering set discovery is conducted on
undecodable messages to find the optimized set of packets to
request from the sender in order to decode all received packets.
For the distributed decoding, a new hop-to-hop reliability
mechanism is proposed that takes advantage of the NC itself
and depicts loss without the need of an acknowledgement
mechanism.
Le codage de réseau (CR) est une nouvelle technique reposant, sur la réalisation par
les noeuds du réseau, des fonctions de codage et de décodage des données afin d’améliorer
le débit et réduire les retards. En utilisant des algorithmes algébriques, le codage
consiste à combiner ensemble les paquets transmis et le décodage consiste à restaurer
ces paquets. Cette opération permet de réduire le nombre total de transmissions de paquets
pour échanger les données, mais requière des traitements additionnels au niveau
des 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’appuyant
sur 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 les
réseaux à pertes. Plusieurs défis ont été relevés notamment concernant les fonctions de
codage/décodage et tous les mécanismes connexes utilisés pour livrer les paquets échangés
entre les noeuds. Des questions comme le cycle de vie des paquets dans le réseau, la
cardinalité des messages codés, le nombre total d’octets transmis et la durée du temps
de 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, les
méthodes utilisées pour étudier précisément le comportement du réseau conduisent à la
proposition 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éseaux
est présenté à partir des travaux de Alshwede et al. Les différentes techniques
sont détaillées mettant l’accent sur les codages linéaires et binaires. Ces techniques sont
décrites en s’appuyant sur différents scénarios pour aider à comprendre les avantages et
les 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’approche
centralisée où le décodage se fait aux noeuds d’extrémités et l’approche distribuée
où 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émoire
tampon 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 sur
les 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 pour
les deux approches proposées. Pour l’approche centralisée, deux mécanismes pour limiter
l’impact de la perte sont présentés. A cet effet, le concept de fermetures et le concept des
sous-ensembles couvrants sont introduits. Les recouvrements optimaux afin de trouver
l’ensemble optimal de paquets à retransmettre dans le but de décoder tous les paquets
reç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 paquets
perdus sans la mise en oeuvre d’un mécanisme d’acquittement.
Loading...