Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 7.5.9 Анализ подходов к реализации общих требованийПотоковые модели весьма плохо приспособлены к алгоритмам динамической маршрутизации ATM сетей вследствие следующих причин: • во-первых, общих особенностей динамической маршрутизации (необходимости вычисления маршрута для каждой вновь поступающей заявки); • во-вторых, специфических особенностей ATM сетей по сравнению с классическими сетями (наличием динамического алгоритма САС, вычисляющего текущие параметры линий после установки и разъединения каждого соединения, требованиями по QoS параметрам, несимметричностью требований в прямом и обратном направлении и т.д.). В связи с этим далее в качестве основы для разработки конкретных алгоритмов будут рассматриваться только алгоритмы кратчайшего пути, которые, в свою очередь, имеют много конкретных реализаций [6] - «Беллмана-Форда», «Дийкстра», «Флойда-Уоршела» и др. В соответствие с изложенными в разделе 7.5.5 требованиями, в настоящем разделе последовательно рассмотрим подходы к их реализации в части учета различных параметров трафика, QoS параметров и общесистемных показателей. Учет параметров трафикаДанный учет производится алгоритмом GCAC до вычисления требуемого маршрута и его целью является предварительная проверка всех линий сети на предмет удовлетворения требований в части параметров трафика. Согласно [133], GCAC учитывает следующие параметры линий (j - номер проверяемой линии) - для всех категорий обслуживания;
Для категории CBR в PNNI [133] используется GCAC в самом простейшем виде - если для текущей заявки удовлетворяется неравенство Для VBR-заявок используется более сложный подход. Обозначим:
Основным допущении, принятым в ходе разработки GCAC [133], является следующее: Для успешной установки (впоследствии, после отработки GCAC) текущего,
После простых преобразований приходим к необходимости выполнения следующего неравенства:
Подчеркнем еще раз, что параметры Критерием «существенности» изменения служит величина AvCR_PM - предельный процент изменения параметра линии AvCR по сравнению со значением, распространяемым по сети в последний раз. Выбор оптимальных значений величины AvCR_PM (как, впрочем, и всех остальных управляемых параметров маршрутизации) производится на основе имитационного моделирования процесса работы сети на уровне установки-разъединения соединений. Все вышеприведенное касалось алгоритма GCAC для ATM сети с полностью распределенным управлением, т.е. обеспечивающего выбор маршрута в узле-источнике соединения и установку коммутируемого виртуального соединения (SVC) на основе использования механизма сигналлинга. При использовании других подходов реализация GCAC может сильно отличаться: • При использовании полностью централизованного управления и выбор, и установка постоянного виртуального соединения (PVC) происходит на основе менеджмента ATM сети. В этом случае центральный узел имеет по каждой линии детальную статистику в части каждого проходящего по ней соединения (и параметры трафика, и значение выделенной ему алгоритмом САС эквивалентной пропускной способности) и поэтому может использовать эти параметры для определения среднестатистических приведенных отношений. • При использовании комбинированного способа управления выбор маршрута производится централизованно, а установка соединения - на основе механизма сигналлинга. В связи с этим GCAC может использовать детальную информацию о параметрах трафика соединений, проходящих по каждой линии (PCR, SCR), но в части выделенной им алгоритмом САС эки-валентной пропускной способности может использовать лишь интегральные характеристики по всем соединениям (AvCR, CRM,...). Для данного способа применение модифицированного алгоритма GCAC для категории обслуживания CBR не требует дополнительных накладных расходов, связанных с распространением информации по сети, и сводится лишь к проверке неравенства
В заключение отметим, что использование алгоритма CGAC в распределенных ATM сетях не является бесспорным - так, например, в [231] подчеркивается, что периодическое распространение по сети значений динамических параметров чрезмерно загружает сеть и предлагается проверять линии на наличие необходимого количества пропускной способности непосредственно в ходе установки соединения. Учет параметров качества обслуживанияПроверка маршрута на предмет удовлетворения QoS параметров заявки может производится до выбора маршрута, в процессе выбора или после выбора. В части параметра CLR проблем не возникает - проверка линий производится, аналогично алгоритму GCAC, до выбора маршрута и обычно все линии удовлетворяют требованию заявки, т. к. эти требования, как правило, находятся в пределах Проверку QoS параметров End-to-EndCDV и End-to-EndMaxCTD также возможно осуществлять до выбора маршрута путем определения для него предельно допустимых параметров линий в части CDV и MaxCTD соответственно выражениями • Все линии сети одинаковы с точки зрения параметров CDV и MaxCTD; • Количество линий в любом маршруте (длина маршрута) ограниченно некоторой заранее заданной величиной Практически использование первого допущения сильно ухудшает качество маршрутизации, т. к. если значения параметра CDV и могут быть одинаковы для всех линий (в случае их однотипности), то значения параметра Второе же допущение не позволяет использовать «слабые» линии даже в очень коротких маршрутах С другой стороны, проверять QoS параметры только после выбора маршрута также неэффективно, т. к. это значительно увеличивает суммарное время маршрутизации в случае необходимости многократного последовательного выбора. В принципе наиболее эффективен, естественно, третий путь - проверять End-to-End QoS параметры маршрута непосредственно в ходе его выбора [214,243,256,266]. Практическое использование этого подхода осложняется тем, что по своей сути алгоритмы кратчайшего пути решают лишь задачу однокритериальной оптимизации без ограничений, т.е. позволяют минимизировать один выходной критерий, являющийся суммой параметров входящих в маршрут линий. Этим критерием может быть длина маршрута («количество прыжков»), сумма административных весов, суммарное время передачи - I_MaxCTD (сумма параметров линий MaxCTD), суммарный разброс в передаче - I_CDV (сумма параметров линий CDV) и т.д. Точный поиск кратчайшего пути по одному из критериев (например, по длине маршрута) при учете ограничений по другим критериям (I_MaxCTD и I_CDV) превращает задачу в проблему NP-сложности (см., например, [193]). Для приближенного решения задачи наиболее естественным представляется свернуть и выходной критерий, и ограничения, в единый критерий. Эту свертку можно производить различными способами (аддитивно, мультипликативно, с зависимыми от линий весами или как-то иначе), но наиболее просто использовать линейно-аддитивное взвешивание. В этом случае обобщенная стоимость линии j может определяться, например, по формуле
где относительные веса важности отдельных критериев {ImpAW, ImpCDV, ImpMaxCTD) являются одинаковыми для всех линий сети в процессе очередного поиска кратчайшего пути, но итеративно меняются до тех пор, пока поиск не увенчается успехом. Исходя из того, что параметры AWfj] входят в критерий оптимизации маршрута, а параметры CDV[j] и MaxCTD[j] - лишь в ограничения на маршрут, естественно начинать поиск со значений Можно предложить различные варианты реализаций данного подхода (с постоянным или переменным шагом приращения весов важности, на основе простых вложенных циклов приращения по отдельным критериям или на основе определения оптимального текущего направления приращения и т.д.), но рекомендации по целесообразности той или иной реализации могут быть даны только на основе имитационного моделирования работы алгоритма применительно к конкретным условиям. Приведенный выше метод не всегда обеспечивает успешный поиск маршрута, удовлетворяющего ограничениям по QoS параметрам, даже если такой маршрут в действительности существует. Для гарантированного поиска существующего маршрута (без учета требования по минимизации длины маршрута в аспекте критерия административных весов) разработано много алгоритмов, в основе которых лежит подход «доминантных маршрутов» в сочетании с поиском
где параметр q стремится к бесконечности. В предельном случае стоимость маршрута идеально соответствует требованиям-ограничениям QoS параметров, но уже не является аддитивно-степенной:
Пользуясь случаем, еще раз подчеркнем, что если требования по QoS параметру CDV отличаются для прямого и обратного направления соединения, и значения параметра линии CDVjj] отличается от значения CDV линии противоположного направления, необходимо учитывать два ограничения по End-to-End_CDV (E_CDV для прямого и для обратного направлений). Для поиска маршрута В свою очередь, чтобы сократить количество хранимых промежуточных маршрутов, используют подход «доминантных маршрутов». Маршрут называется доминантным по отношению к другому (имеющему те же источник и адресат), если он характеризуется меньшими значениями всех отдельных компонент стоимости (в соответствие с выражением (7.54)). Очевидно, что в промежуточных узлах в процессе поиска маршрута в соответствие с (7.54), хранить стоит только недоминантные маршруты. В заключение подчеркнем, что рассмотренный подход в любом случае характеризуется достаточно большой трудоемкостью и к тому же никак не учитывает требования по оптимизации выходных критериев эффективности маршрута (в части административных весов, баланса пропускной способности и т.д.), поэтому применять его рекомендуется только в крайнем случае, при необходимости безусловного поиска маршрута для особо приоритетных заявок. Учет общесистемных требований.Как уже отмечалось в предыдущем разделе, в алгоритмах кратчайшего пути невозможно использовать глобальные критерии эффективности сети. Вместо этого приходится применять локальные критерии, оптимизирующие лишь текущий маршрут. Основными из этих критериев являются показатель-метрика административных весов (7.44) и показатели баланса пропускной способности (7.45)-(7.49). Интуитивно очевидно, что использование в качестве стоимостей линий величин, отражающих степень текущей загруженности линий, снижает вероятность блокировки заявки вследствие нехватки требуемой пропускной способности. В [6] подробно обсуждаются возникающие при этом проблемы колебаний и устойчивости, и при этом подчеркивается, что они проявляются наиболее сильно в дейтаграммных сетях, в сетях же с виртуальными цепями (а тем более ATM сетях, ориентированных на более-менее долговременную установку соединения) такая опасность весьма несущественна. Использование в алгоритмах кратчайшего пути в качестве критерия оптимизации лишь выражений типа (7.45)-(7.47) представляется невозможным, так как так или иначе в процессе маршрутизации необходимо учесть и показатели-метрики административных весов (7.44), и показатели «баланса в отличиях маршрутов» (7.50)-(7.51), и ограничения по QoS параметрам. Аналогично предыдущему разделу, наиболее просто учесть все показатели и ограничения в одном критерии можно путем их линейно-аддитивной свертки. В качестве примера можно использовать следующую формулу:
где: W[j] - обобщенная стоимость линии - относительные веса важности отдельных критериев-метрик; это статические (управляемые) параметры, их значения не меняются в процессе маршрутизации и определяются путем оптимизации глобальных показателей сети на основе ее имитационного моделирования; mpQS, ImpCDV, ImpCTD - относительные веса важности параметров-ограничений (QoS параметров); это динамические (вспомогательные) параметры, их значения итеративно меняются в ходе поиска маршрута начиная с Естественно, что простая свертка нескольких критериев в один не позволяет осуществлять эффективную многокритериальную оптимизацию выбора маршрута. В качестве альтернативных вариантов можно предложить более точные, но одновременно и более трудоемкие, алгоритмы. В целях упрощения изложения материала рассмотрим одновременный учет лишь двух критериев - «административных весов» и «баланса пропускной способности». В качестве статического, управляемого параметра вместо относительных весов важности будем использовать • DevWG - максимально допустимое относительное отклонение значение критерия-метрики административных весов WG (см. формулу (7.45)) от своего локально-оптимального (без учета требования баланса пропускных способностей) значения. В качестве динамического, итеративно изменяемого параметра введем следующий параметр (использование которого и определяет существенное повышение трудоемкости по сравнению с алгоритмом свертки), общий для всех линий сети • LimAvCR- граничное относительное (по отношению к параметру MCR[j]) значение параметра AvCR[j], допустимое к использованию на очередном шаге текущего процесса маршрутизации. Для формального описания алгоритма введем дополнительные понятия - модифицированный административный вес линии
В целях упрощения перенумеруем все
Следующие утверждения очевидны: 1. Кратчайший путь 2. Функция 3. Для критериев-атрибутов «баланса пропускной способности» (7.48) или (7.49) функция Последние два утверждения принципиально позволяют найти седловую точку двухкритериальной задачи, а первое - резко снизить трудоемкость такого поиска. Суть работы алгоритма состоит в следующем: 1. На предварительной стадии находим безусловный кратчайший путь по критерию административных весов (7.44), т.е. соответствующий значению 2. На основной стадии, начиная с
Рассмотренные подходы к учету требований по балансу пропускных способностей различных линий по своей сути предполагают двухэтапную процедуру: • На этапе инженерного анализа сети, в режиме off-line, используя имеющуюся (или предполагаемую) статистическую информацию о параметрах входного потока заявок, осуществляется моделирование работы алгоритма маршрутизации и определяются искомые значения управляемых параметров (ImpAW, ImpBW, ImpDIV или DevWG и др.) с целью оптимизации и-или ограничения значений некоторых глобальных показателей эффективности сети. • На этапе функционирования сети, в режиме on-line, осуществляется динамическая маршрутизация поступающих заявок с целью оптимизации критериев эффективности лишь текущего маршрута, на основе использования ранее выбранных значений управляемых параметров. В ситуации, когда первый этап невозможен (например, статистика входного потока недоступна) в [141,258,264] предлагаются алгоритмы конкурирующей маршрутизации, которые обеспечивают оптимизацию определенных глобальных показателей сети для достаточно широкого диапазона возможного изменения входного трафика. Отметим, что подобного рода вопросы (обеспечение влияния алгоритмов кратчайшего пути на показатели эффективности не только текущего маршрута, но и всей сети в целом) впервые рассматривались еще в [191]. Предложенные в [141,258,264] алгоритмы позволяют оптимизировать выходные показатели «среднее количество отказов» или «средняя загрузка пропускной способности сети». Применительно к ранее введенным обозначениям стоимости линий (а в качестве непосредственно методов динамической маршрутизации также используются алгоритмы кратчайшего пути) задаются, например, в виде
|
1 |
Оглавление
|