4.2 라우터 내부에는 무엇이 있을까?
위 그림을 라우터의 구조를 나타낸다.
입력 포트- 입력 포트의 맨 왼쪽과 맨 오르쪽 박스는 라우터로 들어오는 입력 링크로, 물리 계층 기능을 수행한다.
- 또한 입력 포트는 들어오는 링크의 반대편에 있는 링크 계층과 상호 운용하기 위해 필요한 링크 계층 기능을 수행한다. 이것은 입력 및 출력 포트에서 미들박스로 표시된다.
- 가장 중요한 기능은 입력 포트의 가장 오른쪽에서 수행되는 검색 기능이다. 여기서 포워딩 테이블을 참조하여 도착된 패킷이 스위치 구조를 통해 라우터 출력 포트를 결정한다.
- 라우팅 프로토콜 정보를 전달하는 패킷인
제어 패킷은 입력 포트에서 라우팅 프로세서로 전달된다. - 여기서의 포트는 앞에서 언급한 포트와는 다르다.
스위치 구조- 스위치 구조는 라우터의 입력 포트와 출력 포트를 연결한다.
- 라우터 내부에 포함되어 있다.
출력 포트- 출력 포트는 스위치 구조에서 수신한 패킷을 저장하고 필요한 링크 계층 및 물리 계층 기능을 수행하여 출력 링크로 패킷을 전송한다.
- 링크가 양방향일 경우 출력 포트는 일반적으로 동일한 링크의 입력 포트와 한 쌍을 이룬다.
라우팅 프로세서- 제어평면 기능을 수행한다.
- 전통적인 라우터에서는 라우팅 프로토콜을 실행하고 라우팅 테이블과 연결된 링크 상태 정보를 유지 관리하며 라우터의 포워딩 테이블을 계산한다.
- SDN 라우터에서 라우팅 프로세서는 원격 컨트롤러와 통신하여 원격 컨트롤러에서 계산된 포워딩 테이블 엔트리를 수신하고 라우터의 입력 포트에 이러한 엔트리를 설치한다.
- 네트워크 관리 기능을 수행한다.
라우터의 입력 포트, 출력 포트, 스위치 구조는 거의 항상 하드웨어로 구현된다.
제어 평면은 일반적으로 소프트웨어로 구현되며 라우팅 프로세서(일반적으로 기존 CPU)에서 실행된다.
4.2.1 입력 포트 처리 및 목적지 기반 전송
입력 포트의 기능은 위에서 언급한 바와 같다.
입력 포트에서 수행되는 검색은 라우터 동작의 핵심이다.
라우터는 포워딩 테이블을 사용하여 도착 패킷이 스위치 구조를 통해 전달되는 출력 포트를 검색한다.
포워딩 테이블은 라우팅 프로세서에서 계산되거나 갱신되거나 원격 SDN 컨트롤러에서 수신된다.
포워딩 테이블은 라우팅 프로세서에서 맨위 그림과 같이 각 라인 카드로 복사되고, 이렇게 각 라인이 복사본을 사용하여 패킷 단위로 중앙 집중식 라우팅 프로세서를 호출하지 않게 되어 병목 현상을 피할 수 있다.
목적지 주소 범위 포워딩 테이블
32비트의 IP 주소의 경우 포워딩 테이블을 억지로 구현한다면 모든 가능한 목적지 주소마다 하나의 엔트리가 필요하고, 이는 40억개 이상의 주소가 있어야 하므로 불가능하다.
라우터에서 0에서 3까지의 4개의 링크가 있다고 가정해보자.
목적지 주소 범위로 포워딩 테이블을 구성할 경우 4개의 엔트리를 갖는 포워딩 테이블이면 된다.
프리 픽스 포워딩 테이블
이런 형식의 포워딩 테이블에서 라우터는 패킷의 목적지 주소의
프리픽스(prefix)를 테이블의 엔트리와 매치한다.예를 들어, 패킷의 목적지 주소가
11001000 00010111 00010110 10100001 라면 앞 21개의 비트 프리픽스가 테이블의 첫 번째 엔트리와 매치되므로 라우터는 이 패킷을 링크 인터페이스 0으로 보낸다.11001000 00010111 00011000 10101010와 같이 처음 24비트는 2번째에 처음 21비트는 3번째에 매치되는 경우 라우터는 최장 프리픽스 매치 규칙(longest prefix matching rule)을 사용한다.즉, 테이블에서 가장 긴 매치 엔트리를 찾고, 여기에 연관된 링크 인터페이스로 패킷을 보낸다. (이유에 대해서는 4.3절에서 다룬다.)
이러한 테이블 설계 뿐만 아니라 검색은 나노초 단위로 수행되어야 하므로 이외의 기술이 필요하다.
메모리 접속 시간에 특별한 주의를 기울여야하므로 내장형 DRAM과 빠른 SRAM 메모리가 있는 설계가 필요하다. 실제로 TCAM도 검색을 위해 자주 사용된다.
검색을 통해 패킷의 출력 포트가 결정되면 패킷을 스위치 구조로 보낼 수 있다. 일부 설계에서는 다른 입력 포트로부터 패킷이 현재 구조를 사용하고 있다면 패킷이 스위칭 구조에 들어가는 것을 일시적으로 차단할 수 있다.
앞으로 패킷의 차단, 큐잉, 스케줄링에 대해 자세히 살펴본다.
4.2.2 스위칭
스위치 구조는 패킷이 입력 포트에서 출력 포트로 실제로 스위칭 되는 구조를 통과하므로 라우터의 핵심이다.
여기서는 여러가지 스위칭 방법을 설명한다.
메모리를 통한 교환
초기의 라우터는 라우터 프로세서를 직접 제어해서 입력 포트와 출력 포트 사이에서 패킷을 스위칭하는 전통적인 컴퓨터다. 입력 포트와 출력 포트는 I/O 장치처럼 작동한다.
패킷 전달 과정
- 패킷이 도착하면 입력 포트는 라우팅 프로세서에게 인터럽트를 보내 패킷을 프로세서 메모리에 복사한다.
- 라우팅 프로세서는 헤더에서 목적지 주소를 추출한다.
- 포워딩 테이블에서 적절한 출력 포트를 찾은 다음 패킷을 출력 포트의 버퍼에 복사한다.
위 과정에서 메모리 대역폭이 초당 최대 B인 패킷을 메모리에 쓰거나 메모리에서 읽을 수 있는 경우 전체 전달 처리량은 B/2 보다 작아야하며 목적지 포트가 다른 경우라도 공유 시스템 버스를 통해 한 번에 하나의 메모리 읽기/쓰기 작업을 수행할 수 있기 때문에 두 패킷을 동시에 전달할 수 없다.
최근의 메모리를 통해 스위칭하는 라우터는 목적지 주소를 검색하고 해당 메모리 위치에 패킷을 저장하는 것이 입력 라인 카드에서 처리함으로써 수행한다.
버스를 통한 교환
입력 포트는 라우팅 프로세서의 개입 없이 공유 버스를 통해 직접 출력 포트로 패킷을 전송한다.
일반적으로 미리 준비된 입력 포트 스위치 내부 레이블이 로컬 출력 포트를 나타내는 패킷에게 전송되거나 버스에 패킷을 전송하여 수행된다.
모든 출력 포트에 패킷이 수신되지만 레이블과 매치되는 포트만 패킷을 유지한다.
레이블은 버스를 통과하기 위해서만 사용되므로 출력 포트에서 제거된다.
동시에 여러 패킷이 다른 입력 포트에 있는 라우터에 도착하면 한 번에 하나의 패킷만 버스를 통과할 수 있기 때문에 하나를 제외한 모든 패킷이 대기 해야한다.
모든 패킷이 하나의 버스를 통과해야하므로 라우터의 교환 속도는 버스 속도에 의해 제한된다.
상호 연결 네트워크를 통한 교환
크로스바 스위치는 N개의 입력 포트를 N개의 출력 포트에 연결하는 2N 버스로 구성된 상호연결 네트워크다.
각 수직 버스는 교차점에서 각 수평 버스와 교차하며 스위치 구조 컨트롤러에 의해 언제든지 열거나 닫을 수 있다.
이를 통해 앞의 두가지 방식과 달리 크로스바 스위치는 여러 패킷을 병렬로 전달할 수 있다.
그러나 두개의 서로 다른 입력 포트에서 나오는 2개의 패킷이 동일한 출력 포트로 보내지는 경우 한번에 하나의 패킷만 특정 버스에서 전송될 수 있기 때문에 입력을 기다려야한다.
좀 더 정교한 상호연결 네트워크는 다단계 스위치 구조를 통해 각기 다른 입력 포트의 패킷이 동일한 출력 포트를 향해 동시에 전달할 수 있도록 여러 단계의 스위칭 요소를 사용한다.
4.2.3 출력 포트 처리
위 그림의 출력 포트 처리는 출력 포트의 메모리에 저장된 패킷을 가져와서 출력 링크를 통해 전송한다. 여기에는 전송을 위한 패킷 선택 및 큐 제거, 필요한 링크 계층 및 물리 계층 전송 기능을 수행하는 것이 포함된다.
어디에서 큐잉이 일어날까?
패킷 큐는 입력 포트와 출력 포트 모두에서 형성될 수 있다.
큐의 위치와 범위는 트래픽 로드, 스위치 구조의 상대 속도 및 라인 속도에 따라서 달라진다.
이 큐가 커지면 라우터의 메모리가 결국 소모될 수 있고 도착하는 패킷을 저장할 수 있는 메모리가 없을 때 패킷 손실이 발생한다.
입력 큐잉
지연 없이 구조를 통해 도착하는 모든 패킷을 전송하기에 스위치 구조가 충분히 빠르지 않으면 어떻게 될까?
이 경우에는 패킷이 스위치 구조를 통해 출력 포트로 전송되기 위해 차례를 기다려야한다.
이 큐잉의 결과를 살펴보기 위해 크로스바 스위치 구조를 가정해보자.
- 모든 링크의 속도는 같다.
- 입력 링크가 패킷을 받는 것과 같은 속도로 하나의 패킷을 입력 포트에서 주어진 출력 포트로 전달한다.
- FCFS (First-Come-First-Served) 방식으로 패킷은 입력 큐에서 출력 큐로 이동된다.
출력 포트가 다르다면 여러 패킷이 병렬로 전달 가능하지만, 같다면 하나의 패킷만 지정된 출력 포트로 전송이 가능하고 나머지 패킷은 기다려야한다.
위 그림에서 왼쪽 상단 큐의 앞쪽에서 먼저 패킷을 전송한다고 가정해보자.
왼족 하단 큐의 가장 앞쪽의 패킷은 출력 포트가 같으므로 대기하여야하고, 두번째 패킷은 출력 포트가 다름에도 앞의 패킷 때문에 대기하여야한다.
이 현상은 입력 대기 중인 스위치에서의
HOL(Head-of-the-line) 차단 이라고 한다.츌력 큐잉
입력 포트와 출력 포트의 개수가 각각 N개이고 속도가 R이라 할 때, 스위치의 속도가 R보다 N배 빠르고 모든 입력 포트의 패킷이 동일한 출력 포트로 향한다고 가정해보자.
이 경우, 출력 링크에서 단일 패킷을 보내는 데 걸리는 시간에 N개의 새로운 패킷이 출력 포트에 도착한다. 출력 포트는 시간 단위에 단일 패킷만을 전송할 수 있기 때문에 N개의 도착 패킷은 출력 링크를 통한 전송 큐에서 대기 해야한다.
이때 큐의 공간이 충분하지 않을 때, 즉 메모리가 충분하지 않을 때 도착한 패킷을 삭제하고나 이미 대기 중인 하나 이상의 패킷을 제거하여 새로 도착한 패킷을 저장하기 위한 공간을 확보해야 한다.
위 그림은 출력 포트 큐잉의 예시이다.
이러한 큐잉의 결과는 출력 포트의
패킷 스케줄러가 전송 대기 중인 패킷 중 하나의 패킷을 선택하여 큐에서 제거 해야한다는 것이다. (다음 절에서 다룬다.)얼마나 많은 버퍼가 요구되는가?
몇년 동안 RFC의 버퍼의 크기에 대한 규칙은 링크 용량이 C일 때, 버퍼링의 양은 평균 왕복 시간(RTT)와 같아야 한다는 것이다.
즉,
B = RTT x C 와 같은 버퍼의 양이 필요하다.최근의 실험과 이론에서는 많은 수의 독립적인 TCP 흐름 N이 링크를 통과할 때, 필요한 버퍼링은
B = RTT x C / √N 이라고 제안하고 있다.버퍼링이 클수록 라우터가 패킷 도착 속도의 큰 변동을 흡수하여 라우터의 패킷 손실률을 감소 시킬 수 있기 때문에 버퍼링이 낫다고 생각하는 것보다 버퍼가 클수록 큐잉 지연이 길어진다고 생각하는 편이 좋다.
예를 들어, 패킷 손실을 줄이기 위해 홉당 버퍼의 양을 10배 늘리면 종단 간 지연이 10의 배만큼 증가한다.
즉, 버퍼의 크기 증가는 패킷 손실율을 줄일 수 있지만 종단 간 지연을 증가시킬 수 있는 양날의 검이다.
네트워크 가장자리의 라우터를 생각해보자.
a는 TCP 세그먼트를 원격 게임 서버로 보내는 홈 라우터에 대한 설명이다. 게이머의 TCP 세그먼트를 포함하는 패킷을 전송하는 데 20ms가 소요되며, 큐잉 지연이 무시해도 될 정도라고 가정한다.
게임 서버 경로의 다른 곳에서 지연되며 RTT는 200ms다.
b에서와 같이 t = 0 에서 25개 패킷의 버스트가 큐에 도착한다고 가정한다.
대기 중인 패킷들 중 하나는 20ms 마다 한 번씩 전송되므로, 21 번째 패킷이 전송되고 있는 것처럼 t = 200ms에서 첫 번째 ACK가 도착한다. 이 ACK 도착은 송신자가 다른 패킷을 보내게 한다.
홈 라우터의 송신 링크 t = 220에서 다음 ACK가 도착하고, 또 다른 ACK가 도착한다. TCP 세그먼트는 게이머에 의해 해제되며, 22번째 패킷은 전송되는 큐에 놓인다.
위 과정에서 ACK 클록은 대기 중인 패킷이 있을 때마다 새 패킷이 큐에 도착하게 되고, 전송되어 홈 라우터의 송신 링크에서 큐 크기가 항상 5 패킷이 된다.
즉, 종단 간 파이프는 꽉 찼지만 큐잉 지연의 양은 일정하고 지속적이다.
결과로 게이머는 홈 네트워크에 다른 트래픽이 존재하지 않는 경우에도 지연이 지속적으로 지나치게 긴 이유를 이해하지 못하게 된다.
이러한 지속적 버퍼링으로 인한 긴 지연에 대한 위 과정을 버퍼블로트(bufferbloat)라고 한다.
이를 극복하기 위해 6장에서 연구할 케이블 네트워크용 DOCIS 3.1 표준은 AQM 메커니즘을 추가하여 대량 처리 성능을 보존했다.
4.2.5 패킷 스케줄링
FIFO
링크가 현재 다른 패킷을 전송 중이면, 출력 링크 큐에 도착한 패킷은 전송을 기다린다.
도착한 패킷을 담을 버퍼 공간이 충분하지 않은 경우 도착 패킷의 공간을 확보하기 위해 큐의 패킷 폐기 정책은 패킷 손실 여부 또는 다른 패킷을 큐에서 제거할 것인지 여부를 결정한다.
FIFO 스케줄링 규칙은 출력 링크 큐에 도착한 순서와 동일한 순서로 출력 링크에서 전송할 패킷을 선택한다.
위 그림에서는 FIFO 큐의 동작을 보여준다.
우선순위 큐잉
우선순위 큐잉에서 출력 링크에 도착한 패킷은 우선순위 클래스로 분류된다.
실제로 네트워크 오퍼레이터는 네트워크 관리 정보를 운반하는 패킷이 사용자 트래픽보다 우선순위를 수신하도록 큐를 구성할 수 있다.
전송할 패킷을 선택할 때 전송 대기 중인 패킷으로 차 있는 상태이고 가장 높은 우선순위 클래스에서 패킷을 전송한다.
우선순위가 동일한 패킷들 중에서의 선택은 FIFO 방식으로 행해진다.
위 그림은 우선순위 클래스가 2개인 경우의 큐 동작을 보여준다.
패킷 1,3,4가 우선순위가 높기 때문에 먼저 전송된다.
이때는
비선점 우선순위 큐잉이기 때문에 패킷 4의 우선순위가 높더라도 패킷 2의 전송이 시작되면 선점하지 않고 전송이 끝난 후에야 전송이 시작된다.라운드 로빈과 WFQ
라운드 로빈 큐잉 큐칙에서는 패킷은 우선순위 큐잉과 같이 클래스로 분류되지만 클래스 간에는 엄격한 서비스 우선순위가 존재하지 않으며, 라운드 로빈 스케줄러가 클래스 간에 서비스를 번갈아서 제공한다.
가장 단순한 라운드 로빈 스케줄링에서는 그저 클래스를 번갈아가면서 패킷을 전송한다.
작업 보존 큐잉 규칙의 경우 전송을 위해 큐에서 기다리는 패킷이 있다면 링크는 유휴 상태가 되는 것을 허용하지 않는다.즉, 클래스에 패킷이 없다면 바로 시퀀스의 다음 클래스를 검사한다.
위 그림은 라운드 로빈 큐의 동작을 보여준다.
라우터에서 널리 구현된 라운드 로빈 큐잉의 일반화된 형태는 소위
WFQ(Weighted Fair Queueing) 규칙이다.도착하는 패킷은 적절한 클래스별 대기 영역에서 분류되며 대기한다.
WFQ 스케줄러는 라운드 로빈과 같이 순환식으로 동작한다.
또한, 작업 보존 큐잉 규칙을 따른다.
WFQ는 각 클래스 i 는 가중치 w(i)를 할당 받는다.
WFQ에서는 전송할 클래스 i 패킷이 있는 동안에 클래스 i는
w(i) / ∑w(i) 만큼의 서비스 시간을 보장받으며, 이 식에서 분모 부분은 전송을 위해 큐에 패킷이 있는 모든 클래스의 합이다.즉, 최악의 경우 모든 큐에 패킷이 있을 때도 위의 시간을 보장 받는다.
따라서 전송률 R인 링크에 대해 클래스 i는 항상 최소한
R x w(i) / ∑w(i)의 처리율을 갖는다.패킷이 이상적인 단위 데이터라는 것과 패킷 전송이 다른 패킷을 전송하기 위해 방해되지 않는다는 사실을 고려하지 않았기 때문에 위 설명은 이상적이다.