Испытания протокола TCP с линейным сетевым кодированием (TCP/NC)

Инженеры из Массачусетского технологического института под руководством Муриель Медард (Muriel Médard) уже много лет ведут разработку расширения TCP/NC для протокола TCP, с помощью которого можно сохранить максимальную скорость передачи данных в сетях с потерями пакетов. В первую очередь, TCP/NC планируют применять в беспроводных сетях WiFi, где потери пакетов обычно составляют 2-5%, а временами до 10%. Наконец-то дошло дело до реальных экспериментов.

Во время первых полевых испытаний TCP/NC в локальной WiFi-сети общежития МТИ (потеря пакетов 2%) средняя скорость передачи данных по WiFi выросла с 1 Мбит/с до 16 Мбит/с. Тест в поезде на большой скорости (потеря пакетов 5%) показал увеличение скорости WiFi с 0,5 Мбит/с до 13,5 Мбит/с. Это вполне совпадает с теоретическими расчётами.

Увеличение скорости возможно за счёт эффективного восстановления случайных потерь пакетов на стороне приёмника, бе�� повторной отправки этих пакетов. Восстановление пакетов осуществляется за счёт банальных математических операций, известных каждому из школьного курса алгебры, а именно — из раздела о линейных уравнениях. Алгоритм линейного сетевого кодирования сам по себе интересен, но о нём ниже. Сначала нужно понять, почему в сети резко падает скорость передачи данных при относительно небольших (2-10%) потерях пакетов.

На диаграмме показано уменьшение скорости передачи данных в сети TCP, в зависимости от количества потерянных пакетов.



Проблема TCP состоит в том, что этот протокол «тупо» воспринимает потери пакетов как признак затора (network congestion). Во времена создания TCP ещё не было WiFi и 3G, так что вполне понятно, почему разработчики сразу не применили сетевое кодирование для восстановления потерянных пакетов, хотя соответствующие алгоритмы в то время уже были разработаны и наверняка успешно применялись в армии, космической связи и разведке.

Так вот, против затора у TCP есть одно «лекарство»: уменьшение окна. Триггером для уменьшения окна являются таймаут (TO) и тройной дубликат (TD, дублирование пакета). На практике уменьшение окна приводит к тому, что скорость передачи данных искусственно занижается в десятки раз.

Использование сетевого кодирования решает проблему, восстанавливая максимально возможное количество потерянных пакетов (в идеале — все), так что отправитель не получает информации о потере (ACK), не регистрирует TD и TO, не уменьшает окно — и скорость передачи данных остаётся на прежнем уровне, что и требовалось.

На графике внизу показан теоретический расчёт скорости передачи данных TCP и TCP/NC при разном уровне потерь пакетов. Как видим, в случае TCP скорость резко снижается, а в случае TCP/NC остаётся практически на том же уровне, снижаясь примерно на оверхед сетевого кодирования (к слову, оверхед в TCP/NC совсем небольшой). Чем больше потери пакетов в TCP — тем больше эффект от сетевого кодирования.



Диаграмма от 2009 года показывает сравнение скорости передачи данных TCP и TCP/NC при разных уровнях потерь пакетов.

Основное преимущество TCP/NC состоит в том, что его можно подключить как промежуточный слой в стеке TCP/IP, ничего не меняя в самом TCP, как изображено на схеме.



Другими словами, можно внедрить TCP/ТС даже на программном уровне, установив соответствующее приложение на стороне клиента и сервера, хотя разработчики рекомендуют всё-таки реализовать поддержку TCP/NC в маршрутизаторах и других устройствах.

Алгоритм линейного сетевого кодирования

Сетевое кодирование предполагает изменение пакетов данных на промежуточных узлах, чтобы увеличить ёмкость коммуникационного канала. Принцип действия показан обычно иллюстрируют классическим примером сети «Бабочка», в которой один из узлов применяет сетевое кодирование на пакетах A и B, с помощью операции XOR получая пакет A+B. Это впоследствии позволяет восстановить отсутствующий пакет B в левом н��жнем углу и отсутствующий пакет А в правом нижнем углу. В итоге, пропускная способность сети возрастает, потому что без сетевого кодирования в такой топологии сети невозможно передать пакеты A и B одновременно за один такт обоим получателям.



В протоколе TCP/NC тоже используется сетевое кодирование по линейному уравнению. Каждый байт и каждый пакет в потоке TCP умножается на коэффициент из поля Галуа F₂₅₆ и вписывается в линейное уравнение. По сети передаются уже не пакеты, а степени свободы. Соответственно, если произошла потеря одного пакета, то можно восстановить его из известных значений, то есть из соседних пакетов. В применении к TCP этот принцип хорошо показан на иллюстрации.



Сетевое кодирование — довольно старый раздел теории информации, и существует уже много разных алгоритмов восстановления потерянных пакетов (битов). Проблема в том, что до сих пор никто не нашёл способа применять сетевое кодирование в сети TCP без сильного апгрейда оборудования и без жёстких требований к вычислительным ресурсам. Надстройка над протоколом TCP/NC, судя по всему, позволяет это сделать. Изобретатели уже зарегистрировали фирму Code On Network Coding, LLC и продают лицензии. Возможно, в ближайшее время технологию внедрят у себя многие операторы сотовой связи, так что не удивляйтесь, если после установки новой версии Android у вас внезапно интернет начнёт работать в 10 раз быстрее.

Научные работы с описанием TCP/NC
“An algebraic approach to network coding” (2003). Математическая модель линейного сетевого кодирования.
“Network coding meets TCP” (2009). Базовые принципы.
“Interfacing network coding with TCP: an implementation” (2009). Схема конкретной реализации.
“Modeling Network Coded TCP Throughput: A Simple Model and its Validation” (2010). Результаты лабораторных экспериментов.