Codage de réseau linéaire

En informatique , le codage réseau linéaire est un programme dans lequel les nœuds intermédiaires transmettent des données des nœuds sources aux nœuds puits au moyen de combinaisons linéaires .

Le codage réseau linéaire permet d'améliorer le débit, l'efficacité et l'évolutivité d'un réseau , tout en réduisant les attaques et l'écoute clandestine. Les nœuds du réseau reçoivent plusieurs paquets qui sont ensuite combinés pour la transmission. Ce processus permet d'optimiser le flux d'informations au sein du réseau .

Il a été démontré que, théoriquement, le codage linéaire suffit à atteindre la borne supérieure dans les problèmes de multidiffusion à une source. Cependant, le codage linéaire n'est pas suffisant en général, même pour des versions plus générales de la linéarité telles que le codage convolutionnel et le codage par bancs de filtres . Trouver des solutions de codage optimales pour les problèmes de réseau généraux avec des exigences arbitraires est un problème difficile, qui peut être NP-difficile et même indécidable .

Dans un problème de codage réseau linéaire, un groupe de nœuds est chargé de déplacer les données des nœuds sources vers les nœuds cibles. Chaque nœud génère de nouveaux paquets qui sont des combinaisons linéaires des paquets précédemment reçus, en les multipliant par des coefficients choisis dans un corps fini , généralement de taille .

Plus formellement, chaque nœud, de degré entrant , , génère un message à partir de la combinaison linéaire des messages reçus selon la formule :

Les valeurs sont des coefficients sélectionnés dans . Les opérations étant calculées dans un corps fini, le message généré a la même longueur que les messages originaux. Chaque nœud transmet la valeur calculée ainsi que les coefficients , utilisés au niveau .

Les nœuds de destination reçoivent ces messages codés sur le réseau et les regroupent dans une matrice. Les messages originaux peuvent être récupérés en effectuant une élimination de Gauss sur la matrice. Sous forme échelonnée réduite, les paquets décodés correspondent aux lignes de la matrice.

Un réseau est représenté par un graphe orienté . est l'ensemble des nœuds (ou sommets), est l'ensemble des liens orientés (ou arêtes), et donne la capacité de chaque lien de . Soit le débit maximal possible du nœud au nœud . D'après le théorème du flot maximal et de la coupe minimale , est majoré par la capacité minimale de toutes les coupes , qui est la somme des capacités des arêtes d'une coupe, entre ces deux nœuds.

Karl Menger a démontré qu'il existe toujours un ensemble de chemins arêtes-disjoints atteignant la borne supérieure dans un contexte de diffusion unique , un phénomène connu sous le nom de théorème du flot maximal et de la coupe minimale . Par la suite, l' algorithme de Ford-Fulkerson a été proposé pour trouver de tels chemins en temps polynomial. Enfin, Edmonds a démontré dans l'article « Edge-Disjoint Branchings » que la borne supérieure est également atteignable dans le contexte de la diffusion et a proposé un algorithme polynomial.

Cependant, la situation est plus complexe dans le cas du multicast , et il est impossible d'atteindre une telle limite supérieure avec les méthodes de routage traditionnelles . Ahlswede et al. ont démontré qu'elle est réalisable si des tâches de calcul supplémentaires (regroupement des paquets entrants en un ou plusieurs paquets sortants) sont effectuées au niveau des nœuds intermédiaires.

