КоДел

CoDel ( контролируемая задержка ; произносится « няня ») — алгоритм активного управления очередью (AQM) в сетевой маршрутизации , разработанный Ван Джейкобсоном и Кэтлин Николс и опубликованный как RFC8289. ^[1] Он предназначен для преодоления раздувания буфера в сетевом оборудовании , таком как маршрутизаторы , путем установки ограничений на задержку сетевых пакетов при их прохождении через буферы в этом оборудовании. CoDel стремится улучшить общую производительность алгоритма случайного раннего обнаружения (RED) за счет устранения некоторых его фундаментальных заблуждений, как считает Джейкобсон, и за счет упрощения управления.

В 2012 году Дэйв Тяхт и Эрик Дюмазет написали реализацию CoDel для ядра Linux и получили двойную лицензию: GNU General Public License и трехпунктовую лицензию BSD . Улучшение CoDel от Dumazet называется FQ-CoDel , что означает «Fair/Flow Queue CoDel»; Впервые он был принят в качестве стандартного решения AQM и планирования пакетов в 2014 году в выпуске OpenWrt 14.07 под названием «Barrier Breaker». Оттуда CoDel и FQ-CoDel мигрировали в различные последующие проекты, такие как Tomato , dd-wrt , OPNsense и Ubiquiti функцию «Smart Queues» .

Теория [ править ]

CoDel основан на наблюдениях за поведением пакетов в сетях с коммутацией пакетов под воздействием буферов данных . Некоторые из этих наблюдений касаются фундаментальной природы организации очередей и причин раздувания буфера , другие относятся к слабостям альтернативных алгоритмов управления очередями. CoDel был разработан как попытка решить проблему раздувания буфера. ^[2]

Буферраздувание [ править ]

Поток пакетов замедляется при прохождении через сетевое соединение между быстрой и медленной сетью, особенно в начале сеанса TCP , когда происходит внезапный всплеск пакетов и более медленная сеть может быть не в состоянии быстро принять этот пакет. достаточно. Существуют буферы, которые облегчают эту проблему, предоставляя быстрой сети место для хранения пакетов, которые будут читаться более медленной сетью в своем собственном темпе. ^[3] Другими словами, буферы действуют как амортизаторы, преобразуя скачкообразные поступления в плавные, устойчивые отклонения. Однако буфер имеет ограниченную емкость. Идеальный буфер имеет такой размер, чтобы он мог справиться с внезапным всплеском данных и сопоставить скорость этого всплеска со скоростью более медленной сети. В идеале амортизирующая ситуация характеризуется временной задержкой пакетов в буфере во время пакета передачи, после чего задержка быстро исчезает и сеть достигает баланса в предложении и обработке пакетов. ^[3]

Алгоритм управления перегрузкой TCP основан на отбрасывании пакетов для определения доступной пропускной способности между двумя взаимодействующими устройствами. Он ускоряет передачу данных до тех пор, пока пакеты не начнут теряться, а затем замедляет скорость передачи. В идеале он продолжает ускоряться и замедляться, пока находит равновесие на скорости соединения. Чтобы это работало, отбрасывание пакетов должно происходить своевременно, чтобы алгоритм мог оперативно выбрать подходящую скорость передачи. Пакеты, хранящиеся в слишком большом буфере, дойдут до места назначения, но с более высокой задержкой , но пакеты не будут отброшены, поэтому TCP не замедляется. В этих условиях TCP может даже решить, что путь соединения изменился, и повторить поиск нового равновесия. ^[4]^[5]

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

Хорошие и плохие очереди [ править ]

