tcp-rbp.cc

Go to the documentation of this file.

/* -*-  Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */

/*
 * tcp-rbp.cc
 * Copyright (C) 1997 by the University of Southern California
 * $Id: tcp-rbp.cc,v 1.22 2005/08/25 18:58:12 johnh Exp $
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License,
 * version 2, as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
 *
 *
 * The copyright of this module includes the following
 * linking-with-specific-other-licenses addition:
 *
 * In addition, as a special exception, the copyright holders of
 * this module give you permission to combine (via static or
 * dynamic linking) this module with free software programs or
 * libraries that are released under the GNU LGPL and with code
 * included in the standard release of ns-2 under the Apache 2.0
 * license or under otherwise-compatible licenses with advertising
 * requirements (or modified versions of such code, with unchanged
 * license).  You may copy and distribute such a system following the
 * terms of the GNU GPL for this module and the licenses of the
 * other code concerned, provided that you include the source code of
 * that other code when and as the GNU GPL requires distribution of
 * source code.
 *
 * Note that people who make modified versions of this module
 * are not obligated to grant this special exception for their
 * modified versions; it is their choice whether to do so.  The GNU
 * General Public License gives permission to release a modified
 * version without this exception; this exception also makes it
 * possible to release a modified version which carries forward this
 * exception.
 *
 */

/*
 * Tcp-vegas with Rate-based pacing by John Heidemann <johnh@isi.edu>
 * and Vikram Visweswaraiah <visweswa@isi.edu>.
 * The original SunOS implementation was by Vikram Visweswaraiah
 * and Ashish Savla <asavla@usc.edu>.
 *
 * Rate-based pacing is an experimental addition to TCP
 * to address the slow-start restart problem.
 * See <http://www.isi.edu/lsam/publications/rate_based_pacing/index.html>
 * for details.
 *
 * A paper analysing RBP performance is in progress (as of 19-Jun-97).
 */


#ifndef lint
static const char rcsid[] =
"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcp/tcp-rbp.cc,v 1.22 2005/08/25 18:58:12 johnh Exp $ (NCSU/IBM)";
#endif

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

#include "ip.h"
#include "tcp.h"
#include "flags.h"

#ifndef MIN
#define MIN(x, y) ((x)<(y) ? (x) : (y))
#endif /* ! MIN */

#if 0
#define RBP_DEBUG_PRINTF(x) printf x
#else /* ! 0 */
#define RBP_DEBUG_PRINTF(x)
#endif /* 0 */


#define RBP_MIN_SEGMENTS 2

class RBPVegasTcpAgent;

class RBPVegasPaceTimer : public TimerHandler {
public:
    RBPVegasPaceTimer(RBPVegasTcpAgent *a) : TimerHandler() { a_ = a; }
protected:
    virtual void expire(Event *e);
    RBPVegasTcpAgent *a_;
};
// Hmmm... ``a is a'' in the construction of the RBPVegasPaceTimer edifice :->

class RBPVegasTcpAgent : public virtual VegasTcpAgent {
    friend class RBPVegasPaceTimer;
 public:
    RBPVegasTcpAgent();
    virtual void recv(Packet *pkt, Handler *);
    virtual void timeout(int tno);
    virtual void send_much(int force, int reason, int maxburst);

    double rbp_scale_;   // conversion from actual -> rbp send rates
    enum rbp_rate_algorithms { RBP_NO_ALGORITHM, RBP_VEGAS_RATE_ALGORITHM, RBP_CWND_ALGORITHM };
    int rbp_rate_algorithm_;
protected:
    void paced_send_one();
    int able_to_rbp_send_one();

    // stats on what we did
    int rbp_segs_actually_paced_;

    enum rbp_modes { RBP_GOING, RBP_POSSIBLE, RBP_OFF };
    enum rbp_modes rbp_mode_;
    double rbp_inter_pace_delay_;
    RBPVegasPaceTimer pace_timer_;
};

