Distance Vector Algorithm   거리 벡터 알고리즘

(2021-08-17)

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"

RIP
   1. RIP 라우팅 프로토콜   2. RIP 패킷   3. 거리벡터 알고리즘   4.   5. RIPv2  
라우팅 알고리즘
   1. 라우팅 알고리즘   2. 거리 벡터 알고리즘   3. 링크 상태 알고리즘   4. 라우팅 테이블   5. 라우팅 메트릭   6. 링크 비용  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"