Netværkskodning

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. oktober 2016; checks kræver 2 redigeringer .

Netværkskodning  er en gren af ​​informationsteori, der studerer spørgsmålet om optimering af datatransmission over et netværk ved hjælp af teknikker til at ændre datapakker på mellemliggende knudepunkter.

Grundlæggende om netværkskodning

For at forklare principperne for netværkskodning, brug eksemplet med et sommerfuglenetværk, foreslået i det første arbejde om netværkskodning "Netværksinformationsflow" [1] . Overvej netværket vist i figuren, hvor der er en eller to kilder, der genererer pakker A og B, der ankommer til input til sommerfuglenetværket. De første knudepunkter, der er ansvarlige for at transmittere information, sender hver en pakke (A til venstre og B til højre) ved indgangen til modtagernes slutknudepunkter. De sender også disse pakker til en mellemliggende node, som i stedet for at sende to pakker på skift (og spilde tid), kombinerer disse pakker, for eksempel ved hjælp af XOR- operationen og sender videre.

Destinationsnoder har evnen til at gendanne de originale pakker fra information om en enkelt modtaget pakke og en kombination af dem. Som et resultat heraf øges netværksgennemstrømningen - to pakker kan transmitteres til to modtagere samtidigt (for hver cyklus), selvom den minimale netværkssektion kun indeholder tre datatransmissionskanaler.

Tilfældig netværkskodning

I modsætning til statisk netværkskodning, når modtageren kender alle de manipulationer, der udføres med pakken, overvejes spørgsmålet om tilfældig netværkskodning også, når denne information er ukendt. Forfatterskabet til de første værker om dette emne tilhører Kötter, Krzyszang og Silva [2] . Denne tilgang kaldes også netværkskodning med tilfældige koefficienter - når koefficienterne under hvilke de indledende pakker transmitteret af kilden vil blive inkluderet i de resulterende pakker modtaget af modtageren, med ukendte koefficienter, der kan afhænge af den aktuelle netværksstruktur og endda af tilfældig beslutninger truffet på mellemliggende knudepunkter.

Hovedmetoden er inklusion i den transmitterede pakke af yderligere information, der identificerer pakken inden for en bestemt session (det antages, at pakker, der kun tilhører én session, kan kombineres). Det kunne for eksempel være et simpelt bitfelt. For sommerfuglenetværket diskuteret ovenfor kan dette bitfelt bestå af to bits for hver pakke:

Pakke bit felt
ti
0 1
elleve

Den første modtager vil modtage to pakker med bitfelterne "1 0" og "1 1", den anden modtager vil modtage "0 1" og "1 1". Ved at bruge dette felt som information om koefficienterne for den lineære ligning for pakkerne, kan modtageren gendanne de originale pakker, hvis de blev transmitteret uden fejl.

Beskyttelse af information mod forvrængning

Til ikke-tilfældig netværkskodning kan standard anti-jamming og anti-aliasing-teknikker, der bruges til simpel transmission af information over et netværk, bruges. Men som bemærket i artiklen "LDPC-kodningsskemaer for fejl" [3] , har pakker gendannet fra lineære kombinationer en højere sandsynlighed for at blive modtaget med en fejl, da de påvirkes som en fejlsandsynlighed i to pakker, der bruges til informationsgendannelse kl. enkelt gang.

I betragtning af "sommerfuglenetværket" kan det påvises, at for den første modtager er sandsynligheden for at modtage en pakke uden fejl større end for pakken , selvom vi antager samme, men ikke-nul, fejlsandsynligheder i de modtagne pakker og .

For at reducere denne effekt foreslår forfatterne at ændre metoden til iterativ afkodning af pakker A og B (for eksempel ved hjælp af LDPC- kodning), når pakkeafkodningsiterationer udføres samtidigt, og dekodere udveksler information om fejlsandsynlighederne i en specifik pakke stykker. For helt at slippe af med denne effekt, foreslår forfatterne også at opdele kildepakkerne i flere dele og overføre dem på forskellige måder. Som det numeriske eksperiment viste, udligner dette virkelig sandsynligheden for pakkeafkodning.

Metoderne, der anvendes til afkodning i tilfældig netværkskodning, betragter alle modtagne pakker som et enkelt objekt (ofte en matrix) bygget fra de modtagne rækkepakker. Hvis den første del af pakken er et bitfelt, reduceres operationer med matrixen for det første til at bringe dens venstre side til en diagonal form (ved at bruge Gauss-metoden ), og derefter til at korrigere fejl i højre side af matrixen . For at rette fejl kan der bruges rangkoder , som ikke kun kan rette fejl i matrixens kolonner (på grund af forkert modtagne databits), men også fejl i rækkerne i matrixen (på grund af transmissionsfejl i bitfeltet) .

Noter

  1. ↑ Ahlswede, R.; Ning Cai; Li, S.-YR; Yeung, RW, " Network information flow ", Information Theory, IEEE Transactions on, vol. 46, nr. 4, s. 1204-1216, juli 2000
  2. ↑ Artikler
    • Koetter R., Kschischang FR Kodning for fejl og sletninger i tilfældig netværkskodning// IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007.- S. 791-795.
    • Silva D., Kschischang FR Brug af rang-metriske koder til fejlkorrektion i tilfældig netværkskodning // IEEE International Symposium on Information Theory. Proc. ISIT-07. – 2007.
    • Koetter R., Kschischang FR Kodning for fejl og sletninger i tilfældig netværkskodning // IEEE Transactions on Information Theory. - 2008 - V. IT-54, N.8. - P. 3579-3591.
    • Silva D., Kschischang FR, Koetter R. A Rank-Metric Approach to Error Control in Random Network Coding // IEEE Transactions on Information Theory.- 2008- V. IT-54, N. 9.- P.3951-3967.
  3. ↑ Kang J., Zhou B., Ding Z., Lin S. LDPC-kodningsskemaer til fejlkontrol i et multicast-netværk

Se også