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

Маршрутизация – это выбор маршрута доставки пакета. Частично, алгоритм маршрутизации уже был рассмотрен в лекции, посвященной протоколу IP. Здесь будет рассмотрена только общая классификация алгоритмов маршрутизации, не упоминавшихся ранее.

По степени распределенности схемы маршрутизации выделяют следующие алгоритмы маршрутизации:

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

- Многошаговые алгоритмы. В таблице маршрутизации указываются все шаги маршрута (промежуточные маршрутизаторы), которые должен пройти пакет. Схема работы - аналогично мостам, с маршрутизацией от источника (см. ранее). В сетях распространена мало. Однако в новой версии протокола IP (IPv6), наряду с классической одношаговой маршрутизацией, будет разрешена и маршрутизация от источника.

По способу построения таблиц маршрутизации выделяют следующие алгоритмы маршрутизации:

- Алгоритмы статической маршрутизации. Все записи в таблице маршрутизации задаются админстратором вручную. Пригоден только для небольших сетей. В крупных сетях применяется только совместно с алгоритмом динамической маршрутизации.

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

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

По использованию маски подсети в процессе маршрутизации IP-пакетов выделяют:

- Маршрутизацию на основании классов IP-адресов, без использования маски подсети.

- Бесклассовая междоменная маршрутизация, с использованием маски подсети.

При маршрутизации на основании классов IP-адресов, в таблицах маршрутизации маски подсетей не хранятся. Решение о том, является ли данный IP-адрес адресом сети или адресом конкретного компьютера принимается на основании класса IP-адреса (у сетей класса C адрес компьютера находится в последнем октете, у сетей класса B адрес компьютера находится в последних двух октетах и т.д.). Такой подход прост, но создает неудобства, т.к. минимальный размер подсети составляет 253 компьютера (сеть класса C), что является нерациональным расходованием адресов и не позволяет структуризировать сеть на более мелкие подсети. Поэтому постепенно в сетях происходит переход на маршрутизацию с использованием масок подсети - бесклассовая междоменная маршрутизация (CIDR, Classless Inter-Domain Routing). При этом подходе подсетям выделяются непрерывные диапазоны IP-адресов так, чтобы номер компьютера и номер сети можно было описать при помощи маски подсети (подробнее см. лекции по протоколу IP). При обмене информацией между маршрутизаторами (например, по протоколу RIPv2), вместе с информацией о маршру-тах передается и информация о масках подсетей для соответствующих IP-адресов.