[컴퓨터 네트워크] 34. Network Layer (10) : Distance Vector

Distance Vector

Bellman-Ford

Distance Vector 는 벨만포드 알고리즘 기반의 라우팅 알고리즘이다.

 

벨만포드 알고리즘은 DP 기반의 알고리즘인데, 위와 같은 점화식을 사용한다.

나(x)로부터 목적지(y)까지 가는데, 필요한 최단 경로는 나의 이웃 노드 v가 알려준 Dv(y) 값들과 내가 알고있는 v까지의 거리 Cx,v 로부터 최소값을 계산해서 얻는다는 아이디어다.

(이때 기존의 Dx(y) 값은 사용하지 않는다. 링크의 비용이 증가하는 쪽으로 갱신되어 최소값도 증가했다면, 증가한 것으로 계산해야 되기 때문이다.)

 

Link State 에서 사용했던 예제 그림에 벨만포드를 그대로 적용해보자.

u에서 z로 가는 최단 경로를 찾고자 한다.

 

 

u와 인접한 v, x, w 로 부터 각각 그 노드(라우터)들이 알고있는 z까지의 최단 거리 정보를 받는다.

 

이 정보와 인접한 노드들까지의 거리를 더해서 최소값을 통해 최단 경로를 찾는다.

Distance Vector 에서 D는 위 예제의 Dx(Y)의 D에 해당한다.

Vector 라는 말은 여러 목적지에 대한 D값을 다 포함하고 있다고 해서 벡터라고 한다.

즉, 목적지까지의 거리 벡터라고 생각할 수 있다.

 

Distance Vector 알고리즘

 

Distance Vector는 등장한지 꽤 오래된 아이디어다.

1970~80년대 정도에 등장했고, RIP라는 프로토콜이 이 방식을 사용했다.

 

Distance Vector 의 전반적인 알고리즘을 따르면, 때때로 각 노드들은 자신의 distance vector를 이웃 노드에게 보내준다.

정확히는 자신의 distance vector가 변경되었을 때 이웃 노드에게 전달한다. 변경되지 않았다면 굳이 알릴 필요가 없다.

(하지만 실제로 Distance Vector 알고리즘을 구현한 라우팅 프로토콜은 DV가 바뀌지 않았어도 정기적으로 이웃에게 알린다. 자신이 살아있다는 것을 알릴 수도 있기 때문이다.)

 

어떤 노드가 변경된 DV를 받았다면, 이 정보를 토대로 다시 벨만포드 점화식을 계산해서 최단 경로를 갱신한다.

(만약 최단 경로가 바뀌었다면 다시 자신의 주변 노드들에게 알린다.)

 

이 알고리즘은 분산 알고리즘이기는 하지만, 이 과정을 계속 반복하면 결과적으로 실제 least cost에 수렴하게 된다.

 

그러면 각각의 노드(라우터)는 어떻게 동작할까?

 

각 라우터는 위와 같은 흐름을 따라 동작한다.

처음에 각 노드는 자신의 link cost가 변경되거나, 이웃 노드로부터 갱신된 distance vector를 받을 때까지 기다린다.

만약 link 정보가 변경되었거나, 새로운 정보를 받았다면 다시 DV를 계산한다.

그래서 다시 계산한 결과로 link cost가 변경되었다면 이를 이웃 노드들에게 알려주고, 다시 기다리는 단계로 돌아간다.

 

단, 이 과정에서 라우터는 자신과 자신의 이웃밖에 신경쓰지 않는다.

전체 그래프 맵, 토폴로지는 하나의 노드가 알 필요가 없다.

그래서 broadcast로 정보를 뿌리는게 아니라 이웃까지만 정보를 교환한다.

 

다만 이게 모든 라우터가 딱딱 싱크가 맞춰서 계산이 되는건 아니다.

라우터마다 정보를 받는 속도가 다를 수 있기 때문이다.

따라서 이 계산은 비동기적으로, 독자적으로 계산이 될 수 밖에 없다.

---

Example

 

그림과 같이 라우터가 배치되어 있다고 해보자.

t = 0 일 때 라우터 a 의 DV는 위와 같다.

자신의 이웃 노드 정보만 갖고 있다.

다른 라우터 모두 a와 같이 각각의 DV를 갖고 있다.

 

이제 각각의 라우터들이 자신이 갖고 있는 DV 정보를 이웃 노드에 전달한다.

 

t = 1 시점이 되면 모든 라우터가 이웃노드가 보낸 DV 정보를 받는다.

(그림에서는 싱크를 맞춰서 모든 라우터가 같은 시점에 동시에 DV를 받는 것처럼 표현했지만, 실제로는 이렇게 딱딱 맞아 떨어지지 않을 수 있다. 각자 거리가 다 다르기 때문이다. 따라서 받는 시점이 다른 만큼, 계산하는 시점도 서로 다를 수 있다.)

 

 

