several beginner's questions about QUIC congestion control

[Dong Mo]

Dear group,

I just started to play with quic code a little bit today and have several beginner's questions....

I probably can figure these out by looking at the code.

But it will be very helpful for me to do some stuff interesting sooner if you could be so kind to answer my initial silly questions.....

1. Pacing faster than 10Mbps? alert granularity?

I saw that the pacing alter granularity is at 1ms. How small can it be? to pace at 1Gbps, we need to have a 10us timer, 10Gbps - 1us. How is this alter being implemented in QUIC? Is public QUIC using the same pacing as production-level QUIC?

I used two ways of pacing, one is dedicate one core to busy wait on rdtsc counter (very very accurate but CPU spins crazily, and bad for VM(drift of rdtsc)). The other is phtread_cond_wait(timeout), where timeout = 50-100us and do deficit counter if target pacing rate is higher than 200Mbps.(fine for CPU, not so good for accuracy).

How does quic do it (if you could point me the code and give several key words..) and how does it scale?

2. How is sender buffer/receiver buffer managed and how they are related to congestion window size?

Is quic directly using UDP's buffer only? Or is there another layer of "buffer" on top of bare UDP os buffer, which is used to do things like loss-detection, packet retransmission and all that? How does these buffer grows? Are they statically allocated? dynamically growing? what is the max size for the buffer? How efficient it is to search something(lost packet to retransmit) from the user-level buffer(if any)? How can I set the max size of the buffers? Is there a way to ignore congestion window size if I want my data transfer to only be limited by the maximum buffer size?(set it to a large value I guess? How can I directly override cwnd then?)

3. how could I explicitly set a sending rate?

I took a quick look at pacing sender, but what is the interface for me to explicitly set a sending rate if I want? I didn't see it in the pacing sender..

4. I might have asked this once, but sorry I forgot..., How could I know my packets' fate?

Is there any internal mechanism to track every packet sent out but not delivered to application? or I need to DIY it by establishing some state at onPacketSent()? If I DIY it, what is the "uuid" I should use to track for each packet? And how should I associate the congestionEvent with my tracking for packets?

If any of my question is not clear, please ask me to clarify it..

Thank you so much for helping me!

-Mo

[Dong Mo]

Sorry for my poor English,

Or is there another layer of "buffer" on top of bare UDP os buffer, which is used to do things like loss-detection, packet retransmission and all that? 

=>

Or is there another layer of "buffer",  which is used to do things like loss-detection, packet retransmission and all that, on top of bare UDP os buffer?

[Ian Swett]

I tried to answer as many as I could below.  Some are likely best by looking at the relevant code, which I provided some links to.

On Sun, Nov 16, 2014 at 7:21 PM, Dong Mo <mont...@gmail.com> wrote:

Dear group,

I just started to play with quic code a little bit today and have several beginner's questions....

I probably can figure these out by looking at the code.

But it will be very helpful for me to do some stuff interesting sooner if you could be so kind to answer my initial silly questions.....

1. Pacing faster than 10Mbps? alert granularity?

I saw that the pacing alter granularity is at 1ms. How small can it be? to pace at 1Gbps, we need to have a 10us timer, 10Gbps - 1us. How is this alter being implemented in QUIC? Is public QUIC using the same pacing as production-level QUIC?

I used two ways of pacing, one is dedicate one core to busy wait on rdtsc counter (very very accurate but CPU spins crazily, and bad for VM(drift of rdtsc)). The other is phtread_cond_wait(timeout), where timeout = 50-100us and do deficit counter if target pacing rate is higher than 200Mbps.(fine for CPU, not so good for accuracy).

How does quic do it (if you could point me the code and give several key words..) and how does it scale?

At some point, QUIC's pacing granularity is limited by the alarm granularity, as you point out.  If the alarm granularity is insufficient, QUIC's pacing will just send as many packets as it needs to make up for the elapsed time.  The nature of alarms is that they can always go off late, so pacing in userspace has to be designed with that in mind.

So QUIC's approach is a variant of the second approach, see the pacing_sender.cc

 

2. How is sender buffer/receiver buffer managed and how they are related to congestion window size?

Is quic directly using UDP's buffer only? Or is there another layer of "buffer" on top of bare UDP os buffer, which is used to do things like loss-detection, packet retransmission and all that? How does these buffer grows? Are they statically allocated? dynamically growing? what is the max size for the buffer? How efficient it is to search something(lost packet to retransmit) from the user-level buffer(if any)? How can I set the max size of the buffers? Is there a way to ignore congestion window size if I want my data transfer to only be limited by the maximum buffer size?(set it to a large value I guess? How can I directly override cwnd then?)

