способ и система для планирования выбора данных для передачи в сети передачи данных

Формула изобретения

1. Система для планирования выбора данных для передачи в сети передачи данных, где сеть передачи данных имеет множество дочерних элементов, включающая в себя:

распределитель кредитов, обеспечивающий:

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

поддержку справедливости между дочерними элементами по соотношению предоставленных кредитов;

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

вычитание предоставленных кредитов из кредитного баланса; и

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

выбора, по меньшей мере, одного допустимого и работоспособного дочернего элемента для извлечения из очереди;

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

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

2. Система по п.1, где распределитель кредитов способен дополнительно выполнять следующие операции:

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

добавление снятых кредитов к кредитному балансу для повторного распределения.

3. Система по п.1, где распределитель кредитов имеет, по меньшей мере, одну циклическую очередь управления, содержащую, по меньшей мере, один идентификатор, по меньшей мере, одного из следующего:

допустимый дочерний элемент и дочерний элемент, имеющий отрицательный счетчик кредита, где распределитель кредитов дополнительно выполняет следующие функции:

чередование предоставления кредитов дочерним элементам в рамках первой циклической очереди управления;

предоставление одного кредита каждому дочернему элементу из первой циклической очереди в цикле;

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

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

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

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

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

выбор первой циклической очереди управления для распределения кредитов;

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

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

предоставление кредитов дочерним элементам, обнаруженным в выбранных циклических очередях управления в порядке очереди.

5. Система по п.1, где распределитель кредитов дополнительно выполняет следующие функции;

поддерживает баланс между предоставлением кредитов и передачей данных;

предоставляет кредит приблизительно с той же скоростью, что и нормальная передача данных; и

реагирует на наличие остатка кредитного баланса, повышая скорость предоставления кредитов.

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

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

8. Система по п.7, где очереди управления передачей данных включают в себя очередь положительных кредитов передачи, очередь отрицательных кредитов передачи и очередь экстремальных отрицательных кредитов передачи и где:

первый порог счетчика кредита между очередью положительных кредитов передачи и очередью отрицательных кредитов передачи равен нулю;

второй порог счетчика кредита между очередью отрицательных кредитов передачи и очередью экстремальных отрицательных кредитов передачи равен отрицательной величине максимального блока передачи для сети передачи данных;

очередь положительных кредитов передачи имеет более высокий приоритет при выборе, чем очередь отрицательных кредитов передачи; и очередь отрицательных кредитов передачи имеет более высокий приоритет при выборе, чем очередь экстремальных отрицательных кредитов передачи.

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

очередь экстремальных положительных кредитов передачи, очередь обхода и очередь неизвестных дочерних элементов:

очередь обхода имеет наивысший уровень приоритета и при передаче из очереди обхода кредиты в кредитный баланс не возвращаются;

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

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

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

определение состояния допустимости для каждого дочернего элемента, где каждый дочерний элемент может передавать данные, основанные, по меньшей мере, на ограничении скорости обмена;

предоставление кредитов, по меньшей мере, допустимым и работоспособным дочерним элементам и дочерним элементам, имеющим отрицательный счетчик кредита;

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

вычитание предоставленных кредитов из кредитного баланса.

12. Способ по п.11, дополнительно включающий в себя:

снятие всех кредитов с ранее допустимого и работоспособного дочернего

элемента, пока дочерний элемент не станет неработоспособным или недопустимым; и

добавление снятых кредитов к кредитному балансу для повторного распределения.

13. Способ по п.11, дополнительно включающий в себя:

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

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

выбор первой циклической очереди управления для распределения кредитов;

предоставление кредитов дочерним элементам, обнаруженным в первой циклической очереди управления;

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

14. Способ по п.13, где кредиты предоставляются дочерним элементам,

обозначенным в выбранной циклической очереди в соответствии с нормированными весовыми коэффициентами для каждого дочернего элемента; и

где сумма весов для каждого дочернего элемента по всем циклам равна его нормированному весу, помноженному на множитель для его циклической очереди.

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

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

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

16. Способ планирования выбора данных для передачи в сети передачи данных, где сеть передачи данных содержит множество дочерних элементов, включающий:

определение состояния допустимости для каждого дочернего элемента, где каждый дочерний элемент может передавать данные, основанные, по меньшей мере, на ограничении скорости всплеска;

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

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

выбор, по меньшей мере, одного допустимого дочернего элемента для извлечения из очереди в соответствии с уровнем приоритета очереди управления передачей данных, соответствующей упомянутому допустимому дочернему элементу;

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

17. Способ по п.16, где очереди управления передачей данных включают в себя очередь положительных кредитов передачи, очередь отрицательных кредитов передачи и очередь экстремальных отрицательных кредитов передачи и где:

первый порог счетчика кредита между очередью положительных кредитов передачи и очередью отрицательных кредитов передачи равен нулю;

второй порог счетчика кредита между очередью отрицательных кредитов передачи и очередью экстремальных отрицательных кредитов передачи равен отрицательной величине максимального блока передачи для сети передачи данных;

очередь положительных кредитов передачи имеет более высокий приоритет при выборе, чем очередь отрицательных кредитов передачи; и очередь отрицательных кредитов передачи имеет более высокий приоритет при выборе, чем очередь экстремальных отрицательных кредитов передачи.

18. Способ по п.17, где очереди управления передачей данных дополнительно включают в себя очередь экстремальных положительных кредитов передачи и очередь обхода:

очередь экстремальных положительных кредитов передачи имеет более высокий приоритет, чем очередь положительных кредитов передачи, очередь отрицательных кредитов передачи и очередь экстремальных отрицательных кредитов передачи; и

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

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

Описание изобретения к патенту

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

ПРЕДПОСЫЛКИ СОЗДАНИЯ ИЗОБРЕТЕНИЯ

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

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

