Способ стохастической диспетчеризации очередей коммутатора и устройство, его реализующее

Изобретение относится к области телекоммуникаций. Технический результат направлен на расширение арсенала средств того же назначения. Устройство стохастической диспетчеризации в составе коммутатора или маршрутизатора содержит разделяемую память, блок выбора очередей, включающий узел надзора, узел хранения постоянных величин, генератор псевдослучайных чисел, узел сравнения величин, узел определения номера обслуживаемой очереди, память заголовков и указателей, контроллер памяти, классификатор, входной и выходные порты, также включает набор соединений, соединение (1) является управляющим входом блока выборки очередей, по которому узлом управления очередями инициируется запуск процедуры подсчета номера очереди и нового цикла работы устройства, соединение (2) является информационным входом, по которому узлом управления очередями на момент поступления на соединении (1) управляющего сигнала должны быть переданы длины очередей и параметры, и узел сравнения величин сравнивает значения, подсчитанные узлом расчета вероятностей выбора очереди, а узел подсчета номера обслуживаемой очереди на основе данных сравнения, полученных от узла сравнения величин, производит выдачу обрабатывающим узлам, схеме выборки кадра обрабатывающего блока, а также узлу надзора сигналов разрешения или запрета обслуживания по каждому из классов обслуживания. 2 ил.

 

Изобретение относится к области телекоммуникаций, а именно к коммутаторам и маршрутизаторам с поддержкой качества обслуживания, и предназначено для регулирования доступа очередей коммутатора и маршрутизатора к физическому каналу.

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

В традиционных детерминированных системах диспетчеризации очередей в сетевых устройствах выбор очереди имеет детерминированный характер, задаваемый правилами приоритезации (жёсткими, циклическими и др.) [Олифер В.Г. , Олифер Н.А. Компьютерные сети. Принципы, технологии, протоколы. 4-е изд. – СПБ: Изд-во “Питер”, 2010, - С. 943]. В таких системах время ожидания обслуживания некоторого кадра зависит не только от места кадра в очереди, загруженности очередей и иных аргументов, но и от правил очерёдности обслуживания узлов, что приводит к непредсказуемости задержки кадров.

Известен способ диспетчеризации пакетов, предназначенный для регулирования доступа очередей к аппаратным ресурсам выходного канала, основанный на качестве обслуживания и устройство его реализующее, заключающийся в том, что осуществляется извлечение параметра качества обслуживания, включаемого в заголовок пакета; осуществляется многократное обновление значения случайной величины; осуществляется присвоение ключа приоритета пакету, в зависимости от параметра качества обслуживания и сгенерированной случайной величины, в соответствии с заранее определёнными правилами [Patent EP 1 887 742 A1 System and process for QOS-based packet scheduling]. Система диспетчеризации, приписывания аппаратных ресурсов выходного канала для пропуска пакетам, обрабатываемым различными поставщиками услуг, включает:

-генератор случайной величины;

-программируемое приписывающее устройство, приписывающее ключ приоритета пакету, в зависимости от параметра качества обслуживания и сгенерированной случайной величины, в соответствии с перепрограммируемыми правилами;

-устройство диспетчеризации, содержащее управляющее устройство, генерирующее команды коммутации пакетов в порядке, зависящем от значения ключа приоритета, присваиваемого каждому заголовку пакета;

-устройство коммутации, продвигающее пакеты в направлении аппаратных ресурсов выходного канала в сгенерированном порядке команд коммутации пакетов.

Как следует из формулы изобретения, в известном способе диспетчеризации пакетов, предназначенном для регулирования доступа очередей к аппаратным ресурсам выходного канала, основанном на качестве обслуживания, генерируются команды коммутации пакетов в порядке, зависящем от значения ключа приоритета, присваиваемого каждому заголовку пакета, и значения случайного числа, не зависящего от значений задержки пакетов, длин очередей, накопленных времён обслуживания; пакеты продвигаются в направлении аппаратных ресурсов выходного канала в сгенерированном порядке команд коммутации пакетов.

Недостатками этого способа диспетчеризации пакетов, предназначенного для регулирования доступа очередей к аппаратным ресурсам выходного канала, являются:

1) Большая зависимость величины разброса длин очередей и времён нахождения заявок в очередях от величины разброса количества заявок, принятых очередями, на единицу времени вследствие независимости управления доступом очередей к выходному каналу от значений задержки пакетов, длин очередей, накопленных времён обслуживания и долей от полос пропускания по каждому классу обслуживания, оперативно оцениваемых в процессе диспетчеризации.

2) Кадры, обладающие одинаковыми значениями битового поля приоритета, могут быть распределены по разным очередям с разными долями полосы пропускания, что приводит к потерям кадров [2, 3].

Наиболее близким к предлагаемому изобретению является способ стохастической диспетчеризации, основанный на приоритете, предназначенный для выборки задач на исполнение [Patent 5,247,677 U.S. STOCHASTIC PRIORITY-BASED TASK SCHEDULER / Welland et al. (1993) ], который заключающийся в том, что осуществляет выбор задач из очередей на основе сравнения значений многократно обновляемого случайного числа и суммы постоянных величин вероятностей выборок очередей, номера которых меньше или равны номерам этих очередей, осуществляет возможность обслуживания низкоприоритетных очередей путём выделения гарантированной доли обслуживания.

Из анализа формулы изобретения известного способа следует, что способ предназначен для распределения процессорного времени между задачами в операционных системах одним или несколькими процессорами, а также в любых других цифровых вычислительных системах, где необходима такого рода диспетчеризация. Величины вероятностей выборок очередей являются постоянными и не зависят от длин очередей и долей полос пропускания по каждому классу обслуживания, оперативно оцениваемых в процессе диспетчеризации. Основанный на приоритете стохастический диспетчер выбирает задачи на основе случайного числа, взвешенного приоритетом задачи. С момента обретения каждой задачей ненулевой конечной вероятности быть выбранной, все задачи, включая низкоприоритетные получают шанс быть выбранными, таким образом, устраняя проблему тупиков.

Недостатками стохастической диспетчеризации, основанной на приоритете, являются:

1) Отсутствие возможности управления значениями длин очередей, времён нахождения заявок на выполнение задач по отдельным очередям.

2) Большая зависимость величины разброса длин очередей и времён нахождения заявок в очередях от величины разброса количества заявок, принятых очередями, на единицу времени.

Задачей изобретения является выравнивание основных характеристик канала, проявляемое в уменьшении вариаций среднего значения и стандартного отклонения длин очередей, уменьшении вариаций средних значений задержек кадров различных классов.

Поставленная задача достигается созданием дисциплины диспетчеризации, совмещающей удовлетворение требованиям адаптивности к динамически изменяющимся сетевым параметрам, а также отсутствием детерминированности.

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

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

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

На приложенных к описанию чертежах показано:

на фиг.1 – схема алгоритма цикла работы блока выбора очередей, реализующего способ стохастической диспетчеризации очередей в коммутаторах;

на фиг.2 – блок, реализующий способ стохастической диспетчеризации очередей в коммутаторах.

Устройство, реализующее данный способ стохастической диспетчеризации очередей в коммутаторах (фиг.2), содержит: следующие узлы: генератор псевдослучайных чисел с подключенным к нему узлом сравнения величин; узлом хранения постоянных величин; узлом подсчёта вероятностей выбора очередей на обслуживание, содержащим подузлы: умножения и деления, сложения и вычитания, логических операций, сравнения чисел на ноль, инкрементации, условного перехода, констант; узел подсчёта номера обслуживаемой очереди; узел надзора.

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

Устройство стохастической диспетчеризации в составе коммутатора или маршрутизатора содержит набор соединений.

Соединение 1 является управляющим входом блока выборки очередей, по которому узлом управления очередями инициируется запуск процедуры подсчёта номера очереди и нового цикла работы устройства стохастической диспетчеризации. Соединение 2 является информационным входом, по которому узлом управления очередями на момент поступления на соединении 1 управляющего сигнала должны быть переданы длины очередей и другие параметры, необходимые для подсчёта номера очереди. Соединение 3 является управляющим выходом, по которому узлу управления очередями передаётся управляющий сигнал, свидетельствующий об окончании процедуры подсчёта номера очереди. Соединение 4 является информационным выходом, по которому узлу управления очередями на момент поступления на соединение 3 управляющего сигнала, должен быть передан подсчитанный номер очереди, должной быть обслуженной.