static class RBPVegasTcpClass : public TclClass {
public:
    RBPVegasTcpClass() : TclClass("Agent/TCP/Vegas/RBP") {}
    TclObject* create(int, const char*const*) {
        return (new RBPVegasTcpAgent());
    }
} class_vegas_rbp;


void RBPVegasPaceTimer::expire(Event *) { a_->paced_send_one(); }


RBPVegasTcpAgent::RBPVegasTcpAgent() : VegasTcpAgent(),
    rbp_mode_(RBP_OFF),
    pace_timer_(this)
{
    bind("rbp_scale_", &rbp_scale_);
    bind("rbp_rate_algorithm_", &rbp_rate_algorithm_);
    bind("rbp_segs_actually_paced_", &rbp_segs_actually_paced_);
    bind("rbp_inter_pace_delay_", &rbp_inter_pace_delay_);
}

void
RBPVegasTcpAgent::recv(Packet *pkt, Handler *hand)
{
    if (rbp_mode_ != RBP_OFF) {
        // reciept of anything disables rbp
        rbp_mode_ = RBP_OFF;
        // Vegas takes care of cwnd.
    };
    VegasTcpAgent::recv(pkt, hand);
}

void
RBPVegasTcpAgent::timeout(int tno)
{
    if (tno == TCP_TIMER_RTX) {
        if (highest_ack_ == maxseq_) {
            // Idle for a while => RBP next time.
            rbp_mode_ = RBP_POSSIBLE;
            return;
        };
    };
    VegasTcpAgent::timeout(tno);
}

void
RBPVegasTcpAgent::send_much(int force, int reason, int maxburst)
{
    if (rbp_mode_ == RBP_POSSIBLE && able_to_rbp_send_one()) {
        // start paced mode
        rbp_mode_ = RBP_GOING; 
        rbp_segs_actually_paced_ = 0;
        double rbwin_vegas;
        switch (rbp_rate_algorithm_) {
        case RBP_VEGAS_RATE_ALGORITHM:
            // Try to follow tcp_output.c here
            // Calculate the vegas window as its reported rate
            // times the rtt.
            rbwin_vegas = v_actual_ * v_rtt_;
            RBP_DEBUG_PRINTF(("-----------------\n"));
            RBP_DEBUG_PRINTF(("rbwin_vegas = %g\nv_actual = %g\nv_rtt =%g\nbase_rtt=%g\n",
                      rbwin_vegas, v_actual_, v_rtt_, v_baseRTT_));
            // Smooth the vegas window
            rbwin_vegas *= rbp_scale_;
            break;
        case RBP_CWND_ALGORITHM:
            // Pace out scaled cwnd.
            rbwin_vegas = cwnd_ * rbp_scale_;
            break;
        default:
            // quiet the compiler.
            rbwin_vegas = 0.0;
            abort();
        };
        rbwin_vegas = int(rbwin_vegas + 0.5);   // round
        // Always pace at least RBP_MIN_SEGMENTS
        if (rbwin_vegas <= RBP_MIN_SEGMENTS) {
            rbwin_vegas = RBP_MIN_SEGMENTS;
        };

        // Conservatively set the congestion window to min of
        // congestion window and the smoothed rbwin_vegas
        RBP_DEBUG_PRINTF(("cwnd before check = %g\n", double(cwnd_)));
        cwnd_ = MIN(cwnd_,(TracedDouble) rbwin_vegas);
        RBP_DEBUG_PRINTF(("cwnd after check = %g\n", double(cwnd_)));
        RBP_DEBUG_PRINTF(("recv win = %g\n", wnd_));
        // RBP timer calculations must be based on the actual
        // window which is the min of the receiver's
        // advertised window and the congestion window.
        // TcpAgent::window() does this job.
        // What this means is we expect to send window() pkts
        // in v_rtt_ time.
        rbp_inter_pace_delay_ = (v_rtt_)/(window() * 1.0);
        RBP_DEBUG_PRINTF(("window is %d\n", window()));
        RBP_DEBUG_PRINTF(("ipt = %g\n", rbp_inter_pace_delay_));
        paced_send_one();
    } else {
        VegasTcpAgent::send_much(force,reason, maxburst);
    }
}

