tcp-sack-rh.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1990, 1997 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the University of California, Lawrence Berkeley Laboratory,
 * Berkeley, CA.  The name of the University may not be used to
 * endorse or promote products derived from this software without
 * specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

/*
 * This is TCP SACK with Rate-Halving, contributed code from Matt
 * Mathis, Jeff Semke, Jamshid Mahdavi, and Kevin Lahey, and
 * described at "http://www.psc.edu/networking/rate-halving/". 
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcp/tcp-sack-rh.cc,v 1.5 2002/10/09 03:47:02 difa Exp $ (PSC-SACKRH)";
#endif

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>

#include "ip.h"
#include "tcp.h"
#include "flags.h"
#include "scoreboard-rh.h"
#include "random.h"

#define TRUE    1
#define FALSE   0

#define RH_INCR 0
#define RH_EXACT 11
#define RH_EST 12
#define RH_EST_REPAIR 13

#define RHEH_NONE 0
#define RHEH_COUNTING 1
#define RHEH_NEW_HOLE 2
#define RHEH_RETRANS_OCCURRED 3

//#define DEBUGRH 

class SackRHTcpAgent : public TcpAgent {
 public:
        SackRHTcpAgent();
    virtual int window();
    virtual void recv(Packet *pkt, Handler*);
    virtual void timeout(int tno);
    void plot();
    virtual void send_much(int force, int reason, int maxburst);
    virtual void boundparms();
    virtual void estadjust();
    virtual void rhclear();
    virtual void computefack();
    virtual void SackRHTcpAgent::newack(Packet* pkt);
 protected:
    int fack_;            /* the FACK state variable  */
    int retran_data_;         /* the number of retransmitted packets in the pipe  */
    int num_dupacks_;         /* sigh, I think we still want this for the NewReno case */
    int rh_state_;            /* The rate halving state we are in  */
    double prior_cwnd_;       /* The value of cwnd at the start of RH  */
    int prior_max_seq_;       /* The old value of max_seq  */
    int rh_id_;               /* A unique ID for the current adjustment interval  */
    int rh_max_;              /* The max ID which has been used so far  */
    int rh_est_hole_state_;   /* Status of NewReno style holes during estimation */
    int num_retrans_;         /* Number of retransmissions during the estimation state */
    int rh_retran_flag_;      /* Flag to indicate a retransmission has occured */
    int rh_ecn_flag_;         /* Flag to indicate an ECN was seen during this recovery */
    ScoreBoardRH scb_;
};

static class SackRHTcpClass : public TclClass {
public:
    SackRHTcpClass() : TclClass("Agent/TCP/SackRH") {}
    TclObject* create(int, const char*const*) {
        return (new SackRHTcpAgent());
    }
} class_sack_rh;

int SackRHTcpAgent::window()
{
    return(cwnd_ < wnd_ ? (int) cwnd_ : (int) wnd_);
}

SackRHTcpAgent::SackRHTcpAgent() : fack_(-1), 
    retran_data_(0), num_dupacks_(0), rh_state_(RH_INCR), rh_id_(0), rh_max_(0),
    rh_est_hole_state_(0), rh_retran_flag_(0), rh_ecn_flag_(0), scb_(&numdupacks_)
{
}

void SackRHTcpAgent::recv(Packet *pkt, Handler*)
{
    int old_fack, old_retran_data, old_ack, old_numdupacks;
    hdr_tcp *tcph = hdr_tcp::access(pkt);

    int ecnecho = (hdr_flags::access(pkt)->ecnecho() && last_ack_ != -1);
    int sackpresent = (tcph->sa_length() > 0);

    ++nackpack_;

#ifdef DEBUGRH
    printf ("ENTER: RH=%02d snd.nxt=%3d fack=%3d ack=%3d retran_data=%03d \n",
        rh_state_, (int)t_seqno_, fack_, last_ack_, retran_data_);
    printf ("       prior_max_seq=%3d prior_cwnd=%f rheh=%2d num_dupacks=%2d\n",
        prior_max_seq_, prior_cwnd_, rh_est_hole_state_, num_dupacks_);
    printf ("       cwnd:%f=%d curseq=%d\n",
        (float)cwnd_, int(cwnd_), (int)curseq_);
#endif
    old_ack = last_ack_;
    newack(pkt);

    if (ecnecho) rh_ecn_flag_=1;   /*  Remember that we saw an ECN  */

    /*  Process any SACK blocks:  */
    old_fack = fack_;
    old_retran_data = retran_data_;
    retran_data_ -= scb_.UpdateScoreBoard (last_ack_, tcph, rh_id_);

    old_numdupacks = num_dupacks_;
        if (!sackpresent && (old_ack == last_ack_)) {
        num_dupacks_++;
        if ((rh_est_hole_state_ == RHEH_COUNTING) && 
            (num_dupacks_ == numdupacks_)) {
            rh_est_hole_state_ = RHEH_NEW_HOLE;
        }
    }

    computefack();


    /*  7.8  Reordering Exit transitions */
    if (!rh_retran_flag_ && !rh_ecn_flag_) {
        if (((rh_state_ == RH_EXACT) && !sackpresent && !ecnecho) ||
            ((rh_state_ == RH_EST) && (last_ack_ > old_ack))) {
            rh_state_ = RH_INCR;
            cwnd_ = prior_cwnd_;
            rhclear();
            computefack();  /* In case we were estimating it before */
        }
    }

    /*  7.10 Completion of RH_EXACT  */
    if (rh_state_ == RH_EXACT) {
        if ((fack_ >= prior_max_seq_) || scb_.RetranSacked(rh_id_)) {
            boundparms();
            rh_state_ = RH_INCR;
            rhclear();
        }
    }

    /*  7.11 Completion of RH_EST*  */
    if ((rh_state_ == RH_EST) || (rh_state_ == RH_EST_REPAIR)) {
        if (last_ack_ >= prior_max_seq_) {
            retran_data_ = 0;     /*  Just like a partial ACK, this
                          means a retransmission has left
                          the network.  */
            estadjust();
            boundparms();
            rh_state_ = RH_INCR;
            rhclear();
            computefack();   /*  This is needed to restore 
                         fack now that we are done estimating */
        }
    }

    /*  7.12 NewReno case  */
    if ((rh_state_ == RH_EST) && (cwnd_ <= prior_cwnd_/2)) {
        rh_state_ = RH_EST_REPAIR;
    }

    /*  7.9  Processing partial Acks in RH_EST or RH_EST_REPAIR */
    if (((rh_state_ == RH_EST) || (rh_state_ == RH_EST_REPAIR))
        && (last_ack_ > old_ack)) {
        retran_data_ = 0;
        num_dupacks_ -= (last_ack_ - old_ack - 1);
        if (num_dupacks_ >= numdupacks_) {
            rh_est_hole_state_ = RHEH_NEW_HOLE;
        }
        else {
            /*  We don't have 3 dupacks on this hole, so 
                go back to counting...  */
            rh_est_hole_state_ = RHEH_COUNTING;
        }
        computefack();  /* Recompute the estimate */
    }
        
    /*  Now check the entry conditions:  */

    /*  7.4  Entering RH_EXACT  */
    if ((rh_state_ == RH_INCR) && (ecnecho || scb_.GetNewHoles() != 0)) {
        rh_state_ = RH_EXACT;
        prior_cwnd_ = cwnd_;
        prior_max_seq_ =  t_seqno_;
        cong_action_ = TRUE;
        rh_id_ = ++rh_max_;
    }

    /*  7.5  Entering RH_EST  */
    if ((rh_state_ == RH_INCR)  && (num_dupacks_ > 0)) {
        rh_state_ = RH_EST;
        rh_est_hole_state_ = RHEH_COUNTING;
        prior_cwnd_ = cwnd_;
        prior_max_seq_ =  t_seqno_;
        cong_action_ = TRUE;
        rh_id_ = ++rh_max_;
    }
        
    if ((rh_state_ == RH_EXACT)  && (num_dupacks_ > 0)) {
        rh_state_ = RH_EST;
        rh_est_hole_state_ = RHEH_COUNTING;
        /*  cong_action_ = TRUE;  */   /*  Don't need it, 
                                           since we already
                           sent it  */
        rh_id_ = ++rh_max_;
    }

    if ((rh_state_ == RH_EST_REPAIR)  && (ecnecho)) {
        rh_state_ = RH_EST;
        prior_cwnd_ = cwnd_;
        prior_max_seq_ =  t_seqno_;
        cong_action_ = TRUE;
        rh_id_ = ++rh_max_;
    }

    /*  Updating the window:  */
    switch (rh_state_) {
    case RH_INCR:
        /*  Case 7.2:  */
        if ((t_seqno_ - old_fack + old_retran_data + 1) >= (int)cwnd_) {
            opencwnd();
        }
        break;
    case RH_EXACT:
        /*  Case 7.6  */
        cwnd_ -= ((float)((fack_ - old_fack) + (scb_.GetNewHoles()))) / 2.0;
        break;
    case RH_EST:
        /*  Case 7.7  */
        cwnd_ -= 0.5;
        break;
    case RH_EST_REPAIR:
        /*  Do not modify cwnd in this state  */
        break;
    }

#ifdef DEBUGRH
    printf ("EXIT:  RH=%02d snd.nxt=%3d fack=%3d ack=%3d retran_data=%03d \n       cwnd:%f=%d curseq=%d\n",
        rh_state_, (int)t_seqno_, fack_, last_ack_, retran_data_, (float)cwnd_, int(cwnd_),
            (int)curseq_);
#endif
    send_much(FALSE, 0, maxburst_);

    Packet::free(pkt);
#ifdef notyet
    if (trace_)
        plot();
#endif
}

