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': 노드를 하나씩 추가해 가며 추가된 노드의 집합>
> 알고리즘 복잡도: n nodes
>> 각 iteration 마다 모든 N' 에 속하지 않은 모든 노드 확인
>> O(n^2) --> 더 효율적이게 O(nlogn)에 가능
Distance Vector Algorithm
> Bellman-Ford Equation (DP)
> Dx(y) = x 에서 y 로 가는 예상 최소 비용
> node x 에 대해:
>> neighbor v 에게 비용이 알려져 있다
> 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은 다른 노드들이 사용>