Unicast Routing 중, Distance vector 알고리즘을 기반한 RIP routing protocol을 알아보자.
Autonomous System이란 하나의 조직이나 단체에서 관리하는 네트워크들의 단위이다.
AS끼리 연결되는 라우터가 존재하며 이를 gateway라 한다.(라우터는 네트워크와 네트워크를 연결한다.)
이 gateway끼리의 패킷 경로 설정은 나중에 배운다.
gateway까지의 최단거리를 구하는 알고리즘과 프로토콜을 먼저 배운다.
Interdomain은 AS들 끼리의 routing protocol이다. Intradomain은 하나의 AS 안에서의 routing protocol이다. 이는 두 가지가 존재한다.
일단 Intradomain의 Distance vector 알고리즘을 기반한 RIP 프로토콜을 알아본다.
이는 하나의 AS에서 최단경로를 구하며 테이블을 업데이트하는 방법을 배운다.
참고로, BGP 프로토콜은 무조건 최단경로가 아니다. 이는 cost, 즉 돈이 들어가기 때문이다. 더 싼값으로 좀 더 latency가 있더라도 돌아갈 수도 있다.
위의 이미지를 보면 i에서 j로 가기 위해 경로의 cost 등을 사전에 안다고 했을 때 위와 같이 쉽게 구할 수 있다.
Distance Vector Routing Tables
하나의 AC안에 있는 routing table들이다. 각각의 정점은 router이고 간선은 가중치, 즉 걸리는 시간이라 하자.
우선 라우터마다, 테이블이 수정될 때, 수정된 테이블을 라우터에게 전송한다. 이렇게 수정될 때마다 전송해줘야 AC 안의 최단거리 정보가 담긴 라우팅 테이블들을 빠르게 구축할 수 있다.
라우팅 테이블이 수정되는 과정은 다음과 같다.
- A는 C로부터 수정된 라우팅 테이블을 받는다.
- A는 기존의 라우팅 테이블의 copy본을 만들고 이를 다음과 같이 수정한다.
- destination이 동일한 row에 A에서 C까지는 cost와 C에서 dst까지 가는 cost 서로 더해준다. 그리고 Next를 C로 저장한다.
- A의 table에 존재하지 않으면 추가한다.
- 기존의 테이블과 비교하여 row 값을 수정한다.
- cost가 더 작은 경우, row 값을 수정한다. Next를 C로 설정한다.
- 이전에 없던 row가 있는 경우, row를 추가한다. Next를 C로 설정한다.
- 만약 A table에 next와 To와 동일한 값을 가진 row가 C table에 존재하면 cost가 작던 크던 무조건 수정한다. C가 업데이트 된 이후기 때문에 더 최적의 거리일 수도 있음(이놈이 문제를 유발한다.)
이 방법으로 생기는 문제점과 해결책을 알아본다.
- Before failure: 문제 발생 이전 상황이다.
- After failure: A에서 X로 가는 링크가 하드웨어적 문제로 작동하지 않는다.
이 때 A에서 X로 가는 cost는 무한대가 된다.(Time expired 발생 주기적으로 table을 교환함) 이 정보를 A가 B로 전달해야하는데, 이 전에 B가 수정된 테이블을 미리 보냈을 때 문제가 발생한다.- After A receives update from B: A는 B의 테이블 정보를 보고 무한대보다 작은 3(2+1)으로 cost를 수정한다.
- After B receives update from A: A는 다시 수정된 테이블을 B한테 보내 B는 4(3+1)로 값을 수정한다.
- Finally: 시간이 지나 서로의 cost가 무한대가 될 때까지 table을 수정한다.
하나의 loop이 생긴 꼴이다. 이를 어떻게 해결해야할까?
라우터를 껐다 켜도 된다.
- 무한대 값을 16으로 설정한다. 그리고 무한대를 넘어가면 detect 한다.(라우터 20개를 거치면 미국간다.)
- Split horizon: B의 테이블에서 next가 A인 것은 애초에 보내지 않는다.(A가 들고 있는 정보가 optimal cost를 알아서 가진다.)
근데 이 방법도 안 된다. 만약 B 테이블에 next가 A인 row만 존재하면 table을 주기적으로 전송하지 못해 B가 A가 고장난줄 안다. - Split horizon and poison revers: next가 A인 것을 보내되, cost를 무한대로 설정한다.
무한대니, cost 수정은 절대 발생하지 않는다.
그런데 마지막 해결책도 문제를 유발한다.
3 node
그러나 Split horizon and poison revers도 문제가 있다.
바로 노드 세개가 연결된 경우이다. X로 가는 link가 끊어진 경우 A는 라우팅 테이블에서 X의 cost를 무한대로 설정한다.
이후 업데이트 된 테이블을 B와 C에게 알려주는데, 이 때 C로 가는 테이블 패킷이 소실되었다고 가정하자.
그럼 B는 X로 가는 경로의 cost를 무한대로 설정하겠지만 C는 여전하다. 시간이 지난후 C는 B에게 테이블 정보를 보낼 것이고 B는 이를 cost를 3으로 설정할 것이다. 그럼 A에게 B는 이 업데이트 정보를 보내고 A는 4로 설정한다. 또 하나의 루프가 발생한다.
물론 설정된 무한대만큼 패킷이 돌면 마지막엔 무한대로 설정되어 X로 이동하지 않을 것이다.
실제로 loop는 detect하기 매우 어렵다고 한다.
