[컴퓨터네트워크] distance vector

Bellman-Ford equation

dx(y) = cost of least-cost path from x to y

 

dx(y) = min {c(x,.y)_

 

 

 

Distance Vector Routing Algorithm

반복적

비동기

분산적

 

Dx(y) = x에서 y로의 최소 추정치

 

Distance vector

각 노드는 주기적으로 이웃 노드에게 알려줍니다. 노드 x가 이웃으로부터 새로운 DV에 대한 추정치를 받는다면 

자신의 Dx를 업데이트시킵니다. 자신의 Dx를 가지고 있고 이웃 노드들에게 알려줌으로써 이웃 노드들로 이웃 노드를 받은 것으로 Distance Vector를 업데이트 시키고 반복을 해가면 이 추정치가 최적의 최소비용경로의 비용으로 수렴을 해가는 것입니다. 

 

반복적이고 비동기적인 특성

반복을 수행하는데 언제 실행하냐면

• local link cost change
• DV update message from neighbor

분산적인 특성, Self stopping

• 이웃노드와 Distance Vector 교류 없으면 종료 판단

 

이웃 노드로부터의 distance vector 수신이 올 때까지 기다리고 local link 비용이 올 때까지 대기상태로 있고 변경되거나 이웃노드로 distance vector를 수신했다면 DV를 재계산, 그리고 계산된 결과가 Distance Vector에 대한 변경이 발생했다면 변경된 사실을 이웃 노드들에게 알려짐

 

다시 대기상태로 들어감

Distance vector: example

초기 상태는 판단을 할 수 없어서 각각의 노드들이 이웃노드들의 링크에 초기화되도록 동작을 수행합니다. 

 

그래서 모든 노드가 자신의 local distance vector를 초기화한 상태에서 이웃노드들에게 자신의 vector를 알려줘야 합니다. 자신이 가지고 있는 distance vector 값을 이웃 노드들에게 전달을 해줍니다. 

 

시간 t=1

• 이 순간 모든 노드는 다음의 작업을 수행합니다:
  1. 이웃 노드로부터 거리 벡터를 수신:
     • 각 노드는 직접 연결된 이웃 노드로부터 현재까지 알고 있는 라우팅 정보를 받습니다.
  2. 새로운 로컬 거리 벡터 계산:
     • 수신된 정보에 기반하여 각 노드는 자신이 각 목적지 노드까지 도달하는 최적의 경로와 비용을 재계산합니다.
  3. 이웃에게 업데이트된 거리 벡터 전송:
     • 계산된 최신 거리 정보를 자신과 연결된 모든 이웃 노드에게 전송합니다.

이웃노드와의 Distance Vector를 교환하고 업데이트 시키고 업데이트 된 것을 다시 이웃 노드들에게 알려주는 반복  형태가 Distance Vector 형태입니다. 

 

링크 비용이 증가했을 때 

x에서 y가 60으로 증가한다면?

 

원래 Dy(x) = 4에서 60으로 바뀌기 때문에 Dy(x) = 6으로 바뀌게 됩니다. y가 알기로 링크 비용이 60이기 때문에 x로의 경로를 Dz(x)로 계산하면 됩니다. Y에서 Z로의 링크비용이 1이고 z에서 x의 distance vector가 5이기에 더하면 6이 됩니다. 

 

이걸 z에게 알려줄거고 t2 시점에서 y의 distance 시점에서 x의 distance 시점으로 업데이트 시키면 7이 됩니다. z에서 y의 링크 비용이 1이고 y에서 x가 6이어서 7이 됩닏아.

 

주요 내용:

1. 링크 비용 변경 (Link Cost Changes):
   • 링크 비용이 변경되었을 때 발생하는 상황을 다룹니다:
     • 좋은 소식 (Good News) 전파:
       • 비용 감소(예: 더 짧은 경로 발견)는 네트워크에서 빠르게 전파됩니다.
     • 나쁜 소식 (Bad News) 전파:
       • 비용 증가(예: 경로 단절)는 전파가 느리며, 이는 "Count to Infinity" 문제를 유발할 수 있습니다.
       • 예를 들어, 링크가 끊기면 노드들이 서로에게 "대체 경로가 존재한다"고 잘못 전달하면서 무한으로 증가하는 경향이 있습니다.

---

1. Count to Infinity 문제 설명:
   • 예시 네트워크 구성:
     • 노드 XXX, YYY, ZZZ가 연결되어 있습니다.
     • 초기 상태에서:
       • DY(X)=4D_Y(X) = 4DY​(X)=4, DY(Z)=1D_Y(Z) = 1DY​(Z)=1, DZ(X)=5D_Z(X) = 5DZ​(X)=5
   • 단계별 변화:
     • t1t_1t1​: YYY는 ZZZ를 통해 XXX로 가는 경로를 계산하며 DY(X)=6D_Y(X) = 6DY​(X)=6으로 업데이트.
     • t2t_2t2​: ZZZ도 마찬가지로 YYY를 통해 XXX로 가는 경로를 계산하며 DZ(X)=7D_Z(X) = 7DZ​(X)=7로 업데이트.
     • 이렇게 계속 반복되며 비용이 증가하게 됩니다.
   • 이처럼 각 노드가 서로의 정보를 신뢰하면서 비용이 점점 증가하는 현상을 "Count to Infinity"라고 부릅니다.
     • 알고리즘이 안정화되기까지 44번의 반복이 필요하다고 설명되어 있습니다.

---

1. Poisoned Reverse 기법:
   • 문제 해결 방안:
     • 아이디어: 노드 ZZZ가 YYY를 통해 XXX로 가는 경로를 사용하지 못하도록, ZZZ가 YYY에게 "자신은 XXX로 가는 경로를 무한대로 본다"고 전송합니다.
     • 즉, ZZZ는 YYY가 XXX로 가는 경로를 선택하지 못하도록 방지합니다.

LS와 DV 비교

메시지 복잡도

• LS : n노드, E링크에 대해, 각각 O(nE) 메세지가 전달
• DV : 단지 이웃 노드들 사이에만 교환됨

수렴속도

• LS : : O(n^2)알고리즘은 O(nE)메시지를 요구
• DV : 수렴 시간은 가변적임 라우팅 루프가 발생할 수 있고 count-to-infinity 문제

강건성 (라우터가 오동작하는 경우 어떤 일 발생하는가

• LS :노드는 잘못된 링크 비용을 브로드캐스트, 각 노드든 자신의 테이블만을 계산
• DV :DV 노드는 잘못된 경로 비용을 알림, 각 노드의 테이블은 다른 노드들에 의해 사용됨
• ㄴ 전체 네트워크로 오류 전파