fairblue.cc

ns2中没有的关于BLUE和SFB的仿真源码。

/* -*-	Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
/*
 * Copyright (c) 1994 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. Al ladvertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the Computer Systems
 *	Engineering Group at Lawrence Berkeley 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.
 */

/*Ported to ns2.1b8 by Sunil Thulasidasan, LANL. 11/05/2001*/
/*Last updated on 09/13/2002 */

#include <math.h>
#include <stdlib.h>
#include <sys/types.h>
#include "fairblue.h"
#include "random.h"
#include "delay.h"
#include "flags.h"

int 
hashit(unsigned int a, unsigned int b, unsigned int c, unsigned int d, int modulus)
{
        int h;
        h = ((a << 6) + (b << 12) + (c << 18) + (d << 24) ) % modulus;
        return h;
}


int 
sfbhash(hdr_ip* pkt, int level, unsigned int fudge)
{
	unsigned int i,j;
	switch (level) {
	case 0:
		j = (unsigned int) (pkt->dport() * fudge);
		i = hashit(int(pkt->daddr()), int(pkt->sport()), int(pkt->saddr()), 
			   j, SFQ_BINS);
		break;
	case 1:
		j = (unsigned int)(pkt->sport() * fudge);
		i = hashit(int(pkt->saddr()),int(pkt->dport()),j,int(pkt->daddr()),
			   SFQ_BINS);
		break;
	}
	
	/*If more levels are added to the bloom filter, the functions*/
	/*go here. - Sunil.*/
	
	return(i);
}



static class FairBlueClass : public TclClass {

 public:
	FairBlueClass() : TclClass("Queue/SFB") {}
	TclObject* create(int, const char*const*) {
		return (new FairBlue);
	}
} class_fairblue;


FairBlue::FairBlue() { 
	q_ = new PacketQueue();
	pq_ = q_;
	bind_bool("drop_front_", &drop_front_);
	bind_bool("bytes", &bytes_ );
	bind_bool("setbit", &setbit_);
	bind("decrement", &decrement_);
	bind("increment", &increment_);
	bind_time("hold-time", &holdtime_);
	bind("algorithm", &algorithm_);
	bind_time("pbox-time", &pboxtime_);
	bind("pktsize", &mean_pktsize_);
	bind_time("hinterval", &hinterval_);
}


FairBlue::~FairBlue() {
	{
		delete q_;
	}
	
}

int 
FairBlue::command(int argc, const char*const* argv) {
		
	Tcl& tcl = Tcl::instance();
	if (argc == 3) {
		if (!strcmp(argv[1], "packetqueue-attach")) {
			delete q_;
			if (!(q_ = (PacketQueue*) TclObject::lookup(argv[2])))
				return (TCL_ERROR);
			else {
				pq_ = q_;
				return (TCL_OK);
			}
		}
		
		if (strcmp(argv[1], "link") == 0) {
			LinkDelay* link_  = (LinkDelay*)TclObject::lookup(argv[2]);
			if (link_ == 0) {
				tcl.resultf("SFB : No link delay Object %s\n",
					    argv[2]);
				
				return(TCL_ERROR);
			}

			
			bandwidth_ = link_->bandwidth();
			return(TCL_OK);
		}
	}
	
	return Queue::command(argc, argv);
}


void
FairBlue::reset()
{

	Queue::reset();

	/*packet time constant - units is secs/pkt */

	ptc_ = (8 * mean_pktsize_)/bandwidth_;
	idle_ = 1;
	idletime_ = Scheduler::instance().clock();

	for (int i = 0; i < SFQ_LEVELS; i++)
		for (int j = 0; j < SFQ_BINS; j++) 
			for (int s=0;s<2;s++) {
				
				bins[i][j][s].pkts = 0;
				bins[i][j][s].pmark = 0;
				bins[i][j][s].freezetime = 0;
				//bins[i][j].penalizetime = 0;
			}
	
	allocation_ = qlim_/SFQ_BINS;
	drop_thresh_ = allocation_ + allocation_/2;
	
	//clearpkts_ = 0;
	//pbox_count_ = 0;
	pboxfreeze_ = 0;
	last_fudge_ = 1;
	cursfq_ = 0;
	newsfq_ = 1;

}

