СПОСОБ И УСТРОЙСТВО ДЛЯ ИЗМЕРЕНИЯ ТРАФИКА В СИСТЕМЕ СВЯЗИ Российский патент 2001 года по МПК H04L12/56 

Изобретение относится к способу для измерения трафика в системе связи, включающему этапы, при которых информацию, соответствующую передаваемым единицам трафика, например элементам данных, направляют на ряд параллельных логических схем (G₁, ..., G_n) прореживания трафика, которые принимают решение: прервать передачу или пропустить отдельные единицы трафика, и производят оценку распределения единиц трафика по частоте появления путем одновременного вычисления оценок относительной частоты появления в различных диапазонах значений. Предлагаемый способ предназначен, в частности, для измерения трафика элементов данных в сети с асинхронным режимом передачи (АТМ), но он также применим и для других видов трафика, например, для вызовов, что будет раскрыто ниже. Из-за наличия большого количества операционных сред: элементов данных, пакетов, вызовов и т.д., передаваемые в системе объекты будут именоваться ниже общим термином "единица трафика".

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

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

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

На фиг. 1 показана гистограмма, на которой высота (0,1) первой полосы представляет собой оценку того, что последующее значение случайной переменной будет находится между 0 и пятью, высота (0,2) следующей полосы представляет собой оценку того, что последующее значение случайной переменной будет находиться между пятью и десятью, и т.д. Вычисляя сумму высот до той полосы, координата x которой превышает X, можно получить оценку функции распределения вероятности F переменной r в точке r = X. Например, сумма двух крайних левых полос (0,1 + 0,2 = 0,3) является оценкой того, что последующее значение случайной переменной будет меньше или равно десяти.

Для дискретной случайной величины функцию плотности вероятности f и функцию распределения вероятности F определяют следующим образом:
f(X)= P {любое r_i- X}, i= 0, 1, 2, ...

F(X)= P {любое r_i≤ X} = ∑ f(R_i).
Если функции f и F известны, то о поведении случайной величины известно почти все, что нужно. Тем не менее, на практике это не представляется возможным, потому что в подобном случае потребовалось бы знать не только предыдущие значения последовательности случайной переменной, но также и ее будущие значения. Однако это невозможно, так как трафик исходит из внешнего источника, который не зависит от устройства измерения и поведение которого не может быть известно заранее. Кроме того, функции f и F могут быть функциями времени (то есть они могут изменяться во времени).

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

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

На фиг. 2 показано типичное решение, которое может быть использовано для измерения оценочного значения h функции плотности вероятности f. Результаты измерений трафика или соответствующие данные (например, последовательность импульсов, в которой каждый импульс соответствует единице входящего трафика) подают на устройство сортировки УС, которое вычисляет мгновенную частоту прихода r. Ее получают путем вычисления величины, обратной разности между моментом времени t₁ (то есть, текущим временем) поступающей единицы трафика и моментом времени t₂ предыдущей единицы трафика, то есть r = 1/(t₁-t₂). Эту величину вычисляют при поступлении каждой единицы трафика. (Если при вычислении используют не обратную величину, а саму разность t₁-t₂, то вместо распределения частоты прихода получают оценку распределения времени между последовательными единицами трафика). В действительности вычисление выполняют посредством счетчиков C₁, ..., С_n, по одному на каждую полосу гистограммы, то есть по одному на каждый частотный диапазон. Например, чтобы оценить информацию, представленную на фиг. 1, требуется восемь счетчиков (первый между нулем и пятью, второй между пятью и десятью и т.д., а последний счетчик: между тридцатью пятью и бесконечностью). Выяснив мгновенное значение частоты прихода, устройство сортировки УС должно выработать решение, к какому диапазону полос гистограммы по оси X относится результат. Для этой цели, оно имеет хранимую в памяти (обозначенной ссылочной позицией ПАМ) информацию, согласно которой каждый счетчик C₁, ..., C_n соответствует своему диапазону по оси X. Таким образом, устройство сортировки сравнивает вычисленный результат с хранимыми в памяти данными и после этого увеличивает на единицу показания счетчика, соответствующего тому частному диапазону, к которому относится результат. Таким образом результаты вычислений счетчиков дают оценку h функции плотности вероятности. В начале измерения счетчики обнуляют. После проведения измерения значения счетчика сохраняют, а счетчики обнуляют, после чего может быть произведено следующее измерение.

