dsscheduler.cc.svn-base

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) 2001-2006  Sergio Andreozzi
 *
 * This program 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.
 *
 * 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., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 * GNU Licenses: http://www.gnu.org/licenses/gpl.txt
 *
*/


#include "dsconsts.h"
#include "dsscheduler.h"


/*  Scheduler class 
*/

/* helpful functions */
#define max(x,y) ((x>y)?x:y)
#define min(x,y) ((x>y)?y:x)
#define MAXDOUBLE 100000000.0

dsScheduler::dsScheduler(int NQ)
{  winLen=1; 
   initMeter();
}

dsScheduler::dsScheduler(int NQ, double LBw)
{  winLen=1; 
   initMeter();
}

dsScheduler::dsScheduler(int NQ, double LBw, const char* PFQSchedType)
{  winLen=1; 
   initMeter();
}

void dsScheduler::initMeter()
{ for (int i=0; i<MAX_QUEUES; i++) {
	queueAvgRate[i]=0;
	for (int j=0; j<MAX_PREC; j++) qpAvgRate[i][j]=0;
  
  }
}

void dsScheduler::applyTSWMeter(int PSize, double *AvgRate, double *ArrTime)
{
	double now, bytesInTSW, newBytes;
	bytesInTSW = *AvgRate * winLen;
	newBytes = bytesInTSW+PSize;
	now = Scheduler::instance().clock();
	*AvgRate = newBytes/ (now - *ArrTime + winLen); // in bytes
	*ArrTime = now;
}	


void dsScheduler::UpdateDepartureRate(int Queue, int Prec, int PSize)
{
 for (int i=0; i<NumQueues; i++) {
	applyTSWMeter((i==Queue) ? PSize : 0, &queueAvgRate[i], &queueArrTime[i]); 
	for (int j=0; j<MAX_PREC; j++)
		applyTSWMeter( ((i==Queue)&&(j==Prec)) ? PSize : 0, &qpAvgRate[i][j], &qpArrTime[i][j]); 
 }
}

double dsScheduler::GetDepartureRate(int Queue, int Prec) 
{ // printf("avg rate %f\n",qpAvgRate[Queue][Prec]);
   if (Prec==-1)    return(queueAvgRate[Queue]*8);
   else return(qpAvgRate[Queue][Prec]*8);  // in bit per seconds
}

dsRR::dsRR(int NQ):dsScheduler(NQ) 
{	
	NumQueues=NQ;	
	for (int i=0; i<MAX_QUEUES; i++) queueLen[i]=0;
	qToDq=-1;
        Reset();
}

void dsRR::Reset()
{
  
}

int dsRR::DequeEvent()
{  int i=0; 
   qToDq = ((qToDq + 1) % NumQueues);
   while ((i < NumQueues) && (queueLen[qToDq] == 0)) {
			qToDq = ((qToDq + 1) % NumQueues);			
   			i++;
   }
   if (i==NumQueues) return(-1); else {queueLen[qToDq]--; return qToDq;}
}

void dsRR::EnqueEvent(Packet* pkt, int Queue)
{
   queueLen[Queue]++; 
}

dsWRR::dsWRR(int NQ):dsScheduler(NQ) 
{	
	NumQueues=NQ;	
	for (int i=0; i<MAX_QUEUES; i++) {queueLen[i]=0; queueWeight[i]=1;}
	qToDq=0;
        Reset();
}

void dsWRR::Reset()
{  for (int i=0; i<MAX_QUEUES; i++) {wirrTemp[i]=0;}
}

int dsWRR::DequeEvent()
{    int i=0;
     if (wirrTemp[qToDq]<=0){
  	      qToDq = ((qToDq + 1) % NumQueues);
     	      wirrTemp[qToDq] = queueWeight[qToDq] - 1;
      } else wirrTemp[qToDq] = wirrTemp[qToDq] -1;
					
      while ((i < NumQueues) && (queueLen[qToDq] == 0)) {
			wirrTemp[qToDq] = 0;
  	      		qToDq = ((qToDq + 1) % NumQueues);
     	       		wirrTemp[qToDq] = queueWeight[qToDq] - 1;
			i++;
      }
       if (i==NumQueues) return(-1); else {queueLen[qToDq]--; return qToDq;}
}

