автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка модели и инструментальных средств проектирования и исследования информационных сетей

На правах рукописи

ФИШМАН ЕВГЕНИЙ БОРИСОВИЧ

РАЗРАБОТКА МОДЕЛИ И ИНСТРУМЕНТАЛЬНЫХ СРЕДСТВ ПРОЕКТИРОВАНИЯ И ИССЛЕДОВАНИЯ ИНФОРМАЦИОННЫХ СЕТЕЙ

Специальность 05.13.13 — Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва-2007

003057850

Работа выполнена на кафедре Электронно - вычислительной аппаратуры Московского государственного института электроники и математики (технического университета)

Научный руководитель доктор технических наук, профессор

Азаров Владимир Николаевич

Научный консультант. кандидат технических наук

Иванов Александр Борисович

Официальные оппоненты, доктор технических наук, профессор

Капитанов Валерий Тимофеевич

кандидат технических наук, доцент Авдошин Сергей Михайлович

Ведущая организация ФГУП НИИ Автоматической Аппаратуры

им. академика B.C. Семенихина

Защита состоится « 22 » мая 2007 г в 10 00 часов на заседании диссертационного совета Д 212 133.03 при Московском государственном институте электроники и математики по адресу 109028, г Москва, Б Трехсвятительский пер , д 1-3/12 стр 8

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики

Автореферат разослан « » апреля 2007 г

Ученый секретарь диссертационного совета к.т.11, доцент

ЮЛ Леохин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы. Одной из задач современного этапа развития инфокоммуникаций является переход к сетям следующего поколения (NGN -Next Generation Networks), позволяющим наиболее эффективно обеспечивать необходимый уровень качества обслуживания в сетях (QoS) Выполнение этой задачи невозможно без использования все более эффективных алгоритмов обслуживания (АОО) и управления (АУО) очередями, являющихся основой для предоставления гарантированного качества услуг связи Это, естественно, требует проведения предварительного моделирования сетей связи с целью создания наиболее адекватной системы, способной соответствовать заданным и подразумеваемым требованиям В настоящее время существует достаточно много систем моделирования, большинство из которых основаны на использовании библиотек оборудования известных производителей, что не позволяет выполнить имитационное моделирование новых АОО и АУО и, как следствие, провести оценку их эффективности В связи с этим разработка системы моделирования, использующей теоретические модели, является чрезвычайно актуальной

Цель работы. Целью настоящей работы является разработка модели и инструментальных средств проектирования (системы имитациошюго моделирования - СИМ) и исследования информационных сетей, не привязанных к конкретному оборудованию, а основанных на математических моделях шаблонов настраиваемых (конфигурируемых) элементов сетей

Для достижения этой цели поставлены и решены следующие задачи:

1. Анализ путей обеспечения гарантированного качества обслуживания в сетях инфокоммуникаций

2 Анализ существующих архитектур и методов обеспечения качества обслуживания в сетях инфокоммуникаций

3. Классификация существующих АОО по основным характеристикам и вычислительной сложности

4 Анализ общих пршщипов построения и архитектурных особенностей имитационных моделей

5 Анализ существующих СИМ, выявление их недостатков и разработка требований к СИМ, использующей шаблоны настраиваемых элементов сетей инфокоммуникаций

6 Разработка обобщенного метода построения модели АОО и базового алгоритма моделирования сетей с поддержкой качества обслуживания в MATLAB/ Simulink

7 Создание программного и информационного обеспечения СИМ в виде библиотеки элементов среды MATLAB/ Simulink

8 Разработка удобного и интуитивно понятного интерфейса для пользователя с возможностью быстрой и тонкой настройки необходимых значений, а также адекватной визуализацией и наглядным представлением результатов

9 Разработка методики оценки показателей «качества обслуживания» в сети инфокоммуникаций с применением созданной СИМ

10 Проведение имитационного моделирования с использованием созданной СИМ и подтверждение ее адекватности реальным системам.

11 Разработка методики настройки АОО и выбора АОО с целью улучшения показателей «качества обслуживания» в режиме реального времени

Методы исследований. При решении поставленных задач использовались принципы построения имитационных моделей систем и сетей массового обслуживания (СМО и СеМО), теория телетрафика, теория планирования эксперимента, а также теория массового обслуживания (ТМО).

Для исследования АОО и АУО использовался MATLAB/Sunulmk 7.0 компании Math Works Inc. я проводилось компьютерное моделирование с применением специально разработанной библиотеки шаблонов. Основные теоретические положения подтверждены результатами экспериментальных исследований

Научная новизна результатов работы:

1 Предложена классификация АОО по основным характеристикам и вычислительной сложности

2 Разработаны и исследованы методы создания шаблонов настраиваемых (конфигурируемых) сетевых элементов с целью имитационного моделирования АОО и АУО в MATLAB/ Simulink.

3 Предложена обобщенная архитектура модели АОО

4. Разработан базовый алгоритм моделирования сетей с АОО с использованием данных шаблонов в MATLAB/ Simulink.

5. Разработаны и исследованы структурные методы синхронизации и учета задержек модели

Практическую значимость имеют.

1. Созданная СИМ на базе разработанной библиотеки шаблонов, состоящей из различных АОО и АУО, позволяющая проводить имитационное моделирование сетей передачи данных с поддержкой качества обслуживания

2. Базовый алгоритм моделирования сетей с АОО с использованием созданной СИМ

3. Методика выбора наиболее оптимального АОО для текущей ситуации в режиме реального времени.

4. Разработанная структура имитационных моделей и схемы их функциональных узлов.

Внедрение. Созданная СИМ использована при проектировании модуля оценки качества передачи данных для Автоматизированного многофункционального интегрированного комплекса объектного мониторинга

(АМФИКОМ) сетей инфокоммуникаций компании «Сайрус Системе Корпорейшн», а также в учебном процессе кафедры Электронно — вычислительной аппаратуры Московского государственного института электроники и математики (технического университета).

Апробация работы. Основные положения диссертации докладывались и обсуждались на ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2005-2007 гг.), 13-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов МИЭТ (Москва, Зеленоград, 2006 г), в Трудах международного симпозиума «Надежность и качество» (Пенза, 2006 г.).

На защиту выносятся следующие основные положения:

1. Предложенный обобщенный метод построения модели АОО и базовый алгоритм моделирования сетей с поддержкой качества обслуживания в MATLAB/ Simulink.

2 Разработанное программное и информационное обеспечение системы имитационного моделирования (СИМ) в виде библиотеки элементов среды MATLAB/ Simulink

3. Разработанная методика оценки показателей качества обслуживания в сети с применением созданной СИМ

4 Разработанная методика настройки АОО и выбора АОО с целью улучшения показателей качества обслуживания в режиме реального времени

5. Результаты имитациошюго моделирования сетей телекоммуникаций с использованием разработанной СИМ

Структура работы. Общий объем диссертации составляет 111 стр машинописного текста, включая список литературы, и содержит 32 иллюстрации и 3 таблицы Работа состоит из введения, пяти глав, заключения (выводов), списка сокращений и списка литературы, включающего 47 отечественных и 67 зарубежных изданий

Публикации. Основные положения, выводы и практические результаты изложены в 7-и печатных работах, в том числе в 2-х статьях (1 — в изданиях, рекомендованных ВАК), а также в 5-и тезисах докладов (включая 1 — международные, 1- всероссийские)

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована необходимость и значимость выполненной научной работы, охарактеризовано состояние проблемы в области создания сетей следующего поколения (NGN) и использования для этого технологий качества обслуживания (QoS), обозначена актуальность работ, связанных с созданием и применением СИМ для построения и исследования NGN

В первой главе рассматриваются задачи и функции качества обслуживания, методы его обеспечения и способы применения на практике Характеристиками производительности сетевого соединения являются:

1) полоса пропускания (bandwidth), 2) задержка и ее дрожание (j ítter) при передаче пакетов, 3) потеря пакетов (packet loss)

Способность сети обеспечивать различные уровни обслуживания, запрашиваемые теми или иными сетевыми приложениями, наряду с проведением контроля за характеристиками производительности, может быть классифицирована по трем перечисленным ниже категориям: ^Негарантированная доставка данных (best-effort service),

2)Дифференцированное обслуживание (differentiated service),

3)Гарантированное обслуживание (guaranteed service)

Исходя из вышеизложенного, в рамках данной работы будем придерживаться мнения, что QoS является набором алгоритмов, методов и требований, предъявляемых к ресурсам сети при транспортировке потока данных QoS обеспечивает сквозную гарантию передачи данных и основанный на системе правил контроль за средствами повышения производительности сети, такими, как механизм распределения ресурсов, коммутация, маршрутизация, механизмы обслуживания очередей и механизмы отбрасывания пакетов

Можно перечислить следующие функции качества обслуживания в сетях: 1) Классификация и маркировка пакетов, 2) Управление интенсивностью трафика, 3) Распределение ресурсов; 4) Предотвращение перегрузки и политика отбрасывания пакетов

Существует множество механизмов, позволяющих обеспечить данные функции

1) Trafile shaping (формирование трафика) — используя алгоритм "leaky bucket"' (дырявое ведро), молено разделить трафик на различные выходные очереди для обеспечения предсказуемого поведения в дальнейшем Это может быть сделано на сетевом уровне (IP) или на канальном уровне АТМ

2) Admission control (контроль доступа) - физическое ограничение скорости передачи или использование алгоритма "token bucket" (ведро с маркерами) для уменьшения входного трафика Алгоритм "token bucket" может применяться как сам, так и в сочетании с другими алгоритмами, например, как часть íntegrated services architecture

3) Queumg - алгоритмы и механизмы обслуживания очередей

4) DifFerential congestión management (управление заторами) - алгоритмы, обеспечивающие разнообразные механизмы обработки трафика в случае заторов в сети

Существуют две архитектуры предоставления услуг — архитектура интегрированных услуг (mtserv) и архитектура дифференцированных услуг (diffserv). Первая, основанная на принципах резервирования ресурсов, вследствие сложностей технической реализации, уступила место второй, которая основана на принципе разделения трафика на классы и дальнейшем управлении ими

Важную роль в этом процессе играют АОО (см Гл 2), АУО (Tail Drop ("отбрасывание хвоста"), Random Early Detection (RED), Flow WRED, Slow Start - Global Synchronization, ECN, SPD и др ), алгоритмы формирования трафика и контроля доступа В контексте сетевых технологий понятие «обслуживание очередей» есть процесс разделения пакетов на разные потоки и дальнейшее управление ими

