dsred.cc

区分服务的路由算法

/*
 * 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 "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_);
	int i;

	numPrec = MAX_PREC;
   schedMode = schedModeRR;

    for(i=0;i<MAX_QUEUES;i++){
	queueMaxRate[i] = 0;
	queueWeight[i]=1;
    }
		
    wfq_event = 0;
    v_time = sum = 0;
    last_vt_update = 0;
    idle = 1;
    queuesDone = MAX_QUEUES;
    phbEntries = 0;		// Number of entries in PHB table
    reset();
}


/*------------------------------------------------------------------------------
void edrop(Packet* pkt)
    This method is used so that flowmonitor can monitor early drops.
------------------------------------------------------------------------------*/
void dsREDQueue::reset() {
	int i;

	qToDq = 0;		// q to be dequed, initialized to 0	

    for(i=0;i<MAX_QUEUES;i++){
	queueAvgRate[i] = 0.0;
	queueArrTime[i] = 0.0;
	slicecount[i]=0;
	pktcount[i]=0;
	wirrTemp[i]=0;
	wirrqDone[i]=0;
	finish_t[i]=0.0;
	B[i]=0;

    }
    
    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;
    }

    for (i = 0; i < MAX_QUEUES; i++)
	redq_[i].qlim = limit();

	// 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.
	if (link_)
	    for (int i = 0; i < MAX_QUEUES; i++)
		redq_[i].setPTC(link_->bandwidth());
		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 applyTSWMeter(Packet *pkt)
Pre: policy's variables avgRate, arrivalTime, and winLen hold valid values; and
  pkt points to a newly-arrived packet.
Post: Adjusts policy's TSW state variables avgRate and arrivalTime (also called
  tFront) according to the specified packet.
Note: See the paper "Explicit Allocation of Best effor Delivery Service" (David
  Clark and Wenjia Fang), Section 3.3, for a description of the TSW Tagger.
------------------------------------------------------------------------------*/
void dsREDQueue::applyTSWMeter(Packet *pkt) {
	double now, bytesInTSW, newBytes;
	hdr_cmn* hdr = hdr_cmn::access(pkt);
	double winLen = 1.0;

	bytesInTSW = queueAvgRate[qToDq] * winLen;
	newBytes = bytesInTSW + (double) hdr->size();
	now = Scheduler::instance().clock();
	queueAvgRate[qToDq] = newBytes / (now - queueArrTime[qToDq] + winLen);
	queueArrTime[qToDq] = now;
	
}


/*------------------------------------------------------------------------------
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);
   codePt = iph->prio();	//extracting the marking done by the edge router
   int ecn = 0;
   int enqueued;
   static double lastu[2]={0,0};
   double now;

   //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);
   // WFQ packet size
   hdr_cmn *hdr = hdr_cmn::access(pkt);
   int size = hdr->size();
	now = Scheduler::instance().clock();
   
   if (ecn_ && hf->ect()) ecn = 1;

    stats.pkts_CP[codePt]++;
    stats.pkts++;
    enqueued=0;
   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:
         hf->ce() = 1; 	// mark Congestion Experienced bit		
          enqueued=1;
         break;			
      default:
          printf("Error !!!\n", now);
         break;
   }

   if( schedMode == schedModeWFQ && enqueued) {

    // virtual time update
    // formula 10 in "virtual time implementation" paragraph
	if(idle) {
		v_time=0;
		last_vt_update=now;
		idle=0;
	} else {
		v_time=v_time+(now-last_vt_update)/sum;
		last_vt_update=now;
	}
    // finish time computation
    // implements formula 11 
	finish_t[queue] = (finish_t[queue] > v_time ? 
			finish_t[queue]:v_time)
			+(double)size/queueWeight[queue]/(link_->bandwidth()/8.0);
    // 1/(link_->bandwidth()/8) - real processing time of entire packet

    // update sum and B
	if( (B[queue]++) ==0 )
		sum=sum+queueWeight[queue];
	if ( fabs(sum) < 1.0/1000.0 ) sum=0;

    // insertion in both lists
	PGPS_queueID_l.insert_order(queue,finish_t[queue],queue);
	 GPS_queueID_l.insert_order(queue,finish_t[queue],queue);
    // schedule next departure in the GPS reference system
	if(wfq_event!=0) {
		Scheduler::instance().cancel(wfq_event);
		delete wfq_event;
	} 
	scheduleWFQ();
   }
 
}


/*------------------------------------------------------------------------------
Packet* deque() 
    This method implements the dequing mechanism for a Diffserv router.
------------------------------------------------------------------------------*/
Packet* dsREDQueue::deque() {
    Packet *p;
    int queue, prec;
	// Select queue to deque in a round robin manner:
	selectQueueToDeque();
	// Dequeue a packet from the underlying queue:
	p = redq_[qToDq].deque();

	if (p != 0) {
	    pktcount[qToDq]+=1;

	    if (schedMode==schedModePRI && queueMaxRate[qToDq]) applyTSWMeter(p);
      /* 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);
	}

	// 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 selectQueueToDeque(void) 
    This method determines the next queue in line to be dequed.
------------------------------------------------------------------------------*/
void dsREDQueue::selectQueueToDeque() {
   // If the queue to be dequed has no elements, look for the next queue in line:
   int i = 0;
    static int cnt=0;
   if(schedMode==schedModeRR){
		qToDq = ((qToDq + 1) % numQueues_);
      while ((i < numQueues_) && (redq_[qToDq].getRealLength() == 0)) {
			qToDq = ((qToDq + 1) % numQueues_);			
         i++;
      }
   }
   else if (schedMode==schedModeWRR) {
      if(wirrTemp[qToDq]<=0){
  	      qToDq = ((qToDq + 1) % numQueues_);
     	   wirrTemp[qToDq] = queueWeight[qToDq] - 1;
		} else {
			wirrTemp[qToDq] = wirrTemp[qToDq] -1;
		}			
      while ((i < numQueues_) && (redq_[qToDq].getRealLength() == 0)) {
			wirrTemp[qToDq] = 0;
  	      qToDq = ((qToDq + 1) % numQueues_);
     	   wirrTemp[qToDq] = queueWeight[qToDq] - 1;
			i++;
		}

   }
   else if (schedMode==schedModeWIRR) {
      qToDq = ((qToDq + 1) % numQueues_);
		while ((i<numQueues_) && ((redq_[qToDq].getRealLength()==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;
          }   	
      }
   }	else if (schedMode==schedModeWFQ) {
	       qToDq = PGPS_queueID_l.get_data_min();
	       PGPS_queueID_l.extract();
	       
   }
	else if (schedMode==schedModePRI) {
		qToDq = 0;