<div id="readability-page-1" class="page"><div> 지난번에 이어서 distance vector 알고리즘에 대해 알아볼 것이다.&nbsp;

이전 글에서 봤듯이, 본인과 인접한 부분에 대한 정보만 알고, 나머지 정보들은 이웃에 의해 전달받아야 한다. 그렇기 때문에 Distance vector 알고리즘의 핵심은 이웃에게 정보를 받아 이를 기반으로 정보를 업데이트한다는 것이 된다.&nbsp;
<figure data-origin-width="378" data-origin-height="228" data-filename="스크린샷 2021-09-27 오후 4.12.59.jpg" width="200" height="121" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/lxADJ/btrf3ue1QDK/9OqSMhuJrK5WyihzTI5zSK/img.jpg" data-origin-width="378" data-origin-height="228" data-filename="스크린샷 2021-09-27 오후 4.12.59.jpg" width="200" height="121" data-ke-mobilestyle="widthOrigin"></figure>
이러한 구조에서, x로부터 z로의 최단 경로를 구하기 위해서는 min(C(x,y) + Dy(z), C(x,z) + Dz(z))의 식으로 값을 구해낼 수 있다.&nbsp;

<ul data-ke-list-type="disc">
<li>y를 거쳐서 가는 경우</li>
<li>z로 바로 가는 경우&nbsp;</li>
</ul>
이 두 가지 경우 중 최소값을 가지는 경우를 선택하여 정보를 업데이트 해주는 것이다. 이러한 계산 과정이 반복되며 정보는 계속 업데이트 되고 더 이상 값이 바뀌지 않는(stable)한 상태가 된다면 그 때 종료된다.&nbsp;
<figure data-origin-width="1424" data-origin-height="1058" data-filename="스크린샷 2021-09-27 오후 4.15.20.jpg" width="600" height="446" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/kMB1X/btrf3ttHvXF/8rmrWgqLh91moRmkyS3VP1/img.jpg" data-origin-width="1424" data-origin-height="1058" data-filename="스크린샷 2021-09-27 오후 4.15.20.jpg" width="600" height="446" data-ke-mobilestyle="widthOrigin"><figcaption>Distance Vector Algorithm</figcaption></figure>
한 단계씩 차근차근 살펴보자.&nbsp;

<h3 data-ke-size="size23">Step 0</h3>
우선 x는 인접점인 y,z에 대한 정보만 알고있다. 그렇기에 from의 x행만 알고 있는 정보로 채워주면 된다. y,z도 마찬가지로 인접점에 대한 정보만 채워준다.&nbsp;

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

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

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

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

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

<h3 data-ke-size="size23">Count-to-infinity&nbsp;</h3>
중간에 간선이 소실되어 기존 노드들간의 경로가 무한대로 향하는 문제를 말한다. (즉, 일부 네트워크가 죽을 때!)
아래와 같이 간략하게 연결되어 있는 노드들을 보자.&nbsp;

<figure data-origin-width="2056" data-origin-height="1092" data-filename="스크린샷 2021-09-27 오후 4.32.22.jpg" width="600" height="319" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/dWRitx/btrga3ncY4L/H1g6i2ZkxLJlqQzkURymD1/img.jpg" data-origin-width="2056" data-origin-height="1092" data-filename="스크린샷 2021-09-27 오후 4.32.22.jpg" width="600" height="319" data-ke-mobilestyle="widthOrigin"><figcaption>기존 테이블</figcaption></figure>
각 노드들의 연결정보를 테이블로 정리한 것을 확인할 수 있다.&nbsp;
만약 여기서 B - C구간이 소실되면 어떻게 될까?&nbsp;
(B-C 구간은 이동할 수 없다는 의미로 간선의 비용을 무한대로 표기하곤 한다)
<figure data-origin-width="2036" data-origin-height="1056" data-filename="스크린샷 2021-09-27 오후 4.32.49.jpg" width="600" height="311" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/qvzMN/btrf9DbeMLf/ovovopR5pAKqbS7kYiaNL0/img.jpg" data-origin-width="2036" data-origin-height="1056" data-filename="스크린샷 2021-09-27 오후 4.32.49.jpg" width="600" height="311" data-ke-mobilestyle="widthOrigin"><figcaption>B-C 구간 소실</figcaption></figure>
B-C 구간이 소실됨에 따라 인접부분의 테이블을 수정해줘야 한다.&nbsp;
이 때 B &gt; C 부분, C의 모든 테이블 값이 사라지게 된다.&nbsp;

하지만 A의 테이블을 살펴보면 B를 거쳐 C로 갈 수 있다는 정보가 남아있음을 알 수 있다. 이 때문에 문제가 발생하게 된다!
<figure data-origin-width="2050" data-origin-height="1100" data-filename="스크린샷 2021-09-27 오후 4.33.26.jpg" width="600" height="322" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/xaPdM/btrga1Qrq1m/uxMQGS1kMlkkUEmUducCr0/img.jpg" data-origin-width="2050" data-origin-height="1100" data-filename="스크린샷 2021-09-27 오후 4.33.26.jpg" width="600" height="322" data-ke-mobilestyle="widthOrigin"><figcaption>Count-to-infinity (3)</figcaption></figure>
기존에 B 테이블의 B &gt; C 구간에 대한 정보는 없었으나 A 테이블의 A &gt; C와 B 테이블의 B &gt; A가 하나의 경로가 되어 B &gt; A &gt; B &gt; C로 연결되버리는 문제가 발생하여 B에서 4만큼의 비용으로 C로 이동할 수 있다고 판단하게 된다.&nbsp;

이제 B 테이블이 변경됨에 따라 인접점인 A의 값 또한 재계산이 필요한 시점이 오게 된다. A 테이블은 A &gt; B &gt; C가 현재 불가능하기에 B 테이블의 새로운 정보를 활용하여 A &gt; B &gt; A &gt; C 경로를 새로 만들어서 값을 업데이트 하게 된다.&nbsp;
<figure data-origin-width="2030" data-origin-height="1086" data-filename="스크린샷 2021-09-27 오후 4.33.47.jpg" width="600" height="321" data-ke-mobilestyle="widthOrigin"><img src="https://blog.kakaocdn.net/dn/cBkMOd/btrgbKOeRJE/SulxgKKKy4gOaoHOZAUgRk/img.jpg" data-origin-width="2030" data-origin-height="1086" data-filename="스크린샷 2021-09-27 오후 4.33.47.jpg" width="600" height="321" data-ke-mobilestyle="widthOrigin"><figcaption>A,B에서 C로 향하는 간선 비용이 계속 증가하는 모습</figcaption></figure>
이 과정이 계속 반복되면서 A &gt; C, B &gt; C는 무한대의 값을 가지게 된다. 이런 점을 유의하여 distance vector를 사용해야하며, 이를 해결하기 위한 방법은 차차 알아보자!
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
Ref : <a href="http://www.kocw.net/home/cview.do?mty=p&amp;kemId=1169634">http://www.kocw.net/home/cview.do?mty=p&amp;kemId=1169634</a>&nbsp;
<a href="https://www.youtube.com/watch?v=f2ic7kVnhrs">https://www.youtube.com/watch?v=f2ic7kVnhrs</a>&nbsp; </div></div>

참신러닝(Fresh - Learning)

지난번에 이어서 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기관의 내부 네트워크)
 
만약 중간에 간선의 비용이 바뀌게 되면 어떻게 해야할까?
 
값이 바뀌었다는 것은 새로운 최단 경로가 생겨날 수 있다는 의미를 내포하고 있기에, 그 점과 인접한 부분들에 대해 다시 계산해주어야 한다. 
 
Count-to-infinity 
중간에 간선이 소실되어 기존 노드들간의 경로가 무한대로 향하는 문제를 말한다. (즉, 일부 네트워크가 죽을 때!)
아래와 같이 간략하게 연결되어 있는 노드들을 보자. 
 
각 노드들의 연결정보를 테이블로 정리한 것을 확인할 수 있다. 
만약 여기서 B - C구간이 소실되면 어떻게 될까? 
(B-C 구간은 이동할 수 없다는 의미로 간선의 비용을 무한대로 표기하곤 한다)
B-C 구간이 소실됨에 따라 인접부분의 테이블을 수정해줘야 한다. 
이 때 B > C 부분, C의 모든 테이블 값이 사라지게 된다. 
 
하지만 A의 테이블을 살펴보면 B를 거쳐 C로 갈 수 있다는 정보가 남아있음을 알 수 있다. 이 때문에 문제가 발생하게 된다!
기존에 B 테이블의 B > C 구간에 대한 정보는 없었으나 A 테이블의 A > C와 B 테이블의 B > A가 하나의 경로가 되어 B > A > B > C로 연결되버리는 문제가 발생하여 B에서 4만큼의 비용으로 C로 이동할 수 있다고 판단하게 된다. 
 
이제 B 테이블이 변경됨에 따라 인접점인 A의 값 또한 재계산이 필요한 시점이 오게 된다. A 테이블은 A > B > C가 현재 불가능하기에 B 테이블의 새로운 정보를 활용하여 A > B > A > C 경로를 새로 만들어서 값을 업데이트 하게 된다. 
이 과정이 계속 반복되면서 A > C, B > C는 무한대의 값을 가지게 된다. 이런 점을 유의하여 distance vector를 사용해야하며, 이를 해결하기 위한 방법은 차차 알아보자!
Ref : http://www.kocw.net/home/cview.do?mty=p&kemId=1169634 
https://www.youtube.com/watch?v=f2ic7kVnhrs

[Network] 네트워크 계층 5

댓글