[네트워크] 라우팅 알고리즘 (Routing Algorithms)

라우팅 알고리즘

 라우팅 알고리즘은 송신 호스트에서 목적지 호스트까지의 라우터 네트워크를 통과하는 경로 중 최단 경로를 구하는 것입니다.

 

 네트워크를 그래프로 생각하면 네트워크의 구성 요소를 그래프에 대입해볼 수 있습니다. 그래프의 노드는 router로, 그래프의 edge는 link로, 그래프의 value는 link cost(거리 또는 트래픽 양)으로 대입할 수 있습니다.

 

 그래서 그래프 알고리즘에서 흔히 알고 있는 다익스트라, 벨만 포드 등을 네트워크의 라우팅 알고리즘에 적용할 수 있습니다.

 

 

 라우팅 알고리즘엔 크게 두가지 방식이 있습니다.

 

 첫째는 모든 라우터가 전체적인 비용에 대한 그림을 가지고 있다는 전제로 계산하는 경우인 ‘Link State’입니다. 그리고 두 번째는 전체 그림은 없고 이웃과 정보를 교환해서 최단 경로를 구하는 방법인 ‘Distance Vector Algorithm’입니다.

 

 각각 어떤 과정으로 포워드 테이블을 구성하는지 살펴보겠습니다.

 

 

1. Link State Algorithm

(출처 : 이석복 교수님 컴퓨터와 네트워크 강의 자료)

 링크 상태 알고리즘은 네트워크 노드 간의 모든 비용을 알고 있는 경우에 사용할 수 있습니다. 흔히 알고있는 다익스트라 알고리즘과 동일합니다. 최소 비용을 dp 배열에서 갱신해나가는 것입니다.

 

 

 

 

2. Distance Vector Algorithm

(출처 : 이석복 교수님 컴퓨터와 네트워크 강의 자료)

 

 거리 벡터 알고리즘은, 네트워크 전체 정보를 이용하는 것이 아니라, 반복적으로 경로에 대한 최소 거리 비용을 계산하는 방법입니다. 각 노드는 연결된 노드로부터 거리에 대한 정보를 받고, 반복적으로 계산을 수행하는 것입니다. 

 

 흔히 들어봤을, 벨만 포드 알고리즘으로 구현 가능합니다.

 

(출처 : 이석복 교수님 컴퓨터와 네트워크 강의 자료)

벨만 포드 알고리즘은 위와 같은 그림으로 살펴볼 수 있습니다. 

 

 각 노드들은 연결된 노드로 부터 거리에 대한 정보를 받고, 반복적으로 계산을 수행합니다. 그리고 그렇게 얻은 결과를 다시 연결된 노드에게 전달하고, 이 과정은 정보 교환이 필요하지 않을 때까지 반복됩니다.

 

 

Posioned Reverse

여기서 한 가지의 문제 상황을 고려해야합니다. 새로 갱신되는 값이 기존 값보다 작아진다면, 문제는 생기지 않지만 큰 비용으로 갱신된다면 Poisoned reverse가 생깁니다. 최소 경로가 되돌아가는 경로를 포함하는 경우 역류하게 되는 것입니다. 이를 대비해서 되돌아온 길은 무한대로 업데이트하여 역류를 방지합니다. 

 

 자세한 예시로 살펴보겠습니다. 우선 비용이 감소하는 예시입니다.

(출처 : https://choiblack.tistory.com/33)

위는 링크 비용이 감소한 경우 입니다. 

 

(출처 : https://choiblack.tistory.com/33)

 y테이블은 x와의 비용 값을 수정하고, 이 것을 x와 z에게 전달하게 됩니다. 이렇게 비용이 감소한 경우에는 동작이 많지 않고 빠르게 갱신이 이루어집니다.

 

 

그럼 비용이 증가하는 예시를 살펴보겠습니다.

(출처 : https://choiblack.tistory.com/33)

 비용이 위와 같이 증가한 경우입니다.

 

 비용이 감소했을 때와 마찬가지로 y테이블은 이웃들에게 변경된 값을 전달하게 됩니다. z는 이 값을 받아 테이블을 수정하고 이웃인 x,y테이블에게 갱신된 값을 전달하게 됩니다.

 

 이전에 비용이 감소했을 때와는 달리 많은 테이블의 갱신이 이루어지게 되는 것을 볼 수 있습니다. y테이블의 변화를 받은 z는 D_z(x) = min(D_z(x), D_z(y)+cost(y,x))를 수행하여 증가한 cost보다 작은 자기 자신의 값을 유지하게 됩니다. 그럼 y는 이렇게 유지된 값으로 다시 D_y(x)값을 D_y(z)+cost(z,x)로 갱신하여 6이 됩니다.

 이렇게 처음에 z테이블의 값이 유지되면서 D_y(x)값이 1씩만 증가하여 테이블이 안정되지 않고 계속 위 사진과 같이 많은 반복이 발생하게 됩니다.

 

 많은 반복이 발생하는 원인은 처음 z테이블이 갱신될 때 D_z(x)값이 y를 거쳐가는 경로 값이었다는 것입니다. 증가하기 전의 cost(x,y)를 사용함으로써 계산된 값을 비용이 증가한 이후에도 그대로 사용해서 생긴 문제입니다.

 

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

 

 따라서 최소 경로를 계산할 때 결정적인 역할을 한, 즉 거쳐온 이웃 라우터에게 경로 비용을 무한대로 전달하는 “Poisioned Reverse”를 사용하여 문제를 해결합니다.

 

 

 

Link State Algorithm과 Distance Vector Algorithm 의 차이

 링크 상태 알고리즘(Link State Algorithm)과 거리 벡터 알고리즘(Distance Vector Algorithm)의 차이를 요약하자면 다음과 같습니다.

 

 우선 Link State Algorithm은 거리와 대역폭을 고려하여 최적의 경로를 계산해 높은 효율성 제공한다는 장점이 있습니다.  하지만, 모든 라우터가 네트워크 내의 모든 링크의 상태 정보를 수집하여 라우팅을 결정하기 때문에 메모리 사용이 많다는 단점도 존재합니다.

 

 Distance Vector Algorithm는 각 라우터가 인접 라우터와의 거리 정보만을 공유하기 때문에 라우팅 구성이 간단하며, 라우팅 테이블이 상대적으로 작아 메모리 사용이 적다는 장점이 있습니다.

 단점으로는 라우팅 정보의 주기적 갱신으로 인해 네트워크 트래픽이 증가할 수 있고 네트워크 상태 변화에 대한 반응 속도가 느리다는 것입니다.

 

그래서 Link State Algorithm는 주로 대규모 네트워크에 적합하고 Distance Vector Algorithm 보다 소규모 네트워크에 적합합니다.

 

 

 

 

이렇게 라우팅 알고리즘에 대해 알아보았습니다.

 

 

 

 

참고자료

[컴퓨터 네트워크 - 한양대학교 이석복 교수님]
http://www.kocw.net/home/cview.do?cid=6166c077e545b736

https://blog.naver.com/ds4ouj/222325940682

https://the-square-of-y.tistory.com/221

https://broship.tistory.com/166?category=842347

https://choiblack.tistory.com/33

Computer Networking _ A Top Down Approach, 7th