Регистрация / Вход
Прислать материал

МЕТОДЫ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ФРАКТАЛЬНЫМИ ОЧЕРЕДЯМИ

Сведения об участнике
ФИО
Захаренкова Татьяна Романовна
Вуз
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Омский государственный технический университет»
Тезисы (информация о проекте)
Область наук
Информационные технологии и вычислительные системы
Раздел области наук
Информационные технологии
Тема
МЕТОДЫ МОДЕЛИРОВАНИЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ФРАКТАЛЬНЫМИ ОЧЕРЕДЯМИ
Резюме
Рассматриваются проблемы организации имитационных экспериментов при расчете фрактальных систем с очередями. Фрактальные системы описываются асимптотически степенными законами распределения интервалов поступления и времени обслуживания заявок и являются адекватными математическими моделями сетевых устройств телекоммуникационных систем с фрактальным трафиком. Предлагается решение проблемы корректной реализации распределений с тяжелыми хвостами. Разрабатываются методы контроля точности при расчете фрактальных очередей с помощью последовательных или многократных «параллельных» прогонов имитационных моделей. Приводятся примеры применения разработанных методов.
Ключевые слова
системы массового обслуживания, распределения с тяжелыми хвостами, моделирование, генераторы случайных чисел, оценки, погрешности.
Цели и задачи
Целью работы является радикальное снижение аппаратных затрат на хранение очередей сообщений в телекоммуникационных сетях при сохранении требуемого качества информационного обмена. Для реализации цели, в первую очередь, необходимо разработать аналитико-имитационные методы расчета фрактальных очередей, а именно методы планирования имитационных экспериментов с фрактальными и с классическими очередями, что и является одной из задач данной научно-исследовательской работы.
Также задачами данной работы являются:
- решение проблемы корректной реализации распределений с тяжелыми хвостами;
- разработка методы контроля точности при расчете фрактальных очередей с помощью последовательных или многократных «параллельных» прогонов имитационных моделей.
Введение

Анализ современного состояния сетей передачи данных с коммутацией пакетов и исследования в области сетевого трафика показали, что современный трафик сетей передачи данных имеет фрактальную структуру. Фрактальность трафика заключается в его самоподобии или масштабной инвариантности. В таком трафике прослеживается долговременная зависимость описывающих его случайных переменных, а сами эти переменные описываются распределениями с тяжелыми хвостами (РТХ). Стохастическая фрактальность существенно влияет на характеристики сети, и как результат на её производительность. При проектировании сетевых устройств на системном уровне наиболее подходящими математическими моделями являются системы массового обслуживания.

 

Методы и материалы

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

Предлагается метод ARAND (Accurate RAND) – простой и одновременно универсальный метод решения проблемы корректной реализации распределений с тяжелыми хвостами, обобщающий и упрощающий принципы каскадных генераторов случайных чисел.

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

 

 

Описание и обсуждение результатов

При моделировании очередей для расчета оценки какого-либо интересующего нас математического ожидания используется выборка  зависимых реализаций случайной величины на выходе имитационной модели. С помощью построения статистической оценки коэффициентов r(s) корреляции между реализациями выборки можно определить необходимую длину прогона имитационной модели при заданной точности.

Аналитический анализ и результаты имитационного моделирования классических и фрактальных очередей систем массового обслуживания показал, что расчет доверительных интервалов при больших объемах N выборок значительно упрощается благодаря тому, что асимптотика коэффициентов корреляции r(s) при расчете классических и фрактальных очередей не отличается разнообразием. Для классических систем с очередями она определяется асимптотически экспоненциальным убыванием r(s) с ростом s, для фрактальных систем – асимптотически степенным убыванием r(s) (в качестве примера, см. рисунок 1, где показаны результаты расчета коэффициентов корреляции для классических, и рисунок 2 для фрактальных очередей).

 

В общем случае при расчете любых показателей типа вероятности отказа, среднего времени ожидания и т.д. функция r(s) имеет при расчете классических и фрактальных очередей асимптотику \(r(s) \sim ae^{-bs} \) и , \(r(s) \sim as^{-b} \) соответственно.

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

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

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

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

Используемые источники
1. Leland, W. E., Taqqu, M. S., Willinger, W., Wilson, D. V. On the Self-Similar Nature of Ethernet Traffic. ACM/SIGCOMM Computer communications review, 1993, - 146-155 pp.
2. Czachorski, T., Domanska, J., Pagano, M. On stochastic models of Internet traffic. Information technologies and mathematical modeling. 2015, 289-303 pp.
3. Crovella, M. E., Lipsky, L. Simulation with heavy-tailed workloads. In Self similar network traffic and performance evaluation. K.Park, W.Willinger (eds.), 89 – 100 pp., John Willey & Sons, 2000.
4. Zadorozhnyi, V.N. Fractal Queues Simulation Peculiarities, in Communications in Computer and Information Science, 2015. – P. 413-432.
5. Kleinrock, L. Queueing Systems: V. II – Computer Applications. – New York: Wiley Interscience, 1976. – 576 p.
6. Zwart, A. P. Queueing Systems with Heavy Tails. Eindhoven University of Technology, 2001. – 227 p.

Information about the project
Surname Name
Zakharenkova Tatiana
Project title
Methods of Simulation Queueing Systems with Heavy Tails
Summary of the project
Important problems of a correct organization of simulation experiments for calculating fractal queueing systems are considered. Fractal systems are described asymptotically by power laws of arrival interval distribution and service time of requests and are adequate mathematical models of network devices of telecommunication systems with a fractal (self-similar) traffic. We propose an effective solution of the problem for the correct realization of heavy-tailed distributions. Accuracy control techniques for calculating fractal queues by means of consecutive or repeated "parallel" runs of simulation models are developed. The application examples of the developed methods are given.
Keywords
queueing systems, heavy tailed distributions, simulation, random number generators, estimates, errors.