void dsWRR::EnqueEvent(Packet* pkt, int Queue)
{
   queueLen[Queue]++; 
}

dsWIRR::dsWIRR(int NQ):dsScheduler(NQ) 
{	
	NumQueues=NQ;	
   	queuesDone = MAX_QUEUES;
	for (int i=0; i<MAX_QUEUES; i++) {queueLen[i]=0; queueWeight[i]=1;}
	qToDq=0;
        Reset();
}

void dsWIRR::Reset()
{     for(int i=0;i<MAX_QUEUES;i++){
		slicecount[i]=0;
      		wirrTemp[i]=0;
      		wirrqDone[i]=0;
      }
}

int dsWIRR::DequeEvent()
{    int i=0;
     qToDq = ((qToDq + 1) % NumQueues);
     while ((i<NumQueues) && ((queueLen[qToDq]==0) || (wirrqDone[qToDq]))) {
			if (!wirrqDone[qToDq]) {
				queuesDone++;
				wirrqDone[qToDq]=1;
			}
  	      		qToDq = ((qToDq + 1) % NumQueues);
			i++;
      }
      if (wirrTemp[qToDq] == 1) {
  	       queuesDone +=1;
          wirrqDone[qToDq]=1;
      }
      wirrTemp[qToDq]-=1;
      if(queuesDone >= NumQueues) {
          queuesDone = 0;
          for(i=0;i<NumQueues;i++) {
  	       wirrTemp[i] = queueWeight[i];
     	       wirrqDone[i]=0;
          }   	
      }
      if (i==NumQueues) return(-1); else {queueLen[qToDq]--; return(qToDq);}
}

void dsWIRR::printWRRcount() {

   for (int i = 0; i < NumQueues; i++){
      printf("%d: %d %d %d.\n", i, slicecount[i],queueLen[i],queueWeight[i]);
   }
}


void dsWIRR::EnqueEvent(Packet* pkt, int Queue)
{
   queueLen[Queue]++; 
}


dsPQ::dsPQ(int NQ, double WinLen):dsScheduler(NQ, WinLen)
{	
	NumQueues=NQ;	
	winLen=WinLen; 
	for (int i=0; i<MAX_QUEUES; i++) {
		queueMaxRate[i]=0;
		queueLen[i]=0;
        }
	Reset();

}

void dsPQ::Reset()
{
  for(int i=0;i<MAX_QUEUES;i++)	queueArrTime[i] = 0.0;
}

int dsPQ::DequeEvent()
{ 
   int qToDq=0, i=0;
   while ((i < NumQueues) && ((queueLen[qToDq] == 0) ||
	((queueAvgRate[qToDq] > queueMaxRate[qToDq]) && queueMaxRate[qToDq]))) {
	       i++;
	       qToDq = i;
	}
	if (i == NumQueues) {
		i = qToDq = 0;			
		while ((i < NumQueues) && (queueLen[qToDq] == 0)) {
				qToDq = ((qToDq + 1) % NumQueues);
				i++;
		}
	}
    if (i<NumQueues) {
        queueLen[qToDq]--;   
        return qToDq; 
    } else 
    {return(-1); printf("PRIORITY SCHEDULER: no packet to be dequeued\n");}  // no packet to be dequeued
}

void dsPQ::EnqueEvent(Packet* pkt, int Queue)
{
   queueLen[Queue]++; 
}

dsWFQ::dsWFQ(int NQ, double LBw):dsScheduler(NQ, LBw) 
{	
	NumQueues=NQ;	
	LinkBandwith=LBw;
	for (int i=0; i<MAX_QUEUES; i++) {
		fs_[i].weight_=1;
		fs_[i].B=0;	
	}  	
  	v_time = 0; 
  	idle = 1;
  	wfq_event = 0;
  	sum = 0;
  	last_vt_update = 0;	sessionDelay=0;
  	GPSDeparture=-1;	

	Reset(); 
}

void dsWFQ::Reset()