Skip to content

Instantly share code, notes, and snippets.

@soohyunc

soohyunc/tcp-ttfwc.diff

Created June 21, 2013 10:17
Show Gist options
  • Save soohyunc/5830286 to your computer and use it in GitHub Desktop.
Save soohyunc/5830286 to your computer and use it in GitHub Desktop.
Download ZIP
TCP extension for TTFWC implementation
Raw
tcp-ttfwc.diff
From b7a7b02e30d51ed2117068c7e33b835721157467 Mon Sep 17 00:00:00 2001
From: katoon <[email protected]>
Date: Sun, 17 Jul 2011 17:39:59 +0900
Subject: [PATCH] net: ipv4: add new congestion control
We add Tunable TCP-Friendly Window Control (TTFWC) as TCP
extension. TTFWC allows users or applications to tune the
balance between responsiveness and smoothness with a tuning
parameter. You can set the parameter by sysctl.
Signed-off-by: Midori Kato <[email protected]>
---
include/net/tcp.h | 1 +
net/ipv4/Kconfig | 10 +
net/ipv4/Makefile | 1 +
net/ipv4/sysctl_net_ipv4.c | 7 +
net/ipv4/tcp_input.c | 2 +-
net/ipv4/tcp_ttfwc.c | 238 +++++++++++++++++
net/ipv4/tcp_ttfwc.h | 602 ++++++++++++++++++++++++++++++++++++++++++++
7 files changed, 860 insertions(+), 1 deletions(-)
create mode 100644 net/ipv4/tcp_ttfwc.c
create mode 100644 net/ipv4/tcp_ttfwc.h
diff --git a/include/net/tcp.h b/include/net/tcp.h
index 149a415..2e9443a 100644
--- a/include/net/tcp.h
+++ b/include/net/tcp.h
@@ -252,6 +252,7 @@ extern int sysctl_tcp_max_ssthresh;
extern int sysctl_tcp_cookie_size;
extern int sysctl_tcp_thin_linear_timeouts;
extern int sysctl_tcp_thin_dupack;
+extern int sysctl_ttfwc_tuning_p;
extern atomic_long_t tcp_memory_allocated;
extern struct percpu_counter tcp_sockets_allocated;
diff --git a/net/ipv4/Kconfig b/net/ipv4/Kconfig
index cbb505b..7bca23a 100644
--- a/net/ipv4/Kconfig
+++ b/net/ipv4/Kconfig
@@ -469,6 +469,12 @@ config TCP_CONG_HTCP
based on network conditions and in a way so as to be fair with
other Reno and H-TCP flows.
+config TCP_CONG_TTFWC
+ tristate "TTFWC"
+ default m
+ ---help---
+ TTFWC is implementing a novel congestion control for multimedia streaming.
+
config TCP_CONG_HSTCP
tristate "High Speed TCP"
depends on EXPERIMENTAL
@@ -577,6 +583,9 @@ choice
config DEFAULT_HTCP
bool "Htcp" if TCP_CONG_HTCP=y
+ config DEFAULT_TTFWC
+ bool "Ttfwc" if TCP_CONG_TTFWC=y
+
config DEFAULT_HYBLA
bool "Hybla" if TCP_CONG_HYBLA=y
@@ -606,6 +615,7 @@ config DEFAULT_TCP_CONG
default "bic" if DEFAULT_BIC
default "cubic" if DEFAULT_CUBIC
default "htcp" if DEFAULT_HTCP
+ default "ttfwc" if DEFAULT_TTFWC
default "hybla" if DEFAULT_HYBLA
default "vegas" if DEFAULT_VEGAS
default "westwood" if DEFAULT_WESTWOOD
diff --git a/net/ipv4/Makefile b/net/ipv4/Makefile
index f2dc69c..4ce1300 100644
--- a/net/ipv4/Makefile
+++ b/net/ipv4/Makefile
@@ -41,6 +41,7 @@ obj-$(CONFIG_TCP_CONG_WESTWOOD) += tcp_westwood.o
obj-$(CONFIG_TCP_CONG_HSTCP) += tcp_highspeed.o
obj-$(CONFIG_TCP_CONG_HYBLA) += tcp_hybla.o
obj-$(CONFIG_TCP_CONG_HTCP) += tcp_htcp.o
+obj-$(CONFIG_TCP_CONG_TTFWC) += tcp_ttfwc.o
obj-$(CONFIG_TCP_CONG_VEGAS) += tcp_vegas.o
obj-$(CONFIG_TCP_CONG_VENO) += tcp_veno.o
obj-$(CONFIG_TCP_CONG_SCALABLE) += tcp_scalable.o
diff --git a/net/ipv4/sysctl_net_ipv4.c b/net/ipv4/sysctl_net_ipv4.c
index 69fd720..84b8c7d 100644
--- a/net/ipv4/sysctl_net_ipv4.c
+++ b/net/ipv4/sysctl_net_ipv4.c
@@ -525,6 +525,13 @@ static struct ctl_table ipv4_table[] = {
.proc_handler = proc_tcp_congestion_control,
},
{
+ .procname = "ttfwc_tuning_p",
+ .data = &sysctl_ttfwc_tuning_p,
+ .maxlen = sizeof(int),
+ .mode = 0644,
+ .proc_handler = proc_dointvec,
+ },
+ {
.procname = "tcp_abc",
.data = &sysctl_tcp_abc,
.maxlen = sizeof(int),
diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index ea0d218..bc64c77 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -833,7 +833,7 @@ void tcp_enter_cwr(struct sock *sk, const int set_ssthresh)
tp->undo_marker = 0;
if (set_ssthresh)
tp->snd_ssthresh = icsk->icsk_ca_ops->ssthresh(sk);
- tp->snd_cwnd = min(tp->snd_cwnd,
+ tp->snd_cwnd = min(tp->snd_cwnd,
tcp_packets_in_flight(tp) + 1U);
tp->snd_cwnd_cnt = 0;
tp->high_seq = tp->snd_nxt;
diff --git a/net/ipv4/tcp_ttfwc.c b/net/ipv4/tcp_ttfwc.c
new file mode 100644
index 0000000..779006c
--- /dev/null
+++ b/net/ipv4/tcp_ttfwc.c
@@ -0,0 +1,238 @@
+/*
+ * Tunable TCP Friendly Window Control
+ * Home page:
+ * http://ht.sfc.keio.ac.jp/~katoon/ttfwc/
+ * This is from the implementation of TTFWC in Midori Kato
+ * "Extending TFWC towards Higher Throughput" in CCNC 2012
+ *
+ */
+
+#include <linux/module.h>
+#include <net/tcp.h>
+#include "tcp_ttfwc.h"
+
+int sysctl_ttfwc_tuning_p __read_mostly;
+static int initial_ssthresh __read_mostly;
+
+struct ttfwc {
+ u32 tcp_cwnd;
+ u32 is_reno;
+ u32 reno_cwnd;
+ u32 alpha_cwnd;
+ u32 li_dif;
+ u32 li_counter;
+ u32 li_mean;
+ struct ttfwc_loss_hist *lh;
+};
+
+static inline void ttfwc_reset(struct ttfwc *ca)
+{
+ ca->tcp_cwnd = 0;
+ ca->alpha_cwnd = 0;
+ ca->li_counter = 0;
+ ca->li_mean = 0;
+ ca->reno_cwnd = 0;
+ ca->li_dif = 0;
+ ca->is_reno = 0;
+ ca->lh = kzalloc(sizeof(struct ttfwc_loss_hist), GFP_ATOMIC);
+ memset(ca->lh, 0, sizeof(struct ttfwc_loss_hist));
+}
+
+static void ttfwc_init(struct sock *sk)
+{
+ ttfwc_reset(inet_csk_ca(sk));
+ if (initial_ssthresh)
+ tcp_sk(sk)->snd_ssthresh = initial_ssthresh;
+}
+
+static inline u32 ttfwc_lh_length(struct ttfwc *ca)
+{
+ return min(ca->li_counter, (u32)LIH_SIZE);
+}
+
+static void ttfwc_cong_avoid(struct sock *sk, u32 ack, u32 in_flight)
+{
+ struct tcp_sock *tp = tcp_sk(sk);
+ struct ttfwc *ca = inet_csk_ca(sk);
+ u32 p, cwnd;
+
+ if (!tcp_is_cwnd_limited(sk, in_flight))
+ return;
+
+ if (ca->is_reno || ttfwc_lh_length(ca) < 1) {
+ ca->lh->li_length[0]++;
+ if (tp->snd_cwnd <= tp->snd_ssthresh)
+ tcp_slow_start(tp);
+ else
+ tcp_cong_avoid_ai(tp, tp->snd_cwnd);
+ return;
+ }
+
+ if (sysctl_ttfwc_tuning_p > 0) {
+ if (ca->lh->li_length[0] >= ca->li_dif/2) {
+ if (ca->lh->li_length[0] == ca->li_dif/2)
+ ca->reno_cwnd = ca->tcp_cwnd;
+ if (tp->snd_cwnd_cnt >= ca->reno_cwnd) {
+ if (ca->reno_cwnd < tp->snd_cwnd_clamp)
+ ca->reno_cwnd++;
+ tp->snd_cwnd_cnt = 0;
+ } else
+ tp->snd_cwnd_cnt++;
+ }
+ }
+ if (++ca->lh->li_length[0] > ca->li_dif) {
+ u32 count = ca->lh->li_length[0] - ca->li_dif;
+ if (count == 0)
+ tp->snd_cwnd += ca->alpha_cwnd;
+ if (sysctl_ttfwc_tuning_p <= 5){
+ if (count%6 == 0) goto common;
+ } else {
+ if (count%3 == 0) goto common;
+ }
+ }
+
+common:
+ p = ttfwc_invert_imean(++ca->li_mean);
+ cwnd = ttfwc_calc_x(p);
+ if (cwnd + ca->alpha_cwnd > tp->snd_cwnd)
+ tp->snd_cwnd++;
+}
+
+static inline void ttfwc_loss_hist_update(struct ttfwc *ca)
+{
+ int i, k = ttfwc_lh_length(ca) -1;
+ for (i = k; i > 0; i--)
+ ca->lh->li_length[i] = ca->lh->li_length[i-1];
+ ca->lh->li_length[0] = 1;
+}
+
+static inline u32 ttfwc_avg_loss_interval(struct ttfwc *ca)
+{
+ u32 i_i, i_tot0 = 0, i_tot1 = 0, w_tot = 0;
+ int i, k = ttfwc_lh_length(ca) - 1;
+
+ for (i = 0; i <= k; i++) {
+ i_i = ttfwc_lh_get_interval(ca->lh, i);
+ if (i > 0){
+ if (sysctl_ttfwc_tuning_p >= 5)
+ i_tot1 += i_i * ttfwc_weights_mode01[i-1];
+ else
+ i_tot1 += i_i * ttfwc_weights_mode02[i-1];
+ }
+ if (i < k) {
+ if (sysctl_ttfwc_tuning_p >= 5){
+ i_tot0 += i_i * ttfwc_weights_mode01[i];
+ w_tot += ttfwc_weights_mode01[i];
+ } else {
+ i_tot0 += i_i * ttfwc_weights_mode02[i];
+ w_tot += ttfwc_weights_mode02[i];
+ }
+ }
+ }
+ ca->li_dif = (i_tot1 - i_tot0)/100;
+ return max(i_tot0, i_tot1)/w_tot;
+}
+
+static inline void ttfwc_alpha_cwnd(struct ttfwc *ca, u32 cwnd, u32 calc_cwnd)
+{
+ ca->reno_cwnd = ca->reno_cwnd >> 2;
+ if (ca->reno_cwnd > calc_cwnd){
+ // this scope will be called due to NIC down
+ ca->alpha_cwnd = 0;
+ }else{
+ u32 dthresh;
+ u32 thresh = calc_cwnd - ca->reno_cwnd;
+ if (ca->alpha_cwnd > 0)
+ dthresh = (u32) calc_cwnd*100/(cwnd-ca->alpha_cwnd);
+ else
+ dthresh = (u32) calc_cwnd*100/(cwnd-ca->alpha_cwnd);
+ if (dthresh >= 100)
+ ca->alpha_cwnd = 0;
+ else {
+ if (sysctl_ttfwc_tuning_p >= 5 && dthresh > 72)
+ ca->alpha_cwnd = (u32) thresh*sysctl_ttfwc_tuning_p/10;
+ else if (sysctl_ttfwc_tuning_p > 0 && dthresh > 81)
+ ca->alpha_cwnd = (u32) thresh*sysctl_ttfwc_tuning_p*sysctl_ttfwc_tuning_p/100;
+ else
+ ca->alpha_cwnd = 0;
+ }
+ }
+}
+
+static inline u32 ttfwc_update(struct ttfwc *ca, u32 cwnd)
+{
+ u32 p, calc_cwnd;
+
+ if (++ca->li_counter == 1) {
+ cwnd = cwnd >> 2;
+ ca->lh->li_length[1] = ca->li_dif = ca->li_mean = pseudo_li_calc(cwnd);
+ ca->lh->li_length[0] = 1;
+ ca->li_dif = ca->li_dif/100;
+ ca->li_counter++;
+ return cwnd;
+ } else {
+ if (ca->is_reno > 0) ca->is_reno = 0;
+ if (ca->lh->li_length[0] < ca->li_dif) ca->alpha_cwnd = 0;
+ ttfwc_loss_hist_update(ca);
+ ca->li_mean = ttfwc_avg_loss_interval(ca);
+ if(ca->li_mean > 0) {
+ p = ttfwc_invert_imean(ca->li_mean);
+ calc_cwnd = ttfwc_calc_x(p);
+ }
+ if (sysctl_ttfwc_tuning_p == 0) goto out;
+ else{
+ if (ca->tcp_cwnd <= ca->reno_cwnd)
+ ttfwc_alpha_cwnd(ca, cwnd, calc_cwnd);
+ }
+ }
+ goto out;
+
+out:
+ cwnd = calc_cwnd;
+ if (cwnd <= 2 && ca->is_reno == 0) {
+ cwnd = 2;
+ ca->li_dif = 0;
+ ca->is_reno = 1;
+ }
+ return cwnd;
+}
+
+static u32 ttfwc_ssthresh(struct sock *sk)
+{
+ const struct tcp_sock *tp = tcp_sk(sk);
+ struct ttfwc *ca = inet_csk_ca(sk);
+ ca->tcp_cwnd = ttfwc_update(ca, tp->snd_cwnd);
+ return max(ca->tcp_cwnd, 2U);
+}
+
+static u32 ttfwc_undo_cwnd(struct sock *sk)
+{
+ struct ttfwc *ca = inet_csk_ca(sk);
+ return max(ca->tcp_cwnd, 2U);
+}
+
+static struct tcp_congestion_ops tcp_ttfwc __read_mostly = {
+ .init = ttfwc_init,
+ .ssthresh = ttfwc_ssthresh,
+ .cong_avoid = ttfwc_cong_avoid,
+ .undo_cwnd = ttfwc_undo_cwnd,
+ .owner = THIS_MODULE,
+ .name = "ttfwc",
+};
+
+static int __init tcp_ttfwc_register(void)
+{
+ return tcp_register_congestion_control(&tcp_ttfwc);
+}
+
+static void __exit tcp_ttfwc_unregister(void)
+{
+ tcp_unregister_congestion_control(&tcp_ttfwc);
+}
+
+module_init(tcp_ttfwc_register);
+module_exit(tcp_ttfwc_unregister);
+
+MODULE_AUTHOR("Midori Kato");
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("TTFWC TCP");
diff --git a/net/ipv4/tcp_ttfwc.h b/net/ipv4/tcp_ttfwc.h
new file mode 100644
index 0000000..a3bcaac
--- /dev/null
+++ b/net/ipv4/tcp_ttfwc.h
@@ -0,0 +1,602 @@
+#include <linux/ktime.h>
+#include <linux/list.h>
+#include <linux/slab.h>
+#include <linux/module.h>
+#define NINTERVAL 16
+#define LIH_SIZE (NINTERVAL + 1)
+#define TTFWC_CALC_X_ARRSIZE 500
+#define TTFWC_CALC_X_SPLIT 50000 /* 0.05 * 1000000, details below */
+#define TTFWC_SMALLEST_P (TTFWC_CALC_X_SPLIT/TTFWC_CALC_X_ARRSIZE)
+static const int ttfwc_weights_mode01[NINTERVAL] = { 100, 100, 33, 25, 20, 16, 14, 12, 0, 0, 0, 0, 0, 0, 0, 0 };
+static const int ttfwc_weights_mode02[NINTERVAL] = { 100, 100, 100, 100, 25, 20, 16, 14, 12, 11, 10, 9, 8, 7, 7, 6 };
+
+struct ttfwc_loss_hist {
+ u32 li_length[LIH_SIZE];
+};
+
+static inline u32 ttfwc_lh_get_interval(struct ttfwc_loss_hist *lh, const u32 i)
+{
+ WARN_ON(LIH_SIZE < i);
+ return lh->li_length[i];
+}
+
+static const u32 ttfwc_calc_x_lookup[TTFWC_CALC_X_ARRSIZE][2] = {
+ { 37172, 8172 },
+ { 53499, 11567 },
+ { 66664, 14180 },
+ { 78298, 16388 },
+ { 89021, 18339 },
+ { 99147, 20108 },
+ { 108858, 21738 },
+ { 118273, 23260 },
+ { 127474, 24693 },
+ { 136520, 26052 },
+ { 145456, 27348 },
+ { 154316, 28589 },
+ { 163130, 29783 },
+ { 171919, 30935 },
+ { 180704, 32049 },
+ { 189502, 33130 },
+ { 198328, 34180 },
+ { 207194, 35202 },
+ { 216114, 36198 },
+ { 225097, 37172 },
+ { 234153, 38123 },
+ { 243294, 39055 },
+ { 252527, 39968 },
+ { 261861, 40864 },
+ { 271305, 41743 },
+ { 280866, 42607 },
+ { 290553, 43457 },
+ { 300372, 44293 },
+ { 310333, 45117 },
+ { 320441, 45929 },
+ { 330705, 46729 },
+ { 341131, 47518 },
+ { 351728, 48297 },
+ { 362501, 49066 },
+ { 373460, 49826 },
+ { 384609, 50577 },
+ { 395958, 51320 },
+ { 407513, 52054 },
+ { 419281, 52780 },
+ { 431270, 53499 },
+ { 443487, 54211 },
+ { 455940, 54916 },
+ { 468635, 55614 },
+ { 481581, 56306 },
+ { 494785, 56991 },
+ { 508254, 57671 },
+ { 521996, 58345 },
+ { 536019, 59014 },
+ { 550331, 59677 },
+ { 564939, 60335 },
+ { 579851, 60988 },
+ { 595075, 61636 },
+ { 610619, 62279 },
+ { 626491, 62918 },
+ { 642700, 63553 },
+ { 659253, 64183 },
+ { 676158, 64809 },
+ { 693424, 65431 },
+ { 711060, 66050 },
+ { 729073, 66664 },
+ { 747472, 67275 },
+ { 766266, 67882 },
+ { 785464, 68486 },
+ { 805073, 69087 },
+ { 825103, 69684 },
+ { 845562, 70278 },
+ { 866460, 70868 },
+ { 887805, 71456 },
+ { 909606, 72041 },
+ { 931873, 72623 },
+ { 954614, 73202 },
+ { 977839, 73778 },
+ { 1001557, 74352 },
+ { 1025777, 74923 },
+ { 1050508, 75492 },
+ { 1075761, 76058 },
+ { 1101544, 76621 },
+ { 1127867, 77183 },
+ { 1154739, 77741 },
+ { 1182172, 78298 },
+ { 1210173, 78852 },
+ { 1238753, 79405 },
+ { 1267922, 79955 },
+ { 1297689, 80503 },
+ { 1328066, 81049 },
+ { 1359060, 81593 },
+ { 1390684, 82135 },
+ { 1422947, 82675 },
+ { 1455859, 83213 },
+ { 1489430, 83750 },
+ { 1523671, 84284 },
+ { 1558593, 84817 },
+ { 1594205, 85348 },
+ { 1630518, 85878 },
+ { 1667543, 86406 },
+ { 1705290, 86932 },
+ { 1743770, 87457 },
+ { 1782994, 87980 },
+ { 1822973, 88501 },
+ { 1863717, 89021 },
+ { 1905237, 89540 },
+ { 1947545, 90057 },
+ { 1990650, 90573 },
+ { 2034566, 91087 },
+ { 2079301, 91600 },
+ { 2124869, 92111 },
+ { 2171279, 92622 },
+ { 2218543, 93131 },
+ { 2266673, 93639 },
+ { 2315680, 94145 },
+ { 2365575, 94650 },
+ { 2416371, 95154 },
+ { 2468077, 95657 },
+ { 2520707, 96159 },
+ { 2574271, 96660 },
+ { 2628782, 97159 },
+ { 2684250, 97658 },
+ { 2740689, 98155 },
+ { 2798110, 98651 },
+ { 2856524, 99147 },
+ { 2915944, 99641 },
+ { 2976382, 100134 },
+ { 3037850, 100626 },
+ { 3100360, 101117 },
+ { 3163924, 101608 },
+ { 3228554, 102097 },
+ { 3294263, 102586 },
+ { 3361063, 103073 },
+ { 3428966, 103560 },
+ { 3497984, 104045 },
+ { 3568131, 104530 },
+ { 3639419, 105014 },
+ { 3711860, 105498 },
+ { 3785467, 105980 },
+ { 3860253, 106462 },
+ { 3936229, 106942 },
+ { 4013410, 107422 },
+ { 4091808, 107902 },
+ { 4171435, 108380 },
+ { 4252306, 108858 },
+ { 4334431, 109335 },
+ { 4417825, 109811 },
+ { 4502501, 110287 },
+ { 4588472, 110762 },
+ { 4675750, 111236 },
+ { 4764349, 111709 },
+ { 4854283, 112182 },
+ { 4945564, 112654 },
+ { 5038206, 113126 },
+ { 5132223, 113597 },
+ { 5227627, 114067 },
+ { 5324432, 114537 },
+ { 5422652, 115006 },
+ { 5522299, 115474 },
+ { 5623389, 115942 },
+ { 5725934, 116409 },
+ { 5829948, 116876 },
+ { 5935446, 117342 },
+ { 6042439, 117808 },
+ { 6150943, 118273 },
+ { 6260972, 118738 },
+ { 6372538, 119202 },
+ { 6485657, 119665 },
+ { 6600342, 120128 },
+ { 6716607, 120591 },
+ { 6834467, 121053 },
+ { 6953935, 121514 },
+ { 7075025, 121976 },
+ { 7197752, 122436 },
+ { 7322131, 122896 },
+ { 7448175, 123356 },
+ { 7575898, 123815 },
+ { 7705316, 124274 },
+ { 7836442, 124733 },
+ { 7969291, 125191 },
+ { 8103877, 125648 },
+ { 8240216, 126105 },
+ { 8378321, 126562 },
+ { 8518208, 127018 },
+ { 8659890, 127474 },
+ { 8803384, 127930 },
+ { 8948702, 128385 },
+ { 9095861, 128840 },
+ { 9244875, 129294 },
+ { 9395760, 129748 },
+ { 9548529, 130202 },
+ { 9703198, 130655 },
+ { 9859782, 131108 },
+ { 10018296, 131561 },
+ { 10178755, 132014 },
+ { 10341174, 132466 },
+ { 10505569, 132917 },
+ { 10671954, 133369 },
+ { 10840345, 133820 },
+ { 11010757, 134271 },
+ { 11183206, 134721 },
+ { 11357706, 135171 },
+ { 11534274, 135621 },
+ { 11712924, 136071 },
+ { 11893673, 136520 },
+ { 12076536, 136969 },
+ { 12261527, 137418 },
+ { 12448664, 137867 },
+ { 12637961, 138315 },
+ { 12829435, 138763 },
+ { 13023101, 139211 },
+ { 13218974, 139658 },
+ { 13417071, 140106 },
+ { 13617407, 140553 },
+ { 13819999, 140999 },
+ { 14024862, 141446 },
+ { 14232012, 141892 },
+ { 14441465, 142339 },
+ { 14653238, 142785 },
+ { 14867346, 143230 },
+ { 15083805, 143676 },
+ { 15302632, 144121 },
+ { 15523842, 144566 },
+ { 15747453, 145011 },
+ { 15973479, 145456 },
+ { 16201939, 145900 },
+ { 16432847, 146345 },
+ { 16666221, 146789 },
+ { 16902076, 147233 },
+ { 17140429, 147677 },
+ { 17381297, 148121 },
+ { 17624696, 148564 },
+ { 17870643, 149007 },
+ { 18119154, 149451 },
+ { 18370247, 149894 },
+ { 18623936, 150336 },
+ { 18880241, 150779 },
+ { 19139176, 151222 },
+ { 19400759, 151664 },
+ { 19665007, 152107 },
+ { 19931936, 152549 },
+ { 20201564, 152991 },
+ { 20473907, 153433 },
+ { 20748982, 153875 },
+ { 21026807, 154316 },
+ { 21307399, 154758 },
+ { 21590773, 155199 },
+ { 21876949, 155641 },
+ { 22165941, 156082 },
+ { 22457769, 156523 },
+ { 22752449, 156964 },
+ { 23049999, 157405 },
+ { 23350435, 157846 },
+ { 23653774, 158287 },
+ { 23960036, 158727 },
+ { 24269236, 159168 },
+ { 24581392, 159608 },
+ { 24896521, 160049 },
+ { 25214642, 160489 },
+ { 25535772, 160929 },
+ { 25859927, 161370 },
+ { 26187127, 161810 },
+ { 26517388, 162250 },
+ { 26850728, 162690 },
+ { 27187165, 163130 },
+ { 27526716, 163569 },
+ { 27869400, 164009 },
+ { 28215234, 164449 },
+ { 28564236, 164889 },
+ { 28916423, 165328 },
+ { 29271815, 165768 },
+ { 29630428, 166208 },
+ { 29992281, 166647 },
+ { 30357392, 167087 },
+ { 30725779, 167526 },
+ { 31097459, 167965 },
+ { 31472452, 168405 },
+ { 31850774, 168844 },
+ { 32232445, 169283 },
+ { 32617482, 169723 },
+ { 33005904, 170162 },
+ { 33397730, 170601 },
+ { 33792976, 171041 },
+ { 34191663, 171480 },
+ { 34593807, 171919 },
+ { 34999428, 172358 },
+ { 35408544, 172797 },
+ { 35821174, 173237 },
+ { 36237335, 173676 },
+ { 36657047, 174115 },
+ { 37080329, 174554 },
+ { 37507197, 174993 },
+ { 37937673, 175433 },
+ { 38371773, 175872 },
+ { 38809517, 176311 },
+ { 39250924, 176750 },
+ { 39696012, 177190 },
+ { 40144800, 177629 },
+ { 40597308, 178068 },
+ { 41053553, 178507 },
+ { 41513554, 178947 },
+ { 41977332, 179386 },
+ { 42444904, 179825 },
+ { 42916290, 180265 },
+ { 43391509, 180704 },
+ { 43870579, 181144 },
+ { 44353520, 181583 },
+ { 44840352, 182023 },
+ { 45331092, 182462 },
+ { 45825761, 182902 },
+ { 46324378, 183342 },
+ { 46826961, 183781 },
+ { 47333531, 184221 },
+ { 47844106, 184661 },
+ { 48358706, 185101 },
+ { 48877350, 185541 },
+ { 49400058, 185981 },
+ { 49926849, 186421 },
+ { 50457743, 186861 },
+ { 50992759, 187301 },
+ { 51531916, 187741 },
+ { 52075235, 188181 },
+ { 52622735, 188622 },
+ { 53174435, 189062 },
+ { 53730355, 189502 },
+ { 54290515, 189943 },
+ { 54854935, 190383 },
+ { 55423634, 190824 },
+ { 55996633, 191265 },
+ { 56573950, 191706 },
+ { 57155606, 192146 },
+ { 57741621, 192587 },
+ { 58332014, 193028 },
+ { 58926806, 193470 },
+ { 59526017, 193911 },
+ { 60129666, 194352 },
+ { 60737774, 194793 },
+ { 61350361, 195235 },
+ { 61967446, 195677 },
+ { 62589050, 196118 },
+ { 63215194, 196560 },
+ { 63845897, 197002 },
+ { 64481179, 197444 },
+ { 65121061, 197886 },
+ { 65765563, 198328 },
+ { 66414705, 198770 },
+ { 67068508, 199213 },
+ { 67726992, 199655 },
+ { 68390177, 200098 },
+ { 69058085, 200540 },
+ { 69730735, 200983 },
+ { 70408147, 201426 },
+ { 71090343, 201869 },
+ { 71777343, 202312 },
+ { 72469168, 202755 },
+ { 73165837, 203199 },
+ { 73867373, 203642 },
+ { 74573795, 204086 },
+ { 75285124, 204529 },
+ { 76001380, 204973 },
+ { 76722586, 205417 },
+ { 77448761, 205861 },
+ { 78179926, 206306 },
+ { 78916102, 206750 },
+ { 79657310, 207194 },
+ { 80403571, 207639 },
+ { 81154906, 208084 },
+ { 81911335, 208529 },
+ { 82672880, 208974 },
+ { 83439562, 209419 },
+ { 84211402, 209864 },
+ { 84988421, 210309 },
+ { 85770640, 210755 },
+ { 86558080, 211201 },
+ { 87350762, 211647 },
+ { 88148708, 212093 },
+ { 88951938, 212539 },
+ { 89760475, 212985 },
+ { 90574339, 213432 },
+ { 91393551, 213878 },
+ { 92218133, 214325 },
+ { 93048107, 214772 },
+ { 93883493, 215219 },
+ { 94724314, 215666 },
+ { 95570590, 216114 },
+ { 96422343, 216561 },
+ { 97279594, 217009 },
+ { 98142366, 217457 },
+ { 99010679, 217905 },
+ { 99884556, 218353 },
+ { 100764018, 218801 },
+ { 101649086, 219250 },
+ { 102539782, 219698 },
+ { 103436128, 220147 },
+ { 104338146, 220596 },
+ { 105245857, 221046 },
+ { 106159284, 221495 },
+ { 107078448, 221945 },
+ { 108003370, 222394 },
+ { 108934074, 222844 },
+ { 109870580, 223294 },
+ { 110812910, 223745 },
+ { 111761087, 224195 },
+ { 112715133, 224646 },
+ { 113675069, 225097 },
+ { 114640918, 225548 },
+ { 115612702, 225999 },
+ { 116590442, 226450 },
+ { 117574162, 226902 },
+ { 118563882, 227353 },
+ { 119559626, 227805 },
+ { 120561415, 228258 },
+ { 121569272, 228710 },
+ { 122583219, 229162 },
+ { 123603278, 229615 },
+ { 124629471, 230068 },
+ { 125661822, 230521 },
+ { 126700352, 230974 },
+ { 127745083, 231428 },
+ { 128796039, 231882 },
+ { 129853241, 232336 },
+ { 130916713, 232790 },
+ { 131986475, 233244 },
+ { 133062553, 233699 },
+ { 134144966, 234153 },
+ { 135233739, 234608 },
+ { 136328894, 235064 },
+ { 137430453, 235519 },
+ { 138538440, 235975 },
+ { 139652876, 236430 },
+ { 140773786, 236886 },
+ { 141901190, 237343 },
+ { 143035113, 237799 },
+ { 144175576, 238256 },
+ { 145322604, 238713 },
+ { 146476218, 239170 },
+ { 147636442, 239627 },
+ { 148803298, 240085 },
+ { 149976809, 240542 },
+ { 151156999, 241000 },
+ { 152343890, 241459 },
+ { 153537506, 241917 },
+ { 154737869, 242376 },
+ { 155945002, 242835 },
+ { 157158929, 243294 },
+ { 158379673, 243753 },
+ { 159607257, 244213 },
+ { 160841704, 244673 },
+ { 162083037, 245133 },
+ { 163331279, 245593 },
+ { 164586455, 246054 },
+ { 165848586, 246514 },
+ { 167117696, 246975 },
+ { 168393810, 247437 },
+ { 169676949, 247898 },
+ { 170967138, 248360 },
+ { 172264399, 248822 },
+ { 173568757, 249284 },
+ { 174880235, 249747 },
+ { 176198856, 250209 },
+ { 177524643, 250672 },
+ { 178857621, 251136 },
+ { 180197813, 251599 },
+ { 181545242, 252063 },
+ { 182899933, 252527 },
+ { 184261908, 252991 },
+ { 185631191, 253456 },
+ { 187007807, 253920 },
+ { 188391778, 254385 },
+ { 189783129, 254851 },
+ { 191181884, 255316 },
+ { 192588065, 255782 },
+ { 194001698, 256248 },
+ { 195422805, 256714 },
+ { 196851411, 257181 },
+ { 198287540, 257648 },
+ { 199731215, 258115 },
+ { 201182461, 258582 },
+ { 202641302, 259050 },
+ { 204107760, 259518 },
+ { 205581862, 259986 },
+ { 207063630, 260454 },
+ { 208553088, 260923 },
+ { 210050262, 261392 },
+ { 211555174, 261861 },
+ { 213067849, 262331 },
+ { 214588312, 262800 },
+ { 216116586, 263270 },
+ { 217652696, 263741 },
+ { 219196666, 264211 },
+ { 220748520, 264682 },
+ { 222308282, 265153 },
+ { 223875978, 265625 },
+ { 225451630, 266097 },
+ { 227035265, 266569 },
+ { 228626905, 267041 },
+ { 230226576, 267514 },
+ { 231834302, 267986 },
+ { 233450107, 268460 },
+ { 235074016, 268933 },
+ { 236706054, 269407 },
+ { 238346244, 269881 },
+ { 239994613, 270355 },
+ { 241651183, 270830 },
+ { 243315981, 271305 }
+};
+
+/* integer-arithmetic divisions of type (a * 1000000)/b */
+static inline u64 scaled_div(u64 a, u64 b)
+{
+ BUG_ON(b == 0);
+ return div64_u64(a * 1000000, b);
+}
+
+static inline u32 scaled_div32(u64 a, u64 b)
+{
+ u64 result = scaled_div(a, b);
+
+ if (result > UINT_MAX)
+ return UINT_MAX;
+
+ return result;
+}
+
+static inline u32 ttfwc_calc_x(u32 p)
+{
+ u16 index;
+ u32 f;
+ if (p <= TTFWC_CALC_X_SPLIT){ /* 0.0000 < p <= 0.05 */
+ if (p < TTFWC_SMALLEST_P) /* 0.0000 < p < 0.0001 */
+ index = 0;
+ else /* 0.0001 <= p <= 0.05 */
+ index = p/TTFWC_SMALLEST_P - 1;
+ f = ttfwc_calc_x_lookup[index][1];
+ }else{ /* 0.05 < p <= 1.00 */
+ index = p/(1000000/TTFWC_CALC_X_ARRSIZE) - 1;
+ f = ttfwc_calc_x_lookup[index][0];
+ }
+ return scaled_div32(1, f);
+}
+
+static inline u32 ttfwc_invert_imean(u32 imean)
+{
+ if (imean == UINT_MAX) /* see RFC 4342, 8.5 */
+ return 0;
+ if (unlikely(imean == 0)) /* map 1/0 into 100% */
+ return 1000000;
+ return max_t(u32, scaled_div(1, imean), TTFWC_SMALLEST_P);
+}
+
+static inline u32 btree_x_search(u32 invert_cwnd, int start, int end, int index)
+{
+ int mid;
+ mid = (start+end)/2;
+
+ if (ttfwc_calc_x_lookup[mid][index] < invert_cwnd && ttfwc_calc_x_lookup[mid+1][index] >= invert_cwnd)
+ return ((mid+1)*TTFWC_SMALLEST_P);
+ else if (ttfwc_calc_x_lookup[mid][index] < invert_cwnd)
+ start = mid + 1;
+ else if (ttfwc_calc_x_lookup[mid][index] > invert_cwnd)
+ end = mid - 1;
+
+ return btree_x_search(invert_cwnd, start, end, index);
+}
+
+static inline u32 pseudo_li_calc(u32 cwnd)
+{
+ u32 invert_cwnd, pseudo_p = 1;
+
+ if(cwnd <= 1)
+ return scaled_div32(1, 1000000);
+
+ invert_cwnd = scaled_div32(1, cwnd);
+
+ if (invert_cwnd <= ttfwc_calc_x_lookup[0][1])
+ return scaled_div32(1, TTFWC_SMALLEST_P);
+
+ if (invert_cwnd <= ttfwc_calc_x_lookup[TTFWC_CALC_X_ARRSIZE-1][1])
+ pseudo_p = btree_x_search(invert_cwnd, 0, TTFWC_CALC_X_ARRSIZE-1, 1);
+ else
+ pseudo_p = btree_x_search(invert_cwnd*10000, 0, TTFWC_CALC_X_ARRSIZE-1, 0);
+
+ return scaled_div32(1, pseudo_p);
+}
--
1.7.3.2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment