# Fairness Consideration of Scheduling for Real-Time Services in 4G Systems

Authors: Woei-Hwa Tarn; Jenhui Chen; Chun-Liang Lee
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In order to achieve higher resource utilization, the call admission control (CAC) will allow the number of connections into the system more than the system capacity can offer. However, the fairness problem will occur when these connections are real-time services. To solve this problem, in this paper, we propose a fair scheduling algorithm named contribution-based scheduling algorithm (CSA) for real-time polling service (rtPS) or guarantee bit rate (GBR) in the uplink direction in the forth-generation (4G) systems. In CSA, a mobile subscriber (MS) gains its contribution credit value at the end of each transmission time interval (TTI), which is based on the contribution of MS to the radio resource scheduling. The base station (BS) schedules the bandwidth according to the credit value. Simulation results show that CSA achieves higher fairness in bandwidth allocation while connection drop rate and queuing delay are also guaranteed as compared to the roundrobin (RR) and early deadline first (EDF) mechanisms.


---

## Body

## 1. Introduction

IMT-advanced evaluation guidelines and minimum performance requirements of fourth generation (4G) published by the International Telecommunication Union Radiocommunication Sector (ITU-R) in 2008 [1] guide the goals for outstanding systems such as IEEE 802.16m [2] and long term evolution advanced (LTE-A) [3]. In those systems, the radio resource is controlled by a base station (BS) in a centralized way; that is, the BS plays a role of resource distributor and scheduler to the mobile subscriber (MS) for uplink (UL) or downlink (DL) traffic. According to different types of applications in the media access control (MAC) layer, different scheduling service types, or called quality-of-service (QoS) classes, prioritize the radio resource allocation. Tables 1 and 2 summarize the priority order of QoS classes of IEEE 802.16m and LTE-A systems, respectively [4].Table 1
IEEE 802.16m QoS classes and priorities.
Service
Abbrev.
Priority
Definition
Typical applications
Unsolicited grant service
UGS
1
Real-time data streams comprising fixed-size data packets issued at periodic intervals
T1/E1 transport
Extended real-time polling service
ertPS
2
Real-time service flows that generate variable-sized data packets on a periodic basis
VoIP
Real-time polling service
rtPS
3
Real-time data streams comprising variable-sized data packets that are issued at periodic intervals
MPEG video
Non-real-time polling service
nrtPS
4
Delay-tolerant data streams comprising variable-sized data packets for which a minimum data rate is required
FTP with guaranteed minimum throughput
Best effort
BE
5
Data streams for which no minimum service level is required and therefore may be handled on a space-available basis
HTTPTable 2
3GPP LTE-A standardized QCI and priorities.
QCI
Priority
Resource type
Delay budget
Example services
1
2
GBR
100 ms
Conversational voice
2
4
GBR
150 ms
Conversational video (live streaming)
3
3
GBR
50 ms
Real-time gaming
4
5
GBR
300 ms
Nonconversational video (buffered streaming)
5
1
Non-GBR
100 ms
IMS signaling
6
6
Non-GBR
300 ms
Video (buffered streaming), TCP-based (e.g., www, e-mail, chat, FTP, P2P file sharing, progressive video, etc.)
7
7
Non-GBR
100 ms
Voice, video, interactive gaming
8
8
Non-GBR
300 ms
Video (buffered streaming), TCP-based (e.g., www, e-mail, chat, FTP, P2P file sharing, progressive video, etc.)
9
9
Non-GBR
300 ms
Video (buffered streaming), TCP-based (e.g., www, e-mail, chat, FTP, P2P file sharing, progressive video, etc.)In those standards, the IEEE 802.16 MAC layer provides five types of services [2]. These services are unsolicited grant service (UGS), real-time polling service (rtPS), extended real-time polling service (ertPS), non-real-time polling service (nrtPS), and best effort (BE). In contrast, the LTE-A QoS class identifier (QCI) provides the guaranteed bit rate (GBR) and non-guaranteed bit rate (non-GBR) to fit different priorities and delay budget requirements [3].According to the latest statistics report of mobile data traffic [5], global mobile data traffic grew 81% in 2013. Global mobile data traffic reached 1.5 exabytes per month at the end of 2013, up from 820 petabytes per month at the end of 2012. Since the resource of the system is limited, to avoid leading the QoS violation, the BS has to allocate the available bandwidth accurately and effectively. However, both 802.16m and LTE-A standards did not define any scheduling algorithms and left them to be implemented by individual venders [6].On the other hand, in order to achieve higher average bandwidth utilization, the call admission control (CAC) of system may allow more connections than the system can support in average to enter the system. However, too many connections may lead the peak bandwidth request to exceed the system available capacity. It is caused by the characteristics of variable bandwidth request of the services. Thus, the entrance of more connections will lead the scheduler to dilemma. In other words, to avoid the QoS violation, the scheduler has to delay some nonurgent bandwidth request when the system is saturated. As a result, the situation of QoS violation will be more and more severe; finally the result leads to unfair services among connections. In order to solve fairly scheduling problems for UL traffic, we propose a contribution-based scheduling algorithm (CSA) to give consideration to both scheduling performance and fairness in this paper. The simulation results show that CSA can improve the scheduling efficiently and reduce the dropping rate.The rest of this paper is organized as follows. A brief overview of literature relevant to our work is given in Section2. In Section 3, we describe the fundamental part of the system model. The detailed mechanism of CSA is presented in Section 4. Section 5 provides a series of simulation and presents the performance measurement results in detail. Finally, we give the conclusion and discuss some potential issues in Section 6.


## 2. Related Works

The scheduling problem for UL traffic has been broadly discussed. In [7], the authors considered a coexistence scenario in the uplink of LTE-A networks within an M2M communication and modeled the energy-efficient resource allocation problem as the maximization of bits-per-joule capacity under QoS requirements of different users. Baid et al. proposed a continuous but nondifferentiable concave reward function based on packet delays to obtain the maximum resource allocation in every TTI [8]. In [9], the authors proposed a dynamic carrier aggregation (DCA) scheduling scheme to improve the energy efficiency of uplink communications. As mentioned above we find that most of the investigations for UL scheduling mechanisms focus on the performance improvement issues such as throughput and delay requirements. However, with the development of mobile communication, the requirement of UL variable bit rate (VBR) real-time services increases rapidly. When the system bandwidth becomes saturated, the fairness of resource allocation will be a serious issue.The rtPS with VBR or GBR services are the most difficult service for the BS to deal with since the property of bandwidth requirement is variant and its service is delay sensitive. This phenomenon becomes more severe especially when the system traffic is saturated in the UL. When the system traffic is in saturated condition, only partial connections can be satisfied (i.e., their bandwidth requirements) because of the limitation of the system resources. Certainly, it will cause the problem of fairness. In recent years, many research works [10–13] contributed their efforts to proposing suitable resource scheduling algorithms for VBR real-time services. Ruby and Leung [10] proposed a few suboptimal scheduling algorithms in LTE system to allocate resource blocks (RBs) across all MSs with the help of existing work. Park [11] considered the factors in IEEE 802.16 system, such as average arrival rate, average service rate, delay constraint of each packet, and the number of packets in queue, to schedule the bandwidth in each MAC frame optimally. However, in this mechanism, each MS has to report related parameters periodically to its serving BS (SBS) in order to perform the estimation process. The frequent report will bring a heavy burden to the SBS; meanwhile, it still ignores the problem of fairness in saturated condition. Ahmed and Hamma [12] presented the fairness issue in IEEE 802.16 system when they designed the real-time bandwidth allocation mechanism. This mechanism considered the ratio of request UL bandwidth to the total UL available bandwidth in each MAC frame to determine which connection will be served first. Inevitably, this mechanism will cause starvation when the system is in saturated condition. Meanwhile, the fairness cannot be sustained any more. Abdennebi and Ghamri-Doudane [13] proposed along term reservation mechanism (LTRM) to predict the required bandwidth for real-time service by considering the parameters of average arrival rate and its polling period of each connection. However, it is not fitted in saturated condition either.As mentioned above, we summarize the following key parameters which are closely relative to the efficiency of VBR rtPS or GBR scheduling in the UL: (1) the total amount of bandwidth which is required by all connections, (2) the amount of bandwidth which is actually allocated by scheduler, and (3) the delay constraint of each connection to next buffer status report. The first parameter reflects the ratio by which the SBS can satisfy the bandwidth request of each connection. That is, if a connection does not obtain enough bandwidth which the connection requests for its transmission in a transmission time interval (TTI), that is, 1 subframe (1 ms) in LTE-A and 1 frame (5 ms) in IEEE 802.16m system, the SBS will record the connection higher contribution credit value to let the connection have higher priority to get bandwidth in the next TTI. The second parameter reflects the influence of different bandwidth utilization condition. If the system resource cannot support all of the required bandwidth, that is, the total amount of bandwidth which is required by all connections is larger than the system available resource, then the SBS will give higher contribution credit value to those connections which obtain lower satisfaction ratio of its bandwidth request. On the contrary, if the total required bandwidth is equal to or less than the system available bandwidth, the connections which obtain the same bandwidth satisfaction ratio will obtain lower contribution credit value. The third parameter reflects the urgency of remaining time to the end of polling period. When a connection is nearer to the end of polling period, it has to be given a higher contribution credit value to avoid the packets being dropped. According to the three parameters, CSA can give more contribution credits to those connections which do contribute effort to the system resource allocation in each TTI. Then, these connections will have higher priority to obtain the UL resource than those with lower contribution credit.


## 3. System Model

In order to figure out the system clearly and easily, we consider a point-to-multipoint network in LTE-A system in the following discussion. In the scenario, multiple MSs are connected to a centralized SBS. AssumeC
i is the ith UL real-time GBR connection which is allowed to enter the system by CAC to be served, where i
=
1,2
,
…
,
n, n
>
0 and n
∈
I. T
i, which is counted in TTIs, is the buffer status report (BSR) period of C
i, T
i
=
1,2
,
…
,
∞. In each BSR period, the BS gets the buffer status and resource requirement for transmission in each MS. B
i is the bandwidth requirement of connection C
i during T
i, and B
i
[
j
] denotes the remainder of bandwidth requirement which is waiting to be served in the jth TTI during T
i. We derive(1)
B
i
j
=
B
i
j
-
1
-
ϕ
i
j
-
1
,where ϕ
i
[
j
] denotes the resources which are allocated to C
i by BS in the jth TTI. For each C
i, let T
i
′
[
j
]
=
T
i
-
j
+
1 be the remaining number of TTIs during period T
i; then we have the mean value of resource where the C
i should be allocated in the jth TTI to be(2)
A
i
j
=
B
i
j
T
i
′
j
.


### 3.1. Resource Blocks

Orthogonal frequency division multiple access (OFDMA), with high spectral efficiency and low bit error rate, is adopted by both IEEE 802.16m and LTE-A standards in the PHY layer. OFDMA fragments the information to be transmitted and sends each piece in parallel on different subcarriers, which can be placed tightly and even overlap in frequency. For instance, in LTE-A system, allocation of resources, based on the channel status, is divided as RBs. According to the priority and time budget of each service requirement, the scheduler assigns these RBs to MSs dynamically. Allocation of resources is done per TTI. Physical downlink control channel (PDCCH) plays the major role in signaling resource allocation.The unit the MAC layer of LTE-A allocates for an MS is called the logical resource block (LRB) or slot. Let|
R
| be the number of LRBs by which the MS is waiting to be served in a scheduling period, let |
R
c
| be the number of clear LRBs, and let |
R
x
| be the number of unclear LRBs, respectively. The relation among R, R
c, and R
x follows R
=
R
c
+
R
x. Since the bandwidth demanded by MSs is calculated in bits, the achievable bandwidth of each LRB for different MSs depends on their corresponding adaptive modulation and coding (AMC) levels.Assume there arel different AMC levels supported in the PHY layer. The achievable AMC level depends on the received signal to interference plus noise ratio (SINR) value ψ
r
(
i
) of MS i. Let M
∈
{
1,2
,
…
,
l
} be the index of AMC levels as shown in Table 3. Let ψ
M be the minimum required SINR to achieve modulation level M. Thus the achievable AMC level for MS i, denoted by M
i, can be defined as(3)
M
i
≜
M
∣
ψ
M
≤
ψ
r
i
<
ψ
M
+
1
,where ψ
M
+
1
→
∞.Table 3
Modulation and coding parameters for OFDMA systems.
Level (M)
Modulation (coding ratec
r)
Required SINR (ψ
M)
1
QPSK (1
/
2)
5 dB
2
QPSK (3
/
4)
8 dB
3
16-QAM (1
/
2)
10.5 dB
4
16-QAM (3
/
4)
14 dB
5
64-QAM (1
/
2)
16 dB
6
64-QAM (2
/
3)
18 dB
7
64-QAM (3
/
4)
20 dBAccording toM
i, the number of bits (raw data) that one OFDMA symbol per subband, which consists of several subcarriers, can carry may vary from MS to MS. Thus, the corresponding number of bits b
i per subband for one OFDMA symbol with M
i can be written as(4)
b
i
=
F
i
X
b
M
i
c
r
,where X
∈
S is the data subcarriers for the subband; b
M
(
i
) is the bit volume function (bits per subcarrier) with M
i for C
i; and c
r is the corresponding coding rate. b
M
(
i
) depending on M
i has different values where quadrature phase-shift keying (QPSK) = 2 bits, 16-ary quadrature amplitude modulation (16-QAM) = 4 bits, and 64-QAM = 6 bits, and c
r
=
1
/
2, 2
/
3, and 3
/
4, respectively.Each LRB or slot is composed ofN
s OFDMA symbols in time domain by N
b subbands in frequency domain. Denote the resource unit by R (bits per LRB); the bandwidth of LRB for MS i can be calculated as(5)
R
i
=
N
s
N
b
b
i
=
N
s
N
b
F
i
X
b
M
i
c
r
,where N
s
=
5
,
6, or 7 for the IEEE 802.16m system and N
s
=
7 for the LTE-advanced system. Accordingly, the bandwidths of clear resource R
c
(
i
) and unclear resource R
x
(
i
) for MS i are different and can be obtained by R
c
(
i
)
=
N
s
N
b
F
i
S
c
b
M
(
i
)
c
r and R
x
(
i
)
=
N
s
N
b
F
i
S
x
b
M
(
i
)
c
r. So the available UL bandwidth B
T can be calculated as(6)
B
T
=
R
i
N
f
N
u
,where N
f is number of LRBs in a TTI and N
u is number of UL TTIs.


