A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
lollipop-counter.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2020 Universita' di Firenze, Italy
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Tommaso Pecorella <tommaso.pecorella@unifi.it>
7 */
8
9#ifndef LOLLIPOP_COUNTER_H
10#define LOLLIPOP_COUNTER_H
11
12#include "ns3/abort.h"
13
14#include <limits>
15
16namespace ns3
17{
18
19/**
20 * \ingroup seq-counters
21 * \class LollipopCounter
22 *
23 * \brief Template class implementing a Lollipop counter as defined in \RFC{8505}, \RFC{6550}, and
24 * [Perlman83].
25 *
26 * A Lollipop counter is a counter that solves initialization and
27 * out-of-order problems often occurring in Internet protocols.
28 *
29 * The counter is split in two regions, an initializing region, and a circular region, having the
30 * same size. Assuming a counter using an uint8_t (max value 255), values from 128 and greater are
31 * used as a linear sequence to indicate a restart and bootstrap the counter, and the values less
32 * than or equal to 127 are used as a circular sequence number space of
33 * size 128 as mentioned in \RFC{1982}.
34 *
35 * In both regions, the comparison between two counters is allowed only if both counters are inside
36 * a Sequence Window. The default value for the Sequence Window is equal to 2^N where N is half the
37 * number of digits of the underlying type. For an uint8_t the Sequence Window is 16.
38 *
39 * The counter, by default, is initialized to the maximum counter value minus the Sequence Window
40 * plus one, e.g., in case of a uint8_t, to 240.
41 *
42 * This implementation extends the case presented in RFCs, allowing to use a
43 * larger underlying type and to change the Sequence Window size.
44 *
45 * Warning: two Lollipop counters can be compared only if they are of the same type (same underlying
46 * type, and same Sequence Window).
47 *
48 * References:
49 * [Perlman83] Perlman, R., "Fault-Tolerant Broadcast of Routing Information", North-Holland
50 * Computer Networks 7: pp. 395-405, DOI 10.1016/0376-5075(83)90034-X, 1983,
51 * <https://web.archive.org/web/20180723135334/http://pbg.cs.illinois.edu/courses/cs598fa09/readings/p83.pdf>.
52 *
53 * \tparam T \explicit The type being used for the counter.
54 */
55template <class T>
57{
58 public:
59 /**
60 * Builds a Lollipop counter with a default initial value.
61 *
62 * The Sequence Window is set to the default value.
63 * The initial value is set to the maximum counter value minus the Sequence Window plus one.
64 */
66 {
67 NS_ABORT_MSG_UNLESS(std::is_unsigned<T>::value,
68 "Lollipop counters must be defined on unsigned integer types");
69
70 uint16_t numberofDigits = std::numeric_limits<T>::digits;
71 m_sequenceWindow = 1 << (numberofDigits / 2);
72
74 }
75
76 /**
77 * Builds a Lollipop counter with a specific initial value.
78 *
79 * The Sequence Window is set to the default value.
80 *
81 * \param val the initial value of the Lollipop Counter
82 * \tparam T \deduced The type being used for the counter.
83 */
85 {
86 uint16_t numberofDigits = std::numeric_limits<T>::digits;
87 m_sequenceWindow = 1 << (numberofDigits / 2);
88
89 m_value = val;
90 }
91
92 /**
93 * Assignment.
94 *
95 * \param [in] o Value to assign to this LollipopCounter.
96 * \returns This LollipopCounter.
97 */
99 {
100 m_value = o.m_value;
101 return *this;
102 }
103
104 /**
105 * Resets the counter to its initial value.
106 */
107 void Reset()
108 {
110 }
111
112 /**
113 * Set the Sequence Window Size and resets the counter.
114 *
115 * The sequence window is equal to 2^numberOfBits.
116 * The counter is reset to maxValue - m_sequenceWindow +1, where
117 * maxValue is the maximum number allowed by the underlying type.
118 *
119 * \param numberOfBits number of bits to use in the Sequence Window
120 */
121 void SetSequenceWindowSize(uint16_t numberOfBits)
122 {
123 uint16_t numberofDigits = std::numeric_limits<T>::digits;
124
126 numberOfBits >= numberofDigits,
127 "The size of the Sequence Window should be less than the counter size (which is "
128 << +m_maxValue << ")");
129
130 m_sequenceWindow = 1 << numberOfBits;
131
133 }
134
135 /**
136 * Checks if the counter is comparable with another counter (i.e., not desynchronized).
137 *
138 * If the absolute magnitude of difference of the two
139 * sequence counters is greater than Sequence Window, then a
140 * desynchronization has occurred and the two sequence
141 * numbers are not comparable.
142 *
143 * Sequence Window is equal to 2^N where N is (by default) half the number
144 * of digits of the underlying type.
145 *
146 * \param val counter to compare
147 * \returns true if the counters are comparable.
148 */
149 bool IsComparable(const LollipopCounter& val) const
150 {
152 "Can not compare two Lollipop Counters with different sequence windows");
153
156 {
157 // They are desynchronized - comparison is impossible.
158 T absDiff = AbsoluteMagnitudeOfDifference(val);
159 if (absDiff > m_sequenceWindow)
160 {
161 return false;
162 }
163 }
164 return true;
165 }
166
167 /**
168 * Checks if a counter is in its starting region.
169 *
170 * \returns true if a counter is in its starting region.
171 */
172 bool IsInit() const
173 {
174 return m_value > m_circularRegion;
175 }
176
177 /**
178 * Arithmetic operator equal-to
179 * \param [in] lhs Left hand argument
180 * \param [in] rhs Right hand argument
181 * \return The result of the operator.
182 */
183 friend bool operator==(const LollipopCounter& lhs, const LollipopCounter& rhs)
184 {
186 "Can not compare two Lollipop Counters with different sequence windows");
187
188 return lhs.m_value == rhs.m_value;
189 }
190
191 /**
192 * Arithmetic operator greater-than
193 * \param [in] lhs Left hand argument
194 * \param [in] rhs Right hand argument
195 * \return The result of the operator.
196 */
197 friend bool operator>(const LollipopCounter& lhs, const LollipopCounter& rhs)
198 {
200 "Can not compare two Lollipop Counters with different sequence windows");
201
202 if (lhs.m_value == rhs.m_value)
203 {
204 return false;
205 }
206
207 if ((lhs.m_value <= m_circularRegion && rhs.m_value <= m_circularRegion) ||
209 {
210 // both counters are in the same region
211
212 T absDiff = lhs.AbsoluteMagnitudeOfDifference(rhs);
213 if (absDiff > lhs.m_sequenceWindow)
214 {
215 // They are desynchronized - comparison is impossible.
216 // return false because we can not return anything else.
217 return false;
218 }
219
220 // They are synchronized - comparison according to RFC1982.
221 T serialRegion = ((m_circularRegion >> 1) + 1);
222 return (((lhs.m_value < rhs.m_value) && ((rhs.m_value - lhs.m_value) > serialRegion)) ||
223 ((lhs.m_value > rhs.m_value) && ((lhs.m_value - rhs.m_value) < serialRegion)));
224 }
225
226 // One counter is in the "high" region and the other is in the in the "lower" region
227 bool lhsIsHigher;
228 T difference;
229
231 {
232 lhsIsHigher = true;
233 // this is guaranteed to be positive and between [1...m_lollipopMaxValue].
234 difference = lhs.m_value - rhs.m_value;
235 }
236 else
237 {
238 lhsIsHigher = false;
239 // this is guaranteed to be positive and between [1...m_lollipopMaxValue].
240 difference = rhs.m_value - lhs.m_value;
241 }
242
243 T distance = (m_maxValue - difference) +
244 1; // this is guaranteed to be positive and between [1...m_lollipopMaxValue].
245 if (distance > lhs.m_sequenceWindow)
246 {
247 return lhsIsHigher;
248 }
249 else
250 {
251 return !lhsIsHigher;
252 }
253
254 // this should never be reached.
255 return false;
256 }
257
258 /**
259 * Arithmetic operator less-than
260 * \param [in] lhs Left hand argument
261 * \param [in] rhs Right hand argument
262 * \return The result of the operator.
263 */
264 friend bool operator<(const LollipopCounter& lhs, const LollipopCounter& rhs)
265 {
266 if (!lhs.IsComparable(rhs))
267 {
268 return false;
269 }
270
271 if (lhs > rhs || lhs == rhs)
272 {
273 return false;
274 }
275
276 return true;
277 }
278
279 /**
280 * Prefix increment operator
281 * \param [in] val LollipopCounter to be incremented
282 * \return The result of the Prefix increment.
283 */
285 {
286 val.m_value++;
287
288 if (val.m_value == val.m_circularRegion + 1)
289 {
290 val.m_value = 0;
291 }
292
293 return val;
294 }
295
296 /**
297 * Postfix increment operator
298 * \param [in] val LollipopCounter to be incremented
299 * \param [in] noop ignored argument (used to mark it as a postfix, blame c++).
300 * \return The result of the Postfix increment.
301 */
302 friend LollipopCounter operator++(LollipopCounter& val, int noop) // postfix ++
303 {
304 LollipopCounter ans = val;
305 ++(val); // or just call operator++()
306 return ans;
307 }
308
309 /**
310 * Get the counter value.
311 *
312 * \return the counter value.
313 */
314 T GetValue() const
315 {
316 return m_value;
317 }
318
319 /**
320 * Output streamer for LollipopCounter.
321 *
322 * \param [in,out] os The output stream.
323 * \param [in] counter The LollipopCounter to print.
324 * \returns The stream.
325 */
326 friend std::ostream& operator<<(std::ostream& os, const LollipopCounter& counter)
327 {
328 os << +counter.m_value;
329 return os;
330 }
331
332 private:
333 /**
334 * Compute the Absolute Magnitude Of Difference between two counters.
335 *
336 * The Absolute Magnitude Of Difference is considered to
337 * be on a circular region, and it is represented by
338 * the smallest circular distance between two numbers.
339 *
340 * Arithmetic operator.
341 * \param [in] val Counter to compute the difference against
342 * \return The result of the difference.
343 */
345 {
346 // useless because it is computed always on counters on their respective regions.
347 // Left (commented) for debugging purposes in case there is a code change.
348 // NS_ASSERT_MSG ((m_value <= m_circularRegion && val.m_value <= m_circularRegion) ||
349 // (m_value > m_circularRegion && val.m_value > m_circularRegion),
350 // "Absolute Magnitude Of Difference can be computed only on two values in
351 // the circular region " << +m_value << " - " << +val.m_value);
352
353 T absDiffDirect = std::max(m_value, val.m_value) - std::min(m_value, val.m_value);
354 T absDiffWrapped = (std::min(m_value, val.m_value) + m_circularRegion + 1) -
355 std::max(m_value, val.m_value);
356 T absDiff = std::min(absDiffDirect, absDiffWrapped);
357 return absDiff;
358 }
359
360 T m_value; //!< Value of the Lollipop Counter.
361 T m_sequenceWindow; //!< Sequence window used for comparing two counters.
362 static constexpr T m_maxValue =
363 std::numeric_limits<T>::max(); //!< Maximum value of the counter.
364 static constexpr T m_circularRegion = m_maxValue >> 1; //!< Circular region of the counter.
365};
366
367/**
368 * \ingroup seq-counters
369 * 8 bit Lollipop Counter.
370 */
372/**
373 * \ingroup seq-counters
374 * 16 bit Lollipop Counter.
375 */
377
378} /* namespace ns3 */
379
380#endif /* LOLLIPOP_COUNTER_H */
Template class implementing a Lollipop counter as defined in RFC 8505 , RFC 6550 ,...
static constexpr T m_maxValue
Maximum value of the counter.
friend LollipopCounter operator++(LollipopCounter &val, int noop)
Postfix increment operator.
T AbsoluteMagnitudeOfDifference(const LollipopCounter &val) const
Compute the Absolute Magnitude Of Difference between two counters.
T m_value
Value of the Lollipop Counter.
LollipopCounter()
Builds a Lollipop counter with a default initial value.
friend LollipopCounter operator++(LollipopCounter &val)
Prefix increment operator.
friend std::ostream & operator<<(std::ostream &os, const LollipopCounter &counter)
Output streamer for LollipopCounter.
T GetValue() const
Get the counter value.
T m_sequenceWindow
Sequence window used for comparing two counters.
friend bool operator<(const LollipopCounter &lhs, const LollipopCounter &rhs)
Arithmetic operator less-than.
bool IsInit() const
Checks if a counter is in its starting region.
static constexpr T m_circularRegion
Circular region of the counter.
LollipopCounter(T val)
Builds a Lollipop counter with a specific initial value.
LollipopCounter & operator=(const LollipopCounter &o)
Assignment.
friend bool operator==(const LollipopCounter &lhs, const LollipopCounter &rhs)
Arithmetic operator equal-to.
void SetSequenceWindowSize(uint16_t numberOfBits)
Set the Sequence Window Size and resets the counter.
bool IsComparable(const LollipopCounter &val) const
Checks if the counter is comparable with another counter (i.e., not desynchronized).
friend bool operator>(const LollipopCounter &lhs, const LollipopCounter &rhs)
Arithmetic operator greater-than.
void Reset()
Resets the counter to its initial value.
#define NS_ABORT_MSG_UNLESS(cond, msg)
Abnormal program termination if a condition is false, with a message.
Definition abort.h:133
#define NS_ABORT_MSG_IF(cond, msg)
Abnormal program termination if a condition is true, with a message.
Definition abort.h:97
LollipopCounter< uint8_t > LollipopCounter8
8 bit Lollipop Counter.
LollipopCounter< uint16_t > LollipopCounter16
16 bit Lollipop Counter.
Every class exported by the ns3 library is enclosed in the ns3 namespace.