Weighted round robin scheduling strategies in (E)GPRS radio interface

Published on February 2017 | Categories: Documents | Downloads: 19 | Comments: 0 | Views: 119
of 5
Download PDF   Embed   Report

Comments

Content


Weighted Round Robin Scheduling Strategies in
(E)GPRS Radio Interface
A. Kuume, A. P. Mietinen
Nokia Networks
Espoo, Finland
antti.kuume, antti.p.miettinen, [email protected]
Abstract-Different types of data services have various
requirements for delay and throughput. When a service mix
containing both delay sensitive and insensitive types of services is
offered over a shared channel, it is very beneficial to prioritize
the resource usage of each service. In this paper an analytical
model is presented for studying weighted round robin queuing in
(EDGE) General Packet Radio Service radio interface. A quickly
computable model allows a large number of service mixes to be
studied. The model yields gain achieved by prioritization in terms
of maximum carried load with given end user satisfaction
criteria. It is shown that according to the model, using weighted
round robin scheduling brings a notable increase in the
maximum carried load. However, tuning the queue weights either
based on statistical data on average mix of different services or
dynamically taking into account the current instantaneous active
connections do not increase maximum carried load significantly.
1. INTRODUCTION
The term quality of service or QoS is widely used in
literature in connection with packet switched networks. In this
paper with QoS differentiation we mean prioritization of
certain packet flows over others in the network. End user
observed QoS is refered to with the term qualit of experience,
QoE. Objective of QoS differentiation is to provide adequate,
but not excessive, QoE to all users by sharing the resources
unequally.
QoS differentiation in General Packet Radio Service
(GPRS) network (or its enhanced version, EGPRS) can be
enforced for example based on service used, current radio link
conditions, user subscription class, or a combination of these.
On service based QoS differentiation more network resources
are given to users whose application require high throughput or
low delay to reach adequate QoE. This paper considers only
service based QoS differentiation.
Weighted round robin (WRR) scheduling refers to
treatment of packets (or frames, blocks, etc.) where connection
i gets transmission tum for ni packets during a period where
total number of
(1)
packets are transmitted, where i is running over all connections
and ni is the WRR queue weight for connection i. Number of
user data bits per packet is not considered.
0-7803-8521-7/04/$20.00 © 2004 IEE 3155
The objective of this study is to examine the benefits of
QoS differentiation in (E)GPRS radio interface. Three different
services, streaming media, web browsing and messaging are
presented. With the term 'traffic mix' we refer to proportional
volumes of each service with respect to each other. Each
service has its own requirement for throughput to provide
satisfactory QoE. In a benchmark case the network does not
apply QoS differentiation. WRR scheduling is introduced as a
method to perform the prioritization. Three different strategies
for setting WRR queue weights are proposed. First strategy
('static') is to keep the queue weights fixed irrespective of the
changing traffic mix. In second strategy ('dynamic') the queue
weights are tuned based on a long-ter average traffic mix in
the network. The third strategy ('adaptive') is to tune the queue
weights according to the service types of current active
connections in the cell. The objective is to compare these three
different queue weighting strategies among each other and also
against the benchmark case. In the benchmark case there is no
prioritization in the network at all.
The rest of the paper is structured as follows. In section II
some of the earlier work on the topic is studied and an example
QoS differentiation mechanism in (E)GPRS radio interface is
briefy explained. Section III introduces the model and how it
has been used in this study. Results are explained in section IV
and finally conclusions are drawn in the last section.
II. QoS DIFFERENTIATION IN (E)GPRS RADIO INTERFACE
A. Earlier work
In [1] simulations have been run to study weighted fair
queuing in a cellular network with burst data. Users have been
divided into two distinct priority classes. It has been shown
how weighted fair queuing can effectively provide significant
differences to high and low priority users only when the
network is severely loaded. The focus in [1] is to quantif
differences in throughput that different priority classes can
achieve. The QoS differentiation has been based on user
subscription tpe, and everyone is using the same service or
application.
Uplink scheduling in GPRS has been studied in [2]. One of
the introduced methods has been round robin queuing. The
focus is not on QoS differentiation but more on overall
performance. In [3] the priorit has been based on block size.
This approach is seen to lead to improved spectral efficiency.
In both [1] and [3] the proportion of traffic volumes in different
priority classes (=traffic mix) has been fixed. Radio network
has been modeled in detail with 75 cells in [4]. Maximum load
with given user satisfaction criteria and traffic mix has been
obtained. However due to complex modeling of the radio
network and mobilit of the users has made it possible to study
only few different traffic mixes. Also in [5] QoS differentiation
with weighted round robin is studied, but the main focus in the
paper has been in balancing the resources between circuit
switched voice calls and packet switched data calls.
The aim in this study is to develop a model that is so simple
and quickly computable that it allows studying of several
traffic mixes. The aim is to find out if changing traffic mix
indicates that WRR queue weights should not be fixed but
evolving with the traffic mix. A simple model is believed to be
sufficient since only relative comparisons are made. We
estimate that effect of user mobility and protocol modeling
have only minor effects on gain achieved with different queue
weights in WRR method.
B. (E) GPRS radio interface
(E)GPRS is bound to 8 time slot structure of GSM. Each
time slot can send a radio block once every 20 ms. Number of
user bits in each block varies according to coding scheme used.
There are four coding schemes (CS-l ... CS-4) specified for
GPRS and nine modulation and coding schemes (MCS-
1 ... MCS-9) for EGPRS. The (modulation and) coding scheme
used depends generally on radio conditions. The receiver
acknowledges correctly received blocks (there is also an
unacknowledged mode of operation). Description about
(E)GPRS radio interface is presented for example in [6].
A physical connection between the sender and the receiver
is called a temporary block flow. Each TBF sharing the same
time slot take turs in transmitting their radio blocks. In case
there is no QoS differentiation in the network, two TBFs
sharing a time slot would receive one block on average once
per two block periods, i.e. once per every 40 ms. Thus the total
throughput provided by the time slot is shared equally between
the two TBFs, assuming that on average same number of
retransmission are needed and same (M)CS is used.
c. QoS diff erentiation implementation example
One possibility to implement QoS differentiation is to
prioritize some TBFs over others by giving them the
transmission tum more often. In this study it is assumed that
each TBF has associated with it a parameter called scheduling
step size (SSS), ranging from 1 to 12. After getting to transmit
a radio block, that TBF adds to its existing priority counter a
value equal to TBF's SSS. The next block period is to be used
by the TBF with the smallest priorit value. This is a WRR
scheduling system with each TBF having a weight of l/SSS,
where SSS is specific for each TBF.
Assume TBFs A and B are competing of the resources of
the same time slot, and their SSS values are 3 and 12
respectively. Then TBF A gets on average a throughput, which
is 4 times (12/3) higher than the throughput of TBF B. The
numerical throughput value depends on the total throughput
provided by the time slot. This depends on coding scheme used
and the number of retransmissions needed. Assuming the total
0-7803-8521-7/04/$20.00 © 2004 IEE 3156
throughput is 10 kbps, the throughputs would be on average 8
kbps and 2 kbps for TBFs A and B respectively.
In an arbitrary case of n TBFs sharing one time slot, and
assuming constant total throughput for the slot, a following
formula yields the throughput offered for TBF k on that slot:
1
R =
···

