디스턴스 벡터 (Distance Vector)
- 디스턴스(거리)와 벡터(방향)만을 위주로 만들어진 라우팅 알고리즘
- 목적지까지의 거리(홉 카운트 등)와 거쳐야 하는 인접 라우터(Neighbor Router)에 대한 방향만 저장한다.
- 인접 라우터들과 주기적으로 (RIP의 경우 30초에 한 번) 라우팅 테이블을 교환해서 자신의 정보에 변화가 생기지 않았는지 확인하고 관리한다.
- 소규모 네트워크에 적당하다.
- ex) RIP, IGRP
장점
① 메모리 절약 (모든 라우팅 정보를 가지지 않아도 되어 라우팅 테이블을 줄일 수 있다.)
② 구성이 간단하다.
③ 여러 곳에서 표준으로 사용되고 있다.
단점
① 트래픽 낭비 (주기적으로 라우팅 테이블 업데이트가 일어난다.)
② Convergence Time이 오래 걸린다. (라우팅 테이블에 변화가 생길 경우 이 변화를 모든 라우터가 알 때까지 걸리는 시간)
③ 특히 RIP의 경우 최대 홉 카운트가 15를 못 넘긴다. (라우터 15개까지만 인식)
링크 스테이트 (Link State)
- 한 라우터가 목적지까지의 모든 경로 정보를 다 알고 있다.
- 링크에 대한 정보를 토폴로지 데이터베이스로 만들고 이를 SPF(Shortest Path First) 알고리즘으로 계산한다. 계산된 결과를 SPF 트리로 만들고, 이 트리 정보로 라우팅 테이블을 만든다.
- SPF 트리
- 출발지에서 목적지까지를 마치 나뭇가지처럼 펼쳐놓은 후 가장 빠른 경로를 찾아가는 방식
- 고용량ㆍ고성능 라우터에 적합
- ex) OSPF
장점
① Convergence Time이 짧다. (목적지까지의 모든 경로를 알고 있기 때문에 링크에 변화가 생겨도 이를 알아내는데 걸리는 시간이 잛다.)
② 트래픽 발생이 디스턴스 벡터에 비해 적다. (테이블 교환이 자주 발생하지 않고 변화가 있는 것만 교환한다.)
단점
① 메모리 소모가 많다. (모든 라우팅 정보를 관리해야 한다.)
② CPU 부담이 크다. (SPF 같은 알고리즘을 계산해야 하기 때문이다. SPF는 Distance Vector 알고리즘 보다 계산 과정이 복잡하다.)
SPF Algorithm
- Cost?
- 어떤 네트워크에 도착하기 위한 비용이나 시간 또는 로드(부하, Load)
- A는 Network1과 Network2에 직접 연결. 둘 다, Cost = 0, B까지는 Cost = 20
- B는 Network2와 Network3에 직접 연결. 둘 다, Cost = 0, A까지는 Cost = 20, C까지는 Cost = 30
- C는 Network3와 Network4에 직접 연결. 둘 다, Cost = 0, B까지는 Cost = 30
① Link-State Database
| 라우터 A | 라우터 B | 라우터 C |
| (N1 - 0) | (N2 - 0) | (N3 - 0) |
| (N2 - 0) | (N3 - 0) | (N4 - 0) |
| (RB - 20) | (RA - 20) | (RB - 30) |
| (RC - 30) |
② SPF 트리 만들기
<라우터 A에 대한 라우팅 테이블>
| Destination | Next Hop | Metric |
| Network 1 | Direct | 0 |
| Network 2 | Direct | 0 |
| Network 3 | Router B | 20 |
| Network 4 | Router B | 50 |
<라우터 B에 대한 라우팅 테이블>
| Destination | Next Hop | Metric |
| Network 1 | Router A | 20 |
| Network 2 | Direct | 0 |
| Network 3 | Direct | 0 |
| Network 4 | Router C | 30 |
<라우터 C에 대한 라우팅 테이블>
| Destination | Next Hop | Metric |
| Network 1 | Router B | 50 |
| Network 2 | Router B | 30 |
| Network 3 | Direct | 0 |
| Network 4 | Direct | 0 |
결론
각 라우터들은 공통의 Link-State Database로 부터 자신을 루트로 하는 각각의 트리를 구성한 후, Tree(Shortest Path tree)의 Node는 루트로부터 정점까지의 Shortest하고 Best Cost한 Path로 보이게 된다. Tree가 만들어지면 Next Hop의 Set은 연관된 Destination과 Cost로써 인식되어진다.
