[Network] 네트워크 계층 5

728x90

지난번에 이어서 distance vector 알고리즘에 대해 알아볼 것이다.

이전 글에서 봤듯이, 본인과 인접한 부분에 대한 정보만 알고, 나머지 정보들은 이웃에 의해 전달받아야 한다. 그렇기 때문에 Distance vector 알고리즘의 핵심은 이웃에게 정보를 받아 이를 기반으로 정보를 업데이트한다는 것이 된다.

이러한 구조에서, x로부터 z로의 최단 경로를 구하기 위해서는 min(C(x,y) + Dy(z), C(x,z) + Dz(z))의 식으로 값을 구해낼 수 있다.

y를 거쳐서 가는 경우
z로 바로 가는 경우

이 두 가지 경우 중 최소값을 가지는 경우를 선택하여 정보를 업데이트 해주는 것이다. 이러한 계산 과정이 반복되며 정보는 계속 업데이트 되고 더 이상 값이 바뀌지 않는(stable)한 상태가 된다면 그 때 종료된다.

한 단계씩 차근차근 살펴보자.

Step 0

우선 x는 인접점인 y,z에 대한 정보만 알고있다. 그렇기에 from의 x행만 알고 있는 정보로 채워주면 된다. y,z도 마찬가지로 인접점에 대한 정보만 채워준다.

Step 1

자 이제 정보가 업데이트 되었으니 인접점들에게 정보를 전달해줘야 한다. 여기서 앞서 봤던 공식이 사용되는데, 정보를 전달받음과 동시에 새로운 최단 경로 존재의 가능성이 생기기에 값을 또 다시 계산해줘야 한다. 예로, x를 보면 기존에 0 2 7이었으나 from y z행의 값들이 업데이트 됨에 따라 새로운 최단 경로를 구할 수 있게 되었다. 이에 Dx(y)와 Dx(z)를 다시 계산할 필요가 있게 되는 것이다. 앞선 수식을 통해 계산해보면, x에서 z로 향하는 경로의 값이 갱신된 것을 볼 수 있다. 이러한 과정을 x뿐만 아니라, y와 z에 대해서도 수행해주며 계속 반복한다.

이후에도 마찬가지로 값이 바뀐 테이블이 있다면 그 노드를 기준으로 하여 인접한 노드들의 테이블 값을 변경시켜줘야 한다. 계속 계산하고 업데이트하고 계산하고... 이러한 일련의 과정이 반복되며 최단 경로를 계산해 나가는 것이다.

이전에 그래프의 모든 비용을 알고 있다고 가정하는 link state 알고리즘의 경우 한 번에 최단 경로를 계산했지만, 인접점들이 전달해주는 정보가 중요한 distance vector 알고리즘의 경우 그렇지 못하고 차근차근 계산되고 있는 것을 볼 수 있다. 이런 부분이 큰 차이점이며, distance vector 알고리즘의 경우 하나의 네트워크 안에서 주로 사용된다고 한다. (ex. A기관의 내부 네트워크)

만약 중간에 간선의 비용이 바뀌게 되면 어떻게 해야할까?

값이 바뀌었다는 것은 새로운 최단 경로가 생겨날 수 있다는 의미를 내포하고 있기에, 그 점과 인접한 부분들에 대해 다시 계산해주어야 한다.