Re: [PATCH] TCP Illinois congestion control (rev3)
On Fri, 20 Apr 2007 17:08:13 -0700 (PDT) David Miller <[EMAIL PROTECTED]> wrote: > From: Stephen Hemminger <[EMAIL PROTECTED]> > Date: Wed, 4 Apr 2007 08:07:43 -0700 > > > This is an implementation of TCP Illinois invented by Shao Liu > > at University of Illinois. It is a another variant of Reno which adapts > > the alpha and beta parameters based on RTT. The basic idea is to increase > > window less rapidly as delay approaches the maximum. See the papers > > and talks to get a more complete description. > > > > Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> > > I've applied this to net-2.6.22, let me know if there are any > follow-on bug fixes I need to add as well. > > Thanks! I have a new version ready. - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
Re: [PATCH] TCP Illinois congestion control (rev3)
From: Stephen Hemminger <[EMAIL PROTECTED]> Date: Wed, 4 Apr 2007 08:07:43 -0700 > This is an implementation of TCP Illinois invented by Shao Liu > at University of Illinois. It is a another variant of Reno which adapts > the alpha and beta parameters based on RTT. The basic idea is to increase > window less rapidly as delay approaches the maximum. See the papers > and talks to get a more complete description. > > Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> I've applied this to net-2.6.22, let me know if there are any follow-on bug fixes I need to add as well. Thanks! - To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html
[PATCH] TCP Illinois congestion control (rev3)
This is an implementation of TCP Illinois invented by Shao Liu at University of Illinois. It is a another variant of Reno which adapts the alpha and beta parameters based on RTT. The basic idea is to increase window less rapidly as delay approaches the maximum. See the papers and talks to get a more complete description. Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> --- net/ipv4/Kconfig| 13 ++ net/ipv4/Makefile |1 + net/ipv4/tcp_illinois.c | 284 +++ 3 files changed, 298 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 000..1990ff2 --- /dev/null +++ b/net/ipv4/tcp_illinois.c @@ -0,0 +1,284 @@ +/* + * 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/liubassri06perf.pdf + * + * Implemented from description in paper and ns-2 simulation. + * Copyright (C) 2007 Stephen Hemminger <[EMAIL PROTECTED]> + */ + +#include +#include +#include +#include +#include + +#define ALPHA_SHIFT7 +#define ALPHA_SCALE(1umin_rtt = 0x7fff; +} + +/* + * Keep track of min, max and average RTT + */ +static void tcp_illinois_rtt_calc(struct sock *sk, u32 rtt) +{ + struct tcp_illinois *ca = inet_csk_ca(sk); + + if (rtt < ca->min_rtt) + ca->min_rtt = rtt; + if (rtt > ca->max_rtt) + ca->max_rtt = rtt; + + if (++ca->rtt_cnt == 1) + ca->sum_rtt = rtt; + else + ca->sum_rtt += rtt; +} + +/* max queuing delay */ +static inline u32 max_delay(const struct tcp_illinois *ca) +{ + return ca->max_rtt - ca->min_rtt; +} + +/* average queueing delay */ +static u32 avg_delay(struct tcp_illinois *ca) +{ + u64 avg_rtt = ca->sum_rtt; + + do_div(avg_rtt, ca->rtt_cnt); + + ca->sum_rtt = 0; + ca->rtt_cnt = 0; + + return avg_rtt - ca->min_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 minimum (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) + * + * The result is a convex window growth curve. + */ +static u32 alpha(const struct sock *sk) +{ + struct tcp_sock *tp = tcp_sk(sk); + struct tcp_illinois *ca = inet_csk_ca(sk); + u32 dm = max_delay(ca); + u32 da = avg_delay(ca); + u32 d1, a; + + if (tp->snd_cwnd < win_thresh) + return ALPHA_BASE; /* same as Reno (1.0) */ + + d1 = dm / 100; + if (da <= d1) { + /* Don't let noise force agressive response */ + if (ca->rtt_low < THETA) { + ++ca->rtt_low; + return ca->last_alpha; + } else + return ALPHA_MAX; + } + + ca->rtt_low = 0; + + /* +* Based on: +* +* (dm - d1) amin amax +* k1 = --- +* amax - amin +* +* (dm - d1) amin +* k2 = - d1 +*amax - amin +* +* k1 +* alpha = --
RE: [PATCH] TCP Illinois congestion control
Hi Stephen,
Thanks for the implementation. I have checked the codes, and I have the
following comments:
1, The math is basically correct in computing alpha and beta from da.
2, In the computation of da, you implicitly set d1=0. Setting d1=0 is a
conservative approach, although it also works well (it may lead to a longer
convergence time than a positive d1). The reason is that, even if far from
congestion, there are some burstiness in RTT measurements, and we get
da>d_min. This way, we have an alphahttp://www.ews.uiuc.edu/~shaoliu/papersandslides/liubassri06perf.pdf
We have also implemented this feature in our ns-2 code. The basic idea of
this feature is that, once da exceeds d1 and alphamailto:[EMAIL PROTECTED]
Sent: Tuesday, April 03, 2007 11:17 AM
To: David Miller
Cc: [EMAIL PROTECTED]; [EMAIL PROTECTED]; [EMAIL PROTECTED];
[EMAIL PROTECTED]; [EMAIL PROTECTED]; [EMAIL PROTECTED];
netdev@vger.kernel.org
Subject: [PATCH] TCP Illinois congestion control
This is a new implementation of TCP Illinois invented by Shao Liu at
University of Illinois. It is a another variant of Reno which adapts the
alpha and beta parameters based on RTT. The basic idea is to increase window
less rapidly as delay approaches the maximum. See the papers and talks to
get a more complete description.
Please consider for 2.6.22.
Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]>
---
net/ipv4/Kconfig| 13 +++
net/ipv4/Makefile |1 +
net/ipv4/tcp_illinois.c | 212
+++
3 files changed, 226 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 000..f7c0b76
--- /dev/null
+++ b/net/ipv4/tcp_illinois.c
@@ -0,0 +1,212 @@
+/*
+ * 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.pd
+f
+ *
+ * Implemented from description in paper and ns-2 simulation.
+ * Copyright (C) 2007 Stephen Hemminger
+<[EMAIL PROTECTED]> */
+
+#include
+#include
+#include
+#include
+
+#define ALPHA_SHIFT7
+#define ALPHA_SCALE(1u<min_rtt = 0x7fff;
+}
+
+/*
+ * 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 minimum (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)
+ *
+ * The result is a convex window growth curve.
+ */
+static inline u32 alpha(const struct sock *sk) {
+ const struct tcp
[PATCH] TCP Illinois congestion control
This is a new implementation of TCP Illinois invented by Shao Liu at University of Illinois. It is a another variant of Reno which adapts the alpha and beta parameters based on RTT. The basic idea is to increase window less rapidly as delay approaches the maximum. See the papers and talks to get a more complete description. Please consider for 2.6.22. Signed-off-by: Stephen Hemminger <[EMAIL PROTECTED]> --- net/ipv4/Kconfig| 13 +++ net/ipv4/Makefile |1 + net/ipv4/tcp_illinois.c | 212 +++ 3 files changed, 226 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 000..f7c0b76 --- /dev/null +++ b/net/ipv4/tcp_illinois.c @@ -0,0 +1,212 @@ +/* + * 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 + * + * Implemented from description in paper and ns-2 simulation. + * Copyright (C) 2007 Stephen Hemminger <[EMAIL PROTECTED]> + */ + +#include +#include +#include +#include + +#define ALPHA_SHIFT7 +#define ALPHA_SCALE(1uavg_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 minimum (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) + * + * The result is a convex window growth curve. + */ +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, da; + + if (tp->snd_cwnd < win_thresh) + return ALPHA_BASE; /* same as Reno (1.0) */ + + dm = ca->max_rtt - ca->min_rtt; /* max queuing delay */ + da = ca->avg_rtt - ca->min_rtt; /* avg queuing delay */ + + return (dm * ALPHA_MAX) / + (dm - (da * (ALPHA_MAX - ALPHA_MIN)) / ALPHA_MIN); +} + +/* + * 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 * al