На ФИГ.1 показана система передачи данных 10, соответствующая традиционной технологии, система, которая включает в себя процесс планирования 12, где маршрут передачи данных содержит ряд очередей 14а, 14b, 14с, 14d и 14е (которые все вместе обозначены как очередь данных 14) и мультиплексоры 16а, 16b (которые все вместе обозначены как мультиплексор 16). Несмотря на то, что мультиплексор показан на ФИГ.1 в виде физического устройства, в обычной масштабируемой реализации мультиплексоры физически не существуют, а подразумеваются выбором планировщика очереди данных 14 для передачи. Процесс планирования 12 может выбирать из любой очереди данных 14, располагающей доступными данными ("DA" - «ДД»); однако в силу иерархического характера реализации процесс планирования 12 должен запрашивать у дочернего планировщика 18 для выбора из очереди данных 14d и очереди данных 14е. Затем дочерний планировщик 18 выбирает подходящую очередь данных 14d, 14е. В этом примере процесс планирования 12 может выбрать очереди данных 14а, 14b и 14с непосредственно.

Один из процессов справедливой организации очередей с использованием весовых коэффициентов раскрыт в патенте США № 7.373.420, выданном Lyon (далее «патент 420»), полное содержание которого включено здесь по ссылке. На ФИГ.2 показан процесс справедливой организации очередей с использованием весовых коэффициентов в соответствии с «патентом 420», который включает в себя систему обратного управления кредитами, где для определения очереди, которую следует «кредитовать», используются назначенные весовые коэффициенты. В принципе, планировщик 20 для справедливой организации очередей с использованием весовых коэффициентов на основе обратного управления кредитами ("WFQ-ICM") включает в себя два дополняющих друг друга процесса: распределитель кредитов WFQ 22 и селектор передачи 24. Селектор передачи 24 обычно функционирует циклическим образом, где каждый дочерний процесс, располагающий данными и имеющий положительный кредит, получает право на передачу данных по очереди.

Процесс кредитования 22 предоставляет кредиты дочерним элементам, текущие кредиты которых меньше, чем объем доступных данных ("ADA") для этого дочернего элемента. Объем кредитов, которые каждый дочерний элемент набрал в любой заданный момент, отслеживается в базе данных кредитного состояния дочерних элементов 26. Объем кредитов каждого дочернего элемента никогда не превышает ADA этого дочернего элемента. В любой момент времени дочерний элемент обладает кредитом меньшим, чем его ADA, и включается в распределитель кредитов 22, когда конкурирует за дополнительный кредит.

Селектор передачи 24 выбирает для передачи данных дочерние элементы с положительным счетчиком кредита. Когда дочерний элемент передает данные, кредиты вычитаются из его текущего объема кредита в базе данных кредитного состояния дочерних элементов 26 и возвращаются в распределитель кредитов 22 для повторного распределения другим дочерним элементам, обладающим ADA большим, чем количество кредитов. Распределитель кредитов 22 предоставляет кредиты с той же скоростью, с какой дочерние элементы тратят кредиты (то есть, остаток отсутствует), следовательно, ключевым требованием планировщика WFQ-ICM 20 является то, что системе требуется точно знать в каждый момент времени объем данных каждого дочернего элемента, доступный для передачи. Это требование предотвращает ситуации, когда дочерний элемент лишается права передавать данные, хотя они у него имеются, реализуя процессы перекрытия для определения права на передачу на основе практически возможной скорости передачи. В принципе, ограничения на скорость передачи могут заставить дочерний процесс прекратить передачу или оказаться без данных, доступных для родительского планировщика. Это ограничение также ведет к значительному повышению нагрузки на иерархические планировщики, когда ADA включает в себя все последующие очереди вне зависимости от количества уровней иерархии - требуется эффективное связывание процессов планирования между уровнями планирования.

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

КРАТКОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

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

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

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

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

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

На ФИГ.1 показана блок-схема примерного процесса планирования передачи данных в соответствии с традиционной технологией;

На ФИГ.2 показана блок-схема примерного процесса планирования передачи данных на основе справедливой организации очередей с использованием весовых коэффициентов и обратного управления кредитами;

На ФИГ.3 показана блок-схема примерного процесса планирования передачи данных на основе справедливой организации очередей с использованием весовых коэффициентов и обратного управления кредитами, сконструированного в соответствии с принципами настоящего изобретения;

На ФИГ.4 показана блок-схема примерного распределителя кредитов, сконструированного в соответствии с принципами настоящего изобретения;

На ФИГ.5 показана функциональная схема примерного процесса работы распределителя кредитов в соответствии с принципами настоящего изобретения;

На ФИГ.6 показана функциональная схема примерного процесса кредитования в ответ на изменения допустимости дочерних элементов в соответствии с принципами настоящего изобретения;

На ФИГ.7 показана блок-схема примерного одномерного циклического процесса планирования с использованием весовых коэффициентов и чередования для дочерних элементов с большими весами в соответствии с традиционной технологией;

На ФИГ.8 показана блок-схема примерного двумерного циклического процесса планирования с использованием весовых коэффициентов и чередования для дочерних элементов с большими весами, сконструированного в соответствии с принципами настоящего изобретения;

На ФИГ.9 показана блок-схема примерного двумерного циклического процесса планирования с использованием весовых коэффициентов и чередования, имеющего четыре уровня приоритетов, сконструированного в соответствии с принципами настоящего изобретения;

На ФИГ.10 показана блок-схема примерного базового селектора передачи, сконструированного в соответствии с принципами настоящего изобретения;

На ФИГ.11 показана блок-схема примерного усовершенствованного селектора передачи, сконструированного в соответствии с принципами настоящего изобретения;

На ФИГ.12 показана функциональная схема примерного процесса выбора дочерних элементов при справедливой организации очередей с использованием весовых коэффициентов в соответствии с принципами настоящего изобретения; и

На ФИГ.13 показана функциональная схема примерного процесса выбора в ответ на увеличение кредита и изменения допустимости дочерних элементов в соответствии с принципами настоящего изобретения.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

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

