Link State Algorithm   링크상태 알고리즘

(2020-05-19)

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



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