void SackRHTcpAgent::rhclear()
{
    rh_id_ = prior_max_seq_ = num_dupacks_ = rh_est_hole_state_ = 
        rh_ecn_flag_ = num_retrans_ = rh_retran_flag_ = 0;
    prior_cwnd_ = 0;
}

/*  Compute FACK:  */
void SackRHTcpAgent::computefack()
{
    if ((rh_state_ == RH_INCR) || (rh_state_ == RH_EXACT)) {
        fack_ = scb_.GetFack (last_ack_);
    }
    else {
        fack_ = last_ack_ + num_dupacks_ + 1;
    }
}

/*  7.14: Bounding Parameters  */
void SackRHTcpAgent::boundparms()
{
    if (cwnd_ > prior_cwnd_/2.0) 
        cwnd_ = prior_cwnd_/2.0;
    ssthresh_ = cwnd_;
    if (ssthresh_ < prior_cwnd_/4.0)
        ssthresh_ = (int) (prior_cwnd_/4.0);
}

/*  7.13: Corrections to Estimation  */
void SackRHTcpAgent::estadjust()
{
    cwnd_ = (prior_cwnd_ - num_retrans_)/2.0;
}

/*  7.15: Retransmission Timeout  */
void SackRHTcpAgent::timeout(int tno)
{
    /* retransmit timer */
    if (tno == TCP_TIMER_RTX) {
        if (highest_ack_ == maxseq_ && !slow_start_restart_)
            /*
             * TCP option:
             * If no outstanding data, then don't do anything.
             */
            return;
        if (highest_ack_ == -1 && wnd_init_option_ == 2)
            /* 
             * First packet dropped, so don't use larger
             * initial windows. 
             */
            wnd_init_option_ = 1;

#ifdef DEBUGRH
        printf ("timeout. last_ack: %d seqno: %d\n", 
            (int)last_ack_, (int)t_seqno_);
#endif

        if (rh_state_ != RH_INCR) {
            /*  4.6  We took a timeout in the middle of
                rate-halving.  Pretend like RH
                never started:  */
            cwnd_ = prior_cwnd_;
            rhclear();
            rh_state_ = RH_INCR;
            
        }
        ++nrexmit_;
        slowdown(CLOSE_SSTHRESH_HALF|CLOSE_CWND_RESTART);

        retran_data_ = 0;
        scb_.TimeoutScoreBoard(t_seqno_);
        computefack();

        /*  Pull back the sequence number -- pretend you never
            sent packets beyond FACK  */
        if (t_seqno_ > fack_+1) {
            t_seqno_ = fack_+1;
        }
        reset_rtx_timer(1,1);

        last_cwnd_action_ = CWND_ACTION_TIMEOUT;
        send_much(0, TCP_REASON_TIMEOUT, maxburst_);
    } 
    else {
        timeout_nonrtx(tno);
    }
}


void SackRHTcpAgent::send_much(int force, int reason, int maxburst)
{
    register int found, npacket = 0;
    int xmit_seqno;

    found = 1;
    if (!force && delsnd_timer_.status() == TIMER_PENDING)
        return;
    /*
     * as long as the pipe is open and there is app data to send...
     */

    /*  7.3: data transmission  */
    while (int(cwnd_) >= (t_seqno_ - fack_ + retran_data_)
            && found) {
        if (overhead_ == 0 || force) {
            found = 0;
            xmit_seqno = scb_.GetNextRetran ();

            if (xmit_seqno == -1) { 
                /*  Check to see if we have identified a new hole... */
                if (((rh_state_ == RH_EST) || (rh_state_ == RH_EST_REPAIR)) &&
                    (rh_est_hole_state_ == RHEH_NEW_HOLE)) {
                    xmit_seqno = last_ack_ + 1;
                    rh_est_hole_state_ = RHEH_RETRANS_OCCURRED;
                    num_retrans_++;
                    retran_data_++;
                    rh_retran_flag_ = 1;
                    found = 1;
                }
                else if ((t_seqno_ < curseq_) && 
                     (t_seqno_<=last_ack_+int(wnd_))) {
                    found = 1;
                    xmit_seqno = t_seqno_++;
                }
            } else if (xmit_seqno<=last_ack_+int(wnd_)) {
                found = 1;
                scb_.MarkRetran (xmit_seqno, t_seqno_, rh_id_);
                retran_data_++;
                rh_retran_flag_ = 1;
            }
            if (found) {
#ifdef DEBUGRH
                printf ("      Sending: %3d\n", xmit_seqno);
#endif              
                output(xmit_seqno, reason);
                if (t_seqno_ <= xmit_seqno)
                    t_seqno_ = xmit_seqno + 1;
                npacket++;
            }
        } else if (!(delsnd_timer_.status() == TIMER_PENDING)) {
            /*
             * Set a delayed send timeout.
             * This is only for the simulator,to add some
             *   randomization if speficied.
             */
            delsnd_timer_.resched(Random::uniform(overhead_));
            return;
        }
        if (maxburst && npacket == maxburst)
            break;
    } /* while */
}

void SackRHTcpAgent::plot()
{
#ifdef notyet
    double t = Scheduler::instance().clock();
    sprintf(trace_->buffer(), "t %g %d rtt %g\n", 
        t, class_, t_rtt_ * tcp_tick_);
    trace_->dump();
    sprintf(trace_->buffer(), "t %g %d dev %g\n", 
        t, class_, t_rttvar_ * tcp_tick_);
    trace_->dump();
    sprintf(trace_->buffer(), "t %g %d win %f\n", t, class_, cwnd_);
    trace_->dump();
    sprintf(trace_->buffer(), "t %g %d bck %d\n", t, class_, t_backoff_);
    trace_->dump();
#endif
}

/*
 * Process a packet that acks previously unacknowleged data.
 *
 * The only thing we change here is the policy for clearing
 * RTO backoff...
 *
 */

void SackRHTcpAgent::newack(Packet* pkt)
{
    double now = Scheduler::instance().clock();
    hdr_tcp *tcph = hdr_tcp::access(pkt);
    /* 
     * Wouldn't it be better to set the timer *after*
     * updating the RTT, instead of *before*? 
     */
    newtimer(pkt);
    last_ack_ = tcph->seqno();
    highest_ack_ = last_ack_;

    if (t_seqno_ < last_ack_ + 1)
        t_seqno_ = last_ack_ + 1;
    /* 
     * Update RTT only if it's OK to do so from info in the flags header.
     * This is needed for protocols in which intermediate agents
     * in the network intersperse acks (e.g., ack-reconstructors) for
     * various reasons (without violating e2e semantics).
     */ 
    hdr_flags *fh = hdr_flags::access(pkt);
    if (!fh->no_ts_) {
        if (ts_option_)
            rtt_update(now - tcph->ts_echo());

        if (rtt_active_ && tcph->seqno() >= rtt_seq_) {
            if (!hdr_flags::access(pkt)->ecnecho()) {
                /* 
                 * Don't end backoff if there is still an ECN-Echo
                 * on the packet.
                 */
                t_backoff_ = 1;
            }
            rtt_active_ = 0;
            if (!ts_option_)
                rtt_update(now - rtt_ts_);
        }
    }
    /* update average window */
    awnd_ *= 1.0 - wnd_th_;
    awnd_ += wnd_th_ * cwnd_;
}

---