Тольяттинский Государственный Университет Кафедра «Менеджмент организации» Предмет «Сети ЭВМ и средства коммуникации» Тема «М

1й маршрутизатор в ARPANET
Interface Message Processor
Bolt, Beranek and Newman, Inc., United States
Interface Message Processor (IMP) – первый роутер для ARPANET (предшественница Интернет). Внутри: миникомпьютер Honeywell 516 под управлением программы размером 6 000 слов (мониторинг сети, сбор статистики). Первый трафик в сети ARPANET пошёл между University of California (Лос-Анджелес) и Stanford Research Institute (Менло Парк, Калифорния) в 22:30 PST 29 октября 1969 г.
Скорость: ~0.5 млн.оп./с
Память: 12K
Стоимость: 82 200 $
Команда разработчиков IMP
1965 г.

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

Таблицы маршрутизации
Пример: таблица маршрутизации (Windows):
Y:\>route print
Active Routes:
Network Destination Netmask Gateway Interface Metric 0.0.0.0 0.0.0.0 172.20.175.254 172.20.175.3 10
127.0.0.0 255.0.0.0 127.0.0.1 127.0.0.1 1
172.20.175.0 255.255.255.0 172.20.175.3 172.20.175.3 10
172.20.175.3 255.255.255.255 127.0.0.1 127.0.0.1 10
172.20.255.255 255.255.255.255 172.20.175.3 172.20.175.3 10
224.0.0.0 240.0.0.0 172.20.175.3 172.20.175.3 10
255.255.255.255 255.255.255.255 172.20.175.3 172.20.175.3 1
Default Gateway: 172.20.175.254

Автономная система (AS)
Система IP-сетей и маршрутизаторов, управляемых одним или несколькими операторами, имеющими единую политику маршрутизации с Интернет (RFC 1930).
В настоящее время используются 16-битные номера AS (ASN) (предусмотрен переход на 32-битные).
IANA (Internet Assigned Numbers Authority) выделяет блоки номеров AS региональным интернет-регистраторам (RIR):
ARIN (American Registry for Internet Numbers) – www.arin.net
RIPE (Réseaux IP Européens) – www.ripe.net
APNIC (Asia-Pacific Network Information Centre) – www.apnic.net
LACNIC (Latin American and Caribbean Internet Addresses Registry) – www.lacnic.net
AfriNIC (African Network Information Centre) – www.afrinic.net
16-битные ASN:
0 и 65535 – резерв,
23456 – AS_TRANS,
64512-65534 – private use
http://www.iana.org/assignments/as-numbers
32-битные ASN (2007 г.):
0.0 – 0.65535: отобр. на ASN-16,
2.0 – 2.1023: APNIC,
3.0 – 3.1023: RIPE, …

Автономная система (AS)
Типы AS
Транзитная (transit AS) – пропускает через себя транзитный трафик сетей, подключенных к ней (на рис.: A, B).
Многоинтерфейсная (multihomed AS) – имеет соединения с более чем одним Интернет-провайдером, не разрешает транзитный трафик
(на рис.: C).
Ограниченная (stub AS) – имеет единственное подключение к одной внешней автономной системе (на рис.: D).
A
B
C
D
Stub AS расценивается как бесполезное использование номера AS, так как сеть размещается полностью под одним Интернет-провайдером и, следовательно, не нуждается в уникальной идентификации.

Протоколы маршрутизации
Interior Routing Protocols (внутри AS)
RIP, RIP2 (Routing Information Protocol) – протокол маршрутной информации
IS-IS (Intermediate System to Intermediate System) - промежуточные системы для промежуточной системы
IGRP (Interior Gateway Routing Protocol) - внутренний протокол маршрутизации ворот
OSPF (Open Shortest Path First) – сначала открыть кратчайший путь
Exterior Routing Protocols (между AS) – внешние протоколы маршрутизации
EGP (Exterior Gateway Protocol) – протокол внешней маршрутизации
BGP (Border Gateway Protocol) - протокол пограничной маршрутизации

