[논문 리뷰] Qualcomm에서 사용하는 Proportional-Fair Scheduler

제목: Data throughput of CDMA-HDR a high efficiency-high data rate personal communication wireless system [2000]

저자: A. Jalali, R. Padovani, R. Pankaj

논문 링크: https://ieeexplore.ieee.org/document/851593

---

Qualcomm의 HDR에서 사용되는 스케줄러에 대한 소개에 대한 논문.

PFS에 초점을 맞출 것이기 때문에, 스케줄러 관련한 부분만 해석하고 공부를 해보도록 하겠다.

 

목표

해당 논문에선 퀄콤에서 사용하는 고속 데이터 전송률 무선 액세스 시스템의 순방향 링크 데이터 처리량 성능을 제안한다.

(시스템은 스케줄러로 볼 수 있고, 해당 논문은 이 스케줄러의 자랑을 하는 것)

여기서 말하는 시스템(스케줄러)의 프로세스
1. 데이터는 TDM 방식으로 서로 다른 액세스 단말기(Access Terminals, AT)로 전송.
(각 단말기로 전송되는 속도는 가변적이며 각 AT의 측정된 SINR에 따라 달라진다)
2. AT는 가장 높은 데이터 전송률의 인덱스를 AP에게 전송.
3. AP의 스케줄러는 단말기로부터 온 데이터 속도 요청과 각 단말기에 이미 전송된 데이터 양을 기반으로 다음 단말기를 결정.

 

 

스케줄러

Terminology

DRC: 주어진 슬롯에서 모바일이 요청한 속도
R: 적절한 크기의 창에서 모바일이 수신한 평균 속도

 

설명

스케줄러는 AT가 강한 신호 레벨을 보이는 시간대에 AT에 전송을 예약하여 채널의 시간적 변화를 활용함.

스케줄러는 DRC/R이 가장 높은 모바일로 데이터를 전송하게 된다.

즉, DRC (AT가 요청하는 속도)가 크고, R (AT가 최근에 받은 데이터량)가 작은 노드를 선정해서 보낸다는 것이다.

이렇게 되면 DRC/R의 비율은 사용자가 최근 받은 속도에 비해 현재 얼마나 많은 데이터를 요청하고 있는지를 의미함.

 

이렇게 DRC/R이 높은 모바일로 데이터를 전송하면, 각 사용자는 최근 요청과 비교하여 요청 속도가 피크에 가까운 슬롯에서 서비스를 제공받게 된다.

 

예시를 들어보도록 하자.

N개의 AT가 있다고 가정한다.

 

이때 t_c는 평균 속도를 계산하는 시간 창이다.

 

이때 R_i(t)와 현재 전송 속도를 비교해야 함.

R_i(t)는 평균 전송 속도로, 사용자가 일정 기간 동안 평균적으로 받은 데이터 속도를 의미한다.

반면 현재 전송 속도는 특정 시간 슬롯에서 사용자가 실제로 받은 데이터 전송 속도를 의미한다.

차이를 알겠는가

 

논의

이 HDR 스케줄러를 쓰면 Proportional Fairness(비례적 공정성)을 보장할 수 있다.

 

비례적 공정성이란? (논문에서 써진 말이 좀 어려운 것 같아서 한 성분씩 잘라가며 해석해보겠다.

 

The scheduler used for HDR provides fairness in the following sense.
If we use another scheduling algorithm to increase the throughput of a specific user by x% over what that user receives under the HDR scheduling algorithm, the summation of a11 the percentage decreases suffered by the throughputs of all the other users under the new algorithm will be more than x%. This is known as the proportional fairness criteria [4].

 

만약 다른 스케줄링 알고리즘을 써서,

특정 사용자의 throughput을 (HDR 스케줄링 알고리즘이 제공하는 속도보다) x%만큼 증가시킨다면,

해당 알고리즘에서 다른 모든 사용자의 전송 속도 감소분의 합이 x%보다 클 것이다!

 

다른 말로 정리하자면, 어떤 특정 노드의 처리량을 효율 좋게 만들더라도 다른 노드들은 그 효율량보다 결과론적으론 더 큰 손해를 볼 것이라는 뜻!

이것을 우리는 Proportional-Fairness criteria(비례적 공정성의 기준)라고 부른다.

이렇게 된다면, Proportional-Fairness가 지켜지지 않은 것이고 이렇게 되지 않으면 Proportional-Fairness를 유지하는 것임.

 

우리가 사용하려고 하는 PFS는 이 비례적 공정성을 유지하려고 하는 것이 목표이다.

즉, 한 사용자의 이익을 위해 다른 사용자들이 너무 많은 손해를 보지 않도록 하는 것이다.

 

결과

PF Schedular vs Round Robin (RR) Schedular

 

1. 사용자 수에 따른 스케줄러 비교

PFS에서는 셀 내의 AT(Access Terminal, 즉 사용자 단말)의 수가 증가함에 따라 전송 속도가 꾸준히 증가하는 모습.

이는 사용자 다이버시티(사용자 다양성) 때문이다. 즉, PFS는 각 사용자의 요청 속도가 평균 속도보다 높아질 때 데이터를 전송하는데, 더 많은 사용자가 있을수록 이 조건을 만족할 확률이 높아지는 것이다.

반면, RRS는 모든 사용자에게 동일한 시간만큼 자원을 배분하기 때문에, 사용자 수가 많아져도 비례적 공정성 스케줄러만큼 효율적이지 않다.

 

2. 안테나 수에 따른 PFS 성능 비교

PFS는 1개의 안테나를 사용할 때 사용자가 많아질수록 전송 속도가 증가하지만 (460 kbps -> 690 kbps, 대략 50% 증가), 2개의 안테나를 사용할 땐 920 kbps -> 1.18 Mbps로 28%정도밖에 증가하지 않았음.

왜냐하면 2개 안테나를 사용할 때는 이미 높은 전송 속도를 갖고 있어 추가적인 사용자 수 증가로 인한 이득이 상대적으로 작기 때문.

 

 

최종 정리 해보자면,

 

• PFS는 사용자 수가 많아질수록 RRS보다 더 나은 성능을 보여주며, 이는 사용자 다이버시티 덕분입니다.
• 1개의 안테나를 사용할 때는 PFS의 사용자 수 증가에 따른 성능 향상 비율이 더 크고, 2개의 안테나에서는 그 비율이 다소 낮습니다.