1. 거리 벡터 알고리즘 (Distance Vector Algorithm)
ㅇ 라우팅 결정방식에 사용되는 알고리즘 중의 하나
- 모든 라우터가 경로 결정을 주로 거리(distance)에 의존하는 방식
ㅇ Bellman-Ford 알고리즘에 기초하여 1969년 설계됨
- R.E. Bellman,`Dynamic Programming`,1957
- L.R.Ford Jr and D.R.Fulkerson,`Flows in Networks`,1962
2. 거리벡터 알고리즘 특징
ㅇ 분산적
- 각 노드는 직접 연결된 이웃들이 보내는 정보로부터 계산하고,
그 계산결과(자신의 거리벡터 계산 복사본)를 이웃에게 알림
ㅇ 반복적
- 이웃끼리 라우팅 정보를 반복적으로 주고받음
ㅇ 비동기적
- 모든 노드가 비동기적으로 제각각 동작하며 계산
- 이웃에서 보내준 경로 예측 값들과 자신이 가지고 있는 경로 예측 값을 비교하여
적은 값을 최적 경로로 삼게됨
3. Bellman-Ford 알고리즘 (... 편집중...)
procedure BellmanFord(list vertices, list edges, vertex source)
// This implementation takes in a graph, represented as lists of vertices and edges,
// and fills two arrays (distance and predecessor) with shortest-path information
// Step 1: initialize graph
for each vertex v in vertices:
if v is source then distance[v] := 0
else distance[v] := infinity
predecessor[v] := null
// Step 2: relax edges repeatedly
for i from 1 to size(vertices)-1:
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
distance[v] := distance[u] + w
predecessor[v] := u
// Step 3: check for negative-weight cycles
for each edge (u, v) with weight w in edges:
if distance[u] + w < distance[v]:
error "Graph contains a negative-weight cycle"