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_SCHED_FQ_CODEL_HELPER_H
50 #define _IP_DN_SCHED_FQ_CODEL_HELPER_H
51
52 __inline static struct mbuf *
53 fqc_dodequeue(struct fq_codel_flow *q, aqm_time_t now, uint16_t *ok_to_drop,
54 struct fq_codel_si *si)
55 {
56 struct mbuf * m;
57 struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1);
58 aqm_time_t pkt_ts, sojourn_time;
59
60 *ok_to_drop = 0;
61 m = fq_codel_extract_head(q, &pkt_ts, si);
62
63 if (m == NULL) {
64 /*queue is empty - we can't be above target*/
65 q->cst.first_above_time= 0;
66 return m;
67 }
68
69 /* To span a large range of bandwidths, CoDel runs two
70 * different AQMs in parallel. One is sojourn-time-based
71 * and takes effect when the time to send an MTU-sized
72 * packet is less than target. The 1st term of the "if"
73 * below does this. The other is backlog-based and takes
74 * effect when the time to send an MTU-sized packet is >=
75 * target. The goal here is to keep the output link
76 * utilization high by never allowing the queue to get
77 * smaller than the amount that arrives in a typical
78 * interarrival time (MTU-sized packets arriving spaced
79 * by the amount of time it takes to send such a packet on
80 * the bottleneck). The 2nd term of the "if" does this.
81 */
82 sojourn_time = now - pkt_ts;
83 if (sojourn_time < schk->cfg.ccfg.target || q->stats.len_bytes <= q->cst.maxpkt_size) {
84 /* went below - stay below for at least interval */
85 q->cst.first_above_time = 0;
86 } else {
87 if (q->cst.first_above_time == 0) {
88 /* just went above from below. if still above at
89 * first_above_time, will say it's ok to drop. */
90 q->cst.first_above_time = now + schk->cfg.ccfg.interval;
91 } else if (now >= q->cst.first_above_time) {
92 *ok_to_drop = 1;
93 }
94 }
95 return m;
96 }
97
98 /* Codel dequeue function */
99 __inline static struct mbuf *
100 fqc_codel_dequeue(struct fq_codel_flow *q, struct fq_codel_si *si)
101 {
102 struct mbuf *m;
103 struct dn_aqm_codel_parms *cprms;
104 struct codel_status *cst;
105 aqm_time_t now;
106 uint16_t ok_to_drop;
107 struct fq_codel_schk *schk = (struct fq_codel_schk *)(si->_si.sched+1);
108
109 cst = &q->cst;
110 cprms = &schk->cfg.ccfg;
111
112 now = AQM_UNOW;
113 m = fqc_dodequeue(q, now, &ok_to_drop, si);
114
115 if (cst->dropping) {
116 if (!ok_to_drop) {
117 /* sojourn time below target - leave dropping state */
118 cst->dropping = false;
119 }
120
121 /* Time for the next drop. Drop current packet and dequeue
122 * next. If the dequeue doesn't take us out of dropping
123 * state, schedule the next drop. A large backlog might
124 * result in drop rates so high that the next drop should
125 * happen now, hence the 'while' loop.
126 */
127 while (now >= cst->drop_next_time && cst->dropping) {
128 /* mark the packet */
129 if (cprms->flags & CODEL_ECN_ENABLED && ecn_mark(m)) {
130 cst->count++;
131 /* schedule the next mark. */
132 cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time);
133 return m;
134 }
135
136 /* drop the packet */
137 fq_update_stats(q, si, 0, 1);
138 m_freem(m);
139 m = fqc_dodequeue(q, now, &ok_to_drop, si);
140
141 if (!ok_to_drop) {
142 /* leave dropping state */
143 cst->dropping = false;
144 } else {
145 cst->count++;
146 /* schedule the next drop. */
147 cst->drop_next_time = control_law(cst, cprms, cst->drop_next_time);
148 }
149 }
150 /* If we get here we're not in dropping state. The 'ok_to_drop'
151 * return from dodequeue means that the sojourn time has been
152 * above 'target' for 'interval' so enter dropping state.
153 */
154 } else if (ok_to_drop) {
155 /* if ECN option is disabled or the packet cannot be marked,
156 * drop the packet and extract another.
157 */
158 if (!(cprms->flags & CODEL_ECN_ENABLED) || !ecn_mark(m)) {
159 fq_update_stats(q, si, 0, 1);
160 m_freem(m);
161 m = fqc_dodequeue(q, now, &ok_to_drop,si);
162 }
163
164 cst->dropping = true;
165
166 /* If min went above target close to when it last went
167 * below, assume that the drop rate that controlled the
168 * queue on the last cycle is a good starting point to
169 * control it now. ('drop_next' will be at most 'interval'
170 * later than the time of the last drop so 'now - drop_next'
171 * is a good approximation of the time from the last drop
172 * until now.)
173 */
174 cst->count = (cst->count > 2 && ((aqm_stime_t)now -
175 (aqm_stime_t)cst->drop_next_time) < 8* cprms->interval)? cst->count - 2 : 1;
176
177 /* we don't have to set initial guess for Newton's method isqrt as
178 * we initilaize isqrt in control_law function when count == 1 */
179 cst->drop_next_time = control_law(cst, cprms, now);
180 }
181
182 return m;
183 }
184
185 #endif
Cache object: 66258041437e0a85fd2ae64464f9fb72
|