[RFC] TCP Illinois preliminary version

[Stephen Hemminger <shemminger@linux-foundation.org>]

Preliminary version if TCP Illinois for 2.6.22.
It needs more testing and refinement but it captures the
basic concepts.

---
 net/ipv4/Kconfig        |   13 +++
 net/ipv4/Makefile       |    1 +
 net/ipv4/tcp_illinois.c |  238 +++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 252 insertions(+), 0 deletions(-)
 create mode 100644 net/ipv4/tcp_illinois.c

diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
index dc61e66..e62aee0 100644
--- a/net/ipv4/Kconfig
+++ b/net/ipv4/Kconfig
@@ -588,6 +588,19 @@ config TCP_CONG_YEAH
 	For further details look here:
 	  http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf
 
+config TCP_CONG_ILLINOIS
+	tristate "TCP Illinois"
+	depends on EXPERIMENTAL
+	default n
+	---help---
+	TCP-Illinois is a sender-side modificatio of TCP Reno for
+	high speed long delay links. It uses round-trip-time to
+	adjust the alpha and beta parameters to achieve a higher average
+	throughput and maintain fairness.
+
+	For further details see:
+	  http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html
+
 choice
 	prompt "Default TCP congestion control"
 	default DEFAULT_CUBIC
diff --git a/net/ipv4/Makefile b/net/ipv4/Makefile
index eeb94d5..4ff6c15 100644
--- a/net/ipv4/Makefile
+++ b/net/ipv4/Makefile
@@ -50,6 +50,7 @@ obj-$(CONFIG_TCP_CONG_VENO) += tcp_veno.o
 obj-$(CONFIG_TCP_CONG_SCALABLE) += tcp_scalable.o
 obj-$(CONFIG_TCP_CONG_LP) += tcp_lp.o
 obj-$(CONFIG_TCP_CONG_YEAH) += tcp_yeah.o
+obj-$(CONFIG_TCP_CONG_ILLINOIS) += tcp_illinois.o
 obj-$(CONFIG_NETLABEL) += cipso_ipv4.o
 
 obj-$(CONFIG_XFRM) += xfrm4_policy.o xfrm4_state.o xfrm4_input.o \
