[e2e] Detlef and Opportunistic Scheudling. was: Re: Once again: Detlef and Latencies :-)

[Detlef Bosau]

Hi.

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 
http://www.ti-wmc.nl/eurane/
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. 

You find
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 
things. ;-))

(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 
scheduling 
http://www.detlef-bosau.de/eurane_results/goodput_s_9_t_0.1.eps.gz
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 
Bonald´s Scheduler.

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 
slot allocations:

Fair Channel: 
http://www.detlef-bosau.de/eurane_results/allocated_slots_s_3_t_0.1.eps.gz
Bonald, Score Based: 
http://www.detlef-bosau.de/eurane_results/allocated_slots_s_8_t_0.1.eps.gz

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 
scheduler: 
http://www.detlef-bosau.de/eurane_results/allocated_slots_s_9_t_0.1.eps.gz

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 
conditions.
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:
http://www.detlef-bosau.de/eurane_results/delay_s_9_t_0.1.eps.gz
(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
http://www.detlef-bosau.de/eurane_results/delay_s_1_t_0.1.eps.gz
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
http://www.detlef-bosau.de/eurane_results/delay_s_11_t_0.01.eps.gz
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.

O.k.

The code is available at
http://www.detlef-bosau.de/eurane.html
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