Похожие презентации:
Сети и системы телекоммуникаций. Протоколы маршрутизации
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