[컴퓨터네트워크2] 하향식접근 5장 (2) - 다익스트라 알고리즘, DV 알고리즘

그냥 내가 이해를 어떻게 하고 있는지 혼자 설명하며 이해해 보는 식으로 적어봐야겠당

역시 난 나 보기 좋으라고 글 써놓는게 나중에 봐도 젤 이해가 잘 된다

 

이전 글에서 봤던 다익스트라 알고리즘

걍 

시작점 u에서 각 노드까지 거리 (if v면 D (v) ) 계산하고, 거기까지 도달할 때 바로 직전 노드 쓰기( p(v) )

한 번에 연결 안되어 있으면 무한대임

그리고 최소값인 노드 N'에 추가하기 -> 모든 노드 추가될 때까지

연결 노드가 늘어나는 거니까 최소 거리값도 바뀌겠지 ㅇㅇ 그럼 그때마다 최소로 업데이트

예제 계산해 봄

 

다익스트라 알고리즘 : 복잡도

 

- 알고리즘 복잡도 : n개의 노드

n개 노드가 있을 때 n번을 찾아야 함

n+1개가 있을 때 n개가 남는데 n개를 비교를 해야 함

 

처음에 n개 비교 + (n-1개 비교) + (n-2개 비교) + … + 1개 = S

S = 1 + 2+ 3+ … + n

두개 더하면 2S = (n+1) + (n+1) + … + (n+1) = (n+1) * n

=> S = n(n+1)/2

=> O(n^2) 복잡도 됨

 

 

- 메시지 복잡도

• 다익스트라 알고리즘에서 각 라우터는 자신의 링크 상태 정보를 네트워크 전체에 전파해야 함
• 이때, 메시지가 네트워크 내에서 얼마나 많이 전달되는지를 계산하는 것이 message complexity임

네트워크에 N개의 노드와 E개의 엣지(링크)가 있을 때

각 노드는 본인 링크상태 정보를 다른 노드 다에게 전파해야함 -> 각 노드의 메시지가 네트워크 전체에 퍼진다

-> 그걸 broadcast, flooding 방식으로, 다 흘러들어감, 모든 노드가 보내는 거가 E만큼 가는 것

 

각 노드는 자신이 받은 메시지를 이웃 노드에게 재전송하면 메시지가 각 노드까지 도달할 때까지 확산됨

한 개의 노드가 보낸 메시지는 네트워크를 통해 O(E) 만큼 전달됨

네트워크의 N개 노드가 각각 자신의 정보를 보내야 함

 

전체 메시지 복잡도를 O(N, E) 로 표현하기도 함

 

- each router must broadcast its link state information to other n routers

- efficient (and interesting!) broadcast algorithms: O(n) link crossings to disseminate a broadcast message from one source

- each router’s message crosses O(n) links: overall message complexity: O(n^2)

 

이렇다는데 한 번에 와닿앗는데

 

걍 한 노드가 모든 노드 갈 때 O(n)개의 엣지 거침, 노드가 O(n)개 있으면 각자 다 수행해야 되니까 O(n^2) 된다

(* Big-O 표기법에서 O(n) 은 "최대 n개의 노드에 비례하는 증가"를 의미 )

 

+ spanning tree는 모든 노드를 포함하고 loop가 없는 트리라 똑같은 걸 두 번 안 받게 하는 한 번씩만 보내게 해서 복잡도를 줄일 수 있다

 

 

다익스트라 알고리즘 : 진동문제

알고리즘 전제는 링크 비용이 고정인데 현실에선 바뀔 수도 있음

-> 트래픽 볼륨(부하) 에 따라서 바뀔 수 잇음

-> 그럼 경로 진동 == 경로가 계속 변경된다

는 문제가 발생

 

 

트래픽이 특정 링크를 따라 몰리면 비용이 증가 → 다익스트라 알고리즘이 새로운 경로 선택 → 트래픽 이동 → 이전 경로 비용 감소 → 다시 경로 변경 → 무한 반복 같은 상황

 

- 노드(라우트)에 트래픽이 들어오면, 링크 비용이 트래픽에 따라 바뀜 => 가변적인 방향성 비용(directional, volume-dependent cost)

 

어케 해결?

1) 책에서 말하기론

- 모든 라우터가 동시에 링크 상태 알고리즘을 실행하지 못하도록 하는 방법

라우터들이 동일한 주기 간격으로 링크 상태 알고리즘을 수행한다 하더라도

각 노드에서의 알고리즘의 실행 시각은 같지 않을 것이기 때문에 합리적인 방법이라고 생각된다고 함

 

but 연구자들은 라우터들이 알고리즘을 처음에는 각기 다른 시작 시각에, 그러나 같은 주기를 갖도록 해서 실행하더라도