Динамическая маршрутизация
Различают следующие классы протоколов динамической маршрутизации:
Протоколы вектора расстояния (Distance vector) — используют для поиска наилучшего пути расстояние до удаленной сети. Каждое перенаправление пакета маршрутизатором называется участком (hop). Наилучшим считается путь к удаленной сети с наименьшим количеством участков. Вектор определяет направление к удаленной сети.
Преимущества: требуют меньше вычислительных ресурсов.
Примеры: RIP, IGRP.
Протоколы состояния связи (Link state) — обычно называется "первый - кратчайший путь" (SPF). Каждый маршрутизатор создает три отдельные таблицы. Одна из них отслеживает непосредственно подключенных соседей, вторая — определяет топологию всей объединенной сети, а третья является таблицей маршрутизации. Устройство, действующее по протоколу типа состояния связи, имеет больше сведений об объединенной сети, чем любой протокол вектора расстояния.
Особенности: требуют больше вычислительных ресурсов, больше время конвергенции и восстановления при сбое.
Примеры: OSPF, IS-IS.

Routing Information Protocol
RFC 1058
Пакет RIP содержит:
команда: запрос или ответ,
Address Family Identifier (AFI): IP – код 2,
IP-адрес (маска сети не передаётся – классовый протокол),
метрика: количество участков (hops), max=16 (бесконечность).
Рассылка маршрутной информации происходит через UDP-порт 520, поддержка p2p и broadcast-каналов (по умолчанию).
RIP-пакеты содержат до 25 маршрутов, рассылаются через 30 с, если обновления не последовало за 180 с, то метрика увеличивается до 16, через 240с маршрут удаляется.
Балансировка трафика типа round-robin при наличии маршрутов
(до 6) с одинаковой метрикой.
Нет аутентификации.

RIP в действии…
Начальное состояние таблиц маршрутизации на RIP роутерах – есть записи только о присоединенных подсетях.
Состояние после распространения маршрутной информации.

Проблемы RIP
Медленная конвергенция →
несогласованность таблиц маршрутизации →
возникновение петель маршрутизации (routing loop).
net2 – AB – 0
net3 – AB – 1
net4 – AB – 2
net2 – BA – 0
net3 – BC – 0
net4 – BC – 1
A
B
C
D
net2
net3
net4
net2 – CB – 1
net3 – CB – 0
net4 – CD – 0
net2 – DC – 0
net3 – DC – 1
net4 – DC – 2
net2 – CB – 1
net3 – CB – 0
net4 FAILED
net2 – BA – 0
net3 – BC – 0
net4 – BC – 1
net2 – AB – 0
net3 – AB – 1
net4 – AB – 2
net2 – AB – 0
net3 – AB – 1
net4 – AB – 2
net2 – BA – 0
net3 – BC – 0
net4 – BA – 3
net2 – CB – 1
net3 – CB – 0
net4 FAILED

Проблемы RIP и их решение
Рассмотренная выше проблема с петлей маршрутизации часто называется счетом до бесконечности (counting to infinity) и связана с распространением в сети "слухов" о некорректных путях. Без внешнего воздействия на этот процесс счетчик хопов в пакете будет увеличиваться до бесконечности за счет добавления единицы при проходе пакета через любой маршрутизатор. Решить проблему позволит ограничение максимального значения в счетчике участков. Протокол вектора расстояния (RIP) предполагает счет участков до 15, поэтому любой путь с количеством участков 16 считается ошибочным (недостижимым).
Другим решением проблемы петель маршрутизации является деление горизонта (split horizon). Этот процесс устраняет некорректную информацию о маршрутизации за счет установки правила, согласно которому информация о маршрутизации не может передаваться в обратном направлении относительно направления, по которому она была получена. Деление горизонта не позволит маршрутизатору А послать обновление сведений обратно в маршрутизатор В, если они были получены от маршрутизатора В.

Проблемы RIP и их решение
Еще одним вариантом избежать несогласованности обновлений является порча путей (route poisoning). Например, когда отказывает сеть 4, роутер С сознательно инициирует порчу путей за счет вноса в таблицу записей для сети 4 со значением 16, т.е. устанавливает для этой сети состояние недостижимости (infinite). За счет такого искажения пути к сети 4 роутер B перестает воспринимать некорректные обновления информации о путях в сеть 4. Когда роутер B получает сообщение о порче пути от C, то возвращает ему специальное обновление, называемое "отравленный реверс" (poison reverse). Это гарантирует, что все роутеры в его сегменте получили информацию о порче пути к удаленной сети. Порча путей совместно с удержанием (hold down) позволяет уменьшить время конвергенции.
Удержание (hold down) предотвращает регулярные обновления о восстановлении пути, который был некоторое время недоступным, а также не допускает слишком быстрое изменение за счет установки определенного времени ожидания перед началом рассылки информации о восстановленном пути, либо стабилизации работы некоторой сети. Подобная задержка не позволяет слишком быстро начать изменение сведений о наилучших путях. Роутерам предписывается ограничить на определенный период времени рассылку любых изменений, которые могут воздействовать на переключение состояния недавно удаленных путей. Это предотвращает преждевременное изменение таблиц маршрутизации за счет сведений о временно неработоспособных маршрутизаторах. В процессе удержания используются триггерные обновления. Они сбрасывают счетчики удержания для уведомления соседнего роутера об изменениях в сети. В отличие от обновлений от соседнего роутера триггерные обновления инициируют создание новой таблицы маршрутизации, которая немедленно рассылается всем соседним устройствам.

RIPv2 (RIP II)
Особенности:
поддержка VLSM (маска передается в резервированном поле RIP-пакета)
возможна аутентификация MD5 или clear-text
поддержка групповой рассылки (multicast 224.0.0.9)
поддержка агрегации маршрутов
A
10.0.1.0/26
(10.0.1.0-
10.0.1.63)
10.0.1.64/26
(10.0.1.64-
10.0.1.127)
10.0.1.128/25
(10.0.1.128-
10.0.1.255)
B
Internet
суммарный маршрут
10.0.1.0/24
(10.0.1.0–10.0.1.255)
различные IP-сети

Open Shortest Path First
RFC 2328
Протокол состояния канала связи (link-state): другим роутерам той же иерархии каждые 30 мин. рассылаются объявления о состоянии канала связи (Links State Advertisement – LSA), которые описывают состояние всех своих интерфейсов, метрики и другие параметры. Роутеры накапливают эту информацию и используют в алгоритме Дейкстры (Dijkstra) для расчёта кратчайшего пути до каждого узла.
отсутствие ограничений на размер сети, иерархическая структура сети
несколько маршрутов в сторону одного узла → балансировка трафика типа round-robin
аутентификация
поддержка внеклассовых сетей (VLSM) и агрегации маршрутов
передача обновлений маршрутов с использованием групповых адресов (multicast 224.0.0.5 и 224.0.0.6)
работа поверх IP (не UDP/TCP)
поддержка маршрутизации с учётом TOS (type-of-service)

Дистанционно-векторная маршрутизация
В дистанционно-векторных алгоритмах (DVA) каждый маршрутизатор периодически и широковещательно рассылает по сети вектор, компонентами которого являются расстояния (измеренные в той или иной метрике) от данного маршрутизатора до всех известных ему сетей. Пакеты протоколов маршрутизации обычно называют объявлениями о расстояниях, так как с их помощью маршрутизатор объявляет остальным маршрутизатора известные ему сведения о конфигурации сети.
Получив от некоторого соседа вектор расстояний (дистанций) до известных тому сетей, маршрутизатор наращивает компоненты вектора на величину расстояния от себя до данного соседа. Кроме того, он дополняет вектор информацией об известных ему самому других сетях, о которых он узнал непосредственно (если они подключены к его портам) или из аналогичных объявлений других маршрутизаторов. Обновленное значение вектора маршрутизатор рассылает своим соседям. В конце концов, каждый маршрутизатор узнает через соседние маршрутизаторы информацию обо всех имеющихся в составной сети сетях и о расстояниях до них.
Затем он выбирает из нескольких альтернативных маршрутов к каждой сети тот маршрут, который обладает наименьшим значением метрики. Маршрутизатор, передавший информацию о данном маршруте, отмечается в таблице маршрутизации как следующий (next hop).
Дистанционно-векторные алгоритмы хорошо работают только в небольших сетях. В больших сетях они периодически засоряют линии связи интенсивным трафиком, к тому же изменения конфигурации не всегда корректно могут отрабатываться алгоритмом этого типа, так как маршрутизаторы не имеют точного представления о топологии связей в сети, а располагают только косвенной информацией — вектором расстояний.

