автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами

На правах рукописи

005009987

Соснин Владимир Валерьевич

РАЗРАБОТКА МОДЕЛЕЙ И МЕТОДОВ СИНТЕЗА ПРОЕКТНЫХ РЕШЕНИЙ ДЛЯ ТЕХНИЧЕСКИХ СИСТЕМ С ПРИОРИТЕТАМИ

Специальность 05.13.12 -«Системы автоматизации проектирования (приборостроение)»

Автореферат диссертации на соискание учёной степени кандидата технических наук

1 6 0ЕЗ 2012

Санкт-Петербург

2012

005009987

Работа выполнена в Национальном исследовательском университете информационных технологий, механики и оптики на кафедре вычислительной техники

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

Алиев Тауфик Измайлович.

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

Бухановский Александр Валерьевич,

кандидат технических наук, доцент Косяков Михаил Сергеевич.

Ведущая организация: ФГУП «ЛО ЦНИИС»

Защита диссертации состоится 13 марта 2012 г. в 15:50 на заседании диссертационного совета Д 212.227.05 при Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49.

Отзывы на автореферат, заверенные печатью, просим направлять по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д.49, СПб НИУ ИТМО, Диссертационный совет Д 212.227.05.

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

Автореферат разослан « 30 » 2012 г.

Ученый секретарь /!■, к.т.н., доцент

диссертационного совета Д 212.227.05 / /<■*-" Поляков В.И.

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

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

Значительный вклад в развитие исследований средств математического моделирования, позволяющих решать задачи проекгирования приоритетных систем, внесли Башарин Г.П., Бочаров П.П., Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Клейнрок JI., Климов ПП., Коваленко И.Н. и др.

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

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

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

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

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

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

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

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

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

2. Провести имитационные эксперименты при различной структурно-функциональной организации систем с приоритетным управлением и при варьировании законов распределений нагрузочных параметров.

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

4. На основе полученных частных аппроксимаций сформулировать свойства, присущие более широкому, чем исследованному в работе, классу систем.

5. Разработать инженерную методику синтеза проектных решений, используемых при проектировании технических систем с приоритетным управлением.

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

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

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

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

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

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

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

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

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

2. Предложены инженерные решения по моделированию сложных приоритетных дисциплин обслуживания в системе GPSS World с сохранением хорошей масштабируемости полученных моделей.

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

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

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

2. Закон сохранения вариации задержки в системах обслуживания с неоднородным потоком заявок и неэкспоненциальными законами распределения нагрузочных параметров.

3. Метод оценки ёмкости накопителя в системах обслуживания с памятью при заданных требованиях к уровню потерь заявок, получившж отказ в обслуживании в результате переполнения накопителя.

4. Результаты исследования свойств систем с эквивалентной производительностью при неэкспоненциальных законах распределения нагрузочных параметров.

5. Методика использования выявленных особенностей функционирования систем с приоритетным управлением для синтеза и анализа проектных решений с помощью САПР.

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

Апробация результатов работы. Основные положения диссертационной работы докладывались и обсуждались на Ш-й, IV-й и V-й всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (Санкт-Петербург, 2007, 2009, 2011 г.), на XXXVTI-й научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2008 г.), на V-й всероссийской межвузовской конференции молодых учёных (Санкт-Петербург, 2008 г.), на Х-й международной научно-практической конференции «Современные информационные и электронные технологии» (г. Одесса, 2009 г.), П-й научно-практической конференции молодых учёных «Вычислительные системы и сети (Майоровские чтения)» (Санкт-Петербург, 2010 г.).

Публикаинн. Результаты диссертационного исследования опубликованы в 9 работах, (из них две — в рецензируемых периодических журналах из списка ВАК).

Структура n объем диссертации. Диссертационная работа содержит 125 страниц машинописного текста, 35 рисунков, 12 таблиц, список литературы, включающий 50 работ отечественных и зарубежных авторов. Диссертация состоит из введения, четырёх глав, заключения и приложения, содержащего материалы, подтверждающие внедрение результатов диссертации.

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

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

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

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

Описана постановка задачи исследования в виде трёх независимых этапов, в которых синтез систем заключается в обоснованном выборе:

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

- ёмкости накопителя (который во многих технических системах является дорогостоящим элементом);

- количества обслуживающих приборов.

При этом в соответствии с рекомендациями ITXJ-T для сопоставления рассматриваемых систем обслуживания в диссертации используются следующие инверсные по-

казатели эффективности:

- среднее значение задержки заявок в системе;

- вариация задержки заявок в системе или в очереди;

- вероятность потери заявки в результате переполнения накопителя.

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

Приводится описание подхода, используемого для проведения имитационных экспериментов. Подход основан на применении Гамма-распределения при варьировании параметров исследуемых систем. Это распределение позволяет изменять независимым образом 1-й и 2-й моменты распределения исследуемых величин.

Вторая глава посвящена анализу влияния функциональных параметров систем

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

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

