llc: Use CoDel to drop packages from the LLC queue

Currently packets are only dropped if they have reached their maximum
life time. This leads to LLC queues being constantly filled under
load, increasing the latency up to the maximum life time. This kind
of bufferbloat hinders TCP's congestion avoidance algorithms. To keep
the queues short, the CoDel active queue management algorithm can be
used.

This commit changes to llc_dequeue method to apply the CoDel
algorithm to selectively drop LLC frames before they passed to the
TBF layer to be encoded in BSNs. This feature is currently disabled
by default.

The CoDel state is managed per MS since the LLC queues are also kept
in the MS objects.

Note that there is still some buffering in the TBF objects, in the
worst case (CS4) 3.5kByte + LLC-MTU octets are stored there. The
resulting additional packet delay is not (yet) taken into account for
CoDel.

Also note that configuration changes are applied to new MS objects
only.

The following VTY commands are added to the 'pcu' node:

- queue codel           activates CoDel, the interval is selected by
                        the implementation
- queue codel interval <1-1000>
                        activates CoDel with a fixed interval given
                        in centiseconds (10ms-10s)
- no queue codel        deactivates CoDel

Which interval value to use is still an open issue. For high speed
links (e.g. Ethernet), CoDel suggests 100ms. For slower links, the
expected RTT is recommended. The current implementation uses a
default value of 2000ms.

Measurements:

Note that the following measurements depend on several other factors,
most notably the interaction with the SGSN's flow control. They are
just examples to give an idea how CoDel might influence some
parameters.

The measurements have been done with a single E71, first with a
running ping only (Idle), then with an additional TCP download
of a 360k file (Busy). The CoDel interval was set to 1s.

- Idle :
        ping ~400ms, avg queue delay 0ms, dropped 0
- Busy, No CoDel:
        ping ~6s, avg queue delay 4-6s,
        dropped  0, scheduled  948, duration 54s
- Busy, CoDel:
        ping 500-1500ms, avg queue delay ~600ms,
        dropped 77, scheduled 1040, duration 60s

More measurements with two MS downloading in parallel (two
independant measurements per case).

- Busy, No CoDel:
        dropped  0, scheduled 1883, duration 121s
        dropped 19, scheduled 2003, duration 133s
- Busy, CoDel:
        dropped 22, scheduled 1926, duration 116s
        dropped 22, scheduled 1955, duration 108s

Sponsored-by: On-Waves ehf

5 files changed, 91 insertions, 1 deletions

