|
30 |
#include "rtt-estimator.h" |
30 |
#include "rtt-estimator.h" |
31 |
#include "ns3/simulator.h" |
31 |
#include "ns3/simulator.h" |
32 |
#include "ns3/double.h" |
32 |
#include "ns3/double.h" |
|
|
33 |
#include "ns3/integer.h" |
33 |
|
34 |
|
34 |
namespace ns3 { |
35 |
namespace ns3 { |
35 |
|
36 |
|
|
42 |
static TypeId tid = TypeId ("ns3::RttEstimator") |
43 |
static TypeId tid = TypeId ("ns3::RttEstimator") |
43 |
.SetParent<Object> () |
44 |
.SetParent<Object> () |
44 |
.AddAttribute ("MaxMultiplier", |
45 |
.AddAttribute ("MaxMultiplier", |
45 |
"XXX", |
46 |
"Maximum RTO Multiplier", |
46 |
DoubleValue (64.0), |
47 |
IntegerValue (64), |
47 |
MakeDoubleAccessor (&RttEstimator::m_maxMultiplier), |
48 |
MakeDoubleAccessor (&RttEstimator::m_maxMultiplier), |
48 |
MakeDoubleChecker<double> ()) |
49 |
MakeIntegerChecker<u_int16_t> ()) |
49 |
.AddAttribute ("InitialEstimation", |
50 |
.AddAttribute ("InitialEstimation", |
50 |
"XXX", |
51 |
"Initial RTT estimation", |
51 |
TimeValue (Seconds (1.0)), |
52 |
TimeValue (Seconds (1.0)), |
52 |
MakeTimeAccessor (&RttEstimator::SetEstimate, |
53 |
MakeTimeAccessor (&RttEstimator::m_initialEstimatedRtt), |
53 |
&RttEstimator::GetEstimate), |
|
|
54 |
MakeTimeChecker ()) |
54 |
MakeTimeChecker ()) |
55 |
.AddAttribute ("MinRTO", |
55 |
.AddAttribute ("MinRTO", |
56 |
"Minimum retransmit timeout value", |
56 |
"Minimum retransmit timeout value", |
|
65 |
void |
65 |
void |
66 |
RttEstimator::SetMinRto (Time minRto) |
66 |
RttEstimator::SetMinRto (Time minRto) |
67 |
{ |
67 |
{ |
68 |
minrto = minRto; |
68 |
m_minRto = minRto; |
69 |
} |
69 |
} |
70 |
Time |
70 |
Time |
71 |
RttEstimator::GetMinRto (void) const |
71 |
RttEstimator::GetMinRto (void) const |
72 |
{ |
72 |
{ |
73 |
return Time (minrto); |
73 |
return Time (m_minRto); |
74 |
} |
74 |
} |
75 |
void |
75 |
void |
76 |
RttEstimator::SetEstimate (Time estimate) |
76 |
RttEstimator::SetCurrentEstimate (Time estimate) |
77 |
{ |
77 |
{ |
78 |
est = estimate; |
78 |
m_currentEstimatedRtt = estimate; |
79 |
} |
79 |
} |
80 |
Time |
80 |
Time |
81 |
RttEstimator::GetEstimate (void) const |
81 |
RttEstimator::GetCurrentEstimate (void) const |
82 |
{ |
82 |
{ |
83 |
return Time (est); |
83 |
return Time (m_currentEstimatedRtt); |
84 |
} |
84 |
} |
85 |
|
85 |
|
86 |
|
86 |
|
|
97 |
|
97 |
|
98 |
// Base class methods |
98 |
// Base class methods |
99 |
|
99 |
|
100 |
RttEstimator::RttEstimator () : next (1), history (), |
100 |
RttEstimator::RttEstimator () |
101 |
nSamples (0), multiplier (1.0) |
101 |
: m_next (1), m_history (), |
|
|
102 |
m_currentEstimatedRtt(m_initialEstimatedRtt), |
103 |
m_nSamples (0), |
104 |
m_multiplier (1) |
102 |
{ |
105 |
{ |
103 |
//note next=1 everywhere since first segment will have sequence 1 |
106 |
//note next=1 everywhere since first segment will have sequence 1 |
104 |
} |
107 |
} |
105 |
|
108 |
|
106 |
RttEstimator::RttEstimator(const RttEstimator& c) |
|
|
107 |
: Object (c), next (c.next), history (c.history), |
108 |
m_maxMultiplier (c.m_maxMultiplier), est (c.est), |
109 |
minrto (c.minrto), nSamples (c.nSamples), |
110 |
multiplier (c.multiplier) |
111 |
{ |
112 |
} |
113 |
|
114 |
RttEstimator::~RttEstimator () |
109 |
RttEstimator::~RttEstimator () |
115 |
{ |
110 |
{ |
116 |
} |
111 |
} |
117 |
|
112 |
|
118 |
void RttEstimator::SentSeq (SequenceNumber32 s, uint32_t c) |
113 |
void RttEstimator::SentSeq (SequenceNumber32 seq, uint32_t size) |
119 |
{ // Note that a particular sequence has been sent |
114 |
{ // Note that a particular sequence has been sent |
120 |
if (s == next) |
115 |
if (seq == m_next) |
121 |
{ // This is the next expected one, just log at end |
116 |
{ // This is the next expected one, just log at end |
122 |
history.push_back (RttHistory (s, c, Simulator::Now () )); |
117 |
m_history.push_back (RttHistory (seq, size, Simulator::Now () )); |
123 |
next = s + SequenceNumber32 (c); // Update next expected |
118 |
m_next = seq + SequenceNumber32 (size); // Update next expected |
124 |
} |
119 |
} |
125 |
else |
120 |
else |
126 |
{ // This is a retransmit, find in list and mark as re-tx |
121 |
{ // This is a retransmit, find in list and mark as re-tx |
127 |
for (RttHistory_t::iterator i = history.begin (); i != history.end (); ++i) |
122 |
for (RttHistory_t::iterator i = m_history.begin (); i != m_history.end (); ++i) |
128 |
{ |
123 |
{ |
129 |
if ((s >= i->seq) && (s < (i->seq + SequenceNumber32 (i->count)))) |
124 |
if ((seq >= i->seq) && (seq < (i->seq + SequenceNumber32 (i->count)))) |
130 |
{ // Found it |
125 |
{ // Found it |
131 |
i->retx = true; |
126 |
i->retx = true; |
132 |
// One final test..be sure this re-tx does not extend "next" |
127 |
// One final test..be sure this re-tx does not extend "next" |
133 |
if ((s + SequenceNumber32 (c)) > next) |
128 |
if ((seq + SequenceNumber32 (size)) > m_next) |
134 |
{ |
129 |
{ |
135 |
next = s + SequenceNumber32 (c); |
130 |
m_next = seq + SequenceNumber32 (size); |
136 |
i->count = ((s + SequenceNumber32 (c)) - i->seq); // And update count in hist |
131 |
i->count = ((seq + SequenceNumber32 (size)) - i->seq); // And update count in hist |
137 |
} |
132 |
} |
138 |
break; |
133 |
break; |
139 |
} |
134 |
} |
|
141 |
} |
136 |
} |
142 |
} |
137 |
} |
143 |
|
138 |
|
144 |
Time RttEstimator::AckSeq (SequenceNumber32 a) |
139 |
Time RttEstimator::AckSeq (SequenceNumber32 ackSeq) |
145 |
{ // An ack has been received, calculate rtt and log this measurement |
140 |
{ // An ack has been received, calculate rtt and log this measurement |
146 |
// Note we use a linear search (O(n)) for this since for the common |
141 |
// Note we use a linear search (O(n)) for this since for the common |
147 |
// case the ack'ed packet will be at the head of the list |
142 |
// case the ack'ed packet will be at the head of the list |
148 |
Time m = Seconds (0.0); |
143 |
Time m = Seconds (0.0); |
149 |
if (history.size () == 0) return (m); // No pending history, just exit |
144 |
if (m_history.size () == 0) return (m); // No pending history, just exit |
150 |
RttHistory& h = history.front (); |
145 |
RttHistory& h = m_history.front (); |
151 |
if (!h.retx && a >= (h.seq + SequenceNumber32 (h.count))) |
146 |
if (!h.retx && ackSeq >= (h.seq + SequenceNumber32 (h.count))) |
152 |
{ // Ok to use this sample |
147 |
{ // Ok to use this sample |
153 |
m = Simulator::Now () - h.time; // Elapsed time |
148 |
m = Simulator::Now () - h.time; // Elapsed time |
154 |
Measurement (m); // Log the measurement |
149 |
Measurement (m); // Log the measurement |
155 |
ResetMultiplier (); // Reset multiplier on valid measurement |
150 |
ResetMultiplier (); // Reset multiplier on valid measurement |
156 |
} |
151 |
} |
157 |
// Now delete all ack history with seq <= ack |
152 |
// Now delete all ack history with seq <= ack |
158 |
while(history.size () > 0) |
153 |
while(m_history.size () > 0) |
159 |
{ |
154 |
{ |
160 |
RttHistory& h = history.front (); |
155 |
RttHistory& h = m_history.front (); |
161 |
if ((h.seq + SequenceNumber32 (h.count)) > a) break; // Done removing |
156 |
if ((h.seq + SequenceNumber32 (h.count)) > ackSeq) break; // Done removing |
162 |
history.pop_front (); // Remove |
157 |
m_history.pop_front (); // Remove |
163 |
} |
158 |
} |
164 |
return m; |
159 |
return m; |
165 |
} |
160 |
} |
166 |
|
161 |
|
167 |
void RttEstimator::ClearSent () |
162 |
void RttEstimator::ClearSent () |
168 |
{ // Clear all history entries |
163 |
{ // Clear all history entries |
169 |
next = 1; |
164 |
m_next = 1; |
170 |
history.clear (); |
165 |
m_history.clear (); |
171 |
} |
166 |
} |
172 |
|
167 |
|
173 |
void RttEstimator::IncreaseMultiplier () |
168 |
void RttEstimator::IncreaseMultiplier () |
174 |
{ |
169 |
{ |
175 |
multiplier = std::min (multiplier * 2.0, m_maxMultiplier); |
170 |
m_multiplier = (m_multiplier*2 < m_maxMultiplier) ? m_multiplier*2 : m_maxMultiplier; |
176 |
} |
171 |
} |
177 |
|
172 |
|
178 |
void RttEstimator::ResetMultiplier () |
173 |
void RttEstimator::ResetMultiplier () |
179 |
{ |
174 |
{ |
180 |
multiplier = 1.0; |
175 |
m_multiplier = 1; |
181 |
} |
176 |
} |
182 |
|
177 |
|
183 |
void RttEstimator::Reset () |
178 |
void RttEstimator::Reset () |
184 |
{ // Reset to initial state |
179 |
{ // Reset to initial state |
185 |
next = 1; |
180 |
m_next = 1; |
186 |
est = 1; // XXX: we should go back to the 'initial value' here. Need to add support in Object for this. |
181 |
m_currentEstimatedRtt = m_initialEstimatedRtt; |
187 |
history.clear (); // Remove all info from the history |
182 |
m_history.clear (); // Remove all info from the history |
188 |
nSamples = 0; |
183 |
m_nSamples = 0; |
189 |
ResetMultiplier (); |
184 |
ResetMultiplier (); |
190 |
} |
185 |
} |
191 |
|
186 |
|
|
204 |
.SetParent<RttEstimator> () |
199 |
.SetParent<RttEstimator> () |
205 |
.AddConstructor<RttMeanDeviation> () |
200 |
.AddConstructor<RttMeanDeviation> () |
206 |
.AddAttribute ("Gain", |
201 |
.AddAttribute ("Gain", |
207 |
"XXX", |
202 |
"Gain used in estimating the RTT, must be 0 < Gain < 1", |
208 |
DoubleValue (0.1), |
203 |
DoubleValue (0.1), |
209 |
MakeDoubleAccessor (&RttMeanDeviation::gain), |
204 |
MakeDoubleAccessor (&RttMeanDeviation::m_gain), |
210 |
MakeDoubleChecker<double> ()) |
205 |
MakeDoubleChecker<double> ()) |
211 |
; |
206 |
; |
212 |
return tid; |
207 |
return tid; |
213 |
} |
208 |
} |
214 |
|
209 |
|
215 |
RttMeanDeviation::RttMeanDeviation() : |
210 |
RttMeanDeviation::RttMeanDeviation() : |
216 |
variance (0) |
211 |
m_variance (0) |
217 |
{ |
212 |
{ |
218 |
} |
213 |
} |
219 |
|
214 |
|
220 |
RttMeanDeviation::RttMeanDeviation (const RttMeanDeviation& c) |
215 |
RttMeanDeviation::RttMeanDeviation (const RttMeanDeviation& c) |
221 |
: RttEstimator (c), gain (c.gain), variance (c.variance) |
216 |
: RttEstimator (c), m_gain (c.m_gain), m_variance (c.m_variance) |
222 |
{ |
217 |
{ |
223 |
} |
218 |
} |
224 |
|
219 |
|
225 |
void RttMeanDeviation::Measurement (Time m) |
220 |
void RttMeanDeviation::Measurement (Time m) |
226 |
{ |
221 |
{ |
227 |
if (nSamples) |
222 |
if (m_nSamples) |
228 |
{ // Not first |
223 |
{ // Not first |
229 |
int64x64_t err = m - est; |
224 |
Time err(m - m_currentEstimatedRtt); |
230 |
est = est + gain * err; // estimated rtt |
225 |
m_currentEstimatedRtt += m_gain * err; // estimated rtt |
231 |
variance = variance + gain * (Abs (err) - variance); // variance of rtt |
226 |
m_variance += m_gain * (Abs (err) - m_variance); // variance of rtt |
232 |
} |
227 |
} |
233 |
else |
228 |
else |
234 |
{ // First sample |
229 |
{ // First sample |
235 |
est = m; // Set estimate to current |
230 |
m_currentEstimatedRtt = m; // Set estimate to current |
236 |
//variance = sample / 2; // And variance to current / 2 |
231 |
//variance = sample / 2; // And variance to current / 2 |
237 |
variance = m; // try this |
232 |
m_variance = m; // try this |
238 |
} |
233 |
} |
239 |
nSamples++; |
234 |
m_nSamples++; |
240 |
} |
235 |
} |
241 |
|
236 |
|
242 |
Time RttMeanDeviation::RetransmitTimeout () |
237 |
Time RttMeanDeviation::RetransmitTimeout () |
243 |
{ |
238 |
{ |
244 |
// If not enough samples, justjust return 2 times estimate |
239 |
// If not enough samples, just return 2 times estimate |
245 |
//if (nSamples < 2) return est * 2; |
240 |
//if (nSamples < 2) return est * 2; |
246 |
int64x64_t retval; |
241 |
int64x64_t retval; |
247 |
if (variance < est / 4.0) |
242 |
if (m_variance < m_currentEstimatedRtt / 4.0) |
248 |
{ |
243 |
{ |
249 |
retval = est * 2 * multiplier; // At least twice current est |
244 |
retval = m_currentEstimatedRtt * 2 * m_multiplier; // At least twice current est |
250 |
} |
245 |
} |
251 |
else |
246 |
else |
252 |
{ |
247 |
{ |
253 |
retval = (est + 4 * variance) * multiplier; // As suggested by Jacobson |
248 |
retval = (m_currentEstimatedRtt + 4 * m_variance) * m_multiplier; // As suggested by Jacobson |
254 |
} |
249 |
} |
255 |
retval = Max (retval, minrto); |
250 |
retval = Max (retval, m_minRto); |
256 |
return Time (retval); |
251 |
return Time (retval); |
257 |
} |
252 |
} |
258 |
|
253 |
|
|
263 |
|
258 |
|
264 |
void RttMeanDeviation::Reset () |
259 |
void RttMeanDeviation::Reset () |
265 |
{ // Reset to initial state |
260 |
{ // Reset to initial state |
266 |
variance = 0; |
261 |
m_variance = 0; |
267 |
RttEstimator::Reset (); |
262 |
RttEstimator::Reset (); |
268 |
} |
263 |
} |
|
|
264 |
void RttMeanDeviation::Gain (double g) |
265 |
{ |
266 |
NS_ASSERT_MSG( (g > 0) && (g < 1), "RttMeanDeviation: Gain must be less than 1 and greater than 0" ); |
267 |
m_gain = g; |
268 |
} |
269 |
|
269 |
} //namepsace ns3 |
270 |
} //namepsace ns3 |