Distance Vector Algorithm   거리 벡터 알고리즘

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"

1. ▷ Top (분류 펼침)      :     1,591개 분류    6,514건 해설 검색 펼침