Subject: [conex] Off-Topic: Smoothing Variations in BitRate

From: "Scheffenegger, Richard" <[email-masked]>
Date: Sun, 1 Aug 2010 22:33:49 +0100

A few add-ons to that thread, I'd like some expert statements on:

>From Bob Briscoe:

> As long as the queue gives you more drop or marking for a longer 
> *queue*, congestion indications will be convex (ie hockeystick) 
> with *load*. Any queue will do that, with or without active queue 
> management (AQM).
>
> Nonetheless, an AQM does have to be designed carefully to maintain 
> stability, responsiveness and randomness (ie no bias against 
> certain packets). But its design can hardly affect the equilibrium
> at all.

Will that hold for assessment hold true for a simple instantaneous
queue-depth
Related marking scheme?

p ^
1-|       +-------------
  |       |
  |       |
  +-------+------------->
           Queue Depth

(Instantaneous Queue depth would take some of the sluggishness out from
AQM ECN marking...)

Note that short RTT flows might be then running at quite high CE marking
rates, while long RTT flows under lower - assuming a very bursty traffic
regime...

From: John Leslie:

>  Fundamentally, to get smoother variation, the reduction signaled by
>  an individual ECN-CE mark would need to be less than 50%. This, IMHO,
>  would indeed be reasonable if we agreed somehow to create more of
them.
>  (Unfortunately, setting more CONEX-CE marks isn't likely to cause
this,
>  despite my poorly-worded earlier posting.)

> > With a 0.1% equilibrium point the video streaming service will
likely
> > have to resort to TCP like behavior (rate halving) in its response
> > to the ECN marks. 

>  Unfortunately, the basic ECN expectation in RFC 3168 is that an
>  ECN-CE mark will cause rate halving.

To be pedantic here, from RFC3168:

   The sending
   TCP SHOULD NOT increase the congestion window in response to the
   receipt of an ECN-Echo ACK packet.

   TCP should not react to congestion indications more than once every
   window of data (or more loosely, more than once every round-trip
   time). That is, the TCP sender's congestion window should be reduced
   only once in response to a series of dropped and/or CE packets from a
   single window of data.  In addition, the TCP source should not
   decrease the slow-start threshold, ssthresh, if it has been decreased
   within the last round trip time.  However, if any retransmitted
   packets are dropped, then this is interpreted by the source TCP as a
   new instance of congestion.

Thus, independed on the number of CE marks per cwnd/rtt received, only a

Single response per cwnd/rtt is allowed... However, RFC3168 leaves it
open
if a more granular reaction is allowed, right?

Thus, a LEDBAT-like CC could use a scheme such as 

Cwnd = max(cwnd * 1/2 * (1-f), mss), with 

f ... Fraction of reflected CE received vs. total segments sent.

Similarily, a sender which has higher demands on the speediness could do
with

Cwnd = max(cwnd *  (1/2 + f/2), mss)

But it's true, defining the CC behaviour is beyond the scope of conex :)

Richard Scheffenegger

---

From: Fred Baker <[email-masked]>
Date: Mon, 2 Aug 2010 08:12:04 +0200

It really kind of depends on how the whole thing is designed. AQM is designed to distribute marks or drops across all sessions, with each getting an occasional mark/drop but no consistent rate, so that as mark/drop becomes more consistent the endpoint can infer greater insistence on the part of the network. Instantaneous Marking is the ECN counterpart to Tail Drop, and (especially if the IW=10 proposal is adopted) will likely tend to hit new sessions a lot harder than established sessions. As a result, the end system behavior has to be adapted to the expected network behavior. If the end system is sending with IW=10 (sending an initial burst of up to ten packets) and can reasonably expect one or two to be marked, it should be pretty sensitive to marking. If it is sending ten packets and can reasonably expect all ten to be marked, it should probably be less aggressive in its response to a mark.

I'm rather in favor of the AQM model.