Такие связанные между собой термины, как «первый» и «второй», «нижний» и «верхний», и т.п., могут использоваться здесь исключительно для того, чтобы отличить одну сущность или элемент от другой сущности или элемента, не требуя и не подразумевая обязательного наличия между такими сущностями или элементами физического либо логического соотношения или порядка. «Корневой» узел обозначает узел высшего уровня в «дереве» справедливой организации очередей или узел высшего уровня в иерархическом «дереве» справедливой организации очередей. «Наследник» определенного узла представляет собой любой узел, находящийся ниже и связанный с этим определенным узлом. Аналогично, «предок» определенного узла представляет собой любой узел, находящийся выше и связанный с этим определенным узлом.. Термины «дочерний элемент», «дочерний узел» или «дочерние элементы» относятся к любым прямым наследникам узла в «дереве» планирования. В общем случае, при обсуждении отношений с определенным узлом термин «дочерний элемент» относится к узлу (узлу или очереди планировщика), расположенному на один уровень ниже рассматриваемого узла. Кроме того, любой узел, являющийся наследником узла более высокого уровня, может называться «дочерним узлом» или «дочерним элементом».

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

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

На ФИГ.3 показаны примерный планировщик справедливой организации очередей 28 с усовершенствованным обратным управлением кредитами ("WFQ-ICM-Plus"), сконструированный в соответствии с принципами настоящего изобретения, который включает в себя селектор передачи 30, распределитель кредитов 32 и базу данных кредитного состояния дочерних элементов 34. Селектор передачи 30 выбирает дочерний элемент среди допустимых дочерних элементов для передачи данных. Отдельный процесс определения допустимости 36 решает, допустимо ли выбрать дочерний элемент для передачи данных. Подробное описание функционирования процесса определения допустимости 36 находится за рамками настоящего изобретения; к нему имеет отношение только то, что процесс определения допустимости 36 решает, какие дочерние элементы допустимо выбирать. В простейшем виде процесс определения допустимости представляет собой данные, присутствующие в дочернем элементе. В более сложном виде имеющиеся данные могут содержать ограничения скорости обмена на различных уровнях иерархии. Это приводит к отличиям в поведении от традиционной технологии, состоящим в том, что дочерние элементы с отрицательными кредитами могут быть выбраны для передачи селектором передачи 30. Кроме того, в вариантах осуществления изобретения становится возможным «отключение» ранее допустимого дочернего элемента другим процессом, что также невозможно в рамках традиционной технологии.

Распределитель кредитов 32 включает в себя кредитный баланс ("СВ") 38, который содержит все избыточные кредиты для системы. Распределитель кредитов 32 представляет собой процесс справедливого распределения с использованием весовых коэффициентов, который предоставляет кредиты из кредитного баланса 38 всем допустимым дочерним элементам и всем дочерним элементам, имеющим отрицательные кредиты. Распределитель кредитов 32 в каждый момент времени отслеживает объем кредитов, выданных каждому дочернему элементу, в базе данных кредитного состояния дочерних элементов 34.

В отличие от предшествовавших планировщиков WFQ-ICM, варианты осуществления настоящего изобретения имеют то преимущество, что они не требуют от системы точно знать, сколько имеется данных. Вместо этого распределитель кредитов 32 должен знать то, что дочерний элемент является «допустимым». Распределитель кредитов 32 может распределять кредиты любому допустимому дочернему элементу. Таким образом, вместе с вариантами осуществления настоящего изобретения могут свободно функционировать взаимовлияющие процессы, например, формирователь сигнала скорости обмена (rate shaper). Теоретически дочерний элемент может получить намного больший объем кредитов, чем объем данных, которым в настоящее время располагает дочерний элемент или который сможет передать в ближайшее время. Однако, если дочерний элемент переходит из «допустимых» в «недопустимые», все кредиты, которые этот дочерний элемент приобрел, снимаются и возвращаются в кредитный баланс 38.

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

Существующие планировщики WFQ-ICM не позволяют осуществлять передачу дочерним элементам с отрицательным счетчиком кредита, кроме случаев, когда надо завершить передачу кадра, начатую при положительном счетчике кредита. Однако традиционная технология не позволяет «отключать» или делать недопустимыми для передачи дочерние элементы после получения кредитов, она не нуждается в этой возможности.

На ФИГ.4 показана упрощенная реализация примерного распределителя кредитов 32. В общем случае циклический распределитель кредитов 40 распределяет кредиты допустимым и имеющим отрицательный кредит дочерним элементам с той же скоростью, с которой из планировщика 28 выходят передачи данных. Другими словами, возможности передачи из селектора передачи 30 инициируют возможности распределения кредитов для распределителя кредитов 32.

В течение цикла распределения кредитов каждый допустимый дочерний элемент и дочерний элемент с отрицательным кредитом получают несколько входов в цикле в соответствии со своими весовыми коэффициентами. Каждый дочерний элемент в цикле получает один кредит, когда достигает начала циклической ("RR") очереди распределения 42. Другими словами, один цикл RR предоставляет каждому дочернему элементу один «кредит». Таким образом, в течение полного цикла кредитования каждому дочернему элементу "i" (обозначаемому child_i) предоставляется w_i кредитов, где "w_i" представляет собой значение весового коэффициента для child_i. Количество циклов RR, необходимое для распределения W; кредитов каждому дочернему элементу _i, равно w_i. Цикл кредитования завершается, когда каждый дочерний элемент child_i получает w _i кредитов. Таким образом, длительность цикла кредитования задается дочерним элементом с наибольшим w_i. Когда дочерний элемент получает полную величину своего веса в этом цикле, он временно помещается в очередь превышения весовых коэффициентов 44 для ожидания, и ему не распределяются кредиты до следующего цикла кредитования.

В существовавших до этого планировщиках WFQ-ICM распределение кредитов проходит точно на той же скорости, что и передача, поэтому никогда не бывает остатка кредитного баланса 38. Доступны для распределения те кредиты, которые возвращены из селектора передачи 30.

