tcp-fast.cc

这是一个基于NS2的仿真实现代码

/************************************************************************\
 * TCP-FAST  NS2 Module                                         	*
 * University of Melbourne April 2005                         		*
 *                                                              	*
 * Coding: Tony Cui and Lachlan Andrew                          	*
 *                                                                      *
 * Revision History                                                     *
 * Version 1.1.2                					*
 *     Make FAST_CC_MIQ tunable						*
 *     (using a mi_threshold_ (tunable TCL variable)  to replace it) 	*
 *     Consider the calculation error when cwnd is an integer. Give	*
 *     user 3 choices the calculate cwnd.(use integer without		*
 *     considering calculation error (mode 0),  using integer 		*
 *     with considering calculatioin error (mode 1) and using double	*
 *     (mode 2).							*
 *     Fix a bug in fast_cc: add acks_per_rtt++ in the function. 	*
 *     Fix a bug in fast_cc: compare t_seqno and tcph->seqno() to       *
 *     prevent t_seqno greater than tcph->seqno().			*
 *     Allow user update cwnd every other rtt (default is every rtt)	*
 * Version 1.1.1                                                        *
 *     Set ECT bit correctly if ECN capable				*
 * Version 1.1                                                          *
 *     Add SACK function into Fast                                      *
 *     Fix bug in output function which didn't consider SYN packets.    *
 *     Fix bug in using INT_VARABLE_INVALID_VALUE instead of            *
 *     DOUBLE_VARABLE_INVALID_VALUE                                     *
 * Version 1.0.1 Released 13 November, 2004                             *
 *     Fix bug in baseRTT_ estimation with pk loss                      *
 * Version 1.0   Released 24 September, 2004                            *
\************************************************************************/

#ifndef lint
static const char rcsid[] =
"@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcp/tcp-fast.cc,v 1.35 2004/12/14 05:05:21 xuanc Exp $ (NCSU/IBM)";
#endif

#define FAST_ALLOW_CC 		0x1
#define FAST_ALLOW_MI		0x2
#define INT_VARABLE_INVALID_VALUE	999999999
#define DOUBLE_VARABLE_INVALID_VALUE 	99999999999.0

#include "ip.h"
#include "tcp.h"
#include "tcp-fast.h"
#include "flags.h"
#include "random.h"

/******************************************************************************/
static class FastTcpClass : public TclClass {
public:
	FastTcpClass() : TclClass("Agent/TCP/Fast") {}
	TclObject* create(int, const char*const*) {
		return (new FastTcpAgent());
	}
} class_fast;


/******************************************************************************/
FastTcpAgent::~FastTcpAgent()
{
#ifdef FASTTCPAGENT_DEBUG
	fclose(fasttcpagent_recordfps[0]);
	fclose(fasttcpagent_recordfps[1]);
#endif

	delete scb_;

	if (sendtime_)
		delete []sendtime_;
	if (transmits_)
		delete []transmits_;
	if (cwnd_array_)
		delete []cwnd_array_;
}

/******************************************************************************/
FastTcpAgent::FastTcpAgent() : TcpAgent(),
	avgRTT_(0), baseRTT_(0), avg_cwnd_last_RTT_(1),
	alpha_(0), beta_(0), fastrecov_(FALSE),
	pipe_(-1), next_pkt_(0), firstpartial_(0),
	last_natural_ack_number_(-1), on_first_rtt_(true)
{
	sendtime_ = NULL;
	transmits_ = NULL;
	cwnd_array_ = NULL;
	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();

#ifdef TCP_DELAY_BIND_ALL
#else /* ! TCP_DELAY_BIND_ALL */
	/*bind tunable parameters*/
	bind("fast_update_cwnd_interval_", &cwnd_update_period_);
	bind("avg_cwnd_last_RTT_", &avg_cwnd_last_RTT_);
	bind("avgRTT_", &avgRTT_);
	bind("baseRTT_", &baseRTT_);
	bind("alpha_", &alpha_);
	bind("beta_", &beta_);
	bind("high_accuracy_cwnd_", &high_accuracy_cwnd_);
	bind("mi_threshold_", &mi_threshold_);
#endif /* TCP_DELAY_BIND_ALL */

#ifdef FASTTCPAGENT_DEBUG
	static unsigned int s_agent_ID = 0;
	char strTmp[30];
	sprintf(strTmp, "agent%d_%s.txt", s_agent_ID, "record0");
	fasttcpagent_recordfps[0] = fopen(strTmp, "w+");
	sprintf(strTmp, "agent%d_%s.txt", s_agent_ID, "record1");
	fasttcpagent_recordfps[1] = fopen(strTmp, "w+");
	s_agent_ID++;
#endif
}