Le réseau papillon est souvent utilisé pour illustrer comment le codage réseau linéaire peut surpasser le routage . Deux nœuds sources (en haut de l'image) possèdent des informations A et B qui doivent être transmises aux deux nœuds de destination (en bas). Chaque nœud de destination souhaite connaître à la fois A et B. Chaque arête ne peut transporter qu'une seule valeur (on peut imaginer une arête transmettant un bit à chaque intervalle de temps).

Si seul le routage était autorisé, la liaison centrale ne pourrait transporter que A ou B, mais pas les deux. Supposons que l'on envoie A via la liaison centrale : la destination de gauche recevrait A deux fois et ignorerait totalement B. L'envoi de B pose un problème similaire pour la destination de droite. On dit que le routage est insuffisant car aucun système de routage ne peut transmettre A et B simultanément aux deux destinations. Par ailleurs, il faut au total quatre intervalles de temps pour que les deux nœuds de destination reçoivent la connaissance de A et B.

Grâce à un code simple, comme illustré, A et B peuvent être transmis simultanément aux deux destinations en envoyant la somme des symboles via les deux nœuds relais – A et B étant encodés selon la formule « A+B ». La destination de gauche reçoit A et A+B, et peut calculer B en soustrayant les deux valeurs. De même, la destination de droite reçoit B et A+B, et peut également déterminer A et B. Ainsi, grâce au codage réseau, la transmission ne nécessite que trois intervalles de temps et améliore le débit.

Le codage réseau linéaire aléatoire (RLNC) est un schéma de codage simple mais performant qui, dans les systèmes de transmission par diffusion, permet d'atteindre un débit quasi optimal grâce à un algorithme décentralisé. Les nœuds transmettent des combinaisons linéaires aléatoires des paquets reçus, dont les coefficients sont choisis aléatoirement selon une distribution uniforme d'un corps de Galois . Si la taille du corps est suffisamment grande, la probabilité que le ou les récepteurs obtiennent des combinaisons linéairement indépendantes (et donc des informations nouvelles) tend vers 1. Il convient toutefois de noter que, malgré d'excellentes performances de débit, si un récepteur ne reçoit pas suffisamment de paquets, il est extrêmement improbable qu'il puisse récupérer les paquets originaux. Ce problème peut être résolu en envoyant des combinaisons linéaires aléatoires supplémentaires jusqu'à ce que le récepteur reçoive le nombre de paquets requis.

There are three key parameters in RLNC. The first one is the generation size. In RLNC, the original data transmitted over the network is divided into packets. The source and intermediate nodes in the network can combine and recombine the set of original and coded packets. The original

The sources and the intermediate nodes can combine any subset of the original and previously coded packets performing linear operations. To form a coded packet in RLNC, the original and previously coded packets are multiplied by randomly chosen coefficients and added together. Since each packet is just an appended set of Galois field elements, the operations of multiplication and addition are performed symbol-wise over each of the individual symbols of the packets, as shown in the picture from the example.

To preserve the statelessness of the code, the coding coefficients used to generate the coded packets are appended to the packets transmitted over the network. Therefore, each node in the network can see what coefficients were used to generate each coded packet. One novelty of linear network coding over traditional block codes is that it allows the recombination of previously coded packets into new and valid coded packets. This process is usually called recoding. After a recoding operation, the size of the appended coding coefficients does not change. Since all the operations are linear, the state of the recoded packet can be preserved by applying the same operations of addition and multiplication to the payload and the appended coding coefficients. In the following example, we will illustrate this process.

Tout nœud de destination doit collecter suffisamment de paquets codés linéairement indépendants pour pouvoir reconstituer les données originales. Chaque paquet codé peut être assimilé à une équation linéaire dont les coefficients sont connus puisqu'ils sont ajoutés au paquet. Dans ces équations, chaque paquet original représente l'inconnue. Pour résoudre le système d'équations linéaires, la destination a besoin d'au moins équations (paquets) linéairement indépendants.

La figure illustre la combinaison linéaire de deux paquets en un nouveau paquet codé. Dans cet exemple, nous avons deux paquets, nommés paquet et paquet . La taille de la génération est de deux. Ceci est dû au fait que chaque paquet se voit ajouter deux coefficients de codage ( ). Ces coefficients peuvent prendre n'importe quelle valeur du corps de Galois. Cependant, un paquet de données non codé d'origine aurait ajouté les coefficients de codage ou , ce qui signifie qu'il est construit par une combinaison linéaire de zéro fois l'un des paquets et une fois l'autre. Tout paquet codé se verra ajouter d'autres coefficients. Dans notre exemple, le paquet , par exemple, a ajouté les coefficients . Le codage réseau pouvant être appliqué à n'importe quelle couche du protocole de communication , ces paquets peuvent contenir un en-tête provenant d'autres couches, qui est ignoré lors des opérations de codage réseau.

Supposons maintenant que le nœud du réseau souhaite produire un nouveau paquet codé combinant les paquets A et B. Dans RLNC, il choisira aléatoirement deux coefficients de codage, α et β dans cet exemple. Le nœud multipliera chaque symbole du paquet A par α , et chaque symbole du paquet B par β . Ensuite, il additionnera les résultats symbole par symbole pour produire les nouvelles données codées. Il effectuera les mêmes opérations de multiplication et d'addition sur les coefficients de codage des paquets codés.

Le codage de réseaux linéaires est encore un domaine relativement récent. Cependant, il a fait l'objet de nombreuses recherches au cours des vingt dernières années. Néanmoins, certaines idées reçues persistent et ne sont plus valables :

Complexité de calcul du décodage : Les décodeurs de codage réseau ont été améliorés au fil des ans. Aujourd’hui, les algorithmes sont très efficaces et parallélisables. En 2016, avec les processeurs Intel Core i5 dotés des instructions SIMD , le débit utile de décodage du codage réseau était de 750 Mo/s pour une génération de 16 paquets et de 250 Mo/s pour une génération de 64 paquets .

Surcharge de transmission : On considère généralement que la surcharge de transmission du codage réseau est importante en raison de la nécessité d'ajouter les coefficients de codage à chaque paquet codé. En réalité, cette surcharge est négligeable dans la plupart des applications. La surcharge due aux coefficients de codage peut être calculée comme suit : chaque paquet se voit ajouter des coefficients de codage. La taille de chaque coefficient correspond au nombre de bits nécessaires pour représenter un élément du corps de Galois. En pratique, la plupart des applications de codage réseau utilisent une taille de génération n'excédant pas 32 paquets et des corps de Galois de 256 éléments (binaire-8). Dans ces conditions, chaque paquet nécessite 32 octets de surcharge. Si chaque paquet mesure 1 500 octets (soit la MTU Ethernet), alors 32 octets représentent une surcharge de seulement 2 %.

Surcharge due aux dépendances linéaires : Puisque les coefficients de codage sont choisis aléatoirement en RLNC, il est possible que certains paquets codés transmis soient inutiles à la destination, car ils sont formés à partir d'une combinaison de paquets linéairement dépendants. Cependant, cette surcharge est négligeable dans la plupart des applications. Les dépendances linéaires dépendent de la taille des corps de Galois et sont pratiquement indépendantes de la taille de génération utilisée. Prenons l'exemple suivant : supposons que nous utilisions un corps de Galois à éléments et une taille de génération de paquets. Si la destination n'a reçu aucun paquet codé, on dit qu'elle a degrés de liberté ; alors presque tous les paquets codés seront utiles et innovants. En fait, seul le paquet nul (composé uniquement de zéros dans les coefficients de codage) ne sera pas innovant. La probabilité de générer un paquet nul est égale à la probabilité que chaque coefficient de codage soit égal à l'élément nul du corps de Galois. Autrement dit, la probabilité d'un paquet non innovant est de . À chaque transmission innovante successive, on peut démontrer que l'exposant de la probabilité d'un paquet non innovant diminue d'une unité. Lorsque la destination a reçu des paquets innovants (c'est-à-dire qu'il ne lui manque plus qu'un paquet pour décoder intégralement les données), la probabilité d'un paquet non innovant est alors de l'ordre de . On peut utiliser cette information pour calculer le nombre moyen de paquets linéairement dépendants par génération. Dans le pire des cas, lorsque le corps de Galois utilisé ne contient que deux éléments ( ), le nombre moyen de paquets linéairement dépendants par génération est de 1,6 paquet supplémentaire. Si la taille de la génération est de 32 ou 64 paquets, cela représente une surcharge de 5 % ou 2,5 %, respectivement. Si l'on utilise le corps binaire 8 ( ), le nombre moyen de paquets linéairement dépendants par génération est pratiquement nul. Étant donné que ce sont les derniers paquets qui contribuent le plus à la surcharge due aux dépendances linéaires, certains protocoles basés sur RLNC, tels que le codage réseau clairsemé accordable , exploitent cette propriété. Ces protocoles introduisent de la sparsité (éléments nuls) dans les coefficients de codage au début de la transmission pour réduire la complexité du décodage, et réduisent la sparsité à la fin de la transmission pour réduire la surcharge due aux dépendances linéaires.