CoDel различает два типа очередей: ^[3]^[6] — Хорошая очередь это та, в которой нет раздутия буфера. Всплески связи вызывают не более чем временное увеличение задержки в очереди. Максимальное использование сетевых каналов. приводит Плохая очередь к раздуванию буфера. Всплески связи приводят к тому, что буфер заполняется и остается заполненным, что приводит к низкому использованию и постоянно высокой задержке буфера. Чтобы быть эффективным против раздувания буфера, решение в виде алгоритма активного управления очередью (AQM) должно быть в состоянии распознавать возникновение раздувания буфера и реагировать путем применения эффективных контрмер.

Ван Джейкобсон утверждал в 2006 году, что существующие алгоритмы используют неверные способы распознавания раздувания буфера. ^[5] Алгоритмы, подобные RED, измеряют среднюю длину очереди и рассматривают это как случай раздувания буфера, если среднее значение становится слишком большим. Джейкобсон продемонстрировал в 2006 году, что это измерение не является хорошим показателем, поскольку средняя длина очереди резко возрастает в случае всплеска связи. В этом случае очередь может быстро исчезнуть (хорошая очередь) или превратиться в постоянную очередь (плохая очередь). Другие факторы сетевого трафика также могут вызывать ложноположительные или отрицательные результаты, что приводит к ненужному применению контрмер. Джейкобсон предположил, что средняя длина очереди на самом деле не содержит никакой информации о потребности в пакетах или загрузке сети. ^[3]^[5] Он предположил, что лучшим показателем может быть минимальная длина очереди в течение скользящего временного окна. ^[3]

Алгоритм [ править ]

Основываясь на идее Джейкобсона 2006 года, CoDel был разработан для управления очередями с контролем минимальной задержки, которую испытывают пакеты в рабочем окне буфера. Цель состоит в том, чтобы сохранить эту минимальную задержку ниже 5 миллисекунд. Если минимальная задержка становится слишком высокой, пакеты удаляются из очереди до тех пор, пока задержка не упадет ниже максимального уровня. ^[3] Николс и Джейкобсон приводят несколько преимуществ использования только этого показателя: ^[3]

CoDel не имеет параметров. Одним из недостатков алгоритма RED (по мнению Джейкобсона) является то, что его слишком сложно настроить, особенно в среде с динамическими скоростями соединения.
CoDel по-разному обрабатывает хорошую и плохую очередь. Хорошая очередь по своей природе имеет низкие задержки, поэтому алгоритм управления может ее игнорировать, тогда как плохая очередь подвергается вмешательству управления в виде отбрасывания пакетов.
CoDel работает на основе параметра, который определяется полностью локально; Он не зависит от задержек в обоих направлениях, скорости соединения, нагрузки трафика и других факторов, которые не могут контролироваться или прогнозироваться локальным буфером.
Локальную минимальную задержку можно определить только тогда, когда пакет покидает буфер, поэтому дополнительная задержка для запуска очереди и сбора статистики для управления очередью не требуется.
CoDel адаптируется к динамически изменяющейся скорости соединения без негативного влияния на использование.
Реализация CoDel относительно проста и поэтому может охватывать спектр от недорогих домашних маршрутизаторов до высокопроизводительных решений маршрутизации.

CoDel не делает ничего для управления буфером, если минимальная задержка для окна буфера ниже максимально допустимого значения. Он также ничего не делает, если буфер относительно пуст (если . в буфере содержится менее одного байта MTU) ^[3] Если эти условия не выполняются, CoDel вероятностно отбрасывает пакеты. ^[3]

Алгоритм вычисляется независимо на каждом сетевом узле . Алгоритм работает в течение интервала , первоначально 100 миллисекунд. каждого пакета Задержка в очереди отслеживается на протяжении всего перехода. Поскольку каждый пакет выводится из очереди для пересылки , рассчитывается задержка в очереди (время, в течение которого пакет находился в ожидании в очереди). Сохраняется наименьшая задержка в очереди за интервал. Когда последний пакет интервала выводится из очереди, если наименьшая задержка в очереди для интервала превышает 5 миллисекунд, этот одиночный пакет отбрасывается, а интервал, используемый для следующей группы пакетов, сокращается. Если наименьшая задержка в очереди для интервала составляет менее 5 миллисекунд, пакет пересылается, и интервал сбрасывается до 100 миллисекунд.

