[컴퓨터 네트워크] 26. Network Layer (2) : 라우터

라우터

이번 글에서는 라우터의 동작에 대해 정리해보려고 한다.

라우터는 일종의 컴퓨터이다.

라우터에도 OS가 들어가고, 여러 보드가 들어가있다.

 

라우터의 아키텍처는 위와 같이 되어있다.

라인카드로 된 인풋 포트와 아웃풋 포트가 앞단에서 패킷을 받거나 보내고, 라우터는 여러 네트워크와 연결이 되어있으므로 그 중간에 인터페이스가 필요한데, 인터페이스 자체가 컴퓨터이면서 그 안에 여러 컴퓨팅 보드가 존재하는 것이다.

이때 지금 그림에서는 왼쪽에서 오른쪽 방향으로 표현하여 input port, output port 를 구분했지만, 이는 방향에 따라 구분되는 것이지 실제로 각 라인카드가 input port, output port 의 역할을 정적으로 수행하는 것은 아니다.

방향만 반대로 바꾸면 얼마든지 서로의 역할이 바뀔 수 있다.

 

인터페이스에는 프로세서(컴퓨터의 CPU에 해당, control plane에서 다룰 라우팅 알고리즘을 실행)가 존재하며, 프로세서는 switching fabric 이라는 그 자체로 네트워크인 장치와 통신한다. (여러 라인카드가 switching fabric 이라는 내부 네트워크라고 생각하면 된다.)

네트워크 인풋 포트와 아웃풋 포트를 연결시켜주는 네트워크가 존재한다고 보면 된다.

 

그 내부 내트워크는 간단하게 싱글 버스로 연결되어있을 수도 있고, 아주 복잡한 inter-connection 네트워크로 연결되어 있을 수도 있다.

 

라우팅 프로세서는 라우팅 알고리즘을 통해 생성한 자료 구조 테이블을 각각의 라인 카드에 집어 넣는다.

그러면 라인카드는 자신이 수신한 패킷을 목적지로 전송하기 위해 어떤 아웃풋 링크로 보낼지 결정한다.

라인카드도 각각의 프로세서를 갖고 있어서 포워딩을 담당한다.

위 그림에서는 점선 아랫부분을 얼마나 빠르게 만드느냐에 따라 라우터의 성능이 결정된다.

보통 나노 세컨드 스케일로 패킷 포워딩이 진행되고, 라우팅 알고리즘으로 테이블을 만드는 과정은 밀리 세컨드 단위로 진행된다.

 

Input Port

 

input port는 위와 같이 생겼다.

먼저 line termination 은 physical layer이다. 1계층인 물리 계층이 이곳에 먼저 존재한다.

그 다음에는 link layer protocol이 나와서 2계층인 데이터 링크 계층이 존재한다.

이 부분이 수신자 역할을 수행해서 패킷을 받아들인다. 대표적인 것이 이더넷이다.

파란색 부분은 인터넷 프레임의 주소 (2계층 주소)를 보고 이 라우터에 온 것이 맞는지 확인해서 맞으면 헤더를 제외한 자신의 데이터부분 (패킷)을 빨간색으로 넘겨준다.

 

그리고 빨간색 부분이 3계층으로서, IP패킷의 헤더를 보고 목적지를 결정해서 포워딩한다.

이때 목적지 (라우터 기준으로 나갈 output port) 는 라우팅 알고리즘을 통해 만들어진 포워딩 테이블을 보고 결정한다.

이 위치에서 일어나는 일을 decentralized switching 이라고 하는데, 테이블을 분산 알고리즘에 기반해서 만들기 때문이다.

그리고 포워딩하는 속도에 비해 패킷이 들어오는 속도가 빠른 경우, 패킷들이 큐에 쌓이게 된다.

 

3계층의 목표는 line speed (녹색, 파란색으로 패킷이 들어오는 속도)에 맞춰서 패킷을 처리하여 큐잉이 없도록 하는 것이다. 물론 현실적으로 그렇게 빠르게 처리할 수도 없고, switching fabric 특성에 따라서 만약 같은 output link로 나가는 패킷이 여러개 들어왔다면 큐잉이 될 수 밖에 없기도 하다. 따라서 극단적으로 패킷이 쌓이는 경우에는 패킷이 버려질 수도 있다.

 

3계층에서 포워딩을 하는 방법은 '목적지 기반'의 포워딩이다. (destination-based)

즉, 목적지의 IP주소만 이용해서 포워딩한다.

이 방법은 가장 기본적인 (traditional) 방법이기도 하면서, 동시에 가장 널리 쓰이고 있는 방식이다.

 

이보다 좀 더 일반화된 방법을 'generalized forwarding' 이라고 한다.

목적지 주소 뿐만 아니라 다른 주소도 같이 참조해서 처리하는 방법이다.

 

Destination-based Forwarding

 

먼저 가징 널리 쓰이고있는 목적지 기반 포워딩을 먼저 보자.

라인 카드마다 이렇게 포워딩 테이블이 주어져있다.

포워딩 테이블을 보면 목적지 주소의 범위가 key로 주어졌을 때, 그 범위에 해당하는 IP 주소가 오면 어떤 output port 로 나가야 할 지 인터페이스 번호가 value로 주어져있다.

 

그런데 이렇게 목적지 주소를 비교할 때, 여러 그룹에 동시에 해당하는 ( matching 되는 ) 경우가 있다.

이때는 매칭되는 그룹 중 하나를 선택해야 하는데, 이때 longest prefix match 방법을 사용하여 매칭한다.

이름 그대로 IP주소를 앞에서부터 쭉 살펴봤을 때, 가장 길게 매칭되는 key에 해당하는 link로 보낸다.

 

뒤에서 정리하겠지만 IP주소는 크게 subnet 부분과 host 부분으로 나누어진다.

특정 작은 규모의 네트워크 내에서 같은 네트워크에 속하는 컴퓨터(머신)은 모두 같은 subnet을 갖고, host 부분만 다른 값을 갖는다.

 

이때 prefix는 subnet 부분을 말하는데, subnet의 일부만 해당해도 prefix, 모두 해당해도 prefix 이다.

 

위 예시를 살펴보자.

첫번째 IP 주소는 첫번째 범위에만 해당된다. 따라서 link interface 0번으로 나가게 될 것이다.

두번째 IP 주소는 두번째와 세번째 범위에 모두 해당된다. 하지만 제일 길게 매칭되는 것은 2번째 범위이다.

따라서 Link Interface 1번으로 나갈 것이다.

 

그렇다면 왜 Longest Prefix Matching을 사용할까?

이유는 더 길게 매칭되는 곳이 목적지 컴퓨터에 더 가까운 네트워크라고 추론할 수 있기 때문이다.

그래서 라우터마다 Longest Prefix Matching 알고리즘이 구현되어있고, 이 속도가 라우터의 속도를 결정하기 때문에 라우터 회사들이 이 알고리즘 개선에 돈을 많이 투자한다.

 

그래서 라우터에서 사용하는 메모리는 '주소'를 이용해서 접근하는 일반적인 메모리와 다르게 content addressable memory를 쓴다. (ternary content addressable memories, TCAMs)

여기에서 tenary는 binary 에서 와일드카드 하나가 추가된 것으로 2개 후보군(0, 1)에서 비교하는게 아니라 3개 후보군(0, 1, *) 에서 비교하는 것이다.

 

라우터에 들어오는 패킷이 있을 때, 이 패킷의 목적지 IP주소와 매칭되는 테이블 entry는 실제로 매우 많을 것이다.

이를 일일히 비교하려면 시간이 너무 오래 걸리기 때문에, 목적지 IP주소와 n개 entry를 한꺼번에 비교하는 방식을 사용한다. (하나하나 비교하는 O(n) 도, 심지어 소팅해서 이분탐색으로 찾는 O(log n)도 시간이 너무 많이 걸린다고 한다.)

이 메모리를 사용하면 테이블 크기에 상관없이 1클럭 사이클에 매칭된 주소를 찾을 수 있다.

이 메모리는 만드는데 비용이 많이 들고, 전력 소모도 심하다는 단점이 있다.

 

Switching Fabrics

switching fabric은 위 그림에서 보는 것처럼 input, output port 사이에 존재하는 고성능, 고속 네트워크이다.

가운데에 네트워크가 들어가는 이유는 input port에 들어온 패킷을 output port로 빠르게 내보내줘야 하기 때문이다.

그래서 이 부분의 이름을 switching fabric 이라고 부른다.

 

라우터도 이렇게 스위칭 역할을 하기 때문에 스위치의 일종이다.

라우터의 성능은 이 스위칭을 얼마나 빠르게 할 수 있는지를 가지고 성능 이야기를 한다.

input port 로 들어온 패킷이 output port로 얼마나 빠르게 전달될 수 있는지 비율을 switching rate 라고 하며, 라우터의 성능을 보는 척도가 된다.

 

switching rate는 input, output rate 의 정수 비율로 평가한다.

만약 input 에 n개 링크가 있고, n개 링크를 통해 각각 들어오는 비율을 r 이라고 하면,

n * r 만큼을 단위 시간당 처리할 수 있다고 해보자. (가장 바람직한 상황)

 

 

switching fabric을 실제 구현하는 방법은 크게 그림과 같이 3가지가 있다.

제일 오른쪽에 있는 interconnection network 방식은 고가의 라우터에서 주로 사용된다.

Bus

버스는 시스템 버스을 말하며 CPU에서 마더보드와 도터보드가 있을 때, 마더보드를 통해서 주변 장치들끼리 서로 통신하는 모양과 같다.

패킷이 input port 메모리에서 output port 메모리로 shared bus를 통해 전송되는 모습이다.

이 방식은 bus arbitration 문제가 생길 수 있다. 버스를 잡아야 하기 때문이다.

또 bus contention이 발생했을 때 어떻게 각 디바이스들이 공평하게 버스를 사용하도록 할 건지 고민해야하는 문제가 있을 수 있다. 스위칭 속도가 이 bus bandwidth에 제한되는 영향도 있다.

 

버스를 사용하는 라우터는 엑세스 네트워크 급이면 사용할 수 있겠지만, 네트워크 코어에서는 사용할 수 없다.

Memory

 

메모리의 경우, input 패킷을 받아서 copy한다음 메모리에 넣고, 메모리에 저장된 패킷을 그대로 다시 output에서 읽어가는 방식이다. 하지만 이 방식은 성능이 거의 나오지 않아서 비용이 저렴함에도 불구하고 잘 사용하지 않는다.

과거에 사용하던 방식이고 요즘은 거의 사용하지 않는다. (매우 제한된 상황에서 사용)

 

인풋 포트로 들어온 패킷을 카피해서 메모리에 저장하고, 메모리에 저장된 내용을 다시 카피해서 아웃풋 포트로 내보낸다.

메모리 카피는 오버헤드가 크기 때문에 성능이 잘 나오기도 어렵고, 이 버스도 위에서 말한 시스템 버스와 관련된 문제가 발생하기 때문에 고사양 라우터를 만드는데는 적절하지 않다.

 

Interconnection Network

 

switching fabric에 네트워크 자체가 들어가는 경우다.

이 이론은 멀티 프로세서 (여러 프로세서를 이용해서 어떤 일을 병렬 처리하는 것) 연구를 했을 때 나온 개념을 그대로 사용한 것이다.

다양한 종류의 inter connection network가 적용될 수 있으며 여러가지 아이디어도 등장했다.

가령, IP 패킷을 cell 이라는 더 작은 단위로 쪼개서 병렬적으로 전송한 뒤, 목적지에서 다시 하나로 합치는 기법과 같은 아이디어가 등장했다.

이게 multistage swtich의 아이디어이다.

 

패킷을 쪼개서 여러 중간 통로로 보낸 뒤, 마지막에 합치는 것이다.

 

 

거기에 라우터의 성능을 더 높이기 위해 이렇게 swtiching fabric의 평면(plane)을 여러개 쌓는 형태로 구성하기도 한다.

multistage switch 방식을 여러개 겹겹히 쌓아서 한번 더 병렬적으로 처리하는 것이다.

그래서 점점 대역폭이 늘어나는 상황에 맞춰 라우터의 성능을 같이 높이기 위해 이런 다양한 기술들이 들어간다.

 

Input Port Queuing

 

다음과 같은 상황을 생각해보자.

인풋포트로 다양한 패킷들이 들어온 상황이다.

이때 각각의 패킷은 자신의 색에 맞는 output 포트로 나간다고 해보자.

이때 빨간색 패킷이 나갈 수 있는 통로는 1개인데, 가려고하는 패킷은 2개이다.

이때 두 패킷 사이에 우선순위를 결정해주어야 하는데, 우선 위쪽에 있는 빨간색 패킷이 먼저 지나가고, 아래쪽의 빨간색 패킷은 대기해야 한다고 해보자.

 

그러면 한번의 패킷 전송 시간이 흐른 뒤, 위 그림과 같은 상황이 될 것이다.

이때 녹색 패킷은 자신이 만약 먼저 왔더라면 기다리지 않고 바로 녹색 output port 로 나갈 수 있는 상황이었음에도 빨간색 패킷이 막고 있어서 어쩔 수 없이 1번 기다려야 했다.

이렇게 input port 에서도 HOL Blocking 문제가 발생할 수 있다.

이런 문제는 라우터의 성능을 떨어뜨리게 된다.

 

Output Port Queuing

 

대기는 input 뿐만 아니라 output 에서도 나타날 수 있다.

아웃풋 포트는 일종의 센더와 같다. 따라서 프로토콜 스택을 위에서부터 아래로 내려가는 방향을 거쳐 내보내게 된다.

그래서 라우터는 여러 다른 종류의 네트워크를 연결할 수 있다.

A 방식을 사용하는 네트워크에서 B 방식을 사용하는 네트워크로 보낼 때, 그 B 방식에 맞는 프로토콜을 사용하는 방식으로캡슐화해서 내보내면 되기 때문이다.

이를 통해 라우터는 이기종 네트워크를 서로 접합할 수 있다.

 

다시 큐잉으로 돌아와서 다음과 같은 구조로 Output port가 있을 때, 포트를 통해 패킷이 나가는 속도보다, switch fabirc이 보내주는 패킷이 더 많다면 버퍼에는 점점 패킷이 쌓인다.

(예를 들면 공교롭게도 스위치 패브릭이 보내주는 목적지가 모두 이 아웃풋 포트였던 것이다.)

 

그러면 최악의 경우, 패킷을 버려야 할 수도 있다.

그래서 버릴 때는 어떤 패킷을 버릴지 결정하는 기준이 될 drop policy도 필요하다.

보통은 tail drop을 사용하지만, 경우에 따라 급한 패킷이 있다면 그 패킷을 앞에 끼워주고 다른 패킷을 버릴 수도 있다.

 

이렇게 라우터에서도 loss가 발생할 수 있기 때문에, 네트워크에서 중간에 패킷이 유실될 수 있는 것이다.

큐잉은 input port 에서도 물론 발생할 수 있지만, 주로 output port 에서 큐잉과 패킷 로스가 발생한다.

 

Buffer Management

그런데 여기에 더해 output port 에서는 경우에 따라 스케줄링도 발생할 수 있다.

큐잉되어서 자신의 차례를 기다리는 패킷중에 어떤 패킷을 먼저 처리할지 결정해야 하기 때문이다.

만약 우선순위를 구현한다고 하면 이 때 버퍼 관리가 필요해진다.

그래서 버퍼에 쌓인 데이터를 어떻게 처리해서 빼낼 지 결정하는 것을 link layer 에서 한다고 해보자.

 

이때 사용하는 알고리즘을 priority 스케줄링 이라고 한다.

대부분의 라우터는 이런 알고리즘이 존재해도 실제로 구현하지는 않다.

따라서 priority 스케줄링이 가능은 하지만 실제로 사용되진 않는다. (너무 복잡해서 구현하기가 쉽지 않기 때문이다.)

 

 

라우터는 TCP 헤더의 ECN, RED 플래그도사용한다.

TCP에서 혼잡을 경험하면 라우터에서 IP 헤더에 혼잡을 명시적으로 표시해둘 수 있는데, Explicit Congestion Notification 과 Random Early Detection (또는 Discard) 플래그를 표시한다.

RED의 경우, 좀 더 적극적으로 혼잡이 발생할 조짐을 보이면 미리 적절한 방식을 통해서 drop 시키자는 아이디어다.

라우터가 자신의 버퍼가 급격하게 차오르는 것과 같이 혼잡이 발생할 것 같은 조짐을 느끼면, 아직 버퍼 공간이 남아있더라도 랜덤하게 패킷을 버리는 것이다.

 

그러면 기존 sender 입장에서는 뜬금없이 혼잡이 없음에도 패킷 로스를 경험하게 되고, 센더는 좀 더 일찍 혼잡 제어 단계로 들어가게 되어 전송량을 조절하여 사전에 미리 혼잡을 예방할 수 있다.

(물론 이 아이디어도 실제로 자주 사용하지는 않는다. 랜덤하게 버려진 패킷만 손해를 보기 때문에 공평하지 않기 때문이다.)

 

라우터에서 수행하는 패킷 스케줄링은, FCFS, Priority, Round Robin, Weighted Fair Queuing  과 같은 방식이 존재한다.

