diff options
author | Jacob Erlbeck <jerlbeck@sysmocom.de> | 2015-07-20 12:40:42 +0200 |
---|---|---|
committer | Jacob Erlbeck <jerlbeck@sysmocom.de> | 2015-07-21 19:22:32 +0200 |
commit | 4f666bc1136eb581d11dc47741928725c76b09c6 (patch) | |
tree | ed787c651337acc0324385da373cc58cee441cb1 /src/gprs_codel.c | |
parent | 7f79f0d332316acb306682ecac0a1b812d6023d1 (diff) |
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
Diffstat (limited to 'src/gprs_codel.c')
-rw-r--r-- | src/gprs_codel.c | 179 |
1 files changed, 179 insertions, 0 deletions
diff --git a/src/gprs_codel.c b/src/gprs_codel.c new file mode 100644 index 00000000..02440b4b --- /dev/null +++ b/src/gprs_codel.c @@ -0,0 +1,179 @@ +/* gprs_codel.cpp + * + * Copyright (C) 2015 by Sysmocom s.f.m.c. GmbH + * Author: Jacob Erlbeck <jerlbeck@sysmocom.de> + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. + */ + +#include "gprs_codel.h" +#include "gprs_debug.h" + +#include <osmocom/core/utils.h> + +#include <stdint.h> +#include <stdlib.h> +#include <math.h> + +static void control_law(struct gprs_codel *state, struct timeval *delta) +{ + /* 256 / sqrt(x), limited to 255 */ + static uint8_t inv_sqrt_tab[] = {255, + 255, 181, 147, 128, 114, 104, 96, 90, 85, 80, 77, 73, 71, 68, + 66, 64, 62, 60, 58, 57, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, + 45, 45, 44, 43, 43, 42, 42, 41, 40, 40, 39, 39, 39, 38, 38, 37, + 37, 36, 36, 36, 35, 35, 35, 34, 34, 34, 33, 33, 33, 33, 32, 32, + 32, 32, 31, 31, 31, 31, 30, 30, 30, 30, 29, 29, 29, 29, 29, 28, + 28, 28, 28, 28, 28, 27, 27, 27, 27, 27, 27, 26, 26, 26, 26, 26, + 26, 26, 25, 25, 25, 25, 25, 25, 25, 25, 24, 24, 24, 24, 24, 24, + 24, 24, 24, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 22, 22, 22, + 22, 22, 22, 22, 22, 22, 22, 22, 22, 21, 21, 21, 21, 21, 21, 21, + 21, 21, 21, 21, 21, 21, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, + 20, 20, 20, 20, 20, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, + 19, 19, 19, 19, 19, 19, 19, 18, 18, 18, 18, 18, 18, 18, 18, 18, + 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 17, 17, 17, 17, + 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, + 17, 17, 17, 17 + }; + uint_fast32_t delta_usecs; + uint_fast32_t inv_sqrt; + div_t q; + + if (state->count >= ARRAY_SIZE(inv_sqrt_tab)) + inv_sqrt = 16; + else + inv_sqrt = inv_sqrt_tab[state->count]; + + /* delta = state->interval / sqrt(count) */ + delta_usecs = state->interval.tv_sec * 1000000 + state->interval.tv_usec; + delta_usecs = delta_usecs * inv_sqrt / 256; + + q = div(delta_usecs, 1000000); + delta->tv_sec = q.quot; + delta->tv_usec = q.rem; +} + +void gprs_codel_init(struct gprs_codel *state) +{ + static const struct gprs_codel init_state = {0}; + + *state = init_state; + gprs_codel_set_interval(state, -1); + gprs_codel_set_maxpacket(state, -1); +} + +void gprs_codel_set_interval(struct gprs_codel *state, int interval_ms) +{ + div_t q; + + if (interval_ms <= 0) + interval_ms = GPRS_CODEL_DEFAULT_INTERVAL_MS; + + q = div(interval_ms, 1000); + state->interval.tv_sec = q.quot; + state->interval.tv_usec = q.rem * 1000; + + /* target ~ 5% of interval */ + q = div(interval_ms * 13 / 256, 1000); + state->target.tv_sec = q.quot; + state->target.tv_usec = q.rem * 1000; +} + +void gprs_codel_set_maxpacket(struct gprs_codel *state, int maxpacket) +{ + + if (maxpacket < 0) + maxpacket = GPRS_CODEL_DEFAULT_MAXPACKET; + + state->maxpacket = maxpacket; +} + +/* + * This is an broken up variant of the algorithm being described in + * http://queue.acm.org/appendices/codel.html + */ +int gprs_codel_control(struct gprs_codel *state, const struct timeval *recv, + const struct timeval *now, int bytes) +{ + struct timeval sojourn_time; + struct timeval delta; + + if (recv == NULL) + goto stop_dropping; + + timersub(now, recv, &sojourn_time); + + if (timercmp(&sojourn_time, &state->target, <)) + goto stop_dropping; + + if (bytes >= 0 && (unsigned)bytes <= state->maxpacket) + goto stop_dropping; + + if (!timerisset(&state->first_above_time)) { + timeradd(now, &state->interval, &state->first_above_time); + goto not_ok_to_drop; + } + + if (timercmp(now, &state->first_above_time, <)) + goto not_ok_to_drop; + + /* Ok to drop */ + + if (!state->dropping) { + int recently = 0; + int in_drop_cycle = 0; + if (timerisset(&state->drop_next)) { + timersub(now, &state->drop_next, &delta); + in_drop_cycle = timercmp(&delta, &state->interval, <); + recently = in_drop_cycle; + } + if (!recently) { + timersub(now, &state->first_above_time, &delta); + recently = !timercmp(&delta, &state->interval, <); + }; + if (!recently) + return 0; + + state->dropping = 1; + + if (in_drop_cycle && state->count > 2) + state->count -= 2; + else + state->count = 1; + + state->drop_next = *now; + } else { + if (timercmp(now, &state->drop_next, <)) + return 0; + + state->count += 1; + } + + control_law(state, &delta); + timeradd(&state->drop_next, &delta, &state->drop_next); + +#if 1 + LOGP(DRLCMAC, LOGL_INFO, + "CoDel decided to drop packet, window = %d.%03dms, count = %d\n", + (int)delta.tv_sec, (int)(delta.tv_usec / 1000), state->count); +#endif + return 1; + +stop_dropping: + timerclear(&state->first_above_time); +not_ok_to_drop: + state->dropping = 0; + return 0; +} |