diff --git a/src/bts.h b/src/bts.h
index 1a6d259a..ec17ef21 100644
--- a/src/bts.h
+++ b/src/bts.h
@@ -36,6 +36,9 @@ extern "C" {
 
 #include <stdint.h>
 
+#define LLC_CODEL_DISABLE 0
+#define LLC_CODEL_USE_DEFAULT (-1)
+
 struct BTS;
 struct GprsMs;
 
@@ -152,6 +155,7 @@ struct gprs_rlcmac_bts {
 	uint16_t force_llc_lifetime; /* overrides lifetime from SGSN */
 	uint32_t llc_discard_csec;
 	uint32_t llc_idle_ack_csec;
+	uint32_t llc_codel_interval_msec; /* 0=disabled, -1=use default interval */
 	uint8_t t3142;
 	uint8_t t3169;
 	uint8_t t3191;
diff --git a/src/gprs_ms.cpp b/src/gprs_ms.cpp
index b36c61db..e0023e3d 100644
--- a/src/gprs_ms.cpp
+++ b/src/gprs_ms.cpp
@@ -24,6 +24,7 @@
 #include "bts.h"
 #include "tbf.h"
 #include "gprs_debug.h"
+#include "gprs_codel.h"
 
 #include <time.h>
 
@@ -32,6 +33,8 @@ extern "C" {
 	#include <osmocom/core/utils.h>
 }
 
+#define GPRS_CODEL_SLOW_INTERVAL_MS 2000
+
 extern void *tall_pcu_ctx;
 
 static int64_t now_msec()
@@ -102,8 +105,11 @@ GprsMs::GprsMs(BTS *bts, uint32_t tlli) :
 	m_nack_rate_dl(0),
 	m_reserved_dl_slots(0),
 	m_reserved_ul_slots(0),
-	m_current_trx(NULL)
+	m_current_trx(NULL),
+	m_codel_state(NULL)
 {
+	int codel_interval = LLC_CODEL_USE_DEFAULT;
+
 	LOGP(DRLCMAC, LOGL_INFO, "Creating MS object, TLLI = 0x%08x\n", tlli);
 
 	m_imsi[0] = 0;
@@ -118,6 +124,16 @@ GprsMs::GprsMs(BTS *bts, uint32_t tlli) :
 		m_current_cs_dl = m_bts->bts_data()->initial_cs_dl;
 		if (m_current_cs_dl < 1)
 			m_current_cs_dl = 1;
+
+		codel_interval = m_bts->bts_data()->llc_codel_interval_msec;
+	}
+
+	if (codel_interval) {
+		if (codel_interval == LLC_CODEL_USE_DEFAULT)
+			codel_interval = GPRS_CODEL_SLOW_INTERVAL_MS;
+		m_codel_state = talloc(this, struct gprs_codel);
+		gprs_codel_init(m_codel_state);
+		gprs_codel_set_interval(m_codel_state, codel_interval);
 	}
 	m_last_cs_not_low = now_msec();
 }
diff --git a/src/gprs_ms.h b/src/gprs_ms.h
index 1a135cbb..185ffd23 100644
--- a/src/gprs_ms.h
+++ b/src/gprs_ms.h
@@ -23,6 +23,7 @@
 struct gprs_rlcmac_tbf;
 struct gprs_rlcmac_dl_tbf;
 struct gprs_rlcmac_ul_tbf;
+struct gprs_codel;
 
 #include "cxx_linuxlist.h"
 #include "llc.h"
@@ -92,6 +93,7 @@ public:
 
 	gprs_llc_queue *llc_queue();
 	const gprs_llc_queue *llc_queue() const;
+	gprs_codel *codel_state() const;
 
 	void set_timeout(unsigned secs);
 
@@ -157,6 +159,8 @@ private:
 	uint8_t m_reserved_dl_slots;
 	uint8_t m_reserved_ul_slots;
 	gprs_rlcmac_trx *m_current_trx;
+
+	struct gprs_codel *m_codel_state;
 };
 
 inline uint32_t GprsMs::tlli() const
@@ -207,6 +211,11 @@ inline const gprs_llc_queue *GprsMs::llc_queue() const
 	return &m_llc_queue;
 }
 
