Refactor Cubic, D-Cubic and Prague code

[huitema]

The code supports multiple congestion control algorithms, spread onto multiple binaries: cc_common.c, newreno.c, cubic.c and prague.c. The common and newreno parts are well tested, but the coverage of cubic.c and prague.c is limited. For cubic.c, we have some duplication of code between the standard version and the delay based version, dcubic. Code inspection also shows that the "recovery" state of cubic is not well implemented. The prague code is very similar to the new reno code, the main difference being the handling of ECN signals.

These algorithms all have the same basic state machine:

• a startup phase, implemented as hystart, using code from cc_common.c,
• a congestion avoidance phase, during which different algorithms use different logic,
• a recovery phase, during which the congestion control state is frozen until acknowledgement of new packets is received.

That commonality could be used to put more code components in common.

[hfstco]

master...hfstco:picoquic:cc-cleanup

Currently working on it, because I have already did some modifications/cleanup to cubic.c while implementing HyStart++.

I will give an update until the end of the week. I will take a look dcubic and prague to have a good overview of duplicate code and the similarities of the implementations. Then it is easier to discuss about changes and coverage.

[huitema]

The way I look at it, I see the following commonality and differences:

1. Apart from Reno, all algorithms start with Hystart. It would make sense to add two options to Hystart: monitoring of ECN as specified in Prague, and second phase with 25% growth as in Hystart++.
2. "Pure" Reno should use Van Jacobson's original slow start. But the only point to use that today is for testing against the original version. For a real deployment, Hystart makes much more sense.
3. In congestion avoidance mode, New Reno growth the CWND by 1 packet every CWND packets. Prague does the same, but modulate the growth based on the rate of ECN packets. That kind of difference can be easily handled by a state variable.
4. In congestion avoidance mode, Cubic and DCubic grow the Window per the Cubic equation.
5. The current implementation of DCubic only reacts to delay variations, ignoring packet losses. This is probably a mistake. Both Cubic and DCubic implementations should react to high packet loss, i.e., compute a recent packet loss rate and exit if that reaches a threshold. In fact, the same should be done with Reno and Prague, meaning common code between all these algorithms.
6. The difference between Cubic and DCubic should only be the handling of delay variations. Cubic ignores them, DCubic uses them as a signal to exit congestion avoidance and start a new era.
7. When starting a new era, Cubic uses a coefficient Beta to reduce the CWND. There are three potential ways to enter a new era: after packet losses, after excess ECN rate, and after delay measurements. It might make sense to use different values of Beta in all three cases -- maybe the original 3/4 in case of packet loss, but only 7/8 in case of ECN or excess delay. Maybe use the ECN rate to modulate Beta like Prague does. This would treat loss-driven restart as a harsher signal than delay or ECN driven, which would fit well with real time applications.
8. The standard version of Reno would not use ECN, and the standard version of Prague would not use delay, but this can be managed using state variables.
9. If we use different betas, we could have different "recovery" state: in case of loss, transition to the lower value of Beta.
10. All algorithms should handle "app limited" scenario -- do not increase the window if the congestion is app limited.

[hfstco]

There are many code parts that can be put into cc_common.c. But I like that each CC algorithm has its own code file/notify function. If I look into one of the CC notify functions, I want to understand what is happening.

Apart from Reno, all algorithms start with Hystart. It would make sense to add two options to Hystart: monitoring of ECN as specified in Prague, and second phase with 25% growth as in Hystart++.

In congestion avoidance mode, New Reno growth the CWND by 1 packet every CWND packets. Prague does the same, but modulate the growth based on the rate of ECN packets. That kind of difference can be easily handled by a state variable.

I have implemented Slow Start in cc_common.c for every CC algorithm. They are built on each other to support SS, CSS and Prague beta-dependent growth of CWND.

"Pure" Reno should use Van Jacobson's original slow start. But the only point to use that today is for testing against the original version.

So you are talking about the newreno_sim code, right?

In congestion avoidance mode, Cubic and DCubic grow the Window per the Cubic equation.

The current implementation of DCubic only reacts to delay variations, ignoring packet losses. This is probably a mistake. Both Cubic and DCubic implementations should react to high packet loss, i.e., compute a recent packet loss rate and exit if that reaches a threshold. In fact, the same should be done with Reno and Prague, meaning common code between all these algorithms.

