Линейное сетевое кодирование

редактировать

Сетевое кодирование - это область исследований, основанная на серии статей с конца 1990-х до начала 2000-х годов. Однако концепция сетевого кодирования, в частности линейного сетевого кодирования, появилась намного раньше. В статье 1978 г. была предложена схема повышения пропускной способности двусторонней связи через спутник. В этой схеме два пользователя, пытающиеся общаться друг с другом, передают свои потоки данных на спутник, который объединяет два потока, суммируя их по модулю 2, а затем транслирует объединенный поток. Каждый из двух пользователей, получив широковещательный поток, может декодировать другой поток, используя информацию своего собственного потока.

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

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

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

Содержание

1 Кодирование и декодирование
2 Краткая история
3 Пример сети «бабочка»
4 Случайное линейное сетевое кодирование
- 4.1 Открытые проблемы
5 Кодирование беспроводной сети
6 Приложения
7 Зрелость и проблемы
8 См. Также
9 Ссылки
10 Внешние ссылки

Кодирование и декодирование

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

Каждый узел, $pk {\ displaystyle p_ {k}}$ $p_ { k}$ с степенью, $I n D например ( pk) = S {\ displaystyle InDeg (p_ {k}) = S}$ $InDeg (p_ {k}) = S$ , генерирует сообщение $X k {\ displaystyle X_ {k}}$ $X_{k}$ из линейной комбинации из полученных сообщений ${M i} i = 1 S {\ displaystyle \ {M_ {i} \} _ {i = 1} ^ {S}}$ $\ {M_ {i} \} _ {{i = 1}} ^ {S}$ соотношением:

X к знак равно ∑ я знак равно 1 S gki ⋅ M я {\ displaystyle X_ {k} = \ sum _ {i = 1} ^ {S} g_ {k} ^ {i} \ cdot M_ {i}}

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

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

Узлы-приемники получают эти закодированные в сети сообщения и собирают их в матрицу. Исходные сообщения могут быть восстановлены путем выполнения исключения Гаусса на матрице. В сокращенной форме эшелона строк декодированные пакеты соответствуют строкам формы $ei = [0... 010... 0] {\ displaystyle e_ {i} = [0... 010... 0] }$ $e_ {i} = [0... 010... 0]$ .

Краткая история

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

Карл Менгер доказал, что всегда существует набор непересекающихся по ребрам путей, достигающих верхней границы в одноадресном сценарии, известном как теорема о максимальном потоке и минимальном разрезе. Позже был предложен алгоритм Форда – Фалкерсона для поиска таких путей за полиномиальное время. Затем Эдмондс доказал в статье «Разветвления с непересекающимися краями», что верхняя граница в сценарии широковещательной рассылки также достижима, и предложил алгоритм с полиномиальным временем.

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

Пример сети «бабочка»

Сеть бабочки.

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

Если бы была разрешена только маршрутизация, тогда центральный канал мог бы передавать только A или B, но не оба. Предположим, мы отправляем A через центр; тогда левый пункт назначения получит A дважды и вообще не узнает B. Отправка B создает аналогичную проблему для правильного пункта назначения. Мы говорим, что маршрутизации недостаточно, потому что никакая схема маршрутизации не может передавать как A, так и B одновременно в оба пункта назначения.

Используя простой код, как показано, A и B могут быть переданы в оба пункта назначения одновременно, посылая сумму символов через центр - другими словами, мы кодируем A и B по формуле «A + B ". Левый пункт назначения получает A и A + B и может вычислить B, вычитая два значения. Точно так же правильный адресат получит B и A + B, а также сможет определить как A, так и B.

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

Случайное линейное сетевое кодирование - это простой, но мощный схема кодирования, которая в схемах широковещательной передачи обеспечивает близкую к оптимальной пропускную способность с использованием децентрализованного алгоритма. Узлы передают случайные линейные комбинации пакетов, которые они принимают, с коэффициентами, выбранными из поля Галуа. Если размер поля достаточно велик, вероятность того, что приемники получат линейно независимые комбинации (и, следовательно, получат инновационную информацию), приближается к 1. Однако следует отметить, что, хотя случайное линейное сетевое кодирование имеет отличную пропускную способность, если Получатель получает недостаточное количество пакетов, крайне маловероятно, что он сможет восстановить какой-либо из исходных пакетов. Эту проблему можно решить путем отправки дополнительных случайных линейных комбинаций, пока получатель не получит соответствующее количество пакетов.

Открытые вопросы

Линейное сетевое кодирование все еще относительно новая тема. Основываясь на предыдущих исследованиях, в RLNC есть три важных открытых вопроса:

Высокая вычислительная сложность декодирования из-за использования метода исключения Гаусса-Джордана
Высокие накладные расходы на передачу из-за присоединения больших векторов коэффициентов к кодированным блокам
Линейная зависимость между векторами коэффициентов, которая может уменьшить количество инновационных кодированных блоков

Кодирование беспроводной сети

Широковещательная природа беспроводной сети (в сочетании с топологией сети) определяет характер помех. Одновременная передача в беспроводной сети обычно приводит к потере всех пакетов (т. Е. Конфликту, см. Множественный доступ с предотвращением конфликтов для беспроводной сети ). Следовательно, для беспроводной сети требуется планировщик (как часть функции MAC ) для минимизации таких помех. Следовательно, любой выигрыш от сетевого кодирования сильно зависит от основного планировщика и будет отличаться от выигрыша, наблюдаемого в проводных сетях. Кроме того, беспроводные линии связи обычно являются полудуплексными из-за аппаратных ограничений; т.е. узел не может одновременно передавать и принимать из-за отсутствия достаточной изоляции между двумя путями.