Описанный выше способ будет обеспечивать мгновенную картину или мгновенное распределение трафика. Однако малые мгновенные флуктуации обычно не представляют никакого интереса, а вместо этого желательно было бы оценить состояние трафика в течение длительного времени, потому что такая оценка даст более точную информацию о состоянии трафика. Это выполняется путем усреднения результатов измерений каким-либо способом для сглаживания любых мгновенных флуктуаций. Самый простой способ состоит в том, что перед устройством на фиг. 2 добавляют блок усреднения. Этот альтернативный вариант показан на фиг. 3a, на котором указанный блок обозначен ссылочной позицией БУ. Проблема, которая возникает при таком решении, состоит в том, как выбрать коэффициент усреднения; например, сколько единиц трафика следует учитывать, или какая длительность должна быть у временного окна. Вообще говоря, можно отметить, что правильный коэффициент усреднения зависит от того, каковы отклонения входящего трафика от текущего среднего значения, а это означает, что для поддержания непрерывного и эффективного усреднения лучше установить блок усреднения после блока оценки (как на фиг. 3б) или же подавать параметры трафика для блока усреднения через петлю обратной связи (как на фиг. 3в). В этом случае измеренные данные должны быть сохранены в блоке сортировки так, чтобы из них могли бы быть сформированы параметры обратной связи.

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

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

Этот результат достигается согласно настоящему изобретению тем, что в заявленном способе вычисление оценки для отдельного диапазона значений осуществляют на основании разностей между количеством решений, принятых прореживающими логическими схемами, соответственно рассматриваемому диапазону значений в течение определенного интервала времени. Изобретение также относится к устройству для измерения трафика в системе связи, причем устройство содержит ряд параллельных прореживающих логических схем (G₁,..., G_n), каждая из которых связана с информацией, соответствующей передаваемым единицам трафика, а каждая прореживающая логическая схема содержит средство принятия решения (ПР) для выработки решения о пропускании или прерывании передачи единицы трафика, например, элемента данных, причем решение о пропускании указывает на принятие единицы трафика как удовлетворяющей предварительно заданным критерием соответствия трафика, и средство часов (ЧАС) для определения времени появления каждой единицы трафика. Устройство для измерения трафика, соответствующее изобретению, отличается тем, что оно дополнительно содержит вычислительное средство для вычисления разностей между определенным количеством решений, принятых одиночными прореживающими логическими схемами за определенный период времени.

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

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

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

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

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

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

Так называемый способ прореживания вызовов (термин используется в нескольких международных стандартах, например, в Рекомендации Е.412, 3.1.1.2 и Рекомендации Q. 542, 5.4.4.3 Синей Книги МККТТ (CCITT Blue Book)) представляет собой способ управления трафиком на основании скорости передачи, который ограничивает величину трафика, то есть количество вызовов так, чтобы за единицу времени проходило определенное максимальное количество вызовов. Такой способ был описан не только в вышеупомянутых стандартах, но также, например, в Патенте США N 4224479.

Устройство, работающее в соответствии со способом прореживания вызовов, может представлять собой показанную на фиг. 4 прореживающую логическую схему 40, имеющую один вход, обозначенный позицией ВХОД, и два выхода, обозначенные ПРОПУСКАНИЕ и ПРЕРЫВАНИЕ, в логической схеме заранее запомнен параметр прореживания U, который представляет собой определенное количество единиц трафика за единицу времени (например, элементов данных или вызовов в секунду). Единицы входящего трафика направляют на вход прореживающей логической схемы ВХОД, а передачу пропущенных единиц трафика осуществляют с выхода ПРОПУСКАНИЕ. Прореживающая логическая схема ограничивает частоту (частоту появления) единиц трафика таким образом, чтобы величина переданного трафика за единицу времени не превысила вышеупомянутый параметр прореживания U (единиц трафика в секунду). В случае, когда величина входящего графика за единицу времени превышает значение U, прореживающая логическая схема направляет некоторые из единиц трафика на выход ПРОПУСКАНИЕ таким образом, чтобы скорость передачи выходящего трафика из порта ПРОПУСКАНИЕ была не выше, чем U. Дальнейшая обработка единиц трафика, полученных на выходе ПРЕРЫВАНИЕ, может быть осуществлена различными способами, но это выходит за объем настоящей заявки на изобретение. На практике прореживающая логическая схема может быть реализована, например, с использованием короткой программы, которая может считывать показания часов устройства и на основе этого принимать решения о прерывании передачи.