The difference between Cubic and DCubic should only be the handling of delay variations. Cubic ignores them, DCubic uses them as a signal to exit congestion avoidance and start a new era.

I have made many changes to DCubic. Currently, in many cases, DCubic just redirects the Cubic notify function, except for the delay variations. This also applies to packet loss. I have to avoid calculating the pacing rate twice. A simple fix would be a simple return instead of a break. But I think there would be another, more beautiful solution.
Is there a document that describes DCubic's behaviour?

Is there a document which describes the behavior of DCubic?

When starting a new era, Cubic uses a coefficient Beta to reduce the CWND. There are three potential ways to enter a new era: after packet losses, after excess ECN rate, and after delay measurements. It might make sense to use different values of Beta in all three cases -- maybe the original 3/4 in case of packet loss, but only 7/8 in case of ECN or excess delay. Maybe use the ECN rate to modulate Beta like Prague does. This would treat loss-driven restart as a harsher signal than delay or ECN driven, which would fit well with real time applications.

That sounds good in general. But as described in RFC 9438, we should reduce our CWND by a factor of 0.7/coefficient Beta. Where are these different values from? With values above 0.5, we risk a second round of congestion/losses. Of course, fixed values are much easier to implement than an ECN rate-based Beta.

If we use different betas, we could have different "recovery" state: in case of loss, transition to the lower value of Beta.

Yes. But my coverage results show me, that our recovery phase picoquic_cubic_alg_recovery isn't entered anyway. (e.g. picoquic_cubic_enter_recovery()) It is entered but immediately exits to congestion avoidance (or slow start if CWND < INITIAL_CWIN or timeout). I don't know if It is intended, but the current implementation of the recovery state variable in cubic doesn't make sense.

All algorithms should handle "app limited" scenario -- do not increase the window if the congestion is app limited.

"app limited" scenario as specified in RFC 9002 Section 7.8?
https://datatracker.ietf.org/doc/html/rfc9002#name-underutilizing-the-congesti
Following line is a little bit confusing. How should it protect against limited senders?
/* Protection against limited senders. */ if (cubic_state->start_of_epoch < path_x->last_sender_limited_time) { cubic_state->start_of_epoch = path_x->last_sender_limited_time; }
Isn't following line responsible to ensure our sender is not app limited?
if (path_x->last_time_acked_data_frame_sent > path_x->last_sender_limited_time) {

HyStart is split in two parts according to "Taming the elephants: New TCP slow start":

1. ACK train length
2. delay increase
   Can you shortly explain the relation picoquic_hystart_loss_test, picoquic_hystart_loss_volume_test, picoquic_hystart_test and HyStart?
   picoquic_hystart_loss(_volume)_test checks if high packet/byte loss occur (based on a threshold) and picoquic_hystart_test does look like the delay increase check for HyStart.

[huitema]

DCubic was an experiment in which I initially replaced testing for packet losses by testing for delay variations. There were two objective: not be so sensitive to packet losses; and, avoid buffer bloat. The part about "not so sensitive" to packet losses is not justified today, since we react to loss rate rather than individual losses. We could just use the same behavior as Cubic. The part about "exit congestion avoidance on delay increase" is more interesting, and that's really what we want to keep in a first phase.

If we want to productize that, we will have to solve the classic delay-based issues like preference for late comers, or delay drift. We will also need to solve the "compete with Cubic" situation -- DCubic is more polite than Cubic, so if competing it gets a much lower share of the bandwidth. But that can wait.

For Reno, Prague and Cubic, app limited can be defined as "bytes in flight lower than CWIND". If that condition is true, the window should stay as is. It is more complicted with BBR, but then everything is.

BBR being complicated is why I would like to add delay measurements and Prague-like ECN feedback to Cubic -- that could get us a protocol with latency effects similar to BBR, but much simpler and much easier to implement.

picoquic_hystart_test is the delay increase check for HyStart, but with a jitter filter added. The jitter filter removes a lot of the "false exit" issues with HyStart, especially on wireless links. I will have to go look at the code to explain picoquic_hystart_loss(_volume)_test, but the idea ought to be, maintain an average loss rate experienced in the short term, and use that to trigger loss based exit of slow start or congestion avoidance.