네트워크 17강 - 라우팅 알고리즘

지금까지 라우터의 Data Plane에 대해서 알아봤다. 이번 포스팅부터는 라우터의 두뇌 부분에 해당하는 Control Plane에 대해서 라우팅 알고리즘과 라우팅 프로토콜을 중심으로 알아보자.

라우팅 알고리즘

네트워크 전체 정보가 아닌 이웃한 라우터의 Link State와 그 라우터들의 목적지까지의 거리를 이용한다.
x에서 y로 가는 최소 비용은 이웃한 라우터 v들에 대해 min{C(x,v) + Dv(y)}로 정의할 수 있다. 이를 벨만포드 방정식이라고 한다.
Recursion 방식이다.

Distance Vectorm 는 모든 목적지까지로 가는데 드는 비용 벡터이다.
- 각 라우터(노드)들은 자신의 Distance Vector와 이웃 노드들 까지의 Cost를 알고 있어야 한다.
- 전체 네트워크 상에서 모든 노드들은 이웃들끼리 Distance Vector를 교환한다.
- 그렇게 정보가 퍼져나가면서 전체 네트워크의 Distance Vector가 업데이트된다.
- 한 노드가 새로운 Distance Vector를 받았을 때 벨만-포드 방정식을 사용해서 자신의 Distance Vector를 업데이트한다.
Distance Vector 알고리즘의 사이클
- 1. 이웃으로 가는 링크의 코스트가 변하거나 이웃에게서 DV 업데이트를 받는다.
- 2. 자신의 DV를 다시 벨만포드 알고리즘을 적용해서 업데이트하고 변화가 있으면 이웃에게 알린다.
- 3. 대기한다.
Count to Infinity 문제가 있다.
- 각 노드 x, y, z가 루프를 이룬다고 생각해보자.
- y -> x로 가는 코스트가 크게 상승하면 y는 자신의 DV를 업데이트 할 때 z의 DV를 참고한다.
- 하지만 z는 사실 코스트가 크게 상승하기전 y의 DV를 이용한 DV를 가지고 있다.
- DV를 의존하는 노드가 DV를 물어볼 때 INF로 대답해야 한다. ( Poisoned Reverse)

Message Complexity
- Link State 알고리즘은 네트워크 크기가 커질 수록 한 노드가 처리해야하는 양이 매우 많아진다.
- Distance Vector 알고리즘은 전체 네트워크 크기랑 상관없이 자신의 DV만 계산하면 된다.
Speed of Convergence
- Link State 알고리즘은 Link State가 브로드캐스팅 된 후에는 다익스트라 알고리즘을 계산하는 시간만 필요하다.
- Distance Vector 알고리즘은 Louting Loop 문제와 규모가 커지면 Convergence가 잘 안된다.
Robustness
- Link State 알고리즘은 영향이 적다.
- Distance Vector 알고리즘은 DV에 모든 목적지 정보가 들어가있기 때문에 파장이 크다.

이번 포스팅으로 네트워크 알고리즘 설명을 마치겠다. 네트워크 알고리즘은 손으로 그려가면서 공부해야 이해가 빠른데 블로그 포스팅으로 네트워크 알고리즘을 설명하는 것은 어느정도 한계가 있다. 더 자세히 알고 싶으면 강의를 참고하길 바란다.

본 게시물은 kocw 이화여자대학교 이미정 교수님의 컴퓨터 네트워크 강의를 듣고 정리한 글임을 밝힙니다.

내용상 틀린 부분이 있을 수도 있으며 이에 대한 책임을 지지 않습니다.

틀린 부분이나 오타 지적은 댓글로 남겨주세요.