Способ управления передачей пакетов потоков цифровой информации

 

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

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

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

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

Известен способ управления передачей пакетов, в котором каждому из передаваемых потоков информации приписан определенный приоритет, причем этот приоритет динамически изменяется во времени так, что пакет из очереди с приоритетом j перемещается в очередь с приоритетом j+1, после того как время его пребывания в буфере превысит контрольное время Т, значение которого равно разнице между допустимыми задержками для очередей с приоритетами j и j+1 (S. S. Panwar, D. Towsley, and J. К. Wolf. Optimal scheduling policies for a class of queues with customer deadlines to the beginning of services. Journal of the ACM, 35(4): 832-844, October 1988).

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

Известен также способ, в котором каждому потоку информации выделена определенная полоса пропускания, которая в случае отсутствия в буферном пространстве порта сетевого оборудования пакетов какого-либо потока информации делится между присутствующими потоками информации в соответствии с одним из применяемых критериев (ЕР 0 859 492 А2, 19.08.1998).

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

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

Наиболее близким к предложенному способу является способ управления передачей пакетов ВСО (Взвешенная Справедливая Очередность - Weighted Fair Queuing), заключающийся в том, что создается система очередности отправления пакетов в соответствии с полосой пропускания, занимаемой каждым потоком информации, а также общим количеством потоков информации, пакеты которых находятся в данный момент времени в буферном пространстве порта сетевого оборудования (A. Demers, S. Keshav, S. Shenker "Analysis and Simulation of a Fair Queuing Algorithm" Internetworking: Research and Experience, pp. 3-26, vol. 1, 1990). Данный способ является реализацией теоретической "жидкостной модели" передачи потоков информации, в которой предполагается, что пакеты обладают бесконечно малым размером, а несколько источников могут одновременно передавать пакеты через единый порт сетевого оборудования.

В соответствии со способом ВСО перед началом передачи пакетов каждому из передаваемых потоков информации каждому приписывается величина Ф_i, называемая "весом", которая соответствует полосе пропускания R_i ^выд, выделяемой потоку информации i. Значение R_i ^выд вычисляется так, чтобы выполнялось следующее равенство: где N - множество передаваемых потоков информации; R - общая полоса пропускания порта сетевого оборудования.

В способе ВСО, в случае отсутствия пакетов потока информации j, его полоса пропускания перераспределяется между остальными потоками пропорционально их весам. Это обеспечивается тем, что очередность отправления пакетов, находящихся в буферном пространстве порта сетевого оборудования, определяется возрастанием виртуальных завершающих времен, вычисляемых в соответствии со следующей формулой: где а_i ^j - реальное время прибытия j-го пакета i-го потока; L_i ^j - длина этого пакета; ν(t) - параметр виртуального времени, который в свою очередь вычисляется в соответствии со следующим выражением: где N_f является множеством потоков информации, пакеты которых находятся в данный момент времени в буферном пространстве порта сетевого оборудования.

При этом предполагается, что в случае, когда т. е. когда в буферном пространстве полностью отсутствуют пакеты, параметр виртуального времени ν(t) равен 0.

Предположим (см. фиг.1), что способ ВСО обслуживает потоки информации - 102а, 102b, 102с, пакеты которых временно находятся в буферном пространстве В порта сетевого оборудования 101, полоса пропускания R этого порта равна 10 пакет/с и веса передаваемых потоков информации равны 20, 30, 50% соответственно. Тогда, если в буферном пространстве есть пакеты всех потоков информации, потоки информации 102а, 102b, 102с получат полосы пропускания в 2, 3, 5 пакет/с соответственно. Однако если, например, в буферном пространстве порта нет пакетов потока информации 102с, то тогда свободная полоса будет равна 5 пакет/с и способ ВСО распределит эту полосу между 102а и 102b пропорционально их весам, и таким образом в данный момент времени они получат полосы пропускания в 4 и 6 пакет/с соответственно.

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

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

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

