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

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

1. Способ управления потоками при передаче пакетов данных, заключающийся в том, что предварительно для N>1 потоков пакетов данных устанавливают параметры их обработки, принимают пакеты данных, идентифицируют по принадлежности к одному из потоков, передают в память k-го порта центра коммутации, запоминают их, обрабатывают и передают отправителю подтверждение о приеме очередного пакета, одновременно из числа ранее обработанных пакетов выделяют пакеты для последующей передачи и передают их получателю, отличающийся тем, что в качестве параметров обработки потоков данных устанавливают размер выделенной памяти Ввы, дискретное значение объема памяти В и функцию коэффициента задержки подтверждения Р(В), дополнительно при приеме пакетов данных измеряют время t_m, где m=0,1,2,..., в течении которого текущее значение объема памяти В_T , занятого пакетами данных всех принимаемых потоков, изменится на величину В, среднюю в интервале времени t_m, интенсивность поступления _i(t_m) пакетов i-го потока, где, i=1,2,3...N, из канала связи и среднюю интенсивность их передачи _i(t_m) получателю, по измеренным значениям _i(t_m) и _i(t_m) рассчитывают среднюю в интервале времени t_m скорость заполнения памяти Pзап. пакетами i-го потока, а по текущему значению памяти Вт, занятой пакетами данных всех принимаемых потоков, вычисляют текущее значение функции коэффициента задержки подтверждения Р_m(В_T ), передачу подтверждения о приеме очередного пакета в следующем интервале времени t_m задерживают на время tкв _(m+1)i, причем время задержки tкв _(m+1)n передачи подтверждения о получении очередного пакета данных для i-го потока вычисляют после измерения параметров В_T, _i(t_m), _i(t_m) и расчета скорости заполнения памяти Rзап_mi в интервале времени t_m.

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

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

4. Способ по п.1, отличающийся тем, что дискретное значение объема памяти В выбирают из условия

где M(2·N) максимально допустимое к обработке число потоков.

5. Способ по п.1, отличающийся тем, что скорость заполнения памяти пакетами i-го потока рассчитывают по формуле Rзап= _i(t_m)- _i(t_m).

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

Изобретение относится к электросвязи, а именно к способам управления потоками данных в сетях асинхронной передачи дискретной информации с пакетной коммутацией, в частности к системам управления трафиком (Трафик - нагрузка, создаваемая потоком вызовов, сообщений и сигналов, поступающих на средства связи [Федеральный закон "О связи". - Российская газета 10.07.2003. -№135]), проходящего через центры коммутации пакетов. Способ может быть использован в коммутаторах и маршрутизаторах потоков пакетов данных с целью повышения их производительности (Производительность - интенсивность своевременно обслуженного потока пакетов [Захаров Г.П. Методы исследования сетей передачи данных. - М.: Радио и связь, 1982. - 208 с., ил. на стр.22,25]).

Заявленное техническое решение расширяет арсенал средств аналогичного назначения.

Известен способ управления потоками при передаче пакетов данных по патенту США №5311513, "Способ предотвращения перегрузки в пакетной сети" кл. Н 04 L 12/56, заявл.05.10.1994. Известный способ включает следующую последовательность действий. Предварительное установление статистических параметров обработки потоков пакетов, прием пакетов данных от источника, присвоение каждому пакету потока, статистические параметры которого совпадают с предварительно заданными, высшего приоритета обработки, если статистические параметры потока пакетов находятся вне этих границ, пакетам присваивается низший приоритет, запоминание пакетов в память, обработка их в соответствии с приоритетом и передача получателю, в случае полного заполнения памяти поступающие пакеты стираются.

Недостатком данного способа является низкая производительность коммутационных устройств сети передачи данных в условиях перегрузки, что обусловлено резким увеличением времени пребывания пакетов в памяти коммутационных устройств, а так же возможностью ее блокировки (Блокировка - невозможность передачи данных на каком-либо участке сети из-за полной занятости ресурсов [Протоколы информационно-вычислительных сетей: Справочник /С.А.Аничкин, С.А.Белов, А.В.Бернштейн и др.; Под ред. И.А.Мизина, А.П.Кулешова. - М.: Радио и связь, 1990.-504 с.: ил, на стр.203]) при высокой интенсивности трафика, кроме того, пакеты одного сообщения могут получить различные приоритеты обработки, это снижает вероятностно-временные характеристики передачи сообщения в центрах коммутации пакетов и усложняет процедуру упорядочения и сборки пакетов одного сообщения в месте назначения, так же пользователь услугами связи лишается возможности самостоятельно устанавливать приоритет сообщений.

Также известен способ управления потоками при передаче пакетов данных по патенту Япония №6-164625 кл. Н 04 L 12/48, G 06 F 13/00 "Способ и устройство для управления скоростью потока пакетов" заявл.06.10.1994, 1994. Известный способ включает следующую последовательность действий: предварительное установление параметров обработки потоков пакетов, индивидуальных для каждого потока, прием пакетов данных от источника, сравнение периода поступления пакетов с установленными периодом Т, по результатам сравнения запись пакетов в память или их стирание, передача пакетов получателю.

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

Наиболее близким по технической сущности к заявленному является способ управления потоками при передаче пакетов данных по патенту РФ №2183912, "Способ управления передачей пакетов потоков цифровой информации", МПК Н 04 L 12/56, заявл. 09.02.2001. Способ-прототип заключается в том, что предварительно устанавливают параметры обработки пакетов, общие для всех потоков данных: контрольный интервал времени Т _конт, верхний Р_верх и нижний P_нижн коэффициент заполнения памяти. Одновременно устанавливают параметры обработки пакетов, индивидуальные для i-го потока, где i=1,2,3...N, N - общее число потоков: интенсивность обслуживания пакетов _i, допустимое время задержки пакетов Т_допi , размер выделенной памяти В_выдi= _i Т_допi.

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

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

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

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

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

Поставленная цель достигается тем, что в известном способе управления потоками при передаче пакетов данных, заключающемся в том, что предварительно для N1 потоков пакетов данных устанавливают параметры их обработки, принимают пакеты данных, идентифицируют по принадлежности к одному из потоков, передают в память k-го порта центра коммутации, запоминают их, обрабатывают и передают отправителю подтверждение о приеме очередного пакета, одновременно из числа ранее обработанных пакетов выделяют пакеты для последующей передачи и передают их получателю, в качестве предварительно устанавливаемых параметров задают размер объема памяти Ввыд, дискретное значение объема памяти B и функцию коэффициента задержки подтверждения Р(В_T ). Дополнительно при приеме пакетов данных измеряют время t _m, где m=0,1,2,..., в течение которого текущее значение объема памяти В_T, занятого пакетами данных всех принимаемых потоков, изменится на величину В. Кроме того, измеряют среднюю в интервале времени t_m интенсивность поступления _i(t_m) пакетов i-го потока из канала связи, где i=1,2,3...N и среднюю интенсивность их передачи _i(t_m) получателю. По измеренным значениям _i (t_m) и _i(t_m) рассчитывают среднюю в интервале времени t_m скорость заполнения памяти Rзап_mi пакетами каждого потока. По текущему значению памяти В_т , занятой пакетами данных всех принимаемых потоков, вычисляют текущее значение функции коэффициента задержки подтверждения Р_m(B_T). Передачу подтверждения о приеме очередного пакета в следующем интервале времени t_(m+1) задерживают на время tкв _(m+1)i. Причем время задержки tкв _(m+1)i передачи подтверждения о получении очередного пакета данных для i-го потока вычисляют после измерения параметров В_T, _mi и _mi в интервале времени t_m по формуле