Напротив, варианты осуществления настоящего изобретения позволяют распределителю кредитов 32 поддерживать в случае надобности положительный кредитный баланс 32. Кредитный баланс 32 может стать очень большим из-за того, что ранее допустимые дочерние элементы, имея положительные кредиты, становятся недопустимыми. Чтобы компенсировать этот потенциально большой кредитный баланс кредитный баланс, распределителю кредитов 32 не требуется раздавать точно такое же количество кредитных байтов, приходящих от селектора передачи 30 (обозначенного как "N"), как байты, предоставляемые дочерним элементам (обозначенным как "М"). Таким образом, когда кредитный баланс 38 содержит излишние кредиты (то есть, СВ>0), распределитель кредитов 32 ускоряет распределение кредитов простым увеличением количества кредитов, предоставляемых за один полный цикл очереди распределения RR 42, так, что M>N. Другими словами, в течение цикла RR распределитель кредитов 32 распределяет М байтов кредита каждому дочернему элементу в порядке очереди. Все излишние кредиты могут переноситься на следующий цикл RR. С другой стороны, если кредитный баланс 38 при увеличении М обнуляется, частота распределения ("F") может быть увеличена так, чтобы M*F=N, тем самым, сохраняется возможность предоставления М байтов кредита каждому дочернему элементу до достижения конца цикла RR. Увеличение количества кредитов, предоставляемых в течение всего цикла RR, обеспечивает поддержание справедливости между дочерними элементами. Следует отметить несколько исключений в распределении увеличенного количества М байтов кредита: дочерние элементы, которые превысили бы свой вес после предоставления М байтов кредита, получают только остаток своего веса, а дочерним элементам, которые не являются допустимыми для передачи, но собирают кредит, чтобы вернуть его к нулевому значению, никогда не предоставляется больше кредитов, чем необходимо для возврата к нулевому значению кредита. Другие варианты осуществления распределителя кредитов - на основе управляющей очереди, вектора или других способов - также могут ускорить распределение кредитов путем увеличения «нормальной» скорости распределения кредитов принципиально аналогично описанному здесь способу.

На ФИГ.5 показана примерная функциональная схема, описывающая действия, выполняемые распределителем кредитов 32 в ответ на возможность распределить кредит. На ФИГ.5 распределитель кредитов 32 включается селектором передачи 30 один раз за N байтов переданных данных (этап S100), однако в другом варианте осуществления может присутствовать периодический триггер, решающий ту же задачу. Важно отметить, что в альтернативных вариантах осуществления настоящего изобретения распределитель кредитов 32 может обладать реальной информацией о суммарном количестве переданных байтов, чтобы кредиты могли распределяться группами или секциями по N байтов. Следует также отметить, что следующий процесс еще не учитывает изменений допустимости, однако вопросы допустимости принимаются в расчет ниже, см. ФИГ.5.

Если распределитель кредитов 32 находится не в начале цикла RR (этап S102), то есть, кредиты уже были распределены некоторым дочерним элементам в текущей очереди RR, процесс выбирает дочерний элемент child _i в начале текущей очереди RR для того, чтобы распределять ему кредиты (этап S104). В этом случае используется предшествующее состояние величины предоставляемого кредита М. Однако, если распределитель кредитов 32 готов начать новый цикл RR (этап S102), то есть, предыдущий цикл RR был завершен, распределитель кредитов 32 принимает решение, нужно ли продолжать цикл распределения кредитов, либо следует начать совершенно новый цикл кредитования (этап S106). Если это начало цикла кредитования, то для планирования выбирается очередь RR (этап S108). До настоящего момента рассматривался только процесс планирования, поддерживающий лишь одну очередь RR, поэтому этап S108 только сбрасывает параметры планирования и снова начинает обработку всех дочерних элементов для очереди RR. Однако, в соответствии с нижеприведенным описанием для ФИГ.8, примерный вариант осуществления настоящего изобретения поддерживает несколько очередей RR, отражающих различные приоритеты дочерних элементов, в этом случае этап S108 мог бы выбрать для обработки другую очередь RR. Если это не начало цикла кредитования, то новой очереди RR не требуется.

Возвращаемся к блоку принятия решений S106, если цикл кредитования только начинается, распределитель кредитов 32 определяет, существует ли избыточный кредитный баланс (этап S110), в этом случае - больше кредитов, чем может произвести событие одной передачи (N). Если существует избыточный кредитный баланс, распределитель кредитов 32 входит в цикл ускоренного распределение кредитов (этап S112), где объем распределения кредитов (М) во время этого события распределение кредитов и оставшихся событий распределения кредитов в текущем цикле RR превышает кредиты, переданные между событиями распределения кредитов (N), то есть, M>N. В противном случае, если остаток кредитного баланса отсутствует (этап S114), объем кредитов, который должен быть распределен в течение этого события распределения кредитов и в течение остатка цикла RR, устанавливается равным объему кредитов, обычно передаваемому между событиями распределения кредитов, то есть, M=N (этап S114). Отметим, что другие варианты осуществления настоящего изобретения могут использовать другие пороги для N в блоке принятия решения S110, например, СВ>x байтов, где x - статическое или динамическое число, применяемое для введения гистерезиса в решение для ускорения распределения кредитов.

Распределение кредитов начинается с выбора дочернего элемента child_i в начале текущей очереди RR (этап S104). Если кредитный баланс превышает или равен количеству кредитов, которое должно быть предоставлено каждому дочернему элементу за текущий цикл RR (этап S116), то есть, СВ>=М, дочернему элементу child_i предоставляется наименьшее из его остаточного веса в цикле кредитования и количеству кредитов, которое должно быть предоставлено за цикл RR (этап S118), М. Объем кредитов, предоставленных дочернему элементу child _i, вычитается из кредитного баланса (этап S120), а цикл RR переходит к следующему дочернему элементу в очереди RR (этап S122).

Возвращаемся к блоку принятия решений S116, если кредитный баланс превышает остаточный вес для дочернего элемента child_i (этап S124), то дочернему элементу child_i предоставляется его остаточный кредитный вес (этап S126). Объем кредитов, предоставленных дочернему элементу child_i, вычитается из кредитного баланса (этап S120), и цикл RR переходит к следующему дочернему элементу в очереди RR (этап S122). Однако, если остаточный вес для дочернего элемента child_i превышает кредитный баланс (этап S124), то кредиты не распределяются, и текущее событие распределения кредитов завершается, при этом дочерний элемент child_i остается в начале очереди RR в ожидании следующего события распределения кредитов.

