View | Details | Raw Unified | Return to bug 1405
Collapse All | Expand All

(-)a/src/internet/model/rtt-estimator.cc (-184 / +137 lines)
 Lines 18-37    Link Here 
18
// Author: Rajib Bhattacharjea<raj.b@gatech.edu>
18
// Author: Rajib Bhattacharjea<raj.b@gatech.edu>
19
//
19
//
20
20
21
22
// Ported from:
21
// Ported from:
23
// Georgia Tech Network Simulator - Round Trip Time Estimation Class
22
// Georgia Tech Network Simulator - Round Trip Time Estimator Class
24
// George F. Riley.  Georgia Tech, Spring 2002
23
// George F. Riley.  Georgia Tech, Spring 2002
25
24
26
// Implements several variations of round trip time estimators
25
// Base class allows variations of round trip time estimators to be
26
// implemented
27
27
28
#include <iostream>
28
#include <iostream>
29
#include <cmath>
29
30
30
#include "rtt-estimator.h"
31
#include "rtt-estimator.h"
31
#include "ns3/simulator.h"
32
#include "ns3/double.h"
32
#include "ns3/double.h"
33
#include "ns3/integer.h"
34
#include "ns3/uinteger.h"
35
#include "ns3/log.h"
33
#include "ns3/log.h"
36
34
37
namespace ns3 {
35
namespace ns3 {
 Lines 40-130    Link Here 
40
38
41
NS_OBJECT_ENSURE_REGISTERED (RttEstimator);
39
NS_OBJECT_ENSURE_REGISTERED (RttEstimator);
42
40
41
static const double TOLERANCE = 1e-6;
42
43
TypeId 
43
TypeId 
44
RttEstimator::GetTypeId (void)
44
RttEstimator::GetTypeId (void)
45
{
45
{
46
  static TypeId tid = TypeId ("ns3::RttEstimator")
46
  static TypeId tid = TypeId ("ns3::RttEstimator")
47
    .SetParent<Object> ()
47
    .SetParent<Object> ()
48
    .AddAttribute ("MaxMultiplier", 
49
                   "Maximum RTO Multiplier",
50
                   UintegerValue (64),
51
                   MakeUintegerAccessor (&RttEstimator::m_maxMultiplier),
52
                   MakeUintegerChecker<uint16_t> ())
53
    .AddAttribute ("InitialEstimation", 
48
    .AddAttribute ("InitialEstimation", 
54
                   "Initial RTT estimation",
49
                   "Initial RTT estimate",
55
                   TimeValue (Seconds (1.0)),
50
                   TimeValue (Seconds (1.0)),
56
                   MakeTimeAccessor (&RttEstimator::m_initialEstimatedRtt),
51
                   MakeTimeAccessor (&RttEstimator::m_initialEstimatedRtt),
57
                   MakeTimeChecker ())
52
                   MakeTimeChecker ())
58
    .AddAttribute ("MinRTO", 
59
                   "Minimum retransmit timeout value",
60
                   TimeValue (Seconds (0.2)), // RFC2988 says min RTO=1 sec, but Linux uses 200ms. See http://www.postel.org/pipermail/end2end-interest/2004-November/004402.html
61
                   MakeTimeAccessor (&RttEstimator::SetMinRto,
62
                                     &RttEstimator::GetMinRto),
63
                   MakeTimeChecker ())
64
  ;
53
  ;
65
  return tid;
54
  return tid;
66
}
55
}
67
56
68
void 
57
Time
69
RttEstimator::SetMinRto (Time minRto)
58
RttEstimator::GetEstimate (void) const
70
{
59
{
71
  NS_LOG_FUNCTION (this << minRto);
60
  return m_estimatedRtt;
72
  m_minRto = minRto;
73
}
74
Time 
75
RttEstimator::GetMinRto (void) const
76
{
77
  return m_minRto;
78
}
79
void 
80
RttEstimator::SetCurrentEstimate (Time estimate)
81
{
82
  NS_LOG_FUNCTION (this << estimate);
83
  m_currentEstimatedRtt = estimate;
84
}
85
Time 
86
RttEstimator::GetCurrentEstimate (void) const
87
{
88
  return m_currentEstimatedRtt;
89
}
61
}
90
62
91
63
Time 
92
//RttHistory methods
64
RttEstimator::GetVariation (void) const
93
RttHistory::RttHistory (SequenceNumber32 s, uint32_t c, Time t)
94
  : seq (s), count (c), time (t), retx (false)
95
{
65
{
96
  NS_LOG_FUNCTION (this);
66
  return m_estimatedVariation;
97
}
67
}
98
68
99
RttHistory::RttHistory (const RttHistory& h)
100
  : seq (h.seq), count (h.count), time (h.time), retx (h.retx)
101
{
102
  NS_LOG_FUNCTION (this);
103
}
104
69
105
// Base class methods
70
// Base class methods
106
71
107
RttEstimator::RttEstimator ()
72
RttEstimator::RttEstimator ()
108
  : m_next (1), m_history (),
73
  : m_nSamples (0)
109
    m_nSamples (0),
110
    m_multiplier (1)
111
{ 
74
{ 
112
  NS_LOG_FUNCTION (this);
75
  NS_LOG_FUNCTION (this);
113
  //note next=1 everywhere since first segment will have sequence 1
114
  
76
  
115
  // We need attributes initialized here, not later, so use the 
77
  // We need attributes initialized here, not later, so use the 
116
  // ConstructSelf() technique documented in the manual
78
  // ConstructSelf() technique documented in the manual
117
  ObjectBase::ConstructSelf (AttributeConstructionList ());
79
  ObjectBase::ConstructSelf (AttributeConstructionList ());
118
  m_currentEstimatedRtt = m_initialEstimatedRtt;
80
  m_estimatedRtt = m_initialEstimatedRtt;
119
  NS_LOG_DEBUG ("Initialize m_currentEstimatedRtt to " << m_currentEstimatedRtt.GetSeconds () << " sec.");
81
  m_estimatedVariation = Time (0);
82
  NS_LOG_DEBUG ("Initialize m_estimatedRtt to " << m_estimatedRtt.GetSeconds () << " sec.");
120
}
83
}
121
84
122
RttEstimator::RttEstimator (const RttEstimator& c)
85
RttEstimator::RttEstimator (const RttEstimator& c)
123
  : Object (c), m_next (c.m_next), m_history (c.m_history), 
86
  : Object (c),
124
    m_maxMultiplier (c.m_maxMultiplier), 
125
    m_initialEstimatedRtt (c.m_initialEstimatedRtt),
87
    m_initialEstimatedRtt (c.m_initialEstimatedRtt),
126
    m_currentEstimatedRtt (c.m_currentEstimatedRtt), m_minRto (c.m_minRto),
88
    m_estimatedRtt (c.m_estimatedRtt),
127
    m_nSamples (c.m_nSamples), m_multiplier (c.m_multiplier)
89
    m_estimatedVariation (c.m_estimatedVariation),
90
    m_nSamples (c.m_nSamples)
128
{
91
{
129
  NS_LOG_FUNCTION (this);
92
  NS_LOG_FUNCTION (this);
130
}
93
}
 Lines 140-231    Link Here 
140
  return GetTypeId ();
103
  return GetTypeId ();
141
}
104
}
142
105
143
void RttEstimator::SentSeq (SequenceNumber32 seq, uint32_t size)
144
{ 
145
  NS_LOG_FUNCTION (this << seq << size);
146
  // Note that a particular sequence has been sent
147
  if (seq == m_next)
148
    { // This is the next expected one, just log at end
149
      m_history.push_back (RttHistory (seq, size, Simulator::Now () ));
150
      m_next = seq + SequenceNumber32 (size); // Update next expected
151
    }
152
  else
153
    { // This is a retransmit, find in list and mark as re-tx
154
      for (RttHistory_t::iterator i = m_history.begin (); i != m_history.end (); ++i)
155
        {
156
          if ((seq >= i->seq) && (seq < (i->seq + SequenceNumber32 (i->count))))
157
            { // Found it
158
              i->retx = true;
159
              // One final test..be sure this re-tx does not extend "next"
160
              if ((seq + SequenceNumber32 (size)) > m_next)
161
                {
162
                  m_next = seq + SequenceNumber32 (size);
163
                  i->count = ((seq + SequenceNumber32 (size)) - i->seq); // And update count in hist
164
                }
165
              break;
166
            }
167
        }
168
    }
169
}
170
171
Time RttEstimator::EstimateRttFromSeq (SequenceNumber32 ackSeq)
172
{ 
173
  NS_LOG_FUNCTION (this << ackSeq);
174
  // An ack has been received, calculate rtt and log this measurement
175
  // Note we use a linear search (O(n)) for this since for the common
176
  // case the ack'ed packet will be at the head of the list
177
  Time m = Seconds (0.0);
178
  if (m_history.size () == 0) return (m);    // No pending history, just exit
179
  RttHistory& h = m_history.front ();
180
  if (!h.retx && ackSeq >= (h.seq + SequenceNumber32 (h.count)))
181
    { // Ok to use this sample
182
      m = Simulator::Now () - h.time; // Elapsed time
183
      Measurement (m);                // Log the measurement
184
      ResetMultiplier ();             // Reset multiplier on valid measurement
185
    }
186
  // Now delete all ack history with seq <= ack
187
  while(m_history.size () > 0)
188
    {
189
      RttHistory& h = m_history.front ();
190
      if ((h.seq + SequenceNumber32 (h.count)) > ackSeq) break;               // Done removing
191
      m_history.pop_front (); // Remove
192
    }
193
  return m;
194
}
195
196
void RttEstimator::ClearSent ()
197
{ 
198
  NS_LOG_FUNCTION (this);
199
  // Clear all history entries
200
  m_next = 1;
201
  m_history.clear ();
202
}
203
204
void RttEstimator::IncreaseMultiplier ()
205
{
206
  NS_LOG_FUNCTION (this);
207
  m_multiplier = (m_multiplier*2 < m_maxMultiplier) ? m_multiplier*2 : m_maxMultiplier;
208
  NS_LOG_DEBUG ("Multiplier increased to " << m_multiplier);
209
}
210
211
void RttEstimator::ResetMultiplier ()
212
{
213
  NS_LOG_FUNCTION (this);
214
  m_multiplier = 1;
215
}
216
217
void RttEstimator::Reset ()
106
void RttEstimator::Reset ()
218
{ 
107
{ 
219
  NS_LOG_FUNCTION (this);
108
  NS_LOG_FUNCTION (this);
220
  // Reset to initial state
109
  // Reset to initial state
221
  m_next = 1;
110
  m_estimatedRtt = m_initialEstimatedRtt;
222
  m_currentEstimatedRtt = m_initialEstimatedRtt;
111
  m_estimatedVariation = Time (0);
223
  m_history.clear ();         // Remove all info from the history
224
  m_nSamples = 0;
112
  m_nSamples = 0;
225
  ResetMultiplier ();
226
}
113
}
227
114
228
115
uint32_t 
116
RttEstimator::GetNSamples (void) const
117
{
118
  return m_nSamples;
119
}
229
120
230
//-----------------------------------------------------------------------------
121
//-----------------------------------------------------------------------------
231
//-----------------------------------------------------------------------------
122
//-----------------------------------------------------------------------------
 Lines 239-261    Link Here 
239
  static TypeId tid = TypeId ("ns3::RttMeanDeviation")
130
  static TypeId tid = TypeId ("ns3::RttMeanDeviation")
240
    .SetParent<RttEstimator> ()
131
    .SetParent<RttEstimator> ()
241
    .AddConstructor<RttMeanDeviation> ()
132
    .AddConstructor<RttMeanDeviation> ()
242
    .AddAttribute ("Gain",
133
    .AddAttribute ("Alpha",
243
                   "Gain used in estimating the RTT, must be 0 < Gain < 1",
134
                   "Gain used in estimating the RTT, must be 0 <= alpha <= 1",
244
                   DoubleValue (0.1),
135
                   DoubleValue (0.125),
245
                   MakeDoubleAccessor (&RttMeanDeviation::m_gain),
136
                   MakeDoubleAccessor (&RttMeanDeviation::m_alpha),
246
                   MakeDoubleChecker<double> ())
137
                   MakeDoubleChecker<double> (0, 1))
138
    .AddAttribute ("Beta",
139
                   "Gain used in estimating the RTT variation, must be 0 <= beta <= 1",
140
                   DoubleValue (0.25),
141
                   MakeDoubleAccessor (&RttMeanDeviation::m_beta),
142
                   MakeDoubleChecker<double> (0, 1))
247
  ;
143
  ;
248
  return tid;
144
  return tid;
249
}
145
}
250
146
251
RttMeanDeviation::RttMeanDeviation() :
147
RttMeanDeviation::RttMeanDeviation()
252
  m_variance (0) 
148
{
253
{ 
254
  NS_LOG_FUNCTION (this);
149
  NS_LOG_FUNCTION (this);
255
}
150
}
256
151
257
RttMeanDeviation::RttMeanDeviation (const RttMeanDeviation& c)
152
RttMeanDeviation::RttMeanDeviation (const RttMeanDeviation& c)
258
  : RttEstimator (c), m_gain (c.m_gain), m_variance (c.m_variance)
153
  : RttEstimator (c), m_alpha (c.m_alpha), m_beta (c.m_beta)
259
{
154
{
260
  NS_LOG_FUNCTION (this);
155
  NS_LOG_FUNCTION (this);
261
}
156
}
 Lines 266-327    Link Here 
266
  return GetTypeId ();
161
  return GetTypeId ();
267
}
162
}
268
163
269
void RttMeanDeviation::Measurement (Time m)
164
uint32_t
165
RttMeanDeviation::CheckForReciprocalPowerOfTwo (double val) const
166
{
167
  NS_LOG_FUNCTION (this << val);
168
  if (val < TOLERANCE)
169
    {
170
      return 0;
171
    }
172
  // supports 1/32, 1/16, 1/8, 1/4, 1/2
173
  if (abs (1/val - 8) < TOLERANCE)
174
    {
175
      return 3;
176
    }
177
  if (abs (1/val - 4) < TOLERANCE)
178
    {
179
      return 2;
180
    }
181
  if (abs (1/val - 32) < TOLERANCE)
182
    {
183
      return 5;
184
    }
185
  if (abs (1/val - 16) < TOLERANCE)
186
    {
187
      return 4;
188
    }
189
  if (abs (1/val - 2) < TOLERANCE)
190
    {
191
      return 1;
192
    }
193
  return 0;
194
}
195
196
void
197
RttMeanDeviation::FloatingPointUpdate (Time m)
198
{
199
  NS_LOG_FUNCTION (this << m);
200
201
  // EWMA formulas are implemented as suggested in
202
  // Jacobson/Karels paper appendix A.2
203
204
  // SRTT <- (1 - alpha) * SRTT + alpha *  R'
205
  Time err (m - m_estimatedRtt);
206
  double gErr = err.ToDouble (Time::S) * m_alpha;
207
  m_estimatedRtt += Time::FromDouble (gErr, Time::S);
208
209
  // RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R'|
210
  Time difference = Abs (err) - m_estimatedVariation;
211
  m_estimatedVariation += Time::FromDouble (difference.ToDouble (Time::S) * m_beta, Time::S);
212
213
  return;
214
}
215
216
void
217
RttMeanDeviation::IntegerUpdate (Time m, uint32_t rttShift, uint32_t variationShift)
218
{
219
  NS_LOG_FUNCTION (this << m << rttShift << variationShift);
220
  // Jacobson/Karels paper appendix A.2
221
  int64_t meas = m.GetInteger ();
222
  int64_t delta = meas - m_estimatedRtt.GetInteger ();
223
  int64_t srtt = (m_estimatedRtt.GetInteger () << rttShift) + delta;
224
  m_estimatedRtt = Time::From (srtt >> rttShift);
225
  if (delta < 0)
226
    {
227
      delta = -delta;
228
    }
229
  delta -= m_estimatedVariation.GetInteger ();
230
  int64_t rttvar = m_estimatedVariation.GetInteger () << variationShift;
231
  rttvar += delta;
232
  m_estimatedVariation = Time::From (rttvar >> variationShift);
233
  return;
234
}
235
236
void 
237
RttMeanDeviation::Measurement (Time m)
270
{
238
{
271
  NS_LOG_FUNCTION (this << m);
239
  NS_LOG_FUNCTION (this << m);
272
  if (m_nSamples)
240
  if (m_nSamples)
273
    { // Not first
241
    { 
274
      Time err (m - m_currentEstimatedRtt);
242
      // If both alpha and beta are reciprocal powers of two, updating can
275
      double gErr = err.ToDouble (Time::S) * m_gain;
243
      // be done with integer arithmetic according to Jacobson/Karels paper.
276
      m_currentEstimatedRtt += Time::FromDouble (gErr, Time::S);
244
      // If not, since class Time only supports integer multiplication,
277
      Time difference = Abs (err) - m_variance;
245
      // must convert Time to floating point and back again
278
      NS_LOG_DEBUG ("m_variance += " << Time::FromDouble (difference.ToDouble (Time::S) * m_gain, Time::S));
246
      uint32_t rttShift = CheckForReciprocalPowerOfTwo (m_alpha);
279
      m_variance += Time::FromDouble (difference.ToDouble (Time::S) * m_gain, Time::S);
247
      uint32_t variationShift = CheckForReciprocalPowerOfTwo (m_beta);
248
      if (rttShift && variationShift)
249
        {
250
          IntegerUpdate (m, rttShift, variationShift);
251
        }
252
      else
253
        {
254
          FloatingPointUpdate (m);
255
        }
280
    }
256
    }
281
  else
257
  else
282
    { // First sample
258
    { // First sample
283
      m_currentEstimatedRtt = m;             // Set estimate to current
259
      m_estimatedRtt = m;               // Set estimate to current
284
      //variance = sample / 2;               // And variance to current / 2
260
      m_estimatedVariation = m / 2;  // And variation to current / 2
285
      m_variance = m; // try this
261
      NS_LOG_DEBUG ("(first sample) m_estimatedVariation += " << m);
286
      NS_LOG_DEBUG ("(first sample) m_variance += " << m);
287
    }
262
    }
288
  m_nSamples++;
263
  m_nSamples++;
289
}
264
}
290
265
291
Time RttMeanDeviation::RetransmitTimeout ()
266
Ptr<RttEstimator> 
292
{
267
RttMeanDeviation::Copy () const
293
  NS_LOG_FUNCTION (this);
294
  NS_LOG_DEBUG ("RetransmitTimeout:  var " << m_variance.GetSeconds () << " est " << m_currentEstimatedRtt.GetSeconds () << " multiplier " << m_multiplier);
295
  // RTO = srtt + 4* rttvar
296
  int64_t temp = m_currentEstimatedRtt.ToInteger (Time::MS) + 4 * m_variance.ToInteger (Time::MS);
297
  if (temp < m_minRto.ToInteger (Time::MS))
298
    {
299
      temp = m_minRto.ToInteger (Time::MS);
300
    } 
301
  temp = temp * m_multiplier; // Apply backoff
302
  Time retval = Time::FromInteger (temp, Time::MS);
303
  NS_LOG_DEBUG ("RetransmitTimeout:  return " << retval.GetSeconds ());
304
  return (retval);  
305
}
306
307
Ptr<RttEstimator> RttMeanDeviation::Copy () const
308
{
268
{
309
  NS_LOG_FUNCTION (this);
269
  NS_LOG_FUNCTION (this);
310
  return CopyObject<RttMeanDeviation> (this);
270
  return CopyObject<RttMeanDeviation> (this);
311
}
271
}
312
272
313
void RttMeanDeviation::Reset ()
273
void 
274
RttMeanDeviation::Reset ()
314
{ 
275
{ 
315
  NS_LOG_FUNCTION (this);
276
  NS_LOG_FUNCTION (this);
316
  // Reset to initial state
317
  m_variance = Seconds (0);
318
  RttEstimator::Reset ();
277
  RttEstimator::Reset ();
319
}
278
}
320
void RttMeanDeviation::Gain (double g)
321
{
322
  NS_LOG_FUNCTION (this);
323
  NS_ASSERT_MSG( (g > 0) && (g < 1), "RttMeanDeviation: Gain must be less than 1 and greater than 0" );
324
  m_gain = g;
325
}
326
279
327
} //namespace ns3
280
} //namespace ns3
(-)a/src/internet/model/rtt-estimator.h (-100 / +55 lines)
 Lines 25-32    Link Here 
25
#ifndef RTT_ESTIMATOR_H
25
#ifndef RTT_ESTIMATOR_H
26
#define RTT_ESTIMATOR_H
26
#define RTT_ESTIMATOR_H
27
27
28
#include <deque>
29
#include "ns3/sequence-number.h"
30
#include "ns3/nstime.h"
28
#include "ns3/nstime.h"
31
#include "ns3/object.h"
29
#include "ns3/object.h"
32
30
 Lines 35-70    Link Here 
35
/**
33
/**
36
 * \ingroup tcp
34
 * \ingroup tcp
37
 *
35
 *
38
 * \brief Helper class to store RTT measurements
36
 * \brief Base class for all RTT Estimators
39
 */
40
class RttHistory {
41
public:
42
  /**
43
   * \brief Constructor - builds an RttHistory with the given parameters
44
   * \param s First sequence number in packet sent
45
   * \param c Number of bytes sent
46
   * \param t Time this one was sent
47
   */
48
  RttHistory (SequenceNumber32 s, uint32_t c, Time t);
49
  /**
50
   * \brief Copy constructor
51
   * \param h the object to copy
52
   */
53
  RttHistory (const RttHistory& h); // Copy constructor
54
public:
55
  SequenceNumber32  seq;  //!< First sequence number in packet sent
56
  uint32_t        count;  //!< Number of bytes sent
57
  Time            time;   //!< Time this one was sent
58
  bool            retx;   //!< True if this has been retransmitted
59
};
60
61
/// Container for RttHistory objects
62
typedef std::deque<RttHistory> RttHistory_t;
63
64
/**
65
 * \ingroup tcp
66
 *
37
 *
67
 * \brief Base class for all RTT Estimators
38
 * The RTT Estimator class computes an estimate of the round trip time
39
 * observed in a series of Time measurements.  The estimate is provided in
40
 * the form of an estimate and a sample variation.  Subclasses can implement
41
 * different algorithms to provide values for the estimate and variation.  
68
 */
42
 */
69
class RttEstimator : public Object {
43
class RttEstimator : public Object {
70
public:
44
public:
 Lines 86-177    Link Here 
86
  virtual TypeId GetInstanceTypeId (void) const;
60
  virtual TypeId GetInstanceTypeId (void) const;
87
61
88
  /**
62
  /**
89
   * \brief Note that a particular sequence has been sent
90
   * \param seq the packet sequence number.
91
   * \param size the packet size.
92
   */
93
  virtual void SentSeq (SequenceNumber32 seq, uint32_t size);
94
95
  /**
96
   * \brief Note that a particular ack sequence has been received
97
   * \param ackSeq the ack sequence number.
98
   * \return The measured RTT for this ack.
99
   */
100
  virtual Time EstimateRttFromSeq (SequenceNumber32 ackSeq);
101
102
  /**
103
   * \brief Clear all history entries
104
   */
105
  virtual void ClearSent ();
106
107
  /**
108
   * \brief Add a new measurement to the estimator. Pure virtual function.
63
   * \brief Add a new measurement to the estimator. Pure virtual function.
109
   * \param t the new RTT measure.
64
   * \param t the new RTT measure.
110
   */
65
   */
111
  virtual void  Measurement (Time t) = 0;
66
  virtual void  Measurement (Time t) = 0;
112
67
113
  /**
68
  /**
114
   * \brief Returns the estimated RTO. Pure virtual function.
69
   * \brief Copy object (including current internal state)
115
   * \return the estimated RTO.
116
   */
117
  virtual Time RetransmitTimeout () = 0;
118
119
  /**
120
   * \brief Copy object
121
   * \returns a copy of itself
70
   * \returns a copy of itself
122
   */
71
   */
123
  virtual Ptr<RttEstimator> Copy () const = 0;
72
  virtual Ptr<RttEstimator> Copy () const = 0;
124
73
125
  /**
74
  /**
126
   * \brief Increase the estimation multiplier up to MaxMultiplier.
127
   */
128
  virtual void IncreaseMultiplier ();
129
130
  /**
131
   * \brief Resets the estimation multiplier to 1.
132
   */
133
  virtual void ResetMultiplier ();
134
135
  /**
136
   * \brief Resets the estimation to its initial state.
75
   * \brief Resets the estimation to its initial state.
137
   */
76
   */
138
  virtual void Reset ();
77
  virtual void Reset ();
139
78
140
  /**
79
  /**
141
   * \brief Sets the Minimum RTO.
80
   * \brief gets the RTT estimate.
142
   * \param minRto The minimum RTO returned by the estimator.
81
   * \return The RTT estimate.
143
   */
82
   */
144
  void SetMinRto (Time minRto);
83
  Time GetEstimate (void) const;
145
84
146
  /**
85
  /**
147
   * \brief Get the Minimum RTO.
86
   * Note that this is not a formal statistical variance; it has the
148
   * \return The minimum RTO returned by the estimator.
87
   * the same units as the estimate.  Mean deviation or standard deviation 
88
   * are example quantities that could be provided here.
89
   *
90
   * \brief gets the RTT estimate variation.
91
   * \return The RTT estimate variation.
149
   */
92
   */
150
  Time GetMinRto (void) const;
93
  Time GetVariation (void) const;
151
94
152
  /**
95
  /**
153
   * \brief Sets the current RTT estimate (forcefully).
96
   * \brief gets the number of samples used in the estimates
154
   * \param estimate The current RTT estimate.
97
   * \return the number of samples used in the estimates
155
   */
98
   */
156
  void SetCurrentEstimate (Time estimate);
99
  uint32_t GetNSamples (void) const;
157
158
  /**
159
   * \brief gets the current RTT estimate.
160
   * \return The current RTT estimate.
161
   */
162
  Time GetCurrentEstimate (void) const;
163
100
164
private:
101
private:
165
  SequenceNumber32 m_next;    //!< Next expected sequence to be sent
166
  RttHistory_t m_history;     //!< List of sent packet
167
  uint16_t m_maxMultiplier;   //!< Maximum RTO Multiplier
168
  Time m_initialEstimatedRtt; //!< Initial RTT estimation
102
  Time m_initialEstimatedRtt; //!< Initial RTT estimation
169
103
170
protected:
104
protected:
171
  Time         m_currentEstimatedRtt;     //!< Current estimate
105
  Time         m_estimatedRtt;            //!< Current estimate
172
  Time         m_minRto;                  //!< minimum value of the timeout
106
  Time         m_estimatedVariation;   //!< Current estimate variation
173
  uint32_t     m_nSamples;                //!< Number of samples
107
  uint32_t     m_nSamples;                //!< Number of samples
174
  uint16_t     m_multiplier;              //!< RTO Multiplier
175
};
108
};
176
109
177
/**
110
/**
 Lines 183-188    Link Here 
183
 * by Van Jacobson and Michael J. Karels, in
116
 * by Van Jacobson and Michael J. Karels, in
184
 * "Congestion Avoidance and Control", SIGCOMM 88, Appendix A
117
 * "Congestion Avoidance and Control", SIGCOMM 88, Appendix A
185
 *
118
 *
119
 * The default values for the gain (alpha and beta) are set as documented
120
 * in RFC 6298.
121
 *
186
 */
122
 */
187
class RttMeanDeviation : public RttEstimator {
123
class RttMeanDeviation : public RttEstimator {
188
public:
124
public:
 Lines 208-219    Link Here 
208
   */
144
   */
209
  void Measurement (Time measure);
145
  void Measurement (Time measure);
210
146
211
  /**
212
   * \brief Returns the estimated RTO.
213
   * \return the estimated RTO.
214
   */
215
  Time RetransmitTimeout ();
216
217
  Ptr<RttEstimator> Copy () const;
147
  Ptr<RttEstimator> Copy () const;
218
148
219
  /**
149
  /**
 Lines 221-236    Link Here 
221
   */
151
   */
222
  void Reset ();
152
  void Reset ();
223
153
154
private:
155
  /** 
156
   * Utility function to check for possible conversion
157
   * of a double value (0 < value < 1) to a reciprocal power of two
158
   *
159
   * Values of 1/32, 1/16, 1/8, 1/4, and 1/2 (i.e., within the possible
160
   * range of experimentation for this estimator) are supported.
161
   * 
162
   * \param val value to check 
163
   * \return log base 2 (1/val) if reciprocal power of 2, or zero if not
164
   */
165
  uint32_t CheckForReciprocalPowerOfTwo (double val) const;
224
  /**
166
  /**
225
   * \brief Sets the estimator Gain.
167
   * Method to update the rtt and variation estimates using integer
226
   * \param g the gain, where 0 < g < 1.
168
   * arithmetic, used when the values of Alpha and Beta support the
169
   * integer conversion.
170
   *
171
   * \param m time measurement
172
   * \param rttShift value corresponding to log base 2 (1/alpha)
173
   * \param variationShift value corresponding to log base 2 (1/beta)
227
   */
174
   */
228
  void Gain (double g);
175
  void IntegerUpdate (Time m, uint32_t rttShift, uint32_t variationShift);
176
  /**
177
   * Method to update the rtt and variation estimates using floating
178
   * point arithmetic, used when the values of Alpha and Beta are not
179
   * both a reciprocal power of two.
180
   *
181
   * \param m time measurement
182
   */
183
  void FloatingPointUpdate (Time m);
184
  double       m_alpha;       //!< Filter gain for average
185
  double       m_beta;        //!< Filter gain for variation
229
186
230
private:
231
  double       m_gain;       //!< Filter gain
232
  Time         m_variance;   //!< Current variance
233
};
187
};
188
234
} // namespace ns3
189
} // namespace ns3
235
190
236
#endif /* RTT_ESTIMATOR_H */
191
#endif /* RTT_ESTIMATOR_H */
(-)a/src/internet/model/tcp-newreno.cc (-1 lines)
 Lines 213-219    Link Here 
213
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack
213
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack
214
  NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd <<
214
  NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd <<
215
               ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence);
215
               ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence);
216
  m_rtt->IncreaseMultiplier ();             // Double the next RTO
217
  DoRetransmit ();                          // Retransmit the packet
216
  DoRetransmit ();                          // Retransmit the packet
218
}
217
}
219
218
(-)a/src/internet/model/tcp-reno.cc (-1 lines)
 Lines 188-194    Link Here 
188
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack
188
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack
189
  NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd <<
189
  NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd <<
190
               ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence);
190
               ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence);
191
  m_rtt->IncreaseMultiplier ();             // Double the next RTO
192
  DoRetransmit ();                          // Retransmit the packet
191
  DoRetransmit ();                          // Retransmit the packet
193
}
192
}
194
193
(-)a/src/internet/model/tcp-socket-base.cc (-32 / +133 lines)
 Lines 94-99    Link Here 
94
                   BooleanValue (true),
94
                   BooleanValue (true),
95
                   MakeBooleanAccessor (&TcpSocketBase::m_timestampEnabled),
95
                   MakeBooleanAccessor (&TcpSocketBase::m_timestampEnabled),
96
                   MakeBooleanChecker ())
96
                   MakeBooleanChecker ())
97
    .AddAttribute ("MinRto",
98
                   "Minimum retransmit timeout value",
99
                   TimeValue (Seconds (0.2)), // RFC2988 says min RTO=1 sec, but Linux uses 200ms. See http://www.postel.org/pipermail/end2end-interest/2004-November/004402.html
100
                   MakeTimeAccessor (&TcpSocketBase::SetMinRto,
101
                                     &TcpSocketBase::GetMinRto),
102
                                     MakeTimeChecker ())
103
    .AddAttribute ("ClockGranularity",
104
                   "Clock Granularity used in RTO calculations",
105
                   TimeValue (MilliSeconds (1)), // RFC6298 suggest to use fine clock granularity
106
                   MakeTimeAccessor (&TcpSocketBase::SetClockGranularity,
107
                                     &TcpSocketBase::GetClockGranularity),
108
                                     MakeTimeChecker ())
97
    .AddTraceSource ("RTO",
109
    .AddTraceSource ("RTO",
98
                     "Retransmission timeout",
110
                     "Retransmission timeout",
99
                     MakeTraceSourceAccessor (&TcpSocketBase::m_rto),
111
                     MakeTraceSourceAccessor (&TcpSocketBase::m_rto),
 Lines 148-155    Link Here 
148
    m_sndScaleFactor (0),
160
    m_sndScaleFactor (0),
149
    m_rcvScaleFactor (0),
161
    m_rcvScaleFactor (0),
150
    m_timestampEnabled (true),
162
    m_timestampEnabled (true),
151
    m_timestampToEcho (0),
163
    m_timestampToEcho (0)
152
    m_lastEchoedTime (0)
153
164
154
{
165
{
155
  NS_LOG_FUNCTION (this);
166
  NS_LOG_FUNCTION (this);
 Lines 190-197    Link Here 
190
    m_sndScaleFactor (sock.m_sndScaleFactor),
201
    m_sndScaleFactor (sock.m_sndScaleFactor),
191
    m_rcvScaleFactor (sock.m_rcvScaleFactor),
202
    m_rcvScaleFactor (sock.m_rcvScaleFactor),
192
    m_timestampEnabled (sock.m_timestampEnabled),
203
    m_timestampEnabled (sock.m_timestampEnabled),
193
    m_timestampToEcho (sock.m_timestampToEcho),
204
    m_timestampToEcho (sock.m_timestampToEcho)
194
    m_lastEchoedTime (sock.m_lastEchoedTime)
195
205
196
{
206
{
197
  NS_LOG_FUNCTION (this);
207
  NS_LOG_FUNCTION (this);
 Lines 1568-1575    Link Here 
1568
  if (m_state == LAST_ACK)
1578
  if (m_state == LAST_ACK)
1569
    {
1579
    {
1570
      NS_LOG_LOGIC ("TcpSocketBase " << this << " scheduling LATO1");
1580
      NS_LOG_LOGIC ("TcpSocketBase " << this << " scheduling LATO1");
1571
      m_lastAckEvent = Simulator::Schedule (m_rtt->RetransmitTimeout (),
1581
      Time lastRto = m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4);
1572
                                            &TcpSocketBase::LastAckTimeout, this);
1582
      m_lastAckEvent = Simulator::Schedule (lastRto, &TcpSocketBase::LastAckTimeout, this);
1573
    }
1583
    }
1574
}
1584
}
1575
1585
 Lines 1687-1693    Link Here 
1687
    }
1697
    }
1688
  AddOptions (header);
1698
  AddOptions (header);
1689
  header.SetWindowSize (AdvertisedWindowSize ());
1699
  header.SetWindowSize (AdvertisedWindowSize ());
1690
  m_rto = m_rtt->RetransmitTimeout ();
1700
1701
  // RFC 6298, clause 2.4
1702
  m_rto = Max (m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4), Time::FromDouble (1,  Time::S));
1703
1691
  bool hasSyn = flags & TcpHeader::SYN;
1704
  bool hasSyn = flags & TcpHeader::SYN;
1692
  bool hasFin = flags & TcpHeader::FIN;
1705
  bool hasFin = flags & TcpHeader::FIN;
1693
  bool isAck = flags == TcpHeader::ACK;
1706
  bool isAck = flags == TcpHeader::ACK;
 Lines 1696-1701    Link Here 
1696
      if (m_cnCount == 0)
1709
      if (m_cnCount == 0)
1697
        { // No more connection retries, give up
1710
        { // No more connection retries, give up
1698
          NS_LOG_LOGIC ("Connection failed.");
1711
          NS_LOG_LOGIC ("Connection failed.");
1712
          m_rtt->Reset (); //According to recommendation -> RFC 6298
1699
          CloseAndNotify ();
1713
          CloseAndNotify ();
1700
          return;
1714
          return;
1701
        }
1715
        }
 Lines 1891-1896    Link Here 
1891
{
1905
{
1892
  NS_LOG_FUNCTION (this << seq << maxSize << withAck);
1906
  NS_LOG_FUNCTION (this << seq << maxSize << withAck);
1893
1907
1908
  bool isRetransmission = false;
1909
  if ( seq == m_txBuffer.HeadSequence () )
1910
    {
1911
      isRetransmission = true;
1912
    }
1913
1894
  Ptr<Packet> p = m_txBuffer.CopyFromSequence (maxSize, seq);
1914
  Ptr<Packet> p = m_txBuffer.CopyFromSequence (maxSize, seq);
1895
  uint32_t sz = p->GetSize (); // Size of packet
1915
  uint32_t sz = p->GetSize (); // Size of packet
1896
  uint8_t flags = withAck ? TcpHeader::ACK : 0;
1916
  uint8_t flags = withAck ? TcpHeader::ACK : 0;
 Lines 1960-1968    Link Here 
1960
    }
1980
    }
1961
  header.SetWindowSize (AdvertisedWindowSize ());
1981
  header.SetWindowSize (AdvertisedWindowSize ());
1962
  AddOptions (header);
1982
  AddOptions (header);
1983
1963
  if (m_retxEvent.IsExpired () )
1984
  if (m_retxEvent.IsExpired () )
1964
    { // Schedule retransmit
1985
    {
1965
      m_rto = m_rtt->RetransmitTimeout ();
1986
      // RFC 6298, clause 2.5
1987
      Time doubledRto = m_rto + m_rto;
1988
      m_rto = Min (doubledRto, Time::FromDouble (60,  Time::S));
1989
1990
      // Schedules retransmit
1991
1966
      NS_LOG_LOGIC (this << " SendDataPacket Schedule ReTxTimeout at time " <<
1992
      NS_LOG_LOGIC (this << " SendDataPacket Schedule ReTxTimeout at time " <<
1967
                    Simulator::Now ().GetSeconds () << " to expire at time " <<
1993
                    Simulator::Now ().GetSeconds () << " to expire at time " <<
1968
                    (Simulator::Now () + m_rto.Get ()).GetSeconds () );
1994
                    (Simulator::Now () + m_rto.Get ()).GetSeconds () );
 Lines 1979-1985    Link Here 
1979
      m_tcp->SendPacket (p, header, m_endPoint6->GetLocalAddress (),
2005
      m_tcp->SendPacket (p, header, m_endPoint6->GetLocalAddress (),
1980
                         m_endPoint6->GetPeerAddress (), m_boundnetdevice);
2006
                         m_endPoint6->GetPeerAddress (), m_boundnetdevice);
1981
    }
2007
    }
1982
  m_rtt->SentSeq (seq, sz);       // notify the RTT
2008
2009
  // update the history of sequence numbers used to calculate the RTT
2010
  if (isRetransmission == false)
2011
    { // This is the next expected one, just log at end
2012
      m_history.push_back (RttHistory (seq, sz, Simulator::Now () ));
2013
    }
2014
  else
2015
    { // This is a retransmit, find in list and mark as re-tx
2016
      for (RttHistory_t::iterator i = m_history.begin (); i != m_history.end (); ++i)
2017
        {
2018
          if ((seq >= i->seq) && (seq < (i->seq + SequenceNumber32 (i->count))))
2019
            { // Found it
2020
              i->retx = true;
2021
              i->count = ((seq + SequenceNumber32 (sz)) - i->seq); // And update count in hist
2022
              break;
2023
            }
2024
        }
2025
    }
2026
1983
  // Notify the application of the data being sent unless this is a retransmit
2027
  // Notify the application of the data being sent unless this is a retransmit
1984
  if (seq == m_nextTxSequence)
2028
  if (seq == m_nextTxSequence)
1985
    {
2029
    {
 Lines 2155-2181    Link Here 
2155
void
2199
void
2156
TcpSocketBase::EstimateRtt (const TcpHeader& tcpHeader)
2200
TcpSocketBase::EstimateRtt (const TcpHeader& tcpHeader)
2157
{
2201
{
2158
  Time nextRtt;
2202
  SequenceNumber32 ackSeq = tcpHeader.GetAckNumber();
2203
  Time m = Time (0.0);
2159
2204
2160
  if (m_timestampEnabled)
2205
  // An ack has been received, calculate rtt and log this measurement
2206
  // Note we use a linear search (O(n)) for this since for the common
2207
  // case the ack'ed packet will be at the head of the list
2208
  if (!m_history.empty ())
2161
    {
2209
    {
2162
      nextRtt = TcpOptionTS::ElapsedTimeFromTsValue (m_lastEchoedTime);
2210
      RttHistory& h = m_history.front ();
2163
    }
2211
      if (!h.retx && ackSeq >= (h.seq + SequenceNumber32 (h.count)))
2164
  else
2212
        { // Ok to use this sample
2165
    {
2213
          if (m_timestampEnabled && tcpHeader.HasOption (TcpOption::TS))
2166
      // Use m_rtt for the estimation. Note, RTT of duplicated acknowledgement
2214
            {
2167
      // (which should be ignored) is handled by m_rtt.
2215
              Ptr<TcpOptionTS> ts;
2168
      nextRtt =  m_rtt->EstimateRttFromSeq (tcpHeader.GetAckNumber () );
2216
              ts = DynamicCast<TcpOptionTS> (tcpHeader.GetOption (TcpOption::TS));
2217
              m = TcpOptionTS::ElapsedTimeFromTsValue (ts->GetEcho ());
2218
            }
2219
          else
2220
            {
2221
              m = Simulator::Now () - h.time; // Elapsed time
2222
            }
2223
        }
2169
    }
2224
    }
2170
2225
2171
  //nextRtt will be zero for dup acks.  Don't want to update lastRtt in that case
2226
  // Now delete all ack history with seq <= ack
2172
  //but still needed to do list clearing that is done in EstimateRttFromSeq.
2227
  while(!m_history.empty ())
2173
  if(nextRtt != Time (0))
2228
    {
2174
  {
2229
      RttHistory& h = m_history.front ();
2175
    m_lastRtt = nextRtt;
2230
      if ((h.seq + SequenceNumber32 (h.count)) > ackSeq) break;               // Done removing
2176
    NS_LOG_FUNCTION(this << m_lastRtt);
2231
      m_history.pop_front (); // Remove
2177
  }
2232
    }
2178
  
2233
2234
  if (!m.IsZero ())
2235
    {
2236
      m_rtt->Measurement (m);                // Log the measurement
2237
      // RFC 6298, clause 2.4
2238
      m_rto = Max (m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4), Time::FromDouble (1,  Time::S));
2239
      m_lastRtt = m_rtt->GetEstimate ();
2240
      NS_LOG_FUNCTION(this << m_lastRtt);
2241
    }
2179
}
2242
}
2180
2243
2181
// Called by the ReceivedAck() when new ACK received and by ProcessSynRcvd()
2244
// Called by the ReceivedAck() when new ACK received and by ProcessSynRcvd()
 Lines 2191-2198    Link Here 
2191
      NS_LOG_LOGIC (this << " Cancelled ReTxTimeout event which was set to expire at " <<
2254
      NS_LOG_LOGIC (this << " Cancelled ReTxTimeout event which was set to expire at " <<
2192
                    (Simulator::Now () + Simulator::GetDelayLeft (m_retxEvent)).GetSeconds ());
2255
                    (Simulator::Now () + Simulator::GetDelayLeft (m_retxEvent)).GetSeconds ());
2193
      m_retxEvent.Cancel ();
2256
      m_retxEvent.Cancel ();
2194
      // On recieving a "New" ack we restart retransmission timer .. RFC 2988
2257
      // On receiving a "New" ack we restart retransmission timer .. RFC 6298
2195
      m_rto = m_rtt->RetransmitTimeout ();
2258
      // RFC 6298, clause 2.4
2259
      m_rto = Max (m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4), Time::FromDouble (1,  Time::S));
2260
2196
      NS_LOG_LOGIC (this << " Schedule ReTxTimeout at time " <<
2261
      NS_LOG_LOGIC (this << " Schedule ReTxTimeout at time " <<
2197
                    Simulator::Now ().GetSeconds () << " to expire at time " <<
2262
                    Simulator::Now ().GetSeconds () << " to expire at time " <<
2198
                    (Simulator::Now () + m_rto.Get ()).GetSeconds ());
2263
                    (Simulator::Now () + m_rto.Get ()).GetSeconds ());
 Lines 2320-2326    Link Here 
2320
TcpSocketBase::Retransmit ()
2385
TcpSocketBase::Retransmit ()
2321
{
2386
{
2322
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Start from highest Ack
2387
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Start from highest Ack
2323
  m_rtt->IncreaseMultiplier (); // Double the timeout value for next retx timer
2324
  m_dupAckCount = 0;
2388
  m_dupAckCount = 0;
2325
  DoRetransmit (); // Retransmit the packet
2389
  DoRetransmit (); // Retransmit the packet
2326
}
2390
}
 Lines 2526-2531    Link Here 
2526
    }
2590
    }
2527
2591
2528
  m_timestampEnabled = false;
2592
  m_timestampEnabled = false;
2593
2529
  if (header.HasOption (TcpOption::TS))
2594
  if (header.HasOption (TcpOption::TS))
2530
    {
2595
    {
2531
      m_timestampEnabled = true;
2596
      m_timestampEnabled = true;
 Lines 2622-2631    Link Here 
2622
2687
2623
  Ptr<const TcpOptionTS> ts = DynamicCast<const TcpOptionTS> (option);
2688
  Ptr<const TcpOptionTS> ts = DynamicCast<const TcpOptionTS> (option);
2624
  m_timestampToEcho = ts->GetTimestamp ();
2689
  m_timestampToEcho = ts->GetTimestamp ();
2625
  m_lastEchoedTime = ts->GetEcho ();
2626
2690
2627
  NS_LOG_INFO (m_node->GetId () << " Got timestamp=" <<
2691
  NS_LOG_INFO (m_node->GetId () << " Got timestamp=" <<
2628
               m_timestampToEcho << " and Echo="     << m_lastEchoedTime);
2692
               m_timestampToEcho << " and Echo="     << ts->GetEcho ());
2629
}
2693
}
2630
2694
2631
void
2695
void
 Lines 2643-2646    Link Here 
2643
               option->GetTimestamp () << " echo=" << m_timestampToEcho);
2707
               option->GetTimestamp () << " echo=" << m_timestampToEcho);
2644
}
2708
}
2645
2709
2710
void
2711
TcpSocketBase::SetMinRto (Time minRto)
2712
{
2713
  NS_LOG_FUNCTION (this << minRto);
2714
  m_minRto = minRto;
2715
}
2716
2717
Time
2718
TcpSocketBase::GetMinRto (void) const
2719
{
2720
  return m_minRto;
2721
}
2722
2723
void
2724
TcpSocketBase::SetClockGranularity (Time clockGranularity)
2725
{
2726
  NS_LOG_FUNCTION (this << clockGranularity);
2727
  m_clockGranularity = clockGranularity;
2728
}
2729
2730
Time
2731
TcpSocketBase::GetClockGranularity (void) const
2732
{
2733
  return m_clockGranularity;
2734
}
2735
2736
//RttHistory methods
2737
RttHistory::RttHistory (SequenceNumber32 s, uint32_t c, Time t)
2738
  : seq (s), count (c), time (t), retx (false)
2739
{
2740
}
2741
2742
RttHistory::RttHistory (const RttHistory& h)
2743
  : seq (h.seq), count (h.count), time (h.time), retx (h.retx)
2744
{
2745
}
2746
2646
} // namespace ns3
2747
} // namespace ns3
(-)a/src/internet/model/tcp-socket-base.h (-1 / +57 lines)
 Lines 47-52    Link Here 
47
class TcpHeader;
47
class TcpHeader;
48
48
49
/**
49
/**
50
 * \ingroup tcp
51
 *
52
 * \brief Helper class to store RTT measurements
53
 */
54
class RttHistory {
55
public:
56
  /**
57
   * \brief Constructor - builds an RttHistory with the given parameters
58
   * \param s First sequence number in packet sent
59
   * \param c Number of bytes sent
60
   * \param t Time this one was sent
61
   */
62
  RttHistory (SequenceNumber32 s, uint32_t c, Time t);
63
  /**
64
   * \brief Copy constructor
65
   * \param h the object to copy
66
   */
67
  RttHistory (const RttHistory& h); // Copy constructor
68
public:
69
  SequenceNumber32  seq;  //!< First sequence number in packet sent
70
  uint32_t        count;  //!< Number of bytes sent
71
  Time            time;   //!< Time this one was sent
72
  bool            retx;   //!< True if this has been retransmitted
73
};
74
75
/// Container for RttHistory objects
76
typedef std::deque<RttHistory> RttHistory_t;
77
78
/**
50
 * \ingroup socket
79
 * \ingroup socket
51
 * \ingroup tcp
80
 * \ingroup tcp
52
 *
81
 *
 Lines 101-106    Link Here 
101
   */
130
   */
102
  virtual void SetRtt (Ptr<RttEstimator> rtt);
131
  virtual void SetRtt (Ptr<RttEstimator> rtt);
103
132
133
  /**
134
   * \brief Sets the Minimum RTO.
135
   * \param minRto The minimum RTO.
136
   */
137
  void SetMinRto (Time minRto);
138
139
  /**
140
   * \brief Get the Minimum RTO.
141
   * \return The minimum RTO.
142
   */
143
  Time GetMinRto (void) const;
144
145
  /**
146
   * \brief Sets the Clock Granularity (used in RTO calcs).
147
   * \param clockGranularity The Clock Granularity
148
   */
149
  void SetClockGranularity (Time clockGranularity);
150
151
  /**
152
   * \brief Get the Clock Granularity (used in RTO calcs).
153
   * \return The Clock Granularity.
154
   */
155
  Time GetClockGranularity (void) const;
156
157
104
  // Necessary implementations of null functions from ns3::Socket
158
  // Necessary implementations of null functions from ns3::Socket
105
  virtual enum SocketErrno GetErrno (void) const;    // returns m_errno
159
  virtual enum SocketErrno GetErrno (void) const;    // returns m_errno
106
  virtual enum SocketType GetSocketType (void) const; // returns socket type
160
  virtual enum SocketType GetSocketType (void) const; // returns socket type
 Lines 624-633    Link Here 
624
  uint32_t          m_cnCount;         //!< Count of remaining connection retries
678
  uint32_t          m_cnCount;         //!< Count of remaining connection retries
625
  uint32_t          m_cnRetries;       //!< Number of connection retries before giving up
679
  uint32_t          m_cnRetries;       //!< Number of connection retries before giving up
626
  TracedValue<Time> m_rto;             //!< Retransmit timeout
680
  TracedValue<Time> m_rto;             //!< Retransmit timeout
681
  Time              m_minRto;          //!< minimum value of the Retransmit timeout
682
  Time              m_clockGranularity; //!< Clock Granularity used in RTO calcs
627
  TracedValue<Time> m_lastRtt;         //!< Last RTT sample collected
683
  TracedValue<Time> m_lastRtt;         //!< Last RTT sample collected
628
  Time              m_delAckTimeout;   //!< Time to delay an ACK
684
  Time              m_delAckTimeout;   //!< Time to delay an ACK
629
  Time              m_persistTimeout;  //!< Time between sending 1-byte probes
685
  Time              m_persistTimeout;  //!< Time between sending 1-byte probes
630
  Time              m_cnTimeout;       //!< Timeout for connection retry
686
  Time              m_cnTimeout;       //!< Timeout for connection retry
687
  RttHistory_t      m_history;         //!< List of sent packet
631
688
632
  // Connections to other layers of TCP/IP
689
  // Connections to other layers of TCP/IP
633
  Ipv4EndPoint*       m_endPoint;   //!< the IPv4 endpoint
690
  Ipv4EndPoint*       m_endPoint;   //!< the IPv4 endpoint
 Lines 667-673    Link Here 
667
724
668
  bool     m_timestampEnabled;    //!< Timestamp option enabled
725
  bool     m_timestampEnabled;    //!< Timestamp option enabled
669
  uint32_t m_timestampToEcho;     //!< Timestamp to echo
726
  uint32_t m_timestampToEcho;     //!< Timestamp to echo
670
  uint32_t m_lastEchoedTime;      //!< Last echoed timestamp
671
};
727
};
672
728
673
} // namespace ns3
729
} // namespace ns3
(-)a/src/internet/model/tcp-tahoe.cc (-1 lines)
 Lines 166-172    Link Here 
166
  m_ssThresh = std::max (static_cast<unsigned> (m_cWnd / 2), m_segmentSize * 2);  // Half ssthresh
166
  m_ssThresh = std::max (static_cast<unsigned> (m_cWnd / 2), m_segmentSize * 2);  // Half ssthresh
167
  m_cWnd = m_segmentSize;                   // Set cwnd to 1 segSize (RFC2001, sec.2)
167
  m_cWnd = m_segmentSize;                   // Set cwnd to 1 segSize (RFC2001, sec.2)
168
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack
168
  m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack
169
  m_rtt->IncreaseMultiplier ();             // Double the next RTO
170
  DoRetransmit ();                          // Retransmit the packet
169
  DoRetransmit ();                          // Retransmit the packet
171
}
170
}
172
171
(-)a/src/internet/model/tcp-westwood.cc (-7 / +4 lines)
 Lines 307-329    Link Here 
307
  if (m_state == CLOSED || m_state == TIME_WAIT)
307
  if (m_state == CLOSED || m_state == TIME_WAIT)
308
    return;
308
    return;
309
  // If all data are received, just return
309
  // If all data are received, just return
310
  if (m_txBuffer.HeadSequence() >= m_nextTxSequence)
310
  if (m_txBuffer.HeadSequence () >= m_nextTxSequence)
311
    return;
311
    return;
312
312
313
  // Upon an RTO, adjust cwnd and ssthresh based on the estimated BW
313
  // Upon an RTO, adjust cwnd and ssthresh based on the estimated BW
314
  m_ssThresh = std::max (static_cast<double> (2 * m_segmentSize), m_currentBW.Get() * static_cast<double> (m_minRtt.GetSeconds()));
314
  m_ssThresh = std::max (static_cast<double> (2 * m_segmentSize), m_currentBW.Get () * static_cast<double> (m_minRtt.GetSeconds ()));
315
  m_cWnd = m_segmentSize;
315
  m_cWnd = m_segmentSize;
316
316
317
  // Restart from highest ACK
317
  // Restart from highest ACK
318
  m_nextTxSequence = m_txBuffer.HeadSequence();
318
  m_nextTxSequence = m_txBuffer.HeadSequence ();
319
  NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd <<
319
  NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd <<
320
      ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence);
320
      ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence);
321
321
322
  // Double the next RTO
323
  m_rtt->IncreaseMultiplier();
324
325
  // Retransmit the packet
322
  // Retransmit the packet
326
  DoRetransmit();
323
  DoRetransmit ();
327
}
324
}
328
325
329
void
326
void
(-)a/src/internet/test/rtt-test.cc (-51 / +111 lines)
 Lines 16-108    Link Here 
16
 */
16
 */
17
17
18
#include "ns3/test.h"
18
#include "ns3/test.h"
19
#include "ns3/core-module.h"
20
#include "ns3/internet-module.h"
21
#include "ns3/rtt-estimator.h"
19
#include "ns3/rtt-estimator.h"
20
#include "ns3/attribute.h"
21
#include "ns3/nstime.h"
22
#include "ns3/config.h"
22
#include "ns3/log.h"
23
#include "ns3/log.h"
24
#include "ns3/double.h"
23
25
24
using namespace ns3;
26
using namespace ns3;
25
27
26
NS_LOG_COMPONENT_DEFINE ("RttTestSuite");
28
NS_LOG_COMPONENT_DEFINE ("RttEstimatorTestSuite");
27
29
28
class RttTestCase : public TestCase
30
class RttEstimatorTestCase : public TestCase
29
{
31
{
30
public:
32
public:
31
  RttTestCase (double mean,
33
  RttEstimatorTestCase ();
32
               double variance,
33
               double gain);
34
34
35
private:
35
private:
36
  virtual void DoRun (void);
36
  virtual void DoRun (void);
37
  virtual void DoTeardown (void);
37
  virtual void DoTeardown (void);
38
38
39
  double m_mean;
39
  void CheckValues (Ptr<RttEstimator> rtt, Time m, Time e, Time v);
40
  double m_variance;
40
  void CheckValuesWithTolerance (Ptr<RttEstimator> rtt, Time m, Time e, Time v);
41
  double m_gain;
42
43
};
41
};
44
42
45
RttTestCase::RttTestCase (double mean,
43
RttEstimatorTestCase::RttEstimatorTestCase ()
46
                          double variance,
44
  : TestCase ("Rtt Estimator Test")
47
                          double gain)
48
  : TestCase ("Rtt Estimate Test"),
49
    m_mean (mean),
50
    m_variance (variance),
51
    m_gain (gain)
52
{
45
{
53
}
46
}
54
47
55
void
48
void
56
RttTestCase::DoRun (void)
49
RttEstimatorTestCase::CheckValues (Ptr<RttEstimator> rtt, Time m, Time e, Time v)
57
{
50
{
58
  Config::SetDefault ("ns3::RttEstimator::InitialEstimation", TimeValue (MilliSeconds (m_mean)));
51
  rtt->Measurement (m);
59
  Config::SetDefault ("ns3::RttMeanDeviation::Gain", DoubleValue (m_gain));
52
  NS_TEST_EXPECT_MSG_EQ (rtt->GetEstimate (), e, "Estimate not correct");
60
  Config::SetDefault ("ns3::RttEstimator::MinRTO", TimeValue (Seconds (0)));
53
  NS_TEST_EXPECT_MSG_EQ (rtt->GetVariation (), v, "Estimate not correct");
54
}
55
56
void
57
RttEstimatorTestCase::CheckValuesWithTolerance (Ptr<RttEstimator> rtt, Time m, Time e, Time v)
58
{
59
  rtt->Measurement (m);
60
  NS_TEST_EXPECT_MSG_EQ_TOL (rtt->GetEstimate (), e, Time (NanoSeconds (1)), "Estimate not correct");
61
  NS_TEST_EXPECT_MSG_EQ_TOL (rtt->GetVariation (), v, Time (NanoSeconds (1)), "Estimate not correct");
62
}
63
64
65
void
66
RttEstimatorTestCase::DoRun (void)
67
{
68
  // Set to a non-default value
69
  Config::SetDefault ("ns3::RttEstimator::InitialEstimation", TimeValue (MilliSeconds (500)));
70
  Config::SetDefault ("ns3::RttMeanDeviation::Alpha", DoubleValue (0.5));
71
  Config::SetDefault ("ns3::RttMeanDeviation::Beta", DoubleValue (0.6));
61
72
62
  Ptr<RttMeanDeviation> rtt = CreateObject<RttMeanDeviation> ();
73
  Ptr<RttMeanDeviation> rtt = CreateObject<RttMeanDeviation> ();
63
  Ptr<NormalRandomVariable> nv = CreateObject<NormalRandomVariable> ();
64
  nv->SetAttribute ("Mean", DoubleValue (m_mean));
65
  nv->SetAttribute ("Variance", DoubleValue (m_variance));
66
74
67
  NS_TEST_EXPECT_MSG_EQ (m_mean, rtt->GetCurrentEstimate ().GetMilliSeconds (), "Initial estimate should match mean");
75
  bool ok;
76
  TimeValue timeval;
77
  DoubleValue doubleval;
78
  ok = rtt->GetAttributeFailSafe ("InitialEstimation", timeval);
79
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be gettable");
80
  NS_TEST_EXPECT_MSG_EQ (timeval.Get (), MilliSeconds (500), "Initial estimate should match");
81
  ok = rtt->GetAttributeFailSafe ("Alpha", doubleval);
82
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be gettable");
83
  NS_TEST_ASSERT_MSG_EQ_TOL (doubleval.Get (), 0.5, 0.001, "Alpha not set");
84
  ok = rtt->GetAttributeFailSafe ("Beta", doubleval);
85
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be gettable");
86
  NS_TEST_ASSERT_MSG_EQ_TOL (doubleval.Get (), 0.6, 0.001, "Beta not set");
68
87
69
  double a, v, g;
88
  // Reset to default values
70
  a = v = m_mean;
89
  ok = rtt->SetAttributeFailSafe ("InitialEstimation", TimeValue (Seconds (1)));
71
  g = m_gain;
90
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
91
  ok = rtt->SetAttributeFailSafe ("Alpha", DoubleValue (0.125));
92
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
93
  ok = rtt->SetAttributeFailSafe ("Beta", DoubleValue (0.25));
94
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
95
  rtt->Reset ();
72
96
73
  for (uint32_t i = 0; i < 10000; ++i)
97
  Time t (Seconds (1));
74
    {
98
  Time t2 (MilliSeconds (125));
75
      int measurement = nv->GetInteger ();
99
  NS_TEST_EXPECT_MSG_EQ (t2, Time::From (t.GetInteger () >> 3), "X");
76
      rtt->Measurement (Time::FromInteger (measurement, Time::MS));
100
  NS_TEST_EXPECT_MSG_EQ (rtt->GetEstimate (), Time (Seconds (1)), "Incorrect initial estimate");
77
      double err = (measurement - a);
101
  NS_TEST_EXPECT_MSG_EQ (rtt->GetVariation (), Time (Seconds (0)), "Incorrect initial variance");
78
      a = a + g * err;
102
  NS_TEST_EXPECT_MSG_EQ (rtt->GetNSamples (), 0, "Incorrect initial estimate");
79
      v = v + g * (std::abs (err) - v);
80
    }
81
103
82
  //5% tolerance
104
  // CheckValues (rtt, measurement, new estimate, new variance);
83
  double tolerance = m_mean * .05;
105
  // Initial value:  SRTT <- measurement; RTTVAR <- measurement/2
106
  CheckValues (rtt, Time (Seconds (1)), Time (Seconds (1)), Time (MilliSeconds (500)));
107
  // Subsequent values:  according to RFC 6298
108
  CheckValues (rtt, Time (MilliSeconds (1200)), Time (MilliSeconds (1025)), Time (MilliSeconds (425)));
109
  Ptr<RttEstimator> copy = rtt->Copy ();
110
  CheckValues (rtt, Time (MilliSeconds (900)), Time (MicroSeconds (1009375)), Time (MilliSeconds (350)));
84
111
85
  NS_TEST_ASSERT_MSG_EQ_TOL (m_mean, rtt->GetCurrentEstimate ().GetMilliSeconds (), tolerance, "Unexpected estimate");
112
  // Check behavior of copy; should have inherited state
113
  CheckValues (copy, Time (MilliSeconds (900)), Time (MicroSeconds (1009375)), Time (MilliSeconds (350)));
86
114
87
  int expectedTimeout = (int)a + 4 * (int)v;
115
  // Floating point arithmetic due to alpha and beta settings
116
  rtt->Reset ();
117
  ok = rtt->SetAttributeFailSafe ("Alpha", DoubleValue (0.1));
118
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
119
  ok = rtt->SetAttributeFailSafe ("Beta", DoubleValue (0.1));
120
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
121
  CheckValuesWithTolerance (rtt, Time (Seconds (1.2)), Time (Seconds (1.2)), Time (Seconds (0.6)));
122
  CheckValuesWithTolerance (rtt, Time (MilliSeconds (950)), Time (MilliSeconds (1175)), Time (MilliSeconds (565)));
123
  CheckValuesWithTolerance (rtt, Time (MilliSeconds (1400)), Time (MicroSeconds (1197500)), Time (MilliSeconds (531)));
88
124
89
  NS_TEST_EXPECT_MSG_EQ (rtt->RetransmitTimeout ().GetMilliSeconds (), expectedTimeout, "Timeout values do not match");
125
  // Check boundary values; 0 will not update, 1 will use most recent value
126
  rtt->Reset ();
127
  ok = rtt->SetAttributeFailSafe ("Alpha", DoubleValue (0));
128
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
129
  ok = rtt->SetAttributeFailSafe ("Beta", DoubleValue (0));
130
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
131
  CheckValues (rtt, Time (Seconds (1)), Time (Seconds (1)), Time (MilliSeconds (500)));
132
  CheckValues (rtt, Time (Seconds (2)), Time (Seconds (1)), Time (MilliSeconds (500)));
133
  CheckValues (rtt, Time (Seconds (3)), Time (Seconds (1)), Time (MilliSeconds (500)));
134
  rtt->Reset ();
135
  ok = rtt->SetAttributeFailSafe ("Alpha", DoubleValue (1));
136
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
137
  ok = rtt->SetAttributeFailSafe ("Beta", DoubleValue (1));
138
  NS_TEST_EXPECT_MSG_EQ (ok, true, "Attribute should be settable");
139
  CheckValues (rtt, Time (Seconds (1)), Time (Seconds (1)), Time (MilliSeconds (500)));
140
  CheckValues (rtt, Time (Seconds (2.5)), Time (Seconds (2.5)), Time (Seconds (1.5)));
141
  CheckValues (rtt, Time (Seconds (7)), Time (Seconds (7)), Time (Seconds (4.5)));
142
  
143
  // recheck initial values
144
  rtt->Reset ();
145
  NS_TEST_EXPECT_MSG_EQ (rtt->GetEstimate (), Time (Seconds (1)), "Incorrect initial estimate");
146
  NS_TEST_EXPECT_MSG_EQ (rtt->GetVariation (), Time (Seconds (0)), "Incorrect initial variation");
147
  NS_TEST_EXPECT_MSG_EQ (rtt->GetNSamples (), 0, "Incorrect initial estimate");
90
}
148
}
149
91
void
150
void
92
RttTestCase::DoTeardown (void)
151
RttEstimatorTestCase::DoTeardown (void)
93
{
152
{
94
}
153
}
95
154
96
155
class RttEstimatorTestSuite : public TestSuite
97
static class RttTestSuite : public TestSuite
98
{
156
{
99
public:
157
public:
100
  RttTestSuite ()
158
  RttEstimatorTestSuite ()
101
    : TestSuite ("rtt", UNIT)
159
    : TestSuite ("rtt-estimator", UNIT)
102
  {
160
  {
103
    AddTestCase (new RttTestCase (150.0, 10.0, .1), TestCase::QUICK);
161
    AddTestCase (new RttEstimatorTestCase, TestCase::QUICK);
104
    AddTestCase (new RttTestCase (5000.0, 5.0, .5), TestCase::QUICK);
105
    AddTestCase (new RttTestCase (200.0, 25.0, .7), TestCase::QUICK);
106
  }
162
  }
107
163
108
} g_tcpTestSuite;
164
};
165
166
static RttEstimatorTestSuite  g_rttEstimatorTestSuite;
167
168

Return to bug 1405