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

Вернемся к терминологии сетевых технологий и рассмотрим алгоритм работы маршрутизатора.

Маршрутизатор — это устройство, которое собирает информацию о топологии межсетевых соединений и на ее основании пересылает пакеты сетевого уровня в сеть назначения. Чтобы передать сообщение от отправителя, находящегося в одной сети, получателю, находящемуся в другой сети, нужно совершить некоторое количество транзитных передач между сетями, или хопов (от hop — прыжок), каждый раз выбирая подходящий маршрут. Таким образом, маршрут представляет собой последовательность маршрутизаторов, через которые проходит пакет.

ПРИМЕЧАНИЕ Необходимо отметить, что каждый из портов маршрутизатора находится в своей сети и может рассматриваться как узел этой сети.

Задачу выбора маршрута из нескольких возможных и продвижении пакета маршрутизаторы решают на основе таблиц маршрутизации, которые содержат информацию о том, куда в дальнейшем пакет направлять. Типичная таблица маршрутизации имеет следующий вид (таблица заполнена в соответствии со структурой сети изображенной на рис …. и справедлива для маршрутизатора М2).

Сетевой адрес узла назначения (Network Address)	Выходной номер порта текущего маршрутизатора	Сетевой адрес входного порта следующего маршрутизатора	Метрика (Metric)
S1		M1.1
S2		-
S3		-
S4		M4.4
S5		M4.4
S6		М3.1
S7		M4.4
S8		M4.4
S9		-
S10		M4.4
S10		M6.1
Default		M4.4

ПРИМЕЧАНИЕ Некоторые сети могут присутствовать в таблице более чем в одной строке, это означает что к этим сетям существуют альтернативные маршруты. На практике маршрутизатор выберет путь с наилучшей на этот момент метрикой.

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

Перечислим ключевые параметры, необходимые для работы маршрутизатора:

· адрес сети назначения (или что тоже самое сетевой адрес узла назначения),

· адрес входного порта следующего маршрутизатора,

· адрес порта, на который нужно направить пакет, этот адрес должен принадлежать одной из непосредственно присоединенных к маршрутизатору сетей,

· метрика — параметр характеризующий удаленность сети от маршрутизатора. В простейшем случае метрика будет равна количеству передач между сетями, или хопов. В более сложном случае метрика учитывает загруженность линии связи, скорость передачи, качество канала. Если метрика равна 0 это означает, что эта сеть непосредственно подключена к порту маршрутизатора.

Разберем последовательность шагов, которую выполняет маршрутизатор при продвижении пакета:

1. На порт маршрутизатора поступает кадр, внутри которого инкапсулирован пакет сетевого уровня. Маршрутизатор извлекает пакет из кадра и помещает его в буфер.

2. Маршрутизатор читает заголовок пакета и проверяет время его существования. Прежде всего проверяется контрольная сумма, и если пакет пришел поврежденным, то он отбрасывается. Выполняется проверка, не превысило ли время, которое провел пакет в сети (время жизни пакета), допустимой величины. Если время жизни пакета превышает допустимый срок, то такой пакет считается «заблудившимся» и также отбрасывается (уничтожается).

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

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

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

6. Для пересылки пакета на этот порт необходимо упаковать его в кадр сетевой технологии для сети, которая соединяет два порта – выходной порт текущего маршрутизатора и входной порт следующего. Для того чтобы маршрутизатор мог создать такой кадр, необходимо знать локальный МАС-адрес следующего порта (нам известен его сетевой адрес). Для определения локального адреса по сетевому адресу используется протокол разрешения адреса (Address Resolution Protocol, ARP).

7. Работа протокола ARP начинается с просмотра так называемой ARP-таблицы. Каждая строка таблицы устанавливает соответствие между сетевым адресом и МАС-адресом. В ARP-таблице содержатся записи не обо всех узлах сети, а только о тех, которые активно участвуют в сетевых операциях. Поскольку такой способ хранения информации называют кэшированием, ARP-таблицы иногда называют ARP-кэш. Если искомый адрес в ARP-таблице отсутствует протокол ARP формирует свой запрос (ARP-запрос), вкладывает его в кадр протокола канального уровня и рассылает запрос широковещательно.

8. Все узлы локальной сети получают ARP-запрос и сравнивают указанный там сетевой адрес с собственным. В случае их совпадения узел формирует ARP-ответ, в котором указывает свой сетевой адрес и свой локальный адрес, а затем отправляет его уже направленно на порт его запросивший.

9. Порт маршрутизатора создает кадр, упаковывает в него пакет. В поле адреса назначения заголовка кадра помещается локальный адрес входного порта следующего маршрутизатора. Готовый кадр отправляется в сеть и достигает следующего маршрутизатора. Следующий маршрутизатор повторяет эту же самую последовательность. Это будет повторяться до тех пор пока пакет не достигнет маршрутизатора к порту которого подключена сеть назначения.

10. Когда пакет доходит до сети назначения реализуется второй вариант упаковки пакета в новый кадр (первый вариант был рассмотрен в п.5). При помощи протокола ARP находится МАС-адрес узла-адресата. Порт маршрутизатора создает кадр и пересылает в нем пакет через присоединенную сеть к узлу-адресату.

Протоколы маршрутизации

Задача маршрутизации решается на основе анализа таблиц маршрутизации, размещенных во всех маршрутизаторах и конечных узлах сети. Каким же образом происходит формирование этих таблиц? Какими средствами обеспечивается адекватность содержащейся в них информации постоянно изменяющейся структуре сети? Основная работа по созданию таблиц маршрутизации выполняется автоматически, но и возможность вручную скорректировать или дополнить таблицу тоже, как правило, предусматривается.

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

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

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

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

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

· дистанционно-векторные алгоритмы (Distance Vector Algorithms, DVA);

· алгоритмы состояния связей (Link State Algorithms, LSA).

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

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

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

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

Адресация в IP-сетях

Классы IP-адресов

IP-адреса представляют собой основной тип адресов, на основании которых сетевой уровень передает пакеты между сетями.

IP-адрес имеет длину 4 байта и обычно записывается в виде четырех чисел, представляющих значения каждого байта в десятичной форме и разделенных точками, например, 128.10.2.30 — традиционная десятичная форма представления адреса, а 10000000 00001010 00000010 00011110 - двоичная форма представления этого же адреса (байты разделены пробелами). Иногда вместо термина байт используют термин октет.

Так как IP-адрес является сетевым адресом он состоит из двух логических частей — номера сети и номера узла в сети. Какая часть адреса относится к номеру сети, а какая — к номеру узла, определяется значениями первых бит адреса. Значения этих бит являются также признаками того, к какому классу относится тот или иной IP-адрес.

На рис. … показана структура IP-адреса разных классов.

Класс А. Если адрес начинается с 0, то сеть относят к классу А и номер сети занимает один байт, остальные 3 байта интерпретируются как номер узла в сети. Сети класса А имеют номера в диапазоне от 1 до 126, чтобы было понятно почему, представим этот диапазон в двоичном виде, от 00000001 до 01111110. (Номер 0 не используется, а номер 127 зарезервирован для специальных целей, о чем будет сказано ниже.) Сетей класса А немного (точнее 126), зато количество узлов в них может достигать 2²⁴, то есть 16 777 216 узлов.

Класс В. Если первые два бита адреса равны 10, то сеть относится к классу В. В сетях класса В под номер сети и под номер узла отводится по 16 бит, то есть по 2 байта. Таким образом, сеть класса В является сетью средних размеров с максимальным числом узлов 2¹⁶, что составляет 65 536 узлов. Номера сетей для класса В лежат в диапазоне от 128.0 до 191.255 (от 10000000 00000000 до 10111111 11111111).

Класс С. Если адрес начинается с последовательности 110, то это сеть класса С. В этом случае под номер сети отводится 24 бита, а под номер узла — 8 бит. Сети этого класса наиболее распространены, число узлов в них ограничено 2⁸, то есть 256 узлами. Номера сетей для класса С лежат в диапазоне от 192.0.0 до 223.255.255 (от 11000000 00000000 00000000 до 11011111 11111111 11111111).

Класс D. Если адрес начинается с последовательности 1110, то он является адресом класса. D и обозначает особый, групповой адрес — multicast. Если в пакете в качестве адреса назначения указан адрес класса D, то такой пакет должны получить все узлы, которым присвоен данный адрес, поэтому говорить о числе сетей и узлов бессмысленно. Всего адресов класса D будет 2²⁸. К адресам этого класса относятся адреса от 224.0.0.0 до 239.255.255.255 (от 11100000 00000000 00000000 00000000 до 11101111 11111111 11111111 11111111).

Групповая адресация предназначена для экономичного распространения в Internet или большой корпоративной сети аудио- или видеопрограмм, предназначенных сразу большой аудитории слушателей или зрителей.

Один и тот же узел может входить в несколько групп. Члены какой-либо группы multicast не обязательно должны принадлежать одной сети. В общем случае они могут распределяться по совершенно различным сетям.

Групповой адрес не делится на поля номера сети и узла и обрабатывается маршрутизатором особым образом. Чтобы маршрутизаторы могли автоматически распространять пакеты с адресом multicast по составной сети, необходимо использовать в конечных маршрутизаторах модифицированные протоколы обмена маршрутной информацией.

Класс Е. Если адрес начинается с последовательности 11110, то это значит, что данный адрес относится к классу Е. Адреса этого класса зарезервированы для будущих применений.

В табл. …. приведены диапазоны номеров сетей и максимальное число узлов, соответствующих каждому классу сетей.

 

Класс	Первые биты	Наименьший номер сети	Наибольший номер сети	Максимальное число узлов в сети
A		1.0.0.0	126.0.0.0	2^24
B		128.0.0.0	191.255.0.0	2^16
C		192.0.1.0	223.255.255.0	2^8
D		224.0.0.0	239.255.255.255	Multicast
E		240.0.0.0	247.255.255.255	Зарезервирован

 

Большие сети получают адреса класса А, средние — класса В, а маленькие — класса С.

Особые IP-адреса

В протоколе IP существует несколько соглашений об особой интерпретации IP-адресов.

· Если весь IP-адрес состоит только из двоичных нулей, то он обозначает адрес того узла, который сгенерировал этот пакет; этот режим используется только в некоторых сообщениях ICMP.

· Если в поле номера сети стоят только нули, то по умолчанию считается, что узел назначения принадлежит той же самой сети, что и узел, который отправил пакет.

· Если все двоичные разряды IP-адреса равны 1, то пакет с таким адресом назначения должен рассылаться всем узлам, находящимся в той же сети, что и источник этого пакета. Такая рассылка называется ограниченным широковещательным сообщением (limited broadcast).

· Если в поле номера узла назначения стоят только единицы, то пакет, имеющие такой адрес, рассылается всем узлам сети с заданным номером сети. Например, пакет с адресом 192.190.21.255 доставляется всем узлам сети 192.190.21.0. Такая рассылка называется широковещательным сообщением (broadcast).

При адресации необходимо учитывать те ограничения, которые вносятся особым назначением некоторых IP-адресов. Так, ни номер сети, ни номер узла не может состоять только из одних двоичных единиц или только из одних двоичных нулей. Отсюда следует, что максимальное количество узлов, приведенное в таблице для сетей каждого класса, на практике должно быть уменьшено на 2. Например, в сетях класса С под номер узла отводится 8 бит, которые позволяют задавать 256 номеров: от 0 до 255. Однако на практике максимальное число узлов в сети класса С не может превышать 254, так как адреса 0 и 255 имеют специальное назначение.

Особый смысл имеет IP-адрес, первый октет которого равен 127 (01111111). Он используется для тестирования программ и взаимодействия процессов в пределах одной машины. Когда программа посылает данные по IP-адресу 127.0.0.1, то образуется как бы «петля». Данные не передаются по сети, а возвращаются модулям верхнего уровня как только что принятые. Поэтому в IP-сети запрещается присваивать машинам IP-адреса, начинающиеся со 127. Этот адрес имеет название loopback. Любой адрес сети 127.0.0.0 служит для обозначения своего узла, а не только 127.0.0.1, например 127.0.0.3.

Если некоторая IP-сеть создана для работы в «автономном режиме», без связи с Internet, тогда администратор этой сети волен назначить ей произвольно выбранный номер. Но и в этой ситуации для того, чтобы избежать каких-либо коллизий, в стандартах Internet определено несколько диапазонов адресов, рекомендуемых для локального использования. Эти адреса не обрабатываются маршрутизаторами Internet ни при каких условиях. Адреса, зарезервированные для локальных целей, выбраны из разных классов: в классе А — это сеть 10.0.0.0, в классе В — это диапазон из 16 номеров сетей 172.16.0.0-172.31.0.0, в классе С — это диапазон из 255 сетей - 192.168.0.0-192.168.255.0.