[네트워크] #19 Link status 알고리즘 (Dijkstra's algorithm, Example, Oscillation problem)

2023. 12. 6. 13:09·전공/네트워크
728x90
반응형

목차

  1. Dijkstra's algorithm (다익스트라 알고리즘)
  2. Example
  3. Oscillation problem (진동 문제)

1. Dijkstra’s algorithm

인접한 노드들 중 최적 경로인 노드를 계속 선택하여 최적 경로 Tree를 만드는 알고리즘

Link status algorithm은 Dijkstra’s algorithm을 기반으로 만들어짐

 

특징

  • 모든 노드에 대한 비용을 알고 있을 때 사용 가능
    • 각 라우터들이 link state broadcast 하기 때문에 사용 가능
    • 모든 노드가 동일한 정보를 가짐
  • 하나의 노드(source)에서 모든 노드로의 최소 비용 경로 계산
    • 해당 노드에 대한 포워딩 테이블 주어짐
  • 반복적인 작업을 수행한 후 최소 비용 경로를 파악

2. Example

Dijkstra's algorithm 예시

  • c(x,y): 노드 x에서 y로 링크 비용; 직접 이웃이 아닌 경우 ∞
  • D(v): 소스에서 대상까지의 경로 비용의 현재 값. v
  • p(v): 소스에서 v로 가는 경로의 이전 노드
  • N': 최소 비용 경로가 확실하게 알려진 노드 집합

 

각 step 마다 N과 인접한 노드의 최단경로를 계산

해당 노드들까지 가는 경로 중 가장 작은 값을 N에 포함

N’의 집합의 원소들이 그래프의 집합의 원소들과 같아지면 알고리즘 종료

 

Dijkstra’s algorithm 시간복잡도: O(n^2)

최적화 구현을 한다면 시간복잡도: O(n log n)


3. Oscillation problem

D, B에 단위가 1인 패킷이 도착하고 C에 단위가 e인 큰 패킷이 도착했다고 가정, 모든 목적지는 A

 

  1. C는 B를 경유해 단위가 e인 패킷을 A로 보내기로 결정
    • C→B 경로의 cost=e
    • B→A 경로의 cost=1+e
  2. B 입장에서 B→A의 cost=1+e, B→C→D→A의 cost=0+0+0+1=1이므로 패킷을 B→C→D→A의 경로로 보내기로 결정
    • B→C 경로의 cost=1
    • C→D 경로의 cost=1+e
    • D→A 경로의 cost=2+e
  3. D 입장에서 D→A의 cost=2+e, D→C→B→A의 cost=0+0+0=0이므로 패킷을 D→C→B→A의 경로로 보내기로 결정
    • D→C 경로의 cost=1
    • C→B 경로의 cost=1+e
    • B→A 경로의 cost=2+e
  4. 위와 같은 상황 반복

 

Oscillation(진동) 문제: Dijkstra’s algorithm 사용 시 위와 같은 상황이 반복되어 무한 루프에 빠지게 되는 문제

→ link status 알고리즘에서는 링크 상태 공유 시 랜덤 딜레이를 주어 동시에 경로를 바꾸는 것을 최대한 방지함

 

Link status algorithm vs. Distance vector algorithm

 

[네트워크] #18 라우팅 프로토콜, Link status algorithm vs. Distance vector algorithm

목차 라우팅 프로토콜 Link status algorithm vs. Distance vector algorithm 1. 라우팅 프로토콜 라우팅 프로토콜 목표: 라우터 네트워크를 통해 송신 호스트에서 수신 호스토로의 최적의 경로를 결정 네트워

campus-coder.tistory.com

 

728x90
반응형

'전공 > 네트워크' 카테고리의 다른 글

[네트워크] #21 Intra-AS, Inter-AS routing (OSPF, BGP, Intra-AS vs. Inter-AS)  (0) 2023.12.06
[네트워크] #20 Distance vector 알고리즘 (Bellman-Ford equation, Example, 문제점)  (1) 2023.12.06
[네트워크] #18 라우팅 프로토콜, Link status algorithm vs. Distance vector algorithm  (0) 2023.12.06
[네트워크] #17 IP (개념, Datagram 형식, IPv4, IPv6, 주소 접근, NAT)  (2) 2023.12.05
[네트워크] #16 라우터 (구조, 기능, 포워딩, 스케줄링 정책)  (2) 2023.12.05
'전공/네트워크' 카테고리의 다른 글
  • [네트워크] #21 Intra-AS, Inter-AS routing (OSPF, BGP, Intra-AS vs. Inter-AS)
  • [네트워크] #20 Distance vector 알고리즘 (Bellman-Ford equation, Example, 문제점)
  • [네트워크] #18 라우팅 프로토콜, Link status algorithm vs. Distance vector algorithm
  • [네트워크] #17 IP (개념, Datagram 형식, IPv4, IPv6, 주소 접근, NAT)
dev_ares
dev_ares
대학에서 컴퓨터공학을 전공하고 있는 학생입니다.
    반응형
    250x250
  • dev_ares
    노트
    dev_ares
  • 전체
    오늘
    어제
    • 분류 전체보기 (188) N
      • IT 트랜드 (2)
      • 백엔드 (18)
        • Java + Spring (8)
        • Kotlin + Spring (5)
        • 백엔드 (5)
      • 프론트엔드 (1)
        • React (1)
      • 대외활동 (17)
        • 42서울 (17)
      • 백준 (6)
        • Java (2)
        • C++ (3)
      • 전공 (121)
        • 객체지향프로그래밍 (17)
        • 자료구조 (23)
        • 리눅스시스템관리 (16)
        • 컴퓨터구조 (25)
        • 네트워크 (25)
        • 데이터베이스 (15)
        • 기타 전공 (0)
      • 프로그래밍 언어 (18)
        • Java (5)
        • Swift (4)
        • C++ (1)
        • Kotlin (8)
      • 기타 (4)
      • 공군 (1) N
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    코틀린
    컴공 포트폴리오
    단일 사이클
    반복자
    티스토리챌린지
    백준
    컴퓨터구조
    42서울
    상속
    오블완
    리눅스
    컴퓨터 구조 및 설계
    명령어
    메모리 계층 구조
    자바
    사설 문제
    데이터패스
    C++
    추가 문제
    자료구조
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
dev_ares
[네트워크] #19 Link status 알고리즘 (Dijkstra's algorithm, Example, Oscillation problem)
상단으로

티스토리툴바