Network Layer - 2. What's inside a router? (1)

1. What's inside a router?

router는 Layer 3 device이다. 라우터의 내부를 살펴보자.

라우터의 내부는 두 plane으로 구분할 수 있다.

control plane에서 routing을 수행한다. (컴퓨터의 processor처럼) 프로세서가 routing software를 실행해서 경로를 찾는다. 소프트웨어 차원에서 구현되기 때문에 ms단위로 상대적으로 오래걸린다.

 

그 아래는 data plane이 있다. 여기서 forwarding을 수행한다. switching fabric이 실제로 패킷을 한쪽에서 다른쪽으로 move하는 작업을 수행한다. 하드웨어 차원에서 구현되어 있어 nano초단위로 굉장히 빠른시간 내에 처리된다. 

 

routing processor가 찾은 경로를 기반으로 forwarding table을 만든다. 이것들이 모든 line cards(port)에게로 복사되어 전달된다. 이를 shadow copy라고 한다.

이렇게 모든 곳에 복사를 해주면 각 input port에서 (locally) 아주 빠르게 forwarding decision을 내릴 수 있다.

패킷이 input port로 들어왔을때 어디로 나가야하는지 processor에게 물어볼 필요가 없기 때문이다.

port속을 자세히 들여다보자.

signal이 line termination으로 들어오면 bit로 변환이 된다. (physical layer)

link layer를 통과한 datagram들을, switch fabric이 header field 값과 forwarding table을 참고해서 output port로 즉시 전달한다.

 

전통적으로 목적지 ip주소만 보고 forwarding하는 방법과 header field의 모든 정보를 살펴보는 (SDN) 방식이 있다.

어쨋거나 forwarding 작업을 line speed(들어오는 속도대로 내보낸다)로 처리하는 것이 목적이다. 

물론 datagram들이 엄청 쏟아져서 switch fabric이 매우 바쁘면 패킷들이 queue에서 대기할수도 있다.

 

input port에서는 lookup, queueing, forwarding 말고도 다양한 일을 처리한다.

packet version확인, checksum으로 오류가 있는지 확인(있으면 바로 버림), ttl 확인, 감소 등

또한 각 Interface마다 몇개의 패킷이 오고 갔는지 몇 바이트들이 오고 갔는지 등을 기록하는 counter가 있다.

 

*참고로 라우터는 라우팅에 특화된 메모리를 사용한다. ternary content addressable memory(TCAMs)

one clock cycle만에 address present/retrieve를 처리한다. (테이블 크기와 무관하게 input으로 주자마자 output이 바로 나오는)

2. Destination based forwarding

목적지 ip 주소에 따라서 forwarding하는 방법의 경우 포워딩 테이블은 위처럼 생겼다.

목적지 ip 주소가 해당 범위 안에 속하면 해당 interface(port)로 나간다.

하지만 각 구간들이 겹치는 부분이 있을 수도 있다. (ex. (1,10)구간과 (8,15)구간이 있을 수 있다.)

그래서 internet에서는 longest prefix matching방식을 사용한다.

이런 목적지 주소를 갖는 datagram은 2번이 아니라 1번으로 나간다. (가장 긴 prefix가 일치하므로)

이 모든 내용은 뒤에서 자세히 배운다. 가장 중요한건 forwarding이 nano초 단위로 하드웨어 차원에서 아주 빠르게 처리된다는 사실이다.

3. Switching fabrics

패킷을 input port에서 output port로 이동시킨다.

패킷을 이동시키는 속도를 switching rate라고 한다.

만약 N개의 input port로 각각 x의 속도로 패킷이 들어온다면 switching fabric의 처리 속도는 Nx가 되는게 가장 ideal하다.

그래야 x로 들어오는 line speed를 그대로 x로 살릴 수 있다.

memory기반으로 만들어진 switching fabric은 패킷이 메모리로 복사되었다가 나갈 때 다시 복사해주기 때문에 매우 느린 고전 방식이다.

bus 기반 switching fabric은 상당히 빠르다 하지만 한번에 한 패킷만 버스를 사용하기 때문에 좀 아쉽다.

가장 최신 router는 crossbar 기반의 switching fabric을 사용한다. bus와 달리 동시에 여러 패킷이 서로 다른 경로를 타고 나갈 수 있다. 위 예시에서는 최대 3개의 패킷이 동시에 나갈 수 있다.

4. Input port queueing

fabric이 처리 속도가 상대적으로 느리면 input port queueing delay,loss가 발생할 수 있다.

red output port로 가야하는 두 패킷이 있을때, 한번에 하나씩 밖에 내보낼 수 없으니 한쪽은 queue에서 대기해야 한다. 

그림 맨 밑에 red packet이 wait하는 동안 그 뒤에 green packet은 목적지가 달라 fabric이 동시에 처리할 수 있음에도 불구하고 queue에서 기다려야 한다.

green packet이 Head-of-the-Line (HOL) blocking 상황이라고 한다.

5. Output ports

output port도 마찬가지로 link speed(transmission rate)보다 빨리 패킷이 쌓일 수 있기 때문에 버퍼가 있다. 물론 queueing delay, loss가 발생할 수 있다.

라우터를 설계할 때 버퍼의 크기를 몇으로 하냐에 따라서 delay, loss를 줄일 수 있다. link capacity, switching fabric의 속도에 따라서 버퍼 크기를 결정한다.  

output port는 한가지 다른 점이 있다. queue에 있는 패킷중에 어떤 원칙(ex. 우선순위 등)에 따라서 먼저 dequeue할 패킷을 고를 수 있다. 이를 scheduling이라고 한다.

가장 일반적인 scheduling 방법은 FIFO(FCFS)가 있다. 들어온 순서대로 나가는 것이다.

priority scheduling : 패킷이 도달할 때 우선순위에 따라 다른 큐에 담긴다. 우선순위가 높은 큐 부터 비워 내려간다. 그림에서는 큐가 2개지만 여러개가 있을 수 있다.

round robin scheduling : red, green queue에서 동등하게 돌아가면서 패킷을 하나씩 보내는 방식이다. 

weighted fair queueing(WFQ) : round robin과 priority를 합친 방식이다. red, green, blue 큐마다 우선순위에 따라 weight를 다르게 주고 가중치 마다 공평하게 돌아가면서 link사용 기회를 준다.

 

* queue가 꽉 찼을 때, 꼭 마지막에 도착한 패킷을 discard(tail drop)할 필요는 없다. 마찬가지로 큐가 찼을때 어느 패킷을 버릴 것이냐 하는 discard policy도 있다. (ex. priority, random, RED etc)