본문 바로가기

IT Tech/Network

[네트워크] CSPF (Constrained Shortest Path First) 동작원리





How CSPF Works



이 글을 보기 전에 먼저  아래글을 읽어보기를 권한다.

2011/06/02 - [Network] - [네트워크] OSPF의 SPF(Shortest Path First) 일반적인 동작 원리





라우팅 프로토콜에 의해서 수행되는 SPF와 MPLS Traffic Enginerring에 의해서 수행되는 SPF 과정엔 크게 두 가지의 차이가 있다. (그러나 크게 다르지 않다.)

첫째는 경로를 결정하는 과정이 Tunnel 종단점까지의 모든 라우터에 대한 최적의 경로를 찾을 필요가 없다. CSPF는 원하는 노드까지의 정보를 얻게되면 바로 종료되도록 slightly하게 수정되었다.

둘째는 노드 사이의 링크에 대한 비용을 계산할 때 기존의 cost에
  • Bandwidth

  • Link attributes

  • Administrative weight

의 상태를 추가 고려한다. 따라서, SPF가 {경로, 비용, 다음 노드}의 세가지 항목을 리스트 노드로 계산했다면 CSPF는 위의 세가지 항목을 추가해서 여섯 개의 필드가 사용된다.


CSPF의 또 다른 차이는 목적지 노드까지의 하나의 경로만 찾는 다는 점이다. Load Sharing 이 없다. 따라서 SPF의 비교치가 모두 같아서 몇 개의 동등한 경로가 계산이 될 경우에 미리 정의된 우선순위에 따라서 하나의 경로를 선택한다.


이해를 돕기 위해서 아래의 토폴로지를 예로 설명한다. 각 라우터 노드 사이의 링크엔 Cost 와 Bandwidth가 명시되어 있다. 좀 더 쉬운 설명을 위해서 CSPF의 계산에 사용될 {link, cost, next hop, available bandwidth} 의 네가지만 가지고 설명을 한다.



위의 토폴로지에서 라우터 A는 라우터 D와 최소 BandWidth(이하 BW) 60Mbps의 TE tunnel을 만들고 싶어한다고 가정하자.

BW의 고려가 없다면 최적의 경로는 비용 12의 ABCD 가 되겠지만 BC 구간이 60Mbps 의 BW를 만족하지 않는다.CSPF는 이러한 BW를 SPF에 포함 시켜야한다.

이것은 실제 매우 간단하다. CSPF의 알고리즘은 아래와 같다.
Step 1. SPF 트리의 root로 PATH 리스트에 자신을 추가한다. 이때 distance 0, next hop 은 self 그리고 BW는 N/A 이다.
Step 2. 조금 전 PATH 리스트에 추가한 노드의 이웃 노드를 찾아서 TENT 리스트에 추가한다. 이 때 이미 존재하고 cost가 더 크거나 주어진 조건(여기서는 BW 60Mbps 이상)을 만족하지 않는 노드는 버린다.
Step 3. TENT 리스트에서 가장 낮은 비용의 노드를 찾아 PATH 리스트로 이동한다. 만약 그 노드가 목적지 노드이거나 TENT 리스트가 empty 이면 중단한다.









이제 예제로 든 토폴로지를 가지고 CSPF를 계산하는 과정을 살펴보자.

Step 1. SPF 트리의 root로 자신 라우터 A의 노드를 PATh 리스트에 추가한다. 이 때 distance 는 0, next hop은  "self" 그리고 BW는 N/A의 값으로 설정한다.

PATH ListTENT List
{A,0,self,N/A} (empty)


Step 2. PATH 리스트에 조금 전 추가한 노드 라우터 A의 이웃 노드를 찾아서 TENT 리스트에 추가한다.

PATH ListTENT List
{A,0,self,N/A} {B,5,B,100}
  {C,10,C,100}

노드 A와 직접 연결된 {B,5,B,100}, {C,10,C,100} 가 TENT 리스트에 추가됨.

Step 3. TENT 리스트에서 Cost가 더 작은 {B,5,B,100} 를 PATH 리스트로 이동하고 노드 라우터 B의 이웃 노드를 TENT 리스트에 추가한다.

