5.2 Routing protocols

1. link-state routin algorithm

- Dijkstra's algorithm

D(v) = min(D(v), D(w) + c(w, v))

O(n^2) --> O(nlogn) 까지도 효율 향상 가능

※oscillations possible

- 상기의 알고리즘은 진동 문제를 발생시킬 수 있다.

- 혼잡을 피하기 위해 특정 상황에 한 경로로 트래픽이 몰리면 다음 상황에는 다른 경로로 변경. 이 작동이 반복됨

2. Distance vector algorith

- Bellman-Ford equation (dynamic programming)

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

=> d(xy) = min{c(x, v) + d(vy) (v는 x의 모든 이웃)

- 각 노드의 동작

1) 이웃 노드에서 local link cost나 msg 전송되는 것을 대기

2) 경로 재계산

3) 도착 비용이 변경된 경우 이웃들에게 이를 알림

※ link cost changes

- 링크의 비용 변경 시, 타 라우팅 테이블의 정보가 신속히 반응하지 않기 때문에 잘못된 가중치의 경로를 이용하는 경우가 발생

=> posoned reverse : z 가 y를 통해 x로 갈 때, z는 y에게 z->x의 가중치를 무한대로 전송

『두 알고리즘의 비교』

1) 메시지 복잡성

-  LS : O(nE)

- DV : 이웃들 끼리만 교환

2) 수렴 속도

-  LS : O(n^2)

- DV : 매우 천천히 수렴, 무한 카운트 문제

3) 강건성

-  LS : 틀린 비용 브로드캐스트 가능하지만, 자신의 테이블만 계산

- DV : 잘못된 최소비용경로를 여러, 혹은 모든 목적지에 알릴 수 있다.