Алгоритм маршрутизации на основе входного дерева

Неадаптивные (статистические) алгоритмы

Принципы построения маршрутов

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

Маршрутизатор это устройство, в котором выполняются 2 основных процесса:

· Процесс пересылки. Прием пакета, определение куда его направить.

· Обновление таблиц маршрутизации. Выполняется на основе алгоритма маршрутизации

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

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

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

В основном все основываются на т.н. принципе оптимальности. Он заключается в следующем: если маршрутизатор B располагается на оптимальном маршруте между A и C, то от B к C тоже является оптимальным маршрутом.

В этом случае происходит рассмотрение множества оптимальных маршрутов от всех источников к приемнику в виде дерева.

Расстояния между узлами измеряется количеством транзитных участков. Входное дерево может быть неуникально, то есть их может быть несколько.

Цель всех алгоритмов построение входного дерева для маршрутизаторов. Недостаток: линии связи маршрутизаторов могут выходить из строя и могут быть у каждого маршрутизатора разные представления о сети.

Дата добавления: 2015-01-03