SELF-SIMILAR TRAFFIC ASYNCHRONOUS CONVERSION SIMULATION IN SWITCHING NODES USING QUEUES

Full Text

Одной из проблем транспортных телекоммуникационных сетей является эффективное использование узловых и канальных ресурсов при обслуживании самоподобного трафика. Ее реше ние требует разработки новых методов, позволяющих повысить производительность за счет оптимизации сетевых ресурсов. Анализ используемых моделей трафика современных и перспективных сетей для определения вероятностно-временных характеристик информационного обмена пользователей позволяет сделать вывод о том, что использование пуассоновских моделей во многих случаях ведет к недооценке нагрузки и, как следствие, к невозможности обеспечения требуемых показателей качества информационного обмена Qos [1-3]. Это вызвано тем, что свойства компьютерного и голосового трафика имеют существенные отличия, основными из которых является наличие «долгой памяти» у распределений длин периодов занятости компьютерного трафика, имеющих «тяжелые хвосты» и достаточно хорошо характеризующихся показателем Херста Н. Н. Н Важным параметром информационного обмена, влияющим на качество обслуживания пользователей, а также на производительность сети является вероятность потери сообщений за счет переполнения буферных запоминающих устройств (БЗУ) в узлах коммутации. В настоящее время системам массового обслуживания (СМО) с самоподобным трафиком уделяется достаточно пристальное внимание [2; 4-7]. Однако полученные результаты не позволяют охватить всего многообразия свойств трафика современных приложений. В ряде работ показано [1; 7-9], что явление самоподобия в современных сетях проявляется асимптотически на больших временных интервалах и зависит от различных причин, одна из которых состоит в том, что используемые технологии обработки информации предполагают передачу по одному каналу трафика с разными требованиями к параметрам производительности. Вследствие этого в его свойствах проявляются фрактальность и неоднородность. В [10; 11] сделан вывод о том, что с увеличением самоподобия необходимо увеличивать объем буфера для снижения вероятности потери пакетов. Однако необоснованное увеличение буферного пространства приводит к снижению качества информационного обмена пользователей, например, к увеличению средней задержки. В статье представлена имитационная модель асинхронного преобразования самоподобного трафика в узлах коммутации, в основе которой используется паттерн «производитель-потребитель» с ограниченным буфером. Определена нижняя граница объема буферной памяти в зависимости от степени самоподобия входного трафика Н, когда вероятность потери сообщений Н, когда вероятность потери сообщений Н равна нулю. Анализ состояния проблемы В реальных транспортных сетях входной буфер имеет ограничение на объем хранимых дан ных. При поступлении большого числа пакетов на вход системы может возникнуть блокировка, то есть отказ поступивших на обслуживание пакетов, которые в результате оказываются потерянными. Количество потерянных пакетов является показателем оценки качества обслуживания. Во многих работах исследованы вопросы повышения производительности вычислительных систем и сетей и предложены модели решения данной проблемы. Л. Клейнроком впервые была решена задача определения оптимальных пропускных способностей, в которой использовалась СМО с бесконечным буфером [6]. Большинство известных моделей используют данный подход. Известна работа [10], в которой предлагается подход к определению размеров буфера данных для мультимедийных приложений при переменной пропускной способности канала передачи данных. В [11] представлены модели расчета показателей Qos в сетях следующего поколения, основное внимание уделено свойствам трафика IP-ориентированных мультисервисных сетей и влияния оконечных устройств на основные показатели качества обслуживания - задержек и потерь. Однако эффективного способа получения высокой производительности сети при обслуживании самоподобного трафика и удовлетворения требований Qos в данных работах предложено не было. В [1-3] рассмотрены вопросы оптимизации объема буферной памяти узлов коммутации при передаче самоподобного трафика, представлена структурная схема устройства для преобразования входного трафика, позволяющего проводить преобразования произвольного закона распределения интервалов времени между пакетами в пуассоновский закон. Недостатком данной модели является наличие двух элементов буферной памяти, которые обеспечивают циклический характер функциональных преобразований входного самоподобного потока пакетов. Постановка задачи С целью повышения производительности современных информационно-вычислительных сетей требуется разработать имитационную модель, обеспечивающую преобразование входного потока пакетов 1 ( ),G τ который является заведомо самоподобным, в заданный закон распределения 2 ( ),G τ в частности, в пуассоновский. Объектом преобразования является одномерная плотность распределения интервалов времени между пакетами входного потока 1 ( ).G τ Сформулируем требования к имитационной модели, которая должна определять: - влияние размера буфера М на производиМ на производиМ тельность сети; - величину потерь пакетов в зависимости от размера очереди; - влияние размера очереди на число обработанных пакетов; - зависимость числа потерянных пакетов от времени при различных показателях Херста Н. Н. Н В качестве ограничивающих требований к имитационной модели определим: - конечный размер буфера узла коммутации М; М; М - буфер работает по принципу FIFO. Требуется определить: - величину потерь пакетов в зависимости от размера очереди и заданном показателе Херста; - производительность сети от размера используемого буфера при обслуживании самоподобного трафика; - величину потерь пакетов во времени при фиксированных значениях объема буфера и показателя Херста; - размер буфера (нижнюю границу), учитывающий показатель Херста, в случае обслуживания входного потока без потерь. Решение задачи Основу имитационной модели составляет паттерн producer-consumer, который используется в многопоточном программировании. Его смысл состоит в том, что один или несколько потоков «производят» данные, и параллельно этому один или несколько потоков «потребляют» их. Производящий поток называется «производитель», «поставщик» или «producer», потребляющий - «потребитель» или «consumer». Нетривиальность проблемы заключается в том, что потенциально как создание новых данных, так и их потребление может занимать длительное время. Исходя из условий решаемой задачи требуется, чтобы обработка данных происходила с максимально возможной скоростью. Очевидно, что отношения «производитель-потребитель» подразумевают наличие одностороннего канала связи, по которому могут передаваться порции информации (пакеты). С этой целью процессы связаны через буфер. Произведенные порции информации не потребляются немедленно, а должны иметь возможность организовывать в буфере очередь. Буфер работает по принципу FIFO. Задача «производитель-потребитель» заключается в обеспечении согласованного доступа входного и выходного потоков пакетов к разделяемому буферу. Корректное решение обработки данных должно удовлетворять следующим условиям [12]: - входной и выходной потоки выполняются асинхронно; - потоки должны завершать работу в течение конечного времени; Рисунок 1. Структурная схема модели для преобразования трафика - потоки должны корректно использовать операции с конечным буфером. В варианте, представленном в статье, используется буфер ограниченного размера. В качестве «производителя» используется входной самоподобный поток пакетов 0 ) 5,( , H > а в качестве «потребителя» - выходной поток пакетов, у которого плотность распределения интервалов времени между пакетами распределена по экспоненциальному закону. Входной и выходной потоки сопоставлены между собой по величине математического ожидания. Структурная схема модели для преобразования трафика показана на рисунке 1. Для реализации имитационной модели использован язык Python 3.7, а также пакеты NumPy, SciPy, Matplotlib. В качестве инструмента для создания аналитических отчетов использован Jupyter Notebook, позволяющий совместно сохранять код программы, изображения, комментарии, формулы и графики [3]. Получено свидетельство о государственной регистрации программы для ЭВМ [13]. Имитационная модель реализует следующие действия. 1. Создание объекта. Описание случайной переменной, значения которой распределены по заданному закону (в нашем случае - это закон Парето). Таблица 1. Статистические характеристики потоков пакетов имитационной модели Показатель Херста H Статистические характеристики Входной поток Управляющий поток Поток «производителя» Поток «потребителя» МО МО D МО D Kоэфф. вариации МО D Kоэфф. вариации 0,6 2,25 2,25 5,06 2,11 2.04 0,97 2,38 2,39 1,00 0,8 3,50 3,50 12,25 2,89 4.50 1,55 3,72 3,74 1,00 0,95 10,99 10,99 120,99 4,65 12.15 2,60 11,81 11,35 0,96 Рисунок 2. Диаграмма последовательностей модели преобразования входного потока в выходной поток пакетов 2. Формирование последовательности распределения интервалов времени между пакетами по закону Парето с помощью модуля Stats пакета SciPy, который предоставляет данные для генерации случайных чисел и последовательностей. С этой целью для случайной величины задается значение показателя Херста Н и порождающее Н и порождающее Н значение генератора случайных чисел. 3. Расчет математического ожидания (MO) случайной переменной, распределенной по закону Парето (см. таблицу 1). 4. Создание объекта. В качестве управляющего потока требуется получить экспоненциальный поток пакетов с МО, равным МО потока пакетов, распределенному по закону Парето. Управляющая последовательность формируется с помощью тех же средств, что и для входного потока. 5. Расчет статистических характеристик значений случайной переменной, распределенной по экспоненциальному закону: МО и дисперсии D, см. таблицу 1. 6. Задание числа генерируемых пакетов N и N и N максимального количества пакетов в очереди M. M. M 7. Моделирование процесса преобразования потока пакетов средствами асинхронного программирования. 8. Определение сопроцедур «производитель» и «потребитель» для запуска в цикле обработки событий. 9. Запуск симуляции процесса преобразования потока пакетов. Диаграмма последовательности, описывающая работу разработанной модели, представлена на рисунке 2. Объектами имитационной модели являются: - Event Loop - цикл обработки событий; - producer_task - задача производителя, добавляемая в буфер в цикле обработки событий; Рисунок 3. Зависимость математического ожидания входного потока от показателя Херста Н Рисунок 4. Зависимость коэффициентов вариации Квар Квар К «производителя» и «потребителя» от Н Рисунок 5. Величина потерь пакетов в зависимости от: а - размера очереди М; М; М б - показателя Херста б - показателя Херста б Н а б Рисунок 6. Производительность сети от: а - размера очереди М (используемого буфера); М (используемого буфера); М б - показателя Херста б - показателя Херста б Н а б Рисунок 7. Число потерянных пакетов во времени при фиксированных значениях буфера ( 10; M = 50; M = 0) 10M = и показателя Херста: а - 0,6; H = б - 0,8; H = в - 0,95 H = а б в Рисунок 8. Число потерянных пакетов во времени при фиксированных значениях показателя Херста ( 0,6; H = 0,8; H = 0,95) H = и объема буфера а - 10; M = б - 50; M = в - 100 M = а б в Рисунок 9. Число пакетов в очереди при фиксированных значениях показателя Херста ( 0,6; H = 0,8; H = 0,95) H = и объема буфера а - 10; M = б - 50; M = в - 100 Рисунок 10. Число пакетов в очереди при фиксированных значениях показателя Херста Н и объема буфера М: М: М а - 10; M = 0,6; H = б - 50; M = 0,6; H = в - 10; M = 0,8;H = г - 50; M = 0,8; H = д - 10; M = 0,95; H = е - 50; M = 0,95 H = а б в г д е Рисунок 11. Число пакетов в очереди при фиксированных значениях показателя Херста Н и объема буфера М: М: М а - 100; M = 0,6; H = б - 100; M = 0,8; H = в - 100; M = 0,95 Таблица 2. Размер буфера при обслуживании входного самоподобного потока без потерь Показатель Херста Н 0,55 0,6 0,65 0,7 0,75 0,8 0,85 0,9 0,95 Размер буфера М 115 126 139 160 186 221 299 407 609 - producer - производитель (входной поток пакетов); - input_generator - генератор интервалов времени поступления пакетов входного потока; - consumer_task - задача потребителя изымаемая из буфера в цикле обработки событий; - consumer - потребитель (выходной поток пакетов); - output_generator - генератор интервалов времени поступления пакетов выходного потока; - queue - очередь. В таблице 1 и на рисунках 3-11 представлены результаты применения имитационной модели для анализа показателей качества информационного обмена при следующих исходных данных: - входной поток пакетов 1000; N = - размер буфера 10, M = 50, 100; - распределение интервалов времени между пакетами по закону Парето; - обслуживание потока пакетов реализовано по принципу FIFO. Выходные данные: - величина потерь пакетов в зависимости от размера очереди при показателе Херста Н; Н; Н - производительность сети в зависимости от размера используемого буфера М; - величина потерь пакетов во времени при фиксированных значениях объема буфера и показателя Херста Н; Н; Н - размер буфера, учитывающий показатель Херста Н, в случае обслуживания входного потоН, в случае обслуживания входного потоН ка без потерь. В таблице 2 и на рисунке 12 представлены значения объема буфера (нижняя граница) для случая обслуживания входного самоподобного потока пакетов без потерь. Выводы Исходя из результатов моделирования, которые представлены на рисунках 3-12 и в таблицах 1, 2, можно сделать следующие выводы. 1. При фиксированном объеме буферной памяти величина потерь пакетов возрастает с увеличением показателя Херста Н. Н. Н 2. С увеличением объема буферной памяти доля успешно обработанных пакетов (производительность) увеличивается в случае фиксированного значения показателя Херста Н. Н. Н 3. При увеличении показателя Херста Н проН проН изводительность сети резко снижается, причем, чем выше показатель Херста, тем меньше производительность сети. 4. Анализ числа потерянных пакетов во времени показал, что чем больше объем буфера и меньше показатель Херста, тем меньше потери пакетов. 5. При фиксированном объеме буфера количество пакетов в очереди тем выше, чем больше показатель Херста. 6. Определена нижняя граница размера буфера М при обслуживании входного самоподобного М при обслуживании входного самоподобного М потока при различных показателях Херста в случае отсутствия потери пакетов. 7. Для случая обслуживания входного самоподобного потока пакетов без потерь при увеличении показателя Херста Н объем буферной памяН объем буферной памяН ти возрастает по экспоненциальному закону (см. рисунок 10), что для практики ее использования является неприемлемым ввиду возрастания средней задержки. Исходя из проведенных исследований можно сделать следущий вывод: при обслуживании самоподобного потока пакетов требуется одновременное управление объемом буферной памяти и пропускной способностью узлов коммутации для удовлетворения требуемых показателей качества информационного обмена Qos пользователей сети. Рисунок 12. Размер буфера, учитывающий показатель Херста, в случае обслуживания входного потока без потерь Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 19-07-00856/19.

About the authors

G. I Linets

North-Caucasus Federal University

Stavropol, Russian Federation

V. P Mochalov

North-Caucasus Federal University

Stavropol, Russian Federation

S. V Govorova

North-Caucasus Federal University

Stavropol, Russian Federation

R. A Voronkin

North-Caucasus Federal University

Stavropol, Russian Federation

References

Supplementary files