잠깐, 라우팅 알고리즘이 뭔데?

라우팅 알고리즘

라우팅 알고리즘은 패킷을 어떻게 전송할지 결정하는 데 사용되는 알고리즘이다. 라우터가 패킷을 수신하면, 라우팅 알고리즘은 패킷의 목적지 주소를 분석하여 최적의 경로를 결정한다.

라우팅 알고리즘에는 여러 가지가 있다. 이 중 대표적인 알고리즘들을 소개하면 다음과 같다.

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

거리 벡터 알고리즘은 각 라우터가 자신이 직접 연결된 라우터까지의 거리와 경로 정보를 갖고 있다. 이 거리 정보는 일정 주기마다 다른 라우터와 교환하며, 이 때, 거리 벡터 알고리즘에서는 벨만-포드(Bellman-Ford) 알고리즘을 사용하여 최단 경로를 계산한다.

거리 벡터 알고리즘의 장점

-구현이 간단하다
-각 라우터가 자신이 직접 연결된 라우터까지의 거리만을 알고 있어 메모리 사용이 적다는 것이다.
-또한 네트워크의 크기에 대한 제한이 없다는 점도 장점 중 하나이다.

거리 벡터 알고리즘의 단점

-수렴 문제가 발생할 수 있다는 단점이 있다. 거리 벡터 알고리즘에서는 라우팅 정보를 주기적으로 교환하기 때문에, 라우팅 정보가 일치하지 않는 상황이 발생할 수 있다. 이 때, 라우팅 루프(라우팅 정보가 무한히 전달되는 현상)가 발생하여 수렴하지 못하는 문제가 발생할수 있다.
예를들어 경로 A->B->C->A와 같이 루프가 형성되는 경우이다.

-이러한 문제를 방지하기 위해, 거리 벡터 알고리즘에서는 스플릿-호러(Split-Horizon)이나 홀드다운(Hold-Down) 등의 기법을 사용한다.

링크 상태 알고리즘 (Link State Algorithm)

네트워크 내 모든 라우터들이 상호 간의 링크 상태 정보를 교환하여 네트워크 전체의 정보를 파악하고, 각 라우터에서 SPF (Shortest Path First) 알고리즘을 이용하여 최단 경로를 계산한다.네트워크 전체 정보를 파악해야 하기 때문에 초기 구동 시간이 오래 걸릴 수 있다.

각 라우터가 인접한 라우터의 정보를 수집하여 링크 상태 데이터베이스(Link State Database)를 구성한다 이 링크 상태 데이터베이스는 네트워크의 전체 토폴로지 정보를 저장하고 있으며, 각 링크의 상태 정보(링크의 대역폭, 지연 등)를 포함한다.

링크 상태 데이터베이스를 바탕으로, 다익스트라(Dijkstra) 알고리즘을 사용하여 최단 경로를 계산한다. 이 때, 최단 경로는 링크 상태 데이터베이스에서 수집된 정보를 바탕으로 계산되며, 라우팅 테이블에 다시 저장한다.

링크 상태 알고리즘의 장점

-대규모 네트워크에서도 수렴이 빠르게 이루어진다.
-라우팅 루프가 발생하지 않는다.
-라우팅 테이블의 크기가 작다.

링크 상태 알고리즘의 단점

-하지만 링크 상태 알고리즘은 구현이 복잡하다
-메모리와 처리 성능이 높은 라우터가 필요하다는 단점이 있다.
-또한 링크 상태 데이터베이스의 정보를 전체적으로 유지하는 데 필요한 대역폭과 처리 부담도 높다는 것도 단점 중 하나이다.

경로 벡터 알고리즘 (Path Vector Algorithm)

경로 벡터 알고리즘 (Distance Vector Routing Algorithm)은 라우팅 프로토콜 중 하나로, 라우터 간에 경로 정보를 교환하여 네트워크의 최단 경로를 계산하는 알고리즘이다. 거리-벡터 알고리즘과 유사하지만, 경로 정보도 함께 교환하여 라우팅 판단을 한다. 라우팅 루프 문제가 거리-벡터 알고리즘보다 적게 발생한다.

경로 벡터 알고리즘은 라우터가 주기적으로 자신이 알고 있는 경로 정보를 인접 라우터에게 전달하고, 인접 라우터로부터 수신한 경로 정보를 업데이트한다. 이 때, 정보 전달을 위한 메시지에는 목적지까지의 경로와 거리 정보가 포함된다.

경로 벡터 알고리즘의 장점

-구현이 간단하고, 작은 네트워크에서는 빠른 수렴이 가능하다는 것이다.

경로 벡터 알고리즘의 단점

-하지만 대규모 네트워크에서는 수렴 시간이 오래 걸리거나 라우팅 루프(loop)가 발생할 수 있기 때문에, 대규모 네트워크에서는 OSPF나 BGP와 같은 다른 라우팅 프로토콜을 사용하는 것이 좋다.