void
FairBlue::reset_bins()
{
	clearpkts_ = q_->length();
	newsfq_ = cursfq_;
	cursfq_ = 1 - cursfq_;
	for (int i = 0; i < SFQ_LEVELS; i++)
		for (int j = 0; j < SFQ_BINS; j++) {
			bins[i][j][cursfq_].pkts = 0;
			bins[i][j][cursfq_].freezetime = 0;
			if (bins[i][j][cursfq_].pmark > 1.00)
				bins[i][j][cursfq_].pmark = 1.00;
			if (bins[i][j][cursfq_].pmark < 0)
				bins[i][j][cursfq_].pmark = 0;
			
			//keep pmark from before to identify
			//non-responsives immediately
			bins[i][j][newsfq_].pmark = 0.2;
					
		}
}

void
FairBlue::dq_update_bins(hdr_ip* pkt)
{
	double now;
	int i,j,k;

	for (i = 0; i < SFQ_LEVELS; i++) {
		j = sfbhash(pkt,i,currfudge_);
		k = sfbhash(pkt,i,currfudge_ + 1);
		bins[i][j][cursfq_].pkts--;
		if (bins[i][j][cursfq_].pkts <= 0) {
			now = Scheduler::instance().clock();
			bins[i][j][cursfq_].pkts = 0;
			decrement_bin(decrement_,i,j,k);
		}
	}
}

void 
FairBlue::eq_update_bins()
{
	for (int i = 0; i < SFQ_LEVELS; i++)
		bins[i][p_bins[i]][cursfq_].pkts++;
}

void
FairBlue::increment_bin(double increment, int i)
{
	double now = Scheduler::instance().clock();
	switch (algorithm_) {

	case 0:
	default:
		if (now - bins[i][p_bins[i]][cursfq_].freezetime < holdtime_)
			break;
		bins[i][p_bins[i]][cursfq_].freezetime = now;
		bins[i][p_bins[i]][cursfq_].pmark += increment;
		if (bins[i][p_bins[i]][cursfq_].pmark > 1.00)
			bins[i][p_bins[i]][cursfq_].pmark = 1.00;
		bins[i][p_wbins[i]][newsfq_].pmark += increment;
	}
}


void 
FairBlue::increment_bins(double increment)
{
	double now = Scheduler::instance().clock();
	for (int i = 0; i < SFQ_LEVELS; i++) {
		switch (algorithm_) {
		case 0:
		default:
			bins[i][p_bins[i]][cursfq_].freezetime = now;
			bins[i][p_bins[i]][cursfq_].pmark += increment;
			if (bins[i][p_bins[i]][cursfq_].pmark > 1.00)
				bins[i][p_bins[i]][cursfq_].pmark = 1.00;
			bins[i][p_wbins[i]][newsfq_].pmark += increment;
		}
	}
}
		
	

void 
FairBlue::decrement_bin(double decrement, int i, int j, int k)
{
	double now = Scheduler::instance().clock();
	switch (algorithm_) {
	case 0:
	default:
		if (now - bins[i][j][cursfq_].freezetime < holdtime_)
			break;
		bins[i][j][cursfq_].freezetime = now;
		bins[i][j][cursfq_].pmark -= decrement;
		if (bins[i][j][cursfq_].pmark < 0)
			bins[i][j][cursfq_].pmark = 0;
		bins[i][k][newsfq_].pmark -= decrement;
		
	}
}



/*
 * Return the next packet in the queue for transmission.
 */
Packet* 
FairBlue::deque()
{

	Packet* pkt = q_->deque();

	double now = Scheduler::instance().clock();
	
	if (pkt != 0) {
		
		hdr_ip* iph = hdr_ip::access(pkt);
		if (iph->pmark()) { /*rogue flow packet*/
			iph->pmark() = 0; /*reset marker bit*/
			if (clearpkts_ > 0) clearpkts_--;
			
			/*clearpkts are the ones which were in the queue when the hash function was perturbed*/
			/*Since the perturbation value (fudge), and thus bin informations for thesem pkts is not known, we do*/
			/*not change accounting information while dequeuing these packets. It is important  not to set*/
			/*the hash interval too small due to this reason. A rule of thumb is to set it to K*D, where D is*/
			  /* the time taken to drain queue*/
		}
		else {
			if (clearpkts_ > 0) clearpkts_--;
			else dq_update_bins(iph);
		}
		
		idle_ = 0;
		
	} else {
		idle_ = 1;
		idletime_ = Scheduler::instance().clock();
	}
	return (pkt);
}

