7.5.9 Анализ подходов к реализации общих требований

Потоковые модели весьма плохо приспособлены к алгоритмам динамической маршрутизации ATM сетей вследствие следующих причин:

• во-первых, общих особенностей динамической маршрутизации (необходимости вычисления маршрута для каждой вновь поступающей заявки);

• во-вторых, специфических особенностей ATM сетей по сравнению с классическими сетями (наличием динамического алгоритма САС, вычисляющего текущие параметры линий после установки и разъединения каждого соединения, требованиями по QoS параметрам, несимметричностью требований в прямом и обратном направлении и т.д.).

В связи с этим далее в качестве основы для разработки конкретных алгоритмов будут рассматриваться только алгоритмы кратчайшего пути, которые, в свою очередь, имеют много конкретных реализаций [6] - «Беллмана-Форда», «Дийкстра», «Флойда-Уоршела» и др. В соответствие с изложенными в разделе 7.5.5 требованиями, в настоящем разделе последовательно рассмотрим подходы к их реализации в части учета различных параметров трафика, QoS параметров и общесистемных показателей.

Учет параметров трафика

Данный учет производится алгоритмом GCAC до вычисления требуемого маршрута и его целью является предварительная проверка всех линий сети на предмет удовлетворения требований в части параметров трафика. Согласно [133], GCAC учитывает следующие параметры линий (j - номер проверяемой линии)

- для всех категорий обслуживания;

- для категорий обслуживания -VBR и -VBR.

Для категории CBR в PNNI [133] используется GCAC в самом простейшем виде - если для текущей заявки удовлетворяется неравенство линия j включается в список приемлемых для выбираемого маршрута, в противном случае линия не включается в него. В [259] показано, что именно в силу своей простоты этот алгоритм может приводить к неоправданному увеличению количества отказов на этапе непосредственно установки соединения, т.е. в ходе работы алгоритма САС. В этой связи вместо величины PCR с параметром более целесообразно сравнивать ее модифицированное значение. Модификация может производится путем умножения PCR на среднестатистическое приведенное (по отношению к PCR) значение эквивалентной пропускной способности, выделяемой по линии j алгоритмом САС заявкам данной категории обслуживания. Отметим сразу, что такой подход опять же увеличивает количество параметров линий, распространяемых по сети, и тем самым повышает ее накладные расходы.

Для VBR-заявок используется более сложный подход. Обозначим:

- общее количество соединений данной категории обслуживания, уже проходящих по линии

- суммарное значение эквивалентной пропускной способности, отведенной алгоритмом САС всем соединениям данной категории обслуживания, проходящим по линии

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

Основным допущении, принятым в ходе разработки GCAC [133], является следующее: для данной линии т.е. параметр «вариация пропускной способности» изменяется достаточно медленно.

Для успешной установки (впоследствии, после отработки GCAC) текущего, соединения по линии j необходимо, чтобы значение выделенной ему алгоритмом САС эквивалентной пропускной способности было бы не больше, чем . Исходя из этого получаем, что после установки должно выполняться условие

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

Подчеркнем еще раз, что параметры и CRM являются динамическими параметрами, они определяются после установки текущего соединения по каждой из входящих в маршрут линий. Параметры CRM и VF определяются просто путем арифметических операций, a AvCR вычисляется алгоритмом САС. С целью уменьшения загрузки сети накладными (служебными) расходами, распространение информации по всем узлам сети (потенциальным источникам заявок на установку соединений) о новых значениях динамических параметров происходит не после каждого их вычисления, а только в случае их «существенного» изменения.

Критерием «существенности» изменения служит величина AvCR_PM - предельный процент изменения параметра линии AvCR по сравнению со значением, распространяемым по сети в последний раз. Выбор оптимальных значений величины AvCR_PM (как, впрочем, и всех остальных управляемых параметров маршрутизации) производится на основе имитационного моделирования процесса работы сети на уровне установки-разъединения соединений.

Все вышеприведенное касалось алгоритма GCAC для ATM сети с полностью распределенным управлением, т.е. обеспечивающего выбор маршрута в узле-источнике соединения и установку коммутируемого виртуального соединения (SVC) на основе использования механизма сигналлинга. При использовании других подходов реализация GCAC может сильно отличаться:

• При использовании полностью централизованного управления и выбор, и установка постоянного виртуального соединения (PVC) происходит на основе менеджмента ATM сети. В этом случае центральный узел имеет по каждой линии детальную статистику в части каждого проходящего по ней соединения (и параметры трафика, и значение выделенной ему алгоритмом САС эквивалентной пропускной способности) и поэтому может использовать эти параметры для определения среднестатистических приведенных отношений.

• При использовании комбинированного способа управления выбор маршрута производится централизованно, а установка соединения - на основе механизма сигналлинга. В связи с этим GCAC может использовать детальную информацию о параметрах трафика соединений, проходящих по каждой линии (PCR, SCR), но в части выделенной им алгоритмом САС эки-валентной пропускной способности может использовать лишь интегральные характеристики по всем соединениям (AvCR, CRM,...). Для данного способа применение модифицированного алгоритма GCAC для категории обслуживания CBR не требует дополнительных накладных расходов, связанных с распространением информации по сети, и сводится лишь к проверке неравенства

В заключение отметим, что использование алгоритма CGAC в распределенных ATM сетях не является бесспорным - так, например, в [231] подчеркивается, что периодическое распространение по сети значений динамических параметров чрезмерно загружает сеть и предлагается проверять линии на наличие необходимого количества пропускной способности непосредственно в ходе установки соединения.

