dsred.cc

diff serve for ns-2, work for version 2.29

/* Copyright (C) 2001-2006  Sergio Andreozzi
 *
 * This file is part of DiffServ4NS, a set of improvements to
 * the Network Simulator 2 for DiffServ simulations.
 *
 * Project Homepage: http://diffserv4ns.sourceforge.net/
 *
 * DiffServ4NS is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * DiffServ4NS 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 DiffServ4NS; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 * GNU License: http://www.gnu.org/licenses/gpl.txt
 * 
 * The above copyright applies to the following changes and additions to the official
 * NS2 (http://nsnam.cvs.sourceforge.net/nsnam/ns-2/):
 *
 *  - marking: possibility to define mark rules based on source node, 
 *             destination node, transport protocol type and application type
 *  - new schedulers: WFQ, WF2Q+, SCFQ, SFQ, LLQ
 *  - new policy: possibility to define a DSCP based rate limiter
 *  - new monitoring possibilities:
 *     - For UDP-based traffic
 *        + Average, instantaneous, minimum and frequency distributed OWD
 *        + Average, instantaneous, minimum and frequency distributed IPDV
 *     - For TCP-based traffic
 *        + TCP Goodput on a DSCP basis
 *        + TCP Round-Trip Time on a DSCP basis, both instantaneous value 
 *          and frequency distribution
 *        + TCP Window Size on a DSCP basis, both instantaneous value 
 *          and frequency distribution
 *     - per-hop parameters:
 *        + Instantaneous and average queue length on a queue basis 
 *          or on a queue and drop precedence level basis
 *        + Maximum burstiness for queue 0
 *        + Departure rate on a queue basis or on a queue and drop level 
 *          precedence basis
 *        + Received packets, transmitted packets, dropped packets due to droppers 
 *          and dropped packets due to buffer overflow, 
 *          all on a DSCP basis and for both absolute and percentage values
 *
 *************************************************************************************** 
 */
/*
 * Copyright (c) 2000 Nortel Networks
 * 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 Nortel Networks.
 * 4. The name of the Nortel Networks may not be used
 *    to endorse or promote products derived from this software without
 *    specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY NORTEL 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 NORTEL 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.
 *
 * Developed by: Farhan Shallwani, Jeremy Ethridge
 *               Peter Pieda, and Mandeep Baines
 * Maintainer: Peter Pieda <[e-mail]>
 */

#include <stdio.h>
#include <stdlib.h>
#include <fstream>
#include "ip.h"
#include "dsred.h"
#include "delay.h"
#include "random.h"
#include "flags.h"
#include "tcp.h"
#include "dsredq.h"


/*------------------------------------------------------------------------------
dsREDClass declaration. 
    Links the new class in the TCL heirarchy.  See "Notes And Documentation for 
ns-2."
------------------------------------------------------------------------------*/
static class dsREDClass : public TclClass {
public:
	dsREDClass() : TclClass("Queue/dsRED") {}
	TclObject* create(int, const char*const*) {
		return (new dsREDQueue);
	}
} class_dsred;


/*------------------------------------------------------------------------------
dsREDQueue() Constructor.
    Initializes the queue.  Note that the default value assigned to numQueues 
in tcl/lib/ns-default.tcl must be no greater than MAX_QUEUES (the physical 
queue array size).
------------------------------------------------------------------------------*/
dsREDQueue::dsREDQueue() : de_drop_(NULL), link_(NULL)   {

	
	bind("numQueues_", &numQueues_);
	bind_bool("ecn_", &ecn_);

	bind("PacketSize_",   &PacketSize_);
	bind("DSCP_",         &DSCP_);
	bind("MBS0_",         &redq_[0].qMaxBur); 

	int i;

	for(i=0;i<MAX_CP;i++){
		stats.TCPrttFD_CP[i]	= NULL;
		stats.TCPcwndFD_CP[i]	= NULL;
   }
		
	

	numQueues_=1; 
   	QScheduler = new dsRR(numQueues_);
   	for(i=0;i<MAX_QUEUES;i++) phisQueueLimit[i]=0;
   	phbEntries = 0;		// Number of entries in PHB table
	if (link_)
		for (int i = 0; i < MAX_QUEUES; i++)
			redq_[i].setPTC(link_->bandwidth());
	reset();
   	
}


