[네트워크] #20 Distance vector 알고리즘 (Bellman-Ford equation, Example, 문제점)

목차

1. Bellman-Ford equation
2. Example
3. Distance vector algorithm
4. Distance vector algorithm 문제점

---

1. Bellman-Ford equation

데스티네이션까지의 최적 cost에 대해, 소스 노드가 계산한 값과 이웃 노드가 계산한 값을 비교하여 최적 cost를 찾아내는 알고리즘

 

d_x(y): x에서 y로 가는 최적 경로의 cost

d_x(y) = min_v{c(x,v) + d_v(y)}

---

2. Example

d_u(z) = min{c(u,v) + d_v(z), c(u,x) + d_x(z), c(u,w) + d_w(z)}

 

u에서 z로 가는 최적 경로의 cost는

• u→v의 cost + v→z의 cost
• u→x의 cost + x→z의 cost
• u→w의 cost + w→z의 cost

중 하나임

 

d_v(z) = 5, d_x(z) = 3, d_w(z) = 3이므로 (계산 생략)

d_u(z) = min{2+5, 1+3, 5+3} = 4이다.

---

3. Distance vector algorithm

D_x(y): x에서 y로 가는 예상 최적 경로의 cost

D_x = [D_x(y): y∈N]: x는 y에 따른 D_x(y) 값들의 set을 유지함 (y는 그래프의 노드)

 

노드 x는 이웃 노드들 v로 가는 cost를 알고 있음

→ v: c(x,v)

이웃 노드들 v도 자신과 이웃한 노드들로 가는 cost를 알고 있음

→ D_v = [D_v(y): y∈N]

 

노드 x는 이웃 노드들로 가는 cost와 이웃 노드들로부터 받은 목적지까지의 추정 값, 자신이 추정한 목적지까지의 추정 값도 알고 있음

 

Distance vector algorithm: 이웃 노드들로부터 도움을 받아서 자신이 목적지까지 도달하는 벡터를 예상함

D_x(y) ← min_v{c(x,v) + D_v(y)} for each node y∈N

이 값이 완전히 정확한 값이라고 할 수는 없지만, 예상치가 모여 정확한 값에 근접할 확률이 높아짐 → 결국 D_x(y)의 값이 d_x(y)의 값으로 수렴

 

반복적으로 자신의 링크 cost나 주변 노드들이 주는 값이 변할 때 Distance vector algorithm 구동

1. 자신의 링크 cost나 주변 노드들이 주는 값이 변하기를 대기
2. Distance vector algorithm 구동
3. 자신의 D_v 값이 변하면 주변 노드들에게 알림, 다시 1로 반복

 

특징

링크 cost가 감소했을 때 주변 노드들부터 빠른 속도로 인접한 노드들의 D_v 업데이트

단, 링크 cost가 악화되었을 때에는 업데이트 속도가 느리며 무한루프에 빠질 수 있음

---

4. Distance vector algorithm 문제점

link cost changes

• 링크 cost가 개선된 경우, 주변 노드들부터 빠른 속도로 개선된 정보 전달
• 링크 cost가 악화된 경우, 정보 전파 속도가 느림

 

routing loops

1. t_0:
   D_y(x) = min{c(y,x), c(y,z)+D_z(x)} = min{60, 1+5} = 6
   z는 아직 링크 cost 증가에 대한 정보를 전달받기 못해서 D_z(x)=5이기 때문
2. t_1:
   z가 y로부터 업데이트된 D_y(x)=6을 전달받음
   D_z(x) = min{c(z,x), c(y,z)+D_y(x)} = min{50, 1+6} = 7
3. 이후 D_y(x)=8 → D_z(x)=9 → …
4. 해당 과정을 44번이나 반복한 후에야 올바른 D_y(x), D_z(x)가 정해지게 된다.

 

count-to-infinity problem

y는 z한테 패킷을 보내고 z는 y한테 패킷을 보내게 되므로 무한 루프에 빠진다는 문제도 발생할 수 있음

 

 

해결책

poisoned reverse

링크 cost가 악화된 경우 정보 전파 속도가 느린 문제를 해결하기 위한 해결책

라우팅 정보를 보내온 쪽으로 ∞ 값의 라우팅 정보를 되돌려 보내는 방식

 

하지만 노드가 많은 네트워크에서는 보내온 쪽에 바로 라우팅 정보를 보내지 않더라도 다른 노드들을 거쳐 결국 라우팅 정보가 전달되므로 완전한 해결책이라고 볼 수는 없음

 

 

Link status algorithm vs. Distance vector algorithm

[네트워크] #18 라우팅 프로토콜, Link status algorithm vs. Distance vector algorithm