Codarea rețelei

Codarea rețelei  este o ramură a teoriei informațiilor care studiază problema optimizării transmisiei de date într-o rețea folosind tehnici de schimbare a pachetelor de date la nodurile intermediare.

Fundamentele codificării rețelei

Pentru a explica principiile codării rețelei, folosiți exemplul unei rețele fluture, propus în prima lucrare despre codificarea rețelei „Fluxul de informații în rețea” [1] . Luați în considerare rețeaua prezentată în figură, în care există una sau două surse care generează pachetele A și B, ajungând la intrarea rețelei fluture. Primele noduri responsabile cu transmiterea informațiilor transmit câte un pachet (A în stânga și B în dreapta) la intrarea către nodurile finale ale destinatarilor. De asemenea, ei transmit aceste pachete unui nod intermediar, care, în loc să trimită două pachete pe rând (și să piardă timp), combină aceste pachete, de exemplu, folosind operația XOR și transmite mai departe.

Nodurile de destinație au capacitatea de a recupera pachetele originale din informații despre un singur pachet primit și o combinație a acestora. Ca urmare, debitul rețelei crește - două pachete pot fi transmise la doi destinatari simultan (pentru fiecare ciclu), deși secțiunea minimă de rețea conține doar trei canale de transmisie a datelor.

Codare aleatorie a rețelei

Spre deosebire de codarea statică a rețelei, atunci când destinatarul cunoaște toate manipulările efectuate cu pachetul, problema codificării aleatorii a rețelei este de asemenea luată în considerare atunci când această informație este necunoscută. Paternitatea primelor lucrări pe această temă aparține lui Kötter, Krzyszang și Silva [2] . Această abordare se mai numește și codificare de rețea cu coeficienți aleatori - când coeficienții sub care pachetele inițiale transmise de sursă vor fi incluși în pachetele rezultate primite de destinatar, cu coeficienți necunoscuți care pot depinde de structura actuală a rețelei și chiar de aleatoriu. deciziile luate la nodurile intermediare .

Metoda principală este includerea în pachetul transmis a informațiilor suplimentare care identifică pachetul în cadrul unei anumite sesiuni (se crede că pachetele aparținând unei singure sesiuni pot fi combinate). De exemplu, ar putea fi un simplu câmp de biți. Pentru rețeaua fluture discutată mai sus, acest câmp de biți poate consta din doi biți pentru fiecare pachet:

Pachet	câmp de biți
	zece
	0 1
	unsprezece

Primul destinatar va primi două pachete cu câmpuri de biți „1 0” și „1 1”, al doilea destinatar va primi „0 1” și „1 1”. Folosind acest câmp ca informații despre coeficienții ecuației liniare pentru pachete, receptorul poate recupera pachetele originale dacă acestea au fost transmise fără erori.

Protecția informațiilor împotriva distorsiunii

Pentru codificarea rețelei non-aleatorie, pot fi utilizate tehnici standard de anti-jamming și anti-aliasing utilizate pentru transmiterea simplă a informațiilor într-o rețea. Totuși, așa cum se menționează în articolul „Scheme de codare LDPC pentru eroare” [3] , pachetele recuperate din combinații liniare au o probabilitate mai mare de a fi primite cu o eroare, deoarece sunt afectate ca probabilitate de eroare în două pachete utilizate pentru recuperarea informațiilor la o singura data.

Având în vedere rețeaua „fluture”, se poate demonstra că pentru primul destinatar probabilitatea de a primi un pachet fără erori este mai mare decât pentru pachetul , chiar dacă presupunem aceleași, dar nenule, probabilități de eroare în pachetele primite și .

Pentru a reduce acest efect, autorii propun modificarea metodei de decodificare iterativă a pachetelor A și B (de exemplu, utilizând codificarea LDPC ), atunci când iterațiile de decodare a pachetelor sunt efectuate simultan și decodoarele fac schimb de informații despre probabilitățile de eroare din pachetul specific. biți. Pentru a scăpa complet de acest efect, autorii propun și împărțirea pachetelor sursă în mai multe părți și transferarea lor în diferite moduri. După cum a arătat experimentul numeric, acest lucru echivalează cu adevărat probabilitățile de decodificare a pachetelor.

Metodele utilizate pentru decodare în codificarea aleatorie a rețelei consideră toate pachetele primite ca un singur obiect (adesea o matrice) construit din pachetele de rând primite. Dacă prima parte a pachetului este un câmp de biți, atunci operațiunile cu matricea se reduc, în primul rând, la aducerea părții stângi într-o formă diagonală (folosind metoda Gauss ) și apoi la corectarea erorilor din partea dreaptă a matricei. . Pentru a corecta erorile, pot fi utilizate coduri de rang , care pot corecta nu numai erorile din coloanele matricei (din cauza biților de date primiți incorect), ci și erorile din rândurile matricei (datorită erorilor de transmisie în câmpul de biți) .

Note

1. ↑ Ahlswede, R.; Ning Cai; Li, S.-YR; Yeung, RW, " Network information flow ", Information Theory, IEEE Transactions on, vol.46, nr.4, pp.1204-1216, Jul 2000
2. ↑ Articole
   • Koetter R., Kschischang FR Codificarea erorilor și ștergerilor în codarea aleatorie a rețelei// Simpozionul internațional IEEE privind teoria informației. Proc.ISIT-07.-2007.- P. 791-795.
   • Silva D., Kschischang FR Utilizarea codurilor rank-metrice pentru corectarea erorilor în codarea aleatorie a rețelei // Simpozionul internațional IEEE privind teoria informației. Proc. ISIT-07. — 2007.
   • Koetter R., Kschischang FR Codificarea erorilor și ștergerilor în codarea aleatorie a rețelei // 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. Scheme de codare LDPC pentru controlul erorilor într-o rețea multicast

Vezi și

• Dirijare
• reţea peer-to-peer