Далее в главе проводится анализ всех возможных дисциплин обслуживания с прерываниями, реализуемых стандартными средствами GPSS World. На основе проведённого анализа предлагается набор рекомендаций, позволяющих осуществлять обоснованный выбор среди множества стандартных дисциплин обслуживания, доступных в GPSS World.

В следующем параграфе главы обсуждаются свойства систем с бесприоритетной дисциплиной обслуживания. Традиционно считается, что бесприоритетиая дисциплина обслуживания (ДОБП) по определению предполагает отсутствие каких-либо механизмов, позволяющих одному классу заявок получить преимущественные условия обслуживания по сравнению с другими классами заявок. При этом в качестве показателя качества обслуживания обычно используют среднее время ожидания заявки в очереди и вариацию этой задержки. В соответствующей литературе показано, что в системах, в которых поток обслуживаемых заявок является простейшим, ДОБП действительно не даёт какому-либо классу преимущества в уровне качества обслуживания. Это означает, что если в такой системе времена ожидания в очереди заявок к классов есть случайные величины 1У2,Wk , то их математические ожидания равны: М[W{ ] = M[W2 ] =... = М[Wk ]. Целью автора было проверить, обладает ли этим свойством класс систем, в которых поток поступающих на обслуживание заявок не является простейшим. Исследования проводились для систем, в которых время обслуживания всех классов заявок имеет одинаковый закон распределения.

На рис. 1 приведены результаты имитационного моделирования системы обслуживания с двумя классами заявок, каждый из которых создаёт загрузки = 0.3 и РНК =0.03. Здесь и далее аббревиатура НК означает низконагружающкй класс, аббревиатура ВК - высоконагружающий класс. Времена обслуживания заявок ВК и НК есть случайные величины и такие, что M[Bg^] = М[В^к\ = 10 единиц

времени. Времена между приходом заявок ВК и НК есть случайные величины и Ат- Каждая из них имеет своё фиксированное значение математического ожидания, но коэффициент вариации в экспериментах меняется от 0 до 3 с шагом 0.1 так, что о[Адк] = и[АцК] = v[BBK] = v[Bm] = КВ. Производилось измерение времён ожидания в очереди заявок каждого из классов ( Wg[< и WtfK )= а также относительное отличие их

„ МЩвк] ~M[Whk] ..... _ ..

средних значении: е =—----------1----М00%. Длина вертикальных черточек на гра-

М\}Унк]

фиках рис. 1 равна величине 99%-ш доверительного интервала измеренных величин (по Стьюденту).

На рис. 1, а хорошо видно, что средние задержки НК и ВК существенно различаются за пределами доверительного интервала. На рис. !, б видно, что среднее время ожидания заявок ВК может быть либо на 90% меньше, либо на 20% больше среднего времени ожидания заявок НК. Аналогичный характер имеет соотношение вариации задержек с тем отличием, что относительная разница значений несколько меньше. Приведённый пример позволяет однозначно утверждать, что при непростейшем потоке заявок, поступающих на обслуживание, заявки разных классов получают в общем случае различное качество обслуживания при ДОБП.

Рис. !. Среднее время ожидания в очереди заявок НК и ВК: а) абсолютные значения; б) процентное отличие.

Однако для инженерной практики одного этого факта мало. Важно уметь численно оценить преимущество того или иного класса заявок. Чтобы сделать это, была проведена серия экспериментов по факторному плану' 2к для и[Лдк], и[А^{]. и[ВВК], и[ВНК]. Кроме того, проводились исследования при фиксированных значениях коэффициентов вариации обслуживания. Результаты экспериментов позволили выявить области изменения различных параметров СМО (системы массового обслуживания), при которых тот или иной класс заявок получает преимущество в уровне качества обслуживания.

Например, на рис. 2 приведены результаты для и[5^] = и[5д-д-] = 0.5 , Рвк ~ 0-3 и рнк = 0.03 . Координаты ячеек соответствуют использованному в эксперименте сочетанию и , а в самих ячейках записаны

2■№Гвк]-Щ!ГнкЪ экспериментально полученные величины о\у~——-——;——-—Ши/С и 1 " М[ЖВК]+М[1¥НК]

2-{^вк]-^ж}) Л о] =——-—-——---------— -Ши/о (соответственно на рис. 2, а и о), которые

показывают, сколько процентов составляет отличие сравниваемых величин от их среднего арифметического. Доверительный интервал не указывается, т.к. его 99% значение составляет не более 1% от приводимых величин. При <^ = 200% заявки ВК имеют наибольшее относительное преимущество (т.е. ожидают в очереди меньшее время) по отношению к заявкам НК. При <5и' = -200% ситуация диаметрально противоположная. При *5и' = 0% заявки обоих классов получают одинаковый уровень качества обслуживания.

Результаты этих экспериментов при различных сочетаниях загрузок ВК и НК позволили сделать вывод, что отличие времени ожидания и его вариации НК от ВК увели-

чивается при у[Ат]—> 0, ф!йл-]-»оо, у[Ввк]-^0, у[Внк]^> О, -> со, а зна-

