автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы аналитико-имитационного моделирования систем с очередями и стохастических сетей

4857201

ЗАДОРОЖНЫЙ Владимир Николаевич

МЕТОДЫ АНАЛИТИКО-ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ С ОЧЕРЕДЯМИ И СТОХАСТИЧЕСКИХ СЕТЕЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

1 з ОПТ 2011

4857201

ЗАДОРОЖНЫЙ Владимир Николаевич

МЕТОДЫ АНАЛИТИКО-ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ СИСТЕМ С ОЧЕРЕДЯМИ И СТОХАСТИЧЕСКИХ СЕТЕЙ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора технических наук

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Омский государственный технический университет»

Научный консультант: доктор технических наук, профессор

НИКОНОВ Александр Васильевич

Официальные оппоненты: доктор технических наук, профессор

ГРИГОРЬЕВ Юрий Дмитриевич

доктор технических наук, профессор РЫЖИКОВ Юрий Иванович

доктор технических наук, профессор ШАПЦЕВ Валерий Алексеевич

Ведущая организация: Омский филиал Института математики

им. С. Л. Соболева Сибирского отделения РАН

Защита диссертации состоится 16 ноября 2011 г. в 15.00 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.238.01 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В. И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан « » сентября 2011г.

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.238.01

Н. Л. Щеголева

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Информационные технологии стали в последние десятилетия одним из основных ресурсов и инструментов развития ведущих стран мира. Развитие цифровых технологий, вычислительных систем и сетей особенно важно для Российской Федерации с ее обширной территорией и богатым природным потенциалом. Непрерывная модернизация информационных технологий и повсеместное внедрение компьютерных сетей требуют опережающего развития инженерных методов и теории, направленных на сокращение сроков и повышение качества проектирования информационно-вычислительных сетей (ИВС). Теория вычислительных систем, формируемая в последние десятилетия, решает задачи эффективного комплексирования и использования аппаратных, информационных и программных ресурсов, и основывается на концептуальных и математических моделях, учитывающих стохастический характер поступления данных и запросов на их обработку, а также недетерминированное время обработки запросов вычислительными узлами и каналами связи. Математической базой теории вычислительных систем является теория массового обслуживания (ТМО), позволяющая решать разнообразные задачи анализа и синтеза ИВС путем определения технико-экономических показателей эффективности функционирования систем в целом при известных технических параметрах их отдельных узлов. Широкую известность в последние годы приобрели фундаментальные учебники по теории вычислительных систем и компьютерных сетей, использующие ТМО (Л. Клейн-рок, 1976; С. А. Майоров, Г.И. Новиков, Т.И. Алиев и др., 1978; Д. Феррари, 1978, Ю.И. Рыжиков, 1996; В.М. Вишневский, 2003). Решаемые методами ТМО задачи включают расчет вероятностно-временных характеристик функционирования центральных процессоров и узлов коммутации, анализ буферной памяти и алгоритмов маршрутизации, расчет потерь данных и загрузки линий связи, обеспечение требуемого времени ответа ИВС на запросы конечных пользователей и т.д.

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

то даже при пуассоновском потоке задач аналитическое выражение средних длин очередей к процессорам дается в ТМО лишь для однопроцессорных узлов. Особенно трудно поддаются аналитическим методам задачи оптимизации немарковских СеМО. Разнообразие вероятностных распределений, описывающих время обслуживания заявок в узлах, и корреляция интервалов между заявками в потоках, смешиваемых на входах узлов, делают оптимизацию немарковских сетей аналитическими методами практически невозможной (за исключением, быть может, специальных частных случаев).

Ограниченные возможности применения точных и приближенных аналитических методов ТМО в задачах проектирования ИВС приводят к широкому использованию современных технологий и программных средств имитационного моделирования (ИМ). При этом ИМ, облегчая широкое внедрение в практику проектирования ИВС формализмов и концепций ТМО, приводит, в то же время, к ряду специфических вычислительных проблем, обусловленных стохастическим характером отклика имитационных моделей и необходимостью корректной обработки этого отклика (например, в целях использования градиентных алгоритмов оптимизации). Проблема использования градиентов - это лишь одна из широко известных общих проблем ИМ систем с очередями. Другие известные проблемы связаны с существованием «критических точек» - таких значений параметров моделируемой системы, вблизи которых происходит резкий рост затрат машинного времени на моделирование. Типичные примеры попадания в окрестности критических точек - это ИМ СМО с близкими к единице коэффициентами загрузки или ИМ событий, имеющих малую вероятность. Подобная ситуация возникает и при моделировании приоритетных систем, в которых интенсивности потоков заявок разных классов различаются на порядки (проблема разномасштабных интенсив-ностей). Затраты машинного времени возрастают в этой ситуации также на порядки, поскольку для накопления необходимой статистики по классу редко поступающих заявок приходится вместе с ними имитировать и на порядки большее количество заявок других классов.

Наряду с классическими задачами теории ИВС, решаемыми на базе формализмов ТМО, в последнее десятилетие возникло большое число задач иной природы - задач, связанных с беспрецедентным ростом глобальных информационных сетей, в первую очередь - сети Интернет. Быстро развивающиеся большие стохастические сети, подобные сети Интернет, приобретают специфические свойства, обусловливаемые взаимодействием детерминированных «правил» и стохастических факторов роста сетей. Необходимость адекватного математического описания структурных особенностей стохастических сетей, состоящих из сотен тысяч и миллионов узлов и связей, привела к созданию и быстрому в течение последних лет развитию теории случайных неклассических графов. Ее наиболее развитую ветвь представляет теория сетей (графов) предпочтительного связывания. Такие графы выращиваются из небольших графов-затравок с помощью простых алгоритмов (генераторов), воспроизводящих способы развития моделируемых сетей. Наиболее широко известен граф Барабаши-Альберт (БА-граф), растущий неограниченно в результате циклического добавления к нему приращения графа - новой вершины с фиксированным числом т инцидентных ей ребер

(BarabàsiA., Albert R„ 1999). Графы БА обладают свойствами, принципиально отличающими их от классических случайных графов Эрдеша и Репьи (Erdös Р., Rényi А., 1959). На основе графов БА аналитическими и/или имитационными методами исследуют разнообразные позитивные и негативные процессы, происходящие в реальных сетях, и разрабатывают оптимальные стратегии влияния на эти процессы. Однако, несмотря на лавинообразный рост числа публикаций, посвященных сетям предпочтительного связывания, нерешенными остаются многие важные вопросы, требующие развития аналитической теории таких сетей.

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

В развитие методов аналитико-имитационного моделирования (АИМ) СМО и СеМО большой вклад внесли многие отечественные и зарубежные авторы: В.М. Вишневский, В.А. Жожикашвили, Д.Л. Иглхарт, В.В. Калашников, Дж. Клейнен, И.Н. Коваленко, Н.Ю. Кузнецов, О.И. Кутузов, Б.И. Плакс, Ю.Г. Полляк, Ю.И. Рыжиков, AJI. Толмачев, Д.С. Шедлер, R.B. Gabriel, M. Reinaldo, R.Y. Rubinstein, R. Suri, M. Zazanis и другие. Методы АИМ СМО и СеМО основываются на ТМО, связанной с именами А.К. Эрланга, A.A. Боровко-ва, Б.В. Гнеденко, Л. Клейнрока, И.Н. Коваленко, А.Н. Колмогорова, Ф. Полла-чека, Ю.И. Рыжикова, Т. Саати, А.Я. Хинчина и других ученых.

В развитие методов АИМ больших стохастических сетей значительный вклад внесли О.И. Кутузов, Ю.Л. Павлов, Ю.Ю. Тарасевич, А.Л. Эфрос, R. Albert, A. Barabási, В. Bollobas, S.N. Dorogovtsev, Р. Erdös, P.L. Krapivsky, J. Leskovec, M.E.J. Newman, D. Price, S. Redner и A. Rényi.

Объектами исследования в диссертации являются ИВС и другие технические системы, выполняющие массовую обработку заявок (материалов, данных, денежных средств, документов, клиентов, транспорта и т.д.), представимые в виде СМО и СеМО, а также большие стохастические сети (БСС) типа Интернет.

Предмет исследования: приоритетные СМО, однородные немарковские СеМО, графы предпочтительного связывания и методы их АИМ, разрабатываемые для решения задач, возникающих в проектировании ИВС.

Цель работы: разработка, обоснование, исследование, тестирование и программная реализация математических моделей и методов АИМ, предназначенных для эффективного решения задач анализа и синтеза СМО, СеМО и БСС, возникающих в теории и инженерной практике проектирования ИВС.

Задачи исследования:

1. Разработка ускоренных аналитико-имитационных методов моделирования СМО с дисциплиной абсолютных приоритетов при существенно различающихся интенсивностях поступления заявок разных приоритетных классов.

2. Вывод точных и асимптотических соотношений, позволяющих существенно (на порядки) ускорять ИМ при решении задач анализа и синтеза приоритетных

СМО и сводить эти задачи или отдельные этапы их решения к задачам, решаемым аналитическими или элементарными численными методами.

3. Разработка эффективных аналитико-имитационных градиентных и квазиградиентных методов оптимизации однородных немарковских СеМО.

4. Тестирование разработанных методов и алгоритмов АИМ СМО и СеМО, разработка рекомендаций по их использованию и их программная реализация.

5. Разработка эффективных методов АИМ БСС. Развитие теории графа БА.

6. Создание основ общей теории случайных графов с нелинейным правилом предпочтительного связывания (графов с НППС).

Графы с НППС включают графы БА в качестве частного случая. Теория графов с НППС должна решать в общем виде задачу анализа и задачу синтеза генераторов, выращивающих графы с требуемыми структурными характеристиками, соответствующими структурным характеристикам моделируемых реальных БСС. Основы теории графов с НППС требуется реализовать в виде комплекса эффективных программных средств для моделирования реальных больших сетей.

Методы исследования. Решение поставленных в работе задач осуществляется методами ТМО, теории восстановления, теории вероятностей, математической статистики, теории случайных графов, численными методами оптимизации, исследования операций и аналитико-имитационного моделирования.

Основные положения и результаты, выносимые на защиту:

1. Методы асимптотического анализа цикла обслуживания неприоритетной заявки, основанные на изучении вложенных в цикл обслуживания процессов, восстановления и сопряженных с ними процессов накопления. На защиту выносятся два метода - метод суммирования периодов занятости (метод СПЗ) и метод суммирования периодов обслуживания (метод СПО).

2. Метод декомпозиции систем С12|С12|п и С12|С12|п|| с абсолютными приоритетами на бесприоритетные системы и полученные на его основе аналитические выражения, ускоренные методы моделирования и новый класс моделей с очередями - многоканальные циклические системы обслуживания (ЦСО) с пакетированием неприоритетных заявок. (Нижний индекс 2 в обозначениях СМО указывает на наличие заявок двух классов - приоритетных и неприоритетных. В системах 012|012|п|| неприоритетная работа разделяется между всеми п каналами).

3. Двухуровневые двухэтапные аналитико-имитационные методы оптимизации однородных немарковских СеМО. На защиту выносится входящий в состав этих методов оригинальный метод «направляющих гипербол», а также аппрокси-мационный ускоренный метод оптимального распределения каналов по узлам СеМО и расширенный метод редукции (РМР) графов полумарковских процессов.

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

ной калибровки графа БА по коэффициенту кластеризации.

5. Основы общей теории случайных графов с НППС, включающие: уравнения баланса для стационарного распределения вероятностей локальной степени вершин; точные решения этих уравнений; ускоренный метод генерации случайных графов с НППС; точное распределение степени вершин в графах с НППС; методы калибровки генераторов графов при фиксированном и при случайном числе ребер в приращениях графа; методика калибровки генераторов графов по эмпирическим распределениям степени связности; рекомендации по практическому использованию графов с НППС; рекомендации по дальнейшему развитию теории.

Научная новизна диссертационной работы заключается в следующем.

1. При решении проблемы ИМ процессов с разномасштабными интенсивно-стями применительно к СМО GI2|GI2|n с абсолютными приоритетами и дообслу-живанием заявок выявлены и изучены две системы процессов восстановления и накопления, вложенных в цикл обслуживания неприоритетной заявки. На их основе путем использования известных в теории восстановления асимптотических результатов (Сох D.R., Lewis P.A. W., 1966) разработан для анализа цикла обслуживания метод суммирования периодов занятости (СПЗ) и метод суммирования периодов обслуживания (СПО). Метод СПЗ имеет сходство с методом Гейвера {Gaver D.P.), но свободен от предположения о пуассоновском характере потоков заявок. Это существенно расширяет область его практического применения. Метод СПО является развитием метода СПЗ и позволяет выразить асимптотические характеристики цикла обслуживания через известные параметры интервалов поступления и времени обслуживания заявок приоритетных классов.

2. Обнаруженные новые возможности применения теории восстановления к анализу цикла обслуживания неприоритетной заявки позволили найти ряд неизвестных ранее асимптотических и точных выражений для систем GI2lGI2|n с абсолютными приоритетами и для систем GI|GI|n. В отличие от традиционных методов, основанных на преобразованиях Лапласа-Стилтьеса и производящих функций, методы СПЗ и СПО не связаны с предположениями об экспоненциальном распределении интервалов поступления и/или времени обслуживания заявок.

3. Разработанный на основе методов СПЗ и СПО метод приближенной декомпозиции системы GI2|GI2|n на вложенную систему, сохраняющую только приоритетный поток заявок, и фоновую систему, сохраняющую только неприоритетный поток заявок, эффективно решает проблему разномасштабных интенсивностей при ИМ систем GI2|GI2|n. По сравнению с известным методом усреднения вклада интенсивных прерываний (Максимей КВ., 1979) значительно снижается погрешность результатов моделирования (благодаря учету моментов второго порядка).

4. Посредством разработанных методов декомпозиции для систем GI2|GI2|n и GI2|GI2|n|| найден ряд аналитических приближений, получаемых на основе решений, известных для бесприоритетных систем GI|GI|1 и GI|GI|n. В частности, получены и протестированы приближенные формулы для расчета средней длины очереди неприоритетных заявок для случая сочетания разномасштабных интенсивностей с высокой нагрузкой (в системе GI2|GI2|n||) и для случая пуассоновского потока неприоритетных заявок (в системе GI2|GI2|1).

5. Разработанные в диссертации методы декомпозиции обобщены на системы

GIji|GIji|n (с к классами заявок), в том числе на системы с вложенными прерываниями. Тестирование обобщенных методов показало их приемлемую точность и хорошие перспективы их развития применительно к случаям наличия в системах GI<:|GIt|n интенсивных прерываний.

6. Логика развития разрабатываемых методов АИМ приоритетных СМО привела к разработке и исследованию в диссертации нового класса систем с очередями, названных циклическими системами обслуживания. Для ЦСО найдены асимптотические выражения первичных технико-экономических показателей и разработаны эффективные методы АИМ. Эти системы отражают особенности функционирования многих реальных систем обслуживания и характеризуются наличием циклов накопления пакетов неприоритетных заявок для последующего их обслуживания в фоновом режиме.

7. Для решения задачи оптимального распределения непрерывного ресурса (стоимости, производительности) по узлам однородной немарковской СеМО разработан двухуровневый аналитико-имитационный градиентный метод оптимизации, ядром которого является оригинальный метод «направляющих гипербол» (НГ). Метод НГ использует настраиваемую по результатам ИМ локальную нелинейную аналитическую аппроксимацию поверхности отклика, что позволяет достичь принципиальных преимуществ по сравнению с известными методами оптимизации. Разработанный двухуровневый метод решает актуальную задачу минимизации среднего времени ответа СеМО. Решаемая задача отличается от известной задачи оптимизации замкнутых однородных марковских СеМО ([Жожика-швили В.А., Вишневский В.М., ¡988) общностью постановки: оптимизируются не только замкнутые и не только марковские СеМО.

8. Разработанный расширенный метод редукции графа случайных задержек позволяет рассчитывать математическое ожидание и дисперсию длительности описываемого графом полумарковского процесса с марковской цепью, вложенной в моменты смены состояний. От прототипа - метода Байцера (Beizer В., 1970) он отличается встроенным в ход редукции точным расчетом коэффициентов чувствительности вычисляемых характеристик к вариациям параметров графа, включая вариации переходных вероятностей. Агрегирование двухуровневого метода оптимизации СеМО с РМР позволяет определять чувствительность оптимальных решений к возмущениям параметров оптимизируемых СеМО.

9. Разработанная двухуровневая аналитико-имитационная структура процесса оптимизации применена к другой задаче - задаче оптимального распределения каналов по узлам однородной немарковской СеМО. В результате получены эффективные методы и для решения этой задачи. Оценка перспектив распространения двухуровневой аналитико-имитационной структуры процесса оптимизации на решение других задач позволяет охарактеризовать эту структуру как основу и предмет самостоятельного направления исследований в области АИМ.

10. В отличие от известных асимптотических (Barabäsi А„ Albert R., 1999) и частных точных подходов (Dorogovtsev S.N., Mendes J.F.F., Samukhin A.N., 2000; Krapivsky P.L., Redner S., 2001) в диссертации для определения точного совместного распределения концевых степеней ребра графа БА используется техника составления уравнений баланса и их решения в общем виде. На основе найденного

решения впервые получены аналитические выражения ряда важнейших характеристик, которые ранее рассчитывались трудоемкими приближенными методами ИМ. Разработан метод калибровки графа БА по коэффициенту кластеризации.

11. Предложенная в диссертации общая теория случайных графов с НППС полностью оригинальна и содержит множество новых результатов, часть которых в качестве своих частных случаев охватывает ранее известные или впервые полученные в диссертации результаты, установленные для графа БА.

Личный вклад соискателя. В список положений, выносимых на защиту, включены лишь те результаты, которые получены соискателем единолично.

Теоретическая значимость. Полученные в работе теоретические результаты являются существенным вкладом в развитие двух научных направлений:

1) в разработку эффективных аналитико-имитационных методов решения задач анализа и синтеза сложных систем с очередями;

2) в разработку эффективных аналитико-имитационных методов исследования больших стохастических сетей.

В рамках первого направления в диссертации получены новые аналитические решения, представляющие самостоятельную ценность для ТМО, разработаны эффективные методы АИМ и определены перспективы развития полученных результатов. В рамках второго направления существенно усилена новыми точными методами и решениями теория графа БА, разработаны основы общей теории случайных графов с НППС и определены перспективы ее дальнейшего развития.

Достоверность и обоснованность результатов подтверждается строгими математическими выкладками, а также численными и имитационными тестами. Работоспособность и эффективность предложенных методов подтверждается имитационным моделированием и численными примерами. Пригодность разработанной общей теории случайных графов с НППС, ее преимущества и высокая эффективность ее методов подтверждены имитационным моделированием реальных сетей, содержащих сотни тысяч узлов. Формальными проверками новых аналитических результатов, полученных в диссертации при исследовании СМО, СеМО, графа БА и графов с НППС установлено, что эти результаты включают в качестве частных случаев множество ранее известных результатов.

Практическая ценность работы заключается в следующем.

1. Ускоренные алгоритмы моделирования систем О^^Ып и 012|С12|п|| позволяют в случае значительно различающихся интенсивностей у потоков разных приоритетных классов сокращать на порядки затраты машинного времени на имитационные эксперименты.

2. Соотношения, полученные в результате асимптотического анализа ЦСО, позволяют рассчитывать показатели качества соответствующих реальных СМО, не прибегая к ИМ. В частности, когда циклы накопления пакетов заданы фиксированной длительностью, эти соотношения можно использовать для анализа и оптимизации систем со сменной, суточной или сезонной организацией работы. Задачи оптимизации ЦСО можно на основе этих соотношений сводить к алгебраическим уравнениям, решаемым элементарными численными методами.

3. Двухуровневые аналитико-имитационные методы оптимизации однородных немарковских СеМО позволяют с высокой точностью находить оптимальные ре-

шения для сетей, состоящих из сотен узлов и тысяч каналов. Это открывает новые возможности для оптимизации проектов ИВС.

4. Расширенный метод редукции и двухуровневый метод оптимизации СеМО могут эффективно использоваться в задачах проектирования структур ИВС, разработки программного обеспечения ИВС, маршрутизации сообщений и во многих других задачах, в которых исследуемый процесс может быть представлен полумарковским процессом с вложенной марковской цепью.

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

6. Теория случайных графов с НППС дает инструменты калибровки случайных графов, используемых для моделирования реальных сетей. Применяя такие калиброванные модели, можно прогнозировать развитие этих сетей, исследовать методом ИМ разнообразные процессы, происходящие или планируемые для реализации в этих сетях, оптимизировать стратегии влияния на эти процессы, эффективно противостоять негативным сетевым процессам.

