windowed-filter.h

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 *  Copyright (c) 2016 The Chromium Authors. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *    * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *    * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/*
 *  Note: This code is modified to work under ns-3's environment.
 *  Modified by: Vivek Jain <jain.vivek.anand@gmail.com>
 *               Viyom Mittal <viyommittal@gmail.com>
 *               Mohit P. Tahiliani <tahiliani@nitk.edu.in>
 */
 
// Implements Kathleen Nichols' algorithm for tracking the minimum (or maximum)
// estimate of a stream of samples over some fixed time interval. (E.g.,
// the minimum RTT over the past five minutes.) The algorithm keeps track of
// the best, second best, and third best min (or max) estimates, maintaining an
// invariant that the measurement time of the n'th best >= n-1'th best.
// The algorithm works as follows. On a reset, all three estimates are set to
// the same sample. The second best estimate is then recorded in the second
// quarter of the window, and a third best estimate is recorded in the second
// half of the window, bounding the worst case error when the true min is
// monotonically increasing (or true max is monotonically decreasing) over the
// window.
//
// A new best sample replaces all three estimates, since the new best is lower
// (or higher) than everything else in the window and it is the most recent.
// The window thus effectively gets reset on every new min. The same property
// holds true for second best and third best estimates. Specifically, when a
// sample arrives that is better than the second best but not better than the
// best, it replaces the second and third best estimates but not the best
// estimate. Similarly, a sample that is better than the third best estimate
// but not the other estimates replaces only the third best estimate.
//
// Finally, when the best expires, it is replaced by the second best, which in
// turn is replaced by the third best. The newest sample replaces the third
// best.
 
#ifndef WINDOWED_FILTER_H_
#define WINDOWED_FILTER_H_
 
namespace ns3 {
template <class T>
struct MinFilter
{
public:
  bool operator() (const T& lhs, const T& rhs) const
  {
    if (rhs == 0 || lhs == 0)
      {
        return false;
      }
    return lhs <= rhs;
  }
};
template <class T>
struct MaxFilter
{
public:
  bool operator() (const T& lhs, const T& rhs) const
  {
    if (rhs == 0 || lhs == 0)
      {
        return false;
      }
    return lhs >= rhs;
  }
};
template <class T, class Compare, typename TimeT, typename TimeDeltaT>
class WindowedFilter
{
public:
  WindowedFilter ()
  {
  }
 
  WindowedFilter (TimeDeltaT windowLength, T zeroValue, TimeT zeroTime)
    : m_windowLength (windowLength),
      m_zeroValue (zeroValue),
      m_samples
  {
    Sample (m_zeroValue, zeroTime),
    Sample (m_zeroValue, zeroTime),
    Sample (m_zeroValue, zeroTime)
  } {}
  void SetWindowLength (TimeDeltaT windowLength)
  {
    m_windowLength = windowLength;
  }
  void Update (T new_sample, TimeT new_time)
  {
    // Reset all estimates if they have not yet been initialized, if new sample
    // is a new best, or if the newest recorded estimate is too old.
    if (m_samples[0].sample == m_zeroValue
        || Compare () (new_sample, m_samples[0].sample)
        || new_time - m_samples[2].time > m_windowLength)
      {
        Reset (new_sample, new_time);
        return;
      }
    if (Compare () (new_sample, m_samples[1].sample))
      {
        m_samples[1] = Sample (new_sample, new_time);
        m_samples[2] = m_samples[1];
      }
    else if (Compare () (new_sample, m_samples[2].sample))
      {
        m_samples[2] = Sample (new_sample, new_time);
      }
    // Expire and update estimates as necessary.
    if (new_time - m_samples[0].time > m_windowLength)
      {
        // The best estimate hasn't been updated for an entire window, so promote
        // second and third best estimates.
        m_samples[0] = m_samples[1];
        m_samples[1] = m_samples[2];
        m_samples[2] = Sample (new_sample, new_time);
        // Need to iterate one more time. Check if the new best estimate is
        // outside the window as well, since it may also have been recorded a
        // long time ago. Don't need to iterate once more since we cover that
        // case at the beginning of the method.
        if (new_time - m_samples[0].time > m_windowLength)
          {
            m_samples[0] = m_samples[1];
            m_samples[1] = m_samples[2];
          }
        return;
      }
    if (m_samples[1].sample == m_samples[0].sample
        && new_time - m_samples[1].time > m_windowLength >> 2)
      {
        // A quarter of the window has passed without a better sample, so the
        // second-best estimate is taken from the second quarter of the window.
        m_samples[2] = m_samples[1] = Sample (new_sample, new_time);
        return;
      }
    if (m_samples[2].sample == m_samples[1].sample
        && new_time - m_samples[2].time > m_windowLength >> 1)
      {
        // We've passed a half of the window without a better estimate, so take
        // a third-best estimate from the second half of the window.
        m_samples[2] = Sample (new_sample, new_time);
      }
  }
 
  void Reset (T new_sample, TimeT new_time)
  {
    m_samples[0] = m_samples[1] = m_samples[2] = Sample (new_sample, new_time);
  }
 
  T GetBest () const
  {
    return m_samples[0].sample;
  }
 
  T GetSecondBest () const
  {
    return m_samples[1].sample;
  }
 
  T GetThirdBest () const
  {
    return m_samples[2].sample;
  }
 
  struct Sample
  {
    T sample; 
    TimeT time; 
    Sample ()
    {
    }
 
    Sample (T init_sample, TimeT init_time)
      : sample (init_sample),
        time (init_time)
    {
    }
  };
 
  TimeDeltaT m_windowLength;    
  T          m_zeroValue;       
  Sample     m_samples[3];      
};
 
}  // namespace ns3
#endif  // WINDOWED_FILTER_H_