[Cake] lower bounds for latency

[Cake] lower bounds for latency

[Dave Taht]

bob's been up to good stuff lately..

http://bobbriscoe.net/projects/latency/sub-mss-w.pdf

It was weird, only last night I was thinking upon the real lower
bounds on what was needed to keep a flow going in tcp at X,Y,Z rtts
(in the context of being dissatisified with the stanford result, and
not "quite" in the context of "buffering"), and he nails that in the
first paragraph.

Have to work through his prescription though....

-- 
Dave Täht
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast

Re: [Cake] lower bounds for latency

[David Lang]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 2111 bytes --]

On Fri, 5 Jun 2015, Dave Taht wrote:

> bob's been up to good stuff lately..
>
> http://bobbriscoe.net/projects/latency/sub-mss-w.pdf

one thing that looks wrong to me. He talks about how TCP implementations cannot 
operate at less than two packets per RTT. It's not clear what he means. Does he 
mean two packets in flight per RTT? or two packets worth of buffering per RTT?

Two packets in flight per RTT would make sense as a minimum, but two packets 
worth of buffering on N devices in the path doesn't.

using the example of a 6ms RTT. Depending on the equipment involved, this could 
have from one to several devices handling the packets between the source and the 
destination. Saying that each device in the path must have two packets worth of 
buffering doesn't make sense. At a given line speed and data rate, you will have 
X packets in flight. the number of devices between the source and the 
destination will not change X.

If the requirement is that there are always at least two packets in flight in a 
RTT, it doesn't then follow that both packets are going to be in the buffer of 
the same device at the same time. I spoke with a vendor promising 7ms Los 
Angeles to Los Vegas. For the vast majority of that 7ms the packets are not in 
the buffers of the routers, but exist only as light in the fiber (I guess you 
could view the fiber acting as a buffer in such conditions)

where is the disconnect between my understanding and what Bob is talking about?

David Lang

> It was weird, only last night I was thinking upon the real lower
> bounds on what was needed to keep a flow going in tcp at X,Y,Z rtts
> (in the context of being dissatisified with the stanford result, and
> not "quite" in the context of "buffering"), and he nails that in the
> first paragraph.
>
> Have to work through his prescription though....
>
> -- 
> Dave Täht
> What will it take to vastly improve wifi for everyone?
> https://plus.google.com/u/0/explore/makewififast
> _______________________________________________
> Cake mailing list
> Cake@lists.bufferbloat.net
> https://lists.bufferbloat.net/listinfo/cake

Re: [Cake] lower bounds for latency

[Dave Taht]

On Fri, Jun 5, 2015 at 6:02 PM, David Lang <david@lang.hm> wrote:
> On Fri, 5 Jun 2015, Dave Taht wrote:
>
>> bob's been up to good stuff lately..
>>
>> http://bobbriscoe.net/projects/latency/sub-mss-w.pdf
>
>
> one thing that looks wrong to me. He talks about how TCP implementations
> cannot operate at less than two packets per RTT. It's not clear what he
> means. Does he mean two packets in flight per RTT? or two packets worth of
> buffering per RTT?

Flight.

I also disagree with this statement:

"It is always wrong to send smaller packets more
often, because the constraint may be packet pro-
cessing, not bits."

because I believe (but would have to go look at some data to make
sure) that we're good with packet sizes down into the 300 byte range
on most hardware, and thus could (and SHOULD) also reduce the mss in
these cases to keep the "signal strength" up at a sustainable levels.

I do recall that bittorrent used to reduce the mss and were asked to
stop (a decade ago), when they got as far down as 600 bytes or so.

but the rest I quite liked.

>
> Two packets in flight per RTT would make sense as a minimum, but two packets
> worth of buffering on N devices in the path doesn't.
>
> using the example of a 6ms RTT. Depending on the equipment involved, this
> could have from one to several devices handling the packets between the
> source and the destination. Saying that each device in the path must have
> two packets worth of buffering doesn't make sense. At a given line speed and
> data rate, you will have X packets in flight. the number of devices between
> the source and the destination will not change X.

