Date: Fri, 30 Jan 2009 02:39:08 +0000 (UTC) From: Lawrence Stewart <lstewart@FreeBSD.org> To: src-committers@freebsd.org, svn-src-projects@freebsd.org Subject: svn commit: r187908 - in projects/tcp_cc_8.x: share/man/man4 sys/conf sys/modules sys/modules/cc_cubic sys/netinet Message-ID: <200901300239.n0U2d8lq076983@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: lstewart Date: Fri Jan 30 02:39:08 2009 New Revision: 187908 URL: http://svn.freebsd.org/changeset/base/187908 Log: Initial import from my dev repo of a clean room kernel module implementation of the CUBIC congestion control algorithm. Needs some further testing and debug/style cleanup, but is functional in its current form. Added: projects/tcp_cc_8.x/share/man/man4/cc_cubic.4 (contents, props changed) projects/tcp_cc_8.x/sys/modules/cc_cubic/ projects/tcp_cc_8.x/sys/modules/cc_cubic/Makefile (contents, props changed) projects/tcp_cc_8.x/sys/netinet/cc_cubic.c (contents, props changed) projects/tcp_cc_8.x/sys/netinet/cc_cubic.h (contents, props changed) Modified: projects/tcp_cc_8.x/sys/conf/files projects/tcp_cc_8.x/sys/modules/Makefile Added: projects/tcp_cc_8.x/share/man/man4/cc_cubic.4 ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ projects/tcp_cc_8.x/share/man/man4/cc_cubic.4 Fri Jan 30 02:39:08 2009 (r187908) @@ -0,0 +1,60 @@ +.\" +.\" Copyright (c) 2009 Lawrence Stewart <lstewart@FreeBSD.org> +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions, and the following disclaimer, +.\" without modification, immediately at the beginning of the file. +.\" 2. The name of the author may not be used to endorse or promote products +.\" derived from this software without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR +.\" ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" $FreeBSD$ +.\" +.Dd January 22, 2009 +.Dt CC_CUBIC 4 +.Os +.Sh NAME +.Nm cc_cubic +.Nd CUBIC Congestion Control Algorithm +.Sh DESCRIPTION +The +.N +congestion control algorithm +.Ss Runtime Configuration +There are currently no tunable variables. +.Sh SEE ALSO +.Xr cc 9 +.Sh HISTORY +The +.Nm +congestion control module first appeared in +.Fx 8.0 . +.Sh AUTHORS +.An -nosplit +The +.Nm +congestion control module was written by +.An Lawrence Stewart Aq lstewart@FreeBSD.org +while studying at the Centre for Advanced Internet Architectures, +Swinburne University (http://caia.swin.edu.au/). +.Pp +This manual page was written by +.An Lawrence Stewart Aq lstewart@FreeBSD.org . +.Sh ACKNOWLEDGMENTS +Development of this software was made possible in part by a grant from the +Cisco University Research Program Fund at Community Foundation Silicon Valley. Modified: projects/tcp_cc_8.x/sys/conf/files ============================================================================== --- projects/tcp_cc_8.x/sys/conf/files Fri Jan 30 00:22:08 2009 (r187907) +++ projects/tcp_cc_8.x/sys/conf/files Fri Jan 30 02:39:08 2009 (r187908) @@ -2355,6 +2355,7 @@ netinet/ip_options.c optional inet netinet/ip_output.c optional inet netinet/raw_ip.c optional inet netinet/cc.c optional inet +netinet/cc_cubic.c optional inet netinet/cc_htcp.c optional inet netinet/sctp_asconf.c optional inet sctp netinet/sctp_auth.c optional inet sctp Modified: projects/tcp_cc_8.x/sys/modules/Makefile ============================================================================== --- projects/tcp_cc_8.x/sys/modules/Makefile Fri Jan 30 00:22:08 2009 (r187907) +++ projects/tcp_cc_8.x/sys/modules/Makefile Fri Jan 30 02:39:08 2009 (r187908) @@ -45,6 +45,7 @@ SUBDIR= ${_3dfx} \ ${_canbus} \ ${_cardbus} \ ${_cbb} \ + cc_cubic \ cc_htcp \ cd9660 \ cd9660_iconv \ Added: projects/tcp_cc_8.x/sys/modules/cc_cubic/Makefile ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ projects/tcp_cc_8.x/sys/modules/cc_cubic/Makefile Fri Jan 30 02:39:08 2009 (r187908) @@ -0,0 +1,10 @@ +# $FreeBSD$ + +.include <bsd.own.mk> + +.PATH: ${.CURDIR}/../../netinet +KMOD=cc_cubic +SRCS=cc_cubic.c + +.include <bsd.kmod.mk> + Added: projects/tcp_cc_8.x/sys/netinet/cc_cubic.c ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ projects/tcp_cc_8.x/sys/netinet/cc_cubic.c Fri Jan 30 02:39:08 2009 (r187908) @@ -0,0 +1,410 @@ +/*- + * Copyright (c) 2008-2009 Lawrence Stewart <lstewart@freebsd.org> + * All rights reserved. + * + * This software was developed while studying at the Centre for Advanced + * Internet Architectures, Swinburne University (http://caia.swin.edu.au), + * made possible in part by a grant from the Cisco University Research Program + * Fund at Community Foundation Silicon Valley. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + */ + +/* + * An implementation of the CUBIC congestion algorithm for FreeBSD, + * based on the Internet Draft "draft-rhee-tcpm-cubic-02.txt" by + * Rhee, Xu and Ha. + */ + +#include <sys/cdefs.h> +__FBSDID("$FreeBSD$"); + +#include <sys/param.h> +#include <sys/kernel.h> +#include <sys/systm.h> +#include <sys/malloc.h> +#include <sys/module.h> +#include <sys/socket.h> +#include <sys/socketvar.h> +#include <sys/time.h> + +#include <netinet/cc.h> +#include <netinet/cc_cubic.h> +#include <netinet/tcp_seq.h> +#include <netinet/tcp_timer.h> +#include <netinet/tcp_var.h> + +/* function prototypes */ +int cubic_init(struct tcpcb *tp); +void cubic_deinit(struct tcpcb *tp); +void cubic_pre_fr(struct tcpcb *tp, struct tcphdr *th); +void cubic_post_fr(struct tcpcb *tp, struct tcphdr *th); +void cubic_ack_received(struct tcpcb *tp, struct tcphdr *th); +void cubic_after_timeout(struct tcpcb *tp); +void cubic_after_idle(struct tcpcb *tp); +void cubic_ssthresh_update(struct tcpcb *tp); +void cubic_cwnd_init(struct tcpcb *tp); +void cubic_record_rtt(struct tcpcb *tp); + +struct cubic { + /* cwnd at the most recent congestion event */ + u_long max_cwnd; + /* cwnd at the previous congestion event */ + u_long prev_max_cwnd; + /* time of last congestion event in ticks */ + u_long t_last_cong; + /* minimum observed rtt in ticks */ + u_long min_rtt_ticks; + /* number of congestion events */ + u_long num_cong_events; +}; + +MALLOC_DECLARE(M_CUBIC); +MALLOC_DEFINE(M_CUBIC, "cubic data", + "Per connection data required for the CUBIC congestion algorithm"); + +/* function pointers for various hooks into the TCP stack */ +struct cc_algo cubic_cc_algo = { + .name = "cubic", + .init = cubic_init, + .deinit = cubic_deinit, + .cwnd_init = cubic_cwnd_init, + .ack_received = cubic_ack_received, + .pre_fr = cubic_pre_fr, + .post_fr = cubic_post_fr, + .after_idle = newreno_after_idle, + .after_timeout = cubic_after_timeout +}; + +void +cubic_cwnd_init(struct tcpcb *tp) +{ + struct cubic *cubic_data = CC_DATA(tp); + + newreno_cwnd_init(tp); + + /* + * Ensure we have a sane initial value for max_cwnd recorded. + * Without this here bad things happen when entries from + * the TCP hostcache get used. + */ + cubic_data->max_cwnd = tp->snd_cwnd; +} + +/* + * Initialise CUBIC on the specified TCP control block. Creates a + * new struct for CUBIC specific data and sticks a pointer to it + * in the control block + */ +int +cubic_init(struct tcpcb *tp) +{ + struct cubic *cubic_data; + + cubic_data = malloc(sizeof(struct cubic), M_CUBIC, M_NOWAIT); + + if (cubic_data == NULL) + return 1; + + /* init some key cubic values with sensible defaults */ + cubic_data->t_last_cong = ticks; + cubic_data->min_rtt_ticks = TCPTV_SRTTBASE; + cubic_data->max_cwnd = 0; + cubic_data->prev_max_cwnd = 0; + cubic_data->num_cong_events = 0; + + CC_DATA(tp) = cubic_data; + + return 0; +} + +/* + * Free the struct used to store CUBIC specific data for the specified + * TCP control block. + */ +void +cubic_deinit(struct tcpcb *tp) +{ + if (CC_DATA(tp)) + free(CC_DATA(tp), M_CUBIC); +} + +/* + * Perform any necesary tasks before we enter fast recovery + */ +void +cubic_pre_fr(struct tcpcb *tp, struct tcphdr *th) +{ + struct cubic *cubic_data = CC_DATA(tp); + + cubic_data->num_cong_events++; + + cubic_ssthresh_update(tp); + + /* + * record the current cwnd at the point of congestion so it can be used + * as the basis for resetting cwnd after exiting fr + */ + cubic_data->max_cwnd = tp->snd_cwnd; + + printf("congestion event started (max_cwnd: %ld)\n", cubic_data->max_cwnd); +} + +/* + * Decrease cwnd in the event of packet loss. + */ +void +cubic_post_fr(struct tcpcb *tp, struct tcphdr *th) +{ + struct cubic *cubic_data = CC_DATA(tp); + + /* + * grab the current time and record it so we know when the most recent + * congestion event was + */ + cubic_data->t_last_cong = ticks; + + /* fast convergence heuristic */ + if (cubic_data->max_cwnd < cubic_data->prev_max_cwnd) { + printf("fast convergence heuristic kicked in! (max_cwnd: %d\t prev_max_cwnd: %d\n", (int)cubic_data->max_cwnd, (int)cubic_data->prev_max_cwnd); + cubic_data->prev_max_cwnd = cubic_data->max_cwnd; + cubic_data->max_cwnd = (cubic_data->max_cwnd * CUBIC_FC_FACTOR) + >> CUBIC_SHIFT; + } + else + cubic_data->prev_max_cwnd = cubic_data->max_cwnd; + + /* + * if inflight data is less than ssthresh, set cwnd conservatively + * to avoid a burst of data, as suggested in the NewReno RFC. + * Otherwise, use the CUBIC method. + */ + if (th && SEQ_GT(th->th_ack + tp->snd_ssthresh, tp->snd_max)) + tp->snd_cwnd = tp->snd_max - th->th_ack + tp->t_maxseg; + else { + /* update cwnd based on beta and adjusted max_cwnd */ + tp->snd_cwnd = max(1,((CUBIC_BETA * cubic_data->max_cwnd) + >> CUBIC_SHIFT)); + printf("cubic_post_fr - cwnd: %ld\tmax_cwnd: %ld\n", tp->snd_cwnd, cubic_data->max_cwnd); + } + + printf("congestion event over\n"); +} + +void +cubic_record_rtt(struct tcpcb *tp) +{ + struct cubic *cubic_data = CC_DATA(tp); + int t_srtt_ticks = tp->t_srtt / TCP_RTT_SCALE; + + /* XXX: Should there be some hysteresis for minrtt? */ + + /* + * record the current SRTT as our minrtt if it's the smallest we've + * seen or minrtt is currently equal to its initialised value. + * Ignore srtt until a min number of samples have been taken + */ + if ((t_srtt_ticks < cubic_data->min_rtt_ticks || + cubic_data->min_rtt_ticks == TCPTV_SRTTBASE) && + (tp->t_rttupdated >= CUBIC_MIN_RTT_SAMPLES)) + cubic_data->min_rtt_ticks = max(1, t_srtt_ticks); +} + +/* + * Increase cwnd on the arrival of an ACK. + */ +void +cubic_ack_received(struct tcpcb *tp, struct tcphdr *th) +{ + struct cubic *cubic_data = CC_DATA(tp); + u_long w_newreno, w_cubic_next, ticks_since_cong; + static u_long last_print_ticks = 0; + int print = 0; + + cubic_record_rtt(tp); + + if ((tp->snd_cwnd < tp->snd_ssthresh) || + (tp->snd_ssthresh == TCP_MAXWIN << TCP_MAX_WINSHIFT) || + (cubic_data->min_rtt_ticks == TCPTV_SRTTBASE)) + newreno_ack_received(tp, th); + else { + /* num ticks since last congestion */ + ticks_since_cong = ticks - cubic_data->t_last_cong; + + if ((ticks - last_print_ticks) >= (cubic_data->min_rtt_ticks / 2)) { + + print = 1; + last_print_ticks = ticks; + } + + if (print) + printf("rtt_ticks: %ld\tticks_since_cong: %ld\n", cubic_data->min_rtt_ticks, ticks_since_cong); + + w_newreno = reno_cwnd( ticks_since_cong, + cubic_data->min_rtt_ticks, + cubic_data->max_cwnd, + tp->t_maxseg + ); + + if (print) + printf("reno_cwnd(%ld,%ld,%ld,%d): %ld\n", ticks_since_cong, cubic_data->min_rtt_ticks, cubic_data->max_cwnd, tp->t_maxseg, w_newreno); + + //w_cubic = cubic_cwnd(ticks_since_cong, cubic_data->max_cwnd, tp->t_maxseg); + //printf("cubic_cwnd(%ld,%ld,%d): %ld (w_cubic)\n", ticks_since_cong, cubic_data->max_cwnd, tp->t_maxseg, w_cubic); + + w_cubic_next = cubic_cwnd( ticks_since_cong + + cubic_data->min_rtt_ticks, + cubic_data->max_cwnd, + tp->t_maxseg + ); + + if (print) + printf("cubic_cwnd(%ld,%ld,%d): %ld (w_cubic_next)\n", ticks_since_cong + cubic_data->min_rtt_ticks, cubic_data->max_cwnd, tp->t_maxseg, w_cubic_next); + + if (print) + printf("pre\tmax_cwnd: %ld\tsnd_cwnd: %ld\tw_newreno: %ld\tw_cubic_next: %ld\n", cubic_data->max_cwnd, tp->snd_cwnd, w_newreno, w_cubic_next); + + + if (w_cubic_next < w_newreno) { + /* we are in TCP-friendly region, follow reno cwnd growth */ + tp->snd_cwnd = w_newreno; + + } else if (tp->snd_cwnd < w_cubic_next) { + /* else we are in the concave or convex growth regions */ + if (print) + printf("incr: %lu\n", (w_cubic_next * tp->t_maxseg) / tp->snd_cwnd); + //tp->snd_cwnd += max(1, (w_cubic_next - w_cubic) / tp->snd_cwnd); + //printf("incr: %d\n", max(1, (w_cubic_next - tp->snd_cwnd) / tp->t_maxseg)); + /* XXX: Test under what conditions the following will truncate */ + tp->snd_cwnd += (u_long)(((uint64_t)(w_cubic_next * tp->t_maxseg)) / tp->snd_cwnd); + } + + /* + * if we're not in slow start and we're probing for a new cwnd limit + * at the start of a connection (happens when hostcache has a relevant entry), + * keep updating our current estimate of the max_cwnd + */ + if (cubic_data->num_cong_events == 0 && + cubic_data->max_cwnd < tp->snd_cwnd) + cubic_data->max_cwnd = tp->snd_cwnd; + + if (print) + printf("post\tmax_cwnd: %ld\tsnd_cwnd: %ld\n\n", cubic_data->max_cwnd, tp->snd_cwnd); + } +} + +/* + * Reset the cwnd after a retransmission timeout + */ +void +cubic_after_timeout(struct tcpcb *tp) +{ + struct cubic *cubic_data = CC_DATA(tp); + + cubic_ssthresh_update(tp); + + /* + * grab the current time and record it so we know when the most recent + * congestion event was. Only record it when the timeout has fired more + * than once, as there is a reasonable chance the first one is a false alarm + * and may not indicate congestion. + */ + if (tp->t_rxtshift >= 2) + cubic_data->t_last_cong = ticks; + + newreno_after_timeout(tp); +} + +/* + * Update the ssthresh in the event of congestion. + */ +void +cubic_ssthresh_update(struct tcpcb *tp) +{ + /* + * on the first congestion event, set ssthresh to cwnd * 0.5, on + * subsequent congestion events, set it to cwnd * beta. + */ + if (tp->snd_ssthresh == (TCP_MAXWIN << TCP_MAX_WINSHIFT)) + tp->snd_ssthresh = tp->snd_cwnd >> 1; + else + tp->snd_ssthresh = (tp->snd_cwnd * CUBIC_BETA) >> CUBIC_SHIFT; +} + +/* + * Init the HTCP module when it is first loaded into the kernel. + * Calls the kernel function for registering a new congestion control + * algorithm + */ +static int +init_module(void) +{ + cc_register_algorithm(&cubic_cc_algo); + return 0; +} + +/* + * Called when the module is unloaded from the kernel. + */ +static int +deinit_module(void) +{ + cc_deregister_algorithm(&cubic_cc_algo); + return 0; +} + +/* + * Tell the kernel which functions to use to init and de-init the module. + */ +static int +cubic_load_handler(module_t mod, int what, void *arg) +{ + switch(what) { + case MOD_LOAD: + return init_module(); + break; + + case MOD_QUIESCE: + case MOD_SHUTDOWN: + return deinit_module(); + break; + + case MOD_UNLOAD: + return 0; + break; + + default: + return EINVAL; + break; + } +} + +/* a struct that holds basic data on the module */ +static moduledata_t cubic_mod = +{ + "cubic", /* module's name */ + cubic_load_handler, /* execution entry point for the module */ + NULL +}; + +DECLARE_MODULE(cubic, cubic_mod, SI_SUB_PROTO_IFATTACHDOMAIN, SI_ORDER_ANY); Added: projects/tcp_cc_8.x/sys/netinet/cc_cubic.h ============================================================================== --- /dev/null 00:00:00 1970 (empty, because file is newly added) +++ projects/tcp_cc_8.x/sys/netinet/cc_cubic.h Fri Jan 30 02:39:08 2009 (r187908) @@ -0,0 +1,200 @@ +/*- + * Copyright (c) 2008-2009 Lawrence Stewart <lstewart@freebsd.org> + * All rights reserved. + * + * This software was developed while studying at the Centre for Advanced + * Internet Architectures, Swinburne University (http://caia.swin.edu.au), + * made possible in part by a grant from the Cisco University Research Program + * Fund at Community Foundation Silicon Valley. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + * $FreeBSD$ + */ + +#ifndef _NETINET_CC_CUBIC_H_ +#define _NETINET_CC_CUBIC_H_ + +/* needed for rdtsc() (performance analysis) */ +#include <i386/include/cpufunc.h> + +/* Number of bits of precision for fixed point math calcs */ +#define CUBIC_SHIFT 8 + +#define CUBIC_SHIFT_4 32 + +/* 0.5 with a shift << 8 */ +#define RENO_BETA 128 + +/* ~0.8 with a shift << 8 */ +#define CUBIC_BETA 204 + +/* ~0.2 with a shift << 8 */ +#define ONE_MINUS_CUBIC_BETA 51 + +/* ~0.4 with a shift << 8 */ +#define CUBIC_C_FACTOR 102 + +/* CUBIC fast convergence factor ~0.9 with a shift << 8 */ +#define CUBIC_FC_FACTOR 230 + +/* Don't trust s_rtt until this many rtt samples have been taken */ +#define CUBIC_MIN_RTT_SAMPLES 8 + +/* Userspace only bits */ +#ifndef _KERNEL + +extern int hz; + +inline float +theoretical_cubic_k(double wmax_pkts) +{ + double C = 0.4; + return pow((wmax_pkts*0.2)/C, (1.0/3.0)) * pow(2, CUBIC_SHIFT); +} + +inline u_long +theoretical_cubic_cwnd(u_long ticks_since_cong, u_long wmax, u_int smss) +{ + double C = 0.4; + double wmax_pkts = wmax/(double)smss; + return smss * (wmax_pkts + + (C * pow(ticks_since_cong/(double)hz - + theoretical_cubic_k(wmax_pkts) / pow(2, CUBIC_SHIFT), 3.0))); +} + +inline u_long +theoretical_reno_cwnd( u_long ticks_since_cong, u_long rtt_ticks, u_long wmax, + u_int smss) +{ + return (wmax * 0.5) + ((ticks_since_cong/(float)rtt_ticks) * smss); +} + +#endif /* _KERNEL*/ + +/* + * calc K (adapted from Apple Computer Technical Report #KT-32) + */ +static __inline +long cubic_k(u_long wmax_pkts) +{ + register uint16_t p = 0; + register long s = 0, K = 0; + + /* (wmax * beta)/C with CUBIC_SHIFT worth of precision */ + s = ((wmax_pkts * ONE_MINUS_CUBIC_BETA) << CUBIC_SHIFT) / + CUBIC_C_FACTOR; + + //printf("s: %d\n", s); + + /* + * rebase s such that it is between 1 and 1/8 with + * a shift of CUBIC_SHIFT + */ + while (s >= 256) { + s >>= 3; /* divide by 8 */ + p++; + } + + /* s is now between 1/8 and 1 (shifted by CUBIC_SHIFT) */ + + //printf("rebased s: %d\n", s); + + /* + * Some magic constants taken from the Apple TR with appropriate shifts + * 275 == 1.072302 << CUBIC_SHIFT (8) + * 98 == 0.3812513 << CUBIC_SHIFT (8) + * 120 == 0.46946116 << CUBIC_SHIFT (8) + */ + K = (((s * 275) >> CUBIC_SHIFT) + 98) - + (((s * s * 120) >> CUBIC_SHIFT) >> CUBIC_SHIFT); + + /* + * multiply by 2^p to undo the "divide by 8" transform from the + * previous while loop + */ + return (K <<= p); +} + +/* + * Acknowledgments: Kip Macy + */ +static __inline +u_long cubic_cwnd(u_long ticks_since_cong, u_long wmax, u_int smss) +{ + long K; + int64_t cwnd; + //int64_t start, end; + + //start = rdtsc(); + + K = cubic_k(wmax / smss); + + //printf("K: %d\n", K); + + /* + * we now have K in fixed point form with + * CUBIC_SHIFT worth of precision + */ + + /* t - K, with CUBIC_SHIFT worth of precision */ + cwnd = ((int64_t)(ticks_since_cong << CUBIC_SHIFT) - (K * hz)) / hz; + + //printf("t-k: %lld\n", cwnd); + + /* (t - K)^3, with CUBIC_SHIFT^3 worth of precision */ + cwnd *= (cwnd * cwnd); + + //printf("(t-k)^3: %lld\n", cwnd); + + /* + * C(t - K)^3 + wmax + * The down shift by CUBIC_SHIFT_4 is because cwnd has 4 lots of + * CUBIC_SHIFT included in the value. 3 from the cubing of cwnd above, + * and an extra from multiplying through by CUBIC_C_FACTOR + */ + cwnd = ((cwnd * CUBIC_C_FACTOR * smss) >> CUBIC_SHIFT_4) + wmax; + + //printf("final cwnd: %lld\n", cwnd); + + //end = rdtsc(); + + //printf("%lld TSC ticks\n", end - start); + + return ((u_long)cwnd); +} + +static __inline +u_long reno_cwnd(u_long ticks_since_cong, u_long rtt_ticks, u_long wmax, + u_int smss) +{ + /* + * Simplified form of equation 4 from I-D + * For reno, beta = 0.5, therefore W_tcp(t) = wmax*0.5 + t/RTT + * Equation 4 deals with cwnd/wmax in pkts, so because our cwnd is + * in bytes, we have to multiply by smss + */ + return (((wmax * RENO_BETA) + (((ticks_since_cong * smss) + << CUBIC_SHIFT) / rtt_ticks)) >> CUBIC_SHIFT); +} + +#endif /* _NETINET_CC_CUBIC_H_ */
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200901300239.n0U2d8lq076983>