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

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

 

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

Известны способы управления трафиком в системе связи, основанные на принципе "протекающего ведра". Этот принцип или его специфическая разновидность также упоминаются как маркерный банк (Token Bank) или маркерный "ковш" (Token Bucket). Принцип "протекающего ведра" раскрыт, например, в работе: (Raif О. Onvural: Asynchronous Transfer Mode Networks, Performance Issues, Arctech House Inc. 1994 (ISBN 0-89006-662-0), Chapter 4.5.1. Принцип "протекающего ведра" используется, например, в алгоритме GCRA (Универсальный алгоритм для скорости передачи элементов данных) функции UPC (Управление параметром использования) сети АТМ, причем GCRA применяют для контроля того, соответствует ли трафик элементов данных согласованному трафику рассматриваемого соединения.

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

Известен способ, реализованный в способе и устройстве задания скорости передачи данных в многопользовательской системе связи по А.с. №118473, кл. Н 04 Q 11/04, 08.09.1994. Способ позволяет оптимизировать использование ресурсов связи в системе связи множественного доступа с кодовым разделением каналов. При этом измеряют степень использования ресурсов связи, сравнивают измеренную степень использования, по меньшей мере, с одним предварительно определенным порогом, генерируют сигнал управления скоростью передачи в соответствии с результатом сравнения и кодируют действующее сообщение в виде множества передаваемых кадров. Наряду с этим осуществляют кодирование подмножества из множества передаваемых кадров при пониженной скорости кодирования и кодирование других кадров из множества передаваемых кадров с более высокой скоростью кодирования в соответствии с упомянутым сигналом управления скоростью передачи.

Кроме того, известно устройство управления передачей данных по радиоканалу А.с. №20010610 RU, кл. Н 04 L 29/12, 02.11.99, в котором решается задача повышения эффективности использования сети. Устройство управления передачей данных по радиоканалу включает триггер цикла передачи, входы сброса и установки которого соединены между собой и являются сигнальным входом устройства, а выход соединен с инверсным входом первого элемента "И" и входом формирователя импульсов, синхронизатор, выход которого соединен с прямым входом первого элемента "И", выход которого соединен с первым входом второго элемента "И", второй вход которого соединен со входом установки триггера и является управляющим входом устройства, вход сброса триггера соединен с выходом третьего элемента "И", прямой вход которого соединен с первым входом четвертого элемента "И" и выходом элемента задержки, инверсный вход третьего элемента "И" соединен с выходом четвертого элемента "И" и является выходом "Столкновение" устройства, выход формирователя импульсов соединен с первым входом блока определения интенсивности входного потока, выход генератора интервалов анализа соединен со вторым входом блока определения интенсивности входного потока, выход второго элемента "И" соединен с первым входом элемента "ИЛИ" и входом элемента задержки, выход элемента "ИЛИ" является выходом "Разрешение передачи" устройства, выход триггера соединен со вторым входом элемента "ИЛИ" и является выходом "Включение передатчика" устройства, отличающееся тем, что дополнительно введены блок вычисления пропускной способности, блок принятия решения, блок вычисления среднего параметра дальнодействия, счетчик, демультиплексор, N блоков определения параметра дальнодействия, блок определения удаляемого корреспондента, N-входовый элемент "И", N-входовый элемент "ИЛИ", блок коммутации, при этом выход блока определения интенсивности входного потока соединен с первым информационным входом блока вычисления пропускной способности и входом "Интенсивность входного потока" блока принятия решения, выход блока вычисления пропускной способности соединен со входом "Параметр пропускной способности" блока принятия решения, информационный вход устройства соединен с информационными входами N блоков определения параметра дальнодействия и вторым входом четвертого элемента "И", i-й, где i=1, 2, 3...N, выход счетчика соединен с i-м входом демультиплексора и i-м входом N-входового элемента "И", i-й выход демультиплексора соединен с управляющим входом i-го блока определения параметра дальнодействия, выход N-входового элемента "И" соединен со входом "Изменение порога" блока определения удаляемого корреспондента, выход "Адрес" блока определения параметра дальнодействия соединен с i-м входом N-входового элемента "ИЛИ", выход которого соединен с групповым входом блока коммутации, выход "Параметр дальнодействия" i-го блока определения параметра дальнодействия соединен с i-м входом блока вычисления среднего параметра дальнодействия и i-м входом блока определения удаляемого корреспондента, выход которого соединен со входом блока коммутации, выход которого является адресным выходом устройства, выход блока вычисления среднего параметра дальнодействия соединен со вторым информационным входом блока вычисления пропускной способности и входом "Средний параметр дальнодействия" блока принятия решения, выход которого является сигнальным выходом устройства.

Наиболее близкими по своей технической сущности к заявляемому способу и устройству по прогнозированию трафика в системе связи являются способ и устройство для измерения трафика - см. изобретение "Способ и устройство для измерения трафика в системе связи", А.с. №955406, кл. Н 04 L 12/5, 08.11.96.

Рассмотренный в данной заявке А.с. №955406, кл. Н 04 L 12/5, 08.11.96 способ-прототип заключается в приеме последовательности единиц трафика, ее фильтрации прореживающими логическими схемами в соответствии с установленными параметрами прореживания, формировании разрешающего сигнала i-й схемой "И" для i+1 схемы "И, сравнении сигналов, поступающих с соседних схем "И" в элементах "ИСКЛЮЧАЮЩЕЕ ИЛИ", подсчете единичных импульсов, поступающих с выхода элементов "ИСКЛЮЧАЮЩЕЕ ИЛИ".

Однако способ прототип А.с. №955406, кл. Н 04 L 12/5, 08.11.96 имеют недостаток: низкая вероятность точного принятия решения по распределению сетевых ресурсов. Это объясняется тем, что трафик поступает из внешнего источника, поведение которого не может быть известно заранее, вследствие этого характеристики случайного процесса поступления единиц трафика могут быть функциями времени, поэтому решения по распределению сетевого ресурса могут носить запоздалый характер и не отражать текущего состояния.

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

Поставленная цель достигается тем, что в известном способе заявка А.с. №955406, кл. Н 04 L 12/5, 08.11.96, заключающемся в приеме последовательности единиц трафика, ее фильтрации прореживающими логическими схемами в соответствии с установленными параметрами прореживания, определении оценки распределения единиц трафика по частоте появления путем одновременных вычислений оценок частоты появления в нескольких диапазонах значений, дополнительно производится оценивание математического ожидания времени поступления единиц трафика путем одновременного вычитания значений единиц трафика соседних диапазонов с последующим умножением результатов на относительные частоты появления соответствующих распределений единиц трафика, параллельно производится с одновременным определением размера исходной выборки с дальнейшим умножением полученного значения на сумму оценок частоты появления числа единиц трафика, затем на основе полученного результата рассчитывается автокорреляционная функция случайного процесса, характеризующего время поступления единиц трафика, с последующим расчетом весовых коэффициентов фильтра авторегрессии, на основании которых осуществляется прогнозирование времени поступления к+1, 2...n единицы трафика.

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

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

Рассмотренное в данной заявке устройство (фиг.1), содержащее (i=1...N) прореживающих логических схем (G), (i=1...N) элементов "И", (i=1...N-1) элементов "Исключающее ИЛИ", (i=1...N-1) счетчиков, блок запуска, выход которого подключен к входам прореживающих логических схем (i=1, 2...N), выход "пропускание" первой прореживающей логической схемы подключен к первому и второму входам первого элемента "И", кроме того выход "пропускание" (i=2...N)-й прореживающей логической схемы подключен ко второму входу (i=2...N)-го элемента "И", выход каждого i-го элемента "И", за исключением N-го подключен к первым входам последующего элемента "И" соответственно, также выход каждого (i=1...N-1)-го элемента "И" соединены с первым входом (i=1...N-1)-го элемента "Исключающее ИЛИ" соответственно, кроме того выходы (i=2...N)-го элемента "И" подключены ко вторым входам (i=1...N-1)-го элемента "Исключающее ИЛИ" соответственно, выходы i-го элемента "Исключающее ИЛИ" являются входом i-го счетчика, вход блока запуска является информационным входом устройства, может быть использовано для измерения трафика в системе связи. Недостатком данного устройства является низкая точность принятия решения по управлению сетевым трафиком, связанная с тем, что параметры информационных потоков, учитываемые алгоритмами управления, оцениваются с запаздыванием, и они не соответствуют текущему состоянию трафика.

В заявленном устройстве поставленная цель достигается тем, что в известной системе, использующейся для измерения трафика заявка А.с. №955406, кл. Н 04 L 12/5, 08.11.96, содержащей (i=1...N) прореживающих логических схем (G), (i=1...N) элементов "И", (i=1...N-1) элементов "Исключающее ИЛИ", (i=1...N-1) счетчиков, блок запуска, выход которого подключен к входам прореживающих логических схем (i=1, 2...N), выход "пропускание" первой прореживающей логической схемы подключен к первому и второму входам первого элемента "И", кроме того выход "пропускание" (i=2...N)-й прореживающей логической схемы подключен ко второму входу (i=2...N)-го элемента "И", выход каждого i-го элемента "И", за исключением N-го подключен к первым входам последующего элемента "И" соответственно, также выходы каждого (i=1...N-1)-го элемента "И" соединены с первым входом (i=1...N-1)-го элемента "Исключающее ИЛИ" соответственно, кроме того выходы (i=2...N)-го элемента "И" подключены ко вторым входам (i=1...N-1)-го элемента "Исключающее ИЛИ" соответственно, выходы i-го элемента "Исключающее ИЛИ" являются входом i-го счетчика, вход блока запуска является информационным входом устройства, дополнительно введены блоки разности В (i=1...N-1), умножители Х (i=1...N-1), счетчик D, делитель К, сумматор S, умножитель Т, блок расчета автокорреляционной функции, блок расчета параметров авторегрессии, блок фильтра авторегрессии, выход блока запуска подключен к входу счетчика D, выход которого подключен к входу делителя К, выход которого соединен со вторым входом умножителя Т, второй выход каждой i-й прореживающей логической схемы кроме N-й подключен к первым входам (i=1...N-1) элементов блоков разности В соответственно, вторые выходы (i=2...N)-й прореживающей логической схемы подключены ко вторым входам (i=1...N-1)-го блоков разности В соответственно, выходы блоков разности В соединены с первыми входами умножителей X, на второй вход которых подключены выходы счетчиков (i=1...N-1), выходы умножителей Х (i=1...N-1) соединены с входами (i=1...N-1) сумматора S, выход которого соединен с первым входом умножителя Т, выход которого подключен на первый вход блока расчета автокорреляционной функции, второй вход которого подключен к информационному входу, выход блока расчета автокорреляционной функции соединен с блоком расчета параметров авторегрессии, выход "р" блока расчета параметров авторегрессии соединен с управляющим входом блока фильтра авторегрессии, вход блока фильтра авторегрессии объединен со вторым входом блока расчета автокорреляции, выход блока фильтра авторегрессии является информационным выходом данного устройства (фиг.2).

Блок расчета автокорреляционной функции 1 производит вычисление по формуле:

где x_t - значение времени прихода текущей единицы трафика;

x_t-k - значение времени прихода единицы трафика, сдвинутой на k интервалов назад;

- математическое ожидание времени прихода единиц трафика.

Блок расчета параметров авторегрессии 2 предназначен для расчета весовых коэффициентов фильтра авторегрессии по формулам:

или

Здесь r₁...r_p-1 - коэффициенты нормированной автокорреляционной функции.

Решение системы линейных уравнений позволяет вычислить коэффициенты авторегрессии: ϕ₁...ϕ_р.

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

Здесь:

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

ϕ₁; ϕ₂; ϕ_p - значения весовых коэффициентов фильтра авторегрессии порядка р;

х_t-p - значения времени прихода единицы трафика, сдвинутой на р интервалов назад.

Благодаря новой совокупности существенных признаков, за счет введения новых элементов и связей между ними, повышается точность принятия решения по управлению сетевым трафиком. Новые элементы позволяют определять автокорреляционную функцию и на ее основе рассчитать параметры авторегрессии фильтра порядка р. Результаты расчета являются весовыми коэффициентами фильтра авторегрессии и формируют его импульсную характеристику. Это дает возможность использовать фильтр авторегрессии при прогнозировании значений x_t на один и более отсчетов. Прогноз осуществляется следующим образом: пусть на фильтр авторегрессии, блок 3 Фиг.2 поступает значение времени прихода единицы трафика х_i. Переменная х_i проходит линии задержки и умножается на коэффициенты авторегрессии ϕ₁, ϕ_р, где р=2, значения которых поступили с блока расчета параметров авторегрессии (блок 2). Результаты произведения суммируются, и конечное значение x_i+1 поступает на выход блока 3. Переменная x_i+1 представляет собой прогноз времени поступления k=1, 2,...n единиц трафика, что и определяет признак пункта формулы "прогнозирование времени поступления k=1, 2,...n единиц трафика". Прогноз времени прихода очередной и последующих единиц трафика позволяет обеспечить принятие своевременных решений по перераспределению сетевого ресурса в соответствии с новыми условиями трафика в системе связи.

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

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

Заявленные объекты изобретения поясняются чертежами, на которых показаны:

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

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

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

на фиг.4 - блок-схема прореживающей логической схемы;

на фиг.5 - схема последовательности операций получения прогноза времени поступления единиц трафика.

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

Известно, что в современных протоколах передачи данных, таких например как АТМ, с каждым пользователем оговариваются параметры качества обслуживания, определяется гарантированная скорость передачи, гарантированный объем передаваемых данных. Однако заранее сложно осуществить точное описание трафика, и, как правило, пользователь резервирует более высокую полосу пропускания, что приводит к нерациональному использованию ресурса. Неточное описание трафика, данное пользователем, можно компенсировать реальным измерением трафика. В ходе измерения определяются параметры сетевого трафика и становится возможным перераспределение сетевого ресурса, что улучшает степень его использования. При этом цикл управления, связанный с принятием решения по перераспределению ресурса, должен быть значительно меньше времени протекания переходных процессов в системе, а для конкретного случая меньше периодов локальной стационарности поступающего на вход системы связи трафика. В то же время современные системы связи являются высокоскоростными. Так например, сеть связи, построенная по технологии АТМ, имеет минимальную скорость передачи 155 Мбит/с. Этот факт ужесточает требования по оперативности управления. Снижение цикла управления возможно на основе получения прогнозной оценки параметров трафика, например, на основе прогнозирования времени поступления к+1, к+2, к+n единиц трафика. При увеличении шага прогнозирования, возрастает дисперсия ошибки прогнозирования.

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

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

Процесс получения математической модели включает в себя следующие этапы. Расчет математического ожидания времени прихода единиц трафика. Для расчета данного параметра, после введения новых элементов и связей между ними, может быть использовано устройство для измерения трафика А.с. №955406, кл. H 04 L 12/5, 08.11.96, известное из предшествующего уровня техники. Прореживающие логические схемы и счетчики, лежащие в основе данного устройства, позволяют сформировать вариационный ряд. В простейшем случае вариационный ряд может быть представлен таблицей, первый столбец которой содержит всевозможные значения (варианты) x_i генеральной совокупности, а во втором - числа n_i, т.е. частоты появления i-го значения. Описание такого ряда, например, приведено в источнике [1]. Пример вариационного ряда представлен в таблице.

xi	ni	ni/n
5	4	0,4
10	5	0,5
15	1	0,1
∑	10	1,0

Отношение n_i/n является относительной частотой и отражает вес того или иного значения в выборке. Сумма относительных частот равна единице.

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

где

n - объем выборки;

m - количество вариантов.

Использование прореживающих логических схем позволяет сформировать варианты, которые будут определяться параметрами прореживания U₁...U_m, установленных для каждой логической схемы. Соответствующие частоты n_i могут быть получены на выходе счетчиков. Для сглаживания всплесков трафика и более точной оценки математического ожидания используется усреднение, заключающееся в том, что берутся не абсолютные значения, а разность между значениями "пропустить", принятыми соседними прореживающими логическим схемами. Таким образом, для расчета математического ожидания может быть использовано "Устройство для измерения трафика в системе связи", известное из предыдущего уровня техники при условии введения новых связей, а именно использование вторых выходов каждой i-й прореживающей логической схемы для считывания значений параметров прореживания U₁...U_m, которые являются вариантами x_i, определяемых настройкой каждой прореживающей логической схемы. Кроме того, для расчета математического ожидания необходимо введение ряда дополнительных элементов блоков разности В (i=1...N-1), умножителей Х (i=1...N-1), счетчика D, делителя К, сумматора S, умножителя Т.

Следующий этап расчета автокорреляционной функции. Автокорреляционная функция для процесса x(t), представленного в дискретном виде, как ряд значений х_t, называется неслучайная функция от двух аргументов: x_t, x_t-k, где x_t-k - значение ряда с отставанием в k отсчетов.

В статистике имеется несколько формул для оценки автокорреляционной функции для выборки объемом n отсчетов, где х - среднее для n отсчетов, полученное из выражения 4:

где: x'_t-k==х_t+n-k для k>n.

В силу специфики решаемых задач для расчета автокорреляционной функции использовано выражение 6. Для дальнейших расчетов необходимо провести нормировку автокорреляционной функции по формуле:

Авторегрессионые параметры и автокорреляционная последовательность связаны системой линейных уравнений (2). Таким образом, если задана автокорреляционная последовательность, то параметры авторегрессии можно найти, как решение системы линейных уравнений, которые называются уравнениями Юла-Уолкера. Алгоритм и подпрограмма решения уравнений, например, приведены в источнике [2]. Количество требуемых для решения системы линейных уравнений вычислительных операций пропорционально величине р², поэтому на данном этапе необходимо определить, какое количество параметров авторегрессии должно присутствовать в эффективной и экономичной модели процесса. На практике, как правило, используют модель второго порядка, что позволяет получить приемлемое соотношение между точностью расчета и вычислительными затратами. Вследствие этого система уравнений (2) будет иметь вид:

После того как на интервале наблюдения определены значения параметров модели авторегрессии, становится возможным получение прогнозной оценки времени прихода к+1,2...n единицы трафика. Для получения прогноза используется фильтр авторегрессии второго порядка, так как р=2. Физически эту модель реализует рекурсивный цифровой фильтр порядка p, именуемый БИХ фильтром, т.е. фильтром с бесконечной импульсной характеристикой. Описание такого фильтра, например, приведено в источнике [3]. Для получения прогнозной оценки времени прихода очередной единицы трафика может использоваться БИХ фильтр, описываемый следующим выражением.

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

Заявленное устройство для прогнозирования трафика в системе связи работает следующим образом.

Для получения прогнозной оценки времени прихода единиц трафика необходим некоторый интервал времени для набора статистических данных и обучения системы. Интервал времени, в течение которого производится настройка системы, зависит от скорости трафика и должен быть достаточно большим по отношению к самому медленному трафику из возможных. Для качественной настройки авторегрессионой модели необходимо, чтобы интервал наблюдения включал сто и более отсчетов времени прихода единиц трафика. В исходном состоянии после включения питания единицы входящего трафика (например, поток элементов данных системы АТМ) направляются помимо входной линии ВЛ1, также в тракт прогнозирования, который параллелен входной линии. В тракте прогнозирования поток трафика может сначала быть подан на блок запуска, который вырабатывает по одному импульсу на каждую входящую единицу трафика. Полученную таким образом последовательность импульсов, представляющую собой результат измерения трафика, подают на входы всех прореживающих логических схем. Каждая прореживающая схема настроена на свою частоту пропускания U. Следовательно, при помощи каждой из прореживающих схем можно оценить частоту появления i-го значения времени прихода единиц трафика. Таким образом, матрица прореживающих логических схем формирует вариационный ряд, значения которого определяются настройкой частот пропускания U₁...U_n отдельных прореживающих логических схем. В случае, когда величина входящего трафика в единицу времени превышает значение U, прореживающая логическая схема направляет некоторые из единиц трафика на выход таким образом, чтобы скорость передачи выходящего трафика из порта "ПРОПУСКАНИЕ" была не выше, чем U. Дальнейшая обработка единиц трафика, полученных на выходе "ПРЕРЫВАНИЕ", может быть осуществлена различными способами, но это выходит за объем настоящей заявки на изобретение. Работа отдельной прореживающей логической схемы в предлагаемой матрице прореживающих логических схем может быть осуществлена на основе принципа "протекающего ведра", известного из предшествующего уровня техники. Принцип "протекающего ведра" раскрыт, например, в работе: (Raif О. Onvural: Asynchronous Transfer Mode Networks, Performance Issues, Arctech House Inc. 1994 (ISBN 0-89006-662-0), Chapter 4.5.1. Принцип "протекающего ведра" используется, например, в алгоритме GCRA (Универсальный алгоритм для скорости передачи элементов данных) функции UPC (управление параметром использования) сети АТМ. На фиг.3 в виде блок-схемы показана работа прореживающей логической схемы, основанной на принципе маркерного банка (Token Bank). Прореживающая логическая схема хранит в своей памяти следующие параметры:

- время t₂, соответствующее последней единице трафика (которое первоначально равно текущему времени t₁);

- граничное значение U для логической схемы (фиксированная величина);

- размер банка В (фиксированная величина);

- b - значение счетчика банка, представляющее собой число маркеров в банке в любой момент времени.

Первоначально b=0, но число "маркеров" возрастает со стандартной скоростью, соответствующей граничному значению U. После получения новой единицы трафика (этап 1) прореживающая логическая схема запоминает значение текущего времени в переменной t₁ (этап 2). После этого прореживающая логическая схема вычисляет значение величины [U_x=(t₁-t₂)+b], сравнивает его со значением В и выбирает для переменной b меньшее из этих значений. Кроме того, прореживающая логическая схема обновляет значение переменной t₂ (этап 3). Затем прореживающая логическая схема анализирует, имеет ли переменная b значение, превышающее ноль (этап 4). Если это так, то переменной "пропускание" присваивают значение "истинно" (true) (Т), а значение счетчика банка уменьшают на единицу (этап 6). В случае если значение b счетчика не превышает ноль, переменной "пропускание" присваивают значение "ложно" (false) (F) (этап 5). Наконец, значение переменной "пропускание" вводится, а это означает, что прореживающая логическая схема принимает решение либо пропустить, либо прервать передачу (первое - если "пропускание"=Т, а последнее - если "пропускание"=F).

На фиг.4 показана блок-схема прореживающей логической схемы, которая может работать вышеописанным образом. Основу прореживающей логической схемы составляет блок принятия решения Пр, который включает в себя вход "ВХ" и вышеупомянутые выходы "ПРОПУСКАНИЕ" и "ПРЕРЫВАНИЕ". Прореживающая логическая схема дополнительно включает в себя память П1 для переменных (t₁, t₂ и b), а также память П2 для постоянных параметров. В памяти П2 сохраняют параметры U и В. Прореживающая логическая схема, помимо памяти, дополнительно включает в себя вычислительные средства Выч, часы Час и средство таймера Т, которые добавляют "маркеры" в банк. После поступления новой единицы трафика, блок принятия решения Пр управляет часами Час для запоминания текущего времени в памяти П1, после чего осуществляет управление вычислительными средствами Выч для вычисления значения переменной b и запоминания его в памяти П1. Затем производят операцию сравнения переменной b в блоке принятия решения. В зависимости от значения переменной b блоки принятия решения обновляют скорректированные переменные, как описано выше. Вслед за этим блок принятия решения, в зависимости от того, была ли пропущена единица трафика или нет, подает импульс либо на выход "ПРОПУСКАНИЕ", либо на выход "ПРЕРЫВАНИЕ".

Сигналы с выхода "ПРОПУСКАНИЕ" прореживающих логических схем параллельно поступают на входы элементов "И" фиг.2. Предполагается, что граничное значение [U₃] для логической схемы G₃ выше, чем граничное значение [U₂] для логической схемы G₂, которое выше граничного значения [U_l] для логической схемы G₁. Выход "ПРОПУСКАНИЕ" логической схемы с самым высоким граничным значением (то есть логическая схема самого высокого уровня) соединен с обоими входами первой логической схемы "И", а это фактически означает, что рассматриваемый выход непосредственно соединен с компаратором, то есть рассматриваемый результат принят как таковой. Выход "ПРОПУСКАНИЕ" логической схемы G₂ соединен с первым входом второй логической схемы "И", второй вход которой соединен с выходом логической схемы "И", соответствующей логической схеме (G₃) более высокого уровня. Аналогичным образом выход "ПРОПУСКАНИЕ" логической схемы G₁ соединен с первым входом третьей логической схемы "И", второй вход которой соединен с выходом логической схемы "И", соответствующей логической схеме (G₂) более высокого уровня. Выходы логических схем "И" более низкого порядка вырабатывают результат "пропустить" только в том случае, если выход логической схемы "И" более высокого уровня имеет результат "пропустить". Это предотвращает принятие решения "пропустить" логической схемы более низкого уровня, когда логическая схема более высокого уровня принимает решение "прервать". Сигналы с выхода логических схем "И" поступают параллельно на входы логических схем "ИСКЛЮЧАЮЩЕЕ ИЛИ" (соответственно). Логические схемы "ИСКЛЮЧАЮЩЕЕ ИЛИ" вырабатывают импульс на своих выходах только тогда, когда логические значения импульсов на их входах различны. Поскольку прореживающая логическая схема более высокого уровня имеет более высокое граничное значение U, логические значения сигналов на входах логической схемы "ИСКЛЮЧАЮЩЕЕ ИЛИ" 1, различны только в том случае, если логическая схема G₃ приняла решение "пропустить", а логическая схема G₂ приняла решение "прервать", и, соответственно, логические значения сигналов на входах логической схемы "ИСКЛЮЧАЮЩЕЕ ИЛИ" N-1 различны только в том случае, если логическая схема G₂ приняла решение "пропустить", а логическая схема G₁ приняла решение "прервать". Если счетчик 1 соединен с выходом логической схемы 1, то он будет давать результат, соответствующий количеству решений "пропустить", принятых прореживающей логической схемой G₃, минус количество решений "пропустить", принятых прореживающей логической схемой G₂. Соответственно, если счетчик N-1 соединен с выходом логической схемы N-1, то он будет давать результат, который соответствует количеству решений "пропустить", принятых прореживающей логической схемой G₂, минус количество решений "пропустить", принятых прореживающей логической схемой G₁. Таким образом, расчет производится согласно формуле: пропускание [i]- прерывание [i-1]. Преимуществом данного способа является то, что отдельная прореживающая логическая схема может при своей работе сглаживать всплески трафика, и, вследствие этого, она легко реализует усредняющий эффект, что позволяет более точно рассчитать математическое ожидание.

Одновременно при включении питания значения параметров прореживания U₁...U_n со вторых выходов прореживающих логических схем поступают на входы блоков разности В, как показано на фиг.2.

В блоке разности производится вычитание значений параметров прореживания (U_i; U_i+1) двух соседних прореживающих логических схем. Например, выходной сигнал блока вычитания B₁ равен: [U₃-U₂], а выходной сигнал блока разности B_N-1 равен: [U₂-U_N-1]. Необходимость вычитания значений параметров прореживания двух соседних логических схем обусловлена тем, что в схеме производится сглаживание всплесков трафика, и на выходе счетчиков частоты n_i определяются не абсолютными значениями, а принятыми соседними прореживающими логическими схемами разностями решений на пропускание. Сигналы с выходов блоков разности поступают на вторые входы умножителей, одновременно на первые входы которых поступают сигналы с выходов счетчиков. Сигналы с выходов счетчиков содержат частоты появления n_i того или иного варианта, который определяется разностью пропускания соседних прореживающих логических схем. В умножителях выполняются операции умножения, то есть производится вычисление: n (пропускание [i] - прерывание [i-1])·(G_i-G_i-1).

Сигналы с выхода умножителей подаются на вход сумматора S. В сумматоре производится сложение величин, полученных с выхода умножителей X(1...N-1). Полученный результат поступает на первый вход умножителя Т. Одновременно импульсы с выхода блока запуска поступают на счетчик D. В счетчике D производится подсчет числа единичных символов "1", общее количество которых n будет равно количеству пришедших единиц трафика на интервале наблюдения. После поступления каждого единичного импульса на интервале наблюдения, значение счетчика увеличивается на единицу. Сигнал с выхода счетчика D поступает на вход делителя К. В делителе выполняется операция деления на число n, то есть производится вычисление: 1/n. С выхода делителя К сигнал поступает на второй вход умножителя Т, в котором производится заключительный расчет математического ожидания времени прихода единиц трафика на интервале наблюдения (выражение 4). Здесь:

1/n - сигнал, поступивший с выхода делителя К;

- сигнал с выхода сумматора S.

Полученное значение математического ожидания с выхода умножителя Т поступает на вход 1 блока расчета автокорреляционной функции 1, где по формулам 6 и 8 производится ее расчет и нормировка.

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

Рассчитав значения весовых коэффициентов фильтра авторегрессии, по истечении интервала наблюдения осуществляется прогнозирование времени прихода очередной единицы трафика. При этом в качестве исходных данных для прогнозирования используется информация о времени прихода раннее поступивших единиц трафика. Необходимо отметить, что блок фильтра авторегрессии позволяет получить прогнозную оценку более чем на один шаг. В этом случае значения временного ряда на интервале (х_t...x_t+к), где x_t - последний принятый отсчет, x_t+к - прогнозируемый отсчет, к - шаг прогнозирования, заполняются нулями. В этом случае прогнозирование осуществляется как на основе прошлых значений, так и на основе нулевых значений временного ряда интервала (х_t...x_t+к). Это приводит к возрастанию дисперсии ошибки прогнозирования и повышению оперативности принятия решения. Последовательность операций получения прогнозной оценки времени поступления единиц трафика показана на фиг.5.

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

БИБЛИОГРАФИЧЕСКИЕ ДАННЫЕ

1. Я.К.Колде "Практикум по теории вероятностей и математической статистике" - М.: Высшая школа, 1991, с.157.

2. Марпл С.Л. Цифровой спектральный анализ и его приложения: Пер. с англ. - М.: Мир, 1990. - 584 с.

3. Густав Олссон, Джангуидо Пиани. Цифровые системы автоматизации и управления. - СПб.: Невский диалект, 2001. - 557 с.

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

2. Устройство для прогнозирования трафика в системе связи, содержащее (i=1...N) прореживающих логических схем (G), (i=1...N) элементов И, (i=1...N-1) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, (i=1...N-1) счетчиков, блок запуска, выход которого подключен к входам прореживающих схем (i=1,2...N), выход "пропускание" первой прореживающей логической схемы подключен к первому и второму входам первого элемента И, кроме того, выход "пропускание" (i=2...N)-й прореживающей логической схемы подключен ко второму входу (i=2...N)-го элемента И, выход каждого i-го элемента И, за исключением N-го, подключен к первым входам последующего элемента И соответственно, также выходы каждого (i=1...N-1)-го элемента И соединены с первым входом (i=1...N-1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соответственно, кроме того, выходы (i=2...N)-го элемента И подключены ко вторым входам (i=1...N-1)-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ соответственно, выходы i-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ являются входом i-го счетчика, вход блока запуска является информационным входом устройства, отличающийся тем, что дополнительно введены блоки разности В (i=1...N-1), умножители Х (i=1...N-1), счетчик D, делитель К, сумматор S, умножитель Т, блок расчета автокорреляционной функции, блок расчета параметров авторегрессии, блок фильтра авторегрессии, выход блока запуска подключен ко входу счетчика D, выход которого подключен к входу делителя К, выход которого соединен со вторым входом умножителя Т, второй выход каждой i-й прореживающей логической схемы, кроме N-й, подключен к первым входам (i=1...N-1) элементов блоков разности В соответственно, вторые выходы (i=2...N)-й прореживающей логической схемы подключены ко вторым входам (i=1...N-1)-го блоков разности В соответственно, выходы блоков разности В соединены с первыми входами умножителей X, на второй вход которых подключены выходы счетчиков (i=1...N-1), выходы умножителей Х (i=1...N-1) соединены с входами (i=1...N-1) сумматора S, выход которого соединен с первым входом умножителя Т, выход которого подключен на первый вход блока расчета автокорреляционной функции, второй вход которого подключен к информационному входу, выход блока расчета автокорреляционной функции соединен с блоком расчета параметров авторегрессии, выход "р" блока расчета параметров авторегрессии соединен с управляющим входом блока фильтра авторегрессии, вход блока фильтра авторегрессии объединен со вторым входом блока расчета автокорреляции, выход блока фильтра авторегрессии является информационным выходом данного устройства.