diff --git a/net/ipv4/tcp_illinois.c b/net/ipv4/tcp_illinois.c
new file mode 100644
index 0000000..3536089
--- /dev/null
+++ b/net/ipv4/tcp_illinois.c
@@ -0,0 +1,238 @@
+/*
+ * TCP Illinois congestion control.
+ * Home page:
+ *	http://www.ews.uiuc.edu/~shaoliu/tcpillinois/index.html
+ *
+ * The algorithm is described in:
+ * "TCP-Illinois: A Loss and Delay-Based Congestion Control Algorithm
+ *  for High-Speed Networks"
+ *  http://www.ews.uiuc.edu/~shaoliu/papersandslides/tcpillinois_10pages.pdf
+ *
+ * This implementation uses same constants as the ns-2 simulation.
+ */
+
+#include <linux/module.h>
+#include <net/tcp.h>
+#include <linux/skbuff.h>
+#include <linux/inet_diag.h>
+
+#define ALPHA_SHIFT	7
+#define ALPHA_SCALE	(1u<<ALPHA_SHIFT)
+#define ALPHA_MIN	(ALPHA_SCALE/10)
+#define ALPHA_MAX	(10*ALPHA_SCALE)
+#define ALPHA_BASE	ALPHA_SCALE		/* 1.0 */
+
+#define BETA_SHIFT	6
+#define BETA_SCALE	(1u<<BETA_SHIFT)
+#define BETA_MIN	(BETA_SCALE/8)
+#define BETA_MAX	(BETA_SCALE/2)
+#define BETA_BASE	BETA_MAX		/* 0.5 */
+
+static int win_thresh __read_mostly = 10;
+module_param(win_thresh, int, 0644);
+MODULE_PARM_DESC(win_thresh, "Window threshold for starting adaptive sizing");
+
+/* TCP Illinois Parameters */
+struct tcp_illinois {
+	u32	min_rtt;
+	u32	max_rtt;
+	u32	avg_rtt;
+};
+
+static void tcp_illinois_init(struct sock *sk)
+{
+	struct tcp_illinois *ca = inet_csk_ca(sk);
+
+	ca->min_rtt = 0x7fffffff;
+}
+
+/*
+ * Keep track of min, max and average RTT
+ *
+ * In the paper, it implies that they want average of RTT over
+ * last window of packets. Doing that exactly would require too much
+ * memory (W samples). So we use a sliding average.
+ */
+static void tcp_illinois_rtt_calc(struct sock *sk, u32 rtt)
+{
+	struct tcp_sock *tp = tcp_sk(sk);
+	struct tcp_illinois *ca = inet_csk_ca(sk);
+
+	/* Compute sliding average over last N packets */
+	ca->avg_rtt = (ca->avg_rtt * (tp->snd_cwnd-1) + rtt) / tp->snd_cwnd;
+
+	if (rtt < ca->min_rtt)
+		ca->min_rtt = rtt;
+
+	if (rtt > ca->max_rtt)
+		ca->max_rtt = rtt;
+}
+
+/*
+ * Compute value of alpha used for additive increase.
+ * If small window then use 1.0, equivalent to Reno.
+ *
+ * For larger windows, adjust based on average delay.
+ * A. If average delay is at mininum (we are uncongested),
+ *    then use large alpha (10.0) to increase faster.
+ * B. If average delay is at maximum (getting congested)
+ *    then use small alpha (1.0)
+ *
+ * Given dm is max delay, and da is average delay
+ * and we assume d1 as zero.
+ *
+ *      dm * αmin * αmax
+ * κ1 = ---------------------
+ *       αmax − αmin
+ *                        
+ *       dm * αmin
+ * κ2 = ------------
+ *	 αmax − αmin
+ *
+ *       κ1
+ * α = --------
+ *     κ2 + da
+ *
+ * The result is a convex window growth curve.
+ * 
+ * Scaling notes:  value (scaled) [bits]
+ * 	ALPHA_MAX = 10.0 (1280) [11]
+ *	ALPHA_MIN = ~0.1 (12)  [4]
+ * 	delay max = 2 * 10^6 [21]
+ */
+static inline u32 alpha(const struct sock *sk)
+{
+	const struct tcp_sock *tp = tcp_sk(sk);
+	const struct tcp_illinois *ca = inet_csk_ca(sk);
+	u32 dm, k2;
+	u64 k1;
+
+	if (tp->snd_cwnd < win_thresh)
+		return ALPHA_BASE;	/* same as Reno (1.0) */
+
+	dm = ca->max_rtt - ca->min_rtt;
+	k1 = (u64) dm * (u64)(ALPHA_MAX * ALPHA_MIN);
+	k2 = dm * ALPHA_MIN;
+	k2 += (ca->avg_rtt - ca->min_rtt) * (ALPHA_MAX - ALPHA_MIN);
+
+	do_div(k1, k2);
+
+	return k1;
+}
+
+/*
+ * Increase window in response to successful acknowledgment.
+ */
+static void tcp_illinois_cong_avoid(struct sock *sk, u32 ack, u32 rtt,
+				    u32 in_flight, int flag)
+{
+	struct tcp_sock *tp = tcp_sk(sk);
+
+	/* RFC2861 only increase cwnd if fully utilized */
+	if (!tcp_is_cwnd_limited(sk, in_flight))
+		return;
+
+	/* In slow start */
+	if (tp->snd_cwnd <= tp->snd_ssthresh)
+		tcp_slow_start(tp);
+
+	else {
+		/* additive increase  cwnd += alpha / cwnd */
+		if ((tp->snd_cwnd_cnt * alpha(sk)) >> ALPHA_SHIFT >= tp->snd_cwnd) {
+			if (tp->snd_cwnd < tp->snd_cwnd_clamp)
+				tp->snd_cwnd++;
+			tp->snd_cwnd_cnt = 0;
+		} else
+			tp->snd_cwnd_cnt++;
+	}
+}
+
+/*
+ * Beta used for multiplicative decrease.
+ * For small window sizes returns same value as Reno (0.5)
+ * 
+ * If delay is small (10% of max) then beta = 1/8
+ * If delay is up to 80% of max then beta = 1/2
+ * In between is a linear function
+ */
+static inline u32 beta(const struct sock *sk)
+{
+	const struct tcp_sock *tp = tcp_sk(sk);
+	const struct tcp_illinois *ca = inet_csk_ca(sk);
+	u32 dm, d2, d3, da;
+
+	if (tp->snd_cwnd < win_thresh)
+		return BETA_BASE;
+
+	/* max delay (ie most congested) */
+	dm = ca->max_rtt - ca->min_rtt;
+	/* average delay */
+	da = ca->avg_rtt - ca->min_rtt;
+
+	d2 = dm / 10;
+	if (da < d2)
+		return BETA_MIN;
+	d3 = (8 * dm) / 10;
+	if (da > d3)
+		return BETA_MAX;
+
+	return ((BETA_MIN * d3 - BETA_MAX * d2) + BETA_MAX - BETA_MIN) /
+		max(d3 - d2, 1U);
+
+}
+
+static u32 tcp_illinois_ssthresh(struct sock *sk)
+{
+	struct tcp_sock *tp = tcp_sk(sk);
+
+	/* Multiplicative decrease */
+	return max((tp->snd_cwnd * beta(sk)) >> BETA_SHIFT, 2U);
+}
+
+/* Extract info for Tcp socket info provided via netlink. 
+ * We aren't really doing Vegas, but we can provide RTT info
+ */
+static void tcp_illinois_get_info(struct sock *sk, u32 ext,
+			       struct sk_buff *skb)
+{
+	const struct tcp_illinois *ca = inet_csk_ca(sk);
+
+	if (ext & (1 << (INET_DIAG_VEGASINFO - 1))) {
+		struct tcpvegas_info info = {
+			.tcpv_enabled = 1,
+			.tcpv_rtt = ca->avg_rtt,
+			.tcpv_minrtt = ca->min_rtt,
+		};
+
+		nla_put(skb, INET_DIAG_VEGASINFO, sizeof(info), &info);
+	}
+}
+
+static struct tcp_congestion_ops tcp_illinois = {
+	.init		= tcp_illinois_init,
+	.ssthresh	= tcp_illinois_ssthresh,
+	.min_cwnd	= tcp_reno_min_cwnd,
+	.cong_avoid	= tcp_illinois_cong_avoid,
+	.rtt_sample	= tcp_illinois_rtt_calc,
+	.get_info	= tcp_illinois_get_info,
+
+	.owner		= THIS_MODULE,
+	.name		= "illinois",
+};
+
+static int __init tcp_illinois_register(void)
+{
+	return tcp_register_congestion_control(&tcp_illinois);
+}
+
+static void __exit tcp_illinois_unregister(void)
+{
+	tcp_unregister_congestion_control(&tcp_illinois);
+}
+
+module_init(tcp_illinois_register);
+module_exit(tcp_illinois_unregister);
+
+MODULE_AUTHOR("Stephen Hemminger, Shao Liu");
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("Illinois TCP");
-- 
1.5.0.5