Эвристическая маршрутизация
Эвристическая маршрутизация — это система, используемая для описания того, как осуществляется доставка при возникновении проблем в топологии сети . Эвристика — прилагательное, используемое по отношению к методам обучения, открытий или решения проблем. Маршрутизация — это процесс выбора путей к конкретным пунктам назначения. Эвристическая маршрутизация используется для трафика в телекоммуникационных сетях и транспортных сетях мира.
Эвристическая маршрутизация достигается с помощью специальных алгоритмов для определения лучшего, хотя и не всегда оптимального, пути к месту назначения. Когда происходит сбой в топологии сети, программное обеспечение, работающее на сетевой электронике, может рассчитать другой маршрут к желаемому пункту назначения по альтернативному доступному пути.
По мнению Шустера и Шура (1974 , стр. 1):
Эвристический подход к решению проблем состоит из применения человеческого интеллекта, опыта, здравого смысла и определенных эмпирических правил (или эвристики) для разработки приемлемого, но не обязательно оптимального решения проблемы. Конечно, определение того, что представляет собой приемлемое решение, является частью задачи принятия решения о том, какой подход использовать; Но в широком смысле приемлемое решение — это решение, которое является достаточно хорошим (близким к оптимальному) и получено в разумных пределах усилий, времени и затрат. Часто требуемые усилия (человеческие, компьютерные и другие ресурсы), временные ограничения на то, когда решение необходимо, а также стоимость сбора, обработки и анализа всех данных, необходимых для детерминированных или других сложных процедур, исключают их полезность или способствуют более быстрый и простой эвристический подход. Таким образом, эвристический подход обычно используется, когда детерминированные методы недоступны, экономичны или практичны.
Эвристическая маршрутизация позволяет измерить оптимизацию маршрутов в телекоммуникационных сетях на основе недавних эмпирических знаний о состоянии сети. Данные, такие как временная задержка , могут быть извлечены из входящих сообщений в течение определенных периодов времени и по различным маршрутам и использованы для определения оптимального маршрута для передачи данных обратно к источникам.
IP-маршрутизация
[ редактировать ]Используемые сегодня протоколы IP-маршрутизации основаны на одном из двух алгоритмов: векторе расстояния или состоянии канала . Алгоритмы вектора расстояния передают информацию о маршрутизации всем соседним маршрутизаторам. Протоколы маршрутизации состояния канала создают топографическую карту всей сети на основе обновлений от соседних маршрутизаторов, а затем используют алгоритм Дейкстры для вычисления кратчайшего пути к каждому пункту назначения. Используемые метрики основаны на количестве переходов, задержке, пропускной способности, трафике и надежности.
Алгоритмы вектора расстояния
[ редактировать ]- RIP использует количество пройденных переходов или шлюзов в качестве показателя.
- IGRP использует пропускную способность, задержку, количество переходов, надежность соединения, нагрузку и MTU.
- EIGRP (DUAL). использует алгоритм диффузного обновления
- BGP использует алгоритм вектора расстояния.
Алгоритмы состояния канала
[ редактировать ]- OSPF использует алгоритм Дейкстры .
См. также
[ редактировать ]- Эвристика (информатика)
- Алгоритм Форда – Фулкерсона
- Алгоритм Беллмана – Форда
- Маршрутизация ограничения поворота
Ссылки
[ редактировать ]- Кэмпбелл, Энн Мелисса; Савелсберг, Мартин (2004). «Эффективная эвристика вставки для решения задач маршрутизации и планирования транспортных средств». Транспортная наука . 38 (3): 369–378. CiteSeerX 10.1.1.499.8006 . дои : 10.1287/trsc.1030.0046 . JSTOR 25769207 .
- Малхотра, Рави (2002). IP-маршрутизация . Севастополь, Калифорния: О'Рейли. ISBN 0596002750 . OCLC 49318657 .
- Робертацци, Томас Г. (2007). Сети и гриды: технология и теория . Информационные технологии: передача, обработка и хранение. Нью-Йорк: Спрингер. дои : 10.1007/978-0-387-68235-8 . ISBN 9780387367583 . OCLC 76935739 .
- Шустер, Кеннет А; Шур, Деннис А. (1974). Эвристическая маршрутизация для автомобилей, вывозящих ТБО . Публикация по охране окружающей среды (SW-113) из серии по обращению с твердыми отходами. Вашингтон, округ Колумбия: Агентство по охране окружающей среды США . hdl : 2027/mdp.39015040701149 . ОСЛК 3207134 .
В этой статье использованы общедоступные материалы из Федеральный стандарт 1037C . Управление общего обслуживания . Архивировано из оригинала 22 января 2022 г.