Принципы маршрутизации

Маршрутизатор, как и, например, мост, имеет несколько портов и должен для каждого поступающего пакета решить – отфильтровать его или передать на какой-то другой порт.

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

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

Будем рассматривать принципы маршрутизации на примере сети, изображенной на рис. Здесь S1..S13 – подсети,M1..M13 – маршрутизаторы. Порты маршрутизаторов будем обозначать сочетанием имени маршрутизатора и сети, например,M5/S2 – порт маршрутизатораM5, подключенный к сетиS2.

Для маршрутизатора M7 (см. рис.) таблица маршрутизации должна была бы выглядеть следующим образом (все адреса – сетевые):

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

Эффективность алгоритмов характеризуется:

• временем доставки пакетов

• нагрузкой на сеть

• затратами ресурсов маршрутизаторов (времени и памяти).

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

Классификация алгоритмов:

A. Одношаговые алгоритмы

1. Простая маршрутизация – не изменяющаяся при изменении топологии и состояния сети

• случайная– передача пакета на любой порт, кроме исходного;

• лавинная– передача пакета на все порты, кроме исходного;

• по предыдущему опыту– по принципу моста со счетчиками хопов;

2. Фиксированная маршрутизация – по статически заданным таблицам маршрутизации

• однонаправленная;

• многонаправленная;

3. Адаптивная маршрутизация – с учетом изменений состояния сети (+TTL)

• локальная– только на основе информации о состоянии своих выходных каналов и очередях пакетов;

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

• централизованная– с выделенным центром маршрутизации, собирающем информацию о состоянии узлов и каналов и рассылающем ее всем узлам;

• гибридная– централизованная+локальная (если путь в таблице один, то по нему, иначе – на основе длин очередей)

Б. От источника

Адаптивные алгоритмы:

• Дистанционно-векторные (DistanceVectorAlgorithms) – рассылается вектор из метрик соседних сетей – широковещательный мусор (близко к мосту) -RIP

• Состояния связей (LinkStateAlgorithms) – каждый узел строит полный граф сети (передаются ребра графаrouter-router,router-network) –IS-IS,OSPF,NLSP

Маршрутизаторы:

• Магистральные – модульные, 12-14 слотов, hotswap

• Региональных отделений

• Удаленных офисов

• Локальных сетей