Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Маршрутизация, алгоритм Беллмана-Форда (DV).

Читайте также:
  1. Аксиомы алгоритма «Razoom».
  2. Алгоритм
  3. Алгоритм N 1
  4. Алгоритм N 2
  5. Алгоритм введения и изменения заряда точки привязки
  6. Алгоритм выполнения задания
  7. Алгоритм вычисления коэффициента корреляции Пирсона в программе Ехсе1

Для того чтобы переместить пакеты от хоста-отпарвителя к хосту-получателя, сетевой уровень должен определить путь или маршрут следования пакетов. Этим занимается протокол маршрутизации сетевого уровня. Хост напрямую подключен к одному из маршрутихзаторов - маршрутизатор по умолчанию (первого ретрансляционного участка). Задача выбора пути от источника к приемнику сводится к выбору пути пакета от маршрутизатора-источника к маршрутизатору-приемнику - алгоритм маршрутизации. Алгоритм находит «оптимальный» путь (с минимальной стоимостью).Рассмотрим граф: узлы - маршрутизаторы, дуги - линии связи. Каждой линии связи соответствует некоторое значение, представляющее «стоимость» пересылке пакета по этой линии.

Протоколы: общедоступные: RIP, BGP, OSPF; частный: EIGRP.

Глобальный алгоритм маршрутизации находит путь с наименьшей стоимостью от отправителя до получателя с помощью инф о сети. Особенность: обладает полной инф о топологии сети и стоимости линий.

Децентрализованный алгоритм вычисление пути выполняется итерационным распределенным образом. Ни 1 узел не обладает полной инф о стоимости всех линий связи. Изначальна каждому узлу известна стоимость напрямую присоединенных к нему линий, затем, путем итерационных вычислений и обмена инф с соседними узлами, узел постепенно определяет путь с наименьшей стоимостью до получателя или до группы получателей.

Алгоритмы: статические и динамические

В статическом маршруты изменяются со временем очень медленно, чаще всего вручную.

Динамический запускается либо периодически, либо в ответ на изменение топологии или стоимости линий (по протоколу).

Может быть смесь.

Чувствительность протокола маршрутизации: чувствительные реагируют на загруженность линии связи (стоимость линии возросла, а с ней и загруженность) Так не делается, не устойчиво.

В И используются: алгоритм, основанный на состояниях линий и алгоритм дистанционно-векторной маршрутизации.

Децентрализованный алгоритм (Беллмана-форда, дистанционно векторной маршрутизации): основан на рассылке сообщений (при изменении стоимости пути (событие: пришло сообщение от кого-то или изменение стоимости известной линии связи)), асинхронный (управляется событиями), нет явного критерия остановки (после какой-то итерации строка не изменится, новое сообщение посылаться не будет), не требует знания всей конструкции сети.

Алгоритм: y - 2 - x - 1 - z - 7 - y

1. Инициализация: в таблице бесконечности дл диагональных (.) известные длины пути DX(*, V) = INF, DX(V, V) = C(X, V). Для всех адресатов minWD(Y, W).

2. Ожидание события: (пока не придет сообщение, изменение стоимости линии связи)

а. Если изменилась стоимость С(X, V) на d => меняется стоимость в таблице. Для всех адресатов y DX(Y, V) +=d таблица обновляется. Если появился новый min => рассылка всем соседям

б. Если обновление - новое значение от соседа w адресат y. Обновление DX(Y, V) = C(X, V) + newval. Если получается новое min значение, то рассылка всем соседям.

3. Снова ждет пока что-нибудь не случится.

DX Y Z   DX Y Z
Y   INF Y    
Z INF   Z    
   
DY X Z DY X Z
X   INF X    
Z INF   Z    
   
DZ X Y DZ X Y
X   INF X    
Y INF   Y    

На 3 шаге обновлений нет

На практике строится таблица маршрутизации, по которой передаются дейтаграммы, позволяет реагировать на обрывы канала.

Сравнение: 1) скорость схождения: Д: не > N БФ = INF; 2) живучесть (устойчивость к ошибкам) БФ ниже чем у Д; 3) сложность сообщений.

Другие алгоритмы: Алгоритм горячей картофелины (получив сразу выкидывает сообщение в 1 свободный канал, позволяет избежать очередей, может применяться в сетях АТМ) Телефонные алгоритмы коммутированных каналов: канал на кратчайшем, если занят - найти в обход.

 

 


Дата добавления: 2015-08-05; просмотров: 122 | Нарушение авторских прав


Читайте в этой же книге: Протокол HTTP | Аутентификация в HTTP, cookies, условный GET в HTTP. | Протокол FTP. | Протокол SMTP. | Служба имен доменов (DNS). | Протокол UDP. | Протокол TCP. | Установление и разрыв соединения, состояния TCP. | Максимальное время ожидания подтверждения в TCP (timeout) | Сервисы, предоставляемые функциями сетевого уровня. |
<== предыдущая страница | следующая страница ==>
Маршрутизация, термины, алгоритм Дейкстры (LS).| Протокол IP. Адресация и маршрутизация в IP.

mybiblioteka.su - 2015-2024 год. (0.006 сек.)