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

1.

Сети и системы телекоммуникаций
Протоколы маршрутизации
ИМКН УрФУ

2.

Сети и системы телекоммуникаций. Протоколы маршрутизации
План
Место протоколов маршрутизации в моделях OSI и
TCP/IP
Маршрутизация по вектору расстояний
Маршрутизация с учетом состояния канала
Протоколы внутренней маршрутизации (RIP, OSPF)
Структура Интернет
Протокол внешней маршрутизации BGP
2

3.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Место в моделях OSI и TCP/IP
Модель OSI
Модель TCP/IP
Прикладной
Представления
Прикладной
Сеансовый
Транспортный
Транспортный
Сетевой
Интернет
Канальный
Сетевых
интерфейсов
Физический
3

4.

Сети и системы телекоммуникаций. Протоколы марщрутизации
Сетевой уровень в TCP/IP
Прикладной
HTTP
SMTP
Транспортный
TCP
RIP
Сетевой
Ethernet
FTP
UDP
OSPF
IP
ARP
Сетевых
интерфейсов
DNS
BGP
ICMP
DHCP
WiFi
DSL
4

5.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Маршрутизация
Маршрутизация (routing) – поиск маршрута
доставки пакета между сетями через транзитные
узлы – маршрутизаторы
• Учет изменений в топологии сети
• Учет загрузки каналов связи и маршрутизаторов
Этапы маршрутизации:
• Изучение сети
• Продвижение пакетов на маршрутизаторе
5

6.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Варианты изучения сети
Статическое
• Ручная конфигурация всех маршрутизаторов
• Изменения в сети не учитываются
Динамическое
• Автоматическая конфигурация маршрутизаторов с
использованием протоколов маршрутизации
• Учет изменений в сети
6

7.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Принципы маршрутизации
Каждый маршрутизатор вычисляет собственную
таблицу продвижения (forwarding table)
Маршрутизатор знает только стоимость пути до
соседа, не топологию
Маршрутизатор может обмениваться служебными
сообщениями только со своим соседом
• Знает только то, что сообщил ему сосед
На каждом маршрутизаторе выполняется один и
тот же алгоритм одновременно
Каналы связи могут оборваться, маршрутизаторы
могут сломаться
• Сообщения могут быть потеряны
7

8.

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

9.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Поиск кратчайшего пути
Алгоритм:
1. Присвоить каждой линии связи стоимость
(cost/distance)
2. Определить лучший путь между каждой парой
узлов как путь, имеющий наименьшую полную
стоимость (сумму всех стоимостей линий связи
между узлами)
3. Построить дерево от всех узлов к данному
приемнику
9

10.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Поиск кратчайшего пути
Найти кратчайший
путь от A до E
Линии связи
двунаправленные с
одинаковой
стоимостью в обоих
направлениях
Tanenbaum, Wetherall Computer Networks 5e
10

11.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Поиск кратчайшего пути
dist(AE) = 10
dist(ABE) = 8
dist(ABFE) = 9
dist(ABCE) = 7
dist(ABCDE) = 10
Tanenbaum, Wetherall Computer Networks 5e
11

12.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Поиск кратчайшего пути
dist(AE) = 10
dist(ABE) = 8
dist(ABFE) = 9
dist(ABCE) = 7
dist(ABCDE) = 10
ABCE – кратчайший
путь
dist(ABCE) = 7
Tanenbaum, Wetherall Computer Networks 5e
12

13.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Поиск кратчайшего пути
Вершина Е – корень
дерева
Применение
• Используется только
место назначения,
чтобы следовать
кратчайшему пути
• Каждый узел должен
отправлять только
следующему узлу
• Каждый узел
содержит список
следующих узлов для
Tanenbaum, Wetherall Computer Networks 5e
каждого места
назначения
13

14.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Классификация протоколов
маршрутизации
Используемый алгоритм маршрутизации
• Дистанционно-векторные протоколы (Distance Vector
Protocols): RIP, BGP
• Протоколы состояния каналов связи (Link State
Protocols): OSPF
Область применения
• Протоколы внутридоменной маршрутизации (Interior
Gateway Protocols): RIP, OSPF
• Протоколы междоменной маршрутизации (Exterior
Gateway Protocols): BGP
14

15.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Маршрутизация по вектору расстояний
Distance Vector Routing
Старый подход, использовался в сети ARPANET
В Интернет используется протоколом RIP
Низкая скорость сходимости
Работает по алгоритму Форда-Беллмана (1969 г.)
15

16.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Distance Vector Algorithm
Каждый узел поддерживает вектор расстояний до
всех мест назначения (destination)
1. Назначить стоимость вектора до самого себя 0, до всех
мест назначения - ∞
2. Периодически отправлять вектор соседям
3. Обновить вектор до каждого места назначения, выбирая
кратчайшее расстояние, после добавления стоимости
линии связи до соседа
16