void dsREDQueue::reset() {
	int i;

	QScheduler->Reset();
	stats.drops = 0;
	stats.edrops = 0;
	stats.pkts = 0;

	for(i=0;i<MAX_CP;i++){
		stats.drops_CP[i]	= 0;
		stats.edrops_CP[i]	= 0;
		stats.pkts_CP[i]	= 0;
		stats.TCPnReTX_CP[i]	= 0;
		stats.TCPbReTX_CP[i]	= 0;
		stats.TCPbGoTX_CP[i]	= 0;
		stats.TCPcwnd_CP[i]	= 0;
//		stats.TCPrttFD_CP[i]	= NULL;
//		stats.TCPcwndFD_CP[i]	= NULL;
	}

	for (i = 0; i < MAX_QUEUES; i++)
		redq_[i].qlim = ((phisQueueLimit[i]==0)?limit():phisQueueLimit[i]);
	
	// Compute the "packet time constant" if we know the
	// link bandwidth.  The ptc is the max number of (avg sized)
	// pkts per second which can be placed on the link.
	Queue::reset();
}


/*------------------------------------------------------------------------------
void edrop(Packet* pkt)
    This method is used so that flowmonitor can monitor early drops.
------------------------------------------------------------------------------*/
void dsREDQueue::edrop(Packet* p)
{
	if (de_drop_ != 0) de_drop_->recv(p);
	else drop(p);
}


/*------------------------------------------------------------------------------
void enque(Packet* pkt) 
    The following method outlines the enquing mechanism for a Diffserv router.
This method is not used by the inheriting classes; it only serves as an 
outline.
------------------------------------------------------------------------------*/
void dsREDQueue::enque(Packet* pkt) {
   int codePt, queue, prec;
   hdr_ip* iph = hdr_ip::access(pkt);
   hdr_cmn* cmn = hdr_cmn::access(pkt); 
   //packet_t ptype=cmn->ptype(), aptype=cmn->app_type();
   codePt = iph->prio();	//extracting the marking done by the edge router
   int ecn = 0;
   int enqueued=0;	

   //looking up queue and prec numbers for that codept
   lookupPHBTable(codePt, &queue, &prec);	

   // code added for ECN support
   //hdr_flags* hf = (hdr_flags*)(pkt->access(off_flags_));
   // Changed for the latest version instead of 2.1b6
   hdr_flags* hf = hdr_flags::access(pkt);

   if (ecn_ && hf->ect()) ecn = 1;

	stats.pkts_CP[codePt]++;
	stats.pkts++;

   switch(redq_[queue].enque(pkt, prec, ecn)) {
      case PKT_ENQUEUED:
	 enqueued=1;
         break;
      case PKT_DROPPED:
         stats.drops_CP[codePt]++;
	 stats.drops++;
         drop(pkt);
         break;
      case PKT_EDROPPED:
	 stats.edrops_CP[codePt]++;
	 stats.edrops++;
         edrop(pkt);
         break;
      case PKT_MARKED:
	 enqueued=1;
         hf->ce() = 1; 	// mark Congestion Experienced bit		
         break;			
      default:
         break;
   }

  if (enqueued==1) {QScheduler->EnqueEvent(pkt, queue); 
  	PacketSize_ = cmn->size();
	DSCP_= codePt;
	if (cmn->ptype()==PT_TCP) {		
		hdr_tcp *tcp=hdr_tcp::access(pkt);
		stats.TCPcwnd_CP[DSCP_]=tcp->cwnd();
		stats.TCPrtt_CP[DSCP_]=tcp->t_rtt();

		if (stats.TCPrttFD_CP[DSCP_]!=NULL) {
			if (stats.TCPrtt_CP[DSCP_]>0) 
				 stats.TCPrttFD_CP[DSCP_]->occurency(stats.TCPrtt_CP[DSCP_]);
				 stats.TCPcwndFD_CP[DSCP_]->occurency(stats.TCPcwnd_CP[DSCP_]);
			}

			if (tcp->reason()!=0) { 
				stats.TCPnReTX_CP[DSCP_]++;
				stats.TCPbReTX_CP[DSCP_]+=cmn->size()/1024.0;
			} else stats.TCPbGoTX_CP[DSCP_]+=cmn->size()/1024.0;	
		}			

   }

	
}


