[컴퓨터네트워크] Distance Vector Routing | 거리-벡터(DV) 라우팅
Routing Protocols | 라우팅 프로토콜
라우터 간 통신 방식을 규정하는 통신 규약으로 주로 경로설정을 위한 라우팅(포워딩) 테이블 작성을 한다.
Distance Vector Routing | 거리-벡터(DV) 라우팅
- 거리-벡터 라우팅에서 각 라우터는 인접한 이웃에 대한 정보를 포함하는 자체 최소 비용 트리를 생성한다. 이 트리는 불완전하지만 이웃 간에 교환되면서 점점 더 완전해지고 전체 인터넷을 나타내게 된다.
- 거리 벡터 라우팅에서 라우터는 지속적으로 모든 이웃에게 전체 인터넷에 대해 알고 있는 정보를 알려준다. 그러나 이 정보는 불완전할 수 있다.
- 간단히 말하면, 거리-벡터 라우팅에서 각 라우터는 인접한 이웃들과 정보를 교환하면서 전체 네트워크에 대한 정보를 점차 완성해 나가는 것이다.
Bellman-Ford Equation
DV 라우팅의 핵심은 Bellman-Ford 방정식이다.
이 방정식은 소스 노드와 중간 노드 사이의 비용과 중간 노드와 대상 노드 사이의 최소 비용이 제공될 때 일부 중간 노드(a, b, c, ..)를 통해 소스 노드 x와 대상 노드 y 사이의 최소 비용(최단 거리)을 찾는데 사용된다.
- u[ ] : 라우터 u의 전체 거리 벡터
- u[x] : 라우터 u에서 라우터 x까지 거리(최소 경로 비용), 네트워크의 각 라우터가 거리 벡터의 인덱스
distance vector Example
DV Update | 거리 벡터 업데이트
New B
A와 B의 거리는 2의 비용이 발생 한다. 각 A테이블에 +2 거리 비용 만큼 계산한 값과 old B와 비교 한다.
이 때, A테이블의 d값은 5가 됨으로, old B테이블이 A테이블을 거쳐서 인덱스 D로 가는 거리는 New B테이블의 D는 5가 된다.
Distans Vector Routing에서 라우팅 테이블 작성 순서
initialize → Share → 벨드 포드 공식에 의한 update → Share
Distans Vector Routing의 문제점
Two-node의 instability(불안정성)이 있다.
Count to Infinity(무한 계산 문제)
- 이웃 라우터를 경유하는 경로로 최소 경로 비용을 갱신하고, 해당 이웃 라우터에게 다시 전송하는 과정이 반복되는 문제
문제 발생 이유
- 링크가 고장나거나 비용이 증가할 때 발생
- 이웃 라우터가 자신을 경유하는 최소 경로 비용 전송
- 2개의 이웃 라우터 간에 순환 경로(loop path) 발생
문제점 Example
Solution | 해결법
Split Horizon
A가 X-A 거리를 업데이트 한 후 B로 전송하고, 다시 B가 A한테 전송하지 않는다.
Poison Reverse
A가 업데이트 후, B에게 전달한다. B는 업데이트 후, A에게 ∞(무한대)를 전달한다. (A가 기반으로 보낸 데이터를 다시 쓰지 못하게 하기 위함) → 이로써 둘 다 ∞(무한대)를 가지게 되어 라우터들이 고장이 난 사실을 빠르게 인지하게 된다.
But, 3개 이상의 노드의 불완전성은 여전히 문제가 된다. (Three-Node Instability)
경로 비용이 무한대로 증가(다시 무한 순환 구조가 됨)
