# HG changeset patch # User Tommaso Pecorella # Date 1422598481 -3600 # Parent 9285d060b3989253ff5fcc9ac755fa7149b1c405 diff --git a/src/internet/model/rtt-estimator.cc b/src/internet/model/rtt-estimator.cc --- a/src/internet/model/rtt-estimator.cc +++ b/src/internet/model/rtt-estimator.cc @@ -18,20 +18,18 @@ // Author: Rajib Bhattacharjea // - // Ported from: -// Georgia Tech Network Simulator - Round Trip Time Estimation Class +// Georgia Tech Network Simulator - Round Trip Time Estimator Class // George F. Riley. Georgia Tech, Spring 2002 -// Implements several variations of round trip time estimators +// Base class allows variations of round trip time estimators to be +// implemented #include +#include #include "rtt-estimator.h" -#include "ns3/simulator.h" #include "ns3/double.h" -#include "ns3/integer.h" -#include "ns3/uinteger.h" #include "ns3/log.h" namespace ns3 { @@ -40,91 +38,56 @@ NS_OBJECT_ENSURE_REGISTERED (RttEstimator); +static const double TOLERANCE = 1e-6; + TypeId RttEstimator::GetTypeId (void) { static TypeId tid = TypeId ("ns3::RttEstimator") .SetParent () - .AddAttribute ("MaxMultiplier", - "Maximum RTO Multiplier", - UintegerValue (64), - MakeUintegerAccessor (&RttEstimator::m_maxMultiplier), - MakeUintegerChecker ()) .AddAttribute ("InitialEstimation", - "Initial RTT estimation", + "Initial RTT estimate", TimeValue (Seconds (1.0)), MakeTimeAccessor (&RttEstimator::m_initialEstimatedRtt), MakeTimeChecker ()) - .AddAttribute ("MinRTO", - "Minimum retransmit timeout value", - 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 - MakeTimeAccessor (&RttEstimator::SetMinRto, - &RttEstimator::GetMinRto), - MakeTimeChecker ()) ; return tid; } -void -RttEstimator::SetMinRto (Time minRto) +Time +RttEstimator::GetEstimate (void) const { - NS_LOG_FUNCTION (this << minRto); - m_minRto = minRto; -} -Time -RttEstimator::GetMinRto (void) const -{ - return m_minRto; -} -void -RttEstimator::SetCurrentEstimate (Time estimate) -{ - NS_LOG_FUNCTION (this << estimate); - m_currentEstimatedRtt = estimate; -} -Time -RttEstimator::GetCurrentEstimate (void) const -{ - return m_currentEstimatedRtt; + return m_estimatedRtt; } - -//RttHistory methods -RttHistory::RttHistory (SequenceNumber32 s, uint32_t c, Time t) - : seq (s), count (c), time (t), retx (false) +Time +RttEstimator::GetVariation (void) const { - NS_LOG_FUNCTION (this); + return m_estimatedVariation; } -RttHistory::RttHistory (const RttHistory& h) - : seq (h.seq), count (h.count), time (h.time), retx (h.retx) -{ - NS_LOG_FUNCTION (this); -} // Base class methods RttEstimator::RttEstimator () - : m_next (1), m_history (), - m_nSamples (0), - m_multiplier (1) + : m_nSamples (0) { NS_LOG_FUNCTION (this); - //note next=1 everywhere since first segment will have sequence 1 // We need attributes initialized here, not later, so use the // ConstructSelf() technique documented in the manual ObjectBase::ConstructSelf (AttributeConstructionList ()); - m_currentEstimatedRtt = m_initialEstimatedRtt; - NS_LOG_DEBUG ("Initialize m_currentEstimatedRtt to " << m_currentEstimatedRtt.GetSeconds () << " sec."); + m_estimatedRtt = m_initialEstimatedRtt; + m_estimatedVariation = Time (0); + NS_LOG_DEBUG ("Initialize m_estimatedRtt to " << m_estimatedRtt.GetSeconds () << " sec."); } RttEstimator::RttEstimator (const RttEstimator& c) - : Object (c), m_next (c.m_next), m_history (c.m_history), - m_maxMultiplier (c.m_maxMultiplier), + : Object (c), m_initialEstimatedRtt (c.m_initialEstimatedRtt), - m_currentEstimatedRtt (c.m_currentEstimatedRtt), m_minRto (c.m_minRto), - m_nSamples (c.m_nSamples), m_multiplier (c.m_multiplier) + m_estimatedRtt (c.m_estimatedRtt), + m_estimatedVariation (c.m_estimatedVariation), + m_nSamples (c.m_nSamples) { NS_LOG_FUNCTION (this); } @@ -140,92 +103,20 @@ return GetTypeId (); } -void RttEstimator::SentSeq (SequenceNumber32 seq, uint32_t size) -{ - NS_LOG_FUNCTION (this << seq << size); - // Note that a particular sequence has been sent - if (seq == m_next) - { // This is the next expected one, just log at end - m_history.push_back (RttHistory (seq, size, Simulator::Now () )); - m_next = seq + SequenceNumber32 (size); // Update next expected - } - else - { // This is a retransmit, find in list and mark as re-tx - for (RttHistory_t::iterator i = m_history.begin (); i != m_history.end (); ++i) - { - if ((seq >= i->seq) && (seq < (i->seq + SequenceNumber32 (i->count)))) - { // Found it - i->retx = true; - // One final test..be sure this re-tx does not extend "next" - if ((seq + SequenceNumber32 (size)) > m_next) - { - m_next = seq + SequenceNumber32 (size); - i->count = ((seq + SequenceNumber32 (size)) - i->seq); // And update count in hist - } - break; - } - } - } -} - -Time RttEstimator::EstimateRttFromSeq (SequenceNumber32 ackSeq) -{ - NS_LOG_FUNCTION (this << ackSeq); - // An ack has been received, calculate rtt and log this measurement - // Note we use a linear search (O(n)) for this since for the common - // case the ack'ed packet will be at the head of the list - Time m = Seconds (0.0); - if (m_history.size () == 0) return (m); // No pending history, just exit - RttHistory& h = m_history.front (); - if (!h.retx && ackSeq >= (h.seq + SequenceNumber32 (h.count))) - { // Ok to use this sample - m = Simulator::Now () - h.time; // Elapsed time - Measurement (m); // Log the measurement - ResetMultiplier (); // Reset multiplier on valid measurement - } - // Now delete all ack history with seq <= ack - while(m_history.size () > 0) - { - RttHistory& h = m_history.front (); - if ((h.seq + SequenceNumber32 (h.count)) > ackSeq) break; // Done removing - m_history.pop_front (); // Remove - } - return m; -} - -void RttEstimator::ClearSent () -{ - NS_LOG_FUNCTION (this); - // Clear all history entries - m_next = 1; - m_history.clear (); -} - -void RttEstimator::IncreaseMultiplier () -{ - NS_LOG_FUNCTION (this); - m_multiplier = (m_multiplier*2 < m_maxMultiplier) ? m_multiplier*2 : m_maxMultiplier; - NS_LOG_DEBUG ("Multiplier increased to " << m_multiplier); -} - -void RttEstimator::ResetMultiplier () -{ - NS_LOG_FUNCTION (this); - m_multiplier = 1; -} - void RttEstimator::Reset () { NS_LOG_FUNCTION (this); // Reset to initial state - m_next = 1; - m_currentEstimatedRtt = m_initialEstimatedRtt; - m_history.clear (); // Remove all info from the history + m_estimatedRtt = m_initialEstimatedRtt; + m_estimatedVariation = Time (0); m_nSamples = 0; - ResetMultiplier (); } - +uint32_t +RttEstimator::GetNSamples (void) const +{ + return m_nSamples; +} //----------------------------------------------------------------------------- //----------------------------------------------------------------------------- @@ -239,23 +130,27 @@ static TypeId tid = TypeId ("ns3::RttMeanDeviation") .SetParent () .AddConstructor () - .AddAttribute ("Gain", - "Gain used in estimating the RTT, must be 0 < Gain < 1", - DoubleValue (0.1), - MakeDoubleAccessor (&RttMeanDeviation::m_gain), - MakeDoubleChecker ()) + .AddAttribute ("Alpha", + "Gain used in estimating the RTT, must be 0 <= alpha <= 1", + DoubleValue (0.125), + MakeDoubleAccessor (&RttMeanDeviation::m_alpha), + MakeDoubleChecker (0, 1)) + .AddAttribute ("Beta", + "Gain used in estimating the RTT variation, must be 0 <= beta <= 1", + DoubleValue (0.25), + MakeDoubleAccessor (&RttMeanDeviation::m_beta), + MakeDoubleChecker (0, 1)) ; return tid; } -RttMeanDeviation::RttMeanDeviation() : - m_variance (0) -{ +RttMeanDeviation::RttMeanDeviation() +{ NS_LOG_FUNCTION (this); } RttMeanDeviation::RttMeanDeviation (const RttMeanDeviation& c) - : RttEstimator (c), m_gain (c.m_gain), m_variance (c.m_variance) + : RttEstimator (c), m_alpha (c.m_alpha), m_beta (c.m_beta) { NS_LOG_FUNCTION (this); } @@ -266,62 +161,120 @@ return GetTypeId (); } -void RttMeanDeviation::Measurement (Time m) +uint32_t +RttMeanDeviation::CheckForReciprocalPowerOfTwo (double val) const +{ + NS_LOG_FUNCTION (this << val); + if (val < TOLERANCE) + { + return 0; + } + // supports 1/32, 1/16, 1/8, 1/4, 1/2 + if (abs (1/val - 8) < TOLERANCE) + { + return 3; + } + if (abs (1/val - 4) < TOLERANCE) + { + return 2; + } + if (abs (1/val - 32) < TOLERANCE) + { + return 5; + } + if (abs (1/val - 16) < TOLERANCE) + { + return 4; + } + if (abs (1/val - 2) < TOLERANCE) + { + return 1; + } + return 0; +} + +void +RttMeanDeviation::FloatingPointUpdate (Time m) +{ + NS_LOG_FUNCTION (this << m); + + // EWMA formulas are implemented as suggested in + // Jacobson/Karels paper appendix A.2 + + // SRTT <- (1 - alpha) * SRTT + alpha * R' + Time err (m - m_estimatedRtt); + double gErr = err.ToDouble (Time::S) * m_alpha; + m_estimatedRtt += Time::FromDouble (gErr, Time::S); + + // RTTVAR <- (1 - beta) * RTTVAR + beta * |SRTT - R'| + Time difference = Abs (err) - m_estimatedVariation; + m_estimatedVariation += Time::FromDouble (difference.ToDouble (Time::S) * m_beta, Time::S); + + return; +} + +void +RttMeanDeviation::IntegerUpdate (Time m, uint32_t rttShift, uint32_t variationShift) +{ + NS_LOG_FUNCTION (this << m << rttShift << variationShift); + // Jacobson/Karels paper appendix A.2 + int64_t meas = m.GetInteger (); + int64_t delta = meas - m_estimatedRtt.GetInteger (); + int64_t srtt = (m_estimatedRtt.GetInteger () << rttShift) + delta; + m_estimatedRtt = Time::From (srtt >> rttShift); + if (delta < 0) + { + delta = -delta; + } + delta -= m_estimatedVariation.GetInteger (); + int64_t rttvar = m_estimatedVariation.GetInteger () << variationShift; + rttvar += delta; + m_estimatedVariation = Time::From (rttvar >> variationShift); + return; +} + +void +RttMeanDeviation::Measurement (Time m) { NS_LOG_FUNCTION (this << m); if (m_nSamples) - { // Not first - Time err (m - m_currentEstimatedRtt); - double gErr = err.ToDouble (Time::S) * m_gain; - m_currentEstimatedRtt += Time::FromDouble (gErr, Time::S); - Time difference = Abs (err) - m_variance; - NS_LOG_DEBUG ("m_variance += " << Time::FromDouble (difference.ToDouble (Time::S) * m_gain, Time::S)); - m_variance += Time::FromDouble (difference.ToDouble (Time::S) * m_gain, Time::S); + { + // If both alpha and beta are reciprocal powers of two, updating can + // be done with integer arithmetic according to Jacobson/Karels paper. + // If not, since class Time only supports integer multiplication, + // must convert Time to floating point and back again + uint32_t rttShift = CheckForReciprocalPowerOfTwo (m_alpha); + uint32_t variationShift = CheckForReciprocalPowerOfTwo (m_beta); + if (rttShift && variationShift) + { + IntegerUpdate (m, rttShift, variationShift); + } + else + { + FloatingPointUpdate (m); + } } else { // First sample - m_currentEstimatedRtt = m; // Set estimate to current - //variance = sample / 2; // And variance to current / 2 - m_variance = m; // try this - NS_LOG_DEBUG ("(first sample) m_variance += " << m); + m_estimatedRtt = m; // Set estimate to current + m_estimatedVariation = m / 2; // And variation to current / 2 + NS_LOG_DEBUG ("(first sample) m_estimatedVariation += " << m); } m_nSamples++; } -Time RttMeanDeviation::RetransmitTimeout () -{ - NS_LOG_FUNCTION (this); - NS_LOG_DEBUG ("RetransmitTimeout: var " << m_variance.GetSeconds () << " est " << m_currentEstimatedRtt.GetSeconds () << " multiplier " << m_multiplier); - // RTO = srtt + 4* rttvar - int64_t temp = m_currentEstimatedRtt.ToInteger (Time::MS) + 4 * m_variance.ToInteger (Time::MS); - if (temp < m_minRto.ToInteger (Time::MS)) - { - temp = m_minRto.ToInteger (Time::MS); - } - temp = temp * m_multiplier; // Apply backoff - Time retval = Time::FromInteger (temp, Time::MS); - NS_LOG_DEBUG ("RetransmitTimeout: return " << retval.GetSeconds ()); - return (retval); -} - -Ptr RttMeanDeviation::Copy () const +Ptr +RttMeanDeviation::Copy () const { NS_LOG_FUNCTION (this); return CopyObject (this); } -void RttMeanDeviation::Reset () +void +RttMeanDeviation::Reset () { NS_LOG_FUNCTION (this); - // Reset to initial state - m_variance = Seconds (0); RttEstimator::Reset (); } -void RttMeanDeviation::Gain (double g) -{ - NS_LOG_FUNCTION (this); - NS_ASSERT_MSG( (g > 0) && (g < 1), "RttMeanDeviation: Gain must be less than 1 and greater than 0" ); - m_gain = g; -} } //namespace ns3 diff --git a/src/internet/model/rtt-estimator.h b/src/internet/model/rtt-estimator.h --- a/src/internet/model/rtt-estimator.h +++ b/src/internet/model/rtt-estimator.h @@ -25,8 +25,6 @@ #ifndef RTT_ESTIMATOR_H #define RTT_ESTIMATOR_H -#include -#include "ns3/sequence-number.h" #include "ns3/nstime.h" #include "ns3/object.h" @@ -35,36 +33,12 @@ /** * \ingroup tcp * - * \brief Helper class to store RTT measurements - */ -class RttHistory { -public: - /** - * \brief Constructor - builds an RttHistory with the given parameters - * \param s First sequence number in packet sent - * \param c Number of bytes sent - * \param t Time this one was sent - */ - RttHistory (SequenceNumber32 s, uint32_t c, Time t); - /** - * \brief Copy constructor - * \param h the object to copy - */ - RttHistory (const RttHistory& h); // Copy constructor -public: - SequenceNumber32 seq; //!< First sequence number in packet sent - uint32_t count; //!< Number of bytes sent - Time time; //!< Time this one was sent - bool retx; //!< True if this has been retransmitted -}; - -/// Container for RttHistory objects -typedef std::deque RttHistory_t; - -/** - * \ingroup tcp + * \brief Base class for all RTT Estimators * - * \brief Base class for all RTT Estimators + * The RTT Estimator class computes an estimate of the round trip time + * observed in a series of Time measurements. The estimate is provided in + * the form of an estimate and a sample variation. Subclasses can implement + * different algorithms to provide values for the estimate and variation. */ class RttEstimator : public Object { public: @@ -86,92 +60,51 @@ virtual TypeId GetInstanceTypeId (void) const; /** - * \brief Note that a particular sequence has been sent - * \param seq the packet sequence number. - * \param size the packet size. - */ - virtual void SentSeq (SequenceNumber32 seq, uint32_t size); - - /** - * \brief Note that a particular ack sequence has been received - * \param ackSeq the ack sequence number. - * \return The measured RTT for this ack. - */ - virtual Time EstimateRttFromSeq (SequenceNumber32 ackSeq); - - /** - * \brief Clear all history entries - */ - virtual void ClearSent (); - - /** * \brief Add a new measurement to the estimator. Pure virtual function. * \param t the new RTT measure. */ virtual void Measurement (Time t) = 0; /** - * \brief Returns the estimated RTO. Pure virtual function. - * \return the estimated RTO. - */ - virtual Time RetransmitTimeout () = 0; - - /** - * \brief Copy object + * \brief Copy object (including current internal state) * \returns a copy of itself */ virtual Ptr Copy () const = 0; /** - * \brief Increase the estimation multiplier up to MaxMultiplier. - */ - virtual void IncreaseMultiplier (); - - /** - * \brief Resets the estimation multiplier to 1. - */ - virtual void ResetMultiplier (); - - /** * \brief Resets the estimation to its initial state. */ virtual void Reset (); /** - * \brief Sets the Minimum RTO. - * \param minRto The minimum RTO returned by the estimator. + * \brief gets the RTT estimate. + * \return The RTT estimate. */ - void SetMinRto (Time minRto); + Time GetEstimate (void) const; /** - * \brief Get the Minimum RTO. - * \return The minimum RTO returned by the estimator. + * Note that this is not a formal statistical variance; it has the + * the same units as the estimate. Mean deviation or standard deviation + * are example quantities that could be provided here. + * + * \brief gets the RTT estimate variation. + * \return The RTT estimate variation. */ - Time GetMinRto (void) const; + Time GetVariation (void) const; /** - * \brief Sets the current RTT estimate (forcefully). - * \param estimate The current RTT estimate. + * \brief gets the number of samples used in the estimates + * \return the number of samples used in the estimates */ - void SetCurrentEstimate (Time estimate); - - /** - * \brief gets the current RTT estimate. - * \return The current RTT estimate. - */ - Time GetCurrentEstimate (void) const; + uint32_t GetNSamples (void) const; private: - SequenceNumber32 m_next; //!< Next expected sequence to be sent - RttHistory_t m_history; //!< List of sent packet - uint16_t m_maxMultiplier; //!< Maximum RTO Multiplier Time m_initialEstimatedRtt; //!< Initial RTT estimation protected: - Time m_currentEstimatedRtt; //!< Current estimate - Time m_minRto; //!< minimum value of the timeout + Time m_estimatedRtt; //!< Current estimate + Time m_estimatedVariation; //!< Current estimate variation uint32_t m_nSamples; //!< Number of samples - uint16_t m_multiplier; //!< RTO Multiplier }; /** @@ -183,6 +116,9 @@ * by Van Jacobson and Michael J. Karels, in * "Congestion Avoidance and Control", SIGCOMM 88, Appendix A * + * The default values for the gain (alpha and beta) are set as documented + * in RFC 6298. + * */ class RttMeanDeviation : public RttEstimator { public: @@ -208,12 +144,6 @@ */ void Measurement (Time measure); - /** - * \brief Returns the estimated RTO. - * \return the estimated RTO. - */ - Time RetransmitTimeout (); - Ptr Copy () const; /** @@ -221,16 +151,41 @@ */ void Reset (); +private: + /** + * Utility function to check for possible conversion + * of a double value (0 < value < 1) to a reciprocal power of two + * + * Values of 1/32, 1/16, 1/8, 1/4, and 1/2 (i.e., within the possible + * range of experimentation for this estimator) are supported. + * + * \param val value to check + * \return log base 2 (1/val) if reciprocal power of 2, or zero if not + */ + uint32_t CheckForReciprocalPowerOfTwo (double val) const; /** - * \brief Sets the estimator Gain. - * \param g the gain, where 0 < g < 1. + * Method to update the rtt and variation estimates using integer + * arithmetic, used when the values of Alpha and Beta support the + * integer conversion. + * + * \param m time measurement + * \param rttShift value corresponding to log base 2 (1/alpha) + * \param variationShift value corresponding to log base 2 (1/beta) */ - void Gain (double g); + void IntegerUpdate (Time m, uint32_t rttShift, uint32_t variationShift); + /** + * Method to update the rtt and variation estimates using floating + * point arithmetic, used when the values of Alpha and Beta are not + * both a reciprocal power of two. + * + * \param m time measurement + */ + void FloatingPointUpdate (Time m); + double m_alpha; //!< Filter gain for average + double m_beta; //!< Filter gain for variation -private: - double m_gain; //!< Filter gain - Time m_variance; //!< Current variance }; + } // namespace ns3 #endif /* RTT_ESTIMATOR_H */ diff --git a/src/internet/model/tcp-newreno.cc b/src/internet/model/tcp-newreno.cc --- a/src/internet/model/tcp-newreno.cc +++ b/src/internet/model/tcp-newreno.cc @@ -213,7 +213,6 @@ m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd << ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence); - m_rtt->IncreaseMultiplier (); // Double the next RTO DoRetransmit (); // Retransmit the packet } diff --git a/src/internet/model/tcp-reno.cc b/src/internet/model/tcp-reno.cc --- a/src/internet/model/tcp-reno.cc +++ b/src/internet/model/tcp-reno.cc @@ -188,7 +188,6 @@ m_nextTxSequence = m_txBuffer.HeadSequence (); // Restart from highest Ack NS_LOG_INFO ("RTO. Reset cwnd to " << m_cWnd << ", ssthresh to " << m_ssThresh << ", restart from seqnum " << m_nextTxSequence); - m_rtt->IncreaseMultiplier (); // Double the next RTO DoRetransmit (); // Retransmit the packet } diff --git a/src/internet/model/tcp-socket-base.cc b/src/internet/model/tcp-socket-base.cc --- a/src/internet/model/tcp-socket-base.cc +++ b/src/internet/model/tcp-socket-base.cc @@ -94,6 +94,18 @@ BooleanValue (true), MakeBooleanAccessor (&TcpSocketBase::m_timestampEnabled), MakeBooleanChecker ()) + .AddAttribute ("MinRto", + "Minimum retransmit timeout value", + 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 + MakeTimeAccessor (&TcpSocketBase::SetMinRto, + &TcpSocketBase::GetMinRto), + MakeTimeChecker ()) + .AddAttribute ("ClockGranularity", + "Clock Granularity used in RTO calculations", + TimeValue (MilliSeconds (1)), // RFC6298 suggest to use fine clock granularity + MakeTimeAccessor (&TcpSocketBase::SetClockGranularity, + &TcpSocketBase::GetClockGranularity), + MakeTimeChecker ()) .AddTraceSource ("RTO", "Retransmission timeout", MakeTraceSourceAccessor (&TcpSocketBase::m_rto), @@ -148,8 +160,7 @@ m_sndScaleFactor (0), m_rcvScaleFactor (0), m_timestampEnabled (true), - m_timestampToEcho (0), - m_lastEchoedTime (0) + m_timestampToEcho (0) { NS_LOG_FUNCTION (this); @@ -190,8 +201,7 @@ m_sndScaleFactor (sock.m_sndScaleFactor), m_rcvScaleFactor (sock.m_rcvScaleFactor), m_timestampEnabled (sock.m_timestampEnabled), - m_timestampToEcho (sock.m_timestampToEcho), - m_lastEchoedTime (sock.m_lastEchoedTime) + m_timestampToEcho (sock.m_timestampToEcho) { NS_LOG_FUNCTION (this); @@ -1568,8 +1578,8 @@ if (m_state == LAST_ACK) { NS_LOG_LOGIC ("TcpSocketBase " << this << " scheduling LATO1"); - m_lastAckEvent = Simulator::Schedule (m_rtt->RetransmitTimeout (), - &TcpSocketBase::LastAckTimeout, this); + Time lastRto = m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4); + m_lastAckEvent = Simulator::Schedule (lastRto, &TcpSocketBase::LastAckTimeout, this); } } @@ -1687,7 +1697,10 @@ } AddOptions (header); header.SetWindowSize (AdvertisedWindowSize ()); - m_rto = m_rtt->RetransmitTimeout (); + + // RFC 6298, clause 2.4 + m_rto = Max (m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4), Time::FromDouble (1, Time::S)); + bool hasSyn = flags & TcpHeader::SYN; bool hasFin = flags & TcpHeader::FIN; bool isAck = flags == TcpHeader::ACK; @@ -1696,6 +1709,7 @@ if (m_cnCount == 0) { // No more connection retries, give up NS_LOG_LOGIC ("Connection failed."); + m_rtt->Reset (); //According to recommendation -> RFC 6298 CloseAndNotify (); return; } @@ -1891,6 +1905,12 @@ { NS_LOG_FUNCTION (this << seq << maxSize << withAck); + bool isRetransmission = false; + if ( seq == m_txBuffer.HeadSequence () ) + { + isRetransmission = true; + } + Ptr p = m_txBuffer.CopyFromSequence (maxSize, seq); uint32_t sz = p->GetSize (); // Size of packet uint8_t flags = withAck ? TcpHeader::ACK : 0; @@ -1960,9 +1980,15 @@ } header.SetWindowSize (AdvertisedWindowSize ()); AddOptions (header); + if (m_retxEvent.IsExpired () ) - { // Schedule retransmit - m_rto = m_rtt->RetransmitTimeout (); + { + // RFC 6298, clause 2.5 + Time doubledRto = m_rto + m_rto; + m_rto = Min (doubledRto, Time::FromDouble (60, Time::S)); + + // Schedules retransmit + NS_LOG_LOGIC (this << " SendDataPacket Schedule ReTxTimeout at time " << Simulator::Now ().GetSeconds () << " to expire at time " << (Simulator::Now () + m_rto.Get ()).GetSeconds () ); @@ -1979,7 +2005,25 @@ m_tcp->SendPacket (p, header, m_endPoint6->GetLocalAddress (), m_endPoint6->GetPeerAddress (), m_boundnetdevice); } - m_rtt->SentSeq (seq, sz); // notify the RTT + + // update the history of sequence numbers used to calculate the RTT + if (isRetransmission == false) + { // This is the next expected one, just log at end + m_history.push_back (RttHistory (seq, sz, Simulator::Now () )); + } + else + { // This is a retransmit, find in list and mark as re-tx + for (RttHistory_t::iterator i = m_history.begin (); i != m_history.end (); ++i) + { + if ((seq >= i->seq) && (seq < (i->seq + SequenceNumber32 (i->count)))) + { // Found it + i->retx = true; + i->count = ((seq + SequenceNumber32 (sz)) - i->seq); // And update count in hist + break; + } + } + } + // Notify the application of the data being sent unless this is a retransmit if (seq == m_nextTxSequence) { @@ -2155,27 +2199,46 @@ void TcpSocketBase::EstimateRtt (const TcpHeader& tcpHeader) { - Time nextRtt; + SequenceNumber32 ackSeq = tcpHeader.GetAckNumber(); + Time m = Time (0.0); - if (m_timestampEnabled) + // An ack has been received, calculate rtt and log this measurement + // Note we use a linear search (O(n)) for this since for the common + // case the ack'ed packet will be at the head of the list + if (!m_history.empty ()) { - nextRtt = TcpOptionTS::ElapsedTimeFromTsValue (m_lastEchoedTime); - } - else - { - // Use m_rtt for the estimation. Note, RTT of duplicated acknowledgement - // (which should be ignored) is handled by m_rtt. - nextRtt = m_rtt->EstimateRttFromSeq (tcpHeader.GetAckNumber () ); + RttHistory& h = m_history.front (); + if (!h.retx && ackSeq >= (h.seq + SequenceNumber32 (h.count))) + { // Ok to use this sample + if (m_timestampEnabled && tcpHeader.HasOption (TcpOption::TS)) + { + Ptr ts; + ts = DynamicCast (tcpHeader.GetOption (TcpOption::TS)); + m = TcpOptionTS::ElapsedTimeFromTsValue (ts->GetEcho ()); + } + else + { + m = Simulator::Now () - h.time; // Elapsed time + } + } } - //nextRtt will be zero for dup acks. Don't want to update lastRtt in that case - //but still needed to do list clearing that is done in EstimateRttFromSeq. - if(nextRtt != Time (0)) - { - m_lastRtt = nextRtt; - NS_LOG_FUNCTION(this << m_lastRtt); - } - + // Now delete all ack history with seq <= ack + while(!m_history.empty ()) + { + RttHistory& h = m_history.front (); + if ((h.seq + SequenceNumber32 (h.count)) > ackSeq) break; // Done removing + m_history.pop_front (); // Remove + } + + if (!m.IsZero ()) + { + m_rtt->Measurement (m); // Log the measurement + // RFC 6298, clause 2.4 + m_rto = Max (m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4), Time::FromDouble (1, Time::S)); + m_lastRtt = m_rtt->GetEstimate (); + NS_LOG_FUNCTION(this << m_lastRtt); + } } // Called by the ReceivedAck() when new ACK received and by ProcessSynRcvd() @@ -2191,8 +2254,10 @@ NS_LOG_LOGIC (this << " Cancelled ReTxTimeout event which was set to expire at " << (Simulator::Now () + Simulator::GetDelayLeft (m_retxEvent)).GetSeconds ()); m_retxEvent.Cancel (); - // On recieving a "New" ack we restart retransmission timer .. RFC 2988 - m_rto = m_rtt->RetransmitTimeout (); + // On receiving a "New" ack we restart retransmission timer .. RFC 6298 + // RFC 6298, clause 2.4 + m_rto = Max (m_rtt->GetEstimate () + Max (m_clockGranularity, m_rtt->GetVariation ()*4), Time::FromDouble (1, Time::S)); + NS_LOG_LOGIC (this << " Schedule ReTxTimeout at time " << Simulator::Now ().GetSeconds () << " to expire at time " << (Simulator::Now () + m_rto.Get ()).GetSeconds ()); @@ -2320,7 +2385,6 @@ TcpSocketBase::Retransmit () { m_nextTxSequence = m_txBuffer.HeadSequence (); // Start from highest Ack - m_rtt->IncreaseMultiplier (); // Double the timeout value for next retx timer m_dupAckCount = 0; DoRetransmit (); // Retransmit the packet } @@ -2526,6 +2590,7 @@ } m_timestampEnabled = false; + if (header.HasOption (TcpOption::TS)) { m_timestampEnabled = true; @@ -2622,10 +2687,9 @@ Ptr ts = DynamicCast (option); m_timestampToEcho = ts->GetTimestamp (); - m_lastEchoedTime = ts->GetEcho (); NS_LOG_INFO (m_node->GetId () << " Got timestamp=" << - m_timestampToEcho << " and Echo=" << m_lastEchoedTime); + m_timestampToEcho << " and Echo=" << ts->GetEcho ()); } void @@ -2643,4 +2707,41 @@ option->GetTimestamp () << " echo=" << m_timestampToEcho); } +void +TcpSocketBase::SetMinRto (Time minRto) +{ + NS_LOG_FUNCTION (this << minRto); + m_minRto = minRto; +} + +Time +TcpSocketBase::GetMinRto (void) const +{ + return m_minRto; +} + +void +TcpSocketBase::SetClockGranularity (Time clockGranularity) +{ + NS_LOG_FUNCTION (this << clockGranularity); + m_clockGranularity = clockGranularity; +} + +Time +TcpSocketBase::GetClockGranularity (void) const +{ + return m_clockGranularity; +} + +//RttHistory methods +RttHistory::RttHistory (SequenceNumber32 s, uint32_t c, Time t) + : seq (s), count (c), time (t), retx (false) +{ +} + +RttHistory::RttHistory (const RttHistory& h) + : seq (h.seq), count (h.count), time (h.time), retx (h.retx) +{ +} + } // namespace ns3 diff --git a/src/internet/model/tcp-socket-base.h b/src/internet/model/tcp-socket-base.h --- a/src/internet/model/tcp-socket-base.h +++ b/src/internet/model/tcp-socket-base.h @@ -47,6 +47,35 @@ class TcpHeader; /** + * \ingroup tcp + * + * \brief Helper class to store RTT measurements + */ +class RttHistory { +public: + /** + * \brief Constructor - builds an RttHistory with the given parameters + * \param s First sequence number in packet sent + * \param c Number of bytes sent + * \param t Time this one was sent + */ + RttHistory (SequenceNumber32 s, uint32_t c, Time t); + /** + * \brief Copy constructor + * \param h the object to copy + */ + RttHistory (const RttHistory& h); // Copy constructor +public: + SequenceNumber32 seq; //!< First sequence number in packet sent + uint32_t count; //!< Number of bytes sent + Time time; //!< Time this one was sent + bool retx; //!< True if this has been retransmitted +}; + +/// Container for RttHistory objects +typedef std::deque RttHistory_t; + +/** * \ingroup socket * \ingroup tcp * @@ -101,6 +130,31 @@ */ virtual void SetRtt (Ptr rtt); + /** + * \brief Sets the Minimum RTO. + * \param minRto The minimum RTO. + */ + void SetMinRto (Time minRto); + + /** + * \brief Get the Minimum RTO. + * \return The minimum RTO. + */ + Time GetMinRto (void) const; + + /** + * \brief Sets the Clock Granularity (used in RTO calcs). + * \param clockGranularity The Clock Granularity + */ + void SetClockGranularity (Time clockGranularity); + + /** + * \brief Get the Clock Granularity (used in RTO calcs). + * \return The Clock Granularity. + */ + Time GetClockGranularity (void) const; + + // Necessary implementations of null functions from ns3::Socket virtual enum SocketErrno GetErrno (void) const; // returns m_errno virtual enum SocketType GetSocketType (void) const; // returns socket type @@ -624,10 +678,13 @@ uint32_t m_cnCount; //!< Count of remaining connection retries uint32_t m_cnRetries; //!< Number of connection retries before giving up TracedValue