Пример маршрутизации по алгоритму OSPF

Представим себе один день из жизни транзитной локальной сети. Пусть у нас имеется сеть Ethernet, в которой есть три маршрутизатора - Джон, Фред и Роб (имена членов рабочей группы Internet, разработавшей протокол OSPF). Эти маршрутизаторы связаны с сетями в других городах с помощью выделенных линий.

Пусть произошло восстановление сетевого питания после сбоя. Маршрутизаторы и компьютеры перезагружаются и начинают работать по сети Ethernet. После того, как маршрутизаторы обнаруживают, что порты Ethernet работают нормально, они начинают генерировать сообщения HELLO, которые говорят о их присутствии в сети и их конфигурации. Однако маршрутизация пакетов начинает осуществляться не сразу - сначала маршрутизаторы должны синхронизировать свои маршрутные базы.

Гипотетическая сеть с OSPF маршрутизаторами

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

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

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

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

Посмотрим теперь, как Робин вычисляет маршрут через сеть. Две из связей, присоединенных к его портам, представляют линии T-1, а одна - линию 56 Кб/c. Робин сначала обнаруживает двух соседей - Роба с метрикой 65 и Мило с метрикой 1785. Из объявления о связях Роба Робин обнаружил наилучший путь к Мило со стоимостью 130, поэтому он отверг непосредственный путь к Мило, поскольку он связан с большей задержкой, так как проходит через линии с меньшей пропускной способностью. Робин также обнаруживает транзитную локальную сеть с выделенным маршрутизатором Джоном. Из объявлений о связях Джона Робин узнает о пути к Фреду и, наконец, узнает о пути к маршрутизаторам Келли и Джеффу и к их тупиковым сетям.

После того, как маршрутизаторы полностью входят в рабочий режим, интенсивность обмена сообщениями резко падает. Обычно они посылают сообщение HELLO по своим подсетям каждые 10 секунд и делают объявления о состоянии связей каждые 30 минут (если обнаруживаются изменения в состоянии связей, то объявление передается, естественно, немедленно). Обновленные объявления о связях служат гарантией того, что маршрутизатор работает в сети. Старые объявления удаляются из базы через определенное время.

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

 

16. Протоколы внешней маршрутизации

Внешние протоколы маршрутизации предназначены главным образом для связи между автономными (независимыми) системами.

Протокол EGP (Exterior Gateway Protocol) один из известных протоколов этого типа (RFC 904, 827, 888, 911, 1092, 1093). Документ RFC 827, предложивший первую модель шлюза для взаимодействия со шлюзами других автономных систем, и документ RFC 888, представляющий собой развитие этой модели, накладывали существенное ограничение на топологию сети Internet, предполагая древовидную двухуровневую структуру, корнем которой является так называемая «магистральная» автономная система, состоящая из «магистральных» шлюзов. Главным преимуществом такой модели считалась невозможность образования в древовидной топологической структуре циклических маршрутов между автономными системами.

С помощью протокола EGP шлюзы могут снабжать друг друга информацией о достижимости соседних шлюзов и о маршрутах к соседним шлюзам. При этом динамическое вычисление маршрутов выполняется только шлюзами магистральной автономной системы, и затем результаты могут быть сообщены немагистральным шлюзам. Немагистральные шлюзы также могут предоставлять маршрутную информацию магистральным и немагистральным шлюзам, но они не имеют права передавать дальше маршруты, вычисленные на основе информации, полученной от других шлюзов. Это ограничение часто называется ограничением на распространение информации «третьей группы». Протокол EGP включает в себя механизм определения достижимости соседей (соседними называются шлюзы, совместно выполняющие протокол EGP), контроля достижимости и обмена информацией в форме обновляющих сообщений. Цель использования алгоритма достижимости — убедиться в том, что сосед работает и может поставлять надёжную информацию. Не менее важной является задача фильтрации информации перед тем, как отправлять её другим шлюзам, чтобы избежать лишних изменений базы данных.

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

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

В протоколе EGP определены три основные функции:

§ установление соседских отношений,

§ подтверждение достижимости соседа,

§ обновление маршрутной информации.

Каждая функция работает на основе обмена сообщениями запрос-ответ.

Так как каждая автономная система работает под контролем своего административного штата, то перед началом обмена маршрутной информацией внешние шлюзы должны согласиться на такой обмен. Сначала один из шлюзов посылает запрос на установление соседских отношений (acquisition request) другому шлюзу. Если тот согласен на это, то он отвечает сообщением подтверждение установления соседских отношений (acquisition confirm), а если нет - то сообщением отказ от установления соседских отношений (acquisition refuse), которое содержит также причину отказа.

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

Обмен маршрутной информацией начинается с посылки одним из шлюзов другому сообщения запрос данных (poll request) о номерах сетей, обслуживаемых другим шлюзом и расстояниях до них от него. Ответом на это сообщение служит сообщение обновленная маршрутная информация (routing update). Если же запрос оказался некорректным, то в ответ на него отсылается сообщение об ошибке.

