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. 라우팅 프로토콜 이란?
[라우팅프로토콜 일반/종별]
[RIP]
[OSPF]
[IS-IS]
[BGP]
[시스코社(IGRP,EIGRP)]
OSPF   1. OSPF 이란?
  2. 링크 상태 데이터베이스
  3. 링크 상태 라우팅 프로토콜
  4. 영역(Area)
[OSPF 인접 관계]
[OSPF 라우터 종류]
[OSPF 패킷]
[OSPF 네트워크 종류]

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

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


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

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