Routing Protocols
Routing protocol goal: 좋은 Path를 찾아내기 위함.
Graph abstraction
link cost = 'hop count' or 'bandwidth의 역수'
Routing algorithm classification:
- global(link state알고리즘: 모든 라우터는 전체 topology를 가짐)
- decentralized(distance vector알고리즘: 라우터들은 초기에는 이웃의 link cost밖에 모름)
Link state algorithm
Dijkstra's shortest path algorithm이 쓰인다.
-
centralized: 모든 라우터는 전체 topology를 가지며, 모든 노드로 가는 link cost를 안다 => 자신의 link state를 broadcast함으로서.
-
algorithm complexity:
- n개 node가 있을 때 n번 반복, 총 n(n+1)/2번 비교 = O(n2)
- 효율적인 방식 = O(nlogn)
-
단점: instant traffic volume을 이용하여 routing을 할 경우 Oscillation현상이 발생할 수 있음.(synchronous함)
Distance Vector algorithm
벨만 포드 알고리즘(dynamic programming)사용
V: neighbor를 뜻함
Key Idea: 각각의 path cost(distance vector)를 neighbor끼리 교환을 하고 BF수식으로 자신의 distance vector를 업데이트 한다.
- 단점: 큰 네트워크에서는 시간이 많이 걸린다.
- wait: 이웃으로부터 cost변화가 있기까지 기다림
- recompute: DV계산
변화가 있는 노드만 neighbor에 소식을 전달하기 때문에 asynchronous, iterative함.
- count to infinity problem 발생 가능.
