#include <math.h>
#include <stdio.h>
#include "real.h"
#include "tcp.h"
static void reno_output ();
static void reno_slowtimo ();
static void reno_timers ();
static void reno_ack ();
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
*/
};
reno()
{
/* Dummy variables for nest that we don't use. */
ident
sender, destn;
int
key, seq_no;
int
i;
timev now;
struct frame f;
stop_time ();
bzero ((char *) &f, sizeof f);
f.nn = get_node_id ();
abs_advance (node_start_time[f.nn]);
printf ("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.last_ack
= -1;
f.t_rexmtthresh = 3;
f.t_dupacks
= 0;
f.max_win
= ftp_window;
f.ssthresh
= f.max_win / 2;
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.t_timer[TCPT_REXMT] = f.timeout;
/* send the first packet */
(void) reno_output (&f);
/* schedule the next software timer 500 ms */
{
PKT_PTR
tick_pkt;
int
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 = 1000000.0*0.5;
delay += (now.tv_sec - Graph->header->timenow.tv_sec)
* MILLION + now.tv_usec - Graph->header->timenow.tv_usec;
own_reliable (f.nn, f.nn, f.nn, 0, tick_pkt, delay,
Graph->header->timenow);
}
while (1)
{
sender = recvm (&destn, &key,
&f.pkt);
switch (f.pkt->type)
{
case ACK:
reno_ack (&f);
break;
case INT:
hold ();
f.line_busy = 0;
free (f.pkt);
release (1);
reno_output (&f);
break;
case TIMEOUT:
hold ();
free (f.pkt);
release (1);
break;
case TICK:
hold ();
free (f.pkt);
release (1);
reno_slowtimo (&f);
break;
case DROPPED:
/* This packet has been dropped, so when it times out,
it
* should be retransmitted. This is indicated by
setting the
* 'dropped' bit. */
f.dropped[f.pkt->seq_no % MAX_WINDOW_SIZE] = 1;
hold ();
free (f.pkt);
release (1);
break;
default:
hold ();
free (f.pkt);
release (1);
pr_error ("Vegas_source recvd. a vague pkt ");
break;
}
}
}
/*---------------------------------------------------------------------------*/
static void 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;
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
)
{
int oldsent = fp->last_sent;
int win = min (fp->cur_win,
fp->max_win);
/*exponential decrease*/
win >>= 1;
if (win < 2)
win = 2;
fp->count = fp->count/2;
fp->ssthresh = win;
fp->t_timer[TCPT_REXMT] = 0;
fp->rtt
= 0;
fp->last_sent
= fp->last_ack;
fp->cur_win
= 1;
(void) reno_output(fp);
fp->cur_win = fp->ssthresh + fp->t_dupacks;
if ( fp->last_sent < oldsent)
fp->last_sent = oldsent ;
}else
if (fp->t_dupacks > fp->t_rexmtthresh)
{
if (fp->cur_win < fp->max_win)
fp->cur_win++;
(void) reno_output(fp);
}
goto drop;
}
if (cum_ack < fp->last_ack)
{
fp->t_dupacks = 0;
goto drop;
}
/* ack not seen before */
if (fp->t_dupacks >= fp->t_rexmtthresh &&
fp->cur_win > fp->ssthresh)
fp->cur_win = fp->ssthresh;
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, 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->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) reno_output (fp);
}
drop: ;
}
static void 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 */
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->alpha = alpha_f;
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 /* for simulations this is always true */)
{
fp->t_timer[TCPT_REXMT] = fp->timeout;
fp->back_off
= 0;
}
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 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) reno_timers (fp);
}
if (fp->rtt)
fp->rtt++;
/* schedule the next software timer 500 ms */
{
PKT_PTR
tick_pkt;
int
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
= 1000000.0*0.5;
delay += (now.tv_sec - Graph->header->timenow.tv_sec)
* MILLION + now.tv_usec - Graph->header->timenow.tv_usec;
own_reliable (fp->nn, fp->nn, fp->nn, 0, tick_pkt,
delay, Graph->header->timenow);
}
}
/* TCP timeout processing */
static void 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->ssthresh = win;
fp->t_dupacks = 0;
fp->count = 0;
}
(void) reno_output(fp);
}
static 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);
}