보통은 FCFS 방식으로 먼저 온 패킷을 처리하는 것이 일반적이지만, 경우에 따라서는 정말 긴급하게 먼저 처리를 해줘야 되는 패킷을 앞에 넣어줄 수도 있다.

 

FCFS는 말 그대로 먼저 들어온 패킷을 먼저 처리하는 알고리즘이다. (FIFO와 같다.)

사실 교수님은 이 이외의 방식을 사용하는 라우터를 본 적이 없다고 하신다.

왜냐하면 이 외의 방식은 어떻게보면 망 중립성을 깨는 방식이기 때문이다.

 

망 중립성은 패킷과 트래픽을 차별하지 않는 것을 말한다.

예를 들어 어떤 서비스의 인기가 너무 많아서 그 서비스의 트래픽이 망에서 높은 비중을 차지한다고 해서 ISP가 그 서비스 제공 회사에 요금을 더 내도록 한다거나, 우선순위를 조정하는 일을 하지 않는 것을 말한다.

컨텐츠 회사 입장에서는 좋은 일이지만 ISP 입장에서는 좋지는 않다. 왜냐하면 그런 컨텐츠 회사 때문에 계속해서 설비에 투자하는 등 망을 개선하는 비용을 투자해야 하기 때문이다.

아무튼 망 중립성이 있기 때문에 이론적으로 트래픽에 우선순위를 두는 것이 가능은 해도 실제로 그걸 ISP에서 구현해두지는 않았다.

 

Priority Scheduling

Priority Scheduling은 (이 망 중립성을 깨고) 패킷에 우선순위를 두어 더 높은 우선순위를 가진 패킷을 먼저 처리하는 것을 말한다.

 

우선 각각 우선순위 별로 큐를 나눠두고, output port 에서 패킷을 받으면 패킷을 분류하여 서로 다른 큐에 넣어둔다.

만약 ISP에서 구현한다면 돈을 더 많이 낸 사용자는 윗쪽 큐에 보관하고, 돈을 덜 낸 사용자는 아래쪽 녹색 큐에 패킷을 큐잉하는 것이다.

 

 

이때 우선순위가 높은 큐에 있는 패킷을 먼저 전송하고, 그 패킷이 전송되는 도중에 우선순위가 낮은 패킷 2번이 도착했다고 해보자.

그런데 1번 패킷의 전송이 끝나기 직전에 우선순위가 높은 큐에 새로운 패킷 3번이 들어왔다.

그러면 이 방식에서는 2번 패킷이 아니라 3번 패킷을 먼저 전송해준다.

그리고 3번 패킷이 전송되는 동안, 새로운 패킷이 없었다면 그때 2번 패킷을 전송한다.

 

2번 패킷이 전송되는 중에 4번 패킷이 높은 우선순위 큐에 들어왔다면 이후에 4번 패킷을 전송하고, 5번 패킷이 나중에 들어오면 (사실 우선순위 상관없이) 처리한다.

 

Round Robin (RR)

라운드 로빈 방식은 턴을 바꿔가면서 (돌려가면서) 각각 번갈아 처리해주는 것을 말한다.

 

그림과 같이 큐가 3가지가 있다고 해보자.

이때 각각 들어오는 패킷을 분류해서 적절하게 큐에 나눠 담고, 데이터를 전송할 때는 각 큐에서 한번씩 번갈아가면서 보내준다. 분류 기준은 헤더 필드에서 어떤 값을 사용하든 상관이 없다.

즉, 각각을 1/3 씩 나눠서 서비스해준다.

만약 차례차례 돌리면서 서비스하다가 현재 보는 큐에 패킷이 없다면 그 차례는 건너뛴다.

 

Weighted Fair Queuing (WFQ)

이 방식은 Round Robin 방식을 조금 더 일반화한 것이다.

각각의 큐를 동등하게 1/3 씩 처리하는게 아니라 원하는 가중치를 설정해서 높은 가중치의 큐는 조금 더 많이 서비스를 하도록 비중을 조절할 수 있게 한다.

 

그래서 각각의 큐에서 서비스를 받는 비중은 아래와 같이 표현할 수 있다.

 

이 방식을 이용하면 최소 bandwidth를 보장해줄 수 있다는 장점이 있다.

만약에 w1 = 2, w2 = 1, w3 = 1 이라면, 한 턴에 w1 에서는 1/2 의 서비스를, w2 에서는 1/4의 서비스를, w3 에서는 1/4 의 서비스를 제공받는다.