17.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Пример Distance Vector
До
Стоимость
A
0
B
∞
C
∞
D
∞
Начальный вектор для узла А
17

18.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Пример Distance Vector
До
B
сообщение
D
сообщение
A
∞
∞
B
0
∞
C
∞
∞
D
∞
0
До
B+3
D+7
Стоимость
Следующий
А
∞
∞
0
---
B
3
∞
3
B
C
∞
∞
∞
---
D
∞
7
7
D
18

19.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Первый обмен сообщениями
A = min(B+3, D+7)
C = min(B+6, D+2)
До
A
B
C
D
A
0
∞
∞
∞
B
∞
0
∞
∞
C
D
∞
∞
∞
∞
0
∞
∞
0
B = min(A+3, C+6, D+3)
D = min(A+7, B+3, C+2)
A знает
B знает
C знает
D знает
Cost
Next
Cost
Next
Cost
Next
Cost
Next
0
---
3
A
∞
---
7
A
3
B
0
---
6
C
3
B
∞
---
6
C
0
---
2
C
7
D
3
D
2
D
0
---
19

20.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Второй обмен сообщениями
A = min(B+3, D+7)
C = min(B+6, D+2)
До
A
B
C
D
A
0
3
∞
7
B
3
0
6
3
C
D
∞
7
6
3
0
2
2
0
B = min(A+3, C+6, D+3)
D = min(A+7, B+3, C+2)
A знает
B знает
C знает
D знает
Cost
Next
Cost
Next
Cost
Next
Cost
Next
0
---
3
A
9
B
6
B
3
B
0
---
5
D
3
B
9
B
5
D
0
---
2
C
6
B
3
D
2
D
0
---
20

21.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Третий обмен сообщениями
A = min(B+3, D+7)
C = min(B+6, D+2)
До
A
B
C
D
A
0
3
9
6
B
3
0
5
3
C
D
9
6
5
3
0
2
2
0
B = min(A+3, C+6, D+3)
D = min(A+7, B+3, C+2)
A знает
B знает
C знает
D знает
Cost
Next
Cost
Next
Cost
Next
Cost
Next
0
---
3
A
8
D
6
B
3
B
0
---
5
D
3
B
8
B
5
D
0
---
2
C
6
B
3
D
2
D
0
---
21

22.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Distance Vector Algorithm
Алгоритм запускается при добавлении нового узла
Нет никаких сообщений о неполадках на канале
• Сломался маршрутизатор, оборвалась линия связи
22

23.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Distance Vector Algorithm
Алгоритм запускается при добавлении нового узла
Нет никаких сообщений о неполадках на канале
• Сломался маршрутизатор, оборвалась линия связи
Недостижимые сети (unreachable networks)
• Счет до бесконечности
23

24.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Счет до бесконечности
To B
Host 1
A
To C
B
ToToHost2
B
C
Host 2
24

25.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Счет до бесконечности. Решения
Time To Live (TTL)
Split Horizon
• Никогда не отправлять пакет на интерфейс, с которого
он пришел
Poison Reverse
• Установить стоимость до нерабочего маршрута в
бесконечность и немедленно рассказать всем соседям
Маршрутизация с учетом состояния канала
• Современный подход
25

26.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Маршрутизация с учетом состояния
канала
Link-State Routing
Современный подход
Быстро сходится
Требует большое количество ресурсов
• Обмен топологиями между всеми маршрутизаторами
• Хранение всех топологий в памяти маршрутизатора
Работает по алгоритму Дейкстры (1959 г.)
26

27.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Link-State Algorithm
1. Узлы распространяют собственную топологию
• Каждый узел знает полную топологию
2. Каждый узел вычисляет собственную таблицу
пересылки (forwarding table)
Алгоритм Дейкстры
27

28.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Link-State Algorithm
Повредился канал связи
• Оба маршрутизатора рассылают изменения
• Канал связи удаляется из топологии
Повредился маршрутизатор
Все маршрутизатора рассылают изменения
Сломанный маршрутизатор не может обновлять свою
топологию
Все каналы связи до сломанного маршрутизатора
удалены из топологии
28

29.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
1. Назначить все узлы непосещенными,
установить стоимость от источника до
источника 0, до всех непосещенных узлов - ∞
2. Пока есть непосещенные узлы выполнять:
a) Извлечь узел N с наименьшей стоимостью
b) Добавить канал до N в дерево кратчайшего
пути
c) Пересчитать (уменьшить) стоимость
смежных с N узлов
29

30.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
1. Начальное состояние
30

31.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
2. Снижение стоимости смежных с А узлов
31

32.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
3. Снижение стоимости смежных с В узлов
32

33.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
4. Снижение стоимости смежных с С узлов
33

34.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
5. Снижение стоимости смежных с G узлов
34

