Intra-AS 라우팅을 위해 최적의 경로를 계산하는 알고리즘은 라우팅의 전달 내용, 방법 및 계산하는 방식에 따라 거리 벡터 알고리즘과 링크 상태 알고리즘으로 분류
거리 벡터 알고리즘(Distance Vector Algorithm)
네트워크 이론에서 최단 경로(Shorter Path)를 구하는 벨만-포드(Bellman-Ford) 알고리즘에 기반을 두고 있음
벨만-포드 알고리즘 : 가중치를 갖는 방향(Directed) 그래프에서 최단 경로 문제를 푸는 알고리즘이며, 이때 간선의 가중치는 음수일 수도 있음
각 라우터는 자신으로부터 다른 모든 라우터에 이르는 거리 정보(즉, 라우팅 테이블 자체)를 주기적으로 인접한 라우터와 서로 교환
각 라우터는 목적지(라우터 또는 호스트)별로 자신이 가지고 있는 라우팅 테이블 상의 거리와 다른 라우터로부터 받은 거리로부터 그 목적지에 이르는 더 짧은 거리를 구하여 자신의 라우팅 테이블을 갱신
계산한 결과치가 인접 라우터들끼리 교환되고 갱신되는 과정이 반복되면, 점차 모든 라우터들의 라우팅 테이블은 목적지에 이르는 거리가 최단 거리에 수렴하게 됨
링크 상태 알고리즘(Link State Algorithm)
주변 상태 방송
거리 벡터형 프롴토콜에서는 라우팅 테이블 정보 전체를 인접 라우터 간에 교환하는 데 비해, 링크 상태 알고리즘에 기반한 프로토콜에서는 각 라우터가 인접 라우터에 이르는 시간(Link-delay) 등 자신의 링크 상태(Link-state)를 네트워크 내의 모든 라우터에게 방송형태로 전달
전체의 토플로지 파악
방송한 링크 상태 정보를 토대로 전체의 네트워크 토플로지를 파악
최단 경로 산출
전체 정보에 입각해 각 라우터는 딕스트라(Dijkstra) 알고리즘을 수행하여 자신을 루트(root)로 하여 각 목적지에 이르는 최단 경로 트리(Shortest Path Tree)를 구하고, 그에 따라 라우팅 테이블을 갱신함
딕스트라 알고리즘 : 벨만-포드 알고리즘과 동일한 작업을 수행하고 실행 속도도 더 빠르지만, 가중치가 음수인 경우는 처리할 수 가 없음
알고리즘의 비교
거리 벡터 알고리즘에서는 최적 경로를 구하는 척도(Routing Metric)를 단순히 홉 수로 처리
링크 상태 알고리즘에서는 지연 시간이나 대역폭의 의미도 수용할 수 있는 비용으로 정의
거리 백터 알고리즘
링크 상태 알고리즘
전송대상
인접 라우터
모든 라우터
라우팅 정보
모든 라우터까지의 거리 정보
인접 라우터까지의 링크 비용
최단 경로 알고리즘
벨만 포드 알고리즘
딕스트라 알고리즘 사용
라우팅 프로토콜 예
RIP
OSPF
RIP(Routing Information Protocol)
개요
RIP은 거리 벡터 알고리즘을 사용하는 대표적인 라우팅 프로토콜로, 작은 규모의 네트워크에서 사용되는 간단한 라우팅 프로토콜
RIP에서 사용되는 거리 벡터 값은 홉 수인데, 홉 수란 통과하는 라우터의 수를 의미
패킷
RIP는 요청과 응답의 2가지 패킷으로 구성
요청 패킷
처음 부팅 시 이웃 라우터에게 라우팅 테이블 정보를 요청할 경우와 특정 목적지 정보가 타임아웃 되었을 때, 이를 갱신하기 위해 사용
응답 패킷
목적지에 대한 라우팅 정보를 실제로 담고 있는 패킷으로, 이웃 라우터에게 매 30초마다 주기적으로 라우팅 정보를 전송하는 데 사용
응답 패킷은 자신의 라우팅 테이블에 변화가 생겼을 때, 이를 알리기 위해 사용되기도 함
문제점
지속 수렴
RIP는 라우팅 정보를 매 30초마다 이웃 라우터에게만 보내므로, 네트워크 토플로지가 변화되었을 때 네트워크의 모든 라우터들이 이 상황을 반영하는데 많은 시간이 소요되므로, 국지적인 변화가 네트워크 전체에 매우 느리게 전파됨
불안정성
경로에 라우팅 루프가 발생하여 목적지에 이르는 경로 설정이 이루어지지 않을 수 있으며, 이는 RIP가 목적지에 이르는 거리만을 대상으로 갱신 과정을 수행하고, 그 거리에 대응하는 경로는 확인하지 않는 데에 원인이 발생됨