«Дружественные соседи»
LSA - Link State Advertisment
LSA - оповещающее сообщение, посылается роутером на активный интерфейс. Содержит всю информацию о вызванном изменении роутинга.
Если LSA принес изменения, то они вносятся в топологическую базу, по SFP-алгоритму перестраивается таблица роутинга и LSA рассылается дальше.
Иначе LSA дальше не рассылается.
Посланный пакет распространяется далее всеми роутерами (если в этом есть необходимость)
Посылается только при изменении состояния линка
А так же посылается каждые 30 минут. (На всякий случай)
Выделенные DR роутеры в Multiaccess-сети
Рассылать в multicast-сети LSA-сообщения от каждого к каждому - слишком дорогое удовольствие. "Соседи" все свои LSA шлют только выделенному Designed Router'у(DR). DR рассылает аккумулированные LSA всем "соседям".
DR выбирается по протоколу Hello. Hello использует сетевые multicast сообщения по 224.0.0.5.
Выбирается так же Backup Designate Routera (BDR) - запасной. Он автоматически заменит DR если от того не придет ни одного LSA дольше определенного времени. Став DR он проинициирует выборы нового BDR.

OSPF: иерархия
AS может быть поделена на области (в каждой области у всех роутеров одинаковая БД топологии).
E, F, G – пограничные роутеры области (Area Border Routers).
E, F, G, H составляют магистраль (backbone).
Роутер A знает только о роутерах B и E.
Два типа маршрутизации OSPF: внутриобластная и межобластная.
Магистральная топология не видна для внутриобластных роутеров, а особенности топологии областей скрыты от магистральных роутеров.
AS
area 1
area 2
area 3
E
F
A
B
C
D
G
H
H1
H2
виртуальный канал
Петрозаводский госуниверситет, Lab127 Team, 2003-2007
СЕТЕВЫЕ ТЕХНОЛОГИИ

OSPF: выделенный роутер
В широковещательной (multiaccess) сети несколько маршрутизаторов могут быть подключены к одному сегменту сети (соседи). В этом случае производится процедура выбора выделенного маршрутизатора (DR – Designated Router) и резервного выделенного маршрутизатора (BDR – Backup Designated Router). На DR возлагаются функции общения с маршрутизаторами других областей, остальные маршрутизаторы в данном сегменте получают информацию от DR. Таким образом решается проблема формирования связей между всеми маршрутизаторами – которая могла бы привести к возникновению большого количества ненужных связей. В случае отказа DR – BDR становится на его место и производятся выборы нового BDR.
Петрозаводский госуниверситет, Lab127 Team, 2003-2007
СЕТЕВЫЕ ТЕХНОЛОГИИ

OSPF: принципы
Каждый роутер рассылает информацию о своем состоянии (используемые интерфейсы, доступные соседи) внутри области или по магистрали.
Из БД топологии каждый роутер строит дерево кратчайших путей, считая себя вершиной этого дерева (пути до каждого назначения внутри AS). Формируется таблица кратчайших путей → таблица маршрутизации.
Поля пакета OSPF:
Тип (hello, database description, link-state request and response, link-state acknowledgement),
Router ID – уникальное 32-битное число, идентифицирующее роутер в пределах AS,
Source area ID (0.0.0.0 – для магистрали),
данные.
СЕТЕВЫЕ ТЕХНОЛОГИИ
Петрозаводский госуниверситет, Lab127 Team, 2003-2007

Сравнение RIP и OSPF
В отличие от протокола маршрутизации RIP, который для сравнения маршрутов может использовать только их длину, выраженную в числе переходов, протокол маршрутизации OSPF использует для этой – же цели специальный критерий, который называется метрика. Метрика маршрута в протоколе OSPF формируется по специальному алгоритму и учитывает следующие параметры:
пропускная способность канала
величина задержки распространения сигнала в канале
надежность канала
загруженность канала
размер максимального блока данных, который может быть передан через данный канал
Использование такой метрики позволяет более объективно оценивать маршруты и, при наличии выбора, принимать эффективное и целесообразное решение.