ewma.hh

Go to the documentation of this file.

#ifndef CLICK_EWMA_HH
#define CLICK_EWMA_HH
#include <click/glue.hh>
#include <click/confparse.hh>
CLICK_DECLS
 
template <unsigned alpha, unsigned shift>
class EXPSMOOTH {
    public:
    unsigned val;
 
    void update(unsigned obs) {
        val = (obs * alpha + ((1 << shift) - alpha) * obs) >> shift;
    }
 
 
    unsigned unscaled_average() const {
        return val;
    }
 
    unsigned average() const {
        return val;
    }
};
 
template <typename P>
class DirectEWMAX : public P { public:
 
    typedef typename P::value_type value_type;
 
    DirectEWMAX()
        : _avg(0) {
    }
 
    DirectEWMAX(value_type scaled_value)
        : _avg(scaled_value) {
    }
 
    value_type scaled_average() const {
        return _avg;
    }
 
    value_type unscaled_average() const {
        return (_avg + (P::scaled_one() >> 1)) >> P::scale();
    }
 
    void clear() {
        _avg = 0;
    }
 
    inline void assign(value_type scaled_value) {
        _avg = scaled_value;
    }
 
    inline void update(value_type x);
 
    void update_n(value_type x, unsigned n);
 
    String unparse() const;
 
    inline void update_with(value_type x) CLICK_DEPRECATED;
 
  private:
 
    value_type _avg;
 
};
 
template <typename P>
inline void
DirectEWMAX<P>::update(value_type x)
{
    value_type x_scaled = (x << P::scale()) + P::compensation();
    unsigned stability = P::stability_shift();
#if HAVE_ARITHMETIC_RIGHT_SHIFT
    _avg += static_cast<typename P::signed_value_type>(x_scaled - _avg) >> stability;
#else
    if (x_scaled < _avg)
        _avg -= (_avg - x_scaled) >> stability;
    else
        _avg += (x_scaled - _avg) >> stability;
#endif
}
 
template <typename P>
void
DirectEWMAX<P>::update_n(value_type x, unsigned n)
{
    // XXX use table lookup
    value_type x_scaled = x << P::scale();
    if (n >= 100)
        _avg = x_scaled;
    else {
        x_scaled += P::compensation();
        unsigned stability = P::stability_shift();
#if HAVE_ARITHMETIC_RIGHT_SHIFT
        for (; n > 0; n--)
            _avg += static_cast<typename P::signed_value_type>(x_scaled - _avg) >> stability;
#else
        if (x_scaled < _avg)
            for (; n > 0; n--)
                _avg -= (_avg - x_scaled) >> stability;
        else
            for (; n > 0; n--)
                _avg += (x_scaled - _avg) >> stability;
#endif
    }
}
 
template <typename P>
inline String
DirectEWMAX<P>::unparse() const
{
    return cp_unparse_real2(scaled_average(), P::scale());
}
 
template <typename P>
inline void
DirectEWMAX<P>::update_with(value_type x)
{
    update(x);
}
 
template <unsigned STABILITY, unsigned SCALE, typename T = unsigned, typename U = int>
class FixedEWMAXParameters { public:
 
    typedef T value_type;
    typedef U signed_value_type;
 
    static unsigned stability_shift() {
        return STABILITY;
    }
 
    static unsigned scale() {
        static_assert(SCALE < sizeof(T) * 8, "SCALE too big for EWMA type.");
        return SCALE;
    }
 
    static value_type scaled_one() {
        return (value_type) 1 << SCALE;
    }
 
    static unsigned compensation() {
        return 1 << (STABILITY - 1);
    }
 
};
 
typedef DirectEWMAX<FixedEWMAXParameters<4, 10> > DirectEWMA;
 
typedef DirectEWMAX<FixedEWMAXParameters<3, 10> > FastDirectEWMA;
 
 
template <unsigned SCALE, typename T = unsigned, typename U = int>
class StabilityEWMAXParameters { public:
 
    typedef T value_type;
    typedef U signed_value_type;
 
    StabilityEWMAXParameters()
        : _stability(4) {
    }
 
    unsigned stability_shift() const {
        return _stability;
    }
 
    void set_stability_shift(unsigned stability_shift) {
        _stability = stability_shift;
    }
 
    static unsigned scale() {
        return SCALE;
    }
 
    static value_type scaled_one() {
        return (value_type) 1 << SCALE;
    }
 
    unsigned compensation() const {
        return 1 << (stability_shift() - 1);
    }
 
  private:
 
    unsigned _stability;
 
};
 
 
 
template <typename P>
class RateEWMAX : public P { public:
 
    typedef typename P::value_type value_type;
    typedef typename P::signed_value_type signed_value_type;
 
    RateEWMAX() {
        _current_epoch = P::epoch();
        for (unsigned i = 0; i < P::rate_count; i++)
            _current[i] = 0;
    }
 
    signed_value_type scaled_average(unsigned ratenum = 0) const {
        // note: return type must be signed!
        return _avg[ratenum].scaled_average();
    }
 
    unsigned scale(unsigned ratenum = 0) const {
        return _avg[ratenum].scale();
    }
 
    inline int rate(unsigned ratenum = 0) const;
 
    inline void update(signed_value_type delta, unsigned ratenum = 0);
 
    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);
 
};
 
template <unsigned STABILITY, unsigned SCALE, typename T = unsigned, typename U = int>
class RateEWMAXParameters : public FixedEWMAXParameters<STABILITY, SCALE, T, U> { public:
    enum {
        rate_count = 1
    };
 
    static unsigned epoch() {
        return click_jiffies();
    }
 
    static unsigned epoch_frequency() {
        return CLICK_HZ;
    }
};
 
typedef RateEWMAX<RateEWMAXParameters<4, 10, uint64_t, int64_t> > 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