1 /* 2 * ngtcp2 3 * 4 * Copyright (c) 2018 ngtcp2 contributors 5 * 6 * Permission is hereby granted, free of charge, to any person obtaining 7 * a copy of this software and associated documentation files (the 8 * "Software"), to deal in the Software without restriction, including 9 * without limitation the rights to use, copy, modify, merge, publish, 10 * distribute, sublicense, and/or sell copies of the Software, and to 11 * permit persons to whom the Software is furnished to do so, subject to 12 * the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be 15 * included in all copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 21 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 22 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 23 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 24 */ 25 #ifndef NGTCP2_CC_H 26 #define NGTCP2_CC_H 27 28 #ifdef HAVE_CONFIG_H 29 # include <config.h> 30 #endif /* HAVE_CONFIG_H */ 31 32 #include <ngtcp2/ngtcp2.h> 33 34 #define NGTCP2_LOSS_REDUCTION_FACTOR_BITS 1 35 #define NGTCP2_PERSISTENT_CONGESTION_THRESHOLD 3 36 37 typedef struct ngtcp2_log ngtcp2_log; 38 39 /** 40 * @struct 41 * 42 * :type:`ngtcp2_cc_base` is the base structure of custom congestion 43 * control algorithm. It must be the first field of custom congestion 44 * controller. 45 */ 46 typedef struct ngtcp2_cc_base { 47 /** 48 * :member:`log` is ngtcp2 library internal logger. 49 */ 50 ngtcp2_log *log; 51 } ngtcp2_cc_base; 52 53 /** 54 * @struct 55 * 56 * :type:`ngtcp2_cc_pkt` is a convenient structure to include 57 * acked/lost/sent packet. 58 */ 59 typedef struct ngtcp2_cc_pkt { 60 /** 61 * :member:`pkt_num` is the packet number 62 */ 63 int64_t pkt_num; 64 /** 65 * :member:`pktlen` is the length of packet. 66 */ 67 size_t pktlen; 68 /** 69 * :member:`pktns_id` is the ID of packet number space which this 70 * packet belongs to. 71 */ 72 ngtcp2_pktns_id pktns_id; 73 /** 74 * :member:`sent_ts` is the timestamp when packet is sent. 75 */ 76 ngtcp2_tstamp sent_ts; 77 /** 78 * :member:`lost` is the number of bytes lost when this packet was 79 * sent. 80 */ 81 uint64_t lost; 82 /** 83 * :member:`tx_in_flight` is the bytes in flight when this packet 84 * was sent. 85 */ 86 uint64_t tx_in_flight; 87 /** 88 * :member:`is_app_limited` is nonzero if the connection is 89 * app-limited when this packet was sent. 90 */ 91 int is_app_limited; 92 } ngtcp2_cc_pkt; 93 94 /** 95 * @struct 96 * 97 * :type:`ngtcp2_cc_ack` is a convenient structure which stores 98 * acknowledged and lost bytes. 99 */ 100 typedef struct ngtcp2_cc_ack { 101 /** 102 * :member:`prior_bytes_in_flight` is the in-flight bytes before 103 * processing this ACK. 104 */ 105 uint64_t prior_bytes_in_flight; 106 /** 107 * :member:`bytes_delivered` is the number of bytes acknowledged. 108 */ 109 uint64_t bytes_delivered; 110 /** 111 * :member:`bytes_lost` is the number of bytes declared lost. 112 */ 113 uint64_t bytes_lost; 114 /** 115 * :member:`pkt_delivered` is the cumulative acknowledged bytes when 116 * the last packet acknowledged by this ACK was sent. 117 */ 118 uint64_t pkt_delivered; 119 /** 120 * :member:`largest_acked_sent_ts` is the time when the largest 121 * acknowledged packet was sent. 122 */ 123 ngtcp2_tstamp largest_acked_sent_ts; 124 /** 125 * :member:`rtt` is the RTT sample. It is UINT64_MAX if no RTT 126 * sample is available. 127 */ 128 ngtcp2_duration rtt; 129 } ngtcp2_cc_ack; 130 131 typedef struct ngtcp2_cc ngtcp2_cc; 132 133 /** 134 * @functypedef 135 * 136 * :type:`ngtcp2_cc_on_pkt_acked` is a callback function which is 137 * called with an acknowledged packet. 138 */ 139 typedef void (*ngtcp2_cc_on_pkt_acked)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 140 const ngtcp2_cc_pkt *pkt, 141 ngtcp2_tstamp ts); 142 143 /** 144 * @functypedef 145 * 146 * :type:`ngtcp2_cc_on_pkt_lost` is a callback function which is 147 * called with a lost packet. 148 */ 149 typedef void (*ngtcp2_cc_on_pkt_lost)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 150 const ngtcp2_cc_pkt *pkt, 151 ngtcp2_tstamp ts); 152 /** 153 * @functypedef 154 * 155 * :type:`ngtcp2_cc_congestion_event` is a callback function which is 156 * called when congestion event happens (e.g., when packet is lost). 157 */ 158 typedef void (*ngtcp2_cc_congestion_event)(ngtcp2_cc *cc, 159 ngtcp2_conn_stat *cstat, 160 ngtcp2_tstamp sent_ts, 161 ngtcp2_tstamp ts); 162 163 /** 164 * @functypedef 165 * 166 * :type:`ngtcp2_cc_on_spurious_congestion` is a callback function 167 * which is called when a spurious congestion is detected. 168 */ 169 typedef void (*ngtcp2_cc_on_spurious_congestion)(ngtcp2_cc *cc, 170 ngtcp2_conn_stat *cstat, 171 ngtcp2_tstamp ts); 172 173 /** 174 * @functypedef 175 * 176 * :type:`ngtcp2_cc_on_persistent_congestion` is a callback function 177 * which is called when persistent congestion is established. 178 */ 179 typedef void (*ngtcp2_cc_on_persistent_congestion)(ngtcp2_cc *cc, 180 ngtcp2_conn_stat *cstat, 181 ngtcp2_tstamp ts); 182 183 /** 184 * @functypedef 185 * 186 * :type:`ngtcp2_cc_on_ack_recv` is a callback function which is 187 * called when an acknowledgement is received. 188 */ 189 typedef void (*ngtcp2_cc_on_ack_recv)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 190 const ngtcp2_cc_ack *ack, 191 ngtcp2_tstamp ts); 192 193 /** 194 * @functypedef 195 * 196 * :type:`ngtcp2_cc_on_pkt_sent` is a callback function which is 197 * called when an ack-eliciting packet is sent. 198 */ 199 typedef void (*ngtcp2_cc_on_pkt_sent)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 200 const ngtcp2_cc_pkt *pkt); 201 202 /** 203 * @functypedef 204 * 205 * :type:`ngtcp2_cc_new_rtt_sample` is a callback function which is 206 * called when new RTT sample is obtained. 207 */ 208 typedef void (*ngtcp2_cc_new_rtt_sample)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 209 ngtcp2_tstamp ts); 210 211 /** 212 * @functypedef 213 * 214 * :type:`ngtcp2_cc_reset` is a callback function which is called when 215 * congestion state must be reset. 216 */ 217 typedef void (*ngtcp2_cc_reset)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 218 ngtcp2_tstamp ts); 219 220 /** 221 * @enum 222 * 223 * :type:`ngtcp2_cc_event_type` defines congestion control events. 224 */ 225 typedef enum ngtcp2_cc_event_type { 226 /** 227 * :enum:`NGTCP2_CC_EVENT_TX_START` occurs when ack-eliciting packet 228 * is sent and no other ack-eliciting packet is present. 229 */ 230 NGTCP2_CC_EVENT_TYPE_TX_START 231 } ngtcp2_cc_event_type; 232 233 /** 234 * @functypedef 235 * 236 * :type:`ngtcp2_cc_event` is a callback function which is called when 237 * a specific event happens. 238 */ 239 typedef void (*ngtcp2_cc_event)(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 240 ngtcp2_cc_event_type event, ngtcp2_tstamp ts); 241 242 /** 243 * @struct 244 * 245 * :type:`ngtcp2_cc` is congestion control algorithm interface to 246 * allow custom implementation. 247 */ 248 typedef struct ngtcp2_cc { 249 /** 250 * :member:`ccb` is a pointer to :type:`ngtcp2_cc_base` which 251 * usually contains a state. 252 */ 253 ngtcp2_cc_base *ccb; 254 /** 255 * :member:`on_pkt_acked` is a callback function which is called 256 * when a packet is acknowledged. 257 */ 258 ngtcp2_cc_on_pkt_acked on_pkt_acked; 259 /** 260 * :member:`on_pkt_lost` is a callback function which is called when 261 * a packet is lost. 262 */ 263 ngtcp2_cc_on_pkt_lost on_pkt_lost; 264 /** 265 * :member:`congestion_event` is a callback function which is called 266 * when congestion event happens (.e.g, packet is lost). 267 */ 268 ngtcp2_cc_congestion_event congestion_event; 269 /** 270 * :member:`on_spurious_congestion` is a callback function which is 271 * called when a spurious congestion is detected. 272 */ 273 ngtcp2_cc_on_spurious_congestion on_spurious_congestion; 274 /** 275 * :member:`on_persistent_congestion` is a callback function which 276 * is called when persistent congestion is established. 277 */ 278 ngtcp2_cc_on_persistent_congestion on_persistent_congestion; 279 /** 280 * :member:`on_ack_recv` is a callback function which is called when 281 * an acknowledgement is received. 282 */ 283 ngtcp2_cc_on_ack_recv on_ack_recv; 284 /** 285 * :member:`on_pkt_sent` is a callback function which is called when 286 * ack-eliciting packet is sent. 287 */ 288 ngtcp2_cc_on_pkt_sent on_pkt_sent; 289 /** 290 * :member:`new_rtt_sample` is a callback function which is called 291 * when new RTT sample is obtained. 292 */ 293 ngtcp2_cc_new_rtt_sample new_rtt_sample; 294 /** 295 * :member:`reset` is a callback function which is called when 296 * congestion control state must be reset. 297 */ 298 ngtcp2_cc_reset reset; 299 /** 300 * :member:`event` is a callback function which is called when a 301 * specific event happens. 302 */ 303 ngtcp2_cc_event event; 304 } ngtcp2_cc; 305 306 /* 307 * ngtcp2_cc_compute_initcwnd computes initial cwnd. 308 */ 309 uint64_t ngtcp2_cc_compute_initcwnd(size_t max_packet_size); 310 311 ngtcp2_cc_pkt *ngtcp2_cc_pkt_init(ngtcp2_cc_pkt *pkt, int64_t pkt_num, 312 size_t pktlen, ngtcp2_pktns_id pktns_id, 313 ngtcp2_tstamp sent_ts, uint64_t lost, 314 uint64_t tx_in_flight, int is_app_limited); 315 316 /* ngtcp2_reno_cc is the RENO congestion controller. */ 317 typedef struct ngtcp2_reno_cc { 318 ngtcp2_cc_base ccb; 319 uint64_t max_delivery_rate_sec; 320 uint64_t target_cwnd; 321 uint64_t pending_add; 322 } ngtcp2_reno_cc; 323 324 int ngtcp2_cc_reno_cc_init(ngtcp2_cc *cc, ngtcp2_log *log, 325 const ngtcp2_mem *mem); 326 327 void ngtcp2_cc_reno_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem); 328 329 void ngtcp2_reno_cc_init(ngtcp2_reno_cc *cc, ngtcp2_log *log); 330 331 void ngtcp2_reno_cc_free(ngtcp2_reno_cc *cc); 332 333 void ngtcp2_cc_reno_cc_on_pkt_acked(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 334 const ngtcp2_cc_pkt *pkt, ngtcp2_tstamp ts); 335 336 void ngtcp2_cc_reno_cc_congestion_event(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 337 ngtcp2_tstamp sent_ts, 338 ngtcp2_tstamp ts); 339 340 void ngtcp2_cc_reno_cc_on_persistent_congestion(ngtcp2_cc *cc, 341 ngtcp2_conn_stat *cstat, 342 ngtcp2_tstamp ts); 343 344 void ngtcp2_cc_reno_cc_on_ack_recv(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 345 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts); 346 347 void ngtcp2_cc_reno_cc_reset(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 348 ngtcp2_tstamp ts); 349 350 /* ngtcp2_cubic_cc is CUBIC congestion controller. */ 351 typedef struct ngtcp2_cubic_cc { 352 ngtcp2_cc_base ccb; 353 uint64_t max_delivery_rate_sec; 354 uint64_t target_cwnd; 355 uint64_t w_last_max; 356 uint64_t w_tcp; 357 uint64_t origin_point; 358 ngtcp2_tstamp epoch_start; 359 uint64_t k; 360 /* prior stores the congestion state when a congestion event occurs 361 in order to restore the state when it turns out that the event is 362 spurious. */ 363 struct { 364 uint64_t cwnd; 365 uint64_t ssthresh; 366 uint64_t w_last_max; 367 uint64_t w_tcp; 368 uint64_t origin_point; 369 ngtcp2_tstamp epoch_start; 370 uint64_t k; 371 } prior; 372 /* HyStart++ variables */ 373 size_t rtt_sample_count; 374 uint64_t current_round_min_rtt; 375 uint64_t last_round_min_rtt; 376 int64_t window_end; 377 uint64_t pending_add; 378 uint64_t pending_w_add; 379 } ngtcp2_cubic_cc; 380 381 int ngtcp2_cc_cubic_cc_init(ngtcp2_cc *cc, ngtcp2_log *log, 382 const ngtcp2_mem *mem); 383 384 void ngtcp2_cc_cubic_cc_free(ngtcp2_cc *cc, const ngtcp2_mem *mem); 385 386 void ngtcp2_cubic_cc_init(ngtcp2_cubic_cc *cc, ngtcp2_log *log); 387 388 void ngtcp2_cubic_cc_free(ngtcp2_cubic_cc *cc); 389 390 void ngtcp2_cc_cubic_cc_on_pkt_acked(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 391 const ngtcp2_cc_pkt *pkt, 392 ngtcp2_tstamp ts); 393 394 void ngtcp2_cc_cubic_cc_congestion_event(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 395 ngtcp2_tstamp sent_ts, 396 ngtcp2_tstamp ts); 397 398 void ngtcp2_cc_cubic_cc_on_spurious_congestion(ngtcp2_cc *ccx, 399 ngtcp2_conn_stat *cstat, 400 ngtcp2_tstamp ts); 401 402 void ngtcp2_cc_cubic_cc_on_persistent_congestion(ngtcp2_cc *cc, 403 ngtcp2_conn_stat *cstat, 404 ngtcp2_tstamp ts); 405 406 void ngtcp2_cc_cubic_cc_on_ack_recv(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 407 const ngtcp2_cc_ack *ack, ngtcp2_tstamp ts); 408 409 void ngtcp2_cc_cubic_cc_on_pkt_sent(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 410 const ngtcp2_cc_pkt *pkt); 411 412 void ngtcp2_cc_cubic_cc_new_rtt_sample(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 413 ngtcp2_tstamp ts); 414 415 void ngtcp2_cc_cubic_cc_reset(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 416 ngtcp2_tstamp ts); 417 418 void ngtcp2_cc_cubic_cc_event(ngtcp2_cc *cc, ngtcp2_conn_stat *cstat, 419 ngtcp2_cc_event_type event, ngtcp2_tstamp ts); 420 421 #endif /* NGTCP2_CC_H */ 422