학교
[컴퓨터 네트워크] Chapter 5. Network Layer: Control Plane (Part 1) - (2)
일자: 24-2 14주차 1차시
2-1. 라우팅 프로토콜 - 링크 상태
[1] 다익스트라의 링크 상태 라우팅 알고리즘
1) 특징
중앙 집중형(centralized): 네트워크 토폴로지, 링크 비용이모든 노드에 알려짐링크 상태 방송(link state broadcast)을 통해 수행모든 노드는
동일한 정보를 가짐
출발 노드(“source”)에서 다른 모든 노드로 가는
최소 비용 경로를 계산해당 노드의 전달 테이블 제공
반복적(iterative): k번의 반복 후, k개의 목적지에 대한 최소 비용 경로를 알 수 있음
2) 표기법
$c_{x,y}$: 노드 x에서 y로 가는직접 링크 비용; 직접 연결되지 않은 경우 ∞D(v): 출발지에서 목적지 v까지의 최소 비용 경로의현재 추정값p(v): 출발지에서 v까지 가는 경로에서의선행 노드N':최소 비용 경로가 확정된 노드들의 집합
3) 코드 예시
# 초기화:
N' = {u} # u에서 다른 모든 노드까지의 최소 비용 경로 계산
for all nodes v:
if v adjacent to u: # u는 처음에 직접 연결된 이웃에 대한 경로 비용만 알고 있음
D(v) = c[u,v] # 하지만 이것이 최소 비용이 아닐 수 있음!
else:
D(v) = ∞
# 반복
while True:
# N'에 없는 노드 중 D(w)가 최소인 w를 찾음
w = find_min_D_node(not_in_N')
N'.add(w) # w를 N'에 추가
# w에 인접하고 N'에 없는 모든 v에 대해 D(v) 갱신:
for v in adjacent_to_w and not_in_N':
# v까지의 새로운 최소 경로 비용은 다음 중 더 작은 값:
# 1) v까지의 기존 최소 경로 비용
# 2) w까지의 알려진 최소 경로 비용 + w에서 v까지의 직접 비용
D(v) = min(D(v), D(w) + c[w,v])
if all_nodes_in_N': # 모든 노드가 N'에 포함되면 종료
break[2] 다익스트라 알고리즘: 예시
초기화 (0단계): 모든 a에 대해: a가 인접한 경우 D(a) = $c_{u,a}$
N'에 없는 노드 중 D(a)가 최소인 노드 a를 찾음
a를 N'에 추가
a에 인접하고 N'에 없는 모든 b에 대해 D(b) 갱신
D(b) = min(D(b), D(a) + $c_{a,b}$)
1) u에서의 최소 비용 경로 트리:
2) u에서의 전달 테이블:
$u$에서 $v$로 가는 경로는 직접
$u$에서 다른 모든 목적지로 가는 경로는 x를 경유
[3] 다익스트라 알고리즘: 또 다른 예시
1) 주의 사항:
선행 노드를 추적하여 최소 비용 경로 트리 구축
경로에 대한 동점이 있을 수 있으며, 이는 임의로 해결 가능
[4] 다익스트라 알고리즘: 논의
1) 알고리즘 복잡도: n개의 노드
`n번의 반복마다 모든 노드 w에 대해 확인해야 함
n(n+1)/2번의 비교:
O(n²) 복잡도더 효율적인 구현 가능:
O(nlogn)
2) 메시지 복잡도:
각 라우터는
자신의 링크 상태 정보를 다른 n개의 라우터에브로드캐스트해야 함효율적인 브로드캐스트 알고리즘: O(n) 링크를 통해
하나의 소스에서 브로드캐스트 메시지를 전달각 라우터의 메시지는 O(n) 링크를 가로짐:
전체 메시지 복잡도: O(n²)
[5] 다익스트라 알고리즘: 진동 가능성 (oscillations possible)
1) 특징
링크 비용이 트래픽 양에 따라 달라질 때, 경로가 진동할 수 있음 (route oscillations)예시 시나리오:
목적지 a로의 라우팅, b, c, d에서 진입하는 트래픽의 비율은 1, e(<1), 1
링크 비용은 방향성 있고, 트래픽 양에 의존함
해결책
모든 라우터가 동시에 LS 알고리즘을 실행하지 않도록 함
2) 4단계
초기 상태
이 비용을 기준으로 새로운 라우팅을 찾아 새로운 비용 계산
이 비용을 기준으로 새로운 라우팅을 찾아 새로운 비용 계산
이 비용을 기준으로 새로운 라우팅을 찾아 새로운 비용 계산
(굿노트에 있는 사진 내용 확인하기)
2-2. Routing Protocols - Distance Vector
[1] Distance Vector Algorithm
Distance Vector 알고리즘은 Bellman-Ford 알고리즘을 기반으로 한 라우팅 알고리즘으로, 각 노드가 자신이 알고 있는 최단 경로를 이웃 노드에게 주기적으로 전달하여 네트워크 내에서 최단 경로를 결정한다.
1) Bellman-Ford Equation
Bellman-Ford 방정식은 최단 경로를 계산하는 방법을 제공합니다. 여기서:
$D_x(y)$는 노드 x에서 노드 y까지 가는 최단 경로의 비용을 나타낸다.
이때 최단 경로의 비용을 구하는 방법은, 노드 x의 이웃 노드들(v)을 통해 경로를 계산한다는 원리를 사용한다.
이 방정식은 다음과 같다:
[
D_x(y) = \min_v \left{ c_{x,v} + D_v(y) \right}
]
2) 설명
$min_v$: 노드 x의 이웃 노드들에 대해 최솟값을 구한다는 의미이다. 즉,
x에서y까지 가는 최단 경로를 찾기 위해,x의 이웃들(v)로 가는 경로를 계산하여 그 중 가장 작은 값을 선택한다.$c_{x,v}$: 노드
x에서 노드v로 가는 직접적인 링크 비용을 의미한다. 이는 두 노드가 직접 연결된 경우의 비용이다.$D_v(y)$: 노드
v에서 노드y까지 가는 최단 경로 비용을 의미한다. 이 값은 이미v가 알고 있는y까지의 최단 경로 정보를 기반으로 한다. 즉,v가 계산한 경로 비용을 사용한다.
3) (추가 설명) 알고리즘 동작 방식:
각 노드는 자신이 알고 있는 최단 경로를 이웃 노드에게 전송한다.
이웃 노드는 자신이 알고 있는 경로와 자신에게 전달된 경로를 비교하여, 더 짧은 경로를 선택하고, 그 정보를 다시 전송한다.
이 과정은 네트워크의 모든 노드가 서로 정보를 교환하면서 최단 경로를 계속해서 갱신하는 방식으로 동작한다.
따라서, 각 노드는 주기적으로 자신의 "거리 벡터"(최단 경로 목록)를 이웃 노드에게 전달하고, 이웃 노드는 그 정보를 바탕으로 경로를 갱신해 나간다.
[2-1] Bellman-Ford 예시
u의 이웃 노드들인x,v,w는 목적지z에 대해 각각 알고 있다:
최소값을 달성한 노드(
x)가 목적지z로 가는 추정된 최단 경로의 다음 홉이다.
1) 설명
(1) 상황 설정:
노드
u의 이웃 노드들인x,v,w는 각자 목적지z까지의 최단 경로를 알고 있다고 가정하자.각 노드는 목적지
z로 가는 경로에 대해 다른 노드들과의 경로 비용 정보를 가지고 있다.
(2) 목표:
u는 목적지z로 가는 최단 경로를 찾고자 한다.Bellman-Ford 방정식에 따라,
u는 이웃 노드들(x,v,w)을 통해z로 가는 경로를 계산한다.
(3) 경로 계산:
각 노드가
z까지의 최단 경로를 알고 있다면,u는 이 정보들을 바탕으로 자신의 경로를 계산할 수 있다.예를 들어:
x는z까지 가는 최단 경로를 알고 있으며, 그 비용은c(x, z)이다.v는z까지 가는 최단 경로를 알고 있으며, 그 비용은c(v, z)이다.w는z까지 가는 최단 경로를 알고 있으며, 그 비용은c(w, z)이다.
이제
u는 각 이웃 노드들이 전달한 정보를 바탕으로u에서z까지의 최단 경로를 계산한다. 이때, 각 이웃 노드까지의 경로 비용과 그 노드가 알고 있는z까지의 경로 비용을 더해서 비교한다.u의 경우:$D_u(z)$는 $min_v {c(u, x) + D_x(z), c(u, v) + D_v(z), c(u, w) + D_w(z)}$와 같다.
즉,
u는x,v,w로 가는 경로 비용을 비교하여 가장 적은 값을 선택한다.최소 경로 선택:
x가u에서z로 가는 최단 경로를 결정짓는 노드라면,x가u에서z로 가는 "다음 홉"이 된다. 즉,x를 경유해서z로 가는 경로가 가장 비용이 적다는 것을 의미한다.
2) 중요한 점
: 이 예시에서 중요한 점은, Bellman-Ford 알고리즘이 각 노드의 이웃 노드들과 정보를 교환하면서 목적지까지의 최단 경로를 계산한다는 것이다. 이 과정은 각 노드들이 자신의 경로 정보를 이웃과 주고받으며 반복적으로 이루어진다.
[2-2] Distance Vector Algorithm
1) 핵심 아이디어:
각 노드는 주기적으로 자신의 거리 벡터(DV) 추정치를 이웃 노드들에게 전송한다.
만약
x가 이웃 노드로부터 새로운 거리 벡터 추정치를 받으면, Bellman-Ford 방정식을 사용하여 자신의 거리 벡터를 업데이트한다:$D_x(y)$ ← $min_v{c_{x,v} + D_v(y)}$ for each node $y \in N$
자연스러운 조건 하에서,
D_x(y)추정치는 실제 최단 경로인d_x(y)로 수렴한다.
[2-3] Distance Vector Algorithm:
1) 각 노드의 동작
(로컬 링크 비용 변경 또는 이웃으로부터 메시지 수신) 대기
이웃으로부터 받은 거리 벡터(DV)를 사용하여 거리 벡터 추정치 재계산
만약 목적지에 대한 거리 벡터가 변경되었다면, 이웃들에게 알림
2) 반복적, 비동기적
: 각 로컬 반복은 다음에 의해 발생한다:
로컬 링크 비용 변경
이웃으로부터의 거리 벡터 업데이트 메시지
3) 분산형, 자동 종료
: 각 노드는 자신의 거리 벡터가 변경될 때만 이웃에게 알린다.
이웃은 그 후, 필요한 경우에만 또 다른 이웃에게 알린다.
알림을 받지 않으면, 아무런 행동을 취하지 않는다!
[3-1] 거리 벡터: 예시
모든 노드는 가장 가까운 이웃까지의 거리 추정값만을 가짐
모든 노드는 자신의 로컬 거리 벡터를 이웃 노드에게 전송함
몇 가지 비대칭:
누락된 링크
더 큰 비용
[3-2] 거리 벡터 예시: 반복 과정
1) t = 1
모든 노드는 가장 가까운 이웃까지의 거리 추정값만을 가짐
새로운 로컬 거리 벡터를 계산함
새로운 로컬 거리 벡터를 이웃 노드들에게 전송함
2) t = 2
이웃으로부터 거리 벡터를 수신함
새로운 로컬 거리 벡터를 계산함
새로운 로컬 거리 벡터를 이웃 노드들에게 전송함
3) 그리고 계속 반복됨
노드에서 반복적인 계산 과정을 살펴보자.
[3-3] 거리 벡터 예시
1) t = 1
b는 a, c, e로부터 거리 벡터(DV)를 수신함
c는 b로부터 거리 벡터(DV)를 수신함
e는 b, d, f, h로부터 거리 벡터(DV)를 수신함
[3-4] 거리 벡터: 또 다른 예시
[4] Distance Vector: 상태 정보 확산
: 반복적인 통신 및 계산 단계는 네트워크를 통해 정보를 확산시킨다
1) t = 0
t=0에서 c의 상태는 c에만 존재한다.
2) t = 1
t=0에서 c의 상태는 b로 전파되었으며, 이제 1홉 내의 거리 벡터 계산에 영향을 미칠 수 있다. 즉, b에서 계산에 영향을 준다.
3) t = 2
t=0에서 c의 상태는 이제 2홉 내의 거리 벡터 계산에 영향을 미칠 수 있다. 즉, 이제 b와 a, e에도 영향을 미친다.
4) t = 3
t=0에서 c의 상태는 이제 3홉 내의 거리 벡터 계산에 영향을 미칠 수 있다. 즉, b, a, e는 물론 d, f, h에도 영향을 미친다.
5) t = 4
t=0에서 c의 상태는 이제 4홉 내의 거리 벡터 계산에 영향을 미칠 수 있다. 즉, b, a, e, d, f, h는 물론 g, i에도 영향을 미친다.
[5-1] Distance Vector: 링크 비용 변화 (1)
1) 링크 비용 변화:
노드는 로컬 링크 비용 변화를 감지한다.
라우팅 정보를 업데이트하고, 로컬 거리 벡터(DV)를 재계산한다.
거리 벡터가 변경되면,
이웃들에게 알린다.
2) "좋은 소식은 빨리 퍼진다"
$t_0$:
y가 링크 비용 변화를 감지하고, 자신의 거리 벡터를 업데이트하여 이웃에게 알린다.$t_1$:
z가y로부터 업데이트를 받으면, 자신의 테이블을 업데이트하고,x로 가는 새로운 최단 경로를 계산한 후, 이웃들에게 자신의 거리 벡터를 보낸다.$t_2$:
y가z의 업데이트를 받으면, 자신의 거리 테이블을 업데이트한다. 그러나y의 최단 경로는 변하지 않으므로y는z에게 메시지를 보내지 않는다.
[5-2] Distance Vector: 링크 비용 변화 (2)
1) 링크 비용 변화:
노드는 로컬 링크 비용 변화를 감지한다.
2) 나쁜 소식은 천천히 퍼진다 – 무한 카운트 문제:
y는x와의 직접 링크 비용이 60으로 변경된 것을 알지만,z는 비용이 5인 경로를 가지고 있다고 말한다. 그래서y는 “내가x로 가는 새로운 비용은 6,z를 통해서”라고 계산하고,z에게 새로운x까지의 비용 6을 알린다.z는y를 통한x까지의 경로 비용이 6으로 변경된 것을 알고, “내가x로 가는 새로운 비용은 7,y를 통해서”라고 계산하고,y에게 새로운x까지의 비용 7을 알린다.y는z를 통한x까지의 경로 비용이 7로 변경된 것을 알고, “내가x로 가는 새로운 비용은 8,y를 통해서”라고 계산하고,z에게 새로운x까지의 비용 8을 알린다.z는y를 통한x까지의 경로 비용이 8로 변경된 것을 알고, “내가x로 가는 새로운 비용은 9,y를 통해서”라고 계산하고,y에게 새로운x까지의 비용 9를 알린다.…
가능한 간단한 해결책은 Poisoned Reverse(독극물 역방향) 방식이지만, 완벽하지는 않다.
해결책에 대한 자세한 내용은 본문을 참조하라. 분산 알고리즘은 복잡하다!
[6] LS와 DV 알고리즘 비교
1) 메시지 복잡도
LS: n개의 라우터, O(n²) 메시지가 전송됨
DV: 이웃 간 교환; 수렴 시간은 달라짐
2) 수렴 속도
LS: O(n²) 알고리즘, O(n²) 메시지
진동이 발생할 수 있음
DV: 수렴 시간은 달라짐
라우팅 루프가 발생할 수 있음
무한 카운트 문제 발생
3) 견고성: 라우터가 오작동하거나 해킹된 경우에는 어떻게 될까?
LS:
라우터는 잘못된 링크 비용을 광고할 수 있음
각 라우터는 자기 자신만의 테이블을 계산함
DV:
DV 라우터는 잘못된 경로 비용을 광고할 수 있음 (“어디든지 매우 저렴한 경로가 있음”): 블랙홀링
각 라우터의 테이블은 다른 라우터들이 사용함: 오류가 네트워크를 통해 확산됨
[7] 키워드
Routing Protocols: 네트워크에서 데이터를 전달하기 위한 경로를 결정하는 알고리즘과 규칙들. 네트워크의 구조와 목적에 따라 다양한 라우팅 프로토콜이 존재한다.
Forwarding table: 라우터가 데이터를 목적지로 전달하기 위해 사용하는 테이블. 각 목적지 주소에 대한 경로 정보가 포함된다.
Link state algorithms: 네트워크 내 각 노드가 링크 상태 정보를 주고받아 전체 네트워크의 상태를 파악하고 최단 경로를 계산하는 알고리즘. 예시: Dijkstra’s 알고리즘.
Distance vector algorithms: 각 노드가 자신의 거리 벡터를 이웃에게 전달하고, 이웃의 정보를 바탕으로 최단 경로를 계산하는 알고리즘. 예시: Bellman-Ford 알고리즘.
Dijkstra’s algorithm: 각 노드에서 출발하여 목적지까지 가는 최단 경로를 계산하는 알고리즘. 링크 상태 알고리즘의 일종으로, 네트워크에서 가장 많이 사용된다.
Least-cost-path tree: 주어진 출발지에서 모든 목적지까지의 최단 경로를 나타내는 트리 구조.
Route oscillations: 네트워크 경로가 지속적으로 변경되어 안정되지 않는 현상. 특히 링크 비용 변화나 잘못된 정보로 인해 발생할 수 있다.
Bellman-Ford equation: 거리 벡터 알고리즘에서 사용되는 수식으로, 노드
x에서 목적지y로 가는 최단 경로를 계산하는 방법을 제공한다.D_x(y) = min_v {c_{x,v} + D_v(y)}형태로 사용된다.
