[Network] 라우터(Router)

라우터 구조 개요

라우터는 인터넷 상의 Network를 서로 연결해주는 매개체 역할을 한다.

 

Input port function

• line termination = Physical Layer 담당
• link layer protocol = Link Layer 담당
• decentralized switching = 들어온 패킷을 forwarding table을 참조하여 도착된 패킷이 스위칭 구조를 통해 라우터가 어떤 출력 포트로 나갈지를 결정

라우팅 프로토콜 정보를 전달하는 패킷은 Input port에서 “Routing Process”로 전달된다.

 decentralized switching의 forwarding기법에는 2가지 있는데, destination-based forwarding은 전통적인 방식으로 오직 목적지 IP주소만으로 forward를 진행한다. generalized forwarding은 주소 이외에 지정해 놓은 Header value에 따라 forwarding을 진행한다.

 

Switching fabrics

Input port에서 forwarding table을 참조하여 Output port가 결정되면, switching fabric은 이를 실질적으로 연결해주는 역할을 한다.

Switching rate = Packet이 Input port에서 Output port로 전송될 수 있는 속도.

switching fabric에는 3가지 주요 타입이 있는데, memory, bus, interconnection network이다.

 

1. Switching via memory
라우팅 프로세서를 직접 제어하는 전통적인 방식이다. 패킷이 도착하면 입력 포트는 라우팅 프로세서에게 Interrupt를 전송해 패킷을 시스템 메모리에 복사한다. 속도는 메모리의 bandwidth에 의해 제한된다.

초록색 패킷은 input port를 통해 들어갔다가, memory를 거쳐 output port로 나간다.

2. Switching via bus

입력 포트는 라우팅 프로세스의 개입없이 공유 bus를 통해 직접 출력 포트로 패킷을 전송한다. 속도는 bus의 bandwidth에 의해 제한된다.

3. Switching via interconnection network

여러 개의 패킷이 동시에 출력 포트로 전송될 수 있다. memory, bus에서는 하나의 패킷이 switching에서 출력되기 위해 진행 중이면, 다른 패킷은 이 패킷의 전송이 끝날 때까지 기다려야만 했다. 따라서, Bus, memory의 bandwidth를 극복했다 할 수 있다.

만약, switch fabric의 속도가 입력 포트의 속도보다 느려진다면, input queue에 Queuing이 발생한다.

그림에서 보다 싶이, 빨간색 패킷이 동시에 가려하는 상황에서는 한 패킷은 반드시 기다려야한다(=queuing이 필요). 이렇게 되면, 제일 낮은 위치의 입력 포트에서 초록색 패킷은 앞의 queuing되어있는 빨간색 패킷때문에 blocking되게 되는데, 이러한 현상을 HOL(Head-of-the-line) blocking이라 한다. 즉, 앞의 queuing되어있는 datagram이 같은 큐 안에 있는 다른 datagram이 forward하는 것을 방해하는 것이다.

 

Output port queuing

들어오는 속도가 R보다 크기 때문에 발생하는 queuing을 말한다.

queuing시 출력 버퍼의 공간이 충분하지 않으면(full) 패킷을 버린다(drop).

---

Packet Scheduling

어떤 패킷을 다음 링크로 먼저 보낼지 결정하는 것이다. 하나씩 살펴 보자.

 

FCFS(First Come First Served)

패킷이 도착한 순서대로 내보내는 방법으로, 흔히 알고있는 FIFO방식이다.

 

Priority scheduling

classify가 Header의 값을 보고 우선순위에 따라 나눠진 Queue에 패킷을 분류하고, 높은 우선순위 큐의 패킷을 먼저 내보내는 방식이다.

 

하지만, 우선순위를 사용하게 되면 low priority queue에 있는 패킷은 내보내질 기회를 갖지 못하는 Starvation문제가 발생할 수 있다.

 

Round-Robin(RR) Scheduling

Starvation을 예방하는 방법으로 서버가 원형으로 반복적으로 queue를 확인하고 각 큐마다 패킷을 한 개씩 처리하는 방식이다.

 

 

Weighted Fair Queuing(WFQ)

Round-Robin방식에서 가중치를 더한 것으로 각 큐는 가중치를 가지고 있다.