라우팅 프로토콜
가장 좋은 path를 결정하는것. 가장 효율적으로 보낼 방법 찾기
네트워크 그래프 묘사
숫자가 크면 => 대역폭 작고, 혼잡도 높아.
- Cost of path
라우팅 알고리즘
source~ dst 까지 어떤 경로가 가장 적은 cost로 보낼 수 있는가
Global
모든 라우터들이 완벽한 topology(형상) 을 가지고있고 link cost정보도 갖고 있음
link state 알고리즘
- 모든 링크상태의 정보("모든 노드의 cost정보")를 가지고 라우팅.
- 자신이 변화가 있는지를 주기적 체크하고 상태를 주변 노드한테 알려주는 link state broadcast 사용.
모든 node들에 대한 라우팅 패스를 최소화하는 방법을 계산 => forwarding 테이블에 반영됨
- 다익스트라 알고리즘을 이용
V는 노드
교재에서는 EX2
p(v)는 v까지 가는데 필요한 이전 노드
n개의 노드가 있을때 가능한 링크 코스트는 n(n+1)/2 => O(n^2)
- 단점
진동이 가능하다는 점.
어디는 패킷이 많고, 어디는 적고 해서 경로가 바뀔 수 있어
=> 링크 state를 공유하기 때문에 어디가 빈지 알아서 가능
Decentralized
지역화된 정보를 가지고 라우팅 함. 주변 노드의 link cost만 알고 라우팅 함
distance vector 알고리즘
d가 계산한 값에 이웃노드에서 변경된 값을 구해주면, 이 둘 비교해서 최적값 찾기
- Bellman-Ford equation 사용
dx(y) : x로부터 y까지의 최소 경로에 대한 cost.
dx(y) = x를 기점으로 이웃노드에 대한 link cost가 있는데 이 값 + v라는 노드에서 y까지의 최소 거리를 더한 것들의 "최솟값"
- u에서 z까지의 최소 경로
핵심
- 이웃노드로 갈 수 있는 최적의 값을 받은 다음 내 기점으로 link cost를 보면서 최종 dst에 빠르게 가는 경로 찾기 => 이웃 노드의 도움을 받아 예상하기, 링크 코스트가 변하거나 주변노드가 변할때 벡터가 수정됨.
라우팅 프로토콜 링크 스테이트 vs 디스턴스 벡터 알고리즘 비교
메세지 복잡성
- LS: 메세지 보낼때 N개 노드 x E개 링크 필요
- DV: 이웃노드끼리만 데이터 교환하면 됨
속도
- LS: 노드가 정해지면 메세지도 정해지고, 진동 있더라도 cost가 고정임
- DV: 라우팅 loop, infinity 문제가 생길수도 있음. 대규모 네트워크에 적합X
견고함
- LS: 각자 계산을 해서 노드가 하나 실수하면 자신의 포워딩 테이블만 잘못됨(대규모 적합)
- DV: 이웃노드에게 계산 값을 알려줘서 똥싸면 연쇄적으로 클나..
(소규모 적합)
