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

[Lloyd Wood]

Can't you just write up a paper like everyone else and submit it for publication?

At Friday 11/01/2008 14:06 +0100, Detlef Bosau wrote:
>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
>
>
>