Мережеве кодування

Для терміну "Кодування" см. інші значення.

Мережеве кодування - розділ теорії інформації вивчає питання оптимізації передачі даних по мережі з використанням технік зміни пакетів даних на проміжних вузлах.


1. Основи мережевого кодування

Мережа "Метелик"

Для пояснення принципів мережевого кодування використовують приклад мережі "метелик", запропонованої в першій роботі по мережевому кодуванню "Network information flow" [1]. Розглянемо мережу, показану на малюнку, в якій є один або два джерела, що генерує пакети A та B, що надходять на вхід мережі "метелик". Перші вузли, що відповідають за передачу інформації, передають по одному пакету (A зліва і B праворуч) на вхід кінцевим вузлам одержувачам. Також вони передають ці пакети проміжного вузла, який, замість передачі двох пакетів по черзі (і втрати часу) комбінує ці пакети, наприклад, за допомогою операції XOR і передає далі.

Вузли-одержувачі мають можливість відновити вихідні пакети з інформацією про один отриманому пакеті і їх комбінації. В результаті збільшується пропускна здатність мережі - по два пакети може бути передано двом одержувачам одночасно (за кожен такт), хоча мінімальний перетин мережі містить всього три канали передачі даних.


2. Випадкове мережеве кодування

На відміну від статичного мережевого кодування, коли одержувачу відомі всі маніпуляції, вироблені з пакетом, також розглядається питання про випадковий мережевому кодуванні, коли дана інформація невідома. Авторство перших робіт з даної тематики належить Кеттер, Кшішангу і Сілві [2]. Також даний підхід називають мережевим кодуванням з випадковими коефіцієнтами - коли коефіцієнти, під якими початкові пакети, передані джерелом, увійдуть в результуючі пакети, що приймаються одержувачем, з невідомими коефіцієнтами, які можуть залежати від поточної структури мережі і навіть від випадкових рішень, прийнятих на проміжних вузлах .

В якості основного способу розглядається включення в переданий пакет додаткової інформації, що ідентифікує пакет в рамках деякої сесії (вважається, що комбінуватися можуть пакети належать тільки одній сесії). Наприклад, це може бути просте бітове поле. Для розглянутої вище мережі метелик дане бітове поле може складатися з двох біт для кожного пакету:

Пакет Бітове поле
A 1 0
B 0 1
A \ oplus B 1 січня

Перший одержувач отримає два пакети з бітовими полями "1 0" і "1 +1", другий одержувач - "0 1" і "1 +1". Використовуючи це поле як інформацію про коефіцієнти лінійного рівняння для пакетів, одержувач може відновити вихідні пакети, якщо вони були передані без помилок.


3. Захист інформації від спотворення

Для невипадкового мережевого кодування можна використовувати стандартні способи захисту від перешкод і спотворень, використовуваних для простої передачі інформації по мережі. Однак, як зазначено в статті "LDPC coding schemes for error" [3], пакети, відновлювані з лінійних комбінацій, мають більшу ймовірність бути прийнятими з помилкою, так як на них впливають як ймовірність помилки відразу в двох пакетах, використовуваних для відновлення інформації.

Розглядаючи мережа "метелик", можна показати, що для першого одержувача ймовірність прийняти пакет A без помилок більше, ніж для пакета B , Навіть якщо припустити однакові, але відмінні від нуля імовірності помилок в прийнятих одержувачем пакетах A і A \ oplus B .

Для того, щоб зменшити подібний ефект автори пропонують модифікувати спосіб ітеративного декодування пакетів A і B (при, наприклад, використанні LDPC -кодування), коли ітерації декодування пакетів проводяться одночасно і декодери обмінюються між собою про інформацію про ймовірностях помилок в конкретних бітах пакетів. Для повного позбавлення від даного ефекту автори пропонують також розбити вихідні пакети на декілька частин і передавати їх різними шляхами. Як показав чисельний експеримент, це дійсно зрівнює ймовірності декодування пакетів.

Методи, які використовуються для декодування у випадковому мережевому кодуванні, розглядають всі прийняті пакети як єдиний об'єкт (часто - матрицю), побудованої з прийнятих пакетів-рядків. Якщо перша частина пакету являє собою бітове поле, то операції з матрицею зводяться, по-перше, до приведення лівій її частині до діагонального вигляду (за допомогою методу Гауса), а потім до виправлення помилок у правій частині матриці. Для виправлення помилок можна використовувати рангові коди, які можуть виправити не тільки помилки у стовпцях матриці (через неправильно прийнятих бітів даних), але і помилки в рядках матриці (через помилки передачі в бітовому полі).


Примітки

  1. Ahlswede, R.; Ning Cai; Li, S.-YR; Yeung, RW, " Network information flow - ieeexplore.ieee.org / stamp / stamp.jsp? arnumber = 850663 & isnumber = 18482 ", Information Theory, IEEE Transactions on, vol.46, no.4, pp.1204-1216, Jul 2000
  2. Статті
    • Koetter R., Kschischang FR Coding for errors and erasures in random network coding / / IEEE International Symposium on Information Theory. Proc.ISIT-07.-2007. - P. 791-795.
    • Silva D., Kschischang FR Using rank-metric codes for error correction in random network coding / / IEEE International Symposium on Information Theory. Proc. ISIT-07. - 2007.
    • Koetter R., Kschischang FR Coding for errors and erasures in random network coding / / 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 coding schemes for error control in a multicast network