You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@trafficserver.apache.org by ma...@apache.org on 2017/12/22 02:06:49 UTC
[trafficserver] 02/02: Translate the pseudo code for congestion
control to C++
This is an automated email from the ASF dual-hosted git repository.
maskit pushed a commit to branch quic-latest
in repository https://gitbox.apache.org/repos/asf/trafficserver.git
commit c644c6c1c46f7c5dd17ca89c7312260f9ef632f6
Author: Masakazu Kitajo <ma...@apache.org>
AuthorDate: Fri Dec 22 11:04:58 2017 +0900
Translate the pseudo code for congestion control to C++
---
iocore/net/P_QUICNetVConnection.h | 1 -
iocore/net/QUICNetVConnection.cc | 1 -
iocore/net/quic/QUICCongestionController.cc | 70 ++++++++++++++++-------------
iocore/net/quic/QUICCongestionController.h | 45 -------------------
iocore/net/quic/QUICFrameDispatcher.cc | 5 ---
iocore/net/quic/QUICLossDetector.cc | 21 +++++----
iocore/net/quic/QUICLossDetector.h | 43 ++++++++++++------
7 files changed, 81 insertions(+), 105 deletions(-)
diff --git a/iocore/net/P_QUICNetVConnection.h b/iocore/net/P_QUICNetVConnection.h
index 4f4ba37..3f9d1c2 100644
--- a/iocore/net/P_QUICNetVConnection.h
+++ b/iocore/net/P_QUICNetVConnection.h
@@ -54,7 +54,6 @@
#include "quic/QUICAckFrameCreator.h"
#include "quic/QUICLossDetector.h"
#include "quic/QUICStreamManager.h"
-#include "quic/QUICCongestionController.h"
#include "quic/QUICApplicationMap.h"
// These are included here because older OpenQUIC libraries don't have them.
diff --git a/iocore/net/QUICNetVConnection.cc b/iocore/net/QUICNetVConnection.cc
index 1581332..124a292 100644
--- a/iocore/net/QUICNetVConnection.cc
+++ b/iocore/net/QUICNetVConnection.cc
@@ -116,7 +116,6 @@ QUICNetVConnection::start(SSL_CTX *ssl_ctx)
this->_frame_dispatcher->add_handler(this);
this->_frame_dispatcher->add_handler(this->_stream_manager);
- this->_frame_dispatcher->add_handler(this->_congestion_controller);
this->_frame_dispatcher->add_handler(this->_loss_detector);
}
diff --git a/iocore/net/quic/QUICCongestionController.cc b/iocore/net/quic/QUICCongestionController.cc
index 3ce8e76..d06c090 100644
--- a/iocore/net/quic/QUICCongestionController.cc
+++ b/iocore/net/quic/QUICCongestionController.cc
@@ -22,55 +22,63 @@
*/
#include <ts/Diags.h>
-#include <QUICCongestionController.h>
+#include <QUICLossDetector.h>
-static constexpr char tag[] = "quic_congestion_controller";
+// 4.7.1. Constants of interest
+constexpr static uint16_t DEFAULT_MSS = 1460;
+constexpr static uint32_t INITIAL_WINDOW = 10 * DEFAULT_MSS;
+constexpr static uint32_t MINIMUM_WINDOW = 2 * DEFAULT_MSS;
+constexpr static double LOSS_REDUCTION_FACTOR = 0.5;
-std::vector<QUICFrameType>
-QUICCongestionController::interests()
+QUICCongestionController::QUICCongestionController()
{
- return {QUICFrameType::ACK, QUICFrameType::STREAM};
-}
-
-QUICErrorUPtr
-QUICCongestionController::handle_frame(std::shared_ptr<const QUICFrame> frame)
-{
- QUICErrorUPtr error = QUICErrorUPtr(new QUICNoError());
-
- switch (frame->type()) {
- case QUICFrameType::STREAM:
- case QUICFrameType::ACK:
- break;
- default:
- Debug(tag, "Unexpected frame type: %02x", static_cast<unsigned int>(frame->type()));
- ink_assert(false);
- break;
- }
-
- return error;
+ this->_congestion_window = INITIAL_WINDOW;
}
void
-QUICCongestionController::on_packet_sent(size_t sent_bytes)
+QUICCongestionController::on_packet_sent(size_t bytes_sent)
{
+ this->_bytes_in_flight += bytes_sent;
}
void
-QUICCongestionController::on_packet_acked(QUICPacketNumber acked_packet_number)
+QUICCongestionController::on_packet_acked(QUICPacketNumber acked_packet_number, size_t acked_packet_size)
{
+ // Remove from bytes_in_flight.
+ this->_bytes_in_flight -= acked_packet_size;
+ if (acked_packet_number < this->_end_of_recovery) {
+ // Do not increase congestion window in recovery period.
+ return;
+ }
+ if (this->_congestion_window < this->_ssthresh) {
+ // Slow start.
+ this->_congestion_window += acked_packet_size;
+ } else {
+ // Congestion avoidance.
+ this->_congestion_window += DEFAULT_MSS * acked_packet_size / this->_congestion_window;
+ }
}
void
-QUICCongestionController::on_packets_lost(std::set<QUICPacketNumber> packets)
+QUICCongestionController::on_packets_lost(std::map<QUICPacketNumber, PacketInfo &> lost_packets)
{
+ // Remove lost packets from bytes_in_flight.
+ for (auto &lost_packet : lost_packets) {
+ this->_bytes_in_flight -= lost_packet.second.bytes;
+ }
+ QUICPacketNumber largest_lost_packet = lost_packets.rbegin()->first;
+ // Start a new recovery epoch if the lost packet is larger
+ // than the end of the previous recovery epoch.
+ if (this->_end_of_recovery < largest_lost_packet) {
+ this->_end_of_recovery = largest_lost_packet;
+ this->_congestion_window *= LOSS_REDUCTION_FACTOR;
+ this->_congestion_window = std::max(this->_congestion_window, MINIMUM_WINDOW);
+ this->_ssthresh = this->_congestion_window;
+ }
}
void
QUICCongestionController::on_retransmission_timeout_verified()
{
-}
-
-void
-QUICCongestionController::on_rto_verified()
-{
+ this->_congestion_window = MINIMUM_WINDOW;
}
diff --git a/iocore/net/quic/QUICCongestionController.h b/iocore/net/quic/QUICCongestionController.h
deleted file mode 100644
index 79cb96a..0000000
--- a/iocore/net/quic/QUICCongestionController.h
+++ /dev/null
@@ -1,45 +0,0 @@
-/** @file
- *
- * A brief file description
- *
- * @section license License
- *
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-#pragma once
-
-#include <set>
-#include "QUICTypes.h"
-#include "QUICFrameHandler.h"
-
-// TODO Implement congestion controll.
-// Congestion controller will be required after the 2nd implementation draft.
-class QUICCongestionController : public QUICFrameHandler
-{
-public:
- virtual std::vector<QUICFrameType> interests() override;
- virtual QUICErrorUPtr handle_frame(std::shared_ptr<const QUICFrame>) override;
-
- void on_packet_sent(size_t sent_bytes);
- void on_packet_acked(QUICPacketNumber acked_packet_number);
- virtual void on_packets_lost(std::set<QUICPacketNumber> packets);
- void on_rto_verified();
- void on_retransmission_timeout_verified();
-
-private:
-};
diff --git a/iocore/net/quic/QUICFrameDispatcher.cc b/iocore/net/quic/QUICFrameDispatcher.cc
index c23fff1..b4582b9 100644
--- a/iocore/net/quic/QUICFrameDispatcher.cc
+++ b/iocore/net/quic/QUICFrameDispatcher.cc
@@ -22,11 +22,6 @@
*/
#include "QUICFrameDispatcher.h"
-#include "QUICConnection.h"
-#include "QUICStreamManager.h"
-#include "QUICCongestionController.h"
-#include "QUICLossDetector.h"
-#include "QUICEvents.h"
#include "QUICDebugNames.h"
static constexpr char tag[] = "quic_frame_handler";
diff --git a/iocore/net/quic/QUICLossDetector.cc b/iocore/net/quic/QUICLossDetector.cc
index 7edd181..f99fc32 100644
--- a/iocore/net/quic/QUICLossDetector.cc
+++ b/iocore/net/quic/QUICLossDetector.cc
@@ -169,7 +169,10 @@ QUICLossDetector::_on_ack_received(const std::shared_ptr<const QUICAckFrame> &ac
// Find all newly acked packets.
for (auto acked_packet_number : this->_determine_newly_acked_packets(*ack_frame)) {
- this->_on_packet_acked(acked_packet_number);
+ auto pi = this->_sent_packets.find(acked_packet_number);
+ if (pi != this->_sent_packets.end()) {
+ this->_on_packet_acked(pi->first, pi->second->bytes);
+ }
}
QUICLDDebug("Unacked packets %lu (retransmittable %u, includes %u handshake packets)", this->_sent_packets.size(),
@@ -208,11 +211,11 @@ QUICLossDetector::_update_rtt(ink_hrtime latest_rtt, ink_hrtime ack_delay, QUICP
}
void
-QUICLossDetector::_on_packet_acked(QUICPacketNumber acked_packet_number)
+QUICLossDetector::_on_packet_acked(QUICPacketNumber acked_packet_number, size_t acked_packet_size)
{
SCOPED_MUTEX_LOCK(lock, this->mutex, this_ethread());
- QUICLDDebug("Packet number %" PRIu64 " has been acked", acked_packet_number);
- this->_cc->on_packet_acked(acked_packet_number);
+ // QUICLDDebug("Packet number %" PRIu64 " has been acked", acked_packet_number);
+ this->_cc->on_packet_acked(acked_packet_number, acked_packet_size);
// If a packet sent prior to RTO was acked, then the RTO
// was spurious. Otherwise, inform congestion control.
if (this->_rto_count > 0 && acked_packet_number > this->_largest_sent_before_rto) {
@@ -309,7 +312,7 @@ QUICLossDetector::_detect_lost_packets(QUICPacketNumber largest_acked_packet_num
{
SCOPED_MUTEX_LOCK(lock, this->mutex, this_ethread());
this->_loss_time = 0;
- std::set<QUICPacketNumber> lost_packets;
+ std::map<QUICPacketNumber, PacketInfo &> lost_packets;
double delay_until_lost = INFINITY;
if (this->_time_loss_detection) {
@@ -326,9 +329,9 @@ QUICLossDetector::_detect_lost_packets(QUICPacketNumber largest_acked_packet_num
ink_hrtime time_since_sent = Thread::get_hrtime() - unacked.second->time;
uint64_t packet_delta = largest_acked_packet_number - unacked.second->packet_number;
if (time_since_sent > delay_until_lost) {
- lost_packets.insert(unacked.first);
+ lost_packets.insert({unacked.first, *unacked.second});
} else if (packet_delta > this->_reordering_threshold) {
- lost_packets.insert(unacked.first);
+ lost_packets.insert({unacked.first, *unacked.second});
} else if (this->_loss_time == 0 && delay_until_lost != INFINITY) {
this->_loss_time = Thread::get_hrtime() + delay_until_lost - time_since_sent;
}
@@ -338,8 +341,8 @@ QUICLossDetector::_detect_lost_packets(QUICPacketNumber largest_acked_packet_num
// lets it decide whether to retransmit immediately.
if (!lost_packets.empty()) {
this->_cc->on_packets_lost(lost_packets);
- for (auto packet_number : lost_packets) {
- this->_remove_from_sent_packet_list(packet_number);
+ for (auto lost_packet : lost_packets) {
+ this->_remove_from_sent_packet_list(lost_packet.first);
}
}
}
diff --git a/iocore/net/quic/QUICLossDetector.h b/iocore/net/quic/QUICLossDetector.h
index e67598b..94b707d 100644
--- a/iocore/net/quic/QUICLossDetector.h
+++ b/iocore/net/quic/QUICLossDetector.h
@@ -31,13 +31,39 @@
#include "../../eventsystem/I_Action.h"
#include "ts/ink_hrtime.h"
#include "I_VConnection.h"
-#include "P_Net.h"
#include "QUICTypes.h"
#include "QUICPacket.h"
#include "QUICFrame.h"
#include "QUICFrameHandler.h"
#include "QUICPacketTransmitter.h"
-#include "QUICCongestionController.h"
+
+struct PacketInfo {
+ QUICPacketNumber packet_number;
+ ink_hrtime time;
+ bool ack_only;
+ bool handshake;
+ size_t bytes;
+ QUICPacketUPtr packet;
+};
+
+class QUICCongestionController
+{
+public:
+ QUICCongestionController();
+ virtual ~QUICCongestionController() {}
+
+ void on_packet_sent(size_t bytes_sent);
+ void on_packet_acked(QUICPacketNumber acked_packet_number, size_t acked_packet_size);
+ virtual void on_packets_lost(std::map<QUICPacketNumber, PacketInfo &> packets);
+ void on_retransmission_timeout_verified();
+
+private:
+ // 4.7.2. Variables of interest
+ uint32_t _bytes_in_flight = 0;
+ uint32_t _congestion_window = 0;
+ QUICPacketNumber _end_of_recovery = 0;
+ uint32_t _ssthresh = UINT32_MAX;
+};
class QUICLossDetector : public Continuation, public QUICFrameHandler
{
@@ -54,16 +80,7 @@ public:
private:
QUICConnectionId _connection_id = 0;
- struct PacketInfo {
- QUICPacketNumber packet_number;
- ink_hrtime time;
- bool ack_only;
- bool handshake;
- size_t bytes;
- QUICPacketUPtr packet;
- };
-
- bool _time_loss_detection = false;
+ bool _time_loss_detection = true;
// TODO QUICCongestionController *cc = nullptr;
@@ -103,7 +120,7 @@ private:
void _on_packet_sent(QUICPacketNumber packet_number, bool is_ack_only, bool is_handshake, size_t sent_bytes,
QUICPacketUPtr packet);
void _on_ack_received(const std::shared_ptr<const QUICAckFrame> &ack_frame);
- void _on_packet_acked(QUICPacketNumber acked_packet_number);
+ void _on_packet_acked(QUICPacketNumber acked_packet_number, size_t acked_packet_size);
void _update_rtt(ink_hrtime latest_rtt, ink_hrtime ack_delay, QUICPacketNumber largest_acked);
void _detect_lost_packets(QUICPacketNumber largest_acked);
void _set_loss_detection_alarm();
--
To stop receiving notification emails like this one, please contact
"commits@trafficserver.apache.org" <co...@trafficserver.apache.org>.