РАСПРЕДЕЛЕННЫЙ АЛГОРИТМ БЕЛЛМАНА-ФОРДА

 

Будем считать, что длина d_ij, каждого ребра графа сети поло­жительна. В принципе длина d_ij, может изменяться во времени, но примем, что все изменения в сети произошли до момента t₀ и оста­ются фиксированными после него, по крайней мере, до построения кратчайшего маршрута.

 

 

 

Исходный граф сети

А)

 

P={1,2} P={1,2,5}

 

б)в)

 

 

г)д)

 

P={1,2,5,3,4} P={1,2,5,3,4,6}

Рис. 2.2.

 

Пусть известно D_i кратчайшее расстояние от каждого узла до узла-получателя информации, которым для конкретности будем считать узел 1.

Можно показать, что:

D_i=min [d_ij+D_j], " i¹1, D₁=0. (2.1)

jÎN(i)

Здесь N(i) - множество соседей узла i, т.е. узлов, соединенных с узлом i линией связи.

Асинхронный вариант распределенного алгоритма Беллмана-Форда работает нерегламентированно время от времени (например, при изме­нении d_ij или D_j), выполняя операцию (2.1) в каждом узле i¹1 пе­редавая измененное значение D_i соседям.

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

Особенностью данного алгоритма является то, что для его рабо­ты в узлах сети необходимо хранить очень мало информации и не нуж­ны подробные сведения о топология всей сети - вполне достаточно знать длины уходящих от узла линий и обмениваться о соседями ин­формацией о кратчайших расстояниях D_i на данный момент.

Именно на данном алгоритме маршрутизации был основан перво­начальный алгоритм сети ARPANET, он также близок к алгоритму ис­пользуемого в сети DNA фирмы DEC.

Совокупность значений D_i, образует "рельеф" сети, поэтому рас­сматриваемый метод является разновидностью метода рельефов.