Рнк

чения 8м> И <5/ асимптотически стремятся к некоторому пределу. Переход к соответствующему пределу в аналитической форме позволил получить нижнюю оценку значений исследуемых характеристик. Оказалось, что для любых СМО веоно, что

М[ЖШ\> р ■ М[\¥ш1 АКнк\>р-АШвк] ‘ (1).

1,4 1,8 г,г 2,6 3 3,4 3,8 0_2 0,6 1 1,4 1,8 2,2 2,6

у[Анк]

Рис.2. Взвешенное отклонение времени ожидания НК и В К: а) по средним значениям; б) по вариации (джиттеру).

3 3,4 3.8

v[Ahk]

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

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

Оказалось, что в качестве искомой гибко параметризуемой ДО удобно использовать дисциплину обслуживания с динамическими приоритетами (ДОДП), при которой приоритет заявок изменяется в соответствии с функцией приоритетности <p(t) = k,(t-f„), где t0 - момент поступления рассматриваемой заявки в систему, t - текущий момент времени, kt > 0 — коэффициент приоритетности, определяющий скорость изменения функции приоритетности заявок i-го класса (/' = 1,2,..., Я), где И-число классов заявок. После завершения обслуживания заявки из очереди выбирается заявка с наибольшим значением функции приоритетности.

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

пользуется параметр К = ———. Он удобен тем, что при К--1 второй класс имеет ОП к, +к2

по отношению к первому классу, при К = 1 первый класс имеет ОП по отношению ко второму классу, а случай с К-Q соответствует БПДО. При прочих значениях реализуются промежуточные ДО, т.е. варьируя К, можно осуществить плавный переход от ДОБП к ДООП посредством ДОДП. При -1 :S£<0 заявки первого класса являются заявками низкоприоритетного класса (НЗ), а заявки второго класса -заявками высокоприоритетного класса (ВЗ). При 0 < К < 1 ситуация обратная. Через U( обозначим среднее значение, а через J, - вариацию задержки заявок г-го класса.

На рис. 3 представлены результаты имитационного моделирования одноканальной СМО, в которой нагрузочные параметры классов симметричны: а, ~а, =33.(3) единиц времени, 6,=62=10 ед.вр., р1~рг=03, vbi=vai =0.7 где Ь, - среднее время обслуживания заявок /-го класса, а, — средний интервал времени между поступлением

заявок /-го класса, Р,-~ - загрузи, создаваемая заявками /-го класса, уы и к„,. — а,

коэффициенты вариации интервалов между прибытием заявок и времени обслуживания /-го класса.

Рис. 3, а иллюстрирует закон сохранения величины ГУ: уменьшение средней задержки ВЗ и, достигается за счёт такого же увеличения средней задержки НЗ и2 (т.е. ЛЬ', = Ли2). Однако вариация задержки ВЗ Jl, как видно из рис. 3, б, изменяется быстрее, чем вариация задержки НЗ ^ (т.е. А/, > _1Л) Отсюда следует, что закон сохранения для J не может формулироваться так же, как и для £/. В приводимых результатах имитационного моделирования 95-процентный доверительный интервал составил

Ь,

U, ед.вр.

а)

б)

J, ед.вр.

К

О 0,2 0,4 0,6 0,8 0 0,2 0,4 0,6 0,8

Рис. 3. Результаты моделирования: а - среднее значение задержки; б - вариация задержки.

не более 2% от указываемых значений, поэтому он не показывается на графиках.

Ввиду того, что существующие аналитические методы не позволяют дать численную оценку J для каждого из классов, в диссертации была поставлена задача на основе анализа большого числа имитационных экспериментов выявить некоторую закономерность, которая может быть сформулирована как закон сохранения для вариации задержки. Результаты проведённых экспериментов удалось обобщить для случая с ЛГ классами заявок следующей формулой:

£(д.1о8Д7,)) = С-(1±0.02)> (2)

где С - константа, меняющаяся не более чем на 2% (Д = 0.02). Основание логарифма х может быть выбрано произвольно. Проверка полученного закона сохранения проводилась для случаев N <, 4 и коэффициентах вариации параметров а и Ь, меньших 5. Для широкого класса систем с приоритетным управлением этот диапазон значений N достаточен. Например, в локальных компьютерных сетях обычно используется не более 4-х типов мультимедийного трафика.

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