Flight.

> If the requirement is that there are always at least two packets in flight
> in a RTT, it doesn't then follow that both packets are going to be in the
> buffer of the same device at the same time. I spoke with a vendor promising
> 7ms Los Angeles to Los Vegas. For the vast majority of that 7ms the packets
> are not in the buffers of the routers, but exist only as light in the fiber
> (I guess you could view the fiber acting as a buffer in such conditions)
>
> where is the disconnect between my understanding and what Bob is talking
> about?

Flight, not buffering. Redefining the goal of an aqm to keep packets
in flight rather than achieve a fixed queuing delay is what this is
about, and improving tcps to also keep packets in flight with
subpacket windows is part of his answer.

I like getting away from a target constant for delay (why 5ms when 5us
is doable) and this is an interesting way to think about it from both
ends.

And I was nattering about how I didn't like delayed acks just a few hours ago.

>
> David Lang
>
>> It was weird, only last night I was thinking upon the real lower
>> bounds on what was needed to keep a flow going in tcp at X,Y,Z rtts
>> (in the context of being dissatisified with the stanford result, and
>> not "quite" in the context of "buffering"), and he nails that in the
>> first paragraph.
>>
>> Have to work through his prescription though....
>>
>> --
>> Dave Täht
>> What will it take to vastly improve wifi for everyone?
>> https://plus.google.com/u/0/explore/makewififast
>> _______________________________________________
>> Cake mailing list
>> Cake@lists.bufferbloat.net
>> https://lists.bufferbloat.net/listinfo/cake



-- 
Dave Täht
What will it take to vastly improve wifi for everyone?
https://plus.google.com/u/0/explore/makewififast

Re: [Cake] lower bounds for latency

[David Lang]

On Fri, 5 Jun 2015, Dave Taht wrote:

> On Fri, Jun 5, 2015 at 6:02 PM, David Lang <david@lang.hm> wrote:
>> On Fri, 5 Jun 2015, Dave Taht wrote:
>>
>>> bob's been up to good stuff lately..
>>>
>>> http://bobbriscoe.net/projects/latency/sub-mss-w.pdf
>>
>>
>> one thing that looks wrong to me. He talks about how TCP implementations
>> cannot operate at less than two packets per RTT. It's not clear what he
>> means. Does he mean two packets in flight per RTT? or two packets worth of
>> buffering per RTT?
>
> Flight.

In that case I think his analysis of the effects of AQM are incorrect because 
they only limit the buffer size on one device, not the number of packets in 
flight.


He uses the example of 12 connections totaling 40Mb with a 6ms RTT. What if the 
systems are in the same rack and have <1ms RTT? according to him TCP just won't 
work.

> I also disagree with this statement:
>
> "It is always wrong to send smaller packets more
> often, because the constraint may be packet pro-
> cessing, not bits."
>
> because I believe (but would have to go look at some data to make
> sure) that we're good with packet sizes down into the 300 byte range
> on most hardware, and thus could (and SHOULD) also reduce the mss in
> these cases to keep the "signal strength" up at a sustainable levels.
>
> I do recall that bittorrent used to reduce the mss and were asked to
> stop (a decade ago), when they got as far down as 600 bytes or so.
>
> but the rest I quite liked.

I think it depends on the speed of the link. At the very low end (cheap home 
routers) and the very high end (multiple links >10Gb/s) the available processing 
per packet may be a limit. But in the huge middle ground between these extremes, 
you have quite a bit of cpu time per packet. The 3800 at 100Mb is an example of 
running into this limit, but at 10Mb it has no problem. The WRT1200 with it's 
dual-core GHz+ cpu has a lot of processor available for a bit more money. From 
there up until the large datacenter/ISP cores with multiple 10Gb ports to 
manage, you hae pleanty of cpu.