/******************************************************************************/
void
FastTcpAgent::delay_bind_init_all()
{
#ifdef TCP_DELAY_BIND_ALL
        // Defaults for bound variables should be set in ns-default.tcl.
	delay_bind_init_one("cwnd_update_period_");
	delay_bind_init_one("avg_cwnd_last_RTT_");
	delay_bind_init_one("avgRTT_");
	delay_bind_init_one("baseRTT_");
	delay_bind_init_one("alpha_");
	delay_bind_init_one("beta_");
	delay_bind_init_one("high_accuracy_cwnd_");
	delay_bind_init_one("mi_threshold_");
#endif /* TCP_DELAY_BIND_ALL */
	TcpAgent::delay_bind_init_all();

	reset();
}

/******************************************************************************/
int
FastTcpAgent::delay_bind_dispatch(const char *varName, const char *localName, TclObject *tracer)
{
#ifdef TCP_DELAY_BIND_ALL
	if (delay_bind(varName, localName, "cwnd_update_period_", &fast_update_cwnd_interval_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "avg_cwnd_last_RTT_", &avg_cwnd_last_RTT_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "avgRTT_", &avgRTT_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "baseRTT_", &baseRTT_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "alpha_", &alpha_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "beta_", &beta_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "high_accuracy_cwnd_", &high_accuracy_cwnd_, tracer))
		return TCL_OK;
	if (delay_bind(varName, localName, "mi_threshold_", &mi_threshold_, tracer))
		return TCL_OK;
#endif /* TCP_DELAY_BIND_ALL */

	return TcpAgent::delay_bind_dispatch(varName, localName, tracer);
}

/******************************************************************************/
/* Print out just the variable that is modified */
void
FastTcpAgent::traceVar(TracedVar* v) 
{
	double curtime;
	Scheduler& s = Scheduler::instance();
	char wrk[500];
	int n;

	curtime = &s ? s.clock() : 0;
	if (!strcmp(v->name(), "avgRTT_") || !strcmp(v->name(), "baseRTT_") || !strcmp(v->name(), "mi_threshold_"))
		sprintf(wrk,"%-8.5f %-2d %-2d %-2d %-2d %s %-6.3f",
			curtime, addr(), port(), daddr(), dport(),
			v->name(), double(*((TracedDouble*) v))); 
	else if (!strcmp(v->name(), "avg_cwnd_last_RTT_") || !strcmp(v->name(), "alpha_") || !strcmp(v->name(), "high_accuracy_cwnd_" ) || !strcmp(v->name(), "beta_"))
		sprintf(wrk,"%-8.5f %-2d %-2d %-2d %-2d %s %d",
			curtime, addr(), port(), daddr(), dport(),
			v->name(), int(*((TracedInt*) v))); 
	else
	{
		TcpAgent::traceVar(v);
		return;
	}

	n = strlen(wrk);
	wrk[n] = '\n';
	wrk[n+1] = 0;
	if (channel_)
		(void)Tcl_Write(channel_, wrk, n+1);
	wrk[n] = 0;

	return;
}

/******************************************************************************/
void
FastTcpAgent::reset ()
{
	fast_opts = 0;
	fast_opts |= FAST_ALLOW_CC;
	fast_opts |= FAST_ALLOW_MI;
	cwnd_update_time = fasttime();
	cwnd_increments = 0;
	firstrecv_ = -1.0;
	slowstart_ = 2;
	acks_per_rtt = 0;
	acks_last_rtt = 0;
	bc_ack = 0;
	bc_spacing = 0;
	t_backoff_=1;
	baseRTT_ = DOUBLE_VARABLE_INVALID_VALUE;
	newcwnd_ = DOUBLE_VARABLE_INVALID_VALUE;
	currentTime = 0;
	fast_calc_cwnd_end = 0;
	scb_->ClearScoreBoard();
	cwnd_remainder = 0;

	TcpAgent::reset ();
}