На ФИГ.6 показана примерная функциональная схема, описывающая действия, выполняемые распределителем кредитов 32 в ответ на изменения состояния допустимости дочернего элемента. Распределитель кредитов 32 обнаруживает изменение состояния допустимости дочернего элемента child_i (этап S128). Изменения состояния допустимости могут объявляться отдельным процессом (внутри или вне планировщика), например, путем установки или очистки флага соответствующего дочернего элемента, передачи события или передачи сообщения. Если дочерний элемент child_i перешел из недопустимого состояния в допустимое (этап S130, ветка «ДА»), при этом дочерний элемент child_i уже находится в кредитной системе (этап S132, ветка «ДА»), распределитель кредитов 32 просто очищает флаг ожидания удаления для дочернего элемента child_i (этап S134). Как описано ниже в связи с этапом S150, этот флаг ожидания удаления был установлен для запроса удаления дочернего элемента из распределителя кредитов 32, когда он возвращается в нормальное состояние. Дочерний элемент child _i сохраняет способность получать кредиты в зависимости от своего веса и порядкового места в очереди RR. Однако, если дочерний элемент child_i в настоящий момент находится вне кредитной системы (этап S132, ветка «НЕТ»), и он еще не получил кредитов, превышающих его вес weight_i в цикле кредитования (этап S136, ветка «НЕТ»), то дочерний элемент child_i помещается в конец очереди RR (этап S138) и будет получать кредиты в свою очередь в нынешнем цикле кредитования. Если дочерний элемент child_i уже превысил свой вес weight_i в текущем цикле кредитования (этап S136, ветка «ДА»), то дочерний элемент child _i помещается в конец очереди превышения весов (этап S140) и не получит кредитов снова до начала следующего цикла кредитования.

Возвращаемся к блоку принятия решений S130, если осуществляющий переход дочерний элемент не является вновь допустимым дочерним элементом, то дочерний элемент переходит в состояние недопустимости. Если вновь недопустимый дочерний элемент child _i в настоящий момент обладает положительным кредитом или не обладает кредитами (этап S142), то есть, credits_i >=0, все излишние кредиты возвращаются в кредитный баланс (этап S144), а счетчик кредита for дочернего элемента child _i обнуляется (этап S146). Затем дочерний элемент child _i удаляется из кредитной системы (этап S148). Следует отметить, что удаление из кредитной системы проще всего достигается, если дождаться продвижения дочернего элемента в начало очереди RR и удалить этот дочерний элемент вместо того, чтобы давать ему кредит. Такой способ является одним из потенциальных вариантов использования флага удаления. Однако в других вариантах осуществления вновь недопустимый дочерний элемент child_i может удаляться из системы немедленно после возвращения его кредитов в кредитный баланс.

Возвращаемся к блоку принятия решений S142; если вновь недопустимый дочерний элемент обладает отрицательным кредитом, то есть, credits_i<0, просто устанавливается его флаг удаления, и он готов к удалению. Однако следует отметить, что все вновь недопустимые дочерние элементы с отрицательным кредитным балансом не удаляются из кредитной системы, пока не восстановят свой дефицит кредита кредитного баланса, то есть, дочерний элемент child_i не удаляется, пока не достигнет credits_i=0.

На ФИГ.7 блок-схема примерного одномерного циклического процесса планирования 46 ("WIRR") с использованием весовых коэффициентов и чередования для дочерних элементов с большими весами в соответствии с традиционной технологией. Процесс планирования WIRR 46 использует две очереди: циклическую ("RR") очередь 48 и очередь превышения веса 50. Все дочерние элементы, которые должны получать кредиты в цикле кредитования, начинают в очереди RR 48. При начальных условиях, показанных на ФИГ.7, где в очереди RR присутствуют четыре дочерних элемента (например, А, В, С и D), где А имеет вес 10, В имеет вес 4, а С и D имеют веса по 2. Поскольку количество циклов RR в одном цикле кредитования диктуется дочерним элементом с наибольшим весом, а дочерний элемент А имеет вес 10, один цикл кредитования может включать в себя до десяти циклов RR.

Во время первого цикла RR кредит выдается D, дочернему элементу, находящемуся в начале очереди RR 48, а затем D перемещается в конец очереди RR 48. Аналогичным образом, кредит выдается С, В и А, при этом каждый из дочерних элементов перемещается в конец очереди RR 48, таким образом, D возвращается в начало очереди. В течение цикла RR 2 кредит выдается D, при этом сумма кредитов, распределенных для D в этом цикле кредитования, больше или равна его весу, то есть, credit_D>=текущий RR. Таким образом, D перемещается в очередь превышения веса 50 до окончания этого цикла кредитования. Аналогичным образом, кредит выдается С, который затем перемещается в конец очереди превышения веса 50. Наконец, кредит выдается В и А, которые затем перемещаются в конец очереди RR 48. В течение цикла 3 один кредит выдается В, и один кредит выдается А. В течение цикла 4 один кредит также выдается В, и один кредит выдается А; однако, получив свой вес в виде кредитов за цикл кредитования, дочерний элемент В перемещается в конец очереди превышения веса 50, оставляя в очереди RR только А 48. В течение оставшихся циклов RR, например, циклов 5-10, дочернему элементу А предоставляется один кредит за цикл.

Эффективная последовательность распределения кредитов для этого одномерного WIRR выглядит так:

DCBA, DCBA, ВА, ВА, А, А, А, А, А, А.

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

Вариант осуществления настоящего изобретения улучшает процесс планирования WIRR, вводя новый двумерный планировщик WIRR, чтобы планировщик мог равномерно распределять кредиты дочерним элементам с большими весами. На ФИГ.8 показана блок-схема примерного двумерного планировщика WIRR 52, сконструированного в соответствии с принципами настоящего изобретения. Двумерный планировщик WIRR 52 реализует вместо одной очереди RR несколько очередей RR, представляющих пропускную способность или категории весов. Первое измерение планирования находится в пределах категории пропускной способности, где циклы кредитования WIRR обеспечивают справедливость между дочерними элементами в рамках одной категории пропускной способности. Второе измерение планирования - между категориями пропускной способности, где взвешенное чередование между очередями RR на обслуживание планировщиком первого измерения реализует множитель пропускной способности, связанный с категориями пропускной способности.

Двумерный планировщик WIRR 52 может включать в себя, по меньшей мере, два набора очередей RR, с которыми связаны очередь превышения веса, где каждая очередь "i" конфигурируется в качестве категории пропускной способности в виде множителя пропускной способности "n_i". Дочерние элементы чередуются в очереди RR на основе нормированных весов (позднее) в цикле WIRR и между очередями RR по порядку обслуживания очередей между полными циклами WIRR. В планировщике второго измерения очередь RR_i, имеющая множитель n_i, выполняется n_i раз столько полных циклов WIRR, сколько очередь при 1 (обозначено х1). Например, в двумерном планировщике WIRR 52 (ФИГ.8) присутствует высокоприоритетная ("HP") очередь RR 54, имеющая множитель 4, высокоприоритетная очередь превышения веса 56, низкоприоритетная ("LP") очередь RR 58, имеющая множитель 1, и низкоприоритетная очередь превышения веса 60. Цикл кредитования WIRR высокоприоритетной очереди 54 выполняется 4 раза для каждого выполнения цикла кредитования WIRR низкоприоритетной очереди.

Фиксированный шаблон для работы с очередями RR является приемлемым, если позволяет экономить трудозатраты, что значит, полезные решения по планированию могут приниматься даже в том случае, когда некоторые из очередей RR не содержат допустимых дочерних элементов. Например, для двумерного планировщика WIRR 52, имеющего HP очередь 54 с множителем х4 и LP очередь 58 с множителем х1, шаблон распределения кредитов выглядит так: HP, HP, HP, HP, LP, повтор. Веса, используемые для цикла кредитования WIRR, масштабируются множителем второго измерения, где нормированный вес равен полному весу, деленному на n_i.

Например, при использовании тех же весов и дочерних элементов, что использовались выше в связи с ФИГ.7, в двумерном планировщике WIRR 52 (ФИГ.8) дочерние элементы располагаются таким образом, что А и В находятся в HP очереди 54, а С и D находятся в LP очереди 58. Дочерний элемент А имеет нормированный вес 2,5, а его полный вес остается равным 10 (то есть, норм. вес * множитель = полный вес; 2,5*4=10). Аналогично, В имеет нормированный вес 1 и полный вес 4 (то есть, 1*4=4). Поскольку множитель для LP очереди 58 равен 1, С и D сохраняют свои первоначальные веса, равные 2.

В течение первого цикла кредитования WIRR двумерного WIRR обслуживается только HP очередь 54. Таким образом, распределитель кредитов в течение цикла WIRR 1 предоставляет В один кредит, А - два кредита, при этом сохраняется остаточный вес 0,5 дочернего элемента А. В течение цикла кредитования WIRR 2 снова обслуживается только HP очередь 54, однако в этот раз В получает 1 кредит, А получает 3 кредита (то есть, 2,5 веса для этого цикла + 0,5 остатка веса = 3 кредита). Третий цикл WIRR является повторением цикла WIRR 1, где В получает 1 кредит, А получает 2 кредита с остатком 0,5. Четвертый цикл WIRR является повторением цикла 2, где В получает 1 кредит, А получает 3 кредита. Пятый и последний цикл WIRR обслуживает LP очередь 58, при этом дочерние элементы С и D получают по 2 кредита. Таким образом, эффективный порядок предоставления кредитов за полный цикл кредитования для двумерного планировщика WIRR 52 выглядит так:

.

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

Алгоритм «не-O(1)», то есть, иерархический планировщик, имеющий вычислительную сложность, отличную от O(1) и использующий известную нотацию big-O, может быть удовлетворительным для второго измерения, поскольку масштабируемость не требуется. Как показано выше, сильное чередование ограничивает длину пакета от дочерних элементов с наибольшими весами. Несмотря на то, что вышеприведенное рассмотрение проводилось в контексте распределителя кредитов, предусматривается, что двумерный планировщик WIRR 52 настоящего изобретения может использоваться в качестве процесса планирования извлечения из очередей передачи селектором передачи 30.

Концепция двумерного WIRR может быть расширена для реализации систем, имеющих более двух уровней приоритета. На ФИГ.9 показана блок-схема планировщика WIRR 62, имеющего четыре уровня приоритета, представленных четырьмя приоритетными очередями RR: высокоприоритетная (HP) очередь 64, среднеприоритетная (МР) очередь 66, низкоприоритетная (LP) очередь 68 и очередь очень низкого приоритета (VLP) 70. Выбираются фиксированные множители между очередями, чтобы обеспечить большой динамический диапазон планирования. Например, предположим, что наибольшее нормированное значение веса для всех дочерних элементов во всех очередях RR равно 8, наименьший нормированный вес равен 1, максимальный суммарный вес для всех дочерних элементов составляет 4096 (8⁴ ). Выбор очереди осуществляется на основании веса, поэтому, когда все очереди содержат дочерние элементы, каждые 585 событий планирования HP очередь 64 выбирается 512 раз, МР очередь 66 выбирается 64 раза, LP очередь 68 выбирается 8 раз, a VL очередь 70 выбирается один раз. Планировщик WIRR 62 экономит трудозатраты, поэтому очереди, не содержащие дочерних элементов, не выбираются. Рассчитанный или сконфигурированный шаблон распределения кредитов должен стремиться к максимальному распределению возможностей планирования очередей с большими весами. Кроме того, каждый раз при выборе очереди должен выполняться полный стандартный цикл WIRR. Веса очередей, показанные на ФИГ.9, являются иллюстративными, но не представляют единственную стратегию «взвешивания» очередей RR. Например, другая стратегия использования весов могла бы обеспечивать равномерное изменение весов очередей вместо показанной экспоненциальной стратегии. Другая стратегия могла бы реализовать динамические веса очередей (множители), которые изменяются в зависимости от весов дочерних элементов, активных в системе.