Практическая ценность диссертационной работы значительно усиливается .тем обстоятельством, что разработанные в ней математические модели, аналитико-имитациоиные и численные методы могут быть использованы не только в проектировании ИВС. Их можно использовать и для исследования множества других систем, которые могут рассматриваться как системы с очередями или как БСС. Как системы с очередями можно рассматривать транспортные сети, связь, производственные и торговые комплексы, коммунальные службы и службы здравоохранения, учреждения юстиции, науки и образования, оборонные структуры, системы управления объектами с потенциально опасной технологией и т.д. Теория графов с НППС позволяет воспроизводить в моделях наиболее существенные свойства таких сетей, как сети социальных контактов, сети сотовой связи, сети цитирования, сети финансовых потоков, сети террористических организаций, сети участия белков в химических реакциях организма человека и т.д.

Реализация и внедрение результатов работы. Тематика научных исследований, выполненных в диссертации, связана с проводившимися в ОмГТУ научно-исследовательскими работами: «Система имитационного моделирования вычислительных комплексов (СИМВК)» (СМОФАП Киевского ПКБ АСУ, № ГОСФАП П007643), «Система имитационного моделирования вычислительного процесса в АСУ (научно - исследовательская тема Кг 546, № ГР 76090017, № инв. Б853603), «Анализ эффективности организации банка данных в АСУ реального времени» (№ ГР 81088775, инв. № 02860047403), «Разработка и исследование моделей и методов оптимизации оперативного управления механообрабатывакмцим участком в условиях АСУ» (№ ГР 01. 0031165), «Методология управления нелинейными динамическими фазовыми системами и информационно-вычислительными

комплексами в условиях неопределенности» (инв. № 022.007 01269) и др. Полученные в диссертации результаты нашли практическое применение на следующих предприятиях: ООО «АйПро», г. Омск; Омский филиал института математики РАН; ООО «Фарфалле» и используются в учебном процессе при чтении лекций, в курсовом и дипломном проектировании, проведении студенческих НИР и в лабораторных работах на кафедре «Автоматизированные системы обработки информации и управления» ОмГТУ. Издано 7 учебных пособий, в том числе 2 пособия с рекомендациями УМО вузов по университетскому политехническому образованию, и ряд методических указаний. Практическое использование результатов диссертационной работы подтверждено соответствующими актами о внедрении, представленными в приложении к диссертации.

Публикации. По теме диссертации опубликовано более 60 научных работ. Основные научные результаты представлены в 57 публикациях, в число которых входят: 2 монографии, 20 статей в журналах «Перечня ведущих рецензируемых научных журналов и изданий», 12 статей в других изданиях, 3 свидетельства программ ЭВМ, 20 работ в материалах международных и всероссийских научно-технических конференций.

Апробация работы. Основные научные положения и результаты диссертационной работы докладывались, обсуждались и были одобрены на следующих международных, всероссийских и региональных конференциях: II Всесоюзной конференции по перспективам и опыту внедрения статистических методов в АСУ ТП, Смоленск, 11-13 мая 1984; Всесоюзном научно-техническом семинаре «Информационное обеспечение автоматизированных систем управления нефтеперерабатывающих предприятий», Омск, 18-20 сентября 1984; Региональной научно-практической конференции «Перспективные направления развития автоматизированных систем управления и их компонентов», Омск, 1989; Межрегиональной научно-практической конференции «Омский регион: исторический опыт, проблемы и пути экономического развития в современных условиях», Омск, 1994; Межрегиональной научно-практической конференции «Омский регион: исторический опыт, проблемы и пути экономического развития в современных условиях», Омск, 1999; V Международной научно-технической конференции «Динамика систем, механизмов и машин», 16-18 ноября 2004; Второй Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2005), Санкт-Петербург, 19-21 октября 2005; Конференции-конкурсе работ студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Новосибирск, 22-24 февраля 2006; Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2006», 4-7 мая 2006; Третьей всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2007), Санкт-Петербург, 17-19 октября 2007; Международной конференции «Идентификация систем и задачи управления» (SICPRO'08), Москва, 28-31 января 2008, Институт проблем управления им. В.А. Трапезникова РАН; Всероссийской научно-технической конференции «Россия молодая: передо-

вые технологии - в промышленность», Омск, 2008; Межвузовской научно-практической конференции «Информационные технологии и автоматизация управления», Омск, 20-24 апреля 2009; Четвертой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2009), Санкт-Петербург, 21-23 октября 2009; VII Международной научно-технической конференции «Динамика систем, механизмов и машин» (10-12 ноября 2009); II Межвузовской научно-практической конференции «Информационные технологии и автоматизация управления», Омск, 20-24 апреля 2010; III Региональной научно-практической конференции «Информационные технологии и автоматизация управления», Омск, 9-12 апреля 2011 г.

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, семи приложений и списка литературы, включающего 286 наименований. Основная часть работы изложена на 300 страницах машинописного текста. Работа содержит 54 рисунка и 27 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Во второй главе исследуются системы с относительно интенсивными прерываниями, т.е. СМО GI2¡GI2|n и GI2¡GI2|n|| (n> 1) с абсолютными приоритетами и дообслуживанием и с относительной интенсивностью а = Л/А' » I, где А и А' — интенсивности приоритетного и неприоритетного потоков заявок соответственно. Анализ таких систем является задачей, трудной как для аналитического решения, так и для решения методом ИМ. Если при ИМ для достижения заданной точности оценок, характеризующих неприоритетную очередь, моделируется прохождение через систему N неприоритетных заявок, то вместе с этим моделируется и прохождение в среднем aN приоритетных заявок. И т.к. длительность прогона модели примерно пропорциональна числу имитируемых заявок, то по сравнению со случаем а = 1 равных интенсивностей время моделирования с ростом а возрастает в (N+ aN)/(N+N) = (1 + а)!2 ~ а/2 раз. С ростом а затраты времени на ИМ, и без того значительные, могут возрастать на порядки. Эта ситуация типична, например, для ИМ центральных процессоров ИВС, где управляющие процессы обладают абсолютным приоритетом по отношению к прикладным процессам.

Для решения проблемы ИМ систем с интенсивными прерываниями обосновывается возможность приближенной при больших а декомпозиции системы

GI2|GI2|n (или GI2|GI2|n||) на вложенную приоритетную систему S, получаемую из исходной системы устранением потока неприоритетных заявок, и фоновую систему S*, получаемую устранением приоритетного потока и корректировкой времени обслуживания неприоритетных заявок.

Разрабатываются методы асимптотического анализа систем GI2|GI2|n и GI2|GI2|n|| при а -» оо. Выводятся асимптотические соотношения, характеризующие цикл обслуживания неприоритетной заявки. Условие а -» со специфицируется путем: а) фиксации функций распределения вероятностей (ф.р.) Л,(0 и B¡(t) интервалов поступления и, соответственно, времени обслуживания неприоритетных заявок, и б) масштабного с коэффициентом а преобразования ф.р. A(t) и B(t) интервалов поступления и, соответственно, времени обслуживания приоритетных заявок: A(t) = A¿cU), B(t) = B0(af), где А0, В0 - ф.р., заданные при а = 1. Первые два момента перечисленных распределений полагаются конечными.

В одноканальной СМО GI2|GI2]1 выполнен анализ цикла обслуживания неприоритетной заявки при фиксированном чистом времени х' = Т ее обслуживания. Выявлены и изучены две системы процессов восстановления и накопления, вложенные в цикл обслуживания. Разработаны два метода асимптотического по а анализа цикла обслуживания. Оба метода - основанный на суммировании периодов занятости метод СПЗ и основанный на суммировании периодов обслуживания метод СПО - используют известные предельные теоремы теории восстановлений, установленные при статистическом анализе последовательности событий. С целью применения соответствующих выражений асимптотически нормальной при Т —> оо совместной двумерной ф.р. для числа восстановлений на отрезке [0,Т] и суммы случайных приращений, происходящих в моменты восстановлений, условие Т œ трансформируется в условие Т = const, а -» ». При этом сумма приращений трансформируется в суммарное время прерываний, а число восстановлений - либо в число прерывающих периодов занятости (метод СПЗ), либо в число прерывающих заявок (метод СПО) (Задорожный В.Н., АиТ, 2008).

Методы СПЗ и СПО позволяют корректно реализовать идею декомпозиции системы GI2|GI2|1 на вложенную и фоновую системы, и тем самым решить для системы GI2|GI2|1 проблему разномасштабных интенсивностей. Метод СПО позволяет также найти асимптотические по а выражения условных по Т характеристик цикла обслуживания непосредственно через известные параметры интервалов поступления и времени обслуживания заявок приоритетного класса.

Методом СПЗ установлено, что в системе GI2|GI2¡1 при фиксированном чистом времени х' = Т обслуживания неприоритетной заявки совместное распределение суммарного времени ZT прерываний ее обслуживания и числа /т прерывающих периодов занятости (числа прерываний) является асимптотически нормальным распределением с параметрами:

C2ZT~^(CÎ-2rC„Cv+CÏ),

(а-* со), (1)

где 2Т - среднее суммарное время обслуживания приоритетных заявок (суммарное время прерываний) в цикле обслуживания неприоритетной заявки,

р = Лх - приоритетный коэффициент загрузки (х - среднее время обслуживания приоритетной заявки),

ут - среднее число прерываний обслуживания неприоритетной заявки, у/ - средняя длительность периода незанятости системы приоритетными заявками (приоритетного периода незанятости),

С2т - коэффициент вариации (к.в.) времени прерываний 2Т, С<т> Су - к.в. периода занятости л-и, соответственно, периода незанятости у/ системы приоритетными заявками,

Сп - к.в. числа прерываний обслуживания неприоритетной заявки,

согг(2х, /х) ~ коэффициент корреляции между 2Т и ут, г - коэффициент корреляции периода занятости системы приоритетными заявками и последующего приоритетного периода незанятости.

Характеристики у ,СЖ, С¥ и г в правых частях соотношений (1) определяются по отношению к вложенной системе Б, получаемой путем устранения потока неприоритетных заявок, и в общем случае рассчитываются с помощью ИМ.

Методом СПО установлено, что в системе в^ОЫ! при фиксированном чистом времени х' = 7 обслуживания неприоритетной заявки совместное распределение времени прерываний и числа ут приоритетных заявок в цикле обслуживания является асимптотически нормальным распределением с параметрами:

у Р т _ Т 1 --Т, у-

\-Р ' т г о-Ру

с2 --

•--гт ^

1 -р

с

VI

2 1. т

1 -р

(2)

согг(г7,УТ)—. 1 + , (а-> оо), (3)

где ут - среднее число прерывающих заявок, обслуживаемых в цикле,

г - средняя длительность интервала поступления приоритетных заявок, С„т - к.в. числа прерывающих заявок,

СГ) Сх - к.в. интервалов поступления и, соответственно, времени обслуживания приоритетных заявок,

согг(2т, ку) - коэффициент корреляции между 2-х и

Q = Сх/Сг - относительная вариация времени обслуживания приоритетной заявки.

Найдены асимптотические характеристики цикла обслуживания неприоритетной заявки в многоканальной системе СЫвЫпЦ с разделяемой каналами неприоритетной работой. В этой системе обслуживание неприоритетной заявки идеально распараллеливается между свободными каналами, и новая неприоритетная заявка не начинает обслуживаться, пока не завершится обслуживание предыдущей неприоритетной заявки. Когда какой-либо канал освобождается от приоритетных заявок, на него тут же переносится часть незавершенного обслуживания уже вы-

полняемой неприоритетной заявки (если такая имеется). В этой системе при фиксированном чистом времени х' = Т обслуживания неприоритетной заявки время 21 прерываний и соответствующее число ^ прерывающих заявок имеют асимптотически нормальное двумерное распределение вероятностей с параметрами

1 -р пх

•т,

_ т

у г

1

иг (1-р)

с[+с1 1-р

гг пх (г* , Л с, +Р Сх

> Чт гр 1 1~р )

(а-»со),

где р = х1(пт) - коэффициент загрузки системы приоритетными заявками. Коэффициент корреляции согг(2т, ут) описывается выражением (3).

Для систем С121012|1 и ОЫС12|п|| найдены асимптотические выражения первых двух безусловных моментов календарного времени у обслуживания непри-оригетной заявки и числа V заявок, прерывающих ее обслуживание: х' _ х'

У

п(1 -р)

, пР

иг(1-р)

„ . (Сг2 + С1)4, (1-р) *

1-р

(4)

(5)

где

у - среднее календарное время обслуживания неприоритетной заявки, V - среднее число прерывающих заявок в цикле обслуживания, х' - среднее значение чистого времени (трудоемкости) обслуживания неприоритетной заявки,

Сх- - к.в. временил:'. Соответствующая плотность распределения вероятностей (п.в.) календарного времени^ выражается интегральным асимптотическим приближением

где Ъ,(<) = - п.в. времених\ ст(Т) =

¿1 (

Т

«(1-р)3

,а(Т) =

"(1-Р)

(7)

и масштабным асимптотическим приближением

С использованием ИМ выполнены испытания приближений (6), (7) и сформулированы рекомендации по их практическому применению. В общем случае масштабное приближение (7) рекомендуется применять для оценки формы п.в. ДО в области значений сравнимых с у (рис. 1). Интегральное приближение (6) позволяет с хорошей точностью оценивать хвосты распределения ДО-

38000

I.......................

пттгтпттттттттттттттттгп;

Рис. 1. Трансформация прерываниями двухмодалыгой п.в. чистого времени х' обслуживания

неприорите гной заявки (слева) в п.в. длительности у цикла обслуживания_

Гистограммы на рис. 1 получены путем ИМ одной из тестовых СМО (однока-нальной) при среднем числе прерываний v= 8,33. В этой СМО для сл.в. х' на отрезке (0, 50) задана двухмодальная п.в., симметричный график которой составлен боковыми сторонами двух одинаковых треугольников. Основания треугольников лежат на отрезках (0, 25) и (25, 50), вершины - в точках с координатами (10; 0,04) и (40; 0,04). Здесь х' = 25, = 0,3267. Сл.в. х, г и г' экспоненциальные. Среднее число прерываний v, определяемое формулой (4), при р= 1/4 = const изменялось путем одновременного изменения х и г. При v = vs =8,33 и v=v2 = 83,3 путем ИМ вычислены соответствующие вероятности р\ = 0,022 и рг= 0,0021 хвоста у > 66,67. Из (6) для вероятности хвостау > Т0 выводится интегральная оценка

Р = Р{У>Т0)

1-

\dT,

у °(Т) )

(где Ф - стандартная нормальная ф.р.), дающая для рх и р2 приближения р\ ~ 0,019 и р2 ~ 0,0021. С ростом V точность интегральной оценки возрастает.

Сопоставлением асимптотических представлений (1) и (2) показателя С|т установлено точное соотношение для систем 01[С1| 1, названное С-соотношением:

V

■{cl-2rC„Cv+Cl)=T-

cl+c] 1 -р

Найденное С-соотношение позволяет контролировать правильность результатов, получаемых при исследовании периодов занятости СМО, или упрощать анализ периодов занятости и незанятости при имитационном моделировании за счет вычисления оценки для г через оценки других моментов. В доказательстве С-соотношения используется тог факт, что любую систему С1|С1|1 можно рассматривать как приоритетную систему, вложенную в систему С12|С12(1.

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

В третьей главе метод приближенной декомпозиции систем с абсолютными приоритетами на вложенную систему 8 и фоновую систему Б используется вместе с установленными в главе 2 асимптотическими соотношениями для решения задач расчета и моделирования систем СЯ2|012!п и вЬ^ЫпЦ. Приближенные фор-

мулы для расчета систем GI2|GI2|n и GI2|GI2|n|| выводятся на основе приближенных или точных формул, известных для систем GI|GI|n, n> 1. Вложенная система S рассчитывается непосредственно как система GI|GI|n с заданными известными параметрами. Аналогично (как система GI|GI|n) рассчитывается фоновая система S*, время х' обслуживания заявок в которой предварительно заменяется длительностью х* цикла обслуживания неприоритетных заявок в исходной системе.

Этот подход позволил найти формулы для расчета системы GI2|GI2|n|| при большой нагрузке. При ИМ СМО близкий к единице коэффициент загрузки приводит к большим погрешностям оценок средних характеристик очередей (теоретически это рассмотрено в приложении Б). Погрешности ИМ еще более возрастают при сочетании большой нагрузки и разномасштабных интенсивностей потоков. В таких условиях вместо ИМ может применяться формула, выведенная для расчета средней длины q' очереди неприоритетных заявок в СМО GI2|GI2|n||:

Г1- -L. Л „2 гг

где р • = AS' 1, Г = , С]. = С* + -^—APl + С]), Сг - к.в. длитель-1 - р * (1 - р)

ности т' интервала поступления неприоритетных заявок. Условие а—>сс эквивалентно условию г /х' -» 0. Проверка формулы (8) путем ИМ СМО GI2|GI2|1 с равномерным распределением случайных величин (сл.в.) т', х', т и усеченным гиперболическим распределением сл.в. х (при С7Х= 27,24) показала при а = 10 следующее (табл.1). Точность оценки (8) (графа «расчет») с увеличением суммарной загрузки р возрастает (варьировались х и х' при xlx = const).

Таблица 1

Сравнение результатов расчета и моделирования тестовой СМО

— * X Сх> al ч

р расчет ИМ расчет ИМ Ч 0 расчет ИМ

0,50 5,00 5,00 1,31 1,31 0,15 0,76 0,82

0,70 7,00 6,99 1,50 1,50 0,50 2,40 2,70

0,80 8,00 7,99 1,59 1,59 0,99 4,90 5,17

0,90 9,00 8,99 1,68 1,68 2,63 13,07 13,71

0,95 9,50 9,50 1,72 1,72 5,79 29,98 30,52

Величина ^ в табл. 1 представляет собой альтернативную оценку средней длины очереди, получаемую при использовании известного метода усреднения вклада интенсивных прерываний. Из табл. 1 видно, что погрешность расчета параметров х' и Сх, цикла обслуживания гораздо ниже погрешности расчета величины д' и лежит в пределах долей процента. Это позволяет заключить, что основным источником погрешностей в данном случае является используемая формула Кингмана-Келлерстрема, но не метод декомпозиции. Отсюда следует, что применение в методе декомпозиции для приближенного расчета фоновой систе-

мы Б* точных результатов ТМО должно приводить к более точным решениям.

Для расчета Ц' в системе С512|С512|1 с пуассоновским неприоритетным потоком выводится (с применением для расчета системы 8 формулы Поллачека-Хинчина) следующая приближенная формула:

а р

(9)

2(1 ~Рг)

где р1 = р + р'- суммарный коэффициент загрузки, р = Лх'. Тестирование точности формулы (9) посредством ИМ системы с равномерными и эрланговскими распределениями сл.в. х, х', г показало следующее (табл. 2). При а = 10 в широком диапазоне изменения загрузки погрешность формулы (9) лежит в пределах 2,5%. И даже при а = 1 погрешность формулы (при ръ > 0,5) не превышает 5-6%.

Таблица 2

Результаты приближенного расчета тестовой СМО и ее моделирования при а = 10

* р 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9

г расчет 0,009 0,039 0,101 0,209 0,392 0,705 1,28 2,51 6,35

ИМ 0,009 0,040 0,102 0,209 0,394 0,708 1,32 2,51 6,39

На основе асимптотических результатов главы 2 методом декомпозиции выводятся приближенные формулы для первых двух моментов времени обслуживания пакетов неприоритетных заявок в фоновом режиме. Посредством ИМ показывается хорошая точность полученных формул, возрастающая с ростом среднего числа р прерываний обслуживания пакета. Формулы можно использовать для практических расчетов уже при /?= 1-10 и, тем более, при р> 10. Развитие этого результата приводит к разработке и исследованию (в гл. 4) моделей ЦСО.

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

Я'о-Я' _ 1 Р2 п Г ~ « О-Р)2 Упр'

где <][} - математическое ожидание получаемой этим методом оценки средней длины д' неприоритетной очереди, () = (Сг2 + С\) /(С* + С],) - показатель, характеризующий относительную вариабельность приоритетной нагрузки.

Оценены перспективы обобщения разработанного метода ускоренного моделирования на системы С14|С1*|я при числе классов заявок к> 2, в том числе на

случай многоуровневых прерываний. Тестирование точности обобщенных версий ускоренного метода ИМ показало ее сопоставимость с точностью ускоренного метода ИМ систем Суву!.

В четвертой главе разрабатываются методы АИМ многоканальных ЦСО -циклических систем обслуживания, характеризуемых наличием циклов накопления пакетов неприоритетных заявок и обслуживания этих пакетов в фоновом режиме. Отличие ЦСО от рассмотренных в главе 2 систем 012|С12|п|| с параллельным обслуживанием неприоритетных заявок заключается в том, что неприоритетные заявки, поступления которых в ЦСО образуют рекуррентный поток событий, предварительно накапливаются в пакеты. Длительность циклов накопления пакетов определяется одним из трех способов (Т-, К- и Х-пакетирование). Накопленный пакет обслуживается одновременно всеми каналами в промежутках времени, свободных от обслуживания приоритетных заявок. Период обслуживания пакета - период повышенной нагрузки (ППН) - должен заканчиваться до момента поступления следующего пакета. Если к этому моменту времени обслуживание пакета не заканчивается, то он остается обслуженным не полностью. Возможный вариант - ускорение работ по обслуживанию пакета. Оба варианта или их комбинация отрицательно сказываются на показателях эффективности ЦСО.

Основная задача анализа ЦСО заключается в определении первичных технико-экономических показателей эффективности ЦСО. К ним относятся моментные и квантильные характеристики календарной длительности А обслуживания пакета, и моменты числа у приоритетных заявок, прерывающих обслуживание пакета.

Рассмотрены типичные способы пакетирования неприоритетных заявок:

- формирование пакета по заданному времени Т0 накопления неприоритетных заявок (Т-пакетирование);

- формирование пакета по заданному числу N заявок (>!-пакетирование);

- формирование пакета по заданной его трудоемкости Хт (Х-пакетирование).

При любом из этих способов пакетирования ЦСО можно рассматривать как

систему 012|012|п(1> в которую в качестве потока неприоритетных заявок поступает поток сформированных пакетов. Для этого нужно определить соответствующие характеристики интервала в поступления пакетов, объема N пакета и его трудоемкости <£ (т.е. чистого суммарного времени обслуживания заявок в пакете).

Найдены асимптотические характеристики потоков пакетов.

При Т-пакетировании интервал в поступления пакетов фиксирован: в = Т0, а число N заявок в пакете и его трудоемкость £ случайны. Если Т0 -» то:

(где = Сх-/Сг■ - относительная вариация времени дг' обслуживания заявки), а совместное распределение вероятностей сл.в. N и £ асимптотически нормальное.

При Х-пакетировании формирование пакета заканчивается в момент перескока его трудоемкостью £ заданного уровня Хт. Если Хт —> °о, то £ ~хт, с] ->о.с учетом остаточного превышения трудоемкостью ( заданного верхнего уровня

ОО1

х.

2х

Число N заявок в пакете и интервал в поступления пакетов распределены асимптотически нормально, причем

х'

N

~ХШ

в - ^

г, £>(0)

согг(в,Щ ~

Хт

х

'2 2 -|2^ а.. о> ■ т

——н—--

Г х3

С2

Р(х') , Я-Х'

х

~Х„

■(С'+С2.)-,

с.

1

4с1 + с1

При Ы-пакетировании

Щв) = N' 0(т') >

распределения сл.в. £ и в асимптотически нормальные, и сл.в. £ и в независимы.

На основе характеристик потоков пакетов и результатов, найденных в гл. 3 для систем вЫвЬИ] получены асимптотические выражения первичных показателей эффективности ЦСО. В частности, для длительности А ППН найдено, что

N п

С1 ~

1_ N

(1 -р) 1 х

(Ю)

<\~Р)

где р = Хх!п, а среднее число заявок в пакете N и фактор С1 определяются для различных способов пакетирования следующим образом:

- для Т-пакетирования N = Т0 / г1', С = С;. + С$

- для Х-пакетирования

- для И-пакетирования N = N, С2 = Су

М = Хт1х' + {\ + СЬ)12, С -0;

Для вероятности р превышения величиной к заданного порога Т получены выражения, учитывающие характеристики (10) и использующие интегральное приближение (6), в котором параметры неприоритетных заявок заменяются соответствующими параметрами пакетов. Аналогично с помощью выражений для V (4), (5) получены выражения для числа заявок, прерывающих обслуживание пакета.

С помощью ИМ выполнено исследование точности асимптотических результатов (10). Основным показателем, определяющим возможность практического использования (10) в качестве приближенных формул, является показатель Р = (Мх')!{гп), характеризующий среднее число приоритетных заявок, прерывающих обслуживание пакета. При фиксированном р основными факторами, влияющими на точность приближений (10), являются к.в. С2 е {С, ,С2,С2,С2} сл.в. г, г', х и х'. Точность приближений (10) практически не зависит от других параметров ЦСО, в том числе от п. Установлено, что если все С)2 лежат в пределах

от 0,02 до 30, то формулы (10) вполне можно использовать для практических расчетов. Даже при небольших значениях показателя Д т.е. при 0,2 < р< 10, погрешности формул (10) лежат в пределах 1-3%. С ростом у? погрешности снижаются.

Исследованы возможности регулирования аритмичности нагрузки. В качестве показателя аритмичности используется к.в. Ch. Показано, что при объединении п одноканальных ЦСО в одну многоканальную аритмичность может быть снижена в 4п раз. В ситуациях, где это целесообразно, например, при стрессовых испытаниях ИВС, тренировке спортсменов, операторов технических установок и т.д. аритмичность может повышаться неограниченно (без изменения коэффициентов загрузки) за счет увеличения к.в. Сг и Сх, характеризующих приоритетные заявки. Требуемые Сг и Сх можно обеспечить применением датчиков сл.в.

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

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

Задача оптимального распределения непрерывного ресурса (стоимости, производительности) по узлам однородной немарковской СеМО формулируется следующим образом. Для открытой сети задана ф.р. A(t) интервалов поступления заявок в сеть, определяющая интенсивность А рекуррентного входного потока. Для замкнутой сети фиксировано число R заявок в сети (ф.р. A{t) не задается). Известны ф.р. B,{t) времени обслуживания заявок в узлах i сети, / = 1,л, и числа К, каналов в узлах. Вероятностиpl} (i,j = 0,л) переходов между узлами (индекс i = 0 соответствует внешней среде) заданы неразложимой стохастической матрицей Р = \\p,j}\. Ресурс M сети, определяемый вектором fi = (//,,...,//„) интенсивностей

обслуживания в узлах, фиксирован: M (р) = = М' = const, где с, - стоимо-

стные коэффициенты, Д > 0 - коэффициенты нелинейности.

Среднее время Е = Е(р) прохождения заявки через сеть (среднее время ответа, среднее время цикла) можно представит в виде:

(И)

где а, - среднее число посещений ¡-го узла заявкой за время цикла, р, - среднее время пребывания заявки в г'-м узле, и', - среднее время ожидания заявки в очереди 1-го узла,

b¡ - среднее время обслуживания заявки в í-м узле,

/j¡ = \/b¡ - интенсивность обслуживания заявки каналом ¿-го узла.

Коэффициенты a¡ однозначно определяются из системы уравнений баланса:

ai = H"j=oajPji ¿ = "о = 1 "

Для открытой сети через «i определяются интенсивности X¡ - Aa¡ входных потоков узлов, коэффициенты загрузки узлов р, = /К,), и проверяются условия стационарности p¡< 1 (или р, > X¡/K¡), i = 1,и. Значения w, в (11) определяются посредством ИМ.

В задаче требуется найти вектор Ji = ¡лор,, доставляющий минимум среднего времени ответа Е = Е{р):

£ = £(/}) -»min, (12)