В вышеупомянутом Патенте США N 4224479 прореживающая логическая схема работает таким образом, чтобы между двумя последовательными вызовами имелся минимальный возможный промежуток времени, например 0,1 секунды. (Следовательно, хранимый в прореживающей логической схеме параметр прерывания, может также определять самый короткий допустимый промежуток времени I между двумя последовательными вызовами, упоминаемый как интервал прореживания, и который по существу является тем же самым параметром, так как рассматриваемые параметры прореживания представляют собой величины, обратные друг другу, то есть U = 1/I). Время начала последнего переданного вызова запоминается в прореживающей логической схеме. Если разность между временем поступления нового вызова и запомненного времени начала меньше, чем вышеупомянутый самый короткий из возможных промежуток времени, то вызов будет прерван. Если разность равна или больше вышеупомянутого промежутка времени, то вызов будет пропущен, а значение времени начала последнего переданного вызова будет обновлено так, чтобы оно соответствовало текущему времени.

Функционирование способа прореживания вызова иллюстрируется на фиг. 5. Когда величина усредненного входящего трафика (отмеченная по горизонтальной оси) ниже, чем вышеупомянутый максимум U, то не происходит никаких перерывов в передаче (в идеальном случае). Когда усредненная величина трафика превышает рассматриваемое значение, то прореживающая логическая схема осуществляет прерывание передачи некоторых вызовов (направляя их на выход ПРЕРЫВАНИЕ), при этом величина передаваемого трафика (отмеченная по вертикальной оси) равна U. Идеальный случай представлен пунктирной линией, а реальный случай - сплошной линией. Фактически, характеристическая кривая (сплошная линия), отображающая функционирование прореживающей логической схемы, представляет собой сглаженное приближение кусочно-линейной характеристической кривой (пунктирная линия) для идеального случая - чем ближе к идеальной кривой, тем прореживающая логическая схема лучше. Например, при помощи прореживающей логической схемы согласно Патенту США N 4224479 невозможно достичь идеального случая. С другой стороны, прореживающие логические схемы, основанные на принципе "протекающего ведра", известном из предшествующего уровня техники, являются эффективными, потому что они способны обрабатывать также мгновенные всплески трафика.

Согласно настоящему изобретению, измерение данных гистограммы трафика производят с использованием матрицы прореживающих логических схем ПЛС (фиг. 6), состоящей из множества параллельных прореживающих логических схем G₁, .. . , G_n. Входящий поток трафика (например, поток элементов, данных системы АТМ) помимо того, что его передают по входной линии ВЛ1, также направляют в измерительный тракт, который параллелен входной линии. В измерительном тракте поток трафика может сначала быть подан на блок 61 запуска, который вырабатывает по одному импульсу на каждую входящую единицу трафика. Полученную таким образом последовательность импульсов, представляющую собой результат измерения трафика, подают на входы всех прореживающих логических схем.

Если предположить, что: а) переменная описывает количество единиц трафика (например, элементов данных АТМ системы или вызовов), пропущенных прореживающей логической схемой за определенный промежуток времени d; и б) - логическая схема получила всего N единиц трафика в течение этого промежутка времени, причем доля единиц трафика, пропущенных логической схемой, равна Следовательно, эта величина представляет собой оценку вероятности того, что частота (частота прихода) r входящих единиц трафика будет меньше или равна U, то есть:

Следовательно, при помощи отдельной прореживающей логической схемы можно оценить (путем подсчета принятых прореживающей логической схемой решений "пропустить" и поступающих единиц трафика) значение функции H в точке r = U. Матрица прореживающих логических схем будет давать несколько значений для функции H, а затем эти значения могут быть использованы для вычисления оценок h. Вычисления осуществляют в устройстве по фиг. 6 в отдельном вычислительном блоке ВЫЧ, на который подают данные о принятых матрицей прореживающих логических схем решениях: пропустить или прервать передачу. Однако следует отметить, что, если r > U и если кривая отклика соответствует фиг. 5, то прореживающая логическая схема в любом случае пропустит (вместо нулевых единиц трафика) Ud единиц трафика. Исправление возникающей в результате этого ошибки осуществляют в компараторе КОМП, находящемся между матрицей прореживающих логических схем и вычислительным блоком. Более подробное описание работы такого компаратора приведено ниже.

Для примера предположим, что имеются две прореживающие логические схемы (для простоты примера), и они были приведены в действие на 100 секунд. Прореживающие логические схемы имеют различные граничные частоты u: 5 и 10 единиц трафика в секунду. Решения, принятые прореживающими логическими схемами, будут сохранены, однако они не будут оказывать никакого воздействия на трафик, и он будет направлен дальше во входную линию ВЛ1. Результаты будут следующими:
- общее количество вызовов - 700;
- первая логическая схема (U = 5): пропускание = 200, прерывание = 500;
- первая логическая схема (U = 10): пропускание = 600, прерывание = 100.

