Испытания протокола 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). Результаты лабораторных экспериментов.

Автор: alizar