## 3.1. Resource Blocks

Orthogonal frequency division multiple access (OFDMA), with high spectral efficiency and low bit error rate, is adopted by both IEEE 802.16m and LTE-A standards in the PHY layer. OFDMA fragments the information to be transmitted and sends each piece in parallel on different subcarriers, which can be placed tightly and even overlap in frequency. For instance, in LTE-A system, allocation of resources, based on the channel status, is divided as RBs. According to the priority and time budget of each service requirement, the scheduler assigns these RBs to MSs dynamically. Allocation of resources is done per TTI. Physical downlink control channel (PDCCH) plays the major role in signaling resource allocation.The unit the MAC layer of LTE-A allocates for an MS is called the logical resource block (LRB) or slot. Let|
R
| be the number of LRBs by which the MS is waiting to be served in a scheduling period, let |
R
c
| be the number of clear LRBs, and let |
R
x
| be the number of unclear LRBs, respectively. The relation among R, R
c, and R
x follows R
=
R
c
+
R
x. Since the bandwidth demanded by MSs is calculated in bits, the achievable bandwidth of each LRB for different MSs depends on their corresponding adaptive modulation and coding (AMC) levels.Assume there arel different AMC levels supported in the PHY layer. The achievable AMC level depends on the received signal to interference plus noise ratio (SINR) value ψ
r
(
i
) of MS i. Let M
∈
{
1,2
,
…
,
l
} be the index of AMC levels as shown in Table 3. Let ψ
M be the minimum required SINR to achieve modulation level M. Thus the achievable AMC level for MS i, denoted by M
i, can be defined as(3)
M
i
≜
M
∣
ψ
M
≤
ψ
r
i
<
ψ
M
+
1
,where ψ
M
+
1
→
∞.Table 3
Modulation and coding parameters for OFDMA systems.
Level (M)
Modulation (coding ratec
r)
Required SINR (ψ
M)
1
QPSK (1
/
2)
5 dB
2
QPSK (3
/
4)
8 dB
3
16-QAM (1
/
2)
10.5 dB
4
16-QAM (3
/
4)
14 dB
5
64-QAM (1
/
2)
16 dB
6
64-QAM (2
/
3)
18 dB
7
64-QAM (3
/
4)
20 dBAccording toM
i, the number of bits (raw data) that one OFDMA symbol per subband, which consists of several subcarriers, can carry may vary from MS to MS. Thus, the corresponding number of bits b
i per subband for one OFDMA symbol with M
i can be written as(4)
b
i
=
F
i
X
b
M
i
c
r
,where X
∈
S is the data subcarriers for the subband; b
M
(
i
) is the bit volume function (bits per subcarrier) with M
i for C
i; and c
r is the corresponding coding rate. b
M
(
i
) depending on M
i has different values where quadrature phase-shift keying (QPSK) = 2 bits, 16-ary quadrature amplitude modulation (16-QAM) = 4 bits, and 64-QAM = 6 bits, and c
r
=
1
/
2, 2
/
3, and 3
/
4, respectively.Each LRB or slot is composed ofN
s OFDMA symbols in time domain by N
b subbands in frequency domain. Denote the resource unit by R (bits per LRB); the bandwidth of LRB for MS i can be calculated as(5)
R
i
=
N
s
N
b
b
i
=
N
s
N
b
F
i
X
b
M
i
c
r
,where N
s
=
5
,
6, or 7 for the IEEE 802.16m system and N
s
=
7 for the LTE-advanced system. Accordingly, the bandwidths of clear resource R
c
(
i
) and unclear resource R
x
(
i
) for MS i are different and can be obtained by R
c
(
i
)
=
N
s
N
b
F
i
S
c
b
M
(
i
)
c
r and R
x
(
i
)
=
N
s
N
b
F
i
S
x
b
M
(
i
)
c
r. So the available UL bandwidth B
T can be calculated as(6)
B
T
=
R
i
N
f
N
u
,where N
f is number of LRBs in a TTI and N
u is number of UL TTIs.


