1300779Struckman/* 2300779Struckman * Codel - The Controlled-Delay Active Queue Management algorithm. 3300779Struckman * 4300779Struckman * $FreeBSD$ 5300779Struckman * 6300779Struckman * Copyright (C) 2016 Centre for Advanced Internet Architectures, 7300779Struckman * Swinburne University of Technology, Melbourne, Australia. 8300779Struckman * Portions of this code were made possible in part by a gift from 9300779Struckman * The Comcast Innovation Fund. 10300779Struckman * Implemented by Rasool Al-Saadi <ralsaadi@swin.edu.au> 11300779Struckman * 12300779Struckman * Copyright (C) 2011-2014 Kathleen Nichols <nichols@pollere.com>. 13300779Struckman * 14300779Struckman * Redistribution and use in source and binary forms, with or without 15300779Struckman * modification, are permitted provided that the following conditions 16300779Struckman * are met: 17300779Struckman * 18300779Struckman * o Redistributions of source code must retain the above copyright 19300779Struckman * notice, this list of conditions, and the following disclaimer, 20300779Struckman * without modification. 21300779Struckman * 22300779Struckman * o Redistributions in binary form must reproduce the above copyright 23300779Struckman * notice, this list of conditions and the following disclaimer in 24300779Struckman * the documentation and/or other materials provided with the 25300779Struckman * distribution. 26300779Struckman * 27300779Struckman * o The names of the authors may not be used to endorse or promote 28300779Struckman * products derived from this software without specific prior written 29300779Struckman * permission. 30300779Struckman * 31300779Struckman * Alternatively, provided that this notice is retained in full, this 32300779Struckman * software may be distributed under the terms of the GNU General Public 33300779Struckman * License ("GPL") version 2, in which case the provisions of the GPL 34300779Struckman * apply INSTEAD OF those given above. 35300779Struckman 36300779Struckman * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 37300779Struckman * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 38300779Struckman * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 39300779Struckman * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 40300779Struckman * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 41300779Struckman * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 42300779Struckman * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 43300779Struckman * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 44300779Struckman * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 45300779Struckman * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 46300779Struckman * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 47300779Struckman */ 48300779Struckman 49300779Struckman#ifndef _IP_DN_AQM_CODEL_H 50300779Struckman#define _IP_DN_AQM_CODEL_H 51300779Struckman 52300779Struckman 53300779Struckman// XXX How to choose MTAG? 54300779Struckman#define FIX_POINT_BITS 16 55300779Struckman 56300779Struckmanenum { 57300779Struckman CODEL_ECN_ENABLED = 1 58300779Struckman}; 59300779Struckman 60300779Struckman/* Codel parameters */ 61300779Struckmanstruct dn_aqm_codel_parms { 62300779Struckman aqm_time_t target; 63300779Struckman aqm_time_t interval; 64300779Struckman uint32_t flags; 65300779Struckman}; 66300779Struckman 67300779Struckman/* codel status variables */ 68300779Struckmanstruct codel_status { 69300779Struckman uint32_t count; /* number of dropped pkts since entering drop state */ 70300779Struckman uint16_t dropping; /* dropping state */ 71300779Struckman aqm_time_t drop_next_time; /* time for next drop */ 72300779Struckman aqm_time_t first_above_time; /* time for first ts over target we observed */ 73300779Struckman uint16_t isqrt; /* last isqrt for control low */ 74300779Struckman uint16_t maxpkt_size; /* max packet size seen so far */ 75300779Struckman}; 76300779Struckman 77300779Struckmanstruct mbuf *codel_extract_head(struct dn_queue *, aqm_time_t *); 78300779Struckmanaqm_time_t control_law(struct codel_status *, 79300779Struckman struct dn_aqm_codel_parms *, aqm_time_t ); 80300779Struckman 81300779Struckman__inline static struct mbuf * 82300779Struckmancodel_dodequeue(struct dn_queue *q, aqm_time_t now, uint16_t *ok_to_drop) 83300779Struckman{ 84300779Struckman struct mbuf * m; 85300779Struckman struct dn_aqm_codel_parms *cprms; 86300779Struckman struct codel_status *cst; 87300779Struckman aqm_time_t pkt_ts, sojourn_time; 88300779Struckman 89300779Struckman *ok_to_drop = 0; 90300779Struckman m = codel_extract_head(q, &pkt_ts); 91300779Struckman 92300779Struckman cst = q->aqm_status; 93300779Struckman 94300779Struckman if (m == NULL) { 95300779Struckman /* queue is empty - we can't be above target */ 96300779Struckman cst->first_above_time= 0; 97300779Struckman return m; 98300779Struckman } 99300779Struckman 100300779Struckman cprms = q->fs->aqmcfg; 101300779Struckman 102300779Struckman /* To span a large range of bandwidths, CoDel runs two 103300779Struckman * different AQMs in parallel. One is sojourn-time-based 104300779Struckman * and takes effect when the time to send an MTU-sized 105300779Struckman * packet is less than target. The 1st term of the "if" 106300779Struckman * below does this. The other is backlog-based and takes 107300779Struckman * effect when the time to send an MTU-sized packet is >= 108300779Struckman * target. The goal here is to keep the output link 109300779Struckman * utilization high by never allowing the queue to get 110300779Struckman * smaller than the amount that arrives in a typical 111300779Struckman * interarrival time (MTU-sized packets arriving spaced 112300779Struckman * by the amount of time it takes to send such a packet on 113300779Struckman * the bottleneck). The 2nd term of the "if" does this. 114300779Struckman */ 115300779Struckman sojourn_time = now - pkt_ts; 116300779Struckman if (sojourn_time < cprms->target || q->ni.len_bytes <= cst->maxpkt_size) { 117300779Struckman /* went below - stay below for at least interval */ 118300779Struckman cst->first_above_time = 0; 119300779Struckman } else { 120300779Struckman if (cst->first_above_time == 0) { 121300779Struckman /* just went above from below. if still above at 122300779Struckman * first_above_time, will say it's ok to drop. */ 123300779Struckman cst->first_above_time = now + cprms->interval; 124300779Struckman } else if (now >= cst->first_above_time) { 125300779Struckman *ok_to_drop = 1; 126300779Struckman } 127300779Struckman } 128300779Struckman return m; 129300779Struckman} 130300779Struckman 131300779Struckman/* 132300779Struckman * Dequeue a packet from queue 'q' 133300779Struckman */ 134300779Struckman__inline static struct mbuf * 135300779Struckmancodel_dequeue(struct dn_queue *q) 136300779Struckman{ 137300779Struckman struct mbuf *m; 138300779Struckman struct dn_aqm_codel_parms *cprms; 139300779Struckman struct codel_status *cst; 140300779Struckman aqm_time_t now; 141300779Struckman uint16_t ok_to_drop; 142300779Struckman 143300779Struckman cst = q->aqm_status;; 144300779Struckman cprms = q->fs->aqmcfg; 145300779Struckman now = AQM_UNOW; 146300779Struckman 147300779Struckman m = codel_dodequeue(q, now, &ok_to_drop); 148300779Struckman if (cst->dropping) { 149300779Struckman if (!ok_to_drop) { 150300779Struckman /* sojourn time below target - leave dropping state */ 151300779Struckman cst->dropping = false; 152300779Struckman } 153300779Struckman /* 154300779Struckman * Time for the next drop. Drop current packet and dequeue 155300779Struckman * next. If the dequeue doesn't take us out of dropping 156300779Struckman * state, schedule the next drop. A large backlog might 157300779Struckman * result in drop rates so high that the next drop should 158300779Struckman * happen now, hence the 'while' loop. 159300779Struckman */ 160300779Struckman while (now >= cst->drop_next_time && cst->dropping) { 161300779Struckman 162300779Struckman /* mark the packet */ 163300779Struckman if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) { 164300779Struckman cst->count++; 165300779Struckman /* schedule the next mark. */ 166300779Struckman cst->drop_next_time = control_law(cst, cprms, 167300779Struckman cst->drop_next_time); 168300779Struckman return m; 169300779Struckman } 170300779Struckman 171300779Struckman /* drop the packet */ 172300779Struckman update_stats(q, 0, 1); 173300779Struckman FREE_PKT(m); 174300779Struckman m = codel_dodequeue(q, now, &ok_to_drop); 175300779Struckman 176300779Struckman if (!ok_to_drop) { 177300779Struckman /* leave dropping state */ 178300779Struckman cst->dropping = false; 179300779Struckman } else { 180300779Struckman cst->count++; 181300779Struckman /* schedule the next drop. */ 182300779Struckman cst->drop_next_time = control_law(cst, cprms, 183300779Struckman cst->drop_next_time); 184300779Struckman } 185300779Struckman } 186300779Struckman /* If we get here we're not in dropping state. The 'ok_to_drop' 187300779Struckman * return from dodequeue means that the sojourn time has been 188300779Struckman * above 'target' for 'interval' so enter dropping state. 189300779Struckman */ 190300779Struckman } else if (ok_to_drop) { 191300779Struckman 192300779Struckman /* if ECN option is disabled or the packet cannot be marked, 193300779Struckman * drop the packet and extract another. 194300779Struckman */ 195300779Struckman if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) { 196300779Struckman update_stats(q, 0, 1); 197300779Struckman FREE_PKT(m); 198300779Struckman m = codel_dodequeue(q, now, &ok_to_drop); 199300779Struckman } 200300779Struckman 201300779Struckman cst->dropping = true; 202300779Struckman 203300779Struckman /* If min went above target close to when it last went 204300779Struckman * below, assume that the drop rate that controlled the 205300779Struckman * queue on the last cycle is a good starting point to 206300779Struckman * control it now. ('drop_next' will be at most 'interval' 207300779Struckman * later than the time of the last drop so 'now - drop_next' 208300779Struckman * is a good approximation of the time from the last drop 209300779Struckman * until now.) 210300779Struckman */ 211300779Struckman cst->count = (cst->count > 2 && ((aqm_stime_t)now - 212300779Struckman (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)? 213300779Struckman cst->count - 2 : 1; 214300779Struckman /* we don't have to set initial guess for Newton's method isqrt as 215300779Struckman * we initilaize isqrt in control_law function when count == 1 */ 216300779Struckman cst->drop_next_time = control_law(cst, cprms, now); 217300779Struckman } 218300779Struckman 219300779Struckman return m; 220300779Struckman} 221300779Struckman 222300779Struckman#endif 223