라우터의 4가지 요소
- 입력 포트
- 라우터로 들어오는 패킷을 수신하는 포트
- 입력 포트의 맨 왼쪽과 맨 오른쪽 박스는 라우터로 들어오는 입력 링크로, 물리 계층 기능을 수행한다.
- 또한 입력 포트는 들어오는 링크의 반대편에 있는 링크계층과 상호 운용하기 위해 필요한 링크 계층 기능을 수행한다.
- 가장 중요한 기능은 입력 포트에서 검색 기능을 수행하는 것이다. 여기서 포워딩 테이블을 참조하여 도착된 패킷이 스위치 구조를 통해 라우터 출력 포트를 결정한다.
- 라우팅 프로토콜 정보를 전달하는 제어 패킷은 입력 포트에서 라우팅 프로세서로 전달된다.
- 스위치 구조
- 입력 포트에서 수신한 패킷을 출력 포트로 전달하는 방식
- 라우터의 입력 포트와 출력 포트를 연결한다.
- 스위치 구조는 라우터 내부에 포함되어 있다
- 출력 포트
- 라우터에서 출발하는 패킷을 전송하는 포트
- 스위치 구조에서 수신한 패킷을 저장하고, 필요한 링크 계층 및 물리 계층 기능을 수행하여 출력 링크로 패킷을 전송한다.
- 링크가 양방향인 경우, 출력 포트는 일반적으로 동일한 링크의 입력 포트와 한쌍을 이룬다.
- 라우팅 프로세서
- 패킷을 목적지로 전달하기 위한 경로를 결정하는 장치
- 제어 평면 기능을 수행한다.
- SDN 라우터에서 라우팅 프로세서는 원격 컨트롤러와 통신하여 원격 컨트롤러에서 계산된 포워딩 테이블 엔트리를 수신하고, 라우터의 입력 포트에 이러한 엔트리를 설치한다.
- 또한, 네트워크 관리 기능을 수행한다.
입력 포트 처리 및 목적지 기반 전송
- 입력 포트에서 수행되는 검색은 라우터 동작의 핵심이다.
- 라우터는 포워딩 테이블을 사용하여 도착 패킷이 스위치 구조를 통해 전달되는 출력 포트를 검색한다.
- 포워딩 테이블은 라우팅 프로세서에서 계산/갱신되거나, 원격 SDN 컨트롤러에서 수신된다.
- 32비트 IP주소의 경우, 포워딩 테이블을 억지로 구현한다면 모든 가능한 목적지 주소마다 하나의 엔트리가 필요하고, 이는 40억개 이상의 주소가 있어야 하므로 불가능하다.
- 이 문제의 처리를 위해 라우터 0~3의 4개의 링크가 있다고 가정해보자. 목적지 주소 범위로 포워딩 테이블을 구성할 경우 4개의 엔트리를 갖는 포워딩 테이블이면 가능하다.
- 이런 형식의 포워딩 테이블에서 라우터는 패킷의 목적지 주소의 프리픽스를 테이블의 엔트리와 매치한다.
- 이는 목적지 주소가 1개 엔트리 이상에 매치될 수 있는 가능성이 있음을 알 수 있고, 이러한 다수의 매치가 있을 때 라우터는 프리픽스 매치 규칙(가장 긴 매치 엔트리를 찾고 여기의 링크 인터페이스로 패킷을 보냄)을 사용한다.
스위칭
- 스위치 구조는 패킷이 입력 포트에서 출력 포트로 실제로 스위칭되는 구조를 통과하므로 라우터의 핵심이다.
- 메모리, 버스, 상호연결 네트워크를 사용하는 방법들로 스위칭을 수행할 수 있다.
- 메모리를 통한 교환
- 초기의 라우터는 라우팅 프로세서를 직접 제어해서 입력포트와 출력포트 사이에서 패킷 스위칭을 하는 전통적인 방식을 썼다.
- 패킷이 도착하면, 입력포트는 라우팅 프로세서에게 인터럽트를 보내 패킷을 프로세서 메모리에 복사한다.
- 라우팅 프로세서는 헤더에서 목적지 주소를 추출한다.
- 포워딩 테이블에서 적절한 출력포트를 찾은 후, 패킷을 출력포트의 버퍼에 복사한다.
- 버스를 통한 교환
- 입력포트는 라우팅 프로세서의 개입 없이 공유 버스를 통해 직접 출력포트로 패킷을 전송한다.
- 일반적으로 미리 준비된 입력포트 스위치 내부 레이블이, 로컬 출력포트를 나타내는 패킷에게 전송되거나 버스에 패킷을 전송하여 수행된다.
- 모든 출력포트에 패킷이 수신되지만, 레이블과 매치되는 포트만 패킷을 유지한다.
- 레이블은 버스를 통과하기 위해서만 사용되므로 출력포트에서 제거된다.
- 동시에 여러 패킷이 다른 입력포트에 있는 라우터에 도착하면, 한번에 하나의 패킷만 통과할 수 있기 때문에 나머지 모든 패킷이 대기해야 한다.
- 모든 패킷이 하나의 버스를 통과해야 하므로, 라우터의 교환 속도는 버스 속도에 의해 제한된다.
- 상호연결 네트워크를 통한 교환
- 크로스바 스위치는 N개의 입력포트를 N개의 출력포트로 연결하는 2N 버스로 구성된 상호연결 네트워크이다.
- 각 수직버스는 교차점에서 각 수평버스와 교차하며, 스위치 구조 컨트롤러에 의해 언제든지 열거나 닫을 수 있다.
- 이를 통해 앞의 두 방식과는 달리, 여러 패킷을 병렬로 전달할 수 있다.
- 그러나, 2개의 서로 다른 입력포트에서 나오는 2개의 패킷이 동일한 출력포트로 보내지는 경우는 한번에 하나의 패킷만 특정 버스에서 전송될 수 있기 때문에 입력을 기다려야 한다.
출력 포트 처리
- 출력포트 처리는 출력포트의 메모리에 저장된 패킷을 가져와서 출력링크를 통해 전송한다.
- 여기에는 전송을 위한 패킷 선택 및 큐 제거, 필요한 링크계층 및 물리계층 전송 기능을 수행하는 것이 포함된다.
어디에서 큐잉이 일어날까?
- 패킷 큐는 입력포트와 출력포트 모두에서 형성될 수 있다.
- 큐의 위치와 범위는 트래픽 로드, 스위치 구조의 상대 속도 및 라인 속도에 따라서 달라진다.
- 이 큐가 더 커지면 라우터 메모리가 결국 소모될 수 있고, 도착하는 패킷을 저장할 수 있는 메모리가 없을 때 패킷 손실이 발생한다.
입력 큐잉
- 도착하는 모든 패킷을 전송하기에 스위치 구조에 입력라인 속도에 비해 충분히 빠르지 않으면 어떻게 될까?
- 이 경우에는 패킷이 스위치 구조를 통해 출력포트로 전송되기 위해 차례를 기다려야 한다.
- 이 큐잉의 결과를 살펴보기 위해 크로스바 스위치 구조를 가정해보자.
- 1) 모든 링크의 속도는 같다.
- 2) 입력링크가 패킷을 받는 것과 같은 속도로 하나의 패킷을 입력포트에서 주어진 출력포트로 전달한다.
- 3) FCFS(First-Come-First-Served) 방식으로 패킷은 입력큐에서 출력큐로 이동된다.
- 출력포트가 다르다면 여러 패킷이 병렬로 전달 가능하지만, 같다면 스위치 구조는 한번에 하나의 패킷만 지정된 출력포트로 전송이 가능하고 나머지 패은 기다려야 한다.
- 같은 출력포트로 보내지는 2개의 패킷이 있는 경우 하나의 패킷은 기다려야 하고, 다른 출력포트임에도 앞의 패킷 때문에 대기해야 하는 HOL(Head-of-the-line)차단이 발생한다.
출력 큐잉
- 입력포트와 출력포트의 개수가 각각 N개이고 속도가 R일 때, 스위치의 속도가 R보다 N배 빠르고 모든 입력포트의 패킷이 동일한 출력포트로 향한다고 가정하자.
- 이때, 출력링크에서 단일 패킷을 보내는데 걸리는 시간에 N개의 새로운 패킷이 출력포트에 도착한다. 출력포트는 시간 단위에 단일 패킷만을 전송할 수 있기 때문에 N개의 도착 패킷은 출력링크를 통한 전송 큐에서 대기해야 한다.
- 이때 큐의 공간이 충분하지 않으면, 즉 메모리가 충분하지 않을 때 도착한 패킷을 삭제하거나 이미 대기중인 하나 이상의 패킷을 제거하여 새로 도착한 패킷을 저장하기 위한 공간을 확보해야 한다.
- 이러한 큐잉의 결과는 출력포트의 패킷 스케줄러가 전송 대기중인 패킷 중 하나를 선택하여 큐에서 제거하게 된다.
패킷 스케줄링
FIFO
- 링크가 현재 다른 패킷을 전송 중이면, 출력링크 큐에 도착한 패킷은 전송을 기다린다.
- 도착한 패킷을 담을 버퍼 공간이 충분하지 않은 경우, 도착 패킷의 공간을 확보하기 위해 큐의 패킷 제거 정책은 패킷 손실 여부 또는 다른 패킷을 큐에서 제거할 여부를 결정한다.
- 이 규칙은 출력링크 큐에 도착한 순서와 동일한 순서로 출력링크에서 전송할 패킷을 선택한다.
우선순위 큐잉
- 이 규칙에서 출력링크에 도착한 패킷은 우선순위 클래스로 분류된다.
- 실제로 network operator는 네트워크 관리 정보를 운반하는 패킷이 사용자 트래픽보다 우선순위를 수신하도록 큐를 구성할 수 있다.
- 전송 패킷을 선택할 때 전송 대기중인 패킷으로 차 있는 상태이고, 가장 높은 우선순위 클래스에서 패킷을 전송한다.
- 우선순위가 동일한 패킷들 중에서는 FIFO 방식으로 선택한다.
- 비선점 우선순위 큐잉: 낮은 우선순위의 패킷이 전송되고 있을 때, 높은 우선순위의 패킷이 도착하더라도 선점하지 않고 전송이 끝날 때까지 기다린다.
라운드 로빈과 WFQ
- 라운드 로빈에서는 우선순위 큐잉과 같이 클래스로 분류되지만 엄격한 서비스 우선순위가 존재하지 않으며, 라운드 로빈 스케줄러가 클래스 간에 서비스를 번갈아서 제공한다.
- 작업 보존 큐잉: 전송을 위해 큐에서 기다리는 패킷이 있다면 링크의 유휴 상태(데이터를 전송하지 않는 상태)를 허락하지 않는다.
- 즉, 클래스에서 패킷을 찾지 못하면 시퀀스의 다음 클래스를 바로 검사한다.
- 라우터에서 널리 구현된 라운드 로빈 큐잉의 일반화된 형태는 WFQ (Weighted Fair Queuing)이다.
- 도착하는 패킷은 적절한 클래스별 대기 영역에서 분류되어 대기한다.
- WFQ 스케줄러는 라운드 로빈처럼 순환 방식으로 동작한다. (클래스1 → 클래스2 → 클래스3)
- 작업 보존 큐잉을 따르므로 빈 클래스 큐를 찾으면 서비스 순서에서 다음 클래스로 즉시 이동한다.
- WFQ는 각 클래스마다 다른 양의 서비스 시간을 부여받는다는 점에서 라운드 로빈과 차이가 있다.
- 각 클래스 i는 가중치 w(i)를 할당받고, 전송할 클래스 i 패킷이 있는 동안에 클래스 i는 w(i) / (전송을 위해 큐에 패킷이 있는 모든 클래스의 합) 만큼의 서비스 시간을 보장받는다.
- 따라서 전송률 R인 링크에 대해, 클래스 i는 항상 최소한 R*w(i) / (전송을 위해 큐에 패킷이 있는 모든 클래스의 합)의 처리율을 갖는다.
