lollipop-counter.h

Go to the documentation of this file.

/*
 * Copyright (c) 2020 Universita' di Firenze, Italy
 *
 * SPDX-License-Identifier: GPL-2.0-only
 *
 * Author: Tommaso Pecorella <tommaso.pecorella@unifi.it>
 */
 
#ifndef LOLLIPOP_COUNTER_H
#define LOLLIPOP_COUNTER_H
 
#include "ns3/abort.h"
 
#include <compare>
#include <limits>
 
namespace ns3
{
 
/**
 * @ingroup seq-counters
 * @class LollipopCounter
 *
 * @brief Template class implementing a Lollipop counter as defined in \RFC{8505}, \RFC{6550}, and
 * [Perlman83].
 *
 * A Lollipop counter is a counter that solves initialization and
 * out-of-order problems often occurring in Internet protocols.
 *
 * The counter is split in two regions, an initializing region, and a circular region, having the
 * same size. Assuming a counter using an uint8_t (max value 255), values from 128 and greater are
 * used as a linear sequence to indicate a restart and bootstrap the counter, and the values less
 * than or equal to 127 are used as a circular sequence number space of
 * size 128 as mentioned in \RFC{1982}.
 *
 * In both regions, the comparison between two counters is allowed only if both counters are inside
 * a Sequence Window. The default value for the Sequence Window is equal to 2^N where N is half the
 * number of digits of the underlying type. For an uint8_t the Sequence Window is 16.
 *
 * The counter, by default, is initialized to the maximum counter value minus the Sequence Window
 * plus one, e.g., in case of a uint8_t, to 240.
 *
 * This implementation extends the case presented in RFCs, allowing to use a
 * larger underlying type and to change the Sequence Window size.
 *
 * Warning: two Lollipop counters can be compared only if they are of the same type (same underlying
 * type, and same Sequence Window).
 *
 * References:
 * [Perlman83] Perlman, R., "Fault-Tolerant Broadcast of Routing Information", North-Holland
 * Computer Networks 7: pp. 395-405, DOI 10.1016/0376-5075(83)90034-X, 1983,
 * <https://web.archive.org/web/20180723135334/http://pbg.cs.illinois.edu/courses/cs598fa09/readings/p83.pdf>.
 *
 * @tparam T \explicit The type being used for the counter.
 */
template <class T>
class LollipopCounter
{
  public:
    /**
     * Builds a Lollipop counter with a default initial value.
     *
     * The Sequence Window is set to the default value.
     * The initial value is set to the maximum counter value minus the Sequence Window plus one.
     */
    LollipopCounter()
    {
        NS_ABORT_MSG_UNLESS(std::is_unsigned_v<T>,
                            "Lollipop counters must be defined on unsigned integer types");
 
        uint16_t numberofDigits = std::numeric_limits<T>::digits;
        m_sequenceWindow = 1 << (numberofDigits / 2);
 
        m_value = (m_maxValue - m_sequenceWindow) + 1;
    }
 
    /**
     * Builds a Lollipop counter with a specific initial value.
     *
     * The Sequence Window is set to the default value.
     *
     * @param val the initial value of the Lollipop Counter
     * @tparam T \deduced The type being used for the counter.
     */
    LollipopCounter(T val)
    {
        uint16_t numberofDigits = std::numeric_limits<T>::digits;
        m_sequenceWindow = 1 << (numberofDigits / 2);
 
        m_value = val;
    }
 
    /**
     * Assignment.
     *
     * @param [in] o Value to assign to this LollipopCounter.
     * @returns This LollipopCounter.
     */
    inline LollipopCounter& operator=(const LollipopCounter& o)
    {
        m_value = o.m_value;
        return *this;
    }
 
    /**
     * Resets the counter to its initial value.
     */
    void Reset()
    {
        m_value = (m_maxValue - m_sequenceWindow) + 1;
    }
 
