SPF   Shortest Path First, Dijkstra's Algorithm   SPF 알고리즘, 최단 경로 알고리즘, Dijkstra 알고리즘, 다익스트라 알고리즘

(2018-08-05)

Link State Algorithm, 링크상태 알고리즘, Link State 알고리즘, Link State Protocol, 링크 상태 프로토콜, Link State Routing Protocol, 최소 비용 라우팅

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

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

1. 최단 경로 알고리즘 (Shortest Path Algorithm)그래프 이론에서 두 정점 간에 최단 경로를 찾는 그래프 알고리즘
     - 출발지로부터 최단 경로를 갖는 점들을 차례대로 찾는 탐색 알고리즘

  ㅇ SPF (Shortest Path First) = Dijkstra 알고리즘
     - Dijkstra가 1959년 개발한 알고리즘
     *  Edsger W. Dijkstra (1930~2002) : 네덜란드 과학자

  ㅇ Link State Routing Algorithm (최소비용 기준 알고리즘)
     - 링크 상태 데이터베이스를 사용하여,
     - 동일한 목적지까지의 여러 가능한 경로들 중에서, 각 링크 비용 합에 기반하여,
       최소의 경로 비용을 계산하는 라우팅 알고리즘
  

2. [라우팅]  링크상태 라우팅 알고리즘 주요 특징

  ㅇ 전체 네트워크에 대한 토폴로지와 관련된 모든 정보로써 LSD(Link State Database)
     를 각 라우터가 완벽히 갖고 있게됨.
     - 이 LSD를 통해 SPF 트리를 만들고, 
     - 이를 토대로 최적 경로에 대한 라우팅 테이블을 구축하게 됨

  ㅇ 네트워크 토폴로지 및 모든 링크 비용이 알려져 있고, 이들 값이 입력으로 사용됨
     - 이에 참여하는 모든 라우터는 항상 전체 네트워크에 대한 맵(지도,그림 등)을 그리고,
     - 이를 토대로 최적의 경로를 계산하는 방식을 취함

     - 전체 지도는 점차 전 라우터에서 동일하게 그려지도록 빠르게 수렴됨

  ㅇ 어떤 링크의 변화가 있는 경우 만 정보를 전달하는 방식을 취함
     - 따라서, 라우팅 정보의 교환에 따른 부하는 작은 편임

  ㅇ Link State(링크 상태)에 기반하는 최적의 경로 선택을 위한 알고리즘
     - 이는 OSPF 등에 적용되어 사용됨


3. [라우팅]  링크상태 알고리즘 입력,출력,변수

  ※ 임의 노드부터 모든 가능한 목적지까지 최소비용 경로를 계산함

  ㅇ 입력 : 연결 가중치 그래프 토폴로지 (전체 노드에 대한 맵)
  ㅇ 출력 : L(z) (a에서 z까지 최단 경로 길이)
  ㅇ 변수
     - D(v) : 출발 노드(a)부터 목적지 노드(v)까지 현재까지의 경로비용
     - P(v) : 출발 노드(a)부터 목적지 노드(v)까지 현재 계산에서 이전 노드 (v의 이웃)
     - N    : 노드집합 (링크상태 알고리즘에 의해 현재까지 편입된 노드들의 집합)

  ㅇ ... (작성중) ...


4. [라우팅]  Link State Intradomain Protocol에 속하는 라우팅 프로토콜의 예라우팅 프로토콜            :  운반용 프로토콜들 (Routed Protocol)
     -  OSPF                    :  IP
     -  DECnet Phase V           
     -  IS-IS, Integrated IS-IS :  IP, CLNP
     -  NLSP                    :  (IPX에 대한 IS-IS 버젼)
     -  PNNI                    :  ATM


[라우팅 알고리즘] 1. 라우팅 알고리즘 2. 거리 벡터 알고리즘 3. 링크 상태 알고리즘 4. 라우팅 테이블 5. 라우팅 메트릭 6. 링크 비용

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