Router architecture

위 사진은 대략적인 라우터의 구조를 나타낸 것이다.

routing processor가 존재하고, link와 router를 연결해 주는 input port와 output port가 존재한다. 그 내부에는 high-speed switching fabric을 통과하여 패킷을 이동시킨다.

Input Port functions

• line termination : 라우터로 들어오는 물리적 링크를 종료하는 물리적 계층 기능
• link layer protocol : 들어오는 링크의 다른 쪽에서 데이터 링크 계층 기능과 상호 운용하는 데 필요한 데이터 링크 계층 기능
• lookup, forwarding : 헤더를 확인하고 output port를 forwarding table(routing table)에서 찾는다. 그리고 datagram이 처리되는 속도보다 들어오는 속도가 빠를 경우 queue를 사용하여 대기시킨다. 그리고 이렇게 forwarding하는 방법에는 두 가지가 존재한다.
  * destination IP adderess만을 보고 forwarding 하는 destination-based forwarding
  • SDN의 등장고 함께 destination IP address 뿐만 아니라 네트워크의 혼잡 상태 등 여러 가지를 고려하여 forwarding 하는 generalized forwarding

Destination-based forwarding

router는 router table을 보고 datagram의 헤더에 명시되어 있는 도착 IP 주소를 확인하고 어느 link로 이 datagram을 내보내야 할지 결정한다.

router table(forwarding table)은 목적지 주소의 구간과 output link가 짝지어져 있다.
위로 따지면 11001000 00010111 00010000 00000100 에서 11001000 00010111 00010000 00000111까지는 3번 link로 가야한다.

Longest prefix matching

Longest prefix matching이라는 말은 일치하는 주소가 여러 개가 있다면, 이 중에서 가장 길게 일치하는 쪽을 선택한다는 의미이다.

예를 들어서, 1100100 00010111 00011000 11100011이라는 주소가 들어온다고 가정해보자. 1번 링크, 2번 링크 모두 매칭된다. 하지만 1번 링크가 더 길기에 선택될 수 있는 것이다.

Switching fabrics

Switching fabrics : input link로 들어온 패킷을 적절한 output link로 출력해 주는 과정

Forwarding을 할 때 하는 중간 구조이고, 라우터에서 가장 중요한 부분이다.

패킷이 input link로 들어와서 output link로 출력되는 rate를 switching rate라고 하며 라우터의 성능의 척도가 된다.

Memory 구조

1세대 라우터가 이 구조를 지니고 있다. 각 입력 포트로 들어오는 모든 패킷들은 메모리로 복사되었다가 선택된 출력 포트로 내보내어진다.

즉, 입력 포트에서 메모리, 그리고 메모리에서 출력 포트로 총 2번 메모리 접근이 발생하게 되며, 따라서 메모리의 대역폭(Bandwidth)에 따라 속도가 좌우된다.

하지만 보편적으로는 메모리에 접근하는데에 상당한 시간이 걸리고, 따라서 고속화하는 데에는 한계가 있는 구조다.

Bus 구조

입력 포트로 들어온 패킷이 출력 포트로 나가는데 공유 버스 회선을 사용하는 구조이다.

하나의 회선이 모든 패킷을 공유하기 때문에, 이 버스 회선의 대역폭만큼으로 성능이 제한되고, 한 회선 안에 많은 패킷이 존재하면 서로 충돌할 우려가 있기 때문에 한 사이클 당 하나의 패킷만 처리할 수 있다는 단점이 존재한다.

interconnection network 구조

crossbar(크로스바) 형태라고도 하며, 여러 개의 노선들이 서로 교차로 처럼 얽혀 있다.

교차점에서 신호에 따라 다른 길을 가도록 설계할 수 있으며, 이러한 신호들의 조합을 통해 경로를 설정한다. 한 출력 포트로 갈 수 있는 경로가 여러 개이기 때문에 여러 개의 패킷이 빠르게 이동할 수 있다는 장점이 있다.

