Как сетевое кодирование может повысить эффективность пропускной способности каналов в ячеистых сетях

На сети Mesh все чаще полагаются для обеспечения надежной, масштабируемой беспроводной связи, особенно в средах, где централизованная инфраструктура недоступна или непрактична. Позволяя узлам напрямую связываться друг с другом в децентрализованной сети, топологии mesh естественным образом сопротивляются отдельным точкам отказа и адаптируются к меняющимся условиям. Однако по мере того, как число подключенных устройств и объем трафика данных продолжают расти, возникает постоянное узкое место: эффективная пропускная способность канала. Традиционные подходы к управлению потоком данных в сетях mesh часто оставляют значительную пропускную способность недостаточно используемой или подверженной перегрузке. Одним из перспективных решений этой проблемы является сетевое кодирование, техника, которая коренным образом меняет способ передачи и ретрансляции данных. Благодаря интеллектуальному объединению нескольких потоков данных в промежуточных узлах сетевое кодирование может значительно улучшить эффективную пропускную способность канала, не требуя дополнительных физических ресурсов.

Что такое сетевое кодирование?

Сетевое кодирование — это метод передачи данных, который выходит за рамки традиционной парадигмы «хранить и пересылать». Вместо того, чтобы просто получать пакет и передавать его в неизменном виде, узел, который выполняет сетевое кодирование, объединяет несколько входящих пакетов в один кодированный пакет с использованием алгебраических операций (обычно по конечному полю, такому как GF(28) или GF(216)). Получатель затем использует набор кодированных пакетов вместе со знанием коэффициентов кодирования для декодирования и восстановления исходных данных. Этот подход был впервые формализован Рудольфом Ахлсведе, Нин Кай, Шуо-Йен Роберт Ли и Раймондом Йеунгом в основополагающей статье 2000 года, и с тех пор он широко исследовался как для проводных, так и для беспроводных сетей.

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

Как сетевое кодирование улучшает пропускную способность канала

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

Снижение избыточности передачи

Рассмотрим простой сценарий с двумя потоками, когда узел А хочет отправить данные в узел В, а узел В хочет отправить данные в узел А, причем оба потока проходят через промежуточное реле R. При традиционной маршрутизации R должен пересылать каждый пакет из А в В и из В в А отдельно, потребляя два временных интервала (или частотные интервалы). При сетевом кодировании R может XOR два входящих пакета вместе и транслировать один комбинированный пакет. Оба A и B могут затем декодировать пакет с использованием своих собственных данных (поскольку они знают, что они первоначально отправили). Это сокращает количество передач вдвое, освобождая время канала для другого трафика или уменьшая задержку. Более сложные сценарии с несколькими потоками и несколькими реле могут достигать еще больших сокращений.

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

Расширение пропускной способности сети

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

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

Повышение устойчивости к потерям и неудачам

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

Типы сетевого кодирования, относящиеся к ячеистым сетям

Не все схемы сетевого кодирования одинаково подходят для динамической, распределенной природы ячеистых сетей.

Для более глубокого теоретического обоснования статья Wikipedia о сетевом кодировании дает отличный обзор. Для практических реализаций в беспроводных системах настоятельно рекомендуется исследовательский документ «COPE: подход к сетевому кодированию беспроводных сетей» Katti et al. (2007).

Практические преимущества в развертывании ячеистой сети

Теоретические преимущества сетевого кодирования приводят к ощутимым преимуществам в реальных сетях сетки. Вот некоторые из наиболее эффективных преимуществ:

Сетевые операторы, развертывающие ячеистые сети для интеллектуальных городов, промышленного IoT или военных коммуникаций, часто видят немедленные выгоды при интеграции сетевого кодирования в транспортный уровень. Например, развертывание сетевого кодирования в беспроводном обратном направлении NTT продемонстрировало до 40% улучшение пропускной способности в реалистичных условиях.

Проблемы и ограничения

