[10주차 주간 발표] 동적 라우팅과 다익스트라 알고리즘

 

 

라우팅 방식

정적 라우팅

목적지까지의 경로(혹은 다음 라우터)를 직접 입력하는 방식이다.

• 장점: 동적 라우팅에 비해 속도가 빠르고 안정적이다.
• 단점: 네트워크 상황의 변화를 반영하지 못하고, 네트워크 규모가 커질수록 작업량이 많아진다.

동적 라우팅

네트워크 상황을 반영하여 스스로 경로를 계산하고 변경하는 방식이다.

• 장점: 네트워크 상황의 변화를 반영한다.
• 단점: 변화에 적응할 때까지 시간이 필요하다.

일반적으로는 동적 라우팅이 바람직하지만, 연결된 이웃 라우터가 하나밖에 없는 경우에는 정적 라우팅이면 충분하다.

 

 

라우팅 알고리즘

원으로 표시된 것을 노드, 노드와 노드 사이를 잇는 선을 링크라고 한다.

Link state 계열

각 노드가 네트워크 전체의 형상과 모든 링크 비용을 파악한 후 목적지까지의 최단 경로를 계산하는 방식이다.

예시로 다익스트라 알고리즘이 있다.

Distance vector 계열

각 노드는 인접 노드까지의 링크 비용을 파악하고, 인접 노드들과 지속적으로 정보를 교환하여 각 목적지까지의 최단 경로상의 출력 포트를 계산한다.

예시로 벨만포드 알고리즘이 있다.

 

 

다익스트라 알고리즘

특정한 하나의 노드에서 다른 모든 노드으로 가는 최단 경로를 알려주는 최단 경로 탐색 알고리즘이다.

출발지는 u로 가정한다.

• N: 최단 경로가 이미 발견된 노드의 집합
• D(a): 목적지 a까지의 (현재 발견된) 경로 비용
• p(a): 목적지 a까지의 경로상에서 a 바로 앞에 있는 노드

Step

N

D(v), p(v)

D(w), p(w)

D(x), p(x)

D(y), p(y)

D(z), p(z)

 

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	∞	∞

노드 x까지의 비용이 제일 작으므로 x를 N에 포함시킨다.

 

노드 x가 N에 포함되었기 때문에 이제 노드 x를 경유해도 된다.

Step	N	D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
1	ux	2, u	4, x		2, x	∞

최소 비용인 노드가 v와 y가 있는데, 어느 것을 포함하던 결과는 같다. 그래서 일단 노드 v를 N에 추가한다.

 

Step	N	D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
2	uxv		4, x		2, x	∞

N에 노드 y를 포함시킨다.

 

Step	N	D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
3	uxvy		3, y			4, y

N에 노드 w를 포함시킨다.

 

Step	N	D(v), p(v)	D(w), p(w)	D(x), p(x)	D(y), p(y)	D(z), p(z)
4	uxvyw					4, y

N에 노드 z를 포함시킨다. 네트워크 전체 형상과 모든 링크 비용을 파악했다.

 

아래 표는 각 단계에서 선택한 노드들을 정리한 것이다.

step	선택한 노드(D(a), p(a))
0	x(1, u)
1	v(2, u)
2	y(2, x)
3	w(3, y)
4	z(4, y)

표를 기반으로 그래프를 그리면 위 그림과 같이 최단 경로를 발견할 수 있다.

라우터 u에서 다른 목적지로 데이터를 보내기 위해 다음과 같은 포워딩 테이블을 가진다.

목적지	링크(출력 포트 이름)
v	(u, v)
x	(u, x)
y	(u, x)
w	(u, x)
z	(u, x)

모든 라우터는 이러한 포워딩 테이블을 가지고 있다.