Page MenuHomeFreeBSD
Differential D40436 Diff 122904 sys/netinet/cc/cc_cubic.h

Changeset View

Standalone View

View Options

sys/netinet/cc/cc_cubic.h

Show First 20 Lines • Show All 87 Lines • ▼ Show 20 Lines
/* Kernel only bits */ /* Kernel only bits */
#ifdef _KERNEL #ifdef _KERNEL
struct cubic { struct cubic {
/* CUBIC K in fixed point form with CUBIC_SHIFT worth of precision. */ /* CUBIC K in fixed point form with CUBIC_SHIFT worth of precision. */
int64_t K; int64_t K;
/* Sum of RTT samples across an epoch in usecs. */ /* Sum of RTT samples across an epoch in usecs. */
int64_t sum_rtt_usecs; int64_t sum_rtt_usecs;
/* cwnd at the most recent congestion event. */ /* Size of cwnd just before cwnd was reduced in the last congestion event */
unsigned long max_cwnd; uint64_t W_max;
/* cwnd at the previous congestion event. */ /* An estimate for the congestion window in the Reno-friendly region */
unsigned long prev_max_cwnd; uint64_t W_est;
/* A copy of prev_max_cwnd. Used for CC_RTO_ERR */ /* The cwnd at the beginning of the current congestion avoidance stage */
unsigned long prev_max_cwnd_cp; uint64_t cwnd_epoch;
/*
* Size of cwnd at the time of setting ssthresh most recently,
* either upon exiting the first slow start, or just before cwnd
* was reduced in the last congestion event
*/
uint64_t cwnd_prior;
/* various flags */ /* various flags */
uint32_t flags; uint32_t flags;
/* Minimum observed rtt in usecs. */ /* Minimum observed rtt in usecs. */
int min_rtt_usecs; int min_rtt_usecs;
/* Mean observed rtt between congestion epochs. */ /* Mean observed rtt between congestion epochs. */
int mean_rtt_usecs; int mean_rtt_usecs;
/* ACKs since last congestion event. */ /* ACKs since last congestion event. */
int epoch_ack_count; int epoch_ack_count;
/* Timestamp (in ticks) of arriving in congestion avoidance from last /* Timestamp (in ticks) at which the current CA epoch started. */
* congestion event. int t_epoch;
*/ /* Timestamp (in ticks) at which the previous CA epoch started. */
int t_last_cong; int undo_t_epoch;
/* Timestamp (in ticks) of a previous congestion event. Used for /* Few variables to restore the state after RTO_ERR */
* CC_RTO_ERR. int64_t undo_K;
*/ uint64_t undo_cwnd_prior;
int t_last_cong_prev; uint64_t undo_W_max;
uint64_t undo_W_est;
uint64_t undo_cwnd_epoch;
/* Number of congestion events experienced */
uint64_t num_cong_events;
uint32_t css_baseline_minrtt; uint32_t css_baseline_minrtt;
uint32_t css_current_round_minrtt; uint32_t css_current_round_minrtt;
uint32_t css_lastround_minrtt; uint32_t css_lastround_minrtt;
uint32_t css_rttsample_count; uint32_t css_rttsample_count;
uint32_t css_entered_at_round; uint32_t css_entered_at_round;
uint32_t css_current_round; uint32_t css_current_round;
uint32_t css_fas_at_css_entry; uint32_t css_fas_at_css_entry;
uint32_t css_lowrtt_fas; uint32_t css_lowrtt_fas;
Show All 18 Linestheoretical_cubic_k(double wmax_pkts)
double C; double C;
C = 0.4; C = 0.4;
return (pow((wmax_pkts * 0.3) / C, (1.0 / 3.0)) * pow(2, CUBIC_SHIFT)); return (pow((wmax_pkts * 0.3) / C, (1.0 / 3.0)) * pow(2, CUBIC_SHIFT));
} }
static __inline unsigned long static __inline unsigned long
theoretical_cubic_cwnd(int ticks_since_cong, unsigned long wmax, uint32_t smss) theoretical_cubic_cwnd(int ticks_since_epoch, unsigned long wmax, uint32_t smss)
{ {
double C, wmax_pkts; double C, wmax_pkts;
C = 0.4; C = 0.4;
wmax_pkts = wmax / (double)smss; wmax_pkts = wmax / (double)smss;
return (smss * (wmax_pkts + return (smss * (wmax_pkts +
(C * pow(ticks_since_cong / (double)hz - (C * pow(ticks_since_epoch / (double)hz -
theoretical_cubic_k(wmax_pkts) / pow(2, CUBIC_SHIFT), 3.0)))); theoretical_cubic_k(wmax_pkts) / pow(2, CUBIC_SHIFT), 3.0))));
} }
static __inline unsigned long static __inline unsigned long
theoretical_reno_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, theoretical_reno_cwnd(int ticks_since_epoch, int rtt_ticks, unsigned long wmax,
uint32_t smss) uint32_t smss)
{ {
return ((wmax * 0.5) + ((ticks_since_cong / (float)rtt_ticks) * smss)); return ((wmax * 0.5) + ((ticks_since_epoch / (float)rtt_ticks) * smss));
} }
static __inline unsigned long static __inline unsigned long
theoretical_tf_cwnd(int ticks_since_cong, int rtt_ticks, unsigned long wmax, theoretical_tf_cwnd(int ticks_since_epoch, int rtt_ticks, unsigned long wmax,
uint32_t smss) uint32_t smss)
{ {
return ((wmax * 0.7) + ((3 * 0.3) / (2 - 0.3) * return ((wmax * 0.7) + ((3 * 0.3) / (2 - 0.3) *
(ticks_since_cong / (float)rtt_ticks) * smss)); (ticks_since_epoch / (float)rtt_ticks) * smss));
} }
#endif /* !_KERNEL */ #endif /* !_KERNEL */
/* /*
* Compute the CUBIC K value used in the cwnd calculation, using an * Compute the CUBIC K value used in the cwnd calculation, using an
* implementation of eqn 2 in the I-D. The method used * implementation of eqn 2 in the I-D. The method used
* here is adapted from Apple Computer Technical Report #KT-32. * here is adapted from Apple Computer Technical Report #KT-32.
Show All 30 Lines
/* /*
* Compute the new cwnd value using an implementation of eqn 1 from the I-D. * Compute the new cwnd value using an implementation of eqn 1 from the I-D.
* Thanks to Kip Macy for help debugging this function. * Thanks to Kip Macy for help debugging this function.
* *
* XXXLAS: Characterise bounds for overflow. * XXXLAS: Characterise bounds for overflow.
*/ */
static __inline unsigned long static __inline unsigned long
cubic_cwnd(int usecs_since_cong, unsigned long wmax, uint32_t smss, int64_t K) cubic_cwnd(int usecs_since_epoch, unsigned long wmax, uint32_t smss, int64_t K)
{ {
int64_t cwnd; int64_t cwnd;
/* K is in fixed point form with CUBIC_SHIFT worth of precision. */ /* K is in fixed point form with CUBIC_SHIFT worth of precision. */
/* t - K, with CUBIC_SHIFT worth of precision. */ /* t - K, with CUBIC_SHIFT worth of precision. */
cwnd = (((int64_t)usecs_since_cong << CUBIC_SHIFT) - (K * hz * tick)) / cwnd = (((int64_t)usecs_since_epoch << CUBIC_SHIFT) - (K * hz * tick)) /
(hz * tick); (hz * tick);
if (cwnd > CUBED_ROOT_MAX_ULONG) if (cwnd > CUBED_ROOT_MAX_ULONG)
return INT_MAX; return INT_MAX;
if (cwnd < -CUBED_ROOT_MAX_ULONG) if (cwnd < -CUBED_ROOT_MAX_ULONG)
return 0; return 0;
/* (t - K)^3, with CUBIC_SHIFT^3 worth of precision. */ /* (t - K)^3, with CUBIC_SHIFT^3 worth of precision. */
Show All 20 Lines
* measured over the previous congestion epoch and wmax is the value of cwnd at * measured over the previous congestion epoch and wmax is the value of cwnd at
* the last congestion event. The "TCP friendly" concept in the CUBIC I-D is * the last congestion event. The "TCP friendly" concept in the CUBIC I-D is
* rather tricky to understand and it turns out this function is not required. * rather tricky to understand and it turns out this function is not required.
* It is left here for reference. * It is left here for reference.
* *
* XXX: Not used * XXX: Not used
*/ */
static __inline unsigned long static __inline unsigned long
reno_cwnd(int usecs_since_cong, int rtt_usecs, unsigned long wmax, reno_cwnd(int usecs_since_epoch, int rtt_usecs, unsigned long wmax,
uint32_t smss) uint32_t smss)
{ {
/* /*
* For NewReno, beta = 0.5, therefore: W_tcp(t) = wmax*0.5 + t/RTT * For NewReno, beta = 0.5, therefore: W_tcp(t) = wmax*0.5 + t/RTT
* W_tcp(t) deals with cwnd/wmax in pkts, so because our cwnd is in * W_tcp(t) deals with cwnd/wmax in pkts, so because our cwnd is in
* bytes, we have to multiply by smss. * bytes, we have to multiply by smss.
*/ */
return (((wmax * RENO_BETA) + (((usecs_since_cong * smss) return (((wmax * RENO_BETA) + (((usecs_since_epoch * smss)
<< CUBIC_SHIFT) / rtt_usecs)) >> CUBIC_SHIFT); << CUBIC_SHIFT) / rtt_usecs)) >> CUBIC_SHIFT);
} }
/* /*
* Compute an approximation of the "TCP friendly" cwnd some number of usecs * Compute an approximation of the "TCP friendly" cwnd some number of usecs
* after a congestion event that is designed to yield the same average cwnd as * after a congestion event that is designed to yield the same average cwnd as
* NewReno while using CUBIC's beta of 0.7. RTT should be the average RTT * NewReno while using CUBIC's beta of 0.7. RTT should be the average RTT
* estimate for the path measured over the previous congestion epoch and wmax is * estimate for the path measured over the previous congestion epoch and wmax is
* the value of cwnd at the last congestion event. * the value of cwnd at the last congestion event.
*/ */
static __inline unsigned long static __inline unsigned long
tf_cwnd(int usecs_since_cong, int rtt_usecs, unsigned long wmax, tf_cwnd(int usecs_since_epoch, int rtt_usecs, unsigned long wmax,
uint32_t smss) uint32_t smss)
{ {
/* Equation 4 of I-D. */ /* Equation 4 of I-D. */
return (((wmax * CUBIC_BETA) + return (((wmax * CUBIC_BETA) +
(((THREE_X_PT3 * (unsigned long)usecs_since_cong * (((THREE_X_PT3 * (unsigned long)usecs_since_epoch *
(unsigned long)smss) << CUBIC_SHIFT) / (TWO_SUB_PT3 * rtt_usecs))) (unsigned long)smss) << CUBIC_SHIFT) / (TWO_SUB_PT3 * rtt_usecs)))
>> CUBIC_SHIFT); >> CUBIC_SHIFT);
} }
#endif /* _NETINET_CC_CUBIC_H_ */ #endif /* _NETINET_CC_CUBIC_H_ */