#define CWND_USE_INT	0
#define CWND_USE_INT_CONSIDER_ERROR	1
#define CWND_USE_DOUBLE	2
/******************************************************************************/
/*this function should be used to calculate the new cwnd_ size in every update*/
double
FastTcpAgent::fast_calc_cwnd(double cwnd,double old_cwnd)
{
        double q = avgRTT_ - baseRTT_;
        double cwnd_array_q = old_cwnd * q;
        double target_cwnd = cwnd;

        if ( avgRTT_ == 0 || baseRTT_ == DOUBLE_VARABLE_INVALID_VALUE )
        {
                return cwnd;
        }

        if ( fast_opts & FAST_ALLOW_CC )
        {
                if ( cwnd_array_q < alpha_ * avgRTT_ ||
		     cwnd_array_q >= beta_ * avgRTT_ )
                {
                        target_cwnd = (cwnd + old_cwnd * (baseRTT_/avgRTT_) + alpha_) / 2;
			if ( high_accuracy_cwnd_ == CWND_USE_INT_CONSIDER_ERROR ||
			     high_accuracy_cwnd_ == CWND_USE_INT )	//we use intergal to store cwnd.
			{
				if (high_accuracy_cwnd_ == CWND_USE_INT_CONSIDER_ERROR)	//we consider the calculation error.
				{
					cwnd_remainder += (target_cwnd - (int)target_cwnd);
					if (cwnd_remainder > 1)
					{
						target_cwnd++;
						cwnd_remainder--;
					}
				}
				target_cwnd = (int)target_cwnd;
			}
                }
        }

        return target_cwnd;
}

/******************************************************************************/
/* in this functioin, we can get the new average rtt which */
/* will be used to get the new cwnd_ size */
double
FastTcpAgent::fast_est_update_avgrtt(double rtt)
{
	double scale = avg_cwnd_last_RTT_/3;
	double avgRTT=avgRTT_;
	if ( !avgRTT)
		avgRTT = rtt;
	else if ( scale > 256 )
	{
		avgRTT = ((scale-1) * avgRTT + rtt)/scale;
	}
	else
	{
		avgRTT = (avgRTT*255 + rtt)/256;
	}
	return (double)avgRTT;
}

/******************************************************************************/
/* We get average cwnd size which will be used as a history record. */
double
FastTcpAgent::fast_est_update_avg_cwnd(int inst_cwnd)
{
#if 0
	unsigned int scale = avg_cwnd_last_RTT_/3;
	double avg_cwnd=avg_cwnd_last_RTT_;

	if ( !avg_cwnd)
		avg_cwnd = inst_cwnd;
	else if ( scale > 256 )
	{
		avg_cwnd = ((scale-1) * avg_cwnd + inst_cwnd)/scale;
	}
	else
	{
		avg_cwnd = (avg_cwnd*255 + inst_cwnd)/256;
	}
	return avg_cwnd;
#endif
	return (double)inst_cwnd;
}

/******************************************************************************/
/* parameter estimation */
void
FastTcpAgent::fast_est(Packet *pkt,double rtt)
{			
	hdr_tcp *tcph = hdr_tcp::access(pkt);

	if(rtt < baseRTT_)
		baseRTT_ = rtt;
	avg_cwnd_last_RTT_ = (fast_est_update_avg_cwnd(t_seqno_ - tcph->seqno() - dupacks_));
	avgRTT_ = fast_est_update_avgrtt(rtt);
}

//#define UPDATE_CWND_EVERY_OTHER_RTT
/******************************************************************************/
/* congestion control */
void
FastTcpAgent::fast_cc(double rtt, double old_cwnd)
{
	// We update acks_last_rtt every RTT.
	if ( fast_calc_cwnd_end + rtt < currentTime ) {
		fast_calc_cwnd_end = currentTime;
		acks_last_rtt = acks_per_rtt;
		acks_per_rtt = 0;
		if ( on_first_rtt_ == true )	on_first_rtt_ = false;
		else	on_first_rtt_ = true;
	}
	acks_per_rtt++;

	// We use MI to increase cwnd_ when there is little queueing delay 
	if ( avgRTT_ - baseRTT_ < mi_threshold_ && (fast_opts & FAST_ALLOW_MI) ) {
		cwnd_++;
		cwnd_update_time = currentTime;
		return;
	}

	// If queueing delay is large, we use fast algorithm
	if ( currentTime >= cwnd_update_time + fast_update_cwnd_interval_ 
#ifdef	UPDATE_CWND_EVERY_OTHER_RTT
	&& on_first_rtt_ == true
#endif
	) {
		double updated_cwnd;
		cwnd_increments = 0;
		updated_cwnd = fast_calc_cwnd(cwnd_,old_cwnd);
		if ( updated_cwnd >= cwnd_ && baseRTT_ >= 0.004 && baseRTT_ != DOUBLE_VARABLE_INVALID_VALUE ) {
			fast_pace(&cwnd_, (int)(updated_cwnd-cwnd_));
		}
		else
			cwnd_ = updated_cwnd;
		cwnd_update_time = currentTime;
	}
	else if ( baseRTT_ >= 0.004 && baseRTT_ != DOUBLE_VARABLE_INVALID_VALUE )
		fast_pace(&cwnd_, 0);
}

#define MIN(x, y) ((x)<(y) ? (x) : (y))
/******************************************************************************/
void
FastTcpAgent::recv(Packet *pkt, Handler *)
{
	currentTime = fasttime();
	hdr_tcp *tcph = hdr_tcp::access(pkt);
	hdr_flags *flagh = hdr_flags::access(pkt);
	int valid_ack = 0;

	if (qs_approved_ == 1 && tcph->seqno() > last_ack_)
		endQuickStart();
	if (qs_requested_ == 1)
		processQuickStart(pkt);

	/* W.N.: check if this is from a previous incarnation */
	if (tcph->ts() < lastreset_) {
		// Remove packet and do nothing
 		Packet::free(pkt);
		return;
	}
	++nackpack_;
	if(firstrecv_<0) { // init fast rtt vars
		firstrecv_ = currentTime;
		baseRTT_ = avgRTT_ = rtt_ = firstrecv_;
	}

	if (flagh->ecnecho())
		ecn(tcph->seqno());

	int ecnecho = hdr_flags::access(pkt)->ecnecho();
	if (ecnecho && ecn_)
		ecn(tcph->seqno());
	// Check if ACK is valid.  Suggestion by Mark Allman.
        if (tcph->seqno() >= last_ack_)
		valid_ack = 1;

#ifdef FASTTCPAGENT_DEBUG
	if (cwnd_ <= 0)
		printf("%8.3f : cwnd is not positive! cwnd is %f .\n", (double)currentTime, (double)cwnd_);
#endif	
	/*
	 * 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_) {
			if (last_ack_ == 0 ) {
				cwnd_ = initial_window();
			}

			/* check if cwnd has been inflated */
			if(dupacks_ > numdupacks_ &&  cwnd_ > newcwnd_) {
				//check t_seqno_ before changing cwnd.
        			if (t_seqno_ < tcph->seqno())
				        t_seqno_ = tcph->seqno();
				//cwnd becomes a negative number in some case.
				
				cwnd_ = t_seqno_ - tcph->seqno() + 1;
				dupacks_ = 0;
				for (int i=0;i<maxwnd_;i++)
					cwnd_array_[i]=cwnd_;
			}

			firstpartial_ = 0;

			// reset sendtime for acked pkts and incr transmits_
			double sendTime = sendtime_[tcph->seqno()%maxwnd_];
			double old_pif=cwnd_array_[tcph->seqno()%maxwnd_];
			int transmits = transmits_[tcph->seqno()% maxwnd_];
			for(int k= (last_natural_ack_number_+1); k<=tcph->seqno(); ++k) {
				sendtime_[k%maxwnd_] = -1.0;
				transmits_[k%maxwnd_] = 0;
				cwnd_array_[k%maxwnd_]=-1;
			}
			if (t_seqno_ > tcph->seqno()){
				if ((transmits == 1) && (currentTime - sendTime > 0))
					rtt_ = currentTime - sendTime;
				else
					rtt_ = avgRTT_;
			}else rtt_ = avgRTT_;

			fast_recv_newack_helper(pkt);
			timeout_ = FALSE;
			scb_->ClearScoreBoard();
			fast_est(pkt, rtt_);
			fast_cc(rtt_, old_pif);
			last_natural_ack_number_ = tcph->seqno();
		} else if ((int)tcph->seqno() < last_ack_) {
			/*NOTHING*/
		//the follows are if (int)tcph->seqno() == last_ack_
		} 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