## 4. Contribution-Based Scheduling Algorithm (CSA)

For the design of the scheduler, there are three main objects we desire to achieve. The first one is the fairness consideration of bandwidth distribution among connections. The second one is to minimize the packet drop rate of each MS connection. The last is to maximize the resource utilization, that is, the bandwidth. When a connection of an MS is permitted to enter the system by the CAC, the scheduler has to meet the QoS requirement of these allowed connections by providing enough resource for transmission.This consequence will lead to a dilemma situation, especially when the allowed connections are VBR rtPS/GBR. This situation will become worse, especially when the system is in the saturated condition.In this paper, we take into account the efficient resource utilization as well as the fairness. It first determines the criteria that relate to the bandwidth allocation of certainC
i; then it introduces a concept namedcontribution
K to decide how the scheduler will allocate bandwidth in current TTI. When the C
i has larger contribution K
i, it will have higher priority to get bandwidth allocation.


### 4.1. Criteria of CSA

There are two important factors which are relative toK. The first factor is the available bandwidth which can be allocated to a connection in a TTI; we denote it by K
1. Since system available bandwidth in a TTI is finite, the more the bandwidth is allocated to one connection, the less the bandwidth is left to other connections. If the bandwidth is allocated to one connection more than its expected value A
i
[
j
-
1
] in the (
j
-
1
)th TTI, the K
1 of this connection will be decreased in the jth TTI, especially when the total required bandwidth of all connections is more than system provided bandwidth. The second factor is the frequency by which BS cannot satisfy the expected allocated bandwidth to one connection during a BSR period; we denote by K
2. Since the packets which are queued in buffer exceed their expired delay, these packets will violate the QoS and be dropped. Consequently, a higher value of K
2 will be added to this connection.


### 4.2. The Contribution Approach

In order to examineK in each TTI, we trace the difference of expected volume of bandwidth A
i
[
j
-
1
] and the number of TTIs by which the BS cannot satisfy the expected bandwidth in each TTI. To achieve this goal, two functions K
i
1
[
j
] and K
i
2
[
j
] of the ith connection in the jth TTI are investigated as(7)
K
i
1
j
=
A
i
j
-
A
i
j
-
1
e
10
log
⁡
⁡
B
R
/
B
T
,
(8)
K
i
2
j
=
j
T
i
-
Y
i
e
10
log
⁡
⁡
j
/
T
i
,where (
A
i
[
j
]
-
A
i
[
j
-
1
]
) means the difference of expected volume of bandwidth between the (
j
-
1
)th and the jth TTI; B
R
=
∑
i
=
1
n
A
i
j is the summation of all expected volume of bandwidth of connections in the jth TTI; and B
T is the total available bandwidth of the UL in the jth TTI obtained from (6). (
B
R
/
B
T
) is used to measure the degree of bandwidth request. The less the available system bandwidth is, the more the K
1 variation is.Y
i
=
∑
k
=
1
j
Y
i
k is the summation of Y
i
[
j
], where Y
i
[
j
] is defined as(9)
Y
i
j
=
0
,
if
A
i
j
-
A
i
j
-
1
≤
0
,
1
,
if
A
i
j
-
A
i
j
-
1
>
0
.
Y
i means the quantity of TTI in which the scheduler does not have enough bandwidth to satisfy the requirement of C
i in a BSR period. The connection which has larger Y
i will get more K
i
2. (
j
/
T
i
) is used to weigh the degree of survival BSR period; the smaller the survival BSR period to be left, the more the contribution variation the connection will obtain.Figure1(a) shows B
R versus e
10
log
⁡
⁡
B
R
/
B
T in different UL available bandwidth B
T. In the same B
R, when B
T decreases, the exponent of (7) will exponentially increase. It means that the less the system available UL bandwidth, the more valuable the bandwidth resource and then the more the influence to K
1 it has. Similarly, Figure 1(b) shows the TTI number j versus e
10
log
⁡
⁡
j
/
T
i in different BSR period T
i. When T
i decreases, the exponent of (8) will exponentially increase. It implies that the lower BSR period leaves. In other words, the BS has to increase the value of K
2 if the position of current TTI is near the tail of polling interval.Figure 1
(a) The value ofe
10
log
⁡
⁡
B
R
/
B
T variation in different bandwidth capacity B
T; (b) the value of e
10
log
⁡
⁡
j
/
T
i variation in different BSR period T
i.
(a)
(b)Figure2 shows (
A
i
[
j
]
-
A
i
[
j
-
1
]
) versus (
A
i
[
j
]
-
A
i
[
j
-
1
]
)
e
10
log
⁡
⁡
B
R
/
B
T in different B
R
/
B
T. When (
A
i
[
j
]
-
A
i
[
j
-
1
]
) is positive, the connection will obtain a positive K
1. Conversely, the connection will obtain a negative K
1. Figure 2 also reveals that when the total utilization of bandwidth (
B
R
/
B
T
) decreases, the slope of the line decreases. Then (
A
i
[
j
]
-
A
i
[
j
-
1
]
)
e
10
log
⁡
⁡
B
R
/
B
T will decrease till 0.Figure 2
The value ofK
i
(
1
) in different ratio of B
R
/
B
T.