На первый взгляд, выбор АОО кажется простым Однако не следует торопиться, так как выбор АОО является определяющим в возможности обеспечения необходимого уровня сервиса и его качества Данный процесс также осложнен тем, что трафик сети разнообразен и имеет сложное распределение по времени

Во второй главе проведен подробный анализ 14-и алгоритмов обслуживания очередей Предложена классификация АОО (Рис 2 1.) на основе основных характеристик и вычислительной сложности

ТипАОО

Рис 2 1 Классификация АОО 7

Алгоритм «Первый вошел — Первый вышел» (FIFO First In — First Out) Когда пропускной способности сети априори достаточно для передаваемого трафика, то алгоритмы обслуживания очередей должны исключать "сброс" пакетов при случайных всплесках трафика. В этих случаях наиболее эффективно применение широко известного алгоритма FIFO с очередью, играющей роль буфера Алгоритм FIFO является самым быстрым из всех АОО

Алгоритм "Круговое обслуживание" Round Robin (далее — RR) является самым простым алгоритмом разделения процессорного времени (Process Sharing - PS), как с точки зрения реализации, так и с точки зрения функционирования Основополагающей идеей этого алгоритма является обеспечение одинакового доступа каждой из очередей к ресурсам системы, т е каждый раз, когда система освобождается, планировщик циклически выбирает очередь, из которой принимается пакет на обслуживание.

Алгоритм "Круговое обслуживание с дефицитом". Deficit Round Robin (далее — DRR) является модификацией алгоритма RR для пакетов переменной длины Благодаря тому, что в DRR добавлена функция накопления квантов выделяемого процессорного времени, в случаях, когда некоторой очереди выделено определенное количество процессорного времени для обработки находящегося в ней пакета, но пакет слишком длинный и требует большего кванта процессорного времени, данный пакет не передается на обслуживание При обращении планировщика к этой очереди в следующий раз, квант выделяемого времени суммируется с неиспользованным временем, что позволяет обслужить этот пакет Такое решение позволяет обслуживать пакеты любой длины в соответствии с принципом "справедливого распределения ресурсов"

Алгоритмы обслуживания очередей с приоритетами При организации передачи пакетов, различающихся длиной и приоритетом обслуживания, реализация принципа "справедливого распределения ресурсов" существенно осложняется В связи с этим при обслуживании пакетов различной длины, принадлежащих различным классам качества обслуживания, принцип "справедливого распределения ресурсов" трансформируется в принцип "справедливой буферизации на уровне пакетов" (packet-by-packet fair queuing, далее — PFQ). Последний заключается в том, что каждый пакет, независимо от длины, должен быть передан на обслуживание в соответствии с требованиями по качеству обслуживания того класса, к которому данный пакет принадлежит Для обеспечения гарантий по задержкам в данном случае может быть использован планировщик с приоритетами

Модифицированный алгоритм PS Priority Processor sharing или Priority Queumg (далее PPS или PQ), смысл которого заключается в том, что каждой из очередей присваивается приоритет, т.е планировщик выделяет процессорное время для обслуживания нагрузки из некоторой очереди в соответствии с назначенным ей приоритетом.

Алгоритм "Взвешенное Круговое обслуживание" Weighed Round Robin (далее WRR) является модификацией алгоритма RR, в которой обеспечивается

возможность задания разного веса (приоритета) каждой из очередей

Алгоритм "Модифицированное круговое обслуживание с дефицитом". Modified Deficit Round Robin (далее - MDRR) создан с целью повышения эффективности АОО DRR путем добавления очереди с малой задержкой (low-latency queue) и задания квантового значения, равного величине пакета максимального размера, что гарантирует постоянное обслуживание, по меньшей мере, одного пакета из каждой очереди

Алгоритм GPS Для справедливой приоритезации доступа планировщика к очередям маршрутизатора был разработан алгоритм GPS (Generalized Processor sharing), являющийся модификацией рассмотрештого ранее алгоритма PS GPS относится к классу планировщиков, "работающих непрерывно", и является идеальной моделью, обеспечивающей в непрерывном времени принцип "справедливого распределения ресурсов" в соответствии с критерием max-min для классов трафика с различными требованиями по качеству обслуживания

Предположим, что N потоков проходят через маршрутизатор и разделяют его ресурсы, причем планировщик реализован на базе алгоритма GPS Пусть для каждого потока i е [1, N] выделяется минимальная пропускная способность г„ т е

N

должно выполняться следующее неравенство

i=I

где г — пропускная способпость исходящего канала Пусть также количество потоков равно количеству очередей в рассматриваемом маршрутизаторе Обозначим через B(t) набор активных, но не обслуживаемых в момент времени t потоков (backlogged flow, далее — "бэклог"-поток) Для каждой очереди (потока) при функционировании GPS в некоторый момент времени t должен быть зарезервирован относительный квант процессорного времени g,(t), другими словами, полоса пропускания или скорость для обслуживания нагрузки из данной очереди в соответствии со следующим равенством

g,(t) = r ^- (2 1), где сУмма скоростей обслуживания активных,

но не обслуживаемых в момент t потоков (под активным подразумеваем такой поток, если в момент времени t в очереди находится хотя бы один принадлежащий ему пакет)

Для реализации принципа "справедливой буферизации на уровне пакетов" алгоритм GPS дополнительно предполагает вычисление значения параметра "время окончания обслуживания" (finished tag) для каждого поступающего в маршрутизатор пакета Каждый раз, когда заканчивается обслуживание некоторого пакета, планировщик передает на обслуживание следующий пакет с наименьшим значением параметра "время окончания обслуживания" из некоторой очереди Отметим, что анализируются только HOL-пакеты (Head-Of-Lrne).

Далее рассмотрим принципы распределения процессорного времени на базе алгоритма GPS Обозначим через Д(г,г) количество информации потока 1, поступившей за интервал времени }r,t], через И7, (г, г) — количество

обслуживаний, полученное потоком i (количество обслуженных бит потока i) за тот же промежуток времени и через Q£t) — количество трафика потока 1, находящегося в очереди в момент времени t Таким образом, можно записать

Отметим, что как только в некоторый момент времени система переходит в состояние простоя, те отсутствует нагрузка (idle), все вышеописанные параметры должны быть обнулены Введем ряд определений

- "событие" — поступление или уход на обслуживание потока в рамках моделируемого алгоритма GPS (далее будем называть его сервером GPS) Обозначим через t, момент времеш, когда происходит событие j,

- "период занятости системы" - период времени, в течение которого сервер GPS находится в состоянии обработки нагрузки,

- "бэклог-период" для некоторого потока i - непрерывный промежуток времени, когда пакеты данного потока буферизируются, но не передаются на обслуживание, т е рассматриваемый поток является "бэклог"- потоком,

- "период занятости некоторого потока i" — промежуток времени такой максимальной длины ]г,,г2], что для любого значения t е]г,,г,] пакеты потока i поступают со скоростью равной или выше, чем значение г,, т е Д (г, i) > г, (t - г,).

Рассмотрим на примере, каким образом вычисляется значение параметра "время окончания обслуживания" Для этого предположим, что существует маршрутизатор, через который проходит п потоков, причем каждому потоку отводится индивидуальная очередь Рассмотрим наиболее точную аппроксимацию планировщика, реализованного на базе алгоритма GPS, - за каждый цикл планировщик предоставляет возможность передать один бит на обслуживание каждой го п очередей Таким образом, длина цикла планировщика является переменной и зависит от количества активных очередей nactlve(t) Активной будем называть ту очередь, в которой, на момент обращения планировщика, присутствует хотя бы один бит, ожидающий обслуживания.

Далее предположим, что время непрерывно, причем функционирование системы начинается в момент времени t = 0 Обозначим через V(t) количество циклов, пройденных планировщиком к моменту времени t, это значение можно выразить как отношение пропускной способности канала г (те скорости

обслуживания) к количеству активных очередей: = —~—

Таким образом, функция V(t) является кусочно-непрерывной и изменяет наклон при изменении количества активных очередей Пусть в момент времени aUk в пустую очередь поступает k-й пакет потока i длиной Ь1]ч Если учесть тот факт, что в каждый момент времени планировщик забирает на обслуживание из очереди всего одош бит, то станет очевидно, что обслуживание этого пакета займет Llk циклов А значит, время завершения обслуживания пакета будет равно Р1л = у(а1л)+£>л.

Значение F,^ и есть значение параметра "время окончания обслуживания". Однако если пакет поступает в непустую очередь, в которой находится один

пакет, то при вычислении необходимо учитывать и время обслуживания этого пакета В результате- F:k =

Объединяя два последних выражения, принцип "справедливой буферизации" можно выразить таким образом Flt =max{Flk,V(alk)} + Llk.

Алгоритм Weighed Fair Queuing (WFQ) Алгоритм планировщика WFQ определяется в соответствии с принципами алгоритма GPS и реализует принцип "справедливой буферизации на уровне пакетов" PFQ Обозначим через d™" время окончания обслуживания пакета р, другими словами, время, когда центральный процессор передает пакет р в исходящий канал Аппроксимирующий GPS алгоритм должен обслуживать пакеты в соответствии со значением параметра dcp''s, придерживаясь стратегии, что пакет с меньшим значением этого параметра должен быть обслужен раньше, чем пакет с большим значением Однако на практике такую стратегию поведения планировщика реализовать достаточно сложно — это возможно только в том случае, если алгоритм планировщика относится к классу "работающих с паузами"

Алгоритм планировщика WFQ для реализации функции, подобной функции вычисления "виртуального времени окончания обслуживания", реализованной в GPS, использует подход вычисления значения функции "виртуальное время" (virtual time, далее эту функцию будем называть "виртуальное время GPS"), которая будет сейчас рассмотрена

Обозначим время поступления первого пакета через ^ = 0 Очевидно, что для j = 2, 3, количество потоков, находящихся в "периоде занятости" в интервал времени ]t,.i,t,[, фиксировано Обозначим это количество через переменную В,. Значение функции "виртуальное время GPS" V(t) для любого момента времени, когда центральный процессор простаивает, те отсутствует нагрузка, равно нулю Далее рассмотрим некоторый период занятости, начинающийся в момент времени t = 0 Начальное значение функции "виртуальное время GPS" в этог момент равно 0, а далее вычисляется в соответствии со следующей формулой

F(0) = 0,V(tH + г) = ) + y1-j ДЛЯ г <-t„,j = 2,3, (2 2)

