Networks2012-04-Routing
.pdfАлгоритм Дэйкстры
O Общее число операций:
O N-1 – число шагов
O N – операций при пересчете оценок на каждом шаге
O W = O(N2)
O Достоинства алгоритма:
O Высокая скорость (~N2)
O Недостатки алгоритма:
O Плохо распараллеливается
O Требуется иметь информацию о топологии всей сети O Требует существенных ресурсов памяти (~N2)
Ицыксон В.М. ТКС © 2012 |
41 |
Автономные системы
O Автономная система – AS
O AS имеет уникальный номер
O AS:
OЧасть сети, управляющаяся из одного центра управления
O Реализующая одну политику маршрутизации
OВнутри AS обеспечиваются одинаковые протоколы маршрутизации
Ицыксон В.М. ТКС © 2012 |
42 |
Автономные системы
Ицыксон В.М. ТКС © 2012 |
43 |
Автономные системы
O Протоколы маршрутизации внутри AS
O Внутренние протоколы маршрутизации
O IGP – Interior Gateway Protocol
O Протоколы маршрутизации между AS
O Внешние протоколы маршрутизации
O EGP – Exterior Gateway Protocol
Ицыксон В.М. ТКС © 2012 |
44 |
Протоколы маршрутизации
O Характеристики протоколов маршрутизации
O Название
O Стандартизирующие документы O Алгоритм поиска маршрута
O Метрика протокола O Сходимость
O Избежание петель маршрутизации O Загрузка сети
O Ресурсоёмкость
O Поддержка нескольких маршрутов на сеть O Аутентификации
O Ограничения применения O Конфигурирование
O Поддержка в маршрутизаторах O Достоинства
O Недостатки
Ицыксон В.М. ТКС © 2012 |
45 |
Протоколы маршрутизации. Метрики маршрутов
O Метрика маршрута может зависеть от:
O Числа промежуточных маршрутизаторов O Пропускной способности канала связи
O Задержек в канале связи
O Надежности канала связи O Загрузки канала связи
Ицыксон В.М. ТКС © 2012 |
46 |
Сходимость протоколов маршрутизации
O Сходимость протокола – способность протокола оперативно реагировать на изменения в сети и приводить маршрутизаторы к соответствующее состояние
O Время сходимости – время за которое маршрутные таблицы переходят в состояние, адекватное изменившейся ситуации сети
Ицыксон В.М. ТКС © 2012 |
47 |
Внутренние протоколы маршрутизации
O Внутренние протоколы маршрутизации:
O RIP
O OSPF
O IGRP
O EIGRP
O IS-IS
O ….
Ицыксон В.М. ТКС © 2012 |
48 |
Протокол маршрутизации RIP
O RIP - Routing Information Protocol
O Разработан в 1980х
O Используется в TCP/IP, Novell O Стандарт RFC 1058, 1988 год
O Алгоритм вычисления маршрута – БэллманаФорда
O Тип протокола - однопутевой
Ицыксон В.М. ТКС © 2012 |
49 |
RIP. Метрика
O Целое число из диапазона 0..15
O Измеряется числом промежуточных маршрутизаторов до сети назначения
O Для непосредственно подсоединенных сетей – значение «0»
O Значение «16» – сеть недоступна
Ицыксон В.М. ТКС © 2012 |
50 |