При сокращении интервала это делается в соответствии с обратным квадратным корнем из числа последовательных интервалов, в которых пакеты были отброшены из-за чрезмерной задержки в очереди. Последовательность интервалов $100$ , ${100 \over {\sqrt {2}}}$ , ${100 \over {\sqrt {3}}}$ , ${100 \over {\sqrt {4}}}$ , ${100 \over {\sqrt {5}}}$ ...

Результаты моделирования [ править ]

CoDel был протестирован в симуляционных тестах Николсом и Джейкобсоном при различных MTU, скоростях соединения и других вариантах условий. В целом результаты показывают: ^[3]^[7]

По сравнению с RED, CoDel поддерживает задержку пакетов ближе к целевому значению во всем диапазоне полос пропускания (от 3 до 100 Мбит/с). Измеренное использование канала стабильно составляет около 100 % пропускной способности канала.
При более низком MTU задержки пакетов ниже, чем при более высоком MTU. Более высокий MTU приводит к хорошему использованию канала, более низкий MTU приводит к хорошему использованию канала при более низкой пропускной способности, а при высокой пропускной способности снижается до справедливого использования.

Моделирование также выполняли Грег Уайт и Джои Падден из CableLabs . ^[8]

Реализация [ править ]

Полная реализация CoDel была реализована в мае 2012 года и стала доступна как программное обеспечение с открытым исходным кодом . ^[3] Он был реализован в ядре Linux (начиная с основной версии 3.5). ^[9] Дэйв Тяхт перенес CoDel на ядро Linux 3.3 для проекта CeroWrt , который, помимо прочего, занимается буферизацией, ^[10] где он был тщательно протестирован. CoDel начал появляться в качестве опции в некоторых проприетарных платформах управления полосой пропускания «под ключ» в 2013 году. ^[11] Во FreeBSD CoDel был интегрирован в версию 11.x. ^[12] и 10.х ^[13] ветки кода в 2016 году. ^[14] Реализация распространяется вместе с OpenBSD, начиная с версии 6.2. ^[15]

Производные алгоритмы [ править ]

CoDel Fair/Flow Queue (FQ-CoDel; fq_codel в коде Linux) добавляет в CoDel организацию очереди потоков, что позволяет различать несколько одновременных подключений и работать справедливо. Он дает приоритет первому пакету в каждом потоке, поэтому небольшие потоки могут начинаться и заканчиваться быстрее для более эффективного использования сетевых ресурсов. Соавтор CoDel Ван Джейкобсон рекомендует использовать fq_codel вместо codel там, где он доступен. ^[16] FQ-CoDel опубликован как RFC8290. Его написали Т. Хойланд-Йоргенсен, П. Маккенни, Д. Тяхт, Дж. Геттис и Э. Дюмазе, все участники «проекта раздувания буфера». ^[17]

Common Applications Kept Enhanced (CAKE; sch_cake в коде Linux) — это комбинированный формирователь трафика и алгоритм AQM, представленный проектом bufferbloat в 2018 году. Он основан на опыте использования fq_codel с формирователем трафика HTB (Hierarchy Token Bucket) . Он превосходит реализацию htb+fq_codel в Linux за счет уменьшения коллизий хэшей между потоками, снижения использования ЦП при формировании трафика и ряда других способов. ^[18]

В 2022 году Дэйв Тяхт рассмотрел состояние реализаций fq_codel и sch_cake в реальных условиях. Он обнаружил, что, хотя многие системы перешли на AQM по умолчанию, некоторые реализации имеют сомнительные отклонения от стандарта. Например, реализация fq_codel от Apple (по умолчанию в iOS) имеет очень большое количество пользователей, но не имеет компонента «codel». Тяхт также отмечает общее отсутствие разгрузки оборудования, что становится еще более важным из-за увеличения сетевого трафика, вызванного пандемией COVID-19 . ^[19]

См. также [ править ]

Ссылки [ править ]

^ Николс, К .; Джейкобсон, В .; МакГрегор, А.; Айенгар Дж. (январь 2018 г.). Активное управление очередью с контролируемой задержкой . IETF . дои : 10.17487/RFC8289 . RFC 8289 .
^ Джо Брокмайер (08 мая 2012 г.). «Хорошие новости для решения проблемы раздувания буфера: CoDel предлагает решение без ручек» . ЧитатьWriteWeb . Архивировано из оригинала 12 июля 2012 г. Проверено 16 августа 2012 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Николс, Кэтлин ; Джейкобсон, Ван (6 мая 2012 г.). «Управление задержкой очереди» . Очередь АКМ . 55 (7). Издательство ACM: 42–50. дои : 10.1145/2209249.2209264 . S2CID 381738 . Проверено 12 августа 2012 г.
^ Джейкобсон, Ван; Карелс, MJ (1988). «Предотвращение и контроль перегрузок» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 18 (4): 314–329. дои : 10.1145/52325.52356 . Архивировано из оригинала (PDF) 22 июня 2004 г.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Джейкобсон, Ван (2006). «Напыщенная речь об очередях. Доклад, представленный в MIT Lincoln Labs, Лексингтон, Массачусетс» (PDF) . Проверено 12 августа 2012 г.
^ Ильич ван Бейнум (10 мая 2012 г.). «Управление буферами CoDel может решить проблему раздувания буферов в Интернете» . Арс Техника . Проверено 16 августа 2012 г.
^ Николс, Кэтлин (июль 2012 г.). «Управление активной очередью с контролируемой задержкой (CoDel)» . Pollere Inc. Архивировано из оригинала 22 августа 2012 года . Проверено 12 августа 2012 г.
^ Грег Уайт; Джои Падден (ноябрь 2012 г.). «Предварительное исследование Codel AGM в сети Docsis» (PDF) . Cablelabs.com . Проверено 14 июня 2015 г.
^ Геттис, Джим (22 мая 2012 г.). «Веха достигнута: CoDel в Linux!» . jg's Ramblings . Проверено 12 августа 2012 г.
^ «Цероврт — Обзор» . Буферраздувание . Проверено 24 января 2014 г.
^ «Журнал изменений Procera Packetlogic» . proceranetworks.com . Архивировано из оригинала 24 июля 2013 г. Проверено 24 июля 2013 г.
^ дальнобойщик (26 мая 2016 г.). «Импортировать Dummynet AQM версии 0.2.1 (CoDel, FQ-CoDel, PIE и FQ-PIE)» .
^ дальнобойщик (10.06.2016). «Импорт MFC Dummynet AQM версии 0.2.1 (CoDel, FQ-CoDel, PIE и FQ-PIE)» .
^ Аль Саади, Расул; Армитидж, Гренвилл. «Реализация AQM во FreeBSD» .
^ «ОпенБСД 6.2» . Проверено 13 октября 2017 г.
^ «Бенчмаркинг кодов и кодов FQ — Bufferbloat.net» . www.bufferbloat.net .
^ Токе Хойланд-Йоргенсен; Пол МакКенни; Джим Геттис; Эрик Дюмазе (январь 2018 г.). Планировщик пакетов Flow Queue CoDel и алгоритм управления активной очередью . IETF . дои : 10.17487/RFC8290 . ISSN 2070-1721 . РФК 8290 . Экспериментальный.
^ «Торт — Bufferbloat.net» . www.bufferbloat.net .
^ Дэйв Тяхт (23 апреля 2022 г.). «Состояние fq_codel и sch_cake во всем мире» . CeroWRT .

Внешние ссылки [ править ]

