Лекция №10 Сетевой уровень. Введение. Маршрутизация




НазваниеЛекция №10 Сетевой уровень. Введение. Маршрутизация
Дата конвертации06.02.2013
Размер445 b.
ТипЛекция


КОМПЬЮТЕРНЫЕ СЕТИ

Лекция №10

Сетевой уровень. Введение. Маршрутизация

Сетевой уровень

  • Сетевой уровень решает задачу доставки пакетов от отправителя до получателя

  • Сетевой уровень прокладывает маршрут на всём протяжении следования информации

  • Сетевой уровень должен обеспечить независимость предоставления своих сервисов от низлежащих технологий

  • Сетевой уровень обеспечивает распределение нагрузки на маршрутизаторы и линии связи



Коммутация пакетов с ожиданием



Сетевой уровень

  • Задачи, ставившиеся при разработке сервисов сетевого уровня:

    • Сервисы сетевого уровня не должны зависеть от технологии маршрутизатора
    • Транспортный уровень должен быть независим от количества, типа и топологии присутствующих сетей с маршрутизаторами
    • Сетевые адреса, доступные транспортному уровню, должны использовать единую систему нумерации в локальных и глобальных сетях


Сетевой уровень

  • Первый подход: маршрутизатор только перемещает пакет с места на место, подсеть изначально обладает ненадёжностью и хосты должны сами учитывать ошибки и управлять потоком.

  • Второй подход: надёжный, ориентированный на соединение сервис, с обеспечением качества обслуживания. ATM



Сетевой уровень

  • Дейтаграммные сети, пакеты – дейтаграммы. Internet.

  • Подсети виртуальных каналов, с установкой виртуальных каналов.

ATM.

Реализация сервиса без установления соединения



Реализация сервиса с установкой соединения



Сравнение дейтаграммного подхода и подхода с соединением



Алгоритмы маршрутизации

  • Алгоритмы, определяющие путь прохождения пакетов называются алгоритмами маршрутизации.

  • В дейтаграммной подсети выбор маршрута решается для каждого пакета.

  • В подсети виртуальных каналов маршрут выбирается только при установке канала (сеансовая маршрутизация).

  • Процесс пересылки определяет по таблицам маршрутизации исходящую линию.

  • За заполнение и обновление таблиц отвечает алгоритм маршрутизации.



Алгоритмы маршрутизации

  • Требования к алгоритму:

    • Корректность
    • Простота
    • Надёжность
    • Устойчивость
    • Справедливость
    • Оптимальность


Противоречие справедливости и оптимальности



Алгоритмы маршрутизации

  • Неадаптивные алгоритмы не учитывают при выборе маршрута топологию и текущее состояние сети и не измеряют трафик на линиях. Таблицы маршрутизации формируются на этапе загрузки сети. Статическая маршрутизация.

  • Адаптивные алгоритмы учитывают эти свойства сети



Принцип оптимальности маршрута

  • Принцип оптимальности маршрута.

  • Если маршрутизатор B располагается на оптимальном маршруте от A к С, то оптимальный маршрут от B к С совпадёт с частью оптимального маршрута от А к С.

  • Как следствие, можно рассмотреть множество оптимальных маршрутов в виде дерева, называемого входным деревом.

  • Входное дерево не обязательно уникально.

  • Цель всем алгоритмов выбора маршрутов – построение и использование входных деревьев для всех маршрутизаторов.



Sink tree



Концепция кратчайшего пути

  • Строим граф подсети: узлы – вершины, линии связи – дуги.

  • Вводим веса на дуги (можно брать одинаковые, можно учитывать длину линий и т.д.).

  • Можно учесть среднюю длину очереди, время задержки пересылки, и т.д.

  • При выборе маршрута между двумя маршрутизаторами находим кротчайший путь между ними в графе.

  • Существуют разные алгоритмы поиска кратчайшего пути.



Алгоритм Дейкстры



Метод заливки

  • Статический алгоритм

  • Пришедший пакет посылается на все исходящие линии, кроме той, по которой он пришёл

  • Порождает огромное количество дублированных пакетов. Вводят TTL для борьбы с бесконечной лавиной

  • Можно учитывать все маршрутизаторы, через который проходил пакет

  • Выборочная заливка (определение по косвенным признакам куда пересылать пакет)



Маршрутизация по вектору расстояний

  • Динамический алгоритм

  • Работает, опираясь на таблицу, содержащую наилучшие известные пути к каждому из возможных адресатов.

  • Происходит постоянный обмен этими таблицами с соседями.

  • Алгоритм маршрутизации по вектору расстояний – распределённый алгоритм Беллмана – Форда (Bellman-Ford)

  • Применялся в ARPANET – RIP (Routing Information Protocol)



Маршрутизация по вектору расстояний



Проблема счёта до бесконечности



Маршрутизация с учётом состояния линий

  • Маршрутизация на основе векторов расстояний в ARPANET использовалась до 1979 года

  • Линии начали иметь различную пропускную способность

  • Алгоритм долго приходил к устойчивому состоянию (счёт до бесконечности)



