Содержание к диссертации
Введение
1 Задачи и общие принципы математического модели рования мультисервисных сетей большой размерности 16
1.1 Принципы организации концептуальных моделей мультисервисных сетей 18
1.2 Основные принципы организации программных моделей мультисервисных сетей 23
2 Принципы организации гибридных моделей мультисервисных сетей 37
2.1 Структурные элементы гибридной модели . 37
2.2 Состояния элементов гибридной модели 41
2.3 Эксперимент с гибридной моделью 44
2.4 Классификация математических моделей в составе гибридной 50
2.5 Характерные поведения компонентов гибридной модели 53
3 Методы и средства аналитического моделирования мультисервисных сетей 56
3.1 Сеть массового обслуживания как концептуальная модель метода аналитического моделирования 56
3.2 Элементы структурированной сети обслуживания 61
3.3 Параметры структурированной сети обслуживания 65
3.4 Характеристики структурированной СеМО 77
3.5 Методы анализа сетей обслуживания общего вида 82
3.6 Декомпозиция сетей массового обслуживания 104
3.7 Структурированные сети массового обслуживания, как аналитические модели МСС большой размерности 123
4 Методы и средства имитационного моделирования мультисервисных сетей 135
4.1 Дискретная динамическая система как концептуальная модель метода имитационного моделирования 135
4.2 Компоненты имитационных моделей 140
4.3 Декомпозиция имитационных моделей 169
5 Применение имитационного моделирования для ис следования мультисервисных сетей 175
5.1 Моделирование опорной сети передачи данных с коммутацией пакетов 175
5.2 Моделирование информационно - вычисли тельной сети Минморфлота 184
6 Применение сетей обслуживания для аналитического моделирования мультисервисных сетей 194
6.1 Исследование применение режима обмена короткими сообщениями системы беспроводного абонентского доступа DECT для передачи данных 194
6.2 Моделирование алгоритма обнаружения закладок в мультисервисной сети 206
6.3 Исследование процессов передачи мультимедийных данных в пакетной IP сети 222
7 Применение гибридного моделирования для анализа мультисервисных сетей 231
7.1 Моделирование вычислительного комплекса коллективного пользования 231
7.2 Моделирование сети передачи данных системы геомеханического мониторинга 238
7.3 Моделирование Х.25 вычислительной сети с коммутацией пакетов 248
Заключение 268
Литература
- Принципы организации концептуальных моделей мультисервисных сетей
- Структурные элементы гибридной модели .
- Сеть массового обслуживания как концептуальная модель метода аналитического моделирования
- Дискретная динамическая система как концептуальная модель метода имитационного моделирования
Введение к работе
Мультисервисные сети (МСС), информационные технологии, основанные на их применении, широко внедряются в различные сферы общественной деятельности. Удовлетворяя всё большие информационные потребности общества, МСС имеют тенденцию к увеличению размерности и усложнению принципов организации.
Математическое моделирование является одним из основных методов исследования МСС, обеспечивающим решение задач их анализа, проектирования и оптимизации. Общие постановки этих задач приведены в [18,21,24,26,28,36,38,39,44,50,116,242,249]. Основными задачами являются: определение физической логической и программной структуры МСС; оценивание и оптимизация различных вероятностно - временных характеристик функционирования МСС и их компонентов; управление и оптимизация информационных потоков на МСС; анализ и оптимизация сетевых протоколов, применяемых в МСС; исследование характеристик надёжности и живучести МСС.
Для решения выше приведённых задач программные средства моделирования МСС (СМ) должны обеспечивать [154]: адекватное отображение разнообразных сетевых процессов моделируемых МСС; оценивание с требуемой точностью параметров этих процессов и интерпретацию результатов моделирования; эффективное использование вычислительных ресурсов; использование программных моделей в режиме реального времени при управлении МСС.
Наибольшее распространение в качестве моделей МСС получили дискретные системы (ДС) [45,90,118,193], обеспечивающие отображение информационных процессов в МСС теоретически с любым уровнем детализации, и сети массового обслуживания (СеМО) [3,27,40,78], которые обеспечивают построение оценок важнейшего класса исследуемых параметров - вероятностно - временных характеристик МСС, таких как производительность и задержки передачи данных.
Распространение ДС, как концептуальных моделей метода имитационного моделирования, несмотря на высокую его трудоёмкость и вычислительную сложность, обусловлено в первую очередь его универсальностью в смысле отображения процессов функционирования, прогрессом в области методов и средств разработки больших и сложных программных комплексов, а также быстрым ростом производительности вычислительных средств.
Широкое использование СеМО обусловлено адекватностью отображения статистического мультиплексирования телекоммуникационных ресурсов МСС, естественностью и простотой описания их состава и структуры, развитием теории СеМО, разработкой эффективных вычислительных методов и программных средств их расчёта.
Рост сложности задач моделирования МСС значительно опережает рост производительности вычислительных средств [153]. Поэтому основной тенденцией [98,216,217,267] их развития является ориентация на использование гибридных моделей, включающих в качестве структурных элементов модели различной математической природы: динамические дискретные системы, сети массового обслуживания общего вида, марковские процессы, сети Петри, графы, автоматы и др. При этом наиболее широко в составе гибридных моделей применяются имитационные модели и сети массового обслуживания [58]. Развитие теории и методов гибридного моделирования осуществляется, в основном, в направлении использования принципов декомпозиции. При этом декомпозиция может применяться как к самой МСС, так и к моделям, составляющим гибридную модель [13]. Её использование позволяет принципиально снизить размерность моделей МСС и получить их решение в разумные сроки и с требуемой точностью. Методы декомпозиции линейных стохастических динамических систем рассмотрены в [72,133]. Декомпозиция аналитических моделей различных классов рассмотрены в [60,132,196,253].
В развитии теории и методов имитационного моделирования важное значение имеют [76,82]: разработка концептуальных имитационных моделей МСС, исследование их адекватности и устойчивости; разработка принципов организации систем имитационного моделирования; разработка методов измерений и статистического оценивания характеристик имитационных моделей; разработка методов планирования экспериментов с имитационными моделями.
Фундаментальное значение в имитационном моделировании имеют результаты теории систем [19,20,23,48]. Различные подходы и методы представления и описания ДС в имитационных моделях приведены в [104,113,115,126,130,201,239,240,262,268], наиболее распространёнными из них являются: 1) различные DEVS - схемы, 2) про-цессно - ориентированный подход, 3) событийно - ориентированный подход, 4) графы событий. Подходы к оценке адекватности имитационных моделей разрабатываются в [31,97,101,156,200]. Трудности решения проблем адекватности и устойчивости имитационных моделей определяются их сложностью и размерностью, а также дескриптивным характером их описания (описание не ввиде аналитических выражений).
В последние годы, в связи с широким распространением мультипроцессорных и распределённых архитектур, интенсивно разрабатываются параллельные алгоритмы управления модельным временем и синхронизации событий. Их использование может в значительной степени повысить эффективность математического моделирования [150,224]. В отличие от традиционных алгоритмов синхрониза-
ции событий параллельные алгоритмы сильно привязаны к используемой модели параллельных вычислений. Описание таких параллельных алгоритмов для различных моделей параллельных вычислений и вычислительных архитектур приведены в [93,95,151,152,203,223, 247,250,251,265].
Изобразительные средства систем имитационного моделирования МСС базируются или на специализированных языках моделирования (SIMULA-67 [2], GPSS/VI, SIMSCRIPT-II, GASP-V [233], SLAM-II [71] и т.д.) или на процедурных расширениях языков программирования общего назначения FORTRAN, ALGOL [52-54], PL/I [6], PASCAL [155,220], C++ [190] и т.д. до языков моделирования ДС. Достаточно полный перечень разработанных языков моделирования ДС и программных средств моделирования приведён в работах [34,102, 221,231].
В последние годы при имитационном моделировании широко используется объектно - ориентированная технология программирования, совместно с базами данных и знаний [204,256], которая базируется на языках программирования С++, Smalltalk, Oberon, Java [128, 145,190,205,232]. Это обусловлено следующими факторами: 1) высокой степенью стандартизации данных языков программирования, что обеспечивает возможность использования имитационных моделей на большинстве современных вычислительных платформах, в том числе и с параллельной обработкой; 2) технология разработки имитационных моделей, их отладка и модификация естественным образом ложатся на объектно - ориентированную технологию программирования, поддерживаемую данными языками; 3) объектно - ориентированная технология обеспечивает возможность без изменения большей части программного кода развитие системы понятий и изобразительных средств систем моделирования, что позволяет адаптировать их к широкому классу моделируемых МСС и задач их исследования; 4) базы данных и знаний, содержащие модели МСС, результаты их моделирования, а также различные экспертные оценки, позволяют накапливать, систематизировать и повторно использовать опыт математического моделирования МСС; 5) наличием в выше перечисленных системах моделирования удобных программных интерфейсов, позволяющих использовать в них универсальные программные средства обработки и представления результатов моделирования; 6) наличием развитых интегрированных сред разработки программ, которые обеспечивают построение эффективных моделирующих программ, разработанных на выше перечисленных языках. Всё это значительно сокращает сроки разработки и отладки имитационных моделей и повышает их надёжность.
Основные постановки задач статистического оценивания при ими-
тационном моделировании и их решения приведены в [35,141,173, 236]. Трудности статистического оценивания результатов имитационного моделирования обусловлены следующими факторами [79,125, 129,157]: 1) наблюдаемые случайные модельные параметры, как правило, являются достаточно сильно коррелироваными между собой; 2) исследуемые модельные процессы часто не являются стационарными, особенно на начальных фрагментах траекторий развития моделей; 3) в моделях могут развиваться процессы, имеющие различные временные масштабы; 4) последовательности квазислучайных чисел, используемые для описания модельных случайных процессов, в статистическом отношении не являются идеальными. В связи с этим применяются специальные методы статистического оценивания, которые учитывают наличие данных факторов.
Среди них наибольшее распространение получили методы: спектрального оценивания [ПО, 164], аппроксимации регенеративными процессами [29,41,117,136,177], аппроксимации марковскими и диффузионными процессами общего вида [135,143,144,211], аппроксимации различными процессами теории массового обслуживания [134, 174-176, 178, 230], а также различные методы моделирования редких событий и оценивания параметров их распределений вероятностей [137,148].
Для повышения эффективности имитационных моделей важное значение имеют методы: определения периода вхождения в стационарные режимы моделируемых случайных процессов [123], определения начального состояния моделируемых случайных процессов [237,238], методы уменьшения дисперсии оценок их параметров [142, 166,260], а также методы определения длины их моделируемой траектории, обеспечивающей требуемую точность моделирования [140,163, 165,191,211,234,258].
Для анализа адекватности имитационных моделей используются различные алгоритмы проверки соответствия используемых методов оценивания и наблюдаемых значений оцениваемых параметров [92, 97,171,172]. Ряд систем измерения воспроизводимых модельных траекторий и статистической обработки результатов имитационного моделирования описаны в [51,112,179].
Состояние теории СеМО достаточно полно отражены в работах [37,55,59,68]. В тесной связи с развитием теории СеМО развивались точные и приближённые методы их расчёта, которые обеспечивали: увеличение размерности СеМО (числа узлов, требований, уровней приоритета), повышение уровня детализации (неэкспоненциаль-ность распределений, неоднородность потоков требований, блокировки, ограниченную надёжность), повышение точности.
Точные аналитические методы разработаны для анализа мульти-
пликативных СеМО, среди которых наибольшее распространение получили методы, основанные на конволюционной схеме. Приближённые методы в вычислительном отношении являются, как правило, более эффективными, обеспечивают возможность анализа более широкого класса СеМО, но в ряде случаев имеют только статистическую оценку точности. Среди приближённых методов наибольшее распространение получил метод "анализа средних".
Сетевые модели обслуживания используются в целом ряде систем математического моделирования МСС, к которым можно отнести: QNA [257], Q+ [210], PANACEA [226], QNET [162], RESQ2 [], СЕН-ПР [7], МОНАД [85,262,263].
Современные требования [168] к инструментальным средствам моделирования МСС предполагают наличие в них: 1) средств построения гибридных моделей, содержащих в своём составе аналитические и имитационные модельные компоненты; 2) объектно - ориентированные языковые средства описания процессов функционирования МСС и их компонентов; 3) развитые средства отладки и диагностики моделей; 4) средства организации и сопровождения библиотек и баз данных, используемых в технологии моделирования МСС; 5) средства интерактивного управления процессом моделирования; 6) экспертную систему, обеспечивающую эффективное управление всеми этапами процесса моделирования; 7) разнообразные программные интерфейсы, обеспечивающие открытость инструментальных средств моделирования в отношении возможности расширения класса задач исследований, класса допустимых математических моделей; совершенствования языковых средств; 8) развитие подходов моделирования на основе экспертного оценивания. Наиболее полно вышеперечисленным требованиям удовлетворяют системы моделирования SMARTIE [169], ISENET [139], GPSS/VI [100], SIMSCRIPT-II.5 [233], SLAMSYSTEM [215], SIMA [225], OPNET [124], MODSIM-III [158], AWESIM [222], МОНАД [85,262,263]. Обзор инструментальных систем моделирования приведён в [119].
В основу диссертации положены результаты научных исследований, выполненных в Вычислительном центре (ныне Институт вычислительной математики и математической геофизики СО РАН), Институте горного дела СО РАН, а также Сибирском Государственном Университете Телекоммуникаций и Информатики в соответствии с заданиями и разделами НИР ряда государственных программ: "Создать экспериментальную сеть взаимодействующих вычислительных центров и провести на этой сети исследование вопросов построения ГСВЦ"(Постановление ГКНТ, Госплана и АН СССР № 475/251/131 от 12.12.80, НТП 0.80.14, 23.07); "Теория машинного моделирования"(Постановление АН СССР № 1454 от 25.12.80, комплексная программа
НИР 01.12.10); "Информационные процессы в вычислительных сетях: а) методы адаптивного управления в информационно - вычислительных сетях"(Постановление Президиума АН СССР № 1454 от
комплексная программа НИР 1.13.4.4); "Архитектура сетевых систем. Методы анализа, оптимизации и моделирования сетевых систем "(Постановление СФТМН Президиума АН СССР № 11000-494-1216 от 05.12.85, Комплексной программе фундаментальных и прикладных исследований по проблеме "Информационно - вычислительные сети"АН СССР, 1.13.8.2); "Создать и ввести в опытную эксплуатацию типовую автоматизированную систему непрерывного контроля и прогноза состояния и поведения массива горных пород, опасных по динамическим проявлениям на рудниках Минцветмета СССР"(Постановление ГКНТ, Госплана, Президиума АН СССР № 492/245/164 от
Комплексная целевая программа по проблеме 0.Ц.027); грантами РФФИ № 97-05-65270 и 98-01-00721, Госконтракт №02/72 от 17.04.02 по теме "Исследование технологий управления и мониторинга современных цифровых сетей связи и разработка системы динамического мониторинга обнаружения угроз информационных воздействий", а также планов НИР, утвержденных постановлениями и распоряжениями СО РАН и министерств связи и обороны.
Цель диссертационной работы: Разработка принципов организации средств математического моделирования мультисервисных сетей; разработка методов модельного описания информационных процессов в мультисервисных сетях; разработка программных средств имитационного, аналитического и гибридного моделирования мультисервисных сетей; применение методов и средств математического моделирование для решения задач проектирования реальных вычислительных и телекоммуникационных сетей.
Основные задачи диссертационной работы:
Разработка инструментальной среды математического моделирования мультисервисных сетей, обеспечивающей возможность решения комплексных задач их исследования, разработки и эксплуатации.
Разработка программных компонентов систем гибридного, имитационного и аналитического моделирования в структуре инструментальных средств математического моделирования мультисервисных сетей.
Разработка модельных комплексов для исследования вычислительного центра коллективного пользования; распределённой вычислительной сети с коммутацией пакетов; распределённой системы геомониторинга.
Научная новизна работы:
Предложена методология гибридного моделирования МСС большой размерности, заключающаяся в рассмотрении концептуальной модели МСС в виде структуры моделей различных классов и в её представлении как динамической системы, поведение ко-, торой определено на оси комплексного времени, отображающего последовательность этапов достижения целей моделирования.
Предложено для анализа задержек в МСС и анализа её производительности совместно использовать СеМО в качестве аналитических моделей, дискретные динамические системы в качестве имитационных моделей.
Разработаны формализованные описания гибридных аналитических и имитационных моделей, являющиеся основой для их качественного и количественного анализа на адекватность, точность и вычислительную устойчивость.
Предложены структурированные СеМО как основа для разработки аналитических моделей большой размерности, а также их декомпозиции.
Разработаны и программно реализованы методы анализа СеМО различных видов.
Разработаны и программно реализованы методы декомпозиции СеМО по их состояниям, узлам и классам, а также метод декомпозиции приоритетной СеМО.
Предложен метод декомпозиции имитационной модели СеМО большой размерности.
С использованием объектно - ориентированной технологии программирования созданы инструментальные программные средства (библиотека классов С++), поддерживающие разработанные принципы гибридного моделирования МСС и обеспечивающие разработку и имитационных и аналитических моделей МСС.
Методы построения гибридных моделей задержек и производительности различных МСС.
Аппробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на конкурсе научной молодежи СО АН СССР, Новосибирск, 1987г., а также на более чем на 20 международных, всесоюзных, всероссийских и региональных конгрессах, конференциях, совещаниях, семинарах и школах (подробный список приведён во введении диссертации). Основными из них являются: Всесоюзная конференция "Основные направления развития программного обеспечения ЭВМ, комплексов и сетей", Севастополь, 1980, X-XVII-ые всесоюзные и международные школы-семинары по вычислительным сетям, Тбилиси, Рига, Алма-
Ата, Минск, Ленинград, Одесса, Винница, 1985-1992гг., 1-ый и III-ий Всесоюзные школы-семинары по Распределённым автоматизированным системам массового обслуживания, Нальчик, 1988г. и Москва 1990г., Республиканский семинар "Совершенствование методов исследования потоков событий и СМО", Томск, 1989г., П-ая Всесоюзная конференция "Моделирование систем информатики", Новосибирск, 1990г., Международная научно - техническая конференция "Проблемы функционирования информационных сетей", Новосибирск, 1991г., Международная конференция по автоматизации в горном деле, Екатеринбург, 1992г., Научно - техническая конференция "Развитие лазерных и миллиметровых систем и средств в технике передачи информации и медицине", Воронеж, 1995г., IAAMSAD Международная конференция по теории систем, сигналов, управлению и вычислительной технике, SSCC98, Дурбан, Южная Африка, 1998г., Международная конференция "Распределённые вычислительные и телекоммуникационные сети", DCCN'99, Тель-Авив, Израиль, 1999г., 7-ая Международная конференция по CDMA системам, CIC-2002, Сеул, Южная Корея, 2002г., 7-ая международная научно - техническая конференция "Радиолакация, навигация, связь", Воронеж, 2002г., IEEE Международная научно-техническая конференция "Информатика и проблемы телекоммуникаций", Новосибирск, 2003г., Международная конференция "Проблемы функционирования информационных сетей", Связь 2004, Бишкек, Кыргызстан, 2004г., 2-ая IASTED Международная Мульти Конференция по Автоматизации, Управлению и Информационным технологиям, Новосибирск, 2005г. Кроме того материалы диссертации обсуждались на научных семинарах Научного совета по комплексной проблеме "Кибернетика"АН СССР, ИГД СО РАН, ИВМиМГ СО РАН и СибГУТИ.
Публикации. По результатам научных исследований, представленным в диссертации, опубликовано с 1977 по 2005гг. 44 работы, в том числе: 2 учебника, 7 статей в отечественных и международных журналах, 17 докладов в материалах всесоюзных и международных конгрессов, конференций, школ и совещаний, 10 статей в сборниках научных трудов ВЦ СО АН, ИГД СО РАН, ИВМ и МГ СО РАН, НЭТИ, 5 препринтов ВЦ и ИГД СО АН СССР, 3 учебных пособия СибГУТИ. Кроме того имеется ряд научных отчётов по выполненным научно -исследовательским темам.
Практическая ценность результатов работы. Полученные в диссертации научные результаты в области математического моделирования МСС и сформулированные принципы построения системного и функционального наполнения инструментальных программных систем математического моделирования МСС использованы при разработке: КИМДС - комплекса имитационного моделирования дискрет-
ных систем; ППП ИМСЕТ - имитационного моделирования вычислительных сетей; СИМС - системы имитационного моделирования больших сложных дискретных систем; ППП МОДЕС - для математического моделирования вычислительной сети с коммутацией пакетов; ППП СЕНПР - анализа приоритетных замкнутых СеМО общего вида большой размерности; МОНАД - инструментальной среды математического моделирования МСС.
Программные средства моделирования, разработанные на основе полученных результатов, а также результаты математического моделирования реальных МСС, переданы в организации: НПО "Красная Заря"(г. Ленинград), Институт математики и механики УрО АН СССР, Организацию п/я Г-4725, Центральный НИИ связи (г. Москва), НПО "Сибцветметавтоматика"(г. Красноярск), Научный совет АН СССР по комплексной проблеме "Кибернетика"(г. Москва), Институт лазерной физики СО РАН, Институт вычислительной математики и математической геофизики. Результаты научных исследований, приведённых в диссертации, лежат в основе лекционного курса "Анализ и моделирование телекоммуникационных систем с подвижными объектами "в Сибирском Государственном Университете Телекоммуникаций и Информатики, и используются также в курсах "Основы построения телекоммуникационных систем"и "Компьютерное моделирование".
Теоретические результаты, вычислительные методы и программные средства моделирования использованы при решении задач проектирования и разработки следующих МСС: вычислительного комплекса коллективного пользования СО РАН (ВККП), магистральной сети передачи данных (МСОД), интервально-маркерного метода доступа в локальной сети, системы автоматического управления шахтным транспортным роботом, автоматизированной системы контроля горного давления (АСКГД), информационно-вычислительной сети морского флота, территориально-распределённой вычислительной сети с коммутацией пакетов для электронной почты (ВСКП), системы радиодоступа DECT, режима передачи данных в CDMA системе, системы мультимедийного вещания по IP-сети, лазерной системы связи между наземными и космическими объектами.
В приложении 1 к диссертации (том приложений) приведены акты внедрения разработанных программных средств математического моделирования и моделей различных телекоммуникационных систем в перечисленные выше организации.
Структура диссертации. Диссертация состоит из введения, семи глав, заключения и тома приложений. Общий объём работы - 295 страниц машинописного текста, том приложений - 104 страниц. Работа иллюстрирована 55-ю рисунками и содержит 8 таблиц. Список
использованной литературы включает 268 наименований.
В первой главе рассмотрены основные задачи и общие принципы математического моделирования мультисервисных сетей большой размерности. Приведён обзор состояния теории математического моделирования задержек и производительности этих сетей. Приведена общая технология математического моделирования, в соответствии с которой определяются концептуальная (КМ) и программные (ПМ) модели исследуемой МСС. Определены базовые структурные компоненты концептуальной модели, которые используются для описания имитационных, аналитических и гибридных моделей. Описаны структуры концептуальной программной моделей МСС, реализованные в инструментальной системе моделирования МОНАД.
Во второй главе рассматриваются общие принципы построения гибридных моделей МСС. В общем случае концептуальная модель МСС предполагается гибридной и рассматривается как структурированный компонент, определяющий дескриптивное, математическое и алгоритмическое описание целей моделирования МСС всех существенных, с точки зрения сформулированных целей, сторон её функционирования, а также метода и алгоритма достижения этих целей. Определены типы структурных компонентов, составляющих концептуальную модель. Определены классы математических моделей, используемых для анализа задержек и производительности МСС.
Третья глава посвящена аналитическим моделям типа, в качестве концептуальных моделей которых используются структурированные сети систем массового обслуживания (структурированные СеМО). Рассмотрены основные концепции метода аналитического моделирования МСС с помощью СеМО предложено каноническое представление СеМО, описаны наиболее эффективные методам анализа СеМО, разработаны методы декомпозиции СеМО большой размерности
Четвёртая глава посвящена методу имитационного моделирования МСС. Рассмотрены дискретные динамические системы (ДС), которые выбраны в качестве концептуальных моделей метода имитационного моделирования, и которые определяются как динамические системы с дискретным либо непрерывным временем и алфавитом, поведения которых описываются ступенчатыми функциями произвольного вида. Определены основные компоненты имитационных моделей, рассмотрена структура связей между ними, определены их характерные поведения. На примере моделирования сети массового обслуживания рассмотрена структурная декомпозиция её имитационной модели. Получены оценки точности для такой декомпозиции.
В пятой главе продемонстрировано применение метода имитационного моделирования для исследования следующих телекоммуника-
ционных систем: 1) вычислительного центра коллективного пользования, 2) опорной сети передачи данных с коммутацией пакетов и 3) Информационно - вычислительной сети Минморфлота. Показаны недостатки и достоинства метода имитационного моделирования.
В шестой главе продемонстрировано применение сетей массового обслуживания для исследования следующих телекоммуникационных систем: 1) системы беспроводного абонентского доступа DECT, осуществляющей передачу данных в режиме обмена короткими сообщениями, 2) исследование алгоритма обнаружения закладок в телекоммуникационном оборудовании мультисервисной сети, 3) систему передачи мультимедийных данных в IP сети. Также продемонстрированы возможности и ограничения СеМО при моделировании МСС.
Седьмая глава иллюстрирует применение принципа гибридного моделирования на примере моделирования трёх телекоммуникаци-оннных систем: 1) сети передачи данных (СПД) системы геомеханического мониторинга, 2) Х/25 вычислительной сети с коммутацией пакетов, 3) CDMA системы, функционирующей в режиме передачи данных. Эти примеры моделирования показывают пути преодоления недостатков методов аналитического и имитационного моделирования МСС а также учёта их преимуществ. Делается вывод о перспективности метода гибридного моделирования МСС, основанных на различного вида декомпозиции как самой МСС, так и её моделей.
В заключении диссертации сформулированы основные положения, выносимые автором на защиту.
В выполнение диссертационной работы внесли вклад:
Ю.И. Митрофанов - постановка задач исследования и научное руководство исследованиями, участие в разработке принципов организации комплекса КИМДС, системы моделирования СИМС, участие в разработке пакетов программ ИМСЕТ, МОДЕС, участие в разработке моделей пускового варианта ВККП ВЦ СО АН СССР, сети передачи данных с коммутацией пакетов, моделировании информационно - вычислительной сети Минморфлота, участие в интерпретации результатов математического моделирования;
В.Г. Беляков - разработка методов расчёта сетей массового обслуживания и методов гибридного моделирования, участие в разработке принципов организации программных систем и СИМС и МОНАД, пакетов программ СЕНПР и МОДЕС, участие в разработке аналитических компонентов моделей пускового варианта ВККП ВЦ СО АН СССР, автоматизированной системы контроля горного давления, системы автоматизированного управления шахтным роботом, сети передачи данных с коммутацией пакетов, участие в интерпретации результатов математического моделирования;
М.В. Курленя, А.В. Леонтьев - постановка задач исследования ав-
томатизированной системы контроля горного давления, участие в интерпретации результатов моделирования АСКГД;
В.П. Шувалов - постановка задач исследования мобильных телекоммуникационных систем различного назначения, обсуждение результатов их моделирования.
Б.В. Поллер - постановка задач исследования лазерных систем передачи данных, обсуждение результатов их моделирования.
А.Н. Иванов, Г.А. Квашнин - участие в разработке программных компонентов комплекса КИМДС и пакета ИМСЕТ;
Л.И. Долбня, М.Р. Зарипова, Н.А. Мирошниченко(Кондратова) -участие в разработке программных компонентов пакета СЕНПР и системы МОНАД, участие в проведении моделирования АСКГД и ВСКП;
Г.В. Беляев, Л.Г. Ивлев, П.И. Рогаченко - участие в интерпретации результатов моделирования сети передачи данных автоматизированной системы контроля горного давления и системы автоматического управления шахтным роботом.
В.А. Величко - участие в разработке аналитической модели CDMA системы, обсуждение результатов моделирования.
С.А. Аль-Днебат - участие в разработке аналитической модели передачи мультимедийных данных по IP сети, проведение моделирования, обсуждение результатов моделирования.
Особую признательность и благодарность выражаю Ю.И. Митрофанову и В.Г. Белякову, внёсших наиболее существенный вклад в становление научных исследований, представленных в диссертации.
Принципы организации концептуальных моделей мультисервисных сетей
Для построения концептуальной и программных моделей МСС, для развития теории их анализа и верификации, была разработана система понятий и терминов, которая представлена в диссертации. Она основывается на общей теории систем и теории их моделирования [19,20,23,48]. Данная система понятий и терминов разработана в виде последовательности взаимосвязанных определений. Разработанная система понятий адаптирует терминологию общей теории систем к теории гибридного моделирования МСС, и обеспечивает унифицированное описание различных компонентов концептуальных и программных моделей МСС.
В качестве основного структурного элемента концептуальной модели МСС определяется компонент. Определение 1.1. Компонент cm — топологическая динамическая система [23,48], определяемая следующим кортежем: ст = (тст, Scm, Нст), (1.1) в котором: тт, Scm и Нст - его время, алфавит и поведение.
Определение 1.2. Время тст компонента cm — Упорядоченное множество моментов времени тт - модель реального времени, в котором происходит эволюция компонента ст. Ш
В зависимости от типа компонента cm его время тт может быть определено как пространство с непрерывной или решётчатой топологией, между элементами которого определяются отношения порядка (следования). В зависимости от топологии времени тт (непрерывной или решётчатой), компонент cm является потоком или каскадом, соответственно [25].
Определение 1.3. Состояние sm Є Scm компонента cm — Вектор sm = {pfm}, определяющий точку фазового пространства состояний, в котором происходит эволюция компонента ст. Ш
Состояние sm компонента cm может быть определено в пространстве произвольной размерности. Элементами состояния компонента являются его параметры. Определение 1.4. Параметр рст компонента cm — Координата рст состояния sm, определяющая некоторое свойство компонента ст. Ш Любой параметр р\т є sm компонента cm может быть элементом некоторого пространства произвольной размерности и топологии. Определение 1.5. Алфавит Рст параметра рст компонента cm — множество Рст допустимых значений параметра рст компонента ст. Ш Определение 1.6. Алфавит Scm компонента cm — Множество Scm = {Щт}, Scm С Yl Р, всех возможных состояний компонента cm, опре i деляющее его фазовое пространство состояний. Определение 1.7. Траектория hcm (t) компонента cm — отображение hcm : Scm - тт алфавита Scm компонента cm на его время тт. — Любая траектория hcm компонента cm описывается соответствующим вектором функций hcm [t) = [Щт (t)}, где Щт (t) - траектория параметра р-т компонента cm на его времени тст.
Определение 1.8. Поведение Нст компонента cm — Множество Нст = h-m\, Нст С тт х Нст, всех траекторий компонента cm, которые согласуются с его внутренними законами функционирования.
Определение 1.9. Эксперимент тст с компонентом cm на интервале тш его времени — воспроизведение в программной модели фрагмента hcm (t), t є rcm, некоторой траектории hcm поведения Нст, который соответствует непрерывному интервалу Тст Я гСт его времени. Воспроизведение этого фрагмента траектории обеспечивает достижение поставленной цели моделирования.
Построение КМ МСС заключается в определении её состава (множества компонентов), в построении их пространств состояний, в определении их поведений, в установлении связей между ними. Предполагается, что компоненты КМ описывают не только МСС, но и её исследуемые параметры и методы их оценивания.
В составе КМ различаются примитивные и структурированные компоненты. Поведение структурированного компонента, в отличие от примитивного, определяется поведением системы компонентов, образованной подкомпонентами (как примитивными, так и структурированными) структурированного компонента. Функционирование этих подкомпонентов определено на общей оси времени.
Определение 1.10. Структурированный компонент cm — компонент cm (Определение 1.1., стр. 18), в котором выделяется ряд его подсистем, каждая из которых описывается как компонент КМ. Определение 1.11. Подкомпонент стст структурированного компонента cm — компонент стст [Определение 1.1., стр. 18), определяющий подсистему структурированного компонента ст. Ш Определение 1.12. Состав Аст структурированного компонента cm — множество Acm = {ст{\ всех подкомпонентов структурированного компонента ст. Ш Определение 1.13. Суперкомпонент сіп компонента cm — структурированный компонент cm, в составе которого был определён подкомпонент ст. Ш Предполагается, что компонент cm, определённый в составе структурированного компонента ш, не принадлежит составу Аст суперкомпонента структурированного компонента ст.
Алфавит и траектории поведения структурированного компонента cm определяются соответствующими композициями алфавитов и " лет траектории всех подкомпонентов его состава А .
С целью повышения эффективности разработки ПМ, обеспечения возможности развития изобразительных средств описания процессов функционирования реальных МСС, использования объектно - ориентированной технологии моделирования, множество всех компонентов КМ разбивается на типы.
Структурные элементы гибридной модели .
Так как каждый комплекс в составе КМ является её подкомпонентом, т.е. динамической подсистемой КМ, то для описания его поведения определяются: 1) алфавит Scx с SKM комплекса сх, который может иметь произвольную размерность и топологию; 2) состав типа Мсх его моделей; 3) состав и структура параметров каждой модели типа Мсх, а также их алфавиты.
Определение 2.10. Состояние sx комплекса сх — вектор sx = {pfx}, sx Є Scx, параметров {Определение 1.4., стр. 18) комплекса сх (Определение 2.7., стр. 40), образованный из тех параметров концептуальной модели, которые описывают частную задачу моделирования, соответствующую комплексу сх. Ш
Параметры состояния sx комплекса сх, а также параметры состояния s1 его любой модели ті, по своему функциональному назначению различаются на параметры следующих типов: 1) входные параметры, 2) выходные параметры, 3) внутренние параметры.
Определение 2.11. Входные параметры icx комплекса сх — вектор Iох = р\х \, їсх С sx параметров комплекса сх, которые являются независимыми координатами его состояния sx, и которые определяют начальную точку Ксх (то) его воспроизводимой траектории hcx (г) [Определение 1.7., стр. 19), то = min т. ТЄТС зависимыми координатами его состояния sx, используемые для представления цели комплекса сх. В результате проведения эксперимента с комплексом сх выходные параметры бх будут определяться конечной точкой hcx (тм) его воспроизводимой траектории hcx (т), тм = max т. ттс
Определение 2.13. Внутренние параметры qcx комплекса сх — вектор qcx = \рсх \, qcx С sx параметров комплекса сх, которые являются зависимыми координатами его состояния sx, используемые для описания алгоритма достижения его цели. Внутренние параметры 6ох в ходе его проведения эксперимента с комплексом сх будут определять состояние sx на промежуточных этапах моделирования, т.е. во всех промежуточных точках его воспроизводимой траектории hcx (г).
Аналогично состоянию комплекса определяется состояние каждой его модели.
Определение 2.14. Состояние 5ті модели ml — вектор IIті = IpJ11], параметров модели ml, образованный из соответствующих параметров 3ті комплекса ml (суперкомпонента модели ml, {Определение 1.13., стр. 20)). Он описывает цели соответствующего семейства частных задач комплекса ml, а его элемент р1 = р1 является Щ1 - ым параметром комплекса ті. Ш
Определение 2.15. Входные параметры iml модели ml — вектор Iті = рр \,їт1 С s1 параметров состояния 5 модели ml, которые на интервале т С тс комплексного времени, соответствующем решению некоторой подзадачи семейства модели ml, являются независимыми координатами её состояния 5w/ и определяют начальную точку hml (го) фрагмента траектории h1(t) (Определение 1.7., стр. 19), воспроизводимого на интервале т, TQ = min т. Ш
Определение 2.16. Выходные параметры 6ті модели ml — вектор 5ті - \рщ\, 6ті С s"1 параметров состояния s"11 модели ml, которые на интервале г С тс комплексного времени, соответствующем решению некоторой подзадачи семейства, являются зависимыми координатами ее состояния s7 , и которые используются для представления цели этой подзадачи. Выходные параметры 6ті в результате эксперимента с моделью ml будут определяться конечной точкой пт1 (тм) фрагмента её траектории п%1 (t), соответствующей интервалу г, тм = max т.
Определение 2.17. Внутренние параметры q"11 модели ml — вектор яті яті Q gmi образованный из тех параметров состояния s ШІ r = { }, модели ml, которые на интервале г С тс комплексного времени, соответствующем решению подзадачи семейства, являются зависимыми координатами его состояния s"11, и которые необходимы для описания алгоритма достижения целей подзадач её семейства. Внутренние параметры q"11 в ходе проведения эксперимента с моделью ml определяют её состояние s"11 на всех промежуточных точках фрагмента её траектории К 1 (t), соответствующей интервалу т. Г" С ?"", I
Состояние s1 Є S каждой модели ml определяется соответствующим подмножеством параметров комплекса ml, s"11 С s"11. Аналогично комплексу сх, для каждой его модели ml определяются входные. Ы г ml Tmi = Lmi\ ВЫХОдные 6ті С Г11, 6ті = {/$}, внутренние яті Q яті яті = pmj, \, её параметры а также соответствующие этим параметрам алфавиты Sml, Iті, Oml, Qml.
Каждый параметр комплекса одновременно может выступать как входной, внутренний и выходной. Кроме того каждый из них может выступать в качестве параметра одной или нескольких моделей, составляющих данный комплекс. Структура параметров комплекса и его соотношение с параметрами моделей приведена на рис.3.
Рис. 3. Соотношение между параметрами комплекса сх и параметрами его моделей. Алфавит SKM КМ образуется как прямое произведение ал j г«КМ фавитов ее комплексов, 5 = П Scx, С є Т. Подпространства схеС jcx g ц р« 0сх сЦР и Qcx С Ц Р%, алфавита Scx любого комплек / / / са сх С определяют, соответственно, алфавиты входных, выходных са ml является соответствующим подпространством алфавита S . А подпространства Iті с П Р% 0ті С J] Р1 и Qml с П РІ, алфавита и внутренних его параметров. Алфавит Sml любой модели ті комплек »т/ пет Sm любой модели ml комплекса ml определяют, соответственно, алфавиты входных, выходных и внутренних её параметров.
Сеть массового обслуживания как концептуальная модель метода аналитического моделирования
Пусть Г обозначает СеМО, которая определяется как совокупность систем массового обслуживания (СМО) или узлов, осуществляющих обработку требований, циркулирующих между ними. Каждая СМО (Рис. 5) обслуживает поступающий в неё разнородный поток требований Л. Требования в потоке Л отличаются временем, необходимым для их обработки, а также типом и уровнем приоритета обслуживания. Поступающие в узел требование d размещается в его очереди. Требование пребывает в очереди узла до моментов или начала его обслуживания или его блокировки, а в самом узле до моментов окончания обслуживания или также его блокировки.
Определение 3.1. Блокировка требования в узле — отказ в предоставлении обслуживания требованию в данном узле, вызванный ограниченностью его ресурсов. Лв) № узла или в момент времени ц ty,rd , где q - момент времени начала его обслуживания. ДО As)
Причиной блокировки является ограниченность ресурсов узла, а именно отсутствие свободных мест в его очереди, которая содержит фиксированное число мест 0 b со. Блокировка требования d может возникнуть или в момент времени tj - его поступления в очередь
Состав и структура СМО в составе структурированной СеМО.
Обслуживание требований в узле осуществляется его г идентичными обслуживающими приборами. Если при поступлении требования в узел в нём не имеется ни одного свободного прибора, то оно, либо перейдёт в другой узел, либо поступит в очередь узла до момента начала его обслуживания. По окончании обслуживания требования в некотором приборе узла осуществляется выбор следующего обслуживаемого требования из его очереди. Алгоритм выбора требования для обслуживания и алгоритм его размещения в очереди образуют дисциплину обслуживания требований в узла, которая является одной из важных его характеристик.
Обслуженные в узле требования образуют его поток обслуженных требований Ф. Блокированнные в узле требования образуют его поток блокированных требований S. Они переходят для обслуживания в другие узлы в соответствии с приписанными им маршрутам обслуженных и блокированных требований.
Каждому требованию сети приписывается три следующие параметра (свойства): 1) Маршрут его движения по узлам СеМО; 2) Время его обслуживания в узлах его маршрута; 3) Приоритет его обслуживания в узлах его маршрута.
Определение 3.2. Маршрут требования на СеМО — св. определяющая последовательность узлов, в которых требование должно быть обслужено, для того чтобы быть обслуженным СеМО в целом.
Маршруты требований класса описываются последовательностью, св., функции распределения (ф.р.) которых являются распределениями вероятностей (р.в.) узлов, в которые переходит требование по окончании его обслуживания в каждом узле его маршрута. Обычно эти распределения являются фиксированными для каждого узла и типа требования, но может быть определена их зависимость от распределения требований по узлам и классам СеМО.
При обслуживании требования в узлах его маршрута приборы узлов выполняют соответствующее количество работы, которое определяется трудоёмкостью его обслуживания. При моделировании МСС СеМО существенны лишь временные характеристики процессов обслуживания, поэтому целесообразно ввести общую для узлов различных типов единицу измерения трудоёмкости обслуживания - время I обслуживание. Время обслуживания требования в узле рассматрива ется как св. с соответствующей ф.р. Эти ф.р. обычно являются фиксированным, но в общем случае оно, как и распределения маршрутов требований, также могут зависеть от распределения требований по узлам сети в целом.
Определение 3.3. Время s Є R[0,oo] обработки требования в узле его маршрута — св. s, определяющая время обслуживания требования в узле при условии пребывания в нём только одного этого требования.
Для описания времён s обработки требований используются, либо ф.р. экспоненциального типа, либо ф.р. общего вида, которые задаются первыми двумя её моментами (м.о. и дисперсией). Если времена обработки требований во всех узлах сети описываются ф.р. экспоненциального типа, то такую сеть будем называть экспоненциальной. В противном случае будем называть её сетью обслуживания общего вида.
Определение 3.4. Время v Є R[0, оо] обслуживания требования в узле его маршрута — производная св. 0, которая определяется суммарной длительностью всех интервалов времени от момента начала его обслуживания в узле до момента окончания его обслуживании, в течении которых приборы этого узла заняты обслуживанием этого требования.
Определение 3.5. Время w Є R[0,oo] ожидания требованием обслуживания в узле его маршрута — производная св. ш, которая определяется суммарной длительностью всех интервалов времени от момента поступления этого требования в узел до момента окончания его обработки в этом же узле, в течении оно ожидает освобождения любого прибора узла.
Определение 3.6. Время и Є ЩО, оо] задержки требования в узле его маршрута — производная св. ц, которая определяется длительностью интервала времени между моментом его поступления в узел и моментом окончания его обработки в этом же узле.
Производительность обслуживающих приборов узла может разделяться между несколькими одновременно обслуживаемыми требованиями. Поэтому время v увеличивается пропорционально числу таких требований. Возможно, что обслуживание требования может быть прервано при поступлении в узел более приоритетного требования. В этом случае оно возвращается в очередь узла и ожидает там освобождения любого обслуживающего прибора узла. Таким образом времена и и w зависят от времени s его обработки в узле и от потока требований, поступающего в него. Время и задержки требования в узле является суммой времён V И W.
Дискретная динамическая система как концептуальная модель метода имитационного моделирования
Процесс рг Є Рг является компонентом имитационной модели рг Є Мш с наиболее общим алгоритмом функционирования, описываемым в виде последовательности дискретных событий. Предполагается что процессы имитационной модели рг могут иметь пространство состояний произвольной размерности, при этом каждая координата его состояния может принадлежать либо непрерывному, либо дискретному пространству. Кроме того, траектории поведений процессов имитационной модели рг обладают свойством марковости, т.е. следующие событие на его траектории в некоторый момент модельного времени определяется только текущим состоянием этого процесса и не зависит от предшествующей траектории развития как самого процесса, так и всей структуры компонентов Арг данной модели. Данное ограничение не является существенным, так как путём введения дополнительных параметров состояния процесса его можно преодолеть.
Определение состояния процесса. {Определение 1.3., стр. 18) Состояние s7"- процесса рг имитационной модели рг определяется следующим вектором его параметров (Определение 1.4., стр. 18) ?г = { ff\ /, Г } , (4.8) где Ёг - его функциональное состояние, sfr - его событийное состояние, s" - состояние его интерфейса арг.
Функциональное состояние f/ = Ы), / = 1,2,..., процесса рг, где p l - его функциональный параметр с номером /, описывает внутренние законы функционирования этого процесса. Предполагается, что существенные стороны функционирования процесса рг отображаются его функциональным состоянием. При этом события на траекториях его поведения отражают допустимые изменения его функциональных параметров. Состав параметров функционального состояния каждого процесса рг является индивидуальным, и он определяется отображаемыми этим процессом свойствами моделируемой ДС.
Событийное состояние f/ = {ёеГ,ёрг,ёсГ}, координаты которого описывают множество последовательностей событий (изменений функционального состояния Ёг, которые могут иметь место на траекториях поведения Нрг.
Состояние интерфейса ІҐ процесса рг образуется множеством его параметров, которые образуют его клеммы, составляющие сеть связей между процессами. Его состав параметров и соответствующее ему состояние интерфейса арг процесса рг определяется структурой связей данного процесса с другими компонентами моделируемой ДС. В состав состояния интерфейса процесса рг могут входить следующие координаты: г.РГ - состояние sPr интерфейса аРг процесса рг с другими процессами модели; - состояние s d интерфейса ap d процесса рг с требованиями модели; - состояние S" интерфейса а процесса рг с классами требова нии модели; рг _г - состояние 5 0« интерфейса OQU процесса рг с очередями требований модели; - состояние sRn интерфейса ардп процесса рг со случайными величинами модели; - состояние ї интерфейса аРта процесса рг с датчиками состояний модели; - состояние s0 " интерфейса ар п процесса рг с мониторами модели.
В свою очередь, каждый интерфейс архг, определяется как объединение интерфейсов связи процесса рг с каждым взаимодействующим с ним компонентом типа х Є Tsm выражение (4.7), стр. 139, множества типов компонентов имитационной модели рг. Интерфейс связи aprrj процесса рг с некоторым процессом prj определяется алгоритмами взаимодействия этих процессов, а координаты состояния этого ин терфейса s pri являются координатами функционального состояния Щ . Интерфейсы связей процессов с компонентами других типов рассмотрены ниже при их описании.
Определение алфавита процесса. {Определение 1.6., стр. 19) Алфавит Spr процесса рг является произведением алфавитов его функционального и событийного состояний, а также алфавита состояния его интерфейса, Spr = Sp/ х Sper х Sa"r.
Алфавит функционального состояния Sp/ процесса рг определяется пользователем при описании алгоритма его функционирования. Он является пространством произвольного типа.
Событийный алфавит Sp/ процесса рг определяется следующим прямым произведением трёх множеств Spr = SPJ х Sf х SPJ. Множество Se = {ё/}, / = 1,2,..., отображений ej: Sp{r х Sa"r - Sf x Sa"r описывает образы всех событий, которые могут иметь место на траекториях поведения Щг процесса рг. Множество SPtr = {tj}, j = 1,2,..., отобра жений tj: Sf x Sa"r -» R [0, oo], описывает образы таймеров моментов времени всех событий процесса рг, которые определяют длительности интервалов времени между последовательными событиями на траекториях его поведения. Множество Sc = {dj}, j = 1,2,..., отображений cj: Sf x SaPr - {false, true} описывает образы таймеров условий всех событий процесса рг, которые определяют условия наступления последующих событий на траекториях его поведения.
Типы событий на траекториях процессов. Среди множества Spr событий процесса рг траекторий его поведения Нрт различаются функциональные и управляющие события.
Образ ёрт функционального события ерг определяется на функциональном алфавите Sp/ процесса при описании его поведения.
Реализация управляющего события, которое всегда является зависимым подсобытием некоторого функционального события другого процесса, обеспечивает изменение запланированной траектории развития процесса рг на его функциональном алфавите. Образ ёрг управляющего события процесса рг определён на его событийном алфавите SPJ. На траектории процесса рг могут быть определены следующие три типа управляющих событий: 1. est - возобновление в момент реализации данного события развития прерванной воспроизводимой траектории указанного процесса начиная с указанного функционального события; 2. е п - прерывание развития воспроизводимой траектории указанного процесса; 3. eev - изменение воспроизводимой траектории указанного процесса посредством выполнения незапланированного ранее функционального события.
