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

Постановка задачи
A
E
D
C
H
K
F
G
B
С помощью служебного протокола маршрутизаторы должны автоматически:
построить свои таблицы маршрутизации (Net - Next Hop)
постоянно поддерживать соответствие таблицы текущей топологии сети – добавление и удаление связей и маршрутизатров
Распределенный подход – нет центрального элемента, собирающего топологические данные и вырабатывающего таблицы для всех

Дистанционно-векторные алгоритмы
Distance-Vector Algorithms, DVA
A
E
D
C
H
K
F
G
B
1. Каждый маршрутизатор рассылает всем непосредственным соседям вектор расстояний до известных ему сетей
Расстояние (метрика) – в хопах (промежуточных мршрутизаторах); или в условных единицах, учитывающих пропускную способность каналов связи
H, 1
H, 1
G, 1
A, 1
E, 1
D, 1
A, 1
E, 1
2. Получив векторы от соседей, маршрутизатор добавляет новую информацию к своей базе данных о известных сетях – расстояние наращивается на 1 (или метрику канала связи)
Если к одной и той же сети можно попасть разными маршрутами, то выбирается один – с минимальным расстоянием
База данных о известных сетях –> таблица маршрутизации
3. Процесс обмена векторами расстояний периодически повторяется – отслеживается динамика изменения топологии сети
A, 1
E, 1
D, 2
C, 3
H, 2
…

Алгоритмы состояния связей
Link – State Algorithms, LSA
A
E
D
C
H
K
F
G
B
L
M
N
P
R
S
T
U
1. Маршрутизаторы обмениваются информацией о топологии сети для построения точного графа.
Вершины – маршрутизаторы и сети (A, B, C, …, S, T, U). Передается информация о связях между вершинами графа.
S, U, up
S, A, up
S, E, up
S, T, up
S, L, up

Алгоритмы состояния связей
Link – State Algorithms, LSA
A
E
D
C
H
K
F
G
B
L
M
N
P
R
S
T
U
2. Каждый маршрутизатор через несколько итераций обмена располагает базой топологической информации – графом сети. Графы всех маршрутизаторов идентичны.
Новые топологичские объявления – только при изменении состоянии связи (up -> down)
Периодическое тестирование связи - hello
S, U, up
S, A, up
S, E, up
S, T, up
S, L, up

Алгоритмы состояния связей
Link – State Algorithms, LSA
A
E
D
C
H
K
F
G
B
L
M
N
P
R
S
T
U
3. Каждый маршрутизатор на основе графа строит свою таблицу маршрутизации:
- находит от себя кратчайший маршрут до каждой сети
- запоминает из этого маршрута только следующий хоп
S, U, up
S, A, up
S, E, up
S, T, up
S, L, up

RIP-объявления делаются каждым маршрутизатором каждые 30 секунд (Tобъявл.)

Правила построения таблицы маршрутизации по RIP

M1
M2
M3
30 сек
t
...
Связь
разорвана!
Время существования петли = (16/2-1) x 30 = 210 c = 3,5 мин

M1
M2
M4
...
Split horizon
?
M4 узнал о 1 от M3
M3
Петля существовала 4 х 30 = 120 сек

Пример сети с маршрутизаторами OSPF
Cвязи типа "маршрутизатор - маршрутизатор":
Мило - Робин
Мило - Роб
Роб - Робин
Кэлли - Фред
Джеф -Джон
Cвязи типа "маршрутизатор - сеть":
Мило - 201.106.14.0
Робин - 201.106.15.0
Фред - 195.46.17.0
Джон - 195.46.17.0
Роб - 195.46.17.0
Кэлли - 129.35.0.0
Джеф - 197.13.58.0.

Метрика и оптимизация транзитных локальных сетей
В OSPF три категории сетей :
1) "хост-сеть» - подсеть из одного адреса
2) "тупиковая сеть» - подсеть, подключенная только к одному маршрутизатору
3) "транзитная сеть» - подсеть, подключенная к более чем одному маршрутизатору.
Синхронизация маршрутизаторов "каждый с каждым" на транзитной сети:
передача базы N*(N-1) раз
Синхронизация с "выделенным" маршрутизатором:
передача базы 2*N раз

С) Связь с тупиковой сетью с множественным доступом
N2
RT4
RT3
RT5
RT6

Метрика в направлении от сети до маршрутизатора всегда равна 0
С) Объявления о связях маршрутизатора
D)Объявления о связях сети

G) Внешние маршруты в таблице RT6

Объявления, передаваемые пограничными маршрутизаторами из области 1 в магистраль:
Расстояния, вычисленные RT3 и RT4 до остальных пограничных маршрутизаторов

Объявления, передаваемые пограничными маршрутизаторами RT3 и RT4 внутренним маршрутизаторам области 1:

Фильтрация пакетов с помощью маршрутизаторов
Язык фильтрации маршрутизаторов Cisco Systems:
1. Стандартный список доступа:
access-list access-list-number {deny | permit} {source-address [source-wildcard] | any} [log]
interface serial 0
ip access-group 1 in – применение списка доступа
Определение списка доступа
access-list 1 deny 192.78.46.0 0.0.255
access-list 1 deny host 193.24.15.8
access-list 1 permit any
[access-list 1 deny any] – неявный оператор в конце каждого списка
in
out
serial 0
serial 1
Задача – не принимать (in) или не отправлять (out) пакеты,
удовлетворяюшие определенным признакам

