제한된 최단 경로 우선

제한된 최단 경로 우선(CSPF)은 최단 경로 알고리즘의 확장이다.CSPF를 사용하여 계산된 경로는 일련의 제약조건을 충족하는 최단 경로다.그것은 단순히 주어진 제약조건을 위반하는 링크들을 분리한 후에 최단 경로 알고리즘을 실행한다는 것을 의미한다.제약조건은 링크당 필요한 최소 대역폭(대역폭 보장 제약조건이라고도 함), 엔드투엔드 지연, 통과된 최대 링크 수, 포함/제외 노드일 수 있다.CSPF는 MPLS 트래픽 엔지니어링에서^{[citation needed]} 널리 사용된다.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는 그에 따라 다른 경로를 결정할 수 있다.예를 들어, 이전과 같이 홉 카운트는 비용이 4인 A → B 및 B → C를 제외한 모든 링크의 링크 비용으로 사용된다고 가정합시다.이 경우:

x = 50 단위일 경우 CSPF는 경로 A → D → E → C를 제공한다.

x = 55 유닛이면 CSPF는 경로 A → D → E → C를 제공한다.

x = 90 단위일 경우 CSPF는 경로 A → D → E → F → C를 부여한다.

참조

• Ziegelmann, Mark (2007). Constrained Shortest Path and Related Problems. Constrained Network Optimization. VDM Verlag Dr. Müller. ISBN 978-3-8364-4633-4.