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 | |
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')
-rw-r--r-- | src/Makefile.am | 6 | ||||
-rw-r--r-- | src/gprs_codel.c | 179 | ||||
-rw-r--r-- | src/gprs_codel.h | 108 |
3 files changed, 291 insertions, 2 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index a63281fa..35874164 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -54,7 +54,8 @@ libgprs_la_SOURCES = \ sba.cpp \ decoding.cpp \ llc.cpp \ - rlc.cpp + rlc.cpp \ + gprs_codel.c if ENABLE_SYSMOBTS libgprs_la_SOURCES += \ @@ -99,7 +100,8 @@ noinst_HEADERS = \ decoding.h \ llc.h \ pcu_utils.h \ - cxx_linuxlist.h + cxx_linuxlist.h \ + gprs_codel.h osmo_pcu_SOURCES = pcu_main.cpp 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; +} diff --git a/src/gprs_codel.h b/src/gprs_codel.h new file mode 100644 index 00000000..fb744232 --- /dev/null +++ b/src/gprs_codel.h @@ -0,0 +1,108 @@ +/* gprs_codel.h + * + * This is an implementation of the CoDel algorithm based on the reference + * pseudocode (see http://queue.acm.org/appendices/codel.html). + * Instead of abstracting the queue itself, the following implementation + * provides a time stamp based automaton. The main work is done by a single + * decision function which updates the state and tells whether to pass or to + * drop a packet after it has been taken from the queue. + * + * 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. + */ + +#pragma once + +#include <sys/time.h> + +/* Spec default values */ +#define GPRS_CODEL_DEFAULT_INTERVAL_MS 100 +#define GPRS_CODEL_DEFAULT_MAXPACKET 512 + +#ifdef __cplusplus +extern "C" { +#endif + +struct gprs_codel { + int dropping; + unsigned count; + struct timeval first_above_time; + struct timeval drop_next; + struct timeval target; + struct timeval interval; + unsigned maxpacket; +}; + +/*! + * \brief Decide about packet drop and update CoDel state + * + * This function takes timing information and decides whether the packet in + * question should be dropped in order to keep related queue in a 'good' state. + * The function is meant to be called when the packet is dequeued. + * + * The CoDel state is updated by this function. + * + * \param state A pointer to the CoDel state of this queue + * \param recv The time when the packet has entered the queue, + * use NULL if dequeueing was not possible because the queue is + * empty + * \param now The current (dequeueing) time + * \param bytes The number of bytes currently stored in the queue (-1 if + * unknown) + * + * \return != 0 if the packet should be dropped, 0 otherwise + */ +int gprs_codel_control(struct gprs_codel *state, const struct timeval *recv, + const struct timeval *now, int bytes); + +/*! + * \brief Initialise CoDel state + * + * This function initialises the CoDel state object. It sets the interval time + * to the default value (GPRS_CODEL_DEFAULT_INTERVAL_MS). + * + * \param state A pointer to the CoDel state of this queue + */ +void gprs_codel_init(struct gprs_codel *state); + +/*! + * \brief Set interval time + * + * This function changes the interval time. + * The target time is derived from the interval time as proposed in the spec + * (5% of interval time). + * + * \param state A pointer to the CoDel state of this queue + * \param interval_ms The initial interval in ms to be used (<= 0 selects the + * default value) + */ +void gprs_codel_set_interval(struct gprs_codel *state, int interval_ms); + +/*! + * \brief Set max packet size + * + * This function changes the maxpacket value. If no more than this number of + * bytes are still stored in the queue, no dropping will be done. + * + * \param state A pointer to the CoDel state of this queue + * \param maxpacket The value in bytes + */ +void gprs_codel_set_maxpacket(struct gprs_codel *state, int maxpacket); + +#ifdef __cplusplus +} +#endif |