void
RBPVegasTcpAgent::paced_send_one()
{
    if (rbp_mode_ == RBP_GOING && able_to_rbp_send_one()) {
        RBP_DEBUG_PRINTF(("Sending one rbp packet\n"));
        // send one packet
        output(t_seqno_++, TCP_REASON_RBP);
        rbp_segs_actually_paced_++;
        // schedule next pkt
        pace_timer_.resched(rbp_inter_pace_delay_);
    };
}

int
RBPVegasTcpAgent::able_to_rbp_send_one()
{
    return t_seqno_ < curseq_ && t_seqno_ <= highest_ack_ + window();
}


/***********************************************************************
 *
 * The reno-based version
 *
 */


class RBPRenoTcpAgent;

class RBPRenoPaceTimer : public TimerHandler {
public:
    RBPRenoPaceTimer(RBPRenoTcpAgent *a) : TimerHandler() { a_ = a; }
protected:
    virtual void expire(Event *e);
    RBPRenoTcpAgent *a_;
};
// Hmmm... ``a is a'' in the construction of the RBPRenoPaceTimer edifice :->

class RBPRenoTcpAgent : public virtual RenoTcpAgent {
    friend class RBPRenoPaceTimer;
 public:
    RBPRenoTcpAgent();
    virtual void recv(Packet *pkt, Handler *);
    virtual void timeout(int tno);
    virtual void send_much(int force, int reason, int maxburst);

    double rbp_scale_;   // conversion from actual -> rbp send rates
    // enum rbp_rate_algorithms { RBP_NO_ALGORITHM, RBP_VEGAS_RATE_ALGORITHM, RBP_CWND_ALGORITHM };
    // int rbp_rate_algorithm_;
protected:
    void paced_send_one();
    int able_to_rbp_send_one();

    // stats on what we did
    int rbp_segs_actually_paced_;

    enum rbp_modes { RBP_GOING, RBP_POSSIBLE, RBP_OFF };
    enum rbp_modes rbp_mode_;
    double rbp_inter_pace_delay_;
    RBPRenoPaceTimer pace_timer_;
};

static class RBPRenoTcpClass : public TclClass {
public:
    RBPRenoTcpClass() : TclClass("Agent/TCP/Reno/RBP") {}
    TclObject* create(int, const char*const*) {
        return (new RBPRenoTcpAgent());
    }
} class_reno_rbp;


void RBPRenoPaceTimer::expire(Event *) { a_->paced_send_one(); }

RBPRenoTcpAgent::RBPRenoTcpAgent() : TcpAgent(),
    rbp_mode_(RBP_OFF),
    pace_timer_(this)
{
    bind("rbp_scale_", &rbp_scale_);
    // algorithm is not used in Reno
    // bind("rbp_rate_algorithm_", &rbp_rate_algorithm_);
    bind("rbp_segs_actually_paced_", &rbp_segs_actually_paced_);
    bind("rbp_inter_pace_delay_", &rbp_inter_pace_delay_);
}

void
RBPRenoTcpAgent::recv(Packet *pkt, Handler *hand)
{
    if (rbp_mode_ != RBP_OFF) {
        // reciept of anything disables rbp
        rbp_mode_ = RBP_OFF;

        // reset cwnd such that we're now ack clocked.
        hdr_tcp *tcph = hdr_tcp::access(pkt);
        if (tcph->seqno() > last_ack_) {
            /* reno does not do rate adjustments as Vegas;
             * normally, one wouldn't do any adjustments to
             * cwnd and allow the sliding window to do its job
             * But, if cwnd >> amt_paced, then there's a
             * bunch of data that can be sent asap, plus the
             * two (typically, due to delacks) that get opened
             * up due to the first ack. This would lead to
             * a burst, defeating the purpose of pacing.
             * Ideally, one would want cwnd = amt_paced
             * ALWAYS. Since this doesn't necessarily happen,
             * `cap' cwnd to the amt paced and THEN let
             * sliding windows take over. Note that this
             * mechanism will typically result in 3 segs
             * being sent out when the first ack is received.
             */
            cwnd_ = maxseq_ - last_ack_;
            RBP_DEBUG_PRINTF(("\ncwnd-after-first-ack=%g\n", (double)cwnd_));
        };

    };
    RenoTcpAgent::recv(pkt, hand);
}

void
RBPRenoTcpAgent::timeout(int tno)
{
    if (tno == TCP_TIMER_RTX) {
        if (highest_ack_ == maxseq_) {
            // Idle for a while => RBP next time.
            rbp_mode_ = RBP_POSSIBLE;
            return;
        };
    };
    RenoTcpAgent::timeout(tno);
}

void
RBPRenoTcpAgent::send_much(int force, int reason, int maxburst)
{
    if (rbp_mode_ == RBP_POSSIBLE && able_to_rbp_send_one()) {
        // start paced mode
        rbp_mode_ = RBP_GOING; 
        rbp_segs_actually_paced_ = 0;

        // Pace out scaled cwnd.
        double rbwin_reno;
        rbwin_reno = cwnd_ * rbp_scale_;

        rbwin_reno = int(rbwin_reno + 0.5);   // round
        // Always pace at least RBP_MIN_SEGMENTS
        if (rbwin_reno <= RBP_MIN_SEGMENTS) {
            rbwin_reno = RBP_MIN_SEGMENTS;
        };

        // Conservatively set the congestion window to min of
        // congestion window and the smoothed rbwin_reno
        RBP_DEBUG_PRINTF(("cwnd before check = %g\n", double(cwnd_)));
        cwnd_ = MIN(cwnd_,(TracedDouble) rbwin_reno);
        RBP_DEBUG_PRINTF(("cwnd after check = %g\n", double(cwnd_)));
        RBP_DEBUG_PRINTF(("recv win = %g\n", wnd_));
        // RBP timer calculations must be based on the actual
        // window which is the min of the receiver's
        // advertised window and the congestion window.
        // TcpAgent::window() does this job.
        // What this means is we expect to send window() pkts
        // in v_srtt_ time.
        static double srtt_scale = 0.0;
        if (srtt_scale == 0.0) {  // yuck yuck yuck!
            srtt_scale = 1.0; // why are we doing fixed point?
            int i;
            for (i = T_SRTT_BITS; i > 0; i--) {
                srtt_scale /= 2.0;
            };
        }
        rbp_inter_pace_delay_ = (t_srtt_ * srtt_scale * tcp_tick_) / (window() * 1.0);
        RBP_DEBUG_PRINTF(("window is %d\n", window()));
        RBP_DEBUG_PRINTF(("ipt = %g\n", rbp_inter_pace_delay_));
        paced_send_one();
    } else {
        RenoTcpAgent::send_much(force,reason, maxburst);
    };
}

void
RBPRenoTcpAgent::paced_send_one()
{
    if (rbp_mode_ == RBP_GOING && able_to_rbp_send_one()) {
        RBP_DEBUG_PRINTF(("Sending one rbp packet\n"));
        // send one packet
        output(t_seqno_++, TCP_REASON_RBP);
        rbp_segs_actually_paced_++;
        // schedule next pkt
        pace_timer_.resched(rbp_inter_pace_delay_);
    };
}

int
RBPRenoTcpAgent::able_to_rbp_send_one()
{
    return t_seqno_ < curseq_ && t_seqno_ <= highest_ack_ + window();
}

---