src/libswift/send_control.cpp

   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-2012 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 tint Channel::LEDBAT_TARGET = TINT_MSEC*25;
  19 float Channel::LEDBAT_GAIN = 1.0/LEDBAT_TARGET;
  20 tint Channel::LEDBAT_DELAY_BIN = TINT_SEC*30;
  21 tint Channel::MAX_POSSIBLE_RTT = TINT_SEC*10;
  22 const char* Channel::SEND_CONTROL_MODES[] = {"keepalive", "pingpong",
  23     "slowstart", "standard_aimd", "ledbat", "closing"};
  24
  25
  26 tint    Channel::NextSendTime () {
  27     TimeoutDataOut(); // precaution to know free cwnd
  28     switch (send_control_) {
  29         case KEEP_ALIVE_CONTROL: return KeepAliveNextSendTime();
  30         case PING_PONG_CONTROL:  return PingPongNextSendTime();
  31         case SLOW_START_CONTROL: return SlowStartNextSendTime();
  32         case AIMD_CONTROL:       return AimdNextSendTime();
  33         case LEDBAT_CONTROL:     return LedbatNextSendTime();
  34         case CLOSE_CONTROL:      return TINT_NEVER;
  35         default:                 fprintf(stderr,"send_control.cpp: unknown control %d\n", send_control_); return TINT_NEVER;
  36     }
  37 }
  38
  39 tint    Channel::SwitchSendControl (int control_mode) {
  40     dprintf("%s #%u sendctrl switch %s->%s\n",tintstr(),id(),
  41             SEND_CONTROL_MODES[send_control_],SEND_CONTROL_MODES[control_mode]);
  42     switch (control_mode) {
  43         case KEEP_ALIVE_CONTROL:
  44             send_interval_ = rtt_avg_; //max(TINT_SEC/10,rtt_avg_);
  45             dev_avg_ = max(TINT_SEC,rtt_avg_);
  46             data_out_cap_ = bin_t::ALL;
  47             cwnd_ = 1;
  48             break;
  49         case PING_PONG_CONTROL:
  50             dev_avg_ = max(TINT_SEC,rtt_avg_);
  51             data_out_cap_ = bin_t::ALL;
  52             cwnd_ = 1;
  53             break;
  54         case SLOW_START_CONTROL:
  55             cwnd_ = 1;
  56             break;
  57         case AIMD_CONTROL:
  58             break;
  59         case LEDBAT_CONTROL:
  60             break;
  61         case CLOSE_CONTROL:
  62             break;
  63         default:
  64             assert(false);
  65     }
  66     send_control_ = control_mode;
  67     return NextSendTime();
  68 }
  69
  70 tint    Channel::KeepAliveNextSendTime () {
  71     if (sent_since_recv_>=3 && last_recv_time_<NOW-3*MAX_SEND_INTERVAL)
  72         return SwitchSendControl(CLOSE_CONTROL);
  73     if (ack_rcvd_recent_)
  74         return SwitchSendControl(SLOW_START_CONTROL);
  75     if (data_in_.time!=TINT_NEVER)
  76         return NOW;
  77         /* Gertjan fix 5f51e5451e3785a74c058d9651b2d132c5a94557
  78     "Do not increase send interval in keep-alive mode when previous Reschedule
  79     was already in the future.
  80     The problem this solves is that when we keep on receiving packets in keep-alive
  81     mode, the next packet will be pushed further and further into the future, which is
  82     not what we want. The scheduled time for the next packet should be unchanged
  83     on reception."
  84     */
  85     if (!reverse_pex_out_.empty())
  86         return reverse_pex_out_.front().time;
  87     if (NOW < next_send_time_)
  88         return next_send_time_;
  89
  90     // Arno: Fix that doesn't do exponential growth always, only after sends
  91     // without following recvs
  92
  93     // fprintf(stderr,"KeepAliveNextSendTime: gotka %d sentka %d ss %d si %lli\n", lastrecvwaskeepalive_, lastsendwaskeepalive_, sent_since_recv_, send_interval_);
  94
  95     if (lastrecvwaskeepalive_ && lastsendwaskeepalive_)
  96     {
  97         send_interval_ <<= 1;
  98     }
  99     else if (lastrecvwaskeepalive_ || lastsendwaskeepalive_)
 100     {
 101         // Arno, 2011-11-29: we like eachother again, start fresh
 102         // Arno, 2012-01-25: Unless we're talking to a dead peer.
 103         if (sent_since_recv_ < 4) {
 104             send_interval_ = rtt_avg_;
 105         } else
 106             send_interval_ <<= 1;
 107     }
 108     else if (sent_since_recv_ <= 1)
 109     {
 110         send_interval_ = rtt_avg_;
 111     }
 112     else if (sent_since_recv_ > 1)
 113     {
 114         send_interval_ <<= 1;
 115     }
 116     if (send_interval_>MAX_SEND_INTERVAL)
 117         send_interval_ = MAX_SEND_INTERVAL;
 118     return last_send_time_ + send_interval_;
 119 }
 120
 121 tint    Channel::PingPongNextSendTime () { // FIXME INFINITE LOOP
 122     if (dgrams_sent_>=10)
 123         return SwitchSendControl(KEEP_ALIVE_CONTROL);
 124     if (ack_rcvd_recent_)
 125         return SwitchSendControl(SLOW_START_CONTROL);
 126     if (data_in_.time!=TINT_NEVER)
 127         return NOW;
 128     if (last_recv_time_>last_send_time_)
 129         return NOW;
 130     if (!last_send_time_)
 131         return NOW;
 132     return last_send_time_ + ack_timeout(); // timeout
 133 }
 134
 135 tint    Channel::CwndRateNextSendTime () {
 136     if (data_in_.time!=TINT_NEVER)
 137         return NOW; // TODO: delayed ACKs
 138     //if (last_recv_time_<NOW-rtt_avg_*4)
 139     //    return SwitchSendControl(KEEP_ALIVE_CONTROL);
 140     send_interval_ = rtt_avg_/cwnd_;
 141     if (send_interval_>max(rtt_avg_,TINT_SEC)*4)
 142         return SwitchSendControl(KEEP_ALIVE_CONTROL);
 143     if (data_out_.size()<cwnd_) {
 144         dprintf("%s #%u sendctrl next in %llius (cwnd %.2f, data_out %i)\n",
 145                 tintstr(),id_,send_interval_,cwnd_,(int)data_out_.size());
 146         return last_data_out_time_ + send_interval_;
 147     } else {
 148         assert(data_out_.front().time!=TINT_NEVER);
 149         return data_out_.front().time + ack_timeout();
 150     }
 151 }
 152
 153 void    Channel::BackOffOnLosses (float ratio) {
 154     ack_rcvd_recent_ = 0;
 155     ack_not_rcvd_recent_ =  0;
 156     if (last_loss_time_<NOW-rtt_avg_) {
 157         cwnd_ *= ratio;
 158         last_loss_time_ = NOW;
 159         dprintf("%s #%u sendctrl backoff %3.2f\n",tintstr(),id_,cwnd_);
 160     }
 161 }
 162
 163 tint    Channel::SlowStartNextSendTime () {
 164     if (ack_not_rcvd_recent_) {
 165         BackOffOnLosses();
 166         return SwitchSendControl(LEDBAT_CONTROL);//AIMD_CONTROL);
 167     }
 168     if (rtt_avg_/cwnd_<TINT_SEC/10)
 169         return SwitchSendControl(LEDBAT_CONTROL);//AIMD_CONTROL);
 170     cwnd_+=ack_rcvd_recent_;
 171     ack_rcvd_recent_=0;
 172     return CwndRateNextSendTime();
 173 }
 174
 175 tint    Channel::AimdNextSendTime () {
 176     if (ack_not_rcvd_recent_)
 177         BackOffOnLosses();
 178     if (ack_rcvd_recent_) {
 179         if (cwnd_>1)
 180             cwnd_ += ack_rcvd_recent_/cwnd_;
 181         else
 182             cwnd_ *= 2;
 183     }
 184     ack_rcvd_recent_=0;
 185     return CwndRateNextSendTime();
 186 }
 187
 188 tint Channel::LedbatNextSendTime () {
 189     float oldcwnd = cwnd_;
 190
 191     tint owd_cur(TINT_NEVER), owd_min(TINT_NEVER);
 192     for(int i=0; i<4; i++) {
 193         if (owd_min>owd_min_bins_[i])
 194             owd_min = owd_min_bins_[i];
 195         if (owd_cur>owd_current_[i])
 196             owd_cur = owd_current_[i];
 197     }
 198     if (ack_not_rcvd_recent_)
 199         BackOffOnLosses(0.8);
 200     ack_rcvd_recent_ = 0;
 201     tint queueing_delay = owd_cur - owd_min;
 202     tint off_target = LEDBAT_TARGET - queueing_delay;
 203     cwnd_ += LEDBAT_GAIN * off_target / cwnd_;
 204     if (cwnd_<1)
 205         cwnd_ = 1;
 206     if (owd_cur==TINT_NEVER || owd_min==TINT_NEVER)
 207         cwnd_ = 1;
 208
 209     //Arno, 2012-02-02: Somehow LEDBAT gets stuck at cwnd_ == 1 sometimes
 210     // This hack appears to work to get it back on the right track quickly.
 211     if (oldcwnd == 1 && cwnd_ == 1)
 212        cwnd_count1_++;
 213     else
 214        cwnd_count1_ = 0;
 215     if (cwnd_count1_ > 10)
 216     {
 217         dprintf("%s #%u sendctrl ledbat stuck, reset\n",tintstr(),id() );
 218         cwnd_count1_ = 0;
 219         for(int i=0; i<4; i++) {
 220             owd_min_bins_[i] = TINT_NEVER;
 221             owd_current_[i] = TINT_NEVER;
 222         }
 223     }
 224
 225     dprintf("%s #%u sendctrl ledbat %lli-%lli => %3.2f\n",
 226             tintstr(),id_,owd_cur,owd_min,cwnd_);
 227     return CwndRateNextSendTime();
 228 }
 229
 230
 231