[컴퓨터망] Routing (1) - Routing Algorithm

네트워크 계층을 공부할 때, 네트워크 계층은 컨트롤 평면(Control Plain)과 데이터 평면(Data Plain), 이렇게 둘로 나누어진다고 공부했습니다. 컨트롤 평면은 출발지로부터 도착지까지 어떤 라우터를 통해 어떤 길로 가야 하는 지를 결정하고, 라우팅 테이블(Routing Table)을 만들어줍니다. 그러면 데이터 평면에서 패킷의 헤더를 확인하고, 라우팅 테이블을 참조하여 어느 인터페이스로 보내주어야 하는지를 실제로 포워딩해주게 됩니다.

 

이렇게 라우팅 테이블을 만들고 경로를 찾아주는, 컨트롤 평면이 하는 일들을 규약으로 만들어 둔 것을 라우팅 프로토콜(Routing Protocol)이라고 합니다. 라우팅 프로토콜의 목적은 당연히 네트워크 내에서 출발지로부터 도착지까지 가장 좋은 경로를 만드는 것입니다. 좋은 경로라는 말은, 비용이 최소화되고, 빠르고, 혼잡을 피하는 경로를 뜻합니다.

 

1. 링크 상태 알고리즘 (Link-state Routing Algorithm)

라우팅 알고리즘은 형태에 따라 분류가 가능합니다. 우선 링크 상태 알고리즘에서는 각각의 라우터들이 네트워크에 존재하는 모든 링크의 상태 정보를 모두 가지고 있고, 이를 통해 최단 경로를 찾는 알고리즘입니다. 이 상태는 해당 링크의 현재 트래픽, 대역폭 등을 포함하며 비용(cost)으로 표현됩니다.

 

각각의 라우터가 모두 네트워크 전체에 대한 데이터베이스를 가지며, 이 데이터베이스를 기반으로 각각의 라우터가 SPF 트리(Shortest Path First Tree)를 작성합니다. 이 트리를 기반으로 라우팅을 진행하게 됩니다. 즉 모든 라우터들이 출발지로부터 목적지까지 어떤 경로로 가야 하는지에 대한 지도를 만들어 가지고 있는 것입니다.

 

링크 상태 알고리즘을 구현하기 위해 다익스트라 알고리즘을 사용하며, 모든 라우터들이 네트워크 내의 링크 상태에 대한 테이블을 가지고 있기 때문에, 어떤 링크의 변화가 있을 때만 정보를 서로 전달하는 방식을 사용합니다. 

 

링크의 변화가 있을 때만 변경 정보를 라우터들끼리 공유하므로, 라우팅 정보 교환이 빠를 수 있고, 거리와 대역폭 등의 의 비용에 따른 경로 계산에 유리합니다. 하지만 라우터가 모든 네트워크에 대한 데이터베이스를 소유해야 하므로, 메모리가 많이 소모되고, 각각의 라우터가 이 데이터베이스를 이용해 SPF 트리를 그려야 하기 때문에 CPU 사용도 많습니다.

 

대규모 네트워크에서 사용이 적합하며, 지연, 대역폭 등 다양한 변수들을 비용으로서 고려할 수 있는 알고리즘입니다.

 

2. 거리 벡터 알고리즘 (Distance Vector Algorithm)

링크 상태 알고리즘과는 다르게, 거리 벡터 알고리즘은 경로 결정을 거리와 방향 정보에 의존합니다. 거리 벡터 알고리즘에서는 벨만-포드 알고리즘을 사용합니다. 

 

라우터들은 자신과 인접한 라우터들에게 자신이 가진 모든 정보들을 주기적으로 알려줍니다. 그리고 받은 정보와 자신이 가지고 있는 정보가 다르면, 갱신을 해줍니다. 각각의 라우터는 자신으로부터 목적지까지의 거리와, 해당 목적지까지 가려면 어떤 인접한 라우터로 가야 하는지만을 마치 고속도로 표지판처럼 저장합니다. 

 

목적지까지의 거리는 주로 HOP이라는 개념을 통해 표현하는데, 이 HOP은 목적지까지 도착하기 위해 거쳐야하는 라우터, 게이트 웨이등의 모든 네트워크 장비의 수를 뜻합니다.

 

거리 벡터 알고리즘은 라우팅 테이블의 크기가 작아 메모리를 절약할 수 있고, 구성도 간단해집니다. 하지만 주기적으로 라우팅 정보를 계속 갱신해 주어야 하며, 라우팅 정보 변화 시에 전달이 느리다는 단점이 있습니다. 거리 벡터 알고리즘은 소규모 네트워크에 적합합니다.