Unicast Routing Protocol - Autonomous system, Routing protocol, Routing algorithm, Link state routing

Unicast Routing Protocol

Unicast Routing Protocol

- Routing table을 생성

- Routing table을 통해 packet 전송

Autonomous system(AS)

- 하나의 관리자에 의해 운용되는 router를 포함한 한 network

- router가 관리하는 범위의 네트워크

Routing Protocol의 종류

- routing protocol은 크게 두 가지로 나누어짐

1) Intradomain

- 한 AS에서 router까지 가는 경로를 가지고 routing

-> RIP, OSPF

2) Interdomatin

- AS끼리의 경로를 가지고 routing

-> BGP

-> routing시 최단경로, traffic 비용, 안정성 등 여러가지 고려사항을 보고 선택

Distance vector(RIP) Algorithm

1. Bellman-Ford algorithm

- 가장 간단하고 기본적인 Algorithm

- 시작에서 각 node로 가는 비용 + 각 node에서 최단 경로의 값 중 최소값을 선택하는 방법

2. Distance vector Algorithm

- Router들 끼리 서로 routing table을 공유하며 알지 못했던 경로를 채워나가며 routing table을 구성하는 방식

- Timer가 끝나거나 자신의 table이 update될 때 routing table을 주고 받음

- 자기 자신은 cost 0으로 표시

- 인접한 router들의 비용은 알기 때문에 바로 table에 기록

- 인접한 router들과 routing table을 교환하며 routing table을 채워나감

Example)

- 이러한 network가 형성되어있을 때 최초의 routing table의 모습

이 상태에서 A가 C의 routing table을 받은 경우 다음과 같이 진행된다.

- C의 table을 받은 A는 A->C의 경로의 cost와 C에게 받은 table을 더해 새로운 table을 생성한다

- 이 table과 원래 가지고 있던 table을 비교하여 최소의 cost를 가지는 항목들을 넣어 새로운 table을 구성한다.

- 추후 routing table을 받았을 때 next가 같은 경우 update가 된 것이기 때문에 새로운 것의 cost가 크더라도 변경해준다.

-> 이러한 형태로 router들끼리 서로 routing table을 공유하며 routing table을 완성한다.

Distance vector algorithm에서 생길 수 있는 문제점

① Two-node instability

- 초기에는 제대로 table을 가지고 있는 것을 볼 수 있다.

- X-A의 link가 깨진 경우 A의 table은 2번째 그림처럼 바뀌게 된다.

- 정상적으로 동작하기 위해서는 A의 table을 B에 전송해서 B의 table이 update되야 한다.

- 하지만 여기서 만약 B의 table이 먼저에 A에 전송되게 되면 3번째 그림과 같이 이상이 생기게 된다.

- 실제로 X로 갈 수 있는 경로는 없지만 A와 B가 서로 잘못된 table을 계속 교환하며 loop가 생기게 된다.

Solution

1) 무한대의 값을 default로 잡아서 그 값이 되면 없애는 방법

2) Split Horizon

- B->A로 보낼 때 Next가 A인 정보는 보내지 않음

-> Next가 보내는 대상일 경우 보내지 않는 방법

3) Split Horizon & Poison Reverse

- B-A로 보낼 때 Next가 A인 정보는 cost를 무한대 값으로 해 보냄

-> Next가 보내는 대상일 경우 cost를 무한대로 해서 보내는 방법

② Three-node instability

- Two-node에서 발생하는 error에 대한 해결책으로 해결할 수 없는 error

- 초기에는 제대로 된 table을 가지고 있음

- A-X의 link가 끊기고 A의 table은 update가 되고 A->B, A->C로 update된 내용을 보내주게 된다.

- 만약 A->C로 보내는 정보가 loss된다면 두 번째 그림처럼 C의 table은 수정되지 않는다.

- 이 경우에서 C->B로 table을 보내 update하고 B->A로 table을 보내 update가 되면 밑의 그림처럼 loop가 생기게 된다.

- 이 경우는 two-node에서 언급한 방식으로 해결할 수 없다.

Link state Routing(OFPS)

- Distance vector와 달리 각 router가 모든 경로로 가는 cost가 기록된 topology를 갖고 있음

- 이 topology를 통해 cost와 next router가 표시된 routing table을 생성함

다음과 같이 network에 대한 topology를 각 router가 가지고 있음

- 각 router는 정보를 모두에게 보내고 각자가 전체의 topology를 만들고 topology를 가지고 최단경로(shortest pass tree)를 구성한다.

-> 여기서 최단 경로를 구할 때는 Dijkstra's Algorithm을 사용한다.

-> 다익스트라 알고리즘을 이용해 구한 최단 경로로 table을 구성

http://dongdd.tistory.com/42  - 다익스트라 알고리즘