Control Plane - Routing Protocols

Routing Protocols

- 자고로 라우팅 프로토콜이라 함은, 패킷을 호스트에서 호스트로 보내는데에 있어서 최적의 경로를 찾는 것을 의미한다. 이때 최적이란 "비용이 적고, 빠르고, 덜 혼잡한" 것을 의미한다고 볼 수 있다.

 

- 이때, 라우터들 간의 경로를 찾을때는 그래프가 사용된다. 또한 각각의 링크에는 코소트를 붙여서 계산하게 된다. 이때, Ca_b를 a와 b사이에 직접적인 연결 비용이라 한다. (만약 Ca_b가 infinity면 직접적으로 접근하는 경로 X)

Dijkstra's link-state routing alogrithm

- 만약 네트워크의 link cost가 모든 노드들에게 알려져 있고, 각각이 동일하다고 가정해보자. 그러면 한 노드에서 다른 노드로 가는데 까지 걸리는 최소한의 cost를 계산할 수 있을 것이다. (이때 k번의 반복 이후 알게 될 수 있다.)

- 여기서 D(V)는 Source에서 V까지 가는데 걸리는 최소한의 예상 비용을 표기한 것이고, P(V)는 V까지 가는데에 있어서의 전 노드를 의미한다. (위 사진을 참고하면, 더욱 이해가 쉬울 것이다.)

- Dijkstra Algorithm은 Step에 따라 진행 된다. 먼저 Step 0에서 N'에 Soure Node를 작성한다. 그리고 해당 행에 있는 모든 D('), p(')를 작성한다. 그 다음으로 셀중 가장 적은 D(')를 가지는 element를 Source Node에 붙여서 Step1의 N'으로 넘긴다.

- 이후로 모든 노드에 대해 작성 될 때 까지 해당 과정을 반복해서 진행하며 (k번의 반복) 이후 완성되면 각각의 열중 가장 작은 D(')가 해당 열에 대응되는 노드까지의 최소한의 거리가 된다.

 

- 다만 Dijkstra Algorithm을 사용하면 경로가 주기적으로 흔들릴 수 있는(Route Oscillations)데, 이는 Traffic 변동으로 Link State가 변화함에 따라서 정보 교환이 빠르게 일어나 그때마다 계산, Route를 갱신하기 때문이다.

 

Distance Vector Alogrithm

- Distance Vector Algorithm은 X에서 Y까지의 가는 최소한의 경로를 Cx_v + D_v(y)의 합들 중 가장 작은것으로 정하게 된다. 이때 v는 Source Node의 모든 이웃들에 해당하게 된다고 볼 수 있다.

- 그리고 시간마다 각각의 노드는 자신의 Distance Vector(D_V(y))를 이웃들에게 보내게 되고, 새 DV를 받은 이웃들은 다시 위 공식에 따라서 DV를 계산하게 된다. 즉 Local link Coat가 변했거나, 이웃들로 부터 DV 정보를 받게 되면 계산이 새로 일어난다.

- 다만 이웃들은 DV가 변했을 경우에만 정보를 전달한다는 점에 유의해야 한다.

 

위 문장에 대한 설명

- 다만 문제는 Link Cost가 줄어드는 등 "좋은 소식"은 빠르게 퍼지나, Link Cost가 증가하는 등 "나쁜 소식"은 느리게 변하게 되는데, 이에 대해서는 아래 슬라이드의 예시를 참조하자.

 

 

---

Ref : Computer Networking - A top down approach