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;
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
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.
virtual TypeId GetInstanceTypeId(void) const
Get the most derived TypeId for this Object.
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
int64_t GetInteger(void) const
Get the raw time value, in the current resolution unit.
Definition: nstime.h:399
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...
double GetSeconds(void) const
Get an approximation of the time stored in this instance in the indicated unit.
Definition: nstime.h:355
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
uint32_t CheckForReciprocalPowerOfTwo(double val) const
Utility function to check for possible conversion of a double value (0 < value < 1) to a reciprocal p...
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition: log.h:204
Time GetEstimate(void) const
gets the RTT estimate.
double ToDouble(enum Unit unit) const
Get the Time value expressed in a particular unit.
Definition: nstime.h:505
void(* Time)(Time oldValue, Time newValue)
TracedValue callback signature for Time.
Definition: nstime.h:743
static TypeId GetTypeId(void)
Get the type ID.
Time m_initialEstimatedRtt
Initial RTT estimation.
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()
AttributeValue implementation for Time.
Definition: nstime.h:1124
Base class for all RTT Estimators.
Definition: rtt-estimator.h:43
List of Attribute name, value and checker triples used to construct Objects.
virtual TypeId GetInstanceTypeId(void) const
Get the most derived TypeId for this Object.
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.
uint32_t GetNSamples(void) const
gets the number of samples used in the estimates
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.
Time GetVariation(void) const
Note that this is not a formal statistical variance; it has the the same units as the estimate...
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:1125
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
void Measurement(Time measure)
Add a new measurement to the estimator.
#define NS_LOG_DEBUG(msg)
Use NS_LOG to output a message of level LOG_DEBUG.
Definition: log.h:272
Time Seconds(double value)
Construct a Time in the indicated unit.
Definition: nstime.h:1062
Ptr< RttEstimator > Copy() const
Copy object (including current internal state)
static const double TOLERANCE
Tolerance used to check reciprocal of two numbers.
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.