[네트워크] poisoned reverse란? count to infinity 문제 해결법 | DV 알고리즘

Count to infinity 문제

Distance Vector 알고리즘(이하 DV 알고리즘)은 다른 라우터로 가는 최적 경로를 forwarding table에 저장해놓는다. 위와같은 상황에서 Y에서 X로 가는 비용이 60으로 증가한다면 어떻게 될까? ( 이해를 쉽게하기 위해 x라우터의 forwarding 정보는 무시하자 )

 

Y라우터는 인접 라우터들에 자신이 X로 가는 비용이 60으로 증가했음을 알리고, 최적 경로를 다시 계산하게 된다. 이 때Y라우터는 Z로부터 Z는 X라우터 까지 가는데 5의 비용이 든다는 정보를 얻게 된다. 오직 주변 노드의 정보로만 경로를 판단하기에 Y는 Z 노드까지만 가면 어떻게든 Z에서 X까지 5의 비용으로 갈 수 있다고 생각해 Y에서 Z를 가는 비용 1을 더해 X노드까지 6의 비용으로 갈 수 있다고 생각하게 된다. 즉 X로 가는 비용을 6으로 변경한다.

 

이후 Z노드는 Y노드까지만 가면 Y에서 알아서 X까지 6의 비용으로 간다고 판단한다. 따라서 Z에서 Y노드 가는 비용1을 더해 7의 비용이면 X노드까지 갈 수 있을 거라고 생각하게 된다. 즉 X로 가는 비용을 7로 변경한다.

이후 Y는 X로 가는 비용을 8로 변경, Z는 X로 가는 비용을 9로 변경.... 이렇게 낭비적인 연산을 44번 반복하고 나면 Y에서 X를 가는데 50이 든다고 생각하게 된다. 이 때 드디어 Z는 Y를 통해 가면 50+1=51의 비용이 든다고 생각해 Y를 통해서가 아닌 바로 X로 가는 비용 50이 더 최적이라고 판단하게 된다. 

 

이후 Y노드도 정상적으로 Z를 통해 X를 가면 51의 비용으로 최적경로라는 것을 알게 된다.

 

이러한 문제를 Count to infinity problem 이라고 한다.

---

Poisoned Reverse

위와 같은 Count to infinity problem을 해결할 수 있는 방법은 여러 가지가 있지만, 여기서는 Poisoned Reverse에 대하여 간략하게 설명해보겠다.

 

만약 Z노드에서 Y를 통해 X를 가는게 최적 경로라면, Z노드가 Y노드에게 자신은 X노드로 가는 비용이 무한대라고 전하는 방식이 Poisoned Reverse이다(위에선 forwarding table을 하나로 표현했지만 사실은 모든 라우터마다 forwarding table을 갖고 있다). 이렇게 하면 2번의 iteration 이면 최적 경로를 제대로 갱신할 수 있다. 마찬가지로 Y에서 X로 가는 비용이 60으로 늘어났다고 하자.

 

Y노드는 Z노드를 통해 X를 가면 무한대의 비용이 든다고 생각해 바로 X노드로 가는 60이 최적 경로라고 판단하고 갱신한다. Z노드는 Y를 통해 X를 가면 61의 비용이 든다고 생각해 갱신한다.