Скорость изменения значения параметра V, те dV(tj +г)!dt , вычисляется как отношение l/]Tie/( rt Тогда, учитывая (21) для каждого "бэклог"-потока 1, можно

записать г dV(tt + т) / dг = g, (tj + т),

Следовательно, параметр V можно интерпретировать как скорость, с которой обслуживаются "бэклог"-потоки

Далее пусть k-й пакет потока i поступает в систему (в одну из очередей из классификатора - шейпера) в момент времени акк и имеет длину L, k Усложним задачу и введем две новые функции функцию "виртуальное время поступления" (virtual start time или start potential) пакета в очередь S,^ и функцию окончания обслуживания "виртуальное время окончания обслуживания" (virtual finish time

или finish potential) F, k. Положив F1>0 = 0 для всех i, получим следующие

отношения Slt = ma=Sa +^(2 3)

ri

Отметим, что ввод У(аЦк) в данное выражение необходим для сброса значения S,^ после того, как очередь i стала активной, т е в пустую очередь стала поступать нагрузка. За счет этого достигается достаточно точная аппроксимация GPS с точки зрения вычисления времени начала обслуживания пакета, поступившего в пустую (неактивную) очередь

Также в работе рассмотрены алгоритмы WF2Q и WF2Q+. Алгоритм Virtual Clock В алгоритме Virtual Clock (VC) для расчета значения функции виртуального времени используется реальное время:К|/с(г) = ?,^ля t>0. Тогда, k-му пакету потока i назначается временная метка F^, ранее называемая «время окончания обслуживания»

Fn =max{Fa ,,Vvc0,4)} +— =-■ max{f;t ,,au}+— где alk - время поступления k-го r, rt

пакета потока г Стоит заметить, что данный АОО не обеспечивает принцип «справедливого распределения ресурсов»

Алгоритм Leap Forward Virtual Clock (LFVC) В его основу положен принцип «воспитания детей», заключающийся в том, что если ребенок плохо себя ведет, то его надо на время наказать В данном контексте это означает, что поток трафика, получающий больше полосы пропускания, чем ему положено (такой поток называется oversubscribed), на время отстраняется от обслуживания Создавая высокоприоритетную (Н) и низкоприоритетную (L) очереди, при становлении потока oversubscribed, он помещается на время в L-очередь Обычные потоки (не отстраненные потоки) при этом заносятся в очередь Н и обслуживаются согласно наименьшему значению временных меток потоков. Отметим, что наименьшее значение временной метки потока на момент обслуживания может быть у потока из L, однако обслужен будет поток с наименьшей меткой из Н, откуда следует, что данный АОО не обслуживает пакеты согласно увеличешпо временных меток

Пусть ts - значение текущего виртуального времени, f - поток, pf - пакет потока f, В - пропускная способность исходящего канала, rf - полоса пропускания для потока f (часть В), tf — текущее значение временной метки для потока f (значение метки для HOL-пакета), Af - время обслуживания пакета

^тах

максимальной длины потока f, т е. А, = ——

г/

Тогда поток может содержаться в L до тех пор, пока соблюдается следующее неравенство, которое обеспечивает необходимую границу задержки АОО tf -ts > Af, (2 5) т е необходимо перебросить поток из L в Н до того, как нарушится неравенство

Так как алгоритм LFVC относится к «работающим непрерывно» (т е без пауз), при нахождении всех потоков в L значение виртуального времени системы увеличивается до максимального значения, не нарушая неравенства

(2 5) для любого находящихся в L потока, что и определяет название данного АОО

При использовании методов «приближенной сортировки» и приоритетных очередей вычислительная сложность рассмотренного АОО равна 0(log logN)

Алгоритм Self-clocked Fair Queuing (SCFQ) Данный АОО отличается от VC способом расчета значения «временной метки» В данном алгоритме предлагается обновлять значение «виртуальное время SCFQ» только после полного ухода пакета, обслуживаемого в данный момент Причем значение времени SCFQ равно значению «временной метки» только что ушедшего пакета V™ (t)=F;J, если пакет 1, принадлежащий потоку j, уходит в момент времени />0. Для k-го пакета потока 1 назначается параметр «временная метка», исходя из формулы F,к = max{F,,Vsi'v(a,Ji)}+—

Можно показать, что вышеописанный алгоритм обеспечивает принцип «справедливого распределения ресурсов»

Ввиду того, что некоторые из рассмотренных планировщиков отличаются универсальностью, а другие ориентированы на решение ограниченного круга задач, в рамках которых их эффективность представляется неоспоримой, возникает необходимость правильного и обоснованного выбора АОО при создании систем с возможностью управления трафиком В то же время возникает потребность моделирования АОО, в связи с отсутствием данных о поведении того или иного планировщика в отлшшых от рассмотренных ситуациях Моделирование проводится с целью установления способности АОО соответствовать заданным требованиям

В третьей главе рассмотрены основные принципы и этапы построения имитационных моделей и процесса имитационного моделирования Дана характеристика имитационного моделирования Рассмотрены основные элементы построения имитационных моделей Дано обоснование моделирования вычислительных систем и сетей с помощью имитационного моделирования Рассмотрены существующие СИМ, проведен их анализ, выявлены недостатки и сформулированы следующие требования к создаваемой СИМ 1) Необходимо создать специализированную СИМ для моделирования сетей передачи данных 2) Создаваемая СИМ не должна иметь привязки к реально существующему сетевому оборудованию и должна основываться только на теретико-математических моделях АОО и АУО 3) Создаваемая СИМ должна обеспечивать возможность расширения числа разных элементов (блоков), таких как АОО, АУО, блоки учета характеристик каналов связи и т д 4) Создаваемая СИМ должна обеспечивать возможность построения в ней моделей сетей с любым количеством узлов и каналов связи 5) Создаваемая СИМ должна обеспечивать удобный интерфейс пользователя с возможностями быстрой и тонкой настройки необходимых значений 6) Создаваемая СИМ должна осуществлять регистрацию и сбор всех необходимых характеристик

сети, обеспечивать наглядность их представления и иметь возможность увеличения их числа

В четвертой главе предложен обобщенный метод построения модели АОО для проведения имитационного моделирования сетей с поддержкой качества обслуживания в МАТХАВ/БшиЛтк

В общем виде имитационная модель обслуживания очередей любым из рассмотренных алгоритмов включает в себя источник последовательности пакетов, блок, реализующий АОО, и приемник последовательности пакетов (Рис 4 1 )

Рис 4.1 Прохождение тестовой последовательности через АОО

Источник последовательности пакетов служит для формирования тестовой последовательности пакетов либо произвольным образом (randomize) - при имитации произвольного трафика в сети, либо строго определенным образом — при моделировании конкретного АОО, либо при задании определенной функции распределения.

Рассматриваемые далее модели оперируют пакетами, состоящими из четырех полей 1 — номер пакета в потоке (последовательности), 2 - номер потока (последовательности), 3 — приоритет пакета, 4 — длина пакета в единицах (Рис 4 2)

1 2 3 4

Рис. 4 2 Формат пакета

В основе реализации рассмотренных выше моделей АОО положены следующие базовые принципы

• Модели имеют блочную структуру, что дает возможность гибкого масштабирования числа очередей, потоков трафика и т д

• В моделях поступление сигналов "РШ1Г'(«ВХОД») и "РОР"(«ВЫХОД») осуществляется асинхронно, т е независимо друг от друга, причем сигнал "PUSH" поступает гораздо чаще, чем сигнал "POP", что позволяет имитировать процесс перегрузки системы и дает возможность провести анализ свойств различных АОО

• В моделях существует обратная связь между блоком очередей и блоком управления, позволяющая реализовать требуемое поведение АОО, например, при переполнении или освобождении очереди

• В моделях АОО учитывается длина пакетов, однако считается, что на обработку пакета любой длины требуется гораздо меньше времени, чем то время, которое проходит между двумя последовательными сигналами "PUSH" или "POP".

• В моделях реализованы алгоритмы управления очередями Flow Control -алгоритм Tail Drop и алгоритм подавления источника при переполнении очереди (упрощенный вариант алгоритма RED)

Основным положением моделирования АОО является то, что модели работают в системе модельного времени, причем поступление на вход и передача на выход пакетов осуществляется формируемыми внешними генераторами сигналов "PUSH' и "POP", которые выполнены на элементах Pulse Generator

В процессе работы разработаны и исследованы структурные методы синхронизации и учета задержек модели

В общем случае модель АОО включает в себя (Рис 4 3).

• блок "Шейпер", служащий для разделения по определешюму признаку (per-flow, per-class) входного трафика на несколько потоков,

• блок очередей, состоящий из заданного числа очередей, соответствующих разным потокам трафика,

в блок управления, реализующий логику работы конкретного АОО

Рис. 4 3. Логическая структура АОО

В соответствии с данным рисунком, по сигналу "PUSH' трафик, представляющий собой входную тестовую последовательность, состоящую из пакетов разных потоков, поступает на вход блока шейпер, в настройках которого заранее указываются значения параметров (полей) пакетов, определяющих разделение тестовой последовательности на потоки На основании этих настроек блок шейпер формирует сигнал для блока очередей, уведомляя его о том, в какую конкретно очередь надо ввести обрабатываемый в данный момент пакет, и производит передачу данных Блок очередей, получив пакет от блока шейпер, заносит его в соответствующую очередь при условии, что очередь не полна В противном случае происходит отбрасывание пакета (алгоритм управления очередью "Отбрасывание хвоста" - Tail drop) Очереди

15

блока очередей реализованы на элементах FIFO Глубина каждой очереди, а также другие значения свойств элемента FIFO задаются заранее

Выходная последовательность формируется в приемнике последовательности пакетов под действием сигнала "POP" блока управления, реализующего соответствующий АОО и формирующего последовательность выхода пакетов из блока очередей

С целью оценки адекватности предложенной модели было выполнено следующее моделирование обслуживания четырех очередей с использованием алгоритма WFQ в режиме FQ с одинаковым весом всех потоков В качестве источников трафика использовались четыре источника тестовых последовательностей: первый и второй источники передавали пакеты длиной 1000 единиц (byte) в течение всего времени моделирования, а третий и четвертый - передавали пакеты длиной 40 единиц (byte) 1 раз в 5 единиц модельного времени. Глубина очередей «Блока очередей» была задана равной 20 пакетам

