1 files changed, 173 insertions, 0 deletions
diff --git a/chromium/net/quic/congestion_control/inter_arrival_overuse_detector.h b/chromium/net/quic/congestion_control/inter_arrival_overuse_detector.h
new file mode 100644
index 00000000000..185236279bb
--- /dev/null
+++ b/chromium/net/quic/congestion_control/inter_arrival_overuse_detector.h
@@ -0,0 +1,173 @@
+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// This class is a helper class to the inter arrival congestion control. It
+// provide a signal to the inter arrival congestion control of the estimated
+// state of our transport channel. The estimate is based on the inter arrival
+// time of the received packets relative to the time those packets were sent;
+// we can estimate the build up of buffers on the network before packets are
+// lost.
+//
+// Note: this class is not thread-safe.
+
+#ifndef NET_QUIC_CONGESTION_CONTROL_INTER_ARRIVAL_OVERUSE_DETECTOR_H_
+#define NET_QUIC_CONGESTION_CONTROL_INTER_ARRIVAL_OVERUSE_DETECTOR_H_
+
+#include "base/basictypes.h"
+#include "net/base/net_export.h"
+#include "net/quic/quic_protocol.h"
+#include "net/quic/quic_time.h"
+
+namespace net {
+
+enum NET_EXPORT_PRIVATE RateControlRegion {
+  kRateControlRegionUnknown = 0,
+  kRateControlRegionUnderMax = 1,
+  kRateControlRegionNearMax = 2
+};
+
+// Note: Order is important.
+enum NET_EXPORT_PRIVATE BandwidthUsage {
+  kBandwidthSteady = 0,
+  kBandwidthUnderUsing = 1,
+  kBandwidthDraining = 2,
+  kBandwidthOverUsing = 3,
+};
+
+//  Normal state transition diagram
+//
+//         kBandwidthUnderUsing
+//                  |
+//                  |
+//           kBandwidthSteady
+//             |          ^
+//             |          |
+//   kBandwidthOverUsing  |
+//             |          |
+//             |          |
+//          kBandwidthDraining
+//
+//  The above transitions is in normal operation, with extreme values we don't
+//  enforce the state transitions, hence you could in extreme scenarios go
+//  between any states.
+//
+//  kBandwidthSteady       When the packets arrive in the same pace as we sent
+//                         them. In this state we can increase our send pace.
+//
+//  kBandwidthOverUsing    When the packets arrive slower than the pace we sent
+//                         them. In this state we should decrease our send pace.
+//                         When we enter into this state we will also get an
+//                         estimate on how much delay we have built up. The
+//                         reduction in send pace should be chosen to drain the
+//                         built up delay within reasonable time.
+//
+//  kBandwidthUnderUsing   When the packets arrive faster than the pace we sent
+//                         them. In this state another stream disappeared from
+//                         a shared link leaving us more available bandwidth.
+//                         In this state we should hold our pace to make sure we
+//                         fully drain the buffers before we start increasing
+//                         our send rate. We do this to avoid operating with
+//                         semi-full buffers.
+//
+//  kBandwidthDraining     We can only be in this state after we have been in a
+//                         overuse state. In this state we should hold our pace
+//                         to make sure we fully drain the buffers before we
+//                         start increasing our send rate. We do this to avoid
+//                         operating with semi-full buffers.
+
+class NET_EXPORT_PRIVATE InterArrivalOveruseDetector {
+ public:
+  InterArrivalOveruseDetector();
+
+  // Update the statistics with the received delta times, call for every
+  // received delta time. This function assumes that there is no re-orderings.
+  // If multiple packets are sent at the same time (identical send_time)
+  // last_of_send_time should be set to false for all but the last calls to
+  // this function. If there is only one packet sent at a given time
+  // last_of_send_time must be true.
+  // received_delta is the time difference between receiving this packet and the
+  // previously received packet.
+  void OnAcknowledgedPacket(QuicPacketSequenceNumber sequence_number,
+                            QuicTime send_time,
+                            bool last_of_send_time,
+                            QuicTime receive_time);
+
+  // Get the current estimated state and update the estimated congestion delay.
+  // |estimated_congestion_delay| will be updated with the estimated built up
+  // buffer delay; it must not be NULL as it will be updated with the estimate.
+  // Note 1: estimated_buffer_delay will only be valid when kBandwidthOverUsing
+  //         is returned.
+  // Note 2: it's assumed that the pacer lower its send pace to drain the
+  //         built up buffer within reasonable time. The pacer should use the
+  //         estimated_buffer_delay as a guidance on how much to back off.
+  // Note 3: The absolute value of estimated_congestion_delay is less reliable
+  //         than the state itself. It is also biased to low since we can't know
+  //         how full the buffers are when the flow starts.
+  BandwidthUsage GetState(QuicTime::Delta* estimated_congestion_delay);
+
+ private:
+  struct PacketGroup {
+    PacketGroup()
+        : send_time(QuicTime::Zero()),
+          last_receive_time(QuicTime::Zero()) {
+    }
+    QuicTime send_time;
+    QuicTime last_receive_time;
+  };
+
+  // Update the statistics with the absolute receive time relative to the
+  // absolute send time.
+  void UpdateSendReceiveTimeOffset(QuicTime::Delta offset);
+
+  // Update the filter with this new data point.
+  void UpdateFilter(QuicTime::Delta received_delta,
+                    QuicTime::Delta sent_delta);
+
+  // Update the estimate with this residual.
+  void UpdateDeltaEstimate(QuicTime::Delta residual);
+
+  // Estimate the state based on the slope of the changes.
+  void DetectSlope(int64 sigma_delta);
+
+  // Estimate the state based on the accumulated drift of the changes.
+  void DetectDrift(int64 sigma_delta);
+
+  // Current grouping of packets that were sent at the same time.
+  PacketGroup current_packet_group_;
+  // Grouping of packets that were sent at the same time, just before the
+  // current_packet_group_ above.
+  PacketGroup previous_packet_group_;
+  // Sequence number of the last acknowledged packet.
+  QuicPacketSequenceNumber last_sequence_number_;
+  // Number of received delta times with unique send time.
+  int num_of_deltas_;
+  // Estimated accumulation of received delta times.
+  // Note: Can be negative and can drift over time which is why we bias it
+  // towards 0 and reset it given some triggers.
+  QuicTime::Delta accumulated_deltas_;
+  // Current running mean of our received delta times.
+  int delta_mean_;
+  // Current running variance of our received delta times.
+  int64 delta_variance_;
+  // Number of overuse signals currently triggered in this state.
+  // Note: negative represent underuse.
+  int delta_overuse_counter_;
+  // State estimated by the delta times.
+  BandwidthUsage delta_estimate_;
+  // Number of overuse signals currently triggered in this state.
+  // Note: negative represent underuse.
+  int slope_overuse_counter_;
+  // State estimated by the slope of the delta times.
+  BandwidthUsage slope_estimate_;
+  // Lowest offset between send and receive time ever received in this session.
+  QuicTime::Delta send_receive_offset_;
+  // Last received time difference between our normalized send and receive time.
+  QuicTime::Delta estimated_congestion_delay_;
+
+  DISALLOW_COPY_AND_ASSIGN(InterArrivalOveruseDetector);
+};
+
+}  // namespace net
+
+#endif  // NET_QUIC_CONGESTION_CONTROL_INTER_ARRIVAL_OVERUSE_DETECTOR_H_