int 
FairBlue::drop_early()
{

	int return_code;
	double now = Scheduler::instance().clock();
	
	return_code = 0;
	
	for (int i=0; i < SFQ_LEVELS; i++) {
		if (bins[i][p_bins[i]][cursfq_].pkts >= allocation_) {
			if (bins[i][p_bins[i]][cursfq_].pkts >= drop_thresh_)
				return_code = 1;
			increment_bin(increment_,i);
		}
	}
	return(return_code);
}

/*Probabilistic marking if ECN is enabled)*/
void
FairBlue::ecn_mark(Packet* pkt)
{
	hdr_flags* hf = hdr_flags::access(pkt); 
	double u = Random::uniform();
	double p;
	double now = Scheduler::instance().clock();
	
	p = MIN(bins[0][p_bins[0]][cursfq_].pmark, bins[1][p_bins[1]][cursfq_].pmark);
	
	if (u <= p) { /*drop or mark*/
		if ( setbit_ && hf->ect())
			hf->ce() = 1; /*Set ECN bit here*/
	}
	
}




int 
FairBlue::pcheck()
{

	// Returns 1 if all pmark > 0.98 and all bins are not empty
	// Returns 0 otherwise

	for (int i=0; i < SFQ_LEVELS; i++) {
		if (bins[i][p_bins[i]][cursfq_].pmark < PM_TH)
			return(0);
	}
	return(1);
}



int 
FairBlue::penalize()
{

  double now =  Scheduler::instance().clock();


  if (pcheck()) {

	  switch(algorithm_) {
	  case 0:
	  default:

		  if ((now - pboxfreeze_) < pboxtime_) {
			  increment_bins(increment_);
			  return(1);
		  }
		  else {
			  //pkt->pbox_ = 1;
			  pboxfreeze_ = now;
			  return(2); /*non conformant or else misclassified flow, but we're going to queue it anyway*/
		  }
		  break;
	  }
  }
  return(0);
}
				  



/*
 * Receive a new packet arriving at the queue.
 * The average queue size is computed.  If the average size
 * exceeds the threshold, then the dropping probability is computed,
 * and the newly-arriving packet is dropped with that probability.
 * The packet is also dropped if the maximum queue size is exceeded.
 */


void 
FairBlue::enque(Packet* pkt)
{

	double now = Scheduler::instance().clock();
	int i,m,y,drp;
	unsigned int fudge = 0;
	hdr_ip* iph = hdr_ip::access(pkt);


	switch (algorithm_) {
	case 3:
	default:
		fudge = (unsigned int) now/hinterval_;
		currfudge_ = fudge;
		if (fudge != last_fudge_) {
			last_fudge_ = fudge;
			reset_bins();
		}
		break;
	}
		
	for (i = 0; i < SFQ_LEVELS; i++) {
		p_bins[i] = sfbhash(iph,i,fudge);
		p_wbins[i] = sfbhash(iph,i,fudge + 1);
	}
	
	y = penalize();
	
	if (y == 1) {
		
		drop(pkt);
	}
	
	else {
        	/*
         	 * Mark each packet with probability edv.v_prob.
         	 */
		if (y == 0) {
			/*First check if flow exceeded allocation*/
			if (drop_early()) {
				drop(pkt);
				return;
			}


			/*check if packet needs to be probabilistically*/
			/*marked, i.e., if ECN is enabled*/
			ecn_mark(pkt);
		
		}
		
			
		/*
		 * If we didn't drop the packet above, send it to the interface,
		 * checking for absolute queue overflow.
		 */
		
		
		q_->enque(pkt);
		if (q_->length() >= qlim_) {
			q_->remove(pkt);
			drop(pkt);
		}
		
		else {
			if (y == 0)
				eq_update_bins();
			else {
				if (y == 2) /*non-conformant or misclassified TCP flow*/
					{
						/*Set rogue flow marker*/
						iph->pmark() = 1;
						//pbox_count_++;
					}
			}
			
			
		}
	}
}