+inline gprs_codel *GprsMs::codel_state() const
+{
+	return m_codel_state;
+}
+
 inline unsigned GprsMs::nack_rate_dl() const
 {
 	return m_nack_rate_dl;
diff --git a/src/pcu_vty.c b/src/pcu_vty.c
index ed708f8d..94f89b56 100644
--- a/src/pcu_vty.c
+++ b/src/pcu_vty.c
@@ -116,6 +116,14 @@ static int config_write_pcu(struct vty *vty)
 	if (bts->llc_idle_ack_csec)
 		vty_out(vty, " queue idle-ack-delay %d%s", bts->llc_idle_ack_csec,
 			VTY_NEWLINE);
+	if (bts->llc_codel_interval_msec == LLC_CODEL_USE_DEFAULT)
+		vty_out(vty, " queue codel%s", VTY_NEWLINE);
+	else if (bts->llc_codel_interval_msec == LLC_CODEL_DISABLE)
+		vty_out(vty, " no queue codel%s", VTY_NEWLINE);
+	else
+		vty_out(vty, " queue codel interval %d%s",
+			bts->llc_codel_interval_msec/10, VTY_NEWLINE);
+
 	if (bts->alloc_algorithm == alloc_algorithm_a)
 		vty_out(vty, " alloc-algorithm a%s", VTY_NEWLINE);
 	if (bts->alloc_algorithm == alloc_algorithm_b)
@@ -419,6 +427,46 @@ DEFUN(cfg_pcu_no_queue_hysteresis,
 	return CMD_SUCCESS;
 }
 
+#define QUEUE_CODEL_STR "Set CoDel queue management\n"
+
+DEFUN(cfg_pcu_queue_codel,
+      cfg_pcu_queue_codel_cmd,
+      "queue codel",
+      QUEUE_STR QUEUE_CODEL_STR)
+{
+	struct gprs_rlcmac_bts *bts = bts_main_data();
+
+	bts->llc_codel_interval_msec = LLC_CODEL_USE_DEFAULT;
+
+	return CMD_SUCCESS;
+}
+
+DEFUN(cfg_pcu_queue_codel_interval,
+      cfg_pcu_queue_codel_interval_cmd,
+      "queue codel interval <1-1000>",
+      QUEUE_STR QUEUE_CODEL_STR "Specify interval\n" "Interval in centi-seconds")
+{
+	struct gprs_rlcmac_bts *bts = bts_main_data();
+	uint16_t csec = atoi(argv[0]);
+
+	bts->llc_codel_interval_msec = 10*csec;
+
+	return CMD_SUCCESS;
+}
+
+DEFUN(cfg_pcu_no_queue_codel,
+      cfg_pcu_no_queue_codel_cmd,
+      "no queue codel",
+      NO_STR QUEUE_STR QUEUE_CODEL_STR)
+{
+	struct gprs_rlcmac_bts *bts = bts_main_data();
+
+	bts->llc_codel_interval_msec = LLC_CODEL_DISABLE;
+
+	return CMD_SUCCESS;
+}
+
+
 #define QUEUE_IDLE_ACK_STR "Request an ACK after the last DL LLC frame in centi-seconds\n"
 
 DEFUN(cfg_pcu_queue_idle_ack_delay,
@@ -776,6 +824,9 @@ int pcu_vty_init(const struct log_info *cat)
 	install_element(PCU_NODE, &cfg_pcu_no_queue_lifetime_cmd);
 	install_element(PCU_NODE, &cfg_pcu_queue_hysteresis_cmd);
 	install_element(PCU_NODE, &cfg_pcu_no_queue_hysteresis_cmd);
+	install_element(PCU_NODE, &cfg_pcu_queue_codel_cmd);
+	install_element(PCU_NODE, &cfg_pcu_queue_codel_interval_cmd);
+	install_element(PCU_NODE, &cfg_pcu_no_queue_codel_cmd);
 	install_element(PCU_NODE, &cfg_pcu_queue_idle_ack_delay_cmd);
 	install_element(PCU_NODE, &cfg_pcu_no_queue_idle_ack_delay_cmd);
 	install_element(PCU_NODE, &cfg_pcu_alloc_cmd);
diff --git a/src/tbf_dl.cpp b/src/tbf_dl.cpp
index cdd02bae..4739a500 100644
--- a/src/tbf_dl.cpp
+++ b/src/tbf_dl.cpp
@@ -25,6 +25,7 @@
 #include <gprs_rlcmac.h>
 #include <gprs_debug.h>
 #include <gprs_bssgp_pcu.h>
+#include <gprs_codel.h>
 #include <decoding.h>
 
 #include "pcu_utils.h"
@@ -36,6 +37,7 @@ extern "C" {
 
 #include <errno.h>
 #include <string.h>
+#include <math.h>
 
 /* After sending these frames, we poll for ack/nack. */
 #define POLL_ACK_AFTER_FRAMES 20
@@ -249,6 +251,13 @@ struct msgb *gprs_rlcmac_dl_tbf::llc_dequeue(bssgp_bvc_ctx *bctx)
 
 		gprs_bssgp_update_queue_delay(tv_recv, &tv_now);
 
+		if (ms() && ms()->codel_state()) {
+			int bytes = llc_queue()->octets();
+			if (gprs_codel_control(ms()->codel_state(),
+					tv_recv, &tv_now, bytes))
+				goto drop_frame;
+		}
+
 		/* Is the age below the low water mark? */
 		if (!gprs_llc_queue::is_frame_expired(&tv_now2, tv_disc))
 			break;
@@ -274,6 +283,7 @@ struct msgb *gprs_rlcmac_dl_tbf::llc_dequeue(bssgp_bvc_ctx *bctx)
 		}
 
 		bts->llc_timedout_frame();
+drop_frame:
 		frames++;
 		octets += msg->len;
 		msgb_free(msg);