Distance Vector Algorithm   거리 벡터 알고리즘

(2013-07-20)
Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
통신/네트워킹 >   1. 통신 이란?
  2. 신뢰적 통신
[통신이론]
[선로/전송]
[통신망 일반]
[회선교환(PSTN)]
[무선/이동통신]
[광통신]
[인터넷/데이터통신]
인터넷/데이터통신 >   1. 데이터통신망
  2. 인터넷
  3. 데이터 네트워크 설계
[데이터 단위]
[프로토콜/계층]
[데이터 링크]
[TCP/IP]
[라우팅]
[인터넷 QoS]
[인터넷 관리]
[웹기술]
[인터넷 응용]
[인터넷 기타]
[패킷교환(PSN)]
[인터넷 관련 기관]
라우팅 > [라우팅 기초일반]
[라우팅 방식 구분]
[라우팅 알고리즘]
[라우팅 프로토콜]
[라우터]
[라우팅 수렴성/루핑]
[라우팅 네트워크 구분]
[VLSM,CIDR]
[라우팅 도메인,계위]
[라우팅 최적화]
[멀티캐스팅]
라우팅 프로토콜 >   1. 라우팅 프로토콜 이란?
[라우팅프로토콜 일반/종별]
[RIP]
[OSPF]
[IS-IS]
[BGP]
[시스코社(IGRP,EIGRP)]
RIP   1. RIP 라우팅 프로토콜
  2. RIP 패킷
  3. 거리벡터 알고리즘
  4.
  5. RIPv2

Top > [기술공통]
[기초과학]
[진동/파동]
[방송/멀티미디어/정보이론]
[전기전자공학]
[통신/네트워킹]
[정보기술(IT)]
[공업일반(기계,재료등)]
[표준/계측/품질]
[기술경영]
통신/네트워킹 >   1. 통신 이란?
  2. 신뢰적 통신
[통신이론]
[선로/전송]
[통신망 일반]
[회선교환(PSTN)]
[무선/이동통신]
[광통신]
[인터넷/데이터통신]
인터넷/데이터통신 >   1. 데이터통신망
  2. 인터넷
  3. 데이터 네트워크 설계
[데이터 단위]
[프로토콜/계층]
[데이터 링크]
[TCP/IP]
[라우팅]
[인터넷 QoS]
[인터넷 관리]
[웹기술]
[인터넷 응용]
[인터넷 기타]
[패킷교환(PSN)]
[인터넷 관련 기관]
라우팅 > [라우팅 기초일반]
[라우팅 방식 구분]
[라우팅 알고리즘]
[라우팅 프로토콜]
[라우터]
[라우팅 수렴성/루핑]
[라우팅 네트워크 구분]
[VLSM,CIDR]
[라우팅 도메인,계위]
[라우팅 최적화]
[멀티캐스팅]
라우팅 알고리즘   1. 라우팅 알고리즘
  2. 거리 벡터 알고리즘
  3. 링크 상태 알고리즘
  4. 라우팅 테이블
  5. 라우팅 메트릭
  6. 링크 비용

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. Bell-man-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

 
        최근수정     요약목록     참고문헌