[e2e] Detlef and Opportunistic Scheudling. was: Re: Once again: Detlef and Latencies :-)
detlef.bosau at web.de
Fri Jan 11 05:06:48 PST 2008
There were lots of mistakes in my plots, but I think finally got it fixed.
For my system model, I refer to the Eurane website
I don´t only use their system model but their code as well and in case,
I tell anything about my system modell and the Eurane programmers tell
something else, they are presumably correct :-)
The Eurane code provides a simplified HSDPA simulator and therefore
should be suitable to investigate algorithms for opportunistic scheduling.
What I did are simulations with one sending node and eight mobile
receivers in one common HSDPA cell.
All the users move with velocity 3 meters per second (pedestrian) on a
circular path with 500 meters distance between BS and UE.
As some nasty complication, I changed the transmission power for the
lines 1 to 4 to 32 dBm, whereas the lines 5 to 8 send with 38 dBm.
I simply wanted to simulate a constant shading for a number of lines.
This scenario is particularly interesting because Thomas Bonald pointed
out that Proportional Fair Scheduling, which is state of the art to my
knowledge, does not behave well in scenarios with asymmetric scheduling.
Now, let´s have a look at http://www.detlef-bosau.de/eurane_results.html
I did simuations with 500 seconds transmission time.
The plots in the first column show the achieved TCP goodput.
1. a round robin scheduler (at least, it is called that way within the
Eurane package. In fact, it is a "last recently served" scheduler, which
behaves more or less identical to round robin.)
2. a C/I scheduler (sometimes refered to as "maximum SNR scheduler")
which schedules the line with the best channel conditions in the whole
set of channels.
3. a "Fair Channel" scheduler, which is part of the Eurane package and
addresses the problem of PF scheduling metrics being not comparable for
different flows. So, we expect that this scheduler at least alleviates
the PF weaknesses in case of asymmteric fading.
4. the score based scheduler by Thomas Bonald (the code was provided by
Thomas Bonald and Luca Muscariello),
5. a Proportinal Fair scheduler and the
6. PF flavour proposed by Kolding. The code for both schedulers, PF and
Kolding, was provided by Abdulmohsen Mutairi.
7., 8. an Elastic RR scheduler, which is not yet published and proposed
by me ;-). (If there is any interest in this scheduler, I would well
write a paper about it. But if not, I can spend the time on other
(BTW: If there is someone experienced with octave and could help me to
have the flows 1 to 4 printed with circles and the rest with asterisks
and both done as it can be done in gnuplot so that only every 10 samples
a circle or asterisk is plotted, I would be glad.
And the plots would be much more clear.)
If we compare the achieved goodput, we immediately see the benefits of
exploiting multi user diversity: With respect to the achieved goodput,
nearly everything is better than round robin scheduling.
However, the goodput is not always good for all lines. E.g., with PF
there are flows with quite impressive goodput (flow 1) while others
hardly achieve anything (the rest).
This is not surprising. Particularly with asymmetric fading, "noisy"
lines have to wait for intervals where "low noise lines" experience
extremly low noise to get a time slot assigned.
When we use a C/I scheduler, the noisy lines (1 to 4) hardly achieve any
goodput at all.
However, even the different goodput for the different lines with PF
schedulers is, in my opinion, not really convincing and not adequate for
any practical implementation.
The situation is alleviated with the Fair Channel Scheduler and with
Both achieve fair goodput at least within a group of equal channel
conditions (line 1 to 4 being the one group, line 5 to 8 beign the
other) and quite acceptable ressource fairness when we look at the time
Bonald, Score Based:
Surprisingly, the fair channel scheduler achieves a better ressource
fairness than the score based scheduler.
To my understanding, both schedulers attempt to normalize a scheduling
priority statistic by normalizing location parameters.
The fair channel scheduler uses mean and variance, while the sore based
scheduler relies upon an estimate for an upper and lower limit for a
sample of SNR values. (In his paper, Thomas Bonald talks about a
"ranking", however in fact this is nothing else than finding such limits
and making sample sets comparable with these.)
AFAIK, an empirical average statistic and an empirical variance
statistic are quite robust, presumably more stable than estimates for an
upper and / or lower limit, so it´s perhaps not that suruprising that
the fair channel scheduler achieves a better fairness than the score
based scheduler in this scenario.
There is also a plot for the ressource allocation achieved with the PF
I think, there´s no need for a detailed discussion ;-)
What I did not add so far is an implementation of Thierry Klein´s
modifications to the PF scheduler. If there is interest in that, I will
add these in the future, because in that case, we had traces for all
availabe PF flavours. However, I do not expect better ressource fairness
here, because the problem addressed by Thierry was (same als Kolding) to
cope with buffer underruns in TCP flows which can cause severe delay spikes.
Now, a general weakness of all schedulers using a "scheduling priority",
i.e. C/I, and PF flavours, is that there is hardly a limit for a packet
delay because we cannot predict when a channel will have favourite
We particularly enjoy the packet delays (from BS to UE, i.e the time a
packet needs to travel through the recovery layer) achieved with
Proportional Fair scheduling:
(Can somebody please tell me, where I can complain about the totally
inadequate paper format? The lines 5 and 6 appear somewhat, say,
horizontally challenged here. In case of any publication, I have to find
a plot which is more politcal correct.)
The round robin scheduler
gives an expectation what _can_ be achieved here.
However, please bear in mind that retransmits needed for Chase combining
are not subject to the scheduling algorihtm in the EURANE code, but are
done immediately after a failed transmission. I do not yet know whether
this is the case in real HSDPA implementations as well or whether this
is an EURANE specific artifact. I woul particularly appreciate any
commonts on this one.
The elastic Round Robin scheuler however controls the actual slot rate
_with_ consideration of retransmits, so that
might be somewhat confusing here.
However, the delays achieved with elastic RR are that small and limited,
that I could imagine using this even for streaming applications. Which
are not reasonable with PF scheduling.
The goodput achieved with elastic RR is comparable to that of Fair
Channel scheduling and the fairness is slightly better.
Elastic RR is based upon a rate based round robin scheme which primarily
enforces identical slotrate to all flows and allows to violate this
slotrate within given limits (defined by the tolerance parameter).
Only when _all_ slotrates of _all_ competing flows stay within this
predefined limit, a scheduling decision is made based upon an
opportunistic scheduling priority (actually, I used a fair channel
scheduler for that purpose).
In any other case, the line with the actually smallest rate is assigned
a time slot.
As a general lesson, we learn that we can well exloit multi user
diversity and achieve reasonable high goodput for all competing flows
with only _little_ violation of a traditional round robin scheme and
good ressource fairness.
The code is available at
which of course only contains the changed EURANE files.
And now, I would be glad for any kind of questions, comments and discussion.
Detlef Bosau Mail: detlef.bosau at web.de
Galileistrasse 30 Web: http://www.detlef-bosau.de
70565 Stuttgart Skype: detlef.bosau
Mobile: +49 172 681 9937
More information about the end2end-interest