ewma.hh

Click is a modular router toolkit. To use it you ll need to know how to compile and install the sof

 *
 *  Example: <code>DirectEWMAX@<StabilityEWMAXParameters@<10, unsigned, int@>
 *  @></code> defines a EWMA with user-settable alpha (stability shift)
 *  initially equal to 1/16, scaling factor 10, and value type unsigned.
 *
 *  A <code>DirectEWMAX@<StabilityEWMAXParameters@<...@> @></code> object has
 *  stability_shift() and set_stability_shift() methods.
 */
template <unsigned SCALE, typename T = unsigned, typename U = int>
class StabilityEWMAXParameters { public:

    typedef T value_type;
    typedef U signed_value_type;

    /** @brief  Construct a StabilityEWMAXParameters with initial alpha 1/16. */
    StabilityEWMAXParameters()
	: _stability(4) {
    }

    /** @brief  Return the current stability shift.
     *
     *  The current alpha equals 1. / (2 ** stability_shift()). */
    unsigned stability_shift() const {
	return _stability;
    }

    /** @brief  Set the current stability shift.
     *  @param  stability_shift  new value */
    void set_stability_shift(unsigned stability_shift) {
	_stability = stability_shift;
    }

    /** @brief  Return this EWMA's scaling factor (bits of fraction).
     *  @return  the 1st template parameter */
    static unsigned scale() {
	return SCALE;
    }

    /** @brief  Return this EWMA's scaled value for one. */
    static value_type scaled_one() {
	return (value_type) 1 << SCALE;
    }

    /** @brief  Return this EWMA's compensation.
     *  @return  1 << (stability_shift() - 1) */
    unsigned compensation() const {
	return 1 << (stability_shift() - 1);
    }

  private:

    unsigned _stability;

};



/** @class RateEWMAX include/click/ewma.hh <click/ewma.hh>
 *  @brief  An exponentially weighted moving average used to measure a rate.
 *
 *  The RateEWMAX template class represents an exponentially weighted moving
 *  average that measures a <em>rate</em>: a count of events per unit time.
 *  The average starts out with value 0.
 *
 *  RateEWMAX adds to DirectEWMAX a concept of epochs, which are periods of
 *  time.  A RateEWMAX object collects samples over the current epoch.  When
 *  the epoch closes, the collected sample count is used to update the moving
 *  average.  Thus, the moving average is measured in samples per epoch.  The
 *  rate() and unparse_rate() member functions return the rate in samples per
 *  <em>second</em>, rather than per epoch.  These functions use the epoch
 *  frequency to translate between epochs and seconds.
 *
 *  Note that it often makes sense to call update() before calling
 *  scaled_average(), rate(), or unparse_rate(), in case an epoch or two has
 *  passed and the average should take account of passing time.
 *
 *  The template parameter P defines the EWMA parameters required by
 *  DirectEWMAX, and three others: a rate count, an epoch measurement, and an
 *  epoch frequency.
 *
 *  The rate count is the number of rates measured per object.  Usually it is
 *  1.
 *
 *  The epoch measurement is a function that returns the current epoch as an
 *  unsigned number.  Epochs should increase monotonically.
 *
 *  The epoch frequency is the number of epochs per second, and is only used
 *  by rate() and unparse_rate().
 *
 *  These are defined by:
 *
 *  <dl>
 *  <dt><strong>P::rate_count</strong></dt>
 *  <dd>The rate count, as a static constant (for example, defined by an
 *  enum).</dd>
 *
 *  <dt><strong>unsigned P::epoch()</strong></dt>
 *  <dd>This function returns the current epoch number.</dd>
 *
 *  <dt><strong>unsigned P::epoch_frequency()</strong></dt>
 *  <dd>This function returns the number of epochs per second.</dd>
 *  </dl>
 *
 *  Since RateEWMAX inherits from an object of type P, these members are
 *  also directly available to callers.
 *
 *  The RateEWMAXParameters type is a good template argument for RateEWMAX.
 *
 *  @sa DirectEWMAX
 */
template <typename P>
class RateEWMAX : public P { public:

    typedef typename P::value_type value_type;
    typedef typename P::signed_value_type signed_value_type;

    /** @brief  Create a rate EWMA with initial value(s) 0. */
    RateEWMAX() {
	_current_epoch = P::epoch();
	for (unsigned i = 0; i < P::rate_count; i++)
	    _current[i] = 0;
    }

    /** @brief  Return the current scaled moving average.
     *  @param  ratenum  rate index (0 <= ratenum < rate_count)
     *  @note   The returned value has scale() bits of fraction.
     *  @note   scaled_average() does not check the current epoch.
     *		If an epoch might have passed since the last update(), you
     *		should call update(0, @a ratenum) before calling this
     *		function. */
    signed_value_type scaled_average(unsigned ratenum = 0) const {
	// note: return type must be signed!
	return _avg[ratenum].scaled_average();
    }

