Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Соснин, Владимир Валерьевич
- Специальность ВАК РФ05.13.12
- Количество страниц 125
Оглавление диссертации кандидат технических наук Соснин, Владимир Валерьевич
Оглавление
Основные обозначения и сокращения
Введение
ГЛАВА 1. Принципы функционирования систем с приоритетами
§ 1.1. Классификация методов приоритетной обработки
§ 1.2. Аналитический обзор методов автоматизации проектирования
систем с приоритетами
§ 1.3. Постановка задачи анализа и синтеза проектных решений при
разработке систем с приоритетами
§ 1.4. Выводы по главе 1
ГЛАВА 2. Проектирование функциональной организации систем с
приоритетным управлением
§ 2.1. Проблемы проектирования приоритетных систем с
прерываниями в GPSS World
§ 2.2. Свойства дисциплин обслуживания с прерываниями,
реализуемых стандартными средствами GPSS World
§ 2.3. Проектирование систем с бесприоритетной дисциплиной
обслуживания
§ 2.4. Применение закона сохранения вариации задержки для
проектирования приоритетных систем
§ 2.5. Выводы по главе 2
ГЛАВА 3. Проектирование структурной организации систем с
приоритетным управлением
§ 3.1. Эквивалентность свойств систем с однородной и
неоднородной нагрузкой
§ 3.2. Решение проектной задачи оценки ёмкости накопителя в
системах обслуживания с потерями
§ 3.3. Проектирование систем с эквивалентной
производительностью
§ 3.4. Выводы по главе 3
ГЛАВА 4. Практическая реализация разработанных моделей и методов
§ 4.1. Методика анализа и синтеза проектных решений в САПР
технических систем с приоритетным управлением
§ 4.2. САПР автоматизированной автостоянки
§ 4.3. САПР сегмента WiMAX-сети
§ 4.4. САПР маршрутизатора с высокоуровневыми функциями
§ 4.5. Выводы по главе 4
Заключение
Библиографический список
Приложение. Акты внедрения результатов диссертации
Основные обозначения и сокращения
АП - абсолютный приоритет
БП - буферная память
ВК - высоконагружающий класс
ДОАП - дисциплина обслуживания с абсолютными приоритетами
ДОБП - дисциплина обслуживания без приоритетов
ДОДП - дисциплина обслуживания с динамическими приоритетами
ДООП - дисциплина обслуживания с относительными приоритетами
ДОП - дисциплина обслуживания с прерываниями
ЗР - закон распределения
KB - коэффициент вариации
НК - низконагружающий класс
ОП - относительный приоритет
САПР - система автоматизированного проектирования
СОП - система обработки с приоритетами
ТМО - теория массового обслуживания
CAD - computer-aided design
CQ - custom queueing
FIFO - first in, first out
PQ - priority queueing
WFQ - weighted fair queueing
Рекомендованный список диссертаций по специальности «Системы автоматизации проектирования (по отраслям)», 05.13.12 шифр ВАК
Марковские модели однолинейных систем обслуживания с накопителем конечной емкости2001 год, доктор технических наук Нгуен Хунг Фонг
Исследование алгоритмов управления очередями в вычислительных системах с разделением времени1983 год, кандидат технических наук Ляшев, Станислав Георгиевич
Построение моделей и анализ систем массового обслуживания при скачкообразной интенсивности входного потока2001 год, кандидат технических наук Кучер, Наталья Александровна
Методы анализа показателей эффективности телекоммуникационной сети серверов протокола установлений сессий2014 год, кандидат наук Зарипова, Эльвира Ринатовна
Поддержание целостности обмена сообщениями о движении воздушных судов в автоматизированной системе управления воздушным движением2008 год, кандидат технических наук Ребров, Виталий Анатольевич
Введение диссертации (часть автореферата) на тему «Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами»
Введение
Актуальность проблемы. В технических системах широко применяются приоритетные правила управления, которые позволяют обеспечить требуемое качество обслуживания разным классам управляемых объектов. При автоматизации проектирования такого рода систем необходимо иметь подробную информацию о свойствах приоритетных правил управления и об их влиянии на характеристики функционирования проектируемой системы. Обнаруживать и изучать эти свойства можно с помощью математических моделей, описывающих функционирование приоритетных систем для широкого диапазона значений их структурно-функциональных параметров. Традиционно при проектировании приоритетных систем для решения задач анализа и синтеза используется аппарат теории очередей (иначе называемой теорией массового обслуживания, ТМО). Большое количество задач из разных областей техники, экономики и медицины удаётся сформулировать и решить с помощью этой теории. [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 глав, заключения и приложения, содержащего материалы, подтверждающие внедрение результатов диссертации.
Во введении обоснована актуальность и новизна диссертационной работы, определены цели, задачи, объект и предмет исследования, сформулированы основные научные результаты, выносимые на защиту.
В первой главе рассматриваются области применения приоритетных правил управления в современной технике. Предлагается классификация приоритетных правил управления, которая включает в себя современные приоритетные методы управления, отличные от классических, традиционно рассматриваемых в теории массового обслуживания. Заметим, что в ТМО правила управления очередями традиционно называются дисциплинами обслуживания (ДО). Кроме того, в первой главе формулируется постановка задачи исследования.
Вторая глава посвящена анализу влияния функциональных параметров систем обслуживания на их характеристики при использовании приоритетных правил управления. В процессе исследования были выявлены новые свойства приоритетных правил управления, что позволило предложить метод автомата-
зации проектирования технических систем с исследованными правилами управления.
В третьей главе приводятся разработанные методы и результаты проведённых исследований, посвящённых предпроектному анализу влияния структурных параметров на характеристики функционирования приоритетных систем класса 01/0/1 с приоритетами. Формулируется метод приближённого расчёта характеристик многоканальных систем обслуживания с эквивалентной производительностью. Предложен приближенный метод оценки ёмкости накопителя, при которой вероятность потери заявок в результате переполнения накопителя не превышает некоторой заданной величины.
Четвертая глава посвящена описанию практического использования полученных в диссертационной работе результатов. Приводится методика, позволяющая осуществлять анализ и синтез проектных решений при работе САПР для выбора структурно-функциональной организации приборов и систем обслуживания. Описывается рад примеров, иллюстрирующих применение сформулированной методики на практике в ряде НИР, в которых автор принимал непосредственное участие.
В заключении приведены общий вывод о решении поставленной задачи и основные результаты диссертационной работы.
Похожие диссертационные работы по специальности «Системы автоматизации проектирования (по отраслям)», 05.13.12 шифр ВАК
Методология автоматизированного проектирования информационно-телекоммуникационных систем: На основе моделирования и оптимизации сетей передачи данных2002 год, доктор технических наук Хаустович, Александр Владимирович
Разработка и исследование моделей процессов обслуживания в автоматизированных системах проектирования и управления гибкими производствами1984 год, кандидат технических наук Парадизов, Николай Венедиктович
Исследование моделей систем массового обслуживания в информационных сетях2007 год, доктор технических наук Головко, Николай Иванович
Модели и методы проектирования информационно-управляющих систем реального времени долговременных орбитальных станций: На примере МКС "Альфа"2000 год, доктор технических наук Микрин, Евгений Анатольевич
Модели и методы исследования процессов функционирования и оптимизации построения сетей связи следующего поколения (Next Generation Network)2009 год, доктор технических наук Сычев, Константин Иванович
Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Соснин, Владимир Валерьевич
Результаты исследования. В работе исследовалось независимое влияние на М[U] каждого из этих факторов. Ниже приводятся результаты экспериментов, в которых значение исследуемого фактора варьировалось, а значения двух других факторов фиксировались. На рис. 3.6 приведена зависимость М[£У] от v[B] для трёх значений N при М[А] = 100 единиц времени, v[A] = 1 и р = 0.6 . Для N-1 расчёт проводился по формуле Полячека-Хинчина [18]. Для N-2 и N= 3 приведён 95 % доверительный интервал измеренной характеристики. На рисунке величина Ui означает время обслуживания заявки при числе обслуживающих приборов, равном i.
Обозначим через Nopt число приборов, для которого в данном классе СЭП среднее время пребывания заявок является наименьшим. Под классом СЭП будем понимать множество СМО, на вход которых поступают идентичные потоки заявок, а параметры этих СМО отличаются только количеством обслуживающих приборов при сохранении их суммарной производительности. Как видно из рисунка, при v[5] <2 имеем Nopt= 1, при 2 3 имеем Nopt = 3.
Очевидно, будет существовать некоторое значение, при превышении которого коэффициентом вариации KVTO оптимальным числом приборов станет 4, 5, 6 и т.д. Наличие этого эффекта подтверждается многочисленными экспериментами.
ОД 0,6 1Д 1,6 2,1 2,6 3,1 3,6
Рис. 3.6. Зависимость времени пребывания заявок в СЭП от у[В]
На рис. 3.6 зависимость М[£/г] от у[В] согласно формуле Полячека-Хинчина имеет параболический вид
М[и1] = С1-у2[В] + С2, (3.2) где С1 и С2 - это константы, не зависящие от . Расчёты показали, что и две другие зависимости (М[112] и М[С73]) имеют, с критерием достоверности аппроксимации Я —0.999, аналогичный вид с разницей лишь в значении С1 и С2.
С помощью полученных формул можно использовать следующую схему анализа и синтеза проектных решений в СОП с неизвестным у[В~\ :
1. На имитационной модели найти несколько пар значений М[Ш] и у[В], и М[иЗ] и у[5] при малых значениях у [В] (т.к. именно при малых значениях у[В~\ получаемые характеристики достаточно точны, т.е. имеют узкий доверительный интервал).
2. По найденным парам найти в соответствии с формулой (3.2) аппроксимирующие функции М[Ш]( и М[иЗ]( у[5]): в этом случае аппроксимирующие функции будут определены даже точнее, чем если бы они искалась в том числе и по известным парам значений с высоким у [В], приводящим к значительному разбросу в значении получаемых характеристик.
3. Решить уравнение М[112](у[В]) = М[иЗ](у[В]) относительно .
4. Проделать пункты 1-3 для достаточного числа последующих пар (M[t/3](v[5])=M[í/4](v[5]), M[U4](v[B])=M[U5](v[B]) и т.д.
В результате будут найдены значения v[J5], являющиеся границами изменения значения Nopt. Полученные данные можно использовать при проектировании рассмотренного класса систем.
На рис. 3.7 приведена зависимость U( v[A]) для трёх значений N при М[А] = 100 единиц времени, v[B] = 2 и р = 0.6. Каждая из M[Ui] представлена двумя графиками, задающими нижнюю и верхнюю границу 95 %-го доверительного интервала. Очевидно, что ситуация похожа на предыдущую: здесь также наблюдаются точки пересечения, т.е. смена значения Nopt. По рис. 3.7 можно с уверенностью сказать, что при v[A]<2 получаем Nopt=l, а при v[A] > 2 получаем Nopt > 1.
Время, ед.вр,
667 617 567 517 467 417 367 317 267 217
ОД 0,4 0,7 1 1,3 1,6 1,9 2.2 2,5 2,8 Рис. 3.7. Зависимость времени пребывания заявок в СЭП от v[A]
При исследовании фактора v[A] было замечено, что наличие точек пересечения зависит от выбранного значения v[Z?] (он должен быть больше некоторого числа из интервала (1; 2)), тогда как при варьировании самого v[i?] такой зависимости от других факторов не было. По аналогии с предыдущим случаем для каждого из М[£Л] была получена аппроксимирующая функция. Оказалось, v[A] что с критерием достоверности аппроксимации Я =0.999 для всех трёх случаев она имеет вид:
М[Щ = СЗ-у2[А] + С4- У[А] + С5, (3.3) с разницей лишь в константах СЗ, С4, С5, которые не зависят от у[А] . Очевидно, что полученная закономерность может быть использована аналогичным образом (можно, например, чисто аналитически узнать значение у[А] , при котором Ыор1 = 3, т.к. определить это по рисунку нельзя из-за перекрытия границ доверительных интервалов М[Ш] и М[Ш]).
Рассмотрим теперь зависимость М[СЛ], которая представлена на рис. 3.8, на котором М[А] = ЮОед. времени, у[А] = 1, у[В]= 2.5. И снова видим схожую с предыдущими ситуацию: после некоторого значения варьируемого фактора более выгодным становится использовать СОП с большим числом обслуживающих приборов (на рис. 3.8) при р > 0,25 выгоднее использовать 3 прибора, чем 1.
ОД 0,15 0,2 0,25 03 0,35 0,4 0,45 0,5 0,55 0,6 0,65 0,7 Рис. 3.8. Зависимость времени пребывания заявок в СЭП от р
Однако и для р была замечена зависимость наличия точек смены Ыор1 от выбранного значения у[В], т.е независимое влияние оказывает только у[В], а два других фактора нужно рассматривать в непременной связи с у\В~\ .
Аппроксимирующие функции для М[СЯ] с критерием достоверности ап-2 проксимации R =0.999 для всех трёх случаев имеют вид:
С1
M[Ui] = C6---, (3.4)
1-р с разницей лишь в константах С6 и С7, которые не зависят от р.
Пример. Пусть в некоторой фирме используется выделенный канал Интернет 100 Мбит/с на витой паре. Предположим, что в связи с расширением фирмы становится необходимым удвоить указанную производительность канала. Возникает 2 альтернативы решения задачи:
- проложить дополнительный канал 100 Мбит/с на витой паре;
- отказаться от использования существующего канала (сдать его в утиль) и проложить новый, основанный на оптоволокне, и уже по нему оплатить подключение на скорости 200 Мбит/с.
Требуется с помощью САПР, использовавшейся при проектировании сети, провести анализ каждого из этих проектных решений. Очевидно, дешевле будет реализация первой альтернативы. Но согласно бытовавшим представлениям для минимизации задержек выгоднее должен был оказаться второй вариант. Рассмотрим конкретную ситуацию: замер параметров трафика в сети Fast Ethernet в течение часа случайно взятого времени показал, что v[A] = 2.1 , v[i?] = 1.31. Время прибытия в этом случае - это время между прибывающими пакетами. А время обработки определяется длиной пакета, т.к. скорость передачи постоянна. Если провести имитационное моделирование для загрузки 0,05-Ю, 15 (при которой характеристики измеряются очень точно), а затем по полученным данным построить аппроксимирующие функции для числа N = 1 и N= 2, то для M[U1] получим С6 = -183 и С7 = 274, для М[U2] получим С6 = -80 и С7 = 208. Если составить уравнение M[t/1] = M[U2] , то его решением будет р = 0.34, т.е. при р > 0.34 для минимизации задержек выгоднее использовать 2 канала, чем один. Иначе говоря, при определённой конфигурации потока пакетов с точки зрения минимизации задержек выгоднее использовать два низкоскоростных канала, чем один высокоскоростной.
§ 3.4. Выводы по главе 3
1. Аналитические приближённые методы синтеза проектных решений для систем с накопителями (памятью) неприменимы для получения оценки ёмкости накопителя, обеспечивающей заданную вероятность потерь, т.к. дают завышенную оценку (вплоть до сотен процентов при высокой и средней загрузке системы). Полученные результаты имитационных исследований позволили для ограниченного диапазона изменения нагрузочных параметров предложить метод синтеза проектного решения для верхней оценки ёмкости накопителя.
2. Решение задачи выбора оптимального числа приборов (при проектировании систем с эквивалентной производительностью) с точки зрения минимизации задержек, которое получено в предположении о простейшем потоке требований, нельзя распространять на весь класс приоритетных систем. Имитационные эксперименты показали, что необходимость увеличения числа приборов в СЭП (для минимизации задержек) возрастает:
- с увеличением загрузки;
- с увеличением коэффициента вариации времени между приходами заявок;
- с увеличением коэффициента вариации времени обслуживания заявок.
3. Полученные аппроксимирующие функции для отношения средней длины очереди к ёмкости накопителя могут быть использованы при решении задач синтеза проектных решений при проектировании систем с памятью.
4. Разработанный алгоритм сравнительного анализа систем с эквивалентной производительностью позволяет автоматизировать процесс проектирования таких систем при выборе оптимального числа обслуживающих приборов.
ГЛАВА 4. Практическая реализация разработанных моделей и методов
§ 4.1. Методика анализа и синтеза проектных решений в САПР технических систем с приоритетным управлением
Полученные в диссертации результаты позволяют предложить методику анализа и синтеза проектных решений при создании САПР СОП. При её использовании для обеспечения корректности получаемых результатов важно располагать точными данными о параметрах исследуемых систем, т.к. от них существенно зависит выбор конфигурации синтезируемой СОП.
Пусть с помощью разработанной методики нужно оценить характеристики функционирования компьютера в сети Fast Ethernet, выступающего в роли Интернет-шлюза при передаче VoIP-трафика. Пусть этот компьютер сконфигурирован так, что процесс обработки пакетов является строго последовательным и состоит из одного этапа. Это позволяет рассматривать такую систему как СОП, в которой роль заявок играют пакеты, а роль прибора - компьютер-шлюз. Тогда для использования разработанных методов нужно получить сведения о характере трафика Уо1Р-приложений. В табл. 4.1 приведён пример конфигурации трафика четырёх популярных приложений, полученный автором с использованием утилиты Wireshark, с помощью которой измерялись параметры генерируемого приложениями трафика в течение часа голосового общения.
Заключение
Главный научный результат диссертационной работы заключается в развитии, усовершенствовании и применении методов и моделей синтеза проектных решений, используемых при проектировании технических систем, в которых применяются правила управления, основанные на приоритетах. Полученные результаты можно рассматривать как решение актуальной научно-технической задачи, имеющей существенное значение для развития систем автоматизации проектирования. В диссертационной работе получены следующие основные научные и практические результаты.
1. Показано, что для эффективного синтеза и анализа проектных решений в САПР при проектировании систем с приоритетным управлением необходимо располагать детальными сведениями о свойствах и характеристиках используемых в таких системах приоритетных дисциплин обслуживания в широком диапазоне изменения структурно-функциональных и нагрузочных параметров. Известные результаты исследования приоритетных систем получены для узкого диапазона изменения параметров, что ограничивает их применение для проектирования реальных систем.
2. Проведённые исследования систем с дисциплиной обслуживания FIFO при произвольных законах распределения нагрузочных параметров позволили определить, при каких условиях тот или иной класс заявок получает преимущество в обслуживании. Впервые получена формула для верхней оценки преимущества в обслуживании, которое может получить класс обслуживаемых объектов (заявок), нагружающий такую систему меньше, чем агрегированный поток заявок всех прочих классов. Полученная зависимость позволяет на десятки процентов повысить точность оценок, используемых при принятии решений в процессе проектирования технических систем с использованием САПР.
3. Для приоритетных систем обслуживания с произвольным характером функционирования сформулирован закон сохранения вариации задержки, положенный в основу метода автоматизации проектирования приоритетных технических систем, в которых для оценки качества функционирования применяются рекомендации ITU-T Y.1541.
4. Предложен более точный, чем известные, метод выбора ёмкости накопителя в системах обслуживания, при которой вероятность потерь заявок в результате переполнения не превышает заданного значения. Предложенный метод позволяет повысить точность проектирования систем и приборов с памятью. В области средних и высоких загрузок и вероятности потерь более 10-4 полученный метод даёт минимум в 1,5-2 раза более точные оценки ёмкости накопителя, чем описанные в литературе методы.
5. Предложен метод, позволяющий автоматизировать решение задачи выбора оптимального числа приборов (с точки зрения минимизации задержек) при проектировании систем с эквивалентной производительностью при произвольных законах распределения нагрузочных параметров. Показано, что для решения этой задачи нельзя использовать результаты, полученные в литературе для случая, когда законы распределения параметров являются экспоненциальными.
6. Результаты проведённых исследований положены в основу инженерной методики анализа и синтеза проектных решений в САПР при проектировании приоритетных систем управления с учётом особенностей их структурно-функциональной организации и параметров нагрузки. Применение методики позволяет сократить сроки создания и ввода в эксплуатацию образцов новой техники, в которой используется система управления, основанная на приоритетах. Разработанные методы реализованы в виде комплексов программ, которые использовались различными организациями при проектировании технических систем разных классов.
Список литературы диссертационного исследования кандидат технических наук Соснин, Владимир Валерьевич, 2012 год
Библиографический список
1. Алиев Т.И. Основы моделирования дискретных систем. - СПб: СПбГУ ИТМО, 2009. - 363 с.
2. Алиев Т.П., Муравьева JI.A. Система с динамически изменяющимися смешанными приоритетами и ненадёжным прибором // Автоматика и телемеханика. - 1988. - № 7. - С. 99-106.
3. Алиев Т.П., Муравьева-Витковская JI.A., Соснин В.В. Моделирование: задачи, задания, тесты. - СПб: НИУ ИТМО, 2011. - 197 с.
4. Алиев Т.И., Соснин В.В. Динамическое управление потоком пакетов на основе смешанных приоритетов И Труды десятой международной научно-практической конференции "Современные информационные и электронные технологии" (СИЭТ-2009). - Одесса, 2009. - Т. 1. - С. 122.
5. Боев В. Д. Моделирование систем. Инструментальные средства GPSS World: Учебное пособие. - СПб.: БХВ-Петербург, 2004 - 368 с.
6. Бражник А.Н. Имитационное моделирование: возможности GPSS World. -СПб: Реноме, 2006. - 439 с.
7. Вадзинский Р.И. Справочник по вероятностным распределениям. - СПб: Наука, 2001.-295 с.
8. Вегешна Ш. Качество обслуживания в сетях IP. - М.: Издательский дом "Вильяме", 2003. - 368 с.
9. Вентцель Е.С., Овчаров JI.A. Теория случайных процессов и её инженерные приложения. - Учеб. пособие для втузов. - 2-е изд., стер. - М: Высш. шк., 2000.-383 с.
10. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. - М: Техносфера, 2003. - 512 с.
11. Воробейчиков JI.A., Сосновиков Г.К. Методические указания для слушателей ФПКП по моделированию систем и сетей связи на GPSS/PC. - М.: МТУСИ, 1993.-59 с.
12. Гнеденко Б.В., Даниелян Э.А., Димитров Б.Н., Климов Г.П., Матвеев В.Ф. Приоритетные системы обслуживания. - М.: Издательство Московского университета, 1973. -448 с.
13. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. - 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит. - 1987. - 336 с.
14. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания: Учеб. Пособие для вузов. - М.: Высш. школа, 1982. -256 с.
15. Кельтон В., Jloy А. Имитационное моделирование. Классика CS. 3-е изд. -СПб: Издательская группа BHV, 2004. - 847 с.
16. Клейнрок JI. Вычислительные системы с очередями. - М.: Мир, 1979. -598 с.
17. Клейнрок JI. Коммуникационные сети (стохастические потоки и задержки сообщений). - М.: Наука, 1970. - 256 с.
18. Клейнрок JI. Теория массового обслуживания. - М.: Машиностроение, 1979. -432с.
19. Кругликов В.К. Вероятностный машинный эксперимент в приборостроении.
- JL: Машиностроение, 1985. - 247 с.
20. Майоров С.А., Новиков Г.И., Алиев Т.И., Махарев Э.И., Тимченко Б.Д. Основы теории вычислительных систем. - М.: Высш. школа, 1978. - 408 с.
21. Муравьёва-Витковская JI.A. Методы исследования процессов управления неоднородным трафиком в телекоммуникационных системах // Кандидатская диссертация. - СПбГУ ИТМО, 2007. - 152 с.
22. Нгуен Д.Т. Методы и средства исследования распределённых сетей передачи данных с неоднородным трафиком на основе неэкспоненциальных моделей // Кандидатская диссертация. - СПбГУ ИТМО, 2009. - 145 с.
23. Олифер В.Г., Олифер H.A. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 4-е изд. - СПб.: Питер, 2010. - 944 с.
24. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. - СПб: КОРОНА принт, 2004. - 384 с.
25. Советов Б.Я., Яковлев С.А. Моделирование систем. - М.: Высшая школа, 1998.-320 с.
26. Соснин В.В. Динамическое изменение приоритетов для обеспечения требуемого уровня качества обслуживания в компьютерных сетях // Сборник докладов четвертой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности "Имитационное моделирование. Теория и практика" (ИММОД-2009).
- СПб., 2009. - Т. 1. - С. 177-181.
27. Соснин В.В. Исследование многоканальных систем массового обслуживания с эквивалентной производительностью // Научно-технический вестник
Санкт-Петербургского государственного университета информационных технологий, механики и оптики. - СПб., 2009. - №1 (59). - С. 34-39.
28. Соснин В.В. Моделирование дисциплины обслуживания с абсолютными приоритетами в GPSS World // Сборник докладов третьей всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности "Имитационное моделирование. Теория и практика" (ИММОД-2007). - СПб., 2007. - Т.1. - С. 224-229.
29. Соснин В.В., Алиев Т.И. Оценка емкости буферной памяти в промежуточных узлах телекоммуникационной сети // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. - СПб., 2008. - №56. - С. 81-85.
30. Соснин В.В., Нгуен Дык Тай. Анализ характеристик передачи пакетов через Интернет // Сборник докладов четвертой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности "Имитационное моделирование. Теория и практика" (ИММОД-2009). - СПб., 2009. - Т.2. - С. 245-249.
31. Соснин В.В., Шинкарук Д.Н. Моделирование маршрутизатора с поддержкой методов QoS в среде ns-З // Сборник трудов молодых учёных и сотрудников кафедры ВТ. Выпуск 2 / Под ред. д.т.н., проф. Т.И. Алиева. - СПб: СПбГУ ИТМО, 2011. - С.50-55.
32. Соснин В.В. Дисциплины обслуживания с прерываниями, реализуемые стандартными средствами GPSS // Труды пятой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД 2011).- СПб, 2011. - Т. 1. - С.275-281.
33. Соснин В.В. Свойства бесприоритетной дисциплины обслуживания в системах вида GI/G/1 // Труды пятой всероссийской научно-практической конференции по имитационному моделированию и его применению в науке и промышленности «Имитационное моделирование. Теория и практика» (ИММОД 2011). - СПб, 2011. - Т.2. - С.355-360.
34. Столингс В. Современные компьютерные сети. 2-е изд. - СПб.: Питер, 2003. -783 с.
35. Томашевский В., Жданова Е. Имитационное моделирование в среде GPSS. - М.: Бестселлер, 2003. - 416 с.
36. Шварц M. Сети связи: протоколы, моделирование и анализ. - М.: Наука, 1992.
37. Шнепс М. А. Системы распределения информации. Методы расчета. - М.: Связь, 1979.-344 с.
38. Шрайбер Т. Моделирование на GPSS. - М.: Машиностроение, 1980. - 592 с.
39. Boich G., Greiner S., Meer H., Triverdi К. Queueing networks and Markov chains: modeling and performance evaluation with computer science applications. -New York: John Wiley & Sons, 1998. - 726 p.
40. Braden R., Reynolds J., etc. 30 Years of RFCs //RFC2555. - The Internet Society, IETF, 1999. - Доступно по интернет-ссылке http://tools.ietf.org/rfc/rfc2555.txt.
41. Guerrero H. Excel Data Analysis. Modeling and Simulation. - Berlin: Springer, 2010.-353 pp.
42. ITU-T recommendation Y.1541. Amendment 1: An example showing how to calculate IPDV across multiple sections. - Geneva, 2006.
43. RFC Index. - The Internet Society, IETF, 2010. - Доступно по интернет-ссылке http ://too Is. ietf. org/ rfc.
44. Rubinstein R.Y., Kroese D.P. Simulation and the Monte Carlo method. - New Jersey: John Wiley & Sons, 2008. - 377 pp.
45. Sokolov A. Accuracy of the IP packet delay variation estimation // IEEE/ACM Transactions on Networking. - New York: IEEE, 2009. - p. 1810-1813.
46. Stidham S., Jr. Optimal design of queueing systems. - North Carolina: CRC Press, 2009.-384 pp.
47. Ulanovs P, Petersons E. Modeling of Self-similar traffic in high-performance Computer Networks // Report collection for 42 International Conference. - Riga: RTU, 2001.
48. Wainer G.A. Discrete-event modeling and simulation: a practitioner's approach. -Boca Raton: CRC Press, 2009. - 486 pp.
49. Wehrle K. et al. Modeling and Tools for Network Simulation. - Berlin: Springer, 2010.-545 p.
50. Willinger W. et al. Self-Similarity Through High-Variability: Statistical Analysis of Ethernet LAN Traffic at the Source Level // IEEE/ACM Transactions on Networking. - IEEE, 1997. - Vol. 5, No. 1.
Приложение. Акты внедрения результатов диссертации
На нижеследующих страницах приведены оригиналы или копии актов внедрения результатов диссертации в научно-производственный процесс нескольких научно-исследовательских и коммерческих предприятий.
у'УТВЕРЖДАЮ ,. Геяерпл1ный,директор
< ДавыдозУА.Е.
г.
'3
"■^"ТГЯх
Г
-X
АКТ
о внедрении результатов диссертационной работы Соснина Владимира Валерьевича «Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами», представленной на. соискание учёной степени кандидата технических наук.
Комиссия в составе
председателя
и членов:
гл.
(д.т.н., проф.),
ювича
зам. дйр. по НИОКР Савицкого Олега Константиновича (к.т.н., доц.), начальника комплексного научно-исследовательского отделения, сложных систем Смирнова Павла Игоревича, начальника сектора Дмитрия Павловича Хейстонена.
рассмотрев представленные материалы (описание программного средства «Имитационная модель комплекса обмена данными» и методику его использования для автоматизации проектирования компьютерных сетей) составила настоящий акт о том, что разработанная Сосниным В.В. методика проектирования маршрутизируемых 1Р-сетей позволила решить ряд задач анализа и синтеза в рамках создаваемой САПР компьютерной сети, в которой используется технология обеспечения качества обслуживания сШБегуС^оЗ с помощью приоритетных правил управления. Технический эффект от внедрения методики заключается в сокращении сроков проведения НИР и ОКР по САПР компьютерных сетей, разрабатываемой ФГУП «НИИ «Масштаб». Долевой экономический эффект, вызванный внедрением результатов работ Соснина В.В., составляет 5% от общего экономического эффекта. Данный ящг не является основанием для получения материального вознаграждения. А ур
Председатель комаесии ___'Давыдов Е.Б.
..... /ЦТ
Члены комиссии
Савицкий О.К. Смирнов П.И. Хейстонен Д.П.
ОБЩЕСТВО С ОГРАНИЧЕННОЙ ОТВЕТСТВЕННОСТЬЮ "ЛМТ"
№ i На ЗУа
от "j ><, •
\ УТВЕРЖДАЮ
Генеральный директор »«*1МТ>>. д.т.н.. проф.
CL Платунов А,Е.
АКТ
о внедрении результатов диссертационной работы Соснина Владимира Валерьевича «Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами», представленной на соискание учёной степени кандидата технических наук но специальности 05.13,12 («Системы автоматизации проектирования (приборостроение)»).
Комиссия в составе
председателя нач. лаб. Стародубцева Эдуарда Владимировича,
и членов: ст. науч. сотрудника Кустарева Павла Валерьевича,
ст. науч. сотрудника Кдючева Аркадия. Олеговича, -
составила настоящий акт о том, что следующие результаты диссертационной работы Соснина- В.В.:
- метод оценки времени отклика с помощью закона сохранения вариации задержки при использовании этого закона для проектирования диспетчера задач ОСРВ (данный метод изложен в главе 2 диссертации);
- метод выбора оптимального количества обслуживающих приборов в системах с эквивалентной производительностью при: его использовании для планирования, параллельных вычислений на многоядерных процессорах (данный метод изложен в главе 3 диссертации):
позволили сократить трудоёмкость расчётов при проектировании операционных систем реального времени (ОСРВ) на 5-10% и, как следствие, сократить сроки, проектирования.
Председатель комиссии
К.Т.Н., дон.
Члены комиссии
к.т.н. к.т.н.
Стародубцев Э.В.
Кустарев П.В. Едючев А. О.
у
Ч
199034, г.Санкт-Петербург. Биржевая линия, д. 16 тел./факс: (812)457-18-24; http://Jmufmo.ru, email: info@;Imt Jfmo.ru
САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ университет ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ
ШШл тшш^Мв
АКТ '
Ч»
УТВЕРЖДАЮ. Проректор НИУ ИТМ0 д/ф.-м.н., проф. ^Колесников Ю.Л.
2012 г.
о внедрении в учебный процесс результатов' %*ссертационной работы Соснина В.В. «Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами», представленной на соискание учёной степени кандидата технических наук.
Комиссия в составе
председателя д.т.н., проф. кафедры ВТ Ожигакова Александра Аркадьевича,
и членов: к.т.н., доц., зам. зав. кафедрой ВТ' Бессмертного Игоря
Александровича,
к.т.н., доц. Муразьевой-Витковской Людмилы Александровны, -
составила настоящий акт о том, что результаты диссертационной работы Соснина В. Б. внедрены в учебный процесс на кафедре вычислительной техники НИУ ИТМО для студентов, обучающихся по направлению 23.01.00 -«Информатика и вычислительная техника». Внедрение заключается в следующем:
1. По результатам диссертационной работы разработаны и изданы методические указания по использованию комплекса программ для дисциплин «Моделирование» и «Теория проектирования вычислительных систем и. сетей».
2. Теоретические результаты диссертационной работы, изложенные в главах 2 и 3 диссертации, включены в следующие разделы перечисленных выше дисциплин: «Оптимизация вычислительных систем и сетей», «Методы и средства проектирования вычислительных сетей».
3. Учебные варианты разработанных в рамках диссертационной работы программ, описанных в главе 4 диссертации, используются студентами при выполнении домашних заданий и лабораторных работ по дисциплинам «Моделирование» и «Теория проектирования вычислительных систем и сетей».
Председатель комиссии Ч л е ны коми с с ии:
Ожиганов А.А.
V
_Бессмертный И.А.
И - Муоавьева-Витковская Л. I
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.