안정 경로 문제와 도메인 간 라우팅

RIP 및 OSPF와 같은 동적 라우팅 프로토콜은 본질적으로 최단 경로 문제를 해결하기 위한 분산 알고리즘을 구현합니다. 현재 인터넷에 배포된 유일한 도메인 간 라우팅 프로토콜은 경계 게이트웨이 프로토콜(BGP)입니다. BGP는 거리 기반 메트릭을 재정의할 수 있는 정책 기반 메트릭을 허용해야 하고 자율 시스템이 최소한의 전역 조정으로 라우팅 정책을 독립적으로 정의할 수 있도록 요구되기 때문에 최단 경로 문제를 해결하지 않습니다. 그러므로 BGP를 어떤 근본적인 문제를 해결하기 위한 분산 알고리즘으로 볼 수 있는지 질문하는 것은 자연스러운 일입니다. 우리는 안정 경로 문제를 소개하고 BGP가 이 문제를 해결하기 위한 분산 알고리즘으로 볼 수 있음을 보여줍니다. 최단 경로 트리와 달리, 이러한 해결책은 전역 최적을 나타내지 않고 오히려 각 노드에 지역 최적이 할당된 평형점입니다. 우리는 다양한 노드에서 상충하는 라우팅 정책을 나타내는 분쟁 바퀴라는 파생 구조를 사용하여 안정 경로 문제를 연구합니다. 우리가 보이기 원하는 것은 분쟁 바퀴를 구성할 수 없으면 안정 경로 문제에 대한 고유한 해결책이 존재한다는 것입니다. 우리는 안정 경로 문제를 해결하기 위한 분산 알고리즘인 간단한 경로 벡터 프로토콜(SPVP)을 정의합니다. SPVP는 BGP의 동적 행동을 추상적인 수준에서 포착하기 위해 설계되었습니다. SPVP가 수렴하면 결과 상태는 안정 경로 해결책에 해당합니다. 해결책이 없다면 SPVP는 항상 발산합니다. 사실, SPVP는 해결책이 존재할 때조차 발산할 수 있습니다. 분쟁 바퀴가 존재하지 않을 경우, SPVP는 안정 경로 문제의 하나의 인스턴스에 대한 고유한 해결책으로 수렴할 것임을 보여줍니다.