Протоколы маршрутизации
| Вид материала | Задача |
- Применение алгоритмов адаптивной маршрутизации в протоколе igrp, 37.51kb.
- Исследование эффективности алгоритмов маршрутизации в сетях с кп в датаграммном режиме, 394kb.
- Мазмұны, 738.95kb.
- Методические рекомендации по оформлению деловой документации дуз «сказка», 16.42kb.
- Впредставленном курсовом проекте рассматривается глобальная сеть Internet самая крупная, 477.68kb.
- Задача маршрутизации транспорта Целью задачи маршрутизации транспортных средств (Vehicle, 90.34kb.
- Протоколы локальных сетей, 562.81kb.
- Заключение, 9.45kb.
- Примеры тем дипломных проектов и работ, 73.48kb.
- Президиума Совета Минского городского объединения организаций профсоюзов от 24. 07., 58.86kb.
Протоколы маршрутизации.
Основная задача сетей - транспортировка информации от ЭВМ-отправителя к ЭВМ-получателю. В большинстве случаев для этого нужно совершить несколько пересылок. Проблему выбора пути решают алгоритмы маршрутизации.
Алгоритм маршрутизации должен обладать вполне определенными свойствами: надежностью, корректностью, стабильностью, простотой и оптимальностью. Последнее свойство не так прозрачно, как это может показаться на первый взгляд, все зависит от того, по какому или каким параметрам производится оптимизация.
Среди параметров оптимизации может быть минимальная задержка доставки, максимальная пропускная способность, минимальная цена, максимальная надежность или минимальная вероятность ошибки.
Алгоритмы маршрутизации бывают адаптивными и неадаптивными. Вторые, осуществляя выбор маршрута, не принимают во внимание существующую в данный момент топологию или загрузку каналов. Такие алгоритмы называются также статическими. Адаптивные же алгоритмы предполагают периодическое измерение характеристик каналов и постоянное исследование топологии маршрутов. Выбор того или иного маршрута здесь производится на основании этих измерений.
Динамические протоколы:
Distance vector protocols:
В основе лежит алгоритм Форда-Фалкерсона.
Основное преимущество алгоритма вектора расстояний - его простота. Действительно, в процессе работы маршрутизатор общается только с соседями, периодически обмениваясь с ними копиями своих таблиц маршрутизации. Получив информацию о возможных маршрутах от всех соседних узлов, маршрутизатор выбирает путь с наименьшей стоимостью и вносит его в свою таблицу.
Достоинство этого элегантного алгоритма - быстрая реакция на хорошие новости (появление в сети нового маршрутизатора), а недостаток - очень медленная реакция на плохие известия (исчезновение одного из соседей).
Пусть в начальный момент времени маршрутизатор A не был доступен, т. е. расстояние до него во всех таблицах - бесконечность. При включении А пошлет сообщение своему соседу - узлу B. Все остальные маршрутизаторы узнают об этом через последовательный обмен сообщениями (для простоты будем считать, что обмен между всеми соседними узлами происходит синхронно каждые несколько секунд).
Во время первого обмена узел B узнает, что A заработал и вносит в свою таблицу маршрутизации "1" как расстояние до A; все остальные узлы в этот момент по-прежнему считают A недоступным. При следующем обмене, спустя несколько секунд, узел C также узнает о появлении маршрутизатора A. В результате последовательности таких обменов информация достигнет и узла E, для которого стоимость маршрута до А будет "4".
Таким образом, для сети с максимальной длиной маршрута N сообщение о новом маршрутизаторе дойдет до самого удаленного узла в сети через N-1 циклов обмена таблицами маршрутизации. На этом этапе никаких проблем не возникает.
Теперь мы рассмотрим обратный случай (см. Рисунок 2), когда узел А перестает работать вследствие сбоя. При очередном обмене (мы будем считать его первым в этой серии) узел В не получает никакого сообщения от молчащего маршрутизатора А. Это верный сигнал о том, что у А возникли проблемы, и информацию о нем необходимо удалить из таблицы. Однако в то же самое время узел C сообщает, что ему известен путь до А и стоимость этого пути "2". Тот факт, что путь до А, объявленный узлом C, проходит через сам B (т. е. образуется петля), ускользает от внимания маршрутизатора, и он заносит в таблицу путь до неработающего А стоимостью "3".
Во время следующего обмена C замечает, что оба его соседа рекламируют путь до A стоимостью "3", и немедленно делает поправки в своей таблице. Теперь длина пути от С до A - "4". Если этот процесс не остановить, то он может продолжаться до бесконечности, и никто так и не узнает, что маршрутизатор А давно вышел из строя. Соответственно данные к А будут посылаться и дальше.
Эта проблема алгоритма вектора расстояний получила название проблемы возрастания до бесконечности (count-to-infinity problem). Она является основной причиной задания ограничений на максимальную длину пути во всех протоколах вектора расстояния.
Протокол RIP, например, считает маршрут длиной более чем в 15 транзитных узлов бесконечным. Такой путь будет немедленно удален из таблицы маршрутизации. Т. е. в последнем примере узел B поймет, что узел А недоступен, когда получит объявление пути до А со стоимостью "15". К сожалению, такая процедура занимает слишком много
Link state protocols
Развитие Internet привело к необходимости создания более гибкого и эффективного протокола маршрутизации для обслуживания крупных сетей. По замыслу создателей, протоколы состояния канала должны были решить характерные для протоколов вектора расстояний проблемы. Однако, в отличие от протоколов вектора расстояния, протоколы состояния канала сложны и требовательны к ресурсам маршрутизаторов. Основу протоколов состояния канала составляет алгоритм предпочтения кратчайшего пути, созданный в 1978 году.
Формальное описание протоколов состояния канала достаточно запутанно и может занять не один десяток страниц. В упрощенной форме принципы работы маршрутизаторов в соответствии с этим протоколом можно сформулировать в виде пяти несложных правил. Итак, каждый маршрутизатор в сети должен:
- при включении в сеть получить информацию о своих соседях;
- узнать стоимость пути до каждого из соседей (т. е. узнать о состоянии каналов);
- подготовить пакет-объявление, содержащий полученную информацию;
- разослать этот пакет всем соседям;
- построить дерево кратчайших расстояний до всех остальных маршрутизаторов.
Другими словами, маршрутизатору необходимо узнать всю информацию о топологии сети, измерить метрики каналов, соединяющих собственные физические интерфейсы с соседями и далее, вычислить с помощью алгоритма Дейкстры, кратчайшие пути ко всем остальным узлам и внести полученные результаты в таблицу маршрутизации.
1. При подключении сети, маршрутизатор первым делом должен "познакомиться" со своими соседями. Для этого он рассылает через все свои физические интерфейсы специальные пакеты с приветствием HELLO. Получив такой пакет, соседний узел должен ответить, сообщив данные о себе.
2. Узнав данные о соседях, маршрутизатор принимается за второй пункт программы - тестирование каналов связи с целью выяснения метрики каждого канала. Под метрикой может пониматься пропускная способность, время задержки, надежность (количество ошибок на единицу переданной информации), загрузка канала.
Задержку канала можно определить, послав специальный ECHO-пакет, который принимающая сторона должна немедленно отправить обратно. Разделив время отклика пополам, маршрутизатор вычисляет приблизительную величину задержки канала.
3. Шаг номер три в программе маршрутизатора состоит в сообщении полученных знаний остальным. Информация о каналах должна быть разослана соседям.
В процессе работы маршрутизатора пакеты с объявлениями маршрутов рассылаются обычно лишь в случае каких-либо изменений в сети. В остальное же время протоколы состояния канала молчат и не загружают каналы служебной информацией, лишь изредка обмениваясь небольшими HELLO-пакетами
5. После получения информации от всех узлов маршрутизатор может построить "карту" сети. Для этого он создает ориентированный граф, отражающий топологию сети. Соединение "точка-точка" между узлами представляется на графе парой дуг (по одной в каждом направлении), причем стоимости этих дуг могут отличаться друг от друга.
Пакеты, маршрутизаторы, TCP/IP.
Среди множества возможных подходов к решению задачи коммутации абонентов в сетях выделяют два основополагающих:
* коммутация каналов (circuit switching);
* коммутация пакетов (packet switching).
При коммутации каналов коммутационная сеть образует между конечными узлами непрерывный составной физический канал из последовательно соединенных коммутаторами промежуточных канальных участков.
При коммутации пакетов все передаваемые пользователем сообщения разбиваются в исходном узле на сравнительно небольшие части, называемые пакетами.
Далее речь пойдет о коммутации пакетов.
TCP/IP
Физический уровень
Включает физический интерфейс между устройством передачи данных (компьютером) и сетью. Задача этого уровня – установление характеристик среды передачи, природы сигналов, скорости передачи и тд
Уровень доступа к сети
Связан с обменом данными между конечной системой и сетью. Передающий компьютер должен предоставить сети адрес компьютера назначения, что бы сеть могла проложить маршрут передачи данных.
Межсетевой уровень
Задача этого уровня обеспечить связь с сетью и определяет маршрут продвижения данных по сети для двух конечных систем, подключенных к одной сети. Если устройства подключены к различным сетям, то требуется механизм позволяющий переходить из одной сети в другую.На этом уровне работает протокол IP.
Транспортный уровень
На этом уровне обеспечивается надежность доставки данных.
Уровень приложений
Содержит логику необходимую для поддержки различных пользовательских приложений.
Основной целью разработки модели OSI было желание предоставить основу для стандартизации:
- функции уровней разделены – стандарты можно разрабатывать независимо для каждого уровня
- изменения стандартов одного уровня не мешает ПО на других уровнях
По картинке разбор туда-обратно, а походу дела зайдя в маршрутизатор и изменив сетезависемую часть.