Unicast Routing Protocol

Routing Protocol의 종류에는 Intradomain과 Interdomain이 있다.

 

Intradomain에는 Distance vector(RIP) , Link state(OSPF)가 존재하고,

Interdomain에는 Path vector(BGP)가 존재한다.

 

Intradomain - 도메인 안에서의 경로설정 (Autonomous system 내부)

각 라우터들이 패킷을 받았을 때, 게이트웨이까지 가는 최단 경로를 구하는 일

Interdomain - AS 외부에서 경로설정 (AS 끼리)

정책,비용,보안에 따라 최단경로보다 돌아가는게 더 좋을수도 있음. 따라서, AS 끼리의 경로는 최단 경로 우선이 아니라, 특정 rule에 기반한 rule-base로 결정함.

 

Bellman-Ford algorithm

가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘으로, Dij = i와 j 사이에 최단 거리 / Cij = i와 j 사이의 비용 / N = 노드의 수

Dij = Min( (Ci1+Dij) , (Ci2+D2j) ,,,,, (CiN + DNj) )이다.

 

Distance vector routing tables

각 노드들은 테이블을 관리하여 To / Cost / Next의 정보를 실시간으로 업데이트하며 테이블 정보를 변경한다.

Ex) C 테이블의 정보를 받으면 A 테이블을 수정하고, A의 Old table과 비교하여 A의 New Table을 생성한다.

이 때 중요한 점이 있는데 테이블에서 Next가 다를 경우에는 임시 테이블과 비교해서 비용이 작은것으로 업데이트하고, Next가 같은 경우에는 비용이 크더라도 새로 받은 값으로 업데이트 해야한다. 이러한 이유는 경로가 늘어났을 때 최신 정보가 반영이 되지 않을 수 있으므로 Next가 같은 경우에는 꼭 비용이 크더라도 최단경로가 아니라 새로 받은 값으로 업데이트 해야한다. ( 즉, 누가 보내는 table인지 아는 것이 중요.)

 

Two-node instability

Table을 업데이트 하는 방식에는 주기적으로 교환하는 방법과 수정이 되면 교환하는 방법이 있는데, 2개의 경로가 연결되어 있는 도중에 한 경로가 끊어지면, A와 B는 각자 테이블을 업데이트하고 서로에게 보내 줄 것이다. 이 때, packet이 오는 도중에 update가 되버릴 경우 계속 정보가 수정되기 때문에 Loop가 형성된다. (TTL이 필요한 이유) 이를 두 노드의 불안정이라고 한다.

 

해결 방법

1. 경로의 최대값을 16으로 설정 ( 네트워크에서 누적 경로가 16개면 엄청나게 큰 것이므로, 16까지 도달할 경우 갈 길이 없어 Loop라고 판단하고 Stop)

2. Split horizaon ( 경로가 끊어져 A,B가 업데이트되고 서로에게 보낼 때, A에게는 A가 next로 되어있는 라우팅 정보는 보내지 않는 기법을 말한다.

3. Split horizon & Poison reverse ( 해당하는 cost를 무한대로 보내는 것)