Хотя изначально сетевое кодирование предлагалось использовать на сетевом уровне (см. модель OSI ), в беспроводных сетях сетевое кодирование широко использовалось либо на уровне MAC, либо на PHY слой. Было показано, что сетевое кодирование при использовании в беспроводных ячеистых сетях требует внимательного проектирования и размышлений, чтобы использовать преимущества смешивания пакетов, иначе преимущества не могут быть реализованы. Также существует множество факторов, влияющих на производительность, например протокол уровня доступа к среде передачи данных, алгоритмы управления перегрузкой и т. Д. Неочевидно, как сетевое кодирование может сосуществовать и не подвергать опасности то, что существующие алгоритмы управления перегрузками и потоками делают для нашего Интернета..

Приложения

Краткая иллюстрация сетевого кодирования, применяемого для связи между устройствами. D1 и D2 обозначают устройства, BS - базовая станция, а M1, M2 и M3 - определенные сообщения.

Поскольку линейное сетевое кодирование является относительно новым предметом, его внедрение в отраслях все еще ожидается. В отличие от другого кодирования, линейное сетевое кодирование не полностью применимо в системе из-за его узкого специфического сценария использования. Теоретики пытаются подключиться к приложениям реального мира. Фактически, было обнаружено, что подход BitTorrent намного превосходит сетевое кодирование.

Предполагается, что сетевое кодирование будет полезно в следующих областях:

Из-за характера многоадресной доставки контента из нескольких источников Информационно-ориентированные сети в целом и именованные сети передачи данных в частности, линейное кодирование может повысить эффективность всей сети.
Альтернатива упреждающего исправления ошибок и ARQ в традиционных и беспроводных сетях с потерей пакетов. например:,
Надежность и устойчивость к сетевым атакам, таким как отслеживание, перехват, воспроизведение или повреждение данных.
Распространение цифровых файлов и совместное использование файлов P2P. например: Avalanche от Microsoft
Распределенное хранилище.
Увеличение пропускной способности в беспроводных ячеистых сетях. например :,,, BATMAN
Снижение буфера и задержки в сетях с пространственными датчиками:
Уменьшите количество повторных передач пакетов для односкачковой беспроводной многоадресной передачи и, следовательно, улучшите пропускную способность сети.
Распределенный обмен файлами
Потоковая передача видео низкой сложности на мобильные устройства
От устройства к устройству (D2D) расширения

Появляются новые методы использования сетевого кодирования в системах с множественным доступом для разработки программно-определяемых проводных сетей (SD-WAN), которые могут предложить более низкую задержку, джиттер и высокую надежность. В предложении упоминается, что метод не зависит от базовых технологий, таких как LTE, Ethernet, 5G.

Зрелость и проблемы

Поскольку эта область относительно новая, и математическая обработка этого предмета в настоящее время ограничивается Горстка людей, сетевое кодирование еще не нашло своего пути к коммерциализации продуктов и услуг. На данном этапе неясно, будет ли эта тема преобладать или исчезнет как хорошее математическое упражнение.

Исследователи ясно указали, что требуется особая осторожность, чтобы изучить, как сетевое кодирование может сосуществовать с существующей маршрутизацией, медиа. доступ, перегрузка, алгоритмы управления потоком и протокол TCP. В противном случае сетевое кодирование может не дать больших преимуществ и может увеличить сложность вычислений и требования к памяти.

См. Также

Ссылки

Fragouli, C.; Ле Будек, Дж. И Видмер, Дж. «Сетевое кодирование: мгновенный учебник» в Computer Communication Review, 2006.

Али Фарзамния, Шарифа К. Сайед-Юсоф, Норшейла Фиса «Многоадресное кодирование с множественным описанием с использованием p-Cycle Network Coding ", KSII Transactions on Internet and Information Systems, Vol 7, No. 12, 2013.

Внешние ссылки

Домашняя страница сетевого кодирования
Библиография сетевого кодирования
Раймонд В. Йунг, Теория информации и сетевое кодирование, Springer 2008, http://iest2.ie.cuhk.edu.hk/~whyeung/book2/
Раймонд В. Йунг и др., Теория сетевого кодирования, теперь Publishers, 2005, http://iest2.ie.cuhk.edu.hk/~whyeung/netcode/monograph.html
Кристина Фрагули и др., Сетевое кодирование: мгновенный учебник, ACM SIGCOMM 2006, http: / /infoscience.epfl.ch/getfile.py?mode=bestrecid=58339.
Файловая система Avalanche, http://research.microsoft.com/en-us/projects/avalanche/default.aspx
Случайно Сетевое кодирование, https://web.archive.org/web/20060618083034/http://www.mit.edu/ ~ medard / coding1.htm
Digital Fountain Codes, http://www.icsi.berkeley.edu/~luby/
Coding-Aware Routing, https: //web.archive. org / web / 20081011124616 / http: //arena.cse.sc.edu/papers/rocx.secon06.pdf
MIT предлагает курс: Введение в сетевое кодирование
Сетевое кодирование: следующая революция в сети?
Дизайн протокола с учетом кодирования для беспроводных сетей: http://scholarcommons.sc.edu/etd/230/