- Автономная система представляет собой множество маршрутизаторов с единым техническим администрированием, использующих один протокол внутренней маршрутизации (IGP) и единую метрику для маршрутизации пакетов внутри AS, а для передачи пакетов в другие автономные системы применяющих протокол внешней маршрутизации (exterior gateway protocol или EGP).
-
AS может использовать несколько протоколов внутренней маршрутизации, а в некоторых случаях даже несколько наборов метрик в рамках одной AS.
Типы маршрутизаторов
-
Внутренний маршрутизатор (internal router) — маршрутизатор, все интерфейсы которого принадлежат одной зоне. У таких маршрутизаторов только одна база данных состояния каналов.
-
Граничный маршрутизатор (area border router, ABR) — соединяет одну или больше зон с магистральной зоной и выполняет функции шлюза для межзонального трафика. У граничного маршрутизатора всегда хотя бы один интерфейс принадлежит магистральной зоне. Для каждой присоединенной зоны маршрутизатор поддерживает отдельную базу данных состояния каналов.
-
Магистральный (опорный) маршрутизатор (backbone router) — маршрутизатора у которого всегда хотя бы один интерфейс принадлежит магистральной зоне.
-
Пограничный маршрутизатор автономной системы (AS boundary router, ASBR) Пограничный маршрутизатор автономной системы — обменивается информацией с маршрутизаторами принадлежащими другим автономным системам. Пограничный маршрутизатор автономной системы может находиться в любом месте автономной системы и быть внутренним, пограничным или магистральным маршрутизатором.
Принципы построения маршрутизаторов
-
Каждый маршрутизатор имеет групповой адрес согласно используемого протокола (например, для OSPF 224.0.0.5).
-
Каждый маршрутизатор не имеет индивидуального IP-адреса, но каждому интерфейсу присваивается свой IP, согласованный с сетью/подсетью, к которой он подключен.
-
Взаимодействие протоколов маршрутизации: на маршрутизаторе реализовано несколько протоколов, происходит пересылка с интерфейса с поддержкой одного, на интерфейс с поддержкой другого.
Функциональная модель маршрутизатора
Создание и ведение таблиц маршрутизации
Прикладной уровень
Удаление битых пакетов
Ведение очередей
Определение маршрута по таблице маршрутизации
Сетевой уровень
Анализ и модификация заголовка IP
Фильтрация
Преобразование сетевого адреса следующего маршрутизатора в локальный/порта
Передача уровню интерфейсов:
1. Пакета
2. Адреса след. маршрутизатора
3. номера выходного пакета
Отбрасывание заголовков канального уровня
Канальный
уровень
Прием и распределение данных по портам
1
2
3
4
5
6
7
8
Лавинная маршрутизация
-
Используется протокол IGMP - Internet Group Management Protocol. Относится к управляющим протоколам. Интегрируется в IP на сетевом уровне. Позволяет маршрутизатору определять принадлежность хостов к группе. Ориентирован на минимизацию служебного трафика.
-
Действующие версии IGMP v2, v3 и IGMP snooping,
-
IGMP v1 - устаревшая.
-
Версии IGMP 1, 2 и 3 совместимы между собой
Перерасчет таблицы маршрутизации
Перерасчет таблицы маршрутизации
Перерасчет таблицы маршрутизации
Перерасчет таблицы маршрутизации
Перерасчет таблицы маршрутизации
Перерасчет таблицы маршрутизации
Перерасчет таблицы маршрутизации
Алгоритм Беллмана-Форда
-
Алгоритм имени двух американских учёных: Ричарда Беллмана и Лестера Форда. Форд изобрёл этот алгоритм в 1956 г. Беллман в 1958 г. опубликовал статью, в которой алгоритм был сформулирован в том виде, в котором он известен сегодня.
-
Формулировка задачи: Пусть дан ориентированный взвешенный граф G с n вершинами и m рёбрами, и указана некоторая вершина v. Требуется найти длины кратчайших путей от вершины v до всех остальных вершин. Граф, возможно, содержит ребра отрицательных весов.
-
Ссылка на ресурс с описанием алгоритма: http://e-maxx.ru/algo/export_ford_bellman
Алгоритм Дейкстры
-
Предложен голландским ученым в области программирования Э́дсгером Ви́бе Дейкстрой (Dijkstra) в 1959 г.
-
Формулировка задачи: Дан ориентированный или неориентированный взвешенный граф с n вершинами и m рёбрами. Веса всех рёбер неотрицательны. Указана некоторая стартовая вершина s. Требуется найти длины кратчайших путей из вершины s во все остальные вершины, а также предоставить способ вывода самих кратчайших путей. Эта задача также называется "задачей о кратчайших путях с единственным источником" (single-source shortest paths problem).
-
Ссылка на ресурс с описанием алгоритма: http://e-maxx.ru/algo/export_dijkstra
Метрика в IP-сетях
-
Понятие кратчайшего пути обязательно требует уточнения: в каком смысле кратчайшего. Метрика представляет собой оценку эффективности связи в этом канале: чем меньше метрика, тем эффективнее организация связи.
-
Для протоколов внутренней маршрутизации в небольших сетях под метрикой чаще всего понимают количество переходов. Такие протоколы называются дистанционно-векторными.
-
Для протоколов более крупный сетей, особенно мультсервисных, под метрикой понимается совокупный критерий, включающий в себя различные параметры сети и трафика (по состоянию канала).
-
Пример (Cisco): количество секунд, нужное для передачи 100 Мбит, т.е.
-
M=108/C,
-
где С – пропускная способность канала в бит/с.
-
Метрика маршрута рассчитывается как сумма метрик связей.
Наиболее распространенные протоколы маршрутизации на сетевом уровне
Внутренняя и внешняя маршрутизация
-
внутренняя – для связи внутри одной крупной сети (например
