[Iccrg] Re: [conex] ECN marking over wireless networks

[[e-mail] (Jim Gettys)]

On 06/07/2012 05:14 AM, Michael Welzl wrote:
> Hi,
>
> I've been wanting to write an answer to this for a long time but just
> never got around to it. Sorry!
>
> I see ast least two major problems with suggesting an ECN marking
> method for wireless systems (in fact there are more, as you mention in
> your own email):
>
> 1) Fairness. If I get to send at a lower rate, I waste more of
> everyone's resources. My own benefit is also reduced. Should I send
> even less than what the system now allows me, to be friendly to
> everyone, or should I send as much as I can? I might be in worse
> conditions than others; does that mean that I should be even worse off? 

Probably so: if you can only get 1Mbps, the idea of a single station
being able to starve a network that is primarily running 100x faster
seems broken.
 
> I think the correct answer would have to be a function of the impact
> that my own traffic has on the utility that everyone else is getting
> out of the network resources, and the utility that I am getting out of
> them. We can assume a general case of a strictly concave function and
> solve the problem with calculations a la proportional fairness... 

"Fairness" in this case has to do with access to "air-time", I expect,
and not bandwidth.  I'm not convinced (in fact, I am pretty convinced of
the converse) that this is anything TCP can/should enforce at all, but
is something enforced by the wireless drivers in the AP. If there are
three stations actively "talking", I expect each one to get 1/3 of the
transmission opportunities.

Internal to the Linux wireless drivers, there are separate queues kept
for each station.  Note that we need to control the "aggregate"
delays/buffering, so to avoid very high latencies on a busy network, you
need to be able to mark across all the queues, not treat them as fully
independent queues; but as the "cost" of the packet is different
depending on the rate, the probabilities probably need adjustment. 
Exactly what the "best" strategy here is TBD.  Come help figure out what
TBD is....

With 802.11n aggregation, this all gets "interesting", as in the Chinese
curse....

> but then again, not all applications have such utility functions (e.g.
> VoIP is different, and using e.g. VoIP over WiFi is not at all
> uncommon). A good solution would therefore have to make a local
> decision that is based on knowing which applications are used.

There are four queues in 802.11 that indeed have some real effect at a
fundamental level; but currently traffic is not necessarily dropped into
the correct queues.

This begs the question of proper classification/diffserv marking and
that mapping to those queues.

>
> 2) Heterogeneity: wireless systems differ greatly. For instance, in
> [1] we found that, **in total absence of real noise**, TCP's
> throughput across a WLAN can very much depend on the chosen rate
> adaptation mechanisms. Essentially, this means that some rate
> adaptation mechanisms do a bad job at trying to detect noise, and
> mistake collisions for it. They then switch to a lower rate when they
> really shouldn't (on a side note, Minstrel, available in MadWifi,
> seemed to always work best). Now, note that in a practical WLAN you
> don't even know which rate adaptation mechanism is chosen by the
> individual hosts participating! Under such conditions, how would you
> make an ECN-marking rule work well for everyone? Yes we could design a
> rule, but that would have to depend on the driver and even the
> configuration of not only the AP but all the hosts currently involved.

Most Linux drivers now use the MAC 802.11 framework; Minstrel is used in
MAC 802.11

http://linuxwireless.org/en/developers/Documentation/mac80211

What is used on other OS's I do not know.  But as Linux is heavily used
in home routers, I think the information below should be helpful.


>
> To conclude: yes I think this is interesting stuff, and worth
> investigating as a research topic. As such it's perfectly fine to
> discuss it at ICCRG (I suggest: on the basis of measurements). And
> maybe (an adaptation of) conex can solve problem #1 above - but not
> problem #2. It is therefore clear to me that we cannot make a general
> recommendation at this stage, and I think it's very likely that, even
> after carrying out a lot of research on this, no *general*
> recommendation can ever be made.

Our experience with CeroWrt http://www.bufferbloat.net/projects/cerowrt
and http://cero2.bufferbloat.net/cerowrt/
<http://cero2.bufferbloat.net/cerowrt/>is informative on the topic:

