Источник: Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М.: ИД "Техносфера", 2003. - с. 344-346.
Существует много способов классификации алгоритмов маршрутизации.
На наш взгляд, основная классификация основана на том, чувствительны ли выбираемые маршруты к изменению входных параметров трафика и параметров линий. В статистических алгоритмах выбор пути основан на старой информации о состоянии сети, а в динамических алгоритмах этот выбор основан на текущей информации.
Статические алгоритмы как правило базируются на моделях потокового типа (которые, в свою очередь, используют математический аппарат нелинейного программирования и градиентные методы поиска оптимальных решений), а динамические - на методах кратчайшего пути. Основное отличие между этими подходами состоит в том, что первый позволяет вычислить маршруты сразу для нескольких соединений одновременно, а второй - только для одного соединения. Исходя из этого алгоритмы потокового типа потенциально являются более точными по сравнению с алгоритмами кратчайшего пути. Однако, меняя стоимости линий в процессе использования алгоритма кратчайшего пути исходя из состояния сети (в первую очередь - загруженности линий) можно существенно улучшить качество работы алгоритма. Более того, доказано, что в предельном случае эти два типа алгоритмов характеризуются одинаковой эффективностью.
В практическом плане основной вопрос в реализации алгоритмов маршрутизации заключается в том, будут ли маршруты вычисляться по требованию (On-Demand) или же они будут заранее вычисляемые (Pre-Computed). При использовании подхода "по требованию" вычисление маршрута производится в момент запроса на установку соединения, что приводит к неизбежной задержке установки на время вычисления маршрута. Напротив, при использовании подхода "Заранее вычисляемые маршруты", время установки будет меньше, но при этом погрешность в исходных данных может привести к некорректному определению маршрута. Эти два подхода можно использовать совместно - так, в PNNI первоначально маршрут из множества заранее рассчитанных маршрутов, при невозможности же использования этих маршрутов в свете удовлетворения параметоров заявки производится специальный поиск исходя из требований заявки. Отметим, что стратегии "заранее вычисляемые" принадлежат классу квази-статических алгоритмов, так как маршрут для текущей заявки учитывает лишь старую информацию. В свою очередь, алгоритмы "по требованию" в ряде случаев также вынуждены использовать частично устаревшую информацию о состоянии сети (например, вследствие задержек в модификации этой информации и ее распространении по отдельным узлам сети), в связи, с чем они будут уже "квази-динамическими". Для некоторых типов соединений (например, крупных VPC) к принципе может быть использован и подход "вычисление маршрутов с задержкой" (Post-Computed), цель которого состоит в вычислении маршрутов для нескольких заявок одновременно с использованием текущей (а не старой) информации о параметрах сети. В этом случае неизбежна достаточно большая задержка между моментом возникновения заявки и установкой соответствующего ей соединения.
Алгоритмы "заранее вычисляемые" могут быть разделены на реализующие непостредственно выбор маршрута в источнике (Source Routing), то есть до начала установки соединения, и прыжок-за-прыжком (Hop-by-Hop), выбирающие маршрут непосредственно в процессе установки. В связи с тем, что ATM сети являются ориантированными на соединения, реализация в них второго явно нецелесообразна.
Еще одна классификация алгоритмов разделяет их на временно-зависимые и временно-независимые. Алгоритмы первого типа должны учитывать моменты появления различных заявок на установку и разъединение соединений , алгоритмы второго типа значения этих времен не учитывают. Пока что разработанные временно-зависимые алгоритмы маршрутизации практически не учитывают специфику ATM сетей.