PATH ListTENT List
{A,0,self,N/A} {C,10,C,100}
{B,5,B,100} {D,13,B,90}
{C,8,B,50} was not added to the TENT list because it doesn't meet the minimum bandwidth requirement.

이때, {C,8,B,50}는 BW 조건(60Mbps)을 만족하지 못하므로 버린다.

Step 4. TENT 리스트에서 Cost가 가장 작은 C,10,C,100}를 PATH 리스트로 옮기고 그 노드의 이웃 노드를 TENT 리스트에 추가한다.


PATH ListTENT List
{A,0,self,N/A} {D,13,B,90}
{B,5,B,100}  
{C,10,C,100}  
{D,14,C,60} is not put on the TENT list because the cost to get to D through B is lower than the cost to get there through C.

{D,14,C,60} 는 이미 TENT 리스트 있는 {D,13,B,90}보다 Cost가 커서 버린다.

Step 5. TENT 리스트에서 마지막 남은 {D,13,B,90}을 PATH 리스트로 옮기고 종료한다. 따라서 라우터 D까지의 경로는 B를 통한 Cost 13의 {D,13,B,90}가 최적의 경로이다.

PATH List TENT List
{A,0,self,N/A}  
{B,5,B,100}  
{C,10,C,100}  
{D,13,B,90}  