The other issue is the length of the 'dead air' between packets. The current 
standards have this being a fixed amount of time. combined with the 'wasted' 
packet header data results in the same amount of data using less total time if 
it's sent in fewer, larger packets than in smaller packets. when you are pushing 
the limits of the wire, this can make a difference.

This is why wifi tries to combine multiple packets into one transmission.

<rant>
We just need to break people of the mindset that it makes sense to hold off on 
transmitting something "just in case" something more comes along that could be 
combiend with it.

Instead they need to start off tranmitting the first one that comes along 
without any wait, and then in the future, check the queue to see if there's 
something else that can be combined with what you are ready to transmit, and if 
so, send it at the same time. Rsyslog implements exactly this algorithm in how 
it batches log messages that it's processing, the first message gets the minimum 
delay and future messages only get as much delay as is required to keep things 
moving. It does mean that the process hits continuous processing sooner (where 
there is no delay between finishing working on one batch and starting work on 
the next), but that 'always busy' point is not peak throughput, as batches are 
more efficient to process, the throughput keeps climbing while the latency 
climbs at a much lower rate (eventually you do hit a solid wall where larger 
batches don't help, so you just fall behind until traffic slows)
</rant>

>>
>> Two packets in flight per RTT would make sense as a minimum, but two packets
>> worth of buffering on N devices in the path doesn't.
>>
>> using the example of a 6ms RTT. Depending on the equipment involved, this
>> could have from one to several devices handling the packets between the
>> source and the destination. Saying that each device in the path must have
>> two packets worth of buffering doesn't make sense. At a given line speed and
>> data rate, you will have X packets in flight. the number of devices between
>> the source and the destination will not change X.
>
> Flight.
>
>> If the requirement is that there are always at least two packets in flight
>> in a RTT, it doesn't then follow that both packets are going to be in the
>> buffer of the same device at the same time. I spoke with a vendor promising
>> 7ms Los Angeles to Los Vegas. For the vast majority of that 7ms the packets
>> are not in the buffers of the routers, but exist only as light in the fiber
>> (I guess you could view the fiber acting as a buffer in such conditions)
>>
>> where is the disconnect between my understanding and what Bob is talking
>> about?
>
> Flight, not buffering. Redefining the goal of an aqm to keep packets
> in flight rather than achieve a fixed queuing delay is what this is
> about, and improving tcps to also keep packets in flight with
> subpacket windows is part of his answer.
>
> I like getting away from a target constant for delay (why 5ms when 5us
> is doable) and this is an interesting way to think about it from both
> ends.

I agree, the idea of trying to maintain a fixed buffer delay is not what we're 
trying to do, we're trying for the minimum amount of uneccessary buffer delay. 
The 'target' numbers are just the point where we say the delay is so bad that 
the traffic must be slowed.

> And I was nattering about how I didn't like delayed acks just a few hours ago.

what we need is a TCP stack that can combine acks that arrive separately over 
time and only send one.

David Lang

Re: [Cake] lower bounds for latency

[Jonathan Morton]

[-- Attachment #1: Type: text/plain, Size: 2485 bytes --]

It's an interesting viewpoint, at least, and probably should stimulate some
thought about what happens with very small BDPs. In this case we're talking
about a BDP below 3KB per flow, including light times, permitted queuing
delays, and link occupancy time of a single packet (which by itself
guarantees that the total BDP is always at least one packet).

A point that I think gets missed in discussions involving delayed acks, is
that it's always possible to force an immediate ack from the receiver,
simply by setting the Push flag. A TCP sender could use that if its cwnd is
forced down to 2 segments or less, without more invasive changes, in order
to maintain traditional ack clocking.

However, with only one packet in flight, loss of that packet would result
in an RTO, which I think would be much more severe a penalty than AQMs
generally assume they are giving. This is a related problem to having too
small a receive window.

I happened to be doing some thinking about TCP Pacing yesterday, and how it
might compare to or be convertible into a truly rate based TCP congestion
control. It might be relevant to summarise my thoughts here:

Pacing is generally thought of as spreading the transmission times of
individual packets throughout the RTT interval corresponding to each
congestion window. This is straightforward to implement in theory -
calculate the earliest permitted transmission time of packet N+1 as the
transmission time of packet N plus the length of packet N multiplied by the
RTT estimate divided by the congestion window length (in bytes).

This construct assumes the availability of a high resolution timer for
scheduling packets, but so does Bob's proposal.

The equation above does not include a term for where in the window the
packet lies. This is intentional - that information is not needed. If
pacing is thus applied even to packets transmitted out of order (ie.
retransmissions), and the test against the end of the cwnd in existing TCP
is removed (but not, of course, the rwnd test), then we easily get a rate
based TCP congestion control which, as it turns out, can scale down to a
single segment cwnd without incurring the risk of a single packet drop
causing an RTO.

It is then relatively straightforward to extend this behaviour to cope with
sub-segment cwnd, either by measuring cwnd in bytes rather than segments,
or by introducing a scale factor for RTTe which is incremented in lieu of
attempting to halve a cwnd of 1.

- Jonathan Morton

[-- Attachment #2: Type: text/html, Size: 2662 bytes --]

[Cake] lower bounds for latency

[Benjamin Cronce]

[-- Attachment #1: Type: text/plain, Size: 7126 bytes --]

> [Cake] lower bounds for latency
>
> David Lang david at lang.hm
> Fri Jun 5 20:08:54 PDT 2015
> Previous message: [Cake] lower bounds for latency
> Next message: [Cake] lower bounds for latency
> Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
> On Fri, 5 Jun 2015, Dave Taht wrote:
>
> > On Fri, Jun 5, 2015 at 6:02 PM, David Lang <david at lang.hm> wrote:
> >> On Fri, 5 Jun 2015, Dave Taht wrote:
> >>
> >>> bob's been up to good stuff lately..
> >>>
> >>> http://bobbriscoe.net/projects/latency/sub-mss-w.pdf
> >>
> >>
> >> one thing that looks wrong to me. He talks about how TCP
implementations
> >> cannot operate at less than two packets per RTT. It's not clear what he
> >> means. Does he mean two packets in flight per RTT? or two packets
worth of
> >> buffering per RTT?
> >
> > Flight.
>
> In that case I think his analysis of the effects of AQM are incorrect
because
> they only limit the buffer size on one device, not the number of packets
in
> flight.

I think what he was getting after is if you have a low provisioned
bandwidth and a really low ping, TCP effectively has a lower bound on how
slow it will go. Say you have a 1ms ping to a CDN in your ISP's network,
but your ISP only provisioned you 1Mb of bandwidth. Since all current TCP
implementations require at least 2 segments in flight, this puts a lower
bound on how slowly TCP will send those segments. (1500*2)/1ms = 12Mb/s.
Even though you have a 1Mb connection, TCP will flood your connection with
12Mb and will not back off, even with packetloss signalling to back off.
The example in the paper is a lot more realistic than my extreme example.
Several streams with a 6ms ping, putting a lower bound of (1500*2)/6ms =
4Mb/s per stream.

>
>
> He uses the example of 12 connections totaling 40Mb with a 6ms RTT. What
if the
> systems are in the same rack and have <1ms RTT? according to him TCP just
won't
> work.

If the system's are in the same rack, the choke points are probably
somewhere other than the backplane of the switch, like the CPU, harddrive,
or possibly even the port. In datacenters, it's relatively easy to throw
more bandwidth at the problem.

>
> > I also disagree with this statement:
> >
> > "It is always wrong to send smaller packets more
> > often, because the constraint may be packet pro-
> > cessing, not bits."
> >
> > because I believe (but would have to go look at some data to make
> > sure) that we're good with packet sizes down into the 300 byte range
> > on most hardware, and thus could (and SHOULD) also reduce the mss in
> > these cases to keep the "signal strength" up at a sustainable levels.
> >
> > I do recall that bittorrent used to reduce the mss and were asked to
> > stop (a decade ago), when they got as far down as 600 bytes or so.
> >
> > but the rest I quite liked.
>
> I think it depends on the speed of the link. At the very low end (cheap
home
> routers) and the very high end (multiple links >10Gb/s) the available
processing
> per packet may be a limit. But in the huge middle ground between these
extremes,
> you have quite a bit of cpu time per packet. The 3800 at 100Mb is an
example of
> running into this limit, but at 10Mb it has no problem. The WRT1200 with
it's
> dual-core GHz+ cpu has a lot of processor available for a bit more money.
From
> there up until the large datacenter/ISP cores with multiple 10Gb ports to
> manage, you hae pleanty of cpu.
>
> The other issue is the length of the 'dead air' between packets. The
current
> standards have this being a fixed amount of time. combined with the
'wasted'
> packet header data results in the same amount of data using less total
time if
> it's sent in fewer, larger packets than in smaller packets. when you are
pushing
> the limits of the wire, this can make a difference.
>
> This is why wifi tries to combine multiple packets into one transmission.
>
> <rant>
> We just need to break people of the mindset that it makes sense to hold
off on
> transmitting something "just in case" something more comes along that
could be
> combiend with it.
>
> Instead they need to start off tranmitting the first one that comes along
> without any wait, and then in the future, check the queue to see if
there's
> something else that can be combined with what you are ready to transmit,
and if
> so, send it at the same time. Rsyslog implements exactly this algorithm
in how
> it batches log messages that it's processing, the first message gets the
minimum
> delay and future messages only get as much delay as is required to keep
things
> moving. It does mean that the process hits continuous processing sooner
(where
> there is no delay between finishing working on one batch and starting
work on
> the next), but that 'always busy' point is not peak throughput, as
batches are
> more efficient to process, the throughput keeps climbing while the
latency
> climbs at a much lower rate (eventually you do hit a solid wall where
larger
> batches don't help, so you just fall behind until traffic slows)
> </rant>
>
> >>
> >> Two packets in flight per RTT would make sense as a minimum, but two
packets
> >> worth of buffering on N devices in the path doesn't.
> >>
> >> using the example of a 6ms RTT. Depending on the equipment involved,
this
> >> could have from one to several devices handling the packets between the
> >> source and the destination. Saying that each device in the path must
have
> >> two packets worth of buffering doesn't make sense. At a given line
speed and
> >> data rate, you will have X packets in flight. the number of devices
between
> >> the source and the destination will not change X.
> >
> > Flight.
> >
> >> If the requirement is that there are always at least two packets in
flight
> >> in a RTT, it doesn't then follow that both packets are going to be in
the
> >> buffer of the same device at the same time. I spoke with a vendor
promising
> >> 7ms Los Angeles to Los Vegas. For the vast majority of that 7ms the
packets
> >> are not in the buffers of the routers, but exist only as light in the
fiber
> >> (I guess you could view the fiber acting as a buffer in such
conditions)
> >>
> >> where is the disconnect between my understanding and what Bob is
talking
> >> about?
> >
> > Flight, not buffering. Redefining the goal of an aqm to keep packets
> > in flight rather than achieve a fixed queuing delay is what this is
> > about, and improving tcps to also keep packets in flight with
> > subpacket windows is part of his answer.
> >
> > I like getting away from a target constant for delay (why 5ms when 5us
> > is doable) and this is an interesting way to think about it from both
> > ends.
>
> I agree, the idea of trying to maintain a fixed buffer delay is not what
we're
> trying to do, we're trying for the minimum amount of uneccessary buffer
delay.
> The 'target' numbers are just the point where we say the delay is so bad
that
> the traffic must be slowed.
>
> > And I was nattering about how I didn't like delayed acks just a few
hours ago.
>
> what we need is a TCP stack that can combine acks that arrive separately
over
> time and only send one.
>
> David Lang

[-- Attachment #2: Type: text/html, Size: 9562 bytes --]