경로 배정 알고리즘

경로 배정 알고리즘은 패킷이 네트워크를 통해 이동하는 경로를 계산하며, 일반적으로 전역 링크 상태 뷰 또는 분산된 이웃 간 거리 벡터 계산을 사용하여 라우터와 링크 그래프에서 최저 비용 경로를 찾습니다.

Definition

경로 배정 알고리즘은 가중 그래프로 모델링된 네트워크를 통해 최저 비용(또는 다른 방식으로 선호되는) 경로를 결정하는 절차로, 라우터가 패킷을 목적지로 이동시키는 데 사용하는 포워딩 결정을 생성합니다.

Scope

이 주제는 포워딩 테이블을 채우는 알고리즘을 다룹니다: 링크 비용을 가진 네트워크의 그래프 모델; 전역적으로 공유되는 토폴로지를 사용하는 다익스트라 최단 경로 알고리즘을 이용한 링크 상태 경로 배정; 이웃 교환을 통한 분산된 벨만-포드 계산을 이용한 거리 벡터 경로 배정; 이들의 수렴 동작 및 무한대까지 세기 문제와 같은 병리 현상; 그리고 확장성을 위한 계층적 경로 배정. 이는 알고리즘을 추상적으로 다루며, 구체적인 프로토콜(OSPF, RIP, BGP)과 이들의 도메인 내/도메인 간 조직은 경로 배정 프로토콜 주제로 남겨둡니다.

Core questions

• 네트워크는 경로 배정을 위해 어떻게 가중 그래프로 모델링됩니까?
• 링크 상태 알고리즘은 전체 토폴로지 뷰에서 최단 경로를 어떻게 계산합니까?
• 거리 벡터 알고리즘은 이웃 교환만을 사용하여 어떻게 수렴합니까?
• 무한대까지 세기와 같은 수렴 및 안정성 문제는 무엇이며, 어떻게 완화됩니까?
• 경로 배정이 계층적으로 이루어지는 이유는 무엇이며, 이것이 경로 최적성에 어떤 영향을 미칩니까?

Key concepts

• 가중 네트워크 그래프
• 최저 비용 경로
• 링크 상태 경로 배정
• 다익스트라 알고리즘
• 거리 벡터 경로 배정
• 벨만-포드 방정식
• 무한대까지 세기 문제
• 분할 수평선 및 독성 역전
• 계층적 경로 배정

Key theories

링크 상태 경로 배정 (다익스트라)

각 라우터는 링크 비용을 플러딩하여 모든 라우터가 전체 토폴로지를 공유하도록 한 다음, 독립적으로 다익스트라 알고리즘을 실행하여 최단 경로를 계산합니다. 이는 빠르고 예측 가능하게 수렴하지만 전역 정보 교환이 필요합니다.

거리 벡터 경로 배정 (벨만-포드)

라우터는 각 목적지에 대한 현재 최저 비용 추정치를 이웃과 교환하고 벨만-포드 방정식을 통해 업데이트합니다. 계산은 분산되어 있으며 로컬 정보만 사용하지만 느리게 수렴하고 무한대까지 세기 문제에 시달릴 수 있습니다.

계층적 경로 배정

평면적 경로 배정은 전체 인터넷으로 확장되지 않으므로, 라우터는 지역(자율 시스템)으로 그룹화되며, 각 지역 내에서 경로 배정이 로컬로 처리되고 지역 간에 요약됩니다. 이는 확장성과 관리 자율성을 위해 일부 경로 최적성을 희생합니다.

Clinical relevance

경로 배정 알고리즘은 트래픽이 얼마나 효율적이고 안정적으로 흐르는지를 결정합니다. 링크 상태 알고리즘은 장애 발생 후 빠르게 수렴하는 OSPF와 같은 내부 프로토콜의 기반이 되며, 거리 벡터 개념은 RIP 및 BGP의 경로 벡터 접근 방식에 나타납니다. 이들의 수렴 동작을 이해하는 것은 안정적인 네트워크를 설계하고 링크 또는 라우터 장애 후 경로 루프 및 느린 복구를 진단하는 데 필수적입니다.

History

경로 배정의 핵심인 최단 경로 알고리즘은 컴퓨터 네트워크보다 먼저 개발되었습니다: 1950년대 후반 벨만과 포드의 경로 배정 문제 연구와 1959년 다익스트라의 최단 경로 알고리즘이 있습니다. 패킷 네트워크가 성장함에 따라, 이들은 거리 벡터 및 링크 상태 경로 배정으로 적용되었고, 자율 시스템으로의 계층적 구조화는 전 세계 인터넷으로 경로 배정을 확장시켰습니다.

Debates

링크 상태 대 거리 벡터 경로 배정

링크 상태 경로 배정은 빠르게 수렴하고 무한대까지 세기 문제를 피하지만, 모든 라우터가 전체 토폴로지를 유지하고 더 많은 계산을 수행해야 합니다. 반면 거리 벡터는 더 간단하고 로컬하지만 느리게 수렴하고 일시적인 루프를 형성할 수 있습니다. 실제 네트워크는 다른 규모에서 두 가지 아이디어를 모두 결합합니다.

Key figures

• Edsger W. Dijkstra
• Richard Bellman
• Lester Ford

Seminal works

• dijkstra1959
• bellman1958
• kurose2021

Frequently asked questions

무한대까지 세기 문제(count-to-infinity problem)는 무엇입니까?

이는 거리 벡터의 병리 현상으로, 링크 장애 후 라우터들이 오래된 정보를 교환하여 도달할 수 없는 목적지에 대한 거리 추정치를 서서히 증가시키며, 서로를 통해 경로가 여전히 존재한다고 잘못 믿는 현상입니다. 완화 방법으로는 분할 수평선(split horizon), 독성 역전(poisoned reverse), 그리고 최대 거리 제한이 있습니다.

링크 상태와 거리 벡터가 모두 사용되는 이유는 무엇입니까?

이들은 서로 다른 범위에 적합합니다. OSPF와 같은 링크 상태 프로토콜은 전체 토폴로지 공유가 허용되는 단일 관리 도메인 내에서 빠르고 루프 없는 수렴을 제공합니다. 거리 벡터 및 경로 벡터 접근 방식은 더 잘 확장되고 도메인 간에 내부 세부 정보를 덜 노출하므로, BGP가 네트워크 간에 경로 벡터 설계를 사용하는 이유입니다.