wfq.cc

rsvp and wfq patch for Netowrk Simulator 2

/*
 * Copyright (c) 1998 The University of Bonn
 * All rights reserved.
 * 
 * Permission to use and copy this software in source and binary forms
 * is hereby granted, provided that the above copyright notice, this
 * paragraph and the following disclaimer are retained in any copies
 * of any part of this software and that the University of Bonn is
 * acknowledged in all documentation pertaining to any such copy
 * or derivative work. The name of the University of Bonn may not
 * be used to endorse or promote products derived from this software
 * without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 
 * EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, THE WARRANTIES OF 
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL 
 * THE UNIVERSITY OF BONN BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF 
 * OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 
 * SOFTWARE.
 */

#include "wfq.h"


static class WFQClassCl : public TclClass {
public:
  WFQClassCl() : TclClass("WFQClass") {}
  TclObject* create(int, const char*const*) {
    return (new WFQClass);
  }
} class_WFQClass;


WFQClass::WFQClass() : next_(0), bw_(0), next_time_(-1), last_time_(-1) {
  //bind("off_cmn_", &off_cmn_);
  bind("limit_", &qlim_);
  bind_bw("bw_", &bw_);
  q_ = new PacketQueue;
  size_ = 0;
}


/* Inserts a packet into the queue associated with the WFQClass and
   calculates the new size (in bytes). */
void WFQClass::enque(Packet *p) {
  //hdr_cmn *hdr = (hdr_cmn*)p->access(off_cmn_);
  hdr_cmn *hdr = hdr_cmn::access(p) ;
  q_->enque(p);
  size_ += hdr->size();
}


/* Removes a packet from the queue associated with the WFQClass
   and calculates the new size (in bytes). */
Packet *WFQClass::deque() {
  Packet *p = q_->deque();
  //hdr_cmn *hdr = (hdr_cmn*)p->access(off_cmn_);
  hdr_cmn *hdr = hdr_cmn::access(p) ;
  size_ -= hdr->size();
  return p;
}


/*
 * The function 'calculate_next_time()' is the 'heart' both of the
 * WFQ and WF2Q algorithms. It calculates the time at which the next
 * packet for the queue would complete service in the corresponding
 * GPS system.
 */
void WFQClass::calculate_next_time() {
  Packet *np = q_->head();
  //hdr_cmn *hdr = (hdr_cmn*)np->access(off_cmn_);
  hdr_cmn *hdr = hdr_cmn::access(np) ;
  last_time_ = next_time_;
  /* For packet i that arrives in a queue, the completion time 
   * c_time(i) is:
   * c_time(i) = max {(time() + size(i)/rate) ; (c_time(i-1) + size(i)/rate)}
   * Note that the size of a packet is measured in bytes while the bandwidth
   * is measured in bits per second, hence the 'size()*8' calculation in
   * the formula below.
   */
  if (Scheduler::instance().clock() > next_time_) {
    next_time_ = Scheduler::instance().clock() + hdr->size()*8 / bw_; } 
  else {
    next_time_ = next_time_ + hdr->size()*8 / bw_;
  }
}


/* 
 * There are no commands for the class WFQClass yet. This might
 * change later.
 */
int WFQClass::command(int argc, const char*const* argv) {
  return (Queue::command(argc, argv));
}


static class WFQCl : public TclClass {
public:
  WFQCl() : TclClass("Queue/WFQ") {}
  TclObject* create(int, const char*const*) {
    return (new WFQ);
  }
} class_WFQ;


WFQ::WFQ() : queue_list_(0) {
  // int i; - unused
  //bind("off_ip_", &off_ip_);
  //bind("off_cmn_", &off_cmn_);
  bind_bool("wf2q_", &wf2q_);
  bind_bool("best_effort_", &best_effort_);
  bind_bool("borrow_", &borrow_);
  bind_bool("prio_", &prio_);
  bind("num_classes_", &num_classes_);
  bind("num_flows_", &num_flows_);
  bind("num_drops_", &num_drops_);
  bind("size_drops_", &size_drops_);
  hash = new Hashtable(HASHBUCKETS);
}
 

/* 
 * New classes can be added to (or removed from) a WFQ link with
 * 'add WFQClass' (or 'remove WFQClass'). Flows can be assigned to
 * a class (or the assignment can be deleted) with 'bind WFQClass <flowid>'
 * (or 'unbind <flowid>').
 */
