📡 [Network] 거리 벡터 (Distance Vector) 라우팅 알고리즘이란? 문제와 해결책 (Poisones Reverse)

본 포스팅은 < 컴퓨터 네트워킹 하향식 접근[8판] James F. Kurose, Keith W. Ross 저/최종원, 강현국, 김기태 > 을 참고하여 작성되었습니다.

 

거리 벡터 라우팅 알고리즘 Distance Vector Routing Protocols

링크 상태 알고리즘이 네트워크 전체정보를 이용하는 중앙 집중협 알고리즘인 반면에, 거리벡터 (DV) 알고리즘은 반복적이고 비동기적이며 분산적인 알고리즘이다.

• 분산적(distributed) : 각 노드는 하나 이상의 직접 연결된 이웃으로 부터 정보를 받고, 계산을 수행하며 계산된 결과를 다시 인접 노드들에게 배포한다.
• 반복적(iterative) : 이웃끼리 더 이상 정보를 교환하지 않을 때 까지 프로세스가 지속된다
• 비동기적(asynchronous) : 톱니바퀴가 돌듯이 모든 노드가 서로 정확히 맞물려 동작할 필요가 없다.

 

거리 벡터 알고리즘 Distance vector algorithm (DV)

벨만-포드 (Bellman-Ford, BF) 알고리즘을 기반으로 둔 알고리즘이다.

노드 x 부터 y까지 최소 비용 경로의 비용은 d_x(y)라고 할 때 BF 식에 의해 다음과 같이 나타낼 수 있다.

벨만-포드 식

v는 x에 인접한 모든 이웃들을 뜻한다.

 

Pseudo Code

이렇게 적어놓으니까 전혀 모르겠다. 예시를 보면서 찬찬히 뜯어보도록 하자.

이전에 보았던 아래와 같은 토폴로지가 존재한다고 치자. 위 네트워크를 벨만 포드 라우팅 알고리즘으로 포워딩 테이블을 채우는 방법은 다음과 같다.

먼저 각 출발 노드는 이웃에 대해 최소거리를 갱신한다. 그리고 상태가 변경되었으므로 이를 이웃들에게 알린다.

이웃들에게 알리고 나면 위와 같이 갱신된 상태를 전달받아 저신의 거리 벡터 또한 갱신한다.
그리고 벨만 포드 식을 사용하여 최솟 값을 재계산하고, 변화가 있다면 이를 또 이웃에게 알린다.

이웃으로 부터 갱신된 거리 벡터를 전달받고, 자신의 라우팅 엔트리를 재계산하고, 목적지까지의 최소비용 경로의 비용 변경값을 알리는 과정은 더이상 갱신 메세지가 없을 때까지 지속된다. 더 이상 변화가 없다면 알고리즘은 정지 상태가 된다.

 

거리 벡터 알고리즘 : 링크 비용 변경 문제 Link cost changes

만약 DV 알고리즘에서 링크 비용이 바뀐다면 다음과 같은 일들이 벌어진다.

1. 노드는 local link cost의 변경을 감지
2. 자신의 routing info 를 갠신하고 local DV를 재계산
3. 만약 local DV가 변경되었다면 이웃노드에게 알림

Count-to-Infinity problem 무한계수문제

이때 “good new travels fast bad new travels slow” 로 인해 문제가 발생한다. 링크의 속도가 빨라지는 좋은 소식은 네트워크 전역에 신속히 퍼져나가지만, 링크가 속도가 느려지는 나쁜 소식은 매우 천천히 알려지게 된다. 이로 인해 라우팅 루프가 발생할 수 있다.

 

거리 벡터 알고리즘 : 포이즌 리버스 Poisoned Reverse

위의 링크 비용 변경 문제로 인한 라우팅 루프 시나리오는 포이즌 리버스 (posiones reverse)라는 방법으로 방지할 수 있다.

만약 z가 y를 통해 목적지 x로 가는 경로 설정을 했다면 z는 y에게 x까지의 거리가 무한대라고 알린다. z는 y를 통과해서 x로 가는 동안 이러한 거짓말을 지속하게 된다. y는 z에서 x로 가는 경로가 없다고 믿으므로, z가 계속해서 y를 통해 x로 가는 경로를 지나는 동안에는 z를 통하는 경로를 시도하지 않는다.

 

링크 상태 알고리즘 (LS) vs 벡터 라우팅 알고리즘 (DV)

메세지 복잡성 message complexity

• LV : O(|N||E|)개의 메세지가 전송되어야한다. 또한 링크비용이 변할 때마다 모든 노드에게 이를 전달
• DV : 매번 반복마다 직접 연결된 이웃끼리 메세지를 교환

수렴 속도 speed of convergence

• LV : O(|N|^2)의 시간 복잡도를 가진다
• DV : 거리벡터 알고리즘은 천천히 수렴하고 알고리즘이 수렴하는 동안 라우팅 루프가 발생할 수 있다.

강건성 robustness

• LV : 라우터가 오동작한다면 잘못된 비용을 브로드캐스트할 수 있다.
• DV : 잘못된 최소비용경로를 목적지에 알릴 수 있다.