Распределитель кредитов 32 реагирует на ненулевой кредитный баланс путем увеличения скорости распределения кредитов, другими словами, ускоренным распределением кредитов (CDA), которое обозначено как M>N на ФИГ.5. Способ CDA объединяет несколько циклов RR в одном цикле кредитования в один проход обработки вдоль очереди RR. Это достигается в рамках цикла кредитования любой категории одной полосы пропускания, поэтому второе измерение планирования явно не включается. Этот способ требует знания начала и окончания цикла RR и оценивает параметр величины CDA, или М, в начале каждого цикла RR. Количество циклов RR, объединенных в цикле CDA, обычно составляет 2 (М=2). Кажется также, что М следует увеличить до 4, когда кредитный баланс 38 относительно велик, для возможного конфигурирования в качестве порога для сравнения с кредитным балансом 38.

Другой вариант осуществления объединяет максимальное количество циклов RR в один проход путем выделения всего остаточного веса каждого дочернего элемента в текущем цикле кредитования, тем самым, цикл кредитования WIRR завершается. Еще одна реализация рассчитывает количество дочерних элементов, участвующих в цикле RR, и задает коэффициент ускорения 1+СВ / «количество дочерних элементов», эффективно ликвидируя кредитный баланс 38 за один проход по текущей очереди RR.

Способ CDA позволяет вернуть скорость распределения кредитов в норму в середине ускоренного цикла RR путем пропуска возможностей распределения кредитов. Другими словами, если М равно 2, а кредитный баланс 38 вернулся к нулевому значению, то кредиты распределяются только всеми прочими способами, например, M×N×0,5=N. Проверить непрерывное ускорение просто - пока кредитный баланс больше минимума из М и остаточного веса weight_i, дочерний элемент child_i в начале очереди RR может пользоваться кредитами.

Цикл за циклом RR на любом уровне приоритета может выполняться ускоренное распределение кредитов (CDA). CDA включается в начале цикла RR. В начале цикла RR выбирается коэффициент ускорения М, который действует в течение всего цикла RR. Присваивание дочерним элементам нормированных весовых коэффициентов меньших или равных 1 следует предотвратить, поскольку в ускорении данного типа могут принимать участие только дочерние элементы с нормированными весовыми коэффициентами >1. Дочерние элементы, чей остаточный вес в цикле кредитования меньше кредитов, которые навязывает CDA, получают только свой остаточный вес (то есть, возможность ускорения утрачена полностью или частично).

Теперь перейдем от распределителя кредитов 32 к селектору передачи 30, сконструированному в соответствии с принципами настоящего изобретения. Уже существующие планировщики с обратным управлением кредитами (ICM) содержали только одну очередь передачи, обслуживающую только дочерние элементы с положительными кредитами. Дочерние элементы выбирались для передачи, например, в соответствии с циклическим порядком и помещались в конец очереди передачи. Затем для передачи был выбран дочерний элемент, находившийся в начале очереди.

На ФИГ.10 показана примерная базовая структура управления передачей 72, сконструированного в соответствии с принципами настоящего изобретения. В соответствии с одним из вариантов осуществления настоящего изобретения, базовая структура управления передачей 72 включает в себя три отдельных очереди управления передачей данных: очередь положительных кредитов 74, очередь отрицательных кредитов 76 и очередь экстремальных отрицательных кредитов 78. Все дочерние элементы, которые являются допустимыми для выполнения передачи, например, работают и располагают данными, присутствуют в одной из очередей управления передачей данных. Селектор приоритета 80 выбирает очередь управления передачей данных, из которой следует выполнять передачу, на основании заданной системы приоритетов. Другими словами, очередь управления передачей данных с наивысшим приоритетом, которая содержит, дочерний элемент, всегда выбирается прежде очереди управления передачей данных, имеющей более низкий приоритет. В каждой из очередей управления передачей данных дочерние элементы выбираются просто циклически, то есть, без весовых коэффициентов. Возможность передачи создает соответствующую возможность распределения кредитов.

Дочерние элементы сортируются в очередь управления передачей данных на основании количества кредитов, которым они обладают. Дочерние элементы динамически перемещаются между очередями управления передачей данных по мере изменения их кредитного баланса. Дочерние элементы, имеющие положительное значение счетчик кредита, помещаются в очередь положительных кредитов 74. Если бы не функция «сброса кредита» в системе в случае, когда дочерний элемент становится недопустимым, ожидаемое поведение состояло бы в следующем: передают данные только дочерние элементы из очереди положительных кредитов 74. Поскольку настоящее изобретение допускает сброс кредита (когда кредитный баланс больше N), сумма всех кредитов, которыми обладают все активные дочерние элементы, может быть отрицательной. Дочерние элементы с отрицательным значением счетчика кредита помещаются в очередь отрицательных кредитов 76.

Стандартные очередь положительных кредитов передачи 74 и очередь отрицательных кредитов 76 содержат дочерние элементы с нормальными значениями счетчиков кредитов. Дочерние элементы в очереди положительных кредитов передачи 74 получили немного больше кредитов, чем осуществили передач, тогда как в очереди отрицательных кредитов передачи 76 получили немного меньше кредитов, чем осуществили передач. Передача из стандартной очереди положительных кредитов передачи 74 представляет собой нормальный режим работы в случае, если недопустимость не вызывает колебаний кредитного баланса 38. Однако многие дочерние элементы будут задержаны в очереди отрицательных кредитов передачи 76 после передачи до тех пор, пока счетчик кредита дочернего элемента не будет восстановлен распределителем кредитов 32.

