네트워크 계층 - 라우팅 알고리즘 개요 (링크상태, 거리벡터)

네트워크 계층은 제어 영역과 데이터 영역으로 나누어 진다는 말을 앞선 포스팅에서 언급했었다.

 

 

해당 포스팅에서는 제어 영역에서 이루어지는 활동인 '라우팅'에 대해 살펴볼 예정이다. 라우팅이란 네트워크 현황을 조사하여 데이터를 전송할 수 있는 최적의 경로를 설정하는 활동이고, 이러한 라우팅의 결과로 포워딩 테이블이 생성된다. 

이러한 라우팅 방식은 크게 두 가지로 나눌 수 있다.

첫번째는 라우터 별 제어[Per-Router Control]다. 해당 방식은 전통적인 라우터가 사용하는 방식으로 각각의 라우터에서 동작하기 때문에 분산 제어 방식이다. 즉 하나의 라우터는 라우팅도 하고 포워딩도 하는 방식이다. 이러한 제어방식을 사용하는 프로토콜은 OSPF와 BGP가 있다.

두번째는 SDN이 채택하여 사용하는 중앙 집중 제어 방식이다. 논리적으로 집중된 컨트롤러가 네트워크 전체 환경을 보고 경로를 설정하여 각 라우터들에게 배포하는 방식이다. 각 라우터들은 라우팅 기능없이 포워딩만 수행한다.

 

1. 분산 제어 방식

전통적 라우터에서 동작하는 분산 제어 방식은 각각의 라우터에서 경로를 설정한다. 각 라우터는 전체 네트워크 환경은 볼 수 없다. 그러나 자신이 가지고 있는 정보를 자신과 연결된 이웃 라우터들에게 공유한다. 이러한 정보 교환은 계속 반복적으로 이루어지면서 최소 비용 경로를 계산하게 된다. 이러한 방식을 사용하는 알고리즘을 거리 벡터[DV: Distance Vector] 알고리즘이라 한다. 거리 벡터의 가장 대표적인 알고리즘은 다익스트라가 있다.

2. 중앙 집중 제어 방식

SDN에서 동작하는 중앙 집중형 알고리즘은 네트워크 전체에 대한 완전한 정보를 획득한 후, 이를 기반으로 경로를 계산한다. 따라서, 경로를 설정하기 전에 각 라우터로 부터 정보를 얻어야 한다. 이러한 방식을 사용하는 알고리즘을 링크 상태[LS: Link State] 알고리즘이라 한다. 링크 상태의 대표적인 알고리즘은 벨만-포드가 있다.

	링크 상태 [LS]	거리 벡터 [DV]
방식	네트워크 전체 정보를 필요로 함	연결된 이웃들끼리 반복적으로 정보 교환
메시지 복잡성	네트워크 링크 비용을 전부 알아야 하기 때문에 O(N*E)의 메시지가 필요	특정 라우터는 변경이 일어난 이웃 라우터에 대한 정보만 얻는다.
수렴 속도	O(N*E) 또는 O(N*N)	천천히 수렴하며 무한 계수 문제가 발생할 수 있다.

 

두 알고리즘 중 특정 알고리즘이 더 낫다고 명백하게 말할 수는 없다. 각자 상황에 맞게 사용되는 것이 최적이며 두 알고리즘 모두 현재까지 활발하게 사용되고 있는 방식이다.