QUIC uses a 'buffer' on top of the bare UDP buffer for sending called the UnackedPacketMap.  It's dynamic, though there is a default max CWND of 200 packets, as mentioned in a previous post.  Loss detection is implemented in the sent packet manager and the loss detection algorithms, which are pluggable.  For receiving, data is delivered to the application as quickly as possible, but within a stream, and QUIC does in order delivery in the stream sequencer.  QUIC has per-stream and per-connection flow control.

If you want to send data as quickly as possible, you can make a send algorithm that always returns QuicTime::Zero from TimeUntilSend and uses whatever pacing rate you want, or just don't use pacing.  And ensure the receive buffer is set to a larger size than the default 256kbytes, see quic_protocol.h

 

3. how could I explicitly set a sending rate?

I took a quick look at pacing sender, but what is the interface for me to explicitly set a sending rate if I want? I didn't see it in the pacing sender..

There is a PacingRate() method on the SendAlgorithmInterface.

 

4. I might have asked this once, but sorry I forgot..., How could I know my packets' fate?

Is there any internal mechanism to track every packet sent out but not delivered to application? or I need to DIY it by establishing some state at onPacketSent()? If I DIY it, what is the "uuid" I should use to track for each packet? And how should I associate the congestionEvent with my tracking for packets?

A packet's sequence number is it's "uuid".  All tracking and retransmission is handled for you in QuicSentPacketManager.  In terms of packets fate, I'd take a look at SendAlgorithmInterface's OnCongestionEvent for congestion control, and the QuicAckNotifier if you want to know when data is delivered to the receiver.

 

If any of my question is not clear, please ask me to clarify it..

Thank you so much for helping me!

-Mo

--
You received this message because you are subscribed to the Google Groups "QUIC Prototype Protocol Discussion group" group.
To unsubscribe from this group and stop receiving emails from it, send an email to proto-quic+...@chromium.org.
To post to this group, send email to proto...@chromium.org.
For more options, visit https://groups.google.com/a/chromium.org/d/optout.

[Mo Dong]

Hey Ian,

Thank you so much!

Very helpful information! Some additional questions below:

On Sun, Nov 16, 2014 at 7:43 PM, 'Ian Swett' via QUIC Prototype Protocol Discussion group <proto...@chromium.org> wrote:

I tried to answer as many as I could below.  Some are likely best by looking at the relevant code, which I provided some links to.

On Sun, Nov 16, 2014 at 7:21 PM, Dong Mo <mont...@gmail.com> wrote:

Dear group,

I just started to play with quic code a little bit today and have several beginner's questions....

I probably can figure these out by looking at the code.

But it will be very helpful for me to do some stuff interesting sooner if you could be so kind to answer my initial silly questions.....

1. Pacing faster than 10Mbps? alert granularity?

I saw that the pacing alter granularity is at 1ms. How small can it be? to pace at 1Gbps, we need to have a 10us timer, 10Gbps - 1us. How is this alter being implemented in QUIC? Is public QUIC using the same pacing as production-level QUIC?

I used two ways of pacing, one is dedicate one core to busy wait on rdtsc counter (very very accurate but CPU spins crazily, and bad for VM(drift of rdtsc)). The other is phtread_cond_wait(timeout), where timeout = 50-100us and do deficit counter if target pacing rate is higher than 200Mbps.(fine for CPU, not so good for accuracy).

How does quic do it (if you could point me the code and give several key words..) and how does it scale?

 

At some point, QUIC's pacing granularity is limited by the alarm granularity, as you point out.  If the alarm granularity is insufficient, QUIC's pacing will just send as many packets as it needs to make up for the elapsed time.  The nature of alarms is that they can always go off late, so pacing in userspace has to be designed with that in mind.

So QUIC's approach is a variant of the second approach, see the pacing_sender.cc

 

How fine the granularity can be? What will happen if I tune it down to 10us-level, high CPU load, high variance of alarm firing? And I also noticed that in multiple places in quic_connection.cc, the alarm granularity is hard-coded as 1ms (614, 1333, 1370, 1502 and etc...). So is 1ms the lowest alarm granularity that quic framework suggests to use?

