2 * Codel - The Controlled-Delay Active Queue Management algorithm.
6 * Copyright (C) 2016 Centre for Advanced Internet Architectures,
7 * Swinburne University of Technology, Melbourne, Australia.
8 * Portions of this code were made possible in part by a gift from
9 * The Comcast Innovation Fund.
10 * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au>
12 * Copyright (C) 2011-2014 Kathleen Nichols <nichols@pollere.com>.
14 * Redistribution and use in source and binary forms, with or without
15 * modification, are permitted provided that the following conditions
18 * o Redistributions of source code must retain the above copyright
19 * notice, this list of conditions, and the following disclaimer,
20 * without modification.
22 * o Redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in
24 * the documentation and/or other materials provided with the
27 * o The names of the authors may not be used to endorse or promote
28 * products derived from this software without specific prior written
31 * Alternatively, provided that this notice is retained in full, this
32 * software may be distributed under the terms of the GNU General Public
33 * License ("GPL") version 2, in which case the provisions of the GPL
34 * apply INSTEAD OF those given above.
36 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
37 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
38 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
39 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
40 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
42 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
43 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
44 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
45 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
46 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
49 #ifndef _IP_DN_AQM_CODEL_H
50 #define _IP_DN_AQM_CODEL_H
52 // XXX How to choose MTAG?
53 #define FIX_POINT_BITS 16
59 /* Codel parameters */
60 struct dn_aqm_codel_parms {
66 /* codel status variables */
68 uint32_t count; /* number of dropped pkts since entering drop state */
69 uint16_t dropping; /* dropping state */
70 aqm_time_t drop_next_time; /* time for next drop */
71 aqm_time_t first_above_time; /* time for first ts over target we observed */
72 uint16_t isqrt; /* last isqrt for control low */
73 uint16_t maxpkt_size; /* max packet size seen so far */
76 struct mbuf *codel_extract_head(struct dn_queue *, aqm_time_t *);
77 aqm_time_t control_law(struct codel_status *,
78 struct dn_aqm_codel_parms *, aqm_time_t );
80 __inline static struct mbuf *
81 codel_dodequeue(struct dn_queue *q, aqm_time_t now, uint16_t *ok_to_drop)
84 struct dn_aqm_codel_parms *cprms;
85 struct codel_status *cst;
86 aqm_time_t pkt_ts, sojourn_time;
89 m = codel_extract_head(q, &pkt_ts);
94 /* queue is empty - we can't be above target */
95 cst->first_above_time= 0;
99 cprms = q->fs->aqmcfg;
101 /* To span a large range of bandwidths, CoDel runs two
102 * different AQMs in parallel. One is sojourn-time-based
103 * and takes effect when the time to send an MTU-sized
104 * packet is less than target. The 1st term of the "if"
105 * below does this. The other is backlog-based and takes
106 * effect when the time to send an MTU-sized packet is >=
107 * target. The goal here is to keep the output link
108 * utilization high by never allowing the queue to get
109 * smaller than the amount that arrives in a typical
110 * interarrival time (MTU-sized packets arriving spaced
111 * by the amount of time it takes to send such a packet on
112 * the bottleneck). The 2nd term of the "if" does this.
114 sojourn_time = now - pkt_ts;
115 if (sojourn_time < cprms->target || q->ni.len_bytes <= cst->maxpkt_size) {
116 /* went below - stay below for at least interval */
117 cst->first_above_time = 0;
119 if (cst->first_above_time == 0) {
120 /* just went above from below. if still above at
121 * first_above_time, will say it's ok to drop. */
122 cst->first_above_time = now + cprms->interval;
123 } else if (now >= cst->first_above_time) {
131 * Dequeue a packet from queue 'q'
133 __inline static struct mbuf *
134 codel_dequeue(struct dn_queue *q)
137 struct dn_aqm_codel_parms *cprms;
138 struct codel_status *cst;
142 cst = q->aqm_status;;
143 cprms = q->fs->aqmcfg;
146 m = codel_dodequeue(q, now, &ok_to_drop);
149 /* sojourn time below target - leave dropping state */
150 cst->dropping = false;
153 * Time for the next drop. Drop current packet and dequeue
154 * next. If the dequeue doesn't take us out of dropping
155 * state, schedule the next drop. A large backlog might
156 * result in drop rates so high that the next drop should
157 * happen now, hence the 'while' loop.
159 while (now >= cst->drop_next_time && cst->dropping) {
160 /* mark the packet */
161 if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) {
163 /* schedule the next mark. */
164 cst->drop_next_time = control_law(cst, cprms,
165 cst->drop_next_time);
169 /* drop the packet */
170 update_stats(q, 0, 1);
172 m = codel_dodequeue(q, now, &ok_to_drop);
175 /* leave dropping state */
176 cst->dropping = false;
179 /* schedule the next drop. */
180 cst->drop_next_time = control_law(cst, cprms,
181 cst->drop_next_time);
184 /* If we get here we're not in dropping state. The 'ok_to_drop'
185 * return from dodequeue means that the sojourn time has been
186 * above 'target' for 'interval' so enter dropping state.
188 } else if (ok_to_drop) {
189 /* if ECN option is disabled or the packet cannot be marked,
190 * drop the packet and extract another.
192 if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) {
193 update_stats(q, 0, 1);
195 m = codel_dodequeue(q, now, &ok_to_drop);
198 cst->dropping = true;
200 /* If min went above target close to when it last went
201 * below, assume that the drop rate that controlled the
202 * queue on the last cycle is a good starting point to
203 * control it now. ('drop_next' will be at most 'interval'
204 * later than the time of the last drop so 'now - drop_next'
205 * is a good approximation of the time from the last drop
208 cst->count = (cst->count > 2 && ((aqm_stime_t)now -
209 (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)?
211 /* we don't have to set initial guess for Newton's method isqrt as
212 * we initilaize isqrt in control_law function when count == 1 */
213 cst->drop_next_time = control_law(cst, cprms, now);