/** * Process a SENDME and update the congestion window according to the * rules specified in TOR_VEGAS of Proposal #324. * * Essentially, this algorithm attempts to measure queue lengths on * the circuit by subtracting the bandwidth-delay-product estimate * from the current congestion window. * * If the congestion window is larger than the bandwidth-delay-product, * then data is assumed to be queuing. We reduce the congestion window * in that case. * * If the congestion window is smaller than the bandwidth-delay-product, * then there is spare bandwidth capacity on the circuit. We increase the * congestion window in that case. * * The congestion window is updated only once every congestion window worth of * packets, even if the signal persists. It is also updated whenever the * upstream orcon blocks, or unblocks. This minimizes local client queues. */
/** * Upon receipt of a SENDME, pop the oldest timestamp off the timestamp * list, and use this to update RTT. * * Returns true if circuit estimates were successfully updated, false * otherwise. */ bool congestion_control_update_circuit_estimates(congestion_control_t *cc, constcircuit_t *circ) { uint64_t now_usec = monotime_absolute_usec();
/** * Called when we get a SENDME. Updates circuit RTT by pulling off a * timestamp of when we sent the CIRCWINDOW_INCREMENT-th cell from * the queue of such timestamps, and comparing that to current time. * * Also updates min, max, and EWMA of RTT. * * Returns the current circuit RTT in usecs, or 0 if it could not be * measured (due to clock jump, stall, etc). */ STATIC uint64_t congestion_control_update_circuit_rtt(congestion_control_t *cc, uint64_t now_usec) { uint64_t rtt, ewma_cnt; uint64_t sent_at_timestamp;
tor_assert(cc);
/* Get the time that we sent the cell that resulted in the other * end sending this sendme. Use this to calculate RTT */ sent_at_timestamp = dequeue_timestamp(cc->sendme_pending_timestamps);
rtt = now_usec - sent_at_timestamp;
/* Do not update RTT at all if it looks fishy */ if (time_delta_stalled_or_jumped(cc, cc->ewma_rtt_usec, rtt)) { num_clock_stalls++; /* Accounting */ return0; }
if (rtt > cc->max_rtt_usec) { cc->max_rtt_usec = rtt; }
if (cc->min_rtt_usec == 0) { // If we do not have a min_rtt yet, use current ewma cc->min_rtt_usec = cc->ewma_rtt_usec; } elseif (cc->cwnd == cc->cwnd_min && !cc->in_slow_start) { // Raise min rtt if cwnd hit cwnd_min. This gets us out of a wedge state // if we hit cwnd_min due to an abnormally low rtt. uint64_t new_rtt = percent_max_mix(cc->ewma_rtt_usec, cc->min_rtt_usec, rtt_reset_pct);
staticratelim_t rtt_notice_limit = RATELIM_INIT(300); log_fn_ratelim(&rtt_notice_limit, LOG_NOTICE, LD_CIRC, "Resetting circ RTT from %"PRIu64" to %"PRIu64" due to low cwnd", cc->min_rtt_usec/1000, new_rtt/1000);
cc->min_rtt_usec = new_rtt; num_rtt_reset++; /* Accounting */ } elseif (cc->ewma_rtt_usec < cc->min_rtt_usec) { // Using the EWMA for min instead of current RTT helps average out // effects from other conns cc->min_rtt_usec = cc->ewma_rtt_usec; }
/** * Called when we get a SENDME. Updates the bandwidth-delay-product (BDP) * estimates of a circuit. Several methods of computing BDP are used, * depending on scenario. While some congestion control algorithms only * use one of these methods, we update them all because it's quick and easy. * * - now_usec is the current monotime in usecs. * - curr_rtt_usec is the current circuit RTT in usecs. It may be 0 if no * RTT could bemeasured. * * Returns true if we were able to update BDP, false otherwise. */ staticbool congestion_control_update_circuit_bdp(congestion_control_t *cc, constcircuit_t *circ, uint64_t curr_rtt_usec) { int chan_q = 0; unsignedint blocked_on_chan = 0;
tor_assert(cc);
if (CIRCUIT_IS_ORIGIN(circ)) { /* origin circs use n_chan */ chan_q = circ->n_chan_cells.n; blocked_on_chan = circ->circuit_blocked_on_n_chan; } else { /* Both onion services and exits use or_circuit and p_chan */ chan_q = CONST_TO_OR_CIRCUIT(circ)->p_chan_cells.n; blocked_on_chan = circ->circuit_blocked_on_p_chan; }
/* If we have no EWMA RTT, it is because monotime has been stalled * or messed up the entire time so far. Set our BDP estimates directly * to current cwnd */ if (!cc->ewma_rtt_usec) { uint64_t cwnd = cc->cwnd;
tor_assert_nonfatal(cc->cwnd <= cwnd_max);
/* If the channel is blocked, keep subtracting off the chan_q * until we hit the min cwnd. */ if (blocked_on_chan) { /* Cast is fine because we're less than int32 */ if (chan_q >= (int64_t)cwnd) { log_notice(LD_CIRC, "Clock stall with large chanq: %d %"PRIu64, chan_q, cwnd); cwnd = cc->cwnd_min; } else { cwnd = MAX(cwnd - chan_q, cc->cwnd_min); } cc->blocked_chan = 1; } else { cc->blocked_chan = 0; }
cc->bdp = cwnd;
staticratelim_t dec_notice_limit = RATELIM_INIT(300); log_fn_ratelim(&dec_notice_limit, LOG_NOTICE, LD_CIRC, "Our clock has been stalled for the entire lifetime of a circuit. " "Performance may be sub-optimal.");
return blocked_on_chan; }
4. 计算队列长度
1 2 3 4
if (vegas_bdp(cc) > cc->cwnd) queue_use = 0; // This should not happen anymore.. else queue_use = cc->cwnd - vegas_bdp(cc);
structvegas_params_t { /** The slow-start cwnd cap for RFC3742 */ uint32_t ss_cwnd_cap; /** The maximum slow-start cwnd */ uint32_t ss_cwnd_max; /** The queue use allowed before we exit slow start */ uint16_t gamma; /** The queue use below which we increment cwnd */ uint16_t alpha; /** The queue use above which we decrement cwnd */ uint16_t beta; /** The queue use at which we cap cwnd in steady state */ uint16_t delta; /** Weighted average (percent) between cwnd estimator and * piecewise estimator. */ uint8_t bdp_mix_pct; };