На рисунке 4 4 изображен способ формирования входной последовательности от четырех источников. «Блок управления» на основании заранее заданных значений (например, от третьего источника принимать пакеты 1 раз в 5 единиц модельного времени) формирует управляющий сигнал, согласно которому «Блок коммутации» принимает пакеты от того или иного источника и передает их на вход «Блока шейпер»

Пропускная способность каналов от источников трафика до АОО - 800 Kbit/sec, от АОО до приемника последовательности пакетов — 56 Kbií/sec Моделирование таких скоростей передачи данных на вход и обслуживание на выходе осуществляется путем установки частоты импульсов сигнала ''PUSH" в генераторах импульсов PG PUSH (Pulse Generator PUSH) и частоты сигнала "POP" в PG POP (Pulse Generator POP) Для простоты расчетов будем считать, что 1Kbyte = 1000 bytes, 800 Kbit/sec = 100 Kbyte/sec, т e при длшге пакета в 1Kbyte за 1 sec проходит 100 пакетов. Было предположено, что один пакет такой длины обслуживается за одну единицу модельного времени, которая равна 4 тактам системы моделирования MATLAB/Simulink, те 100 пакетов проходят за 400 тактов

Принимая, что 56Kbit/sec = 7 Kbyte/Sec, т е за 1 sec проходит 7 пакетов по 1Kbyte, PG PUSH должен выдавать сигналы с частотой 1 сигнал в 4 такта, а PG POP — с частотой 1 сигнал в 400/7=57 тактов Однако, ввиду того, что времени при обслуживании пакета длиной 40 bytes требуется меньше, чем на 1000 bytes, следующий сигнал "POP" должен придти раньше, т е. должен придти после обслуживания 40 байтного пакета через несколько тактов системы моделирования MATLAB/Simulink

Сбор данных осуществлялся в течение 500 Sec, что соответствует примерно 50000 единицам модельного времени и составляет примерно 200000 тактов системы моделирования MATLAB/Smuilink

Результаты моделирования приведены в Таблице 4 1

Таблица 4 1 Результаты моделирования

Типы пакетов Источник 1 Источник 2 Источник 3 Источник 4

lOOObytes lOOObytes 40Byte/5 40Byte/5

Throughput (packets) 1747 1746 98 98

Dropped (packets) 0 0 0 0

Как видно из таблицы, результаты полностью соответствуют данным, известным из литературы, т е показана адекватность созданных моделей АОО

Рис 4 4 Формирование входной последовательности от четырех источников

В пятой главе предложена методика моделирования сетей с поддержкой алгоритмов обслуживания очередей и управления очередями с использованием созданной СИМ Библиотека состоит из набора реализованных в виде блочных структур АОО и АУО с возможностью легкого масштабирования и задания необходимых значений параметров элементов

Как и в любой системе визуального моделирования, для создания имитационной модели сети необходимо иметь логическую структуру проектируемой системы Далее необходимо сформировать создаваемую сеть из элементов библиотеки, задать им необходимые числовые характеристики и соединить их необходимыми связями

Для демонстрации возможностей разработанной системы имитационного моделирования были созданы несколько имитационных моделей сети, обобщенная архитектура которых представлена на рисунке 5.1

Модели состоят из трех узлов, АОО каждого из которых может быть задан разработчиком Каждый из узлов имеет четыре входа и один выход (узел 4x1) В моделях имеются десять источников последовательностей пакетов (трафика) Первые четыре источника генерируют трафик и передают его через узел 1, источники 7-10 - через узел 2, а еще два (5-й и 6-й) - через 3-й и 4-й

входы узла 3 Выходная последовательность собирается в приемнике последовательностей пакетов (трафика)

Рис 5 1 С фуктура моделей

Настройка модели подразумевает задание и выбор всех необходимых элементов и значений параметров, которые определяют поведение системы В предложенных моделях возможен выбор и настройка следующих параметров 1) выбор АОО каждого из узлов - PQ (приоритетная очередь), RR (круговое обслуживание), WRR (взвешенное круговое обслуживание), DRR (взвешенное круговое обслуживание с дефицитом), WFQ (взвешенное равномерное обслуживание) и др , а также настройка всех значений параметров самих АОО — веса очередей, принцип распределения по очередям (приоритеты), квантовое значение очереди и т д, 2) настройка количества очередей в каждом узле; 3) настройка глубин очередей, 4) настройка скоростей каналов от источников трафика - частота импульсов «PUSH» в источнике трафика, 5) настройка скоростей выходных каналов — частота импульсов «РОР», б) настройка законов, по которым работает элементы Repeating Sequence Interpolated, 7) определение алгоритмов и функций распределения, по которым источники трафика генерируют пакеты входящего трафика, 8) определение количества входящих пакетов, 9) определение длительности времени моделирования

Регистрируемые и вычисляемые параметры С помощью разработанной системы моделирования возможна регистрация и отслеживание следующих параметров системы 1) время входа каждого пакета в систему (генерация в источнике пакетов), 2) время выхода каждого пакета из системы (приход в приемник пакетов), 3) время нахождения пакета в системе (задержка), 4) дрожание задержек пакетов; 5) время прохождения пакетом каждого из узлов, 6) количество прошедших пакетов, 7) количество потерянных (отброшенных) пакетов, 8) изменение длин очередей и их текущих значений, 9) показатель качества, определяемый на основании вышеупомянутых значений параметров (характеристик), например, определение возможности ограничения задержки пакетов в системе сверху (см главу 1)

Таким образом, предлагается создание системы моделирования, способной наглядно формировать и адекватно представлять характеристики передачи данных для их дальнейшего анализа и оценки показателей качества в сетях NGN Ввод новых параметров расширяет возможности и увеличивает число случаев применения системы

Таблица 5 1 Результаты прогонов моделирования

Скорость исходящих каналов (Kbit/Sec) Узлы 12 3 Время моделирования (500 Sec) Кол-во обслуженных пакетов Кол-во потерянных пакетов 1 2 3 И с 4 Пакеты т о ч н и к и 5 6 7 8 9 10

АОО

YVFQ

WFQ 56 56 56 196225 4029 0 870 865 97 97 98 98 845 863 98 98

WFQ 112 112 56 196225 3987 0 U39 611 98 98 98 98 1085 564 98 98

WFQ 112 112 112 196225 7269 0 1680 1673 97 97 98 98 1664 1666 98 98

WFQ 224 224 112 196225 7262 0 1943 1477 98 98 98 98 1729 1525 98 98

VVRR вес lq-10,2q-I0, 3q-2,4q-2

WRR 56 56 56 196225 4035 0 860 869 96 96 97 96 860 869 96 96

WRR 112 112 56 196225 4048 0 885 895 97 97 97 97 845 841 97 97

WRR 224 224 56 196225 4049 0 886 876 97 97 97 97 850 855 97 97

FQ Приоритет уменьшается от 1-й к 4-й очереди

PQ 56 56 56 196225 3503 0 1821 0 0 0 0 0 1682 0 0 0

PQ 112 112 56 196225 3504 0 1763 0 0 0 0 0 1741 0 0 0

DRR квантовые значения 1 q - 1000,2q - 1000,3q - 40,4q - 40

DRR 56 56 56 196225 4024 0 863 862 97 97 98 98 856 859 97 97

В соответствии со структурой, приведенной на рисунке 5 1 , были созданы несколько сетевых моделей с различными АОО Во всех трех узлах каждой из моделей были использованы АОО \VRJl, Ш^СЬ ОШ1

соответственно Количество очередей в каждом из узлов — 4 Глубины первой и второй очередей в узлах - 20 пакетов, третьей и четвертой - 4 пакета

Предполагалось, что источники трафика I, 2, 7, 8 постоянно генерируют трафик с длиной пакета 1000 bytes, а источники трафика 3, 4, 5, 6, 9, 10 генерируют 1 раз в 5 секунд пакеты длиной 40 bytes Скорость канала от источников - 800 Kbit/Sec В моделях также реализован «упрощенный вариант» АУО RED - как только необходимая очередь переполняется, источник трафика мгновенно получает сигнал и перестает подавать трафик данного типа В результате проведенных прогонов модели были получены следующие результаты (Таблица 5 1)

Для возможности анализа свойств и особенностей поведения различных АОО могут быть построены следующие графики задержек пакетов в системе (Рис.5.2. и Рис 5 3), например, АОО WFQ Скорость исходящих каналов узла I - 56 Kbit/Sec, узла II - 56 Kbit/Sec, узла III - 56 Kbit/Sec

я 5СЗЭ -------—

S

bi тяо 4* ^j*-«

С iirV» _________

- T i-

= eJ CO i

ЖО ЭОЕО iOX

Номер пакета

Рис 5 2. График задержки пакетов 1-го источника трафика в системе

а ---

3160 |-

С В«1-

с

§ ai0&J-

I Zf%.

КПП зссс *вш

_ Номер пакета

Рис. 5 3 График задержки пакетов 3-го источшжа трафика в системе

Предложенный метод настройки и замены АОО в режиме реального времени заключается в следующем Предположим, что АУО RED выключен, тогда очевидно, что начнется процесс потери пакетов Это же подтверждает эксперимент Если в модели с АОО WPQ во всех узлах выключить АУО RED для 1-го источника трафика, то потери пакетов составят 98% Если же вместо АОО WFQ в узле 1 выбрать АОО WRR (вес lq-10, 2q-10, 3q-2, 4q-2), то потери составят 95% (Таблица 5 2) Таким образом, с помощью созданной СИМ можно итеративно выбирать наиболее подходящий АОО или настраивать текущей АОО в зависимости от требований к обслуживанию или в зависимости от некого заранее оговоренного показателя качества

Скорость Время К-во Пакеты

исходящих модели- Обслу-

каналов рования женных источники

(KbitfSec) (50 Sec) пакетов 1 23456 7 8 9 10

Узлы 1 2 3

АОО

WFQ 56 56 56 20098 407 вышло 77 98 9 9 10 10 86 88 10 10

пришло 5024 98 9 9 10 10 86 88 10 10

потери 4947 00000 0 0 0 0 (98%)

WRR 56 56 56 2009S 409 вышло 237 0 9 9 10 10 30 86 9 9