Все сообщения протокола EGP передаются в поле данных IP-пакетов. Сообщения EGP имеют заголовок фиксированного формата.

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

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

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

Протокол BGP (Border Gateway Protocol, RFC 1267) — это протокол маршрутизации между автономными системами в сети Internet; он построен на основе опыта, накопленного при эксплуатации протокола EGP. Главная цель BGP — сократить транзитный трафик. Протокол BGP использует расширенное понятие автономной системы. В данном случае внутри автономной системы шлюзы могут использовать несколько различных протоколов маршрутизации и несколько метрик. Однако внутри автономной системы должен существовать единый план маршрутизации, позволяющий рассматривать автономную систему как единое целое.

В зависимости от того, с каким трафиком имеет дело автономная система, она причисляется к одной из следующих категорий:

§ тупиковая автономная система, имеющая единственное соединение с другими автономными системами; фактически, тупиковая система имеет дело только с локальным трафиком;

§ многовходовая автономная система. Эта система имеет более одного соединения с другими автономными системами, но она отказывается поддерживать транзитный трафик;

§ транзитная автономная система, которая имеет более одного соединения с другими автономными системами и предназначена для поддержания обоих видов трафика.

Протокол BGP использует в качестве транспортного протокола протокол ТСР. Хост-ЭВМ, выполняющие протокол BGP, не обязательно должны одновременно являться шлюзами. Хост-ЭВМ, не являющаяся шлюзом, может обмениваться маршрутной информацией со шлюзами при помощи протокола EGP или внутреннего протокола маршрутизации. Эта хост-ЭВМ может затем использовать протокол BGP для обмена маршрутной информацией с граничным шлюзом другой автономной системы.

17. Требования, предъявляемые к новой версии IP.

 

Создание новой версии IP-протокола версии 6, также называемого "IP Next Generation" (IP NG), стало основной мерой расширения адресного пространства Интернета. Одним из требований, предъявляемых к новой версии адресации, является поддержка не менее 1 миллиарда сетей. Чтобы достичь этого показателя используются 128-разрядные адреса. Как и в 4-й версии, IP-адрес версии 6 состоит из двух частей: идентификатора сети и идентификатора хоста.

Схема адресации 6-й версии разработана таким образом, чтобы она длительное время могла сосуществовать вместе с 4-й версией. Адрес IP версии 6 может содержать 32-разрядный адрес IP версии 4, который размещается в 32 младших разрядах. Признаком адреса является заполнение 80 первых битов нулями, за которыми следует 16 единичных или нулевых битов.

+ лекции

 

18. Адресация в IP v4

IP-адрес является уникальным 32-битным идентификатором IP-интерфейса в Интернет. Часто говорят, что IP-адрес присваивается хосту; это верно в случае, если хост имеет один сетевой IP-интерфейс. IP-адреса принято записывать разбивкой всего адреса по октетам, каждый октет записывается в виде десятичного числа, числа разделяются точками.

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

Классовая модель

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

Класс А. Старший бит адреса равен нулю. Размер сетевой части равен 8 битам. Таким образом, может существовать всего примерно 2⁷ сетей класса А, но каждая сеть обладает адресным пространством на 2²⁴ хостов. Т.к. старший бит адреса нулевой, то все IP-адреса этого класса имеют значение старшего октета в диапазоне 0 — 127, который является также и номером сети.

Класс В. Два старших бита адреса равны 10. Размер сетевой части равен 16 битам. Таким образом, может существовать всего примерно 2¹⁴ сетей класса В, каждая сеть обладает адресным пространством на 2¹⁶ хостов. Значения старшего октета IP-адреса лежат в диапазоне 128 — 191, при этом номером сети являются два старших октета.

Класс С. Три старших бита адреса равны 110. Размер сетевой части равен 24 битам. Количество сетей класса С - примерно 2²¹, адресное пространство каждой сети рассчитано на 254 хоста. Значения старшего октета IP-адреса лежат в диапазоне 192 - 223, а номером сети являются три старших октета.

Класс D. Сети со значениями старшего октета IP-адреса 224 и выше. Зарезервированы для специальных целей.

В классе А выделены две особые сети, их номера 0 и 127. Сеть 0 используется при маршрутизации как указание на маршрут по умолчанию (см. следующую тему "IP-Маршрутизация"). Сеть 127 используется для адресации IP-интерфейсом себя самого (loopback). На любом хосте обращение по адресу 127.0.0.1 означает связь с самим собой (без выхода пакетов данных на уровень доступа к среде передачи); для протоколов на уровнях транспортном и выше такое соединение неотличимо от соединения с удаленным хостом, что удобно использовать, например, для тестирования сетевого программного обеспечения.

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

Например, 194.124.84.0 - сеть класса С, номер хоста в ней определяется последним октетом. При отправлении широковещательного сообщения оно отправляется по адресу 194.84.124.255. Номера, разрешенные для присваивания хостам: от 1 до 254 (194.84.124.1 — 194.84.124.254), всего 254 возможных адреса.

Другой пример: в сети 135.198.0.0 (класс В, номер хоста занимает два октета) широковещательный адрес 135.198.255.255, диапазон номеров хостов: 0.1 — 255.254 (135.198.0.1 — 135.198.255.254).

Бесклассовая модель (CIDR)

Предположим, в локальной сети, подключаемой к Интернет, находится 2000 компьютеров. Каждому из них требуется выдать IP-адрес. Для получения необходимого адресного пространства нужны либо 8 сетей класса C, либо одна сеть класса В. Сеть класса В вмещает 65534 адреса, что много больше требуемого количества. При общем дефиците IP-адресов такое использование сетей класса В расточительно. Однако, если мы будем использовать 8 сетей класса С, возникнет следующая проблема: каждая такая сеть должна быть представлена отдельной строкой в таблицах маршрутов на маршрутизаторах, потому что с точки зрения маршрутизаторов — это 8 абсолютно никак не связанных между собой сетей, маршрутизация дейтаграмм в которые осуществляется независимо, хотя, фактически, эти IP-сети и расположены в одной физической локальной сети и маршруты к ним идентичны. Таким образом, экономя адресное пространство, мы многократно увеличиваем служебный трафик в сети и затраты по поддержанию и обработке маршрутных таблиц.

С другой стороны, нет никаких формальных причин проводить границу сеть-хост в IP-адресе именно по границе октета. Это было сделано исключительно для удобства представления IP-адресов и разбиения их на классы. Если выбрать длину сетевой части в 21 бит, а на номер хоста отвести, соответственно, 11 бит, мы получим сеть, адресное пространство которой содержит 2046 IP-адресов, что максимально точно соответствует поставленному требованию. Это будет одна сеть, определяемая своим уникальным 21-битным номером, следовательно, для ее обслуживания потребуется только одна запись в таблице маршрутов.

Единственная проблема, которую осталось решить: как определить, что на сетевую часть отведен 21 бит? В случае классовой модели, старшие биты IP-адреса определяли принадлежность этого адреса к тому или иному классу, и, следовательно, количество бит, отведенных на номер сети.

В случае адресации вне классов, с произвольным положением границы сеть-хост внутри IP-адреса, к IP-адресу прилагается 32-битовая маска, которую называют маской сети (netmask) или маской подсети (subnet mask). Сетевая маска конструируется по следующему правилу:

· на позициях, соответствующих номеру сети, биты установлены;

· на позициях, соответствующих номеру хоста, биты сброшены.

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

Запись адресов в бесклассовой модели

Для удобства записи IP-адрес в модели CIDR часто представляется в виде a.b.c.d / n, где a.b.c.d — IP адрес, n — количество бит в сетевой части.

Пример: 137.158.128.0/17

Маска сети для этого адреса: 17 единиц (сетевая часть), за ними 15 нулей (хостовая часть), что в октетном представлении равно

11111111.11111111.10000000.00000000 = 255.255.128.0.

Представив IP-адрес в двоичном виде и побитно умножив его на маску сети, мы получим номер сети (все нули в хостовой части). Номер хоста в этой сети, мы можем получить, побитно умножив IP-адрес на инвертированную маску сети.

Пример: IP = 205.37.193.134/26 или, что то же,

IP = 205.37.193.134 netmask = 255.255.255.192.

Распишем в двоичном виде:

IP = 11001101 00100101 11000111 10000110

маска = 11111111 11111111 11111111 11000000

Умножив побитно, получаем номер сети (в хостовой части - нули):

network = 11001101 00100101 11000111 11 000000

или, в октетном представлении, 205.37.193.128/26 или, что то же, 205.37.193.128 netmask 255.255.255.192.

Хостовая часть рассматриваемого IP адреса равна 000110, или 6. Таким образом 205.37.193.134/26 адресует хост номер 6 в сети 205.37.193.128/26. В классовой модели адрес 205.37.193.134 определял бы хост 134 в сети класса С 205.37.193.0, однако указание маски сети (или количества бит в сетевой части) однозначно определяет принадлежность адреса к бесклассовой модели.

Очевидно, что сети классов А, В, С в бесклассовой модели представляются при помощи масок, соответственно, 255.0.0.0 (или /8), 255.255.0.0 (или /16) и 255.255.255.0 (или /24).

 

19. Показатели алгоритмов маршрутизации.

Качество алгоритма определяется следующими показателями:

- Оптимальность,

- Простота и низкие непроизводительные затраты,

- Живучесть и стабильность,

- Быстрая сходимость,

- Гибкость.