    /**
     * Set the Sequence Window Size and resets the counter.
     *
     * The sequence window is equal to 2^numberOfBits.
     * The counter is reset to maxValue - m_sequenceWindow +1, where
     * maxValue is the maximum number allowed by the underlying type.
     *
     * @param numberOfBits number of bits to use in the Sequence Window
     */
    void SetSequenceWindowSize(uint16_t numberOfBits)
    {
        uint16_t numberofDigits = std::numeric_limits<T>::digits;
 
        NS_ABORT_MSG_IF(
            numberOfBits >= numberofDigits,
            "The size of the Sequence Window should be less than the counter size (which is "
                << +m_maxValue << ")");
 
        m_sequenceWindow = 1 << numberOfBits;
 
        m_value = (m_maxValue - m_sequenceWindow) + 1;
    }
 
    /**
     * Checks if the counter is comparable with another counter (i.e., not desynchronized).
     *
     * If the absolute magnitude of difference of the two
     * sequence counters is greater than Sequence Window, then a
     * desynchronization has occurred and the two sequence
     * numbers are not comparable.
     *
     * Sequence Window is equal to 2^N where N is (by default) half the number
     * of digits of the underlying type.
     *
     * @param val counter to compare
     * @returns true if the counters are comparable.
     */
    bool IsComparable(const LollipopCounter& val) const
    {
        NS_ABORT_MSG_IF(m_sequenceWindow != val.m_sequenceWindow,
                        "Can not compare two Lollipop Counters with different sequence windows");
 
        if ((m_value <= m_circularRegion && val.m_value <= m_circularRegion) ||
            (m_value > m_circularRegion && val.m_value > m_circularRegion))
        {
            // They are desynchronized - comparison is impossible.
            T absDiff = AbsoluteMagnitudeOfDifference(val);
            if (absDiff > m_sequenceWindow)
            {
                return false;
            }
        }
        return true;
    }
 
    /**
     * Checks if a counter is in its starting region.
     *
     * @returns true if a counter is in its starting region.
     */
    bool IsInit() const
    {
        return m_value > m_circularRegion;
    }
 
    /**
     * Arithmetic operator equal-to
     * @param [in] lhs Left hand argument
     * @param [in] rhs Right hand argument
     * @return The result of the operator.
     */
    friend bool operator==(const LollipopCounter& lhs, const LollipopCounter& rhs)
    {
        NS_ABORT_MSG_IF(lhs.m_sequenceWindow != rhs.m_sequenceWindow,
                        "Can not compare two Lollipop Counters with different sequence windows");
 
        return lhs.m_value == rhs.m_value;
    }
 
    /**
     * Spaceship comparison operator. All the other comparison operators
     * are automatically generated from this one.
     *
     * Note that the comparison is a ``std::partial_ordering``, as two
     * lollipop counters could be not comparable, @see IsComparable() for details.
     *
     * @param [in] lhs Left hand argument
     * @param [in] rhs Right hand argument
     * @returns The result of the comparison.
     */
    friend constexpr std::partial_ordering operator<=>(const LollipopCounter& lhs,
                                                       const LollipopCounter& rhs)
    {
        NS_ABORT_MSG_IF(lhs.m_sequenceWindow != rhs.m_sequenceWindow,
                        "Can not compare two Lollipop Counters with different sequence windows");
 
        if (lhs.m_value == rhs.m_value)
        {
            return std::partial_ordering::equivalent;
        }
 
        if ((lhs.m_value <= m_circularRegion && rhs.m_value <= m_circularRegion) ||
            (lhs.m_value > m_circularRegion && rhs.m_value > m_circularRegion))
        {
            // both counters are in the same region
 
            T absDiff = lhs.AbsoluteMagnitudeOfDifference(rhs);
            if (absDiff > lhs.m_sequenceWindow)
            {
                // They are desynchronized - comparison is impossible.
                return std::partial_ordering::unordered;
            }
 
            // They are synchronized - comparison according to RFC1982.
            T serialRegion = ((m_circularRegion >> 1) + 1);
            if (((lhs.m_value < rhs.m_value) && ((rhs.m_value - lhs.m_value) > serialRegion)) ||
                ((lhs.m_value > rhs.m_value) && ((lhs.m_value - rhs.m_value) < serialRegion)))
            {
                return std::partial_ordering::greater;
            }
            return std::partial_ordering::less;
        }
 
        // One counter is in the "high" region and the other is in the in the "lower" region
        bool lhsIsHigher;
        T difference;
 
        if (lhs.m_value > m_circularRegion && rhs.m_value <= m_circularRegion)
        {
            lhsIsHigher = true;
            // this is guaranteed to be positive and between [1...m_lollipopMaxValue].
            difference = lhs.m_value - rhs.m_value;
        }
        else
        {
            lhsIsHigher = false;
            // this is guaranteed to be positive and between [1...m_lollipopMaxValue].
            difference = rhs.m_value - lhs.m_value;
        }
 
        // this is guaranteed to be positive and between [1...m_lollipopMaxValue].
        T distance = (m_maxValue - difference) + 1;
        if (distance <= lhs.m_sequenceWindow)
        {
            lhsIsHigher = !lhsIsHigher;
        }
 
        if (lhsIsHigher)
        {
            return std::partial_ordering::greater;
        }
        return std::partial_ordering::less;
    }
 
