USE FUNCTIONAL TRANSFORMATION OF SELF-SIMILAR FLOW OF PACKETS TO IMPROVE PERFORMANCE TRANSPORT NETWORKS

Full Text

Введение При использовании в транспортных сетях (ТС) различных механизмов управления неизбежно возникают нелинейные зависимости ввиду объективной ограниченности имеющихся ресурсов, приводящей к различным конфликтным ситуациям и проявлению фрактальных свойств сетевой нагрузки, которые не могут быть разрешены простыми способами. Если в ТС механизмы управления потоками не используются, сетевой трафик в меньшей степени проявляет фрактальные свойства. Проблема возникает при использовании механизмов управления потоками и предотвращения перегрузки, когда появляется дополнительная нелинейность. В подобных ситуациях могут возникнуть сложные взаимосвязи между флуктуациями рабочей нагрузки и сетевыми механизмами управления. Проблема корректного распределения сетевых ресурсов при таких ситуациях становится особенно актуальной. Несмотря на продолжительный период активного изучения явления самоподобия в современных сетях, до сих пор остается ряд нерешенных вопросов и задач, основными из которых явля ются [1]: не выявлен единый причинный фактор, приводящий к появлению самоподобного трафика; самоподобие проявляется в основном в сетях с промежуточным накоплением (в пакетных сетях); нет единой общепризнанной модели самоподобного трафика; фактически отсутствует строгая теоретическая база, которая пришла бы на смену классической теории массового обслуживания при проектировании современных систем распределения информации с самоподобным трафиком; не существует достоверной и признанной методики расчета параметров и показателей эффективности систем, имеющих распределенную структуру и учитывающих влияние эффекта самоподобия трафика при информационном обмене; практически отсутствуют методики и алгоритмы, обеспечивающие заданное качество обслуживания в условиях самоподобного трафика. Возникающие нелинейности с возможностями динамического поведения систем в пакетных сетях приводят к проявлениям хаотических свойств, что приводит к возникновению следующих проблем. Требуется: - осуществлять проверку сетевого трафика на самоподобность; - проводить измерение численных значений показателя Херста; - знать степень изменения характеристик трафика под действием механизмов сетевого управления в процессе эксплуатации транспортных сетей; - оценивать влияние трафика на производительность и эффективность механизмов сетевого управления. «Инфокоммуникационные технологии» Том 12, № 1, 2014 30 Линец Г.И, Говорова С.В. На практике проверка трафика на самоподобие является чрезвычайно сложной задачей. Проблема состоит в том, что в реальных условиях всегда оперируют с конечным набором данных. Поэтому проверить, является ли трасса самоподобной, на практике обычно является невыполнимой задачей. Необходимо исследовать различные свойства самоподобности в реальном трафике. Трудность заключается в том, что, даже если подтверждаются некоторые свойства само-подобности, нельзя сделать вывод о том, что проанализированные данные имеют самоподобную структуру, так как к тем же самым свойствам трафика могут приводить и другие воздействия (например, наличие нестационарности). Некоторые нестационарные процессы (например, процессы со смещающими уровнями) могут приводить к подобным свойствам. Это означает, что пульсирующий сетевой трафик может быть вызван как долговременной зависимостью, так и нестацио-нарностью наблюдаемого процесса. Исследования показали, что присутствие нестационарно-сти может «обмануть» тесты на самоподобие. Возможность решения этой проблемы вызывает сомнение, поскольку использование показателя Херста в практических целях и его интерпретация весьма не очевидна для реальных трафиковых трасс, поскольку измеренные его значения не дают оснований рассматривать их как теоретически самоподобный процесс, тем более использовать их результаты при моделировании. Необходимо заведомо знать, что рассматриваемый процесс является самоподобным. Это возможно только при знании причин возникновения самоподобности того или иного вида. Необходимо также располагать предварительными сведениями о пределах изменения критических значений параметров самоподобности. Это позволит: провести моделирование данных процессов в реальном сетевом окружении, генерируя процессы с заданными характеристиками; исследовать реакцию ТС при воздействии на ее входы самоподобного трафика; определить практические шаги по управлению самоподобным трафиком; заранее получить аналитические зависимости при оптимизации топологических структур транспортных сетей. Исследование проблемы управления самоподобным трафиком находится на ранней стадии своего развития [1]. Под управлением самоподобным трафиком понимают проблему регулирования трафика таким образом, чтобы производительность и эффективность использования сетевых ресурсов были оптимальными (в том числе и пропускная способность). Масштабно инвариантная структура трафика вносит новые сложности в общую картину управления ТС, что делает задачу предоставления требуемого качества обслуживания и эффективного использования ресурсов более сложной. Пульсирующая структура трафика с самоподобными свойствами подразумевает существование периодов скученности (высокой активности) на больших временных масштабах, что отрицательно сказывается на управлении перегрузкой. Однако долговременная зависимость, по определению, подразумевает существование необычной корреляционной структуры трафика, что может быть использовано для целей так называемого перегрузочного управления. В [1] показана возможность предсказания (прогнозирования) случайных процессов в условиях передачи самоподобного трафика с высокой надежностью и на больших временных интервалах. Для этих целей может быть предложен механизм регулирования трафика, основанный на многомасштабной структуре перегрузочного управления, который используется для повышения эффективности функционирования ТС, в частности, для увеличения ее производительности [1]. Так называемый механизм селективной агрессивности дает достаточно хорошие результаты даже для кратковременно зависимого трафика, и тем более этот механизм намного эффективнее для долговременно зависимого трафика. Его применение приводит к гораздо большему выигрышу в отношении производительности [1]. Причины самоподобия в трафике ТС Исследования последних лет локального и глобального трафика привели к восприятию свойств, которые проявляются в изменчивости трафика в широком диапазоне масштабов времени, получивших название самоподобия [1-2]. Инвариантная к масштабу пульсирующая структура трафика оказывает влияние на качественные показатели и производительность сети и несовместима с традиционными моделями сетевого трафика. Повсеместность этого явления поразительна, поскольку самоподобие наблюдается в различных сетевых контекстах, от Ethernet до ATM, LAN, WAN, сжатого видео и WWW-трафика, поэтому выяснение причин и последствий самоподобия является чрезвычайно важной задачей [1-3]. При разработке эффективных объединенных сетевых структур, в пределах которых поддерживаются гарантии запрашиваемого QoS «Инфокоммуникационные технологии» Том 12, № 1, 2014 Линец Г.И, Говорова С.В. 31 (Quality of Service) при максимально эффективном использовании ресурсов, вопросы понимания и обоснования самоподобия на основе физических принципов реального сетевого окружения выходят на первое место. В [1] при анализе причин самоподобия в трафике утверждается, что самоподобие может возникать в результате объединения множества отдельных, сильно изменчивых ОК/ОРР-источников, проявляющих синдром бесконечной дисперсии. Иначе говоря, в результате наложения образуется объединенный сетевой трафик, стремящийся к фрактальному броуновскому движению. Однако авторы признают, что, несмотря на ценность полученных результатов, эти результаты страдают из-за целого ряда предположений, которые не являются реалистичными в условиях реального сетевого окружения [2]. Сложность понимания лежащих в основе принципов, которые могут привести к самоподобию в сетевом трафике, определяется, по мнению авторов, тем, что не существует одного причинного фактора, вызывающего самоподобность. На основе анализа более 700 библиографических источников (в основном американского производства) авторы приводят основные факторы, которые могут продуцировать в сетевом трафике долговременную зависимость различных видов [1-2]: поведение пользователя; генерация, структура и поиск данных; объединение трафика; средства управления ТС; механизмы управления с обратной связью; развитие сети. Следует отметить, что действие указанных механизмов позволяет влиять на структуру трафика, изменяя его природу, и, если самоподобие уже присуще трафику, в некоторых случаях усилить его [2].Однако трудно представить, что в силу действия указанных факторов самоподобие может возникнуть само по себе. Возникновение фрактальных свойств трафика на прикладном уровне возможно только в случае, когда сам источник является хаотической динамической системой и генерирует трафик, обладающий свойством самоподобия, что мало вероятно [2]. Многочисленные измерения показали, что подобная структура трафика - не отдельное побочное явление, а характерная особенность, сложившаяся в пределах существующих распределенных сетевых структур с промежуточным накоплением, к которым относятся и современные ТС. Возникает естественное мнение, что в основе самоподобия лежит один-единст-венный причинный фактор, который, несмотря на многообразие форм проявления, объединяет всю их совокупность одним и тем же способом обработки информации [2]. Таким образом, самоподобие является неотъемлемым свойством пакетных сетей. Целью исследования является доказательство того, что долговременная зависимость, следовательно и самоподобие, в сетевых структурах возникает в процессе преобразования битового потока в поток пакетов [2]. Статистические свойства потока пакетов определяются следующими факторами [2; 4-5]: - случайным характером трафика в виде битового потока, генерируемого источником информации; - особенностями преобразования битового потока в поток пакетов (ячеек), обусловленными технологическими особенностями преобразования; - целенаправленными преобразованиями потока в процессе агрегирования с целью улучшения качественных показателей. Так как в этих трех случаях пакеты поступают неравномерно, то временной интервал между последовательными приходами пакетов является случайной величиной [4]. На статистические характеристики и структуру полученного потока пакетов, в свою очередь воздействует целый ряд факторов [2]: а) специфика операционных систем с разделением времени. Каждый процесс в системе развивается в «виртуальном времени», что определяется прежде всего доступными ресурсами. В процессе передачи информации от уровня приложения до канального уровня возникают неравномерности интервалов времени между фазами формирования пакетов, даже при условии генерации равномерного потока данных; б) динамика работы информационного приложения, использующего средства межсетевого взаимодействия, является важным фактором, определяющим характер агрегированного потока данных. Приложение может генерировать данные с интенсивностью, определяемой наличными ресурсами (объемом буферной памяти и пропускной способностью каналов связи); в) реализация протокола транспортного уровня. Обеспечивает достоверную доставку пакетов и регулирование скорости их передачи с использованием замкнутого контура обратной связи между получателем и источником данных; г) особенности работы протоколов канального уровня, например коллизии, возникающие при разделении среды передачи, увеличива «Инфокоммуникационные технологии» Том 12, № 1, 2014 32 Линец Г.И, Говорова С.В. ющие временные интервалы между пакетами при росте загрузки каналов. Это проявляется особенно наглядно в сетях, использующих протоколы TCP/IP, в которых реализуется «оконное управление». В [1] показано, что трафик, не проявлявший ранее самоподобных свойств, пройдя обработку в узловых серверах сети, превращается в сетевой фрактал; д) характеристики и административные ограничения, введенные в промежуточных сетевых узлах с целью обеспечения заданных параметров качества сервиса. Более сложные зависимости в потоке данных возникают при использовании протоколов АТМ и Frame Relay, которые предусматривают встроенные функции контроля качества виртуальных соединений с помощью стратегий буферизации, приоритезации и резервирования [2; 6]. Формирование трафика в этом случае направлено на целенаправленное изменение характеристик потока ячеек в соединении виртуального пути или канала с целью снижения пиковой скорости, ограничения длины пачки или снижения времени задержки путем расстановки ячеек во времени, а также планирования трафика (Traffic Shaping). Право формирования трафика предоставляется как операторам сети, так и пользователям с целью согласования параметров трафика, проходящего через интерфейс «пользователь-сеть», с соглашением по трафику. Для сетевых операторов формирование трафика становится эффективным средством оптимального использования сетевых ресурсов по критерию «задержка-производительность» [2]. Постановка задачи функциональных преобразований трафика по критерию максимальной производительности Исходя из целевой установки исследования, требуется достичь максимальной производительности ТС. В динамической модели канала функциональных преобразований осуществляются преобразования, которые формально могут быть представлены в виде / О) -> F(?i) -> Ft (b ) -> g(T2). Канал функциональных преобразований решает следующие задачи: 1. Преобразование битового потока f x) в поток пакетов F(-r). 2. Идентификацию потока пакетов F(ri) известными аналитическими законами Fi(ri). 3. Преобразование потока пакетов Fi(ri) в закон g(r2), обеспечивающий максимальную про изводительность ТС. В статье приведены решения первой и третьей задач. Аналитическая модель преобразования плотности распределения битового потока в поток пакетов. Стохастический процесс будем называть фрактальным, когда некоторые из его важных статистических характеристик проявляют свойства масштабирования с соответствующими масштабными показателями [1]. К числу основных понятий, определяющих свойства фрактальных процессов, относятся самоподобность, долговременная зависимость, медленно затухающая дисперсия, бесконечные моменты, фрактальные размерности, распределения с тяжелыми хвостами, зависимость спектральной плотности S(rn) по закону 1/f [1]. Ограничим класс используемых в работе самоподобных процессов процессами, статистические свойства которых полностью определяются распределением длительности интервалов между пакетами. Эти процессы наиболее характерны для пакетных сетей, в которых преобразования битового потока в поток пакетов сопровождаются появлением распределений с тяжелыми хвостами. Введем новый класс самоподобных процессов, который определим как процесс с сингулярной (особой) интенсивностью [7]. В них преобразование исходного битового потока по формуле преобразования г(г) = 1/г мгновенных значений битовой скорости, задаваемого плотностью распределения, концентрирует пакеты вблизи нуля, увеличивая его пачечность (по этой причине они названы сингулярными). Интенсивность таких потоков обратно пропорциональна длительности интервалов между пакетами т. Отличительными свойствами (ограничениями) сингулярных процессов являются следующие моменты. 1. Длина пакета L0 является фиксированной величиной. 2. Длительность интервала времени т определяется временем формирования пакета в буфере. 3. При относительно малых значениях длины пакета Lо с небольшой погрешностью среднее значение скорости процесса rcp можно заменить мгновенной скоростью r(t) в интервале г, то есть Гер = r{f). 4. Среднее значение скорости процесса на интервале т формирует пакет длиной L то есть уср t L0. 5. Случайная переменная Z имеет распределение с тяжелым хвостом, если вероятность «Инфокоммуникационные технологии» Том 12, № 1, 2014 Линец Г.И, Говорова С.В. 33 P[Z > х]« сх а, х -> оо, где 0 < а <2 является индексом хвоста или параметром формы, с - положительная константа [1]. 6. Корреляционная функция R(t1,t2) = - /и)] является инвариантной относительно сдвига, то есть R(Ji,t2)~ +k,t2+ к) для любых tl,t2,k^Z. Предполагается, что первые два момента существуют и конечны: m = M[X(t)], a2 =M[X(t)-m\. Здесь М(-) - операция усреднения; m - первый центральный момент; сг - дисперсия процессаX(t). 7. Случайный процесс X(t) является точно самоподобным второго порядка с показателем Херста H (1/2 < H < 1), если ад=^((* + 1)“-2*“+(*-1>“) для Любых к > 1. Корреляционная функция агрегированного потока равна корреляционной функции исходного процесса, то есть R(m\k) = R{k) для любых т>1, где m - параметр агрегирования. Масштабная инвариантность определяется объединенным (агрегированным) процессом 1 mi = - £X(t)• т t-m(i-l)+l При исследовании сетей самоподобность второго порядка является основной структурой для описания сетевого трафика [1]. 8. Функция преобразования плотности вероятности интервалов времени между пакетами <р(х) - однозначная дифференцируемая функция, для которой известна и существует обратная функция х = у/{у) [8]. 9. При функциональных преобразованиях плотности вероятности интервалов времени между пакетами выполняется свойство инвариантности дифференциала вероятности, вероятности этих двух событий, они равны giy)dy = f (x)dx. 10. Для генерирования выборки случайных величин с функцией распределения F(y) обратная функция от интегральной функции распределения определяется формулой у = F~l(rnd), где rnd - случайная переменная, равномерно распределенная в интервале [0, 1. 11. Процесс преобразования плотности распределения вероятностей временных интервалов является дискретным и предполагает накопление пакетов в первой буферной памяти в нулевом цикле работы устройства преобразования и считывание накопленной информации по закону, формируемому вычислительным устройством в первом цикле работы устройства. Задержка процесса появления информации на выходе определяется временем накопления пакетов в буферной памяти. При таком построении процесса преобразования закон распределения временных интервалов выходной последовательности пакетов не зависит от закона входной последовательности и определяется законом, формируемым в вычислительном устройстве. Будем считать известной плотность вероятности у =flx) случайной величины X. Требуется найти плотность вероятности g(y) случайной величины Y, связанной с X функциональной зависимостью у = ф(х), где ф(х) - однозначная дифференцируемая функция, для которой известна и существует обратная функция х = Иу) [8]. Так как случайные величины x и у связаны однозначной дифференцируемой функциональной зависимостью, необходимо исходить из того факта, что полученные значения случайной величины X заключены в интервале [х ; х + dbc]. Отсюда следует, что величина у будет также находиться в интервале [у ; у + dy], где у = <р(х) ,ady = <p'(x)dx. Поскольку при этих условиях выполняется свойство инвариантности дифференциала вероятности [8], то вероятности этих двух событий равны g{y)dy = f(x)dx. Из формулы (1) следует, что . dx (1) g(y) = M- = fMy)] ■ У(у) • (2) dy Аналитические выражения функции у = f(x) с указанием области определения {х} играют ключевую роль при синтезе законов распределения случайных величин. Поэтому в классе дифференцируемых функций У = Ф) (3) необходимо определить такие функции, которые обеспечивали бы получение функций g(.y) с заданными характеристиками. При преобразованиях законов распределения трафика скорость передачи информации, доступная пользователю i-ой службы транспортной сети, является стохастической величиной. Следовательно, она представляет совокупность функций времени и имеет вероятностное описание. Соответствующими вероятностными характеристиками могут быть безусловные и совместные плотности вероятности случайных величин, яв «Инфокоммуникационные технологии» Том 12, № 1, 2014 34 Линец Г.И, Говорова С.В. ляющиеся точечными функциями процесса для фиксированных моментов времени. Причем полная их совокупность (например, битовая скорость передачи информации) представляет ансамбль, где любая его компонента есть выборочная функция случайного процесса At), отнесенная к конкретному сеансу [2]. td ti+T Рис. 1. Принцип преобразования битового потока в поток пакетов Значения ее реализации в некоторый момент времени ti определяют случайную величину При пакетной коммутации битовый поток преобразуется в дискретную последовательность пакетов, в общем случае переменной длительности (показаны штриховкой на рис. 1 [2; 4]. Для проведения количественного анализа ограничимся фиксированной длиной L пакета (например, ячейки АТМ - 53 байта). В этом случае структура трафика полностью описывается распределением длительности интервалов времени между передаваемыми пакетами [2; 6]. Длительность интервала т определяется временем накопления информации в буфере, рис. 2, достаточном для образования пакета заданной длины L0 [2; 6]: Ч-ri J r(t)dt =L0. (4) Битовый поток Память Пакеты (Lo) Т Рис. 2. Процесс преобразования битового потока в поток пакетов Левая часть формулы (4) является средним значением скорости передачи на интервале т, умноженном на длину этого интервала, то есть ср. ■r = L о > (5) где J ti+T rcp=~ J r(t)dt. При относительно малых значениях длины пакета L0 с небольшой погрешностью r можно заменить текущим значением скорости в интервале т, то есть гср = г- Это допущение дает возможность найти функциональную зависимость между случайными величинами ги г [2; 4]: т = LJr (6) и, следовательно, определить закон распределения g(t) непрерывной случайной величины т как функцию одного случайного аргумента r, если известен закон его распределения fr). Рассмотрим случай, когда исходная плотность вероятности описывает распределение мгновенных значений случайного процесса г(i), рис. 1. Случайная величина 0 связана с ней функциональной зависимостью (6) и определяет характер преобразования. Результатом преобразования является получение пакетов в накопителе, при этом случайная величина ® = т, где т - интервал времени между пакетами, является случайной величиной, и закон распределения величины т полностью описывает статистические свойства потока пакетов, так что Т = ф(г). (7) С учетом этого уточнения связь между мгновенными значениями случайного процесса r(t) и интервалом времени между образованными таким образом пакетами т перепишем в следующем виде ¥(*) О М= J/Mrfr, (8) а плотность распределения интервалов времени между пакетами определяется формулой g(r) = G'(T) = У(т) I • f[yr(r)]. (9) В (8) параметр а является нижним граничным параметром, определяемым из условия оо нормировки \g{x)dx = 1. Отличительной осоа бенностью зависимости между случайными величинами гиг является инвариантность по отношению к замене местами функции и аргумента (обратная пропорциональность). Выразим эту зависимость через обобщенные переменные у = к/X, что позволяет рассматривать закон распределения (9) как обратное преобразование: «Инфокоммуникационные технологии» Том 12, № 1, 2014 Линец Г.И, Говорова С.В. 35 f(x)=~g \х) л * (10) Доказательство существования связи между распределениями с «тяжелыми хвостами» и долговременной зависимостью Введем необходимые определения. Случайная переменная х имеет распределение с «тяжелым хвостом» [2], если вероятность Р[х>х0]~Сс0“,х -»°0, (11) где 0<а <2 - индекс хвоста или параметр формы; С - положительная константа. Таким образом, «хвост» затухает по гиперболическому закону. Воспользуемся (10) для вычисления вероятности (11) и согласно [2] получим д* > *0)=- Ы “Т dx. х (12) Произведем замену переменной в определенном интеграле - = y\dx =--\ dy. Тогда х у Уо P(x>x0) = +jf(y)dy. (13) Для вычисления интеграла (13) разложим функцию f(y) в ряд Тейлора в окрестности точки а (приу ^ да): f(y) = m + (y-d)f\a) и ограничимся первыми двумя членами (линейная аппроксимация). Тогда согласно [2] о о Р(х > х0) = - jДа) dy + J(j - а) /(а) dy = У О Уо = ~f(a)y + ^(y~af /'(а) У о Уо Полагая у0 = а = L0/x, получим P(x>x0) = f Переходя к более общей форме, можно утверждать, что х имеет распределение с «тяжелым хвостом», если Р(х > х0) = x~aL(x), где L(x) медленно изменяющаяся функция на бесконечности, для x > 0. Окончательное выражение для распределения с «тяжелым хвостом», полученное путем преобразования (12), имеет вид [2]: Р(х>х0) = х LJ rL Л 0 VXoy Характерная черта распределений с «тяжелыми хвостами» в том, что их дисперсия для 0<а<2 бесконечна, а при 0 < а < 1 распределения имеют бесконечное среднее значение. Расчеты показывают, что моментные функции любого порядка M(xs) = оо при S > а стремятся к бесконечности. В данном случае распределение «хвоста» с параметром формы а = 1 удовлетворяет условию (12). Согласно [2] M(xs) = | xs / (x)dx. (14) Для рассматриваемой плотности распределения g(r) - jfirr) и (13) принимает вид т 00 О Вычислив (15) по частям, получаем (15) M(ts) = L0‘ s-1 1 £---: i=1 ms-/) J=1 - -0-0 1) J ( O) I7(s - г) 0 <=i Для убывающей по экспоненциальному закону функции все члены под знаком суммы имеют нулевой предел, поэтому расходимость будет определяться интегралом [2]: (l Л 0 -=/ (L Л L х-1 ■^0 0 * Хе UoJ *0 UJ -Ат (О Вычисляя производные (г) для функции получим оо /(r) = A'(-l)'+1JV“VAr</r = О 00 2п Vй = вд+£(-1)*^-->®. ..1 пп\ «Инфокоммуникационные технологии» Том 12, № 1, 2014 36 Линец Г.И, Говорова С.В. Оценим условную вероятность того, что соединение будет существовать в будущем, поддерживая свою активность в течение заданного времени: L(t) = 1 - P(z = т) P(z < т) (16) Для «тяжелых хвостов» вычисления приводят к формуле [2]: L(r)=1_££2z£fct5ir=(^r, ст т + тп предел которого стремится к единице: т L(t) = lim(т + т0 Таким образом, чем больше период наблюдаемой активности, тем больше вероятность того, что соединение/сеанс будет существовать в будущем. Отсюда очевидно, что «тяжелые хвосты» приводят к предсказуемости и, следовательно, являются причиной долговременной зависимости в трафике ТС. Аналитическая модель функционального преобразования случайных самоподобных процессов При синтезе современных ТС возникает проблема оценки их производительности. Суть проблемы состоит в отсутствии аналитических моделей, адекватно описывающих особенности современного трафика, обладающего самоподобными и фрактальными свойствами. История развития теории синтеза сетей связи убедительно доказывает тот факт, что в настоящее время наиболее развитыми в аналитическом плане оказались сети связи, использующие экспоненциальный закон распределения интервалов времени между пакетами входящего трафика (пуассоновская модель), который играет исключительно важную роль и занимает особое место в теории массового обслуживания. Имеется развитый научно-методический аппарат (НМА), позволяющий исследовать вероятностно-временные характеристики экспоненциальных сетей. По этой причине целесообразно осуществлять преобразование любого известного потока требований ТС в экспоненциальный закон. Это позволит: применять для выбора требуемых характеристик информационного обмена НМА синтеза экспоненциальных сетей теории массового обслуживания и использовать его при исследовании самоподобных потоков; осуществлять преобразование самоподобного потока па кетов с целью устранения в нем долговременной зависимости, что позволит ослабить динамически возникающие перегрузки в каналах связи и повысить реальную производительность ТС. Рассмотрим присущие данному методу ограничения и допущения. Пусть случайный процесс *(0. имеющий отсчеты наблюдаемые в моменты времени tx,t2,t3,...,tn, подвергается целенаправленному функциональному преобразованию для получения требуемых характеристик. Тогда для исследования процесса преобразования случайного процесса в некоторый случайный процесс 7(0 используем следующую формальную запись [8] (19) Формула (19) означает, что каждой реализации случайного процесса £(t) по определенному правилу, определяемому оператором преобразования T, ставится в соответствие некоторая реализация случайного процесса rj(t) <^(0 есть случайный процесс на входе узла коммутации ТС, определяющий поступающий на обслуживание самоподобный поток пакетов, 7(0 - случайный процесс на выходе узла коммутации после целенаправленного преобразования, Т - конкретный вид оператора преобразования случайного процесса m в случайный процесс 7(0. Преобразования вида (19) могут быть линейными и нелинейными [9]. Среди нелинейных преобразований выделим два класса: безынерционные (функциональные) и инерционные преобразователи. В данном случае будем рассматривать только нелинейные безынерционные преобразователи, осуществляющие целенаправленное функциональное преобразование случайного потока пакетов £(t) в требуемый случайный поток 7(0 , обладающий заданными статистическими свойствами. Функциональность безынерционного преобразователя определим следующим образом. Пусть выходной процесс системы 7(0 связан с входным процессом m соотношением m=gm)\, где детерминированная функция g(x) не зависит от t и является функцией х, либо означает, что, при заданном t = t1 выходной процесс зависит только от £(tx) и не зависит от прошлых и будущих значений %(0. Такие преобразования будем называть функциональными. Поскольку функция g(x) не зависит явно от времени, выполняется условие: V(t + r) = g [£(* + *■)]. (20) «Инфокоммуникационные технологии» Том 12, № 1, 2014 Линец Г.И, Говорова С.В. 37 Системы, удовлетворяющие этому условию, называются стационарными (инвариантными во времени) [8]. Характеристики выходного процесса 7(0 , которые необходимо получить, определяются физическим содержанием решаемой задачи. В данном случае практический интерес представляют плотности распределения вероятностей, полученные в результате функционального преобразования входного процесса «W- Будем считать известной плотность вероятности у = fix) случайной величины X. Требуется найти плотность вероятности g(y) случайной величины Y, связанной с X функциональной зависимостью у = <р(х), где $>(jc) - однозначная дифференцируемая функция, для которой известна и существует обратная функция [8] вида х = Иу) = <Р~\х). Случайные величины X и Y связаны однозначной дифференцируемой функциональной зависимостью. Поэтому из факта, что полученные значения случайной величины X, заключенные в интервале [х, х + dx\, достоверно следует то, что случайные величины Y будут находиться в интервале \у, У + dy\, где у = (р{х), a dy = (p\x)dx. Для дальнейшего решения задачи используем следующую теорему [9]. Теорема. Дифференциал сложной функции У =Ли)> для которой и = g(x), имеет тот же вид dy =f(u)du, какой он имел бы, если бы промежуточный аргумент u был независимой переменной. Иначе говоря, форма дифференциала не зависит от того, является аргумент функции независимой переменной или функцией другого аргумента (свойство инвариантности формы дифференциала вероятности). Используя это свойство, можно утверждать, что вероятности этих двух событий равны [8; 10-11] g(y)dy = f(x)dx. (21) Из условия (17) следует, что [8, 11] «00= № = Л^Су)] • \v'(y)\ • (22) dy Плотности вероятности fix) и g(y) называются законами распределения случайных величин X и Y (дифференциальными законами), которые устанавливают связь между значениями этих величин и вероятностями их появления. Вероятность того, что случайная величина X примет значение, лежащее в интервале [x x2], в соответствии с теоремой сложения вероятностей опреде ляется площадью, ограниченной в этом интервале кривой f(x) и осью абсцисс, то есть [2] *2 Р(jc, < jc < х2) = | f(x)dx. Функция F(x), характеризующая вероятность того, что данная случайная величина X не превзойдет значения х, называется интегральной функцией (интегральным законом) распределения [2] X F{x) = Р(Х < х) = J f{x)dx. (23) -оо Модель преобразования случайных самоподобных процессов в закон распределения, имеющий равномерную плотностью вероятности Применяя свойство инвариантности дифференциала вероятности для входного потока пакетов и потока пакетов на выходе нелинейного безынерционного преобразователя, получим [11-12] fir^dr, = g(T2)dr2 (24) где г, - длительность интервала времени между пакетами входной последовательности £(t) ; т2 - длительность интервала времени между пакетами выходной последовательности 7(0; Ж) -плотность распределения вероятностей интервалов входной последовательности пакетов; g(T2) - плотность распределения вероятностей интервалов выходной последовательности пакетов. Закон преобразования т2= (р (гх) является однозначной дифференцируемой функцией, определяемой из решения дифференциального уравнения (24) [12]. Он обеспечивает получение импульсной последовательности g(r2), после чего пакеты выходного потока рассылают по виртуальному каналу в режиме коммутации пакетов. В пакетных сетях распределение длительности интервалов между пакетами при постоянной длине каждого пакета полностью описывает статистические свойства потока пакетов [12]. Условие (24) определяет равенство интегральных функций распределения исходного и конечного процессов [11-12]: F(t1) = G(t2). (25) Из уравнения (25) находим заданный закон преобразования т2 = 9(? i)> в случае когда решение относительно одной из переменных находится в явном виде. Это требование касается и второй переменной, так как должна «Инфокоммуникационные технологии» Том 12, № 1, 2014 38 Линец Г.И, Говорова С.В. существовать однозначная обратная функция h =^(^2)’где v = ^_1[8; п-12]. Рассмотрим преобразование, представляющее практический интерес [12]. Пусть непрерывная случайная величина Тх с функцией распределения F(Tj) подвергается преобразованию Ъ =Фг) так, чтобы в результате преобразования получился закон распределения с равномерной плотностью вероятности [11-12]: г2 ~Д Ъ-а = F(rl). Искомая функция преобразования [12] г2 - a +(b-a)F(T1). (26) (27) Действительно, для предельно возможных значений случайной величины -со<т1 < оо выполняется равенство F(-oo) = 0, F(+oo) = 1, тогда по условию (25) все значения т будут заключены в интервале [а, b]: f(ji) = g(j2) dr2 drx (28) Дифференцируя (27) по xx, получим dr. drj 2 _ = (6-a)F(r1) = (6-a)/(r1). (29) Подставив (29) в (28), получим [12] Таблица 1. Функциональные преобразование законов Парето и Вейбулла Исходный закон распределения Функция преобразования ср{тх) Закон распределения интервалов пакетов Парето Экспоненциальный . а-ка §(ri) = <z+T а, к -In- к тх f(r2) = Ле т\х>0 Вейбулла Экспоненциальный g(ri) = а- Ртхрле~ат' ат; {(т2) = Ле' Т2,х>0 Парето Равномерный /л а'ка B(h) = -r f(x) = 1, р < X < 1 О, х < 0, х > 1 Вейбулла Равномерный g(Tl) = a-fizf'le~aTl‘ f(x) = \,р < х < 1 О, д; < 0, jc > 1 «Инфокоммуникационные технологии» Том 12, № 1, 2014 Линец Г.И, Говорова С.В. 39 g(r2) = -а<т2<Ь. о -а Следовательно, всякая непрерывная плотность вероятности интервалов входной последовательности пакетов может быть преобразована в равномерную последовательность. Полученный путем функционального преобразования произвольного закона распределения плотности вероятности закон с равномерной плотностью, по-видимому, является наилучшим распределением, поскольку позволяет равномерно заполнить среду передачи пакетами [12]. Однако ввиду отсутствия методик расчета сетей связи, находящихся под воздействием трафика, распределенного по закону с равномерной плотностью, заслуживает внимания вопрос о преобразовании произвольного закона распределения (аналитически заданного) в пуассоновский (экспоненциальный характер распределения длительности интервалов между пакетами), для которого такие методики существуют Модель преобразования самоподобного потока в пуассоновский поток пакетов Пусть непрерывная случайная величина с плотностью распределения подвергается преобразованию т2 = $> (z^ ). Необходимо выбрать функцию (р, такую, чтобы в результате преобразования получился закон распределения [11-12] £(г2) = Яе^2, (30) где Т2 - длительность интервала между пакетами. Согласно (25) функции распределения должны быть равны, то есть F(t1) = G(t2). (31) Отсюда [11] т2 =-\ln[l-F(Ti)\. (32) Л Решая (32) относительно т2, получим F(t1) = 1-е-Ятг. Дифференцируя (32) по тх, получим [11] dr2 1 F'jrJ 1 /(г,) (33) dr, Л1 -F(tx) Л l-F(rj) ( ) Подставив (33) в (24), окончательно получим конечную формулу (30), найденную в результате преобразования (25). Разработанная модель преобразования самоподобного потока в пуассоновский поток пакетов положена в основу изобретения [12], где объектом преобразования является одномерная плотность распределения интервалов времени между пакетами для сообщений, длина которых меньше порогового значения. За счет использования данных преобразований увеличивается производительность и эффективность использования сетевых ресурсов. Пример. В качестве примера рассмотрим преобразования по формуле (24) двух исходных законов распределений Парето и Вейбулла, имеющих «тяжелые хвосты» (первая графа таблицы 1) - в экспоненциальный и равномерный законы соответственно таблице 1 [11]. Выводы 1. Ввиду того, что транспортные сети относятся к распределенным структурам с промежуточным накоплением, долговременная зависимость, а следовательно и самоподобность, возникают в процессе преобразования битового потока в поток пакетов. 2. Выдвинуто предположение, что преобразование битового потока в поток пакетов сопровождается появлением распределений с «тяжелыми хвостами», которые возникают независимо от того, какой закон распределения вероятностей имеет исходный преобразуемый битовый поток. Наличие «тяжелых хвостов» является причиной долговременной зависимости в трафике транспортных сетей. 3. Сформулировано условие, что статистические свойства потока пакетов полностью определяются распределением интервалов времени между пакетами. <0 36(17 О1 V Экспоненциальный Вейбулла б) / 3607 Повышение производительности в 18 раз 192 Экспоненциальный Парето Рис. 3. Верхние оценки производительности при преобразовании в экспоненциальный закон законов: а) Вейбулла; б) Парето «Инфокоммуникационные технологии» Том 12, № 1, 2014 40 Линец Г.И, Говорова С.В. 4. Для повышения производительности транспортных сетей применен метод функциональных преобразований плотности распределения интервалов времени между пакетами, основанный на свойствах инвариантности формы дифференциала вероятности и независимости переменных х и у. 5. Получены преобразования плотности распределения интервалов времени между пакетами самоподобного трафика в пуассоновский закон. 6. Разработана аналитическая модель преобразования плотности распределения битового потока в поток пакетов, позволяющая осуществлять преобразование одного закона распределения в любой другой. 7. Получена модель формирования самоподобного трафика, позволяющая получать последовательность пакетов с заданными свойствами, которая может использоваться при моделировании самоподобного трафика при проектировании ТС. 8. Проведенные исследования показали, что на основе разработанного НМА возможно осуществить повышение производительности ТС за счет применения функциональных преобразований и использования свойств экспоненциальных сетей. На рис. 3 представлен пример верхних оценок производительности при преобразовании законов Вейбулла и Парето в экспоненциальный закон. 9. С целью ослабления влияния самоподобных свойств трафика на производительность ТС в [12] предложен способ снижения влияния само-подобности в сетевых структурах и устройство для его осуществления.

About the authors

G. I Linets

Email: kbytw@mail.ru

C. V Govorova

Email: mitnik2@yandex.ru

References

Supplementary files