Несмотря на свои преимущества, сетевое кодирование не является «серебряной пулей». Принятие в ячеистых сетях должно учитывать несколько практических проблем:

Вычислительные накладные расходы

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

Пакет сверху

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

Безопасность и целостность

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

Совместимость и стандартизация

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

Практические стратегии реализации

Для инженеров и системных архитекторов, рассматривающих сетевое кодирование в ячеистых сетях, несколько стратегий развертывания могут максимизировать преимущества при одновременном смягчении проблем:

  • Использовать внутрипотоковое кодирование — Начните с простого блочного кодирования в пределах одного потока.Это проще интегрировать и отлаживать, чем межпотоковое кодирование.
  • Адаптивный размер блока — Корректируйте количество пакетов на блок на основе условий канала и вычислительной мощности.Меньшие блоки уменьшают задержку и накладные расходы на шумные каналы; большие блоки повышают эффективность на стабильных ссылках.
  • Модульная интеграция — Реализуйте сетевое кодирование как слой шима между транспортным и сетевым слоями, чтобы его можно было вводить без переписывания всего стека. Многие исследовательские прототипы используют «сетевую структуру кодирования», которая перехватывает пакеты.
  • Использовать спаривание — В случайном линейном кодировании используйте векторы с разреженными коэффициентами (т.е. большинство коэффициентов равны нулю) для снижения как накладных расходов на вычисления, так и коэффициентов. Это особенно эффективно для больших блоков и высоких скоростей передачи данных.
  • Комбинируйте с расширенным планированием — Сетевое кодирование работает лучше всего, когда уровень MAC знает о возможностях кодирования. В сетке централизованный планировщик (если это возможно) или распределенный оппортунистический планировщик может расставлять приоритеты передач, которые позволяют кодировать.

Реальные приложения

Сетевой кодирование перешло от академической теории к практическому внедрению в нескольких областях:

  • Спутники с ограниченной мощностью и пропускной способностью используют сетевое кодирование для объединения нескольких потоков от наземных терминалов, повышая спектральную эффективность. Стандарт DVB-S2X включает в себя дополнительные расширения сетевого кодирования для обратных каналов.
  • Мобильные специальные сети (MANET) — Военные и аварийно-спасательные команды полагаются на MANET, которые часто включают сетевое кодирование для поддержания связи в деградированных условиях. Например, тестовая стенда сетевого кодирования армии США показала 50% улучшение пропускной способности в сценариях сетки транспортных средств.
  • Беспроводные сенсорные сети — Системы экологического мониторинга и сельскохозяйственные IoT-системы используют сетевое кодирование для агрегирования данных от многих датчиков через сетку, уменьшая количество передач и продлевая срок службы батареи.
  • Распределение контента — В городских сетях сетки, которые предлагают публичный Wi-Fi, сетевое кодирование помогает распространять популярный контент (например, обновления программного обеспечения, карты) для многих пользователей одновременно.

Всесторонний обзор реализаций можно найти в «Сетевой кодинг для беспроводных сетей сетки: Обзор» по А. Аль-Нуайми и др. (2013) .

Будущие направления и выводы

По мере распространения ячеистых сетей, управляемых умными домами, промышленной автоматизацией и 5G-Advanced Integrated Access/backhaul, спрос на более высокую эффективную пропускную способность каналов будет только усиливаться. Сетевое кодирование будет играть ключевую роль не только в увеличении пропускной способности, но и в обеспечении новых функций, таких как сетевое нарезка и кодированное кэширование. Продолжающиеся исследования в области кодирования сетей физического уровня, которое использует суперпозицию сигнала над воздухом, обещает еще больший прирост пропускной способности. Между тем, машинное обучение изучается для оптимизации параметров кодирования и планирования в режиме реального времени.

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

Для дальнейшего чтения, фундаментальная статья по Ahlswede et al. (2000) остается отличной отправной точкой. Практические реализации хорошо документированы в Microsoft Research бумаги по практическому сетевому кодированию.