Для решения поставленной задачи с достижением технического результата в известном способе управления передачей пакетов через порт оборудования сети с коммутацией пакетов, в котором перед началом передачи пакетов каждому из передаваемых потоков информации выделяют часть полосы пропускания порта сетевого оборудования, после чего вычисляют для каждого пакета, находящегося в буферном пространстве порта, виртуальное завершающее время в соответствии с его длиной, реальным временем его прибытия, полосами пропускания, выделенными потокам информации, количеством потоков информации, пакеты которых находятся в данный момент времени в буферном пространстве порта, отправляют из буферного пространства порта пакет с наименьшим виртуальным завершающим временем, перед началом передачи пакетов каждому из N передаваемых потоков информации выделяют часть В_i ^выд (i=1,2...N) буферного пространства порта В, равную произведению выделенной ему полосы пропускания и допустимой задержки передачи его пакетов, и устанавливают значения верхнего коэффициента заполнения Р_верх выделенного ему буферного пространства, которое берут из интервала от 0 до 1, нижнего коэффициента заполнения Р_ниж выделенного ему буферного пространства, которое берут из интервала от 0 до Р_верх, контрольного интервала времени Т_конт, после чего в реальном времени для каждого потока информации измеряют занимаемое им буферное пространство B_i ^зан (i=1,2...N), как сумму всех пакетов этого потока информации, находящихся в данный момент времени в буферном пространстве порта, и если при получении пакета какого-либо потока информации, занимаемое этим потоком информации буферное пространство В_i ^зан превышает выделенное ему буферное пространство В_i ^выд в течение интервала времени Т_конт, то выделенное ему буферное пространство В_i ^выд увеличивают на величину ΔB^ув, определяемую по формуле:

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

а если при отправлении пакета какого-либо потока информации, занимаемое этим потоком информации буферное пространство B_i ^зан меньше в течение интервала времени Т_конт, чем произведение выделенного ему буферного пространства В_i ^выд и нижнего коэффициента заполнения Р_ниж, то выделенное ему буферное пространство В_i ^выд уменьшают на величину ΔB^ум, определяемую по формуле:

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

Возможны дополнительные варианты осуществления способа, в которых целесообразно, чтобы:
- значение верхнего коэффициента заполнения P_верх брали из диапазона от 0,7 до 0,9, а нижнего коэффициента заполнения Р_ниж - из диапазона от 0,2 до 0,6;
- удаление пакетов из буферного пространства порта сетевого оборудования осуществляли случайным образом с одинаковой вероятностью для всех этих пакетов, равной обратной величине от их текущего количества;
- значение контрольного интервала времени Т_конт устанавливали равным характерному интервалу времени, в течение которого изменение скорости потока много меньше средней скорости потока в этом интервале времени.

На фиг.1 показана общая схема передачи пакетов потоков информации через порт сетевого оборудования.

На фиг.2 показана функциональная структура интегральной схемы.

На фиг. 3 показана зависимость обобщенной величины потерь пакетов, усредненной по всем передаваемым потокам информации, от значения верхнего коэффициента заполнения P_верх при различных значениях нижнего коэффициента заполнения Р_ниж (кривая 1 - Р_ниж=0,1; кривая 2 - Р_ниж=0,2; кривая 3 - Р_ниж= 0,4; кривая 4 - Р_ниж=0,6).

На фиг. 4 показана зависимость общей частоты изменения выделенных ресурсов, усредненной по всем передаваемым потокам информации, от значения верхнего коэффициента заполнения P_верх при различных значениях нижнего коэффициента заполнения Р_ниж (кривая 1 - Р_ниж = 0,2, кривая 2 - Р_ниж=0,6; кривая 3 - Р_ниж=0,7).

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

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

На фиг. 7 показана зависимость части сеансов связи с обеспеченным качеством передачи пакетов от общего количества сеансов связи для способа ВСО (кривая 1) и для предлагаемого способа при различных значениях его количественных характеристик:
- Р_ниж=0,1/Р_верх=0,2/Т_конт=0,033 с (кривая 2);
- Р_ниж=0,2/Р_верх=0,7/Т_кoнm=0,033 с (кривая 3);
- Р_ниж=0,6/Р_верх=0,9/Т_конт=0,033 (кривая 4);
- Р_ниж=0,8/Р_верх=0,9/Т_конт=0,033 с (кривая 5).

Средством реализации предлагаемого способа является известная интегральная схема 201 (см. фиг.2), устанавливаемая в корпусе сетевого оборудования, состоящая из микропроцессора 209, постоянного запоминающего устройства 208 (ПЗУ), оперативного запоминающего устройства 203 (ОЗУ), устройства ввода/вывода 205, внутренней шины 204, тактового генератора 210, контроллера прерывания 211.

Данная интегральная схема является стандартным микроконтроллером, также называемым в русскоязычной литературе однокристалльным ЭВМ (ОЭВМ), и в качестве ее примера можно привести широко распространенные 16-разрядные микроконтроллеры серии MCS-96 компании Intel.

Разряд 207 одного из порта устройства ввода/вывода 205 программируют на вход. В него поступают пакеты, которые после этого направляются в кэш-память 202 оперативного запоминающего устройства 203, которое является буферным пространством порта сетевого оборудования В, т. е. в ней поступившие пакеты временно хранятся перед отправлением. В общем случае в группу ОЗУ 203 входят несколько устройств кэш-памяти, в том числе и внешних ОЗУ, и в данном случае одна из них является буферным пространством порта сетевого оборудования.

Разряд 206 одного из порта устройства ввода/вывода 205 программируют на выход. Данный разряд связан с портом сетевого оборудования. Через него передаются пакеты, отправляемые из кэш-памяти 202.

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

Предлагаемый способ реализуется следующим образом.

Перед установлением сеанса связи каждому потоку информации 102а, 102b, . . ., 102N, передаваемому через порт оборудования сети с коммутацией пакетов, в порте сетевого оборудования 101 (см. фиг.1), имеющего буферное пространство В и полосу пропускания R, выделяют полосы пропускания R_а ^выд, R_b ^выд . . . R_N ^выд, сумма которых равна R, что осуществляется посредством известного программирования интегральной схемы 201, при котором в ОЗУ 203 вводят значение полос пропускания R_a ^выд, R_b ^выд ... R_N ^выд. Обычно это программирование осуществляется оператором связи при настройке сетевого оборудования.

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

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

После выделения полос пропускания R_a ^выд, R_b ^выд ... R_N ^выд, потокам информации 102а, 102b, ..., 102N выделяют буферные пространства В_a ^выд, В_b ^выд, .. . , В_N ^выд, значения которых равняются произведению полос пропускания _a ^выд, R_b ^выд . . . R_N ^выд и допустимой задержки передачи пакетов потоков информации 102а, 102b... 102N соответственно.

Это осуществляется посредством того, что микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, вычисляет значение упомянутых буферных пространств, как произведения полос пропускания R_a ^выд, R_b ^выд . . . R_N ^выд и допустимой задержки передачи пакетов потоков информации 102а, 102b... 102N, значения которых хранятся в ОЗУ 203, и помещает значения буферных пространств B_a ^выд, B_b ^выд . . . B_N ^выд в ОЗУ 203. После этого в соответствии с программным кодом, хранящимся в ПЗУ 203, микропроцессор 209 разбивает известным способом кэш-память 202 так, чтобы она содержала N областей памяти размерами B_a ^выд, B_b ^выд ... B_N ^выд, в которые микропроцессор 209 помещает получаемые пакеты только потоков информации 102a, 102b ... 102N соответственно.

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

В выделенных буферных пространствах B_a ^выд, B_b ^выд ... B_N ^выд располагаются пакеты только потоков информации 102а, 102b... 102N соответственно. Отсюда следует, что если занимаемое потоком информации буферное пространство (длина очереди пакетов этого потока информации) меньше, чем выделенное ему буферное пространство, то:
1. все принимаемые пакеты этого потока информации будут расположены в буферном пространстве порта;
2. все пакеты этого потока информации, находящиеся в буферном пространстве порта, будут отправлены в пределах допустимой задержки их передачи.

Таким образом, смыслом буферных пространств B_a ^выд, B_b ^выд ... B_N ^выд, выделенных потокам информации 102а, 102b... 102N, является то, что они являются минимальными размерами буферных пространств, которые необходимо гарантировать потокам информации для передачи их пакетов через порт сетевого оборудования без потерь, т. е. обобщенная величина потерь пакетов этих потоков информации в данном случае будет равна 0.

В качестве ресурсов, выделенных потокам информации 102а, 102b... 102N, рассматриваются полосы пропускания R_a ^выд, R_b ^выд ... R_N ^выд и буферные пространства B_a ^выд, B_b ^выд, ..., B_N ^выд соответственно.

Коэффициентом заполнения P_i ^зап выделенного какому-либо потоку информации буферного пространства В_i ^выд, называется отношение занимаемого этим потоком буферного пространства B_i ^зан к выделенному этому потоку буферному пространству В_i ^выд :
P_i ^зап = B_i ^зан/B_i ^выд.

Таким образом, коэффициент заполнения P_i ^зап определяет степень, на которую заполнено выделенное потоку информации буферное пространство В_i ^выд. Верхний и нижний коэффициенты заполнения P_верх и Р_ниж, которые будут подробно описаны ниже, являются фиксированными значениями коэффициента заполнения Р_i ^зап.