### 4.3. Bandwidth Allocation Scheduling

According to (7) and (8), we develop an algorithm to consider both the influence of available resources and remaining BSR period time to bandwidth allocation, simultaneously. We present the procedures of CSA algorithm as follows.When the value of contribution creditK for each connection is calculated in every TTI, the connection with the largest value of K will be served first until the UL available bandwidth is exhausted. First of all, the CSA sorts all connections which are permitted to enter the system in descending order in accordance with K
1
[
j
]. The CSA divides these connections into G groups and checks group by group. When the amount of bandwidth requested in a group is less than or equal to the available bandwidth, the scheduler will satisfy all requests of connections in this group. In contrast, if the amount of bandwidth requested by the connections in a group is greater than the available bandwidth (i.e., the remaining available bandwidth is not enough for all connections in this group), it sorts the connections in the same group by K
2
[
j
] in descending order and assigns the bandwidth to connections one by one until the bandwidth is exhausted. The detailed CSA is shown in Algorithm 1.Algorithm 1:CSA.
Input:
n: number of connections; L
a: available bandwidth in a TTI; T
i: BSR period;
A
i
[
j
]: excepted bandwidth in jth TTI;
Output: Resource allocation priority of connections
(1)
for  j
=
1 to T
i
do
(2)
for  i
=
1 to n
do
(3)   Calculate K
i
(
1
)
[
j
] and K
i
(
2
)
[
j
] of each connection.
(4)   Sort all connections by K
i
(
1
)
[
j
] in descending order.
(5)   Divide the n connections into G groups.
(6)   Sort the connections again in the same group by K
i
(
2
)
[
j
] in descending order
(7)   Save the connection IDs into array sequentially.
(8)
end for
(9)
for  i
=
1 to n
do
(10)  if (L
u
<
L
a and i
<
n) then
(11)   L
u
=
L
u
+
A
i
[
j
]
(12)   Put A
i
[
j
] into scheduler
(13)  end if
(14)  end for
(15) end for


## 4.1. Criteria of CSA

There are two important factors which are relative toK. The first factor is the available bandwidth which can be allocated to a connection in a TTI; we denote it by K
1. Since system available bandwidth in a TTI is finite, the more the bandwidth is allocated to one connection, the less the bandwidth is left to other connections. If the bandwidth is allocated to one connection more than its expected value A
i
[
j
-
1
] in the (
j
-
1
)th TTI, the K
1 of this connection will be decreased in the jth TTI, especially when the total required bandwidth of all connections is more than system provided bandwidth. The second factor is the frequency by which BS cannot satisfy the expected allocated bandwidth to one connection during a BSR period; we denote by K
2. Since the packets which are queued in buffer exceed their expired delay, these packets will violate the QoS and be dropped. Consequently, a higher value of K
2 will be added to this connection.


## 4.2. The Contribution Approach