/*------------------------------------------------------------------------------
Packet* deque() 
    This method implements the dequing mechanism for a Diffserv router.
------------------------------------------------------------------------------*/
Packet* dsREDQueue::deque() {
	Packet *p=NULL;
	int queue, prec;
   	hdr_ip* iph;
   	int fid;

	int qToDq=QScheduler->DequeEvent();

	// Dequeue a packet from the underlying queue:
	if (qToDq >= 0) {
		p = redq_[qToDq].deque();
      		iph = hdr_ip::access(p);
      		fid = iph->flowid()/32;

      		/* There was a packet to be dequed;
         	   find the precedence level (or virtual queue)
         	   to which this packet was attached:
      		*/
      		lookupPHBTable(getCodePt(p), &queue, &prec);

      		// update state variables for that "virtual" queue
      		redq_[qToDq].updateREDStateVar(prec);

      		QScheduler->UpdateDepartureRate(qToDq, prec, hdr_cmn::access(p)->size());
		//printf("dep rate %d %d %f\n",qToDq,prec,QScheduler->GetDepartureRate(qToDq,prec));		
	}

	// Return the dequed packet:	
	return(p);
}


/*------------------------------------------------------------------------------
int getCodePt(Packet *p) 
    This method, when given a packet, extracts the code point marking from its 
header.
------------------------------------------------------------------------------*/
int dsREDQueue::getCodePt(Packet *p) {
	hdr_ip* iph = hdr_ip::access(p);
	return(iph->prio());
}


/*------------------------------------------------------------------------------
void lookupPHBTable(int codePt, int* queue, int* prec)
    Assigns the queue and prec parameters values corresponding to a given code 
point.  The code point is assumed to be present in the PHB table.  If it is 
not, an error message is outputted and queue and prec are undefined.
------------------------------------------------------------------------------*/
void dsREDQueue::lookupPHBTable(int codePt, int* queue, int* prec) {
   for (int i = 0; i < phbEntries; i++) {
      if (phb_[i].codePt_ == codePt) {
         *queue = phb_[i].queue_;
         *prec = phb_[i].prec_;
         return;
      }
   }
   printf("ERROR: No match found for code point %d in PHB Table.\n", codePt);
}


/*------------------------------------------------------------------------------
void addPHBEntry(int codePt, int queue, int prec)
    Add a PHB table entry.  (Each entry maps a code point to a queue-precedence
pair.)
------------------------------------------------------------------------------*/
void dsREDQueue::addPHBEntry(int codePt, int queue, int prec) {
	if (phbEntries == MAX_CP) {
      printf("ERROR: PHB Table size limit exceeded.\n");
	} else {
		phb_[phbEntries].codePt_ = codePt;
		phb_[phbEntries].queue_ = queue;
		phb_[phbEntries].prec_ = prec;
		stats.valid_CP[codePt] = 1;
		phbEntries++;
	}
}


/*------------------------------------------------------------------------------
void getStat(int argc, const char*const* argv) 
    
------------------------------------------------------------------------------*/
double dsREDQueue::getStat(int argc, const char*const* argv) {

	if (argc == 3) {
		if (strcmp(argv[2], "drops") == 0)
         return (stats.drops*1.0);