Содержание к диссертации
Введение
ГЛАВА 1. Классы обслуживания в сети atm и классификация механизмов управления буферным накопителем узла коммутации сети ATM 21
1.1. Характеристика классов обслуживания в сети ATM 21
1.2. Классификация механизмов управления буферным накопителем узла коммутации ATM 27
Выводы по главе 1 32
ГЛАВА 2. Модели механизмов управления буферными накопителями узла коммутации ATM 33
2.1. Описание предлагаемых механизмов управления буферными накопителями узла коммутации ATM , 33
2.2. Аналитические модели механизмов управления буферным накопителем с приоритетами узла коммутации ATM 39
2.2.1. Аналитическая модель механизма управления буфером без приоритетов 39
2.2.2. Аналитическая модель механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступающей нагрузки 42
2.2.3. Аналитическая модель механизма управления буфером с приоритетами, учитывающего состояние системы 46
2.2.4. Аналитическая модель механизма управления буфером с фиксированными приоритетами 48
2.3. Имитационная модель механизмов управления буферным накопителем с приоритетами узлов коммутации ATM 51
2.4. Анализ и сравнение ВВХ механизмов управления буфером, полученных аналитическим и имитационным методами 55
Выводы по главе 2 80
ГЛАВА 3. Определение эффективных значений параметра управления буфером узла коммутации ATM 82
3.1. Постановка задачи 82
3.2. Выбор аппарата векторной оптимизации 85
3.3. Выделение области компромиссов 89
3.4. Нахождение Парето-оптимальных решений для задачи управления буфером узла коммутации ATM 92
Выводы по главе 3 96
ГЛАВА 4. Задача оптимального распределения пропускных способностей в сетях с разнородной нагрузкой . 97
4.1. Постановка задачи 97
4.2. Разбиение задачи оптимального распределения пропускных способностей сети с разнородной нагрузкой на три эквивалентные подзадачи 103
4.3. Алгоритм решения задачи оптимального распределения пропускных способностей сети с разнородной нагрузкой 108
4.4. Пример решения задачи 109
Выводы по главе 4 110
Заключение 111
Список литературы 113
Приложение 123
- Классификация механизмов управления буферным накопителем узла коммутации ATM
- Аналитическая модель механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступающей нагрузки
- Анализ и сравнение ВВХ механизмов управления буфером, полученных аналитическим и имитационным методами
- Нахождение Парето-оптимальных решений для задачи управления буфером узла коммутации ATM
Введение к работе
Актуальность работы. Одним из основных свойств широкополосных цифровых сетей с интеграцией служб (Ш-ЦСИС) [27], использующих
* транспортную технологию ATM (Asynchronous Transfer Mode) [29, ЗО, 26],
является гарантия определенного качества обслуживания для каждого соединения
из множества виртуальных соединений с различными скоростями передачи и с
существенно отличающимися характеристиками. Требуемое качество
обслуживания в сети ATM может быть обеспечено только при использовании
эффективных методов управления ресурсами и борьбы с перегрузками [25, 31,3].
Разработка таких методов, наряду с решением задачи анализа вероятностно-
временных характеристик (ВВХ), рассматривались в большом количестве работ
[1, 2,14, 16, 18, 19,23,32,33, 35, 40,43,45,53, 64,65, 72,73,78, 82,83, 84,85, 86,
88, 94, 97, 98, 99, 108, 109, ПО, 119, 128, 130, 132, 133, 135, 136, 137]. В числе
авторов, получивших важные результаты в этой области, отметим отечественных
и зарубежных исследователей Г.П.Захарова, В.Г.Лазарева, А.Н. Назарова, М.В.
Симонова, С.Н.Степанова, В.СШибанова, Г.ГЛновского, M.Gerla, P. Kuhn, Т.
* Ors, Н. Saito, и др.
Известно, что сети, использующие технологию ATM, создавались для передачи разнородной нагрузки [12, 22, 27, 28, 33, 41,43, 70, 84, 86,110, 128, 137], и в первую очередь, передачи мультимедийной информации, содержащей данные, голос и видео, и изначально предусматривали соблюдение заданных для каждого типа нагрузки параметров качества обслуживания (Quality of Service, QoS) [3, 25, ЗІ]. Разнообразные типы приложений (услуг) с различными типами и характеристиками нагрузки и, соответственно, специфическими требованиями по качеству их обслуживания особенно характерны для сетей связи будущего, так называемых сетей следующего поколения (Next Generation Networks, NGN) [137, 33, 59, 9, 123]. Очевидно, что для обеспечения необходимых значений параметров
* качества обслуживания необходимы специфические механизмы управления
v нагрузкой. Однако, как показал анализ документов Форума ATM (ATMForum) [3]
и рекомендаций МСЭ-Т (Международного Союза Электросвязи - International Telecommunications Union, Telecommunication Standardization Sector, ITU-T) [25, 31], стандартизованные механизмы носят общий характер и не учитывают всех особенностей разнородной нагрузки, что важно для обеспечения качества обслуживания в современных телекоммуникационных сетях, учитывая скорость и тенденции их развития в направлении NGN. Поэтому сегодня для новых мультимедийных приложений, таких, как передача компрессированного голоса, видео, трафика Интернет, задача усовершенствования механизмов управления трафиком и ресурсами сети является, безусловно, актуальной.
Цель и задачи исследования. Целью диссертационной работы является исследование и разработка механизмов управления ресурсами в сетях ATM, оптимизация этих механизмов, а также разработка новых методов решения задач распределения пропускных способностей мультисервисных сетей. Поставленная цель обусловила необходимость решения следующих основных задач:
исследование и классификация механизмов управления ресурсами в сетях ATM;
разработка новых механизмов управления ресурсами в сетях ATM с целью их применения для улучшения качества обслуживания в сетях с мультимедийной нагрузкой;
анализ и сравнение предложенных механизмов с ранее известными;
разработка метода нахождения оптимального режима работы предложенных механизмов и решение задачи двухкритериальной оптимизации для сетей с мультимедийной нагрузкой;
разработка метода решения оптимизационной задачи распределения пропускных способностей мультисервисных сетей с учетом требований по качеству обслуживания, предъявляемых мультимедийной нагрузкой.
Методы исследования. Проводимые исследования базируются на теории вероятностей, теории массового обслуживания, математической статистике и методах имитационного моделирования.
Для численных расчетов использовались программные математические
пакеты Excel 7.0, Mathcad 7.0. Программное обеспечение необходимое для решения задач, использующих имитационное моделирование, реализовано с помощью пакета прикладных программ Stroboscop Simulation System v.1.3.
Научная новизна. Основными результатами диссертационной работы, обладающими научной новизной, являются:
Разработка аналитических методов и имитационных моделей для анализа поведения буферных накопителей узла коммутации ATM при различных механизмах бесприоритетного и приоритетного обслуживания при больших нагрузках.
Разработка механизмов управления ресурсами буферных накопителей узла коммутации ATM, обеспечивающих наилучшие показатели качества обслуживания для разнородной нагрузки в сетях ATM по сравнению с известными ранее механизмами.
Разработка подхода к определению оптимальных параметров механизмов управления ресурсами буферных накопителей узла коммутации ATM с учетом качества обслуживания для разнородной нагрузки в сетях ATM.
Решение оптимизационной задачи распределения пропускных способностей мультисервисных сетей минимальной стоимости с двумя ограничениями.
Практическая ценность. Внедрение результатов диссертационной работы показало, что результаты работы могут быть использованы на этапе планирования и проектирования сетей передачи информации, построенных на базе технологии ATM, в частности для оптимизации пропускных способностей сети ATM при предоставлении мультимедийных услуг, определения оптимальных объемов буферных накопителей и механизмов управления накопителями в узлах коммутации ATM, а также при эксплуатации широкополосных сетей, построенных на базе технологии ATM, обслуживающих мультимедийную нагрузку.
Реализация результатов работы. Основные результаты диссертационной работы внедрены в НИР ФГУП ЛОНИИС, при реализации проектов ОАО «Гипросвязь-СПб» и в учебном процессе СПб ГУТ им. проф. М.А. Бонч-Бруевича, что подтверждается актами о внедрении.
Апробация работы и публикации. Результаты диссертационной работы были представлены в форме докладов и обсуждались на следующих семинарах и конференциях:
ICINAS-1997: International Conference on Informational Networks and Systems, Yaroslavl, Sept. 8-12,1997;
Teletraffic Theory as a base for QoS: Monitoring, Evaluation, Decisions. International Teletraffic Seminar, St-Petersburg, LONIIS, 1998;
ICINAS-98: International Conference on Informational Networks and Systems. International Informatization Forum V, St.Petersburg, Sept. 7-12,
1998, St.Petersburg, LONIIS;
4. Научный семинар «Информационные сети и системы»: 26-27 октября
1999, Москва;
FZR-280 Conference, Dresden University, Dresden, 1999;
10-я Международная Конференция «СВЧ-техника и телекоммуникационные технологии CriMiCo'2000», Севастопольский Технический Университет, Севастополь, Крым, Украина, 11-15 сентября 2000г.
Пути создания интеллектуальной мультисервисной сети связи в составе российской инфотелекоммуникационной инфраструктуры: 1-ая Международная Конференция, СПб, 26 - 28 июня 2001 г.;
ICINAS-2000: International Conference on Informational Networks and Systems. International Informatization Forum VI: Proceedings, St.Petersburg, LONIIS, Oct.2-7, 2000;
11-я Международная Конференция «СВЧ-техника и телекоммуникационные технологии СгіМіСо'2001», Севастопольский Технический Университет, Севастополь, Крым, Украина, 10-14
сентября 2001г; 10. Международная Конференция по телекоммуникациям IEEE: ICC2001,
Спб Политехнический Университет, 11-15 июня 2001г.; И. ICINAS-2001: International Conference on Informational Networks and
Systems, St.Petersburg, 2001г.;
12-я Международная Конференция «СВЧ-техника и телекоммуникационные технологии СгіМіСо'2002», Севастопольский Технический Университет, Севастополь, Крым, Украина, 9-13 сентября 2002г.;
Информационные сети, системы и технологии (МКИССиТ-2002): Information Networks, Systems and Technologies (ICINSAT-2002). VIII Межд. конф., С.-Петербург, 16-19 сентября 2002 г.,
а также на научно-технических конференциях профессорско-преподавательского состава, научных сотрудников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича в 1997-2001 гг. и опубликованы в журнале "Проблемы информационной безопасности".
Основные положения, выносимые на защиту:
Аналитические и имитационные модели очередей в узлах коммутации ATM для различных механизмов бесприоритетного и приоритетного обслуживания разнородной нагрузки в сетях ATM.
Механизмы управления ресурсами буферных накопителей узлов коммутации ATM, обеспечивающие лучшие характеристики по качеству обслуживания для разнородной нагрузки в сетях ATM по сравнению с известными ранее механизмами.
Метод решения задачи оптимизации параметров разработанных механизмов управления ресурсами буферных накопителей узлов коммутации ATM с учетом требований по качеству обслуживания для разнородной нагрузки в сетях ATM.
Метод решения оптимизационной задачи распределения пропускных
способностей мультисервисной сети с учетом требований по качеству
обслуживания, предъявляемых разнородной нагрузкой.
Личный вклад автора. Основные результаты теоретических и прикладных
исследований получены автором лично. В работах, опубликованных в
соавторстве, соискателю принадлежит основная роль при решении поставленных
задач и обобщении полученных результатов.
Публикации. Основные результаты диссертационной работы опубликованы в 27 печатных работах.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Работа содержит 130 страниц машинописного текста, 25 рисунков, 10 таблиц, 71 формулу.
СОДЕРЖАНИЕ РАБОТЫ
Во Введении обоснована актуальность темы исследования, сформулированы цели и задачи работы, перечислены результаты диссертации, определены практическая ценность и области применимости результатов, приведены сведения об апробации работы и представлены основные положения, выносимые на защиту.
Диссертационная работа посвящена исследованию механизмов управления ресурсами в сетях ATM.
Под ресурсами сети ATM понимаются [29, 28, 136, 110]:
производительность узлов коммутации ATM,
емкости накопителей (буферов) узлов коммутации и
пропускные способности линий связи.
Ввиду того, что вопросы производительности узлов коммутации ATM на сегодняшний день достаточно хорошо изучены [41, 21, 23, 110, 12, 9, 108], в диссертационной работе они не рассматривались.
Анализу методов управления буферными накопителями узлов коммутации ATM посвящена первая глава диссертации. Вторая глава посвящена разработке новых методов управления буферами узлов коммутации ATM и их анализу на основе предложенных в диссертации моделей. В третьей главе получено решение задачи оптимизации параметров управления для разработанных методов управления ресурсами буферных накопителей. В четвертой главе решена задача оптимального распределения пропускных способностей мультисервисной сети с разнородной нагрузкой.
Первая глава диссертационной работы посвящена анализу методов управления буферными накопителями узлов коммутации ATM.
Проводится анализ рекомендаций МСЭ-Т и документов Форума ATM, касающихся характеристик классов обслуживания в сети ATM и основных механизмов управления трафиком и ресурсами сети ATM [3, 31], а также анализ и классификация известных методов управления буферными накопителями узлов коммутации [4, 6, 8, 10, 34, 36, 37, 38, 47, 50, 51, 60, 62, 68, 69, 75, 76, 80, 81, 98, ПО, 111, 128, 136]. Анализ проводится с целью выявления различий между существующими методами управления ресурсами мультисервисных сетей и определения их влияния на функционирование сетей ATM. В результате проведенного анализа показано, что стандарты МСЭ-Т и Форума ATM описывают требования по качеству обслуживания (QoS), предъявляемые к широкополосной сети для предоставлении широкого спектра услуг, но не содержат описаний конкретных механизмов управления буферными накопителями узлов коммутации такой сети, гарантирующих выполнение предъявляемых требований, но содержат общие рекомендации.
В первой главе также проведен анализ механизмов управления буферными накопителями узлов коммутации мультисервисных сетей с целью выявления различий между существующими методами управления ресурсами и определения их влияния на функционирование сетей ATM. Показано, что известные методы
управления буферными накопителями имеют ряд недостатков, в частности, не обеспечивают выполнение требований по качеству обслуживания одновременно для различных типов нагрузки, передаваемой в мультисервисной сети связи, что актуально в свете требований, представленных в первой главе в результате анализа международных стандартов. Это доказывает необходимость разработки новых, более сложных механизмов управления буфером, гибко учитывающих приоритеты с целью обеспечения требуемого качества обслуживания в современных мультисервисных сетях связи.
Предложены новые механизмы управления буферными накопителями. На основе проведенного анализа разработана классификация всех описанных механизмов управления буферным пространством узлов коммутации мультисервисной сети, в которой обозначено место механизмов, предложенных в диссертации. Предложенные механизмы управления ресурсами сети, представленные в диссертационной работе, проводятся в русле общих рекомендаций, содержащихся в международных стандартах.
Во второй главе описаны новые механизмы управления буферными накопителями узла коммутации ATM:
механизм управления буфером с приоритетами, учитывающий состояние системы и
механизм управления буфером с приоритетами, учитывающий состояние системы и интенсивность поступающей нагрузки.
Целью разработки данных механизмов является улучшение (по сравнению с известными ранее механизмами) двух основных показателей качества обслуживания мультимедийной нагрузки:
- вероятности потери ячейки рттеръ
и
it Тзадержки
- времени задержки ячейки 1
в буфере ATM.
Предлагаемые механизмы отличаются от ранее известных идеей разделения буферного пространства с целью организации отдельных очередей для
каждого класса нагрузки в мультисервисной сети и управления буфером на основе оценки состояния этих очередей с учетом текущих значений количества ячеек в буфере и интенсивности поступления ячеек каждого класса. В рамках диссертационной работы рассматриваются два класса нагрузки:
класс нагрузки, чувствительной к задержкам (КЧЗ) и
класс нагрузки, чувствительной к потерям (КЧГП.
Для сравнения показателей качества обслуживания предложенных механизмов управления буфером с ранее известными механизмами разработаны их аналитические и имитационные модели и получены соответствующие ВВХ.
При построении аналитических моделей предложенных механизмов рассматривается следующая система массового обслуживания (СМО): процесс поступления ячеек на каждый вход коммутатора ATM подчиняется закону Бернулли с интенсивностью нагрузки X; процесс обслуживания имеет постоянное время обслуживания, что обусловлено особенностью технологии ATM, в которой ячейки ATM имеют фиксированную (постоянную) длину; буфер имеет конечное число мест для ожидания и рассматривается четыре схемы назначения приоритетов для выбора заявки на обслуживание: без приоритетов; с фиксированным приоритетом; с приоритетом, зависящим от количества заявок в системе, и с приоритетом, зависящим от количества заявок в системе и интенсивности их поступления в систему.
Для построения ВВХ используется величины вероятности потерь ячеек
для нагрузки, чувствительной к потерям, Р^герь1 среднего времени задержки
ячеек для класса нагрузки, чувствительной к задержкам, Т^ержки> а также отношения времени задержки, которое определяется как отношение величины средней задержки для класса нагрузки, чувствительного к потерям, к среднему времени задержки для класса нагрузки, чувствительного к задержкам, т.е.
*р задержки кчп
пг задержки * кчз
Результаты имитационного моделирования сравниваются с результатами, полученными с помощью аналитической модели, и подтверждают правильность расчетов.
Для имитационного моделирования используется пакет прикладных программ Stroboscop Simulation System v. 1.3 и те же исходные данные, что и для аналитических расчетов. ВВХ получены для следующих механизмов управления буфером узла коммутации ATM:
Механизма управления буфером без приоритетов (известного ранее),
Механизма управления буфером с фиксированными приоритетами (известного ранее),
Механизма управления буфером с приоритетами, учитывающего состояние системы (предлагаемого в диссертации) и
Механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступления нагрузки (предлагаемого в диссертации).
В результате проведенного исследования, описанного в главе 2, показано, что применение предложенных механизмов управления буфером с приоритетами позволяет получить лучшие показатели качества обслуживания «вероятность потери ячейки» и «время задержки ячейки» по сравнению с известными ранее механизмами управления буфером, особенно в режиме больших нагрузок, а именно:
- Применение механизма управления буфером с приоритетами, учитывающего
состояние системы, на 8-10% улучшает параметр качества обслуживания
«время задержки ячейки» для класса нагрузки, чувствительного к задержкам, и
на 6-8% - параметр «вероятность потери ячейки» для класса нагрузки,
чувствительного к потерям, по сравнению с ранее известными механизмами
управления буфером. При этом данный эффект достигается при
незначительном ухудшении (в пределах норм) параметра «время задержки
ячейки» для класса нагрузки, чувствительного к потерям, и без превышения
допустимого значения параметра «время задержки ячейки» для класса
нагрузки, чувствительного к задержкам;
- Применение механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступающей нагрузки, на 10-12% улучшает параметр качества обслуживания «время задержки ячейки» для класса нагрузки, чувствительного к задержкам, и на 8-10% - параметр «вероятность потери ячейки» для класса нагрузки, чувствительного к потерям, по сравнению с указанными ранее известными механизмами управления буфером. При этом данный эффект достигается при незначительном ухудшении (в пределах норм) параметра «время задержки ячейки» для класса нагрузки, чувствительного к потерям, и без превышения допустимого значения данного параметра для класса нагрузки, чувствительного к задержкам.
Таким образом, основные результаты данной главы состоят в описании моделей бесприоритетных и приоритетных механизмов управления буфером в узле коммутации ATM, разработке методов их аналитического расчета и имитационного моделирования, анализе и сравнении полученных ВВХ и доказательстве того, что предложенные механизмы улучшают параметры качества обслуживания мультимедийной нагрузки в мультисервисной сети связи.
В третьей главе рассматривается дальнейшее развитие предложенных механизмов управления буфером коммутатора ATM в направлении оптимизации этих механизмов в зависимости от характера поступающей нагрузки с целью «настройки» параметра управления буфером предложенных механизмов под характеристики конкретных потоков нагрузки и, соответственно, достижения максимального эффекта от применения данных механизмов, т.е. максимального улучшения ВВХ.
Третья глава посвящена решению задачи оптимизации параметров управления предложенных во второй главе приоритетных механизмов распределения буферного пространства узлов коммутации с учетом требований по качеству обслуживания для разнородной нагрузки в сетях ATM.
Как показано в главе 2, механизм управления буфером коммутатора ATM с приоритетом, зависящим от состояния системы и интенсивности поступающей
нагрузки, имеет лучшие ВВХ по сравнению с другими механизмами управления буфером, исследованными в работе.
В главе 3 решается задача, являющаяся следующим шагом на пути повышения эффективности управления ресурсами в мультисервисных сетях, а именно задача определения области эффективных значений параметра управления буфером для механизма управления буфером с приоритетом, зависящим от состояния системы и интенсивности поступающей нагрузки.
С учетом того, что в коммутаторе ATM обслуживается мультимедийная нагрузка, в задаче нахождения оптимального значения параметра управления буфером имеются, как минимум, два критерия:
Т^а ржки - среднее время задержки ячеек в буфере для класса нагрузки, чувствительной к задержкам, и
Р^ерь - вероятность потерь ячеек в буфере для класса нагрузки,
чувствительной к потерям. Рассматриваемая задача определения области эффективных значений относится к классу многокритериальных задач векторной оптимизации [67, 74, 77]. Для ее решения используется метод оптимизации по Парето [67]. Критерий оптимизации представлен как вектор, состоящий из двух независимых компонент, а именно времени задержки для класса нагрузки, чувствительного к задержкам, и вероятности потерь для класса нагрузки, чувствительного к потерям
, гр задержки р потерь ^
VJ кчз » кип )'
Результаты оптимизации параметра управления буфером по методу Парето показали, что даже при больших нагрузках область Парето-оптимальных значений параметра управления буфером ограничивается узким диапазоном значений, что говорит о возможности достаточно точного выбора эффективного значения параметра управления при обслуживания мультимедийной нагрузки.
Четвертая глава посвящена решению задачи оптимального распределения пропускных способностей мультисервисной сети с разнородной нагрузкой. Предлагается подход, обеспечивающий решение оптимизационной задачи расчета пропускной способности линий связи мультисервисной сети
минимальной стоимости. Задача заключается в оптимальном распределении пропускных способностей линий связи мультисервисной сети с учетом требований по качеству обслуживания мультимедийной нагрузки.
В математической формулировке задачи используются модельные соотношения, базирующиеся на соотношениях, опубликованных в трудах ГЛ. Захарова [83, 87], и служащих для вычисления следующих характеристик, обслуживания мультимедийной нагрузки:
вероятности своевременной доставки в канале связи Q(/j) и
среднего времени доставки в канале связи сети T(ju).
В качестве критерия для сравнения между собой вариантов распределения пропускных способностей используется стоимостной показатель. Тогда оптимизационная задача расчета сетевого оборудования мультисервисной сети минимальной стоимости, удовлетворяющего требованиям по качеству обслуживания мультимедийной нагрузки, может быть сформулирована следующим образом:
Минимизировать стоимость сети
S(/i,//,.?,...) =>min
при ограничениях на критерии, связанные с Q(p) и Г(//):
S - стоимость системы,
2зад, тш " заданные значения Q и Tt причем Q^e[Qmin,QmJr
^задє^ min'-* max]'
ц - пропускная способность канала связи,
s - стоимость единицы пропускной способности канала связи.Рассматриваемая задача, в принципе, может быть решена методом возможных направлений, реализующим метод наискорейшего спуска применительно к задачам с ограничениями [54, 74, 78]. Метод представляет собой итерационный процесс, на каждом шаге которого необходимо решить вспомогательную задачу линейного программирования для определения возможного подходящего направления спуска и нелинейную оптимизационную
задачу определения шага в этом направлении. И если решение первой задачи затруднений не представляет, то вторая задача по сложности сопоставима с исходной и требует проведения специальных исследований. В целом процедура решения получается весьма громоздкой и не может быть рекомендована для практического использования.
В диссертации разработан метод, практически избавляющий от использования этой громоздкой процедуры метода возможных направлений для решения подобных задач. Исследование условий оптимальности решения, вытекающих из основной теоремы математического программирования, позволяют выделить области в плоскости значений Q3aa и 7^, в которых
исходная сложная задача сводится к эквивалентным, но существенно более простым задачам, как показано в данной главе. Предложенный метод позволяет решить поставленную оптимизационную задачу с двумя ограничениями с инженерной точностью.
В главе 4 диссертационной работы приведены алгоритмы решения задачи и приведен пример решения предложенным методом по описанному алгоритму. Важным результатом является вывод о возможности применения предлагаемого метода для любых задач с двумя ограничениями.
Анализ результатов расчетов, приведенных в главе 4, позволяет сделать вывод о том, что предложенный метод решения задачи оптимального распределения пропускных способностей с разнородными потоками существенно упрощает решение оптимизационных задач распределения ресурсов мультисервисной сети связи при наличии двух ограничений, накладываемых на сеть разнородными требованиями по качеству обслуживания для мультимедийной нагрузки.
Классификация механизмов управления буферным накопителем узла коммутации ATM
В общем случае все механизмы управления буфером можно разделить на механизмы управления буфером с приоритетами и без приоритетов. К последним относятся FIFO (First In - First Out или «первым пришел - первым обслужен») или LIFO (Last In - First Out или «последним пришел — первым обслужен») [80, 81,93].
В сетях ATM, обслуживающих мультимедийную нагрузку, в состав которой входят потоки различного типа, предъявляющие к сети свои требования по задержке и вероятности потерь, требуется применения более сложных механизмов управления буфером, а именно механизмов управления буфером с приоритетами.
Простейший механизм управления буфером с приоритетами - механизм управления буфером со статическим (фиксированным), то есть абсолютным, приоритетом [37,71, 75,76, 111]. Применительно к сетям ATM, обслуживающим мультимедийную нагрузку, и в соответствии с принятой нами терминологией, это означает, что сначала обслуживаются один класс нагрузки, например, чувствительный к задержкам (КЧЗ), а затем - другой, соответственно, чувствительный к потерям (КЧП).
Такой механизм обслуживания ячеек в буфере узла коммутации ATM способен обеспечивать небольшие задержки для КЧЗ, но при большом проценте нагрузки от КЧЗ задержка для КЧП может превышать допустимые пределы. Лишены этого недостатка механизмы управления буфером с динамическим приоритетом [17, 47, 49, 71, 75, 76, 98, 99], Приведем ниже краткую характеристику этих механизмов. Механизм OCF (Oldest Customer First или «наистарейшая информация обслуживается первой»). Приоритет в обслуживании предоставляется ячейкам с наибольшим временем пребывания в сети. Механизм EDF (Earliest Deadline First или «информация, имеющая наименьший срок окончания времени жизни, обслуживается первой»).Приоритет в обслуживании предоставляется ячейкам, которые имеют наиболее близкий срок окончания времени жизни.
Поскольку даже внутри нагрузки, чувствительной к задержкам, может быть множество классов, имеющих различные требования к задержке, то для удовлетворения всех их используется механизм HOL-PG (Head Of The Line with priority Jumps или «поток информации, имеющему наименьший срок окончания времени жизни, обслуживается первым»). Высший приоритет предоставляется классу нагрузки с более строгими требованиями к задержке. Это значит, что каждый класс приоритетов формирует свою очередь. Внутри каждого такого класса ячейки обслуживаются по FIFO, пока очереди с высоким приоритетом имеют приоритет, превосходящий очереди с более низким приоритетом. Определяются максимальные задержки ячеек внутри каждой очереди. Когда время ожидания ячейки превышает заданный предел, ячейка "перескакивает" в конец очереди со следующим более высоким приоритетом. Таким образом, задержка ячейки в очереди, прежде чем она поступит в очередь с наивысшим приоритетом, составляет сумму пределов задержек всех очередей с приоритетами, равными или большими, чем у класса данной ячейки. Обслуживание каждого класса контролируется с учетом величины предела задержки. Возможный недостаток описанного выше метода состоит в слишком больших требованиях к возможностям процессора (вычислительных затратах) узла коммутации ATM, требуемых для изменения приоритета ячеек, и в том, что каждая поступающая ячейка требует привязки по времени поступления. С учетом огромных скоростей передачи в сетях ATM реализация данного механизма выглядит мало реалистичной.
Механизм WFQ (Weighted Fair Queue или «Справедливая дисциплина обслуживания»). Механизм подобен процессу мультиплексирования с разделением времени (TDM), он выделяет полосу пропускания линии связи равными долями для различным потоков информации (источников). Механизм WFQ динамически регулирует полосы пропускания в зависимости от доступности/занятости линии. «Справедливая дисциплина обслуживания» предусматривает уменьшение джиггера и эффективное разделение приемлемой полосы пропускания между всеми источниками.
В данной главе предлагаются и анализируются следующие усовершенствованные динамические механизмы управления буфером с приоритетами узла коммутации ATM, реализация которых выглядит более реалистичной для сетей ATM. Перейдем к рассмотрению предлагаемых в диссертации новых методов управления буфером:
Механизм управления буфером с приоритетами, учитывающий состояние системы. Под состоянием системы будем понимать количество ячеек определенного класса нагрузки, находящихся в буфере к моменту окончания обслуживания очередной ячейки в обслуживающем приборе (то есть к моменту окончания передачи в линию из буфера очередной ячейки). При использовании данного механизма принятие решения о том, какой класс нагрузки выбрать из буфера для обслуживания, базируется только на числе ячеек каждого класса нагрузки в буфере в данный момент времени. Механизм управления буфером с приоритетами, учитывающий состояние системы и интенсивность поступающей нагрузки. В данном механизме в каждый момент времени учитывается как число ячеек каждого класса нагрузки в буфере, так и интенсивность поступления нагрузки каждого класса. С учетом этой информации принимается решение о том, ячейку какого класса нагрузки выбрать для обслуживания в следующий отсчет времени.
Нужно отметить, что существует большой выбор различных схем организации буферного пространства в узлах коммутации ATM. Узлы коммутации могут иметь буферное пространство, являющееся общим и используемое для хранения информации всех соединений. Узлы коммутации могут иметь разделенную память, где для каждого тракта, или даже для каждого соединения (например, для каждого виртуального соединения ATM) организован свой буфер. При этом буферы могут быть организованы как на входе узла коммутации (на входящих линиях), так и на его выходе (на исходящих линиях), и даже внутри коммутационного поля. Опираясь на мировой опыт производителей коммутационного оборудования [41, 9, 109, 73] можно заключить, что для сетей ATM наиболее эффективными признаны схемы организации узлов коммутации с выходными буферами, которым и посвящена работа. Механизмы управления буфером коммутатора ATM, предложенные и исследованные в данной главе, рассматриваются применительно к управлению как раз выходным буфером узла коммутации ATM (далее - коммутатора ATM).
В результате проведенного анализа показано, что известные методы управления буферными накопителями имеют ряд недостатков, в частности, не обеспечивают выполнение требований по качеству обслуживания одновременно для различных типов нагрузки, передаваемой в мультисервисной сети связи, что актуально в свете требований, представленных в Табл. 1 и 2. Это доказывает необходимость разработки новых, более сложных механизмов управления буфером, гибко учитывающих приоритеты с целью обеспечения требуемого качества обслуживания в современных мультисервисных сетях связи ВЫВОДЫ ПО ГЛАВЕ 1 1. На основе проведенного анализа международных стандартов приведено сравнение требований по качеству обслуживания, специфицированных МСЭ-Т и Форумом ATM для сетей ATM и разработана классификация механизмов управления буферным пространством узлов коммутации мультисервисной сети. 2. Показано, что существующие методы управления ресурсами, предлагаемые для использования в сетях ATM или уже применяемые, имеют ряд недостатков или накладывают некоторые ограничения, что обосновывает актуальность исследования и разработки новых механизмов управления ресурсами в сети с разнородным трафиком. 3. Поставлена задача выявления наиболее эффективных механизмов управления мультимедийным трафиком в буферных накопителях узлов коммутации ATM (решению данной задачи посвящена глава 2).
Аналитическая модель механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступающей нагрузки
В общем случае для расчета ВВХ могут использоваться два подхода: аналитический и имитационный. Каждый из подходов имеет свои преимущества и недостатки.
При аналитическом моделировании задача заключается в создании адекватной математической модели, включающей ряд уравнений, описывающих процессы передачи информации в системе, в которых неизвестными являются задержки, время доставки и т.п. Система уравнений решается или в явном виде, или численными методами. Основным преимуществом данного подхода является то, что аналитическое решение позволяет получать зависимость результатов от исходных данных, что очень полезно при решении задач оптимизации параметров системы. Однако, при использовании аналитического подхода порой невозможно учесть многие важные особенности анализируемой системы, поскольку при разработке аналитической модели приходится делать упрощающие предположения, позволяющие сделать аналитическую модель решаемой.
При использовании имитационного моделирования с точностью до наоборот инвертируются достоинства и недостатки аналитического моделирования. По результатам имитационного моделирования очень трудно с приемлемой точностью построить зависимости результатов от исходных данных, которые можно было бы использовать затем для задач оптимизации параметров системы, если в том есть необходимость. Однако, имитационная модель открывает для исследователя самые широкие (в зависимости от возможностей конкретного программного средства моделирования) возможности для детального учета особенностей анализируемой системы. Обычно при имитационном моделировании с учетом временных соотношений (в псевдореальном времени) имитируются все события, связанные с процессом обработки информации в системе (генерация нагрузки в источнике, обработка в узле связи, ожидание в очереди, передача в канале связи с учетом возможных потерь и задержек на каждой стадии обработки).
Программные системы моделирования являются мощным инструментом исследования и проектирования телекоммуникационных сетей и систем. Такие продукты позволяют проводить объективный предварительный анализ для обоснования телекоммуникационных проектов и при исследовании новых предложений с точки зрения их технико-экономических и качественных показателей.
Назначение программ математического моделирования заключается в анализе вероятностно-временных характеристик (ВВХ) доставки информации и надежности телекоммуникационной сети, в оценке стоимости ее создания и эксплуатации. Рассматривая различные варианты топологии, используемых каналов и оборудования, а также систем обслуживания можно выбрать оптимальный вариант с точки зрения стоимости и степени удовлетворения требованиям по качеству обслуживания. Моделирование позволяет проверить результаты, полученные аналитическим способом, и последствия внедрения тех или иных решений до реализации или установки готового оборудования. С помощью моделирующих систем можно анализировать работу отдельных компонентов системы, получать данные о загрузке оборудования, выявлять «узкие места» и т.п. Использование компьютерного моделирования обходится гораздо дешевле физического (с использованием стендов или готового оборудования), а количество исследуемых вариантов может быть значительно шире. Создать программу имитационного моделирования можно самостоятельно, но можно воспользоваться и доступными фирменными пакетами прикладных программ [79, 42, 9, 38, 133, 58, 89]. Среди известных можно назвать, например, пакет прикладных программ Stroboscop Simulation System, пакет прикладных программ для имитационного моделирования сетей связи NS2 [24] и др. В силу того, что возможности многих программ имитационного моделирования уже не отвечают требованиям моделирования современных высокоскоростных систем, а NS2 является современным, но весьма сложным решением, требующим долгой «настройки» и больших вычислительных мощностей, нами был выбран пакет прикладных программ Stroboscop Simulation System v.1.3.
Внешний вид рабочего окна программирования Stroboscop Simulation System v,1.3 (в данном случае - ввода исходных данных для моделирования) представлен на рис.П 1.1 в Приложении 1.
На рис.П 1.2 в Приложении 1 представлен интерфейс рабочего окна программирования ППП Stroboscop Simulation System v. 1.3 (окна создания логики работы имитационной модели, в представленном примере - процессов поступления ячеек в буфер и обслуживания ячеек в буфере, т.е. собственно механизма управления).
Здесь представлена имитационная модель, построенная для механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступающей нагрузки, с помощью программного пакета Stroboscop Simulation System с использованием исходных данных, которые использовались также в аналитическом методе исследования этого механизма, приведенном в п.2.1.
На Рис. 2.3 представлена схема имитационной модели, построенная с помощью программного пакета Stroboscop Simulation System v. 1.3 для механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступления нагрузки. Схема описывает логику работы системы управления буфером (см. рис. 2.2) для механизма управления буфером с приоритетами, учитывающего состояние системы и интенсивность поступающей нагрузки.
Анализ и сравнение ВВХ механизмов управления буфером, полученных аналитическим и имитационным методами
Отношения времени задержки для последних одинаковы, так как коэффициент ЛГКЧЗ=0,5 и, следовательно, ЛКчз=Лкчп и отношение - эквивалентно отношению t;K4" ,—. В механизме с фиксированным приоритетом отношение времени задержки возрастает с увеличением интенсивности поступающей нагрузки, а в механизмах, учитывающем состояние системы и учитывающем состояние системы и интенсивность поступающей нагрузки отношение времени задержки сначала возрастает, а затем постепенно приближается к величине управляющего параметра R, когда интенсивность поступающей нагрузки приближается к 0,9. Кроме того, отношение времени задержки для этих механизмов возрастает с ростом параметра R. При R - » оба указанные механизма становятся аналогичны механизму с фиксированным приоритетом. При Л=1 отношение времени задержки больше 1. Это значит, что среднее время задержки для класса нагрузки, чувствительного к задержкам, меньше, чем среднее время задержки для класса нагрузки, чувствительного к потерям. На рис.2.4,6 представлена зависимость среднего времени задержки ячеек каждого класса от интенсивности поступающей нагрузки при использовании различных механизмов управления буфером, когда доля нагрузки, чувствительной к задержкам, составляет ЛГкчз=0,95, при фиксированном значении R для механизмов управления буфером М2, МЗ и М4 при значении управляющего параметра R=2. Как было упомянуто выше, при АГКЧз=0,5 время задержки для МЗ и М4 одинаково. Среднее время задержки для нагрузки, чувствительной к задержкам, для механизма М4 больше, чем для механизма М2, в то время как среднее время задержки для нагрузки, чувствительной к потерям, для механизма М4 меньше, чем для механизма М2. Таким образом, улучшение времени задержки для нагрузки, чувствительной к потерям, происходит за счет ухудшения времени задержки для нагрузки, чувствительной к задержкам. На рис. 2.5 (а и б) размер буфера равен 50, число выходных портов коммутатора ATM равно 16, и доля нагрузки, принадлежащей классу нагрузки, чувствительному к задержкам, KK4j равна 0,95. При таком параметре /Гкчз большая часть нагрузки является чувствительной к задержкам. На рис. 5а представлена зависимость отношения времени задержки разных классов нагрузки от загрузки системы для механизма с фиксированным приоритетом и механизмов с приоритетами М4 и МЗ. Из рис. 2.5 видно, что отношение времени задержки для механизма М4 значительно меньше, чем для механизма МЗ. Причина этого заключается в том, что интенсивность нагрузки, чувствительной к задержкам, Лкчз значительно превосходит интенсивность нагрузки, чувствительной к потерям, Лкчп вследствие чего K4! -R 1. Другими словами, поскольку в механизме М4 мы рассматриваем интенсивность нагрузки каждого класса, поведение механизма М4 можно представить как поведение механизма МЗ с управляющим параметром R = R. На рис. 2.56 представлена зависимость времени задержки для каждого класса нагрузки от загрузки системы для различных механизмов обслуживания. Управляющий параметр R для механизмов М4 и МЗ равен 2. В механизме МЗ среднее время задержки для нагрузки, чувствительной к задержкам, пренебрежительно мало возрастает по сравнению с механизмом с фиксированным приоритетом, в то время как среднее время задержки для нагрузки, чувствительной к потерям, пренебрежительно мало уменьшается. В механизме М4 среднее время задержки для нагрузки, чувствительной к задержкам, пренебрежительно мало возрастает по сравнению с механизмом с фиксированным приоритетом, в то время как среднее время задержки для нагрузки, чувствительной к потерям, уменьшается значительно. Улучшение времени задержки для механизма М4 лучше, чем улучшение времени задержки для механизма МЗ. Как было сказано выше, большую часть нагрузки здесь составляет нагрузка, чувствительная к задержкам, что часто является причиной «зависания» в буфере нагрузки, чувствительной к потерям. В любом случае, в обоих механизмах М4 и МЗ проблема «зависаний» в буфере уменьшается, а в качестве компромисса выступает пренебрежимо малое увеличение времени задержки для нагрузки, чувствительной к задержкам. Очевидно, что в случае преобладания нагрузки, чувствительной к задержкам, выгоднее использовать механизмы с приоритетами, учитывающие состояние системы, чтобы контролировать время задержки для обоих типов нагрузки.
Нахождение Парето-оптимальных решений для задачи управления буфером узла коммутации ATM
Первая проблема связана с выбором принципа оптимальности, который строго определяет свойства оптимального решения и отвечает на вопрос, в каком смысле оптимальное решение превосходит все остальные допустимые решения. В формулах (3.5, 3.6) это соответствует раскрытию оператора оптимизации opt вектора эффективности. В отличие от задач однокритериальной оптимизации, у которых только один принцип оптимальности у(Хр ) у(Х), в случае многокритериальных задач имеется большое количество различных принципов оптимальности, и каждый принцип может приводить к выбору различных оптимальных решений. Это объясняется тем, что приходится сравнивать векторы эффективности на основе некоторой схемы компромисса, то есть выбирать критерии по своей значимости и т.п.
В математическом отношении эта проблема идентична задаче упорядочивания векторных множеств, а выбор принципа оптимальности opt — выбору отношения порядка.
Следует заметить, что данная проблема часто именуется проблемой скаляризации ввиду того, что, как правило, выбор принципа оптимальности приводит к некоторому обобщенному скалярному критерию, являющемуся функцией локальных критериев. Однако, в нашем случае, применить этот принцип невозможно ввиду невозможности адекватной скаляризации критериев из-за того, что они имеют разную природу и, соответственно, разные единицы измерения, как отмечалось в п.3.1.
Вторая проблема связана с нормализацией векторного критерия эффективности У. Она вызвана тем, что очень часто локальные критерии, являющиеся компонентами вектора эффективности, имеют различные масштабы измерения и их сравнение становится трудным или даже невозможным. Поэтому приходится приводить критерии к единому масштабу измерения, т. е. нормализовать их. Данная проблема так же не имеет отношения к нашей задаче в виду разницы в единицах измерения критериев оптимальности.
Третья проблема связана с учетом приоритета (или различной степени важности) локальных критериев. Хотя при выборе решения и следует добиваться наивысшего качества по всем критериям, однако степень совершенства по каждому из них, как правило, имеет различную значимость. Поэтому обычно для учета приоритета вводится вектор распределения важности критериев Л=(Л\,Л2,...,Лп), с помощью которого корректируется принцип оптимальности или проводится дифференциация масштабов измерения критериев. В случае нашей задачи речь идет о векторе распределения важности критериев ТзалКЧз и Рпот_кчп вида Л=(ЯіД2). где Х\ - важность критерия 7 3, а Хг - важность критерия
С описанными выше проблемами связаны основные трудности многокритериальной оптимизации, и от того, насколько успешно они преодолены, во многом зависят успех и правильность выбора решения. Надо отметить, что все эти трудности носят не вычислительный, а концептуальный характер. Поэтому здесь непременно должно участвовать лицо или орган, ответственные за принятие решения. В задачах выбора решения, формализуемых в виде модели векторной оптимизации, в качестве первого шага решения задачи необходимого произвести выделение области компромиссов (или решений, оптимальных по Парето [67, 90]).
Областью компромиссов Гх (в нашем случае - Гя) называется подмножество допустимого множества решений Dx (в нашем случае - D«), обладающее тем свойством, что все принадлежащие ему решения не могут быть улучшены одновременно по всем локальным критериям — компонентам вектора эффективности. Следовательно, для любых двух решений, принадлежащих этому подмножеству Х\Х"еГх (в нашем случае - R\R"erR), обязательно имеет место противоречие хотя бы с одним из локальных критериев. Это автоматически приводит к необходимости проводить выбор решения в Гх (в нашем случае - /д) на основе некоторой схемы компромисса, что и послужило причиной для названия этого подмножества областью компромиссов. В теории кооперативных игр [77] эта область именуется «переговорным множеством» и имеет ясный смысл: переговоры следует вести только о решениях из этого множества, так как любое решение вне его может быть улучшено одновременно для всех партнеров.
Легко увидеть, что оптимальное решение, выбираемое на основе многокритериального подхода независимо от избираемого принципа оптимальности, всегда должно принадлежать области компромиссов. Иначе оно может быть улучшено и, следовательно, не является оптимальным. Таким образом, область компромиссов есть область потенциально оптимальных решений. В нее также входят и локальные оптимальные решения, т.е. решения оптимальные по одному из локальных критериев. Следовательно, при выборе решения по векторному критерию эффективности можно ограничить поиск оптимального решения областью компромиссов Гх (в нашем случае - Гц), которая, как правило, значительно уже всей области возможных решений Dx (в нашем случае - DR).
Приведенному определению области компромиссов rR соответствует модель выбора: При реализация модели (3.7) в случае невыпуклых задач помимо глобального оптимума необходимы определения всех локальных оптимумов, а также их проверка на условия доминирования. Реализация модели (3.7) для выпуклого допустимого множества требует нахождения глобального оптимума. Условия выпуклости задач векторной оптимизации определяются выпуклостью области Dx в пространстве критериев.
Для случая выпуклых задач с двумя критериями [67] был предложен так называемый геометрический способ определения области компромиссов. Задача отыскания оптимального значения параметра управления R механизма управления буфером с приоритетом, зависящим от состояния системы и интенсивности поступающей нагрузки, является задачей с двумя критериями. Поэтому для использования этого метода остается только проверить область компромиссов на выпуклость.
