Способ декорреляции сетевого трафика

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

Под коррелированностью трафика подразумевается статистическая зависимость случайных интервалов времени между пакетами и зависимость между собой случайных интервалов времени обработки пакетов. При возникновении такой статистической зависимости трафику, как случайному процессу, приписывают свойства самоподобия, которые возникают из-за воздействия на сетевой трафик различных факторов [1], таких как поведение пользователя, структура данных, их генерация и поиск, объединение трафика, управление трафиком и пр. Многочисленные исследования характеристик сетевых устройств [2, 3, 4, 5] показывают, что наличие, например, корреляционных свойств у последовательности интервалов времени между пакетами приводит к увеличению среднего времени задержки пакета в обрабатывающем устройстве, что в итоге снижает пропускную способность сети и, как следствие, могут не выполняться показатели качества обслуживания (QoS).

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

Известен способ декорреляции произвольной случайной последовательности (К. Фукунага. Введение в статистическую теорию распознавания образов / Пер. с англ. - М.: Наука, 1979,368с.), основанный на применении разложения Карунена-Лоэва. Суть применения разложения Карунена-Лоэва к декорреляции случайной последовательности интервалов времени между пакетами поясняется следующим образом.

Пусть - вектор (размером N) отсчетов значений интервалов времени между пакетами, зарегистрированный на некотором временном интервале времени (Т – символ транспонирования). Естественно, что все элементы матрицы Х являются положительными величинами. И пусть - корреляционная матрица отсчетов наблюдаемого вектора. Преобразуем вектор X c коррелированными элементами в некоторый вектор Y с некоррелированными элементами следующим образом , где ортогонализирующая матрица составлена из векторов , являющихся собственными векторами корреляционной матрицы , соответствующих i–му характеристическому числу, . Так как вектора , являются ортонормированными, т.е. удовлетворяют соотношению

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

При таком преобразовании некоторые из положительных элементов вектора X могут изменить знак. Если ко всем элементам вектора Y прибавить некоторое положительное число d, например, такое, чтобы выполнялось условие , и получить новый вектор , то это не внесет корреляции между элементами вектора , но сохранит физический смысл элементов данного вектора (интервалы времени не могут быть отрицательными). Здесь - наименьшее значение элемента вектора Y.

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

Недостатком данного способа является очень большое число операций, которое необходимо выполнить вычислительному устройству: - для расчета корреляционной матрицы, - для определения характеристических значений и собственных векторов корреляционной матрицы, - для выполнения декоррелирующего преобразования [6], - для расчета элементов модернизированной последовательности. Итого - операций. Даже при малых (например, ) реализация такого объема вычислений для декорреляции трафика может привести к недопустимо большой задержке пакетов в вычислительном устройстве, что приведёт к потере пропускной способности сети связи.

Самым близким к заявляемому способу по своей технической сущности является способ декорреляции сигналов в системе обработки аудиоданных. Патент № 2614381, дата конвенционного приоритета 14.02.2013 US 61/764,837, опубликовано 24.03.2017, МПК G10L 19/008 (2013.01), G10L 19/02 (2013.01), H04S 3/00 (2006.01).

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

1. Способ обработки звуковых сигналов, включающий:

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

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

…

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

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

На практике ограничиваются, как правило, малым числом элементов аудиоданных, подвергаемых декорреляции. Обычно число элементов
. Метод декорреляции, основанный на дискретном косинусном преобразовании (ДКП), можно описать следующим образом [7]. Используя предыдущие обозначения задачу можно сформулировать так. Есть вектор , составляющие которого суть коррелированные между собой интервалы времени между пакетами трафика. Необходимо, используя некоторую матрицу W, удовлетворяющую соотношению (где I – единичная матрица), получить вектор Y с некоррелированными элементами такого же размера N в виде . В дискретном косинусном преобразовании элементы матрицы W записываются как , .

Для элементы матрицы Y получаются в виде

.

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

Предлагаемое техническое решение направлено на уменьшение вычислительной сложности процесса декорреляции последовательности интервалов времени между пакетами за счет применения вейвлет – преобразования вместо преобразований Карунена-Лоэва и ДКП.

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

Способ декорреляции сетевого трафика реализуется устройством, поясненным фиг.1, где изображено: К_вх (входной коммутатор) 1, сниффер (устройство измерения интервалов времени) 2,
Рг.1 (регистр 1) 3, Рг.2 (регистр 2) 4, Пр. (процессор) 5, Рг.3 (регистр 3) 6, К_вых (выходной коммутатор) 7, блок декорреляции 8.