Для каждого потока информации устанавливают:
1. значение верхнего коэффициента заполнения Р_верх, которое берут из интервала от 0 до 1;
2. значение нижнего коэффициента заполнения Р_ниж, второе берут из интервала от 0 до Р_верх;
3. значение контрольного интервала времени Т_конт.

Это осуществляется посредством известного программирования интегральной схемы 201, при котором в ОЗУ 203 вводят значения коэффициентов заполнения P_веpx и Р_ниж и контрольного интервала времени Т_конт. Обычно это программирование осуществляется оператором связи при настройке сетевого оборудования.

Также в ОЗУ 203 хранятся значения описанных выше параметров качества передачи пакетов, метод и средства установления (и соответственно ввода в ОЗУ) которых являются известными и не относятся к предметам предлагаемого изобретения. В качестве примера их установления можно привести способ, при котором используют модифицированный протокол резервирования ресурсов (S. Shenker, I. Breslau. Two issues in reservation establishment. Computer Communications Review, 25(4): 16-24, October 1995).

To, что значения верхнего коэффициента заполнения P_верх берут из интервала от 0 до 1, а нижнего коэффициента заполнения Р_ниж - из интервала от 0 до Р_верх, позволяет избежать неопределенности, возникающей в случае равенства значений коэффициентов Р_ниж и Р_верх, а также при равенстве значения одного из коэффициентов 0 или 1 (по определению интервал (а, b) не включает в себя концы а и b).

После установления сеанса связи в реальном времени для каждого потока информации измеряют занимаемое им буферное пространство B_i ^зан (i=1,2... N), как сумму всех пакетов этого потока информации, находящихся в данный момент времени в буферном пространстве порта, что осуществляется посредством того, что микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, суммирует длины всех пакетов этого потока информации, находящихся в данный момент времени в кэш-памяти 202, и помещает значение буферного пространства _i ^зан (i=1,2...N) в ОЗУ 203.

В реальном времени микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, сравнивает для каждого потока информации:
1. занимаемое этим потоком информации буферное пространство В_i ^зан (i= 1,2...N) и выделенное ему буферное пространство В_i ^выд (i=1,2... N);
2. занимаемое этим потоком информации буферное пространство В_i ^зан (i= 1,2...N) и произведение выделенного ему буферного пространства B_i ^выд (i=1,2. ..N) и значения нижнего коэффициента заполнения Р_ниж.

Если значение буферного пространства B_i ^зан превышает в данный момент времени значение B_i ^зан, то микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, осуществляет увеличение в соответствии с изменением реального времени значения временного интервала Т_i ^ув, хранящегося в ОЗУ 203, в обратном случае - значение временного интервала Т_i ^ув обнуляется.

Если значение буферного пространства B_i ^зан меньше в данный момент времени, чем произведение выделенного ему буферного пространства В_i ^выд и нижнего коэффициента заполнения Р_ниж, то микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, осуществляет увеличение в соответствии с изменением реального времени значения временного интервала Т_i ^ум, хранящегося в ОЗУ 203, в обратном случае - значение временного интервала Т_i ^ум обнуляется (перед установлением сеансов связи значения временных интервалов Т_i ^ув и Т_i ^ум равняются 0).

Таким образом, текущее значение временного интервала Т_i ^ув является непрерывным промежутком времени, в течение которого занимаемое потоком информации буферное пространство B_i ^зан превышает выделенное ему буферное пространство В_i ^выд, а значение Т_i ^ум - непрерывным промежутком времени, в течение которого занимаемое потоком информации буферное пространство B_i ^зан меньше, чем произведение выделенного ему буферного пространства В_i ^выд и значения нижнего коэффициента заполнения Р_ниж.

Получаемый через разряд 207 устройства ввода/вывода 205 j-й пакет i-го потока информации помещается микропроцессором 209 в кэш-память 202, который при этом фиксирует время получения а_i ^j этого пакета и помещает значение времени а_i ^j в ОЗУ 203.

Если при получении пакета потока информации 102i текущее значение занимаемого этим потоком буферного пространства B_i ^зан превышает выделенное ему буферное пространство B_i ^выд в течение интервала времени Т_конт, то считается, что буферное пространство B_i ^выд и соответственно полоса пропускания R_i ^выд являются недостаточными для передачи пакетов потока информации 102i с обеспечением требуемых параметров качества и необходимо их увеличение.

В данном случае выделенное потоку информации буферное пространство В_i ^выд увеличивают на величину ΔB^ув_i, определяемую по формуле:

