Network Coding

El Network coding (codificació en xarxa) és un camp de la teoria de la informació i la teoria de la codificació, també és un mètode per l'obtenció del màxim flux d'informació en una xarxa.

Història

Una xarxa és representada per un graf dirigit

G=(V,E,C).

On:

V és el conjunt de nodes o vèrtex,

E és el conjunt de enllaços o vores,

C són les capacitats en cada enllaç de E.

Sigui t(s,t) el que designi el rendiment (throughput) possible a partir del node s al node t. S'ha sabut per molt de temps que el límit superior de t(s,t) és la capacitat mínima de tots els talls, on és la suma de les capacitats de les vores en un tall, entre aquests dos nodes.

Karl Menger va demostrar que sempre hi ha un conjunt de vores-disjunts camins arribant al límit superior en un escenari unicast, conegut com el teorema min-tall màx-flux. Posteriorment l'algorisme Ford-Fulkerson va ser proposat per trobar aquests camins en un temps polinòmic. Després, Edmons va demostrar en el document “Edge-Disjoint Branchings” que el límit superior en l'escenari broadcast també és aconseguible, i va proposar un algorisme de temps polinòmic. La situació a l'escenari multicast és més complicat, i de fet, com un límit superior no pot ser aconseguit usant les idees de routing tradicionals. Ahlswede, et al. va demostrar que això pot ser aconseguit si les tasques de computació addicionals (els paquets rebuts són combinats amb un o diversos paquets de sortida) poden ser realitzades als nodes intermedis.

El 2003, Li, et al. va demostrar que la codificació linear és suficient per arribar al límit superior en els problemes multicast. El 2005, es va mostrar que la codificació linear no és suficient en general (múltiples fonts, “multisink” amb peticions arbitràries), fins i tot per les versions més generals de la linealitat com la codificació convolucional, codificació “filter-bank”,etc.

Network Coding Lineal

En un problema de Network Coding Lineal un grup de nodes $P$ estan involucrats en el moviment de dades dels nodes fonts $S$ als nodes receptors $K$. Cada node genera un paquet nou, que és una combinació lineal dels paquets que havia rebut anteriorment en l'enllaç, pels coeficients en un cos finit.

Un missatge generat $X_{k}$ està relacionat amb els missatges rebuts $M_{i}$ de la relació:

$X_{k}=\sum _{i=1}^{S}g_{k}^{i}\cdot M_{i}$

Cada node transmet el valor $X_{k}$ calculat juntament amb tots els coeficients utilitzats en el $k^{th}$ nivell, $g_{k}^{i}$.

Els valors $g_{k}^{i}$ són coeficients del camp de Galois $GF(2^{s})$. Atès que les operacions es calculen en el camp finit, el resultat de l'operació també és de la mateixa longitud, com la mida de cada vector de $M$.

Cada node produeix un resultat similar, com es va calcular anteriorment. Això produeix un problema lineal del tipus $X=GM$, on amb el coneixement de la $X$ i la $G$ necessitem calcular $M$. Cada un dels receptors en $K$, tracta de resoldre aquesta equació lineal, i per als que almenys $N\geq S$ els paquets han de ser rebuts. Els paquets rebuts són contínuament utilitzats en el mètode d'eliminació de Gauss per reduir la matriu $G$ en la forma esglaonada. Finalment, els valors resultants de $X=G_{echelon}M$ es resolen per obtenir $M$.

Exemple

Butterfly Network.

A la xarxa de papallona (Butterfly network), hi ha dues fonts situades a la part superior de la imatge, on cada una té coneixement del valor A o B. Hi ha dos nodes de destinació (a la part inferior), i tots dos volen saber els valors A i B. Cada vora només pot transportar un únic valor (podem pensar que es transmet un bit a cada ranura de temps).

Si usem el mecanisme d'encaminament, llavors la línia central seria capaç de dur a A o B, però no ambdós al mateix moment. Suposem que enviem A per l'enllaç del mig, el node de la dreta rebrà A i B, però el destí de l'esquerra rebrà A dos cops. Enviar B suposa el mateix problema per l'altre node destí. Diem que l'encaminament és insuficient perquè no hi ha cap sistema d'encaminament que pot transmetre tant A i B al mateix temps a totes dues destinacions.

Utilitzant un codi simple, com es mostra, s'obté A i B en els dos nodes destí simultàniament mitjançant l'enviament de la suma dels símbols a través del centre (en altres paraules, es codifiquen A i B utilitzant la fórmula "A + B"). El destí de l'esquerra rep A i (A + B), i es pot trobar B, restant els dos valors. Aquest és un codi lineal a causa de la codificació i descodificació dels règims són operacions lineals.

Network coding i el P2P

Molts acadèmics creuen que el Network Coding podria ajudar a millorar el rediment de les xarxes P2P. Però també n'hi ha molts que es mantenen escèptics. Fins i tot un dels creadors del Network Coding, el Dr. Yeung menciona al document "Can Network Coding Help in P2P" que no necessàriament dona un millor rediment en les xarxes P2P.

S'han trobat diferents problemes per l'aplicació del Network Coding a les xarxes P2P:

• Un peer(igual) pot arribar a necessitar molt de temps per descodificar les dades que reb
• Els recursos (CPU, etc.) que necesiten els nodes per descodificar
• Com garantir la singularitat dels coeficients quan hi ha multitud de peces a l'arxiu transferit
• La topologia d'una xarxa P2P és canviant
• Els Peers (iguals) poden deixar la xarxa en qualsevol moment vulguin.

Basat en això, han descobert que una xarxa P2P amb Network Coding pot arribar a ser pitjor que la xarxa BitTorrent.