Link State Algorithm   링크상태 알고리즘

(2023-08-03)

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


1. 최단 경로 알고리즘 (Shortest Path Algorithm)그래프 이론에서, 최단 경로를 찾는 그래프 알고리즘
     - 주로, 단일 출발지로부터 모든 정점까지의 최단 경로를 차례대로 찾는 탐색 알고리즘


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

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

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

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

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

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

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


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

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

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

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


5. [라우팅]  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)   5. OSPF 용어  
라우팅 알고리즘
   1. 라우팅 알고리즘   2. 거리 벡터 알고리즘   3. 링크 상태 알고리즘   4. 라우팅 테이블   5. 라우팅 메트릭   6. 링크 비용  


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