Глава 2. Аббёойёооба ёинфоадшб пйдйё 103

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

Этих недостатков лишены методы распределенного управления маршрутизацией, кото­рые и нашли наиболее широкое применение в современных глобальных компьютерных се­тях. Примером использования метода распределенной маршрутизации является компьютер­ная сеть ARPA, Агентства перспективных исследований США.

При распределенной адаптивной маршрутизации каждый узел коммутации сам фор­мирует свою таблицу маршрутов, используя для этого информацию, получаемую от всех уз­лов, находящихся на возможных путях к получателю. Узлы обмениваются информацией о своем состоянии, временных задержках и очередях пакетов. При выборе маршрутов допол­нительно учитывается время, которое потребовалось для получения положительных под­тверждений на предыдущие пакеты. Таким образом, любое существенное отклонение от ис­ходного состояния сразу же передается смежным узлам для коррекции их таблиц маршрутов.

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

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

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

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

Одной из основных задач большинства способов маршрутизации является нахождение кротчайшего пути между отправителем и получателем информации. В качестве критерии длины пути может выступать время или стоимость передачи информации. К наиболее рас­пространенным алгоритмам выбора кратчайшего пути относятся алгоритмы Дейкстры и Форда — Фалкерсона. Результаты работы данных алгоритмов в равной степени могут ис­пользоваться для формирования таблиц маршрутов, как для централизованного, так и для распределенного алгоритма маршрутизации.