패킷 스케줄링
지난 포스팅을 떠올려 큐에 있는 패킷이 출력 링크를 통해 전송되는 순서를 결정하는 문제를 생각해보자.
이러한 순서를 결정하는 방법은 여러가지가 존재하며 이번 포스팅에서 이에 대해 알아보자.
FIFO (FCFS) 선입선출
링크가 현재 다른 패킷을 전송 중이라면, 출력 링크 큐에 도착한 패킷은 전송을 기다린다. 패킷이 출력되는 링크를 통해 완전히 전송되면 큐에서 제거된다. 아래 시간 흐름에 따른 패킷 전송을 보자
FCFS (first come first out) 또는 FIFO (first in first out) 가장 단순한 알고리즘이며, 직관적이다. 도착한 순서와 동일한 순서로 패킷들을 내보낸다.
Priority 우선순위
우선순위 큐잉은 큐에 도착한 패킷들을 우선순위 클래스로 분류한다. 예를 들어 실시간 VoIP 패킷은 전자메일과 같은 패킷보다 높은 우선순위를 부여받을 수 있다. 전송할 패킷을 선택할 때 가장 높은 우선순위 클래스에서 패킷을 전송한다. 우선순위가 동일한 경우 전형적으로 FIFO 방식으로 행해진다.
위 그림은 우선순위 클래스가 2개인 경우의 큐동작을 보여준다. 패킷 1,3,4 는 높은 우선순위, 나머지는 낮은 우선순위를 가진다. 따라서 높은 우선순위의 패킷이 존재할 경우, 낮은 우선순위의 패킷이 존재하더라도 우선시 된다.
패킷 3의전송이 끝나고 패킷2의 전송을 하는 도중 패킷 4가 도착한다. 이때 비선점 우선순위 큐잉 (non-premeemptive priority queuing)에서는 패킷의 전송이 시작된 이상 중단하지는 않으므로 패킷2의 전송이 끝날 때 까지 대기한다.
이 방법은 높은 우선순위의 패킷이 끊임 없이 들어올 경우 낮은 우선순위의 패킷이 전송되지 못하는 starvation 아사 문제가 발생할 수 있다.
RR (Round-Robin) 라운드 로빈
라운드 로빈 RR 방식의 경우 우선순위 큐잉과 마찬가지로 여러 클래스로 패킷을 분류하지만 우선순위를 두지 않는다. 다만 클래스 간 번갈아 가며 패킷을 전송하게 된다.
작업 보전 큐잉 (work-conserving queuing)의 경우 큐에 대기하고 있는 패킷이 있다면 유휴상태가 되는 것을 허용치 않는다. 따라서 해당 차례에 클래스에서 패킷을 찾지 못하면 바로 다름 클래스를 즉시 검사한다.
위 그림은 RR 알고리즘의 큐잉 동작을 보여주고 있다.
WFQ (Weighted Fair Queuing)
이는 라우터에서 널리 구현된 RR 방식의 일반화된 형태이다.
WFQ 큐잉 알고리즘에서는 클래스 별 대기영역에서 분류되며 대기한다. RR 방식과 같이 순환형식으로 동작하지만 각 클래스마다 다른양의 서비스 시간을 스케줄러에게 부여된다. 각 클래스는 가중치를 할당 받으며 패킷이 존재하는 클래스들의 전체 가중치의 합에서 할당된 가중치의 비율만큼 서비스 시간을 보장받는다.
WFQ 또한 작업보전큐잉이며, 우선순위 큐잉과 달리 starvation이 발생하지 않는다. 이는 최소 대역폭을 보장할 수 있음을 의미한다.
주의할 것은 여기서 설명하는 WFQ는 이상적인 형태이다. 왜냐하면 패킷이 이상적인 단위 데이터임을 전제하고 있고, 패킷 전송이 다른 패킷을 전송하기 위해 방해되지 않는다는 사실을 고려하고 있지 않았기 때문이다.