From 4f666bc1136eb581d11dc47741928725c76b09c6 Mon Sep 17 00:00:00 2001 From: Jacob Erlbeck Date: Mon, 20 Jul 2015 12:40:42 +0200 Subject: llc: Add CoDel AQM implementation This commit adds an implementation of the CoDel algorithm based on the reference pseudocode presented in http://queue.acm.org/appendices/codel.html. Instead of abstracting the queue itself, the implementation provides a time stamp based automaton which is invoked after a package has been dequeued. Note that the modifications of the algorithm shown in https://tools.ietf.org/html/draft-ietf-aqm-codel-01 are not yet applied. Sponsored-by: On-Waves ehf --- tests/codel/codel_test.c | 147 ++++++++++++++++++++++++++++++++++++++++++++++ tests/codel/codel_test.ok | 29 +++++++++ 2 files changed, 176 insertions(+) create mode 100644 tests/codel/codel_test.c create mode 100644 tests/codel/codel_test.ok (limited to 'tests/codel') diff --git a/tests/codel/codel_test.c b/tests/codel/codel_test.c new file mode 100644 index 00000000..91bad13e --- /dev/null +++ b/tests/codel/codel_test.c @@ -0,0 +1,147 @@ +/* Test routines for the CoDel implementation + * + * (C) 2015 by sysmocom s.f.m.c. GmbH + * Author: Jacob Erlbeck + */ + +#undef _GNU_SOURCE +#define _GNU_SOURCE + +#if 0 +#include +#include +#endif +#include +#include +#include + +#include "gprs_codel.h" + +#include +#include +#include + +static int do_codel_control(struct gprs_codel *state, const struct timeval *recv, + struct timeval *now, const struct timeval *delta_now, int count) +{ + int drop; + + drop = gprs_codel_control(state, recv, now, -1); + if (drop) { + printf("Dropping packet %d, " + "recv = %d.%03d, now = %d.%03d, " + "codel.count = %d\n", + count, + (int)recv->tv_sec, (int)recv->tv_usec/1000, + (int)now->tv_sec, (int)now->tv_usec/1000, + state->count); + } else { + timeradd(now, delta_now, now); + } + + return drop == 0 ? 0 : 1; +} + +static void test_codel(void) +{ + struct gprs_codel codel; + struct timeval now; + struct timeval recv; + const struct timeval delta_now = {0, 10000}; + const struct timeval init_delta_recv = {0, 5000}; + struct timeval delta_recv; + unsigned count; + unsigned sum = 0; + unsigned dropped = 0; + int drop; + + printf("----- %s START\n", __func__); + gprs_codel_init(&codel); + gprs_codel_set_interval(&codel, 100); + + timerclear(&now); + timerclear(&recv); + delta_recv = init_delta_recv; + + for (count = 0; count < 20; count++, sum++) { + drop = do_codel_control(&codel, &recv, &now, &delta_now, sum); + timeradd(&recv, &delta_recv, &recv); + dropped += drop; + } + + printf("Dropped %d packets\n", dropped); + OSMO_ASSERT(dropped == 0); + OSMO_ASSERT(!codel.dropping); + + for (count = 0; count < 20; count++, sum++) { + drop = do_codel_control(&codel, &recv, &now, &delta_now, sum); + timeradd(&recv, &delta_recv, &recv); + dropped += drop; + } + + OSMO_ASSERT(dropped == 2); + OSMO_ASSERT(codel.dropping); + + /* slow down recv rate */ + delta_recv.tv_usec = delta_now.tv_usec; + + for (count = 0; count < 75; count++, sum++) { + drop = do_codel_control(&codel, &recv, &now, &delta_now, sum); + timeradd(&recv, &delta_recv, &recv); + dropped += drop; + } + + OSMO_ASSERT(dropped == 20); + OSMO_ASSERT(codel.dropping); + + for (count = 0; count < 50; count++, sum++) { + drop = do_codel_control(&codel, &recv, &now, &delta_now, sum); + timeradd(&recv, &delta_recv, &recv); + dropped += drop; + } + + OSMO_ASSERT(dropped == 20); + OSMO_ASSERT(!codel.dropping); + OSMO_ASSERT(codel.count >= 20); + + /* go back to old data rate */ + delta_recv = init_delta_recv; + + for (count = 0; count < 20; count++, sum++) { + drop = do_codel_control(&codel, &recv, &now, &delta_now, sum); + timeradd(&recv, &delta_recv, &recv); + dropped += drop; + } + + OSMO_ASSERT(dropped == 20); + OSMO_ASSERT(!codel.dropping); + + for (count = 0; count < 20; count++, sum++) { + drop = do_codel_control(&codel, &recv, &now, &delta_now, sum); + timeradd(&recv, &delta_recv, &recv); + dropped += drop; + } + + OSMO_ASSERT(dropped == 22); + OSMO_ASSERT(codel.count >= 2); + + printf("Dropped %d packets\n", dropped); + + printf("----- %s END\n", __func__); +} + +static struct log_info info = {}; + +int main(int argc, char **argv) +{ + osmo_init_logging(&info); + log_set_use_color(osmo_stderr_target, 0); + log_set_print_filename(osmo_stderr_target, 0); + log_set_log_level(osmo_stderr_target, LOGL_INFO); + + printf("===== CoDel test START\n"); + test_codel(); + printf("===== CoDel test END\n\n"); + + exit(EXIT_SUCCESS); +} diff --git a/tests/codel/codel_test.ok b/tests/codel/codel_test.ok new file mode 100644 index 00000000..ec0696ec --- /dev/null +++ b/tests/codel/codel_test.ok @@ -0,0 +1,29 @@ +===== CoDel test START +----- test_codel START +Dropped 0 packets +Dropping packet 21, recv = 0.105, now = 0.210, codel.count = 1 +Dropping packet 32, recv = 0.160, now = 0.310, codel.count = 2 +Dropping packet 41, recv = 0.210, now = 0.390, codel.count = 3 +Dropping packet 47, recv = 0.270, now = 0.440, codel.count = 4 +Dropping packet 53, recv = 0.330, now = 0.490, codel.count = 5 +Dropping packet 59, recv = 0.390, now = 0.540, codel.count = 6 +Dropping packet 64, recv = 0.440, now = 0.580, codel.count = 7 +Dropping packet 69, recv = 0.490, now = 0.620, codel.count = 8 +Dropping packet 73, recv = 0.530, now = 0.650, codel.count = 9 +Dropping packet 77, recv = 0.570, now = 0.680, codel.count = 10 +Dropping packet 81, recv = 0.610, now = 0.710, codel.count = 11 +Dropping packet 86, recv = 0.660, now = 0.750, codel.count = 12 +Dropping packet 89, recv = 0.690, now = 0.770, codel.count = 13 +Dropping packet 93, recv = 0.730, now = 0.800, codel.count = 14 +Dropping packet 97, recv = 0.770, now = 0.830, codel.count = 15 +Dropping packet 100, recv = 0.800, now = 0.850, codel.count = 16 +Dropping packet 104, recv = 0.840, now = 0.880, codel.count = 17 +Dropping packet 107, recv = 0.870, now = 0.900, codel.count = 18 +Dropping packet 111, recv = 0.910, now = 0.930, codel.count = 19 +Dropping packet 114, recv = 0.940, now = 0.950, codel.count = 20 +Dropping packet 186, recv = 1.555, now = 1.660, codel.count = 1 +Dropping packet 197, recv = 1.610, now = 1.760, codel.count = 2 +Dropped 22 packets +----- test_codel END +===== CoDel test END + -- cgit v1.2.3