35.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
6. Снижение стоимости смежных с F узлов
35

36.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
7. Снижение стоимости смежных с E узлов
36

37.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
8. Снижение стоимости смежных с D узлов
37

38.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
9. Снижение стоимости смежных с H узлов
38

39.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Алгоритм Дейкстры
Строит полное дерево
• Больше, чем нужно для пересылки
• Полная топология сети
Находит кратчайший путь, увеличивая расстояние
от источника
Время построения быстро увеличивается с ростом
сети
39

40.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Routing Information Protocol
RIP – протокол маршрутной информации
Дистанционно-векторный протокол
Использует алгоритм Форда-Беллмана
Использует число хопов (hops) как метрику
• Бесконечность устанавливается в 16 хопов
• Ограниченный размер сети
Маршрутизаторы отправляют вектор каждые 30 с.
• Таймаут 180 с.
• Путь считается
таймаута
недостижимым
при
достижении
40

41.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Версии RIP
RIPv1
• RFC 1058
• 1969 г.
RIPv2
• RFC 2453
• 1994 г.
RIPng
• Разработан для сетей IPv6
41

42.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Open Shortest Path First
OSPF
Протокол состояния канала связи
Использует алгоритм Дейкстры
Метрика учитывает пропускную
канала и задает его стоимость
способность
• Метрика = относительная пропускная способность
/пропускную способность канала
• Бесконечность равна 224 —1
Хранит резервный маршрут для сети
Hello интервал 10 с., Dead интервал 40 с.
42

43.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Версии OSPF
OSPFv2
• Работа в сетях IPv4
OSPFv3
• Работа в сетях IPv6
43

44.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Структура Интернет
Магистральный оператор
Магистральный оператор
Магистральный оператор
Сеть
предприятия
Региональный
оператор
Локальный
оператор
Региональный
оператор
Локальный
оператор
Региональный
оператор
Локальный
оператор
Сеть
предприятия
Сеть
предприятия
Индивидуальные клиенты
44

45.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Особенности Интернет
Интернет – объединение сетей
Сети строятся разными организациями
• Разные люди управляют сетью внутри организаций
• Разные политики маршрутизации
Необходим протокол, учитывающий особенности
Интернет
• Маршрутизация в составной сети,
независимо управляемых подсетей
• Учет политик маршрутизации
состоящей
из
45

46.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Внутри- и междоменная маршрутизация
Граничный
маршрутизатор
OSPF
BGP
Граничный
маршрутизатор
Граничный
маршрутизатор
BGP
Граничный
маршрутизатор
OSPF
OSPF
BGP
Граничный
маршрутизатор
46

47.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Тип сервиса «Transit»
Интернет
Сеть 2
Сеть 1
Сеть 3
47

48.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Тип сервиса «Peer»
Интернет
Сеть 2
Сеть 1
Сеть 3
48

49.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Автономная система
Autonomous System (AS)
Одна
или
несколько
администрированием
сетей
с
единым
или
крупным
• Часто принадлежат одному провайдеру
• Имеет свой номер
• Включает адреса IP-сетей (префиксы)
Выдает номера (ASN) IANA
• RIR выдают номера
организациям
провайдерам
49

50.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Номер автономной системы
AS УрФУ - 5468 (26046 – у бывшего УрГУ)
16-битные номера (0 – 65536)
• До 2007 года
• От 64512 до 65534 – приватные номера AS
• Исчерпание доступного диапазона
32-битные номера
• RFC 4893
• 65536-4294967295 (232)
Используется в BGP–маршрутизации
50

51.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Border Gateway Protocol
BGP – протокол граничного шлюза
Используется для вычисления
маршрутов в Интернет
Использует
вектору
алгоритм
междоменных
определения
пути
по
• Разновидность Distance Vector
• Метрика – вектор (path vector)
51

52.

Сети и системы телекоммуникаций. Протоколы маршрутизации
BGP-маршрутизация
Разные
провайдеры
автономные системы
используют
разные
Маршрутизаторы на границе AS анонсируют BGP
маршруты до других маршрутизаторов
Каждый анонс содержит префикс, вектор пути
(path vector), следующий маршрутизатор
• Вектор пути – список AS по пути до префикса
Выбор маршрута на основе политик
В
качестве
адресов
автономных систем
используются
номера
52

53.

Сети и системы телекоммуникаций. Протоколы маршрутизации
BGP
53

54.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Итоги
Место протоколов маршрутизации в моделях OSI и
TCP/IP
Маршрутизация по вектору расстояний
Маршрутизация с учетом состояния канала
Протоколы внутренней маршрутизации (RIP, OSPF)
Структура Интернет
Протокол внешней маршрутизации BGP
54

55.

Сети и системы телекоммуникаций. Протоколы маршрутизации
Вопросы?
55