하지만 입출력 포트가 많아지면 이렇나 교차점들이 매우 많아지게 되는 문제점이 존재한다.
-> 그래서 대안이 multi-stage switch

multi-stage switch

위와 같은 fabric plane을 여러 개의 병렬로 구성할 수도 있다.

위 그림은 Cisco에서 개발한 CRS 라우터의 내부 모습이며 3-stage interconnection network plane 8개가 병렬 형태로 구성되어 있다.

Input port queueing

switch fabric이 패킷을 처리하는 정도보다 입력 포트들로부터 패킷이 들어오는 정도가 빠르면 queuing delay가 발생한다. 이럴 때는 버퍼링을 어떻게 관리할 것인지에 대한 buffering management policy가 필요하다.

큐의 맨 앞에 있는 패킷 때문에 큐의 뒤에 있는 패킷이 처리되지 못하고 대기하는 상황을 HOL(Head of Line) blocking 이라고 한다.

만약에 버퍼에 더 이상 공간이 없다면 이전에 다뤘듯 패킷은 loss 될 수 있다.
어떤 패킷이 drop 될 것인지에 대한 정책, drop policy가 존재해야 한다.

Buffer management

• Drop
  버퍼가 꽉 차있는 상황에서, 새로운 패킷이 들어왔을 때 어떤 패킷은 drop 되어야 한다. 어떤 패킷이 drop 될 것인지는 두 가지 정책이 존재한다.

• tail drop
  * 큐의 꼬리 부분, 즉 새로 들어오려는 패킷을 들여보내는 것이 아니라 drop 하는 정책
• priority
  * 각 패킷들에 우선 순위(Priority) 개념을 부여해서 우선 순위가 낮은 패킷을 내보내는 정책
  

Packet Scheduling

FCFS

FIFO(First In, Fisrt Out)과 동일하다. 들어오는 순서대로 처리하는 것이다.

Priority

여러 개의 큐가 있다고 가정하면, 각 큐에 우선순위를 부여하여 우선순위가 높은 큐에 속해 있는 패킷을 우선적으로 처리하는 정책이다.

빨간 큐가 초록색 큐보다 우선순위가 더 높은 큐라고 가정했을 때 빨간색 큐에 존재하는 패킷이 먼저 처리될 때까지 초록색 큐는 처리되지 않는다.

만약 빨간 큐가 비어지지 않아서 초록색 큐에 존재하는 패킷들이 처리되지 못하며, 이러한 현상을 '기아 현상'이라고 한다.

Round-Robin

적절한 기준에 따라 큐를 여러 큐에 나누어서 분배를 하고, 일정 시간 단위를 두고 큐를 번갈아 가면서 처리한다.

모든 큐에 동일한 기준을 적용하기 떄문에 공평한 방식이다.

우리는 패킷 단위로 패킷을 처리해야 하낟. 시간 단위로 큐 사용시간을 할당한다고 하면 어떤 패킷은 전송 중간에 끊겨버리게 된다.

하지만 패킷의 크기는 또 제각기 다르다. 즉, 패킷 단위로 큐의 순서를 돌린다는 것은 생각보다 구현 과정이 까다로울 수 있다.

만약 큐 간에 우선순위가 있다면, 모든 큐가 평등하게 분배받는 것은 비효율적일 수 있다. 따라서 큐 간에 가중치를 부여하는 round robin 방식도 존재한다.

weighted fair queueing

각 큐에 우선순위 가중치를 할당하고, 그 큐의 가중치만큼 큐 사용시간 분배에 차등을 두는 방식이다. weighted fair queueing(WFQ) 방식은 round-robin 방식을 일반화한 방식이다.

round-robin은 각 큐 간의 우선순위가 없어 가중치가 동일한 사례라고 생각할 수 있으므로 WFQ 방식이 보다 일반화된 방식이라고 할 수 있다.

빨강, 초록, 파랑 큐의 가중치가 각각 w1, w2, w3이라고 했을 때 빨강 큐의 가중치는 w1/(w1+w2+w3) 이다.