Можно предположить, что сумма кредитов, которыми обладают в настоящий момент все активные дочерние элементы, может быть отрицательной, таким образом, некоторые дочерние элементы, обладающие отрицательным значением счетчика кредита, могут случайно получить право на передачу, еще больше снижая значение своего счетчика кредита. Однако дочерние элементы с большим количеством передач при отрицательных значениях могут быть отделены, чтобы уменьшить «несправедливость». Таким образом, устанавливается пороговое значение, например, отрицательной величины максимального объема передачи для среды передачи, при этом дочерние элементы, имеющие отрицательный кредитный баланс ниже этого порога, помещаются в очередь экстремальных отрицательных кредитов 78. Передача из очереди экстремальных отрицательных кредитов 78 предполагает наличие очень большого избытка кредитного баланса 38 в распределителе кредитов 32, который может требовать специального внимания. Очередь экстремальных отрицательных кредитов 78 предотвращает «скатывание» дочерних элементов к очень низкому кредитному балансу, если только не все дочерние элементы участвуют в этом «скатывании». Передача из очереди экстремальных отрицательных кредитов 78 указывает на проблему с кредитным балансом 38, которая вызывает нестабильность системы. Чрезвычайной мерой, которая может быть предпринята для защиты кредитного баланса 38 от дополнительного роста, является уменьшение скорости траты кредита на передачу (например, тратить на передачу N/4 вместо N кредитов). Такая неравномерность стоимости передачи данных вносит ошибку в алгоритм справедливой организации очередей с использованием весовых коэффициентов, поскольку на передачу некоторых данных будет тратиться N, а других - N/4, однако это простая реализация защиты от бесконечного роста кредитного баланса 38.

Дополнительные варианты осуществления используют более усовершенствованную структуру управления передачей 82, как показано ФИГ.11. Такая усовершенствованная структура управления передачей 82 объединяет три очереди управления передачей данных, рассмотренные выше, с дополнительными очередями, которые (не обязательно) могут использоваться для повышения гибкости планирования и добавления новых свойств. Например, структура управления передачей 82 может объединять дочерние элементы с заданным приоритетом, например, дочерние элементы, содержащие пакеты речевых данных, с дочерними элементами справедливой организации очередей посредством очереди управления обходом высшего приоритета 84. Усовершенствованная структура управления передачей 82 и рассмотренная выше методология позволяет объединять планирования с приоритетами и справедливую организацию очередей с минимальными затратами.

Необязательные очереди управления передачей данных могут также включать в себя очередь экстремальных положительных кредитов 86 и очередь неизвестных дочерних элементов 88. Очередь экстремальных положительных кредитов 86 предотвращает скачки счетчика кредита, вызванные остановкой системы передачи, тем самым, повышая устойчивость кредитного баланса. Несмотря на то, что очередь экстремальных положительных кредитов 86 не является обязательной, ее использование желательно, поскольку дочерние элементы с большими весовыми коэффициентами при отсутствии приоритетной передачи могут быстро наращивать кредиты. Большие запасы кредитов представляют опасность для стабильности системы, поскольку в случае, если дочерний элемент становится недопустимым, кредиты внезапно возвращаются в кредитный баланс 38. Если какой-то дочерний элемент обладает большим значением счетчика кредита, селектор передачи 30 должен опросить дочерний элемент, чтобы определить, нет ли опасности достижения этим дочерним элементом верхнего порога кредита. Верхний порог кредита может устанавливаться разработчиком системы в соответствии с характеристиками среды передачи, включая такие параметры, как текущий трафик. Если дочерний элемент нарушает верхний порог кредита, этот дочерний элемент должен быть перемещен в очередь экстремальных положительных кредитов 86, чтобы получать приоритетное обслуживание. Очередь неизвестных дочерних элементов 88 допускает возможность, что дочерний элемент известен родительскому планировщику, который пока не известен текущему планировщику. Если текущий планировщик выбирается для планирования и не имеет других допустимых дочерних элементов, то необходимый дочерний элемент предоставляет очередь неизвестных дочерних элементов 88.

На ФИГ.12 показана примерная функциональная схема, описывающая действия, выполняемые селектором передачи 30 во время выбора дочерних элементов при справедливой организации очередей. Селектор передачи 30 определяет, если дочерний элемент является новым выбором (этап S152). Если нет, селектор передачи 30 продолжает передавать кадр из очереди и(или) из дочернего элемента, совпадающей (совпадающего) с предыдущим выбором (этап S154). Если выбор является новым (этап S152), селектор передачи 30 выбирает очередь передачи с наивысшим приоритетом, содержащую дочерние элементы для извлечения (этап S156), и выбирает child _i в начале очереди передачи для осуществления передачи (этап S158). После выбора дочернего элемента для передачи селектор передачи 30 вычитает количество переданных байтов ("N") из суммы имеющихся кредитов (credit_i) для этого дочернего элемента child_i (этап S160). Когда селектор передачи 30 достигает конца передачи (этап S162), если child_i не является более допустимым (этап S164), child_i удаляется из системы передачи (этап S166), то есть, child _i более не является видимым для селектора передачи 30. Однако, если child_i остается допустимым (этап S164), child_i снова помещается в конец очереди передачи, которая подходит для оставшегося количества кредитов дочернего элемента credits_i (этап S168).

На ФИГ.13 показана примерная функциональная схема, описывающая действия, выполняемые селектором передачи 30 в ответ на увеличение кредитов и изменения допустимости. Селектор передачи 30 определяет, является ли child_i новым дочерним элементом (этап S170), что означает его отсутствие в системе очередей селектора передачи. Если child_i не является новым, а селектор передачи 30 определяет, что child_i не является более допустимым (этап S172), то в случае, если child_i в настоящий момент не передает данные (этап S174), child_i удаляется из системы передачи (этап S176). В противном случае, если child _i в настоящий момент передает данные (этап S174), селектор передачи 30 не реагирует. Такая реакция наблюдается в рамках процесса извлечения из очереди, ФИГ.12.

Возвращаемся снова к блоку принятия решений S172, если child_i является допустимым, a credits_i указывает, что дочерний элемент получил достаточно новых кредитов для смены уровней приритета (этап S178), поскольку child_i в настоящее время не осуществляет передачу (этап S180), то child_i удаляется из текущей очереди передачи (этап S182) и помещается в конец очереди передачи, обозначенной количеством credits_i (этап S184), то есть, очереди передачи с более высоким приоритетом.

Кроме того, обращаемся снова к блоку принятия решений S170, если child_i представляет собой новый дочерний элемент, селектор передачи 30 просто помещает child_i в конец очереди передачи, обозначенной количеством credits _i (этапы S184).

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

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

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

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