Испытания протокола 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 умножается на коэффициент из поля Галуа F256 и вписывается в линейное уравнение. По сети передаются уже не пакеты, а степени свободы. Соответственно, если произошла потеря одного пакета, то можно восстановить его из известных значений, то есть из соседних пакетов. В применении к 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). Результаты лабораторных экспериментов.
    Support the author
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 34

      –6
      <Радостные вопли хомячка>
      «Ура-ура, я смогу во дворе смотреть сериалы, пока ребёнка гуляет!»
      </Радостные вопли хомячка>

      *Это было к тому что в нашем дворе мамаши собираются вокруг одной с планшетом и смотрят сериалы у неё, потому что её йпад более-менее видит домашний вифи, а у остальных сигнал слишком слабый.
        0
        Я так понимаю, что оверхед дополнительного трафика (необходимого для избыточного кодирования) оправдан значительно бОльшим оверхедом от TO и TD при потерях в указанных процентах?

        И, кстати, по оверхеду трафика для избыточного кодирования — сколько получается?
          +1
          Я не совсем понял. Для использования этого протокола необходим апгрэйд ПО на всем оборудовании между конечными точками или достаточно поставить его на конечные точки?
            0
            Как я понял, речь идет об относительно менее надежных сетях, типа WiFi и 3G, по сравнению с куском меди или оптоволокна, соответственно, главное обеспечить надежность передачи между роутером и устройством или оператором 3G и устройством, а это всего две точки сочленения, они же и оконечные, а дальше пакеты и так будут идти по надежным каналам (за роутером или оператором)… Но со временем, конечно, апгрейд может распространиться по всей инфраструктуре…
              +5
              Роутеру оператора глубоко плевать на протоколы TCP/UDP.

              Новый прокол должен поддерживаться только на стороне клиента и на стороне сервера. Инфраструктуру оператора эти изменения не задевают.
                0
                А, ну, да, логично, ведь это отправляющая сторона инициирует снижение скорости. Согласен.
                  +2
                  Не всегда. Оператору может и наплевать, а в корпоративных сетях полно фишек, когда TCP перехватывается по сути или хотя бы инспектируется. Оптимизаторы для WAN каналов типа cisco WAAS, банальный TCP Intercept и inspect. Всякие IDS и IPS, полноценные statefull файрволы, которые отслеживают корректность TCP потока. Все это добро должно будет понимать новые фичи протокола. Иначе от алармов, до дропов.
              +3
              Что-то я в диаграму не очень врубился… Нужно послать 3 «символа». Вместо того, чтоб послать каждый в отдельности, посылается 3 разных линейных комбинации. Одна теряется. Остается 2 уравнения на 3 неизвестных. И?
              Нужен тот самый overhead — одна «лишняя» комбинация (ну или 1 на 10 при потерях в 10%), чтоб восстановить все символы при потере любого.

              Или я что-то не правильно понял?
                0
                > Нужен тот самый overhead — одна «лишняя» комбинация (ну или 1 на 10 при потерях в 10%), чтоб восстановить все символы при потере любого.

                Все правильно. Для таких дел обычно используется Reed-Solomon encoding.
                  0
                  Forward error correction в спутниковой связи. Имплементирован уже очень давно. Не на четвёртом, а на втором уровне, правда. Но результат практически тот же самый. Ну и там 1 лишний бит на 10 это best case scenario :)
                    0
                    > Forward error correction в спутниковой связи.
                    Кодировка Хамминга? Вроде она много где еще используется (e.g. DSL).

                    Но насколько я знаю она не защищает от полной потери пакета. Reed-Solomon разбивает пакеты на группы и добавляет дополнительные пакеты которые могут использоватся в случае потери основных.
                      0
                      Про DSL не знаю, но вполне возможно.
                      Да, вы правы, она защищает от отдельных битых битов (пардон за каламбурчик). Если пакет теряется полностью — второй уровень не спасёт.
                    0
                    А если так подумать, то в сам 802.11 этот механизм тоже встроен.
                      0
                      вы ведь не CSMA/CA имеете ввиду?
                        0
                        Нет конечно, я имею в виду forward error correction.
                    0
                    Желали послать два символа, послали три. Любой пропал — два исходных можно восстановить.
                      0
                      На диаграме сивола 3 — p1, p2, p3.
                    0
                    Извините, мимо кассы.
                      –1
                      Еще один уровень абстракции в многострадальный TCP/IP стек? WeNeedToGoDeeper.jpg

                      Почему ошибки datalink layer решаются на уровне transport layer? Правильно было бы решить это в самом wifi. 802.11 содержит возможность retransmit пакет в случае ошибки. Я не знаю что делает 802.11 в случае потери пакета, но если это такая большая проблема, то не вижу причин почему 802.11 не может переслать пакет и в это случае.

                      PS по ссылкам не ходил :) но зная ализара — стоило бы это сделать
                        +1
                        802.11 в случае потери пакета делает тоже самое что и ethernet — выкидавает и забывает. Но в нём есть механизм исправления ошибок. Просто, видимо, работает кривовато. Думается мне, что из-за того, что SNR сигнала очень сильно меняется и кодировка не успевает. Если работаем в 64QAM 5/6, и вдруг сосед за стенкой начинает вещать, или просто телефон двигается с места на место — SNR падает, кодировка оказывается слишком высокая чтоб исправить все ошибки и в итоге она становится пониже. Но фрейм-то уже убежал, а значит TCP роняет window size.
                          0
                          > 802.11 в случае потери пакета делает тоже самое что и ethernet — выкидавает и забывает.

                          Мне казалось что 802.11 имеет acknowledgement и делает retransmition, но я могу ошибатся.
                            0
                            At the end of every packet the receiver, if it has successfully received the packet, will return an ACK packet (if not received or received with errors the receiver will NOT respond i.e. there is no NACK). The transmit window allows for the ACK i.e. CONTENTION period starts after the ACK should have been sent.

                            www.zytrax.com/tech/wireless/802_mac.htm

                            Ваша правда, я ошибся.
                        0
                        At the end of every packet the receiver, if it has successfully received the packet, will return an ACK packet (if not received or received with errors the receiver will NOT respond i.e. there is no NACK). The transmit window allows for the ACK i.e. CONTENTION period starts after the ACK should have been sent.

                        www.zytrax.com/tech/wireless/802_mac.htm

                        Ваша правда, я ошибся.
                          0
                          «Так вот, против потери пакета у TCP есть два «лекарства»: таймаут (TO) и тройной дубликат (TD, дублирование пакета).»

                          Это не лекарства, это средства детектировать проблемы. Таймаут — мы ждем аск на отправленный сегмент слишком долго и не дожидаемся (RTO). Тройной дубликат (или более) — нам пришло три (или более) аск подряд, это значит удаленная сторона определила нарушение порядка следования и «долбит» нас аск с последовательностью, после которой она ожидает корректных данных.
                          А лекарством является уменьшение CWND (окна перегрузки) и ssthresh (порога медленного старта или какого-то другого, более оптимального алгоритма подавления перегрузки), причем для разных реализаций протокола алгоритмы разные. Есть оптимизированные для WAN каналов, для спутниковых, для выскопроизводительных ЛВС и т.д. Так что не надо диагностику путать с лекарством.
                            0
                            «Так вот, против потери пакета у TCP есть два «лекарства»: таймаут (TO) и тройной дубликат (TD, дублирование пакета)»

                            Вижу, в статье поправили эту фразу :)

                            Но все равно неточно получилось. TCP ничего не знает о пропускной способности канала, достижение предела пропускной способности для него нормально, это способ «разогнаться». В итоге возникают потери и это тоже нормально. Производительность при этом в десятки раз не падает. У вас на 100мбит линке TCP работает только на 10мбит? Кто настраивал полисеры, тот знает, что кроме баловства burst-ом можно просто 10-15% накинуть к полосе, что бы TCP в итоге вышел на нужную скорость.
                            Проблема в том, как верно замечено в другом месте статьи, что при случайных потерях TCP действует так же, как при перегрузке, а это неверно. Одну ситуацию от другой он не может отличить, у него признаков для этого нет. Поэтому при случайных потерях, тем более существенных такая деградация. Если бы он мог отличить один случай от другого, то даже без хитрого кодирования, просто за счет повторной передачи со всеми вытекающими доп. задержками (но без изменения окна и других переменных!), ситуация бы не превращалась в такую печальную.

                            0
                            Интересный материал, но не раскрыт толком вопрос, почему именно потери НЕ связанные с перегрузкой так сильно влияют на производительность. При перегрузке пакеты тоже теряются, однако механизмы, описанные мной в сообщении выше подстраиваются под «планку», чем бы она ни была обусловлена — физикой, полисером, и подстраиваются, особенно для новых реализаций TCP/IP весьма не плохо. Характерная пила не такая амплитудная получается и вообще.
                            Но ошибки передачи, связанные с физикой/средой, случайные по сути не исчезают при уменьшении CWND, могут проявляться в любой стадии медленного ли старта, быстрой ли ретрансмиссии, что и «гасит» так сильно производительность. В этом дело, а не просто в накладных расходах на повторные передачи. В ситуации обычной перегрузки TCP «осаживается» алгоритмом устранения этой самой перегрузки и потери исчезают, но если потери не ей (перегрузкой) обусловлены, он «осаживается» к месту и не к месту. Отсюда такие дикие результаты, как десятикратная потеря в пропускной способности всего при нескольких % потерь.
                            И описанная в статье фишка — не единственный способ борьбы с этим явлением.

                            Одна из идей — скрывать от уровня TCP ошибки, связанных с физикой.
                            Другая идея — уведомлять TCP о причинах потерь.

                            Подробнее можно почитать тут

                            Влияние ошибок передачи на производительность TCP

                            ru.scribd.com/doc/86168682/30/%D0%92%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5-%D0%BE%D1%88%D0%B8%D0%B1%D0%BE%D0%BA-%D0%BF%D0%B5%D1%80%D0%B5%D0%B4%D0%B0%D1%87%D0%B8-%D0%BD%D0%B0-%D0%BF%D1%80%D0%BE%D0%B8%D0%B7%D0%B2%D0%BE%D0%B4%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C-TCP
                              0
                              «Увеличение скорости возможно за счёт эффективного восстановления случайных потерь пакетов на стороне приёмника, без повторной отправки этих пакетов.»

                              «Во время первых полевых испытаний TCP/NC в локальной WiFi-сети общежития МТИ (потеря пакетов 2%) средняя скорость передачи данных по WiFi выросла с 1 Мбит/с до 16 Мбит/с. „

                              Простая математика. Без потерь скорость была бы 16мбит. Теряется 2% всех пакетов, пусть каждый будет 1460 байт — по максимуму. Даст ли только это 10 кратное уменьшение скорости? Нет. Скорость так сильно падает, потому что при повторяющихся потерях TCP уменьшает окно, если же при его уменьшенном значении опять потеря? Якобы опять перегрузка и окно снова уменьшается и снова попытка разогнаться. И так постоянно, а не только на границе пропускной способности, как при нормальной ситуации с перегрузкой, отсюда такая деградация во многие разы.

                              с. 48 в указанной мной ссылке описывает механизм и мат. зависимость от вероятности потерь
                                0
                                В принципе, избыточное кодирование и восстановление фреймов можно внедрять на любом уровне, вплоть до L1. Собственно, на L1 оно и так широко применяется (но оперирует микрофреймами, типа октетов, кодирующихся 10-ю битами). Выбор TCP уровня вполне оправданный, изменения в нем (теоретически) не затрагивают текущую сетевую инфраструктуру, и в то же время максимально широко охватывают все причины потерь, т.е. на всех уровнях, например, из-за переполнения очереди интерфейса, где L1/L2 ничего не смогут исправить…

                                Иллюстрация к протоколу на самом деле не совсем корректная, в ней не указывается, что сначала надо передать избыточные данные p0, p0+p1, p0+p1+p2, и только после этого можно выйти на стабильный режим передачи p[i]+p[i+1]+p[i+2], корректируя задетектированные потери новыми избыточными пересылками необходимых сумм. И без соотв поддержки в сетевухах это будет немного напряжно для проца, хотя овчинка выдержки стоит однозначно…

                                И что-то не понятна ситуация с внедрением NC поверх немодифицированного TCP — что-то сильно маркетингом попахивает, ведь TCP все равно будет пытаться доставить порученный ему поток данных, исправно пересылая потерянные пакеты и занижая соотв скорость, даром что уровень сверху смог бы восстановить поток и без пересылки потерянного пакета.
                                  0
                                  Во-во, деградация ведь не столько от необходимости повторной передачи зависит, сколько от действия алгоритма борьбы с перегрузкой. Производительность от уменьшения окна сильно падает и от того, на сколько шустро окно потом будем повышать. Если обертка будет немодифицированный TCP — все те же яйца.
                                    0
                                    И что-то не понятна ситуация с внедрением NC поверх немодифицированного TCP


                                    Могу ошибаться, но это TCP поверх NC. На схеме Encoder ниже Sender TCP. Да и есть аналогия TCP/IP — TCP/NC.

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


                                    NC возможно будет препятствовать отправлению этих пакетов или вообще ACK подсунет.
                                    0
                                    Странно, что только сейчас начали полевые испытания. На самом деле, на рынке давно уже есть устройства, в которых реализован алгоритм Forward Error Correction — это WAN оптимизаторы от Silver Peak. Они есть в виде железок и виртуальных машин и оптимизируют трафик на транспортном уровне(TCP и UDP).

                                    Они действительно считают, что основная проблема для TCP — это постоянно уменьшающееся cwnd в сетях(постоянные ACKи повышают latency), где существует перегрузка(TCP считает перегрузкой все) и декларируют, что могут растягивать окно до 1Гб именно за счет FEC, ну и также SACK.

                                    И я даже видел практически такие же графики где-то у них.
                                      0
                                      кстати вот здесь есть статья и комментарии с ответами самой Муриель Медард:

                                      www.technologyreview.com/news/429722/a-bandwidth-breakthrough/
                                        0
                                        Делают из пакетов нечто типа RAID — массива? Классная идея, естественный вопрос — почему только теперь.
                                          0
                                          Где можно скачать это приложение :)?

                                          Only users with full accounts can post comments. Log in, please.