Способ декорреляции сетевого трафика реализуется устройством (фиг.1) следующим образом. Через входной коммутатор 1 пакеты из сети поступают в свободный блок декорреляции 8, номер которого передаётся в выходной коммутатор 7, в блоке декорреляции 8 пакеты поступают в регистр 3 до его заполнения, параллельно с процессом фиксации пакетов в регистре 3 в сниффере 2 производится измерение интервалов времени между приходящими пакетами и значения этих интервалов времени последовательно фиксируются в регистре 4 данного блока декорреляции 8, после заполнения пакетами регистра 3 процессор 5 через выходной коммутатор 7 переключает входной коммутатор 1 на другой свободный блок декорреляции 8, номер которого аналогично передаётся в выходной коммутатор 7, в данном блоке декорреляции 8 с использованием вейвлет-преобразования процессор 5 данного блока декорреляции 8 производит расчёт значений декоррелированных интервалов времени между пакетами, которые фиксируются в регистре 6, после завершения процесса расчёта декоррелированных интервалов времени между пакетами в данном блоке декорреляции 8 процессор 5 включает выходной коммутатор 7, который отдаёт в сеть пакеты из регистра 3 данного блока декорреляции 8 через интервалы времени, фиксированные в регистре 6, после заполнения пакетами регистра 3 и значениями интервалов времени между поступающими пакетами регистра 4 другого свободного блока декорреляции процесс обработки потока пакетов из сети продолжается аналогичным образом в другом свободном блоке декорреляции 8, при этом входной коммутатор 1 переключает входной поток пакетов на следующий свободный блок декорреляции 8 и процесс декорреляции входного потока пакетов продолжается непрерывно во времени.

Способ реализуется следующим образом.

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

, (1)

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

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

Разобьём последовательность интервалов времени между пакетами, фиксируемую в регистре 4, на группы по элементов в каждой группе. Каждую такую группу будем интерпретировать, как кусочно-постоянную функцию, заданную на разбиении отрезка на отрезков длины . Таким образом, получим функцию . Представим эту функцию (для простоты изложения) в пространстве вейвлетов Хаара [8] в виде

, (2)

где d – константа (среднее значение), а - вейвлет Хаара. При он определяется следующим образом

, (3)

а для остальных значений вейвлеты получаются сдвигами и сжатиями этого :

. (4)

Задача заключается в поиске набора коэффициентов и по заданной функции . При этом вычисление вейвлет-коэффициентов осуществляется по формулам

, (5)

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

Определим корреляционные свойства коэффициентов .

Дальнейший анализ для простоты и наглядности проведем при , что соответствует размеру, равному , для регистра 3. Раскроем сумму в выражении (6) при данном k

, (7)

где .

Для фиксированного k вейвлеты существуют не для всех значений функции . На фиг.2 представлены все вейвлеты, полученные по формулам (3) и (4), для . Как следует из фиг.2, всего при существует 7 функций. Ниже каждая функция представлена своими 8 отсчетными значениями на интервале :

, ,

, ,

, ,

.

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

Выпишем некоторые значения в явном виде.

,

,

.

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

Определим, для примера, корреляцию и , а также и .

.

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

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

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

Таким образом, приведенный анализ подтверждает эффективность предлагаемого способа.

ЛИТЕРАТУРА

1. Шелухин О.И., Тенякшев А.М., Осин А.В. Фрактальные процессы в телекоммуникациях / Под ред. О.И. Шелухина. – М.: Радиотехника, 2003.- 480с.

2. Назаров А.Н., Сычев К.И. Модели и методы расчета показателей качества функционирования узлового оборудования и структурно-сетевых параметров сетей связи следующего поколения. – 2-е изд. перераб. и доп. - Красноярск: Изд-во ООО «Поликом», 2011. – 491с.

3. Бузов А.Л., Букашкин С.А. и др. Специальная радиосвязь. Развитие и модернизация оборудования и объектов / М.: Радиотехника. - 2017. – 448с.

4. Галкин А.М., Симонина О.А., Яновский Г.Г. Анализ характеристик сетей NGN с учетом свойств самоподобия трафика // Электросвязь, №12, 2007, с. 23-25.

5. Карташевский И.В., Волков А.Н., Киричек Р.В. Анализ среднего времени задержки в системе массового обслуживания при обработке коррелированного трафика // Электросвязь, №3, 2019, с.41-50.

6. Чернов В.М. Арифметические методы синтеза быстрых алгоритмов дискретных ортогональных преобразований. – М.: Физматлит, 2007.-264с.

7. Сэломон Д. Сжатие данных, изображений и звука.- ТЕХНОСФЕРА, Москва, 2004 – 368с.

8. Дремин И.М., Иванов О.В., Нечитайло В.А. Вейвлеты и их использование // Успехи физических наук, 2001, т.171, №5, с.485-501.

9. Малла С. Вэйвлеты в обработке сигналов.- М.: Мир, 2005, 671с.