Студопедия Главная Случайная страница Обратная связь

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

ПРОБЛЕМА МАРШРУТИЗАЦИИ В ИНФОРМАЦИОННЫХ СЕТЯХ





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

МЕТОДЫ МАРШРУТИЗАЦИИ, ОСНОВАННЫЕ НА ВЫБОРЕ

КРАТЧАЙШЕГО ПУТИ

Большинство реальных алгоритмов маршрутизации так или иначе базируется на выборе кратчайшего пути в графе о той или иной мет­рикой. При этом определение кратчайшего пути может осуществлять­ся как централизованно по имеющейся информации о состоянии сети, так и децентрализовано (распределено) на основе имеющейся в узле информации о состоянии ближайших соседей, когда структура всей сети неизвестна (метод "рельефа").

 

ЦЕНТРАЛИЗОВАННЫЕ АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ

 

Наиболее распространенными стандартными алгоритмами решения задачи нахождения кратчайшего пути на графе являются: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела [1],[10].

Первые два алгоритма находят кратчайшие пути от узла источ­ника ко всем другим узлам, а третий алгоритм находит кратчайшие пути от всех узлов ко всем другим узлам.

Рассмотрим в качестве примера алгоритм Дийкстра. Этот алго­ритм требует, чтобы длины (веса) всех ребер были положительны. Объем вычислений для этого алгоритма значительно меньше, чем у алгоритма Беллмана-Форда.

Основная идея алгоритма - отыскание кратчайших путей в по­рядке возрастания длины пути.

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

Алгоритм работает следующим образом.

Полагаем Р = {1}, Di = 0 Di = d1j " j¹1 при наличии cвязи узла c1.

Шаг I. Поиск следующего ближайшего узла.

Находим узел iÏ P такой, что Di minjÏP Dj

Полагаем Р: PÈ{1}. Еcли Р содержит вcе узлы, то на этом работа алгоритма заканчивается.

Шаг 2. Обновление меток.

Для всех jÏP положить Di min {Dj, Di + dij}

Перейти к шагу I.

Пример использования алгоритма Дийкстра приведен на рис. 2.2.

Число операций, выполняемых алгоритмом Дийкстра на каждом шаге, пропорционально N, а шаги итерируются N-1 раз. Таким обра­зом, объем вычислений в худшем случае пропорционален N2, а не N3, как у алгоритма Беллмана-Форда.

 

 







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




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Этапы трансляции и их характеристика Трансляция (от лат. translatio — перевод) — процесс синтеза белка из аминокислот на матрице информационной (матричной) РНК (иРНК...

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

Метод архитекторов Этот метод является наиболее часто используемым и может применяться в трех модификациях: способ с двумя точками схода, способ с одной точкой схода, способ вертикальной плоскости и опущенного плана...

Типовые ситуационные задачи. Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт Задача 1.У больного А., 20 лет, с детства отмечается повышенное АД, уровень которого в настоящее время составляет 180-200/110-120 мм рт. ст. Влияние психоэмоциональных факторов отсутствует. Колебаний АД практически нет. Головной боли нет. Нормализовать...

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

Признаки классификации безопасности Можно выделить следующие признаки классификации безопасности. 1. По признаку масштабности принято различать следующие относительно самостоятельные геополитические уровни и виды безопасности. 1.1. Международная безопасность (глобальная и...

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