Max Home IndustryДобавление исправления ошибок в стандартное беспроводное соединение TCP может ускорить работу на 1000%. Но это не ваш обычный код исправления ошибок, это новинка. В ходе демонстрации, проведенной командой под руководством Мюриэль Медард из Массачусетского технологического института, пропускная способность телефонного соединения выросла с 0,5 Мбит / с до 13,5 Мбит / с.
Клод Шеннон в одиночку изобрел теорию информации, и с тех пор ничего революционного не произошло. Мы можем вычислить пропускную способность любого канала, а затем просто подобрать правильную кодировку для обеспечения пропускной способности. Вы не можете добиться большего, чем пропускная способность канала, но, испортив кодировку и протокол, вы можете сделать намного хуже.
Все выглядело как решенная проблема, но сети с узлами, которые могут связываться друг с другом и передавать сообщения, создавали некоторую проблему, поскольку было трудно сделать четкое заявление о пропускной способности всей сети. Прорыв произошел в 2000 году, когда идея о том, что многоузловая сеть может преобразовывать данные, смешивая их вместе по мере их прохождения через узлы, была представлена миру Р. Алсведе, Н. Кай, С.-Й. Р. Ли и Р. В. Йунг, «Сетевой информационный поток», (IEEE Transactions on Information Theory, IT-46, pp. 1204-1216, 2000). Используя сетевое кодирование, можно определить максимальную пропускную способность многоадресных сетей.
Все это звучит загадочно, но вы можете увидеть поведение, которое приводит к интересному сетевому кодированию, в следующем каноническом примере.
Предположим, у вас есть сеть, как показано на схеме. Каждая ссылка может передать один пакет за единицу времени, и ваша проблема состоит в том, чтобы доставить пакеты A и B к узлам приемника за минимальное время.
Используя стандартную коммутацию пакетов, лучшее, что вы можете сделать, — это отправить A и B на приемный узел и в то же время использовать центральный канал для отправки A или B. Если мы отправим A, то пакетный трафик будет выглядеть так:
Вы можете видеть, что один из узлов-приемников получает A B, а другой — только A. Если вы используете отправку B по центральному каналу, то левый узел получает A B, а правый узел получает только B.
Так можно ли организовать получение обоими узлами-приемниками обоих пакетов за один шаг?
Если вы разрешите узлам формировать линейные комбинации пакетов и передавать их вместо исходных пакетов, тогда да, вы можете. Если первый центральный узел передает не A или B, а A + B, то мы имеем:
Теперь узлы-приемники могут получить A и B одновременно, вычитая A из A + B и B из A + B.
В этом суть сетевого кодирования. Передавая линейные комбинации пакетов, вы можете улучшить общую информацию, передаваемую в многоадресной системе.
В последней работе используется случайное линейное сетевое кодирование, которое является немного более продвинутым. Все, что мы делаем в этом случае, — это позволяем каждому узлу формировать случайные линейные комбинации пакетов. Для этого узел выбирает случайные коэффициенты, а затем использует их для формирования линейных комбинаций пакета. Каждый узел также добавляет коэффициенты к заголовкам пакетов и затем отправляет их по пути. Узлы-приемники больше не получают исходные пакеты, а получают линейные комбинации. Извлекая коэффициенты, узлы-приемники могут построить матрицу, которая представляет преобразование, которому были подвергнуты исходные пакеты. Все, что нужно сделать узлу-приемнику, — это инвертировать матрицу и умножить, чтобы восстановить исходные пакеты. (На практике уравнения решаются методом исключения Гаусса, который выполняется быстро.)
Причина, по которой это работает лучше, чем просто отправка исходных пакетов, заключается в том, что узлы-приемники просто должны ждать, пока у них не будет неособой матрицы коэффициентов, а затем они смогут восстановить данные. Пока отправлено достаточное количество линейных комбинаций, это, вероятно, произойдет с высокой вероятностью, даже если некоторые пакеты будут потеряны. Накладные расходы просто связаны с отправкой дополнительных пакетов и крошечной дополнительной памяти, необходимой для коэффициентов. Это больше похоже на исправление стирания пакетов, чем на исправление ошибок, поскольку пропущенные потерянные пакеты не мешают восстановлению исходных пакетов.
На этом этапе вы могли бы подумать, что включение в пакеты некоторого вида исправления ошибок было бы хорошей идеей, но это потребует небольшого изменения в протоколе TCP. TCP — не лучший протокол для ненадежного канала. Он отправляет пакеты по одному и полагается на получателя для их подтверждения. Если какие-либо пакеты пропадают, приемник сигнализирует об этом, и передатчик отправляет пакет снова.
По проводным соединениям это работает достаточно хорошо, потому что теряется мало пакетов, и обычно проблема заключается в перегрузке сети, от которой, как правило, помогает замедление работы. Однако в беспроводных сетях, особенно в телефонных сетях, потеря пакетов является обычным явлением. В этом случае происходит то, что пропускная способность сети тратится на повторную отправку пакетов и на подтверждение связи, необходимое для запроса повторной отправки. По мере увеличения потерь пакетов фактическая полезная пропускная способность сети быстро падает. Даже совсем небольшой процент потери пакетов может снизить пропускную способность соединения до 10% от его значения.
В последних тестах, проведенных профессором Исследовательской лаборатории электроники Массачусетского технологического института Мюриэль Медард, использовалась установка Amazon EC2 для передачи сетевых кодированных пакетов на их мобильные телефоны в поезде Acela из Нью-Йорка в Бостон, который известен плохим приемом. Кодирование увеличило эффективную пропускную способность с 0,5 Мбит / с до 13,5 Мбит / с. Улучшения было достаточно, чтобы смотреть видео на YouTube, в то время как другие пассажиры изо всех сил пытались подключиться к сети.
Фактические детали используемых методов кодирования являются секретными, и была создана компания для заключения лицензионных сделок. Предположительно, в будущем кодирование может быть встроено в маршрутизаторы и телефоны, в результате чего программное обеспечение будет по-прежнему полагать, что оно использует устаревший, неэффективный, неизмененный TCP.
Конечно, как это улучшение будет масштабироваться, если каждый пользователь будет подключен с использованием сетевого кодирования — это другой вопрос. В принципе, сетевое кодирование означает, что TCP можно значительно улучшить, но с небольшими изменениями.