[RFC8289-1] Николс, К .; Джейкобсон, В .; МакГрегор, А.; Айенгар Дж. (январь 2018 г.). Активное управление очередью с контролируемой задержкой . IETF . дои : 10.17487/RFC8289 . RFC 8289 .

[2] Джо Брокмайер (08 мая 2012 г.). «Хорошие новости для решения проблемы раздувания буфера: CoDel предлагает решение без ручек» . ЧитатьWriteWeb . Архивировано из оригинала 12 июля 2012 г. Проверено 16 августа 2012 г.

[CoDel_ACMQ-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Николс, Кэтлин ; Джейкобсон, Ван (6 мая 2012 г.). «Управление задержкой очереди» . Очередь АКМ . 55 (7). Издательство ACM: 42–50. дои : 10.1145/2209249.2209264 . S2CID 381738 . Проверено 12 августа 2012 г.

[4] Джейкобсон, Ван; Карелс, MJ (1988). «Предотвращение и контроль перегрузок» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 18 (4): 314–329. дои : 10.1145/52325.52356 . Архивировано из оригинала (PDF) 22 июня 2004 г.

[Rant_Jacobson-5] Перейти обратно: Перейти обратно: ^а ^б ^с Джейкобсон, Ван (2006). «Напыщенная речь об очередях. Доклад, представленный в MIT Lincoln Labs, Лексингтон, Массачусетс» (PDF) . Проверено 12 августа 2012 г.

[6] Ильич ван Бейнум (10 мая 2012 г.). «Управление буферами CoDel может решить проблему раздувания буферов в Интернете» . Арс Техника . Проверено 16 августа 2012 г.

[CoDel_sims-7] Николс, Кэтлин (июль 2012 г.). «Управление активной очередью с контролируемой задержкой (CoDel)» . Pollere Inc. Архивировано из оригинала 22 августа 2012 года . Проверено 12 августа 2012 г.

[8] Грег Уайт; Джои Падден (ноябрь 2012 г.). «Предварительное исследование Codel AGM в сети Docsis» (PDF) . Cablelabs.com . Проверено 14 июня 2015 г.

[CoDel_Linux-9] Геттис, Джим (22 мая 2012 г.). «Веха достигнута: CoDel в Linux!» . jg's Ramblings . Проверено 12 августа 2012 г.

[10] «Цероврт — Обзор» . Буферраздувание . Проверено 24 января 2014 г.

[Procera_PacketLogic_Changelog-11] «Журнал изменений Procera Packetlogic» . proceranetworks.com . Архивировано из оригинала 24 июля 2013 г. Проверено 24 июля 2013 г.

[12] дальнобойщик (26 мая 2016 г.). «Импортировать Dummynet AQM версии 0.2.1 (CoDel, FQ-CoDel, PIE и FQ-PIE)» .

[13] дальнобойщик (10.06.2016). «Импорт MFC Dummynet AQM версии 0.2.1 (CoDel, FQ-CoDel, PIE и FQ-PIE)» .

[14] Аль Саади, Расул; Армитидж, Гренвилл. «Реализация AQM во FreeBSD» .

[15] «ОпенБСД 6.2» . Проверено 13 октября 2017 г.

[16] «Бенчмаркинг кодов и кодов FQ — Bufferbloat.net» . www.bufferbloat.net .

[rfc8290-17] Токе Хойланд-Йоргенсен; Пол МакКенни; Джим Геттис; Эрик Дюмазе (январь 2018 г.). Планировщик пакетов Flow Queue CoDel и алгоритм управления активной очередью . IETF . дои : 10.17487/RFC8290 . ISSN 2070-1721 . РФК 8290 . Экспериментальный.

[18] «Торт — Bufferbloat.net» . www.bufferbloat.net .

[19] Дэйв Тяхт (23 апреля 2022 г.). «Состояние fq_codel и sch_cake во всем мире» . CeroWRT .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]