From e0a3ad423db070bee076216d9d94587b40fdc680 Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Wed, 30 Nov 2016 07:59:30 +0100 Subject: Handle timers which should be executed right away --- common/rfb/Timer.cxx | 3 +++ 1 file changed, 3 insertions(+) (limited to 'common') diff --git a/common/rfb/Timer.cxx b/common/rfb/Timer.cxx index efae36e2..e2aefacc 100644 --- a/common/rfb/Timer.cxx +++ b/common/rfb/Timer.cxx @@ -129,6 +129,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); } -- cgit v1.2.3 From b2a417c1554f81d9ce7b35c8eea6b5e571ed62b6 Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Fri, 11 Dec 2015 19:32:21 +0100 Subject: Use a queue for congestion pings This reduces the data sent, and avoids any problems with the client corrupting it. --- common/rfb/VNCSConnectionST.cxx | 40 ++++++++++++++++++++++++++-------------- common/rfb/VNCSConnectionST.h | 6 ++++-- 2 files changed, 30 insertions(+), 16 deletions(-) (limited to 'common') diff --git a/common/rfb/VNCSConnectionST.cxx b/common/rfb/VNCSConnectionST.cxx index d2206f9b..ef49a28e 100644 --- a/common/rfb/VNCSConnectionST.cxx +++ b/common/rfb/VNCSConnectionST.cxx @@ -72,7 +72,7 @@ VNCSConnectionST::VNCSConnectionST(VNCServerST* server_, network::Socket *s, fenceDataLen(0), fenceData(NULL), baseRTT(-1), congWindow(0), ackedOffset(0), sentOffset(0), minRTT(-1), seenCongestion(false), - pingCounter(0), congestionTimer(this), + congestionTimer(this), server(server_), updates(false), updateRenderedCursor(false), removeRenderedCursor(false), continuousUpdates(false), encodeManager(this), pointerEventTime(0), @@ -659,6 +659,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; @@ -682,18 +684,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"); - switch (len) { + type = data[0]; + + switch (type) { case 0: // Initial dummy fence; break; - case sizeof(struct RTTInfo): - memcpy(&rttInfo, data, sizeof(struct RTTInfo)); - handleRTTPong(rttInfo); + case 1: + handleRTTPong(); break; default: - vlog.error("Fence response of unexpected size received"); + vlog.error("Fence response of unexpected type received"); } } @@ -734,7 +738,8 @@ void VNCSConnectionST::supportsLocalCursor() void VNCSConnectionST::supportsFence() { - writer()->writeFence(fenceFlagRequest, 0, NULL); + char type = 0; + writer()->writeFence(fenceFlagRequest, sizeof(type), &type); } void VNCSConnectionST::supportsContinuousUpdates() @@ -768,6 +773,7 @@ bool VNCSConnectionST::handleTimeout(Timer* t) void VNCSConnectionST::writeRTTPing() { struct RTTInfo rttInfo; + char type; if (!cp.supportsFence) return; @@ -778,13 +784,14 @@ void VNCSConnectionST::writeRTTPing() rttInfo.offset = sock->outStream().length(); rttInfo.inFlight = rttInfo.offset - ackedOffset; + pings.push_back(rttInfo); + // 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++; + sizeof(type), &type); sentOffset = rttInfo.offset; @@ -793,11 +800,16 @@ void VNCSConnectionST::writeRTTPing() congestionTimer.start(__rfbmin(baseRTT * 2, 100)); } -void VNCSConnectionST::handleRTTPong(const struct RTTInfo &rttInfo) +void VNCSConnectionST::handleRTTPong() { + struct RTTInfo rttInfo; unsigned rtt, delay; - pingCounter--; + if (pings.empty()) + return; + + rttInfo = pings.front(); + pings.pop_front(); rtt = msSince(&rttInfo.tv); if (rtt < 1) @@ -881,7 +893,7 @@ bool VNCSConnectionST::isCongested() // 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) + if (pings.size() == 1) return false; return true; diff --git a/common/rfb/VNCSConnectionST.h b/common/rfb/VNCSConnectionST.h index 74a6946d..ccca6744 100644 --- a/common/rfb/VNCSConnectionST.h +++ b/common/rfb/VNCSConnectionST.h @@ -27,7 +27,9 @@ #ifndef __RFB_VNCSCONNECTIONST_H__ #define __RFB_VNCSCONNECTIONST_H__ +#include #include + #include #include #include @@ -160,7 +162,7 @@ namespace rfb { // Congestion control void writeRTTPing(); - void handleRTTPong(const struct RTTInfo &rttInfo); + void handleRTTPong(); bool isCongested(); void updateCongestion(); @@ -195,8 +197,8 @@ namespace rfb { unsigned minRTT; bool seenCongestion; - unsigned pingCounter; Timer congestionTimer; + std::list pings; VNCServerST* server; SimpleUpdateTracker updates; -- cgit v1.2.3 From 707fa123a699423f1466a201a7c4dd0975bb9e61 Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Fri, 11 Dec 2015 20:21:20 +0100 Subject: Reduce header dependencies in server classes --- common/rfb/ListConnInfo.h | 4 ++++ common/rfb/VNCSConnectionST.cxx | 13 ++++++++----- common/rfb/VNCSConnectionST.h | 5 ++--- common/rfb/VNCServerST.cxx | 7 ++++--- common/rfb/VNCServerST.h | 3 +-- 5 files changed, 19 insertions(+), 13 deletions(-) (limited to 'common') 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 + +#include + namespace rfb { struct ListConnInfo { diff --git a/common/rfb/VNCSConnectionST.cxx b/common/rfb/VNCSConnectionST.cxx index ef49a28e..cd5d0896 100644 --- a/common/rfb/VNCSConnectionST.cxx +++ b/common/rfb/VNCSConnectionST.cxx @@ -29,15 +29,18 @@ #endif #include -#include + +#include +#include +#include #include #include +#include +#include +#include +#include #include #include -#include -#include -#include -#include #define XK_MISCELLANY #define XK_XKB_KEYS #include diff --git a/common/rfb/VNCSConnectionST.h b/common/rfb/VNCSConnectionST.h index ccca6744..7022d8a9 100644 --- a/common/rfb/VNCSConnectionST.h +++ b/common/rfb/VNCSConnectionST.h @@ -30,15 +30,14 @@ #include #include +#include #include -#include -#include #include -#include struct RTTInfo; namespace rfb { + class VNCServerST; class VNCSConnectionST : public SConnection, public Timer::Callback { diff --git a/common/rfb/VNCServerST.cxx b/common/rfb/VNCServerST.cxx index ec5e962f..65439192 100644 --- a/common/rfb/VNCServerST.cxx +++ b/common/rfb/VNCServerST.cxx @@ -51,12 +51,13 @@ #include #include +#include +#include +#include +#include #include #include #include -#include -#include -#include #include #include diff --git a/common/rfb/VNCServerST.h b/common/rfb/VNCServerST.h index 00f77c73..9d252689 100644 --- a/common/rfb/VNCServerST.h +++ b/common/rfb/VNCServerST.h @@ -28,19 +28,18 @@ #include #include -#include #include #include #include #include #include -#include #include namespace rfb { class VNCSConnectionST; class ComparingUpdateTracker; + class ListConnInfo; class PixelBuffer; class KeyRemapper; -- cgit v1.2.3 From c09e5580d1058718301fe83fdb8750cc579e7ea1 Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Fri, 11 Dec 2015 20:23:17 +0100 Subject: Move congestion control to its own class It's a general function and it's better to have that particular complexity in its own place. --- common/rfb/CMakeLists.txt | 1 + common/rfb/Congestion.cxx | 222 ++++++++++++++++++++++++++++++++++++++++ common/rfb/Congestion.h | 62 +++++++++++ common/rfb/VNCSConnectionST.cxx | 199 +---------------------------------- common/rfb/VNCSConnectionST.h | 15 +-- 5 files changed, 292 insertions(+), 207 deletions(-) create mode 100644 common/rfb/Congestion.cxx create mode 100644 common/rfb/Congestion.h (limited to 'common') 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..c4c4d96d --- /dev/null +++ b/common/rfb/Congestion.cxx @@ -0,0 +1,222 @@ +/* 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. + */ + +#include + +#include +#include + +// Debug output on what the congestion control is up to +#undef CONGESTION_DEBUG + +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; + +struct Congestion::RTTInfo { + struct timeval tv; + int offset; + unsigned inFlight; +}; + +Congestion::Congestion() : + baseRTT(-1), congWindow(INITIAL_WINDOW), + ackedOffset(0), sentOffset(0), + minRTT(-1), seenCongestion(false), + congestionTimer(this) +{ +} + +Congestion::~Congestion() +{ +} + + +void Congestion::sentPing(int offset) +{ + struct RTTInfo rttInfo; + + if (ackedOffset == 0) + ackedOffset = offset; + + memset(&rttInfo, 0, sizeof(struct RTTInfo)); + + gettimeofday(&rttInfo.tv, NULL); + rttInfo.offset = offset; + rttInfo.inFlight = rttInfo.offset - ackedOffset; + + pings.push_back(rttInfo); + + sentOffset = offset; + + // Let some data flow before we adjust the settings + if (!congestionTimer.isStarted()) + congestionTimer.start(__rfbmin(baseRTT * 2, 100)); +} + +void Congestion::gotPong() +{ + struct RTTInfo rttInfo; + unsigned rtt, delay; + + if (pings.empty()) + return; + + rttInfo = pings.front(); + pings.pop_front(); + + 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; + } + + // 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; +} + +bool Congestion::isCongested(int offset, unsigned idleTime) +{ + // 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) && (idleTime > 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; + } + + // FIXME: Should we compensate for non-update data? + // (i.e. use sentOffset instead of offset) + if ((offset - ackedOffset) < congWindow) + 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 (pings.size() == 1) + return false; + + return true; +} + +bool Congestion::handleTimeout(Timer* t) +{ + unsigned diff; + + if (!seenCongestion) + return false; + + // 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 > __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); +#endif + + minRTT = -1; + seenCongestion = false; + + return false; +} + diff --git a/common/rfb/Congestion.h b/common/rfb/Congestion.h new file mode 100644 index 00000000..e8548f93 --- /dev/null +++ b/common/rfb/Congestion.h @@ -0,0 +1,62 @@ +/* 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 + +#include + +namespace rfb { + class Congestion : public Timer::Callback { + public: + Congestion(); + ~Congestion(); + + // sentPing() must be called when a marker is placed on the + // outgoing stream, along with the current stream position. + // gotPong() must be called when the response for such a marker + // is received. + void sentPing(int offset); + void gotPong(); + + // isCongested() determines if the transport is currently congested + // or if more data can be sent. The curren stream position and how + // long the transport has been idle must be specified. + bool isCongested(int offset, unsigned idleTime); + + private: + // Timer callbacks + virtual bool handleTimeout(Timer* t); + + private: + unsigned baseRTT; + unsigned congWindow; + unsigned ackedOffset, sentOffset; + + unsigned minRTT; + bool seenCongestion; + Timer congestionTimer; + + struct RTTInfo; + std::list pings; + }; +} + +#endif diff --git a/common/rfb/VNCSConnectionST.cxx b/common/rfb/VNCSConnectionST.cxx index cd5d0896..43eb8256 100644 --- a/common/rfb/VNCSConnectionST.cxx +++ b/common/rfb/VNCSConnectionST.cxx @@ -17,17 +17,6 @@ * USA. */ -// Debug output on what the congestion control is up to -#undef CONGESTION_DEBUG - -#include - -#ifdef CONGESTION_DEBUG -#include -#include -#include -#endif - #include #include @@ -49,33 +38,12 @@ 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; -}; - VNCSConnectionST::VNCSConnectionST(VNCServerST* server_, network::Socket *s, bool reverse) : sock(s), reverseConnection(reverse), queryConnectTimer(this), inProcessMessages(false), pendingSyncFence(false), syncFence(false), fenceFlags(0), fenceDataLen(0), fenceData(NULL), - baseRTT(-1), congWindow(0), ackedOffset(0), sentOffset(0), - minRTT(-1), seenCongestion(false), - congestionTimer(this), server(server_), updates(false), updateRenderedCursor(false), removeRenderedCursor(false), continuousUpdates(false), encodeManager(this), pointerEventTime(0), @@ -428,10 +396,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) @@ -697,7 +661,7 @@ void VNCSConnectionST::fence(rdr::U32 flags, unsigned len, const char data[]) // Initial dummy fence; break; case 1: - handleRTTPong(); + congestion.gotPong(); break; default: vlog.error("Fence response of unexpected type received"); @@ -759,9 +723,7 @@ void VNCSConnectionST::supportsContinuousUpdates() bool VNCSConnectionST::handleTimeout(Timer* t) { try { - if (t == &congestionTimer) - updateCongestion(); - else if (t == &queryConnectTimer) { + if (t == &queryConnectTimer) { if (state() == RFBSTATE_QUERYING) approveConnection(false, "The attempt to prompt the user to accept the connection failed"); } @@ -775,20 +737,11 @@ bool VNCSConnectionST::handleTimeout(Timer* t) 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; - - pings.push_back(rttInfo); - // 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. @@ -796,63 +749,11 @@ void VNCSConnectionST::writeRTTPing() writer()->writeFence(fenceFlagRequest | fenceFlagBlockBefore, sizeof(type), &type); - sentOffset = rttInfo.offset; - - // Let some data flow before we adjust the settings - if (!congestionTimer.isStarted()) - congestionTimer.start(__rfbmin(baseRTT * 2, 100)); -} - -void VNCSConnectionST::handleRTTPong() -{ - struct RTTInfo rttInfo; - unsigned rtt, delay; - - if (pings.empty()) - return; - - rttInfo = pings.front(); - pings.pop_front(); - - 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; - } - - // 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(sock->outStream().length()); } bool VNCSConnectionST::isCongested() { - int offset; - // Stuff still waiting in the send buffer? sock->outStream().flush(); if (sock->outStream().bufferUsage() > 0) @@ -861,98 +762,8 @@ bool VNCSConnectionST::isCongested() 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) - 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 (pings.size() == 1) - return false; - - 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; + return congestion.isCongested(sock->outStream().length(), + sock->outStream().getIdleTime()); } diff --git a/common/rfb/VNCSConnectionST.h b/common/rfb/VNCSConnectionST.h index 7022d8a9..96d7e4c9 100644 --- a/common/rfb/VNCSConnectionST.h +++ b/common/rfb/VNCSConnectionST.h @@ -27,15 +27,13 @@ #ifndef __RFB_VNCSCONNECTIONST_H__ #define __RFB_VNCSCONNECTIONST_H__ -#include #include +#include #include #include #include -struct RTTInfo; - namespace rfb { class VNCServerST; @@ -161,9 +159,7 @@ namespace rfb { // Congestion control void writeRTTPing(); - void handleRTTPong(); bool isCongested(); - void updateCongestion(); // writeFramebufferUpdate() attempts to write a framebuffer update to the // client. @@ -190,14 +186,7 @@ namespace rfb { unsigned fenceDataLen; char *fenceData; - unsigned baseRTT; - unsigned congWindow; - unsigned ackedOffset, sentOffset; - - unsigned minRTT; - bool seenCongestion; - Timer congestionTimer; - std::list pings; + Congestion congestion; VNCServerST* server; SimpleUpdateTracker updates; -- cgit v1.2.3 From a99d14d1939cb2338b6268d9aebe3850df66daed Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Sun, 13 Dec 2015 15:43:46 +0100 Subject: Improved congestion control handling Refine the previous method by interpolating the values we need. This reduces the effect of the problem that we cannot send enough ping packets. --- common/rfb/Congestion.cxx | 357 ++++++++++++++++++++++++++++++---------- common/rfb/Congestion.h | 57 +++++-- common/rfb/VNCSConnectionST.cxx | 27 ++- common/rfb/VNCSConnectionST.h | 1 + common/rfb/util.cxx | 31 +++- common/rfb/util.h | 8 + 6 files changed, 363 insertions(+), 118 deletions(-) (limited to 'common') diff --git a/common/rfb/Congestion.cxx b/common/rfb/Congestion.cxx index c4c4d96d..94d78e32 100644 --- a/common/rfb/Congestion.cxx +++ b/common/rfb/Congestion.cxx @@ -24,12 +24,16 @@ * 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. + * 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. */ +#include #include #include +#include #include // Debug output on what the congestion control is up to @@ -49,158 +53,332 @@ static const unsigned MINIMUM_WINDOW = 4096; // limit for now... static const unsigned MAXIMUM_WINDOW = 4194304; -struct Congestion::RTTInfo { - struct timeval tv; - int offset; - unsigned inFlight; -}; +static LogWriter vlog("Congestion"); Congestion::Congestion() : + lastPosition(0), extraBuffer(0), baseRTT(-1), congWindow(INITIAL_WINDOW), - ackedOffset(0), sentOffset(0), - minRTT(-1), seenCongestion(false), - congestionTimer(this) + 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; + } + + // 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(int offset) +void Congestion::sentPing() { struct RTTInfo rttInfo; - if (ackedOffset == 0) - ackedOffset = offset; - memset(&rttInfo, 0, sizeof(struct RTTInfo)); gettimeofday(&rttInfo.tv, NULL); - rttInfo.offset = offset; - rttInfo.inFlight = rttInfo.offset - ackedOffset; + rttInfo.pos = lastPosition; + rttInfo.extra = getExtraBuffer(); + rttInfo.congested = isCongested(); pings.push_back(rttInfo); - - sentOffset = offset; - - // Let some data flow before we adjust the settings - if (!congestionTimer.isStarted()) - congestionTimer.start(__rfbmin(baseRTT * 2, 100)); } 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(); - rtt = msSince(&rttInfo.tv); + lastPong = rttInfo; + lastPongArrival = now; + + rtt = msBetween(&rttInfo.tv, &now); 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; + // 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; - if (delay < rtt) - rtt -= delay; - else - rtt = 1; + // Estimate added delay because of overtaxed buffers (see above) + delay = rttInfo.extra * 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; - } + // 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; - // 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. + // 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(int offset, unsigned idleTime) +bool Congestion::isCongested() { - // 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) && (idleTime > 2 * baseRTT)) { + if (getInFlight() < congWindow) + return false; -#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 + return true; +} - // Close congestion window and allow a transfer - // FIXME: Reset baseRTT like Linux Vegas? - congWindow = __rfbmin(INITIAL_WINDOW, congWindow); +int Congestion::getUncongestedETA() +{ + unsigned targetAcked; + + const struct RTTInfo* prevPing; + unsigned eta, elapsed; + unsigned etaNext, delay; + + std::list::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; - return false; + // 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; } +} - // FIXME: Should we compensate for non-update data? - // (i.e. use sentOffset instead of offset) - if ((offset - ackedOffset) < congWindow) - return false; +unsigned Congestion::getExtraBuffer() +{ + unsigned elapsed; + unsigned consumed; - // 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 (pings.size() == 1) - return false; + if (baseRTT == (unsigned)-1) + return 0; - return true; + elapsed = msSince(&lastUpdate); + consumed = elapsed * congWindow / baseRTT; + + if (consumed >= extraBuffer) + return 0; + else + return extraBuffer - consumed; } -bool Congestion::handleTimeout(Timer* t) +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; - if (!seenCongestion) - return false; + // 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. + // First we check all pongs to make sure we're not having a too large + // congestion window. diff = minRTT - baseRTT; - if (diff > __rfbmin(100, baseRTT)) { + // FIXME: Should we do slow start? + if (diff > 100) { // Way too fast congWindow = congWindow * baseRTT / minRTT; - } else if (diff > __rfbmin(50, baseRTT/2)) { + } else if (diff > 50) { // Slightly too fast congWindow -= 4096; - } else if (diff < 5) { - // Way too slow - congWindow += 8192; - } else if (diff < 25) { - // Too slow - congWindow += 4096; + } else { + // Secondly 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) @@ -209,14 +387,13 @@ bool Congestion::handleTimeout(Timer* t) 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); + vlog.debug("RTT: %d ms (%d ms), Window: %d KiB, Bandwidth: %g Mbps", + minRTT, baseRTT, congWindow / 1024, + congWindow * 8.0 / baseRTT / 1000.0); #endif - minRTT = -1; - seenCongestion = false; - - return false; + measurements = 0; + gettimeofday(&lastAdjustment, NULL); + minRTT = minCongestedRTT = -1; } diff --git a/common/rfb/Congestion.h b/common/rfb/Congestion.h index e8548f93..2bea5dac 100644 --- a/common/rfb/Congestion.h +++ b/common/rfb/Congestion.h @@ -21,41 +21,62 @@ #include -#include - namespace rfb { - class Congestion : public Timer::Callback { + 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, along with the current stream position. - // gotPong() must be called when the response for such a marker - // is received. - void sentPing(int offset); + // 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. The curren stream position and how - // long the transport has been idle must be specified. - bool isCongested(int offset, unsigned idleTime); + // or if more data can be sent. + bool isCongested(); - private: - // Timer callbacks - virtual bool handleTimeout(Timer* t); + // 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(); + + protected: + unsigned getExtraBuffer(); + unsigned getInFlight(); + + void updateCongestion(); private: + unsigned lastPosition; + unsigned extraBuffer; + struct timeval lastUpdate; + struct timeval lastSent; + unsigned baseRTT; unsigned congWindow; - unsigned ackedOffset, sentOffset; - unsigned minRTT; - bool seenCongestion; - Timer congestionTimer; + struct RTTInfo { + struct timeval tv; + unsigned pos; + unsigned extra; + bool congested; + }; - struct RTTInfo; std::list pings; + + struct RTTInfo lastPong; + struct timeval lastPongArrival; + + int measurements; + struct timeval lastAdjustment; + unsigned minRTT, minCongestedRTT; }; } diff --git a/common/rfb/VNCSConnectionST.cxx b/common/rfb/VNCSConnectionST.cxx index 43eb8256..b2ceb7d2 100644 --- a/common/rfb/VNCSConnectionST.cxx +++ b/common/rfb/VNCSConnectionST.cxx @@ -43,7 +43,7 @@ VNCSConnectionST::VNCSConnectionST(VNCServerST* server_, network::Socket *s, : sock(s), reverseConnection(reverse), queryConnectTimer(this), inProcessMessages(false), pendingSyncFence(false), syncFence(false), fenceFlags(0), - fenceDataLen(0), fenceData(NULL), + fenceDataLen(0), fenceData(NULL), congestionTimer(this), server(server_), updates(false), updateRenderedCursor(false), removeRenderedCursor(false), continuousUpdates(false), encodeManager(this), pointerEventTime(0), @@ -726,6 +726,8 @@ bool VNCSConnectionST::handleTimeout(Timer* t) if (t == &queryConnectTimer) { if (state() == RFBSTATE_QUERYING) approveConnection(false, "The attempt to prompt the user to accept the connection failed"); + } else if (t == &congestionTimer) { + writeFramebufferUpdate(); } } catch (rdr::Exception& e) { close(e.str()); @@ -742,6 +744,8 @@ void VNCSConnectionST::writeRTTPing() if (!cp.supportsFence) return; + 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. @@ -749,11 +753,15 @@ void VNCSConnectionST::writeRTTPing() writer()->writeFence(fenceFlagRequest | fenceFlagBlockBefore, sizeof(type), &type); - congestion.sentPing(sock->outStream().length()); + congestion.sentPing(); } bool VNCSConnectionST::isCongested() { + unsigned eta; + + congestionTimer.stop(); + // Stuff still waiting in the send buffer? sock->outStream().flush(); if (sock->outStream().bufferUsage() > 0) @@ -762,13 +770,22 @@ bool VNCSConnectionST::isCongested() if (!cp.supportsFence) return false; - return congestion.isCongested(sock->outStream().length(), - sock->outStream().getIdleTime()); + congestion.updatePosition(sock->outStream().length()); + if (!congestion.isCongested()) + return false; + + eta = congestion.getUncongestedETA(); + if (eta >= 0) + congestionTimer.start(eta); + + return true; } 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. @@ -805,6 +822,8 @@ void VNCSConnectionST::writeFramebufferUpdate() writeDataUpdate(); network::TcpSocket::cork(sock->getFd(), false); + + congestion.updatePosition(sock->outStream().length()); } void VNCSConnectionST::writeNoDataUpdate() diff --git a/common/rfb/VNCSConnectionST.h b/common/rfb/VNCSConnectionST.h index 96d7e4c9..dde0b1ec 100644 --- a/common/rfb/VNCSConnectionST.h +++ b/common/rfb/VNCSConnectionST.h @@ -187,6 +187,7 @@ namespace rfb { char *fenceData; Congestion congestion; + Timer congestionTimer; VNCServerST* server; SimpleUpdateTracker updates; diff --git a/common/rfb/util.cxx b/common/rfb/util.cxx index 22e00ffc..755c91fd 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 e9114c3d..3ca92f9d 100644 --- a/common/rfb/util.h +++ b/common/rfb/util.h @@ -95,9 +95,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, -- cgit v1.2.3 From da8904cb0a6867ce676a4b60334ce2be3746cf60 Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Mon, 21 Dec 2015 07:59:20 +0100 Subject: Add simple slow start to congestion control --- common/rfb/Congestion.cxx | 77 +++++++++++++++++++++++++++++++++-------------- common/rfb/Congestion.h | 1 + 2 files changed, 56 insertions(+), 22 deletions(-) (limited to 'common') diff --git a/common/rfb/Congestion.cxx b/common/rfb/Congestion.cxx index 94d78e32..c7d6f710 100644 --- a/common/rfb/Congestion.cxx +++ b/common/rfb/Congestion.cxx @@ -27,6 +27,10 @@ * 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 @@ -57,7 +61,7 @@ static LogWriter vlog("Congestion"); Congestion::Congestion() : lastPosition(0), extraBuffer(0), - baseRTT(-1), congWindow(INITIAL_WINDOW), + baseRTT(-1), congWindow(INITIAL_WINDOW), inSlowStart(true), measurements(0), minRTT(-1), minCongestedRTT(-1) { gettimeofday(&lastUpdate, NULL); @@ -98,6 +102,7 @@ void Congestion::updatePosition(unsigned pos) measurements = 0; gettimeofday(&lastAdjustment, NULL); minRTT = minCongestedRTT = -1; + inSlowStart = true; } // Commonly we will be in a state of overbuffering. We need to @@ -355,29 +360,56 @@ void Congestion::updateCongestion() // a "perfect" one cannot be distinguished from a too small one. This // translates to a goal of a few extra milliseconds of delay. - // First we check all pongs to make sure we're not having a too large - // congestion window. diff = minRTT - baseRTT; - // FIXME: Should we do slow start? - if (diff > 100) { - // Way too fast + 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; - } else if (diff > 50) { - // Slightly too fast - congWindow -= 4096; - } else { - // Secondly only the "congested" pongs are checked to see if the - // window is too small. + inSlowStart = false; + } - diff = minCongestedRTT - baseRTT; + if (inSlowStart) { + // Slow start. Aggressive growth until we see congestion. - if (diff < 5) { - // Way too slow - congWindow += 8192; - } else if (diff < 25) { - // Too slow - congWindow += 4096; + 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; + } } } @@ -387,9 +419,10 @@ void Congestion::updateCongestion() congWindow = MAXIMUM_WINDOW; #ifdef CONGESTION_DEBUG - vlog.debug("RTT: %d ms (%d ms), Window: %d KiB, Bandwidth: %g Mbps", - minRTT, baseRTT, congWindow / 1024, - congWindow * 8.0 / baseRTT / 1000.0); + 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; diff --git a/common/rfb/Congestion.h b/common/rfb/Congestion.h index 2bea5dac..5feea65e 100644 --- a/common/rfb/Congestion.h +++ b/common/rfb/Congestion.h @@ -61,6 +61,7 @@ namespace rfb { unsigned baseRTT; unsigned congWindow; + bool inSlowStart; struct RTTInfo { struct timeval tv; -- cgit v1.2.3 From 8cf7163ec07e9d97fe48d6dc4a29d6dc338eef9d Mon Sep 17 00:00:00 2001 From: Pierre Ossman Date: Fri, 11 Mar 2016 09:38:08 +0100 Subject: Add crude congestion window debug trace Allows us to compare our computed congestion window with the underlying one used by the TCP layer. --- common/rfb/Congestion.cxx | 38 ++++++++++++++++++++++++++++++++++++++ common/rfb/Congestion.h | 5 +++++ common/rfb/VNCSConnectionST.cxx | 1 + 3 files changed, 44 insertions(+) (limited to 'common') diff --git a/common/rfb/Congestion.cxx b/common/rfb/Congestion.cxx index c7d6f710..a2f7a256 100644 --- a/common/rfb/Congestion.cxx +++ b/common/rfb/Congestion.cxx @@ -36,6 +36,14 @@ #include #include +#ifdef __linux__ +#include +#include +#include +#include +#include +#endif + #include #include #include @@ -43,6 +51,9 @@ // 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. @@ -273,6 +284,33 @@ int Congestion::getUncongestedETA() } } +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; diff --git a/common/rfb/Congestion.h b/common/rfb/Congestion.h index 5feea65e..fd57c22e 100644 --- a/common/rfb/Congestion.h +++ b/common/rfb/Congestion.h @@ -47,6 +47,11 @@ namespace rfb { // 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(); diff --git a/common/rfb/VNCSConnectionST.cxx b/common/rfb/VNCSConnectionST.cxx index b2ceb7d2..5b9152c2 100644 --- a/common/rfb/VNCSConnectionST.cxx +++ b/common/rfb/VNCSConnectionST.cxx @@ -764,6 +764,7 @@ bool VNCSConnectionST::isCongested() // Stuff still waiting in the send buffer? sock->outStream().flush(); + congestion.debugTrace("congestion-trace.csv", sock->getFd()); if (sock->outStream().bufferUsage() > 0) return true; -- cgit v1.2.3