Netværkskodning

Foshammer, Louise ; Neve-Græsbøll, Malte

4. semester

Matematik, Kandidat

2014

2014-06-10

138

Dette projekt undersøger netværkskodning, en metode hvor datapakker kombineres undervejs i netværket for at udnytte kapaciteten bedre og gøre overførsler mere robuste. Vi fokuserer først på lineær multicast-netværkskodning, hvor den samme information skal nå flere modtagere. Her gennemgår vi grundlæggende teori, beskriver hvornår problemet kan løses, og vurderer sandsynligheden for at en løsning opstår, når indkodningskoefficienterne (de vægte, der kombinerer pakker) vælges tilfældigt. Dernæst undersøger vi, hvordan man beskytter sig mod fejl og tab af pakker. Vi bruger Kötter–Kschischang-koder, som kan rette fejl, der opstår i netværket, og genskabe indholdet, selv hvis enkelte datapakker forsvinder. Herefter ser vi på lineære koder i mere generelle netværk og præsenterer en metode baseret på Gröbnerbaser, et værktøj fra beregningsalgebra, der kan afgøre, om der overhovedet eksisterer en lineær løsning til et givet netværkskodningsproblem. Til sidst behandler vi situationer, hvor lineær netværkskodning ikke er tilstrækkelig. Vi opstiller begrænsninger og krav til de enkelte indkodningspunkter og undersøger, om man ved tilfældigt valg af funktioner fra forskellige funktionsklasser kan finde løsninger i sådanne netværk.

This project studies network coding, a technique where data packets are combined inside the network to use capacity more efficiently and improve reliability. We first focus on linear multicast network coding, where the same information must reach multiple receivers. We introduce the basic theory, explain when the problem is solvable, and analyze the likelihood that a solution is found when the encoding coefficients (the weights used to combine packets) are chosen at random. We then examine how to protect against errors and packet losses. We use Kötter–Kschischang codes, which can correct errors introduced by the network and recover the message even if some packets are lost. Next, we consider linear codes in more general networks and present a method based on Gröbner bases, a tool from computational algebra, to determine whether a linear solution exists for a given network coding problem. Finally, we study cases where linear network coding is not sufficient. We set constraints and requirements for individual encoding points and explore whether randomly selecting functions from different function classes can yield solutions in such networks.

[Dette resumé er genereret ved hjælp af AI]

Download
Vis denne rapport i AAU Studenterprojekter