0) there are many bugs that need to be fixed in different drivers. 
Infinite retransmit bugs have been found in several drivers.  The driver
we currently "trust" the most (or maybe "distrust" the least is a better
term) is the Atheros ath9k driver.

1) the current Linux 802.11 stack has serious over buffering and design
problems: in order to do good 802.11n aggregation, a large number of
packets currently get sucked out of the queue disciplines in Linux into
the driver (to be able to fill aggregation buffers).  Since ECN marking
goes on (in the current design) in the queue disciplines, this means
that marking only starts to happen much later than it should.  What is
more, some drivers have grossly too much buffering in the driver even
for 802.11n aggregation.  Again, the ath9k driver is currently
distrusted the least (Felix Fietkau having worked with Dave Taht to get
it reduced from > 130 packets to no more than 34 packets, which is still
way too much). Ideally, marking/dropping should be unified across the
queue disciplines and device drivers; but that's not how the queuing
works today.

Working through the redesign/refactoring of the 802.11 stack in light of
bufferbloat and the desire for good AQM (with or without use of ECN) has
begun, but it's not a trivial undertaking.

2) RED is (nearly) useless in wireless, as bandwidth is variable. Dave
Taht spend months (while we were hoping for and then waiting for CoDel)
experimenting with RED, and (as we were warned by Van) it's  impossible
to tune well in the face of such variable bandwidth.

Dave Taht is getting much, much better results (given that there is
still too much buffering in the drivers) using CoDel (specifically the
fq_codel discipline, which also does fair queueing).  The codel and
fq_codel AQM mechanisms were recently merged for release in Linux 3.5. 
Even with the extremely excessive buffering, we're seeing good
improvement using CoDel (without any of the tuning headaches).  Dave can
speak to this if he likes, when he comes up for air....

I have a number of conclusions:
    o anything observed on older versions of Linux is almost certainly
close to useless now.  There are just too many bugs, and too much
buffering in the current wireless stack to believe much can be learned
in terms of TCP performance, and certainly not working well enough to
inform anyone how TCP might be changed.  The right approach is to dig
into the implementations and iteratively test (and fix!) problems that
are uncovered.  If you just observe the system as a "black box" from the
outside, you won't get very far.
   o RED is the wrong AQM mechanism, particularly for wireless.  Note
that the codel/fq_codel line disciplines do implement ECN, so have fun
taking data!
   o view this as experimental computer science crossed with
engineering.  The problems are interesting, the code is available, and
you should all beat the heck out of the software.
   o we need a much larger set of people trying experiments and seeing
what works best. Come help!  CeroWrt has extensive network testing tools
already its image to help make this much easier.
                                Best regards,
                                        Jim


