Студопедия — РАСПРЕДЕЛЕННЫЙ АЛГОРИТМ БЕЛЛМАНА-ФОРДА
Студопедия Главная Случайная страница Обратная связь

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

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






 

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

 
 

 

 


 

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

А)

       
   
 
 

 


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

 

б)в)

 
 

 

 


г)д)

 

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

Рис. 2.2.

 

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

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

Di=min [dij+Dj], " i¹1, D1=0. (2.1)

jÎN(i)

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

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

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

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

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

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

 







Дата добавления: 2015-03-11; просмотров: 875. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

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

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

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Философские школы эпохи эллинизма (неоплатонизм, эпикуреизм, стоицизм, скептицизм). Эпоха эллинизма со времени походов Александра Македонского, в результате которых была образована гигантская империя от Индии на востоке до Греции и Македонии на западе...

Демографияда "Демографиялық жарылыс" дегеніміз не? Демография (грекше демос — халық) — халықтың құрылымын...

Субъективные признаки контрабанды огнестрельного оружия или его основных частей   Переходя к рассмотрению субъективной стороны контрабанды, остановимся на теоретическом понятии субъективной стороны состава преступления...

Правила наложения мягкой бинтовой повязки 1. Во время наложения повязки больному (раненому) следует придать удобное положение: он должен удобно сидеть или лежать...

ТЕХНИКА ПОСЕВА, МЕТОДЫ ВЫДЕЛЕНИЯ ЧИСТЫХ КУЛЬТУР И КУЛЬТУРАЛЬНЫЕ СВОЙСТВА МИКРООРГАНИЗМОВ. ОПРЕДЕЛЕНИЕ КОЛИЧЕСТВА БАКТЕРИЙ Цель занятия. Освоить технику посева микроорганизмов на плотные и жидкие питательные среды и методы выделения чис­тых бактериальных культур. Ознакомить студентов с основными культуральными характеристиками микроорганизмов и методами определения...

САНИТАРНО-МИКРОБИОЛОГИЧЕСКОЕ ИССЛЕДОВАНИЕ ВОДЫ, ВОЗДУХА И ПОЧВЫ Цель занятия.Ознакомить студентов с основными методами и показателями...

Studopedia.info - Студопедия - 2014-2024 год . (0.009 сек.) русская версия | украинская версия