wfq.cc

c＋＋编写的ns环境下关于wfq算法的仿真源代码

/*
 * Copyright (c) 1999-2000 Paolo Losi ([e-mail])
 *
 * Copyright (c) 2001-2005 Paolo Losi ([e-mail])
 *                         Alexander Sayenko ([e-mail])
 *
 * All rights reserved
 *
 * 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.
 */

#include <wfq.h>

WFQ::WFQ() : GPS_hand(this),
             GPS_event(0),
             idle(1),
             virt_time(0),
             last_vt_update(0),
             sum(0),
             wfq_classifier(NULL) 
{
	bind_bw("bandwidth_",&bandwidth);
}

/*
 * Interface to otcl: implements "install" command 
 * to install the classifier 
 */
int WFQ::command(int argc,const char*const* argv) 
{ 
 if (argc==3) {
   if(strcmp(argv[1],"install")==0) {

     wfq_classifier = (WFQAggregClassifier *)TclObject::lookup(argv[2]);
     return TCL_OK;
   }
 }

 return(Queue::command(argc,argv));
}


void WFQ::updateSum ()
{
  sum = 0;

  std::map<unsigned int, WFQClass*>::iterator i = 
    wfq_classifier->mWFQClasses.begin ();

  while (i != wfq_classifier->mWFQClasses.end()) {
    if (i->second->B)
      sum += i->second->mWeight;

    i++;    
  }

  return;
}

			
void WFQ::enque(Packet *p) 
{
  /*
   * Check that the classifier has been installed.
   * Otherwise, just drop a packet
   */
  if (!wfq_classifier) {
    drop (p);
    return;
  }

  /*
   * Ask the classifier to detemine the class a packet belongs to
   */
  WFQClass* wfq_class = wfq_classifier->get_queue(p); 


  /*
   * If a class cannot be determined, then just drop a packet
   */
  if (!wfq_class) {
    drop (p);
    return;
  }

  /*
   * Queue length management:
   * note that B is not suited for this porpouse since 
   * it contains the n. of packet in the GPS reference system.
   */
  if (wfq_class->mMaxLength < wfq_class->mPackets+1 ) {
    drop(p);
    return;
  }

  wfq_class->mPackets++;

  /*
   * End of queue length management
   */
  hdr_cmn *hdr = hdr_cmn::access(p);
  int size = hdr->size();

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

  /*
   * Virtual time update
   * formula 10 in "virtual time implementation" paragraph
   */
  if(idle) {
    last_vt_update=now;
    virt_time=0;
    idle=0;
  } else {
    virt_time=virt_time+(now-last_vt_update)/sum;
    last_vt_update=now;
  }
	
  /*
   * Let's compute finish time
   * implements formula 11 
   */

  wfq_class->mFinishTime = 
   (wfq_class->mFinishTime > virt_time ? wfq_class->mFinishTime : virt_time)
   + size / wfq_class->mWeight / (bandwidth/8);

  /*
   * Update B and sum
   */
  wfq_class->B++;
  updateSum ();

  if ( fabs(sum) < wfq_classifier->get_safe_limit() ) sum=0;


  /*
   * Insertion in both lists
   */ 
  PGPS_pack_l.insert_order(p,wfq_class->mFinishTime,wfq_class->mID);
  GPS_queueID_l.insert_order(wfq_class->mID,wfq_class->mFinishTime,wfq_class->mID);

  /*
   * Schedule next departure in the GPS reference system
   */ 
  if (GPS_event != 0) {
    Scheduler::instance().cancel(GPS_event);
    delete GPS_event;
  } 

  scheduleGPS();
}


void WFQ::scheduleGPS() 
{
  GPS_event=new Event();
       
  /*
   * Implements last unnumbered formula in 
   * "Virtual Time Implemetation" paragraph
   * "GPS Approach to flow...:single node case"  Parekh e Gallager
   */
  double tmp=(GPS_queueID_l.get_key_min()-virt_time)*sum;
	
  /*
   * following line is there to recover errors due to finite precision	
   */
  if (tmp<0) tmp=0;

  Scheduler::instance().schedule((Handler *)&GPS_hand,GPS_event,tmp);
}


void WFQ::handle(Event *e) 
{
  double now = Scheduler::instance().clock();
	
  /*
   * Update virtual time
   */
  virt_time=virt_time+(now-last_vt_update)/sum;
  last_vt_update=now;

  /*
   * Extract packet in GPS system
   */
  int queueid=GPS_queueID_l.get_data_min();
  GPS_queueID_l.extract();

  /*
   * Update B and sum
   */ 
  wfq_classifier->mWFQClasses[queueid]->B--;

  updateSum ();

  if ( fabs(sum) < wfq_classifier->get_safe_limit() ) sum=0;
    if(sum==0) {
      idle=1;

      std::map<unsigned int, WFQClass*>::iterator i =
        wfq_classifier->mWFQClasses.begin ();
      while (i != wfq_classifier->mWFQClasses.end ()) {
        i->second->mFinishTime = 0;
        i++;
      }
  }

  /* 
   * if GPS is not idle, schedule next GPS departure
   */
  delete e;
  if(!idle) 
    scheduleGPS();
  else 
    GPS_event = 0;
}


Packet* WFQ::deque() 
{
  Packet* p=PGPS_pack_l.get_data_min();
  PGPS_pack_l.extract();

  /*
   * Queue length management
   */
  if (p) {
    WFQClass* wfq_class = wfq_classifier->get_queue (p);
    wfq_class->mPackets--;
  }

  return p;
}

	
inline void GPSHandler::handle(Event* e) { q->handle(e); }