Разработка моделей и методов синтеза проектных решений для технических систем с приоритетами

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

Результаты исследования. В работе исследовалось независимое влияние на М[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 = 2, при v[5] > 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[i/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. Результаты проведённых исследований положены в основу инженерной методики анализа и синтеза проектных решений в САПР при проектировании приоритетных систем управления с учётом особенностей их структурно-функциональной организации и параметров нагрузки. Применение методики позволяет сократить сроки создания и ввода в эксплуатацию образцов новой техники, в которой используется система управления, основанная на приоритетах. Разработанные методы реализованы в виде комплексов программ, которые использовались различными организациями при проектировании технических систем разных классов.