sys/netpfil/ipfw/dn_aqm_pie.h

   1 /*
   2  * PIE - Proportional Integral controller Enhanced AQM 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  * 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 (1L << 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 ((1LL<<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 (1L<<PIE_FIX_POINT_BITS)
  50
  51
  52 /* PIE options */
  53 enum {
  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 */
  62 struct 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 */
  73 struct 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
  91 enum {
  92         ENQUE = 1,
  93         DROP,
  94         MARKECN
  95 };
  96
  97 /* PIE current state */
  98 enum {
  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
 110 drop_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