Маршрутизация с учётом состояния линий

  • Маршрутизатор должен:

  • Обнаруживать своих соседей и узнавать их сетевые адреса.

  • Измерять задержку или стоимость связи с каждым соседом.

  • Создавать пакет, со всей собранной информацией.

  • Посылать этот пакет всем маршрутизаторам.

  • Вычислять кратчайший пусть ко всем маршрутизаторам.



Маршрутизация с учётом состояния линий. Знакомство с соседями

  • Посылаем HELO по всем линиям. Маршрутизатор на том конце, должен послать ответ с информацией о себе (имена должны быть уникальны).



Маршрутизация с учётом состояния линий. Измерение стоимости линии

  • Наиболее прямой способ – отправка ECHO всем.

  • Можно учесть загруженность линии (запускать таймер сразу при отправке на канальный уровень)

  • Можно не учитывать (запускать таймер при достижении очереди ECHO на отправка)



Маршрутизация с учётом состояния линий. Измерение стоимости линии



Маршрутизация с учётом состояния линий. Формирование пакетов состояния линий

  • Идентификатор отправителя

  • Порядковый номер

  • Возраст

  • Список соседей с задержками



Маршрутизация с учётом состояния линий. Распространение пакетов состояния линий

  • Основная идея – алгоритм заливки

  • Приходит пакет – смотрим адрес отправителя, если уже есть запись – сверяем порядковые номера

  • Возраст требуется для удаления записей об отключенных маршрутизаторах (например, уменьшается каждый 10 секунд) и предотвратить бесконечное блуждание пакетов (уменьшается при каждой итерации заливки)

  • Для защиты от ошибок – требуем подтверждения получения пакетов состояния линий



Маршрутизация с учётом состояния линий. Распространение пакетов состояния линий



Маршрутизация с учётом состояния линий. Вычисление новых маршрутов

  • Собрав все пакеты состояния линий, маршрутиазтор может построить полный граф подсети. Каждая линия представлена дважды.

  • Далее можно локально применять алгоритм Дейкстры для поиска минимального пути

  • Такой подход используют протокол внутреннего шлюза OSPF (Open Shortest Path First), IS-IS (Intermediate System to Intermediate System)



Иерархическая маршрутизация

  • Размер таблиц маршрутов увеличивается пропорционально увеличению размеров сети

  • Вводят иерархическую маршрутизацию

  • Выделаются области – регионы. Каждый маршрутизатор знает всё только в пределах своего региона.

  • Можно ввести несколько уровней иерархии: кластеры, зоны, группы и т.д.



Иерархическая маршрутизация



Широковещательная маршрутизация

  • Рассылка пакетов по всем пунктам назначения

    • Рассылка всем
    • Заливка
    • Многоадресная маршрутизация (в пакете – все получатели, маршрутизатор генерирует новые пакеты с меньшими списками на линиях, где есть адресаты)
    • Связующее дерево
    • Продвижение по встречному пути


Широковещательная маршрутизация. Продвижение по встречному пути

  • Когда приходит широковещательный пакет, маршрутизатор проверяет, используется ли линия, по которой пришёл пакет для нормальной передачи пакетов источнику широковещания.

  • Если да, то пакет прибыл по наилучшему маршруту и является первой копией. Тогда рассылаем заливкой.

  • Иначе отвергаем.



Широковещательная маршрутизация. Продвижение по встречному пути



Многоадресная рассылка

  • Рассылка сообщений группам адресатов

  • Необходимо управление группами

  • Маршрутизаторы должны знать кто какой группе принадлежит (или хосты оповещают маршрутизаторы, или маршрутизаторы сами опрашивают хосты)

  • Для рассылки маршрутизатор рассчитывает связующее дерево и отсекает ненужные линии к хостам, которых нет в группе, генерируя усечённое связующее дерево

  • При маршрутизации по векторам расстояний, применим алгоритм продвижения по встречному пути (когда нет хостов из группы – отсечка )



Многоадресная рассылка



Алгоритмы маршрутизации для мобильных хостов

  • Есть стационарные и есть мигрирующие (мобильные) хосты

  • У всех хостов есть постоянное местоположение, которое не меняется

  • Внешний агент – следит за мобильными хостами, временно находящимися в его области

  • Внутренний агент – следит за мобильными хостами, покинувшими область местоположения



Алгоритмы маршрутизации для мобильных хостов



Алгоритмы маршрутизации для мобильных хостов

  • Внешний агенту узнаёт о наличии гостя – мобильного хоста

  • Мобильный хост регистрируется в данной области, сообщая внешнему агенту свой домашний адрес, текущий адрес уровня передачи данных, подпись подлинности

  • Внешний агент связывается с внутренним агентом домашней области хоста

  • Внутренний проверяет идентификатор безопасности и разрешает связь

  • Внешний заносит в свою таблицу этот хост



Алгоритмы маршрутизации для мобильных хостов



