scoreboard-rh.cc

Ns2 TCP 协议改进 版本 提高goodput

/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1996 The Regents of the University of California.
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 * 	This product includes software developed by the Network Research
 * 	Group at Lawrence Berkeley National Laboratory.
 * 4. Neither the name of the University nor of the Laboratory may be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */


/* 9/96 Pittsburgh Supercomputing Center
 *      UpdateScoreBoard, CheckSndNxt, MarkRetran modified for fack
 */

#ifndef lint
static const char rcsid[] =
    "@(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcp/scoreboard-rh.cc,v 1.2 2000/08/12 21:45:39 sfloyd Exp $ (LBL)";
#endif

/*  A quick hack version of the scoreboard  */
#include <stdlib.h>
#include <stdio.h>
#include <sys/types.h>
#include <math.h>

#include "packet.h"
#include "scoreboard-rh.h"
#include "tcp.h"

#define ASSERT(x) if (!(x)) {printf ("Assert SB failed\n"); exit(1);}
#define ASSERT1(x) if (!(x)) {printf ("Assert1 SB (length)\n"); exit(1);}

#define SBNI SBN[i%SBSIZE]

// last_ack = TCP last ack
int ScoreBoardRH::UpdateScoreBoard (int last_ack, hdr_tcp* tcph, int rh_id)
{
	int i, sack_index, sack_left, sack_right;
	int sack_max = 0;
	int retran_decr = 0;

	/* Can't do this, because we need to process out the retran_decr  */
#if 0
	if (tcph->sa_length() == 0) {
		// There are no SACK blocks, so clear the scoreboard.
		this->ClearScoreBoard();
		return(0);
	}
#endif

	/*  What we do need to do is not create a scoreboard if we don't need one.  */
	if ((tcph->sa_length() == 0) && (length_ == 0)) {
		return(0);
	}
	

	//  If there is no scoreboard, create one.
	if (length_ == 0) {
		i = last_ack+1;
		SBNI.seq_no_ = i;
		SBNI.ack_flag_ = 0;
		SBNI.sack_flag_ = 0;
		SBNI.retran_ = 0;
		SBNI.snd_nxt_ = 0;
		SBNI.sack_cnt_ = 0;
		SBNI.rh_id_ = 0;
		first_ = i%SBSIZE;
		length_++;
		if (length_ >= SBSIZE) {
			printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
			exit(1);
		}
	}	

	//  Advance the left edge of the block.
	if (SBN[first_].seq_no_ <= last_ack) {
		for (i=SBN[(first_)%SBSIZE].seq_no_; i<=last_ack; i++) {
			//  Advance the ACK
			if (SBNI.seq_no_ <= last_ack) {
				ASSERT(first_ == i%SBSIZE);
				first_ = (first_+1)%SBSIZE; 
				length_--;
				ASSERT1(length_ >= 0);
				SBNI.ack_flag_ = 1;
				SBNI.sack_flag_ = 1;
				if (SBNI.retran_) {
					SBNI.retran_ = 0;
					SBNI.snd_nxt_ = 0;
					retran_decr++;
					retran_sacked_ = rh_id;
				}
				if (length_==0) 
					break;
			}
		}
	}

	for (sack_index=0; sack_index < tcph->sa_length(); sack_index++) {
		sack_left = tcph->sa_left(sack_index);
		sack_right = tcph->sa_right(sack_index);

		/*  Remember the highest segment SACKed by this packet  */
		if (sack_right > sack_max) {
			sack_max = sack_right;
		}

		//  Create new entries off the right side.
		if (sack_right > SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_) {
			//  Create new entries
			for (i = SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_+1; i<sack_right; i++) {
				SBNI.seq_no_ = i;
				SBNI.ack_flag_ = 0;
				SBNI.sack_flag_ = 0;
				SBNI.retran_ = 0;
				SBNI.snd_nxt_ = 0;
				SBNI.sack_cnt_ = 0;
				SBNI.rh_id_ = 0;
				length_++;
				if (length_ >= SBSIZE) {
					printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
					exit(1);
				}
			}
		}
		
		for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_right; i++) {
			//  Check to see if this segment is now covered by the sack block
			if (SBNI.seq_no_ >= sack_left && SBNI.seq_no_ < sack_right) {
				if (! SBNI.sack_flag_) {
					SBNI.sack_flag_ = 1;
				}
				if (SBNI.retran_) {
					SBNI.retran_ = 0;
					SBNI.snd_nxt_ = 0;
					retran_decr++;
					retran_sacked_ = rh_id;
				}
			}
		}
	}

	/*  Now go through the whole scoreboard and update sack_cnt
	    on holes which still exist.  */
	if (length_ != 0) {
		for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_max; i++) {
			//  Check to see if this segment is a hole
			if (!SBNI.ack_flag_ && !SBNI.sack_flag_) {
				SBNI.sack_cnt_++;
			}
		}
	}

	retran_decr += CheckSndNxt(sack_max);

	return (retran_decr);
}
int ScoreBoardRH::CheckSndNxt (int sack_max)
{
	int i;
	int num_lost = 0;

	if (length_ != 0) {
		for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_max; i++) {
			//  Check to see if this segment's snd_nxt_ is now covered by the sack block
			if (SBNI.retran_ && SBNI.snd_nxt_ < sack_max) {
				// the packet was lost again
				SBNI.retran_ = 0;
				SBNI.snd_nxt_ = 0;
				SBNI.sack_cnt_ = 1;
				num_lost++;
			}
		}
	}
	return (num_lost);


}

void ScoreBoardRH::ClearScoreBoard()
{
	length_ = 0;
}

/*
 * GetNextRetran() returns "-1" if there is no packet that is
 *   not acked and not sacked and not retransmitted.
 */
int ScoreBoardRH::GetNextRetran()	// Returns sequence number of next pkt...
{
	int i;

	if (length_) {
		for (i=SBN[(first_)%SBSIZE].seq_no_; 
		     i<SBN[(first_)%SBSIZE].seq_no_+length_; i++) {
			if (!SBNI.ack_flag_ && !SBNI.sack_flag_ && !SBNI.retran_
			    && (SBNI.sack_cnt_ >= *numdupacks_)) {
				return (i);
			}
		}
	}
	return (-1);
}


void ScoreBoardRH::MarkRetran (int retran_seqno, int snd_nxt, int rh_id)
{
	SBN[retran_seqno%SBSIZE].retran_ = 1;
	SBN[retran_seqno%SBSIZE].snd_nxt_ = snd_nxt;
	SBN[retran_seqno%SBSIZE].rh_id_ = rh_id;
	retran_occured_ = rh_id;
}

int ScoreBoardRH::GetFack (int last_ack)
{
	if (length_) {
		return(SBN[(first_)%SBSIZE].seq_no_+length_-1);
	}
	else {
		return(last_ack);
	}
}

int ScoreBoardRH::GetNewHoles ()
{
	int i, new_holes=0;

	for (i=SBN[(first_)%SBSIZE].seq_no_;
	     i<SBN[(first_)%SBSIZE].seq_no_+length_; i++) {
		//  Check to see if this segment is a new hole
#if 1
		if (!SBNI.ack_flag_ && !SBNI.sack_flag_ && SBNI.sack_cnt_ == 1) {
			new_holes++;
		}
#else
		if (!SBNI.ack_flag_ && !SBNI.sack_flag_ && SBNI.sack_cnt_ == *numdupacks_) {
			new_holes++;
		}
#endif
	}
	return (new_holes);
}

void ScoreBoardRH::TimeoutScoreBoard (int snd_nxt)
{
	int i, sack_right;

	if (length_ == 0) {
		// No need to do anything!  
		return;
	}

	sack_right = snd_nxt;  // Use this to know how far to extend.

	//  Create new entries off the right side.
	if (sack_right > SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_) {
		//  Create new entries
		for (i = SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_+1; i<sack_right; i++) {
			SBNI.seq_no_ = i;
			SBNI.ack_flag_ = 0;
			SBNI.sack_flag_ = 0;
			SBNI.retran_ = 0;
			SBNI.snd_nxt_ = 0;
			SBNI.sack_cnt_ = 0;
			SBNI.rh_id_ = 0;
			length_++;
			if (length_ >= SBSIZE) {
				printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
				exit(1);
			}
		}
	}

	/*  Now go through the whole scoreboard and update sack_cnt on holes;
	    clear retran flag on everything.  */
	for (i=SBN[(first_)%SBSIZE].seq_no_;
	     i<SBN[(first_)%SBSIZE].seq_no_+length_; i++) {
		//  Check to see if this segment is a hole
		if (!SBNI.ack_flag_ && !SBNI.sack_flag_) {
			SBNI.retran_ = 0;
			SBNI.snd_nxt_ = 0;
			SBNI.sack_cnt_ = *numdupacks_;  // This forces all holes to be retransmitted.
		}
	}

	/*  And, finally, check the first segment in case of a renege.  */
	i=SBN[(first_)%SBSIZE].seq_no_;
	if (!SBNI.ack_flag_ && SBNI.sack_flag_) {
		printf ("Renege!!! seqno = %d\n", SBNI.seq_no_);
		SBNI.sack_flag_ = 0;
		SBNI.retran_ = 0;
		SBNI.snd_nxt_ = 0;
		SBNI.sack_cnt_ = *numdupacks_;  // This forces it to be retransmitted.
	}
}

#if 0
/*  This routine inserts a fake sack block of length num_dupacks,
    starting at last_ack+1.  It is for use during NewReno recovery.
*/
int ScoreBoardRH::FakeSack (int last_ack, int num_dupacks)
{
	int i, sack_left, sack_right;
	int retran_decr = 0;

	//  If there is no scoreboard, create one.
	if (length_ == 0) {
		i = last_ack+1;
		SBNI.seq_no_ = i;
		SBNI.ack_flag_ = 0;
		SBNI.sack_flag_ = 0;
		SBNI.retran_ = 0;
		SBNI.snd_nxt_ = 0;
		SBNI.sack_cnt_ = 0;
		SBNI.rh_id_ = 0;
		first_ = i%SBSIZE;
		length_++;
		if (length_ >= SBSIZE) {
			printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
			exit(1);
		}
	}	

	//  Advance the left edge of the scoreboard.
	if (SBN[first_].seq_no_ <= last_ack) {
		for (i=SBN[(first_)%SBSIZE].seq_no_; i<=last_ack; i++) {
			//  Advance the ACK
			if (SBNI.seq_no_ <= last_ack) {
				ASSERT(first_ == i%SBSIZE);
				first_ = (first_+1)%SBSIZE; 
				length_--;
				ASSERT1(length_ >= 0);
				SBNI.ack_flag_ = 1;
				SBNI.sack_flag_ = 1;
				if (SBNI.retran_) {
					SBNI.retran_ = 0;
					SBNI.snd_nxt_ = 0;
					retran_decr++;
				}
				if (length_==0) 
					break;
			}
		}
		/*  Now create a new hole in the first position  */
		i=SBN[(first_)%SBSIZE].seq_no_;
		SBNI.ack_flag_ = 0;
		SBNI.sack_flag_ = 0;
		SBNI.retran_ = 0;
		SBNI.snd_nxt_ = 0;
		SBNI.rh_id_ = 0;
		SBNI.sack_cnt_ = num_dupacks;
	}

	sack_left = last_ack + 1;
	sack_right = sack_left + num_dupacks - 1;

	//  Create new entries off the right side.
	if (sack_right > SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_) {
		//  Create new entries
		for (i = SBN[(first_+length_+SBSIZE-1)%SBSIZE].seq_no_+1; i<sack_right; i++) {
			SBNI.seq_no_ = i;
			SBNI.ack_flag_ = 0;
			SBNI.sack_flag_ = 0;
			SBNI.retran_ = 0;
			SBNI.snd_nxt_ = 0;
			SBNI.sack_cnt_ = 0;
			SBNI.rh_id_ = 0;
			length_++;
			if (length_ >= SBSIZE) {
				printf ("Error, scoreboard too large (increase SBSIZE for more space)\n");
				exit(1);
			}
		}
	}
		
	for (i=SBN[(first_)%SBSIZE].seq_no_; i<sack_right; i++) {
		//  Check to see if this segment is now covered by the sack block
		if (SBNI.seq_no_ >= sack_left && SBNI.seq_no_ < sack_right) {
			if (! SBNI.sack_flag_) {
				SBNI.sack_flag_ = 1;
			}
			if (SBNI.retran_) {
				SBNI.retran_ = 0;
				retran_decr++;
			}
		}
	}

	/*  Now go through the whole scoreboard and update sack_cnt
	    on holes which still exist.  In this case the only possible 
	    case is the first hole.  */
        i=SBN[(first_)%SBSIZE].seq_no_;
	//  Check to see if this segment is a hole
	if (!SBNI.ack_flag_ && !SBNI.sack_flag_) {
		SBNI.sack_cnt_++;
	}

	return (retran_decr);
}

#endif

int ScoreBoardRH::RetranSacked (int rh_id) {
	return (retran_sacked_ == rh_id);
}