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


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

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

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

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

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

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

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

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

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

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

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

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

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


Похожие новости:

Пакеты с логотипом в Саратове: особенности рекламной продукции

Пакеты с логотипом в Саратове: особенности рекламной продукции
Полиэтиленовые пакеты встречаются в магазинах и в каждом доме. Сегодня достаточно трудно представить свой быт и совершение покупок без привычных всем изделий из полиэтилена. Речь идет о пакетах

Теория кодирования

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

Media-independent handover

Media-independent handover
Медиа-независимая передача (MIH) представляет собой стандарт, разработанный IEEE 802.21 для передачи IP — сессии от одной технологии доступа уровня 2 к другому, чтобы достичь мобильности устройств

Алгоритм текущего ведра

Алгоритм текущего ведра
Алгоритм маркерной корзины (англ. Token Bucket Algorithm) — алгоритм, позволяющий ограничить полосу пропускания канала и в то же время гарантировать некоторую скорость передачи данных (кадров или
Комментариев пока еще нет. Вы можете стать первым!

Добавить комментарий!

Ваше Имя:
Ваш E-Mail:
Введите два слова, показанных на изображении: *
Популярные статьи
Почему ремонт общественных зданий важен для эффективной эксплуатации
Почему ремонт общественных зданий важен для эффективной эксплуатации
Зачем ремонтировать общественные здания? Этот вопрос волнует многих, ведь общественные здания – это...
Охранное предприятие в Москве – защита и надежность
Охранное предприятие в Москве – защита и надежность
В современном мире, где угрозы личной безопасности и сохранности имущества становятся все более...
Особенности выбора мебели: секреты правильного подбора для интерьера
Особенности выбора мебели: секреты правильного подбора для интерьера
При обустройстве интерьера дома или офиса одним из самых важных аспектов является выбор мебели....
Все новости