/*
* This code is based on Tahoe 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 <math.h>
#include <stdio.h>
#include "real.h"
#include "tcp.h"

static void     tahoe_output ();
static void     tahoe_slowtimo ();
static void     tahoe_timers ();
static void     tahoe_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 */

};

tahoe()
{
/* 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 ("Tahoe 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) tahoe_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:
   tahoe_ack (&f);
   break;

case INT:
   hold ();
   f.line_busy = 0;
   free (f.pkt);
   release (1);
   tahoe_output (&f);
   break;

case TIMEOUT:
   hold ();
   free (f.pkt);
   release (1);
   break;
case TICK:
   hold ();
   free (f.pkt);
   release (1);
   tahoe_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 tahoe_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      win      = min (fp->cur_win, fp->max_win);

   /*exponential decrease*/

   win >>= 1;
   if (win < 2)
     win = 2;

   fp->count               = 0;
   fp->ssthresh            = win;
   fp->t_timer[TCPT_REXMT] = 0;
   fp->rtt                 = 0;
   fp->last_sent           = fp->last_ack;
   fp->cur_win             = 1;

   (void) tahoe_output(fp);

}
      goto drop;
    }

if (cum_ack < fp->last_ack)
    {
      fp->t_dupacks = 0;
      goto drop;
    }

/* ack not seen before */

/*
   * 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, Tahoe 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) tahoe_output (fp);
}

drop: ;

}

static void tahoe_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 */

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;
}

      tahoe_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 tahoe_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) tahoe_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 tahoe_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) tahoe_output(fp);
}

tahoe_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);

}