Routing protocols in Internet
internet은 interconnection of network라는 뜻으로 이는 네트워크를 서로 연결한다는 뜻이다.
(대문자 I를 사용하는 Internet은 TCP/IP를 이용하여 전세계 호스트와 상호통신이 가능한 대규모의 네트워크를 말하며, 소문자 internet과는 뜻이 다르다)
이 네트워크를 연결해주는 장치를 Router라고 한다고 했다. 즉, 인터넷이란, 라우터에 의해 여러 개의 네트워크가 결합되어 있는 형태를 말한다. 이런 형태의 인터넷에서는 IP 프로토콜을 사용하는데, 이 IP 프로토콜은 데이터그램 서비스를 기본으로 한다.
이 Datagram Service는 Connectionless하며 Unreliable한 서비스이다. 자세한 내용은 TCP에서 다시 언급된다.
이때, Datagram Packet을 보낼 때 이 Packet을 어디로 보낼 지를 결정해야 한다. 여기서 어떤 경로가 좋은 지를 판단하기 위해서는 기준이 필요하다. 이 기준을 Metric이라고 한다.
Metric은 네트워크마다 부과되는 코스트로, 이 네트워크를 지나가기 위한 비용, 더 쉽게는 네트워크 간 거리 정도로 생각하면 된다. 라우터는 이 Metric이 가장 작은 경로를 선택해서 Packet을 보내는데, 이 Shortest Path를 계산하는 프로토콜로는 RIP과 OSPF가 있다. RIP같은 경우에는 모든 Metric을 일치시킨 상태로 동작한다. 뒤에서 자세히 다뤄보자.
Interior and exterior routing
AS (Autonomous system)
하나의 관리 기구에 의해 관리되는 네트워크
갑자기 왜 AS가 나오고 Interior, exterior이라는 용어들이 나왔을까? 앞에서 말한 RIP과 OSPF가 바로 Interior routing의 종류이기 때문이다.
AS는 한 대학의 네트워크를 정보처에서 주관하는 것처럼 하나의 관리 기구(=정보처)에 의해 관리되는 네트워크를 말한다.
이 한 AS 내에서 동작하는 프로토콜을 Interior routing이라고 하고, AS 내에 있는 컴퓨터가 다른 AS에 있는 컴퓨터와 통신할 때 사용하는 프로토콜은 Exterior routing이라고 한다.
RIP
RIP는 Distance Vector Routing Algorithm을 기반으로 하는 프로토콜이다. 즉, Distributed Asynchronous Bellman-Ford Algorithm을 기반으로 한다.
Distance vector routing은 인접 라우터들이 주기적으로 자신이 알고 있는 정보들을 뿌려준다. 라우터가 속한 AS에 대해 라우터가 아는 정보를 인접 라우터들에게 일정한 간격으로 Broadcast 하는 방식으로 동작한다. 그래서 자신이 아는 정보를 Broadcast 한 후에는 다른 라우터가 Broadcast한 정보를 받아 자신의 라우팅 테이블 정보를 업데이트한다.
라우팅 테이블 정보
라우팅 테이블에는 Destination address, Subnet mask, Next hop 정보가 포함되어 있었다. 이제는 라우팅 테이블에 Hop Count라는 정보를 더 줘야 한다. 이건 Shortest Path로 목적지 노드까지 갈 때 거치는 라우터의 개수를 의미한다. 이때, RIP은 앞서 말했듯 모든 Metric을 동일하게 취급하기 때문에 Hop Count가 곧 그 경로의 Cost가 된다.
이렇게 만들어진 라우팅 테이블 엔트리를 주기적으로 인접 라우터들에게 알려주고 자신도 그 정보들을 받아 엔트리를 업데이트 하는 것이 RIP이다.
RIP Updating Algorihm
RIP 메시지를 받았다면
- 자신이 받은 정보에 1을 더한다. (인접 노드와 자신과의 Cost를 더하는 과정)
- 라우팅 테이블에 Destinatoin 정보가 없으면 해당 정보를 테이블에 새로 추가한다.
-> 지금까지 이 경로에 대한 정보가 없었다는 것이므로 새로 테이블에 추가 - 라우팅 테이블에 Destination 정보가 있다면 Next Hop 필드를 확인한다.
- Next Hop 필드가 같다면 새로 들어온 정보로 기존 정보를 교체한다.
-> Next Hop 필드가 같다는 것은 Shortest Path로 가는 노드에서 보내준 정보이므로, 이 경로가 제일 좋은 경로일 것이다. 그 경로에서 새로 보내준 정보이므로 이 정보는 네트워크 상황이나 혹은 현재 경로의 여러 문제 상황 등을 고려한 최신 정보이므로 라우팅 테이블에 이런 최신 정보를 반영하기 위해 기존 정보를 신규 정보로 교체한다. - Next Hop 필드가 다르다면 Hop Count를 확인한다.
- Hop Count가 테이블에 있는 것보다 작다면 테이블에 기존 정보를 교체한다.
-> 기존 Shortest Path가 아닌 다른 노드에서 보내준 정보인데, 기존 경로보다 Cost가 크다면 의미가 없으므로, Cost가 작아 기존보다 더 Metrix이 작은 새로운 Shortest Path일 경우에만 테이블에 새로 추가하고 기존 정보를 삭제한다.(=교체) - Hop Count가 테이블에 있는 것보다 같거나 크다면 아무 동작을 하지 않는다.
- 2번부터 7번까지의 과정을 반복한다.
//pseudo flow
if(Receive RIP_Message){
RIP_INFO += 1
//라우팅 테이블에 Destination 정보가 없다면
if( DESTINATION not in Routing_Table ){
//테이블에 새로운 정보 추가
INSERT INTO Routing_Table VALUES RIP_INFO;
}
//Destination 정보가 있을 때, NEXTHOP 필드가 같다면
else if (NEXTHOP == Routing_Table_Entry_NEXTHOP){
//기존 정보 교체
UPDATE Routing_Table SET 기존 Routing_Table_Entry = RIP_INFO;
}
//NEXTHOP 필드까지 다르고, Hop Count가 기존보다 작다면
else if (HOPCOUNT < Routing_Table_Entry_HOPCOUNT) {
//기존 정보를 삭제하고 새로운 정보 추가(교체)
UPDATE Routing_Table SET 기존 Routing_Table_Entry = RIP_INFO;
}
//Hop Count가 같거나 크다면
else (
//기존 정보가 더 우열하므로 아무 동작을 하지 않는다.
Do nothing;
}
}
그림으로 살펴보자.
기존 테이블이 있을 때, C로부터의 RIP 메시지가 들어왔다면 우선 1을 모두 값에 더해준다. 그리고 하나하나 시행에 들어간다.
- Destination이 기존에 없었던 Net3는 바로 추가한다.
- Net2는 Next Hop이 기존과 같으므로(C로부터 들어왔으므로 Next Hop은 C) 교체시킨다. C에서 들어온 새로운 정보이기 때문에 리뉴얼해준다.
- Net6,8,9는 Next Hop이 다르다. 이 중 Hop Count값이 기존보다 작은 Net6만 새로운 정보로 교체해준다.
 |  |