Фильтрация пакетов с помощью маршрутизаторов
(продолжение)
Язык фильтрации маршрутизаторов Cisco Systems:
1. Расширенный (extended) список доступа:
access-list [list number] [permit|deny]
[protocol|protocol key word]
[source address source-wildcard mask] [source port]
[destination address destination-wildcard mask]
[destination port] [log options]
Запрещает ли список 101 доступ к серверу 192.78.46.8 по TCP,
разрешая остальной доступ по IP?
access-list 101 permit IP any host 192.78.46.8
access-list 101 deny TCP any host 192.78.46.8
Запрет ping хоста 192.78.46.8:
access-list 101 deny ICMP any host 192.78.46.8 eq 8
in
out
serial 0
serial 1
Задача – не принимать (in) или не отправлять (out) пакеты,
удовлетворяюшие определенным признакам

Фильтрация объявлений протоколов маршрутизации
in
serial 0
serial 1
Маршрутизаторы Cisco Systems:
Подавление отправки объявлений на определенном интерфейсе:
passive-interface serial 0
Управление объявлением определенных маршрутов
distribute-list 2 out serial 1
access-list 2 deny 194.12.34.0 0.0.0.255
access-list 2 deny 132.7.0.0 0.0.255.255
access-list 2 permit any
Управление приемом определенных маршрутов
distribute-list 2 in serial 1
В ОС Unix – gated поддерживает язык фильтрации объявлений

Связь между различными протоколами маршрутизации
serial 0
ethernet 0
interface serial 0
ip address 130.93.1.1 255.255.255.0
!
interface ethernet 0
ip address 130.94.1.1 255.255.255.0
!
router ospf 9000
network 130.93.0.0 0.0.255.255 area 0
redistribute rip metric 1
!
router rip
network 130.94.0.0 0.0.255.255 area 0
redistribute ospf 9000 metric 1

Исключение петель в BGP
Объявление RTA->RTB: AS100; NH=150.10.30.1; Net=150.10.0.0 255.255.0.0
Объявление RTB->RTC: AS200, AS100; NH = 160.10.20.1; Net=150.10.0.0 255.255.0.0
Объявление RTC>RTA: AS300, AS200, AS100; NH = 150.10.20.2; Net=150.10.0.0 255.255.0.0 – отбраковывается, так как в пути встретился номер своей AS
150.10.30.1
150.10.30.2

RTA#
router bgp 100 ( – номер AS)
neighbor 129.213.1.1 remote-as 200
RTB#
router bgp 200
neighbor 129.213.1.2 remote-as 100
neighbor 175.220.1.2 remote-as 200
RTC#
router bgp 200
neighbor 175.220.212.1 remote-as 200
Внешнее и внутреннее использование BGP
Exterior BGP – между AS
Interior BGP – между маршрутизаторами одной AS

RTC#
router bgp 300
neighbor 2.2.2.2 remote-as 100
neighbor 2.2.2.2 route-map STOPUPDATES out
route-map STOPUPDATES permit 10
match ip address 1
access-list 1 deny 170.10.0.0 0.0.255.255
access-list 1 permit 0.0.0.0 255.255.255.255
Фильтрация объявлений в BGP
match as-path
match community
match clns
match interface
match ip address
match ip next-hop
match ip route-source
match metric
match route-type
match tag

A
B
C
D
Сеть назначения
1
1
1
1
10
Записи о пути к сети назначения
D: direct, metric 1
B: route via D, metric 2
C: route via B, metric 3
A: route via B, metric 3
Вопрос
Имеется сеть:

A
B
C
D
Сеть назначения
1
1
1
1
10
Записи о пути к сети назначения
D: dir, 1 dir, 1
B: 16
C: B, 3
A: B, 3
Связь B-D отказывает
Маршрутизаторы не поддерживают Split Horizon
Что происходит в сети при наихудшей синхронизации объявлений?

Исключение петель в BGP
Объявление RTA->RTB: AS100; NH=150.10.30.1; Net=150.10.0.0 255.255.0.0
Объявление RTB->RTC: AS200, AS100; NH = 160.10.20.1; Net=150.10.0.0 255.255.0.0
Объявление RTC>RTA: AS300, AS200, AS100; NH = 150.10.20.2; Net=150.10.0.0 255.255.0.0 – отбраковывается, так как в пути встретился номер своей AS
150.10.30.1
150.10.30.2

RTA#
router bgp 100 ( – номер AS)
neighbor 129.213.1.1 remote-as 200
RTB#
router bgp 200
neighbor 129.213.1.2 remote-as 100
neighbor 175.220.1.2 remote-as 200
RTC#
router bgp 200
neighbor 175.220.212.1 remote-as 200
Внешнее и внутреннее использование BGP
Exterior BGP – между AS
Interior BGP – между маршрутизаторами одной AS