Сетевое кодирование - это область исследований, основанная на серии статей с конца 1990-х до начала 2000-х годов. Однако концепция сетевого кодирования, в частности линейного сетевого кодирования , появилась намного раньше. В статье 1978 г. [1] была предложена схема повышения пропускной способности двусторонней связи через спутник. В этой схеме два пользователя, пытающиеся общаться друг с другом, передают свои потоки данных на спутник, который объединяет два потока, суммируя их по модулю 2, а затем транслирует объединенный поток. Каждый из двух пользователей, получив широковещательный поток, может декодировать другой поток, используя информацию своего собственного потока.
В статье 2000 г. [2] приведен пример сети «бабочка» (обсуждается ниже), который показывает, как линейное сетевое кодирование может превзойти маршрутизацию. Этот пример эквивалентен схеме спутниковой связи, описанной выше. В той же статье дается оптимальная схема кодирования для сети с одним исходным узлом и тремя конечными узлами. Это первый пример, иллюстрирующий оптимальность сверточного сетевого кодирования (более общая форма линейного сетевого кодирования) в циклической сети.
Линейное сетевое кодирование может использоваться для повышения пропускной способности, эффективности и масштабируемости сети , а также устойчивости к атакам и перехвату. Вместо простой ретрансляции пакетов информации, которые они получают, узлы сети берут несколько пакетов и объединяют их вместе для передачи. Это может быть использовано для достижения максимально возможного информационного потока в сети .
Математически доказано, что теоретически линейного кодирования достаточно для достижения верхней границы в задачах многоадресной рассылки с одним источником. [3] Однако линейного кодирования в целом недостаточно (например, с несколькими источниками, с несколькими каналами с произвольными требованиями), даже для более общих версий линейности, таких как сверточное кодирование и кодирование с помощью банка фильтров . [4] Поиск оптимальных кодовых решений для общих сетевых проблем с произвольными требованиями остается открытой проблемой.
Кодирование и декодирование
В задаче линейного сетевого кодирования группа узлов участвуют в перемещении данных из исходные узлы для приемные узлы. Каждый узел генерирует новые пакеты, которые представляют собой линейные комбинации ранее полученных пакетов, умножая их на коэффициенты, выбранные из конечного поля , обычно размера.
Каждый узел, со степенью ,, генерирует сообщение из линейной комбинации полученных сообщений отношением:
где значения коэффициенты, выбранные из . Обратите внимание, что, поскольку операции вычисляются в конечном поле, сгенерированное сообщение имеет ту же длину, что и исходные сообщения. Каждый узел пересылает вычисленное значение вместе с коэффициентами, , используемый в уровень, .
Узлы-приемники получают эти закодированные в сети сообщения и собирают их в матрицу. Исходные сообщения могут быть восстановлены путем исключения Гаусса на матрице. [5] В сокращенной форме эшелона строк декодированные пакеты соответствуют строкам формы.
Краткая история
Сеть представлена ориентированным графом . это множество узлов или вершин, - множество направленных звеньев (или ребер), а дает емкость каждого звена . Позволять быть максимально возможной пропускной способностью от узла к узлу . По теореме мин-среза макс потока ,ограничена сверху минимальной пропускной способностью всех разрезов , которая представляет собой сумму мощностей ребер разреза между этими двумя узлами.
Карл Менгер доказал, что всегда существует набор непересекающихся по ребрам путей, достигающих верхней границы в одноадресном сценарии, известный как теорема о максимальном потоке и минимальном разрезе . Позже был предложен алгоритм Форда – Фулкерсона, позволяющий находить такие пути за полиномиальное время. Затем Эдмондс доказал в статье "Edge-Disjoint Branchings", что верхняя граница в сценарии широковещательной рассылки также достижима, и предложил алгоритм с полиномиальным временем.
Однако ситуация в сценарии многоадресной рассылки более сложна, и на самом деле такая верхняя граница не может быть достигнута с использованием традиционных идей маршрутизации . Альсведе и др. доказано, что это может быть достигнуто, если дополнительные вычислительные задачи (входящие пакеты объединяются в один или несколько исходящих пакетов) могут быть выполнены в промежуточных узлах. [2]
Пример сети бабочек
Сеть «бабочка» [2] часто используется для иллюстрации того, как линейное сетевое кодирование может превзойти маршрутизацию . Два исходных узла (вверху рисунка) имеют информацию A и B, которая должна быть передана двум узлам назначения (внизу). Каждый целевой узел хочет знать как A, так и B. Каждое ребро может нести только одно значение (мы можем думать о ребре, передающем бит в каждом временном интервале).
Если бы была разрешена только маршрутизация, тогда центральный канал мог бы передавать только A или B, но не оба. Предположим, мы отправляем А через центр; тогда левый пункт назначения получит A дважды и вообще не узнает B. Отправка B создает аналогичную проблему для правильного пункта назначения. Мы говорим, что маршрутизации недостаточно, потому что никакая схема маршрутизации не может передавать как A, так и 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]
Приложения
Поскольку линейное сетевое кодирование является относительно новым предметом, его внедрение в отрасли все еще не принято. В отличие от другого кодирования, линейное сетевое кодирование не полностью применимо в системе из-за его узкого специфического сценария использования. Теоретики пытаются подключиться к приложениям реального мира. [9] Фактически, было обнаружено, что подход BitTorrent намного превосходит сетевое кодирование. [ расплывчато ] [ необходима ссылка ]
Предполагается, что сетевое кодирование будет полезно в следующих областях:
- Благодаря тому, что информационная сеть в целом и сеть с именованными данными в частности имеют многоадресную доставку контента с множеством источников, линейное кодирование может улучшить эффективность всей сети. [10]
- Альтернатива прямому исправлению ошибок и ARQ в традиционных и беспроводных сетях с потерей пакетов. например: Кодированный TCP , [11] Многопользовательский ARQ [12]
- Надежность и устойчивость к сетевым атакам, таким как отслеживание, перехват, воспроизведение или повреждение данных. [13] [14]
- Распространение цифровых файлов и обмен файлами P2P. например: Avalanche от Microsoft
- Распределенное хранилище. [15] [16] [17]
- Увеличение пропускной способности в беспроводных ячеистых сетях. например: COPE , [18] CORE , [19] Маршрутизация с учетом кодирования , [20] [21] BATMAN [22]
- Уменьшение буфера и задержки в сетях пространственных датчиков: мультиплексирование пространственного буфера [23]
- Уменьшите количество повторных передач пакетов для односкачковой беспроводной многоадресной передачи и, следовательно, улучшите пропускную способность сети. [24]
- Распределенный обмен файлами [25]
- Потоковое видео низкой сложности на мобильные устройства [26]
- Расширения " устройство-устройство" (D2D) [27] [28] [29] [30] [31]
Появляются новые методы использования сетевого кодирования в системах с множественным доступом для разработки программно-определяемых проводных сетей (SD-WAN), которые могут предложить меньшую задержку, джиттер и высокую надежность. [32] В предложении упоминается, что метод не зависит от базовых технологий, таких как LTE, Ethernet, 5G. [33]
Срок погашения и проблемы
Поскольку эта область относительно нова, и математическое рассмотрение этого предмета в настоящее время ограничено несколькими людьми, сетевое кодирование все же нашло свой путь к коммерциализации продуктов и услуг. На данном этапе неясно, будет ли этот предмет преобладать или прекратится как хорошее математическое упражнение. [34]
Исследователи четко указали на необходимость особого внимания к изучению того, как сетевое кодирование может сосуществовать с существующей маршрутизацией, доступом к среде передачи, перегрузкой, алгоритмами управления потоком и протоколом TCP. В противном случае сетевое кодирование может не дать больших преимуществ и может увеличить сложность вычислений и требования к памяти. [35]
Смотрите также
- Протокол обмена секретом
- Гомоморфные подписи для сетевого кодирования
- Кодирование треугольной сети
Рекомендации
- ^ Селебилер, М .; Г. Стетте (1978). «Об увеличении пропускной способности регенеративного спутникового ретранслятора в прямой связи». Труды IEEE . 66 (1): 98–100. DOI : 10,1109 / PROC.1978.10848 .
- ^ а б в Альсведе, Рудольф ; N. Cai; S.-YR Li; Р. В. Йунг (2000). «Сетевой информационный поток». IEEE Transactions по теории информации . 46 (4): 1204–1216. CiteSeerX 10.1.1.722.1409 . DOI : 10.1109 / 18.850663 .
- ^ С. Ли, Р. Йунг и Н. Цай, «Линейное сетевое кодирование» ( PDF ), в IEEE Transactions on Information Theory, Vol 49, No. 2, pp. 371–381, 2003
- ^ Р. Догерти, К. Фрейлинг и К. Зегер, «Недостаточность линейного кодирования в потоке сетевой информации» ( PDF ), в IEEE Transactions on Information Theory, Vol. 51, No. 8, pp. 2745-2759, август 2005 г. ( опечатка )
- ^ Чоу, Филип А .; У, Юньнань; Jain, Камаль (октябрь 2003), «Практическая сеть кодирования», Аллертоне конференция по связи, управления и вычислительной техники ,
любой приемник может затем восстановить векторы источника с помощью метода исключения Гаусса на векторах в час (или более) , полученные пакеты
. - ^ Т. Хо, Р. Koetter, М. Médard , DR Karger и М. Эфрос, «Преимущество кодирования над маршрутизацией в рандомизированной Настройке» архивной 2017-10-31 в Wayback Machine в 2003 году Международного симпозиума IEEE по теории информации . DOI : 10.1109 / ISIT.2003.1228459
- ^ MHFirooz, З. Чен, С. Рой и Х. Лю, ( Кодирование беспроводной сети с помощью модифицированного 802.11 MAC / PHY: проектирование и реализация на SDR ) в журнале IEEE по избранным областям связи, 2013.
- ^ XOR в воздухе: практическое кодирование беспроводной сети
- ^ «Насколько практично сетевое кодирование? Меа Ван, Баочунь Ли». CiteSeerX 10.1.1.77.6402 . Цитировать журнал требует
|journal=
( помощь ) - ^ Билал, Мухаммед; и другие. (2019). "Подход сетевого кодирования для информационных сетей". Системный журнал IEEE . 13 (2): 1376–1385. arXiv : 1808.00348 . Bibcode : 2019ISysJ..13.1376B . DOI : 10.1109 / JSYST.2018.2862913 .
- ^ Ким, Минджи (2012). «Сетевой протокол TCP (CTCP)». arXiv : 1212.2291 [ cs.NI ].
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 2008-11-08 . Проверено 16 июня 2007 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ «Добро пожаловать в Безопасность сетевого кодирования - безопасное сетевое кодирование» .
- ^ http://home.eng.iastate.edu/~yuzhen/publications/ZhenYu_INFOCOM_2008.pdf [ постоянная мертвая ссылка ]
- ^ Билал, Мухаммед; и другие. (2019). "Подход сетевого кодирования для информационных сетей". Системный журнал IEEE . 13 (2): 1376–1385. arXiv : 1808.00348 . Bibcode : 2019ISysJ..13.1376B . DOI : 10.1109 / JSYST.2018.2862913 .
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 19 сентября 2013 года . Проверено 18 апреля 2013 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ Димакис, Александрос (2007). «Сетевое кодирование для распределенных систем хранения». arXiv : cs / 0702015 .
- ^ http://people.csail.mit.edu/rahul/papers/cope-ton2008.pdf
- ^ Кригслунд, Йеппе; Хансен, Йонас; Хундеболл, Мартин; Lucani, Daniel E .; Фитцек, Фрэнк HP (2013). Ядро: БОЛЬШЕ ОБРАБОТКИ в беспроводных ячеистых сетях . 77-я Конференция по автомобильным технологиям, IEEE, 2013 (весна VTC) . С. 1–6. DOI : 10.1109 / VTCSpring.2013.6692495 . ISBN 978-1-4673-6337-2.
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 11 октября 2008 года . Проверено 10 мая 2007 .CS1 maint: заархивированная копия как заголовок ( ссылка )
- ^ http://www.cs.wisc.edu/~shravan/infocom-07-2.pdf
- ^ «NetworkCoding - batman-adv - Open Mesh» . www.open-mesh.org . Проверено 28 октября 2015 .
- ^ Добро пожаловать в IEEE Xplore 2.0: Взгляд на большие сети: кодирование против очередей
- ^ Донг Нгуен; Туан Тран; Тхинь Нгуен; Бозе, Б. (2009). «Беспроводное вещание с использованием сетевого кодирования». IEEE Transactions по автомобильной технологии . 58 (2): 914–925. CiteSeerX 10.1.1.321.1962 . DOI : 10.1109 / TVT.2008.927729 .
- ^ Распространение данных в беспроводных сетях с сетевым кодированием
- ^ Коды диапазонов для энергоэффективного сетевого кодирования с приложением к мобильной потоковой передаче P2P
- Перейти ↑ Wu, Y., Liu, W., Wang, S., Guo, W., & Chu, X. (2015, июнь). Сетевое кодирование при обмене данными между устройствами (D2D), лежащих в основе сотовых сетей . В 2015 году Международная конференция по коммуникациям IEEE (ICC) (стр. 2072-2077). IEEE.
- Перейти ↑ Zhao, Y., Li, Y., & Ge, N. (2015, декабрь). Сетевое кодирование физического уровня способствует двусторонней связи между устройствами, лежащей в основе сотовых сетей . В 2015 году IEEE Global Communications Conference (GLOBECOM) (стр. 1-6). IEEE.
- ^ Abrardo А., Fodor, Г., и Тола, B. (2015, июнь). Схемы сетевого кодирования для ретрансляции на основе связи между устройствами для расширения покрытия сотовой связи . В 2015 г. состоялся 16-й международный семинар IEEE по усовершенствованию обработки сигналов в беспроводной связи (SPAWC) (стр. 670-674). IEEE.
- Перейти ↑ Gao, C., Li, Y., Zhao, Y., & Chen, S. (2017). Двухуровневый подход теории игр для совместного выбора ретранслятора и распределения ресурсов в сетевом кодировании способствует связи D2D . IEEE Transactions on Mobile Computing, 16 (10), 2697-2711.
- Перейти ↑ Zhou, T., Xu, B., Xu, T., Hu, H., & Xiong, L. (2015). Индивидуальная для пользователя схема адаптации канала для многоадресного сетевого кодирования от устройства к устройству. IET Communications, 9 (3), 367-374.
- ^ SD-WAN с сетевым кодированием в системах с множественным доступом для управления задержкой
- ^ Контроллер SD-WAN для минимизации джиттера задержки в системах с кодированным множественным доступом
- ^ «Насколько практично сетевое кодирование?». CiteSeerX 10.1.1.77.6402 . Цитировать журнал требует
|journal=
( помощь ) - ^ "XOR в воздухе" (PDF) .
- 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=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/