Линейное сетевое кодирование - Linear network coding

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

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

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

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

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

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

Каждый узел, ${ displaystyle p_ {k}}$ с степень, ${ displaystyle InDeg (p_ {k}) = S}$ , генерирует сообщение ${ displaystyle X_ {k}}$ из линейной комбинации полученных сообщений ${ Displaystyle {M_ {я} } _ {я = 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}}$ , используемый в ${ Displaystyle к ^ { текст {th}}}$ уровень, ${ displaystyle g_ {k} ^ {i}}$ .

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

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

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

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

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

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

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

Сеть бабочек ^[2] часто используется для иллюстрации того, как линейное сетевое кодирование может превзойти маршрутизация. Два исходных узла (вверху рисунка) имеют информацию 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.

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

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

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

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

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

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

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

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

Приложения

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

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

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

Благодаря многоадресной доставке контента из нескольких источников Информационно-ориентированные сети в целом и Именованная сеть передачи данных в частности, линейное кодирование может улучшить эффективность всей сети. ^[10]
Альтернативой упреждающее исправление ошибок и ARQ в традиционных и беспроводных сетях с потерей пакетов. например.: Кодированный TCP,^[11] Многопользовательский ARQ^[12]
Надежность и устойчивость к сетевым атакам, таким как отслеживание, перехват, воспроизведение или повреждение данных.^[13]^[14]
Распространение цифровых файлов и обмен файлами P2P. например.: Лавина от Microsoft
Распределенное хранилище.^[15]^[16]^[17]
Увеличение пропускной способности в беспроводных ячеистых сетях. например : СПРАВИТЬСЯ,^[18] ОСНОВНОЙ,^[19] Маршрутизация с учетом кодирования,^[20]^[21] БЭТМЕН.^[22]
Уменьшение буфера и задержки в пространственных сенсорных сетях: Мультиплексирование пространственного буфера ^[23]
Уменьшите количество повторных передач пакетов для односкачковой беспроводной многоадресной передачи и, следовательно, улучшите пропускную способность сети.^[24]
Распределенный обмен файлами ^[25]
Потоковое видео низкой сложности на мобильные устройства ^[26]
От устройства к устройству (D2D) расширения^[27]^[28]^[29]^[30]^[31]

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

Срок погашения и проблемы

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

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

Смотрите также

внешняя ссылка

Домашняя страница сетевого кодирования
Библиография сетевого кодирования
Раймонд В. Йунг, Теория информации и сетевое кодирование, 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=best&recid=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
Коды цифровых фонтанов, http://www.icsi.berkeley.edu/~luby/
Маршрутизация с учетом кодирования, https://web.archive.org/web/20081011124616/http://arena.cse.sc.edu/papers/rocx.secon06.pdf
MIT предлагает курс: Введение в сетевое кодирование
Сетевое кодирование: следующая революция в сети?
Дизайн протокола с учетом кодирования для беспроводных сетей: http://scholarcommons.sc.edu/etd/230/

[Celebiler&S1978-1] Селебилер, М .; Г. Стетте (1978). «Об увеличении пропускной способности регенеративного спутникового ретранслятора в прямом канале связи в двухточечной связи». Труды IEEE. 66 (1): 98–100. Дои:10.1109 / PROC.1978.10848.

[Ahlswede2000-2] а ^б ^c Альсведе, Рудольф; Н. Цай; С.-Ю. Р. Ли; Р. В. Йунг (2000). «Сетевой информационный поток». IEEE Transactions по теории информации. 46 (4): 1204–1216. CiteSeerX 10.1.1.722.1409. Дои:10.1109/18.850663.

[3] С. Ли, Р. Юнг и Н. Цай, "Линейное сетевое кодирование" (PDF ), в IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003.

[4] Р. Догерти, К. Фрейлинг, и К. Зегер, "Недостаточность линейного кодирования в потоке сетевой информации" (PDF ), в IEEE Transactions on Information Theory, Vol. 51, No. 8, pp. 2745-2759, август 2005 г. ( ошибка )

[5] Чоу, Филип А .; У, Юньнань; Джайн, Камаль (октябрь 2003 г.), «Практическое сетевое кодирование», Конференция Allerton по коммуникациям, управлению и вычислениям, Затем любой приемник может восстановить исходные векторы, используя исключение Гаусса на векторах в его час (или больше) полученных пакетов.

[Ho2003-6] Т. Хо, Р. Кёттер, М. Медар, Д. Р. Каргер и М. Эффрос, «Преимущества кодирования над маршрутизацией в случайном порядке» В архиве 2017-10-31 в Wayback Machine в 2003 г. на международном симпозиуме IEEE по теории информации. Дои:10.1109 / ISIT.2003.1228459

[firooz2013-7] М. Х. Фируз, З. Чен, С. Рой и Х. Лю, (Кодирование беспроводной сети через модифицированный 802.11 MAC / PHY: разработка и реализация на SDR ) в журнале IEEE по избранным областям коммуникаций, 2013.

[8] XOR в воздухе: практическое кодирование беспроводной сети

[9] «Насколько практично сетевое кодирование? Меа Ван, Баочунь Ли». CiteSeerX 10.1.1.77.6402. Цитировать журнал требует | журнал = (помощь)

[10] Билал, Мухаммед; и другие. (2019). "Подход сетевого кодирования для информационных сетей". Системный журнал IEEE. 13 (2): 1376–1385. arXiv:1808.00348. Bibcode:2019ISysJ..13.1376B. Дои:10.1109 / JSYST.2018.2862913.

[11] Ким, Минджи (2012). «Сетевой протокол TCP (CTCP)». arXiv:1212.2291 [cs.NI ].

[12] «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2007-11-08. Получено 2007-06-16.CS1 maint: заархивированная копия как заголовок (связь)

[13] «Добро пожаловать в систему безопасности сетевого кодирования - безопасное сетевое кодирование».

[14] ttp://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf^{[постоянная мертвая ссылка ]}

[15] Билал, Мухаммед; и другие. (2019). "Подход сетевого кодирования для информационных сетей". Системный журнал IEEE. 13 (2): 1376–1385. arXiv:1808.00348. Bibcode:2019ISysJ..13.1376B. Дои:10.1109 / JSYST.2018.2862913.

[16] «Архивная копия» (PDF). Архивировано из оригинал (PDF) в 2013-09-19. Получено 2013-04-18.CS1 maint: заархивированная копия как заголовок (связь)

[17] Димакис, Александрос (2007). «Сетевое кодирование для распределенных систем хранения». arXiv:cs / 0702015.

[18] ttp://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf

[19] Кригслунд, Йеппе; Хансен, Йонас; Хундеболл, Мартин; Lucani, Daniel E .; Фитцек, Фрэнк Х. П. (2013). Ядро: БОЛЬШЕ КОПИРА в беспроводных ячеистых сетях. 77-я Конференция по автомобильным технологиям, IEEE, 2013 (весна VTC). С. 1–6. Дои:10.1109 / VTCSpring.2013.6692495. ISBN 978-1-4673-6337-2.

[20] «Архивная копия» (PDF). Архивировано из оригинал (PDF) на 2008-10-11. Получено 2007-05-10.CS1 maint: заархивированная копия как заголовок (связь)

[21] ttp://www.cs.wisc.edu/~shravan/infocom-07-2.pdf

[22] "NetworkCoding - batman-adv - Open Mesh". www.open-mesh.org. Получено 2015-10-28.

[23] Добро пожаловать в IEEE Xplore 2.0: Взгляд на большие сети: кодирование против очередей

[24] Донг Нгуен; Туан Тран; Тхинь Нгуен; Бозе, Б. (2009). «Беспроводное вещание с использованием сетевого кодирования». Транзакции IEEE по автомобильным технологиям. 58 (2): 914–925. CiteSeerX 10.1.1.321.1962. Дои:10.1109 / TVT.2008.927729.

[25] Распространение данных в беспроводных сетях с сетевым кодированием

[26] Полосные коды для энергоэффективного сетевого кодирования с применением для мобильной потоковой передачи P2P

[27] Ву Ю., Лю В., Ван С., Го В. и Чу X. (2015, июнь). Сетевое кодирование при обмене данными между устройствами (D2D), лежащих в основе сотовых сетей. В 2015 году Международная конференция по коммуникациям IEEE (ICC) (стр. 2072-2077). IEEE.

[28] Чжао, Ю., Ли, Ю., и Ге, Н. (2015, декабрь). Сетевое кодирование на физическом уровне, поддерживающее двустороннюю связь между устройствами, лежащую в основе сотовых сетей. В 2015 году IEEE Global Communications Conference (GLOBECOM) (стр. 1-6). IEEE.

[29] Абрардо, А., Фодор, Г., и Тола, Б. (2015, июнь). Схемы сетевого кодирования для ретрансляции на основе связи между устройствами для расширения покрытия сотовой связи. В 2015 году IEEE 16-й Международный семинар по достижениям в обработке сигналов в беспроводной связи (SPAWC) (стр. 670-674). IEEE.

[30] Гао, К., Ли, Ю., Чжао, Ю., и Чен, С. (2017). Двухуровневый подход теории игр для совместного выбора ретранслятора и распределения ресурсов в D2D-коммуникациях с помощью сетевого кодирования. IEEE Transactions on Mobile Computing, 16 (10), 2697-2711.

[31] Чжоу, Т., Сюй, Б., Сю, Т., Ху, Х., и Сюн, Л. (2015). Индивидуальная для пользователя схема адаптации канала для многоадресного сетевого кодирования от устройства к устройству. IET Communications, 9 (3), 367-374.

[32] SD-WAN с сетевым кодированием в системах множественного доступа для контроля задержек

[33] Контроллер SD-WAN для минимизации джиттера задержки в системах с кодированным множественным доступом

[34] «Насколько практично сетевое кодирование?». CiteSeerX 10.1.1.77.6402. Цитировать журнал требует | журнал = (помощь)

[35] "XOR в воздухе" (PDF).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]