OSPF 프로토콜

OSPF 알고리즘

Link-state 알고리즘은 OSPF(Open Shortest Path First) 라우팅 프로토콜에서 사용되는 알고리즘 중 하나입니다.
이 알고리즘은 OSPF 라우터가 연결된 모든 링크 정보를 수집하고 그래프 형태로 나타내며, 그래프를 사용하여 최단 경로를 계산합니다.

OSPF는 대규모 네트워크에서 사용되며, 이런 환경에서는 라우팅 테이블을 구성하는 것이 굉장히 복잡하고 시간이 많이 걸립니다.
따라서 OSPF에서는 각 라우터가 이웃 라우터와 정보를 교환하며, 이 정보는 링크 상태, 대역폭, 지연 등의 정보를 포함합니다
결과적으로 라우터는 이 정보를 사용하여 자신의 최단 경로 테이블을 계산합니다.

Link State 알고리즘 : OSPF 라우팅 프로토콜

OSPF(Open Shortest Path First)는 링크 상태(link-state) 라우팅 프로토콜입니다.
OSPF는 라우터 간의 경로 정보를 교환하고 이를 기반으로 최단 경로를 계산합니다.
이를 위해 OSPF는 링크 상태 정보를 라우터들끼리 교환하고 Dijkstra 기반의 SPF(Shortest Path First) 알고리즘을 사용하여 최단 경로를 계산합니다.

OSPF는 네트워크를 영역으로 분할하고, 각 영역마다 OSPF 라우터를 배치합니다.
OSPF 라우터는 자신이 속한 영역에서 다른 영역으로 가는 경로 정보를 자신의 영역 내에서만 공유합니다.
이를 통해 OSPF는 대규모 네트워크에서도 경로 계산을 빠르게 수행할 수 있습니다.

OSPF는 다양한 링크 유형을 지원하며, 링크 상태 정보를 주기적으로 업데이트하여 네트워크 변화에 대응합니다.
OSPF는 인접한 라우터 간에 Hello 메시지를 교환하고, 이를 통해 인접 관계를 형성합니다.
인접한 라우터 간에 링크 상태 정보를 교환하여 링크 상태 데이터베이스(LSDB)를 유지하고, SPF 알고리즘을 사용하여 최단 경로를 계산합니다.

하지만, 인접 라우터의 Cost가 같으면 어떡하죠?

OSPF에서는 라우터 간 링크의 대역폭을 코스트로 사용합니다. 그렇기 때문에 두 라우터 간 대역폭이 같은 경우, OSPF는 라우터 ID를 비교하여 코스트가 동일한 경우 라우팅 결정을 하게 됩니다.

라우터 ID는 OSPF 도메인 내에서 각 라우터를 유일하게 식별하는 식별자이며, IP 주소와는 별도로 관리됩니다
따라서, 코스트가 동일한 경우 OSPF는 라우터 ID가 더 작은 라우터를 더 선호하여 최단 경로를 결정하게 됩니다.

관련 내용은 Tie Breaker with OSPF Equal-Cost를 보면 더 자세히 알 수 있습니다 :>
(Tie breaker"는 경쟁 상황에서 동점이 나왔을 때 이를 해결하기 위한 추가적인 요소나 규칙을 의미합니다.)

라우터 ID는 OSPF 프로토콜이 시작될 때 자동으로 생성되며, 변경할 수 없습니다.
이때 OSPF는 라우터 ID를 기준으로 정렬하여 라우터 ID가 작은 경로를 선택합니다.
추가적인 정보는 OSPF 프로토콜의 공식 문서인 RFC 2328에서 확인할 수 있습니다.

Tie-breaking : Link State 알고리즘으로 개념 확장

링크 스테이트 알고리즘에서는 일반적으로 동일한 cost를 가진 링크에 대해 tie-break 기준을 라우터 ID의 오름차순으로 정하고 있습니다.
이를 통해 어느 한쪽으로 편향되는 것을 방지하며 안정적인 경로를 유지합니다.

그러나 초기에는 모든 라우터가 랜덤으로 tie-breaking을 수행합니다.
따라서 임시적으로 비효율적인 경로가 선택될 수 있습니다.
이러한 문제를 방지하기 위해서는 초기에 라우터 ID를 일정한 순서대로 부여하거나 수동으로 tie-breaking을 수행하여 원하는 경로를 선택할 수 있습니다.

또한, 두 라우터 사이의 경로 선택에 대한 tie-breaking이 이미 수행되었지만, 이후에 다른 링크의 상태 변경으로 인해 cost가 변경될 수도 있습니다.
이 경우 변경된 cost를 기반으로 다시 tie-breaking을 수행하여 경로를 선택하게 됩니다.
따라서 링크 스테이트 알고리즘은 상황에 따라 최적의 경로를 선택하기 위해 tie-breaking 정책을 유연하게 조정합니다.

그러나 이 tie-breaking이 랜덤하게 이루어지는 것은 아닙니다.

RFC 2328에서는 tie-breaking의 우선순위를 라우터 ID > IP 주소 > 인터페이스 순으로 명시하고 있습니다.
따라서 라우터 ID가 동일하다면, IP 주소를 비교하고, 이 역시 같다면 인터페이스를 비교하는 방식으로 우선순위를 결정합니다.

따라서, 라우터 ID를 설정할 때 이를 신중하게 설정하면 최적 경로를 선택하는데 도움이 될 수 있습니다.
그리고 만약에 동일한 cost가 발생했을 때, 라우터 ID, IP 주소, 인터페이스 등의 정보가 모두 동일하다면, 이 때는 tie-breaking을 위한 알고리즘이 명시되어 있지 않아, 그 때는 랜덤 tie-breaking이 적용될 것입니다.

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>