Improving application limited tests for BBR

[alexrabi]

As discussed in #1758, the current "application limited" test with BBR is insufficient as it sometimes mistakes busty traffic for path capacity saturation. This can lead to a very poor throughput. Testing the congestion window (bytes_in_flight < cwnd) is not enough as BBR uses the pacing rate as the main control variable, with the congestion window as a "backup". In normal operation, pacing dominates and the bytes in flight remain below the congestion window. Testing on the pacing rate is also imprecise, because pacing is implemented with a leaky bucket. There will be brief period in which the leaky bucket will be full, letting packets go without pacing, only limiting the last packet out of a train -- but that can happen whether the application is "limiting" or not.

We need to come up with a solution to more accurately detect whether we are application limited or not.

[alexrabi]

I'm wondering if it is worth taking a few notes from the bufferbloat community in regards to this. The issue is being able to distinguish "good queues", i.e. queues that "absorb" bursts, but that eventually drain, from "bad queues", i.e. persistent, standing queues. If we are application limited, then the leaky bucket should act more like a good queue, rather than a bad queue.

The CoDel AQM algorithm uses the sojourn times of each packet to track the (local) minimum queue delay that packets experience. As long as the minimum queue delay is below some target threshold for some time interval, the queue is considered a good queue. Perhaps we can do something similar here to help identify application limited scenarios?

[huitema]

Damn, 4 months without a comment...

The key insight in the CoDel design is to distinguish between standing queues and transient queues, and measuring the "minimum" value of the queue rather than its maximum. I am wondering how to apply that concept in picoquic, as a typical high speed implementation will use the "just in time" API, and thus does not rely on the picoquic code to maintain queues. On the other hand, the just in time API allows implementations to mark streams or the datagram queue as "active", as in "there is data to send". The first approximation of "empty queue" would thus be "there is no data to send", and the code in picoquic_prepare_stream_and_datagrams (lines 2751 to 2941 in sender.c) manages that. There is no data to send if that function does not queue data, and also does not set the "more data" bit to indicate that there is data but it will not fit in the current packet.

The current code in sender.c will set the last_sender_limited_time1 if there was no data to send. (The "preemptive repeat" flag instructs tested here instructs that stack to repeat old data if there is nothing else to send, in which case the sender is never limited.) This is part of the following block of code in sender.c`:

                            if (length <= header_length) {
                                /* Mark the bandwidth estimation as application limited */
                                path_x->delivered_limited_index = path_x->delivered;
                                /* Notify the peer if something is blocked */
                                bytes_next = picoquic_format_blocked_frames(cnx, &bytes[length], bytes_max, &more_data, &is_pure_ack);
                                length = bytes_next - bytes;
                            }

                            if (no_data_to_send) {
                                path_x->last_sender_limited_time = current_time;
                            }

The BBR code only depends on the last_sender_limited_time in the startup phase, and only if the startup uses Hystart instead of the native BBR mechanism. In the other cases, BBR depends on path_x->delivered_limited_index. The code tests that when processing an acknowledgement, and will signal that in the ack_state variable passed to BBR (ack_state.is_app_limited). All that is fairly convoluted, which would be reason enough to try simplify it. The good news is that the test only fires if both pacing and CWIN would have allowed a packet to be sent, which means it will work for both Cubic using CWIN, and BBR using a combination of CWIN and pacing.

The main issue that I see is that the code fires the "app_limited" condition too often. Suppose the sender is "time limited" at time T, but sends data at time T+1 microsecond. The application is in fact keeping the bottleneck full, and is not app_limited. But on the other hand, setting app_limited two often only prevents BBR from reducing the bottleneck rate, and is not our problem.

@alexrabi is there a specific change that you would like to try?

[alexrabi]

Indeed, the "just in time" API complicates the problem, since the queue would be on the user application side of things, rather than in picoquic itself. As you say, if the stream and/or datagram queues are marked as active it makes sense for that to be interpreted as a persistent queue and therefore non-limited scenario. However, I feel like it is a bit too naïve to interpret a failure to queue data necessarily as a signal for "application limitation".

I'll need to mull it over a bit, since it is a complex scenario, but here are some initial thoughts:
The signalling between the application and the picoquic stack needs to be improved, since a lot of information that could be useful to picoquic will be lost when running the "just in time" API (e.g. the status of queues on the application side). For example, when marking a stream or datagrams ready to send, the application might want to signal that it is almost ready to send.

Signalling could also be further improved by allowing the application to signal roughly how much data it is/is going to be ready to send on a stream or over datagrams. That would allow picoquic to glean some information about how much queueing is going on on the application side, and could therefore act accordingly. E.g. something like:
int picoquic_mark_datagram_ready_ex(picoquic_cnx_t* cnx, int is_ready, size_t bytes_to_send) and
int picoquic_mark_active_stream_ex(picoquic_cnx_t* cnx, uint64_t stream_id, int is_active, void* v_stream_ctx, size_t bytes_to_send)

[huitema]

@alexrabi please look at PR #1903, which introduces a process for letting application control the per stream flow control. Would that fix your issue?