In order to examineK in each TTI, we trace the difference of expected volume of bandwidth A
i
[
j
-
1
] and the number of TTIs by which the BS cannot satisfy the expected bandwidth in each TTI. To achieve this goal, two functions K
i
1
[
j
] and K
i
2
[
j
] of the ith connection in the jth TTI are investigated as(7)
K
i
1
j
=
A
i
j
-
A
i
j
-
1
e
10
log
⁡
⁡
B
R
/
B
T
,
(8)
K
i
2
j
=
j
T
i
-
Y
i
e
10
log
⁡
⁡
j
/
T
i
,where (
A
i
[
j
]
-
A
i
[
j
-
1
]
) means the difference of expected volume of bandwidth between the (
j
-
1
)th and the jth TTI; B
R
=
∑
i
=
1
n
A
i
j is the summation of all expected volume of bandwidth of connections in the jth TTI; and B
T is the total available bandwidth of the UL in the jth TTI obtained from (6). (
B
R
/
B
T
) is used to measure the degree of bandwidth request. The less the available system bandwidth is, the more the K
1 variation is.Y
i
=
∑
k
=
1
j
Y
i
k is the summation of Y
i
[
j
], where Y
i
[
j
] is defined as(9)
Y
i
j
=
0
,
if
A
i
j
-
A
i
j
-
1
≤
0
,
1
,
if
A
i
j
-
A
i
j
-
1
>
0
.
Y
i means the quantity of TTI in which the scheduler does not have enough bandwidth to satisfy the requirement of C
i in a BSR period. The connection which has larger Y
i will get more K
i
2. (
j
/
T
i
) is used to weigh the degree of survival BSR period; the smaller the survival BSR period to be left, the more the contribution variation the connection will obtain.Figure1(a) shows B
R versus e
10
log
⁡
⁡
B
R
/
B
T in different UL available bandwidth B
T. In the same B
R, when B
T decreases, the exponent of (7) will exponentially increase. It means that the less the system available UL bandwidth, the more valuable the bandwidth resource and then the more the influence to K
1 it has. Similarly, Figure 1(b) shows the TTI number j versus e
10
log
⁡
⁡
j
/
T
i in different BSR period T
i. When T
i decreases, the exponent of (8) will exponentially increase. It implies that the lower BSR period leaves. In other words, the BS has to increase the value of K
2 if the position of current TTI is near the tail of polling interval.Figure 1
(a) The value ofe
10
log
⁡
⁡
B
R
/
B
T variation in different bandwidth capacity B
T; (b) the value of e
10
log
⁡
⁡
j
/
T
i variation in different BSR period T
i.
(a)
(b)Figure2 shows (
A
i
[
j
]
-
A
i
[
j
-
1
]
) versus (
A
i
[
j
]
-
A
i
[
j
-
1
]
)
e
10
log
⁡
⁡
B
R
/
B
T in different B
R
/
B
T. When (
A
i
[
j
]
-
A
i
[
j
-
1
]
) is positive, the connection will obtain a positive K
1. Conversely, the connection will obtain a negative K
1. Figure 2 also reveals that when the total utilization of bandwidth (
B
R
/
B
T
) decreases, the slope of the line decreases. Then (
A
i
[
j
]
-
A
i
[
j
-
1
]
)
e
10
log
⁡
⁡
B
R
/
B
T will decrease till 0.Figure 2
The value ofK
i
(
1
) in different ratio of B
R
/
B
T.


## 4.3. Bandwidth Allocation Scheduling

According to (7) and (8), we develop an algorithm to consider both the influence of available resources and remaining BSR period time to bandwidth allocation, simultaneously. We present the procedures of CSA algorithm as follows.When the value of contribution creditK for each connection is calculated in every TTI, the connection with the largest value of K will be served first until the UL available bandwidth is exhausted. First of all, the CSA sorts all connections which are permitted to enter the system in descending order in accordance with K
1
[
j
]. The CSA divides these connections into G groups and checks group by group. When the amount of bandwidth requested in a group is less than or equal to the available bandwidth, the scheduler will satisfy all requests of connections in this group. In contrast, if the amount of bandwidth requested by the connections in a group is greater than the available bandwidth (i.e., the remaining available bandwidth is not enough for all connections in this group), it sorts the connections in the same group by K
2
[
j
] in descending order and assigns the bandwidth to connections one by one until the bandwidth is exhausted. The detailed CSA is shown in Algorithm 1.Algorithm 1:CSA.
Input:
n: number of connections; L
a: available bandwidth in a TTI; T
i: BSR period;
A
i
[
j
]: excepted bandwidth in jth TTI;
Output: Resource allocation priority of connections
(1)
for  j
=
1 to T
i
do
(2)
for  i
=
1 to n
do
(3)   Calculate K
i
(
1
)
[
j
] and K
i
(
2
)
[
j
] of each connection.
(4)   Sort all connections by K
i
(
1
)
[
j
] in descending order.
(5)   Divide the n connections into G groups.
(6)   Sort the connections again in the same group by K
i
(
2
)
[
j
] in descending order
(7)   Save the connection IDs into array sequentially.
(8)
end for
(9)
for  i
=
1 to n
do
(10)  if (L
u
<
L
a and i
<
n) then
(11)   L
u
=
L
u
+
A
i
[
j
]
(12)   Put A
i
[
j
] into scheduler
(13)  end if
(14)  end for
(15) end for


## 5. Simulation Result