м

и принадлежащий области допустимых решений (ОДР):

М(fi) - ¿cdlt' =М\ (i = ü), (13)

где для открытой сети fi¡min=Aí/K¡ (граница области стационарности), а для замкнутой сети ju¡min = 0. Для ресурса М' выполняется условие М > Mmím где для открытой сети Мт-т = J^^ufL = , а для замкнутой Mmin = 0.

В задаче (12), (13) имеется в виду, что изменение любой интенсивности д приводит к изменению среднего Ъ< = 1/р, и к соответствующему масштабному изменению ф.р. B,{t). Вид ф.р. B,{t) не изменяется, поскольку ассоциируется со случайной трудоемкостью заявок на соответствующих этапах обслуживания сетью. Варьируемый параметр р, взаимно однозначно связан с ресурсом c¡fjf' ¿-го узла.

Для решения задачи (12), (13) разработан двухуровневый двухэтапный ана-литико-имитационный метод, включающий следующие два этапа. Этап I - ускоренный градиентный поиск точки Jiopt оригинальным методом «направляющих гипербол», использующим ИМ сети и локальную аппроксимацию целевой функции (название метода НГ отражает роль и форму компонент аппроксимации). Этап II (не обязательный) - уточнение найденного решения ускоренным методом циклического покоординатного спуска, не использующим аппроксимаций.

Аппроксимация Еар{р) среднего времени ответа E{fi) на каждой итерации к> 2 поиска оптимального решения Jiop, методом НГ формируется по результатам ИМ сети в Точках ju - р.к'х й ¡1 = ¡йк, и применяется для определения следующей точки /} = /ít+1. Метод НГ использует следующие опорные элементы.

Io. Центр fic ОДР (13) при ресурсе М* > Мтт определяется условием равной загрузки узлов: p¡ =A¡/(juiK¡) = a¡Á1>í(^¡K¡) = рс, (i = 1,и), где !<, - интенсивность на терминальной дуге (для открытой сети Ло=Л). Отсюда jj, =(а,Л0)/(А'(рс.), =(a¡/Ki)(Kx/at), - (a¡ / K¡)(Kl/al)fii. Подставляя последнее выражение в (13), получаем уравнения:

« („ К У" _

£с, ^-^-Mi = М*' //,=(«,/*, XV«. )/Л> '" = 2,и. (14) ы 1Л «i )

Из первого уравнения численными методами определяется единственный положительный корень ¡1у, затем из остальных - все другие координаты центра ßc. Если сеть открытая, то в центре fic сразу вычисляются все р, = рс. < 1, i = 1, п.

Если все Д = 1, то из (14) координаты центра ОДР можно выразить явно:

/ yi _

Hcj-aj/Kj , ; = 1,и.

2°. Диаметр D ОДР определяется как длина максимального из диапазонов варьирования переменных D = тах{/,}, где = р,тах - /4 min и, согласно (13),

3°. Малый шаг размером, например, D 10~4, применяется при построении и сканировании траекторий на поверхности ограничений, определяемой уравнением (13). Шаг выбирается с учетом требований к точности оптимизации.

4°. Аппроксимация Eap(ß) целевой функции £(£), используемая для приближенного вычисления градиента, представляет собой сепарабельную функцию варьируемых переменных д.:

' 1

= + — , где №',(/;,) =

м V А

k

' , если nf * w( ,

Mi - si

.-Л-'

Ц, если IV," =и}"

которая на каждом шаге к оптимизации заново настраивается (посредством коэффициентов Я, и 5,) по оценкам и й* среднего времени ожидания, найденным для узлов / = 1,л при ИМ сети в точках ]л - рк~1 и Ц = р*. При А* * й*4 выражение Д,/(//, -5, ), входящее в Еар(р), должно аппроксимировать соответствующую функцию п; = и;(/2) в (11) так, чтобы его значение в точках /2 = /2к~1 и р = рк совпадало с имеющимися оценками н»/-1 и ч>к « ы{(Цк). Отсю-

да, требуя выполнения равенств /?,. - 5, ) = Л*', Л,- /(//,* - ) = н>к, находим:

И'; - И*;

(верхний индекс здесь везде соответствует шагу оптимизации). Такая настройка функции Е"р(/3) обеспечивает ее совпадение с £(Д) в точках и Д* (с точностью до стохастической погрешности оценок ИМ). В других точках /2 точность аппроксимации Еар(р) тем хуже, чем они более удалены от и р.к, и чем «менее сепарабельна» £(/2), т.е. чем сильнее изменение интенсивностей обслуживания д в одних узлах влияет на среднее время ожидания 'л>л в других (/ ф]).

5°. Градиент ЧЕар()1) в точке Ц = Цк есть аппроксимация градиента VЕф) в этой точке, и вычисляется с помощью выражения, полученного дифференцированием Еар(/й):

4Eap(jlk) =

dW. a, dW„ а„ а—---L_ ,•••, ап—--2-г

дцх (л)2 "дМ„ (цп)

где

dW,

L —

дм,

-Я

УЦфуЦ-1

' (/ = 1,»).

О,

— к -»ifc+J

6°. Валидная часть [Z,] исходящей из // траектории Z. поиска точки ¡л ле-

—к — жит между Ц и первой на L точкой ц, у которой какая-либо координата достигает границы ОДР Mi = Amin или полюса ^ =St аппроксимации Eap(Ji).

Разработаны пошаговые алгоритмы метода НГ и двухэтапного метода в целом (Zadorozhnyi V.N., Automation and Remote Control, 2009). Их программная реализация включена в систему ИМ и внедрена на предприятиях.

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

Однородная немарковская СеМО усиливается путем ввода в ее состав М> 1 дополнительных каналов. Все каналы технически идентичны, любой из них можно добавлять в любой узел. Различия между ф.р. B,{t) времени обслуживания заявок в узлах i = i,N связано с разной трудоемкостью работ, выполняемых разными узлами. Среднее время обслуживания в i-м узле может зависеть от числа л, его каналов. При увеличении и,- интенсивность /j, = 1/Ь, = д(и,) обслуживания в канале узла может снижаться или повышаться. Функции //,(и,) монотонные. Целью усиления сети в частном случае является снижение среднего времени ответа Е: при заданных функциях и заданном распределении n0 = (n0i,..., nw) имеющихся каналов по узлам 1,..., N требуется найти такое распределение m = (тх,..., mN) дополнительных М каналов (где т, > 0 - число каналов, добавляемых в /-й узел), которое минимизирует Е. В общем случае целью является минимизация некоторой выпуклой функции F от линейной комбинации средних длин очередей:

ш (15)

I т| = М, т>0,

где д,{п0 + т) — средняя длина очереди в /-м узле, су - стоимостные коэффициенты (штрафы), ||т|| = т, +...+ mN.

Для решения этой задачи предложен ускоренный метод последовательного размещения дополнительных каналов. Для случая открытой сети с производительностью каналов в узлах, не зависящей от и„ разработан аппроксимационный метод решения задачи. Метод основан на следующем эмпирическом приближении зависимости среднего времени ожидания w в изолированной СМО GI|GI|n от числа п ее каналов (Рыжиков Ю.И., 2003):

у ч Ч1) / ч

w(w)k——, или, равносильно, , и>1,

пг пг

где г - числовой параметр, который для фиксированных ф.р. A(t) длительности

интервалов поступления заявок и ф.р. B(t) времени их обслуживания можно подобрать с помощью ИМ. Аппроксимационный метод использует сепарабельную аппроксимацию зависимостей г/,{п0 + m) в целевой функции (15) выражениями, распространяющими приближение Ю.И. Рыжикова на узлы СеМО:

где Г/ определяются по результатам ИМ сети в двух точках: при исходном распределении п0 = (п0[,...,п0.>/) и при произвольном распределении п0+ т'=(/г<н + т'и ..., пом+т'м), в котором все т',> 1. Получаемая после подстановки (16) в (15) задача легко решается элементарными численными методами.

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

В контексте задач оптимизации СеМО разработан численный расширенный метод редукции, позволяющий без применения численного дифференцирования рассчитывать коэффициенты чувствительности (КЧ) моментов длительности полумарковского процесса (с марковской цепью, вложенной в моменты смены состояний) к вариациям переходных вероятностей. В приложениях В, Г приводятся формулы РМР. Его вычислительная сложность оценивается в приложении Д. Показано, что он требует выполнения 0(п2) операций при затратах памяти не более, чем 0(п2), где п - размер редуцируемого графа полумарковского процесса (степень связности вершин графа ограничена сверху). Метод НГ агрегирован с РМР для эффективного вычисления КЧ среднего времени ответа СеМО к возмущениям ее переходных вероятностей. Определяются три вида КЧ: частные (рассчитываются при условии отсутствия очередей), виртуальные (не учитывают чувствительности очередей к изменению переходных вероятностей) и полные КЧ. Метод РМР реализован программно, внедрен и используется в организациях.

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

Существенно развит аналитический аппарат теории графа БА - случайного бесконечного графа с линейным правилом предпочтительного связывания, широко используемого для моделирования сетей типа Интернет. Граф БА выращивается из небольшого графа-затравки путем неограниченного добавления фиксированных приращений графа - новых вершин с одним и тем же числом ребер т>\. Свободный конец каждого нового ребра присоединяется к той или иной имеющейся г-й вершине графа, которая выбирается случайно с вероятностью р„ пропорциональной локальной степени связности к,■ этой вершины:

Бесконечный граф БА характеризуется следующими стационарными вероятностями ()/< того, что случайно выбранная вершина имеет степень связности к

(16)

(17)

(DorogovtsevS.N., Mendes J.F.F., Samukhin A.N., 2000):

2m(m +1)

k>m.

к(к + \){к + 2У

Недостаточная изученность более тонких структурных свойств графа БА требует существенного развития точных аналитических методов его исследования.

Для ориентированной версии графа БА выведены уравнения баланса для стационарного совместного распределения вероятностей Оя концевых степеней /, к связности случайно выбранной дуги графа. Найдено его решение в общем виде, представленное в рекурсивной форме:

о,

(т + 2)(2/и + 3)

2(nt + l) | (*-1) к(к + \)(к + т + 2) (к + т + 2)

(1 + к + 2)

1>т,к = т, 1 = т,к = т + \,

1 = т,к>т + 2,

1>т + \,к>т + \.

(19)

Расчет матрицы Q = || Q, k || выполняется, начиная с заполнения крайнего левого столбца (столбца к = т) нулями и расчета элементов верхней строки (строки I = т): сначала по формуле (19) вычисляется ее второй слева элемент за-

тем, через него - следующие вправо элементы Qm k, к > т + 2. После этого построчно, слева направо, рассчитываются элементы следующих строк матрицы Q.

Результат (19) установлен впервые. В качестве частного случая он определяет следующее решение, известное для т = 1 (Krapivsky P.L., RednerS., 2001):

4(fc -1)_ _12(к — 1)

, (U> 1).

/(/ +1)(/ + ¿)(/ + к +1)(/ + & + 2) 1(1 + к~\)(1 + к)(2 + к + 1)(1 + к + 2) Найдены маргинальные распределения концевых степеней дуг графа:

2т(т +1)

2(к - т)(т +1)

1,к>т,

к(к + \)(к + 2) к(к + \)(к + 2)

где (£?•,*) - вероятность того, что начало дуги (конец дуги) имеет степень к. В среднем степень начала дуги равна 2т, степень конца дуги в среднем бесконечна. Концевые степени дуги - зависимые сл.в. Выведенные отсюда для неориентированного графа БА маргинальные вероятности концевых степеней ребра («начало» и «конец» которого выбираются случайно) составляют:

•* 2 (к +1)(& + 2) Асимптотическое по / и к совместное распределение концевых степеней ребра

т(т + \) ' l(l + l)k(k + \)'

или, компактнее, 0, к ~ т(т +1)/ 2к'

с ростом т сходится к распределению независимых сл.в.

Установлен асимптотический закон квадратичной пропорциональности между максимальной степенью К вершин графа БА и временем (числом шагов) N его выращивания: АГср = М(тах{£,-}) ос//"2 (рис. 2). С учетом этого закона с помощью полученных выше асимптотических распределений концевых степеней дуг выведено ранее для графа БА неизвестное аналитическое выражение важной структурной характеристики графа - коэффициента кластеризации. Коэффициент кластеризации С в общем случае определяется как утроенное отношение среднего числа лд треугольников в графе к среднему числу пу вилок (т.е. путей длины 2): С = Ъп^пу. Для графа БА

_ {т -1) (1п М)2 , 1Ч 1пЛГ „

+(я«-1)с, —, т>2, (20)

где коэффициент ст можно вычислять путем ИМ. Так, при т = 2, 3, ..., 8 его значения приблизительно равны 0.5, 0.35, 0.275, 0.18, 0.12, 0.10 и 0.07 соответственно (с ростом т коэффициент ст убывает по экспоненте). Второе слагаемое в (20) можно отбросить, т.к. его отношение к первому сходится к нулю. Формула (20) иллюстрируется соответствующими спрямленными зависимостями (рис. 3).

Рис. 2. Зависимость ЛсР от N при т - 2, Рис. 3. Данные ИМ графов БА: зависимости построенная по данным 11М (маркеры) показателя у » 1пС от х = 1п[(!пЛг) /Л/]

Для улучшения согласования выращиваемых графов БА с моделируемыми реальными сетями разработан метод сепарабельной калибровки выращиваемого графа по коэффициенту кластеризации. Такая калибровка не влияет на распределение степени связности вершин (РСС) графа, но позволяет в широких пределах изменять коэффициент кластеризации. Так, при N= 103 + 106 этот метод позволяет формировать граф с любым значением коэффициента в пределах от 0 до (20 -5- 3000)С соответственно, где С - номинальное его значение (20).

Разработана общая теория случайных графов с нелинейным правилом предпочтительного связывания. Граф БА, выращиваемый в соответствии с правилом (17), имеет при числе вершин N-*c° асимптотически степенное по к РСС (18). Однако в больших сетях типа Интернет РСС часто не являются асимптотически-степенными (ClausetAShalizi С. R., Newman М. Е. J.,' 2009). Для по-

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

А=/(*,)/2у/(*,), (21)

где /(к) =_/*> О - вес (предпочтение) вершины со степенью к - произвольная функция от к, ^ < к <М < оо). При этом число ребер в приращениях графа может задаваться как независимая сл.в. х с распределением гк = Р {дг = к}, g < к < И, (к < М). Т.о., алгоритм генерации (генератор) графа задается параметрами {/¿}и {гк).

Выведены уравнения баланса для стационарных вероятностей Qk степеней к вершин случайного графа с НППС. Найдено их решение в рекурсивной форме:

2*=

& =

_ rk(f) + mfk_xQk_,

if) + mfk

k>g +1,

(22)

где (/) = ^kQkfk~ средний вес вершины, т - М(х) - среднее число ребер в приращении графа. В частном случае, при х = т = g,f(k) = к из (22) вытекает известное распределение (18). Разработан метод быстрого численного расчета вероятностей Qk в (22) с одновременным определением среднего веса {/) вершины.

Найдено условие существования стационарного графа: М+ \>2т. При М+ 1 = 2т генерируются псевдорешетки - бесконечные случайные графы, степень вершин которых с вероятностью единица равна 2т = М+ 1 (рис. 4).

Разработаны методы синтеза генераторов графов с НППС, позволяющие выращивать случайные графы с заранее заданными РСС.

Задача синтеза: для заранее заданного РСС Ш = 1 > 0 со средним (k) > 2g найти веро-

ятности {гк) = rg,..., rh и веса {/"*} =/s, ...,fM> 0, при которых выращивается граф с РСС {Qk} = {Qk}.

Решение задачи выводится из (22):

Рис. 4. Начальный фрагмент псевдорешетки, выращиваемой из 10-вершннной цепочки при/,,..„Л =1,10,100,1000, М = 4,т = 2,5

f 1

J г X 1'

f - f J к ~~~ /*-1

+ 0--1, (k = g + l,...,M), fM+l = 0, </> = m, (23)

Qk

.0

о, ' " а

где т = (х) = ^кгк. При гг = 1 (фиксированное приращение графа: x = g = m) реализуется наименьшее для данного g среднее (к) = 2g. Вероятности ..., о, при заданном необходимо задавать так, чтобы выполнялось условие (к) = 2т. Если генератор использует вычисленные по заданному {()к} неотрицательные веса (23), выполнено условие М+ 1 > 2т и (к) = 2т > 2g, то генератор реализует требуемое распределение {б4} = {2*} и ПРИ этом (/) = /п. Справедливость этого утверждения доказывается подстановкой формул (23) в формулы (22).

Примечания. 1). Значения ..., выбираемые с учетом условия (к) = 2т, должны быть такими, чтобы веса (23) были неотрицательными. Для этого необходимо и достаточно при всех к<к соблюдать условие г- > й • Это ус-

ловие позволяет обеспечивать выполнение равенства (к) ~ 2т при любом (к) > 2g.

2). Стационарный режим существует, если М+ 1 > 2т, однако вероятность его реализации при немедленном связывании поступающих приращений графа может быть меньше единицы. Так, при гх = ...= г4 = 1/4 и любом наборе весов> О (здесь т = 2,5, М + 1=5= 2т) бесконечная псевдорешетка выращивается с нулевой вероятностью. Здесь после конечного числа шагов неизбежно возникает ситуация, когда после связывания нескольких ребер очередного приращения графа степень всех вершин становится равна пяти. Но поскольку /5 = 0, остальные ребра приращения становится невозможно связать ни с одной из вершин. В подобных случаях для достоверной реализации стационарного режима те приращения графа, которые не могут быть добавлены на данном шаге, можно помещать в очередь для последующего их добавления при первой возможности. Тогда при / -> °э если М + 1 > 2т, то средняя длина Щ) очереди приращений графа сходится к нулю, а если М + 1 = 2т, то 1(1) -> со, но £(Г)/А,~ ¿(1)/( 0.

Разработана методика калибровки генераторов графов с НППС по эмпирическим РСС реальных сетей, состоящих из сотен тысяч узлов и связей (Задо-рожный В.Н., Проблемы управления, 2010). Аппарат теории графов с НППС реализован в системе ИМ. Имеется свидетельство о ее официальной регистрации.

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

1. Решается задача оптимизации измерений производительности ЭВМ, осуществляемых с помощью выборочного микропрограммного измерителя. Задача состоит в определении максимальной интенсивности выборок, т.е. максимальной дополнительной загрузки р процессора измерителем, при которой погрешность измерения средней длины очереди прикладных программ, обусловленная загрузкой р, не превышает заданной величины 8. Адекватным представлением рассматриваемой системы является СМО 012|С312! 1 с пуассоновским потоком неприоритетных заявок. С помощью асимптотик, найденных в главе 3, задача сводится к алгебраическому уравнению второй степени и решается в общем виде:

р = -р12-^рг!Л-ц, где

Параметры приоритетных заявок здесь соответствуют операциям измерителя, реализующим выборки, а параметры неприоритетных заявок - прикладным программам. Проверка полученного аналитического решения р путем ИМ системы показывает его вполне достаточную для инженерной практики точность. Так, в условиях изменения от 0,1 до 0,8 загрузки р' процессора прикладными программами найденная предельная его загрузка р измерителем действительно обусловливает погрешности измерений 4,8-4,9% , близкие к заданной фанице 8= 5%.

2. Решается задача оптимизации режима работы серверного центра. Посредством асимптотик, полученных для ЦСО в главе 4, задача сводится к системе

а -Р') (с;+с1 1

р'2 ;

р =-(2-р')~ А'х ■

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

- не экспоненциальные распределения и многоканальные узлы;

- относительно интенсивные потоки заявок с абсолютными приоритетами;

- пакетирование неприоритетных заявок;

- циклическое ежесуточное изменение интенсивностей входных потоков;

- медленный тренд интенсивностей на больших периодах времени;

- малые значения вероятности - показателя, который нужно минимизировать.

Ежесуточно обслуживается два пакета: пока один накапливается в коммутационной ЭВМ, другой обслуживается многопроцессорным узлом. Накопление пакетов осуществляется непрерывно. Задача состоит в выборе оптимального времени Т1 начала часа профилактики (ЧП), в течение которого пакеты не обслуживаются (один пакет обслуживается от начала суток до Т1, другой - от Т1 + 1ч до начала следующих суток). Необходимо минимизировать вероятность того, что обслуживание хотя бы одного из двух пакетов не будет завершено вовремя.

Рис. 5. Структура серверного центра

Задача сведена к системе алгебраических уравнений для времени Т, начала ЧП: 60 • (23 -Т\) — у\ 60-Ц- у 2 I = I

У1-Су 1 У2-Су2 ' "(1 -ру п{\-рУ

О ~Р) 6 (1-Р) $2

I = 60-(Т, -4,333), £ = 60-(23 - Т,), (24)

где р, х. С, ,СХ - известные числовые характеристики приоритетного потока заявок, п - число процессоров. Путем численного решения уравнений (24) легко определяется искомое Т, = 12,58 ч и соответствующие вероятности Р1 и Р2 несвоевременного обслуживания первого и второго пакета: Р1 = Р2 = 1,Ы0~8.

Наряду с оптимальным временем Т! начала ежесуточного ЧП решается ряд других вопросов, в частности, определяются сроки наращивания числа процессо-

ров. Полученные решения (часть которых иллюстрируется рисунком 6), проверяются и подтверждаются непосредственным ИМ. На рис. 6 б) маркерами * и + отмечены результаты точечных проверок, полученные непосредственным ИМ.

;++++*

Ж*Ж*Ж" X* X 1 X 9 10 11 12 13 14 15 16 17 18

а) результаты расчета по асимптотическим приближениям

в) сравнение результатов расчета с результатами ИМ

кпиХН

_Рис. 6. Зависимость вероятностей PI, Р2 от начала Т1 часа профилактики_

Применение здесь формул глав 2—4 с учетом времени их точечных проверок ускорило решение по сравнению с непосредственным ИМ примерно в 104 раз.

3. С применением ИМ выполнено тестирование точности и быстродействия метода НГ. В испытаниях выполнялась оптимизация пяти однородных немарковских СеМО (рис. 7, 8) с одно-и многоканальными узлами, с набором п.в. времени обслуживания в разных узлах, характеризуемым большим разбросом к.в. Число узлов в тестовых сетях менялось от 9 до 100, а общее число каналов - от 12 до 260. Результаты сравнивались с результатами ИМ, полученными применением: а) базового «классического» метода приращений и 6) программы OptQuest, занимающей лидирующие позиции на рынке универсальных оптимизаторов.

При сравнении установлены принципиальные преимущества метода НГ как в скорости, так и в точности решения задачи. Так, заметно выигрывая у базового метода в глубине оптимизации, метод НГ превосходит его и в быстродействии. Например, решение, определяемое для СеМО-1 методом НГ за 7-11 итераций, обеспечивает среднее время ответа Е ~ 7,49...7,51, а базовый метод за 100... ¡40 итераций (т.е. за 1000... 1400 прогонов модели) дает более слабый результат Е -9,3...9,5. Это преимущество достигается за счет резкого снижения числа итераций и за счет того, что для вычисления градиента на каждой итерации метод НГ использует один прогон имитационной модели, а не (п + 1) прогонов, как базовый метод. При оптимиза-

Л = 1,

/>01 = 0.2, Л,,2 = <и Ли = 0-5. Р2.4 = 0-7, ^„ = 0.3,

Р4.6=0-3- Р4.7 = 0.4, 0.3, рц = 0.9, р5,9 = 0.1.

Рнс. 7. Тестовый пример СеМО-1. Штриховая дуга соответствует замкнутой версии сети

ции СеМО-1 с помощью программы ОрК^иев! за 750... 1000 прогонов модели (т.е. при стократном превышении времени, затраченного методом НГ) достигается среднее время ответа Е ~ 7.91, также заметно проигрывающее результату метода НГ.

Фазовая погрешность 8 - 100%х | рор! - ц | /1 рор, | метода НГ в тестовых задачах (табл. 3) не выходила за пределы 1%, и лишь в специально сконструированных «жестки») случаях - при перепаде значений к.в. времени обслуживания в разных узлах от 0 до 5 - достигала 3% (погрешность 8 метода НГ оценивалась сверху на втором этапе двухэтапного метода). Здесь /лор1 - оптимальное решение, /л - решение методом НГ. Упущенный эффект е = 100% х [Е(р') - Е{рор1))/Е(рор1) всегда составлял доли процента. Испытания метода на замкнутых сетях, функция Е(Ц) в которых «сильно не сепарабельна», показали, что при линейном ограничении (13) значение Сможет достигать 3%, а при нелинейном, с разбросом коэффициентов Д от 0,5 до 1,5,5 составляет (6-8)%. Но упущенный эффект остается достаточно малым (е < 1 %).

Как видно из табл. 3, при числе узлов и каналов, достигающем сотен (СеМО-5), когда высокие затраты времени на ИМ существенно ограничивают возможность увеличения числа итераций, метод НГ позволяет достигать значительного сокращения времени Е при числе итераций Ы, меньшем размерности п факторного пространства.

Таблица 3

Результаты испытаний метода НГ на тестовых сетях СеМО-2, ...,СеМО-5

СеМО-2 п = 9,К= 12 СеМО-3 л = 30,ЛГ= 134 СеМО-4 п = 20,К=52 СеМО-5 л=100,/С=260

Число узлов п. общее число каналов К

Число итераций N * время итерации Тч (мин) 20x2 60* 10 40x5 50x94 75*94

Распределяемый ресурс М 24 32 96 128 39 52 437 582

Отклик £с в центре ОДР 13,98 8,043 49,92 27,88 78,08 38,19 278,1 163,3

Отклик £ /.(/] ) 10.83 6.225 41,53 22,97 55,12 29,94 249,6 143,8

Эффект оптимизации (£с-¿')/£с' 100% 22,5% 22,6% 17% 18% 29% 22% 10% 12%

4. Решаются задачи калибровки генераторов с НППС по эмпирическим РСС реальных больших сетей. Калиброванные генераторы выращивают графы с распределениями степени связности (рис. 9 - 11, см. сплошные линии), хорошо согласующимися с эмпирическими РСС (см. рис. 9-11, маркеры). Эти генераторы можно рассматривать и как результаты структурной идентификации реальных сетей. Рис. 9 отражает результат идентификации сети автономных систем Интернет по реальным данным, включающим параметры N = 22 961 узлов и Я = 48 436 ребер (2006г.). Параметры калиброванного генератора: г, = 0,342, г2= 0,432,

/-3 = 0,096, г4= 0,13, т = Г) + 2г2+Згз + 4г4 = 2,014, /¡, ..., /4 = 0,0017, 0,0245, 0,0999,2,5303 соответственно, н/к = 0,8603-к при к > 5.

Рис. 10 характеризует качество идентификации сети маршрутизаторов Интернет (Ы = 124 651, Я = 207 214). Параметры генератора: гх = 0,435, гг = 0,565, /¡ = 0,272,/2 = 1,224, /* = 0,512Лп{к) + 0,372-/:, к> 3. Рис. И характеризует идентификацию сети участия актеров в общих фильмах (/V =511 416 - без изолированных узлов, Я = 1 463 331). Два соответствующих актерам узла связаны ребром, если эти актеры снимались в одном фильме. Здесь п, ..., г8> 0, численно фиксированы /1, ...,/ю , а при к> 10 общая формула весов имеет вид^ = 4,429- 1п(&).

Рис. 9. РСС калиброванного Рис. 10. РСС калиброванного Рис. 11. РСС калиброванного графа и сети автономных графа и сети маршрутизаторов графа и сети участия актеров в систем Интернет Интернет общих фильмах

5. Калиброванные графовые модели сетей можно использовать для анализа и оптимизации различных сетевых процессов. Интернет - «сеть сетей», представляет собой иерархическую структуру, модулями которой являются автономные системы (АС). Каждая АС - это система 1Р-сетей, имеющих свои уникальные 1Р-адреса, и маршрутизаторов (шлюзов), управляемая одним или несколькими операторами, которые осуществляют единую политику маршрутизации сообщений в пределах АС, независимую от остальной части Интернета. В состав АС может входить от единиц до нескольких тысяч компьютеров. Связь между АС осуществляют «граничные» шлюзы, прокладывающие маршруты между АС, рассматриваемыми как неделимые элементы и имеющими минимальный набор параметров, необходимых для маршрутизации. Этот набор включает уникальный номер АС, количество 1Р-сетей в АС, их адреса и внутренние расстояния до этих сетей от данного граничного шлюза. Граф сети автономных систем, выращиваемый калиброванным генератором, можно использовать для анализа ее связности при случайных отказах элементов (т.е. при потере связи с отдельными АС) и для расчета критической вероятности отказа, при достижении которой сеть распадается на несвязные компоненты. Администраторы АС, учитывая результаты такого анализа, могут уточнять свой выбор числа провайдеров и смежных АС для соединения с Интернетом. Уточнение выбора может привести к системному эффекту, несколько изменяющему ход развития Интернета. Этот эффект можно оценивать заранее, генерируя графы по первоначальным и по скорректированным правилам предпочтительного связывания, и используя в качестве затравки известное текущее состояние сети АС.

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

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

В приложении Ж приводятся сведения о разработанных в ходе диссертационного исследования комплексах программ, реализующих методы АИМ систем с очередями и стохастических сетей, об их внедрении и государственной регистрации, копии свидетельств о регистрации, актов внедрения и актов приемки-сдачи.

В заключении сформулированы основные результаты работы, включающие:

- методы асимптотического анализа цикла обслуживания СМО с абсолютными приоритетами С512|С12(п и 012!012|гг||, п> 1, приближенные формулы для очередей в этих СМО и ускоренный метод их имитационного моделирования;

- точное С-соотношение, связывающее первые два момента периодов занятости и незанятости в системе С1|01|1 и его обобщение на системы С1|01|п;

- математическую модель систем обслуживания с циклическим пакетированием неприоритетных заявок и результаты ее асимптотического анализа;

- эффективные двухуровневые аналитико-имитационные методы оптимизации однородных немарковских СеМО;

- расширенный метод редукции графовых моделей полумарковских процессов с вложенной в моменты смены состояний марковской цепью;

- методы и результаты точного анализа структурных свойств графа БА;

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

- численные методы и комплексы программ, реализующие разработанные математические модели и методы АИМ систем с очередями и стохастических сетей.

Основные результаты диссертации опубликованы в следующих работах

В монографиях

1. Задорожный В.Н. Аналитико-имитационные исследования систем и сетей массового обслуживания: монография / В.Н. Задорожный. - Омск: Изд-во ОмГТУ, 2010. - 280 с.

2. Задорожный В.Н. Аналитико-имитационные исследования Больших Сетевых Структур: монография / В.Н. Задорожный. - Омск: Изд-во ОмГТУ, 2011. - 208 с.

В журналах перечня ВАК

3. Задорожный В.Н. Асимптотический анализ систем с интенсивными прерываниями // Автоматика и телемеханика, 2008. - № 2 - С. 86-96.

4. Задорожный В.Н. Оптимизация однородных немарковских сетей массового обслуживания // Проблемы управления, 2009. - № 6. - С. 68-75.

(Zadorozhnyi, V.N. Optimizing Uniform Non-Markov Queueing Networks // Automation and Remote Control ISSN 0005-1179. - Vol. 71, No. 6,2010. - P1158-1169).

5. Задорожный В.Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления, 2010. -№6. - С. 2-11.

6. Задорожный В.Н., Литунов С.Н., Штриштинг С.Л. К вопросу о проблеме муара при воспроизведении изображений печатными способами // Известия высших учебных заведений. Проблемы полиграфии и издательского дела, 2007. -№1,-С. 30-39.

7. Задорожный В.Н. Общая статистическая структура простейших клеточных автоматов /V Омский научный вестник, 2005. 2 (31) - С. 150-156.

8. Задорожный В.Н. Анализ систем с приоритетами методом декомпозиции // Омский научный вестник, 2005. - № 3 (32) - С. 126-132.

9. Задорожный В.Н., Пуртов A.M. Анализ чувствительности в имитационном моделировании сетей массового обслуживания // Омский научный вестник, 2005. № 4 (33). - С. 165-171.

10. Задорожный В.Н. Асимптотический анализ периодов повышенной нафузки в приоритетных системах // Омский научный вестник, 2006. - № 3 (36). - С. 117-124.

11. Задорожный В.Н., Семенова И.И. Управление сложными техническими объектами и парадигмы имитационного моделирования И Омский научный вестник, № 6 (41), 2006. - С. 102-108.

12. Задорожный В.Н., Ершов Е.С., Канева О.Н. Двухуровневые градиентные методы для оптимизации сетей с очередями И Омский научный вестник, 2006. -№7 (43).-С. 123-131.

13. Задорожный В.Н. Распределение календарного времени обслуживания неприоритетных заявок в системах с абсолютными приоритетами // Омский научный вестник, 2006. - № 8 (44). - С. 124-131.

14. Задорожный В.Н. Комбинированный метод моделирования циклических систем обслуживания // Омский научный вестник, 2006. - № 9 (46). - С. 156-163.

15. Задорожный В.Н. О качестве программных генераторов случайных чисел // Омский научный вестник, 2009. - № 2 (80). - С. 199-205.

16. Задорожный В.Н., Ершов Е.С. Градиентный метод и программа оптимизации сетей с очередями//Омский научный вестник, 2009. -№ 2 (80). - С. 205-210.

17. Задорожный В.Н., Юдин Е.Б. Статистически однородные случайные графы: определение, генерация, применение // Омский научный вестник. - 2009. - № 3 (83).-С. 7-13.

18. Задорожный В.Н., Юдин Е.Б. Точная теория графа Барабаши-Альберт // Омский научный вестник. - 2009. - № 3 (83). - С. 13-18.

19. Задорожный В.Н. Распределение каналов в однородных немарковских сетях с очередями //Омский научный вестник, 2010. - № 1 (87). - С. 5-10.

20. Задорожный В.Н. Методы калибровки аддитивных генераторов стохастических графов // Омский научный вестник, 2010. - № 1 (87). - С. 171-176.

21. Задорожный В.Н. Предпосылки создания фрактальной теории массового обслуживания // Омский научный вестник, 2010. - № 2 (90) - С. 182-187.

22. Задорожный В.Н., Тулубаев Д.А. Метамодель систем оперативно-диспетчерского управления сложными крупномасштабными организационно-техническими объектами // Омский научный вестник, 2011. - № 1 (97) - С. 19-23.

В материалах международных и всероссийских научно-технических конференций

23. Задорожный В.Н. Методы ускоренной имитации процессов с интенсивными прерываниями. - Имитационное моделирование. Теория и практика: Материалы 2-й всерос. конф., Том 1. - СПб.: ФГУП ЦНИИТС, 2005. - С. 101-106.

24. Задорожный В.Н. Асимптотические приближения в имитационном моделировании систем с очередями // Имитационное моделирование. Теория и практика: Материалы 3-й всероссийской конференции. Том 1. - СПб.: ФГУП ЦНИИТС, 2007. - С. 117-122.

25. Задорожный В.Н. Методы двухуровневого моделирования систем с очередями // Труды VII Международной конференции «Идентификация систем и задачи управления» SICPRO '08. - Москва, 28-31 января 2008. - С. 1484-1563.

26. Задорожный В.Н. К дискуссии о качестве датчиков случайных чисел. Имитационное моделирование. Теория и практика (ИММОД-2009): Материалы 4-й всероссийской конференции. Том 1. - СПб.: ЦТ СС, 2009. - С. 128-134.

27. Задорожный В.Н. Оптимизация немарковских сетей с очередями // Динамика систем, механизмов и машин: Матер. VII междунар. науч.-техн. конф. -Омск, 2009. Кн. 1. - С. 288-292.

Свидетельства о регистрации комплексов программ

28. Задорожный В.Н., Юдин Е.Б. Система агентного моделирования «Simbigraph» (ОФЭРНиО № 16539) / М.: ИНИМ РАО, ОФЭР «Наука и образование», -2011. -№ 50201050316.

29. Ершов Е.С., Задорожный В.Н. Комплекс программ оптимизации сетей массового обслуживания «RedOpt» (ОФЭРНиО № 16589) / М.: ИНИМ РАО, ОФЭР «Наука и образование», - 2011. - № 50201150081.

30. Юдин Е.Б., Задорожный В.Н. Система агентного моделирования «Simbigraph» / Свидетельство №2011612193 о государственной регистрации программы для ЭВМ / Федеральная служба по интеллектуальной собственности, патентам и товарным знакам. - М.: РОСПАТЕНТ, - 2011. - № 2011612193.

Печатается с оригинал-макета, представленного автором

ИД №06039 от 12.10.2001 г. Подписано в печать 31.08.11. Формат 60x84 '/16. Бумага офсетная. Отпечатано на дупликаторе. Усл. печ. л. 2,25. Уч.-изд. л. 2,25. Тираж 100 экз. Заказ 508 .

Издательство ОмГТУ. 644050, г. Омск, пр. Мира, 11; т. 23-02-12 Типография ОмГТУ

СПИСОК СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

1. ЗАДАЧИ ЭФФЕКТИВНОГО КОМПЛЕКСИРОВАНИЯ И ИСПОЛЬЗОВАНИЯ РЕСУРСОВ ИВС И МЕТОДЫ ИХ РЕШЕНИЯ.

1.1. Вычислительные системы, компьютерные сети и их модели.

1.1.1. Задачи эффективного комплексирования ресурсов ВС и методы их решения.

1.1.2. Приоритетное обслуживание: проблема разномасштабных интенсивностей.

1.1.3. Компьютерные сети: задачи оптимизации.

1.1.4. «Фрактальная ТМО» и проблема датчиков случайных чисел.

1.1.5. Расширенный метод редукции: задача анализа чувствительности.

1.2. Методы моделирования глобальных компьютерных сетей.

1.2.1. Глобальные компьютерные сети: задача адекватного описания топологии.

1.2.2. Теория графа БА: задача развития аналитических методов теории.

1.2.3. Задача создания общей теории случайных графов с НППС.

1.3. Метод имитационного моделирования.

1.3.1. Общие положения.

1.3.2. Типы («парадигмы») имитационного моделирования.

1.3.3. Особенности предметно ориентированного ИМ.

1.3.4. Особенности применения ИМ в диссертационном исследовании.

1.4. Разработка методов АИМ: задачи, решаемые в диссертации.

1.4.1. Асимптотический анализ цикла обслуживания в системах 012|012|п.

1.4.2. Вывод асимптотических выражений для характеристик цикла обслуживания.

1.4.3. Разработка асимптотических методов декомпозиции системы 012|012|п.

1.4.4. Вывод асимптотических выражений для неприоритетных очередей.

1.4.5. Обобщение методов декомпозиции на системы (31*|01*|п.

1.4.6. Разработка методов АИМ систем с циклическим накоплением пакетов заявок.

1.4.7. Разработка аналитихо-имитационного метода оптимизации однородных немарковских СеМО

1.4.8. Разработка расширенного метода редукции и его использование при оптимизации СеМО.

1.4.9. Разработка аналитико-имитационного метода распределения каналов по узлам СеМО.

1.4.10. Разработка методов точного анализа безмасштабного графа БА.

1.4.11. Разработка аналитических основ общей теории случайных графов с НППС.

Выводы к главе.

2. ЦИКЛ ОБСЛУЖИВАНИЯ НЕПРИОРИТЕТНОЙ ЗАЯВКИ В СМО С12|С12|п.

2.1. Постановка задачи.

2.1.1. Проблема разномасштабности.

2.1.2. Система с относительно интенсивными прерываниями.

2.2. Условные характеристики цикла обслуживания в одноканальных системах.

2.2.1. Асимптотики общего времени прерываний и числа прерываний.

2.2.2. Метод суммирования приоритетных периодов занятости.

2.2.3. Метод суммирования приоритетных периодов обслуживания.

2.2.4. Суммарное время прерываний и число прерывающих заявок.

2.3. Условные характеристики цикла обслуживания в многоканальных системах

2.3.1. Применение метода СПЗ.

2.3.2. Применение метода СПО в системах с разделенными приоритетными потоками.

2.3.3. Применение метода СПО в системах с разделяемой неприоритетной работой.

2.4. Безусловные характеристики цикла обслуживания.

2.4.1. Безусловные моменты длительности цикла и числа прерывающих заявок.

2.4.2. Распределение вероятностей для длительности цикла.

2.4.3. Интегральное приближение для п.в. длительности цикла.

2.4.4. Масштабное приближение для п.в. длительности цикла.

2.4.5. Испытания интегрального и масштабного приближений.

2.4.6. Косвенный контроль погрешности масштабного приближения.

2.4.7. Приближения для хвоста распределения длительности цикла.

2.4.8. Требование достаточно быстрой сходимости приближений.

2.5. С-соотношения для систем GI|GI|1 и GI|GI|n.

2.5.1. С-соотношение для одноканальных систем.

2.5.2. С-соотношение для многоканальных систем.

Выводы к главе.

3. АНАЛИЗ ОЧЕРЕДЕЙ В СИСТЕМАХ GI2|GI2|n. ПРИБЛИЖЕНИЯ И УСКОРЕННОЕ МОДЕЛИРОВАНИЕ.

3.1. Прикладные методы анализа систем с прерываниями.

3.2. Асимптотическое приближение для большой нагрузки.

3.2.1. Задача моделирования СМО с большой нагрузкой.

3.2.2. Средняя длина неприоритетной очереди при большой нагрузке.

3.2.3. Сходимость приближения для большой нагрузки.

3.3. Случай пуассоновского неприоритетного потока.

3.3.1. Вывод приближения для средней длины очереди.

3.3.2. Оценка сходимости приближения.

3.4. Приближение для фонового пакета.

3.4.1. Основные соотношения.

3.4.2. Сходимость приближения для фонового пакета.

3.5. Ускоренное моделирование систем с прерываниями.

3.5.1. Контроль отрицательных приращений календарного времени.

3.5.2. Пример имитационного моделирования.

3.5.3. Область пригодности метода усреднения.

3.6. Декомпозиция систем GI*|GI*|/i при к >2.

3.6.1. Обобщение метода декомпозиции на системы GI*|GIt|>7.

3.6.2. Испытания метода декомпозиции систем с несколькими классами заявок.

3.6.3. Случай пуассоновского неприоритетного потока.

Выводы к главе.

4. ЦИКЛИЧЕСКИЕ СИСТЕМЫ ОБСЛУЖИВАНИЯ.

4.1. Основная задача анализа ЦСО.

4.2. Типичные схемы пакетирования заявок.

4.3. Параметры потоков пакетов.

4.3.1. Т-пакетирование.

4.3.2. Х-пакетирование.

4.3.3. N-пакетирование.

4.4. Первичные характеристики эффективности ЦСО.

4.5. Сходимость и точность асимптотических приближений.

4.6. Регулирование аритмичности нагрузки.

4.7. Сети циклических систем с пакетированием.

Выводы к главе.

5. АНАЛИТИКО-ИМИТАЦИОННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ ОДНОРОДНЫХ НЕМАРКОВСКИХ СеМО.

5.1. Оптимизация немарковских СеМО и проблема градиентов в ИМ.

5.1.1. Практическая значимость задач оптимизации СеМО.

5.1.2. Задача оптимального распределения нерерывного ресурса однородной немарковской сети.

5.1.3. Проблема вычисления градиентов в имитационном моделировании.

5.2. Двухуровневый двухэтапный метод распределения непрерывного ресурса.

5.2.1. Опорные элементы метода ИГ.

5.2.2. Ускоренный покоординатный спуск (второй этап оптимизации).

5.3. Двухуровневый метод оптимального распределения каналов.

5.3.1. Задача распределения каналов.

5.3.2. Методы решения.

5.3.3. Пример применения последовательного метода.

5.3.4. Аппроксимационный метод оптимизации.

5.4. Точный рекурсивный метод анализа чувствительности.

5.4.1. Краткое описание базового метода (метода Байцера).

5.4.2. Точный рекурсивный расчет коэффициентов чувствительности.

5.5. Оценка вычислительной эффективности РМР.

5.6. Анализ чувствительности в ИМ немарковских СеМО.

5.6.1. Анализ чувствительности к промежуточным показателям.

5.6.2. Анализ чувствительности к переходным вероятностям СеМО.

Выводы к главе.

6. МЕТОДЫ АНАЛИТИКО-ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ БОЛЬШИХ СТОХАСТИЧЕСКИХ СЕТЕЙ.

6.1. О развитии теории графа БА и создании теории графов с НППС.

6.1.1. Исходные положения.

6.1.2. Распределение локальной степени связности вершин в графе БА.

6.1.3. Обобщенная формула распределения локальной степени связности.

6.2. Свойства случайно выбранного ребра графа БА.

6.2.1. Постановка задачи.

6.2.2. Ориентированная версия графа БА.

6.2.3. Совместное распределение вероятностей концевыхепенейв.д.

6.2.4. Маргинальные распределения начальной и концевой степени дуг.

6.2.5. Характеристики случайно выбранного ребра графа БА.

6.3. Коэффициент кластеризации графа БА.

6.3.1. Изменение среднего числа слоев при построении графа.

6.3.2. Коэффициент кластеризации.

6.3.3. Сепарабельная калибровка графа по коэффициенту кластеризации.

6.4. Случайные графы с нелинейным правилом предпочтительного связывания

6.4.1. Исходные положения.

6.4.2. Стационарное распределение степени связности.

6.4.3. Свойства распределений, реализуемых при фиксированном приращении.

6.5. Калибровка генераторов графов с НППС.

6.5.1. Калибровка генераторов с фиксированным приращением.

6.5.2. Калибровка генераторов со стохастическим приращением.

Выводы к главе.

7. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ИСПЫТАНИЯ МЕТОДОВ АИМ.

7.1. Оптимизация режима измерений производительности.

7.1.1. Задача оптимизации режима измерений.

7.1.2. Нулевое приближение.

7.1.3. Первое приближение.

7.1.4. Второе приближение.

7.1.5. Тестовая задача.

7.1.6. Проверка решения тестовой задачи.

7.1.7. Проверка решения в области больших нагрузок.

7.2. Применения асимптотических результатов теории ЦСО.

7.2.1. Постановка задачи.

7.2.2. Асимптотический анализ системы.

7.2.3. Имитационные эксперименты.

7.2.4. Результаты решения задачи моделирования.

7.3. Испытания двухэтапного двухуровневого метода оптимизации СеМО.

7.3.1. Испытания метода на открытых немарковских сетях.

7.3.2. Специальные испытания метода НГ.

7.3.3. Испытания метода НГ на замкнутых сетях.

7.4. Применения аппроксимационного метода распределения каналов.

7.5. Построение моделей больших стохастических сетей.

7.5.1. Калибровка генераторов графов по эмпирическим данным.

7.5.2. Задача структурной идентификации сетей.

Выводы к главе.273 L

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

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

Ограниченные возможности применения точных и приближенных аналитических методов ТМО в задачах проектирования ИВС приводят к широкому использованию современных технологий и программных средств имитационного моделирования (ИМ). При этом ИМ, облегчая широкое внедрение в практику проектирования ИВС формализмов и концепций ТМО, приводит, в то же время, к ряду специфических вычислительных проблем, обусловленных стохастическим характером отклика имитационных моделей и необходимостью корректной обработки этого отклика (например, в целях использования градиентных алгоритмов оптимизации). Проблема использования градиентов - это лишь одна из широко известных общих проблем ИМ систем с очередями. Другие известные проблемы связаны с существованием «критических точек» - таких значений параметров моделируемой системы, вблизи которых происходит резкий рост затрат машинного времени на моделирование. Типичные примеры попадания в окрестности критических точек - это ИМ СМО с близкими к единице коэффициентами загрузки или ИМ событий, имеющих малую вероятность. Подобная ситуация возникает и при моделировании приоритетных систем, в которых интенсивности потоков заявок разных классов различаются на порядки (проблема разномасштабных ин-тенсивностей). Затраты машинного времени возрастают в этой ситуации также на порядки, поскольку для накопления необходимой статистики по классу редко поступающих заявок приходится вместе с ними имитировать и на порядки большее количество заявок других классов.

Наряду с классическими задачами теории ИВС, решаемыми на базе формализмов ТМО, в последнее десятилетие возникло большое число задач иной природы - задач, связанных с беспрецедентным ростом глобальных информационных сетей, в первую очередь - сети Интернет. Быстро развивающиеся большие стохастические сети, подобные сети Интернет, приобретают специфические свойства, обусловливаемые взаимодействием детерминированных «правил» и стохастических факторов роста сетей. Необходимость адекватного математического описания структурных особенностей стохастических сетей, состоящих из сотен тысяч и миллионов узлов и связей, привела к созданию и быстрому в течение последних лет развитию теории неклассических случайных графов (сл.г). Ее наиболее развитую ветвь представляет теория сетей (графов) предпочтительного связывания. Такие графы выращиваются из небольших графов-затравок с помощью простых алгоритмов (генераторов), воспроизводящих способы развития моделируемых сетей. Наиболее широко известен граф Барабаши-Альберт (граф БА), растущий неограниченно в результате циклического добавления к нему приращения графа - новой вершины с фиксированным числом т инцидентных ей ребер. Графы БА обладают свойствами, принципиально отличающими их от классических сл.г. Эрдеша и Реньи. На основе графов БА аналитическими и/или имитационными методами исследуют разнообразные позитивные и негативные процессы, происходящие в реальных сетях, и разрабатывают оптимальные стратегии влияния на эти процессы. Однако, несмотря на лавинообразный рост числа публикаций, посвященных сетям предпочтительного связывания, нерешенными остаются многие важные вопросы, требующие развития аналитической теории таких сетей.

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

В развитие методов АИМ СМО и СеМО большой вклад внесли многие отечественные и зарубежные авторы: В.М. Вишневский, В.А. Жожикашвили, Д.Л. Иглхарт, В.В. Калашников, Дж. Клейнен, И.Н. Коваленко, Н.Ю. Кузнецов, О.И. Кутузов, Б.И. Плакс, Ю.Г. Полляк, Ю.И. Рыжиков, A.JL Толмачев, Д.С. Шедлер, R.B. Gabriel, M. Reinaldo, R.Y. Rubinstein, R. Suri, M. Zazanis и другие. Методы АИМ СМО и СеМО основываются на ТМО, связанной с именами А.К. Эрланга, A.A. Боровкова, Б.В. Гнеденко, JI. Клейнрока, И.Н. Коваленко, А.Н. Колмогорова, Ф. Поллачека, Ю.И. Рыжикова, Т. Саати, А.Я. Хинчина и других ученых.

В развитие методов АИМ больших стохастических сетей (БСС) значительный вклад внесли О.И. Кутузов, Ю.Л. Павлов, Ю.Ю. Тарасевич, А.Л. Эфрос, R. Albert, A. Barabási, В. Bollobas, S.N. Dorogovtsev, Р. Erdös, P.L. Krapivsky, J. Leskovec, M.E.J. Newman, D. Price, S. Redner и A. Rényi.

Объектами исследования в диссертации являются ИВС и другие системы, выполняющие массовую обработку заявок (материалов, данных, денежных средств, документов, клиентов и т.д.), представимые в виде СМО и СеМО, а также БСС типа Интернет.

Предмет исследования: приоритетные СМО, однородные немарковские СеМО, графы предпочтительного связывания и методы их АИМ, разрабатываемые для решения задач, возникающих в проектировании ИВС.

Цель работы: разработка, обоснование, исследование, тестирование и программная реализация математических моделей и методов АИМ, предназначенных для эффективного решения возникающих в теории и инженерной практике проектирования ИВС задач анализа и синтеза СМО, СеМО и БСС.

Задачи исследования:

1. Разработка ускоренных аналитико-имитационных методов моделирования СМО с абсолютными приоритетами при существенно различающихся интенсивностях поступления заявок разных приоритетных классов.

2. Вывод точных и асимптотических соотношений, позволяющих на порядки ускорять ИМ при решении задач анализа и синтеза приоритетных СМО и сводить эти задачи или отдельные этапы их решения к задачам, решаемым аналитическими или элементарными численными методами.

3. Разработка эффективных аналитико-имитационных градиентных и квазиградиентных методов оптимизации однородных немарковских СеМО.

4. Тестирование разработанных методов и алгоритмов АИМ СМО и СеМО на предмет быстродействия и точности, разработка рекомендаций по их использованию и их программная реализация.

5. Разработка эффективных методов АИМ БСС. Развитие теории графа БА. Нахождение «фундаментальной матрицы» графа, определяющей вероятностные свойства случайно выбранного ребра.

6. Создание основ общей теории сл.г. с нелинейным правилом предпочтительного связывания (графов с НППС). Графы с НППС включают графы БА в качестве частного случая. Теория графов с НППС должна решать в общем виде задачу анализа и задачу синтеза генераторов, выращивающих графы с требуемыми структурными характеристиками, соответствующими структурным характеристикам моделируемых реальных БСС. Основы теории графов с НППС требуется реализовать в виде комплекса эффективных программных средств, предназначенных для моделирования реальных больших сетей.

Методы исследования. Решение поставленных задач осуществляется методами ТМО, теории восстановления, теории вероятностей, математической статистики, теории сл.г., численными методами оптимизации, исследования операций и методами АИМ.

Реализация и внедрение результатов работы. Тематика научных исследований, выполненных в диссертации, связана с проводившимися в Ом-ГТУ научно-исследовательскими работами: «Система имитационного моделирования вычислительных комплексов (СИМВК)» (СМОФАП Киевского ПКБ АСУ, № ГОСФАП П007643), «Система имитационного моделирования вычислительного процесса в АСУ (научно - исследовательская тема № 546, № ГР 76090017, № инв. Б853603), «Анализ эффективности организации банка данных в АСУ реального времени» (№ ГР 81088775, инв. № 02860047403), «Разработка и исследование моделей и методов оптимизации оперативного управления механообрабатывающим участком в условиях АСУ» (№ ГР 01. 0031165), «Методология управления нелинейными динамическими фазовыми системами и информационно-вычислительными комплексами в условиях неопределенности» (инв. № 022.007 01269) и др. Полученные в диссертации результаты нашли практическое применение на следующих предприятиях: ООО «АйПро», г. Омск; Омский филиал института математики РАН; ООО «Фарфалле» и используются в учебном процессе при чтении лекций, в курсовом и дипломном проектировании, проведении студенческих НИР и в лабораторных работах на кафедре «Автоматизированные системы обработки информации и управления» ОмГТУ. Издано 7 учебных пособий, в том числе 2 пособия с рекомендациями УМО вузов по университетскому политехническому образованию, и ряд методических указаний. Практическое использование результатов диссертационной работы подтверждено соответствующими актами о внедрении, представленными в прил. Ж к диссертации.

Публикации. По теме диссертации опубликовано более 60 научных работ, в число которых входят: 2 монографии [66, 67], 20 статей в журналах «Перечня ведущих рецензируемых научных журналов и изданий» [68-87], 3 свидетельства программ ЭВМ [63, 90,240], более 12 статей в других изданиях [34,38, 105-120, 151], более 20 работ в материалах международных и всероссийских научно-технических конференций [37,91-104,148,149,153,187,189,192].

Апробация работы. Основные научные положения и результаты диссертационной работы докладывались, обсуждались и были одобрены на следующих международных, всероссийских и региональных конференциях: II Всесоюзной конференции по перспективам и опыту внедрения статистических методов в АСУ ТП, Смоленск, 11-13 мая 1984; Всесоюзном научно-техническом семинаре «Информационное обеспечение автоматизированных систем управления нефтеперерабатывающих предприятий», Омск, 18-20 сентября 1984; Региональной научно-практической конференции «Перспективные направления развития автоматизированных систем управления и их компонентов», Омск, 1989; Межрегиональной научно-практической конференции «Омский регион: исторический опыт, проблемы и пути экономического развития в современных условиях», Омск, 1994; Межрегиональной научно-практической конференции «Омский регион: исторический опыт, проблемы и пути экономического развития в современных условиях», Омск, 1999; V Международной научно-технической конференции «Динамика систем, механизмов и машин», 16-18 ноября 2004; Второй Всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2005), Санкт-Петербург, 19-21 октября 2005; Конференции-конкурсе работ студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Новосибирск, 22-24 февраля 2006; Всероссийской научно-технической конференции студентов, аспирантов и молодых ученых «Научная сессия ТУСУР-2006», 47 мая 2006; Третьей всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2007), Санкт-Петербург, 17-19 октября 2007; Международной конференции «Идентификация систем и задачи управления» (SICPRO'08), Москва, 28-31 января 2008, Институт проблем управления им. В.А. Трапезникова РАН; Всероссийской научно-технической конференции «Россия молодая: передовые технологии - в промышленность», Омск, 2008; Межвузовской научно-практической конференции «Информационные технологии и автоматизация управления», Омск, 20-24 апреля 2009; Четвертой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2009), Санкт-Петербург, 21-23 октября 2009; VII Международной научно-технической конференции «Динамика систем, механизмов и машин» (10-12 ноября 2009); II Межвузовской научно-практической конференции «Информационные технологии и автоматизация управления», Омск, 20-24 апреля 2010; III Региональной научно-практической конференции «Информационные технологии и автоматизация управления», Омск, 9-12 апреля 2011 г.

Структура и объем работы. Диссертация состоит из введения, семи глав, заключения, семи приложений и списка литературы, включающего 286 наименований. Основная часть работы изложена на 300 страницах машинописного текста. Работа содержит 54 рисунка и 27 таблиц.

Выводы к главе

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

К этому ряду методов относится оптимизация однородных немарковских СеМО (задача оптимального распределения непрерывного ресурса и задача оптимального распределения каналов по узлам СеМО), а также расширенный метод редукции графов, внедренный и используемый в омском филиале института математики СО РАН.

Система ИМ 8нпЬ^гарЬ, разработанная в ходе диссертационного исследования, официально зарегистрированная (выданы два свидетельства о ее государственной регистрации) реализует:

- все точные результаты, полученные при анализе структурных свойств безмасштабного графа Барабаши-Альберт;

- точные результаты, полученные в разработанных основах общей теории случайных графов с НППС;

- методику калибровки случайных графов с НППС по статистическим данным о моделируемых сетях;

- ряд имитационных моделей, в которых сетевые процессы имитируются и исследуются на калиброванных моделях случайных графов с НППС.

Ряд методов, разработанных при исследовании безмасштабных графов и случайных графов с НППС, внедрен на предприятии и широко используется в учебном процессе кафедры АСОИУ ОмГТУ.

ЗАКЛЮЧЕНИЕ

В ходе разработки и исследования методов АИМ систем с очередями и стохастических сетей в диссертации получен ряд важных результатов:

- для неэкспоненциальных одноканальных и многоканальных СМО с абсолютными приоритетами разработаны методы асимптотического анализа характеристик цикла обслуживания, найдены асимптотические выражения характеристик очередей, разработан ускоренный метод ИМ таких СМО;

- для систем GI|GI|1 и GI|GI|n найдены точные соотношения, связывающие первые два момента периодов занятости и незанятости, принадлежащих одному периоду регенерации;

- предложен и исследован новый класс моделей массового обслуживания - циклические системы обслуживания с пакетированием неприоритетных заявок, разработаны эффективные методы АИМ таких СМО;

- разработаны и исследованы высокоэффективные двухуровневые ана-литико-имитационные методы оптимизации однородных немарковских СеМО и расширенный метод редукции графов полумарковских процессов;

- разработаны методы точного анализа графа БА и аналитические основы общей теории случайных графов с НППС.

Эти результаты включают следующие конкретные составляющие.

1. При решении проблемы ИМ процессов с разномасштабными интен-сивностями применительно к системам GI2|GI2|n с абсолютными приоритетами получены следующие результаты.

1.1. Выявлены две системы процессов восстановления и накопления, вложенных в цикл обслуживания неприоритетной заявки. На основе асимптотического (по относительной интенсивности а приоритетного потока заявок) анализа характеристик цикла обслуживания разработаны метод суммирования приоритетных периодов занятости (СПЗ) и метод суммирования приоритетных периодов обслуживания (СПО). Метод СПЗ имеет сходство с методом Гейвера (Gaver D.P.), но не связан с предположением о пуассоновском характере потоков заявок, что существенно расширяет область его практического применения. Метод СПО является оригинальным и позволяет выразить асимптотические характеристики цикла обслуживания через известные параметры интервалов поступления и времени обслуживания заявок приоритетных и неприоритетных классов.

1.2. В системе Gl2|GI2|l при фиксированном чистом времени Т обслуживания неприоритетной заявки найдено асимптотическое по а двумерное нормальное распределение суммарного времени прерываний обслуживания заявки и соответствующего числа прерывающих периодов занятости.

1.3. В системе GI2|GI2|n|| (с разделяемой каналами неприоритетной работой) при фиксированном Т найдено асимптотическое по а двумерное нормальное распределение суммарного времени прерываний обслуживания заявки и соответствующего числа прерывающих заявок.

1.4. Для систем GI2IGI211 и Gl2|GI2|n|| найдены асимптотические выражения первых двух безусловных моментов, характеризующих длительность цикла обслуживания неприоритетной заявки и число приоритетных заявок, обслуживаемых в этом цикле. Соответствующее безусловное распределение вероятностей длительности цикла выражено двумя различными асимптотическими представлениями - интегральным представлением и масштабным представлением. На основе интегрального представления получены оценки вероятностей для хвостов распределения длительности цикла.

1.5. Для систем GI|GI|1 и GI|GI|n установлены точные соотношения, связывающие первые и вторые моменты (включая ковариацию) периодов занятости и незанятости с первыми двумя моментами интервалов поступления и времени обслуживания заявок. Эти соотношения позволяют контролировать правильность результатов, получаемых при исследовании СМО GI|GI|1 и GI|GI|n, и тестировать используемые системы ИМ.

1.6. Разработаны методы приближенной декомпозиции системы с абсолютными приоритетами GI2|GI2|n на вложенную систему, сохраняющую только приоритетный поток заявок, и фоновую систему, сохраняющую только неприоритетный поток заявок, время обслуживания которых скорректировано. На основе такой декомпозиции решена проблема разномасштабных ин-тенсивностей при ИМ систем ОЫО^п. Предложен, математически обоснован и протестирован алгоритм их ускоренного моделирования, сформулированы практические рекомендации по его применению. По сравнению с известным методом усреднения вклада интенсивных приоритетных потоков значительно снижена погрешность результатов ускоренного ИМ (благодаря учету вторых моментов) и расширена область его практического применения.

1.7. Разработанные методы декомпозиции систем С12|С12|п и 012|012|п|1 позволяют находить для их вероятностных характеристик аналитические приближения на основе приближений или точных решений, известных для систем 01|С1| 1 и 01|01|п. В частности, методом декомпозиции получены и протестированы приближенные формулы для расчета средней длины очереди неприоритетных заявок для случая сочетания разномасштабных интенсивно-стей с высокой нагрузкой (в системе 012|012|п||) и для случая пуассоновского потока неприоритетных заявок (в системе 012|012|1).

1.8. Методы декомпозиции обобщены на системы с абсолютными приоритетами. Тестирование обобщенных методов показало их хорошую точность в той же области применения (а> 1, ., 10), которая рекомендована для метода декомпозиции систем СТ2|012|п.

2. При исследовании приоритетных ЦСО, предложенных в диссертации в качестве модели многоканальных систем с циклическим накоплением пакетов неприоритетных заявок и их параллельным обслуживанием каналами в фоновом режиме, получены следующие результаты.

2.1. Предложены основные (первичные) показатели эффективности функционирования ЦСО, включающие м.о. и дисперсию календарного времени обработки пакета в фоновом режиме, аритмичность нагрузки ЦСО, а также вероятность превышения порога, установленного для времени обработки пакета.

2.2. Выполнен асимптотический анализ трех типичных способов пакетирования неприоритетных заявок, включающих Т-пакетирование (формирование пакета по заданному времени накопления заявок), Ы-пакетирование (формирование пакета по заданному числу заявок) и Х-пакетирование (формирование пакета по заданной суммарной трудоемкости заявок). Для этих способов пакетирования найдены асимптотические выражения первых двух моментов интервала поступления пакетов, накопленной трудоемкости пакета и числа заявок в нем (включая коэффициенты корреляции между этими сл.в.). Найденные асимптотические выражения характеристик потока пакетов имеют самостоятельное значение и вне задач анализа ЦСО, т.к. накопление пакетов заявок - типичная операция во многих реальных СМО.

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

2.4. Исследованы методы регулирования нагрузки, позволяющие понижать или повышать аритмичность функционирования ЦСО, разработаны соответствующие практические рекомендации.

3. При исследовании и разработке методов оптимизации однородных немарковских СеМО получены следующие результаты.

3.1. Для решения задачи оптимального распределения непрерывного ресурса (стоимости, производительности) по узлам сети разработан эффективный двухуровневый двухэтапный аналитико-имитационный метод оптимизации, ядром которого является оригинальный метод «направляющих гипербол» (НГ), основанный на использовании локальной сепарабельной аппроксимации поверхности отклика. Локальная аппроксимация перенастраивается на каждом шаге поиска точки оптимума путем лишь одного обращения к имитационной модели и используется для выбора приближенно оптимального направления шага и приближенно-оптимальной длины шага. Это выгодно отличает метод НГ от метода приращений, требующего п + 1 обращения к ИМ на каждую итерацию.

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

3.3. Благодаря минимальному числу обращений к имитационной модели СеМО и эффективному использованию градиентов двухуровневый двух-этапный метод позволяет за один сеанс работы на ПК выполнять оптимизацию однородных немарковских СеМО, содержащих десятки и сотни узлов.

3.4. Разработан расширенный по сравнению с методом Байцера (Beizer В.) метод редукции графов случайных задержек. Метод Байцера позволяет рассчитывать м.о. и дисперсию длительности описываемого графом конечного полумарковского процесса с марковской цепью, вложенной в моменты смены состояний, имеющих независимые случайные продолжительности с произвольными ф.р. Разработанный РМР от прототипа - метода Байцера -отличается: а) расширенным набором подстановок (локальных упрощений графа), обеспечивающим эффективную редукцию исходного графа к единственной вершине, помеченной искомыми характеристиками длительности процесса; б) встроенным в ход редукции точным расчетом КЧ найденных характеристик к вариациям исходных параметров модели (включая вариации переходных вероятностей).

Вычисления КЧ осуществляются в РМР методами формального (не численного) дифференцирования и требуют выполнения 0(п ) операций при затратах памяти 0(па), где п - число вершин графа, а значение а близко к 2.

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

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

4. При аналитико-имитационном исследовании больших стохастических сетей получены следующие результаты.

4.1. Разработаны методы точного анализа безмасштабного случайного графа Барабаши-Альберт, описывающего большое количество реальных сетевых структур, которые развиваются последовательным наращиванием узлов и ребер по правилу предпочтительного связывания «богатые становятся богаче». К таким структурам относятся Интернет, социальные сети, сети белковых реакций в организме человека и т.д. Разработанные в диссертации методы в отличие от известных асимптотических {Barabasi A., Albert R., Newman М. Е. J.) и частных точных подходов (Dorogovtsev, S.N., Mendes

J.F.F. Samukhin A.N.) используют технику составления и решения уравнений баланса, позволяющую определять стационарные характеристики бесконечного графа БА. Впервые найдено точное совместное распределение вероятностей концевых степеней случайно выбранной дуги (или ребра) ориентированного (или неориентированного) графа БА и на этой основе получены следующие новые аналитические результаты и методы:

- маргинальные распределения концевых степеней дуг/ребер графа БА;

- асимптотически степенной с показателем 0,5 закон роста максимальной степени вершин от числа N шагов эволюции графа;

- аналитическое выражение коэффициента кластеризации графа БА;

- метод ускоренной генерации графа БА;

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

4.3. Разработаны аналитические основы оригинальной общей теории случайных графов с НППС (граф БА является простым частным случаем таких графов). К числу конструктивных результатов теории относятся:

- метод генерации сл.г. с НППС, использующим произвольную функцию предпочтения и случайное число ребер в приращениях графа;

- представленное в общем виде точное стационарное распределение локальной степени связности вершин в графах с НППС;

- метод калибровки генератора графов с фиксированным числом ребер в приращениях графа;

- метод калибровки генератора графов со случайным числом ребер в приращениях графа;

- методика калибровки генератора графов по эмпирическим распределениям степени связности вершин в моделируемых сетях;

- калиброванные модели сети автономных систем Интернет, сети маршрутизаторов Интернет и сети актеров, участвующих в общих фильмах, построенные на основе реальных данных, описывающих связи между десятками и сотнями тысяч узлов в этих сетях;

- рекомендации по практическому использованию графов с НППС при моделировании БСС (в том числе сети Интернет и сетей в составе Интернет);

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

Применение НППС расширяет возможности моделирования больших сетей, в которых вероятности выбора узлов очередными приращениями для связывания с ними не обязательно пропорциональны степеням связности этих узлов. Точные формулы распределений степени связности, найденные в диссертации для сл.г. с НППС, включают ранее установленные результаты в качестве частных случаев. Разработанные на основе найденных формул методы калибровки генераторов просты в практическом применении и позволяют быстро выращивать графы, содержащие миллионы вершин и точно реализующие заданные распределения степени связности. Полученные в диссертации при разработке методов АИМ БСС результаты обеспечивают возможность эффективного решения задач структурной идентификации, моделирования и оптимизации больших сетей. Калиброванные сл.г. могут использоваться для ИМ, прогнозирования и оптимизации процессов, происходящих или планируемых для реализации в исследуемых сетях, или для тестирования разнообразных алгоритмов и программ, предназначенных для работы с большими графами.

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

1. Акимов C.B. Методология создания имитационных моделей класса объектов//Имитационное моделирование. Теория и практика. Матер. 1. Все-росс. конф. (ИММОД-2005), Т. 1. - СПб. : ФГУП ЦНИИ ТС, 2005. - С. 77-80.

2. Аладьев В. Известия АН Эст. ССР, Физика и Математика, 21. 1972. -С. 80-83.

3. Аладьев В.З., Хунт Ю.Я., Шишаков M.JI. Математическая теория классических однородных структур. Таллинн-Гомель : TRG & VASCO & Salcombe Eesti Ltd. - 1998. - 300 с.

4. Ализар А. Маршрутизация сетей по принципу пчелиного роя // URL: http://www.webplanet.rU/news/intemet/2004/9/13/bee.html (дата обращения 19.08.2011).

5. Анисимов В.В. Асимптотические методы анализа стохастических систем. Тбилиси : Мецинереба. - 1984. - 178 с.

6. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы / пер. с англ. М. : Мир. - 1982. - 583 с.

7. Байхельт Ф., Франкен П. Надежность и техническое обслуживание. Математический подход: Пер. с нем. М. : Радио с связь. - 1988. - 392 с.

8. Байцер Б. Архитектура вычислительных комплексов М. : Мир. -1974. - Т. 1 -664 с.

9. Байцер Б. Микроанализ производительности вычислительных систем. М. : Радио и связь. - 1983. - 360 с.

10. Бандман O.JI. Параллельная реализация асинхронных клеточных автоматных алгоритмов // Вестник ТГУ. Прил. № 18, авг. 2006 г. : Матер. Междунар., всеросс. и регион, научн. конф., симпоз., школ, проводимых в ТГУ.-С. 76-81.

11. Барабаши А., Бонабо Э. Безмасштабные сети // В мире науки, №8, 2003.-С. 55-63.

12. Бараш Л. Массивы хранения и . теория протекания / Компьютерное Обозрение, №36, 16-22 сент. 2003. URL: http://ko.com.ua/massivyhraneniyaiteoriyaprotekaniya 14753 (дата обращения 19.08.2011).

13. Башарин Г.П. Массовое обслуживание в телефонии. М. : Наука. -1968.-246 с.

14. Бахвалов Л.: Компьютерное моделирование длинный путь к сияющим вепшинам? // Компьютерра. - № 40 (217). - 1997.- С26-36.

15. Беляков В.Г., Митрофанов Ю.И. К исследованию замкнутых сетей массового обслуживания большой размерности // Автоматика и телемеханика. 1982. - №7. - С. 61-69.

16. Бернатович A.C. Многокритериальная оптимизация и анализ устойчивости в имитационном моделировании. В кн.: Электронная техника. Экономика и системы управления. - М. : ЦНИИ Электроника, вып. 2 (22). -1979.-с. 81-99.

17. Бернатович A.C. Применение методов планируемого эксперимента для исследования сложных имитационных моделей. В кн.: Электронная техника. Экономика и системы управления. - М. : ЦНИИ Электроника, вып. 1 (22).-1977.-с. 37-51.

18. Билик Р.В., Петухова Н.В., Ребортович Б.И. Приближенный метод анализа замкнутых сетей массового обслуживания // Автоматизтрованные системы массового обслуживания / Ин-т пробл. управления. М. - 1985. - С. 5-18.

19. Блехман И.И. и др. Прикладная математика: предмет, логика, особенности подходов. Киев : Наук. Думка. - 1976. - 269 с.

20. Богатырев В.А., Литвак Е.И., Мизин И.А., Ушаков И.А. Системы с монотонной структурой // Надежность технических систем: справочник / Под ред. И.А. Ушакова. М. : Радио и связь. - 1985. - С. 96-111.

21. Богоявленская О.Ю. Анализ случайного потока, генерируемого транспортным протоколом с обратной связью, в сети передачи данных // Автоматика и телемеханика, № 12. 2003. - С. 60-69.

22. Богуславский Л.Б., Ляхов А.И. Оценка производительности распределенных информационно-вычислительных систем архитектуры «Клиент-Сервер» // Автоматика и телемеханика. 1995. - № 9. - С. 160-175.

23. Боровков A.A. Математическая статистика. Учебник. - М. : Наука. ГРФМЛ.- 1984.-472 с.

24. Боровков A.A. Теория вероятностей: Учеб. пособие для вузов. 2-е изд., перераб. и доп. - М. : Наука. ГРФМЛ. - 1986. - 432 с.

25. Борщев A.B. Практическое агентное моделирование и его место в арсенале аналитика // Exponenta Pro, № 3-4. 2004. - С. 38-47.

26. Бочаров П.П. Приближенный метод расчета разомкнутых неэкспоненциальных сетей МО конечной емкостью с потерями или блокировками // Автоматика и телемеханика. 1987. - №1. - С. 160-179.

27. Бочаров П.П. Сеть массового обслуживания с сигналами со случайной задержкой // Автоматика и телемеханика. 2002. - №9. - С. 90-101.

28. Бочаров П. П., Гаврилов Е.В., Д'Апиче Ч., Печинкин A.B. О декомпозиции сетей массового обслуживания с зависимым обслуживанием и отрицательными заявками // Автоматика и телемеханика, № 1, 2004. С. 91.

29. Бочаров Н.П., Гаврилов Е.В., Печинкин A.B. Экспоненциальная сеть массового обслуживания с зависимым обслуживанием, отрицательными заявками и изменением типа заявок // Автоматика и телемеханика, № 7. 2004.

30. Бройер JL, Дудин А.Н., Клименок В.И., Царенков Г.В. Двухфазная система BMAP|g|l|N —> РН|1|М с блокировкой // Автоматика и телемеханика, № 1,2004.- С. 101.

31. Бронштейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно-вычислительных системах. М.: Наука. - 1976. - 220 с.

32. Бухштаб A.A. Теория чисел. М. : Просвещение. - 1966. - 384 с.

33. Быкова В.В., Задорожный В.Н. Оценка трудоёмкости алгоритма методом редукции графа. В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. - Омск. - 1979. - С. 120-124.

34. Васильев Ф.П. Численные методы решения экстремальных задач. -М. : ГРФМЛ, 1980. 520 с.

35. Васильева JI.A., Горцев А.М. Оценивание длительности мертвого времени асинхронного дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика, № 12,2003. С. 70-80.

36. Васин А.Ю., Задорожный В.Н. Модели и методы решения задачи двумерной контейнерной упаковки / Россия молодая: передовые технологии в промышленность: матер. Всерос. науч.-техн. конф. - Омск: Изд-во Ом-ГТУ, 2008.-Кн. 2.-С. 12-15.

37. Васин А.Ю., Задорожный В.Н. Математические алгоритмы оптимизации в решении производственных задач по автоматизации оконного производства / Современные окна Сибири и Дальнего Востока, 2008. №2 - С. 16-17.

38. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М. : Техносфера. - 2003. - 512 с.

39. Вишневский В.М., Герасимов А.И. Исследование потоков в замкнутых экспоненциальных сетях массового обслуживания // Проблемы управления и теории информации. 1983. - Т. 12, № 6. - С.16-22.

40. Вишневский В.М., Гузаков H.H., Ляхов А.И. Оценка максимальной производительности беспроводного доступа в Интернет // Автоматика и телемеханика, № 9, 2004. С. 52-70.

41. Вишневский В.М., Круглый З.Л. Оптимизация замкнутых стохастических сетей // Автоматика и телемеханика. 1987. - № 2. - С. 72-83.

42. Вишневский В.М., Пороцкий С.М. Моделирование ведомственных систем электронной почты // Автоматика и телемеханика. 1996. № 12. -С. 48-57.

43. Вишневский В.М., А.И. Ляхов, Даскалова Хр. Вероятностные методы исследования широкополосных беспроводных сетей, Proc. Int. Workshop "Distributed Computer and Communication Networks" (DCCN-2005). Sofia, Bulgaria, April 23-29. 2005. - pp. 9-18.

44. Вишневский В.М. Аналитические методы исследования телеавтоматических систем массового обслуживания // Автоматизированные системымассового обслуживания / Ин-т проблем управления. М., 1980. - С. 5-18.

45. Волфрам С. Научные исследования / Пер. Бряндинской А. А. / Современный компьютер. М. : Мир. - 1986. С. 158-173.

46. Гадасин В.А., Ушаков И.А. Надежность структурно-сложных ретрансляционных сетей // Надежность технических систем: справочник / Под ред. И.А. Ушакова. М. : Радио и связь. - 1985. - С. 457-470.

47. Гарднер М. Крестики-нолики / Пер. с англ. -М. : Мир. 1988. - 352 с.

48. Герасимов А.И. Оптимизация замкнутых сетей массового обслуживания с несколькими классами сообщений // Пробл. передачи информ., 30:1 (1994), С. 85-96.

49. Гинсберг К.С. Неклассическая модель структурной идентификации // Тр. Междунар. конф. «Параллельные вычисления и задачи управления» (РАСО1 2001). Москва. 2-4 окг. 2001. - М. : ИПУ РАН. - 2001. Раздел 1. - С. 121-140.

50. Гинсберг К.С. Системные закономерности и теория идентификации // Тр. Междунар. конф. «Параллельные вычисления и задачи управления» (РАСО' 2001). Москва. 2-4 окг. 2001.-М. : ИПУ РАН.-2001. Раздел 1.-С. 103-120.

51. Гнеденко Б.В., Даниэлян Э.А. и др. Приоритетные системы обслуживания. М. : Издательство Московского университета. - 1973. - 447 с.

52. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М. : Наука. - 1987. - 336 с.

53. Голованов О.В. и др. Моделирование сложных дискретных систем на ЭВМ третьего поколения. Опыт применения GPSS. М. : Энергия. - 1978. - 178 с.

54. Головкин Б.А. Параллельные вычислительные системы. М. : Наука. - 1980. - 520 с.

55. Губанов Д.А., Новиков Д.А., Чхартишвили А.Г. Социальные сети: модели информационного влияния, управления и противоборства. М. : Изд-во физико-математической литературы, 2010. - 228 с.

56. Д'Апиче Ч., Кристофано М.Л., Печенкин A.B. Система обслуживания MAPK|GK|l|oo с обобщенной дисциплиной преимущественного разделения прибора // Автоматика и телемеханика, № 12, 2004. С. 110-114.

57. Де Гроот М. Оптимальные статистические решения. М. : Мир. -1974.-492 с.

58. Димитров Б.Н., Рыков В.В., Круглый 3.JI. Периодические пуассо-новские процессы и распределения с почти отсутствующей памятью // Автоматика и телемеханика, № 10, 2004. С. 85-100.

59. Долгий Э. Храните свои терабайты в ящике // «Экспресс-Электроника» #8(117)/2004 / URL: http://citforum.ru/hardware/data/tbbox.shtml.

60. Дудин A.H., Ким Ч.С., Семенова O.B. Оптимальное многопороговое управление входным потоком для системы обслуживания GI|PH|1 с ВМАР-потоком отрицательных запросов // Автоматика и телемеханика, № 9, 2004. -С. 71-79.

61. Ермаков С.М., Михайлов Г.А. Статистическое моделирование / 2-е изд., доп. М. : Наука, 1982. - 296 с.

62. Ершов Е.С., Задорожный В.Н. Комплекс программ оптимизации сетей массового обслуживания «RedOpt» (ОФЭРНиО № 16589) / М. : ИНИМ РАО, ОФЭР «Наука и образование», 2011. - № 50201150081.

63. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М. : Радио и связь, 1988. - 192 с.

64. Журбенко И.Г., Кожевникова И.А., Клиндоухова О.В. Определение критической длины последовательности псевдослучайных чисел // Вероятностно-статистические методы исследования. М.: Изд-во МГУ. - 1983. - С. 18-39.

65. Задорожный В.Н. Аналитико-имитационные исследования систем и сетей массового обслуживания: монография / В.Н. Задорожный. Омск : Изд-во ОмГТУ. - 2010. - 280 с.

66. Задорожный В.Н. Аналитико-имитационные исследования Больших Сетевых Структур: монография / В.Н. Задорожный. Омск : Изд-во ОмГТУ, 2011.-208 с.

67. Задорожный В.Н. Асимптотический анализ систем с интенсивными прерываниями // Автоматика и телемеханика, 2008. №2 - С. 86-96.

68. Задорожный В.Н. Оптимизация однородных немарковских сетей массового обслуживания // Проблемы управления, 2009. № 6. - С. 68-75).

69. Задорожный В.Н. Случайные графы с нелинейным правилом предпочтительного связывания // Проблемы управления, 2010. № 6. - С. 2-11.

70. Задорожный В.Н., Литунов С.Н., Штриплинг С.Л. К вопросу о проблеме муара при воспроизведении изображений печатными способами // Известия высших учебных заведений. Проблемы полиграфии и издательского дела, 2007. -№ 1. С. 30-39.

71. Задорожный В.Н. Общая статистическая структура простейших клеточных автоматов // Омский научный вестник, 2005. № 2 (31) - С. 150-156.

72. Задорожный В.Н. Анализ систем с приоритетами методом декомпозиции // Омский научный вестник, 2005. № 3 (32) - С. 126-132.

73. Задорожный В.Н., Пуртов А.М. Анализ чувствительности в имитационном моделировании сетей массового обслуживания // Омский научный вестник, 2005. -№ 4 (33). С. 165-171.

74. Задорожный В.Н. Асимптотический анализ периодов повышенной нагрузки в приоритетных системах // Омский научный вестник, 2006. № 3 (36).-С. 117-124.

75. Задорожный В.Н., Семенова И.И. Управление сложными техническими объектами и парадигмы имитационного моделирования // Омский научный вестник, № 6 (41). 2006. - С. 115-117.

76. Задорожный В.Н., Ершов Е.С., Канева О.Н. Двухуровневые градиентные методы для оптимизации сетей с очередями // Омский научный вестник, 2006. № 7 (43). - С. 119-126.

77. Задорожный В.Н. Распределение календарного времени обслуживания неприоритетных заявок в системах с абсолютными приоритетами // Омский научный вестник, 2006. № 8 (44). - С. 124-131.

78. Задорожный В.Н. Комбинированный метод моделирования циклических систем обслуживания // Омский научный вестник, 2006. № 9 (46). -С. 156-163.

79. Задорожный В.Н. О качестве программных генераторов случайных чисел // Омский научный вестник, 2009. № 2 (80). - С. 199-205.

80. Задорожный В.Н., Ершов Е.С. Градиентный метод и программа оптимизации сетей с очередями // Омский научный вестник, 2009. — № 2 (80). -С. 205-210.

81. Задорожный В.Н., Юдин Е.Б. Статистически однородные случайные графы: определение, генерация, применение // Омский научный вестник, 2009.-№3 (83).-С. 7-13.

82. Задорожный В.Н., Юдин Е.Б. Точная теория графа Барабаши-Альберт // Омский научный вестник, 2009. № 3 (83). - С. 13-18.

83. Задорожный В.Н. Распределение каналов в однородных немарковских сетях с очередями // Омский научный вестник, 2010. № 1 (84). - С. 5-10.

84. Задорожный В.Н. Методы калибровки аддитивных генераторов стохастических графов // Омский научный вестник, 2010. № 1 (87). - С. 171 -176.

85. Задорожный В.Н. Предпосылки создания фрактальной теории массового обслуживания // Омский научный вестник, 2010. № 2(90) - С. 182-187.

86. Задорожный В.Н., Тулубаев Д.А. Метамодель систем оперативно-диспетчерского управления сложными крупномасштабными организационно-техническими объектами // Омский научный вестник, 2011. № 1 (97) - С. 19-23.

87. Задорожный В.Н. Разработка и исследование методов имитационного моделирования производительности вычислительных систем. Авто-реф. дис. канд. техн. наук. - Омск. - 1983. - 16 с.

88. Задорожный В.Н., Юдин Е.Б. Система агентного моделирования «Simbigraph» (ОФЭРНиО № 16539) / М. : ИНИМ РАО, ОФЭР «Наука и образование», 2011. -№ 50201050316.

89. Задорожный В.Н., Борзенков Д.П. Моделирование информационно-вычислительных систем по макродинамическим показателям // Динамика систем, механизмов и машин: Матер. V Междунар. науч.-техн. конф. Кн. 1. -Омск, 2004.-С. 351-355.

90. Задорожный В.Н. Методы ускоренной имитации процессов с интенсивными прерываниями // Имитационное моделирование. Теория и практика. Матер. II Всеросс. конф. (ИММОД-2005), Т.1. СПб. : ФГУП ЦНИИ ТС, 2005.-С. 101-106.

91. Задорожный В.Н. Асимптотические приближения в имитационном моделировании систем с очередями // Имитационное моделирование. Теория и практика. Матер. III Всеросс. конф. (ИММОД-2007), Т.1. СПб. : ФГУП ЦНИИТС, 2007. - С.117-122.

92. Задорожный В.Н., Донец A.A. Алгоритм структурной оптимизации сетей с очередями // Имитационное моделирование. Теория и практика. Матер. Ш Всеросс. конф. (ИММОД-2007), Т.1. СПб.: ФГУП ЦНИИТС, 2007. - С. 123-128.

93. Задорожный В.Н., Юдин Е.Б. Мультиагентный подход в имитационном моделировании клеточных автоматов и сетевых структур // Имитационное моделирование. Теория и практика. Матер. Ш Всеросс. конф. (ИММОД-2007), Т.2. СПб.: ФГУП ЦНИИТС, 2007. - С.72-77.

94. Задорожный В.Н. Методы двухуровневого моделирования систем с очередями // Труды VII Международной конференции «Идентификация систем и задачи управления» SICPRO '08. Москва, 28-31 января 2008. - С. 1484-1563.

95. Задорожный В.Н., Ершов Е.С. Оптимизация сетей массового обслуживания в ANYLOGIC 6 // Россия молодая: передовые технологии в промышленность: матер. Всерос. науч.-техн. конф., Кн. 2. - Омск: Изд-во ОмГТУ, 2008.-С. 19-23.

96. Задорожный В.Н., Юдин Е.Б. Использование мультиагентного моделирования в исследовании сложных сетевых структур // Россия молодая: передовые технологии в промышленность: матер. Всерос. науч.-техн. конф., Кн. 2. - Омск : Изд-во ОмГТУ. - 2008. - С. 27-31.

97. Задорожный В.Н. К дискуссии о качестве датчиков случайных чисел // Имитационное моделирование. Теория и практика. Матер. IV-й Всеросс. конф. (ИММОД-2009). СПб. : ЦТ СС, 2009. - С. 128-134.

98. Задорожный В.Н. Оптимизация немарковских сетей с очередями // Динамика систем, механизмов и машин: Матер. VII Междунар. науч.-техн. конф., Кн. 1. Омск, 2009. - С. 288-292.

99. Задорожный В.Н., Мызникова Т.А. Рекурсивный анализ чувствительности для метода Байцера // Деп. в ВИНИТИ, № 5490 В88. - 29 с.

100. Задорожный В.Н., Мызникова Т.А. Автоматизация анализа трудоемкости вычислительных алгоритмов // Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Омск : ОмПИ, 1984. - С. 4-9.

101. Задорожный В.Н. Разработка методов ускоренного моделирования разномасштабных по интенсивности процессов обслуживания // Омский научный вестник, 2004. № 3 (28) - С. 49-54.

102. Задорожный В.Н., Кузнецова Е.М. К разработке имитационной модели организации вычислительного процесса на вычислительном комплексе /В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Новосибирск, 1977. - С. 53-57.

103. Задорожный В.Н. Реализация логических функций арифметическими выражениями / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Новосибирск, 1978. - С. 53-57.

104. Задорожный В.Н., Кузнецова Е.М. Адекватность и уровень детализации имитационной модели вычислительных процессов / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. -Омск, 1979.-С. 109-112.

105. Задорожный В.Н., Кузнецова Е.М. Методика моделирования многомашинных вычислительных комплексов в АСУ / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Омск, 1980.-С. 106-110.

106. Задорожный В.Н., Кузнецова Е.М., Пуртов A.M. Макрооператорыдля моделирования многомашинных вычислительных комплексов. В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. - Омск, 1981. - С. 88-90.

107. Задорожный В.Н. Об одном свойстве рекуррентных потоков / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Омск, 1979. - С. 77-80.

108. Задорожный В.Н., Кузнецова Е.М., Пуртов A.M. К вопросу использования методов оптимизации при имитационном моделировании / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Омск, 1982. - С. 105-107.

109. Задорожный В.Н., Пуртов A.M. О возможностях моделирования баз данных в СИМВК / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. Омск, 1982. - С. 145-147.

110. Задорожный В.Н., Кузнецова Е.М., Попов А.Ю. О путях автоматизации анализа и синтеза структур вычислительных систем / В кн.: Автоматизация анализа и синтеза структур ЭВМ и вычислительных алгоритмов. -Омск, 1982.-С. 142-147.

111. Задорожный В.Н., Серов В.Ф. Принципы построения диалоговой системы имитационного моделирования вычислительных комплексов / Анализ и синтез элементов и структур управляющих ЭВМ. Омск, 1986. - С. 61-64.

112. Задорожный В.Н., Попов А.Ю. Анализ пропускной способности автоматизированных систем диспетчерского управления / Анализ и синтез элементов и структур управляющих ЭВМ. Омск, 1986. - С. 74-80.

113. Задорожный В.Н., Меньшов В.А., Борзенков Д.П. Оценка трудоемкости вкладных операций с помощью имитационной модели / Банковские технологии, № 4, 2002. С. 48-49.

114. Задорожный В.Н., Кузнецова Е.М., Быкова В.В. Система имитационного моделирования вычислительного процесса в АСУ / Отчёт по научно исследовательской теме № 546, № ГР 76090017,1979, № инв. Б853603,22.05.80.

115. Емельянов C.B., Калашников В.В., Лутков В.М., Немчинов Б.В. Методологические вопросы построения имитационных систем: обзор. М. : ЦНТИ, 1978. - 88 с.

116. Иглхарт Д.Л., Шедлер Д.С. Регенеративное моделирование сетей массового обслуживания: Пер. с англ. / Под ред. В.В. Калашникова. М. : Радио и связь, 1984. - 136 с.

117. Имитационное моделирование процессов самоорганизации наночастиц / М.В. Алфимов, P.M. Кадушников, H.A. Штуркин, В.М. Алиевский, П.В. Лебедев-Степанов // Российские нанотехнологии, Т.1, № 1-2. 2006. - с. 127-133.

118. Исследование операций: Пер. с англ. / Под ред. Дж. Моудера и С. Элмаграби. М. : Мир., 1981. - Т.1: Методологические основы и математические методы. - 712 е., Т.2: Модели и применения. - 677 с.

119. Каминский В.М. Оптимизация замкнутых стохастических сетей с экспоненциальным обслуживанием // Изв. АН СССР. Техническая кибернетика, 1980. № 6. - С. 68-76.

120. Карпов Ю.Г. Имитационное моделирование систем. Введение в моделирование с AnyLogic 5. СПб. : БХВ-Петербург, 2005. - 400 с.

121. Кац В.М., Лившиц К.И., Назаров A.A. Исследование нестационарных бесконечнолинейных систем массового обслуживания и их применение к анализу экономико-математических моделей // Вестник ТГУ, 2002. -№275.-С. 189-192.

122. Киндлер Е. Языки моделирования // пер. с чешского. М. : Энер-гоатомиздат, 1985. -288 с.

123. Клейнен Дж. Статистические методы в имитационном моделировании : Пер с англ. / Под ред. Ю.П.Адлера и В.Н.Варыгина. М. : Статистика, 1978.-Вып. 1.-221 е., Вып. 2.-335 с.

124. Клейнрок Л. Вычислительные системы с очередями / Пер. с англ. под ред. Б.С. Цыбакова. М.: Мир, 1979. - 600 с.

125. Клейнрок Л. Теория массового обслуживания / пер. с англ. И.И. Грушко; ред. В.И. Нейман. М. : Машиностроение, 1979. - 432 с.

126. Климов Г.П., Матвеев В.Ф. Системы массового обслуживания с ненадежным прибором // Надежность технических систем: справочник / Под ред. И.А. Ушакова. М.: Радио и связь, 1985. - С. 169-183.

127. Кнут Д. Искусство программирования для ЭВМ. Т. 2: Получисленные алгоритмы. М.: Мир, 1977. - 728 с.

128. Коваленко И.Н., Кузнецов Н.Ю. Методы расчета высоконадежных систем. М. : Радио и связь, 1988. - 176 с.

129. Коваленко И. Н., Кузнецов Н. Ю. Моделирование высоконадежных систем // Надежность технических систем: справочник / Под ред. И. А. Ушакова. М.: Радио и связь, 1985. - С. 194-204.

130. Кокс Д., Льюис П. Статистический анализ последовательности событий. М.: Мир. - 1969. - 312 с.

131. Кокс Д.Р. Теория восстановления / Кокс Д.Р., СмитВ.Л.: Пер. с англ. под ред. Ю.К. Беляева. М. : Сов. радио, 1967. - 300 с.

132. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. / пер. с англ. М. : Наука, 1973. - 832 с.

133. Королюк B.C., Ушаков И.А., Франкен П., Шубинский И.Б., Штреллер А. Специальные методы исследования систем с восстановлением / Надежность технических систем: справочник / Под ред. И.А. Ушакова. М. : Радио и связь, 1985. - С. 470-495.

134. Коцюруба П.И., Назаров A.A. Локальная диффузионная аппроксимация процесса изменения состояний неустойчивой сети случайного доступа в окрестности асимптотического среднего / Пробл. передачи информ,2004, 40:1.-С. 85-97.

135. Коцюруба П.И., Назаров A.A. Исследование асимптотических средних характеристик немарковских моделей неустойчивых сетей случайного доступа / Пробл. передачи информ, 2003, 39:3. С. 77-86.

136. Крейн М., Лемуан О. Введение в регенеративный анализ моделей / пер. с англ. М. : Наука, 1982. - 104 с.

137. Кругликов В.К., Тарасов В.Н. Анализ и расчет сетей массового обслуживания с использованием двумерной диффузной аппроксимации // Автоматика и телемеханика, 1983. № 8. - С. 72-84.

138. Кузнецов Н.Ю. Аналитико-статистический метод нахождения нестационарного коэффициента готовности у альтернирующего процесса восстановления // Кибернетика, 1986. -№ 1. С. 125-127.

139. Кузнецов Н.Ю. Вычисление коэффициента оперативной готовности восстанавливаемой системы аналитико-статистическим методом // Кибернетика, 1985. -№ 5. С. 95-101.

140. Кузнецов Д. Ю., Назаров А. А. Исследование сети связи, управляемой адаптивным протоколом случайного множественного доступа, в условиях критической загрузки / Пробл. передачи информ, 2004,40:3. С. 69-80.

141. Кузнецова Е.М., Задорожный В.Н., Попов А.Ю. Применение статистического моделирования при проектировании АСУ ТП // Перспективы и опыт внедрения статистических методов в АСУ ТП : Тез. докл. II Всесоюзной конференции. Смоленск, 1984. - С. 126-127.

142. Кун Т. Структура научных революций / Пер. с англ. И.З. Налетова. Общая ред. и послесловие С.Р.Микулинского и Л.А.Марковой. М. : Прогресс, 1975; 2 изд. 1977. - 300 с.

143. Кутузов О.И., Задорожный В.Н. Аналитико-статистический метод для расчета высоконадежных систем связи // Техника средств связи. Техника проводной связи, 1990, Вып. 1. С. 121-130.

144. Лебедев A.B. Вероятностные методы классификации клеточных автоматов / Фундаментальная и прикладная математика, 2002. Т.8, № 2. - С. 621- 626.

145. Левин В. И. Логическая теория надёжности сложных систем. М. : Энергоиздат, 1985. - 128 с.

146. Линник Ю.В. Метод наименьших квадратов и основы теории наблюдений. M. : Гос. изд-во физ.-мат. лит., 1962. - 352 с.

147. Липаев В.В. Распределение ресурсов в вычислительных системах.- М. : Статистика, 1979. 249 с.

148. Лычкина H.H. Современные технологии имитационного моделирования и их применение в информационных бизнес-системах и системах поддержки принятия решений // Матер. II Всеросс. конф. (ИММОД-2005), Т. 1. СПб. : ФГУП ЦНИИ ТС, 2005. - С. 25-31.

149. Макдугал М. Моделирование на уровне системы // Автоматизация проектирования вычислительных систем. Языки, моделирование и базы данных / Брейер M. М. : Мир, 1979. - 463 с.

150. Маклаков C.B. BPwin и Erwin. CASE-средства разработки информационных систем. М. : Диалог - МИФИ, 1999. - 256 с.

151. Максимей И.В. Функционирование вычислительных систем (Измерения и анализ). -М. : Советское радио, 1979. 272 с.

152. Мандельброт Б. Фрактальная геометрия природы М. : Институт компьютерных исследований, 2002. - 656 с.

153. Материалы II Всероссийской конференции «Имитационное моделирование. Теория и практика» (ИММОД-2005). СПб., 19-21 окт. 2005. -СПб. : ФГУП ЦНИИ ТС, 2005.-Т. 1. З06с.,-Т.2. 308 с.

154. Микадзе И.С., Хочолава В.В., Хуродзе P.A. Виртуальное время ожидания в однолинейной системе с ненадежным прибором // Автоматика и телемеханика, № 12, 2004. С. 115-124.

155. Моисеев H.H. Математические задачи системного анализа: Учеб. пособие для вузов по спец. «Прикладная математика». М. : Наука, 1981. - 487 с.

156. Моисеев H.H. Математика ставит эксперимент. М. : Наука, 1979.- 224 с.

157. Назаров A.A. Управляемые системы массового обслуживания и их оптимизация. Томск : Изд-во Томск, ун-та, 1984. - 240 с.

158. Назаров A.A. Формулы Энгсета для неоднородных немарковских систем массового обслуживания и их применение в сетях связи / Пробл. передачи информ, 1998, 34:2. С. 109-116.

159. Назаров A.A., Шохор C.JI. Исследование управляемого несинхронного множественного доступа в спутниковых сетях связи с оповещением о конфликте / Пробл. передачи информ., 2000, 36:1. С. 77-89.

160. Назаров A.A. Исследование процесса изменения числа заявок в нестационарной немарковской бесконечнолинейной системе массового обслуживания // Вестник ТГУ, № 280, 2003. С. 230-231.

161. Назаров A.A., Цой С.А. Исследование математической модели двухка-нальной сети случайного доступа // Вестник ТГУ, 2003. № 280. - С. 232-238.

162. Назаров A.A., Терпугов А.Ф. Теория массового обслуживания: Учеб. пособие. Томск, 2004. - 228 с.

163. Нгуен Д.Т. Оценка погрешностей аналитических методов расчета и исследование СМО типа G|G|1 // Имитационное моделирование. Теория и практика. Матер. III Всеросс. конф. (ИММОД-2007), Т.1. СПб. : ФГУП ЦНИИТС, 2007. - С.200-204.

164. Нейлор Т. Машинные имитационные эксперименты с моделями экономических систем. М.: Мир, 1975. 502 с.

165. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. М. : Изд-во МГТУ им. Н.Э. Баумана, 2000. - 360 с.

166. Ольшанский А.Ю. Плоские графы // Соросовский Образовательный Журнал, 1996. -№ 11.-С. 117-122.

167. Основы теории вычислительных систем / под ред. С.А. Майорова.- М. : Высшая школа, 1978. 408 с.

168. Оценка системы моделирования GPSS World. Режим доступа: http://gpss.ru/paper/ryzhikov/indexw.html (дата обращения: 01.10.2010Х

169. Парадимитру X., Стейнглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М. : Мир, 1984. - 510 с.

170. Петров A.A. Экономика модели. Вычислительный эксперимент. -М. : Наука, 1996. 250 с.

171. Печинкин A.B., Тришечкин С.И. Система SM2|MSP|n|r с дисциплиной случайного выбора на обслуживание и общим накопителем // Автоматика и телемеханика, № 11, 2003. С. 106.

172. Плакс Б.И. Расчет надежности систем со сложной структурой ускоренным методом Монте-Карло // Изв. АН СССР. Техническая кибернетика, 1983.-№6.-С. 158-162.

173. Полляк Ю.Г. Оценка малых вероятностей при статистическом моделировании систем // Изв. АН СССР, Техн. кибернетика, 1973. №2. - С. 197-202.

174. Полляк Ю.Г. Вероятностное моделирование на ЭВМ. М. : Сов. радио, 1971.-400 с.

175. Полляк Ю.Г. Некоторые способы повышения точности статистического моделирования систем массового обслуживания. Изв. АН СССР. Техн. кибернетика, 1970. -№ 4, С. 75-84.

176. Полляк Ю.Г. Оценка точности статистического моделирования систем массового обслуживания. Изв. АН СССР. Техн. кибернетика, 1970.- № 1, С. 80-88.

177. Пригожин И., Стенгерс И. Порядок из хаоса. Новый диалог человека с природой / Пер. с англ.; Общ. ред. В.И. Аршинова, Ю.Л. Климонтови-ча и Ю.В. Сачкова. M : Прогресс, 1986. - 432 с.

178. Пуртов A.M. Задорожный В.Н., Использование графов для сокращения имитационных экспериментов // Имитационное моделирование. Теория и практика. Матер. II Всеросс. конф. (ИММОД-2005), Т.1. СПб. : ФГУП ЦНИИ ТС, 2005.-С. 152-157.

179. Пуртов А. М. Анализ производительности сетей ЭВМ на графах и имитационных моделях.: Автореф. дисс. на соиск. учен, степени канд. техн. наук (05.13.16)./ Науч. рук. В. А. Шапцев Омск : ИИТПМ СО РАН, 1995. - 17 с.

180. Пуртов A.M. Интеграция технологии ГИС и метода редукции графов для анализа транспортных сетей // Омский научный вестник, 2011. № 1 (97).-С. 164-168.

181. Рубальский Г.Б., Ушаков И.А. Оптимальное управление запасами // Надежность технических систем: справочник / Под ред. И. А. Ушакова. -М. : Радио и связь, 1985. С. 257-270.

182. Руководство пользователя по GPSS World. / Перевод с английского/. Казань : Изд-во «Мастер Лайн», 2002. - 384 с.

183. Рыжиков Ю.И., Соколов Б.В., Юсупов P.M. Проблемы теории и практики имитационного моделирования // Имитационное моделирование. Теория и практика. Матер. III Всеросс. конф. (ИММОД-2007), Т. 1. СПб. : ФГУП ЦНИИТС, 2007. - С. 58-70.

184. Рыжиков Ю.И. Теория очередей и управление запасами. СПб. : Питер, 2001.-384 с.

185. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. СПб. : КОРОНА принт; М. : Альтекс-А, 2004. - 384 с.

186. Рыжиков Ю.И. Имитационное моделирование. Курс лекций. -СПб. : BKA им. Можайского, 2007. 125 с.

187. Рыжиков Ю.И. Компьютерное моделирование систем с очередями. Курс лекций. СПб. : BKA им. Можайского, 2007. - 164 с.

188. Рыжиков Ю.И. Место имитации в моделировании дискретных систем. URL: http://www.gpss.ru/immod'03/003.html (дата обращения 19.08.2011).

189. Рябинин И.Д., Черкесов Г.Н. Логико-вероятностные методы исследования надежности структурно-сложных систем. М.: Радио и связь, 1981. - 264 с.

190. Самарский A.A., Михайлов А.П. Математическое моделирование: идеи, методы, примеры. М. : Наука, Физматлит, 2001. - 320 с.

191. Седжвик Р. Фундаментальные алгоритмы на С-Н-. Алгоритмы на графах: Пер. с англ. / Роберт Седжвик. СПб.: ООО «ДиаСофтЮП», 2002. - 496 с.

192. Секей Г. Парадоксы в теории вероятностей и математической статистике / Пер. с анл. М. : Мир, 1990. - 240 с.

193. Семенова О.В. Оптимальное пороговое управление системой ВМАР|СМ|1 с MAP-потоком сбоев // Автоматика и телемеханика, № 9, 2003.

194. Соболь ИМ. Метод Монте-Карло. М., 1978. - 64 с.

195. Соболь И.М. Численные методы Монте-Карло. М., 1973. - 212с.

196. Советов Б.Я., Яковлев С.А. Моделирование систем. Практикум: Учеб. пособие для вузов. М. : Высш. шк., 2009. - 296 с.

197. Соловьев А.Д. Методы расчета надежности систем с восстановлением // Надежность технических систем: справочник / Под ред. И. А. Ушакова. М. : Радио и связь, 1985. - С. 457-470.

198. Сотский Н.М., Чуркин Е.А. Стационарное распределение длины очереди в многоканальной системе массового обслуживания с приоритетами //Автоматика и телемеханика, 1985. №1. - С. 69-76.

199. Столингс В. В. Современные компьютерные сети. СПб. : Питер, 2003.-784 с.

200. Структура автономных систем сети Интернет, воссозданная на основе BGP таблиц, 2006 г., URL: http://www-personal .umich.edu/~mejn/netdata/as-22july 06 .zip (дата обращения: 01.09.2009).

201. Структура сети маршрутизаторов Интернет (2006 г.). URL: http://www.cise.ufl.edu/ research/sparse/mat/Pajek/internet.mat (дата обращения: 01.09.2009).

202. Структура сети участия актеров в общих фильмах. URL: http://www.nd.edu/~networks/resources/actor/actor.dat. gz (дата обращения:0302.2010).

203. Тарасевич Ю.Ю. Перколяция: теория, приложения, алгоритмы -М. Едиториал УРСС, 2004. 112 с.

204. Таташев А.Г. Системы обслуживания MAP|Gn|l|l с двумя специальными дисциплинами // Автоматика и телемеханика, № 12,2001. С. 33-39.

205. Таташев А.Г. Система обслуживания с инверсионной дисциплиной, двумя типами заявок и марковским входящим потоком // Автоматика и телемеханика, № 11, 2003. С. 122.

206. Толуев Ю.И. Применение имитационного моделирования для исследования логистических процессов // Имитационное моделирование. Теория и практика. Матер. П Всеросс. конф. (ИММОД-2005), Т.1. СПб. : ФГУП ЦНИИ ТС, 2005.-С. 71-76.

207. Томашевский В.Н., Жданова Е.Г. Имитационное моделирование в среде GPSS. М.: Бестселлер, 2003. - 416 с.

208. Тоффли Т., Марголус Н. Машины клеточных автоматов: Пер. с англ. М. : Мир, 1981. - 280 с.

209. Уилкс С. Математическая статистика. М. : Наука, гл. редакция физико-математической литературы, 1967. - 632 с.

210. Уолфрэм С. Научные исследования. Современный компьютер: сб. науч.-попул. статей / Пер. с англ. под ред. В.М. Курочкина; предисл. JI.H. Королева. -М. : Мир, 1986. - С. 158-173.

211. Учебное пособие по GPSS World Текст. / Перевод с английского /- Казань : Изд-во «Мастер-Лайн», 2002. 270 с.

212. Ушаков И.А. Вероятностные модели надежности информационно-вычислительных систем. М. : радио и связь, 1991. - 132 с.

213. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1.- М. : Мир, 1963.-512 е.

214. Феррари Д. Оценка производительности вычислительных систем: Пер. с англ. А.И. Горлина, Ю.Б. Котова и Л.В. Ухова / Под ред. В.В. Марты-нюка. М.: Мир, 1981 - 576 с.

215. Форрестер, Дж. Мировая динамика М. : ACT, 2003. - 379 с.

216. Франкен Петер, Кениг Д., Арндт У., Шмидт Ф. Очереди и точечные процессы. Киев : Наук. Думка, 1984. - 284 с.

217. Харин Ю.С., Степанова М.Д. Практикум на ЭВМ по математической статистике: Для мат. спец. ун-тов. Минск, 1987. - 304 с.

218. Хомоненко А.Д. Вероятностный анализ приоритетного обслуживания в многопроцессорных системах //АиТ, 1990. № 2. - С. 55-61.

219. Черкесов Г.Н. Системы с резервом времени // Надежность технических систем: справочник / Под ред. И.А. Ушакова. М. : Радио и связь, 1985.-С. 130-169.

220. Шелухин О. И., Тенякшев А. М., Осин А. В. Фрактальные процессы втелекоммуникациях / Под ред. О. И. Шелухина. М.: Радиотехника, 2003. 480 с.

221. Шеннон Р. Имитационное моделирование систем искусство и наука. - М. : Мир, 1978. - 418 с.

222. Ширяев А. Н. Вероятность М. : Наука, ГРФ-МЛ, 1980. - 576 с.

223. Шрайбер Т.Дж. Моделирование на GPSS / Пер. с англ. В.И. Гаргера, И.Л. Шмуйловича; Ред. М.А. Файнберг. М.: Машиностроение, 1980. - 592 с.

224. Эфрос А.Л. Физика и геометрия беспорядка. М. : Наука, ГРФМЛ, 1982.-268 с.

225. Юдин Е.Б. Генерация случайных графов предпочтительного связывания // Омский научный вестник, 2010. № 2 (90). - С. 188-192.

226. Якубайтис Э.А. Информационно-вычислительные сети. М. : Финансы и статистика, 1984. - 232 с.

227. Aaron Clauset, Cosma Rohilla Shalizi, M. E. J. Newman Power-law distributions in empirical data SI AM Review, ubmitted on 7 Jun 2007 (vl), last revised 2 Feb 2009 (this version, v2) in press.

228. Akira M, Kimura M. Injectivity and Surjectivity of Maps for Cellular Automata, J. Сотр. 18 (1979). P. 47-64.

229. Albert R., Barabasi A.-L. Statistical mechanics of complex networks //Rev. Mod. Phys.- 2002.- V.74. P. 42-97.

230. Barabasi, Albert-Laszlo and Albert, Reka. "Emergence of scaling in random networks". Science, 286:509-512, October 15, 1999.

231. Barabasi, Albert-Laszlo. Scale-Free Networks: A Decade and Beyond // SCIENCE , VOL 325, 24 JULY 2009. P. 412-413.

232. Barabasi, Albert-Laszlo The Architecture of Complexity, IEEE CONTROL SYSTEMS MAGAZINE, AUGUST, 2007.

233. Bolloba's, B. Random Graphs (Academic, London). 1985.

234. Bruell S.C., Balbo G. Computational Algorithms for Closed Queueing Networks. North Holland. - 1980. - 190 p.

235. Bruell S.C., Balbo G., Afshar P.V., Mean Value Analysis of Mixed Multiple Class BCMP Networks with Load Dependent Service Stations // Perform. Eval. 1984. - V. 4, N 4. - P. 241-260.

236. Chandy K.M., Sauer C.H. Computational Algorithms for Product form Queueing Networks // Commun. ACM. 1980. - V. 23., N 10. - P. 573-583.

237. Conway R., Maxwell V. and Miller L. Theory of Scheduling Reading: Addison-Vesley, 1967. Пер. на рус. яз.: Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний. - М. : Наука. - 1975. - 360 с.

238. Coveyoy R.R., MacPherson R.D. (1967). Fourier analysis of uniform random number generators. // J.Assoc. Computing Machinery. 1967. - 14. - P. 100-119.

239. Dorogovtsev, S.N. and Mendes, J.F.F. and Samukhin, A.N., "Structure of Growing Networks: Exact Solution of the Barabasi-Albert's Model", Phys. Rev. Lett. 85,4633.-2000.

240. Duncan J. Watts & Steven H. Strogatz Collective dynamics of small-world' networks//Nature. 1998. -V.393.-P.440.

241. Erdos P., Renyi A., On random graphs I, Publ. Math. Debrecen 6, 1959. -P. 290-297.

242. Erdos, P., and A. Renyi, Publ. Math. Inst. Hung. Acad.Sci. 5, 17. 1960.

243. Fishman G.S., Moor L.R. In search of correlation in multiplicative con-gruental generators with modulus 2 // Computer science and Statistics: Proc. of 13th Symp. on the Interface". New York : Springer Verlog. - 1982. -1. - P. 155-157.

244. Gaver D.P. A waiting line with interrupted service, including priorities, J. Roy. Stat. Soc., Ser. В 25 1962. - P.73-90.

245. Guclu, H. and Yuksel, M. Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks. In Proc. of IEEE ICDCS. 2007.

246. Iglehart D.L. The regenerative method for simulation analysis. In Current Trends in Programming Methodology, Vol. Ill: Software Modelling, K.M. Chandy and R.T. Yen, Eds., Prentice-Hall, Englewood, Cliffs N.J. 1978. - P. 52-71.

247. Jaiswal N.K. Priority Queues (Academic Press, New York, 1968). Пер. на рус. яз.: Джейсуол Н.К., Очереди с приоритетами. М. : Мир, 1973. 280 с.

248. Johnson М.Е., Jackson J. Infinitesimal Perturbation Analysis: a Tool for Simulation // J. of the Operational Res. Soc. 1989. - v. 40. no. 3. - P. 134-160.

249. Klemm Konstantin, Victor M. Eguiluz. Highly clustered scale-free networks Phys. Rev. E 65, 036123. 2002.

250. Klemm K., Eguiluz V.M. Growing scale-free network with small world behavior Phys. Rev. E, 2002, V. 65, P. 057102.

251. Krapivsky P.L., Redner S. Organization of Growing Random Networks

252. Phys. Rev. E. 2001. Article number 63.066123.

253. Kramer W., Langenbach-Belz M. Approximate formulae for the delaythin the queueing system GI/G/1// Congressbook, 8 Intranet. Telegraffic Congress, Melbourne. 1976.

254. Lam S., Lien I. A Tree Convolution Algorithm for the Solution of Queueing Networks // Commun. ACM. 1983. - V. 26., N 3. - P. 203-215.

255. Leskovec J., Chakrabarti D., Kleinberg J., Faloutsos C., Gharamani Z. Kronecker graphs: an approach to modeling networks, 29 Dec 2008.

256. Leskovec J., Lang K.J., Dasgupta A., Mahoney M.W. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. ArXiv, arXiv:0810.1355. Oct 2008c.

257. Lewis P.A.W. Large-Scale Computer-Aided Statistical Mathematics. Naval Postgraduate Shool, Monterey, Calif. // Proc. Computer Science and Statistics : 6th Annual Symp. Interface, Western Periodical Co., Hollywood, Calif. 1972.

258. Luce R.D. and Perry A.D. (1949). A method of matrix analysis of group structure. Psychometrika 14 (1): 95-116.

259. Marsaglia G. The structure of linear congruental sequences. In: Applications of Number Theory to Numerical Analysis, S.K.Zaremba (ed), Academic, New York. - 1972.

260. Marshall K.T. Some inequalities in queueing // Oper. Res., 1968. Vol. 16. P. 651-655.

261. Miiller Albe M., Lattice K. Monte Carlo simulations of FePt nanopar-ticles: Influence of size, composition, and surface segregation on order-disorder phenomena / PHYSICAL REVIEW B 72, 094203. 2005.

262. Nance R.E. and Overstreet C. A bibliography on random number generation: Computing Rev., 13, P. 495-508. 13. - 1972.

263. Newman M. E. J. The structure and function of complex networks SIAM Review 45, 167-256. 2003.

264. Price D. Networks of scientific papers, Science, 149,1965.-P. 510-515.

265. Rubinstein R.Y. Sensitivity analysis of computer simulation models via the efficient score // Oper. Res, 1989. V. 37. P. 72-81.

266. Suri R., Zazanis M. Perturbation Analysis Gives Strongly Consistent Sensitivity Estimates for the M|G| 1 Queue. // Mgmt Science, 1988. v. 34. - P. 39-64.

267. Tatara E., Birol I., Teymour F. and Cinar A. Static and Dynamic Behavior of Autocatalytic Replicators in Reactor Networks / Industrial and Engineering Chemistry Research, 43, 3972-3993. 2004.

268. Wolfram S. A New Kind of Science. Wolfram Press, 2003.