В тпетьсй главе диссертации рассматривается задача синтеза систем обслуживания с памятью, в которой нужно выбрать такую ёмкость накопителя, при которой вероятность потери заявок в результате переполнения накопителя не превышает некоторой заданной величины. В специальной литературе для решения этой задачи предлагается использовать следующий метод: при выборе числа К в проектируемой системе вида «01/С/1/К» (в символике Кендалла), которую назовём СМО №1, нужно аналитическими методами получить функцию распределения Б(1) длины очереди Ь для системы вида «С1ДЗ/1» (СМО №2), имеющей такие же параметры, что и СМО №1, и отличающуюся от неё лишь наличием накопителя неограниченной ёмкости. Затем нужно решить неравенство Р(£) < л. относительно Ь, где я - заданное ограничение вероятности потерь заявок в результате переполнения накопителя. В итоге получится неравенство I < а, где а - верхнее ограничение на количество заявок в очереди. Данный метод является приближенным и оказывается применимым лишь в очень узкой области параметров СМО№1. В диссертационной работе показано, что этот метод может давать ошибки в десятки и сотни процентов. Кроме того, на практике далеко не всегда можно с доста точной точностью получить закон распределения величины Ь. Поэтому для решения поставленной задачи в общем виде применение аналитических методов исследования крайне затруднено. В работе ставилась задача на основе большого числа имитационных экспериментов предложить эмпирическую оценку числа а.

На рис. 4 показан результат проведённых имитационных экспериментов при

К

п = 10~!. Исследовалось поведение функции 2{р,тг) = —где К0!0!ук - ём-

ЩОс/ап)

кость накопителя в СМО №2, обеспечивающая долю потерь заявок меньшую, чем заданное значение яг, а М\Оа1а1,] - математическое ожидание среднего количества заявок в СМО №1. В приведённом на рис. 4 семействе кривых чем выше расположена кривая, тем больше коэффициент вариацииу = 1/[Л] = у[.В] в соответствующем экспери-

менте, где А и В суть случайные величины, задающие время между приходом заявок в СМО и время их обслуживания в приборе. При движении от точки "А" к точке "В" пунктирная стрелка пересекает графики в порядке уменьшения V. Очевидно, что уже при р > 0.5 характер графика мало зависит от значения V. Следовательно, аппроксимация, полученная для больших значений V, будет достаточно точной верхней границей для значений Ъ при меньших V. Для приведённого случая аппроксимирующая функция выглядит так: 2 < 35 - 28 • р при р > 0.5.

Рис. 4. Отношение ёмкости накопителя к средней длине очереди при я = 10~5

Подобным же образом выглядит верхняя граница для 2 при других значениях Результаты экспериментов, проведённых при других значениях к, удалось обобщить следующим неравенством:

2(р,я)< /? (6-І«(/т) +1.73)-7.77-^(гг)-3.67