Au fil des ans, de nombreux chercheurs et entreprises ont intégré des solutions de codage réseau à leurs applications. Voici quelques exemples d'applications du codage réseau dans différents domaines :

• VoIP : Les performances des services de streaming tels que la VoIP sur les réseaux maillés sans fil peuvent être améliorées grâce au codage réseau en réduisant le délai et la gigue du réseau.
• Diffusion et visioconférence vidéo et audio Les performances du trafic MPEG-4 en termes de délai, de perte de paquets et de gigue sur les réseaux sans fil sujets aux pertes de paquets peuvent être améliorées grâce à RLNC. Dans le cas de la diffusion audio sur des réseaux maillés sans fil, le taux de livraison des paquets, la latence et la gigue du réseau peuvent être considérablement améliorés en utilisant RLNC au lieu de protocoles basés sur le transfert de paquets tels que le transfert multicast simplifié et l’élagage dominant partiel. Les améliorations de performances du codage réseau pour la visioconférence ne sont pas seulement théoriques. En 2016, les auteurs de ont mis en place un banc d’essai réel composé de 15 appareils Android sans fil afin d’évaluer la faisabilité des systèmes de visioconférence basés sur le codage réseau. Leurs résultats ont montré des améliorations importantes du taux de livraison des paquets et de l’expérience utilisateur globale, en particulier sur les liaisons de faible qualité, par rapport aux technologies de multidiffusion basées sur le transfert de paquets .
• Réseaux étendus définis par logiciel ( SD-WAN ) : Les grands réseaux sans fil IoT industriels peuvent tirer parti du codage réseau. Des chercheurs ont montré que le codage réseau et ses capacités de regroupement de canaux amélioraient les performances des SD-WAN comportant un grand nombre de nœuds avec de multiples connexions cellulaires. Aujourd’hui, des entreprises telles que Barracuda utilisent des solutions basées sur RLNC en raison de leurs avantages : faible latence, faible encombrement sur les équipements informatiques et faible surcharge.
• Agrégation de canaux : Grâce à ses caractéristiques d'absence d'état, RLNC permet d'effectuer efficacement l'agrégation de canaux, c'est-à-dire la transmission d'informations via plusieurs interfaces réseau. Les paquets codés étant générés aléatoirement et l'état du code étant transmis sur le réseau avec les paquets codés, une source peut réaliser l'agrégation sans planification complexe, simplement en envoyant des paquets codés via toutes ses interfaces réseau. La destination peut décoder les informations dès réception d'un nombre suffisant de paquets codés, quelle que soit l'interface réseau. Une vidéo illustrant les capacités d'agrégation de canaux de RLNC est disponible à l'adresse suivante :
• Réseaux privés 5G : La technologie RLNC peut être intégrée à la norme 5G NR afin d’améliorer les performances de la diffusion vidéo sur les systèmes 5G. En 2018, une démonstration présentée au Consumer Electronics Show a illustré un déploiement pratique de RLNC avec les technologies NFV et SDN pour améliorer la qualité vidéo face aux pertes de paquets dues à la congestion du réseau central.
• Collaboration à distance.
• Assistance et formation à distance en réalité augmentée .
• Applications de conduite de véhicules à distance.
• Réseaux de voitures connectées .
• Applications de jeu telles que la diffusion en continu à faible latence et la connectivité multijoueur.
• Applications dans le domaine de la santé.
• Industrie 4.0 .
• Réseaux satellitaires.
• Champs de capteurs agricoles.
• Réseaux de divertissement en vol.
• Mises à jour majeures de sécurité et de micrologiciel pour les gammes de produits mobiles.
• Infrastructures de villes intelligentes .
• Réseaux centrés sur l'information et réseaux de données nommées : Le codage réseau linéaire peut améliorer l'efficacité des réseaux centrés sur l'information en exploitant la nature multi-sources et multidiffusion de ces systèmes. Il a été démontré que le codage réseau linéaire peut être intégré à des réseaux de diffusion de contenu distribués tels que IPFS afin d'accroître la disponibilité des données tout en réduisant les ressources de stockage.
• Alternative à la correction d'erreurs sans voie de retour et aux demandes de répétition automatique dans les réseaux traditionnels et sans fil avec perte de paquets, comme le TCP codé et l'ARQ multi-utilisateur
• Protection contre les attaques réseau telles que l’espionnage, l’écoute clandestine, la relecture ou la corruption de données.
• Distribution de fichiers numériques et partage de fichiers P2P, par exemple le système de fichiers Avalanche de Microsoft
• Stockage distribué
• Augmentation du débit dans les réseaux maillés sans fil, par exemple : COPE , CORE , Routage sensible au codage , et BATMAN
• Réduction de la taille du tampon et du délai dans les réseaux de capteurs spatiaux : multiplexage du tampon spatial
• Diffusion sans fil : RLNC peut réduire le nombre de transmissions de paquets pour un réseau de multidiffusion sans fil à saut unique et ainsi améliorer la bande passante du réseau
• Partage de fichiers distribué
• Diffusion vidéo à faible complexité vers un appareil mobile
• Extensions de périphérique à périphérique