<http://cero2.bufferbloat.net/cerowrt/>
>
> Cheers,
> Michael
>
> [1] Naeem Khademi, Michael Welzl, Stein Gjessing: "Experimental
> Evaluation of TCP Performance in Multi-rate 802.11 WLANs", accepted
> for publication, IEEE WoWMoM 2012, 25-28 June 2012, San Francisco,
> California, USA.
>
>
>
> On 5/9/12 10:48 PM, [e-mail] wrote:
>>
>> Hi,
>>
>> There has been some discussion during the IETF 83 in Paris in ICCRG
>> and CONEX WG about relevant ECN marking algorithms over wireless
>> networks.
>>
>> Some aspects related to this topic are discussed in this draft:
>> http://www.ietf.org/id/draft-jobert-tsvwg-pre-congest-notif-mobile-00.pdf,
>> briefly introduced during ICCRG meeting.
>>
>> This email aims at starting some discussion on the mailing lists of
>> ICCRG and CONEX, as requested by the chairs after the discussions
>> during IETF 83.
>>
>> Essentially, the main aspect pointed out during the discussions was
>> that there might benefits in taking into account the radio conditions
>> of the mobile terminal for ECN marking over the radio segment and for
>> congestion-volume counting. The reason for this is that it requires
>> more radio resources to transmit the same amount of data to a
>> terminal in bad radio conditions compared to a terminal in good radio
>> conditions.
>>
>> As an introduction to the discussion, it might be useful to mention
>> that different potential /use cases/ for ECN marking involving the
>> mobile terminal could be envisaged:
>>
>> 1.interaction with TCP
>>
>> 2.adapt the coding rate of adaptive application (e.g. adaptive
>> streaming, etc.), as suggested in 3GPP TS 36.300 document
>>
>> 3.stop/delay the non-urgent applications (background tasks in the
>> terminal, etc.)
>>
>> 4.congestion-volume counting (as for Conex related use cases)
>>
>> This list is obviously non-exhaustive, and shows that depending on
>> the final utilization of the congestion notification, different
>> algorithms for ECN marking over the radio segment might be imagined.
>> The most optimal algorithm certainly depends on the final objective.
>>
>> From the comments received during the discussion, it seems that the
>> first ECN marking algorithm over the radio segment that comes to most
>> people?s mind is to consider an average queue length exceeding a
>> given threshold, as for RED. It should be noted that because the
>> radio segment shares the radio resource among several terminals, one
>> dedicated queue per terminal is in general considered.
>>
>> Therefore, if one would like to apply RED over a wireless segment, it
>> should be clarified whether it would be applied independently on each
>> dedicated queue per terminal (n instances of RED considered for the
>> radio segment), or on the sum of all the dedicated queues (1 single
>> instance of RED considered for the radio segment). This would lead to
>> two different ECN marking /criteria/:
>>
>> 1.RED based on the individual queue of each terminal
>>
>> 2.RED based on a single shared queue between all the terminals
>>
>> Several remarks were raised during the presentation of the draft in
>> ICCRG and the discussion in CONEX:
>>
>> -On the interactions with TCP (use case #1 listed above), it was
>> mentioned that TCP works on a longer timescale relative to the
>> wireless channel. In other words: the radio conditions may vary more
>> quickly than TCP reactions. This is correct, however, it should be
>> mentioned that the objective of ECN marking over the radio segment is
>> not to replace the existing radio schedulers, which already provide a
>> suitable control loop over these shorter time scales. As an example,
>> the very common Proportional Fair (PF) algorithm aims at addressing
>> exactly this point, by trying to optimize the allocation of radio
>> resources (the terminals in good instantaneous radio conditions are
>> favored compared to the others, as to optimize the cell capacity,
>> while certain fairness is ensured in the longer term by taking into
>> account also the averaged throughputs delivered to the terminals).
>>
>> -Still regarding the interactions with TCP (use case #1 listed
>> above), assume now that a PF algorithm is used to control the
>> allocation of radio resources. It was mentioned also that if it is
>> assumed that ECN marking is done according to the individual queue of
>> each terminal (criteria #1 listed above), then a terminal in bad
>> radio conditions will already experience ECN marking more often
>> without the need to weight the probability of the ECN marking with
>> the radio conditions of the terminal. This is due to the fact that PF
>> provides higher throughput to terminals in good averaged radio
>> conditions than in bad averaged radio conditions. Actually, the
>> amount of ECN marking will depend in this case whether the throughput
>> required to transmit the data to a particular terminal is lower than
>> the throughput provided to this terminal by PF; if not, then no ECN
>> marking should happen for this terminal in these conditions (even
>> during congested periods actually).
>>
>> -Based on this discussion, it seems to me that the interaction of ECN
>> marking with TCP should not be analyzed in terms of benefits it
>> brings to control the allocation of resources over the radio segment,
>> which is already under the control of the radio scheduler. It seems
>> that this second control loop provided by ECN marking interacting
>> with TCP would rather aim at indicating when the traffic rate of a
>> terminal exceeds the throughput provided by PF to this terminal,
>> which could be useful for use case #2 (coding rate adaptation).
>> Basically, it is expected that this second control loop would try to
>> ?align? with the throughput provided by the first one (keeping in
>> mind that PF provides throughputs varying with time).
>>
>> -The same example but now with the ECN marking criteria #2 instead of
>> #1 raises however issues. Indeed, in case the throughput required to
>> transmit the data to one particular terminal is lower than the
>> throughput provided to this terminal, this will lead to ECN marking
>> for all the terminals, even the ones below the PF throughput, which
>> is a situation that should be avoided when interaction with TCP is
>> desirable. Excessive traffic consumption on one terminal should not
>> impact the others (i.e. should not lead to the generation of ECN
>> marking for the others). Definitely, the criteria #1 does not seem a
>> good idea when interaction with TCP is desired.
>>
>> -Considering the use case #3 depicted earlier now, it should be noted
>> however that the previous situation with PF + ECN marking based on
>> individual queues (criteria #1) has some limitation. Indeed, in case
>> of radio congestion (assume here that radio congestion means that all
>> the radio resources are used and are not enough to transmit all the
>> data to be transmitted to all the terminals ? a more accurate
>> definition might be found), some of the terminals may not received
>> ECN marking, as indicated before (in case they require less than what
>> PF can provide to them). Perhaps some of the data transmitted to
>> these non-notified terminals are not so critical and might be
>> delayed, as to free resources to the other users with more important
>> traffic to be exchanged. The depicted situation does not provide
>> incentives to do this, because ECN marking only applies to some
>> users. It is the reason why it might be interesting to consider other
>> ECN marking algorithms (which might not aim at interacting
>> necessarily with TCP; BTW not all the applications are running over
>> TCP), as to inform about the congestion situation. The idea is to say
>> to the end user: ?Hey! The system starts being full, the PF algorithm
>> will still provide you with some network resources, but if some of
>> your data can be delayed, please do so!? Of course, this kind of
>> approach might be coupled with congestion-volume counting / CONEX use
>> cases, to provide incentives.
>>
>> -Let?s take a practical example to illustrate (note sure it is the
>> best one, but it is the one that comes to my mind?): you need to go
>> to some administration to collect some administrative document ? say,
>> a voting card to elect your new president. There is already a long
>> queue, but you could pass with a ?certain priority? because what you
>> need to do is faster than what other people have to do. However, if
>> you collect your document, you consume resources of the system that
>> will not be available to the others during this time ? the person in
>> front of you will be busy giving you your document. And what you need
>> to do is not urgent ? the election is not tomorrow, you will have
>> time to come back later. Perhaps you would like to be fair with the
>> other people having more urgent things to do and waiting in the
>> queue, and you will not wait and instead come back later? And perhaps
>> a signal indicating the congestion might be useful (it is probably
>> good to know if the queue is long or not, rather than waiting without
>> information).
>>
>> -Considering the use case #4 depicted earlier now on
>> congestion-volume counting: it seems logical to me that the count
>> would take into account the real network resource usage rather than
>> simply the number of bits transmitted. This would provide again
>> incentives to users in bad radio conditions to delay non-urgent
>> network usage. Moreover, an interesting question which should be
>> raised would be to define what corresponds to a ?congested period?
>> for the radio segment: is it only when the terminal exceeds its PF
>> rate, or should a congestion period be considered when the system
>> starts being full/is full? This might trigger different ECN marking
>> algorithms on the wireless segment.
>>
>> I had noted two other comments from the discussions in IETF 83:
>>
>> -TCP middlebox accelerating TCP window growth: some comment was made
>> on the mic, however I am not sure that I understood what this device
>> is supposed to do; would anyone of you have some reference on this?
>>
>> -Retransmission over the radio segment: should it be taken into
>> account as well for congestion-volume counting? It would mean that a
>> lost packet that is retransmitted by the low layers should be counted
>> twice? (after all, if it was retransmitted by TCP, it would have been
>> counted twice as well, right?)
>>
>> Feedback on this discussion is welcomed. Thanks in advance.
>>
>> Cheers,
>>
>> *S?bastien JOBERT*
>> Orange Expert "Future Networks", network synchronization and QoS in
>> mobile networks
>> *Orange Labs, Networks & Carriers - France Telecom R&D*
>> [e-mail] <mailto:[e-mail]>
>>
>>
>>
>> _______________________________________________
>> conex mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/listinfo/conex
>
>
> _______________________________________________
> Iccrg mailing list
> [e-mail]
> http://oakham.cs.ucl.ac.uk/mailman/listinfo/iccrg