пришло 5024 0 9 9 10 10 30 86 9 9

потери 4787 00000 0 0 0 0

_(95%)_

В заключении работы были сделаны следующие выводы

1 Проведенный анализ задач и функций качества обслуживания, а также анализ существующих архитектур и методов обеспечения качества обслуживания в сетях инфокоммуникаций позволяет особо подчеркнуть значимость применения АОО и АУО Предложена классификация существующих АОО по основным характеристикам и вычислительной сложности, позволяющая инженеру-разработчику предварительно оценивать и выбирать необходимые АОО в соответствии с конкретными задачами

2 Произведен анализ общих принципов построения и архитектуры имитационных моделей Произведен анализ существующих систем имитационного моделирования (СИМ), выявлены их недостатки и разработаны требования длст создаваемой СИМ

3 Разработано программное и информационное обеспечения системы имитационного моделирования в виде библиотеки элементов среды МАТЬАВ/ВнпиЬпк Главной особенностью предложенной СИМ является отсутствие в ней привязки к конкретному сетевому оборудованию, что дает возможность, быстро реализовав, например, только что созданный АОО, сравнить его с другими и проанализировать целесообразность его использования

4 Созданная по блочному принципу СИМ имеет возможность как масштабирования числа узлов, так и настройки внутренних характеристик узлов (например, количества очередей или порядка приоритетов), что дает возможность применять данную систему для практически неограниченного числа случаев Ограничениями в этом случае могут служить только аппаратные особенности ЭВМ — производительность процессора, память и т.д Созданная СИМ, давая возможность разработчику получить картину применения того или иного АОО и АУО в определенной (исследуемой) ситуации, позволяет произвести их обоснованное сравнение, становится мощным инструментом для инженеров-разработчиков сетей и предоставляет не

только широкий спектр возможностей проектирования сетей, но и возможностей управления сетями

5 Разработаны обобщенный метод построения модели АОО и базовый алгоритм моделирования сетей с поддержкой качества обслуживания в MATLAB/SImulink Созданная СИМ обеспечивает удобный и интуитивно понятный интерфейс для пользователя с возможностью быстрой и тонкой настройки необходимых значений, а также адекватной визуализацией и наглядным представлением результатов

6 Проведено имитационное моделирование с использованием созданной СИМ и подтверждена ее адекватность теоретическим описаниям и реально существующим системам

7 Разработана методика оценки показателей качества обслуживания в сети с применением созданной СИМ Предложена методика настройки АОО и выбора АОО с целью улучшения показателей качества обслуживания в режиме реального времени

8 Созданный на базе MATLAB/Simulink инструментарий на данный момент не учитывает, например, характеристики самих линий связи между узлами, однако широкий спектр математических возможностей MATLAB/Simulink позволит в дальнейшем наращивать систему, не нарушая уже созданных элементов

9 Созданная СИМ использована при проектировании модуля оценки качества передачи данных системы АМФИКОМ компании «Сайрус Системе Корпорейшн», а также в учебном процессе кафедры Электронно - вычислительной аппаратуры Московского государственного института электроники и математики (технического университета), что подтверждено актами о внедрении

Публикации в журналах, рекомендованных ВАК и других изданиях:

1 Анализ алгоритмов обслуживания очередей в сетях с поддержкой «Качества обслуживания» (QoS) / Фишман Е Б. // Качество Инновации Образование 2006, №6, стр 63-71

2 Имитационные модели обслуживания очередей, создание и применение / Иванов А.Б, Фишман Е Б // Качество и CALS-технологии 2007, № 1

3. Моделирование алгоритмов обслуживания очередей / Фишман ЕБ // Микроэлектроника и информатика - 2006 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов Тезисы докладов М'МИЭТ, 2006 -404с ISBN 5-7256-0426-8 стр 179.

4 Принципы создания моделей алгоритмов обслуживания очередей в MATLAB. / Фишман Е Б. // Труды международного симпозиума «Надежность и качество» в 2-х томах Том 1. Пенза Изд-во Пенз гос. унта, 2006, с 147-148

5 Quality of Service в сетях инфокоммуникаций механизмы обслуживания очередей, анализ преимуществ и недостатков / Фишман Е Б // Научно-технической конференции студентов, аспирантов и молодых

специалистов МИЭМ Тезисы докладов - М, ~:МИЭМ 2005 -429с ISBN 5-94506-106-9 стр 185-187 6. Модели алгоритмов обслуживания очередей в MATLAB/SIMULINK /Фишман Е Б // Научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ Тезисы докладов - М, ~ МИЭМ 2006 -404с ISBN 5-94506-137-9 стр 68 7 Методология и инструментарий моделирования сетей с QoS / Фишман Е Б // Научно-техническая конференция студентов, аспирантов, и молодых специалистов МИЭМ Тезисы докладов - М ~ МИЭМ, 2007 -469с ISBN 978-5-94506-167-5 стр 122

Подписано в печать 19 04 2007 Формат 60x84/16 Бумага типографская № 2 Печать - ризография Уел печ л 1,4 Тираж 100 экз Заказ

Московский государственный институт электроники и математики 109028, Москва, Б Трехсвятительский пер , 3/12

Центр оперативной полиграфии (095) 916-88-04, 916-89-25

СОДЕРЖАНИЕ.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

ВВЕДЕНИЕ.

ГЛАВА 1. МЕТОДЫ И СРЕДСТВА ОБЕСПЕЧЕНИЯ КАЧЕСТВА ОБСЛУЖИВАНИЯ.

1.1. Качество обслуживания.

1.2. Функции качества обслуживания и инструменты его обеспечения.

1.3. Анализ архитектур интегрированных и дифференцированных услуг (intserv и diffserv).

1.4. Показатель качества.

1.5. Предоставления сервиса провайдерами.

1.6. Выводы.

ГЛАВА 2. АНАЛИЗ АЛГОРИТМОВ ОБСЛУЖИВАНИЯ ОЧЕРЕДЕЙ.

2.1 Необходимость сравнения АОО.

2.2. Общие принципы обслуживания очередей в сетях с поддержкой качества обслуживания.

2.3. Алгоритмы обслуживания очередей.

2.3.1. Алгоритм «Первый вошел - Первый вышел» (FIFO First In - First Out).

2.3.2. Алгоритм "Круговое обслуживание".

2.3.3. Алгоритм "Круговое обслуживание с дефицитом".

2.3.4. Алгоритмы обслуживания очередей с приоритетами.

2.3.5. Модифицированный алгоритм PS.

2.3.6. Алгоритм "Взвешенное Круговое обслуживание".

2.3.7. Алгоритм "Модифицированное круговое обслуживание с дефицитом".

2.3.8. Алгоритм GPS.

2.3.9. Алгоритм Weighed Fair Queuing.

2.3.10. Алгоритм WF2Q.

2.3.11. Алгоритм WF2Q+.

2.3.12. Алгоритм Virtual Clock.

2.3.13. Алгоритм Leap Forward Virtual Clock.

2.3.14. Алгоритм SCFQ.

2.4. Классификация АОО.

2.5. Выводы.

ГЛАВА 3. АНАЛИЗ СИСТЕМ ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ.

3.1. Выбор метода моделирование для анализа проектируемых вычислительных систем и сетей.

3.2. Обзор имеющихся СИМ.

3.2.1. Универсальная система Симула 67.

3.2.2. GPSS.

3.2.3. Система NetCracker.

3.2.4. SimEvent.

3.3. Возможности имитационного моделирования.

3.4. Организация имитационного моделирования.

3.5. Элементы архитектуры имитационной модели.

3.6. Разработка требований к создаваемой СИМ.

3.7. Выводы.

ГЛАВА 4. МОДЕЛИРОВАНИЕ АЛГОРИТМОВ ОБСЛУЖИВАНИЯ ОЧЕРЕДЕЙ.

4.1. Необходимость моделирования для выбора АОО.

4.2. Принципы и положения моделирования АОО.

4.3. Базовая структура модели обслуживания очередей.

4.4. Методы синхронизации и учета задержек в модели АОО.

4.5. Разработка обобщенной логической архитектуры модели АОО.

4.6. Базовые блоки и элементы модели.

4.7. Пример реализации модели АОО.

4.7.1. Блок Вход/Выход.

4.7.2. Блок "Шейпер".

4.7.3. Блок очередей.

4.7.4. Блок управления.

4.8. Базовый алгоритм моделирования и анализ результатов.

4.9. Выводы.

ГЛАВА 5. МЕТОДИКА ПРИМЕНЕНИЯ РАЗРАБОТАННОЙ СИМ ДЛЯ МОДЕЛИРОВАНИЯ ИНФОРМАЦИОННЫХ СЕТЕЙ С ПОДДЕРЖКОЙ

АЛГОРИТМОВ ОБСЛУЖИВАНИЯ И УПРАВЛЕНИЯ ОЧЕРЕДЯМИ.

5.1. Инструментарий создания моделей.

5.2. Основа построения моделей сетей.

5.3. Архитектурные особенности моделей сетей.

5.4. Настройка модели.

5.5. Регистрируемые и вычисляемые параметры.

5.6. Эксперимент с целью оценки показателей качества.

5.7. Метод настройки и замены АОО в режиме реального времени.

5.8. Выводы.

Актуальность работы. Одной из задач современного этапа развития инфокоммуникаций является переход к сетям следующего поколения (NGN -Next Generation Networks), позволяющим наиболее эффективно обеспечивать необходимый уровень качества обслуживания в сетях (QoS). Выполнение этой задачи невозможно без использования все более эффективных алгоритмов обслуживания (АОО) и управления (АУО) очередями, являющихся основой для предоставления гарантированного качества услуг связи. Это, естественно, требует проведения предварительного моделирования сетей связи с целью создания наиболее адекватной системы, способной соответствовать заданным и подразумеваемым требованиям. В настоящее время существует достаточно много систем моделирования, большинство из которых основаны на использовании библиотек оборудования известных производителей, что не позволяет выполнить имитационное моделирование новых АОО и АУО и, как следствие, провести оценку их эффективности. В связи с этим разработка системы моделирования, использующей теоретические модели, является чрезвычайно актуальной.

Цель работы. Целью настоящей работы является разработка модели и инструментальных средств проектирования (системы имитационного моделирования - СИМ) и исследования информационных сетей, не привязанных к конкретному оборудованию, а основанных на математических моделях шаблонов настраиваемых (конфигурируемых) элементов сетей. Для достижения этой цели поставлены и решены следующие задачи:

1. Анализ путей обеспечения гарантированного качества обслуживания в сетях инфокоммуникаций.

2. Анализ существующих архитектур и методов обеспечения качества обслуживания в сетях инфокоммуникаций.

3. Классификация существующих АОО по основным характеристикам и вычислительной сложности.

4. Анализ общих принципов построения и архитектурных особенностей имитационных моделей.

5. Анализ существующих СИМ, выявление их недостатков и разработка требований к СИМ, использующей шаблоны настраиваемых элементов сетей инфокоммуникаций.

6. Разработка обобщенного метода построения модели АОО и базового алгоритма моделирования сетей с поддержкой качества обслуживания в MATLAB/ Simulink.

7. Создание программного и информационного обеспечения СИМ в виде библиотеки элементов среды MATLAB/ Simulink.

8. Разработка удобного и интуитивно понятного интерфейса для пользователя с возможностью быстрой и тонкой настройки необходимых значений, а также адекватной визуализацией и наглядным представлением результатов.

9. Разработка методики оценки показателей «качества обслуживания» в сети инфокоммуникаций с применением созданной СИМ.

10. Проведение имитационного моделирования с использованием созданной СИМ и подтверждение ее адекватности реальным системам.

11.Разработка методики настройки АОО и выбора АОО с целью улучшения показателей «качества обслуживания» в режиме реального времени.

Методы исследований. При решении поставленных задач использовались принципы построения имитационных моделей систем и сетей массового обслуживания (СМО и СеМО), теория телетрафика, теория планирования эксперимента, а также теория массового обслуживания (ТМО).

Для исследования АОО и АУО использовался MATLAB/Simulink 7.0 компании Math Works Inc. и проводилось компьютерное моделирование с применением специально разработанной библиотеки шаблонов. Основные теоретические положения подтверждены результатами экспериментальных исследований.

Научная новизна результатов работы:

1. Предложена классификация АОО по основным характеристикам и вычислительной сложности.

2. Разработаны и исследованы методы создания шаблонов настраиваемых (конфигурируемых) сетевых элементов с целью имитационного моделирования АОО и АУО в MATLAB/ Simulink.

3. Предложена обобщенная архитектура модели АОО.

4. Разработан базовый алгоритм моделирования сетей с АОО с использованием данных шаблонов в MATLAB/ Simulink.

5. Разработаны и исследованы структурные методы синхронизации и учета задержек модели. л

Практическую значимость имеют:

1. Созданная СИМ на базе разработанной библиотеки шаблонов, состоящей из различных АОО и АУО, позволяющая проводить имитационное моделирование сетей передачи данных с поддержкой качества обслуживания.

2. Базовый алгоритм моделирования сетей с АОО с использованием созданной СИМ.

3. Методика выбора наиболее оптимального АОО для текущей ситуации в режиме реального времени.

4. Разработанная структура имитационных моделей и схемы их функциональных узлов.

Внедрение. Созданная СИМ использована при проектировании модуля оценки качества передачи данных для Автоматизированного многофункционального интегрированного комплекса объектного мониторинга (АМФИКОМ) сетей инфокоммуникаций компании «Сайрус Системе Корпорейшн», а также в учебном процессе кафедры Электронно -вычислительной аппаратуры Московского государственного института электроники и математики (технического университета).

Апробация работы. Основные положения диссертации докладывались и обсуждались на ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2005-2007 гг.), 13-й Всероссийской межвузовской научно-технической конференции студентов и аспирантов МИЭТ (Москва, Зеленоград, 2006 г.), в Трудах международного симпозиума «Надежность и качество» (Пенза, 2006 г.).

На защиту выносятся следующие основные положения:

1. Предложенный обобщенный метод построения модели АОО и базовый алгоритм моделирования сетей с поддержкой качества обслуживания в MATLAB/ Simulink.

2. Разработанное программное и информационное обеспечение системы имитационного моделирования (СИМ) в виде библиотеки элементов среды MATLAB/ Simulink.

3. Разработанная методика оценки показателей качества обслуживания в сети с применением созданной СИМ.

4. Разработанная методика настройки АОО и выбора АОО с целью улучшения показателей качества обслуживания в режиме реального времени.

5. Результаты имитационного моделирования сетей телекоммуникаций с использованием разработанной СИМ.

Структура работы. Общий объем диссертации составляет 111 стр. машинописного текста, включая список литературы, и содержит 32 иллюстрации и 3 таблицы. Работа состоит из введения, пяти глав, заключения (выводов), списка сокращений и списка литературы, включающего 47 отечественных и 67 зарубежных изданий.

Публикации в журналах, рекомендованных ВАК и других изданиях:

1. Анализ алгоритмов обслуживания очередей в сетях с поддержкой «Качества обслуживания»(С>о8). / Фишман Е.Б.// Качество. Инновации. Образование. 2006, №6, стр.63-71.

2. Имитационные модели обслуживания очередей: создание и применение. / Иванов А.Б., Фишман Е.Б.// Качество и CALS-технологии. 2007, № 1.

3. Моделирование алгоритмов обслуживания очередей. / Фишман Е.Б.// Микроэлектроника и информатика - 2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. М.: МИЭТ, 2006. - 404с. ISBN 5-72560426-8 стр.179.

4. Принципы создания моделей алгоритмов обслуживания очередей в MATLAB. / Фишман Е.Б.// Труды международного симпозиума «Надежность и качество» в 2-х томах. Том 1. Пенза: Изд-во Пенз. гос. ун-та, 2006, с. 147-148.

5. Quality of Service в сетях инфокоммуникаций: механизмы обслуживания очередей, анализ преимуществ и недостатков. / Фишман Е.Б.// Научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. - М, ~:МИЭМ 2005. -429с. ISBN 5-94506-106-9 стр. 185-187.

6. Модели алгоритмов обслуживания очередей в MATLAB/SIMULINK. /Фишман Е.Б.// Научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. - М, ~:МИЭМ 2006. - 404с. ISBN 5-94506-137-9 стр.68.

7. Методология и инструментарий моделирования сетей с QoS. / Фишман Е.Б.// Научно-техническая конференция студентов, аспирантов, и молодых специалистов МИЭМ. Тезисы докладов. - М. ~:МИЭМ, 2007. - 469с. ISBN 978-5-94506-167-5 стр.122.

ВВЕДЕНИЕ.

Сети связи следующего поколения.

До недавнего времени поставщикам услуг Internet (провайдерам) и крупным компаниям приходилось создавать и поддерживать отдельные сети для передачи голосовой информации, видеоизображения, трафика, необходимого для решения критически важных задач, и всего остального сетевого трафика. Тем не менее, нельзя не отметить сложившуюся в последнее время ярко выраженную тенденцию к объединению всех этих сетей в одну сеть с пакетной передачей данных. Начались радикальные изменения тех концептуальных положений, которые определяют основные направления дальнейшего развития телекоммуникационной системы. Сформировалась идея построения сети связи следующего поколения, известная под аббревиатурой NGN (Next Generation Network). Большинство специалистов считает идею NGN самой разумной концепцией дальнейшего развития инфокоммуникационной системы - симбиоза электросвязи и информатики.

Теоретически концепция NGN может быть реализована в процессе развития любой эксплуатируемой ныне сети электросвязи: телефонной, обмена данными, кабельного телевидения. Гипотетически можно рассматривать идею создания еще одной - новой - сети, полностью соответствующей концепции NGN. Однако с практической точки зрения интерес представляет только тот способ построения NGN, который основан на целенаправленном развитии телефонной сети общего пользования (ТФОП). Среди изменений в ТФОП необходимо выделить переход к пакетным технологиям передачи и коммутации, стимулирующим разработку новых принципов построения сети [33].

Одной из важнейших задач при создании NGN является разработка методов расчета характеристик, которые позволяют анализировать качество обслуживания трафика в NGN в целом, а также в ее отдельных фрагментах.

Поскольку количество пользователей Internet и различных сетевых приложений увеличивается с каждым днем, сеть нуждается в средствах, которые бы обеспечили поддержку как существующих, так и появляющихся приложений и служб. Тем не менее, на сегодняшний день Internet может обеспечить всего лишь негарантированную доставку данных (best effort service). Негарантированная доставка данных не предполагает предоставления каких-либо гарантий, касающихся времени и самого факта прибытия пакета в пункт назначения. При этом нельзя не отметить, что отбрасывание пакетов может произойти только в момент перегрузки сети.

Характеристики качества обслуживания трафика традиционно считаются одним из важнейших научных направлений в исследованиях сетей телефонной связи и обмена данными. Российская научная школа в этом направлении (теория телетрафика) - одна из сильнейших в мире. Существенный вклад в развитие теории телетрафика внесли Г.П. Башарин, Б.С. Лившиц, В.И Нейман, С.Н. Степанов, А.Д. Харкевич, М.А. Шнепс-Шнеппе, Г.Г. Яновский и другие известные ученые. Говоря о достижениях зарубежных специалистов, следует упомянуть имена В. Иверсена, JI. Клейнрока, П. Кюна.

Результаты, полученные отечественными и зарубежными специалистами, полезны для исследования характеристик качества обслуживания трафика в NGN. Вместе с тем, принципы функционирования всех устройств коммутации в NGN имеют специфику, которая обусловлена выбранной технологией распределения информации. По этой причине необходима разработка новых методов расчета ряда вероятностно-временных характеристик NGN, адекватно отражающих процессы обмена информацией между абонентами [33].

5.8. Выводы

1. В главе подробно изложены методы построения сетей в созданной СИМ с целью их дальнейшего изучения и проектирования, и определены регистрируемые параметры сети.

2. Рассмотрены особенности коммутации элементов созданной библиотеки моделирования сетей телекоммуникаций.

3. Выполнено моделирование четырех базовых АОО, показавшее возможность наглядного представления исследуемых характеристик сети.

4. Предложен метод настройки и изменения АОО в режиме реального времени для улучшения показателей качества обслуживания.

ЗАКЛЮЧЕНИЕ

В ходе работы над диссертацией были сделаны следующие выводы:

1. Проведенный анализ задач и функций качества обслуживания, а также анализ существующих архитектур и методов обеспечения качества обслуживания в сетях инфокоммуникаций позволяет особо подчеркнуть значимость применения АОО и АУО. Предложена классификация существующих АОО по основным характеристикам и вычислительной сложности, позволяющая инженеру-разработчику предварительно оценивать и выбирать необходимые АОО в соответствии с конкретными задачами.

