Chapter 4.5: Routing Algorithm

Link-State Routing Algorithm

          > Dijkstra's Algorithm

                    >> 네트워크상 모든 노드가 링크 비용을 알고 있다

                    >> 가장 적은 비용이 드는 path (한 노드에서 다른 모든 노드로)

                              <Forwarding Table>

                    >> Iterative

                    >> Notation

                              <c(x,y): node x ~ node y 의 링크 비용 -> 바로 옆에 있는것이 아니라면 무한대>

                              <D(v): 현제에서 목표지점 v 까지의 비용>

                              <p(v): v까지 계산을 했을 때, 어느 노드를 통해서 왔는가(이전노드)>

                              <N': 노드를 하나씩 추가해 가며 추가된 노드의 집합>

Dijkstra's Algorithm

Dijkstra's Algorithm Example

Another Example

          > 알고리즘 복잡도: n nodes

                    >> 각 iteration 마다 모든 N' 에 속하지 않은 모든 노드 확인

                    >> O(n^2) --> 더 효율적이게 O(nlogn)에 가능

 

Distance Vector Algorithm

          > Bellman-Ford Equation (DP)

Bellman-Ford Equation

          > Dx(y) = x 에서 y 로 가는 예상 최소 비용

          > node x 에 대해:

                    >> neighbor v 에게 비용이 알려져 있다

x maintains distance vector

Bellman-Ford Example

 

 

          > Distance Vector Algorithm 의 Key Idea

                    >> 일정한 시간이 지나면 각 노드는, 각자의 distance vector를 보낸다.

                    >> x 가 새로운 DV를 이웃에게서 받으면, Bellman-Ford Equation을 사용해 자신의 DV를 update

                    >> 특정 조건 하에, Dx(y) 는 dx(y)에 수렴한다.

          > Distance Vector Algorithm은 

                    >> Iterative & Asynchronous

                              <각 로컬 iteration은 local link-cost 가 바뀔때, DV update 발생시에 일어난다>

                    >> Distributed

                              <각 노드는 DV가 바뀔때만 이웃에게 알린다>

 

          > Link Cost Changes

                    >> 노드가 local link cost change 를 감지한다

                    >> Routing 정보를 update, DV 다시 계산

                    >> DV가 바뀔 경우 이웃에게 알림

          > 위의 경우 다음과 같이 작동한다

                    >> t0: y 가 링크 비용 변경을 감지, DV update, 이웃에게 알린다.

                    >> t1: z는 y로부터 업데이트를 받고, 자신의 테이블을 업데이트 하고 x로의 새로운 최소 비용을 계산, DV                                         update 후 알림

                    >> t2: y는 z의 업데이트를 받고 DV를 update. y 의 최소 비용이 변경 되지 않았기에 y는 메세지를 보내지 않음

          > 위의 상황에서 만약 Z가 X 로 가기위해 Y를 경유한다면...(Poisoned Reverse)

                    >> Z는 Y 에게 X 까지의 거리가 무한대임을 알린다 --> Y는 Z를 통해 가지 않음

                    >> 무한대 거리를 가진 링크를 가진 노드가 루프를 만들어 무한루프를 도는 문제를 해결할 수 있지만 계수 무한대 문제를 해결할 수 없다.

 

Link-State vs. Distance Vector

          > Message Complexity

                    >> LS: n개의 노드, E 개의 링크일 경우 O(nE)

                    >> DV: 이웃 사이에 교환... convergence time varies

          > Speed of Convergence

                    >> LS: O(n^2)

                    >> DV: Convergence time varies

                              <routing loop 이 생길 수 있음>

                              <count-to-infinity 문제 발생 가능>

          > Robustness(라우터가 오작동하면 무슨일이 발생하는가?)

                    >> LS: 노드가 틀린 링크 비용을 알릴 수 있음

                              <각 노드는 자신의 비용만 계산>

                    >> DV: DV 노드는 틀린 path cost를 알릴 수 있음

                              <각 노드의 table은 다른 노드들이 사용>