Merge branch 'congestion' of https://github.com/CendioOssman/tigervnc

11 files changed, 650 insertions, 219 deletions

diff --git a/common/rfb/CMakeLists.txt b/common/rfb/CMakeLists.txt
index 5047e5e7..62ef401c 100644
--- a/common/rfb/CMakeLists.txt
+++ b/common/rfb/CMakeLists.txt
@@ -2,6 +2,7 @@ include_directories(${CMAKE_SOURCE_DIR}/common ${JPEG_INCLUDE_DIR})
 
 set(RFB_SOURCES
   Blacklist.cxx
+  Congestion.cxx
   CConnection.cxx
   CMsgHandler.cxx
   CMsgReader.cxx
diff --git a/common/rfb/Congestion.cxx b/common/rfb/Congestion.cxx
new file mode 100644
index 00000000..a2f7a256
--- /dev/null
+++ b/common/rfb/Congestion.cxx
@@ -0,0 +1,470 @@
+/* Copyright 2009-2015 Pierre Ossman for Cendio AB
+ * 
+ * This is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This software is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this software; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,
+ * USA.
+ */
+
+/*
+ * This code implements congestion control in the same way as TCP in
+ * order to avoid excessive latency in the transport. This is needed
+ * because "buffer bloat" is unfortunately still a very real problem.
+ *
+ * The basic principle is TCP Congestion Control (RFC 5618), with the
+ * addition of using the TCP Vegas algorithm. The reason we use Vegas
+ * is that we run on top of a reliable transport so we need a latency
+ * based algorithm rather than a loss based one. There is also a lot of
+ * interpolation of values. This is because we have rather horrible
+ * granularity in our measurements.
+ *
+ * We use a simplistic form of slow start in order to ramp up quickly
+ * from an idle state. We do not have any persistent threshold though
+ * as we have too much noise for it to be reliable.
+ */
+
+#include <assert.h>
+#include <sys/time.h>
+
+#ifdef __linux__
+#include <sys/ioctl.h>
+#include <sys/socket.h>
+#include <netinet/in.h>
+#include <netinet/tcp.h>
+#include <linux/sockios.h>
+#endif
+
+#include <rfb/Congestion.h>
+#include <rfb/LogWriter.h>
+#include <rfb/util.h>
+
+// Debug output on what the congestion control is up to
+#undef CONGESTION_DEBUG
+
+// Dump socket congestion window debug trace to disk
+#undef CONGESTION_TRACE
+
+using namespace rfb;
+
+// This window should get us going fairly fast on a decent bandwidth network.
+// If it's too high, it will rapidly be reduced and stay low.
+static const unsigned INITIAL_WINDOW = 16384;
+
+// TCP's minimal window is 3*MSS. But since we don't know the MSS, we
+// make a guess at 4 KiB (it's probably a bit higher).
+static const unsigned MINIMUM_WINDOW = 4096;
+
+// The current default maximum window for Linux (4 MiB). Should be a good
+// limit for now...
+static const unsigned MAXIMUM_WINDOW = 4194304;
+
+static LogWriter vlog("Congestion");
+
+Congestion::Congestion() :
+    lastPosition(0), extraBuffer(0),
+    baseRTT(-1), congWindow(INITIAL_WINDOW), inSlowStart(true),
+    measurements(0), minRTT(-1), minCongestedRTT(-1)
+{
+  gettimeofday(&lastUpdate, NULL);
+  gettimeofday(&lastSent, NULL);
+  memset(&lastPong, 0, sizeof(lastPong));
+  gettimeofday(&lastPongArrival, NULL);
+  gettimeofday(&lastAdjustment, NULL);
+}
+
+Congestion::~Congestion()
+{
+}
+
+void Congestion::updatePosition(unsigned pos)
+{
+  struct timeval now;
+  unsigned delta, consumed;
+
+  gettimeofday(&now, NULL);
+
+  delta = pos - lastPosition;
+  if ((delta > 0) || (extraBuffer > 0))
+    lastSent = now;
+
+  // Idle for too long?
+  // We use a very crude RTO calculation in order to keep things simple
+  // FIXME: should implement RFC 2861
+  if (msBetween(&lastSent, &now) > __rfbmax(baseRTT*2, 100)) {
+
+#ifdef CONGESTION_DEBUG
+    vlog.debug("Connection idle for %d ms, resetting congestion control",
+               msBetween(&lastSent, &now));
+#endif
+
+    // Close congestion window and redo wire latency measurement
+    congWindow = __rfbmin(INITIAL_WINDOW, congWindow);
+    baseRTT = -1;
+    measurements = 0;
+    gettimeofday(&lastAdjustment, NULL);
+    minRTT = minCongestedRTT = -1;
+    inSlowStart = true;
+  }
+
+  // Commonly we will be in a state of overbuffering. We need to
+  // estimate the extra delay that causes so we can separate it from
+  // the delay caused by an incorrect congestion window.
+  // (we cannot do this until we have a RTT measurement though)
+  if (baseRTT != (unsigned)-1) {
+    extraBuffer += delta;
+    consumed = msBetween(&lastUpdate, &now) * congWindow / baseRTT;
+    if (extraBuffer < consumed)
+      extraBuffer = 0;
+    else
+      extraBuffer -= consumed;
+  }
+
+  lastPosition = pos;
+  lastUpdate = now;
+}
+
+void Congestion::sentPing()
+{
+  struct RTTInfo rttInfo;
+
+  memset(&rttInfo, 0, sizeof(struct RTTInfo));
+
+  gettimeofday(&rttInfo.tv, NULL);
+  rttInfo.pos = lastPosition;
+  rttInfo.extra = getExtraBuffer();
+  rttInfo.congested = isCongested();
+
+  pings.push_back(rttInfo);
+}
+
+void Congestion::gotPong()
+{
+  struct timeval now;
+  struct RTTInfo rttInfo;
+  unsigned rtt, delay;
+
+  if (pings.empty())
+    return;
+
+  gettimeofday(&now, NULL);
+
+  rttInfo = pings.front();
+  pings.pop_front();
+
+  lastPong = rttInfo;
+  lastPongArrival = now;
+
+  rtt = msBetween(&rttInfo.tv, &now);
+  if (rtt < 1)
+    rtt = 1;
+
+  // Try to estimate wire latency by tracking lowest seen latency
+  if (rtt < baseRTT)
+    baseRTT = rtt;
+
+  // Pings sent before the last adjustment aren't interesting as they
+  // aren't a measurement of the current congestion window
+  if (isBefore(&rttInfo.tv, &lastAdjustment))
+    return;
+
+  // Estimate added delay because of overtaxed buffers (see above)
+  delay = rttInfo.extra * baseRTT / congWindow;
+  if (delay < rtt)
+    rtt -= delay;
+  else
+    rtt = 1;
+
+  // A latency less than the wire latency means that we've
+  // understimated the congestion window. We can't really determine
+  // how much, so pretend that we got no buffer latency at all.
+  if (rtt < baseRTT)
+    rtt = baseRTT;
+
+  // Record the minimum seen delay (hopefully ignores jitter) and let
+  // the congestion control do its thing.
+  //
+  // Note: We are delay based rather than loss based, which means we
+  //       need to look at pongs even if they weren't limited by the
+  //       current window ("congested"). Otherwise we will fail to
+  //       detect increasing congestion until the application exceeds
+  //       the congestion window.
+  if (rtt < minRTT)
+    minRTT = rtt;
+  if (rttInfo.congested) {
+    if (rtt < minCongestedRTT)
+      minCongestedRTT = rtt;
+  }
+
+  measurements++;
+  updateCongestion();
+}
+
+bool Congestion::isCongested()
+{
+  if (getInFlight() < congWindow)
+    return false;
+
+  return true;
+}
+
+int Congestion::getUncongestedETA()
+{
+  unsigned targetAcked;
+
+  const struct RTTInfo* prevPing;
+  unsigned eta, elapsed;
+  unsigned etaNext, delay;
+
+  std::list<struct RTTInfo>::const_iterator iter;
+
+  targetAcked = lastPosition - congWindow;
+
+  // Simple case?
+  if (lastPong.pos > targetAcked)
+    return 0;
+
+  // No measurements yet?
+  if (baseRTT == (unsigned)-1)
+    return -1;
+
+  prevPing = &lastPong;
+  eta = 0;
+  elapsed = msSince(&lastPongArrival);
+
+  // Walk the ping queue and figure out which one we are waiting for to
+  // get to an uncongested state
+
+  for (iter = pings.begin(); ;++iter) {
+    struct RTTInfo curPing;
+
+    // If we aren't waiting for a pong that will clear the congested
+    // state then we have to estimate the final bit by pretending that
+    // we had a ping just after the last position update.
+    if (iter == pings.end()) {
+      curPing.tv = lastUpdate;
+      curPing.pos = lastPosition;
+      curPing.extra = extraBuffer;
+    } else {
+      curPing = *iter;
+    }
+
+    etaNext = msBetween(&prevPing->tv, &curPing.tv);
+    // Compensate for buffering delays
+    delay = curPing.extra * baseRTT / congWindow;
+    etaNext += delay;
+    delay = prevPing->extra * baseRTT / congWindow;
+    if (delay >= etaNext)
+      etaNext = 0;
+    else
+      etaNext -= delay;
+
+    // Found it?
+    if (curPing.pos > targetAcked) {
+      eta += etaNext * (curPing.pos - targetAcked) / (curPing.pos - prevPing->pos);
+      if (elapsed > eta)
+        return 0;
+      else
+        return eta - elapsed;
+    }
+
+    assert(iter != pings.end());
+
+    eta += etaNext;
+    prevPing = &*iter;
+  }
+}
+
+void Congestion::debugTrace(const char* filename, int fd)
+{
+#ifdef CONGESTION_TRACE
+#ifdef __linux__
+  FILE *f;
+  f = fopen(filename, "ab");
+  if (f != NULL) {
+    struct tcp_info info;
+    int buffered;
+    socklen_t len;
+    len = sizeof(info);
+    if ((getsockopt(fd, IPPROTO_TCP,
+                    TCP_INFO, &info, &len) == 0) &&
+        (ioctl(fd, SIOCOUTQ, &buffered) == 0)) {
+      struct timeval now;
+      gettimeofday(&now, NULL);
+      fprintf(f, "%u.%06u,%u,%u,%u,%u\n",
+              (unsigned)now.tv_sec, (unsigned)now.tv_usec,
+              congWindow, info.tcpi_snd_cwnd * info.tcpi_snd_mss,
+              getInFlight(), buffered);
+    }
+    fclose(f);
+  }
+#endif
+#endif
+}
+
+unsigned Congestion::getExtraBuffer()
+{
+  unsigned elapsed;
+  unsigned consumed;
+
+  if (baseRTT == (unsigned)-1)
+    return 0;
+
+  elapsed = msSince(&lastUpdate);
+  consumed = elapsed * congWindow / baseRTT;
+
+  if (consumed >= extraBuffer)
+    return 0;
+  else
+    return extraBuffer - consumed;
+}
+
+unsigned Congestion::getInFlight()
+{
+  struct RTTInfo nextPong;
+  unsigned etaNext, delay, elapsed, acked;
+
+  // Simple case?
+  if (lastPosition == lastPong.pos)
+    return 0;
+
+  // No measurements yet?
+  if (baseRTT == (unsigned)-1) {
+    if (!pings.empty())
+      return lastPosition - pings.front().pos;
+    return 0;
+  }
+
+  // If we aren't waiting for any pong then we have to estimate things
+  // by pretending that we had a ping just after the last position
+  // update.
+  if (pings.empty()) {
+    nextPong.tv = lastUpdate;
+    nextPong.pos = lastPosition;
+    nextPong.extra = extraBuffer;
+  } else {
+    nextPong = pings.front();
+  }
+
+  // First we need to estimate how many bytes have made it through
+  // completely. Look at the next ping that should arrive and figure
+  // out how far behind it should be and interpolate the positions.
+
+  etaNext = msBetween(&lastPong.tv, &nextPong.tv);
+  // Compensate for buffering delays
+  delay = nextPong.extra * baseRTT / congWindow;
+  etaNext += delay;
+  delay = lastPong.extra * baseRTT / congWindow;
+  if (delay >= etaNext)
+    etaNext = 0;
+  else
+    etaNext -= delay;
+
+  elapsed = msSince(&lastPongArrival);
+
+  // The pong should be here any second. Be optimistic and assume
+  // we can already use its value.
+  if (etaNext <= elapsed)
+    acked = nextPong.pos;
+  else {
+    acked = lastPong.pos;
+    acked += (nextPong.pos - lastPong.pos) * elapsed / etaNext;
+  }
+
+  return lastPosition - acked;
+}
+
+void Congestion::updateCongestion()
+{
+  unsigned diff;
+
+  // We want at least three measurements to avoid noise
+  if (measurements < 3)
+    return;
+
+  assert(minRTT >= baseRTT);
+  assert(minCongestedRTT >= baseRTT);
+
+  // The goal is to have a slightly too large congestion window since
+  // a "perfect" one cannot be distinguished from a too small one. This
+  // translates to a goal of a few extra milliseconds of delay.
+
+  diff = minRTT - baseRTT;
+
+  if (diff > __rfbmax(100, baseRTT/2)) {
+    // We have no way of detecting loss, so assume massive latency
+    // spike means packet loss. Adjust the window and go directly
+    // to congestion avoidance.
+#ifdef CONGESTION_DEBUG
+    vlog.debug("Latency spike! Backing off...");
+#endif
+    congWindow = congWindow * baseRTT / minRTT;
+    inSlowStart = false;
+  }
+
+  if (inSlowStart) {
+    // Slow start. Aggressive growth until we see congestion.
+
+    if (diff > 25) {
+      // If we see an increased latency then we assume we've hit the
+      // limit and it's time to leave slow start and switch to
+      // congestion avoidance
+      congWindow = congWindow * baseRTT / minRTT;
+      inSlowStart = false;
+    } else {
+      // It's not safe to increase unless we actually used the entire
+      // congestion window, hence we look at minCongestedRTT and not
+      // minRTT
+
+      diff = minCongestedRTT - baseRTT;
+      if (diff < 25)
+        congWindow *= 2;
+    }
+  } else {
+    // Congestion avoidance (VEGAS)
+
+    if (diff > 50) {
+      // Slightly too fast
+      congWindow -= 4096;
+    } else {
+      // Only the "congested" pongs are checked to see if the
+      // window is too small.
+
+      diff = minCongestedRTT - baseRTT;
+
+      if (diff < 5) {
+        // Way too slow
+        congWindow += 8192;
+      } else if (diff < 25) {
+        // Too slow
+        congWindow += 4096;
+      }
+    }
+  }
+
+  if (congWindow < MINIMUM_WINDOW)
+    congWindow = MINIMUM_WINDOW;
+  if (congWindow > MAXIMUM_WINDOW)
+    congWindow = MAXIMUM_WINDOW;
+
+#ifdef CONGESTION_DEBUG
+  vlog.debug("RTT: %d/%d ms (%d ms), Window: %d KiB, Bandwidth: %g Mbps%s",
+             minRTT, minCongestedRTT, baseRTT, congWindow / 1024,
+             congWindow * 8.0 / baseRTT / 1000.0,
+             inSlowStart ? " (slow start)" : "");
+#endif
+
+  measurements = 0;
+  gettimeofday(&lastAdjustment, NULL);
+  minRTT = minCongestedRTT = -1;
+}
+
diff --git a/common/rfb/Congestion.h b/common/rfb/Congestion.h
new file mode 100644
index 00000000..fd57c22e
--- /dev/null
+++ b/common/rfb/Congestion.h
@@ -0,0 +1,89 @@
+/* Copyright 2009-2015 Pierre Ossman for Cendio AB
+ * 
+ * This is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ * 
+ * This software is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this software; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307,
+ * USA.
+ */
+
+#ifndef __RFB_CONGESTION_H__
+#define __RFB_CONGESTION_H__
+
+#include <list>
+
+namespace rfb {
+  class Congestion {
+  public:
+    Congestion();
+    ~Congestion();
+
+    // updatePosition() registers the current stream position and can
+    // and should be called often.
+    void updatePosition(unsigned pos);
+
+    // sentPing() must be called when a marker is placed on the
+    // outgoing stream. gotPong() must be called when the response for
+    // such a marker is received.
+    void sentPing();
+    void gotPong();
+
+    // isCongested() determines if the transport is currently congested
+    // or if more data can be sent.
+    bool isCongested();
+
+    // getUncongestedETA() returns the number of milliseconds until the
+    // transport is no longer congested. Returns 0 if there is no
+    // congestion, and -1 if it is unknown when the transport will no
+    // longer be congested.
+    int getUncongestedETA();
+
+    // debugTrace() writes the current congestion window, as well as the
+    // congestion window of the underlying TCP layer, to the specified
+    // file
+    void debugTrace(const char* filename, int fd);
+
+  protected:
+    unsigned getExtraBuffer();
+    unsigned getInFlight();
+
+    void updateCongestion();
+
+  private:
+    unsigned lastPosition;
+    unsigned extraBuffer;
+    struct timeval lastUpdate;
+    struct timeval lastSent;
+
+    unsigned baseRTT;
+    unsigned congWindow;
+    bool inSlowStart;
+
+    struct RTTInfo {
+      struct timeval tv;
+      unsigned pos;
+      unsigned extra;
+      bool congested;
+    };
+
+    std::list<struct RTTInfo> pings;
+
+    struct RTTInfo lastPong;
+    struct timeval lastPongArrival;
+
+    int measurements;
+    struct timeval lastAdjustment;
+    unsigned minRTT, minCongestedRTT;
+  };
+}
+
+#endif
diff --git a/common/rfb/ListConnInfo.h b/common/rfb/ListConnInfo.h
index 9e939d1e..c49947da 100644
--- a/common/rfb/ListConnInfo.h
+++ b/common/rfb/ListConnInfo.h
@@ -20,6 +20,10 @@
 #ifndef __RFB_LISTCONNINFO_INCLUDED__
 #define __RFB_LISTCONNINFO_INCLUDED__
 
+#include <list>
+
+#include <rfb/util.h>
+
 namespace rfb {
 
   struct ListConnInfo  {
diff --git a/common/rfb/Timer.cxx b/common/rfb/Timer.cxx
index 71887a0f..7179cd87 100644
--- a/common/rfb/Timer.cxx
+++ b/common/rfb/Timer.cxx
@@ -124,6 +124,9 @@ void Timer::start(int timeoutMs_) {
   gettimeofday(&now, 0);
   stop();
   timeoutMs = timeoutMs_;
+  // The rest of the code assumes non-zero timeout
+  if (timeoutMs <= 0)
+    timeoutMs = 1;
   dueTime = addMillis(now, timeoutMs);
   insertTimer(this);
 }
diff --git a/common/rfb/VNCSConnectionST.cxx b/common/rfb/VNCSConnectionST.cxx
index bd4bc366..e707e492 100644
--- a/common/rfb/VNCSConnectionST.cxx
+++ b/common/rfb/VNCSConnectionST.cxx
@@ -17,28 +17,20 @@
  * USA.
  */
 
-// Debug output on what the congestion control is up to
-#undef CONGESTION_DEBUG
-
-#include <sys/time.h>
-
-#ifdef CONGESTION_DEBUG
-#include <sys/socket.h>
-#include <netinet/in.h>
-#include <netinet/tcp.h>
-#endif
-
 #include <network/TcpSocket.h>
-#include <rfb/VNCSConnectionST.h>
+
+#include <rfb/ComparingUpdateTracker.h>
+#include <rfb/Encoder.h>
+#include <rfb/KeyRemapper.h>
 #include <rfb/LogWriter.h>
 #include <rfb/Security.h>
+#include <rfb/ServerCore.h>
+#include <rfb/SMsgWriter.h>
+#include <rfb/VNCServerST.h>
+#include <rfb/VNCSConnectionST.h>
 #include <rfb/screenTypes.h>
 #include <rfb/fenceTypes.h>
 #include <rfb/ledStates.h>
-#include <rfb/ServerCore.h>
-#include <rfb/ComparingUpdateTracker.h>
-#include <rfb/KeyRemapper.h>
-#include <rfb/Encoder.h>
 #define XK_LATIN1
 #define XK_MISCELLANY
 #define XK_XKB_KEYS
@@ -48,24 +40,6 @@ using namespace rfb;
 
 static LogWriter vlog("VNCSConnST");
 
-// This window should get us going fairly fast on a decent bandwidth network.
-// If it's too high, it will rapidly be reduced and stay low.
-static const unsigned INITIAL_WINDOW = 16384;
-
-// TCP's minimal window is 3*MSS. But since we don't know the MSS, we
-// make a guess at 4 KiB (it's probably a bit higher).
-static const unsigned MINIMUM_WINDOW = 4096;
-
-// The current default maximum window for Linux (4 MiB). Should be a good
-// limit for now...
-static const unsigned MAXIMUM_WINDOW = 4194304;
-
-struct RTTInfo {
-  struct timeval tv;
-  int offset;
-  unsigned inFlight;
-};
-
 static Cursor emptyCursor(0, 0, Point(0, 0), NULL);
 
 VNCSConnectionST::VNCSConnectionST(VNCServerST* server_, network::Socket *s,
@@ -73,10 +47,7 @@ VNCSConnectionST::VNCSConnectionST(VNCServerST* server_, network::Socket *s,
   : sock(s), reverseConnection(reverse),
     inProcessMessages(false),
     pendingSyncFence(false), syncFence(false), fenceFlags(0),
-    fenceDataLen(0), fenceData(NULL),
-    baseRTT(-1), congWindow(0), ackedOffset(0), sentOffset(0),
-    minRTT(-1), seenCongestion(false),
-    pingCounter(0), congestionTimer(this),
+    fenceDataLen(0), fenceData(NULL), congestionTimer(this),
     server(server_), updates(false),
     updateRenderedCursor(false), removeRenderedCursor(false),
     continuousUpdates(false), encodeManager(this), pointerEventTime(0),
@@ -457,10 +428,6 @@ void VNCSConnectionST::authSuccess()
   // - Mark the entire display as "dirty"
   updates.add_changed(server->pb->getRect());
   startTime = time(0);
-
-  // - Bootstrap the congestion control
-  ackedOffset = sock->outStream().length();
-  congWindow = INITIAL_WINDOW;
 }
 
 void VNCSConnectionST::queryConnection(const char* userName)
@@ -769,6 +736,8 @@ void VNCSConnectionST::setDesktopSize(int fb_width, int fb_height,
 
 void VNCSConnectionST::fence(rdr::U32 flags, unsigned len, const char data[])
 {
+  rdr::U8 type;
+
   if (flags & fenceFlagRequest) {
     if (flags & fenceFlagSyncNext) {
       pendingSyncFence = true;
@@ -792,18 +761,20 @@ void VNCSConnectionST::fence(rdr::U32 flags, unsigned len, const char data[])
     return;
   }
 
-  struct RTTInfo rttInfo;
+  if (len < 1)
+    vlog.error("Fence response of unexpected size received");
+
+  type = data[0];
 
-  switch (len) {
+  switch (type) {
   case 0:
     // Initial dummy fence;
     break;
-  case sizeof(struct RTTInfo):
-    memcpy(&rttInfo, data, sizeof(struct RTTInfo));
-    handleRTTPong(rttInfo);
+  case 1:
+    congestion.gotPong();
     break;
   default:
-    vlog.error("Fence response of unexpected size received");
+    vlog.error("Fence response of unexpected type received");
   }
 }
 
@@ -842,7 +813,8 @@ void VNCSConnectionST::supportsLocalCursor()
 
 void VNCSConnectionST::supportsFence()
 {
-  writer()->writeFence(fenceFlagRequest, 0, NULL);
+  char type = 0;
+  writer()->writeFence(fenceFlagRequest, sizeof(type), &type);
 }
 
 void VNCSConnectionST::supportsContinuousUpdates()
@@ -865,7 +837,7 @@ bool VNCSConnectionST::handleTimeout(Timer* t)
 {
   try {
     if (t == &congestionTimer)
-      updateCongestion();
+      writeFramebufferUpdate();
   } catch (rdr::Exception& e) {
     close(e.str());
   }
@@ -889,182 +861,54 @@ bool VNCSConnectionST::isShiftPressed()
 
 void VNCSConnectionST::writeRTTPing()
 {
-  struct RTTInfo rttInfo;
+  char type;
 
   if (!cp.supportsFence)
     return;
 
-  memset(&rttInfo, 0, sizeof(struct RTTInfo));
-
-  gettimeofday(&rttInfo.tv, NULL);
-  rttInfo.offset = sock->outStream().length();
-  rttInfo.inFlight = rttInfo.offset - ackedOffset;
+  congestion.updatePosition(sock->outStream().length());
 
   // We need to make sure any old update are already processed by the
   // time we get the response back. This allows us to reliably throttle
   // back on client overload, as well as network overload.
+  type = 1;
   writer()->writeFence(fenceFlagRequest | fenceFlagBlockBefore,
-                       sizeof(struct RTTInfo), (const char*)&rttInfo);
-
-  pingCounter++;
-
-  sentOffset = rttInfo.offset;
-
-  // Let some data flow before we adjust the settings
-  if (!congestionTimer.isStarted())
-    congestionTimer.start(__rfbmin(baseRTT * 2, 100));
-}
-
-void VNCSConnectionST::handleRTTPong(const struct RTTInfo &rttInfo)
-{
-  unsigned rtt, delay;
-
-  pingCounter--;
-
-  rtt = msSince(&rttInfo.tv);
-  if (rtt < 1)
-    rtt = 1;
-
-  ackedOffset = rttInfo.offset;
-
-  // Try to estimate wire latency by tracking lowest seen latency
-  if (rtt < baseRTT)
-    baseRTT = rtt;
-
-  if (rttInfo.inFlight > congWindow) {
-    seenCongestion = true;
-
-    // Estimate added delay because of overtaxed buffers
-    delay = (rttInfo.inFlight - congWindow) * baseRTT / congWindow;
-
-    if (delay < rtt)
-      rtt -= delay;
-    else
-      rtt = 1;
-
-    // If we underestimate the congestion window, then we'll get a latency
-    // that's less than the wire latency, which will confuse other portions
-    // of the code.
-    if (rtt < baseRTT)
-      rtt = baseRTT;
-  }
+                       sizeof(type), &type);
 
-  // We only keep track of the minimum latency seen (for a given interval)
-  // on the basis that we want to avoid continuous buffer issue, but don't
-  // mind (or even approve of) bursts.
-  if (rtt < minRTT)
-    minRTT = rtt;
+  congestion.sentPing();
 }
 
 bool VNCSConnectionST::isCongested()
 {
-  int offset;
+  unsigned eta;
+
+  congestionTimer.stop();
 
   // Stuff still waiting in the send buffer?
   sock->outStream().flush();
+  congestion.debugTrace("congestion-trace.csv", sock->getFd());
   if (sock->outStream().bufferUsage() > 0)
     return true;
 
   if (!cp.supportsFence)
     return false;
 
-  // Idle for too long? (and no data on the wire)
-  //
-  // FIXME: This should really just be one baseRTT, but we're getting
-  //        problems with triggering the idle timeout on each update.
-  //        Maybe we need to use a moving average for the wire latency
-  //        instead of baseRTT.
-  if ((sentOffset == ackedOffset) &&
-      (sock->outStream().getIdleTime() > 2 * baseRTT)) {
-
-#ifdef CONGESTION_DEBUG
-    if (congWindow > INITIAL_WINDOW)
-      fprintf(stderr, "Reverting to initial window (%d KiB) after %d ms\n",
-              INITIAL_WINDOW / 1024, sock->outStream().getIdleTime());
-#endif
-
-    // Close congestion window and allow a transfer
-    // FIXME: Reset baseRTT like Linux Vegas?
-    congWindow = __rfbmin(INITIAL_WINDOW, congWindow);
-
-    return false;
-  }
-
-  offset = sock->outStream().length();
-
-  // FIXME: Should we compensate for non-update data?
-  //        (i.e. use sentOffset instead of offset)
-  if ((offset - ackedOffset) < congWindow)
+  congestion.updatePosition(sock->outStream().length());
+  if (!congestion.isCongested())
     return false;
 
-  // If we just have one outstanding "ping", that means the client has
-  // started receiving our update. In order to not regress compared to
-  // before we had congestion avoidance, we allow another update here.
-  // This could further clog up the tubes, but congestion control isn't
-  // really working properly right now anyway as the wire would otherwise
-  // be idle for at least RTT/2.
-  if (pingCounter == 1)
-    return false;
+  eta = congestion.getUncongestedETA();
+  if (eta >= 0)
+    congestionTimer.start(eta);
 
   return true;
 }
 
 
-void VNCSConnectionST::updateCongestion()
-{
-  unsigned diff;
-
-  if (!seenCongestion)
-    return;
-
-  diff = minRTT - baseRTT;
-
-  if (diff > __rfbmin(100, baseRTT)) {
-    // Way too fast
-    congWindow = congWindow * baseRTT / minRTT;
-  } else if (diff > __rfbmin(50, baseRTT/2)) {
-    // Slightly too fast
-    congWindow -= 4096;
-  } else if (diff < 5) {
-    // Way too slow
-    congWindow += 8192;
-  } else if (diff < 25) {
-    // Too slow
-    congWindow += 4096;
-  }
-
-  if (congWindow < MINIMUM_WINDOW)
-    congWindow = MINIMUM_WINDOW;
-  if (congWindow > MAXIMUM_WINDOW)
-    congWindow = MAXIMUM_WINDOW;
-
-#ifdef CONGESTION_DEBUG
-  fprintf(stderr, "RTT: %d ms (%d ms), Window: %d KiB, Bandwidth: %g Mbps\n",
-          minRTT, baseRTT, congWindow / 1024,
-          congWindow * 8.0 / baseRTT / 1000.0);
-
-#ifdef TCP_INFO
-  struct tcp_info tcp_info;
-  socklen_t tcp_info_length;
-
-  tcp_info_length = sizeof(tcp_info);
-  if (getsockopt(sock->getFd(), SOL_TCP, TCP_INFO,
-                 (void *)&tcp_info, &tcp_info_length) == 0) {
-    fprintf(stderr, "Socket: RTT: %d ms (+/- %d ms) Window %d KiB\n",
-            tcp_info.tcpi_rtt / 1000, tcp_info.tcpi_rttvar / 1000,
-            tcp_info.tcpi_snd_mss * tcp_info.tcpi_snd_cwnd / 1024);
-  }
-#endif
-
-#endif
-
-  minRTT = -1;
-  seenCongestion = false;
-}
-
-
 void VNCSConnectionST::writeFramebufferUpdate()
 {
+  congestion.updatePosition(sock->outStream().length());
+
   // We're in the middle of processing a command that's supposed to be
   // synchronised. Allowing an update to slip out right now might violate
   // that synchronisation.
@@ -1101,6 +945,8 @@ void VNCSConnectionST::writeFramebufferUpdate()
   writeDataUpdate();
 
   sock->cork(false);
+
+  congestion.updatePosition(sock->outStream().length());
 }
 
 void VNCSConnectionST::writeNoDataUpdate()
diff --git a/common/rfb/VNCSConnectionST.h b/common/rfb/VNCSConnectionST.h
index 8d6a7bc6..2f075a64 100644
--- a/common/rfb/VNCSConnectionST.h
+++ b/common/rfb/VNCSConnectionST.h
@@ -28,15 +28,14 @@
 #define __RFB_VNCSCONNECTIONST_H__
 
 #include <map>
+
+#include <rfb/Congestion.h>
+#include <rfb/EncodeManager.h>
 #include <rfb/SConnection.h>
-#include <rfb/SMsgWriter.h>
-#include <rfb/VNCServerST.h>
 #include <rfb/Timer.h>
-#include <rfb/EncodeManager.h>
-
-struct RTTInfo;
 
 namespace rfb {
+  class VNCServerST;
 
   class VNCSConnectionST : public SConnection,
                            public Timer::Callback {
@@ -164,9 +163,7 @@ namespace rfb {
 
     // Congestion control
     void writeRTTPing();
-    void handleRTTPong(const struct RTTInfo &rttInfo);
     bool isCongested();
-    void updateCongestion();
 
     // writeFramebufferUpdate() attempts to write a framebuffer update to the
     // client.
@@ -192,13 +189,7 @@ namespace rfb {
     unsigned fenceDataLen;
     char *fenceData;
 
-    unsigned baseRTT;
-    unsigned congWindow;
-    unsigned ackedOffset, sentOffset;
-
-    unsigned minRTT;
-    bool seenCongestion;
-    unsigned pingCounter;
+    Congestion congestion;
     Timer congestionTimer;
 
     VNCServerST* server;
diff --git a/common/rfb/VNCServerST.cxx b/common/rfb/VNCServerST.cxx
index f27099f0..fc649fa1 100644
--- a/common/rfb/VNCServerST.cxx
+++ b/common/rfb/VNCServerST.cxx
@@ -51,12 +51,13 @@
 #include <assert.h>
 #include <stdlib.h>
 
+#include <rfb/ComparingUpdateTracker.h>
+#include <rfb/KeyRemapper.h>
+#include <rfb/ListConnInfo.h>
+#include <rfb/Security.h>
 #include <rfb/ServerCore.h>
 #include <rfb/VNCServerST.h>
 #include <rfb/VNCSConnectionST.h>
-#include <rfb/ComparingUpdateTracker.h>
-#include <rfb/Security.h>
-#include <rfb/KeyRemapper.h>
 #include <rfb/util.h>
 #include <rfb/ledStates.h>
 
diff --git a/common/rfb/VNCServerST.h b/common/rfb/VNCServerST.h
index 3a563703..e00a1f7e 100644
--- a/common/rfb/VNCServerST.h
+++ b/common/rfb/VNCServerST.h
@@ -28,19 +28,18 @@
 
 #include <rfb/SDesktop.h>
 #include <rfb/VNCServer.h>
-#include <rfb/Configuration.h>
 #include <rfb/LogWriter.h>
 #include <rfb/Blacklist.h>
 #include <rfb/Cursor.h>
 #include <rfb/Timer.h>
 #include <network/Socket.h>
-#include <rfb/ListConnInfo.h>
 #include <rfb/ScreenSet.h>
 
 namespace rfb {
 
   class VNCSConnectionST;
   class ComparingUpdateTracker;
+  class ListConnInfo;
   class PixelBuffer;
   class KeyRemapper;
 
diff --git a/common/rfb/util.cxx b/common/rfb/util.cxx
index cfec2ef3..4fd84eb6 100644
--- a/common/rfb/util.cxx
+++ b/common/rfb/util.cxx
@@ -121,19 +121,38 @@ namespace rfb {
     dest[src ? destlen-1 : 0] = 0;
   }
 
+  unsigned msBetween(const struct timeval *first,
+                     const struct timeval *second)
+  {
+    unsigned diff;
+
+    diff = (second->tv_sec - first->tv_sec) * 1000;
+
+    diff += second->tv_usec / 1000;
+    diff -= first->tv_usec / 1000;
+
+    return diff;
+  }
+
   unsigned msSince(const struct timeval *then)
   {
     struct timeval now;
-    unsigned diff;
 
     gettimeofday(&now, NULL);
 
-    diff = (now.tv_sec - then->tv_sec) * 1000;
-
-    diff += now.tv_usec / 1000;
-    diff -= then->tv_usec / 1000;
+    return msBetween(then, &now);
+  }
 
-    return diff;
+  bool isBefore(const struct timeval *first,
+                const struct timeval *second)
+  {
+    if (first->tv_sec < second->tv_sec)
+      return true;
+    if (first->tv_sec > second->tv_sec)
+      return false;
+    if (first->tv_usec < second->tv_usec)
+      return true;
+    return false;
   }
 
   static size_t doPrefix(long long value, const char *unit,
diff --git a/common/rfb/util.h b/common/rfb/util.h
index 0de64c4a..b678b890 100644
--- a/common/rfb/util.h
+++ b/common/rfb/util.h
@@ -99,9 +99,17 @@ namespace rfb {
     return (secs < 0 || secs > (INT_MAX/1000) ? INT_MAX : secs * 1000);
   }
 
+  // Returns time elapsed between two moments in milliseconds.
+  unsigned msBetween(const struct timeval *first,
+                     const struct timeval *second);
+
   // Returns time elapsed since given moment in milliseconds.
   unsigned msSince(const struct timeval *then);
 
+  // Returns true if first happened before seconds
+  bool isBefore(const struct timeval *first,
+                const struct timeval *second);
+
   size_t siPrefix(long long value, const char *unit,
                   char *buffer, size_t maxlen, int precision=6);
   size_t iecPrefix(long long value, const char *unit,