이제 받은 정보들을 토대로 새로운 DV를 계산한다.

 

만약 변경된 DV가 있다면, 이를 이웃 라우터에게 알려준다.

 

이 과정을 t=2, t=3, ... 계속 반복한다.

---

 

이제 각 시점에서 계산할 때, 어떻게 계산하는지 구체적으로 살펴보자.

 

t=1 시점에서, 라우터 b 가 이웃 라우터로부터 DV정보를 받은 상황이다.

t=1 시점에서는 각 라우터가 자신과 이웃한 노드까지의 거리 정보밖에 갖고 있지 않다.

 

라우터 b는 받은 정보를 토대로 자신의 Distance Vector를 구성하는 8개 원소를 모두 재계산한다.

이때 계산할 때는 자신의 이웃 3개의 정보를 조합해서 계산한다.

 

그리고 이렇게 계산된 DV에 정보가 바뀌었으니, 바뀐 정보를 이웃 노드 a, c, e 에 알려준다.

나머지 라우터에 대해서도 이 과정이 반복적으로 일어난다.

 

그리고 이 과정은 언젠가 끝나게 되는데, 그게 끝나는 시점은 내가 나로부터 나까지 오는 거리를 물어보는 시점에서 끝난다. 이때는 최단 경로가 0이기 때문에 이웃 노드에게 정보를 물어볼 필요가 없다.

 

---

Distance Vector 특징

State Information Diffusion

 

DV는 각 라우터의 state가 점점 퍼져나가는 개념이다.

라우터 C의 t = 0 일 때 정보는 t = 0 일 C 내부에만 있을 것이다.

 

이 정보는 t = 1 일 때는 1 hop 떨어져 있는 b까지 퍼지게 된다.

 

t = 2 일 때는 추가로 한칸 더 떨어진 라우터까지 t = 0 시점의 c의 정보가 영향을 미칠 것이다.

 

t = 3일때는 그림과 같은 경계까지 퍼지고, t = 4 일때는 모든 라우터에 퍼진다.

 

Link Cost Change

DV 는 자신의 Link Cost가 바뀌었을 때, 바뀐 link cost를 반영하여 DV를 다시 계산하고, 다시 계산된 DV 값이 바뀌었다면 이웃 노드들에게 알려준다.

그런데 DV는 좋은 정보(링크 비용의 감소)는 빠르게 퍼지고, 안좋은 정보(링크 비용의 증가)는 느리게 퍼지는 특징이 있다.

 

 

y-x 사이의 비용이 4에서 1로 감소했다고 해보자.

t = 0 일때, y가 link cost 의 변경을 감지했으므로, 이 정보를 z에게 알려준다.

t = 1 일때, z가 y로부터 업데이트된 정보를 받는다. 따라서 x까지 가는 비용을 다시 계산하고, 이를 y에게 보내준다.

z 입장에서는 x까지 갈 때 y를 경유하는 것은 똑같은데 5 에서 1로 감소했으므로 DV에 변화가 일어나서 y 에게 보내주는 것이다.

t = 2 일때, y가 z로부터 변경된 내용을 받는다. 하지만, 자신이 알고있는 비용 1이 더 짧으므로 갱신하지 않고, DV가 바뀌지 않았으니 아무것도 하지 않아서 이 상태로 종료된다. (z를 거쳐서 x로 가게되면 1 + 2 = 3이 되므로)

그러면 y, z 모두 변경된 링크 정보를 공유한다.

 

이렇게 3번의 정보 교환으로 빠르게 좋은 소식이 공유된다.

 

 

반면 안좋은 정보는 느리게 퍼진다.

이를 count-to-infinity 라고 부르는데, 말 그대로 무한대까지 계속 1씩 카운트를 한다는 뜻이다.

 

t = 0 일 때, y가 link cost 의 변화를 감지해서 z에게 변화된 DV를 보내준다.

기존에는 y-x 가 4였지만, 이제는 60으로 증가했으니, 기존에 알고 있던 Dy(z) 값인 5를 통해서 Dy(x) 값을 6으로 바꿔서 DV를 갱신하고, 이를 z에게 알려준다.

(y는 기존에 DV를 계산할 때 사용했던 모든 데이터를 다 갖고 있다.)

 

t = 1 일 때, z는 y가 보내준 6이라는 정보를 토대로 y를 거쳐 x까지 가는 경로가 6 + 1 = 7이라는 정보를 새로 계산한다.