Also I am curious how the internals work? Is TimeUntilSend called every minimum alarm granularity time (tracing calls from SendAlarm::onAlarm())? Does that implies I actually cannot pace faster than 10Mbps if I am using 1ms granularity? Or is there some mechanism of deficit counter implemented? (i.e. when you say "QUIC's pacing will just send as many packets as it needs to make up for the elapsed time. ") How does this make up process happen work? I saw last_delayed_packet_sent_time and was_last_packeted_delayed, but I am missing the part where there is a "micro burst" of packets get sent out to make up for the rate mismatch...

 

2. How is sender buffer/receiver buffer managed and how they are related to congestion window size?

Is quic directly using UDP's buffer only? Or is there another layer of "buffer" on top of bare UDP os buffer, which is used to do things like loss-detection, packet retransmission and all that? How does these buffer grows? Are they statically allocated? dynamically growing? what is the max size for the buffer? How efficient it is to search something(lost packet to retransmit) from the user-level buffer(if any)? How can I set the max size of the buffers? Is there a way to ignore congestion window size if I want my data transfer to only be limited by the maximum buffer size?(set it to a large value I guess? How can I directly override cwnd then?)

QUIC uses a 'buffer' on top of the bare UDP buffer for sending called the UnackedPacketMap.  It's dynamic, though there is a default max CWND of 200 packets, as mentioned in a previous post.  Loss detection is implemented in the sent packet manager and the loss detection algorithms, which are pluggable.  For receiving, data is delivered to the application as quickly as possible, but within a stream, and QUIC does in order delivery in the stream sequencer.  QUIC has per-stream and per-connection flow control.

Got it. 

If you want to send data as quickly as possible, you can make a send algorithm that always returns QuicTime::Zero from TimeUntilSend and uses whatever pacing rate you want, or just don't use pacing.  And ensure the receive buffer is set to a larger size than the default 256kbytes, see quic_protocol.h

This is actually related to my previous question, if I have pacing enabled, and set QuicTime::Zero for TimeUntilSend, will I really get full rate blast or it is still limited by some alarm granularity?

 

 

3. how could I explicitly set a sending rate?

I took a quick look at pacing sender, but what is the interface for me to explicitly set a sending rate if I want? I didn't see it in the pacing sender..

There is a PacingRate() method on the SendAlgorithmInterface.

Ok. I see, pacing_sender wraps cubic sender whose PacingRate function returns Cwnd/rtt (roughly). The thing that actually controls pacing rate is send_alarm, which comes back to my first question. 

 

4. I might have asked this once, but sorry I forgot..., How could I know my packets' fate?

Is there any internal mechanism to track every packet sent out but not delivered to application? or I need to DIY it by establishing some state at onPacketSent()? If I DIY it, what is the "uuid" I should use to track for each packet? And how should I associate the congestionEvent with my tracking for packets?

A packet's sequence number is it's "uuid".  All tracking and retransmission is handled for you in QuicSentPacketManager.  In terms of packets fate, I'd take a look at SendAlgorithmInterface's OnCongestionEvent for congestion control, and the QuicAckNotifier if you want to know when data is delivered to the receiver.

Got it Thanks. 

[Ian Swett]

On Sun, Nov 16, 2014 at 11:59 PM, Mo Dong <mont...@gmail.com> wrote:

Hey Ian,

Thank you so much!

Very helpful information! Some additional questions below:

On Sun, Nov 16, 2014 at 7:43 PM, 'Ian Swett' via QUIC Prototype Protocol Discussion group <proto...@chromium.org> wrote:

I tried to answer as many as I could below.  Some are likely best by looking at the relevant code, which I provided some links to.

On Sun, Nov 16, 2014 at 7:21 PM, Dong Mo <mont...@gmail.com> wrote:

Dear group,

I just started to play with quic code a little bit today and have several beginner's questions....

I probably can figure these out by looking at the code.

But it will be very helpful for me to do some stuff interesting sooner if you could be so kind to answer my initial silly questions.....

1. Pacing faster than 10Mbps? alert granularity?

I saw that the pacing alter granularity is at 1ms. How small can it be? to pace at 1Gbps, we need to have a 10us timer, 10Gbps - 1us. How is this alter being implemented in QUIC? Is public QUIC using the same pacing as production-level QUIC?

I used two ways of pacing, one is dedicate one core to busy wait on rdtsc counter (very very accurate but CPU spins crazily, and bad for VM(drift of rdtsc)). The other is phtread_cond_wait(timeout), where timeout = 50-100us and do deficit counter if target pacing rate is higher than 200Mbps.(fine for CPU, not so good for accuracy).

How does quic do it (if you could point me the code and give several key words..) and how does it scale?

 

At some point, QUIC's pacing granularity is limited by the alarm granularity, as you point out.  If the alarm granularity is insufficient, QUIC's pacing will just send as many packets as it needs to make up for the elapsed time.  The nature of alarms is that they can always go off late, so pacing in userspace has to be designed with that in mind.

So QUIC's approach is a variant of the second approach, see the pacing_sender.cc

 

How fine the granularity can be? What will happen if I tune it down to 10us-level, high CPU load, high variance of alarm firing? And I also noticed that in multiple places in quic_connection.cc, the alarm granularity is hard-coded as 1ms (614, 1333, 1370, 1502 and etc...). So is 1ms the lowest alarm granularity that quic framework suggests to use?

You can say the alarm granularity is as small as you want(ie: 0ms), but it'll more CPU from more alarms being scheduled and triggering.  The alarm granularity you see in quic_connection is an optimization which prevents alarms from being rescheduled if they're "close enough" to the correct time.  

 

Also I am curious how the internals work? Is TimeUntilSend called every minimum alarm granularity time (tracing calls from SendAlarm::onAlarm())? Does that implies I actually cannot pace faster than 10Mbps if I am using 1ms granularity? Or is there some mechanism of deficit counter implemented? (i.e. when you say "QUIC's pacing will just send as many packets as it needs to make up for the elapsed time. ") How does this make up process happen work? I saw last_delayed_packet_sent_time and was_last_packeted_delayed, but I am missing the part where there is a "micro burst" of packets get sent out to make up for the rate mismatch...

There is a deficit counter implemented.  See line 65. The PacingSender is a complex bit of code to say the least, so you'll likely have to read it a few times over to understand.  Looking at the tests may be instructive as well. 

 

 

2. How is sender buffer/receiver buffer managed and how they are related to congestion window size?

Is quic directly using UDP's buffer only? Or is there another layer of "buffer" on top of bare UDP os buffer, which is used to do things like loss-detection, packet retransmission and all that? How does these buffer grows? Are they statically allocated? dynamically growing? what is the max size for the buffer? How efficient it is to search something(lost packet to retransmit) from the user-level buffer(if any)? How can I set the max size of the buffers? Is there a way to ignore congestion window size if I want my data transfer to only be limited by the maximum buffer size?(set it to a large value I guess? How can I directly override cwnd then?)

QUIC uses a 'buffer' on top of the bare UDP buffer for sending called the UnackedPacketMap.  It's dynamic, though there is a default max CWND of 200 packets, as mentioned in a previous post.  Loss detection is implemented in the sent packet manager and the loss detection algorithms, which are pluggable.  For receiving, data is delivered to the application as quickly as possible, but within a stream, and QUIC does in order delivery in the stream sequencer.  QUIC has per-stream and per-connection flow control.

Got it. 

If you want to send data as quickly as possible, you can make a send algorithm that always returns QuicTime::Zero from TimeUntilSend and uses whatever pacing rate you want, or just don't use pacing.  And ensure the receive buffer is set to a larger size than the default 256kbytes, see quic_protocol.h

This is actually related to my previous question, if I have pacing enabled, and set QuicTime::Zero for TimeUntilSend, will I really get full rate blast or it is still limited by some alarm granularity?

 

The alarm granularity only comes in for pacing.  Once you're sending, you'll continue sending until something stops you.  If you wanted to use the pacer, but not at the moment, return Zero from PacingRate() in SendAlgorithmInterface.

[Jim Roskind]

There was some evidence to suggest that "chunky pacing" may be superior to perfect packet-by-packet pacing.  By "chunky" I mean that groups of packets are sent in blasts (with no deliberate interpacket pacing/spacing in a blast), and then having a pause between blasts, so that the average send rate matches the desired overall "pacing rate." 

As a result, there may be no need to have ultra fine timers (re: 10us time that was mentioned).  This is also why the current code uses "catch up" logic (re: "deficit counter") to blast a chunk of packets when the alarm interrupt is too infrequent to support a packet-by-packet pacing rate.

Additional experimentation needs to be performed to further validate these results. We certainly didn't have a lot of experience with real-world (non-laboratory) browsers receiving anywhere near 10Gbps.