Problem statement [Under Telecom > Base station scheduling]
Background
Take GPRS, UMTS, LTE, WiMAX/802.16 or possibly any other packet based bearer services - where resources are limited and are to be shared, the question that standards and specifications don't answer is "How are the allocations to be made ?" or "Which resource should go to which user at certain point in time ?" !! Specification do specifiy the way resources are arranged and protocols for managing (allocation & deallocation) these resources, but it is left to the implementor to design appropriate "logic", "method" or "algorithm" to decide dynamic allocations.
Allocation functions are (usually) implemented in base station (BSS in GPRS, RNC in UMTS, eNB in LTE). In this article, we will analyse these functions and come out with a generic design of scheduler in base station based on certain assumptions.
Introduction
Even though resource allocation logic is not mentioned in standards, standards do mention possible classes of services or types of bearers that can be or are to be supported. Best example would be IEEE 802.16 standard. 802.16 (Elements of 802.16 - 2) specifiy 5 types of allocations. These types are rightly called "scheduling mechanisms"; even though each type is capable of supporting bearer for particular service or application, when implemented in base station, it is basically a scheduling mechanism !! For example, 802.16 UGS (Unsolicited Grant Service) supposed to provide "periodic" and "fixed" allocations. This service is suitable for constant bit rate services like voice call, video call (without any compression or silent suppresion intelligence). So to support this service, 802.16 base station has to implement scheduling methods for fixed and periodic allocations.
Another example is UMTS which calls it "bearer service". UMTS goes a step ahead by distinguising between end-to-end service (called Teleservice) and bearer service. Refer article UMTS - Services for more details. Here bearer service is specified in terms of certain parameters, called "QoS parameters". The QoS parameter of our importance is "Traffic Class". UMTS specifies four traffic classes - Conversational, Streaming, Interactive, and Background. Conversational class maps to UGS in 802.16.
This separation of bearer services in terms of classes or services helps scheduling mechanisms by limiting the possible combinations of allocation requests. We will see more of it later.
To bring completeness to above examples, let us mention how LTE specifies it. In LTE, a QoS parameter called QCI distinguishes betweens types of bearers. QCI range from 1 thru 9 (1. Conversational Voice, 2. Conversation Video or live streaming, 3. Real time gaming, 4. Non-conversational Video or buffered streaming, 5. IMS/Network signaling, 6-9. Voice/Video over TCP/email/chat/ftp/interactive gaming). At the same time, LTE considers QCI 1 thru 4 as bearers requiring Guaranteed Bit Rate (GBR). Rest of it are considered of Non-GBR type. Refer 3GPP TS 36.300:13, 23.401:4..7.3, and 23.203:6.1.7 to understand more about LTE bearer services.
Problem statement
A resource is a smallest block of medium that can be allocated. The resources are mostly arranged in grid structure of time and frequency, e.g. DL/UL maps in 802.16 (WiMAX - Elements of 802.16-1) or PHY structure in LTE (LTE - basic PHY structure). For our analysis, we will consider resource as a "bucket" that can be allocated to a user and we will take a simplified view of "bucket queue" as below:
A bucket is supposed to be able to carry data and it can hold various kinds of data. The amount of data that can be put in depend on kind of data. But in time, bucket size is assumed to be constant for all buckets. In wireless world, we can think of bucket as certain frequency-time resource that would be used to carry certain number of bits (data) depending on modulation technique (kind of data). As of now, we will not consider "kind of data" in our scheduler design and assume that all buckets can carry only one kind of data. That means all buckets can carry same amount of data in certain Δt time.
Next element is "service class" or "bearer class". We will take a simple case of two classes of services: one requiring constant data rate (let's call it CR) and the other requiring variable data rate (let's call it VR). For VR, we will assume zero minimum guaranted data rate and no bound on maximum data rate. Similarly, for CR, we will assume that maximum rate that can be requested for a CR bearer is well below the capacity i.e. CRMAX « (amount of data in a bucket/Δt). Also, we will assume that no upper limit has been set on percentage capacity that can be allocated to a particular bearer class. This assumption may lead to hogging of resources by certain class of bearers; we will analyse such scnenarios later in our discussion.
We will also add third class of bearers: high priority variable rate data (let's call it HPVR). You can think of HPVR as carrying signaling data (which of course has highest priority).
So the problem statement is to dynamically allocate buckets to users so that:
1. Number of buckets that goes unallocated which can otherwise be allocated to user over a certain duration T (» Δt) are to be minimal - zero in ideal case.
2. Service requirements for all users are satisfied (till the extent possible) assuming aggregate requirements does not exceed the capacity.
| Copyright © Samir Amberkar 2010-11 | § |
| . | Base Station Scheduling Index | » Incremental solution - 1 |