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

Для термина «Кодирование» см. другие значения.

Сетевое кодирование — раздел теории информации изучающий вопрос оптимизации передачи данных по сети с использованием техник изменения пакетов данных на промежуточных узлах.

Основы сетевого кодирования

Сеть «Бабочка»

Для объяснения принципов сетевого кодирования используют пример сети «бабочка», предложенной в первой работе по сетевому кодированию «Network information flow»^[1]. Рассмотрим сеть, показанную на рисунке, в которой есть один или два источника, генерирующего пакеты A и B, поступающих на вход сети «бабочка». Первые узлы, отвечающие за передачу информации, передают по одному пакету (A слева и B справа) на вход конечным узлам получателям. Также они передают эти пакеты промежуточному узлу, который, вместо передачи двух пакетов по очереди (и потере времени) комбинирует эти пакеты, например, с помощью операции XOR и передаёт далее.

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

Случайное сетевое кодирование

В отличие от статического сетевого кодирования, когда получателю известны все манипуляции, производимые с пакетом, также рассматривается вопрос о случайном сетевом кодировании, когда данная информация неизвестна. Авторство первых работ по данной тематике принадлежит Кёттеру, Кшишангу и Силве^[2]. Также данный подход называют сетевым кодированием со случайными коэффициентами — когда коэффициенты, под которыми начальные пакеты, передаваемые источником, войдут в результирующие пакеты, принимаемые получателем, с неизвестными коэффициентами, которые могут зависеть от текущей структуры сети и даже от случайных решений, принимаемых на промежуточных узлах.

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

Пакет	Битовое поле
$A$	1 0
$B$	0 1
$A \oplus B$	1 1

Первый получатель получит два пакета с битовыми полями «1 0» и «1 1», второй получатель — «0 1» и «1 1». Используя это поле как информацию о коэффициентах линейного уравнения для пакетов, получатель может восстановить исходные пакеты, если они были переданы без ошибок.

Защита информации от искажения

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

Рассматривая сеть «бабочка», можно показать, что для первого получателя вероятность принять пакет $A$ без ошибок больше, чем для пакета $B$, даже если предположить одинаковые, но отличные от нуля вероятности ошибок в принятых получателем пакетах $A$ и $A \oplus B$.

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

Методы, используемые для декодирования в случайном сетевом кодировании, рассматривают все принятые пакеты как единый объект (часто — матрицу), построенной из принятых пакетов-строк. Если первая часть пакета представляет собой битовое поле, то операции с матрицей сводятся, во-первых, к приведению левой её части к диагональному виду (с помощью метода Гаусса), а затем к исправлению ошибок в правой части матрицы. Для исправления ошибок можно использовать ранговые коды, которые могут исправить не только ошибки в столбцах матрицы (из-за неправильно принятых битов данных), но и ошибки в строках матрицы (из-за ошибок передачи в битовом поле).

Примечания

1. ↑ Ahlswede, R.; Ning Cai; Li, S.-Y.R.; Yeung, R.W., «Network information flow», Information Theory, IEEE Transactions on, vol.46, no.4, pp.1204-1216, Jul 2000
2. ↑ Статьи
   • Koetter R., Kschischang F.R. 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 F.R. Using rank-metric codes for error correction in random network coding // IEEE International Symposium on Information Theory. Proc. ISIT-07. — 2007.
   • Koetter R., Kschischang F.R. 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 F.R., 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

См. также

• Маршрутизация
• Одноранговая сеть