int WFQ::command(int argc, const char*const* argv) {
  Tcl& tcl = Tcl::instance();
  if (argc == 3) {
    // add WFQClass
    if (strcmp(argv[1], "add") == 0) {
      WFQClass *cl = (WFQClass*)TclObject::lookup(argv[2]);
      if (cl == NULL) {
	tcl.resultf("WFQ: no class object %s", argv[2]);
	return (TCL_ERROR);
      }
      insert(cl);
      num_classes_++;
      return (TCL_OK);
    }
    // remove WFQClass
    if (strcmp(argv[1], "remove") == 0) {
      WFQClass *cl = (WFQClass*)TclObject::lookup(argv[2]);
      if (cl == NULL) {
	tcl.resultf("WFQ: no class object %s", argv[2]);
	return (TCL_ERROR);
      }
      WFQClass *search = queue_list_;
      if (queue_list_ == NULL) {
	tcl.resultf("WFQ: no class object %s found in WFQ link", argv[2]);
	return (TCL_ERROR);
      }
      if (queue_list_ == cl) {
	queue_list_ = queue_list_->next_;
      } else {
	while ((search->next_ != NULL) && (search->next_ != cl)) {
	  search = search->next_;
	}
	if (search->next_ == NULL) {
	  tcl.resultf("WFQ: no class object %s found in WFQ link", argv[2]);
	  return (TCL_ERROR);
	}
	search->next_ = search->next_->next_;
      }
      num_classes_--;
      return (TCL_OK);
    }
    // getclass <flowid>
    if (strcmp(argv[1], "getclass") == 0) {
      WFQClass *cl;
      int fid = atoi(argv[2]);
      if ((cl = (WFQClass *)hash->lookup(fid)) == NULL) {
	tcl.resultf("");
      } else {
	tcl.resultf("%s", cl->name());
      }
      return (TCL_OK);
    }
  }
  if ((argc == 4) || (argc == 5)) {
    // bind WFQClass <priority>   or   bind WFQClass <src id> <flowid>
    if (strcmp(argv[1], "bind") == 0) {
      WFQClass *cl = (WFQClass*)TclObject::lookup(argv[2]);
      if (cl == NULL) {
	tcl.resultf("WFQ: no class object %s", argv[2]);
	return (TCL_ERROR);
      }
      WFQClass *search = queue_list_;
      while ((search != NULL) && (search != cl)) {
	search = search->next_;
      }
      if (search == NULL) {
	tcl.resultf("WFQ: no class object %s found in WFQ link", argv[2]);
	return (TCL_ERROR);
      }
      int fid = -1;
      if ((prio_) && (argc == 4)) {  
	fid = atoi(argv[3]);
      }
      if ((!prio_) && (argc == 5)) {
	fid = (atoi(argv[3]) + 1) * FLOWNUM + atoi(argv[4]);
      }
      if (fid == -1) {
	tcl.resultf("WFQ: Wrong number of arguments for bind");
	return (TCL_ERROR);
      }
      hash->insert(cl, fid);
      num_flows_++;
      return(TCL_OK);
    }
  }
  if ((argc == 3) || (argc == 4)) {
    // unbind <flowid>   or   unbind <src id> <flowid>
    if (strcmp(argv[1], "unbind") == 0) {
      int fid = -1;
      if ((prio_) && (argc == 3)) {  
	fid = atoi(argv[2]);
      }
      if ((!prio_) && (argc == 4)) {
	fid = (atoi(argv[2]) + 1) * FLOWNUM + atoi(argv[3]);
      }
      if (fid == -1) {
	tcl.resultf("WFQ: Wrong number of arguments for unbind");
	return (TCL_ERROR);
      }
      if (hash->lookup(fid) == NULL) {
	tcl.resultf("%s WFQ: No class assigned to flow %d", name(), fid);
	return (TCL_ERROR);
      }
      hash->remove(fid);
      num_flows_--;
      return(TCL_OK);
    }
  }
  return (Queue::command(argc, argv));
}


int WFQ::length() {
  WFQClass *s = queue_list_;
  int l;
  l = 0;
  while (s != NULL) {
    l += s->length();
    s = s->next_;
  }
  return l;
}


void WFQ::enque(Packet* p)
{
  int num;
  WFQClass *cl; // , *next; - next is unused
  int be;
  Tcl& tcl = Tcl::instance();
  // hdr_ip *hdr = (hdr_ip*)p->access(off_ip_);
  hdr_ip *hdr = hdr_ip::access(p) ;
  // Check if a class has been assigned to this flow/priority:
  if (prio_) {
    num = hdr->prio();
    cl = (WFQClass *)hash->lookup(num);
    if ((be = (cl == NULL))) {
      if (best_effort_) {
	cl = (WFQClass *)hash->lookup(0);
      } else {
	tcl.evalf("%s WFQ: unknown priority %u",name(), num);
      }
    }
  } else {
    // num = ((hdr->src() >> Address::instance().NodeShift_[1]) + 1) * FLOWNUM +
    num = ( hdr->saddr() + 1 ) * FLOWNUM + // SM
      hdr->flowid();