[논문 리뷰] Generalized Proportional Fair Scheduling in Third Generation Wireless Data Networks

"Proportional Fair Scheduling이 무엇인지 이해하는 것에 focus"

 

#1. Generalized Proportional Fair Scheduling in Third Generation Wireless Data Networks

 

Abstract

3G 데이터 네트워크에서 네트워크 사업자는 사용자에게 공정한 방식으로 서비스를 제공하면서 시스템 처리량의 균형을 맞추고자 합니다. 이를 위해 비례 공정성이라는 개념을 사용합니다. 하지만 지금까지는 각 기지국마다 독립적으로 비례 공정성을 적용했습니다. 

이러한 접근 방식은 네트워크 전체를 고려할 때 파레토 최적이 아닌 대역폭 배치를 초래할 수 있습니다. 따라서 일반화된 비례 공정성 목표를 최적화하여 기지국에 대한 사용자 연결을 관리하는 네트워크 전반의 맥락에서 비례 공정성을 고려하는 것이 중요합니다. 이 논문에서는 이 문제를 공식화하고 엄격하게 연구하는 첫 번째 단계를 밟습니다. 일반적인 문제는 NP-하드이며 최적에 가까운 해를 구하는 것 또한 어렵다는 것을 보여줍니다. 그런 다음 다중 사용자 다양성이 함께 예약된 사용자 수에만 의존하는 특수한 경우를 고려합니다. 이 문제를 해결하기 위해 효율적인 오프라인 최적 알고리즘과 휴리스틱 기반의 탐욕스러운 온라인 알고리즘을 제안합니다. 미국 대형 서비스 제공업체의 기지국 배치를 기반으로 한 상세한 시뮬레이션을 통해 기존 사용자의 연관성을 변경하지 않고 일반화된 비례 공정성 목표를 가장 많이 개선하는 기지국에 신규 사용자를 할당하는 간단한 온라인 알고리즘이 오프라인 최적 솔루션에 매우 가깝다는 것을 보여줍니다. Greedy Algorithm은 신호 강도가 가장 좋은 기지국에 사용자를 할당하는 방식에 비해 이질적인 사용자 분포에서 훨씬 더 나은 처리량과 공정성을 달성할 수 있습니다. 

 

Introduction

3세대 무선 데이터 네트워크에서는 여러 사용자 간의 다운링크 흐름을 예약하기 위해 기지국에서 비례 공정(PF) 스케줄링[4]이 사용됩니다.

 

Proportional fair은 채널 상태 기반 스케줄링 알고리즘으로, 사용자 다양성 활용이라는 개념에 의존합니다.

무선 채널을 공유하는 활성 사용자가 있고 각 사용자가 보는 채널 상태가 독립적으로 달라지는 모델을 생각해 보세요.

채널 상태가 좋으면 데이터 전송률이 높아지고 그 반대의 경우도 마찬가지입니다.

각 사용자는 측정된 채널 상태를 기지국에 있는 중앙 집중식 PF 스케줄러로 지속적으로 전송합니다.

채널 측정 피드백 지연이 채널 속도 변동에 비해 상대적으로 작으면 (channel measurement feedback delay < channel rate variation = 채널 측정 피드백이 채널 속도 변동에 비해 더 빨리 일어난다면), 스케줄러는 사용자에게 전송할 패킷을 예약할 때 모든 사용자의 채널 상태를 충분히 추정할 수 있습니다. (당연하지, 채널 측정을 훨씬 전에 알 수 있으니까)

채널 상태는 사용자마다 독립적으로 변하기 때문에 PF는 서로 다른 시간대에 전송하기에 가장 좋은 상태를 가진 사용자를 선택함으로써 사용자 다양성을 활용합니다.

이 접근 방식은 라운드 로빈 스케줄러에 비해 시스템 처리량을 크게 늘릴 수 있습니다. 그러나 이러한 전송률 극대화 방식은 매우 불공평할 수 있으며 채널 상태가 상대적으로 좋지 않은 사용자는 고갈될 수 있습니다. 따라서 PF에서 사용되는 메커니즘은 사용자가 현재 달성할 수 있는 속도에 사용자가 받은 평균 속도에 가중치를 부여하는 것입니다. 

(Hence, the mechanism used in PF is to weight the current rate achievable by a user by the average rate received by a user.)

 

