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

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

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

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

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

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

Номер подсети назначения	Адрес порта следующего маршрутизатора	Адрес выходного порта	Расстояние до сети назначения
S1	M1/S4	M7/S4
S2	M5/S5	M7/S5
S3	M5/S5	M7/S5
S4	––	M7/S4
S5	––	M7/S5
S6	M6/S4	M7/S4
S9	M9/S4	M7/S4
S11	M9/S4	M7/S4
Default	M10/S5	M7/S5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

13. СТЕК ПРОТОКОЛОВ TCP/IP

Все протоколы стека TCP/IP, сетевые службы, принципы их реализации и другие сопутствующие вопросы описываются в документах RFC (Request For Comment – предложение для обсуждения). Исходно это были действительно документы, предназначенные для обсуждения, но впоследствии сформировавшиеся стандарты также оформлялись в виде RFC. RFC-документу может быть присвоено одно из состояний стандартизации:

- Утвержденный стандарт (Standard),

- Предложенный к рассмотрению,

- Экспериментальный,

- Устаревший.

Кроме того, протоколу, описываемому в RFC-документе, может быть назначен один из статусов:

- Должен быть внедрен,

- Рекомендуется к внедрению,

- Может внедряться,

- Не рекомендуется внедрять.

Рассмотрение стека протоколов TCP/IP будем сопровождать указаниями номеров RFC, описывающих тот или иной протокол. Документы RFC можно получить, например, с Web-узла РосНИИРОС:

http://www.ripn.net/nic/archive.html

13.1. Система адресации в TCP/IP

TCP/IP пользуется тремя разновидностями адресов: локальными (MAC-адресами – в случае локальной сети, X.25-адресами – в случае X.25-сети и т.п.), сетевыми (IP-адресами) и символьными именами(доменными именами, DNS-именами).

Локальные адреса используются для доставки пакетов в пределах подсети, сетевые адреса – для маршрутизации пакетов между подсетями, а символьные имена – для более простого и запоминающегося именования узлов.

Сетевой уровень стека TCP/IP передает пакеты между сетями, опираясь на IP-адреса (RFC 990 и RFC 997). IP-адрес (четвертой версии, являющейся основной в настоящее время) состоит из 32 бит (4 байт). Как правило, IP-адрес записывают как четыре десятичных числа (значения отдельных байтов), разделенные точками, например: 123.45.67.89. Адрес состоит из двух частей: номера подсети и номера узла, причем номер узла не зависит от его MAC-адреса (или другого локального адреса). Распределение номеров подсетей для Internet осуществляется централизованно (долгое время только InterNIC, потом ICANN, в скором времени – группа независимых организаций), а для внутренних подсетей, не связанных напрямую с Internet, может назначаться администратором сети.

Все IP-адреса разделены на 5 классов (от A до E), задающих разные соотношения между количеством подсетей и количеством узлов в них (см. рис.13.1).

	1 байт	2 байт	3 байт	4 байт
Класс А	0\| N сети	N узла
Класс B	10\| N сети	N узла
Класс C	110\| N сети	N узла
Класс D	1110\| Адрес multicast-группы
Класс E	11110\| Зарезервировано

Рис.13.1 Классы IP-адресов

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

- адрес, все биты которого равны нулю, обозначает адрес того узла, который выдал этот пакет

- адрес, в поле номера сети которого стоят только нули, считается относящимся к той же сети, что и узел, выдавший этот пакет

- адрес, все биты которого равны единице, означает, что данный пакет должны получить все узлы подсети, к которой относится узел, выдавший этот пакет (ограниченное широковещательное сообщение – limited broadcast)

- адрес, в котором все биты поля номера узла равны единице, а поле номера сети задает определенную сеть (не все нули и не все единицы), то такой пакет должен рассылаться всем узлам указанной подсети (широковещательное сообщение – broadcast).

Таким образом, ни номер подсети, ни номер узла не может состоять из одних нулей или одних единиц. Это ограничивает количество узлов в подсети соотношением: N_узлов = 2ⁿ-2, где n – количество бит в поле номера узла, а количество подсетей – соотношением: N_{подсетей} = 2^m-2, где m – количество бит в поле номера подсети.

Например, каждая из 16382 (2¹⁴-2) подсетей класса B (14 бит под номер подсети, 16 бит под номер узла) максимально может включать 65534 (2¹⁶-2) узла с номерами от x.x.0.1 до x.x.255.254.

Кроме того, выделяется группа адресов, первый байт которых равен 127. Эти адреса используются для передачи данных между процессами на одном компьютере или для тестирования. Данные, отправленные по такому адресу, рассматриваются, как только что принятые из сети, в результате чего образуется как бы “петля” (loopback). Обычно используется адрес 127.0.0.1, но для этих целей можно использовать любой адрес вида 127.x.x.x.