Сетевое кодирование

В задаче линейного сетевого кодирования подмножество узлов ${\displaystyle P}$ функционирует для пересылки данных от ${\displaystyle S}$ исходных узлов к ${\displaystyle K}$ узлам-приёмникам. Каждый узел создаёт новые пакеты, представляющие собой линейные комбинации уже полученных данных с использованием коэффициентов, выбираемых из конечного поля Галуа, обычно ${\displaystyle GF(2^{s})}$.

Более формально: каждый узел ${\displaystyle p_{k}}$ со входной степенью ${\displaystyle InDeg(p_{k})=S}$ формирует сообщение ${\displaystyle X_{k}}$ как линейную комбинацию принятых сообщений ${\displaystyle \{M_{i}\}_{i=1}^{S}}$:

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

где ${\displaystyle g_{k}^{i}}$ — коэффициенты из ${\displaystyle GF(2^{s})}$. Благодаря тому, что все операции выполняются в конечном поле, длина сгенерированного сообщения не меняется. Каждый узел передает получателю как вычисленное значение ${\displaystyle X_{k}}$, так и соответствующие коэффициенты ${\displaystyle g_{k}^{i}}$.

Узлы-приёмники собирают поступающие закодированные сообщения, составляя из них матрицу, и могут восстановить исходные данные путём выполнения метода Гаусса над этой матрицей^[7]. В приведённом к ступенчатому виду случае каждая декодированная строка соответствует исходному сообщению.

Сеть моделируется в виде ориентированного графа ${\displaystyle {\mathcal {G}}=(V,E,C)}$, где ${\displaystyle V}$ — множество узлов, ${\displaystyle E}$ — множество рёбер (дуг), а ${\displaystyle C}$ задаёт пропускную способность каждого ребра. Пусть ${\displaystyle T(s,t)}$ — максимальная пропускная способность между узлами ${\displaystyle s}$ и ${\displaystyle t}$. По теореме о максимальном потоке и минимальном разрезе, ${\displaystyle T(s,t)}$ ограничена минимальной пропускной способностью разреза между этими узлами.

Карл Менгер доказал, что в задачи уникаста всегда существует набор несовпадающих путей, позволяющий достичь теоретического максимума^[8]. В задачах широковещания эта граница также достижима, как показал Эдмондс, предложив полиномиальный алгоритм. Однако мультикаст сложнее: максимальный поток тут невозможен при обычной маршрутизации, но достижим с помощью вычислительных операций (например, суммирования пакетов) на промежуточных узлах.

Сеть-бабочка — классический пример, наглядно демонстрирующий преимущества линейного сетевого кодирования по сравнению с обычной маршрутизацией. Если разрешена только маршрутизация, центральное звено может передавать либо только А, либо только В, что приводит к избыточной передаче для одной из сторон и невозможности получить обе информации одновременно. С помощью простого кодирования (например, передачи A+B) обе принимающие стороны могут за три шага получить оба сообщения, тогда как при маршрутизации это требует четырёх шагов.

Случайное линейное сетевое кодирование (англ. random linear network coding, RLNC)^[9] — схема кодирования, при которой узлы сети формируют пакеты как случайные линейные комбинации полученных данных с равновероятно выбранными коэффициентами из конечного поля Галуа. При достаточно большом поле вероятность получить линейно независимые комбинации стремится к единице.

Если получателю не хватило количества пакетов для декодирования, восстановить исходные данные крайне маловероятно; для устранения этой проблемы отправитель передаёт дополнительные комбинации, пока не будет получено минимум нужных независимых пакетов.

Три основных параметра RLNC:

• Размер поколения: исходные данные делятся на группы (поколения), которые кодируются вместе.
• Размер пакета: обычно фиксированный; при необходимости пакеты дополняются нулями или разбиваются.
• Поле Галуа: широко используются поля ${\displaystyle GF(2)}$ и ${\displaystyle GF(2^{8})}$ (binary-8).

Каждый пакет состоит из набора символов конечного поля. Для закодированного пакета исходные и уже закодированные пакеты умножают на случайные коэффициенты и складывают поэлементно. Коэффициенты кодирования добавляются в заголовок пакета, что позволяет любому узлу отслеживать, каким образом получены данные.

Одно из преимуществ линейного сетевого кодирования — возможность повторного комбинирования уже закодированных пакетов. После рекодирования размер дополнительной информации (коэффициентов) не увеличивается.

Для успешного декодирования приёмнику необходимо собрать не менее ${\displaystyle M}$ линейно независимых пакетов (где ${\displaystyle M}$ — размер поколения); алгоритм восстановления — решение системы линейных уравнений по известным коэффициентам.

На рисунке приведён пример, где два пакета ${\displaystyle f}$ и ${\displaystyle e}$ объединяются в новый закодированный пакет. Каждый из исходных пакетов содержит дополнительные коэффициенты для идентификации их состава — например, оригинальный (некодированный) пакет содержит ${\displaystyle [1,0]}$ или ${\displaystyle [0,1]}$, а закодированный — произвольные ${\displaystyle [C_{ij}]}$.

Для получения нового кода узел выбирает случайные коэффициенты ${\displaystyle d_{1}}$ и ${\displaystyle d_{2}}$, умножает соответствующие пакеты по символам и складывает их, формируя новый комбинированный пакет. Тот же принцип применяется для обновления набора коэффициентов.

Несмотря на интенсивные исследования за последние 20 лет, остаются некорректные представления:

Сложность декодирования: современные декодеры эффективны и легко параллелизуются. Например, на процессорах Intel Core i5 с SIMD-доступом скорость декодирования достигает 750 МБ/с для 16 пакетов или 250 МБ/с для 64 пакетов^[10]. Стадии кодирования и декодирования отлично масштабируются за счёт параллельных вычислений^[11].

Передача коэффициентов: добавление коэффициентов кодирования в пакеты практически не увеличивает объём передаваемой информации — при типичных параметрах этот overhead составляет около 2 %.

Линейная зависимость пакетов: из-за случайности коэффициентов возможна передача невостребованных комбинаций, но эта избыточность минимальна и уменьшается с ростом размера поля Галуа. На практике даже для бинарного поля этот overhead обычно не превышает 5 %.

Сетевое кодирование активно внедряется учёными и компаниями для повышения производительности и надёжности сетевых решений в различных областях:

• VoIP-сервисы: увеличение устойчивости потоковой передачи в mesh-сетях вследствие снижения задержек и джиттера^[12].
• Видеостриминг и аудиоконференции: увеличение доставляемости и уменьшение потерь данных по сравнению с классическими схемами ретрансляции^[13].
• SD-WAN и IoT: снижается задержка и jitter в сетях с несколькими каналами связи^[14].
• Объединение каналов связи между устройствами^[15].
• 5G частные сети: совершенствование качества передачи мультимедиа посредством интеграции RLNC^[16].
• Удалённая совместная работа и VR/AR-тренинги^[17].
• Ведение автомобилей с удалённым управлением и сети подключённых авто^[18].
• Онлайн-игры и стриминг с низкими задержками^[19].
• Защищённая передача файлов, P2P файловые системы (Avalanche filesystem).
• Умные города, IoT-инфраструктура, системы автоматического обновления прошивок.
• Повышение пропускной способности mesh-сетей, например, с применением технологий COPE, CORE, Coding-aware routing, B.A.T.M.A.N. и других^[20].
• Пространственные сенсорные сети, спутниковые связные системы^[21].
• Защита от атак: предотвращение подслушивания, модификации, искажений или повторной передачи информации^[22].
• Децентрализованные системы хранения данных.
• Поиск и оптимизация маршрутов передачи в средах с большими задержками и потерями: альтернатива Forward Error Correction, ARQ и др.