Учет параметров качества обслуживания

Проверка маршрута на предмет удовлетворения QoS параметров заявки может производится до выбора маршрута, в процессе выбора или после выбора. В части параметра CLR проблем не возникает - проверка линий производится, аналогично алгоритму GCAC, до выбора маршрута и обычно все линии удовлетворяют требованию заявки, т. к. эти требования, как правило, находятся в пределах а параметры-атрибуты линий CLR, независимо от их типа (см. таблицу 7.6), как правило равны В связи с этим проблема удовлетворения требованиям заявки в части CLR полностью переносится на САС, задачей которого и является вероятностный анализ стохастического процесса обслуживания ячеек в буферах входных и выходных линий узла.

Проверку 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 параметрам, даже если такой маршрут в действительности существует. Для гарантированного поиска существующего маршрута (без учета требования по минимизации длины маршрута в аспекте критерия административных весов) разработано много алгоритмов, в основе которых лежит подход «доминантных маршрутов» в сочетании с поиском короткого пути (вместо просто кратчайшего пути) [126,222,295]. Стоимость маршрута в этом случае вычисляется по аддитивно-степенной формуле:

где параметр q стремится к бесконечности. В предельном случае стоимость маршрута идеально соответствует требованиям-ограничениям QoS параметров, но уже не является аддитивно-степенной:

Пользуясь случаем, еще раз подчеркнем, что если требования по QoS параметру CDV отличаются для прямого и обратного направления соединения, и значения параметра линии CDVjj] отличается от значения CDV линии противоположного направления, необходимо учитывать два ограничения по End-to-End_CDV (E_CDV для прямого и для обратного направлений).

Для поиска маршрута , минимизирующего длину в соответствие с метрикой (7.54), достаточно в процессе применения алгоритма кратчайшего пути в каждом узле хранить не только текущий кратчайший путь, но и по значению короткий путь.

В свою очередь, чтобы сократить количество хранимых промежуточных маршрутов, используют подход «доминантных маршрутов». Маршрут называется доминантным по отношению к другому (имеющему те же источник и адресат), если он характеризуется меньшими значениями всех отдельных компонент стоимости (в соответствие с выражением (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], допустимое к использованию на очередном шаге текущего процесса маршрутизации.

Для формального описания алгоритма введем дополнительные понятия - модифицированный административный вес линии и критерий модифицированных административных весов :

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

Следующие утверждения очевидны:

1. Кратчайший путь остается неизменным и, соответственно, при изменении параметра в границах

2. Функция является монотонно неубывающей функцией по параметру

3. Для критериев-атрибутов «баланса пропускной способности» (7.48) или (7.49) функция соответствующая кратчайшим путям по длинам линий AW является монотонно невозрастающей функцией по параметру LimAvCR.

Последние два утверждения принципиально позволяют найти седловую точку двухкритериальной задачи, а первое - резко снизить трудоемкость такого поиска.

Суть работы алгоритма состоит в следующем:

1. На предварительной стадии находим безусловный кратчайший путь по критерию административных весов (7.44), т.е. соответствующий значению со значением целевой функции (7.44), равным

2. На основной стадии, начиная с находим кратчайший путь, соответствующий модифицированным административным весам (7.55) и критерию (7.56) со значением и итеративно уменьшаем на единицу, до тех пор, пока не выполнится неравенство

Рассмотренные подходы к учету требований по балансу пропускных способностей различных линий по своей сути предполагают двухэтапную процедуру:

• На этапе инженерного анализа сети, в режиме off-line, используя имеющуюся (или предполагаемую) статистическую информацию о параметрах входного потока заявок, осуществляется моделирование работы алгоритма маршрутизации и определяются искомые значения управляемых параметров (ImpAW, ImpBW, ImpDIV или DevWG и др.) с целью оптимизации и-или ограничения значений некоторых глобальных показателей эффективности сети.

• На этапе функционирования сети, в режиме on-line, осуществляется динамическая маршрутизация поступающих заявок с целью оптимизации критериев эффективности лишь текущего маршрута, на основе использования ранее выбранных значений управляемых параметров.

В ситуации, когда первый этап невозможен (например, статистика входного потока недоступна) в [141,258,264] предлагаются алгоритмы конкурирующей маршрутизации, которые обеспечивают оптимизацию определенных глобальных показателей сети для достаточно широкого диапазона возможного изменения входного трафика. Отметим, что подобного рода вопросы (обеспечение влияния алгоритмов кратчайшего пути на показатели эффективности не только текущего маршрута, но и всей сети в целом) впервые рассматривались еще в [191]. Предложенные в [141,258,264] алгоритмы позволяют оптимизировать выходные показатели «среднее количество отказов» или «средняя загрузка пропускной способности сети». Применительно к ранее введенным обозначениям стоимости линий (а в качестве непосредственно методов динамической маршрутизации также используются алгоритмы кратчайшего пути) задаются, например, в виде где L - некоторая константа, удовлетворяющая достаточно широкому диапазону допущений о работе сети (например, L может быть ограниченна максимальным количеством линий в маршрутах сети). Для различных видов выходных критериев и различных допущениях о характере заявок и соединений (например, неограниченное или ограниченное заданной величиной время пребывания соединения в сети) в упомянутых работах доказываются ряд утверждений, обеспечивающих асимптотическую оптимальность предложенных алгоритмов. В сугубо практическом плане использование этих подходов в алгоритмах динамической маршрутизации именно ATM сетей пока что недостаточно проработано, т.к. они не учитывают ограничения по QoS параметрам и не позволяют оценивать другие глобальные показатели сети.