Yozzang의 해킹일기 💻
article thumbnail
728x90

이번 포스트에서는 라우팅 알고리즘 중의 "Link-State Algorithm"에 대해 다루도록 하겠습니다.

 

Link-State Algorithm 이란?

: 링크 상태 데이터베이스를 사용하여 목적지까지의 여러 가능한 경로들 중에서 각 링크 비용 합에 기반하여 최소의 경로 비용을 계산하는 라우팅 알고리즘입니다. 즉 쉽게 말해 모든 라우터가 주기적으로 브로드캐스트를 통해 전체 라우터의 토폴로지(topology)를 알아내어 최적의 경로를 계산하는 알고리즘입니다.

 

Link-State 알고리즘 동작 과정 :

Initialization:
 N' = {u}
  for all nodes v
   if v adjacent to u
    then D(v) = Cu,v
   else D(v) = ∞
   
Loop
 find w not in N' such that D(w) is a minimum
 add w to N'
 update D(v) for all v adjacent to w and not in N':
  D(v) = min (D(v), D(w) + Cw,v)
  
until all nodes in N'
  • Cx, y : x에서 y로 직접 연결된 링크의 비용, 직접 연결되지 않으면 무한대(∞)로 표시
  • D(v) : 임의의 노드까지의 최소경로 비용
  • p(v) : 선행노드
  • N' : 현재까지 최단 경로가 확실하게 정해진 노드들의 집합

 

Link-State 알고리즘 예시 (1) :

 

Step N' D(v), p(v) D(w), p(w) D(x), p(x) D(y), p(y) D(z), p(z)
0 u 2, u 5, u 1, u
1 ux 2, u 4, x - 2, x
2 uxv - 4, x - 2, x
3 uxvy - 3, y - - 4, y
4 uxvyw - - - - 4, y
5 uxvywz 2, u 3, y 1, u 2, x 4, y

 

Link-State 알고리즘 예시 (2) :

 

Step N' D(v), p(v) D(w), p(w) D(x), p(x) D(y), p(y) D(z), p(z)
0 u 7, u 3, u 5, u
1 uw 6, w - 5, u 11, w
2 uwx 6, w - - 11, w 14, x
3 uwxv - - - 10, v 14,x
4 uwxvy - - - - 12, y
5 uwxvyz 6, w 3, u 5, u 10, v 12, y

'Networking' 카테고리의 다른 글

Transport Layer (전송 계층)  (0) 2022.05.06
Distance-Vector Algorithm (거리 벡터 알고리즘)  (0) 2022.05.02
ICMP & Traceroute  (0) 2022.04.13
DHCP (동적 호스트 구성 프로토콜)  (0) 2022.04.12
NAT (Network Address Translation)  (0) 2022.04.11
profile

Yozzang의 해킹일기 💻

@요짱

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!