구체적으로, 각 시간 슬롯(EV-DO에서는 1.67ms마다)에서 PF 스케줄러의 결정은 사용자가 달성할 수 있는 속도가 가장 큰 사용자를 스케줄링하는 것이며, 사용자의 평균 속도는 입니다. 평균 속도는 일정 시간 동안 이동 평균으로 계산됩니다: => ???

 

해석본이 개떡같아서 다시 설명하자면, PF 스케줄러는 user with the largest max_i R_i/A_i를 schedule하는 것이다.

R_i = rate achievable by user i. (user i가 가능한 rate)

A_i = average rate of user i. (user i의 평균 rate)

이걸 가장 크게 한다?

가능한 rate는 평균 rate보다 상대적으로 엄청 크게 만드는 것!

 

average rate 계산 방법

 PF 스케줄링은 높은 처리량을 달성하고 기지국의 모든 사용자 간에 비례적인 공정성을 유지하지만, 오늘날 네트워크에서 모바일 디바이스와 기지국 간의 연결은 공정성을 고려하지 않습니다. 대신, 모바일 디바이스는 단순히 가장 강력한 시그널을 수신하는 기지국에 연결됩니다. 이러한 연결 알고리즘은 일부 '핫스팟' 기지국의 부하가 과중한 반면 주변 기지국의 부하가 가벼운 부하 불균형을 초래할 수 있습니다. 또한 이러한 불균형은 전체 처리량을 감소시킬 뿐만 아니라 인접한 기지국의 사용자 간의 공정성을 떨어뜨립니다. 실제로 이러한 접근 방식은 네트워크 전체를 고려할 때 파레토 최적이 아닌 대역폭 할당을 초래할 수 있습니다. 

 

이 백서에서는 공정한 스케줄링 알고리즘이 네트워크 전반을 고려하고 기지국 네트워크에 연결된 모든 사용자 간의 공정성을 지원해야 한다는 전제에서 출발합니다. 이를 위해 공정성에 대한 보다 거시적인 관점을 취하고 기지국 네트워크에 연결된 모든 사용자에게 공정성을 제공하기 위한 전체 전략의 일부로 사용자를 기지국에 할당하는 일반화된 비례 공정성(GPF) 문제를 공식화합니다. 일반적인 문제는 NP-하드이며 최적에 가까운 해를 구하는 것도 어렵다는 것을 보여줍니다. 그런 다음 다중 사용자 다양성이 함께 예약된 사용자 수에만 의존하고 모든 사용자가 동일한 우선순위를 갖는 특수한 경우를 대략적으로 고려합니다. 이 문제를 해결하기 위해 효율적인 오프라인 최적 알고리즘과 휴리스틱 기반의 탐욕스러운 온라인 알고리즘을 제안합니다. 미국 대형 서비스 제공업체의 기지국 배치를 기반으로 한 상세한 시뮬레이션을 통해 기존 사용자의 연관성을 변경하지 않고 일반화된 비례 공정성 목표를 가장 많이 개선하는 기지국에 새로 도착한 사용자를 할당하는 간단한 온라인 알고리즘이 오프라인 최적 솔루션에 매우 가깝다는 것을 보여줍니다. 욕심 알고리즘은 사용자가 고르게 분포되지 않은 많은 경우에 신호 강도가 가장 좋은 기지국에 사용자를 할당하는 접근 방식에 비해 처리량과 공정성을 현저히 개선할 수 있습니다. 또한 예상대로 최대-최소 공정성은 각 사용자의 관점에서 공정성을 위해 전체 처리량을 너무 많이 희생(알고리즘이 달성하는 처리량의 60% 미만)하는 것으로 나타났습니다. 

 

이 백서의 나머지 부분은 다음과 같이 구성되어 있습니다. 섹션 II에서는 일반화된 비례 공정성에 대한 동기를 제시하고 시스템 모델을 설명합니다. 섹션 III에서는 일반화된 비례 공정성 문제에 대한 엄격한 공식화를 제시하고 일반적인 문제가 NP-하드이며 최적에 가까운 해를 구하는 것도 어렵다는 것을 보여줍니다. 섹션 IV에서는 오프라인 최적 알고리즘과 온라인 탐욕 알고리즘의 세부 사항을 소개합니다. 섹션 VI에서는 시뮬레이션을 통해 알고리즘에 대한 자세한 평가를 제시합니다. 섹션 VII에서는 관련 작업을 소개합니다. 마지막으로, 섹션 VIII에서는 향후 작업에 대한 논의와 함께 결론을 제시합니다.