В качестве функции коэффициента задержки подтверждения Р(В_T) выбирают линейную или экспоненциальную, или тригонометрическую функции, а дискретное значение объема памяти В выбирают из расчета где M(2·N).

Среднюю скорость заполнения памяти пакетами i-го потока в интервале времени t_m рассчитывают по формуле Rзап _mi= _i(t_m)- _i(t_m).

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

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

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

Заявленный способ поясняется чертежами:

фиг.1 - блок-схема алгоритма, реализующего способ управления потоками;

фиг.2 - график зависимости периода поступления пакетов от времени передачи подтверждения;

фиг.3 - график изменения периода поступления пакетов при изменении времени задержки подтверждения.

фиг.4 - график изменения интенсивности трафика и состояния памяти ЦК при ее неограниченном объеме;

фиг.5 - график изменения интенсивности трафика и состояния памяти ЦК при управлении потоками в соответствии со способом, заявленном в прототипе;

фиг.6 - график изменения интенсивности трафика и состояния памяти ЦК при управлении потоками в соответствии с заявленным способом;

фиг.7 - график зависимости вероятности своевременной обработки пакетов в ЦК от интенсивности их обработки при различных способах управления потоками.

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

Известные способы локального управления потоками (см., например, В.М. Вишневский "Теоретические основы проектирования компьютерных сетей" Москва: Техносфера, 2003, стр.273-287; В.Г.Олифер, Н.А.Олифер "Компьютерные сети. Принципы, технологии, протоколы" СПб.: Питер, 2003, стр.634-644), в соответствии с которыми ограничивается либо общее количество пакетов в памяти центра коммутации либо объем памяти, выделяемой разным классам пакетов, включают в себя действия, присущие описанным выше аналогам.

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

Предотвращение перегрузки может быть выполнено с помощью глобального управления потоками, которое основывается на механизмах квитирования и концепции окна (см., например, С.А.Аничкин, С.А.Белов, А.В.Бернштейн и др. Протоколы информационно-вычислительных сетей: Справочник под ред. И.А. Мизина, А.П. Кулешова - М.: Радио и связь, 1990, стр.203-207). Данные способы позволяют снизить нагрузку на сеть в целом, однако не предотвращают возможность блокировки памяти отдельных центров коммутации. Кроме того, они предусматривают передачу пакетов с установлением соединения и наличием служебной информации, передаваемой между входными и выходными узлами. Следовательно, данные способы требуют дополнительного расхода ресурсов сети.

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

На решение данной проблемы и направлен заявленный способ, блок-схема алгоритма которого представлена на фиг.1.

Предварительно устанавливают параметры обработки пакетов, общие для всех потоков: объем памяти Ввы _k, выделенной для k-го порта центра коммутации, дискретное значение объема памяти В и функцию коэффициента задержки подтверждения Р(В_T ). Величина объема дискретного значения памяти определяется выражением где М - значение частоты дискретизации М памяти определяется в соответствии с теоремой Котельникова В.А. по формуле M2·N, где N1 число потоков пакетов данных, обрабатываемых ЦК в k-ом направлении передачи. Выбор значения М определяет чувствительность системы управления потоками пакетов данных к изменению их интенсивности. Изменение значения функции коэффициента задержки подтверждения Р(В_T) позволит регулировать время задержки подтверждения приема очередного пакета. Затем принимают пакеты N потоков. При приеме пакетов их идентифицируют по принадлежности к одному из потоков и передают в память k-го порта центра коммутации объемом Ввыд для последующей обработки.

Измеряют время t _m, в течение которого произошло изменение занятого объема памяти на величину B и текущее значение объема памяти занятого пакетами всех потоков В_т. Вычисляют среднюю на интервале t _m интенсивность обслуживания пакетов _i(t_m), принадлежащих различным потокам, которая может зависеть от категории срочности пакетов и требований потока к качеству обслуживания и среднюю интенсивность поступления пакетов _i(t_m). Рассчитывают скорость Rзап_mi заполнения памяти k-го порта пакетами i-го потока в интервале времени t _m. Порядок расчета скорости заполнения буфера Rзап _mi пакетами i-го потока приведен в Приложении 1.

