Сначала ограниченный кратчайший путь
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Ограниченный алгоритм поиска кратчайшего пути (CSPF) является расширением алгоритмов поиска кратчайшего пути. Путь, вычисленный с помощью CSPF, является кратчайшим путем, удовлетворяющим набору ограничений. Это просто означает, что он запускает алгоритм кратчайшего пути после обрезки тех ссылок, которые нарушают заданный набор ограничений. Ограничением может быть минимальная пропускная способность, необходимая для каждого канала (также известная как ограничение гарантированной пропускной способности), сквозная задержка, максимальное количество пройденных каналов, включение/исключение узлов. CSPF широко используется в MPLS. системе управления трафиком [ нужна ссылка ] . Маршрутизация с использованием CSPF известна как маршрутизация на основе ограничений (CBR).
Путь, вычисленный с помощью CSPF, может быть точно таким же, как путь, вычисленный из OSPF и IS-IS , или может быть совершенно другим в зависимости от набора ограничений, которым необходимо соответствовать.
Пример с ограничением пропускной способности
[ редактировать ]
Рассмотрим сеть справа, где необходимо вычислить маршрут от маршрутизатора-A до маршрутизатора-C, удовлетворяющий пропускной способности, ограниченной x-единицами, а стоимость канала для каждого канала основана на количестве переходов (т. е. 1).
Если x = 50 единиц, CSPF выдаст путь A → B → C.
Если x = 55 единиц, CSPF выдаст путь A → D → E → C.
Если x = 90 единиц, CSPF выдаст путь A → D → E → F → C.
Во всех этих случаях OSPF и IS-IS приведут к пути A → B → C.
Однако если стоимость соединения в этой топологии различна, CSPF может соответственно определить другой путь. Например, предположим, что, как и раньше, количество переходов используется в качестве стоимости канала для всех каналов, кроме A → B и B → C, для которых стоимость равна 4. В этом случае:
Если x = 50 единиц, CSPF выдаст путь A → D → E → C.
Если x = 55 единиц, CSPF выдаст путь A → D → E → C.
Если x = 90 единиц, CSPF выдаст путь A → D → E → F → C.
Ссылки
[ редактировать ]- Зигельманн, Марк (2007). Ограниченный кратчайший путь и связанные с ним проблемы. Ограниченная оптимизация сети . ВДМ Верлаг Доктор Мюллер . ISBN 978-3-8364-4633-4 .