Определение кратчайшего пути от одного узла до другого | Выбор сетевого оборудования. Обзоры, настройка, сравнение характеристик. | Ofisp.org

Определение кратчайшего пути от одного узла до другого

Для определения кратчайшего пути от одного узла до другого Дейкстра предложил следующий алгоритм. Топология сети представляется в виде неориентированного графа с указанными для каждого ребра значениями метрики (например, расстояния между двумя соседними узлами). Изначально путь неизвестен, поэтому все вершины графа получают метки с бесконечным значением расстояния до отправителя. Метки могут быть временными или постоянными.

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

Похожие материалы

24.12.2013
В качества примера мы рассмотрим определение таблицы на маршрутизаторе компании Morning Star с тремя интерфейсами: одним интерфейсом Ethernet, последовательным портом, подключенным к внешнему модему, и интерфейсом глобальной сети frame relay (см. Таблицу).
24.12.2013
Согласно определению крупнейшего производителя маршрутизаторов компании Cisco - "это устройство третьего уровня, использующее одну и более метрик для определения оптимального пути передачи сетевого трафика на основе информации сетевого уровня". По существу маршрутизатор представляет собой компьютер с необходимым программным обеспечением и устройствами ввода/вывода. В простейшем случае маршрутизатор имеет два сетевых интерфейса. Так, например, для организации связи филиала с главным офисом зачастую достаточно маршрутизатора с одним интерфейсом Ethernet и одним интерфейсом глобальной сети.
24.12.2013
Алгоритм маршрутизации - это часть программного обеспечения маршрутизатора, отвечающая за выбор выходной линии, на которую поступивший пакет должен быть передан. Алгоритмы маршрутизации можно разделить на две большие группы: неадаптивные (статические) и адаптивные (динамические). В случае статических алгоритмов выбор маршрутов осуществляется заранее и прописывается вручную в таблицу маршрутизации, где хранится информация о том, на какой интерфейс отправить пакет с соответствующей адресной информацией.
24.12.2013
В предшествующем разделе под словом "маршрутизатор" подразумевался прежде всего IP-маршрутизатор, т. е. что он предназначен только для продвижения IP-пакетов. Однако маршрутизаторы могут работать и с пакетами других протоколов сетевого уровня, например с IPX. Таким образом, кроме IP-маршрутизаторов есть еще IPX-маршрутизаторы и др.
24.12.2013
Основная масса IPсетей может быть выстроено при помощи всего 2-ух типов приборов: коммутаторов (концентраторов) и маршрутизаторов. Назначение первых мы уже разбирали, наступило время пообщаться о вторых – маршрутизаторах. В этой статье пойдет речь про то, что же такое маршрутизатор и для чего он необходим. Коммутаторы позволяют совместить сетевые приспособления в общий сегмент сети с единой IP адресацией (например, у нас есть компьютер с адресом 172.20.20.20/24 и 172.20.20.21/24, просто втыкаем их в коммутатор и они уже видят друг друга – образуют единый сегмент сети).

Оборудование:

Общие характеристики Тип: Wi-Fi точка доступа Стандарт беспроводной связи: 802.11n, частота 2.4 ГГц...
→ Оставить отзыв
Для начала давайте определим что такое IPTV и мини-роутер. Мини-роутер (маршрутизатор) – сетевое...
→ Оставить отзыв
Подключение При подключении нового роутера к сети интернет необходимо подключить кабель провайдера...
→ Оставить отзыв
Сначала – посмотрим, что такое Wi-Fi 3G роутер вообще, и чем такие решения лучше «модемов». В...
→ Оставить отзыв