R
n
1
tot'
¯

;=1
···

(2)
where SSSk denotes the value of SSS parameter for TBF k
(similarly for i) and Rtot
is the total throughput provided by the
time slot. Note that R is the throughput offered by the
scheduling algorithm for TBF k. The TBF might not use all this
capacity. Thus the real throughput of the TBF k is obtained
from
R = min ¦k ,R:
ax
[ (3)
where R:
ax
is the maximum throughput usable by TBF k. The
difference between R and Rk is then available to be shared by
other TBFs, according to (2).
III. THE MODEL
A. The Model Assumptions
Assume that radio conditions are equal for all terminals.
Then given the number of TBFs sharing a time slot and their
SSS values, (2) can be used to calculate the individual
throughput for each TBF on that particular time slot. Generally
however each cell has several time slots available for GPRS
use. A terinal might be able to use for example three time
slots simultaneously.
Assume three terminals, each using three time slots in
downlink and a cell with five slots available for GPRS. Total
throughput of five time slots (Rtot) is known if we know the
(equal and stable) radio conditions of the terminals. However
the three phones using three slots each can't be divided to the
total five slots of the cell so that each TBF would be in equal
position. In this example one TBF gets necessarily allocated to
time slots, which are all shared between some other TBF. The
two other TBFs get one slot of their own. Fig. 1 illustrates the
fairest allocation. TBFs 1 and 3 both get one slot of their own
while TBF 2 shares all its slots with at least one other TBF. In
an example like this, (2) would have to be applied individually
for each time slot. Then the contribution of each slot to the
throughput of every TBF would be summed up.
Figure l . Example allocation of TBFs 1, 2 ad 3 to five time slots.
It requires some computation to actually allocate the time
slots for each TBF and apply (2) separately for each slot. In a
real network implementation the time slots chosen generally
depends on several issues. Also reallocations can be made
periodically or in an event based manner. In the model this
issue is omitted and the error in the throughputs is accepted. In
(2) Rtot
is simply taken to be the total bit rate of the cell.
B. Trafc and User Satisfaction
Number of terinals is given as an input to the model. Each
terminal in the network is using either streaming media,
browsing or messaging service. Streaming media service is one
where user chooses typically a video clip from a server in a
network. The clip is sent to the user, and viewed during the
transmission. In this study the media encoding rate is assumed
to be constant 20 kbps. Browsing service is assumed to be web
surfing tpe of service. User is downloading content from the
Interet, but due to snapshot nature (passing of time is not
modeled) of the model there is no need to take into account file
or reading time length. Browsing service is simply assumed to
require a certain throughput in order to not to make user
annoyed by delays in page download. Finally messaging
service is one where users send messages or e-mails where
time is not a critical factor.
The three services have different required throughput in
order to achieve satisfactory QoE for the user. For streaming
service the required throughput is 20 kbps based on the media
encoding rate. It is also the maximum throughput taken by one
streaming TBF no matter how much capacity is available. For
browsing service the definition of minimum throughput giving
acceptable QoE is difficult to define. Thus several values are
used. They are listed in section IV. Messaging service is
assumed to be such where throughput does not significantly
impact the QoE. Therefore the minimum throughput is set to 2
kbps, as this is assumed to be sufficient for example to avoid
problems with retransmissions on higher layer protocols, such
as Tep (transmission control protocol). Maximum throughput
with both browsing and messaging service is set to 30 kbps.
Mobile terminals are assumed to be capable to use maximum
three time slots in downlink direction, and one slot is assumed
to provide the throughput of 10 kbps (without EGPRS).
On network level it is required that within each of the three
service classes, at least 90% of the users have to meet the
throughput criterion. Otherwise it is considered that the
network level qualit is unacceptable and there were too many
users in the network.
Traffic mix in the network refers to portions of streaming,
browsing and messaging users in the network, denoted with V S,
VB and VM respectively. Multiple traffic mixes are tested to see
if they impact the optimal values for SSS parameters of each
service class. Given the total number of users in the network
Niol and the traffic mix, the total number of users in the
network within each service class is obtained with
N
i = rou
n
dVN
tot ·
,
i E ¦s.:¦ ( 4)
where round means taking closest integer value, S refers to
streaming, B to browsing and M to messaging users. Since
V
i
represent portions of all users, it holds that
0-7803-8521-7/04/$20.00 © 2004 IEE 3157
(5)
C. The Model
The network consists of Ne identical cells, each having six
time slots for GPRS use. As one slot is assumed to provide
constant throughput of 10 kbps, each cell offers a throughput of
60 kbps (without EGPRS). A probability for a user to connect
to a particular cell is equal for all cells and is noted with p.
Since all users are connected to some cell, p is obtained with
1
p= -.
Ne
(6)
F or each cell the number of streaming users follows the
binomial distribution
(7)
The number of streaming users in a cell is independent of
number of browsing or messaging users. Thus the probabilit
of having ns streaming, nB browsing and nM messaging users in
a cell is given by
where Ns, NB and N M are total number of streaming, browsing
and messaging users in the network and p is the probabilit of a
call to be located in one particular cell as defined in (6).
Once the probabilit of each call combination for a cell is
known, the expected value of happy users within each service
class in the cell can be calculated. As the cells are identical, the
expected number of satisfied users in the network is obtained
simply by multiplying with number of cells. Thus
h
i
=
Ne ¯
PnS,nB,nM ·· ,
{(nS.nB.nM llR,2R,min}
(9)
where hi, i E ¦s . : ¦refers to expected number of happy
users within any service class, Ne is the number of cells in the
network, P is as defined in (8), Ri denotes the throughput of
service class i calculated with (3),
R
min
is the chosen minimum
throughput for service class i that provides adequate QoE and
ni refers to either ns, nB or nM-
Portion of satisfied users Si within service class i is given by
iE ¦s.:¦
It is required that
> min
= 090
Si -Si
. Vi
(10)
(11)
for all three service classes, streaming, browsing and
messaging. It is assumed that any service having too low user
satisfaction rate is not widely accepted by users. Thus the
requirement for high enough satisfaction rate is independent for
each service class.
To further clarif the model, all the input parameters are
listed in Table 1. With a given set of input values, the output of
the model is either 'positive' or 'negative', depending on
whether condition specified by (11) is true or not,
corespondingly. Positive result indicates that the network level
quality was within acceptable limits. If negative result is
obtained, Ntot
is decreased and the model recalculated, until
positive result is received. Maximum value of
Ntot
that still
gives positive result is called the maximum load of the network
with all other inputs fixed, Nmo. Maximum load can be found
out for all scheduling strategies, i.e. all feasible values of SSSB
(based on work done in [4] it is evident that SSSs can be
always fixed to best priority, 1, and SSSM to worst priority, 12).
Since there are only 12 feasible values for SSSB, brute force
method is used to find out the value giving highest maximum
load. SSSB can be constrained to have identical value in all the
cells in the network. It can be further constrained to have
identical value over all traffic mixes. When such constraints are
used, they are noted in connection with results. The value of
SSSB that maximizes Nmo is called optimal SSSB.
IV. RESULTS
In this study the optimal SSSB is searched for all points on a
grid in the space spanned by Vs, VB and VM- Distance between
the grid points has been 0.05 (i.e. 5% step). Note that due to
constraint given by (5), this space is two-dimensional only. The
grid is referred to as 'all traffic mixes' further in the text.
TALE!. INUT PARATERS FOR THE MODEL.
Symbol Value Explanation
R
mi
n
s
20 kbps Min acceptable throughput for streaming
R
m
ax
s
20 kbps Max throughput used by streaming TBF
R
mi
n
Varies Min acceptable throughput for browsing
B
R
m
ax
B
30 kbps Max throughput used by browsing TBF
R
mi
n
M
2 kbps Min acceptable througput for messaging
R
m
ax
M
30 kbps Max througput used by messaging TBF
R
tot
10 kbps Throughput provided by one cell
Ntot
Varies Total number of users (TBFs)
V
s Varies Portion of streaming users (TBFs)
V
B Varies Portion of browsing users (TBFs)
V
M Varies Portion of messaging users (TBFs)
SSSs 1 Scheduling step size for streaming TBF s
SSSB Varies Scheduling step size for browsing TBF s
SSSM 12 Scheduling ste size for messaging TBF s
p
11300 Probabilit of a call in any single cell
S
m
in
0.90 Mu network level satisfaction level
0-7803-8521-7/04/$20.00 © 2004 IEE 3158
Traffic mix with x % margin refers to all traffic mIxes
where such points are removed where
V
i < x/lOO (12)
for any iE {S,B,M}.
The grid in the space sPamled by V s, VB and V M can be
represented in a triangle form as shown in Fig. 2. Each service
tpe has its own vertex where the 100% of the trafic belongs
to that particular service tpe. Starting from the vertex, the
portion of the traffc tpe in the trafic mix is decreasing along
the line from the vertex to the mid point of the opposing edge.
Fig. 2 shows the optimal SSSB values for all traffc mixes with
5% grid and R;
i
n
fxed to 10 kbps. Additionally in the results
shown by Fig. 2 SSSB is constrained to have identical value in
all the cells in the netork.
From Fig. 2 it can be seen that highest values (worst
priorit) for SSSB are on the area where there are about 25% to
40% of streaming traffc and more browsing users than
messaging. Low SSSB is optimal when there is only little
streaming or browsing trafic is present. This indicates that
browsing traffc can have relatively good priorit when there is
no real competition between streaming and browsing service
tpes due to small presence of either tpe. When there are
significant portion of both trafc tpes, then browsing priorit
has to yield to make room for streaming.
Nmo is obtained for each traffc mix. Value of Nmo depends
on constraints set on SSSB. Four different prioritization
strategies are studied in this paper. In the benchmark scenario
there is no diferentiation at all, so that each service receives
equal treatment. We call static diferentiation strategy the case
where SSSs and SSSM are set according to Table I, and SSSB is
optimized to maximize Nmo but is constrained to single value
in all cells and all trafic mixes. It corresponds to real network
situation where SSS values a used but they are on the BSC
level and cannot be set on cell-by-cell basis. Furthermore SSS
values are kept fxed irrespective of the average traffc mix in
the network.
Dynamic diferentiation stategy difers from static one in
that SSSB is individually optimized for each traffc mix. Still it
is constrained to have an equal value in all cells of the network,
but this value is changed as trafic mix changes in the network.
Finally in adaptive diferentiation strategy, SSSB is optimized
individually for each cell. In real network it coresponds to a
case where SSS values are automatically optimized on cell
level every time a new TBF is set up on the cell or an existing
one leaves.
TALE I. SET OF FOUR TRAFFIC MXS, NAD 'EVOLUTION'.
Service M 1 M 2 Mx 3 M 4
Staming 10% 15% 20% 25%
Browsing 40% 45% 50% 50%
Messgng 50% 40% 30% 25%
Nma is specifc for each traffc mix. Therefore when
evaluating how much do aforementioned four priortization
strategies make diference to Nma , we have to consider some
particular traffc mix or rather a combination of several. Table
III presents the gain in Nma in percents from using different
differentiation strategies compared to benchmark scenario.
Gain of 100% means that double trafc compared to
benchmark was caried with the same end user qualit crteria.
The gains are listed for different values of Ry
i
n
and for four
different trafic mix combinations. Trafic mix combinations
are defned by margin as exlained in connection with (12),
except for trafic mix combination called 'Evolution'. I is a set
of four tfc mixes, listed in Table II. It represents a fctive
evolution path where portion of streaming and browsing traffc
tpes increase and portion of messaging decreases.
The results in Table III show that the load of the ()GPRS
netork can be increased significantly while maintaining
identical end user experience when service differentiation is
introduced. The gains from static differentiation strategy var
from 80% to 211%, depending on Ry
i
n
and on which trafc
mixes the results are averaged over. Gains from dynamic and
adaptive strategies compared to benchmark case of not
differentiation are very close to the gain from the static
differentiation strategy. This means that the beneft from these
more complex strategies is very marginal. The values are listed
with GPRS assumptions, but due to simplicit of the model the
results are similar with EGPRS assumptions (Rtot 30 kbps etc.).
In Table III lower value of Ry
i
n
always yields larger
gains, since this allows browsing trafic to be treated with
lower priorit (higher SSS), thus leaving more resources for
streaming and background services. Increasing margin
decreases the gain with all differentiation strategies. This is due
to fact that traffc mixes with very large portion of messaging
service can lead to extremely high gains. Increasing margin
leaves these extreme cases out thus decreasing the gain.
TABLE II GAI FROM THREE QoS DIFFERENTIATION STRATEGIS.
R y
i
n
[kbps]
Static Dynamic Adaptive
margin [%] SSSB [%] [%] [%]
6 0 6 163 166 178
6 5 6 137 138 145
6 10 8 112 113 114
6 'Evolution' 7 211 212 220
10 0 3 120 123 127
10 5 4 107 109 112
10 10 4 95 96 99
10 'Evolution' 4 162 165 172
12 0 3 98 101 108
12 5 3 88 89 96
12 10 3 80 81 87
12 'Evolution' 3 121 121 134
8-12 0 3 115 117 -
8-12 5 3 102 104
-
8-12 10 4 91 93 -
8-12 'Evolution' 3 151 154
-
0-7803-8521-7/04/$20.00 © 2004 IEE 3159
Figure 2. Optimal SSSB with Ry
i
n
� 10 kbit/s
V. CONCLUSIONS
In this study we derved a model to estimate the qualit of
end user exerence in ()GPRS network with a given load and
trafic mix. Three distinct tpes of service were used;
Streaming video, web browsing and messaging. A weighted
round robin (WR) scheduling algorithm where priorit of the
connection depends on the service was presented. Three
diferent strategies to set the WR weights were compared.
The derived model was used to evaluate the gain achieved with
the three strategies in terms of caried load at a given qualit of
end user experience. Benchmark scenaro was the same
network with no prioritization, where each user had an equal
priorit independent of the service used. The results showed
that the simplest (static) WR strategy allowed roughly tice
the load of the benchmark scenario to be caried in the netork
with equal end user exerience. More complex WRstrategies
showed only marginal further improvement compared to the
simple strategy.
REFERENCES
[1] Z. Jiang, Chang L. F., Shankaranarayanan N. K., "Providing multiple
service classes for bursty data trafic in cellular networks", IEEE
Infocom, 2000, pp. 1087-1096.
[2] W. Ajib and P. Godlewski, "Service disciplines performance for WWW
trafic in GPRS system," 3G Communication technologies, 2000, IEE
Conference publication No. 471, pp. 431-435.
[3] D. Todinca, P. Perry and J. Murphy, "Novel prioritised EGPRS medium
access regime for reduced file transfer delay during congested periods,"
3G Communication technologies, 8-10 May 2002, IEE Conference
publication No. 489, pp. 550-554.
[4] A. Kuure, R. Sanchez, D. Ferandez, "Service Based Prioritization in
(E)GPRS Radio Interface", IEEE VTC fall 2004 [in press].
[5] C. Lindemann, A. Thiimmler, "Evaluating the GPRS radio interface for
different quality of service profiles", Proc. 12th GIITG Fachtagung
kommunikation in verteilten systemen, Hamburg, Germany, Feb 2001,
pp. 291-30l .
[6] T. Halonen, J. Romero, J. Melero, (ed.) "GSM, GPRS and EDGE
performance", John Wiley & Sons, 2002, ISBN 0470 84457 4.

Sponsor Documents

Or use your account on DocShare.tips

Hide

Forgot your password?

Or register your new account on DocShare.tips

Hide

Lost your password? Please enter your email address. You will receive a link to create a new password.

Back to log-in

Close