Unicast Routing
Autonomous System(이하 AS)는 하나의 독립적인 네트워크이며 인터넷들은 이러한 AS들의 연결로 이루어져 있다.
Routing Protocol은 Intradomain(AS 내 통신), Interdomain(AS 끼리 통신)으로 구분된다.
- Intradomain
- Distance vector(RIP)
- Link state(OSPF)
- Interdomain
- Path vector(BGP)
각 사용되는 개념(프로토콜 이름) 이며
Intradomain은 최단경로, Interdomain은 규칙기반경로 설정이다.
Distance vector Routing
Distance vector Routing 에서는 Bellman-Ford 알고리즘이 사용된다.
i에서 j로 갈 때 shortest path를 찾는다.
초기에 각 노드들이 이러한 테이블을 가지고 있다고 가정해보자
테이블은 직접 연결된 노드들에 대해서만 정보를 가지고 있다.
Distance vector 개념은 인접한 노드들끼리 서로 테이블을 교환하면서 정보를 계속 업데이트 해나가는 것이다.
A가 C에게 테이블을 받으면 Next는 C로 두고 받은 테이블에 C로 가는 cost를 더해서 임시 테이블을 생성한다.
이후 원래 테이블과 비교하여 새로운 테이블로 업데이트 한다.
자신에게 변동사항이 생기면 인접 노드들과 테이블을 주고 받으면서 계속 업데이트 해나가는 방식이다.
다만 여기서는 cost만을 가지고 적은 cost만 골랐지만 문제가 생기는 경우가 있다.
C에게 받은 테이블이 E로 가는 cost가 네트워크 상황에 의해 늘어났다고 가정해보자
cost만 보고 비교하면 업데이트가 안되겠지만 업데이트를 해야하는 상황이다.
따라서 Next가 같다면 Cost에 상관없이 무조건 업데이트 해야한다.
다만 이 방식은 무한 Loop를 초래할 수 있는데
맨 위 상황에서 A가 X와의 연결이 끊어졌다고 가정해보자
이때 A가 B에게 테이블을 받게 된다면
B로 보내면 X로 도달할 수 있다고 착각하게 되는 것이다.
이후 다시 B가 A에게 받게 되면 next가 같기에 업데이트 하고
이 상황이 계속 반복된다.
이것을 해결하기 위해 3가지 방법을 제시할 수 있는데
-
무한대를 16으로 설정하는 것이다.
AS 내에서 router가 16개나 지나간다는 것은 네트워크 구축이 잘못되었다는 의미의 매우 큰 숫자이다.
일반적으로는 2~3 개면 AS를 벗어난다. -
Split Horizon
Next가 상대이면 안보내주는 것이다. -
Split Horizon and Poison Reverse
Next가 상대이면 cost를 무한대로 설정해서 보낸다.
cost가 무한대면 갈 수 없다는 의미와 같다.
다만 이런 해결 방식에도 무한 Loop가 생성되는 경우가 또 발생하는데
A가 X와의 연결이 끊어진 상태에서 B에겐 알렸지만 C에게 알리려고 할 때 Loss가 발생한 상황이다.
C는 자신의 테이블을 A한테는 안보내지만 B에게 보내어
B는 C로 보내면 X에게 도달할 수 있다고 착각한다.
그럼 다시 A에게 X로 갈 수 있는 길이 생겼다고 알리고
이 Loop가 반복된다.
Link State Route
위에서 본 Distance vector의 개념은 초기 상태에서 인접 노드들 끼리 테이블을 주고 받으면서
시간의 흐름에 따라 완전한 테이블을 구축하는 것이다.
Link State 개념은 모든 노드가 어떻게 연결되어 있는지를 서로 공유한 다음
자신을 Root로 하는 Tree에 대해 모든 노드의 최단경로 알고리즘을 적용하여 테이블을 생성하는 것이다.
일반적인 경우에 Link State를 많이 사용하는데 이유는 Distance vector는 테이블을 구축하는 데 있어서 시간이 걸리기 때문이다.
우리는 최단경로 알고리즘에서 다익스트라 알고리즘을 많이 사용하고 쉽기 때문에 설명은 생략한다.
