1 /*
2 * Copyright (c) 2021 Fastly, Kazuho Oku
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a copy
5 * of this software and associated documentation files (the "Software"), to
6 * deal in the Software without restriction, including without limitation the
7 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8 * sell copies of the Software, and to permit persons to whom the Software is
9 * furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20 * IN THE SOFTWARE.
21 */
22 #include <math.h>
23 #include "quicly/cc.h"
24 #include "quicly.h"
25
26 /**
27 * Calculates the increase ratio to be used in congestion avoidance phase.
28 */
calc_bytes_per_mtu_increase(uint32_t cwnd,uint32_t rtt,uint32_t mtu)29 static uint32_t calc_bytes_per_mtu_increase(uint32_t cwnd, uint32_t rtt, uint32_t mtu)
30 {
31 /* Reno: CWND size after reduction */
32 uint32_t reno = cwnd * QUICLY_RENO_BETA;
33
34 /* Cubic: Cubic reaches original CWND (i.e., Wmax) in K seconds, therefore:
35 * amount_to_increase = 0.3 * Wmax
36 * amount_to_be_acked = K * Wmax / RTT_at_Wmax
37 * where
38 * K = (0.3 / 0.4 * Wmax / MTU)^(1/3)
39 *
40 * Hence:
41 * bytes_per_mtu_increase = amount_to_be_acked / amount_to_increase * MTU
42 * = (K * Wmax / RTT_at_Wmax) / (0.3 * Wmax) * MTU
43 * = K * MTU / (0.3 * RTT_at_Wmax)
44 *
45 * In addition, we have to adjust the value to take fast convergence into account. On a path with stable capacity, 50% of
46 * congestion events adjust Wmax to 0.85x of before calculating K. If that happens, the modified K (K') is:
47 *
48 * K' = (0.3 / 0.4 * 0.85 * Wmax / MTU)^(1/3) = 0.85^(1/3) * K
49 *
50 * where K' represents the time to reach 0.85 * Wmax. As the cubic curve is point symmetric at the point where this curve
51 * reaches 0.85 * Wmax, it would take 2 * K' seconds to reach Wmax.
52 *
53 * Therefore, by amortizing the two modes, the congestion period of Cubic with fast convergence is calculated as:
54 *
55 * bytes_per_mtu_increase = ((1 + 0.85^(1/3) * 2) / 2) * K * MTU / (0.3 * RTT_at_Wmax)
56 */
57 uint32_t cubic = 1.447 / 0.3 * 1000 * cbrt(0.3 / 0.4 * cwnd / mtu) / rtt * mtu;
58
59 return reno < cubic ? reno : cubic;
60 }
61
62 /* TODO: Avoid increase if sender was application limited. */
pico_on_acked(quicly_cc_t * cc,const quicly_loss_t * loss,uint32_t bytes,uint64_t largest_acked,uint32_t inflight,uint64_t next_pn,int64_t now,uint32_t max_udp_payload_size)63 static void pico_on_acked(quicly_cc_t *cc, const quicly_loss_t *loss, uint32_t bytes, uint64_t largest_acked, uint32_t inflight,
64 uint64_t next_pn, int64_t now, uint32_t max_udp_payload_size)
65 {
66 assert(inflight >= bytes);
67
68 /* Do not increase congestion window while in recovery. */
69 if (largest_acked < cc->recovery_end)
70 return;
71
72 cc->state.pico.stash += bytes;
73
74 /* Calculate the amount of bytes required to be acked for incrementing CWND by one MTU. */
75 uint32_t bytes_per_mtu_increase;
76 if (cc->cwnd < cc->ssthresh) {
77 bytes_per_mtu_increase = max_udp_payload_size;
78 } else {
79 bytes_per_mtu_increase = cc->state.pico.bytes_per_mtu_increase;
80 }
81
82 /* Bail out if we do not yet have enough bytes being acked. */
83 if (cc->state.pico.stash < bytes_per_mtu_increase)
84 return;
85
86 /* Update CWND, reducing stash relative to the amount we've adjusted the CWND */
87 uint32_t count = cc->state.pico.stash / bytes_per_mtu_increase;
88 cc->cwnd += count * max_udp_payload_size;
89 cc->state.pico.stash -= count * bytes_per_mtu_increase;
90
91 if (cc->cwnd_maximum < cc->cwnd)
92 cc->cwnd_maximum = cc->cwnd;
93 }
94
pico_on_lost(quicly_cc_t * cc,const quicly_loss_t * loss,uint32_t bytes,uint64_t lost_pn,uint64_t next_pn,int64_t now,uint32_t max_udp_payload_size)95 static void pico_on_lost(quicly_cc_t *cc, const quicly_loss_t *loss, uint32_t bytes, uint64_t lost_pn, uint64_t next_pn,
96 int64_t now, uint32_t max_udp_payload_size)
97 {
98 /* Nothing to do if loss is in recovery window. */
99 if (lost_pn < cc->recovery_end)
100 return;
101 cc->recovery_end = next_pn;
102
103 ++cc->num_loss_episodes;
104 if (cc->cwnd_exiting_slow_start == 0)
105 cc->cwnd_exiting_slow_start = cc->cwnd;
106
107 /* Calculate increase rate. */
108 cc->state.pico.bytes_per_mtu_increase = calc_bytes_per_mtu_increase(cc->cwnd, loss->rtt.smoothed, max_udp_payload_size);
109
110 /* Reduce congestion window. */
111 cc->cwnd *= QUICLY_RENO_BETA;
112 if (cc->cwnd < QUICLY_MIN_CWND * max_udp_payload_size)
113 cc->cwnd = QUICLY_MIN_CWND * max_udp_payload_size;
114 cc->ssthresh = cc->cwnd;
115
116 if (cc->cwnd_minimum > cc->cwnd)
117 cc->cwnd_minimum = cc->cwnd;
118 }
119
pico_on_persistent_congestion(quicly_cc_t * cc,const quicly_loss_t * loss,int64_t now)120 static void pico_on_persistent_congestion(quicly_cc_t *cc, const quicly_loss_t *loss, int64_t now)
121 {
122 /* TODO */
123 }
124
pico_on_sent(quicly_cc_t * cc,const quicly_loss_t * loss,uint32_t bytes,int64_t now)125 static void pico_on_sent(quicly_cc_t *cc, const quicly_loss_t *loss, uint32_t bytes, int64_t now)
126 {
127 /* Unused */
128 }
129
pico_init_pico_state(quicly_cc_t * cc,uint32_t stash)130 static void pico_init_pico_state(quicly_cc_t *cc, uint32_t stash)
131 {
132 cc->state.pico.stash = stash;
133 cc->state.pico.bytes_per_mtu_increase = cc->cwnd * QUICLY_RENO_BETA; /* use Reno, for simplicity */
134 }
135
pico_reset(quicly_cc_t * cc,uint32_t initcwnd)136 static void pico_reset(quicly_cc_t *cc, uint32_t initcwnd)
137 {
138 *cc = (quicly_cc_t){
139 .type = &quicly_cc_type_pico,
140 .cwnd = initcwnd,
141 .cwnd_initial = initcwnd,
142 .cwnd_maximum = initcwnd,
143 .cwnd_minimum = UINT32_MAX,
144 .ssthresh = UINT32_MAX,
145 };
146 pico_init_pico_state(cc, 0);
147 }
148
pico_on_switch(quicly_cc_t * cc)149 static int pico_on_switch(quicly_cc_t *cc)
150 {
151 if (cc->type == &quicly_cc_type_pico) {
152 return 1; /* nothing to do */
153 } else if (cc->type == &quicly_cc_type_reno) {
154 cc->type = &quicly_cc_type_pico;
155 pico_init_pico_state(cc, cc->state.reno.stash);
156 return 1;
157 } else if (cc->type == &quicly_cc_type_cubic) {
158 /* When in slow start, state can be reused as-is; otherwise, restart. */
159 if (cc->cwnd_exiting_slow_start == 0) {
160 cc->type = &quicly_cc_type_pico;
161 pico_init_pico_state(cc, 0);
162 } else {
163 pico_reset(cc, cc->cwnd_initial);
164 }
165 return 1;
166 }
167
168 return 0;
169 }
170
pico_init(quicly_init_cc_t * self,quicly_cc_t * cc,uint32_t initcwnd,int64_t now)171 static void pico_init(quicly_init_cc_t *self, quicly_cc_t *cc, uint32_t initcwnd, int64_t now)
172 {
173 pico_reset(cc, initcwnd);
174 }
175
176 quicly_cc_type_t quicly_cc_type_pico = {
177 "pico", &quicly_cc_pico_init, pico_on_acked, pico_on_lost, pico_on_persistent_congestion, pico_on_sent, pico_on_switch};
178 quicly_init_cc_t quicly_cc_pico_init = {pico_init};
179