В заявленном способе интенсивность i-го поступающего потока _mi находится в зависимости от скорости заполнения памяти Rзап_mi. пакетами этого потока и от состояния буфера B_T:

где Pm(В_T) - функция коэффициента задержки подтверждения. Влияние функции коэффициента задержки подтверждения Р_m(B_T) на интенсивность поступления пакетов _i(t_m) обосновывается в Приложении 2.

Интенсивность поступления пакетов i-го потока _mi изменяют за счет изменения времени передачи подтверждения о факте получения очередного пакета этого потока на величину tкв _(m+1)i (фиг.2, 3). На графике фиг.2 - среднее время между поступлениями пакетов в интервале времени t_m,а - среднее расчетное время между поступлениями пакетов этого потока на следующий этап итерации. Время задержки передачи подтверждения tкв _(m+1)i факта получения пакетов i-го потока рассчитывают по формуле:

Вывод формулы 2 представлен в Приложении 3.

После истечения времени задержки передачи подтверждения tкв _(m+1)i передают подтверждение отправителю о получении очередного пакета.

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

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

Выбор вида функции Р(В_T) может определяться характером трафика, передаваемого по сети, особенностями обработки и передачи пакетов данных по каналам и трактам.

Таким образом, изменение времени подтверждения на величину tкв _mi, рассчитанную по формуле 2, приводит к адаптации периода поступления пакетов i-го потока (фиг.3) в соответствии с объемом памяти заполненного пакетами всех потоков Вт и скорости ее заполнения пакетами i-го потока Rзап_mi, что позволяет предотвратить возможность блокирования памяти ЦК и дифференцировать интенсивность поступления в ЦК пакетов в соответствии с их требованиями по качеству обслуживания в сети передачи данных. Это обеспечивает повышение производительности центров коммутации пакетов.

Возможность достижения заявленного эффекта проверена путем математического моделирования трафика и процесса его обработки в ЦК и поясняется графиками фиг.4-7, построенными по результатам моделирования.

При нестационарном характере трафика интенсивность поступления пакетов в ЦК обладает свойством самоподобия и имеет определенный период Т_cn (см., например, Городецкий А.Я., Заборовский B.C. Фрактальные процессы в компьютерных сетях. / СПб.: Изд-во СПбГТУ, 2000, с.101 на стр.48-57). На графиках фиг.4 представлен один из возможных вариантов изменения интенсивности поступления пакетов _сп(t) и интенсивности их обработки _cn(t) в ЦК (фиг.4, график "а"), а так же процесс заполнения и освобождения памяти ЦК (фиг.4, график "б") на одном периоде самоподобия T_cn. В силу необходимости выполнения вероятностно-временных требований по передаче пакетов данных или по техническим причинам память ЦК имеет ограниченный объем Ввыд в этих условиях изменение текущего объема памяти B _T имеет вид, представленный на фиг.5, график "б". После заполнения памяти поступающие в ЦК пакеты стирают, но отправитель передает их повторно до тех пор, пока не получит подтверждение о приеме. На графике фиг.5 график "а", показано изменение интенсивности поступления пакетов _on(t) в случае ограниченного объема памяти в ЦК при использовании способа управления потоками пакетов, описанного в прототипе.

На графиках фиг.6 представлено изменение интенсивности поступления пакетов _уn(t) и процесс заполнения и освобождения памяти B _T при использовании заявленного способа управления потоками пакетов.

