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

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

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





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

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

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

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

 

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

 

Наиболее распространенными стандартными алгоритмами решения задачи нахождения кратчайшего пути на графе являются: алгоритм Беллмана-Форда, алгоритм Дийкстра и алгоритм Флойда-Уоршела [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. Нарушение авторских прав; Мы поможем в написании вашей работы!




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


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


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


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

СПИД: морально-этические проблемы Среди тысяч заболеваний совершенно особое, даже исключительное, место занимает ВИЧ-инфекция...

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

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

ТРАНСПОРТНАЯ ИММОБИЛИЗАЦИЯ   Под транспортной иммобилизацией понимают мероприятия, направленные на обеспечение покоя в поврежденном участке тела и близлежащих к нему суставах на период перевозки пострадавшего в лечебное учреждение...

Кишечный шов (Ламбера, Альберта, Шмидена, Матешука) Кишечный шов– это способ соединения кишечной стенки. В основе кишечного шва лежит принцип футлярного строения кишечной стенки...

Принципы резекции желудка по типу Бильрот 1, Бильрот 2; операция Гофмейстера-Финстерера. Гастрэктомия Резекция желудка – удаление части желудка: а) дистальная – удаляют 2/3 желудка б) проксимальная – удаляют 95% желудка. Показания...

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