On Aug 1, 2010, at 11:33 PM, Scheffenegger, Richard wrote:
> _______________________________________________
> conex mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/conex

http://www.ipinc.net/IPv4.GIF

---

From: Bob Briscoe <[email-masked]>
Date: Mon, 02 Aug 2010 20:26:48 +0100

Fred & Richard,

inline...
[Remembering, this is off-topic for ConEx]

At 07:12 02/08/2010, Fred Baker wrote:
>It really kind of depends on how the whole thing is designed. AQM is 
>designed to distribute marks or drops across all sessions, with each 
>getting an occasional mark/drop but no consistent rate, so that as 
>mark/drop becomes more consistent the endpoint can infer greater 
>insistence on the part of the network. Instantaneous Marking is the 
>ECN counterpart to Tail Drop, and (especially if the IW=10 proposal 
>is adopted) will likely tend to hit new sessions a lot harder than 
>established sessions.

I believe the bias against new flows and towards established flows 
comes from TCP not anything the AQM is doing. It's because TCP treats 
any number of marks within a RTT as one event. Any well-randomised 
AQM will hit an established flow with more marks if the flow has 
established more bit-rate than a new flow. But if both use the TCP 
assumption (many marks within 1 RTT = 1 mark), then the established 
flow will gain because it ignores more marks.

FWIW, there is an important difference between a step ECN threshold 
and tail-drop; packets that arrive when the queue is greater than the 
threshold still get forwarded (they are just marked). Once the queue 
has been driven to the threshold, an instantaneous AQM will surely 
mark any arriving packets in proportion to their relative 
instantaneous bit-rates. I don't think the AQM per se will be biased 
by whether packets are from established or new flows - only TCP 
creates that bias I think.

BTW, for similar reasons, an ECN step threshold doesn't lock out 
larger packets like tail drop does. With tail drop, the queue has to 
have drained more to fit a larger packet than a smaller one. But with 
an ECN step threshold, any size packet can still fit into the buffer 
above the threshold without being dropped.  So, as the queue drains, 
random marking will be proportionate to the arriving bit-rates of the 
different flows, irrespective of their packet sizes.

>As a result, the end system behavior has to be adapted to the 
>expected network behavior. If the end system is sending with IW=10 
>(sending an initial burst of up to ten packets) and can reasonably 
>expect one or two to be marked, it should be pretty sensitive to 
>marking. If it is sending ten packets and can reasonably expect all 
>ten to be marked, it should probably be less aggressive in its 
>response to a mark.
>

Yup. But I have an open mind as to exactly what 'the AQM model' 
means, as there's a large part of the AQM design space still to 
explore. However, you're right that we do have to worry about 
interoperability of responses.

But I believe interop is best served by thinking of it the other way 
round. The best AQM will be the one that most accurately reflects 
back on a bursty flow the harm from the increase in queue it has 
caused. And interop is best served if transports assume that all AQMs 
will try to reflect back harm as quickly as poss, and any that are 
sluggish are just the deficient exceptions that a bursty transport 
has been 'lucky' enough to encounter.

So queue averaging can be thought of as a weakness; because one flow 
can bump up the queue then it can leave the system before the 
averaging has caught up - causing someone else to get hit. An AQM can 
never be as fast as it ought to be ideally, but I'm coming round to 
the view that adding delay deliberately is not good (I used to buy 
Sally Floyd's argument, but now I'm not so sure).

Sally's argument: The idea of queue averaging is to filter out spikes 
that will go away of their own accord. Ie. filtering improves 
performance. DCTCP implements this filtering on the end-system 
instead of in the network. That is better in many respects except 
one: the averaging can be done more quickly across an aggregate of 
flows, rather than over one flow.

An interesting thought experiment: If the AQM provided both an 
instantaneous signal and an averaged one, which would an end-system 
react to? I think the reason we've had trouble on this point is that 
you will choose the smoothed one if all you care about is your own 
performance. But if you are also made to care about causing 
unnecessary congestion to others (as in some ConEx use-cases), the 
answer is not so clear-cut.

a response to RIchard inline too...

> > Will that hold for assessment hold true for a simple instantaneous

Yes.

The point is that if (marks vs queue length) is a step function, 
(marks vs load) will be a hockey-stick function. This is true only 
for traffic with some variance in it; so it's not true if every flow 
is pure CBR (in which case marks vs load will be a sharply bent 
right-angled hockey-stick!). However, as long as the traffic has at 
least some variance in its inter-arrival times, the little peaks in 
load hit the threshold in the queue earlier than the rest of the 
traffic, which starts the marking smoothly growing up the hockey-stick.

If we don't want to rely on the traffic's variance being the only 
source of smoothness in the response, then we want to put a ramp in 
the AQM's response function (marking vs queue length). But Damon 
Wischik tells me that setting a step threshold at a small queue 
length in the buffer to a high speed line ensures that it will pick 
out sufficient randomness in the traffic to give a smooth response. 
He was going to write a paper about this, but I don't think he has 
yet - so I am not sure of the exact conditions/assumptions.

If this bleeding edge research turns out to be true, it would mean 
that we might be able to get away with step threshold in high speed 
equipment (where simplicity of implementation is more important), 
while still needing a ramp threshold in slower queues (where there is 
probably time to run the extra cyles the ramp algorithm will need).

> > p ^

Indeed - other than to claim that ConEx should make it possible to 
encourage a wider range of congestion responses.

Bob

>http://www.ipinc.net/IPv4.GIF

________________________________________________________________
Bob Briscoe,                                BT Innovate & Design

---

From: Aki Nyrhinen <[email-masked]>
Date: Tue, 03 Aug 2010 02:47:03 +0300

Hi all,

Just wanted to have my piece of this off-topic discussion.. everything
Bob says is true, but there is another important difference between a
step threshold marker and tail-drop, which is easier to miss but not
less substantial. I hope this hasn't been discussed over and over in the
past. The following is much a result of a thought experiment, but i was
originally hit (in the head) by the difference when experimenting with
"different" marking and congestion control algorithms. Bob gives a hint
to this very difference in his remark about the pure CBR case funny
looking hockeystick.

In general, a step threshold marker will mark way more packets than
tail-drop would drop. Simplifying, tail-drop will drop packets
proportional to load when congested. A step threshold marker will mark
ALL packets between the start and end of congestion independent of load
and capacity between those two instants.

This is not a property we want a bottleneck to have in an environment
where congestion control algorithms seek to cause load > 1 on the
bottleneck. Yes I am serious, tail-drop is immeasurably better. TCP is
probably the only thing I can imagine working reasonably well over the
step threshold marker.

A trivial example: we have a bottleneck device and a single bulk tcp
connection going through it. The tcp connection has reached a point (in
congestion avoidance for simplicity) where it fully utilizes the link
and some queue has built up at the bottleneck. Now here is what will
follow, 

	1) window passes by, tcp increases cwnd by one
	2) marking threshold is exceeded (by one).
	3) bottleneck starts marking.
	4) after a window's worth of segments, tcp receives first mark.
	5) tcp halves transmission rate.
	6) queue starts to drain and falls below marking threshold
	7) bottleneck stops marking.

How much time is there between steps 3 and 7? Does this have anything to
do with load at the bottleneck between those two steps? I'd say '1 RTT
(tcp-view)' and 'no'. The load is (1+cwnd)/cwnd but cwnd packets are
marked instead of a single one, which would be proportional to load. Due
to self-clocking, a single tcp connection looks very much like CBR
except for the once in RTT bump which periodically increases the
bottleneck queue length.

Relentless would respond to the step threshold marker by dropping its
sending rate to zero (which may or may not be surprising) and anything
more fine-grained than TCP would still suffer.

I don't think smarter marking schemes necessarily imply AQM, random
numbers or anything very complicated at all, but I really think we (me
included) should actively forget the idea of step threshold being
similar to tail-drop: the only similarity they have is "if(qlen >
threshold)".

Just my fraction of a cent.

	Aki

---

From: "Scheffenegger, Richard" <[email-masked]>
Date: Tue, 3 Aug 2010 11:44:52 +0100

Bcc'ed ConEx, as it sways too much off topic for conex, and into ICCRG
territory...
Hi Aki,

> -----Original Message-----
> From: Aki Nyrhinen [mailto:[email-masked]] 
> 
> In general, a step threshold marker will mark way more 
> packets than tail-drop would drop. Simplifying, tail-drop 
> will drop packets proportional to load when congested. A step 
> threshold marker will mark ALL packets between the start and 
> end of congestion independent of load and capacity between 
> those two instants.

True; but therefore, it's implementation at wirespeed on 10G, 40G and
100G interfaces would be much less complex. I agree, that obtaining more
granular information from the bottleneck would be ideal, though.

> This is not a property we want a bottleneck to have in an 
> environment where congestion control algorithms seek to cause 
> load > 1 on the bottleneck. Yes I am serious, tail-drop is 
> immeasurably better. TCP is probably the only thing I can 
> imagine working reasonably well over the step threshold marker.

CBR wouldn't care much about step-threshold either.
 
> 
> How much time is there between steps 3 and 7? Does this have 
> anything to do with load at the bottleneck between those two 
> steps? I'd say '1 RTT (tcp-view)' and 'no'. The load is 
> (1+cwnd)/cwnd but cwnd packets are marked instead of a single 
> one, which would be proportional to load. Due to 
> self-clocking, a single tcp connection looks very much like 
> CBR except for the once in RTT bump which periodically 
> increases the bottleneck queue length.
> 
> Relentless would respond to the step threshold marker by 
> dropping its sending rate to zero (which may or may not be 
> surprising) and anything more fine-grained than TCP would 
> still suffer.
> 
> I don't think smarter marking schemes necessarily imply AQM, 
> random numbers or anything very complicated at all, but I 
> really think we (me
> included) should actively forget the idea of step threshold 
> being similar to tail-drop: the only similarity they have is 
> "if(qlen > threshold)".
> 

I believe one can not look at AQM schemes completely independent of the
transport layer and it'S congestion control.

Currently, RED has implemented multiple tunables:

Min_th
Max_th
Mark_p (@max_th)
EWMA weight

(Max_th-Min_th is the tunable, with Min_th only being an offset to queue
length and could be excluded).

For none of which exists a good, closed formula, how to deploy them when
one doesn't run (and know about) the full e2e path (AFAIK).

However, all of these tunables directly influence the CC algorithm in
the transport layer.

And to get back to your objection - moving the averaging up from the
bottleneck to the transport layer, to cover, say, 10 RTT, you can still
obtain a very fine-grained, congestion-related signal from a simple
step-response marking scheme. At the same time, as the end systems
actually knows the RTT, it can optimize the weight for different flows
(ie, low for short RTT , and high for long RTT - so that the
responsiveness in absolute time (not RTT) stays about the same).

Also, remember that MulTFRC could do more educated things in response to
a more fine-grained congestion signal - even if the fine-grain signal is
only sythesized within the sender (after feedback from the receiver).

I have to admit, that I'm not an expert in control theory; but it would
appear to me that building a more suitable control strategy based on a
valid set of assumptions has the potential of better results than
relying on the notion that AQM knows what it's doing, even though each
independent entity can freely choose between 3 arbitrary values
(max-min; p; weight) when setting up AQM (unless an implementator has
choose all or some already). And step-response would only be a
corner-case of AQM (so nothing prevents one from using a set of
(0;1.0;1.0) at the moment other than potential implementiation
limitations somewhere - such as impacting TCP-like flows independent of
relative bandwidth though the bottleneck, as there is only a single
response, once per RTT, in TCP).

Perhaps I should take this to ICCRG though ;)

Richard Scheffenegger