WAITING TIME ANALYSIS FOR G/G/1 QUEUE

Full Text

Введение В телекоммуникационном оборудовании аналитическое исследование и расчет статистических параметров трафика, дает возможность приблизиться к определению пропускной способности сети, оптимального размера буфера. Для решения задач, в которых существуют случайные события, используются как аналитические, так и имитационные модели. Зачастую аналитические модели предпочтительнее имитационных по нескольким причинам: не требуется проведения большого числа испытаний; можно получить оптимальное решение. Традиционная теория очередей посвящена очередям, где время между прибытием и время обслуживания являются независимыми процессами обновления. Есть предположение о том, что время обслуживания потока пакетов взаимно независимые, а соответствующее предположение о независимости потока пакетов от интервалов между прибытиями, часто неоправданно - следовательно, необходимо учитывать при моделировании СМО G/G/1 свойство самоподобия данных процессов, Изучение очередей с зависимыми процессами прибытия является актуальным и имеет практическую ценность. Можно сделать вывод: точные решения (аналитические или численные) обычно недоступны для очереди G/G/1, так как исследователи прибегают к моделированию Монте-Карло или используют классическую теорию Маркова и ее вариации для проведения параметрического анализа по средней длине очереди [1]. Корреляции в прибывающем потоке событий, в предположении очереди на один сервер, существенно влияют на среднее время ожидания по сравнению с соответствующим потоком событий, приходящих повторно, тому же серверу. Однако если использовать такие модели СМО G/G/1, для которых созданы и построены реальные или максимально приближенные к действительности аппроксимации распределений интервалов времени между пакетами и длительной обслуживания для очередей с коррелированными поступлениями [2] становится возможным поиск решения неизвестных средних характеристик трафика. В основном используются распределения с «тяжелым» хвостом Парето и Вейбулла для построения процесса прибывающего потока пакетов и определения среднего времени ожидания пакета в очереди, учитывая его скорость, коэффициент вариации и другие характеристики. Исследование, проведенное относительно распределения времени между пакетами, описываемых распределениями с «тяжелым» хвостом Вейбулла, Парето показало, что его можно использовать для аналитического определения параметров трафика [3-4]. Применение распределений с «тяжелым» хвостом наилучшим образом приближенны к функциям распределений, описывающих статистические характеристики трафика. Определяя преобразования Лапласа законов распределений, которым подчиняются интервалы времени между пакетами и длительности пакетов, и, используя спектральный метод решения интегрального уравнения (ИУ) Линдли, можно найти функцию времени ожидания пакетов в очереди. Определение данной сетевой характеристики позволяет повысить качество обслуживания при конфигурации сети и проследить изменчивый характер трафика, учесть его свойства, чтобы, в свою очередь, наиболее точно оценить параметры сети. Предложенный в [5] метод аппроксимации распределения суммой затухающих экспонент дает неудовлетворительные результаты по точности на «восходящих» ветвях распределений. Кроме того, аппроксимация «восходящих» ветвей распределений приводит к появлению в сумме затухающих экспонент слагаемых с отрицательными коэффициентами, что нивелирует вычислительные преимущества спектрального метода, обусловленные использованием гиперэкспоненциальных распределений. Анализ времени ожидания в очередях СМО G/G/1 с использованием приближения PMRQ аппроксимации Ряд исследований подтвердило теоретические расчеты - продемонстрировав влияние автокорреляций в процессах прибытия (или сервисных процессах) на статистику очередей в связанных очередях по сравнению с их аналогами обновления [1; 5-6]. В более общем случае, если данные о статистических параметрах доступны, то методы, рассмотренные и проанализированные в этом исследовании, могут быть использованы для получения среднего времени ожидания. Для исследования произвели анализ результатов, полученных в работе [7]. Идея данной работы заключается в сравнении результатов аппроксимации способами PMRQ и PMRS при сопоставлении СМО G/G/1 аппроксимирующей GI/G/1 [7] и аппроксимации суммой затухающих экспонент [5, 6] при одних и тех же параметрах сети смоделированными и приближенными к реальным значениям. Предложенная схема аппроксимации, представленная в работе [7], которая сопоставляет G/G/1 аппроксимирующей GI/G/1 PMRQ (Peakedness Matched Renewal Queue) использует аппроксимации потока распределения услуг в пиковом режиме, которые имеют названия PMRS (Peakedness Matched Renewal Stream). Приближенный процесс прибытия PMRS сохраняет пиковость исходного процесса прибытия и его скорость прибытия; кроме того, квадратный коэффициент вариации построенного процесса прибытия PMRS равен индексу дисперсии исходного процесса прибытия. Заслуга приближения PMRQ заключается в том, что он легко разрешим, в отличие от первоначальной очереди G/G/1. Для этого в работе [7] используется функция меры остроты пика [8], а отставание - коэффициентом автокорреляции в исходном потоке. Приближение PMRQ аппроксимации способом для поиска среднего времени ожидания в схеме TES+/G/1 (Transform Expand Sample) лучше по сравнению со ссылочными значениями, полученными с помощью моделирования, где простой вариант процессов прибытия TES+ служил процессом прибытия, связанным с автокором [9-10]. Рассмотрение универсальных классов автокорреляционных (лопастных) стохастических процессов, называемых TES+ [9-10] впоследствии служат процессами прибытия в очереди G/G/1, результирующая TES+/G/1 это проверка эффективности среднего времени ожидания приближения, предложенного в работе [7]. При рассмотрении данной модели одновременно подбирается маргинальное распределение и корреляционная функция. Целью при аппроксимации PMRQ и PMRS является построение модели, соответствующей трем требованиям одновременно: маргинальное распределение должно соответствовать ее оригиналу (гистограмме); основные корреляционные модели должны приближаться к оригиналам до приемлемой задержки; выборки, сгенерированные моделью, должны «иметь сходство» с опытными временными сериями. Интересное приближение PMRS возможно следующим образом. Можно показать [8], что пиковая функция любого возобновляемого потока трафика имеет представление (1) где - преобразование Лапласа плотности временного интервала между временем и . Из (1) следует, что для общего движения процесса соответствующее PMRS аппроксимирующего процесс обновления полностью определяется через преобразование Лапласа от его плотности временного интервала между временем вида (2) Уравнение (2) фактически подразумевает, что . Обоснование аппроксимации PMRS очевидно: в целом аналитически проще, чем - факт, который будет использоваться позже в приблизительном анализе очереди G/G/1. Более конкретно, PMRQ аппроксимации очереди G/G/1 общего процесса является просто соответствующей очереди GI/G/1 с обновлением предлагаемого трафику процесс , где - PMRS аппроксимации . Поэтому трафик рассматривается как пульсирующий процесс времени [11], имеющий описания и свойства процессов TES [9]. Процессы TES представляют собой универсальный класс стационарных временных рядов, допускающих любое предельное распределение, большое разнообразие автокорреляционных функций (монотонность, колебание, чередование и др.), и широкий спектр поведения, в том числе направленных и ненаправленных процессов. Процессы TES могут быть разработаны, чтобы соответствовать любому эмпирическому (маргинальному) распределению, и одновременно приближенных эмпирических автокорреляционных функций различных функциональных форм. В частности, можно определить TES процессы с различными автокорреляционными функциями, тем самым контролируя (оценивая) их степень. Решение статистики равновесного времени ожидания в очереди GI/G/1 обычно требует сложной расчетной процедуры. Для нахождения функции времени ожидания (3) необходимо воспользоваться обратным преобразованием Лапласа функции посредством интегрирования, учитывая, свойства дельта-функции [1] (например, ИУ Линдли для частного случая) (3) Для оценки параметров приближенного среднего времени ожидания в качестве альтернативы вычислению среднего времени ожидания рассматривается приближение большого трафика. Из работы [7] когда GI/G/1 имеем очередь при большом трафике, а именно аппроксимация среднего времени ожидания (4) (4) где - коэффициенты вариации интервалов поступления времени и времени обслуживания соответственно [12]. В [7] исследована эффективность предлагаемого приближения путем сравнения с моделированием. Проведено сравнение точности аппроксимации двумя способами: масштабный метод усреднения и аппроксимация , изменялись три типа параметров в системе TES+/G/1. Рассмотрены частоты поступления со значениями и Данные частоты соответствуют средней загрузке и тяжелой загрузке системы, соответственно, поскольку среднее значение службы всегда было равным единице. Параметр пачечности должен быть различен по диапазону значений надлежащим выбором параметров . Значения определяют сильный эффект пачечности, в то время как имеет вторичный эффект. В результате рассмотрены четыре среднесрочных распределения времени обслуживания: Exponential, Erlang, Deterministic, MCE2 и MMPP (Markov-modulated Poisson processes) [7], где получены результаты для среднего времени ожидания СМО TES+/G/1. Аппроксимация в виде суммы затухающих экспонент Анализ сетевого трафика проводился с использованием сети связи, в которой при передаче в глобальную сеть через коммутатор были получены данные, имеющие один Uplink. Пропускная способность абонентского канала изменялась с помощью программного обеспечения коммутатора, а порт, являющийся пограничным для этого коммутатора, имел конфигурацию зеркалирования, что позволяло производить захват всего трафика, проходящего в глобальную сеть. Uplink к узлу агрегации был занижен по скорости, а именно скорость передачи была ограничена до 60 и 80 Мбит/с. Основываясь на имеющихся исследованиях трафика при загрузках со значениями и , и полученных распределений согласно их гистограмме, были рассмотрены случаи системы СМО G/G/1: система типа P/W/1 и W/P/1, где символы и означают соответственно распределения Парето и Вейбулла. Распределение Парето и Вейбулла, соответственно, имеют вид: ; (5) , (6) где - параметр формы; - масштабный параметр. Уравнение Линдли имеет следующий общий вид [1]: , (7) где - функция распределения времени ожидания требования в очереди; - ядро, связывающее произвольную функцию распределения вероятностей интервалов времени между поступлениями соседних требований и произвольную функцию распределения длительности обслуживания требований . Заметим, что само ИУ Линдли выведено в предположении независимости элементов последовательности интервалов времени между заявками и интервалов времени обработки заявок. Известно, что для СМО G/G/1 возможен спектральный метод решения ИУ Линдли, если для плотностей вероятностей и , соответствующих распределениям и использовать аппроксимацию в виде суммы затухающих экспонент [3-4]. При этом и имеют представления, соответственно: (8) (9) где . Среднее время ожидания пакета в очереди для вышеприведенных примеров находится согласно известному свойству характеристической функции (10) По результатам моделирования была проведена проверка соответствия параметров генерируемого узлом-отправителем потока заданным параметрам с использованием программы EasyFit. Рассматривался случай с частотой поступления или интенсивностью . Данная частота соответствуют средней загрузке системы, соответственно, поскольку среднее значение интенсивности обслуживания всегда равно единице. При рассмотрении СМО TES+/G/1 (распределение интервалов времени между поступления TES+ и длительностей обслуживания MGE2) с параметрами: ; После вычисления по масштабному методу усреднения и аппроксимация , среднее время ожидания пакета получилось равным Если рассмотреть при той же средней загрузке полученные гистограммы статистических параметров снятого трафика (см. рисунок 1) имеем соответствие системе W/P/1. Интервалы времени между пакетами распределены по закону Вейбулла с параметрами: а для длин пакетов распределением Парето с параметрами После аппроксимации распределений СМО W/P/1 в виде суммы затухающих экспонент для поиска решения ИУ Линдли среднее время ожидания пакета получилось равным Рассмотрен случай при пиковой загрузке системы при интенсивности СМО TES+/G/1 (MMPP (Markov-modulated Poisson processes)) [7], где получены результаты для среднего времени ожидания. СМО MMPP с параметрами: После вычисления по масштабному методу усреднения и аппроксимации (7), среднее время ожидания пакета получилось равным Далее (11) где - вектор от ; ; ; ; находятся из алгоритма [13]. Если рассмотреть при том же значении загрузки полученные гистограммы статистических параметров снятого трафика (рис.1) имеем соответствие системе W/P/1. Интервалы времени между пакетами распределены по закону Вейбулла с параметрами: , а для длин пакетов распределением Парето с параметры: После аппроксимации распределений СМО W/P/1 в виде суммы затухающих экспонент для поиска решения ИУ Линдли среднее время ожидания пакета получилось равным Заключение В статье представлены методики определения среднего времени ожидания в очереди СМО G/G/1: масштабный метод усреднения и аппроксимация , а также аппроксимацию в виде суммы затухающих экспонент для поиска решения ИУ Линдли. При этом в качестве модуля транспортного уровня выбран модуль TCP, а интенсивность поступления пакетов равна и Погрешность решения ИУ Линдли спектральным методом в сравнении с результатами [7] составляет при порядка 4%, а при - до 14%, что вполне приемлемо. Такая погрешность может быть связана с идеализацией исходных распределений временных параметров рассматриваемых моделей, с допущением независимости элементов рассматриваемых последовательностей интервалов времени и с определенными точностями, характерными для любой используемой программы при снятии и обработки сетевого трафика. Захват трафика осуществлялся с помощью программы анализатора трафика Wireshark. Распределения временных параметров были получены в программе анализа данных EasyFit, разработанной для быстрого анализа статистических данных и принятия решения. Проведенное сравнение методов аппроксимации сетевого трафика позволяет оценить среднее время ожидание пакета с использованием статистического анализа данных, что даст возможность повысить качество обслуживания и спрогнозировать поведение трафика.

About the authors

Olga Aleksandrovna Karaulova

Povolzhskiy State University of Telecommunications and Informatics

Email: Olya4369@yandex.ru

Natalia Valerievna Kireeva

Povolzhskiy State University of Telecommunications and Informatics

Email: zeppelinSN@yandex.ru

Liliya Ravilevna Chupakhina

Povolzhskiy State University of Telecommunications and Informatics

Email: garip4ik555@mail.ru

References

Supplementary files