sys/netpfil/ipfw/dn_aqm_pie.h

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