dn_aqm_pie.h revision 301772 
1/*
2 * PIE - Proportional Integral controller Enhanced AQM algorithm.
3 *
4 * $FreeBSD: stable/10/sys/netpfil/ipfw/dn_aqm_pie.h 301772 2016-06-10 00:00:25Z truckman $
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 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 *    notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 *    notice, this list of conditions and the following disclaimer in the
19 *    documentation and/or other materials provided with the distribution.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#ifndef _IP_DN_AQM_PIE_H
35#define _IP_DN_AQM_PIE_H
36
37#define DN_AQM_PIE 2
38#define PIE_DQ_THRESHOLD_BITS 14
39/* 2^14 =16KB */
40#define PIE_DQ_THRESHOLD (1UL << PIE_DQ_THRESHOLD_BITS)
41#define MEAN_PKTSIZE 800
42
43/* 31-bits because random() generates range from 0->(2**31)-1 */
44#define PIE_PROB_BITS 31
45#define PIE_MAX_PROB ((1ULL<<PIE_PROB_BITS) -1)
46
47/* for 16-bits, we have 3-bits for integer part and 13-bits for fraction */
48#define PIE_FIX_POINT_BITS 13
49#define PIE_SCALE (1UL<<PIE_FIX_POINT_BITS)
50
51
52/* PIE options */
53enum {
54	PIE_ECN_ENABLED =1,
55	PIE_CAPDROP_ENABLED = 2,
56	PIE_ON_OFF_MODE_ENABLED = 4,
57	PIE_DEPRATEEST_ENABLED = 8,
58	PIE_DERAND_ENABLED = 16
59};
60
61/* PIE parameters */
62struct dn_aqm_pie_parms {
63	aqm_time_t	qdelay_ref;	/* AQM Latency Target (default: 15ms) */
64	aqm_time_t	tupdate;		/* a period to calculate drop probability (default:15ms) */
65	aqm_time_t	max_burst;	/* AQM Max Burst Allowance (default: 150ms) */
66	uint16_t	max_ecnth;	/*AQM Max ECN Marking Threshold (default: 10%) */
67	uint16_t	alpha;			/* (default: 1/8) */
68	uint16_t	beta;			/* (default: 1+1/4) */
69	uint32_t	flags;			/* PIE options */
70};
71
72/* PIE status variables */
73struct pie_status{
74	struct callout	aqm_pie_callout;
75	aqm_time_t	burst_allowance;
76	uint32_t	drop_prob;
77	aqm_time_t	current_qdelay;
78	aqm_time_t	qdelay_old;
79	uint64_t	accu_prob;
80	aqm_time_t	measurement_start;
81	aqm_time_t	avg_dq_time;
82	uint32_t	dq_count;
83	uint32_t	sflags;
84	struct dn_aqm_pie_parms *parms;	/* pointer to PIE configurations */
85	/* pointer to parent queue of FQ-PIE sub-queues, or  queue of owner fs. */
86	struct dn_queue	*pq;
87	struct mtx	lock_mtx;
88	uint32_t one_third_q_size; /* 1/3 of queue size, for speed optization */
89};
90
91enum {
92	ENQUE = 1,
93	DROP,
94	MARKECN
95};
96
97/* PIE current state */
98enum {
99	PIE_ACTIVE = 1,
100	PIE_INMEASUREMENT = 2
101};
102
103/*
104 * Check if eneque should drop packet to control delay or not based on
105 * PIe algorithm.
106 * return  DROP if it is time to drop or  ENQUE otherwise.
107 * This function is used by PIE and FQ-PIE.
108 */
109__inline static int
110drop_early(struct pie_status *pst, uint32_t qlen)
111{
112	struct dn_aqm_pie_parms *pprms;
113
114	pprms = pst->parms;
115
116	/* queue is not congested */
117
118	if ((pst->qdelay_old < (pprms->qdelay_ref >> 1)
119		&& pst->drop_prob < PIE_MAX_PROB / 5 )
120		||  qlen <= 2 * MEAN_PKTSIZE)
121		return ENQUE;
122
123
124	if (pst->drop_prob == 0)
125		pst->accu_prob = 0;
126
127	/* increment accu_prob */
128	if (pprms->flags & PIE_DERAND_ENABLED)
129		pst->accu_prob += pst->drop_prob;
130
131	/* De-randomize option
132	 * if accu_prob < 0.85 -> enqueue
133	 * if accu_prob>8.5 ->drop
134	 * between 0.85 and 8.5 || !De-randomize --> drop on prob
135	 *
136	 * (0.85 = 17/20 ,8.5 = 17/2)
137	 */
138	if (pprms->flags & PIE_DERAND_ENABLED) {
139		if(pst->accu_prob < (uint64_t) (PIE_MAX_PROB * 17 / 20))
140			return ENQUE;
141		 if( pst->accu_prob >= (uint64_t) (PIE_MAX_PROB * 17 / 2))
142			return DROP;
143	}
144
145	if (random() < pst->drop_prob) {
146		pst->accu_prob = 0;
147		return DROP;
148	}
149
150	return ENQUE;
151}
152
153#endif
154