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