Packet Scheduling

상위 문서: Router

개요

패킷 스케쥴링(Packet scheduling)이란 출력 포트 버퍼에 여러 패킷이 대기하고 있을 때 어떤 순서로 패킷을 보낼지를 결정하는 메커니즘이다. 이때 패킷 스케쥴링에서 고려해야할 요소는 크게 network neutrality와 priority이다. Network neutrality는 네트워크가 특정 기업이나 서비스에 편향적인 대우를 해서는 안된다는 것이다. 즉, 네트워크는 공공의 것이므로 그 누구에게 치우침도 없이 공정하게 운영되어야 한다는 것이다. 이는 일견 맞는 말처럼 보인다. 하지만 network neutrality를 엄격하게 실천할 경우에는 네트워크 트래픽을 과도하게 사용하고 있는 어떤 무임승차자를 처벌하거나 제제할 방법이 없다. 이 경우에는 네트워크에 투자할 기업이나 국가가 줄어들어 전체 네트워크 망에 대한 투자가 감소할 수도 있다.
이에 대치되는 개념이 priority이다. 어떤 패킷은 특별히 더 중요한 성격을 띄고 있을 수 있다. 예를 들어 해당 패킷의 송신 호스트가 망사용료를 많이 내는 기업이나 개인일 수도 있고, 중요한 기관에서 전송된 패킷일 수도 있다. 이러한 패킷에 더 높은 priority를 주고, 해당 패킷에 더 많은 혜택을 제공한 다면 국가나 기업이 네트워크 망에 투자할 유인이 생겨 네트워크에 대한 투자가 증가할 수도 있다. 그러나 이는 공공의 성격을 띄는 네트워크의 목적성에 부합하지 않는다는 점이 지적되기도 한다.
따라서 패킷 스케쥴링을 설계할 때는 priority나 neutrality를 고려하여 설계되며, 그 설계 방식에 따라 neutrality를 중시할 수도 있고, priority를 중심으로 설계될 수도 있으며, 이 선택에 따라 네트워크의 성능, 사용자 만족도, 투자 유인 등에 큰 영향을 미친다.

First-in-First-Out

Figure 1. The FIFO queue in operation

Figure 2. FIFO queueing abstraction

FIFO(First-in-First-Out) 방식은 쉽게 말해서 버퍼에 도착한 순서대로 패킷을 전송하는 방식이다. Figure 1은 FIFO 방식이 어떻게 동작하는지 잘 보여준다. 패킷 도착 순서는 위쪽 타임라인 위의 상자에 표시되어 있으며, 패킷 전송(출발)은 아래쪽 타임라인에 나타나있다. 또한 각 시간에 어떤 패킷이 전송되고 있는지는 두 타임라인 사이에 표시되어 있다. 해당 문서의 예제에서는 각 패킷을 전송하는데 3t 만큼이 소요된다. Figure 2는 각 패킷이 도착한 순서대로 전송되는 것을 잘 보여준다. 또한 패킷 4가 전송된 이후 queue에는 아무 패킷도 남아 있지 않기 때문에 패킷 5가 도착하기 전까지 출력 링크(link)는 idle 상태가 되어있다. Figure 2는 FIFO 방식에 사용되는 포트를 추상화하여 도식적으로 나타낸 것이다.

Priority Queuing

Figure 3. The priority queue in operation

Figure 4. The priority queueing model

Priority queuing에서는 출력 링크로 도착하는 패킷들이 queue에 도착하면서 priority class로 분류된다. 각 priority class는 고유한 queue를 가지며, 스케쥴러는 전송할 패킷을 고를 때 queue가 비어있지 않은 가장 높은 priority queue에서 패킷을 선택한다. 또한 같은 priority class 내에서는 보통 FIFO 방식으로 처리한다. Figure 4는 priority queueing 방식을 이용하는 포트를 추상화하여 도식적으로 나타내었다. 또한 figure 3는 priority queueing 방식이 어떻게 동작하는지 잘 보여준다. 해당 예제에서는 priority class가 두개 존재하며, 패킷 1, 3, 4는 high-priority class, 패킷 2, 5는 low-priority class에 속한다. 위 예제는 다음과 같이 동작한다.

1. 패킷 1이 도착했을 때 링크가 비어 있으므로 즉시 전송을 시작한다.
2. 전송 중에 패킷 2(low), 패킷 3(high)이 도착하여 각자 큐에 저장된다.
3. 패킷 1 전송이 끝나면 패킷 2가 먼저 도착했음에도 high-priority queue에 저장된 패킷 3이 먼저 전송되고 이후 패킷 2가 전송된다.
4. 패킷 2 전송 중에 패킷 4(high)가 도착하더라도 전송 중단은 없으며, 패킷 4는 high-priority queue에서 대기하다가 패킷 2 전송 후 전송된다.

Round Robin and Weighted Fair Queuing

Figure 5. The two-class robin queue in operation

Round robin 방식에서도 패킷은 class 별로 구분된다. 하지만 class 사이에 엄격한 priority는 존재하지 않으며, class 별로 번갈아가며 전송된다. 이때 work-conserving queueing이라는 개념이 추가로 적용되어, 전송할 패킷이 있는 한 link를 idle 상태로 만들지 않을 수 있다. 즉, 특정 class에 전송할 패킷이 없다면 다음 class 순번으로 바로 넘어가는 방식이다. Figure 5는 round robin 방식이 어떻게 동작하는지 잘 보여준다. 해당 예제에서는 2개의 class로 구분되어 있으며, 패킷 1, 2, 4는 class 1에, 패킷 3, 5는 class 2에 속한다. 위 예제는 다음과 같이 동작한다.

1. 패킷 1은 즉시 전송된다.
2. 전송 중 패킷 2, 3 도착하며, 각 패킷은 해당하는 class queue에 저장된다.
3. 패킷 1을 전송 완료한 후, 클래스 2가 전송될 차례이므로 패킷 3을 전송한다.
4. 패킷 2를 전송 완료한 후, 클래스 1이 전송될 차례이므로 패킷 2를 전송한다.
5. 패킷 2를 전송하고 남은 패킷은 패킷 4 하나이므로 class 순서를 기다리지 않고 즉시 전송한다.

Figure 6. Weighted fair queueing

WFQ(Weighted Fair Queueing)은 round robin의 일반화된 형태로, 실제로 라우터에서 많이 구현되는 방식이다. WFQ는 round robin과 같이 class 별 고유한 queue가 존재하며, round robin과 같이 순환적으로 패킷 전송을 지원하나, 각 class 별로 가중치(weight)를 설정한다는 차이점이 있다. 이때 WFQ의 핵심 아이디어는 class i 에 가중치 w_i 가 주어졌을 때, 해당 class가 활성 상태이면 (즉, queue에 패킷이 있으면) 전체 서비스 중 $\frac{w_i}{\mathrm{\Sigma }{w}_j}$ 정도의 비율을 보장한다는 것이다. 예를 들어 각각 가중치가 1, 2, 3인 class 1, 2, 3이 존재하고, 모든 class의 queue에는 충분한 패킷이 있다고 가정해보자. 이때 가중치가 3인 class 3은 패킷을 3개 보내고, class 2에게 다음 순서를 양보한다. 다음으로 가중치가 2인 class 2는 패킷을 2개 보내고, class 1에게 다음 순서를 양보한다. 다음으로 가중치가 1인 class 1은 패킷을 1개 보내고, 다시 class 3에게 다음 순서를 양보한다. 이 과정이 충분히 반복하면 class 3은 전체 서비스 중 3/(1+2+3) 정도의 비율을 점유한다. 또한 class 2, 1도 각각 전체 서비스 중 약 2/(1+2+3), 1/(1+2+3) 정도의 비율을 점유한다. 이러한 WFQ의 추상화된 도식은 figure 6에 잘 나타나있다.