Введение
Constrained Shortest Path First (CSPF) - это расширение алгоритмов кратчайшего пути. Путь, вычисленный с помощью CSPF, является кратчайшим путем, выполняющим набор ограничений. Это просто означает, что он запускает алгоритм кратчайшего пути после обрезки тех ссылок, которые нарушают данный набор ограничений. Ограничением может быть минимальная полоса пропускания, требуемая для каждого звена (также известная как гарантированное ограничение полосы пропускания), задержка от конца до конца, максимальное количество пересеченных звеньев, включение/исключение узлов. CSPF широко используется в MPLS Traffic Engineering. Маршрутизация с использованием CSPF известна как Маршрутизация на основе ограничений (CBR). Путь, вычисленный с использованием CSPF, может быть точно таким же, как и путь, вычисленный с OSPF и IS IS, или он может быть совершенно другим в зависимости от набора ограничений, которые должны быть выполнены.
Пример с ограничением по полосе пропускания
Рассмотрим сеть справа, где маршрут должен быть вычислен от маршрутизатора А до маршрутизатора 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.
If x = 55 units then CSPF will give path A → D → E → C.
If x = 90 units then CSPF will give path A → D → E → F → C.
In all of these cases OSPF and IS IS will result in path A → B → C.
However, if the link costs in this topology are different, CSPF may accordingly determine a different path. For example, suppose that as before, hop count is used as link cost for all links but A → B and B → C, for which the cost is 4. In this case:
If x = 50 units then CSPF will give path A → D → E → C.
If x = 55 units then CSPF will give path A → D → E → C.
If x = 90 units then CSPF will give path A → D → E → F → C.