Содержание к диссертации
Введение
ГЛАВА 1 АНАЛИЗ МЕХАНИЗМОВ QOS В ТЕХНОЛОГИИ DIFFSERV 16
1.1 Сети следующего поколения и QOS 16
1.1.1 Параметры QoS 16
1.1.2 Различное понимание QoS для разных видов трафика 17
1.1.3 Пересчёт требуемого QoS соединения в параметры QoS узла 20
1.1.4 Средства обеспечения QoS 22
1.1.5 Дозирование средств обеспечения QoS 25
1.2 Технология дифференцированных услуг (DIFFSERV) 25
1.2.1 Терминология дифференцированных услуг 26
1.2.2 Классы трафика и поле DSзаголовка дейтаграммы 34
1.2.3 Сетевая архитектура DiffServ 37
1.2.4 Архитектура узла DiffServ 40
1.2.5 Поведение на переходе (РНВ) и дисциплина обслуживания 44
1.3 Дисциплины ОБСЛУЖИВАНИЯ (ДО) 47
1.3.1 Простая очередь (First In, First Out - FIFO) 48
1.3.2 Приоритетные очереди (Priority Queuing) 48
1.3.3 Взвешенная справедливая буферизация (Weighted Fairness Queuing-WFQ) 49
1.3.4 Очереди no классам (Class-Based Queuing- CBQ) 50
1.3.5 Отбрасывание хвоста (Tail Drop) 50
1.3.6 Случайное раннее отбрасывание (Random Early Detection -RED) 51
1.4 Концепция имитационной дисциплины обслуживания
(ИДО) 52
1.4.1 Место моделирования трафика в ДО. 53
1.4.2 Определение имитационной ДО 54
1.4.3 Моделирование и прогнозирование , 55
1.4.4 Микро-и макроуправление 56
1.4.5 Сопоставление имитационной ДО и обычных ДО 56
Выводы 57
ГЛАВА 2 РАЗРАБОТКА МОДЕЛЬНОЙ РЕАЛИЗАЦИИ ИДО 59
2.1 Подсистема времени 60
2.2 Разработка модели источников мультисервиснои нагрузки 61
2.2.1 Архитектура модели источников 61
2.2.2 Модельные агрегаты трафика 63
2.3 Разработка подсистемы ведения очередей с контролем QOS 64
2.3.1 Параметры QoS 65
2.3.2 Параметры управления 65
2.3.3 Алгоритм работы подсистемы ведення очередей 66
2.3.4 Характеризагщяразработанной СМО , 67
2.4 Оптимизация управления 67
2.4.1 Математическая постановка оптимизационной задачи управления 68
2.4.2 Целевая функция 70
2.4.3 Условный и безусловный прогноз 71
2.4.4 Методика дискретной оптимизации 71
2.4.5 Временные параметры оптимизации 72
2.5 Эволюция ДИНАМИЧЕСКОЙ СИСТЕМЫ 73
Выводы 74
ГЛАВА 3 НЕЙРОСЕТЕВОЕ ПРОГНОЗИРОВАНИЕ 76
3.1 Анализ нейросетевого прогнозирования 76
3.2 Разработка нейросетевого предиктора 78
3.2.1 Обобщённая оцифровка 79
3.2.2 Прогнозирование на несколько шагов вперёд 81
3.2.3 Структура нейросети предиктора 81
3.3 Обучение нейросетевого предиктора 85
3.3.1 Метод обратного распространения 85
3.3.2 Метод сопряжённых градиентов 55
3.3.3 Имитация отжига 91
3.4 Тестирование нейросетевого предиктора 91
Выводы 94
ГЛАВА 4 ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ РЕАЛИЗАЦИИ ИДО 96
4.1 Временные параметры оптимизации 97
4.2 Эволюция с управлением и без управления 98
4.3 Идеальный предиктор 103
4.4 Обсуждение результатов численного эксперимента 106
выводы 107
Заключение 109
Список литературы 111
ПРИЛОЖЕНИЕ 1. Вывод соотношений ортогональности градиентов и
сопряженности направлений в методе сопряжённых градиентов 120
- Сети следующего поколения и QOS
- Разработка модели источников мультисервиснои нагрузки
- Анализ нейросетевого прогнозирования
- Временные параметры оптимизации
Введение к работе
Актуальность проблемы. В настоящее время внимание мирового телекоммуникационного сообщества сосредоточено на концепции сетей, которые обеспечивают предоставление любых услуг электросвязи на основе единой сетевой инфраструктуры, таких как сети следующего поколения (NGN) [7,22, 30, 99,15, 55,95,14,1, 16,17].
Одним из важнейших аспектов сетей следующего поколения является обеспечение качества обслуживания (QoS) для всех услуг, поддерживаемых сетью [57, 23, 56]. Трудность заключается в том, что требования QoS для каждого сервиса свои, а сетевые ресурсы, которыми обеспечиваются эти требования - общие. Естественной представляется идея разделить сетевые ресурсы по сервисам по справедливости. Эта идея присутствует практически во всех концепциях, используемых в NGN, таких как IntServ [72, 74], DiffServ [78,76, 83, 84], MPLS [86, 5]. Сейчас эти технологии обычно рассматриваются как взаимодополнительные [85, 23, 88].
Однако разделить сетевые ресурсы по сервисам недостаточно. Точнее, надо позаботиться о том, чтобы это разделение было достаточно эффективным. Ведь, в худшем случае, можно полностью лишиться достоинств единой сети многих услуг, превратив её в независимые наложенные сети. Поэтому крайне важна разработка механизмов взаимодействия сервисов в NGN обеспечивающих, с одной стороны, эффективность использования общих сетевых ресурсов, а с другой стороны, достаточную изоляцию сервисов, чтобы обеспечить специфическое для каждого сервиса качество обслуживания.
В качестве системно-сетевого контекста таких механизмов выбрана технология дифференцированных услуг (DiffServ) сетей IP. В её рамках определены [78] обобщённые описания поведения агрегатов трафика, соответствующих отдельным сервисам - РНВ и находится естественное место для средств контролируемого взаимодействия сервисов - механизмы реализации РНВ. Эталонным примером механизма в DiffServ является дисциплина обслуживания.
Дисциплина обслуживания является концептуальной основой СМО и обеспечивает большую или меньшую эффективность сетевого узла дифференцированных услуг с этой СМО. Существующие дисциплины обслуживания [58, 96, 48, 97, 98, 51, 69] недостаточно рассматривают некоторые аспекты работы СМО. Сравнительно подробно разработаны вопросы порядка буферизации (например, дисциплины FIFO, WFQ, CBQ) и отбрасывания пакетов (TailDrop, RED, WRED), а также алгоритмы управления и выравнивания нагрузки (LeakyBucket, TokenBucket). Однако эти механизмы обычно рассматривают распределение ресурсов по агрегатам трафика, как заданное извне. Оптимизации распределения ресурсов по агрегатам трафика в узле DiffServ посвящена данная диссертационная работа.
Цель и задачи исследований. Целью диссертационной работы является разработка дисциплины обслуживания мультисервисного трафика, распределяющая доступные сетевые ресурсы по агрегатам трафика оптимальным (в некотором смысле) образом. Поставленная цель достигается решением следующих основных задач.
Анализ параметров QoS и пересчёт их в ограничения экстремальной задачи управления трафиком. .
Формулировка экстремальной задачи управления и включение её в архитектуру дифференцированных услуг. Минимизируется функция потерь трафика в обозримом будущем при условии выполнения требований QoS для обслуженного трафика и при условии заданного поведения сетевого окружения узла дифференцированных услуг.
Анализ существующих дисциплин обслуживания на предмет возможностей управления ими и возможностей перераспределения ресурсов между агрегатами трафика.
Разработка концепции имитационной дисциплины обслуживания как средства решения задачи оптимального управления. Для вычисления целевой функции необходимо знать будущие потери трафика, что требует имитационного моделирования этого будущего. Поведение окружения узла DiffServ самому узлу не известно и может быть только спрогнозировано. Следовательно, необходима подсистема прогнозирования.
Разработка модельной системы, состоящей из сетевого окружения и узла дифференцированных услуг с возможностью включения/выключения имитационной дисциплины обслуживания. Система связывает в единое целое подсистемы, о которых сказано ниже.
Разработка модельного окружения узла DiffServ - модели источников мультисервисной нагрузки. Модель источников должна адекватно реагировать на потери своих пакетов сетью. Иначе невозможна корректная оптимизация управления.
Разработка подсистемы ведения очередей с возможностью управления и с контролем параметров QoS трафика DiffServ.
Разработка подсистемы оптимизации параметров управления. Подсистема оптимизации оценивает пробный набор параметров управления по предсказанному будущему при данном управлении.
Разработка подсистемы прогнозирования поведения источников трафика. Прогноз может опираться только на информацию, доступную узлу DiffServ. Предиктор основан на искусственной нейронной сети, обучаемой на реальной предыстории трафика.
Разработка подсистемы обучения нейросети с учётом специфики обучающего ансамбля как предыстории.
11. Численный эксперимент реализации имитационной дисциплины обслуживания. Сравнение поведения модельной системы при обыкновенной и при имитационной дисциплинах обслуживания.
В процессе исследований получено не только оптимальное распределение ресурсов дисциплиной обслуживания, но решена более общая задача - оптимальное управление сетевым узлом. Иначе говоря, можно управлять не только распределением ресурсов. Например, оптимизацией превентивного отбрасывания пакетов можно улучшить поведение даже единственного агрегата трафика.
Методы исследований. Проведённые в диссертационной работе исследования основаны на теории вероятностей, теории массового обслуживания, теории искусственных нейронных сетей, вычислительной математике и линейной алгебре.
Исследования основаны также на разработках IETF в области сетевых аспектов развития телекоммуникаций. В первую очередь, на понятийном аппарате и моделях рабочей группы DiffServ.
Для проведения численных расчётов, моделирования и отображения функциональных зависимостей использовался программный продукт MatLab.
Научная новизна. Основными результатами диссертационной работы, обладающими научной новизной, являются: модель источников мультисервисного трафика с обратной связью сети на источники; обобщённая оцифровка для сигмоидальных нейросетей; концепция и модельная реализация имитационной дисциплины обслуживания.
Практическая ценность. Основными результатами диссертационной работы, обладающими практической ценностью, являются: имитационная дисциплина обслуживания; нейросетевой предиктор входящего трафика.
Имитационная дисциплина обслуживания представляет практическую ценность и как концепция, и как реализация вместе с модельным окружением. Последняя может служить примером практической реализации концепции динамической оптимизации управления на основе имитации будущего поведения системы.
Нейросетевой предиктор обладает также самостоятельной практической ценностью безотносительно к имитационной дисциплине обслуживания.
Апробация работы и публикации. Результаты диссертационной работы были представлены в форме докладов на следующих научно-технических конференциях: международная конференция "Информационные сети, системы и технологии" (МКИССиТ-2006), 30 октября - 2 ноября 2006, Санкт-Петербург; международный телекоммуникационный симпозиум "Мобильная связь. Мультисервисные услуги в высокоскоростных системах мобильной связи", 27-30 июня 2006, СПб.
Результаты диссертационной работы были представлены в форме следующих публикаций: статья в журнале "Электросвязь": 2005, №8, с.24-26; статья в журнале "Электросвязь": 2006, №8; учебное пособие: Кучерявый А.Е., Станкевич А.А. Пакетная сеть связи общего пользования. Дифференцированные услуги. - СПб.: Изд. СПбГУТ им. проф. М.А.Бонч-Бруевича, 2004. учебное пособие: Кучерявый А.Е., Иванов АЛО., Станкевич А.А. Протокол SIGTRAN. - СПб.: Изд. СПбГУТ им. проф. МА.Бонч-Бруевича, 2004. учебное пособие: Кучерявый А.Е., Иванов АЛО., Станкевич А.А. Протоколы SIP и SIP-T. - СПб.: Изд. СПбГУТ им. проф. М.А.Бонч-Бруевича, 2005.
Основные положения, выносимые на защиту: постановка задачи оптимального управления узлом дифференцированных услуг при условии заданного поведения сетевого окружения и выполнения ограничений QoS; концепция имитационной дисциплины обслуживания как средства решения задачи оптимального управления; реализация имитационной дисциплины обслуживания в составе модельной сети, обеспечивающая оптимизацию распределения ресурсов по агрегатам трафика в узле DiffServ; нейросетевой предиктор с эффективным использованием динамического диапазона сигмоидальных нейронов, благодаря обобщению двоичного разряда числа.
Личный вклад автора. Основные положения, теоретические выводы и рекомендации, содержащиеся в диссертационной работе, получены автором самостоятельно.
Публикации, Основные результаты диссертационной работы представлены в 7 печатных работах.
Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и одного приложения.
Работа содержит 122 страницы машинописного текста, включая 26 рисунков, список литературы из 102 наименований и приложение.
СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность исследования, сформулированы цели и задачи диссертационной работы, перечислены основные полученные результаты диссертации, определены практическая ценность и области использования полученных результатов. Приведены сведения об апробации работы, представлены основные положения, выносимые на защиту.
В первой главе проведён анализ механизмов обеспечения качества обслуживания в сетях связи следующего поколения. Проанализированы значения параметров QoS разных сервисов (агрегатов трафика) для соединения в целом и для отдельного мультисервисного узла. Сформулированы ограничения QoS для экстремальной задачи оптимального управления трафиком. Проанализирована технология дифференцированных услуг в качестве системно-сетевого средства внедрения QoS в NGN. В контексте DiffServ определено место задачи оптимального управления трафиком с поддержкой QoS. В качестве средства решения задачи оптимального управления предложена имитационная дисциплина обслуживания. В первой главе сформулирована её концепция и проведено сравнение с обычными дисциплинами обслуживания.
Во второй главе проведена разработка имитационной дисциплины обслуживания. На самом деле разрабатывать пришлось не только её, но и всю окружающую систему модельной сети с мультисервисным трафиком. Система состоит из: модели источников мультисервисного трафика; подсистемы ведения очередей с контролем QoS и с возможностью управления; подсистемы оптимизации параметров управления; подсистемы времени, которая организует все подсистемы в единую модельную систему.
Подсистема оптимизации управления, в свою очередь, обращается к подсистеме прогнозирования, организованной на основе нейросетей, и подсистеме обучения нейросетей. Разработанная реализация ИДО содержит внутри себя две экстремальные задачи: оптимизации управления мультисервисным узлом; минимизации среднеквадратической ошибки прогноза на обучающем ансамбле эталонов.
В третьей главе проведён анализ механизмов нейросетевого прогнозирования и разработка нейросетевого предиктора входящего трафика.
Анализ временной структуры прогнозирования позволил разработать и обосновать архитектуру нейросетевого предиктора. В качестве типа нейросети выбран многослойный персептрон с одним скрытым слоем и с сигмоидальной функцией активации.
Разработана обобщенная оцифровка для нейросетей с сигмоидальной функцией активации нейрона. Обобщенная оцифровка вместе с логарифмическим преобразованием масштаба позволяют эффективно использовать динамический диапазон нейронов и не вносить погрешность дискретизации.
Разработана структура нейросетевого предиктора как для собственно прогноза, так и для моделирования будущего с учётом отброшенного и обслуженного трафика (условного прогноза).
Разработана процедура обучения нейросети на реальном прошлом трафика. Обучение производится по критерию минимума ошибки прогноза на эталонных примерах, взятых из предыстории.
Проведена адаптация метода обратного распространения и метода сопряжённых градиентов к разработанному нейросетевому предиктору. Показана вычислительная эффективность этих методов в тестовых примерах.
Для поиска глобального экстремума и исключения неудачных попыток оптимизации применён метод имитации отжига.
В четвёртой главе проведён численный эксперимент по реализации ИДО и сравнению СМО мультисервисного трафика. В качестве сравниваемых СМО выступали СМО со статической настройкой параметров (обыкновенная СМО) и СМО с оптимизацией параметров управления на основе моделирования будущего поведения сети (имитационная СМО).
Осуществлена настройка временных параметров оптимизации, обеспечивающая управляемость и устойчивость системы. Исследовано влияние точности прогноза на эффективность работы ИДО.
Доказано, что имитационная СМО мультисервисного трафика работает удовлетворительно и имеет преимущество перед СМО со статической настройкой параметров.
Сети следующего поколения и QOS
По смысловому содержанию МСЭ-Т подразделяет [100] параметры QoS на следующие группы:
Скорость доставки информации.
Шумы. Допустимый уровень потерь/искажений пакетов.
Задержка прохождения сигнала.
Джиттер - вариация задержки.
Скорость доставки информации соответствует доступной полосе частот. Соответствие зависит от способа кодирования информации: сколько бит приходится на бод. Эффективная скорость доставки информации несколько ниже, т.к. потери пакетов вынуждают применять избыточное кодирование и/или повторную передачу пакетов. Говоря о параметрах QoS, имеют в виду эффективную скорость. Скорость доставки информации, вообще говоря, переменна. Поэтому используют ряд параметров QoS, таких как: средняя скорость, пиковая скорость, максимальный размер пикового выброса.
Шумы проявляются в потерях пакетов. Искажения пакетов в конце концов приводят к их отбрасыванию и, следовательно, потере. Потери пакетов влияют на скорость доставки информации и, что важнее, на задержку. Если повторная передача потерянных пакетов недопустима, необходимо превентивно избыточное кодирование, что увеличивает требуемую скорость доставки информации. Если же информация изначально избыточна, потери пакетов могут быть не критичны. Используются такие параметры QoS, как допустимая доля потерянных пакетов или вероятность отбрасывания.
Задержка прохождения сигнала ограничивает снизу время отклика системы. В ряде приложений задержка настолько критичный параметр, что не позволяет использовать повторную передачу потерянных пакетов или сглаживать трафик, задерживая его в буфере.
Джиттер является статистической погрешностью задержки. Однако его выделяют в отдельный параметр QoS, т.к. в потоковых приложениях джиттер значительно заметнее задержки. Так, для вещательного трафика задержка вообще не имеет значения, но требования к джиттеру столь же жесткие, как в интерактивных приложениях.
Не все параметры QoS одинаково важны. Набор критичных параметров и требования к параметрам QoS для разных видов трафика сильно разнятся.
Разработка модели источников мультисервиснои нагрузки
Анализ нейросетевого прогнозирования
Источники мультисервисного трафика реализованы независимо по агрегатам-сервисам. В каждом агрегате поддерживаются массивы:
состояний источников;
накапливающегося трафика приостановленных источников;
входящего трафика источников;
исходящего трафика источников;
отброшенного трафика источников.
Кроме того, поддерживаются общие для агрегатов массивы:
входящего трафика;
исходящего трафика;
отброшенного трафика.
Трафик считается входящим/исходящим/отброшенным по отношению к мультисервисному узлу.
Состояние источника может быть неактивным, активным или приостановленным. Состояние приостановленного источника кодируется положительным числом, имеющим смысл значения таймера до восстановления. Источники статистически независимы. Источник меняет своё состояние спонтанно с некоторой вероятностью или вынужденно под воздействием отбрасывания его трафика сетью. Источник вынужденно переходит в приостановленное состояние, если на предыдущем временном шаге доля его отброшенного трафика по отношению к исходящему превысила порог, задаваемый параметром QoS_loss. По истечении таймера восстановления источник вынужденно переходит в активное состояние с вероятностью P_res и в неактивное с дополнительной вероятностью.
Входящий трафик генерируется только активными источниками. Если источник приостановлен, его отброшенный трафик накапливается и при восстановлении добавляется к входящему. Пиковый выброс трафика источником моделирует повторную передачу.
Данная модель похожа на ВМАР (Batch Markovian Arrival Process) [67, 63, 65, 64, 53]. Однако она отличается тем, что реализует обратную связь сети на источники. Данная модель более реалистично описывает приближение перегрузки в сети.
Интенсивность генерации пакетов активным источником задаётся произвольной функцией времени, чтобы смоделировать нестационарность входящего трафика. Применена следующая зависимость (рис. 2Л).
Временные параметры оптимизации
Модельная эволюция проводилась при различных временных параметрах. Опытным путём выбраны такие значения, при которых поведение динамической системы не искажено посторонними эффектами, о которых сказано ниже, и, в то же время, нетривиально. Также принимался во внимание объём вычислений, необходимых для моделирования эволюции.
В данной главе приведены результаты модельной эволюции при следующих значениях временных параметров.
Название параметра Обозначение параметра Значение
Длина предыстории
Длина обучения
Длина управления
Длина моделирования
Период оптимизации
Соображения, по которым введено три параметра (t_predict, t_sim, t4end) вместо одного, уже обсуждались выше.
При заданных значениях временных параметров поведение динамической системы удовлетворительно. При менее удачных настройках могли наблюдаться эффекты перерегулирования: последующее ухудшение оптимизируемой величины и возникновение автоколебаний. Или же оптимизации была мало заметной.
В описываемом численном эксперименте длина моделирования (t_sim=20) больше длины управления (t_predict=5). Это означает, что параметры управления только первых 5 шагов свободно варьировались. На последующих шагах они поддерживались равными последнему из варьируемых.
Эволюция с управлением и без управления
Эволюция до момента времени 1500 шагов производилась без оптимизации параметров управления, а с 1500 до 3000 - как без управления, так и с управлением. "Эволюция без управления" означает, что параметры управления поддерживаются постоянными. Начальный интервал [0, 1500] без управления необходим для исключения эффектов старта, чтобы процесс стал установившимся.
Моделирование эволюции проводилось для 1-го и для 2-х агрегатов. Ниже для каждого случая приводятся графики исходящего трафика (y_out), фактических (y_drop) и оцененных потерь (y_cost) в эволюции без управления и с управлением. Интервал, на котором эволюция может быть управляемой - [1500,3000].
На рис. 4.1 и 4.2 показана эволюция 1-го агрегата без и с оптимизацией управления. На рис. 4.3 и 4.4 - то же для 2-х агрегатов. Среднее значение целевой функции и средние фактические потери на [1500,3000] приведены в табл. 4.2.
