tcp-sack1.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.
 */

/* 8/02 Tom Kelly - Made scoreboard a general interface to allow
 *                  easy swapping of scoreboard algorithms.  
 */

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

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

#define TRUE    1
#define FALSE   0
#define RECOVER_DUPACK  1
#define RECOVER_TIMEOUT 2
#define RECOVER_QUENCH  3

class Sack1TcpAgent : public TcpAgent {
 public:
    Sack1TcpAgent();
    virtual ~Sack1TcpAgent();
    virtual void recv(Packet *pkt, Handler*);
    int is_sacked(hdr_tcp *tcph, int seqlo, int seqhi);
    void reset();
    virtual void timeout(int tno);
    virtual void dupack_action();
    virtual void partial_ack_action();
    void plot();
    virtual void send_much(int force, int reason, int maxburst);
 protected:
    u_char timeout_;    /* boolean: sent pkt from timeout? */
    u_char fastrecov_;  /* boolean: doing fast recovery? */
    int pipe_;      /* estimate of pipe size (fast recovery) */ 
    int partial_ack_;   /* Set to "true" to ensure sending */
                /*  a packet on a partial ACK.     */
    int next_pkt_;      /* Next packet to transmit during Fast */
                /*  Retransmit as a result of a partial ack. */
    int firstpartial_;  /* First of a series of partial acks. */
    ScoreBoard* scb_;
    static const int SBSIZE=64; /* Initial scoreboard size */
};

static class Sack1TcpClass : public TclClass {
public:
    Sack1TcpClass() : TclClass("Agent/TCP/Sack1") {}
    TclObject* create(int, const char*const*) {     
        return (new Sack1TcpAgent());
    }
} class_sack;

Sack1TcpAgent::Sack1TcpAgent() : fastrecov_(FALSE), pipe_(-1), next_pkt_(0), firstpartial_(0)
{
    bind_bool("partial_ack_", &partial_ack_);
    /* Use the Reassembly Queue based scoreboard as
     * ScoreBoard is O(cwnd) which is bad for HSTCP
     * scb_ = new ScoreBoard(new ScoreBoardNode[SBSIZE],SBSIZE);
     */
    scb_ = new ScoreBoardRQ();
}

Sack1TcpAgent::~Sack1TcpAgent(){
    delete scb_;
}

void Sack1TcpAgent::reset ()
{
    scb_->ClearScoreBoard();
    TcpAgent::reset ();
}


