Skip to main content

6. Algorithm

6.1. Initialization Steps​

At the beginning of a congestion control response phase initiated by a congestion control algorithm, a data sender using PRR MUST initialize the PRR state.

The timing of when a congestion control response phase begins is entirely determined by the congestion control algorithm, for example, it may correspond to the beginning of a fast recovery phase, or it may occur each round a reduction is performed after fast recovery has already been underway upon detection of a lost retransmission or a lost original transmission.

PRR initialization allows a congestion control algorithm CongCtrlAlg() to set ssthresh to a value other than FlightSize/2 (e.g., including CUBIC [RFC9438]).

A key step in PRR initialization is computing the Recovery Flight Size (RecoverFS), which is the sender's estimate of the number of bytes that may be delivered during the current PRR phase. This can be thought of as the sum of the following values at the beginning of the phase: inflight, the bytes cumulatively acknowledged in the ACK that triggered recovery, the bytes SACKed in the ACK that triggered recovery, and the bytes already marked lost between SND.UNA and SND.NXT. RecoverFS includes losses because losses are marked using heuristics and thus during recovery some packets previously marked as lost may end up ultimately being delivered (without requiring retransmission). PRR uses RecoverFS to compute a smooth sending rate. Upon entering fast recovery, PRR initializes RecoverFS, and RecoverFS remains constant throughout a given fast recovery phase.

The full sequence of PRR algorithm initialization steps is as follows:

ssthresh = CongCtrlAlg()  // Target flight size in recovery
prr_delivered = 0          // Total bytes delivered in recovery
prr_out = 0                // Total bytes sent in recovery
RecoverFS = SND.NXT - SND.UNA  // Bytes SACKed before entering recovery

// Bytes SACKed before entering recovery will not be marked as
// delivered during recovery:
RecoverFS -= (bytes SACKed in scoreboard)

// Include selectively ACKed bytes (common case):
RecoverFS += (newly SACKed bytes)

// Include cumulatively acknowledged bytes (rare case):
RecoverFS += (newly cumulatively acknowledged bytes)

6.2. Per-ACK Steps​

On each ACK at the beginning of or during fast recovery, excluding the ACK that ends the PRR phase, PRR performs the following steps.

First, the sender computes DeliveredData, which is the data sender's best estimate of the total bytes the current ACK indicates have been delivered to the receiver since the previously received ACK. With SACK, DeliveredData can be computed precisely as the change in SND.UNA, plus the signed change in the amount of data marked SACKed in the scoreboard. Thus, in the special case when there are no SACKed sequence ranges in the scoreboard before or after an ACK, DeliveredData is the change in SND.UNA.

In a recovery without SACK, DeliveredData is estimated to be 1 SMSS on each received duplicate ACK (i.e., SND.UNA has not changed). When SND.UNA advances (i.e., a full or partial ACK), DeliveredData is the change in SND.UNA, minus 1 SMSS for each preceding duplicate ACK. Note that without SACK, a misbehaving receiver that returns excess duplicate ACKs (as described in [Savage99]) could try to artificially inflate DeliveredData. As a mitigation, when SACK is not in use, PRR does not allow increasing DeliveredData when the total bytes delivered in the PRR phase exceeds the estimated outstanding data upon entering recovery (RecoverFS).

Next, the sender computes inflight, which is the data sender's best estimate of the number of bytes in flight in the network. To compute inflight, a connection with SACK enabled and using [RFC6675] loss detection can use the "pipe" algorithm specified in [RFC6675]. A SACK-enabled connection using RACK-TLP loss detection [RFC8985] or other loss detection algorithms MUST compute inflight by starting with SND.NXT - SND.UNA, subtracting the bytes SACKed in the scoreboard, subtracting the bytes marked lost in the scoreboard, and adding the bytes from the scoreboard that have been retransmitted since being marked lost.

For a connection without SACK enabled, the sender MUST subtract: min(RecoverFS, 1 SMSS for each preceding duplicate ACK in the fast recovery phase); the min() with RecoverFS is to defend against a misbehaving receiver [Savage99], instead of subtracting the bytes SACKed in a SACK scoreboard.

Next, the sender computes SafeACK, a local Boolean variable indicating that the current ACK reports good progress. SafeACK is true only when the ACK cumulatively acknowledges new data and the ACK does not indicate further losses. For example, an ACK that triggers a "rescue" retransmission (Section 4 of [RFC6675], NextSeg() condition 4) may indicate further losses. Both of these conditions indicate that recovery is making good progress, and the sender can send more aggressively if appropriate, increasing inflight.

Finally, the sender uses DeliveredData, inflight, SafeACK, and other PRR state to compute SndCnt, a local variable indicating how many bytes should be sent in response to each ACK, and then uses SndCnt to update cwnd.

The full sequence of per-ACK PRR algorithm steps is as follows:

if (DeliveredData is 0)
    Return

prr_delivered += DeliveredData
inflight = (estimated amount of in-flight data)
SafeACK = (SND.UNA advanced AND no further losses indicated)

if (inflight > ssthresh) {
    // Proportional Rate Reduction
    // This uses integer division, rounding up:
    #define DIV_ROUND_UP(n, d) (((n) + (d) - 1) / (d))
    out = DIV_ROUND_UP(prr_delivered * ssthresh, RecoverFS)
    SndCnt = out - prr_out
} else {
    // Use PRR-CRB by default
    SndCnt = MAX(prr_delivered - prr_out, DeliveredData)
    if (SafeACK) {
        // Use PRR-SSRB when recovery is making good progress
        SndCnt += SMSS
    }
    // Try to catch up, as much as allowed
    SndCnt = MIN(ssthresh - inflight, SndCnt)
}

if (prr_out is 0 AND SndCnt is 0) {
    // Force fast retransmit upon entering recovery
    SndCnt = SMSS
}

cwnd = inflight + SndCnt

After the sender computes SndCnt and uses it to update cwnd, the sender transmits more data. Note that the decision of what data to send (e.g., retransmitting missing data or sending more new data) is beyond the scope of this document.

6.3. Per-Transmit Steps​

On any data transmission or retransmission, PRR performs the following:

prr_out += (data sent)

6.4. Completion Steps​

The PRR phase ends upon completing fast recovery or before starting a new PRR phase due to a new congestion control response phase.

Upon completing a PRR phase, PRR performs the following:

cwnd = ssthresh

Note that this step to set cwnd to ssthresh may in some cases allow a back-to-back burst of segments into the network.

Implementations are encouraged to use pacing to reduce the burstiness of the data flow. This encouragement is consistent with current practices to mitigate burstiness (e.g., [PACING]), including pacing transmit bursts after restarting from idle.

Last updated on