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 |