|---|
초기에 RIP가 진행되면 테이블 상태가 완성된다.
RIP의 단점
Slow convergence
라우터들이 인접 라우터들에게 주기적으로 일정한 시간 간격을 두고 자신이 가진 라우팅 테이블 엔트리를 전달하는 것이 RIP인데, 라우터 간 거리가 멀어질 수록 정보가 도착하는 시간이 너무 오래 걸리게 된다. 예를 들어, 주기적으로 정보를 보내는 시간이 보통은 30초이니까 평균적으로 한 네트워크 간에는 변화를 알아차리는 시간은 15초가 된다.
<변화가 생기자마자 메시지를 보내는 타이밍이라 RIP 메시지를 보내는 경우>
- 0.00001초
<RIP 메시지를 보내자마자 변화가 생기는 경우>
- 29.999999초
이러한 이유로 평균적으로는 변화를 인지하는 시간은 15초 정도 걸린다.
이러한 이유로 인해 RIP에서는 Hot Count를 최대 15로 제한을 두었다. 그래서 RIP에서의 Hop Count는 16보다 작아야 하므로, RIP에서 무한대는 16으로 표현한다.
Instability
다음은 A 라우터에서 Net1이 끊어지는 경우에 발생할 수 있는 문제점이다.
원래는 A 라우터에서 Net1이 끊어지면 A 라우터는 Net1의 Hop Count를 16, 즉 무한대로 설정한다. 이때, 인접 라우터인 B 라우터도 이 정보를 알아차려야 한다.
그러나, 이 상황에서 B라우터가 Net1으로 접근하지 못한다는 정보를 전달하는 A -> B 방향으로의 RIP 메시지보다 B -> A 방향으로의 RIP 메시지가 먼저 A 라우터에게 도착한다면, A 라우터는 B로부터 들어온 RIP 메시지를 받아 기존 정보를 교체하게 되는 문제가 발생한다.
B 라우터는 A 라우터에게 받은, A를 거쳐 Net 1로 가는 RIP 정보를 A 라우터에게 보내준 것인데, 원래라면 Hop Count 값이 커서 무시되었을 정보가 이제는 A가 가진 Net 1에 대한 Hop Count가 16이므로 B가 보낸 정보로 A 라우터의 정보가 교체되고 만다.
A 라우터는 자신이 Net1으로 향하는 유일한 라우터임을 모른 채, B로 보내면 Net 1로 보낼 수 있겠구나! 라고 생각하고 Routing Table 정보를 교체하는 것이다. 그 정보는 A 라우터가 Net 1과 연결이 끊기기 전에 생성된 정보를 사용해서 얻어진 결과값일 뿐인데도 말이다!
이렇게 된다면, A 라우터와 B 라우터 사이에는 루프가 발생하여 RIP 메시지를 서로 주고받을 수록 계속 Hop Count값만 올라가게 되고, 둘 모두에서 Hop Count가 16이 될 때까지 이 시행은 반복되게 된다.
이 Instability를 해결하기 위한 방법으로는 크게 3가지가 있다.
1. Triggered update
첫 번째 방법은 테이블에 변화가 생기자마자 바로 RIP 메시지를 보내는 것이다.
이렇게 되면 A->B 방향의 RIP 메시지가 먼저 전달되기 때문에 루프가 발생하지 않는다.
2. Split horizons
두 번째 방법은 정보를 알게된 쪽으로는 다시 RIP를 보내지 않는 것이다.
A 라우터 기준으로는 Net1에서 A 라우터로 끊어짐을 알게 됐으니 A -> B 방향으로만 Net1과 관련된 RIP를 보내고, 반대로 B 라우터는 Net1에 대한 정보는 A 라우터에서 알려주기 때문에 Net1과 관련된 RIP 메시지는 A로 보내지 않는다. 이렇게 되면 루프가 생기는 것을 방지할 수 있다.
3. Poison reverse
마지막 방법은 같은 방향으로 보낼 때 16으로 설정하여 보낼 수도 있다. 즉, 방향이 같은 쪽으로 보낼 때는 Cost를 무한대로 넘겨주기 때문에 이 값은 반영되지 않을 것이다.