Из этих результатов могут быть сделаны следующие выводы. В течение периода наблюдения средняя скорость трафика равнялась 700/100 = 7 единиц трафика в секунду. 200 единиц трафика, то есть 28,5% от общего количества, поступали со скоростью меньшей, чем 5 (единиц трафика в секунду), а 100 единиц трафика (то есть 14,3% от общего количества) поступали со скоростью большей, чем 10 (единиц трафика в секунду). Разность (500-100=400) между прерываниями передачи, осуществленными первой и второй логическими схемами, соответствует количеству единиц трафика, которые находятся внутри диапазона (5,10) (единиц трафика в секунду).

Данные гистограммы, полученные в вышеописанном примере, показаны на фиг. 7а и 7б. На фиг. 7а показана оценка H функции распределения вероятности для плотности трафика, а на фиг. 7б показана оценка h функции плотности вероятности для плотности трафика. Оценка H имеет ступенчатый вид с подъемами величиной h(0) в точке x = 0, h(5) в точке x = 5, h(10) в точке x = 10. (Следовательно, величины оценок h могут быть рассчитаны по оценкам H).

При большем количестве прореживающих логических схем будет получена более подробная картина состояния трафика. Предположим, что используется n логических схем, граничные частоты которых обозначены U[1], U[2], ..., U[n]. (U[1] самая низкая, а [U[n] самая высокая частота). Эти n граничных значений определяют (n + 1) диапазонов; последний диапазон, то есть (n+1)-й расположен между (U[n], ∞). Общее число прерываний и пропусканий логической схемы, имеющей индекс i (i = 1,2, ..., n), обозначают как прерывание [i] и пропускание [i] , а счетчиком, подсчитывающим общее количество единиц трафика является, в известном смысле, дополнительная логическая схема с граничным значением U[n+1] = ∞, а это приводит к тому, что пропускание [n+1] = N и прерывание [n+1] = 0. Это означает, что количество единиц трафика, которые находятся в диапазоне (U[i-1], U[i]) равно:
пропускание [i-1] - прерывание [i] (1)
Количество единиц трафика в диапазоне (U[i-1], U(i)] также может быть вычислено из соотношения:
пропускание [i] - прерывание [i-1] (2)
Следует дополнительно учитывать, что когда плотность входящего трафика выше, чем граничное значение для прореживающей логической схемы, то, как отмечено выше, функционирующая в соответствии с фиг. 5 логическая схема пропустит Ud единиц трафика, то есть не все решения "пропустить" принимаются исходя из трафика, который имеет скорость ниже или равную граничному значению U для логической схемы. Эту ошибку расчета оценки исправляют компаратором КОМП, представленным на фиг. 6, который после каждой единицы трафика (или соответствующего ей импульса) анализирует выходы логических схем в порядке, соответствующем убыванию их граничного значения (то есть, начиная с логической схемы, имеющей самое высокое граничное значение U). Обнаружив первый результат прерывания передачи, компаратор заменяет результаты пропускания, которые имеют все остальные логические схемы, на результаты прерывания (так как они являются точно теми же результатами пропускания, которые, возможно, возникают в трафике, где выполняется условие r > U). Таким образом можно устранить большинство из этих результатов пропускания, которые являются "лишними" с точки зрения результата оценки.

Работа отдельной прореживающей логической схемы в предлагаемой матрице прореживающих логических схем может быть осуществлена на основе принципа "протекающего ведра", известного из предшествующего уровня техники. Этот принцип или его специфическая разновидность также упоминаются как маркерный банк (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 применяют для контроля того, соответствует ли трафик элементов данных согласованному трафику рассматриваемого соединения. В предлагаемом способе для этих элементов могут быть использованы решения, уже имеющиеся в сети.

На фиг. 8 в виде блок-схемы показана работа прореживающей логической схемы, основанной на принципе маркерного банка (Token Bank). Прореживающая логическая схема хранит в своей памяти следующие параметры:
- время t₂, соответствующее последней единице трафика (которое первоначально равно текущему времени t₁),
- граничное значение U для логической схемы (фиксированная величина),
- размер банка В (фиксированная величина), и
- значение счетчика банка b, представляющее собой число маркеров в банке в любой момент времени. Первоначально b = 0, но число "маркеров" возрастает со стандартной скоростью, соответствующей граничному значению U.

После получения новой единицы трафика (этап 81) прореживающая логическая схема запоминает значение текущего времени в переменной t₁ (этап 82). После этого прореживающая логическая схема вычисляет значение величины [U_x(t₁- t₂)+ b] , сравнивает его со значением B и выбирает для переменной b меньшее из этих значений. Кроме того, прореживающая логическая схема обновляет значение переменной t₂ (этап 83). Затем прореживающая логическая схема анализирует, имеет ли переменная b значение, превышающее ноль (этап 84). Если это так, то переменной "пропускание" присваивают значение "истинно" (true) (Т), а значение счетчика банка увеличивают на единицу (этап 85а). В случае, если значение b счетчика не превышает ноль, переменной "пропускание" присваивают значение "ложно" (false) (F) (этап 85б). Наконец, значение переменной "пропускание" вводится, а это означает, что прореживающая логическая схема принимает решение либо пропустить, либо прервать передачу (первое - если "пропускание" = T, а последнее - если "пропускание" = F).

Компаратор КОМП и вычислительный блок ВЫЧ могут быть реализованы, например, как показано на фиг. 9, на которой изображен вариант реализации с использованием трех параллельных прореживающих логических схем. Входы компаратора отмечены BX1, ..., BX3. Вход BX3 соединен с выходом ПРОПУСКАНИЕ логической схемы G₃, вход BX2 - с выходом ПРОПУСКАНИЕ логической схемы G₂, а вход BX1 - с выходом ПРОПУСКАНИЕ логической схемы G₁. В примере далее предполагается, что граничное значение [U3] для логической схемы G₃ выше, чем граничное значение [U2] для логической схемы G₂, которое выше граничного значения [Ul] для логической схемы G₁. Выход ПРОПУСКАНИЕ логической схемы с самым высоким граничным значением (то есть логическая схема самого высокого уровня) соединен с обоими входами первой логической схемы И 90, а это фактически означает, что рассматриваемый выход непосредственно соединен с компаратором, то есть рассматриваемый результат принят как таковой. Выход ПРОПУСКАНИЕ логической схемы G₂ соединен с первым входом второй логической схемы И 91, второй вход которой соединен с выходом логической схемы И, соответствующей логической схеме (G₃) более высокого уровня. Аналогичным образом выход ПРОПУСКАНИЕ логической схемы G₁ соединен с первым входом третьей логической схемы И 92, второй вход которой соединен с выходом логической схемы И, соответствующей логической схеме (G₂) более высокого уровня. Выходы логических схем И 91 и 92 вырабатывают результат "пропустить" только в том случае, если выход логической схемы И более высокого уровня имеет результат "пропустить". Это предотвращает принятие решения "пропустить" логической схемы более низкого уровня, когда логическая схема более высокого уровня принимает решение "прервать". Оценку значения функции распределения вероятности H получают путем подсчета выходных импульсов логических схем И 90, . .., 92.

Оценка значения функции плотности вероятности h может быть получена путем добавления после узла компаратора КОМП, например, схемы счетчика ВЫЧ, реализованной, например, согласно фиг. 9. В этом случае выходы логических схем И 90 и 91 соединяют с входами первой логической схемы ИСКЛЮЧАЮЩЕЕ ИЛИ 93 (соответственно), а выходы логических схем И 91 и 92 соединяют с входами второй логической схемы ИСКЛЮЧАЮЩЕЕ ИЛИ 94 (соответственно). Логические схемы ИСКЛЮЧАЮЩЕЕ ИЛИ вырабатывают импульс на своих выходах только тогда, когда логические значения импульсов на их входах различны. Поскольку прореживающая логическая схема более высокого уровня имеет более высокое граничное значение U, логические значения сигналов на входах логической схемы 93 различны только в том случае, если логическая схема G₃ приняла решение "пропустить", а логическая схема G₂ приняла решение "прервать", и, соответственно, логические значения сигналов на входах логической схемы 94 различны только в том случае, если логическая схема G₂ приняла решение "пропустить", а логическая схема G₁ приняла решение "прервать". Если счетчик 95a соединен с выходом логической схемы 93, то он будет давать результат, соответствующий количеству решений "пропустить", принятых прореживающей логической схемой G₃, минус количество решений "пропустить", принятых прореживающей логической схемой G₂. Соответственно, если счетчик 95б соединен с выходом логической схемы 94, то он будет давать результат, который соответствует количеству решений "пропустить", принятых прореживающей логической схемой G₂, минус количество решений "пропустить", принятых прореживающей логической схемой G₁. Таким образом, расчет производится согласно формуле (2), описанной выше.

Вариант осуществления на фиг. 9 может быть модифицирован так, чтобы его функционирование осуществлялось на основании решений "прервать". Такой вариант осуществления показан на фиг. 10, который соответствует варианту осуществления фиг. 9 за исключением того, что теперь выходы ПРЕРЫВАНИЕ прореживающих логических схем соединены с входами компаратора (выходы ПРЕРЫВАНИЕ дают информацию о принятых решениях "прервать"), а вместо логических схем И используются логические схемы ИЛИ 101 и 102. В этом случае первый счетчик 105a дает результат, который соответствует количеству решений "прервать", принятых прореживающей логической схемой G₂, минус количество решений "прервать", принятых прореживающей логической схемой G₃. Соответственно, второй счетчик 105б дает результат, который соответствует количеству решений "прервать", принятых прореживающей логической схемой G₁, минус количество решений "прервать", принятых прореживающей логической схемой G₂. Таким образом, расчет производится согласно формуле (1), описанной выше.

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

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

После поступления новой единицы трафика (этап 111) прореживающая логическая схема запоминает текущее время в переменной t₁ (этап 112). После этого прореживающая логическая схема вычисляет значение величины [Ux(t₁-t₂)+b], сравнивает его со значением В и выбирает для переменной b меньшее из этих значений. Кроме того, прореживающая логическая схема обновляет значение переменной t₂ (этап 113). Затем прореживающая логическая схема анализирует, имеет ли переменная b значение, превышающее ноль (этап 114). Если это так, то переменной "пропускание" присваивают значение "истинно" (Т), а значение счетчика банка уменьшают на единицу (этап 115a). В случае, если значение b счетчика не превышает ноль, переменной "пропускание" присваивают значение "ложно" (F) (этап 115b). После этого анализируют, превышает ли значение b счетчика вышеупомянутое предварительно определенное значение - D (этап 116). Если это так, то на следующем этапе для счетчика будут производить выбор наибольшего из значений - D и b-1 (этап 117). Затем на этапе 118 вводят значение переменной, "пропускание". Если на этапе 116 обнаружено, что значение счетчика не превышает - D (то есть счетчик уже достиг своего минимального значения), процедура обработки непосредственно переходит на этап 118, на который можно также перейти непосредственно с этапа 115a, когда на нем переменная "пропускание" получила значение "истинно" (T).

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

Работа модифицированной для работы в низкочастотном режиме прореживающей логической схемы показана на фиг. 11б. Если средняя величина представленного трафика превышает рассматриваемое значение, прореживающая логическая схема в идеальном случае будет осуществлять прерывание передачи всех единиц трафика (направляя их на выход ПРЕРЫВАНИЕ). Идеальный случай отображен прерывистой кривой, а реальный случай - сплошной линией. На практике характеристическая кривая (сплошная линия), отображающая функционирование прореживающей логической схемы, представляет собой приближение кусочно-линейной характеристической кривой (прерывистая линия) для идеального случая. Форма характеристической кривой прореживающей логической схемы также зависит от того, насколько велико предварительно определенное значение постоянной D.

Принцип "протекающего ведра" или маркерного банка (Token Bank) может быть проиллюстрирован различными способами, зависящими от того, какие переменные анализируют и какая точка зрения выбрана для анализа. Например, не обязательно использовать маркеры, а используемым ресурсом может быть время. В результате, работу в низкочастотном режиме можно реализовать в других механизмах управления, действующих по аналогичному принципу. Однако в рамках настоящего изобретения эти различные изменения незначительны, и поэтому в качестве ссылки может быть использована находящаяся в стадии одновременного рассмотрения заявка на Патент Финляндии N 955407, которая относится к рассматриваемой прореживающей логической схеме и соответствующая заявка РСТ на "Управление трафиком в системе связи" от 8 ноября 1996 г., поданная от имени фирмы Nokia Telecommunications.

Поскольку при функционировании устройства описанной выше модифицированной прореживающей логической схемы уже учитывается ошибка вычисления оценки, исправление которой в вышеупомянутом варианте осуществления производит компаратор КОМП (см. фиг. 6), наличие компаратора после матрицы прореживающих логических схем не является обязательным, если отдельные прореживающие логические схемы функционируют в соответствии с фиг. 11a. В этом случае устройство является таким, как показано на фиг. 11с : оно соответствует варианту осуществления на фиг. 6 за исключением того, что узел компаратора может отсутствовать (выходы прореживающих логических схем соединены непосредственно с входами вычислительного блока). (Однако следует отметить, что компаратор мог бы оказаться полезным даже в варианте осуществления с использованием модифицированных прореживающих логических схем).

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

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

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

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

Предлагаемый способ может быть также использован для отыскания распределения таких промежутков времени, в которых скорость трафика r находится в пределах длительности однократного измерения. Для этого необходимо модифицировать функционирование прореживающих логических схем так, как показано на фиг. 13 и 14. На фиг. 13 показаны те видоизменения, которые нужно осуществить с прореживающей логической схемой, соответствующей фиг. 8, а на фиг. 14 - видоизменения логической схемы по фиг. 11a. В модифицированных прореживающих логических схемах производят измерения разности между временем поступления пропущенной единицы трафика и временем поступления предшествующей единицы трафика, причем эта разность упоминается как термин "время между поступлениями" и обозначена как ВМП на фиг. 13 и 14. Измерение выполняют на этапе 83 (фиг. 13) или 113 (фиг. 14). Если единица трафика не пропущена, ВМП обнуляют на этапе 85б (фиг. 13) или 115б (фиг. 14). На этапе 86 (фиг. 13) и 118 (фиг. 14) логическая схема осуществляет ввод значения ВМП. Стоящий после логической схемы счетчик суммирует времена между поступлениями (значения ВМП, полученные на этапах 86 и 118) единиц трафика, которые пропущены каждой прореживающей логической схемой в течение интервала времени измерений d.

Обозначение а[1] используют для суммы времен между поступлениями (1≤ i ≤n+1 и a[n-1]=d), которые пропущены в течение интервала времени измерения d прореживающей логической схемой, имеющей граничное значение U[1], а обозначения T[1] используют для времени, в течение которого скорость передачи источника трафика находится в диапазоне (U[i-1], U[1]). Таким образом, T[i] = [i] - [i-1], то есть конечный результат получают как разность между суммами, измеренными двумя соседними логическими схемами.

Приближенные значения Т[i] могут также быть получены путем их расчета по гистограмме. Предположим, что величины в вышеупомянутой формуле (2) в течение периода времени измерения d достигают значения c[i]. Тогда T[i] = c[i] /r[i] , где значения r[i] находятся в диапазоне (U[i-1], U[i]). Гистограмма не дает значения для r[i], но оно может быть аппроксимировано различными способами. Аппроксимация может быть выполнена, например, при предположении, что r[i] равно наибольшему значению U[i] из диапазона. Это приводит к тому, что T[i] ≈ c[i]/U[i], где 1 ≤ i ≤ n. Следовательно, время Т[n+1], затраченное на последний диапазон, может быть получено из:
T[n+1] = d - [T[1] + T[2] +T[3], ... T[n]].

Другой способ аппроксимации r[i] состоит в том, чтобы определить его как среднее значение диапазона. Соответственно, T[-i] ≈ 2c[i] / (U[i-l]+ U[i]), где 1 ≤ i ≤ n. Понятно, что чем шире диапазон, тем хуже аппроксимация. Путем непосредственных измерений значений T[i], как описано выше, будет получено точное оценочное значение вне зависимости от ширины диапазонов.

На основании вышеописанного очевидно также, что путем измерений как распределения h (гистограмма), так и распределения интервалов времени, может быть вычислено r[i], то есть, скорость, с которой поступило большинство единиц трафика в диапазоне (U[i-l], U[i]) в течение периода измерений d. Для скорости же выполняется равенство:
r[i] = c[i] / T[i] (3)
Если в i-том диапазоне трафик отсутствует, то есть, если с[i] и T[i] равны нулю, то r[i] может быть присвоено значение из центра диапазона:
r[i] = (U[i-1] + U[i])/2 (4)
(Это правило также применимо при c[i] > 0, если c[i] очень мало по сравнению с общим количеством N единиц трафика, например, если c[i]/N < 10^-3).

Как видно из фиг. 11б, чем ближе r к значению U, тем дальше от идеального случая отстоят характеристики фильтра. Следовательно выполненные логической схемой измерения наименее точны тогда, когда r[i] имеет значение, близкое к U[i]. Таким образом, если для каждого периода измерений распределение по оси скоростей может быть изменено, то в преимущественном варианте границы диапазонов U[i] следует установить такими, чтобы измеренные ранее значения r[i] как можно дальше отстояли от граничных значений U[i]. Следовательно, граничные значения диапазонов могут быть изменены путем выбора новых значений U[i] в конце каждого периода измерений следующим образом: U[i] = (r[i-1] + r[i])/2, где i = 1, 2, ..., n, а значения r[i] получены из уравнений (3) и (4) по измеренным данным c[i] гистограммы.

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

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

Изобретение относится к способу и устройству для измерения трафика в системе связи. Технический результат - повышение скорости передачи информации и точности измерения трафика. Информацию, соответствующую передаваемым единицам трафика, например элементам данных, направляют на ряд параллельных логических схем (G₁..., G_n) для прореживания трафика, которые принимают решение "прервать передачу" или "пропустить" отдельные единицы трафика и определяют оценку распределения единиц трафика по частоте появления путем одновременных вычислений оценок частоты появления в нескольких диапазонах значений. Для упрощения процедуры получения точности вида трафика определение оценки для отдельного диапазона значений осуществляют по разности между количеством решений, принятых соответствующими рассматриваемому диапазону значений прореживающими логическими схемами за определенный период времени. 2 с. и 12 з.п.ф-лы, 14 ил.

1. Способ измерения трафика в системе связи, при котором информацию, соответствующую передаваемым единицам трафика, в качестве которых используются элементы данных, пакеты, вызовы, направляют на ряд параллельных прореживающих логических схем (G₁, ..., G_n) для прореживания единиц трафика, причем прореживающие логические схемы принимают решение о прерывании передачи или пропускании отдельных единиц трафика, и определяют оценку распределения единиц трафика по частоте появления единиц трафика путем одновременного вычисления оценок относительной частоты появления единиц трафика в нескольких диапазонах значений, отличающийся тем, что оценку отдельного диапазона значений частоты появления единиц трафика определяют на основании разностей между количеством решений, принятых соответствующими рассматриваемому диапазону значений частоты появления единиц трафика прореживающими логическими схемами в течение конкретного интервала времени. 2. Способ по п.1, отличающийся тем, что определение осуществляют только на основании принятых прореживающими логическими схемами решений "пропустить". 3. Способ по п.1, отличающийся тем, что определение осуществляют только на основании принятых прореживающими логическими схемами решений "прервать передачу". 4. Способ по п.1, отличающийся тем, что в качестве указанного интервала времени используют предварительно определенный отрезок времени. 5. Способ по п.1, отличающийся тем, что в качестве указанного интервала времени используют предварительно определенное количество принятых единиц трафика. 6. Способ по п.1, отличающийся тем, что индивидуальная прореживающая логическая схема осуществляет измерение разности между временем поступления пропущенной единицы трафика и временем поступления предшествующей единицы трафика и вычисление на основании этих разностей относительного времени T[i] , затраченного источником трафика на отдельный диапазон значений. 7. Способ по п.1, отличающийся тем, что указанное количество разностей также используют для аппроксимации относительного времени, затраченного источником трафика на отдельный диапазон значений. 8. Способ по п.1, отличающийся тем, что часть решений "пропустить" для единицы трафика переводят в состояние непротиворечивости решению "прервать передачу", принятому определенной выбранной прореживающей логической схемой, при этом указанную часть селектируют на основании критериев U прореживания, используемых выбранной прореживающей логической схемой. 9. Способ по п.1, отличающийся тем, что в качестве прореживающей логической схемы используют низкочастотную логическую схему, причем низкочастотная логическая схема обеспечивает прерывание передачи всего трафика, когда интенсивность передачи единиц трафика достигает определенного граничного значения. 10. Способ по п.6, отличающийся тем, что при переходе от одного периода измерений к другому в логических схемах массива прореживающих логических схем осуществляют автоматическое изменение граничного значения, превышение которого приводит к тому, что прореживающая логическая схема начинает прерывание передачи единиц трафика. 11. Способ по п.10, отличающийся тем, что новые граничные значения выбирают на основании оценок относительной частоты появления c[i] единиц трафика и вычисленных относительных времен T[i]. 12. Устройство для измерения трафика в системе связи, содержащее ряд параллельных прореживающих логических схем (G₁, ..., G_n), каждая из которых осуществляет прием информации, соответствующей передаваемым единицам трафика, в качестве которых используются элементы данных, пакеты, вызовы, а каждая прореживающая логическая схема содержит средство принятия решения для принятия решения "пропустить" или "прервать" передаваемую в системе единицу трафика, причем решение "пропустить" указывает на принятие единицы трафика как удовлетворяющей предварительно заданным критериям, и средство часов для определения времени появления каждой единицы трафика, отличающееся тем, что дополнительно содержит вычислительное средство для вычисления разностей между количеством решений, принятых отдельными прореживающими логическими схемами за определенный период времени. 13. Устройство по п.12, отличающееся тем, что вычислительное средство содержит ряд параллельных счетчиков, причем каждый отдельный счетчик определяет разность между количеством решений "пропустить", принятых двумя прореживающими логическими схемами. 14. Устройство по п.12, отличающееся тем, что вычислительное средство содержит ряд параллельных счетчиков, причем каждый отдельный счетчик определяет разность между количеством решений "прервать передачу", принятых двумя прореживающими логическими схемами.