/* * This code is based on New_Reno TCP version (V. Jacobson). Written by * O. Ait-Hellal by changing Jacobson-Karels FTP source. * Originally written by S. Keshav. Revised by S. McCanne@LBL */ #include #include #include "../kernel/real.h" #include "tcp.h" static void new_reno_output (); static void new_reno_slowtimo (); static void new_reno_timers (); static void new_reno_ack (); float time_begin[MAX_NODES + 1]; int count_paq[MAX_NODES + 1]; int R_DEBUG; struct frame { PKT_PTR pkt; /* in BSD, packets are queued for retransmissions (prev, next). Here we create a packet every time we need to retransmit it */ short nn; int timeout; long last_sent; /* seq of last pkt. sent */ long last_ack; /* last ack recvd */ int cur_win; /* current window size */ int ssthresh; /* slow start threshold */ int count; /* count of # of increments made * to cur_window so far */ int max_win; /* max window size allowed */ short mdev; /* of rtt estimate from mean */ short rtt; /* actually, the estimate */ short srtt; long t_rtseq; char back_off; /* determines multiplier for timeout */ int line_busy; /* respect of the interpacket delay */ char n_retx[MAX_WINDOW]; /* number of retxs of packet i * in cur win */ int t_timer[MAX_TIMERS]; char t_dupacks; /* number of dupliacte Acks seen */ char t_rexmtthresh; /* number of duplicate Acks for retxsion */ long max_sent; char dropped[MAX_WINDOW_SIZE]; int s_n_retx; /* number of retransmissions */ int fast_retransmit; /* avoid restarting fast retransmits */ int save_cwnd; long snd_high; long high_ack; }; new_reno() { /* Dummy variables for nest that we don't use. */ ident sender, destn; int key, seq_no; int i; timev now; struct frame f; bzero ((char *) &f, sizeof f); f.nn = get_node_id (); abs_advance (node_start_time[f.nn]); printf ("New_Reno ftp source: %d ", f.nn); printf ("sending to sink %d\n", assigned_sink[f.nn]); source_node_type[f.nn] = FTP_SOURCE; for (i = 0; i< MAX_TIMERS; i++) f.t_timer[i] = 0; f.last_sent = -1; f.max_sent = -1; f.snd_high = -1; f.high_ack = -1; f.last_ack = -1; f.t_rexmtthresh = 3; f.t_dupacks = 0; f.max_win = ftp_window; f.ssthresh = 16; f.cur_win = 1; f.count = 0; f.mdev = 4; f.rtt = 1; f.t_rtseq = -1; f.srtt = 1; f.back_off = 0; f.timeout = 2; f.s_n_retx = 0; f.line_busy = 0; f.t_rtseq = -1; f.back_off = 0; f.timeout = 2; f.fast_retransmit = 0; /* do fast retransmit whenever three dups are received */ f.t_timer[TCPT_REXMT] = f.timeout; /* send the first packet */ (void) new_reno_output (&f); /* schedule the next software timer 500 ms */ { PKT_PTR tick_pkt; float delay; timev now; now = runtime (); hold(); tick_pkt = (PKT_PTR) malloc ((unsigned) sizeof (PKT)); release(1); tick_pkt->source = tick_pkt->dest = f.nn; tick_pkt->size = ftp_size; tick_pkt->type = TICK; delay = 0.5; set_timer (delay, tick_pkt); } while (1) { sender = recvm (&destn, &key, &f.pkt); switch (f.pkt->type) { case ACK: new_reno_ack (&f); break; case INT: hold (); f.line_busy = 0; free (f.pkt); release (1); new_reno_output (&f); break; case TIMEOUT: hold (); free (f.pkt); release (1); break; case TICK: hold (); free (f.pkt); release (1); new_reno_slowtimo (&f); break; default: hold (); free (f.pkt); release (1); pr_error ("Vegas_source recvd. a vague pkt "); break; } } } /*---------------------------------------------------------------------------*/ static void new_reno_ack (fp) struct frame *fp; { PKT_PTR pkt; int i; int last, cum_ack; pkt = fp->pkt; last = fp->last_ack; cum_ack = pkt->seq_no; if (cum_ack > fp->high_ack) { fp->high_ack = cum_ack; make_plot("high_ack", fp->high_ack); } hold (); free (pkt); release (1); make_plot ("ack", cum_ack); if (cum_ack == fp->last_ack) /* duplicate Ack seen */ { if (++fp->t_dupacks == fp->t_rexmtthresh) { if (fp->high_ack > fp->snd_high) { int oldsent = fp->last_sent; int win = min (fp->cur_win, fp->max_win); fp->fast_retransmit = 1; /*exponential decrease*/ win >>= 1; if (win < 2) win = 2; fp->count = fp->count/2; fp->ssthresh = win; make_plot ("ssthresh", fp->ssthresh); fp->t_timer[TCPT_REXMT] = 0; fp->rtt = 0; fp->snd_high = fp->last_sent; fp->last_sent = fp->last_ack; make_plot ("snd_high", fp->snd_high); fp->cur_win = 1; fp->save_cwnd = fp->ssthresh + 1; (void) new_reno_output(fp); } } /* if (fp->t_dupacks > fp->t_rexmtthresh ) { if ((fp->t_dupacks %2) == 1) { int oldsent = fp->last_sent; int win = fp->cur_win; fp->cur_win = 1; fp->last_sent = fp->max_sent; (void) new_reno_output(fp); fp->cur_win = win; fp->last_sent = oldsent; } }*/ goto drop; } if (cum_ack < fp->last_ack) { fp->t_dupacks = 0; goto drop; } /* ack not seen before */ if((cum_ack >= fp->snd_high) && (fp->fast_retransmit == 1)) { fp->fast_retransmit = 0; fp->cur_win = fp->save_cwnd; /*fp->last_sent = fp->max_sent;*/ } fp->t_dupacks = 0; /* * If transmit timer is running and timed sequence * number was acked, update smoothed round trip time. * Since we now have an rtt measurement, cancel the * timer backoff (cfp->, Phil Karn's retransmit alg.). * Recompute the initial retransmit timer. */ if (fp->rtt && cum_ack >= fp->t_rtseq) { if (fp->srtt != 0) { register short delta; /* * to the smoothing algorithm in rfc793 * with an alpha of .875 * (srtt = rtt/8 + srtt*7/8 in integers ???). * Adjust t_rtt to origin 0. */ fp->rtt--; delta = fp->rtt - (fp->srtt >> 3); if ((fp->srtt += delta) <= 0) fp->srtt = 1; /* * We accumulate a smoothed rtt variance * (actually, a smoothed mean difference), * then set the retransmit timer to smoothed * rtt + 2 times the smoothed variance. * rttvar is stored integer * The following is equivalent * to rfc793 smoothing with an alpha of .75 * (rttvar = rttvar*3/4 + |delta| / 4). * This replaces rfc793's wired-in beta. */ if (delta < 0) delta = -delta; delta -= (fp->mdev >> 2); if ((fp->mdev += delta) <= 0) fp->mdev = 1; } else { /* * No rtt measurement yet - use the * unsmoothed rtt. Set the variance * to half the rtt (so our first * retransmit happens at 2*rtt) */ fp->srtt = fp->rtt << 3; fp->mdev = fp->rtt << 1; } fp->rtt = 0; fp->back_off = 0; TCPT_RANGESET(fp->timeout, ((fp->srtt >> 2) + fp->mdev) >> 1, TCPTV_MIN, TCPTV_REXMTMAX); } if (cum_ack == fp->max_sent) fp->t_timer[TCPT_REXMT] = 0; else fp->t_timer[TCPT_REXMT] = fp->timeout; make_plot("timeout", fp->timeout); for (i = 0; i <= cum_ack - last; ++i) { /* reset the bit anyhow */ fp->n_retx[(last + i) % MWS] = 0; } /* * when new data is acked, New_Reno increases * its cwnd on every Ack if doing slow-start * or on every RTT i doing congestion avoidance. */ { int incr = ftp_size; if (fp->fast_retransmit) { fp->cur_win = min (++fp->cur_win, fp->max_win); fp->cur_win = min(fp->save_cwnd, fp->cur_win); } else { if (fp->cur_win > fp->ssthresh) incr = max(ftp_size / fp->cur_win, 1); fp->count += incr; if (fp->count >= ftp_size) { fp->cur_win++; fp->count -= ftp_size; if (fp->cur_win == fp->max_win) fp->count = 0; } fp->cur_win = min (fp->cur_win, fp->max_win); } fp->last_ack = cum_ack; if (fp->last_sent < fp->last_ack) fp->last_sent = fp->last_ack; (void) new_reno_output (fp); } drop: ; } static void new_reno_output (fp) struct frame *fp; { PKT_PTR pkt; int win, nqueued; win = min (fp->cur_win, fp->max_win); /* Send as mutch data as we can, with respect to the inter-packet delay */ make_plot ("last_sent", fp->last_sent); make_plot ("last_ack", fp->last_ack); make_plot ("max_sent", fp->max_sent); if (fp->line_busy) return; if (fp->last_sent + 1 <= fp->last_ack + win) { int startseq = (++fp->last_sent); /* ok to send now */ hold (); pkt = (PKT_PTR) calloc (1,(unsigned) sizeof (PKT)); release (1); fp->pkt = pkt; pkt->size = ftp_size; pkt->gen_time = runtime (); pkt->type = FTP; pkt->gs = 0; pkt->seq_no = max (fp->last_sent, fp->last_ack+1); pkt->dest = assigned_sink[fp->nn]; if (pkt->dest < ABSOLUTE_MAX_NODES) pkt->dest += ABSOLUTE_MAX_NODES * realnum; pkt->source = realnum * ABSOLUTE_MAX_NODES + fp->nn; fp->dropped[pkt->seq_no % MAX_WINDOW_SIZE] = 0; fp->line_busy = 1; if (fp->last_sent > fp->max_sent) { fp->max_sent = fp->last_sent; if (fp->rtt == 0) { fp->rtt = 1; fp->t_rtseq = startseq; make_plot("rt_seq", fp->t_rtseq); } }else { ++fp->n_retx[fp->last_sent % MWS]; ++fp->s_n_retx; } if (fp->t_timer[TCPT_REXMT] == 0 && fp->last_sent != fp->last_ack) { fp->t_timer[TCPT_REXMT] = fp->timeout; fp->back_off = 0; } new_reno_send (fp); } } /* * This routine is called every 500 ms, updates the timers * (retransmission timer), and the round trip times. * The fast timeout for processing delayed Acks is not used */ static void new_reno_slowtimo (fp) struct frame *fp; { if (fp->t_timer[TCPT_REXMT] && --fp->t_timer[TCPT_REXMT] == 0) { /* * when a timer expire, this routine calls tcp_usrreq * which determines which timer has been timed out, * and calls the appropriate routine. In our case * the only even which may happen is the retransmission * timer which has expired. So tcp_timers is directly called */ (void) new_reno_timers (fp); } if (fp->rtt) fp->rtt++; /* schedule the next software timer 500 ms */ { PKT_PTR tick_pkt; float delay; timev now; now = runtime (); hold(); tick_pkt = (PKT_PTR) malloc ((unsigned) sizeof (PKT)); release(1); tick_pkt->source = tick_pkt->dest = fp->nn; tick_pkt->size = ftp_size; tick_pkt->type = TICK; delay = 0.5; set_timer (delay, tick_pkt); } } /* TCP timeout processing */ static void new_reno_timers (fp) struct frame *fp; { register int rexmt; if (++fp->back_off > TCP_MAXRXTSHIFT) { printf ("connection timed out \n"); printf("Acknowledged %ld packets\n", fp->last_ack); } rexmt = ((fp->srtt >> 2) + fp->mdev) >> 1; rexmt *= tcp_backoff[fp->back_off]; TCPT_RANGESET(fp->timeout, rexmt, TCPTV_MIN, TCPTV_REXMTMAX); fp->t_timer[TCPT_REXMT] = fp->timeout; make_plot("TIMEOUT", fp->timeout); /* * If losing, let the lower level know and try for * a better route. Also, if we backed off this far, * our srtt estimate is probably bogus. Clobber it * so we'll take the next rtt measurement as our srtt; * move the current srtt into rttvar to keep the current * retransmit times until then. */ if (fp->back_off > MAX_RT_SHIFT / 4) { fp->mdev += fp->srtt; fp->srtt = 0; } fp->last_sent = fp->last_ack; /* * If timing a segment in this window, stop the timer. */ fp->rtt = 0; /* * Close the congestion window down to one segment * (we'll open it by one segment for each ack we get). * Since we probably have a window's worth of unacked * data accumulated, this "slow start" keeps us from * dumping all that data as back-to-back packets (which * might overwhelm an intermediate gateway). * * There are two phases to the opening: Initially we * open by one mss on each ack. This makes the window * size increase exponentially with time. If the * window is larger than the path can handle, this * exponential growth results in dropped packet(s) * almost immediately. To get more time between * drops but still "push" the network to take advantage * of improving conditions, we switch from exponential * to linear window opening at some threshhold size. * For a threshhold, we use half the current window * size, truncated to a multiple of the mss. * * (the minimum cwnd that will give us exponential * growth is 2 mss. We don't allow the threshhold * to go below this.) */ { int win = fp->cur_win / 2; if (win < 2) win = 2; fp->cur_win = 1; /*fp->snd_high = fp->max_sent; make_plot ("snd_high", fp->snd_high); fp->fast_retransmit = 1; */ fp->fast_retransmit = 0; fp->ssthresh = win; make_plot ("ssthresh", fp->ssthresh); fp->t_dupacks = 3; fp->count = 0; } (void) new_reno_output(fp); fp->snd_high = fp->last_sent; } static new_reno_send (fp) struct frame *fp; { PKT_PTR pkt; ident dest; timev now; ident node_number; int win; node_number = get_node_id (); now = runtime (); pkt = fp->pkt; make_plot("seq", pkt->seq_no); make_plot ("win", fp->cur_win); dest = pkt->dest; if ((dest / ABSOLUTE_MAX_NODES) != realnum) /* not local */ dest = cc_router; else dest = dest % ABSOLUTE_MAX_NODES; pkt->timeout = (long) (200 * MILLION); if (route[node_number][dest] == 0) pr_error ("Routing error in Vegas_source"); if (sendm (route[node_number][dest], 0, (char *) pkt) isnt 1) pr_error ("Vegas_safe_send: message undeliverable ", pkt); }