svn commit: r188043 - in projects/tcp_cc_7.x: share/man/man4 sys
sys/conf sys/modules sys/modules/cc_cubic sys/netinet
Lawrence Stewart
lstewart at FreeBSD.org
Mon Feb 2 19:46:26 PST 2009
Author: lstewart
Date: Tue Feb 3 03:46:26 2009
New Revision: 188043
URL: http://svn.freebsd.org/changeset/base/188043
Log:
Merge r187908 from tcp_cc_8.x
Added:
projects/tcp_cc_7.x/share/man/man4/cc_cubic.4
- copied unchanged from r187908, projects/tcp_cc_8.x/share/man/man4/cc_cubic.4
projects/tcp_cc_7.x/sys/modules/cc_cubic/
- copied from r187908, projects/tcp_cc_8.x/sys/modules/cc_cubic/
projects/tcp_cc_7.x/sys/netinet/cc_cubic.c
- copied unchanged from r188041, projects/tcp_cc_8.x/sys/netinet/cc_cubic.c
projects/tcp_cc_7.x/sys/netinet/cc_cubic.h
- copied unchanged from r187908, projects/tcp_cc_8.x/sys/netinet/cc_cubic.h
Modified:
projects/tcp_cc_7.x/share/man/man4/ (props changed)
projects/tcp_cc_7.x/sys/ (props changed)
projects/tcp_cc_7.x/sys/conf/files
projects/tcp_cc_7.x/sys/modules/Makefile
Copied: projects/tcp_cc_7.x/share/man/man4/cc_cubic.4 (from r187908, 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_7.x/share/man/man4/cc_cubic.4 Tue Feb 3 03:46:26 2009 (r188043, copy of r187908, projects/tcp_cc_8.x/share/man/man4/cc_cubic.4)
@@ -0,0 +1,60 @@
+.\"
+.\" Copyright (c) 2009 Lawrence Stewart <lstewart at 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 at 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 at 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_7.x/sys/conf/files
==============================================================================
--- projects/tcp_cc_7.x/sys/conf/files Tue Feb 3 03:43:00 2009 (r188042)
+++ projects/tcp_cc_7.x/sys/conf/files Tue Feb 3 03:46:26 2009 (r188043)
@@ -1795,6 +1795,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_7.x/sys/modules/Makefile
==============================================================================
--- projects/tcp_cc_7.x/sys/modules/Makefile Tue Feb 3 03:43:00 2009 (r188042)
+++ projects/tcp_cc_7.x/sys/modules/Makefile Tue Feb 3 03:46:26 2009 (r188043)
@@ -47,6 +47,7 @@ SUBDIR= ${_3dfx} \
${_canbus} \
${_cardbus} \
${_cbb} \
+ cc_cubic \
cc_htcp \
cd9660 \
cd9660_iconv \
Copied: projects/tcp_cc_7.x/sys/netinet/cc_cubic.c (from r188041, 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_7.x/sys/netinet/cc_cubic.c Tue Feb 3 03:46:26 2009 (r188043, copy of r188041, projects/tcp_cc_8.x/sys/netinet/cc_cubic.c)
@@ -0,0 +1,410 @@
+/*-
+ * Copyright (c) 2008-2009 Lawrence Stewart <lstewart at 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);
Copied: projects/tcp_cc_7.x/sys/netinet/cc_cubic.h (from r187908, 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_7.x/sys/netinet/cc_cubic.h Tue Feb 3 03:46:26 2009 (r188043, copy of r187908, projects/tcp_cc_8.x/sys/netinet/cc_cubic.h)
@@ -0,0 +1,200 @@
+/*-
+ * Copyright (c) 2008-2009 Lawrence Stewart <lstewart at 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_ */
More information about the svn-src-projects
mailing list