[Network] 네트워크 계층 : 라우터(Router)

라우터 내부에는 무엇이 있을까?

 

 

• 입력 포트 : 입력 포트의 맨 왼쪽 상자와 출력 포트의 맨 오른쪽 상자로서, 라우터로 들어오는 입력 링크의 물리 계층 기능을 수행한다.
  • 가장 중요한 검색기능은 입력 포트의 가장 오른쪽 상자에서 수행한다. 여기서 포워딩 테이블을 참조하여 도착된 패킷이, 스위칭 구조를 통해 전달되는 라우터 출력 포트를 결정한다. '포트'라는 의미는 물리적인 입출력 라우터 인터페이스(전선)를 의미한다. 애플리케이션과 트랜스포트 계층 사이에서의 소켓과 관련된 포트와는 완전히 다른 의미이다. 
• 스위치 구조 : 라우터의 입력 포트와 출력 포트를 연결한다.
• 출력 포트 : 스위칭 구조로부터 수신한 패킷을 저장하고 필요한 링크 계층(헤더 확인) 및 물리적 계층 기능(패킷 전송)을 수행해서 출력 링크로 패킷을 전송한다. 링크가 양방향인 경우, 출력 포트는 일반적으로 동일한 링크의 입력포트와 한 쌍을 이룬다.
• 라우팅 프로세서 : 제어 평면 기능(소프트웨어)을 수행한다. 예전의 라우터에서는 라우팅 프로토콜을 실행하고 라우팅 테이블과 라우터의 포워딩 테이블을 계산한다. SDN라우터에서 라우팅 프로세서는 원격 컨트롤러와 통신하여 포워딩 테이블을 수신한다.

 

라우터의 입력 포트, 출력 포트, 스위칭 구조는 거의 항상 하드웨어로 구현된다.

하드웨어 구현이 필요한 이유는 무엇일까?

N개의 포트에서 데이터그램이 들어오면 데이터그램 처리 파이프라인(패킷 이동)은 한 번에 1개의 패킷만을 처리할 수 있지만, 라우팅 프로세서는 N개의 패킷을 동시에 처리할 수 있다.

따라서 데이터그램 처리 파이프라인은 소프트웨어에 비해서 최소 N배 더 빠르게 동작할 필요가 있다.

 

---

라우터의 패킷 전달

 

라우터의 패킷 전달 방식에는 2가지가 있다.

바로

1. 목적지 기반 전달과

2. 일반적인 전달이다.

 

라우터 = 회전교차로, 패킷 = 자동차 라고 생각해보자. 

• 목적지 기반 전달 : 입구에 있는 승무원이 최종 목적지를 검색하고 최종 목적지로 연결되는 회전 교차로 출구를 결정한 후 자동차 운전자에게 어떤 원형 교차로 출구가 있는지 알려준다.
• 일반적인 전달 : 특정 도시, 자동차의 제조사, 연도 등 임의의 많은 요인이 출구를 선택하는데 관여할 수 있다.

 

목적지 기반 전달

입력 포트로 패킷이 들어오고 패킷은 스위치 구조 전에 멈춰서 포워딩 테이블을 참고해 올바른 출력 링크로 포워딩 된다. 예를 들어 32비트 IP 주소의 경우, 모든 IP 주소에 대해서 포워딩 테이블을 구성하면 42억개 가량의 행이 생기는데 이는 불가능하다. 이 문제를 처리하기 위한 간단한 예를 알아보겠다. 바로 IP의 접두사를 사용하는 방법이다.

 

 

이러한 형식의 포워딩 테이블에서 라우터는 패킷의 목적지 IP 주소의 접두사를 테이블의 엔트리와 대응시킨다. 대응하는 엔트리가 존재하면 라우터는 패킷을 올바른 링크로 보낸다. 만약 대응하는 엔트리가 없다면 최장 프리픽스 매칭 규칙(longest prefix matching rule)을 적용한다. 즉, 테이블에서 가장 긴 대응 엔트리를 찾고, 여기에 연관된 링크 인터페이스로 패킷을 보낸다. 이러한 방법 덕분에 포워딩 테이블의 크기를 대폭 줄일 수 있다.

 

 

패킷 전달 기본 개념

패킷은 match 및 action이라는 대표적인 개념을 갖는다.

목적지 IP 주소를 찾는 과정 = match

패킷을 스위칭 구조를 통해 지정된 출력 포트로 보내는 것 = action

---

스위치

패킷을 올바른 출력 포트로 이동시키기 위한 방법이 여러 개 존재한다.

 

• 메모리를 통한 교환
  1. 패킷이 도착하면 입력 포트는 라우팅 프로세서(제어 평면)에게 인터럽트를 보내 패킷을 프로세서 메모리에 복사하도록 한다.
  2. 헤더에서 목적지 IP 주소를 추출하고 포워딩 테이블에서 적절한 출력 포트를 찾은 다음 패킷을 출력 포트의 버퍼에 복사한다.
  3. 위 과정에서 메모리 대역폭이 B/sec 인 패킷을 메모리에 쓰거나 메모리에서 읽을 수 있는 경우 전체 전달 처리량은 B/2보다 작아야 한다. -> 출력 버퍼로 패킷이 복사되기 때문이다.
  4. ** 목적지 포트가 다른 경우라도 공유 시스템 버스를 통해 한 번에 하나의 메모리 읽기/쓰기 작업을 하기 때문에 두 패킷을 동시에 전달할 수 없다. **