Маршрутизация в специализированных сетях

  • Мобильны как хосты, так и маршрутизаторы

  • Каждый узел состоит из маршрутизатора и хоста одновременно – специализированная сеть или мобильная специализированная сеть (MANET, Mobile Ad hoc network)

  • Протокол AODV (Ad hoc On-demand Distance Vector)



Маршрутизация в специализированных сетях



Маршрутизация в специализированных сетях

  • Смотрим Адрес источника и идентификатор запроса в локальной истории

  • Приемник ищет адрес назначения в таблице маршрутов. Если маршрут свежий (5 поле в табл. Больше или равно 5 полю в пакете), отправляем reply

  • Если меньше, то inc 6 поле, и посылаем запрос широковещательно.



Поиск в равноранговых сетях. Метод хорды



Поиск в равноранговых сетях. Метод хорды

  • SHA-1 хэш от адреса – 160-ти битное число – идентификатор узла

  • Функция последователя: successor(k) – возвращает идентификатор первого реального узла, следующего после k

  • Названия ресурсов хэшируем, получая ключи (key = hash (name))

  • Строится кортеж из полей name, адрес. Храниться будет на successor(hash(name)).

  • Два направления поиска

  • Таблицы указателей



Алгоритмы борьбы с перегрузкой



Алгоритмы борьбы с перегрузкой

  • Методы без обратной связи – предотвратить возникновение перегрузок

  • Методы с обратной связью – с учетом состояния системы:

  • Наблюдение за системой с целью определения где и когда произойдёт перегрузка

  • Передача информации о перегрузке в необходимые места, где можно повлиять на ситуацию

  • Принятие мер по стабилизации системы



Алгоритмы борьбы с перегрузкой

  • Влияющие на перегрузку политики:

  • Транспортный:

    • Политика повторной передачи
    • Политика кэширования пакетов с неверным порядком
    • Политика подтверждений
    • Политика управления потоком
    • Определение тайм-аутов


Алгоритмы борьбы с перегрузкой

  • Сетевой:

    • Виртуальные каналы или дейтаграммы
    • Политика очередей пакетов и обслуживания
    • Политика игнорирования пакетов
    • Алгоритм маршрутизации
    • Управление временим жизни пакетов


Алгоритмы борьбы с перегрузкой

  • Передачи данных:

    • Политика повторной передачи
    • Политика кэширования пакетов с неверным порядком
    • Политика подтверждений
    • Политика управления потоком


Борьба с перегрузкой в подсетях с виртуальными каналами

  • Управление допуском - новые каналы не создаются, пока не исчезнет перегрузка.

  • Прокладка новых каналов мимо проблемных зон

  • Избежание перегрузки путём договорённостей при организации канала – резервирование ресурсов



Борьба с перегрузкой в подсетях с виртуальными каналами



Борьба с перегрузкой в подсетях с дейтаграммным подходом

  • Биты предупреждения во все пакеты

  • Сдерживающие пакеты

  • Сдерживающие пакеты для ретрансляционных участков

  • Сброс нагрузки (игнорирование пакетов)

  • Случайное раннее обнаружение (TCP)

  • Борьба с флуктуациями (среднеквадратичное отклонение времени доставки пакетов)



Похожие:

Лекция №10 Сетевой уровень. Введение. Маршрутизация iconЛекция №11 Сетевой уровень. Качество обслуживания. Объединение сетей. Ipv4
Сетевой уровень. Качество обслуживания Последовательность пакетов, предающихся от источника к приемника, называется потоком
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconIp сетевой уровень модели osi сетевой уровень модели osi
Отвечает за адресацию пакетов и преобразование логических адресов и имен сетевых узлов в физические адреса
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconЛекция №13 Транспортный уровень. Введение. Tcp, udp, sctp
Транспортный уровень. Введение Цель транспортного уровня предоставление эффективных, надежных и экономичных (в плане использования...
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconМаршрутизация пациента Маршрутизация пациента
Министерства Здравоохранения и социального развития РФ в гуз «Консультативно-диагностический центр Республики Коми»
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconПротоколы определяют, происходит ли передача данных через сетевой уровень к верхним уровням эталонной модели osi

Лекция №10 Сетевой уровень. Введение. Маршрутизация iconЯзыки и методы конструирования программ
...
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconЛекция №5 Уровень передачи данных или канальный уровень
Первая фаза. Установка соединения, инициализация переменных и счетчиков для слежения за тем, какие кадры уже приняты, а какие ещё...
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconСетевой анализ для оценки программ и политик Западный и российский опыт
Методология «сетевой анализ» прочно вошла в арсенал политического анализа в последние два десятилетия
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconЛекция 2 План лекции
Основные понятия теории чебышевских сетей: геодезические линии, сетевой угол, угол перекоса
Лекция №10 Сетевой уровень. Введение. Маршрутизация iconМаршрутизация и транспортировка данных Маршрутизация и транспортировка данных по компьютерным сетям
Интернет-пакеты, отправленные первыми, могут достичь компьютера-получателя в последнюю очередь. Например, в процессе передачи файла...
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница