Skip to contentSkip to conversation

YeAH-TCP: algorithm implementation

PATCH In review Angelo P. Castellani 3 participants 4 messages Feb 19, 2007 – Mar 7, 2007

Subsystems (3)
Networking Network drivers TCP
lore
Share & tools
lore

Angelo P. Castellani

author
#0 lore raw

PATCH 1/2 YeAH-TCP: algorithm implementation

From: Angelo P. Castellani <[email protected]>

YeAH-TCP is a sender-side high-speed enabled TCP congestion control algorithm, which uses a mixed loss/delay approach to compute the congestion window. It's design goals target high efficiency, internal, RTT and Reno fairness, resilience to link loss while keeping network elements load as low as possible.

For further details look here:
http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf

Signed-off-by Angelo P. Castellani <[email protected]>

---

This is the YeAH-TCP implementation of the algorithm presented to PFLDnet2007 (http://wil.cs.caltech.edu/pfldnet2007/).

Regards,
Angelo P. Castellani

Kconfig    |   14 ++
Makefile   |    1
tcp_yeah.c |  288
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
tcp_yeah.h |  134 ++++++++++++++++++++++++++++
4 files changed, 437 insertions(+)
author
#1 lore raw

The patch.

Angelo P. Castellani ha scritto:

Quoted 21 lines

From: Angelo P. Castellani <[email protected]>

YeAH-TCP is a sender-side high-speed enabled TCP congestion control algorithm, which uses a mixed loss/delay approach to compute the congestion window. It's design goals target high efficiency, internal, RTT and Reno fairness, resilience to link loss while keeping network elements load as low as possible.

For further details look here:

   http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf
Signed-off-by Angelo P. Castellani <[email protected]>

---

This is the YeAH-TCP implementation of the algorithm presented to PFLDnet2007 (http://wil.cs.caltech.edu/pfldnet2007/).

Regards,
Angelo P. Castellani

Quoted 8 lines
Kconfig    |   14 ++
Makefile   |    1
tcp_yeah.c |  288
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
tcp_yeah.h |  134 ++++++++++++++++++++++++++++
4 files changed, 437 insertions(+)
net/ipv4/Kconfig +14 -0
diff -uprN linux-2.6.20-a/net/ipv4/Kconfig linux-2.6.20-b/net/ipv4/Kconfig
@@ -574,6 +574,20 @@ config TCP_CONG_VENO
 	loss packets.
 	See http://www.ntu.edu.sg/home5/ZHOU0022/papers/CPFu03a.pdf
 
+config TCP_CONG_YEAH
+	tristate "YeAH TCP"
+	depends on EXPERIMENTAL
+	default n
+	---help---
+	YeAH-TCP is a sender-side high-speed enabled TCP congestion control
+	algorithm, which uses a mixed loss/delay approach to compute the
+	congestion window. It's design goals target high efficiency,
+	internal, RTT and Reno fairness, resilience to link loss while
+	keeping network elements load as low as possible.
+	
+	For further details look here:
+	  http://wil.cs.caltech.edu/pfldnet2007/paper/YeAH_TCP.pdf
+
 choice
 	prompt "Default TCP congestion control"
 	default DEFAULT_CUBIC
net/ipv4/Makefile +1 -0
diff -uprN linux-2.6.20-a/net/ipv4/Makefile linux-2.6.20-b/net/ipv4/Makefile
@@ -49,6 +49,7 @@ obj-$(CONFIG_TCP_CONG_VEGAS) += tcp_vega
 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_NETLABEL) += cipso_ipv4.o
 
 obj-$(CONFIG_XFRM) += xfrm4_policy.o xfrm4_state.o xfrm4_input.o \
net/ipv4/tcp_yeah.c +288 -0

288 lines not on this page · raw message

net/ipv4/tcp_yeah.h +134 -0

134 lines not on this page · raw message

#2 lore raw

PATCH 1/1 TCP Yeah: cleanup

Eliminate need for full 6/4/64 divide to compute queue. Variable maxqueue was really a constant.
Fix indentation.

Signed-off-by Stephen Hemminger <[email protected]>
---
 net/ipv4/tcp_yeah.c |   42 +++++++++++++++++++++++-------------------
 1 file changed, 23 insertions(+), 19 deletions(-)
net/ipv4/tcp_yeah.c +23 -19
@@ -74,7 +74,7 @@
 }
 
 static void tcp_yeah_cong_avoid(struct sock *sk, u32 ack,
-				 u32 seq_rtt, u32 in_flight, int flag)
+				u32 seq_rtt, u32 in_flight, int flag)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 	struct yeah *yeah = inet_csk_ca(sk);

@@ -142,8 +142,8 @@
 		 */
 
 		if (yeah->cntRTT > 2) {
-			u32 rtt;
-			u32 queue, maxqueue;
+			u32 rtt, queue;
+			u64 bw;
 
 			/* We have enough RTT samples, so, using the Vegas
 			 * algorithm, we determine if we should increase or

@@ -158,32 +158,36 @@
 			 */
 			rtt = yeah->minRTT;
 
-			queue = (u32)div64_64((u64)tp->snd_cwnd * (rtt - yeah->baseRTT), rtt);
-
-			maxqueue = TCP_YEAH_ALPHA;
-
-			if (queue > maxqueue ||
-				    rtt - yeah->baseRTT > (yeah->baseRTT / TCP_YEAH_PHY)) {
-
-				if (queue > maxqueue && tp->snd_cwnd > yeah->reno_count) {
-					u32 reduction = min( queue / TCP_YEAH_GAMMA ,
-					                 tp->snd_cwnd >> TCP_YEAH_EPSILON );
+			/* Compute excess number of packets above bandwidth
+			 * Avoid doing full 64 bit divide.
+			 */
+			bw = tp->snd_cwnd;
+			bw *= rtt - yeah->baseRTT;
+			do_div(bw, rtt);
+			queue = bw;
+
+			if (queue > TCP_YEAH_ALPHA ||
+			    rtt - yeah->baseRTT > (yeah->baseRTT / TCP_YEAH_PHY)) {
+				if (queue > TCP_YEAH_ALPHA
+				    && tp->snd_cwnd > yeah->reno_count) {
+					u32 reduction = min(queue / TCP_YEAH_GAMMA ,
+							    tp->snd_cwnd >> TCP_YEAH_EPSILON);
 
 					tp->snd_cwnd -= reduction;
 
-					tp->snd_cwnd = max( tp->snd_cwnd, yeah->reno_count);
+					tp->snd_cwnd = max(tp->snd_cwnd,
+							   yeah->reno_count);
 
 					tp->snd_ssthresh = tp->snd_cwnd;
-			}
+				}
 
 				if (yeah->reno_count <= 2)
-					yeah->reno_count = max( tp->snd_cwnd>>1, 2U);
+					yeah->reno_count = max(tp->snd_cwnd>>1, 2U);
 				else
 					yeah->reno_count++;
 
-				yeah->doing_reno_now =
-					           min_t( u32, yeah->doing_reno_now + 1 , 0xffffff);
-
+				yeah->doing_reno_now = min(yeah->doing_reno_now + 1,
+							   0xffffffU);
 			} else {
 				yeah->fast_count++;