Содержание к диссертации
Введение
ГЛАВА 1. Исследование существующих алгоритмов защиты от перегрузок сетей ATM
1.1 Постановка задачи 18
1.2 Исследование состояния проблемы 18
1.3 Классификация алгоритмов защиты от перегрузок
1.4 Анализ алгоритмов с превентивным методом защиты от перегрузок 36
1.5 Анализ алгоритмов с реактивным методом защиты от перегрузок 43
1.6 Выводы 69
ГЛАВА 2. Разработка алгоритмов защиты от перегрузок сетей ATM
2.1 Постановка задачи 71
2.2 Разработка алгоритма с функцией защиты от неуправляемых источников 72
2.2.1 Определение требований к разработке алгоритмов защиты от перегрузок сетей ATM 72
2.2.2 Разработка процедур предупреждения перегрузок 73
2.2.3 Разработка процедур защиты от неуправляемых источников 75
2.3 Разработка алгоритма с функцией защиты от перерезервирования или недоиспользования полосы пропускания виртуального канала 77
2.4 Разработка алгоритма с функцией защиты от перегрузок вызванных переполнением буферных накопителей коммутаторов ATM з
2.5 Сравнительный анализ функций и процедур разработанных алгоритмов защиты от перегрузок 81
2.6 Разработка алгоритма защиты от перегрузок IERCA 82
2.6.1 Разработка диаграммы процесса алгоритма IERCA 82
2.6.2 Разработка режима предупреждения перегрузок 2.6.3 Вывод формулы расчета допустимой скорости передачи по виртуальному каналу 94
2.6.4 Разработка процедур расчета допустимой скорости передачи и обработки ячеек RM 99
2.6.5 Разработка режима выборочного уничтожения ячеек с
заданной вероятностью 101
2.6.6 Разработка режима защиты от неуправляемых источников.. 111
2.6.7 Разработка режима защиты от перерезервирования или
недоиспользования полосы пропускания виртуального канала 114
2.7 Выводы 118
ГЛАВА 3 Теоретический анализ структуры алгоритма защиты от перегрузок сетей ATM
3.1 Постановка задачи 120
3.2 Разработка Процедуры теоретического анализа структуры алгоритма защиты от перегрузок 121
3.2.1 Разработка графа сети Петри Алгоритма 122
3.2.2 Построение составной матрицы изменений, эквивалентной графу сети Петри Алгоритма 129
3.3 Определение критериев для оценки результатов теоретического анализа структуры алгоритма защиты от перегрузок 139
3.3.1 Основные принципы выполнения сетей Петри 139
3.3.2 Определение критериев для оценки результатов теоретического анализа структуры алгоритма защиты от перегрузок 141
3.4 Теоретический анализ структуры алгоритма защиты от
перегрузок 145
3.5 Выводы 153
ГЛАВА 4. Экспериментальная оценка работоспособности и эффективности разработанного алгоритма защиты от перегрузок сетей ATM
4.1 Постановка задачи 154
4.2 Разработка имитационной модели фрагмента сети ATM 155
4.2.1 Определение ограничений, вводимых при имитационном моделировании фрагмента сети ATM 155
4.2.2 Разработка алгоритма имитационного моделирования фрагмента сети ATM 158
4.2.3 Разработка программы алгоритма имитационного моделирования фрагмента сети ATM 165
4.3 Экспериментальная оценка работоспособности и эффективности алгоритма защиты от перегрузок 169
4.3.1 Выбор вариантов и определение исходных данных имитационного моделирования фрагмента сети ATM 169
4.3.2 Определение параметров экспериментальной оценки работоспособности и эффективности разработанного алгоритма
4.3.3 Имитационное моделирование фрагмента сети ATM 182
4.3.4 Анализ результатов имитационного моделирования фрагмента сети ATM и экспериментальная оценка работоспособности и эффективности разработанного алгоритма 201
4.4 Выводы 218
Заключение 220
Список литературы
- Анализ алгоритмов с превентивным методом защиты от перегрузок
- Разработка алгоритма с функцией защиты от перерезервирования или недоиспользования полосы пропускания виртуального канала
- Разработка Процедуры теоретического анализа структуры алгоритма защиты от перегрузок
- Экспериментальная оценка работоспособности и эффективности алгоритма защиты от перегрузок
Анализ алгоритмов с превентивным методом защиты от перегрузок
В соответствии с поставленными задачами тема диссертации освещается по главам в следующем порядке.
В первой главе исследовано состояние проблемы защиты от перегрузок сетей ATM. Приведены статистические данные, полученные при наблюдениях за работой сети ATM в 1998-1999 г.г., которые показали, что существующие в сетях ATM неуправляемые источники трафика категории услуг ABR, то есть источники, не снижающие скорость передачи по требованию алгоритма защиты от перегрузок и источники, превышающие необходимую величину резервирования ресурсов сети для своего трафика, не используя при этом полученный избыток ресурсов, являются причиной: уменьшения ресурсов, доступных другим источникам; потери пропускной способности сети; несправедливого распределения и неэффективного использования полосы пропускания и наступления перегрузки. Как показали статистические данные, в среднем на сети ATM неуправляемые источники осуществляли перерезервирование 14,8% общей полосы пропускания, доступной источникам категории услуг ABR.
В данной главе исследована возможность существующих алгоритмов защитить сети ATM от перегрузок, вызванных неуправляемыми источниками. Для этого проведена классификация алгоритмов защиты от перегрузок сетей ATM, позволившая систематизировать исследования алгоритмов. В качестве признаков классификации алгоритмов защиты от перегрузок были приняты метод защиты и используемая модель. Проведенная классификация показала, что 79% исследованных алгоритмов базируются на реактивном методе защиты и 21%) алгоритмов базируется на превентивном методе защиты. Среди алгоритмов, базирующихся на реактивном методе, 64% используют скоростную модель и 36% используют кредитную модель. На основе классификации проведено исследование возможности существующих алгоритмов обеспечить защиту от перегрузок, вызванных неуправляемыми источниками категории услуг ABR. По результатам анализа сделаны следующие выводы: существующие алгоритмы не защищают сети ATM от перегрузок, вызванных неуправляемыми источниками и переполнением буферных накопителей коммутаторов ATM; разрабатываемые алгоритмы защиты от перегрузок должны базироваться на реактивном методе защиты и скоростной модели, поддерживать функцию справедливого распределения полосы пропускания между активными источниками категории услуг ABR, использовать процедуры превентивного метода защиты, обеспечивающие контроль трафика по длине очереди в буферных накопителях коммутаторов ATM и выборочное уничтожение ячеек с заданной вероятностью.
Во второй главе разработан алгоритм защиты от перегрузок, который обеспечивает защиту сетей ATM от перегрузок, вызванных неуправляемыми источниками и переполнением буферных накопителей коммутаторов ATM. Разработанный алгоритм базируется на реактивном методе защиты и скоростной модели, поддерживает функцию справедливого распределения полосы пропускания между активными источниками категории услуг ABR, использует процедуры превентивного метода защиты, обеспечивающие контроль трафика по длине очереди в буферных накопителях коммутаторов ATM и выборочное уничтожение ячеек с заданной вероятностью. В качестве контролируемого параметра и в качестве критерия переключения режимов работы алгоритма защиты от перегрузок принята средняя длина очереди в коммутаторе ATM. В качестве управляющего параметра алгоритма защиты от перегрузок принята допустимая скорость передачи по виртуальному каналу. Для расчета допустимой скорости передачи по виртуальному каналу выведена формула, отличающаяся от известных тем, что учитывает не только величину полосы пропускания, доступной источникам категории услуг ABR, но и длину очереди в буферных накопителях коммутатора ATM.
В третьей главе проведен теоретический анализ структуры разработанного алгоритма защиты от перегрузок. При разработке нового алгоритма возможно появление ошибок в его структуре в виде тупиковых и пассивных ветвей, что приводит к «зависаниям» программы алгоритма и снижает оптимальность его построения и функционирования. Для выявления и исключения пассивных и тупиковых ветвей разработана Процедура теоретического анализа структуры алгоритма защиты от перегрузок сетей ATM (Алгоритма), в основе которой лежит построение двудольного ориентированного мультиграфа сети Петри, являющегося математической моделью разработанного алгоритма. Определены критерии для оценки результатов теоретического анализа структуры алгоритма защиты от перегрузок, в качестве которых используются такие свойства сетей Петри, как сохраняемость, безопасность, ограниченность, достижимость и активность. Доказано отсутствие в структуре разработанного алгоритма защиты от перегрузок тупиковых и пассивных ветвей.
Разработка алгоритма с функцией защиты от перерезервирования или недоиспользования полосы пропускания виртуального канала
Режим предупреждения перегрузок реализуется первым функциональным модулем Алгоритма, который базируется на скоростной модели с петлей обратной связи. Диаграмма процесса данного модуля, разработанная на основе раздела 2.2.2, представлена на рисунке 2.3.
Как уже говорилось, источники трафика категории услуг ABR периодически сканируют установленное соединение на предмет наличия требуемой полосы пропускания. Для этого, через каждые 100 мкс или 31 ячейку данных передается специальная служебная ячейка RM, которая несет в себе величину желаемой скорости передачи ER (Explicit Rate) по данному виртуальному каналу.
Алгоритм IERCA каждого коммутатора ATM рассчитывает свою величину ERa, исходя из наличия свободных ресурсов и принципа справедливого распределения полосы между источниками, которая в последствии и будет использоваться источниками нагрузки. Процедура расчета величины ERa должна работать следующим образом:
Для каждого интервала времени ts Алгоритм рассчитывает скорость работы Ri(t)vc.abr для категории услуг ABR по каждому (i=l,N) виртуальному каналу, проходящему через коммутатор ATM.
Для этого подсчитывается количество ячеек Nvc, поступивших по данному виртуальному каналу за интервал времени ts: где MCR - минимальная скорость передачи по виртуальному каналу. Далее определяется количество активных источников нагрузки категории услуг ABR - Nact, как количество виртуальных каналов ABR, по которым идет передача трафика через данный коммутатор ATM в интервале измерения ts.
Для определения изначально свободных ресурсов для виртуальных каналов ABR на данном коммутаторе ATM включается процедура расчета так называемой емкости ABR - Bmax-ahr, исходя из значения которой, будут распределяться свободные ресурсы между источниками нагрузки.
Емкость ABR рассчитывается как общее количество ресурсов Rmax коммутатора ATM, определяемое, как правило, структурой и мощностью Пропускания Rchr,vbr зарезервированной более приоритетными источниками категории услуг CBR и VBR: Bmax.abr -тах -K-cbr,vbr- У -- ) Для гарантии неблокируемости коммутатора ATM на случай неожиданных всплесков нагрузки, вызванной, например, одновременным увеличением активности источников, имеет смысл предусмотреть введение процедуры статистического резервирования некоторого процента полосы пропускания К%, который обеспечит передачу пульсирующего трафика. Здесь К - процент допустимой загрузки, определяемый оператором связи, как правило, лежит в диапазоне 90%-95%.
Под одновременным увеличением активности источников, прежде всего, имеются в виду источники категории услуг VBR, имеющие более высокий приоритет. Изменение активности источников YBR может привести к существенным изменениям в текущем распределении ресурсов коммутатора ATM. Для большей устойчивости к подобным ситуациям и резервируется некоторый процент полосы пропускания К%, способный вобрать в себя часть трафика до того, как Алгоритм перераспределит ресурсы для трафика категории услуг ABR. Исходя из вышесказанного, емкость ABR должна вычисляться по следующей формуле: Втъх.аЬг = (7? max- Rcbr,vbr) X К%. (2-4) Для определения текущей загрузки коммутатора ATM Z(t) вычисляется суммарная скорость категории услуг ABR - R(t)BX.abr, как сумма всей нагрузки категории услуг ABR, поступающей по всем виртуальным каналам на данный коммутатор ATM в интервале измерения ts.
Способность алгоритма отслеживать текущую загрузку коммутатора ATM является ключевым моментом в работе Алгоритма. Именно исходя из коэффициента загрузки Z(t), в дальнейшем рассчитывается распределение полосы пропускания между виртуальными каналами.
По величине загрузки Z(t) можно оценить уровень перегрузки в виртуальном канале. Высокий уровень загрузки коммутатора ATM говорит о его функционировании на грани перегрузки, низкий уровень загрузки является показателем неэффективного использования каналов. Наиболее оптимально коммутатор ATM функционирует при загрузке
Далее должна включаться процедура расчета справедливой доли полосы пропускания Bfs (Fair Share), которая может быть предоставлена каждому виртуальному каналу ABR исходя из того, что каждому источнику достанется равная часть от общих ресурсов. Справедливая доля полосы пропускания Bfs рассчитывается как: где Nact - количество активных виртуальных каналов Фактически, параметр Bfs представляет собой равную долю общей полосы пропускания Втахаьг, на которую теоретически может претендовать каждый виртуальный канал.
Таким образом, коммутатор ATM позволяет источникам работать в полосе пропускания Bfs, информируя источник каждый раз о величине доступной полосы пропускания, тем самым предоставляя всем источникам равные возможности.
Однако не всякий источник нуждается в полосе пропускания Bfs в данный момент времени.
Если источник не использует всю полосу пропускания Bfs, то Алгоритм включает процедуру перераспределения освободившейся полосы пропускания между остальными источниками. Для этой цели, исходя из реальной ситуации в сети, производится расчет доли полосы пропускания, выраженной через скорость, для каждого виртуального канала Ri(t)vcshare: Ri(t)vc.abr Ki{ t)vc.share = , (7. К) Z{t) K } где Ri(t)vcabr - текущая скорость данного виртуального канала. Параметр Ri(t)vcshare учитывает реальную загрузку коммутатора ATM, а также долю данного виртуального канала в загрузке коммутатора.
Если все виртуальные каналы ABR приведут свою скорость передачи в соответствие с параметром Ri(t)vcshare, то при следующем временном интервале расчета параметров коэффициент загрузки будет равен единице. Таким образом, с помощью параметра Ri(t)vcshare определяющего скорость для каждого виртуального канала, Алгоритм стремится привести сеть ATM к эффективному, но не обязательно справедливому распределению полосы пропускания для каждого виртуального канала.
С помощью параметра Bfs, определяющего справедливую долю полосы пропускания для каждого виртуального канала, Алгоритм распределяет полосу справедливо, но не всегда наиболее эффективно.
Применение обоих параметров позволяет Алгоритму построить устойчивую, оптимально работающую систему для расчета допустимой скорости передачи ERa (Explicit Rate) по виртуальному каналу.
Разработка Процедуры теоретического анализа структуры алгоритма защиты от перегрузок
Функциональная схема алгоритма моделирования 3-его из четырех последовательно включенных коммутаторов ATM фрагмента сети ATM. давая Алгоритму, реализованному в блоке коммутатор ATM , возможность стабилизироваться. Линейное изменение скорости происходит постепенно и однократно. За это время происходит несколько итераций процесса моделирования, и другие генераторы трафика могут многократно менять скорость передачи.
Данная модель генерирует трафик только с постоянной скоростью Итен. Скорость Яген определяется заранее и может быть разной для каждого из четырех источников. Третья модель - Генератор трафика 3 - работает с одним источником: ABR 5. Источник ABR5 заказывает переменную скорость передачи Язак, которая изменяется случайным образом в установленном диапазоне. Эту величину заказанной скорости передачи Язак источник с помощью петли обратной связи передает генератору трафика, в соответствие с которой генератор трафика 3 устанавливает свою скорость передачи Итен в следующей итерации процесса моделирования.
Начальная скорость RreH для первой итерации процесса моделирования может быть выбрана как случайное значение.
На рисунке 4.1 представлены шесть источников трафика. Первый источник VBR - источник приоритетного трафика. Второй и третий источники ABR1, ABR2 являются неуправляемыми источниками. Четвертый, пятый и шестой источники: ABR3, ABR4, ABR5 - нормально управляемые источники, подчиняющиеся указаниям Алгоритма.
Источник VBR - является источником с переменной скоростью работы, трафик которого является абсолютно приоритетным по отношению ко всем остальным источникам. Его трафик не может уничтожаться и скорость его работы не контролируется Алгоритмом. Таким образом, текущая скорость на выходе источника VBR - Ятек всегда полностью определяется входящей скоростью Яген от генератора трафика 1: RTeK=RreH.
Второй и третий источники - ABR1, ABR2. Источники ABR1, ABR2 являются неуправляемыми источниками. Их работа учитывается, но не управляется Алгоритмом. Текущая скорость их работы RTeK постоянна и равняется скорости RreH Генератора трафика 2 : RTeK = RreH.
При этом текущая скорость работы RTeK источника ABR1 может отличаться от RTCK источника ABR2.
Кроме генерации трафика источники ABR заказывают некоторую скорость R3aK, с которой они хотели бы работать в следующий интервал времени. По умолчанию для всех источников ABR значение R3aK должно совпадать со скоростью генератора трафика: R3aK = RreH. Но для неуправляемых источников R3aK может отличаться от значения RreH и RTCK и иметь некоторое значение, задаваемое перед запуском процесса моделирования. Четвертый и пятый источники ABR3, ABR4. Данные источники нагрузки являются источниками, управляемыми Алгоритмом и, следовательно, к них кроме скорости от генератора RreH поступают еще значения скорости Raлг, рассчитанные Алгоритмом для каждого из них.
Значение текущей скорости RTeK, устанавливаемое каждым источником, определяется, как минимальное значение между RreH и Raлг: RreK = min (RreH, Raлг), а значение заказанной скорости R3aK всегда равняется скорости генератора RreH: R3aK = RreH. Шестой источник ABR5. Шестой источник также является управляемым и его текущая скорость RTCK определяется работой Алгоритма: RTCK = min (RreH, Raлг). Отличие источника ABR5, который является источником со случайной скоростью передачи, состоит в том, что скорость заказа R3aK определяется случайным образом в заданном диапазоне с помощью генератора случайных чисел. При этом скорость Генератора трафика 3 -RreH принимается равной скорости R3aK, заказанной в предыдущей итерации процесса моделирования.
Таким образом осуществляется обратная связь между источником ABR5 и Генератором трафика 3, определяющая, какую скорость RreH генератор должен выдавать в последующей итерации процесса моделирования.
В этом модуле реализован собственно Алгоритм, основной задачей которого является расчет скорости Ranr для каждого источника ABR: ABRl, ABR2, ABR3, ABR4, ABR5. При этом Алгоритм имеет возможность управлять только источниками ABR3, ABR4, ABR5. Для неуправляемых источников ABRl, ABR2 Алгоритм имеет возможность блокировать/уменьшать поступающий от них трафик RTCK.
Для расчета скорости Raлг для каждого источника выполняются следующие процедуры с использованием формул главы 2:
Вычисляется пропускная способность коммутатора доступная источникам ABR - Bmax.abr, как пропускная способность коммутатора Rmax, величина которой задается в качестве исходных данных, минус текущая скорость источника VBR- RTeK (VBR):
Экспериментальная оценка работоспособности и эффективности алгоритма защиты от перегрузок
При этом, коэффициент использования полосы пропускания Кисп = 0,83. Таким образом, из-за перерезервирования полосы пропускания источниками ABR1 и ABR2 в случае, когда Алгоритм не защищает сеть ATM от таких источников, недоиспользуется 17% полосы пропускания.
Результаты пятнадцатого варианта представлены на рисунке 4.18. Алгоритм IERCA работал с включением всех функций защиты от перегрузок и, следовательно, проводил сравнение значения текущей скорости источника и скорости, установленной данному источнику при предыдущей итерации Алгоритма. Обнаружив перерезервирование, осуществленное источниками ABR1 и ABR2, алгоритм IERCA ликвидировал перерезервирование и снизил их скорость до минимальной (ICR). Освободившуюся полосу пропускания Алгоритм разделил между всеми остальными управляемыми источниками ABR3, ABR4, ABR5. В результате, всем управляемым источникам досталась равная доля полосы пропускания по 30 Мбит/с каждому источнику: Однако, вследствие того, что источник ABR3 требует всего 25 Мбит/с, освободившиеся 5 Мбит/с были отданы источнику ABR5, скорость передачи которого стала 35 Мбит/с . При этом, коэффициент использования полосы пропускания Кисп достиг 1. Алгоритм IERCA выполняет функции защиты от перегрузок.
Результаты шестнадцатого варианта представлены на рисунке 4.19. Как следует из графиков, из-за того, что алгоритм IERCA в данном варианте работает в режиме алгоритма ERICA и не реагирует на поведение источников ABR1 и ABR2, перерезервировавших полосу пропускания виртуальных каналов, ухудшается распределение полосы пропускания для управляемых источников ABR3, ABR4, ABR5: RxeK(ABR3, ABR4, ABR5) = Rmax- RTeK(VBR) - RxeK(ABRl) - R3aK(ABR2) _ Как и в XIV варианте, Алгоритм при вычислении скорости передачи источников ABR3, ABR4, ABR5 использует значение R3aK ABR2 вместо RTCKABR2, поскольку источник ABR2 осуществляет перерезервирование полосы пропускания виртуального канала.
Коэффициент справедливого распределения полосы пропускания Кср = 0,96. Коэффициент использования полосы пропускания Кисп = 0,93.
Следовательно, из-за того, что Алгоритм работал только в режиме предупреждения перегрузок, как и применяемые в сетях ATM алгоритмы защиты от перегрузок, справедливого распределения полосы пропускания и эффективного использования ресурсов не достигается.
Результаты семнадцатого варианта представлены на рисунке 4.20. Как следует из рис. 4.20, алгоритм IERCA снизил скорость источников ABR1 и ABR2 до ICR = 5 Мбит/с. Источник ABR2 был определен сразу, путем сравнения его текущей скорости работы и скорости, рассчитанной для него на предыдущей итерации Алгоритма. Снижение скорости источника ABR1 произошло только на 60-ой итерации, когда возникла перегрузка вследствие увеличения активности источника VBR. Тогда Алгоритм перераспределил освободившуюся полосу пропускания между управляемыми источниками:
Подсчитав по формулам 4.4 и 4.5 коэффициент справедливого распределения полосы пропускания между источниками ABR3, ABR4, ABR5 и коэффициент использования полосы пропускания, получаем: Кср = 1, Кисп - 1. За счет выполнения Алгоритмом функций защиты от перегрузок, скорость источников ABR3, ABR4, ABR5 возросла с 15 Мбит/с до 25 Мбит/с. При этом, использование полосы пропускания достигло 100%. Алгоритм IERCA выполняет функции защиты от перегрузок.
Таким образом, анализ результатов имитационного моделирования показал, что существующие алгоритмы защиты от перегрузок не способны защитить сети ATM от неуправляемых источников. При наличии в сети таких источников, существующие алгоритмы защиты от перегрузок не в состоянии обеспечить справедливое распределение полосы пропускания (Кср) и высокое использование полосы пропускания (Кисп). Среднее значение Кср составляет величину порядка 0,775, а Кисп - 0,88.
В то же время, разработанный алгоритм IERCA выполняет все возложенные на него функции и защищает сети ATM от перегрузок, вызванных наличием неуправляемых источников и переполнением буферных накопителей коммутаторов ATM. Коэффициент справедливого распределения полосы пропускания Кср и коэффициент использования полосы пропускания Кисп достигают значения 1. Отсюда следует вывод о работоспособности разработанного алгоритма IERCA.
Анализ результатов имитационного моделирования позволяет сделать следующие выводы. Разработанный алгоритм IERCA более эффективен, чем один из наиболее эффективных из существующих алгоритмов защиты от перегрузок - алгоритм ERICA. Эффективность разработанного алгоритма возрастает с увеличением величины полосы пропускания, занимаемой неуправляемыми источниками. Оценка эффективности разработанного алгоритма Эалг в зависимости от величины полосы пропускания, занимаемой неуправляемыми источниками представлена в таблице 4.20.
