Введение
Эвристическая маршрутизация – это система, используемая для описания организации доставки при возникновении проблем в топологии сети. Эвристика – это прилагательное, относящееся к методам обучения, обнаружения или решения проблем. Маршрутизация – это процесс выбора путей к конкретным пунктам назначения. Эвристическая маршрутизация применяется для передачи трафика в телекоммуникационных и транспортных сетях по всему миру. Эвристическая маршрутизация реализуется с помощью специальных алгоритмов для определения более подходящего, хотя и не всегда оптимального, пути к пункту назначения. При возникновении сбоя в топологии сети программное обеспечение, работающее на сетевом оборудовании, может вычислить альтернативный маршрут к нужному пункту назначения по доступной резервной линии. Согласно определению: эвристический подход к решению проблем заключается в применении человеческого интеллекта, опыта, здравого смысла и определенных практических правил (или эвристик) для разработки приемлемого, но необязательно оптимального решения. Разумеется, определение того, что представляет собой приемлемое решение, является частью задачи выбора подходящего подхода; однако, в общем смысле, приемлемое решение – это решение, которое достаточно хорошо (приближено к оптимальному) и получено с разумными затратами усилий, времени и средств. Зачастую требуемые ресурсы (рабочая сила, вычислительные мощности и прочее), ограничения по времени получения решения, а также стоимость сбора, обработки и анализа всех данных, необходимых для детерминированных или других сложных процедур, делают их нецелесообразными и отдают предпочтение более быстрому и простому эвристическому подходу. Таким образом, эвристический подход обычно используется, когда детерминированные методы недоступны, неэкономичны или непрактичны. Эвристическая маршрутизация обеспечивает определенную степень оптимизации маршрутов в телекоммуникационных сетях на основе актуальных эмпирических данных о состоянии сети. Информация, такая как задержка передачи, может извлекаться из входящих сообщений в течение заданных периодов времени и по различным маршрутам, а затем использоваться для определения оптимального маршрута передачи данных обратно к источникам.
The heuristic approach to problem solving consists of applying human intelligence, experience, common sense and certain rules of thumb (or heuristics) to develop an acceptable, but not necessarily an optimum, solution to a problem. Of course, determining what constitutes an acceptable solution is part of the task of deciding which approach to use; but broadly defined, an acceptable solution is one that is both reasonably good (close to optimum) and derived within reasonable effort, time, and cost constraints. Often the effort (manpower, computer, and other resources) required, the time limits on when the solution is needed, and the cost to compile, process, and analyze all the data required for deterministic or other complicated procedures preclude their usefulness or favor the faster, simpler heuristic approach. Thus, the heuristic approach is generally used when deterministic techniques or are not available, economical, or practical. Heuristic routing allows a measure of route optimization in telecommunications networks based on recent empirical knowledge of the state of the network. Data, such as time delay, may be extracted from incoming messages, during specified periods and over different routes, and used to determine the optimum routing for transmitting data back to the sources.
IP-маршрутизация
Протоколы маршрутизации IP, используемые в настоящее время, основаны на одном из двух алгоритмов: алгоритме векторного расстояния или алгоритме состояния канала связи. Алгоритмы векторного расстояния распространяют информацию о маршрутизации среди всех соседних маршрутизаторов. Протоколы маршрутизации состояния канала связи строят топологическую карту всей сети на основе обновлений от соседних маршрутизаторов, а затем используют алгоритм Дейкстры для вычисления кратчайшего пути к каждому получателю. Метрики, используемые для расчетов, основаны на количестве переходов, задержке, пропускной способности, загруженности и надежности.
Алгоритмы состояния ссылки
OSPF использует алгоритм Дейкстры.