[ch5] 2. routing protocols

Routing protocols

global info. vs decentralized info.
- global:
  - 모든 router, link cost에 대한 정보를 알아야 함
  - "link state" algorithms
- decentralized
  - router들은 완전한 구조를 몰라도 됨
  - 물리적으로 인접해 있는 이웃노드와 link cost만 알면 됨
  - iterative한 계산
  - "distance vector" algorithms
static vs dynamic
- static: routes는 느리게 바뀜
- dynamic: routes가 빠르게 바뀜
  - 주기적인 업데이트
  - link cost에 대한 변화

Dijkstra's algorithm
- 모든 노드가 모든 노드에 대한 net topology, link cost를 알아야 함
- one node --> all nodes로 가는 least cost path 계산
  - node에 대한 forwarding table를 만듦
- iterative: after k iterations, know least cost path to k destinations
algorithm complexity
- n개의 node
- O(n): get min, O(n): search adj node
  - heap 사용하면 get min 단계를 O(log n)로 줄일 수 있음
  - O(n logn)
oscillations possible
- link cost는 같으나 router에서 delay가 생기는 경우

dynamic programming
주요 아이디어
- 각 노드는 자신의 distance vector 추정치를 인접노드로 보냄
- 노드 x가 새로운 dv를 인접노드로 부터 받았을 때, B-F equation을 사용해서 dv를 업데이트 한다.
  - equation: D_x(y) <- min_v{c(x,v) + D_v(y)} for each node y in N
iterative, asynchronous
- 각각의 local iteration은 다음과 같은 경우에 발생한다.
  - local link cost가 바뀌었을 때
  - DV update message가 이웃으로부터 왔을 때
distributed
- DV가 업데이트될 때 각각의 node는 인접노드에게 알린다
  - 이웃은 필요시 그들의 이웃에게 알림
list cost는 다음과 같은 경우에 바뀜
- node가 local link cost가 바뀐 것을 알아차렸을 때
- routing info를 업데이트하고, distance vector를 다시 계산할 때
- DV가 바뀐다면, 이웃에게 알려줌
  - good news travels fast
  - bad news travels slow
poisoned reverse
- route가 없다고 선의의 거짓말을 하는 것

message complexity
- LS: O(nE)
- DV: neighbors 사이의 메시지 교환
speed of convergence
- LS: O(n^2) (O(nE))
- DV: convergence time이 다양함
  - routing loops, count-to-infinity
robustness: router에 문제가 생기면?
- LS: node는 잘못된 link cost를 알릴 수 있음
  - 각 노드는 자신의 테이블만 계산
- DV: node는 잘못된 path cost를 알릴 수 있음
  - 각 노드는 다른 노드의 테이블을 사용해 error가 network를 타고 전파될 수 있음