СПОСОБ ДИСПЕТЧЕРИЗАЦИИ ОЧЕРЕДЕЙ В КОММУТАТОРАХ С ПОДДЕРЖКОЙ КАЧЕСТВА ОБСЛУЖИВАНИЯ
METHOD OF DISPATCHING OF SWITCH QUEUES WITH SERVICE QUALITY MAINTAINING

Область применения
Изобретение относится к области телекоммуникаций и может быть использовано в коммутаторах с поддержкой качества обслуживания для регулирования доступа очередей коммутатора к физическому каналу.
Уровень техники
В сетевых коммутаторах с поддержкой качества обслуживания важным механизмом обеспечения требуемых параметров продвижения трафика является диспетчеризация очередей кадров, направляемых в каждый выходной порт, определяющим задержку передачи кадров и ее вариацию (джиттер), значения которых важны при передаче трафика реального времени через сети с пакетной коммутацией. Кадры, продвигаемые коммутатором, помечаются метками класса трафика, базируясь на которые он помещает кадры в очереди, соответствующие указанному в метке классу.
Механизм диспетчеризации заключается в правиле выбора обслуживаемой очереди, а так же регулировании выделяемой каждому классу полосы пропускания выходного канала.
Известны циклические алгоритмы диспетчеризации решающие эту задачу: взвешенный циклический (WRR- Weighted Round Robin), взвешенный дефицитный циклический (WDRR- Weighted Deficit Round Robin) (Кучерявый E.A. Управление трафиком и качество обслуживания в сети Интернет - СПб.: Наука и Техника, 2004). Особенностью данных алгоритмов является использование циклического приоритета при выборе обслуживаемой очереди, а длительность непрерывного обслуживания очереди определяется кредитом (допустимым количеством данных, считываемых их каждой очереди за сеанс ее обслуживания), значение которого пропорционально выделяемой для данного класса трафика полосы пропускания выходного канала. Недостатком алгоритма WRR является невысокая точность регулировки значения полосы пропускания из-за задания кредита в кадрах. Алгоритм WDRR в отличие от WRR обеспечивает высокую точность задания полосы пропускания, т.к. кредит задается в байтах, его значение должно быть не меньше максимальному размеру кадра. При этом величина кредита на новый цикл обслуживания по завершению очередного цикла корректируется (уменьшается) на величину дефицита - превышения кредита в завершенном цикле обслуживания из-за передачи последнего кадра (размер кадра не может быть уменьшен).
Для обоих алгоритмов свойственен общий недостаток - неконтролируемая величина джиттера (разброса задержки) коммутируемых кадров из-за разницы во времени ожидания кадров в различных очередях. Кроме того, задержка кадров определенного класса качества обслуживания, а также размеры соответствующих очередей, зависят от выделенной полосы пропускания для конкретного класса. Это приводит к увеличению задержки кадров и перегрузки очередей в каналах с малой назначенной полосой пропускания при пульсирующем характере трафика, так как алгоритмы циклического обслуживания не позволяют эффективно перераспределять неиспользуемую полосу пропускания недогруженных каналов для расширения полосы пропускания перегруженных.
Кроме того, непрерывная передача в одном сеансе больших порций данных трафика одного класса приводит к «пачечности» трафика, что в свою очередь увеличивает нагрузку на буфера последующих телекоммуникационных устройств.
Существующий алгоритм справедливого взвешенного обслуживания WFQ (Вегешна Ш. Качество обслуживания в сетях IP - СПБ: Изд-во "Вильямс", 2003), которому в меньшей мере свойственны указанные выше недостатки циклических алгоритмов. Однако данный алгоритм обладает высокой сложностью и требует значительных вычислительных ресурсов, что ограничивает его применение в коммутаторах. Наиболее близким техническим решением является патент US 2005/0141424 А1 «TIME-INDEPENDENT DEFICIT ROUND ROBIN METHOD AND SYSTEM», в котором описан метод диспетчеризации блоков протокольных данных (PDU) из множества очередей, каждый из которых характеризуется соответствующим кредитным требованием, причем способ содержит этапы: выделение кредита для каждой из множества очередей; извлечение из очереди по меньшей мере одного PDU из одной или более очередей, имеющих доступный кредит; вычитание требования к кредиту каждого PDU, извлеченного из очереди из доступного кредита, связанного с очередью, из которой он был извлечен; а также пополнение кредита, доступного для каждой из множества очередей, когда доступного кредита, связанного с одной из множества очередей, недостаточно для вывода из очереди PDU, при этом кредит определяет размер полосы пропускания, связанной с выходом диспетчера.
Технический результат
Технический результат заявляемого изобретения заключается в повышении качества обслуживания для регулирования доступа очередей коммутатора к физическому каналу за счет уменьшения вариаций значений джиттера трафика различных классов, распределения полосы пропускания выходного канала между трафиком различных классов и уменьшения пачечности в передаче трафика каждого класса.
Краткое описание чертежей
На фиг. 1 показана схема алгоритма функционирования диспетчера выходного порта коммутатора, реализующего предлагаемый алгоритм управления очередями.
На фиг. 2 показан предпочтительный вариант аппаратной реализации диспетчера, где 1 - память типа FIFO, разделенная между очередями и содержащая для каждой очереди: очередь кадров - 2, очередь служебных меток - 3; 4 - процессор диспетчеризации; 5 - классификатор поступающих кадров и канал прямой записи в память; 6 - таймер; 7 - канал прямого чтения кадров из очередей; 8 - физический интерфейс выходного порта: 9, 10 - шины записи и чтения из памяти; 11 - шина выходного канала; 12 - шина приема кадров из аппаратуры продвижения кадров в порт назначения коммутатора; 13 - сигнал «очереди свободны»; 14 - сигнал «выходной порт свободен».
Подробное описание изобретения
Реализации предлагаемого алгоритма диспетчеризации заключается в выполнении следующих действий:
1. При запуске коммутатора должна быть выполнено его конфигурирование, заключающееся в задании параметров: значение кредита для каждой очереди в байтах, начальные значения циклического приоритета и квота (в байтах) на допустимое количество денных, непрерывно передающихся при обслуживании очередей, и тем самым задающая длительность подсеанса.
2. Кадры, передаваемые в порт назначения коммутатора, классифицируются по классу трафика и записываются в соответствующие очереди, при этом снабжаются метками, указывающими на размер кадра и время его поступления в очередь.
3. Диспетчер запускается при освобождении выходного канала и наличии непустых очередей.
4. Выбирается очередь для обслуживания с учетом текущего значения циклического приоритета.
5. Запускается передача первого кадра из выбранной очереди в выходной канал.
6. Увеличивается счетчик переданных данных и уменьшается значение кредита на величину размера кадра.
7. По окончании передачи кадра выполняется последовательность проверок:
1) наличие в обслуживаемой очереди информации;
2) закончилась ли квота непрерывного обслуживания;
3) наличие дефицита, т.е. превышение выделенного кредита;
8. Если в обслуживаемой очереди больше нет информации, то:
1) изменяется значение циклического приоритета;
2) значения кредита и квоты непрерывного обслуживания устанавливаются в начальные значения;
3) выполняется переход к п. 3 для начала цикла обслуживания следующей очереди;
9. Если в обслуживаемой очереди закончилась квота непрерывного обслуживания, то:
1) значение квоты устанавливается в начальное;
2) при освобождении выходного порта, диспетчер выбирает, анализируя временные метки, очередь, содержащую кадр дольше всех ожидающий обработку;
3) для выбранной очереди выполняется передача одного кадра с корректировкой кредита на размер переданного кадра;
4) выполняется переход к п. 5;
10. При наличии дефицита выполняются следующие действия:
1) значение кредита для нового цикла обслуживания данной очереди устанавливается как разница между начальным значением и дефицитом;
2) значение квоты устанавливается в начальное значение;
3) изменяется значение циклического приоритета;
4) выполняется переход к п. 3 для начала цикла обслуживания следующей очереди;
11. При передаче каждого кадра через выходной порт вычисляется текущее среднее значение размера кадров в байтах, по текущему значению которого периодически корректируется значение квоты, ограничивающей время непрерывного обслуживания очередей (длительность подсеанса).
Пример обслуживания очереди 1, показанный на фиг.1 и 2, иллюстрирует последовательность передачи кадров в выходной канал. За первый подсеас передаются кадры 1-3 из очереди 1, затем диспетчер ищет самый «старый» кадр во всех заполненных очередях, пусть это кадр 1 очереди 3, он передается в качестве разделительного. После чего выполняется второй подсеанс, за время которого передаются кадры 4 и 5 очереди 1. На этом сеанс заканчивается (с дефицитом), т.к. исчерпан кредит, выделенный для очереди 1.
Функционирование предпочтительного устройства, реализующего предложенный способ диспетчеризации, заключается в следующем.
По шине 12 поступают кадры из аппаратуры продвижения кадров в порт назначения коммутатора, направленные в данный выходной порт. Они классифицируются устройством 5 по метке, содержащейся в кадре, и записываются по шине 9 в соответствующие классу трафика очереди 2. Одновременно в очередь 3 записываются метки длины кадра и времени его поступления в очередь, формируемую таймером 6.
Работа процессора запускается сигналами 13 и 14, в случае если канал свободен, и имеются не свободные очереди. Процессор, опрашивая метки длины кадра, выбирает согласно алгоритму, представленному на фиг.1 очередь для обслуживания и запускает процедуру чтения очередного кадра из этой очереди и его передачу в канал. После чтения каждого кадра процессор проверяет условия окончания цикла обслуживания, и достижения квоты непрерывной передачи согласно фиг.1. В случае если цикл закончен, то выполняется корректировка кредита и выбор следующей очереди согласно циклическому приоритету. Если цикл не закончен, то выполняется анализ временных меток и выбор очереди с наименьшим значением, из которой организуется передача разделительного кадра с соответствующей коррекцией ее кредита, после чего возобновляется прерванный цикл обслуживания до его окончания. Одновременно с этим процессор диспетчеризации периодически ведет подсчет средней длины кадров за определенное количество переданных кадров, например 1024. Вычисленное текущее значение средней длины используется для корректировки значений квот непрерывной передачи.