что осуществляется посредством того, что при достижении временного интервала T_i ^ув значения Т_конт, микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, последовательно выполняет:
1. вычисление по приведенной выше формуле значения величины ΔB^ув_i, используя при этом значения верхнего коэффициента заполнения Р_верх и выделенных буферных пространств B_a ^выд, B_b ^выд... B_N ^выд, хранящихся в ОЗУ 203;
2. увеличение значения буферного пространства B_i ^выд, хранящегося в ОЗУ 203, на величину ΔB^ув_i;
3. увеличение области памяти кэш-памяти 202, в которую микропроцессор 209 помещает получаемые пакеты только потока информации 102i, так чтобы ее размер равнялся значению выделенного буферного пространства B_i ^выд, хранящегося в ОЗУ 203;
4. обнуление значения временного интервала Т_i ^ув, хранящегося в ОЗУ 203.

Увеличение буферного пространства B_i ^выд на величину ΔB^ув(1)_i, определяемую по формуле:

соответствует варианту, при котором B_i ^выд увеличивают так, чтобы отношение нового значения выделенного потоку 102i буферного пространства B_i ^выд к предыдущему значению буферного пространства B_i ^выд равнялось значению верхнего коэффициента заполнения P_верх.

Отсюда следует, что смыслом значения верхнего коэффициента заполнения P_верх является то, что оно является коэффициентом заполнения буферного пространства B_i ^выд, выделенного потоку информации 102i после его увеличения. Значение верхнего коэффициента заполнения P_веpx определяет размер, на который увеличивают выделенные потокам информации ресурсы, - чем меньше значение верхнего коэффициента заполнения Р_верх, тем больше размер, на который увеличивают полосу пропускания и буферное пространство, выделенные какому-либо потоку информации.

Однако в связи с тем, что буферное пространство порта сетевого оборудования имеет ограниченный размер, возможна ситуация, при которой увеличение на величину ΔB^ув(1)_i невозможно, так как она превышает буферное пространство В^невыд, которое является частью буферного пространства порта В, не выделенной никаким потокам информации. В данном случае, выделенное буферное пространство B_i ^выд увеличивают на величину В^невыд, то есть так, чтобы сумма буферных пространств, выделенных всем потокам информации, равнялась буферному пространству порта сетевого оборудования В.

Значение величины ΔB^ув(2)_i, на которую в данном случае увеличивают выделенное буферное пространство B_i ^выд, определяется по формуле:
.

Таким образом, в соответствии с описанными выше ситуациями, в общем случае увеличение буферного пространства B_i ^выд, выделенного какому-либо потоку информации, осуществляют на меньшую из двух величин - ΔB^ув(1)_i и ΔB^ув(2)_i, что и определяет представленную выше величину ΔB^ув_i/.
Перед увеличением буферного пространства B_i ^выд, выделенного рассматриваемому потоку информации, из буферного пространства порта сетевого оборудования удаляют пакеты других потоков информации, лежащие вне выделенных им буферных пространств, в таком количестве, чтобы сумма длин удаленных пакетов была не меньше, чем величина ΔB^уд_i, определяемая по формуле:

Это осуществляется посредством того, что микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, последовательно выполняет:
1. вычисление по приведенной выше формуле значения величины ΔB^уд_i, используя при этом значения верхнего коэффициента заполнения Р_верх, выделенных буферных пространств B_a ^выд, B_b ^выд... B_N ^выд и занимаемых буферных пространств B_a ^зан, B_b ^зан... B_N ^зан, хранящихся в ОЗУ 203;
2. удаление из кэш-памяти 202 пакетов, не принадлежащих рассматриваемому потоку информации и не лежащих в выделенных потокам информации буферных пространствах, до тех пор, пока суммарная длина этих пакетов не достигнет, по крайней мере, величины ΔB^уд;
Приведенная формула для вычисления ΔB^уд имеет следующее объяснение.

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

