1 /*
2  *  send_control.cpp
3  *  congestion control logic for the swift protocol
4  *
5  *  Created by Victor Grishchenko on 12/10/09.
6  *  Copyright 2009-2016 TECHNISCHE UNIVERSITEIT DELFT. All rights reserved.
7  *
8  */
9 
10 #include "swift.h"
11 #include <cassert>
12 
13 using namespace swift;
14 using namespace std;
15 
16 tint Channel::MIN_DEV = 50*TINT_MSEC;
17 tint Channel::MAX_SEND_INTERVAL = TINT_SEC*58;
18 //const uint32_t Channel::LEDBAT_BASE_HISTORY = 10;
19 uint32_t Channel::LEDBAT_ROLLOVER = TINT_SEC*30;
20 tint Channel::LEDBAT_TARGET = TINT_MSEC*25;
21 float Channel::LEDBAT_GAIN = 1.0/LEDBAT_TARGET;
22 tint Channel::LEDBAT_DELAY_BIN = TINT_SEC*30;
23 tint Channel::MAX_POSSIBLE_RTT = TINT_SEC*10;
24 const char* Channel::SEND_CONTROL_MODES[] = {"keepalive", "pingpong",
25                                              "slowstart", "standard_aimd", "ledbat", "closing"
26                                             };
27 
28 
NextSendTime()29 tint Channel::NextSendTime()
30 {
31     TimeoutDataOut(); // precaution to know free cwnd
32     switch (send_control_) {
33     case KEEP_ALIVE_CONTROL:
34         return KeepAliveNextSendTime();
35     case PING_PONG_CONTROL:
36         return PingPongNextSendTime();
37     case SLOW_START_CONTROL:
38         return SlowStartNextSendTime();
39     case AIMD_CONTROL:
40         return AimdNextSendTime();
41     case LEDBAT_CONTROL:
42         return LedbatNextSendTime();
43     case CLOSE_CONTROL:
44         return TINT_NEVER;
45     default:
46         fprintf(stderr,"send_control.cpp: unknown control %d\n", send_control_);
47         return TINT_NEVER;
48     }
49 }
50 
SwitchSendControl(send_control_t control_mode)51 tint Channel::SwitchSendControl(send_control_t control_mode)
52 {
53     dprintf("%s #%" PRIu32 " sendctrl switch %s->%s\n",tintstr(),id(),
54             SEND_CONTROL_MODES[send_control_],SEND_CONTROL_MODES[control_mode]);
55     switch (control_mode) {
56     case KEEP_ALIVE_CONTROL:
57         send_interval_ = rtt_avg_; //max(TINT_SEC/10,rtt_avg_);
58         if (keepalivereason_ != NOTHING_TO_SEND) { // && data_out_.size() == 0) {
59             cwnd_ = 1;
60             dev_avg_ = max(TINT_SEC,rtt_avg_);
61             data_out_cap_ = bin_t::ALL;
62         }
63         break;
64     case PING_PONG_CONTROL:
65         dev_avg_ = max(TINT_SEC,rtt_avg_);
66         data_out_cap_ = bin_t::ALL;
67         cwnd_ = 1;
68         break;
69     case SLOW_START_CONTROL:
70 // Ric: TODO test
71         cwnd_ = 4;
72         break;
73     case AIMD_CONTROL:
74         break;
75     case LEDBAT_CONTROL:
76         break;
77     case CLOSE_CONTROL:
78         break;
79     default:
80         assert(false);
81         break;
82     }
83     send_control_ = control_mode;
84     return NextSendTime();
85 }
86 
KeepAliveNextSendTime()87 tint Channel::KeepAliveNextSendTime()
88 {
89     if (sent_since_recv_>=3 && last_recv_time_<NOW-3*MAX_SEND_INTERVAL) {
90         lprintf("\t\t==== Switch to Close Control ==== \n");
91         return SwitchSendControl(CLOSE_CONTROL);
92     }
93     if (ack_rcvd_recent_ && hint_in_size_) {
94         if (keepalivereason_==NOTHING_TO_SEND) {
95             lprintf("\t\t==== Switch back to LEDBAT ==== \n");
96             keepalivereason_ = NONE;
97             return SwitchSendControl(LEDBAT_CONTROL);
98         } else {
99             lprintf("\t\t==== Switch to Slow Start Control ==== \n");
100             return SwitchSendControl(SLOW_START_CONTROL);
101         }
102     }
103     if (data_in_.time!=TINT_NEVER)
104         return NOW;
105 
106     if (live_have_no_hint_) {
107         live_have_no_hint_ = false;
108         return NOW;
109     }
110     /* Gertjan fix 5f51e5451e3785a74c058d9651b2d132c5a94557
111     "Do not increase send interval in keep-alive mode when previous Reschedule
112     was already in the future.
113     The problem this solves is that when we keep on receiving packets in keep-alive
114     mode, the next packet will be pushed further and further into the future, which is
115     not what we want. The scheduled time for the next packet should be unchanged
116     on reception."
117     */
118     if (!reverse_pex_out_.empty())
119         return reverse_pex_out_.front().time;
120 
121     // Arno: Fix that doesn't do exponential growth always, only after sends
122     // without following recvs
123 
124     //dprintf("KeepAliveNextSendTime: gotka %d sentka %d ss %d si %" PRIi64 " rtt %" PRIi64 "\n", lastrecvwaskeepalive_, lastsendwaskeepalive_, sent_since_recv_, send_interval_, rtt_avg_ );
125 
126     if (lastrecvwaskeepalive_ && lastsendwaskeepalive_) {
127         send_interval_ <<= 1;
128     } else if (lastrecvwaskeepalive_ || lastsendwaskeepalive_) {
129         // Arno, 2011-11-29: we like eachother again, start fresh
130         // Arno, 2012-01-25: Unless we're talking to a dead peer.
131         if (sent_since_recv_ < 4) {
132             send_interval_ = rtt_avg_;
133         } else
134             send_interval_ <<= 1;
135     } else if (sent_since_recv_ <= 1) {
136         send_interval_ = rtt_avg_;
137     } else if (sent_since_recv_ > 1) {
138         send_interval_ <<= 1;
139     }
140     if (send_interval_>MAX_SEND_INTERVAL)
141         send_interval_ = MAX_SEND_INTERVAL;
142     return last_send_time_ + send_interval_;
143 }
144 
PingPongNextSendTime()145 tint Channel::PingPongNextSendTime()    // FIXME INFINITE LOOP
146 {
147     //fprintf(stderr,"PING: dgrams %d ackrec %d dataintime %" PRIi64 " lastrecv %" PRIi64 " lastsend %" PRIi64 "\n", dgrams_sent_, ack_rcvd_recent_, data_in_.time, last_recv_time_, last_send_time_);
148     if (dgrams_sent_>=10) {
149         lprintf("\t\t==== Switch to Keep Alive Control (dgrams_sent_>=10) ==== \n");
150         return SwitchSendControl(KEEP_ALIVE_CONTROL);
151     }
152     if (ack_rcvd_recent_) {
153         lprintf("\t\t==== Switch to Slow Start Control ==== \n");
154         return SwitchSendControl(SLOW_START_CONTROL);
155     }
156     if (data_in_.time!=TINT_NEVER)
157         return NOW;
158     if (last_recv_time_>last_send_time_)
159         return NOW;
160     if (!last_send_time_)
161         return NOW;
162     return last_send_time_ + ack_timeout(); // timeout
163 }
164 
CwndRateNextSendTime()165 tint Channel::CwndRateNextSendTime()
166 {
167     if (data_in_.time!=TINT_NEVER)
168         return NOW; // TODO: delayed ACKs
169     if (last_recv_time_<NOW-rtt_avg_*8) {
170         lprintf("\t\t==== Switch to Keep Alive Control (last_recv_time_<NOW-rtt_avg_*8) ==== \n");
171         return SwitchSendControl(KEEP_ALIVE_CONTROL);
172     }
173     send_interval_ = rtt_avg_/cwnd_;
174     if (send_interval_>max(rtt_avg_,TINT_SEC)*4) {
175         lprintf("\t\t==== Switch to Keep Alive Control (send_interval_>max(rtt_avg_,TINT_SEC)*4) ==== \n");
176         return SwitchSendControl(KEEP_ALIVE_CONTROL);
177     }
178     // Ric: test
179     /*
180     if (data_out_size_<(int)cwnd_) {
181         dprintf("%s #%" PRIu32 " sendctrl send interval %" PRIi64 "us (cwnd %.2f, data_out %" PRIu32 ")\n",
182                 tintstr(),id_,send_interval_,cwnd_,data_out_size_);
183         return last_data_out_time_ + send_interval_ - timer_delay_;
184     } else {
185         dprintf("%s #%" PRIu32 " sendctrl avoid sending (cwnd %.2f, data_out %" PRIu32 ")\n",
186                 tintstr(),id_,cwnd_,data_out_size_);
187         assert(data_out_.front().time!=TINT_NEVER);
188         return data_out_.front().time + ack_timeout();
189     }*/
190     // start test
191     if (data_out_size_<(int)cwnd_ || cwnd_ >= 1) {
192         dprintf("%s #%" PRIu32 " sendctrl send interval %" PRIi64 "us (cwnd %.2f, data_out %" PRIu32 ")\n",
193                 tintstr(),id_,send_interval_,cwnd_,data_out_size_);
194         return last_data_out_time_ + send_interval_ - reschedule_delay_;
195     } else {
196         dprintf("%s #%" PRIu32 " sendctrl avoid sending (cwnd %.2f, data_out %" PRIu32 ")\n",
197                 tintstr(),id_,cwnd_,data_out_size_);
198         assert(data_out_.front().time!=TINT_NEVER);
199         return data_out_.front().time + ack_timeout();
200     }
201     // end-test
202 
203 }
204 
BackOffOnLosses(float ratio)205 void Channel::BackOffOnLosses(float ratio)
206 {
207     //ack_rcvd_recent_ = 0;
208     ack_not_rcvd_recent_ =  0;
209     if (last_loss_time_<NOW-rtt_avg_) {
210         cwnd_ *= ratio;
211         last_loss_time_ = NOW;
212         dprintf("%s #%" PRIu32 " sendctrl backoff %3.2f\n",tintstr(),id_,cwnd_);
213     }
214 }
215 
SlowStartNextSendTime()216 tint Channel::SlowStartNextSendTime()
217 {
218     if (ack_not_rcvd_recent_) {
219         BackOffOnLosses();
220         lprintf("\t\t==== Switch to LEDBAT Control (1) ==== \n");
221         return SwitchSendControl(LEDBAT_CONTROL);//AIMD_CONTROL);
222     }
223     // Ric: TODO test
224     // if (rtt_avg_/cwnd_<TINT_SEC/10) {
225     if (rtt_avg_/cwnd_<TINT_SEC/20) {
226         lprintf("\t\t==== Switch to LEDBAT Control (2) ==== \n");
227         return SwitchSendControl(LEDBAT_CONTROL);//AIMD_CONTROL);
228     }
229     cwnd_+=ack_rcvd_recent_;
230     ack_rcvd_recent_=0;
231     return CwndRateNextSendTime();
232 }
233 
AimdNextSendTime()234 tint Channel::AimdNextSendTime()
235 {
236     if (ack_not_rcvd_recent_)
237         BackOffOnLosses();
238     if (ack_rcvd_recent_) {
239         if (cwnd_>1)
240             cwnd_ += ack_rcvd_recent_/cwnd_;
241         else
242             cwnd_ *= 2;
243     }
244     ack_rcvd_recent_=0;
245     return CwndRateNextSendTime();
246 }
247 
LedbatNextSendTime()248 tint Channel::LedbatNextSendTime()
249 {
250 
251     if (ack_rcvd_recent_) {
252 
253         // reset the min value
254         owd_min_ = TINT_NEVER;
255 
256         // Ric: TODO for the moment we only use one sample!!
257         for (int i=0; i<10; i++) {
258             if (owd_min_>owd_min_bins_[i])
259                 owd_min_ = owd_min_bins_[i];
260         }
261 
262         // We may apply a filter over the elements.. as suggested in the rfc
263         ttqueue::iterator it = owd_current_.begin();
264         int32_t count = 0;
265         tint total = 0;
266         tint timeout = NOW - rtt_avg_;
267         // use the acks received during the last rtt, or at least 4 values
268         while (it != owd_current_.end() && (it->second > timeout || count < 4)) {
269             total += it->first;
270             count++;
271             it++;
272         }
273         owd_cur_ = total/count;
274 
275         dprintf("%s #%" PRIu32 " sendctrl using %" PRIi32 " samples from the last rtt value [%" PRIi64 "], current owd: %"
276                 PRIi64 "\n",
277                 tintstr(),id_,count, rtt_avg_, owd_cur_);
278 
279         if (ack_not_rcvd_recent_)
280             BackOffOnLosses(0.8);
281 
282         ack_rcvd_recent_ = 0;
283 
284         tint queueing_delay = owd_cur_ - owd_min_;
285         tint off_target = LEDBAT_TARGET - queueing_delay;
286         cwnd_ += LEDBAT_GAIN * off_target / cwnd_;
287         if (cwnd_<1)
288             cwnd_ = 1;
289         if (owd_cur_==TINT_NEVER || owd_min_==TINT_NEVER)
290 // Ric: TODO test
291             cwnd_ = 40;
292     }
293 
294     return CwndRateNextSendTime();
295 }
296 
297 
298 
299