A Discrete-Event Network Simulator
API
rtt-estimator.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 //
3 // Copyright (c) 2006 Georgia Tech Research Corporation
4 //
5 // This program is free software; you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License version 2 as
7 // published by the Free Software Foundation;
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program; if not, write to the Free Software
16 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 //
18 // Author: Rajib Bhattacharjea<raj.b@gatech.edu>
19 //
20 
21 // Ported from:
22 // Georgia Tech Network Simulator - Round Trip Time Estimator Class
23 // George F. Riley. Georgia Tech, Spring 2002
24 
25 // Base class allows variations of round trip time estimators to be
26 // implemented
27 
28 #include <iostream>
29 #include <cmath>
30 
31 #include "rtt-estimator.h"
32 #include "ns3/double.h"
33 #include "ns3/log.h"
34 
35 namespace ns3 {
36 
37 NS_LOG_COMPONENT_DEFINE ("RttEstimator");
38 
39 NS_OBJECT_ENSURE_REGISTERED (RttEstimator);
40 
42 static const double TOLERANCE = 1e-6;
43 
44 TypeId
46 {
47  static TypeId tid = TypeId ("ns3::RttEstimator")
48  .SetParent<Object> ()
49  .SetGroupName ("Internet")
50  .AddAttribute ("InitialEstimation",
51  "Initial RTT estimate",
52  TimeValue (Seconds (1.0)),
54  MakeTimeChecker ())
55  ;
56  return tid;
57 }
58 
59 Time
61 {
62  return m_estimatedRtt;
63 }
64 
65 Time
67 {
68  return m_estimatedVariation;
69 }
70 
71 
72 // Base class methods
73 
75  : m_nSamples (0)
76 {
77  NS_LOG_FUNCTION (this);
78 
79  // We need attributes initialized here, not later, so use the
80  // ConstructSelf() technique documented in the manual
84  NS_LOG_DEBUG ("Initialize m_estimatedRtt to " << m_estimatedRtt.GetSeconds () << " sec.");
85 }
86 
88  : Object (c),
89  m_initialEstimatedRtt (c.m_initialEstimatedRtt),
90  m_estimatedRtt (c.m_estimatedRtt),
91  m_estimatedVariation (c.m_estimatedVariation),
92  m_nSamples (c.m_nSamples)
93 {
94  NS_LOG_FUNCTION (this);
95 }
96 
98 {
99  NS_LOG_FUNCTION (this);
100 }
101 
102 TypeId
104 {
105  return GetTypeId ();
106 }
107 
109 {
110  NS_LOG_FUNCTION (this);
111  // Reset to initial state
114  m_nSamples = 0;
115 }
116 
117 uint32_t
119 {
120  return m_nSamples;
121 }
122 
123 //-----------------------------------------------------------------------------
124 //-----------------------------------------------------------------------------
125 // Mean-Deviation Estimator
126 
128 
129 TypeId
131 {
132  static TypeId tid = TypeId ("ns3::RttMeanDeviation")
134  .SetGroupName ("Internet")
135  .AddConstructor<RttMeanDeviation> ()
136  .AddAttribute ("Alpha",
137  "Gain used in estimating the RTT, must be 0 <= alpha <= 1",
138  DoubleValue (0.125),
140  MakeDoubleChecker<double> (0, 1))
141  .AddAttribute ("Beta",
142  "Gain used in estimating the RTT variation, must be 0 <= beta <= 1",
143  DoubleValue (0.25),
145  MakeDoubleChecker<double> (0, 1))
146  ;
147  return tid;
148 }
149 
151 {
152  NS_LOG_FUNCTION (this);
153 }
154 
156  : RttEstimator (c), m_alpha (c.m_alpha), m_beta (c.m_beta)
157 {
158  NS_LOG_FUNCTION (this);
159 }
160 
161 TypeId
163 {
164  return GetTypeId ();
165 }
166 
167 uint32_t
169 {
170  NS_LOG_FUNCTION (this << val);
171  if (val < TOLERANCE)
172  {
173  return 0;
174  }
175  // supports 1/32, 1/16, 1/8, 1/4, 1/2
176  if (std::abs (1/val - 8) < TOLERANCE)
177  {
178  return 3;
179  }
180  if (std::abs (1/val - 4) < TOLERANCE)
181  {
182  return 2;
183  }
184  if (std::abs (1/val - 32) < TOLERANCE)
185  {
186  return 5;
187  }
188  if (std::abs (1/val - 16) < TOLERANCE)
189  {
190  return 4;
191  }
192  if (std::abs (1/val - 2) < TOLERANCE)
193  {
194  return 1;
195  }
196  return 0;
197 }
198 
199 void
201 {
202  NS_LOG_FUNCTION (this << m);
203 
204  // EWMA formulas are implemented as suggested in
205  // Jacobson/Karels paper appendix A.2
206 
207  // SRTT <- (1 - alpha) * SRTT + alpha * R'
208  Time err (m - m_estimatedRtt);
209  double gErr = err.ToDouble (Time::S) * m_alpha;
211 
212  // RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R'|
213  Time difference = Abs (err) - m_estimatedVariation;
214  m_estimatedVariation += difference * m_beta;
215  return;
216 }
217 
218 void
219 RttMeanDeviation::IntegerUpdate (Time m, uint32_t rttShift, uint32_t variationShift)
220 {
221  NS_LOG_FUNCTION (this << m << rttShift << variationShift);
222  // Jacobson/Karels paper appendix A.2
223  int64_t meas = m.GetInteger ();
224  int64_t delta = meas - m_estimatedRtt.GetInteger ();
225  int64_t srtt = (m_estimatedRtt.GetInteger () << rttShift) + delta;
226  m_estimatedRtt = Time::From (srtt >> rttShift);
227  if (delta < 0)
228  {
229  delta = -delta;
230  }
231  delta -= m_estimatedVariation.GetInteger ();
232  int64_t rttvar = m_estimatedVariation.GetInteger () << variationShift;
233  rttvar += delta;
234  m_estimatedVariation = Time::From (rttvar >> variationShift);
235  return;
236 }
237 
238 void
240 {
241  NS_LOG_FUNCTION (this << m);
242  if (m_nSamples)
243  {
244  // If both alpha and beta are reciprocal powers of two, updating can
245  // be done with integer arithmetic according to Jacobson/Karels paper.
246  // If not, since class Time only supports integer multiplication,
247  // must convert Time to floating point and back again
248  uint32_t rttShift = CheckForReciprocalPowerOfTwo (m_alpha);
249  uint32_t variationShift = CheckForReciprocalPowerOfTwo (m_beta);
250  if (rttShift && variationShift)
251  {
252  IntegerUpdate (m, rttShift, variationShift);
253  }
254  else
255  {
257  }
258  }
259  else
260  { // First sample
261  m_estimatedRtt = m; // Set estimate to current
262  m_estimatedVariation = m / 2; // And variation to current / 2
263  NS_LOG_DEBUG ("(first sample) m_estimatedVariation += " << m);
264  }
265  m_nSamples++;
266 }
267 
270 {
271  NS_LOG_FUNCTION (this);
272  return CopyObject<RttMeanDeviation> (this);
273 }
274 
275 void
277 {
278  NS_LOG_FUNCTION (this);
280 }
281 
282 } //namespace ns3
List of Attribute name, value and checker triples used to construct Objects.
This class can be used to hold variables of floating point type such as 'double' or 'float'.
Definition: double.h:41
void ConstructSelf(const AttributeConstructionList &attributes)
Complete construction of ObjectBase; invoked by derived classes.
Definition: object-base.cc:159
A base class which provides memory management and object aggregation.
Definition: object.h:88
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:74
Base class for all RTT Estimators.
Definition: rtt-estimator.h:43
Time m_initialEstimatedRtt
Initial RTT estimation.
virtual TypeId GetInstanceTypeId(void) const
Get the most derived TypeId for this Object.
Time GetEstimate(void) const
gets the RTT estimate.
virtual void Reset()
Resets the estimation to its initial state.
Time m_estimatedVariation
Current estimate variation.
uint32_t m_nSamples
Number of samples.
uint32_t GetNSamples(void) const
gets the number of samples used in the estimates
Time GetVariation(void) const
Note that this is not a formal statistical variance; it has the the same units as the estimate.
virtual ~RttEstimator()
Time m_estimatedRtt
Current estimate.
static TypeId GetTypeId(void)
Get the type ID.
The "Mean--Deviation" RTT estimator, as discussed by Van Jacobson.
static TypeId GetTypeId(void)
Get the type ID.
double m_beta
Filter gain for variation.
void Measurement(Time measure)
Add a new measurement to the estimator.
void Reset()
Resets the estimator.
void FloatingPointUpdate(Time m)
Method to update the rtt and variation estimates using floating point arithmetic, used when the value...
Ptr< RttEstimator > Copy() const
Copy object (including current internal state)
uint32_t CheckForReciprocalPowerOfTwo(double val) const
Utility function to check for possible conversion of a double value (0 < value < 1) to a reciprocal p...
double m_alpha
Filter gain for average.
virtual TypeId GetInstanceTypeId(void) const
Get the most derived TypeId for this Object.
void IntegerUpdate(Time m, uint32_t rttShift, uint32_t variationShift)
Method to update the rtt and variation estimates using integer arithmetic, used when the values of Al...
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:103
double ToDouble(enum Unit unit) const
Get the Time value expressed in a particular unit.
Definition: nstime.h:529
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:379
static Time From(const int64x64_t &value)
Create a Time in the current unit.
Definition: nstime.h:450
static Time FromDouble(double value, enum Unit unit)
Create a Time equal to value in unit unit.
Definition: nstime.h:480
int64_t GetInteger(void) const
Get the raw time value, in the current resolution unit.
Definition: nstime.h:423
@ S
second
Definition: nstime.h:114
AttributeValue implementation for Time.
Definition: nstime.h:1308
a unique identifier for an interface.
Definition: type-id.h:59
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:922
Ptr< const AttributeAccessor > MakeDoubleAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition: double.h:42
Ptr< const AttributeAccessor > MakeTimeAccessor(T1 a1)
Create an AttributeAccessor for a class data member, or a lone class get functor or set method.
Definition: nstime.h:1309
int64x64_t Abs(const int64x64_t &value)
Absolute value.
Definition: int64x64.h:205
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:205
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:273
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by ",...
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1244
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:793
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:522
static const double TOLERANCE
Tolerance used to check reciprocal of two numbers.