пользователей: 21258
предметов: 10464
вопросов: 177980
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

I семестр:
» Сети ЭВМ

Алгоритмы маршрутизации. Сравнение алгоритмов маршрутизации. Алгоритм дистанционно-векторной марштуризации

для всех узлов V; Если V смежный с А; D(v)=C(A,v) иначе D(v)=бесконечности.

Цикл: Найти W, не входящий в N, такой что D(W) минимальна. Добавить W к N. Обновить D(v) для всех v смежных с W и не входящих в N: D(v)=min(D(v), D(W), D(W,v)). По всем узлам в N.  

 

Алгоритм дистанционно-векторной марштуризации является распределенным, итерационным и асинхронным. Процесс продолжается пока соединенные узлы не перестают обмениваться информацией. Асинхронный поскольку не требует, чтобы все узлы работали в жесткой взаимосвязи. Каждый узел имеет свою таблицу расстояний, строка для адресата и столбец для каждого ближайшего соседа. Dx(y,z)=C(x,z)+minw(Dz(y,w)).

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

Алгоритм инициализация: Для всех всех смежных узлов V: Dx(*,v)=бесконечности // *-любой узел. Dx(v,v)=C(x,v).  Для всех адресатов Y- послать minwD(y,W) каждому соседу.

Цикл:

Ждать(пока не изменится стоимость ЛС с соседом v или пока не будет получено обновление от соседа v). Если (стоимость C(x,v) изменилась на d) /*изменение стоимости путей ко всем адресам через соседа v на величину d*/     /*d-может быть как положительным так и отрицательным*/  Для всех адресов Y:  Dx(y,v)= Dx(y,v)+d. Иначе если (получено обновление от v адресат Y)  /* изменение кратчайшего пути от v до Y */     /* Узел v послал новое значение minwDY (Y,W), назовем его newVal  */   для одного адресата y: Dx(Y,v)=C(x,v)+ newVal . Если получим новое значение  minwDX (Y,W) для Y  послать новое значение  minwDX (Y,W) всем соседям.   Конец цикла.

30. Алгоритмы маршрутизации. Сравнение алгоритмов маршрутизации.

Основы маршрутизации:

Определение пути занимается протокол маршрутизации. Задачи выбора пути пакета сводится к задачи от маршрутизатора источника к маршрутизатору приемника.

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

Если рассматривать сеть как граф то узлы графа это маршрутизаторы, а ребра графа- это физические линии связи.

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

При рассмотрение сети в виде графа  для определения маршрута с минимальной стоимостью, необходимо найти последовательность линий такую что:

-первая линия соединена с источником. –последняя линия соединена с адресатом. –для всех i-линий с номерами i и i-1 соединены с одним и тем же узлом. –для пути с минимальной стоимостью сумма стоимостей всех линий пути является минимальной, по всем возможным путям.

Все маршруты можно разбить на 2 класса: 1.Глобальный класс. 2.Детерцентрализованный класс (вычисление пути происходит итерационным, распределенным образом).

 

Алгоритм  Дейкстры  вычисляет путь с наименьшей стоимостью. Алгоритм циклический.

D(v)-стоимость пути от узла источника до узла адресата V минимальная на данной итерации.

P(v)-предыдущий узел  на текущем пути с наименьшей стоимостью от источника до узла V.

N-множество узлов для которых на данной итерации известны пути с наименьшей стоимостью.

1 этап инициализации  N=


20.01.2014; 23:09
хиты: 164
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь