Содержание к диссертации
Введение
ГЛАВА 1. Методы и средства обеспечения качества обслуживания 13
1.1. Качество обслуживания 13
1.2. Функции качества обслуживания и инструменты его обеспечения 16
1.3. Анализ архитектур интегрированных и дифференцированных услуг (intservn diffserv) 17
1.4. Показатель качества 19
1.5. Предоставления сервиса провайдерами 20
1.6. Выводы 23
ГЛАВА 2. Анализ алгоритмов обслуживания очередей 25
2.1 Необходимость сравнения АОО 25
2.2. Общие принципы обслуживания очередей в сетях с поддержкой качества обслуживания 25
2.3. Алгоритмы обслуживания очередей 26
2.3.1. Алгоритм «Первый вошел - Первый вышел» (FIFO First In - First Out) 26
2.3.2. Алгоритм "Круговое обслуживание" 26
2.3.3. Алгоритм "Круговое обслуживание с дефицитом" 27
2.3.4. Алгоритмы обслуживания очередей с приоритетами 27
2.3.5. Модифицированный алгоритм PS 28
2.3.6. Алгоритм "Взвешенное Круговое обслуживание" 28
2.3.7. Алгоритм "Модифицированное круговое обслуживание с дефицитом" 29
2.3.8. Алгоритм GPS 30
2.3.9. Алгоритм Weighed Fair Queuing 34
2.3.10. Алгоритм WF2Q 36
2.3.11. Алгоритм WF2Q+ 39
2.3.12. Алгоритм Virtual Clock 41
2.3.13. Алгоритм Leap Forward Virtual Clock 41
2.3.14. Алгоритм SCFQ 42
2.4. Классификация AOO 43
2.5. Выводы 45
ГЛАВА 3. Анализ систем имитационного моделирования . 46
3.1. Выбор метода моделирование для анализа проектируемых вычислительных систем и сетей 46
3.2. Обзор имеющихся СИМ 47
3.2.1. Универсальная система Симула 67 48
3.2.2. GPSS 50
3.2.3. Система NetCracker 54
3.2.4. SimEvent 56
3.3. Возможности имитационного моделирования 56
3.4. Организация имитационного моделирования 59
3.5. Элементы архитектуры имитационной модели 64
3.6. Разработка требований к создаваемой СИМ 67
3.7. Выводы 68
ГЛАВА 4. Моделирование алгоритмов обслуживания очередей 69
4.1. Необходимость моделирования для выбора АОО 69
4.2. Принципы и положения моделирования АОО 69
4.3. Базовая структура модели обслуживания очередей 70
4.4. Методы синхронизации и учета задержек в модели АОО 71
4.5. Разработка обобщенной логической архитектуры модели АОО 72
4.6. Базовые блоки и элементы модели 73
4.7. Пример реализации модели АОО 73
4.7.1. Блок Вход/Выход 74
4.7.2. Блок "Шейпер" 76
4.7.3. Блок очередей 77
4.7.4. Блок управления 79
4.8. Базовый алгоритм моделирования и анализ результатов 81
4.9. Выводы 85
ГЛАВА 5. Методика применения разработанной сим для моделирования информационных сетей с поддержкой алгоритмов обслуживания и управления очередями 86
5.1. Инструментарий создания моделей 86
5.2. Основа построения моделей сетей 86
5.3. Архитектурные особенности моделей сетей 88
5.4. Настройка модели 88
5.5. Регистрируемые и вычисляемые параметры 89
5.6. Эксперимент с целью оценки показателей качества 90
5.7. Метод настройки и замены АОО в режиме реального времени 96
5.8. Выводы 97
Заключение 98
Список сокращений 100
Список литературы 101
- Анализ архитектур интегрированных и дифференцированных услуг (intservn diffserv)
- Алгоритм "Модифицированное круговое обслуживание с дефицитом"
- Возможности имитационного моделирования
- Базовая структура модели обслуживания очередей
Введение к работе
Сети связи следующего поколения.
До недавнего времени поставщикам услуг Internet (провайдерам) и крупным компаниям приходилось создавать и поддерживать отдельные сети для передачи голосовой информации, видеоизображения, трафика, необходимого для решения критически важных задач, и всего остального сетевого трафика. Тем не менее, нельзя не отметить сложившуюся в последнее время ярко выраженную тенденцию к объединению всех этих сетей в одну сеть с пакетной передачей данных. Начались радикальные изменения тех концептуальных положений, которые определяют основные направления дальнейшего развития телекоммуникационной системы. Сформировалась идея построения сети связи следующего поколения, известная под аббревиатурой NGN (Next Generation Network). Большинство специалистов считает идею NGN самой разумной концепцией дальнейшего развития инфокоммуникационной системы - симбиоза электросвязи и информатики.
Теоретически концепция NGN может быть реализована в процессе развития любой эксплуатируемой ныне сети электросвязи: телефонной, обмена данными, кабельного телевидения. Гипотетически можно рассматривать идею создания еще одной - новой - сети, полностью соответствующей концепции NGN. Однако с практической точки зрения интерес представляет только тот способ построения NGN, который основан на целенаправленном развитии телефонной сети общего пользования (ТФОП). Среди изменений в ТФОП необходимо выделить переход к пакетным технологиям передачи и коммутации, стимулирующим разработку новых принципов построения сети [33].
Одной из важнейших задач при создании NGN является разработка методов расчета характеристик, которые позволяют анализировать качество обслуживания трафика в NGN в целом, а также в ее отдельных фрагментах.
12 Поскольку количество пользователей Internet и различных сетевых приложений увеличивается с каждым днем, сеть нуждается в средствах, которые бы обеспечили поддержку как существующих, так и появляющихся приложений и служб. Тем не менее, на сегодняшний день Internet может обеспечить всего лишь негарантированную доставку данных (best effort service). Негарантированная доставка данных не предполагает предоставления каких-либо гарантий, касающихся времени и самого факта прибытия пакета в пункт назначения. При этом нельзя не отметить, что отбрасывание пакетов может произойти только в момент перегрузки сети.
Характеристики качества обслуживания трафика традиционно считаются одним из важнейших научных направлений в исследованиях сетей телефонной связи и обмена данными. Российская научная школа в этом направлении (теория телетрафика) - одна из сильнейших в мире. Существенный вклад в развитие теории телетрафика внесли Г.П. Башарин, Б.С. Лившиц, В.И Нейман, С.Н. Степанов, А.Д. Харкевич, М.А. Шнепс-Шнеппе, Г.Г. Яновский и другие известные ученые. Говоря о достижениях зарубежных специалистов, следует упомянуть имена В. Иверсена, Л. Клейнрока, П. Кюна.
Результаты, полученные отечественными и зарубежными специалистами, полезны для исследования характеристик качества обслуживания трафика в NGN. Вместе с тем, принципы функционирования всех устройств коммутации в NGN имеют специфику, которая обусловлена выбранной технологией распределения информации. По этой причине необходима разработка новых методов расчета ряда вероятностно-временных характеристик NGN, адекватно отражающих процессы обмена информацией между абонентами [33].
Анализ архитектур интегрированных и дифференцированных услуг (intservn diffserv)
В 1994-году проблемная группа проектирования Internet (Internet Engineering Task Force — IETF) сформировала рабочую группу по созданию интефированных услуг (intserv Working Group), главной задачей которой являлось расширение базовой модели услуг Internet с целью обеспечения улучшенной поддержки разнообразных приложений, ориентированных на передачу голосового трафика и трафика видеоизображении. Созданная рабочая группа должна была четко определить новую усовершенствованную модель услуг Internet, разработать средства, позволяющие приложениям выражать сквозные требования к ресурсам, и создать механизмы, которые бы обеспечили надлежащую интерпретацию этих требований маршрутизаторами и различными технологиями, использующимися в подсетях. Основная идея при этом заключалась в отдельной обработке потоков трафика, запросивших определенный уровень качества обслуживания.
С этой целью были разработаны две услуги — гарантированного обслуживания и регулируемой нагрузки. Гарантированное обслуживание (guaranteed service) предполагает предоставление детерминированных гарантий задержки, в то время как служба регулируемой нагрузки (controlled load service) использует механизм, похожий на механизм негарантированной доставки трафика в слегка загруженной сети.
В качестве сигнального протокола, использующегося для передачи требований сквозного обслуживания, был предложен протокол резервирования ресурсов (Resource Reservation Protocol — RS VP).
Следует отметить, что модель intserv требует обеспечения гарантированного качества обслуживания для каждого отдельного потока трафика в масштабах Internet. Учитывая тот факт, что на сегодня в каждый момент времени в Internet существуют тысячи потоков трафика, объем информации, который должны поддерживать маршрутизаторы, может быть запредельно большим. К сожалению, это означает наличие практически неизбежных проблем, связанных с масштабированием сети, поскольку объем информации, который следует поддерживать маршрутизаторам, увеличивается пропорционально росту числа потоков трафика.
Поэтому, в 1998 году организация IETF сформировала рабочую группу по созданию дифференцированных услуг (diffserv Working Group). Архитектурная модель diffserv является неким консенсусом между требованиями гарантированного качества обслуживания модели intserv и механизмом негарантированной доставки трафика, использующимся сегодня в Internet. Модель diffserv обеспечивает дифференцирование трафика путем его разбивки на классы с различным приоритетом.
В соответствии с моделью diffserv обеспечение качества обслуживания в сети предполагает наличие небольшого числа четко определенных "строительных" блоков, на основе которых можно создать множество различных услуг. Главной задачей подхода diffserv является определение стандартизированной метки дифференцированной услуги и ее соответствующая маркировка, от которой зависит принятие специфического решения о продвижении пакета данных на каждом переходе (per-hop behavior — РНВ), т.е. в каждом промежуточном узле.
Архитектура дифференцированных услуг обеспечивает базовую основу, которая может быть использована поставщиками услуг для предоставления своим клиентам большого диапазона различных предложений в зависимости от предъявляемых требований к качеству обслуживания. Клиент может выбрать требуемый уровень услуг. Если же объем передаваемого трафика превысит установленную квоту для данного уровня обслуживания, то предоставление оговоренных услуг для "сверхплановых" пакетов не гарантируется.
Отдельно следует отметить [14], что необходимо строго различать понятия «характеристики QoS услуги» и «показателя качества обслуживания (QoS)». Характеристика QoS выражает одну из особенностей ее качества, которую можно выделить явно и представить количественно. Последнее, согласно теории измерений, можно соотнести с определением идеального поведения, в связи с чем характеристика QoS может рассматриваться как одна из величин, отражающих фундаментальные аспекты QoS абстрактной модели услуги. Данная модель может быть выражена в виде формулы, схемы, условного описания с указанием скалярных или векторных характеристик, использующих такие количественные категории, как числа, функции, функционалы, операторы и т. д. Другое же, не менее важное понятие концепции QoS связано с качеством работы систем, ее элементов или служб. Оно определяется как «показатель качества обслуживания», который также имеет количественное выражение, но в отличие от характеристики отражает некий аспект качества объекта.
Таким образом, если характеристика QoS количественно отражает тот или иной аспект качества услуг, описываемого математическими моделями пользователя и объекта, то показатель QoS количественно выражает фактические возможности предоставления того же аспекта качества услуги и по этой причине может контролироваться и изменяться путем соответствующего управления.
Алгоритм "Модифицированное круговое обслуживание с дефицитом"
Modified Deficit Round Robin (далее - MDRR) [46] создан с целью повышения эффективности АОО DRR путем добавлением очереди с малой задержкой (low-latency queue) и задания квантового значения, равного величине пакета максимального размера, что гарантирует постоянное обслуживание, по меньшей мере, одного пакета из каждой очереди.
В соответствии с алгоритмом MDRR, все очереди, за исключением очереди с малой задержкой, обслуживаются по круговому принципу, а очередь с малой задержкой может обслуживаться в двух режимах: режиме строгого приоритета и режиме чередующегося приоритета.
В режиме строгого приоритета (strict priority mode) очередь с малой задержкой обслуживается при наличии в ней хотя бы одного пакета, что обуславливает минимально возможную задержку для обрабатывающегося с помощью этой очереди класса трафика. Однако следует отметить, что высокоприоритетная очередь с малой задержкой способна на продолжительный период времени занять сто процентов полосы пропускания канала и тем самым подавить остальные очереди.
В режиме чередующегося приоритета (alternate priority mode) очередь с малой задержкой обрабатывается в промежутках между обработкой остальных очередей. Если предположить, что в дополнение к очереди с малой задержкой, имеющей номер 0, существует еще семь очередей, то, в соответствии с режимом чередующегося приоритета, очереди будут обслужены в следующем порядке: 0, 1,0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7. Режим чередующегося приоритета позволяет снизить максимальную задержку обслуживания очереди 0 с суммы квантовых значений (что было бы в случае традиционного механизма кругового обслуживания) до максимального квантового значения всех оставшихся очередей.
Для справедливой приоритезации доступа планировщика к очередям маршрутизатора был разработан алгоритм GPS (Generalized Processor sharing) [98, 99], являющийся модификацией рассмотренного ранее алгоритма PS. GPS относится к классу планировщиков, "работающих непрерывно" и является идеальной моделью, обеспечивающей в непрерывном времени принцип "справедливого распределения ресурсов" в соответствии с критерием max-min для классов трафика с различными требованиями по качеству обслуживания.
Предположим, что N потоков проходят через некоторый CQS-маршрутизатор (Классификация - Classify, Буферизация - Queue, Обслуживание - Schedule) [21] и разделяют его ресурсы, причем планировщик реализован на базе алгоритма GPS. Пусть для каждого потока ie[l,N] выделяется минимальная пропускная способность rh т.е. должно выполняться следующее неравенство:
где г - пропускная способность исходящего канала. Пусть также количество потоков равно количеству очередей в рассматриваемом маршрутизаторе. Обозначим через B(t) набор активных, но не обслуживаемых в момент времени / потоков (backlogged flow, далее - "бэклог"-поток). Для каждой очереди (потока) при функционировании GPS в некоторый момент времени / должен быть зарезервирован относительный квант процессорного времени gi(t), другими словами, полоса пропускания или скорость дая обслуживания нагрузки из данной очереди в соответствии со следующим равенством: где X «=«(,) 0"" сУмма скоростей обслуживания активных, но не обслуживаемых в момент t потоков (под активным подразумеваем поток, если в момент времени t в очереди находится хотя бы один принадлежащий ему пакет). Для реализации принципа "справедливой буферизации на уровне пакетов" алгоритм GPS дополнительно предполагает вычисление значения параметра "время окончания обслуживания" (finished tag) для каждого поступающего в маршрутизатор пакета. Каждый раз, когда заканчивается обслуживание некоторого пакета, планировщик передает на обслуживание следующий пакет с наименьшим значением параметра "время окончания обслуживания" из некоторой очереди, т.е., другими словами, на обслуживание передается тот пакет, который должен быть обслужен быстрее. Отметим, что анализируются только те пакеты, которые стоят первыми на обслуживание в каждой из очередей, называемые HOL-пакетами (Head-Of-Line).
Возможности имитационного моделирования
Аналитическими методами может быть исследован сравнительно узкий круг задач массового обслуживания. С другой стороны, уникальность и дороговизна многих реальных систем, а также ответственность решаемых ими задач мешают проведению натурных экспериментов — особенно в критических режимах [28].
Имитационное моделирование [6, 17, 18, 22, 23 26, 29, 30] в принципе позволяет воспроизводить любой марковский процесс в целях анализа, оптимизации или обучения персонала системы. Естественными требованиями к модели являются:
полнота (получаются все необходимые характеристики, причем с требуемой точностью и достоверностью);
гибкость (допустимо варьирование структуры и параметров);
минимальная длительность разработки;
блочная структура;
эффективность воспроизведения на ЭВМ.
Реализации процесса работы системы массового обслуживания (СМО) моделируются на компьютере с помощью серий случайных или псевдослучайных величин. Управление работой модели строится в за 57 висимости от цели исследования и может быть организовано по текущему значению счетчика, связанного с этой целью. В более сложных моделях останов может определяться некоторой комбинацией условий, а также достижением требуемой точности. Усреднение результатов моделирования по времени функционирования модели или числу реализаций процесса позволяет методами математической статистики получить искомые характеристики. Эту обработку также следует проводить на компьютере.
Благодаря возможности достаточно полного отражения реальности (например, многокаскадного обслуживания, неоднородных потоков и каналов, блокировок из-за ограниченной емкости буферов, сложной системы приоритетов и дисциплин обслуживания и т. п.) имитационное моделирование удобно для исследования практических задач: определения показателей эффективности, сравнения вариантов построения и алгоритмов функционирования системы, проверки устойчивости режимов системы при малых отклонениях входных переменных от расчетных значений и др. Полнота имитации может быть проверена построением серии последовательно уточняемых моделей. Если дальнейшая детализация практически не влияет на интересующие показатели, расчеты можно прекратить и принять в качестве выходных последние полученные результаты.
В любом случае моделируются все те и только те стороны процесса, которые влияют на выбранный показатель эффективности или критичны к наложенным ограничениям. В частности, заявка может характеризоваться не только временем ее обслуживания, но. и своим объемом (весом), видом обслуживания, необходимыми затратами ресурсов и т. п.
Между длительностью моделируемого процесса и длительностью имитации нет прямой связи. Длительность имитации определяется уровнем детальности и соотношением характерных времен. К примеру, моделирование работы пользователя вычислительной системы коллективного доступа, выдающего запросы с 15-минутными интервалами, трудно сочетается с моделированием регистров процессора ЭВМ, работающего в наносекундном диапазоне.
Промежуточные результаты имитационного моделирования, в отличие от результатов аналитического счета, имеют четкий физический смысл. Это облегчает обнаружение ошибок в программе - в особенности при работе в интерактивном режиме.
Метод имитационного моделирования свободен от каких-либо ограничений на класс решаемых задач, нагляден, прост в освоении, обладает повышенной устойчивостью к сбоям ЭВМ, все промежуточные результаты легко интерпретируются и контролируются.
Недостатками имитационного моделирования являются:
большой расход машинного времени;
малая точность вероятностных характеристик редких событий;
трудность получения обобщающих выводов и рекомендаций;
сложность оптимизации системы (поиск оптимума требует многовариантных расчетов и ведется при наличии вероятностных помех — случайных ошибок в результатах);
вероятностная оценка погрешностей, хотя для вероятностных задач такая оценка вполне нормальна.
Перечисленные недостатки имитационного моделирования несколько смягчаются постоянным ростом технических характеристик (быстродействия и объема памяти) современных ЭВМ и использованием методов понижения дисперсии.
По указанным причинам применение имитационного моделирования (особенно в квалификационных работах) нужно сводить к разумному минимуму. Такое применение представляется целесообразным:
для накопления первичных данных об изучаемом явлении, если эти данные нельзя получить в натурном эксперименте;
для проверки правомерности допущений, сделанных разработчиком в целях перехода к аналитическим методам; для демонстрации конечных результатов исследования на достаточно полной модели реальной ситуации;
при "безысходности", когда сложность ситуации намного превосходит возможности аналитических методов, известных разработчику.
Для дальнейшего построения СИМ необходимо понять и проанализировать все фазы имитационного моделирования.
В типичном случае процесс моделирования проходит следующие фазы [43]:
Определение системы.
Формализация описания.
Подготовка данных.
Трансляция модели.
Оценка адекватности.
Планирование эксперимента.
Планирование прогонов.
Машинный эксперимент.
Анализ результатов.
Интерпретация.
Реализация.
Документирование.
Базовая структура модели обслуживания очередей
В общем виде имитационная модель обслуживания очередей любым из рассмотренных алгоритмов включает в себя источник последовательности пакетов, блок, реализующий АОО, и приемник последовательности пакетов (Рис. 4.1.).
ерез АОО. Источник последовательности пакетов служит для формирования тестовой последовательности пакетов, это может происходить произвольным образом (randomize) - при имитации произвольного трафика в сети - или строго определенным образом - при моделировании конкретного АОО. В ряде случаев источник последовательности пакетов может содержать одновременно несколько тестовых последовательностей, каждая из которых определяется своими значениями параметров пакетов.
Рассматриваемые далее модели оперируют пакетами, состоящими из четырех полей: 1 - номер пакета в потоке (последовательности), 2 - номер потока (последовательности), 3 - приоритет пакета, 4 - длина пакета в единицах (Рис. 4.2.).
Как известно, ни одна реально существующая электронная схема не может работать без задержек, вызванных переходными процессами в ее элементах. Эта «неидеальность» элементов являются залогомработоспособности схемы. В системе MATLAB/Simulink все элементы «идеальны», т.е. переключение из одного состояние в другое происходит без задержки. Это приводит к тому, что при реализации моделей нужно учитывать необходимые задержки, вводя в схему соответствующие элементы - элементы задержек (Unit Delay). При этом, вводя элемент задержки, например, в линию связи между двумя последовательными элементами, следует помнить о периодах и длительностях других сигналов (например "PUSH" или "POP"), а также учитывать сдвиг их фронтов, который может привести к рассинхронизации данных. Для устранения этого эффекта следует вводить блоки компенсации задержек, число которых определяется количеством ранее введенных дополнительных элементов задержек.
4.5. Разработка обобщенной логической архитектуры модели АОО. В общем случае модель АОО, включает в себя [38] (Рис. 4.3.): - Блок "Шейпер", служащий для разделения по определенному признаку (per-flow, per-class) входного трафика на несколько потоков; - блок очередей, состоящий из заданного числа очередей, соответствующих разным потокам трафика;
- блок управления, реализующий логику работы конкретного АОО.
Data IN
- Data OUT
"PUSH"
В соответствии с данным рисунком (Рис 4.3.), по сигналу "PUSH" трафик, представляющий собой входную тестовую последовательность, состоящую из пакетов разных потоков, поступает на вход блока шейпер, в настройках которого заранее указываются значения параметров (полей) пакетов, определяющих разделение тестовой последовательности на потоки. На основании этих настроек блок шейпер формирует сигнал для блока очередей, уведомляя его о том, в какую конкретно очередь надо ввести обрабатываемый в данный момент пакет, и производит передачу данных. Получив пакет от блока шейпер, блок очередей заносит его в соответствующую очередь, при условии, что очередь не полна. В противном случае происходит отбрасывание пакета (алгоритм управления очередью "Отбрасывание хвоста" - Tail drop). Очереди блока очередей реализованы на элементах FIFO. Глубина каждой очереди, а также другие значения свойств элемента FIFO задаются заранее.
Выходная последовательность формируется в приемнике последовательности пакетов под действием сигнала "POP" блока управления, реализующего соответствующий АОО и формирующего последовательность выхода пакетов из блока очередей. С этой целью блок управления анализирует состояние частей системы, реагирует на изменения и следит за процессами в системе по цепи обратной связи, например, определяя освобождение очередей, меняя соответствующим образом порядок обработки (выхода) пакетов и т.д.
