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