In order to evaluate the performance of the CSA algorithm, a simulator built by C++ programming language is constructed. The basic scheduling functions refer to the scheduler design presented in [14]. In the simulation, we compare the CSA algorithm with the round robin (RR) and early deadline first (EDF) algorithms. We set 20 concurrent connections in the LTE-A wireless networks. The service type of all connections in the simulation experiments is considered as the real-time GBR service with VBR. The entrance of connections to the system is controlled by the CAC mechanism. The bandwidth acquisition must follow the contention procedures defined in the LTE-A standard. After the allowance of connection entrance, the SBS takes a 10-TTI cyclic BSR period to serve these connections. All simulation parameters are shown in Table 4.Table 4
Simulation parameters.
Parameter
Value
System bandwidth (UL)
5 MHz
BSR period (number of TTIs)
10 (subframe)
Number of RBs in a TTI
25
Number of connections
20
Transmission time interval (TTI)
1 ms
RB bandwidth
180 KHz
BSR period
Delay constraint (frame)
Simulation time
5 minFirst, we investigate the representation of fairness among these three algorithms. The fairness degree is measured by Jain’s fairness index [15]. The formula for Jain’s fairness index is F
=
∑
i
=
1
n
s
i
2
/
(
n
∑
i
=
1
n
s
i
2
), where n is number of connections in the same class and s
i is the throughput of connection i. Figure 3 shows Jain’s fairness index under different traffic loads condition. When F is equal to 1, it indicates complete fairness. In Figure 3, the CSA has the highest fairness, overall. It is because when the remaining BSR period of C
i decreases, according to (8), it will have higher priority for compensation. In the other way, compared with CSA, EDF has the worst fairness.Figure 3
Fairness comparisons among RR, EDF, and CSA algorithms.Figure4 shows the drop rate in different traffic loads under different delay constraints. When delay constraint is small, the CSA drop rate is a little higher than EDF as shown in Figures 4(a) and 4(b). It is because CSA needs time to make response to more bandwidth requests. If the BSR period T
i is short, it cannot satisfy the required extra bandwidth of the connections immediately. In Figures 4(c) and 4(d), the drop rates of CSA and EDF are close when the delay constraint is more than 8 frames. Meanwhile, the drop rate of RR is the worst in all delay constraints.Figure 4
Drop rate in different traffic loads under different delay constraints: (a) 2 TTIs; (b) 4 TTIs; (c) 8 TTIs; (d) 16 TTIs.
(a)
T
i
=
2
(b)
T
i
=
4
(c)
T
i
=
8
(d)
T
i
=
16Figure5 shows the drop rate of RR, EDF, and CSA under different traffic loads with different bandwidth variation, respectively. From the simulation results, we find that the drop rate of RR, RDF, and CSA in Figure 5(b) all is larger than the drop rate in Figure 5(a). It conforms to the inference that when the variation of MSs bandwidth request increases, it implies the scheduler is more difficult to predict and satisfy the MSs requirement. Then the drop rate in high bandwidth variation will be larger than the drop rate in low bandwidth variation. Meanwhile, although the EDF surpasses CSA in the result, its gap is not too large (2%). When the bandwidth variation is 80% the gap decreases as the traffic load increases. This is because EDF takes the discipline of earliest deadline first. If the bandwidth variation is low, the packet, which has the smallest deadline, will be served first and have lower mean drop rate. When the bandwidth variation increases, the resource allocation cannot make response to the real condition of the data flow of MS; then the drop rate of EDF increases. This result reveals that CSA can achieve a higher fairness scheduling outcome and does not lead to a worse performance of packet drop rate.Figure 5
Drop rate in different traffic loads when bandwidth variation is (a) 20% and (b) 80%.
(a)
(b)In Figure6, we simulate the queuing delay under different traffic loads. The queuing delay of CSA is as well as EDF. It is because when the remaining BSR period of connections is smaller, the K
2 of connection will cause a higher priority. RR is still the worst performance in queuing delay. This result reveals that CSA can achieve a lower queuing delay and maintain fairness of services in each connection.Figure 6
Queuing delay in different traffic loads.


## 6. Conclusion

In order to achieve higher system resource utilization, excessive CAC may cause the system saturated condition and lead to fairness problem. In this paper, we studied several critical parameters that affect the performance of UL VBR rtPS/GBR scheduling algorithm. According to the characteristics of VBR rtPS/GBR, we proposed CSA to resolve fairness problem and keep lower packet dropping rate in saturated condition. CSA calculates the contribution creditK
i
[
j
] by considering the quantity of available bandwidth and survival BSR period to decide the priority of scheduling for connections in each TTI. The simulation results show that CSA has good scheduling efficiency as well as considers the fairness in the same time. How to simplify the calculation procedure and contribution credit may be our future work.



---

*Source: 597173-2015-05-07.xml*