실제 경로를 구하는 과정은 link attributes와 같은 경로가 생겼을 경우를 고려해야하기 때문에 여기에 설명한 과정보다 훨씬 복잡하다. 이제 tiebreakers(같은 비용의 경로가 두개 이상 존재할 경우에 대해서 고려해 보자.







Tiebreakers in CSPF

정규 OSPF나 IS-IS에서 사용된는 정규 SPF 에서는 같은 경로의 다중 목적지가 가능하다. 때때로 ECMP(Equal-Coat MultiPath)로 부르고 Load Sharing이 가능하다.

하지만, CSPF에서는 모든 가능한 최적의 경로를 계산하지 않고 오직 하나의 경로만 찾는다.  TENT 리스트에 같은 Cost의 경로가 존재할 경우 하나의 경로를 선택해야한다.

Here are the tiebreakers between paths, in order:
  1. 가장 큰 최소 가용 BW를 가진 노드

  2. 여전히 같은 노드가 존재한다면, Hop 카운트가 작은 노드를 선택한다.

  3. 그래도 같은 노드가 존재한다면, 랜덤하게 선택한다. (랜덤이지만, 리스트의 맨 처음 노드를 선택하기 때문에 같은 DB를 이용해서 계산한다면 매번 같은 노드를 선택하게 된다.)


위의 예제서 조건으로 든 BW를 10Mbps로 낮으면 다음과 같은 Tiebreakers들이 존재하게된다.


이것을 테이블로 정리하면 다음과 같다.


Path NameRouters in PathPath CostMinimum Bandwidth on Path (in Mbps)
P1 RtrARtrL1RtrR1RtrZ 21 100
P2 RtrARtrL2RtrR2RtrZ 19 80
P3 RtrARtrL3RtrM3RtrR3RtrZ 19 90
P4 RtrARtrL4RtrR4RtrZ 19 90
P5 RtrARtrL5RtrR5RtrZ 19 90


이중 하나의 경로를 선택하는 과정은 다음과 같다.

  • P1 은 가장 큰 Path Cost를 가지므로 사용하지 않는다.

  • P2 는 Minimum BW가 작으므로 사용하지 않는다.

  • P3 는 다른 경로보다 Hop 카운트(4)가 커서 사용하지 않는다.

  • P4와 P5가 모든 조건이 같다. 라우터 A는 TENT 리스트의 위에 있는 P4를 선택한다.








CSPF에 영향을 주는 요소들..

Bandwidth, Link Attributes, Administrative Weight 의 요소들은 매우 직관적으로 CSPF 계산에 반영되는 요소들이다.

위에서 얘기한 것처럼 필요한 Bandwidth는 매우 직관적으로 필요한 Bandwidth를 만족하지 못하면 MPLS TE tunnel을 위해 사용하지 않는다.

Link Attributes또한 Bandwidth와 비슷하다. 설정된 affinity bits와 정확히 매치하는지를 고려한다.

Administrative weight 는 TE 정보가 플러딩 될때 IGP에 의해서 전달된다. 기본적으로 이 값은 오직 터널의 경로를 계산하는데 사용되지만 특정 링크에 필요한 유연성(가중치?)배제하기 위해 변경할 수 있다. (정확히 이해가 안감 아래 원문 참조)
(By default, only the administrative weight is used to calculate a tunnel's path. However, just being able to change the administrative weight for a particular link might not give you the flexibility you need.)

IGP의 메트릭 값은 대게 Bandwidth에서 추출된다. OSPF의 경우, default link metric은 reference-bandwidthlink bandwidth로 나눈 값이다. 시스템에서 기본적으로 사용하는 referencd-bandwidth는 108 (100Mbps가 cost 1)이고, IS-IS의 경우 default link cost는 10이다.

이처럼 OSPF와 IS-IS 모두 링크의 bandwidth를 기준으로 메트릭을 계산한다. 이것은 데이타를 위한 네트워크에서는 꽤 잘 동작한다. DiffServ Queue와 결합한 TCP congestion-control 매카니즘에서 사용 가능한 최대의 Bandwidth를 쓸 수 있는 장점이 있다.


하지만 음성 데이타의 경우엔?
음성의 경우엔 실제 대역폭보다는 지연에 의한 끊김에 더 민감하다.
이때 link metric값으로 Bandwidth 보다 지연(delay)값을 기준으로 하도록 조정할 수 있다. 주의해야할 점은 이렇게 할 경우 정확한 데이타 경로 배정의 능력을 잃게되어 망에 심각한 영향을 줄 수 도 있다.


음성을 처리하기 위한 경로 배정을 알아보기 위해 아래 토폴로지를 보자.


여기 RtrA 와 RtrZ 사이에 3개의 경로가 있다.

  • P1 은 OC3 satellite 을 이용하고, 150Mbps지만 지연률이 높다.

  • P2 는 OC3 land line, 지연률이 낮지만 이용가능한 bandwidth가 없다.

  • P3 는 DS3 land line, 45 Mbps의 대역폭과 지연률이 낮다.


데이타의 특성에 따라 즉, 상활에 맞게 경로를 선택한다.

MPLS Traffic Engineering은 링크의 대역폭과 딜레이 모두 고려할 수 있다. Voice를 위한 터널은 데이타 터널이 사용하는 메트릭값으로부터 cost를 분리해서 딜레이의 고려가 가능하다.
Step 1. 명령어를 사용해서 링크의 딜레이 값을 설정한다.
 mpls traffic-eng administrative-weight 0-4294967295

Step 2. tunnel-decision 과정에서 링크의 cost를 측정시 TE metric 이 아닌 IGP metric 값을 사용하도록 한다.
 mpls traffic-eng path-selection metric igp  (for global) 
 tunnel mpls traffic-eng path-selection metric igp (for tunnel)
global path-selection metric를 설정한다면, traffic-eng path-selection metric te 를 설정한 터널들의 경우에 한해 TE metric 링크과 관련된 TE 터널들을사용하길 원할 것이다. (햇갈려서 원문 첨부함. If you set the global path-selection metric to IGP, you might want to have some TE tunnels refer to the TE metric link, in which case you configure those tunnels with traffic-eng path-selection metric te.)


administrative weight의 설정과 연결된 고유 단위는 없다. mpls traffic-eng administrative-weight 10을 설정했다면, 10초, 100초, 1000초인지 명확하지 않다.

원하는 단위가 무엇이든지 다음과 같은 이유로 일반적으로 밀리초로 인코딩을 하기를 권한다.

  • TE metric은 32비트(0 ~4,294,967,295)의 크기이다. 4,294,967,295 밀리초는 대략 7주에 해당된다.

  • 대부분의 VoIP 응용프로그램들이 지연값을 밀리초단위로 설정한다.

  • 밀리초 보다 더 큰 단위를 사용하는 특정 회선에서 end-to-end 지연의 양을 결정하기가 매우 어렵다.






[참고 서적]
Traffic Engineering with MPLS by CISCO Press