이 값은 자신이 알고있는 x-z 로 바로 가는 경로 5보다 길기 때문에, z-x 까지 가는 최단경로를 5에서 7로 갱신한다.

그리고 이 정보를 다시 y 에게 보내준다.

 

t = 2 일 때, y는 z가 보내준 x까지 가는 경로 비용 7을 보고, 자신의 DV를 수정한다.

기존에는 y-x 까지 가는 최단 경로를 6이라고 계산했는데, 이 값을 7 + 1 = 8 로 갱신해서 DV를 수정한다.

이 값을 z에게 보내준다.

 

이 과정을 거쳐 y는 최단경로를 기존 4에서 6, 8, ... 순으로 갱신하고, z는 최단 경로를 기존 5에서 7, 9, ... 순으로 갱신한다.

 

위 규칙에 따라가면 y는 최단 경로를 짝수로 갱신하므로, 만약 y가 최단경로를 48로 갱신했다고 해보자.

이 정보를 z 에게 보내면, z는 이를 받아서 y를 경유해서 x로 가면 48 + 1 = 49 의 비용으로 갈 수 있다고 판단한다.

여전히 이 값은 자신이 알고있는 50이라는 직선 경로보다 짧으므로 이 값을 y에게 알려준다.

 

y는 다시 49를 받았을 때 60보다 짧으므로 50으로 계산해서 z에게 알려준다.

z는 이 값을 보면 50 + 1과 직선경로 50을 비교해서 드디어 50이라는 진짜 최단 경로값으로 수정한 뒤 y에게 알려준다.

 

y는 50을 받았을 때 60보다 짧으므로 51로 계산해서 z 에게 알려준다.

z는 51을 받았을 때 50이라는 최단경로보다 기므로 DV를 수정하지 않고 아무 행동도 취하지 않는다.

이때 y도 51이 최단경로라는 것을 알게 된다.

 

즉, (무한대까지는 아니지만) y는 51이라는 진짜 최단 경로를, z는 50이라는 진짜 최단 경로 값을 알 때까지 계속해서 서로 1씩 증가하는 최단경로 변화값을 주고 받게 된다.

 

실제 네트워크는 충분히 저렇게 삼각형 모양으로 구성이 될 수 있는데, 이 문제를 해결하기 위해서 실제로는 만약 상대가 업데이트했다고 보낸 값이 알고보니 자신을 경유해서 구한 값이었다면 그냥 자신으로부터 x까지 가는 최단 경로를 무한대로 설정해서 보내준다. y가 어떤 새로운 값에 의해 갱신한 것인지 모르고, 그때까지 계속해서 데이터를 주고받을 수 없으니 그냥 처음부터 다시 구해서 달라는 뜻이다. y가 갱신한 최단 경로를 나에게 알렸는데 그게 나를 경유한 것이었고, 근데 그게 내가 알고있는 것보다 작은 값이면 굳이 내가 다시 거기로 거쳐서 갈 게 아니니 뭔가 bad news가 발생했다는 것을 감지해서 무한대로 설정한다.

 

그러면 y는 무한대를 받고, 업데이트된 60을 최단 경로로 수정해서 z에게 알려준다.

z는 60이라는 값을 보고 자신이 알고있는 x까지의 거리 (기존에 5)를 50이라는 값으로 바꿔서 y에게 알려준다.

y는 50을 받고 51이라는 최단 경로를 계산해서 z에게 알려주고,

z는 이 값을 받아도 50이라는 기존 최단 경로는 변하지 않으므로 무시해서 최단경로를 계산하는 프로세스가 간단하게 끝난다.

 

---

Link State  vs  Distance Vector

만약 해커가 라우터를 해킹해서, 임의로 값을 바꾸거나, 라우터가 잘못된 값을 전달했을 때, LS 와 DV가 얼마나 이에 대해 견고한지 비교해보자.

LS 방식은 어떤 라우터의 link 값을 조작해서 자신을 통해서 가면 무조건 빨리 갈 수 있다고 허위 광고를 한다고 해도, 네트워크 전체적으로 문제가 발생하지 않는다.

왜냐하면 각각의 라우터는 자기 자신의 그래프를 보고 최단경로를 계산해서 만든 테이블을 사용하기 때문이다.

(그런데 LS도 이때 잘못된 링크 정보가 퍼질 수 있지 않을까?)

 

반면 DV 방식은 어떤 라우터 하나가 거짓말로 나에게 오면 빨리 갈 수 있다고 하는 경우, 모든 트래픽을 자신이 받는 블랙홀 현상이 발생할 수 있다. 실제로 라우터는 이렇게 몰린 트래픽을 처리할 수 없으니 전체 네트워크가 마비되는 결과가 발생한다.

따라서 DV가 LS보다 더 위험하다.