    /** @brief  Returns one of the average's scaling factors (bits of
     *		fraction). */
    unsigned scale(unsigned ratenum = 0) const {
	return _avg[ratenum].scale();
    }

    /** @brief  Return the current rate in samples per second.
     *  @param  ratenum  rate index (0 <= ratenum < rate_count)
     *  @note   The returned value is unscaled.
     *  @note   rate() does not check the current epoch.
     *		If an epoch might have passed since the last update(), you
     *		should call update(0, @a ratenum) before calling this
     *		function. */
    inline int rate(unsigned ratenum = 0) const;

    /** @brief  Update the sample count for the current epoch.
     *  @param  delta    increment for current epoch sample count
     *  @param  ratenum  rate index (0 <= ratenum < rate_count)
     *  @note   If the epoch has changed since the last update(),
     *		this function applies the last epoch's sample count (if any)
     *		to the relevant moving average, accounts for any passage of
     *		time (in case one or more epochs have passed with no samples),
     *		and clears the sample count for	the new epoch. */
    inline void update(signed_value_type delta, unsigned ratenum = 0);

    /** @brief  Unparse the current average into a String.
     *  @param  ratenum  rate index (0 <= ratenum < rate_count)
     *  @note   The returned value is unscaled, but may contain a fractional
     *  part.
     *  @note   unparse_rate() does not check the current epoch.
     *		If an epoch might have passed since the last update(), you
     *		should call update(0, @a ratenum) before calling this
     *		function. */
    String unparse_rate(unsigned ratenum = 0) const;

  private:

    unsigned _current_epoch;
    value_type _current[P::rate_count];
    DirectEWMAX<P> _avg[P::rate_count];

    inline void update_time(unsigned now);

};

/** @class RateEWMAXParameters include/click/ewma.hh <click/ewma.hh>
 *  @brief  Parameters for a RateEWMA with constant scaling factor
 *	    and alpha, one rate count, and epochs of jiffies.
 *
 *  The RateEWMAXParameters template class is used as a template argument
 *  to RateEWMAX.  It defines a EWMA with fixed constant scaling factor and
 *  alpha and one rate count.  The EWMA uses jiffies as epochs.  Template
 *  parameters are as for DirectEWMAXParameters.
 *
 *  Example: <code>RateEWMAX@<RateEWMAXParameters@<4, 10, unsigned, int@>
 *  @></code> defines a rate EWMA with user-settable alpha (stability shift)
 *  initially equal to 1/16, scaling factor 10, and value type unsigned.
 */
template <unsigned STABILITY, unsigned SCALE, typename T = unsigned, typename U = int>
class RateEWMAXParameters : public FixedEWMAXParameters<STABILITY, SCALE, T, U> { public:
    enum {
	rate_count = 1
    };

    /** @brief  Return the current epoch number.
     *  @note   RateEWMAXParameters measures epochs in jiffies. */
    static unsigned epoch() {
	return click_jiffies();
    }

    /** @brief  Return the number of epochs (jiffies) per second. */
    static unsigned epoch_frequency() {
	return CLICK_HZ;
    }
};

/** @brief A RateEWMAX with stability shift 4 (alpha 1/16), scaling factor 10
 *  (10 bits of fraction), one rate, and underlying type <code>unsigned</code>
 *  that measures epochs in jiffies. */
typedef RateEWMAX<RateEWMAXParameters<4, 10> > RateEWMA;


template <typename P>
inline void
RateEWMAX<P>::update_time(unsigned now)
{
    unsigned jj = _current_epoch;
    if (now != jj) {
	for (unsigned i = 0; i < P::rate_count; i++) {
	    // adjust the average rate using the last measured packets
	    _avg[i].update(_current[i]);

	    // adjust for time w/ no packets
	    if (jj + 1 != now)
		_avg[i].update_n(0, now - jj - 1);
	    _current[i] = 0;
	}
	_current_epoch = now;
    }
}

template <typename P>
inline void
RateEWMAX<P>::update(signed_value_type delta, unsigned ratenum)
{
    update_time(P::epoch());
    _current[ratenum] += delta;
}

template <typename P>
inline int
RateEWMAX<P>::rate(unsigned ratenum) const
{
    return (scaled_average(ratenum) * P::epoch_frequency()) >> _avg[ratenum].scale();
}

template <typename P>
inline String
RateEWMAX<P>::unparse_rate(unsigned ratenum) const
{
    return cp_unparse_real2(scaled_average(ratenum) * P::epoch_frequency(), _avg[ratenum].scale());
}

CLICK_ENDDECLS
#endif