Для осуществления упомянутого выше увеличения буферного пространства B_i ^выд необходимо, чтобы величина свободного буферного пространства В^своб превышала или, по крайней мере, равнялась величине ΔB^ув_i. Разность величины ΔB^ув_i и свободного буферного пространства В^своб определяет приведенную формулу для вычисления ΔB^уд.
Возможны два варианта, определяющие количество пакетов, которое удаляют, при различных значениях величины ΔB^уд:
1. в случае если свободное буферное пространство В^своб меньше, чем ΔB^ув_i (это означает, что ΔB^уд>0), то рассматриваемый признак соответствует удалению количества пакетов, суммарная длина которых не меньше, чем ΔB^уд;
2. в случае если свободное буферное пространство В^своб больше или равняется, чем ΔB^ув_i (это означает, что ΔB^уд<0 или ΔB^уд=0 соответственно), то рассматриваемый признак соответствует удалению пакетов в любом количестве (в том числе и не удалению ни одного пакета). Это объясняется тем, что суммарная длина любого количества пакетов (принимая очевидное предположение о том, что суммарная длина нулевого количества пакетов равняется 0) является заведомо числом неотрицательным и, соответственно, большим, чем ΔB^уд.
Отсюда следует, что в общем случае для упомянутого увеличения выделенного буферного пространства B_i ^выд необходимо увеличение буферного пространства В^своб на величину, равную или превышающую ΔB^уд.
Увеличение буферного пространства В^своб возможно только за счет удаления пакетов потоков информации, лежащих вне выделенных им буферных пространств. Не допустимо удаление пакетов, лежащих в буферных пространствах B_a ^выд, B_b ^выд. .. B_N ^выд, выделенных потокам информации 102а, 102b,... 102N, так как, как было упомянуто при описании смысла выделенных потокам информации буферных пространств B_a ^выд, B_b ^выд... B_N ^выд, все лежащие в них пакеты должны быть переданы без потерь.

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

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

Это осуществляется посредством того, что микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, вычисляет для каждого пакета, находящегося в кэш-памяти 202, известное виртуальное завершающее время, в соответствии со следующими параметрами:
1. длиной рассматриваемого пакета;
2. количеством потоков информации, пакеты которых находятся в данный момент времени в кэш-памяти 202;
3. полосами пропускания, выделенными потокам информации, значения которых хранятся в ОЗУ 203;
4. реальным временем прибытия рассматриваемого пакета, значение которого хранится в ОЗУ 203.

После этого, микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, отправляет из кэш-памяти 202 через разряд 206 устройства ввода/вывода 205, запрограммированного на выход, пакет с наименьшим виртуальным временем.

Если при отправлении пакета какого-либо потока информации занимаемое этим потоком информации буферное пространство B_i ^зан меньше в течение интервала времени Т_конт, чем произведение выделенного ему буферного пространства B_i ^выд и значения нижнего коэффициента заполнения Р_ниж, считается, что буферное пространство B_i ^выд и соответственно полоса пропускания R_i ^выд являются избыточными для передачи пакетов потока информации 102i с обеспечением требуемых параметров качества и необходимо их уменьшение. Выделенное этому потоку информации буферное пространство B_i ^выд уменьшают на величину ΔB^ум, определяемую по формуле:

что осуществляется посредством того, что при достижении временного интервала Т_i ^ув значения Т_конт, хранящегося в ОЗУ 203, микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, последовательно выполняет:
1. вычисление по приведенной выше формуле значения величины ΔB^ум_i, используя при этом значения верхнего коэффициента заполнения P_верх и выделенного буферного пространства B_i ^выд, хранящихся в ОЗУ 203;
2. уменьшение значения буферного пространства B_i ^выд, хранящегося в ОЗУ 203, на величину ΔB^ум_i;
3. увеличение области памяти кэш-памяти 202, в которую микропроцессор 209 помещает получаемые пакеты только потока информации 102i, так чтобы ее размер равнялся значению выделенного буферного пространства B_i ^выд, хранящегося в ОЗУ 203;
4. обнуление значения временного интервала Т_i ^ум, хранящегося в ОЗУ 203.

Уменьшение выделенного буферного пространства B_i ^выд на величину ΔB^ум(1)_i, определяемую по формуле:

соответствует варианту, при котором выделенное буферное пространство B_i ^выд уменьшают на величину ΔB^ум(1)_i, равную описанной выше величине ΔB^ум(1)_i, т.е. уменьшение буферного пространства B_i ^выд производят симметрично (в части величины изменения) относительно его увеличения.

Однако для интервала значений верхнего коэффициента заполнения Р_верх от 0 до 0,5, который является допустимым, значение величины ΔB^ум(1)_i превышает буферное пространство B_i ^выд, и в данном случае буферное пространство B_i ^выд уменьшают до 0, т. е. осуществляют уменьшение на величину ΔB^ум(2)_i, равную B_i ^выд.

Таким образом, в соответствии с описанными выше ситуациями, в общем случае уменьшение буферного пространства B_i ^выд, выделенного какому-либо потоку информации, осуществляют на меньшую из двух величин - ΔB^ум(1)_i/ и ΔB^ум(2)_i, что и определяет представленную выше величину ΔB^ум_i.
Из описанного выше следует, что смыслом значения нижнего коэффициента заполнения Р_ниж является то, что оно определяет минимальный допустимый коэффициент заполнения буферного пространства B_i ^выд, выделенного какому-либо потоку информации, в том плане, что при степенях использования буферного пространства B_i ^выд выше Р_ниж, выделенные потоку информации ресурсы не считаются избыточными.