Это неравенство даёт при а ={10'6; 10'5; Ю"4; 1(Г3;1(Г2} верхнюю оценку числа Ъ с

„ „ - г(р,я-)-2(і,,т)

ошиокои не оолее-------------------100 процентов, поэтому ею целесообразно пользо-

2(Р, я)

ваться при р > 0.5. Для других значений я оценка 2 получится линейно интерполированной, что может увеличить ошибку. Однако чаще всего в стандартизующих технических документах в качестве значения л выбирают одно из указанных значений степени числа 10, что делает полученную оценку полезной для целей практических инженерных расчётов.

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

В следующем параграфе главы исследуются свойства многоканальных СМО вида вї/Сі/К с целью обнаружить закономерности, которые можно использовать в САПР при синтезе проектных решений. В таких системах на обработку к N приборам одинаковой производительности поступает произвольный поток заявок, а время обслуживания в каждом приборе описывается произвольным законом распределения (ЗР). Под производительностью прибора понимается интенсивность обслуживания заявок. Пусть V, -производительность СМО при N -1. Тогда всё множество СМО с N > 1, в которых

у

производительность каждого из N приборов равна Ук = —, будем называть система-

N

ми с эквивалентной производительностью (СЭП), т.к. суммарная производительность всех приборов в них остаётся постоянной: Уг - ■ N = V,. При этом все СМО из за-

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

Целью автора стало исследование свойств СЭП ОШ/М. Применение аналитических методов для этого невозможно, т.к. при этом понадобилось бы точно задать параметры ЗР входящего потока и ЗР времени обслуживания. Поэтому исследование проводилось на имитационных моделях, в результате чего автором было выявлено новое свойство СЭП: при определённой конфигурации нагрузочных параметров оптимальное число каналов может оказаться больше единицы. Для болсс детального исследования зависимости среднего времени пребывания заявок в системе от числа N (для СЭП с неэкспоненциальными потоками) решались следующие задачи:

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

- выявление влияния каждого из этих факторов на эту характеристику;

- формулирование рекомендаций для выбора оптимального числа N.

В качестве примера сравним характеристики двух классов СЭП: М/МЖ и вЮ/К, - с некоторым заданным набором параметров. Зададим среднее время между приходом заявок М[А] = 100 единиц времени, коэффициент загрузки р - 60%, коэффициент вариации времени обслуживания заявок в приборе у[Я] и коэффициент вариации времени между приходами заявок у[А]. Среднее время обслуживания заявок будет определяться в зависимости от N по формуле: М[В] = р-М{А]-Ы.

На рис. 5, а представлена зависимость среднего времени пребывания заявок СЭП М/М/М (теоретический расчёт) от числа приборов N. Принятые обозначения: I/ — случайное время пребывания заявки в СМО, IV- случайное время ожидания обслуживания заявки. На рис. 5, б показана аналогичная зависимость для М[Г7] в СЭП СШ/Ы (по результатам имитационного моделирования). Здесь и далее на графиках с результатами экспериментов приводится 95%-й доверительный интервал (по Стьюденту) всех измеренных характеристик.

График на рис. 5, а иллюстрирует классический случай, когда с точки зрения минимизации задержек наиболее выгодным является использование одноканальной СМО, т.к. время пребывания М[6] монотонно возрастает с ростом N. Имитационные эксперименты показали, что подобный характер поведения системы сохраняется при любой загрузке при условии, что 0<у[Л]<1 и 0 < у[В]< 1. Однако стоит увеличить оба ко эффициента вариации свыше этих ограничений, как это правило потеряет силу (см. рис. 5, б): у функции М[{7] теперь наблюдается минимум в точке N = 4. Этот пример доказывает, что применение эмпирического правила о предпочтительности минимального числа каналов в СЭП нельзя распространять на весь класс систем ОШМ.

Приведённые на рис. 5, б графики представляют собой предлагаемые в специальной литературе нижнюю (НГ) и верхнюю (ВГ) границы для значения М[V] (для систем 01/0/К более точных аналитических оценок значения М[с/] не получено). Из графика видно, что эти граничные оценки нельзя использовать для выбора оптимального числа N т.к. оно бы оказалось в этом случае равным 2 (при Н=2 функции НГ и ВГ имеют минимум).

Рис. 5. Зависимость времени пребывания заявок в СЭП от числа приборов: a) v'[S] = l,v[^] = l; б) v[5] = 3,v[j4J = 1.5.

На следующем этапе работы решалась задача оценки влияния следующих параметров на экстремум функции М[{7): коэффициент вариации времён обслуживания заявок в приборе v[B], коэффициент вариации времён между приходами заявок v[A], коэффициент загрузки СМО р. Исследовалось независимое влияние на М[{/| каждого из этих факторов. В результате было получено, что соответствующие зависимости с критерием достоверности аппроксимации R2 =0.999 имеют следующий вид:

A/[[/,](v[5]) = С, • v2[/>'] + с2, Щи,](у{А}) = С3 - у2 [А] + С4 ■ v[A] + С5, (4)

где С\, С,2, — константы, не зависящие от v[S], Съ, С4 - константы, не зависящие от v[A], Uj - время пребывания заявок в СЭП при АН.

Полученную закономерность можно использовать в САПР, используемых для проектирования систем с эквивалентной производительностью, при котором требуется в качестве проектной задачи синтеза осуществить выбор количества обслуживающих приборов. Для этого в САПР с помощью полученных формул можно использовать следующую схему поиска решения при синтезе систем СЭП GI/G/N при неизвестном v[fij (аналогично при неизвестном v[A]):

1. На имитационной модели найти несколько пар значений M[t/J и v[В], и M[£/j] и v[S] при малых значениях v[B] (т.к. именно при малых значениях v[B\ получаемые характеристики достаточно точны, т.е. имеют узкий доверительный интервал).

2. По найденным парам найти в соответствии с приведённой формулой аппроксимирующие функции M[t/?](v[B]) и М[С/з](у[Б]): в этом случае аппроксимирующие функции будут определены даже точнее, чем если бы они искалась в том числе и по известным парам значений с высоким v[B], приводящим к значительному разбросу в значении получаемых характеристик.

3. Решить уравнение M[U~](v[B]) = M[U3]{v[B]) относительно v[fi].

4. Проделать пункты 1-3 для требуемого числа последующих пар щи г ]№]) = M\ut ](V[B]), M[Ut ](v[Z?]) = M[U5 ](V[B]) и т. д.

5. Окончить процесс поиска числа N.

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

Четвертая глава посвящена описанию практического использования полученных

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

На первом этапе предлагаемой методики с помощью САПР нужно задать конкретные значения среднего значения и коэффициента вариации случайных величин, характеризующих нагрузочные параметры проектируемой системы. Этими случайными величинам являются множества и {В[,Вг,...,Вк}, задающие, соответ-

ственно, время между приходом заявок каждого из К классов заявок и время обслуживания каждого из К этих классов. Затем полученные значения А;, В\ (« = 1, 2,..., К) и загрузки р нужно соотнести с данными в Таблице. Если рассматриваемые параметры укладываются в ограничения, сформулированные в одной из четырёх строк Таблицы, то для проектирования СМО применим метод, описанный в столбце "Метод исследования" соответствующей строки.

Таблица

К у|А1 '[В,] Р> Метод исследования

2 [0.1; 3.8] [0.1; 3.8] [0.1; 0.9] С помощью формулы (1) при ДОБП можно получить нижнюю границу' числовых характеристик времени пребывания в системе для заявок низконагружающего класса

1,2, 3,4 [0.1; 2.1] [0.1; 2.1] [0.1; 0.9] С помощью формулы (2) можно оценить возможный эффект от изменения ДО для двух выбранных классов заявок.

1 [0.5; 1.5] [0.5; 1.5] [0.5; 0.9] С помощью формулы (3) можно оценить ёмкость накопителя, при которой вероятность потерь не больше заданного значения ж = {1 ОТ6; 10'5;)О"4;!0~3}

1 [0.1; 3.6] [0.1; 3-6] [0.1; 0.9] С помощью формул (4) можно выбрать оптимальное число обслуживающих приборов для СМОЭП.

Далее в главе приводятся примеры внедрения разработанных методов в системы автоматизации проектирования различных технических приборов и систем. Во втором параграфе описываются проблемы, возникшие при автоматизации проектирования парковочного комплекса, в котором автомобили располагаются на передвижных пандусах. Одна из проблем заключалась в сравнении уровня задержек при неоднородном трафике машин. Разобьём его условно на два класса: постоянные клиенты автостоянки (класс А) и случайные клиенты (класс Б). Специфика местоположения моделируемой парковки такова, что интенсивность класса А существенно выше класса Б, т.к. большинство клиентов являются офисными работниками в том же бизнес-центре, где планировалось построить парковочную систему. К тому же владельцам автостоянки сравнительно просто получить экспериментальные данные о нагрузочных параметрах трафика класса А и об уровне задержек, которые испытывают клиенты класса А. Возникает вопрос: можно ли на этапе проектирования оценить средний уровень задержек, которые будут испытывать клиенты класса Б? Помочь решить эту задачу позволяет метод, описанный в главе 2. Пусть в результате натурного эксперимента получилось, что в среднем автомашины класса А ожидают в течение 5 минут подгона пандуса, а уровень загрузки, который они создают равен 60%. Воспользуемся формулой (1) для оценки средней задержки машин класса Б. Получим, что это значение не может быть меньше 3 минут. Более детальную оценку можно дать, если известны законы распреде-

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

Во втором и третьем параграфе описаны проблемы, возникавшие при автоматизации проектирования компьютерных сетей. Например, моделировался сегмент беспроводной компьютерной сети, по которой передаётся трафик трёх видов: аудио-, видео- и управляющих данных. Приводится пример задачи, когда системному администратору этой сета требуется изменить политику назначения приоритетов классам трафика так, чтобы джиттер пакетов аудиопотока (АП) уменьшился до рекомендуемого документами ITU-T значения 50 мс, а джиттер пакетов управляющего потока (УП) не изменился. Пусть измерения на исследуемой беспроводной точке доступа показали, что загрузка, создаваемая B1I равна р\ ~ 0.45, загрузка АП и УП равна р2 = Рз ~ 0.05. Джиттеры в том же порядке приблизительно равны Jx = 300 мс, J2 - 300 мс и Уз = 50 мс соответственно. Тогда по формуле (2) получим, что

С = 0.45 ■ 1п(300) + 0.05 • 1п(300) + 0.05 • 1п(50) и 3.047 . Выразим через остальные ком. . (С-(]±0.02)-р-, ■ ln(J2) -Рз • 1п(./3)) „

поненты формулы: Jx = exp —i, J. Подставив вместо

V Pi )

J-l желаемое значение 50 мс (вместо 300 мс), получим, что J\ ~ 370 ± 50 мс. Если подобный диапазон значений Jt устраивает системного администратора, он может принять решение о пересмотре политики приоритетного управления, тем самым решив задачу синтеза проектного решения в автоматизированном виде при проектировании функциональной организации сети.

Рассматривается другой пример из той же области: пусть в некоторой САПР маршрутизируемой компьютерной сети требуется в автоматизированном виде оценить, какой должен быть размер буфера на исследуемом выходном порте некоторого маршрутизатора, чтобы вероятность потерь в результате переполнения буфера не превысила значения 105, рекомендованного ITU-T. В выходных портах маршрутизатора пакеты ждут передачи предыдущего пакета в канал связи. При этом обработка производится по принципу FIFO и ДОБП. Время выдачи пакета в канал связи пропорционально его размеру, который можно в общем случае считать случайной величиной. В ожидании передачи пакеты хранятся в независимой буферной памяти каждого порта. При решении проектной задачи оценки ёмкости буферной памяти с помощью САПР можно сначала воспользоваться формулой (3), чтобы получить значение ёмкости, выраженное в количестве пакетов. Затем, используя известные аналитические методы, можно пересчитать полученное значение в число, выраженное количеством байт.

В заключении приведены основные результаты исследования и сформулированы выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

3. Для приоритетных систем обслуживания с произвольным характером функционирования сформулирован закон сохранения вариации задержки, положенный в основу метода автоматизации проектирования приоритетных технических систем, в которых для оценки качества функционирования применяются рекомендации ITU-T Y.1541.

4. Предложен более точный, чем известные, метод выбора ёмкости накопителя в системах обслуживания, при которой вероятность потерь заявок в результате переполнения не превышает заданного значения. Предложенный метод позволяет повысить точность проектирования систем и приборов с памятью. В области средних и высоких загрузок и вероятности потерь более Ю'4 полученный метод даёт минимум в 1,5—2 раза более точные оценки ёмкости накопителя, чем описанные в литературе методы.

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

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

СПИСОК ПУБЖ1КАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Соснин В.В. Моделирование дисциплины обслуживания с абсолютными приоритетами в GPSS World // Сборник докладов третьей всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД-2007). - СПб., 2007. - Т. I. - С. 224-229.

2. Сосшш В.В., Алиев Т.Н. Оценка ёмкости буферной памяти н промежуточных узлах телекоммуникационной сети // Научно-технический ыеспшк Санкт-Петербургского государственного университета информационных технологий, механики и оптики. - СПб., 2008. - №56. - С. 81-85.

3. Алиев Т.И., Соснин В.В. Динамическое управление потоком пакетов на основе смешанных приоритетов // Труды десятой международной научно-практической конференции «Современные информационные и электронные технологии» (СИЭТ 2009).

- Одесса, 2009. - Т. I. - С. 122.

4. Соснин В.В. Исследование мпогокапальных систем массового обслуживании с эквивалентной производительностью // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. - СПб., 2009. -№1 (59). - С. 34-39.

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

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

2009.-Т.2.-С. 245-249. ’

7. Соснин В.В., Шинкарук Д.Н. Моделирование маршрутизатора с поддержкой мето-

дов QoS в среде ns-З // Сборник трудов молодых учёных и сотрудников кафедры ВТ. Выпуск 2 / Под ред. д.т.н., проф. Т.Н. Алиева. - СПб: СПбГУ ИТМО 2011 -С.50-55. '

8. Соснин В.В. Дисциплины обслуживания с прерываниями, реализуемые стандартными средствами GPSS // Труды пятой всероссийской научно-практической конференции но имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД 2011) -СПб, 2011. - Т.1. -C.275-28I.

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

GI/G/1 // Труды пятой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД 2011). - СПб 2011 - Т2 -С.355-360. ' ' '

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации»

197101, Санкт-Петербург, Кронверкский пр., 46 Тел. (812) 233-46-69.

Объем 1 уел. печ. л. Тираж 100 экз.

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

61 12-5/2596

и1 и/^о^и рукописи

Соснин Владимир Валерьевич

РАЗРАБОТКА МОДЕЛЕЙ И МЕТОДОВ СИНТЕЗА ПРОЕКТНЫХ РЕШЕНИЙ ДЛЯ ТЕХНИЧЕСКИХ СИСТЕМ С ПРИОРИТЕТАМИ

Специальность 05.13.12 -«Системы автоматизации проектирования (приборостроение)»

Диссертация на соискание учёной степени кандидата технических наук

Научный руководитель д.т.н., профессор Алиев Т.И.

Санкт-Петербург 2012

Оглавление

Основные обозначения и сокращения................................................................3

Введение...............................................................................................................4

ГЛАВА 1. Принципы функционирования систем с приоритетами.................12

§ 1.1. Классификация методов приоритетной обработки........................12

§ 1.2. Аналитический обзор методов автоматизации проектирования

систем с приоритетами....................................................................18

§ 1.3. Постановка задачи анализа и синтеза проектных решений при

разработке систем с приоритетами.................................................24

§ 1.4. Выводы по главе 1............................................................................31

ГЛАВА 2. Проектирование функциональной организации систем с

приоритетным управлением......................................................................32

§ 2.1. Проблемы проектирования приоритетных систем с

прерываниями в GPSS World..........................................................32

§ 2.2. Свойства дисциплин обслуживания с прерываниями,

реализуемых стандартными средствами GPSS World...................38

§ 2.3. Проектирование систем с бесприоритетной дисциплиной

обслуживания...................................................................................49

§ 2.4. Применение закона сохранения вариации задержки для

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

§ 2.5. Выводы по главе 2............................................................................67

ГЛАВА 3. Проектирование структурной организации систем с

приоритетным управлением......................................................................68

§ 3.1. Эквивалентность свойств систем с однородной и

неоднородной нагрузкой.................................................................68

§ 3.2. Решение проектной задачи оценки ёмкости накопителя в

системах обслуживания с потерями................................................71

§ 3.3. Проектирование систем с эквивалентной

производительностью......................................................................77

§ 3.4. Выводы по главе 3............................................................................87

ГЛАВА 4. Практическая реализация разработанных моделей и методов......88

§ 4.1. Методика анализа и синтеза проектных решений в САПР

технических систем с приоритетным управлением.......................88

§ 4.2. САПР автоматизированной автостоянки........................................93

§ 4.3. САПР сегмента WiMAX-сети..........................................................99

§ 4.4. САПР маршрутизатора с высокоуровневыми функциями...........106

§ 4.5. Выводы по главе 4..........................................................................115

Заключение.......................................................................................................116

Библиографический список.............................................................................118

Приложение. Акты внедрения результатов диссертации..............................122

Основные обозначения и сокращения

АП - абсолютный приоритет

БП - буферная память

ВК - высоконагружающий класс

ДОАП - дисциплина обслуживания с абсолютными приоритетами

ДОБП - дисциплина обслуживания без приоритетов

ДОДП - дисциплина обслуживания с динамическими приоритетами

ДООП - дисциплина обслуживания с относительными приоритетами

ДОП - дисциплина обслуживания с прерываниями

ЗР - закон распределения

KB - коэффициент вариации

НК - низконагружающий класс

ОП - относительный приоритет

САПР - система автоматизированного проектирования

СОП - система обработки с приоритетами

ТМО - теория массового обслуживания

CAD - computer-aided design

CQ - custom queueing

FIFO - first in, first out

PQ - priority queueing

WFQ - weighted fair queueing

Введение

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

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

Развитию методов ТМО для исследования и проектирования систем обработки с приоритетами (СОП) посвящены работы [12, 13, 14, 18]. Достаточно полный обзор аналитических методов моделирования дискретных систем приведён в [39].

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

скому моделированию, что требует комплексного подхода, основанного на применении многоуровневого иерархического моделирования [20], сочетающего аналитические и статистические методы.

Значительный вклад в развитие исследований средств математического моделирования приоритетных систем внесли Башарин Г.П., Бочаров П.П., Гне-денко Б.В., Даниелян Э.А., Димитров Б.Н., Клейнрок JL, Климов Г.П., Коваленко И.Н. и др.

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

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

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

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

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

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

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

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

2. Провести имитационные эксперименты при различной структур-но-функциональной организации систем с приоритетным управлением и при варьировании законов распределений нагрузочных параметров.

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

4. На основе полученных частных аппроксимаций сформулировать свойства, присущие более широкому, чем исследованному в работе, классу систем.

5. Разработать инженерную методику синтеза проектных решений, используемых при проектировании технических систем с приоритетным управлением.

Методами исследования, применяемыми в диссертационной работе, являются аппарат теории вероятностей, теории массового обслуживания [18], теории случайных процессов [9], методов численного анализа и имитационного моделирования [19, 38, 5, 15].

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

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

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

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

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

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

1. Разработаны приближённые методы расчёта характеристик систем с приоритетным управлением при различных вариантах структурно-

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

2. Предложены инженерные решения по моделированию сложных приоритетных дисциплин обслуживания в системе GPSS World с сохранением хорошей масштабируемости полученных моделей.

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

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

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

2. Закон сохранения вариации задержки в системах обслуживания с неоднородным потоком заявок и неэкспоненциальными законами распределения нагрузочных параметров.

3. Метод оценки ёмкости накопителя в системах обслуживания с памятью при заданных требованиях к уровню потерь заявок, получивших отказ в обслуживании в результате переполнения накопителя.

4. Результаты исследования свойств систем с эквивалентной производительностью при неэкспоненциальных законах распределения нагрузочных параметров.

5. Методика использования выявленных особенностей функционирования систем с приоритетным управлением для синтеза и анализа проектных решений с помощью САПР.

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

Апробация результатов работы. Основные положения диссертационной работы докладывались и обсуждались на Ш-й, 1У-й и У-й всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (Санкт-Петербург, 2007, 2009, 2011 г.), на ХХХУИ-й научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2008 г.), на У-й всероссийской межвузовской конференции молодых учёных (Санкт-Петербург, 2008 г.), на Х-й международной научно-практической конференции «Современные информационные и электронные технологии» (г. Одесса, 2009 г.), П-й научно-практической конференции молодых учёных «Вычислительные системы и сети (Майоровские чтения)» (Санкт-Петербург, 2010 г.).

Публикации. Материалы, отражающие основное содержание работы, изложены в 9 печатных работах [4, 26-33], две из которых [27, 29] находятся в перечне изданий, рекомендованных ВАК.

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

В [4] и [29] автору принадлежат программная реализация имитационных моделей, а также проведение экспериментов с этими моделями и статистический анализ полученных результатов.

В [30] автору принадлежит программная реализация утилит, использованных в процессе экспериментальных замеров, а также статистический анализ полученных результатов измерений.

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

Структура и объем диссертации. Диссертационная работа содержит 125 страниц машинописного текста, 35 рисунков, 12 таблиц, список литературы, включающий 50 работ отечественных и зарубежных авторов. Диссертация состоит из введения, 4 глав, заключения и приложения, содержащего материалы, подтверждающие внедрение результатов диссертации.

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

В первой главе рассматриваются области применения приоритетных правил управления в современной технике. Предлагается классификация приоритетных правил управления, которая включает в себя современные приоритетные методы управления, отличные от классических, традиционно рассматриваемых в теории массового обслуживания. Заметим, что в ТМО правила управления очередями традиционно называются дисциплинами обслуживания (ДО). Кроме того, в первой главе формулируется постановка задачи исследования.

Вторая глава посвящена анализу влияния функциональных параметров систем обслуживания на их характеристики при использовании приоритетных правил управления. В процессе исследования были выявлены новые свойства п