[네트워크] ch5.2 routing protocols

# ch 5.2 routing protocols(중요)

## routing protocol 라우팅 프로토콜

1. 라우팅 프로토콜의 목적

• : 좋은 path를 찾는 것
• path : 라우팅의 경로
• good path: 적은 비용, 빠르고, 가장 적은 혼잡

2. 그래프 graph

1) 개념

• 노드: 라우터
• edge: 링크

2) cost (비용)

• 개념: c(a,b) a부터 b 까지 경로의 비용
• 라우팅 알고리즘: 가장 적은 비용의 경로를 찾는 알고리즘

3. 라우팅 알고리즘 종류(routing algorithm classification)

1) global ( link state 알고리즘)

• 모든 라우터와 링크의 비용을 알고 있는 상태

2) decentralized(분산적)(distance vector 알고리즘)

• 직접 연결되거나 주변 노드와 링크 비용만 아는 상태
• 계속해서 주변 라우터와 소통

3) 정적/ 동적

• static : 루트가 거의 변하지 않음
• dynamic: 루트가 많이 바뀜(라우터, 비용)

## link state algorithm(LS) 링크상태 라우팅 알고리즘

1. 다익스트라(dijkstra's) 알고리즘

1) 개념

• 모든 노드,비용 알고있어야 한다(모든 라우터가 같은 정보 공유)
• source 노드로부터 최소비용 계산
• interactive : 반복적 계산

2) 기호

• c(x,y) : x부터y 까지 비용
• D(v) : 목적 노드v 까지의 비용
• p(v): predecessor v 노드 이전 노드
• N' : 최소비용 경로가 알려진 노드의 집합

3) 다익스트라 알고리즘 과정

• D(v) = min(D(v),D(w)+c(w,v))
• 최소 비용 경로 계속 비교하며 업데이트

4) 다익스트라 정보

• 시간복잡도 : O(n^2)
• oscillations 가능 : 비용이 같은 경로

 

 

## Distance vector algorithm

## Distance vector algorithm(DV) (거리벡터 라우팅 알고리즘)

• 주변의 노드와 링크만 보고

1. 벨만포드 방정식(동적계획법) (Bellman ford equation)

• 각 단계에서 최소값을 찾아가다보면 결국 최소비용경로

1) 기호

• dx(y): x에서 y 까지 최소비용 경로의 최소비용

2). 벨만포드 예시

• 이웃 노드들에서 각 목적지까지 최소 비용 비교

2. Distance vector algorithm(DV) (거리벡터 라우팅 알고리즘)

1) 기호

• Dx(y) : x부터 y 까지 예상 최소비용

2) 정의

• Dx(y) = min(c(x,y) + Dv(y))
• : 각 인접 노드까지 최소비용 비교하면서 마지막 목적지까지 최소비용 안다.

3) 특 징

• 반복적, 비동기적 : 노드마다 반복적으로 계산하고 메시지 노드들을 거쳐 전달
• 분산적 : 메시지가 노드들을 거쳐 분산된다

작동과정: 기다림 -> 메시지나,링크 비용 바뀜 -> 재계산 0> 이웃노드 전달

4) 예시

5) 링크 비용 변화시 작동

• y 가 링크비용 변화 감지
• y가 이웃노드 에게 변환 비용 전달
• z 가 메시지 받고 최소비용 업데이트 하고 이웃노드에 메시지 전송
• y는 z로부터 메시지 수신, 업데이트할 내용 없으므로 끝

6) count to infinity 문제

• : 링크비용이 변화시 업데이트 해야되는데 업데이트 내용 중에 다른 노드의 업데이트 안된 정보를 이용 -> 업데이트를 횟수가 엄청 많이 증가함
• 해결: poisoned reverse

• - 업데이트 안된 비용을 무한대로 바꿔준다.

3. LS / DV 비교

1) 메시지 복잡도

• LS : 모든 노드들에 전송
• DV: 이웃 노드만 교환

2) convergence 속도

• LS : O(n^2)
• DV: 상황에 따라 다름, infinity 문제 도 있음

3) 라우터 오작동에 대한 반응

• LS : 잘못된 링크비용 advertise
• DV: 잘못된 정보 전파 가능