2. Произведен анализ общих принципов построения и архитектуры имитационных моделей. Произведен анализ существующих систем имитационного моделирования (СИМ), выявлены их недостатки и разработаны требования для создаваемой СИМ.

3. Разработано программное и информационное обеспечения системы имитационного моделирования в виде библиотеки элементов среды MATLAB/Simulink. Главной особенностью предложенной СИМ является отсутствие в ней привязки к конкретному сетевому оборудованию, что дает возможность, быстро реализовав, например, только что созданный АОО, сравнить его с другими и проанализировать целесообразность его использования.

4. Созданная по блочному принципу СИМ имеет возможность как масштабирования числа узлов, так и настройки внутренних характеристик узлов (например, количества очередей или порядка приоритетов), что дает возможность применять данную систему для практически неограниченного числа случаев. Ограничениями в этом случае могут служить только аппаратные особенности ЭВМ -производительность процессора, память и т.д. Созданная СИМ, давая возможность разработчику получить картину применения того или иного АОО и АУО в определенной (исследуемой) ситуации, позволяет произвести их обоснованное сравнение, становится мощным инструментом для инженеров-разработчиков сетей и предоставляет не только широкий спектр возможностей проектирования сетей, но и возможностей управления сетями.

5. Разработаны обобщенный метод построения модели АОО и базовый алгоритм моделирования сетей с поддержкой качества обслуживания в MATLAB/Simulink. Созданная СИМ обеспечивает удобный и интуитивно понятный интерфейс для пользователя с возможностью быстрой и тонкой настройки необходимых значений, а также адекватной визуализацией и наглядным представлением результатов.

6. Проведено имитационное моделирование с использованием созданной СИМ и подтверждена ее адекватность теоретическим описаниям и реально существующим системам.

7. Разработана методика оценки показателей качества обслуживания в сети с применением созданной СИМ. Предложена методика настройки АОО и выбора АОО с целью улучшения показателей качества обслуживания в режиме реального времени.

8. Созданный на базе MATLAB/Simulink инструментарий на данный момент не учитывает, например, характеристики самих линий связи между узлами, однако широкий спектр математических возможностей MATLAB/Simulink позволит в дальнейшем наращивать систему, не нарушая уже созданных элементов.

9. Созданная СИМ использована при проектировании модуля оценки качества передачи данных системы АМФИКОМ компании «Сайрус Системе Корпорейшн», а также в учебном процессе кафедры Электронно - вычислительной аппаратуры Московского государственного института электроники и математики (технического университета), что подтверждено актами о внедрении.

1. Авен О.И., Гурин Н.Н., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М.: Наука, 1982. - 464 с.

2. Альянах И.Н. Моделирование вычислительных систем JI.: Маштностроение, 1988. - с. 225.

3. Андрианов А.Н., Бычков СЛ., Хорошилов Д.И. Программирование на языке Симула 67. М.: Наука, 1985. - 228 с.

4. Андрианов А.Н., Бычков СЛ., Хорошилов Д.И. Средства раздельной компиляции СИМУЛА-программ на БЭСМ-64 ЕС ЭВМ. М.: ИПМ АН СССР, 1982.-40 с.

5. Андрианов А.Н., Бычков СЛ. и др. Система моделирования на базе языка СИМУЛА-67 для БЭСМ-6 и ЕС ЭВМ // Моделирование дискретных управляющих и вычислительных систем: Тез. докл. III Всесоюз. Семинара. Свердловск, 1981. - С. 44,45.

6. Ахламов А.Г., Баева И.Н. и др. Диалоговые процедуры управления ходом имитационного эксперимента на ЭВМ. // Теория и практика имитационного моделирования сложных систем: Тез. докл. республик, науч.-техн. Конф. Одесса, 1983. -сс. 16, 17.

7. Базенов В.И., Стрельченко A.M. Основы планирования и моделирования в теории инженерного эксперимента. Учебн. пособие факультета повыш. квалиф. ИТР. М.: МАИ, 1983. - 58 с.

8. Важенин В.И. и др. Методы моделирования сложных систем ЭВМ. Труды Радиотехнического института АН СССР. 1972, №12.

9. Волковинский М.И., Кабалевский А.Н. Анализ приоритетных очередей с учетом времени переключения. М.: Энергоатом издат, 1981. - 168 с.

10. Ю.Гультяев А. Визуальное моделирование в среде MATLAB: учебный курс, Издательский дом Питер, Москва, Харьков, Минск, 2000. 432с.

11. Дал У., Мюрхауг Б, Нюгорд К. Симула 67. Универсальный язык программирования / перевод с английского М.: Мир 1969г. - 100с.

12. Джонсон В.П. Справочник системного программиста по операционной системе ОС ЕС. М.: Финансы и статистика, 1982. - 224 с.

13. Иванов А.Б., Фишман Е.Б. Имитационные модели обслуживания очередей: создание и применение. Качество и CALS-технологии. 2007, № 1.

14. Иванова А.Б. Контроль соответствия в телекоммуникациях и связи. Часть I. 2-е издание. М.: Компания САЙРУС СИСТЕМС 2001. - 375с.

15. Калашников В.В., Лутков В.И. и др. Вопросы разработки имитационных систем // Электронная техника. Сер. Экономика и системы управления. 1983. - Вып. 1. - сс. 71-87.

16. Калашников В.В Организация моделирования сложных систем // Математика и кибернетика. М.: Знание, 1982. - №3/82. - сс. 64-72.

17. Киндлер Е. Языки моделирования / перевод с чешского М.: Энернгоатомиздат, 1985 - с. 288.

18. Клейнрок Л. Теория массового обслуживания. М.: Машиностроение, 1979.-432с.

19. Кучерявый Е.А. Управление трафиком и качество обслуживания в сети интернет. СПб.: Наука и Техника, 2004. - 336с.

20. Максимей И.В. Имитационное моделирование. М.: Радио и связь, 1988.-231 с.

21. Потемкин В.Г., Matlab 5 для студентов, М.: Диалог-Мифиб 1998 314 с.

22. Полляк Ю.Г. Вероятностное моделирование на электронных вычислительных машинах. М.: Сов. Радио, 1971. - 399 с.

23. Пранявичюс Г. Модели и методы исследования вычислительных систем. Вильнюс: Мокслас, 1982. - 227 с.

24. Рыжиков Ю.И. Имитационное моделирование. Теория и технологии. -СПб.: КОРОНА принт; М.: Альтекс-А, 2004. 384 с.

25. Семишев Ю.А. Входной язык автоматизированной системы имитационного моделирования. Одесса, 1987. - 26 с. - Деп. в ВИНИТИ, №3655-78.

26. Смит Дж.М. Математическое и цифровое моделирование для инженеров и исследователей. М.: Машиностроение, 1980. - 271 с.

27. Советов Б.Я., Яковлев С.А. Моделирование систем М.: Высшая школа, 1998.-320с.

28. Советов Б.Я., Яковлев С.А. Моделирование систем: практикум М.: Высшая школа, 1999. - 224с.

29. Таненбаум Э. Современные операционные системы. 2-е издание / перевод с английского. СПб.: Питер, 2002 - 1040с.

30. Феррари Д. Оценка производительности вычислительных систем. М.: Мир, 1981.-576 с.

31. Фишман Е.Б. Анализ алгоритмов обслуживания очередей в сетях с поддержкой «Качества обслуживания» (QoS). Качество. Инновации. Образование. 2006, №6, сс.63-71.

32. Фишман Е.Б. Методология и инструментарий моделирования сетей с QoS. Научно-техническая конференция студентов, аспирантов, и молодых специалистов МИЭМ. Тезисы докладов. М. ~:МИЭМ, 2007. -469с. ISBN 978-5-94506-167-5 с. 122.

33. Фишман Е.Б. Модели алгоритмов обслуживания очередей в MATLAB/SIMULINK. Научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. М, ~:МИЭМ 2006. -404с. ISBN 5-94506-137-9 с.68.

34. Фишман Е.Б. Моделирование алгоритмов обслуживания очередей. Микроэлектроника и информатика 2006. 13-я Всероссийская межвузовская научно-техническая конференция студентов и аспирантов: Тезисы докладов. М.: МИЭТ, 2006. - 404с. ISBN 5-72560426-8 с Л 79.

35. Фишман Е.Б. Принципы создания моделей алгоритмов обслуживания очередей в MATLAB. Труды международного симпозиума «Надежность и качество» в 2-х томах. Том 1. Пенза: Изд-во Пенз. гос. ун-та, 2006, сс. 147-148.

36. Харин Ю.С. и др. Имитационное и статистическое моделирование: учебное пособие. Минск: Белорусский Гос. Ун-т., 1992. - 176с.

37. Шеннон Р. Имитационное моделирование систем искусство и наука / перевод с английского. - М.:, 1978. - 418с.

38. Шрайбер Т. Дж. Моделирование на GPS / перевод с английского. М.: Машиностроение, 1980 - 592с.

39. Шрайбер Т.Дж. Моделирование на GPSS. М.: Машиностроение, 1980. -592 с.

40. Шринивас Вегешна. Качество обслуживания в сетях IP / перевод с английского. М.: Издательский дом «Вильяме», 2003 - 368с.

41. Яновский Г.Г., Методы и модели управления сетевыми ресурсами в цифровых сетях интегрального обслуживания, диссертация на соискание ученой степени доктора технических наук, ГУТ им. Проф. М.А. Бонч-Бруевича, С.-Петербург, 1994.

42. Anjum F.M., Tassiulas L., Balanced RED: An Algorithm to Achieve Fairness in the Internet, Technical Report T.R. 99-17, Center for Satellite and Hybrid Communication Networks, 1999.

43. Armitage G., Quality of Service in IP networks. Foundations for a MultiService Internet, Mtp, 2000.

44. Athuraliya S., Li V.H., Low S.H., Yin Q., REM: Active Queue Management, IEEE Network, May 2001.

45. Bacon D., Dupuy A., Schwartz J., Yemimi Y., Nest: a Network Simulation and Prototyping Toll, Proceeding of Winter 1988 USENIX Conference, 1988, pp. 17-78.