• 버스를 통한 교환
  1. 입력 포트는 라우팅 프로세서의 개입 없이 공유 버스를 통해 직접 출력 포트로 패킷을 전송한다.
  2. 모든 출력 포트에 패킷이 수신되지만 라벨과 일치하는 포트만 패킷을 유지한다.
  3. 라벨은 스위치 내에서 버스를 통과하기 위해서만 사용되므로 출력 포트에서 제거된다.
  4. 한 번에 하나의 패킷만 버스를 통과할 수 있기 때문에 나머지 패킷은 대기해야 한다. -> 버스의 속도에 영향을 크게 받는다.
• 크로스바 스위치를 통한 교환 : 패킷 병렬 전달 가능
  1. 크로스바 스위치는 출력 포트로 전달되는 패킷을 다른 패킷이 현재 해당되는 출력 포트로 전달되지 않는 한 해당 출력 포트에 도달하는 것을 차단하지 않는다.
  2. 하지만 두 개의 서로 다른 입력 포트에서 나오는 두 개의 패킷이 동일한 출력 포트로 보내지는 경우 한번에 하나의 패킷만 전송될 수 있기 때문에 하나는 대기해야한다.

 

논 블록킹 스위칭 전략 : 입력 포트와 출력 포트가 병렬로 작동하는 N개의 스위칭 구조에 연결된다. 입력 포트는 패킷을 K개의 작은 청크로 분해하고 이 청크들은 N개의 링크로 나뉘어서 원하는 출력 포트로 보내진다. 출력 포트는 K개의 청크를 다시 조합한다.

---

큐잉

입력 큐잉

 

왼쪽 상단 큐의 첫 번째 패킷과 왼쪽 하단 큐의 첫 번째 패킷의 목적지가 같다. 그래서 왼쪽 하단의 첫 번째 패킷은 큐잉 지연을 겪게 된다. 왼쪽 하단의 두 번째 패킷은 목적지가 다르지만 자신보다 앞에 있는 패킷 때문에 대기해야한다.

위와 같은 상황을 HOL(Head-Of-the-Line) 차단이라고 한다.

 

---

출력 큐잉

스위치의 속도가 패킷을 입력받는 속도보다 훨씬 빠를 때에도 출력 포트에서 큐잉이 발생할 수 있다.

만약 N개의 입력 포트 각각에 도착하는 모든 패킷이 동일한 출력포트로 향한다면?

이 경우, 출력 링크가 단일 패킷을 전송하는 시간에 특정 출력 포트의 큐에는 N개의 데이터가 쌓일 것이다. 결국 대기 중인 패킷의 수가 너무 많아져 메모리를 초과하게 될 것이다. 

 

 

  들어오는 패킷을 저장할 메모리가 충분하지 않을 때 패킷을 폐기할 수 있다. 이미 대기중인 패킷을 폐기하거나 / 새로 도착한 패킷을 폐기하는 정책(Drop-tail)을 사용한다. 

최근 AQM(Active Queue Management) 알고리즘으로 알려진 많은 패킷 폐기와 패킷 마킹 정책들이 나오는 중이다. 그 중에서 RED(Random Early Dectection) 알고리즘이 가장 폭넓게 연구되었다.

 

RED 는 큐의 크기가 미리 정해 놓은 임계치를 넘게 되면 이후에 들어오는 패킷을 확률적으로 폐기함으로써, 큐의 크기가 차오르는 것을 미리 제어하는 방식이다. 그러나 RED 는 고정된 파라미터를 이용하기 때문에 네트워크 상황에 능동적으로 대처 할 수 없어, 네트워크의 성능이 파라미터 설정에 좌우되는 단점이 있다

---

스케줄링

FIFO (First In First Out) : Stack

패킷이 큐에 도착한 순서대로 큐를 통과하는 방식이다.

 

 

PQ (Priority Queue)

각각의 큐는 여러개의 클래스로 구분된다. 클래스마다 우선순위가 다르며 우선순위가 높은 클래스의 큐에서 패킷이 먼저 빠져나간다. 예를 들어 VoIP패킷은 SMTP, IMAP 전자 메일 패킷과 같은 트래픽보다 우선순위를 받을 수 있다.

위 그림에서는 2번 패킷이 4번 패킷보다 우선순위가 낮지만 이미 2번 패킷이 전송 중이기 때문에 2번을 먼저 서비스하는 것을 볼 수 있다. 이를 비 선점형 우선순위 큐 라고 한다.

만약 우선순위 큐가 현재 서비스 중인 상황을 고려하지 않고 우선순위가 높은 패킷이 들어왔을 때 현재 패킷의 전송을 취소한다면 이를 선점형 우선순위 큐 라고 한다.

 

PQ의 문제점으로는 Starvation(기아) 현상이 발생할 수 있다는 것이다. 낮은 우선순위 큐에 패킷이 많이 들어있지만, 계속해서 높은 우선순위를 가진 패킷이 들어올 경우 낮은 우선순위의 패킷에게는 절대 자신의 차례가 오지 않을 것이다. 이를 Starvation이라고 한다.

 

Round robin

우선순위 큐와 같이 클래스로 구분된다. 하지만 클래스 간에 우선순위가 존재하지 않으며 공평하게 클래스를 돌면서 패킷을 전송한다. 작업 보존 큐잉 규칙을 가지고 있기 때문에 비어있는 클래스에 접근하면 바로 다음 클래스로 넘어간다.

 

WFQ(Weighted Fair Queuing)

라운드 로빈 방식과 동일하다. 하지만 각 클래스마다 다른 양의 서비스 시간을 부여받는다는 점에서 차이가 있다.

각 클래스 i는 가중치 wi를 받게 된다. 클래스 i는 wi/(wj의 총 합) 의 서비스 시간을 보장받는다.