1 // Copyright (C) 2021, Cloudflare, Inc. 2 // All rights reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are 6 // met: 7 // 8 // * Redistributions of source code must retain the above copyright notice, 9 // this list of conditions and the following disclaimer. 10 // 11 // * Redistributions in binary form must reproduce the above copyright 12 // notice, this list of conditions and the following disclaimer in the 13 // documentation and/or other materials provided with the distribution. 14 // 15 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS 16 // IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 17 // THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 18 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR 19 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 20 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 21 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 22 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 23 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 24 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 25 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27 //! Proportional Rate Reduction 28 //! 29 //! This implementation is based on the following RFC: 30 //! 31 //! <https://datatracker.ietf.org/doc/html/rfc6937> 32 33 use std::cmp; 34 35 #[derive(Default, Debug)] 36 pub struct PRR { 37 // Total bytes delivered during recovery. 38 prr_delivered: usize, 39 40 // FlightSize at the start of recovery. 41 recoverfs: usize, 42 43 // Total bytes sent during recovery. 44 prr_out: usize, 45 46 // Total additional bytes can be sent for retransmit during recovery. 47 pub snd_cnt: usize, 48 } 49 50 impl PRR { on_packet_sent(&mut self, sent_bytes: usize)51 pub fn on_packet_sent(&mut self, sent_bytes: usize) { 52 self.prr_out += sent_bytes; 53 54 self.snd_cnt = self.snd_cnt.saturating_sub(sent_bytes); 55 } 56 congestion_event(&mut self, bytes_in_flight: usize)57 pub fn congestion_event(&mut self, bytes_in_flight: usize) { 58 self.prr_delivered = 0; 59 60 self.recoverfs = bytes_in_flight; 61 62 self.prr_out = 0; 63 64 self.snd_cnt = 0; 65 } 66 on_packet_acked( &mut self, delivered_data: usize, pipe: usize, ssthresh: usize, max_datagram_size: usize, )67 pub fn on_packet_acked( 68 &mut self, delivered_data: usize, pipe: usize, ssthresh: usize, 69 max_datagram_size: usize, 70 ) { 71 self.prr_delivered += delivered_data; 72 73 self.snd_cnt = if pipe > ssthresh { 74 // Proportional Rate Reduction. 75 if self.recoverfs > 0 { 76 ((self.prr_delivered * ssthresh + self.recoverfs - 1) / 77 self.recoverfs) 78 .saturating_sub(self.prr_out) 79 } else { 80 0 81 } 82 } else { 83 // PRR-SSRB. 84 let limit = cmp::max( 85 self.prr_delivered.saturating_sub(self.prr_out), 86 delivered_data, 87 ) + max_datagram_size; 88 89 // Attempt to catch up, as permitted by limit 90 cmp::min(ssthresh - pipe, limit) 91 }; 92 93 // snd_cnt should be a positive number. 94 self.snd_cnt = cmp::max(self.snd_cnt, 0); 95 } 96 } 97 98 #[cfg(test)] 99 mod tests { 100 use super::*; 101 102 #[test] congestion_event()103 fn congestion_event() { 104 let mut prr = PRR::default(); 105 let bytes_in_flight = 1000; 106 107 prr.congestion_event(bytes_in_flight); 108 109 assert_eq!(prr.recoverfs, bytes_in_flight); 110 assert_eq!(prr.snd_cnt, 0); 111 } 112 113 #[test] on_packet_sent()114 fn on_packet_sent() { 115 let mut prr = PRR::default(); 116 let bytes_in_flight = 1000; 117 let bytes_sent = 500; 118 119 prr.congestion_event(bytes_in_flight); 120 121 prr.on_packet_sent(bytes_sent); 122 123 assert_eq!(prr.prr_out, bytes_sent); 124 assert_eq!(prr.snd_cnt, 0); 125 } 126 127 #[test] on_packet_acked_prr()128 fn on_packet_acked_prr() { 129 let mut prr = PRR::default(); 130 let max_datagram_size = 1000; 131 let bytes_in_flight = max_datagram_size * 10; 132 let ssthresh = bytes_in_flight / 2; 133 let acked = 1000; 134 135 prr.congestion_event(bytes_in_flight); 136 137 // pipe > ssthresh uses PRR algorithm. 138 let pipe = bytes_in_flight; 139 140 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 141 142 assert_eq!(prr.snd_cnt, 500); 143 144 let snd_cnt = prr.snd_cnt; 145 146 // send one more allowed by snd_cnt 147 prr.on_packet_sent(snd_cnt); 148 149 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 150 151 assert_eq!(prr.snd_cnt, 500); 152 } 153 154 #[test] on_packet_acked_prr_overflow()155 fn on_packet_acked_prr_overflow() { 156 let mut prr = PRR::default(); 157 let max_datagram_size = 1000; 158 let bytes_in_flight = max_datagram_size * 10; 159 let ssthresh = bytes_in_flight / 2; 160 let acked = 1000; 161 162 prr.congestion_event(bytes_in_flight); 163 164 prr.on_packet_sent(max_datagram_size); 165 166 // pipe > ssthresh uses PRR algorithm. 167 let pipe = bytes_in_flight + max_datagram_size; 168 169 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 170 171 assert_eq!(prr.snd_cnt, 0); 172 } 173 174 #[test] on_packet_acked_prr_zero_in_flight()175 fn on_packet_acked_prr_zero_in_flight() { 176 let mut prr = PRR::default(); 177 let max_datagram_size = 1000; 178 let bytes_in_flight = 0; 179 let ssthresh = 3000; 180 let acked = 1000; 181 182 prr.congestion_event(bytes_in_flight); 183 184 // pipe > ssthresh uses PRR algorithm. 185 let pipe = ssthresh + 1000; 186 187 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 188 189 assert_eq!(prr.snd_cnt, 0); 190 } 191 192 #[test] on_packet_acked_prr_ssrb()193 fn on_packet_acked_prr_ssrb() { 194 let mut prr = PRR::default(); 195 let max_datagram_size = 1000; 196 let bytes_in_flight = max_datagram_size * 10; 197 let ssthresh = bytes_in_flight / 2; 198 let acked = 1000; 199 200 prr.congestion_event(bytes_in_flight); 201 202 // pipe <= ssthresh uses PRR-SSRB algorithm. 203 let pipe = max_datagram_size; 204 205 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 206 207 assert_eq!(prr.snd_cnt, 2000); 208 209 let snd_cnt = prr.snd_cnt; 210 211 // send one more allowed by snd_cnt 212 prr.on_packet_sent(snd_cnt); 213 214 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 215 216 assert_eq!(prr.snd_cnt, 2000); 217 } 218 219 #[test] on_packet_acked_prr_ssrb_overflow()220 fn on_packet_acked_prr_ssrb_overflow() { 221 let mut prr = PRR::default(); 222 let max_datagram_size = 1000; 223 let bytes_in_flight = max_datagram_size * 10; 224 let ssthresh = bytes_in_flight / 2; 225 let acked = 500; 226 227 prr.congestion_event(bytes_in_flight); 228 229 // pipe <= ssthresh uses PRR-SSRB algorithm. 230 let pipe = max_datagram_size; 231 232 prr.on_packet_sent(max_datagram_size); 233 234 prr.on_packet_acked(acked, pipe, ssthresh, max_datagram_size); 235 236 assert_eq!(prr.snd_cnt, 1500); 237 } 238 } 239