46. Bala K., Cidon I., Sohraby K. Congestion Control for High Speed Packet Switched Networks", INFOCOM '90, 1990, pp. 520-526.

47. Bennett J.C.R., Stephens D. C., Zhahg Hui. High Speed, Scalable and Accurate Implementation of Fair Queuing Algorithms in ATM Networks // in Proceedings of ICNP International Conference of Network Protocols, 1997.

48. Bennett J.C.R., Zhang H. «WF2Q: Worst-case Fair Weighted Fair Queueing» // in Proceedings of INFOCOM'96, March, 1996.

49. Bonald Т., May M., Bolot J.-C., Analytic evaluation of RED performance, IEEE INFOCOM 2000, pp. 1415-1444.

50. Brakmo L.S., O'Malley S.W., Peterson L.L. TCP Vegas: New Techniques for Congestion Detection and Avoidance // in proceedings of ACM SIGCOMM'94, August 1994, pp 24-35.

51. Bratley P., Fox B.L., Schrage L.E. A guide of Simulation N.Y. SpringerVerlag, 1983.

52. Cassandras, Christos G., and Stephane Lafortune, Introduction to Discrete Event Systems, Boston, Kluwer Academic Publishers, 1999.

53. Chao J.H., Guo X., Quality of Service Control in High-Speed Networks, John Willey & Sons Inc., 2002, 432 p., ISBN 0-471-00379-2.

54. Clark D., Fang W., Explicit Allocation of Best Effort Packet Delivery Service, ACM Transactions on Networking, vol.6., no.4., August, 1998, pp. 362-373.

55. Cruz R.L., A calculus for network delay. I. Network elements in isolation, IEEE Transactions on Information Theory, Volume: 37, Issue: 1, January 1991, pp. 114-131.

56. Cruz R.L., A calculus for network delay. II. Network analysis, IEEE Transactions on Information Theory, Volume: 37, issue: 1, January 1991, pp. 132-141.

57. D. Chiu and R. Jain, Analysis of the Increase/Decrease Algorithms for Congestion Networks and ISDN, Vol. 17, No. 1, June 1989, pp 1-14.

58. Demers A., Keshav S., Shenkar S. A classical self-locked WFQ algorithm // SIGCOMM '89, Austin, TX, September 1989

59. Demers A., Keshav S., Shenker S. Analysis and Simulation of a Fair Queuing Algorithm // University of California at Berkeley. 1989.

60. Elwalid A., Mitra D., Wentworth R., A new approach for allocating buffers and bandwidth to heterogeneous, regulated traffic in an ATM node, IEEE Journal on Selected Areas in Communications, vol.13, no.6, August 1995, pp,l 115-1127.

61. Feng W.-C., Kandlur D.D., Saha D., Shin K.G., A self-configuring RED gateway, proceedings of INFOCOM'99, vol. 3, pp. 1320-1328.

62. Ferguson P., Huston G., Quality of Service: delivering QoS on the Internet and in corporate networks. Johb Wiley & Sons, Inc., 1998 - 266pp.

63. Floyd S. RED: Discussions of Byte and Packet Modes, March 1997, http://www-nrg.ee.lbl.gov/floyd/REDaveraging.txt.

64. Floyd S., Equation-Based Congestion Control for Unicast Applications: the Extended Version, International Computer Science Institute tech report TR-00-03, March 2000.

65. Floyd S., and Jacobson V. Link-Sharing and Resource Management Models for Packet Networks. IEEE/ACM Transactions on Networking, Vol. 3 No. 4, pp. 365-386, August 1995.

66. Floyd S., Connection with Multiple Congested Gateways in Packet-Switched Networks Part 1: One-way Traffic, Computer Communication Review, V.21 N.5, October 1991, pp. 30-47.

67. Floyd S., Jacobson V. Random Early Detection Gateway for Congestion Avoidance / To appear in the August 1993 IEEE/ACM Transactions on Networking

68. Floyd, S., and Fall, K., Promoting the Use of End-to-End Congestion Control in the Internet, IEEE/ACM Transactions on Networking, August 1999.

69. Georgiadis L., Guerin R., Peris V., Sivarajan K., Efficient network QoS Provisioning Based on per Node Traffic Shaping, IEEE/ACM Ttransactions on Networking, Vol. 4, No. 4, August 1996.

70. Gevros P., Crowcroft J., Kirstein P., Bhatti S., Congestion Control mechanism and the best Effort Service Model, IEEE Network, May/June, 2001, pp. 16-26.

71. Golenstani S.J. «А Self-clocked Fair Queuing Schema for Broadband Applications» // in proceedings of IEEE INFOCOM Torontro, April, 1994, pp.636-646.

72. Gordon G. The Application of GPSS V to Discrete System Simulation. -Prentice-Hall, Englewood Cliffs, N.J. 1975. - 398pp.

73. Grossglauser М., Tse D., A Framework for Robust Measurement-Based Admission Control, IEEE/ACM trans. On Networking, vol 7, no 3, June 1999.

74. Grossglauser M., Tse D., A Time-Scale Decomposition Approach to Measurement-Based Admission Control, IEEE/ACM Trans. On Networking (to appear), 2002.

75. Guerin R., Quality-of-Service in IP Networks, IEEE RTAS 2000, Washinton D.C., May 2000.

76. Hashem E., Analysis of random drop for gateway congestion control, report LCS TR-465, Laboratory for Cmputer Science, MIT, Cambridge, MA, 1989, p.103.84.http://www.mathworks.com/access/helpdesk/help/toolbox/simevents/gs/.

77. Jacobson V., Congestion Avoidance and Control, Proceedings of SIGCOMM '88, August 1988, pp. 314-329.

78. Jaffe J.M., Bottleneck Flow Control, IEEE Transactions on Communications, vol.29, july 1981, pp.954-962.

79. Jain R., A Delay-Based Approach for Congestion Avoidance in Interconnected Heterogeneous Computer Networks, Computer Communication Review, V.19 N5, October 1989, pp. 56-71.

80. Jamin S., A Measurement-based Admission control Algorithm for Integrated Services Packet Networks, PhD dissertation, Department of Computer Science, University of Southern California, August 1996.

81. Jamin S., Danzig P.B., Shenker S., Zhang L., A Measurement-Based Admission Control Algorithm for Integrated Services Packet Networks, IEEE/ACM Transactions on Network, 5(1), February 1997.

82. Jamin S., Shenker S., Danzig P.B., Comparision of Measurement-Based Admission Control Algorithms for Controlled-Load Service // in Proceedings of IEEE INFOCOM, March 1997.

83. Keshav S. An Engineering Approach to Computer Networking -Reading // MA: Addison-Wesley, 1997

84. Keshav S., REAL: a Network Simulator, Report 88/472. Conputer Science Department, University of California at Berkeley, Berkeley, California, 1988.

85. Lakshman T.V., Neidhardt A., Ott Т., The Drop From Front Strategy in TCP Over ATM and Its Interworking with Other Conrtol Features, INFOCOM'96, MA28.1.

86. Law, Averill M., and W. David Kelton, Simulation Modeling and Analysis, 3rd Ed.,New York, McGraw-Hill, 1999.

87. LeBoudec J.Y., Thiran P., Network Calculus. A theory of deterministic queueing systems for the Internet, Springer-Verlag, LNCS number 3050, 2002.

88. McDysan D, QoS & Traffic Management in IP & ATM Networks -McGraw-Hill, 2000 458 pp.

89. P. van Emde Boas, R. Kaas and E. Zijlstra. Desigh and implementation of an efficient priority queue.//Math. Syst. Theory, 10:99-127,1977.

90. Parekh A.K. Gallager R.G. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Multiple Node Case // IEEE/ACM Transaction of Networking, vol.2, no.2, pp. 137-150, April 1994

91. Parekh A.K. Gallager R.G. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Single Node Case // IEEE/ACM Transaction of Networking, vol.1, no.3, pp.344-357, June 1993

92. Perkins C., Hodson o., Hardman V., A Survey of Packet Loss Recovery Techniques for Streaming Audio, IEEE Network Magazine, September/October 1998, pp. 40-47.

93. Rosenberg J., Qiu L., Schulzrinne H., Integrating Packet FEC into Adaptive Playout Buffer Algorithms on the Internet, in proceedings of INFOCOM 2000, Tel Aviv, 2000.

94. Sariowan H., Cruz R.L., Polyzos G.C., Scheduling for Quality of Service Guarantees via Service Curves, Proceedings of the International

95. Conference on Computer Communications and Networks (ICCCN) 1995, Las Vegas.

96. Shreedhar M., Varghese G., Efficient fair queuing using deficit round-robin // IEEE/ACM Transaction of Networking, vol.4, no.3, pp.375-385, June 1996

97. Stiliadis D. Traffic scheduling in packet-switching networks: analysis, design and implementation // PhD dissertation, Computer Science Department, University of California, Santa Cruz, June 1996.

98. Stiliadis D., Varma A, A general methodology for design efficient traffic scheduling and shaping algorithms // IEEE INFOCOM, Kobe, Japan, April 1997.

99. Stiliadis D., Varma A, Efficient fair queuing algorithms for packet-switched networks // IEEE/ACM Transactions on Networking, vol. 6, no. 2, pp.175-185, April 1998.

100. Suri S., Varghese G, Chandranmenon G., Leap Forward Virtual Clock: a new fair queuing scheme with guaranteed delays and throughput fairness // IEEE INFOCOM 1997.

101. Wang Z., Crowcroft J. A new Congestion Control Scheme: Slow Start and Search (Tri-S), Computer Communication Review, V.21 N1, January 1991, pp. 32-43.

102. Widjaja I., Performance analysis of burst admission-control protocols, IEE Proceeding of Communications, 142:7-14, February 1995.

103. Wroclawski J. Specification on the Controlled-Load Network Elements Service // RFC 2211, September 1997.

104. Zhang H., Ferrari D., Rate-controlled Service Disciplines, Journal of High Speed Networks: Special Issue on Quality of Service, 3(4), 1994.

105. Zhang L. Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks // proceedings of ACM SIGCOMM, September 1990, pp. 19-29.

106. Zhao W., Olshefski D., Schulzrinne H., Internet Quality of Service: an Overview, Columbia Technical Report CUCS-003-00, February 2000.

107. Zhou J., Onozato Y., Yamamoto U., The Study of Burst Admission Control in an Integrated Voice/Data Cellular System, NETWORKING 2000:908-919.