Из описанного выше также следует, что смыслом контрольного интервала времени Т_конт является то, что он определяет максимальный промежуток времени, в течение которого допустимо (без изменения выделенных ресурсов), чтобы:
1. занимаемое каким-либо потоком информации буферное пространство B_i ^зан превышало выделенное ему буферное пространство B_i ^выд;
2. занимаемое этим потоком информации буферное пространство B_i ^зан было меньше, чем произведение выделенного ему буферного пространства B_i ^зан и значения нижнего коэффициента заполнения Р_ниж.

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

Контрольный интервал времени Т_конт необходим для того, чтобы:
1. избежать частой настройки выделенных ресурсов, вызванной лишь кратковременными изменениями плотности потока;
2. изменять выделенные потоку информации ресурсы, если скорость какого-либо потока информации меньше или больше выделенной ему полосы пропускания в течение длительного времени.

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

Это осуществляется посредством того, что микропроцессор 209, в соответствии с программным кодом, хранящимся в ПЗУ 208, осуществляет для потока информации (102i), выделенное которому буферное пространство B_i ^выд было изменено, обновление значения полосы пропускания R_i ^выд, хранящегося в ОЗУ 203, так чтобы оно равнялось отношению буферного пространства B_i ^выд к допустимой задержке передачи его пакетов.

Для определения оптимальных диапазонов коэффициентов заполнения Р_ниж и Р_верх был проведен эксперимент, в котором через порт маршрутизатора Cisco 2610 компании Cisco Systems с буферным пространством размером 128 Кбит и полосой пропускания 10 Мбит/с, передавалось 50 потоков оцифрованной видео информации с кодировкой MPEG-1. Все эти потоки информации являлись частями одного и того же мультипликационного фильма и имели одинаковую структуру.

Скорость каждого потока информации периодически менялась во времени и имела следующие параметры:
1) средняя скорость - 128 Кбит/с,
2) максимальная во времени (пиковая) скорость - 1,2 Мбит/с.

Всем этим потокам информации соответствовали следующие параметры качества передачи пакетов:
1) допустимая задержка передачи пакетов потоков информации - 0,01 с,
2) допустимая обобщенная величина потерь пакетов - 1%.

Из фиг.3 видно, что при значениях верхнего коэффициента заполнения Р_верх менее 0,7 и значениях нижнего коэффициента заполнения Р_ниж менее 0,2, для части передаваемых потоков информации происходит превышение допустимой обобщенной величины потерь пакетов 1%. Из этого следует, что для достижения более высокого количества сеансов связи с обеспеченным качеством передачи пакетов потоков информации значения коэффициентов заполнения Р_верх и Р_ниж целесообразно брать из диапазонов от 0,7 и от 0,2 соответственно.

Из фиг. 4 видно, что для всех рассматриваемых значений нижнего коэффициента заполнения Р_ниж при росте значения верхнего коэффициента заполнения P_верх частота изменения ресурсов увеличивается, причем наиболее значительно при значениях коэффициентов заполнения P_веpx более 0,9 и Р_ниж более 0,6. Большое количество изменений ресурсов, выделенных потоку информации, оказывает сильное влияние на вычислительные ресурсы микропроцессора 209 интегральной схемы 201. В частности, при частоте изменений ресурсов 20 с^-1 иногда наблюдался сбой работы сетевого оборудования, вызванный перезапуском его операционной системы. Для избежания слишком частого изменения ресурсов значения коэффициентов заполнения P_верх и Р_ниж целесообразно брать из диапазонов от 0 до 0,9 и от 0 до 0,7 соответственно.

Таким образом, с учетом результатов на фиг.3 и фиг.4 значения коэффициентов заполнения Р_ниж и Р_верх целесообразно брать из диапазонов от 0,2 до 0,6 и от 0,7 до 0,9 соответственно.

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

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

Для потока оцифрованной видео информации с кодировкой MPEG-1, которой соответствует частота дискретизации 30 кадров/с, значение характерного интервала времени, в течение которого скорость потока приблизительно постоянна, равно обратной величине от частоты дискретизации. Следовательно, в соответствии с теоретическим обоснованием значение контрольного интервала Т_конт целесообразно брать равным 0,033 с.