    /**
     * Prefix increment operator
     * @param [in] val LollipopCounter to be incremented
     * @return The result of the Prefix increment.
     */
    friend LollipopCounter operator++(LollipopCounter& val) // prefix ++
    {
        val.m_value++;
 
        if (val.m_value == m_circularRegion + 1)
        {
            val.m_value = 0;
        }
 
        return val;
    }
 
    /**
     * Postfix increment operator
     * @param [in] val LollipopCounter to be incremented
     * @param [in] noop ignored argument (used to mark it as a postfix, blame c++).
     * @return The result of the Postfix increment.
     */
    friend LollipopCounter operator++(LollipopCounter& val, int noop) // postfix ++
    {
        LollipopCounter ans = val;
        ++(val); // or just call operator++()
        return ans;
    }
 
    /**
     * Get the counter value.
     *
     * @return the counter value.
     */
    T GetValue() const
    {
        return m_value;
    }
 
    /**
     * Output streamer for LollipopCounter.
     *
     * @param [in,out] os The output stream.
     * @param [in] counter The LollipopCounter to print.
     * @returns The stream.
     */
    friend std::ostream& operator<<(std::ostream& os, const LollipopCounter& counter)
    {
        os << +counter.m_value;
        return os;
    }
 
  private:
    /**
     * Compute the Absolute Magnitude Of Difference between two counters.
     *
     * The Absolute Magnitude Of Difference is considered to
     * be on a circular region, and it is represented by
     * the smallest circular distance between two numbers.
     *
     * Arithmetic operator.
     * @param [in] val Counter to compute the difference against
     * @return The result of the difference.
     */
    T AbsoluteMagnitudeOfDifference(const LollipopCounter& val) const
    {
        // useless because it is computed always on counters on their respective regions.
        // Left (commented) for debugging purposes in case there is a code change.
        // NS_ASSERT_MSG ((m_value <= m_circularRegion && val.m_value <= m_circularRegion) ||
        //                (m_value > m_circularRegion && val.m_value > m_circularRegion),
        //                "Absolute Magnitude Of Difference can be computed only on two values in
        //                the circular region " << +m_value << " - " << +val.m_value);
 
        T absDiffDirect = std::max(m_value, val.m_value) - std::min(m_value, val.m_value);
        T absDiffWrapped = (std::min(m_value, val.m_value) + m_circularRegion + 1) -
                           std::max(m_value, val.m_value);
        T absDiff = std::min(absDiffDirect, absDiffWrapped);
        return absDiff;
    }
 
    T m_value;          //!< Value of the Lollipop Counter.
    T m_sequenceWindow; //!< Sequence window used for comparing two counters.
    static constexpr T m_maxValue =
        std::numeric_limits<T>::max();                     //!< Maximum value of the counter.
    static constexpr T m_circularRegion = m_maxValue >> 1; //!< Circular region of the counter.
};
 
/**
 * @ingroup seq-counters
 * 8 bit Lollipop Counter.
 */
typedef LollipopCounter<uint8_t> LollipopCounter8;
/**
 * @ingroup seq-counters
 * 16 bit Lollipop Counter.
 */
typedef LollipopCounter<uint16_t> LollipopCounter16;
 
} /* namespace ns3 */
 
#endif /* LOLLIPOP_COUNTER_H */