АссистентНовый вопросИсторияОбласти знаний
Партнёрские проектыСпецпроектыСтать автором
Сменить язык
О РУВИКИ

CoDel

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

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

Теория

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

Буфферблоат

Поток пакетов замедляется при прохождении сетевого участка между быстрой и медленной сетями, особенно при начале TCP-сеанса, когда происходит внезапный «всплеск» трафика, а медленная сеть не успевает обработать пакеты этого всплеска[3]. Буферы предназначены для смягчения этой проблемы: они предоставляют быстродействующей сети место для временного хранения пакетов, чтобы медленная сеть могла забирать их в своём ритме. Иными словами, буферы действуют как амортизаторы, превращая «рваную» подачу трафика в равномерный поток. Однако размер буфера ограничен. Идеальный буфер должен быть способен поглотить кратковременный всплеск и согласовать скорости передачи в обе стороны. При хорошем проектировании задержка в буфере появляется лишь временно во время передачи всплеска, после чего исчезает, и сеть достигает баланса[3].

Алгоритм управления перегрузкой TCP (англ. TCP congestion control) опирается на потери пакетов для определения доступной пропускной способности между устройствами: скорость передачи увеличивается, пока не начнутся потери, после чего снижается. Для корректной работы потери пакетов должны происходить своевременно, чтобы алгоритм успевал реагировать и выбирать подходящую скорость. Если же слишком большой буфер не опустошается, то пакеты доходят до получателя с большой задержкой, но не теряются, из-за чего TCP не замедляет передачу. В таких условиях TCP может ошибочно считать, что маршрут изменился, и начать заново искать баланс[4][5].

Если буфер велик и постоянно заполнен, то увеличивается задержка передачи и снижается интерактивность, особенно при работе нескольких соединений на одном канале. Такой эффект называется буфферблоатом. В результате часть каналов может остаться незагруженной, если буфер «забит» данными для медленных получателей.

Хорошие и плохие очереди

CoDel различает два типа очередей:[3][6] «Хорошая очередь» — та, в которой нет буфферблоата: всплески создают лишь временное увеличение задержки, а использование канала максимально. «Плохая очередь» характеризуется буфферблоатом: всплески приводят к заполнению буфера, он не освобождается, что ведёт к высокой и постоянной задержке и сниженному использованию канала. Эффективный AQM-алгоритм для борьбы с буфферблоатом должен уметь распознавать момент перехода к плохой очереди и реагировать на него.

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

Алгоритм

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

  • CoDel не требует настройки вручную (параметров); недостаток RED, по мнению Джейкобсона, — это сложность настройки, особенно при динамических скоростях линий;
  • CoDel «отличает» хорошие очереди от плохих: хорошие имеют малую задержку и не требуют вмешательства, плохие нуждаются в сбросе пакетов;
  • Алгоритм опирается только на локальную переменную (минимальная задержка), не зависит от задержки туда и обратно, пропускной способности, нагрузки и других внешних факторов;
  • Минимальную задержку можно узнать именно при покидании пакетом буфера, без специального накопления статистики и задержек;
  • CoDel адаптируется к изменению скорости канала без ухудшения использования полосы;
  • Простота реализации, что позволяет использовать CoDel как в простых домашних, так и в сложных корпоративных маршрутизаторах.

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

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

Сокращение интервала происходит обратно пропорционально квадратному корню из числа подряд идущих интервалов, в которых происходил сброс (100 мс, 100/√2, 100/√3, 100/√4, 100/√5 и т. д.).

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

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

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

Отдельное моделирование проводили также Грег Уайт и Джои Пэдден (англ. CableLabs)[8].

Реализации

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

Производные алгоритмы

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

Common Applications Kept Enhanced (CAKE; sch_cake в ядре Linux) — это комплексное решение для шейпинга и управления очередями, представленное проектом bufferbloat в 2018 году. CAKE основан на опыте использования fq_codel с планировщиком HTB (Hierarchy Token Bucket). Алгоритм уменьшает количество коллизий хеширования потоков, снижает загрузку CPU при шейпинге и включает иные улучшения по сравнению с htb+fq_codel[17].

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

Примечания

  1. ↑ K. Nichols, V. Jacobson, A. McGregor, J. Iyengar. Controlled Delay Active Queue Management (англ.). rfc-editor.org. IETF (январь 2018). Дата обращения: 10 июня 2024. Архивировано 1 января 2023 года.
  2. ↑ Joe Brockmeier. Good News for Solving Bufferbloat: CoDel Provides "No Knobs" Solution (англ.). ReadWriteWeb (8 мая 2012). Дата обращения: 10 июня 2024. Архивировано 12 июля 2012 года.
  3. ↑ 1 2 3 4 5 6 7 8 9 10 Kathleen Nichols, Van Jacobson (6 мая 2012). “Controlling Queue Delay”. ACM Queue [англ.]. ACM Publishing. 55 (7): 42—50. DOI:10.1145/2209249.2209264. S2CID 381738. Дата обращения 2024-06-10.
  4. ↑ Van Jacobson, M. J. Karels (1988). “Congestion avoidance and control” (PDF). ACM SIGCOMM Computer Communication Review [англ.]. 18 (4): 314—329. DOI:10.1145/52325.52356. Архивировано из оригинала (PDF) 2004-06-22. Дата обращения 2024-06-10. Используется устаревший параметр |url-status= (справка)
  5. ↑ 1 2 3 Van Jacobson. A rant on queues. A talk presented at MIT Lincoln Labs, Lexington, MA (англ.) (2006). Дата обращения: 10 июня 2024.
  6. ↑ Iljitsch van Beijnum. CoDel buffer management could solve the Internet's bufferbloat jams (англ.). Ars Technica (10 мая 2012). Дата обращения: 10 июня 2024.
  7. ↑ Kathleen Nichols. Controlled Delay (CoDel) Active Queue Management (англ.). Pollere Inc. (июль 2012). Дата обращения: 10 июня 2024. Архивировано 22 августа 2012 года.
  8. ↑ Greg White, Joey Padden. Preliminary Study of Codel AQM in a Docsis Network (англ.). cablelabs.com (ноябрь 2012). Дата обращения: 10 июня 2024.
  9. ↑ Jim Gettys. A Milestone Reached: CoDel is in Linux! (англ.). jg's Ramblings (22 мая 2012). Дата обращения: 10 июня 2024.
  10. ↑ Cerowrt — Overview (англ.). Bufferbloat. Дата обращения: 10 июня 2024.
  11. ↑ Procera Packetlogic Changelog (англ.). proceranetworks.com. Дата обращения: 10 июня 2024. Архивировано 24 июля 2013 года.
  12. ↑ truckman. Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE) (англ.) (26 мая 2016).
  13. ↑ truckman. MFC Import Dummynet AQM version 0.2.1 (CoDel, FQ-CoDel, PIE and FQ-PIE) (англ.) (10 июня 2016).
  14. ↑ Rasool Al Saadi, Grenville Armitage. Implementing AQM in FreeBSD (англ.).
  15. ↑ OpenBSD 6.2. Дата обращения: 10 июня 2024.
  16. ↑ Benchmarking Codel and FQ Codel — Bufferbloat.net (англ.). bufferbloat.net. Дата обращения: 10 июня 2024.
  17. ↑ Cake — Bufferbloat.net (англ.). bufferbloat.net. Дата обращения: 10 июня 2024.
  18. ↑ Dave Täht. The state of fq_codel and sch_cake worldwide (англ.). CeroWRT (23 апреля 2022). Дата обращения: 10 июня 2024.

Литература

Ссылки

Категории