На фиг. 5 и фиг.6 видно, что при росте значения интервала Т_конт уменьшается частота изменения ресурсов и увеличивается обобщенная величина потерь пакетов, а значение времени Т_конт, равное 0,033 с, обеспечивает и небольшую частоту изменения ресурсов в 10 с^-1, и приемлемую обобщенную величину потерь пакетов в 1%, что таким образом подтверждает теоретическое обоснование.

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

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

На фиг. 7 видно, что при реализации предлагаемого способа достигается увеличение по сравнению со способом ВСО количества сеансов связи с обеспеченным качеством передачи пакетов потоков информации для интервала времени Т_конт, равного 0,033 с, и для значений коэффициентов заполнения Р_ниж и Р_верх из интервалов от 0,1 до 0,8 и от 0,2 до 0,9 соответственно.

В качестве примера можно привести результаты данного исследования, показывающие количество сеансов связи с обеспеченным качеством передачи пакетов, для общего количества сеансов, равного 45:
1) для способа ВСО - 14% (6 сеансов связи);
2) для предлагаемого способа при Р_ниж = 0,1 и Р_верх = 0,2 - 21% (9 сеансов связи);
3) для предлагаемого способа при Р_ниж = 0,2 и Р_верх = 0,7 - 30% (14 сеансов связи);
4) для предлагаемого способа при Р_ниж = 0,6 и Р_верх = 0,9 - 59% (26 сеансов связи);
5) для предлагаемого способа при Р_ниж = 0,8 и Р_верх = 0,9 - 78% (35 сеансов связи).

Это подтверждает достижение технического результата при использовании предлагаемого способа для количественных характеристик способа, выраженных в виде интервала значений, которыми являются:
1. верхний коэффициент заполнения Р_верх (значения из интервала от 0 до 1);
2. нижний коэффициент заполнения Р_ниж (значения из интервала от 0 до P_веpx).

Все программные коды, в соответствии с которыми микропроцессор 209 выполняет описанные выше операции по обработке или передаче данных, вводят в ПЗУ 208 посредством известного программирования интегральной схемы 201. Обычно это программирование осуществляется разработчиком интегральной схемы при ее изготовлении.

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

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

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

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

1. Способ управления передачей пакетов через порт оборудования сети с коммутацией пакетов, в котором перед началом передачи пакетов каждому из передаваемых потоков информации выделяют часть полосы пропускания порта сетевого оборудования, после чего вычисляют для каждого пакета, находящегося в буферном пространстве порта, виртуальное завершающее время в соответствии с его длиной, реальным временем его прибытия, полосами пропускания, выделенными потокам информации, количеством потоков информации, пакеты которых находятся в данный момент времени в буферном пространстве порта, отправляют из буферного пространства порта пакет с наименьшим виртуальным завершающим временем, отличающийся тем, что перед началом передачи пакетов каждому из N передаваемых потоков информации выделяют часть _i ^выд(i = 1, 2, ..., N) буферного пространства порта B, равную произведению выделенной ему полосы пропускания и допустимой задержки передачи его пакетов, и устанавливают значения верхнего коэффициента заполнения Р_верх выделенного ему буферного пространства, которое берут из интервала от 0 до 1, нижнего коэффициента заполнения Р_ниж выделенного ему буферного пространства, которое берут из интервала от 0 до Р_верх, и контрольного интервала времени Т_конт, после чего в реальном времени для каждого потока информации измеряют занимаемое им буферное пространство B_i ^зан(i = 1, 2, ..., N), как сумму всех пакетов этого потока информации, находящихся в данный момент времени в буферном пространстве порта, и если при получении пакета какого-либо потока информации занимаемое этим потоком информации буферное пространство B_i ^зан превышает выделенное ему буферное пространство B_i ^выд в течение интервала времени Т_конт, то выделенное ему буферное пространство B_i ^выд увеличивают на величину ΔB^ув, определяемую по формуле

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

а если при отправлении пакета какого-либо потока информации занимаемое этим потоком информации буферное пространство B_i ^зан меньше в течение интервала времени Т_конт, чем произведение выделенного ему буферного пространства B_i ^выд и нижнего коэффициента заполнения Р_ниж, то выделенное ему буферное пространство B_i ^выд уменьшают на величину ΔB^ум, определяемую по формуле

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

2. Способ по п.1, отличающийся тем, что значение верхнего коэффициента заполнения Р_верх берут из диапазона от 0,7 до 0,9, а нижнего коэффициента заполнения Р_ниж - из диапазона от 0,2 до 0,6.

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7