점진적으로 결국엔 서로 동기화된다는 것을 발견햇다

-> '자기 동기화' 는 각 노드가 링크 상태 정보를 송신하는 시각을 임의로 결정하게 함으로써 회피할 수 있다고 함

 

 

2) 다른 방법으론

- 링크 비용을 트래픽 변화에 민감하지 않게 설계: 트래픽 부하에 따른 비용 증가폭을 줄여 급격한 변화 방지.

- 경로 업데이트 주기를 길게 조정 : 너무 자주 다익스트라 알고리즘을 실행하지 않고 일정 시간마다 경로를 업데이트.

- 부하 균형(Load Balancing) 적용 : 트래픽을 여러 경로로 나누어 특정 링크에 과부하가 걸리지 않도록 함.

 

 

거리 벡터(DV) 알고리즘

아 이거 우선 벨만포드(BF) 식 기반인데

그게 뭐냐면

내 neighbor 노드가 3개면, 걔네한테 도착하려는 노드 (예: y) 까지 얼만지 계산하라고 하고

내 네이버 노드 3개까지 거리 + 걔네가 계산한 각각의 거리 계산해서 최소 거리비용 찾는 거 ㅇㅇ

식으로 쓰면 이런데

 

 

각 항목의 의미

1. ( D_x(y) )

• 노드 ( x )에서 목적지 ( y )까지의 최소 비용(최단 경로)
• 우리가 구하고 싶은 값

2. ( c_{x,v} )

• 노드 ( x )에서 인접 노드 ( v )까지 이동하는 데 드는 비용 (가중치)
• 즉, x → v 로 가는 직접적인 비용

3. ( D_v(y) )

• 노드 ( v )에서 목적지 ( y )까지의 최소 비용 경로
• 즉, ( v )를 거쳐서 ( y )까지 가는 최적 비용

4. ( c_{x,v} + D_v(y) )

• ( x )에서 ( y )까지 가는 한 가지 경로의 비용
  • 먼저 ( x -> v ) 로 이동하고
  • 그다음 ( v -> y ) 까지의 최단 경로 비용 ( D_v(y) )을 더한 것

5. ( min_v { c_{x,v} + D_v(y) } )

• ( x )에서 ( y )까지 가는 가능한 모든 경로 중 최소 비용을 선택
• 즉, ( x )의 모든 인접 노드 ( v )에 대해 ( c_{x,v} + D_v(y) ) 값을 계산하고, 그 중 가장 작은 값을 선택
• 이 과정이 반복되면서 최소 비용이 점진적으로 업데이트

이런 뜻임 

단 우리가 구하고 싶은 값은 확정된 값 아니고 현재 값

 

DV 알고리즘의 key idea 부분은

-> 새 DV 정보 받으면 BF식 이용해서 자기 DV를 업데이트한다, natural condition에서는 그 예상 값이 실제 최소 비용 d_x(y)에 수렴한다

 

자 그러면

DV알고리즘에서 스스로 정보를 주고 받으면서 분산적으로(distributed) 한다면

언제 그걸 하나? 어떤 이벤트가 발생하면?

-> local link cost가 바뀔 때 거나 neighbor로부터 메시지를 받았거나

다시 계산해라, neighbor로부터 받은 값을 가지고.

 

==> 반복적(iterative, neighbor랑 교환 안 일어날 때까지), 아무때나 할 수 있어서 asynchronous(비동기적, 모든 노드가 정확히 맞물려있지 않아도 할 수 잇음)

언제끝난다 정해진 게 아니라 더이상 그런 일이 벌어지지 않으면 걍 자동으로 알고리즘이 끝난 것(self-stopping)

 

( <-> 링크 상태 알고리즘이 네트워크 전체 정보를 이용하는 알고리즘인 반면,
거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다)

 

 

예제가 9개 노드짜리라 되게 많이 써있는데

거리 비용을 받은 정보들로 계속 iterative하게 계산을 해본다~ 

주고 받았는데도 값이 변경되지 않으면 그때 알고리즘이 끝난다는 거

 

• DV 알고리즘에서 하나의 노드가 갖는 정보는 단지 자신에게 직접 연결된 이웃으로의 링크 비용과 그 이웃들로부터 수신하는 정보뿐이다.

 

계산할 떄 더 작은 값으로 변경되면 빨리 평형상태가(끝난다) 된다. 근데 큰 값으로 변경되면 루프 많이 계산해야함.

저걸 이용해서 패킷을 포워딩을 해야되면 Loop를 도는 현상이 발생할 수도 있다

목적지를 찾아가지 못하고 루프를 도는 현상이 발생할 수도 있음

 

 

 

참고

• 이미지 출처 : https://gaia.cs.umass.edu/kurose_ross/ppt.php