пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

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

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

Алгоритм дистанционно-векторной марштуризации является распределенным, итерационным и асинхронным. Процесс продолжается пока соединенные узлы не перестают обмениваться информацией. Асинхронный поскольку не требует, чтобы все узлы работали в жесткой взаимосвязи. Каждый узел имеет свою таблицу расстояний, строка для адресата и столбец для каждого ближайшего соседа. 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) всем соседям.   Конец цикла.


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