По соединению 5 осуществляется передача кадров с входного порта на классификатор с целью классификации трафика в соответствии с различными требованиями, задаваемыми качеством обслуживания, например, задержек кадров и т. д.

По соединению 6 осуществляется передача кадров в контроллер разделяемой памяти из классификатора, при этом, адрес расположения начала кадров записывается в памяти указателей и заголовков (см. далее).

По соединению 7 осуществляются операции записи содержимого разделяемой памяти контроллером разделяемой памяти.

По соединению 20 осуществляются операции чтения содержимого разделяемой памяти контроллером разделяемой памяти.

По соединению 8 осуществляется запись кадров, извлекаемых из разделяемой памяти, контроллером памяти в выходной порт.

По соединению 9 осуществляется передача управляющего сигнала от выходного порта к контроллеру памяти об окончании процедуры передачи кадра из выходного порта в среду передачи.

По соединению 21 осуществляется передача управляющего сигнала от выходного порта к контроллеру памяти о предстоящем окончании процедуры передачи кадра из выходного порта в среду передачи.

По соединению 10 осуществляется передача запроса, управляющего сигнала, на проверку сведений о пустоте очереди. Если две очереди и более не пусты, то происходит передача запроса на определение номера обслуживаемой очереди по соединению 1.

По соединению 11 осуществляется передача управляющего сигнала – запроса узла управления очередями, адресованного контроллеру памяти, на извлечение кадра, адрес и длина которого передаются по соединению 12, из разделяемой памяти.

По соединению 13 осуществляется передача управляющего сигнала от классификатора, адресованного узлу управления очередями, на запись заголовка кадра, заголовок которого передаётся по соединению 14, а номер очереди, присвоенный классификатором, по соединению 15.

По соединению 22 передаётся управляющий сигнал для соединения 21. По соединению 21 передаётся адрес кадра, необходимый для записи, в память указателей и заголовков.

Узел надзора осуществляет контроль аргументов, т.е длин очередей, времён обслуживания, передаваемых по информационному соединению 2. Если, например, сумма длин очередей больше размера разделяемой памяти, то процедура расчёта номера обслуживаемой очереди не производится, номер обслуживаемой очереди, подаваемый на выход 4, приобретает значение, соответствующее предыдущему номеру обслуживаемой очереди.

Узел надзора соединён соединением 1 и соединением 2 с узлом управления очередями, а также имеет выход, связанный с узлом подсчёта вероятностей.

Узел подсчёта вероятностей выбора очередей на обслуживание обеспечивает подсчёт значений вероятностей, осуществляемый согласно алгоритму, показанному на фиг.1.

Узел подсчёта вероятностей выбора очередей на обслуживание имеет входы с узла надзора, узлом хранения постоянных величин (ПЗУ), а также имеет выход, связанный с узлом сравнения величин.

Процедура подсчёта номера обслуживаемой очереди является циклической, инициируется схемой выборки кадра с разрешения узла надзора устройства стохастической диспетчеризации в момент времени, соответствующий остатку времени до момента окончания передачи кадра, необходимому для расчёта искомого номера. Передача аргументов для подсчёта вероятностей осуществляется из передаточных очередей заголовков и указателей кадрового обработчика к узлу надзора и к узлу подсчёта вероятностей устройства стохастической диспетчеризации. Узел надзора проверяет аргументы на корректность и разрешает или запрещает расчёт. Подсчёт вероятностей для каждой из очередей осуществляется параллельно и независимо от подсчёта вероятностей выбора других очередей. Однако, в соответствии с предлагаемым способом, происходит подсчёт сумм вероятностей (кумулятивных вероятностей). Этот подсчёт также ведётся в узле подсчёта вероятностей выбора очередей на обслуживание.

Узел хранения постоянных величин содержит некоторые числовые константы, предназначенные для расчётов вероятностей, такие как: выделяемые доли обслуживания под каждый тип трафика, приоритеты по умолчанию (начальные значения вероятностей), семя генератора псевдослучайных чисел.

Узел хранения постоянных величин имеет выход, связанный с узлом сравнения величин.

Генератор псевдослучайных чисел в процессе инициализации получает ключевой код из узла хранения постоянных величин, порождает случайное число через фиксированное число тактов часов так, чтобы на каждый цикл диспетчеризации приходилось не менее одного вычисление псевдослучайного числа. Порождённая последовательность псевдослучайных чисел подчиняется равномерному распределению. Любое число из этой последовательности обладает неотрицательным значением, меньшим единицы.

Узел сравнения величин сравнивает значения, подсчитанные узлом подсчёта вероятностей выбора очереди на обслуживание, т.е. т.н. кумулятивные вероятности, и генератором случайной величины. Для каждого типа трафика ставится либо значение истины или значение лжи в зависимости от разности значений.

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

Способ реализуют алгоритмом, приведённым на фиг. 1. Выполнение его происходит циклически.

Узел подсчёта вероятностей выбора очередей на обслуживание обеспечивает подсчёт значений вероятностей, осуществляемый согласно алгоритму, показанному на фиг.1. Для подсчёта вероятностей необходимо решить уравнение (1), где - произвольная константа, - автоматное время работы устройства (для блока, реализующего расчёт номера очереди на обслуживание, согласно способу предназначен один источник синхронных импульсов), - накопленное время обслуживания -той очереди за всё время работы, m – общее число очередей, - длина i - той очереди в битах, - столбцовая матрица размером , характеризующая доли разрешённых полос пропускания, выделенных для каждой -той очереди при , при этом является постоянной величиной, – поправочные величины, нахождение значений которых является промежуточным этапом, необходимым в процессе вычисления вероятностей выборок очередей на обслуживание согласно уравнению (1).

Расчёт вероятностей осуществляется, исходя из решения уравнения (1) на основе имеющихся данных о загрузке очередей, текущей полосе и т. д. с неизвестным x являющимся столбцовой матрицей. В случае пустоты i – той очереди расчёт вероятности по i – тому классу обслуживания не имеет смысла, ибо она станет равной нулю.

После нахождения значения x необходимо найти искомые значения вероятностей выбора очередей согласно формуле (2).

Для решения уравнения (1) необходимо вычислить несколько значений, в т.ч. значения числовых критериев выбора очередей на обслуживание согласно формуле (3). Таким образом, уравнение (1) можно записать в виде (4). Значения не являются постоянными и переменны во времени. Значение является постоянной величиной. Т.о., для решения уравнения (1) необходимо вычислить, в т.ч. значения числовых критериев выбора очередей на обслуживание согласно формуле (3). Таким образом, уравнение (1) можно записать в виде (4). Значения не являются постоянными и переменны во времени. Уравнение (1) можно записать в виде (6). Решением уравнения (6) является выражение (7). Для каждой очереди вычисляется значение согласно формуле (7). На основе полученных значений подсчитываются значения вероятностей выбора очередей на обслуживание согласно формуле (2). На основе полученных значений осуществляется подсчёт значений кумулятивных вероятностей согласно формуле (8). К моменту окончания подсчёта кумулятивных вероятностей значение (псевдо-) случайного числа Rand должно быть сгенерированным и известным. Затем осуществляется сравнение кумулятивных вероятностей со значением Rand согласно алгоритму, показанному на фиг.2.

(1),

(2),

(3)

(4)

(5)

(6)

(7)

(8)

Устройство стохастической диспетчеризации в составе коммутатора или маршрутизатора, содержащее разделяемую память, блок выбора очередей, включающий узел надзора, узел хранения постоянных величин, генератор псевдослучайных чисел, узел сравнения величин, узел определения номера обслуживаемой очереди, память заголовков и указателей, контроллер памяти, классификатор, входной и выходные порты, также включает набор соединений, соединение (1) является управляющим входом блока выборки очередей, по которому узлом управления очередями инициируется запуск процедуры подсчета номера очереди и нового цикла работы устройства, соединение (2) является информационным входом, по которому узлом управления очередями на момент поступления на соединении (1) управляющего сигнала должны быть переданы длины очередей и параметры для подсчета номера очереди, соединение (3) является управляющим выходом, по которому к узлу управления очередями передается управляющий сигнал, свидетельствующий об окончании процедуры подсчета номера очереди, соединение (4) является информационным выходом, по которому узлу управления очередями на момент поступления на соединение (3) управляющего сигнала должен быть передан подсчитанный номер обслуживаемой очереди, должной быть обслуженной, по соединению (5) осуществляется передача кадров с входного порта на классификатор, по соединению (6) осуществляется передача кадров в контроллер разделяемой памяти из классификатора, при этом адрес расположения начала кадров записывается в памяти указателей и заголовков, по соединению (7) осуществляются операции записи содержимого разделяемой памяти контроллером разделяемой памяти, по соединению (20) осуществляются операции чтения содержимого разделяемой памяти контроллером разделяемой памяти, по соединению (8) осуществляется запись кадров, извлекаемых из разделяемой памяти, контроллером памяти в выходной порт, по соединению (9) осуществляется передача управляющего сигнала от выходного порта к контроллеру памяти об окончании процедуры передачи кадра из выходного порта в среду передачи, по соединению (21) осуществляется передача управляющего сигнала от выходного порта к контроллеру памяти о предстоящем окончании процедуры передачи кадра из выходного порта в среду передачи, по соединению (10) осуществляется передача запроса управляющего сигнала на проверку сведений о пустоте очереди, если две очереди и более не пусты, то происходит передача запроса на определение номера обслуживаемой очереди по соединению (1), по соединению (11) осуществляется передача управляющего сигнала - запроса узла управления очередями, адресованного контроллеру памяти, на извлечение кадра, адрес и длина которого передаются по соединению (12) из разделяемой памяти, по соединению (13) осуществляется передача управляющего сигнала от классификатора, адресованного узлу управления очередями, на запись заголовка кадра, заголовок которого передается по соединению (14), а номер очереди, присвоенный классификатором - по соединению (15), по соединению (22) передается управляющий сигнал для соединения (21), по соединению (21) передается адрес кадра, необходимый для записи, в память указателей и заголовков, узел надзора осуществляет контроль длин очередей и времени обслуживания, передаваемых по информационному соединению (2), в случае если сумма длин очередей больше размера разделяемой памяти, то процедура расчета номера обслуживаемой очереди не производится, номер обслуживаемой очереди, подаваемый на выход (4), приобретает значение, соответствующее предыдущему номеру обслуживаемой очереди, при этом генератор псевдослучайных чисел в процессе инициализации получает ключевой код из узла хранения постоянных величин, периодически порождает случайное число, узел хранения постоянных величин имеет выход, связанный с узлом сравнения величин, отличающееся тем, что блок выбора очередей содержит узел расчета вероятностей выбора очередей на обслуживание, который имеет входные соединения с узлами надзора и хранения постоянных величин, а также имеет выход, связанный с узлом сравнения величин, при этом узел подсчета вероятностей выбора очередей на обслуживание обеспечивает подсчет значений вероятностей выбора очередей на обслуживание по следующей циклической процедуре, которая инициируется схемой выборки кадра с разрешения узла надзора устройства в момент времени, соответствующий остатку времени до момента окончания передачи кадра, необходимому для расчета искомого номера, передача аргументов для узла расчета вероятностей осуществляется из очередей заголовков и указателей через узлы управления очередями и надзора, при этом узел сравнения величин сравнивает значения, подсчитанные узлом расчета вероятностей выбора очереди на обслуживание и указанные суммарные вероятности выбора очереди, а узел подсчета номера обслуживаемой очереди на основе данных сравнения, полученных от узла сравнения величин, производит выдачу обрабатывающим узлам, схеме выборки кадра обрабатывающего блока, а также узлу надзора сигналов разрешения или запрета обслуживания по каждому из классов обслуживания.