7.5.4 Классификация алгоритмов маршрутизации
Существует много способов классификации алгоритмов маршрутизации.
На наш вгляд, основная классификация основана на том, чувствительны ли выбираемые маршруты к изменению входных параметров трафика и параметров линий. В статических алгоритмах выбор пути основан на старой информации о состоянии сети, а в динамических алгоритмах этот выбор основан на текущей информации.
Статические алгоритмы как правило базируются на моделях потокового типа (которые, в свою очередь, используют математический аппарат нелинейного программирования и градиентные методы поиска оптимальных решений), а динамические - на методах кратчайшего пути. Основное отличие между этими подходами состоит в том, что первый позволяет вычислять маршруты сразу для нескольких соединений одновременно, а второй - только для одного соединения. Исходя из этого алгоритмы потокового типа потенциально являются более точными по сравнению с алгоритмами кратчайшего пути. Однако, меняя стоимости линий в процессе использования алгоритма кратчайшего пути исходя из состояния сети (в первую очередь - загруженности линий) можно существенно улучшить качество работы алгоритма. Более того, доказано [191], что в предельном случае эти два типа алгоритмов характеризуются одинаковой эффективностью.
В практическом плане основной вопрос в реализации алгоритмов маршрутизации заключается в том, будут ли маршруты вычисляться по требованию (On-Demand) или же они будут заранее вычисляемые (Pre-Computed). При использовании подхода <<по требованию>> вычисление маршрута производится в момент запроса на установку соединения, что приводит к неизбежной задержке установки на время вычисления маршрута. Напротив, при использовании подхода «Заранее вычисляемые маршруты», время установки будет меньше, но при этом погрешность в исходных данных может привести к некорректному определению маршрута. Эти два подхода можно использовать совместно - так, в PNNI [133] первоначально маршрут выбирается из множества заранее рассчитанных маршрутов, при невозможности же использования этих маршрутов в свете удовлетворения параметров заявки производится специальный поиск исходя из требований заявки.
Отметим, что стратегии «заранее вычисляемые» принадлежат классу квази-статических алгоритмов, т.к. маршрут для текущей заявки учитывает лишь старую информацию. В свою очередь, алгоритмы «по требованию» в ряде случаев также вынужденны использовать частично устаревшую информацию о состоянии сети (например, вследствие задержек в модификации этой информации и ее распространении по отдельным узлам сети), в связи, с чем они будут уже «квази-динамическими». Для некоторых типов соединений (например, крупных VPC) в принципе может быть использован и подход «вычисление машрутов с задержкой» (Post-Computed), цель которого состоит в вычислении маршрутов для нескольких заявок одновременно с использованием текущей (а не старой) информации о параметрах сети. В этом случае неизбежна достаточно большая задержка между моментом возникновения заявки и установкой соответствующего ей соединения.
Алгоритмы «заранее вычисляемые» могут быть разделены на реализующие непосредственно выбор маршрута в источнике (Source Routing), т.е. до начала установки соединения, и прыжок-за-прыжком (Hop-by-Нор), выбирающие маршрут непосредственно в процессе установки. В связи с тем, что ATM сети являются ориентированными на соединения, реализация в них второго подхода явно нецелесообразна.
Еще одна классификация алгоритмов разделяет их на временнозависимые и временно-независимые. Алгоритмы первого типа должны учитывать моменты появления различных заявок на установку и разъединение соединений (см., например, [262]), алгоритмы второго типа значения этих времен не учитывают. Пока что разработанные временно-зависимые алгоритмы маршрутизации практически не учитывают специфику ATM сетей, в связи с чем в настоящей книге они и не рассматриваются.
Один из способов классификации состоит в разделении всех алгоритмов на централизованные (реализованные на основе сетевого менеджмента) и распределенные (реализованные на основе сетевого сигналлинга). В централизованых алгоритмах выбор всех маршрутов осуществляется в центральном узле сети, а в распределенных - в отдельных узлах (как правило, в источниках сообщений) и при этом узлы сети должны обмениваться информацией о текущих значениях параметров связанных с ними линий.
В целом взаимосвязь различных классификаций показана в таблице 7.5.
Таблица 7.5
