MODEL FOR TRANSFORMATION OF SELF-SIMULAR TRAFFIC INTO POISSONS ARRIVAL PACKETS

Full Text

При использовании в транспортных сетях различных механизмов управления, неизбежно возникают нелинейные зависимости ввиду объективной ограниченности имеющихся ресурсов, приводящих к различным конфликтным ситуациям и проявлению фрактальных свойств сетевой нагрузки, которые не могут быть разрешены простыми способами. Если в транспортных сетях механизмы управления потоками не используются, сетевой трафик в меньшей степени проявляет фрактальные свойства. Проблема возникает при использовании механизмов управления потоками и предотвращения перегрузки, когда появляется дополнительная нелинейность. В подобных ситуациях могут возникнуть сложные взаимосвязи между флюктуациями рабочей нагрузки и сетевыми механизмами управления. Проблема корректного распределения сетевых ресурсов при таких ситуациях становится особенно актуальной. Возникающие нелинейности с возможностями динамического поведения систем в пакетных сетях, приводят к проявлениям хаотических свойств, что приводит к возникновению проблем, в рамках которых требуется: - осуществлять проверку сетевого трафика на самоподобность; - проводить измерение численных значений показателя Херста; - знать степень изменения характеристик трафика под действием механизмов сетевого управления в процессе эксплуатации транспортных сетей; - оценивать влияние трафика на производительность и эффективность механизмов сетевого управления. На практике проверка трафика на самоподобие является чрезвычайно сложной задачей. Проблема состоит в том, что в реальных условиях всегда оперируют с конечным набором данных. Поэтому задача проверить, является ли трасса самоподобной, на практике обычно является невыполнимой. Необходимо исследовать различные свойства самоподобности в реальном трафике. Трудность заключается в том, что даже если подтверждаются некоторые свойства самоподобности, нельзя сделать вывод о том, что проанализированные данные имеют самоподобную структуру, так как к тем же самым свойствам трафика могут приводить и другие воздействия (например, нестационарность). Некоторые нестационарные процессы (процессы со смещающими уровнями), могут приводить к подобным свойствам. Это означает, что пульсирующий сетевой трафик может быть вызван как долговременной зависимостью, так и нестационарностью наблюдаемого процесса. Исследования показали, что присутствие нестационарности может привести к неправильным выводам при анализе результатов тестов на самоподобие. Необходимо также располагать предварительными сведениями о пределах изменения критических значений параметров самоподобности. Это позволит провести моделирование данных процессов в реальном сетевом окружении, генерируя процессы с заданными характеристиками; исследовать реакцию транспортной сети при воздействии на ее входы самоподобного трафика; определить практические шаги по управлению самоподобным трафиком; заранее получить аналитические зависимости при оптимизации топологических структур транспортных сетей. Анализ состояния проблемы Исследование проблемы управления самоподобным трафиком находится на ранней стадии своего развития [1]. Масштабно инвариантная структура трафика вносит новые сложности в общую картину управления транспортной сетью, что делает задачу предоставления требуемого качества обслуживания и эффективного использования ресурсов более сложной. Пульсирующая структура трафика с самоподобными свойствами подразумевает существование периодов скученности (высокой активности) на больших временных масштабах времени, что отрицательно сказывается на управлении перегрузкой. Однако, долговременная зависимость, по определению, подразумевает существование необычной корреляционной структуры трафика, что может быть использовано для целей так называемого перегрузочного управления. В [1] показана возможность прогнозирования случайных процессов в условиях передачи самоподобного трафика с высокой надежностью и на больших временных интервалах. Для этих целей предложен механизм регулирования трафика, основанный на многомасштабной структуре перегрузочного управления, который может быть использован для повышения эффективности функционирования сети. Инвариантная к масштабу пульсирующая структура трафика оказывает влияние на качественные показатели и производительность сети и несовместима с традиционными моделями сетевого трафика. Поэтому, выяснение причин, а также снижение влияния последствий самоподобия, являются чрезвычайно важными задачами для практики. При разработке эффективных объединенных сетевых структур, в пределах которых поддерживаются гарантии запрашиваемого QoS (Quality of Service) при максимально эффективном использовании ресурсов, вопросы понимания и обоснования самоподобия на основе физических принципов реального сетевого окружения выходят на первое место. На основе анализа более семисот англоамериканских источников авторами определены основные факторы, которые могут продуцировать в сетевом трафике долговременную зависимость различных видов [1]: поведение пользователя; генерация, структура и поиск данных; объединение трафика; средства управления сетью; механизмы управления с обратной связью; развитие сети. Отметим, что действие указанных механизмов позволяет влиять на структуру трафика, изменяя его природу, и, если самоподобие уже присуще трафику, в некоторых случаях усилить его [2]. Однако трудно представить, что в силу действия указанных факторов самоподобие может возникнуть само по себе. Возникновение фрактальных свойств трафика на прикладном уровне возможно только в случае, когда сам источник является хаотической динамической системой и генерирует трафик, обладающий свойством самоподобия, что маловероятно [2]. Многочисленные измерения показали, что подобная структура трафика - не отдельное побочное явление, а характерная особенность, сложившаяся в пределах существующих распределенных сетевых структур с промежуточным накоплением, к которым относятся и современные транспортные телекоммуникационные сети. Возникает естественное мнение, что в основе самоподобия лежит единственный причинный фактор, который, несмотря на многообразие форм проявления, объединяет всю их совокупность одним и тем же способом обработки информации [2]. Таким образом, самоподобие, является неотъемлемым свойством пакетных сетей. Статистические свойства потока пакетов определяются следующими факторами [2-4]: - случайным характером трафика в виде битового потока, генерируемого источником информации; - особенностями преобразования битового потока в поток пакетов, обусловленные технологическими особенностями преобразования; - целенаправленными преобразованиями потока в процессе агрегирования с целью улучшения качественных показателей. Так как в этих трех случаях пакеты поступают неравномерно, то временной интервал между последовательными приходами пакетов является случайной величиной [5]. На статистические характеристики и структуру полученного потока пакетов, в свою очередь воздействует целый ряд факторов [2]: - специфика операционных систем с разделением времени. Каждый процесс в системе развивается в «виртуальном времени», что определяется, прежде всего, доступными ресурсами. В процессе передачи информации от уровня приложения до канального уровня, возникают неравномерности интервалов времени между фазами формирования пакетов, даже при условии генерации равномерного потока данных; - динамика работы информационного приложения, использующего средства межсетевого взаимодействия, является важным фактором, определяющим характер агрегированного потока данных. Приложение может генерировать данные с интенсивностью, определяемой наличными ресурсами (объемом буферной памяти и пропускной способностью каналов связи); - реализация протокола транспортного уровня. Обеспечивает достоверную доставку пакетов и регулирование скорости их передачи с использованием замкнутого контура обратной связи между получателем и источником данных; - особенности работы протоколов канального уровня, например, коллизии, возникающие при разделении среды передачи, увеличивающие временные интервалы между пакетами при росте загрузки каналов. Это проявляется особенно наглядно в сетях, использующих протоколы TCP/IP, в которых реализуется «оконное управление». В [1] показано, что трафик, не проявляющий ранее самоподобных свойств, пройдя обработку в узловых серверах сети, превращается в сетевой фрактал; - характеристики и административные ограничения, введенные в промежуточных сетевых узлах с целью обеспечения заданных параметров качества сервиса. Более сложные зависимости в потоке данных возникают при использовании протоколов АТМ и Frame Relay, которые предусматривают встроенные функции контроля качества виртуальных соединений с помощью стратегий буферизации, приоритезации и резервирования [2]. Формирование трафика в этом случае направлено на изменение характеристик потока пакетов в соединении виртуального пути или канала с целью снижения пиковой скорости, ограничения длины пачки или снижения времени задержки путем расстановки пакетов во времени, а также планирования трафика (Traffic Shaping). Право формирования трафика предоставляется как операторам сети, так и пользователям с целью согласования его параметров, проходящего через интерфейс «пользователь-сеть», с соглашением по трафику. Для сетевых операторов формирование трафика становится эффективным средством оптимального использования сетевых ресурсов по критерию «задержка-производительность» [2]. Одним из свойств мультисервисного трафика является его структурная сложность, которая характеризуется коэффициентом вариации c(t). Коэффициент вариации c(t) является дисперсионной характеристикой потока пакетов и определяется отношением среднеквадратического отклонения s(t) значений интервалов времени τ между поступлением очередных пакетов к их математическому ожиданию m(t), то есть . Мультисервисному потоку пакетов современных транспортных телекоммуникационных сетей присущи свойства нестационарности и самоподобия, который, в отличие от потока пакетов с пуассоновским распределением, имеет коэффициент вариации больше единицы, то есть . В [2] показано, что эффективность использования сетевых ресурсов у трафика, имеющего поток пакетов с пуассоновским распределением гораздо выше, чем у самоподобного потока пакетов, свойства которого, в основном, описываются коэффициентом Херста Н. В статье предложена модель, в основе которой использованы функциональные преобразования, имеющие цель снизить структурную сложность входного самоподобного потока пакетов и получить поток, имеющий свойства простейшего потока, коэффициент вариации которого равен единице. Постановка задачи Исходя из целевой установки исследований будем считать, что входной поток пакетов подвергается идентификации известными аналитическими методами с целью определения его самоподобных свойств. Предположим, что в результате идентификации установлено, что плотность распределения интервалов времени между пакетами описывается законом Парето. В канале функциональных преобразований узла коммутации осуществляется преобразование плотности распределения интервалов времени между пакетами потока , в экспоненциальный закон . В результате функциональных преобразований плотности распределения интервалов времени пакетов потока , его структурная сложность была снижена до единицы и получен поток , имеющий свойства простейшего потока. Необходимо выполнить следующие действия. 1. Разработать модель, преобразующая входной поток пакетов , у которого плотность распределения интервалов времени между пакетами распределена по закону Парето и структурная сложность , в поток , плотность распределения интервалов времени между пакетами которого описывается экспоненциальным законом распределения и имеет структурную сложность . 2. Найти функциональную связь между показателем Херста и коэффициентом вариации, определяющим структурную сложностью входного потока пакетов, обладающего заведомо самоподобными свойствами. Для корректности решения задачи введем ограничения: длина пакета L0 является фиксированной величиной; длительность интервала времени τi определяется временем формирования пакета в буфере; при относительно малых значениях длины пакета L0 с малой погрешностью среднее значение скорости процесса rср можно заменить мгновенной скоростью r(t) в интервале t, то есть rср = r(t). 3. Определить среднее значение скорости процесса, которое на интервале τ формирует пакет длиной L0, то есть rср t = L0. 5. Случайная переменная Z имеет распределение с тяжелым хвостом, если вероятность , (1) где является индексом «хвоста» или параметром формы, с - положительная константа [1]. 6. Учесть, что корреляционная функция является инвариантной относительно сдвига, то есть для любых . Предполагается, что первые два момента существуют и конечны: , . Здесь - операция усреднения; m - первый центральный момент; - дисперсия процесса X(t). 7. Случайный процесс X(t) является точно самоподобным второго порядка с показателем Херста 1/2 < H < 1, если для любых . 8. Функция преобразования плотности вероятности интервалов времени между пакетами - однозначная дифференцируемая функция, для которой известна и существует обратная функция . 9. При функциональных преобразованиях плотности вероятности интервалов времени между пакетами выполняется свойство инвариантности дифференциала вероятности, вероятности этих двух событий равны . Модель преобразования самоподобного потока в пуассоновский поток пакетов Так как случайные величины x и у связаны однозначной дифференцируемой функциональной зависимостью, необходимо исходить из того факта, что полученные значения случайной величины X, заключены в интервале [x, x+dx]. Отсюда следует, что величина y будет также находиться в интервале [у, у + dу], где , а . Поскольку при этих условиях выполняется свойство инвариантности дифференциала вероятности, то вероятности этих двух событий равны (2) откуда следует, что . (3) Аналитические выражения функции y = f(x) с указанием области определения играют ключевую роль при синтезе законов распределения случайных величин. Поэтому в классе дифференцируемых функций необходимо определить такие, которые обеспечивали бы получение функций с заданными характеристиками. При преобразованиях законов распределения трафика скорость передачи информации, доступная пользователю i-ой службы транспортной сети является стохастической величиной. Следовательно, она представляет совокупность функций времени и имеет вероятностное описание. Соответствующими вероятностными характеристиками могут быть безусловные и совместные плотности вероятности случайных величин, являющиеся точечными функциями процесса для фиксированных моментов времени. Причем полная их совокупность (например, битовая скорость передачи информации), представляет ансамбль, где любая его компонента есть выборочная функция случайного процесса rk(t), отнесенная к конкретному сеансу [2; 6]. Значения ее реализации в некоторый момент времени ti определяют случайную величину [5]. При пакетной коммутации битовый поток преобразуется в дискретную последовательность пакетов, в общем случае переменной длительности [2; 5]. Для проведения количественного анализа ограничимся фиксированной длиной L пакета. В этом случае структура трафика полностью описывается распределением длительности интервалов времени между передаваемыми пакетами [2; 7]. Длительность интервала t определяется временем накопления информации в буфере, достаточном для образования пакета заданной длины L0 [2]: . (4) Левая часть (4) является средним значением скорости передачи на интервале t, умноженное на длину этого интервала, то есть [2; 4]: , (5) где . При относительно малых значениях длины пакета L0 с малой погрешностью rср заменим текущее значение скорости в интервале t, то есть rср = r. Это допущение дает возможность найти функциональную зависимость между случайными величинами t и r [2; 8]: , (6) и, следовательно, определить закон распределения g(t) непрерывной случайной величины t, как функцию одного случайного аргумента r, если известен закон его распределения . Рассмотрим случай, когда исходная плотность вероятности описывает распределение мгновенных значений случайного процесса . Случайная величина связана с ней функциональной зависимостью (6) и определяет характер преобразования. Результатом преобразования является получение пакетов в накопителе, при этом случайная величина , где t - интервал времени между пакетами, является случайной величиной, и закон распределения величины t полностью описывает статистические свойства потока пакетов, так что . (7) Связь между мгновенными значениями случайного процесса и интервалом времени между образованными таким образом пакетами t, перепишется в виде [8]: , (8) а плотность распределения интервалов времени между пакетами определяется формулой (9) В (8) параметр а является нижним ограничением, определяемым из условия нормировки Отличительной особенностью зависимости между случайными величинами r и t является инвариантность по отношению к замене местами функции и аргумента (обратная пропорциональность). Выразим эту зависимость через обобщенные переменные , что позволяет рассматривать закон распределения (9) как обратное преобразование: (10) Тогда модель преобразования самоподобного потока закона Парето в пуассоновский поток пакетов может быть получена из следующих рассуждений. Пусть непрерывная случайная величина с плотностью распределения подвергается преобразованию . Необходимо выбрать функцию такую, чтобы в результате преобразования получился закон распределения [5] , (11) где - длительность интервала между пакетами. Согласно (1) функции распределения должны быть равны, то есть . (12) Отсюда [7] . (13) Решая (12) относительно , получим . Дифференцируя (12) по , получим [8] . (14) Определение функциональной связи между показателем Херста и коэффициентом вариации Пусть имеется входной поток пакетов , имеющий плотность распределения интервалов времени между пакетами и обладающий самоподобными свойствами. Для определенности покажем решение данной задачи для длины выборки входного потока , состоящей из 106 пакетов, имеющей плотность распределения интервалов времени между пакетами по закону Парето, обладающего заведомо самоподобными свойствами (показатель Херста H = 0,8), интегральная функция распределения которого имеет вид , где k - нижний граничный параметр, a - коэффициент формы. Для генерирования случайных величин с распределением Парето воспользуемся подходом, изложенном в [1]. Требуется найти обратную функцию от интегральной функции распределения [1]: где rnd (1) - случайная переменная, равномерно распределенная на интервале [0, 1]. Параметр α связан с показателем Херста зависимостью [1] Для экспоненциальных сетей распределение интервалов времени между пакетами определяется формулой где - управляемая интенсивность потока пакетов [1; 8]. Моделирование пуассоновского закона распределения интервалов времени между пакетами проведем, используя формулу [1-2]: . Определим численные значения входного потока пакетов : математическое ожидание, дисперсию, среднее квадратическое отклонение, коэффициент вариации. Получим результат: ; . Рис. 1. Графики: а) зависимость коэффициента вариации от показателя Херста входного потока; б) связь между интенсивностью экспоненциального закона и коэффициентом вариации входного потока; в) зависимость показателя формы a закона Парето и интенсивности экспоненциального закона Таблица 1. Функциональное преобразование распределения интервалов следования пакетов закона Парето в экспоненциальный закон Исходный закон распределения Парето Функция преобразования Экспоненциальный закон распределения интервалов пакетов Для трафика, имеющего показатель Херста H = 0,8 коэффициент вариации оказался гораздо больше единицы. На рис. 1 представлены зависимости: коэффициента вариации от показателя Херста входного потока , связь между интенсивностью экспоненциального закона и коэффициентом вариации входного потока, а также зависимость показателя формы a закона Парето и интенсивности экспоненциального закона при равенстве их математических ожиданий. В качестве конкретного примера рассмотрим преобразование закона распределения Парето в экспоненциальный закон, результаты моделирования которого представлены в таблице 1 [5]. Рис. 2. Аппроксимация зависимости от Н входного потока Найдем функциональную связь между коэффициентом вариации и показателем Херста, используя уравнение кубической регрессии: Аппроксимация зависимости коэффициента вариации от показателя Херста входного потока представлена на рис. 2 Для оценки значимости параметров регрессии и корреляции определим среднее значение коэффициента вариации: Составим таблицу 2 вспомогательных величин, где ; Определим индекс корреляции: Индекс детерминации равен Используя значения таблицы 2, определим среднюю ошибку аппроксимации коэффициента вариации Таблица 2. Таблица вспомогательных величин для оценки значимости регрессии и корреляции i Hi Ai 1 0,3 0,868 0,591 -2,511 6,307 0,277 0,0770 0,3195 - - 2 0,35 0,952 0,985 -2,427 5,892 -0,033 0,0011 0,034 -0,1295 0,0168 3 0,4 1,054 1,218 -2,325 5,407 -0,164 0,0269 0,1555 -0,047 0,0022 4 0,45 1,178 1,345 -2,201 4,846 -0,167 0,0280 0,142 0,011 0,0001 5 0,5 1,330 1,422 -2,049 4,200 -0,092 0,0085 0,0695 0,0445 0,002 6 0,55 1,522 1,503 -1,857 3,450 0,019 0,0003 0,012 0,0565 0,0032 7 0,6 1,768 1,644 -1,611 2,596 0,1243 0,0155 0,070 0,050 0,0025 8 0,65 2,088 1,898 -1,291 1,669 0,190 0,0360 0,091 0,026 0,0007 9 0,7 2,514 2,322 -0,865 0,749 0,192 0,0368 0,076 -0,0075 0,0001 10 0,75 3,091 2,970 -0,288 0,083 0,121 0,0146 0,039 -0,0445 0,0020 11 0,8 3,890 3,898 0,511 0,261 -0,008 0,0001 0,002 0,228 0,0520 12 0,85 5,011 5,159 1,632 2,662 -0,148 0,0220 0,0295 -0,0671 0,0045 13 0,9 6,598 6,810 3,219 10,36 -0,212 0,0451 0,032 -0,0156 0,0002 14 0,95 8.825 8,905 5.446 29,65 -0,080 0,0065 0,009 0,0984 0,0097 15 1 11,85 11,50 8,471 71,75 0,350 0,1225 0,0295 0,2549 0,065 ∑ - - - - 253,48 - 0,7570 2,070 - 0,3760 Выводы Разработана модель, преобразующая входной поток пакетов , у которого плотность распределения интервалов времени между пакетами распределена по закону Парето, в поток , плотность распределения интервалов времени между пакетами которого, описывается экспоненциальным законом распределения и имеет структурную сложность . Модель позволяет получать последовательность пакетов с заданными свойствами, которая может использоваться при моделировании самоподобного трафика. Анализ показал, что с увеличением показателя Херста Н коэффициент вариации, характеризующий структурную сложность трафика возрастает. Для трафика, имеющего коэффициент вариации много больше единицы, в случае его преобразования в узлах коммутации, с целью получения простейшего потока, необходимо учитывать то обстоятельство, что с увеличением коэффициента вариации входного потока интенсивность выходного потока уменьшается. Определена зависимость показателя формы а закона Парето и интенсивности экспоненциального закона при равенстве их математических ожиданий. Установлено, что с увеличением показателя формы а интенсивность увеличивается. Установлена функциональная связь между коэффициентом вариации и показателем Херста с использованием уравнения кубической регрессии. Для закона Парето определены индекс корреляции, индекс детерминации, средняя ошибка аппроксимации и F-критерии Фишера.

About the authors

Gennady Ivanovich Linets

North-Caucasian Federal University

Email: kbytw@mail.ru

Svetlana Vladimirovna Govorova

North-Caucasian Federal University

Email: mitnik2@yandex.ru

References

Supplementary files