tcp: delivery rate estimator

Type: feature

First cut implementation with limited testing. The feature is not
enabled by default and the expectation is that cc algorithms will enable
it on demand.

Change-Id: I92b70cb4dabcff0e9ccd1d725952c4880af394da
Signed-off-by: Florin Coras <fcoras@cisco.com>

1 files changed, 312 insertions, 0 deletions

diff --git a/src/plugins/unittest/tcp_test.c b/src/plugins/unittest/tcp_test.c
index f919790b031..e604884d107 100644
--- a/src/plugins/unittest/tcp_test.c
+++ b/src/plugins/unittest/tcp_test.c
@@ -780,6 +780,312 @@ tcp_test_session (vlib_main_t * vm, unformat_input_t * input)
   return rv;
 }
 
+static inline int
+tbt_seq_lt (u32 a, u32 b)
+{
+  return seq_lt (a, b);
+}
+
+static int
+tcp_test_delivery (vlib_main_t * vm, unformat_input_t * input)
+{
+  u32 thread_index = 0, snd_una, *min_seqs = 0;
+  tcp_rate_sample_t _rs = { 0 }, *rs = &_rs;
+  tcp_connection_t _tc, *tc = &_tc;
+  sack_scoreboard_t *sb = &tc->sack_sb;
+  int __clib_unused verbose = 0, i;
+  u64 rate = 100, burst = 100;
+  sack_block_t *sacks = 0;
+  tcp_byte_tracker_t *bt;
+  rb_node_t *root, *rbn;
+  tcp_bt_sample_t *bts;
+
+  while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT)
+    {
+      if (unformat (input, "verbose"))
+	verbose = 1;
+      else
+	{
+	  vlib_cli_output (vm, "parse error: '%U'", format_unformat_error,
+			   input);
+	  return -1;
+	}
+    }
+
+  /* Init data structures */
+  memset (tc, 0, sizeof (*tc));
+  session_main.wrk[thread_index].last_vlib_time = 1;
+  transport_connection_tx_pacer_update (&tc->connection, rate);
+
+  tcp_bt_init (tc);
+  bt = tc->bt;
+
+  /*
+   * Track simple bursts without rxt
+   */
+
+  /* 1) track first burst a time 1 */
+  tcp_bt_track_tx (tc);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 1, "should have 1 sample");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->next == TCP_BTS_INVALID_INDEX, "next should be invalid");
+  TCP_TEST (bts->prev == TCP_BTS_INVALID_INDEX, "prev should be invalid");
+  TCP_TEST (bts->delivered_time == 1, "delivered time should be 1");
+  TCP_TEST (bts->delivered == 0, "delivered should be 0");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_RXT), "not retransmitted");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_APP_LIMITED), "not app limited");
+
+  /* 2) check delivery rate at time 2 */
+  session_main.wrk[thread_index].last_vlib_time = 2;
+  tc->snd_una = tc->snd_nxt = burst;
+  tc->bytes_acked = burst;
+
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 0, "sample should've been consumed");
+  TCP_TEST (tc->delivered_time == 2, "delivered time should be 2");
+  TCP_TEST (tc->delivered == burst, "delivered should be 100");
+  TCP_TEST (rs->ack_time == 1, "ack time should be 1");
+  TCP_TEST (rs->delivered == burst, "delivered should be 100");
+  TCP_TEST (rs->sample_delivered == 0, "sample delivered should be 0");
+  TCP_TEST (rs->tx_rate == rate, "delivered should be %u", rate);
+  TCP_TEST (!(rs->flags & TCP_BTS_IS_RXT), "not retransmitted");
+
+  /* 3) track second burst at time 2 */
+  tcp_bt_track_tx (tc);
+  tc->snd_nxt += burst;
+
+  /* 4) track second burst at time 3 */
+  session_main.wrk[thread_index].last_vlib_time = 3;
+  tcp_bt_track_tx (tc);
+  tc->snd_nxt += burst;
+
+  TCP_TEST (pool_elts (bt->samples) == 2, "should have 2 samples");
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  bts = pool_elt_at_index (bt->samples, bt->head);
+  TCP_TEST (bts->min_seq == tc->snd_una, "min seq should be snd_una");
+  TCP_TEST (bts->next == bt->tail, "next should tail");
+
+  bts = pool_elt_at_index (bt->samples, bt->tail);
+  TCP_TEST (bts->min_seq == tc->snd_nxt - burst,
+	    "min seq should be snd_nxt prior to burst");
+  TCP_TEST (bts->prev == bt->head, "prev should be head");
+
+  /* 5) check delivery rate at time 4 */
+  session_main.wrk[thread_index].last_vlib_time = 4;
+  tc->snd_una = tc->snd_nxt;
+  tc->bytes_acked = 2 * burst;
+
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 0, "sample should've been consumed");
+  TCP_TEST (tc->delivered_time == 4, "delivered time should be 4");
+  TCP_TEST (tc->delivered == 3 * burst, "delivered should be 300 is %u",
+	    tc->delivered);
+  TCP_TEST (rs->ack_time == 2, "ack time should be 2");
+  TCP_TEST (rs->delivered == 2 * burst, "delivered should be 200");
+  TCP_TEST (rs->sample_delivered == burst, "delivered should be 100");
+  TCP_TEST (rs->tx_rate == rate, "delivered should be %u", rate);
+  TCP_TEST (!(rs->flags & TCP_BTS_IS_RXT), "not retransmitted");
+  TCP_TEST (!(bts->flags & TCP_BTS_IS_APP_LIMITED), "not app limited");
+
+  /*
+   * Track retransmissions
+   *
+   * snd_una should be 300 at this point
+   */
+
+  snd_una = tc->snd_una;
+
+  /* 1) track first burst a time 4 */
+  tcp_bt_track_tx (tc);
+  tc->snd_nxt += burst;
+
+  /* 2) track second burst at time 5 */
+  session_main.wrk[thread_index].last_vlib_time = 5;
+  tcp_bt_track_tx (tc);
+  tc->snd_nxt += burst;
+
+  /* 3) track third burst at time 6 */
+  session_main.wrk[thread_index].last_vlib_time = 6;
+  tcp_bt_track_tx (tc);
+  tc->snd_nxt += burst;
+
+  /* 4) track fourth burst at time 7 */
+  session_main.wrk[thread_index].last_vlib_time = 7;
+  /* Limited until last burst is acked */
+  tc->app_limited = snd_una + 4 * burst - 1;
+  tcp_bt_track_tx (tc);
+  tc->snd_nxt += burst;
+
+  /* 5) check delivery rate at time 8
+   *
+   * tc->snd_una = snd_una + 10
+   * sacks:
+   * [snd_una + burst, snd_una + burst + 10]
+   * [snd_una + 2 * burst + 10, snd_una + 2 * burst + 20]
+   */
+  session_main.wrk[thread_index].last_vlib_time = 8;
+  tc->snd_una += 10;
+  tc->bytes_acked = 10;
+  sb->last_sacked_bytes = 20;
+
+  TCP_TEST (pool_elts (bt->samples) == 4, "there should be 4 samples");
+
+  vec_validate (sacks, 1);
+  sacks[0].start = snd_una + burst;
+  sacks[0].end = snd_una + burst + 10;
+  sacks[1].start = snd_una + 2 * burst + 10;
+  sacks[1].end = snd_una + 2 * burst + 20;
+  tc->rcv_opts.sacks = sacks;
+
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 4, "there should be 4 samples");
+  TCP_TEST (tc->delivered_time == 8, "delivered time should be 8");
+  TCP_TEST (tc->delivered == 3 * burst + 30, "delivered should be %u is %u",
+	    3 * burst + 30, tc->delivered);
+  /* All 3 samples have the same delivered number of bytes. So the first is
+   * the reference for delivery estimate. */
+  TCP_TEST (rs->ack_time == 4, "ack time should be 4 is %.2f", rs->ack_time);
+  TCP_TEST (rs->delivered == 30, "delivered should be 30");
+  TCP_TEST (rs->sample_delivered == 3 * burst,
+	    "sample delivered should be %u", 3 * burst);
+  TCP_TEST (rs->tx_rate == rate, "delivered should be %u", rate);
+  TCP_TEST (!(rs->flags & TCP_BTS_IS_RXT), "not retransmitted");
+  TCP_TEST (!(rs->flags & TCP_BTS_IS_APP_LIMITED), "not app limited");
+
+  /* 6) Retransmit and track at time 9
+   *
+   * delivered = 3 * burst + 30
+   * delivered_time = 8 (last ack)
+   *
+   * segments:
+   * [snd_una + 10, snd_una + burst]
+   * [snd_una + burst + 10, snd_una + 2 * burst + 10]
+   * [snd_una + 2 * burst + 20, snd_una + 4 * burst]
+   */
+  session_main.wrk[thread_index].last_vlib_time = 9;
+
+  tcp_bt_track_rxt (tc, snd_una + 10, snd_una + burst);
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  /* The retransmit covers everything left from first burst */
+  TCP_TEST (pool_elts (bt->samples) == 4, "there should be 4 samples");
+
+  tcp_bt_track_rxt (tc, snd_una + burst + 10, snd_una + 2 * burst + 10);
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 5, "there should be 5 samples");
+
+  /* Retransmit covers last sample entirely so it should be removed */
+  tcp_bt_track_rxt (tc, snd_una + 2 * burst + 20, snd_una + 4 * burst);
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 5, "there should be 5 samples");
+
+  vec_validate (min_seqs, 4);
+  min_seqs[0] = snd_una + 10;
+  min_seqs[1] = snd_una + burst;
+  min_seqs[2] = snd_una + burst + 10;
+  min_seqs[3] = snd_una + 2 * burst + 10;
+  min_seqs[4] = snd_una + 2 * burst + 20;
+
+  root = bt->sample_lookup.nodes + bt->sample_lookup.root;
+  bts = bt->samples + bt->head;
+  for (i = 0; i < vec_len (min_seqs); i++)
+    {
+      if (bts->min_seq != min_seqs[i])
+	TCP_TEST (0, "should be %u is %u", min_seqs[i], bts->min_seq);
+      rbn = rb_tree_search_subtree_custom (&bt->sample_lookup, root,
+					   bts->min_seq, tbt_seq_lt);
+      if (rbn->opaque != bts - bt->samples)
+	TCP_TEST (0, "lookup should work");
+      bts = bt->samples + bts->next;
+    }
+
+  /* 7) check delivery rate at time 10
+   *
+   * tc->snd_una = snd_una + 2 * burst
+   * sacks:
+   * [snd_una + 2 * burst + 20, snd_una + 2 * burst + 30]
+   * [snd_una + 2 * burst + 50, snd_una + 2 * burst + 60]
+   */
+  session_main.wrk[thread_index].last_vlib_time = 10;
+  tc->snd_una = snd_una + 2 * burst;
+  tc->bytes_acked = 2 * burst - 10;
+  sb->last_sacked_bytes = 20;
+
+  sacks[0].start = snd_una + 2 * burst + 20;
+  sacks[0].end = snd_una + 2 * burst + 30;
+  sacks[1].start = snd_una + 2 * burst + 50;
+  sacks[1].end = snd_una + 2 * burst + 60;
+
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 3, "num samples should be 3 is %u",
+	    pool_elts (bt->samples));
+  TCP_TEST (tc->delivered_time == 10, "delivered time should be 10");
+  TCP_TEST (tc->delivered == 5 * burst + 40, "delivered should be %u is %u",
+	    5 * burst + 40, tc->delivered);
+  /* A rxt was acked and delivered time for it is 8 (last ack time) */
+  TCP_TEST (rs->ack_time == 2, "ack time should be 2 is %.2f", rs->ack_time);
+  /* delivered_now - delivered_rxt ~ 5 * burst + 40 - 3 * burst - 30 */
+  TCP_TEST (rs->delivered == 2 * burst + 10, "delivered should be 210 is %u",
+	    rs->delivered);
+  TCP_TEST (rs->sample_delivered == 3 * burst + 30,
+	    "sample delivered should be %u", 3 * burst + 30);
+  TCP_TEST (rs->tx_rate == rate, "delivered should be %u", rate);
+  TCP_TEST (rs->flags & TCP_BTS_IS_RXT, "is retransmitted");
+  /* Sample is app limited because of the retransmits */
+  TCP_TEST (rs->flags & TCP_BTS_IS_APP_LIMITED, "is app limited");
+  TCP_TEST (tc->app_limited, "app limited should be set");
+
+  /*
+   * 8) check delivery rate at time 11
+   */
+  session_main.wrk[thread_index].last_vlib_time = 11;
+  tc->snd_una = tc->snd_nxt;
+  tc->bytes_acked = 2 * burst;
+  sb->last_sacked_bytes = 0;
+  sb->last_bytes_delivered = 40;
+
+  memset (rs, 0, sizeof (*rs));
+  tcp_bt_sample_delivery_rate (tc, rs);
+
+  TCP_TEST (tcp_bt_is_sane (bt), "tracker should be sane");
+  TCP_TEST (pool_elts (bt->samples) == 0, "num samples should be 3 is %u",
+	    pool_elts (bt->samples));
+  TCP_TEST (tc->delivered_time == 11, "delivered time should be 10");
+  TCP_TEST (tc->delivered == 7 * burst, "delivered should be %u is %u",
+	    7 * burst, tc->delivered);
+  /* Last rxt was at time 8 */
+  TCP_TEST (rs->ack_time == 3, "ack time should be 3 is %.2f", rs->ack_time);
+  /* delivered_now - delivered_rxt ~ 7 * burst - 3 * burst - 30.
+   * That's because we didn't retransmit any new segment. */
+  TCP_TEST (rs->delivered == 4 * burst - 30, "delivered should be 160 is %u",
+	    rs->delivered);
+  TCP_TEST (rs->sample_delivered == 3 * burst + 30,
+	    "sample delivered should be %u", 3 * burst + 30);
+  TCP_TEST (rs->tx_rate == rate, "delivered should be %u", rate);
+  TCP_TEST (rs->flags & TCP_BTS_IS_RXT, "is retransmitted");
+  TCP_TEST (rs->flags & TCP_BTS_IS_APP_LIMITED, "is app limited");
+  TCP_TEST (tc->app_limited == 0, "app limited should be cleared");
+
+  /*
+   * Cleanup
+   */
+  vec_free (sacks);
+  vec_free (min_seqs);
+  tcp_bt_cleanup (tc);
+  return 0;
+}
+
 static clib_error_t *
 tcp_test (vlib_main_t * vm,
 	  unformat_input_t * input, vlib_cli_command_t * cmd_arg)
@@ -800,12 +1106,18 @@ tcp_test (vlib_main_t * vm,
 	{
 	  res = tcp_test_lookup (vm, input);
 	}
+      else if (unformat (input, "delivery"))
+	{
+	  res = tcp_test_delivery (vm, input);
+	}
       else if (unformat (input, "all"))
 	{
 	  if ((res = tcp_test_sack (vm, input)))
 	    goto done;
 	  if ((res = tcp_test_lookup (vm, input)))
 	    goto done;
+	  if ((res = tcp_test_delivery (vm, input)))
+	    goto done;
 	}
       else
 	break;