Известно (см., например, Захаров Г.П. Методы исследования сетей передачи данных. М.: Радио и связь, 1982.-208 с., ил. на стр.22, 25), что производительность ЦК прямо пропорциональна вероятности своевременной обработки пакетов Q в центре коммутации. На графиках фиг.7 показана зависимость вероятности своевременной обработки пакетов в ЦК от интенсивности их обработки при различных объемах выделенной памяти Ввыд, где Q_on - вероятность своевременной обработки пакетов в ЦК при использовании способа управления потоками пакетов, описанного в прототипе, Q_уn - вероятность своевременной обработки пакетов при использовании заявленного способа управления потоками пакетов. Вероятность своевременной обработки пакетов при управлении потоками в соответствии с заявленным способом значительно повышается, особенно при низкой интенсивности обработки пакетов в ЦК.

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

Приложение 1

Расчет скорости заполнения буфера пакетами i-го потока

Известно (см., например, Л.Клейнрок Теория массового обслуживания", пер. с англ. И.И.Грушко; ред. В.И.Нейман - М.: Машиностроение, 1979, стр.31-34), что интенсивность суммарного поступающего потока равна а интенсивность суммарного обработанного потока где nпост_mi и nобр_{mi -} количество поступивших и обработанных пакетов i-го потока соответственно в интервале времени t_m.

Скорость заполнения памяти Rзап _m пакетами всех потоков определяется по формуле: а дискретный объем памяти B, заполненный пакетами за время t_m, есть разность межу всеми поступившими и обработанными пакетами в этом интервале времени B(t _m)=nnocm_m-nобр_m, тогда:

Скорость Rзап_mi заполнения памяти к-го порта пакетами i-го потока в интервале времени t _m соответственно равна разности между интенсивностью поступления пакетов этого потока и интенсивностью их обработки:

Rзап_mi= _I(t)m-(t _m).

Приложение 2

Влияние функции коэффициента задержки подтверждения

на интенсивность поступления пакетов

Суммарная интенсивность обработки пакетов (t _m) определяется состоянием памяти и не может быть выше своего максимального значения, определяемого пропускной способностью канала связи:

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

Суммарная интенсивность поступления пакетов N потоков определяется по формуле (см. приложение 1) из приведенной формулы следует, что потоки, интенсивность обработки которых в центре коммутации выше, будут иметь меньшую скорость заполнения памяти при равной интенсивности поступления пакетов на вход ЦК.

Установление зависимости скорости заполнения памяти Rзап_m от объема памяти В_T, заполненного пакетами всех потоков приведет к дифференцированному изменению интенсивности поступления пакетов i-го потока _i(t_m) в ЦК, так как, чем выше скорость заполнения памяти пакетами i-го потока Rзап_mi, тем сильнее ограничивается этот поток, при этом интенсивность поступления пакетов i-го потока _i(t_m) определяется выражением:

Таким образом, интенсивность поступления пакетов i-го потока (t _m) будет находиться в зависимости от интенсивности обработки пакетов этого потока _i(t_m) в ЦК и от состояния буфера. Кроме того, при установлении такой зависимости вероятность перегрузки центра коммутации значительно снижается.

Приложение 3

Расчет времени задержки передачи подтверждения

Известно (см., например, Л.Клейнрок "Теория массового обслуживания", пер. с англ. И.И.Грушко; ред. В.И.Нейман - М.: Машиностроение, 1979. стр.27-30), что среднее время между поступлениями пакетов в ЦК определяют как а среднее время их обработки в ЦК и среднее время ожидания пакетов в памяти ЦК в интервале времени t=t _m-t_(m-1) определяют как

Среднее время между поступлениями пакетов i-го потока варьируют путем изменения времени задержки подтверждения факта получения очередного пакета на величину . (фиг.2). Среднее на интервале t_m время между моментами поступления пакетов i-го потока определяют как . Время ожидания пакетов в памяти где tож _(m+1)i - величина изменения времени ожидания пакетов i-го потока в памяти ЦК на следующий интервал времени t_(m+1) . Для изменения среднего времени между поступлениями пакетов изменяют время задержки подтверждения tкв _i, которое рассчитывают по формуле:

После ряда преобразований это выражение принимает вид: