|
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 { |
|
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 |
} |
|
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 |
//----------------------------------------------------------------------------- |
|
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 |
} |
|
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 |