void Sack1TcpAgent::recv(Packet *pkt, Handler*)
{
    hdr_tcp *tcph = hdr_tcp::access(pkt);
    int valid_ack = 0;

        if (qs_approved_ == 1 && tcph->seqno() > last_ack_)
        endQuickStart();
        if (qs_requested_ == 1)
                processQuickStart(pkt);
#ifdef notdef
    if (pkt->type_ != PT_ACK) {
        Tcl::instance().evalf("%s error \"received non-ack\"",
                      name());
        Packet::free(pkt);
        return;
    }
#endif
        /* W.N.: check if this is from a previous incarnation */
        if (tcph->ts() < lastreset_) {
                // Remove packet and do nothing
                Packet::free(pkt);
                return;
        }
    ++nackpack_;
    int ecnecho = hdr_flags::access(pkt)->ecnecho();
    if (ecnecho && ecn_)
        ecn(tcph->seqno());
        if (tcph->seqno() >= last_ack_)
        // Check if ACK is valid.  Suggestion by Mark Allman.
        valid_ack = 1;
    /*
     * If DSACK is being used, check for DSACK blocks here.
     * Possibilities:  Check for unnecessary Fast Retransmits.
     */
    if (!fastrecov_) {
        /* normal... not fast recovery */
        if ((int)tcph->seqno() > last_ack_) {
            /*
             * regular ACK not in fast recovery... normal
             */
            firstpartial_ = 0;
            recv_newack_helper(pkt);
            timeout_ = FALSE;
            scb_->ClearScoreBoard();
            if (last_ack_ == 0 && delay_growth_) {
                cwnd_ = initial_window();
            }
        } else if ((int)tcph->seqno() < last_ack_) {
            /*NOTHING*/
        } else if (timeout_ == FALSE) {
            if (tcph->seqno() != last_ack_) {
                fprintf(stderr, "pkt seq %d should be %d\n" ,
                    tcph->seqno(), last_ack_);
                abort();
            }
            scb_->UpdateScoreBoard (highest_ack_, tcph);
            /*
             * Check for a duplicate ACK.
             * Check that the SACK block actually
             *  acknowledges new data.
             */
                if(scb_->CheckUpdate()) {
                if (++dupacks_ == numdupacks(cwnd_)) {
                    /*
                     * Assume we dropped just one packet.
                     * Retransmit last ack + 1
                     * and try to resume the sequence.
                     */
                    dupack_action();
                } else if (dupacks_ < numdupacks(cwnd_) && singledup_ ) {
                    send_one();
                }
            }
            if (sfrto_enabled_ && frto_ == 2) {
                /*
                 * SACK-based F-RTO: If SACK only acknowledges
                 * data that was transmitted before RTO and
                 * not acknowledged earlier,
                 * the timeout was spurious.
                 */
                if (scb_->IsChanged() &&
                    !is_sacked(tcph, recover_, maxseq_)) {
                    spurious_timeout();
                } else {
                    t_seqno_ = highest_ack_ + 1;
                    cwnd_ = frto_;
                    frto_ = 0;
                    dupacks_ = 0;
                }
            }
        }
            if (valid_ack || aggressive_maxburst_)
            if (dupacks_ == 0)
                send_much(FALSE, 0, maxburst_);
    } else {
        /* we are in fast recovery */
        --pipe_;
        if ((int)tcph->seqno() >= recover_) {
            /* ACK indicates fast recovery is over */
            recover_ = 0;
            fastrecov_ = FALSE;
            newack(pkt);
            /* if the connection is done, call finish() */
            if ((highest_ack_ >= curseq_-1) && !closed_) {
                closed_ = 1;
                finish();
            }
            timeout_ = FALSE;
            scb_->ClearScoreBoard();

            /* New window: W/2 - K or W/2? */
        } else if ((int)tcph->seqno() > highest_ack_) {
            /* Not out of fast recovery yet.
             * Update highest_ack_, but not last_ack_. */
            highest_ack_ = (int)tcph->seqno();
            scb_->UpdateScoreBoard (highest_ack_, tcph);
            if (partial_ack_) {
              /* partial_ack_ is needed to guarantee that */
              /*  a new packet is sent in response to a   */
              /*  partial ack.                            */
                partial_ack_action();
                ++pipe_;
                if (firstpartial_ == 0) {
                    newtimer(pkt);
                    t_backoff_ = 1;
                    firstpartial_ = 1;
                }
            } else {
                --pipe_;
                newtimer(pkt);
                t_backoff_ = 1;
             /* If this partial ACK is from a retransmitted pkt,*/
             /* then we decrement pipe_ again, so that we never */
             /* do worse than slow-start.  If this partial ACK  */
             /* was instead from the original packet, reordered,*/
             /* then this might be too aggressive. */
            }
        } else if (timeout_ == FALSE) {
            /* got another dup ack */
            scb_->UpdateScoreBoard (highest_ack_, tcph);
                if(scb_->CheckUpdate()) {
                if (dupacks_ > 0)
                        dupacks_++;
            }
        }
            if (valid_ack || aggressive_maxburst_)
            send_much(FALSE, 0, maxburst_);
    }

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


/*
 * Returns TRUE if any of the SACK blocks in the current packet (tcph)
 * cover sequence numbers between seqlo and seqhi
 */
int Sack1TcpAgent::is_sacked(hdr_tcp *tcph, int seqlo, int seqhi)
{
    int i, sleft, sright;
    for (i=0; i < tcph->sa_length(); i++) {
        sleft = tcph->sa_left(i);
        sright = tcph->sa_right(i);

        if ((sright > seqlo && sright <= seqhi) ||
            (sleft >= seqlo && sleft < seqhi) ||
            (sleft < seqlo && sright > seqhi)) {
            return TRUE;
        }
    }
    return FALSE;
}


void
Sack1TcpAgent::dupack_action()
{
    int recovered = (highest_ack_ > recover_);
    if (recovered || (!bug_fix_ && !ecn_)) {
        goto sack_action;
    }
 
    if (ecn_ && last_cwnd_action_ == CWND_ACTION_ECN) {
        last_cwnd_action_ = CWND_ACTION_DUPACK;
        /*
         * What if there is a DUPACK action followed closely by ECN
         * followed closely by a DUPACK action?
         * The optimal thing to do would be to remember all
         * congestion actions from the most recent window
         * of data.  Otherwise "bugfix" might not prevent
         * all unnecessary Fast Retransmits.
         */
        reset_rtx_timer(1,0);
        /*
         * There are three possibilities: 
         * (1) pipe_ = int(cwnd_) - numdupacks_;
         * (2) pipe_ = window() - numdupacks_;
         * (3) pipe_ = maxseq_ - highest_ack_ - numdupacks_;
         * equation (2) takes into account the receiver's
         * advertised window, and equation (3) takes into
         * account a data-limited sender.
         */
        if (singledup_ && LimTransmitFix_) {
          pipe_ = maxseq_ - highest_ack_ - 1;
        }
        else {
          // numdupacks(cwnd_) packets have left the pipe
          pipe_ = maxseq_ - highest_ack_ - numdupacks(cwnd_);
        }
        fastrecov_ = TRUE;
        scb_->MarkRetran(highest_ack_+1);
        output(last_ack_ + 1, TCP_REASON_DUPACK);
        return;
    }

    if (bug_fix_) {
        /*
         * The line below, for "bug_fix_" true, avoids
         * problems with multiple fast retransmits in one
         * window of data.
         */
        return;
    }

sack_action:
    recover_ = maxseq_;
    if (oldCode_) {
        pipe_ = int(cwnd_) - numdupacks(cwnd_);
    } else if (singledup_ && LimTransmitFix_) {
          pipe_ = maxseq_ - highest_ack_ - 1;
    }
    else {
          // numdupacks(cwnd_) packets have left the pipe
          pipe_ = maxseq_ - highest_ack_ - numdupacks(cwnd_);
    }
    reset_rtx_timer(1,0);
    fastrecov_ = TRUE;
    scb_->MarkRetran(highest_ack_+1);
        if (!lossQuickStart()) {
                // we are now going into fast_recovery and will trace that event
                trace_event("FAST_RECOVERY");
                last_cwnd_action_ = CWND_ACTION_DUPACK;
                slowdown(CLOSE_SSTHRESH_HALF|CLOSE_CWND_HALF);
        output(last_ack_ + 1, TCP_REASON_DUPACK);   // from top
        /*
         * If dynamically adjusting numdupacks_, record information
         *  at this point.
         */
    }
    return;
}

/*
 * Process a packet that acks previously unacknowleges data, but
 * does not take us out of Fast Retransmit.
 *
 * The need for a mechanism to ensure that Sack TCP sends a packet in
 * response to a partial ACK has been discussed in
 * "Challenges to Reliable Data Transport over Heterogeneous
 * Wireless Networks", Hari Balakrishnan, 1998, and in
 * "Responding to Spurious Timeouts in TCP", Andrei Gurtov and 
 * Reiner Ludwig, 2003. 
 */
void
Sack1TcpAgent::partial_ack_action()
{
    if (next_pkt_ < highest_ack_ + 1) {
        next_pkt_ = highest_ack_ + 1;
    }
    // Output two packets in response to a partial ack,
    //   so as not to do worse than slow-start.
    int i;
    for (i = 1; i<=2; i++) {
        int getNext = scb_->GetNextUnacked(next_pkt_);
        if (getNext > next_pkt_) {
            next_pkt_ = getNext;
        }
        if (t_seqno_ < next_pkt_) {
            t_seqno_ = next_pkt_;
        }
        output(next_pkt_, TCP_REASON_PARTIALACK);   
        scb_->MarkRetran(next_pkt_);
        ++next_pkt_; 
    }
    return;
}

void Sack1TcpAgent::timeout(int tno)
{
    // F-RTO is not allowed if earlier SACK fast recovery is underway.
    int no_frto = fastrecov_;

    if (tno == TCP_TIMER_RTX) {
        /*
         * IF DSACK and dynamic adjustment of numdupacks_,
         *  check whether a smaller value of numdupacks_
         *  would have prevented this retransmit timeout.
         * If DSACK and detection of premature retransmit
         *  timeouts, then save some info here.
         */ 
        dupacks_ = 0;
        fastrecov_ = FALSE;
        timeout_ = TRUE;
        if (highest_ack_ > last_ack_)
            last_ack_ = highest_ack_;
#ifdef DEBUGSACK1A
        printf ("timeout. highest_ack: %i seqno: %i fid: %i\n", 
            (int)highest_ack_, (int)t_seqno_, fid_);
#endif
        recover_ = maxseq_;
        scb_->ClearScoreBoard();
    }
    TcpAgent::timeout(tno);

    // Overrule frto_ setting that may have been done in TcpAgent
    if (no_frto)
        frto_ = 0;
}

void Sack1TcpAgent::send_much(int force, int reason, int maxburst)
{
    register int found, npacket = 0;
    int win = window();
    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...
     */
    while (((!fastrecov_ && (t_seqno_ <= last_ack_ + win)) ||
            (fastrecov_ && (pipe_ < int(cwnd_)))) 
            && t_seqno_ < curseq_ && found) {

        if (overhead_ == 0 || force) {
            found = 0;
            xmit_seqno = scb_->GetNextRetran ();

#ifdef DEBUGSACK1A
            printf("highest_ack: %d xmit_seqno: %d\n", 
            (int)highest_ack_, xmit_seqno);
#endif
            if (xmit_seqno == -1) { 
                if ((!fastrecov_ && t_seqno_<=highest_ack_+win)||
                    (fastrecov_ && t_seqno_<=highest_ack_+int(wnd_))) {
                    found = 1;
                    xmit_seqno = t_seqno_++;
#ifdef DEBUGSACK1A
                    printf("sending %d fastrecovery: %d win %d\n",
                        xmit_seqno, fastrecov_, win);
#endif
                }
            } else if (recover_>0 && xmit_seqno<=highest_ack_+int(wnd_)) {
                found = 1;
                scb_->MarkRetran (xmit_seqno);
                win = window();
            }
            if (found) {
                output(xmit_seqno, reason);
                if (t_seqno_ <= xmit_seqno)
                    t_seqno_ = xmit_seqno + 1;
                npacket++;
                pipe_++;
                if (QOption_)
                    process_qoption_after_send () ;
                            if (qs_approved_ == 1) {
                                    double delay = (double) t_rtt_ * tcp_tick_ / cwnd_;
                                    delsnd_timer_.resched(delay);
                                    return;
                            }
            }
        } 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 Sack1TcpAgent::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
}

---