7.5.11 Выбор оптимального алгоритма и значений его параметров

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

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

Анализ методов имитационого моделирования ATM сетей

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

Имитационное моделирование работы ATM сети на уровне установки-разрыва соединения можно осуществлять на основе следующих средств:

• Универсальных языков программирования (СИ, Паскаль и т.п.).

• Универсальных языков моделирования и обеспечивающих их программных средств - GPSS (см. [50]), SES (см. HTTP://www.ses.com_), ARENA (см. HTTP://www.sm.com ) и т.п.

• Специализированных средств моделирования, ориентированных на исследование именно вычислительных сетей - OPNET (см. HTTP://www.mil3.com ), BONES (см. HTTP://www.alta.com), C0MNET(cm. НТРР:// www.caciasl.com ) и др.

На первый взгляд, наиболее целесообразно использовать средства третьей группы, тем более во всех из них имеются специальные программные модули моделирования именно ATM сетей. Но, на наш взгляд, практически использование этих специализированных средств эффективно и оправданно только при анализе стандартных конфигураций и алгоритмов. Это объясняется тем, что специализированные программные системы моделирования вычислительных систем построены по иерархическому принципу.

При исследовании типовых конфигураций и алгоритмов в используемых модулях достаточно лишь изменить значения отдельных параметров - интенсивности поступления заявок, количества узлов и т.п. Такие изменения прозводятся на верхнем уровне описания модели и осуществляются очень быстро, практически без необходимости более-менее детального изучения работы используемой системы моделирования. При необходимости осуществления более глубоких изменений в используемой типовой модели (например, модифицировать типовую структуру узла ATM сети в части количества портов узла и схемы их коммутации) необходимо спуститься на следующий уровень описания модели, что требует более глубоких знаний в части применяемой системы моделирования. На самом нижнем уровне изменения производятся в части схем описания переходов между состояниями (State Transition Diagrams). Поэтому, хотя в специализированные системы моделирования и включены базовые средства маршрутизации (например, в системе OPNET есть средства статической распределенной маршрутизации на основе алгоритмов Беллмана-Форда, обеспечивающих поиск кратчайшего пути), модифицировать их с целью использования дополнительных возможностей достаточно непросто.

В недалеком прошлом наиболее широкоиспользуемым универсальным средством моделирования был язык GPSS, получивший свое начало более тридцати лет назад. Этот язык был реализован практически на всех ЭВМ - от IBM/360 и ЕС ЭВМ до ПЭВМ. Последние версии реализации этого языка на ПЭВМ позволяют эффективно использовать расширенную память, графический режим, меню, подсказки и другие особенности современных PC. Но принципиальные особенности GPSS (в первую очередь - реализация его в виде интерпретатора) не позволяют эффективно использовать его в сочетании с универсальными языками программирования. В связи с этим данный язык целесообразно использовать при моделировании непосредственно сетей массового обслуживания (и учете таких особенностей, как очереди, приоритеты, ресурсы и т.п.), но при необходимости учета «не стохастических» особенностей (например, описании и расчете алгоритмов кратчайшего пути) данный язык, на наш взгляд, недостаточно эффективен.

Ярким примером языка, позволяющим легко и гибко использовать средства универсальных языков программирования (а именно - СИ++) непосредственно в теле программы моделирования, является SES. Большая часть операторов СИ++ встроена в язык SES, поэтому в отличие от GPSS, в котором обращение к подпрограммам на универсальных языках осуществляется посредством оператора CALL, программы на SES позволяют легко реализовывать алгоритмы кратчайшего пути, алгоритмы GCAC и прочие рассмотренные выше подходы. В связи с этим при моделировании алгоритмов маршрутизации ATM сетей использовалось именно средство SES.

Пример моделирования алгоритма маршрутизации

Исследовался алгоритм свертки, рассмотренный в разделе 7.5.9, при этом анализировались 4 конфигурации сети [259]:

• Однородная сеть из 16 узлов и 48 линий, все линии - STM-1;

• Неоднородная сеть из 16 узлов и 48 линий, 44 линии - TM-1 и 4 линии - DS-3;

• Однородная сеть из 36 узлов и 120 линий, все линии - TM-1;

• Неоднородная сеть из 36 узлов и 120 линий, 112 линий - TM-1 и 8 линий - DS-3.

Выборочные результаты моделирования (в части второй конфигурации) приведены в таблице 7.8.

В качестве глобальных показателей эффективности сети оценивались следующие:

• A11_R ejects - частота отказа поступившей заявке (% );

• Av_Hops - средняя длина маршрута (в количестве линий);

GCAC_R - частота отказа поступившей заявке вследствие работы алгоритма GCAC (% );

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

• CAC_R - частота отказа поступившей заявке вследствие работы алгоритма САС % );

• A_AvCR

- среднее значение параметра линии vCR (количества свободной пропускной способности).

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

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

Отметим, что имитационное моделирование по своей сути является вероятностным процессом и поэтому в целях получения корректных результатов необходимо определять не только средние значения выходных показателей, но и их доверительные интервалы. Для динамических систем, характеризующихся наличием корреляции между последовательными событиями, данная задача требует повышенной трудоемкости моделирования. Так, например, для обеспечения средствами SES (а именно - методами оценки автокорреляции) относительной погрешности моделирования 10% с уровнем достоверности в 95% по всем из введенным выходным показателям необходимо для каждого из экспериментов использовать 50 часов машинного времени ЭВМ SUN-UltraSparc. Безусловно, суммарную (по всем экспериментам) трудоемкость моделирования в принципе можно существенно снизить посредством применения методов «Importance Sam-pling»(cM., например, [265]), базирующихся на теории регенеративных случайных процессов. Но если при моделировании непосредственно сетей массового обслуживания распознать регенеративные циклы не представляет особого труда и поэтому упомянутые методы оказываются весьма эффективными (см., например, [35]), то применительно к моделированию маршрутизации эта задача представляется очень сложной. В связи с этим корректная оценка доверительных интервалов производилась только для первых двух (основных) показателей, для остальных же показателей определялись лишь средние значения. Такой комбинированный подход позволил по каждому из 100 экспериментов собирать трассу из 100,000 устанавливаемых соединений, по каждому из экспериментов машинное время моделирования составляло 2...5 часов.

Анализ полученных результатов позволяет сделать следующие выводы:

1. Относительная ошибка результатов моделирования в части показателя «Средняя длина маршрута» достаточно мала и не превышает 1% (с уровнем достоверности 95%) для каждого из 100 проведенных экспериментов.

Таблица 7.8. Результаты моделирования неоднородной сети из 16 узлов

В части показателя «частота отказов» относительная погрешность достаточно высока и находится в пределах 5... 10% . Для получения более точных результатов (обеспечения погрешности порядка 1% ) необходимо значительно увеличить время моделирования, до 100... 500 часов для одного эксперимента.

2. Рассмотренный в разделе 7.5.9 управляемый параметр ImpBW существенно влияет на значения выходных показателей:

• Значение частоты отказов намного меньше при использовании алгоритма свертки по сравнению с использованием алгоритма «минимум прыжков» (отметим, что последний алгоритм соответствует алгоритму свертки при значении ).

• Средняя длина маршрута также меньше для алгоритма свертки по сравнению с алгоритмом «минимум прыжков». Это очень интересный и важный факт, т.к. при каждом текущем поиске последний алгоритм обеспечивает безусловный минимум длины вычисляемого маршрута; но когда линия становится заблокированной (вследствие полной загрузки ее пропускной способности), данный алгоритм может быть вынужден использовать намного более длинные маршруты.

Учет показателя «баланса пропускной способности» приводит к более равномерному использованию всех линий и, в связи с этим, более редким блокировкам отдельных линий.

3. Использование в алгоритме свертки динамических весов важности QoS параметров (ImpQS, ImpCDV, ImpCTD) позволяет снизить значение показателя QS_R в 2...4 раза. Использование динамических весов незначимо только для алгоритма «минимум прыжков» применительно к однородной сети, т.к. в этом случае маршрут с минимальным количеством линий обеспечивает одновременно и наилучшие значения в части QoS параметров (влияние протяженности линий на значение параметра линии MaxCTD не учитывалось). Применительно к неоднородной сети даже алгоритм «минимум прыжков» (не говоря уже о алгоритмах, учитывающих баланс пропускных способностей) весьма чувствителен к значениям динамических весов важности QoS параметров, т.к. линии STM-1 и DS-3 характеризуются различными значениями параметра CDV (см. таблицу 7.6.).

4. В части влияния QoS параметров заявок на эффективность функционирования сети:

• Предварительный анализ приводит к парадоксальному выводу - после усиления QoS требований со стороны заявок (снижения MaxCTD со 100 до 30...50 мс и CDV с 5 до 1.5...2.5 мс) мы не наблюдаем увеличения суммарной частоты отказов. Более того, в некоторых случаях мы наблюдаем даже незначительное (в пределах гарантированного доверительного интервала) уменьшение значения показателя All_Rejects. Данный факт объясняется следующим. Частота отказа вследствие неудовлетворения QoS требований возрастает с 0% до 1.2 - 3.6 % , но большинство из этих отказов отвечают заявкам с большим расстоянием (в смысле количества линий) от источника до адресата - этот вывод подтверждается также уменьшением средней длительности маршрута на 5 % . Это приводит к резкому (на 10...15 %) увеличению значения доступной пропускной способности - параметра A_AvCR, вследствие чего количество отказов вследствие работы GCAC и САС существенно уменьшается, что в итоге перевешивает увеличение показателя QS_R! Очевидно, что в аспекте эффективности работы сети целесообразно отказывать заявкам на «длинные» соединения, но в аспекте обслуживания конечных пользователей такой подход, естественно, неприемлем.

Таким образом, при сравнении вариантов с разной входной нагрузкой ориентироваться лишь на показатели All_Rejects и Av_Hops неправомерно. В этом случае мы должны использовать более сложные выходные (глобальные) показатели, учитывающие исходное (независимое от окончательного выбора маршрута, т.е. соответствующее простому алгоритму «минимум прыжков») расстояние от источника к адресату. В качестве примера такого показателя можно привести следующий - «Произведение частоты отказов на исходное расстояние от источника до адресата».

• Чтобы проверить данные выводы, был проведено несколько более длинных экспериментов с целью обеспечения доверительного интервала с 1% -й относительной погрешностью, собиралась также дополнительная статистика с целью учета исходного расстояния от источника до адресата. Полученные результаты (см. таблицу 7.9) подтвердили вышеприведенные выводы.

5. Наблюдается достаточно большое значение частоты отказов вследствие работы алгоритма САС (особенно при использовании алгоритма «минимум прыжков», никак не учитывающего требования по балансу пропускных способностей), хотя до его выполнения линии проверяются посредством алгоритма GCAC. Это свидетельствует о недостаточной эффективности используемого стандартного алгоритма GCAC и о необходимости его модификации (возможные направления этого обсуждались в разделе 7.5.10). Улучшение алгоритма GCAC позволит существенно снизить общую частоту отказов. Например, в случае использования идеального GCAC, полностью идентичного алгоритму САС, снижение общей частоты отказов достигает 25%.

Таблица 7.9.