Distance-Vector Algorithm (거리 벡터 알고리즘)

이번 포스트에서는 라우팅 알고리즘 중의 "DIstance-Vector Algorithm"에 대해 다루도록 하겠습니다.

 

Distance-Vector Algorithm 이란?

: 목적지까지의 모든 거리를 계산하는 게 아니라 목적지까지의 최단거리와 그 목적지까지 가려면 어떤 인접 라우터를 거쳐서 가야하는지를 저장하는 알고리즘입니다. 즉, 거리와 방향만을 고려하는 알고리즘입니다.

 

 

Distance-Vector 알고리즘 동작 과정 : 

1. 자신과 연결된 코스트의 비용이 바뀌거나 주변 인접 노드로부터 DV(Distance Vector)를 받으면 액션을 취한다.
2. 자신의 DV를 다시 계산한다.
3. 자신의 DV가 바뀌면 주변 인접 노드한테 전달한다.

Distance-Vector 알고리즘 예시 (1): 

공식 : dx(y) = min{c(x, v) + dv(y)}

⏰ t=0일 때 (초기화)

Node X

From\To	x	y	z
x	0	4	50
y	∞	∞	∞
z	∞	∞	∞

Node Y

From\To	x	y	z
x	∞	∞	∞
y	4	0	1
z	∞	∞	∞

Node Z

From\To	x	y	z
x	∞	∞	∞
y	∞	∞	∞
z	50	1	0

⏰ t=1일 때 (본인 값 재 계산)

Node X

From\To	x	y	z
x	0	4	5
y	4	0	1
z	50	1	0

Node Y

From\To	x	y	z
x	0	4	50
y	4	0	1
z	50	1	0

Node Z

From\To	x	y	z
x	0	4	50
y	4	0	1
z	5	1	0

⏰ t=2일 때 (바뀐 값 재 전달 후 재 계산)

Node X

From\To	x	y	z
x	0	4	5
y	4	0	1
z	5	1	0

Node Y

From\To	x	y	z
x	0	4	5
y	4	0	1
z	5|∞	1	0

Node Z

From\To	x	y	z
x	0	4	5
y	4	0	1
z	5	1	0

Distance-Vector 알고리즘 예시 (2) : 

⏰ t=0일 때

Node X

From\To	x	y	z
x	0	51	50
y	4	0	1
z	5	1	0

Node Y

From\To	x	y	z
x	0	4	5
y	60	0	1
z	∞ (z는 y로 경유하니까)	1	0

Node Z

From\To	x	y	z
x	0	4	5
y	4	0	1
z	5	1	0

⏰ t=1일 때

Node X

From\To	x	y	z
x	0	51	50
y	60	0	1
z	5	1	0

Node Y

From\To	x	y	z
x	0	51	50
y	60	0	1
z	∞	1	0

Node Z

From\To	x	y	z
x	0	51	50
y	60	0	1
z	50	1	0

⏰ t=2일 때

Node X

From\To	x	y	z
x	0	51	50
y	60	0	1
z	50	1	0

Node Y

From\To	x	y	z
x	0	51	50
y	51	0	1
z	50	1	0

Node Z

From\To	x	y	z
x	0	51	50
y	60	0	1
z	50	1	0

⏰ t=3일 때

Node X

From\To	x	y	z
x	0	51	50
y	51	0	1
z	50	1	0

Node Y

From\To	x	y	z
x	0	51	50
y	51	0	1
z	50	1	0

Node Z

From\To	x	y	z
x	0	51	50
y	51	0	1
z	50	1	0

---

Poisoned Reverse

:  DV 알고리즘은 경로에 대한 정보를 가지고 있지 않고, 단순 방향과 거리를 가지고 계산하므로 매우 긴 시간 동안 벡터가 교환되는 일이 발생할 수 있습니다. 이를 방지하기 위해 무한대 값을 사용한다. 즉, Z노드에서 Y를 통해 X로 가는 게 최적 경로라면, Z노드가 Y노드에게 자신이 X노드로 가는 비용이 무한대라고 전달합니다.