Routing Protocols

CinnamonTree·2022년 6월 14일
0

네트워크

목록 보기
7/7

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밖에 모름)

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를 업데이트 한다.

  • 단점: 큰 네트워크에서는 시간이 많이 걸린다.
  1. wait: 이웃으로부터 cost변화가 있기까지 기다림
  2. recompute: DV계산

변화가 있는 노드만 neighbor에 소식을 전달하기 때문에 asynchronous, iterative함.

  • count to infinity problem 발생 가능.

0개의 댓글