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),
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;
215 
216  return;
217 }
218 
219 void
220 RttMeanDeviation::IntegerUpdate (Time m, uint32_t rttShift, uint32_t variationShift)
221 {
222  NS_LOG_FUNCTION (this << m << rttShift << variationShift);
223  // Jacobson/Karels paper appendix A.2
224  int64_t meas = m.GetInteger ();
225  int64_t delta = meas - m_estimatedRtt.GetInteger ();
226  int64_t srtt = (m_estimatedRtt.GetInteger () << rttShift) + delta;
227  m_estimatedRtt = Time::From (srtt >> rttShift);
228  if (delta < 0)
229  {
230  delta = -delta;
231  }
232  delta -= m_estimatedVariation.GetInteger ();
233  int64_t rttvar = m_estimatedVariation.GetInteger () << variationShift;
234  rttvar += delta;
235  m_estimatedVariation = Time::From (rttvar >> variationShift);
236  return;
237 }
238 
239 void
241 {
242  NS_LOG_FUNCTION (this << m);
243  if (m_nSamples)
244  {
245  // If both alpha and beta are reciprocal powers of two, updating can
246  // be done with integer arithmetic according to Jacobson/Karels paper.
247  // If not, since class Time only supports integer multiplication,
248  // must convert Time to floating point and back again
249  uint32_t rttShift = CheckForReciprocalPowerOfTwo (m_alpha);
250  uint32_t variationShift = CheckForReciprocalPowerOfTwo (m_beta);
251  if (rttShift && variationShift)
252  {
253  IntegerUpdate (m, rttShift, variationShift);
254  }
255  else
256  {
258  }
259  }
260  else
261  { // First sample
262  m_estimatedRtt = m; // Set estimate to current
263  m_estimatedVariation = m / 2; // And variation to current / 2
264  NS_LOG_DEBUG ("(first sample) m_estimatedVariation += " << m);
265  }
266  m_nSamples++;
267 }
268 
271 {
272  NS_LOG_FUNCTION (this);
273  return CopyObject<RttMeanDeviation> (this);
274 }
275 
276 void
278 {
279  NS_LOG_FUNCTION (this);
281 }
282 
283 } //namespace ns3
Simulation virtual time values and global simulation resolution.
Definition: nstime.h:102
uint32_t GetNSamples(void) const
gets the number of samples used in the estimates
Smart pointer class similar to boost::intrusive_ptr.
Definition: ptr.h:73
#define NS_LOG_FUNCTION(parameters)
If log level LOG_FUNCTION is enabled, this macro will output all input parameters separated by "...
static TypeId GetTypeId(void)
Get the type ID.
double m_alpha
Filter gain for average.
#define NS_OBJECT_ENSURE_REGISTERED(type)
Register an Object subclass with the TypeId system.
Definition: object-base.h:45
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...
The "Mean--Deviation" RTT estimator, as discussed by Van Jacobson.
static Time From(const int64x64_t &value)
Create a Time in the current unit.
Definition: nstime.h:426
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:202
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:733
static TypeId GetTypeId(void)
Get the type ID.
Time m_initialEstimatedRtt
Initial RTT estimation.
virtual TypeId GetInstanceTypeId(void) const
Get the most derived TypeId for this Object.
Ptr< const AttributeChecker > MakeTimeChecker(const Time min, const Time max)
Helper to make a Time checker with bounded range.
Definition: time.cc:446
virtual ~RttEstimator()
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:355
AttributeValue implementation for Time.
Definition: nstime.h:1069
double ToDouble(enum Unit unit) const
Get the Time value expressed in a particular unit.
Definition: nstime.h:505
Base class for all RTT Estimators.
Definition: rtt-estimator.h:43
List of Attribute name, value and checker triples used to construct Objects.
int64x64_t Abs(const int64x64_t &value)
Absolute value.
Definition: int64x64.h:184
Time m_estimatedRtt
Current estimate.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
Time GetVariation(void) const
Note that this is not a formal statistical variance; it has the the same units as the estimate...
void ConstructSelf(const AttributeConstructionList &attributes)
Complete construction of ObjectBase; invoked by derived classes.
Definition: object-base.cc:80
uint32_t m_nSamples
Number of samples.
int64_t GetInteger(void) const
Get the raw time value, in the current resolution unit.
Definition: nstime.h:399
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:1070
virtual void Reset()
Resets the estimation to its initial state.
void Reset()
Resets the estimator.
double m_beta
Filter gain for variation.
void FloatingPointUpdate(Time m)
Method to update the rtt and variation estimates using floating point arithmetic, used when the value...
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
static Time FromDouble(double value, enum Unit unit)
Create a Time equal to value in unit unit.
Definition: nstime.h:456
Ptr< RttEstimator > Copy() const
Copy object (including current internal state)
void Measurement(Time measure)
Add a new measurement to the estimator.
virtual TypeId GetInstanceTypeId(void) const
Get the most derived TypeId for this Object.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:270
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1007
static const double TOLERANCE
Tolerance used to check reciprocal of two numbers.
Time GetEstimate(void) const
gets the RTT estimate.
second
Definition: nstime.h:114
A base class which provides memory management and object aggregation.
Definition: object.h:87
This class can be used to hold variables of floating point type such as &#39;double&#39; or &#39;float&#39;...
Definition: double.h:41
a unique identifier for an interface.
Definition: type-id.h:58
TypeId SetParent(TypeId tid)
Set the parent TypeId.
Definition: type-id.cc:915
Time m_estimatedVariation
Current estimate variation.
uint32_t CheckForReciprocalPowerOfTwo(double val) const
Utility function to check for possible conversion of a double value (0 < value < 1) to a reciprocal p...