1 /* 2 * Codel - The Controlled-Delay Active Queue Management algorithm. 3 * 4 * $FreeBSD$ 5 * 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> 11 * 12 * Copyright (C) 2011-2014 Kathleen Nichols <nichols@pollere.com>. 13 * 14 * Redistribution and use in source and binary forms, with or without 15 * modification, are permitted provided that the following conditions 16 * are met: 17 * 18 * o Redistributions of source code must retain the above copyright 19 * notice, this list of conditions, and the following disclaimer, 20 * without modification. 21 * 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 25 * distribution. 26 * 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 29 * permission. 30 * 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. 35 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. 47 */ 48 49 #ifndef _IP_DN_AQM_CODEL_H 50 #define _IP_DN_AQM_CODEL_H 51 52 53 // XXX How to choose MTAG? 54 #define FIX_POINT_BITS 16 55 56 enum { 57 CODEL_ECN_ENABLED = 1 58 }; 59 60 /* Codel parameters */ 61 struct dn_aqm_codel_parms { 62 aqm_time_t target; 63 aqm_time_t interval; 64 uint32_t flags; 65 }; 66 67 /* codel status variables */ 68 struct codel_status { 69 uint32_t count; /* number of dropped pkts since entering drop state */ 70 uint16_t dropping; /* dropping state */ 71 aqm_time_t drop_next_time; /* time for next drop */ 72 aqm_time_t first_above_time; /* time for first ts over target we observed */ 73 uint16_t isqrt; /* last isqrt for control low */ 74 uint16_t maxpkt_size; /* max packet size seen so far */ 75 }; 76 77 struct mbuf *codel_extract_head(struct dn_queue *, aqm_time_t *); 78 aqm_time_t control_law(struct codel_status *, 79 struct dn_aqm_codel_parms *, aqm_time_t ); 80 81 __inline static struct mbuf * 82 codel_dodequeue(struct dn_queue *q, aqm_time_t now, uint16_t *ok_to_drop) 83 { 84 struct mbuf * m; 85 struct dn_aqm_codel_parms *cprms; 86 struct codel_status *cst; 87 aqm_time_t pkt_ts, sojourn_time; 88 89 *ok_to_drop = 0; 90 m = codel_extract_head(q, &pkt_ts); 91 92 cst = q->aqm_status; 93 94 if (m == NULL) { 95 /* queue is empty - we can't be above target */ 96 cst->first_above_time= 0; 97 return m; 98 } 99 100 cprms = q->fs->aqmcfg; 101 102 /* To span a large range of bandwidths, CoDel runs two 103 * different AQMs in parallel. One is sojourn-time-based 104 * and takes effect when the time to send an MTU-sized 105 * packet is less than target. The 1st term of the "if" 106 * below does this. The other is backlog-based and takes 107 * effect when the time to send an MTU-sized packet is >= 108 * target. The goal here is to keep the output link 109 * utilization high by never allowing the queue to get 110 * smaller than the amount that arrives in a typical 111 * interarrival time (MTU-sized packets arriving spaced 112 * by the amount of time it takes to send such a packet on 113 * the bottleneck). The 2nd term of the "if" does this. 114 */ 115 sojourn_time = now - pkt_ts; 116 if (sojourn_time < cprms->target || q->ni.len_bytes <= cst->maxpkt_size) { 117 /* went below - stay below for at least interval */ 118 cst->first_above_time = 0; 119 } else { 120 if (cst->first_above_time == 0) { 121 /* just went above from below. if still above at 122 * first_above_time, will say it's ok to drop. */ 123 cst->first_above_time = now + cprms->interval; 124 } else if (now >= cst->first_above_time) { 125 *ok_to_drop = 1; 126 } 127 } 128 return m; 129 } 130 131 /* 132 * Dequeue a packet from queue 'q' 133 */ 134 __inline static struct mbuf * 135 codel_dequeue(struct dn_queue *q) 136 { 137 struct mbuf *m; 138 struct dn_aqm_codel_parms *cprms; 139 struct codel_status *cst; 140 aqm_time_t now; 141 uint16_t ok_to_drop; 142 143 cst = q->aqm_status;; 144 cprms = q->fs->aqmcfg; 145 now = AQM_UNOW; 146 147 m = codel_dodequeue(q, now, &ok_to_drop); 148 if (cst->dropping) { 149 if (!ok_to_drop) { 150 /* sojourn time below target - leave dropping state */ 151 cst->dropping = false; 152 } 153 /* 154 * Time for the next drop. Drop current packet and dequeue 155 * next. If the dequeue doesn't take us out of dropping 156 * state, schedule the next drop. A large backlog might 157 * result in drop rates so high that the next drop should 158 * happen now, hence the 'while' loop. 159 */ 160 while (now >= cst->drop_next_time && cst->dropping) { 161 162 /* mark the packet */ 163 if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) { 164 cst->count++; 165 /* schedule the next mark. */ 166 cst->drop_next_time = control_law(cst, cprms, 167 cst->drop_next_time); 168 return m; 169 } 170 171 /* drop the packet */ 172 update_stats(q, 0, 1); 173 FREE_PKT(m); 174 m = codel_dodequeue(q, now, &ok_to_drop); 175 176 if (!ok_to_drop) { 177 /* leave dropping state */ 178 cst->dropping = false; 179 } else { 180 cst->count++; 181 /* schedule the next drop. */ 182 cst->drop_next_time = control_law(cst, cprms, 183 cst->drop_next_time); 184 } 185 } 186 /* If we get here we're not in dropping state. The 'ok_to_drop' 187 * return from dodequeue means that the sojourn time has been 188 * above 'target' for 'interval' so enter dropping state. 189 */ 190 } else if (ok_to_drop) { 191 192 /* if ECN option is disabled or the packet cannot be marked, 193 * drop the packet and extract another. 194 */ 195 if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) { 196 update_stats(q, 0, 1); 197 FREE_PKT(m); 198 m = codel_dodequeue(q, now, &ok_to_drop); 199 } 200 201 cst->dropping = true; 202 203 /* If min went above target close to when it last went 204 * below, assume that the drop rate that controlled the 205 * queue on the last cycle is a good starting point to 206 * control it now. ('drop_next' will be at most 'interval' 207 * later than the time of the last drop so 'now - drop_next' 208 * is a good approximation of the time from the last drop 209 * until now.) 210 */ 211 cst->count = (cst->count > 2 && ((aqm_stime_t)now - 212 (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)? 213 cst->count - 2 : 1; 214 /* we don't have to set initial guess for Newton's method isqrt as 215 * we initilaize isqrt in control_law function when count == 1 */ 216 cst->drop_next_time = control_law(cst, cprms, now); 217 } 218 219 return m; 220 } 221 222 #endif 223