Routing

Routing이란?

- 패킷을 목적지로 전하기 위해 다음 전달 노드를 결정하고 해당 노드로 전달하는 과정 

- Routing Table 이라는 자료구조를 활용

 

Routing 에는 Shortest Path Problem이 존재

즉 가장 최적화된 길을 찾는 문제가 계속 있었습니다.

 

 

2 Basic Routing Architecture

1) Distance-Vector (거리 벡터)

2) Link-State (링크상태)

 

 

	Distance-Vector	Link-State
Algorithm	Distributed Bellman-Ford	Dijkstra
Routing Info	Distance-Vector	Link-State
Exchange with	Neighbor Routers	All Routers in the Network
Standard Routing Protocol	RIP(Routing Information Protocol)	OSPF(Open Shortest Path First)

 

Routing 간에 information 교환을 위해 Routing protocol 을 이용.

이 프로토콜은 Routing Algorithm을 실행시킴. Forwarding/Routing Table 을 통해

 

 

-Distance-Vector는 이웃 노드끼리만 정보를 공유함. 업데이트 많이 시켜서 최적의 루트를 얻음. 이 업데이트에 사용하는 알고리즘이 Distributed Bellman-Ford Algorithm임. 

 

-Link States 는 모든 노드가 정보를 교환함. 전반적인 topology을 한번에 볼 수 있음. Dijkstra algorithm 을 이용해 모든 목적지에서의 최적화 path를 얻어냄.

 

 

distance-Vector에는 큰 문제가 있는데 Count-to-Infinity Problem이다. 이는 만약 A,B,C,D 라는 노드가 존재할때 A,B 가 끊어졌다. C는 이 사실을 모르기 때문에 routing loop 에 빠지게 됨. 이는 목적지로 못가고 계속 패킷을 도는 거를 의미함.

다음과 같이 A와 B가 끊어졌음에도 불구하고 C는 그걸 알지 못한 채로 B로 가는 거리가 줄어들었다 판단하여 계속계속 업데이트하는 상황.