[네트워크] #18 라우팅 프로토콜, Link status algorithm vs. Distance vector algorithm

목차

1. 라우팅 프로토콜
2. Link status algorithm vs. Distance vector algorithm

---

1. 라우팅 프로토콜

라우팅 프로토콜 목표: 라우터 네트워크를 통해 송신 호스트에서 수신 호스토로의 최적의 경로를 결정

네트워크의 그래프 추상화

그래프: G = (N,E)

 

N = 라우터 집합

-> {u, v, w, x, y, z }

 

E = 링크 집합

-> { (u,v), (u,x), (v,x), (v,w), (x,y), (w,y), (w,z), (y,z) }

 

c(x,x') = 링크 비용(x,x')

-> 예를 들어, c(w,z) = 5

-> 비용은 대역폭, u 또는 혼잡과 역으로 관련될 수 있음

 

경로 비용(x1, x2, x3,..., xp)

-> c(x1,x2) + c(x2,x3) + ... + c(xp-1,xp)

 

라우팅 알고리즘 분류

Global vs. Decentralized

Global

• 모든 라우터에 완전한 링크 비용 정보가 있음
• link status algorithm (링크 상태 알고리즘)
• Link status 알고리즘 (Dijkstra's algorithm, Example, Oscillation problem)

 

Decentralized

• 라우터는 물리적으로 연결된 이웃과 이웃으로 가는 링크 비용을 앎
• 계산의 반복 과정, 이웃들과의 정보 교환
• Distance vector algorithm (거리 벡터 알고리즘)
• Distance vector 알고리즘 (Bellman-Ford equation, Example, 문제점)

 

static vs. dynamic

static

• 경로가 거의 바뀌지 않는 상황

 

dynamic

• 경로가 빠르게 변함
  • 주기적 업데이트
  • 링크 비용 변화에 대응

---

2. Link status algorithm vs. Distance vector algorithm

	Link status algorithm(LS)	Distance vector algorithm(DS)
Message complexity	O(N^2)	이웃 노드끼리만 데이터 전달 수렴 시간이 노드마다 다름
Speed of convergence	O(N^2) oscillation 발생 가능	수렴 시간이 노드마다 다름 routing loops, count-to-infinity problem 발생 가능
Robustness (오작동 시)	잘못된 값 계산 시 해당 노드 자신만 문제가 생김	잘못된 값 계신 시 주변 노드들까지 잘못된 정보가 전달됨

 

결론: LS는 대규모 네트워크에 적합, DS는 소규모 네트워크에 적합