디스턴스 벡터와 링크 스테이트

 
 
라우팅 프로토콜에서 라우팅 테이블을 어떤 식으로
관리하는지는 두 가지 분류로 나눌 수 있다.
바로 디스턴스 벡터 알고리즘과 링크 스테이트 알고리즘이다.
 
 
 
 

디스턴스 벡터 알고리즘

라우팅 프로토콜에서 사용되는 경로 결정 알고리즘 중
하나로 각 라우터가 인접 라우터들과 거리 정보를 공유하며
최적의 경로를 찾는 방식이다.
 

특징

자신의 라우팅 테이블을 인접 라우터와 주기적으로 공유

벨만-포드(Bellman-Ford) 알고리즘 기반

라우팅 업데이트는 주기적 또는 변경 감지 방식으로 이루어짐

작은 네트워크에서 사용하기 적합, 네트워크 규모가 커지면 속도와 안정성 문제 발생

대표적인 프로토콜로는 RIP(15홉 제한)가 있음

 
 
 

장단점

장점	단점
라우팅 테이블을 줄일 수 있어 메모리 절약 가능	라우팅 테이블의 주기적인 업데이트로 트래픽 낭비
라우팅의 구성이 간단	라우팅 테이블이 변할 경우 모든 라우터가 알 때까지 오래 걸림
여러 곳에서 표준으로 사용

 
 
 
 

벨만-포드 알고리즘

최단 경로 탐색 알고리즘으로 RIP 라우팅 프로토콜의 핵심이다.
특징으로는 음수 가중치를 허용한다.
 

작동 방식

1. 각 노드는 자신과 직접 연결된 이웃 노드와의 거리(가중치)를 저장

2. 주기적으로 모든 이웃 노드와 라우팅 정보를 공유

3. 현재 거리 + 이웃을 거쳐 가는 거리를 비교하여 더 짧은 경로가 발견되면 갱신

4. 이 과정을 여러 번 반복하며 최적 경로를 찾음

 
 
 

 
위와 같이 음수가 포함될 수 있다.
 
예를 들어 A -> B로 바로 갈 때는 6이지만
A -> C -> E -> B로 가게 되면 2로 줄어든다.
 
 
 
 

 

하지만 다음과 같이 음수 가중치를 가지게 되면
C -> E -> B로 음의 무한인 노드가 발생하게 된다.
 
 
즉 음수 가중치를 처리할 수 있지만, 음수 순환이 존재하면
경로를 계산할 수 없다는 점을 가지고 있다.

 
 
 
 
 
 
 
 
 
 
 
 
 

링크 스테이트 알고리즘

네트워크의 전체 토폴로지를 기반으로 
최단 경로를 계산하는 방식이다.

 

특징

각 라우터가 네트워크의 전체 구조를 알고 있음

다익스트라(Dijkstra) 알고리즘 기반

변경 사항이 있을 때만 업데이트 전송

대규모 네트워크에서 효율적

대표적인 프로토콜로 OSPF(홉 제한 없음)가 있음

 
 
 

장단점

장점	단점
모든 경로를 알고 있기 때문에 변화 감지가 빠름	메모리 사용량 증가
변화가 있는 라우팅 테이블만 교환하여 트래픽을 줄일 수 있음	라우터 CPU에 부담이 감

 
 
 
 
 

다익스트라 알고리즘

그래프에서 한 정점에서 모든 정점까지의 최단 경로를
찾는 알고리즘이다.
음수 가중치를 허용하지 않는다.
 

작동 방식

1. 출발 노드를 설정하고 모든 노드까지의 거리를 무한대로 초기화, 출발 노드의 거리는 0

2. 가장 가까운 노드(가장 작은 가중치)를 선택하고 확정

3. 해당 노드와 연결된 이웃 노드들의 거리를 업데이트

4. 위 과정을 반복하여 모든 노드의 최단 경로를 결정

 
 
 

 
위와 같이 있다고 하자.
 
A부터 시작한다고 했을 때 다음과 같이 적용이 된다.

A	B	C	D	E
0	2	1	5	무한

 
E는 아직 직접적으로 연결돼있지 않아 
무한으로 표시된다.
 
 
이제 다음으로 작은 노드인 C로 가게 된다.
여기서 다시 노드 최솟값을 계산하게 되는데 다음과 같다.

A	B	C	D	E
0	2	1	2	3

 

위와 같이 D로 가는 길이 5보다 C를 거쳐
가는 것이 더 최적인걸 알게 되어 2로
C와 E가 연결되어 있어 거리를 알 수 있게 된다.
 
 
이제 다음 작은 노드인 D로 가게 되고
변경할 점이 없다면 위의 테이블은 유지가 된다.
 
 
또 다음 작은 노드인 E로 가게 되고
변경할 점이 없다면 위의 테이블은 유지가 될 것이다.
 
 
 
 
 
 
 
 
 
 
 
 
 간단히 정리하자면 디스턴스 벡터 알고리즘은 
소규모, 벨만-포드 알고리즘, 주기적 업데이트, RIP가 있고
 
링크 스테이트 알고리즘은 
대규모, 다익스트라 알고리즘, 변화 발생 시 업데이트, 
OSPF가 있다.