Алгоритмы маршрутизации

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

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

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

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

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