В сетевой маршрутизации , CoDel (произносится « Coddle ») для контролируемой задержки является алгоритм планирования для сетевого планировщика , разработанной Van Jacobson и Kathleen Nichols . Он разработан для преодоления избыточного буфера в сетевом оборудовании , таком как маршрутизаторы , путем установки ограничений на задержку сетевых пакетов при их прохождении через буферы в этом оборудовании. CoDel стремится улучшить общую производительность случайного раннего обнаружения (КРАСНЫЙ) алгоритм, устраняя некоторые из его фундаментальных заблуждений, по мнению Якобсона, и упрощая управление.
В 2012 году реализация CoDel была написана Дэйвом Тэхтом и Эриком Дюмазе для ядра Linux с двойной лицензией под Стандартной общественной лицензией GNU и лицензией BSD с тремя пунктами . Вариант CoDel от Dumazet называется fq_codel, что означает « задержка, управляемая справедливой очередью »; он был принят как стандартное решение для активного управления очередью (AQM) и планирования пакетов в версии OpenWrt под названием «Прерыватель барьеров». Оттуда CoDel и fq_codel мигрировали в различные последующие проекты, такие как Tomato , dd-wrt , OPNsense и функцию «Умных очередей» Ubiquiti .
Теоретические основы
Теория, лежащая в основе CoDel, основана на наблюдениях за поведением пакетов в сетях с коммутацией пакетов под влиянием буферов данных . Некоторые из этих наблюдений касаются фундаментальной природы очередей и причин буферного раздува , другие относятся к слабым местам альтернативных алгоритмов управления очередями. CoDel был разработан как попытка решить проблему буферного разряда. [1]
Bufferbloat
Поток пакетов замедляется при прохождении по сетевому каналу между быстрой и медленной сетью, особенно в начале сеанса TCP , когда происходит внезапный всплеск пакетов, и более медленная сеть может быть не в состоянии быстро принять этот пакет. достаточно. Существуют буферы, чтобы облегчить эту проблему, предоставляя быстрой сети место для хранения пакетов, которые будут считываться более медленной сетью в ее собственном темпе. [2] Другими словами, буферы действуют как амортизаторы, преобразуя резкое прибытие в плавный и устойчивый отъезд. Однако буфер имеет ограниченную емкость. Идеальный буфер имеет размер, позволяющий справиться с внезапным всплеском обмена данными и согласовывать скорость этого всплеска со скоростью более медленной сети. В идеале, ситуация поглощения ударов характеризуется временной задержкой пакетов в буфере во время пакета передачи, после чего задержка быстро исчезает, и сеть достигает баланса в предложении и обработке пакетов. [2]
TCP управления перегрузкой алгоритм основан на пакет капель , чтобы определить доступную полосу пропускания между двумя взаимодействующими устройствами. Он ускоряет передачу данных до тех пор, пока не начнут падать пакеты, а затем снижает скорость передачи. В идеале он продолжает ускоряться и замедляться по мере достижения равновесия со скоростью соединения. Чтобы это работало, отбрасывание пакетов должно происходить своевременно, чтобы алгоритм мог быстро выбрать подходящую скорость передачи. Если пакеты хранятся в слишком большом буфере, они прибудут в место назначения, но с большей задержкой, но пакеты не будут отброшены, поэтому TCP не замедлится. В этих условиях TCP может даже решить, что путь соединения изменился, и повторить поиск нового равновесия. [3] [4]
Наличие большого и постоянно заполненного буфера, вызывающего увеличение задержек передачи и снижение интерактивности, особенно при просмотре двух или более одновременных передач по одному и тому же каналу, называется буферной блокировкой. Доступная полоса пропускания канала также может оказаться неиспользованной, поскольку некоторые быстрые пункты назначения могут быть недоступны из-за того, что буферы забиты данными, ожидающими доставки в медленные пункты назначения.
Хорошие и плохие очереди
CoDel различает два типа очередей: [2] [5]
- Хорошая очередь
- Определяется как очередь, не имеющая буферной пустоты. Пакеты связи вызывают не более чем временное увеличение задержки очереди. Использование сетевого канала максимально.
- Плохая очередь
- Определяется как очередь, которая демонстрирует буферную пустоту. Пакеты связи заставляют буфер заполняться и оставаться заполненным, что приводит к низкому использованию и постоянно большой задержке буфера.
Для того, чтобы быть эффективным против буферного разряда, решение в форме алгоритма активного управления очередью (AQM) должно быть способно распознавать возникновение буферного разрыва и реагировать путем развертывания эффективных контрмер.
Ван Якобсон утверждал в 2006 году, что существующие алгоритмы использовали неправильные средства распознавания буферной пустоты. [4] Такие алгоритмы, как RED, измеряют среднюю длину очереди и считают это случаем разгрузки буфера, если среднее значение становится слишком большим. Джейкобсон продемонстрировал в 2006 году, что это измерение не является хорошей метрикой, поскольку средняя длина очереди резко возрастает в случае всплеска связи. Очередь может затем быстро исчезнуть (хорошая очередь) или превратиться в постоянную очередь (плохая очередь). Другие факторы сетевого трафика также могут вызывать ложные срабатывания или отрицательные результаты, вызывая ненужное развертывание контрмер. Якобсон предположил, что средняя длина очереди на самом деле не содержит никакой информации о спросе на пакеты или загрузке сети. [2] [4] Он предположил, что лучшим показателем может быть минимальная длина очереди в течение скользящего временного окна. [2]
Алгоритм
Основываясь на идее Якобсона от 2006 года, CoDel был разработан для управления очередями с контролем минимальной задержки, испытываемой пакетами в рабочем окне буфера. Цель состоит в том, чтобы минимальная задержка не превышала 5 миллисекунд. Если минимальная задержка становится слишком высокой, пакеты удаляются из очереди до тех пор, пока задержка не упадет ниже максимального уровня. [2] Николс и Джейкобсон приводят несколько преимуществ использования только этой метрики: [2]
- CoDel не имеет параметров. Одна из слабых сторон алгоритма RED (по словам Якобсона) заключается в том, что его слишком сложно настроить, особенно в среде с динамической скоростью соединения.
- CoDel по-разному относится к хорошей и плохой очередям. Хорошая очередь имеет низкие задержки по своей природе, поэтому алгоритм управления может ее игнорировать, в то время как плохая очередь подлежит вмешательству управления в виде отбрасывания пакетов.
- CoDel работает с параметром, который определяется полностью локально; Он не зависит от задержек приема-передачи, скорости канала, нагрузки трафика и других факторов, которые нельзя контролировать или прогнозировать с помощью локального буфера.
- Локальная минимальная задержка может быть определена только тогда, когда пакет покидает буфер, поэтому не требуется дополнительной задержки для запуска очереди для сбора статистики для управления очередью.
- CoDel адаптируется к динамически изменяющейся скорости соединения без отрицательного влияния на использование.
- Реализация CoDel относительно проста и, следовательно, может охватывать весь спектр от недорогих домашних маршрутизаторов до высокопроизводительных решений маршрутизации.
CoDel ничего не делает для управления буфером, если минимальная задержка для окна буфера ниже максимально допустимого значения. Он также ничего не делает, если буфер относительно пуст (если в буфере меньше одного MTU байтов). [2] Если эти условия не выполняются, CoDel вероятностно отбрасывает пакеты. [2]
Описание
Алгоритм независимо вычисляется на каждом сетевом переходе . Алгоритм работает в течение интервала , первоначально 100 миллисекунд. Задержка постановки в очередь для каждого пакета отслеживается через переход. Когда каждый пакет удаляется из очереди для пересылки , вычисляется задержка постановки в очередь (время, в течение которого пакет находится в очереди в ожидании). Сохраняется самая низкая задержка в очереди за интервал. Когда последний пакет интервала удаляется из очереди, если самая низкая задержка в очереди для интервала превышает 5 миллисекунд, этот единственный пакет отбрасывается, а интервал, используемый для следующей группы пакетов, сокращается. Если наименьшая задержка в очереди для интервала меньше 5 миллисекунд, пакет пересылается, и интервал сбрасывается до 100 миллисекунд.
Когда интервал сокращается, это делается в соответствии с обратным квадратным корнем из числа последовательных интервалов, в которых пакеты были отброшены из-за чрезмерной задержки в очереди. Последовательность интервалов, , , , ...
Результаты симуляции
CoDel был протестирован в симуляционных тестах Николсом и Якобсоном при различных значениях MTU, скоростях соединения и других вариациях условий. В целом результаты показывают: [2] [6]
- По сравнению с RED, CoDel сохраняет задержку пакетов ближе к целевому значению во всем диапазоне пропускной способности (от 3 до 100 Мбит / с). Измеренные коэффициенты использования канала неизменно составляют около 100% от пропускной способности канала.
- При меньшем MTU задержки пакетов меньше, чем при более высоком MTU. Более высокий MTU приводит к хорошему использованию канала, меньший MTU приводит к хорошему использованию канала при более низкой полосе пропускания, что приводит к снижению до справедливого использования при высокой пропускной способности.
Моделирование также было выполнено Грегом Уайтом и Джои Падденом из CableLabs . [7]
Выполнение
Полная реализация CoDel была реализована в мае 2012 года и стала доступной как программное обеспечение с открытым исходным кодом . [2] Это было реализовано в ядре Linux (начиная с основной ветки 3.5). [8] Дэйв Тэхт произвел обратный перенос CoDel на ядро Linux 3.3 для проекта CeroWrt , который, помимо прочего, касается bufferbloat [9], где он был тщательно протестирован. CoDel начал появляться в качестве опции в некоторых проприетарных / готовых к использованию платформах управления пропускной способностью в 2013 году. [10] FreeBSD интегрировала CoDel в ветки кода 11.x [11] и 10.x [12] в 2016 году. [13] Реализация распространяется с OpenBSD начиная с версии 6.2. [14]
Смотрите также
- Протокол скользящего окна
- Настройка TCP
Рекомендации
- ^ Джо Брокмайер (2012-05-08). «Хорошие новости для решения проблемы Bufferbloat: CoDel предлагает решение« без ручек » . ReadWriteWeb . Архивировано из оригинала на 2012-07-12 . Проверено 16 августа 2012 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Б с д е е г ч я J K Николс, Кэтлин ; Якобсон, Ван (6 мая 2012 г.). «Контроль задержки очереди» . Очередь ACM . ACM Publishing. DOI : 10.1145 / 2209249.2209264 . Проверено 12 августа 2012 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Якобсон, Ван; Карелс, MJ (1988). «Предотвращение и контроль перегрузок» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 18 (4). Архивировано из оригинального (PDF) 22 июня 2004 года. CS1 maint: обескураженный параметр ( ссылка )
- ^ а б в Якобсон, Ван (2006). «Беседа об очередях. Доклад, представленный в MIT Lincoln Labs, Лексингтон, Массачусетс» (PDF) . Проверено 12 августа 2012 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Ильич ван Бейнум (10 мая 2012 г.). «Управление буфером CoDel могло бы решить проблему заторов в Интернете» . Ars Technica . Проверено 16 августа 2012 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Николс, Кэтлин (июль 2012 г.). «Управление активной очередью с контролируемой задержкой (CoDel)» . Pollere Inc. Архивировано из оригинала 22 августа 2012 года . Проверено 12 августа 2012 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Грег Уайт; Джои Падден (ноябрь 2012 г.). «Предварительное исследование Codel AGM в сети Docsis» (PDF) . cablelabs.com . Проверено 14 июня 2015 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Геттис, Джим (22 мая 2012 г.). «Веха достигнута: CoDel в Linux!» . jg's Ramblings . Проверено 12 августа 2012 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Cerowrt - Обзор» . Bufferbloat . Проверено 24 января 2014 . CS1 maint: обескураженный параметр ( ссылка )
- ^ «Журнал изменений Procera Packetlogic» . procranetworks.com . Архивировано из оригинала на 2013-07-24 . Проверено 24 июля 2013 .
- ^ дальнобойщик (2016-05-26). «Импортировать Dummynet AQM версии 0.2.1 (CoDel, FQ-CoDel, PIE и FQ-PIE)» .
- ^ дальнобойщик (2016-06-10). «MFC Import Dummynet AQM версии 0.2.1 (CoDel, FQ-CoDel, PIE и FQ-PIE)» .
- ^ Ас-Саади, Расул; Армитаж, Гренвилл. «Внедрение AQM во FreeBSD» .
- ^ «OpenBSD 6.2» . Проверено 13 октября 2017 года . CS1 maint: обескураженный параметр ( ссылка )
Внешние ссылки
- CoDel псевдокод
- Фундаментальный прогресс в решении проблемы Bufferbloat